Responsible AI (RAI) Games and Ensembles
Authors: Yash Gupta
Runtian Zhai
Arun Suggala
Pradeep Kumar Ravikumar
Venue: NeurIPS 2023 poster (2023)
Keywords: Responsible AI
fairness
DRO
robustness

Abstract: Several recent works have studied the societal effects of AI; these include issues such as fairness, robustness, and safety.  In many of these objectives, a learner seeks to minimize its worst-case loss over a set of predefined distributions (known as uncertainty sets), with usual examples being perturbed versions of the empirical distribution. In other words, the aforementioned problems can be written as min-max problems over these uncertainty sets. In this work, we provide a general framework for studying these problems, which we refer to as Responsible AI (RAI) games. We provide two classes of algorithms for solving these games:  (a) game-play based algorithms, and (b) greedy stagewise estimation algorithms. The former class is motivated by online learning and game theory, whereas the latter class is motivated by the classical statistical literature on boosting, and regression. We empirically demonstrate the applicability and competitive performance of our techniques for solving several RAI problems, particularly around subpopulation shift.

Responsible AI (RAI) Games and Ensembles
Yash Gupta
Runtian Zhai Carnegie Mellon University rzhai cmu edu
Carnegie Mellon University yashgup2@cs. cmu.edu
Arun Suggala
Pradeep Ravikumar Carnegie Mellon University pradeeprØcs cmu. edu
Google Research arunss@google.c com
Abstract
Several recent works have studied the societal effects of AI; these include issues such as fairness, robustness, and safety. In many of these objectives, a learner seeks minimize its worst-case loss over set of predefined distributions (known uncertainty sets), with usual examples being perturbed versions the empirical distribution. In other words, aforementioned problems can be written as min-max problems over these uncertainty sets. In this work, we provide a general framework for studying these problems, which refer to as Responsible Al (RAI) games. We provide two classes of algorithms for solving these games: (a) game-play based algorithms,, and (b) greedy stagewise estimation algorithms. The former class is motivated by online learning and game theory, whereas the latter class motivated by the classical statistical literature boosting, and regression. We empirically demonstrate the applicability and competitive performance of our techniques for solving several RAI problems, particularly around subpopulation shift.
Introduction
In recent years, Al is increasingly being used in high-stakes decision-making contexts such as hiring. criminal justice, and healthcare. Given the impact these decisions can have people's 's lives, it is important to ensure these Al systems have beneficial social effects. An emerging line of work has attempted to formalize such desiderata ranging over ethics, faimess, train-time robustness, test-time or adversarial robustness, and safety, among others. Each of these forms rich sub-fields with disparate desiderata, which are sometimes collated under the umbrella of "responsible AI". Many organizations are increasingly advocating the use of responsible Al models [Microsoft, 2021, Google, 2020].
But how do we do so when the majority of recent work around these problems is fragmented and usually focuses on optimizing one of these aspects time (DRO [Namkoong and Duchi, 2017, Duchi and Namkoong, 2018]. GDRO [Sagawa et al.. 2019], CVaR [Zhai et al.. 2021a], Distribution Shift [Hashimoto et al., 2018, Zhai et al., 2021b])? Indeed optimizing for just one of these aspects has even been shown to exhibit adverse effects on the other aspects [Roh et al., 2020]. To address this, we study general framework that is broadly applicable across many of the settings above, and which we refer to as Responsible A/ (RAI) games. Our starting point is the recent understanding of a unifying theme in many these disparate problems, that learner seeks to minimize its worst-case loss over set of predefined distributions. For example, in fairness, we seek to perform well all sub-groups the data. robustness, we aim to design models that are robust to perturbations the training data the test distribution. This allows us set up zero-sum game between learner that aims to learn a responsible model and an adversary that aims to prevent the learner from doing so. In
The relevant code for this work can be found http::/gghhubb.comyyssgggupp///
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the general RAI game setting, this is computationally intractable game that need not even have a Nash equilibrium. To address this computational issue, we study a relaxation of the single predictor RAI game, which we term the ensemble RAI game, which can also be motivated as linearization of the original RAI game.
We note that our framework encompasses not only the responsible AI settings but also the setting of classical boosting. Drawing upon the insights from boosting, we provide boosting-based algorithms for solving responsible AI games. We provide convergence guarantees of our algorithms by relying on the connections between boosting and online convex optimization, two-player gameplay [Arora et al., 2012, McMahan, 2011 1, Bubeck, 2011] lI. We also conduct empirical analyses to demonstrate the convergence and utility of our proposed algorithms. Interestingly, the algorithms allow for plug-ane play convenience, with changes in the RAI settings requiring only simple changes to the algorithms. More importantly, we could consider intersections of different responsible Al considerations, which in turn can simply be incorporated into our algorithms. Finally, we also study the population risks of our algorithms certain important settings. We show a surprising result that for the case of binary classification with the 0/1 loss, the optimal predictor for a large class of RAI games is the same the Bayes optimal predictor, thus generalizing an emerging line of results demonstrating this for certain specific games [Hu et al., 2018]. Under such settings, solving the RAI game could nonetheless be helpful in finite sample settings (as also demonstrated in our experiments) since the RAI game serves to encode desiderata satisfied by the Bayes optimal classifier.
2 Problem Setup and Background
We consider the standard supervised prediction setting, with input random variable X E X C R output random variable Y E y, and samples S {(T,, 81) drawn from a distribution Paama over X' x y. Let Panta denote the empirical distribution over the samples. We also have a set H of hypothesis functions h X + y from which we wish to learn the best predictor. We evaluate the goodness of predictor via loss function é y x y + R, which yields the empirical risk: R(h) TE p... ((((z),)) v) where Ep (f(x,, v))
E.=1 f vk). Apart from having low expected risk, most settings require h to have certain properties, for example, robustness to distribution shift, fairness w.r.t subpopulations, superior tail performance, resistance to adversarial attacks, robustness in the presence of outliers, etc. We cast all these subproblems into umbrella term "Responsible AI". Each of these properties has been studied extensively in recent works, albeit individually. In this work, we attempt to provide general framework to study these problems.
2.1 Related Work
We draw our unified framework from seminal works over the past decade by responsible Al re- searchers on devising non-expected risk objectives, particularly min-mux problems, to ensure ML. models are responsible. These have resulted in multitude of different objectives (even for a single responsible AI desideratum such as fairness), and also multiple different sub-communities (so that fairness and multiple disparate robustness communities are relatively fractured), many (if not all) of which we combine within a single umbrella. There is emerging work on relating worst-case performance to invariance [Bühlmann, 2018]; in other words, we might be able to get approximate group invariance via minimizing an appropriately constructed worst-group risk and vice-versa.
constrained opti- et al., 2015, Gao and Kleywegt, 2022, Namkoong and Duchi, 2016, Ben-Tal et al., 201 I]. There have also been few prior works enforcing fairness constraints [Mandal et al., 2020]. To the best of our knowledge, there exists minimal prior work focusing on multiple desiderata once this regard.
RAI aspects as constraints. Many prior works have enforeed robustness
mization [Shafiezzadeh-Abade
Multi Objective Optimization. Several works have considered a multi-objective view of ensuring fairness in classifiers [Martinez et al., 2020, Oneto et al., 2018]. If used for multiple RAI objectives, there is usually overhead in choosing a model that achieves a good trade-off between various losses. Also, it is difficult to guarantee that the solution is robust to any of the involved aspects. Our framework guarantees a certain level of performance on each of the RAI aspects under consideration.
Distribution shift. [Koh et al., 2021] classifies distribution shift problems into two categories: Domain generalization, and subpopulation shift. In this work, we focus on the subpopulation shift problem, where the target distribution is absolutely continuous to the source distribution. It has two

---

main applications: fairness [Hashimoto et al., 2018, Hu et al., 2018, Sagawa et al., 2019, Zhai et al., 2021b] and long-tail learning (i.e. learning on caassimmallacee datasets) [Cao al., 2019, Menon et al., 2021, Kini et al., 2021].
Distributionally Robust Optimization (DRO). In DRO one aims to study classifiers that are robust to deviations of the data distribution. DRO has been studied under various uncertainty sets including f-divergence based uncertainty sets [Namkoong and Duchi, 2017, Duchi and Namkoong, 2018, Sagawa et al., 2019], Wasserstein uncertainty sets [Sinha et al., 2017, Gao et al., 2022], Maximum Mean Discrepancy uncertainty sets [Staib and Jegelka, 2019], more general uncertainty sets in the RKHS space [Zhu et al., 2020]. [Li et al., 2021a] evaluate model performance under worst-case subpopulations. Owing to its importance, several recent works have provided efficient algorithms for solving the DRO objective [Namkoong and Duchi, 2016, Qi et al., 2020, Kumar et al., 2023, Jin et al., 2021]. However, a lot of these techniques are specific to particular perturbation sets and are not directly applicable to the more general framework we consider in our work. Furthermore, in our work, we aim to learn an ensemble of models instead of a single model.
Boosting. Classical boosting aims to improve the performance of a weak learner by combining multiple weak classifiers to produce a strong classifier [Breiman, 1999, Friedman et al., 2000, Friedman, 2001, Freund and Schapire, 1995, Freund et al., 1996, Mason et al., 2000J. Over the years, a number of practical algorithms have been introduced such as AdaBoost [Schapire, 1999], LPBoost [Demiriz et al., 2002], gradient boosting [Mason et al., 1999], XGBoost [Chen and Guestrin, 2016], boosting for adversarial robustness [Zhang et al., 2022]. [Meunier al., 2021], [Balcan et al.. 2023], and holistic robustness [Bennouna and Parys, 2022]. The algorithms we develop for RAI games are inspired by these algorithms.
There are a number of fairness notions for algorithmic fairness, ranging from individual fairness [Dwork al., 2012, Zemel al., 2013], group fairness [Hardt et al., 201 6a, Zafar al., 2017], counterfactual fairness [Kusner et al., 2017], Rawlsian max-min fairness [Rawls, 2020, Hashimoto al., 2018] and others [Barocas et al., 2017, Chouldechova and Roth, 2018. Mehrabi et al., 2021]. Our framework includes the popular notion of minimax group fairness. It doesn't capture other notions of group fairness such as Demographic Parity, Equality of Odds, Equality of Opportunity.
Fairness.
Population RAI Risks. Several recent works have studied properties of the population risks arising in various responsible Al scenarios. Hu al. [2018] showed that the minimizer of population DRO risk (under general f-divergences) is the classical Bayes optimal classifier. Li et al. [2021b), Duchi and Namkoong [2018], Sinha et al. [2017] provided generalization guarantees for DRO risk under various divergence families ranging from f-divergences to Wasserstein perturbations.
3
RAI Games
In many cases, we do not wish to compute an unweighted average over training samples; due to reasons of noise, tail risk, robustness, and fairness, among many other "responsible Al" considerations. Definition (RAI Risks) Given a set of samples ((I;, )i)) we define the class of empirical RAI risks (for Responsible Al risks) as: Rw. (h) supwew, (f(xx) v), where Wn. An, is some set of sample weights (a.k.a uncertainty set), and E. (f 9)) Ei= w.f( yc).
Various choices of Wn give rise to various RAI risks. Table presents examples of RAI risks that are popular in MI.. Interestingly, classical problems such boosting are special cases of RAI risks. In this work, we rely on this connection to design mootting-inspired algorithms for minimizing RAI risks. More choices for Wn, can be obtained by combining the one's specified in Table using union, intersection, convex-combination operations. For example, if one wants models that are fair to certain pre-specified groups, and the same-time achieve good tail-risk, then one could choose W,, to be the intersection of Group-DRO and a a-CVaR uncertainty sets.
Given the empirical RAI risk Rw, (h) of a hypothesis, and set of hypotheses H, we naturally wish to obtain the hypothesis that minimizes the empirical RAI risk: minne Rw. (h). This can be seen as solving a zero-sum game.
Definition (RAI Games) Given a set of hypothesis H. and a RAI sample weight set Wn. the class of RAI games is given as: minse h maxwew, E,, (h(x),)).
We thus study RAI Games for the special cases above and for an arbitrary constraint set Wa.
3

---

