Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints

1 Introduction

• Data-dependent constraints can overfit, so training-set satisfaction does not ensure the same constraint level on an i.i.d. test set.The paper highlights the concern for fairness requirements such as the 80% rule.Source: §1 · p. 1
• Independent validation data lets the λ-player choose constraint penalties on validation examples while the θ-player minimizes the empirical Lagrangian on training examples.This adapts validation-based hyperparameter selection to constraint generalization.Source: §1 · p. 2
• Because θ and λ are chosen using different datasets, the players optimize different functions, making the game non-zero-sum.The approach therefore departs from the typical Lagrangian formulation.Source: §1 · p. 2
• The authors adapt Cotter et al. [2018]’s non-zero-sum game to derive constraint-generalization bounds agnostic to model complexity.They introduce two algorithms with theoretical bounds.Source: §1 · p. 2
• Two-dataset experiments improved constraint generalization on three of four datasets with both practical algorithms, while error rates were somewhat higher.Business Entity Resolution was the exception; the improvement appeared even when the proofs did not apply.Source: §1 · p. 2

2 Related Work

• Constraint generalization was comparatively new: Woodworth et al. [2017] had addressed equalized-odds constraints, while other cited work proved bounds for constrained problems.The passage names Goh et al. [2016], Agarwal et al. [2018], and Donini et al. [2018] among the latter work.Source: §2 · p. 2
• Woodworth et al. [2017] train a complex predictor and then tune a simple validation-set correction; this paper extends that two-dataset idea to data-dependent constraints generally.Their correction approach relies on equalized-odds structure and a small number of tunable parameters.Source: §2 · p. 3
• Agarwal et al. [2018] is the primary baseline, but their algorithm focuses on fair classification while this paper considers the more general inequality-constrained setting.Both approaches use an oracle to optimize θ and produce stochastic classifiers.Source: §2 · p. 3

3 Background & Definitions

• The proxy-Lagrangian is a non-zero-sum game using surrogate constraint losses for the θ-player; this paper instead uses the game to assign different datasets to the players.The original constraints remain the goal, including when surrogate losses are used for nondifferentiable or discontinuous constraints.Source: §3 · p. 3
• The empirical proxy-Lagrangian uses a training-set average for θ and a validation-set average for λ, which chooses penalties for the original constraints.The proxy losses are used only by θ; using them is optional.Source: §3 · p. 3

3.1 Generalization

• Training generalization error concerns the objective and proxy constraint losses, whereas validation generalization error concerns the original constraint losses.The two errors are defined over their respective datasets and apply to the specified sets of models and losses.Source: §3.1 · p. 4
• Guarantees are stated for stochastic models supported on the set of T iterates found by the proposed algorithms.If every iterate generalizes well, any distribution supported on those iterates does so in expectation as well.Source: §3.1 · p. 4

4 Algorithms

• Independent datasets let the θ-player choose model parameters and the λ-player impose constraints, with constraint-generalization bounds independent of model-class complexity.The approach builds on proxy-Lagrangian optimization and seeks solutions that are nearly optimal, nearly feasible, and generalize on constraints.Source: §4 · p. 4

4.1 Covering-based Algorithm

• Discretizing the allowed λ values yields a finite set of associated θ values chosen using training data, supporting validation generalization without requiring convexity.The covering-based method uses an approximate Bayesian optimization oracle; its guarantees also require a sufficiently small covering radius.Source: §4.1 · p. 5, §4 · p. 5
• The covering-based algorithm returns nearly optimal, nearly feasible solutions while bounding validation constraint generalization independently of the complexity of Θ.Its constraint-generalization bound is distinct from the feasibility bound; whether validation violations are close to zero also depends on the feasibility-margin condition.Source: §4.1 · pp. 5, 7
• The feasibility-margin condition can be removed by defining γ on the training sample, but then γ depends on that sample rather than only on the constrained problem and proxy losses.Source: §4.1 · p. 6

4.2 Gradient-based Algorithm

