PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Optimization for Fairness with Noisy Protected Groups

Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, Michael I. Jordan

arXiv:2002.09343v3cs.LGstat.ML

TL;DR

Noisy, missing, or unreliable protected-group information complicates enforcing group-based fairness. The paper develops two robust optimization approaches and finds that they satisfy true-group constraints on average across noise levels, while the naïve approach’s violations increase as noise rises.

  • Problem

    Practitioners may have noisy, missing, or unreliable protected-group labels, raising the question of whether fairness measured on those labels holds for the true groups.

    Source: §1 · p. 2, Broader Impact · p. 11

  • Method

    The paper bounds true-group violations under naïve noisy-group constraints and proposes DRO and soft-group robust optimization methods that target true-group fairness while minimizing a training objective.

    Source: §1 · p. 2

  • Results

    The robust approaches satisfy true-group constraints on average across noise levels, while the naïve approach’s true-group violations increase as noise rises, despite its noisy-group constraints being satisfied.

    Source: §1 · p. 2, §7.3 · p. 9

  • Takeaways & Limitations

    The robust methods offer stronger true-group fairness guarantees than naïve enforcement, with higher error rates than the naïve approach.

    Source: §7.3 · p. 9, §8 · p. 9

    The ideal soft-group algorithm may be impractical because it requires a nonconvex minimization oracle, nested computation, and a distribution over models.

    Source: §6.4 · p. 7

Abstract

from arXiv · show

Many existing fairness criteria for machine learning involve equalizing some metric across protected groups such as race or gender. However, practitioners trying to audit or enforce such group-based criteria can easily face the problem of noisy or biased protected group information. First, we study the consequences of naively relying on noisy protected group labels: we provide an upper bound on the fairness violations on the true groups G when the fairness criteria are satisfied on noisy groups $\hat{G}$. Second, we introduce two new approaches using robust optimization that, unlike the naive approach of only relying on $\hat{G}$, are guaranteed to satisfy fairness criteria on the true protected groups G while minimizing a training objective. We provide theoretical guarantees that one such approach converges to an optimal feasible solution. Using two case studies, we show empirically that the robust approaches achieve better true group fairness guarantees than the naive approach.

1 Introduction

Group-based fairness is difficult to measure or enforce when protected-group labels are noisy, missing, or unreliable. The paper bounds the naïve approach’s true-group violations and proposes two robust methods that target true-group fairness while minimizing a training objective.

1 Introduction

  • Survey response bias, outdated data, classifier-estimated labels, and zip-code proxies are examples of sources of unreliable protected-group information.The paper notes that separately trained classifiers may estimate group labels for image corpora without such labels.Source: §1 · p. 2
  • The paper studies binary classifiers with fairness constraints when only noisy labels are available for the true protected groups.It asks what noisy-group constraints imply for true groups and how noise-model side information can improve enforcement.Source: §1 · p. 2
  • Two robust-optimization methods target fairness on true groups while minimizing a training objective, unlike simply enforcing constraints on noisy groups.The paper also bounds true-group violations under the naïve approach and reports that the robust methods satisfy true-group criteria on average.Source: §1 · p. 2
  • DRO uses bounds on the total-variation distances between true- and noisy-group conditional distributions, but may be overly conservative without tight bounds.The uncertainty sets are constructed to include the unknown true group distributions.Source: §1 · p. 2
  • Soft group assignments use a more detailed noise model and offer an ideal algorithm guaranteed to converge to an optimal feasible point, plus a more tractable alternative.The model can capture bias between group labels and does not require the noisy and true groups to be direct approximations of one another.Source: §1 · p. 2

2 Related work

Prior work addresses fairness constraints, noisy group information, and robust optimization through distinct approaches. This paper builds on those lines while focusing on training under parity-based constraints with noisy groups.

