Optimal algorithms for group distributionally robust optimization and beyond
Authors: Tasuku Soma
Khashayar Gatmiry
Stefanie Jegelka
Venue: NeurIPS 2022 Submitted (2022)
Keywords: fairness
robustness
subpopulation fairness
conditional value at risk
distributionally robust optimization

Abstract: Distributionally robust optimization (DRO) can improve the robustness and fairness of learning methods. In this paper, we devise stochastic algorithms for a class of DRO problems including group DRO, subpopulation fairness, and empirical conditional value at risk (CVaR) optimization. Our new algorithms achieve faster convergence rates than existing algorithms for multiple DRO settings. We also provide a new information-theoretic lower bound that implies our bounds are tight for group DRO. Empirically, too, our algorithms outperform known methods.

Optimal algorithms for group distributionally robust optimization and beyond
Anonymous Author(s)
Affiliation
Address email
Abstract
Distributionally robust optimization (DRO) can improve the robustness and fairness of learning methods. In this paper, devise stochastic algorithms for class DRO problems including group DRO, subpopulation fairness, and empirical conditional value at risk (CVaR) optimization. Our new algorithms achieve faster convergence rates than existing algorithms for multiple DRO settings. We also provide new information-thest theoretic lower bound that implies our bounds are tight for group DRO. Empirically, too, our algorithms outperform known methods.
3
Introduction
9 Commonly, machine learning models are trained to optimize the average performance. However,
10 such models may not perform equally well among all demographic subgroups due to a hidden bias in
11 the training set distribution shift in training and test phases [Hovy and Søgaard 2015 HHshhmoto
al. 2018 Martinez et al.) 2021 Duchi and Namkoong. [021]. Biases in datasets are also directly
13
related to fairness concerns in machine learning [Buolamwini and Gebru 2018 Jurgens el al. 2017
14 Recently, various algorithms based on distributionally robust optimization (DRO) have been proposed
15
of address these problems (Hovy and Søgaard 2015 Hashimoto al. [0018] Hu al 2018 Oren
18
al. al.|20199 WWiliiamon and Menon (2019; Sagawa et al. 22220] Curi et al.) [2200] Zhang et al. 2021
17
Martinez al.] [021] Duchi and Namkoong [002]. However, these algorithms
often highly
18
tailored to each specific DRO formulation Furthermore, it is often unclear whether these proposed
19
algorithms are optimal in terms of the convergence rate, Are there unified algorithmic methodology
20
and lower bound for these problems?
21
Contributions. In this paper, we study general class of DRO problems, which includes group DRO Hu et al. 22188) Oren er al., 2019 Sagawa et al., 2020). subpopulation fairness [Martinez et aL 202T conditional value risk (CVaR) optimization [Curi al, 2020), and many others. Let be convex set of model parameters and {(0; 2) Q + R be convex loss of the model with parameter f with respect to data point 2. The data point may be drawn from one out of m distributions PI.....P P.. which are accessible via stochastic oracle that returns an i.i.d. sample P.. Let Q be convex subset of the probability simplex Rm that contains the uniform vector, i.e. (1/m,... 1/m) E Q. Our DRO formulation is follows:
22
28
24
25
26
27
min max dE QEQ
E [[(00=))) 2~P
29 If Q are the probability simplex and scaled k-set polytope, can recover group DRO [Sagawa e
30 al. 2020 and subpopulation fairness [Martinez et al. 202T]. respectively. Moreover, we Tormulate
31 new, more general fairness concept based on weighted rankings with Q being permutahedron.
32
which includes these special cases; see Section 2 for details.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

Table I: Summary of convergence results for group DRO. Here, denotes the number of groups, the dimension of f, G the Lipschitz constant of loss function f, D the diameter of feasible set θ M the range of loss function f, and T the number of calls to stochastic oracle.
reference
convergence rate E E(eT)
iteration complexity
lower bound
Sagawa al. 2020
o mm
G +M logm
( + +n) + proj. onto θ
Ours (Theorem
G2
( + +n) proj. onto Q
M
GP D2 M2m
(Theorem 5
(m + n) + proj. onto + solving scalar equation
Ours (Theorem
G2 G2D2
33
For our general DRO, we devise an efficient stochastic gradient algorithm. Furthermore, we show that it achieves the inforeetion-theoretie optimal convergence rate for group DRO. Our main technical contributions are as follows;
34
35
36
We provide generic stochastic gradient algorithm for our general DRO. By specializing it in the group DRO setting, we provide two algorithms (GDRO-EXL and GDRO-TINF) that improve the rate of Sagawa et al. [2020] by a factor of (1(m)) with the almost same complexity per iteration; see Table || Furthermore, our generic algorithm can be specialized to improve the convergence rate of Curi et al. [2020) for subpopulation fairesss (a.k.a. empirical CVaR optimization). Finally, we show that our algorithm runs efficiently if Q is permutahedron, which includes all aforementioned subclasses.
37
38
39
41
We prove a matching information-theoreeti lower bound for the convergence rate of group DRO. This implies that no algorithm can improve the convergence rate of GDRO-TINF (up a constant factor). To the best of our knowledge, this is the first iifoormation-thhoreede lower bound for group DRO.
44
45
46
Our experiments real-world and synthetic datasets show that our algorithms also empiri- cally outperform the known algorithm, supporting our theoretical analysis.
48
49
1.1
Our techniques
The core idea of our algorithms stochastic no-regret dynamics (Hazan 2016). We 51 regard DRO (I) as a two-player zero-sum game between player who picks 0 E θ and another player
50 Algorithms.
52 who picks q E Q. The two players iteratively update their solution using online learning algorithms;
53 in particular, we will use online gradient descent (OGD) [Zinkevich] 2003) and online mirror descent
54 (OMD) [Cesa-Bianchi and Lugosi 2006) for the 0-player and y-player, respectively. addition, we need estimate gradients for both players, since the objective function of our DRO is stochastic and 56 we cannot obtain exact gradients.
57
The convergence rate of stochastic no-regret dynamics depends on the expected regret of OGD and OMD. To obtain the optimal convergence rate, we must carefully choose the regularizer in OMD as well as gradient estimators, exploiting the structure of our DRO. In particular, we need to balance the variance of gradient estimators and the diameter terms in both OGD and OMD. This the most challenging part of the algorithm design. Inspired by adversarial multi-armed bandit algorithms, we design gradient estimators for no-regret dynamics of OGD and OMD in our DRO. Indeed, our algorithms for group DRO (GDRO-EXP3 and GDRO-TINF) are based on adversarial multi-armed bandit algorithms, EXP3 [Auer et al. 2003 and INA (Zmmert and Seldin 2021], respectively, hence the name. Although each building block (OGD, OMD, and gradient estimators) fairly known in the literature, we need to put them together in the right combination to obtain the optimal rate.
58
59
60
61
82
63
64
66
67
Lower bound. For the lower bound, we carefully design family of group DRO instances for which any algorithm requires a certain number of queries achieve a good objective value. To bound the number of queries, we use coormattion-thoreeti tools such as Le Cam's 's lemma and bound the Kullback-Leible divergence between Bernoulli distributions. Such tools are also used at the heart of
68
69
70
lower bounds for stochastic convex optimization (Agarwal et af. [012 and adversarial multi-armed
72
bandits [Auer al. [2003), but the connection to those settings is much more subtle here, and our construction is specifically designed for group DRO-type problems.

---

74
1.2
for Related work
75
DRO is a wide field ranging from robust optimization to machine learning and statistics [Goh and Sim
78
2010; Bertssimas et al. 2018). whose original idea dates back to |carr] [1958]. Popular choices of the
77
uncertainty set DRO include balls around an empirical distribution in Wasserstein distance [Esfahani
78
and Kuhn 2018 Blanchet el al.) [019]] f-divergence [Namkoong and Duchi, 2016) Duchi and
79
Namkoong 2021 J. X divergeee [Staib el al. 2019), and maximum mean discrepancy (Staib and
80
Jegelkal 2019: Kirschner el al. 2020].
81
DRO algorithms have been mainly studied for the offline setting, i.c., algorithms can access all data points of the empirical distribution. Note that our DRO is not offline because the group distributions are given by the stochastic oracles. Namkoong and Duchi [016] proposed stochastic gradient algorithms for offline DRO with f f-divergence uncertainty sets. Curi et al. [020] used no-regret dynamics for empirical CVaR minimization. Their algorithm invokes sampling from k-DPP in each iteration, which is more computationally demanding than our algorithm. Furthermore, our algorithm gets rid of an O(log m) factor in the convergence rate using the Tsallis entropy regularizer; see Theorem 4 Qi el al. (202T] : Jin et al. [202]] devised stochastic gradient algorithms for several DRO
82
83
84
85
86
87
88
89
with non-convex losses.
90
Agarwal et al. [2012] gave a lower bound for stochastic convex optimization, which is a special case of our DRO with only one distribution. Recently, Carmon al. [2021) showed lower bound for minimax problem min, max f((x) for non-stochastic Lipschitz convex fi. Our lower bound deals with the stochastic functions, so this result does not apply.
91
92
93
94
In this paper, we assume that the group information given in advance. However, the group information might not be easy to define in practice. [ao et al. [2021] propose a simple method to 96 define groups for classification problems based on mistakes of models in the training phase. Their method often generates group DRO instances with large m. Our algorithms more efficient for such group DRO thanks to the better dependence on m in the convergence rate.
98
No-regret dynamics is well-studied method for solving two-player zero-sum games Cesa-Biaanchi
100
and Lugosi 2006). For non-stochastic convex-concave games, one can achieve O(1/T) convergence Via predictable sequences [Rakhlin and Sridharan] 2013). This result does not apply to our setting because our DRO is a stochastic game.
102
103
Throughout the paper, m denotes the number of distributions (groups) and denotes the dimension of variable f. For a positive integer m, we write [m] := (1....,m) .m]. The orthogonal projection onto set θ is denoted by projg. The ith standard unit vector is denoted by e, and the all-one vector is denoted by 1. The probability simplex in Rm is denoted by Am.
Notations.
104
106
Examples contained in our general DRO
107
In this section, we show how several DRO formulations in the literature can be phrased in our general DRO formulation (T. In addition, we propose a novel fairness constraint based on weighted rankings using our general DRO.
109
111
Group DRO. When Q equals the probablility simplex, we obtain group DRO Hu et al. 2018
112
Oren et al. 2019 Sagawa et al. 2020
min max E [[(0; IE0 i=1 aNP.
That is, group DRO aims to minimize the expected loss in the worst group, thereby ensuring better performance across all groups.
114
115
Empirical CVaR, Subpopulation fairness, Average top-k worst group loss. Group DRO may yield overly pessimistic solutions. For instance, the groups might be automatically generated by other algorithms (such as one in Bao el al. (202T) and there might exist a few "outlirr" groups that make
116
118 the group DRO objective trivial.
119 For such case, we can restrict Q to a small subset of the probability simplex so that the solution
120 cannot put large weights on a few outlier groups. Especially, let Q = {u E Am S qa S pm
3

---

some parameter p E (0, 1), i..., Q is a scaled k-set polytope. The intuition behind the choice of Q that, by limiting the largest entry of q to 1/pm, DRO would optimize the expected loss over the worst y-fraction subgroups of groups. Therefore, if the fraction of outlier groups is sufficiently small compared to p. then p- p-fraction subgroups must contain "inlier" groups as well. Therefore, is likely that DRO with Q finds solutions more robust than group DRO.
122
124
125
128
When P. is the Dirac measure of data 2,, then the resulting DRO empirical CVaR optimization (Curi al. 2020 In the fairness context, the same problem is called subpopulation fairness Williamson
127
128
and Menon 2019 Martinez et al., 2021 Duchi and Namkoong 2021
129
m/k for some positive integer k, the resulting DRO is the average top-k worst group
loss [hhng al. 2021
min 1
Σ (0),
where (0) denotes the the ith largest population group loss of 9. More precisely, let L,(0) E P. [e(0; 2)] for E [m]] and sort them in the non-increasing order: LŞ(0) 2 ... 2 L (0).
132
133
Weighted ranking of group losses. The aforementioned DRO formulations are special cases of the following DRO, which we call the weighted ranking of group losses. Let A be fixed vector with non-increasing entries. Let Q be the permutahedron of a the convex hull of (oo(1))... (m)) for all permutations a of [m]. Then, the resulting DRO is
134
135
136
(O).
min dEG
1=1
137
Group DRO corresponds to = O,,0,.... 0) and the average top-k worst group losses corresponds (1/k, 0, O). Another example that is contained none of the above examples is
138
times lexicographic minimax fairness (Diana et al. 2021 The goal of lexicographical minimax fairness to find 0 E O such that the sequence (O) L (0)) is lexicographically minimum. This corresponds to a with sufficiently varied entries, i.e., 01 > 02 > >> Omm
140
141
Algorithms
142
In this section, we describe our algorithms. First, we present generic algorithm for general DRO (1) and provide unified convergence analysis in Section [.]] Then, we specialize it into two concrete algorithms for group DRO (2) in Section 3.2 We sketch algorithms for the average of top-k
144
146
group losses and weighted ranking of group loss in Section 3.3
3.1
Algorithm for the general case
We present our algorithm for geranal DRO (T. At high level, our algorithm can be regarded as stochastic no-regret dynamics. Let denote L(0,, q) Em 4i Eg-r, [E(0; 2)]. Imagine that the 8 9-player and g-player run online algorithms Ag and An, respectively, to solve the minimax problem minøge max L(0, q). That is, for t I.
148
150
151
152
0₂ ④ and qe e Q are determined by As and Ay. respectively.
Both players feed gradient estimators Vo,, and Vg,t to Ao and Ag. respectively. Here, E[Vo,] = VoL(O,, 9:) and E q.1 V,L(B,,9:).
159
154
Let
:= = max L(O - min max L(O,g) aeB QEQ
geQ
be the optimality gap of the averaged iterate 01. 1 ΣT fg. We can bound the expected convergence rate E[sr] via regrets Rg and Rg of these online algorithms (see Appendix A for formal definition), i.c.,
156
157
158
Ro + E(R((T)
E G
(3)
T

---

159
We can obtain hence the convergence rate of the above algorithms by investigating the expected regret bounds of these online algorithms.
180
161
To get a concrete algorithm, we must specify the online algorithms As, Ag as well as the gradient estimators Ve,r, Vo..- We use OGD and OMD Ag and A,, respectively, We construct the gradient estimators by sampling 8 ~ q: and 2 ~ Ps. and setting Vo, = Vol(0;; and Vg,t 4t.4, ei.-
((0;z))
163
184
This leads to Algorithm [ There, L : Q + R denotes the regularizer of OMD and TJ,, and "y denote the step sizes of OGD and OMD, respectively. It turns out that this combination of online algorithms and gradient estimators yields the best convergence rate (for group DRO) because the expected regrets of both players are optimal.
185
186
167
Algorithm Algorithm for general DRO (1)
Require: initial solution 0 E O, number of iterations T, step sizes N0, > 0 (t E (T). > 0, and strictly convex function V/ Q IR.
1: Let !1 = (1/m....,
2: for i ,',
3: Sample i
4: Call the stochastic oracle obtain P.c.
5: BG41 + 1aa4-proop proje(0: - n7. V vol(0;;2))
6: (g+())+1)
(((())
{0,; 2), 9++1 + argmin Dy (g. q(+1), where
4tht
(1r y) V(x) ((y) (v) (y x)) is the Bregman divergence with respect V.
7: return Eim1 Or.
188 We now analyze the convergence rate of Algorithm I We make the following standard assumptions. Assumption 1. The loss function E(O: 2) continuously differentiable and G-Liphhitz in 6, and has range [0, for all z. The Euclidean diameter of the feusible region @ is at most D.
189
171
The following theorem follows from plugging regret bounds of OGD and OGD, and the construction of the gradient estimators into (3).
Theorem 1. If 19, is nonincreasing, Algorithm Sanaaimmmaaee Jachievss the expected convergence rate
173
1 E(er] s
G2
T
D2
M
(qt))
max Dv 1/m)
Σ
Tott +
+
4a
E
T 2
2n6Tr
2
7lg
174
formal proof can be found in Appendix We will see how specific choices of the regularizer V yield various algorithms and convergence rates for group DRO and others in the next subsections. A few remarks on the regularizers, step sizes, and projection step are in order.
175
178
177
Although Algorithm works with general V we can choose specific regularizer for Q appearing applications, e.g. the probability simplex, scaled k-set polytope, or a permutahedron.
Regularizer.
178
179
In the next subsections, we show that the entropy regularizer (xx Ex(r; log x; 2;) and Tsallis entropy regularizer (2) 2(1 E. Vxr) yield efficient algorithms with improved convergence
180
rates for these cases.
182
Step sizes. The theorem includes decreasing step sizes such as yjo. mGVT in addition to fixed step sizes. Decreasing step sizes have the advantage that we do not require the knowledge of T the beginning of the algorithm but come the cost of an extra constant factor in the expected convergence rate. Since both step size policies give the asymptotically same convergence rate, we describe only fixed step sizes in the theorems in the next subsections. In practice, decreasing step sizes stabilize the algorithm and often outperform fixed step sizes.
183
184
185
186
187
Projection step. In general, the Bregman projection argmin, as Dg ( is convex, but may be costly to compute. For the applications described in Section 2
189
Q
is a pernutahedron. In this case,
We make a standard assumption that the regularizer V is differentiable and strictly convex, and satisfies +00 as tends to the boundary of Q.
[v(()]]
5

---

Algorithm 2 GDRO-EXP3
Algorithm GDRO-TINE
Require: initial solution 01 θ, number it-
Require:
initial solution 01 E e, number of it- crations T, and step sizes no, > 0 (t [T],
erations T, and step sizes no, 0 (t [T]),
f/ > 0.
> 0.
1: Let Q: (1/m.....) 1/m).
Let ạt (1/m..... 1/m).
2: for ===,, -.....,dd
2: for t 1,=1.-.. 1,.,..,,, ,
3: Sample gc.
Sample i gt.
4: Call the stochastic oracle to obtain ~ P..
4: Call the stochastic oracle to obtain 2 ~ Pi..
5: 0c+1 5 projo(0; - 1/o, V vol(0,;z))
5: Dc41 + proje 11,
6: @++1 - 9r exp
1c+1 < qt
Ro
E(0e; 2)0i,)
7:
90+1 Σ g4t1s"
9113
7: Compute
E
R
such
that
8: return 1 -1 Or.
Σ (Vo++1,) - (1)
-2
=1
7
g++1 (Vgx+1 a1)
-2
9: return
T
1 Ei=1 O2.
190 is known that the Bregman projection with respect to the entropy and Tsallis entropy regularizers can be done in (m log m) time (Lim and Wright 2016). If Q is the probability simplex, have a closed form for the Bregman projection.
192
193
3.2
Algorithms for Group DRO
194
As applications of our generic algorithm, we now describe two concrete algorithms for group DRO and their convergence rates.
195
196
Let V the entropy regularizer, which corresponds to EXP3 algorithm for the q-player. The resulting algorithm, GDRO-EXP3, is shown in Algorithm 2 The update is in closed formula and its complexity is O(m + n) time. The convergence rate follows from Theorem achieves the expected convergence
GDRO-EXP3.
198
Theorem 2. If n a is nonincreasing, GDRO-EXP3 (Algorithm 2
199
200
rate
2 2
D
m.2
log
E OT
S T
1e.t +
+
17
+
(4)
2no.T
7/
201
For 11.
GVT
and Tlg
log mn m we obtain
D2 + 2M log
E(er] < V2
GRDO-TINE.
We further improve the convergence using the Tsallis entropy regularizer at the cost of slightly higher iteration complexity. The update of q₁ is then
203
nay9 E(O.; z)e:.
@++1
1++1= (V
a1
Gt.i
204
where the multiplication, square-root, and power operations are entry-wise and a E IR is the unique solution of equation > (v@ a) 1. The solution a can be computed via the Newton method. Practically, one can use a the previous iteration to warm start the Newton method. In each iteration, the algorithm performs a single orthogonal projection onto O the Newton method for finding a, and Omm + n.) operations to update 0r, gt. The pseudocode is given in Algorithm 3 From Theorem I we obtain the following convergence rate.
205
206
208
210
Theorem 3. e is nonincreasing. GDRO-TINE (Algorithm) 3) achieves the expected convergence
211
rate
G2
D2
Vmn
E G
no.t +
+ VmM I
(5)
T
2
2ToTT
71
t=1

---

212
For ne. GVT
D and nl = MVT we obtain
GGD + 4M
E S v2
VT
Comparison to Sagawa et al. 2020). Our algorithms improve the convergence rate of Sagawa et al. [2020) by a factor of (lym) see Table The reason lies in the choice of gradient estimator. All be
214
gorithmm stochastic no-regret dynamies. As outlined above, their convergence hence bounded by the regrets the players, which depend on the variance of the local norm of the gradient estimators. Their strategy is based
216
uniform sampling that yields variance of (m)) for both players, whereas our bound is O( O(ym) thanks to the gradient estimators tailored to the regularizer of OMD. More details may be found in Appendix D
218
220
3.3
Algorithm for weighted ranking of group losses
221
We now consider a more general case that Q is a permutahedron. Applying Algorithm Tsallis entropy regularizer, obtain the following result.
|
with the
222
Theorem 4. If n is nonincreasing and Q is permutahedron, Algorithu 7 with the Tsallis entropy
224
regularizer achieves the same expected convergence rate as Theorem Furthermore, the iteration complexity is O log n).
226
This implies a convergence rate of O(
G2 M for empirical CVaR optimization, which
improves OVV GDD convergence by Curi er al. [2020]. Furthermore, their iteration
227
complexity is (mm²) due to the k-DPP sampling step, so our algorithm is even faster in terms of
228
iteration complexity.
4 Lower bound
230
states that we can find an e-optimal solution for group DRO in O G calls to stochastic oracles. Next, we show that this query complexity is information theooeeiical optimal.
Theorem 3
232
Let L be a class of convex G-Lipschitz loss functions e > [0, .M. Given loss function E C, 233
and m-set P (P1, ..... ]., of distributions, denote the optimality gap of 0 E θ by R(0, E, P) max E PEP =~P
[e(0; =)] min max E [e(0"; z)]. gr PEP
Let Ar the of algorithms that outputs å making T queries the stochastic oracle. Theorem (Lower Bound).
235
GD VT'
inf sup E E, max B ECC,O,P
M
236
where θ runs over convex sets with diameter D) and P over m-sets of distributions, and Ep denotes 237 the expectation over outcomes of the stochastic oracle in P.
As V x + < V + VD S /2(x + vy) for x, 2 0, this theorem immediately implies that the
238
minimax convergence rate is Ω (V /GDDR4MMP which equals the convergence rate achieved by
239
Algorithm up constant factor.
Proof Sketch. It suffices to show two lower bounds GD and / independently. The former is vT well-known lower bound for stochastic convex optimization [Agarwal et al. 2012). To illustrate the latter, we take an algorithmic dependent point of view via the cam's 's method. For any algorithm in Ar. we need to construct instances Po, Pi such that the total variation distance between the distributions over the query outcomes (they depend on both the behavior of the algorithm and the instance) with respect to Po and P, is small. On the other hand, the objective function of the two
241
242
243
245
7

---

Optimality gap
10-2
Optimality gap
10-2
10
10
10-4
10
10
10
10
10a
10
10
Iteration T
Iteration T
Logistic loss
(b) Hinge loss
Sagawa al.
GDRO-EXP3 GDRO-TINF
Figure 1 Results on Adult dataset
10
50
100
100.05
Objective
10"
100.05
10 1000.05
0.05
100
100
10
105
106
10
10a
10
10
10
106
Iteration T
Iteration T
Iteration T
Sagawa GDRO-EXP3 GDRO-TINE
Figure 2: Results on synthetic dataset
247
instances must be well-separated, i.c., any fixed 0 is ô sub-optimal for either Po or P1. So, any algorithm that solves group DRO up to error å needs to distinguish two instances Po and Pi. This implies a query lower bound because the total variation distance of the outcome distributions of these instances is small. The challenge is how to construct such instances for the regime of small dimensions of e.g, n
249
250
251
this end, we carefully construct linear functions for m groups using opposite slopes. Then, based on the behavior of the algorithm, we tweak the noise bias in one of the groups with a positive slope, in way that any fixed 0 (()) sub-optimal for one of these instances. For the detailed proof, see Appendix
253
5
Experiments
296
this section, we compare our algorithms with the known algorithm using real-world and synthetic datasets. We follow the setup in [Namkoong and Duchi 2016
Adult dataset. For the real-worke dataset, we use Adult dataset [Dua and Graff 2017 0 The dataset consists of age, gender, race, educational background, and many other attributes of 48, 842 individuals from US census. The task is to predict whether the person's 's income is greater than 50, 000 USD 260
258
or not. We set up 6 groups based on the race and gender attributes: each group corresponds to a combination of (black, white, others) x {female, male). Converting the categorical features to obtain 101-dimensional feature vector R" (n 101) for each individual. We train the linear model with the logistic loss and hinge loss functions. The group-DRO objective is the worst empirical loss over the 6 groups:
262
dummy variables,
284
Σ ((0;a,b)
max
(a.M)ET
where 7; the set of data points in the ith group. The feasible region is set to the Fuclidean ball of 286
radius D 10.

---

288
Synthetic dataset. To observe the performance of the algorithms over the regime of high- sigh-dimension model parameters and the larger number of groups, we also conducted experiments using the following synthetic instances. First, we set n 500 and varied m E {10, 50, 100]. For each group i E [ml] we generated the true classifier fr E IR from the uniform distribution over the unit sphere RR. The ith
269
271
272
group distribution P; was the empirical distribution of 1,000 data points, where each data point (a, b)
273
was drawn ~ (0,, In) and b sign(a' 07) with probability 0.9 and
sign(a" 0,) with probability 0.1. We trained the linear model with the hinge loss function. Finally, the group-DRO
274
275
objective is
max (a.
E
16(0;a, a, b]]-
278
The feasible region is set the Euclidean ball of radius D 10.
277
5.1
Algorithms
We implemented GIRO-EXP3, GDRO-TINE, and the algorithm in (Sagawa al. We ran our algorithms for T =2,000,000 iterations.
2020 in Python.
279
Inner online algorithms. is known that EXP3 has a variance as large as O Lattimore and Szepesvári 2020]. Therefore, vanilla EXP3 often fails to achieve a sublinear regret even though it achieves O (VT)) regret in expectation. This large variance makes it difficult to reliably evaluate the performance of the algorithms. To stabilize the algorithms, we replaced EXP3 with its variation,
280
282
285
EXP3P (Auer er al. ) which achieves ((VT) regret with high probability. Note that this change does not harm our expected convergence bounds.
284
286
Step sizes. The choice of step sizes crucial to the practical performance of first-order methods.
We found that the decreasing step size T7, ~ 1/vē for 0g and the fixed step size 17 ~ 1/vT for
287
4e gave the best results. More precisely, we set VJo,: vt
Co (1 E (T) and 14 Cg V mll"
log m
where
289
C. E [0.1, and C. 3.01 are hyper-parameters tuned for each algorithm. We used the best hyper-parameter found by Optuna [Akiba et al. 2019] for the shown results.
281 Mini-batch.
The use of mini-hatch often improves the stability of stochastic gradient algorithms. In experiments, we used mini-batches of size 10 to evaluate stochastic gradients. Neither the objective values of outputs nor the stability was improved with larger mini-batch sizes. The group DRO objective evaluated using the entire dataset.
293
294
295
Initialization.
For both datasets, we initialized the algorithms with 01 = 0.
5.2
Results
297
We show the results of our experiment in Figures I and
Adult dataset. In Figure I we plot the optimality gap of the averaged iterate ET= Og against the number of iteration T. We observe that all the algorithms converge with rate roughly 005 for both loss functions, consistent with our convergence bound. Furthermore, our algorithms (GDRO-EX) EXX3 and GDRO-TINF) achieve faster convergence compared to the algorithm by (Sagawa et al. (2020) Interestingly, GDRO-TINF achieves a 10 optimality gap in T = 106 iterations, which is faster than the theoretical 005 rate in Theorem
300
302
303
304
we plot the objective values of the averaged iterate against the number iterations. For all the values of m. our algorithms (especially GDRO-EXP3) consistently achieve smaller loss values faster than the known algorithm. The performance gap between our algorithms and the known algorithm increased as m grows, which verifies that our algorithms have better dependence on m in the convergence rate.
Synthetic dataset. In Figure 2
305
307

---

References
309
310
Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transac- tions on Information Theory, pages 3235-3249, 2012.
312
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
314
316
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2003.
318
Yujia Bao, Shiyu Chang, and Regina Barzilay. Predict then interpolate: A simple algorithm to learn stable classifiers. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 640-650, 2021.
320
321
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Programming, 167(():235 292, 2018.
322
323
Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust wasserstein profile inference and applica- tions to machine learning. Journal of Applied Probability, 56(3):830 857, 2019.
324
325
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, pages 77-91, 2018.
328
327
Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Proceedings of 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 866-882, 2021.
329
330
331
Nicolo Cesa- Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
332
333
Sebastian Curi, Kfir Y. Levy, Stefanic Jegelka, and Andreas Krause. Adaptive sampling for stochastic risk-averse learning. In Advances in Neural Information Processing Systems, pages 1036-1047, 2020.
335
Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, and Saced Sharifi- Malvajerdi. Lexicographically fair learning: Algorithms and generalization. In Proceedings of the 2nd Symposium on Foundations of Responsible Computing, pages 6: 1-6:23,, 2021.
337
339
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
340
John C. Duchi and Hongseok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 49(3):1378 1406. 2021.
341
342
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115-16) 2018.
343
344
Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approximations. Operations Research, 58844-pat--))9002-9777 2010.
346
Tatsunori Hashimoto, Megha Srivastava. Hongseok Namkoong, and Percy Liang, Fairness without demographics in repeated loss minimization. In Proceedings of the 35th International Conference on Machine Learning, pages 1929-19388 2018
348
349
350
Elad Hazan. Introduction to Online Convex Optimization. 2016.
Dirk Hovy and Anders Søgaard. 'aagiig performance correlates with author age. In Proceedings of the 53d Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 483-488, 2015.
352
10

---

354
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In Proceedings of the 35th International Conference on Machine Learning, pages 2029-20222022 20372037,22200 2018.
355
356
Jikai Jin, Bohang Zhang. Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non- -on-asymptotic analysis. In Advances in Neural Information Processing Systems, volume 34, pages 2771-2782. 2021.
358
360
David Jurgens, Yulia Tsvetkov, and Dan Jurafsky, Incorporating dialectal variability for socially equitable language identification. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 51-57, 2017.
351
382
363
Johannes Kirschner, Ilija Bogunovie, Stefanie Jegelka, and Andreas Krause. Distributionally ro- bust bayesian optimization. In Proceedings of the 33rd International Conference on Artificial Intelligence and Statisties, pages 1174-21844 2020.
364
385
386
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
387
Cong Han Lim and Stephen J. Wright. Efficient bregman projections onto the permutahedron and related polytopes. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 1213,,, 2016.
368
389
370
Natalia L Martinez, Martin A Bertran, Afroditi Papadaki, Miguel Rodrigues, and Guillermo Sapiro. Blind pareto fairness and subgroup robustness. In Proceedings of the 38th International Conference on Machine Learning. pages 7492-7501, 2021.
371
372
373
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, 2016.
374
375
Yonatan Oren, Shiori Sagawa, Tatsunori Hashimoto, and Percy Liang. Distributionally robust language modeling. In Proceedings of the Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP), pages 4227-4237, 2019.
377
378
379 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 Advances in Neural Information Processing Systems, volume 34, pages 10067-10080, 2021.
380
381
382
Al eexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, 2013.
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. In The 8th International Conference on Learning Representations, 2020.
385
386
387
Herbert Scarf. A min-max solution of an inventory problem. Studies in the mathematical theory of inventory and production, 1958.
388
389
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. In Advances Neural Information Processing Systems, 2019.
390
391 Matthew Staib, Bryan Wilder, and Stefanie Jegelka. Distributionally robust submodular maximization. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 506-516, 516, 2019.
393
394
Robert Williamson and Aditya Menon. Fairness risk measures. In Proceedings of the 36th Interna- tional Conference on Machine Learning, pages 6786-6799 (066-677,222 2019.
396
Jingzhao Zhang, Aditya Krishna Menon, Andreas Veit, Srinadh Bhojanapalli. Sanjiv Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. In The 9th International Conference on Learning Representations, 2021.
387
398
399
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 12(28):1-49) 2021.

---

401
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Pro- ceedings of the 20th International Conference on International Conference on Machine Learning. pages 928-935, 2003.
402
Checklist
404
1. For all authors...
408
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
407
408
(b) Did you describe the limitations of your work? [No]
409
(c) Did you discuss any potential negative societal impacts of your work? [No] This paper
410
a theoretical paper.
411
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
413
2. If you are including theoretical results...
414
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion
416
(b) Did you include complete proof's of all theoretical results? [Yes] Ommited Proof can be found in the supplemental material.
417
418
3. If you ran experiments...
419
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The experiment code can be found in the supplemental material.
420
421
422
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section [
424
(c) Did you report error bars (e.g., with respect the random seed after running experi-
425
ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
427
428
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
430
(b) Did you mention the license of the assets? [Yes]
431
(c) Did you include any new assets either the supplemental material or as URL? [No]
432
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We used public dataset.
434
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
435
436
5. If you used crowdsourcing or conducted research with human subjects...
437
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No] Not applicable
(b) DidNo describe any potential participant risks, with links Institutional Review Board
440
(IRB) approvals, if applicable? [No]
441
(c) DidNo include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No]
442
12


Reviews:
[{"review_id": "lSxj-kCwY_L", "reviewer": "Reviewer_oPHP", "summary": "The paper proposes an algorithm for a two-player zero-sum game based on stochastic no-regret dynamics which achieves a faster convergence rate than existing algorithms for group DRO problems. They further show that their bound is tight for group DRO. \n", "questions": "# Major Comments\n\n1) Throughout the paper formulation of \"distributionally robust optimization\" and \"group distributionally robust optimization\" terms are used interchangeably, which I find very confusing.\nFor example, in Line 21, the reference to general DRO problems is not precise. This paper studies the general formulation of group DRO problems because the problem introduced in (1) is already a group distributionally robust optimization problem, which is different from than traditionally studied distributionally robust optimization problem.\nA similar problem occurs in Line 148, Line 143, in the title of  Algorithm 1, and so on.\n\nTo avoid confusion, the problem formulated in (1) could be called a general formulation for group distributionally robust optimization. \n\n2) I am not entirely sure why $q_t$ is removed from the objective in the gradient update of $\\theta_t$.\nIs it common to apply such a technique in two-player games?\nI am not sure if the unbiasedness of the gradient estimates goes through in that case.\n\n3) I do not think the related literature for online stochastic games is covered fully. I suggest the authors to extend this part. \n\n\n4) It is not clear what is $f$ in Section A.1.\n\n5) I cannot follow the correctness of proofs because of a couple of reasons.\n\t\t- I could not see proofs for Lemma 1, 2, 3, and 4. If these lemmas are proved in a reference, please indicate them. \n\t\t- The proofs of the theorems are dependent on these lemmas.  \n\n## Minor Comments: \n\n1) The sentence in Line 125 is neither rigorous nor clear. Please clarify this sentence.\n", "limitations": "The authors did not study the limitations of their work. \n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written.\n\nThe idea seems original, however, I am not entirely sure if there is an algorithm in the multi-arm bandits that has the same convergence rate. If not this result can be seen as a contribution to the two-player stochastic online learning problems. \nI highlight the need for a comprehensive literature review. Please see my comments below.\n\nI appreciate that the authors put a separate section about the algorithm that is the most related to their work and provide a simple proof for the convergence of the competitive algorithm. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EWm_lsZerKL", "reviewer": "Reviewer_Uz3v", "summary": "This paper studies a generalized notion of distributionally robust optimization (DRO). In particular, the mixing weights for different data distributions ($m$ groups) can belong to arbitrary subsets $Q$ of the simplex $\\Delta_m$ as long as $Q$ also contains uniform mixing weights $\\frac{1}{M}\\cdot \\mathbb{1}$. Thus, popular DRO objectives such as group-DRO, etc., are special cases of this objective. \n\nThe paper casts this objective as a two-player game and uses stochastic gradient methods to obtain convergence guarantees for the optimality gap. The players' algorithms are simple online gradient and mirror descent algorithms with appropriate regularization. For the particular case of group-DRO, their rates improve upon the best-known rate by $\\sqrt{m}$. The paper also presents a novel lower bound, showing that their algorithm has an optimal convergence under their assumptions.  ", "questions": "1) The authors use mini-batching in the experiments, but the theory doesn't have any mini-batching. I would guess that under the assumptions of $G$-lipschitzness and compact parameter space, it is hard to show such a benefit theoretically? If this is true, could some other assumptions show an improvement (such as smooth, non-Lipschitz functions)? I understand this might is a more fundamental question for online convex optimization.\n\n2)  I believe a much more extensive empirical evaluation is possible here, particularly on data sets widely used in the fairness/robustness community. Since the theoretical results are not very hard to attain and are positive, it would be good to see that the simple algorithms outperform known algorithms on a broad range of tasks. It would also be good to see these experiments on data sets where the general objective proposed in the paper makes more sense than group DRO, etc.  ", "limitations": "No apparent negative societal impacts. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the presentation of the paper: discussion of the related work and their connections in section two, review of current convergence rates, and discussion of algorithm design and results. The result is clean and also shown to be optimal for group DRO. \n\nMy main concern is that the algorithmic insight here is just casting the objective as a two-player game and using the correct regularizer for OMD. On the one hand, the simplicity is excellent (and OCO theory itself is known to be clean and simple), but on the other, I feel that the techniques and analysis used are not novel. This is apparent in the proof of the upper bounds, which immediately follow from known convergence lemmas. The lower bound is more interesting, and the analysis idea looks more novel. This is why I give the paper a weak acceptance. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4N3DRIWnVkf", "reviewer": "Reviewer_xXcs", "summary": "This paper proposes a general class of DRO that includes Group DRO, subpopulation fairness, empirical conditional value at risk optimization and others, and the stochastic gradient learning algorithms under these frameworks. As the convergence rates shown in the previous studies are improved, the proposed algorithms are efficient, and especially, it is theoretically shown that the optimal convergence rate is achieved under the Group DRO framework. This allows to superior performance over a baseline in the Adult and synthetic datasets, which are aligned with theoretical results.", "questions": "* Due to its methodological simplicity, it seems that the proposed algorithms have the advantage of being applicable to a variety of datasets.\n* The background for adopting the synthetic dataset was to confirm the performance of the proposed algorithm in the high-dimensional model scenario. For the readers, it seems better to utilize natural network architectures rather than only linear models. (e.g., [1] used ResNet50 for image datasets and BERT for language dataset.)\n* The introduction of oracle makes a difference in terms of the setting in consideration from the existing methods, so it would be good to add a discussion on this.\n\n[1]: (Sagawa et al.) Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.", "limitations": "Limitations (e.g., some consideration in practice) are not specified, as mentioned in the checklist.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n* This paper is clearly written in overall.\n* It is interesting to combine online learning algorithms and appropriate gradient estimators in the scenario, where the group distributions are given by the stochastic oracles.\n* It differs from previous studies in that it derives algorithms and theoretical results for online learning scenarios with stochastic functions.\n* The introduction of the weighted ranking of group losses (general DRO) seems natural after Group DRO and empirical CVaR optimization.\n* This paper shows several theoretical results including improvement of convergence rate compared to existing studies through the proposed algorithms and corresponding convergence analysis.\n\n[Weaknesses]\n* Compared to the theoretical results, experimental analysis and setting seem to be insufficient. (e.g., Accuracy, the number of random seeds, corresponding standard deviations can also be reported in the Appendix.)\n* Line 129: ‘p=m/k’ → ‘p=k/m’", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0nluoTQP-yx", "reviewer": "Reviewer_CKHk", "summary": "In this paper the authors introduce new algorithms to solve a set of DRO problems consisting of Group DRO, Empirical CVar and Weighted Ranking problems. Their algorithms treats the problems as a two player game between players of the minimization and maximization problems. They leverage Online Gradient Descent and Online mirror descent for each of these respectively.  \nThey also develop DRO instances which show a lower bound the queries required for objective performance. The bound the best possible performance of any algorithm for the Group DRO problem. \n", "questions": "What is the evaluation of the methods of this paper on other real world data sets. \nWhat is the comparison to other methods to solve DRO problems beyond those introduced in Sagawa et al. \nWhat are practical applications of the Group DRO, Empirical CVaR and other mentioned problems. How is the performance of the algorithm on the real world instances of these problems. ", "limitations": "The authors do not discuss any limitations of their work. Though I doubt the existence of negative societal impact, it would be interesting to see any differences in the solutions obtained by their method as compared to Sagawa. Do this focus on different aspects etc. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I feel the paper is original as it provides new and innovative algorithms for existing problems. \n\nQuality: I feel the paper is technically sound. The novel algorithms provided in the paper improve upon existing methods and these aspects are illustrated through theoretical and numerical results. However, I feel that the numerical section is quite limited with only 1 real data set. Expanding this section will significantly improve the quality of the paper. \n\nClarity: I think the paper is well written and clearly communicates the various assumptions, results, numerical experiments etc. \n\nSignificance: I feel the paper is important as it takes a step forward in solve practical DRO problems by identifying new algorithms for the DRO problems. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject