Privacy Budget Tailoring in Private Data Analysis
Authors: Daniel Alabi
Chris Wiggins
Venue: Accepted by TMLR ()

Abstract: We consider the problem of learning differentially private linear and logistic regression models that do not exhibit disparate performance for minority groups in the data. Small-sized datasets pose a challenging regime for differential privacy; that is, satisfying differential privacy while learning models from data can lead to models with worse accuracy for minority---in size---subgroups. To address this challenge, inspired by Abowd & Schmutte (2018), we propose: (i) to systematically tailor the privacy budget to the different groups, (ii) use linear optimization oracles in a grid to optimize Lagrangian objectives that correspond to fair learning and optimization. We present efficient differentially private algorithms for linear and logistic regression subject to fairness constraints (e.g., bounded group loss) that allocate the privacy budget based on the private standard error of each subgroup in the data. Consequently, the formulation reduces the amount of noise added to these groups, which leads to more accurate models for such groups. We validate the proposed, group-aware budget allocation, method on synthetic and real-world datasets where we show significant reductions in prediction error for the smallest groups, while still preserving sufficient privacy to protect the minority group from re-identification attacks. In addition, we provide sample complexity lower bounds for our problem formulation.

Published in Transactions on Machine Learning Research (12/2023)
Privacy Budget Tailoring in Private Data Analysis
Daniel Alabi
alabid@@cs.coaambiiccce edu
Cohumbia University
Chris Wiggins Columbia University
chris. wwwgginn@@@kkummicc.c.. edu
Reviewed on OpenReview: https: /ttts:://operrvvieet net/ forun? id= SnPEWMyyYX
Abstract
We consider the problem of learning differentially private linear and logistic regression models that do not cxhibit disparate performance for minority groups in the data. Small-sized datasets pose a challenging regime for differential privacy; that is, satisfying differential privacy while learning models from data can lead to models with worse accuracy for minority in size subgroups. To address this challenge, inspired by Abowd & Schmutte (2018), we propose: (i) to systematically tailor the privacy budget to the different groups, (ii) use linear optimization oracles in a grid to optimize Lagrangian objectives that correspond to fair learning and optimization. We present efficient differentially private algorithms for linear and logistic regression subject to faimesss constraints (c.g.. bounded group loss) that allocate the privacy budget based on the privale standard error of each subgroup in the data. Consequently, the formulation reduces the amount of noise added to these groups, which leads more accurate models for such groups. We validate the proposed, group-aware budget allocation, method synthetic and real-world datasets where we show significant reductions in prediction error for the smallest groups, while still preserving sufficient privacy to protect the minority group from re-identification attacks. In addition, we provide sample complexity lower bounds for our problem formulation.
1 Introduction
Learning predictive models that satisfy diffcrential privacy (DP) (Dwork et al., 2006) worst-case crypto- graphic privacy definition an increasingly imporlant requirement healthcare (Pfohl et al., 2019), social science (Evans al., 2023), and federated learning (McMahan et al., 2017). Overparametrized deep models increasingly memorize portions of the input training data (Carlini al., 2020); however, such memorization behavior is neutralized when these models optimized via differentially private procedures (Carlini et al., 2018; Chen et al., 2020). Despite such benefit, Bagdasaryan et al. (2019) show that models optimized to satisfy DP via privatized versions of (stochastic) gradient descent (DPSGD) (Bassily et al., 2014; Chaudhuri et al., 2011; Abadi et al., 2016) have worse performance test accuracy for example- for minority (in size) groups in the data if the privacy budget split. equally amongst all groups. Disparate performance due DP hampers its deployment in high-stakes applications like healtheare (Santos-Lozada et al., 2020) and synthetic census data release (Petti & Flaxman, 2019; Kenny et al., 2021). Consequently, we consider the challenge of learning differentially private models-from from data via (stochastic) gradient descent- do not exhibit disporate performance for minority subgroups in the data.
The key insight in our proposed approach is to apportion the privacy budgel across different subgroups in the data. We propose a two-stage group-aware scheme which we instantiate this insight in the linear regression setting. The proposed algorithm can handle the case where an individual can be in multiple groups. While we instantiate our formulation for linear regression, the key idea of allocating the privacy budget across sub-groups in the data can be applied more broadly.

---

Published in Transactions on Machine Learning Research (12/2023)
First, we estimate the standard error (SE) of the prediction across sub-groups in the data for 'precursor' model. We then assign the privacy budget for DP according to the estimated SE, of the predictions aaaectioonaallcatinng more privacy budget to subgroups with higher standard error. Larger standard errors in a particular group suggests a form of underfitting and structural uncertainty in the group statistic; hence, larger DP noise addition to such groups exacerbates the uncertainty in the parameter estimates for these groups.
We justify the group-aware privacy budget allocation with a theoretical analysis of an idealized 2-mixture of Gaussians model (in Lemma 3.1). We analyze the expected loss of randomized linear regression coefficient vector on the mixture model, and show that naively applying differential privacy disadvantages the group with higher standard prediction cyror-typically the smaller group.
In the second stage, we use the privacy budget allocation to learn DP linear regression estimates via gradient descent. Private versions of gradient descent typically involve gradient clipping and calibrated Gaussian noise addition. Group-aware privacy budget allocation based on standard errors of the prediction across groups results in less noise addition to groups with larger standard errors of the prediction.
A potential objection to the proposed formulation is that relaxing the privacy requirement for minority subgroups will make these input groups more susceptible to privacy attacks. Indeed, this could be the case if cantion is not exercised. However, recent empirical findings show that models produced by private (stochastic) gradient descent. with even minimal levels of privacy (budget of <=89) are still effective at stemming re- identification attacks (Carlini et al., 2018). Also, as suggested by one of the reviewers of this work, it might be better to set minimum or target level for the privacy budget for the minority subgroup(s) and then calculate an overall budget for the end-to-end scheme. We leave this choice to the framework designer. Also, since we build upon previous work on Lagrangian fair regression (Agarwal et al., 2019), the majority group might incur slightly larger error so that the minority groups could gain in predictive accuracy. As per DP guarantees, we operate with zero- Concentrated differential privacy (zCDP) and track the budget of our proposed mechanisms with p. A mechanism that satisfies p-ZCDP also satisfics (c, d) = (p + poolog((1)))) 8D for all 5 > 0, and equivalently, DD satisfies e² 2/222CDP (Bun & Steinke, 2016).
The two-stage formulation that we present can also be extended to incorporate user-defined 'fairness' objectives like bounded sub-group loss. To accomplish this, we consider a lincar regression formulation subject to bounded subgroup loss (BGL), and show how to incorporate the constraint into reformed objective using the Lagrangian approach of Agarwal et al. (2019). We then solve the Lagrangian formulation using the group aware approach we proposed here.
We evaluate the performance of the two-stage group-aware DP linear regression formulation and the fair constrained versions across synthetic and real world datasets. We find that the proposed two-stage formulation results in a 10% to 50% reduction in the mean standard prediction error for the smallest groups in the data both for traditional differentially private learning and the fair Lagrangian setting. Taken together, the empirical results suggest that group-aware allocation of the privacy budget can ease the disparate utility impact of differential privacy.
A series of closely related works (Xu el al. (2020), A Abowd& & Schmutte (2018), and Tran et al. (2021a)) consider a setting similar to ours. Xu et al. (2020) propose DPSGD-F, which adaptively performs gradient clipping and noise addition to groups in the data. Abowd Schmutte (2018) allocate the privacy parameter to subgroups in the data, but focus on estimating the resulting economic costs of such decision. In particular, bowd & Schmutte (2018) treat privacy budget allocation as resource allocation problem via an economic lens: choose budgets such that the marginal cost of increasing privacy equals the marginal benefit. In our case, we just use statistical properties of the dataset itself for resource allocation. Another related work is that of Tran et al. (2021a) which studies the underlying cause of disparate impact for output perturbation and DP-SGD, and find that the noise due to privacy, gradient clipping, and a group difficulty term captured by the based trace of the hessian of the loss govern the underlying group disparities. These findings align with ours, but we focus on the privacy budget, which is the fundamental parameter that determines the level of noise added to each group.
To conclude, we summarize our contributions follows:
2

---

