Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
Authors: Ronak Mehta
Jelena Diakonikolas
Zaid Harchaoui
Venue: NeurIPS 2024 poster (2024)
Keywords: Distributionally Robust Optimization
Stochastic Optimization
Convex Optimization
Saddle Point
Primary area: optimization
TL;DR: A stochastic primal-dual algorithm for solving distributionally robust optimization problems. It achieves a state-of-the-art linear convergence rate and combines randomized and cyclic components.

Abstract: We consider the penalized distributionally robust optimization (DRO) problem with a closed, convex uncertainty set, a setting that encompasses learning using $f$-DRO and spectral/$L$-risk minimization. We present Drago, a stochastic primal-dual algorithm which combines cyclic and randomized components with a carefully regularized primal update to achieve dual variance reduction. Owing to its design, Drago enjoys a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems witha fine-grained dependency on primal and dual condition numbers. The theoretical results are supported with numerical benchmarks on regression and classification tasks.

DRAGO: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
Ronak Mehta
Jelena Diakonikolas
Zaid Harchaoui!
UUiiersitty of Washington, Seattle
University of Wisconsin, Madison
Abstract
We consider the penalized distributionally robust optimization (DRO) problem with closed, convex uncertainty set, a setting that encompasses learning us- ing f-DRO and spectral/L-risk minimization. We present DRAGO, a stochastic primal-dual algorithm that combines cyclic and randomized components with a carefully regularized primal update to achieve dual variance reduction. Owing its design, DROGO enjoys a state-of-the-art linear convergence rate strongly convex-strongly concave DRO problems with a fine- greeggaaned dependency on pri- mal and dual condition numbers. The theoretical results are supported by numer- ical benchmarks on regression and classification tasks.
1 Introduction
Contemporary machine learning research is increasingly exploring the phenomenon distribution shift, in which predictive models encounter different data-generating distributions in training versus deployment [Wiles al., 2022]. A popular approach to learn under potential distribution shift distributionally robust optimization (DRO) of an empirical risk-type objective
min max wEW gE
Co(w, g) = Ex (.)(
(I)
where l, Rdd -> R denotes the loss training instance [n] (1.....m), and g (q1....,4,, E Q is a vector of n weights for each example. The feasible set Q, often called the uncertainty ser, is collection of possible instance-level reweightings arising from distributional shifts between train and evaluation data, and is often chosen as a ball about the uniform vector 1/n (1/n,..., 1 1/n) in /-divergence [Namkoong and Duchi, 2016, Carmon and Hausler, 2022, Levy et al., 2020] or a spectral/ ---risk-basedd uncertainty set [Mehta et al., 2023].
We consider here the penalized version of (1), stated as
# L(w, q) = Σ ggl((w)) - DD(alli/n) + 2 [|
where μ, v 2. O are regularization parameters and D(g](1/n) denotes some statistical divergence (such the Kullback-Leibler (KL) or x -iveerrrg)))e between the original weights 1/n and shifted weights For clarity, we focus on the cases of v > 0, but also describe the modifications to the methods, results, and proofs for cases in which μ or / 0, in Appx. C.4. See Fig. I for intuition on the relationship between the uncertainty set, divergence D, and hyperparameter v.
Standard (1) and penalized (2) DRO objectives have
outpour of recent use in reinforcement learning and control [Lotidis et al., 2023, Yang et al., 2023, Wang et al., 2023a, Yu et al., 2023, Kallus et al., 2022, Liu et al., 2022] well creative applications in robotics [Sharma et al., 2020], language modeling [Liu et al., 2021], sparse neural network training [Sapkota et al., 2023]
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

