Stochastic Constrained DRO with a Complexity Independent of Sample Size
Authors: Qi Qi
Jiameng Lyu
Kung-sik Chan
Er-Wei Bai
Tianbao Yang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Distributionally Robust Optimization (DRO), as a popular method to train robust models against distribution shifts between training and test sets, has received tremendous attention in recent years. In this paper, we propose and analyze stochastic algorithms that apply to both non-convex and convex losses for solving Kullback–Leibler divergence constrained DRO problem. Compared with existing methods solving this problem, such as primal-dual methods and large mini-batch methods, our stochastic algorithms not only enjoy competitive if not better complexity independent of sample size but also just require a constant batch size at every iteration, which is more practical for broad applications. We establish a nearly optimal complexity bound for finding an $\epsilon$-stationary solution for non-convex losses and an optimal complexity for finding an $\epsilon$-optimal solution for convex losses. Empirical studies demonstrate the effectiveness of the proposed algorithms for solving non-convex and convex constrained DRO problems. 

Under review as a conference paper at ICLR 2023
STOCHASTIC CONSTRAINED DRO WITH A COMPLEX- ITY INDEPENDENT OF SAMPLE SIZE
Anonymous authors Paper under double-bling review
ABSTRACT
Distributionally Robust Optimization (DRO), as popular method to train ro- bust models against distribution shift between training and test sets, has received tremendous attention in recent years. In this paper, we propose and analyze stochastic algorithms that apply to both non-convex and convex losses for solving Kullback-Leibler divergence constrained DRO problem. Compared with existing methods solving this problem, our stochastic algorithms not only enjoy competitive if not better complexity independent of sample size but also just require a constant batch size at every iteration, which is more practical for broad applications. We establish a nearly optimal complexity bound for finding an e-stationary solution for non-convex losses and an optimal complexity for finding an e-optimal solution for convex losses. Empirical studies demonstrate the effectiveness of the proposed algorithms for solving non-convex and convex constrained DRO problems.
INTRODUCTION
Large-scale optimization of DRO has recently garnered increasing attention due to its promising per- formance on handling noisy labels. imbalanced data and adversarial data (Namkoong & Duchi 2017] Zhu et al. 2019; Qi et al. 2020aa Chen & Paschalidis 2018). Various primal-dual algorithms can be used for solving various DRO problems (Ratique et al. 2021 Nemirovski et al. 2209). However, primal-dual algorithms inevitably suffer from additional overhead for handling a dimensionality dual variable, where n is the sample size. This is an undesirable feature for large-scale deep learning, where could be in the order of millions or even billions. Hence, recent trend is to design dual-free algorithms for solving various DRO problems (Qi al. 202T Jin et al.) 202T Levy al,, 2020).
In this paper, we provide efficient dual-free algorithms solving the following constrained DRO problem, which are still lacking in the literature,
Epiliww) - (DD()))>>oD(,1//0)
min WEW (PEA,, D(p.1/n)so)
max
(I)
where denotes the model parameter, W is closed convex set, A, (p R2 EE p. 11 0} denotes a n-dimensional simplex, (((w) denotes a loss function on the i-th data, (p, Ei p; (pg( represents the Kullback-Leibler (KL) divergence measure between p and uniform probabilities 1/n E R",, and p is the constraint parameter, and A > 0 is a small constant. A small KL regularization on p is added to ensure the objective in terms of smooth for deriving fast convergence.
There are several reasons for considering the above constrained DRO problem. First, existing dual- et al. 2020 Hu et al. 2021). They are either restricted to problems with no additional constraints on the dual variable p except for the simplex constraint (Qi et al.] 202T Jin et al.) (021), or restricted to convex analysis or have a requirement on the batch size that depends on accuracy level (Levy et al., 2020 Hu et al. 2021). Second, the Kullback-Leibler divergence measure is more natural metric for measuring the distance between two distributions than other divergence measures, e.g., Euclidean distance. Third, compared with Ke-reuularized DRO problem without constraints, the above KL-constrained DRO formulation allows to automatically decide a proper regularization effeet that depends on the optimal solution by tuning the constraint upper bound p. The question to be addressed is the following:
free algorithms are not satisfactory (Qi et al. 2021 Jin et al.)

---

Under review as a conference paper at ICLR 2023
Can develop stochastic algorithms whose oracle complexity is optimal for both convex and non-convex losses, and its per-iteration complexity is independent of sample size n without imposing any requirements on the (large) batch size in the meantime?
We address the above question by (i) deriving an equivalent primal-only formulation that is of a compositional form; (ii) designing two algorithms for non-convex losses and extending them for convex losses; (iii) establishing an optimal complexity for both convex and non-convex losses. In particular, for a non-convex and smooth loss function (ww), we achieve an oracle complexity of (L//e²) 1 for finding an e-stationary solution; and for a convex and smooth loss function, we achieve an oracle complexity of ( for finding c-optimal solution. We would like to emphasize that these results are on par with the best complexities that can be achieved by primal-dual algorithms (Huang al. 2020 Namkoong & Duchi (016). But our algorithms have a per-iteration complexity of (dd), which is independent of the sample size n. The convergence comparison of different methods for solving ① is shown in Table
To achieve these results, we first convert the problem into an equivalent problem:
(((w) (<(()) + (A- da)p.
min min F(w, A) == A Alo
cxp
(2)
WEW A
X
By considering x= , E Rd+11 as a single variable to be optimized, the objective function is
a compositional function of x in the form of fg(()), where g = { +/ Ei= exp
((())
E R
and f(g)- 91 log(ge) 91p. However, there are several challenges to be addressed for achieving optimal complexities for both convex and non-convex loss functions e (w)). First, the problem F(x) non-smooth terms of given the domain constraint w E W and À 2 Xg- Second, the outer function [g)'s 's gradient is non-Lipschtiz continuous in terms of the second coordinate 92 if À is unbounded, which is essential for all existing stochastic compositional optimization algorithms. Third, to the best of our knowledge, no optimal complexity in the order of (112²) has been achieved for a convex compositional function except for Zhang & Lan (2021), which assumes ff is convex and component component-wisely non-decreasing and hence is not applicable to
To address the first two challenges, we derive an upper bound for the optimal À assuming that (w) is bounded for w E W, ie.. À E DA, Å], which allows us to establish the smoothness condition of F(x) and [g). Then consider optimizing F(x) F(x) + 6x(xx, where 6x(xx) = if W, [Λo, ÅJ}. By leveraging the smoothness conditions of F and f. we design stochastic algorithms by utilizing recursive variance-reduction technique to compute a stochastic estimator of the gradient of Fxx), which allows us to achieve a complexity of (()/²)) for finding a solution x such that [d) åx())) S E. To address the third challenge, we consider optimizing (x) F(x) + 14 ||| /2 for a small μr. We prove that (x) satisfies Kurdyka--Lojasiewiizz inequality, which allows us to boost the convergence of the aforementioned algorithm enjoy an optimal complexity of (11/e²) for finding an e-optimal solution to F(x).
x E X {x- (w" T, AATT
Besides the optimal algorithms, we also present simpler algorithms with worse complexity, which are more practical for deep learning applications without requiring two backpropagations at two different points per iteration as in the optimal algorithms.
2 RELATED WORK
DRO springs from the robust optimization literature (Bertsimas et al. and has been extensively studied in machine learning and statistics (Namkoong & Duchi 2017
2018 Ben- Tal et al. 2013
Duchi et al.) 2016; Staib & Jegelka| 22019] Deng et al. 2020 Qi et al. 2020b Duchi & Namkoong
2021). and operations research (Rahimian & Mehrotra 2019; Delage & Ye 2010). Depending
on how to constrain or regularize the uncertain variables, there are constrained DRO formulations that specify a constraint set for the uncertain variables, and regularized DRO formulations that use a regularization term in the objective for regularizing the uncertain variables (Levy et al. 2020). Duchi et al. (2016) showed that minimizing constrained DRO with f-divergence including x divergence constraint and KL-divergence constraint, is equivalent to adding variance regularization for the Empirical Risk Minimization (ERM) objective, which is able to reduce the uncertainty and
' omits logarithmic dependence over
2

---

Under review as a conference paper at ICLR 2023
Table 1: Summary of algorithms solving KL-constrained DRO problem. Complexity represents oracle
complexity for achicving Eldist(O, [F(x))] S é other first-order stationarity convergence for the non-convex setting and [xx(x) - [xx)] S e for the convex setting. Per Iter Cost denotes the per-iteration computational
complexity. The algorithm styles include primal-dual (PD), primal only (P), and compositional (COM).
means not available in the original paper.
Setting
Algoritims
Reference
Complexity
Batch Size
Per tter Cost
Style
PG-SMD
(Rafique et al. 2021
0[1)
Oin + +
PD
Non-convex
AccMDA
(Fuunng al. 2020
0(1/))
0(1
Oin dd)
PD
Dual SGM
Lovy ct al.
[[1]
O(d)
SCDRO
O[1]
O(d)
COM
This work
ASCDRO
0(1/))
0()
Old)
COM
FastDRC
(Levy al. 2020
O
O11())
O(5)
P
Convex
SPD
Namkoong & Ducht 2016
O
0[1
Olu Dl++d) d)
PD
Dual SGM
(Levy et al. 20220
O[1
Old)
RSCDRO
0[1
Old)
COM
This work
RASCDRO
O(1
O(o)
COM
improve the generalization performance of the model. Primal-Dual Algorithms. Many primal-dual
algorithms designed for the min-max problems can be directly applied to optimize the constrained
DRO problem. The algorithms proposed in (Nemirovski et al. |209] Juditsky et al.] [201T] Yan
eet al. 2019 Namkoong & Duchi 2016 Yan et al.) 2020 [Song et al. [021]] Alacaoolu al. 2022)
are applicable le to solving ① when l is a convex function. Recently, Ratique et al. (2021) and Yan
eet al. 2020)) proposed non-convex stochastic algorithms for solving non-convex strongly convex
min-max problems, which are applicable to solving (1) when is weakly convex function or smooth.
Many primal-dual stochastic algorithms have been proposed for solving non-convex strongly concave problems with a state of the art oracle complexity of (11c23) for finding stationary solution (Huang) ct al. 2020; Luo et al.) 2020: Tran-Dinh et al. 2020). However, the primal-dual algorithms require maintaining and updating an (n) dimensional vector for updating the dual variable.
Constrained DRO. Recently, [evy et al. (2020) proposed sample independent algorithms based on gradient estimators for solving group of DRO problems in the convex setting. To be more specific, they achieved a convergence rate of (1/e)²) for the xe-constraineddregulaiiie and CVaR- constrained convex DRO problems and the batch size of logarithmically dependent on the inverse accuracy level (log( For the KL-constrained DRO objective and other more general setting, they achieve a convergence rate of ((1/2)) under a Lipschitz continuity assumption and a mini-batch gradient estimator with a batch size in the order O(1/c) (please refer to Table in Levy et al. (2020)). In addition, [Levy et al. (020)) also proposed simple stochastic gradient method for solving the dual expression of the DRO formulation, which is called Dual SGM. In terms of convergence, they only discussed the convergence guarantee for the x²-regularized and CVaR penalized convex DRO problems (cf. Claim 3 in their paper). However, there is still gap for proving the convergence rate of Dual SGM for non-convex KL-constrained DRO problems due to similar challenges mentioned in the previous section, in particular establishing the smoothness condition in terms of the primal variable and the Lagrangian multipliers (denoted as x, V; 1 respectively in their paper). This paper makes unique contributions for addressing these challenges by (i) removing 7 in Dual SGM and deriving the box constraint for our Lagrangian multiplier À for proving the smoothness condition; (ii) establishing an optimal complexity in the order of O(1/e²) in the presence of non-smooth box constraints, which, to the best of our knowledge, is the first time for solving a non-convex constrained compositional optimization problem.
with the help of multi-level Monte-Carie (MLMC) gradient estimator.
the inverse CDF of the loss function
Regularized DRO. DRO with KI. divergence regularization objective has shown superior perfor- mance for addressing data imbalanced problems (Qi et al. 2021 2020a Li et al.) 2020 202 I). Jin et al. (202T) proposed a mini-batch normalized gradient descent with momentum that can find a first-order stationary point with an oracle complexity of (11/e)) for KL-regularized DRO and x2 regularized DRO with a non-convex loss. They solve the challenge that the loss function could be unbounded. Qi al. (2021) proposed online stochastic compositional algorithms solve KI-- regularized DRO. They leveraged a recursive variance reduction technique (STORM (Cutkosky & Orabonal ) compute a gradient estimator for the model parameter w only. They derived a complexity of ((1/e)) for a general non-convex problem and improved it O(1((ue)) for a
PPG-SMD2 refers to PG-SMD algorithm under Assumption D2 in Rafique et al. 2021).
FastDRO is name of the GitHub repository of Levy et al. (2020) and we use the name "FastDRO" to refer the algorithm based mini-batch gradient estimator in I levy 2020
3

---

Under review as a conference paper at ICLR 2023
problem that satisfies an Jt-PL condition. Qi et al. (2020a) reports worse complexity for simpler algorithm for solving KL-regularized DRO. Li et al. (2020) 2021) studied the effectiveness of KL regularized objective different applications, such enforcing fairness between subgroups, and handling the class imbalance.
More related works included in the appendix due limit of space, which will not affect the discussion of results in this paper.
PRELIMINARIES
In this section, we introduce notations, definitions and assumptions. We show that is equivalent to 2 in Section G in Appendix.
Notations: Let ||- denotes the Euclidean norm of a vector or the spectral norm of matrix. And x A
(w A E Rd+1 9: (x) exp( fi(w) and g()) Ee-p[exp( (=(W)) )} where D denotes the training set and denotes the index of the sample randomly generated from D. Let fx(+) = log(-) + Ap,
and (g) = denotes the gradient f in terms of g. Let [Ix(-) denote an Euclidean projection
onto the domain X. Let [2'] = fI, 7" and T ~ [7] denotes a random selected index. We make the following standard assumptions regarding to the problem
Assumption 1. There exists R, G, C, and L such that
(a) The domain of model parameter W is bounded by R. i.e. for all w E W, we have ||w|| S R.
(b) &, (w) is G-Lipschitz continuous function and bounded by C, i..., [[),(())] S G and [w)) C. for all w W and D.
(c) & (w()) ) is L-smooth, i.e., [V1:(w)) V(.(22) S L|[wi - well. Vw1, W2 E W,i D.
(d) There exists a positive constant A < oc and an initial solution (W1, A1) such that F(W1: A1) min min F(w, A) A.
wEW X2
Assumption 2. Let gg. ovg be positive constants and x² max Jgg.. For D, assume that (x) - (x S og. (x) - Vg(x)
< o.
Remark: Assumption I (a). i... the boundness condition W is also assumed in Levy et al. (2020), which is mainly used for convex analysis. Assumption [T). (c), i.e., the Lipstchiz continuity and smoothness of loss function, and the variance bounds for g: and its gradient in Assumption 2 can
be derived from Assumption 1 (b), such that [x]lg((x) [ < [x)]9( S exp( (o ) and
g Vg(x))l?] < [|| gx) S exp( 22 (G + Ca
Au
However, F(w, X) is not necessarily smooth in terms x = (w" A)T if A is unbounded. To address this concern, prove that optimal À is indeed bounded.
Lemma The optimal solution of the dual variable X to the problem ? is upper bounded by Ā do + C/p, where C is the upper bound of the loss function and p is the constraint parameter. Thus, we could constrain the domain of X in the DRO formulation with the upper bound ', and obtain the following equivalent formulation:
Σ exp (((w)
min min llg WEW AAŠA
+ Ap.
(3)
The upper bound guarantees the smoothness of F(w, A) and the smoothness of fx(-), which are critical for the proposed algorithms to enjoy fast convergence rates.
Lemma 2. F(w, A) is Lp-smooth for any E W and X E [No, where Lp = ÄL3 2Lg
ÄLV, + 1 + X. Ly and Lv, are constants independent of sample size and explicitly derived in Lemmal 7
Below, we let X {x/w E W, SA (AS 0f E X, and dx(x) 0o if x $ X. The
problem is equivalent to: min x Fxx) = F(x) + 5x()),
(4)
Since F is non-smooth, define the regular subgradient follows.
"We would like to point out that the variance bound and the smoothness constant Lr are exponentially dependent on the problem parameters, are these constants in some other stochastic methods solving constrained DRO, like Dual SGM in Levy et al. (2020).
4

---

Under review as a conference paper at ICLR 2023
Definition (Regular Subgradient), Consider function T R - R and ((x)) is finite at point For vector R", is a regular subgradient & at x, written 0
lim inf ((x)
((x)) (x 20 0.
xx x
Since (x) is differentiable, we use (x) (x))) + xxx((x) (see Exercise 8.8 Rockafellar Wets 1998)) in the analysis. Recall the definition of subgradient of convex function F which is denoted by D.. When Fxx) is convex, have 0F(x) 0F(x) (see Proposition 8.2 in Rockafellar
& Wets 1998 ). The (Ost((0, (F())) measures the distance between the origin and the regular subgradient set of F at x. The oracle complexity is defined below:
Definition (Oracle Complexity). Let > 0 be a small constant, the oracle complexity is defined as the number of processing samples z in order to achieve E[dist(()) @F(x))) S c for non-convex loss function or [[F(x) F(xx.] ] S c for convex loss function.
4 STOCHASTIC CONSTRAINED DRO WITH NON-CONVEX LOSSES
In this section, we present two stochastic algorithms for solving 4 The first algorithm is simpler yet practical for deep learning applications. The second algorithm accelerated one with better complexity, which is more complex than the first algorithm.
Algorithm 1 SCDRO(x), V1, 81, m,,
Algorithm 2 ASCDRO(X), V1, 81, m1, Ti)
1: Input: w1 E W. 2 λo X1 = [wT, T
I: Input: w1 E W1 2 Au x1 = -wT A2)
2: Initialization: Draw sample
D, and 2: Initialization: Draw a sample E D, and
calculate = exp({((w1)/Ai)
calculate 81 = exp(fx (x))((())/\\))
V1 = VfA, #1 = Vfx,
ERd
VI (wg(( Rd
log(s1) + P
#i = (x1) E
3: for 1,... , do
for 1. 1, 1.... 7 do
4:
Update X++1 = xIx (x; - TI2))
4: Update X,+1 = xxx r72z), where is
5: Draw a sample E,
given in (8)
6: Let 81+1 (1 B)st + Bgi (x++1)
5: Draw sample & D
7: Update Vi+1, U1+1 according to
6: Update 81-1, Ve+1, U4+1 according to
8: end for
7: end for
9: return: (x,, Vr, Ur 87), where T
8: return: (7,, Ur 87), where T ~ [T]
4.1 BASIC ALGORITHM: SCDRO
major concern of the algorithm design is to compute a stochastic gradient estimator of the gradient of F [xx). At iteration the gradient of F(x,) given by
Ow F(x,) V fx, V (x;)) F(x) = Vʃa (g( Vxg(x,) (x.()(())) + p.
(5)
Both (xg(x;) and Vx)( can be estimated by unbiased estimator denoted by (x,... The
concern lies at how to estimate x.) inside V V/x, (-). The first algorithm SCDRO is applying existing techniques for two-level compositional function. In particular, we estimate gxx)) ) by a sequence of
St, which is updated by moving average s, (1 -) 1 + (x,) Then we substitute gxx,)
in Ow F' Fx;:) and F(x;) with 8t, and invoke the following moving average to obtain the gradient estimators in terms of w, and A respectively,
V: = (1 3), + 3( fA, (5t) V Agg (x:) + log(st) + p).
3)v + 8V [x, (s:) ( (x))
Finally we complete the update step of x, by X 11. (x: - 72z), where Z: = (v. uz)
We would like to point out the moving average estimator for tracking the inner function g (w) is widely used for solving compositional optimization problems (Wang et al.) 2017 Qi et al. 2021 Zhang & Xiao 2019 Zhou et al.] 2019). Using the moving average for computing stochastic gradient estimator of a compositional function was first used the NASA method proposed in Ghadimi et al. (2020). The proposed method SCDRO is presented in Algorithm It is similar to NASA but with
5

---

Under review as a conference paper at ICLR 2023
simpler design on the update of X(+1- We directly use projection after SGD-tyle update. In contrast, NASA uses two steps to update x As a consequence, NASA has two parameters for updating x while SCDRO only has one parameter for updating x It is this simple change that allows us to extend SCDRO for convex problems in the next section. Below, we present the convergence rate of our basic algorithm SCDRO for a non-convex loss function.
Theorem 1. Suppose the Assumption / and hold, and set 3 - .1
3
Then after running
2013
Algorithm T iterations, we have El (F(x))) S (624x² + 2802)
//4
+
201
T
Remark: T shows that SCDRO achieves a complexity of (1/c²)) for finding an e-stationary
point. i... [O, (F I for non-convex loss function. Note that NASA Ghadiim et al. 2020) enjoys the same oracle complexity but for different convergence measure, i.c., E [x,
x|| Iz F S for returned primal-dual pair (x, 2). where yx, 2) = IIx z]. We can see that our convergence measure is more intuitive. In addition, we are able to leverage our convergence measure to establish the convergence for convex functions by using
(KL) inequality and the restarting trick as shown in next section. In contrast, such convergence for NASA missing in their paper. Compared with stochastic primal-dual methods (Rafique al. 2021; Yan et al., 2020) for the min-max formulation (I). their algorithms are double looped and have the same oracle complexity for different convergence measure, i.e., E(dist(O, åF (x) < y | - x. ||2] < for some returned solution x, where x. a reference point that is not computable. Our convergence measure is stronger as we directly measure E Eldist(O,, (F(())) on a returned solution x,, This due to that we leverage the smoothness of F(-).
4.2 ACCELERATED ALGORITHM: ASCDRO
Our second algorithm presented in Algorithm i inspired by Qi et al. (2021) for solving the KL- regularized DRO by leveraging a recursive variance reduced technique (i.c.. STORM) to estimate g(we) and V w.) for computing 0w F(x,) and 0₂ F(x,) in (5). In particular,
use v, for tracking V (xg( use ut for tracking Vxg(x,), and use 8t for tracking g(x)), which are updated by:
V.- = Vwgi(x,) + (1 (v, V WiDi (x+-1))
U4 (x (1- (1-3) -
8, (x.) + (1 () (x)x
A similar update to 8t has been used in Chen al. (202T) for tracking the inner function values for two-level compositional optimization. However, they do not use similar updates for tracking the gradients Vt, ug Hence, their algorithm has worse complexity.
Then we invoke these estimators into Owr (xx,) and F(x,) to obtain the gradient estimator + log(s;) + p)
2: (s) fA.
Below, we show ASCDRO can achieve a better convergence rate in the non-convex loss function. ag 3/8
Theorem 2. Under Assumption I and 2 for any a > 1, let = Lp w max(2o² (1)
and e = 14hpKT + 1. Then after running Algorithm 2 for iterations with 1)- (w+to2)
9²
and B. = ent we have (O, OF(x))) so
loo T Ta/a
Remark: Theorem 2 iiplies that with polynomial decreasing step size, ASCDRO is able find an e-stationary solution such that (0, (F(()))) S < with a near-optimal complexity ((1ee). Note that the complexity ( is optimal up to a logarithmic factor for solving non-convex smooth optimization problems (Arjevani et al., 2019). State-of-the-art primal-dual methods with variance-reducce for min-max problems (Huang et al. 2020) have the same complexity but for different convergence measure, i.e, B[ XX
IIx X > VF(x)]l < e for a returned solution x.
5 STOCHASTIC ALGORITHMS FOR CONVEX PROBLEMS
In this section, we presented restarted algorithms for solving 3 with a convex loss function & (w). The key is to restart SCDRO and ASCDRO by using stagewise step size scheme. We define new objective F (x) = (x) + |||x||| // and correspondingly (x) = [x)()) + (x)),, where μ is a constant to be determined later. With this new objective,
have the following lemma.
Lemma 3. Suppose that & (w) is convex for all i, then for all x E X. Fx(x) satisfies the following
Kurdyka-Lojasiewicz (KL) inequality dist(0, aF,, (x))² 2 (x(FF(x))
inf Pu(x)).
xEX

---

Under review as a conference paper at ICLR 2023
Algorithm 3 RSCDRO or RASCDRO
1: Input: Wi E W, E ERR. x1 (wi,, AT)
2: Initialization: The same as in SCDRO or ASCDRO
3: Let Ag = (xx: Vk: Ug: 8k)
4: for k = 1. K do
5: AR+1 = SCDRO Th, Tk) or A&+1 ASCDRO Ax. Tee T): Tk)
6: Change 7ı. T& according to Lemma or Lemma
7: end for
8: return: XK
Lemma allows us to obtain the convergence guarantee for convex losses. The idea of the restarted algorithm is to apply SCDRO and ASCDRO to the new objective (x) by adding μix to fx, (&)) V x.) (x,( + +p) Eq. (6 of Algorithm I and substituting (v v,, ffx, (sr)u, log( (8)) + p) + (uX,, and restarting SCDRO or ASCDRO with a stagewise step size to enjoy the benefit of KL incquality of (x). is notable that stagewise step size is widely and commonly used in practice. The multi-stage restarted version of SCDRO and ASCDRO are shown Algorithm
(x,), (x,)
in (8) of Algorithm by
3 to which we refer as restarted-SCDDR
(RSCDRO) and restarted-ASCDRO (RASCDRO).
5.1 RESTARTED SCDRO FOR CONVEX PROBLEMS In this subsection, present the convergence rate of RSCDRO for convex losses. We first present lemma that states Fy (xx) is stagewisely decreasing.
Lemma 4. Suppose Assumptions
[ and 2 hold, f((w) convex for all i, and (x(x1) infxxx (x) I A < OC. Let 61
Du Ck Ck-1/2, BR minf peg 1), 7k co
seL min 02 T2cb7 and Ta max{ 384c1300 384c12 where = -84LLp. Run RSCDRO. then have (Xp)
A
inf Fx)) S ct for each stage k.
xEX
The above lemma implies that the objective gap E (x(x)) innfxxx (x)) is decreased by a factor of 2 after each stage. Based the above lemma, RSCDRO has the following convergence rate
Theorem 3. Under the same assumptions and parameter settings as Lemma 4 after K ((lg2((1/c)) stages, the output of RSCDRO satisfies ([F,(xk) infxex (x(x]] S c, and the oracle complexity is O(1/p²e).
The following corollary follows from the above theorem (please see Appendix F.5 for proof).
Corollary 1. Lef J = c/(2(R2 + X2)). Then under the same assumptions and parame- ter settings as Lemma 4 after K O(logz(E1/e) stages, the output of RSCDRO satisfies
[[F(xk) - infxex F(x) < and the oracle complexity is (11/e))
5.2 RESTARTED ASCDRO FOR CONVEX PROBLEMS
In this subsection, establish a better convergence rate of RASCDRO for convex losses.
Lemma 5. Suppose Assumptions
7 and 2 hold, l,(w) is convex for all i, and F Fx(x1) An Ck ck-1/2, Be = min 20 1 cl, 7k
infxex (x(x) S Aμ < oc. Let
JeEE ming ZicLnoz 24cT. and max 192cLpg 192aL,.0² 1311-
192612 where c 768L7, Run RASC-
pez P
DRO, then we have (xx,)xx) - infxex Fu(x)]
S for each stage k.
The above lemma implies that the objective gap (x+) infxex Fx(x)) is decreased by factor of 2 after each stage. Hence we have the following convergence rate for the RASCDRO.
Theorem 4. Under the same assumptions and parameter settings as Lemma 5 after K =
(log2(e1/c)) stages, the output of RASCDRO satisfies E(F,(xk) infxex Fy S c, and the oracle complexity is O (max (1/pe, 1/ 1/2 //))/
By the same method of derivation of Corollary
I the following corollary of Theorem holds.
Corollary 2. Let μ = (2 + X2)). Then under the same assumptions and parameter settings
as Lemma 5 after K = ((log((1/E)) stages, the output of RASCDRO satisfies [F(((x)) infxex F(x) and the oracle complexity is (1122).
7

---

Under review as a conference paper at ICLR 2023
CIAAIEST
CIPARI9-TT
trageho-111
Provedic
24
Commile
Figure 1: Training accuracy (%) vs # of processed training samples for the convex setting. p is fixed to 0.5 on CIFARIO-ST and CIFAR100 ST, and 0.1 on ImageNet-LT and INaturalist2018. The results are averaged over independent runs,
CIPARINGST
Frag
Training accuracy vs # of processed training samples for the non-convex setting. p is fixed 0.5 on all datasets. The results are averaged over independent runs.
Figure 2:
Remark: Corollary 2 shows that RASCDRO achieves the claimed oracle complexity O()/²2) for finding c-optimal solution, which is optimal for solving convex smooth optimization problems (Ne mirovsky& & Yudin 1983). Finally, we note that a similar complexity was established in (Zhang & Lan 2021) 1) for constrained convex compositional optimization problems. However, their analysis requires each level function to be convex, which does not apply to our case as the outer function fx(+)
non-convex.
6 EXPERIMENTS
In this section, we verify the effectiveness of the proposed algorithms in solving imbalanced classifi- cation problems. We show that the proposed methods outperform baselines under both the convex and non-convex settings in terms of convergence speed, and generalization performance. In addition, we study the influence of to the robustness of different optimization methods in supplement. Baselines. For the comparison of convergence speed, for optimizing the same objective (T. including, stochastic primal-dual algorithms, namely PG- SMD2 (Rafique et al. 2021) for non-convex loss, and SPD (Namkoong & Duchi 2016) for convex loss, Dual SGM (Levy et al. 2020) and mini-batch based SGD named FastDRO (Levy et al.)
compare with different algorithms
2020) for both convex and non-convex losses. For the comparison of generalization performance, we compare with different methods for optimizing different objectives, including the traditional ERM with CE loss by SGD with momentum (SGDM), KL-regularized DRO solved by RECOVER (Qi DRO optimized by FastDRO.
et al. 2021), and WWaR-coostrrinedd x² beggularized/-constiiie
Datasets. We conduct experiments four imbalanced datasets, namely CIFAR10- CIFAR100-ST
(Qi et al.] 2020b). ImageNet-LT (Liu et al.) 2019). and iNaturalis22018 (iNaturalist 2018 competition dataset). The original CIFARIO. CIFARIOO 100 are balanced data, where CIFARIO (resp. CIFAR 100) has 10 (resp. 100) classes and each class has 5K (resp. 500) training images. For constructing CIFARIO-ST and CIFARI00-ST, we artificially construct imbalanced training data, where we only keep the last 100 images of each class for the first half classes, and keep other classes and the test data unchanged. ImageNet-IT is long-tailed subset of the original ImageNet-2012 by sampling a subset following the Pareto distribution with the power value 6. It has 1 115.8K images from 1000 categories, which include 4980 for head class and images for tail class. iNaturalist 2018 a real- dataset whose class-frequency follows heavy-tail distribution. It contains 437K images from 8 8142 classes.
Models. For a non-convex setting (deep model), we learn ResNet20 for CIFARIO-ST. and ResNet50 for ImageNet-LT and iNtuuralis2201. 18, respectively. On CIFARIO-ST, CIFARIO0- we optimize the network from scratch by different algorithms. For the large-scale ImageNet-L.T and iNaturalist2018 8 datasets, we optimize the last block of the feature layers and the classifier weight with other layers frozen of a pretrained ResNet50 model. This is a common training strategy in the literature (Kang al. 2019: Qi et al. 2020a). For a convex setting (linear model), we freeze the feature layers of the pretrained models, and only fine-tune the last classifier weight. The pretrained models for ImageNet-LT, CIFARIO-STI CIFAR 100-STT are trained from scratch by optimizing the standard cross- cross-yntropy (CE) loss using SGD with momentum 0.9 for 90 epochs. The pretrained ResNet50 model for iNaturalis22018 8 is from the released model by Kang et al. (209.)
1IFAR100-ST
8

---

Under review as a conference paper at ICLR 2023
Parameters and Settings. For all experiments, the batch size is 128 for CIFARIO-ST and CIFARIO0- ST. and 512 for ImageNet-LT and iNaturalist2018. The loss function is the CE loss. The A is set to 1e-3. The (primal) learning rates for all methods are tuned in {0.01, 0.05, 0.1, 0.5, 1]. The learning rate for updating the dual variable in PG_SMD2 and SPD is tuned in (1e-5, 5e-5, le-4, 3e-4)). The momentum parameter in our proposed algorithms and RECOVER are tuned {0.1 0.1 : 0.9). For RECOVER, the hyper-parameter À is tuned in {1, 50, 100}. The constrained parameter is tuned in 10.1,0.5, 13 for the comparison of generalization performance unless specified otherwise. The initial À and Larange multiplier in Dual SGM are both tuned in {0.1, 1, 10).
Convergence comparison between different baselines. In the convex setting, we compare RSCDRO and RASCDRO with SPD, FastDRO and Dual SGM baselines. We report the training accuracy and testing accuracy in terms of the number (#) of processing samples. We denote pass of training data by 1 epoch. We run total of 3 epochs for CIFARIO-ST and CIFAR 100-ST and decay the learning rate by factor of 10 the end of 2nd epoch. Similarly, we run 60 epochs and decay the learning rate at the 30th epochs for the ImageNet-LT, and run 30 epochs and decay the learning rate at the 20th epoch for iNaturalist2018. In the nonconvex setting, we compare SCDRO with two baselines, PG-SMD2 and FastDRO. We run 120 epochs for CIFAR 10-ST and CIFAR 100-ST, and decay the learning rate by a factor of 10 at the 90th epoch. And we run 30 epochs for ImageNet-IIT and INaturalist0018, 18, and decay the learning rate at the 20th epoch.
Results. We first report the results for convex setting in Figures and 3 It is obvious to see that RSCDRO and RASCDRO are consistently better than baselines on CIFARIO-SY CIFAR100-ST and ImageNet-LTT PD-SMD2 and Dual SGM have comparable results with our proposed algorithms on the iNaturalist2018 8 in terms of training accuracy, but is worse in terms of testing accuracy. FastDRO has the worst performance on all the datasets. RSCDRO and RASCDRO achieve comparable results on all datasets, however, the stochastic estimator in RASCDRO requires two gradient computations per iteration, which incurs more computational cost than RSCDRO. Hence, in the non-convex setting, we focus on SCDRO. Figure 2 and 4 report the results for non-convex setting. We can see that SCDRO achieves the best performance on all the datasets. The margin increases on the large scale ImageNet-LT and INaturalist2018 datasets. For the three baselines, Dual SGM has better testing performance than FastDRO and PD-SGM2 on CIFAR 10-ST and CIFAR I O0-ST. On the large scale data ImageNet-LT and iNaturalist018. however, Dual SGM has the worst performance in terms of the testing accuracy. Furthermore, SCDRO is more stable than FastDRO and Dual SGM in different settings as the training of Dual SGM and FastDRO comparable SCDRO in convex settings and much worse than SCDRO in non-convex settings.
Comparison with ERM and Kl-rreglarrized DRO. Next, we compare our method for solving Kl--conttriined DRO (KL--DDR) with 1) ERM+SGDM, and KL.rregularized DRO (KL_-DRO) optimized by RECOVER in the non-convex setting 2) CVaR-constrained DRO, x x-rregularized DRO x *--constainned DRO optimized by FastDRO in the convex setting. We conduct the experiments on the large-scale ImageNet-LT and iNaturalis20188 datasets. The results shown in Table 2 and vividly demonstrate that our method for constrained DRO outperforms the ERM-based method and other popular f-divergence constrained/reggllrizedd DRO in different settings.
Table 2: Testing Accuracy in Convex Setting
Table 3: Testing Accuracy in Non-Conver Setting
ImageNa-LLT
iNaturalist2018
ImngeNet-LT
INaturalis20118
KL. Ml--Contraintt a SCDRO
24.08 (= 0.01) | 55.63 (+: 0.03)
KL-C KL-Coostraint SCDRO
43.74
65.59
CVaR- Constraint FisDRO
17.23 (= 0.03)
54.52 (2: 0.11)
ERM-SGDM
43.36
61.12
x Regularization FasDRR
23.98 (= 0.01)
| 55.03 (+ 0.03)
KL- RegaRaiizztiinnn RECOVER
42,68
61.57
x Constraint FasDRO
23.61 (= 0.01) 53.71 (+: 0.05)
CONCLUSIONS
In this paper, we proposed dual-free stochastic algorithms for solving KL-constrained distributionally robust optimization problems for both convex and non-convex losses. The proposed algorithms have nearly optimal complexity in both settings. Empirical studies vividly demonstrate the effectiveness of the proposed algorithm for solving non-convex and convex constrained DRO problems.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ahmet Alacaoglu, Volkan Cevher, and Stephen J Wright. On the complexity of a practical primal-dual coordinate method. arXiv preprint arXiv:2201. 006644 2022.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: arXiv: 1912.0236,, 2019.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 39(2):341-357, 2013.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Programming, 262222235- 2018.
Mathematical
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Ruidi Chen and Ioannis C Paschalidis. A robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Research, 19(13), 2018.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimizatiion is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processingg 69:4937-4948, 2021. doi: 10.1 119/tt0..022222 20....21111777 URL htttttts////i...///11111 wtt.://///0.1111.5555501...
3092377
Ashok Cutkosky and Francesco Orabona. Momentum- variance reduction in non-convex sgd. Advances in Neural Information Processing Systems, 92:15236-152453 2019.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, (8(3):595-612 2010.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances Neural Information Processing Systems, 33, 2020.
Darinka Dentcheva, Spiridon Penev, and Andrzej Ruszezynski. Statistical estimation of composite risk functionals and risk optimization problems. Annals of the Institute of Statistical Mathematics, 69(4):737-760 2017. bttp::ttpsss....... httpatttppe/eeoappppeeeeeeeeeeee repe v:69:y: 2017 4: :d: 10. 1110000111300111-111111111111111 htt.://ppr...e..e....eoe//eee.aa www.:ee..rrg/ePP.ese.....
C. John Duchi, W. Peter Glynn, and Hongseok Namkoong. Statistics of robust optimization: A
generalized empirical likelihood approach. Mathematics of Operations Research, 2016.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 49(3): (113):377-1146) 2021.
Saeed Ghadimi, Andrzej Ruszezynski, and Mengdi Wang. A single timescale stochastic approxima- tion method for nested stochastic optimization. SIAM Journal on Optimizution, 30(1)99009979
2020.
Yifan Hu, Xin Chen, and Niao He. On the bias-variance-cost tradeoff of stochastic optimiza- tion. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 22119-22131. Curran As- sociates, Inc., 2021, URL (oLL:atttpaa/pproeeediii
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated ordeth-order momentum methods from mini to minimax optimization. arXiv e-prints. pp. arXiv-2008, 2020.
iNaturalist 2018 competition dataset. iNaturalist 2018 competition dataset. hatts::/
com/ve hom/viss wwviviseeee www.spppiiaa// hatpa/iantttopppaeeeeee reee mas ser 2018 2018.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust
optimization: aon-asymptotic analysis. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Under review as a conference paper at ICLR 2023
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. arXiv preprint arXiv:1910.09217, 2019.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33, 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference Learning Representations, 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi. and Virginia Smith. On tilted losses in machine learning: Theory and applications. arXiv preprint wrXiv:2109.06144 2021.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2537-2544 2019.
Luo Luo, Haishan Ye. Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strone www.ee-stroolyyconcaee minimax problems. Advances in Neural Information Processing Systems, 33, 2020.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In NIPS, volume 29, pp. 2208-220111 2016.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in neural information processing systems, pp. 2971 1-970, 2017.
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddlc-point problems. Journal of optimization theory and applications, 142(1):205-22) 228, 2009.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 19(4):1574- 1609, 2009.
A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. A Wiley-Intersciencee publication. Wiley, 1983. ISBN 9780471103455. URL vittps://boot
google wow.glee.com/booos01000 SUL
Qi Qi. Yi Xu, Rong Jin, Wotao Yin, and Tianbao Yang. Attentional biased stochastic gradient for imbalanced classification. arXiv preprint (..Xxx20022069955 2020a.
Qi Qi, Yan Yan, Zixuan Wu, Xiaoyu Wang, and Tianbao Yang. A simple and effective framework for pairwise deep metric learning. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVII 16, pp. 375-391. Springer, 2020b.
Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for a class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34, 2021.
Hassan Ratique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-concan min-max optimization: provable algorithms and applications machine learning. Optimization Methods and Software, pp. 1 1-35, 2021.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.0560 2019.
RT Rockafellar and RJB Wets. Variational analysis springer. MR149/362, 1998.
Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In International Conference on Machine Learning, pp. 9824 PMLR, 2021.

---

Under review as a conference paper at ICLR 2023
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems, 32:9134 9144, 2019.
Quoc Tran-Dinh, Deyi Liu, and Lam M Nguyen. Hybrid variance-reduced sgd algorithms for minimax problems with nonconvex-linear function. In NeurIPS, 2020.
Madeleine Udell, Karanveer Mohan, David Zeng. Jenny Hong. Steven Diamond, and Stephen Boyd. Convex optimization in julia. In 2014 First Workshop for High Performance Technical Computing in Dynamic Languages, pp. 18-28 28. IEEE, 2014.
Jie Wang, Rui Gao, and Yao Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109. /926,, 2021.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Progranming, 161(1-2): 419-449, 2017.
Yi Xu, Rong Jin, and Tianbao Yang. Non-asymptotic analysis of stochastic methods for non-smooth non-convex regularized problems. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. (630-2640, 2019.
Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual algorithms with faster convergence than ((IvVT) for problems without bilinear structure. arXiv preprint arXiv: 1904. /0/ 2019.
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for min-max optimization. In Conference on Neural Information Processing Systems, 2020.
Junyu Zhang and Lin Xiao. stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pp. 9075-9085, 2019.
Zhe Zhang and Guanghui Lan. Optimal algorithms for convex nested stochastic composite optimiza- tion. ArXiv e-prints, arXiv:2011.10072 2021.
Yi Zhou, Zhe Wang, Kaiyi Ji, Yingbin Liang, and Vahid Tarokh. Momentum schemes with stochastic variance reduction for nonconvex composite optimization. arXiv preprint arXiv:1902.02775. 2019.
Dixian Zhu, Zhe Li, Xiaoyu Wang, Boqing Gong, and Tianbao Yang. robust zero-sum game framework for pool-based active learning. In The 22nd international conference on artificial intelligence and statistics, pp. 517-526. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
A
MORE RELATED WORK
Wang et al. (2021) studies the Sinkhorn distance constraint, variant of Wasserstein distance based on entropic regularization. An efficient batch gradient descent with a bisection search algorithm has been proposed to obtain near-optimal solution with an arbitrarily small sub-optimality gap. However, no non-asymptotic convergence results are established in their paper. [uchi & Namkoong (2021) developed convex DRO framework with f-divergence constraints improve model robustness. The author developed the finite-sample minimax upper and lower bounds and the non non-asynn asymptotic convergence rate of (1/ vn), and provided the empirical studies on real distributional shifts tasks with existing interior point solver (Udell et al. 2014) and gradient descent with backtracking Armijo line-searches (Boyd al. 2004). However, stochastic algorithms that directly optimize the considered constrained DRO with non-asymptotic convergence rates are provided in their paper.
Compositional Functions and DRO. The connection between compositional functions and DRO formulations have been observed and leveraged in the literature. [entcheva et al. (0177) studied the statistical estimation of compositional functionals with upplications estimating conditional- value-at-riss, measures, which is closely related to the CVaR constrained DRO. However, they do not consider stochastic optimization algorithms. To the best of our knowledge, Qi et al. (202T) was the first to use stochastic compositional optimization algorithms to solve KLL-regularized DRO problems. Our work is different that we solve KL-constrained DRO problems, which more challenging than KL-regularized DRO problems. The benefits of using compositional optimization for solving DRO include (i) we do not need maintain and update a high dimensional dual variable as in the primal-dual methods (Rafique et al. [021]; (ii) do not need to worry about the batch size in
MLMC-based stochastic methods (Levy et al. 2020 Hu et al. 2021)
B MORE EXPERIMENTAL RESULTS
GPU Setting: All our results are conducted on Tesla V100.
Testing convergence curves are presented the Figure and for the convex and non-convex setting respectively.
CIFARIOST
CIPARIIC-ST
Figure 3: Testing accuracy (%) vs # of processed training samples for the convex setting. is fixed to 0.5 on CIFARIO-ST and CIFARI00-ST ST. and 0.1 on ImageNet-LT and INaturalist2018. The results are averaged over independent runs.
CIARIDSTT
CITARIC-ST
Naaralaabll
Figure 4: Testing accuracy (%) vs # of processed training samples for the non-conver setting, is fixed to 0.5 all datasets. The results averaged over 5 independent runs.
Sensitivity to p. We study the sensitivity of different methods to p. The results on CIFARIO-ST and CIFAR100-ST shown in Table 4 in the supplement, which demonstrates that the testing performance sensitive to p. However, our method SCDRO is better than basclines PG-SMD2 and FastDRO for different values of p.
13

---

Under review as a conference paper at ICLR 2023
Table 4: Test accuracy (%) of different methods for different constraint parameter p in the non-convex setting. The results are averaged over 5 independent runs.
0.01
0.05
0.1
0.5
PG-SMD2
67.09 0.59)
66.96 0.71)
67.12 0.61)
07.36 (# 0.36)
67 0.61)
CIFARIO-ST
FastDRO
65.41 0.33)
66.15
0.09)
66.24
0.63)
65.98 (+ 0.45)
65.68 (+ 0.52)
SCDRO
67.73 (# 0.39)
67.58 0.48)
67.71 0.43)
67.57 (1 0.28)
67.96 67.96 0.50)
PG-SMD2
57.31 (# 0.09)
56.44 (# 0.17)
55.85 (# 0.19)
52.68 (# 0.40)
48.72 (# 0.25)
CIFARIO0-ST
FastDRO
$7.60 0.32)
$7.20 0,42)
56.78 (1 0.40)
55.58 (1 0.62)
$2.39 (1 0.31)
SCDRO
57.84 0.15)
57.60 0.15)
58.32 (+ 0.43)
57.90 (+ 0.26)
57.71 (+ 0.24)
Comparison
Seconds
ORALEOO CIAR1D
innegeMeee44
Natuofiat/08
Figure 5: Running time comparison between PG-SMD2 and SCDRO
Per Iteration Cost report the per iteration cost between the non-convex primal-dual algorithm PG-SMD2 and SCDRO single Tesla V100 GPU in Figure It clear to that the primal-dual algorithm incurs significantly overhead time due to the updates dual variables. By comparing the large-scale datasets, ImageNet-LT and iNaturalist201. 8, with the medium datasets, CIFAR 10-ST and CIFAR100-1 the increased dataset size leads to amplified running time gap as the dual variables dependent the dataset size (n). For the largest INaturalist2018 dataset, SCDRO could save days of training time.
C PRELIMINARY LEMMAS
Lemma 6. For 1, fx(g) Allg(() + Ap Lsx cia--Lippchitr.cminuuoee continuous and L -smooth, where
Lu = Lsa =
Remark: g:(w, A) exp( (<((W) 2 as A Ao E IR and (,w) 2 0 in problem Thus
g(x) = Dn 1 Ii w, A) 2 1. Then by this lemma we have [[V[x(((x)]] S X and g
V Al[g(x1) 9xx2)] for x, X1, X2 X.
Proof. For any 2 1, we have
vfa(g) SA
And for any qn 02 2 1, we have
( 22)
(V)x())) - vfa(12))
5
> 4el
91
42
9192
This complete the proof.
Lemma 7. Let LA exp( (o 23
X C + L),, LB exp( exp( C ( + 3). Le expl CGGTo))))
and Ln = expl ()) C" g,(w, A) is Lg Lipschtz continuous and L -moooh in terms of (w, A), where Lg expl ( ( ) and Lv, = / + 13 + L3
14

---

Under review as a conference paper at ICLR 2023
Proof. The gradient of g:(w, A) is given
Vw, A) = (dw.gi (w, A)", (w, A))
(((W)
V Vwls(w)
(((w)
(((w)
exp
. -
A
1
A2
Then by Assumption
I we have
(((W)
(
V [w(((W)
(((w)
V w.A (w, A]] S exp
1
d
X2
AZAO
C
G
C
exp
Ao
Ag
Xg
Thus, Lgg exp (o)) ( G +
C x
For for all (w, A), (w', , X') E X, we have
V ASi (w, A) - V WwA.R(WW ,AO1
(<(w)
Vwl(w)
(((w'))
V Vwl((w))
V/
exp
texp
X
X
(i(w)
((())
(((w')
4:(w')
1?
+
exp
AL exp
X
X22
C (w))
V (wl((w) exp
(((w))
[wl((w))
2
exp
A
A
(((w')
Vwl((w") exp
(((w')
Vwl((w")
12
+
exp
A
X
N
(i(W))
(((w)
(2(w")
2 (,(w")
+
exp
exp
X
(s(w") À
Es
(ww')
(((w')
((('))
+
exp
exp
X2
X'
X
To bound the first term, we first check the Lipschitz continuous of exp( (((W) to w,
V ((()) with respect
1
exp
[s(w]
x
Ow
((())
V Vwe((w)
V Vwli(w)
(((W)
V ((w)
exp
+
exp
X
A
A
(0)
(((w)
Vwla
(wl)(w)
Vwll(W))
)
(s(w)
(el((w)
exp
+
exp
X
A
(6)
((())
[wli(w)
2
(((w))
[kle(w)
exp
+
+exp
exp
X
X
C No
G²
2 exp
+
LA-
Xg
Au
where equality (a) is due to the property of the norm of rank-one symmetric matrix and inequality (b) due to Cauchy-Schee Schwarz inequality.
Therefore, we have
(((W), Vwl((w) exp( ((w'), Vwl((w')) 2 S || 2'1?
exp( A
A
15

---

Under review as a conference paper at ICLR 2023
Furthermore, it holds that
0 exp
[((w) 2
(((W)
l (
V (w(((w)
(s(W) (
[ww((W)
exp
+ +exp
0x
A
13
X2
C'
CG
G
S
exp
+
= LB
A0
10
X
<.(w)
[w(] X
exp
(i(w)
(s(w) V Vv..i (w(((w)
(((WW Vwli(
exp
+exp
Ow
A
A3
X2
C
CG + AO
exp
= Lc
Ao
① exp
(((w))
{i(w) 2²
fi(w)
(?(w)
(w(w)
(w)
exp
11 + exp
02
A
A3
C
C + 2AOC
S
exp
LDD
Ao
As result, we obtain
|V Ww,Ade W, 2) V Ww.Agi(w',>())
S L' - -w'l + L3 1 -X11 + L3 |w-
w'12 ww'? LLD 1A 2
(I22 + [2) |w- w'12 + (I2 + L2)) y| -1133
(L3 + Li 1/g Lip) [( (wT,)) - -(w"T, (w','') 1x)
Thus LV, v L3 + D 1/ + D.
Lemma 8. F(w, A) is Lm-sohhhh, where LF = XΣz + 2Lg + rLv, +1+
Remark: Lemma 6 and Lemma & Simply that LNsa = Lsg S Ly, Lug S LF and Lp 2
Proof. For all x1 (wI, A1) TT X2 (2)) E X. and let d(x) (0, ,,, log(((x))) +
p)" E Rd+1, by expansion we have
[VF(X)) - VF(x2)1
+ -//))///dd))/////////////--dd-d)
< (o(x))))) - 104100)))))000000)110000)0000))-
(
+ (o(x))
(x(x)) -x()))
Noting the Lipschtiz con.htuoucuoiuuuuuuuuuuuuuuuuuuo of (z) and (Ir),, we obtain
[V((x) VF(x))
< (L Lg 1)1g(x1)) g(xx)l + [ ||
g g(x2) |A1 >eel + [Vx(x)) Vg(xe)]l
(a)
(Lv fs1
r.2 Lg)l[>1 X2ll + [| )ll|a >xll + Le Lv 1111 1111-88 -xll
< (Lv,,, Lg + 2L + L1,, LV Lv,)1xx X2
(9)
S (Ar 2Lg + محo + + -)((x - X2|1-
where the inequality (a) is due to g(x2) > and the inequality (b) is due to the upper bound of X.
Thus, I,r X13 2T. ÅL, + X.
16

---

Under review as a conference paper at ICLR 2023
C.I PROOF OF LEMMA ]
Proof. Recall the primal problem:
E pili(w) 1p,(p,//n)
IIX
Invoking dual variable A, we obtain the dual problem:
min max X PEA. ==1
[n)((w- A(D(p,
1/m) (MV,(w))>((())////) p) 1p, 1/m).
(9)
Set p (1/n,... ..... 1/ /n), which is Slater vector satisfying D(p, 1/n) p Applying Lemma
in (Nedić & Ozdaglar 2009), we have
|
p q Σ
p.li(w)
-
==1
Since the primal problem is concave in term p given w, have p* =q" q-" Therefore,
| <
p Σ pel((w)
Σ (,(((w) DD -
Enili pil((W)
1=1
1=1
(10)
where the last inequality is because [(((w) S for E W. Let X = A Ao, we have
min max As PE
p(li(w) M(D(p.1/m) pp) dop.
Section G will also show
1
(<(W)
min X
log
exp
+ A(p MP)).
i=1
propii By Eq. 100, we have the optimal solution of above optimization problem |X S | No S Ao p which complete the proof
D PROOFS IN SECTION
D.1 TECHNICAL LEMMAS
Lemma 9. Suppose Assumption
holds and ~ D and s are initialized with $1 = exp( (((2))
Then for every E -1, T} have
2T22
xx+1 - x,112
Billg(x++1) 8 1131 <
(1 ()))((x)) stll2
B B2022
Taking summation of Eillg sc+1l13 from 1 to T. we have
Σ Blllg(x)) - sx11 [(((x)) - s1ll
T
21.2
T
3 +
9
Σ
X - x 3To2 +
(11)
32
17

---

Under review as a conference paper at ICLR 2023
Proof. Note that 86-1 (1 B)st + (x1(1))1) and E(g(x++1) (xx+1))]=0 then by simple
expansion we have
[lll(((+1)) st+11²1]
[[[])(g(x(+1) 91 (x+++1)) + -1 (x)x))((x++1)) - st)
18|3219( (x(++)1) 9i (x++1))l I| + (1- (x+()( srl
+ (g( - (i(x () g(x(++1) - -s6)
= 11133 (x(+)))) gi (x++1) )l( + (1- (1)1)((((()++ g(x)) g(x)) - sx (12)
Invkoing Lemma
7 to Eq. 12
and recalling Assumption 2 we obtain
Eillo (x(+1)
Sc+1
F (x++1) 9: (x )1 B) (x))((x))) -
+ (1 + 3 ]1 l1 g(xx))1
IA
2 X1+1 x
E
8 (1g((x++1) - (x(41) 12 (11- (x))
- -sell
8
(1 (1)))))() 3x112 2T. Xx++ -xel12
E
+ B²202
B
where the inequality (a) is due to (a + b)2 < (1+ A) + (1 1/1 }))b², the inequality (b) is because of 91 11 } 3/ and the Lemma and the inequality (c) is from Assumption
IT
Lemma 10. Under Assumption run Algorithm
with nLF S 1/4, and then the output XR. of
Algorithm 7 satisfies
T
40L 2
2A
40L
Ex(dist(O, (x))))
1|z VF(x))|
+
(13)
T
T/T'
T
Proof. The proof of this lemma follow the proof of Theorem in (Xu et al.
2019
Recall the update of x is
X1-1 xxx(x; - 7p2t)
arg min (xx( + (21, x.) XER
2n ||x xel12)
then by Exercise 8.8 and Theorem 10.1 of (Rockafellar Wets 1998) we know
2t (x++1 - xx) d6x (x++1),
which implies that
(x(+++1) 2t (xx-1 x1) E VF (xx+1) 06x (x1+1) ÔF (x++1).
(14)
By the update of x,+1. we also have,
8x(xx+1)+ (z,, X,+1 xx) + 2n
||x+1 xel1? s 6x((x)).
Since Fxx) is smooth with parameter LF. then
F(x++1) & F(x,) + (VF();), Xx+1 - xx) + LF
2 ||++1 - xel12.
Combing the above two inequalities, get
(z+ VF(x:), Xx+1 xx) こタ (1/11 D)|lx++1 x F(x.) F(x++1).
18

---

Under review as a conference paper at ICLR 2023
That is
2 (1/n -
1
-xel2 F(x)) F(x(+1) - (z: VF(x,)) x(+1 xi)
F(x.) F(x++1) + + VF(x))]l + An)
- l|xt Xx+1ll?
1
where the last inequality uses Young's inequality (a. b) < ||a|2 + lbbl Then by rearranging the
above inequality and summing it across / -,,... , ,,, we have
T
LF
T
|x++1 xi112 S F(xi) F(XT+1)+
Σ
nl|a - VF(xx)]1
An
- F(()) inf F(x) +
Σ n1/zz VF(x;)11
XEX
1=1
<
nlZe VF(x)11?
(15)
t=1
By the same method used in the proof of Theorem 2 in Xu al. (2019), we have the following inequality,
24
Zt VF(x++1) + -x)1
x1)1
2
zz VF(x)]
1=1
(16)
3LF
+
2 +
X - x111?
1
Recalling nLe S 1 and combining Eq. 15) and Eq.
16 we obtain
1
22 VF(x++1) + -x x1)11
1
(0)
24
5LF
-
T
VF((O))))
|2l - |1(x)11 +
+
n1 + 1/1
Σ
11 |21
11
n
1/4 MLFF2
1=1
T - (I
24
+
+ 400 A + 40
12 VF
(17)
1=1
1=1
where inequality (a) is due to (2L + 2/r < She and inequality (b) is due to 174-1br/2 $
Recalling Eq. (14 and the output rule of Algorithm | we have
(0, S
T 1Iz--V((xn VF(x+1) (xx+1 11411-x,11 x;)11
1
1
(18)
Then by combining Eqs. (87 together we have the Lemma.
Lemma 11. Under Assumption /
2
run Algorithm 7 with S 41. /442012 I 1
4h. and then we
have
2BI 2
2E
VF(x)11
A
20L E(1g((x))) -1 24.L3,0²
Elll
VF(x))1
T
3T
T/T
3T
Proof.
To facilitate our proof statement, we define the following notations:
(x Fx(x)) (8wF(xx)T (OFF(x)) (V))) (/) +og(g(x:)) + +p)
(. (F(x)) = (V (1 +og(g((x))) + +p)
G(x,) = =Go,,(x)) GA (x1)) (V/2, VsA, log(st) + p)-
It is worth to notice that E F(x))) = Vx.)))
19

---

Under review as a conference paper at ICLR 2023
For every iteration t, by simple expansion we have
4 = |||| (xx:) - ze|l
= F - (1 -
- [E[II(1 ()(V(( - v[((x-1)) + (1- (1 (x-
(1-3)=)))---))) (VF(())) -3c(x))1
3)
3G((x))1
- -I]I 3) (VF(x,) VF(xx-1)) + (1 B) (VF(x 21-1) -2 1191
B
+ +B]I8( - G(x,)) + 3 (VF(x) FF(x)) 11
= - |) + (1 8) 3 |0 + B)
+ (), 23(1 () + 2 -)) ( D) + 23,
(a)
B[(1 - (1 100
- -2(1-1))84
B) + - - + (C, I)
where the equality (a) is due to E(V - vf(x-1), VF(x)) - vf(x)) = and B(z,-1-
(x(xx,)), (x.))) vx(x))) = 0.
By Young's inequality, we have (1 (A, B) $ 9),A B) $ -11411 + (1-9) |||?
2 (C, B) (1-9) B| C 23(1 (),,C) S (1- B) + 3 and
2
5) 3 112 Therefore, noting (1 </and1/B> 1, can obtain
1 s E[(1
1 + (1-
+
+ 2
3 11 + (1 - 3933 1 + (1- (1- ||B11
2
+ (1 1// +
4 11 + +5 + 2 |
$ E[( B
(19)
Thus recalling the defintion of G(x:), (x:)) Vx(x)) and applying the smoothness and Lipschitz continuity of fx and we have
C = F - G(x))|?
VV (xx - (sr (w.
+ [V/5% + log - (s
- log(s;))12
< (g/x 0 SIA Ow, 2 Sx, (o(x.))0xs V.x, (xx)0x((xx)))
+ 2 ( (x. log((:)))
2 ||s - (xxx))1 21|s - g(x))11
(6)
S 22, 9(xx))1
(20)
where the incquality (a) is due to log(g(x:)) - log(s:)) S |sc - -x(xx) since g(x:) 2 st 2 1 for all t = {1.... .'') by the definition and initialzation of g: (xt), St, and the inequality (6) is due to
L2 +1 Lz.
20

---

Under review as a conference paper at ICLR 2023
And by the similar method, also have
D = (VV (l1
V/V (() (o,, (w(
+ V (9( + log(g(x;)) + P VfA. (fxx(((x)))xx0xxx)) log(g(x;)) p|l
+ (
V
(g) (x)
< 1,,, [V)((;)
Vy. xx) - 7 - (x:)l
(21)
Thus combining the Eqs.
19
20
21 and applying Assumption we can obtain
2
||| 2 (1+
4
E[(l 3)||
)1 + [V VF(x
=53] - 2 // Fx(x)11
- - [[[1-8]|z--1 VF(x + 4 1 - x1-111 + ll(x) - sell 2/3 LZ00
3
Taking summation of B1]|24+1 (x [1=] from 1 T and invoking Lemma g we have
Billze VF(x))
BI Fx())) z1 11
4L
B[[| [|| xx|]] 10L Σ
- + 2,8 L +e|l]++255
A3
B1 (((,)
z1 21
4L
E X,41 x11
B²
+ 107,
[1x(x1)
81
2L
T
x 1 - x,|13
+ +,8702
2
8
B
Taking Eq. 15 into the above inequality, we have
Bi[lz xe V (x
Bill Fxx)) - 2
4L2
20L3,L2
7
T
E[| 2z - VF(x))) ))
+
+
A +
12
182
1/4 nT.F/2
[
81 11
+ 10L
+
0T
+ +2922
B
(2) E| V
21 21
4L
20L2 I
87
A + >
E Ellz VF(X))119)
82
[1llg(x1)
1
+ BTO
+ +28L3TT0
(0)
E| [|
FF(xx)
A
1
T
+
E
Elllz 31
8
2n
2
1=1
B[llg(x)) - 81
+ 10
+
+BT
+ ToT
(22)
3
where the inequality (a) is due nLF S 1/4 and the inequality (b) is due to 8(423 2003?13)m7
Rearranging terms and dividing I' on both sides of Eq. (22 we compelte the proof.
21

---

Under review as a conference paper at ICLR 2023
D.2 PROOF OF THEOREM 1
Proof. Since 1j
3
LF 2 and LF S Lg. it holds that S
1LF which satisfy
2017
ALF /42024
the assumptions of 1) in Lemma 10 and Lemma
Therefore, combining Lemma 10 and Lemmal 11
we have
(O (F(x)))²
2 + 40
2A
4
Billz
VF((x))
n/T
12
24
20L
R zt - VF(xx)]1
T/T
T
24E
2 VF(
|1
12A T/
311131
2A
20L3A
+
+
288
+
3T
3T
1/T
T
(23)
By the definition of 81 and Assumption 2 it holds that B|lss1 - g(x()) 1 - - -xx)))))))
(24)
Since S I Li and 2L, < Li, we have
E 2 (x )
(x)) VSA,
( - VV) 14 < (213/ + +21 )0² < 4L.00
-
(0)
vo(x1)12
(25)
where the inequality (a) is due to l|a b122 < 2|a|| + 2/
Combining Eqs. 23 24
25
we obtain
(0, OF X
xR))²
24F 21
12A [F(1)]11
2407. (llgxx
2A
201
288
+
+
3T
VTT
BT
T/T
T
9613,02
12A
240L3,02
2A
2013A
288L2 +
3T
T/T
3T
1/T T
96L3.02
240A12
528
40AL2
20 A
VT
VT
VT
VT
T
L2
2013.4
< (624o² 2 + 280A)
+
VT
This complete the proof.
E PROOFS IN SECTION 4.2
E. TECHNICAL LEMMAS
Lemma 12. Let = VfA (s:) + q where qi = (V..uv) u.) 9x, = = _0_,log(ss) + P) and
O E Rdd Let 12 = [|st g(x;) 112 IV: awg(x:)11 luu 0xg(x:)1 Under Assumption
run Algorithm 2 and then for every t E (1.... .. T) we have
2
VF(x))]1 < 11
22

---

Under review as a conference paper at ICLR 2023
Proof. By simple expansion, holds that
1z - VF(x))l
IVA, (((x) VIA. (s.vvell
+ VVA. (9(x))) - v. + log(g(xx)) - log(+))]1
(a)
fA. (g( (x,) - (s) vf - (f,
+ 2 (x1g(()) 11
21 V fx, (xxx)
(s)((s)) 2 sell
(26)
where the inequality (a) is because ||a + bl < 2| + b|1 and log(x) log(v)] S |r -
for all x, y 2
Applying the smoothness and Lipschitz continuity of ʃx and g. we obtain
| (... V (s.
- V Vfa (s).gl
< (g) -
s 22 || g(x)) /,, /1q Vg(x))]1 2l)g s3ll?.
(27)
Noting ||q. - Vg((,) = ||, - g xx) )12 Ur - Ox (x) 12 and combining Eqs.
26 27 we
have
12: VF(x:)11
S (4L2I 1x, + +2) g(x1))1 + 4L,,,, /,, |1q Vg((2))1?
< 4 |8: - -(xx))1 41 11/1 q: V)(xx)]1
(1|s (xx:)11= + live ~xwg(x))) )112 2 +lue 0xg(xx)1²).
This complete the proof.
Lemma 13. Under Assumption 7 run Algorithm and then for every 1 {1, (1....T)
T we have
E| [[|| || & (1 - 3,) 2 [2] + 8(1 - E|||x++1 - Xx +
Proof. Since 81+1 (9:(x++1) + (1 B) gx(x))), it holds that
B[[|st11 ((x+11]1
= (xllg(xx+11) + - (1-Bt) (xx)) s(x++1))1
< B[ll(1 B:)( (00e-g(x1)) + (g -((x+1)))) g(x(+1))
+ (1 3.)((i(x+1))) - (x.) - (g(x1+1) (x
= B[(1 - 3,)211se g(xx) - (9 (x(+1) - g(x(+1))
(28)
+ (1 - 3:) (x.(41)) - (x,) - (g( (0(x)41) -g(x))))111
where the last inequality is due to E(g:(x(+1) - g(x++1)) 0.
Noting El(g (x+41) - g: (xx+ (xx+1)) ((xx))) E[ll(g(x++1) g(()))1 and applying the
Lipschitz continuty of (x),,, we have
B[]lg((x++1) (x(++ - (g(x++1) (xx)))
[[](()(X*+1) - (xx+1))) (1(((x+1) - (xx (x.(x))1) - (x(x)(1), g(x(+1) - g(xx))l
((((()( - (x++1 ||1 (x(x(x++)) - (xx
< (x((()( - (x(e)))))
BlIxxxe x.
(29)
23

---

Under review as a conference paper at ICLR 2023
Combining Eqs. 28
29
and invoking the Lipschitz continuty of 9x(x), under Assumption 2 we have
B|||st+1 g(x++1)
< (1- B[] - [1
+ 2 - -
gi(xx+)))))))))))))))))))))))))) (0(xx+1) 9xx)))
< (1- - BBll|= s(xx)ll + 23 + - 3,)² L3 B[][((+++ - x.112].
(30)
In the same way, also have
E v-11 (x - (1 3,) B v. Owg( x 11 28/00 + +2(1 ,
Bi||x++1
x; xx|
(31)
BlJu++1 0xg(x++1) = - Bx) 2 - - axg(xx) (1 1 + - 8,) ,11xx++ - X2 1x|1% ||
(32)
Therefore, combining Eqs. (30
32
31
we obtain
B[||*++ [| < (1
E[
x 12 63,00² + 4 (L + L, x1+1 - -x x=13²)
< -1- [0][|>1113 [1 + 8(1 33) x x +63300,
where the last inequality applies (L + 12) - 2 This complete the proof.
Lemma 14. Under Assumption 1 and 2 for any a > 1, let
2/3
LF w max(2o (1))
and c
k4 + 130L4. Then with 17, (w+to2)173. Be
o²
enj and after running T iterations,
Algrithmm satisfies
E 2 11
4L4
n.lll
171
6c 0² + 64L7A
7o
TT
Proof. Since w 2 (1673,k)3, is easy to note that
T S no S
S
16L7
ALF
In addition,
3: = S sab <
+ 1300
1
14
256L
LZL
65
1
65
< 1.
22 256L.
128
14a²
2556L
128
With M)
(m+tre)) we obtain
1
1
(w+ +
(w
(w+1o2)2//3 102)2/3 (w + (t - 1)02)1/3 (0)
0²
7-
k
3k W + (t 1)02)2/3
(b)
02
σ²
22/302
S
3k(w / + to2)2/3
3k(w/2 + to 2
3k(w + 2/23
22/3
(e)
22/3
σ²
343 n/
12Lph3 < 7Lk3" Th.
where the inequality (a) uses the inequality (x + 2/3 1/3 < yz 2 2g², and the inequality (c) is due 7 ALF
the inequality (b) is due to
24

---

Under review as a conference paper at ICLR 2023
Noting 3t
oTii and 0 I (1 - Bi) S 1, by Lemma 13 we have
E| 24+1 [1a] E
7/-1
(1 3,)²
8(1 - L
|B|||=1||
6 00
[E| Xx+1 x,11
1/-
8(1 - L 8|||x1111 - xr|1
S (nr 11-11 201: x
+ 6c 2 0² +
6c 17:00²²02 + 8(1 - 3,) L?
S -2
|1
[|||x111 - x1
(33)
where the last inequality is due to 1
201p S
FLyb3 1/1 2(
14LFRT + 130T, S
x²
-6-0
Taking summation of Eq.
(33 from to T, we have
260L1
Σ
n 24
E
x
[|2]
E
[12]
T
6c
6c 0²
11
+
8L
Bi|xx++1 xx11
70
7/
7p
(34)
In the same way with Eq.
15
and 1/2
1/1 14 2
could also have
T
T
T
1 2mp L
2m L
X1-1 x2
X - x <
+
1/
12
VF(x))1
Anp
[=1
1=1
(35)
Noting 7h Lp S 1 and invoking Lemma
we obtain
1
4
B[[|x++1
x
(A +
VF((x))1
77
1
2m LF
T'
84 +
[=1
T 8A + 32L Σ
n
[rBil14111 1721.
(36)
Combining Eqs.
34 36
we have
EE ||
20 [|
T
4L4
7
E
x
+ Σ
6c + 64I2A.
(37)
t=1
This complete the proof.
E.2
PROOF OF THEOREM
Proof.
Noting the monotonity of n) and dividing
1/1-mLe/2 on both sides of Eq. (35) we have
1
|x++1 x, 1| <
1/4mmLA m m + m Σ Th Tz VF(x))]
(38)
1=1
By the same method used in the proof of Theorem 2 in Xu et al. (019)). have the following inequality,
2 (F((x)+) F(x.))
12 VF((++1) + _x, - x1+1)1
s 211z (x,-xx1))1 VF(x)]] +
17c
71
3LF
+ (2T7
nt || x,112.
25

---

Under review as a conference paper at ICLR 2023
Multiplying 7t both sides of the above inequality and taking summation from to T, we have
1 -(x+11- - x,)11
n z VF(x++1)++
1/1
(0)
T
T
2
nell - VF(xx))] + 24 + 5LF 1/4- LLF
1h + m Σ nellz - VF(x))1
-V(x)))
t=1
<
12
N/ [al|zz - VF(x)) 12A,
(39)
1=1
where inequality (a) is due (2L
<
bbe, inequality (b) is due MLLF and Y
1/4-m145/2 8.
Combining Eqs.
37 39 and invoking Lemma 12 we have
nellz Vx(x++1)
- (x1+1 x12
1
1/t
T Σ
$ 4
17 x
12A
1=1
sc 11
E|
11
< 12
Σ
Ge + +642,4
+ 12A
(40)
T/
Noting the monotonity of and dividing Typ on both sides of Eq.
40
we obtain
T
1
FX(x++)) + - -xx+1 - xt)112
1/t
[B|| x
111+=1++11 1|
T
64L2A
12A
< 12
66 ooo
(41)
T To
TTF
Thp
Tur
Tifr
t=1
Combining Eqs.
18
41 and noting Σi11 mr & Ollog T), we get the conclusion that
El å (xR)))
El|lz - VF(((+1) + (x++1 - -x:)111
T
1=1
E E 11
64L
124
12
+ Tur
66 6e?11000 02 +
+
Tipooo
Tnr
Tur
1=1
log T
0
72/3
This complete the proof.
F PROOFS IN SECTION 5
F.1 TECHNICAL LEMMAS
Lemma 15. ((w)) is convex for all i, we can show that F(w, A) is jointly convex in terms of (w,A). A).
Proof. We have
F(w, A) max D
pily (w) A
Σ pa log p) Aop.
G(w.A.p)
26

---

Under review as a conference paper at ICLR 2023
Since G(w, A, p) is jointly convex in terms of (w, A) for every fixed p. F(w, A) is jointly convex in terms of (w, A).
Lemma 16. Under Assumption run Algorithm with I ALe v 942012 I 61.p
1 and apply
SCDRO to the new objective F (x) by adding μxx, to (V (8:) wilh (x)) VSx, (8)) X (x)((x)) + (og(s)) + p) in Eq. o of Algorithm where I is a small constant to determined later. Without loss of the generality, we assume O S andd then we have
2E | 21
FF
A p nT
20L BOL (1g(())))))) - -1
R [1 [P(()))]
+
24
T
3T
BT
Proof.
To facilitate our proof statement, we define the following notations:
(x,( = (x(e) .x (xx)))
(V pow. ((x,
pd1)
(x.)
-V (oxx + ) +og(((x))))))))) mdee)
C
(Gww (xx) ( Gx (x)) (V pw7 (f..())) log(si) + p pde).
worth to notice that [x( (x,).
Since F(x) is Lm-smohhh, then we have (x) is -smooth, where L,,, = (LF + 14). Noting
LF 1 and μ I 2. obtain LF $ 2/4 Lp. For every iteration by simple expansion have
4. [|[]] V F2 (x:) 2e
V (x,) (1 - [G -
[1[[ (x;,,,, (F, + (01-3)VF,,C (x--1) 8)2z-1 (VF,(x.) 3xx((1
[E[][( ()(VF, (x.) (F,((x-1)) + +11 ()( 2
+ (1I1)((F,((x) - (x()))) 3 BVV (x.)))
[1[1[11 B) (VF, (x.) VF. + (1 - 3) (x - |1
+ +E|IS - -((x) + B (VF(x) F((x)) 11?.
The above inequality shows that the only difference between 7 in the proof of Lemma and 7, in the proof of Lemma i6 term A.
Therefore, by the same method used in the proof of Lemma have
T
E (x.()111
E V (x1) - 11
4T2
F.
20L2L2
71
( +
Billze (x.()x)))))
B
1B2
1/4
nT.
F,,
12
B[]lg(x1) - 11
100
3TO2)
2312T002
13
27

---

Under review as a conference paper at ICLR 2023
By LF, I 2 LF and nLF s LnL - 1/4, it holds that
Blllz (xx())
B|ll Fl 2111
201
81j
A 17
E Blllz V.P((x))))))
8
B2
B2
[x)lg(x1)
s1113]
+ 1
+ 18TT22
+ 233
3
Bl 11
(x1(11)11
An
T
+
Σ
Billz - (F)(Xx)1
8
21
2
1=1
[x)lg(x1)
- $1 +
+ 10L
STO²
+ +23L3TTO
(42)
where the last inequality is due to 8996 + 20L S -
Rearranging terms and dividing T on both sides of Eq. (42). we complete the proof of this Lemma.
Lemma 17. At the k-th stage of RASCDRO, let Bg = cgf and c = 512T. we have
Th
Tx + 6,3 64
Ell - (x,,(x))111
(43)
Tr
where 2/ (xx) infxe Fx(x).
Proof. Recall the definition of ||> and by the same proof of Lemma 12 we have
lz: VF
Xx
1 < 4 |1.
(44)
Denote x at kth-stage as x and by Lemma
13 at the stage in RASCDRO we have Bi|l 4 1 $ (1 3 =
6.3 8L 3x)) X1+1 x,|
$ (1 - 34 2 x 2 + 6
3xx (((-)
+ +8 Bx)² Σ 3e )(L)))))) || ||x x1
$ (1 - -3x) 11>1 1| + 6.
(45)
+ 81 Σ (1 20 1
- -x112
im1
Combining Eqs. 45
we obtain
To
E|[ b
(x.(x))
AT.3.T. T
Tx
E[1 - 11) - 636002+ +8L7 - 11,)11xe+11 - x
Tx t=1
1 T
81, - Bx)
Σ
Bkk)
2 24 11 0. +
Σ
8x 2 2 -x
Tx t=1
T
t=1 1=1
28

---

Under review as a conference paper at ICLR 2023
Noting
E/= The 1-1 (1 3x) < 1/Bk and invoking Eq. (38). have
Tx
E|[ 1 - VF (x.)111
t=1
B say
817 3x)
6,300²
B Xx+1 xx|1²]
Tx
E||| sap 121
+ 8L 3x)2
Th
+ 6,300²
E| + 77
El - V (xx())))1)1)
BxTh
3xT
1/4 - 7) 1F, /2
Bi1l x 121
GA (A
64L3,n1 Tv
+
63
+
+
2z (F+(()))
BxTT
BxTx
3xIx
1=1
where the last incquality is due to
S 8, (1 - 3x)² S 1, 1 + + - 2L3..
Invoking Bk = ctt and c = J7 to above inequality, we get the conclusion that
Th
| 1| + 6,
Blllz - (F,(())
Ta
F.2
PROOF OF LEMMA 3
Proof.
Since & (w) is convex for all i, by Lemma 15 we know F(x) convex. And thus by the definition of Fy (x) we have F (x) is strongly convex function. Then by strong convexity, we have
Fa(y) 2 (x(x) + (y x) 2
" lyy x X.V (Fμ(x)).
Then
inf F3 (x) > min F2 (x) T xx)+ 1 yly x
xEX
yEd
2 min F (x) + v (y x) H
2 y x
|v|
= Fx(x)
Vv E (x)
2/
Hence,
||v| 2μ
2 Fx(x) infxex Fy (x). .v (x),,)), which implies
OF,, 2 2p (P) - Fy (x.))
F.3 PROOF OF LEMMA 4
Proof. We use inductions to prove Eli - (x.()l S 4ez/4, B[lg(xx) - su|l2] S pes/ and B[F, (xx) inf (x)) Eg. Let's consider the first stage in the beginning.
XEX
Let E An, thus B[F, (x;) infxEx [x)] < c1- And can use a batch size of 4/ μed for initialization.to make sure [[]] V F2, (X1) 21 I pt1 [4s (xx1)
& pc1/4.
Suppose that [x[lg(xx-1) 8k- 1 S 1 B[l|2--1 V (x+-1)) < _ 1/4 and E[F,(x - infxex Fx(x)) < 6k-1
By setting Bk-1 min μck-1
38LL3 3812? }, 7h-1
min 1 1008L40= 100814 and Tx-1 maxf 1474567
1474561 }. it is easy to obtain that 77-11 S
29

---

Under review as a conference paper at ICLR 2023
Therefore, invoking Lemma 16 have
20
2k
F (xx) [?]]
Ta
Σ
Ell 11 (x.)(1))
Tk-1
E[2 Z
AI (x 11
ETA k- 1
8k-
+ 24 1.70²
Bk-1Tk- 1Tk
M k-
3k TT-
p66-11
ch-1
5L
+ -1
28k-12k-1
12-11
Without loss the generality, we consider the case pek- ucx-110² < 1. By definition have Bk-1 =
(Cx=17(384T2,02)) M6-1 pec- (46088..4)) and Th-1 1474561. o² / which im-
ply
P 384L2"
1
I and 243 1
PCk-1
B4-1Th-1
Th-17h-1
32
16
Then, LF 1, 1 < and 6x
c we have
B z [FA(xx)1111
ck
+
Puck-1
5p
PCk-1
LF
16
384LF
8
pACk-1
1CEk-1
5/ACK:
MCC-1
768
32
192
16
P.C.
j.C.
HIE
+
192
16
40
8
juCk
S
4
Next we need show B[]lg(xx)- < μex /4 under the assumption that [[[lg[[ 1) /44.
-
8K- 1|3]
By Lemma
9 we have
Ex]lg(x)) - =sx
Tk-1 Σ B(lg((x)) - []
E[llg(xx-1) 1) 11
2L Tv-1
B[l1x++1 - -xo1 + BB-10²
B T Tk-1
B
Th
1=1
2L2
Th-1
Elllz V (x.((x)))3) )
p
BlAy + + 77-11 1/4 Mk-1 LF,
7k-1
4,8 Th-1
Th-1
1=1
Br 10-
where A = Ff,(Xx-1) - infxex (x). With 1/(1/4 1F,1
< 8, Elllg(xx-1)
8k 1 2| < 1 1/4 and E(Fx(Xx-1) - infxex F2 (x) S 6k-1, holds that
16L n2 -16--1
+ 4L3 MER-1
[(]lg(xx)= 1x S p66
+ B 3k-102
285-1T
32 T
8
I L2ycc-
L-Jcck11
P.k
pC
384L2 2
288
36L F
1921
J.ck
2
30

---

Under review as a conference paper at ICLR 2023
Invoking Lemma 10 (k 1) stage (k >> 1) have
(0 OF,, (xx)))
2 + 40LF, nk
Tk-1
2E k-
F0LF, El k-
5
Blllz - (X,((x))1
T--1
7/6-
k
Tk-1
(2 F0LF, Th
1)
2ck-1 +
40LF cK-1
4
Tk-1
197
pee
192
8
147456I
- 2pcce:
where the second inequality is due to Le, m1--1 S (3/2)LF7h-- 1/1536.
Since Fú (xs) - (xx) and infxex Fx(x) = infxex Fx(x), applying Lemma we have
1 (0, (xx)) v
2
(x,) - inf (x)) < (x)) inf (x(x)) -
6k-
xEx
XEX
2/
2/
This complete the proof of this Lemma.
F.4 PROOF OF THEOREM 3
Proof. Invoking Lemma then after K (1lo2((11/e) stages, we have
(x inf (x)] S EK 2 =
61
xEX
Since Σ 2* (LLee) the overall oracle complexity is
4
4
Th +
36864o L1
Σ
+
1PEE
uEl
k=
3686402 L4
K
1
+
1:e
2
k=1
1
0
1126
F,5 PROOF OF COROLLARY
It is easy to note that (x) (x.)) (x.) < (xK) -nfx Fx(x), where x., arg min xEx F(x).
Therefore, if after K stages it holds that F[F, infxex F,(x)] S c/2 with an oracle complexity of 0(1 (1))))),
have [xF,((x))
(x.)] S c/2 i.e., [x(((x)) x||* | F(x.)
x||x. 11 //2 S c/2. By Assumption with | < (R² + +X2 we have
a)) W bounded by R, and then by setting μ = c/(2(R++X))
B[F(xk) - F(x.)] < 6 + (2(R2 + +X1)
< c
+ Sc
with an oracle complexity of O(1/e).
F.6 PROOF OF LEMMA 5
Proof. We use inductions to prove [[[] 1112 S mex/ 111/ and (xx) consider the first stage in the beginning.
inf F,(x)) S Eg. Let's
xEX
Let 6 AN.. thus F[FF, infxex (x)] E1. And we can use batch size of 48L7/ for
initialization to make sure ||| [| = E[||s] - g(x:) + ||v - axg(x)))1 2 + l - (xg(1))111 pc1/1613 167.
31

---

Under review as a conference paper at ICLR 2023
Suppose that 1 I pCk-1/16L3 and (x - infxxe Fu(x)] I ck-1. By
setting
Bk-1 min
, 7
= min VPEE-T
18132L3,01 1813214 } and Tk-1 =
768L3.2 768L3
14 1474561..2 1474561
m 1012
ME6-1
Then following the above Lemma
17 for k 2
Tk
1
B|||>1
Elllz - V.F((x)111)
4T.
T
2E
2
11
1.8L7BBIA 10
17
2
+ 12.3x-102
Bk-17k-1
1x-17x-
- pc6k-1
3. 1 + 12
+ 1 1
3x =T--
Without loss of the generality, we consider the case μ S By definition we have 3k-1 o 7
-
which imply
1
S
and 12 z
pé 64L2
Bk T-
96
M7 Th-
Then, noting Lr 2 1, < and c = C 122 we have
|| 1|
uEE
pEk-1
1
384L7
64L
69121
pEg
19217
32L
345617
Pack
1612
Then by Eq. (44). we have | (k: - 1) stage (k 1) we have
V (xx))2 - 41,31122211 I pex/4. Invoking Lemma 10 at
Bldist (0, (x
+ 40LF, 7k
Th-1
2 R- 1]
40Lr B
B[12: - (F,((x))1
Tk-1
T7K TT
Th. Tx-1
(2 40LF AK 2
26k-1
40L,F 6k-1
+
T
Tx-1
773μER
MER
F0LF.HER-1
768
2
73728L4
I 2jcck=
where the second inequality is due to LF, 1h S (3/2) S 1/3072.
Since (x,) S (x*) and infxex Fx(x) = infxEx Fx(x). applying Lemma 3 we have
1
24r
(xF) inf (x)] S (x+) inf xEX
[x(x)] - E(dist(O, (afistt,,F,, (x+)) <
xEX
2/4
2/
This complete the proof of this Lemma.
F.7
PROOF OF THEOREM 4
Proof. Invoking Lemma
then after K ((logg(e//e) stages, we have 6
E Fx((
inf (x)) < cK
2K-1 = c.
xEX
32

---

Under review as a conference paper at ICLR 2023
Since Σk=1 2 (1/cc,, the overall oracle complexity is
K
4812 uei
K
4812
Tk
o
Σ
max
1a12 (EEk
+
p.ck
A=1
2=
2t
11312//5 (/m=//mm)))>> ))
V2"
48L7
o
Σ max
Pi
pac
k=2
0
max
This complete the proof.
G DERIVATION OF THE COMPOSITIONAL FORMULATION
Recall the original KL-constrained DRO problem:
min WEW
max IDEA,..(PP. 1tp.1//p..........p./ //)55p) 1=1
Σ - (oo 1/m),
where A, (p Rd EE 1,0 S p 1). D(p, 1/n) is the KI. divergence and Ao is small positive constant.
In order to tackle this problem, let first consider the robust loss
D(p. Enl((w) AoD(p,./n))
And then we invoke the dual variable À to transform this primal problem to the following form
max min [nel(w)- - X(D(p.1/m) - p) - 1p, PmAn X20 t=1
Since this problem is concave in term of p given w, by strong duality theorem, we have
Σ pre((w) A(D(D, 1/n) p) - -
max min PE A20
1
Σ (il)(w) X(D(p, - p) - Do, 1/m).
min max A2O PEAn
1=1
Let X Ag. have
min max
Σ Emil(()) - ((D()) -p) - Dp. 1/n)
X20 PEA.. am
min max Σ Dids(ww- A(D(p, 1/m) - p) >op.
λ PEA, 1=1
Then the original problem is equivalent to the following problem
min min Max NEW XZ PEA,
pudi(w) - A(D(p, 1/n) p) - Aop,
Next we fix x (w A)T and derive an optimal solution pa (x) which depends on x and solves the inner maximization problem. We consider the following problem
Σ peli(w) + XD(P, 1/n).
min PEAP
which has the same optimal solution (x(x) with our problem.
There are three constraints handle, i.e., p: 0, Vi and p; 1, Vi and En P; the constraint pa 2 0 is enforced by the term p; log(p:), otherwise the above objective will become infinity. As result, the constraint P; < 1 is automatically satisfied due Σ P: and p; 2 Hence, only need to explicitly tackle the constraint Ei Pc 1. To this end, define the
Note that
33

---

Under review as a conference paper at ICLR 2023
following Lagrangian function
(x(P. -
Epll(w)+
logn + pt log(p;)
Σ pi 1),
where is the Lagrangian multiplier for the constraint Σ = 1. The optimal solutions satisfy the KKT conditions:
4 ww) + À (log(p) (x)) + 1) + 0 and Σ (x) =1
2=
From the first equation, can derive Pf (x) x (xp((((w)/A)) Due to the second equation, we can conclude that (x) Σ. exp(4, problem, have
(w)A) Plugging this optimal p*(w) into the inner maximization
(x)( - log n + Σ pf (w) log(p? (w)) A log
n Σ
(((w) A
))
exp
72
Therefore, we get the following equivalent problem to the original problem
& ((())
min min Alog
Σ
exp
+ Ap.
wEW AZAB
t=1
which is Eq. 22 in the paper.
34


Reviews:
[{"review_id": "ruYlM9JE4F", "reviewer": "Reviewer_E9G7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes new stochastic algorithms to solve both nonconvex and convex KL divergence constrained Distributionally Robust Optimization (DRO) problems. The proposed methods are dual-free, which means the per-iteration computational complexity is independent of sample size. By utilizing the recursive variance-reduced technique and stagewise step size scheme, optimal convergence rates are also established in both nonconvex and convex cases. Empirical results demonstrate both the effectiveness of the proposed methods and the privilege of the underlying model.", "summary_of_the_review": "I am confused about why there are both KL penalty and constraint in the problem setting. In addition, the author basically reformulates the minimax problem to a minimization problem by using convex conjugate, which does not require much technical effort.", "strength_and_weaknesses": "Strength:\nOverall, the paper is clear and well-organized. This work proposes four efficient dual-free algorithms to solve nonconvex and convex KL divergence constrained DRO problems. Optimal convergence rates are also established in both nonconvex and convex cases. The proposed ASCDRO and BASCDRO methods are the first optimal dual-free algorithms for the KL divergence constrained DRO problem.\n\nWeakness:\n1. It seems that there are both a Kullback-Leibler (KL) divergence constraint and a KL penalty. Is there a particular reason for doing this?\n\n2. The author claims primal-dual algorithms require maintaining and updating an O(n) dimensional vector for updating the dual variable. But I believe some stochastic primal-dual methods can take coordinate steps on the dual side and have per-iteration complexity O(d). Please correct me if I am wrong.\n\n3. In the convex part of Table 1, The complexity of Dual SGM is the same as the proposed method. Could the author discuss the advantage of their method compared to Dual SGM?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KO-wlJv-gX", "reviewer": "Reviewer_rwfs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to develop new stochastic algorithms for solving the popular KL-divergence-constrained distributionally robust optimization (DRO) problem for both non-convex and convex losses. The proposed method, SCDRO or its variants, establishes (near-)optimal oracle complexities for both convex and non-convex losses. Furthermore, the said complexities are independent of per-iterate sample and batch sizes. Empirical studies further validate the effectiveness of SCDRO variants.", "summary_of_the_review": "As indicated above, this work enjoys strength of good clarity and quality but suffer from potential weakness of limited technical novelty. My rating is based on this, barring further rebuttals and revisions from the authors.", "strength_and_weaknesses": "Strength\n\nI find this paper interesting and well-written. To me, the methodology behind SCDRO is highly innovative in deriving a primal-only formulation linked with existing compositional optimization works. The developed theory for SCDOR was designed for non-convex loss functions and further extended to convex loss functions, enjoying optimal complexities for finding $\\epsilon$-accurate solutions for both convex ($O(1/\\epsilon^2)$) and non-convex ($\\tilde{O}(1/\\epsilon^3)$) smooth loss functions $\\ell_i(\\mathbf{w})$. Both of these complexities are first in literature in the given settings.\n\n\nWeaknesses\n\nOn pp. 3 ending part, the authors essentially indicate that DRO with KL divergence regularization enjoys shown superior performance for distributional shift. End of pp. 1, \"They are either restricted to problems with no additional constraints on the dual variable p except for the simplex constraint (Qi et al., 2021; Jin et al., 2021), ...\" On pp. 13 middle part the authors indicate that Qi et al. (2021) firstly cast the KL-regularized DRO problems into stochastic compositional optimization. They also indicate the difference with this work that they \"solve KL-constrained DRO problems, which is more challenging than KL-regularized DRO problems.\"\n\nAs indicated in the paper, the hardness of their analyses lies on the non-smoothness of $F(\\mathbf{x})$ and the non-Lipschitzness of outer function in the given unbounded regime, which breaks the assumptions of stochastic compositional optimization theory, hindering the achievement of optimal complexities for both convex and non-convex loss functions. I am wondering if the said challenge bring essential new difficulties for this change? From the perspectives of Lagrangian's multiplier these two formulations are essentially the same. Can the authors bring more details on this comparison?\n\n\nMinor comments:\n\nPage 2, middle part, the authors said $f$ being \"monotone\" which can confuse readers since this work does not involve variational inequalities.\n\nPage 13, middle part, \"(i) we do not need to maintain and update ... (i) we do not need to worry ... \" the second (i) should be (ii).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IGq1Am-d44", "reviewer": "Reviewer_Z1u3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of constrained DRO, and proposed a dual-free algorithm for solving the robust optimization problem, and hence the per-iteration complexity is independent of the sample size. ", "summary_of_the_review": "The paper is well motivated and thoroughly discussed related literatures. The authors have made concrete contributions, especially developed a dual-free algorithm for the constrained DRO, which can be much cheaper to run especially in modern ML high dimensional regime. Although there are a few points that the paper can improve on, e.g. defining $F$ earlier in the paper to cause less confusion, and discuss about the total running time when $d$ is large in the experiment. I think the paper is still a good contribution to ML community and I would like to suggest accepting this paper.", "strength_and_weaknesses": "The algorithm for solving the constrained DRO doesn't use dual information and hence enjoys per-iteration complexity O(d). The algorithm also enjoys relatively good iteration complexiy. One drawback in the experiment is that, the per-iteration complexiy is the main improvement from this algorithm, but there is no running time comparison which would be more interesting. Also in Assumption 1 the smoothness assumption on $l$ is pretty strong.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DxtuKI6_nD", "reviewer": "Reviewer_p2MP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes and analyzes stochastic algorithms that apply to solve a specific distributional robust optimization problem. This problem, Eq. (1), is not a general formulation solved by the existing methods. The uncertainty set of Eq. (1) must be a KL-ball, and the KL constraint in Eq. (1) seems to be too deliberate. With the help of the particular form, the proposed method shows a better complexity independent of the sample size for convex and non-convex settings. ", "summary_of_the_review": "This target problem, Eq. (1), is not a general formulation solved by the existing methods. The uncertainty set of Eq. (1) must be a KL-ball. The KL regularization on $\\boldsymbol{p}$ is not a common regular term. Eq. (1) is not a generic objective function but a deliberate one. \nConsequently, the reviewer suggests \"marginally below the acceptance threshold\" as the recommendation.", "strength_and_weaknesses": "* **Strength**\n  - This paper is well-written and easy to follow.\n\n* **Weakness**\n  - This method is only applicable to solving problems with a particular form.  \n  - The KL regularization on $\\boldsymbol{p}$ is not a common regular term. Eq. (1) is not a generic objective function but a deliberate one. \n  - Computational complexity of the proposed method is not well portrayed in the experimental studies.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject