Stochastic Differentially Private and Fair Learning
Authors: Andrew Lowy
Devansh Gupta
Meisam Razaviyayn
Venue: ICLR 2023 poster (2023)
Keywords: algorithmic fairness
differential privacy
private fair learning
stochastic optimization

Abstract: Machine learning models are increasingly used in high-stakes decision-making systems. In such applications, a major concern is that these models sometimes discriminate against certain demographic groups such as individuals with certain race, gender, or age. Another major concern in these applications is the violation of the privacy of users. While fair learning algorithms have been developed to mitigate discrimination issues, these algorithms can still leak sensitive information, such as individuals’ health or financial records. Utilizing the notion of differential privacy (DP), prior works aimed at developing learning algorithms that are both private and fair. However, existing algorithms for DP fair learning are either not guaranteed to converge or require full batch of data in each iteration of the algorithm to converge. In this paper, we provide the first stochastic differentially private algorithm for fair learning that is guaranteed to converge. Here, the term “stochastic" refers to the fact that our proposed algorithm converges even when minibatches of data are used at each iteration (i.e. stochastic optimization). Our framework is flexible enough to permit different fairness notions, including demographic parity and equalized odds. In addition, our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes. As a byproduct of our convergence analysis, we provide the first utility guarantee for a DP algorithm for solving nonconvex-strongly concave min-max problems. Our numerical experiments show that the proposed algorithm consistently offers significant performance gains over the state-of-the-art baselines, and can be applied to larger scale problems with non-binary target/sensitive attributes.

Published as a conference paper at ICLR 2023
STOCHASTIC DIFFERENTIALLY PRIVATE AND FAIR LEARNING
Andrew Lowy University of Southern Califomia lowyalusc.ede
Devansh Gupta*
Indraprastha Institute of Information Technology. Delhi devansh1 91 6001 i i iitd. ww..d........................... ac.in
Meisam Razaviyayn University of Southern Californa
razaviya@use.cm
ABSTRACT
Machine learning models are increasingly used in high-stakes decision- making systems. In such applications, major concern that these models sometimes discriminate against certain demographic groups such as individuals with certain race, gender, or age. Another major concern these applications is the violation of the privacy of users. While fair learning algorithms have been developed to mitigate discrimination issues, these algorithms can still leak sensitive information, such individuals' health or financial records. Utilizing the notion of differential privacy (DP), prior works aimed developing learning algorithms that are both private and fair. However, existing algorithms for DP fair learning are either not guaranteed to converge or require full batch data in each iteration of the algorithm to converge. In this paper, provide the first stochastic differentially private algorithm for fair learning that guaranteed to converge. Here, the term "stochastic" refers to the fact that our proposed algorithm converges at each iteration (i.e. stochastic optimization). Our framework is flexible enough permit different fairness notions, including demographic parity and equalized odds. In addition, our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes. As a byproduct of our convergence analysis, we provide the first utility guarantee for a DP algorithm for solving nonconvex-strongs concave min-max problems. Our numerical experiments show that the proposed algorithm consistently offers significunt performunce gains over the state-of-the-e buselines, and can be applied to larger scale problems with non-binary target/sensitive attributes.
when minibatches of data used
INTRODUCTION
In recent years, machine learning algorithms have been increasingly used inform decisions with far-reaching consequences (e.g. whether to release someone from prison grant them loan), raising concerns about their compliance with laws, regulations, societal norms, and ethical values. Specifically, machine learning algorithms have been found to discriminate against certain "sensitive" demographic groups (e.g. racial minorities), prompting profusion of algorithmic fairness rescarch (Dwork et al., 2012; Sweeney, 2013; Datta et al., 2015; Feldman et al., 2015; Bolukbasi et al., 2016; Angwin et al., 2016; Calmon et al., 2017: Hardt et al., 201 Fish et al., 2016; Woodworth et al., 2017; Zafar al., 2017; Bechavod & Ligett, 2017; Kearns et al., 2018; Prost et al., 2019; Baharlouei et al., 2020; Lowy et al., 2022a). Algorithmic fairness literature aims to develop fair machine learning algorithms that output con-discriminatryy predictions.
Fair learning algorithms typically need access to the sensitive data in order to ensure that the trained model is non-discriminatory. However, consumer privacy laws (such as the F.U. General Data Protection Regulation) restrict the use of sensitive demographic data algorithmic decision-making.
Work done visiting scholar the University of Southern California, Viterhi School of Engineering.

---

