The Price of Fairness in Active Learning: Fundamental Limits and Optimal Label Acquisition

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.