Source-linked AI summary
Minimax Pareto Fairness: A Multi Objective Perspective
Natalia Martinez, Martin Bertran, Guillermo Sapiro
TL;DR
The paper addresses how to improve fairness across sensitive groups without unnecessary harm in high-impact classification settings. It formulates group fairness as multi-objective optimization, selects a minimax Pareto-efficient classifier, and provides an algorithm compatible with deep neural networks. The method improves worst-case group performance across several applications while allowing policy-driven post-processing toward zero risk disparity.
Problem
High-impact machine-learning decisions require accurate and unbiased predictions, but naively trained models may not satisfy fairness criteria across sensitive groups.
Method
The paper treats each group-specific risk as an objective, selects the Pareto-efficient model with the smallest worst-group risk, and recovers it using an adaptive-loss gradient-descent algorithm.
Results
The proposed approach improves minimax group risk across several metrics and achieves the best worst-case performance in Acc and CE on the Adult dataset.
Takeaways & Limitations
The framework provides a single classifier that avoids test-time sensitive-attribute access and can serve as an intermediate model for policy-driven perfect fairness.
Takeaways & Limitations
For non-convex hypothesis classes or risk functions, the algorithm may recover only a subset of the Pareto front, so minimax optimality may not be achievable through linear risk weighting.
Abstract
from arXiv · showhide
In this work we formulate and formally characterize group fairness as a multi-objective optimization problem, where each sensitive group risk is a separate objective. We propose a fairness criterion where a classifier achieves minimax risk and is Pareto-efficient w.r.t. all groups, avoiding unnecessary harm, and can lead to the best zero-gap model if policy dictates so. We provide a simple optimization algorithm compatible with deep neural networks to satisfy these constraints. Since our method does not require test-time access to sensitive attributes, it can be applied to reduce worst-case classification errors between outcomes in unbalanced classification problems. We test the proposed methodology on real case-studies of predicting income, ICU patient mortality, skin lesions classification, and assessing credit risk, demonstrating how our framework compares favorably to other approaches.
1. Introduction
The paper frames group fairness as balancing predictive risks across sensitive groups while avoiding unnecessary harm. It proposes selecting Pareto-efficient models with the smallest worst-group risk, while retaining the option of policy-driven perfect fairness.
- High-impact applications require predictions that are both accurate and unbiased with respect to sensitive attributes.
- Existing group-fairness criteria seek predictions independent of sensitive populations or independent conditional on ground truth.
- The proposed method can support policy-driven zero-gap classification through harmful post-hoc corrections and does not require sensitive attributes at test time.
- The paper formulates fairness as multi-objective optimization, treating each sensitive group’s conditional risk as a separate objective.
- Pareto efficiency identifies classifiers where increasing one group’s predictive risk is justified by decreasing another group’s risk, avoiding unnecessary harm.
- Minimax Pareto fairness selects the Pareto-efficient classifier with the smallest maximum group risk, without requiring zero disparity when disadvantaged groups do not directly benefit.
2. Related Work
The paper positions its approach against group-fairness methods that target independence, decoupled classifiers, or disparity reduction, emphasizing worst-group performance with a single classifier.
- Prior work studies prediction independence from sensitive groups, conditional independence given ground truth, and individual fairness.
- Unlike literature centered on discrimination-gap constraints or error-unfairness tradeoffs, this work characterizes attainable tradeoffs between sensitive groups.
- Decoupled classifiers can reduce group-risk disparity but may be unsuitable with insufficiently large datasets and require test-time group membership when deployed by group.
- The paper instead uses a single classifier that avoids test-time sensitive-group access and may permit transfer learning across diverse groups.
- Prior analysis indicates differing noise levels across sub-populations can make perfect fairness impossible without explicitly degrading one group’s performance.
3. Minimax Pareto Fairness: Formulation and Basic Properties
The formulation treats each group-specific risk as an objective and uses Pareto optimality to exclude unnecessary harm. Minimax Pareto fairness then chooses the efficient classifier with the lowest worst-group risk, with perfect equality available when supported by the hypothesis class.
- The framework is developed for training settings with trustworthy labels and sensitive attributes that need not be available at deployment.
- The classifier is the decision variable, while conditional risks for sensitive groups form the multi-objective risk vector.
- A risk vector dominates another when it is no worse in every component and strictly better in at least one.
- Pareto-efficient classifiers are those for which no classifier in the hypothesis class improves every group-specific risk while strictly improving one.
- Minimax Pareto fairness selects the Pareto-front classifier minimizing the maximum group-specific risk.
- If a Pareto-optimal classifier has equal risk across all groups, it is also minimax Pareto fair.
- An equal-risk classifier can have worse performance for every group than the minimax Pareto classifier, while post-processing can equalize risks by increasing over-performing groups’ risk.
- When Pareto classifiers do not achieve equal risk, reducing the remaining gap outside the Pareto front degrades the privileged group without tangible benefit to the underprivileged group.
4. Analysis of Pareto Optimal Solutions
The paper characterizes Pareto-efficient classifiers for convex hypothesis classes and risk functions, including DNN outputs and standard classifier losses. For Brier score and cross-entropy, optimal group-risk decompositions provide a full characterization that includes the minimax Pareto fair classifier.
- Convex Pareto characterization: DNN hypothesis classes are convex in function-output space, while Brier score and cross-entropy are convex with respect to classifier output.This convexity concerns interpolated classifier outputs, not necessarily the parameter space.
- Convex Pareto characterization: Under convexity, the Pareto front is convex and every Pareto solution can be recovered by solving a linear weighting problem.Each Pareto-efficient risk vector corresponds to some choice of nonnegative group weights.
- Risk characterization: For Brier score and cross-entropy, each optimal group risk decomposes into an irreducible minimum-risk term plus a nonnegative discrepancy from the group-optimal predictor.The irreducible term is independent of the weighted classifier, and the discrepancy depends on its deviation from p(y|X, a).
- Special cases: When Y ⊥A|X, every subgroup can attain its minimum risk and the Pareto front collapses to the Utopia point.The Pareto front also tends toward the Utopia point when the sensitive attribute is highly predictable from features.
- Special cases: Even under ideal separability conditions, unequal baseline group risks can make perfect risk equality require sub-optimal classifiers or improved features.Selecting a classifier solely to equalize risks can therefore introduce unnecessary harm.
5. Minimax Pareto Fair Optimization
The paper seeks a Pareto-efficient classifier that minimizes worst-group risk and develops APStar to recover its weighting vector from risk evaluations. APStar iteratively updates weights toward minimax performance, while its guarantees are narrower for non-convex models and risks.
- Objective: The target classifier is Pareto-efficient while minimizing the maximum sensitive-group risk.The corresponding minimax risk vector or classifier need not be unique.
- Motivation: Directly computing the optimal weighting vector is difficult because risk gradients require conditional-distribution estimates and the maximum-risk objective may have local minima.These difficulties motivate an optimization method based on risk function evaluations instead of gradients.
- Optimization method: The proposed method recovers the optimal weighting vector using only evaluations of the group-risk vector, with plug-in density estimation or joint classifier estimation as implementation options.Joint estimation uses all samples for one classifier, whereas separate density estimation can fragment data and limit transfer learning.
- Synthetic experiment: In a three-group synthetic experiment, all group risks converge to the minimax value and the weights converge to the optimal weighting vector.The experiment reports convergence across five randomized runs and compares maximum risk with the theoretical optimum.
- Optimization method: APStar iteratively refines the linear weighting vector by approximately projecting onto star-shaped regions associated with groups whose risks can be reduced.Updates interpolate the current weights with a vector associated with unsatisfied group-risk regions.
- Scope: For non-convex risk functions or hypothesis classes, APStar solutions remain Pareto-front members but may not characterize all Pareto-optimal solutions.The method is applied with DNNs and SGD, but the full characterization guarantee depends on the convex setting.
6. Experiments and Results
Experiments evaluate APStar and MMPF across synthetic optimization tasks and fairness datasets, emphasizing worst-group risk, disparity, calibration, and deployment without test-time sensitive attributes.
- Synthetic optimization: APStar requires fewer iterations than random sampling, especially when the triple-intersection area ratio is low.The synthetic experiment compares APStar, random sampling, and MWU on star-shaped sets.
- Real-world case studies: The evaluation covers mortality prediction, skin lesion classification, income prediction, and credit risk across accuracy, Brier Score, and Cross-Entropy.For datasets with more than two sensitive groups, the study reports sample mean, group mean, worst group, and disparity.
- Implementation: Sensitive attributes are omitted from observation features, broadening potential deployment settings.The classifiers use neural networks and/or linear logistic regression.
- Mortality prediction: MMPF improves worst-case Brier Score performance over Balanced in MIMIC, with gains also reflected in accuracy; plug-in estimation does not improve on joint estimation.The MIMIC study uses eight groups defined by age, ethnicity, and outcome.
- Income and credit risk: MMPF attains the best worst-case accuracy and Cross-Entropy on Adult, while methods perform similarly overall.Kamishima has a slight advantage in gender-case Cross-Entropy standard-deviation performance.
- Income and credit risk: MMPF produces the best worst-case Cross-Entropy and smallest accuracy and Cross-Entropy disparities on German Credit.Feldman’s accuracy comparison involves test-time sensitive-attribute access.
7. Discussion
The discussion frames MMPF as a minimax Pareto-fair approach that improves worst-case group performance without unnecessary harm and remains broadly implementable, while identifying open limitations.
- Discussion: MMPF formulates each group-specific risk as an objective and seeks efficient classifiers that reduce worst-case group risks without unnecessary harm.The formulation assumes trustworthy training target labels unaffected by discrimination.
- Discussion: The proposed algorithm does not require test-time access to sensitive attributes and is compatible with varied hypothesis classes, risk functions, and optimization methods.The framework can be integrated with classification pipelines including neural networks.
- Discussion: For nonconvex hypothesis classes or risk functions, the algorithm can recover Pareto-efficient models, although linear risk weighting may not achieve minimax optimality.Marginal risk tradeoffs can be controlled by constraining ratios between linear weights.
- Limitations and future work: Future work includes identifying high-risk sub-populations during learning rather than relying on predefined disadvantaged groups.The authors also state that APStar is empirically convergent but lacks a formal proof or counterexample.
A.1. Proofs
The proofs establish structural properties of Pareto-efficient classifiers, weighted-risk solutions, and minimax optimization under convexity and related assumptions.
- Proof strategy: The proof outlines derive contradictions from convexity, feasibility, continuity, and properties of weighted-risk solutions.Several auxiliary lemmas establish the conditions used for the main theorem.
- Minimax fairness: An equal-risk classifier cannot have a smaller worst-case risk than the Pareto-fair classifier under the stated definitions.The proof uses Pareto dominance to derive a contradiction.
- Pareto structure: Theorem 4.1 states that, for convex hypothesis classes and convex group risks, the Pareto front is convex.The theorem also connects Pareto solutions with linear weighting problems.
- Risk minimization: For Cross-Entropy and Brier loss, the conditional-risk minimizer is the conditional probability P(Y|X).Substituting this estimator yields the corresponding risk expressions.
- Risk minimization: When Y is conditionally independent of A given X, the resulting group-risk expressions do not depend on the linear weights.The cited lemma states this condition explicitly.
- Weight perturbations: Increasing selected linear weights either reduces at least one corresponding risk or leaves all selected risks unchanged.This property supports the monotonicity arguments used in the proofs.
A.2. Analysis of Proposed Optimization Method
The APStar analysis shows that its updates remain feasible, shrink under repeated non-improving steps, and can reach feasible-region points with sufficient updates.
- Update sequence: Consecutive updates that do not decrease minimax risk have step sizes converging to zero.The analysis expresses this through the norm of successive weight-vector differences.
- Update sequence: The update sequence is defined by averaging the current weighting vector with an update direction and increasing the update counter.The displayed update rule gives the operational form of this transition.
- Update sequence: APStar updates remain feasible and use progressively smaller step sizes while retaining access to any feasible-region point given sufficient updates.This summarizes the stated properties of the update sequence.
All update directions that are non-viable descent updates
The APStar update analysis identifies non-viable descent directions and motivates convergence through a gradient-descent interpretation, while noting that pathological cases can still cycle.
- A full convergence proof requires showing that APStar has no cycles.
- The update directions can be interpreted as gradient descent on a function F.This interpretation motivates, but does not complete, the convergence argument.
- Gradient descent on discontinuous functions can still produce cycles in pathological cases.
- In the synthetic experiments, APStar converged to a viable update direction in every tested instance and was significantly faster than random sampling.Challenging scenarios were also solved, although simple cases required fewer iterations on average.
SAMPLING STAR-CONVEX DISTRIBUTIONS
The sampling procedure constructs star-convex distributions in the simplex by parameterizing star-shaped sets with boundary curves and rejecting samples that violate the theorem’s conditions.
- Points in the simplex can be embedded into R2, enabling parametric curve constructions for the required star-shaped sets.
- APStar required fewer iterations than random sampling and MWU, especially when the triple-intersection area ratio was low.APStar found a viable weight in all scenarios, with simpler sets and initial conditions requiring fewer iterations on average.
- Star-shaped sets in the simplex are represented by boundary curves C_i centered on the corresponding basis elements.Figure 5 illustrates how each boundary curve generates its star-shaped set.
- Property 3 is checked by verifying that the triple intersection covers the entire triangle and satisfies three pairwise curve inequalities.The inequalities are C0(0) + C1(π/3) > 1, C1(0) + C2(π/3) > 1, and C2(0) + C0(π/3) > 1.
A.3. MMPF Implementation Details
The implementation alternates between optimizing a weighted risk and updating group-risk weights, with joint and plug-in estimators evaluated across synthetic and real-data settings.
- Joint estimation uses stochastic gradient descent with uniformly sampled sensitive groups to reduce variance in conditional-risk estimates.The APStar decisions use validation-set risk vectors to improve generalization and limit overfitting.
- Across the synthetic experiments, the algorithm converged effectively with neural-network estimation, and relative errors decreased as training samples increased.
- In Case I, joint estimation is expected to outperform plug-in estimation at the same number of weight updates, whereas Case II may involve negative transfer and unclear relative performance.Case I has no group-risk trade-off under an unbounded hypothesis class; Case II can have group-risk trade-offs.
- In Case I, joint estimation showed a clear benefit, while in Case II plug-in estimation appeared marginally better and both methods improved with more samples.
- Plug-in estimation derives weighted classifiers from estimated conditional probabilities, allowing Pareto-optimal classifiers to be obtained by reweighting output probabilities.The optimal weights can then be found with APStar.
- Joint estimation may benefit from transfer learning, but negative transfer may be required by MMPF when target conditional distributions differ.
- MMPF searches for weights μ* whose weighted-risk solution has minimax Pareto risk r* and alternates optimization with weight updates.The baseline classifier may be a neural network, and the loss and optimization method vary by experiment.
- The real-data evaluation used eight sensitive groups in ICU records, with substantial imbalance between the majority and minority groups.The reported metrics included accuracy, Brier Score, cross-entropy, and calibration errors by group.