• The gradient-based algorithm replaces the oracle and discretization with gradient descent, requiring strong convexity of the objective and proxy-constraint losses and Lipschitz continuity of original constraint losses.Strong convexity is required for the objective and proxy losses, not the original constraint losses.Source: §4.2 · pp. 7–9
• The gradient-based method has theoretical performance roughly comparable to the covering-based method, but uses stronger assumptions while avoiding discretization and an oracle.Its optimality and feasibility guarantees are very similar, and its more complicated constraint-generalization bound is roughly comparable.Source: §4.2 · p. 9

5 Experiments

• Algorithm 3 simultaneously updates θ and λ using stochastic updates; Algorithm 4 adds proxy constraints and independent datasets to a variant of the standard Lagrangian formulation.Neither practical algorithm has the theoretical guarantees established for Algorithms 1 and 2.Source: §5 · p. 9
• Both approaches use the same total data, but the two-dataset method splits training data between S(train) and S(val), while the baseline uses their union for both.For the two-dataset method, training errors and constraint violations are reported on their respective training and validation sets; test results use the testing set.Source: §5 · p. 10

5.1 Simulated-data Experiments

• The two-dataset approach comes closer to satisfying simulated-test constraints, at a slight cost in testing accuracy, with the greatest advantage for 100-hidden-unit networks.Figure 1 shows the linear-model comparison; the trend holds across the tested model types and is strongest for the most complex model.Source: §5.1 · p. 11, Figure 1 · p. 11

5.2 Real-data Experiments

• The real-data experiments use linear, calibrated-lattice, or one-hidden-layer neural-network models; the neural networks were chosen because they overfit.The neural networks have 50 ReLU neurons.Source: §5.2 · p. 11
• Communities and Crime uses eight racial-percentage groups, each constrained to have a false positive rate no greater than the overall rate.The task predicts whether a community's crime rate is above or below the 70th percentile.Source: §5.2 · pp. 11–12
• On three of four real datasets, both two-dataset algorithms significantly improve constraint generalization, except on Business Entity Resolution, while error rates are somewhat higher.Table 4 reports error rates and maximum constraint violations, averaged over 100 runs.Source: Table 4 · p. 12, §5.2 · p. 12
• Business Entity Resolution constrains recall to at least 95% for each of 16 common countries and for chain and non-chain businesses, and limits their accuracy gap.The accuracy on non-chain businesses must be no more than 10% higher than on chain businesses.Source: §5.2 · p. 12
• Adult uses the 80% demographic-parity rule for four overlapping groups, while COMPAS constrains positive-label prediction rates for four groups to at most 5% above the overall rate.Adult predicts income above $50,000; COMPAS predicts recidivism under equal-opportunity constraints.Source: §5.2 · p. 12

10 Hidden Units 0/1 error Constraint violation

• The fragment shows the value 0.06 alongside labels for two-dataset training and testing and one-dataset training and testing.It does not identify a metric-value pairing.Source: §5 · p. 13
• The fragment names both 2-dataset and 1-dataset results.No comparison between their values is supplied.Source: §5 · p. 13
• Training and testing appear as separate labels for both dataset approaches.The fragment does not provide further interpretation of these labels.Source: §5 · p. 13

10 Hidden Units 0/1 error Constraint violation

• The supplied table fragment labels 100 hidden units and reports 0/1 error and constraint violation.It supplies no result values or comparisons.Source: §10 · p. 13
• Figure 2 reports the same general trend as Figure 1, with two-dataset benefits more pronounced as model complexity increases.It covers one-hidden-layer networks with 5, 10, and 100 hidden units.Source: Figure 2 · p. 13
• Figure 2 covers one-hidden-layer neural networks with 5, 10, and 100 hidden units.The passage states that the results follow Figure 1's general trend.Source: Figure 2 · p. 13

Symbol Description

• The symbol description defines the notation for losses, constraints, datasets, model parameters, Lagrange-multiplier-like hyperparameters, and algorithm quantities.It also lists generalization bounds, oracle and covering terms, step sizes, and other theorem parameters.Source: Symbol Description · p. 16

A Examples of Constraints

