Regression under demographic parity constraints via unlabeled post-processing

Authors: gayane  taturyan
evgenii  chzhen
mohamed  hebiri
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:19:18

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.

Main paper: 
 introduction: 
 Algorithmic fairness is an umbrella term for a subset of machine learning research that aims to better understand, quantify, mitigate, evaluate, and conceptualize negative and/or positive effects of datadriven algorithms on the society. At least one direction in this field falls within theoretical machine learning, where a 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 non-discriminatory 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-populations that share a common sensitive characteristic. Many works fall within this category (Barocas et al., 2018 , Calders et al., 2009 , Chiappa et al., 2020 , Dwork et al., 2011 , Feldman et al., 2015 , Gordaliza et al., 2019 , Hardt et al., 2016 , Jiang et al., 2020 , Lum and Johndrow, 2016 , Zafar et al., 2017 , Zemel et al., 2013, just to name a few).Even without going into debates on the relevance of a 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 awarenessthe 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 et 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 case for other fairness constraints or the unawareness setup-the situation when the sensitive attribute is not available at inference time. In particular, while the case of 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-efficient, fully theory-driven algorithm for 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 a smooth convex objective function whose exact solution yields a fair and optimal prediction function. It 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 a gradient-map) 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 to achieve this goal, properly setting all the hyper-parameters and recovering the usual statistical rate 1/ √ T for both fairness and risk guarantees -T being the number of samples.Our work falls withing the realm of post-processing methods-another umbrella term that combines all the methods that perform a 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 it 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 fairness constraints, and unawareness setup; we introduce entropic regularization for this problem and design a dual convex objective from it; ii) we design a semi-supervised post-processing algorithm and show that it enjoys strong theoretical guarantees; iii) we perform numerical simulations demonstrating the relevance of our approach in practice.Organization. This paper is organized as follows: in Section 2 we present the problem setup and introduce main problem-related notation; in Section 3 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, . . . , K} and [[K] ] to denote {-K, . . . , 0, . . . , K}. For a > 0 denote by ⌊a⌋ largest non-negative integer that is smaller or equal to a. For a univariate probability measure µ, we denote by supp(µ) its support. For every β > 0, m ∈ N, and w = (w 1 , . . . , w m ) ⊤ ∈ R m , we denote by LSE β : R m → R the log-sum-exp function, defined asLSE β (w) = β -1 log m j=1 exp(βw j ) .For every m ∈ N, w = (w 1 , . . . , w m ) ⊤ ∈ R m , we denote by σ = (σ 1 , . . . , σ m ) : R m → R m the soft-argmax as σ j (w) = exp(w j )/( m i=1 exp(w i )). For any matrix A, the notation A ⩾ 0 means that A is positive coordinate-wise. For any a ∈ R and w ∈ R m we set (a) + = max{0, a} and (w) + = ((w 1 ) + , . . . , (w m ) + ) ⊤ . The notation O hides (unimportant) constants and polylogarithmic factors. For a pair of random elements (A, B), we denote by Law(A), the law of A, by Law(A | B), the conditional law of A given B, and we write A ⊥ ⊥ B to denote that variables A and B are independent. For two vectors w, w ′ ∈ R m , we write w/w ′ = (w j /w ′ j ) j∈[m] ∈ R m to denote element-wise division. The Euclidean norm of a vector and the Frobenius norm of a matrix are denoted by ∥ • ∥, while the spectral norm of a matrix is denoted by ∥ • ∥ op . We denote by B(R), the Borel sigma-algebra on R, induced by the usual topology. We write log to denote the natural logarithm and log a , the base a > 0 logarithm.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 fairness and risk and Section 6 illustrates the performance of the method and a comparison to a state-of-the-art 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 in 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 it is clear that these goals are not attained by the paper. 