Name
Wa.
Deseription
Empirical Risk Minimization
(Pam)
object of focus in most of ML/II
used for designing
A.. entire probubility simplex
Worst Case Margin
margin-boosting algorithms
[Warmuth et al., 2006, Bartlett et al., 1998]
Margin
(w: KL(w Parn) S pa)
AdaBoost [Freund and Schapire. 1995]
used in the design
a-Conditional Value Risk (CVaR)
(10: E As, w dn
used in Jaimess
[/hai et al., 2021a, Sagawa al., 2019]
various choices for D)
Distributionally Robust Optimization (DRO)
(wr: D(wil Paase) & pn)
have been studied
f-divergence [Duchi and Namkoong. 2018]
(Pun(Gi) Paza(Ga).... (Gm() Pan(G. (G.) is dist. of 7th group
used in group fairness, agnostic federated learning [Mohri al., 2019]
Group DRO
Table 1: Various ML/AI problems that fall under the umbrella RAI risks.
4 Ensemble RAI Games
In this section, we begin discussion about ensembles. In general, statistical caveat with Definition 2 is that good worst-case performance over the sample weight set W,, is generally harder, and for a simpler set of hypotheses H. there may not exist h H that can achieve such good worst-case performance. Thus is natural to consider deterministic ensemble models over H, which effectively gives more powerful hypothesis classes. Let first define RAI risk for such classifiers.
Definition 3 (Deterministic Ensemble) Consider the problem of classification, where y is a discrete set. Given a hypothesis class H, a deterministic ensemble is specified by some distribution Q E AH- and is given by: ( = arg maXyey En~oll(((x) = w). Correspondingly, we can write the deterministic ensemble RAI risk as Rw, (x)) maX E.g (hhe(ha)((2)) y)-
We discuss alternative definitions of deterministic ensembles in the Appendix. This admits class of deterministic RAI games:
Definition 4 (Deterministic Ensemble RAI Games) Given a set of hypothesis H. RAI sample weight set Wn. the class of RAI games for deterministic ensembles over H is given as:
min max (heee(hee:((x) QEAn wEW,
However, the aforementioned game is computationally less amenable because of the non-smooth nature of de-randomized predictions. Moreover, there are some broader challenges with RAI games given by Definitions 2 and 4. Firstly, they need not have Nash Equilibrium (NE), and in general, their min-max and max-min game values need not coincide. This poses challenges in solving the games efficiently. Next, in some cases, directly optimizing over the worst-case performance might not even be useful. For instance, [Hu et al., 2016, Zhai et al.. 2021a] show the pessimistic result that for classification tasks where when models are evaluated by the zero-one loss, ERM achieves the lowest possible DRO loss defined by some f-divergence or the c-CVaR loss, given that the model is deterministic. To this end, we consider the following randomized ensemble:
Definition 5 (Randomized Ensemble) Given hypothesis class H, randomized ensemble is specified by some distribution Q Au, and is given by: P(brant:((xr) = yl = T [h(()) = 3). Similarly, we can define its corresponding randomized ensemble RAI risk: Rrand:W, (Q) max En..)E..(((()... y))
We can then also define the class of ensemble RAI games:
Definition 6 (Randomized Ensemble RAI Games) Given a set of hypothesis H, RAI sample weight set Wn. the class of mixed RAI games is given as:
min max (())))) QEAR wCW,
This is a much better class of zero-sum games: it is linear both the hypothesis distribution P, as well as the sample weights w, and if the sample weight set W,, is convex, is convex-concave game. As shown below, under some mild conditions, this game has a Nash equilibrium which can be well approximated via efficient algorithms.

---

Proposition 1 Let H be parameterized by E θ S R', for convex. compact set Q and let W, be a comvex, compact set. Then mingeAn max Bn- maxwew, minqeAn (n--QBu((((2).))
The proposition follows as a direct consequence well known minimax theorems (Appendix D.3).
4.1 Going from Deterministic to Randomized Ensembles
To begin, we point out that what we want is a deterministic ensemble rather than a randomized ensemble. In fact, it can be seen that the deterministic ensemble in Definition 3 is a specific de- randomization of the randomized ensemble. It is such deterministic ensembles that we usually simply refer to ensemble predictors. But the RAI risk for the ensemble predictor is NOT equal to the ensemble RAI risk minimized by our desired game in Equation above for randomized ensembles. Thus, the ensemble RAI game might in general capture the ideal deterministic ensemble. this section, we study why and when might solving for a random ensemble is meaningful.
Binary Classification. Interestingly, for the very specific case of binary classification, can provide simple relationships between the risks of the randomized and deterministic ensemble.
Proposition 2 Consider the setting with = {-1, 1}. the zero-one loss and W, An. Then, Rw, (hang) = II I[w,, (brand:g) 2 1/2]..
See Appendix E.2 for a simple proof. In this case, we can also relate the existence of perfect deterministic ensemble ("boostability") to weak learning condition the set of hypotheses. Specifically, suppose H is boostable iff there exists proposition this equivalent to requiring that Rw. (Bramd:o) < 1/2.. We thus obtain:
ΔH Rw, (haeu)) 0. From the above
inf sup E.n.q((h(z).v)) 1/2 O sup inf (,,,((((())))) < 1/2 weW, REH
QEAN weW.
where the equivalence follows from the min-max theorem and the linearity of the objective in P. The last statement says that for any sample weights E Wn, there exists hypothesis h E H that has w- w-weighted loss at most 1/2. We can state this as a "weak-learning" condition on individual hypotheses in H. The above thus shows that for the specific case of y (-1,1), }. the zero-one loss Kyy,y/) = Hy # y'), and W., = A., we can relate boostability of H to weak learning condition on hypothesis within H.
General Classification But in general, do not have simple connections between Rw, (hacrQ) and Rw, (Arand:q). All we can guarantee is the following upper bound:
Proposition 3 Let qq 1/ mingg(n] maxyey P2(h(x;) = w). Then,
Rw. (harre) S To Rw. (hrmmd:))
See Appendix E.2 for a simple proof.
Corollary For binary classification, we have Typ S 2 and thus, we recover the well known bound Rw, (haer:) & 2Rw, (hrund:))
Remark These bounds might be loose in practice. Specifically, for the binary case, if Rw. (hramd:0) & 1 then we have Rw, (haer:)) = 0. To this end, prior work [Lacasse et al., 2006, Germain et al., 2015, Masegosa et al., 2020] have developed tighter bounds using second-order inequalities. We leave the analyses of these second-order RAI games to future work.
As such, can cast minimizing randomized RAI risk minimizing an upper bound the deterministic ensemble RAI risk. Thus, the corresponding randomized RAI game can be cast as relaxation of the deterministic RAI game. In the sequel, we thus focus on this randomized ensemble RAI game, which we will then use to obtain a deterministic ensemble. Following the bounds above, the corresponding deterministic ensemble risk will be bounded by the randomized ensemble RAI risk
5 Algorithms
In this section, we present two algorithms for solving the RAI game in Equation (1). Our first algorithm is motivated from online learning algorithms and the second algorithm is motivated from
5

---

greedy stepwise algorithms that have been popular for solving many statistical problems such as regression. For simplicity of presentation, we assume H is finite set. However, our results in the section extend to uncountable sets.
5.1 Methods
Game-play. In game play based algorithms, both the min and the max players are engaged in a repeated game against each other. Both players rely no-regret algorithms to decide their next action. It is well known that such procedure converges to a mixed NE of the game Cesa-Bianchh and Lugosi [2006]. In this work, we follow similar strategy to solve the game in Equation (I) (see Algorithm for the pseudocode). In the nd round of our algorithm, the following distribution w E W is computed over the training data points
W. +- argmiax WEW,
Σ E E(h" + 11" Reg(w)
(2)
This update is called the concave regularizer and 1 is the regularization strength. One popular choice for Reg(-) is the negative entropy which is given by Σ. we log w,. This regularizer is also used by AdaBoost, which popular boosting algorithm. In Appendix F.2. we provide analytical expressions for w" for various choices of W.. n. Reg(-). We note that the regularizer in the FTRL update ensures the stability of the updates; i.e., it ensures consecutive iterates do not vary too much. This stability is naturally guaranteed when W,, is strongly convex set (an example of a strongly convex set is the level set of a strongly convex function. See Appendix for formal definition and more details). Consequently, the regularization strength s could be set to this case, and the algorithm still converges to NE [Huang et al., 2017].
(FTRL) update. Here, Reg(-) is strongly
Once we have w², new classifier 1e is computed to minimize the weighted loss relative to w', and added to the ensemble. This update is called the Best Response (BR) update. Learning h in this way helps fix past classifiers' mistakes, eventually leading to ensemble with good performance.
Algorithm 1 Game play algorithm for solving Equation (1)
Input: Training data {z1, y:) } loss function é, constraint set W,, hypothesis set H, strongly concave regularizer R over WT. learning rates (1
for 1 T do
2: FTRL: w' +- argmax
()) + - -Re((w)
3: BR: h² < argminnee Eg (h(r))))
4: end for
5: return p== 1 ET
w', Q = Unif(h h7}
Greedy. We now take an optimization theoretic viewpoint to design algorithms for Equation (1). Let L(Q) denote the inner maximization problem of (I): L(Q) = max En, y). When L(Q) is smooth (this is the case when Wn, is a strongly convex set), one could use Frank-War Wolfe (FW) minimize The updates of this algorithm are given by
Q' -
(1- -1- (1-a')Q²+ a'G, where = argmin (Q, VQL(011) Q
Here, VoL(Q'-1) argmax Ep-ge 1 (b()())))))))))) v). This algorithm is known converge to minimizer of I()) at O(1/t) rate [Jaggi, 2013]. When L(Q) is non-smooth, we first need to smooth the objective before performing FW. In this work we perform Moreau smoothing [Parikh et al., 2014], which is given by
(Q) = max (((2)) v) + meRgg(w) wEW,
Here Reg(-) is strongly concave regularizer. If Reg(-) is 1-strongly concave, it is well known that (Q, is O(1/n) smooth. Once we have the smoothed objective, we perform FW to find its optimizer (see Algorithm 2 for pscudocode).

---

Relaxing the simplex constraint. We now derive slightly different algorithm by relaxing the simplex constraint on Q. Using Lagrangian duality we can rewrite mingEAN (2( the following problem for some À E R
min Ly (Q) + Σ Q(h). QE0
НEH
One interesting observation is that when W', is the entire simplex and when À = -1/2, we recover the AdaBoost algorithm. Given the practical success of AdaBoost, we extend general Wn. In particular, we set À = -1/2 and solve the resulting objective using greedy coordinate-descent. The updates of this algorithm are given in Algorithm
Remark 6 Algorithm 2 takes the step sizes {a')T=1 input. In practice, one could line search to figure out the optimal step-sizes, for better performance.
Algorithm 2 Greedy algorithms for solving Equation (1)
Input: Training data {(x, yr) Be))== loss function É, constraint set Wn, hypothesis set H, strongly concave regularizer R over W,, regularization strength 1, step sizes (a (a')
for to T do
2: G = argming (Q, Vob,(Q()))
3: FW: Q' + (1 - aa)) a'G Gen-AdaBoost: Q' - Q a
4: end for
5: return Q"'
We provide convergence rates for the algorithms below:
Proposition (Convergence Rates) Let ((((x),)) E [0,1] Wh Hx, y) E and Reg An TR. be 1-strongly concave function w.r.f norm 1--11. Let Q² be the output returned from running Algorithm I or 2 for T iterations. Let Dn be constant S.T. D maxx,yeW. [Reg(>) Reg(y))
1. (Gameplay) 1f =1, then Q" satisfies L(Q²) S minQ L(Q) + 2D 0
2. (Greedy) If line-search is performed for a', then Q" (FW or the Gen-AdaBoost update) satisfies L(Q") minq L(Q) + n ((1) )
We refer the reader to Appendix F.1 for a simple proof using existing theory on online convex optimization [McMahan, 2011, Jaggi, 2013]. Another useful insight is that Algorithms I and 2 are related to each other under special settings as shown by Appendix H.1.
Corollary Consider Reg(w: = EE= ue log ws and as the zero-one loss. Then, Algorithm
(v login) T
and Algorithm (line-search) achieve c- approximate NE with e as O
Weak Learning Conditions
might not be practical for H-player to play BR (Step 3: Algorithm
or correspondingly, find the best possible classifier every round (Step 2: Algorithm 2). Under weak learning conditions, we can indeed achieve (approximate) convergence when we only solve these problems approximately. See Appendix H.2 for more details.
6 Generalization Guarantees
In this section, we study the population RAI risk and present generalization bounds which quantify the rates at which empirical RAI risk converges to its population counterpart.
6.1 Population RAI Games
Recall, the empirical RAI risk optimizes over all sample re-weightings E W,, that lie within the probability simplex An, Thus it's population counterpart optimizes over distributions that are absolutely continuous with respect to the data distribution Pamn:
Rw (h)
sup
Ep (e((((()))))) v)].
P.P Pents d
J.P.

---

Following [Shapiro et al., 2021], we can rewrite this as follows. Suppose we use Z = (X,Y) E == X' x V. so that P. Pamta are distributions over Z. We then define ln : + R as (n(2) = (()(z).)).
We can then write the population RAI risk as (see Appendix G for a proof):
Rw (h)
sup r: Z (())dPPa())=
E P (z))
For classification, define the RAI-Bayes optimal classifier as: Qiv = arg ming Rw (Q). Here, the minimum is w.r.t the set of all measurable classifiers (both deterministic and random). This is the "target" classifier we wish to learn given finite samples. Note that this might not be the same as the vanilla Bayes optimal classifier: Q arg ming E [[))], which only minimizes the expected loss, and hence may not satisfactorily address RAI considerations.
We now try to characterize the RAI-Bayes optimal classifier. However, doing this requires bit more structure on W. So, in the sequel, we consider constraint sets of the following form:
f (:(r(=))dPPamm(() S c, E [m]]
W r 2 - T
(5)
where we assume that gi IR+ i E [mm] convex. Note that this choice of W encompasses broad range of RAI games including DRO with f-divergence, CVaR, soft-margin uncertainty sets. Perhaps surprisingly, the following proposition shows that the minimizer of population RAI risk is nothing but the vanilla Bayes optimal classifier.
Proposition 9 (Bayes optimal classifier) Consider the problem of binary classification where O' = [-1,-11. Suppose ((h(x). y) o(yh(z)) for some ø R + [0, oo) which is either the 0/1 loss, or a convex loss function that is differentiable at O with o' (0) < O. Suppose the uncertainty set W is specified in Equation (5). Moreover, suppose {gi i==...m are convex and differentiable functions. Then, the vanilla Bayes optimal classifier is also a RAI-Bayes optimal classifier.
Remark 10 In the special case of m = 1 in Equation (5), we recover the result of [Hu et al., 2018]. However, proof is much more elegant than the proof of [Hl et al., 2018], and relies the dual representation of the population RAI risk.
One perspective of the above result is that the vanilla Bayes optimal classifier is also "responsible" as specified by the RAI game. This is actually reasonable in many practical prediction problems where the label annotations Why then might we be interested in the RAI risk? One advantage of the RAI risks is in finite sample settings where the equivalence no longer holds, and the RAI risk could be construed as encoding prior knowledge about properties of the Bayes optimal classifier. We also note that the above equivalence is specific for binary classification.
actually derived from humans, who presumably are also responsible.
6.2 Generalization Guarantees
Our generalization bounds rely on the following dual characterization of the RAI population risk. Proposition 11 Suppose the uncertainty set W is as specified in Equation (5). Then for any hypothesis h, the population RAI risk can be equivalently written as
Rw (h)
inf E (2(((()) + X20.7
Σ As +T,
where G is the Fenchel conjugate of Gx(!) E (t).
We utilize the above expression for Rw (h) to derive the following deviation bound for Rw, (h).
Theorem 12 Consider the setting of Proposition 11. Suppose (g: are convex and differen-
tiable functions. Suppose (2) E [0, B for all h E H, z E Z. Suppose, for any distribution P Pata the minimizers (X*,"* (5") of Equation (6) lie in the following set: E = T(),T): ||>*|| < A, |T" < T}.
Moreover, let's suppose the optimal X* for Pasta is bounded away from 0 and satisfies min; X; A.
Let G, L, be the range and Lipschitz constants of G
aG (z - T) 0(1,))
G = sup GB - 7) - -G)(-)) L==
sup (A Amni, 2,24
(ATTEE
2
8

---

For any fixed h E H, with probability at least 1 - 2
(h) Rw. (b)) I 10m 1/2 G/2G( m mlog(nT.)..
Given Theorem 12, one can take a union bound over the hypothesis class H derive the following uniform convergence bounds.
Corollary 13 Let (HH, 6, (2))) be the covering number of H in the sup-norm which is defined as (2)] = supsez |1(2)], Then with probability at least 1 - N (H,, ens Il -11=)=)))
the following holds for any h E H: |Rw (h) -Rw, (h)) S 30n G/ m log(n Here
en = =n= =n=nn///// m log(nI.).
The above bound depends on parameters (A*,T",G ,, which specific to the constraint set W. To instantiate it for any W one needs to bound these parameters. We note that our generalization guarantees become sub-optimal as A 0. This is because the Lipschitz constant L could potentially get larger as X approaches the boundary. Improving these bounds is an interesting future direction. Remark 14 We note that aforementioned results results follow from relatively stringent assumptions. Exploring the impact of relaxing these assumptions is an interesting direction for future works.
7 Experiments
In this section, we demonstrate the generality of proposed RAI methods by studying one of the most well-studied problems in RAI i.c. the case of subpopulation shift. Given a large number of possible W. we acknowledge that this is not a complete analysis, even with respect to the problems that live within the minimax framework. Instead, we aim display convergence, and superior performance over some seminal baselines of this task. We conduct experiments on both synthetic and real-world datasets. Please refer Appendix for details on synthetic experiments. We consider a number of responsible AI settings, including subpopulation shift, in the domain-oblivious (DO) setting where we do not know the sub-populations [Hashimoto et al., 2018 8, Lahoti et al., 2020, Zhai et al., 2021a] the domain-aware (DA) setting where we do [Sagawa et al., 2019], and the partially domain- aware (PDA) setting where only some might be known.
souug-and-laay generality,
Datasets & Domain Definition. We use the following datasets: COMPAS [Angwin et al., 2016], CIFAR-10 (original, and with a class imbalanced split [Jin et al., 2021, Qi et al., 2021]) and CIFAR- 100. See the Appendix for more details on our datasets. For COMPAS, we consider race ( (White vs Other) and biological gender (Male vs Female) as sensitive attributes. This forms four disjoint subgroups defined by these attributes. In the PDA setting, we partition only across the attribute race while training, but still run tests for all four subgroups. On CIFAR-10, class labels define our 10 subpopulations. Similarly as above, for the PDA setting, we make 5 super-groups of two classes each. On CIFAR-100, class labels define our 100 subpopulations. For the PDA setting, we make 20 super-groups, each consisting of five classes.
Baselines. We compare our method against the following baselines: (a) Deterministic classifiers trained on empirical risk (ERM) and DRO risks, particularly the quasi-online algorithm for Group DRO [Sagawa et al., 2019] (Online GDRO), and ITLM-inspired SGD algorithm [Zhai al., 2021b, Shen and Sanghavi, 2018] for x2 DRO (SGD (x²)) (b) Ensemble models AdaBoost [Schapire, 1999]. Note that the purpose of our experiments is to show that we can match baselines for specific single desideratum (e.g. worst-case sub-population) while allowing for learning models that can solve multiple responsible Al desiderata at the same time, for which we have existing baselines.
Proposed Methods We focus on Algorithm 2 and refer to FW and Gen-AdaBoost updates as RAI-FW and RAI-GA, respectively. Moreover, our implementations include the following alterations: We track the unregularized objective value from Equation| for the validation set, and whenever it increases we double the regularization factor 7). which we find can improve generalization. * We also use this objective w.r. the normalized Q' to perform a line search for the step size a. For the FW update, our search space is ball around at round while for GA, we search within (0,1). 1).
Base Learners & Training. Training time scales linearly with the number of base learners. Inference, though, can be parallelized if need be. We usually find training on 3-5 learners is good enough on all scenarios explored in the paper. We defer further details of our base learners and hyperparameter choices to the Appendix.

---

Constraint sets W.. For RAI algorithms, we use the following constraint sets: Domain Oblivious (DO): We use the x DDO constraint set to control for worst-case subpopulations. Domain Aware (DA): We use the Group DRO constraint set as the domain definitions are known. Partially Domain-Aware (PDA): We use novel set W,, which is the intersection over Group DRO constraints over the known domains and x² constraints to control for unknown group performance. For baselines, we use AdaBoost and SGD(X") for the DO setting. Online GDRO serves as our baseline for both DA and PDA settings, where the algorithm uses whatever domain definitions are available.
Table 2: (Table 1 in the paper) Mean and worst-case expected loss for baselines, RAI-GA and RAI-FW. (Complex) indicates the of larger models. Constraint sets W,, indicated in (). Each experiment is carried out over three random seeds and confidence intervals are reported.
Setting
Algorithm
COMPAS
CIFAR-10 (Imbalance))
CIFARIO
CIFARIOU
Avenge
Worst Group
Average
Wonst Class
Average
Worst Class
Avenae
Worst Class
1X0
ERM RAI-GA (x3)
102
10.1
10.3
30.4
8.3
10.5
25.2
64.0 _07
(Complex)
3123:102
31.2 10.2
11.7 10.4
29.0 10.3
8.2 -0.1
19.0 10.1
25.6 10.4
56.8 008
RAL-PW (x*)
31.2+011
31.4
11.9
29.1 +0.2
8.0 -0.3
15.4 +04
25.4 +0.2
58.0 58.0-1.1
ERM
32.1 1:03
34.6 10.4
14.2 10.1
33.6 10.3
11.4 20.4
27.0 10.1
27.1 10.
66.0 =1.1
AdaBoost
31.8=04
32.6 +1.3
15.2 =0.2
40.6 #0.2
12.0 =0.1
28.7 #0.3
28.1 #0.2
72.2 =1.2
DO
SGD (x")
10.2
10.3
10.4
11.3 20.3
10.1
27.4
65.9 =1.2
RAI-GA (x")
30.5
33.2 10.3
14.0 10.1
32.2 10.
10.8 10.4
25.0 1.0.2
27.4 10.4
65.0 _0..8
RAL-FW
31.6
32.5 401.5
13,9 20.1
32.6 40.3
10.9 20.4
23,4 #0.22
27.5
63.8 =0.6
DA
RAL-GA (Group)
Online GDRO
31.7
32.0=0.1
32.7 +0.1
32.2 10.3
13.1 20.2
13.0 =0.3
26.6 4012
27.3 +0.4
11.2 20.1
11.5 =0.1
22.4 +0.2
21.7 20.3
27.4 +0.2
27.3 2001
57.0 =0.5
56.6 =1.1
RAI-FW (Group)
32.1:102
11.4 20.3
100.1
27.9
52.9
PDA
Online GDRO
31.5
32.7 #022
13.4 =0.1
32.2 4:12
11.3 202
25.2 #0.1
27.7 2012
64.0 =0,8
RAI-GA (Group
30.4
32,9 10.2
13.3
30,1 10.1
10.8 202
23.7 10.2
27.5 10.1
62.5 -0.6
RAL-FW (Group xxx
31.8 202
32.3 10.11
13.5 10.3
29.4 10.3
11.2 20.4
24.0
1.0.2
27.9 10.3
58.9 =07
Results and Discussion. We run our methods and baselines under the settings described above and report the results in Table 2. As such, we can make the following observations:
1. RAI-FW and RAI-GA methods significantly improve the worst-cass performance with only few base learners across all datasets in all three settings, while maintaining average case performance. Moreover, For seemingly harder tasks i.c. a large gap between average and worst-case performance, the algorithms are able to improve significantly over the baselines. For example, we observe a 5% improvement in performance in the case of CIFAR-100.
2.
The plug-and-plen framework allows for several different Wn, to enhance various responsible Al qualities at once. We demonstrate this with the partial domain aware setting (PDA), where the performance lead widens, indicating that RAI is able jointly optimize effectively for both known and unknown subpopulations while Online GDRO suffers from some of the group information being unknown. In practice, one can construct many more novel sets Wn.
3. Although bigger (complex) models exhibit stronger performance than RAI ensembles, there are several caveats to this observation. Firstly, these models are 10-15 times larger than our base models. This limits their use w.r.t both training & inference compute required. However, RAI ensembles utilize a small number of much smaller models which can be individually trained quite casily. Even with these large models as base learners, constructing ensembles exhibits a perfor- mance boost, indicating that our framework is able to "boost" models of varying complexities.
8 Conclusion
Under the umbrella of "responsible AI", an emerging line of work has attempted to formalize desiderata ranging over ethics, fairness, robustness, and safety, among others. Many of these settings (Table 1) can be written as min-mat problems involving optimizing some worst-case loss under set of predefined distributions. For all the problems that can be framed as above, we introduce and study general framework, which we refer to as Responsible AI (RAI) games. Our framework extends to classical boosting scenarios, offering boosting- convergence guarantees. We propose practical algorithms to solve these games, as well as statistical analyses of solutions of these games. We find that RAI can guarantee multiple responsible Al aspects under appropriate choices of uncertainty sets.
algorithms for RAI games alongside proven
10

---

Acknowledgements
We acknowledge the support of DARPA via HR001 12020006, and NSF via IIS-19099 1909816.
References
Microsoft.
Microsoft. http:///ww...cootttooooooaaa/aaa ai, 2021. Ac-
cessed: Date Accessed.
Google. Google. https: /aai http://ccwgaataaaa/////////////a http:///sspppaaallal//////aaaaaa Accessed: Date Accessed.
2020.
Hongseok Namkoong and John C Duchi. Variance-baseds regularization with convex objectives. Advances in neural information processing systems, 30, 2017.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv: /80.0008/0 2018.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv: /91 /. 1008311, 2019.
Runtian Zhai, Chen Dan, Arun Suggala, J Zico Kolter, and Pradeep Ravikumar. Boosted evar classification. Advances in Neural Information Processing Systems, 34:21860-21871, 2021a.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. International Conference On Machine Learning, 2018.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Doro: Distributional and outlier robust optimization. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12345-12355. PMLR, 18-24 Jul 2021b. URL httpp::/pproceeeeeeeeee zhai21a. html.
mlr press/v139/
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fr-train: A mutual information- based approach fair and robust training, arXiv preprint arXiv: Arxiv-2002.10334 2020.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of computing. 8(1):121-664, 2012.
Brendan McMahan. Follow-the-rrgularizedd-eedddd and mirror descent: Equivalence theorems and
11 regularization. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 525-533, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Sébastien Bubeck. Introduction to online optimization. Lecture notes, 2:1-86, 2011.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pages 2029- 2037. PMLR, 2018.
Peter Bühlmann.
Invariance, causality and robustness. arXiv preprint arXiv: 1812.08233, 2018.
Soroosh Shafieezadeh-Abadeh Peyman Mohajerin Esfahani, and D. Kuhn. Distributionally robust logistic regression. Neural Information Processing Systems, 2015.
Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 2022.
Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust
optimization with f-divergences. In Neural Information Processing Systems, 2016. URL. https: //api www.aticscoooola...ooooooccccc org.org///oooo Werg/CorpusID::0/e 7481496.

---

Aharon Ben- Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Advanced Risk & Portfolio Management@) Research Paper Series, 2011. URI.tttps:/aap http:ttpss//ppp..senaiaiccccci semanticschola.. org/Corpus ID: 7617933
Debmalya Mandal, Samuel Deng, Suman Jana, Jeannette Wing, and Daniel J Hsu, Ensuring faimesss beyond the training data. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18445-18456. Cur- ran Associates, Inc., 2020. URL https: pppo:eeep///oooedingg.s.m innuureeeeennnneererrrpps neurips....... wwtpppcccfcciciaccccee www.efillepppeeeeee /apeer//ppr////// (0000///1//659000077119944422222
Paper.ppa
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairnsss: A multi objective perspective. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6755-676660 6764. PMLR, 13-18 Jul 2020. URL https: /ttp:ee//proccedinggs mlr pat.spress//// martinez20a. html.
L. Oneto, Michele Donini, Amon Elders, and M. Pontil. Taking advantage of multitask learning for fair classification. AAAI/ACM Conference on AI, Ethics, and Society, 2018. doi: 10.1 10.1145/3306618 3314255.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with labell margin loss. Advances in Neural Information Processing Systems, 32:1567-1578,, 2019.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterrizaton. In Thirty-Fiith Confer- ence on Neural Information Processing Systems, 2021.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10577 2017.
Rui Gao, Xi Chen, and Anton J Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research, 2022.
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kemel methods. Advances in Neural Information Processing Systems, 32, 2019.
Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, and Bernhard Schölkopf. Kernel distributionally robust optimization. arXiv preprint arXiv:2006.0696 2020.
Mike Li, Hongscok Namkoong, and Shangzhou Xia. Evaluating model performance under worst-case subpopulations. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021a. URL https : //openrevie net/ drrumiid-mehzxAdyyttt
Qi Qi, Yi Xu, Rong Jin, Wotao Yin, and Tianbao Yang. Attentional biased stochastic gradient for imbalanced classification. arXiv preprint arXiv:2012.06951, 2020.
Ramnath Kumar, Kushal Majmundar, Dheeraj Nagaraj, and Arun Sai Suggala. Stochastic re-weighted gradient descent via distributionally robust optimization. arXiv preprint arXiv:23066.0922, 2023.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman URI. https:
Vaughan, editors, Advances in Neural Information Processing Systems, 2021. // //openreview net/ wowooooddgggggiiiiii
12

---

Leo Breiman. Prediction games and arcing algorithms. Neural computation, 11(7))1493-1555 -51777 1999.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. Additive logistic regression: statistical view of boosting (with discussion and rejoinder by the authors). The annals of statistics, 28(2):
337-407, 2000.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of
statistics, pages 1189-1232, 2001.
Yoav Freund and Robert E Schapire. A desicion-theorett generalization of on-line learning and an application to boosting. In European conference on computational learning theory, pages 23-37. Springer, 1995.
Yoav Freund, Robert E Schapire, et al. Experiments with new boosting algorithm. In ieml, volume 96, pages 148-156. Citeseer, 1996.
Llew Mason, Jonathan Baxter, Peter L Bartlett, and Marcus R Frean. Boosting algorithms as gradient descent. In Advances in neural information processing systems, pages 512-518, 2000.
Robert E Schapire. The boosting approach to machine learning: An overview. In MSRI workshop Nonlinear Estimation and Classification, 1999.
Ayhan Demiriz, Kristin Bennett, and John Shawe- Taylor. Lpboost: boosting algorithm with linear programming. In International Conference on Machine Learning, pages 143-150. AAAI Press, 2002.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999. URL
newreeedddddnnnnnnne.seeeeee.ee cc/paper. /ttp://ee//999/111//9/////20 11119////00088888866666666688863 Paper .df.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. arXiv preprint arXiv: Arxiv-1603.0255, 2016.
Dinghuai Zhang, Hongyang Zhang, Aaron Courville, Yoshua Bengio, Pradeep Ravikumar, and Arun Sai Suggala. Building robust ensembles via margin boosting. In International Conference on Machine Learning, pages 166699226699 PMLR, 2022.
Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, and Yann Chevaleyre. Mixed nash equilibria in the adversarial examples game. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings Machine Learning Research, pages 7677-7687. PMLR, 18-24 Jul 2021. URL stttps:/pproceedingg mlr. mlr. M.rrpress/vv33 meunier211 html.
Maria-Florina Balcan, Rattana Pukdee, Pradeep Ravikumar, and Hongyang Zhang. Nash equilibria and pitfalls of adversarial training in adversarial robustness games. In International Conference on Artificial Intelligence and Statistics, pages 9607-9636. PMLR, 2023.
M. A. Bennouna and Bart P. G. Van Parys. Holistic robust data-driven decisions. ARXIVOOR,, 2022. doi: 10.48550/arXiv.2200 .09560.
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, pages 214-226, 2012.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference machine learning, pages 325-333 PMLR, 2013.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in neural information processing systems, 29, 2016a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreat- ment. Proceedings of the 26th international conference on world wide web, pages 1171-1180. 2017.
13

---

Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
John Rawls. A theory of justice: Revised edition. Harvard university press, 2020.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness machine learning. Nips tutorial, 2017, 2017.
Alexandra Chouldechova and Aaron Roth. The frontiers of faimess in machine learning. arXiv preprint arXiv:1810.0883 2018
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1335 2021.
Mike Li, Hongseok Namkoong, and Shangzhou Xia. Evaluating model performance under worst-case subpopulations. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 17325-17334, Curran Associates, Inc., 2021b. URL httpss://proceediiggs neurips.. wttccc/ppppa.... pappr_fillss____pppppppppppppp_e files/ Pffer.ddf..
Manfred K Warmuth, Jun Liao, and Gunnar Rätsch. Totally corrective boosting algorithms that maximize the margin. Proceedings of the 23rd international conference on Machine learning. pages 1001-1008, 2006.
Peter Bartlett, Yoav Freund. Wee Sun Lee, and Robert E Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 1998.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- lional Conference on Machine Learning, pages 4615-4625. PMLR, 2019.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? International Conference On Machine Learning, 2016.
Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. Pac-bayes bounds for the risk of the majority vote and the variance of the gibbs classifier. Advances in Neural information processing systems, 19, 2006.
Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: From a pac-bayesian analysis learning algorithm. arXiv preprint arXiv: arXiv: 003.08829 2015.
Andrés Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Second order pac-bayesian bounds for the weighted majority vote. Advances Neural Information Processing Systems, 33: 5263-5273, 2020.
Nicolo Gesa-Bianchs and Gabor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Ruitong Huang, Tor Lattimore, András György, and Csaba Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. The Journal of Machine Learning Research, 18(1):5325-5355 2017.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International PML.R.R.R..RR conference on machine learning, pages 427-435. PMLR, 2013.
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimization, 1 (3):127-239, 2014.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic program- ming: modeling and theory. SIAM, 2021.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. Advances in neural information processing systems, 33:728-7400 2020.
14

---

Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and its biased against blacks. ProPublica, May 2016. URI. https://wwt machine-bias-ries -sss-s---s----sssseee----------. in- -tt--mma---eeeeenciiin
http:s///ww.ppppbliccc. propublica. org/ hrggrrticl/////
Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for a class of distributionally robust optimization with non-convex objectives. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 10067-10080, Curran Associates, Inc., 2021. URL https: http://///occecces/eeee neurips. cc/pcc/pppcp/cccccccccccc f wiweeieeaaaaeeeeeee pttps//pppp///////////. 1e33ar999bb299111111122222261219 Papere-appppppppep pdf.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. International Conference On Machine Learning, 2018.
Nidhi Kalra and Susan M. Paddock. Driving safety: How many miles of driving would it take demonstrate autonomous vehicle reliability? Transportation Research Part A: Policy and Practice, 94:182-193, 2016.
Andreas Fuster, Paul Goldsmith-Pinkhamm, Tarun Ramadorai, and Alexander Walther. Predictably unequal? the effects of machine learning credit markets. Social Science Research Network, (3072038), 2018.
Xinsong Ma, Zekai Wang, and Weiwei Liu. On the tradeoff between robustness and faireess. In S. Koyejo, S. Mohamed, Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 26230-26241, Curran Associates, Inc., 2022. URL https/////pp neurips weurips.cc/paper files/ ltteaeeelleeeeeeeeeeeeeeeee /apee////2////ell abbobbeecesss77ss11lldd.22222222 Cowaaapprrroooeeeeeeeeee pdf.
Anastasia Chan. Gpt-3 and instructgpt: technological dystopianism, utopianism, and "contextual" perspectives ai ethics and industry. Al and Ethics, 3(1):53-64, 2023.
Emily M Bender, Timnit Gebru, Angelina McMillan-Main Major, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 610-623, 2021.
Christos Louizos, Kevin Swersky, Yujia Li, M. Welling, and R. Zemel. The variational fair autoen- coder. International Conference on Learning Representations, 2015.
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in super- vised learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016b. URL https: https::/pproceeding. www.riiiininnnnnnnneeeeeeeeeieee newrips.u.... wttpsscccpppp.pppeeeeee http:/pppr_ffll/ppppeeeeeeeeeeee http///llee//ppp///////leee att.://r.e.2eddefeeeeeee22222e2
Paper. .pff.
Haohan Wang, Zexue He, Zachary Chase Lipton, and E. Xing. Learning robust representations by projecting superficial statistics out. International Conference on Learning Representations, 201 8.
Sravanti Addepalli, Anshul Nasery, R. Venkatesh Babu, Praneeth Netrapalli, and Prateek Jain. Learning an invertible output mapping can mitigate simplicity bias in neural networks. arXiv preprint arXiv: 2210.01360, 2022.
Junbum Cha, Kyungiae Lee, Sungrae Park, and Sanghyuk Chun. Domain generalization by mutual- information regularization with pre-trained models. European Conference on Computer Vision, 2022. doi: (0-485500arXiv.2203.1777
Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2016. doi: 10.1561/ 2400000013,
Kartik Gupta, Arun Sai Suggala, Adarsh Prasad, Praneeth Netrapalli, and Pradeep Ravikumar. Learning minimax estimators via online learning. ARXIV.ORG, 2020.
Jonathan Michael Borwein. A very complicated proof of the minimax theorem. 2016.
15

---

Abraham Wald. Generalization of theorem by neumann conceriin zero sum two person games. Annals of Mathematics, 46:281, 1945.
Stephen Simons. Minimax theorems and their proofs. 1995.
TES Raghavan. Zemo-sum two-person games. Handbook of game theory with economic applications, 16735-768, 1994.
Andrew Cotter, Maya Gupta, and Harikrishna Narasimhan. On making stochastic classifiers deter- ministic. Advances in Neural Information Processing Systems, 32, 2019.
Jimmy Wu, Yatong Chen, and Yang Liu. Metric-fair classifier derandomization. In International Conference on Machine Learning, pages 23999 240166. PMLR, 2022.
Brendan McMahan. A survey algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 18(1):11773116, 2017.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
TTrrell Rockafellar. Convex analysis. Number 28. Princeton university press, 1970.
Peter L Bartlett Michael I Jordan, and Jon D McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, (0(44))138--1555 2006.
Ambuj Tewari and Peter I. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(5), 2007.
Martin Wainwright. High-dimensions statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Robert M. Freund and Paul Grigas. New analysis and results for the frank-wolfe method.
Mathematical Programming, 155:199-230, 2014. doi: 10. 10.1007744010074444-0111166 URL com/ aataicletlleeo 100701000000000440000000000 08844-0881-6668 04 html.
httt:://linnssppinnee
Sergey Zagoruyko and N. Komodakis. Wide residual networks. British Machine Vision Conference, 2016. doi: 10.5244/C.30.77.
16

---

A Broader Impact
18
Limitations
18
C Terminology and Notation
19
C.I Terminology
19
C.2 Notation
19
D Background
19
D.I Two Player Zero-sum Games
19
D.2 Online Learning...
20
D.3 General Minimax Theorems (Proof of Proposition 1)
21
Ensemble RAI Games
E.1
Alternative Definitions: Deterministic Ensembles
E.2
Proofs
21
Algorithms
22
F.1
Convergence Rates
22
F22 Closed Form Updates for different uncertainty sets
23
F3 Proof of Corollary 8
24
G Generalization
24
G.1 Population Risk
................................
24
G.2 Generalization Guarantees
................................
26
G.3 Proof of Corollary 13
27
H Algorithms: Further Discussion
28
H.1 Equivalence Conditions for RAI Algorithms (1 and 2)
28
H.2 Weak Learning Conditions
28
I
Experiments
29
L1
Setup
29
I.2
Further Details for Section
30
1.3
Interesting Observation: Boosting Robust Learners
30
1.4
Synthetic Datasets
17

---

A Broader Impact
Responsible AI has become an important topic as ML/AI systems increase in scale, and are being deployed in a variety of scenarios. Models not optimized for responsible facets can have disastrous consequences [Kalra and Paddock, 2016, Angwin al., 2016, Fuster et al., 2018].
Our research promotes the principles of Responsible Al (RAT), encompassing ethics, faimness, and safety considerations. By providing framework to consider these simultaneously, this research could help prevent scenarios where optimizing for one aspect unintentionally compromises another [Ma et al., 2022], mitigating the risk of creating biases vulnerabilities in Al systems.
We also address the fragmentation in recent work around Responsible AI. The suug-and-llay nature of approach allows for the easy adaptation of algorithms for different Responsible Al considerations. This adaptability could lead to more practical and user-frienan euer-friendly tools for implementing RAI across different applications.
Numerous ML models like Large language models, (GPT-3, GPT-4), are rapidly transforming numerous domains, including natural language processing, data analysis, content creation, and more. Given their remarkable ability to generate human-like text, they can be used to construct narratives, answer queries, even automate customer service. However, with such capabilities come significant responsibilities, as these models can inadvertently perpetuate biases, misinformation, or harmful content if not correctly regulated. Therefore, ensuring the responsible behavior of these models is crucial [Chan, 2023, Bender et al., 2021]. Our research presents a general framework that can be pivotal in the responsible design of such large language models.
B Limitations
We now identify some limitations of our current work, along with corresponding future directions.
To more concretely establish the empirical superiority of our optimization techniques, more experiments involving large over-parametrized models need to be conducted.
The proposed generalization bounds not tight for all risks. A more careful analysis would be needed for such a generalization.
Our framework only handles uncertainty sets that are supported on the training data. It'd be inter- esting to generalize framework further to support other uncertainty sets based Wasserstein divergences that are not necessarily supported on the training data.
Finally, the presence of outliers can often destabilize training of large models[Zhai et al., 2021b]. However, our current framework assumes the training data is un-corrupted. In future, aim to extend our framework to support corruptions in the training data.
We note that our framework can also be extended to the problem of adversarial test-time robustness where there is an adversary corrupting the inputs sent to the model during inference. Let A(x) be the set of perturbations that the adversary can add to input x. The uncertainty set in this case contains distributions supported on ((x/, ./) 3xx, y) E Pasta such that x' E x A(x), y
Our framework primarily covers RAI aspects which can written minmax problems. Here provide some other notions of RAI which our framework does not directly cover.
Fairness: Various notions of fairness have been studied by the MI. community. While our frame- work captures minimax group fairness, it doesn't capture other notions of group fairness such as Demographic Parity [Louizos et al., 2015], Equality of Odds, Equality of Opportunity [Hardt et al., 2016b]. Our framework doesn't capture individual fairness notions.
Robustness: While our framework covers group robustness and certain forms of distributional robustness, it doesn't 't cover robustness to Wasserstein perturbations and other (un)structured distribu- tion shifts often studied in the domain generalization community [Wang et al., 2018, Addepalli et al., 2022, Cha et al., 2022].
18

---

C Terminology and Notation
C.1 Terminology
Strongly Convex Sets A set A is X-strongly convex w.r. norm || if, for any I, y E A, [0,1], the || norm ball with origin y (1 y and radius 7(1 >) y /2 lies lies in A.
f-divergence For any two probability distributions P. Q, f-divergence between P and Q is defined as (EP Here f RR+ + a convex function such that f 0.
C.2 Notation
Table 3: Notation
Symbol
Description
X
Input Random Variable
X
Input Domain
Y
Output Random Variable
y
Output Domain
Z
Sample Random Variable (X,Y)
2
Sample Domain X y
S
Sample Set
Patta
Data Generating Distribution Empirical Distribution (Uniform) over S
Panta
H
Set of Hypothesis
Q
Distribution over Hypothesis from Any given hypothesis
h
hrand:Q
Randomized Ensemble given by Q
De-randomizeedDettrmiiii Classifier corresponding Arand; Loss Function
R(h)
Empirical Risk of h Set of allowed sample weights (aka Uncertainty Set)
Wn
Rw, (h)
Empirical RAI Risk of Population RAI Risk of h
Rw(H (h)
Rrand; (Q)
Randomized Ensemble RAI Risk
K ((plla)
KL-divergence Metric between and
G
Subpopulation/Domall i Any given regularizer function
Reg
D Background
D.1 Two Player Zero-sum Games
Consider the following game between two players. One so-called "row player" playing actions H, and the other "column player" playing actions E Z. Suppose that when the players play actions h, z respectively, the row player incurs a loss of [[h, 2) E R, while the column player incurs loss of -1(h, 2). The of the losses for the two players can be seen be equal zero so such a game is known as a two-player zero-sum game. It is common in such settings to refer to the gain 1(h, z) of the column player, rather than its loss of -1(h, z). Both players try maximize their gain/minimize their loss.
It is common in game theory to consider lincarized game in the space of probability measures, which is in general better behaved. To set up some notation, for any probability distributions P,, over H. and P. over Z, define:
((P P.) Ep,.P, P. (h,,2)
19

---

Nash Equilibrium A Nash Equilibrium (NE) is a stable state of a game where no player can gain by unilaterally changing their strategy while the other players keep theirs unchanged. two-player zero-sum game, Nash Equilibrium is pair of mixed strategies (h", =²) satisfying
sup ((h" 2) - u(h", 2²) S inf =EZ
(h, 2")
hell
Note that whenever pure strategy NE exists, the minimax and maximin values of the game are equal each other:
inf sup [(h, 2) = 1(h" =²") = sup inf 1(h, 2) NEH =EZ
=EZ REH
What often exists is mixed strategy NE, which is precisely a pure strategy NE of the linearized game. That is, (Ph. P2) is called mixed strategy NE of the zero-sum game, if
I(P) P.) ((P P.) z inf P.EP3
sup
((Pn:PP)
PAEPH
For this paper, Q = Ph, 1 = P. AH = PH and W, = Pz.
c-Approximate Nash Equilibrium An c-approximate Nash Equilibrium is relaxation of the Nash Equilibrium, where each player's 's strategy may not be the best response but is still within e of the best response. Formally, pair of mixed strategies (Phr P2) is e-approximate Nash Equilibrium if
Pe),, + P2), sup U(P, Px) -6 PLEPH
inf
P.EP2
No Regret Algorithms No-regret algorithms games. The regret of a player is defined as the difference between their cumulative payoff and the best cumulative payoff they could have achieved by consistently playing single strategy. A no-regret algorithm guarantees that the average regret of a player goes to zero as the number of iterations (or rounds) tends to infinity. In the context of two-player zero-sum games, if both players follow no-regret algorithms, their average strategy profiles converge to the set of Nash Equilibria.
class of online algorithms used in repeated
D.2 Online Learning
A popular and widely used approach for solving min-max games is to rely on online learning algorithms [Hazan, 2016, Cesa-Bianch and Lugosi, 2006]. In this approach, the row (minimization) player and the column (maximization) player play repeated game against each other. Both players rely on online learning algorithms to choose their actions each round of the game, with the objective of minimizing their respective regret. The following proposition shows that this repeated gameplay converges to a NE.
Proposition 15 ([Gupta et al., 2020l) Consider repeated game between the minimization and maximization players in the linearized game. Let (Pk, P.) be the actions chosen by the players in iteration t. Suppose the actions are such that the regret of each player satisfies:
Σ 1(Pt)
inf Σ 10h, (t), (T) NEH
sup sEZ
1(Ph 2)
Σ P!), S (T(
Let PRAVG, PZAVG denote the mixture distributions 1 EE= Ph. and T D Ps. (PRAVG, PLAvg) is an c-approximate mixed NE of the game with:
Then
(T) + (T)
T
There exist several algorithms such as FTRL, FTPL, and Best Response (BR), which guarantee sub-linear regret. It is important to choose these algorithms appropriately, given the domains H, Z as our choices impact the rate of convergence to a NE and also the computational complexity of the resulting algorithm.
20

---

D.3
General Minimax Theorems (Proof of Proposition 1)
We first state the following convenient generalization of the original Von Neumann's minimax theorem.
Proposition 16 (Von Neumann-Fied Fan minimax theorem, [Borwein, 20161) Let X and Y be Banack spaces. Let C C X be nonempty and convex, and let D C Y be nonempty, weakly compact, and + R be convex with respect to x E and concave and upper-semicontnuous with respect to y E D, and weakly continuous in when restricted to D. Then,
convex. Let g X
sup inf g y) inf sup g(,, y) yED RED
ZEC yED
We now proceed to the proof of Proposition 1. Observe that convex, compact Wn, satisfies the conditions for D the above proposition. Moreover, we have Ah i.e. the set of probability measures on O. It is indeed nonempty and convex. Also, g is bilinear in and w, and thus is convex-concave. Thus, Proposition directly follows from the above result.
Relaxations
We can relax the assumption that h is parameterized by finite dimensional vector 6. For simpler H, the minimax result directly holds with mild assumptions.
If H (11, hn, } i.e. H is finite. Then the original minimax theorem by Neumann holds for arbitrary functions l.
If H = (h1 h1....) i.e. H is denumerable. We further assume is bounded loss function. Then from Theorem 3.1 from [Wald, 1945] to compact and convex W over n (finite) datapoints, can conclude the relation holds.
Hoever, minimax theorems for more general require other conditions like continuity of loss, compactness in function space, etc. See [Simons, 1995] and [Raghavan, 1994].
E Ensemble RAI Games
E.1 Alternative Definitions: Deterministic Ensembles
Alternative definitions for deterministic ensembles could be considered. For example, could consider hz) = arg minyey En~o@(h(r))... y). [Cotter et al., 2019, Wu et al., 2022] designed other more sophisticated strategies, but these largely domain dependent. For reasons that will be explained later, we stick with Definition 3 this work. For regression, a popular de-randomization strategy is compute the expected prediction: (a)
E.2 Prools
E.2.1
Proposition 2
Proof.
sup (e.ll(aa + A.A,
sup Um A arg magmax (2(h(x;) v]l vE(N]
yEy
= [[ sup E, Eg + y| 2 1/2]
wEAn
I[Rw, (Iuandg) 2 1/2]
required.
21

---

E.2.2 Proposition 3
Proof. Denote yq (z) arg maxyey (2(h(x) = y). Then,
Rw. (huave)
sup E. Eu((vQ(z).v) wEW,
Po(1(x)= =vo(x))
sup weW,
En 8)
1/70
S sup weW, N'EY
Ew Ely PQ(()))((h(()) = =v/
E
Eg Σ <(v'.0) = -7
To sup wEW,
V'EY
TQ sup (o wEW,
Row (hrand:)).
required.
F
Algorithms
F.
Convergence Rates
F111
Gameplay
We begin with the following lemma adapted from [McMahan, 2017] (Theorem-1)
Lemma 17 Consider the setting of Algorithm and further assume that ny' 2 -/'->> Reg(w) 2
of Reg(w) is 1-strongly concave w.r.t. some norm [l-l[(e)- Then for any w" Wn, and any T > 0. we have:
T
Regret S "j"''"Reg(w") +
1 (-1),
(where 1, = 1(h((x:). v.))
2
Consider r/' 11 and (1-1 Vill-111, then
1
T
RegretD.r r)Reg(w")
|1 nD +
2n
2n
Moreover, as H-player plays BR,
Regretn.r S 0
Using Proposition 15, achieve e-approximate NE with:
eT Regretn.1 + Regretp.r
D T + O
!
T
Using definition in Equation 7 gives us the required result.
F.1.2 Greedy
Note that we trying minimize the objective (q) w.r.t by the FW update. Using properties of Fenchel conjugates, it is well known that T.,, (Q) is smooth w.r.t ||-I11- Also, the diameter of the simplex Ah w.r.t. |I-[| is < 1. By [Jaggi, 2013] (Lemma 7), we have Cj S 1 and thus by [Jaggi. 2013] Theorem 1, we have:
FW Update
2
L, (2)
min (q) <
O
Q
(T + +2)
7/T
Using the definition of L,, (Q).
L(Q") - min L(Q) < DD +
TT
22

---

Gen-AdaBoost Update This update boils down to standard coordinate descent update on convex and 1 smooth L, (Q) (w.nt II.l Following along the lines of analysis [Boyd and Vandenberghe, ni
2004] (Section 9.4.3),
T, (Q') S (Q,(Q==)) - - (0
Using this decent equation, we can follow standard gradient descent analysis to get:
min L,, - min L,))) 5
n/
The rest of the argument will go through as above.
F.2 Closed Form Updates for different uncertainty sets
In this section, derive closed-form updates for Equation 2 for the entropic regularizer (also mentioned below). We consider common settings mentioned Table 1.
w + argmax E. ((h n/- Σ log(w) wEW,
#=1
Wn (Panta) (Empirical Risk Minimization)
w x- Paata
Wn, = An (Worst Case Margin)
w² 4
Σ (a)(();), Us)
where ut + exp
||u///2
rp--1
Wn = {w (w:w W An, w 1 1 (a-CVaR)
D E ((h" (1) --))
-)) for A S.T. Σ w =1
w + min
an
exp
np-11
Algorithm 3 describes projection procedure find such À in O(n log n) time.
Algorithm 3 Projection for o-CVaR set
Input: 17, a
Ei-i ((v)))))
Vi + cxp
nt-1
2: V f-
3: if Tall 5
Vi then
4: Wi l
5: return
6: else
7:
B(3) f sort(y:) S.T. Via) 206 2io Visj
8:
function CANDIDATE(M)
9:
Cm
((m)
Sm
2u Cml(s) Lem
11: return Sm
end function
13: Let m &- binary search for the smallest m such that CANDIDATE(m)) S
14: Cm Eizm" V(e)
Wy + min Vos 1)
16: return
17:
end
23

---

Wn = fw: D(w]] Pdata) I Pn (DRO) For general f-divergences, there do not exist closed form updates for wt. However, they can still be empirically solved using FW-like updates.
Wn (Paata(G)) Paata (Gat, Pa (Gk)} (Group DRO)
u²
-==1
t-1
Dieg, l(h (2)) for i E Gk. 8% = |Gxl
w² +
where u t exp
exp
||ut112
1/
F.3 Proof of Corollary
Proof. Note that Reg is 1-strongly concave w.r.t II-1/1 and 11- A conservative upper bound for D & log(n) for all (S An). Thus, we can thus take appropriate values of 7) to get:
(V log(n) T
I(Q") S min I(Q) +0
Q
Thus, we have ~ (V log(n) T
from Proposition 15.
G
Generalization
G.1 Population Risk
We first present proposition which gives equivalent characterization of the RAI population risk Proposition 18 The following are equivalent characterizations of the population RAI risk
Rw (h)
sup AP Jam
Bp(((h(2))v))
P.P Passo
Rw (h)
sup r2 (s)
EP (r)))(()))]
Proof. The equivalence between (1) and (2) follows by reparameterizing P in (1) as follows
dP(2) r(2)dPanm (2),
for some r(z) 2 0
Now suppose the uncertainty W defined in Equation (5). The next proposition uses duality to derive an equivalent characterization of the RAI risk in this setting.
Proposition 19 Suppose the uncertainty set is as specified in Equation (5). Then for any hypothesis h, the population RAI risk can be equivalently written as
Rw (h)
inf Ex (en(())) - T) + Σ Nrc +T, X20.7
(8)
where G is the Fenchel conjugate of Gx(()=== =
\lgi(1).
Proof. We rely on duality prove the proposition. First observe that the population RAI risk can be rewritten as
Rw (h)
sup r:Z-R4.J (rs))
E (x)))
(a) sup
inf Epc. [r(=) + 11 f ((())ddPaaal)) + > C
Σ 1=1
9:(r()))dPann(()
Z A
24

---

Since the above objective is concave in r and linear in T, we rely on Lagrangian duality to rewrite it
Rw (h)
inf sup LT,, X20.7 2-2
where L(r, X, T) is defined as:
L(r, 2) E ((2)(en(2)-T) -T) -- )(g(((()) + +Σ de +
Recall the interchangeabillty theorem:
/
IER (Mn ((.2))
inf rEM
F(r(3))))p(2)dz=
(0s0)ppp21 p(z)dzz
so long as the space H decomposable. Since our case we are working with the set (, P) fr 2 + R /(())p(2)dz = =}, which is decomposable, we can apply the interchangeability
theorem to get:
sup Epa.. r:2+RR
((=)(( -)) -r) M )()(((())) Baa sup ((lx(=) - T) (1):(()
120
Ban. G (C)((z) - T),
where Gx(1) = Em Xigi(t), and G is its Fenchel conjugate. so that:
m
R(G,) inf X20,7
Na + T Era.. (fa) (() 7).
We have the following properties of the Fenchel conjugate (t) These follow from the properties of Fenchel conjugates described in Rockafellar [1970].
Lemma 20 Consider the setting of Proposition 19. The Fenchel conjugate G is convex, differentiable and an increasing function that satisfies
dG
dr O, V.
Proof of Proposition 9 For the sake of clarity, we first state Proposition 9 below.
Proposition 21 (Bayes optimal classifier) Consider the problem of binary classification where Y = (-1, Suppose ((h(x),)) v) <(yh(x)) for some & R - [0, oo) which is either the 0/1 loss, or a convex loss function that is differentiable at O with &' (0) < O. Suppose the uncertainty set W is specified in Equation (5). Moreover, suppose {gi ii
corvex and differentiable
functions. Then, the vanilla Bayes optimal classifier is also a RAI-Bayes optimal classifier.
Proof. Following Proposition 19 is easy see that the RAI Bayes optimal classifier is the minimizer of the following problem
inf inf b A20,7
Aace + Epp,, (ő((((()) - r),
where the minimization over h is over the set of all classifiers. For any fixed T), we now show that the classifier h that minimizes the above optimization problem is vanilla Bayes optimal classifier. First note that the above optimization problem, for a fixed (2, T), can be rewritten as
inf Epr.. G (o(y((z) 7).
Using the interchangeability theorem, we can further rewrite this as
pa
inf 11,+1)
Eran(ll)) (ō(()) - 7)] x
WE
25

---

Here, data
is the marginal distribution of Pdata over z, and P is the distribution of y condi-
tioned on
Now suppose & is the 0/1 loss
0, d(z)= {L.
if > 0 otherwise
1,
Recall, G is an increasing function (see Lemma 20). So G3 S G - Using this, it is easy to see that for any 2, the following a minimizer of inf inf E Pam((la) (o 7)]
if Paatn 11x) 2
otherwise
This shows that the vanilla Bayes optimal classifier is minimizer of the population RAI risk.
Now suppose á IR + [0, oo) is convex, differentiable at 0 with o' (0) < O. Moreover, suppose h: X + IR is a real valued classifier. In this case, the RAI Bayes optimal classifier is minimizer of the following objective
Eps. des
inf (- (G)()) - -T] MEB
Let((x)) = G (0(x) - 7). It easy to see that (ax) is convex. This is because (xxx) = (6))( T) is an increasing function; this follows from the fact that G is convex with non- neg-nngte gradients. Moreover, (0) (G))(((0) 7) (0) I Then, Bartlett et al. [2006], Tewari and Bartlett [2007] show that for any z, the following u is minimizer of the inner optimizatin problem: "" > 0 (y 1|x) 2 2. u² otherwise. This shows that vanilla Bayes optimal classifier minimizer of the population RAI risk.
G.2 Generalization Guarantees
G.2.1 Proof of Proposition 11
Proposition 11 directly follows from Proposition 19.
G.2.2 Proof of Theorem 12
first present a key concentration result we use in the proof.
Lemma 22 (Hoeffding bound (Wainwright, 2019I) Suppose that the random variables (Xi)== are independent with mean pi, and bounded between [a, b). Then for any Z 0, we have
2t
P
X;
mil 2
$ 2 2exp
(- n(b a)3
We now proceed to the proof of the Theorem. Following Proposition 11, we know that the population and empirical RAI risk of a classifier h can be written as
(w)
inf Σ Nr. + r + EP.. (3))((2) (x -) X20,7
Rw. (h)
inf
NuG + Ep (la((2) 7)
X
1=1
Our goal here is to bound the following quantity for any given h::
sup RRw (h) R.w. (A)) (Ami),,.Amin, A.2A
E (((x()) -T) Ep (x(la(z) -
The rest of the proof focuses bounding the RHS of the above equation. The overall idea is to first provide high probability bound of the RHS for any given T, r. Next, we take union bound over all feasible (A, T'' by constructing appropriate e-net.
26

---

Fixed T. Observe that (fx(2)) - T) is bounded and satisfies
(- (Cx((=)) S (B
This follows from the fact that G is an increasing function (see Proposition 20), and b, is bounded between 0 and B. From Heoffding bound we know that for any fixed E H, the following holds with probability at least - 2
Pan (1(((z) -T) PE (X(en(=) - 7) S GV
Union bound over T. Define set E' as
= ((),)): 0, min X; 2 NE.
(9)
Let N(E",,, el I12) be the e-net over 8 in || 2|2 norm. It is well known that there exists such set whose size is upper bounded by [Wainwright, 2019]
IN e, |221 so
(^+
A
m+1
E
For any (). E E', let (Ae, Te) be an element in N(E', c, (12) that is c-close to (A, r). Now consider the following
P. (x) - - - EE... (ex -T) r)
sup (A.r)EE*
Epn (1x -) - Ep... (1 - 7)
sup (A,T)EN(E" (.ll-la))
+ sup (XT))E
Bran (2)((()) - -T) - -Eaa G3, (1)(z) - Tc)
Ep (2)) 7) EE G (c)(2) - Te)
sup (A,))E
Since G is L-Lipschitz, the last two terms in the RHS above can be upper bounded by Le. Substitut- ing this in the above equation, we get
P (b(l((2) - T) - Es (i(ln(z) - +)
sup (A.))EE(
sup (A, (A.)) (.1lla))))
EP (2r -
E Gi(Ca(z) - + 2Le
GV - n + 2Le,
(A+T) m+1
where (a) follows from Equation (9), and holds with probability at least
e-
Choosing = C. V we get the desired result.
G.3 Proof Corollary 13
The proof follows from a standard covering number argument. For any h E H, let he be the point in the c-net that is closest h. Then we have
sup (w(hh) Ro. (11) S kell
(w(()) Rw. (h)l
sup
sup helf
RR (h) Rw (he)l sup RRw, (h) Rw, (he)l
beH
Observe that the last two terms above are bounded by G.- Also observe that the first term in the RHS can be upper bounded by 10n 10n-1/100 -
log(nL)) with probability least 1 (N, en -| (2))e=* Combining these two and substituting the value of e, gives the required result.
27

---

H Algorithms: Further Discussion
H.1 Equivalence Conditions for RAI Algorithms (1 and
Proposition 23 Assume that we set Or = and perform coordinate descent update in Algorithm (FW) ie. G argmin (h, V (n then the update is equivalent to the update given by Algorithm I with 1f² =tj.
Proof. From Equation 3, and using the fact that (Q) can be written as a fenchel conjugate, we know that
Voln(Q0-+)) argmax W,
+ ryReg(w)
Bo ntRee(w) (ptc(())) a a' =
argmaa wEW, W
This matches Equation 2 with = Moreover,
= argmin Enc Enc where w² w'= -VbL(Q
bCH
This corresponds the update for ht in Algorithm 1. Thus, we have equivalence.
H.2
Weak Learning Conditions
For the well-knoww scenario of binary classification and zero-one loss, we recover the quasi- Adaai-AdaBoostt weak learning condition:
Proposition 24 Consider the scenario of binary classification and I as the zero-one loss. If the H-player only plays an approximate best response strategy i.e. h satisfies B (x), S 1/2 - for some > 0, then Rw, (heersQT) for T >> Tofor some large enough To-
Proof. Since the D-player uses regret optimal strategy, we have that:
T
Σ
E.t (()(((())))))))))))))()) (x). max (h cr.
t=1
while from the approximate-Bi BR condition we have that:
E ((h())),)) S 1/2-7:
so that we have:
1
Σ
Bug E(h' - 1/2 - eT,
max WE W.,
so that for >> Ty large enough so that cr 7/2, we have that:
1
Σ E. ((h(()))))) < 1/2 1/2.
we W,, T
As Q" assigns T/T to each of (19TT have:
Rw, (hrand:Qr) max Eor EqTE
1/2 7/2
weW,,
Rw, (bdet:qr)= =0 (from Proposition 2)
Hence, we see that h incurs zero enror.
For the general setting, we have slightly stronger weak learning condition, which follows from the analysis of Frank-Woll update [Freund and Grigas, 2014, Jaggi, 2013].
28

---

Proposition 25 Consider Algorithm 2 with the FW update and Reg(.) as 1-strongly concave
regularize w.r.t. I1-I11- If Go satisfies G Σ ming (Q. VoIn,(Q-11) + d, where {64} is the
sequence of approximation errors with 6, 2 0, then:
1. 6f S ((+2] i.e. decaying errors, then L2( & ming (Q) + -(1-()
+[]+2]
6, S f i.e. constant errors, then L, minq Lg n[7+2)
2
Proof. Note that we trying minimize the objective (Q) w.r.t Q by the FW update. Using smooth w.r.t. I1-I12- Also, the
properties of Fenchel conjugates, it is well known that L2( is 7
diameter of the simplex Δи w.r.t ||-II2
1. By [Jaggi, 2013] (Lemma 7, Theorem 1), we have Cj S 1 and thus, we have:
2( 1 7/ 22)
L2( min L,)
2. By [Freund and Grigas, 2014] (Theorem 5. in case of approximation error, the FW/optimality gap converges as before along with a convex combination of errors at each time step i.. if we able solve the linear optimization problem within constant error S. then these errors do not accumulate. Moreover, the convex combination be bound by the maximum error possible and we get,
2 11(T + 2)
L,( - min (Q) S
Q
Experiments
RAI games constitute an optimization paradigm that goes beyond traditional approaches such as distributionally robust optimization, fairness, and worst-case performance. We have seen that for specific uncertainty sets W, RAI Games optimize over well-cstablished robust optimization objectives. As such, the purpose of our experiments is to demonstrate the practicality and generality of our proposed strategies, rather than establishing state-of-the-arr over baselines. Given large number of possible W, do not attempt exhaustive empirical analysis. Instead, we underscore the plug- - and and-play nature RAI Games.
I.1 Setup
Subpopulation Shift A prevalent scenario in machine learning involves subpopulation shift, neces- sitating model that performs effectively the data distribution of each subpopulation (or domain). We explore the following variations this setting:
Domain Oblivious (DO). Recent work [Hashimoto et al., 2018], [Lahoti et al., 2020], [Zhai al., 2021a] studies the domain-oblivion setting, where the training algorithm lacks knowledge of the domain definition. In this case, approaches like a-CVaR and x² aim to maximize performance over general notion of the worst-off subpopulation.
Domain Aware (DA). Several prior works [Sagawa et al., 2019] have investigated the domain-aware setting, in which all domain definitions and memberships are known during training.
Partially Domain-Aware (PDA). More realistically, in real-world applications, there usually exist multiple domain definitions. Moreover, some of these domain definitions may be known during training, while others remain unknown. The model must then perform well on instances from all domains, regardless of whether their definition is known. This setting is challenging it necessitates the model learn both domain-invarte and domain-specific features and to generalize well to instances from unknown domains.
29

---

1.2 Further Details for Section 7
Base Learners We use linear classifiers. WRN-28-1, and WRN-28-5 [Zagoruyko and Komodakis, 2016] as base classifiers for COMPAS, CIFAR- 10 and CIFAR- 100 respectively. To get a sense of performance improvements, we also benchmark performance with larger models, namely three- hidden-layer neural network for COMPAS and WRN-34-10 for CIFAR-10/100.
This paper introduces two categories of algorithms. We elect not to present results for Algorithm 1, which we notice has similar performance to Algorithm 2. Conversely, we provide in-depth experimental analyses for both updates of Algorithm 2, which warrant some special attention due to due to their relation to AdaBoost. In this section, we refer to the FW and Gen-AdaBoost updates as RAI-FW and RAI-GA, respectively. Our implemented versions incorporate a few alterations: 1. We track the un-regularized objective value from Equation I for the validation set. it increases at any round I, we increase the regularization factor y by fixed multiple (specifically, 2). We notice that it leads to better generalization performance over the test set. 2. The same un-regularized objective w.r.t normalized Q' is also used to perform a line search for the step size a. For the FW update, our search space is ball around & at round t, while for the GA update, we search within the range (0, 1).
Proposed Methods
Training, We use SGD with momentum = 0.9 for optimization. We first warm up the model with some predefined epochs of ERM (3 for COMPAS and 20 for CIFAR- (ERR-0/100), followed by maximum of T = 5 base models trained from the warm-up model with sample weights provided by our algorithms. Each base model is trained for 500 iterations on COMPAS and 2000 iterations on CIFAR-100 10/10. Each experiment is run three times with different random seeds. For evaluation, we report the averaged expected and worst-case test loss from Equation 1.
Datasets
We conduct our experiments on three real-world datasets:
COMPAS [Angwin et al., 2016] pertains to recidivism prediction, with the target being whether an individual will re-offend within two years. This dataset is extensively used in fairness research. We randomly sample 70% of the instances for the training data (with fixed random seed), and the remainder is used for validation/testingg.
C1 and CIFAR- 100 are widely used image datasets. For CIFAR-10, we consider two settings: the original set and an imbalanced split [Jin et al., 2021, Qi et al., 2021]. In the imbalanced split, make worst-case performance more challenging by randomly sampling each category at different ratios. To precise, we sample the ith class with a sampling ratio P; where p = (0.804, 0.543, 0.997, 0.593, 0.390, 0.285, 0.959, 0.806, 0.967, 0. 0.660). For these datasets, use the standard training and testing splits, reserving 10% of the training samples as validation data.
Hyperparameters For COMPAS, we warm up for 3 epochs and then train every base classifier for 500 iterations. For CIFAR-IO and CIFAR- 100, we warm up the models for 20 epochs and train base classifiers for 2000 iterations. The mini-baich size is set to 128. It should be noted that the primary aim of our experiments is not hyperparameter tuning. The experiments this paper are designed to demonstrate cases and compare different algorithms. Hence, while we maintain consistency of hyperparameters across all experiments, we do not extensively tune them for optimal performance.
I.3 Interesting Observation: Boosting Robust Learners
Table 4: Mean and worst-case expected loss for RAI-FW + robust optimization algorithms.
COMPAS
CIFAR- (Imbalanced)
CIFARIO
CIFAR100
Algorithm
Average
Worst Group
Average
Worst Class
Average
Worst Class
Average
Worst Class
SGD (x")
32.0
33.7
13.3
31.7
11.3
24.7
27.4
65.9
RAL-EW SGD (x*)
30.9
32.2
13.6
31.0
11.2
23,8
27.6
63.8
Online GDRO
31.7
32.2
13.1
26.6
11.2
21.7
27.3
$7.0
RAI-FW Online GDRO
31.6
33.3
12.9
24.4
19.5
27.8
51.2
Boosting Robust Base Learners
We conclude our results with one interesting observation. Until we have been comparing ensembles with deterministic models. As such, acknowledge
30

---

that given the inherent differences between the two, making a fair comparison is challenging. However, we find that our setup can "boost" not only ERM but also other robust base learners i.e. we use these robust optimization methods to find our base learners under analogous RAI constraints, we are able to further enhance the robust performance of these algorithms. The results are shown in Table 4. We hypothesize that individually robust base learners are able to help the ensemble generalize well, allowing our approach to further optimize through ensembles.
1.4 Synthetic Datasets
In this section, we use synthetic datasets to illustrate how our RAI algorithms converge, and how different constraints on W translate into performance across various responsüble metrics. We use the following distributions to construct the datasets, and use class labels as the group labels.
Dataset-I: P(X 0) = =)][00((0)) 1),
= --(((331))) [V 0), I)) =
[N((0, -3), [),
(), P(Y 0) 0.7, P0 0.3.
Dataset-Il: P(X = =0) -0--V((222-2)00001) () ((2,)))).)
P(X 1) ((((3330)),.33) + 033.) P(Y=)) = = (.7.P( =1) = 0.3
We sample 1000 points each for both training and testing from both distributions. Note that these datasets deliberately exhibit: 1. Class imbalance (particularly in Dataset-I) Multiple minority sub- colb-ooulations (within and between classes) 3. Varying noise levels in the sub-populations (predom- inantly Dataset-II), Such characteristics are frequently encountered in real-world scenarios and demand responsible classifiers.
Models For base learners, we use linear classifiers for Dataset-l and neural network classifiers with single hidden layer of size 4 and ReLU activations for Dataset-II. We find that base learners can be models with varying complexity.
Hyperparameters Due to the limited size of the datasets, we forgo the warm-up stage. At every round, we run 1000 iterations with a mini-batch size of 32. We run a-LPBoost with the default value 7 1. For a-CVaR experiments, we observe similar results and comparisons, albeit with substantial reduction average metrics. Consequently, opt for conservative values to standardize average performance across all models and subsequently compare worst-case performance in responsible settings.
take 0.7 across all experiments. For lower values of a,
1.4.1 Results and Discussion
Domain Oblivious (DO) To begin, run ERM, AdaBoost, a-LPBoost, and RAI games Dataset-I. For RAI-GA and RAI-FW games, we use a-CVaR uncertainty set as W. Given the class imbalance, Y 0 and Y = 1 represent good candidates for subpopulations of interest, The results are reported in Figure We immediately observe the following:
Both proposed methods RAI-FW and RAI-GA effectively decrease the objective value and achieve lower worst-class classification loss, as compared to both ERM and AdaBoost.
They closely follow the a LPLoossst iterates. Intuitively, our quasi-boosting updates resemble a a-ooBosst for the CVaR objective, and that is reflected in similar objective values.
Domain Aware (DA) For this setting, we run ERM, AdaBoost, Online GDRO, RAI-GA. and RAI-FW on Dataset-ll. We use Group DRO over the five gaussian groups as the uncertainty set W. Although Dataset-Il was selected due the presence of more pronounced subpopulation behavior, we get similar results for Dataset-I as well. The results are reported in Figure 2 and Table 5.
Partially Domain-Aware (PDA) For this setting, we run our algorithms for Dataset-Il II. Similar to gaussian memberships, the class labels Y provide another secondary definition of implicit grouping in the dataset. We report the results Table 5. critical observation from the DA setting results is that Online GDRO, and RAI (Group) all exhibit inferior performance according to the secondary class definition iee. although they optimize for the known groups (gaussian), they fail to optimize for unknown groups (class labels). Thus, natural solution is to run RAI updates over the intersection
31

---

Synthetic Datset-1
Algurithm
Ads (best)
Average Loss
Worst Class Loss
ClaR Objective
RAlGame Itrain)
RAIGame-F// (test)
ERM
27.3
82.6
LPBoost (train)
AdaBonst
26.5
27.7
RAlGame- GA (train)
a-LPBoost
23.5
23.7
0.32
RAlGame (test)
RAI-GA
23.9
24.4
[RM (test)
0.30
RAI-FW
23.9
24.2
ERM (traiin)
(number of rounds)
Figure I: Results for Dataset-I. Left: Average and worst class losses for baselines and proposed RAI updates. Right: a-R objective values number rounds train and test splits
ERM
AdaBoost
class 0
RAI-FW
RAI-GA
Online GDRO
Group DRD Obgerive
0.18
AdaRoost (test)
EAM (test)
Online GDRD (tast)
0.14
RAI-W (test)
0.10
0.08
-6
-4
2
x1
Figure 2: Results Dataset-ll, Left: Visualization classifiers learned. For ensembles, we derandomized them using Definition 3. RAI methods (and Online GDRO) effectively prioritize minority and noisy instances (orange). Righr: Testing Group DRO objective values the number of rounds (train values similar and omitted to improve figure clarity). Quantitative results are reported in Table
of x (for unknown groups) and Group (for known groups) constraints. As seen in the Table, see that both RAI-GA and RAI-FW achieve middle ground by significantly improving worst-case performance for both known and unknown groups.
Synthetic Datset-II
Algorithm
Group
Group
Group
Group
Group
Worst Group
Average
Worst Class
FRM
0.0
3.1
15.2
22.9
1.6
22.9
5.5
5.7
RAI-GA (x2)
3.1
5.6
10.1
13.3
2.5
13.3
5.3
5.9
RAL-FW (x²)
2.1
4.7
8.9
13.4
2.9
13.4
4.9
5.1
Online GDRO
5.1
3.7
5.8
10.2
5.6
10.2
6.1
6.2
RAI-GA (Group)
5.0
4.2
7.4
10.3
3.2
10.3
5.4
5.7
RAL-FW (Group)
10.0
4.7
6.5
9.5
5.5
10.0
6.9
7.5
RAI-GA (x2 n Group)
3.4
4.0
7.3
10.3
3.4
10.3
5.1
5.5
RA1-FW (x2 n Group)
4.7
4.9
9.2
10.6
2.6
10.6
5.2
6.1
Table Average, worst group, worst class losses Synthetic Dataset- II, All the algorithms listed after Online GDRO have access to group information.
32

---

33


Reviews:
[{"review_id": "InIWMc04ey", "reviewer": "Reviewer_qrVx", "summary": "This paper looks at different notions of Responsible AI (RAI) and formulates aspects such as fairness and tail-risk as weights on the samples.  The paper addresses the fact that work on RAI often only focuses on improving one of these aspects, which has been shown to worsen other aspects in some cases.  To simultaneously address these multiple aspects of RAI, the paper formulates the problem as a min-max problem, where the minimization is over an ensemble of models and the maximization is over different weight sets, with each weight set corresponding to a different aspect of RAI (e.g. subgroup performance).  The paper proposes two solutions to the min-max problem, one through game playing and alternating between maximizing the weights and minimizing over the models, and the other through a greedy descent algorithm.  The paper derives convergence bounds and contains empirical analyses showing that their method is superior to baseline methods such as Group DRO and AdaBoos for various settings, such as domain-oblivious, domain-aware, and partially domain aware.", "questions": "Did the authors consider how the min-max formulation compares to treading the different RAI aspects as a multi-objective function in the loss?\n\nHow does the min-max approach compare to the baselines in terms of compute resources/time to solving the problem?", "limitations": "The authors discuss some of the theoretical limitations of relaxing the problem from a deterministic ensemble to a randomized ensemble, as well as the potential for improving the bounds on the convergence rate.\n\nThere did not seem to be any discussions on the practical limitations of implementing this approach.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents an original formulation to solve the problem of simultaneously addressing different aspects of responsible AI such as fairness and robustness.  This problem is interesting and relevant to the general field of algorithmic fairness and responsible AI.  Concrete examples such as those found in Table 1 help make the formulation easier to understand, and the paper does a good job of balancing mathematical proofs with empirical results to support the usefulness of the proposed solution.  ", "weaknesses": "In section 4, the introduction of deterministic and randomized ensembles could benefit from an example to help make the section easier to understand.  This section is pretty central to the problem formulation and so more wording could be devoted to this section.\n\nFor the experiments section, it did not seem that multiple RAI objectives were addressed, just subpopulation shift with various levels of awareness of the subpopulation.  It would be nice to see how the algorithm performs when more objectives are introduced.\n\nThe results table, Table 2, lacks confidence intervals, so it is hard to assess the significance of the improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are extremely thankful to the reviewer for their feedback and very insightful questions. We address them below.\n * **Determinstic vs Randomized Ensembles:** We will add an example to the final revision of our paper to make Section 4 clearer. Here is a simple and concrete example of deterministic and randomized ensembles: consider the problem of binary classification with the hypothesis class $H$ = { $h_1, h_2$ } where $h_1(x) = 0$ and $h_2(x) = 1$ $\\forall x \\in \\mathcal{X}$. Suppose $Q = (\\frac{1}{3}, \\frac{2}{3})$ is the distribution over $H$, then $h_{det;Q}(x) = 1$ $\\forall x \\in \\mathcal{X}$ due to the majority vote and $h_{rand;Q}(x)$ is a random variable which is equal to $0$ with probability $1/3$ and equal to $1$ with probability $2/3$. \n\n\n    To add to the question, it is useful to think about why we need this distinction and when random ensembles are actually useful over deterministic ones. There are a couple of reasons: 1) the first is computational and pertains to the difficulty of solving the minimax objective  2) the second is more statistical and pertains to randomized ensembles being more powerful than deterministic ensembles. As mentioned in our work, one prime example is CVaR loss. For instance, [1] showed that for classification tasks under zero-one loss, randomized ensembles have better CVaR loss than deterministic ensembles. \n   \n  * **Multiple RAI objectives in experiments:**\n    There might be some misunderstanding related to diversity in our experiments. While our experimental set is definitely not exhaustive, we indeed show experiments from multiple objectives mentioned in Table 1: $\\alpha-$CVaR in Figure 1 (Appendix), and $\\chi^2$, Group DRO as well as their combination ($\\chi^2$ + Group DRO) in Tables 1 and 5. Similar to $\\chi^2$, the usual evaluation in $\\alpha$-CVaR optimization is done by evaluating worst-case group loss [2] and we find their individual performance is also very similar. Thus, we omit the $\\alpha-$CVaR results from Table 1. Moreover, we are also able to display better performance than all our baselines in these cases. Note that while solving for multiple responsible AI desiderata at the same time, we have no existing formal baselines! We think it is conclusive evidence to show that our framework achieves better performance than baselines. Finally, we once again highlight the generality of the RAI framework and the impracticality of conducting experiments on all possible uncertainty $W$ sets. The framework and theoretical guarantees that come with it are the main highlights of our paper. The experiments are intended towards establishing convergence and superior worst-case performance in some of the most well-studied problems in literature (as above). \n * **Confidence intervals:** All experiments in the original paper were averaged over three random seeds. We have now added confidence intervals to both Tables 1 and 5 as an attachment in our global response. \n\nA more detailed explanation of the setup and results can also be found in Appendix J and in our global response titled 'Results and Discussion'.\n\n[1] https://arxiv.org/abs/2110.13948\n\n[2] https://arxiv.org/abs/2106.06142\n\n* **Multi-Objective Loss Function:** One of the drawbacks of a multi-objective loss function is the huge overhead in choosing a model that achieves a good trade-off between various losses (and also the pareto optimal frontier). Even then, the solution is not guaranteed to be robust to any of the RAI aspects. We believe this is where the RAI framework provides a better formulation to work with. First of all, it allows us to treat a broad range of responsible AI scenarios under a common framework. For example, all the settings described in Table 1 and their combinations come under the RAI umbrella. Second, it is a much more computationally efficient alternative and also guarantees certain level of performance on each of the RAI aspects under consideration i.e. if we construct a DRO and CVaR uncertainty set and solve the resulting objective using our proposed algorithms, the solution will have certain robustness guarantees in both DRO and CVaR settings simultaneously. \n * **Compute Resources/Time:** Training time scales linearly with the number of base learners. Inference, though, can be parallelized if need be. We usually find training on 3-5 learners is good enough on all scenarios explored in the paper.\n\nWe are very thankful for the time spent by the reviewer to review our work and hope the discussion above clarifies the reservations the reviewer has. We will be delighted to provide any more clarifications if need be!"}, {"review_id": "Z1Fcc6Q9wV", "reviewer": "Reviewer_yXJG", "summary": "The paper demonstrates originality in its approach to proposing a general framework for Responsible AI (RAI) games. The authors introduce the concept of RAI risks and present algorithms based on game-play and greedy strategies to solve the RAI games. The connection between deterministic and randomized ensembles is also explored. Overall, the paper offers novel perspectives on addressing the challenges of responsible AI.", "questions": "Abstract\n1. “In these problems, a learner seeks to minimize its worst-case loss over a set of predefined distributions.” This sentence could be rephrased for better clarity. “In these problems” reads a bit odd, the meaning of “predefined distributions” is not very clear.\n2. “In this work, we provide a general framework for studying these problems…” It is unclear what the authors mean by “these problems”. Are they referring to the aforementioned societal issues of AI such fairness, robustness, and safety? Are all RAI issues studied in this paper, or just the mentioned ones (fairness, robustness, and safety)?\n3. The abstract introduces the Responsible AI (RAI) games framework but does not provide a clear definition or description of what RAI games entail. It would be helpful to briefly outline the key components and principles of RAI games to give readers a better understanding of the framework being proposed.\n4. The phrase \"Empirically we demonstrate the generality and superiority of our techniques for solving several RAI problems around subpopulation shift\" could be rephrased to sound less self-promotional and more objective. Additionally, \"several RAI problems\" is too vague as RAI encompasses a broad range of issues. Furthermore, \"subpopulation shift\" is not mentioned or explained.\n\nSection I: Introduction\n5. The mention of fragmented work and optimization of different aspects is valuable, but it would be beneficial to provide references or briefly summarize the existing literature to give readers an understanding of the current state of research. This will help establish the context and importance of the proposed unified framework for responsible AI. \n6. The authors introduce RAI games as a general framework but does not clearly define what RAI games entail. It is essential to provide a concise definition or description of RAI games to ensure readers have a clear understanding of the framework being proposed from the outset.\n7. Please consider rephrasing “this is a computationally difficult game that need not even have a Nash equilibrium” for better clarity.\n8. The term \"population risks\" is introduced without a clear context or explanation.\n\nSection II: Problem Setup and Background\n9. Appendix C is mentioned as a location for related work. But it would be beneficial to include at least a brief summary or mention of some of the related works in this section itself. This will allow readers to gain insights into the existing literature without having to refer to the appendix separately.\n", "limitations": "The authors identify the broader impact and limitations of this work in the Appendix. The limitations include inadequate evaluation, limited generalization, and the need for handling corruptions in training data.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper's contribution mainly lies in providing a comprehensive framework for studying responsible AI problems and proposing algorithms for solving RAI games. By addressing various aspects such as fairness, robustness, and safety within a unified framework, the paper offers practical solutions for building responsible AI systems. ", "weaknesses": "In general, the paper is well-structured but the overall presentation quality requires improvements, and there are instances where the language and explanations could be further improved for better clarity and comprehension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review of the paper content. We acknowledge that some parts of the paper as written may not be very clear. We have provided additional clarifications in our global response. We will also edit as per all your comments in the final version.\n1. We will rephrase the sentence for clarity in the final version of the paper. By ``predefined distributions'' we refer to the uncertainty set in RAI games. \n2. We acknowledge that our RAI framework might not encompass all modern issues. However, it unifies a lot of subproblems that have been historically studied in isolation (Table 1) and comes with theoretical guarantees. To this end, we have clarified the scope of our contributions in our global response (titled 'Revised Contributions' and 'On whether the worst-case focused developments cover all notions of responsible AI').\n3. By RAI games, we mean RAI problems that can be written as min-max problems. The key component in an RAI game is the domain of the inner maximization problem which captures the set of sub-populations over which we would like to have low risk. We would like to note that the domain of the inner max is predetermined and doesn't change during the course of the learning.\n4. We apologize if the phrase sounded too self-promotional. We will edit it to be more objective in the final version of the paper. It was intended to underscore the fact that the RAI framework is not just theoretically sound, but is able to train robust models as per RAI aspects in Table 1 as well as their combinations. With only a few learners (3-5), we are able to show enhanced performance on a widely studied task over some seminal baselines, which usually have been developed in isolation and do not necessarily consider multiple aspects at once. We acknowledge that the phrase might be vague. To this end, we have extensively clarified the exact scope (and limitations) of our framework in our global response (titled 'Revised Contributions' and 'On whether the worst-case focused developments cover all notions of responsible AI'). As the task is quite well known, we had explained the task of 'subpopulation shift' in detail in Appendix J (J.1 to be specific). We acknowledge we could have placed the section better and will update the final version of our paper correspondingly. Please let us know if any of the explanation still seems unclear.\n5. Sure, we will modify this line to: But how do we do so when the majority of recent work around these problems is fragmented (DRO [1,2]), GDRO [3], CVaR [4], Distribution Shift [5,6] and usually focuses on optimizing one of these aspects at a time?\n6. Kindly refer to our response in point 3 above. We also have addressed this point in the global response.\n7. Sure, we will clarify this line in our final revision. The RAI game considers fairness objectives that take a minimax representation (for e.g. [7]). In general, these games might not admit a Nash Equilibrium and thus might not be easily solvable by online learning algorithms considered. This forms one of the motivations to go from a single predictor to a deterministic ensemble i.e. to have convergence and very desirable theoretical guarantees. For more detail on two-player-zero-sum games, please refer to Appendix E. \n8. We have introduced population risk in line 233. To reiterate, empirical RAI optimization focuses on all adversarial weightings over the given $n$ samples (drawn from $P_{data}$) which are close to the simplex. In the limit, the population counterpart is then defined over all distributions in a certain ball (defined by the appropriate distance metric) around the true data generating distribution $P_{data}$.\n9. We will include a brief version of related work (with the most important prior work) to the main paper in the final version.\n\nWe hope we have clarified all your reservations about the unclear language of the paper. We will make additional macro improvements regarding clarity in the final version. Moreover, we have thoroughly clarified our contributions, and motivation in our global response. We look forward to addressing any additional comments you might have.\n\n[1] https://arxiv.org/abs/1610.02581\n\n[2] https://arxiv.org/abs/1810.08750\n\n[3] https://arxiv.org/abs/1911.08731\n\n[4] https://arxiv.org/abs/2110.13948\n\n[5] https://arxiv.org/abs/1806.08010\n\n[6] https://arxiv.org/abs/2106.06142\n\n[7] https://arxiv.org/abs/2011.03108\n"}, {"review_id": "zY3EVNhhJ4", "reviewer": "Reviewer_TUyo", "summary": "In this paper the authors formulate a framework of responsible AI (RAI) games, which represents a variety of societal effects of AI as minimizing worst-case loss over a set of predefined distributions. The authors cover their framework and present a number of related definitions and propositions. They then present two algorithms for attempting to solve these games. They end by briefly covering results comparing their approach with a variety of baselines across a variety of common tasks/datasets. \n\nEdit: Based on the author's rebuttal and our discussion I have increased my initial review to a weak accept.", "questions": "1. What was the inclusion/exclusion criteria for the representations of AI societal effects not covered by the author's framework?\n2. What is the reason that the performance of the RAI approaches are so similar to the baselines?", "limitations": "The paper does not appear to have any negative societal impacts, except perhaps overstating its contributions leading to overuse.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Section 2-4 are definitely the highlights of the paper. They give a well-written argument for the utility and implications of the RAI framework. Outside of these, the clarity of the introduction and coverage of related work are also both strong.", "weaknesses": "There are three primary weaknesses in the current draft of the paper. First, the authors chose to use minimizing worst-case loss as a sole target for all societal effects of AI. However, this is not the only computational representation of these effects. For example, fairness is often defined in terms of symmetry across classes, which is not necessarily identical [1]. In general, this represents only one particular perspective on a subset of these societal effects. The paper would be improved with acknowledgement of this and direct discussion of what definitions are being used and why.\n\nThe second weakness is the relatively weak results. The performance of the RAI approaches appears to be very close to the baselines in all cases. This doesn't match the claim of \"solving responsible AI games\". The earlier text in the paper generally suggests an expectation of much stronger results. There's also an odd claim that larger models are limiting, when these are very commonly used models. Relatedly, for the third weakness, there is a lack of discussion around the results, just three bullet points and a two sentence conclusion. Reducing Sections 2-4 could allow for a better contextualization of the results to clarify if they are stronger than they appear. Otherwise, the proposed algorithms do not seem to be good fits for the RAI framework. \n\n1. van den Brink, René. \"An axiomatization of the Shapley value using a fairness property.\" International Journal of Game Theory 30 (2002): 309-319.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very thought-provoking review and appreciate the time the reviewer has taken to thoroughly review our work!\n\n*  **Minimizing worst-case loss (and Q1):** There has been a surge of RAI-related topics in recent years, and it is impossible for a single framework to cover all RAI problems. However, the framework we formulate in this work can cover most of them, at the very least including all of those listed in Table 1 and their combinations. Broadly speaking, it covers RAI aspects that can be represented in a minimax fashion (for e.g. [1]). Please refer to our global response (titled *'On whether the worst-case focused developments cover all notions of responsible AI'* and *'Contributions'*) for further discussion and our full response on this aspect. \n * **Weakness of results (and Q2):** There might be some misunderstanding regarding the claim 'weakness of results'. We believe the improvements are significant and are of similar order as related works [2,3,4]. We have now uploaded updated result tables 1 and 5  including error bars in our global response. To justify our point, we note: \n    1) from Table 1, observe that the tasks get harder from left to right i.e. the gap between average and worst-case baseline performance increases. The magnitude of improvements also increases significantly as we move to the right. For instance, RAI algorithms are able to achieve a \\~5\\% improvement in worst-case performance over the baselines for CIFAR-100. \n    2) the improvements in datasets like COMPAS may seem small but that is primarily because the average and worst-case performance are similar i.e. the imbalance in the dataset is intrinsically small. \n    3) Finally, we would like to highlight that good empirical results are not the only contribution of our work. One of the key goals is to initiate a principled RAI framework that encompasses a broad range of tasks that have been mostly dealt with in isolation in previous work. It also comes with algorithms and theoretical guarantees for the population risk. To further the effort of clarifying our contribution and provide a discussion on results, please refer to our global response as well (titled *'Contributions'* and *'Results and Discussion'*).\n    4) We apologize, but the comment about large models might have been misunderstood. We just underscore the fact that our RAI ensembles of smaller models are able to match up to the robust performance of the big models, which are then further outperformed by robust ensembles of those large models.\n *  **Discussion around results** We acknowledge that there might have been a lack of clarity around some discussions around the results. A discussion of results can be found in Appendix J and in the global response (titled 'Results and Discussion'). We will add these comments to the main paper. \n * **Algorithms** Can you kindly clarify what you mean when you say, 'the proposed algorithms do not seem to be good fits for the RAI framework'? We will be happy to resolve this question once get some more context on this.\n\nPlease let us know if there is any residual feedback and we will be delighted to resolve it with further discussion.\n\n[1] https://arxiv.org/abs/2011.03108\n\n[2] https://arxiv.org/abs/2110.12459\n\n[3] https://arxiv.org/abs/1911.08731\n\n[4] https://arxiv.org/abs/2106.06142"}, {"review_id": "Rtk4mq7tQp", "reviewer": "Reviewer_KQkZ", "summary": "This paper aims to provide a general framework that is broadly applicable across responsible AI (such as ethics, fairness, train-time robustness, test-time or adversarial robustness etc). Motivated by this, the authors proposed Responsible AI (RAI) games, where a learner seeks to minimize its worst-case loss over a set of predefined distributions. This is modeled by a zero-sum game between a learner that aims to learn a responsible model, and an adversary that aims to prevent the learner from doing so. To solve this problem, the authors first go from a single predictor to a deterministic ensemble, namely a distribution over predictors that can then be de-randomized via a majority vote. Then, the authors study a relaxation of this deterministic ensemble RAI game, which they term the randomized ensemble RAI game, which can also be motivated as a linearization of the original RAI game. Finally, the authors conduct empirical analyses to demonstrate the convergence and performance of their proposed algorithms.", "questions": "Can the authors add some more details to clarify the experiments? For example, the research questions to be tested in support of the motivation of the paper, the hypothesis, and clarify the results analysis according to these questions.", "limitations": "Yes the authors addressed limitation in Appendix B. I do not see any negative societal impact.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The topic of responsible AI is an interesting and important area of research.\n- The theoretical results are backed by proofs included in the appendix.", "weaknesses": "- Despite the appealing motivation of building a general framework that is broadly applicable across responsible AI, I find the proposed framework to be overly simplistic, as well as the experiments. This makes it difficult for me to connect the proposed theoretical framework with the motivation described in the introduction.\n- the paper is very difficult to follow and needs to be clarified for the audiences from the general AI community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We’re extremely grateful for the valid and insightful suggestions that the reviewer has made. Below we address some of the key concerns raised.\n\n**Scope of RAI Framework.** \n\n* The RAI framework introduced in our work aims to unify the fragmented works in the literature around RAI aspects which can be written as min-max problems. This turns out to be a large umbrella of modern problems, which includes distribution shift[1], group fairness [2], tail risk (CVaR loss)[3], etc. Our framework comes with algorithms to provably train models for these (and any combination of these) RAI aspects. As mentioned in related work, there is a large body of work that studies individual problems falling within our framework [4,5,6,7]. And we believe our framework can be very valuable in studying the optimization and generalization aspects of these problems.\n* Another important aspect of our work is that it tries to connect boosting to RAI games (to the best of our knowledge, both these lines of work have been treated separately until now), and uses the insights from boosting to design algorithms for RAI games. Please take a look at our global response where we clarify the scope of our framework and our contributions. \n* We have provided further context and summarized our contributions in the global response as well (titled *'Contributions'* and *'Importance of our developments and whether the worst-case focused developments cover all notions of responsible AI'*)\nPlease let us know if any of your questions still remain unresolved. We are happy to resolve any other follow-up comments as well.\n\n[1] https://arxiv.org/abs/1911.08731\n\n[2] https://arxiv.org/abs/2011.03108\n\n[3] https://arxiv.org/abs/2110.13948\n\n[4] https://arxiv.org/abs/1610.02581\n\n[5] https://arxiv.org/abs/1810.08750\n\n[6] https://arxiv.org/abs/1806.08010\n\n[7] https://arxiv.org/abs/2106.06142\n\n**Result Section.**\n\n*  We acknowledge the discussion around the result section might not be very clear due to space constraints. Task definitions, synthetic experiments, etc. can be found in Appendix J in detail. A discussion of results can also be found in the global response (titled *'Results and Discussion'*). We will add these comments to the main paper. Here are the research questions we test and our analysis for the same.\n  * RQ1: Do Algorithms 1 and 2 converge for real-world datasets? If yes, are they able to improve worst-case performance in the considered RAI aspects from one-off deterministic baselines proposed by past literature? \n  * RQ2: Can multiple RAI aspects (e.g. in Table 1) be combined efficiently to have our model satisfy several robustness criteria at once?\n\nHere is the analysis we find:\n   * RQ1: We answer both these questions in the affirmative. RAI-FW and RAI-GA methods significantly improve the worst-case performance with only a few base learners across all datasets in all three settings, while maintaining average case performance.\n   * RQ2: We answer this question in the affirmative as well. The plug-and-play framework allows for several different $W_n$ to enhance various responsible AI qualities at once. The worst-case performance of all our baselines is a lot worse in the PDA setting than in the DA setting. This suggests that although the DA setting can optimize for the known groups, it fails to optimize for unknown groups. Thus, a natural solution is to run RAI updates over the intersection $\\chi^2$ (for unknown groups) and Group DRO (for known groups) constraints. Indeed, we see that in the PDA setting, the performance lead widens, indicating that RAI is able to optimize effectively for both known and unknown subpopulations while Online GDRO suffers from some of the group information being unknown. In practice, one can construct many more novel sets $W_n$.\n\nOnce again, we have also clarified some discussion around results in the main paper in our global response (titled *'Results and Discussion'*). We sincerely hope that this discussion is satisfying and addresses the reviewer’s concerns and suggestions. Please let us know if anything else needs clarification. "}]

Author rebuttal:
## Global Response to All Reviewers
**Contributions.** We have rephrased our overall contributions to improve clarity and refine the scope of our work. We want to highlight the concrete contributions of this work below.
* Under the umbrella of “responsible AI”, an emerging line of work has attempted to formalize such desiderata ranging over ethics, fairness, train-time robustness, test-time or adversarial robustness, and safety, among others. Many of these settings (given in Table 1) can be written as min-max problems involving optimizing some worst-case loss under a set of predefined distributions. For all the problems that can be framed as above, we introduce and study a general framework, which we refer to as Responsible AI (RAI) games.
* We note that our framework encompasses not only these specific responsible AI settings but also the setting of classical boosting. Drawing upon the insights from boosting, we provide boosting-based algorithms for solving responsible AI games and derive their convergence guarantees.
* We study the population RAI risk and characterize it's global minima. Perhaps surprisingly, we show that classical Bayes optimal classifier is a minimizer of the population RAI risk for a wide range of uncertainity sets.  Finally, we initiate the study of generalization guarantees of RAI risk, which we believe is very important for understanding the test-time performance of ML models in the responsible AI setting.
* We also conduct empirical analyses to demonstrate the convergence and performance of our proposed algorithms. Owing to the generality of the framework, there is a very large body of RAI settings. Instead of attempting to exhaustively cover all of those, we  conduct experiments for one of the most well-studied problems of subpopulation shift. We demonstrate that these algorithms converge empirically and show superior performance over baselines for both synthetic and real-world datasets. Another crucial point is that all the baselines try to solve individual RAI subproblems in isolation. Instead, RAI can guarantee multiple responsible AI aspects under appropriate choices of uncertainty sets.

**Importance of our developments and  whether the worst-case focused developments cover all notions of responsible AI:**
We note that we draw our unified framework from the seminal work over the past decade by responsible AI researchers on devising non-expected risk objectives to ensure ML models are responsible. But as we note in the paper, these have resulted in a multitude of different objectives (even for a single responsible AI desideratum such as fairness), and also multiple different sub-communities (so that fairness and multiple disparate robustness communities are relatively fractured). Our goal is to draw a unified framework that combines many if not all such objectives within a single umbrella. Moreover, as we show in our experiments, such a unified framework might allow for interesting combinations such as requiring both robustness and fairness; which we imagine will result in new connections between the different communities.

We note that there is emerging work on relating worst-case performance to invariance [1]; in other words, we might be able to get approximate group invariance via minimizing an appropriately constructed worst-group risk and vice-versa. But overall we agree that RAI games might not fully cover all possible notions of responsible AI, and will be sure to emphasize this in this final version.

[1] https://arxiv.org/abs/1812.08233

**Overly mathematical developments**
We note that while at first blush the game-theoretic formulation might seem unnecessarily complex, there is an emerging trend in many of the different communities, such as tail risk, robustness, and sub-population fairness to name a few, of connecting the respective responsible AI desiderata to solving games as we note in the paper. We thus view our development as a natural teleological consequence of developments within the different responsible AI communities themselves.

**Results and Discussion**
we acknowledge that the discussion around results might be a little unclear. So we discuss it in more detail below:
 * We empirically study one of the most well-studied problems in RAI i.e. the case of subpopulation shift. We acknowledge that this is not a complete analysis, even with respect to the problems that live within the minimax framework. We aim to display convergence, plug-and-play generality of our framework, and superior performance over some seminal baselines of this task. 
 * We note that for a single responsible AI desideratum, our developments mirror those emerging in the respective communities (e.g. worst-case sub-population performance) since our goal was to develop a unified framework. So the purpose of our experiments was to show that we can match baselines for a specific single desideratum (e.g. worst-case sub-population performance) while allowing for learning models that can solve multiple responsible AI desiderata at the same time, for which we have no existing baselines!

To this end, the results are shown in Table 1 (real) and Table 5 (synthetic).  As such, we can make the following observations:
  * RAI-FW and RAI-GA methods match or improve the worst-case performance with only a few base learners across all datasets in all three settings while maintaining average case performance.
  * For seemingly harder tasks i.e. a large gap between average and worst-case performance, the algorithms are able to improve significantly over the baselines. For example, we observe a $\sim$5\% improvement in performance in the case of CIFAR-100.
  * Moreover, our unified framework allows for interesting combinations such as requiring both known and unknown group fairness. We demonstrate this with the partial domain aware setting (PDA). We jointly optimize both objectives ($\chi^2$, Group-DRO) and are able to perform significantly better than baselines here.

Meta-review: This paper puts forward a framework for Responsible AI (RAI) algorithms. The framework allows algorithm designers to address different aspects of RAI (such as robustness and fairness) in a unified way, via a zero-sum, or min-max optimization perspective. The reviewers have expressed several weaknesses of this work (besides of minor issues): the baselines approaches seems to perform quite well relatively to the new approach; some of you required the authors to clarify some parts of the paper (e.g., clarification on determinstic and randomized ensembles); worst-case perspective is quite limited.

That being said, in general, the reviews acknowledged the solid contribution of the framework and the extensive results the authors provide in this work, as well as the novelty of their formulation. Due to these, I support the acceptance of this work.
Decision: Accept (poster)