• The appendix presents examples of constrained optimization problems in the form of Equation 1.The examples include Neyman–Pearson classification and an equal-opportunity fairness constraint.Source: A Examples of Constraints · p. 17, §A.1 · p. 17, §A.2 · p. 17

A.1 Neyman-Pearson

• The Neyman–Pearson example minimizes false positive rate subject to false negative rate at most 10%.It expresses the problem using paired positive- and negative-label feature distributions; hinge upper bounds and a proxy constraint are suggested for practice.Source: §A.1 · p. 17

A.2 Equal Opportunity

• The equal-opportunity example minimizes overall error while bounding each protected class's false negative rate by 110% of the overall rate.It defines constraint losses using the protected-class indicator and assumes probabilities in the ratio denominators are known constants; differentiable upper bounds and proxy constraints may be used in practice.Source: §A.2 · p. 17

• The LP selects a distribution over iterates that minimizes the objective while keeping every constraint violation within ϵ.Source: B Shrinking · p. 18
• Every vertex of the LP has at most m + 1 nonzero weights, so the selected classifier uses at most m + 1 iterates.Source: B Shrinking · p. 18
• Setting ϵ to the original classifier’s maximum validation violation yields a vertex with no greater training objective or maximum validation violation.The resulting stochastic classifier is supported on at most m + 1 iterates, and the paper’s generalization definitions still apply.Source: B Shrinking · p. 18
• In experiments, the authors instead use outer bisection to find the smallest nonnegative ϵ for which the LP is feasible.Source: B Shrinking · p. 18

• The paper adapts Cotter et al.’s equilibrium result to the separate-dataset proxy-Lagrangian setting, accounting for generalization.The analysis uses proxy losses that upper-bound the corresponding constraint losses.Source: C Proofs · pp. 18–19
• Under the stated sequence conditions, the resulting randomized model is nearly optimal; a strict feasibility bound additionally assumes a comparator satisfying every constraint with margin γ.Source: C Proofs · p. 19
• The proof of feasibility translates validation-sample constraints into claims over the data distribution, while the objective-loss range bound supports the multiplier bound.Source: C Proofs · pp. 19–20
• The proof bounds validation generalization by covering the multiplier simplex, whose radius-r external cover has size at most (5/r)^m when r ≤ 1.Source: C Proofs · p. 21
• A finite, sample-independent model class with bounded loss admits a uniform concentration result over its members with probability at least 1 − δ.Source: C Proofs · p. 21

C.1 Algorithm 1

• For validation generalization, the proof applies Lemma 2 to training-dependent ΘCr, then uses a radius-r 1-norm cover Cr and a union bound, since ˆΘ ⊆ ΘCr and |ΘCr| = |Cr|.The cover satisfies |Cr| ≤ (5/r)m; Lemma 2 gives each i ∈ [m] probability δ/m uniformly over θ ∈ ΘCr.Source: §C.1 · pp. 22–23
• Theorem 1 states that θ̄ is nearly-optimal in expectation and gives a generalization result holding with probability 1 − δ over sampling of S(val).Source: §C.1 · p. 23

C.2 Algorithm 2

• Algorithm 2’s proof uses a multiplier covering and concentration to establish its validation-generalization bound for the candidate models.Source: §C.2 · pp. 25–26
• Algorithm 2’s guarantees require a compact convex parameter space and losses that are strongly convex in the parameters.Its validation-generalization result additionally assumes constraint losses are Lipschitz continuous.Source: §C.2 · pp. 25–26

• The baseline applies the empirical Lagrangian to one training dataset, extending the fair-classification approach of Agarwal et al. [2018] to inequality-constrained optimization.Source: D One-dataset Lagrangian Baseline… · p. 26
• Its equilibrium result is nearly optimal relative to the population constrained objective, with an additive term involving training generalization error.Source: D One-dataset Lagrangian Baseline… · p. 27
• Feasibility analysis uses a comparator satisfying constraints with margin γ and requires γ to exceed the training generalization error.Source: D One-dataset Lagrangian Baseline… · p. 27
• The appendix first derives optimality and feasibility for the finite training sample, then uses the training generalization bound to relate those results to the distribution.Source: D One-dataset Lagrangian Baseline… · p. 27