Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· 0 citations· 26 references
Abstract
When a classifier is trained by actively choosing which examples to label, should its labeling budget depend on which notion of fairness it must satisfy? We answer this with the first information-theoretic lower bounds for group-fair active learning, and the answer is a sharp hierarchy across the three standard notions. Demographic Parity (DP), which equalizes the positive prediction rate across groups, can be verified from unlabeled data alone, so it adds no labels beyond ordinary learning. Equal Opportunity (EO), which equalizes each group's true positive rate, is fundamentally harder: estimating a rate conditioned on the true label forces the learner to collect labeled positives from every group, an irreducible cost that no query strategy can avoid. Equalized Odds (EqOdds), which additionally equalizes false positive rates, costs no more than EO whenever positives are the minority, the typical regime. This exposes a separation at the heart of fair learning: active querying yields the well-known exponential savings for accuracy, but no speedup whatsoever for fairness verification. Concretely, certifying EO to fairness tolerance γ requires Ω(d/ε2 + k/(ε2 p+)) labels, where d is the model's Vapnik--Chervonenkis (VC) dimension, k the number of groups, ε the target error, and p+ = Pr[Y=1] the positive rate; the fairness term is independent of ε, so it is a floor that active learning cannot lower. We give matching algorithms (ConstrainedERM-DP for DP, FairStratified for EO and EqOdds) that are tight up to logarithmic factors. The cost is largest exactly when positives are rare: at p+ = 0.01, as in fraud detection, EO demands roughly 90× more labels than DP. Experiments on Folktables, COMPAS, and Adult confirm the predicted scaling and yield 36 to 39% label savings over passive fair-learning baselines.
Differential privacy (DP) is increasingly deployed to limit membership inference risk in machine-learning systems. Prior work has shown that DP-SGD can widen accuracy disparities across demographic groups, but this framing treats fairness as a purely outcome-side concern. We argue that privacy cost, the information leakage borne by each group, is itself a form of harm, and adopt a compensatory-fairness framework in which a group that involuntarily bears greater privacy exposure is owed proportionally greater benefit from the system. From this principle we derive the \emph{Privacy-Cost Equity Ratio} (PCER), a group fairness metric defined as a group's positive prediction rate normalized by its per-group overfitting gap. By a standard membership inference bound, this overfitting gap upper-bounds each group's vulnerability to inference attacks, making PCER a conservative measure of benefit relative to exposure. PCER needs only per-group train and test accuracy (no shadow models), making it a practical post-hoc audit tool. We evaluate PCER alongside standard fairness metrics across six benchmark--attribute combinations spanning tabular and NLP domains, under DP-SGD at a range of privacy budgets, and validate the overfitting-gap proxy against a direct threshold membership-inference attack. The results reveal patterns that outcome-based metrics miss. On COMPAS, PCER uncovers a persistent double disadvantage: the protected group bears both greater privacy exposure and worse predictive outcomes, something demographic parity gap masks entirely. Sensitivity analysis shows very strong privacy guarantees collapse both groups'overfitting to a numerical floor, rendering exposure-based audits uninformative in that regime. Together, these findings show that fairness audits of privacy-preserving systems must account for who bears the cost of protection, not only who benefits from its outcomes.
This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.
Background: Classifiers increasingly affect people’s lives, necessitating their audit for fairness and accuracy on diverse populations. However, direct auditing is often not possible, due to a lack of access to the classifier or to suitable individual-level validation data.
Objectives: This work aims to assess the fairness and accuracy of black-box classifiers using only population-level statistics, without requiring access to the classifier or individual predictions. Specifically, it introduces a method to lower-bound the discrepancy of a classifier: a quantity that jointly captures inaccuracy and unfairness.
Methods: We define a novel measure of unfairness based on the equalized odds fairness criterion, quantifying the fraction of the population on which a classifier deviates from ideal fair behavior. Using this measure, we develop a computationally efficient procedure for calculating the tightest possible lower bound on the classifier’s discrepancy, using only aggregated rates of positive predictions and true positives across protected sub-populations.
Results: Empirical evaluations confirm the tightness of the proposed lower bound in practical settings. The method is demonstrated on several use cases, including estimating the reliability of voting polls and assessing the fairness of patient identification from internet search data. The code and data are available at https://github.com/sivansabato/bfa2.
Conclusions: This work provides a practical and interpretable framework for auditing classifiers using population-level statistics. The proposed approach enables stakeholders to identify fairness and accuracy concerns in settings where traditional auditing is not feasible.
Sivan Sabato, E. Yom-Tov· Journal of Artificial Intell...· 0 citations
When sensitive attributes are continuous and high-dimensional $-$ demographic score vectors, posteriors over attributes, age or income profiles $-$ enforcing full statistical independence is often too restrictive, and existing relaxations rely on indirect dependence penalties or adversarial schemes that do not directly target the fairness-accuracy trade-off. We instead consider mean demographic parity through DPVar, the variance of the conditional-mean prediction given the sensitive attribute, and show that optimizing it yields a functional bilevel problem. We propose two algorithms for this problem: FBO, which uses a closed-form adjoint we derive for the squared-loss case to obtain an exact hypergradient, and ITD, which differentiates through unrolled inner steps and extends beyond squared loss. On synthetic data and a new semi-synthetic benchmark built from 60 tabular regression datasets, both methods achieve the lowest or near-lowest aggregate fairness-accuracy regret, and consistently match or outperform strong HSIC, adversarial, linear-dependence, and generalized-DP baselines.
Ieva Petrulionyte, Julien Mairal, Michael Arbel· 0 citations
Distributional reinforcement learning agents learn full return distributions that are increasingly read at face value: for interpretability, risk-sensitive control, and safety monitoring. We ask a question theory anticipates but that has not been measured directly: are the risk claims of a trained distributional agent true? Our audit combines a decision-relevant screening metric (the excess Wasserstein gap between the top two actions, which equals the mass by which first-order stochastic dominance is violated), ground truth from snapshot-restart Monte Carlo, and a statistical harness (permutation nulls, bootstrap refutation, FDR control) without which the audit itself manufactures false conclusions. Across QR-DQN, C51, and IQN on MinAtar (33 runs), 40-95% of the strongest claimed risk trade-offs are refuted at 95% confidence, the placement of the strongest claims is statistically indistinguishable from truth-blind, and essentially no claim is confirmable: for these agents, the learned"risk"reflects a training artifact rather than environment stochasticity. The artifact is structural (fully formed early in training, uncorrelated with final score, idiosyncratic to each seed) and appears unchanged at full-Atari scale, with every top Breakout claim of a pretrained near-state-of-the-art QR-DQN refuted. Positive controls of known magnitude confirm 96-100% of real claims (correlation 0.89-0.92): the reading measures the agents, not the audit. Acting on the heads'CVaR advice at their most-flagged states ranges from beneficial to significantly worse than chance. Neither training for risk nor ensembling removes the artifact, and recalibration passes the audit only by nullifying the claims: the head is uninformative, not merely miscalibrated. We release the toolkit and document two silent pitfalls that produced convincing but wrong audits of our own.
On Mehrotra's hard class the authors prove more than the failure of a single algorithm, showing that no monotone permutation-invariant compression scheme of any finite size attains the clean rate.