2 Related work

  • Post-hoc threshold adjustments can enforce group-based constraints, but their resulting classifiers may not be optimal in accuracy.Constrained optimization instead trains models to satisfy fairness constraints while minimizing a training objective.Source: §2 · p. 3
  • Naïvely enforcing constraints on noisy groups does not guarantee fairness for true groups, while Hashimoto et al. [33] use DRO for Rawlsian Max-Min fairness without group information.This paper assumes some knowledge of the noise model and applies DRO to equalize fairness metrics over groups.Source: §2 · p. 3
  • Lahoti et al. [42] use adversarial reweighting for Rawlsian Max-Min fairness, whereas this paper studies parity-based fairness constraints.The paper’s setting concerns training subject to constraints, rather than post-processing a fixed trained model, and does not rely on conditional independence assumptions.Source: §2 · p. 3
  • Kallus et al. [37] propose soft-group robust fairness criteria for auditing; this paper adds training algorithms that optimize a model under those criteria.The proposed DRO approach also provides a practical TV-distance bound under its noise-model assumptions.Source: §2 · p. 3

3 Optimization problem setup

The setup trains a binary classifier to minimize expected loss while satisfying group-conditional constraints on a target fairness metric. The paper introduces noisy group labels as the available training information for the later problem setting.

3 Optimization problem setup

  • The setup defines a binary classifier with parameters θ and treats noisy protected-group labels as available during training.It initially assumes the noisy and true group labels coincide for simplicity.Source: §3 · pp. 3–4
  • The objective is expected binary-classification loss, and each constraint function is the expected fairness metric conditional on a true group.The target metric can represent a criterion such as demographic parity.Source: §3 · p. 4

4 Bounds for the naïve approach

The naïve approach replaces true-group constraints with constraints on noisy groups, and its true-group violations can be bounded when the groups do not differ too much. The paper relates the needed distribution bound to an empirically estimable misclassification rate.

4 Bounds for the naïve approach

  • If noisy-group constraints are satisfied, true-group fairness violations can be bounded when noisy groups do not deviate too much from true groups.The section frames this as a bound on how far a classifier satisfying noisy-group constraints may be from true-group fairness.Source: §4 · p. 4

4.1 Bounding fairness constraints using TV distance

  • When each fairness function has differences bounded by 1 and TV(p_j, ˆp_j) ≤ γ_j, satisfying noisy-group constraints implies true-group constraints g_j(θ) ≤ γ_j.The bound is tight for this function family and covers rate-based fairness metrics such as demographic parity.Source: §4.1 · p. 4

4.2 Estimating the TV distance bound in practice

  • If the class prior is unchanged by noise, TV(p_j, ˆp_j) is at most P(G ≠ ˆG | G = j), making the bound estimable from misclassification information.The paper notes that such information may come from an auxiliary dataset or a prior estimate; the resulting bound can also support a robust approach.Source: §4.2 · pp. 4–5

5 Robust Approach 1: Distributionally robust optimization (DRO)

DRO uses bounds on the distance between true- and noisy-group distributions to constrain worst-case fairness violations. Feasible solutions are guaranteed to satisfy the true-group constraints, though specifying useful bounds can be difficult.

5 Robust Approach 1: Distributionally robust optimization (DRO)

  • Any feasible DRO solution satisfies the true-group fairness constraints when each group's distributional distance is bounded by γ_j.The bound is based on the assumed upper limit on total variation distance between true- and noisy-group conditional distributions.Source: §5 · p. 5

5.1 General DRO formulation

  • DRO minimizes a worst-case objective over distributions constrained by a divergence metric and bound.The paper uses total variation distance; choosing a meaningful divergence and bound can be difficult.Source: §5.1 · p. 5, §5.2 · p. 5

5.2 Solving the DRO problem

  • The authors solve the empirical DRO formulation efficiently with a gradient-based algorithm adapted from prior work.The constrained problem is rewritten as a total-variation DRO problem using a Lagrangian.Source: §5.2 · p. 5

6 Robust Approach 2: Soft group assignments

The soft-assignment approach uses auxiliary data and estimated group-membership probabilities to formulate robust fairness constraints. It combines those constraints with a training objective; an ideal algorithm has convergence guarantees, while a practical approximation is computationally more tractable.

6.1 Constraints with soft group assignments

  • The method assumes a main dataset with noisy groups, labels, and features, plus auxiliary data containing both noisy and true groups.The auxiliary data estimates P(G=j|Ĝ=k), used to construct possible soft group assignments.Source: §6.1 · p. 6
  • Soft assignments estimate each example’s probability of belonging to a true group, and the robust criteria enforce fairness under the worst admissible weights.The admissible weights are limited by the law of total probability and the estimated group-noise model.Source: §6.1 · p. 6