Published in Transactions on Machine Learning Research (12/2023)
We present two-stage, end-to-end differentially private, scheme for linear regression that maintains 'reasonable' performance for minority subgroups in the data. To do this, we allocate the privacy budget towards different subgroups in the data.
We conduct extensive empirical evaluation of the two-stage formulation for synthetic and real world data sets and observe 10% to 50% reduction in mean square standard prediction error for the smallest groups across scttings.
2 Background and Linear Regression with DP
In this section, provide overview of notation, definitions, and problem formulation.
Setup. Let X denote the domain of non-sensitive features, A the domain of sensitive attributes, and y correspond to the set of possible labels. We take Cp to denote a decision set from which a regression coefficient. vector 0 is chosen. For example, Cp can be the space of P-dimensional real vectors i.e, Cp = R.. We use the random variable (X, A)) to specify joint distribution over (X, A.,A)) and X, A, Y to represent marginal distributions over A,A, respectively. Given any dataset with row size n, we can categorize by sensitive and insensitive attributes follows: Z = (Zx; Za) (Zxy, Za) where Z E A", Zxy E (X x y)"" For example, A could be the set of all possible outcomes a HIV medical test: }+,-}. Obviously, due lo state and federal privacy law, the results of a HIV test cannot be released without permission or without some form of explicit privacy protection mochanisms; thus, A is sensitive. On the other hand, zip code might be considered a non-sensitive attribute.
Remark. We assume that the dataset size, n, (and the size of all subgroups) is public information.
The notion of privacy that consider in this work is record-level (bounded) differential privacy. Our framework can also be instantiated in the unbounded (add-remove instead of swap) DP model without much modification.
Definition 2.1 Cenc-CConeetrrteed differential Privacy (Bun & Steinke, 2016)). An algorithmm M:2" 2 + RR is P zero-concentrated differentially private (zCDP) for all neighboring z' E z", D,(M(22),Me in, for all 7 E 00), where [A] B) is the 7éRéngi divergence between random variables A and B. The randomness is over the coin flips of the algorithm M. The privocy budget allocated to all groups is p.
Definition 2.1 reduces to standard pure DP (Dwork et al., 2006) as ? co.
Fairness Definitions. For this paper, we will focus on a single notion of fairness: Bounded Group Loss (BGL). Intuitively, BGL requires that the prediction error for any protected group remain below certain pre-specified level. A more formal definition is given in Definition 2.2.
Definition 2.2 (Bounded Group Loss (Agarwal et al., 2019)). Let 0 be a predictor over (X, A,Y. Then Cr satisfies Bounded Group Loss if Va E A, (((((,0(X)) loss function we wish to mènimize and Ta is loss constraint for group E A.
= a) S Aa; where f: x X R is a
Linear Regression with Differential privacy (e.g., see (Alabi & Vadhan, 2022; Alabi, 2022) and references thercin). To set the stage, we work through DP Gradient Descont for linear regression. Given a dataset Z = ((x,, y1) Vi= suppose that Cp C R... We consider a function, h : Cp + R, defined as (0) = E x,) - y:)² with gradient: Vh(0) 2
n E. (0, x,) - y:) E TR... To optimize with xCDP, we add Gaussian noise to the gradients Vh while optimizing for 0. This formulation requires two important seper-parameters (1) T: the number of gradient calls to Vh, and (2) A: clipping bound. The mumber of iterations determines how the privacy budget, p is apportioned. For any neighboring databases 2, 2' and query g. if [g(2) - q(=') < A for finite A, then we can satisfy p-zCDP. In general, gradicnts can be unbounded so to satisfy cDP, we clip the gradients to lie in a certain range.
3 Group-Based Privacy Budget Allocation & Langrangian Fair Regression
In this section, we provide justification for the need to allocate the privacy budget in DP groups in the data in order to mitigate disparate model performance. To do this, consider mixture of 2 Gaussians and
3

---

Published in Transactions on Machine Learning Research (12/2023)
analytically derive the expected prediction risk for the case where single predictor is learned from data. This analysis provide insight into how DP regression exacerbates performance disparity. Consequently, we arrive at the natural insight that tailoring the privacy budget to groups in the data based on the standard helps mitigate performance disparity. In the second subsection, we
error of an initial- prael--pperusoo-prrraee describe the Lagrangian formulation for fair regression.
3.1 Mixture Model Analysis for Standard Error
Consider a mixture model of two groups, for a linear model, where the output for each group is derived as: Y1 ~ (X,,,,,, (fmix)))
Y2 ~ -(Xx382.03//xxx))) and where X1 E RT xd X2 E R are the design matrices. Y1 E R Y22 E R are the dependent variables. In this model, 01,02 characterize the inherent noise in the dependent while 31 E IR are the regression coefficients.
Suppose we wish to learn single linear predictor, B, for the mixture model c of + (1-c) c)- (xx23 of xmnz)) for any c 1). Learning prodictors with low error, in this case, can be achioved via randomization. In particular, to learn a single predictor when group membership is unknown, one predictor is to prodict 31 with probability e and B3 with probability (1 1--0 c). Now we state the expected square loss for this predictor.
Lemma 3.1. For any E (0.1), 31, 32 E Rd, EIE , X2 E RU 01,02 > 01 n2 E E+, define the mixture model Y ~ cN(X131 In xn.) (1- c),(X223, o3Inaxns) ~ cYi + (1-ccJy c)y². Let 3 = 3 with probubilily e and 3- = 32 with probubility 1 1 c, then the prediction Y is Y1 with probubility e and Y2 with probability (1-c). The expected prediction loss of 3 on Y is c2.nn, (1-c)2
where Ii= = ||/ 1231112,1 122 || x1 C xi, and xi is the chi-squared distribution with degrees of freedom.
We refer to the appendix for a proof of the Lemma. As shown, the expected square loss for the optimal predictor is c². mn,n,,Co
= || -| 3213. where I, || -x33 12,1; C ~~ x2, and xi is the chi-squared distribution with one degree of freedom. The errors from c² =ixio and (1-c)² - can be controlled if 01 or 02 is small. On the other hand, the upper bounds of T2 and r2 depend on how much 8i differs from B2 based on fit. to either Yi, Y2.
Why allocate privacy budget based on standard errors? Consider a dataset consisting of two groups G1 = =X,, Yi), G2 = (X2, Y2) where G1 has strictly larger size than G2 and G1 has smaller prediction standard error than G2. We wish to minimize the le loss of a differentially private regression estimate via DP gradient descent, across these groups, which is equivalent to minimizing: I, (3, A, Pl, m1) = ii E (Y,s - (X1,, 3) + (1, T,33, X1, N1 pI, m1) and (22 A, P2, n2) 1 E (Y2: (X2,, 3)) P2, n2) L(8 X2, Y2) N2(A, (2. where (1, P1. m1) and N₂(A, P2. n2) are the random variables that ensure that the losses (and their gradients) satisfy 2CDP - for DPGD. Here (1 p,m1) ~ (O, A (22p))) can be used for p-zCDP release if 3 is public and A is bound on the per-example squared residuals. Up to scaling factors, Tn & Ta correspond to the standard errors for G1 & G2 respectively.
m2
To illustrate the source of the disparate impact incurred due to DP, let pt P2 = p/2 and suppose that the estimate B is computed on the entire dataset. Without fairness constraints, the optimizer will aim to minimize average loss by prioritizing minimizing loss on the laryer group or the group with smaller standard errors, resulting in B. Further with DP, the noise added will be agnostic to the relative sizes or standard errors across groups. As a result, for a fixed privacy budget of p = P1 + P2: we have the inequality, with high probability: L, (8, (1, m1) (3, X2, Y1)= S L2(8, A. R2)) L(8, X2, Y2), which could result in disparate impact that is not necessarily present in the non-private case.
To resolve the disparate impact issue, we need mechanisms that will make Nı (A, P1, n1), randomized function of only two tunable quantities (A, p), strictly greater than N2(A, m2). As a result, we can either decrease A -which could result in further statistical measurement error or increase the privacy budget PI or P2- Furthermore, the "right" " scaling for P1 versus P2 should alleviate the non-private standard errors disparity in L, Lzz, thus justifying our allocation strategy by scaled standard errors. This strategy might increase the average loss for the larger group (provably relatively small increase for larger groups which goes to as n + 00) but decrease the average loss for the minority group. However, as we will see in our empirical
4

---

Published in Transactions on Machine Learning Research (12/2023)
results we find, perhaps surprisingly, that our proposed strategy does not always hurt the performance in the majority group.
Using a simplified generative model, Lemma 3.1 illustrates that a mixture model has expected prediction error that scales with the standard deviation of each identifiable group. This informs our privacy allocation strategy based on standard errors. Concretely, a differentially private release of T2 Fi >i= (Vi (X1,,32)) 2 + (1 p) where lo represent a clipping operation lie between 0 and A and Ni p) the noise distribution (for DP) that is function of the clipping parameter A and the privacy parameter p. For example, NN1 (A, p) (0, A? /(2p)) is a p-zCDP release for clipping parameter A. A similar calculation be done for releasing 1 and quantifying the release via (2 p) = E (Y2; (Y2; (X2,, (1)) + N2 p) For large enough clipping parameter, the estimator F2 (2 p) will be more accurate if N2(A, p)
A + does not overwhelm the signal in A. This is more likely to happen if the standard error (and/ou or the sample size) the group is large enough.
3.2 Solving the Lagrangian Formulation of Fair Regression
We now setup the langrangian formulation for fair linear regression, which fits under the constrained group- objective optimization formulation of Agarwal et al. (2019). In Section 4, we present algorithms to optimize this formulation.
Za), Sctup and Notation. Given datasct, Z (Zx, ZA), with K |Al groups, and hypothosis class, Cp, the Lagrangian formulation for fair regression requires: 1) Group Losses: The function é Cp x (X' x y x A)" + [0, 1] that gives the average loss for each group for predictor 0 E Cp on the dataset Z; 2) Total Ggnustt Loss: f 10, + R which gives the average loss for all groups; 3) Group-Deviation Loss: g: [0. 11K + R a measure of loss deviation across groups.
Consider the composition of functions fol: Cr x (X' x y A)" + R and g go : Cp (X' x A)" R. can for any 0 E Cp, and >> 0, a Lagrange multiplier, define the Lagrangian: h(8, Z) f ((0, Z) + G max(0. Z)). The function h has gradient
To minimize f of subject to constraint on g o
Vh(0, 7) G-1(g(E(0.Z)) 2 0)Ve((.2)VV(((0...
Z))+
(1)
(2)
where 2) is P K matrix of the gradient of E(0, Z) (or the transpose of its Jacobian), and Vg(((0, Z)) is K x column vector representing the gradient of g.
The Langrangian incorporates the constraint function while minimizing f. Following Agarwal el al. (2019),
the Lagrangian for linear regression with BGL (definition 2.2) can be stated as follows:
n Σ U (z;)))
da 1 [4, = a1) 1]
Σ na
min SECP
n
Solving the formulation above is challenging because there is no efficient algorithm for selecting the Lagrange multipliers in the general case. Agarwal et al. (2019) give a two-player game that eventually converges to an equilibrium. However, this game is not guaranteed to converge in polynomial time. Consequently, we use the constrained group objective optimization (CGOO) formulation to sidestep this issue. We now define the CGOO problem.
+ Definition 3.2 (Constrained Group-Objective Optimization: CGOO(n, K,J,g, Z, a)). : + be function we wish to minimize subject a constraint function g: [0, 1] + R. Specifically, for any excess risk parameler a > O, decision set C, and any datasel, Z, we wish to obtašn a decision Ô E C such that
f(E(0, Z)) < min
{e Z)) + g(e(0, ()) aa
(4)
0EC:g(((P.2)50
Any procedure that takes input Z and returns decision ô E C that satisfies Equation 4 a Constraèned Group-Objective optimization algorithm that solves the problem specified by CGOO(n, K, K. 9, l, Z, a) 0.
5

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm 1 Stage 1: r-CCDP Standard Errors Computation for All Groups in Linear Regression
Input: Z E (X' x y A)", K,
Split dataset
(X,Y.4) 4) into ZI...., Zx for K |Al groups as follows:
X2,X2,.... Xx Raxd
Y1, 12...... Yk= E R=
5: n1, R2,..... nK integers
6:
7: T =T((K + 1)
8: Use budget of Tk/2 to sample X7 v, differentially private estimate of X X
9: Use budget of 7x/2 to sample XTY, a differentially private estimate of X
10:
11: Amin (XTX) < 0 then
12: // Returns "no information" or alternatively, halt/terman termmnate
13: return 1/VK- 1g
14: end
15: // Calculate DP estimate of regression coefficients entire dataset.
16: β (XTX) -XTX)-IXXTX -XTY
17: for k = to k = K do
18: S = E (YAs (YRs (Kk,, B11310² +NN(0,A/(2m)))
19: if S S 50 then
20: return 1/VK 1k
21: end
22: 8k-
nE
23: end for
24:
Normalize 81, ,K that b =1
8 return $1, .2..,, SK
25:
the Lagrangian setup, f, and g are convex and Lipschitz, we can apply convex optimization algorithms that will result in a solution close the global optima in time polynomial in n, P. K. Given these properties, can solve the optimization problem using modified versions of (stochastic) gradient descent algorithms.
4 Group-aware DP Fair Regression
We now present our end-to-end differentially private two-stage algorithm for linear regression. The algorithms present also directly address the Lagrangian fair regression problem discussed in Section Even though focus on linear regression in this work, our privacy allocation strategy is a meta-strategy that can be used for other estimators.
In the first stage, we estimate a precursor differentially private regression model on the data. We then calculate the standard error of the predictions for this regression model across all subgroups in the data. Given group standard error estimates, we allocate the privacy budget to prioritize groups with larger standard error of the prediction-i.c. more privacy budget allocated to such groups. In the second stage, we solve the constrained linear regression formulation described in Section 3.2. Assuning that the gradient calls take constant time, it is easy to see that Algorithm 1 and Algorithm 2 runs in time O(K max nk). In Algorithm 1, by using a privacy budget to sample a matrix, we mean that we compute the matrix in a differentially private manner (e.g,, via the use of the exponential or gaussian mechanism). Also, we assume that the groups can overlap so we have to split. the privacy budget for the K groups. there is no overlap, we can apply parallel composition- without splitting the privacy budget (Kairouz et al., 2017).
Setup & Notation. In Algorithms and for any 2 1, 1a is the all-ones d-dimensional vector and laxd is the identity diagonal d d matrix. We rely on standard methods (e.g., see (Dwork et. al., 2014)) to obtain differentially private estimates of XT X, XTY, which are the variance and covariance matrices respectively

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm 2 Stage 2: 4-zCDP Gradient Descent for Langrangian Fair Regression
Input: Z E (X' x x A)" St, A, 2 1, l > 0, G 0 ...........
Obtain DP standard errors $1, $2...., SK from Algorithm 1 Like in Algorithm 1, split dataset Z (X, Y, A) into 71...., ZK for K |A| groups Arbitrarily set 01 Cp
5: for t = to t == T do
6: for k = to k= K do
7:
(0, 2) = =E= 20, Xks) Y = = (0,, Vis)
8:
(0,,,,) = =E ((0, Xk.) Ynu)
>==)==>> ='m1
mhe la (0, XAi, Yks)
Use budget of pr p. (2T) sample M as follows:
10:
(O, 7) ni E (0, 10, 11)1 (fz-norm per-example gradient clipping)
11:
M = (c, 7) No0 pxP
A²
2p0
12:
Use budget of pr p p. / (2T") to sample M2 as follows:
(0 2) 1 " شim (0, Xkin Yue) laa
13:
14:
M = L 2) + NN0, 2
A²
15:
end for
Vh(O,, Z) using M1 = (M) ,, E Pxk and M2 = (MM....,,KN) E RxX1 (via Equation 2)
16:
as follows:
17:
Vh( Z) M1 (M2) +G- (G) ()22))
18:
O2-1- -Icc (0. 7/e Vh(0,, 2))
19: end for
20:
return 0,
(see Lemma D.1 in the appendix for proof details and mechanism for exact computation). We use là to denote the clipping operator. For scalar v, vl returns v clipped to lie the range [0, A]. For vector V, VIA returns V clipped such that its fe-norm is at most A. standard way to perform this operation is to return Z/ max(1, 1
Stage Standard Error Estimation. First, we estimate, privately, the standard error of the prediction for a single linear regression model fit on data for all groups. Intuitively, the coefficients for this model will have higher structural uncertainty and standard error of the prediction for the smaller groups in the data. We then partition the data into K groups and estimate each group's standard error by computing 8% IV= & l//n - d but with noise added to ensure xCDP for the 'global' regression model B. Following previous work, we also assume that the group sizes, RI...., RK,, are public, but that the record-level data is not. We allocate a privacy budget of T/K for each group's standard error computation and normalize so that their squares sum to 1.
Lemma 4.1 (Lemma C.1). For any
0, Algorithm is T-2CDP
Stage 2: DP-based optimization. In this stage of the formulation we use the privacy budget allocation from the first stage to learn a single linear predictor that satisfies the CGOO formulation (Section 3) via a differential private gradient descent scheme. Regular linear regression corresponds to the CGOO formulation without any fairness (Bounded Group Loss) constraints. We refer readers the appendix for version of Algorithm 2 for linear regression without fairness constraints. In this setting, we perform budget allocation follows: for any i E [K], allocate μ & budget to calculating la (c Z) and Vla Z). Recall that la is the loss for group k and Vule, Z) is its gradient.
We implement DPGD following the algorithm of Bassily et al. (2014) specialized to the ordinary least squares objective. For any fixed privacy budget μ > O, we allocate p/2 to and 1/2 to Ve. Algorithm 2 spells out the crux of our procedure, using learning rate fht-
Lemma 4.2 (Lemma C.2). For any p 0, Algorithm 2 is p-zCDP.
Algorithm Algorithm sub-routine. Algorithm has own privacy hudget.
7

---

Published in Transactions on Machine Learning Research (12/2023)
Based on Lemmas 4.1 and 4.2 and by basic composition of differential privacy (e.g., see (Dwork et al., 2006)), the entire scheme (Algorithm 1 and 2) is (r + 11) p-xCDP.
5 Lower Bounds
For privale constrained group-objective optimization; we now show excess risk bounds. Note that these results are equivalent lower bound on the sample complexity required solve the problem since these bounds are function of the dataset size Our lower bound results are specialized to the CGOO setting (see Definition 3.2). For the functions f.g analyzed below, one can think of f as function that computes average or total loss over the K group losses and g as function that computes the maximum or tail loss over the K groups.
We attack the following question: over the randomness of any (c, 0) or (e, algorithm, for a fixed dataset of size n, what a lower bound for the accuracy of the mechanism that solves the constrained group-objective optimization problem (Definition 3.2)?
Assuming the dataset is also drawn from B show lower bound the excess risk for decision set Cp Cp= B Ic k= |cll2 1}. That is, consider the case where the decisions and datasets lie in the unit ball with & norm. We show that for all n, K E N and c > O there exists a dataset D = {2))i= S B for which there is a CGOO problem with functions f.g such that both / and g will have excess risk lower bounds of 2 Q K and 2 Q x for any (e, 0), (e, dddifferrentiall private algorithms respectively.
5.1
(e, Lower Bound
The major idea in the proof of Theorem 5.1 is to reduce to the problem of optimizing 1-way marginals (a standard method for lower bounding the accuracy of differentially private mechanisms). Thcorem 5.1. Let n, K E N,c> O and a (0. For every c-differentially private algorithm M that produces decision è E Cp such that
S(E(C, D)) S
min f(((c, D)) + a, g(f(e, S a,
cECr:glticDD))o
there is a dataset D = (I 3 S B such that, with probability at least 1/2, we must have 2 S (K) for equivalently, n Ω (k) where f,g Lipschite, smooth functions defined as follows:
f(e(c, = Σ x)),
= f((()
x
for all E B/S.
Proof. We have defined f as [(((c, ()) -t which has minimum c² 12-1* x.| by Lemma A.1.
(c
We defined as g(f(c, D)) = f(l(c, D)) + + x,I| = f(e(c, D)) - f(l(cc, D)) which has minimum e* so that the constraint g(l(c", "e((cc,DD0 D)) & is satisfied.
Now by Lemma A.2, we have that f(l(c, f(l(ce D)) E x:1l - 1+ Now we invoke Lemma A.3. If è is the output of any e-differentially private mechanism M then we must have that ||c c²Il s( )) Suppose not. Then that would imply that we can construct a new mechanism M' that outputs é. 12 x:1
which would contradict Lemma A.3. As a result, ||c - e*Il 2(1) so that S(E(e, D)) - s(e(c", (D)) = 2 (k{ for the output of any e differentially private mechanism.
5.2
(c.6)
Lower Bound
For the proof of Theorem 5.2, we follow the steps of the proof for Theorem 5.1 but invoke the lower bound for 1-way marginals in the approximate DP case (and not the pure case).
8

---

Published in Transactions on Machine Learning Research (12/2023)
Theorem 5.2. Let K E 0, E (0.1), and ó o( For every (c, diff--iiferyttlially private algorithm M that produces decision è E Cp such that
f(e(2,
min oECr:glBeeDD))00
f(((e, + aa, g(e(e, S a,
there a dataset {aı,..., Ind S B such that, with probability at least 1/3, we must have a 2 52 (or equivalently, n 2 yK) ca
[K
m
where f.g are Läpschitz, smooth functions defined as follows:
1 n f(e(c, -
E (c -( a)),
n
g(e(c, =0000(((eec ((((e,
n
n
for all c E BY.
Proof. Again, the way we have defined f, by Lemma A.2, we have that f(E(c, D))) - f(e(c( D))
E xill ||c
c²1. Now we invoke Lemma A.4.
2n
If è is the output of any (c, dddifferrnnt private mechanism M then we must have that ||c c² = 12(1)
Suppose not. Then that would imply that we can construct a new mechanism M' that outputs è. 12-0 x;il
which would contradict Lemma A.4. As a result, ||e- |cc-c|l = ((1) so that S(E(e, D)) - [(e(c", D)) = 92 ( for the output of any (e, didfferrrnyy private mechanism.
en
6 Empirical Evaluation
We now discuss the empirical performance of our proposed scheme for synthetic and real-world datasets. We discuss the results for the law school dataset in the appendix. We find that the proposed group-aware privacy budget allocation leads to 10% to 50% reduction in mean standard error of the prediction for the smallest groups. For real-world datasets, we find even more substantial gains. For all our experiments, the total privacy budget is p= T + μ. We allocate 20% of the budget to stage 1 (i.e., r = 0.2p) and 80% to stage 2 (i.e., f = 0.8p). We present results for other budget allocation schernes between the two stages the Appendix. In the results, 'DPSE' refers to our proposed scheme and 'DPNoSE' refers standard lincar regression computed via DPGD (budget of p) but with no group aware budget allocation.
We also tried our methods data with more than 2 groups (in particular, K = 5 and K = 10 groups). For simplicity, we focus on the K = case (one majority group and one minority group) since it is alrcady very nuanced in this case.
In this section, we present a subset of our empirical results. More experimental details can be found in the appendix. Soe Scction B.
Setup for Synthetic Experiments. For the results presented here, we assume that Cr [-5,5) We define & to be multivariate function such that for any group k E [K] and dataset Z with n. items with features X Xin, E R.. Let (x(c, = Em (Y, (Xa., c) Its gradient is (cx We set 5(1) = EK=4, 4 and g(l) max 4. For the synthetic data experiments, we assume the following ordinary least squares (OLS) generation model: for any group &o E [K] and for all E [Nx], Y, X NO, lo where B% R., σk 0, X R
=K)=IK1
Overview of Results: Synthetic Datascts. Figure 6 shows different parameter settings for a two-group synthetic scenario where we observe what happens to the MSPE as we vary the privacy parameter The blue line shows the MSPE for the smallest subgroup when the privacy budget is set with our group-aware scheme while the cyan line the MSPE for the smallest group when the privacy budget is not tailored to any group. For reasonable levels of privacy, we observe substantial (10% to 50%) reduction in the MSPE when set the privacy budget using our proposed formulation. When incorporate fairness constraints, we find
9

---

Published in Transactions on Machine Learning Research (12/2023)
that the group aware formulation (DPSE smaller group) still maintains the 10% to 50% reduction in the MSPE for the smaller groups.
K > 2 Groups and Group Sizes. We also considered additional settings with more than 2 groups. In this case, we still observe at least a 10 percent reduction in MSPE for the smallest groups without hurting the larger groups. concern might be that as K (the number of groups) gets larger, the standard error calculation in stage becomes more inaccurate. In this case, one could allocate more privacy budget stage 1. We conducted comprehensive experiments for K 2, 5, 10, 15, 20 groups. Similarly, we include additional discussion empirical results the law school and credit datasets in the Appendix of the original paper. For the sake of brevity, we present tables here for the K = 5 case. In the first experiment, the largest group (group 1) has size 10,000 and the smallest has size 500 (so a 20x ratio). In the second experiment, the largest group has size 5,000 and the smallest has size 100 (so a 50x ratio). For all the other cases (K = 10, 15, 20), we observe similar gains in Mean Squared Prediction Error (MSPE).
Logistic Regression. Our methods can be easily translated to the logistic regression (for use in classification) setting. For training data Z {(x, y:)} the linear regression loss is
10 2) = Σ 20) - y;)²
which has an explicit gradient. We can replace this with the logistic loss as follows
h(O Z) 1 Σ log(1 + e e-:00=))
where Y/ are the labels in this case. The logistic loss also has an explicit gradient. And since our algorithms require only oracle access to the gradients, the change to compute the logistic regression results is minimal.
Group
DPNoSE (p 2)
DPSE (p 2)
Group
DPNOSE (p 4.5)
DPSE (p 4.5)
1.02
1.27
1.01
1.26
18.71
15.75
18.69
15.73
21.09
17.75
21.07
17.73
21.35
17.94
21.34
17.93
18.11
15.29
18.09
15.28
Group
DPNoSE (p = 8)
DPSE (p = 8)
1.01
1.25
18.64
15.71
21.02
17.71
4
21.29
17.91
18.05
15.26
Table 1: MSPE for DPSE vs. DPNoSF. (5 groups, 20x)
6.1 Evaluating Different Privacy Splits Based on Dataset Characteristics
In the main paper, our methodology is such that we can specify any privacy budget splits between the 2 stages via (T, ju) as long as p + μ. However, in our experimental evaluation, we set 0.2p. Note that the gains of our approach will likely be bigger when the standard errors are larger in the minority group. Now we show, via some experimental validation, that using 20% of the privacy budget allows us to privately estimate the standard errors in the first stage that we can then use for privacy budget allocation. For simplicity, we only generate 2 groups. 71, n2 are the sizes of the majority and minority groups, respectively. We see from Table 2 that since the minority group is much smaller size than the majority group, it tends have a much larger relative standard error. As result, majority of the privacy budget is used for privately estimating quantities related to the minority group. See Tables 2 and 3.
10

---

Published in Transactions on Machine Learning Research (12/2023)
p
Standard Errors (Majoriy-Mimority)
Normalizod Budget Splits (Majority-Minorrity
2-/2
0.00043513 0. 1.14421164
1. 1.2036260e=05 9.99987964e-01
32/2
0.00078679 0.04677319
2.82876770c-04 9.99717123<-01
/2/2
10.00048994 0.039354088]
1.07969485c-04 0.99892031c-01
52/2
0.00038963 0.03800898)
1.05070219e-04 9.99894930--01
Table 2: Standard Errors and Splits. R4 = 8000000, n2 = 500
p
Standard Errors (Majortty-Miorrity)
Normalized Budget Splits (Majority-Minonin
32/2
00.00535333 0.05429162
9.72139296c-05 9.99902786c-01
/2/2
10.00018697 0.03429942
2.97124804c-05 9.99970288c-01
52/2
[0.00015344 0.04948024]
9.61694723e-06 9.99990383e-01
Table Standard Errors and Splits. 01 16000000, n2 500
Why Even Look at Standard Errors? We have now added additional experiments to illustrate why looking at the standard errors could provide information that is impossible to obtain by just looking at the data set sizes. In particular, we provide datasets where two groups have exactly the same data set sizes. So just looking at the sizes alone would result in the same privacy split. However, one group has much larger sampling error and the other does not. According to our methodology, more budget. would be allocated to the group with larger sampling error.
We vary the variance in the independent variable as follows: the first group (group 1) has variance 10000 and the second (group 2) has variance of 10 (much smaller!). To account for the severe imbalance in the variance, our methodology assigns privacy budget split that favors the group with much larger variance. We show these results in Table 4.
7 Additional Related Work
The Disparate Impact Due to Differential Privacy & Langrangian Approaches. Our work was inspired by the findings of Bagdasaryan et al. (2019), who showed that predictors learned via DPSGD have low performance for minority groups. Similarly, Pujol et al. (2020) show, in a resource allocation setting, that under e-differential privacy, the noise added disproportionately affects minority groups in the data.
Mahdi Khalili et al. (2020) provide an approach that uses the exponential mechanism as post-processing step to improve the downstream lairness and privacy properties of standard supervised learning model. Tran et al. (2020) address satisfying privacy and fairness constraints through a Langrangian duality approach. We also roly on Langrangian framework to incorporate fairness constraints the setting we consider. However, we focus on bounded group loss definitions of fairness in our formulation, which Tran al. (2020) does not consider. Using Lagrangian duality for privacy (via linear programming, for example) has been considered before, in different contexts, in the differential privacy literature (Nikolov et al., 2013; Hsu et al., 2014).
More recently, Xu et al. (2019); Esipova et al. (2023) show results for achieving differential privacy and a range of notions of algorithmic fairness (Hardt et al., 2016). These impossibility results do not apply to bounded group loss, which the notion of disparity that we consider in this work. Mozannar et al. (2020) consider the task of learning fair predictors without access to sensitive attributes under local differential privacy.
n
Standard Errors (Majority- Minority) Normalized Budget Splits Majority-Minorrty)
T1 1000
4.04838336, 96.67176174]
0.04019438,, 0.95980562) 0.03081106, 0.96918894
n 50000
3.18102322, 100.06187079
7 9000000
3.16276276, 100.01852322
0.03065248, 0.96934752)
Table 4: Standard Errors and Splits. n = 1000, 1000,50000, 90000.00000000.
11

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithmic Fairness. Predictors learned via empirical risk minimization (ERM) often exhibit poor performance for minority, both in size and by category, groups in the data (Buolamwini & Gebru, 2018; Koenecke et al., 2020; Barocas et al., 2019). In this work, we also consider learning regression models subject to fairness constraints using a Lagrangian formulation that builds on the work of Agarwal et al. (2019). Khalili et al. (2021); Tran et al. (2021b). Agarwal et al. (2019) present algorithms to obtain linear regression predictors subject to statistical parity and bounded sub-group loss; specifically, they study how to transform fair regression problem with constraints to a generic loss minimization problem, via Lagrange duality, without constraints. We abstract the fair constrained regression problem into one that we term a "constrained group-objective optimization" problem, where the goal is to minimize an objective with certain properties (say Lipschitzness and/or Convexity), but for which there are 'group' constraints. The Lagrangian fair linear regression formulation that we consider falls under their abstraction.
Group-Aware Learning. The principle underlying the group-aware scheme that we propose requires treating different subgroups in the data differently. For example, Hobert-Johnson al. (2018) proposed multicalibration, a principle that requires calibrated predictions for all subgroups in the training data that can be identified. Building on this work, Kim et al. (2019) propose multiaccuracy boost, an approach, using group rewcighting, to audit and improve the performance of the predictive model among subgroups in the data that have low performance. Alternatively, one can also learn group-specific predictors for each subgroup in the data (Dwork et al., 2018). Koyejo et al. (2014) and Hiranandani et al. (2020) explore the goal of learning functions of partitions of the confusion matrix with applications to algorithmic fairness.
8 Conclusion
In this paper, we proposed group-aware approach to set the privacy budget while learning regression models for datasets with stratification. This proposed formulation seeks to overcome the disparate model performance that naive application of differential privacy incurs for minority subgroups. We propose to allocate the privacy budget for each subgroup of the dataset based on the standard error of a precursor regression model. This formulation allows us to reduce the level of noise that DP adds to groups where the parameter estimation will be most uncertain uusually groups with smaller sizes. We justify the group-aware privacy budget allocation with a theoretical analysis of an idcalized 2-mixture of Gaussians model. Finally, we show that the proposed scheme leads to reduction in the mean square prediction error, compared to the standard privacy formulation, synthetic and real-world datasets where observe substantial (10% to 50%) reduction in the MSPE when we set the privacy budget using our proposed formulation.
We however note that it is unclear whether our current proposal extends directly to deep learning and modern neural networks. We believe this challenge presents avenue for intriguing future work. There are straightforward modifications to our scheme that would extend to the deep learning setting.
Our proposed group-aware privacy budget allocation shows promise; however, there still remain open questions. As it stands, it is unclear how to, optimally, split the overall privacy budget between the two stages of the algorithm. We make this decision a user-dependent one, but future work will look at how to determine the privacy split in an optimal fashion via analysis of the Pareto frontier of the utility-privacy trade-off. We considered the bounded subgroup loss formulation here, however, future work can also consider more sophisticated fairness constraints.
Our framework is centered on linear regression, a fundamental task; however, extensions to other estimators including those with non-convex loss functions is also desirable. Taken together, we hope this work opens up discussion about approaches for mitigating the disparate impact of differential privacy for small subgroups.
Acknowledgments
Daniel Alabi was supported by the Simons Foundation (965342, D.A.) as part of the Junior Fellowship from the Simons Society of Fellows and Fellowship from Meta AI during his graduate studies at Harvard University. We thank Julius Adebayo for his contributions to early stages of this project.
12

---

Published in Transactions on Machine Learning Research (12/2023)
References
Martin Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, 1yya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. CoRR, abs/1607.00133 2016. URL http://arxiv.org/
5bbs/667.00033. 1
John M. Abowd and Ian M. Schmutte. An economic analysis of privacy protection and statistical accuracy social choices. CoRR, abs/1 hts/1808.066003, 2018. URL http: http///iivv..orrbb////aaaa 06303. 1,
Alekh Agarwal, Miroslav Dudik, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and roduction-based algorithms. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 120 129, 2019. URL http://prooeedding.. mlr. mlr.press/v9l http:///////aaaaaaaaa/ aaggaaaaaaaaldd html. 2, 3, 5, 12
Daniel Alabi and Salil Vadhan. Hypothesis testing for differentially private linear regres- sion. In Advances in Neural Information Processing Systems, volume 35, pp. 14196 URL
14209,
neurips...... wwtpppper.ileeepppppeeeeeee.peee wttp://////ap//////1//22 Ble356c0fa11SS111786666221122222 otr.:a/eeeeeiiteieeeeeoreeeoeerr
2022.
Daniel Gbenga Alabi. The Algorithmic Foundations of Private Computational Social Science. PhD thesis,
Harvard University, 2022. 3
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate im- pact on model accuracy. In Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canado, pp. 15462,15462, 2019. URL https://proceedinga. www.eddiinnnnnuisss...m wwwuips.cc/pappeee. 20199///2099/hhht 000644008661125577660088333388
Abstract html. 1, 11, 18
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlbook.org, 2019.
http://www.farrl// org. 12
Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 464-473, 2014. 1, 7, 16
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4)2311 -57, 2015. 23
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptogrophy 14th International Conference, TCC 2016-B, Beijing, China, October November 3, 2016, Proceedings, Parl I, pp. 635 658, 2016. 2, 3, 19, 20, 21, 22, 23, 24
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on Foirness, Accountability and Transparency, FAT 2018, 23-24 February 2018, New York, NY, USA, pp. 77 91, 2018. URL http: http:///rroceedings mlr, ptw.s//81////////// www.amwwiiiiiimmmoommmmmww.wwiiw 18a, html. 12
Nicholas Carlini, Chang Liu, Jernej Kos, Úlfar Erlingsson, and Dawn Song. The secret sharer: Mcasuring unintended neural network memorization & extracting secrets. orXiv preprint arXiv:100200820 08232, 2018. 1, 2
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulaar Erlingsson, al. Extracting training data from large language models. arXiv preprint orXiv:2012.07800 2020.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069 1109, 2011.
Junjie Chen, Wendy Hui Wang, and Xinghua Shi. Differential privacy protection against membership inference attack machine learning for genomic data. bioRwiv, pp. 2020-08 2020. 1
13

---

Published in Transactions on Machine Learning Research (12/2023)
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryplography, Third Theory of Cryplography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, pp. 265 284, 2006. 1, 3, 8
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: Optimal bounds for privacy-proserving principal component analysis. In Proceedings of the Forty-Sizth Annual ACM Symposium on Theory of Compuling, STOC '14, pp. 11 11-20, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. doi: (11144//59119622591122 2591796. 2591883. 6, 21
URL attps://doi. org/oog////o 1x45//.114//
Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In Conference on Fairness, Accounlability and Transporency, pp. 119-133. PMLR, 2018. 12
Maria S. Esipova, Atiyeh Ashari Ghomi, Yaqiao Luo, and Jesse C. Cresswell. Disparate impact in differential privacy from gradient misalignment. The Fleventh International Conference on Learning Representations (ICLR), 2023. 11
Georgina Evans, Gary King, Margaret Schwenzfeier, and Abhradoep Thakurta. Statistically valid inferences from privacy-protected data. Americon Political Science Review, 117(4):1255-1290, 2023. doi: 10.1017/ $0003055422001411.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315 3315-3323, 2016.
Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (compptatiinaall--eeettiiaaa masses, In International Conference on Machine Learning, pp. PMLR, 2018. 12
Gaurush Hiranandani, Harikrishna Narasimhan, and Oluwasanmi Koyejo. Fair performance metric clicitation. CoRR, abs/2006.1 12732, 2020. URL https://arxiv: wrg//bs////// httg//bb/2006.. ht.bs//00...277000 12732. 12
Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan R. Ullman. Privatcly solving lincar programs. In Automata, Languages, and Programming 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part pp- 612 1224 2014. 11
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. 1EEE Trans. Inf. Theory, 63774440,, 2017. 6
Christopher T. Kenny, Shiro Kuriwaki, Cory McCartan, Evan Rosenman, Tyler Simko, and Kosuke Imai. The impact of the u.s. census disclosure avoidance system on redistricting and voting rights analysis, 2021.
Mohammad Mahdi Khalili, Xueru Zhang, Mahed Abroshan, and Somaych Sojoudi. Improving fairness and privacy in solection problems. In Thirly- AAAI Conference on Arlificial Intelligence, AAAT 2021, pp- 8092 8100, 2021. 12
Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAT/ACM Conference on AI, Ethics, and Society, pp. 247-254, 2019. 12
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnic Quartey, Zion Mengesha, Connor Toups, John R Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition.
Proceedings of the National Academy of Sciences, 117(14):7684-7658 2020. 12
Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K. Ravikumar, and Inderjit S Dhillon. Consistent binary classification with generalizod performance metries. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and Q. Weinberger (ods.), Advances in Neural Information Processing Systems 27, pp. Curran Associates, Inc., 2014. 12
14

---

Published in Transactions on Machine Learning Research (12/2023)
Mohammad Mahdi Khalili, Xueru Zhang, Mahed Abroshan, and Somayeh Sojoudi. Improving fairness and privacy in selection problems. Xi e-prinls, pp- - 2020. 11
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint Xio::11710. 0.0.6666, 2017. 1
Hussein Mozannar, Mesrob Ohannessian, and Nathan Srebro. Fair learning with private demographic data. In International Conference on Machine Learning, pp. 7066 7075. PMLR, 2020. 11
Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pp. 351 360, 2013. 11
Samantha Petti and Abraham Flaxman. Differential privacy in the 2020 us census: What will it do? quantifying the accuracy/privaey tradeoff. Gales Open Research, 3, 2019. 1
Stephen R Pfohl, Andrew M Dai, and Katherine Heller. Federated and differentially private learning for electronic health records. arXiv preprint orXiv:1911.05861 2019.
David Pujol, Ryan McKenna, Salya Kuppam, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklan Fair decision making using privacy-protectee data. In Proceedings of the 2020 Conference on Fairness, Accountabiliby, and Transparency, pp. 189 199, 2020. 11
Alexis R. Santos-Lozada, Jeffrey T. Howard, and Ashton M. Verdery. How differential privacy will affect our understanding of health disparities in the united states. Proceedings of the National Academy of Sciences, 117((4):134055 13412, 2020. ISSN 0027-8424. doi: 10.1073/pman 1.107//pma.2200314117,
URL https:
// //ww.ppas... org/ httg://ootentt117////3/4344
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, pp. 71-79, 2013. URL http:// org wwt.oorg//eeooeeooooooo prgpproceeding// papers/ /atarss/v8/// 2atrrr//2//hharr133 shamir13.......//// html.
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. arXiv preprint orXi::2009. 2020. 11
Cuong Tran, My H Dinh, and Ferdinando Fioretto. Differentially private deep learning under the fairness lens. arXiv preprint arXi::2006.0200 2021a. 2
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, pp. 9932 9939, 2021b. 12
Depeng Xu, Shuhan Yuan, and Xinlao Wu. Achieving differential privacy and fairness in logistic regression. In Companion Proceedings of The 2019 World Wide Web Conference, WWW '19, pp. 594-599, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366755. doi: 10.1145 00.114//3005560.331788 1tt..o......14/3086666666
URL https:///ot: http:///doooor//.... 2tg//1..10 1145/3308866 3317584. 11
Depeng Xu, Wei Du, and Xintao Wu. Removing disparate impact of differentially private stochastic gradient descent on model accuracy. CoRR, abs/ hbs//2033.0366 2020. URL attps://arxx org/ argg/bs/2000 03699. 2
15

---

Published in Transactions on Machine Learning Research (12/2023)
A Helper Lemmas for Section 5
Lemma A.1. Let c* arg min [1ll211
1 n
Ei= (c, xx) where os B for all i [n], then e* m
aill
Proof. For any BK
have (e, Σ
xi) S |||||| - x,1 1|== xill by Cauchy-Schwarz and this is X1
tight when c
X or
As a result, the minimum of 1 Ei= (c, x,) is attained at
i-1 xill
12 11
i-1 xill
x;
Lemma A.2. Let [(E(e D)) = - -i (c, mx) where e, 24 E B2e for all i [n], then
(((c, ,(((c(, = 1Σ -
|c - c" ||?
2n
for any a BK and c² 1210 all
Proof. We have that
D))
1
Σ
((c", x,) - -(,,x,))
(5)
i=1
1
{e
x1) (c, Ex1)
(6)
n
i=1
1=1
1
x; || - (c, Σxx xz)
(7)
n
iml
iml
E X:|l
(1 {c, c*))
(8)
n
1i=1= xil
||c - cc-2
(9)
2n
E.
where we have used that ||c - e=2 ||e||2 + || 2(e, = 2 2(c, c*) and 6²
x.Il
We now state lower bound lemmas for 1-way marginals. Lemma A.3 shows the lower bound for 1-way marginals for e-differentially private algorithms and Lemma A.4 is for (c, dddifferrentilll private algorithms. Lemma A.3 (Part of Lemma 5.1 in (Bassily et al., 2014)). Let n, K N and
There erists number M Q(min(n, K) such that for every e-differentially private algorithm M there is a dataset D (m...... ... ]n} S B with || aill2 [M -M-1,,2 M, + 1] such that, with probability at least 1/2 (over the mandomness of the algorillan), we have
[IM(D)- - (DD) (minn11 K
)), en
where ((D) = Em= x3
Lemma A.4 (Part 2 of Lemma 5.1 in (Bassily et al., 2014)). Let n, K E <> 0, and 5 o( There is
number M = Q(min(n, xK)) such that for every (c, -ifffferrentially private algorithm M, there is dataset D D= fm..... 2n) C BK with |E æil12 E [M - 1, M + 1] such that, with probability at least 1/3 (over the randomness of the algoritho)), we have
[M(D) 2(D)ll2 = M(min(1, VK )),
where (D) n E Z;
16

---

Published in Transactions on Machine Learning Research (12/2023)
B Additional Experimental Details
In this section, we present additional empirical evaluation of the our proposed group-aware differentially private budget allocation algorithm. For our experimental ovaluation, the method that uses standard error information called DPSE while the method that doesn't use such information called DPNoSE.
Code We include copy of Numpy implementation of the algorithms that we present in the main paper along with the README and requirements file.
Trials & Compute Used Our results are computed over different instances of mixtures. Each run a mixture is evaluated 1000 (random seeds) times and results are averaged over these Monte Carlo trials. We find that the average standard deviation of the Mean Squared Prediction Error (MSPE) of our results is less than 10% of the MSPE. All our experiments are run on a MacBook Pro (13-inch, 2018) with 2.3GHz Quad-Core Intel Core i5 with 16GB Memory.
Real-Worle Datasets In this section, give more detailed overview of the Credit dataset, which discussed in the paper. In addition, we present empirical results on the Law School dataset.
Law School Dataset Description The second real-world data set that we consider consists demographic variables for law school students derived from the Longitudinal Bar Passage Study (Wightman, 1998). this data set, there are attributes including the type of law school attended, the LSAT score, the undergraduate grade point average (GPA), the age; the race, the first year law school GPA, and the final cumulative GPA of each applicant. We consider the task of predicting the final cumulative GPA of each applicant given the underlying demographic variables. We take the attribute race as the sensitive attribute in the fair regression framework. We consider two groups: the 'white" students (22610 samples), and the 'black' students (1874 samples). We normalize all features to lic in an & ball.
A
B
C
Correlation HealMup
customer age
Male: customer age
100053
30999
30003
Loseeed
50063
40003
Hute
10331
tecionl
3339
2008
22
20
50
20
24
30
90
Female: Credit Lamit
Male Chali Laus
700073
120004
23000
2000
50008 130000
15000e 200089 200893
Figure Data set overview. We examine some statistics of the Credit dataset. A) The variables present. in the Credit dataset and the correlation heatmap amongst these variables. We see that asset, income, and educational status are the variables relatively more highly correlated with the credit limit than gender. B) The distribution of customer age for Females in the dataset. C) The distribution of customer age for Males in the dataset. D) The distribution of credit limit for females in the dataset. E) The distribution of credit limit for males in the dataset.
Credit Dataset. First, as discussed in the paper, the key task in the credit setting that of predicting the credit limit assigned to individual given socio-economic variables like income, asset, and Age. In Figure 1,
17

---

Published in Transactions on Machine Learning Research (12/2023)
Mean Squared Prediction Error
Law School Dataset
1.20
DINOSE Larger Groups
DISE Larger Group
DPNoSE Smallar Group
DPSE Smaller Group
1.30
1.05
10
20
30
40
P
Figure 2: Empirical Results on the Law School Dataset.
we show a heat map of the correlation amongst these variables as well as histograms of age and credit limit. for the male and female groups in the dataset. For the experiments performed, we subsampled the dataset into two: 11, 11,480 males and 2,937 females.
In Figure 3, we show that DPSE outperforms DPNoSE on the smallest subgroup. Let 31. denote the slopes in the 2 groups in the dataset. We see about a > 50% improvement in MSPE, on average, for slopes (2),82) = (-10, 10) and (B1, 32) = (10, 10)) whether the ratio of sample sizes 5x or 50x. The improvement becomes small when the ratio of the slopes is much higher (i.e., when (81, 82) = (-10, -1)). We vary the privacy parameter from == 0.12 to p = 102 /2 and our Monte Carlo results are averaged over 1000 trials. de is the noise in the dependent variable for both groups. We o, 1. e.g., for group 1, (N(1, o2 where is the number of data points in group 1, the majority group.
Figure 2 shows the empirical results for regression models trained on the law school data. Again, we see that the group-aware budget allocation approach (DPSE) provides a reduction in the mean squared prediction error of the resulting models. Taken together, these results further demonstrate that our proposed approach reduces the disparate impact of differential privacy in small groups.
B.1 MSPE Results for DPSE & DPNoSE for additional synthetic settings.
In all the synthetic data experiments below, the clipping bound (for the gradicnts and losses) is set to = 2. We make this choice because given the synthetic setting that we consider, the Lipschitz constant of the is Lagrangian formulation function usually at most 2. We note here that the clipping bound here is applied to the gradients and losses and not the OLS parameters learned.
Beyond Linear Regression. We replicate the MNIST "8-vs-2" binary classification experiment from Bagdasaryan et al. (2019). We use a logistic regression model in the first stage, and a LeNet network for the second stage (total e 5.73). This means that we tailor the group privacy budgets based on the residuals of the logistic regression for the LeNet model. We find 64 percent reduction in classification error, for the minority '8' class, compared to the results of Bagdasaryan et al. (2019). This experiment suggests that our approach can generalize to other model classes.
C Proofs and Additional Detail on Algorithms for Group-Aware OLS
Lemma C.I. For any 0, Algoritlom is T-2CDP
18

---

Published in Transactions on Machine Learning Research (12/2023)
Puuti (13300 5001 Ad
(2000 500) 18, 115,
Syy (Co0e 130,, A1-
thu (100000000 500r, (1i, Rot-
15000) 1-20.10)
1h 1500 1021 110
15025, 15533
15000 1001
OPS Lorger Gree 0PS Smalle
Figure 3: Additional Empirical Results for Synthetic Datasets. We vary the sample size ratio between the larger and smaller groups from 20x to 50x. We also vary the slopes used to generate the OLS models within each group. We consider group slopes {(-10, 10), -00), (10, 1), (-10.-1)) Across most regimes, that the MSPE in the smallest group is reduced with the DPSE procedure.
Monn Squared tre-detive Enter Moan Siqureed Predicion Erier
-40
(/,,))) (5000. 50), (6, (-1.11
in..n:1-5000 50). Ba) 11-11. -1
1000
80
60
[ (100000 500),
(10000, 5001, (8. 8.)=
DPNeSt Larger Groups
120
DPSE Larger
DPNoSE Smaller Group
DPSE Smaller Group
80
80
7.5
17.5
Figure 4: Additional Empirical Results for Synthetic Datasets. We vary the sample size ratio between the larger and smaller groups from 20x to 100x. We also vary the slopes used generate the OLS models within each group. We consider group slopes {(-1, 1), (1, (1]- We also vary the noise in the dependent variable and observe similar results. Across all regimes, reduced with the DPSE procodure.
that the MSPE in the smallest group is
Proof. First, recall Lemma 2.3 in (Bun & Steinke, 2016) (for composition and postprocessing of zCDP) and Lemmas 2.4, 2.5 for the application of the Gaussian Mechanism for zCDP. We use T/(K + 1) to calculate DP estimates of the covariance and variance matrices: X and XTY. If the minimum eigenvalue of XTX is 0 (which implies noninvertibility or non-positive variances), we return normalized all-ones vector, step that is still private by postprocessing DP capabilities.
We proceed to calculate the DP estimate of the standard error (SE) for each group using Lemma 2.4 in (Bun & Steinke, 2016) to satisfy T/(K + 1)-zCDP. Again, the SE results in a value < 0, we return a normalized all-ones vector. Finally, by composition properties, the whole procedure satisfies 7-2CDP.
Lemma C.2. For any 1 0, Algorithm is μ-zCDP.
19

---

Published in Transactions on Machine Learning Research (12/2023)
(yy (3.000000000000010000000 (0 (22,000 500), (8, (1. 101
(0u0)1(10000 (1,000 500n, (1-(100))
(0,,00)- 500). (1-1000
OPhedt Smaller UPSE Smaller Group
Figure 5: Empirical Results for Synthetic Datasets. We set the sample size ratio between the larger and smaller groups to 100x. We vary the slopes used to generate the OLS models within each group. We consider group slopes { ((-10,10) (10, 10), (10, 1), (-100-111))) Across most regimes, we see that the MSPE in the smallest group is reduced with the DPSE procedure. In this case, the loss in the larger group even much smaller given the large size of the larger group.
3:4
10, nil 15003 1001, Balm 10
Pitott/Me) (M60 10 01005115025.1 1205 1.. (1111
-2 23000 1001 20
OPIOE Snaderdee drug
Won 10
Figure Empirical Results for Synthetic Datasets. We observe, on average, a 10-20% reduction in the MSPE. For small privacy parameters, tend to overpenalize the larger group, leading to quicker convergence to the right parameters for the smaller group.
Proof. Again, we apply Lemma 2.3 in (Bun & Steinke, 2016) (for composition and postprocessing of zCDP) and Lemmas 2.4, 2.5 for the Gaussian Mechanism xCDP application.
There are T iterations so we split our privacy budget into μ/T. Since from stage 1, Σ + =1, for each group k [K], we use budget of s p//T (split into two for computing 4 and its gradient Vlx). By post-procesing and composition properties of zCDP, the whole procedure satisfies p-ZCDP
20

---

Published in Transactions on Machine Learning Research (12/2023)
In this section, we provide variation of Algorithm 2 with no fairness constraints but with budget allocation strategy. See Algorithm 3.
Algorithm Stage 2 Variant: μ-zCDP DP OLS Regression
1: Input: μ; Tt, A, T
2: Obtain standard errors .1,,, SK from Algorithm
3: Initialize 01 arbitrarily
4: for = to 1 T do k K do (0g 7) -i=1 2( X Xx Ei (ex Kki Vks)
for k
Use budget of Pr μ s TT to compute M follows:
8:
(L, 2) E
( (0,, Xug. Ma))
Xe..
(f2-norm per-example gradient clipping)
9:
M = (L, 2) + NN 2pT
10: end for
M = (M :.... .....M)) )K E Rx
11:
12:
0--1 cTc (0. ne (M))))
13:
end for
return 0, // public DP release
Lemma C.3. For any j 0, Algorithm is μ-2CDP.
Proof. We apply Lemma 2.3 in (Bun & Steinke, 2016) (for composition and post-proccssing of 2CDP) and Lemmas 2.4, 2.5 for the zCDP guarantees via the application of the Gaussian Mechanism.
Each iteration E [T]] receives privacy budget of μ/T' From stage 1, of = We can use this to allocate budget of 5x 11/T for each group E [K]. By post-processing and composition properties of zCDP, the whole procedure satisfies p-zCDP.
Mixture Model Analysis for Standard Error and Other Proof Details
In this section, we include proofs that we could not, because of space constraints, include in the main paper. Lemma D.1. Let U be an f2-norm upper bound on the rows of X E Raxd and the rows of Y e R". Then XTX = X + 122 Z is T-2CDP where E Raxd is symmetric matris with each entry in the upper triangular matrix sampled from (0, and the lower triangle entries are copied from its upper triangle part. Purthermore, XTY = XTY
U is 7-2CDP where Z (axa) V2T
Proof. The proof of privacy follows from the Analyze-Gar Gauss algorithm (see Algorithm 1 and Theorem 2 in (Dwork et al., 2014)) where we apply the Gaussian Mochanism to satisfy 5-2CDP, by Proposition 1.6 in (Bun & Steinke, 2016).
Lemma D.2 (Restatement of Lemma 3.1). For any (0,1), 31,82 E Rd X1 Roixd X2 1 01,02 > 0, n2 E Z4, define the mixture model Y of + c) of Ing
cY₁ + (1 (1-c) (1-c) Y2
Let B 31 with probability and 3 = B2 with probability 1 1- c, then the prediction Ý is Yı with probability and Y2 with probability c). The expected prediction loss of B on Y is c² n, Cof + (1 - c)² nzCaz +
c(l-c)[, + c(1 2 where I1 = 1|22 X233 12,, P. | &2 C x2. and x the chi-squared distribution with k degrees of freedom
21

---

Published in Transactions on Machine Learning Research (12/2023)
Proof. First note that ||Y X1 ~ nixîof since Y1 - X1 (0 of xm1) so that for any i E [n1];
(Y1 - x181); ~ (N0, of) ~ (0, 1). (Vi - x1 (X))) ~ ooxi
since x is the sum of squares of i.dd standard normal random variables. Then || -X, ~ nioixi.
Similarly, || - X2 ~ n20
Then the expected loss given the learned estimate 3
Bs[1y - Y1 = Es cl| Vi - x
- (1- x2,11
c² || X1,31 12 (1- (1-c)) - X2 2 + c(1 c)|[Vi X1 + c) 1 X2
~ e Cot (1 - + c[1- + c(1 - c)l
where C ~ Xi.
As shown above, even the best randomized predictor has dependence on group size and the standard error of the prediction. Compounding this issue, the requirement for diffcrential privacy nocessitates additional noise, which increases measurement error. To account for measurement error, we need to make sure that the error in the estimates of 1, 22 not exacerbated.
E Asymptotic Convergence Analysis of (Stochastic) Gradient Descent for CGOO Problem
In this section, give convergence guarantees for (stochastic) gradient descent for the CGOO problem. We discuss the optimal setting of the learning rate when applying differentially private gradient descent to solve constrained maximization problems defined on smooth functions for the CGOO problem. Assume that the functions f and g have smoothness parameters By and 3, respectively. Recall that a function f V + R is ß-smooth if its gradient f is B-Lipschitz. That is, [V] Vf(x')l I B|| x'll for all x, x' E E..
In Algorithm 4, we reproduce Algorithm 2 but with a learning rate that depends on the privacy noise parameter a. We show that, after at most T (n)) calls a perturbed version of Vh, we can differentially privately minimize h to within for any a 0 for large enough sample size Note that could still
minimize h to within with smaller T in practice.
Algorithm 4 p-2CDP DP (Fair) Regression Smooth Functions
n. p, T, BT,,B,,,8 B,, Input: D,
x² K13y+G9,,*t
2pn²
Arbitrarily set 01 E Cp
for 1=1 to l. = T - do
Vh(c,, D) ~ N(VVhe,, o'
DJV (V(.
7)()) VIU(+G)+PP
C+1 = ITc, (c - (t()q;) end for return CT
In Figures 7-A, we illustrate (graphically) how projected gradient descent behaves under differential privacy constraints. The projection step in gradient descent. becomes noisy because of the noisy gradient computation process. For Frank- Wolfe under differential privacy, the vertices of the set C, if convex, appear to be moved or perturbed. We illustrate differentially private Frank-Wolf in Figure 7-B. Frank-Woll is, essentially, an iterative first-order optimization algorithm that replaces the projection step of gradient descent with solving linear approximation sub-problems.
Lemma E.1 (Composition of p-xCDP (Bun Steinke, 2016))). Let M X - y and M' : X - Z be (randomized) algorithms that satisfy p-zCDP and pC22DDP respectively. Define M" X + y where (* (Mxx), M'(x)). Then M satisfies (p + p')-
22

---

Published in Transactions on Machine Learning Research (12/2023)
22
Cc nc
V
D2
2
c' = Vi
C' = Pr
V/3
1/3
4
U4
4
D3
(b)
Figure (a) Illustration of Projected Gradient Descent for private Constrained Strou-Objjcctvy Optimization using noisy projection oracle. (b) Illustration of perturbed vertices when solving linear optimization subproblems for private Constrained Group-Objective Optimization.
Lemma E.2 (Post-Processing of p-zCDP (Bun & Steinke, 2016))). Let M x" + and g be (randomized) algorithms. Suppose that M satisfies p-2CDP. Define M' X" Z M² g(M())) Then M' salisfies p-zCDP.
Theorem E.3 (Theorem 2 from (Shamir & Zhang, 2013)). Suppose that h is conver function and that for some constants S, Q, it holds that B[ll S Q² for all t. and e' palle-cll c'll S S. Then the stochastic gradient descent algorithm with initialization rule E EC, and update rule
c++1 = IIe (ce - -
and slep size tt v/Vi (where e is constant) has the following guaranlee for uny T >
S2 - M (=+002)
+og T VT
where c* arg min h(c), 4 Oh(ce) is subgradient of h and Hle is projection oracle into feasible set C. Theorem E.4 (Theorem 3.7 from (Bubeck, 2015)). On the set let projected gradient descent be of the form C++1 Ie (a v)(((c) for t >> and e1 be arbitrory decision in C. Suppose h is convez and 8-smooth on C. Then projected gradient descent with step size 1 satisfies
h(c)) - h(c²) 3 - c²12 + h(a)) h(c²)
t
where e* arg min h(c).
Algorithm Gradient Descent for Constrained Group- Objective Optimization.
Input: D, T, Ile, Arbilrarily set EC
for t= to T do
7tt) = (I+G]
Vh(G, D) Vllc, D)V +))+))))++11))
DVV (D D))
C+11 He (c+ nttVVh(c, D))
end for return ==
Algorithms and correspond the algorithms for solving the CGOO problem with learning rates from Theorem E.3 and Theorem E.4 (for the smooth case).
Lemma E.5. For any Lipschitz continuous functions f.g: [0, 1]k - R, suppose that there erists y E [0, 1] such that ( 0.
23

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm Gradient Descent for Constrained Group-Objective Convex Smooth Optimization.
Input: D, p, T, Icc, G Arbitrarily set EC
for 1= to to -- do
m(()= [8,+G
Vh(c, D) Ve(g, D)Vi(((e,,)) D)) + Lig(((e; D)) 2 D) D)) G+1 CTc (ct - (()Vh((,, D))
end for return é
For any G O, define the function h : [0, 1]k + R as follows: h(x)) f(x) + G max (0,g(z)) for any
[0, 11 Then for all a [0,1]* 0 such that h(x²) s (0, h(x) a, guaranteed that
g( a L G
f(z) S
min [
f(x) + a,
where Lg is the Lipschitz constant for the function
Using Lemma E.5, we solve the CGOO problem by composition of functions f.g into h. So for the rest of this section, will focus on optimizing the Lagrangian formulation via the function h. We assume that f are 1-smooth but all theorems can be generalized to handle any f.g with smoothness parameters 33 > 0.
Theorem E.6. Suppose we are given convex, 1-Lipschitz, 1-smooth functions f,g: [0, 1] - IR, loss function L:C x (X' x x A)" [0, 1]", and privacy parameter p 2
Then assuming that
KP af
KP
n max
Ω
after T= O()) iterations, Algorithm 4 is a p-2CDP differentially private algorithm that returns a decision E C with the following guarantee:
f(elc, DII f(l(c" ,)) a,
g(l(c, Sa a
with probability at least 9/10 where c² E arg 5t fll(c S)) is the best decision in the feasible set C C TRP,, a>>0 0. We assume access to projection oracle He and that C C TR. lies in P-dimensional space. that is bounded in each aris.
Proof. We combined f and into "new" convex function h(f(c, D)) f(l(e, + G max g(f(c, D)))
defined for all e E C. Its gradient given as D) = Vi(c, DlVf( D)) + [[ (o(f(c,D)) D)) 2 ojV D)Vg((e,) D)). Then note that has smoothness parameter at most Bg + G3, if B Bg are the smoothness parameters for functions f.g respectively.
First, we go through the proof of privacy of Algorithm 4. We invoke Lemma 2.5 in (Bun & Steinke, 2016), which states that if M: X Rd is mechanism that releases ((((z)), o² Iaxx)) for some function 2m + Rd, then M satisfics p-2CDP for
sup D.D
q(D')3
20
where D. D' are neighboring databases that differ in one entry.
Then since f(c, D) Ei= l(c. Dz) and E(c, D) E [0, 1]K,
[VV(((e Vh(l(e, D')lI S (8p + GB))le(e,)) Elc, D'Il
(10)
< (B) + GB,)VK/nn.
(11)
24

---

Published in Transactions on Machine Learning Research (12/2023)
As result, 9, of satisfies p-zCDP (where split the budget amongst the T rounds).
For the utility guarantees, we will rely on Theorem E.3 which requires bound G2 on the norm of subgradients de and & bound on the norm of maximum difference between any two c, E C which is supe,e // c'll s ||C|| = O(VP) S. We have that the subgradients are 9r (VVh(c, D), (Pxp) so that
VVh(,, [)( = (VS( D)) G (l((((, D)) 2 0] Vo(e(e,, -
(12)
+ D)), Vo(((e,, D)),
(13)
< DVTC (DCp
(14)
()+
(15)
by the Cauchy-Schward incquality and the bound on the gradients of f.g.
Then since q NVVh(a, D), Trxr) Vh(c,, D) at with at (0, o² Trxp) have that
4l | = ||| Vh(c D) al
(16)
2 (1 + G) o
(17)
by Fact E.7 so that || = G1- PPP.
Algorithm uses the optimal settings - up to constants of the learning rate (can be derived via differentiation and solving for the constant e) based on Theorem E.3:
VP
m(t) = c -QQ GV Paz
V QU
Then it follows from Theorem E.3 that the "new" function h: [0, 10, IR for the setting of nnt) has the following convergence guarantees:
B[M(,, M 2log T(2SQ)
(18)
VT
=0 logT T VT
(VP(1++))++ Po②)
(19)
and plugging in a we get
logT T VT
G)+ + TPK(1 + G)2
vp
pm
Sctting T ((n) and using that ((PK/p), can further simplify to obtain that
Elh(2, D)] h((((", S)) S a.
if n = O(PK/a0) for G= VK/a. And by Lemma E.5 this implics that
Bif(e(e, D))] ((e(c",S)) + a,
Big(l(?, D)) s
Applying Markov's inequality then gives the desired result.
Fact E. Let Z ~ (O00 Then for any (fized) vector e IR,,
(Z, v) ~ ~(00 1111B))
25


Reviews:
[{"review_id": "e1nyYOg2is", "reviewer": "Reviewer_cZaT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n1. The paper is well-written. \n2. The problem is well-motivated.\n3. The paper is technically sound.\n\nWeaknesses:\n1. The organization of the paper is a bit messy. In particular, the experiment results could be more organized, and the results findings should be highlighted. In the Sec. 6 empirical evaluation, the organizations are divided into multiple paragraphs, with some of the main results deferred to the appendix. This makes the section hard to read. In addition, taking Sec. 6.1 “Increasing Number of Groups” as an individual subsection is strange since this organization will diverge the reader’s attention from the main results of synthetic and real-world credit card datasets.\n2. Empirical baselines are missing. In Sec. 1, “Introduction,” the authors mentioned a series of closely related works (e.g., Abowd & Schmutte (2018) and Xu et al. (2020). I believe that the authors also need to compare their methods empirically and understand the pros and cons of each method compared to the proposed method.\n\t\t\t\t\n\t\t\t\nMinor problems:\n1. Theoretical analysis in Sec. 3.1 needs to be improved: In “Why allocate privacy budget based on standard errors?”, I suggest providing a more rigorous way to present this part (e.g., lemmas).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper aims to mitigate the disparate performance for differential private linear regression. Specifically, the authors design a two-stage approach: (1) tailor the privacy budget to the different groups, (2) use linear optimization oracles in a grid to optimize Lagrangian objectives that correspond to fair learning and optimization. Empirical results demonstrate that the proposed group-aware budget allocation method effectively reduces the disparate performance between different groups on synthetic and real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the Weaknesses and minor problems in the above section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bKPfxhQVAC", "reviewer": "Reviewer_VjZX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* The writing is mostly clear and easy to follow.\n\n* The problem of improving minory group results (under DP) is an important and timely one.\n\n* The proposed approach is simple and seems to work (although see also weaknesses).\n\n### Weaknesses\n\n1) What the authors propose is basically replacing the worse-than-majority prediction performance for the minorities with worse-than-majority privacy protection for the same. I do not agree with the authors that this is acceptable since even very large epsilons have been experimentally shown to protect against some attacks: I would argue that due to the privacy-utility trade-off, DP guarantees will pretty much always be set to be as weak as can be tolerated in order to get the most useful models. In such cases, further weakening the guarantees is not feasible.\n\n2) I am not sure whether it is a good practice to report the DP guarantees as a single guarantee in this case, since we know that the guarantees are different for the majority and the minority groups. To me, this looks like it could very easily give the false impression of having equal privacy protection between the groups.\n\n3) The empirical results, especially for the more complex models, would be more convincing if they included comparisons using various amounts of privacy apportioned between the majority and the minory group, and then showing that the specific amount resulting from looking at the std errors as proposed is a good one compared to all the other possibilities.\n\n4) The analysis only looks at a simple 2-mixture Gaussian, while anything more complex is only tested empirically.\n\n5) The proposed method introduces new hyperparameters that need to be tuned, without much guidance as to how one should set them. This is especially problematic when the tuning needs to be done under DP; e.g., the paper only considers how to divide the privacy budget in the second stage of the proposed algorithm, while the division between stages and division between loss and gradient (in Algorithm 2) are left as free extra hyperparameters.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method for improving prediction accuracy for minority groups under DP guarantees. The basic approach is to divide the total available privacy budget unevenly between groups to improve the relative performance of the predictions on minority groups, while (possibly) hurting the performance on the majority. The authors motivate the approach by analysing a simple 2-Gaussian mixture model, and show empirically that the proposed method results in improved prediction performance for the minority group(s). Additionally, the paper includes some additional empirical results with multiple minority groups, as well as some basic convergence theory under some assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In decreasing order of importance:\n\n1) Glancing at DP release of XX, XY in Lemma C.1, do you assume that 0<= X,Y <=U always? If not, I would think that you need a lower bound on the values as well for the sensitivity (in which case the sensitivity for the cross-terms does not look correct for bounded DP). If yes, please add it explicitly as an assumption.\n\n2) Include some test showing at least a couple of different privacy splits including the one resulting from looking at the std errors to motivate that this is really agood idea (would expect the proposed method to be consistently at least close to the best choice).\n\n3) Maybe reformulate the discussion on the weakening of the minority DP guarantees a bit: might be better to set the target DP guarantees according to the minority protection, while the majority would then get that much more privacy.\n\n4) In summarising the results (e.g., Intro), it would be good to also state the evidence of how much the majority tends to lose. The current wording seems to indicate that this is not a trade-off but simply a gain.\n\n\n\nMinor corrections, typos etc. (no need to comment on these)\n\n* There are some bad sentences in the Appendices (e.g. first paragraph in A.2), probably resulting from moving the text from the main body into the Appendix without fixing it in any way.\n\n* The notation for clipping seems bad, since it leaves one guessing which terms are actually included in the clipping operation.\n\n* Sec 3.2, Setup and Notation \"formulation for fair requires\".\n\n* Algorithm 1, line 8: variance matrix?\n\n* Are the labels mixed in Fig 6? The results look a bit surprising.\n\n* Appendix D: gradient f missing nabla.", "broader_impact_concerns": "It is potentially quite problematic to provide weakened privacy guarantees for minority groups.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XKBkpm8GQc", "reviewer": "Reviewer_BzM5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n  1. The problem studied in this paper is important to the community (Fairness and privacy are both \"big concerns\" in machine learning)\n  2. The experiments observe a significant improvement in comparison with the baseline\n\nWeakness:\n  1. The presentation needs huge improvement (hard to follow)\n  2. The experimental results in Figure 1 do not make sense to me (additional explanation is required from the authors, see the \"requested changes\" section). Owing to this, I temporarily put a \"No\" in \"Claims And Evidence\". I will change it if the revision and/or rebuttal make sense here.\n  3. The complexity analysis of the proposed algorithm is missing.\n  4. Some key points are missing in section 5 (maybe this causes weakness 2)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a group-aware DP fair regression algorithm to avoid the disparate performance for minority groups in differentially private linear and logistic regression models. Theoretically, this paper uses the notion of zCDP to measure the privacy for the proposed algorithm. Experimentally, a significant reduction in mean square error (MSE) is observed on both synthetic and real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "------------------ For weakness 1 ------------------\n1. The meaning of $\\mathcal{A}$ is not clear. On top of page 3: $\\mathcal{A}$  the domain of sensitive attributes. However, in Definition 2.2, $\\mathcal{A}$ seems to represent the set of all groups. What means \"sensitive attributes\" and how is it related to the group?\n\n2. The last sentence on Page 6 is lack of reasoning. I guess the authors is trying to use some composition property of zCDP. However, this should not be common knowledge for the readers. A citation and a detailed explanation need to be added.\n\n3. In Algorithms 1 and 2, what means \"use budget of ... to sample\"? A rigid definition or an explanation should be added.\n\n4. Lots of grammar issues. Especially steps 8 & 9 of Algorithm 1, I think the author intends to say \"Use budget of $\\tau_k/2$ to sample \\tilde{$X^T X$}, which is a differentially private estimation of $X^TX$ (the variance matrix)\". Again, I don't know what means \"Use budget of $\\tau_k/2$ to sample\"\n\n------------------ For weakness 2 ------------------\n\nThe following two properties in the curve of DPNoSE's MSE in Figure 1 look very suspicious to me \n1. It keeps increasing with $\\rho$. \n2. It seems coverage to a large constant when $\\rho\\to\\infty$\n\nFor 1, since a larger $\\rho$ corresponds to a milder privacy requirement, usually the MSE is expected to reduce when $\\rho$ is larger.\n\nFor 2, when $\\rho\\to\\infty$, we no longer need any noise for privacy. If I understand correctly, all four curves should converge to the same (small) constant when $\\rho\\to\\infty$.\n\n------------------ For weakness 3 ------------------\n\nIf the complexity of the proposed algorithm is unknown, the mechanism designers will find it hard to decide because most application scenarios have complexity constraints. Either a comprehensive comparison with the standard mechanisms or a rigid theoretical analysis should be able to fill this gap.\n\n------------------ For weakness 4 ------------------\n1. On page 7, what means OLS? Is it ordinary least-squares? This abbreviation is never defined in the paper. \n2. I don't think the context is clear enough to explain how OLS is applied in the experiments. Thus, further explanation is required. OLS's slopes $\\beta_1$ and $\\beta_2$ may also require rigid definitions.\n\n------------------ Others ------------------\n\nIt looks strange that there are only Lemmas but no Theorem in this paper. I would suggest having a theorem saying that \"The entire scheme (Algorithm 1 and 2) is $\\rho$-zCDP, where $\\rho = \\tau+\\mu$\"\n\n\n\n------------------ After rebuttal and revision------------------\n\nMost of my concerns have been addressed. Changed \"Claims And Evidence\" from \"No\" to \"Yes\".", "broader_impact_concerns": "No concerns about the Broader Impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given the fact that the paper presents a novel algorithm to boost fairness in differentially private learning, and that the empirical evidence shows that the algorithm can provide significant improvements, I believe the paper should be accepted. This sentiment was also generally shared among the reviewers, although one of the reviewers didn't vote for acceptance.

However, the paper still needs some polishing before publication. As noted by the reviewers BzM5 and cZaT in their original reviews, the organization of the paper needs some improvements. After reading the updated manuscript, I agree with the reviewers on this. For me the most crucial parts that need to be clarified before acceptance are:
1. Section 3.1: how the Lemma 3.1 connects to the rest of the Section. More precisely, how does the Lemma 3.1 motivate the paragraph "Why allocate privacy budget based on standard errors?".
2. Clarify the importance of Section 5, and how it connects to the rest of the paper.
3. Consider moving the "Helper Lemmas" to the appendix, and moving the empirical evidence from appendix back to the main paper. I think this would highly benefit the reader.
4. Provide the clarifications you have promised post-rebuttal. Specifically the ones listed in response to [my comment](https://openreview.net/forum?id=SnPEhMyuYX&noteId=UvTlrPKIG6).
Decision: Accept (poster)