f-FERM: A  Scalable Framework for  Robust Fair Empirical Risk Minimization
Authors: Sina Baharlouei
Shivam Patel
Meisam Razaviyayn
Venue: ICLR 2024 poster (2024)
Keywords: Algorithmic Fairness
Distributionally Robust Optimization
Distribution Shift
Fairness
f-divergences
Primary area: societal considerations including fairness, safety, privacy

Abstract: Training and deploying machine learning models that meet fairness criteria for protected groups are fundamental in modern artificial intelligence. 
While numerous constraints and regularization terms have been proposed in the literature to promote fairness in machine learning tasks, most of these approaches are not amenable to stochastic optimization due to the complex and nonlinear structure of constraints and regularizers. Here, the term ``stochastic'' refers to the ability of the algorithm to work with small mini-batches of data. Motivated by the limitation of existing literature, this paper presents a unified stochastic optimization framework for fair empirical risk minimization based on $f$-divergence measures ($f$-FERM). The proposed stochastic algorithm enjoys theoretical convergence guarantees. In addition, our experiments demonstrate the superiority of fairness-accuracy tradeoffs offered by $f$-FERM for almost all batch sizes (ranging from full-batch to batch size of one). Moreover, we show that our framework can be extended to the case where there is a distribution shift from training to the test data. 
Our extension is based on a distributionally robust optimization reformulation of $f$-FERM objective under $\ell_p$ norms as uncertainty sets. Again, in this distributionally robust setting, $f$-FERM not only enjoys theoretical convergence guarantees but also outperforms other baselines in the literature in the tasks involving distribution shifts. 
 An efficient stochastic implementation of $f$-FERM is publicly available.

Published as a conference paper at ICLR 2024
f F-FERM: A SCALABLE FRAMEWORK FOR ROBUST FAIR EMPIRICAL RISK MINIMIZATION
Sina Baharlouei
Shivam Patel f
Meisam Razaviyayn
ABSTRACT
Training and deploying machine learning models that meet fairness criteria for protected groups are fundamental in modern artificial intelligence. While numerous constraints and regularization terms have been proposed in the literature to promote fairess in machine learning tasks, most of these approaches not amenable stochastic optimization due to the complex and nonlinear structure of constraints and regularizers. Here, the term "stochastic" refers to the ability of the algorithm to work with small mini-batches of data. Motivated by the limitation of existing literature, this paper presents a unified stochastic optimization framework for fair empirical risk minimization based on f-divergence measures (f-FERM). The pro- posed stochastic algorithm enjoys thcoretical convergence guarantees. In addition, our experiments demonstrate the superiority of fairness- accuracy tradeoffs offered by f-FERM for almost all batch sizes (ranging from full-batch to batch size of one). Moreover, we show that our framework can be extended to the case where there is a distribution shift from training to the test data. Our extension is based on distributionally robust optimization reformulation of f-FERM objective under lp norms as uncertainty sets. Again, in this distributionally robust setting, f-FERM not only enjoys theoretical convergence guarantees but also outperforms other baselines in the literature in the tasks involving distribution shifts. An efficient stochastic implementation of f-FERM is publicly available
INTRODUCTION
Machine learning models are increasingly deployed in critical applications ranging from health- care (Ahmad et al. 2018) to image processing (Krizhevsky et al. (017)) education to job recruit- ment (Boselli et al. 2018), and social networking to cybersecurity (Xin et al.. 2018). Machine learning practitioners have adopted learning algorithms to fathom inherently difficult and crucial problems. However, naive deployment of these models may lead to serious shortcomings such as biased predictions against minority groups (Angwin et al. 2016 [Buolamwini & Gebru 2018). vulnerability to adversarial attacks (Madry et al. 2017 20177/1Crr [Crllnni & Wagner 2017 Baharlouei et al.. 2023), or lack of generalizability (Arjovsky et al. (019). Consequently, it is of utmost importance to have reliable and trustworthy models that are, in particular, fair and comply with equality norms and
provisions worldwide (Act. 1964 Elford 2023).
With the increasing concern for the trustworthiness of unchecked machine learning algorithms, a broad class of paradigms has been proposed to counteract and mitigate both the cause and effects of model unreliability. Imposing statistical independence between model output and particular input features is of interest in various domains, especially when the generalization of trained model is based on collection of spurious features present in the training dataset (Dwork et al.. 2012 Hardt et al. 2016 Yan et al.) 2017). These could be sensitive features like gender, race, age, and/or income in the context of fairness or confounding factors like environmental artifacts in the context of image classification (Arjovsky et al.) 2019). Existing literature on imposing statistical independence between selected input features and model outputs is directed into three approaches: pre-processing. post-processing. and in processssnn methods.
Pre- pre-processing methods entail upstream changes made in datasets to mask sensitive features or reduce the dependency of output variables on sensitive features through transforming data a stage before the training phase (Kamiran & Calders] 2012 Zemel et al. 2013 Ustun et al. 2019). Post- processinn methods involve -peee--ppecffi adjustments to the model 's output to ensure the independence of
* "University of Southern California (babarlou, razaviya@usc. edu) Department of Electrical Engincering, IIT Bombay vahiaatee 2002 20mma com)

---

