Research map / Learning theory and algorithms / Fairness
Disparate Conditional Prediction in Multiclass Classifiers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes the binary Disparate Conditional Prediction (DCP) fairness-auditing measure to multiclass classifiers and gives lower/upper bounds via sequential LP, both with known confusion matrices and with only population-level label/prediction frequencies.
Problem
Auditing multiclass classifiers for deviation from multiclass equalized odds when confusion matrices per protected sub-population are unavailable or the classifier is inaccessible; computing the multiclass DCP measure is non-convex and possibly intractable.
Approach
Extends DCP to multiclass by taking, per true label, the minimal baseline confusion row and a max over predicted labels of a per-entry deviation; computes a closed-form lower bound and an upper bound via a greedy initialization plus sequential linear programming (with a split of the non-smooth eta into two smooth parts), and a best-case minDCP for the setting without confusion matrices.
Key results
- Greedy+LM gives the tightest upper bound in nearly all experiments, with upper-to-lower bound ratios from 1.00 to 2.85 on US Census and 1.00 to 1.58 on Natality.
- Without confusion matrices, the minDCP local optimizer value was below the true DCP range in all but one US Census case (e.g., 0.97% vs 2.36-3.03% for an NN, 3 labels).
- Greedy initialization outperformed the weighted-average initialization on nearly all settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy initialization instead of weighted-average initialization, then run local minimization (ablation) | DCP upper-bound estimation for a decision tree · US Census (3 labels) | DCP upper bound: 14.07% -> 7.65% | Helped |
| Add local minimization after greedy initialization (ablation) | DCP upper-bound estimation for a decision tree · US Census (3 labels) | DCP upper bound: 9.65% -> 7.65% | Helped |
| Replace greedy initialization with weighted-average initialization (ablation) | DCP upper-bound estimation for a decision tree · US Census (3 labels) | DCP upper bound: 7.65% -> 27.19% | Hurt |
| Use greedy initialization instead of weighted-average initialization, then run local minimization (ablation) | DCP upper-bound estimation for a decision tree · Natality (Attendant protected attribute) | DCP upper bound: 2.10% -> 2.08% | Helped |
| Add local minimization after greedy initialization (ablation) | DCP upper-bound estimation for a decision tree · Natality (Attendant protected attribute) | DCP upper bound: 2.34% -> 2.08% | Helped |
| Initialize with the weighted average instead of the greedy method (ablation) | DCP upper-bound estimation · US Census and Natality experiments with known confusion matrices | DCP upper bound | Hurt |
Limitations
- Local optimization only reaches local minima of a non-convex problem, so the upper bound is not guaranteed tight.
- Bounds can be loose (ratios up to 2.85), with large gaps in some cases such as 8-label attribute.
- Requires a step-size/trust region parameter and removal of constraints heuristically; convergence analysis only for convex variant.
Experimental setup
Datasets: US Census Natality (US births 2017) UK general elections 1918-2019 US education data set
Benchmarks: US Census Natality UK elections US education
Metrics: upper bound lower bound best ratio (upper/lower) minDCP local optimizer value
Baselines: Average confusion matrix initialization Average+LM Greedy+LM
Builds on: Disparate Conditional Prediction (Sabato & Yom-Tov 2020) equalized odds (Hardt et al. 2016) sequential linear programming
Closest papers by meaning
- Demystifying the Optimal Fair Classifier in Multi-Class Classification (ICML 2026 · similarity 0.87)
- On the Maximal Local Disparity of Fairness-Aware Classifiers (ICML 2024 · similarity 0.87)
- On Fairness and Calibration (NeurIPS 2017 · similarity 0.86)
- Kernel-based Equalized Odds: A Quantification of Accuracy-Fairness Trade-off in Fair Representation Learning (NeurIPS 2025 · similarity 0.85)
- FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation (ICML 2025 · similarity 0.85)
- Efficient Fairness-Performance Pareto Front Computation (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.