Published as a conference paper at ICLR 2023
These two requirements fair algorithms trained with private data penta-presetts quandary: how can we train a model to be fair to a certain demographic if we don't t even know which of our training examples belong to that group?
The works of Veale & Binns (2017); Kilbertus et al. (2018) proposed a solution to this quandary using secure multi-party computation (MPC), which allows the learner to train a fair model without directly accessing the sensitive attributes. Unfortunately, as Jagielkki et al. (2019) observed, MPC does not prevent the trained model from leaking sensitive data. For example, with MPC, the output of the trained model could be used to infer the race of an individual in the training data set (Fredrikson et al., 2015; He al., 2019; Song et al., 2020; Carlini al., 2021). To prevent such leaks, Jagielski et al. (2019) argued for the use of differential privacy (Dwork et al., 2006) in fair learning. Differential privacy (DP) provides a strong guarantee that no company (or adversary) can learn much more about any individual than they could have learned had that individual's is data never been used.
Since Jagielski et al. (2019), several follow-up works have proposed alternate approaches to DP fair learning (Xu et al., 2019; Ding et al., 2020; Mozannar et al., 2020; Tran et al., 202 Ib;a; 2022). As shown in Fig. 1, each of these approaches suffers from at least two critical shortcomings. In particular, none of these methods huve convergence guarantees when mini-butches of data are used in training. In training large-scale models, memory and efficiency constraints require the use of small minibatches in each iteration of training (i.e. stochastic optimization). Thus, existing DP fair learning methods cannot be used in such settings since they require computations on the full training data set in every iteration. See Appendix A for more comprehensive discussion of related work.
Our Contributions: In this work, we propose a novel algorithmic framework for DP fair learning. Our approach builds on the non-private fair learning method of Lowy et al. (2022a). We consider a regularized empirical risk minimization (ERM) problem where the regularizer penalizes fairness violations, as measured by the Exponential Rényi Mutual Information. Using a result from Lowy et al. (2022a), we reformulate this fair ERM problem as a min-max optimization problem. Then, we use an efficient differentially private variation of stochastic gradient descent-ascent (DP-SGDA) to solve this fair ERM min-max objective. The main features of our algorithm are:
1. Guaranteed convergence for any privacy and fairesss level, even when mini-batches of data are used in each iteration of training (i.e. stochastic optimization setting). As discussed, stochastic optimization is essential in large-scale machine learning scenarios. Our algorithm is the first stochastic DP fair learning method with provable convergence.
2. Flexibility to handle non- non-binary classification with multiple (non-binane sensitive attrbutes (e.g. race and gender) under different fairness notions such as demographic parity or equalized odds. In each of these cases, our algorithm is guaranteed to converge.
Empirically, we show that our method outperforms the previous state-of-the-art methods in terms of fairness vs. accuracy trade-off across all privacy levels. Moreover, our algorithm is capable of training with mini-batch updates and can handle non-binary target and non-binary sensitive attributes. By contrast, existing DP faimess algorithms could not converge in our stochastic/non-bet
experiment.
A byproduct of our algorithmic developments and analyses is the first DP convergent algorithm for nonconvex min-max optimization: namely, we provide an upper bound on the stationarity gap of DP-SGDA for solving problems of the form ming maxw F(O, W). where F(,, W) is non-convex. We expect this result to be of independent interest to the DP optimization community. Prior works that provide convergence results for DP min-max problems have assumed that F(s, W) is either (strongly) convex (Boob& & Guzmán, 2021; Zhang al., 2022) or satisfies generalization of strong convexity known as the
(PL) condition (Yang et al., 2022).
PROBLEM SETTING AND PRELIMINARIES
Let 2 = (2, (1, [ be data set with non-sensitive features 2; X, discrete sensitive attributes (e.g. race, gender) 8; E [k] + fl....,k, k), and labels E [/]. Let (o(x) denote the model predictions parameterized by 0, and E(O, xr, y) (()(()), y) be loss function (e.g. cross-entropy loss). Our goal is to (approximately) solve the empirical risk minimization (ERM) problem
[(0) = Σ 8(, Izs vi)
min 0
(1)
2

---

Published as a conference paper at ICLR 2023
in fair manner, while maintaining the differential privacy of the sensitive data [s))_.. We consider two different notions fairness in this work:'
Definition 2.1 (Fairness Notions). Let A: : 2 y be classifier.
satisfies demographic parity (Dwork et al., 2012) if the predictions A(Z) are statistically independent of the sensitive attributes.
A satisfies equalized odds (Hardt et al., 2016a) if the predictions A(Z) are conditionally independent of the sensitive attributes given Y y for all y.
Depending on the specific problem at hand, one fairness notion may be more desirable than the other (Dwork et al., 2012; Hardt et al., 2016a).
Reference
Non-binary target?
Muttiple fairnsss
Convergence guarantea (poty: time]?
Guarantees
with
In practical applications, achieving exact fair- ness, i.e. (conditional) independence of γ and S, unrealistic. In fact, achieving exact fair- ness can be impossible for differentially pri- vate algorithm that achieves non-trivial accu- racy (Cummings et al., 2019). Thus, instead aim to design an algorithm that achieves small fairness violation the given data set Z. Fair- ness violation can be measured in different ways: see e.g. Lowy al. (2022a) for thorough sur- vey. For example, if demographic parity is the desired fairness notion, then one can measure (empirical) demographic parity violation by
This work
Jagielski al.
(201))
N/A
Jagielskiet
(2019)
[n-proo)
at
(2019)
Ding al.
(2020)
Mozannar et (2020)
Tran (201aa)
Tran (2021b)
max yey SES
P9)s(019) P (
Tran (2022)
where P denotes an empirical probability calcu- lated directly from (Z, 1
Figure I: Comparison with existing works. "Guarantee" refers to provable guarantee. N/A: the post-processing method of Jagielski al. (2019) not an iterative algo- rithm. *Method requires access to the sensitive data at test time. The in-processing method of Jagielski et al. (2019) is inefficient. The work of Mozannar et al. (2020) specializes equalized odds, but most of their analysis seems extendable to other fairness notions.
Next, we define differential privacy (DP). Fol- lowing the DP fair learning literature in (Jagiel- ski et al., 2019; Tran et al., 2021b; 2022)), we consider relaxation of DP, which only the sensitive allributes require privacy. Say Z and Z' are adjucent with respect to sensitive data if Z = { Vs, st) Z' = {I,,, Vs, s and there is a unique E [n]] such that s, * $
1). A randomized algorithm A is (e, 8) diffeeerrntially private w.r.. sensitive attributes S (DP) if for all pairs data sets Z, Z' that are adjacent w.r.t. sensitive attributes. we have
Definition 2.2 (Differential Privacy w.r.t. Sensitive Attributes). Let 0, 8 [0,
P(A(Z) E O) < <(P(((()) E 0) 5
(3)
for all measurable O y.
As discussed in Section 1, Theorem 2.2 is useful if a company wants to train fair model, but is unable to use the sensitive attributes (which are needed to train a fair model) due to privacy concerns and laws (e.g., the E.U. GDPR). Theorem 2.2 enables the company privately use the sensitive attributes to train a fair model, while satisfying legal and ethical constraints. That being said, Theorem 2.2 still may not prevent leakage of non-sensitive data. Thus, if the company is concerned with privacy of user data beyond the sensitive demographic attributes, then should impose DP for all the features. Our algorithm and analysis readily extends to DP for all features: Section 3.
Throughout the paper, we shall restrict attention to data sets that contain at least p- o-fraction of every sensitive attribute for some p (0, 1): i.c. Ž Σ (s,-r) 2 p for all r [k]. This is reasonable
'Our method can also handle any other fairness notion that can be defined in terms of statistical (conditional) independence, such as equal opportunity. However, our method cannot handle all faimess notions: for example, false discovery and calibration error not covered by our framework.
3

---

Published as a conference paper at ICLR 2023
assumption in practice: for example, if sex is the sensitive attribute and data set contains all men, then training a model that is fair with respect to sex and has a non-trivial performance (better than random) seems almost impossible. Understanding what performance is imm-possibble for DP fair learning in the absence of sample diversity is an important direction for future work.
3 PRIVATE FAIR ERM VIA EXPONENTIAL RÉNYI MUTUAL INFORMATION
standard in- mn-processing strategy in the literature for enforcing fairness is to add a regularization term the empirical objective that penalizes fairness violations (Zhang al., 2018; Donini et al., 2018; Mary et al., 2019; Baharlouei et al., 2020; Cho et al., 2020b; Lowy et al., 2022a). We can then jointly optimize for fairness and accuracy by solving
min {E(0) sD(Y,s.))
where D is some measure of statistical (conditional) dependence between the sensitive attributes and the predictions (given Y), and A > O is a scalar balancing faimess and accuracy considerations. The choice of D is crucial and can lead to different fairness-accuracy profiles. Inspired by the strong empirical performance and amenability to stochastic optimization of Lowy et al. (2022a), we choose DD to be the Exponential Rényi Mutual Information (ERMI):
Definition 3.1 (ERMI- Exponential Rényi Mutual Information). We define the exponential Rényi mutual information between random variables y and S with empirical joint distribution Py,s and marginals pg. ps by:
Py. (V.)( py ( (Ss
- 11 Σ Σ s6,r( JE(T] re(k) Do(i)s(())
D S) :- E
(ERMI)
Theorem 3.1 is what we would use if demographic parity were the desired faimess notion. If instead one wanted to encourage equalized odds, then Theorem 3.1 can be readily adapted to these fairness notions by substituting appropriate conditional probabilities for PÝ,s S py, and Ps in (ERMI); see Appendix B for d It can be shown that ERMI > O, and is zero if and only demographic parity (or equalized odds, for the conditional version of ERMI) is satisfied (Lowy et al., 2022a). Further, ERMI provides an upper bound on other commonly used measures of fairness violation: e.g.) (2), Shannon mutual information (Cho et al., 2020a), Rényi correlation (Baharlouei et al., 2020), Lg fairness violation (Kearns et al., 2018; Hardt et al., 2016a) (Lowy et al., 2022a). This implies that any algorithm that makes ERMI small will also have small fairness violation with respect these other notions. Lastly, (Lowy et al., 2022a, Proposition 2) shows that empirical ERMI (Theorem 3.1) 1) is an asymptotically unbiased estimator of "population ERMI"- can be defined as Theorem 1. except that empirical distributions are replaced by their population counterparts.
Our approach to enforcing fairness is to augment (1) with an ERMI regularizer and privately solve:
min FERMI(O) = ((0) + (D)())(X))
(FERMI obj.)
Since empirical ERMI is an asymptotically unbiased estimator of population ERMI, a solution to (FERMI obj.) is likely to generalize to the corresponding fair population risk minimization problem (Lowy al., 2022a). There are numerous ways to privately solve (FERMI obj.). For example, one could use the exponential mechanism (McSherry & Talwar, 2007), run noisy gradient descent (GD) (Bassily et al., 2014). The problem with these approaches is that they are inefficient or require computing gradients at every iteration, which is prohibitive for large-scale problems, as discussed earlier. Notice that we could not run noisy stochastic GD (SGD) on (FERMI obj.) because we do not (yet) have a statistically unbiased estimate of Va Vnoon (X)()
Our next goal is derive stochastic, differentially private fair learning algorithm. For feature input x, let the predicted class labels be given by 7(z, 0) = j E [4] with probability [z 0), where F(x, 0) is differentiable in 0, has range [0, 1]', and Σ (x,
1. For instance,
TTo simplify the presentation, we will assume that demographic parity is the fairness notion of interest in the remainder of this section. However, consider both fairness notions in our numerical experiments.
4

---

Published as a conference paper at ICLR 2023
0)) could represent the output of neural net after softmax layer the probability label assigned by a logistic regression model. Then we have the following min-max re-formulation of (FERMI obj.):
(F
Theorem 3.2 (Lowy et al. (2022a)). There are differentiable functioon i/s such that (FERMI obj.) is
equivalent to
F(0.W) ((0) Σ 50.0mm
min max WER
Further, (0, ) is strongly concave for all 0.
The functions v; are given explicitly in Appendix C. Theorem 3.2 is useful because it permits us to stochastic optimization solve (FERMI obj.): for any batch size e [n]. the gradients (with respect f and W) of 1 m Eies ((x,, y4; 0) + (0) W) are statistically unbiased estimators of the gradients of F(0, W). if B is drawn uniformly from Z. However, when differential privacy of the sensitive attributes is also desired, the formulation (4) presents some challenges, due to the non-convexity of ((,, W). Indeed, there is no known DP algorithm for solving non-convex min-max problems that is proven converge. Next, we provide the first such convergence guarantee.
3.1 NOISY DP-FERMI FOR STOCHASTIC PRIVATE FAIR ERM
Our proposed stochastic DP algorithm for solving (FERMI obj.), is given in Algorithm 1. It is noisy DP variation of two-timescale stochastic gradient descent ascent (SGDA) Lin et al. (2020).
Algorithm DP-FERMI Algorithm for Private Fair ERM
1: Input: 0g R:4, Wo Rxx step-sizes (no. Nw)) fairness parameter À > 0, iteration
number T. minibatch size [Bll = m e [n], set W R xxx noise parameters o og.
2: Compute P-1/2
3: for ( 0, 0,l,...,T T do
4: Draw mini-batch B, of data points ((z,, St. (1))
To 5: Set dt+1 < 0g |a,
EiEB, (Vol(z,, + ((Vode( W:) + 4z), where un
(O, (00,ogIaa
6: Set W IIw (W, + The B E (e WT) + vil)
where V is k x matrix with independent random Gaussian entries (V)rs ~(0,0
7: end for
8: Pick i uniformly at random from (1....,7).
9: Return: 02 = 0r.
Explicit formulae for (o W,) and V (0,, W;) are given in Theorem D.1 (Appendix D). We provide the privacy guarantee of Algorithm Theorem 3.3:
Theorem 3.3. Let 2m(1/))), (0, 1), and T
Assume F(x,-) is Lg-Lipschita for all and I(W:)ral & D for all i [T), [k],j E [1]. Then, for o > 16T1n(1/6) and In(1/8TT In(1/81 Cutpp
vE n 2m
o >
Algorithm I is (DP with respect to the sensitive attributes for all data
sets containing least p-fraction of minority attributes. Further, if o
32T1/( 222
( D2+ and
641. Io(1//0T 32.2 11P() then Algoritium I is (c, 8)DP (with respect all features) 2nd
of for all data sets containing at least p-fraction of minority attributes.
Fnd
See Appendix D for the proof. Next, we give convergence guarantee for Algorithm 1:
Theorem 3.4. Assume the loss function E(-, x. y) and F(x,,) are Lipschitz continuous with Lip- schitz, gradient for all (a, y), and Ps(r) p 0 A r E [k]. In Algorithm choose W to be

---

Published as a conference paper at ICLR 2023
sufficiently large ball that contains W* argmaxw F(0, () for every 0 in some neigh- borhood of tt E argming maxw F(0, W). Then there exist algorithmic parameters such that the (e, 6DD Algorithm returns Or with
(
(
[mmax(do ki) (n(1/8)
E (FERM((T)))
en
treating D diameter(W), A. I, and the Lipschitz and smoothness parameters of and F as constants.
Theorem 3.4 shows that Algorithm finds an approximate stationary point of (FERMI obj.). Finding approximate stationary points is generally the best one can hope to do in polynomial time for non- convex optimization (Murty & Kabadi, 1985). The stationarity gap Theorem 3.4 depends on the number of samples n and model parameters do, the desired level of privacy (c, (c, and the number of labels I and sensitive attributes k. For large-scale models (e.g. deep neural nets), we typically have da >> 1 and k, I O(1), so that the convergence rate of Algorithm I is essentially immune to the number of labels and sensitive attributes. contrast, no existing works with convergence guarantees are able handle non non-binary classification (1 2), even with fill batches and single binary sensitive attribute.
A few more remarks are in order. First, the utility bound in Theorem 3.4 corresponds to DP for all of the features. DP is only required for the sensitive attributes, then using the smaller oî o² in Theorem 3.3 would improve the dependence
constants D, 1, Lo in the utility bound. Second, the choice of W in Theorem 3.4 implies that (4) is equivalent ming maxwew F(e, W). which what our algorithm directly solves (c.f. (7)). Lastly, note that while we return a uniformly random iterate in Algorithm for our theoretical convergence analysis, we recommend returning the last iterate 0r in practice: our numerical experiments show strong performance of the last iterate.
In Theorem E. of Appendix E, we prove result which is more general than Theorem 3.4. Theo- rem E.1 shows that noisy DP-SGDA converges to approximate stationary point of any smooth nonconvex-strongle concave min-max optimization problem (not just (4)). We expect Theorem E. to be of general interest the DP optimization community beyond its applications to DP fair learning, since it is the first DP convergence guarantee for nonconvex min-max optimization. We also give a bound on the iteration complexity T in Appendix E.
The proof of Theorem E. involves a careful analysis of how the Gaussian noises propagate through the optimization trajectories of 0, and we Compared with DP non-convex minimization analyses (e.g. Wang et al. (2019); Hu et al. (2021); Ding et al. (2021b); Lowy et al. (2022b)), the two noises required privatize the solution of the min-max problem consider complicates the analysis and requires careful tuning of V72 and 1/W. Compared to existing analyses of DP min-max games in Boob & Guzmán (2021); Yang et al. (2022); Zhang al. (2022), which assume that f(. is conver or PL, dealing with non-convexity is a challenge that requires different optimization techniques.
4 NUMERICAL EXPERIMENTS
In this section, we evaluate the performance of our proposed approach (DP-FERMI) in terms of the fairness violation vs. test error for different privacy levels. We present our results in two parts: In Section 4.1, assess the performance of our method in training logistic regression models on several benchmark tabular datasets. Since this is a standard setup that existing DP fairness algorithms can handle. we are able to compare our method against the state-of-ther of-the-rrt baselines. We carefully tuned the hyperparameters of all baselines for fair comparison. We find that DP-FERMI consistently outperforms all state-of-ther These observations hold for both demographic parity and equalized odds fairness notions. To quantify the improvement of our results over the state-of-the-e baselines, we calculated the performance gain with respect to faimesss violation (for fixed accuracy level) that our model yields over all the datasets. We obtained a performance gain of demographic parity that was 79.648 % better than Tran et al. (2021b) on average, and 65.89% better median. The average performance gain of equalized odds was 96.65% while median percentage gain was 90.02%. In Section 4.2, we showcase the scalability of DP-FERMI by using it to train deep convolutional neural network for classification large
baselines across all data sets and all privacy levels.

---

Published as a conference paper at ICLR 2023
image dataset. In Appendix F, give detailed descriptions of the data sets, experimental setups and training procedure, along with additional results.
4.1 STANDARD BENCHMARK EXPERIMENTS: LOGISTIC REGRESSION ON TABULAR DATASETS
In the first set of experiments we train logistic regression model using DP-FERMI (Algorithm 1) for demographic parity and a modified version of DP-FERMI (described in Appendix F) for equalized odds. We compare DP-FERMI against all applicable publicly available baselines in each expeiment.
4.1.1 DEMOGRAPHIC PARITY
We use four benchmark tabular datasets: Adult Income, Retired Adult, Parkinsons, and Credit-Card dataset from the UCI machine learning repository (Dua & Graff (2017)). The predicted variables and sensitive attributes are both binary in these datasets. We analyze fairness-accuree
trade-offs with four different values of {0.5, 1, 3, 9} for each dataset. We compare against state-of-the-an algorithms proposed in Tran et al. (2021a) and (the demographic parity objective of) Tran et al. (2021b). The results displayed are averages over 15 trials (random seeds) for each value of c.
For the Adult dataset, the task is to predict whether the income is greater than $50K or not keeping gender as the sensitive attribute. The Retired Adult dataset is the same as the Adult dataset, but with updated data. We use the same output and sensitive attributes for both experiments. The results for Adult and Retired Adult are shown in Figs. 2 and 6 (in Appendix F.2). Compared to Tran et al. (a,)), DP- offers superior fairness- tradcoff's at every privacy (c) level.
* Tan et al. (2021b)
0.20
* Tran et al. (2321b) Tran (232la)
Taan (2021a) FERMI
Demopraphic Panty Wolatnn
0,375
Damog aphic Failty Volation
DF
0.150
Non-Prusze FERMI Private
0.15
Non-Frivate FERMI Private
0.325
0.300
0.10
0.050
0.05
0.025
0.000
0.00
0.16
0.27
218
0.19
0.20
0.22
0.2
a23
0.6
0.7
0.15
0.19
0.20
021
0.22
0.23
Misclesslk.aaiion
Mistlesilkaaiii
(a) 0.5
(b) E=
0,200
* (2021b) Tan ot al. (2021a]
0,200
*
(2321b)
Demographic Party Party Welaton
0.175
DP-FERMI
Demographic Party Vilazion
0.175
DP FLRMI
Tran et (2321a)
0.150
Non Privece TERMI
0.150
Non Privete ICRMI
Non Private Nan Fair ERM
Non Private Non Fair ERM
0.125
0.125
0,100
0.100
0.0/2
0.075
0.030
0.050
0.023
0.025
0.000
0.000
0.155
0,160 0.165 0.170 0.175 0.180 0.185 0.190 0:195
0.16
D177
0.88
0.19
0.20
Misclesilkaaliinn Eruur
Mistlessii Brur
(C) e
(d) 9
Figure 2: Private, Fair (Demographic Parity) logistic regression on Adult Dataset.
In the Parkinsons dataset, the task is to predict whether the total UPDRS score of the patient is greater than the median or not keeping gender as the sensitive attribute. Results for e E (1,3) are shown in Fig. 3. See Fig. 8 in Appendix F for (0.5.9). Our algorithm again outperforms the baselines Tran et al. (2021a;b) for all tested privacy levels.
In the Credit Card dataset, the task is to predict whether the user will default payment the next month keeping gender as the sensitive attribute. Results are shown in Fig. 7 in Appendix F.2. Once again, DP-FERMI provides the most favorable sateec--farnesssacco profile.
7

---

Published as a conference paper at ICLR 2023
0.08
Tan et al, (2021b)
Tran et (2321b) (2321a) DP FLRMI
Tan (2021a)
Demographc Pot Party Wolo on
0.07
DP-TERMI
Demegrapiic Party Violz on
0.05
hon Priveze
Kon Private Non Fair ERM
0,0B
Privete FCRMI Non Privale Non Fair ERM
0.04
0.05
0.04
0.04
0.08
0.03
0.02
0.02
0.04
0.05
0.06
0.07
0.05
0.09
0.10
0.11
0.2
0.34
0.06
0.08
0.10
0.12
Misclssilkaaionn Error
Misdessification Erior
(a)
(b)
Figure 3: Private, Fair (Demogrpahic Parity) logistic regression on Parkinsons Dataset
4.1.2 EQUALIZED ODDS
Next, we consider the slightly modified version of Algorithm I, which is designed to minimize the Equalized Odds violation by replacing the absolute probabilities in the objective with class conditional probabilities: see Appendix F.2.4 for details.
We considered the Credit Card and Adult datasets for these experiments, using the same sensitive attributes as mentioned above. Results for Credit Card are shown in Fig. 4. Adult results are given in Fig. 9 in Appendix F.2.4. Compared to Jagielski et al. (2019) and the equalized odds objective Tran et al. (2021b), our equalized odds variant of DP-FERMI outperforms these state-of-the-un baselines at every privacy level.
TI GEG221
The et IDRZIN
Tox et IDOZIN
Eoulaad Oda DoMrbe
0:44
Me Pilooo Nan YU EAP
Mix PVlvW FFASE
FFAMI
Equkteed Odt COAArTO
0.00
Nen Rijun FIRM
Non +hitt Soe nolr DPee
Equatied Odta CQMATEO
0.02
0034-
Ion +kate Soe fok DPM
0:2-
0.52
0:2
am
0.01
0.00
0.00
Mix Scataa Erorr
(a) = 0.5
(b)
(c) 6 ==
Figure 4: Private, Fair (Equalized Odds) logistic regression on Credit Card Dataset
4.2 LARGE-SCALE EXPERIMENT: DEEP CONVOLUTIONAL NEURAL NETWORK ON IMAGE DATASET
In our second set of experiments, we train a deep 9-layer VGG-like classifier (Simonyan & Zisserman, 2015) with d 1.6 million parameters on the UTK- dataset (Zhang et al., 2017) using Algo- rithm 1. We classify the facial images into 9 age groups similar to the setup in Tran et al. (2022), while keeping race (containing 5 classes) as the sensitive attribute. See Appendix F.3 for more details, We analyze consider with four different privacy levels E {10, 25, 50, 100). Compared to the tabular datasets, larger e is needed to obtain stable results in the large-scale scale setting since the number of parameters d is much larger and the cost of privacy increases with d (see Theorem 3.4). Larger values of é > 100 were used in the baseline Jagielski al. (2019) for smaller scale experiments.
The results in Fig. 5 empirically verify our main theoretical result: DP- converges even for non-binary classification with small batch size and non-binary sensitive attributes. We took Tran et al. (2021a;b) as our baselines and attempted to adapt them to this non-binary large-scale task. We observed that the baselines were very unstable while training and mostly gave degenerate results method was able to obtain
(predicting single output irrespective of the input). By contrast, stable and meaningful tradeoff curves. Also, while Tran et al. (2022) reported results on UTK-Face, their code is not publicly available and we were unable reproduce their results.
8

---

Published as a conference paper at ICLR 2023
0:30-
DP FERMI
DR-FERMI
Privala FERMI
0.50
Non Frivate FERMI
Derriggep Parity Volation
0.25
Non Private Non Fair ERM
Demograp aphic Partyy Volatin
Non Private Non Fair ERM
0.25
0:20
0.15-
0.15
0.30
010
0.05
2.55
0.00
3.3
0.4
0.5
0.6
0.7
0.8
0.9
0.3
0.4
0.5
0.6
0.7
0.8
Misclassficctor Enar
Misclassification Emrr
(a) 10
(b) c
25
DP-FERMI
DF-FERMI
0.30
Private FLRMI
Non Private FERMI
Den aphii Parily Viseeion
Nor Private Non Fair ERM
Damogran aphic Parity violation
0.25
Non Private Non Fair ERM
0.25
0.20
0.20-
0.35
0.30
0.05
0.3
0.4
0.5
0.6
0.7
0.8
0.30
0.35
0:40
0.45
0,50
0.55
0.60
Misc asafficttion Emor
Misclassiiicatoo Emor
(c) = 50
(d)
100
Figure 5: DP-FERMI on a Deep CNN for Image Classification on UTK-Face
5 CONCLUDING REMARKS
Motivated by pressing legal, ethical, and social considerations, we studied the challenging problem of learning fair models with differentially private demographic data. We observed that existing works suffer from few erucial limitations that render their approaches impractical for large-scale problems. Specifically, existing approaches require full batches of data in each iteration (and/or exponential runtime) in order to provide convergence/accuracyy guarantees. We addressed these limitations by deriving DP stochastic optimization algorithm for fair learning, and rigorously proved the convergence of the proposed method. Our convergence guarantee holds even for non-binary classification (with any hypothesis class, even infinite VC dimension. c.f. Jagielski et al. (2019)) with multiple sensitive attributes and access random minibatches of data in each iteration. Finally, we evaluated our method in extensive numerical experiments and found that it significantly outperforms the previous otate-of-the-art models, in terms of fairness-accuracy tradeoff. The potential societal impacts of our work are discussed in Appendix G.
ACKNOWLEDGMENTS
This work was supported in part with funding from the NSF CAREER award 2144985, from the YIP AFOSR award, from a gift from the USC-Meta Center for Research and Education in AI & Learning. and from a gift from the USC-Amazon Center on Secure & Trusted Machine Learning.

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. doi: 10.1145/297674922978881 URL http: / /txx doo.doiooooo... 10. 11w.1..1/99971444411111 297.//9997774..7.81...
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification, International Conference on Machine Learning, pp. 60 69. PMLR, 2018.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, 2016.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact model accuracy. Advances in neural information processing systems, 32, 2019.
Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In ICLR, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, 2019.
Yahav Bechavod and Katrina Ligett. Penalizing unfairness binary classification, arXiv preprint 17X1::1707.00044, 2017.
Yahav Bechavod, Katrina Ligett, Aaron Roth, Waggoner, and Zhiwei Steven Wu. Equal opportu- nity in online classification with partial feedback. arXiv preprini arXiv: 1902.0224,, 2019.
Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 434994455,, 2016.
Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. arXiv preprint urXiv:2104.02988 2021.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre- pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems, pp. 3992-4001, 2017.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, al. Extracting training data from large language models. 30th USENIX Security Symposium (USENIX Security 21), pp. 2633 (033-2650, 2021.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. fair classifier using mutual information. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2521-2526 IEEF, 2020a.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estimation. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Aariia-Floria Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020b.
Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern. On the compatibility of privacy and faimess.. In Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, pp. 309-315, 2019.
Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings. Proceedings privacy enhancing technologies, 2015(1):92-112, 2015.
10

---

Published as a conference paper at ICLR 2023
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), in Neural Information Processing Systems, volume 34, pp. 6478-6490. Curran As- sociates, Inc., 2021a. URL URL. http:::://///cceeeeeeeeee 92e54441e63888 www.bbabbbbbbbaea wtc.coobbbacc44cccccc (3c-00099-055445500-0-50300 pdf.
meurips. ps. cc htcc/apper/222//111
Jiahao Ding, Xinyue Zhang, Xiaohuan Li, Junyi Wang. Rong Yu, and Miao Pan. Differentially private and fair classification via calibrated functional mechanism. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 622-629, 2020.
Jiahao Ding, Guannan Liang. Jinbo Bi, and Miao Pan. Differentially private and communication efficient collaborative learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7219-7227, 2021b.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, pp. 2791-2801, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://////rchhii ics. uci. ics.uci.edu/mii edu/ml.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in
private data analysis. In Theory of cryptography conference, pp. 284.284. Springer, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp.
214-226, 2012.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 259-268, 2015.
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. confidence- based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference Data Mining, pp. 144-152. SIAM, 2016.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference Computer and Communications Security, pp. 1332-1333, 2015.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016a.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1225-1234, New York, New York, USA, 20-22 Jun 2016b. PMLR. URL http:/ /ttp///eceengg..cc/// mlr. press v48 14AB/hharrt1. html.
Zecheng He, Tianwei Zhang, and Ruby B Lee. Model inversion attacks against collaborative inference. In Proceedings of the 35th Annual Computer Security Applications Conference, pp. 148-162, 2019.
Rui Hu, Yuanxiong Guo, and Yanmin Gong. Concentrated differentially private federated learning with performance analysis. IEEE Open Journal of the Computer Society, 2:276-289, 2021, doi: 10.1
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvaipee Malvajerdi, and Jonathan Ullman. Differentially private fair learning. In International Conference on Machine Learning, pp. 3000-3008. PMLR, 2019.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning. pp. 2564-2572, 2018.
11

---

Published as a conference paper at ICLR 2023
Niki Kilbertus, Adrià Gascón, Matt Kusner, Michael Veale, Krishna Gummadi, and Adrian Weller. Blind justice: Fairness with encrypted sensitive attributes. In International Conference on Machine Learning, pp. 2630-2639 PMLR, 2018.
Niki Kilbertus, Manuel Gomez Rodriguez, Bernhard Schölkopf, Krikamol Muandet, and Isabel Valera. Fair decisions despite imperfect predictions. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 277-287. PMLR, 26-28 Aug 2020.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via sesg methods. In Proceedings of the s1 International Conference on Neural Information Processing Systems, pp. 2345-2355 2017.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems, In International Conference on Machine Learming, pp. 6093, PMLR, 2020.
Andrew Lowy, Sina Baharlouei, Rakesh Pavan, Meisam Razaviyayn, and Ahmad Beirami. A stochastic optimization framework for fair risk minimization. Transactions on Machine Learning Research, 2022a.
Andrew Lowy, Ali Ghafelebashi, and Meisam Razaviyayn, Private non-convex federated learning without a trusted server. arXiv preprint arXiv:2203.0611 2022b.
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Faimess-aware learning for continu- ous attributes and treatments. In International Conference on Machine Learning, pp. PMLR, 2019.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS'07), pp. 94-103. IEEE, 2007.
Hussein Mozannar, Mesrob Ohannessian, and Nathan Srebro. Fair learning with private demographic data. In International Conference Machine Learning, pp. 7066-7075. PMLR, 2020.
Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. 1985.
Flavien Prost, Hai Qian, Qiuwen Chen, Ed H Chi, Jilin Chen, and Alex Beutel. Toward better trade-off between performance and fairness with kernel-based distribution matching, arXiv preprint arXiv:19I0.1 11779, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference Learning Representations, 2015.
Mengkai Song, Zhibo Wang. Zhifei Zhang, Yang Song, Qian Wang, Ju Ren, and Hairong Qi. Analyzing user-level privacy attack against federated learning. IEEE Journal on Selected Areas in Communications, 2831042440-2244, 2020. doi: 10. A.110/SAA..222203000377.
Latanya Sweeney. Discrimination in online ad delivery. arXiv preprint
2013.
Cuong Tran, My Dinh, and Ferdinando Fioretto. Differentially private empirical risk minimization under the fairness lens. Advances in Neural Information Processing Systems, 34:27555-27565, 2021a.
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9932-9939, 2021b.
Cuong Tran, Ferdinando Fiorctto, Pascal Van Hentenryck, and Zhiyan Yao. Decision making with differential privacy under faimness lens. IJCAL, pp. 560-566, 2021c.
Cuong Tran, Keyu Zhu, Ferdinando Fioretto, and Pascal Van Hentenryck. Sf-pate: Scalable, fair, and private aggregation of teacher ensembles. arXiv preprint 55X: 2022.
12

---

Published as a conference paper at ICLR 2023
Michael Veale and Reuben Binns. Fairer machine learning in the real world: Mitigating discrimination without collecting sensitive data. Big Data & Society, 422:2003991177745550, 2017.
Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy-preserving stochastic nonconvex optimization. arXiv preprint 1910. 2019.
Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. arXiv preprint arXi:
2017.
Depeng Xu, Shuhan Yuan, and Xintao Wu. Achieving differential privacy and fairness in logistic regression. In Companion proceedings of The 2019 world wide web conference, pp. 594-599, 2019.
Zhenhuan Yang. Shu Hu, Yunwen Lei, Kush R Varshney, Siwei Lyu, and Yiming Ying. Differentially private sgda for minimax problems, arXiv preprint arXiv:2201.09046. 2022.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Faimess constraints: Mechanisms for fair classification. Artificial Intelligence and Statistics, pp. 962-970.
PMLR, 2017.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335- 340, 2018.
Liang Zhang, Kiran Koshy Thekumparampil. Sewoong Oh, and Niao He. Bring your al- gorithm for optimal differentially private stochastic minimax optimization. arXiv preprint 201::22006.00363, 2022.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/regrssoon by conditional adversarial autoencoder. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5810-5818, 2017.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
A ADDITIONAL DISCUSSION OF RELATED WORK
The study of differentially private fair learning algorithms initiated by Jagielski al. (2019). Jagielski et al. (2019) considered equalized odds and proposed two DP algorithms: 1) an e-DP post-processing approach derived from Hardt et al. (2016a); and 2) an (e. ().P) in-processing approach based on Agarwal et al. (2018). The major drawback of their post-processing approach the unrealistic requirement that the algorithm have access to the sensitive attributes test time, which Jagielski et al. (2019) admits "isn' 't feasible (or legal) in certain applications." Additionally, post-processing approaches are known to suffer from inferior fairness- -cceuacy tradeoffs compared with in-processing methods. While the in in-processing method of Jagielski et al. (2019) does not require access to sensitive attributes at test time, comes with a different set of disadvantages: I) it is limited to binary classification; 2) its theoretical performance guarantees require the use of the computationally inefficient (i.e. exponential-tinge
exponential mechanism (McSherry & Talwar, 2007); 3) its theoretical performance guarantees require computations on the full training set and do nol permil mini-batch implementations; 4) it requires the hypothesis class H to have finite VC dimension. In this work, we propose the first algorithm that overcomes all of these pitfalls: our algorithm is amenable to multi-way classification with multiple sensitive attributes, computationally efficient, and comes with convergence guarantees that hold even when samples are used in each iteration of training, and even when VC(H) = oc. Furthermore, our framework is flexible enough to accommodate many notions of group fairness besides equalized odds (e.g. demographic parity, accuracy parity).
of m < n
Following Jagielski al. (2019), several works have proposed other DP fair learning algorithms. None of these works have managed to sinultaneously address all the shortcomings of the method of Jagielski et al. (2019). The work of Xu al. (2019) proposed DP and fair binary logistic regression, but did not provide any theoretical convergenceperformance guarantees. The work of Mozannar et al. (2020) combined aspects of both Hardt et al. (2016a) and Agarwal et al. (2018) in a two-step locally differentially private fairness algorithm. Their approach is limited to binary classification. Moreover, their algorithm requires n/22 samples in each iteration (of their in- po-processing step), making it impractical for large-scale problems. More recently, Tran et al. (2021b) devised another DP in-processing method based on lagrange duality, which covers non-binary classification problems. In a subsequent work, Tran et al. (2021a) studied the effect of DP on accuracy parity in ERM, and proposed using regularizer to promote fairness. Finally, Tran et al. (2022) provided a semi- supervised fair "Private Aggregation of Teacher Ensembles" framework. shortcoming of each of these three most recent works is their lack of theoretical convergence or accuracy guarantees. In another vein, some works have observed the disparate impact of privacy constraints on demographic subgroups (Bagdasaryan et al., 2019; Tran et al., 2021c).
B EQUALIZED ODDS VERSION OF ERMI
If equalized odds (Hardt et al., 2016b) is the desired faimess notion, then one should use the following variation of ERMI as a regularizer Lowy et al. (2022a):
iv SYS S(V)
DR(P; = E
(p DSs (S|Y)
1 Σ (l))ss fy()) 1.
Py (i
(5)
Here p9,slY denotes the empirical joint distribution of the predictions and sensitive attributes (f,
conditional on the true labels Y. In particular, if D S) = O, then y and S are conditionally independent given Y (i.e. equalized odds is satisfied).
S|Y)
14

---

Published as a conference paper at ICLR 2023
C COMPLETE VERSION OF THEOREM 3.2
Let (a;;;) 10, 13/ and 10 & be the one-hot encodings of (zz, 0) and respec- tively: i.e. 8,(2; 0) = (0(x1,0)=5) and Si,r = 1 [x,rr) for j 14,r E [k]. Also, denote P. diag(ps ....,
D.................. fs(k)), where (r(r) 1 -==11 (.:-))))) p 0 is the empirical prob- ability of attribute r (r [k]). Then we have the following re-formulation of (FERMI obj.) min-max problem:
Theorem C.I (Lowy al. (2022a)). (FERMI obj.) is equivalent
(f 2(0) x Σ 50
min max WER
(6)
where
(. W) = Tr(WE[S(a;, 0)5 0) 1>/x>:/W'
+ +2T- (2g | s; 1. 1/2) -1,
(x;; 0)5 (ara; 0)² [1cs] diag(Fi 0).................... .....
Fi (m;, 0)), and (By 0)s L.,, s.] is a x matrix
with (x, 0)s? [2,, silnd = 5 0).
Strong concavity bū shown in Lowy et al. (2022a).
D DP-FERMI ALGORITHM: PRIVACY
We begin with a routine calculation of the derivatives of V. which follows by elementary matrix calculus:
Lemma
D.1.
Let (),0WW W)
= Tr(WE (x) (zi, (x.") +
2 TT 0)s [2,, P
I, where (1,; 10
diag (2, O)..................... ............ Fi(x;;00 0)) and EMy [ is K matrix with B[y (mn; 0)s} [i, 8:jry Fi (x,, 0). Then,
(0 W) = Vo veo(E 018(,, [,),,) veo(WTT) + 2V, (e 10 82]) vee WT (Ps) -1/2
and
Ww 2WV () (I,, ()),,)), |,; 2p5 1/2 2/-1/2 (1,,,,,,,,
Using Theorem D.I, we prove that Algorithm is DP:
Theorem D.2 (Re-statement of Theorem 3.3). Let & 2 2n1/6)), E (0.1), and T > n ve
2m
Assume F(,,z) is Li-Liccchitz for all x, and 1(Wrr.l & D for all t e [T,r r [K].] e M.. Then, for o² > 16TIn(1/6) and oî > 16L3D" In(1/8TT Algorithm is (e, 6)DP with respect to the 2=a'p
cnnpp
sensitive attributes for all data sets containing at least p-fraction of minority attributes. Further, 32T 1n1/8))
(1 D2) and oă 6
1a(1888 ln(1/8yT "2D'L then Algorithm is c²n²
o
c"n²"
c'a'p
(c, 8) (with respect to all features) for all data containing least p-fraction of minority attributes.
Proof. First consider the case in which only the sensitive attributes are private. By the moments accountant Theorem in Abadi al. (2016), it suffices to bound the sensitivity of the gradient dD'L. and A & m²p" Here
updates by A3 & m=p
2
A
sup
Σ
- -
W,W
17
BEB.
15

---

Published as a conference paper at ICLR 2023
and Z Z' means that Z and Z' are two data sets (both with p-fraction of minority attributes) that differ in exactly one person's ' sensitive attributes: i.c. S; * 5/ for some unique E [ni] but 2j = 2/ for all j * and (I;, Ui) = (z', 1/.). Likewise,
Σ de Bi.
V b(0, vn Ww;
sup Z~ O,W
Now, by Theorem D.I.
Voùi(0, Ve vec rec(E[f((,, 0)5 1>;1=;1) (x,1)) vec(W?
+ v vec(Eils zz, 0) [ 8:l) vec W Ps
1/2
and notice that only the second term depends on S. Therefore, we can bound the &g fz-sensitivity of the 0 8-gradient updates by:
m 2 o vec (B(: 120, 86]) vec W
-1/2
A
(Ps)
sup Z W.O
2
2V, vec (ec(B 0)" (0,,, 8(I) vec (WT (Ps))
-1/2
sup m x W.O
(0,
8i,r
(
Ps(rr)
v PPs((r)
(eF)
sup
pm3 2,W
8D
pm²
using Lipschitz continuity of F(..2), the assumption that W has diameter bounded by D. the assumption that the data sets have at least p-fraction of sensitive attribute r for all r e [k]. Similarly, for the W -raddiients, we have
V W) =
+ 2p' 1/2 (1,,)(E,,)))
by Theorem D.I. Hence
A sup s m²
4
P35 E(s: 0z)² las,
Wdiag(FF (F0), F((0,x))) - P-1/2B|s' (isss,,,(aa (x;; 0.) p00, s{]
4
sup Σ xz Σ
8i.r
$
m a.W.s.
(Ps(r)
Pr)
8
m2p'
since Σ (6, < F(0,0.) = 1. This establishes the desired privacy guarantee with respect to sensitive attributes for Algorithm 1.
Now consider the case which all features are private. We aim to bound the sensitivities of the gradient updates to changes in a single sample x; (si, Tie M.). Denote these new sensitivities by
Å
Σ Be
VoL(O, Wo
sup W.W
m
16

---

Published as a conference paper at ICLR 2023
where write Z Z' mean that Z and Z' are two data sets (both with p-fraction of minority attributes) that differ in exactly one person's 's (sensitive and senssiisstiee data: i.e. 2, # 2f for some unique E [n]]. Likewise.
Áw
Σ Br
V (w (; 10 W:
sup Z-2100 W,W
Then
V vec(E[S(e,, ())((( 1x:3)))) vec(W" W) + 2Vo vec(Bls. 1)=,0 sx,,
sup s,, S,W.SS
WT (Ps) 1/2
+ Ve voc 0)5 "0 vec(W"')
vec
vec(EE/s/55/ ([ 1) s vee W" (Pst) 1/2) )
- -2 vee
2L.gDD
+
m
Thus, A3
<
+ 2. Therefore, by the moments accountant, the collection of all 0r updates m²
in Algorithm 1 is (e, if o L2D la(1/8)
SD*
SL3D2T (m(1/)) + 12
pc
enn
c'n
Next, we bound the sensitivity Åw of the W W-gradient updates. We have
Aw
4
(F.. + 2-112 (
0,) ( si)
sup O.W.
m²
+ Wdiia (..b
F((0,(()) P 1/2 (x)'''((( (2f: s/1
2
22 W +
sup
Wdiag((F(O..a)) F.. Fi(0,
m²
O.W.a..
16
2AW
sup
x0,
m²
0,00
j=1
16D2
$ 24
m?
Therefore, by the moments accountant, the collection of all W, updates in Algorithm is (e, 0)- if 327 (1
(2 + D²) This completes the proof.
2n2
E DP-FERMI ALGORITHM: UTILITY
To prove Theorem 3.4, we will first derive a more general result. Namely, in Appendix E. we will provide precise upper bound the stationarity gap of noisy DP stochastic gradient descent ascent (DP-SGDA).
E.1 NOISY SP-SGDA FOR NONCONVEX-STRONS STRONGLY CONCAVE MIN-MAX PROBLEMS
Consider generic (smooth) nonconvex-strone concave min-max ERM problem:
min F(0, w) 1 Σ S(0, w; 2.) #E
(7)
weW
where f(0, is ju-strongly concave for all 0, z but f(, wi z) is potentially non-convex. We
We say a differentiable function g is p-strongly concave if g(a) + (Vg(a). a' - aa - -laa a-1l= > g(a')
for all a'.
17

---

Published as a conference paper at ICLR 2023
Algorithm 2 Noisy Differentially Private Stochastic Gradient Descent-Ascent (DP-SGDA)
1: Input: data Z, 0o RRdo, wy E W, step-sizes (no, Nh), privacy noise parameters op, Ow batch size iteration number 7 > 1.
2: for = 0, 1...., 1 do
3: Draw batch of data points
{2) { 1=1
uniformly at random from Z.
4: Update 0e+1 02- 770 L T
Vol(O, wai -ue,, where ue (O (g),)) and
2i-11
W0++1 Tl [wr Th -i=1
(0r, my; 24) + mx)], where Us -N
5: end for
6: Draw Or uniformly at random from {0:}2-1.
7: Return: 0T
propose Noisy DP-SGDA" (Algorithm 2) for privately solving (7), which is a noisy DP variation of two-timescale SGDA (Lin et al., 2020). Now, we provide first theoretical convergence guarantee for DP non-convex min-max optimization:
Theorem E.1 (Privacy and Utility of Algorithm 2, Informal Version). Let E & 2l å e (0, 1). Assume: f(:; w;22 is Lo-Lipschite" and =(0,,;2) is Lw-Lipschitz for all 8, w. 2; and W c Rd
convex, compact set. Denote ((0) max F(0, w). Choose a 8T ln(1/8) (T)
oz
en
Then, Algorithm 2 is (e,5)-DP. Further, if (()))))) has Lipschitz gradients and (0) is strongly concave, then 3 T, 1lo: Tww such that
tm(18) and T en
(m
=| /dlm(118) (Vddl)
en
where d = max(do, d.w). (The expectation is solely over the algorithm.)
In our DP fair learning application, f(0. w; = f(0, (.....,)) Ui) + A W) and the strong concavity assumption on f in Theorem E.1 automatically satisfied, by Lowy et al. (2022a). The Lipschitz and smoothness assumptions on f are standard in optimization literature and are satisfied for loss our application to DP-FERMI, these assumptions
functions that are typically used in pracdtice. hold as long as the loss function l and F are Lipschitz continuous with Lipschitz gradients. Our next goal is to prove (the precise, scale-invariant version of) Theorem E.I. To that end, we require the following notation.
Notation and Assumptions: Let f Redo Rd x R. and F(O,w) = - [(0,, w; 2;) for fixed training data 7 = (21, =n)) E nn Let W c Rdd be a convex, compact set. For maxwew F(0, w). Let As ((,)) infg C (0)) Recall that function h is 8-smooth if its derivative Vh is B-Lisschitz We write & if there is an absolute constant C > such that a & Cb. Assumption E.2.
any 0 E Rdo denote (0) argmax F(0,u) w) and ((0)
f(,, wi 2) is La Lo-Lipcchiz and 3y-smo for all W, Z.
2. ((0,)22 is -w- Lipschitz, Smosth,,h, and μ-strongly concave on W for all 0 Rd 2 Z. 3. [(A, w: 2) f w; 2)ll Bowllo l'll and of w; 2) Vof(0, w/ 2)1l <
Bew w'll for all 0, 0' w',
4. W has &g diameter bounded by D 0.
5. F(f, wn (8)) 0 for all 0, where w (0) denotes the unconstrained global minimizer of F(O.)).
The first four assumptions are standard in (DP and min-max optimization. The fifth assumption means that W contains the unconstrained global minimizer w w*(0) of F(0.-) for all 6. Hence (7) is equivalent to
min max F(0, w). dER wERd
*DP-SGDA was also used in Yang et al. (2022) for convex and PL. min-max problems. We say function g T--Lipschitz [gg(o) - g(a'))l T.aaa a'll for all a'.
18

---

Published as a conference paper at ICLR 2023
This assumption is not actually necessary for our convergence result to hold, but we will need it when we apply our results to the DP fairness problem. Moreover, it simplifies the proof our convergence result. We refer to problems of the form (7) that satisfy Theorem E.2 as "(smooth) nonconvex-strong strongly concave min-max." We denote fiw #
Sw and Kow
Bew
We now provide the complete, precise version of Theorem E.I: Theorem E.3 (Privacy and Utility of Algorithm 2, Formal Version). Lefe & 2ln(1/6), de (0, 1). Grant Theorem E.2. Choose de
ST In(1/6) og
8T ln(1/8)
e*n
and T 3
n
2m
Then Algorithm is (c.8)-DP. Further, if we choose 17
16k (Bl
Bow Kuml
Tk
and
Dalen mim min T / AollAD( Bow + B Da
Bw
then
Lov/o
Dow Lews of Ke the
Lo do (n(1/5)
( /ii
Lo V dew In(1/))
E| [] & V Do (3a + Kom h Ken DinDD D2)
en
en
(m-nn)
L3
Karl 32
I.2
m
By
In particular, if 2 min
enlo
Ln NWw
Vdonwl Bow Now + t. Da]
Bow v du [ (B0 Now ) 1+8 DP)
then
[Vl((100)
( + ( (Sowy/iee Iow V thar
Kin [Do (0m + Bg D2
en
The proof of Theorem E.3 will require several technical lemmas. These technical lemmas, in turn, require some preliminary lemmas, which we present below.
We begin with refinement of Lemma 4.3 from Lin et al. (2020):
Lemma E.4. Grant Theorem E.2. Then + is 2(B So New ) smoooh with ( Vo w" (0)). and (-) -ipsccihh
Proof. The proof follows almost exactly in the proof of Lemma 4.3 of Lin et al. (2020), using Danskin's 's theorem, but we carefully track the different smoothness parameters with respect to w and 0 (and their units) obtain the more precise result.
Lemma F.5 (Lei et al. (2017)). Let {ar he(m] be arbitrary collection of vectors such that >n_ 0. Further, let S be uniformly random subset of [n]] of size m. Then,
E
a
m
|
1 (mmen))
a 2
m
n
m
m7 n
Lemma E.6 (Co-coercivity of the gradient). For any B-smooth and convex g, have VV(()) - Vg(b)) 28(g(a) - g(b) - (g(b),
for all a, b domain(g).
Having recalled the necessary preliminaries, we now provide the novel technical ingredients that we'll Il need for the proof of Theorem E.3. The next lemma quantifies the progress made in minimizing from single step of noisy stochastic gradient descent in 6 (i.e. line 4 of Algorithm 2):
Lemma F.7. For all t e [T]. the iterates of Algorithm 2 satisfy
B&(0,) & ((0-1) (7h)
2(30 Bor )na)
E V (1)-)))
1/ ( (Bo Bow ( (.F(0-1,,--11]1 + (Bo doop
4T
(mmn))
m
conditional 0,-1, W4
19

---

Published as a conference paper at ICLR 2023
Proof. Let us denote := Ei Vof(0 (-11i: u g + 24-1, so 8₂ 0 neg. First condition on the randomness due to sampling and Gaussian noise addition. By smoothness of +> (see Theorem E.4), we have
((t)) < (()-1)) Oo v + (3o + Bow n
(0:-1) mhl (=(0 ( - V (0-)), (0(0+-1)) (Bo + Bow
Kew ) 101
Taking expectation (conditional on 0,-1, w)-1),
[[+(0,]] & ((0,-1) n7l (0. 1]12 - (++0-11))
+ (3e + Sookow no [dop + Egg F( W: +
w
< 4 (0;0-1) nel V (0, )l( -no 11 - (0 (1,0-1)))
4L3 1 {m-n) + VoP
+ (3o +
doog +
m
(0)--1 nol (+ )1(
no VoF(((-1,
-- (
4L2
+ (3g Kow nā
dgo3 +
1 (men) + 22 Wy V 11 (00_1))
m
< (0 noll V (1 )11
1/0
VoF(O, 11
4L2
+ (30 + (5w 11
doog +
[man) + 22 w. (0) 2 -
(0,-)))
m
$(0--1)
-(10
110
2(33 + Bur (i)))[100 (0)()--))
+
110
+ 2(30 + Bom ( [[V(()-1)) V 10
2
4L2 {msnn)
+ (3o + Row doog
In the first inequality, we used the fact that the Gaussian noise has mean zero and is independent of (0.-1, W/-1- , Z). plus the fact that Ey (oF(O,,,, (0 In the second inequality, we used Theorem E.5 and Lipschitz continuity of f. In the third and fourth inequalities, we used Young's s inequality and Cauchy-Schward
For the particular hl prescribed in Theorem E.3, we obtain:
Lemma E.8. Grant Theorem E.2. If no 180 9ow then the iterates of Algorithm 2 satisfy (vt > 0)
4L3 5 5 (eulw=((0)) wrr2++ doop + m 3 th (00))1 + B0(0++1) & E (0.))
1l (menn) )
Proof. By Theorem E.7, we have
E4(0(+1) & (d)())
[10 (2h 2(33 + Bow
E (
2
Me
+ ( (Bo + kow E (A,) - VoF(Br, mx))l²) + (Bw doop +
4I3 1 (men)
+
2
3
5
4L3 1 [(man))
E0.())
no
(
8 T
((, VoF(Or, w2)l :opp +
m
3 E 8
5
4L3 m
B ElIw (0.) w.|1 doož
1 (m=n)
8
In the second inequality, we simply used the definition of no. In the third inequality, we used the fact that (0.) = VoF(O, w* (0.) (see Theorem E.4) together with Theorem E.2 (part 3).
Next, we describe the progress made in the w, updates:
20

---

Published as a conference paper at ICLR 2023
Lemma E.9. Grant Theorem E.2. If the
Bu then the iterates of Algorithm 2 satisfy (Vt e 0)
4T
B F|w" (0c+1) wit1l 12 &
4h Ku 10 T6 Bo Ellw0 well vrl12+
m [men) d
2kw
3%
(B)) + ddoo))
Proof. Fix any t and denote 6, := E w* (0:) wi 1 == Ell - we12 We may assume without loss of generality that ;(),:;2) is j-strongly convex and that w++1 Iww[w
B ( - [ WA; zi) vi)] = uwlw: Bo (Vh(w,) + w.]] = Iwwww B- Vh(w:)] Now,
1 vh(w:)] - -
E E 2l1+11 wº -012-
Tw
$ E
14
Vh(we) w*
3a
Bw
2
W
w01 1 + [h(ww))
+ dwo
EE'
Wr w", vh(we))
B
B
2
E Wele
w w²112= +
E Vh(w,)11
+ dw
E
F(0e, wx) F(Oe, w²) + [wo ==1
B
11
2
E E[F wt) ((Or,w*)) + Vh(w;)ll
dwo
8, 1
Br
B2.
Further,
E| B| = [[[Vh(w)) V F(Or, w;)ll + V F(,, wx)
4L3
(m-en) + E wx)ll
m
4L
(men)) m
23 2f (0., w.) F(O,, w* (((,,,""00))))) (0.))),
using independence and Theorem E.5 plus Lipschitz continuity of f in the first inequality and Theo- rem E.6 (plus Theorem E.2 part 5) in the second inequality. This implies
E W1++1 w01 2 < d: (1-
(1-1
412
o w +
1 [men)
(8)
Kiw
32
m
Therefore,
8.+1
E [14++1 (0,) + (0,))) - w (0(+0++)ll'
1 + 2fw 1
E 1 w² (0.))1 + 2n. Bllw==((BB) w² (0++1))l
2
412
1
6 +
d +
{mmen]
+ 2x 2Ni (0t)
w= (0c+
2km
KmD
32
m
2
41.2
5,
d
{m=nn)
2k 2 Bl0, 0++11
2
Kew
8
m
412
52 +
d
+
{me<n)
22
Ke
32
m
+ 4 Kig
Nigu 11
2
[ V we)
V
(0.))
2
VVb(0.)1 + doop)
4L2 w {m=cn)
6, +
d w
+
260
Km
32
m
2 + K
F wx)
- VoF
"* (02)) + (++()))) + doopp
d 2 + 4L2 1 {man)
1 + 2
6, +
K5
32
m
+ 4k Kig 11
2 2 12 Ellwss
w (0:) + [V + dooe]
21

---

Published as a conference paper at ICLR 2023
by Young's 's inequality, (8), and Theorem E.4. Since
(1+
2x
(1
Rw
1
$
Zrew
we obtain
4L2
5++1 $
1
+ 4k 11 33g
òe +
d +
(men)]
+ Akmniew
[IV)))))) doo
B
m
as desired.
We are now prepared to prove Theorem E.3.
Proof of Theorem E.3. Privacy: This is an easy consequence of Theorem Abadi et al. (2016) (with precise constants obtained from the proof therein, as in Bassily et al. (2019)) applied to both the min (descent in 0) and max (ascent w) updates. Unlike Abadi al. (2016), don't clip the gradients here before adding noise, but the Lipschitz continuity assumptions (Theorem E.2 parts I and 2) imply that the fz-sensitivity of the gradient updates in lines 4 and of Algorithm are nevertheless bounded by 2La/m /mm and 2 m, respectively. Thus, Theorem in Abadi et al. (2016) still applies.
Convergence: Denote Ç 1
22 1 + knw Npm 2k
8t Bll (0.) woll? and
2 4 B3
C ==
1 (man) + d
+ 4km 2 n (L) (+,0,)1 doog).
m
so that Theorem E.9 reads as
6, $ (6: + C
(9)
for all E [7]. Applying (9) recursively, we have
6, < g0 +
C
j-0
D² + 4Kim 110
2
(
2
4L2
1 (men) + d + Nkw dooo
Combining this inequality with Theorem E.8, we get
3
41. 1 (m-nn)
EΦ(())) & E
((0,-1)
8 nol (6.()11))
770 doop +
+ 8 n0
(²T)² +
415 1i
E V (0,))2
Σ
(1-
2
442
[m=nn) + dwo + Akmm doog
B2
Summing over all t E
[T'] and re- arranginng terms yields
Ed(0r) < (Po))
3
8 no
T
E
(0
no (doo?+ 4L3 m (men))
+
5
T
5" D²
8
4ng 2 Key Ki
V (0,))2
(=13=
+
5
Σ
T
1
32
2
4L2
1 [men) + duo ) + todo
8
1--0
22

---

Published as a conference paper at ICLR 2023
Now, 5 & 1 4xw
which implies that
T
&
4k and
1-1
1-1-)
& 4kw
Hence
T
(() (0))
dgop + 4L3 1 (men)
7 D2 Kw
E
V
(0,1)
T
T
48 Dg
2 2
Σ E V2(0.)2
T
2
4L
8k Fw
+ 32 2 11 (m-n) + d
Ki 1
32
Since 18 u rig <
256 we obtain
E ()
Kiu
T
(Bo + (om
+
de ToLTTIn(1/0)
en
+ m
1
[m=n]
I. +
Kiw 3 12
B3
+
Ke
3 1 T In(1/6)
$2. e
Pow D2
T
Our choice ' then implies
Lo dg In(1/8)
(Bow Riw
L V dew ln(1/5)
I (mmen) v $ V Ao (Bo +
: + Kew k On (2 D2)
En
B
Ke Ku L w
12
m
B2
Finally, our choice of sufficiently large m yields the last claim Theorem E.3.
E.2 PROOF OF THEOREM 3.4
Theorem 3.4 is easy consequence of Theorem E.1, which proved in the above subsection:
Theorem E.10 (Re-statement of Theorem 3.4). Assume the loss function E( 2, y) and F(x, ))
are Lipschitz continuous with Lipschitz gradient for all (x, and Ps(r) > p 0 v [k]. In Algorithm choose W to be a sufficiently large ball that contains (*( == argmaxw F(O, W) for every 0 in some neighborhood of 6* argming maxw F(0, W). Then there exist algorithmic parameters such that the (e, 6D- Algorithm I returns Or with
(
(Vmax(do, kl) In (188)
E (+E =0
treating D diameter(W), A. and the Lipschitz and smoothness parameters of and F as constants.
Proof. By Theorem 1, suffices show that 5(0, W; : =(0 x1, vi) + X W) is Lipschitz (Itz 8i), and
continuous with Lipschitz gradient in both the and W variables for any that 24) strongly concave. We assumed ((- y1) is Lipschitz continuous with Lipschitz gradient. Further, the work of Lowy et al. (2022a) showed that f(0, 2,) is strongly concave. Thus, it suffices to show that (0, W) is Lipschitz continuous with Lipschitz gradient. This clearly holds by Theorem D.I, since F(x,)) .) is Lipschitz continuous with Lipschitz gradient and W E W is bounded.
23

---

Published as a conference paper at ICLR 2023
F NUMERICAL EXPERIMENTS ADDITIONAL DETAILS AND RESULTS
F. MEASURING DEMOGRAPHIC PARITY AND EQUALIZED ODDS VIOLATION
We used the expressions given in (10) and (11) to measure the demographic parity violation and the equalized odds violation respectively. We denote y to be the set of all possible output classes and S to be the classes of the sensitive attribute. P[E] denotes the empirical probability of the occurrence of an event E.
max
Plù = 5/18 = 81] P 3/ 8 = 82]
(10)
max P[ 1/ 81,9 y/ - P 5'1s 82. = v/]l.
max y'EV,.1..9ES
(11)
PDD y'ss $1 # v1 PID 5 s= 52,3 v
F.2 TABULAR DATASETS
F.2.1 MODEL DESCRIPTION AND EXPERIMENTAL DETAILS
Demographic Parity: We split each dataset in a 3:1 trainttsst ratio. We preprocess the data similar to Hardt et al. (2016a) and use simple logistic regression model with sigmoid output O= >=o(W> x + b) which we treat as conditional probabilities p(ğ = i|z). The predicted variables and sensitive attributes are both binary in this case across all the datasets. We analyze fairness-accuracy trade-offs with four different values of e E {0.5, 1, 3, 9} for each dataset. We compare against state-of-the-ar algorithms proposed in Tran al. (2021a) and (the demographic parity objective of) Tran et al. (2021b). The tradeoff curves for DP-FERMI were generated by sweeping across different values for À [0, 2.5.. The learning rates for the descent and ascent, 7e and The- remained constant during the optimization process and were chosen from [0.005, 0.01]. Batch size was 1024. We tuned the E diameter of the projection set W and 0 f-gradient clipping threshold in [1, 5] in order to generate stable results with high privacy (i.e. low e). Each model was trained for 200 epochs. The results displayed are averages over 15 trials (random seeds) for each value of
Equalized Odds: We replicated the experimental setup described above, but we took & diameter of W and the value of gradient clipping for to be in [1,2]. Also, we only tested three values of (0.5, 1,3).
F.2.2 DESCRIPTION OF DATASETS
This dataset contains the census information about the individuals. The classification task predict whether the person earns more than 50k every year or not. We followed a preprocessing approach similar to Lowy et al. (2022a). After preprocessing, there were total of 102 input features from this dataset. The sensitive attribute for this work in this dataset was taken to be gender. This dataset consists of around 48, 28,000 entries spanning across two CSV files, which we combine and then we take the train-test split of 3:1.
Adult Income Dataset:
Retired Adult Income Dataset: The Retired Adult Income Dataset proposed by Ding et al. (2021a) essentially superset of the Adult Income Dataset which attempts counter some caveats of the Adult dataset. The input and the output attributes for this dataset is the same as that of the Adult Dataset and the sensitive attribute considered in this work the same as that of the Adult. This dataset contains around 45, ,000 entries.
In the Parkinsons dataset, we use the part of the dataset which had the UPRDS scores along with some of the features of the recordings obtained from individuals affected and not affected with the Parkinsons disease. The classification task was to predict from the features whether the UPDRS score was greater than the median score not. After preprocessing, there were total of 19 input features from this dataset and the sensitive attribute for this dataset was taken to be gender. This dataset contains around 5800 entries in total. We took train-test split of 3:1.
Parkinsons Dataset:
Credit Card Dataset: This dataset contains the financial data of users in a bank in Taiwan consisting of their gender, education level, age, marital status, previous bills, and payments. The assigned
24

---

Published as a conference paper at ICLR 2023
classification task is to predict whether the person defaults their credit card bills not, essentially making the task if the clients were credible or not. We followed a preprocessing approach similar to Lowy et al. (2022a). After preprocessing, there were total of 85 input features from this dataset. The sensitive attribute for this dataset was taken to be gender. This dataset consists of around 30,000 entries from which take the train-test split of 3:1.
This dataset a large scale image dataset containing with an age span from 0 to 116. The dataset consists of over 20,000 face images with details of age, gender, and ethnicity and covers large variation in pose, facial expression, illumination, occlusion, resolution. We consider the age classification task with 9 age groups similar the experimental setup in Tran et al. (2022). We consider the sensitive attribute to be the ethnicity which consists of 5 different classes.
UTK-Face Dataset:
F.2.3 DEMOGRAPHIC PARITY
See Fig. 6 for our results on Retired Adult Dataset. The results are qualitatively similar to the reusults reported in the main body: our algorithm (DP-FERMI) achieves the most favorable fairness-accuracy tradeoff's across all privacy levels.
Retired Adult Results:
* Tan et (2021b)
0.200
* Tran et (2321a)
et (23218)
Tan et al. (2021a)
Demograshic Farby Vilation
0.20
Parny Velthon
0.1/5
hon-Privece FEAMI
Non-Frivate IERMI
Private Fair
0.150
Privato Non
0.15
0.00
0.10
0.050
0.025
0.00
0:18
0.20
0.17
0.19
Misciossllkation
Misdlssificatio
(a) 0.5
(b) ==1
0.200
Tan (2021h) Tan et al, (2021a) DR-FERMI
0.200
(2.30 Tran et (2321a)
Demographc Ps Try Velsdon
0.175
Demographic my Wolsoo
0.175
DP-FERMI
Non-Private FERMI
Non-Private FERMI Non Privote Non Fair ERM
0.150
hon Private Non Foir ERM
0.150
0,125
0.125
0.200
0.100
0.075
0.050
0.025
0.66
a17
0.88
0.19
0.20
0.11
0.22
0.66
0.17
0.18
0.22 (d) c 9
0.19
0.20
021
Misclasification Enror
Misdasstiictton Enror
(C) c
Figure 6: Private, fair logistic regression on the Retired Adult Dataset
Credit Card Results: See Fig. 7 for our results on Credit Card Dataset. DP-FERMI offers superior fairess-accuurccy-rivve profile compared to all applicable baselines.
Additional Results for Parkinsons Dataset: More results for Parkinsons are shown Fig. DP-FERMI offers the best performance.
F.2.4 EQUALIZED ODDS
Equalized Odds Variation of DP-FERMI Algorithm: The (FERMI obj.) minimizes the Expo- nential Renyi Mutual Information (ERMI) between the output and the sensitive attributes which
25

---

Published as a conference paper at ICLR 2023
* Tan et al. (2021b)
Tran al (2321b)
(233.aa)
0.0200
FERMI
00200
DR FERMI
0.0175
Privace FERMI
00175
Moon-Privte FLRMI
Pricate
Private
0.0150
00150
0.0125
0,0125
3,0100
0.0075
0.0055
Miclassilicaioon
Micclasification
0.5
(b) 6
0.0225
*
Tann et (2021b)
0.0225
* Tran (2321b) Tran at (2321a)
Tan et al. (2021a)
00200
0.0175
Non Privace FERMI
Non Privat TERMI
Private
Private Fair
0.0150
0.030
0.0125
3,0100
0.100
0.0755
0.0050
00050
0.130
3192
0.294
0.196
0.195
0,203
0.90
0.192
0.194
0.196
0.190
Misclasslkaation
Misdlasiiication
(c)
(d) 9
Figure 7: Private, fair (demographic parity) logistic regression on the Credit Card Dataset
0.08
(2021b)
(2321b)
(2021a)
(2321a)
Damegraphc Punty Volaben
0.07
De FERMI
Damcgraphi aphic Parky Vilatin
0.08
DR FERMI
0.06
Non Privaze kon Private Non Fair FRM
Non Private Non Fair FRM
0.04
0.03
0.03
0.02
0.02
6.01
0.01
0.04
0.36
0.08
0.10
0.22
0.04
0.08
0.08
0.10
0.12
Misclasotication Erior
Mislassiiiation Erio
(a)
(b)
Figure 8: Private, Fair (Demogrpahic Parity) Logistic regression Parkinsons Dataset
essentially leads to a reduced demographic parity violation. The equalized-odds condition is more constrained and enforces the demographic parity condition for data grouped according to labels. For the equalized-odds, the ERMI between the predicted and the sensitive attributes minimized conditional each of the label present in the output variable of the dataset. So, the FERMI regularizer split into as many parts as the number of labels in the output. This enforces each part of the FERMI regularizer to minimize the ERMI while output label is given/constant. Each part has its unique W that is maximized order to create a stochastic estimator for the ERMI with respect to each of the output labels.
26

---

Published as a conference paper at ICLR 2023
Adult Results: Results for the equalized odds version of DP- FERM Adult dataset are shown in Fig. 9. Our approach outperforms the previous state-of-the-an methods.
0.25
The eral paviN
The enal D121gg
Yhu on DIIIN Piy modkiee (PBNN)
pipesss pons)
0.20
0.0
0.55
hrvate
0.35
hrivss
0:15
hhhme for
0.22
0.0
0.2
378
0.20
638
4.6
0.20
022
3.26
0.5
(b)
Figure 9: Results obtained for applying DP-FERMI with equalized odds violation on logistic regression on the Adult Dataset
Retired Adult Results: (Initial) Results for the equalized odds version of DP-FERMI the retired- adult dataset are shown in Fig. 10. Our approach outperforms Tran et al. (2021b) and we are currently tuning our non-private and/or non-fair versions of our models along with Jagielski et al. (2019).
0250
2305
Taric& 1001M
03/9
41 2113X
4t (212)
0289
2
2153
0315
0150
301
652
007
511
318
218
3.1
023
031
032
311
020
021
5.2
(a) 6 0.5
(b) c
(c) 6
Figure 10: Results obtained for applying DP-FERMI with equalized odds violation on logistic regression on the Retired Adult Dataset
F.3 IMAGE DATASET (UTK-FACE)
We split the dataset in 3:1 train:test ratio. Batch size was 64. 128 x 128 normalized images were used as input for our model. We tuned the le diameter of W and the value gradient clipping for 0 to be in [1,2] and learning rates for the descent and ascent, 7h and The remained constant during the optimization process and were chosen as 0.001 and 0.005 respectively. We analyze the {10, 25, 50, 100, 200). The results
fairness-accuracy trade-offs with five different values of displayed were averaged over observations obtained from 5 different randomly chosen seeds on each configuration of and dataset. Each model trained for 150 epochs. The tradeoff curves for this set of experiments were obtained by sweeping across different values for À E [0, 0050.
27

---

Published as a conference paper at ICLR 2023
G SOCIETAL IMPACTS
In this paper, we considered the socially consequential problem of privately learning fair models from sensitive data. Motivated by the lack of scalable private fair learning methods in the literature, developed the first differentially private (DP) fair learning algorithm that is guaranteed to converge with small batches (stochastic optimization). We hope that our method will be used help companies, governments, and other organizations to responsibly use sensitive, private data. Specifically, we hope that our DP-FERMI algorithm will be useful in reducing discrimination in algorithmic decision- making while simultaneously preventing leakage of sensitive user data. The stochastic nature of our algorithm might especially appealing to companies that are using very large models and datasets. On the other hand, there are also some important limitations of our method that need to be considered before deployment.
One caveat of our work is that we have assumed that the given data set contains fair and accurate labels. For example, gender is the sensitive attribute and "likelihood of repaying loan" is the target, then assume that the training data accurately describes everyone's 's financial history without discrimination. If training data is biased against a certain demographic group, then is possible that algorithm could amplify (rather than mitigate) unfairness. See e.g. Kilbertus et al. (2020); Bechavod et al. (2019) for further discussion.
Another important practical consideration how weigh/value the different desiderata (privacy, fairness, and accuracy) when deploying our method. As shown in prior works (e.g.. Cummings al. (2019)) and re-enforced in the present work, there are fundamental tradeoff's between fairness, accuracy, and privacy: improvements in one generally come at cost to the other two. Determining the relative importance of each of these three desiderata is critical question that lacks clear or general answer. Depending on the application, one might be seriously concerned with either discrimination or privacy attacks, and should calibrate e and À accordingly. Or, perhaps very high accuracy is necessary for a particular task, with privacy and/or fairness case, one might want to start with very large and small to ensure high accuracy, and then gradually shrink and/or increase À improve privacy/faimess until training accuracy dips below critical threshold. thorough and rigorous exploration of these issues could be an interesting direction for future work.
afterthought. In such
28


Reviews:
[{"review_id": "tX3PKJG-ylc", "reviewer": "Reviewer_yWF7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies how to learn models that satisfy various fairness desiderata (e.g., demographic parity and equalized odds) while satisfying differential privacy. Like prior work, it writes down a loss function encoding some weighted combination of accuracy and fairness constraints and aims to develop a private method for optimizing it. The proposed \"DP-FERMI\" solution does so using DP-SGD. The claimed novelty lies in its convergence analysis, which appears to be the first of its kind for DP-SGD applied to a fairness-constrained loss. The key technical step relies on the \"exponential Renyi mutual information\" loss developed by (Lowy+ 2021) and used in that paper to derive a similar convergence result for stochastic/mini-batch (non-DP) SGD. While other papers have studied similar DP-SGD-based approaches to optimizing a fairness-constrained loss, those works did not attempt to theoretically analyze convergence. This paper concludes with some experiments demonstrating that DP-FERMI obtains better empirical tradeoffs between fairness and accuracy loss at the same privacy levels as existing baselines.", "summary_of_the_review": "Overall, I think the current submission has some promising ideas and results that are hindered by an unclear explanation of technical or conceptual novelty and a sparse empirical evaluation on meaningful notions of fairness. As a result, my current recommendation is weak reject. However, I think a modified version of this paper, perhaps implementing the suggestions above, could be acceptable at ICLR or a similar venue, especially since the DP fairness literature has (IMO) still not featured much compelling work.\n\nEDIT: After reading the author responses and discussing with some of the other reviewers, I've increased my score to a weak accept. Other reviewers have expressed stronger misgivings about 1) the assumptions required to set the parameters to satisfy the utility guarantee, 2) the difference between the \"random iterate\" version analyzed and the \"final iterate\" version implemented, and 3) the division between sensitive and non-sensitive attributes. IMO, these aren't serious problems, but after discussing with the other reviewers, I'm not planning to champion this paper further. I suggest that the authors attempt to address these issues and re-submit a modified version of this paper.", "strength_and_weaknesses": "Strengths: The DP-FERMI formulation seems like a neat idea for getting to a convergence analysis. The paper is generally easy to follow (though there is a sudden drop-off in clarity when explaining technical bits, see below). The empirical performance looks like a nontrivial improvement over existing baselines.\n\nWeaknesses: The application of FERMI is not obviously a large improvement over its introduction in (Lowy+ 2021): we want to optimize a weird fairness-constrained loss, so we instead optimize an upper bound on it, which admits a stochastic convergence analysis, and also handles non-binary classification. The added contribution here is, in the paper's phrasing, \"a careful analysis of how the Gaussian noises [necessary for DP-SGD] propagate through the optimization trajectories\". I don't have much feel for what constitutes an \"interesting\" convergence analysis, but the conceptual novelty here is unclear, and the introduction is a bit slippery about what is novel and what is borrowed from the FERMI paper.\n\nThe paper also struggles to explain its technical contributions in terms between a very high level summary and a long, opaque theorem statement. I suggest changing the focus of the paper to 1) reduce, relegate to the appendix, or eliminate the discussion of demographic parity (an extremely coarse notion of fairness that, IMO, the fairness literature needs to move past, and has only been discussed this long because it's very simple), which takes up over a page of the main body without meaningfully adding to the story told by the equalized odds results alone, 2) extending the discussion of how Theorem 3.1 works and what it accomplishes (the current statement is a blizzard of notation with little explanation -- I still don't know what W is doing), along with Theorem 3.2, and 3) extending the equalized odds results to more datasets (why are Parkinsons and Retired Adult results only reported for demographic parity? it seems like equalized odds should also apply here, and an empirical story built on 2 datasets seems thin). I think 2) would help provide a clearer explanation of the paper's improvement over (Lowy+ 2021) and 3) would make a stronger empirical case separate from the convergence analysis.\n\nOther questions/comments:\n1) I'd appreciate a table in the appendix attempting to concisely explain all of the relevant variables -- by my count, Theorem B.1 has well over a dozen.\n2) Why is Tran 2021b a single point where the other methods have curves? More generally, perhaps I missed the explanation of this in the text, but what is varied to generate the curves?\n3) As far as I can tell, the paper does not discuss the tightness of the upper bound offered by ERMI, nor does it explicitly write out the expression for equalized odds. This makes it hard to contextualize the convergence guarantee in terms of the underlying loss we actually want to optimize.\n4) Figure 4 \"priavte\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ntV2_ZzKHT4", "reviewer": "Reviewer_bxYf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "An SGD-style algorithm is proposed for fair, private learning, with provable convergence even on non-convex loss.", "summary_of_the_review": "The described algorithm has the practical weaknesses I mentioned above. Unless I am mistaken, it seems unlikely that this method would be useful in practice. But as far as I know the technical contribution is novel and could be a useful stepping stone toward a more practical algorithm with the strengths of the proposed approach.", "strength_and_weaknesses": "Strength: It is maybe of theoretical interest that SGD-style algorithm is proposed for fair, private learning, with provable convergence even on non-convex loss.\nWeaknesses:\n1) The input of each training example is partitioned into sensitive features s and nonsensitive features x. The algorithm is private and fair with respect to s, while the trained classifier only uses x as input. It is not clear to me why one would want to partition features in this way. If I'm training a language model on text input I want my credit card number to be private, but I'm not worried about fairness with respect to credit card numbers. Conversely, I want my face recognition system to be fair with respect to skin tone, but I don't necessarily need that to be kept private. Finally, in principle it seems like it should be possible to use sensitive features as model input while retaining privacy and/or fairness.\n2) The final model parameters are chosen by drawing uniformly at random from all intermediate models during training. Won't that often destroy model utility, if an early iterate is chosen?\n3) The experimental results are not impressive. Other than Figure 3a, the results are not significantly stronger than the Tran et al. (2021b) baseline, although they do allow an interpolation between fairness and model utility. I would like to see non-private and/or non-fair baselines. How much model utility are we losing due to weakness #2 above?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YEmcsFEfTx", "reviewer": "Reviewer_oW3z", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a differentially private and fair learning algorithm, satisfying two common group fairness notions: demographic parity and equalized odds. The proposed algorithm relies on augmenting the standard empirical risk loss component with an exponential Renyi mutual information term between the protected group feature and the label. The latter term requires fine-tuning to fit the specific fairness notion adopted. \nThe claimed benefit of the proposed procedure, which relies on approximating the resolution of a min-max problem through a classic stochastic gradient method, is its convergence property even when this optimization procedure operates over mini-batches.\n", "summary_of_the_review": "The paper develops a technique for an important much-needed problem: guaranteeing both privacy and fairness while providing convergence guarantees. \nSome of the contributions of the work are however overstated and some clarity over the experimental setting adopted is needed. \n", "strength_and_weaknesses": "*Settings and contributions*:\n\nThe paper tackles an interesting and significant problem. I believe this one posed is a highly relevant question and am happy the authors studied this problem. \n\nI have also, however, found the claimed contributions to be a bit overstated: It is nice that the proposed method allows to handle non-binary sensitive attributes and that multiple fairness definitions, but this is also what is currently assumed in the recent literature, including in some of the work against this paper compare. \n\nI also believe that the claimed guarantees are overstated. From the abstract all the way to section 3 the paper claims that this proposal allows convergence for any fairness level even when mini-batches of data are used in each iteration of training. \nThis is, however, misleading. In section 3 and Theorem 3.1, in fact, after learning the assumptions adopted, I am left with the impression that claimed results are much less general than what is implied in the abstract and introduction: The restrictions taken on the loss function (strongly concave in the parameter space, global L-Lipschitz property in both the parameter of the primal and the dual space and convexity of the {\\cal W} set.).\n\nThe claimed mechanism properties thus, need to be tuned down substantially in the eyes of this reviewer. \nI encourage the authors to be very clear from the abstract on which assumptions the claimed properties are satisfied. \n\nNotice that, related to this overstatement, the last sentence before section 4 \"no existing work with convergence guarantees are able to handle non-binary classification\" is misleading. I don't think it does good to our community. \n\n*Experiments*:\n\nI really like the way the authors have displayed the experiments. They show a good Pareto boundary and can clearly see the superiority of the proposed method w.r.t. Tran et al.\n\nHowever, I also need to point out that there is no need to \"adapt\" Tran et al algorithms to non-binary cases, as their paper clearly reports experiments on non-binary cases too. I also found the statement about the instability of these methods to be possibly unjustified. Has a hyperparameter tuning over these methods been performed? Or did the authors use the hyperparameters adopted by Tran et al in their paper? If the latter is true, note that the datasets and architectures adopted for the experiments in this paper differ from what was used by Tran et al. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NE8RR8nZf", "reviewer": "Reviewer_8e2X", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a fair learning algorithm with DP guarantees. The algorithm owns a provable “convergence” guarantee and can deal with multi-class, multi-sensitive attributes classification tasks.", "summary_of_the_review": "Interesting paper but many concerns need to be addressed", "strength_and_weaknesses": "The problem studied in this paper (i.e., fair learning algorithm with DP guarantees) is important and significant. Overall, this paper is easy to follow. The new algorithms introduced in this paper look interesting. \n\n\nMy main concerns are listed below:\n\n**Privacy mechanism**: it is unclear to me why the DP is defined only in terms of the sensitive attribute S. This may be vulnerable: when S is correlated with the rest of the features, an adversary can potentially reconstruct it from the rest of the features. \n\n**Convergence guarantee**: The convergence guarantee (e.g., Theorem 3.2) is different from the typical convergence results. First, it only guarantees the existence of T (number of iterations), eta_theta, and eta_w (step size) such that the results hold. Hence, it is very likely that the (T, eta_theta, eta_w) a data scientist chooses does not have any convergence guarantee. Second, it is unclear to me why the result is only derived for the gradient of Phi. This is not even the gradient used for updating the parameters. Ideally, the convergence results should tell us the convergence of theta and w. Finally, the authors did not provide any convergence rate so it is unclear how the algorithm converges w.r.t. the number of iterations. \n\n**Estimation error** it seems that the algorithm introduced by the author depends on estimating the joint distribution of \\hat{Y} and S. It is unclear to me how the estimation error influences the performance of the algorithm. In particular, since fairness is defined through chi-square divergence and the accuracy of estimating chi-square divergence relies on the support set, I am a bit worried about how the estimation error propagates to the learning algorithm. This problem is important because this paper considers the setting of multi-class, multi-sensitive attributes (I assume this is one main contribution of this paper). Hence, the support of \\hat{Y} and S can be very large. \n\n**Misleading statement** the authors wrote “if sex is the sensitive attribute and a data set contains all men, then any classifier is trivially fair with respect to sex, so fairness with respect to sex is meaningless for that data set.” I find this sentence very misleading! The authors should revise this statement.\n\n**Novelty** It seems that many results in this paper rely on prior work [Lowy et al., 2021]. \n\nOther comments:\n\nThe authors may consider discussing what group fairness measures can be covered in this paper. For example, can the learning algorithm cover false discovery rate and calibration error?\n\nMinor comment: D_R(\\hat{Y}, S) is chi-square information. Calling it Renyi mutual information may not be accurate\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster