A Comprehensive View of Fairness through Distributional Stability

Gayane Taturyan; Charlotte Laclau; Stephan Clémencon

cs.LGSep 29, 2026

A Comprehensive View of Fairness through Distributional Stability

Authors: Gayane Taturyan, Charlotte Laclau, Stephan Clémencon

Organizations: LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France

Abstract

We view fairness as a property of distributional stability. Rather than assessing a predictor under a fixed data distribution, we study how its predictions change under perturbations that modify the composition of protected groups. A predictor is fair if it remains stable under such shifts. Under this perspective, several classical notions of fairness arise as stability with respect to specific perturbations, with the associated unfairness gap given by a Lipschitz constant of a prediction-rate functional. This formulation also yields guarantees that hold uniformly over a range of demographic compositions at test time, without requiring knowledge of the deployment distribution. It leads to a learning procedure based on convex combinations of reweighted predictors, formulated as a second-order cone program, for which we establish generalization bounds. Experiments on standard benchmarks illustrate the approach.

Figures & tables

		Adult			COMPAS
Constraint	Model	${\mathcal{U}}(h)$ $\downarrow$	Deploy gap $\downarrow$	Accuracy $\uparrow$	${\mathcal{U}}(h)$ $\downarrow$	Deploy gap $\downarrow$	Accuracy $\uparrow$
DP	ERM	$.180\pm.005$	$.122\pm.003$	$.845\pm.002$	$.132\pm.009$	$.079\pm.006$	$.680\pm.007$
	ERM+DP	$.036\pm.006$	$\underline{.049\pm.006}$	$\mathbf{.827\pm.002}$	$\underline{.012\pm.006}$	$\underline{.011\pm.004}$	$\underline{.566\pm.019}$
	PostProc	$\underline{.013\pm.009}$	$.097\pm.005$	$\underline{.823\pm.004}$	$.038\pm.021$	$.044\pm.022$	$.555\pm.016$
	Shifty	$.033\pm.021$	$.138\pm.032$	$.802\pm.010$	$.015\pm.012$	$.472\pm.039$	$.510\pm.007$
	STABLE	$\mathbf{{.011\pm.000}}$	$\mathbf{.006\pm.000}^{*}$	$.753\pm.003$	$\mathbf{.012\pm.001}$	$\mathbf{.006\pm.001^{*}}$	$\mathbf{.680\pm.009^{*}}$

Table 1 : Results on the Adult Income and COMPAS datasets (mean

\pm

std over 20 seeds). The deploy gap is

\sup_{\pi^{\prime}\in\{0,1\}}|\Phi(h;\pi^{\prime})-t|

. Bold indicates the best value per column, constraint, and dataset. "*" indicates statistical significance when compared with the second-best result (underlined). Significance is assessed via paired Wilcoxon signed-rank tests. ERM is reported for reference only.

Figure 1 : Prediction rate

\Phi(h;\pi^{\prime})

under demographic shift on the Adult Income and COMPAS datasets for DP and EO. Shaded regions show

\pm

std of the curve shape over 20 random seeds.

Figure 2 : Geographic generalization on ACS Income. (left) Prediction rate

\Phi(h;\pi_{\text{state}})

as a function of the state proportion of White residents. Dashed lines show linear fits per method; (right) Accuracy vs. DP unfairness gap

{\mathcal{U}}(h)

across held-out states. Each point corresponds to one state.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

$p_{1}\;\backslash\;\bar{\pi}$	$0.1$	$0.2$	$0.3$
$0.2$	$1.15$	$0.83$	$0.58$
$0.3$	$0.79$	$0.53$	$0.34$
$0.5$	$0.37$	$0.19$	$0.08$

Appendix

Table 2 : Minimum DRO radius

\varepsilon^{*}(\bar{\pi})

required to cover all demographic shifts

\pi^{\prime}\in[\bar{\pi},1-\bar{\pi}]

, for varying training group proportion

p_{1}

and perturbation lower bound

\bar{\pi}

	ERM + constraint		STABLE (ours)		PostProc		Shifty
	DP	EO	DP	EO	DP	EO	DP	EO