problem setup: 
 Let (X, S, Y ) be a triplet of nominally non-sensitive, nominally sensitive, and output characteristics, taking values in R d × [K] × R 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) Law Y π | X = x, S = s = π(• | x) x ∈ R d , s ∈ [K] . Remark 2.1. Note that if π(• | x) is a Dirac measure for all x ∈ R d , the above condition just means that Y π = g(X)almost surely for some deterministic g : R d → R. The above condition is not to be confused with the fairness constraint, which is not formulated point-wise. It is 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, Y π ) but leaves the relation between Y π and Y ambiguous. To be more formal, one needs to add the condition ( Y π ⊥ ⊥ Y ) | (X, S), that is, the prediction Y π is independent from the true label Y , conditionally on (X, S). That would define a complete joint distribution of (X, S, Y, Y π )∼ P π = P (X,S) ⊗ P Y |(X,S) ⊗ π(• | X).We consider the following risk of a prediction function πR(π) def = E[( Y π -η(X)) 2 ] = E R ( y -η(X)) 2 π(d y | X) . A prediction function π is said to satisfy the demographic parity constraint, if Y π ⊥ ⊥ S.That is, Y π is stochastically independent of S viewed from the perspective of the joint distribution of (X, S, Y π ). 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 is controlled as quantified by some measure of unfairness. The above problem is well understood in the case of awareness-the situation when π is expressed as π(• | x, s) (Chiappa et al., 2020 , Chzhen et al., 2020a , 2021 , Jiang et al., 2020 , Le Gouic et al., 2020) -revealing an intimate connection of this problem with Wasserstein barycenters. Yet, when the sensitive attribute is not an input of 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 a sound theory. One of the principal goals of this work is to design a computationally efficient algorithm that admits a (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 a 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 S is known at inference time, which is not the case for the considered problem. 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(π) = E[r(X, Y π )] and multi-class classification respectively under the demographic parity constraint. Here r(x, y) quantifies fit of y for an individual x and can be either known or unknown.Question: Does the paper discuss the limitations of 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 no 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 a separate "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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
our methodology: 
 The starting point of our work is similar to the one of Chzhen et al. (2020b) and relies on a simple observation-if | supp(π(• | x))| < ∞ and stays the same for all x, the independence constraint is reduced to a finite amount of constraints that only involve the image of π(• | x). In particular, assuming that supp(π(• | x)) = Y ⊂ R for all x ∈ R d , Y π is independent from S iff P( Y π = y | S = s) = P( Y π = y) for all s ∈ [K]and all y ∈ Y. In view of the definition of Y π , the latter is equivalent toEQUATIONwhich, assuming that Y is fixed, correspond to linear constraints on π. Combined with the observation that π → R(π) is also linear, we end up with a problem that is significantly easier to handle. Furthermore, again assuming that Y is fixed, the sketched direction gives a natural way to introduce some slack to the independence constraint-simply requiring an approximate equality in (1). SetEQUATIONfor all s ∈ [K] and y ∈ Y. Thus, for a fixed support (whose choice will be discussed in the next paragraph) and a fixed vector ε def = (ε 1 , . . . , ε K ) ⊤ , our goal is to build an estimator of a solution toEQUATIONLet us now describe the methodology for selecting Y 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 gridY L def = B • [[L]]/L on [-B, B], so that | Y L | = 2L + 1, which is viewed as a support of prediction functions π(• | x).For the sake of simplicity, we will assume that the regression function η(•) is bounded in [-B, B] for some known B > 0. Assumption 3.1 (Bounded signal). There exists B > 0 such that |η(X)| ⩽ 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 to a small number of constraints. Thus, there is a trade-off that is introduced by L. A natural attempt to tackle the problem of fairness in this context would be to estimate a solution to (3) with Y = Y L . 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 a complete knowledge of the underlying distribution P, solving (3) requires solving a linear program in dimension Ω(LK) 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 β > 0, we considermin π:B(R)×R d →[0,1] R β (π) : supp(π(• | x)) = Y for x ∈ R d , Us(π, y) ⩽ εs for y ∈ Y, s ∈ [K] , (4) where R β (π) = R(π) + 1 β E[Ψ(π(• | X))] and for any discrete univariate distribution µ, we define its negative entropy Ψ(µ) def = y∈supp(µ) µ( y) log(µ( y)).Remark 3.1 (On abuse of notation). Note that for every y ∈ Y L there is a unique ℓ ∈ [[L]] such that y = ℓB/L and we will write π(ℓ | x) instead of π( y | x). Similarly, we write U s (π, ℓ) instead of U s (π, y), defined in (2), when no confusion is possible and the support Y L is fixed.An extremely attractive feature of the problem in (4) is the fact that the solution to 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.EQUATIONwhere t(x)def = 1 -τ (x) p , r ℓ (x) def = η(x) -ℓB L 2 , and λ ℓ = (λ ℓs ) s∈[K] , ν ℓ = (ν ℓs ) s∈[K]. Then, (4) admits a solution in the formEQUATIONAssuming perfect knowledge of η and τ , the above lemma suggests a natural approach to estimating the π Λ ⋆ ,V ⋆ -we can run a (version of) stochastic gradient descent on F (•, •) and then plug-in the resulting dual variables in the formula for π Λ ⋆ ,V ⋆ . Notably, a stochastic gradient of F (•, •) can be obtained by simply sampling one X from P X -it 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 F for good statisitcal properties of the algorithm. That goes without saying that this relaxation has its price-the smaller the regularization parameter β the less accurate the resulting solution, but the resulting dual optimization problem is easier and vice-versa.Properties of F and π Λ ⋆ ,V ⋆ . Let us summarized key properties of the objects introduced in Lemma 3.1. The first two results concern the population properties ofπ Λ ⋆ ,V ⋆ : Lemma 3.2 (Fairness quantification). Let L ∈ N, ε = (ε s ) s∈[K] ∈ [0, 1] K , β > 0, and π Λ ⋆ ,V ⋆ be defined in Lemma 3.1. Then, U s (π Λ ⋆ ,V ⋆ , ℓ) ⩽ ε s for all s ∈ [K], ℓ ∈ [[L]].In words, the optimal entropic-regularized 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 ∈ N, β > 0, and π Λ ⋆ ,V ⋆ be defined in Lemma 3.1. For any π :B(R) × R d → [0, 1] that is feasible for (3), we have R(π Λ ⋆ ,V ⋆ ) ⩽ R(π) + log | Y L | β .The above result is rather instructive, it quantifies the price of the introduced regularization. Intuitively, one wants to set β high enough, so that the additive term in the above bound is vanishing. Unfortunately, we cannot set it arbitrarily high, since it will introduce instabilities from the optimization perspective-the function F becomes less regular as β growth. This is summarized below.Lemma 3.4 (Regularity of F ). Let σ 2 def = 2 s∈[K]1-ps ps . The objective function in (5) is convex and its gradient is (βσ 2 )-Lipschitz.As mentioned, we see that the larger the β is, the less regular the function F is, making it harder to minimize. Thus, β ⩾ 0 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 Λ, V ⩾ 0 asEQUATIONWe want to show that if Λ, V ⩾ 0 is nearly stationary point of F , then π Λ,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, we cannot hope for the gradient of F to go to zero. Instead, we introduce gradient mapping-a quantity that shares many properties of the gradient in the case of constraint optimization problem. For α > 0,EQUATION)Our main observation is summarized in the next lemma. Lemma 3.5.Let σ 2 def = 2 s∈[K] 1-ps ps , L ∈ N, Λ, V ⩾ 0, then for any α > 0, β > 0, the unfairness of π Λ,V satisfies ℓ∈[[L]]s∈[K] U s π Λ,V , ℓ -ε s 2 + ⩽ ∥G α (Λ, V)∥ 2 .Furthermore,R(π Λ,V ) ⩽ R(π Λ ⋆ ,V ⋆ ) + ∥(Λ, V)∥ + α σ + ∥ε∥ 2| Y L | ∥G α (Λ, V)∥ + log | Y L | β .Lemma 3.5 is very instructive on its own-we can obtain a good estimator of π Λ ⋆ ,V ⋆ in terms of risk and unfairness by performing stochastic optimization on F and controlling the norm of gradient mapping for a suitable parameter α > 0. The final choice of the parameter α 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 α > 0 that yields desired statistical properties. A naive approach in doing so relies on a well-known relation between F (Λ, V) -F (Λ ⋆ , V ⋆ ) and ∥G α (Λ, V)∥ 2 using the Lipshitzness of the gradient of F (see e.g., Beck, 2014, Lemma 9.11) . More concretely, forgetting about the constraints1 , one hasEQUATION)where M is the Lipschitz constant of ∇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 we 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 on the variance of the stochastic gradient and scales as 1/ √ T , with T being the number of future samples from P X , and "optimization" rate of convergence that depends on M and the diameter of the problem and typically scales as 1/T or even 1/T 2 if acceleration is used. Indeed, in our setup, Lipschitz constant M of ∇F is not a fixed constant, but a parameter to be set-it relates to β (cf. Lemma 3.4). Ideally, seeing Lemma 3.3, we want to set β = Θ( √ T ), leading to M = Ω( √ T ). Thus, in view of (9), a term of the form M/ √ T 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 as 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 to sketch our approach and the formal presentation is deferred to the next section. For well selected parameters β > 0, L ∈ 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 P X and it appears that this stochastic gradient has a 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 α > 0, the term E∥G α ( Λ, V)∥ 2 is controlled and then rely on Lemma 3.5 and some additional results to demonstrate that the resulting π Λ, V possesses good statistical properties.Remark 3.2 (On the dynamic of algorithm). Note that for Λ = V = 0, the correspondingπ 0,0 (ℓ | x) ℓ∈[[L]] = σ β -(η(x) -ℓ ′ B/L) 2 ℓ ′ ∈[[L]] .That is, the above prediction puts the most amount of mass on the atom ℓ which minimizes (η(x) -ℓB/L) 2 -the most accurate, but unfair prediction. Since our algorithm is based on a SGD-type algorithm, initialized at Λ 0 = V 0 = 0, then we expect that during the dynamic of the algorithm, the risk of π Λt,Vt increases, while the unfairness decreases. This phenomena coincides with the intuition of post-processing-we want to 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 an in-processing estimator and by Chzhen et al. (2020b) for a 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-processing and even online post-processing, where i.i.d. samples from P X comes in a stream and we do not need to store them in memory. Also, while their algorithm is 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-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 an 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) as we rely on different phenomenons and provide a very different algorithm. On a more 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 matter2 . This is precisely the phenomena highlighted by Nesterov (2012) .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to 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 6 to make our experiments reproducible.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
proposed algorithm: 
 Algorithm 1: DP post-processing(L, T, β, p, B, η, τ )1: Input: discretization parameter L ⩾ 1; regularization β > 0, number of stochastic gradient evaluations T ⩾ 1; marginal distribution p of S; regression function η; conditional distribution τ of S | X; bound B > 0 on η. 2: Build uniform grid Y L over [-B, B]; 3: Set parameters: σ 2 = 2 s∈[K] 1-ps ps , M = βσ 2 ; 4: Set (Λ, V) → F (Λ, V)as defined in Lemma 3.1 5: Run a black-box optimizer A(F, σ 2 , M, T ) on function F having access to T stochastic gradient evaluations (see ( 11)) with variance σ 2 and smoothness parameter M to obtain ( Λ, V);6: return π ( Λ, V) (• | •) as defined in (7);In this section, we provide all the details about the proposed algorithm in case η and τ are known. If they are unknown, these quantities are replaced by their estimates η and τ that are constructed on a separate labeled dataset. First, forΛ = (λ ℓs ) ℓ∈[[L]],s∈[K] , V = (ν ℓs ) ℓ∈[[L]],s∈[K], let us provide the expression for the gradient of F :EQUATIONwhere □ ∈ {λ, ν} and △ = 1 if □ = λ and △ = -1 otherwise. Thus, a stochastic gradientg(Λ, V) = (g λ ℓs (Λ, V), g ν ℓs (Λ, V)) ℓ∈[[L]],s∈[K] of F at a point (Λ, V) can be computed by erasing expectation in (10), i.e., by sampling one X ∼ P X , using the same convention as above about □, △:EQUATIONThe next result controls the variance of the above stochastic gradient.Lemma 4.1. Let σ 2 def = 2 s∈[K] 1-ps ps . It holds that E∥g(Λ, V) -∇F (Λ, V)∥ 2 ⩽ σ 2 .The proposed method is summarized in Algorithm 1. It uses a black-box stochastic optimization algorithm A, that operates on a convex function F and a stochastic first-order oracle. The stochasticfirst 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 σ 2 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 accelerated SGD of Ghadimi and Lan (2012) . 