CVaR Uncertainty Set with x² Penalty
X Uncertainty Set with x Penalty
CVaR Uncertainty Set with KL Penalty
10
414
12
08
K4
14
30
Figure/ 1: Visualization of Uncertainty Sets and Penalties. Each plot is a probability simplex in n = 3 dimensions with the uncertainty set as the colored portion. The black dots are optimal dual variables of : arg ma Ex= q:l((w)= Dgll 1/n) for fixed w W. As decreases, o may shift toward the boundary of the uncertainty set. The combination of v and D determines an "effective" uncertainty set, whose shape is given by the level sets of D. Our methods apply both.
and defense against model extraction [Wang et al., 2023b]. However, even a classical supervised learning setup, current optimization algorithms for DRO have limitations in both theory and practice.
For context, we consider the large-scale setting in which the sample size n is high, and the training loss in each example is accessed through a collection of primal first-order oracles {(4,. } Quantitatively, we measure the performance of algorithms by runtime or global complexity of ele- mentary operations to reach within of the minimum of C(w) max Cww, q). while qualita- tively, we consider the types of uncertainty sets that can be handled by the algorithm and convergence analysis. Under standard assumptions, L is differentiable with gradient computed via
9" (w) = arg max L(w, g), followed by V((w) = Σ of (w) (w, + pwv qEQ
(3)
In the learning setting, we are interested in stochastic algorithms that can approximate this gradient with b < n calls to the oracles. For uniformly randomly sampled i E [n]. (w) (W()) + paw is an unbiased estimator of VL(w). However, computing of (w) depends on the first step in (3) which itself requires calling all n oracles (see (2)), i.e., it descent. A direct minibatch stochastic gradient descent approach would approximate [(w,) in the first step of (3) with only calls to generate approximate weights (ww). Because ((w) + q q'(w) in general for b < n, these methods have non-vanishing bias, i.e., do not converge [Levy et al., 2020].
no different than the cost of full batch gradient
This motivated research on DRO-specific stochastic algorithms with theoretical convergence guaran- tees under particular assumptions (see Tab. 1 and Appx. B for details) [Namkoong and Duchi, 2016, Levy et al., 2020, Carmon and Hausler, 2022]. Although we highlight the dependence on sample size and suboptimality the dependence all constants is given in Tab. 1. For f adivergence-basee uncertainty sets in the standard oracle framework, several methods achieve a O( complexity. Levy et al. [2020] do so by proving uniform bias bounds, that if scales as O(s the con- vergence guarantee achieved. However, if the required batch size exceeds the training set size n, then the method reduces the sub-gradient method, we rates typically stem from two causes. The first is the adoption of a "fully stochastic" perspective on the oracles, wherein each oracle's output is treated probability distribution. The second is the non-smoothness of the objective, as we shall see below.
in Tab. 1. These sublinear
independent random sample drawn from
Variance reduction techniques, on the other hand, exploit the fact that the optimization algo- rithm takes multiple passes through the same dataset, and achieve linear rates of the form O((n + ke) log(=-1)) in empirical risk minimization when the objective is both smooth (i.e., has Lipschitz continuous gradient) and strongly convex and Kg is an associated condition number [Johnson and Zhang, 2013, Defazio et al., 2014]. Assuming access to stronger oracles involving constrained minimization and applying a variance reduction scheme, Carmon and Hausler [2022] achieve 22/3 + 3/1g-11 for /-divergencess as well, but do not obtain linear convergence due to the second type of cause: the objective V L is non-smooth when 0.

---

Recently, Mehta et al. [2024] handled the v > O case for spectral risk uncertainty sets, and their variance-redueed algorithm achieves a linear O((n+((oo))
In(1/E)) convergence guarantee (where
kig 2 1 measures the "size" of the uncertainty set), but only with lower bound of order ((()) on the problem parameter v. The challenge of this problem, considered from a general optimization viewpoint beyond DRO, stems from the non-bilinearity of the coupled term > Li=1 (:(((w) and the constraint that Σ i= 9: = 1 for probability vectors. If the coupled term was bilinear (i.e., of the form qº Aw for A E R= and the constraints applied separately to each qs then dual decomposition techniques could be used. Qualitatively, algorithms and analyses often rely on particular uncertainty sets; for example, Kumar et al. [2024] use duality arguments specific to the Kullback-Leibbe uncer- tainty set to create a primal-only minimization problem. See Appx. B for detailed discussion of related work from the ML and the optimization lenses. Given the interest from both communities, we address whether a stochastic DRO algorithm can simultaneously 1) achieve a linear convergence rate for any V > 0 and 2) apply to many common uncertainty sets.
Contributions We propose DRAGO, a minibatch primal-dual algorithm for the penalized DRO prob- lem (2) that achieves e-suboptimalliyy in
o n KOL (1=
n b
nG² u
I
+
In
(4)
iterations, where b E {I,...,n] n is the minibatch size, Kg = T.mmax := Y m8 qi mea- sures the size of the uncertainty set, and G and L are the Lipschitz continuity parameters of é and Vl, respectively. For commonly used parameters of uncertainty sets, Rfmmax is bounded above by an absolute constant independent in n (see Prop. 3), so for d < n and b n/d, we maintain an Onn) per-iteration complexity (the dual dimensionality) while reducing the number of iterations to O(dd + KgLl + (x/nG2/(ww)) In (1/e)). Theoretically, the complexity bound we achieve in (4) the best one among current penalized DRO algorithms, delineating a clear dependence on smoothness constants of the coupled term and strong convexity constants of the individual terms in (2). Practically, ARAGO has single hyperparameter and operates on any closed, convex un- certainty set for which the map 1 + arg max o ( DRAGO is also of general conceptual interest as stochastic variance-reduse reduced primal-dual algorithm for min-max problems. It delicately combines randomized and cyclic updates, which effectively address the varying dimensions of the two problems (see Sec. 2). The theoretical guarantees of the algorithm are explained in Sec. 3. Numerical performance benchmarks shown in Sec. 4.
L v D 1/n) } is efficiently computable.
2 The DRAGO Algorithm
We present here the Distributionally Robust Annular Gradient Optimizer (DRAGO). While similar in spirit primal-dual proximal gradient method with a stochastic flavor, there are several inno- vations that allow the algorithm to achieve its superior complexity guarantee. These include using 1) minibatch stochastic gradient estimates to improve the trade-off between the per-iteration com- plexity and required number of iterations (especially when n >> d), 2) combination of randomized and cyclically updated components in the primal and dual gradient estimates, and 3) a novel regu- larization term in the primal update which reduces variance in the gradient estimate (i.e., coupled variance reduction). Here, we describe the algorithm a manner that helps elucidate the upcoming theoretical analysis (Sec. 3). On the other hand, in Appx. D, we present an alternate description of DRAGO that is amenable to direct implementation code.
Notation & Terminology Let : R² + R U (+00] be a proper, convex function such that Q C d) : {q E R" ())4)= < + Let & have non-empty subdifferential for each E Q and denote by V a map from q E Q an arbitrary but consistently chosen subgradient in (v)()). We denote the Bregman divergence generated by v as Ag g) (g(g) vh(g) (V ②) We employ the Bregman divergence in this way for purely technical reasons, and for common cases this version will not be invoked. Finding minimizer of (2) is equivalent to finding a saddle-point (w..g. q-) E W Q which satisfies
max L(w.. 9) L(w,, q.) min L(w, Q
wEW
3

---

Method
Assunptions
Uncertainty Sc
Runtinc/ Globel Complestyy (Big-()
alll included)
4 is Lipshizz
Suppoet Constiited
nd (GRR)
Suh Gradeet Method
2 o asclaed)
Suppon Conanized Support Cinstrited
val pan [2 a 4 (oe()/e)
und ud-G'p
L-piochhile and included)
P-CVak م-bll is x (-dierggacc F-dieeggesee pasally
mis [n. (ig- d (G ( min (n. (iPP) (4 (020) min (infn, (n.BPurla-1)) (oRy)
is G-Lipahhis and is (.
oll,, Rfrrlll P. of inccldddd)
Eyt pu SCDb!
[Lary atal, 20200)
BR00"
6, CiLipohitz
L-belin didvergeace 1/Nil in f-divegence
nd (CZR)ARgg4 SCRRA
BR00
In al,, i it for of 6
out (CSMP) 49 effa DPPit 109
[Cacscc and Haniler 3023]
VT, L-Lipschite (iiccldde)
15VRG
6 is C- Lipecizz
Special Risk Messures (r stall) Risk Meaasres Rp0l
Nove
L5VIG
57, L-Lipattiz
(s rige) (lad(-/e))
(Merra st... 20233
2 0. 3 0. - (2: wi/u
Propeet
1. is ipachite
Spectall Rick Mizesrra crall) Speciall Iisk Measures DinG2//i) (pi)
noo d) more (nd snpuae, //PPP (1P) (ng/ In mgei dflog14/e)
Proppect
57, L-Lipettizz
(Metra rtal. 2014)
Oua 0. (1.4))ff G (1pw)
G GiLipohitz
DRAGO (Durs)
VY, is L/Lipcctiee
Suppon Comonized
a mightu 4 d150077/p0) Dent1))))
J OU 0,8 Butch
Table 1: Complexity Bounds of DRO Methods. Runtime or global complexity (i.e., the total num- ber of elementary operations required to compute w satisfying max L(w, q) L(w,, q-) S s. Throughout, we assume that each & is convex and v, 0. The "Support Constrained" uncertainty set refers to all closed, convex sets of probability mass vectors and any 1-strongly convex penalty. This includes f-divergences and spectral risk measures, but not general Wasserstein balls. "Bounds hold in high probability. !Complexity is measured in our framework; see Appx. B for details.
We denote the Jacobian of é == (41,..., Cn) at w as Vl(w) Raxd We refer to the gradient of the coupled term q f(w) of (2) with respect to and q (that is, V((w) q and f(w)) as the primal and dual gradients, respectively. In both the definition of the algorithm as well as the analysis, we will consider sequence of positive constants (a1)121 with the additional values ag = 0. The partial sums of this sequence will be denoted A, = Σr a7. Here, represents the iteration counter while the convergence rate will be proportional to A," (see Sec. 3), so we wish for the sequence to grow as fast as possible. As mentioned in Sec. 1, d is the primal dimension, is the dual dimension as well as the sample size, and b denotes a batch size that divides n for ease of presentation.
Algorithm Description We specify the algorithm by recursively defining a sequence of primal-dual iterates {ww,, {(w),)))2) } that achieve particular convergence guarantee. First, we may assume that E W without loss of generality, so fix We = O and go = 1/n. For any t 2 1, we introduce of_, and uP as to-be-specified stochastic gradient estimates of the quantities V T qt-1 and ((w;), respectively. We choose to update wi before qr, so that vf_1 may depend only on the history ((Wr, 4r )- whereas uP may depend additionally on w; as well. Letting (Ct)e2) and (c))22 be to-be-specified sequences of positive constants with Co cu = 0. we employ primal-dual proximal approach guided by the updates
We := arg min nEW
a1 (vr, w)
+ ||0
apf
C-11
||l Wt 111112 112
(5)
2
2
2-2 2
+
1t
I waval12
(6)
2
sm t- //b
{at (p - -vvD(alll))) - AL--DD((.
9t = arg max
qEQ
For the primal update, despite the non- non-standard term (6), wi can be computed easily in closed form when W Rdd. Otherwise, retrieving We relies on computing an & &2-norm projection onto W. On the other hand, the maximization (7) can often be solved exactly or to high accuracy using methods specific to each uncertainty set; we describe these in detail in Appx. D.2. The randomized and cyclic coordinate-wiee components mentioned above are contained within the upcoming formulas for =f and o.. After specifying these vectors, the constants (Cz, ex) will be chosen in the analysis to recover the final algorithm.

---

Next, we describe the computation of e and eP, which will rely on quantities that are stored by the algorithm along its iterations. We store three tables of values & E R q R and I E Raxd which are approximations of f(w;), Qt, and Vε(ws), respectively. Before explaining how these tables are updated, consider the data indices (1....:77 nz to be partitioned into n/b blocks, written (Bi,... Bn/t) for Bx (K - b + ..... Kb). On each iteration 4, we randomly sample independent block indices Je ~ Unif[n/bl and define
J = 9 + at-1 n Σ
- 2.
(8)
IEBI,
of = &g + 0111 n E a1 JEB
(4)())) 1e)
(9)
As for the tables of approximations, we update them on each iteration without suffering the (ndd) computational cost of querying every first-order oracle (f1, Ve))...., (fn, V62)- We set (lo, (o.90) = (l(wo), 2o. V((wa)), and for iteration & 2 1 update block K₁ == (n/b) mod t ++1 1 via
(le(w))) ge,ki ((x(w))) ft- (e 2t- 1,.,
if E Bk. if l & BR.
While q: in particular is always known by the algorithm, we use the approximation &. which is pos- sibly dual infeasible for every t 2 1, but will approach qi as f grows large. Using this approximation is essential to controlling the per-iteration time complexity. as described below. In addition, the de- sign of (8) and (9) is grounded in the long line of work on incremental methods (both deterministic and randomized). The table of past gradients updated cyclically resembles IAG [Blatt et al., 2007], whereas the randomized component resembles methods such SAGA [Defazio et al., 2014] and stochastic PDHG [Chambolle et al., 2018J. The full algorithm description is given in Algorithm 1. In the next section, we show that (a,, Ct, G))22 can be determined by a single hyperparameter.
Computational Complexity We also discuss the per-iteration time complexity and the global space complexity of Algorithm 1, whereas the number of required iterations for s-suboptimality is given in the next section. We see that the per-iteration time complexity is O(n + bd), as we query b first-order oracles in both the primal and dual updates and all other operations occur on n-length or d-length vectors. While we need to employ O(nd) operations to compute 9 (8) when t = 1. this quantity can be maintained with ((bd) operations in every subsequent iteration as only b rows of di and Åt are editted in each iteration. For space complexity, we may consider storing the entire gradient table Jt in memory, resulting in an O(nd) complexity. However, due to our time complexity calculation, we may reduce the space complexity to O(n + bd) by storing only w;-1:... Wt-n/b and recomputing the relevant values of in (8) in every iteration. Therefore, the use of block-cyelic updates the historical tables may significantly reduce the space complexity as compared to randomized updates (as in Defazio et al. [2014]).
3 Theoretical Analysis
We provide the theoretical convergence rate and global complexity of DRAGO along with technical highlights of the proof which may be of independent interest.
Convergence Analysis We measure suboptimality using the primal-dual gap:
it L(w,, q+) L(w., qt) l w=1l 1/: 9+ 1:11
where the saddle point (w", (w",q") qq") exists under Asm. Note that y 2 O, as it is the sum of non- negative quantities
/ 2 ||,, w.112 112 2 0 and L(w., q.) - L(w,, (:)
V 1l q.112 2 0.
[( q.) - L(w,, q.)
2
To state the main result, define E, as the conditional expectation over (Tz, Jt) given (w,-1, z: and E, as the marginal expectation over the optimization trajectory. Consider the following assumptions.
5

---

Algorithm Distributionally Robust Annular Gradient Optimizer (DRAGO)
Input: Sequence of constants (ar, CtN 120. block size E {l,...,ni n., number of iterations T. Initialize who = 0dd Qo = 1/n, lo = ((wo), 90 = V((wo), and qo = 90-
for t 1 to T do
Sample blocks 4, and J, uniformly on [n/b]. and define K₁ =t t mod (n/b) +
Primal Update:
Set -p 1 04-1" LiEB, (9-11, V(((ee)) 22-22-0-221 update we using (5).
oib
Update table (be, Dc,e) to (fx(wr); Vle(wr)) if BR, or (f1-1,8, $1-1 1.)) if & Bk
Dual Update:
Set uP = + aeb LjeBn, (L)(w)) ( update qi using (7).
Update table Gr, to dr if E Bx, or gr- 1 if Bk.
end for return (WT.QT).
Assumption 1. Let .i,...,,,,, En be G-Lipschitz continuous and L-smooth, in that for all E [n]]
[[(,(w) (,('))l )11 S G || [/w- 12 and [[V[;(w) Vl L ||w w 12
i.e, each & is G-Lipschitz continuous and L-smooth with respect 11-112- Let μ. and v/ O, and let q + (qq]inn/n) be 1-strongly convex with respect to I1- Finally, Q is closed, convex, and contains 1/n.
Regarding Asm. an example of a loss function satisfying both Lipschitzness and smoothness is given by the Huber loss used in robust statistics [Huber, 1981]. Another setting in which both assumptions are satisfied is when the domain W is compact, as smoothness will imply Lipschitz continuity. Compactness is a common assumption when pursuing statistical guarantees such as uniform convergence. As for the assumption of strong convexity, we describe modifications of the algorithm when 0 or = 0 in Appx. C.4 along with corresponding changes in the analysis.
Theorem 2. For constant a define the sequence
1, .2 4a, and at (1 a) a for tortt > 2,
along with its partial sum A, = Σ' ar. Under Asm. 1, there is an absolute constant C such that using the parameter
11 b
J1v
a C min
n Lin n
nG²
the iterates of Algorithmm satisfy:
ATp Ey |or 1l.1
Arv E,
nG2
Σ
Erl
llrr
<
|wg
w1 11
4
can compute a point (wT, (T) achieving an expected gap no more than e with big-O complexity
Lio
n
nG²
1
(n + bd)
In
(10)
b
By dividing the result of Thm. 2 by Ar, we see that both the expected gap and expected distance- to-optimum in the primal and dual sequences decay geometrically in T'. By plugging in b n/d we get the following runtime for Algorithm 1:
o ( nd ndLRn + n d2
G w
In
(11)
11

---

Note in particular the individual dependence on the condition numbers L/u and nG² nG²//wv), as opposed the max-over-minn eiver-mi-ttppe condition numbers such as those achievable by generic primal- dual or variational inequality methods (see Appx. B.3). The proof of Thm. 2 is provided in Appx. C, along with a high-level overview in Appx. C.I. Our analysis relies on controlling ar' by bounding a, (w,, (t) above and bounding 0g (u q.) below. Key technical steps occur in the lower bound. We first apply that w + ag {(w) is convex to produce a linear underestimator of the function supported at W1, and use that Wo the minimizer of strongly convex function, so
a1 C(w. 9c) z arq, k(w)) + telescoping and non non-positive terms
+ 0r (V((wr) gr u - -w:-w>
(12)
Cafí
||w, wrvoll2
(13)
2
Note that the terms above will be negated when combining the upper and lower bounds. The laheled terms highly relevant in the analysis, with the second being non-standard. By expanding the definition of of and adding and subtracting W4-1, we write
ae ( (V((w) qe ur w. w2) = (Ve(w))) 2/_ 14-1,11100 -wi)
nd
Σ
(V (w.-1)gt-1 106-1-9--200 23 W. W
6(1 IET
ndp-
(Vl;(w:-1)9- -2-2, W wt)
6(1 m
When choosing the learning rate 7 correctly, the first two terms will telescope expecta- tion (see Lem. 11). The third term, after applying Young's incquality, requires controlling Eiel, (V - in expectation, which dub the "primal noise bound" (Lem. 5). When we combine the upper and lower bounds, we get a similar inner prod- uct term 0r (2. ge, [(w)) oP)), and mirroring the arguments above, encounter the term Eie, (e,(wr) - 1 which also requires a "dual noise bound" (Lem. 6). Without loss of generality, assume that the blocks are ordered such that
1- (:(w:-1 for E BR.
(14)
By computing the conditional expectation E,[:] = EE[ -1 we have that
E+
Σ JEJ
(ks(wr) 2 =
(er(w)) - e
Σ
(L((wr) ((WW)-1-voo)}
K=
BB
G
t-2
Σ
where the second line follows from (14) and the third from G-Lipschitzness. This will telescope with the second term introduced in (13), showing the importance of the regularization. The argument follows similarly even when (14) does not hold, as the blocks can simply be "renamed" to achieve the final bound. While the proof is technical, this core idea guides the analysis and the algorithm design.
4 Experiments
In this section, we provide numerical benchmarks to measure DRAGO against baselines in terms of evaluations of each component {(C,, v4,) and wall clock time. We consider regression and classification tasks. Letting (I,, ys) denote feature-label pair, we have that each & represents the
7

---

yaclt
energy
concrete
yacht
En5rgy
concrete
Subossimalits
10711
10
10-1
1077
10
00000 aesincome
3000)
2000: kinSom
10000
power
actincome
kindnm
power
1001
Subostimdiig
10
10
T0000
T0xE1
2000)
Fri-Ordo
Wal-Gock Tima
Wal-Bock
Wal-Clock (Sooodd))
5GD
LSVRG
Drago (b =0= 16)
Drago n//d/
Drago (6
Figure 2: Regression Benchmarks. In both panels, the y-axis measures the primal suboptimality gap (15). Individual plots correspond to particular datasets. Left: The æ-axis displays the number of
individual first-order oracle queries to {44, V4)), Right: The æ-axis displays wall-clock time.
squared error loss multinomial cross-entropy loss, given by
(ww) == 2 (y/, xx, w)
2 and ((()) == -x, was + log Σ exp (a+ wyy)
yEV
respectively, In the latter case, we denote w = (Wi...., WC) E RCxd, indicating multiclass clas- sification with label set y : (1, . ...
C}. We show results for the conditional value-at-risk (CVaR) [Rockafellar and Royset, 2013] in this section, exploring the effect of sample size n, dimensionality d, and regularization parameter y on optimization performance. The parameter interpretations both as conditioning device (as it is inversely related to the smoothness constant of m C(w, q) and as a robustness parameter, as it controls the essential size of the uncer- tainty set. Detailed experimental settings are contained in Appx. E, including additional experiments with the x2 -ivverggee ball uncertainty set. The code to reproduce these experiments can found at http://gghhub.coooooonna///////t
particular has
We compare against baselines that can be used on the CVaR uncertainty set: distributionally robust stochastic gradient descent (SGD) [Levy et al., 2020] and LSVRG [Mehta et al., 2023]. For SGD, use batch size of 64 and for LSVRG we use the default epoch length of For DRAGO, investigate the variants in which b is set to 1 and b = nt/d a priori, as well as cases when b is a tuned hyperparameter. On the y-axis, we plot the primal gap
max C(w,, q) L(w., 9.) max,59 L(wo. 9) [w qx)
(15)
where we approximate L(w., q.) by running LBFGS [Nocedal and Wright, 1999] on the primal objective until convergence. On the z-axis, we display either the exact number of calls to the first- order oracles of the form (lz, V&2) or the wall clock time in seconds. We fix μ but vary v to study its role as a conditioning parameter, which is especially important as prior work establishes different convergence rates for different values of (see Tab. 1).
4.1 Regression with Large Block Sizes
In this experiment, we consider six regression datasets, named yacht (n = 244, d = 6) [Tsanas and 824, d 8)
Xifara, 2012], energy (n 614, 8) [Baressi Segota al., 2020], concrete [Yeh, 2006], acsincome (n 4000, d = 202) [Ding et al., 2021]. kin8nm (n 6553, d = 8) [Akujuobi and Zhang, 2017]. and power univariate, real-valued output. Notice that most datasets, besides acsincome, are low- www-dimensionll as compared to their sample size. Thus, the default block size n//d becomes relatively large, imposing an expensive per-iteration cost in terms of oracle queries. However, when the block size is high, the stochastic gradient estimates in each iteration have lower variance and the table components are updated more frequently, which could improve convergence in principle. The main question of this
7654, d = [Tüfekei, 2014]. In each case, there is

---

M- 10
- 0.01
0.001
p- 0.01
0.01
20
[K] Fackerion (K)
(K)
(Serodd))
(Seood))
(Twoos)
Figure 3: Text Classification Benchmarks. all plots, the y-axis measures the normalized primal (i.e., DRO risk) suboptimality gap, defined in (15). Columns represent varying dual regularization parameter v. On the first three columns the r-axis measures the number of individual first-order oracle queries to {(l,, [4,) and the remaining three the z-axis displays wall-clock time. The objective becomes ill-conditioned as v decreases.
section is whether DRAGO efficiently manages this trade-off via the block size parameter b. Results for gradient evaluations and wall clock time are on the left and right panels of Fig. 2, respectively.
Results The DRAGO variant for b n/d not included on the left plot, as the number of queries (al- most 2,000 in the case of power) penalizes its performance heavily. Still, the same variant performs best or near best on all datasets in terms of wall clock time (right plot). Thus, the computation of the queries is inexpensive enough, DRAGO can achieve the lowest suboptimality within a fixed time budget. This is most striking in the case of kin8nm, in which DRAGO achieves 10-7 primal gap within 1 second, versus LSVRG which is only able to reach within 10-2 of the minimum in the same amount of time. We also experiment with tuning b to reach a balance between the cost of queries and distance to optimum in the left plot with the b = 16 variant. In the datasets with n S 1, 000, DRAGO can match the performance of baselines with only b = 1, whereas in the larger datasets, a batch size of 16 is needed to be comparable.
4.2 Text Classification Under Ill-ooditiioing
We consider a natural language processing example using the emotion dataset [Saravia al., 2018), which is a classification task consisting of six sentiment categories: sadness, anger, love, fear, joy, and surprise. To featurize the text, we fine-tune a pre-trained BERT network [Devlin et al., 2019] on held-out set of 8,000 training examples to learn vectorial representation. We then use disjoint subset 8,000 training points and apply PCA to reduce them to 45-dimensional vectors. Because of the six classes this results in d = 270 parameters to learn. To study the effect of dual regularization, we consider v E {1.0, 0.01, 0.0013. As v decreases, the dual solution may shift further from uniformity, and potentially increase the distributional robustness of the learned minimizer. However, the objective can also become poorly conditioned, introducing a key trade-off between optimization and statistical considerations when selecting v. The results in Fig. 3.
Results The time required for LSVRG to make 500K gradient evaluations is too large to be considered. We also observe that LSVRG is vulnerable to ill-conditioned objectives, as it is out- performed by SGD for smaller values of y in terms of wall clock time. Within 4 seconds, DRAGO can achieve close to a 10-5 primal suboptimality gap while the gaps of SGD and LSVRG are 2 to 3 orders of magnitude larger in the same amount of time. We hypothesize that because the dual variables in LSVRG are updated once every n iterations, the primal gradient estimates may accrue excessive bias. DRAGO with b n/d, making ~ 30 individual first-order queries per iteration, is performant in terms of oracle queries and wall clock time even as v drops by orders of magnitude.
5 Conclusion
We proposed DRAGO, a stochastic primal-dual algorithm for solving a host of distributionally robust optimization (DRO) problems. The method achieves linear convergence without placing conditions on the dual regularizer, and its empirical performance remains strong across varying settings of the sample size dimension d, and the dual regularization parameter v. The method combines ideas of variance reduction, minibatching, and cyclic coordinate-style updates even though the dual feasible set (a.k.a. the uncertainty set) is non-separable. Opportunities for future work include extensions to non-convex settings and applications to min-max problems beyond distributional robustness, such as missing data imputation and fully composite optimization.

---

Acknowledgements This work was supported by NSF DMS- AMS-2023166, CCF-2019844, DMS- 2134012, NIH, IARPA 2022-22072200003. N00014-22-1-2348. Part of this work was done while R. Mehta and Z. Harchaoui were visiting the Simons Institute for the Theory of Computing.
Office of Naval Research under award number
Broader Impact Distributionally robust optimization (DRO) within machine learning is heavily motivated by problems artificial intelligence (AI) safety, such as mitigating catastrophic perfor- mance of models minority groups end-users. While this work is focused theoretical and algorithmic aspects of the problem, we intend to increase accessibility and scalability for down- stream applications well.
References
U. Akujuobi and X. Zhang. Delve: A Dataset-Driven Scholarly Search and Analysis System. SIGKDD Explor. Newsl., 19, 2017.
A. Alacaoglu and Malitsky. Stochastic variance reduction for variational inequality methods. In Conference Learning Theory, pages
PMLR, 2022.
A. Alacaoglu, V. Cevher, and Wright. On the complexity of practical primal-dual coordinate method. arXiv preprint arXiv:2201.0766 2022.
S. Baressi Segota, N. Andelic, J. Kudlacek, and R. Cep. Artificial Neural Network for Predict- ing Values of Residuary Resistance per Unit Weight of Displacement. Journal of Maritime & Transportation Science, 57, 2020.
J. Blanchet, Y. Kang, and K. Murthy. Robust Wasserstein Profile Inference and Applications to Machine Learning. Journal of Applied Probability, 56, 2019.
D. Blatt, A. O. Hero, and H. Gauchman. A Convergent Incremental Gradient Method with Con- stant Step Size. SIAM Journal on Optimization, 2007.
X. Cai, C. Song, S. Wright, and J. Diakonikolas. Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization. In ICML, 2023.
X. Cai, A. Alacaoglu, and J. Diakonikolas. Variance reduced Halper iteration for finite-sum mono- tone inclusions. In ICLR, 2024.
Y. Carmon and D. Hausler. Distributionally Robust Optimization via Ball Oracle Accelcration. In NeurlPS, 2022.
A. Chambolle, M. Ehrhardt, P. Richtárik, and C.-B. Schonlieb. Stochastie Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications. SIAM Journal on Opti- mization, 28 2874)22783- 2018.
L. Condat. Fast projection onto the simplex and the balll.. Mathematical Programming, 2016.
A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A Fast Incremental Gradient Method With Support for Non- Stronnrongly Convex Composite Objectives. NeurIPS, 27, 2014.
Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional trans- formers for language understanding. In Proceedings of the 2019 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics; Human Language Technologies. 2019.
F. Ding, M. Hardt, J. Miller, and L. Schmidt. Retiring Adult: New Datasets for Fair Machine Learning. In NeurlPS, volume 34. Curran Associates, Inc., 2021.
S. S. Du, G. Gidel, M. I. Jordan, and C. J. Li. Optimal Extragradient-Base Bilincarly-Coupled Saddle-Point Optimization, 2022.
N. He, Z.. Harchaoui, Wang, and I.. Song. Point Process Estimation with Mirror Prox Algorithms. 2020..
Applied Mathematics & Optimization, 2020.
10

---

P. J. Huber. Robust statistics. Wiley New York, 1981.
R. Johnson and T. Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Re- duction. NeurlPS, volume 26, 2013.
N. Kallus,, X. Mao, K. Wang, and Z. Zhou. Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning. In ICML, 2022.
D. Kovalev, A. Gasnikov, and P. Richtárik. Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling. In NeurlPS, 2022.
D. Kuhn, P. M. Esfahani, V. A. Nguyen, and Shaficezadeb-Abadehh. Wasserstein Distributionally Robust optimization: Theory and Applications in Machine Learning. Operations research & management science the age of analytics, 2019.
R. Kumar, K. A. Majmundar, D. M. Nagaraj, and A. Suggala, Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization. TMLR, 2024.
D. Levy, Y. Carmon, J. Duchi, and A. Sidford. Large-Scale Methods for Distributionally Robust Optimization, In NeurIPS, 2020.
C. Li, A. Yuan, G. Gidel, Q. Gu, and M. I. Jordan. Nesterov meets optimism: rate-optimal separable minimax optimization. In ICML, 2023.
Lin, C. Jin, and M. I. Jordan. Near-Optimal Algorithms for Minimax Optimization. In COLT, 2020.
E. Z. Liu, B. Haghgoo, A. S. Chen, A. Raghunathan, P. W. Koh, S. Sagawa, P. Liang, and C. Finn. Just Train Twice: Improving Group Robustness without Training Group Information. In JCML, 2021.
Z. Liu, Q. Bai, Blanchet, P. Dong, W. Xu, Z. Zhou, and Z. Zhou. Distributionally Robust Q- Learning. In ICML, 2022.
K. Lotidis, N. Bambos, J. Blanchet, and J. Li. Wasserstein Distributionally Robust Linear- Quaara-t Estimation under Martingale Constraints. In AISTATS, 2023.
R. Mehta, V. Roulet, K. Pillutla, L.. Liu, and Z. Harchaoui. Stochastic Optimization for Spectral Risk Measures. In AISTATS, 2023.
R. Mehta, Roulet, K. Pillutla, and Z. Harchaoui. Distributionally Robust Optimization with Bias and Variance Reduction. In ICLR, 2024.
H. Namkoong and J. C. Duchi. Stochastic Gradient Methods for Distributionally Robust Optimiza- tion with f-divergences. In NeurlPS, 2016.
H. Namkoong and C. Duchi. Variance-basce Regularization with Convex Objectives. NeurlPS, 2017.
J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
B. Palaniappan and F. Bach. Stochastic Variance Reduction Methods for Saddle-Point Problems. NeurIPS, 29, 2016.
R. Rockafellar and O. Royset. Superquantiles and Their Applications to Risk, Random Vari- ables, and Regression. In Theory Driven by Influential Applications. Informs, 2013.
H. Sapkota, D. Wang, Z. Tao, and Q Yu. Distributionally Robust Ensemble of Lottery Tickets Towards Calibrated Sparse Network Training, In NeurIPS, 2023.
E. Saravia, H.-C Liu, Y.-H. Huang, Wu, and Y.-S. Chen. CARER: Contextualized Affect Representations for Emotion Recognition. In EMNLP, 2018.
V. D. Sharma, M. Toubeh, L. Zhou, and P. Tokekar. Risk-Aware Planning and Assignment for Ground Vehicles using Uncertain Perception from Aerial Vehicles. 2020 IEFF/RSJ IROS, 2020.
11

---

C. Song, S. J. Wright, and J. Diakonikolas. Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In ICML, 2021.
C. Song, C. Y. Lin, S. Wright, and J. Diakonikolas. Coordinate Linear Variance Reduction for Generalized Linear Programming. In NeurIPS, 2022.
A. Tsanas and A. Xifara. Accurate Quantitative Estimation of Energy Performance of Residential Buildings Using Statistical Machine Learning Tools. Energy and Buildings, 49, 2012.
Tüfekci. Prediction of Full Load Electrical Power Output of Base Load Operated Combined Cycle Power Plant using Machine Learning Methods. International Journal of Electrical Power & Energy Systems, 60, 2014.
S. Wang, N. Si, J. Blanchet, and Z. Zhou. A Finite Sample Complexity Bound for Distributionally Robust Q-learning. In AISTATS, 2023a.
Z. Wang, L. Shen, T. Liu, T. Duan, Zhu, D. Zhan, D. Doermann, and M. Gao. Defending against Free Model Extraction by Distributionally Robust Defensive Training. In NeurlPS, 2023b.
O. Wiles, S. Gowal, F. Stimberg, S.-A. Rebuffi, I. Ktena, K. D. Dvijotham, and A. T. Cemgil. A fine-gratne ane-grained analysis on distribution shift. In JCLR, 2022.
G. Xie, L. Luo, Y. Lian, and Z. Zhang. Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems. ICML, 2020.
Yang. S. Zhang. N. Kiyavash, and N. He. A Catalyst Framework for Minimax Optimization. In NeurIPS, 2020.
Z. Yang, Y. Guo, P. Xu, A. Liu, and A. Anandkumar. Distributionally Robust Policy Gradient for Offline Contextual Bandits. AISTATS, 2023.
I. Yeh. Analysis Strength of Concrete Using Design of Experiments and Neural Networks. Jour- nal of Materials in Civil Engineering, 18, 2006.
Y. Yu, T. Lin, V. Mazumdar, and M. Jordan. Fast Distributionally Robust Learning with Variance- Reduced Min-Max Optimization. In AISTATS, 2022.
Z. Yu, L. Dai, S. Xu, S. Gao, and C. P. Ho. Fast Bellman Updates for Wasserstein Distributionally Robust MDPs. In NewrIPS, 2023.
Zhang, M. Hong, and S. Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematial Programming, 194, 2022.
12

---

Appendix
Appx. A contains all notation introduced throughout the paper. Appx. B discusses convergence rate comparisons detail with contemporary work. The full convergence analysis of DRAGO given in Appx. C. description of the algorithm amenable implementation given Appx. D, whereas experimental settings are descrihed in detail within Appx. E.
Table of Contents
A Notation
14
B Comparisons to Existing Literature
15
B.1 Directly Using Gradient Descent
15
B.2 Distributionally Robust Optimization (DRO)
15
B.3 Primal-Dual Saddle Point Algorithms
C Convergence Analysis of DRAGO
21
C.I Overview
21
C.2 Technical Lemmas
23
C33 Proof of Main Result
29
C.4 Modification for Unregularized Objectives
40
Implementation Details
Algorithm ................................
................................
44
D.2 Solving the Maximization Problem
44
E Experimental Details
48
E.1 Datasets
48
E.2 Hyperparameter Selection
48
E.3 Compute Environment
49
Additional Experiments
49
F NeurIPS Paper Checklist
51
13

---

A
Notation
Symbol
Description
"
Sample size, or number of loss functions.
d
Dimensionality of primal variables.
S R
Primal feasible set, which closed and convex.
Uncertainty set, or dual feasible set, which is closed and convex.
Q A
Here, A {p [0. 1]"h Σi
1}.
90
The uniform vector @o 1/n = (1/n,.... 1/n). Used a dual initialization. statistical divergence between g E Q and go. which is I-strongly convex in its first argument with respect to Il-l12-
D(allg))
Loss function E W I", which differentiable in each component on an open set O C B such that W O.
t
2 0
Primal regularization constant.
Dual regularization constant.
C(w, 9)
Objective function ((w, := q [(w) vDlll + " 1 Saddle point of L, which satisfies
(wa.q.) .w)
((w.,9) 9) S f((... q-) & [(w:, q-) for all (w, E W Q
[r]]
Index set [rt] (I....,n). The value m llall The condition number Ki niuaax 2 Lipschitz continuity constant each 6, for E [n]. for which [fx(w) (((w/) - G || w 1l2-
fmxx
Ri
G
Lipschitz continuity constant of each V4; for [n]. for which ([V((()) Ve,(")) ] S ||w w l
L
V((w)
Jacobian matrix of É: R + R at w (shape n d).
(oc)
Sequence of positive constants that weigh the average gap criterion. Sequence of partial sums of (ax), A Ei a. The convergence rate will be given by A," so have a increase geometrically. Batch or block size.
(4,)
b
M
Number of blocks n/b.
(wx, gr )22
Sequence of primal and dual iterates.
ej
The j-th standard basis vector ej E (0,1)"'
é.
Loss table, which approximates ((wr) E R
Gradient table, which approximates Vf(wx) E Raxd
â.
Weight table, which approximates de E Q.
E, [-]
Shorthand for [.1 (4-1]] i.e., expectation conditioned on history H4-1 (1I.)
Table 2: Notation used throughout the paper.
14

---

B Comparisons to Existing Literature
In this appendix, we compare our work to existing literature along two axes: distributional robust optimization (DRO), and 2) primal-dual algorithms for saddle-poini problems. In the first cate- gory, we are primarily concerned with questions of practical and statistical interest, such as which uncertainty sets can be used, how the size of the uncertainty set affects the convergence rate, and what assumptions are needed on the distribution of losses. In the second category, we discuss com- putational complexity under various assumptions such as smoothness and strong convexity of the objective.
B.1 Directly Using Gradient Descent
In the penalized case, we add that the objective + m L(w, q) is (L - p + nG', )-smooth when the losses l, are G-Lipschitz continuous and L-smooth. For this reason, we may consider simply applying full-batch gradient descent to this objective, which is included in our comparisons. To see why this smoothness condition holds, define h(T) = maxge {q 1 |/l]ll//n), so that when q + D(gll//n) is 1-strongly convex with respect to 11-112- it holds that V is (1/r)-Lipschitz continuous with respect to I1-11:: and that Vh(l) is non-negative and sums to one (i.e. is probability mass function on [n]). Then, by the chain rule, for any wi, w2 E W, we have that
[ Vh(e(w:)) (2())) vh(((w2))] vh(((w>)))]l + [[(((w)) (VV(
s nG ( - {(w2)112 + I. || -
v
nn +1.) ||un w2
Thus, when referring to the gradient descent on w maxgeo L(w,g) h((((w)) + ||w || we reference the smoothness constant
(L+ μ n
B.2 Distributionally Robust Optimization (DRO)
Examples of DRO Problems
Our problem
min max we W TEQ
[(w,, q) q. ===((w)=v((())) 1 + |
(16)
accommodates several settings of interest across machine learning. For example, f-DRO with pa- rameter o [Namkoong and Duchi, 2016, Carmon and Hausler, 2022] results by defining the uncer- tainty set and penalty as
@ = Q(p) = (q: Dylll/))) 2} and D(gll1/n) Dy(q)11/m).
where Dy(alpp) Σn - Paf(li///// denotes f-divergence generated by f (which is always
well-defined when = 1/n). Common examples include the Kullback-Leibler (KL) divergence, generated by fKL(x) x log x and the >d-divergeece generated by fx)(x) (a 1) Spectral risk measures [Mehta et al., 2023] are parametrized by an n-length vector o (a o.,) such that 0 < σi S... on and Σn a; 1. The penalty that setting may also in the form of an f-divergence [Mehta et al., 2024], so that
Q (())) == conv ((permutations of o)}) and ((gll//m) = (all///n).
where conv (-) denotes the convex hull. The most notable example of such an uncertainty set the 0-conditional value-at-risk, or CVaR [Rockafellar and Royset, 2013], wherein the largest On values of a are set to 1/(n0) and the remaining are set to zero (with fractional component On not an integer). Finally, Wasserstein-DDe parameter 8 typically sets the uncertainty set to be a 8-ball {Q Wa(Q, P.) S 8) in Wasserstein distance, where Q is probability measure, P, is the empirical measure of the training data, and
[Kuhn et al., 2019, Blanchet et al., 2019, Yu et al., 2022] with
15

---

We is the Wasserstein distance associated to cost function c. This differs from f-DRO and spectral risk minimization because in the latter settings, the "shifted" distribution Q assumed remain on the same n atoms as before, so that it may simply be specified by probability vector q E [0, 1 (resp. P.. by 1/n). However, as shown by Yu et al. [2022], Wasserstein-DRee can be reformulated into a problem of the form (16) if the following conditions are satisfied: 1) the loss is of generalized linear model e, (w) = ((w, zx) 93) with feature-label pair (at,, yi) and discrepancy function V, 2) the cost function c((x, v), (a', y²)) is of the form || x' ll2 + B ly y'1 for B > 0, and 3) the function V is Lipschitz continuous with known constant.
Comparison of DRO Approaches The performance of classical and recent algorithms designed for the problems above is detailed in Tab. 3. The rightmost column displays the oracle complexity, meaning the number of queries to individual/componee loss functions {L, V&,)} function of the desired suboptimality e. The desiderata in the large-scale setting is to decouple the contribution of the sample size and the condition number in smooth, strongly convex settings (u > O and L < oc) or the quantity 1/E in non-smooth or non-strongly convex settings. For readability, we encode dependence on in red and dependence on 1/c in blue within Tab. 3. In certain cases, such as in the sub-gradient method, the dependence on n is understood as part of smoothness constant. Similarly, because ymax is of order 1/n in the best case and in the worst case, we interpret Kig to play the role of a condition number that measures the size of the uncertainty set. That being said, ko upper bounded by a constant independent of in common cases. We collect examples of these results below.
Proposition 3. In (16) if Q is chosen to be the CVaR uncertainty set with tail probability 0, then Ki S 8- If is chosen to be the 2DRRO uncertainty set with radius p. then Kg S v + p.
Proof. For the 0-CVAR, we have that qs E [0, 1/(n0)) for all i E [n]] Thus,
ng: S g
for all I,...: n.
For the x-DROO uncertainty set, we have by direct computation that
n 119 1 1/nl
< L +
| S
1 ++
n
n²
This implies that for any E [nx]. we have that df < (1 + p)/n² which implies that
ng: S V1+p
the result desired.
The closest comparison to our setting is that of LSVRG [Mehta et al., 2023] and Prospect [Mehta al., 2024]. Including DRAGO, these methods all achieve linear convergence on (16). under the assumption of strongly convex regularization in the primal objective. However, both LSVRG and Prospect demand stringent lower bound of Q(n //²) on the dual regularization parameter v to achieve this rate, which essentially matches ours in this regime (as /nG² / (pw) reduces to a con- stant). When this condition does not hold, however, LSVRG does not have convergence guarantee while Prospect underperforms against the sub-gradee gradient method. Furthermore, while Propsect has a single hyperparameter, LSVRG must search over both learning rate and an epoch length. DRAGO, on the other hand, is the only method that achieves unconditional linear convergence and fully cap- tures the dependence on the dual regularization parameter which is a smoothness measure of the objective max, L(:.g).
Moving to methods that are not linearly convergent, Levy et al. [2020] consider a variant of mini- batch SGD that solves the maximization problem within the mini-batch itself. In Tab. 3, we include a term min fn. b(E)}. where b(=) denotes a required batch size. This is because Levy et al. [2020] measures complexities in terms of calls to first-order oracles for loss summed across an arbitrary batch size. Thus, our comparison relies on multiplying the required batch size with the number of iterations required for a desired suboptimality (see Levy et al. [2020, Theorem 2], for example). In the setting in which there is a fixed training set of size we incorporate this requirement on the batch size the complexity bound, to account for the case in which the theoretically required batch size grows so large that it exceeds the full batch size itself. Indeed, as commented by Carmon
16

---

and Hausler [2022], when the uncertainty set is large (i.e. O is small for CVaR and p is large for d--divergence) the method may underperform against the sub-gra uub-gradient method. This is true of methods such as in Mehta et al. [2024] and ours that depend on K2 S n. This indicates that across DRO settings, increased uncertainty set sizes can bring the performance of incremental methods arbitrarily close to that of the full-batch sub-gradien method. Finally, notice that DRAGO also has dependence on the batch size b in Tab. 3. While would appear that 6 = 1 would minimize oracle complexity, we describe in the next section how b can be chosen to minimize global complexity. which includes the cost of each oracle call as a function of the primal dimension d. Because of the diversity of settings, coarser measure such first-order oracle evaluations may be sufficient to compare methods along the DRO axis; we use the finer-grained global complexity to compare methods along the axis of saddle-point algorithms.
B.3 Primal-Dual Saddle Point Algorithms
For context, both (1) and (2) are coupled min-max problems with primal-dual variables (w, q). Ob- serve that the coupled term in the objective (depending on both w and q) is not bilinear in general. Such objectives have received much less attention in the optimization literature on primal-dual meth- ods than their bilinearly-couppe algorithms [He et al., 2020, Song et al., 2021] use stochastic suriance-reduced updates, and in particular, employ coordinate-style updates of single dual variable per iteration. To illustrate the advantage of these updates, notice that the primal and dual dimensions are and n, respectively. When is significantly larger than d. and assuming that each (f,, V&;) call comes at an ((d) cost, updating the dual variables (()) cost every iteration becomes the primary compu- tational bottleneck. Coordinate-style updates can eliminate this dependence, but apply only when the dual feasible set Q decomposes as 2 ... x On. i.e., separable.
counterparts. For the bilinear setting, methods such as stochastic
Hhambolle-oock-see
There is a long line of work on variance-reduced algorithms for general stochastic optimization problems [Johnson and Zhang, 2013, Defazio et al., 2014, Palaniappan and Bach, 2016, Cai al., 2023] and structured and/or bilinearly coupled min-max problems [Yang et al., 2020, Song et al., 2021, Du et al., 2022, Kovalev al., 2022. Alacaoglu et al., 2022]. However, few of these results can be directly applied to (2) due to non-bilinearity and non-separability of the dual feasible set. These issues motivated work on reformulating common DRO problems as bilinearly coupled min- max problems in Song et al. [2022]. However, the guarantees obtained in Song et al. [2022] are of the order O(E-)).
Another viewpoint is that (2) can be written as a monotone variational inequality (VI) problem for the operator F(w, g) (V (ww) T q + jaw, -((w) + D(gl E Rd4*, where we assumed 1 1-smoothness of D for ease of presentation. Under our assumptions. this operator is min (H, strongly monotone and max {nG², L. -Lipschhtt continuous, and VI algorithms such as mirror- prox, Popov's method, and variance-reduced methods like Alacaoglu and Malitsky [2022], Cai al. [2024] can be used. However, the max-over-min dependence on the individual Lipschitz constants and strong convexity constants is unfavorable compared to the individual condition numbers ob- served in (4). If F is called directly, the global complexity will be n² because is n-ddimensional along with in the condition number. A finite sum approach could improve dependence on the number of oracle calls, but the global complexity would still be n² due to the non-separability of the dual feasible set and again the n-dimensional dual variables.
To summarize the points above and in order to make comparisons among methods for general min- max problems, we first collect aspects of (16) that make it highly specialized problem in this regard. The major points include:
1. The objective has a fimite-sum structure, in that it can be written as E Si(w, q), where fi (w,,) == (w) (Dlll + //2 ||
2. The dimension of the dual variable is equal to n, the number of functions in the sum (i.e. the sample size), and could be much larger than d.
3. The dual regularizer q + (( 1/n) is not necessarily smooth. This encompasses common statistical divergences such as the Kullback Leibler (KL).
4. The dual feasible set Q is non-separable, as any feasible dual iterate must sum to 1.
17

---

For discussions in which linear convergence is pre-requisite, it is typically assumed that (w, q) H [(w, q) is smooth map, and finer aner-grained results depend on the individual Lipschitz continuity parameters of to + V (w. ()..q). + V (f( wt g), - (w, q). and q - (w,, q). To make the regularized DRO setting of (16) comparable to classical and contemporary saddle-point methods, we make the additional assumption in this section that the (rescaled) x² -divergence penalty is used, so that (4 1/n)
1/2 l1g 1/mll2 and we may compute the smoothness constants
[(, q) V -w 1l12 - (L + n)) I w' w'll2
[w, 9) vwL(w, = [[ve(w) [|
d')ll2 S VnG -
V,,((w, ②) - v,[(w, S v 11q - --'lla
(17)
V VgL(w,g) ②) Vgf(w', ,9]l12 = [|((w) - ((2))l22 S VnG w w'll
(18)
| (w.g) [(w, ((w.)) . S ((L+ V (GG)v21((u,, (wl, 11222
(19)
In making this assumption, however, we emphasize that our results do not depend (17), (18), and (19) being true. We assume here that calls to the oracles (l,, Vwei) cost O(d) operations while calls V.f cost (n)) operations, making the total O(n d). This per-iteration complexity is subtlety of DRO which is essential to recognize when comparing methods. With DRAGO, we also have batch size parameter b, setting the complexity to O(n + be). By tuning b, may achieve improvements in terms of global complexity over standard primal-dual methods. Results comparing linearly convergent methods in terms of the global complexity of elementary operations in Tab. 4. The table contains a "half-life" column, which is the constant T multiplied with (og(1/e) when describing the number of iterations needed reach e-suboptimality as T (1/)).)). Before comparisons, observe that the optimal batch size for DRAGO is = /2/ d, in the sense that the global number of arithmetic operations is of order
given
LUO
nG²
n
+ nd
uuv
This is improvement setting b = 1, in which case the same number is
(n + d) Lie + +n(n + d)
nG²
Next, the most comparable and recent setting is that of Li et al. [2023]. Notice that DRAGO is able to improve by a factor of d on the y term, long as KQ = (1).
μ
While less comparable, we mention known lower bounds for completeness. In terms of lower bounds, since (16) enjoys a particular structure, such as decomposability into so-called marginal terms (gl 1/n) and & || and a coupled term q7 f(w). we are not necessarily constrained by the more general lower bounds of Zhang et al. [2022] and Xie al. [2020]. For example, the prox- imal incremental first-order (PIFO) model of Xie et al. [2020] assumes that we observe first-order information from single component in the sum; in DRAGO, using batch size of n/d is required to achieve the desired improvement. Zhang et al. [2022], on the other hand, do not treat the finite sum class of problems considered here. Furthermore, we still list the per- per-iteration cost as O(n d) because a single PIFO call to the dual gradient is of size n.
18

---

nd. (GBya/a 2/3 + n (GRe -1 1 1/2)
nin d) max {nō 6elgomx ne 62 n266) log(1/c) (R + (igg) (n + dolog( 1/))
(d (d+ + dy (G/) log(1/E)
Runtime Global Complexity (Big- O)
min {u, B 1- - (GD) min (n, (1+ d)B: 2) d (-
nd: g- (L+ + nV) no) log(L/e)
min (n. B (GR)
nd- (GR)2 273 + d
None (n (gg)) ( 11o)(1/e))
nd (GR)
nd Gp
Spectral Risk Measures (v 2 92n6 /p))
Spectral Risk Measures (vr 2 Q(n (p))
Spectral Risk Measures (2 small)
Spectral Risk Measures small)
Support Constrained
Support Constrained
Support Constrained
p-ball in x d-vivergence X² divverreecce penalty
I-ball /-divergence 1-bull in f-divergence
Support Constrained
Unvertainty Set
Table 3: Replicate of Tab. 1.
D.C
#> 0>0, A. == (L + d/u,, G ((w)
VA is L-pischhitz and v >> 0 (if included)
|| - wfl1, all nn w/ e w
b| l2 for w/ w
1/w - w < R included)
is G-Lipcchitz and [0, B]
V/, i.s.pitc (if included)
# >> 0. > 0, K: (L H/p
#> 1, b:= Batch Size
& is G-Lipschitz
> 0 (if incluudd)))
>> (if included)
f. is G- Lipschitz
1, is G-Lipschitzz
V.. is L-Liscchitz
is Giipscchitz
VE, is L-Lipschitz
is G-iisscizzz
Ve, is Lipsschttz
Assumptions
[Carmon Hausler, 2022]
Sub- Gradient Method
(Levy et al.. 2020)
[Mehta al., 2023]
[Mehta et al., 2024]
Leva SGD! SyD-
Cx SGD!
DRAGO (Ours)
Method
BROO
BROO
LSVRG
LSVRG
Prospect
Prospect
19

---

Method
Assumptions
Half-Life
Per-Iteration Cost
Sub-Gradient Method
L+H
nG
nd
1 n
Minimax-APPA [Lin et al., 2020]
( vnc Vie
nd
Finite Sum
Lower Bound [Xie al., 2020]
n (I.ta)w min(p.]
Single component oracle
n n
May not be decomposable
Lower Bound
May not be decomposable
L+H + a
nG
nd
[Zhang et al., 2022]
May not be finite sum
AG-OG with Restarts
V
nG
nd
[Li et al., 2023]
Lsq
nC2
Drago (b 1)
1/11 need be smooth
11
12
n
Drago (b = n d)
LKg
+ d.
nC7
Drago (b = n))
Lug
+
nd
Table 4: Complexity of Primal-Dual Saddle Point Methods. Half-life (defined as т such that linearly convergent method requires O(7 log(1/e)) iterations to achieve e-suboptimality) and per- iteration cost of linearly convergent optimization algorithms. The global number of arithmetic oper- ations (under the assumption that (&,, &, costs (dd) operations and V.C costs ((n) operations) required to achieve a point (w. q) satisfying L(w, q.) L(w., 9) S can be computed by multi- plying the last two columns. The "Assumptions" column contains changes to the assumptions that each & is L-smooth and that (-- is y-smooth.
20

---

C
Convergence Analysis of DRAGO
This section provides the convergence analysis for DRAGO. We first recall the quantities of interest and provide an alternate description of the algorithm that is useful for understanding the analysis. high-level overview given in Appx. C.I, and the remaining subsections comprise steps of the proof.
C.1 Overview
See Tab. 2 for a reference on notation used throughout the proof, which will also be introduced as appears. Define qo 1/n and recall the objective
[(w, q) q (T((w) vD(allo)) M |w|l
(20)
By strong convexity of + max, L(w; q) with respect ||-1|2 and strong concavity of g miny [(w, q) with respect to I1- a primal- solution pair (w", q²) is guaranteed to exist and is unique, and thus we define
W.
arg min max [ww, q) and q. arg min [(w, q)- qeQ wEW
WEW
q
In other words, we have that m [(w., g) = [(w,, q.) = ei L(w, q.). We proceed to describe the algorithm, the optimality criterion, and the proof outline.
Algorithm Description First, describe two sequences of parameters that used to weigh various terms in the primal and dual updates. The parameters are set in the analysis, and the version of the algorithm in Appx. is description with these values plugged in. However, we keep them as variables in this section to better describe the logic of the proof.
Specifically, let (0x)121 be sequence of positive numbers and define dg = 0 in addition. Denote A, Σ 0g- These will become the averaging sequence that will aggregate successive gaps Tt. (see (27)) into the return value Σ 0,%,, which will be upper bounded by constant in T (in expectation). We also define another similar sequence (c))211, and define C. A₁ - (n/b- for batch size b. We assume for simplicity that b divides n. When all constants are set, the algorithm will reduce to that given in Algorithm We have one hyperparameter a > which may be interpreted as learning rate.
Using initial values wi 0 and qu = 1/n, initialize the tables lu = f(wo) E R" 9o V((wo) E Raxdd and ÿo = E TR. In addition, partition the [n] sample indices into M == n/b blocks of size 6, BI.... Ba with Bx ((K- 1)b 1, , Kb) for K [M]. We can set the averaging sequence according to the following scheme:
Q1 1, 02 = 4a, and a = (1 + a) a-11 for > 2.
The initial value 02 4a slight modification for theoretical convenience, and the algorithm operates exactly as in Appx. D in practice. In order to retrieve the Appx. D version, we simply replace the condition above with a (1 + q:) a;-1 for t 2 2.
Consider iterate E f1,.... We sample a random block I, uniformly from [M] and compute the primal update.
of = b Σ
(1-11, Ve((w)-1) - (1-2,00t-2))
(21)
SEB
nai-1 5p
of = gf 16-1 1
(22)
a₁
W. arg min ag (op w) wEW
aefl
|w
C1-1/1
||
we
4-1
Σ
1-2
|| w wsvo
11
2
s=t-n/b
(23)
21

---

We see that C--1 + (n-(nn/b 1) = AL-1, so the inner objective of the update (23) is Aqp- strongly convex (as the one (26) A,v-strongly concave). Note that when n/b 1, we simply treat the method as not including the additional regularization term 9--1 Σ E w|w - wavollz- 2
Proceeding, we then modify the loss and gradient table. The loss update has to oceur between the primal and dual updates achieve control the variation in the dual update (see Appx. C.2). Define K2 =t mod M + as the (deterministic) block to be updated, and set
(Be(we)) Vex(w)) if l E Bk. (11-111
(e. -
otherwise
Define ej to be the j-th standard basis vector. Then, sample a random block Jr uniformly from [M] compute
8.
Σ (es(wr)
(24)
JEBu
0/
& +
na
60
(25)
at
Q: arg max as (v..9) D.vllo))))) AL-1VAp(a.--1
(26)
T
Notice the change in indices between (21) and (25), which accounts for the update in the loss table that occurs in between. Finally, must update the remaining table. Set
qr,k 1
if Bk. otherwise
de.k
We define the random variable H4 := Jo)) the history of blocks selected at all times up and including f. and define E, to be the conditional expectation operator given H4-1- other words, E,, integrates the randomness {(T,, Ja)] Accordingly E,, [-] is the marginal expectation of the entire random process. We may now describe the optimality criterion.
Proof Outline
Construct the gap function
Th ae (Clwe, q-) L(w-, 4:) [ wx12
11 2-112)
(27)
by a constant. Throughout the proof, we will use a free parameter and aim to bound E2 ESe 7/s a, with update rule
min {(1+ 9)
1)²n/
(28)
Because we will search for a down to an absolute constant, we will often swap (1 + a) for (1 + a) for readability. We assume the right-hand side of (28) holds in Step and Step 2. We then select to satisfy this condition (and all others) in Step below. The proof occurs in five steps total.
1. Lower bound the dual suboptimality o.L(w., q:)-
2. Upper bound the primal suboptimality acC(w, q.), and combine both to derive a bound on the gap function for /. 2.
3. Derive all conditions on the learning rate constant a and batch size b.
4. Bound " and sum 7: over for T-step progress bound.
5. Bound the remaining non-telescoping terms complete the analysis.
We begin with section of technical lemmas that will not only be useful in various areas of the proof but also capture the main insights that allow the method to achieve the given rate. Given these lemmas. the main proof occurs in Appx. C.3 and otherwise follows standard structure.
22

---

C.2 Technical Lemmas
This section contains a number of lemmas that describe common structures in the analysis of quan- tities in the primal and dual. Lem. 4 bounds cross terms that arise when there are inner products between the primal-dual iterates and their gradient estimates. Lem. 5 and Lem. 6 are respectively the primal and dual noise bounds, constructed to control the variation of the terms of and op ap- pearing in (21), Finally, Lem. 10 exploits the cyclic style updates of the q table to bound the term || 1 - gr 2-22222 which is used in the primal noise bound.
Cross Term Bound Both of the estimates of the gradient of the coupled term q ((w) with respect to the primal and dual variables share a similar structure (see (22) and compare to (29)). They are designed to achieve a particular form of telescoping, with a remaining squared term that can be controlled by case-specific techniques. This can be observed within Lem. 4. In the sequel, we will refer to a sequence of random vectors (uz)e21 as adapted to He, where Hr = ((T,, J.)). is the history of random blocks. This simply means that Ur when conditioned on H is only function of the current random block Jc). Similarly, conditioned on Hz- we have that u is not random. In the language of probability theory, (orHH) }22 forms a filtration and is o (Hs)- measurable, but this terminology not necessary for understanding the results.
Lemma (Cross Term Bound). Let (1z)121. (ut)e21, and (ūt )22 denote random sequences of valued vectors, and let Fx E Ih" be vector, Denote by It be the index of a uniform random block [M]
Ra4-1 1
Up = Dt-1
E(1111 11-2,))
(29)
Ot
SEBI.
Finally, let (Ies yt: 12) adapted He (as defined above). Then, for any positive constant 7 >
ae B. 1,, xx)] S Be [ive 1, xz)]] a1-1 (Wi-1
11-2. x2-1)
+ n a Er EiER, (y0-1,1 21-), ||²
2 2 Ee 1|x, - xr-
+
27
2
Proof. By plugging in the value of i and using v. - Jt. = Ix 8t- + It-1 - It, we have that
(/ve 0z, x+ - -xt)] = arE, [(ye i1 1, szt1l -aan-11. R,
Σ
(yt-1 - G1 2): x' - 8t.
b
iEBi,
11-1, - xztil -0-1 (11-1
Ôt -1-2, F4-1)
( Σ (11-1 2)-2), Fz x1-1 1
+ na EE,
'EBI,
< E, 1(y1
11-1, - xz)1l a1-1 (16-1 - 01-2, - 12-1)
n2a a E,
1/b EieB,, (y1-1,i 21 22-2,)) ||:
+ 2 EE, 1|,, x2-1
27
2
where the final step follows from Young's inequality with parameter
In the primal case, have that 1 = of y: vl(w,) gt d. 9, qr. and x, wy. In the dual case, have that U,- uf Vt ((w,), ú. let2. and x2 = q. The next few lemmas control the third term appearing in Lem. 4 for the specific case of the primal and dual sequences.
Noise Term Bounds Next, we proceed to control the 8, and 6p by way of Lem. 5 and Lem. 6. As discussed in Sec. 3, key step in the convergence proof establishing control over these terms. Define (1., i) to satisfy dr, = (x(t.,),t and Ôt.ü = Vl, (w)(tt))) that is, the time index of the last update of table element i on or before time L. This notation is used to write the table values such as in terms of past values of the iterates (c.g., q:).
23

---

Lemma (Primal Noise Bound), When t 2 2, we have that
34max
91-14 [[
(V
n
3qmax
(x(t-2,5) [l((W<(t-2.)) - Vle(w*)l12
7
i=1
3G
1t-11
20-2
(30)
Proof. By definition, we have that
E
10 11
E.
|| EiEB, -1( - 2, 2,
| - 2, 2.2
12
02 Be
$ E2 b
EiEBi, ( - -. -,222,
V((ww-1) -101-11-------0
where we use that 4 is drawn uniformly over n/b. Continuing again with the term above, we have
n
I(V((())1) 1. -0:-2, V(s(w+)) (ft-1, 2.-2,) (e:(w=)11
3
Σ
2 V 22, 11 - ve((w-)11
11
1=1
+ (90-1. 2,1) (
3 Σ
qmax 4 1, (e ve((w))11 Imax 21- 110 Ve((w)))1
11
+ (90-1, - (022;)
where we use that [VV )1² < G2 because every is G-Lipschitz with respect to 11-112- and that 5 4max = m / | This completes the proof.
The corresponding dual noise bound Lem. follows similarly, using cyclic updates in loss table.
Lemma (Dual Noise Bound). For 2
2,
G
1-2
E2
2
Σ
| wyvol2
71
T=t-n/b
24

---

Proof. Then, we may exploit the coordinate structure of the noise term to write
E,
100111
Ex
1
Σ
(B((1-1) -
b
JEBr
1
2
F Σ
(eg(w)=1) - la 1
g²
jEBa
Σ (1-1)))))--2,) -h- (-IwMee)
+ E2,
jzk
1 E,
Σ (B/(wr-1) le 1
ba
JEB₁,
1
E
Σ
(e 20-
b²
jEB
(((w=11) 1,12
bn
i=1
G
|1we-1-w
The red term is zero because * k. The sum in the last line has n/b terms because our order of updates forces one of the blocks of the h--1 vector to have values equal to Wr-1 before defining op-
Controlling the Recency of the Loss Table In this section, bound the 1|g:-1 2-22 term appearing in the primal noise bound Lem. 5. Controlling this term essential to achieving the correct rate, as we comment toward the end of this section.
Recall that the [n] indices are partitioned into blocks (Bi,..., BM) for M = nt/b, where assumed to divide n. For any 2 1, we first decompose
Σ (g. 2-1,;)²
Σ K=1
(ge.s 9
and analyze block-by-block. Our goal is be able to count this quantity in terms of || - 4t-1 1 terms. The main result is given in Lem. 10, which is built up in the following lemmas. Consider block index K [M]. Define the number Lg M [(t K)/MJ + K when t 1 > K and and tx = 0 otherwise.
Lemma 7. It holds that
Σ BE
( 1,-1,
Σ (1 - (x)
Σ
(go.i - q0-1,;)?
BEBK
s=tk+ +1
Proof. We define (x to be the earliest time index T on or before when block of qr was used to update á.- When < K, then lx = 0. When / 2 K, we can compute this number
25

---

= M 1) - (K - 1)]1/M +K = M 1(t K)/MJ + K. Then, write
Σ
(q1. - -1115)= Σ
(qt.5 9)x,))
E B
kE
=
gosi 9--1d
BE
s=1x+1
tk)
Σ
(90,) 90-1,1)
k
s=tx+1
where the last line follows by Young's inequality.
While we will not be able to cancel these terms on every iterate, will be able when aggregating over time and then redistributing them. Recall (at)121 as described in Appx. C.I. Indeed, by summing across iterations, we see that
n at. 1.-1,)
ax
S
Σ at Σ
Σ - (x)
Σ (g.,1 -0-1)=))1,))? 8=1x+1
K=liEBx
We can start by swapping the first two sums and only considering the values of / that are greater than or equal K.
4
Σ
tk)
Σ
(go,s
1,-1,
Bx
a=tx+1
T
Σ
Σ
(t tk)
(go.t 1,-1,)) +
Σ a: Σ (t (t-ta (t-tk)
Σ
(g0,i 20-1,))
K=l
1=1
BK
s=t++1
K= t=
ieBk
s=
M
K
M T
a1
(qa,
- 1,)), +
Ot
Σ
(t - tx)
Σ
(4aii 1,-1,
K=1
Bx
8=1
K=1t=K
iEBK
+
So
81
(31)
where we use in the last line that ix = 0 when f < K. We handle the terms Sp and Si separately. In either case, have to match the sums over K and over in order create complete vectors, as opposed to differences between coordinates. We also maintain the update rules the sequence (ax)221 that will be used in the proof.
Lemma 8. Assume that a S 1
MJ and a, < (1 + a)ar1. 1. It holds that So as defined in (31) satisfies
So < eM(M 1) M-1
at llqe 9-11
26

---

Proof. Write
M K-
So = Σ
Σ
at Σ
98. 9=-1,;)
by definition
K=
t=1
iEBK
8=1
M-1
M
Σ
ta
(95, - 90-1,5)
swap sums over and
K=t+1
Bx ==1
ta:
Σ
Σ
Σ
(9a. 90-1,;)
move sum over
K=t+liEBr
M
M
to
(gst - 90-1,)²
Σ
()
K=liEBx
K=++1
K=1
M
tot
11. - -0--112
E Σ
Σ
()
K=LiEBK
ta:
110 -0-1112
swap sums over s and
t(1 (11+0) (1) + as
114- - 9--1112
a, (1+
M-1
a=(1+a) M
Σ t
11q. - 10-211
t- 8-$3 M
l1g. as 2
(1+a) M Se
eas
M
M-1
M-1
eas
Σ
11g. 20-11/
Σ
()5 5 ()
1=1
cM -1)
M-1
0g 119 9 70-1112
2
the result as desired.
Thus, Sn contributes about 3/3 of such terms over the entire trajectory, which can be viewed as an initialization cost. Next, we control St.
Lemma 9, Assume that a S 1 and 0₁ < (1 + a)aa)- It holds that S as defined in (31) satisfies
T
S 2 M
at || 11.
27

---

Proof. We can reparametrize t in terms of r =- K, which will help in reasoning with xx. Define
TK M [r/M]+ + K, and let
M T-K
r+k
S1 Σ
Σ
ar+K Σ
Kr
rK)
Σ
(9,,3 - 20-1,))
by definition and r = -
iB
STR+1
T-K
r+k
- M
Σ
Or+K
Σ
Σ
(9st - as 1,-1,;)
M [r/MJ) S M
iEBK
#rr+11
M T-K
M
Σ
(I+a)*Mr
K
Σ
(96,) 9s 9,0)
01 S (1 +1+ +a)ac-111
K=1 r=
BE s=rg+1
M T-K
r+
S eM
Σ
Σ
Σ
(gs, - 4 1,i2
K 3 M and a S M
iE
s
T-2
min T
r.
r+k
=MM]
Σ
Gr
Σ
Σ
Σ
(Ba - ao 1,)2
swap sums over r and K
R=1
Bx +
T-2
[in(T-r,M)
MTT
min(r+M,TT
<
eM
Σ
Σ
Σ
Σ
(96, - 99--1,)
Σ
Σ (+)
K=1
EB
#
8= MIMMI4
T-2
M,T(
(Tn(T-
eM
4+
Σ
Σ
Σ
(ga. - 1,)2
move sum over
M
H+
BE
min(r+M.T)
M
min M MrrMa
M
eMM
Σ
Σ
(go.s - 1.))
()) S Σ ())
8=M
Mr/MI +1 K =1 iE
K
K=1
T-2
M,7(
eM
a+
Σ
11 14--9--111 1 11
Σ Σ (1= Σ6 ())
M+/Mi
K=liEBx
T-2 min (,TT
<eM) Σ
Σ
(1+a)-
as 11g.- - 11-1
0. S (1 + +0)a-1
0=0
Lr/M]
T min/ (r
< < Σ
Σ
ag 11.. 10-1112
M and
1 M
M
< 2c 2
Σ
as 114. 9-- 12
The last line follows because the inner sum Em Mir/M] as 1lq, 94-1 1/ can be thought of as sliding window of size at most 2M centered at r, which essentially repeats each element in the sum 2M times at most.
In either case, the contribution over the entire trajectory is order M (n/b)² terms. Combining the bounds for So and S₁ yields the following.
Lemma 10. Letting M n//b be the number of blocks. Assume that a S 1 and or S (1 (1+00 (1+a)u--1- We have that
20-1,)) S 322 a 11 9:-1 1g-
a
28

---

Proof. Use Lem. 7 to achieve (31) and apply Lem. 8 and Lem. 9 on each term to get
Mt.s 9 eM - 1) M-1
T
11 ---1l12 + 2c M²
at 11
t=1
ae llq 9-11l2 I M²
completing the proof.
We close this subsection with comments on how Lem. 10 can be used. The term E, ||6 is multiplied in (36) by a factor nar_, Thus, we apply Lem. when redistributing over time pC
term |19-11 2-2212 which will be multiplied by a factor (ignoring absolute constants) of
nap-,
n maaa-1
M
HO1-1
6PHO--1
In order to cancel such a term, we require the use of be used up by (49), and be left with the condition
14 12
1
We can reserve half to
n G2
b² pv
S AL-1" = a²
bP
n
2nG
we have applied that a--1 20Cr-1 and at-1 aA.11. Thus, this introduces a dependence of nG order V pur a, which propagates to the learning rate We proceed to the main logic of the convergence analysis.
C.3 Proof of Main Result
C.3.1 Lower Bound on Dual Objective
We first quantify the gap between L(w., qt) and L(w,, q-) by providing lower bound in expecta- tion on L(w., 9t). given in Lem. 11. As in Lem. 5, recall the notation π (4, i) to satisfy Úr, = (x(1.s). and gt.s = Vl. (w))))) that is, the time index of the last update of table element i on or before time with π (t, i) = 0 for & 0.
Lemma 11. Assume that a S (/(2eLni)) Then, for 2 2, we have that:
EalaaL(w,, ((w.(()))))) 9c)
a1 Σ ne [[V[,(r,) - ve((u.)11
2T.
a111
1,1 [li(we-1) - ve(ww.)12 +
am(t-2.8) 2,6)
(m(1-2,0)
V4 v..
4L
4L
6
11t-1 -
P
arBi](VE(uuu)
T a: 9._ 1/ 1,-1, - -.w)))) at-1 (Ve(wr-1) 9c-1 -T-20--2 w. w.-l)
azll E, ||wa 12 + a.vE, DD [|0)l
HA
E, -|w. -eel2
2
pCt-1
||ue w 1C2-1
||u, -w----11 w1-1112
4
2
t-2
11-
Σ
Er l|w -rrooll
C- 1/1
Σ
||w. ww--waa wwrol
2
/=t
n/b
29

---

Proof. We use convexity and smoothness (1), then add and subtract (2) elements from the primal update, and finally use the definition of the proximal operator (3) with the optimality of w, for the problem that defines it.
ag (w. qt) == arge k(w.) + at 1 l|..li. 112 - a.u:(q:il90)
2
(1)
2 arq ((ws) + ac (V((w))) ge, w. - -wi) +
at Σ ges [[i(wr)) - Ve((w.)
2L
Oefl
|/.,, 11 (2
2
044, ((w))) + az VaxKVe (V((w:)) T 9: 1/ 14 -wi) at (up -/ wee
0rf4
||.,11 Dv
Ot Σ +
qi [2r(wr) - (er(w,))1
2
2L
i=1
1
||,, - Wh-1 112
100,
W 112
(32)
2
1-2
ct-1/1
|,,+ wivall 2
11-111
Σ
I| wivoll2
2
2
r=t-n/b
T=t-n/b
((wi) + at (V((w)) 9: of w. wi) top (up We wi)
4b40
cross
=0
011
|/ acuD(a:llo))
Σ te [[v(s()))) - (e,(1=)11 21
2
pCa-1
1C
|ml 11-1112
1| Wy w/- 11
(33)
2
2
1-2
2-2
Ct-1/M
Σ
|wo-
wrvol12
C-1
Σ
I|w. wrvoll
r=t-n/b
r=t-n/6
ww,, - wi11.
(34)
2
Next, we are able to use Lem, 4 with Us = of', 3e v((w:) 9e. d1 = -9. âc xe we. v. w.,, and 1/2-1/2 which yields that
E, | (V((w)) ge- of w. w:)l
S a. B. [< (V((w:) T a: 14-1 w. 10-1) -wi) a:-1 (V((W)-1)
qt-1 20-201 w+ wL-1)
+ n² ax-1"
uC E, l/we - we-2 112-
Ee Eien. Ve((01-199--1 - 96- 2,-
MC
4
R.1105112
(35)
Then, apply Lem. 5 to achieve
E2 1
3qmax
91-1, [[11( Ve,(w=))1
n
3
(, [l((W<((-22)) - Vl((w"))
n
im1
3G2
1/--1 22221
(36)
12
30

---

In the following, the blue terms indicate what changes from line to line. Combine the previous two steps to collect all terms for the lower bound. That is, apply (34) write
Ex (ww+(((w)))))) 9:)]
a.9.Te(un ((w.) at 14 1w.112 D(ulleel))))
2 aege ((wx) + (a (Ve(ws) TT a: - ui w. -w)-
wx)1 4f
[V)(w)) - ve(w+)l
2L ==1
+ atl
||00
1/2 -avD(aell0))
+ uAr
1| - -well2
2
2
pCt-1
1=
| w
100, Wi W1-1112
2
2
1-2
1-2
+
G-
1/
||w
wrvoll2
1-
I|w,
2
2
2
T=t-n/b
n/b
then apply (35) to the blue term above to write
Eg (e 9c)]
2 azqe ((ux))
Ot
qi [V(((w)) - ve((w)11
2L
1=1
n 1
Es Vein (w (w0-1)9t-1,--1 2,- 10- 2
(37)
MC
+o,lE,
(Ve(w)) T ai- -6 00-1 W. 11- -wb>| a,-1 (Ve(wr-1) 9--1 -6- w. wt-1)
0:ll
||wel12 a. + MAc
1|00, well 11
2
2
cC
PCp-1
|| w
||0,
Wt wt-1lls 1
4
2
t-2
111
||,,
wrvn
112
Ct-1H
Σ
I|,, wrvoll2
2
2
/=t-n/b
T-t-n/b
Finally, apply (36) to the term (37) to achieve
2 azqe [(wx)
ae
Σ
[V(( - (l.(w))
2T.
3
3k 2
Σ 1-111 [[((w)-1) -e((w)))
Σ
2 VV ve((w))) 1
MCI-1
PC
3nG
19-11 - 21-2112
1C,-1
+ (,E,[(VE(u;)) T - 0T_11 16-1 W1 - -w,) a.-1 (Ve(w,-1) 9c-1 2 w. - w.,.))
arf
||wel12 - a.u((gellen) + HAc
l!,,, - wrl12 2
2
2
WC
1C
|| - - w
|u. We wt-all 11
2
t-2
t-2
G--111
Σ
||,,- wrvoll
112 C-1141
Σ
I| - wrvol2
2
2
t/t
a//b
31

---

Next, we apply at-1 S -aC,-1 and a 1 24eLNe
to achieve:
3nG
GnG
pC111
3 0t-1
- 4L
pCp-1
3koa 1
(x((1226)
vi [n]
4L
For terms that contain (tt - 2,1), we recall that t(t - 2) can be at most n/b timesteps behind t 2, so we have that
1 n//b/
S
1
Ot-n/b S e0e-n/b S (0x((-22))-
We use here that a S (1 + a ) and impose the condition 4 S n back into the lower bound achieves the desired claim.
in the rate. Substituting this
D
C.3.2 Upper Bound on Gap Criterion
Next, quantify the gap between L(w,, q.) and C(w., q.) by upper bounding a LuW, q+), as given Lem. 12. When combined with the lower bound Lem. 11, we may then control the gap.
Lemma 12. Fort t 2 2, we have that:
arC(we, q+) S ard. T (f((u)) - -(p)+ + aclt || 112 + A. ivAp(un,
2
+ asqi ToP a.v a.vD(qilluu) AL- AvvAp(a.
Proof. We add and subtract (1) terms in the dual update step and apply the definition of the proximal operator (2) with Bregman divergence, and the optimality of qe for the maximization problem that defines it.
a C.C( g= az T T((wr) a. +
0zf4
2 ||wel22
a.q. ((((w))-o) + atf
|| |well A4.-vAD(lq...
2
+arh+ tie D D. (0)) A - (1..appgg.t1)))))
arg. T (l(w:) - 2.6) acf4
1 A
+ a:q dn a.v a.vD(gell40) A A 9- A,uAD
We can combine the upper bound from Lem. 12 and lower bound from Lem. 11 in Lem. 13. We identify telescoping terms blue and non-pos non-positive terms in red. The green term is canceled after aggregation across time t. This bound, like before applies fort 2 2.
32

---

Lemma 13. Assume that a S (22eLnii)). Fort > 2, we have that:
Be [76] = Br [a.(C(ur, 9-) - [(W+, (b)
0r/4
| -. Ux11
2 11 2m112
2
$ a, [(9.- - q)) (e(wi)) - - - -a-11q9-
- 1) (e(w)-1) - 2)
(38)
+ + 1 u p (Mn, 1t-1) - A ( 9t)]
(39)
n
at Et 2L
Σ qt. [[e(ux)) - ve((w=))13
(40)
+ 0t-1
qt-1, 1, [[;(w=11) ve((w)12 + Σ
2.()
1,8t-228), (2
vl((w,))
4L
4L
(41)
-, [ (Ve(wr)) T ar - 20- w,)] + + (Ve(wr-1) 90-1 90-11))))111110111111111111 -1 -2, w.
wt-1)
W
(42)
GnG-
l1ac-1 222211
(43)
1
uAg Eg ||,,
-wall
PC2-1
l|u, W/-
12
C1-1/1
Σ
1-2
|| wrval2
(44)
2
r=l-n/b
nan- 1a02
Σ
|
wrvol
12
Ct-111
Σ
EE | w
(45)
2
n//b
F=t-n/b n/b
+ Ra4 -202
w1-2112 1C
||
E, ||wl
1/- 11
(46)
2 Es ||:0e w. [12]
a.V
E, 11 q. 112
Ar-1V
Er [A (gt: 16-1))
(47)
2
2
Fort t- = 2, the above holds with the addition of the term
1 9111- - 11 + nc²
11100 w1 l1.
33

---

Proof. First, combine Lem. 11 and Lem. 12 to write:
E, [7o] = Es a (C((s, 9.) - L(w.,
aeft
|
w.112
w.
4.V
l19:
1
2
2
B2 (ax 9r) (e(((r)()))) [P]]
cross term
+ B
A
n1
-F,
at
Tes [[1(10+)) -
2L
+ 0t-1
qt
1, V[((w)-1) ve((w)12
(a(1-2
2
V vli(w)))
4L
4L
1=1
6nG2aat-1
|10(-1 - 2-221
1
-,
(Ve(ur) T q: -. 19-11, W. w,)l + a-- (Ve(wr=1) q--1 -9- w. w(-1)
Ee l|u,
well 2
pC
l|u, we-2 1/ C-11/1
Σ
1-2
110, - w.vull2
2
T=l-n/b
pCa-1
1
Ey 1lw1e- wi-1l12 -
9011)
4
1-2
B,
arl'
B1
|1:0--1 - w.
C1-1/4
E, llue wivall
2 E,,
|1 q.112]
2
T=t-n/b
Bound the cross term identified above. In the case that = 2, use Lem. 4 with 21 = up, y/ = E(we),
Dc+1 = le Zt = gr. T. = g.. and = VA,,1 = which yields that
Br [12- 92) (2)))(((())))) (f((w)) - -2))]
S R2 [1++ - -22) (20T((((()))) (f(w)) - -22]] an(a - (()T-((() - -11)
E2 l1 - 2ull [l]] + n² Es 1 EiEe (e)(1)) E 1
(48)
where the fourth term above can be bounded as
n
nb
-21))-11-) E nG2
Ez
- (()))
=E -
||u wwll
Using the definition of the update, we have that ||w: woll2 (1/22) Vi(wo)) g0ll In the case that t > 2, use Lem. 4 as above but instead with y = A which yields that
a.E, [(g. q)) (f(wr) uP)]
$ 1. [9g. - qt) ([(we) - -6]] - -0-1119- - 90-1) (e(we-1)- - Pc-1)
+ Ar E, l1q. 9--1 [12] + n²af-1
Er Eses (lg(w--1) - l 15)es 11
(49)
4
A,
E. 1.110p1113
We may then apply Lem. and a:-1 S aAr-2 to get that
n n²
E, || 1
naa na.-1aG"
Σ
L-2
||
-wvoll
(50)
A 20
T/t
We may use strong convexity to get the A
E, l1 --- 10m-111: 112]
term
cancel with
1
Ap(ge, 1)- and that Ar-2 & A to complete the proof.
2
34

---

C.3.3 Determining Constants
In this section, we provide derivations that determine the values of the constant c that allow for cancellation of errors. We slightly adjust the notation in this subsection, in that we assume that for some 77 > 0
S (1 + +na
and determine such that (28) is satisfied. We will see that 7) is simply a constant factor away from actually be
a, so the resulting condition assume here that n/b 2 2, which is taken as an assumption of Thm.
The latter is given formally in Lem. 14. We
In the statement of Lem. 13, the lines above (43) will telescope without additional conditions. For (44), we set Ct a./m for some parameter m. Note that this condition does not need to be checked when n/b < 1, as the additional sum term over will not be included in the update. Counting all the terms that will appear when matched on the index -- 1, we have the condition that
(tn/b-1
0t-1 A + C
Σ
a./m S.
8=++1
The first term result from the "good term"
4 1 w. from the bottom. The rightmost
term above results because a, ||w. - wy 2 will have T = t - when E (t+1, .t...tt tt+nt/ nt/bbb 1}. We will begin by requiring that require that a I (1 $)a,-1 for all and some 3 0, and then determine / below. The condition reads as
4n/b 4 +
(1 3)3
n/b-2
(1+ a-11
4m
m
which can be summed and represented
(An/b 4 + m)
3) (1+
3)m/b-1
2 (1 + B)2
4
8
Rearranging and taking a logarithm on both sides, this is the same
8(4n/b - 4 m)
+ i) 2 (n/b- 1) log(1 + 3).
In
(51)
4(1 33)2
Next, using the inequality have
2x 2+x
$ In(1 + x)) with x
8(4m/b-4-m) which holds for all æ 2 0, we 1(1+1}²
2 3(4m/bb--mm
In
B(4n/bb - 4 m)
+1) 2 2 8(4n/h m))
23 m)
(52)
4(1 B)²
8(1 8)2 + ((4n/b 4 + m)
4(1+3)²
We also apply the upper bound In(x 1) with write
(which also holds for any x: 2 0) to
(n/b 1) (1 + 3) S (n/b 1))3,
which means that (51) will be satisfied (using (52)) if
28n4 b 4 + m)
2 (n/b - 1)B
(53)
8(1 + 3)2 + ((n
m)
n/b - + m/4 > (1 B)²
(n/2) m/44)
(54)
n/b
35

---

In order to satisfy the inequality, substitute (n/b - 1)2 for some >> 0 to be determined and assume that 3 < n/b-I so that (n/b -1 S The LHS reads as
n/b 4/b-1+m/2 cB(n/b- 1).
n/b
The RHS can be upper-bounded as
(1 + + (3/2l//0 m/4 (1+
(8/2) (1 c 1)2)
S 11 B) B(n/b- 2
which makes the inequality satisfied when
4 2,3 12/b - +11
c2
set 16. We now have the flexibility control and the telescoping of (44) is achieved. For (45), set 3 = ā and pass the condition of B S 1/(n/b - 1) onto a, which maintains the rate (and is already satisfied when I J/2 and 2 2). Then, can achieve
a2
ud=-1
p
V
m
Aa(n/b - 1)2
by requiring that a may satisfy it if
/ 3
which achieves the telescoping of (45). Finally, to address (46), we
nagaGa 1dC1-1
4
which we can achieve by incorporating the condition at S 4a(n/b-1)CC, 1) into the update of because paraGa < μad by the previous condition
Having chosen we are prepared to produce learning rate parameter n to capture all conditions on a in one, given in Lem. 14.
y/
Lemma 14. For all 2 we have the following.
Setting c =a/[1GG(nn/b 1)2] implies that a, S 2aCr.
Using the update scheme
02 4na1, and a₂ (1 + 17) for t t>> 2,
when
1
1
n2
= min
4
32n'
24 n
we have that (28) holds.
Proof. Noting that 16a(n/b - 1)² we confirm that
C. 2 A,
1
A 16a(n/b 1)
01 2 A-1/2
0, 2 11-1/2
16a((n/b -1)
0, S A 16a((n/b- 1 -1
This condition is satisfied when o < 32(m/b-Tj so we incorporate a < that a; < 2aC,. This concludes the proof of the first bullet point.
b. into the rate, implying
32m
36

---

Next, we show that I (1+a/ / 4)a;-1 will imply that S ad which is the second part of (28). First, we define ag = aa, as an initialization (which also satisfies 02 S (1+a/4)a, when a - 4/3), and show inductively that if 0t-1 I AA,,2, then S (1 + //44aa111 = S - In the base case, A = 01, so the condition 02 001 satisfies 02 S a.1. Next, fixing t and assuming that 1) ac-1 I 0.A-2 and 2) that 0r S + a/4)),-1 we have that
aA,1 = a( + 2, 2 (a+ + 1) 2 Cr,
the desired result. Finally, consider the condition d, S 4a(n/b 1)²C,-1, the third part of (28). We wish to show that the following inequality holds:
1
a S 4a(n/b 11,0-111-111 4a(n/b 1)2
Ar-1 4a(n/b 0c-1
1
4a(n/b- 1)²
a:11 + A - Ac((1/b 11) (1e
which is implied by the inequality
1 4a(n/b - 1) 00-1
at 4a(n/b 112 ar-1 fe-1+(1/a00--1
-4nn/b-1) (a+1- 4(n/b-11 - ar-1.
When n/6 2 2, we have that (1 + a/4) s 4(n//b - 1)² (a (a+1- a(m/b-1))
so we require that
b S n/2. Thus, our final updates are given by
a2 4na, S (1 + 1) a and a; (1 + 1)) 0:-1 fort 2.
we Because each condition was satisfied when using a; (1 (1+a/4)at-1. we define x/4 to achieve the claimed result.
C.3.4 Bound Sum of Successive Gaps
Lem. 15 is an upper estimate for the expected sum of the gap function over T iterates. Recall that E, [-] the full expectation over (4), The green term is a quantity that remain as an initialization term, whereas the blue terms have be bounded from above. The terms directly below the blue terms account for all of the "negative x i)" terms are not yet used up by the telescoping in lines (39), (40), and (41), and there are in fact between and n copies of those terms in each iteration, even though we will use only 1.
Lemma 15 (Progress Bound). Assume that
{ b
b
wuv
S min
32n'
24cLxe
3602n V
nG²
37

---

For any T 2 1, we have that
T
nG
VV(un)" (((wo))ooll) goll2
Yt
rpa
Bo
ar
(0.- (r)) (2) (e(wr)) - En)
(55)
Bo
(V((ur)) qr -1- wx wr)
(56)
Σ (n T (T - 1,)) a (1, Bo V - Vl,(w,))
4L
(57)
6n
a
At-1"
Eo
0--1 11-11 2-
Eo (D(eellee-1)
(58)
2
4T
Eu
9r,,
(e((w,)
2L i=1
HAT Eo
[11+--rrli
(59)
2
T-2 2
par-1
Σ
Eo | wrvol
(60)
1)] 2116a(n1/6
== mm/b]
ArVEo
[D(++117))
(61)
aell E | - w=112 T
T
025Y
En 11
--112-
(62)
2
1=1
Proof. We proceed by first deriving an upper bound on 71, the gap function for L 1. Note that wy is non-random, as 0 implies that up = V((w)). Using that wi is the optimum for the proximal operator that defines it, the upper bound can be written as
a ((C( 9+) a19. T(e(w;) E1) + an w 112 aigi Té, a, 1l0) - AivAn(a...) 91),
where we use that é, é1. For the lower bound, use similar argument to Lem. 11 to achieve
a1 aif(w., 2 anqe ((w1) + (V((wi) a1 V((wo) T qu. w. - -w1> +
01/4
| 11
2
-a + di n. [V((w)) ve((w.)11
UAi
I| wi 11
2L
2
where we use that of ve(wo)) T qu- We combine them to get
(q, - q1) (f(w)) - 21) - a (V((wi) q1 - Vé(wo) go. w. - -w1)
71 S ai
01
a
41 [V](w:)- ve((w.)1
nA1 I|w. w1 AIvAD(q..
2L
014
||
w.112
a1v |/ 9. 1.112.
where the last terms are the result of the additional quadratic slack terms in 7I. All of the terms from the display above will be telescoped. Thus, we apply Lem. 13 and collect the unmatched terms from the 1 > 2 one-step bound (using that Ag 0). The term (57) can be viewed as counting the remainder of (40) after it has telescoped some but not all terms Ra!T Ra(T-1.12 Ey ( (( Ve, ||
across iterations.
4L
38

---

C.3.5 Completing the Proof
We use similar techniques before to bound the remaining terms from the 7 Tstep progress bound given Lem. 15. We may now prove the main result.
Theorem 2. For a constant a > O, define the sequence
Q1 1, 02 4a, and at (1 + a1- for
along with its partial sum A, = -E ar. Under Asm. 1, there is absolute constant C such that using the parameter
1 b
a = min
n2 Line
nG²
the iterates of Algorithm satisfy:
Σ
T
1.dd + ATH E1 IUT w.
AT
E1
ll4
qa112
nG²
|0g - W1 12
4
We can compute a point (wr, ar) achieving an expected gap no more than E with big-O complexity
(w) +
LiQ
n
nG2
In (
(n+ + bd)
(10)
p b b/
pv
E
Proof. We first apply Lem. 15, and proceed to bound the inner product terms (55) and (56). Apply Young's inequality with parameter -Ar-1/2 2 to get
ar ((.. -qr) (()T((((T)) êT)
VAT
Bo 119.
0rl12
+
Boll [oll[(wT)
- 1r
4
VAT
MAT-1
d²
Eo 119.
Eo lWT wrvoll 11 Σ
VAT
T=T-n/b
M MAT Bo l1..
araG²
21l12
Σ
Eo |uT wrvo 11
T-T-//b
The left-hand term will be canceled by (61) by applying strong concavity (leaving behind vIw Eo llq. qr 1r) and the right-hand term (because of the condition a S 4n3/aG will be
..AA
canceled by (60). Next, consider (56). By Young's inequality with parameter μAT-1/2, have
Er (V((WT)) T qr - TT -0 W. - -WT>I
a
Eo [((WT) T qr - -1-10r-111 pAr-1
Eo l|u. -
AAT
4
or Eu [((wr)
gr 9T- 1rr- MAT-1
Ey l|w. wr wr
4
where the second term will be canceled by (59). For the remaining term,
E. [((WT) qr - 0Q-
< En ([VE((T)) {(w,)) qr + V((w,) T (r-1) + (V((w.) - GT T/ 112
(yr
3Eo [[(V((TT) v((w.)) 9r + 3 V[(w..) T (ØT 1 3E, (Vee(..) -1) 1 T
< 30 Eo (VC [V( + B 11 - âr rr 2 30 Σ Eg ( [V:)) 9r -.
39

---

We may add the middle term above to (58), so that the remaining term to bound is
GnG
a a l1::11 2212
T+1
A
Eo (A q-1))
P
2
To show that this quantity is non-negative, use that du 0 and Lem. 10 (recalling that M n/b to see that
6nG2a ar Eo Eaelle -
18 b2p
T+1
18c 18
Eo
Σ
a 11
12-21122
Eo
Σ A l1q.
-2-112
b²
which will cancel with the rightmost term in (58) provided that a the previous displays into Lem. 15, we have that
I
b 36e
por nG2
Thus, plugging
G² mn
Eo
Vi(wo))Tol))
3arona a
Eg
9T [[
aT
Eo
QT, [[((T))
vei(w.)]l
2/x
2L
i=1
3 aT
En (x(T- / [[]()))) - V
2/1
1=1
n
n
( 1,,))
ax(T
Ey (x(T-1,1) Ve(W ve((w))12
4L
T
T
agfl
En |/we
w=11
Σ
Eo |1:: - 9-112
4
t=1
Aq 1/1 Eo ||TT- - 12.12 11
Eg 1r 9- 12-
The black lines will cancel given our conditions on a. Substituting the definition of 7t and moving the final non-positive terms on the last line, that is, [Ar-itar)y Eo I|w w. and (Ar-1 tarle
Eo lQT 1.112 to the left-hand side achieves the claim.
C.4 Modification for Unregularized Objectives
For completeness, we describe a modification of DRAGO for unregularized objectives, or (2) when J and > 0. The analysis follows similarly the previous subsections (regarding the μt, case), and we highlight the steps that differ in this subsection by presenting a slightly different upper bound on the gap criterion based the modified primal and dual updates. This will result a different update for the sequence (a:)221, subsequently affecting the rate.
C.4.1 Overview
The modified algorithm is nearly identical to Algorithm 1, except that the dual and primal updates can be written as
qe = arg max ai (vP.g) a,,rD(gllg)) (NAr11 v1)Ap(9.991)
(63)
and
Wt arg min de (V,,w) wEW
azHl 2
C- |
||w w-11112 C2-1/t 42
Σ
|| mavall?
2
s=t-n/b
(64)
respectively, and μt, 12, v1 2 0 are to-be-set hyperparameters. When v 0, we may set 1 0. and when μ > O, may set μl #2 0, which recover the Algorithm I updates exactly. While
40

---

we may set = 1 when it is positive (and similarly for Yr and p2), they may be set to different values order balance the terms appearing in the rate below. As in Appx. C.I, we wish to upper bound the expectation of the quantity
Tt ar (L(w), Q+) L( (t)) |/u w+ 11
V
2 1 9-1
(65)
2
which is still non-negative in the case of f = 0 or = O. By using an appropriate averaging
sequence (at)121 and defining Ar Ei= de. upper bound Σ a,Eolyu] (see Thm. 2) by a constant value independent of T. Recall that the batch size is denoted by b. As we derive in Appx. C.4.3, our final update the (at) sequence is
min CC-IMt + 12enqmaxe L'
(1+ b) n2 at-1: 32n
b ()) min (Ct-1 M1,0-111 #2)
a. min
VTG
Observe that when j = O, we set dg 12enqmax L achieve O(1/t) rate. We omit proofs in this subsection they follow with the exact same steps as the corresponding lemmas in the strongly convex-strongly concave setting (which we point to for each result).
C.4.2 Upper Bound on Gap Criterion
Following the steps of Appx. C.3.1 and Appx. C.3.2, we will first derive lower and upper bounds on E,for[(w,, 9:)l )] and a aw q+) and combine them to upper bound a [ne]]. Recalling that Eg [-] denotes the condition expectation given (w,-1, (t-1). and we can then take the marginal expectation
to upper bound az [n.]. The following lower bound is analogous to Lem. and follows the exact same proof technique.
Lemma 16. Fort t 2 2, assuming that S
Ct-IttH and S (1 + b/n)a, we have that: 12engmace
- -E,lar[(u,,g))
-e [(w+)] 2L
qt E. [[v.) - ve((w))1
arl 1|
at-1
Σ
91-1,i [ei(wi-1) - ve((w))11
Σ
(n())2.6)
2n(t-2,0)
(2:(W(((22)) (e,(w,)))
4L
4L
1=1
2=1
3nG2af_1
||0:-1 - 2122
C2-1/++ 1h
a.E,[ (VE(w:) 9:-
0 W - wi)) at-1 (V((w,-)) 90-1 -0T-29-22 w+ -0,
Arpl MM + 12 F2 ||w- -wwl-w:l..
B. (D(c:1(2)))))
2
C2-1/1+ + 11
| 1 C1-1/t+ 11 I|w, Wi- 12
4
2
2-2
G- 1/1 + 112
E2 - wivollz
Ct- 111 112
lwo,
wrvol 2
r=t-n/b
r=t-n/b
Similarly, following the same steps as Lem. 12, one can derive the following upper bound.
Lemma 17. For 2 2, we have that:
a, L(w, q.) S 0.g. T ((l(w)) - uP) (Ac- 12 11)
+ a,qi ToP a, qu) (Ai-1V + 1n) - (A₁r + A))
By combining Lem. 17 and Lem. 16, we can upper bound the quantity E, [a (L(W,, q.) [(w,, 9:)] Consequently, the following result follows the same steps as Lem. 13. As before, we identify telescoping terms in blue, non-positive terms in red, where green term is bounded after aggregation across time l.
41

---

Lemma 18. Assume that ac-1 S
C. Ch-ttt and S (1+ 12eLnqmox
Fort > 2, we have that:
E, Ivel = Er (F((W 9.) - [( 9:)
acfl
||0, w. =
a.
11 9u113
2
2
S Saylee (40. - 9r) (e(uur())) - Ed)l - a1-11g. -q--1
(e(ut-1) 1--1)
(66)
+ + u) (s+, 91-1) - (Ape 1n E (D(().
(67)
E,
At (w:) - ve((w>)l1
(68)
2L
+ 0t-1
Σ
1--1, [[; ve;(w)112 + Σ
4L ga(e- V - vl,(w,))
4L
i=1
(69)
-0 [ (Ve(wr) -6-1-- 10-, we)] + #a-1 (V 9--1 T
2, w, wt-1)
(70)
3nG ||ge-1 2c-2
(71)
Ct-111 + 11
Aqp - 11 + H2(n1/b b- 1)
M1
Ct + M2
t-2
Ex lle, well
|0., w--1l1
I|w,
wrvol 1
2
T=t-n/b
(72)
na G2
|2--1 wrvoll
Ct-1/1 + P2
Σ
1-2
E, 1|we wrvoll2
(73)
Ar-2V + V1
2
1=1-n/6
n/b
na nap-, G²
C1-1M + 11
||1,-1 w
EY ||1,
1.-11 112
(74)
A-22V + 1/1
|w1 w. 12
a+V E,
1190
2.11 A + 1s
E, [dD (010)99911).
(75)
2
2
2
For t- = 2, the above holds with the addition of the term including A in the denominator.
nG it4n
1|wl wollz and without any term
We then select constants to achieve the desired telescoping in each line of Lem. 18.
C.4.3 Determining Constants
We now select the constants (M1, (12, 11), and the sequences (at) and (ct) to complete the main part of the analysis.
In the statement of Lem. 18, the lines above (71) will telescope without additional conditions. For (72), we set e = a./m for some parameter m (just as in Appx. C.3.3). Note that this con- dition does not need to be checked when n/b < 1, as the additional sum term over 7 will not be included in the update. Counting all the terms that will appear when matched on the index t 1, have the condition that
b-n/b-1
0:~1
A + C
Σ s=++1
a./m
+-(p1 (p1 + (nnnbb - 1)) + #n + (n/b 1)p2 $ 0,
4
where the first underbrace is non non-positive based on the choice of m selected in Appx. C, and the equality is satisfied for all values of µn and μ2z Lines (73) and (74) yield the conditions
Ga
C1-144 + #1 and A, V1
Go?G²
C1-14 + p2
<
(76)
1 V1
4
2
42

---

for the telescoping to be achieved, which can equivalently be rewritten as
a S A (i)(Cr mi) and a S (A-- v (c) 1/4 + u22
(77)
4nG²
2nG²
These can be accomplished by setting
(V + v1) min (C1-11 + 11141114 + U2)
a1 S
2/rG
We must also handle the term Ch-1pt instead of we have that when summing over I, we have that
3nGPa
1 4- 122. By the argument of Lem. 10 using of
an
3nG²
11
1-
3e M
ai 11 2 1-
Ht
C1-1Ht + 1ı
M22
Σ of 11:: 9--1
1 C2-1H+ + P1
where M = n//b b is the number of blocks, and the e term appears from the squared constants (as opposed to e²)) Using that we will sum the non-positive terms Ei= AL-1vB,(AD(9 1111 so that the final condition needed cancel this term
M12nG²M² a <
A 11
C1-1H+ 11
which can also be rewritten as
(Ai-1V 11 u1)
04
32M
nG
Thus, combining the previous conditions, our final update on the (a,) sequence is
a, min ( CC-IM+ + 1
b mm) b +1)
min min [C1-1H + n1, 11 42)
12enqmax L'
n2
ac-1 32n
VTG
as alluded to in Appx. C.4.1.
43

---

D Implementation Details
In this section, we provide additional background on implementing DRAGO in practice. This in- volves description of the algorithm amenable for direct translation into code and procedures for computing the dual proximal mapping for common uncertainty sets and penalties. We assume in this section that W R and provide multiple options for the uncertainty set Q
D.I Algorithm Description
The full algorithm is given in Algorithm We first describe the notation. Recall that M = n/b, or the number of blocks. We partition [n)] into (Bı,..., BM), where each Bx denotes b-length list of contiguous indices. For any matrix E Ruxm (including m 1), we denote by a[Bx]= Rx the rows of u corresponding to the indices in Вк- Finally, for a vector & E R we denote by sC the vector that contains Sę in indices & Bx, and has zeros elsewhere. Next, comment particular aspects regarding the implementation version as compared to Algorithm (Sec. 2).
We store two versions of each table, specifically i R", 01 E Raxd and @1 92 IR For any iterate these variables are meant store &,, l--1 E R" -t- 1,9-2 Ruxd and ft E IR..
The quantities Oags Fdd and iage Rd are introduced to not recompute the sums in the primal update on each iteration (which would cost ((nd) operations). Instead, these aggregates updated using (bde) operations.
The loss and gradient tables are not updated immediately after the primal update. However, the values that fill the tables are computed, and the update occurs at the end of the loop. This is because [[xx. is used to fill é [Bx,] at the end of the loop, knowledge of [., temporarily.
must maintain
While the proximal operator is specified for the primal in the case of W = Rd, the proximal operator for the dual os computed by a subroutine DualProx, which we describe the next subsection.
D.2 Solving the Maximization Problem
As discussed in Appx. B, the primary examples of DRO uncertainty sets Q are balls in f-divergence (specifically, KI. and x²) and spectral risk measure sets. For the penalty D, it is also common to use f-divergences. We review these concepts in this section and provide recipes for computing the maximization problem.
f-Divergences We first recall the definition f-divergences used throughout this section.
Definition 19. Let [0, oo) + R ( { be a convex function such that f(1) 0, f(x) is finite for atoms. The f-divergence from to q generated by this function f is given by
and lim (xx)
Let q and q be two probability mass functions defined
Dy(gl
q
qo.
where we define 0f (0/0) := 0. For any such that q. but 9: > 0, we define Dy(gllg) =: +00.
The two running examples we use are the x² divergeene generated by fx²(z) = x² - 1 and the KL divergence generated by (z) In oo) and define 0 0 0. For any convex set X' C k we also introduce the convex indicator function
if E X otherwise
(x(x)
In either of the two cases below, we select the penalty D(gll1/n) = Dy(all1/n) to be an f- divergence. Denote in addition f the Fenchel conjugate of
44

---

Algorithm 2 DRAGO:
Implementation Version
Input: Learning rate parameter a 0, batch size b be {I....,n) n., number of iterations T.
Initialization:
Oa and q 1/n
- f(w). l + f(w), 91 t- V((w), 92 + V((w), @1 + q and d2 + q
o + for K E (1,..., .......M)...... M) for M = nn/b
Juge - 91 91 and uugg - -K=1
K=1 WK
M
3 = 1/ + an/bn/b- 1)2] if n/b > and 0 otherwise
fort t 1 to T do
Sample blocks 4, and Jr uniformly on [n/b] and compute K; = mod (n/b) +
8 + (1 (1 + a))++) aaa= + a))
Primal Update:
- [Vi(W)]iBB, E bxd and eº + Iagz + I4= 8P.
[1+6.] ((B. B(M 1)) - + (wngg (ix,) v. ///1)) dagg + -agg + w 0x, and 0k, < w
Compute Loss and Gradient Table Updates:
(1,, g.) + 16x (w), (lx(W)) R² x Bbxd
Dual Update:
8D + M(1 (1) and DD - (1 (1- (K..eeB. + 1 d eeB..
Ita + DualProx(q, 6P, BB)) arg m (v) vD(allln/n) BvADp(g.9)
Update All Tables:
92 [Bx,] < 01[Bx.] and [x.] t 91
[B.]] + [[Bx.] and [BR. t
22 [K.] + 9 [x.] and 9 [Bx]] + g(Bkr]
OagE 4 Iugg + タ1 [Bx,] ( [Bx,] go bx| d2 Bx,]
end for
return (w, q).
D.2.1 Spectral Risk Measure Uncertainty Sets
As in Appx. B, the spectral risk measure uncertainty set is defined by set of non-decreasing, non- negative weights a = (o1,..., ,x) that sum to one. Our uncertainty set given by
== Q(o) == conv (fpermutations of a))),
and we Dy has the penalty for either fxa or fKL. The set Q(o) is referred to the permutahedron on σ. In this case, the maximization problem can be dualized and solved via the following result.
Proposition 20. |Mehta et al., 2024, Proposition 3] Let l E R² be a vector and a be permutation that sorts its entries in non-decreasing order, i.e., (m(1) S... S latn)- Consider a function I stricily convex with strictly convex conjugate defining divergence Dj. Then, the maximization over the permutahedron subject to the shift penalty can be expressed as
-- (511-DD(g((1.//)) (EQ(A)
min
Σ (((;(),
(78)
SER"
21 2IS...
where we define (2 1) == 0,2 0,2+% vn fr ((1)1)) 2)/v) The optima of both problems, denoted
" arg min Σ (z;1), gopt arg max q Ti- vDD((l)1../)) 2ER" #1
opt (1)
(EQ(O)
45

---

are related as (1) =
zopt (1)), that is,
opt (1) -1= 15T (2 - (0)) q
opt
(79)
As described in Mehta et al. [2024, Appendix C), the minimization problem (78) is an exact instance of isotonic regression and can be solved efficiently with the pool adjacent violators (PAV) algorithm.
D.2.2 Divergence-Ban Ball Uncertainty Sets
Another common uncertainty set format is ball in in f-divergence, or
= 2=
{a TR"::"
Dy(alla/n) 0, and 1 ==1
We describe the case of the rescaled x²-divergence in particular. in which the feasible set is an Ez-ball intersected with the probability simplex. Given a vector RR, we aim to compute the mapping
T arg max qEP,
(1,4) 14 1/nlB3p
2 114 1/ml12:
(80)
where Pn, P= : 2 4= =-= }} denotes the n-dimensional probability simplex. We apply similar approach Namkoong and Duchi [2017], in which take partial dual of the problem above. Indeed, note first that for any q Pn.. have that & llg 1,/n1 l1 2n the optimal solution to (80) can be computed by solving
Thus,
/' |al12 - >
16 111122 2n
max min (1. q) Q.P, A20
or equivalently, by strong duality via Slater's condition, solving
1 q 2 119 - 1/(v 2)12 > > (0+
1
(())= = (v A) min max X
|1
2n 2(v + A)
Notice that evaluation of the outer objective itself requires Fuclidean projection onto the probability simplex as a subroutine, after which the maximization problem can be computed via the bisection method, as it is univariate concave maximization problem over convex set. In order determine which half' to remove in the bisection search, we also compute the derivative of À + f(A), which is given by
1
(((A) : (P) P
2n'
where gopt()) (X) achieves the minimum in minger, 2 1////(u + 2)l for a fixed À 2 0. For pro- jection onto the probability simplex, we apply Algorithm from Condat [2016], which is solution relying on sorting the projected vector. The overall method consists of three steps.
1. Sorting:
Projection onto the simplex relies on sorting the vector 1/(v + X) each eval- uation. However, because 1/(u + A) varies from evaluation to evaluation simply by mul- tiplying by a positive scalar, may pre-sort and use the same sorted indices on each evaluation of ( listed below.
2. Two-Pointer Search: We find the upper and lower limits for X by initializing Amiu
and Amax = 1, and repeatedly making the replacement (Amin Amax &- (Amax 2xmaxx until ['(maxx) ) < - for some tolerance > 0. This, along with f' (Amin > indicates that the optimal value of À lies within (Amin Amax ). For any À with [f(()) the associated (X) as the solution.
< E, we return
3. Binary Search: Finally, we repeatedly evaluate ('(A) for A = (Amin + Amax )/2. If ('(2) > E, we set Amin + X, whereas if f'(A) -8, then we set Amax + X. We terminate when Xmax -Amin < [f()) <.
46

---

The parameter E is set to 10 10 in our experiments. Note that the same procedure can be used to com- pute the dual proximal operator in Algorithm 1. In particular, when AD((, 9), 9-11) = ll qu l which is true when D is the x²-divergence, then
(1 (3+4, 2) v(1 + Bc)
2 11q 1/mll22
arg max qEP, lll 1/
which is particular of (80), and hence he solved using the exact procedure. The runtime of this subroutine is On log + n (o)() accounting for both the initial sorting at O(n log n)) cost, and the (log((1/e) iterations of the exponential and binary searches. Each itera- tion requires a linear scan of n elements at cost O(n).
Hardware Acceleration Finally, note that the computations Appx. D.2 and Appx. D.2.2 involve primitives such sorting, linear scanning through vectors, and binary search. Due their serial nature (as opposed to algorithms that rely on highly parallelizable operations such as matrix multi- plication), also utilize just-in-time compilation on the CPU via the Numba package for increased efficiency.
47

---

Dataset
d
Task
Source
yacht
6
244
Regression
UCI
energy
614
Regression
UCI
concrete
8
824
Regression
UCI
kin8nm
6,553
Regression
OpenML
power
4
7,654
Regression
UCI
acsincome
202
4,000
Regression
Fairlearn
emotion
270
8,000
Multiclass Classification
Hugging Face
Table 5: Dataset attributes such sample size n, parameter dimension d, and sources.
E
Experimental Details
We describe details of the experimental setup, including datasets, compute environment, and hyper- paramater tuning. We largely maintain the benchmarks of Mehta et al. [2023].
E.1 Datasets
The sample sizes, dimensions, and source of the datasets are summarized in Tab. 5. The tasks associated with each dataset are listed below.
(a) yacht: predicting the residuary resistance of a sailing yacht based on its physical attributes Tsanas and Xifara [2012].
(b) energy: predicting the cooling load of a building based on its physical attributes Baressi Segota et al. [2020].
(c) concrete: predicting the compressive strength of concrete type based its physical and chem- ical attributes Yeh [2006].
(d) kin8nu:
predicting the distance of an 8 link all-revolute robot arm spatial endpoint [Aku- juobi and Zhang, 2017].
(e) power: predicting net hourly electrical energy output of power plant given environmental
factors [Tüufecii, 2014).
acsincome: predicting income of US adults given features compiled from the American Com- munity Survey (ACS) Public Use Microdata Sample (PUMS) [Ding et al., 2021].
(g) emotion: predicting the sentiment of sentence in the form of six emotions. Each input segment of text and we use a BERT neural network Devlin et al. [2019] as an initial feature map. This representation is fine-tuned using epochs on a random half (8,000 examples) of the original emotion dataset, and then applied to the remaining half. We then apply principle components analysis (PCA) reduce the dimension each vector 45.
E.2 Hyperparameter Selection
We fix a minibatch size of 64 SGD and an epoch length of = n for LSVRG. In practice, the regularization parameter μ and shift cost are tuned by statistical metrie, i.e. generalization error as measured on a validation set.
For the tuned hyperparameters, we use the following method. Let & E {1...., K} be seed that determines algorithmic randomness. This corresponds to sampling a minibatch without replacement for SGD and SRDA and single sampled index for LSVRG. Letting Lx (1) denote the average value of the training loss of the last ten passes using learning rate and seed kt the quantity L(n) =
1 <KKK (n) was minimized to select 7). The learning rate 77 is chosen in the set (1 x 10-4,3 x K ===1
10 10-4,1x10 3 10-3 1 x 10-2 2 3x 10-2, x 10-1,3 x 10-1, 1 x 10 3x 10"]. with two orders of magnitude lower numbers used in acs ncome due to sparsity. We discard any learning rates that cause the optimizer to diverge for any seed.
48

---

yacht
EnErAy
concrete
yacht
Entrgy
concrete
Saborimmaitty
10:
1072
1077
1013
10r1
2000 kinSnm
(0000
10000
poweer
emotion
kinSnm
powtr
emotion
M
urd
10
Fist-Ordrr
Dock Time
Wal-Dock
Wid
SGD
Drago (b= 16)
Drago (6 x//d)
Drago (b
Figure 4: Benchmarks on the x² Uncertainty Set. In both panels, the y-axis measure the primal suboptimality gap, defined in (15). Individual plots correspond particular datasets. Left: The x-axis displays the number of individual first-order oracle queries to {(4, V4,) Right: The
rraxxi displays wall-clock time.
E.3 Compute Environment
CPU workstation with Intel i9 processor, clock speed of 2.80GHz, 32 virtual cores, and 126G of memory. The code used in this project was written in Python 3 using the Numba packages for just-in-time compilation. Run-time experiments parallelism. The algorithms are primarily written in PyTorci and support automatic differentiation.
Experiments
conducted without CPU
E.4 Additional Experiments
We explore the sensitivity of the results to alterations of the objective and algorithm hyperparame- ters.
Sensitivity to Uncertainty Set Choice In Sec. 4, we mainly show performance on spectral risk- based uncertainty sets, in particular the conditional value-at-risk (CVaR). In this section, we also consider f-divergence ball-based uncertainty sets, with the procedure described in Appx. D.2.2. radius that is inversely proportional to the sample
As in Namkoong and Duchi [2017], size, namely p = 1. and the strong convexity-strong concavity parameter μ = V = 1. Fig. 4, demonstrate the performance of DRAGO with 6 1. b 16 (as chosen heuristically), and b = nt/d. We compare against the biased stochastic gradient descent, which can defined using oracle compute the optimal dual variables given vector of losses; however, note that LSVRG is designed only for spectral risk measures, so the method does not apply in the divergence ball setting. We observe that the optimization performance across both regression and multi-class classification tasks are qualitatively similar to that seen in Fig. 2 nad Fig. 3. The b = 1 variant performs well on smaller datasets (n S 1, 0000, whereas the 16 heuristic generally does not dominate in terms of gradient evaluations or wall time. While the number of gradient evaluations is significantly larger the n/d /d variant, implementation techniques such as just-in-tima complication (see Appx. D) allow for efficient computation, resulting in better overall optimization performance as a function of wall time.
n
Sensitivity to Batch Size In Fig. 5, we consider the datasets with the largest ratio of n d (hence the largest theoretically prescribed batch size) and assess the performance of DRAGO with smaller batch sizes. For both datasets, have that in magnitude, n/d 1000. Intuitively, the smaller batch size methods would perform better in terms of oracle queries but the large batch methods would be more performant terms of wall time. With only batch size generally matches the best-perten best-performing setting when viewed from either oracle calls or direct wall time. This is approximately 16x smaller than the n benchmark, indicating that tuning the batch size can significantly reduce the memory overhead of the algorithm while increasing speed.
64, this variant of DRAGO
49

---

p 10-10,
j 10.00000
11 11000, 10.0
10.00
2271
3374
33
103
340
58
100
194
380
110
123
200
380
100
33-1
32
Ocade Evaluations (K)
FinttOrider Exalusiion (K)
Onacle Exaluations (K)
FinstDrdar Evaluation
11 11.10. x10
11000,0
1t 110, 1000
10.0, v 10.00
13.
po06
12-
13"
6
31
31
13
Wall-Clock Time (Secordh)
WalkClock Time (Secards)
Wel-Clock Tims (Sucands)
Wal-Click Tim (Smxunds)
Drago (b
Drago (6
Drago (b-
Drago (6 16)
Drogo (b
Drago (6-
Figure 5: DRAGO on varying batch sizes and strong convexity parameters. Each row indicates dataset, where as each column denotes the CVaR objective with the given regularization parameters. Top Rows: The r-axis displays the number of individual first-order oracle queries {(e, v4,) Bottom Rows: The z-axis displays wall-clock time.
50

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sec. 3 for direct theoretical claims and Appx. B for detailed comparisons to other work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Sec. 1 and Sec. 5 for general points, whereas Sec. 4 mentions specific
cases of algorithm performance. The assumptions made are otherwise standard.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
51

---

Answer:
[Yes]
Justification:
This is done for every theoretical statement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appx. contains detailed descriptions experimental details and code with associated environment and quickstart guide is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
52

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is made public at https//ggiiubb.ccom//ooonndnnnne
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: /nips.ccl
public/ gwwgguudds//eo Soaedeee/oooeuuune www.iisssiooooooo olicy) for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g,, for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / inpps- cc/publi c/ gu des / /CodeSubd as onPol cy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See Appx. D and Appx. E for implementation and experiment details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Training curves and hyperparameter selection experiments averaged over multiple seeds, but error bars are not shown to make the plots visible.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
53

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Yes, as written in Appx.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /neurips..p..e/ wwwpppbllcc//thccoououoeeee
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
is written after the main text of the paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
54

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification:
Generative and related large-scale models are not used in this work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pac re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
55

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
Documented code is provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: Human participants are not used.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No IRM approvals were needed for this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
56


Reviews:
[{"review_id": "BQhhiLIVRO", "reviewer": "Reviewer_P67z", "summary": "The paper studies stochastic variance-reduced algorithms for regularized distribution robust optimization problems, formulated as a minimax problem. The paper proposed a novel primal-dual algorithm, and analyzed its iteration complexity. Under Lipschitz and smoothness assumptions, the algorithm achieves a linear convergence rate, with $O(n + d)$ per-iteration complexity, and total oracle calls of order $n + n q_{\\max} L/\\mu + n^{3/2} \\sqrt{G^2 / (\\mu \\nu)}$.", "questions": "- In order to minimize the total computational cost (assuming that the individual gradients can be computed in $O (d)$ time), what is the optimal choice of the minibatch size?\n- On a related note, if we choose the parameters optimally, how does the total computational cost compare to other algorithms. In particular, as the per-iteration cost depends on $n$ as well, it is important to compare with the full-batch gradient-based algorithms.", "limitations": "The paper addressed limitations adequetly.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Distribution-robust estimation is an important question, and the minimax ERM formulation leads to a challenging optimization problem. This paper made solid progress in this direction. The algorithm idea is natural, and the result improves over several exisitng works along this line of research. Importantly, the result imposes no additional structural assumptions on the uncertainty set $\\mathcal{Q}$, except for convexity and an upper bound on the $\\ell^\\infty$ norm bounds for its elements.", "weaknesses": "When seeing $G$, $\\mu$ and $\\nu$ as constants, the oracle complexity scales as $n^{3/2}$ in terms of $n$. Although we get logarithmic dependence on $\\varepsilon$ and the result is already state-of-the-art, if we only track the dependence on $n$, it's worse than the vanilla subgradient methods, as listed in Table 1.\n\nAdditionally, the analysis relies on the Lipschitz smooth convex + strongly convex regularization structure. Is it possible to extend the analysis to non-strongly convex settings, or the case with convex individual functions but strongly convex summation?\n\nAnother weakness is the space complexity. Storing the gradient estimates $\\widehat{g}$ requires $O(n d)$ space. In many cases, this costs the same complexity as storing all the training data. So the advantage of stochastic algorithm is not very clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough comments. We address them below.\n\n> **Is it possible to extend the analysis to non-strongly convex settings, or the case with convex individual functions but strongly convex summation?**\n\nThank you for raising this important point. We discuss in Appendix C.4 modifications to the analysis which would handle if either or both of the strongly convex (strongly concave) parts of the objective were changed to convex (concave). In summary, we would not achieve linear convergence of course, but $O(1/t^2)$ if either $\\mu = 0$ or $\\nu = 0$ or $O(1/t)$ if $\\mu = \\nu = 0$. Because achieving an unconditional linear convergence rate that improves upon gradient descent was the main motivation of the work, we focused on the strongly convex-strongly concave setting. In the final version, we will provide a unified analysis for all settings.\n\nThe “strongly convex summation” could be handled with a similar overall structure, but different inequalities to produce the upper and lower bounds on the primal-dual objective function. For the lower bound, rather than applying the smoothness of $\\ell_i$ and then the definition of the proximal operator, we may apply an interpolation inequality that combines smoothness and strong convexity. One challenge is that we require $\\ell_i$ to be Lipschitz continuous, so we would need to assume a compact domain for it to also be strongly convex. \n\n>**...if we only track the dependence on $n$, it's worse than the vanilla subgradient methods.**\n\nThe vanilla subgradient method has an $n^2$ dependence due to the second term, whereas our method achieves an $n^{3/2}$ dependence. \n\n>**In many cases, this costs the same complexity as storing all the training data.**\n\nThank you for identifying this point. We have updated the manuscript to include a discussion on space complexity, which in many cases can be reduced far below $O(nd)$ for two reasons. Firstly, this is a known limitation for SAG/SAGA-type variance reduction methods for empirical risk minimization. That being said, the additional storage cost (beyond the training data) is $O(n)$ in many common cases. This is because convex losses in machine learning can typically be expressed as $\\ell_i(w) = h(y_i, x_i^\\top w)$ for some differentiable error function $h$ and so the gradient is given by the scalar multiplication $h’(y_i, x_i^\\top w) \\cdot x_i$, where $h’$ is the derivative with respect to the second argument. Thus, only these scalar derivatives need to be stored.\n\nSecondly, a more subtle advantage of our method is that we use cyclic updates instead of randomized updates for the table of past gradients (as opposed to the randomized updates in SAGA). Conceptually, this means that for very large-scale workloads, a fraction of the gradient table can be paged out of memory until its values are updated again.  \n\n>**In order to minimize the total computational cost... what is the optimal choice of the minibatch size?**\n\nThe optimal batch size is $b = n/d$, which is used in the red lines in the experiments. As mentioned in the “Global Complexity” paragraph on page 7, because the dual variables must normalize to 1, we have an $O(n)$ computational cost per iteration regardless. Thus, under the assumption that $n \\geq d$, we can compute $n/d$ gradients at $O(d)$ cost without changing the per-iteration complexity. This allows for the $n^{3/2}$ dependence in the sample size in Table 1, as opposed to $n^2$ for gradient descent.\n\n>**If we choose the parameters optimally, how does the total computational cost compare to other algorithms? In particular, as the per-iteration cost depends on $n$ as well, it is important to compare with the full-batch gradient-based algorithms.**\n\nThank you for the suggestion; we have added a table for this quantity as well for clarity (see the supplemental PDF Table 6). Among the linearly convergent methods of the manuscript, this can be measured by multiplying the complexity of gradient descent, LSVRG, and Drago by $d$ and multiplying the complexity of LSVRG/Prospect by $n+d$. Thus, under $b = n/d$, Drago achieves the best complexity without conditions on $\\nu$. A comparison to general-purpose primal-dual min-max algorithms is also given in Table 4 of the manuscript, with runtime.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VXveLcwaKG", "reviewer": "Reviewer_em1q", "summary": "The paper considers the DRO problem with a dual penalization term and primal regularization term. Their core contribution is a new primal-dual algorithm for this problem:\n- It achieves a new best first-order oracle complexity in certain parameter regimes. In particular, it beats previous algorithms when the dual penalization parameter $\\nu$ is small.\n- It achieves fine-grained dependence on the primal and dual condition numbers (i.e., not having a max over min term).\n- The uncertainty set $\\mathcal{Q}$ can be any closed and convex subset of the simplex. This is in contrast to previous works which specialize to more structured uncertainty sets.\n- The algorithm adapts ideas in a novel way - in particular, they show that coordinate-style updates can be applied even though the dual feasible set is non-separable. This might lead to applications in other minimax problems. It also only has a single hyperparameter $\\eta$ to tune, and comes with a batch-size parameter $b$ which can be used to trade-off between iteration count and per-iteration complexity.\n- Strong experimental results are shown (albeit, I should say that while they look very encouraging, I don't have the empirical background necessary to evaluate the methods used/experimental setup carefully).", "questions": "1. Just to make sure I understand correctly, it is always best to choose $b = 1$ to get the best first-order oracle complexity, but your runtime may be better with a different choice of $b$?\n2. I'm confused by the $n q_{max} \\le n$ in Line 491. Isn't this always true? Similarly, Line 81 says that $n q_{max}$ is upper bounded by \"a constant in $n$,\" but isn't it just bounded by $n$ because $q_{max} \\le 1$? I thought $\\mathcal{Q}$ still needed to be a subset of the simplex per the text under Table 1. If not, I would fix that text and also include exactly what $\\mathcal{Q}$ is in Assumption 1.\n3. Regarding the case where $\\mu = 0$ or $\\nu = 0$, in Appendix C.4 you modify the entire algorithm/analysis to handle this case. It is good to know this works, but a classic trick to recover a non-strongly convex rate from the strongly-convex case is to just set something like, e.g., $\\mu = \\epsilon / D^2$ where $D$ is a bound on the diameter of $\\mathcal{W}$. Would this recover the same rate, and/or is there a reason you don't do this? Just curious.\n4. Just to make sure I understand correctly, is this the first work you are aware of which applies these cyclic coordinate-style updates to a non-separable dual feasible set, or is there any precedent for this?\n5. I'm a bit confused by Lines 199 to 204 and how they connect to Appendix B.3 and in particular the bound after Line 556. It is also claimed in Line 202 that $n q_{max}$ is constant - why is this? (Even after clarifying this to me, I would recommend connecting it more closely to Appendix B, i.e., cite the exact equation in Appendix B you are referencing as opposed to all of Appendix B.)", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think this is a strong contribution to the DRO literature. The algorithm combines several ideas (variance reduction, minibatching, and cyclic coordinate-style updates) in a careful way. Of these, the application of cyclic coordinate-style updates to this setting (with a non-separable dual feasible set) seems the most novel and interesting to me. It is also very nice that it handles general uncertainty sets unlike previous work. The presentation is generally solid, although I think it could be improved in a few ways (see below).", "weaknesses": "Regarding presentation:\n1. I like Table 1 a lot, but I wish the comparison between your first-order complexity bound and previous complexity bounds was a bit more \"in your face\" and expansive. Currently, the comparisons are kind of spread out throughout the paper, requiring the reader to do more work than I think they should have to to understand where your method improves. For example, I like the discussion of Lines 471-479, but I think this should be in the main body. Also, I would compare your method directly to the sub-gradient method in the same place and carefully state what regimes you are winning in. \n2. I would formally put your first-order oracle complexity (and probably runtime too) into a theorem which also collects all of your assumptions together (or mentions Assumption 1). Currently, this is just in the body of the paper after Theorem 2. I think putting it into a theorem makes it more clear and easier to cite.\n3. The cases with $\\mu = 0$ or $\\nu = 0$ are handled in Appendix C.4, but not in a very formal way. E.g., a $O(1 / t)$ rate is mentioned, but I think the performance of your algorithm in these settings should be both stated carefully in a theorem and compared to prior work in this setting (e.g., the sub-gradient method as well as Levy et al. 2020, Carmon and Hausler 2022). Indeed, the $\\mu = 0$ and $\\nu = 0$ settings are important enough that entire papers have been written about them (and in fact, in some sense it is the original setting), so I think it is important that these are not an afterthought, and that the reader doesn't have to do any work to understand how the bounds you get in these settings compares to prior work. This is actually the single biggest weakness in my opinion.\n\nMinor/typos:\n1. Line 71 is missing a subscript. $\\ell(w)$ should be $\\ell_i(w)$.\n2. In the two inline lines above Line 431, there shouldn't be a square on the norm. I.e., it should just be $|| w_1 - w_2||_2$.\n3. Although it is clear what it is from context, I don't the the map $\\ell(w)$ is ever formally defined before you start using it in Line 97.\n4. \"witha\" in Line 7.\n5. It might be good to just mention that when you say \"smooth\" in the paper, you always mean it in the sense that the gradient is Lipschitz (and not in the sense of a $C^\\infty$ function).\n6. I would include the fact that $\\mathcal{Q}$ is any closed, convex, and nonempty set in Assumption 1. As far as I can tell, the only place you formally state this is in the text under Table 1.\n7. Maybe just use the term \"runtime\" instead of, e.g., \"global complexity.\" (Unless there is a reason you aren't using the term \"runtime\" that I'm missing?)\n8. It might be nice to mention some prior work which doesn't just have a single hyperparameter (or really, state which algorithms do and don't), just to make it more clear how significant of a contribution that is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed suggestions&mdash;we have incorporated the comments about comparisons, formal statements of complexity results, and minor typos into the manuscript.\n\n>**The cases with  $\\mu=0$ or $\\nu=0$  are handled in Appendix C.4, but not in a very formal way.**\n\nThank you for raising this point. We have changed the analysis to account for the settings of $\\mu = 0$, $\\nu = 0$, and $\\mu = \\nu = 0$ formally. Because achieving an unconditional linear convergence rate that improves upon gradient descent was the main motivation of the work, we focused on the strongly convex-strongly concave setting. In the final version, we will provide a unified analysis for all settings.  \n\n>**...it is always best to choose  $b=1$ to get the best first-order oracle complexity, but your runtime may be better with a different choice of $b$?**\n\nThat is correct. If we assume that the cost of querying the oracle is $O(d)$ and $n \\geq d$, then taking into account the $O(n)$ cost of updating the dual variable in each iteration, a batch size of $b = n/d$ balances the costs of the two updates. This affords us a $O(n^{3/2})$ dependence on $n$ in the overall runtime.\n\n>**Line 81 says that $n q_{\\max{}}$ is upper bounded by \"a constant in 𝑛,\" but isn't it just bounded by $n$ because $ q_{\\max{}} \\leq 1$?**\n\nWe have added to Appendix B a precise claim regarding the fact that $n q_{\\max{}}$ is constant. In summary, we mean that $nq_{\\max{}}$ is bounded by a constant independent of $n$. The two canonical examples of $\\mathcal{Q}$ are divergence-ball based and spectral risk measure-based feasible sets. It is true that $\\mathcal{Q}$ is always a subset of the probability simplex so $q_{\\max{}} \\leq 1$. However, this bound is only tight when  $\\mathcal{Q}$ is the entire probability simplex, regardless of the choice of $n$. Because this feasible set is often defined using statistical properties of the weights $q$, each element can be upper bounded as $q_i \\leq c/n$ for some $c \\geq 1$. For spectral risk measures, this can be seen by the argument in Section 2 of [Mehta (2023)](https://proceedings.mlr.press/v206/mehta23b.html)&mdash;every weight will be the integral of a bounded function over an interval of length $1/n$. For the $\\theta$-CVAR (see our Appendix B.2), this bound is $1/(\\theta n)$.  For f-divergence balls, in [Namkoong and Duchi (2017)](https://papers.nips.cc/paper_files/paper/2017/hash/5a142a55461d5fef016acfb927fee0bd-Abstract.html) Eq (4), the divergence ball ambiguity set is defined using radius $\\rho/n$, which enforces the condition $\\frac{n}{2} \\Vert q - \\mathbf{1}/n \\Vert _2^2 \\leq \\frac{\\rho}{n}$ on every element of $\\mathcal{Q}$ in the case of $\\chi^2$-divergence. \n\n>**Is this the first work you are aware of which applies these cyclic coordinate-style updates to a non-separable dual feasible set?**\n\nWe are not aware of any previous work that does so in a cyclic fashion. The key element at play is that $\\hat{q}_t$ (see Algorithm 1) does not need to be in the feasible set to be used in the gradient estimate in the primal update. Thus, we may apply cyclic updates to this vector even if we cannot do the same for $q_t$. \n\n>**...a classic trick to recover a non-strongly convex rate from the strongly-convex case is to just set something like, e.g., $\\mu = \\frac{\\epsilon}{2D}$ where $D$ is a bound on the diameter of $\\mathcal{W}$.**\n\nThank you for identifying this trick. This would be one way to approach this, but it relies on knowing $D$, the diameter or initial distance-to-optimum in an unbounded setting. Furthermore, it leads to an extra log factor on the complexity. We chose to provide analysis for a direct method, which does not require knowledge of $D$ and leads to the improved convergence rates.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K3mng86cuu", "reviewer": "Reviewer_VCV6", "summary": "This paper proposes DRAGO, a variance-reduced optimization method for\ndistributionally robust optimization (DRO). In particular, the authors consider\nthe penalized DRO framework and view DRO as min-max optimization with a simple\nfinite-sum structure. Their algorithm maintains explicit histories for the\nindividual loss functions $l_i$, loss function gradients $\\nabla l_i$, and dual\nparameters $q_i$ (i.e. like SAG/SAGA); these estimates are used to control the\nvariance in both the primal and dual updates, which the authors prove leads to\na fast linear rate of convergence.  Unlike existing methods, DRAGO supports any\npenalty parameter $\\nu \\geq 0$ and its convergence rate on depends explicitly\non the different problem constants.", "questions": "- Line 491: Isn't $n q_{\\text{max}} \\leq n$ trivially satisfied since $q$\n    is constrained to the probability simplex?\n\n- Figure 2: Why is $b = 1$ only show for three datasets and only in \n    terms of oracle complexity?\n\n- Display after Line 124: It looks you are using the equality,\n\n$$\\\\mathbb{E}[(l_{j_t}(w_{t+1}) - \\hat l_{t, j_t}) (l_{j_t}(w_t) - \\hat l_{t-1, j_t})] = \\\\mathbb{E}[(l(w_{t+1}) - \\hat l_{t}) (l_{j_t}(w_t) - \\hat l_{t-1, j_t})]$$\n\nbut I don't think this is true because the terms in the product are correlated. \nCan you please explain this?", "limitations": "Limitations appear to be appropriate addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- DRAGO obtains a fast linear rate and the analysis shows its dependence on\n    batch size, dataset size, and the other problem constants.\n\n- DRAGO performs well in practice, particularly when the batch-size is tuned. \n\n- The analysis permits any non-negative penalization strength $\\nu$ for the\n    dual (i.e. uncertainty) parameters.", "weaknesses": "- The paper organization makes it quite difficult to understand the different\n    algorithmic components used in DRAGO.\n    \n- The assumptions necessary for convergence are somewhat unrealistic, although\n    these appear to be standard in the literature. \n\n- The experimental evaluation is small and limited to relatively low-dimensional\n    problems.\n\n### Detailed Comments\n\nThis is an interesting paper which tries to speed up DRO by combining variance reduction with proximal gradient updates for a structured min-max problem. While I'm not an expert in DRO, the paper seems to make a solid contribution, particularly by relaxing previous requirements on the dual regularization strength $\\nu$. I also appreciate that the convergence rate shows the role of each problem constant and tuning parameter, including batch-size. Please note that I did not check the appendix for correctness. \n\n**Paper Organization**:\nI found this paper quite confusing to read. Instead of introducing DRAGO and\nthen explaining it's various algorithmic components, the authors first try to\nexplain the intuition behind the updates. This is a good idea in theory, but in\npractice there are too many moving parts to DRAGO and I quickly got lost in the\n(mostly unimportant) details. The actually key parts of DRAGO --- proximal-gradient\nupdates with SAG/SAGA style variance reduction --- are barely mentioned and this\nmakes the algorithm much harder to understand.\n\nMy suggestion is to introduce Algorithm 1 first and then explain why \nadditional proximal terms are needed in the proximal-gradient update in order\nto control the variance. At least this way the reader has a reference point\nfor understanding the discussion.\n\n**Assumptions**:\nI think that assuming each $l_i$ is both Lipschitz continuous and Lipschitz\nsmooth is quite unrealistic. Typically only one or the other of these\nconditions holds. For instance, Lipschitz continuity implies that $l_i$ is\nbounded above by a linear function, while Lipschitz smoothness implies that\n$l_i$ is bounded above by a quadratic. While both can be true, the quadratic\nbound will generally be vacuous. However, I understand from Table 1 that these\nassumptions are typical for the literature, so I don't think this is too much\nof an issue.\n\n**Experimental Evaluation**: \nI would have liked to see experiments on a higher dimensional dataset.  Since\nthe entire Jacobian $\\nabla l(w)$ must be maintained in the history, SAG-type\nmethods usually have high memory requirements as $d$ increases. The authors\npartially handle this by using a large batch-size, but this is only feasible if\nthe mini-batches can still be fit on the GPU. When $d$ is sufficiently large,\nmini-batch gradients will be inefficient to compute and I am curious if the\nrelative performance of DRAGO and LSVRG ill switch. This is particularly \nworth considering because it is only in the large-batch setting that DRAGO\nseems to outperform LSVRG\n\n### Minor Comments\n\n- Line 52: This is a super-linear complexity, but a sub-linear convergence rate.\n    Contrast with Line 62, which shows a linear rate, but a logarithmic complexity.\n\n- Line 65: Should this read \"but do not\"?\n\n- Line 24/71: It seems like you are only considering $\\nu$ in the probability simplex.\n    It would be nice if you stated this explicitly somewhere.\n\n- Line 80: It's generally unrealistic for both $l_i$ and $\\nabla l_i$ to be \n    Lipschitz continuous over an unbounded set.\n\n- Line 86: You should mention that strong convexity comes only from the regularizer,\n    as otherwise it seems to conflict with Lipschitzness of $l_i$. \n\n- Line 102: Does $\\nabla l(w_{t-1})$ denote the Jacobian of the vector-valued map\n    $l$ such that $[l(w)]_i = l_i(w)$? It would be nice if you clearly defined\n    this notation.\n\n- Table 1: The font-size is much too small to read when printed. \n\n- Algorithm Description: The purposes of $\\bar{\\beta}$ and $\\beta_t$ and their\n    settings are not well described.\n\n- Display after Line 164: You seem to be using $D(q \\| 1/n)$ is\n    1-strongly-convex for this result, but this assumption is only introduced\n    in Assumption 1. Maybe move Assumption 1 to the start of the discussion\n    of convergence to fix this?\n\n- Figure 3: The font-size is much too small to be readable without zooming.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We address them below.\n\n>**SAG-type methods usually have high memory requirements as $d$ increases.**\n\nThank you for identifying this important point. We have updated the manuscript to include a discussion on space complexity, which in many cases can be reduced far below $O(nd)$ for two reasons. First, this is a known limitation for SAG/SAGA-type variance reduction methods for empirical risk minimization. That being said, the additional storage cost (beyond the training data) is $O(n)$ in many common cases. This is because convex losses in machine learning can typically be expressed as $\\ell_i(w) = h(y_i, x_i^\\top w)$ for some differentiable error function $h$ and so the gradient is given by the scalar multiplication $h’(y_i, x_i^\\top w) \\cdot x_i$, where $h’$ is the derivative with respect to the second argument. Thus, only these scalar derivatives need to be stored. Second, there is a more subtle difference between our method and SAG-type methods. We use cyclic updates instead of randomized updates for the table of past gradients (as opposed to the randomized updates in SAGA). Conceptually, this means that for very large-scale workloads, a fraction of the gradient table can be paged out of memory until its values are updated again.   \n\n>**The experimental evaluation is small and limited to relatively low-dimensional problems.**\n\nTo illustrate performance, we scaled up the text classification task to $d = n/2 \\approx 4000$ and show the improvement over LSVRG in the attached PDF (see Figure 5). This means that the batch size is approximately $2$. We hypothesize that the benefit over LSVRG comes from the fact that the dual variable is updated in epochs of length $n$ iterations to balance out the $O(n)$ cost of the update. We incur a higher per-iteration cost but have improved theoretical and empirical performance over the training trajectory. \n\n>**The paper organization makes it quite difficult to understand the different algorithmic components used in Drago.**\n\nThank you for the helpful suggestions on paper organization. In the revised version, we have introduced the algorithm early on and described it using the reference points you have mentioned. We have dedicated more of the main text toward the comparisons noted in Appendix B.\n\n>**The assumptions necessary for convergence are somewhat unrealistic, although these appear to be standard in the literature. I think that assuming each $\\ell_i$ is both Lipschitz continuous and Lipschitz smooth is quite unrealistic. Typically only one or the other of these conditions holds.**\n\nBecause the losses exist within the statistical learning context, assuming both Lipschitz continuity and smoothness is valid in common scenarios. A canonical loss in robust statistics is the Huber loss, which is both Lipschitz and smooth. Similarly, any smooth loss will be Lipschitz continuous if $\\mathcal{W}$ is compact. Compactness is a common assumption, as statistical guarantees (uniform convergence, minimax rate optimality, etc.) rely on it.\n\n>**Isn't $nq_{\\max{}} \\leq n$ trivially satisfied since 𝑞 is constrained to the probability simplex?**\n\nWe have added to Appendix B a precise claim regarding the fact that $n q_{\\max{}}$ is constant. In summary, we mean that $nq_{\\max{}}$ is bounded by a constant independent of $n$. The two canonical examples of $\\mathcal{Q}$ are divergence-ball based and spectral risk measure-based feasible sets. It is true that $\\mathcal{Q}$ is always a subset of the probability simplex so $q_{\\max{}} \\leq 1$. However, this bound is only tight when  $\\mathcal{Q}$ is the entire probability simplex, regardless of the choice of $n$. Because this feasible set is often defined using statistical properties of the weights $q$, each element can be upper bounded as $q_i \\leq c/n$ for some $c \\geq 1$. For spectral risk measures, this can be seen by the argument in Section 2 of [Mehta (2023)](https://proceedings.mlr.press/v206/mehta23b.html) - every weight will be the integral of a bounded function over an interval of length $1/n$. For the $\\theta$-CVAR (see our Appendix B.2$, this bound is $1/(\\theta n)$.  For divergence balls, in [Namkoong and Duchi (2017)](https://papers.nips.cc/paper_files/paper/2017/hash/5a142a55461d5fef016acfb927fee0bd-Abstract.html) Eq (4), the divergence ball ambiguity set is defined using radius $\\rho/n$, which enforces the condition $\\frac{n}{2} \\Vert q - \\mathbf{1}/n \\Vert _2^2 \\leq \\frac{\\rho}{n}$ on every element of $\\mathcal{Q}$ in the case of $\\chi^2$-divergence. \n\n>**Why is $b=1$ only show for three datasets and only in terms of oracle complexity?**\n\nAs mentioned toward the end of section 4.1, the $b=1$ is only competitive with baselines for small datasets. As the dataset size grows, the batch size needs to be increased to maintain performance. While the theoretically optimal batch size $n/d$ is a good default value, $b$ can be tuned experimentally to achieve the best performance (with respect to $b$) for a particular empirical setting. \n\n>**Display after Line 124: It looks you are using the equality ... but I don't think this is true because the terms in the product are correlated.**\n\nThis equality holds because the expression in the expectation is the inner product between two vectors $\\ell(w\\_{t+1}) - \\hat{\\ell}\\_t$ and a “one-hot” vector $(\\ell\\_{t, j\\_t} - \\hat{\\ell}\\_{t-1, j\\_t})e\\_{j\\_t}$ (see Eq (8)). Thus, the only terms that are multiplied are in the $j_t$ coordinate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zjHEE1p89C", "reviewer": "Reviewer_ccWo", "summary": "The authors provide a state-of-the-art optimization algorithm with convergence guarantees for f-divergence DRO. The numerical study is also extensive", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Techincal results are strong and to the best of my knowledge, I haven't find mistakes\n2. Numerical study is extensive", "weaknesses": "As the author has commented, they only solve for convex optimization formulation. The extension to non-convex setup also seems interesting and important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We address the main concern below.\n\n>**As the author has commented, they only solve for convex optimization formulation. The extension to non-convex setup also seems interesting and important.**\n\nThank you for raising this point. Broadly, the study of optimization approaches for the non-convex setting (e.g., deep learning) relies on completely different technical tools and evaluations. Convexity is considered to make precise statements about global optimality, namely the linear convergence of the algorithm’s iterates to a solution in terms of problem constants. In the non-convex setting, one seeks convergence to a first-order stationary point under a gradient-domination or Polyak-Łojasiewicz condition or for large deep learning models with Gaussian random weights or other strong assumptions. Our focus here is on sound theoretical convergence results, for convex optimization algorithms, one of the subject areas of NeurIPS.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xEB1D6yOOG", "reviewer": "Reviewer_WLa8", "summary": "To tackle the optimization problem where the objective is a weighted sum of losses from multiple domains, an improved optimization algorithm is designed by incorporating past history and appropriate regularization. Merits of the proposed algorithm are demonstrated by a rigorous theoretical analysis of convergence rate  and numerical analysis by synthetic and text classification data.", "questions": "1. Regarding the remark on global complexity on page 7, I do not follow where the $bd$ term comes from in the per iteration complexity. Is it possible to provide some details? My understanding may be inaccurate, but if each elementwise update of $v_t^D$ is of low computational cost, and we update all elements in a distributed fashion, can we improve the per iteration cost to be $O(n)$? \n2. The dimensionality considered in the empirical analysis is pretty low. Can additional empirical analysis be shown where $d$ is, e.g. of a similar magnitude as $n$, if not greater than $n$? I understand that there may be a challenge in updating $q$.", "limitations": "No direct societal impact as the paper is focused on theoretical aspects of the out of distribution inference problem.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Theoretical analysis seems solid.", "weaknesses": "The proposed method seems to be only relevant for problems with a low dimensionality $d$. Otherwise, the fact that the algorithm requires to keep track of historical weights would cause a high space complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your concrete comments. We address them below.\n\n>**I do not follow where the $bd$ term comes from in the per iteration complexity. Is it possible to provide some details?**\n\nThe quantity comes from the fact that $b$ evaluations of $(\\ell_i, \\nabla \\ell_i)$ in the computation of $v^{P}_t$ (not from $v^{D}_t$), and we assume each evaluation costs $O(d)$.\n\n>**The proposed method seems to be only relevant for problems with a low dimensionality 𝑑. Otherwise, the fact that the algorithm requires to keep track of historical weights would cause a high space complexity.**\n\nThank you for identifying this point. We have updated the manuscript to include a discussion on space complexity, which in many cases can be reduced far below $O(nd)$ for two reasons. Firstly, this is a known limitation for SAG/SAGA-type variance reduction methods for empirical risk minimization. That being said, the additional storage cost (beyond the training data) is $O(n)$ in many common cases. This is because convex losses in machine learning can typically be expressed as $\\ell_i(w) = h(y_i, x_i^\\top w)$ for some differentiable error function $h$ and so the gradient is given by the scalar multiplication $h’(y_i, x_i^\\top w) \\cdot x_i$, where $h’$ is the derivative with respect to the second argument. Thus, only these scalar derivatives need to be stored.\n\nSecondly, a more subtle advantage of our method is that we use cyclic updates instead of randomized updates for the table of past gradients (as opposed to the randomized updates in SAGA). Conceptually, this means that for very large-scale workloads, a fraction of the gradient table can be paged out of memory until its values are updated again.   \n\n>**The dimensionality considered in the empirical analysis is pretty low. Can additional empirical analysis be shown where $d$ is, e.g. of a similar magnitude as $n$, if not greater than $n$?**\n\nThank you for raising this point. We scaled up the text classification task to $d = n/2 \\approx 4000$ in the attached PDF (see Figure 5). This means that the batch size is approximately $2$. Qualitatively, similar trends are observed across varying orders of magnitude for $d$, in that we show improvement over LSVRG baseline in the attached PDF. We hypothesize that the benefit over LSVRG comes from the fact that the dual variable is updated in epochs of length $n$ iterations to balance out the $O(n)$ cost of the update. We incur a higher per-iteration cost but have improved theoretical and empirical performance over the training trajectory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their hard work reviewing our paper and providing insightful and concrete comments! We have revised the manuscript to incorporate these suggestions. A summary of the main points of concern is listed below, and all remaining comments are addressed in individual responses.

**Space Complexity:** Reviewers P67z, VCV6, and WLa8 raised the major point that the space complexity of the proposed method appears to be $O(nd)$, which hinders applicability in high-dimensional scenarios. We describe in the individual responses that the true space complexity of the method can in fact be much lower (up to $O(n)$). One reason is due to a standard improvement of SAG/SAGA-type variance-reduced algorithms, and a second reason is particularly due to the unique cyclic coordinate-wise updates in our algorithm. We have also added additional experiments in a higher dimensional setting to understand performance in the $n \approx d$ regime.

**Theoretical assumptions and dependences:** First, Reviewers em1q and VCV6 inquired why we stated that quantity $n q_{\max{}}$ is upper bounded by a constant, given that it is trivially upper bounded by $n$. We clarify that the constant is independent of $n$, so it does not affect the overall complexity in terms of $n$. Second, Reviewers P67z and VCV6 mentioned the assumption that the losses and their gradients are both Lipschitz continuous may be unrealistic in common settings. In the comments, we justify these assumptions in various practical scenarios.  

**The convex-concave setting:** Finally, Reviewers em1q and P67z brought up the importance of the non-strongly convex/non-strongly concave settings, i.e. when either or both $\mu = 0$ and $\nu = 0$. We have revised the manuscript to include the analysis formally; the dependence on $n$ remains competitive.

Please see the individual responses for more details. Thank you!

Meta-review: The paper received positive reviews, with a consensus that this is a solid contribution to the literature on optimization algorithms for distributionally robust optimization. Consequently, I recommend acceptance of this paper. When preparing the camera-ready revision, please pay close attention to the reviewers’ feedback and include the additional explanations provided during the rebuttal period. In addition, in Table 1, the complexities listed for Levy et al. do not agree with the best results obtained in that paper (and shown in Table 1 of Levy et al.) - please correct this in the revision.
Decision: Accept (poster)