Research map / Adversarial robustness and security / Certified and empirical robustness
Optimal Fair Learning Robust to Adversarial Distribution Shift
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.
Theoretical study showing the randomized Fair Bayes Optimal Classifier (for demographic parity, equal opportunity, predictive equality) is locally Lipschitz robust to adversarial distribution shift, while the deterministic Fair BOC is not.
Problem
Robustness of accuracy and group-fairness guarantees of the optimal (Fair Bayes Optimal) binary classifier under adversarial/malicious noise in the data distribution, which is unclear once fairness constraints are added.
Approach
Shows deterministic Fair BOCs can be non-robust (accuracy jumps by Omega(1) under tiny TV shift), but the randomized Fair BOC, which is randomized on at most one domain point, has accuracy that is Lipschitz in total variation distance with a distribution-dependent constant, via decomposition of shifts into elementary mass transfers and a mass-threshold analysis.
Key results
- Theorem 1 gives DP-Fair BOC accuracy Lipschitz bound: |Acc(f_P,P) - Acc(f_P',P')| <= TV * (1 + max(P(A),P'(A))/min(P(A),P'(A)) + max(P(D),P'(D))/min(P(D),P'(D))).
- Claim 1 shows deterministic DP-Fair BOC accuracy can change by Omega(1) under TV shift of epsilon, while randomized Fair BOC is robust.
- The randomized Fair BOC is randomized on at most one domain point and can be computed in O(|X| log|X|) time, whereas computing the deterministic Fair BOC is NP-complete.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a randomized Fair BOC instead of a deterministic Fair BOC | Fair classification with Demographic Parity · Example 1 | accuracy: 0.5 − ϵ | Helped |
| Add Demographic Parity constraints to the deterministic BOC | Deterministic BOC · Adversarial distribution shift | accuracy difference across distributions: |Acc(f, P) − Acc(f′, P′)| ≥ Ω(1) | Hurt |
| Use a randomized Fair BOC under Demographic Parity | Fair BOC · Adversarial distribution shift | accuracy difference across distributions: \epsilon (1 + max (P(A), P′(A))/min(P(A), P′(A)) + max (P(D), P′(D))/min(P(D), P′(D))) | Helped |
| Use a randomized Fair BOC under Equal Opportunity | Fair BOC · Adversarial distribution shift | accuracy difference across distributions: \epsilon (1 + 2 max(P(1), P′(1))K(P, P′)) | Helped |
Surprising findings
- Deterministic Fair BOC accuracy can jump by about 0.5 under arbitrarily small distribution shift, unlike the unconstrained BOC.
- The randomized Fair BOC is nearly deterministic, randomizing on at most one point of the domain.
Limitations
- Results are local Lipschitz with constants that blow up when group masses become very small.
- Only binary classification and two groups are analyzed; no experiments validate the theory.
Experimental setup
Baselines: Blum et al. (2024) randomized closure PQ(H) Xian & Zhao (2024) sensitivity analysis Chen et al. (2024) deterministic Fair BOC
Builds on: Kearns & Li (1988) malicious noise Agarwal & Deshpande (2022) Fair BOC characterization Konstantinov & Lampert (2022)
Closest papers by meaning
- On the Alignment between Fairness and Accuracy: from the Perspective of Adversarial Robustness (ICML 2025 · similarity 0.87)
- Enhancing Robust Fairness via Confusional Spectral Regularization (ICLR 2025 · similarity 0.87)
- Can Private Machine Learning Be Fair? (AAAI 2025 · similarity 0.87)
- On the Fairness ROAD: Robust Optimization for Adversarial Debiasing (ICLR 2024 · similarity 0.87)
- How Far Can Fairness Constraints Help Recover From Biased Data? (ICML 2024 · similarity 0.86)
- Preserving AUC Fairness in Learning with Noisy Protected Groups (ICML 2025 · similarity 0.86)
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.