Paper deep dive
A Comprehensive View of Fairness through Distributional Stability
Gayane Taturyan, Charlotte Laclau, Stephan Clémencon
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.37061v1
- Canonical: https://arxiv.org/abs/2609.37061v1
Trouble viewing inline? Open PDF directly →
Full Text
125,104 characters extracted from source content.
Expand or collapse full text
A Comprehensive View of Fairness through Distributional Stability Gayane Taturyan Affiliation: LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France Email: gayane.taturyan@telecom-paris.fr Charlotte Laclau Affiliation: LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France Email: charlotte.laclau@telecom-paris.fr Stephan Clemencon Affiliation: LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France Email: stephan.clemencon@telecom-paris.fr 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. 1 Introduction Fairness in the field of machine learning has been studied primarily from two distinct perspectives, leading to the introduction of two broad categories of definitions. Group fairness, on the one hand, requires that predictive outcomes be statistically equal or comparable across groups defined by sensitive characteristics such as gender or ethnic origin, which has given rise to a large number of competing metrics, including demographic parity, equal opportunity, or equalized odds, among others [8, 21]. On the other hand, the concept of individual fairness stipulates as a mandatory condition that similar individuals be assigned similar predictive outcomes, which is formalized by a Lipschitz condition with respect to a task-specific metric [16]. These two approaches rest on different foundations and have been studied largely in isolation. We also note that both of these approaches evaluate fairness relative to a fixed data distribution. In practice, a model trained on one population is often deployed on another, whether in different regions, at different times, or in different institutional contexts. Recent work has begun to investigate how fairness guarantees degrade under such changes [19, 23, 4], but these approaches are either tailored to specific shift models, require knowledge of the deployment distribution at training time, or model the shift as acting on the feature space while leaving the distribution of the sensitive attribute G itself unchanged. Our framework takes a different perspective: we consider perturbations that act directly on the marginal distribution of G, which is the primary driver of deployment bias in practice. In this article, we propose to approach fairness from the perspective of stability — specifically, the distributional stability of a given prediction function rather than the algorithmic stability derived from learning theory. A classifier is fair if its behavior does not change in the face of perturbations in the data distribution that reflect social considerations, such as changes in the composition of protected groups. This single principle links the concepts of fairness at the individual level and at the group level, which appear as special cases corresponding to different classes of perturbations. This naturally resolves the issue of context shifts during deployment: a classifier trained to remain stable in the face of variations in group distribution inherits fairness guarantees that apply uniformly to all demographic compositions at deployment time, without the need to know the deployment distribution in advance. Contributions. We define fairness of a predictive rule as a stability property (Section 2). We then establish formal equivalences between individual fairness, demographic parity, equal opportunity, and stability under specific perturbation classes, showing that the unfairness gap is in each case a Lipschitz constant (Section 3). For group fairness, we unify these results into a single optimization problem via a constraint functional measuring deviation between predictions and a target level across deployment contexts; its decomposition ensures guarantees for both fairness and uniform deployment. Restricting to convex mixtures of reweighted classifiers turns the empirical problem into a second-order cone program, for which we establish generalization bounds (Section 4). Numerical experiments confirm the theory’s practical applicability (Section 5). Proofs, the Equalized Odds extension, and additional experiments and discussions are deferred to the Supplementary Material. Related works. Algorithmic fairness, especially for binary classification, has been extensively studied from both theoretical and methodological perspectives. A large part of this literature considers aware setting, in which the sensitive attribute is available at the prediction time [8, 12, 35, 18, 34, 20, 10], whereas fewer works address the unaware setting [1, 28, 11, 22, 9, 27], in which it is not. A number of works aim to unify fairness-constrained classification within a common framework. A classical example is the reductions approach of Agarwal et al. [1], where the authors reduce fair classification to a sequence of cost-sensitive classification problems and construct a randomized classifier with minimum empirical error under the prescribed constraint. A recent work of Chzhen et al. [11] proposes a unified post-processing framework for randomized classification under general system-level constraints (including group-fairness constraints), based on entropic regularization and stochastic optimization. The stability-based perspective is related to recent work on the robustness of fairness-constrained learning under adversarial perturbations [6], that shows how malicious noise in the training data can significantly affect the validity of fairness constraints. In our work we define fairness itself as a stability under perturbations. Despite an initial resemblance to distributionally robust optimization approaches, our framework is based on specific perturbations induced by a prescribed perturbation rule and admits an importance-weight representation. Unlike DRO, this structural specificity yields non-vacuous deployment guarantees, as we discuss in Appendix A.2. Notation. For an integer K>0K>0, we define [K]=def 1,⋯,K[K] -0.75346pt def =\1,·s,K\ and write ΔK _K for the probability simplex in ℝKR^K. The notation ~ O hides unimportant constants and logarithmic terms. 2 Defining fairness as a property of stability The concept of stability is ubiquitous in the sciences, particularly in mathematics, as it describes how a “system”, such as a machine-learning algorithm, responds to changes in the parameters or data used to define it. The various notions of stability and their applications are far too numerous to list here and we refer to Appendix A.1 for an in-depth description in the machine-learning context. Instead of the main concepts of a predictor’s fairness introduced in the literature, we propose a definition based on the concept of stability under changes in the data distribution. As we will see in the following sections, this new definition allows us to subsume the previous ones within a unified formal framework. 2.1 Background and preliminaries Let us consider the generic problem of predictive learning with fairness concerns regarding sensitive attributes G valued in G, where the random label Y takes values in a space Y equipped with a metric d:2→[0,∞)d_Y:Y^2→[0,∞), and the predictive information is modelled by a random vector X, valued in a high-dimensional metric space (,d)(X,d_X). By =(,g,y) z=( x,g,y) is meant a realization in the product space =×Z=X×G×Y of the random triplet =(,G,Y) Z=( X,G,Y), defined on a probability space (Ω,ℱ,ℙ)( ,F,P) with joint distribution D describing the system under study, by h:→h:X→Y an arbitrary (measurable) predictive rule in unaware setting. Equipped with these notations, let us now review the standard definitions that aim to formalize algorithmic fairness. Individual fairness (IF), introduced by Dwork et al. [16], which requires that similar individuals receive similar predictions, is defined as follows. Definition 1 (Individual Fairness). A predictor h:→h:X→Y satisfies the IF property when it satisfies the (d,d)(d_Y,d_X)-Lipschitz condition for some constant L<∞L<∞: ∀(,′)∈2,d(h(),h(′))⩽L⋅d(,′).∀( x, x )∈X^2,\;\;d_Y(h( x),h( x )) L· d_X( x, x )\,. The concept of group fairness differs in that it requires measures of performance to be identical across groups defined by the sensitive attribute G. Depending on the type of predictive problem considered (e.g., classification, regression, ranking) and the criterion chosen to measure performance, it can take various forms. Among those introduced in the literature, below we highlight the following two major notions for binary classification (i.e., =0,1Y=\0,1\), that will serve as main examples in the subsequent analysis. For simplicity, the definitions are given for only two sensitive groups, i.e., =0,1G=\0,1\. They can be immediately extended to the case where the sensitive attribute G takes more than two values. Definition 2 (Demographic Parity). A predictor h:→0,1h:X→\0,1\ satisfies Demographic Parity (DP) if its predictions are independent of G: Pr(h()=1|G=0)=Pr(h()=1|G=1) (h( )=1 G=0)\;=\; (h( )=1 G=1). The concept of equal opportunity (EO) requires that there be no disparity with respect to a specific aspect of predictive performance. Definition 3 (Equal Opportunity). A classifier h satisfies the EO property if it achieves equal true positive rates across groups: Pr(h()=1∣Y=1,G=0)=Pr(h()=1∣Y=1,G=1) (h( )=1 Y=1, G=0)\;=\; (h( )=1 Y=1, G=1). The concept of Equalized Odds (EOdd) strengthens the EO property by requiring the equality to hold conditionally on both values of the label; its definition is recalled in Appendix D. 2.2 A new definition of fairness for a predictive rule We now propose to define the fairness of a predictor as a stability property. The concept of stability is already widely used in statistical learning theory, primarily to account for the sensitivity of a learning algorithm to changes in the training examples [7, 24]. An algorithm is said to be stable if replacing a few training data points does not significantly change the learned function. The framework we are developing here is of a different nature. We consider a fixed prediction function h and seek to quantify how its outputs change as the distribution of sensitive attributes G varies. Unlike domain adaptation [29], which aims to correct such changes, we characterize predictors whose behavior remains stable in the face of these perturbations, and show that classical notions of fairness naturally follow from the requirement for this specific type of stability. Consider a class P of (perturbation) operators :D⊂ℳ1()→ℳ1()P:D _1(Z) _1(Z) acting on the elements D of a domain ℳM included in the set ℳ1()M_1(Z) of probability measures on Z to produce a perturbed probability measure ()P(D) on Z. Since only the values taken by the variable h(X)h(X) are relevant to the definition of individual fairness, we set Z equal to X in this case. With this in mind, we propose the following definition, inspired by the formalism of PAC learning. Definition 4 (Fairness as Distributional Stability). Consider a class P of perturbation operators acting on a domain D⊂ℳ1()D _1(Z) and a prediction function h:→h:X→Y. Let ε>0 >0 and Δ(h,(,)) (h;\;(D,P)) be a statistical distance between the distributions of the prediction h(X)h(X) under ∈ℳD and under ()P(D). The prediction function h is said to be ε -fair w.r.t. P and Δ if and only if sup(,)∈ℳ×Δ(h,(,))⩽ε. _(D,P) ×P (h;\;(D,P)) \,. The choice of P and that of Δ are left intentionally general here; specific and interpretable instances are constructed in Section 3. As we shall see, it is natural to consider perturbations of the distribution of the sensitive attribute G in the context of group fairness. 3 From various existing concepts of fairness to a unified approach In this section, we show that the general formalism introduced accounts for the various concepts of individual and group fairness for specific choices of the class of P and the statistical distance Δ . 3.1 Individual fairness and local perturbations The feature space X being equipped with a task-specific metric d_X, as in Dwork et al. [16], consider the class of transformations of X indexed by ρ>0ρ>0: ρ=T:→;T measurable and ∀∈,d(,T())≤ρ.T_ρ=\T:X→X; T measurable and ∀ x∈X, d_X( x,T( x))≤ρ\\,. (1) Each transformation T∈ρT _ρ is naturally associated with a perturbation operator TP_T acting on the distribution of X and assigning to any probability distribution D on X its pushforward by T. Proposition 1 (IF and Stability). Let h:→h:X→Y be a prediction function and d:2→[0,∞)d_Y:Y^2→[0,∞) a metric on predictions. The following assertions are equivalent. 1. The predictive function h satisfies the IF property with (d,d)(d_Y,d_X)-Lipschitz constant L<∞L<∞. 2. For all ρ>0ρ>0, the predictive function h is LρLρ-fair w.r.t. to the class ρP_ρ of perturbation operators TP_T, T∈ρT _ρ, defined on the domain ℳ=δ:∈M=\ _ x:\; x∈X\ of all point masses and taking Δ(h,(,)) (h;\;(D,P)) as the Wasserstein 11-distance between the pushforward of h()h( X)’s distribution under D and that under ()P(D) based on the cost function d_Y: sup(,T)∈×ρd(h(),h(T()))⩽Lρ. _( x,T)∈X×T_ρd_Y(h( x),h(T( x))) Lρ\,. (2) Individual fairness is therefore equivalent to distributional stability in the sense of Definition 4, with a stability parameter LρLρ proportional to the perturbation parameter ρ. 3.2 Group fairness and resampling perturbations We now consider the various notions of group fairness. Rather than perturbing individual feature vectors, we consider perturbations that act on the marginal distribution of the sensitive attribute G (assumed binary for simplicity). The magnitude of the perturbation is parametrized here by the proportion π∈(0,1)π∈(0,1) of group G=1G=1 in the population, and Δ measures how the prediction rates of h change as this proportion varies. We introduce two types of perturbation. The first resamples G globally, while the second resamples G within the positive label class. Perturbation 1. The class πGP^G_π is composed of all operators :ℳ1()→ℳ1()P:M_1(Z) _1(Z) such that, for all distribution ∈ℳ1()D _1(Z), 1) the conditional distribution of (,Y)( X,Y) given G is the same under D and under ()P(D), 2) ℙ()(G=1)=πP_P(D)(G=1)=π. Such a class is non empty, since the type 1 perturbations of a distribution D are in 1-to-1 correspondence with the Bernoulli random variables on (Ω,ℱ,ℙ)( ,F,P) with parameter π. Perturbation 2. The class πG|1P^G 1_π is composed of all operators :ℳ1()→ℳ1()P:M_1(Z) _1(Z) such that, for all distribution ∈ℳ1()D _1(Z), 1) X’s conditional distribution given (Y,G)(Y,G) and Y’s distribution are the same under D and under ()P(D), 2) ℙ()(G=1∣Y=1)=πP_P(D)(G=1 Y=1)=π. Remark 1 (On perturbations). In Perturbation 2, we fix ℙ(∣Y,G)P( X Y,G) rather than the stronger ℙ(,Y∣G)P( X,Y G) used in Perturbation 1. While ℙ(,Y∣G)P( X,Y G) implies the invariance of ℙ(∣Y,G)P( X Y,G), it also implies the invariance of ℙ(Y∣G)P(Y G). This, combined with the imposed constraint of ℙ()(G=1∣Y=1)=πP_P(D)(G=1 Y=1)=π, may be infeasible by Bayes’ rule. Fixing only ℙ(∣Y,G)P( X Y,G) ensures feasibility. Given a perturbation operator ∈π□P _π , with □∈G,G∣1 ∈\G,G 1\ and a base distribution D, we write π=def ()D_π -0.75346pt def =P(D). We show that group fairness constraints can be expressed by a certain descriptive functional that depends on the perturbation setting and is affine w.r.t. the perturbation parameter. Throughout the paper, we reserve the label Claim for statements that generalize a pattern observed on the running examples (e.g., DP, EO), under conditions tailored to each perturbation rule. Definition 5 (Prediction rate functional). For a prediction function h:→0,1h:X→\0,1\ and a perturbation parameter π∈[0,1]π∈[0,1], we define the functional Φ(h,π)=def π[φh()], (h;π) -0.75346pt def =E_D_π[ _h( Z)]\,, where φh:→[0,1] _h:Z→[0,1] is some statistic that is linear w.r.t. h. Claim 1. Let πD_π be a perturbed distribution obtained from D according to a given, appropriate perturbation rule and a fixed perturbation parameter π∈[0,1]π∈[0,1]. The prediction rate functional Φ(h,π) (h;π) admits a form Φ(h,π)=α(h)+πγ(h), (h;π)=α(h)+πγ(h)\,, (3) where α(h)α(h) and γ(h)γ(h) are some prediction rate quantities under the initial (unperturbed) distribution D. Moreover, it holds that |Φ(h,π)−Φ(h,π′)|=|γ(h)||π−π′|,∀π,π′∈[0,1], and | (h;π)- (h;π )|=|γ(h)||π-π |\,, ∀π,π ∈[0,1]\,, and (4) supπ,π′∈[0,1]|Φ(h,π)−Φ(h,π′)|=|γ(h)|=def (h), _π,π ∈[0,1]| (h;π)- (h;π )|=|γ(h)| -0.75346pt def =U(h)\,, (5) where (h)U(h) is the explicit fairness gap (unfairness) for each constraint. The functional Φ(h,π) (h;π), although at first obscure, clearly captures the intuition behind each constraint, by being defined as a relevant prediction rate under the perturbed distribution. We now show that DP and EO correspond, respectively, to stability under the introduced perturbations. Throughout, h:→0,1h:X→\0,1\ is a possibly randomized prediction function and G∈0,1G∈\0,1\ is the sensitive attribute. Demographic Parity and Stability. Let πD_π be a perturbed distribution according to Perturbation 1. We define the global positive prediction rate under πD_π as Ph(π)=def ℙπ(h()=1)=π[h()]P_h(π) -0.75346pt def =P_π(h( X)=1)=E_D_π[I \h( X) \] (or π[h()]E_D_π[h( X)] when randomized) and denote by rg(h)=def ℙ(h()=1∣G=g)r_g(h) -0.75346pt def =P(h( X)=1 G=g) . Proposition 2. The prediction h satisfies DP if and only if Ph(π)P_h(π) is constant in π. Moreover, Ph(π)=r0(h)+π(r1(h)−r0(h)), and supπ,π′∈[0,1]|Ph(π)−Ph(π′)|=|r1(h)−r0(h)|.P_h(π)=r_0(h)+π(r_1(h)-r_0(h))\,, and _π,π ∈[0,1]|P_h(π)-P_h(π )|=|r_1(h)-r_0(h)|\,. The deviation from stability coincides exactly with the DP gap. This result also connects DP to sample representativity: if the training dataset has group proportions that differ from the population, resampling perturbations model precisely this shift. Example 1. Suppose the model predicts a positive outcome for 80%80\% of individuals in group 00 and for 40%40\% of individuals in group 11, so r0(h)=0.8r_0(h)=0.8 and r1(h)=0.4.r_1(h)=0.4\,. The global positive prediction rate under a population with group prevalence π is Ph(π)=0.8(1−π)+0.4π=0.8−0.4π.P_h(π)=0.8\,(1-π)+0.4\,π=0.8-0.4\,π\,. Thus, as π varies from 00 to 11, the prediction rate decreases linearly from 0.80.8 to 0.40.4, and the maximal deviation is supπ,π′∈[0,1]|Ph(π)−Ph(π′)|=|r0−r1|=0.4, _π,π ∈[0,1]|P_h(π)-P_h(π )|=|r_0-r_1|=0.4\,, which is the DP gap. The same analysis applies to intra-class resampling. Equal Opportunity and Stability. Let πD_π be a perturbed distribution according to Perturbation 2. We define the true positive prediction rate under πD_π as Ph|Y=1(π)=def ℙπ(h()=1∣Y=1)=π[h()Y=1ℙ(Y=1)]P_h Y=1(π) -0.75346pt def =P_D_π(h( X)=1 Y=1)=E_D_π [ I \h( X) \I \Y=1 \P(Y=1) ] (or π[h()Y=1ℙ(Y=1)]E_D_π[ h( X)I \Y=1 \P(Y=1)] when randomized) and denote by qg(h)=def ℙ(h()=1∣G=g,Y=1)q_g(h) -0.75346pt def =P(h( X)=1 G=g,Y=1) . Proposition 3. The prediction h satisfies EO if and only if Ph|Y=1(π)P_h|Y=1(π) is constant in π. Moreover, Ph|Y=1(π)=q0(h)+π(q1(h)−q0(h)), and supπ,π′∈[0,1]|Ph|Y=1(π)−Ph|Y=1(π′)|=|q1(h)−q0(h)|.P_h Y=1(π)=q_0(h)+π(q_1(h)-q_0(h))\,, and _π,π ∈[0,1]|P_h Y=1(π)-P_h Y=1(π )|=|q_1(h)-q_0(h)|\,. Claim 2. Due to linearity of φh _h w.r.t. h (Definition 5), there exists a constant B>0B>0 such that for every measurable function f:→ℝf:X , it holds that [φf()]⩽B|f()|E[ _f( Z)] BE|f( X)|. For example, in the case of Demographic Parity, we have φh()=h() _h( X)=h( X) and B=1B=1. Variance control. It is easy to notice that in all of the examples we have supπ,π′∈[0,1]|Φ(h,π)−Φ(h,π′)|=|Φ(h,1)−Φ(h,0)| _π,π ∈[0,1]| (h;π)- (h;π )|=| (h;1)- (h;0)|, meaning the supremum is achieved at the endpoints. This rewrites the problem as the usual “minimization under DP/EO”. However, our interest lies within the resampling aspect of the problem. Rather than focusing on the worst-case deviation over all perturbations, we now adopt a stochastic viewpoint, in which perturbations are achieved according to a distribution Π . This allows us to quantify fairness in terms of average sensitivity, leading to smoother and more tractable constraints. We propose to reformulate the constraint through variance control. Definition 6 (Perturbation variance functional). Let Π be a probability measure on [0,1][0,1] and π∼Ππ . We define the perturbation variance functional as Π(h)=def Varπ∼Π(Φ(h,π)).V_ (h) -0.75346pt def = _π ( (h;π))\,. From Definition 5, we have that Φ(h,π)=α(h)+πγ(h) (h;π)=α(h)+πγ(h). Using the fact that for a,b∈ℝa,b and a random variable X, Var(a+bX)=b2Var(X) (a+bX)=b^2 (X), we get Π(h)=γ(h)2Varπ∼Π(π).V_ (h)=γ(h)^2 _π (π)\,. This equation above leads to the equivalence (h)⩽ε⇔Π(h)⩽ε2Varπ∼Π(π).\,U(h) \, \,V_ (h) ^2 _π (π)\,. Links between individual and group fairness. As we established, both individual and group fairness can be equivalently expressed by our notion of stability from Definition 4. Let us emphasise one more connection between the two. The functional Φ(h,π) (h;π) is Lipschitz w.r.t. perturbation parameter π (4), and its Lipschitz constant is exactly the unfairness gap. This provides a complementary angle to view fairness notions: while individual fairness requires similar predictions for similar individuals, formalized by Lipschitz property of the prediction function w.r.t. the feature space, our generalized group-fairness formulation requires stability of perturbation-indexed prediction rates under small changes in the perturbation parameter, that is, Lipschitz continuity of the map π→Φ(h,π)π→ (h;π). However, despite these conceptual analogies and the possibility of extending our variance-based perspective to individual fairness through suitably randomized local perturbations, the methodologies required to achieve fairness in the two settings remain structurally different. We therefore focus from now on on group fairness, leaving explorations of corresponding methods for individual fairness to future work. 4 Methodology: variance and mean control with mixture models 4.1 Problem formulation Variance and mean control. Under the introduced perturbation-variance functional constraint, the problem reduces to classical fairness constraints, with a scaling governed by the variance of the perturbation-parameter distribution. This holds even for the empirical problem. Rather than controlling only the variability of Φ(h,π) (h;π) across perturbations, we consider a stricter objective of requiring Φ(h,π) (h;π) to remain close to a given target level t. Definition 7 (Perturbation t-variance functional). Let Π be a probability measure on (0,1)(0,1) and π∼Ππ . For a t∈[0,1]t∈[0,1], we define the perturbation t-variance functional as Π(h,t)=def π∼Π[(Φ(h,π)−t)2].C_ (h;t) -0.75346pt def =E_π [( (h;π)-t)^2]\,. Adding and subtracting π∼Π[Φ(h,π)]E_π [ (h;π)] inside the square yields the following decomposition: Π(h,t)=Π(h)+(π∼Π[Φ(h,π)]−t)2.C_ (h;t)=V_ (h)+(E_π [ (h;π)]-t)^2\,. (6) As the decomposition (6) shows, the functional Π(h,t)C_ (h;t) controls not only the variance term equivalent to fairness, but also the mean level of Φ(h,π) (h;π) itself. Moreover, one can notice that Π(h)=inft∈[0,1]Π(h,t), with t⋆=π∼Π[Φ(h,π)].V_ (h)= _t∈[0,1]C_ (h;t)\,, with t =E_π [ (h;π)]\,. Thus, we can state the following obvious lemma. Lemma 1. If h satisfies Π(h,t)⩽δC_ (h;t) δ for t∈[0,1],t∈[0,1], then Π(h)⩽δV_ (h) δ and (π∼Π[Φ(h,π)]−t)2⩽δ(E_π [ (h;π)]-t)^2 δ. Remark 2 (On the choice of t). We can choose t as desired, or, more naturally, we can set t=π∼Π[Φ(h0,π)]t=E_π [ (h_0,π)], where h0h_0 is an unconstrained baseline. The impact of t is studied in Appendix E.4. We introduce the following standard regularity assumption on the loss. Assumption 1. The loss ℓ:[0,1]×→[0,1] :[0,1]×Y→[0,1] is convex and L-Lipschitz in its first argument. We define the corresponding population risk of a predictor h:→[0,1]h:X→[0,1] by ℛ(h)=def [ℓ(h(),Y)]R(h) -0.75346pt def =E[ (h( X),Y)]. Given a t∈[0,1]t∈[0,1], our goal is to solve the following constrained problem minh∈ℋℛ(h):Π(h,t)⩽δ. _h \R(h)\,:\,C_ (h;t) δ \\,. (P) Convex mixtures. In our framework, fairness is characterized through the behaviour of the prediction function across a family of perturbed distributions. This makes it natural to combine predictors trained on different distributions, especially given that model averaging has already been shown to be effective for enforcing fairness in the classical setting [17]. For π1,⋯,πK∼i.i.d. Π _1,·s, _K -0.45206pt i.i.d.~ , let η1,⋯,ηK _1,·s, _K be (unconstrained) Bayes regression functions minimizing the risks on respective distributions π1,⋯,πKD_ _1,·s,D_ _K, that is ηk∈argminhℛk(h),for k∈[K]. _k∈ _hR_D_k(h)\,,for k∈[K]\,. For ∈ΔK α∈ _K, we define a convex mixture =def ∑k=1Kαkηk η_ α -0.75346pt def = _k=1^K _k _k. Rather than optimizing the true risk of the mixture directly, we focus on its linearized convex surrogate, defined as ℛ¯()=def ∑k=1Kαkℛ(ηk) R( η_ α) -0.75346pt def = _k=1^K _kR( _k). Since the loss is convex in prediction, Jensen’s inequality implies that ℛ()=ℛ(∑k=1Kαkηk)⩽∑k=1Kαkℛ(ηk)=ℛ¯(),R( η_ α)=R( _k=1^K _k _k) _k=1^K _kR( _k)= R( η_ α)\,, showing that this surrogate upper-bounds the actual risk of the convex mixture. Given a t∈[0,1]t∈[0,1], the problem ( P ) translates as ⋆∈argmin∈ΔKℛ¯():Π(,t)⩽δ. α ∈ _ α∈ _K \ R( η_ α)\,:\,C_ ( η_ α;t) δ \\,. Empirical problem. Let us define the empirical counterparts of the quantities of our interest and consider the empirical problem of (4.1). We define the empirical risk of h on an i.i.d. sample N=1,⋯,ND^N=\ Z_1,·s, Z_N\ as ℛ^N(h)=def 1N∑i=1Nℓ(h(i),Yi) R_D^N(h) -0.75346pt def = 1N _i=1^N (h( X_i),Y_i). Let η^k∈argminhℛ^πkN(h) η_k∈ _h R_D^N_ _k(h) estimate ηk _k for all k∈[K]k∈[K] on the perturbed samples of ND^N. For ∈ΔK α∈ _K, we define ^=def ∑k=1Kαkη^k η_ α -0.75346pt def = _k=1^K _k η_k. Assumption 2. (Regression rates) It holds that maxk⩽K|η^k−ηk|⩽ρN _k KE| η_k- _k| _N. Remark 3. (On regression rates) Assumption 2 can be satisfied with ρN⩽~(1/N) _N O( 1 N) for parametric cases, and even with faster rates under certain assumptions. For example, under the assumption, that there exist β∈ℕ∖0β \0\ and L>0L>0, such that |η()−η(′)|⩽L‖−′‖β,|η( x)- _ x( x )| L\| x- x \|^β\,, where η _ x is Taylor polynomial of degree β at x, and under an additional assumption that the support of ℙP_ X is =[−1,1]dX=[-1,1]^d and it admits density uniformly lower and upper bounded on X, then for some constants C1,C2C_1,C_2, it holds that supℙn(|η()−η^()|⩾ϵ)⩽C1exp(C2N−2β2β+dϵ2) _PP_n(|η( X)- η( X)| ε) C_1 (C_2 N^- 2β2β+dε^2) [3, Theorem 3.2]. Here, Assumption 2 is satisfied with ρN⩽~(N−β2β+d) _N O(N^- β2β+d). Lemma 2 (Mixture rates). Under Assumption 2 and Claim 3, |^−|⩽ρNE| η_ α- η_ α| _N for all ∈ΔK α∈ _K. Let n=1,⋯,nD^n=\ Z_1,·s, Z_n\ be i.i.d. samples from D, and Πm=π1′,⋯,πm′ ^m=\π _1,·s,π _m\ be i.i.d. samples from Π . For a fixed π′π , we define Φ^n(h,π′)=def 1n∑i=1nwπ(i)φh(i) _n(h;π ) -0.75346pt def = 1n _i=1^nw_π( Z_i) _h( Z_i). Let ^∈ℝm×K A ^m× K be a matrix with elements A^j,k=Φ^n(η^k,πj) A_j,k= _n( η_k, _j). Notice, that we can rewrite the empirical constraint as ^n,m(^,t)=1m‖^α−t‖22. C_n,m( η_ α,t)= 1m\| Aα-t1\|_2^2\,. Denoting r^k=def ℛ^(η^k) r_k -0.75346pt def = R( η_k) and ^=(r^1,⋯,r^K) r=( r_1,·s, r_K), we obtain the following second-order cone program (SOCP) ^∈argmin∈ΔK^⊤:‖^−t‖2⩽mδ. α∈ _ α∈ _K \ r α\,:\, \| A α-t1 \|_2 mδ \\,. (SOCPP_ SOCP) Feasibility and existence. The problem ( P SOCP ) has a continuous linear objective, and the simplex ΔK _K is compact and convex. Therefore, once feasibility is established, existence of an optimizer follows from the Weierstrass extreme value theorem. In classical fairness problems, (strict) feasibility is ensured by constant functions, but in our mixture setting one cannot generally claim that a constant function belongs to the convex hull of ηkk=1K\ _k\_k=1^K (or η^kk=1K\ η_k\_k=1^K). However, if we augment both population and empirical dictionaries by constant functions hK+1≡1h_K+1≡ 1 and hK+2≡0h_K+2≡ 0, and choose =(0,⋯,0,t,1−t) α=(0,·s,0,t,1-t), yielding a constant predictor h≡th_ α≡ t, we will have Π(t,t)=0<δC_ (t,t)=0<δ (or ^n,m(t,t)=0<δ C_n,m(t,t)=0<δ). Note, that these two additional predictors do not affect our general theoretical results, thus we omit them from our discussion, and impose strict feasibility as an assumption. Assumption 3 (Strict feasibility). There exists 0∈ΔK α^0∈ _K s.t. Π(0,t)<δC_ ( η_ α^0;t)<δ. 4.2 Constructing perturbations Let us denote by pg=def ℙ(G=g)p_g -0.75346pt def =P(G=g) and pg,y=def ℙ(G=g∣Y=y)p_g,y -0.75346pt def =P(G=g Y=y) for all g,y∈0,1.g,y∈\0,1\\,. Assumption 4 (Bounded group probabilities). Let pg,pg,y∈[p¯,1−p¯]p_g,p_g,y∈[ p,1- p], with p¯∈(0,1/2) p∈(0, 12). Assumption 5 (Bounded perturbations). Let Π be supported on [π¯,1−π¯][ π,1- π], with π¯∈(0,1/2) π∈(0, 12). The construction of perturbations is twofold. First, we consider stratified sampling from Π . Letting Π=U(π¯,1−π¯) =U( π,1- π), we partition [π¯,1−π¯][ π,1- π] uniformly into intervals I1,⋯,ImI_1,·s,I_m of length (1−2π¯)m (1-2 π)m, and sample πj′∼U(Ij)π _j U(I_j) independently for j=1,⋯,mj=1,·s,m. The stratification yields faster convergence rates, as discussed in the next section. Then, for a perturbation parameter π∈Ππ∈ , the corresponding distribution shift is represented through importance-weights, defined by the Radon-Nikodym derivative as wπ()=def dπd()>0.w_π( z) -0.75346pt def = dD_πdD( z)>0\,. For our examples, Assumptions 4,5 ensure that π≪D_π , and we can explicitly compute wπw_π (Appendix C.1). Applying Radon-Nikodym theorem gets us Φ(h,π)=π[φh()]=[wπ()φh()]. (h;π)=E_D_π[ _h( Z)]=E[w_π( Z) _h( Z)]\,. This means, that instead of resampling, we can just compute and plug in the respective importance weights onto our expressions. Claim 3 (Bounded weights). Under Assumptions 4,5, ∃W>0∃ W>0 s.t. wπ()<W,∀(π,)∈Π×w_π( Z)<W,∀(π, Z)∈ ×Z. 4.3 Convergence rates We now turn to the convergence analysis of the finite procedure, aiming to understand how the empirical solution ^ η_ α is approaching its population counterpart ⋆ η_ α . There are three sources of error in our framework, each contributing in its own rate. Under Assumption 2 and Remark 3, estimating regression functions ηk _k from N samples of ND^N yields to an error ρN≍N−β2β+d _N N^- β2β+d, that under convexity transfers to the mixture η_ α as well. Linearity of φh _h in h, combined with Claims 2,3 leads to overall rate of |Φ(^,π)−Φ(,π)|⩽δN≍ρN| ( η_ α;π)- ( η_ α;π)| _N _N. For a fixed π′π , under Claim 3, and with Bernstein’s inequality, the empirical approximation of Φ(η^k,π′) ( η_k;π ) from n samples from nD^n contributes δn≍n−12 _n n^- 12. The third error comes from perturbation parameter sampling, where for any Lipschitz function of π, stratification of [π¯,1−π¯][ π,1- π] into m intervals replaces the usual m−12m^- 12 by δm≍m−32 _m m^- 32. The risk analysis relies on a value continuity argument, that follows from Assumption 3. Under Assumption 1, the approximation of the linearized risk introduces an additional error δn(R)≍n−12 _n(R) n^- 12. The combination of the introduced errors leads to the following (informal) theorem. The formal versions of all the statements from this section, along with their proofs, are given in Appendix C.2. Theorem 1 (Informal). Suppose Assumptions 1–5 hold. Then, conditionally on ND^N and with “high probability” over (n,Πm)(D^n, ^m), the following hold. 1. Constraint. Let ^∈ΔK α∈ _K s.t. ^n,m(^,t)⩽δ C_n,m( α;t) δ. Then, Π(^^,t)⩽(δ+δn)2+δm.C_ ( η_ α;t) ( δ+ _n)^2+ _m\,. 2. Unfairness. It holds that (^^)⩽(δ+δn+δm)/VarΠ(π).U( η_ α) ( δ+ _n+ _m) _ (π)\,. 3. Uniform Deployment. For all π′∈[π¯,1−π¯]π ∈[ π,1- π], it simultaneously holds that |Φ(^^,π′)−t|⩽(δ+δn+δm)⋅(1+|π′−Π[π]|/VarΠ(π)).| ( η_ α;π )-t| ( δ+ _n+ _m)· (1+ |π -E_ [π]| _ (π) )\,. 4. Risk. There exists a constant 0<C<∞0<C<∞, s.t. it holds that ℛ¯(^^)−ℛ¯(⋆)⩽L⋅δN+C⋅(2δ(δn+δN)+(δn+δN)2+δm)+2δn(R). R( η_ α)- R( η_ α ) L· _N+C·(2 δ( _n+ _N)+( _n+ _N)^2+ _m)+2 _n(R)\,. Theorem 1 shows that the rates in 11,22 and 44 are within ~(n−12+m−32+N−β2β+d) O(n^- 12+m^- 32+N^- β2β+d). It also shows that our reformulated problem (4.1) doesn’t yield any convergence loss for unfairness, and provides additional guarantee for deployment. The deployment gap is the largest at the extreme points π′∈0,1π ∈\0,1\, corresponding to single-group populations. Unlike a classifier trained under a classical fairness constraint (e.g., DP,EO) at the training marginal p1p_1, that only controls the unfairness, and does not prevent Φ(h,π′) (h;π ) from drifting linearly as π′π changes, the solution ^ η_ α of ( P SOCP ) controls both the slope γ(^^)γ( η_ α) and the absolute level around t, yielding a strictly stronger and distribution-free deployment guarantee. This also highlights the role of Π as a design parameter. Since the guarantee improves with VarΠ(π) _ (π), choosing broader perturbation law leads to stronger fairness guarantees. 5 Numerical experiments Table 1: Results on the Adult Income and COMPAS datasets (mean ± std over 20 seeds). The deploy gap is supπ′∈0,1|Φ(h,π′)−t| _π ∈\0,1\| (h;π )-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. Adult COMPAS Constraint Model (h)U(h) ↓ Deploy gap ↓ Accuracy ↑ (h)U(h) ↓ Deploy gap ↓ Accuracy ↑ DP ERM .180±.005.180±.005 .122±.003.122±.003 .845±.002.845±.002 .132±.009.132±.009 .079±.006.079±.006 .680±.007.680±.007 ERM+DP .036±.006.036±.006 .049±.006¯ .049±.006 .827±.002.827±.002 .012±.006¯ .012±.006 .011±.004¯ .011±.004 .566±.019¯ .566±.019 PostProc .013±.009¯ .013±.009 .097±.005.097±.005 .823±.004¯ .823±.004 .038±.021.038±.021 .044±.022.044±.022 .555±.016.555±.016 Shifty .033±.021.033±.021 .138±.032.138±.032 .802±.010.802±.010 .015±.012.015±.012 .472±.039.472±.039 .510±.007.510±.007 STABLE .011±.000.011±.000 .006±.000∗.006±.000^* .753±.003.753±.003 .012±.001.012±.001 .006±.001∗.006±.001^* .680±.009∗.680±.009^* EO ERM .075±.015.075±.015 .037±.007.037±.007 .845±.002.845±.002 .126±.013.126±.013 .069±.007.069±.007 .680±.007.680±.007 ERM+EO .021±.015¯ .021±.015 .018±.008¯ .018±.008 .842±.003¯ .842±.003 .015±.007∗.015±.007^* .056±.006¯ .056±.006 .595±.050¯ .595±.050 PostProc .036±.025.036±.025 .052±.012.052±.012 .841±.002.841±.002 .074±.037.074±.037 .089±.044.089±.044 .525±.017.525±.017 Shifty .043±.024.043±.024 .081±.053.081±.053 .824±.012.824±.012 .046±.029¯ .046±.029 .363±.085.363±.085 .550±.021.550±.021 STABLE .013±.009∗.013±.009^* .013±.007∗.013±.007^* .844±.003.844±.003 .052±.008.052±.008 .029±.005∗.029±.005^* .651±.010∗.651±.010^* Figure 1: Prediction rate Φ(h,π′) (h;π ) under demographic shift on the Adult Income and COMPAS datasets for DP and EO. Shaded regions show ± std of the curve shape over 20 random seeds. We evaluate our approach (referred to as STABLE) on two benchmark datasets under both DP and EO constraints11 1 The code is available at https://anonymous.4open.science/r/stable-fairness-public-7AC7/.. On Adult Income [5] and COMPAS [2], we consider binary classification with gender and race as sensitive attributes, comparing against ERM under constraints [1], PostProc [11] and Shifty [19]. Demographic shift is simulated via importance weighting (see Appendix E.1). We also consider a large-scale deployment scenario using ACS Income [15], a survey of the US adult population covering all 5050 states, each with a distinct racial composition. We train on California and evaluate on 1111 held-out states, whose proportion of White residents varies, constituting a real geographic demographic shift rather than a simulated one. The target t is set as the mean prediction of ERM on the training set (DP) or the average group-conditional TPR of ERM (EO). An analysis of hyperparameters and the impact of t values on training is conducted in Appendices E.1 and E.4. Results. The accuracy-fairness tradeoff varies across settings. Overall, STABLE is highly competitive with the other models (Table 1). On Adult, it outperforms all baselines under EO, while under DP it suffers a notable loss in accuracy, despite achieving the lowest unfairness and deployment gap. On COMPAS, it outperforms all baselines under DP and, under EO, still achieves the best accuracy and deployment gap, although with higher unfairness. Overall, this is consistent with the theory: the SOCP constraint controls both the slope γ(h)γ(h) and the absolute level of Φ(h,π′) (h;π ) around t (Figure 1), which is strictly stronger than the classical fairness constraint and shrinks the feasible set accordingly. Moreover, SOCP optimizes a linearized surrogate of the risk, which, despite upper-bounding the true mixture risk, introduces a linearization gap that may occasionally translate into reduced accuracy. Figure 2: Geographic generalization on ACS Income. (left) Prediction rate Φ(h,πstate) (h; _state) as a function of the state proportion of White residents. Dashed lines show linear fits per method; (right) Accuracy vs. DP unfairness gap (h)U(h) across held-out states. Each point corresponds to one state. On the ACS geographic experiment, STABLE remains the closest to t across all held-out states (Figure 2). The other baselines, even Shifty that considers demographic shift, introduce a systematic geographic bias: their slope πstate↦Φ(h,πstate) _state (h; _state) is negative, causing them to drift below t in high-proportion states. This illustrates that controlling static unfairness does not preclude deployment bias. On the accuracy-DP unfairness trade-off, Shifty and STABLE behave similarly, while the others maintain a higher accuracy but at the cost of a larger variance in fairness scores. 6 Conclusion and perspectives We introduced a stability-based perspective on fairness and showed that both individual and group fairness arise from it through appropriate perturbation classes. We then introduced a stronger constraint that jointly controls group fairness and the stability of the prediction rate across perturbations, and showed that when considering a linearized risk, the problem admits a tractable SOCP solution. We further established convergence guarantees from empirical to population quantities and illustrated the practical relevance of the problem through numerical experiments and comparisons to various benchmarks. One limitation is that our method addresses a specific tractable surrogate rather than the original problem in full generality. A natural next step is therefore to derive a more direct solution of the original problem and to establish end-to-end guarantees. Acknowledgments and Disclosure of Funding Acknowledgments References [1] A. Agarwal, A. Beygelzimer, M. Dudik, J. Langford, and H. Wallach (2018) A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 60–69. External Links: Link Cited by: §E.1, §1, §5. [2] J. Angwin, J. Larson, S. Mattu, and L. Kirchner (2016) Machine Bias. ProPublica. External Links: Link Cited by: §5. [3] J. Audibert and A. Tsybakov (2007) Fast learning rates for plug-in classifiers. Annals of Statistics 35 (2), p. 608–633. Cited by: Remark 3. [4] A. Barrainkua, P. Gordaliza, J. A. Lozano, and N. Quadrianto (2025) Preserving the fairness guarantees of classifiers in changing environments: a survey. ACM Comput. Surv. 57 (6). External Links: ISSN 0360-0300, Link, Document Cited by: §1. [5] B. Becker and R. Kohavi (1996) Adult Dataset. UCI Machine Learning Repository. External Links: Document, Link Cited by: §5. [6] A. Blum, P. Okoroafor, A. Saha, and K. M. Stangl (2024) On the vulnerability of fairness constrained learning to malicious noise. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, S. Dasgupta, S. Mandt, and Y. Li (Eds.), Proceedings of Machine Learning Research, Vol. 238, p. 4096–4104. External Links: Link Cited by: §1. [7] O. Bousquet and A. Elisseeff (2002) Stability and generalization. J. Mach. Learn. Res. 2, p. 499–526. External Links: ISSN 1532-4435, Link, Document Cited by: §A.1, §2.2. [8] T. Calders, F. Kamiran, and M. Pechenizkiy (2009) Building classifiers with independency constraints. In Proceedings of the 2009 IEEE International Conference on Data Mining Workshops, ICDMW ’09, USA, p. 13–18. External Links: ISBN 9780769539027, Link, Document Cited by: §1, §1. [9] E. Celis, L. Huang, V. Keswani, and N. Vishnoi (2019) Classification with fairness constraints: a meta-algorithm with provable guarantees. In Proceedings of the conference on fairness, accountability, and transparency, p. 319–328. Cited by: §1. [10] S. Chiappa, R. Jiang, T. Stepleton, A. Pacchiano, H. Jiang, and J. Aslanides (2020) A general approach to fairness with optimal transport. In AAAI, Cited by: §1. [11] E. Chzhen, M. Hebiri, and G. Taturyan (2025) Randomized multi-class classification under system constraints: a unified approach via post-processing. External Links: 2512.14246, Link Cited by: §E.1, §1, §5. [12] C. Denis, R. Elie, M. Hebiri, and F. Hu (2024) Fairness guarantees in multi-class classification with demographic parity. Journal of Machine Learning Research 25 (130), p. 1–46. Cited by: §1. [13] L. Devroye and T. Wagner (1979) Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory 25 (5), p. 601–604. External Links: Document Cited by: §A.1. [14] L. Devroye and T. Wagner (2006) Distribution-free inequalities for the deleted and holdout error estimates. IEEE Trans. Inf. Theor. 25 (2), p. 202–207. External Links: ISSN 0018-9448, Link, Document Cited by: §A.1. [15] F. Ding, M. Hardt, J. Miller, and L. Schmidt (2021) Retiring Adult: new datasets for fair machine learning. In Advances in Neural Information Processing Systems, Vol. 34, p. 6478–6490. Cited by: §E.2, §5. [16] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel (2012) Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, p. 214–226. Cited by: §1, §2.1, §3.1. [17] J. Fermanian, D. Guégan, and X. Liu (2025) Fair learning by model averaging. Risk and Decision Analysis 11 (1-2), p. 20–49. External Links: Document Cited by: §4.1. [18] S. Gaucher, N. Schreuder, and E. Chzhen (2023) Fair learning with wasserstein barycenters for non-decomposable performance measures. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 206, p. 2436–2459. External Links: Link Cited by: §1. [19] S. Giguere, B. Metevier, Y. Brun, P. S. Thomas, S. Niekum, and B. C. da Silva (2022) Fairness guarantees under demographic shift. In International Conference on Learning Representations, Cited by: §1, §5. [20] P. Gordaliza, E. del Barrio, F. Gamboa, and J. Loubes (2019) Obtaining fairness using optimal transport theory. In ICML, p. 2357–2365. Cited by: §1. [21] M. Hardt, E. Price, and N. Srebro (2016) Equality of opportunity in supervised learning. NeurIPS 29. Cited by: §1. [22] X. Hou and L. Zhang (2024) Finite-sample and distribution-free fair classification: optimal trade-off between excess risk and fairness, and the cost of group-blindness. arXiv preprint arXiv:2410.16477. Cited by: §1. [23] Z. (. Jiang, X. Han, H. Jin, G. Wang, R. Chen, N. Zou, and X. Hu (2023) Chasing fairness under distribution shift: a model weight perturbation approach. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 63931–63944. Cited by: §1. [24] M. Kearns and D. Ron (1999) Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural Comput. 11 (6), p. 1427–1453. External Links: ISSN 0899-7667, Link, Document Cited by: §A.1, §2.2. [25] S. Kutin and P. Niyogi (2002) Almost-everywhere algorithmic stability and generalization error. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, UAI’02, San Francisco, CA, USA, p. 275–282. External Links: ISBN 1558608974 Cited by: §A.1. [26] H. Lei, A. Gohari, and F. Farnia (2024) On the inductive biases of demographic parity-based fair learning algorithms. In The 40th Conference on Uncertainty in Artificial Intelligence, Cited by: §A.2. [27] T. Leteno, M. Perrot, C. Laclau, A. Gourru, and C. Gravier (2025) Fair text classification via transferable representations. Journal of Machine Learning Research 26 (239), p. 1–47. Cited by: §1. [28] L. Oneto, M. Donini, and M. Pontil (2020) General fair empirical risk minimization. In 2020 International Joint Conference on Neural Networks (IJCNN), p. 1–8. Cited by: §1. [29] I. Redko, E. Morvant, A. Habrard, M. Sebban, and Y. Bennani (2022) A survey on domain adaptation theory: learning bounds and theoretical guarantees. External Links: 2004.11829 Cited by: §2.2. [30] W. H. Rogers and T. J. Wagner (1978) A Finite Sample Distribution-Free Performance Bound for Local Discrimination Rules. The Annals of Statistics 6 (3), p. 506 – 514. External Links: Document, Link Cited by: §A.1. [31] S. Sagawa*, P. W. Koh*, T. B. Hashimoto, and P. Liang (2020) Distributionally robust neural networks. In International Conference on Learning Representations, External Links: Link Cited by: §A.2. [32] J. A. Soloff, R. F. Barber, and R. Willett (2024) Bagging provides assumption-free stability. JMLR. External Links: Link Cited by: §A.1. [33] R. Vershynin (2018) High-dimensional probability: An introduction with applications in data science. Cambridge University Press. Cited by: Lemma 3, Lemma 4. [34] R. Xian, L. Yin, and H. Zhao (2023) Fair and optimal classification via post-processing. In International conference on machine learning, p. 37977–38012. Cited by: §1. [35] X. Zeng, E. Dobriban, and G. Cheng (2022) Fair bayes-optimal classifiers under predictive parity. Advances in Neural Information Processing Systems 35, p. 27692–27705. Cited by: §1. Organization of the Supplementary Material The Supplementary Material is organized as follows. • Appendix A provides additional literature review and further discussion. • Appendix B contains the main proofs establishing the equivalence between existing fairness notions and our stability-based definition, together with additional discussion. • Appendix C provides the explicit forms of the importance weights, the proofs of the convergence results for the constraints and the risk, along with some auxiliary lemmas needed in the analysis. • Appendix D extends the framework to Equalized Odds. We introduce the relevant notions and prove the associated equivalence result with stability. • Appendix E is dedicated to numerical experiments. We provide additional implementation details and conduct further experiments. Appendix A Discussions on related works Machine learning models are increasingly used in high-stakes decisions, such as hiring, healthcare, and criminal justice. In such settings, biases already present in the data may be inherited or even amplified by the resulting models, with potentially serious consequences for the individuals affected. Algorithmic fairness seeks to understand, quantify, and mitigate these effects. Since this question also involves philosophical and social considerations, it naturally lies at the intersection of several fields; in this paper, however, we focus on its mathematical aspect and do not aim to resolve the broader question of what fairness ought to be. A.1 Stability and learning theory Many notions of stability have been introduced in the Statistics and Machine-Learning literature to define and quantify the stability property of a statistical learning algorithm, meaning roughly that a slight change in the data (distribution) has no significant effect on the decision function produced by the algorithm. Depending on the definition of stability chosen, it is possible to use concentration results to deduce error bounds for decision rules from the stability property satisfied by the algorithm producing them, e.g., ERM with a certain cost function and/or with additive penalization, bagging. This idea is not new at all and dates back at least to the late 70’s in Statistics, refer to [30], [14], [13] and [24] for instance. The concept of stability has more recently been revisited in new forms by the machine learning community. See in particular the concept of uniform stability in [7] yielding exponential bounds and the refinements in [25]. More generally, this line of research has been adopted by many authors, too numerous to be listed in an exhaustive fashion, dealing with various approaches (e.g. bagging in [32]) and issues (clustering, latent variable analysis, ranking). A.2 Comparison with Distributionally Robust Optimization While our framework bears a resemblance to distributionally robust optimization (DRO), the two approaches differ in both structure and the guarantees they provide, with interesting connections that we now discuss. DRO reminder. Given a divergence d (here KL) and radius ε>0 >0, define the uncertainty set ε=′:KL(′∥)≤εU_ =\D :KL(D \|D)≤ \. DRO solves minsup′∈εh′[ℓ(h(),Y)]. _h _D _ E_D [ (h( X),Y)]. Our demographic shifts πD_π (Perturbation 1) satisfy π∈εD_π _ whenever ε≥KL(π∥) (D_π\|D). Since πD_π only resamples G while keeping P(,Y∣G)P( X,Y G) fixed, the KL reduces to the KL between two Bernoulli distributions: KL(π∥)=πlogπp1+(1−π)log1−π1−p1.KL(D_π\|D)=π πp_1+(1-π) 1-π1-p_1. To cover all deployment proportions π′∈[π¯,1−π¯]π ∈[ π,1- π], DRO requires a radius at least ε∗(π¯)=maxπ∈[π¯,1−π¯][πlogπp1+(1−π)log1−π1−p1], ^*( π)= _π∈[ π,1- π] [π πp_1+(1-π) 1-π1-p_1 ], which is attained at one of the endpoints π∈π¯,1−π¯π∈\ π,1- π\ by convexity of the KL divergence. Since KL(Bernoulli(π)∥Bernoulli(p1))KL(Bernoulli(π)\|Bernoulli(p_1)) is continuous and strictly positive for π≠p1π≠ p_1, we have ε∗(π¯)>0 ^*( π)>0 uniformly in p1∈[p¯,1−p¯]p_1∈[ p,1- p]; in particular, ε∗=Ω(1) ^*= (1) whenever |π¯−p1|≥c| π-p_1|≥ c for some constant c>0c>0. Table 2 illustrates representative values. Table 2: Minimum DRO radius ε∗(π¯) ^*( π) required to cover all demographic shifts π′∈[π¯,1−π¯]π ∈[ π,1- π], for varying training group proportion p1p_1 and perturbation lower bound π¯ π. p1\π¯p_1\; \; π 0.10.1 0.20.2 0.30.3 0.20.2 1.151.15 0.830.83 0.580.58 0.30.3 0.790.79 0.530.53 0.340.34 0.50.5 0.370.37 0.190.19 0.080.08 At radius ε=ε∗=Ω(1) = ^*= (1), the uncertainty set εU_ is sufficiently large to contain distributions that arbitrarily corrupt the feature mechanism P(∣G)P( X G) and the label mechanism P(Y∣G)P(Y G). Consequently, the worst-case risk over εU_ is controlled by corruptions of P(|G)P( X|G) and P(Y|G)P(Y|G) that are unrelated to demographic fairness, hence making the bound uninformative about the performance under such demographic shift. Why our framework avoids this problem. The uncertainty set εU_ contains distributions that alter P(∣G)P( X G), P(Y∣G)P(Y G), and other aspects of the data generating process entirely irrelevant to demographic fairness. Our framework instead restricts to the one-dimensional manifold π:π∈[π¯,1−π¯]\D_π:π∈[ π,1- π]\, which captures exactly the shifts of interest while preserving P(,Y∣G)P( X,Y G). This structural specificity combined with the affine form Φ(h,π)=α(h)+πγ(h) (h;π)=α(h)+πγ(h), enables simultaneous control of slope and absolute level via Π(h,t)C_ (h;t). As a result, Theorem 1 provides guarantees that converge to zero as n,m→∞n,m→∞ – something no DRO bound with radius ε=O(1) =O(1) can achieve. Connection to Group DRO and SA-DRO. Our framework is more closely related to structured DRO approaches such as Group DRO [31]. In the binary case, Group DRO minimizes maxλ∈[0,1]λD1[ℓ(⋅)]+(1−λ)D0[ℓ(⋅)] _λ∈[0,1] _D_1[ (·)]+(1-λ)E_D_0[ (·)], which is exactly the worst-case risk over our Perturbation 1 family π:π∈[0,1]\D_π:π∈[0,1]\. The two frameworks thus share the same perturbation structure for demographic parity. The differences are twofold. First, the objectives differ: Group DRO minimizes only the worst-case risk, while Stable controls the variance of Φ(h,π) (h;π) around a target level t, which we show to be formally equivalent to fairness constraints. Second, Perturbation 2, which resamples G within the positive class to capture equal opportunity, has no natural Group DRO counterpart, as Group DRO cannot vary P(G=1∣Y=1)P(G=1 Y=1) independently of P(G=1∣Y=0)P(G=1 Y=0). A closely related work is SA-DRO [26], which applies DRO directly on the marginal distribution of the sensitive attribute and adds an explicit fairness regularization term. The same structural differences with Group DRO apply here. Additionally, SA-DRO relies on soft regularization rather than a hard constraint, and therefore does not provide quantitative guarantees on the unfairness gap (h)U(h) or on the deployment gap. Appendix B Proofs for Section 3 B.1 Individual fairness Recall that the Wasserstein 11-distance between the pushforward of h()h( X)’s distribution under D and that under ()P(D) based on the cost function d_Y is inf∼,′∼()[d(h(),h(′)], _ X ,\; X P(D)E[d_Y(h( X),h( X )], where the infimum is taken over all couplings (,′)( X, X ) of the pair of distributions D and ()P(D). Proof of Proposition 1. Proposition (Proposition 1, IF and Stability). Let h:→h:X→Y be a prediction function and d:2→[0,∞)d_Y:Y^2→[0,∞) a metric on predictions. The following assertions are equivalent. 1. The predictive function h satisfies the IF property with (d,d)(d_Y,d_X)-Lipschitz constant L<∞L<∞. 2. For all ρ>0ρ>0, the predictive function h is LρLρ-fair w.r.t. to the class ρP_ρ of perturbation operators TP_T, T∈ρT _ρ, defined on the domain ℳ=δ:∈M=\ _ x:\; x∈X\ of all point masses and taking Δ(h,(,)) (h;\;(D,P)) as the Wasserstein 11-distance between the pushforward of h()h( X)’s distribution under D and that under ()P(D) based on the cost function d_Y: sup(,T)∈×ρd(h(),h(T()))⩽Lρ. _( x,T)∈X×T_ρd_Y(h( x),h(T( x))) Lρ\,. Proof. Let us show that (1⇒2)(1 2). It is easy to notice that sup(,T)∈×ρd(h(),h(T()))⩽sup(,T)∈×ρLd(,T())⩽Lρ. _( x,T)∈X×T_ρd_Y(h( x),h(T( x))) _( x,T)∈X×T_ρLd_X( x,T( x)) Lρ\,. Now let us show that (2⇒1)(2 1). First, let us fix any ,′ x, x , and denote ρ′:=d(,′)ρ :=d_X( x, x ). Let us also introduce the following transformation T→′()=′,if=,otherwise.T_ x→ x ( z)= cases x \,,&if z= x\\ z\,,&otherwise\,. cases Choosing ρ=ρ′ρ=ρ , we consider the set ρ′T_ρ . We notice that T→′∈ρ′T_ x→ x _ρ and observe that d(h(),h(′)) d_Y(h( x),h( x )) =d(h(),h(T→′())) =d_Y(h( x),h(T_ x→ x ( x))) ⩽sup∈d(h(),h(T→′())) _ x∈Xd_Y(h( x),h(T_ x→ x ( x))) ⩽supT∈ρ′sup∈d(h(),h(T()))⩽Lρ′=Ld(,′). _T _ρ _ x∈Xd_Y(h( x),h(T( x))) Lρ =Ld_X( x, x )\,. The proof is concluded. ∎ B.2 Group fairness Proof of Proposition 2. Proposition (Proposition 2, DP and Stability). Let h:→0,1h:X→\0,1\ be a (possibly randomized) prediction function, G∈0,1G∈\0,1\ be a sensitive attribute, and denote rg(h)=def ℙ(h()=1∣G=g),∀g∈0,1r_g(h) -0.75346pt def =P(h( X)=1 G=g),∀ g∈\0,1\. Let πD_π be a perturbed distribution according to Perturbation 1. We define the global positive prediction rate under πD_π as Ph(π)=def ℙπ(h()=1)P_h(π) -0.75346pt def =P_D_π(h( X)=1). Then, the following statements are equivalent: 1. h satisfies Demographic Parity: r0(h)=r1(h)r_0(h)=r_1(h). 2. Ph(π)P_h(π) is constant in π on [0,1][0,1] (i.e., the global positive rate is invariant to any resampling of G). Moreover, one has the explicit identity Ph(π)=r0(h)+π(r1(h)−r0(h)),P_h(π)=r_0(h)+π(r_1(h)-r_0(h))\,, so that supπ,π′∈[0,1]|Ph(π)−Ph(π′)|=|r1(h)−r0(h)|. _π,π ∈[0,1]|P_h(π)-P_h(π )|=|r_1(h)-r_0(h)|\,. Proof. By the law of total probability, for any π∈[0,1]π∈[0,1], Ph(π)=ℙπ(h()=1)=πr1(h)+(1−π)r0(h).P_h(π)\;=\;P_D_π(h( X)=1)\;=\;π\,r_1(h)+(1-π)\,r_0(h)\,. We note that if r0(h)=r1(h)r_0(h)=r_1(h), then Ph(π)=πr1(h)+(1−π)r1(h)=r1(h)P_h(π)=π r_1(h)+(1-π)r_1(h)=r_1(h), which does not depend on π, hence (1) ⇒ (2). Secondly, if we suppose that Ph(π)P_h(π) is constant in π, then for all π,π′∈[0,1]π,π ∈[0,1], we have πr1(h)+(1−π)r0(h)=π′r1(h)+(1−π′)r0(h),π r_1(h)+(1-π)r_0(h)\;=\;π r_1(h)+(1-π )r_0(h)\,, which can be rewritten as (π−π′)(r1(h)−r0(h))=0.(π-π )(r_1(h)-r_0(h))=0\,. Since we may choose π≠π′π≠π , it follows that r1(h)−r0(h)=0r_1(h)-r_0(h)=0, i.e., r0(h)=r1(h)r_0(h)=r_1(h), which is exactly Demographic Parity (so (2) ⇒ (1)). This proves the equivalence. ∎ Proof of Proposition 3. Proposition (Proposition 3, EO and Stability). Let h:→0,1h:X→\0,1\ be a (possibly randomized) prediction function, G∈0,1G∈\0,1\ be a sensitive attribute, and denote qg,y(h)=def ℙ(h()=1∣G=g,Y=y),∀g,y∈0,1q_g,y(h) -0.75346pt def =P(h( X)=1 G=g,Y=y),∀ g,y∈\0,1\ . Let πD_π be a perturbed distribution according to Perturbation 2. We define the true positive prediction rate under πD_π as Ph|Y=1(π)=def ℙπ(h()=1∣Y=1)P_h Y=1(π) -0.75346pt def =P_D_π(h( X)=1 Y=1). Then the following statements are equivalent: 1. h satisfies Equal Opportunity: q0,1(h)=q1,1(h)q_0,1(h)=q_1,1(h). 2. Ph|Y=1(π)P_h Y=1(π) is constant in π on [0,1][0,1] (i.e., the true positive rate is invariant to any resampling of G within positive label class). Moreover, one has the explicit identity Ph|Y=1(π)=q0,1(h)+π(q1,1(h)−q0,1(h)),P_h Y=1(π)=q_0,1(h)+π(q_1,1(h)-q_0,1(h))\,, so that supπ,π′∈[0,1]|Ph|Y=1(π)−Ph|Y=1(π′)|=|q1,1(h)−q0,1(h)|. _π,π ∈[0,1]|P_h Y=1(π)-P_h Y=1(π )|=|q_1,1(h)-q_0,1(h)|\,. Proof. Let us show that (1⇒2)(1 2). Denoting q:=q0,1(h)=q1,1(h)q:=q_0,1(h)=q_1,1(h) and applying the law of total probability, we get Ph|Y=1(π)=ℙπ(h(X)=1∣Y=1)=(1−π)q0,1(h)+πq1,1(h)=q,P_h Y=1(π)=P_D_π(h(X)=1 Y=1)=(1-π)q_0,1(h)+π q_1,1(h)=q\,, which does not depend on π. Now let us show that (2⇒1)(2 1). Assuming Ph|Y=1(π)P_h Y=1(π) is constant in π, we can state that (1−π)q0,1(h)+πq1,1(h)=(1−π′)q0,1(h)+π′q1,1(h).(1-π)q_0,1(h)+π q_1,1(h)=(1-π )q_0,1(h)+π q_1,1(h)\,. Rewriting the above as (π−π′)(q1,1(h)−q0,1(h))=0,(π-π )(q_1,1(h)-q_0,1(h))=0\,, we deduce that q1,1(h)=q0,1(h)q_1,1(h)=q_0,1(h). The proof is concluded. ∎ Appendix C Details and proofs for Section 4 C.1 Importance weights representation In this section we show that the distribution shifts under our consideration can be described by their corresponding importance-weights, defined by the Radon-Nikodym derivative wπ(,g,y)=def dπd(,g,y).w_π( x,g,y) -0.75346pt def = _π ( x,g,y)\,. Recall, that pg=ℙ(G=g)∀g∈0,1p_g=P(G=g)\,\,∀ g∈\0,1\ and ℙ(G=g∣Y=y)∀g,y∈0,1.P(G=g Y=y)\,\,∀ g,y∈\0,1\\,. For Perturbation 1, considering the factorization ℙ(,G,Y)=ℙ(G)ℙ(,Y∣G)P( X,G,Y)=P(G)P( X,Y G), and computing the Radon-Nikodym derivative, we get wπ(g)=πp1,if g=1,1−πp0,if g=0.w_π(g)= cases πp_1\,,&if g=1\,,\\ 1-πp_0\,,&if g=0\,. cases For Perturbation 2, considering the factorization ℙ(,G,Y)=ℙ(Y)ℙ(G∣Y)ℙ(∣Y,G)P( X,G,Y)=P(Y)P(G Y)P( X Y,G), and computing the Radon-Nikodym derivative, we get wπ(g,y)=πp1,1,if (g,y)=(1,1),1−πp0,1,if (g,y)=(0,1),1,if y=0.w_π(g,y)= cases πp_1,1\,,&if (g,y)=(1,1)\,,\\ 1-πp_0,1\,,&if (g,y)=(0,1)\,,\\ 1\,,&if y=0\,. cases C.2 Convergence rates First, let us recall the following two crucial lemmas. Lemma 3. [33, Hoeffding inequality] Let 1,⋯,N X_1,·s, X_N be independent random variables such that i∈[ai,bi] X_i∈[a_i,b_i] for every i. Then, for any t>0t>0, we have ℙ(∑i=1N(i−[i])⩾t)⩽exp(−2t2∑i=1N(bi−ai)2).P ( _i=1^N( X_i-E[ X_i]) t ) (- 2t^2 _i=1^N(b_i-a_i)^2 )\,. Lemma 4. [33, Bernstein inequality] Let 1,⋯,N X_1,·s, X_N be independent, mean-zero random variables satisfying |i|⩽K| X_i| K for every i. Let σ2=∑i=1Ni2σ^2= _i=1^NE X_i^2 is the variance of the sum. Then, for any t>0t>0, we have ℙ(|∑i=1Ni|⩾t)⩽2exp(−t2/2σ2+Kt/3).P ( | _i=1^N X_i | t ) 2 (- t^22σ^2+ Kt3 )\,. We now examine the different sources of error arising from the estimation of population-level quantities. C.2.1 Regression error rates Recall the following expressions ⋆=∑k∈[K]k⋆ηk,^=∑k∈[K]^kηk,^⋆=∑k∈[K]k⋆η^k,^^=∑k∈[K]^kη^k. η_ α = _k∈[K] α _kη_k\,, η_ α= _k∈[K] α_k _k\,, η_ α = _k∈[K] α _k η_k\,, η_ α= _k∈[K] α_k η_k\,. Lemma 5. Let Assumption 2 and Claims 2–3 hold. Then, for all for every ∈ΔK α∈ _K and all π∈[π¯,1−π¯]π∈[ π,1- π], it holds that |Φ(^,π)−Φ(,π)|⩽BWρN=def δN. | ( η_ α;π)- ( η_ α;π) | BW _N -0.75346pt def = _N\,. Proof. By the linearity of φh _h in h and the definition of the mixture, for any ∈ΔK α∈ _K, we have |Φ(^,π)−Φ(,π)| | ( η_ α;π)- ( η_ α;π)| =|∑k=1Kαk[Φ(η^k,π)−Φ(ηk,π)]|⩽max1⩽k⩽K|Φ(η^k,π)−Φ(ηk,π)|. = | _k=1^K _k\, [ ( η_k;π)- ( _k;π) ] | _1 k K | ( η_k;π)- ( _k;π) |\,. For each k and π, from Hölder’s inequality and Claims 2–3, we obtain |Φ(η^k,π)−Φ(ηk,π)| | ( η_k;π)- ( _k;π)| =|[wπ()φη^k−ηk()]|⩽‖wπ()‖L∞[φη^k−ηk()] =|E[w_π( Z) _ η_k- _k( Z)]| w_π( )_L^∞E[ _ η_k- _k( Z)] ⩽WB[|η^()−η()|]. WBE[| η( Z)-η( Z)|]\,. Assumption 2 concludes the proof. ∎ C.2.2 Perturbation error rates Lemma 6 (Stratified sampling). Let Π=U(π¯,1−π¯) =U( π,1- π) and ℐ1,⋯,ℐmI_1,·s,I_m be a uniform partition of [π¯,1−π¯][ π,1- π] into m intervals of length |ℐ|=(1−2π¯)m|I|= (1-2 π)m. We sample πj′∼U(ℐj)π _j U(I_j) independently for j=1,⋯,mj=1,·s,m. Let f:[π¯,1−π¯]→ℝf:[ π,1- π] be a L−L-Lipschitz function. For all aδm∈(0,1)a_ _m∈(0,1) with probability greater than 1−aδm1-a_ _m, it holds that |1m∑j=1mf(πj′)−Π[f(π)]|⩽L(1−2π¯)m3/22log(2/aδm)=def δL,m. | 1m _j=1^mf( _j )-E_ [f(π)] | L(1-2 π)m 32 2 ( 2a_ _m) -0.75346pt def = _L,m\,. Proof. Denote the stratum mean by μj=def 1|ℐ|∫ℐjf(π)π _j -0.75346pt def = 1|I| _I_jf(π)\,d\,π and the intra-stratum deviation by ξj=def f(πj′)−μj _j -0.75346pt def =f( _j )- _j. Notice, that 1m∑j=1mμj=1m∑j1|ℐ|∫ℐjf(π)π=11−2π¯∫π¯1−π¯f(π)π=Π[f(π)], 1m _j=1^m _j= 1m _j 1|I| _I_jf(π)\,d\,π= 11-2 π _ π^1- πf(π)\,d\,π=E_ [f(π)]\,, therefore 1m∑jf(πj′)−Π[f(π)]=1m∑j=1mξj 1m _jf( _j )-E_ [f(π)]= 1m _j=1^m _j. Moreover, for π∈ℐjπ _j, |f(π)−μj|⩽supπ,π′∈ℐj|f(π)−f(π′)|⩽L|ℐ||f(π)- _j| _π,π _j|f(π)-f(π )| L|I|, so |ξj|⩽L|ℐ|| _j| L|I|. Combining this with the facts that [ξj]=0E[ _j]=0 for each j, that ξj _j are independent, and applying Hoeffding’s inequality, we obtain ℙ(|1m∑jξj|>ϵ)⩽2exp(−mϵ22L2|ℐ|2)=2exp(−m3ϵ22L2(1−2π¯)2).P ( | 1m _j _j |>ε ) 2 (- m ε^22 L^2 | |^2 )=2 (- m^3 ε^22 L^2 (1-2 π)^2 )\,. Setting aδm=2exp(−m3ϵ22L2(1−2π¯)2)a_ _m=2 (- m^3 ε^22 L^2 (1-2 π)^2) and obtaining ϵ=2L(1−2π¯)m3/2log(2/aδm)ε= 2L(1-2 π)m 32 ( 2a_ _m) concludes the proof. ∎ C.2.3 Sample generalization rates Lemma 7. For all aδn∈(0,1)a_ _n∈(0,1) with probability greater than 1−aδn1-a_ _n and conditionally on ND^N, with probability greater than 1−aδn1-a_ _n it holds that maxk∈[K],j∈[m]|Φ^n(η^k,πj′)−Φ(η^k,πj′)|⩽2W2log(2Km/aδn)n+2Wlog(2Km/aδn)3n=def δn. _k∈[K],j∈[m] | _n( η_k; _j )- ( η_k; _j ) | 2W^2 ( 2Kma_ _n)n+ 2W ( 2Kma_ _n)3n -0.75346pt def = _n\,. Moreover, for all ∈ΔK α∈ _K and j∈[m]j∈[m], it holds that |Φ^n(^,πj′)−Φ(^,πj′)|⩽δn. | _n( η_ α; _j )- ( η_ α; _j ) | _n\,. Proof. Let us fix k∈[K]k∈[K] and j∈[m]j∈[m]. The function η^k η_k is fixed conditionally on sample ND^N. Let us define ξi=def wπj′(i)φη^k(i) _i -0.75346pt def =w_π _j( Z_i) _ η_k( Z_i), for i∼i.i.d. n Z_i -0.45206pt i.i.d.~ D^n. We have [ξi]=Φ(η^k,πj′)E[ _i]= ( η_k; _j ), |ξi|⩽W| _i| W, |ξi−[ξi]|⩽W| _i-E[ _i]| W and Var(ξi)⩽[ξi2]⩽W2 ( _i) [ _i^2] W^2. Applying Bernstein’s inequality, for any ϵ>0ε>0 it holds that ℙn(|1n∑iξi|>ϵ|N)⩽2exp(−nϵ22W2+23Wϵ).P_D^n ( | 1n _i _i |>ε\,|\,D^N ) 2 (- nε^22W^2 + 23Wε )\,. Setting aδnKm=2exp(−nϵ22W2+23Wϵ) a_ _nKm=2 (- nε^22W^2 + 23Wε), obtaining ϵ=2W2log(2Km/aδn)n+2Wlog(2Km/aδn)3nε= 2W^2 ( 2Kma_ _n)n+ 2W ( 2Kma_ _n)3n, and applying union bound over all pairings(k,j)∈[K]×[m](k,j)∈[K]×[m] concludes the proof of the first inequality. Moreover, using the triangle inequality and the fact that αk⩾0 _k 0, ∑kαk=1 _k _k=1, we obtain |Φ^n(^,πj′)−Φ(^,πj′)| | _n( η_ α; _j )- ( η_ α; _j ) | =|∑k=1Kαk(Φ^n(η^k,πj′)−Φ(η^k,πj′))| = | _k=1^K _k( _n( η_k;\, _j )- ( η_k; _j )) | ⩽∑k=1Kαk|Φ^n(η^k,πj′)−Φ(η^k,πj′)| _k=1^K _k | _n( η_k; _j )- ( η_k; _j ) | ⩽maxk|Φ^n(η^k,πj′)−Φ(η^k,πj′)|⩽δn. _k| _n( η_k; _j )- ( η_k; _j )| _n. The proof is concluded. ∎ C.2.4 Final constraint rates Formal version and the proof of the first statement of Theorem 1. Theorem 2 (Constraint rates). Let α be a simplex vector, s.t. ^n,m(^^,t)⩽δ C_n,m( η_ α;t) δ. For all aδm,aδn∈(0,1)a_ _m,a_ _n∈(0,1) and conditionally on ND^N, with probability greater than 1−aδm−aδn1-a_ _m-a_ _n it holds that Π(^^,t)⩽(δ+δn)2+δm,C_ ( η_ α;t) ( δ+ _n )^2+ _m\,, where δm=def 2(2−π¯)(1−2π¯)m3/22log(4/aδm)andδn=2W2log(2Km/aδn)n+2Wlog(2Km/aδn)3n. _m -0.75346pt def = 2(2- π)(1-2 π)m 32 2 ( 4a_ _m) _n= 2W^2 ( 2Kma_ _n)n+ 2W ( 2Kma_ _n)3n\,. Proof. Let us fix j∈[m]j∈[m]. By the triangle inequality, and Lemma 7, we have |Φ(^^,πj′)−t|⩽|Φ^n(^^,πj′)−t|+|Φ^n(^^,πj′)−Φ(^^,πj′)|⩽|Φ^n(^^,πj′)−t|+δn. | ( η_ α; _j )-t| | _n( η_ α; _j )-t|+| _n( η_ α; _j )- ( η_ α; _j )| | _n( η_ α; _j )-t|+ _n\,. Squaring both sides of the above inequality, we get (Φ(^^,πj′)−t)2⩽(|Φ^n(^^,πj′)−t|+δn)2.( ( η_ α; _j )-t)^2 (| _n( η_ α; _j )-t|+ _n)^2\,. Averaging over j=1,⋯,mj=1,·s,m yields 1m∑j=1m(Φ(^^,πj′)−t)2 1m _j=1^m( ( η_ α; _j )-t)^2 ⩽1m∑j(|Φ^n(^^,πj′)−t|+δn)2 1m _j(| _n( η_ α; _j )-t|+ _n)^2 =^n,m(^^,t)+2δn1m∑j|Φ^n(^^,πj′)−t|+δn2. = C_n,m( η_ α;t)+2 _n 1m _j| _n( η_ α; _j )-t|+ _n^2\,. By Cauchy–Schwarz inequality, and the fact that ^n,m(^^,t)⩽δ C_n,m( η_ α;t) δ, we have 1m∑j|Φ^n(^^,πj′)−t|⩽1m∑j(Φ^n(^^,πj′)−t)2=^n,m(^^,t)⩽δ. 1m _j| _n( η_ α; _j )-t| 1m _j( _n( η_ α; _j )-t)^2= C_n,m( η_ α;t) δ\,. Combining the inequalities above we get 1m∑j=1m(Φ(^^,πj′)−t)2⩽(δ+δn)2. 1m _j=1^m( ( η_ α; _j )-t)^2 ( δ+ _n)^2\,. (7) For any ∈ΔK α∈ _K, by linearity of α(⋅)α(·)22 2 Do not confuse the functional α(⋅)α(·) from the decomposition of Φ(h,π) (h;π) with the simplex vector =(α1,⋯,αK) α=( _1,·s, _K). and γ(⋅)γ(·), that follows from linearity of Φ(h,π) (h;π) in Claim 1, and denoting α=def ∑k=1Kαkα(η^k) _ α -0.75346pt def = _k=1^K _kα( η_k) and γ=def ∑k=1Kαkγ(η^k) _ α -0.75346pt def = _k=1^K _kγ( η_k), we get (Φ(^,π)−t)2=(α−t)2+2(α−t)γπ+γ2π2.( ( η_ α;π)-t)^2=( _ α-t)^2+2( _ α-t) _ απ+ _ α^2π^2\,. Averaging over π1′,⋯,πm′π _1,·s,π _m and subtracting from Π(^,t)C_ ( η_ α;t), we get Π(^,t) C_ ( η_ α;t) −1m∑j=1m(Φ(^;πj′)−t)2 - 1m _j=1^m( ( η_ α; _j )-t)^2 =2(α−t)γΠ[π]−1m∑j=1mπj′+γ2Π[π2]−1m∑j=1m(πj′)2. =2( _ α-t) _ α \E_ [π]- 1m _j=1^mπ _j \+ _ α^2 \E_ [π^2]- 1m _j=1^m(π _j)^2 \\,. Now, let us notice that the maps π↦π π and π↦π2π π^2 are respectively 11–Lipschitz and 2(1−π¯)2(1- π)–Lipschitz on [π¯,1−π¯][ π,1- π]. Applying Lemma 6 with a union bound, and recalling that α∈[0,1] _ α∈[0,1] and γ∈[−1,1] _ α∈[-1,1], with probability at least 1−aδm1-a_ _m and uniformly in ∈ΔK α∈ _K, we obtain Π(^,t)⩽1m∑j(Φ(^,πj′)−t)2+2(2−π¯)(1−2π¯)m3/22log(4/aδm).C_ ( η_ α;t) 1m _j( ( η_ α; _j )-t)^2+ 2(2- π)(1-2 π)m 32 2 ( 4a_ _m)\,. Finally, specializing at = α= α and applying (7), we get Π(^^,t)⩽1m∑j(Φ(^^,πj′)−t)2+δm⩽(δ+δn)2+δm.C_ ( η_ α;t) 1m _j( ( η_ α; _j )-t)^2+ _m ( δ+ _n)^2+ _m\,. The proof is concluded. ∎ The second statement of Theorem 1 is stated below as a corollary and follows directly from Theorem 2. Corollary 1 (Unfairness rates). Under the conditions of Theorem 2, it holds that (^^)⩽(δ+δn)2+δmVarΠ(π)⩽δ+δn+δmVarΠ(π).U( η_ α) ( δ+ _n)^2+ _m _ (π) δ+ _n+ _m _ (π)\,. Thus, if we set δ=δ02VarΠ(π)δ= _0^2 _ (π), then we will have (^^)−δ0⩽~(1n1/2+1m3/4).U( η_ α)- _0 O ( 1n 12+ 1m 34 )\,. Formal version and the proof of the third statement of Theorem 1. Theorem 3 (Uniform Deployment Guarantee). Let ^ η_ α be any feasible solution of ( P SOCP ) with threshold δ and target t∈[0,1]t∈[0,1]. Under the conditions of Theorem 2, For all aδm,aδn∈(0,1)a_ _m,a_ _n∈(0,1) and conditionally on ND^N, with probability greater than 1−aδm−aδn1-a_ _m-a_ _n over (Dn,Πm)(D^n, ^m), the following holds simultaneously for all π′∈[π¯,1−π¯]π ∈[ π,1- π] |Φ(^^,π′)−t|⩽(δ+δn+δm)⋅(1+|π′−μΠ|VarΠ(π)). | ( η_ α;π )-t | ( δ+ _n+ _m)· (1+ |π - _ | _ (π) )\,. Proof. It follows from (6) and Theorem 2 that (π∼Π[Φ(^^,π)]−t)2⩽(δ+δn)2+δm.(E_π [ ( η_ α;π)]-t)^2 ( δ+ _n)^2+ _m\,. Taking the square root, we obtain |π∼Π[Φ(^^,π)]−t|⩽δ+δn+δm.|E_π [ ( η_ α;π)]-t| δ+ _n+ _m\,. For a fixed π′π , we have Φ(^^,π′)−t=[Φ(^^,π′)−Π[Φ(^^,π)]]⏟fluctuation term+[Π[Φ(^^,π)]−t]⏟bias term. ( η_ α;π )-t= [ ( η_ α;π )-E_ [ ( η_ α;π)] ]_fluctuation term+ [E_ [ ( η_ α;π)]-t ]_bias term. Let us denote by μΠ=def Π[π] _ -0.75346pt def =E_ [π]. For the fluctuation term, by the linearity of Φ(^^,π) ( η_ α;π) and the identity Π[α(h)+πγ(h)]=α(h)+μΠγ(h)E_ [α(h)+πγ(h)]=α(h)+ _ γ(h), we have Φ(^^,π′)−Π[Φ(^^,π)] ( η_ α;π )-E_ [ ( η_ α;π)] =(α(^^)+π′γ(^^))−(α(^^)+μΠγ(^^)) = (α( η_ α)+π γ( η_ α) )- (α( η_ α)+ _ γ( η_ α) ) =(π′−μΠ)γ(^^). =(π - _ )γ( η_ α)\,. Therefore, Φ(^^,π′)−t=(π′−μΠ)γ(^^)+[Π[Φ(^^,π)]−t]. ( η_ α;π )-t=(π - _ )γ( η_ α)+ [E_ [ ( η_ α;π)]-t ]\,. (8) Applying the triangle inequality to (8) and substituting bounds from Theorem 2, |Φ(^^,π′)−t| | ( η_ α;π )-t | ⩽|π′−μΠ|⋅|γ(^^)|+|Π[Φ(^^,π)]−t| |π - _ |·|γ( η_ α)|+ |E_ [ ( η_ α;π)]-t | ⩽|π′−μΠ|⋅(δ+δn+δm)VarΠ(π)+(δ+δn+δm) |π - _ |· ( δ+ _n+ _m) _ (π)+( δ+ _n+ _m) =(1+|π′−μΠ|VarΠ(π))⋅(δ+δn+δm). = (1+ |π - _ | _ (π) )·( δ+ _n+ _m)\,. Since this bound holds for all π′∈[0,1]π ∈[0,1] simultaneously, the proof is concluded. ∎ Let us also prove the following lemma, that we will use in later analysis. Lemma 8 (Reverse feasibility). Under the conditions of Lemma 5, Lemma 6 and Lemma 7, let δ>δn+δN δ> _n+ _N and (δ−δn−δN)2>δm( δ- _n- _N)^2> _m. We define the tightened level as δ~=def (δ−δn−δN)2−δm. δ -0.75346pt def =( δ- _n- _N)^2- _m\,. If ∈ΔK α∈ _K satisfies Π(η,t)⩽δ~C_ ( _ α;t) δ, then ^n,m(η^,t)⩽δ C_n,m( η_ α;t) δ. Proof. Fix any j∈[m]j∈[m]. By the triangle inequality, |Φ^n(^,πj′)−t| | _n( η_ α;π _j)-t | ⩽|Φ^n(^,πj′)−Φ(^,πj′)|+|Φ(^,πj′)−Φ(,πj′)|+|Φ(,πj′)−t| | _n( η_ α;π _j)- ( η_ α;π _j) |+ | ( η_ α;π _j)- ( η_ α;π _j) |+ | ( η_ α;π _j)-t | ⩽δn+δN+|Φ(,πj′)−t|. _n+ _N+ | ( η_ α;π _j)-t |\,. Squaring and averaging over j=1,…,mj=1,…,m gives ^n,m(^,t)=1m∑j=1m(Φ^n(^,πj′)−t)2⩽1m∑j=1m(|Φ(,πj′)−t|+δn+δN)2. C_n,m( η_ α;t)= 1m _j=1^m ( _n( η_ α;π _j)-t )^2 1m _j=1^m ( | ( η_ α;π _j)-t |+ _n+ _N )^2\,. (9) Let us define g(π)=def (Φ(,π)−t)2g(π) -0.75346pt def =( ( η_ α;π)-t)^2. Since the map π↦Φ(,π)π ( η_ α;π)is affine, g is a polynomial of degree two in π, and in particular Lipschitz on [π¯,1−π¯][ π,1- π] with constant at most 2W22W^2, applying Lemma 6, we obtain 1m∑j=1mg(πj′)⩽Π[g(π)]+δm=Π(,t)+δm⩽δ~+δm. 1m _j=1^mg(π _j) _ [g(π)]+ _m=C_ ( η_ α;t)+ _m δ+ _m\,. Applying the Cauchy–Schwarz inequality, we get 1m∑j=1m|Φ(,πj′)−t|⩽1m∑j=1mg(πj′)⩽δ~+δm. 1m _j=1^m | ( η_ α;π _j)-t | 1m _j=1^mg(π _j) δ+ _m\,. Expanding the right-hand-side of (9), we obtain ^n,m(^,t) C_n,m( η_ α;t) ⩽1m∑jg(πj′)+2(δn+δN)⋅1m∑j|Φ(η;πj′)−t|+(δn+δN)2 1m _jg(π _j)+2( _n+ _N)· 1m _j | ( _ α;π _j)-t |+( _n+ _N)^2 ⩽(δ~+δm)+2(δn+δN)δ~+δm+(δn+δN)2 ( δ+ _m)+2( _n+ _N) δ+ _m+( _n+ _N)^2 ⩽(δ~+δm+δn+δN)2. ( δ+ _m+ _n+ _N )^2\,. Substituting δ~=(δ−δn−δN)2−δm δ=( δ- _n- _N)^2- _m gives δ~+δm=(δ−δn−δN)2=δ−δn−δN, δ+ _m= ( δ- _n- _N)^2= δ- _n- _N\,, and finally we get ^n,m(^,t)⩽((δ−δn−δN)+δn+δN)2=δ. C_n,m( η_ α;t) (( δ- _n- _N)+ _n+ _N )^2=δ\,. The proof is concluded. ∎ C.2.5 Risk rates For prediction functions h1,⋯,hKh_1,·s,h_K, let us recall the notation of population and empirical linearized risks ℛ¯(h)=def ∑k=1Kαkℛ(hk),ℛ¯^n(h)=def ∑k=1Kαkℛ^n(hk). R(h_ α) -0.75346pt def = _k=1^K _kR(h_k)\,, R_n(h_ α) -0.75346pt def = _k=1^K _k R_n(h_k)\,. Let us also define ν¯(δ′)=def min∈ΔKℛ¯():(,t)⩽δ′, for δ′>0. ν(δ ) -0.75346pt def = _ α∈ _K \ R( η_ α)\,:\,\ C( η_ α;t) δ \\,, for δ >0\,. The population-optimal mixture at level δ is ⋆=def argmin∈ΔKR¯():CΠ(,t)⩽δ α -0.75346pt def = _ α∈ _K\ R( η_ α):C_ ( η_ α;t) δ\, so that ν¯(δ)=R¯(⋆) ν(δ)= R( η_ α ). Lemma 9 (Value continuity). Under Assumption 3, for every 0⩽γ⩽δ−(0,t),0 γ δ-C( η_ α^0;t)\,, it holds that 0⩽ν¯(δ−γ)−ν¯(δ)⩽γC,whereC=def ℛ¯(0)−ν¯(δ)δ−(0,t).0 ν(δ-γ)- ν(δ) γ C\,, C -0.75346pt def = R( η_ α^0)- ν(δ)δ-C( η_ α^0;t)\,. Proof. Let δ⋆ α_δ be a minimizer in the definition of ν¯(δ) ν(δ). Fix γ∈[0,δ−(0,t)]γ∈[0,δ-C( η_ α^0;t)] and set λγ=def γδ−(0,t)∈[0,1],γ=def (1−λγ)δ⋆+λγ0. _γ -0.75346pt def = γδ-C( η_ α^0;t)∈[0,1]\,, α_γ -0.75346pt def =(1- _γ) α_δ + _γ α^0\,. The simplex ΔK _K is convex, hence γ∈ΔK α_γ∈ _K. Moreover, ↦Φ(,π) α ( η_ α;π) is affine for every fixed π, hence ↦(Φ(,π)−t)2 α ( ( η_ α;π)-t)^2 is convex, and taking the expectation over π∼Ππ , again, preserves the convexity. Therefore, it holds that (γ,t)⩽(1−λγ)(δ⋆,t)+λγ(0,t)⩽(1−λγ)δ+λγ(0,t)=δ−γ.C( η_ α_γ;t) (1- _γ)C( η_ α_δ ;t)+ _γC( η_ α^0;t) (1- _γ)δ+ _γC( η_ α^0;t)=δ-γ\,. Hence, γ α_γ is feasible for level δ−γδ-γ, and thus ν¯(δ−γ)⩽ℛ¯(γ). ν(δ-γ) R( η_ α_γ)\,. Using the linearity of ℛ¯ R, we obtain ℛ¯(γ)=(1−λγ)ℛ¯(δ⋆)+λγℛ¯(0)=ν¯(δ)+λγ(ℛ¯(0)−ν¯(δ)). R( η_ α_γ)=(1- _γ) R( η_ α_δ )+ _γ R( η_ α^0)= ν(δ)+ _γ( R( η_ α^0)- ν(δ))\,. Combining the last two, we obtain ν¯(δ−γ)−ν¯(δ)⩽γℛ¯(0)−ν¯(δ)δ−(0,t). ν(δ-γ)- ν(δ) γ R( η_ α^0)- ν(δ)δ-C( η_ α^0;t)\,. We conclude the proof by noticing that ν¯(δ)⩽ν¯(δ−γ) ν(δ) ν(δ-γ) due to monotonicity of the feasible sets. ∎ Lemma 10. Under Assumption 2 and Assumption 1, for every α∈ΔKα∈ _K, |ℛ¯(^)−ℛ¯()|⩽LρN. | R( η_ α)- R( η_ α) | L _N\,. Proof. For each k∈[K]k∈[K], by the Lipschitz property of ℓ in its first argument, |ℛ(η^k)−ℛ(ηk)|=|[ℓ(η^k(),Y)−ℓ(ηk(),Y)]|⩽L|η^k()−ηk()|. |R( η_k)-R( _k) |= |E[ ( η_k( X),Y)- ( _k( X),Y)] | LE| η_k( X)- _k( X)|\,. Since ∈ΔK α∈ _K, |ℛ¯(^)−ℛ¯()| | R( η_ α)- R( η_ α) | =|∑k=1Kαk(ℛ(η^k)−ℛ(ηk))|⩽∑k=1Kαk|ℛ(η^k)−ℛ(ηk)| = | _k=1^K _k(R( η_k)-R( _k)) | _k=1^K _k |R( η_k)-R( _k) | ⩽Lmaxk|η^k()−ηk()|⩽LρN. L _kE| η_k( X)- _k( X)| L _N\,. The proof is concluded. ∎ Lemma 11 (Uniform linearized risk deviation). For every aδR∈(0,1)a_ _R∈(0,1), with probability at least 1−aδR1-a_ _R, sup∈ΔK|ℛ¯()−ℛ¯^n()|⩽log(2K/aδR)2n=def δn(R). _ α∈ _K | R( η_ α)- R_n( η_ α) | ( 2Ka_ _R)2n -0.75346pt def = _n(R)\,. Moreover, the statement is identical for estimated mixture η_ α. Proof. For each fixed k∈[K]k∈[K], the random variables ℓ(hk(Xi),Yi) (h_k(X_i),Y_i) are i.i.d. and take values in [0,1][0,1]. Hoeffding’s inequality yields ℙn(|ℛ(ηk)−ℛ^n(ηk)|>ϵ|N)⩽2exp(−2nϵ2).P_D^n ( |R( _k)- R_n( _k) |>ε\,|\,D^N ) 2 (-2nε^2)\,. Taking the union bound over k∈[K]k∈[K] gives ℙn(maxk∈[K]|ℛ(ηk)−ℛ^n(ηk)|>ϵ|N)⩽2Kexp(−2nϵ2).P_D^n ( _k∈[K] |R( _k)- R_n( _k) |>ε\,|\,D^N ) 2K (-2nε^2)\,. Choosing ϵ=log(2K/aδR)2nε= ( 2Ka_ _R)2n yields, with probability at least 1−aδR1-a_ _R and conditionally on ND^N, maxk∈[K]|ℛ(ηk)−ℛ^n(ηk)|⩽δn(R). _k∈[K] |R( _k)- R_n( _k) | _n(R)\,. Finally, for any ∈ΔK α∈ _K, |ℛ¯()−ℛ¯^n()|=|∑k=1Kαk(ℛ(ηk)−ℛ^n(ηk))|⩽∑k=1Kαk|ℛ(ηk)−ℛ^n(ηk)|⩽δn(R). | R( η_ α)- R_n( η_ α) |= | _k=1^K _k (R( _k)- R_n( _k) ) | _k=1^K _k |R( _k)- R_n( _k) | _n(R)\,. The proof is concluded. ∎ Formal version and the proof of the fourth statement of Theorem 1. Theorem 4 (Risk rates). Let α be a solution of ( P SOCP ). Suppose Assumptions 2–5 hold, and n,m,Nn,m,N are large enough so that δ>δn+δN δ> _n+ _N and (δ−δn−δN)2>δm( δ- _n- _N)^2> _m. Then, for all aδn,aδm,aδn(R)∈(0,1)a_ _n,a_ _m,a_ _n(R)∈(0,1), conditionally on DND^N, with probability at least 1−aδn−aδm−aδn(R)1-a_ _n-a_ _m-a_ _n(R) over (Dn,Πm)(D^n, ^m), it holds that ℛ¯(^^)−ℛ¯(⋆)⩽L⋅ρN+C⋅(2δ(δn+δN)+(δn+δN)2+δm)+2δn(R), R( η_ α)- R( η_ α ) L· _N+C·(2 δ( _n+ _N)+( _n+ _N)^2+ _m)+2 _n(R)\,, where δn _n and δm _m are from Theorem 2, and δn(R)=log(2K/aδR)2n,C=ℛ¯(0)−ν¯(δ)δ−(0,t). _n(R)= ( 2Ka_ _R)2n\,, C= R( η_ α^0)- ν(δ)δ-C( η_ α^0;t)\,. Proof. Let δ~=(δ−δn−δN)2−δm>0 δ=( δ- _n- _N)^2- _m>0 be the tightened threshold from the reverse feasibility (Lemma 8). When n,m,Nn,m,N are “large enough”, then δn,δm,δN _n, _m, _N are “sufficiently” small, so it holds that Π(0,t)<δ~C_ ( η_ α_0;t)< δ, that is the feasible set at the level δ~ δ is non-empty. Let us denote by ~ α the minimizer of ν¯(δ~) ν( δ). We have Π(~,t)C_ ( η_ α;t) and ν¯(δ~)=ℛ¯(~) ν( δ)= R( η_ α). From Lemma 8, we have that n,m(^~)⩽δC_n,m( η_ α) δ. Since α is the empirical minimizer of ( P SOCP ), and ~ α is empirically feasible, we have ℛ¯^n(^^)⩽ℛ¯^n(^~) R_n( η_ α) R_n( η_ α). Combining this, with Lemma 11, we get ℛ¯(^^)⩽ℛ¯^n(^^)+δn(R)⩽ℛ¯^n(^~)+δn(R)⩽ℛ¯(^~)+2δn(R). R( η_ α) R_n( η_ α)+ _n(R) R_n( η_ α)+ _n(R) R( η_ α)+2 _n(R)\,. Next, we apply Lemma 10 and obtain ℛ¯(^~)⩽ℛ¯(~)+LρN=ν¯(δ~)+LρN. R( η_ α) R( η_ α)+L _N= ν( δ)+L _N\,. Finally, we are in position to apply value continuity (Lemma 9). Setting γ γ =δ−δ~=δ−(δ−δn−δN)2+δm =δ- δ=δ-( δ- _n- _N)^2+ _m =2δ(δn+δN)+(δn+δN)2+δm, =2 δ( _n+ _N)+( _n+ _N)^2+ _m\,, we get ν¯(δ~)=ν¯(δ−γ)⩽ν¯(δ)+γC. ν( δ)= ν(δ-γ) ν(δ)+γ C\,. Combining everything above, we finally obtain ℛ¯(^^)⩽ℛ¯(⋆)+γC+LρN+2δn(R). R( η_ α) R( η_ α )+γ C+L _N+2 _n(R). The proof is concluded. ∎ Appendix D Extension to Equalized Odds Definition 8 (Equalized Odds). A classifier h satisfies the EOdds property if it achieves equal true positive rates and equal false positive rates across groups: Pr(h()=1∣Y=y,G=0)=Pr(h()=1∣Y=y,G=1),∀y∈0,1. (h( )=1 Y=y, G=0)\;=\; (h( )=1 Y=y, G=1)\,, ∀ y∈\0,1\\,. To connect EOdds to stability, we consider the following perturbation. Perturbation 3. The class G|YP^G Y_ π, with =(π0,π1) π=( _0, _1), is composed of all operators :ℳ1()→ℳ1()P:M_1(Z) _1(Z) such that, for all distribution ∈ℳ1()D _1(Z), 1) X’s conditional distribution given (Y,G)(Y,G) and Y’s distribution are the same under D and under ()P(D), 2) ℙ()(G=1∣Y=y)=πy,∀y∈0,1P_P(D)(G=1 Y=y)= _y\,,∀ y∈\0,1\. Proposition 4 (EOdds and Stability). Let h:→0,1h:X→\0,1\ be a (possibly randomized) prediction function, G∈0,1G∈\0,1\ be a sensitive attribute, and denote qg,y(h)=def ℙ(h()=1∣G=g,Y=y),∀g,y∈0,1q_g,y(h) -0.75346pt def =P(h( X)=1 G=g,Y=y),∀ g,y∈\0,1\ . Let D_ π be a perturbed distribution according to Perturbation 3. We define the true positive and false positive prediction rates under D_ π respectively as Ph|Y=1()=def ℙ(h()=1∣Y=1)P_h Y=1( π) -0.75346pt def =P_D_ π(h( X)=1 Y=1) and Ph|Y=0()=def ℙ(h()=1∣Y=0)P_h Y=0( π) -0.75346pt def =P_D_ π(h( X)=1 Y=0). Then, the following statements are equivalent: 1. h satisfies Equalized Odds: q0,y(h)=q1,y(h),∀y∈0,1q_0,y(h)=q_1,y(h)\,,∀ y∈\0,1\. 2. Ph|Y=y()P_h Y=y( π) is constant in πy _y on [0,1],∀y∈0,1[0,1]\,,∀ y∈\0,1\ (i.e., the true positive and false negative rates are invariant to any intra-class resampling of G). Moreover, one has the explicit identity Ph|Y=y()=q0,y(h)+πy(q1,y(h)−q0,y(h)),∀y∈0,1,P_h Y=y( π)=q_0,y(h)+ _y(q_1,y(h)-q_0,y(h))\,, ∀ y∈\0,1\\,, so that supπy,πy′∈[0,1]|Ph|Y=y(πy)−Ph|Y=y(πy′)|=|q1,y(h)−q0,y(h)|,∀y∈0,1. _ _y, _y ∈[0,1]|P_h Y=y( _y)-P_h Y=y( _y )|=|q_1,y(h)-q_0,y(h)|\,, ∀ y∈\0,1\\,. Proof. Let us show that (1⇒2)(1 2). Denoting qy:=q0,y(h)=q1,y(h),∀y∈0,1q_y:=q_0,y(h)=q_1,y(h),∀ y∈\0,1\, and applying the law of total probability, we get Ph|Y=y()=ℙ(h()=1∣Y=y)=(1−πy)q0,y(h)+πyq1,y(h)=qy,∀y∈0,1,P_h Y=y( π)=P_D_ π(h( X)=1 Y=y)=(1- _y)q_0,y(h)+ _yq_1,y(h)=q_y\,,∀ y∈\0,1\\,, which does not depend on πy _y. Now let us show that (2⇒1)(2 1). Assuming Ph|Y=y()P_h Y=y( π) is constant in πy,∀y∈0,1 _y\,,∀ y∈\0,1\, we can state that for y∈0,1y∈\0,1\,it holds that (1−πy)q0,y(h)+πyq1,y(h)=(1−πy′)q0,y(h)+πy′q1,y(h)∀y∈0,1.(1- _y)q_0,y(h)+ _yq_1,y(h)=(1- _y )q_0,y(h)+ _y q_1,y(h) ∀ y∈\0,1\\,. Rewriting the above as (πy−πy′)(q1,y(h)−q0,1(h))=0,( _y- _y )(q_1,y(h)-q_0,1(h))=0\,, we deduce that q0,y(h)=q1,y(h),∀y∈0,1q_0,y(h)=q_1,y(h)\,,∀ y∈\0,1\. The proof is concluded. ∎ Importance-weights representation Under Perturbation 3, considering the factorization ℙ(,G,Y)=ℙ(Y)ℙ(G∣Y)ℙ(∣Y,G)P( X,G,Y)=P(Y)P(G Y)P( X Y,G), and computing the Radon-Nikodym derivative, we get w(g,y)=π1p1,1,if (g,y)=(1,1),1−π1p0,1,if (g,y)=(0,1),π0p1,0,if (g,y)=(1,0),1−π0p0,0,if (g,y)=(0,0).w_ π(g,y)= cases _1p_1,1\,,&if (g,y)=(1,1)\,,\\ 1- _1p_0,1\,,&if (g,y)=(0,1)\,,\\ _0p_1,0\,,&if (g,y)=(1,0)\,,\\ 1- _0p_0,0\,,&if (g,y)=(0,0)\,. cases Appendix E Experiments: additional details and results All experiments are run on an Apple M2, 16 GB RAM. The average running times per seed are reported in Table 3. In all experiments, we operate in the unaware setting: the sensitive attribute G is not available at prediction time. Results are reported as mean ± standard deviation over 20 random seeds. Algorithm 1 Pseudo-Algorithm 0: Samples ii=1n∼i.i.d. \ Z_i\_i=1^n -0.45206pt i.i.d.~ D, perturbation parameter law Π , target t, threshold δ. 1: Sample π1,⋯,πK∼i.i.d. Π _1,·s, _K -0.45206pt i.i.d.~ 2: for k=1k=1 to K do 3: Train η^k η_k by weighted ERM on i\ Z_i\ with weights wπk(i)w_ _k( Z_i). 4: end for 5: Sample π1′,…,πm′∼i.i.d. Ππ _1,…,π _m -0.45206pt i.i.d.~ . 6: Build A, with A^j,k=Φ^n(η^k,πj′)=1n∑i=1nwπj′(Zi)φη^k(Zi) A_j,k= _n( η_k,π _j)= 1n _i=1^nw_π _j(Z_i) _ η_k(Z_i); and rk=ℛ^n(η^k)r_k= R_n( η_k) 7: Solve the SOCP ( P SOCP ) to obtain α. 8: Set ^^=∑k=1Kα^kη^k η_ α= _k=1^K α_k η_k. E.1 Evaluation protocol 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, α=0.25α=0.25). NANA stands for Not Applicable. ERM + constraint STABLE (ours) PostProc Shifty DP EO DP EO DP EO DP EO Adult 3.5±0.393.5±0.39 5.06±1.355.06±1.35 4.98±0.564.98±0.56 6.41±0.66.41±0.6 1.6±0.11.6±0.1 1.85±0.071.85±0.07 284.34±314.12284.34±314.12 269.8±165.8269.8±165.8 COMPAS 1.01±0.181.01± 0.18 1.01±0.271.01± 0.27 1.66±0.521.66± 0.52 1.69±0.271.69± 0.27 1.12±0.071.12± 0.07 1.25±0.081.25± 0.08 11.67±4.911.67± 4.9 16.98±6.5616.98± 6.56 ACS 126.8±12126.8± 12 101.2±15.8101.2± 15.8 151.2±11.1151.2± 11.1 149.9±10.3149.9± 10.3 8.38±0.678.38± 0.67 17.0±1.617.0± 1.6 56.9±11.656.9± 11.6 50.2±9.850.2± 9.8 Simulating deployment shift. For the Adult Income and COMPAS datasets we simulate the deployment under demographic shift without retraining. Given a fixed trained model h and a test set (xi,gi,yi)\(x_i,g_i,y_i)\, the functional Φ(h,π′) (h;π ) is estimated via importance weighting: each observation receives weight wπ′(gi)=π′p1gi=1+1−π′p0gi=0w_π (g_i)= π p_11\g_i=1\+ 1-π p_01\g_i=0\, where pg=ℙ^(G=g)p_g= P(G=g) is estimated on the test set. This reweights the empirical distribution to match a target group proportion π′π without requiring a new dataset, and corresponds exactly to Perturbation 1 of Section 3. The deploy gap is then supπ′∈0,1|Φ(h,π′)−t| _π ∈\0,1\| (h;π )-t|, evaluated at the two extremes. Hyperparameter selection. STABLE learns a convex mixture of K weighted-ERM predictors, each being an ℓ2 _2-regularised logistic regression (regularisation C=1C=1, lbfgs solver). The mixture is optimised via a SOCP evaluated on m stratified perturbation points drawn from Π . We fix K=30K=30 (number of mixture components) and m=60m=60 (number of SOCP constraint evaluation points) across all experiments, as preliminary runs showed no sensitivity beyond these values. The two hyperparameters subject to selection are π¯ π, the lower bound of the perturbation interval Π=[π¯, 1−π¯] =[ π,\,1- π], and δ, the SOCP feasibility threshold controlling the trade-off between fairness and accuracy. For each dataset and constraint, δ and π¯ π are selected via grid search on a fixed held-out validation split (seed 0 for Adult and COMPAS, five validation states for ACS Income), optimising the deploy gap max(|Φ(h,0)−t|,|Φ(h,1)−t|) (| (h;0)-t|,\,| (h;1)-t|). The search grids are: π¯∈0.02, 0.05, 0.10, 0.15, 0.20, 0.30, 0.40,δ∈10−5,×10−5, 10−4,×10−4,10−3,×10−3, 10−2,×10−2 π∈\0.02,\,0.05,\,0.10,\,0.15,\,0.20,\,0.30,\,0.40\, δ∈\10^-5,\,5\!×\!10^-5,\,10^-4,\,5\!×\!10^-4,10^-3,\,5\!×\!10^-3,\,10^-2,\,5\!×\!10^-2\. All reported results use the selected hyperparameters evaluated on 20 independent random seeds (independent test states for ACS Income), ensuring no leakage between selection and evaluation. The selected values are reported in Table 4. We also report the sensitivity analysis for the grid on Adult with DP constraints in Figure 3. We observe the same behavior on all datasets, for both constraints (DP or EO). For Shifty, the fairness tolerance ε was set to the largest value avoiding systematic No-Solution-Found outcomes: ε=0.10 =0.10 (Adult, DP), ε=0.05 =0.05 (COMPAS and ACS, DP), and ε=0.15 =0.15 (Adult COMPAS and ACS, EO); all runs used the unknown-shift setting (setting=2=2) with α=0.25α=0.25. ERM and all base classifiers use ℓ2 _2-regularised logistic regression with C=1C=1 and the lbfgs solver. ERM+DP and ERM+EO (Exponentiated Gradient) use ε=0.01 =0.01 as the fairness tolerance, following the default recommended in Agarwal et al. [1]. For PostProc, the entropic regularisation is set to ε=2−128 =2^-128 (effectively zero, corresponding to the unregularised regime), and the number of stochastic optimization steps T is set to twice the size of the unlabeled calibration set, in accordance with the theoretical prescription of Chzhen et al. [11]. (a) Accuracy↑ (b) (h)↓U(h) (c) Deployment Gap ↓ Figure 3: Hyperparameter sensitivity on the Adult dataset (DP constraint, seed 0). Each cell reports the value of accuracy (left), (h)U(h) (center) and deploy gap max(|Φ(h,0)−t|,|Φ(h,1)−t|) (| (h;0)-t|,| (h;1)-t|) (right) as a function of threshold δ and the perturbation lower bound π¯ π. E.2 ACS geographic experiment. The ACS Income task [15] is derived from the 2018 American Community Survey and covers over 1.5 million working-age adults across all US states. We train on California (n=80,000n=80,000 subsampled) and select hyperparameters on 3 validation states (n=30,000n=30,000 per state). We use 11 test states, with White resident proportions ranging from 62%62\% to 93%93\%, never seen during hyperparameter selection. Table 4: Selected hyperparameters for STABLE. K=30K=30 and m=60m=60 are fixed across all settings. N.A. stands for Not Applicable. Adult COMPAS ACS Income DP EO DP EO DP EO π¯ π 0.020.02 0.150.15 0.020.02 0.150.15 0.020.02 0.150.15 δ 10−510^-5 10−510^-5 10−510^-5 10−410^-4 10−510^-5 10−510^-5 E.3 Results on ACS with EO constraint On the ACS geographic experiment under EO (see Figure 4, Stable remains the closest to t across all held-out states, with a near-flat slope πstate↦ΦEO(h,πstate) _ state _ EO(h; _ state), and ERM+EO achieves comparable deployment stability. PostProc drifts systematically above t, while Shifty drifts below t despite explicitly accounting for demographic shift. On the accuracy-EO unfairness tradeoff, Stable and ERM+EO form a competitive frontier in the low-unfairness, high-accuracy region, whereas PostProc exhibits larger variance across states and Shifty trades accuracy for fairness without closing the gap on either. Figure 4: Geographic generalization on ACS Income. (left) Prediction rate Φ(h,πstate) (h; _state) as a function of the state proportion of White residents. Dashed lines show linear fits per method; (right) Accuracy vs. EO unfairness gap (h)U(h) across held-out states. Each point corresponds to one state. E.4 The effect of t We denote by tERMt_ERM the target level estimated from ERM and used throughout our experiments. In addition, we consider a grid of 25 values for t in (0.05,0.95)(0.05,0.95). We train STABLE under both DP and EO on Adult dataset for all the values of t, using the hyperparameters tuned at tERMt_ERM, over 20 random seeds. For DP, Figure 5(a) shows that the accuracy is fairly stable over the first half of the grid, then it slightly peaks around t=0.5t=0.5, then dramatically drops, suggesting that the problem no longer converges. By contrast, the unfairness and the deployment gap remain very stable. For EO, Figure 5(b) shows that the accuracy increases as t approaches tERMt_ERM, remains stable in its neighbourhood, then drops dramatically as t moves away, again indicating non-convergence. The unfairness and deployment gap increase as t approaches tERMt_ERM, then slightly peak, and finally decrease gradually. (a) The effect of target t on Accuracy, Unfairness, and Deployment Gap for STABLE under DP. Shaded regions show ± std over 20 random seeds. (b) The effect of target t on Accuracy, Unfairness, and Deployment Gap for STABLE under EO. Shaded regions show ± std over 20 random seeds. Figure 5: The effect of target t.