6.2 Robust optimization with soft group assignments

  • The authors combine robust soft-assignment fairness criteria with the training objective; every feasible solution satisfies fairness for the true groups.The section presents this as a constrained optimization problem.Source: §6.2 · p. 6

6.3 Ideal algorithm

  • The ideal algorithm returns a near-optimal, near-feasible solution when run for enough iterations, with objective and expected constraint violations within ε.Its best-response step uses an oracle, and the algorithm’s guarantee applies to the robust optimization problem.Source: §6.2 · p. 6, §6.3 · p. 7

6.4 Practical algorithm

  • The ideal algorithm may be impractical because it needs a nonconvex oracle, nested optimization, and a distribution over models; the practical variant approximates its best response.The practical method uses a linear program over weights followed by a gradient step, but does not share the ideal algorithm’s convergence guarantees.Source: §6.2 · p. 6, §6.4 · p. 7

7 Experiments

The experiments compare naive training with DRO and soft assignments on Adult and Credit data under synthetically increasing group-label noise. Across both studies, the robust methods satisfy true-group constraints on average, while the naive method’s violations grow with noise and the robust methods incur higher error.

7 Experiments

  • Group noise is synthetically generated by randomly changing a fraction γ of memberships, with γ ranging from 0.1 to 0.5.The experiments use two UCI datasets and measure performance across ten train/validation/test splits.Source: §7 · p. 7

7.1 Case study 1 (Adult): equality of opportunity

  • On Adult, the study predicts income over $50K across three race groups and enforces equality of opportunity through true-positive-rate constraints.The constraints require each group’s TPR to be at least the overall TPR, with slack α.Source: §7.1 · p. 8

7.2 Case study 2 (Credit): equalized odds

  • On Credit, the study predicts loan default across three education groups and enforces equalized odds using TPR and FPR constraints.Each group’s TPR is constrained relative to the overall TPR, and its FPR relative to the overall FPR.Source: §7.2 · p. 8

7.3 Results

  • With true-group information, Adult’s constrained model reaches −0.0469 ± 0.0068 maximum violation at 0.1459 ± 0.0012 error, while Credit reaches −0.0105 ± 0.0070 at 0.1796 ± 0.0011.These are test-set results averaged over ten splits; the authors report that true-group constraints were satisfiable at reasonably low error on Adult and approximately the unconstrained error on Credit.Source: §7.3 · pp. 8–9
  • Across both case studies, DRO and soft assignments satisfy true-group constraints on average at all tested noise levels, while naive violations increase as noise rises.The robust approaches have higher error than the naive approach; DRO generally has higher error than soft assignments.Source: Figure 1 · p. 8, §7.3 · p. 9, Figure 2 · p. 9

8 Conclusion

The paper develops robust methods for enforcing group-based fairness with noisy protected-group information, while emphasizing that technical guarantees do not settle which groups or fairness criteria should be used. Its conclusion also calls for domain-specific scrutiny and identifies open questions about the methods’ scope and conservatism.

8 Conclusion

  • Both robust approaches satisfy true-group fairness criteria on average, unlike the naïve noisy-group approach; the paper also provides a bound on true-group violations under noisy-group feasibility.The DRO approach has a TV-distance bound, while the soft-group-assignments approach provides an ideal algorithm guaranteed to converge to an optimal feasible point and a more tractable alternative.Source: §8 · p. 9

Broader Impact

  • The technical improvement alone does not ensure positive societal impact, and group-based criteria may be insufficient to mitigate background injustice in some domains.The authors call for domain-specific considerations before applying algorithmic solutions in sensitive settings.Source: Broader Impact · p. 11, Domain specific considerations · p. 11

Choice of fairness criteria

  • The work does not choose among group-based fairness criteria, whose different choices can produce different prediction outcomes and tradeoffs.The authors say criterion selection should involve domain experts and awareness of tradeoffs.Source: Choice of fairness criteria · p. 11

