Regression under demographic parity constraints via unlabeled post-processing
Authors: Gayane Taturyan
Evgenii Chzhen
Mohamed Hebiri
Venue: NeurIPS 2024 poster (2024)
Keywords: fairness
regression
Primary area: fairness

Abstract: We address the problem of performing regression while ensuring demographic parity, even without access to sensitive attributes during inference. We present a general-purpose post-processing algorithm that, using accurate estimates of the regression function and a sensitive attribute predictor, generates predictions that meet the demographic parity constraint. Our method involves discretization and stochastic minimization of a smooth convex function. It is suitable for online post-processing and multi-class classification tasks only involving unlabeled data for the post-processing. Unlike prior methods, our approach is fully theory-driven. We require precise control over the gradient norm of the convex function, and thus, we rely on more advanced techniques than standard stochastic gradient descent. Our algorithm is backed by finite-sample analysis and post-processing bounds, with experimental results validating our theoretical findings.

Regression under demographic parity constraints via unlabeled post-processing
Gayane Taturyan
Evgenii Chzhen CNRS, Université Paris-Saclay evgenii. chzhen@cnrs.f
IRT SystemX, Université Gustave Eiffel, Université Paul-Sabatier
gayane waturyaanumii--eeeff....fff
Mohamed Hebiri Université Gustave Eiffel mohamed, hebiri@univ-eiffi
Abstract
We address the problem of performing regression while ensuring demographic parity, even without access sensitive attributes during inference. We present a general-puree purpose post-pon post-processing algorithm that, using accurate estimates of the regression function and sensitive attribute predictor, generates predictions that meet the demographic parity constraint. Our method involves discretization and stochastic minimization of smooth convex function. It is suitable for online post-processing and multi-class classification tasks only involving unlabeled data for the post-processing. Unlike prior methods, our approach fully theory-driven. We require precise control over the gradient norm of the convex function, and thus, we rely on more advanced techniques than standard stochastic gradient descent. Our algorithm is backed by finie-ssmple analysis and pest-processing bounds, with experimental results validating our thcoretical findings.
1 Introduction
Algorithmic fairness an umbrella term a subset machine learning research that aims to better understand, quantify, mitigate, evaluate, and conceptualize negative and/or positive effects of data- driven algorithms on the society. At least one direction this field falls within theoretical machine learning, where form of fairness constraint, mainly inspired by common sense and formalized within mathematical framework, is proposed as an arguably reasonable proxy for a definition of ethical and con-discriminatrry prediction. Even more particular sub-field of this research direction is formalized within a paradigm of group fairness, that aims at mitigating negative impact (or provide equal treatment to) towards sub- nub-populations that share common sensitive characteristic. Many works fall within this category (Barocas et al., 2018, Calders et al., 2009, Chiappa et al., 2020, Dwork al., 2011, Feldman et al., 2015, Gordaliza al., 2019, Hardt et al., 2016, Jiang al., 2020, Lum and Johndrow, 2016, Zafar et al., 2017, Zemel et al., 2013 2013,1 just to name a few).
Even without going into debates on the relevance of given definition of fairness, many, purely mathematical and algorithmic questions remain unanswered in this field. The best theoretical understanding of the problem is available for the demographic parity constraint in case of awareness the situation when the sensitive attribute is available at inference time (Agarwal et al., 2019, Chiappa et al., 2020, Chzhen and Schreuder, 2020b, Chzhen et al., 2019, Denis al., 2024, Gaucher et al., 2023, Le Gouic et al., 2020). The latter case is well studies both in classification and regression setups. This is no longer the for other fairesss constraints the mnwaarenes setup the situation when the sensitive attribute is not available at inference time. particular, while the case of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

classification has been studied before from algorithmic and mathematical perspectives (Chzhen et al., 2019. Gaucher et al., 2023, Gordaliza et al., 2019, Hardt et al., 2016), the regression setup remains largely under explored and many methods lack strong theoretical evidences. In particular, to date, none of previous works effectively build computationally-efiiiiii the problem of regression under the demographic parity constraint in the case of unawareness. The present work fills this gap. Relying on previous ideas of discretization that goes back to Agarwal et al. (2019), we design smooth convex objective function whose exact solution yields a fair and optimal prediction function. turns out that this objective admits a first-order stochastic oracle that can be evaluated using only one independent sample of feature vector, thus allowing for stochastic optimization approach. Furthermore, despite the convexity, we show that the key quantity to control is the gradient (or rather gradd)nttmaap) of this objective function, deviating from the more common setup of controlling the optimization error measured by the objective function. We deploy recent machinery of Allen-Zhu (2021) and Foster et al. (2019) that allows achieve this goal, properly and recovering the usual statistical rate 1/ I/VT for both fairness and
fully theory-driven algorithm for
setting all the Slyper-parameee risk guarantees - T being the number of samples.
Our work falls withing the realm of post-processing methods-anothed umbrella term that combines all the methods that perform refitting of a base estimator to satisfy a certain constraint.
Importantly, due to the careful design of the above mentioned objective function, we can perform this post-processing in an online manner using a stream of i.i.d. unlabeled data without keeping in memory, making it attractive in practice. Our approach is based on a combination of ideas from previous contributions to fairness from Agarwal et al. (2019) and Chzhen et al. (2020b) and recent stochastic optimization literature (Allen-Zhu, 2021, Foster et al., 2019) that deals with stationary point-type guarantees in the case of convex optimization.
Contributions Our contribution is three-fold: i) we significantly enhance the discretization strategy of Chzhen et al. (2020b) accommodating multiple sensitive features, relaxed fairess constraints, and unawareness setup; we introduce entropic regularization for this problem and design dual convex objective from it; ii) we design semi-supervised post-processing algorithm and show that it enjoys strong theoretical guarantees; fii) we perform numerical simulations demonstrating the relevance of our approach in practice.
Organization. This paper is organized as follows: in Section we present the problem setup and introduce main rroblem-related notation; in Section we describe our methodology step-by-step and highlight main challenges and relations to other results; in Section 4 we gives technical details of the proposed approach; Section 5 contains main theoretical results of the work; finally, Section 6 contains empirical evaluation of our method. All the proofs are postponed to the appendix.
Notation. Let us present generic notation that is used throughout this work. For a positive integer
K, we write [K] to denote [1...., }} and [K] to denote { {-K.... ...... K}. For a > 0 denote by [a] largest non-negative integer that smaller or equal to a. For a univariate probability measure μ., we denote by supp(p) its support. For every 3 > 0, m E N. and w = (wi...., .., wm, R", we denote by LSEg IR" + IR the log-sum-ext function, defined as
b......K,
LSEs(w) = =8-21og
Σ exp(Bwc))
For every E N, w = (Wi, Wm) T RT we denote by (aI,..., am) Rm + Rmm the soft-argmax as (w) = exp(w, ( exp(w;)). For any matrix A, the notation A > means that A is positive coordinate- wise. For any a E R and w E R" we set (a)_ max (0, a} and (w) - ((w1)+..... (w,m))))...,,)) The notation Ö hides (unimportant) constants and polylogarithmic factors. For pair of random elements (A, B), we denote by Law(A), the law of A, by Law(A B). the conditional law of given B. and we write A IL B to denote that variables independent. For two vectors w, w E R",, we write w//w' (wy/w()) element- wiie division. The Euclidean norm of a vector and the Frobenius norm of a matrix are denoted by || |l. while the spectral norm of matrix is denoted by || llop- We denote by B B(R), the Borel sigma-algebra on IR, induced by the usual topology. We write log to denote the natural logarithm and log,, the base > 0 logarithm.
and B are E R to denote
2

---

2
Problem setup
Let Y) be a triplet of nominally non-sensitive, nominally sensitive, and output characteristics, taking values in R x [K] I for some K > 2. We assume that (X, S,Y) P, for some unknown distribution P. The main quantities of interest are the following: the regression function ((x)) def E X æ]; the marginal distribution of sensitive vectors p def
(Pa)sE[K] with ps def (Ta(#)) with (2)) def P(S= = X = z). A randomized prediction function is a map т. BR) x R + [o, 1] such that the map B + π ( x) for B ((R is probability measure on (RR, B (R)) for all
P(S = s): the conditional distribution of S given X, defined as ((x)
def
Rdd For any prediction ι we define random variable V as
Law Yxx X x. S ==)= x x)) VER [K].
Remark 2.1. Note that T( x) is a Dirac measure for all x E R the above condition just means R - R. The above condition is not to
that Yz g(X) almost surely for some deterministic be confused with the fairness constraint, which is not formulated point-wise. It only viewed as an extension of the unawareness framework to the case of randomized predictions. The above condition completely specifies the distribution of the triplet (X, S, Yx) but leaves the relation between Yx and Y ambiguous. To be more formal, one needs to add the condition (Y,, Y) (X,S), that is, the prediction Yz is independent from the true label Y, conditionally on (X, That would define a complete joint distribution of (X, (X,SYY,
S,Y. Yn) ~ P ((S))) @ Pr((x.)) @ T[- X).
We consider the following risk of a prediction function π
R(T) def B - 7 (x)) ( (()) x))
n(
A prediction function π is said to satisfy the demographic parity constraint, if Yx 1 S.
That is, Yn is stochastically independent of S viewed from the perspective of the joint distribution of (X,S, Yz). On the high-level, the goal in this setup is to find a prediction function æ, whose risk is small and whose violation of the demographic parity constraint controlled as quantified by some measure of unfairness. The above problem is well understood in the case of awareness thesess-hhhhhhhhhe situation when is expressed as π-- x 8) (Chiappa et al., 2020, Chzhen et al., 2020a, 2021, Jiang et al., 2020, Le Gouic et al., barycenters. Yet, when the sensitive attribute is not an input the prediction function, the situation is drastically different. Some attempts have been made to either (so far only partially) characterise the optimal prediction function (Chzhen and Schreuder, 2020a, Gaucher et al., 2023, Zhao, 2021) or to design efficient algorithms for this problem (Agarwal et al., 2019, Maheshwari and Perrot, 2022, Narasimhan et al., 2020) that are only partially supported by sound theory. One of the principal goals of this work is design computationally efficient algorithm that admits (near) end-to-end theoretical guarantees. The main difficulty of the problem lies in very different natures of the risk and the fairness constraint the latter involves image measures, while the former is simple linear functional of æ. In the case of awareness this issue can be bypassed by lifting the problem in the space of measures, working there directly and, then, returning to the initial space of prediction functions. Crucially, this is achieved only thanks to the fact that is known at inference time, which is not the case for the considered problem.
intimate connection of this problem with Wasserstein
Remark 2.2. In what follows we will exclusively focus on the squared risk and the regression setup. However, one can observe that the proposed methodology can be extended or even simplified for R(T)) [[[(X,Y, Yx)l and multi- classification respectively under the demographic parity constraint. Here r(æ, y) quantifies fit of ÿ for an individual x and can be either known unknown.
3 Our methodology
The starting point of our work is similar to the one of Chzhen et al. (2020b) and relies on a simple observation-iit (upp(TT(:] æ))] oo and stays the same for all æ. the independence constraint
3

---

is reduced to a finite amount of constraints that only involve the image of π(- x). In particular, assuming that (upp(x((1 æ)) D R for all x E Rd, Yz is independent from S iff PP(Y, ū
= 8) P( = 9) for all 8 E [K] and all y E D. In view of the definition of Pr, the latter is
equivalent to
R|=(O X) S] El X)]
E [K], D
(1)
which, assuming that V is fixed, correspond to linear constraints on æ. Combined with the observation that - R(T)) is also linear, we end up with a problem that is significantly easier to handle.
Furthermore, again assuming that 5 is fixed, the sketched direction gives a natural way to introduce some slack to the independence constraint- constraint-simplyy requiring approximate equality in (1). Set
(TT, [E [T(( x) S = s] E X)]I
del
(2)
for all E [K] and y D. Thus, for a fixed support (whose choice will be discussed in the next paragraph) and fixed vector def (EK).. our goal is to build an estimator of solution to {R(#)) supp(r(- x)) 5 for R., Us v & E, for T E 5, 8 [x]]
min [o.1] x:B(R)xxd
(3)
Let us now describe the methodology for selecting S and the trade-offs that are introduced.
Introducing discretization. Having in mind the above discussion, for every integer L > 0 and real B > 0. we introduce a uniform grid Dr def B [[] L on [-B, B). so that [52]| = 2L + 1, which is viewed as support of prediction functions T[- x). For the sake of simplicity, we will assume that the regression function 77-) is bounded in B, B] for some known B > O.
-BBB,
Assumption 3.1 (Bounded signal). There exists B > 0 such that (n) XX] < B almost surely.
Thus, for a given B, the main parameter to tune is L > 1-the higher the L is, the more accurate prediction functions can be produced, while lower values of L ensure that the demographic parity requirement reduces L. natural attempt to tackle the problem of fairnsss in this context would be to estimate a solution
small number of constraints. Thus, there is a trade-off that is introduced by
to (3) with 5 = VL. Of course, L needs to be chosen so that the aforementioned solution attains the risk that is close to the risk of some benchmark prediction function that does not involve any discretization. This will be discussed later in the text. For now, let us address another subtle issue. Even assuming complete knowledge of the underlying distribution P. solving (3) requires solving linear program in dimension 2
(LL)) which can be infeasible in practice for large values of L and K.
Instead of (3), we rather focus on the entropic regularized version of it. For / > O, we consider
(R((T) supp(r(- x)) = 5 for a ER" U. T) E, for ū 5, E [K]] (4) -xB(R)xdd_ 10,11 where (T) = R(x) + (R(((T( X))] and for any discrete univariate distribution μı, we define def
min
its negative entropy & (1)) Enjesppp(e) (()) log (())).
Remark 3.1 (On abuse of notation). Note that for every ij E 52 there is a unique & [L] such that ÿ =BtB/L (B/L L and we will write T( x) instead of αt z). Similarly, we write Ud (TT, E) instead of (T, 9). defined in (2), when no confusion is possible and the support Vr. is fixed.
An extremely attractive feature of the problem in (4) is the fact that the solution it can be written explicitly as a function of optimal dual variables, with the latter being a solution of a stochastic convex program with Lipschitz gradient-the main observation of our approach, that shares many similarities with the smoothing technique of Nesterov (2005). This is summarized in the following lemma.
Lemma 3.1. Let L E N and 8 > O. Let A (X1s)e114),sE(R) and V (VE))eTL)).s(( be two matrices that are solutions to
min F(A, V) def A.V30
LSE ((tee - ve, f(x)) - re rx(())))))))))))))))()))))) [elm4]]
+
Σ (De + ve, 5) et (5)
[E(C]
where t(x)) def 1 [(m)
re())) def (1((²) 4 and A = (Des) Us (Ut)) Then, (4)
p
admits solution in the form
7A (. x)) def
0e (3 ((2x - vē. t(x)) - re (=()))) for l E [L].
(6)