theoretical guarantees.: 
 Let us first provide main results for Algorithm 1 assuming that η and τ are known. Note that Algorithm 1 can rely on any optimization algorithm. We provide a complete analysis using a refined version of SGD3 algorithm of Allen-Zhu (2021) that is due to Foster et 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 a primer on optimization to the supplementary material (Appendix C-D).Theorem 5.1.Let ε = (ε s ) s∈[K] ∈ [0, 1] K and σ 2 = 2 s∈[K] (1 -p s )/p s . Setting β = T 8 log 2 (T )and L = √ T , there exists an optimizer A to be used in Algorithm 1 that, for T larger than some absolute constant, ensuresE 1 /2 ℓ∈[[L]]s∈[K] U s π Λ,V , ℓ -ε s 2 + ⩽ O σ √ T 1 + σ √ T ∥(Λ ⋆ , V ⋆ )∥ .Furthermore, if Assumption 3.1 is satisfied and letEQUATIONandE(π Λ, V ) def = E R(π Λ, V ) -R ⋆ , then for the same algorithm E(π Λ, V ) ⩽ O σ √ T E 1 /2 ∥( Λ, V)∥ 2 + ∥ε∥ T 5 /4 1 + σ √ T ∥(Λ ⋆ , V ⋆ )∥ + B √ T .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 a 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 a Kolmogorov-Smirnov distance. One first main observation is that both fairness and risk decrease at the rate 1/ √ T 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 a result, we increase artificially T -without generating new data-which gives a significant empirical improvement. We also remark that σ is the parameter that depends on the number of groups. For example, in the case of uniform distribution of sensitive groups σ = O(K). We finally remark that both bounds involve a single unknown quantity-∥(Λ ⋆ , V ⋆ )∥, which from standard duality argument can be shown to be bounded by O(1/ min s∈[K] {ε s }) (see e.g., Nedić and Ozdaglar, 2009, Lemma 3) . Thus, having this norm multiplied by T -1/2 is a very attractive property of the bound. It allows to set ε ≈ T -1/2 without damaging the parametric convergence rate.To derive the above result, we slightly extend the analysis of Foster et al. (2019) , who, relying on the SGD3 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 a 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 β, we noticed that there is no need to restart the accelerated SGD as it is done by Foster et al. (2019) because it leads to identical statistical convergence rates. The interested reader can take a 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 a careful and practical choice of all the parameters of the algorithm.Extension to unknown η and τ . In this part we show that if we replace η and τ with their estimates η and τ and run DP post-processing(L, T, β, p, B, η, τ ) algorithm with the same choice of parameters, Theorem 5.1 remains if we pay additional price for the estimation of η and τ . From now on, we assume that η and τ are provided and are trained on its own labeled data sample, while the refitting is performed on an independent stream of i.i.d. data from P X . So, we essentially treat η and τ as deterministic functions. Let us introduce a family of prediction functionsEQUATIONNote that for fixed matrices Λ, 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 η and τ . To be more precise, we consider the plug-in version of (5), defined as minΛ,V⩾0 E X LSE β λ ℓ -ν ℓ , t(X) -r ℓ (X) L ℓ=-L + L ℓ=-L ⟨λ ℓ + ν ℓ , ε⟩ . ( P LSE )Let us denote by F , the objective function of the above problem. Thus, main interesting part is to demonstrate that a control of the gradient map of F , denoted by ∥G F ,α ( Λ, V)∥, gives a control of risk and unfairness of π Λ, V , quantifying the price induced by the plug-in estimation. This is precisely the purpose of the following two results:Lemma 5.1. Let L ∈ N, Λ, V ⩾ 0, then for any α > 0, β > 0 it holds that ℓ∈[[L]]s∈[K] (U s ( π Λ,V , ℓ) -ε s ) 2 + ⩽ ∥G F ,α (Λ, V)∥ + E 1 /2 ∥ t(X) -t(X)∥ 2 . Lemma 5.2. Let σ 2 = 2 s∈[K] E X (ps-τs(X)) 2 p 2 s , L ∈ N, Λ, V ⩾ 0, then for any α > 0, β > 0 it holds that R( π Λ,V ) ⩽ R(π Λ ⋆ ,V ⋆ ) + ∥(Λ, V)∥ + α σ + ∥ε∥ 2| Y L | G F ,α (Λ, V) + log | Y L | β + 2E X max ℓ∈[[L]] |r ℓ (X) -r ℓ (X)| + √ 2∥(Λ, V)∥ • E 1 /2 ∥t(X) -t(X)∥ 2 .Note that the two above results are extensions of Lemma 3.5, where both t and η 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. 
numerical illustration: 
 In this section we conduct empirical study of the proposed algorithm, denoted by DP-postproc, and demonstrate its relevance in practical problems3 . 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-SGD3 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 stick to the latter. 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-white individuals or communities (majority-wise).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 D train = {(x i , s i , y i ) n i=1 } to train a base (unfair) regressor to estimate η and to train a classifier to estimate τ . We use simple LinearRegression and LogisticRegression from scikit-learn for training the regressor and the classifier. Finally, we use the trained regressor and classifier to train the Algorithm 1 with D unlabeled = (x) n+T i=n+1 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 useD test = {(x ′ i , s ′ i , y ′ i ) m i=1} to collect evaluation statistics. In Figure 1 we illustrate the post-processing dynamics of our method. We have 2 plots for each test dataset: the history of risk (R( π)) and of the unfairness (U 0 ( π) and U 1 ( π)) w.r.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. 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-a 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 D train and D unlabeled as training set for ADW-1, whereas for ADW-2 we use only D train . 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 -i , 2 -i ) i∈I }, where I = {1, 2, 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. 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). 4On 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 in both training regimes. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Section 6 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 in the core of the paper to a 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, or as supplemental material. 