Choice of protected groups

  • The approach assumes practitioners have already defined the true protected groups, although selecting appropriate labels is itself nontrivial.Considerations include how labels were collected, who chose them, and the assumptions built into those categories.Source: Choice of protected groups · p. 11
  • Group-based criteria do not account for within-group inequality, so intersections of groups may still experience unfairness even when criteria are robustly enforced.The paper identifies intersectionality as a key consideration when defining protected groups.Source: Choice of protected groups · p. 11

A Proofs for Section 4

A.1 Proofs for TV distance

This appendix bounds fairness violations on true groups using distances between true- and noisy-group conditional distributions. It extends the guarantee to Wasserstein distances and describes DRO implementation details, fairness constraints, and a setting with different group-label dimensionalities.

A.1 Proofs for TV distance

  • Under 1-bounded constraint functions, TV radii γ_j guarantee true-group fairness violations within slack γ_j when the model satisfies fairness criteria on noisy groups.The proof bounds the difference between noisy- and true-group constraint expectations by their TV distance.Source: §A.1 · p. 16
  • For discrete distributions, the TV-distance bound can remain valid but become very loose.Source: §A.1 · p. 16
  • If P(G = i) = P(ˆG = i), then TV(p_i, ˆp_i) is bounded by P(G ≠ ˆG | G = i).Source: §A.1 · p. 16

A.2 Generalization to Wasserstein distances

  • For constraint functions Lipschitz in metric c, Wasserstein radii W_c(p_j, ˆp_j) ≤ γ_j likewise guarantee true-group fairness within slack γ_j.This extends the bound beyond the TV-distance setting.Source: §A.2 · p. 17

B.1 Empirical Lagrangian Formulation

  • The DRO formulation converts expectations to empirical distributions and uses projected gradient descent ascent, with efficient projections onto the ℓ1 ball.The empirical optimization is written as a minimax problem using a Lagrangian formulation.Source: §B.1 · p. 18

B.3 Equalizing TPRs and FPRs using DRO

  • The DRO constraints equalize TPRs and FPRs within slack α; setting α = 0 exactly equalizes the corresponding rates.The case studies use m constraints for TPRs and 2m constraints for TPRs and FPRs together.Source: §B.3 · p. 19

B.4 DRO when ˆG and G have different dimensionalities

  • DRO can be generalized to differing numbers of true and noisy groups, but empirically comparing it with soft group assignments in that setting remains future work.Source: §B.4 · p. 21

C.1 Derivation for E[h(θ, X, Y )|G = j]

The soft-group-assignments appendix expresses true-group conditional expectations through weights based on noisy group information. It applies these weights to TPR and FPR constraints, with zero slack corresponding to exact rate equalization.

C.1 Derivation for E[h(θ, X, Y )|G = j]

  • The appendix derives the true-group conditional expectation using weights based on the predicted label, outcome, and noisy group information.Source: §C.1 · p. 21

C.2 Equalizing TPRs and FPRs using soft group assignments

  • For soft group assignments, TPR and FPR constraints estimate group-specific rates with weights w(j|ˆY, Y, ˆG), while comparing them with full-population rates.The method uses m constraints for TPRs alone and 2m constraints when equalizing both TPRs and FPRs.Source: §C.2 · p. 22
  • Setting slack α to zero exactly equalizes true positive rates and false positive rates under the soft-group-assignments constraints.Source: §C.2 · p. 22

D.1 Optimality and feasibility guarantees

The appendix establishes optimality and feasibility guarantees for the ideal algorithm, then details best-response procedures and a more practical approximation. Its guarantees rely on stated assumptions, while the practical procedure uses deterministic iterates and heuristic updates.

D.1 Optimality and feasibility guarantees

  • With sufficiently accurate substeps and enough iterations, Algorithm 1 returns an ε-optimal, ε-feasible stochastic model.The guarantee concerns a stochastic classifier and requires the errors in Steps 2 and 4 to be sufficiently small.Source: §D.1 · p. 24

