Source-linked AI summary
Differentially Private Fair Learning
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, Jonathan Ullman
TL;DR
The paper studies how to learn fair classifiers while protecting sensitive attributes with differential privacy. It develops private post-processing and in-processing approaches, revealing tradeoffs among fairness, accuracy, and privacy that can improve when protected attributes are available at test time.
Problem
Algorithmic models can discriminate against demographic groups, motivating fair learning methods that also prevent sensitive attributes from being inferred from learned models.
Method
The paper designs differentially private fair-learning algorithms, including a private post-processing method that perturbs group-conditioned statistics before solving a linear program.
Results
The paper identifies fairness, accuracy, and privacy tradeoffs, with better tradeoffs when protected attributes can be used at test time and higher private estimation error otherwise.
Takeaways & Limitations
Protected attributes can support fairness enforcement while differential privacy limits how accurately those attributes can be inferred from models or decisions.
Takeaways & Limitations
The simple post-processing approach does not generally achieve error comparable to the best fair classifiers and requires protected attributes at test time.
Abstract
from arXiv · showhide
Motivated by settings in which predictive models may be required to be non-discriminatory with respect to certain attributes (such as race), but even collecting the sensitive attribute may be forbidden or restricted, we initiate the study of fair learning under the constraint of differential privacy. We design two learning algorithms that simultaneously promise differential privacy and equalized odds, a 'fairness' condition that corresponds to equalizing false positive and negative rates across protected groups. Our first algorithm is a private implementation of the equalized odds post-processing approach of [Hardt et al., 2016]. This algorithm is appealingly simple, but must be able to use protected group membership explicitly at test time, which can be viewed as a form of 'disparate treatment'. Our second algorithm is a differentially private version of the oracle-efficient in-processing approach of [Agarwal et al., 2018] that can be used to find the optimal fair classifier, given access to a subroutine that can solve the original (not necessarily fair) learning problem. This algorithm is more complex but need not have access to protected group membership at test time. We identify new tradeoffs between fairness, accuracy, and privacy that emerge only when requiring all three properties, and show that these tradeoffs can be milder if group membership may be used at test time. We conclude with a brief experimental evaluation.
1 Introduction
The paper studies learning algorithms that jointly protect sensitive attributes through differential privacy, enforce approximate fairness, and retain predictive accuracy. It develops simple post-processing and more complex in-processing approaches, revealing tradeoffs among privacy, fairness, and accuracy.
- 1 Introduction: Regulatory restrictions on collecting or using protected attributes make it difficult to guarantee non-discrimination when group membership is unavailable.The paper frames this as a tension between fairness requirements and restrictions on sensitive data.
- 1 Introduction: The paper replaces MPC-only protection with differential privacy, which limits leakage of individual race beyond population-level correlations.The guarantee concerns inferences from the learned model rather than only access during computation.
- 1.1 Our Results: The algorithms simultaneously provide differential privacy for protected attributes, approximate Equalized Odds, and error comparable to non-private fair benchmarks.Equalized Odds approximately equalizes false positive and false negative rates across protected groups.
- 1.1 Our Results: The first algorithm privately perturbs group-conditioned statistics before solving a linear program, but requires protected attributes at test time and is not generally optimal among fair classifiers.Its main advantage is simplicity, while its limitations concern optimality and test-time access.
- 1.1 Our Results: The paper identifies an inherent privacy–accuracy–fairness tradeoff: increasing iterations can increase gradient perturbations and may fail to reduce error.This differs from the non-private setting, where iterations mediate fairness and running time.
- 1.1 Our Results: Allowing protected attributes at test time yields a better tradeoff, essentially removing the role of parameter B, although the improvement requires relaxing fairness to Equalized False Positive Rates.The paper also reports that test-time protected attributes are necessary for obtaining this better tradeoff.
2 Model and Preliminaries
The paper models learning from data containing unprotected attributes, protected attributes, and binary labels, while requiring privacy for protected attributes and approximate Equalized Odds fairness. It formalizes privacy mechanisms and fairness constraints empirically, highlighting tradeoffs among privacy, fairness, and classification error.
- The data contain m i.i.d. individuals described by unprotected attributes X, protected attribute A, and binary label Y.
- The learning objective is to output a possibly randomized classifier that protects A under differential privacy and satisfies approximate Equalized Odds fairness.
- Equalized Odds fairness constrains false-positive and true-positive rate differences across protected groups to be at most γ.
- Using group 0 as an arbitrary anchor reduces the fairness formulation from quadratically many pairwise inequalities to linearly many constraints.
- Differential privacy is defined by limiting how much an algorithm’s output distribution changes when one database entry changes, with parameters ε and δ.
- The paper uses Laplace and Exponential mechanisms, respectively perturbing sensitive queries and privately selecting classifiers or other objects.
3 Differentially Private Fair Learning: Post-processing
DP-postprocessing privately adapts a base classifier to equalize group-specific error rates, but requires protected attributes at test time and inherits the non-private method’s lack of optimality guarantees.
- Method: DP-postprocessing privately perturbs group-conditional prediction statistics before solving a linear program for the fair classifier.The base classifier is trained without protected attributes; noisy statistics are used in the optimization.
- Method: The method equalizes false-positive and true-positive rates across protected groups through post-processing.The classifier mixes the base predictions with protected-attribute-dependent decisions parameterized by probabilities.
- Limitation: The resulting classifier must explicitly use the protected attribute at test time, which may be infeasible or illegal.This requirement is the principal deployment limitation of the approach.
- Guarantees: The privacy analysis bounds fairness violations using noisy group-conditional statistics and the privacy parameter.The supplied theorem fragments express false-positive and true-positive violations as γ plus terms involving logarithmic factors, sample size, and ϵ.
- Guarantees: Its accuracy guarantee is relative to the non-private post-processing algorithm, not the optimal fair classifier.The non-private post-processing method is simple but has no general optimality guarantee.
4 Differentially Private Fair Learning: In-processing
DP-oracle-learner privately solves fair classification as a repeated Learner–Auditor game, avoiding protected attributes in the classifier while exposing a privacy–accuracy–fairness tradeoff.
- Method: DP-oracle-learner reduces fair learning to a zero-sum game between a classifier Learner and an Auditor detecting fairness violations.The Learner uses an unconstrained learning or cost-sensitive classification subroutine, while the Auditor updates fairness constraints.
- Method: Private gradients for the Auditor and private best responses for the Learner yield an approximate equilibrium.The construction uses the Laplace mechanism for Auditor gradients and the exponential mechanism or another private learning oracle for Learner responses.
- Privacy setting: The A-blind formulation excludes protected attributes from classifier inputs to prevent privacy loss through the hypothesis range.The analysis assumes finite VC dimension and uses the induced labelings on unprotected features.
- Tradeoffs: Stronger privacy guarantees lead to weaker accuracy and fairness guarantees in the algorithm’s bounds.The main theorem characterizes this joint privacy–accuracy–fairness tradeoff for the output classifier.
- Tradeoffs: Increasing B loosens the error bound while tightening the fairness-violation bound.The parameter B controls the dual-variable domain and therefore mediates an accuracy–fairness tradeoff.
- A-aware extension: Allowing protected attributes at test time can remove the extra B-mediated tradeoff, but changes the classification setting.The A-aware extension replaces the VC-dimension dependence with a hypothesis-class-size dependence in the iteration and bound expressions.
5 Experimental Evaluation
Experiments on Communities and Crime compare privacy–accuracy–fairness Pareto frontiers for the two algorithms and show that dataset size and test-time attribute access materially affect their tradeoffs.
- Experimental design: The evaluation measures Pareto frontiers of error and realized fairness violation across differential-privacy levels.The study varies the fairness bound γ and records the resulting error and fairness violation for each algorithm.
- Results: On the relatively small dataset, DP-postprocessing achieves good accuracy–fairness tradeoffs at meaningful ϵ values, whereas DP-oracle-learner does not.The in-processing algorithm still recovers the Pareto-curve shape at unreasonable privacy levels.
- Results: Upsampling the dataset by a factor of 10 preserves the tradeoff curve while making the privacy parameter meaningful for the in-processing algorithm.The original dataset has m ≪ 2K, while the upsampled version has m ≈ 20K.
- Deployment: Post-processing requires protected attributes at test time, whereas in-processing does not.This difference is central to interpreting the algorithms’ deployment tradeoffs.
- Deployment: The results suggest avoiding disparate treatment can be extremely burdensome with small datasets but feasible through in-processing at larger dataset sizes.The conclusion links the deployment constraint to dataset scale under simultaneous privacy and fairness requirements.
A Appendix for Models and Preliminaries: Differential Privacy
The appendix reviews differential privacy properties used by the algorithms, especially preservation under post-processing and controlled degradation under composition.
- Post-processing: Post-processing any randomized function of a differentially private output preserves the same privacy parameters.This property supports privately computing statistics and then feeding them into subsequent optimization.
- Composition: Adaptive composition combines multiple differentially private mechanisms with a cumulative privacy guarantee.The composed mechanism’s parameters depend on the per-step privacy costs and the number of mechanisms.
- Composition: Basic composition can require each of T iterations to use ϵ/T privacy, causing substantial per-iteration noise when T is large.Advanced composition permits a less restrictive per-step scaling under appropriate conditions.
- Post-processing pipeline: Figure 2 depicts training the base classifier and finding the optimal post-processing probabilities by solving a linear program.The resulting probabilities are later combined with the base prediction and sensitive attribute to make predictions.
B.1 Fair Learning Approach of [Hardt et al., 2016]
The approach post-processes an arbitrary base classifier to obtain an optimal randomized classifier satisfying γ-fairness with respect to the sensitive attribute. In practice, it estimates the required quantities from the empirical distribution and solves a linear program.
- An arbitrary base classifier pY is post-processed so its predictions become γ-fair with respect to sensitive attribute A.The derived classifier uses randomized probabilities conditioned on the base prediction and group membership.
- The minimum-error fair randomized classifier is found by solving optimization problem LP (5).Its probability vector specifies P[Yp = 1 | pY = ŷ, A = a], subject to probability constraints.
- Further predictions use the optimal probability vector together with the base estimate and sensitive attribute A.
- Because the true distribution P is unknown, the method estimates LP quantities using the empirical distribution.
B.2 Proof of Theorem 3.1
The proof establishes high-probability bounds showing that private estimates preserve feasibility and control fairness deviations of the empirical optimization solution. The resulting deviations scale with logarithmic confidence and privacy terms, sample size, and group-label frequencies.
- The proof relies on sensitivity and concentration bounds for empirical quantities involving false-positive and true-positive rates.
- The optimal solution p* of private LP (6) is feasible for the corresponding constrained program.
- With probability at least 1 − β, the estimated distribution is close to its reference counterpart in ℓ∞ distance.The bound is ln(4|A|/β) · (2/(mϵ)).
- The true-positive-rate deviation is likewise bounded by γ plus privacy-dependent estimation terms.The displayed bound uses ln(4|A|/β), mϵ, and the minimum relevant frequency.
- 8 ln(4|A|/β) / (mϵ) bounds the additional false-positive-rate deviation around γ, scaled by the smallest relevant reference frequency.The proof combines an empirical fairness bound with estimation-error terms.
C.1 Fair Learning Approach of [Agarwal et al., 2018]
This approach formulates fair empirical risk minimization as a bounded two-player zero-sum game between a classifier learner and a fairness auditor. An exponentiated-gradient reduction uses a cost-sensitive classification oracle, and approximate equilibrium yields near-optimal error with limited fairness violation.
- Fair ERM is rewritten as a two-player zero-sum game whose equilibrium solves the fair classification problem.The Learner selects a randomized classifier while the Auditor represents fairness violations through the Lagrangian.
- The dual variable is restricted to an ℓ1-bounded feasible set Λ to guarantee convergence.The bound is ||λ||1 ≤ B.
- The iterative reduction uses exponentiated-gradient updates for the Auditor and best responses from the Learner over T rounds.The Learner's best response can be solved efficiently using a cost-sensitive classification oracle for H.
- ν-approximate equilibrium means neither player can improve its Lagrangian objective by more than ν through unilateral strategy changes.
- Such an approximate equilibrium achieves error close to the best attainable error while keeping fairness-constraint violations reasonably small.
C.2 Missing Lemmas and Proofs of Section 4
The lemmas and proofs bound the sensitivity and accuracy of the private Learner and Auditor, then translate approximate equilibrium into error and fairness guarantees. A separate construction shows that the fair optimum can have sensitivity on the order of 1/(γm) in a restricted hypothesis class.
- The private Auditor's sensitivity is controlled by the number of groups, the dual bound B, sample size, and the smallest empirical group-label frequency.The corresponding ℓ1 bound is stated for each iteration t.
- The private Learner's loss sensitivity is bounded by (2|A|B + 1) divided by the smallest relevant frequency times m − 1.
- The private players' regret bounds yield a ν-approximate equilibrium with high probability, where ν is the sum of their regret terms.The analysis hides additional logarithmic dependence on m, ϵ, and |A| under rO notation.
- Under feasible fairness constraints, the resulting classifier inherits empirical error and fairness-violation guarantees from approximate equilibrium.The fairness proof bounds violations using the error guarantee and the dual norm bound.
- γ + 2ν divided by B − (|A| − 1) bounds the maximum false-positive-rate deviation from the reference group.
- Ω(1/(γm)) is a lower bound on the sensitivity of the fair optimum in one restricted hypothesis-class construction.The construction changes one individual's record between neighboring data sets.