conclusion: 
 Deriving a dual convex surrogate, we have provided a 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 a 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 be beneficial to further investigate stationary point guarantees for convex optimization to yield a better practical performance.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are 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 or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: We reported all this information in a footnote in Section 6. 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 as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification:We only used open source data and codes. Therefore, we believe that there are no issues form the ethical point of 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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] Justification: 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ε-fairness. While approximate fairness is desired in general, this setting allows for a control of the amount of unfairness that we allow or accept. From this point of view, providing the control on the fairness to some user may generate ethical issues.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset'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 not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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 is used. • 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. 
 
 Appendix: First we explicit the first order optimality conditions for the problem in (5). Lemma A.1. Let (Λ ⋆ , V ⋆ ) ⩾ 0 be any minimizer of (5) and π ⋆ = π Λ ⋆ ,V ⋆ be defined in (6). Then, there existEQUATIONwhereγ ℓ = (γ ℓs ) s∈[K] , γ ′ ℓ = (γ ′ ℓs ) s∈[K] .Proof. We first observe that the optimization problem in ( 5) is convex and smooth. Thus, Karush-Kuhn-Tucker conditions are sufficient for optimally. Furthermore, since Slatter's condition is satisfied, the latter is also necessary, as the strong duality holds. In particular, there existΓ = (γ ℓs ) ℓ∈[[L]],s∈[K] , Γ ′ = (γ ′ ℓs ) ℓ∈[[L]],s∈[K] -element-wise non-negative matrices such that              ∇ Λ F (Λ ⋆ , V ⋆ ) -Γ = 0 ∇ V F (Λ ⋆ , V ⋆ ) -Γ ′ = 0 Λ ⋆ , V ⋆ ⩾ 0 γ ℓs λ ⋆ ℓs = 0 γ ′ ℓs ν ⋆ ℓs = 0 ∀ℓ ∈ [[L]], s ∈ [L] .To conclude, it is sufficient to evaluate the gradient on F , whose expression is given in ( 10) and use the definition of π ⋆ . ■Proof of Lemma 3.1. To prove this result, we introduce the Lagrangian for the problem in (4).L(π, Λ, V) = R β (π) + E X   ℓ∈[[L]] ⟨ν ℓ -λ ℓ , t(X)⟩ π(ℓ | X)   - ℓ∈[[L]] ⟨λ ℓ + ν ℓ , ε⟩ ,where we used the fact, that using the definition of U s , for any randomized prediction function π, we can writeEQUATIONThus, denoting by (⋆) the value in (4), we have(⋆) = min π max Λ,V⩾0 L(π, Λ, V) = max Λ,V⩾0 min π L(π, Λ, V) ,where the second equality holds thanks to Sion's minmax theorem. Let us solve the inner minimization problem on the right-hand-side. We can writeEQUATIONThus, using the variational representation of LSE β , recalled in Lemma F.1, we havemin π L(π, Λ, V) = -max π    E X   ℓ∈[[L]] (⟨λ ℓ -ν ℓ , t(X)⟩ -r ℓ (X)) π(ℓ | X) - 1 β Ψ(π(• | X))   + ℓ∈[[L]] ⟨λ ℓ + ν ℓ , ε⟩    = -E X LSE β (⟨λ ℓ -ν ℓ , t(X)⟩ -r ℓ (X)) ℓ∈[[L]] - ℓ∈[[L]] ⟨λ ℓ + ν ℓ , ε⟩ ,and the optimum in the above problem for every Λ, V ⩾ 0 is achieved by π Λ,V , defined in (7). Thus, we haveEQUATION)The proof is concluded. ■Proof of Lemma 3.2. As shown in (15), for any randomized prediction function π, we can writeU s (π, ℓ) = |E X [π(ℓ | X)t s (X)]| .Our goal is to show that π ⋆ satisfies the required fairness constraints. We are going to rely on Lemma A.1 Subtracting the first equation in ( 14) from the second one, we deduce thatγ ℓ + γ ′ ℓ = 2ε. Since γ ℓ , γ ′ ℓ ⩾ 0, then we conclude that γ ℓs , γ ′ ℓs ∈ [0, 2ε s ]. The above implies that -ε s ⩽ E X [π ⋆ (ℓ | X)t s (X)] = U s (π ⋆ , ℓ) ⩽ ε s , 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 Y. Then, we can bound its negative risk as followsEQUATIONfor (a) we used the assumption that π is fair (i.e., U s (π, ℓ) ⩽ ε s ), which due to the fact that Λ ⋆ , V ⋆ ⩾ 0 implies ℓ∈[[L]] ⟨λ ⋆ ℓ , E X [t(X)π(ℓ | X)] + ε⟩ + ℓ∈[[L]] ⟨ν ⋆ ℓ , -E X [t(X)π(ℓ | X)] + ε⟩ ⩾ 0 ,λ ⋆ ℓs E X [π ⋆ (ℓ | X)t s (X)] = -λ ⋆ ℓs ε s ν ⋆ ℓs E X [π ⋆ (ℓ | X)t s (X)] = ν ⋆ ℓs ε s ∀ℓ ∈ [[L]], s ∈ [K] ,implying thatE X   ℓ∈[[L]] ⟨λ ⋆ ℓ -ν ⋆ ℓ , t(X)⟩ π ⋆ (ℓ | X)   + ℓ∈[[L]] ⟨λ ⋆ ℓ + ν ⋆ ℓ , ε⟩ = 0 .The proof is concluded. ■Proof of Lemma 3.5. Fix arbitrary Λ, V ⩾ 0 and consider π Λ,V , defined in (7). To ease the notation, in this proof, we write π instead of π Λ,V .Part I. Let us first recall the definition of the gradient map G α given in (8). We have the following expressionG α (Λ, V) = (Λ, V) -((Λ, V) -α∇F (Λ, V)) + α ,where (•) + is to be understood entry-wise. Observing that for any α, a ⩾ 0 and b ∈ R, we havea -(a -αb) + α = a -max{0; a -αb} α = min a α ; b ⩾ |min {0; b}| ⩾ (-b) + ,we deduce thatEQUATION)Relying on (10) and the expression for π in (7), we observe that∇ λ ℓs F (Λ, V) = E X [π(ℓ | X)t s (X)] + ε s ∇ ν ℓs F (Λ, V) = -E X [π(ℓ | X)t s (X)] + ε s (20) and that U s (π, ℓ) = |E [π(ℓ | X)t s (X)]| as it is shown in (15). Using the fact that (|a| -c) 2 + = (-a -c) 2 + + (a -c) 2+ for all a ∈ R and c ⩾ 0, we deduce from above(U s (π Λ,V , ℓ) -ε s ) 2 + = (-∇ λ ℓs F (Λ, V)) 2 + + (-∇ ν ℓs F (Λ, V)) 2 + ∀ℓ ∈ [[L]], s ∈ [K] . (21) Thus, we have shown ℓ∈[[L]] s∈[K] (U s (π, ℓ) -ε s ) 2 + = (-∇F (Λ, V)) + 2 ,and ( 19) yields the claim.Part II. We note that π (Λ,V) is a unique solution tomin π L(π, Λ, V) ,where L is the Lagrangian defined in (16). Furthermore,min π L(π, Λ, V) = -F (Λ, V) = L(π (Λ,V) , Λ, V). Hence, R β (π (Λ,V) ) + F (Λ, V) = ℓ∈[[L]],s∈[K] λ ℓs ∇ λ ℓs F (Λ, V) + ℓ∈[[L]],s∈[K] ν ℓs ∇ ν ℓs F (Λ, V) = ⟨(Λ, V) , ∇F (Λ, V)⟩ .For the sake of simplicity let us denote by 2L+1) and recall the definition of gradient mapping G α given in (8). For any j ∈ [2K(2L + 1)] and α > 0, we haveu def = (Λ, V) ∈ R 2K(G αj (u) = uj /α if α∂ j F (u) > u j , ∂ j F (u) if ∂ j F (u) ⩽ u j .To bound ⟨u, ∇F (u)⟩, let us examine each term of the scalar product. Denoting by 2L+1) , for any j ∈ [2K(2L + 1)] and α > 0, we haveu def = u - α∇F (u) ∈ R 2K(u j ∂ j F (u) = α∂ j F (u)G αj (u)I{ u j < 0} + u j G αj (u)I{ u j ⩾ 0} . Thus, it holds that ⟨u, ∇F (u)⟩ ⩽ j∈[2K(2L+1)] (α|∂ j F (u)G αj (u)| + |u j G αj (u)|) ⩽ (∥u∥ + α ∥∇F (u)∥) ∥G α (u)∥ ⩽ ∥u∥ + ασ + α ∥ε∥ 2(2L + 1) ∥G α (u)∥ ,where the last inequality follows from Lemma F.5 that bounds ∥∇F (u)∥.To conclude the proof, we use the fact that It remains to observe that min Λ,V F (Λ, V) = -R β (π (Λ ⋆ ,V ⋆ ) ), the bound (19) on ∥(-∇F (Λ, V)) + ∥ and the fact that R β (π) ⩽ R(π)+ log(2L+1) β for all π. ■ B Bound on the variance of the stochastic gradient and its' smoothnessProof of Lemma 4.1. We haveE X ∥g Λ,V (X) -∇ Λ,V F (Λ, V)∥ 2 ⩽ 2E X σ ℓ β (⟨λ ℓ ′ -ν ℓ ′ , t(X)⟩ -r ℓ ′ (X)) L ℓ ′ =-L t s (X) ℓ∈[[L]],s∈[K] 2 ⩽ 2E X   s∈[K] t 2 s (X)   ⩽ 2 s∈[K] 1 -p s p s def = σ 2 ,where the first inequality follows from the expressions of g Λ,V and ∇ Λ,V F (Λ, V), and the fact that Var(X + a) = Var(X) ⩽ E[X 2 ]; the second inequality follows from the facts that ∥(a i b j ) i,j ∥ 2 2 = ∥a∥ 2 2 ∥b∥ 2 2 ⩽ ∥a∥ 2 1 ∥b∥ 2 2and that ∥σ(•)∥ 1 = 1; and the last inequality follows from Lemma F.4. ■ Proof of Lemma 3.4. The goal of this proof is to show that the gradient of (Λ, V) → F (Λ, V) is M -Lipschitz. To this end, we first introduce some, rather heavy, but convenient, notation which will allow us to derive the announced result.Introducing notation. We first vectorize the variables (Λ, V) and express them asz def = (λ -L1 , • • • λ -LK =λ -L , • • • • • • , λ L1 , • • • λ LK =λ L , ν -L1 , • • • ν -LK =ν -L , • • • • • • , ν L1 , • • • ν LK =ν L ) ∈ R 2K(2L+1) .Furthermore, for each x ∈ R d , we introduce a matrix A(x) ∈ R (2L+1)×2K(2L+1) defined asA(x) def =      t(x) ⊤ 0 • • • 0 • • • 0 • • • 0 -t(x) ⊤ 0 • • • 0 • • • 0 • • • 0 0 • • • 0 t(x) ⊤ • • • 0 • • • 0 0 • • • 0 -t(x) ⊤ • • • 0 • • • 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 • • • 0 0 • • • 0 • • • t(x) ⊤ 0 • • • 0 0 • • • 0 • • • -t(x) ⊤      , as well as b(x) def = (r -L (X), • • • , r L (X)) ⊤ ∈ R 2L+1 and c def = (ε 1 , • • • , ε K , ε 1 , • • • , ε K , • • • • • • , ε 1 , • • • , ε K ) ⊤ ∈ R 2K(2L+1) .Hessian of F in the introduced notation. With the above introduce notation, we can express the function F asF (Λ, V) = F (z) = E X [LSE β (A(X)z -b(X))] + ⟨c, z⟩ .That is, F is obtained from the LSE β by a point-wise affine transformation of the coordinates plus a linear term. Chain rule yields the following expressions for the Hessian of F :∇ 2 F (z) = E X A(X) ⊤ ∇ 2 LSE β (A(X)z -b(X))A(X) .Bounding the operator norm of the Hessian of F . To conclude the proof, we provide a uniform upper bound on the operator (spectral) norm of the Hessian of F . Using the Jensen's inequality and the fact that the operator norm is subordinate, we deduce that∥∇ 2 F (z)∥ op = ∥E X A(X) ⊤ ∇ 2 LSE β (A(X)z -b(X))A(X) ∥ op ⩽ E X ∥A(X) ⊤ ∇ 2 LSE β (A(X)z -b(X))A(X)∥ op ⩽ E X ∥A(X)∥ op ∥∇ 2 LSE β (A(X)z -b(X))∥ op ∥A(X)∥ op .Lemma F.2, implies that ∥∇ 2 LSE β (A(X)z -b(X))∥ op ⩽ β almost surely and for all z. Thus, it remains to bound E X ∥A(X)∥ 2 op to conclude the proof. To this end, consider a vector u, expressed "block-wise" asu = u λ -L1 , • • • u λ -LK def = u λ -L , • • • • • • , u λ L1 , • • • u λ LK def = u λ L , u ν -L1 , • • • u ν -LK def = u ν -L , • • • • • • , u ν L1 , • • • u ν LK def = u ν L ⊤ ∈ R 2K(2L+1) .Using the definition of the operator norm and the expression for A(X), we deduce thatE X ∥A(X)∥ 2 op = E X sup ∥u∥ 2 2 =1 ∥A(X)u∥ 2 2 = E X sup ∥u∥ 2 2 =1 L ℓ=-L u λ ℓ -u ν ℓ , t(X) 2 ⩽ 2E X ∥t(X)∥ 2 2 sup ∥u∥ 2 2 =1 ℓ∈[[L]] u λ ℓ 2 2 + ∥u ν ℓ ∥ 2 2 ,where the last inequality combines the Cauchy-Schwartz inequality and the fact that ∥v -w∥ 2 2 ⩽ 2(∥v∥ 2 2 + ∥w∥ 2 2 ) for all v, w ∈ R m . The proof is concluded using Lemma F.4 to bound E X ∥t(X)∥ 2 2 . ■ Lemma B.1 (Price of discretization). Let Assumption 3.1 be satisfied. Let β, B > 0, L ∈ N. Consider R ⋆ def = inf h:R d →R E(h(X) -η(X)) 2 : sup t∈R |P(h(X) ⩽ t | S = s) -P(h(X) ⩽ t)| ⩽ ε s /2, ∀s ∈ [K] .Then, it holds thatR(π Λ ⋆ ,V ⋆ ) ⩽ R ⋆ + 4B L + 1 L 2 + log(2L + 1) β . Proof. Let us assume that R ⋆ = E(h ⋆ (X) -η(X)) for some h ⋆ : R d → [-B, B].If it is not the case, the standard argument based on the minimizing sequence yields the same result.Consider an operator T L , which maps a deterministic classifier h : R d → [-B, B] onto a deterministic classifier T L (h) : R d → Y L , which is defined point-wise as follows(T L (h))(x) = ⌊Lh(x)/B⌋B/L ∀x ∈ R d ,where ⌊a⌋ is the closest integer smaller or equal to a ∈ R in absolute value. Notice, that for any ℓ ∈ {-L, . . . , L -1} and any x ∈ R d , we have(T L (h ⋆ ))(x) = ℓB L ⇐⇒ h ⋆ (x) ∈ ℓB L , (ℓ + 1)B L .Moreover,(T L (h ⋆ ))(x) = B ⇐⇒ h ⋆ (x) = B .Since h ⋆ satisfies (ε/2)-fairness constraints, one checks that for all ℓ ∈[[L]], s ∈ [K] U s (T L (h ⋆ ), ℓ) ⩽ ε s .That is, T L (h ⋆ ) is feasible for the problem in (4). Therefore, Lemma 3.3 implies thatR(π Λ ⋆ ,V ⋆ ) ⩽ R(T L (h ⋆ )) + log(2L + 1) β . Furthermore, since |T L (h ⋆ )(x) -h ⋆ (x)| ⩽ 1/L and |η(x) -h ⋆ (x)| ⩽ 2B, we have R(T L (h ⋆ )) = E (η(X) -T L (h ⋆ )(X)) 2 ⩽ R(h ⋆ ) + 4B L + 1 L 2 .The proof is concluded. ■ Algorithm 2: AC-SA(F, w 0 , µ, M, T )1: Input: function F ; initial vector w 0 ; parameters µ, M ⩾ 0; number of iterations T ⩾ 1 2: w ag 0 = w 0 3: for t = 1 to T do 4:sample new z ∼ P , independently from the past 5: α t ← 2 t+1 6: γ t ← 4M t(t+1) 7: w md t ← (1-αt)(µ+γt) γt+(1-α 2 t )µ w ag t-1 + αt((1-αt)µ+γt) γt+(1-α 2 t )µ w t-In this part of the appendix, we provide the analysis for the proposed algorithm. First, we introduce required notation and recall a result of Foster et al. (2019) , who provided an algorithm for convex stochastic optimization. The provided algorithm is a refined version of the SDG3 algorithm of Allen-Zhu (2021). We note that Foster et al. (2019) give a 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 a control of the expected squared norm of the gradient mapping of the final estimated solution.The setup and notation.Consider f : R d × Z → R, such that w → f (w, z) is convex for each z ∈ Z. Let W ⊂ R d be a closed convex set. Let F (w) def = f (w, z)d P (z)for some probability distribution P on Z. In what follows, we assume thatw ⋆ ∈ arg min w∈W F (w)always exists.Assumption C.1. We assume that F is M -smooth and the variance of ∇ w f (w, z) is bounded. That is, for some M > 0 and σ > 0∀w, w ′ ∈ W ∥∇F (w) -∇F (w ′ )∥ ⩽ M ∥w -w ′ ∥ and ∀w ∈ W ∥∇ w f (w, z) -∇F (w)∥ 2 d P (z) ⩽ σ 2 .Let us also define gradient mapping asG F,α (w) def = w -w + α with w + ∈ arg min w ′ ∈W ⟨∇F (w), w ′ ⟩ + 1 2α ∥w ′ -w∥ 2 .Let Proj W (•) 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.Algorithm 3: AC-SA 2 (F, w 0 , µ, M, T )1: Input: function F ; initial vector w 0 ; parameters µ, M ⩾ 0; number of iterations T ⩾ 1 2: w 1 ← AC-SA(F, w 0 , µ, M, T 2 ) 3: w 2 ← AC-SA(F, w 1 , µ, M, T2 ) 4: return w 2 Algorithm 4: SGD3-refined(F, w 0 , µ, M, T ) 1: Input: function F ; initial vector w 0 ; parameters 0 < µ ⩽ M ; number of iterationsT ⩾ Ω M µ log 2 M µ 2: F (0) (w) ← F (w) + µ 2 ∥w -w 0 ∥ 2 ; w 0 ← w 0 ; µ 0 ← µ 3: for j = 1 to J = log M µ do 4: w j ← AC-SA 2 (F (j-1) , w j-1 , µ j-1 , 2(M + µ), T J ) 5:µ j ← 2µ j-1 6: Foster et al. (2019) propose another version of AC-SA, called AC-SA 2 , which resets the stepsize halfway through the process.F (j) (w) def = F (j-1) (w) + µj 2 ∥w -w j ∥α t = 2 t + 1 and γ t = 4M t(t + 1) , ∀t > 1 AC-SA(F, w 0 , µ, M, T ), defined in Algorithm 2, outputs w T satisfying E[F ( w T )] -F (w * ) ⩽ 2M ∥w 0 -w ⋆ ∥ 2 T 2 + 8σ 2 µT .Lemma C.1. (Foster et al., 2019 , Lemma 1) Let W = R d , w ⋆ ∈ arg min w∈W F (w), w 0 ∈ R d a starting vector. If µ > 0, M ⩾ 0 and T ⩾ 1 then AC-SA 2 (F, w 0 , µ, M, T ), defined in Algorithm 3, outputs w satisfying Foster et al. (2019) do not consider constrained optimization throughout their work. However, the proof of Lemma C.1 follows analogous arguments. In what follows, we will show that Algorithm 4, after T evaluations of the stochastic gradient, produces a point w such that E∥G F,α ( w)∥ 2 is controlled. This is a, rather mild, extension of Foster et al. (2019) and Allen-Zhu (2021).E[F ( w)] -F (w * ) ⩽ 128M 2 ∥w 0 -w ⋆ ∥ 2 µT 4 + 256M σ 2 µ 2 T 3 + 16σ 2 µT . Remark C.1.Most of the proof techniques are already present in the original contribution of Allen-Zhu (2021) and Foster et al. (2019) , we 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, introduceEQUATION)By construction, F µ is µ def = J j=1 µ j -strongly convex and (M + µ)-smooth. Let us also define F (0) def = F (w) and F (j) (w) def = F (j-1) (w) + µj 2 ∥w -w j ∥ 2 , for j = 1, 2, . . . , 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 µ-strongly convex function. Let w, w ′ ∈ W and w + = w -α • G F ,α (w). For any α ∈ 0, 1 M , we haveF (w ′ ) ⩾ F (w + ) + G F ,α (w), w ′ -w + α 2 G F ,α (w) 2 + µ 2 ∥w ′ -w∥ 2 .Lemma C.3. (Allen-Zhu, 2021, Lemma 5.1) Consider F µ and w ⋆ µ as defined in (22) and w ∈ W . For any α ∈ 0, 1 M + µ , we have∥G F,α (w)∥ ⩽ J j=1 µ j w ⋆ µ -w j + 3 G F µ ,α (w) .Claim C.1. (Allen-Zhu, 2021, Claim 6.2) Suppose for every j = 1, . . . , J iterates w j of Algorithm 4 satisfyE F (j-1) ( w j ) -F (j-1) w ⋆ j-1 ⩽ δ j where w ⋆ j-1 ∈ arg min w F (j-1) (w) , then, (a) for every j ⩾ 1 we have E w j -w ⋆ j-1 2 ⩽ E w j -w ⋆ j-1 2 ⩽ 2δj µj-1 ; (b) for every j ⩾ 1 we have E w j -w ⋆ j 2 ⩽ E w j -w ⋆ j 2 ⩽ δj µj ; (c) if µ j = 2µ j-1 , then for all j ⩾ 1 we have E J j=1 µ j ∥ w j -w ⋆ J ∥ ⩽ 4 J j=1δ j µ j .In addition to Claim C.1, we prove the following lemma.Lemma C.4. Suppose for every j = 1, . . . , J, µ j = 2µ j-1 and the iterates w j of Algorithm 4 satisfy E F (j-1) ( w j ) -F (j-1) w ⋆ j-1 ⩽ δ j where w ⋆ j-1 ∈ arg min w F (j-1) (w) ,then,E      J j=1 µ j ∥w ⋆ J -w j ∥   2    ⩽ 16J J j=1 µ j δ j .Proof. Let P j def = j t=1 µ t w ⋆ j -w t , yielding that P J = J j=1 (P j -P j-1 ), with the agreement that P 0 = 0. Cauchy-Schwartz inequality givesEQUATION)Since P j is non-decreasing, to bound the above quantity, it suffices to bound each increment of the form P j -P j-1 . One can writeP j -P j-1 (a) ⩽ µ j w ⋆ j -w j + j-1 t=1 µ t ( w ⋆ j -w t -w ⋆ j-1 -w t ) (b) ⩽ µ j w ⋆ j -w j + j-1 t=1 µ t w ⋆ j -w ⋆ j-1 (c) ⩽ µ j (2 w ⋆ j -w j + w ⋆ j-1 -w j ) ,Now, let us substitute the bound on δ j from Remark C.2 and replicate the steps of Foster et al. (2019) to control the above. We getJ j=1 µjδj ⩽ 2 10 M 2 ∥w0 -w * ∥ 2 (T /J) 4 + 2 10 M σ 2 µ0(T /J) 3 + 2 5 σ 2 (T /J) + J j=2 2 10 M 2 δj-1 µj-1(T /J) 4 + 2 10 M σ 2 µj-1(T /J) 3 + 2 5 σ 2 (T /J) ⩽ 2 10 M 2 ∥w0 -w * ∥ 2 J 4 T 4 + 2 10 M σ 2 J 3 µ0T 3 J j=1 1 2 j-1 + 2 5 σ 2 J 2 T + 2 10 M 2 J 4 T 4 J j=2 δj-1 µj-1 ⩽ 2 10 M 2 ∥w0 -w * ∥ 2 J 4 T 4 + 2 11 M σ 2 J 3 µ0T 3 + 2 5 σ 2 J 2 T + 2 10 M 2 J 4 µ 2 0 T 4 J j=1 µjδj ,where the last inequality comes from the facts thatJ j=1 1 2 j-1 ⩽ 2 and J j=2 δj-1 µj-1 ⩽ J j=1 δj µj ⩽ 1 µ 2 0 J j=1 µ j δ j .Rearranging the terms and multiplying both sides by 144J, we get144J J j=1 µ j δ j ⩽ 9 1 -2 10 M 2 J 4 µ 2 0 T 4 2 14 M 2 ∥w 0 -w * ∥ 2 J 5 T 4 + 2 15 M σ 2 J 4 µ 0 T 3 + 2 9 σ 2 J 3 T .Choosing T > 2 11 /4 J M µ0 ensures that1 1-2 10 M 2 J 4 µ 2 0 T 4 ⩽ 2.Finally, substituting the derived bounds and the value of J = log 2 M µ0 , we conclude thatE ∥G F,α ( w J )∥ 2 ⩽ 9 • 2 15 M 2 ∥w 0 -w * ∥Proof. Part I. At first, let us assume that F is µ 0 -strongly convex. Applying Lemma C.3 and using the fact that (a + b) 2 ⩽ 2a 2 + 2b 2 , we getEQUATION)Lemma C.4 provides a control of the second term of the above inequality. To control the first term, let us apply Lemma C.2 with F (J-1) and w= w ′ = w J , getting α 2 G F (J-1) ,α ( w J ) 2 ⩽ F (J-1) ( w J ) -F (J-1) ( w + J ) ⩽ F (J-1) ( w J ) -F (J-1) (w * J-1 ), ∀α ∈ (0, 1 2M ]. Meaning, that G F (J-1) ,α ( w J ) 2 ⩽ 2δ J α . Let us recall, that J = log 2 M µ0 and µ J = 2 J µ 0 ⩽ M ⩽ 2µ J .Hence, choosing α = 1 4µ J and substituting the derived bound into ( 27), we deduce thatE ∥G F,α ( w J )∥ 2 ⩽ 36δ J α + 32(J -1) J-1 j=1 µ j δ j ⩽ 144J J j=1 µ j δ j .Let us substitute the bound on δ j from Remark C.2 to control the above. We getJ j=1 µjδj ⩽ 4M ∥w0 -w * ∥ 2 µ1 (T /J) 2 + 8σ 2 µ1 (T /J)µ0 + J j=2 8M δj-1 (T /J) 2 + 16σ 2 (T /J) ⩽ 8M µ0 ∥w0 -w * ∥ 2 J 2 T 2 + 32σ 2 J 2 T + 8M J 2 T 2 J j=2 δj-1 ⩽ 8M µ0 ∥w0 -w * ∥ 2 J 2 T 2 + 32σ 2 J 2 T + 8M J 2 µ0T 2 J j=2 µj-1δj-1 ⩽ 8M µ0 ∥w0 -w * ∥ 2 J 2 T 2 + 32σ 2 J 2 T + 8M J 2 µ0T 2 J j=1 µjδj .Rearranging the terms and multiplying both sides by 144J, we get144J J j=1 µ j δ j ⩽ 1152 1 -8M J 2 µ0T 2 M µ 0 ∥w 0 -w * ∥ 2 J 3 T 2 + 4σ 2 J 3 T . Choosing T > 4J M µ0 ensures that 1 1-8M J 2 µ 0 T 2 ⩽ 2.Finally, substituting the derived bounds and the value of J = log 2 M µ0 , we conclude thatEQUATIONPart II. When F is not strongly convex, let F µ (w) def = F (w) + µ 2 ∥w -w 0 ∥ 2 and w ⋆ µ ∈ arg min w {F µ (w)}. Applying (26) and Lemma C.3 with J = 1 and w 1 = w 0 , we getE ∥G F,α ( w)∥ 2 ⩽ 3 4 2 9 M µ T 2 log 3 2 M µ + 2µ 2 w 0 -w * µ 2 + 3 4 2 11 σ 2 T log 3 2 M µ . Since µ 2 ∥w ⋆ -w 0 ∥ 2 -µ 2 w ⋆ µ -w 0 2 = (F µ (w ⋆ ) -F (w ⋆ )) + (F (w ⋆ µ ) -F µ (w ⋆ µ )) ⩾ 0, then w ⋆ µ -w 0 2 ⩽ ∥w ⋆ -w 0 ∥ 2 .The proof is concluded. ■In order to derive statistical guarantees for the proposed method, we are going to instantiate the extension provided in the previous appendix.Proof of Theorem 5.1. Let us instantiate Theorem C.2. According to Lemma 4.1 and Lemma 3.4 we have thatσ 2 = 2 s∈[S]1-ps ps and M = βσ 2 . Setting β = T 8 log 2 T and µ = σ 2 /β, ensures that µ ⩽ M and thatT > 4 M µ log 2 M µ = T log 2 T log 2 T 8 log 2 T , ∀T ⩾ 2.For T larger than some large enough absolute constant, the conditions of Theorem C.2 are satisfied for the function F .Fairness guarantee. Theorem C.2 yieldsE ∥G F,α ( w)∥ 2 ⩽   3 4 2 6 σ 4 T 2 log 5 2 T 2 64 log 2 2 T log 2 2 T + 2 7 σ 4 T 2 log 2 2 T   ∥(Λ ⋆ , V ⋆ )∥ 2 + 3 4 2 11 σ 2 T log 2 2 T log 4 2 T 2 64 log 2 2 T + 3 4 2 11 σ 2 T log 3 2 T 2 64 log 2 2 T.Therefore, we have shown thatEQUATIONHence, the first part of Lemma 3.5 implies the fairness guarantee.Fairness guarantee with AC-SA. Theorem C.3 yields∥G F,α ( w)∥ 2 ⩽ 3 4 2 9 σ 4 T 2 log 3 2 T 2 64 log 2 2 T + 2 7 σ 4 T 2 log 2 2 T ∥(Λ ⋆ , V ⋆ )∥ 2 + 3 4 2 11 σ 2 T log 3 2 T 2 64 log 2 2 T.Therefore, we have shown thatEQUATION)Hence, the first part of Lemma 3.5 implies the fairness guarantee.Risk guarantee. The second part of Lemma 3.5 states thatR(π Λ, V ) -R(π Λ ⋆ ,V ⋆ ) ⩽ ( Λ, V) + ασ + α ∥ε∥ 2(2L + 1) • G α ( Λ, V) + log(2L + 1) β .Taking the expectation and applying the Cauchy-Schwartz inequality, we obtainE R(π Λ, V ) -R(π Λ ⋆ ,V ⋆ ) ⩽ E ( Λ, V) 2 + ασ + α ∥ε∥ 2(2L + 1) • E G α ( Λ, V) 2 + log(2L + 1) √ T .Recalling the value of α = 1 2 J+2 µ J ⩽ 1 2M from Theorems C.2 and C.3 and the fact that M = βσ 2 , we get ασ ⩽ 1 2βσ . Finally, applying (29)-( 30) and setting L = √ T , we obtainE R(π Λ, V ) -R(π Λ ⋆ ,V ⋆ ) ⩽ O σ √ T 1 + σ √ T ∥(Λ ⋆ , V ⋆ )∥ E 1 /2 ∥( Λ, V)∥ 2 + 1 T σ + ∥ε∥ T 3 /4 σ + log( √ T ) √ T .Above combined with Lemma B.1 yields the claimed bound. ■In this section we consider the case, when η and τ are unknown and estimated by η and τ . We denote by t(x)def = 1 -τ (x) p and r ℓ (x) def = η(x) -ℓB L 2. We consider the plug-in version of (5), defined as minΛ,V⩾0 E X LSE β λ ℓ -ν ℓ , t(X) -r ℓ (X) L ℓ=-L + L ℓ=-L ⟨λ ℓ + ν ℓ , ε⟩ . ( P LSE )Let us denote by F , the objective function of the above problem and introduceR β (π) def = E X   ℓ∈[[L]] r ℓ (X)π(ℓ | X) + 1 β Ψ(π(• | X))   .The gradient of F is given for any Λ, V ⩾ 0 byEQUATIONfor ℓ ∈ [[L]], s ∈ [K].Let us denote by g(Λ, V) the stochastic gradient of F , defined asEQUATIONforX ∼ P X and ℓ ∈ [[L]], s ∈ [K].We also define, by the analogy with the main body, a family of plug-in estimatorsEQUATION)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 proofs only depend on the nature of t via Lemma F.4. In particular, the key quantity to control isσ 2 = 2 s∈[K] E X (p s -τ s (X)) 2 p 2 s .Before, when we assumed the perfect knowledge of τ , the above was controlled by the Bhatia-Davis inequality, leveraging the fact that variance of τ s (X) appears in the numerator. It is no longer the case here. However, if one can build calibrated estimators, that is, estimators for which E X [ τ s (X)] = p s , the same machinery is applicable. In any case, even without requiring calibrated predictions, one can have a reasonable control of σ 2 building sufficiently accurate estimator τ s .That being said, results of Lemma 4.1 and Lemma 3.4 generalize line-by-line, replacing σ 2 by σ 2 and give supΛ,V⩾0 E X g Λ,V (X) -∇ Λ,V F (Λ, V) 2 ⩽ σ 2 and sup Λ,V ∥∇ 2 F (Λ, V)∥ op ⩽ β σ 2 .Moreover, the result of Lemma F.5 generalizes as well and gives sup Λ,V⩾0 ∇ Λ,V F (Λ, V) ⩽ σ.As in (19), we can show thatEQUATIONwhere the gradient mapping G F ,α is defined by analogy with G α = G F,α , discussed in the main body.Considering the SGD3 algorithm with the same choice of parameters, but replacing σ 2 by σ 2 , results in a control of G F ,α ( Λ, V) .Proof of Lemma 5.1. Fix Λ, V ⩾ 0. To ease the notation, we write π to denote π Λ,V within this proof. Similarly to the proof of (21) from Lemma 3.5, one shows that for all Λ, V ⩾ 0ℓ∈[[L]]s∈[K] E π(ℓ | X) t s (X) -ε s 2 + = ∥(-∇ F (Λ, V)) + ∥ ∀ℓ ∈ [[L]], s ∈ [K] . Recalling that U s ( π, ℓ) = |E [ π(ℓ | X)t s (X)] |, triangle's inequality combined with the above yields ℓ∈[[L]]s∈[K] (U s ( π, ℓ) -ε s ) 2 + ⩽ ∥(-∇ F (Λ, V)) + ∥ + ℓ∈[[L]]s∈[K] E[ π(ℓ | X)| t s (X) -t s (X)|] 2 .Cauchy-Schwartz inequality givesℓ∈[[L]]s∈[K] E[ π(ℓ | X)| t s (X) -t s (X)|] 2 ⩽ s∈[K] E     ℓ∈[[L]] π(ℓ | X) 2   | t s (X) -t s (X)| 2   . Since ℓ∈[[L]] π(ℓ | X) = 1, then ℓ∈[[L]] π(ℓ | X) 2 ⩽ 1. Thus, we have shown that ℓ∈[[L]]s∈[K] (U s ( π Λ,V , ℓ) -ε s ) 2 + ⩽ -∇ F (Λ, V) + + E 1 /2 ∥ t(X) -t(X)∥ 2 .We conclude using (34). ■Proof of Lemma 5.2. Fix Λ, V ⩾ 0. To ease the notation, we writeπ def = π Λ,V and π ⋆ def = π Λ ⋆ ,V ⋆ , within this proof.As in the second part of the proof of Lemma 3.5, we haveR β ( π) + F (Λ, V) ⩽ ∥(Λ, V)∥ + α σ + α ∥ε∥ 2(2L + 1) G F ,α (Λ, V) . (35) Furthermore, since ∥∇ LSE β (•)∥ 1 ≡ 1, we have | F (Λ, V) -F (Λ, V)| ⩽ E max ℓ∈[[L]]|r ℓ (X) -r ℓ (X)| + ∥λ ℓ -ν ℓ ∥∥t(X) -t(X)∥ ,and | R β ( π) -R β ( π)| ⩽ E[max ℓ∈[[L]] {|r ℓ (X) -r ℓ (X)|}].The last two displays combined with (35), givesR β ( π) + F (Λ, V) ⩽ E 2 max ℓ∈[[L]] |r ℓ (X) -r ℓ (X)| + ∥λ ℓ -ν ℓ ∥∥t(X) -t(X)∥ + ∥(Λ, V)∥ + α σ + α ∥ε∥ 2(2L + 1) G F ,α (Λ, V) .Observe that min Λ,V⩾0 F (Λ, V) = -R β (π ⋆ ). Using triangle's inequality and the fact thatmax ℓ∈[[L]] ∥λ ℓ -ν ℓ ∥ ⩽ √ 2∥(Λ, V)∥, we conclude recalling that R(π)+ log(2L+1) β ⩾ R β (π) ⩾ R(π)for any randomized prediction function. ■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 thatLSE β (w) = max p∈∆ ⟨w, p⟩ - 1 β Ψ(p) ,where ∆ is the probability simplex in R m and Ψ(p) = m i=1 p i log(p i ). 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 a = (a 1 , • • • , a m ) and β > 0. Define log-sum-exp and softmax functions respectively asLSE β (a) def = 1 β log m i=1exp(βa i ) and σ j (βa)def = exp(βa j ) m i=1 exp(βa i ) j ∈ [m] .The LSE property is as followsmax{a 1 , • • • , a m } ⩽ LSE β (a) ⩽ max{a 1 , • • • , a m } + log(m) β .Moreover, σ(βa) = ∇ LSE β (a), and σ(βa) is β-Lipschitz. Lemma F.3 (Bhatia and Davis (2000) ). Let m and M be the lower and upper bounds, respectively, for a set of real numbers a 1 , • • • , a n , with a particular probability distribution. Let µ and σ 2 be respectively the expected value and the variance of this distribution. Then the Bhatia-Davis inequality states:σ 2 ⩽ (M -µ)(µ -m) .Lemma F.4. It holds thatE X   s∈[K] t 2 s (X)   ⩽ s∈[K] 1 -p s p s ,where t s (x) = 1 -τs(x) ps .Proof. We have E X [τ s (X)] = p s and 0 ⩽ τ s (X) ⩽ 1 almost surely. Using Bhatia-Davis inequality written in Lemma F.3, we deduce thatE X   s∈[K] t 2 s (X)   = s∈[K] Var τ s (X) p s = s∈[K] 1 p 2 s Var (τ s (X)) ⩽ s∈[K] 1 -p s p s .The proof is concluded.■ Lemma F.5. Let σ 2 def = 2 s∈[K] 1-ps ps . It holds that ∥∇ Λ,V F (Λ, V)∥ ⩽ σ + 2(2L + 1) ∥ε∥.Proof. By Jensen's inequality∥∇ Λ,V F (Λ, V)∥ 2 = ∥E X [g Λ,V (X)]∥ 2 ⩽ E X [∥g Λ,V (X)∥ 2 ] .Recalling the definition of g Λ,V , given in (11), we haveE X [∥g Λ,V (X)∥ 2 ] = E X ℓ∈[[L]]s∈[K] (σ ℓ (•)t s (X) + ε s ) 2 + (-σ ℓ (•)t s (X) + ε s ) 2 = 2E X ℓ∈[[L]]s∈[K] σ 2 ℓ (•)t 2 s (X) + ε 2 s ⩽ σ 2 + 2(2L + 1) ∥ε∥ 2 ,where the last inequality comes from the proof of Lemma 4.1.The proof is concluded. ■Evaluation measures. We useD test = {(x ′ i , s ′ i , y ′ i )} m i=1 to collect the following statistics of any (randomized) prediction π R(π) def = 1 m m i=1 +∞ -∞ ( y -y ′ i ) 2 π(d y | x ′ i ) , U s (π) def = sup t∈R 1 m s m i=1 t -∞ π(d y | x ′ i )I{s ′ i = s} - 1 m m i=1 t -∞ π(d y | x ′ i ) ,which correspond to the empirical risk and the empirical group-wise unfairness quantified by the Kolmogorov-Smirnov distance of a randomized. We note that our classifier is supported on a finite grid, thus all the integrals involved transform into weighted sums. Agarwal et al. (2019) build multi-class classifiers h k : R d → Θ, where Θ is some finite grid over R and k = 1, . . . , K, that come with weights (w 1 , . . . , w K ) ⊤ such that w k ⩾ 0 andK k=1 w k = 1. Then, they build a randomized classifier π(• | •) such that supp(π(• | x)) = Θ and for each θ ∈ Θ P( Y π = θ | X = x) = K k=1 w k I{h k (x) = θ} .Thus, integrals appearing in R and U s reduced to finite sums for both methods. 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 SGD3 are more stable in the low unfairness (high fairness) regime. We compare our method with the ADW method. We train ADW 2 times: we use D train and D unlabeled as training set for ADW-1, whereas for ADW-2 we use only D train . We take the set {(2 -i , 2 -i ) i∈I }, where I = {1, 2, 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 unfairness for convergence for ε = (2 -8 , 2 -8 ) unfairness threshold. We also illustrate the comparison of our model with ADW-1, ADW-2 and base models. 1 .Additional experiments on a synthetic dataset. We conduct an additional experiment to demonstrate the results of Algorithm 1 in the case of multiple sensitive attributes. We generate a synthetic dataset D n = (X i , S i , y i ) n i=1 of n = 2000 points, where(X i ) n i = (X i1 , X i2 , X i2 ) n i ∼ N (0, 1). We choose S i = 0 if X i1 ⩽ -0.7, S i = 1 if X i1 < 0, S i = 2 if X i1 < 0.7 and S i = 4 if X i1 ⩾ -0.7. For i ∈ [n], we generate y i = 4 3 j=1 X ij + X i1 + ξ i , where ξ = (ξ i ) ni ∼ N (0, 1). We split D n into train, unlabeled and test datasets with proportions of 0.4 × 0.4 × 0.2. We use (X train , y train ) to train the base estimator, (X train , S train ) to train the classifier and X unlab 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. This experiment is for visual representation of the Algorithm 1 in the case of multiple sensitive attributes, thus we do not collect further statistics. Constraints introduce additional challenges, but are not relevant for this discussion.To be more precise, the optimization error is automatically handled by the control of the gradient.The code is available at https://github.com/taturyan/unaware-fair-reg.The experiments are conducted on a Processor 11th Gen Intel(R) Core(TM) i7-1195G7 2.90GHz with 16GB RAM. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper presents a post-processing algorithm designed to enforce demographic parity in regression tasks without access to sensitive attributes during inference.
strength_weakness: strength_weakness: 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. 

The 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.

There 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.
questions: 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?

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?

Reference [1] addresses a similar topic with a minimax approach. Is this minimax result applicable or relevant to the methodology used in your paper?

In Algorithm 1, "DP" is mentioned in the name. Could you specify what "DP" stands for?

The algorithm "fairname" appears in line 305 without a prior definition. Could you explain what this term means within the context of your study?

[1]  Fukuchi, Kazuto, and Jun Sakuma. "Demographic parity constrained minimax optimal regression under linear model." Advances in Neural Information Processing Systems 36 (2024).
limitations: limitations: Not applicable.
paper_summary: paper_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}$.
strength_weakness: strength_weakness: Typos: 
* falls withing -> falls within (page 2)
* statisitcal properties -> statistical properties (page 5)
* out approach -> our approach (page 7)
* phenomenons -> phenomena (page 7)
* outperfomce -> outperform (page 8)
questions: questions: In practice, how do we pick algorithm parameters such as L, B and \beta?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper considers post-processing regressors to satisfy the group fairness criterion of demographic parity, in particular, under the attribute unaware setting.

1. 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.

2. 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 (\*).

3. The paper closes with empirical evaluations of the proposed algorithm.
strength_weakness: strength_weakness: 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.
2. 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?
3. 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.