D.2 Best Response over θ

  • Algorithm 3 decouples θ-dependent probability constraints using multipliers, then minimizes over θ and µ while ascending over w on the simplex.The joint minimization over θ and µ is not necessarily convex and uses a minimization oracle.Source: §D.2 · pp. 26–27
  • Theorem 5 gives Algorithm 3 an optimality guarantee under strict slack and boundedness conditions; the inner multipliers are bounded under those assumptions.The strict-slack condition requires a feasible w with ru(θ, w) ≤ −γ for every relaxed constraint.Source: §D.2 · p. 27

E Discussion on the Practical algorithm

  • Algorithm 4 approximates the best response with deterministic classifiers, a maximization over w for the current θ, and a single gradient update on θ.The maximization over w can be solved with linear programming; the algorithm also updates λ by gradient ascent.Source: E Discussion on the Practical algorithm · p. 30

F Additional experiment details and results

  • Appendix F adds experimental setup details and further results beyond those reported in the main paper.The additional results, like the main-paper results, are test-set averages over 10 random train/validation/test splits.Source: F Additional experiment details and… · p. 30

F.1 Additional experimental setup details

The experiments use finite-sample training, tune hyperparameters on validation data, and evaluate methods over repeated data splits. In the Adult case study, the robust methods satisfy their robust constraints on average across noise levels, while the naïve method’s true-group violations rise with noise.

F.1 Additional experimental setup details

  • Training and constraints use empirical finite-sample expectations and hinge upper bounds; the noisy groups are model features, while true groups are not used in training or validation.True groups are used to estimate the noise model for soft group assignments.Source: §F.1 · p. 30

F.1.1 Adult dataset

  • The Adult study uses 48,842 examples, race as the true protected group, income above $50,000 as the label, and constraint slack α = 0.05.Race categories other than “white” or “black” are combined into “other”; noisy race labels replace true race as a model feature.Source: §F.1.1 · p. 31

F.1.3 Optimization code

  • Models are compared with unconstrained and true-group-constrained baselines; training took less than 10 minutes per model.The approaches include naïve, DRO, and soft group assignments.Source: §F.1.3 · p. 32

F.1.4 Hyperparameters

  • Hyperparameters were selected by validation performance over 10 splits, minimizing error while satisfying each method’s relevant constraints; hinge-relaxed training used additional slack β.All approaches ran for 750 iterations; β was chosen so the hinge-relaxed constraints were satisfied on the training set.Source: §F.1.4 · p. 32, Table 1 · p. 32

F.2.1 Case study 1 (Adult)

  • As group noise increases, the naïve Adult model’s true-group violations rise even though it satisfies constraints on the noisy groups.Figure 4 reports the mean and standard error over 10 random train/validation/test splits.Source: Figure 4 · p. 33, §F.2.1 · p. 33
  • Both DRO and soft group assignments satisfy their respective robust constraints on the Adult test set on average across noise levels.Figure 5 reports mean and standard error over 10 random splits; Table 2 reports error rates and maximum true-group violations, but the supplied passages give no cell values.Source: Figure 5 · p. 33, §F.2.1 · p. 33, Table 2 · p. 33

F.2.2 Case study 2 (Credit)

In the Credit study, DRO and soft assignments satisfy their robust constraints on average across noise levels. The results also compare true-group TPR and FPR violations, with higher TPR violations than FPR violations.

F.2.2 Case study 2 (Credit)

  • Across noise levels, Credit true-group TPR violations are higher than FPR violations, while the FPR constraint still prevents satisfying TPR constraints simply by adding false positives.Figure 6 shows TPR violations in the top panel and FPR violations in the bottom panel.Source: §F.2.2 · p. 34, Figure 6 · p. 34
  • Table 3 reports Credit test error rates and fairness violations on the true groups, averaged over 10 splits.The supplied passages do not provide the table’s cell values.Source: Table 3 · p. 34, §F.2.2 · p. 34
  • All three approaches satisfy fairness constraints on the noisy Credit groups on the test set.Figure 7 reports maximum violations over different group noise levels.Source: §F.2.2 · p. 34, Figure 7 · p. 35
  • DRO and soft assignments satisfy their respective robust constraints on the Credit test set on average across noise levels.Figure 8 reports mean and standard error over 10 random train/validation/test splits.Source: §F.2.2 · p. 34, Figure 8 · p. 35
Loading 2002.09343v3…