Distributionally Robust Optimization via Ball Oracle Acceleration
Authors: Yair Carmon
Danielle Hausler
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
distributionally robust optimization
theory
oracle complexity
monteiro-svaiter acceleration
accelerated methods
algorithm design
entropy regularization
multilevel monte-carlo

Abstract: We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. In particular, we consider group-structured and bounded $f$-divergence uncertainty sets. Our approach relies on an accelerated method that queries a ball optimization oracle, i.e., a subroutine that minimizes the objective within a small ball around the query point. Our main contribution is efficient implementations of this oracle for DRO objectives. For DRO with $N$ non-smooth loss functions, the resulting algorithms find an $\epsilon$-accurate solution with  $\widetilde{O}\left(N\epsilon^{-2/3} + \epsilon^{-2}\right)$ first-order oracle queries to individual loss functions. Compared to existing algorithms for this problem, we improve complexity by a factor of up to $\epsilon^{-4/3}$.

Distributionally Robust Optimization via Ball Oracle Acceleration
Yair Carmon Tel Aviv University ycarmon@tauex, tau. ac i1
Danielle Hausler Tel Aviv University hausler@mail tau ac
Abstract
We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. In particular, we consider group-structured and bounded f- divergence uncertainty sets. Our approach relies on an accelerated method that queries ball optimization oracle, i.e., a subroutine that minimizes the objec- tive within small ball around the query point. Our main contribution ef- ficient implementations of this oracle for DRO objectives. For DRO with N non-smooth loss functions, the resulting algorithms find an e-accurate solution with Ô (Ne 2/3 + + first-order oracle queries to individual loss functions. Com- pared existing algorithms for this problem, improve complexity by factor of up to -4/3
Introduction
The increasing use of machine learning models in high-stakes applications highlights the importance of reliable performance across changing domains and populations [11, 46, 35]. An emerging body of research addresses this challenge by replacing Empirical Risk Minimization (ERM) with Dis- tributionally Robust Optimization (DRO) [6, 50, 49, 22, 40], with applications in natural language processing [47, 61, 35], reinforcement learning [17, 54] and algorithmic fairness [27, 56]. While ERM minimizes the average training loss, DRO minimizes the worst-case expected loss over all probability distributions an uncertainty set U, that is, minimizes
CDRO(2) (x) sup [s~o[(s(x)). Qeu
where (1) is the loss a model x E X' incurs on a sample S and X' is closed convex set with bounded Euclidean diameter. This work develops new algorithms for DRO. focusing on formulations where UI contains distributions supported on N training points, where N is potentially large. We consider two well-studied DRO variants: (1) Group DRO [57, 31, 49], and (2) f-divergence DRO
[19, 6, 22].
Group DRO Machine learning models may rely on spurious correlations (that hold for most training examples but are wrongly linked to the target) and therefore suffer high loss on minority groups where these correlations do not hold [30, 27, 11]. To obtain high performance across all groups, Group DRO minimizes the worst-case loss over groups. Given a set U = {wi,.... WM} } of M distributions over [N], the Group DRO objective is!
N
(z) = max Ejiw: (z(x) max rE[M]
(x)
(2)
M
'Typically, each w, is uniform over subset ("group") of the N training points. However, most approaches (and ours included) extend to the setting of arbitrary w. 's, which was previously considered in [57].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Smoothness
Method
Group DRO (2)
f f-divergence DRO (3)
Subgradient method [45]
Ne-2
N
None (I. = oo)
Stoch. primal-dual [43]
M
Ne
MLMC stoch. gradient [39]
pE- or a c Ne-2/3 +E-
Ours
NE-2/3 2/3 +E-
AGD on softmax [44]
Nc-1
Ne
Weak (L R 1/c)
Ours
Ne- + N3/4
2/-2/3 2/3 + VNe-1
Table 1. Number of Ve; and 4 evaluations to obtain E[Crao (x)] ming.ex CORO S where N is the number of training points and (for Group DRO) M is the number of groups. The stated rates omit constant and polylogarithmic factors. Requires an additional uniform bound on losses (see Appendix A. These rates hold only for specitic f-divergences: divergence with size p. respectively.
CVRR at level a or X²
If we define the loss of group Lx(x)) Σx (x)((() then objective (2) is equivalent to max ΣiEl (zLe(z) with AM = {q E R gT = 1}. Note that, unlike ERM, Group DRO requires additional supervision in the form of subgroup identities encoded by (w:).
DRO with f-divergence Another approach to DRO, which requires only as much supervision as ERM, takes 21 to be an f-divergence ball around the empirical (training) distribution. For every convex function f : R + I U {+ such that f(1) = O, f(0/0) = and the f-divergence between distributions q and p over [N] is (q. = EiE(N (q./..) The f-divergence DRO problem corresponds to the uncertainty set 21 = {1 E AN DD(g, N 1)) S 11,,ie.
L- (x)
max REAM: & EMEM S(NN)S
Σ q.((()). NE[N]
Several well-studied instances of DRO are a special case of this formulation, with the two most notable examples being conditional value at risk (CVaR) and x² uncertainty sets. CVaR at level corresponds to (xx = 1 ( } such that U {q E A s.t || S 1/(aN)}. and has many
applications in finance such as portfolio optimization and credit risk evaluation [48, 37] as well as in machine learning [47, 39, 20, 60, 17, 54]. The x² uncertainty set with size p 0 corresponds to fx) := 2p (x 1)² and the resulting DRO problem is closely linked to variance regularization [21] and has been extensively studied in statistics and machine learning [42, 27, 21, 39, 61].
methods for solving the convex problems (2) and (3) under the assumption that the loss E, is convex and Lipschitz for all We measure complexity by the (expected) required number of (x()) and (1x(z) evaluations to obtain e-suboptimal solution, i.e., return x such that (z) ming, Ex (IRO( S e with constant probability. Table summarizes our complexity bounds and compares them to prior art. Throughout
Complexity notion In this paper, design suproved-compless
the introduction we assume (for simplicity) a unit domain size (| yll < for all x, y E X²) and that each loss is 1-Lipschitz.
Prior art Let us review existing methods that solve Group DRO and f -ddieergence DRO problems (see Section 1.1 for extended discussion). For a dataset with N training points, the subgradient method [45] finds an approximate solution in c -2 iterations. Computing single subgradient costs N functions evaluations (since need to find the maximizing q). Therefore, the complexity of this method is ONE-2)
DRO can also be viewed as game between a minimizing playee and maximizing q-player, which makes it amenable to primal-dual methods [43, 42, 49]. If we further assume that the losses are bounded then, for E A",, stochastic mirror descent with local norms obtains regret bound of 0(
(see Appendix A. As a consequence, for Group DRO (where m M) the complexity is Ô(M and for /-divergence DRO (m = N) the complexity is Ō(Ne-2).
Levy et al. [39] studied "-ddieereence and CVaR DRO problems, and proposed using standard gradient methods with a gradient estimator based on multilevel Monte Carlo (MLMC) [9]. For x² divdivereence with ball of size P they proved complexity bound of Ö(pe-3) and for CVaR at

---

level a they established complexity 9))) However, for large uncertainty sets (when p or a" approach N) their method does not improve over the subgradient method.
Stronger complexity bounds are available under the weak smoothness assumption that each L has ((-''--ipsccitzz gradient. Note that this is weak assumption since if function é is not continuously differentiable, it is possible to approximate & with additive error most c/2, by its Moreau envelope f(x) min ((v) + G²
2. || u1l?) (see [15, Appendix A.1] for more details). In particular, we can apply Nesterov's i accelcrated gradient descent method [44] on an entropy-regularized version of our objective to solve the problem with complexity ( )) see
Appendix A.2 for more details.
Our contribution We propose algorithms that solve the problems (2) and (3) with complexity O(Nc-2/3 + 2) Compared to previous works, we obtain better convergence rates for DRO with general f-divergence when N > 1 and for Group DRO when M > N/4/3 When the losses have O(c L-ipschiis gradient, we solve f-divergence DRO with complexity Ö(Ne-2/3 + VNc- and, under an even weaker mean-square smoothness assumption (Ej-w; [+)(()) - vez(y)12 S - y for all x, y and i), we solve Group DRO with complexity ONN 2/3 + N3)
Our complexity bounds are independent of the structure of f and {w:},, allowing us to consider arbitrarily J-divergence balls and support a large number of (potentially overlapping) groups. Our rates optimal up to logarithmic factors for the special case of minimizing max4e[N] (xr). which corresponds to Group DRO with N distinct groups and f-divergence DRO with f = 0 [58, 62, 15].
Our approach Our algorithms are based on a technique for acceleration with ball optimization oracle, introduced by Carmon et al. [13] and further developed in [15, 3]. Given a function F' and query point x, the ball optimization oracle returns an approximate minimizer of F inside ball around x with radius r; the works [13, 15, 3] show how to minimize F using ((r-2/3) oracle calls. Our development consists of efficiently implementing ball oracles with radius r = Ö(e) for the DRO problems (2) and (3), leveraging the small ball constraint to apply stochastic gradient estimators that would have exponential variance and/or cost without it.
Carmon et al. [15] previously executed this strategy for minimizing the maximum loss, i.c., max,E Ex (x)), which a special case of both Group DRO and f-divergence DRO. How- ever, the ball-oracle implementations of [15] do not directly apply to the DRO problems that we consider; our oracle implementations differ significantly and intimately rely on the Group DRO and f-divergence problem structure. We now briefly review the main differences between our approach and [15], highlighting our key technical innovations along the way.
Since the Group DRO objective is max Σ, (x) for (x))= -Ej=- EjE[N] (x),, one may naively apply the technique of [15] with L, replacing f, However, every step of such a method would involve computing quantities of the form ex)(e) (for some e' = θ(e)), which can be up to N times more expensive than computing ef)())/e' for single j. To avoid such expensive computation we use MLMC [9] to obtain an unbiased estimate of cf((s)/ with complexity O(1) and appropriately bounded variance. In the weakly- smooth case we also adapt our estimator to facilitate variance reduction [33, 2].
For f-divergence we consider the well-known dual form [6, 50]
Σ (a((())) - ((a)) = min REAN ME[M]
T(. v) = M'> (e(x))) +
max
vER
(E(M]
where vi (v) max:zo - }t)} is the Fenchel dual of tb. Stochastic gradient methods applied directly on the dual formulation are notoriously unstable (see e.g., [42]). This is due to the fact that the Fenchel dual 3* can be very badly behaved even for standard f-divergences. We solve this v.. Our techniques rely on two technical observations: (i) log(v?'(-) is 1/c' for all convex dh and (ii) for I-Lipschitz losses, y (x) = argmin YR T(x, y) satisfies ly" (x) (x')l < || x'Il for all x. x'. To the best of our knowledge, these observations are new and potentially of independent interest.
problem by (a) considering a small ball, (b) mntropy-rreglaaiing
Paper organization. Section provides notation and a concise summary of the ball acceleration framework (largely taken from prior work) on which we build our algorithms. Sections 3 and 4
3

---

present our main contributions in the Group and f-divergence DRO settings, respectively. Finally, Section 5 concludes with discussion on the limitations and possible extensions of our work.
1.1 Additional related work
MLMC estimators The multilevel Monte Carlo (MLMC) technique was introduced by Giles [26] and Heinrich [29] in order reduce the computational cost of Monte Carlo estimation of integrals. Blanchet and Glynn [9] extended this technique estimating functions of expectation and proposed several applications, including stochastic optimization [10]. In this work we use their estimator for two distinct purposes: (1) obtaining unbiased Moreau envelope gradient estimates for ball oracle acceleration as proposed by Asi et al. [3]. and (2) estimating the exponential of an expectation for Group DRO. Levy et al. [39] also rely on MLMC for DRO, but quite differently than we do: they directly estimate the DRO objective gradient via MLMC, while we estimate different quantities.
Other DRO methods Several additional works proposed algorithms with theoretical guarantees for f-divergence DRO. Jin et al. [32] considered non-convex and smooth losses. Song et al. [53] proposed an algorithm for linear models with complexity comparable to the "AGD on softmax" approach (Appendix A.2). Namkoong and Duchi [42] proposed a primal-dual algorithm that is suitable for small uncertainty x² sets (with size p < T and Curi et al. [20] proposed a primal-dual algorithm specialized for CVaR. Other works consider DRO with uncertainty sets defined using the Wasserstein distance [24, 23, 51, 34]. Another relevant line of works proposes refinements for DRO that address some of the challenges in applying it to learning problems [60, 59, 55].
2 Preliminaries
Notation We write ||||| for the Euclidean norm. We denote by (x)) ) the Euclidean ball of radius around To. We let A = {q E R l"q 1} denote the probability simplex in R For the sequence 2m...., Zn, we use the shorthand zm Using F as a generie placeholder (typically for a loss function (,), we make frequent use of the following assumption.
Assumption The function F X IR is convex and G-Lipschitz, i.e., for all x, X have [F(x) - Fly) & Gl|zz - yll- In addition, the domain is a closed and corvex set, and it has Euclidean diameter most R.
Throughout, N denotes the number of losses and, in Section 3, M denotes the number of groups. We use e for our target accuracy and r. == e//G for the ball radius, where = e/(2 M) for Group-DRO (Section 3) and e' = e/ log N) for f-divergence DRO (Section 4).
Complexity model We measure an algorithm's 's complexity by its expected number of l, and V4, evaluations; bounds on expected evaluation number can be readily converted to more standard probability bounds [see 3, Appendix A.3]. Moreover if X' C Rdd 2log N),² and the time to evaluate E, and Vl; is Od)) the expected runtime of all the algorithms we consider is at most d times the evaluation complexity.
2.1 Ball oracle acceleration
We now briefly summarize the complexity bounds given by the framework of [13, 15, 3] for acceler- ated minimization using queries to (inexact) ball optimization oracles, defined as follows.
Definition An algorithum is a Ball Regularized Optimization Oracle of radius r (r-BROO) for function F P:A. X - R for query point a E X, regularization parameter X > O and desired accuracy > 0 returns Ox.(T) E X satisfying
X E B[F(OAO(E)) + (10xs(0) - -ai]
min (E)
F(x)
-11 E11
(4)
Proposition 1. Let F satisfy Assumption 1, let CF be the complexity of evaluating F exactly, and let Cx(8) bound the complexity of an r-BROO query with 8, X. Assume that Cx(6) non- increasing in X and at most polynomial in 1/8. For any e > 0. Algorithu 1 returns I such that
'The assumption d = 2ilog N) is only necessary for our results on f-divergence DRO (Section 4), where the runtime of computing argmingeR T(x, is O(Nd + N log N) due to the need to sort the losses.

---

F(x) minz,ex Ex F(x.) S with probability at least 2 For (log GR² mit
and Am
). the complexity of the algorithm is 0 (373))1))
me (C2mn (r) Cp)mm? )
R
2/3
me
(5)
23/2m²
1=0
Informally, the proposition shows that (((R/r)2/3) BROO calls with = (r R2/3)) and accuracy 8 8= (rr) suffice to find an e-accurate solution. As we show in the sequel, for Cx = Ö(N () the resulting complexity bound is Ó [V 2 +
() The summation over
j in bound (5) stems from the use of MLMC to de-bias the BROO output (i.e., make it exact in expectation): compared to the original proposal of Asi et al. [3], our version of the procedure in Appendix B slightly alters this MLMC scheme by de- be-biising one accurate BROO call instead of averaging many inaccurate de-biased calls, improving our bounds by logarithmic factors.
3 Group DRO
In this section we develop our BROO implementations for the Group DRO objective (2). Section 3.1 describe an "'xpoonntiaatd "roup-softmax" function that approximates Cg-DRO with additive error at most e/2. We then apply stochastic gradient methods on this function to obtain BROO implementations that yield improved rates for Group DRO via Proposition 1: we first consider the non-smooth case in Section 3.2 and then the weakly-smooth case Section 3.3.
3.1 Exponentiated group-softmax
Given a cheap and unbiased stochastic gradient estimator of V Vg DRO. we could use a variant of SGD and minimize Lg LRD to e-suboptimal solution using O O(E-2) steps. However, obtaining an unbiased estimator is challenging due the maximum operator in LR. As first step we use entropy smoothing [7, 8, 5, 4] to replace the maximum in Lg-DRO with the softmax operation. More specifically, we use the trick from [15] and minimize the "exponentiated softmax" (that has the form of weighted finite sum) within small ball. For target accuracy e, regularization parameter À 2 0, center point& X and =nd''=e/2 log M) > 0, the (regularized) group-softmax function
=
Lamax,e, (xx) = é' log
Σ ME[M
2/ where Li(x)
Σ (x)l((x). (6)
JE[N]
We will implement BROO for Lemax,e ==
Lymaxxe,, which is a uniform approximation of Lg (oo)) Lamaxx (x) S c/2 for all x E X;; see Appendix C.1 for details.
The (regularized) exponentiated group-softmax is
(xx(x) = Σ Pri( where x((x)= = e'e 22()) 2((0) 41= ala
and pi
E
RE[M]
In the following lemma (easily) extend Carmon al. [15, Lemma 1] exponentiated group- softmax, showing that I e',, is well-behaved inside a ball of (appropriately small) radius r around B and facilitates minimizing Lsmaxx,,,, in that ball; Appendix C. for the proof.
Lemma 1. Let each l; satisfy Assumption 1, and consider the restriction of Lamax.e (6) and Te.x (7) to (T). Then the functions have the same minimizer x, BB) and, i ((Grr) and < OOe' then (a) Fe,x is (())) strongly convex, (b) each 74 is ( Lipschitz and for every x E (z) we have (=max.ex(x)) Lamax.t.Xx..) I ((T,,((z)) -o) Tx.))
3.2 BROO implementation for Group DRO non-smooth losses
To motivate our BROO implementation, let us review how [15] use the exponentiated softmax in the special case of size- groups, i.e., L. é, and explain the difficulty that their approach faces when the group structure is introduced. The BROO implementation in [15] is based on SGD variant with the stochastic gradient estimator ((x) (B)))= V V where i pi. However, for
5

---

Group DRO where L; = EJE(N] Wiylz, the estimator ğ(x) can be up to N times more expensive to compute. Approximating ((x)) by drawing j.J' ~ w; and taking ((((())) Vty will result in biased estimator since Eiiw, (tr,,,e(((())))))))
* L, To address this challenge propose a new gradient estimator based on the multilevel Monte Carlo (MLMC) method [9].
The MLMC unbiased estimator for ((xx) = (((.(())-(())))) which we denote by M[x(x)). is
defined as follows:
D2.
Draw J ~ Geom(1 (1- vz) v Sn dd wa and let M(7[(>)] == Si; +
P.
where p= j) =)= (1- and, for 2N, we define
Dr 7(; 9 ST:
+7 Sm S2/21) and ((;; = 6 e 25-1 68, 10,00)-8 (0) 211
2
With the MLMC estimator for in hand, we estimate the gradient of T',,A as follows:
Draw ~ p(ă) j ~ wi and set g(x) = (VE + A(x - -i).
(8)
In the following lemma we summarize the important properties of the MLMC and gradient estimators; see Appendix C.2 for the proof.
Let each & satisfy Assumption I, and let S &, X and x E BT) Then M(ns(1)] and ((x) are unbiased for w(x) and (T), respectively, and have bounded second moments: E [=M[+ S (0""la + +²²²) and R[(Í()))) S O In addition, the complexity of
Lemma 2.
computing M[)((>)] and ((x) is O())
Due to Lemma 2 and since Fe,, is (((A)-strongly convex, of Hazan and Kale [28] with our gradient estimator (8). This algorithm has rate of convergence (GT)/(XT) and our gradient estimator requires additional N function evaluations for precomputing the sampling probabilities {p.). We thus arrive at the following complexity bound.
the Epoch-SGD algorithm
Theorem Let each l satisfy Assumption 1, let e, > and let r. = e/(2G log M). For any query point ã Rd, regularization strength X S O(G/r.) and accuracy 5, EpochSGD 128, Algorithm 1J) with the gradient estimator (8) outputs a valid BBROO response and has complexity (x) = O(N + ) Consequently, the complexity of finding e-suboptimal minimizer of Lg-DRO (2) with probability least
GR
2/3
GR
2
log² H where H M GR
N
log 11/3 H +
We provide the proof for Theorem in Appendix C.3; the final complexity bound follows from straightforward calculations which we now briefly outline. According to Proposition 1, finding an
paale (((R/r.)) 2/3) BROO calls with accuracy = ārr22 J/2) and regularization strength À 2 Am- where J = min (omm(G))))))) m). We may therefore bound the complexity of each such call by
-suuboptiall solution for Lsmax,e (and consequently an e-suboptimal solution for Lg-DRO) involves
2 (r:2-5/2)= 1=0
(12-112=--200 N +
2¹
( δ
GR
re 2/3 R
N
1=0
where (+) follows from substituting An = -(er- R 2/3) and m Ō(1). Multiplying this bound by Ō((/rr.22/) yields (up to polylogarithmic factors) the conclusion of Theorem 1.

---

Theorem 2. Let each l satisfy Assumptions I and Let e' = e/(2log M) and r. - /GGG. TRd, regularization strength À S O(G/r)) and accuracy 5, KatyushaX 12, Algorithm 2/ with the gradient estimator (9) outputs a valid BB-OOO response and has com- Consequently, the complexity of finding an 3.3 Accelerated variance reduction for mean-square smooth losses
In this section we provide algorithm with improved rate of convergence under the following mean-square smoothness assumption.
Assumption 2. For all x, x' E IB, and i [M], BBj.,: [1) Vez(21)) S - x'1
Note that assuming L-Lipschitz gradient for each é, implies Assumption 2, but the other way around. To take advantage of Assumption 2, we first rewrite the function (xr,2(z) in way that is more amenable variance reduction:
(x) = Σ Cx' (e.E((E' where ((xxx²) == de 4
SE[M]
Sile
Σ jEIM e
Gr
5,00
and ps (x()
Cyla
EyE(M
Σjetan
(Note that (x 3) (x))). Given reference point x', to compute a reduced-variance estimator of VT (T), we draw i ~ ps(x') and j ~ wa, and set:
(x) = VT VT.x(x)) + C
Min(I, (')(
(9)
e'
where (x) Vty(1) A(= z) and MZx x')] is MLMC estimator for (1 2²) defined analogously to ([)(()) (see details in Appendix C.4). The estimator (9) is not precisely standard SVRG [33] since we use (1, x')] as an estimator for (xxxx)) Simple calculations show that Eg.' (z) = VT and the following lemma shows that Ô satisfies type of variance bound conducive rariance-reduction schemes; see Appendix C.4 for the proof.
Lemma 3. Let each ij satisfy Assumptions 1 and For any E = & and x E BT)),, the variance of 9x (z) is bounded by (ar())((1)) S 50 (
+ +
G 1| x' 2'11").
Accelerated variance reduction methods for convex functions typically require stronger variance bound of the form Var(g. (x)) < (Fx')=)) - F(x)= (VF(x),,' - 2)) for every æ [ef. 1, Lemma 2.4]. The guarantee of Lemma is weaker, but still allows for certain accelerated rates via, e.g., the Katyusha X algorithm [2]. With it, we obtain the following guarantee.
For any query point
plexity (x = =0((N N3/ (G++()))EL) log
Gr. X82
Vxe
e-suboptimal minimizer of LE-DRO (2) with probability at least 1 is
(
o
GR
2/3
log 14/3
H + 23/1
H
GR
LR
1og 7/2 H
where H = M GR
We provide the proof of Theorem 2 in Appendix C.5. For the special case of Group DRO with single group satisfying Assumption 2 with = ((G* /E), i.e. minimizing the average loss, we have the lower bound (NV GR) [62] and for the case of N distinct groups, i.c. minimizing the maximal loss, we have the lower bound ONN 2/3) [15]. This implies that in the weakly mean-square smooth setting the term scaling 33/4g-1 and the term scaling - are unimprovable.
2/3
DRO with f f-divergence
In this section we develop our BROO implementation for the f-divergence objective (3). In Section 4. we reduce the original DRO problem to a regularized form using Lagrange multipliers. Next, in Section 4.2 we show that adding negative entropy regularization to the objective produces the stability properties necessary for efficient ball optimization. In Section 4.3 we describe a BROO implementation for the non-smooth case using a variant of Epoch-SGD [28], and in Section 4.4 we implement the BROO under a weak-smoothness assumption by carefully restarting an accelerated variance reduction method [1].
7

---

4.1 The dual problem
We first note that (due to Slater's 's condition), by Lagrange duality, the objective (3) is equivalent to
Ly-aw(x) =
max RNaa
Σ
(l((x) = min
V
max TEAN VE[N]
- }
Σ
V (nll(())))))
DEA CENN EEE(N)))
SE[M]
220
Writing (b()) = ((Ns) for 25 14+ + R, we therefore consider objectives of the form
E (((()) Gy) + Go) (10) CE(N]
(x)x)
(arl(1)) gEAN iE(N]
max
Σ
min yER
T(z,y)=
where G is the Lipschitz constant of each loss f; and for the last equality we use Lagrange duality, with 16 (u) == maX (ut {))} the Fenchel dual of d (for more details see Appendix D.1). We show that under weak assumptions (introducing logarithmic dependence the losses) we can solve the constrained problem (3) to accuracy c by computing a polylogarithmic number of -accuucce minimizers of (10); see Appendix D.2 for details. Since the complexity of solving (10) holds for any v >> O, and we have a lower bound for the required v, for the remainder of this section we focus on minimizing Lup for arbitrary convex vb.
bounds on f and
4.2 Stabilizing the gradient estimator
While minimizing (10) can be viewed as ERM (over and y), straightforward application of SGD does not solve it efficiently. To see this, consider the standard gradient estimator formed by sampling i~ (nV]( and taking ğ" = (fx (z)));(z) and g G(1 (e, (z) Gy)). For general 4 this estimator will have unbounded second moments, and therefore SGD using them would lack convergence guarantee. As an extreme example, consider ab = 0 (corresponding to
minimizing the maximum loss) whose conjugate function v/5 (v) 0 for S 0 and oo for e >
leading to meaningless stochastic gradients.
We obtain bounded gradient estimates in steps. First, we find better distribution for i using a reference point ह E X with corresponding y = argmin Y( y). Namely, we note that the optimality condition for implies that v (f())) Gt) is pmf over [N]. Therefore, we may sample ~ 1)² (L,(T) Gty) and estimate the gradient of Y (x, y) using g" = pr(2;; (z) (G)
and g" G(1 - (, y)). where pt(z, v) v p- (2,(2) Gi)) However, for general (and eb 0 in particular), the ratio p, y) can be unbounded even when xr y are arbitrarily close to T, 7-
Our second step ensures that pı(x, 3) is bounded around T, ÿ by adding a small negative entropy term vb defining
(g( = (g) + +''glogy where é' ==
(11)
2 2log N'
and
(x))()) = min Te y) with Te( = Σ (t(((()) - Gyy) + Gy.
(12)
yER
VE[N]
Due to our choice of e', we have (x) - Lx)e S e/2 for all x E Rd. and conse- quently an e/2-accurate minimizer of Lv.e is also an e-accurate for Ey (see Lemma 18 in Appendix D.3). When vb = 0 we have (v) = c(v-1)/e' and therefore the corresponding pi(x, v) = (((())) G(o--))ee The following lemma, which might be of independent inter- est, shows that the same conclusion holds for any convex v.
Lemma 4. For any convex vb E - and the defined in (10), log log(vi" (v))(()) is 3/ --iisschiiz
See proof in Appendix D.4. Thus, 352 (v)/ (0) = logg (o) (o) < B)fe' and pr(x.)) S e(fa(z)=((()) (G)) continues to hold. Therefore, if ly 5l S e/G T. and B, (o) (so that (x) - (x)) < if & satisfies Assumption 1), we have the bound pz y) < e².
It remains to show that we may indeed restrict y to be within distance from To this end, we make the following observation which plays a key part in our analysis and might also of independent interest (see proof in Appendix D.4).
8

---

Lemma 5. For G > 0, {x)) - y² (x)
and y²)) argmin yER (z y). we have [l((x)) - f(x')lloc for all x, of E X. Moreover, each & is G-Lipschitz,
have 1y (x) y" (x') S 1x x'Il.
Lemma 5 implies that x², ,², argmin (2) (r) satisfy - || 31l S re- Therefore, when minimizing T, (or any regularized version of it) inside the ball B,, (z), we may restrict y to [ 11--e Te. B + Te] without loss of generality. We also note that Lemma 5 holds for all values of and therefore valid even without entropy regularization (as long as gi strongly convex y is unique, and if y is not unique then we can still choose y" such that the bound of this lemma holds).
4.3 BROO implementation for forr-ddol fdiivegeence DRO with non-smooth losses
By the discussion above, to implement BROO for (x) (with radius e'/G, regularization X, and query & X) it suffices to minimize e,,x (2c, y) Y, (x, y) + 2 || =1|2 over E BB, (ω) and y E [g Te, V + re). where ÿ = argmin (T, y). To that end we estimate the gradient of T,,,(1r, v) as follows. Letting sample i ~ p and set
(e) Gt) (making a pmf by optimality of y), we
(2, (((()) - v(,x,)) and g' (x, = G -0 (e'((((())) Gy)
(13)
Pi
P.
Lemma 4 implies the following bounds on our gradient estimator; see proof in Appendix D.5.
Lemma 6. Let each & be G-Lipschitz, let o E X and ý = argminyeR Te, y). Let = & then for all x E B,, (3) and y E [0 Te, re]. the gradient estimators 9 and g satisfy the following:
1. Ei.p, (x, w) V Tx, v) and Einp, 1g" (r. v)] V,,)())
2. E, 1 (2,y)) w) S G²2 and 10 (z. v)
S G
To implement the BROO using our gradient estimator we develop variant of the Epoch-SGD algorithm of Hazan and Kale [28] (Algorithm 3 in Appendix D.5). Similarly to Epoch-SGD, we apply standard SGD on T., (with gradient estimator (13)) in "'epochs" whose length doubles in every repetition. Our algorithm differs slightly in how each epoch is initialized. Standard Epoch-SGD initializes with the average of the previous epoch's iterates, and strong convexity shows that the suboptimality and distance to the optimum shrink by constant factor after every epoch. However, since Y, T.. is strongly convex only in x and not in y. we cannot directly use this scheme. Instead, we set the initial y variable to be argmin,, Te,x 1r',20 3), where x' is the initial x variable still defined as the previous epoch's 's average; this initialization has complexity N, but we only preform a logarithmic number of times. Using our initialization scheme and Lemma 5, we recover the original Epoch-SGID contraction argument, yielding the following complexity bound (see proof in Appendix D.5).
Theorem 3. Let each & satisfy Assumption 1. Let e, X,8 > O, and r. = c/(2G log N). For any query point 5. E Red, regularization strength X S O(G/r.) and accuracy < re/2, Algorithm 3 outputs a valid r. BRRO response for Lite and has complexity Cx(6) = O 3a8z + N log( (3x) )). Consequently, the complexity of finding an e-suboptimal minimizer of Eg (10) with probability at least 1 is
(
GRR
2/3
(GR) 2
GR
log 11/3
Н
log² H
where H ==
4.4 Accelerated variance reduction for smooth losses
In this section, we take advantage of the following smoothness assumption. Assumption 3. For every i E [N] the loss e, is L-smooth, i.e., has L-Lipschitz grudient.
Let us rewrite Te, in form that is more amenable to variance reduction techniques:
Te,((I,))= Σ (z, where vx x/ (e,(x) - Gyy + Gy + |1 =1|2 NE[N]
X
and, as before D. Jे (Z) Gij) for some ball center v E X and y argmin yER Y, v). In the following lemma, we bound the smoothness of the functions U; deferring the proof to Appendix D.6.

---

Lemma 7. For any E [N], let & be G-Lipschitz and L -moothh let - & and X = ( The restriction of Uj to E Br, (T) and y E 1 - r.: y + rr. is -ipssiips and O .) smooth.
obtain reduced-variand gradient estimates by the standard SVRG technique [33]. For any reference point x', y', the estimator
Since T,, is finite sum of smooth functions,
gn'na/ (I, 2) - (x', ./) + Vu; v) Vui(=', (')()
(14)
where V is with respect to the vector [a, y]. Similar non-smooth case, obtaining an efficient BROO implementation is complicated by the fact that T,, is strongly-convex in but not in Our solution is also similar: we propose restart scheme and minimize over y exactly between restarts (Algorithm 4 in Appendix D.6), that gives the following complexity bound (see proof in Appendix D.6).
Theorem 4. Let each l satisfy Assumptions I and 3, let c, X, > O, and re 2Glog N- For any ( and accuracy Algorithm 4 outputs a valid r. -BROO response for Lype and has complexity Cx = (( (0)0)=0(()))))
query point z E R. regularization strength I (
vN(C+VEL) log XO Vxe'
Consequently, the complexity of finding e-suboptimal minimizer of b (10) with probability at least 2 is
GR
2/3
GR
LR
where N GRR
N
log 11/3 H VN
log 5/2 H
5 Discussion
Limitations While our work indicates that the ball optimization approach offers significant com- plexity gains for DRO, note that turning the algorithms propose into practical DRO methods faces several challenges. main challenge is the costly bisection procedure common to all Monteiro- Svaiter-type acceleration schemes [41, 25, 13, 52]. Fortunately, very recently, two works [16, 36] (the former partially motivated by our paper) have shown how to remove the bisection from Monteiro- Svaiter schemes, significantly improving the practical potential of the methods propose. However, another practical limitation of our approach is the need to tune many parameters that are not known in advance, such as those relating the ball radius r, and smoothing level e', as well step sizes and number of iterations of oracle implementations; a more adaptive setting for these parameters is likely important.
Extensions First, it would be interesting to extend our approach to DRO objectives max,eu EsE[N] (2) with uncertainty set U that is arbitrary subset of the simplex. While the subgradient method, the primal-dual method (Appendix A.1), and "AGD softmax" (Ap- pendix A.2) all apply to any L/ S AN, our methods strongly rely on the structure of induced by Group- f-divergence DRO, and extending them to unstructured ll's seems challenging.
Second, it would be interesting to generalize our results in the "opposite" direction of getting better complexity bounds for problems with additional structure. For Group-DRO our bounds are essentially optimal when the number of groups M = Q(N). but are suboptimal when M = O(1). We leave it question for further research if it is possible
obtain a stronger bound such as Ö(N Me -2/3 + =2), which recovers our result for M N but improves on it for smaller values of M. Taking CVaR at level a as a special case of f-divergence DRO, our bounds are optimal when is close to 1/N but suboptimal for larger value of a; it would be interesting obtain bounds such as Ö(N + -te-2/1 +
A third possible extension of our research is DRO in the non-convex setting. For this purpose, it might be possible to use the technique of Carmon et [12] for turning accelerated convex optimization algorithms to
methods for smooth non-convex optimization.
Acknowledgments
We thank Mare Teboulle for detailed and helpful feedback. This work was supported by Israeli Science Foundation (ISF) grant no. 2486/21, the Len Blavatnik and the Blavatnik Family foundation and the Adelis Foundation.
10

---

References
[i] Z. Allen-Zhu. Katyusha: The first direct acceleration stochastic gradient methods. Journal of Machine Learning Research, 18(221):1-51, 2017.
[2] Z. Allen-Zhu. Katyusha X: Practical momentum method for stochastic sum-of-nonconvex
optimization. In International Conference on Machine Learning (ICML), 2018.
[3] H. Asi, Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Stochastic bias-rect Sausredduced gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[4] A. Beck and M. Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557-580, 2012.
[5] A. Ben-Tal and M. Teboulle. A smoothing technique for nondifferentiable optimization prob- lems. In Optimization, pages 1-11. Springer, 1989.
[6] A. Ben-Tal, den Hertog, A. De Waegenaere, B. Melenberg, and G. Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2): 341-357, 2013.
[7] D. Bertsekas. Nondifferentiable optimization via approximation. Springer, 1975.
[8] D. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. Academic Press, 1982.
[9] J. H. Blanchet and P. W. Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), 2015.
[10] J. H. Blanchet, P. W. Glynn, and Y. Pei. Unbiased multilevel Monte Carlo: Stochastic optimiza- tion, steady-state simulation, quantiles, and other applications. arXiv:1904.09929, 2019.
[11] J. Buolamwini and T. Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. Conference on fairness, accountability and transparency, pages 77-91, 2018.
[12] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. "Convex until proven guilty": Dimension- free acceleration of gradient descent on non-convex functions. In International Conference on Machine Learning (ICML), 2017.
[13] Y. Carmon, A. Jambulapati, Q. Jiang, Jin, T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. In Advances Neural Information Processing Systems (NeurIPS), 2020.
[14] Y. Carmon, Y. Jin, A. Sidford, and K. Tian. Coordinate methods for matrix games. In Foundations of Computer Science (FOCS), 2020.
[15] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference Learming Theory (COLT), 2021.
[16) Y. Carmon, D. Hausler, A. Jambulapati, Y. Jin, and A. Sidford. Optimal and adaptive Monteiro- Svaiter acceleration. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[17] Y. Chow, A. Tamar, S. Mannor, and M. Pavone. Risk-sensitive and robust decision-making: a CVaR optimization approach. In Advances neural information processing systems (NeurIPS), 2015.
[18] M. B. Cohen, Y. T. Lee, G. Miller, J. Pachocki, and A. Sidford. Geometric median in nearly linear time. ACM symposium on Theory of Computing, 2016.
[19] I. Csiszár. On topological properties of f-divergences. Studia Math. Hungar, 2:329-338 1967.
[20] S. Curi, K. Y. Levy, S. Jegelka, and A. Krause. Adaptive sampling for stochastic risk-averse learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
11

---

[21] J. Duchi and H. Namkoong, Variance- regularization with convex objectives. Journal of Machine Learning Research, 20(68):1-55, 2019.
[22] J. C. Duchi and H. Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3): 370- 2021.
[23] M. Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the wasser- stein metrie: Performance guarantees and tractable reformulations. Mathematical Programming. Series A, 171())115-166, 2018.
[24] R. Gao and A. J. Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. arXiv:1604.02199 2016.
[25] A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang. S. Zhang. S. Bubeck, Q. Jiang, Y. Lee, Y. Li, and A. Sidford. Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. In Conference on Learning Theory (COLT), 2019.
[26] M. B. Giles. Multilevel monte carlo path simulation. Operations research, 56(3):607-617, 2008.
[27] T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, 2018.
[28] E. Hazan and S. Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-conved optimization. Journal of Machine Learning Research, (5(71):2489-2512, 2014.
[29] S. Heinrich. Multilevel Monte Carlo methods. In International Conference on Large-Scale Scientific Computing, 2001.
[30] D. Hovy and Søgaard. Tagging performance correlates with author age. Association for Computational Linguistics (ACL), pages 488,488,44 2015.
[31] W. Hu, G. Niu, I. Sato, and M. Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning (ICML), 2018.
[32] J. Jin, B. Zhang, H. Wang, and L. Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In Advances in Neural Information Processing Systems (NewrIPS), 2021.
[33] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems (NeurIPS), 2013.
[34] C. Kent, Blanchet, and P. Glynn. Frank-wolfe methods in probability space. arXiv:2105.05352, 2021.
[35] W. Koh, Sagawa, H. Marklund, M. Xie, M. Zhang, A. Balsubramanii, W. Hu, M. Ya- sunaga, R. I.. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. A. Earnshaw I. S. Haque, S. Beery, J. Leskovee, A. Kundaje, Pierson, S. Levine, C. Finn, and P. Liang. Wilds: benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
[36] D. Kovalev and A. Gasnikov. The first optimal accelcration of high-order methods in smooth convex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[37] P. Krokhmal, J. Palmquist, and S. Uryasev. Portfolio optimization with conditional value-at-risk objective and constraints. Journal of risk, 4:43-68, 2002.
[38] G. Lan, Z. Li, and Zhou. A unified variance-reduced accelerated gradient method for convex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[39] D. Levy, Y. Carmon, J. C. Duchi, and Sidford. Large-scale methods for distributionally robust optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
12

---

[40] F. Lin, X. Fang, and Z. Gao. Distributionally robust optimization: review on theory and applications. Numerical Algebra, Control & Optimization, 12(1):159, 2022.
[41] R. D. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23(2):1092-1125 2013.
[42] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust opti- mization with f-divergences. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[43] A. Nemirovski, A. Juditsky, G.
Lan, and A. Shapiro. Robust stochastic approxattiinn approach stochastic programming. SIAM Journal on optimization, 19(4):1574-160, 2009.
[44] Y. Nesterov. Smooth minimization of non-smooth functions. Series A, 103(1):127-152, 2005.
Mathematical Programming,
[45] Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[46] L. Makden-Rayner J. Dunnmon, G. Carneiro, and C. Ré. Hidden stratification causes clinically meaningful failures in machine learning for medical imaging. In ACM conference on health, inference, and learning, 2020.
[47] Y. Oren, S. Sagawa, T. B. Hashimoto, and P. Liang. Distributionally robust language modeling. In Empirical Methods in Natural Language Processing (EMNLP), 2019.
[48] R. T. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 21 21-41, 2000.
[49] S. Sagawa, W. Koh, T. Hashimoto, and P. Liang. Distributionally robust neural networks. In International Conference on Learning Representations (ICLR), 2020.
[50] A. Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization, 27 04-2258-22755 2017.
[51] A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations (ICLR), 2018.
[52] C. Song, Y. Jiang, and Y. Ma. Unified acceleration of high-order algorithms under Hölder continuity and uniform convexity. SIAM journal of optimization, 2021.
[53] C. Song, C. Y. Lin, S. J. Wright, and J. Diakonikolas. Coordinate linear variance reduction for generalized linear programming. arXiv:21 2021.
[54] N. A. Urpí, S. Curi, and A. Krause. Risk-averse offline reinforcement learning. In International Conference on Learning Representations (ICLR), 2021.
[55] K. A. Wang, N. Chatterji, S. Haque, and T. Hashimoto. Is importance weighting incompatible with interpolating classifiers? In International Conference on Learning Representations, 2022.
[56] S. Wang, W. Guo, H. Narasimhan, A. Cotter, M. R. Gupta, and M. I. Jordan. Robust optimization for faimess with noisy protected groups In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[57] J. Wen, C.-N. Yu, and R. Greiner. Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. In International Conference on Machine Learning (ICML), pages 631 631-639, 2014.
[58] B. E. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems (NeurIPS), 2016.
[59] R. Zhai, C. Dan, Kolter, and P. Ravikumar. Doro: Distributional and outlier robust optimiza- tion. In International Conference Machine Learning (ICML), 2021.
13

---

[60] R. Zhai, C. Dan, A. Suggala, J. Z. Kolter, and P. Ravikumar, Boosted CVaR classification. In Advances neural information processing systems (NeurIPS), 2021.
[61] C. Zhou, D. Levy, X. Li, M. Ghazvininejad, and G. Neubig. Distributionally robust multilingual machine translation. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
[62] D. Zhou and Q Gu. Lower bounds for smooth nonconvex finite-sum optimization. In Interna- tional Conference on Machine Learning (ICML), 2019.
14


Reviews:
[{"review_id": "yMLxAt5iNXA", "reviewer": "Reviewer_ZWwH", "summary": "The paper deals with distributionally robust optimization, in two specific settings : group DRO and f-divergence DRO. Distributionally robust optimization can minimizes a supremum over distributions in a set of test distributions, which is finite in the case of group DRO and a ball of finite radius for a certain similarity measure in the case of f-divergence DRO. This supremum makes the optimization harder : one cannot readily apply available techniques for minimisation of convex losses.\n\nThe contributions of the paper are : \n\n1. To present methods to compute ball oracles in a fast way in both cases for potentially non smooth function\n2. To present methods to compute ball oracles in an accelerated way when dealing with a certain degree of smoothness\n3. To use these ball oracles to design an optimization with low complexity in terms of gradient evaluations, relying on a MLMC methods.\nPoint 1 and 2 are crucially involve the introduction of a way of computing a gradient estimator which differs from previous work (and which also relies one a MLMC method).", "questions": "- Can you provide any kind of experiment ? case where BROO has been use even in a non DRO setting\n- Could you provide more information about working (or non-working) DRO techniques\n- NB : the fact that regularisation transforms the dual to a smooth thing is not new at all (see Nesterov books for instance)\n", "limitations": "For me, the clear limitation is the apparent complexity of the algorithms (there are a lot of logarithmic bricks but which add up) and no experiment to support their applicability. ", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For me, the methods are in general not new even if the gradient estimate seems new. \n\nI believe the related works are adequately cited for the technical part, and it is pretty clear the this work is essentially an application of a set of technique (MLMC + BROO optimization) to the problem of DRO (even if that application calls for the introduction of some “new” machinery”)\n\nI believe the work on DRO could be more cited, in particular the more applicable work, as this work does not contain any sort of simulation.\n\n    * Quality: \n\nI did not read the entire proofs but a large part of them, and they are correct. \n\nFor me, while these theoretical results are interesting, as the lower bounds are known, the goal is to reach them with an implementable algorithm (at least in a conference like NeurIPS). The complete lack of experiments is disturbing, especially as the proposed methods seem to have a very high constant hidden. \n\nMoreover, the papers on which this relies are also of a theoretical nature, and very few experiments convince me of the quality of the method. While this drawback is underlined in the paper, I believe it to be a very crucial lack of the MCML methods. \n\n\n\n    * Clarity:\n\nIn terms of organisation, the paper is clear\n\nIn terms of claims, I believe the references are not clear enough : algorithm 1 mentioned in the main paper has to be found manually, and no detail is given about it. Also, the bounds involve many complex terms. I believe that part of this complexity should be moved to the appendix, to better present the results (as this paper is completely concentrated in the appendices in any case), especially for part 2. \n\n\nTechnically, the paper is involved for a novice in the field, and cannot be followed easily without looking into the references. I believe doing sketches of proofs or algorithm in a more self contained way (for example the lambda bisection is completely skipped) would help understanding. \n\n\n\n    * Significance:\n\nWithout any kind of applications, even on toy problems, it is very hard for me to evaluate the significance of the results. For me, for NeurIPS, the lack of ANY kind of non-theoretical work is disturbing. ", "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": "o350Dx83_-", "reviewer": "Reviewer_zx8s", "summary": "This paper proposes accelerated algorithms for distributionally-robust optimization based on group-structured and bounded f-divergence sets uncertainty. The algorithm uses ball oracle technique, a multi-level monte-carlo technique and exploits specific structures associated with these uncertainty sets. These ingredients lead to improved convergence guarantees both in terms of accuracy of the iterate and the number of iterations. \n", "questions": "--\nCan this be extended for Wasserstein metric which is prevalent in a lot of ML literature? ", "limitations": "--\nLack of numerical experiments demonstrating that the algorithm works. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-- Strength \n\nNice mixture of existing ideas for uncertainty sets are practically applicable. Further, results are improved for smooth, Lipschitz functions. \n\n-- Weakness:\n- The results are tailored to very specific uncertainty sets. The other ingredients or their combination doesn't seem to be new. \n- Lack of numerical experiments to validate. This is crucial especially for this paper since the claims themselves are about reducing computation relative to state-of-the-art! ", "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": "gycG18oshXj", "reviewer": "Reviewer_uy4v", "summary": "This paper proposes efficient algorithms for distributionally robust optimization (DRO). The objective in DRO is to minimize the worst case expected loss over a family of distributions over the population. A simple example of this problem is group DRO, where we have $N$ separate loss functions, and $m$ distributions, where each distribution assigns a weight to each of the loss functions; the objective in this case becomes to minimize the maximum over m weighted linear combinations of the loss functions.\nA more challenging setting is DRO with $f$-divergence, where the family of distributions is all distributions that are close to some fixed distribution where the distance between distributions is measured by a divergence.\n\nAssuming that each of the loss functions is Lipschitz, and that the domain has bounded diameter, the authors present an algorithm for group DRO / f-divergence DRO that can compute a point that achieves a loss at most $\\epsilon$ larger than the minimum possible in roughly $N\\epsilon^{-2/3} + \\epsilon^{-2}$ gradient evaluations of individual loss functions. Directly applying previously known algorithms results in a bound of $N\\epsilon^{-2}$ gradient evaluations.\n\nThe approach is similar to [11], and designs a \"ball-optimization oracle\" for regularized versions of the problems, in order to be able to apply accelerated optimization algorithm from [9]. This paper establishes the ball optimization oracle by using SGD and building unbiased gradient estimators for the the group DRO and a regularized version of $f$-divergence DRO.\n\n[9] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. In Advances in Neural Information Processing Systems (NeurIPS), 2020.\n\n[11] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory (COLT), 2021.", "questions": "My main suggestion would be to work at making the key ideas in the paper more accessible. The paper gets really terse and difficult to follow a few pages in. \nAs a concrete suggestion, shorter theorem statements highlight the most significant parts of the results would be helpful.", "limitations": "As the authors already identify and suggest, it seems likely that these bounds should extend to the case of arbitrary subsets of the simplex, but the current algorithms depend highly on the structure of the DRO problems. Obtaining such an extension would be quite impressive.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n- DRO is a well-studied problem from robust optimization. It is somewhat surprising that the authors are able to obtain essentially the same running time complexity as SGD for small $N,$ and the same as in the case of minimizing the maximum of $N$ loss functions\n- The bound on gradient evaluations achieved by this paper matches known lower bounds even in the case of minimizing the maximum over $N$ distinct loss functions. Thus, in some parameter regimes, the presented algorithm is essentially optimal.\n\n**Weaknesses**:\n- The approach is a somewhat too similar to [11]. The main difference is the construction of gradient estimators. The estimator for group DRO is pretty straightforward.\n- Even the main body of the paper is very very notation heavy, and it is difficult to parse at many places to discern the key technical ideas", "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": "R5QHStC4mdm", "reviewer": "Reviewer_MgTq", "summary": "The paper proposed new algorithms for two formulations of DRO, i.e. group DRO and f-divergence DRO. The new algorithms achieve better regret bound than existing ones. The key idea is to implement ball optimization oracle and plug it into state of the art optimization algorithms to solve DRO efficiently.", "questions": "I think this is a solid paper, I do not have much questions. One suggestion is to move less important content into Appendix and add more discussions in the main paper.", "limitations": "Limitations are well-discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths are the solid analyses and improved convergence rate. The weaknesses are that these algorithms are purely theoretical and not tested in practice as mentioned by authors. Also the presentation of the paper could be improved as currently there is too much content filled in the main paper. \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": {}}]

Author rebuttal:

Decision: Accept