[3] https://arxiv.org/pdf/2006.07286
questions: 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: limitations: - See weaknesses.
- 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].

Comments: comment: I thank the authors for their elaborate rebuttal. This does address my concerns and questions.
Thank you for the the response, which has addressed most of my concerns. I believe the authors will improve the readability in the final version. I am no longer opposed to the acceptance of this paper and will adjust my score accordingly.
The reviewer thanks the authors for the response, and think the readers would appreciate if these points are highlighted in the main body.  The reviewer has raised their score.
We appreciate the reviewer's feedback. In Lemma B.1 (Appendix B, line 518), we show that discretization increases the risk by $4B/L + 1/L^2 + \log(2L+1)/\beta$. Additionally, as demonstrated in the proof of Theorem 5.1 (Appendix D, line 615), setting $L = \sqrt{T}$ achieves a risk rate of $1/\sqrt{T}$. Therefore, we use $L = \sqrt{T}$ in our experiments, resulting in $2\sqrt{T} + 1$ bins, where T is the number of unlabeled samples. We also note that using more bins wouldn't improve statistical performance but would complicate the optimization due to higher dimensionality. Hence, we adhere to the theoretically recommended setting in practice.
The reviewer thanks the authors for the response.

Could the authors also (briefly) comment on how the number of bins is chosen (in the experiments), and how it affects performance (theoretically)?