Adult	$3.5\pm{0.39}$	$5.06\pm{1.35}$	$4.98\pm{0.56}$	$6.41\pm{0.6}$	$1.6\pm{0.1}$	$1.85\pm{0.07}$	$284.34\pm{314.12}$	$269.8\pm{165.8}$
COMPAS	$1.01\pm 0.18$	$1.01\pm 0.27$	$1.66\pm 0.52$	$1.69\pm 0.27$	$1.12\pm 0.07$	$1.25\pm 0.08$	$11.67\pm 4.9$	$16.98\pm 6.56$
ACS	$126.8\pm 12$	$101.2\pm 15.8$	$151.2\pm 11.1$	$149.9\pm 10.3$	$8.38\pm 0.67$	$17.0\pm 1.6$	$56.9\pm 11.6$	$50.2\pm 9.8$

Appendix

Table 3 : Average training time per seed (seconds). All experiments run locally on an Apple M2, 16 GB RAM, macOS. Shifty uses Setting 2 (unknown demographic shift,

\alpha=0.25

NA

stands for Not Applicable.

Panel of Figure 3 — Figure 3 : Hyperparameter sensitivity on the Adult dataset (DP constraint, seed 0). Each cell reports the value of accuracy (left), ${\mathcal{U}}(h)$ (center) and deploy gap $\max(|\Phi(h;0)-t|,|\Phi(h;1)-t|)$ (right) as a function of threshold $\delta$ and the perturbation lower bound $\bar{\pi}$ .

	Adult		COMPAS		ACS Income
	DP	EO	DP	EO	DP	EO
$\bar{\pi}$	$0.02$	$0.15$	$0.02$	$0.15$	$0.02$	$0.15$
$\delta$	$10^{-5}$	$10^{-5}$	$10^{-5}$	$10^{-4}$	$10^{-5}$	$10^{-5}$

Appendix

Table 4 : Selected hyperparameters for STABLE.

K=30

and

m=60

are fixed across all settings. N.A. stands for Not Applicable.

Figure 4 : Geographic generalization on ACS Income. (left) Prediction rate

\Phi(h;\pi_{\text{state}})

as a function of the state proportion of White residents. Dashed lines show linear fits per method; (right) Accuracy vs. EO unfairness gap

{\mathcal{U}}(h)

across held-out states. Each point corresponds to one state.

Panel of Figure 5 — Figure 5 : The effect of target $t$ .

Explore similar work

Deep Fair Learning: Task-Aware Fair Representations via Joint Distance-Covariance Regularization
Apr 8, 2025Enze Shi, Yiqun Xiao, Linglong Kong +1Algorithmic Fairness Privacy-Preserving Machine Learning
Department of Mathematical and Statistical Science, University of Alberta.
No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems
Jun 16, 2026Khoat ThanAlgorithmic Fairness Learnability
Hanoi University of Science and Technology
Multi-Distribution Robust Conformal Prediction
Jan 6, 2026Yuqi Yang, Ying JinOnline Conformal Prediction Nonconformity Scores
Mathematics Department, The Hong Kong University of Science and Technology, Hong Kong, China · Department of Statistics and Data Science, University of Pennsylvania, Philadelphia, PA, USA.

Apr 8, 2025, stat.MLJ/K move · Enter open · S save

Deep Fair Learning: Task-Aware Fair Representations via Joint Distance-Covariance Regularization

Enze Shi, Yiqun Xiao, Linglong Kong, Bei Jiang

Department of Mathematical and Statistical Science, University of Alberta.

Algorithmic Fairness Privacy-Preserving Machine Learning

Open paper AskPDF arXiv

Ensuring fairness is essential as machine learning increasingly informs consequential decisions. However, many fairness-aware methods focus on the outputs of individual predictors, without directly controlling sensitive information retained in the underlying representations. We propose Deep Fair Learning (DFL), which combines distance covariance regularization with predictive loss to jointly learn representations and downstream predictors, promoting fairness at both levels while preserving task-relevant information. Its marginal and class-conditional formulations target independence and separation, respectively. Under suitable regularity conditions, we establish non-asymptotic joint excess-risk rates and convergence of the learned representation up to natural invariances. We further derive fairness-inheritance bounds linking representation-level dependence to downstream disparities over suitable predictor classes, extending fairness guarantees beyond the jointly trained predictor. Experiments on tabular, text, and image benchmarks show that DFL achieves lower fairness gaps than competing methods in many evaluated settings while maintaining competitive predictive accuracy, with fairness gains largely preserved after downstream retraining.

Abstract

Explore similar work

Deep Fair Learning: Task-Aware Fair Representations via Joint Distance-Covariance Regularization

No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems

Multi-Distribution Robust Conformal Prediction