Published as a conference paper at ICLR 2024
predictions and sensitive attributes (Hardt et al. 2016 Alghamdi et al., 2022) While pre- processing and post- post-procsssing methods do not affect the training procedure, they fail to exploit underlying training mechanisms for the best achievable accuracy-faimess tradeoffs. Unsurprisingly enough, optimizing accuracy and fairness jointly (in-processing) leads to better tradeoffs than sequentially optimizing fairness and accuracy in pre-processing or post-processing fashion.
In in-processing methods alternatively add fairness constraints or regularizers, penalizing dependence between sensitive attributes and output variables. (Zafar et al. 2017) utilizes covariance as the measure of independence between the sensitive attributes and the predictions. While such a measure amenable to stochastic updates, it fails to capture correlations beyond linear. Alternatively, several non-linear measures such as Rényi correlation (Baharlouei et al. 2020), x² divergence (Lowy et al. 2022), To distance (Donini et al. 2018), and Maximum Mean Discrepancy (MMD) (Prost et al. 2019) are proposed in the literature to establish the independence of the predictors and sensitive
attributes. In-processing techniques can be model-specific (Wan et al. A et al. 2019) or
generalizable to different training algorithms (Baharlouei et al. 2020
Lowy et al. 2022
In the spirit of in-processing methods, input data-driven constraints or regularization terms are used to modify training objectives of problems like learning generalizable models to new environments, invariant learning, and learning in the presence of distribution shifts (Arjovsky et al., 2019 Mary
et al. 2019 Bahaalouui et al. 2020). Such constrainned/regulatized reformulations
prevalent in learning robust classifiers against adversarial attacks (Sinha et al.] 2018), meta-learning (Balaji et al.
2018), federated learning (Deng et al. (2023), and alternative learning paradigms such learning
distributionally robust optimization (DRO) models (Kuhn et al. 2019 Levy et al. 2020). tilted
empirical risk minimization (TERM) (Li el al. 2020), and Squared-root Lasso (Belloni et al. 2011).
While in- in-processing techniques outperform pre-processing and post-processing approaches, they are not scalable to large datasets because of a lack of adaptability to stochastic optimization (Mary iet al. 2019 Lowy et al. 2022). All aforementioned examples consist of regularization terms in their objective functions where the gradient cannot be described as a linear combination of data point functions. As a result, applying stochastic gradient descent or other stochastic first-order methods on the objective functions of such problems might not converge, especially for small batch sizes.
Motivated by this, (Lowy et al. 2022) proposes stochastic optimization framework for Exponential Rényí Mutual Information as the measure of independence. More recently Zhong & Tandon (2023) use /-divergences as regularization terms to establish the independence between sensitive attributes and predictions. They estimate the f-divergence regularizers offline through multi-layer neural networks to avoid the computational challenges of devising scalable stochastic methods for nonconvex min-max problems. Our approach, on the other hand, directly solves the variational formulation for both full-batch and stochastic settings with convergence guarantees non-spurious solutions. In Section 2 using the variational representation of fddivergences, we present a convergent stochastic optimization framework for fair learning via f-divergences. (Lowy et al. 2022) is a special case of f-divergences where [() = 12 - 1 (x2 divergence). Aside from x all other divergences listed in Table I are not introduced in the literature to the best of our knowledge.
Designing convergent stochastic algorithms for fair empirical risk minimization can be further explored scenarios involving changes in the data distribution from the source to the target domain. Detection and mitigation of biases against protected groups in the presence of distribution shifts have been extensively studied in recent years. [Lechner et al. (202)) theoretically shows that learning fair representations pere-processing) is nearly impossible for the popular notions of fairness, such as demographic parity in the presence of the distribution shift. Ding et al. (202T), on the other hand, experimentally demonstrates that applying post-processing faimeess techniques (Hardt et al. 2016) to learn fair predictors of income concerning race, gender, and age fails to transfer from one US state (training domain) to another state. Overlooking distribution shifts can lead to catastrophic decisions threatening the well-being of human subjects when deploying a trained model in certain hospitals to other hospitals (Schrouff' et al., (002)). The current literature for handling distribution shifts with in-processing methods relies on certain assumptions on the type of distribution shift (demographic shift (Fang et al. 22020, Du & Wu 2021 Maity et al. 2021 Giguere et al. 2021), label shift (Dai & Brown 2020), and/or covariate shift (Rezaei et al.] 2222 [ingh et al. 2022 or explicit access to the causal graph (Mishler & Dalmasso [022] SScrouuf al., (022) of predictors, sensitive attributes, and target variables. As a result. they face practical limitations and cannot cope with most real- world problems involving complex shifts that cannot be categorized in the ones assumed in their works.
2

---

Published as a conference paper at ICLR 2024
Alternatively, Taskesen et al. (2020) provides convex objective functions for imposing fairness on logistic regression using constraint optimization. [Staib & Jegelka (2019) use MMD for defining uncertainty sets around training distribution, whereas Husain (2020) use Integral Probability Measure (IPM) to mitigate the distribution shift. The main limitation of these approaches is their reliance on the convexity of the underlying learning model and lack of scalability due to incompatibility
with stochastic optimization algorithms. Wang et al. (2023) uses the Maximum Mcan Discrepancy (MMD) distance between the spectral norm of the Hessian matrix at advantaged and disadvantaged data points. However, they do not provide convergence guarantees for their proposed algorithm to any notion of optimality. In addition, the method is not necessarily amenable stochastic updates. While we naturally define the uncertainty set directly on the joint distribution of sensitive attributes and predictions, they use the curvature of the obtained solution quantified by the norm of the Hessian matrix as a heuristic for promoting the robustness of the fair solution.
This paper establishes a scalable (stochastic) fair empirical risk minimization framework through regularization via f-divergences (f-FERM) for both standard and distributed shift settings. f-FERM presents a unified methodology based on the Legendre- Fenchel transformation, enabling us to develop theoretically convergent first-order stochastic algorithms when only small batches of data are available at each iteration. Further, we have presented the first distributionally robust optimization framework under fp norms uncertainty sets covering nonconvex losses such as neural networks. The presented framework for fair inference in the presence of distribution shifts does not rely on the causal graph describing the causal interaction of input features, sensitive attributes, and target variables, which is rarely available in practical problems.
Contributions:
Paper Organization: We structure our response towards designing scalable, robust, and fair algo- rithms into two sections. Section 2 motivates the design of unbiased gradient estimators of objectives with information -theootiin-thoorttii f-divergence regularizers. In Section 3 we present our approach for fair inference in the presence of the distribution shift in detail. Our experiments provide an extensive examination of various f fddivergences and their suitability as regularizers and also show the consis- tency of our method across all batch sizes in contrast to existing benchmarks. Similar experiments are carried out for robust training on varying amounts of distributional shifts in data.
2 FAIR EMPIRICAL RISK MINIMIZATION VIA f E-DIVERGENCES
A widely studied problem in algorithmic faimess is promoting notion of group faimess, such as demographic parity, equalized odds, equality of opportunity, or sufficiency through an in-processing method. For these notions, we aim establish a [conditional] statistical independence between the predictions (e.g., the creditworthiness of the individual) and the sensitive attributes (e.g., gender, race). For simplicity of presentation, we formulate all problems under the demographic parity notion, which requires statistical independence between the prediction and the sensitive attribute. Without loss of generality, all formulations and methods are generalizable to other aforementioned notions of group fairness by considering conditional random variables (see Appendix AA. A popular in in-processing approach for training fair (classification) models under the demographic parity notion is to regularize the empirical risk minimization:
min e
Σ
llio (x:))))) v.) + (D((()0(x) s), (()))))) P(s)).
where 0 is the learning parameters (c.g., weights of the neural network); x; E Rd is the i-th input feature vector; y4 is the actual label/class for sample i; ÿo (x;) is the prediction of the model for sample i; and (x;)) y/) is the loss function measuring the "goodness-of-ff D is divergence between the joint probability distribution of the predictions and sensitive attributes and the Kronecker product of their marginal distributions. Recall that ğe and are statistically independent iff (()o( s) follows (())(x)) @ P(s)). Thus, the second term in (T) is zero iff ÿe and are statistically independent (complete fairness under the demographic parity notion).
for sample i. Here,
This section studies the fair empirical risk minimization regularized by a broad class of f-divergence measures. Let IP and Q be two discrete probability measures taking values in P = {L..... . m). The f-divergence between P and Q is defined as (Polyanskiy Wu 2022 Def (s9e Appendix B for the general continuous case):
P Q
Dj(p,Q)= -
(2)
3

---

Published as a conference paper at ICLR 2024
The above definition, which is also known as f-mutual information (Lu et al. 2023 Csiszár 1967).
covers many known divergence measures used for imposing fairness, such as KL-divergence for the choice of ft) t tlog(t) (t) (Shui et al., 2022). or x2 divergence when f(t) = (t - 1)² Lowy et al. 2022). As shown in Appendix C D in ① is zero if and only if the probability distribution of s and Vo are statistically independent for the choices of f listed in Table T In addition, we prove that these f-divergences either cover or provide upper bounds for the popular notions of fairness violations the literature, such as lp distances, Rényi correlation (Baharlouei et al. 2020), and demographic parity (equalized odds) violation. This means that by minimizing these regularizers, we are minimizing an upper bound of (other) popular faimess violation measures, and thus we are controlling them implicitly. Further, unlike Rényí correlation (Baharlouei et al. 2020; Grari et al. 2020). we can utilize Legendre- Fenchel duality (and variational representation) to develop (provably) convergent algorithms with stochastic (mini-batch) updates. This formulation and the resulting stochastic optimization algorithm are described in the next subsection.
2.1 A CONVERGENT STOCHASTIC ALGORRIHM FOR FAIR ERM VIA J-DIVERGENCES
Let us start by rewriting ① using f-divergences as the divergence measure:
1 ((oo(x)), vi) + + Σ Pa(s k)P so (0o))
P (00 = j. k) Pio (No = ()) -= k)
min
(f-FERM)
While the non-linearity of /ddivergences in (-FERM) empowers the underlying model to capture more complex dependencies between sensitive attributes and predictions compared to the linear measures Zafar et al. 2017). the objective function can no longer be represented as a summation of functions over input data points. Consequently, one cannot directly apply the stochastic gradient descent method (or its variations, such as Adam) to the objective function in (-FERM). In particular, directly evaluating the gradient of the objective function of (f-FERM) on mini-batch of data leads to statistically biased estimation of the entire objective's gradient. Such statistical biases prevent the convergence of algorithms such as SGD (even with a strongly convex minimization landscape) (Ajalloeian & Stich 2020 Chen & Luss 2018). let aside the more complex objectives arising in modern-day neural networks.
To derive stochastic algorithms,, one can use the variational forms of f-divergences to delineate them as pointwise supremum of affine transformation over probability densities. The most commonly used and well-behaved transform is the Legendre- Legendre-Fenchel transform (often called the convex conjugates), which linearizes the dependence of the objective functiion to input data points using a variational reformulation. Particularly, we can rewrite ( (/FFERM) using the following result:
Proposition 2.1. Let f(-) be convex function. Then, (-FERM) can be reformulated as:
min max Σ ((0((x)) + Σ
AycPP..(00 =, - (A( = j)P = k)]
(3)
JEY.
LEB
where f*(2) = Suppwddm(() w² s(w) is the Legendre-Fenchel transformation of the function S.
Proof. The proof is standard and appears in Appendix D
In order to solve (3), we will use (stochastic) first-order methods. Notice that (. k) is constant through the optimization procedure and is computed once by counting the number of data points whose sensitive attribute takes the value of k: T. == (. = k) = >i= L(s; = k). Assume we use the softmax layer to compute the probabilities of different classes our classification task (as is standard in logistic regression or using neural networks for classification). Let (x;; 0) be the j-th entry of the softmax layer output for datapoint x,, predicting the probability of class j. Then it is easy to show that we can obtain unbiased estimators of P 5o (No j) and IP je.s (5o = j. k) using i..d. mini-batch B of data points. More precisely, we have
88
1 Σ n
Poo (ōo = =) =
(x 0) =
Ps (x)00)
B3
Pap Gi B3)
(4)
[18
P Pio. (00 = =j 8. = =k)- 1 Σ
= =B 1
Fs (x:: 0)1(s= ]
B
2og (g.k; 13)
4

---

Published as a conference paper at ICLR 2024
Table I: Unbiased Estimators for f-divergence Regularizers
Divergence
f(t)
The term Fjk inside regularizer À EE J, Jik in
yxPPyols - (Ask + A7 PPyll
x²
(t- - 1)2 -lnl - tlnt
Tk A yolsx
Reverse KL
*
+ (1 In(nnnn(n ((-)))))))))))))))))))))) Pyll
Total Variational
k A Volss - -1ool(1Auuk1/1)
KL
n yals. -AA 10aa-11p 10011PPpp -yo
Sassen-Shanoon
-(++1) ( +/hl
T Aja yolss yolss + +11(2
e PPol
Squared Hellinger
(Vi 1)
n P solss + (A,H 7 + y)lPyol
As a result, Problem 3 can be written as a linearly separable function of input data points (x, ss:
min max 1 Σ {(ūo (x:), vs)
Σ (xx; =k) (A
(5)
JEY.
Thus, evaluating the gradient of the objective function w.r.t. the variables O and A over a random batch of data points leads an unbiased estimator of the gradient of the objective function.
In addition to providing an unbiased estimator of gradients, the reformulation (5) has another crucial property: the objective
is concave in A. Therefore, optimization problem (5) falls under the category of cencoovvexcconcay min-max optimization problems. That is, the objective is (possibly) nonconvex in 0 and concave in A. Thus, we can borrow tools from the (stochastic) nonconvex-
concave min-max optimization literature (Lin et al. 2020 Razaviyayn et al. 2020a Li et al.) 2023)
to derive a convergent first-order stochastic algorithm as presented Algorithm | We listed the closed-form of f()). (+)) (+), for several widely-used f-divergence measures including KL-divergence, Reverse KL-diieegence, x2 diveeeegen Squared Hellinger distance, -haenn-Shnnoon divergence, and
total variation distance in [ For the derivation, Appendix
Algorithm 1 Stochastic Gradient Descent-Ascent (SGDA) for f-FERM
Input: 0º E Re step-sizes ne, Na. faireess parameter 2 0, iteration number T, Batchsize b 2: for = 1, ...., do
3: Sample minibatch of data B, Vet), (Xib. yes)]
4: 0¹ = 0
me 0
Σ Vol(jo(x),)) 7o
(j, k;; - (A 1) (f: B,))
5:
A
t-1 + Na A
V (A)x 1 Ps.. k; B.) (A 1) PP (i: B.))
6: Return: 0²
Theorem 2.2. (Informal Statement) Assume that E(.,-) and F5(,00 are Lipschitz continuous for any given j and O and their gradients are L-Lipshitz Further, assume that IP(s k) for all protected groups and P j) 0 at every iteration for all labels j. Then, for any given batch size 1 < B S n, Algorithm finds an e-stationary solution of (-FERMM in O ( for any given
Proof.
The formal statement and proof relegated to Appendix
Theorem 2.2 applies to all f-divergences listed in Table for all batch-sizes (even as small as the batch size 1). More sophisticated algorithms can be used to obtain O iteration complexity Rafique
et al. (810); Zhang et al. (2022). However, such algorithms use nested loops and require more hyperparameter tunings. We provide an example of such an algorithm in Appendix G the f- divergence leads to strongly concave function in A satisfies Dolyak-Lojasiewicz condition (c.g.. for x² divergence). a faster rate of OEE -5) can be obtained for this algorithm (Appendix F). In further improve this rate to O(c-1) iteration
addition, if larger batch size of O(c-2) 2) used, we
complexity (see Appendix (F). Finally, when full batch size is used, then double/triple-Ion algorithms can lead to the iteration complexity bounds of ((e 2) in the nonconvex-strongly concave setting and
O in the general nonconvex-concav. setting; see (Kong & Monteiro 2021 Nouiehed et al.
2019 Ostrovskii et al. 2021b Thekumparampil al. 2019).
ROBUST F-RM IN THE PRESENCE OF DISTRIBUTION SHIFTS
In the previous section, we assumed that the training and test domains have the same distribution. However, this assumption is not necessarily valid in certain applications (Fang et al. 2020). In
5

---

Published as a conference paper at ICLR 2024
particular, model that behaves fairly on the training data distribution may have unfair performance in the test phase. To address this issue, this section develops stochastic algorithms for fair empirical risk minimization via f-divergences in the presence of the distribution shifts.
Assume that (s.y(s, ()) is the joint distribution of sensitive attributes and predictions on the training data. The distributionally robust fair empirical risk minimization via f-divergences is formulated as:
min 0 TI E (x;) Ui)
max D (P(0o (x), s)1l (x)) @ P(s)) S K.. (6)
s.t.
PEB
B = B(P, 6) is the distributional uncertainty set defined as certain ball around the training distri- bution P with radius 8. This formulation guarantees that the model fairness is preserved (up to violence of f-divergence less than k) even when the test distribution slightly changes. With a slight change of notation, IP refers to the training distribution, whereas is the optimization parameter.
One can define the uncertainty set through an neighborhood around the joint distribution of the training data characterized by distance measure such as lp norms, Wasserstein distance, or MMD distance. While these distributionally robust uncertainty sets are thoroughly analyzed for empirical risk minimization (ERM) (Kuhn et al. 2019, Blanchet et al. 2019; Levy et al. 2020), the DRO formulation for ERM is limited to the Wasserstein distance for the fair logistic regression (Taskesen et al. 2020) and MMD distance (Wang et al. (022)) on the distribution curvature as a heuristic for robustness. Unfortunately, none of these approaches offer a convergent algorithm with stochastic updates. Further, some of these approaches are limited to special loss functions and heuristics. On the other hand, we study imposing the distributionally robust fairness via f-divergences for a general loss function where the uncertainty set is characterized by f norms (Section 3.1 or f-divergences (Section 3.2 Our results show that the former approach is more suitable when lower levels of robustness for fairness are required, and the latter works better for handling larger distribution shifts.
3.1 ROBUST F-FERM UNDER Ep NORMS AND SMALL DISTRIBUTION SHIFTS
This section focuses on the widely studied lp norms as the uncertainty set for the distributional distance between the training and test domains. In this case, Problem (6) can be written as:
min Ø
(((o(x;), (1) s.t.
max
(PI S,
PP- 1.55
110
where Ip represents the joint distribution of the sensitive attributes and predictions and Q denotes the Kronecker product of the marginal distributions between sensitive attributes and predictions.
Since handling non-convex constraints challenging, as is standard in training machine learning models, we consider the Lagrangian relaxation of Problem as follows:
min (x)((x)), + A max (P(I)
FF- Pllp S8
1 S4
This problem falls under the nonconvex cowneeex-oococcae... min-max optimization category and is most likely to be computationally hard for general uncertainty sets (Daskalakis al. 2021). However, such a min-max optimization problem can be solved to stationanty when the diameter set B is small (i.e., under small domain shift), see (Ostrovskii et al. 2021a). The core idea is to approximate the inner maximization problem with the Taylor approximation, leading to a nonconvex-concat
min-max optimization, which is easier to solve (Daskalakis et al. 2021; Razaviyayn et al.) (020b). (see|Foret This idea has been used and been successful in machine learning (see Foret al. (2020) for its use in
Sharpness aware minimization). Utilizing this idea, Problem (8) can be approximated as:
min max S6
h(0, U.
Σ Elge (x.). v.) A(U, (L)I() + A(V, (PPI (9)
where we used the change of variables U : P PP-Paam Pan == Q Q Equivalently,
min
((o( v1) + V U + ^6 (
(10)
where || l1g is the dual of the lp norm with 1 + =
Proposition 3.1. Assume that the gradient of the loss function is L-Lipshitz. and the seder derivative of the loss exists. Then, a given e- approximate stationary solution of Problem (10) is an (()) aapprxximat stationary solution of Problem ( whenever L S

---

Published as a conference paper at ICLR 2024
This proposition, which is an immediate application of Ostrovski et al. (2021a Theorem 3.1), states that if the desired training accuracy e is comparable with the distribution shift amount (i.e. small distribution shift regime), then one can solve problem (IO) instead of (8) Thus, in this regime, need to solve (T0) or equivalently (9) To this end, we need to obtain the (sub)-gradients of the objective function in w.r.t the 0, D, and V variables. First, notice that
Vuh U, = VpD, = x (p, Q) and Vyh(e,U,V) = VODI =
f f" (p, Q)),
where a² (P, Q) arg max Ej (0) 4, ()) Here invoked Danskin's 's theorem on the variational form of Dy; (0) and (0) is the j-th element of P and Q respectively. Next, we need to compute Veh UJ, V). Notice that the derivative of the first term in h(-) w.r.t. is easy to compute. We next calculate the derivative of the second term of h(O, U, V) w.r.t. O. As the derivative
of the third term can be computed similarly, we omit its derivation here.
Vo (U, o (f, - E uy 2, ()) ()) ())O
VU,
() (f*)) (=);()))))
(II)
where in the last equation, we used the implicit function theorem to compute the derivative of a' w.r.t. 0. Notice that implicit assumption here is that f is differentiable (which holds for KL-divergence, x2 divergence, reverse KL, -Saannon,, and Squared Hellinger distance). Having access to the gradients, we can apply the standard [sub-]get laradlgradeent descent-ascent algorithm obtain a solution to Problem (T)) (see Appendix H for the details).
A semi-stochastic memory-efliciem first-order training algorithm. To apply (stochastic) gradient descent-ascent algorithm (Lin et al. 2020) to problem ()) we need to have unbiased estimator of the function (0, U, V) w.r.t. 0, U, and V variables. While it seems challenging to obtain unbiased estimator w.r.t. all variables, one can notice that if p, (0) and 9; (0) can be computed easily with one forward pass over all data points (i.e., in O(m X n) memory requirement). Consequently, the gradient of O,, U, V) w.r.t. U and V can be computed with one forward pass over all data points (without the need for doing backpropagation). On the other hand, one can easily obtain unbiased estimator of V Vop, (0) and Ved, (0) in (II) using small maini-bach of data. Such task requires O(b x d) memory with d being the number of parameters (i.e., O E (Rd) and 6 being the batch size. Combining this unbiased estimation with the computed values of s (0) and q (0) leads to an unbiased estimator of the objective of (9) w.r.t. O variable. To summarize, we need to do one forward propagation to obtain gradients w.r.f. U and V, and we only do backpropagation for computing gradients w.r.t. over the mini-batch of data. Such an algorithm requires O + bd) memory requirement and thus can be used for training large models (with d, n >> b, m). It is known that memory requirements are the major limiting factors in training large models such LLMs (Malladi al. 2023).
3.2 ROBUST F-FERM UNDER foo NORMS AND POTENTIALLY LARGE DISTRIBUTION SHIFTS
The developed framework in the previous section assumes the distribution shift is small (the uncer- tainty set diameter is smaller than a certain threshold). When preserving fairness in the presence of large distribution shifts is a priority, our previous methodology might not work well. As discussed before, the formulation (8) leads to a nonconvex-noncoomaae min-max optimization problem and this class of problems hard to solve computationally in general (even stationarity notions). Thus, we need to exploit the structure of the problem. In this section, we show that we can exploit the structure to develop first-order algorithm under large distribution shifts. Particularly, we focus on the case where the uncertainty set is Eo ball and the divergence satisfies certain assumptions (i.e., f*(a") > 0 and a* 0, which is satisfied for KL divergence).
Since the function D, is convex in IP and Q, under l. uncertainty set on IP and Q, the optimal solution of the maximization problem ( will be at an extreme point. Moreover, under the assumption that f* > 0 and a² > 0 (which is satisfied for KI. divergence). one can easily see that the optimal Pj = min + 6, 1} and g; = max(ú; 6, 0} (see Appendix [ for the exact proof). Notice that we need to relax the probability simplex constraint to obtain this efficient, optimal closed-form solution. Thus under this assumption, problem (8) can be reformulated as
1 Σ e(jo (x:) v1) XDy + 111 max (Q 6, 0)),
min n
(12)
which is regular minimization problem and (sub)gradient descent can be utilized to solve it.
7

---

Published as a conference paper at ICLR 2024
4 EXPERIMENTS
We use three popular notions of group fairesss: demographic parity, equalized odds, and equality of opportunity violations (see Appendix foro definitions) to measure the fairness of trained models. To run A we set f/8 and 1/a to 10-5 and 10-6 respectively in all experiments. Further, by changing A, we get different points in the trade-off curve between accuracy and fairness. The range of À depends on the f-divergence (see Appendix[]oo for more information on tuning sypee-parameters) In the inference phase of our experiments, we use the standard maximum likelihood decoding based on the output of the softmax layer, i.e., the predicted label is the label with the highest logit value.
As we will see in this section, several f-divergence measures lead to reasonable fairness/accuracy tradeoffs and can outperform existing benchmarks. However, no single f-divergence measure uniformly outperforms other measures in all the experiments. Thus, we believe in applications, the choice of the f-divergence can be viewed as hyperparameter that can be tuned by cross-validation.
4.1
TRADEOFFS ON BENCHMARK DATASETS
In the first of experiments, we compare different f- divergence formulations for (-FERM) to each other and several state-of-the the-art approaches supporting multiple sensitive attributes. Figure [ demonstrates the given tradeoff on the adult dataset (Becker & Kohavi, 1996) with gender and race as the sensitive attributes (black-female, black-male, white-female,
Batch Size 8 (Gender and Race)
Demographin Parity Violation
0.30
Naive
0.25
Jensen Sharmon
Squared Heellinger
0.20
KL Divergence
Chi Square Reverse K.
0.15
0.10
white-male). To measure faireess, we use the demo- graphic parity violation defined as:
0.05
DPV max iJES
[ = 1/s = i) - P(ù = 1|s = 5
0.00
0.16
0.18
0.20
0.72
0.74
Test Error
In the case of binary sensitive attributes (e.g., gen- der), there is no significant variation between dif- ferent f-divergences. However, when we have 2 sensitive attributes and the batch size is small (8 in Figure [ the results significantly differ for various f- divergences. Interestingly, KL-divergence for smaller A values shows improvement in fairness violation and accuracy simultaneously. We do not observe such a phenomenon for other f-divergences and state-of-the art approaches in the literature. Further, in Figure 2 we compare one of the f-divergences (reverse KL)
Figure I: Performance of different f-divergences as the regularizers. The experiment is on the adult dataset with gender and race as sensitive attributes. While the offered tradeoff's close to each other for small demographic parity viola- tions, KL-divergence shows an extraordinary per- formance for a low-fairness high-accuracy regime. We do not display the performance for larger batch sizes when only one sensitive attribute is avail- able due to the insignificant difference between the performance of different f fddivergences.
to several SOTA methods including Mary et al. (2019), Baharlouei et al. (020);; Cho et al. 2020).
Other approaches such as the pre-processing method of Zemel al. (2013). post- proepeocessing approach Hardt et al.] (2016), and several in in-processing methods including Zafar et al. (2017); Donini et al. (2018): Jiang et al. (2020) demonstrate lower performance compared to the ones depicted Figure 2 and are removed from the figure. While our approach demonstrates consistently good performance across different batch sizes (full-batch, 64, 8, 2), the performances of other methods drop significantly for smaller ones. For further experiments other datasets (German and COMPAS) and other fairness measures (equality of opportunity and equalized odds violations), see Appendix K
Fill Bucch EGenser ynd Raod)
Borch Size 66 (Gender and Raon
Fatch Size = Höender and Rand)
Banch Size 2 (Gender and Rocel
all 2013
Aote ai 2018
3.23
2000
0.0
0.20
3.00
6.00
0.30
2.00
850 037 0TE 850 633 023 322 633 024
C33 OLT 150 039 528 121 632 033 134
314 037 031
315 120 031 332 935 034
035 035 818 853 623 AZI #22 033 AM4
Figure 2: Performance attributes with different Batch-sizes. The red dashed line represents the Naive baseline where the model outputs zero with probability By increasing the model hecomes fairer at the cost of the loss in accuracy.
the trained fair models on Adult Dataset with gender and race as two sensitive
4.2 CHIRNESS-ACCUR.NN TRADEOFFS IN THE PRESENCE OF THE DISTRIBUTION SHIFT
We perform two experiments to evaluate the Algorithms developed in Section In the first experiment, randomly switch the label of genders for n% of the data points (n ranges from to 20) in the
8

---

Published as a conference paper at ICLR 2024
Adult dataset. Then, we train models the new datasets with a proportion of corrupted sensitive attributes and evaluate the performance on the test data. Figure is obtained by training different models to achieve 80% accuracy on the test data and comparing their demographic parity violation. By increasing the percentage of corrupted sensitive attributes, we see that both f-DRO and f-infinity achieve less DP violation than SOTA approaches in the literature. In this specific experiment, f-DRO works better than f-infinity, and there is no significant difference between choosing KL- divergence or x" the function f. Among the papers designed for handling distribution shifts, Rezaei et al. 2021) and Wang et al. (2020) were the only options with the available implementation. In a more recently collected dataset (new adult) (Ding et al. 2021), the users are sepa- rated based on their living state. We train differ- ent fair models in single state and evaluate the fairness-accurace
0.14
Mary, et al. 2019
Cho, et al. 2020
0.12
Baharioues,
2023
Rezael, al. 2021
tradcoff in other states. Fig- ure depicct the performance of different meth-
Warg, et 2022
DP Violation
0.10
al. 2022
Fettnty Divergence
ods. For each method, the center point is the av- erage of accuracy and fairness among 50 states. The horizontal and vertical lines show the 25- percentile to 75-percentile range of performance among the states. The training fairness violation set to 0.02 for all methods. We observe that f- f-infinity preserves the fairness level better than comparison, f-DRO has
0.08
Divergence
tnttnity X2
FORC
0.06
0.04
0.02
0.0
2.5
12.5 15.0 17.5 20.0 Corrupted Label Proportion (%)
5.0
7.5
10.0
other approaches. a better accuracy. Depending on the applica- tion, we suggest using f-infinity preserving a high level of fairness is a priority and f-DRO for the cases when a better tradeoff between fair- ness and accuracy is expected. Note that both approaches offer better fairness-accuracy trade- offs compared the SOTA approaches in the literature.
Figure 3: Performance of different sfate-of-the-ar ap- proaches and our two methods for handling distribution shift. The dataset is adult, and the sensitive attribute is gender. We randomly flip the label of a proportion of gender entries (from 0 to 20%). As we observe, our approach demonstrates more robustness against the drop DP violation compared to other approaches.
Source Domain: California State
Source Domain: Texas State
75
Zeme et ai. 2013
Zamel et 2013
71
Harth al., 2018
74-
Hardt et el., 2016
Zafar et at, 2017
Zafar et al, 2017
Accuracy (%)
70
Rezael 2021
Wang
Accuracy [%6
73
Wang al.,
Rezaal al., 2021
Lowy at 2022
Laxy
finfinity AORO
72
Sinfinity
KORO
69
71
69-
67
68
0.01
0.02
0.03
0.04
0.05
0.06
0.02 0.03 0.04 0.05 0.06 0.07 0.08
Equality of Opportunity Violation
Equality of Opportunity Violation
Figure 4: Performance of the trained fair models new Adult Dataset. The model is trained one state (California or Texas) and evaluated in 50 states. The distribution each state dataset different than others. Thus, the IID assumption does not hold among datasets of different states.
CONCLUSION
This paper presented a unified stochastic framework for fair empirical risk minimization via f- divergences (f-FERM). The key idea is to reformulate the objective function min-max op- timization problem using Legendre-Fencchn Fenchel duality of f-divergence. This enables us to develop an unbiased gradient estimator and a convergent stochastic first-order algorithm. Furthermore, we robustified f-FERM using &p norm balls as the uncertainty set against distributional changes. While our empirical investigation delves into the performance and fairness distinctions among various f-divergences, more comprehensive analysis is warranted to determine the optimal f-divergence concerning the tradeoff between performance and fairness, faster convergence, and asymptotic behav- iors. Furthermore, the distributionally robust formulation of fair empirical risk minimization and the advantages of each formulation can be explored beyond f-divergences as the measure of fairness violation and &p norm balls uncertainty sets.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by the NSF CAREER Award CCF2144985, the AFOSR Young Investigator Program Award FA9550-22-1-0192, a gift from the USC-Meta Center for Research and Education in AI, and gift from Google.
REFERENCES
Civil Rights Act. Civil rights act of 1964. Title VII, Equal Employment Opportumities, 1964.
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision- decision-making. In Proceedings of the AAAI conference on artificial intelligence, pp. 1418-1426, 2019.
Muhammad Aurangzeb Ahmad, Carly Eckert, and Ankur Teredesai. Interpretable machine learning in healthcare. In Proceedings of the 2018 ACM international conference on bioinformatics, computational biology, and health informatics, pp. 559-560, 2018.
Ahmad Ajalloeian and Sebastian Stich. Analysis of SGD with biased gradient estimators. CoRR, abs/2008.00051, 2020. URL https::/axxi....a.mm.mmm wwt.:ogg//aa....o http:////aaxx..orrraaaa/0/2.. 00051
Wael Alghamdi, Hsiang Hsu, Haewon Jeong, Hao Wang, Peter Michalak, Shahab Asoodeh, and Flavio Calmon. Beyond adult and compas: Fair multi-class prediction information projection. Advances in Neural Information Processing Systems, 35:38747-38760. 2022.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In Ethics of Data and Analytics. pp. 254-2644 Auerbach Publications, 2016.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02880 2019.
Sina Baharlouei, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In International Conference on Learning Representations, 2020.
Sina Baharlouei, Fatemeh Sheikholeslami, Meisam Razaviyayn, and Zico Kolter. Improving adver- sarial robustness via joint classification and multiple explicit detection classes. Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Confer- ence on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 110781 PMLR, 25-27 Apr 2023.
Yogesh Balaji, Swami Sankaranarayanan. and Rama Chellappa. Metareg: Towards domain gen- cralization using meta-rogularization. Advances in neural information processing systems, 31, 2018.
Barry Becker and Ronny Kohavi. Adult. UCI Machine
Learning Repository, 1996. DOI:
Alexandre Belloni, Victor Chernozhukov, and Lie Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791-806 2011.
Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust wasserstein profile inference and applica- tions to machine learning. Journal of Applied Probability, 56(3):830-88 857, 2019.
Roberto Boselli, Mirko Cesarini. Fabio Mercorio, and Mario Mezzanzanica. Classifying online job advertisements through machine learning. Future Generation Computer Systems, 86:319-322 2018.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities commercial gender classification. In Conference on fairness, accountability and transparency, pp. 77-91. PMLR. 2018
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57, 2017. doi: 10. 10.1109/SP.001..49
10

---

Published as a conference paper at ICLR 2024
Alessandro Castelnovo, Riccardo Crupi, Greta Greco, Daniele Regoli, Ilaria Giuseppina Penco, and Andrea Claudio Cosentini, A clarification of the nuances in the faimess metrics landscape. Scientific Reports, 12(1):4209, 2022.
Jie Chen and Ronny Luss. Stochastic gradient descent with biased but consistent gradient estimators. CoRR, abs/1807.1 1880, 2018.
11880
Jaewoong Cho, Gycongjo Hwang, and Changho Suh. A fair classifier using kernel density estimation. Advances in neural information processing systems, 33:15088-15099, 2020.
Imre Csiszár. Information-type measures of difference of probability distributions and indirect observation. studia scientiarum Mathematicarun Hungarica, 2(4):229-318, 1967.
Jessica Dai and Sarah M Brown. Label bias, label shift: Fair machine learning with unreliable labels. In NeurIPS 2020 Workshop Consequential Decision Making in Dynamic Environments, volume 12, 2020.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, Pouria Mahdavinia, and Mehrdad Mahdavi. Distributed personalized empirical risk minimization. In International Workshop on Federated Learning for Distributed Data Mining, 2023.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34:6478-64999 2021.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor and Massimiliano Pontil. Empirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018.
Wei Du and Xintao Wu. Fair and robust classification under sample selection bias. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2999-3003, 2021.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214 2012.
Gideon Elford. Equality of Opportunity. 2023.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. Advances in Neural Information Processing Systems, 33: 11996-12007, 2020.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. 2020.
Stephen Giguere, Blossom Metevier, Bruno Castro da Silva, Yuriy Brun, Philip S Thomas, and Scott Niekum. Faimess guarantees under demographic shift. In International Conference on Learning Representations, 2021.
Vincent Grari, Sylvain Lamprier, and Marcin Detyniecki. Fairess-awaae neural rényi minimization for continuous features. Twenty-iinth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence (IJCAI-PRICA 20), pp. 2262-2268. International Joint Conferences on Artificial Intelligence Organization, 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.

---

Published as a conference paper at ICLR 2024
Hisham Husain. Distributional robustness with ipms and links regularization and gans. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 11816-11827. Curran Associates, Inc., neur cc/paper fi w41ls//pppee/22000 2020. URL 2at.aa7004000000aa0442422222333. [1225355500011177711333323222263
f1 02
Aleksandr Davidovich Ioffe and Vladimir Mihajlović Tihomirov. Theory of extremal problems. Elsevier, 2009.
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in artificial intelligence, pp. 862-872. PMLR, 2020.
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimi- nation. Knowledge and information systems, 33(1):1-33, 2012.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-coneet concave min-max max problems. SIAM Journal on Optimization, 31(4)22558 2585, 2021.
Alex Krizhevsky, Πya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6):84-90, 2017.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh-Aballe Wasserstein distributionally robust optimization: Theory and applications machine learning. In Operations research & management science the age of analytics, pp. 130-166. Informs. 2019,
Tosca Lechner, Shai Ben-David, Sushant Agarwal, and Nivasini Ananthakrishnan. Impossibility results for fair representations. arXiv preprint urXiv:2107.03444 2021.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33:8847-8860 2020.
Jiajin Li, Linglingzhi Zhu, and Anthony Man-Cho So. Nonsmooth nonconvex-noncoocave minimax optimization: Primal-dual balancing and iteration complexity analysis, 2023.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization.
arXiv preprint arXiv:2007.01162, 2020.
Tianyi Lin, Chi Jin, and Michael Jordan, On gradient descent ascent for nonconvex-coneet minimax problems. In Hal Daumé IIII and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 6083 6093. PMLR, 13-18 Jul 2020. URL 1ir20a html
Andrew Lowy, Sina Baharlouci, Rakesh Pavan, Meisam Razaviyayn, and Ahmad Beirami. A stochastic optimization framework for fair risk minimization. tmlr, 2022.
Yiwei Lu, Guojun Zhang, Sun Sun, Hongyu Guo, and Yaoliang Yu. SIS-MICL: Understanding and
generalizing InfoNCE-based contrastive learning. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL [Ettpss://openeevieee.eeeteteeee wot.te/////ooomaidodoo000/
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex--trroglyy-ommm Processing Systems, 33:20566-220 20076,, 2020.
minimax problems. Advances in Neural Information
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 17XXiv:7006000 170..66083 2017.
Subha Maity, Debarghya Mukherjee, Mikhail Yurochkin, and Yuekai Sun. Does enforcing fairness mitigate biases caused by subpopulation shift? Advances in Neural Information Processing Systems, 34:25773-25788 2021.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. arXiv preprint 2rXiv:2305.17333 2023.
12

---

Published as a conference paper at ICLR 2024
Jeremie Mary, Clément Calauzènes, and Noureddine El Karoui. Satrness-awarte learning for con- tinuous attributes and treatments. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Pro- ceedings of Machine Learning Research, pp. 3382-43391 PMLR, 09-15 Jun 2019. URL htttps:/prrcceddin
mm www.r.press///e mary 9a html
Alan Mishler and Niccolò Dalmasso. Fair when trained, unfair when deployed: Observable fairness measures are unstable in performative prediction settings. arXiv preprint arXiv:2202.05049) 2022.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Dmitrii M Ostrovskii, Babak Barazandeh, and Meisam Razaviyayn. Nonconvex-noonconce min-max optimization with a small maximization domain. arXiv preprint arXiv:2110.033550 2021a. 2021aa,
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex cenconvxx-concvee concave smooth min-max problems. SIAM Journal on Optimization, 31 (4):2508-2538, 2021b.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Book draft, 2022.
Flavien Prost, Hai Qian, Qiuwen Chen, Ed H Chi, Jilin Chen, and Alex Beutel. Toward better trade-off between performance and fairness with kernel- basee distribution matching. arXiv preprint arXiv:/910.111 11779, 2019.
H Rafique, M Liu, Q Lin, and T Yang. Non-convex min-mi max optimization: provable algorithms and applications in machine learning (2018). arXiv preprint arXiv:1810.0200 1810.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-coneee min-max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3):1087-1122) 2022.
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong, Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances. IEEE Signal Processing Magazine, 37(5):55-6)) 66, 2020a. doi: 10. 109/MMPP2020.300338.
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances. IEEE Signal Processing Magazine, 37(5):55-66, 2020b.
Ashkan Rezaei, Anqi Liu, Omid Memarrast, and Brian D Ziebart. Robust fairness under covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9419-9427, 2021.
Jessica Schrouff, Natalie Harris, Oluwasanmi Koyejo, Ibrahim Alabdulmohsin, Eva Schnider, Krista Opsahl-Ong, Alex Brown, Subhrajit Roy, Diana Mincu, Christina Chen, et al. Maintaining faimess across distribution shift: do have viable solutions for real-world applications? arXiv preprint arXiv:2202.01034. 2022.
Changjian Shui, Gezheng Xu, Qi Chen, Jiaqi Li, Charles X Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning fairness and accuracy on multiple subgroups. Advances in Neural Information Processing Systems, 35:34121-34135, 2022.
Harvineet Singh, Rina Singh, Vishwali Mhasawade, and Rumi Chunara. Fairness violations and mitigation under covariate shift. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 3-13, 2021.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference Learning Representations, 2018.
13

---

Published as a conference paper at ICLR 2024
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL / pcppppp fi corrrrfilesss Filespaperr 201 9019//110 2011:///117777783100006155555513
Bahar Taskesen, Viet Anh Nguyen, Daniel Kuhn, and Jose Blanchet. A distributionally robust approach to fair classification, 2020.
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
Berk Ustun, Yang Liu, and David Parkes. Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference Machine Learning, pp. 6373 -3822. PMLR, 2019.
Mingyang Wan, Daochen Zha, Ninghao Liu, and Na Zou. Modeling techniques for machine learning fairness: A survey. CoRR, abs/2111.03015, 2021. URL http:/pss//aaaa..rrr/ab////// 03C15
Haotao Wang, Junyuan Hong. Jiayu Zhou, and Zhangyang Wang. How robust is your fairness? evaluating and sustaining fairness under unseen distribution shifts. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https:
httpp:://openrevee.. http://ppppeeeeeeeeeeepeee net forum?
Id=11pGlecI22
Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Michael Jordan. Robust optimization for fairness with noisy protected groups. Advances in neural information processing systems, 33:5190-528 90-0900, 2020.
Yang Xin, Lingshuang Kong, Zhi Liu, Yuling Chen, Yanmiao Li, Hongliang Zhu, Mingcheng Gao, Haixia Hou, and Chunhua Wang. Machine learning and deep learning methods for cybersecurity. Ieee access, 6:35365-3538L1 2018.
Ke Yan, Lu Kou, and David Zhang. Learning domain-invariant subspace using domain features and independence maximization. JEEE transactions on cybernetics, 48( (8(1):288-299) -9988 2017.
Mubammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairesss constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pp. 962-970. PMLR, 2017.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems. Advances in Neural Information Processing Systems, 35:21668-21681 2022.
Meiyu Zhong and Ravi Tandon. Learning fair classifiers via min-max f-divergence regularization, 2023.
14


Reviews:
[{"review_id": "FY2xsvlm1x", "reviewer": "Reviewer_o4nf", "summary": "This paper first presents a framework for fair ERM using f-divergence. Next, the authors propose a distributionally robust fair ERM framework, where the ambiguity set is constructed using $\\ell_p$-norm. For the theoretical part, a convergence analysis of the stochastic optimization for the ERM formulation is proposed, leveraging the results from Lin et al. (2020). The authors perform comprehensive numerical study to validate the superior performance of their proposed framework.", "questions": "See the weakness part.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The formulation, optimization algorithm, and convergence analysis for the ERM formulation seem correct and novel.\n- The numerical study is comprehensive to demonstrate the effectiveness of their proposed algorithm.", "weaknesses": "- The only novel theoretical part is the convergence analysis of the SGDA for solving the ERM formulation. The corresponding sample complexity for finding $\\epsilon$-statariony solution of (f-FERM) is $O(\\epsilon^{-8})$. However, I wondered if the authors use the state-of-the-art optimization algorithm for solving nonconvex-concave min-max games and if the sample complexity is currently the optimal one in the literature. If so, the authors should highlight it in the literature. \n- For the distributionally robust formulation (8), the authors used $\\ell_p$-norm to model the ambiguity set, but I am afraid that this usage may not be a novel choice because it is not a flexible choice as Wasserstein, $f$-divergece, or MMD, to quantify the difference between distributions. I encourage the authors consider the extension to other choices of ambiguity sets.\n- When the ambiguity set of formulation (8) is small, the authors propose a first-order approximation formula to solve it (see Eq.(10)). Although the authors present the approximation error between formula (8) and (10), the complexity for solving Eq.(10) is not presented in this paper.\n- When the ambiguity set of formulation (8) is potentially large, the first-order approximation formula may not achieve good performance. To this end, the authors consider another formulation in Section 3.2. However, I have several concerns of the deviation:\n  * Can the authors add more details regarding the sentence \"One can easily see that the optimal $p_j=\\min(\\hat{p}_j+\\delta, 1)$ and $q_j=\\max(\\hat{q}_j-\\delta,0)$\"? It is not obvious for readers to check this point.\n  * What is the meaning of the scalar $\\delta>0$? It is not introduced. if I remember correctly, in standard f-divergence DRO it is the Lagrangian multiplier corresponding to the probability simplex constraint that needs to be optimized.", "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": "", "extra_scores": {}}, {"review_id": "U1VOxWNnHv", "reviewer": "Reviewer_PRWu", "summary": "Fairness constraints, such as DP and EO are hard to optimise directly thanks to their discrete nature. Existing bias mitigation approaches propose various differentiable proxies, typically correlation based, such as Zafar et al. They however do not allow unbiased small-batch estimation of the corresponding gradient.\n\nThe present paper uses f-divergence as a proxy for independence (they include EO & DP). They introduce a gradient based method, where that has unbiased estimate and therefore allows arbitrary small batch size. In the experiments they use batch size as small as 8. Arguably, this can allow to scale the method to larger problems.\n\nTo my knowledge, this paper presents the first theoretical result for gradient based optimisation of fair classifiers.\n\nI want to ask authors to clarify, how do they obtain classifier $ \\hat{y}$?\nTypically, one obtains differentiable probabilities $p_{\\theta}(y = j|x)$, and then maximising the probability yields the classification. However, the expression (4) suggest that the estimator is sampled.\nThis may harm the accuracy in practice. It is ok to use $F_j$ as a proxy, but it is better if you clarify that explicitly for applied people who may potentially use your method.\n\nSecondly, in Theorem 2.2 the stated convergence time is $O(\\epsilon^{-8})$ which seems rather slow. Does it affect the amount of epochs you use in the experiments, is it unusually large?\n\nThirdly, could you please clarify directly in Proposition 2.2. what is the dimension of variables $A_{jk}$", "questions": "mentioned in summary", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "SGD with unbiased gradient updates for fair classification.\n\nAdditional result for robust fair classification.\n\nTheoretical result for SGD for fair classification.", "weaknesses": "mentioned in summary", "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": "", "extra_scores": {}}, {"review_id": "SzZ5qXIAqV", "reviewer": "Reviewer_zLcF", "summary": "The paper proposed a unified stochastic optimization framework for fair ERM based on f-divergence measures.  The main idea is to reformulate it as a minimax problem using the Legendre-Fenchel conjugate function. This minimax formulation facilitates the development of the standard stochastic gradient descent and ascent algorithms for solving fair ERM. The convergence guarantees are stated in Theorem 2.2 which is mainly a corollary of the results in Lin et al. (2020) since this formulation is concave w.r.t. the dual variable.   The paper also addressed the problem of distribution shift and reformulated it using Lagrangian relaxation as a non-convex and non-concave problem. Extensive experiments are conducted to validate the proposed algorithms.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A unified formulation for fair ERM using the f-divergence and then minimax reformulation which facilitates the application of SGDA. \n2.  A robust variant to address the distribution shift\n3. Extensive  and convincing experiments", "weaknesses": "1. The proposed unified formulation and its minimax reformulation seem incremental as similar minimax forms have appeared in many existing works of fair machine learning \n2. The convergence analysis is straightforward from the paper by Lin et al. (2020).", "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": "", "extra_scores": {}}, {"review_id": "WPrbzZ4mUl", "reviewer": "Reviewer_hKcK", "summary": "This paper proposes a new framework for fairness, based on f-divergence and mutual information. This method is called f-FERM. From theory of minimax optimization, it shows the convergence to the optimum of f-FERM. Empirically, f-FERM also shows improvement over existing baselines.\n\n--post rebuttal--\nThank you for the rebuttal and my understanding of this paper got sharpened. I think the fairness definition needs to be clearly stated in the paper, and the uncertainty of which f-divergence seems a bit confusing to me. Unfortunately I cannot change the score based on my point of view.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The method is quite straightforward. Suppose the output $y$ and the sensitive attribute $s$ are independent, then the f-Mutual Information term becomes zero. Therefore, the $f$-FERM encourages independence and thus fairness.\n2. Using variational bound and convergence theory of minimax, it proves the convergence of SGDA to a stationary point.\n3. Experimental results show the improvement of $f$-FERM over existing benchmarks.", "weaknesses": "1. This paper is missing a related reference called TERM (Tilted Empirical Risk Minimization) which also studies fairness.\n2. The main formulation (1) could be simplified. The f-divergence between the joint distribution and the product of marginals is called f-mutual information. See https://openreview.net/forum?id=ZD03VUZmRx for example and the references therein.\n3. SGDA for minimax optimization is highly inefficient and Theorem 2.2 has a really weak convergence result. How is it related to the experiments?\n4. The paper didn't discuss which $f$ (in f-div) is the best choice in detail.\n5. All the experiments are conducted on small-scale datasets.\n6. The definition of fairness is not clear to me. This paper considers both DP and EO, but which one is what f-FERM is trying to approach?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)