---

Assuming perfect knowledge of 1) and т, the above lemma suggests a natural approach to estimating the TA V...v.- can run (version of) stochastic gradient descent on F(.:-) and then plug-in the resulting dual variables in the formula for л v Notably, stochastic gradient of F(:.)) can be obtained by simply sampling one X from x- does not require labels for this step. Yet, even in the above idealized case, it is not clear which optimization criteria would allow us to prove that the resulting solution would yield good properties in terms of risk and fairness. As we will see, despite the problem in (5) being convex with Lipschitz gradient, it is crucial to control the norm of the gradient of for good statisitcal properties of the algorithm. That goes without saying that this relaxation has its price- the smaller the regularization parameter 3 the less accurate the resulting solution, but the resulting dual optimization problem is easier and vice-versa.
Properties of F and VV..V". Let us summarized key properties of the objects introduced in Lemma 3.1. The first two results concern the population properties of AV+,v*
Lemma 3.2 (Faimess quantification). Let I. e N, (Es)>E[K] E [0, 1]K B 0, and T be defined in Lemma 3.1. Then, U₁ (TT--VVV-.)) for all s [K], E [4]-
In words, the optimal entropic-regulariize prediction function is feasible for (3), that is, it satisfies the relaxed fairness constraints as quantified by (2). Furthermore, we can show that its risk is also controlled by the regularization parameter
0.
Lemma 3.3 (Risk gain). Let L E N. > 0, and V be defined in Lemma 3.1. For any T: ((R) x R + [0, 1] that is feasible for (3), we have
R(TA..V.) & R(T)+ + logl B
The above result is rather instructive, it quantifies the price of the introduced regularization. Intuitively, one wants to set B high enough, so that the additive term in the above bound is vanishing. Unfor- tunately, we cannot set it arbitrarily high, since will introduce instabilities from the optimization perspective the function F becomes less regular 3 growth. This is summarized below.
Lemma 3.4 (Regularity of F). Let o² del -2 2>EE[K] 1-P,, The objective function in (5) is convex and its gradient is -Lpsh-iipschitz.
As mentioned, we see that the larger the 3 is. the less regular the function F is. making it harder to minimize. Thus, 3 > O controls the trade-off between the optimization error and statistical bias.
Gradient of F is crucial. Let us show that the control of the gradient of F is the most important and non-trivial part that allows to demonstrate strong statistical properties of the plug-in rule derived from the above strategy.
To this end, let us introduce parametric family of prediction functions, defined for any A, V > 0sas
(e x)) def oe (B(e ve, t(x)) re (x)))4111 for l E [4].
We want to show that if A, V > is nearly stationary point of F, then TA,V v is nearly optimal in terms of risk and its violation of the demographic parity constraint is controlled. Note that the optimization problem in (5) is constrained, thus, unless the minimum lies in the interior of the domain, cannot hope for the gradient of F to go to zero. Instead, we introduce gradient mapping- quantity that shares many properties of the gradient in the case of constraint optimization problem. For 0,
A. V) ((A, V) - aVF (A, V))
G. (A,
ak
Our main observation is summarized in the next lemma.
Lemma 3.5. Let 2² 2 Eee(K] of TAN satisfies
1-Ps L N, 2 0, then for any > 0, B > 0, the unfairness
Pa
Σ (E[L|EE[K]
(u(( - (IG
Furthermore,
R(TAV) & R((TA.V-)+ + (I(A,
a fo ao+ ||E|| V v2521 |Ga(A, V)Il+ log 5i
B
5

---

Lemma 3.5 is very instructive on its own we can obtain good estimator of TA in terms of risk and unfairness by performing stochastic optimization on F and controlling the norm of gradient mapping for suitable parameter a >> O. The final choice of the parameter a will depend on the optimization algorithm used and will be purely theoretical. In particular, for our purposes, it is sufficient to guarantee an existence of some value of a: > 0 that yields desired statistical properties. A naive approach in doing so relies on a well-known relation between F F(A, V) - F(A", V*) and [G,(A, V)l using the Lipshitzness of the gradient of F (see e.g., Beck, 2014, Lemma 9.11), More concretely, forgetting about the constraints', one has
|VF V) < 2M (M(A
V*).
where M is the Lipschitz constant of V F. Thus, the above inequality suggests that it is sufficient to control the standard optimization error in order to control the norm of the gradient. Unfortunately this approach is deemed to fail for two reasons: the first being that control only the squared norm of the gradient map and not the norm itself, thus loosing in the rate of convergence; the second, and more subtle reason, is the separation of the purely "statistical" rate that depends only the variance of the stochastic gradient and scales 1/ /T, with T being the number of future samples from IP x. and "optimization" rate of convergence that depends on M and the diameter of the problem and typically scales 1/T or even 1/ if acceleration is used.
Indeed, our setup, Lipschitz constant M of VF is not a fixed constant, but a parameter to be set-it relates to ,3 (cf. Lemma 3.4). Ideally, seeing Lemma 3.3, we want to set B = ((VT), leading to M = (VV)). Thus, in view of (9), a term of the form M/ M/vT appears in the convergence rate, which destroys consistency of the resulting estimator. Arguably, this is less of an issue in case of convex optimization with constant Lipschitz constant M, especially if we only want the norm to go to zero. This discussion highlights that it is crucial to keep the separation between the statistical part of the rate and the optimization part of the rate, while controlling the norm of the gradient. Lucky for us, it is known that for convex problems one can indeed control the gradient mapping keeping this separation of the rate (Allen-Zhu, 2021, Foster et al., 2019). Note that it is not the case for non-convex problems demonstrated by Arjevani et al. (2023).
Summary of our approach and why is it different from others. Now, keeping in mind the above, rather long justification, we are in position sketch our approach and the formal presentation is deferred to the next section. For well selected parameters |3 >> 0, L E N, we are going to perform stochastic optimization of F. relying on the SGD3 algorithm of Allen-Zhu (2021). In order to compute the stochastic gradient of F,, we are simply going to sample one I'x and it appears that this stochastic gradient has well-behaved variance (see Appendix B-C for details). To make our approach completely data-driven (or at least to understand the order of magnitude of the parameters), we will compute or bound all the oracle quantities that appear in the used optimization algorithm (essentially related to the step-size tuning). We will show that for any sufficiently small a > 0, the term B|| G. (A, V)[l is controlled and then rely on Lemma 3.5 and some additional results to demonstrate that the resulting Tx v. possesses good statistical properties.
Remark 3.2 (On the dynamic of algorithm). Note that for A V 0, the corresponding
(To.o(E) ( x)) x)) = ( (()(((
That is. the above prediction puts the most amount of mass on the atom E which minimizes (π((x) {BIL LBj most accurate, but unfair prediction. Since our algorithm is based on a SGD-type algorithm, initialized at Ao = =Vo- = 0, then we expect that during the dynamic of the algorithm, the risk of N,N, increases, while the unfairness decreases. This phenomena coincides with the intuition of post- post-processing-ww we want gain in fairness, while sacrificing some accuracy.
As it has been already mentioned, the idea of discretizing the image of (randomized) predictions is not novel and has been successfully deployed by Agarwal et al. (2019) for in in-rrocessing estimator and by Chzhen et al. (2020b) for a post-proce post-processing estimator. We use this insight as a building block, but significantly deviate from both algorithms. Compared to Agarwal et al. (2019), our algorithm is positioned in the realm of post- post-processing and even online post- post-processing, where i.i.d. samples
Constraints introduce additional challenges, but are not relevant for this discussion.

---

from Px comes in stream and we do not need to store them in memory. Also, while their algorithm partially inspired by theory. the same theory suggests that this algorithm is not computationally efficient and it relies on some black-box parts that assume perfect solutions to some optimization problems. That being said, the algorithm of Agarwal et al. (2019) seem to be the gold standard method for the generic in tn-processing method in this problem. Compared to Chzhen et al. (2020b), we have made a sequence of improvements. First, our setup is unawareness, which is not the case in their paper; second, our algorithm is able to handle multiple protected attributes as well as approximate fairness constraints; finally, and most importantly, we do not make black-box assumptions about having access to exact minimizers of convex problems and provide end-to-end analysis of out approach. Let us also remark that our method cannot be considered as a simple extension of Chzhen et al. (2020b) subjective note, we believe that our approach is a nice example of a real convex optimization problem, where the norm of the gradient plays the central role, while the optimization error in term of the objective function does not m This is precisely the phenomena highlighted by Nesterov (2012).
rely on different phenomenons and provide very different algorithm. On more
4 Proposed algorithm
Algorithm 1: DP post-processing[L.,..81 ,,
1: Input: discretization parameter > 1; regularization B > 0, number stochastic gradient evaluations T > 1; marginal distribution p of S; regression function rj; conditional distribution T of 5 X; bound B > 0 on
2: Build uniform grid V/ over [|B
3: Set parameters: o²
EeE[K] 1= M =30²;
p.
4: Set (A, V) + ((A, V) as defined in Lemma 3.1
5: Run black-box optimizer A(F, o² M,, T) on function F having access to T stochastic gradient
evaluations (see (11)) with variance o² and smoothness parameter M to obtain (A, V);
6: return V) 1.) defined in (7);
In this section, we provide all the details about the proposed algorithm in case and T are known. If they are unknown, these quantities are replaced by their estimates f and f that are constructed separate labeled dataset. First, for A = (Aes)eE(4(,EE(4) V (41.)))14)).E11)) let us provide the expression for the gradient of F:
VD. V) AE de (3(12e ve, t(X)) re (X)) t, (x) + t
(10)
where D E {A.v) and A = lif À and A = -1 otherwise. Thus, a stochastic gradient g(A, V) (gxz, (A, V). (A. ViJeE(L).eEIN of F at point (A, V) can be computed by erasing expectation in (10), i.e., by sampling one X Fx, using the same convention as above about U, A:
9Dc (A, V) = Aoe (B( ve, t(X)) - - (x) rx (X)6=-)) to (X) + Es.
(11)
The next result controls the variance of the above stochastic gradient.
Lemma 4.1. Let o2 def 2 E
P_ It holds that (A, V) - VF V) < o2.
The proposed method is summarized in Algorithm It uses a black-box stochastic optimization algorithm A, that operates on convex function F and stochastic first-order oracle. The stochastic- first order oracle is implemented by (11) and only requires to sample X ~ P in an i.i.d. manner. We also pass two additional parameters to this algorithm: namely, we pass the variance o² from Lemma 4.1 and the Lipschitz constant of the gradient of F from Lemma 3.4. Then one can use any such algorithm. However, as shown in Lemma 3.5, those algorithms that are tailored to control expected norm of gradient mapping are preferred. For example, one can use SGD3 of Allen-Zhu (2021) or an improved version of Foster et al. (2019) that relies on restarted accelcrated SGD of Ghadimi and Lan (2012).
"To be precise, the optimization emor is automatically handled by the control of the gradient.
7

---

5 Theoretical guarantees.
Let first provide main results for Algorithm assuming that 1) and t are known. Note that Algorithm can rely on any optimization algorithm. We provide complete analysis using a refined version of SGD3 algorithm of Allen-Zhu (2021) that is due to Foster al. (2019) with additional modifications taking into account the specific structure of our problem. We state the main result in existential form and postpone all the details on the implementation of the algorithm and primer on optimization to the supplementary material (Appendix C-D).
Theorem 5.1. Let & (E)) E [0, 1]K and 0² 2 EEEKK Ps)/ Setting B (ogg((T) and VT, there exists an optimizer to be used in Algorithm that, for T larger than some absolute constant, ensures
E//a
Σ
(U.(TAV -..)
o VT
1
o
IIA
RE[L[(E[R]]
Furthermore, if Assumption 3.1 is satisfied and let
R. def
inf
Ex R(h) : sup (P(((X) Et/S= - (()(X) & $0]
Ao E [x]]
(12)
hand-a [- B.B]
EER
2
and El (
def E [R(TAV))] -
RR,, then for the same algorithm
{(TXN) kō (( BVV (or)
||ll| + T%
(1
a VT IIA'', V
+
Theorem 5.1 gives two results: the first one being on the unfairness of the proposed estimator and the second one on the risk of thereof compared to benchmark prediction function in (12). The benchmark that we pick is rather natural, we compare to the risk of a deterministic prediction that minimizes the risk and whose unfairness is controlled by Kolmogonov- -miinov distance. One first main observation is that both faimess and risk decrease the rate 1/VT and T is the number of unlabeled data. From our numerical experiments, we observed that we can keep the number of unlabeled data unchanged and iterate several times through them. As result, we increase artificially T-without generating new data-which gives a significant empirical improvement. We also remark that a is the parameter that depends the number of groups. For example, in the case of uniform distribution of sensitive groups a = O(K). We finally remark that both bounds involve a single unknown quantity-llAA
VII].. which from standard duality argument can be shown to be bounded by OL1/ (k] (see c.g., Nedić and Ozdaglar, 2009, Lemma 3). Thus, having this norm multiplied by T12 is very attractive property of the bound. It allows to set E = 1 without damaging the parametric convergence rate.
1/2
To derive the above result, we slightly extend the analysis of Foster et al. (2019), who, relying on the SCD3 algorithm of Allen-Zhu (2021), gave an optimal algorithm that controls the expected norm of the gradient in the convex case. More concretely, we incorporate projection step into their analysis and extend the control to the squared norm of the gradient map. Interestingly, due to our smoothing step and the choice of the parameter 3, we noticed that there is no need to restart the accelerated SGD as it is done by Foster et al. (2019) because leads to identical statistical convergence rates. The interested reader can take closer look into the Appendix C, where all the optimization results are either recalled or derived for the sake of completeness. Finally, having a control of the squared norm of the gradient map, the proof of Theorem 5.1 follows from Lemma 3.5 and careful and practical choice of all the parameters of the algorithm.
Extension to unknown 1) and In this part we show that if we replace 77 and 7 with their estimates 7 and 7 and run DP ppost-processing/e T,B, p. B, 7, 7) algorithm with the same choice of parameters, Theorem 5.1 remains if we pay additional price for the estimation of and T. From now on, we assume that f and f are provided and are trained on its own labeled data sample, while the refitting is performed on an independent stream of i..d. data from Px. So, we essentially treat fj and as deterministic functions. Let us introduce a family of prediction functions
RA. (E x)) oe ((( ve, b(x)) - Fer Fe) )
for l E [T]]
(13)
8

---

Note that for fixed matrices A, V. the above prediction function is fully data-driven. With this plug-in strategy, our approach becomes fully data-driven and, in Appendix E, we show that the guarantees presented in the main body still hold paying additional price for estimation of 1) and T. To be more precise, we consider the plug-in version of (5), defined as
(((>-- ((x),(x)x))))) - fx )
L Σ ビ=-L
Ae vc, a). (PLSE) (PLSE)
min A.V30
Ex
LSE,
+
(Ae
Let us denote by F, the objective function of the above problem. Thus, main interesting part is to demonstrate that control of the gradient map of F, denoted by (. V)Il gives a control of risk and unfairness of A. v quantifying the price induced by the plug-in estimation. This is precisely the purpose of the following two results:
Lemma 5.1. Let N. A, e 0, then for any a > 0, 8 0 it holds that
Σ
(M) -)
|| (A, V) + E [(x) - +(x)
[EIL]HE[K]
Lemma 5.2. Let 6a 2EEE[K]
Ex(p- (x)))
LEN,A, O. then for any a > 00,3 > 0
P.
holds that
R(MAV) & V(TA..V-)+ + [I(A, +a ++ |ell V2
| F,a (A, vi/l+ log 15
33
+ 2Ex
max (re(X) - f(())) + (2I V)I E {(1) (ELL)
Note that the above results are extensions of Lemma 3.5, where both & and 1) were assumed to be known. These results are following the spirit of post-processing bounds-the quality of the final approach depends on the initial estimator and the optimization algorithm used to post-process and the two errors are clearly separated. Proofs of both results with additional details and discussions is provided in the supplementary material.
6 Numerical illustration
In this section we conduct empirical study of the proposed algorithm, denoted by DP OP-postproc. and demonstrate its relevance in practical problems 3. We have implemented both SGD3 of Allen- Zhu (2021) and an improved version by Foster et al. (2019), observing that the latter significantly outperforms the former. We also tested the approach that is suggested by the theory-SGDS and accelerated SGD, without restart and it show nearly identical performance as the restarted version of Foster et al. (2019). Thus, for numerical evaluation, We conduct our study on two datasets: Law School dataset ( (Wightman (1998)) and Communities and Crime dataset (Redmond (2009)). In the Law School dataset, the aim is to predict students' GPA on a scale of 0 to 4, normalized to [0, 1]. while in the Communities and Crime dataset, we focus on predicting the normalized number of violent crimes per population within the range of [0, 1]. In both datasets, ethnicity is a sensitive attribute, distinguishing between white and non-w ooitw individuals or communities (majority-wisee Our pipeline is the following: First, we randomly split the data into training, unlabeled and testing sets with proportions of 0.4 0.4 0.2. We use Duruin = {(x;, 8;, ys y to train base (unfair) regressor to estimate 17 and to train a classifier to estimate т. We use simple LinearRegression and LogisticRegression from seikit-learn for training the regressor and the classifier. Finally, we use the trained regressor and classifier to train the Algorithm 1 with Punlabeled = (z) n+T for N (note that our theory suggests that N = T is enough, but we have noticed that larger N can be more beneficial in practice) iterations. We use D D
stick to the latter.
{(1%, 8/, =0mm1) to collect evaluation statisties.
In Figure 1 we illustrate the post- poot-processing dynamics of our method. We have 2 plots for each test dataset: the history of risk (R())) and of the unfairness (U)(a) and U (7)) w.t. number of iterations. We illustrate the convergence for (2-8 2-8) unfairness threshold. The explicit formulas of the
evaluation measures are provided in Appendix G.
The code is available at https: htttts://githut www. wctm//aaurraannuuaareetttt.a

---

CENVE
Toe schec
Resitions
Figure 1: Risk and unfairness of our estimator on Communities and Crime and Law School datasets.
Comparison with Agarwal et al. (2019). Surprisingly, we were unable to find many open source competitors that target regression with demographic parity constraint in unaware setting, even the FairLearn popular python package does not deal with the demographic parity constraint in regression. The only easily accessible algorithm that deals with our problem was kindly provided by Agarwal et al. (2019) (from now on referenced as ADW). We train ADW method in two ways: we use DD Derain and D unnlabeled as training set for ADW-1, whereas for ADW-2 we use only Derain- The second situation is realistic, when unlabeled data is available and unlike ADW, our approach is able to take advantage of it. We take the set {(2- 2 ">ee)) ), where I {1, 2, 4, 8, 16) as unfairness thresholds for training both datasets. We train ADW-1 1 and ADW-2 for each pair of epsilons for 10 times. With our available computing power and the code provided by the authors, the algorithm runs for 13.5 hours (see Appendix G for additional details).*
On Figure 2 we illustrate the comparison of risk and unfairness between ADW-1, ADW-2, base (LinearRegression) and our model. We plot the mean and standard deviation of risk and unfairness for each epsilon threshold on both datasets. We observe that our method is competitive or eventually outperforms ADW both training regimes.
communttes and oliee
school
CR2
Figure 2: Comparison with ADW model on Communitites and Crime and Law School datasets.
7 Conclusion
Deriving a dual convex surrogate, we have provided generic way to build a post-processing estimator of any off-the-shelf method that achieves the demographic parity constraint. Our approach is fully data and theory driven, revealing key role of stationary point guarantees in stochastic convex optimization. Following Remark 2.2, we intend to extend our approach, which is general enough, to other learning problems, beyond algorithmic fairness.
Limitations. From the theoretical perspective, the knowledge of B seems to be the main limitation. While it is available for many applications, it does not have to be the case all the time. Replacing this assumption with some tail conditions, could be more realistic. From the applied perspective, it would beneficial to further investigate stationary point guarantees for convex optimization to yield a better practical performance.
A Acknowledgements The work of Gayane Taturyan has been supported by the French government under the "France 2030" program, part of the SystemX Technological Research Institute within the Confiance.ai project.
'The experiments are conducted on a Processor 11th Gen Intel(R) Core(TM) 17-11 2.90GHz with 16GB
RAM.
10

---

References
A. Agarwal, M. Dudik, and Z. S. Wu. Fair regression: Quantitative definitions and reduction- based algorithms. In International Conference on Machine Learning, 2019.
Z. Ahu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd, 2021.
Y. Arjevani, Y. Carmon, J. Duchi, D. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):165-1144 2023.
Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning. fairmlbook.ng org, 2018.
A. Beck. Infroduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB. SIAM, 2014.
R. Bhatia and C. Davis. A better bound on the variance. The American Mathematical Monthly 107 (4):353 357, 2000. doi: 00.1080000298990200011100000
S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
T. Calders, F. Kamiran, and M. Pechenizkiy. Building classifiers with independency constraints. In IEEE international conference Data mining, 2009.
S. Chiappa, R. Jiang. T. Stepleton, A. Pacchiano, H. Jiang, and J. Aslanides. A general approach to fairness with optimal transport. AAAI, 2020.
E. Chzhen and N. Schreuder. An example of prediction which complies with demographic parity and equalizes group-wise risks in the context of regression. arXiv preprint arXiv:2011.07155 2020a.
E. Chzhen and N. Schreuder. A minimax framework for quantifying risk-fairness trade-off in regression. arXiv preprint arXiv:2007. 14265522, 2020b.
E. Chzhen, C. Denis, M. Hebiri, L. Oneto, and M. Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. In Advances Neural Information Processing Systems, 2019.
E. Chzhen, C. Denis, M. Hebiri, L. Oneto, and M. Pontil. Fair regression with wasserstein barycenters. NeurlPS 2020, 2020a.
E. Chzhen, M. Denis, C.and Hebiri, L. Oneto, and M. Pontil. Fair regression via plug-in estimator and recalibration. NeurlPS 2020, 2020b.
E. Chzhen, C. Denis, and M. Hebiri. Minimax semi- supervised set-valued approach to multi-class classification. Bernoulli, 2021.
C. Denis, R. Elie, M. Hebiri, and F. Hu. Fairnsss guarantees in multi-class classification with demographic parity. Journal of Machine Learning Research, 25(130): 2024.
C. Dwork, M. Hardt, T. Pitassi, Reingold, and R. Zemel. Fairness through awareness, 2011. URL /taps://arxiie org/ /1044. 3913.
M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian. Certifying and removing disparate impact. In International Conference on Knowledge Discovery and Data Mining, 2015.
D. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference Learning Theory, pages 1319-1345 PMLR, 2019.
B. Gao and L. Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: 1704000004. 2017.
S. Gaucher, N. Schreuder, and E. Chzhen. Fair learning with wasserstein barycenters for non- decomposable performance measures. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 2436-2459, PMLR, 25-27 Apr 2023, URL https: h/tp::/ee/ccccc....eeeooae mlr. press/v206/ 2aucher23a html.
Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22 (4):1469-1492, 2012.
Gordaliza, F. Del Barrio, Fabrice, and M. Loubes. Obtaining fairness using optimal transport theory. In International Conference on Machine Learning, 2019.

---

M. Hardt. E. Price, and N. Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
R. Jiang, A. Pacchiano, T. Stepleton, H. Jiang, and S. Chiappa. Wasserstein fair classification. Uncerlainty in Artificial Intelligence Conference, 2020.
Le Gouic, J.-M. Loubes, and Rigollet. Projection to faimess in statistical learning. arXiv preprint 20KY::0005.11720, 2020.
M. Lichman. Adult. UCI Machine Learning Repository, 2013. URL http::/archiiee ics icci uci. edu/ml.
K. Lum and Johndrow. A statistical framework for fair predictive algorithms. arXiv preprini 110.007610.08077, 2016.
G. Maheshwari and M. Perrot. Fairgrad: Fairness aware gradient descent. arXiv preprint
MrXh::2206110933 2022.
H. Narasimhan, A. Cotter, M. Gupta, and S. Wang. Pairwise faimess for ranking and regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5248-522 5255, 2020. Nedić and A Ozdaglar. Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications, 142(1):205-228, 2009.
Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(3):
127-152, 2005.
Y. Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, 188):10-11, 2012.
M. Redmond. Communities and Crime. UCI Machine Learning Repository, 2009. DOI: http:://doi.or//10.4444433 24332/533333
L. Wightman, Lsac national longitudinal bar passage study. Isac research report series. 1998. URL https://api. semanti cachooaaacclclrr.... org/ CorpusID:: : 151073942.
M. Zafar, I. Valera, M. Gomez Rodriguez, and K. Gummadi. Faimnsss beyond disparate treatment
& disparate impact: Learning classification without disparate mistreatment. International Conference on World Wide Web, 2017.
R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork. Learning fair representations. In International Conference on Machine Learning, 2013.
H. Zhao. Costs and benefits of fair regression. arXiv preprint
2021.
12

---

A Proofs for results in Section
First explicit the first order optimality conditions for the problem in (5).
Lemma A.1. Let (A*, V*)= > be any minimizer of (5) and πt' N- be defined in (6). Then, there exist r = (7te) [[[K] r ( wlise non-negalive matrices such that
Ex [x (1) X) - YE E (x+ (R) X)t( =E %
ve [4], E [K],
(14)
Veaiio =0
le =0
where = (Ttt) 9/ (clE))
Proof. We first observe that the optimization problem in (5) is convex and smooth. Thus, Karush-Kubn-Tuuckr conditions are sufficient for optimally. Furthermore, since Slatter's con- dition is satisfied, the latter is also necessary, the strong duality holds. In particular, there exist T = (Yea (11))) r' = (16s)eE [[),<<( -lemet non non-negative matrices such that
VAF V*) - =
FyF(A V*) - =
A V 00
vl E [4] s E [4].
Tea =0
16.4% =0
To conclude, is sufficient evaluate the gradient on F, whose expression given in (10) and the definition of .².
Proof of Lemma 3.1. To prove this result, introduce the Lagrangian for the problem in (4).
C(T, A, V) = (T)(T) + Ex
Σ
vv - Xe, t(x)) (e
x)
Σ
EETA
RE|L
where we used the fact, that using the definition of Ug, for any randomized prediction function m, we write
Us(T,t)= Ex [T(EE x)I{S= = P(S= =)
Ex [T(( x)]
Fx [<(e X),,())
(15)
Thus, denoting by (*) the value in (4), have
min max C(T, A, V)= max min C( A, V), V.
A.V30
where the second equality holds thanks to Sion's minmax theorem. Let solve the inner minimization problem on the right-hand-side. We can write
L(m, A. V) = Ex
(re(X) (). - 12, t(X))) (( EE[L]
Σ
x) + (T(( x))
(16)
Σ (e + uz,
SE|4]
Thus, using the variational representation of LSSE,, recalled Lemma F.1, we have
min C(T, A. V) =
max
Ex
(1) Mr, ((X)) (x)))) X) 3 ((((( x))
[E[T]]
Σ (e + Mz, e)
EE|L
= -EEx LSEs
(12e - vs. ((X)) re xe())es
Σ (Ae + +u, E) [E[L]
13

---

and the optimum in the above problem for every A, V > 0 is achieved by TA,V, defined in (7). Thus, we have
(+) = max {-F(A, V) RA(TA-NV-).
(17)
3.
The proof is concluded.
Proof of Lemma 3.2. As shown in (15), for any randomized prediction function π,, we can write U,( E) [xx [=(e (x)]
Our goal to show that n² satisfies the required fairness constraints. We are going rely on Lemma A.1 Subtracting the first equation in (14) from the second one, we deduce that Ye + % = 2e. Since Ye, v 2 then we conclude that Yex: Tés
[0, 28.). The above implies that
Ex
(E
X) (X) (= ,) E
as claimed.
Proof of Lemma 3.3. Fix some randomized prediction function æ that is feasible for the problem in (3). In particular, it must be supported on V Then, we can bound its negative risk as follows
RR(x)= -E Ex
Σ (T( X)
[E[L]]
(w)
$ Ex
Σ
((2) vi, t(x)) - (x) a(E x)
+ Σ
(Ai + vē, E)
[E[L]
[E[L]
(0)
Ex
LSEj
(116 vi, t(x)) - (x)2 ))
Σ
(Xi + vz 2)
(E[L]
(c) Ex
Σ
((A) v2. ((X)) (x))) xe x)
V(( [x))
Σ
(Ni + vř, e)
<E[L]
[E(L]
(d)
log log + 1)
15x
Σ
((X vú, t(x)) (x))) (4 x)
Σ
{x + vz, e)
B
[E[L]
tE|4
log(2L + 1)
R(mT)
B
(18)
for (a) used the assumption that is fair (iee Us(TT))) & ex), which due the fact that 2 0 implies
Σ (z Ex(((x( +E)+ E (ut, Ex [(X))(( X)] e) 00 [E|L]
EE[L]
since every term in the summation is non-negative; (b) uses the fact that (SE > (w, p) for any probability vector p (see Lemma F.1 for details); (c) relies on the variational representation of the LSE3, recalled in Lemma F.1 and the definition of x*(- X); (d) uses the uniform bound on the entropy: (c) the last equality relies on the complementary slackness condition (14) of Lemma A. ensures that
1r (T (E (X)) ~>i { 1E Ex (e (X)) = U2
V8 e [L], s E [K],
implying that
Ex
Σ x(x)) x (2) EE|4
+ Σ
(1) + + 8) 00
SE|L
The proof is concluded.
14

---

Proof of Lemma 3.5. Fix arbitrary A, V > 0 and consider TA, v. defined in (7). To ease the notation, in this proof, we write x instead of A. Part I. Let us first recall the definition of the gradient map G. given in (8). We have the following expression
G. (A. V) (A, V) ((A. V) aVF (A,(AA))),
a
where (+)+ is be understood entry-wise. Observing that for any a, a 2 0 and b R, we have max 00; ob)
(a- ab)+
min { b)
min (0: b)l > (-b)+,
a
a
we deduce that
(-VAA VI)+ & [[G.(A, V)II VA, Relying on (10) and the expression for π in (7), we observe that
(19)
Ve F(A, V) Ex [T (X)]
(20)
V Ve. F(A, V) Ex (T( (X)) + Ex
and that (T( [E [T t2 (X) }| as it shown in (15). Using the fact that (Ia) - c)
(-a- c) + (a (a- + for all a E R and c > O. we deduce from above
(U.(,AVV 0) =+ (- Vx. F(A, v)) + + (-V (A, V))
vee E [K]. (21)
Thus, we have shown
Σ ( = VI v))
EELL]
SE|K]
and (19) yields the claim.
Part II. We note that V) is unique solution min
"
where L is the Lagrangian defined in (16). Furthermore, min, A, -F(AAV)) ((TAAV) A, V). Hence,
Ra(M(()) + F(A,V)= =
Σ (E[]]
V F(A.V) V)+
Σ
VEA F(A,
EE[K]
= V), (F V))
For the sake of simplicity let us denote by def
(A, V) E (22(22-11) and recall the definition of gradient mapping Ga given in (8). For any j E [2T + +1] and a >> 0, we have
uifa (())(u)
if ad F(u) > Ujj
(u)
if 0, F F(u) < uj.
To bound (u, VF(u)), let examine each term of the scalar product. Denoting by ū der FVF(u) 22 for any j E [2K + 1)] and O. we have u(u) ad, Guy) 0} + G.
2 0}.
Thus, it holds that
(u, VF(u)) <
Σ
(ayj + + Gay (u)l < (| + [ [Ga(u)]
1E(K(2L+1))
(Iuul no +a v 222
|G.
where the last inequality follows from Lemma F.5 that bounds [VF(())].
To conclude the proof, we use the fact that It remains to observe that mina, v F(A, V) -R -RD(T(A, the bound (19) on [IFA, V))+ and the fact that RT(TT) < R(TT) + 12g(2L+11
for all k.
15

---

B Bound on the variance of the stochastic gradient and its' smoothness
Proof of Lemma 4.1. We have
Ex ( - VA,F(A,
(oe (3((Ae - ve, t(x)) - -Te -re (X)66=-- to (x()
x
27 [[[K]
x
Σ (x) [E[R]
2
1
Pe del
Ps
<E(K]
where the first inequality follows from the expressions of gA.v and VA.v (A, V). and the fact that
Var(X) < E[X²]: the second inequality follows from the facts that (a;bb)) ||al2 |b] < |all? [bll2 and that ||o(-))1 1; and the last inequality follows from Lemma F.4
Var(X X + a)
Proof of Lemma 3.4. The goal of this proof is to show that the gradient of (A, V) + F(A, V) is M- M-Lipschitz. To this end, first introduce some, rather heavy, but convenient, notation which will allow us to derive the announced result.
Introducing notation.
We first vectorize the variables (A, V) and express them
LI. LK,
AL ALK, -1---VV-LL.
ULI," ".I,"..00 ..K C (2(L++1
Furthermore, for each a Rdd we introduce a matrix (x) E (22 1) defined as
t(xx) 0...0
0...0
-(x) T
0...0
0 0...0 0
(xx) def 0...0 t(x)
0..
0...0
((x)
0
0...0 0
t(x)T
0...0 0...0
t(x) T
as well
b( x def (X-)(X), r(())) E 2
and
def
(EI, ,KK; 61, ,K,,
,K) E 22((2+11)
Hessian in the introduced notation. function F as
With the above introduce notation, we can express the
F(, = F(z) Ex [LSE:
- - b(X)) ( (c. z)
That is, F is obtained from the LSSE,3 by wise affin transformation of the coordinates plus linear term. Chain rule yields the following expressions for the Hessian F:
F²F(=) = Ex A(X) T (ASSE((((X -(ai===bxxxxx)) ((X))
Bounding the operator norm of Hessian of F. upper bound on the operator (spectral) norm of the Hessian of F. Using the Jensen's inequality and the fact that the operator norm subordinate, we deduce that
conclude the proof, we provide uniform
= [x A(X)
22 (S 6(x)) (X)))(()) llop
E x
|
2 LSE
b(X)) [|ap]
E
x ||A(X)
-(x)) b(x)) |A(x)
Lemma F.2, implies that | LSE, (A(X)= b( x)) llop < 8 almost surely and for all z. Thus, remains to bound Ex Ax||AA (AX) "block-wise"
()) [| to conclude the proof. To this end, consider a vector u, expressed
(nd L13 LK
E 22(22111)
W
L.K:
LI:
LLD
del
def
def 4
del
16

---

Using the definition of the operator norm and the expression for ( we deduce that
Ex || (X))
Ex
sup || 3=1
(A(X))l3
= Ex sup
Σ
u/ x(x)))²
||u| 2=1
< 2Ex [|t(())]] 11
(11x2113 EE[L]
|| 11a))1])
sup 1
where the last inequality combines the Cauchy-Schwand inequality and the fact that || w/ % 2(110: [2 ( for all v, E mR The proof concluded using Lemma F.4 bound Ex [|t(X) (X)
Lemma B.1 (Price of discretization). Let Assumption 3.1 be satisfied. Let B3 B > D.N. Consider
R
def
inf I.Rd +R
B(h(x) - ((x))) sup P(h <t|S= s) P(h(X) < < E,/2, sER
Vs E [K] E
Then, it holds that
4B
log(2L +
R( & R
+
L
L B
Proof. Let assume that R (X) (X)) for some ht Rd - [[ B). If is not the case, the standard argument based on the minimizing sequence yields the same result.
Consider an operator TI, which maps a deterministic classifier h IR [[B,, B, B] onto a determinis- tic classifier (h) Rd + V2. which is defined point- mint follows
(T)()))))) BB Va Rd
where [a] is the closest integer smaller equal I in absolute value. Notice, that for any E b 1) and any x E Rd, we have
{B (Tz(h'))))= L = (x(x) E
[B (L+1)B L
L
Moreover,
(h))))((z)=
+ (x)x= = B.
Since h* satisfies (s/2)- faimnes constraints, one checks that for all l [L] [K]
4. (T(),)")) & E..
That is, Th()t* is feasible for the problem in (4). Therefore, Lemma 3.3 implies that
R( < R(Tz(h+)) + (2g(2[++1) Furthermore, since (T)(h))(m)) - (x)) < 1/L and (n)x=) -('=))-((a)))) < 2B, we have
8
4B 1
( (x(1))(())²² R(h")
L
I2
The proof is concluded.
17

---

Algorithm 2: AC-SA(F, wu, He M,T)
1: Input: function F; initial vector wo: parameters μı, M > O; number of iterations >> 1
2: wi Wo
3: for t == 1 to T do
4: sample new 2 independently from the past
5: a1 ++1
6: "t 1(t+1)
4M
wi d (1-ax)utt)) w (e(1-aaf)
ae((1-as)ut Wi-1
7:
++(1-a))
8:
wt Projw 7
(1-o))tt w
anp wo pt
V (uo( 2)
9:
wi
w 04 (1 04) w
10: end for
11: return wi
C Additional details on the algorithm
In this part of the appendix, we provide the analysis for the proposed algorithm. First, we introduce required notation and recall result of Foster et al. (2019), who provided an algorithm for convex stochastic optimization. The provided algorithm is refined version of the SDG3 algorithm of Allen-Zhu (2021). We note that Foster et al. (2019) give control of the expected norm of a gradient, while we require a control of the expected squared norm of the gradient mapping. We introduce projection to the algorithm of Foster et al. (2019) based on the original algorithm of Ghadimi and Lan (2012) and provide control of the expected squared norm of the gradient mapping of the final estimated solution.
The setup and notation.
Consider f IRd x Z + IR, such that + f(w,2) is convex for each Z. Let W C R be closed convex set. Let
F(w) def f f(w,2)dP(()
for some probability distribution on Z. In what follows, we assume that
w E arg min F(w)
wEW
always exists.
Assumption C.1. We assume that F is M-soooth and the variance of V wwf 2) is bounded. That is, for some M > and a > 0
Vw, w' E W
[VF(w) - VF(w")] < M w| ww'l and
/ [V vF dP(x) < o².
Vw W
Let us also define gradient mapping as
GF.((w) del w W
with
W4 E arg min w W'EW
(VF(w)), w²) + 2a
|| - wol²
Let Projw (.) be the Euclidean projection onto closed convex W.
C.1 Some known results.
We start by introducing the original AC-SA algorithm of Ghadimi and Lan (2012) and recall some of their results for the sake of completeness.
18

---

Algorithm 3: AC-SA (F, wo, H4 M,
1: Input: function F; initial vector wo: parameters M > O; number of iterations > 1
2: wi AC-SA(F; wo: p, M,, 4)
3: u2 f AC-SA(F; w 14 M,
4: return 272
Algorithm 4:
wo, μ4 M,T)
1: Input: function F; initial vector we: parameters 0 < μ & M; number of iterations
T Ω
M. log2
M
2: [w)) + Fww)
+ 1|00 woll ; f- wo: f
3: for 1o J = log M
do
4: W0 AC-SA 3 (FU 1 2(M + 11); F)
5: M1j + 21--11
6: F()(w) del F F(i-1) (w) + Mi w - -w= 1
7: end for
8: return JJ
Theorem C.1. (Ghadimi and Lan, 2012, Proposition 9) Let w² arg min wew F(w), wh W starting vector. If F is strongly convex and 2 1 then with
2 and "t
4M
1>>
1+1
+(t+1)'
AC-SA(F, wo, M,,M,,7 T), defined in Algorithm 2, outputs wT satisfying
2M Uu0
w
8g
E[F(ūr)) )] F(w")
T2
μT
Foster et al. (2019) propose another version of AC-SA, called AC-SA?, which resets the stepsize halfway through the process.
Lemma C.1. (Foster et al.. 2019, Lemina 1) Let W Rd, w" E arg min wew F(w), wo E Rd starting vector. If f > 0, M > 0 and > 1 then A (F, wo, p. M, M))), defined in Algorithm 3, outputs to satisfying
128M Wwo-- w
256
16o²
B) - F(w")= <
nT
1T
nT
Remark C.1. Foster et al. (2019) do not consider constrained optimization throughout their work. However, the proof of Lemma C. follows analogous arguments.
Foster et al. (2019) also introduce refined version of algorithm SCD3 of Allen-Zi -hu (2021).
In what follows, will show that Algorithm 4, after T evaluations of the stochastic gradient, produces point / such that E rr (1))l controlled. This a, rather mild, extension Foster al. (2019) and Allen-Zhu (2021).
C.2 Control of the expected squared norm
Most the proof techniques are already present the original contribution of Allen-Zhu (2021) and Foster et al. (2019), slightly extend their proof, introducing modifications related to the control of the squared norm and the projection step. For some J > 1. to be fixed later on, introduce
J w
Fu(w) def F(w))
Σ j=1
Mj
S and wn E arg min Fa(w).
(22)
wEW
19

---

By construction, Fi is j def Ej=1 strsngyy convex and (M + -i)-smooth. Let us also define F(0) def F'w) and F def f(i1)) (w) + _ - "v,-w, for j = 1.2.....J..
J. We will use the
following results of Allen-Zhu (2021).
Lemma C.2. (Allen-Zhu, 2021, Lemma 2.3) Let F be an M-smooth and p--ttronly convex function. Let w, w' E W and w
F.,(())) For any (0, M
we have
F(w') > F(w*)=+ + (G (w), w' - ww)+ + a G (w) 2
M 1|w wll 2
Lemma C.3. (Allen-Zhu, 2021, Lemma 5.1) Consider Fp and w as defined in (22) and w E W.
For any a E (0.mta] we have
(G)a(w)]
&
Σ My m e0,l + +
Claim C.I. (Allen-Zhu, 2021, Claim 6.2) Suppose for every j = 1.....J J the iterates Wy of Algorithm 4 satisfy
E p (wo) - FD- (ww & 6g where w E arg min ((
then,
(a) for every j 2 1 we have E [0, - wn w-]111?
< E Wij - 1|
26
(b) for every j > we have E [[| wr - un; I11 <
|| [0, 20 w3]1²]
$ 6 a/z
(c) if p. = 2p for all j > 1 we have E
E/= My 1100, will & < Voply.
In addition to Claim C.I, we prove the following lemma.
Lemma C.4. Suppose for every j = 1,...,JJ J, M4g
-215-11 and the iterates w, of Algorithm 4 satisfy
E p 1) (ūr;) p(-11) (w]_1) < 8, where w E arg min (wi)
then,
)
E
Σ ng 1/w3
< 16. Σ 1168-
Proof. Let P3 def El Me || will. yielding that Py Σ)= Pÿ-1), with the agreement
that Pa = O. Cauchy-Schward inequality gives
P3- = E(..-Pp-1))
<
((,
(23)
1=1
j=1
Since P, is non non-decreasing, to bound the above quantity, it suffices to bound each increment of the
form P. PJ-1- One can write
(a) Mi ||:0
P3 - P3-1
-,,ll +
Me ( - wi.ll ||
-w: 1
1=1
(6)
1-11
< 14 |00 wلحl +
Σ Ht
|1003 w0i-1l
(
< 15(2 : + ||
+ |w3 - i;,1),
20

---

where (a) follows from the definition of Py. (b) from reverse triangle inequality and (c) uses triangle inequality and the fact that E Mr E M4 μj 241-1- Therefore, using the fact that (a + 6)² < 2a² + 2b², we deduce from the above that
u3,l² (P) P-1) < 2p w3 -0,1"= + || - =
Taking the expectation and applying Claim (a) and Claim C.) the latter is bounded as
e/ 12 B - w, 11 < 8u} 81 + +2n 26,
E [ee [ - P--)) < B
16
HJ Mÿ-1
(24)
Plugging (24) into (23) yields the claimed bound.
Remark C.2. Notice, that in Algorithm 4 apply SC- to F(-1) with starting point ún-1 and j-1 Mr < 2M - smooth and jfj1- -tttongly convex, applying
T iterations. Since F(511) M 2
Lemma C.I and Claim C. (bb), we gel [FU-1) (mz) - Fū-1) (00 < 83 and
8j 128 E ū0 - w 9-1 11
256(2M)o²
16o²
M4 (T/1(
(T/1(
(1-1(T/J)
29 + (T/1( (T/13 PJ-1(T/J)*
2o
2¹
We are in position to prove the main ingredient of this section. Theorem C.2 (Control of the expected squared norm), Let w E arg min wew F(w), wo E Rd a starting vector. When μ E (0, M] and T > 211/4
log, } then for a = 2042 with
J = loga M # SCD3-refined F. wo M, T) oulputs ip satisfying
E [|GFa
3 22
log2
M
24²²
|1200 w/ 1
Tt
3 227 Mo²
M
3
0z
M
logz
+
logz
3
NT3
1
T
Proof. Part At first, let us assume that is sto-srongly convex. Since the definition of F
satisfies the definition given in (22) with J - 1, applying Lemma C.3 and using the fact that (a + b)2 & 2a² + 212 we get that for any E (0, + Ej=1 + )))))))) -"]. it holds that
J-1
[ & E
3 3||GGuu PPGpuu- ( (ا,)))
Σ
My |wj- - 20;
Σ Mg || Tا,|ه )}
2E
9 9 p()
(w:) (
+
(25)
Note, that due to definition of μýj we have E/=1 Hj < M, thus, the derived inequality holds for any E (0, (2M)-1] C (o, (M + E (3) - Lemma C.4 provides a control of the second term of
J-1
(25). To control the first term, let us apply Lemma C.2 with F(J-1) and w w w. getting F(J-1) F()-)( & (())))(0)) - F()-1) (w Vo E (0, 3. Meaning, that ||G p(Guu- , (1)) < 261, Let recall, that J logg M and ja = pa
| [GGu-n,(( < (w,)
2' & .M & 2p.. Hence, choosing zps
1 and substituting the derived bound into (25),
deduce that
J-1 368, -2 Gr (w)))) <
E
- 1=1
Σ ujd < 144. Σ 155g.
a
3=1
21

---

Now, let us substitute the bound on 6, from Remark C.2 and replicate the steps of Foster et al. (2019) to control the above. We get
Mj0z &
2 2
W0 wn
n Mo² Po(T/J}a
0²0²
+
Σ
2
M2
Mo²
o
(T/J)a
(T/J)
(5-1(T/J)²
1T-1(T/J}²
(T/J)
1=1
1=2
2 M²
1w00
w 1|? Jz
2 Mo²j J
Σ
1
2²
2 M
Σ 83-1
+
T
1oT
25-1
T
T
My-1
M2 2
Wu
2 J
2 J
2
M J
Σ
T4
PoTs
T
T4
where the last inequality comes from the facts that Σj - < and Σj=
<
4
<
Σj= Mzō5. Rearranging the terms and multiplying both sides by 144J, we get Hb
1
9
22
Ww - w' 11 js
2 Mo²
2002
144J
Σ 155
<
+
M T
T
MOT3
T
j=1
Choosing T >>2 2
M Me
ensures that
2. Finally, substituting the derived bounds and
1
J 2574
the value of J = |l08 we conclude that
9 9.2 22 w
w011
M
9 4-24MM²
Ma²
M
9-
1.220
M
E ([Gr((W)))1""
log2
+
logz
+
log2
74
P4
To
140
T
(26)
Part II. When F is not strongly convex, let (w) def F(w) + うタG ||
woll wwoll
and w
arg min (F](.) Applying (26) and Lemma C.3 with J = 1 and w = wp. we get
E (
<
3 M2
log2
5 M
+22²²
|| w ||
T
3
217 Mo²
M
3
221
M
log2
+
log2
HT
T
Since 1/2 1100 woll2 - 11 m/= wol| || (ww =(w*))) + (F(w)) Fx(ww))) > 0, then
| woll? & I|w0 wol' 2 The proof is concluded.
Remark C.3. Notice, that in Algorithm 4 we apply AC- SA to FG-1) with starting point 6ر and T/J iterations. Since FÚ-1) is M Σ Et=1 Mt & 2M R.M-smon smooth and 1j-1- strongly convex, applying Lemma C.1 and Claim C.1(b), we get F
w FG-1) (w) < 8j and
2(2M) i
w
802
4M +
802
8, <
(T/J)2
P (T/)
(T/r²
(T-1(T/J)
Theorem C.3 (Control of the expected squared norm). Let w E arg min NeW F(w), wo Rd 1
a starting vector. When j E (0 and T > /v A
H logz then for 20+2 with
log, M p SCD3-refèned(F: wos H4 M, T) with AC-St SA outputs w satisfying
E [[))=((0))3] &
M M
log3
+ 2p²
|lw0 w011 + T
31211 2
log
3 M
T
4
22

---

j3 Proof. Part I. At first, let us assume that F is po-strongly convex. Applying Lemma C.3 and using the fact that (a + b)² 2a² + 2b2, we get
Σ My |w - 21
E [
& E
+
Mg [|w3-1 26; )
2E 9 [[GpveJ)) (
(27)
Lemma C.4 provides control of the second term of the above inequality. To control the first term, let us apply Lemma C.2 with fo(-11) and w = w' = w. getting Gru-n, ( < (())))(()))) - (()) & ( F(J-)) Va E (0, 3 Meaning, that M and μuf 2 po < M 2p, Hence, (Gru-n,((s))) < 25,, Let recall, that J loga nо
1 and substituting the derived bound into (27), we deduce that choosing a 4ps
J-1
368J +3((J 1) 1)
E [Gaa(())))
ngd & 144J Σ 1y68.
a
J=1
Let us substitute the bound on 6, from Remark C.2 to control the above. We get
Σ m, < 4M Ww0 (T/J)²
w'I" m
80²M1 (T/J)HO
8M8 (T/J)²
16o²
Σ
(T/J)
1=1
3=2
8M μm wwo
320
+
8MJ²
Σ
85-1
T2
T
j=2
8M |1200 - w01 J²
320 J²
8MJ²
Mg py 1
T2
T
NoT
8M
|/w0
w
w01l"
112
J²
320²-²² J²
8MJ²
M5dg
T2
T
NoT
Rearranging the terms and multiplying both sides by 144J, we get
1152
MHo 1w0
w0
j3
144J
1
<
+
1
SMJ No
T
T
F=1
Choosing T > 4J /
/
M
ensures that
< 2. Finally, substituting the derived bounds and the
na
value of J = 1ogg
Mi
we conclude that
po
2304 M
M ||woo w=11 T
40
E
| F (+))
<
(28)
po
T
Part II. When F is not strongly convex, let (w) del F(w) + b/4 w|w woll and w
arg min (F)(w)). Applying (26) and Lemma C.3 with J = and 10 wp, we get
E [|G ( [3] &
(322 Mp
log2
M
||uno - will /100-w;'' + T + 2/0²)
3'22102 M
log
T2
/
Since い Ilw0 woll= 3 I/
woll
(F, (wx) F(wx*) + (F(w)) F, F₂ > 0, then
w woll? < I|w0 wall The proof is concluded.
23

---

D Proofs of statistical guarantees
In order derive statistical guarantees for the proposed method, we are going instantiate the extension provided in the previous appendix.
Proof of Theorem 5.1. Let instantiate Theorem C.2. According to Lemma 4.1 and Lemma 3.4 T
have that 6² 2 Σ SE]S]
1-Px and M Bo8.. Setring
/
llgg I and μ 02/ / ensures that
Ps
& M and that T > 4V large enough absolute constant, the conditions of Theorem C.2 are satisfied for the function F.
M logg M
logg T logg llgg
T
VT > 2. For T larger than some
Fairness guarantee. Theorem C.2 yields
E [(Irra((D)1
0 3126
log2
64 64 T
T
+
20
log T
IIAA', v1
T
log2? T
3-2
T
34211 0²
T
+
log2
log2
T 1og2
T
64 log T
64 log2 2
T
Therefore, have shown that
22
T I(A,,
(29)
Hence, the first part of Lemma 3.5 implies the fairness guarantee.
Fairness guarantee with AC-SA. Theorem C.3 yields
34290
T
2
E [Gr.
<
log
+
log3
|(A,, v*)1²²
T2
T 64 logg
72
312 o²
T
log
T
64 64
Therefore, we have shown that
E
(A v)
<
1 of -IIa
(30)
T
Hence, the first part of Lemma 3.5 implics the fairness guarantee. Risk guarantee. The second part of Lemma 3.5 states that
R(TA.V) R(TA..V.) < (1 O + ao + ||||| / 2(2 2222
Ga(A, f) |
log(2L + 1)
Taking the expectation and applying the
inequality, we obtain
E [((TAV)] R( &
( || ||a ao + ||E|| 2222 + 1)
E (2,
v 19]
log(2L +1)
Recalling the value of 2 & 2M from Theorems C.2 and C.3 and the fact that M Bo
get
2B0 Finally, applying (29)-(30) and setting L VT, we obtain
E R(
R((TA
σ v*)I)
EE [[( V)
1 To
||E||
log(vT)
VT
1
VT
T
+
VT
Above combined with Lemma B.1 yields the claimed bound.
24

---

E
Unknown 7) and т
In this section consider the case, when 17 and unknown and estimated by and f. We denote
by
t(x)
def
1
F(o) and Fz( def (f(z) _ We consider the plug-in version of (5), defined as
LSEA ((A:-1r -
xxx())
Σ Ae + ve, e).. (PLSE)
min
Ex
A.V
Let us denote by F, the objective function of the above problem and introduce
(T( def Ex
Σ
((() X) + 1 v x))
EEILI
The gradient of F is given for any A, > by
Nea F(A, V) Ex de B ((2e ve, t(X)) Fe (x) ('= (x(
tEs:
(31)
VuG F(A, V) -xx fae (3 ((der vu, 1 f(X)) Fe (x) p= Pio (x) +6s
for E [1], E [K] Let us denote by G(A, V) the stochastic gradient of F, defined as
TAc. (A, V) az (08(8(( (8(( ve, B(x)) (x((x)) 7
Tx(X) Eer
P==L) vo, f(x)) Fer (x))
(32)
Ten. (A, V) = - (3 (0((Ar- ve,
L
(x) t
e==
for X Fx and E [L], [K]. We also define, by the analogy with the main body, a family of plug-in estimators
i x) del -oz or (B(c i(x)) - P-- {
A,V
(33)
Our goal is to derive analogous optimization results for the new plug-in objective. Inspecting the proofs of Lemma 4.1 and Lemma 3.4, which bound variance of and the Lipschitz constant of the gradient respectively, we observe that those proof' only depend on the nature of via Lemma F.4. In particular, the key quantity to control is
Ex (p. (x))²
2 Σ
SE(K]
Before, when assumed the perfect knowledge of the above was controlled by the Shatia-Davis inequality, leveraging the fact that variance of T, (X) appears in the numerator. It is no longer the case here. However, if one can build calibrated estimators, that is, estimators for which Ex (+. (X)) = P.. the same machinery is applicable. In any case, even without requiring calibrated predictions, one can have a reasonable control of σ² building sufficiently accurate estimator f..
That being said, results of Lemma 4.1 and Lemma 3.4 generalize line-by-line replacing o² by 0 and give
sup Ex ( - VAVÊ V,
(A.) x²
and sup //V2 V) & 3002 A
Moreover, the result of Lemma F.5 generalizes as well and gives supA. V00
VA v) 6
As in (19), we can show that
(-vPia. < & (A. v|
AA, VA,V>0 0,
(34)
where the gradient mapping Gp,a. is defined by analogy with G. = G F.o, discussed in the main body.
Considering the SGD3 algorithm with the same choice of parameters, but replacing o² by 02, results
control of Gr (A, D
25

---

Proof of Lemma 5.1. Fix A, V > 0. To ease the notation, we write ह to denote TA.V v within this proof. Similarly to the proof of (21) from Lemma 3.5, one shows that for all A, 0
Σ
(E X 7Z. [X] -.) I(-V
Vl E [4] 8 E [K].
(EIL]SE[K]
Recalling that (), = E ( X)4 (X)] triangle's inequality combined with the above yields
E
(U.(5.)) c.) < II (-VV((A V))+1I+
Σ
(Bla(e) xx),(x) to (x))))
[E[T][E[R]
[E[T][E[K]
inequality gives
[E|T(E) - (X)I|
Σ E
# x)2
f. xx
[E[L]E[[K]
sE[K]
REIL]
Since EeELy #([] X)= then EeELl #(e xx2 & 1. Thus, have shown that
Σ ()( Es) < <-)
+ /|
x(2)
[E[T]SE[R]
We conclude using (34).
Proof of Lemma 5.2. Fix A, V > 0. To ease the notation, we write del R..V and n del
within this proof.
As in the second part of the proof of Lemma 3.5, we have
R (T) + F(A, V) & (II(A, V)II aõ + +allell 2(22+ | (A, (35)
Furthermore, since V (SSE(()li = 1, we have
(re(X)) - (x()) + | - vell(((() x
|FA V) F(A, V) < E max
[ELL]
and RT) - [T) < E[maxeejy ( - with (35), gives
The last two displays combined
+(A)) V) & E max {lr(x)) -x( ( + | - -1 8 x(x) m1
FE|T.
+ (I(A,, V)Il + +0 a 22(2L (A,,
(A, (A,))
Observe that minA. 30 F(A, V) Rg( Using triangle's inequality and the fact that max |Ae- & 22 V) we conclude recalling that R(T)+ log(2L+1) for any randomized prediction function.
3 > R₂(TT) > R(x)
26

---

F Auxilliary results
In this appendix, we collect some standard auxiliary results, that are used to derive main claims of the paper.
Lemma F.1 (Boyd and Vandenberghe (2004)). It holds that
(SE = max (w. p) 3 [VD) PEA
where A is the probability simplex in I and (p) = = P. log(p:). Furthermore, - (p) [0, log(m)) and the optimum in the above optimization problem is achieved at p' = ((w)).
Lemma F.2 (Gao and Pavel (2017)). Let (ar,".. am) and O. Define log-sun-exp and softmax functions respectively as
(a) log Σ Eexp(Bus) and and (BB))) exp(Ba,)
j E [m]
ii=1 exp(Bas)
The LSE property is as follows
am + log(m)
max(a1, ... amm & La) & maxfa1,
B
Moreover, a (Ba)= (LSEg(a), and (Ba) is B-Lipschitz
Lemma F3 (Bhatia and Davis (2000)). Let and M be the lower and upper bounds, respectively, for a set of real numbers 01," ... an with a particular probability distribution. Let μ. and o² be respectively the expected value and the variance of this distribution. Then the Bhatia -Davis inequality states:
²² & (M - (1) - m))
Lemma F.4. It holds that
Ex
Σ (X)
1 Ps
Ps
KE[K]
sE|K]
where tx(x) = Ta(x)
Proof. We have
Ps and 0 < To (X) < 1 almost surely. Using Bhatia-Davis inequality
written in Lemma F.3, deduce that
Ex
Σ (x)
Σ KE[K]
Var Tx(X)
Σ
Var (Tx(X)) &
- Ps
Ps
P2
Ps
[E|K]
KE[K]
<E[K]
The proof is concluded.
Lemma F.S. Let o² del
2
2.EKK]
I-B, It holds that [V.v < 12 ||=|| Pe
Proof. By Jensen's inequality
VAA.F(AA VII [Ex(oAv Exxllov(X)111
Recalling the definition of 9A. given in (11), we have
(x]] Ex Σ (x)())(()++))) (- + +²)
[E[T]]E[K]
2Ex
(o(0)(() +&,)) < 0² + 2(2L + 1) ||= [E[L]&E[K]
Σ
where the last inequality comes from the proof of Lemma 4.1.
The proof is concluded.
27

---

G Additional details on experiments
Evaluation measures.
We use Dust ((0r), s/ 10 collect the following statistics of any
(randomized) prediction π
R()) def
1 3/1²² ( x!),
m
[ T(d x!)
(T)
del
sup
T Fd
- =
Σ
ER
m
which correspond to the empirical risk and the empirical groep-wise unfairness quantified by the Kolmogorov- -miimov distance of randomized. We note that our classifier is supported on a finite grid, thus all the integrals involved transform into weighted sums.
Agarwal al. (2019) build multi-class classifiers hy R2 + O. where θ is some finite grid over I and k ,,..,, K, that come with weights (Wi,..., wx) T such that wg e and _k=1 Wk 1. Then, they build a randomized classifier π such that supp(T((- æ)) = Q and for each A E θ
P( = x x)
Σ wgI[(h(() 0}
Thus, integrals appearing in R and Ü, reduced to finite sums for both methods.
Additional details on the experiments on Communities and Crime and Law School datasets. Communities and Crime dataset has 1994 instances, however we use 1984 examples with 120 features after preprocessing. Law School dataset has 20649 instances, thus we use a smaller sub-sample of 2000 points with features after preprocessing.
We take 21, 5, the sets of unfairness thresholds 16, 32, 128, 512] for Communities and Crime dataset, and {0, 1, 4, 5, 6, 8, 16, 32, 64, 128} for Law School dataset. We train Communities and Crime dataset for N=15000 iterations and Law School dataset for N=5000 iterations for each pair of epsilons. We use parameters L VT, 3 = vT log VT and B for both datasets. We repeat the aforementioned pipeline 10 times to ensure more reliable statistical summary.
where I
Discussion on other algorithms. We conduct additional experiments to observe the behaviors of the more straightforward algorithms discussed in Appendix C. We illustrate the comparison in Figure 3. In conclusion, all of the algorithms perform similarly in the middle to high unfairness regime, while those based on SCD3 are more stable in the low unfaimesss (high fairness) regime.
Figure 3: Comparison of SDG, ACSA, ACSA2, SDG3+ACSA and SDG3+ACSA2 algorithms on Communi- tites and Crime and Law School datasets.
Additional experiments on Adult dataset. We conduct further experiments on Adult dataset (Lichman (2013)). Classically, Adul is used for classification, however we use it to predict individual's age scale of 0 to 100, normalized to J0, 1]. We factor in between male and female individuals. Adult dataset has 48842 instances, however we clean and preprocess it, and use smaller sub-sample of 2000 points with 8 features throughout our experiments.
sensitive attribute, distinguishing
The pipleline of the experiments is the same as the one for Law School and Communities and Crime datasets in the main body. We randomly split the data into training, unlabeled and testing sets
28

---

po-psso
ADW-1
ADW-2
communities
5.89 0.47
378.39 + 263.77
199.05 + 161.18
law school
0.78 + 0.08
240.53 = 178.68
136.3 = 96. 73 96.78 + 61.35
adult
3.7 0.34
174.57 + 91.7
Table 1: The average training time (in seconds) for one threshold.
$i 8 to train a base (unfair) regressor to estimate 1 and to train classifier estimate т. We use simple LinearRegression and LogisticRegression from scikit-learn for training the regressor and the classifier, and give (x) for N = 10000 iterations. We use Drest (ar,, s,, v1) }mm to collect statistics. We take the sets of unfairness thresholds ((2-1,2-")ee) where I = {0, 1,2, 4, 5, 6, 16, 32, 64, ]28} for. As in the experiments in the main body, we set VT, 3 = VT/ log VT and = 1. We repeat the pipeline 10 times.
with proportions of 0.4 x 0.4 x 0.2. We use Dtrain =
them to Algorithm with Dunlabeled
We compare our method with the ADW method. We train ADW 2 times: we use Drrain and D Dunlabeled as training set for ADW-1, whereas for ADW-2 we use only Drrain We take the set {(2 2 k)))) where I = 21, 4, 8, 16} as unfairness thresholds for training both datasets. We train ADW-1 and ADW-2 for each pair of epsilons for 10 times.
In Figure 4 we illustrate the convergence of the risk and the unfaimess for convergence for (2 8 2,2 2-2) unfairness threshold. We also illustrate the comparison our model with ADW-1, ADW-2 and base models.
ad.it
Lef
CD
6000
num of Rorot ons
num of Iterations
untaiiness
Figure 4: Experiment on Adult dataset: risk convergence, unfaireess convergence and comparison with ADW.
Running time. Additional details about training time for Communities and Crime, Law School and Adult datasets are presented in Table
Additional experiments on synthetic dataset. We conduct an additional experiment to demon- strate the results of Algorithm 1 in the case of multiple sensitive attributes. We generate synthetic
dataset D., = (X,, St, yo " of n = 2000 points, where (X,) = (X X,2, X22)² ~ NN(0, 1). We if X, < 0, S, 2 X,1 0.7 and S, 4 if X₁1 > -0.7. For [n]. we generate y 42 Xy X where & (E.) (O 1). We split D,, into train, unlabeled and test datasets with proportions of 0.4 x 0.4 x 0.2. We use (Xtrinn Virain) to train the base estimator, (X (Xtrain> Sivain) to train the classifier and X Xantab to train the fair regression model. We evaluate our model on test dataset. In Figure 5 we illustrate the distributions of the predictions (scaled to [-1, 1)) of the fair and base models.
choose S. 0 Xn1 0.7,,
This experiment is for visual representation of the Algorithm I in the case of multiple sensitive attributes, thus we do not collect further statistics.
29

---

5-00
30-
5-2.0
25
5-30
5030
20-
15
15-
03
Figure 5: The distributions of the (scaled) predictions of the fair and base models.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We translate the fairness problem to a smooth and convex problem as stated in Lemma 3.1. Theorem 5.1 gives the main theoretical control on faimess and risk and Section illustrates the performance of the method and a comparison to state-of-the-ar method.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
A limitation section is included in the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: We extensively developed our methodology in the main body and decided to postpone all the proofs to the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the experiments are reproducible. We provide the link to the source code in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
32

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the datasets that are used are benchmark datasets. Moreover, as previously mentioned, we point to a GitHub link in Section to make our experiments reproducible.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
oeeeionoollooooo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /tpps.ccpppiiiiiiiieeipepppppppp wwtppcccccc//cccccccccccccc.ctlt wtwp///gg///eeeeeeeeeeceeeeseeee /Ctps//ooeSSueeeeeee seaibbmmsssooPP ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section gives all necessary information on the datasets splits and on the tuning parameters.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All our experiments include and illustrate the standard deviations reported over 10 repetitions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We reported all this information footnote in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /tttps:/nnuurppee http://uurrpsccccpuuubee/s http:public/thhcccuiieeeeeee
Answer: [Yes]
Justification: We only used open source data and codes. Therefore, we believe that there are no issues form the ethical point view.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The contribution falls within the scope of fairness and the goal is to mitigate bias in decision making. The paper focus on the general notion of approximate fairness e-fairness. While approximate fairness is desired in general, this setting allows for control of the amount of unfairness that we allow or accept. From this point of view, providing the control on the faimess to some user may generate ethical issues.
Justification:
34

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
All the datasets are open source and widely used by the fairness community.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provided references for the two datasets we are using. In addition, we also referred the papers that we considered for a numerical comparison.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ condaataeet has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The main contribution is a novel approach for imposing demographic parity fairness in the unawareness case. This is challenging problem for which we spend the whole core of the paper to explain the method and its new considerations.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper considered public data that does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [No]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "22cfiE1Ahr", "reviewer": "Reviewer_3wik", "summary": "This paper presents a post-processing algorithm designed to enforce demographic parity in regression tasks without access to sensitive attributes during inference.", "questions": "The paper focuses on demographic parity as a fairness metric. Are there impacts on other fairness metrics like Equalized Odds and Equal Opportunity when using the proposed algorithm? Does it improve these metrics, or could it potentially worsen them?\n\nRegarding the risks plot in Figure 1, could you clarify its purpose given there are no comparative benchmarks provided? How should the unfairness score presented in the plot be interpreted?\n\nReference [1] addresses a similar topic with a minimax approach. Is this minimax result applicable or relevant to the methodology used in your paper?\n\nIn Algorithm 1, \"DP\" is mentioned in the name. Could you specify what \"DP\" stands for?\n\nThe algorithm \"fairname\" appears in line 305 without a prior definition. Could you explain what this term means within the context of your study?\n\n[1]  Fukuchi, Kazuto, and Jun Sakuma. \"Demographic parity constrained minimax optimal regression under linear model.\" Advances in Neural Information Processing Systems 36 (2024).", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "The solution is versatile solution for enforcing demographic parity as it can be applied on different optimizers.\n\nThe paper provides a rigorous theoretical foundation to quantify the risk.\n\nThe fairness problem is relevant.", "weaknesses": "While the algorithm presented in the paper appears promising, its evaluation is hampered by the presentation style, which tends to obscure clarity. Technical details such as the reliance on discretization and sophisticated methods for controlling the gradient norm are emphasized in the abstract, which could be streamlined to focus on broader impacts and significance instead. \n\nThe paper contains numerous remarks that disrupt the flow of discussion; for instance, Remark 2.1 seems tangential and could be relegated to an appendix or omitted entirely. Other generalizations and discussions, such as those in Remark 2.2 and the paragraph on line 304, should be consolidated and presented at the end of the paper to maintain focus. The 'abuses notation' in Remark 3.1 could be resolved by providing clear definitions Comparisons with other literature are inconsistently integrated within the text, appearing at disparate locations such as lines 56, 228, and 334, which could be better organized to aid in comparative analysis and enhance readability.\n\nThere is excessive use of sub-titles or mini-sections. Some of these sections are notably brief (line 176, for example), where the short content under each title does not justify the need for a separate heading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in reviewing our work, but we respectfully disagree  with the evaluation.\n\n*Weaknesses*\n\nThe reviewer has criticized several stylistic choices in our paper. While we recognize that these choices may not align with the reviewer's preferences, it is worth noting that neither of the other two reviewers raised similar concerns. Our approach is driven by theory and is based on a carefully developed methodology rooted in mathematical reasoning, rather than common sense. Given this theoretical foundation, we believe our stylistic choices are justified and aid the reader in understanding our thought process. Below, we address the specific stylistic comments raised:\n\n\n1.  *\"Remark 2.1\"*. We disagree with the assessment that *Remark 2.1* is tangential. On the contrary, clearly defining the joint distribution of every random variable involved is crucial for understanding the problem. Including *Remark 2.1* helps prevent potential misconceptions, such as assuming that $\\hat{Y} = Y$ is a valid prediction function for any distribution of $(X, S, Y)$. *Remark 2.1* explicitly clarifies that $\\hat{Y} = Y$ is not a valid prediction function unless $Y$ is measurable with respect to $X$.\n\n2. *\"Remark 2.2\"*. *Remark 2.2* anticipates potential questions from readers about possible extensions of our methodology. While we do not insist on keeping this remark in the main body, we believe it could be useful for some readers.\n\n3. *\"Remark 3.1\"*.  We do not see any issue in abuse of notation as it is extremely common in mathematical science. Yet, we find it equally important to be extremely clear when such an abuse happens so that the reader is aware and could easily understand the logic behind our choice. The reviewer suggests providing clear definitions, but we would appreciate more specific guidance: which quantities are not clearly defined in our paper?\n\n4. *\"There is excessive use of sub-titles or mini-sections\"*. This is a stylistic choice we made to clarify the purpose of each paragraph. We believe it helps in setting the context clearly. We prefer to keep this as is unless the reviewer can provide a clearly better alternative.\n\n*Questions*\n\n**Q1:** The paper focuses on demographic parity as a fairness metric. Are there impacts on other fairness metrics like Equalized Odds and Equal Opportunity when using the proposed algorithm? Does it improve these metrics, or could it potentially worsen them?\n\n**A1:** Equalized Odds and Equal Opportunity typically refer to fairness conditions in binary classification, while our work addresses fairness in the context of regression. While extensions of these notions to regression are possible, our approach focuses on demographic parity. As such, it might improve, worsen, or maintain fairness under other definitions. Since we have not claimed to address all definitions of fairness simultaneously, studying the trade-offs between different fairness notions is beyond the scope of this work. However, we will include a discussion emphasizing that our algorithm is tailored for a specific fairness definition as it is highlighted by the title.\n\n**Q2:** Regarding the risks plot in *Figure 1*, could you clarify its purpose given there are no comparative benchmarks provided? How should the unfairness score presented in the plot be interpreted? \n\n**A2:** The purpose of *Figure 1* is to illustrate the post-processing dynamics of our proposed method, not to compare it with other algorithms, which are based on different approaches. A comparison with other algorithms is shown in *Figure 2*. Additional details on the implementation are provided in *Appendix G*, and the code is available via the link provided in the paper.\n\n**Q3:** Reference [1] addresses a similar topic with a minimax approach. Is this minimax result applicable or relevant to the methodology used in your paper?\n\n**A3:**  The paper suggested by the reviewer has little in common with our contribution. Firstly, it deals with the scenario where sensitive attributes are available for prediction (the awareness setup) and relies on an explicit form of the optimal prediction provided by [Chzhen et al. (2020b)](https://arxiv.org/pdf/2006.07286) and by [Le Gouic et al. (2020)](https://arxiv.org/pdf/2005.11720). Such an explicit form is not yet available for regression in the unawareness setup, which remains an open question in the field. Secondly, that paper focuses exclusively on linear regression and provides a minimax statistical analysis for this case. In contrast, our work presents a versatile, theoretically grounded post-processing algorithm that can be applied to any pre-trained model in the unawareness setup for regression.\n\n**Q4:** In Algorithm 1, \"DP\" is mentioned in the name. Could you specify what \"DP\" stands for?\n\n**A4:** DP in the name of *Algorithm 1* \"DP post-processing\" stands for *demographic parity*. We have indeed not introduced this term in the main body and will include it in the revision.\n\n**Q5:** The algorithm \"fairname\" appears in line 305 without a prior definition. Could you explain what this term means within the context of your study?\n\n**A5:** The name \"fairname\" in $\\texttt{FairName}(L, T, \\beta, \\boldsymbol{p}, B, \\hat\\eta, \\hat{\\boldsymbol{\\tau}})$ in the section of extension to unknown $\\eta$ and $\\tau$ is an unfortunate typo. It should be  $\\texttt{DP post-processing}$ and it will be corrected upon revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "divMNSqAC8", "reviewer": "Reviewer_RqJN", "summary": "This paper proposes an algorithm that takes in an fitted regression function and a sensitive attribute predictor and output a prediction function satisfying the demographic parity constraint. It designs a smooth convex objective function with discretization to solve for a prediction function with small risk and controlled violation of the demographic parity constraint. Stochastic minimization techniques are applied to solve the proposed optimization problem and recover the statistical rate $1/\\sqrt{T}$.", "questions": "In practice, how do we pick algorithm parameters such as L, B and \\beta?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithm is supported by theoretical analysis and error bounds. The proofs are well-organized and clear to read. The algorithm deploys suitable stochastic minimization techniques to achieve statistical guarantees. Moreover, based on the experiment results, the proposed algorithm is much more computationally efficient than existing methods.", "weaknesses": "Typos: \n* falls withing -> falls within (page 2)\n* statisitcal properties -> statistical properties (page 5)\n* out approach -> our approach (page 7)\n* phenomenons -> phenomena (page 7)\n* outperfomce -> outperform (page 8)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for the careful reading and evaluation. We agree with the feedback and will correct the suggested typos in the revision. We will also address the question raised below.\n\n**Q**: In practice, how do we pick algorithm parameters such as L, B and $\\beta$?\n\n**A**:  In practice, we normalize the target variables to the range $[-1, 1]$, so we set $B = 1$ as our default practical recommendation, which aligns with actual practice. We have found that the other hyperparameters suggested by our theory already produce good empirical results. The exact choices of these parameters are detailed in Appendix G (line 693), and, aside from some multiplicative constants, they closely follow the theoretical values. These will be the default settings in the package we plan to release.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DNQLYUVAVV", "reviewer": "Reviewer_qMMa", "summary": "This paper considers post-processing regressors to satisfy the group fairness criterion of demographic parity, in particular, under the attribute unaware setting.\n\n1. The authors begin by analyzing the constrained optimization problem (\\*) for fair post-processing, and showing in lemma 3.1 that the solution, i.e., the post-processed regressor, can be represented and parameterized by the dual variables of (\\*); and provided that the base models are accurate and (\\*) is solved to optimiality, the resulting regressor will be optimally fair.\n\n2. Then the authors discussed optimization and statistical aspects of (\\*). Specifically, the convergence rate is analyzed, as well as the conditions for non-perfect solutions to satisfy fairness, namely that the \"gradient mapping\" of (\\*) needs to be lipschitz. For this reason, the authors recommended using the SGD3 algorithm for optimizing (\\*).\n\n3. The paper closes with empirical evaluations of the proposed algorithm.", "questions": "- Does the analysis rely on properties unique to the demographic parity fairness criterion? If not, is there a path to extend to other criteria (potentially taking inspirations from [1, 2])?", "limitations": "- See weaknesses.\n- Minor, but the proposed procedure requires discretizing the support, which is a limitation; even though the reviewer is aware that, in practice, discretization helps with generalization hence gives better performing models compared to non-parametric methods [3].", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To my knowledge, this is the first paper that studies fair post-processing regressors in the attribute unaware setting.\n2. The primal-dual analysis that leads to the representation result in lemma 3.1 is interesting. Because the proposed procedure involves discretization, the formulation of (\\*) is based on the support of the regressor's output space. This is different from somewhat similar works for the classification setting [1, 2] where the optimization problem is based on the scores of the training examples (without discretization).\n3. The theoretical analysis is thorough, hence the proposed procedure is well-supported, including the choice of SGD3.\n\n[1] https://arxiv.org/pdf/2310.05725  \n[2] https://arxiv.org/pdf/2405.04025", "weaknesses": "1. Regarding lipschitzness of $F$. The reviewer feels that some discussions are curt. The authors introduced the \"gradient mapping\" $G_\\alpha$ in eq. (8), with a hyperparameter $\\alpha$. It is not mentioned: how $\\alpha$ should be chosen, in theory or in practice; how exactly SGD3 controls the norm of $G_\\alpha$ (lines 237-239) in the main body. At least a brief discussion should be included in the main body for the latter, since theorem 5.1 would depend on whether SGD3 can provably reduce this quantity.\n2. Regarding the use of SGD3, an ablation study would have been appreciated at illustrating the importance of using SGD3 over other optimizers; is it absolutely necessary? Also, could the authors discuss potential limitations with SGD3?\n3. The authors mentioned that there are several hyperparameters associated with SGD3 (line 236), and with discretization (i.e., the number of bins). But it does not seem to be discussed how these are chosen for the experiments in section 6, and whether mis-specification of these hyperparameters would impact performance.\n\n[3] https://arxiv.org/pdf/2006.07286", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful reading and fully agree with the evaluation regarding the strengths and potential directions for future investigation. We will address the questions raised below.\n\n*Weaknesses*\n\n**W1:**\n\n* Regarding lipschitzness of $F$. The reviewer feels that some discussions are curt.\n\n**A:** We will enhance our discussion to better emphasize that the smoothness properties of $F$ are controlled by the regularization parameter $\\beta$ *(Lemma 3.4)*. Our final theoretical guarantees also provide practical guidance on selecting this parameter, balancing the regularization error *(Lemma 3.3)* and ensuring the algorithm's fast convergence.\n\n* The authors introduced the \"gradient mapping\" $G_\\alpha$ in eq. (8), with a hyperparameter $\\alpha$. It is not mentioned how $\\alpha$ should be chosen, in theory or in practice.\n\n**A:** In theory, we set $\\alpha = 1/M$ and any value of $\\alpha \\leq 1/M$ would yield exactly the same result. However, the choice of $\\alpha$ is not critical for our specific problem, as the bounds on unfairness and risk are valid for any $\\alpha > 0$ (see *Lemma 3.5*, lines 203-204). In practice, there is no $\\alpha$ hyperparameter in the final implementation of SGD3 with a black-box optimizer.\n\n*  It is not mentioned how exactly SGD3 controls the norm of $G_\\alpha$ in the main body. \n\n**A:** Due to space limitations, we have provided the details of this part in the *Appendix C*. We would also like to remind that any algorithm designed to minimize the expected squared norm of the gradient mapping can be used. SGD3 is just an example that we included because it is supported by convergence rates.\n\n**W2:** \n* An ablation study would have been appreciated at illustrating the importance of using SGD3 over other optimizers; is it absolutely necessary?\n\n**A:** We conducted additional experiments to observe the behaviors of simpler algorithms. A figure that illustrates the comparison is included in the attached pdf file. In conclusion, all algorithms perform similarly in the middle to high unfairness regime, while those based on SGD3 are more stable in the low unfairness (high fairness) regime. However, since the stochastic minimization of the norm of the gradient of a convex function is a relatively niche topic, there are only a few algorithms with established convergence rates. As we aim for end-to-end guarantees, we have chosen methods based on SGD3. Nonetheless, other stochastic minimization methods could potentially perform just as well in practice.\n\n* Also, could the authors discuss potential limitations with SGD3?\n\n**A:**  The SGD3 algorithm, as described by [Allen-Zhu (2021)](https://arxiv.org/pdf/1801.02982), serves primarily as a theoretical model that highlights a unique phenomenon in stochastic convex optimization with an unconventional criterion. Between the submission and the rebuttal, we extended and simplified the theory from [Foster et al. (2019)](https://arxiv.org/pdf/1902.04686) to be applicable to our problem. This has enabled us to provide a theoretical guarantee for a simpler algorithm that combines an SGD3-like approach with accelerated stochastic gradient descent. While this improved analysis slightly enhances our fairness and risk guarantees, it does not alter the main message of the paper.\n\n**W3:** The authors mentioned that there are several hyperparameters associated with SGD3 (line 236), and with discretization (i.e., the number of bins). But it does not seem to be discussed how these are chosen for the experiments in section 6, and whether mis-specification of these hyperparameters would impact performance.\n\n**A:** In practice, we normalize the target variables to the range $[-1, 1]$, so we set $B = 1$ as our default practical recommendation, which aligns with actual practice. We have found that the other hyperparameters suggested by our theory already produce good empirical results. The exact choices of these parameters are detailed in *Appendix G* (line 693), and, aside from some multiplicative constants, they closely follow the theoretical values. These will be the default settings in the package we plan to release.\n\n*Questions*\n\n**Q:** Does the analysis rely on properties unique to the demographic parity fairness criterion? If not, is there a path to extend to other criteria (potentially taking inspirations from [1, 2])?\n\n**A:** This is an excellent question. As the reviewer may have noticed, the key feature that ensures everything works is the compatibility of the demographic parity constraint with discretization. This approach can be adapted to any other notion of fairness that is \"friendly\" to discretization. However, care must be taken when introducing new notions of fairness. The demographic parity constraint is convenient because there are always predictions that satisfy it (e.g., constants), but this may not be true for other fairness notions. Since our algorithm relies heavily on a primal-dual approach, the finiteness of the optimal dual variables can only be guaranteed if certain constraint qualification conditions are met. This is not an issue for the demographic parity constraint but could be a potential obstacle for other fairness definitions.\n\nWe appreciate the reviewer's suggestion to include those two references, and they will be added to the final version. We want to emphasize that both references heavily depend on the ability to express the form of the optimal classifier under a given fairness constraint analytically. However, this is not applicable to regression in the unawareness setup as no such formula exists. Nevertheless, combining our discretization approach with the two references could potentially lead to a sensible method, and it is indeed an interesting avenue for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We conducted an ablation study to observe the behaviors of other algorithms, as suggested by Reviewer qMMa. A figure that illustrates the comparison is included in the attached pdf file.

In conclusion, all algorithms perform similarly in the middle to high unfairness regime, while those based on SGD3 are more stable in the low unfairness (high fairness) regime. However, since the stochastic minimization of the norm of the gradient of a convex function is a relatively niche topic, there are only a few algorithms with established convergence rates. As we aim for end-to-end guarantees, we have chosen methods based on SGD3. Nonetheless, other stochastic minimization methods could potentially perform just as well in practice.

Meta-review: The paper studies the problem of fair regression with demographic parity constraints under a setting where sensitive features are not revealed at the test time. The setting is new and well-motivated. The paper develops algorithms with theoretical guarantees and is supported with numerical experiments.
Decision: Accept (poster)