Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis
Authors: Jikai Jin
Bohang Zhang
Haiyang Wang
Liwei Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributionally robust optimization
non-convex optimization
first order methods

Abstract: Distributionally robust optimization (DRO) is a widely-used approach to learn models that are robust against distribution shift. Compared with the standard optimization setting, the objective function in DRO is more difficult to optimize, and most of the existing theoretical results make strong assumptions on the loss function. In this work we bridge the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective, we are able to provide non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth and has unbounded gradient noise. In particular, we prove that a special algorithm called the mini-batch normalized gradient descent with momentum, can find an $\epsilon$-first-order stationary point within $\mathcal O(\epsilon^{-4})$ gradient complexity. We also discuss the conditional value-at-risk (CVaR) setting, where we propose a penalized DRO objective based on a smoothed version of the CVaR that allows us to obtain a similar convergence guarantee. We finally verify our theoretical results in a number of tasks and find that the proposed algorithm can consistently achieve prominent acceleration.

Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis
Jikai Jin Bohang Zhang?* Haiyang Wang²
Liwei Wang2.3.41
Schooo of Mathematical Sciences, Peking University
Key Laboratory of Machine Perception, MOE, School of EECS, Peking University
Center Data Science, Peking University *Institute for Artificial Intelligence, Peking Unviersity
{jkjin, haangiihhhnoohhg)00ptttt edu.cn, vanghaiyangodatu. pku pku.edu. edu. en, wanglwdcis pku. edu.
Abstract
Distributionally robust optimization (DRO) is widely-used approach to learn models that are robust against distribution shift. Compared with the standard optimization setting, the objective function in DRO more difficult to optimize, and most of the existing theoretical results make strong assumptions on the loss function. In this work we bridge the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective, we are able to provide non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth and has unbounded gradient noise. particular, we prove that special algorithm called the mini-bate normalized gradient descent with momentum, can find e-first-order stationary point within O gradient complexity. We also discuss the conditional value- at-risk (CVaR) setting, where we propose a penalized DRO objective based on a smoothed version of the CVaR that allows us to obtain a similar convergence guarantee. We finally verify our theoretical results in number of tasks and find that the proposed algorithm can consistently achieve prominent accelcration.
Introduction
For a classical machine learning problem, the goal is typically to train a model over a training set that achieves good performance from the same distribution P. While such an assumption reasonable and simple for theoretical analysis, it is often not the case in real applications. For example, this setting may be improper when there is gap between training and test distribution (c.g. in domain adaptation tasks) [Zhang et al., 2021], when there is severe class imbalance in the training set [Sagawa et al., 2020], when fairness in minority groups is an important consideration [Hashimoto et al., 2018], or when the deployed model exposed to adversarial attacks [Sinha et al., 2018].
set, where both the training and the test set drawn
Distributionally robust optimization (DRO), as a popular approach to deal with the above situations, has attracted great interest for the machine learning research communities in recent years. In contrast to classic machine learning problems, for DRO it is desired that the trained model still has good performance under distribution shift. Specifically, DRO proposes to minimize the worst-case loss a set of probability distributions Q around P. This can be formulated as the following constrained optimization problem [Rahimian and Mehrotra. 2019, Shapiro, 2017]:
minimize
V (ax) == sup Egn [f(x;; E)]
QEU(P)
"qqual Contribution, alphabetical order. Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where z E X' is the parameter to be optimized, & is sample randomly drawn from distribution Q. and f(:; {) the loss function so that Eę~o [f(r;; {)] is the expected loss over distribution Q. The DRO objective V (xx) is therefore the worst-case loss when the distribution P is shifted to Q. The set (P) is called the uncertainty set and typically defined as
U(P) = {Q P) c
(2)
where d measures the distance between two probability distributions, and the positive number e corresponds to the magnitude of the uncertainty set.
Instead of imposing hard constrained uncertainty set, sometimes it is more preferred to use a soft penalty term, resulting in the penalized DRO problem [Sinha et al., 2018]:
minimize
V (x) :=
sup {lee-q [6(2; E) Ad(Q.
where À > 0 is the regularization coefficient.
There are many possible choices of d. A detailed discussion of different distance measures and their properties can be found in Rahimian and Mehrotra [2019]. In this paper we consider general class of distances called the ei-divergence, which a popular choice in DRO literature [Namkoong and Duchi, 2016, Shapiro, 2017]. Specifically, for non-negative convex function & such that (1) = 0 and two probability distributions P. Q such that Q absolutely continuous w.r.t. P, the -i-divergence between Q and P is defined as
dQ dP
d (Q, ==
dP.
which satisfies d) 2 0 and de = Pas.
The main focus of this paper is to study efficient first-order optimization algorithms for DRO problem (3) for non-convex losses {(x. E). While non-convex models (especially deep neural networks) have been extensively used in DRO setting (e.g. Sagawa al. [2020]), theoretical analysis about the convergence speed is still lacking. Most previous works (e.g. Levy et al. [2020]) assume the loss l(: E) is convex, and this case (3) is equivalent to convex optimization problem (see Section for details). Recently some works provide convergence rates of algorithms for non-convex losses in certain special cases, c.g. the divergence measure v is chosen as the conditional-value risk (CVaR) and the loss function has some nice structural properties [Soma and Yoshida, 2020, Kalogerias, 2020]. Gürbüzbalaban et al. [2020] considered a more general setting but only proved an asymptotic convergence result for non-convex DRO.
Compared with these works, we provide the first non-asymptotic analysis of optimization algorithms for DRO with general smooth non-convex losses É(x, {) and general vi-iivereence In this setting, there are two major difficulties we must encounter: (i) the DRO objective (xx) is non-convex and can become arbitrarily non-smooth, causing standard techniques in smooth non-convex optimization fail to provide a good convergence guarantee; (ii) the noise of the stochastic gradient of (xx) can be arbitrarily large and unbounded even if we assume the gradient of the inner loss l(x, {) has bounded variance. To tackle these challenges, we propose to optimize the DRO objective using mini-bated normalized SGD with momentum, and we are able to prove O complexity of this algorithm. The core technique here is to exploit the specific structure of T (x)). which shows that (i) the DRO objective satisfies generalized smoothness condition [Zhang al., 2020a,b] and (ii) the variance of the stochastic gradient can be bounded by the true gradient. This motivates us to adopt the special algorithm that combines gradient normalization and momentum techniques into SGD, by which both non-smoothness and unbounded noise can be tackled, finally resulting in an O(e complexity similar standard smooth non-convex optimization.
The above analysis applics to a broad class of divergence functions vb. We further discuss special cases when & has additional properties. In particular, to handle the CVaR case (a non-differentiable loss), we propose a divergence function which is a smoothed variant of CVaR and is further Lipschitz. In this case we show that convergence guarantee can be established using vanilla SGD, and an similar complexity bound holds.
We highlight that the algorithm and analysis in this paper are not limited to DRO setting, and are described the context a general class of optimization problem. Our analysis clearly demonstrates the effectiveness of gradient normalization and momentum techniques in optimizing ill-conditioned objective functions. We believe our result can shed light on why some popular optimizers, particular Adam [Kingma and Ba. 2015], often exhibit superior performance in real applications.

---

Contributions. We summarize our main results and contributions below. Let 1 be the conjugate function of 1a (see Definition 2.3). For non-convex optimization problems, since obtaining the global minima is NP-hard in general, this paper adopts the commonly used (relaxed) criteria: to find an
<-approximate first-order stationary point of the function (see Definition 2.5). We measure the complexity of optimization algorithms by the number of computations of the stochastic gradient V((r,&) to reach an e-stationary point.
Assuming that * is smooth and the loss fs Lipschitz and smooth (possibly non-convex or unbounded), we show in Section 3.2 that the mini-batch normalized momentum algorithm (cf. Algorithm 1) has complexity of ())
Assuming that u5* is further Lipschitz, in Section 3.4 we prove that vinilla SGD suffices to achieve the ( +) complexity. As a special case, we propose a new divergence which is a smoothed approximation of CVaR.
We conduct experiments to verify our theoretical results. We observe that our proposed methods significantly accelerate the optimization process, and also demonstrates superior test performance.
1.1 Related work
Constrained DRO and Penalized DRO. There are two existing formulations of the DRO problem:
the constrained DRO and the penalized DRO. The constrained DRO formulation (1) has been studied in number of works [Namkoong and Duchi, 2016, Shapiro, 2017, Duchi and Namkoong, 2018], while other works consider the penalty-based formulation (3) [Sinha et al., 2018, Levy et al., 2020]. From a I Lagrangian perspective, the formulations are equivalent; however, the dual objective of the constrained formulation is sometimes hard to solve as pointed out in [Namkoong and Duchi, 2016, Duchi and Namkoong, 2018) In this paper focus the penalty-based version and provide the first non-asymptotic analysis in the non-convex setting. Moreover, we do not make the assumption that the loss is bounded, assumed in Levy al. [2020] in the convex setting,
DRO with ei-divergence. v-divergence is one of the most common choices in DRO literature to measure the distance between probability distributions. It encompasses variety of popular functions such as KL-divergenne, -didiverge,ce, and the conditional--allueattriii (CVaR), etc. Table 1 gives detailed descriptions for these functions.
For CVaR, Namkoong and Duchi [2016] proposed a mirror-descent method which achieves O (VV)) regret. Levy et al. [2020] proposed a stochastic gradient- based method with optimal convergence rate in the convex setting. They also discussed an alternative approach based on the dual formulation which they call Dual SGM. the non-convex setting, Soma and Yoshida [2020] proposed a smoothed approximation of CVaR and obtain an (c--9) complexity. We contribute to this line of work by proposing a different divergence with similar behavior as CVaR and an O 41) complexity.
For x divergence, Hashimoto et al. [2018] considered a constrained formulation of DRO but did not provide theoretical guarantees. Levy al. [2020] proposed algorithms based on an multi-level Monte- Carlo stochastic gradient estimator, and provide convergence guarantees in the convex setting. In contrast, we consider general smooth non-convex loss function E and provide convergence guarantee for x divergence as special case of Corollary 3.6.
Non-smooth non-convex optimization. Conventional non-convex optimization typically focuses on smooth objective functions. For general smooth non-convex stochastic optimization, it is already known that the best possible gradient complexity for finding an e-approximate stationary point is ((--)) [Arjevani et al., 2019), which is achieved by SGD based algorithms [Ghadimi and Lan, 2013]. However, the optimization can be much harder for non-smooth non-convex objective functions, and there are limited results in this setting. Ruszezynski [2020] proposed stochastic gradient- method which converges a stationary point with probability one, under the assumption that the feasible region is bounded. For unconstrained optimization. Zhang et al. [2020c] showed that it is intractable to find an c-stationary point for some Lipschitz and Hadamard semi-differentiable function. When the function is weakly convex, Davis and Drusvyatskiy [2019] showed that the projected SGD converges to the stationary point of a Moreau envelope, and a recent work [Mai and Johansson, 2020] extended this result to SGD with momentum. In this paper, we show that for smooth non-convex loss DRO can be formulated as a non-smooth non-convex optimization problem, but the special property of the DRO objective makes it possible to find an e-stationary point within O complexity.
3

---

2 Preliminaries
2.1 Notations and Assumptions
Throughout this paper we use ||- to denote the l2- no-m in an Euclidean space R$ and use (.. to denote the standard inner product. For real number denote (t)+ max(t, 0). For a set C, denote (-) as the indicator function such that Ic(x) = 0 if x E C' and [c(x) = +oo otherwise. We first list some basic definitions in optimization literature, which will be frequently used this paper.
Definition 2.1. (Lipschitz continuity) A mapping f - + RT is G-Lipschitz continuous for any y,y X. [1] [wv)l G || yll-
Definition 2.2. (Smoothness) A function f: f x.- + R is L-smooth if is differentiable on X and the gradient f is L-Lipschitz continuous, i.e. [[) Vf(y))l S | for all x. X. We
say J is non-smooth if such L does not exist.
Definition 2.3. (Conjugate fincttion) For function & IR + R, the conjugate functiion di is defined as r (t) == supsER (st (²())).
Assumption 2.4. We make the following assumptions throughout the paper:
Given ç, the loss function {(x,E) G-Lipschitz continuous and L-smooth with respect to x:
1b is a valid divergence function, i.e, a non-negative convex function satisfying (11 = and (t) too for all t O. Furthermore the conjugate v/" is M-smooth.
We finally define the notion of e-stationary points for differentiable non-convex functions. Definition 2.5. (c-stationary point) For a differentiable functiooo f : X - R, a point x E X is said be first-order e-stationary if V f())] <.
2.2 Equivalent formulation of the DRO objective
The aim of this paper is find an e-stationary point of problem (3). However, the original formulation (3) involves max operation over distributions which makes optimization challenging. By duality
arguments we can show that the DRO objective (3) can be equivalently written as (see detailed derivations in [Levy et al., 2020, Section A.1.2
[((x;)) (((x;))1) +
V (x) = min XEE nE
(4)
Thus, to minimize (x) in (4), one can jointly minimize C(x, 11) == EE-P Adt [(x:8) +
over (z, 1)) X' x IR C R=+1, This can be seen as standard stochastic optimization problem. The remaining thing is to show one can find an e-stationary point of V/ (x) by optimizing L(z, n) instead. We first present a lemma that gives connection of the gradient of V (z) to the gradient of L(z, n)) Lemma 2.6. Under the Assumption 2.4, (x) is differentiable, and VV = V.Lla, n) for any 7) E arg mitly L(x,n')
Note that the 7) in Lemma 2.6 may not be unique but the values of V vzL(x,)) are all equal. Since (x) is differentiable, the c-stationary points are well-defined. We now prove that the problem of finding c-stationary point of (Ir) is equivalent to finding c-stationary point of a rescaled version of C(x,1 m)).
Theorem 2.7. Under the Assumption 2.4. if for some (z, n) the following holds: L(, m) GVV,C(o m)l I c, then x is an c-stationary point of (x)). Furthermore, define a rescaled function
[((;)) ( ( + +Gn
A(x 7) = C(x, GT)) = :=EE- >ap""
(5)
then |VL(,, m)ll S c/v2 implies that an c-stationary point of (xr).
The proof of Lemma 2.6 and Theorem 2.7 can be found in Appendix A. From the above theorem suffices to find an c-stationary point of [(x, 17) such that [[V[(,,))) 7/)l I (ignoring numerical constant V2). As result, we will mainly work with E. in subsequent analysis. The property of the objective function (5) heavily depends on v². We list some popular choices of y together with the corresponding o in Table 1. They serve as motivating examples of our subsequent analysis.

---

Table I: Some commonly used divergences and the corresponding conjugates.
Divergence
(t)
* (t)
)(11 1)2
1 1 (1 2)
K-L CVaR
tlog ++1
e¹
10.0- 1), E (0,1)
α (t)+
regulagllrd CVaR
To.. + fogt + 1, (0,1)
min(e', log
Cressie-Read
#httk--1 k(--1)
k
(k (1- 1) -1
3 Analysis of general non-convex DRO
In this section we will analyze the DRO problem with general smooth non-convex loss functions We first discuss the challenges appearing in our analysis, then show how to leverage the specific structure of the objective function in order to overcome these challenges. Specifically, we show that our proposed algorithm can achieve a non-asymptotic complexity of O( ((e-))
3.1 Challenges in non-convex DRO
standard result in optimization literature states that if the objective function is smooth and the stochastic gradient is unbiased and has bounded variance", then standard stochastic gradient descent (SGD) algorithms can provably find an e-first-order stationary point under O(e gradient complexity [Ghadimi and Lan, 2013J. Here the smoothness and bounded variance property are crucial for the convergence of SGD [Zhang et al., 2019]. However, we find that both assumptions are violated in non-convex DRO, even the inner loss { {) is smooth and the stochastic noise is bounded for both f(x, -) and vzl(x.)). :). We present counter example illustrate this point, in which we can gain some insight about the structure of the DRO objective.
Example 3.1. Consider the loss E(x; {) x² (1+
which a quadratic- like function with noise e. where ş is Rademacher variable drawn from {-1, with equal probabilities. Then straightforward calculation shows that the loss l has the following properties:
w=+1
(Smoothness) For any & (-1, (-1,+1) +11. l(x, E) is L-smooth with respect x for L 8;
(Bounded variance) For any x R, Eg (e(xx -2)) then follows that Varg [f(x, {)] < 4;
4r4 (*-+1)=
+ (*=+1) S 4. It
(Bounded variance for gradient) Similarly we can check that the gradient of l also has bounded variance. Moreover, the variance tends to zero when x + co.
Now consider the DRO where vp is chosen as the commonly used diveeregeee Fix = 1 and 7 0. Based on the expression of v/* (t) in Table 1, the DRO objective function (5) thus takes the
form 0: = x² (1
+ 1, which is quartic-like function. It follows that
((I,0:E) ((x*) for large and therefore Ō(x, 0; ) is not globally smooth:
veL(o,0:E) x3 + 2nt 2x + O(1) for large a and the stochastic gradient variance Var(V=L(x,,0 0: (aa)) which is unbounded globally.
As we can see from the above example, both the local smoothness and the gradient variance of strongly rely on the scale of æ. Indeed, in general non-convex DRO both the two quantities have positive correlation with the magnitude of f. As shown in Appendix B, if we make the additional assumption that f bounded by small constant, then the smoothness and gradient noise can be controlled in straightforward way, and we show that projected stochastic gradient method can be applied this setting. However, such bounded loss assumption is quite restrictive and not satisfactory.
'E V.l(x, val(x))] o² 2 for some and all z X where {(x) Ee-r((x,
5

---

3.2 Main results
In this section, we present the main theoretical result of this paper. All proofs can be founded in Appendix C. We make the following assumption on the noise of the stochastic loss:
Assumption 3.2. We assume that for all x E X, the stochastic loss has bounded variance, i.e. EgEp (f(x,E) ((x))² 2 o² where {(x) = (L,,)(
We now provide formal statements of the key properties mentioned above, which show that both the gradient variance and the local smoothness can be controlled in terms of the gradient norm.
Lemma 3.3. Under Assumptions 2.4 and 3.2, the gradient estimators of (5) satisfies the following property:
EgIIV((,, - Vā(x, m)1 11G2 8(G [VV[(,,))'' 1)1=)
(6)
Lemma 3.4. Under Assumption 2.4, for any pair of parameters (x,, 11) and (æ', ,'), we have the following property for the gradient of L:
[VL(x, Vā(z', .7)1 (K GIVV mII) [[ - 1 1.7-117 n')ll where K =
(7)
Note that (7) reduces to the standard notion of smoothness if the term 1 & 7))l is absent. Thus the inequality (7) can be seen generalized smoothness condition. Zhang et al. [2020b] for the first time proposed such generalized smoothness twice-differentiable functions a different form, and Zhang et al. [2020a] further gave a comprehensive analysis of algorithms for optimizing generalized smooth functions. However, all these works make strong assumptions on the gradient noise and can not be applied in our setting.
Instead, we propose use the mini-batch normalized SGD with momentum algorithm for non-convex DRO, shown in Algorithm 1. The algorithm has been theoretically analysed in [Cutkosky and Mehta, 2020] for optimizing standard smooth non-convex functions. Compared with Cutkosky and Mehta [2020], we use mini-batches in each iteration in order to ensure convergence in our setting.
Algorithm 1: Mini-batch Normalized SGD with Momentum
Input:
The objective function F(w). distribution P. initial point wo. initial momentum mo, learning rate 7, momentum factor 3, batch size S and total number of iterations T
for L 4-11 to T do
F( (w:-1) + 1 Di Diml
(F(W)-1,$E)) where (2 s are i.i.d. samples drawn from P (w;
3
m f- 8m,-1 +
17
w. + 1 [mm]
The following main theorem establishes convergence guarantee of Algorithm 1. We further provide sketch of proof in Section 3.3, where gain insights how normalization and momentum techniques help tackle the difficulties shown Lemmas 3.3 and 3.4.
Theorem 3.5. Suppose that F satisfies the following conditions:
(Generalized smoothness) |/ FWw)) (W(w))) S (Ko K.II wel holds for any Wi, w2:
(Gradient variance) The stochastic gradient F(w, {) is unbiased (VF(w)= Eg F E)) and satisfies Eg F(w, F F(c)l < [2
+ A2 for some I and A.
Let {we} be the sequence produced by Algorithm Then with a mini- size = ((T2) and a suitable choice of parameters " and for any small O Ommnn(Ks Ko/K,, need at most O (AKgA?c- gradient complexity to guarantee that we find an e-stationary point in expectation, i.e. -TD ((w)) < where = F(wo) inf F(w).
Substituting Lemmas 3.3 and 3.4 into Theorem 3.5 immediately yields the final result:

---

Corollary 3.6. Suppose the DRO problem (3) satisfies Assumptions 2.4 and 3.2. Using Algorithm I with constant batch size, the gradient complexity for finding an e-stationary point of L (z)
O (G² (M + 1) (X- MG² + L) (E)))=))))) A
Corollary 3.6 shows that Algorithm 1 finds an e-stationary point with complexity O(c=*), which is the same as standard smooth non-convex optimization. Also note that the bound in Theorem 3.5 does not depend on K and I as long as is sufficiently small. In other words, Algorithm 1 is well-adapted to the non-smoothness and unbounded noise in our setting. We also point out that although the batch size is chosen propositional to I the required number of iterations T is inversely propositional to r2, therefore the total number of stochastic gradient computations remains the same.
Finally, note that Theorem 3.5 is stated in general form and is not limited to DRO setting. It greatly extends the results in Zhang et al. [2020a,b] by relaxing their noise assumptions, and demonstrates the effectiveness of combining adaptive gradients with momentum for optimizing ill ill-conditioned objective functions. More importantly, our algorithm is to some extent similar to currently widely used optimizers in practice, e.g. Adam. We believe our result can shed light on why these optimizers often show superior performance in real applications.
3.3 Proof sketch of Theorem 3.5
Below we present our proof sketch, in which the motivation of using Algorithm will be clear. Similar to standard analysis in non-convex optimization, we first derive a descent inequality for functions satisfying the generalized smoothness:
Lemma 3.7. (Descent inequality) Let F(z) be function satisfying the generalized smoothness condition in Theorem 3.5. Then for any point x and direction z the following holds:
2( (VF (x) , - ((K + Ki [[V
The above lemma suggests that the algorithm should take a small step size when |[ is large in order decrease F. This the main motivation of considering normalized update. Indeed, after some careful calculation we can prove the following result:
Lemma 3.8. Consider the algorithm that starts at we and makes updates Wi-1 wt 7 Me41
where }m²} an arbitrary sequence of points. Define 8, == m (F(w,, be the estimation error. If 0(1/K)), then
F(w.)) F(w(+1) 2 (7 -11² ( [VF((a)] 1 _Kon² 21116e
which is 7 VF w. 27 - for small y. Therefore the objective function F(w) decreases if || 1/2 (w:)( i.c. small estimation error. However, 6, is related to the stochastic gradient noise which can be very large due to Lemma 3.3. This motivates us to the use the momentum technique for the choice of {m,} reduce the noise. Formally, let / be the momentum factor and define 8, F((:)) Fu:,), then using the recursive equation of momentum me in Algorithm 1 we can show that
1-1
1-1
6. = Σ
-V(
(1-
Σ T=0
8 (1 -3)
(10)
T=
The first term of the right hand side in (10) can be bounded using the generalized smoothness condition, and the core procedure is to bound the second term using a careful analysis of conditional expectation and the independence of noises {& (see Lemma C.9 in Appendix). Finally, the use of
mini- mini-batches of size @(T²), carefully chosen 3 and a small enough y ensure that ΣT= || <
E (EI]VF((w)) + (())) where 1/2. This guarantees that the right hand side of (9) is overall positive, and by taking summation over t in (9) we have that
F(wo)) F(WT) 2 (1 20)7
[VF(w)) )| - -OGTT
T
namely.
(V < 0
7T + +
T
Finally, for suitable choice of y can obtain the minimum gradient complexity bound on T.
7

---

3.4 Dealing with the CVaR case
Previous analysis applies to any divergence function db as long as v is smooth. This includes some popular choices such the x²-divergence, but not the CVaR. In the case of CVaR, o is not differentiable as shown in Table I, which is undesirable from an optimization viewpoint. In this section we introduce smoothed version of CVaR. The conjugate function of the smoothed CVaR is also smooth, so that the results in Section 3.2 can be directly applied in this setting.
For standard CVaR level a, (t) takes when t E [0. 1/a) and takes infinity otherwise. Instead, we consider the following smoothed version of CVaR:
t tlogt t + 1-at log 1-at t E [0.1/a| otherwise
sma (1)
(11)
It is easy to see that viamo is valid divergence. The corresponding conjugate function is
Ri (t) log(1 - a + exp(()))
(12)
O
The following propositions demonstrate that viam is indeed a smoothed approximation of CVaR.
Proposition 3.9. Fix O <. < 1. When À - 0+, the solution of the DRO problem for smoothed CVaR tends to the solution for the standard CVaR. Note that the solution of the standard CVaR does not depend on X.
Proposition 3.10. (t))
(t) is 1 a -Liischit and ia -smooth
Based on Proposition 3.10, we can then use Corollary 3.6 to obtain the gradient complexity (taking M = 1/4a).
Note that (t)))(()) is not only smooth but also Lipschitz. In this setting, we can in fact obtain stronger result than the general one provided in Corollary 3.6. Specifically, the gradient noise and smoothness of the objective function L(x, E) can be bounded, as shown in the following lemma:
Lemma 3.11. Suppose Assumption 2.4 holds. For smoothed CVaR, the DRO objective (5) satisfies
BIIV 1, 2a GG?
(13)
Moreover, ((x,1) 11) is K-smooth with K = L C
2
Equipped with the above lemma, we can obtain the following guarantee for smoothed CVaR, which shows that vanilla SGD suffices for convergence.
Theorem 3.12. Suppose that vp = 1/-2m0 and Assumption 2.4 holds. If we run SGD with properly
selected hyper-paramesd on the loss L(x, 17) then the gradient complexity of finding an c-stationary point of (x) is O (a-3>-1 + AL) where A = L(xo, 71) inf, (xr).
The above theorem shows a similar convergence rate compared with Corollary 3.6 in terms of e and G, and the dependency À is even better. Therefore the Lipschitz property of g/* is very useful, in that it is now possible to use simpler algorithm while achieving similar (or even better) bound.
4 Experiments
We perform two sets of experiments verify our theoretical results. In the first set of experiments, we consider the setting in Section 3.2, where the loss É(x; {) is highly non-convex and unbounded, and chosen to be the commonly used x² -dvveeeeeee such that conjugate is smooth. We will show that (i) the vanilla SGD algorithm cannot optimize this loss efficiently due to the non-smoothness of the DRO objective; (ii) by simply adopting the normalized momentum algorithm, the optimization process can be greatly accelerated. In the second set of experiments, we deal with the CVaR setting Section 3.4. We will show that by employing the smooth approximation of CVaR defined in (11) and (12), the optimization can be greatly accelerated.
8

---

0.05
SGD Mommenmetu
1.75
MGD+Momentum Normalized MMDmMmmmnu
Normalized SGD Momentum
1.25
0.03
1.00
0.75
0.02
0.25
0.00
0.00
50
100
150
200
20
40
60
80
100
(a) Regression for x² penalized DRO
(b) Classification for x² penalized DRO
CVaR
CVaR Smoothed CVaR
Smoothed
0.10
DRO abjoctive
0.08
1.0
0.06
0.04
0.5
0.0
50
100
150
200
20
100
epoch
epoch
(c) Regression smoothed CVaR
(d) Classification smoothed CVaR
Figure 1: Training curve of x2 penalized DRO and smoothed CVaR in regression and classification task.
4.1 Experimental settings
Tasks. We consider two tasks: the classification task and the regression task. While classification more common in machine learning, here we may also highlight the regression task, since recent studies show that DRO may be more suitable for non-classification problems in which the metric of interest is continuous as opposed to the 0-1 loss [Hu al., 2018, Levy et al., 2020].
Datasets. We choose the AFAD-Full dataset for regression and CIFAR-10 10 dataset for classification. AFAD-Full [Niu et al., 2016] is regression task to predict the age of human from the facial information, which contains more than 160K facial images and the corresponding age labels ranging from 15 to 75. Note that AFAD-Full is an imbalanced dataset where the ages of two thirds of the whole dataset are between 18 and 30. Following the experimental setting in [Chang et al., 2011, Chen al., 2013, Niu et al., 2016], we split the whole dataset into training a test set comprised of the remaining 20% data. CIFAR-10 10 dataset is a classification task consisting of 10 classes with 5000 images for each class. To demonstrate the effectiveness of our method in DRO setting, we adopt the setting in Chou et al. [2020] to construct an imbalanced CIFAR-10 by randomly sampling each category at different ratio. See Appendix for more details.
comprised of 80% data and
Model. For all experiments in this paper, we use the standard ResNet- 18 model in [He et al., 2016]. The output has 10 logits for CIFAR-10 classification task, and has single logit for regression.
Training details. We choose the penalty coefficient
0.1 and the CVaR coefficient a 0.02 in all experiments. For each algorithm, we tune the learning rate byper-parameter from grid search and pick the one that achieves the fastest optimization speed. The momentum factor is taken 0.9 in all experiments, and the mini-batch size is chosen to be 128. We train the model for 100 epochs on CIFAR-10 dataset and 200 epochs on AFAD-Full dataset. Other training details can be found in Appendix E.
4.2 Experimental results
Results are demonstrated in Figure For each figure, we plot the value of the DRO objective (x)
through the training process. Here we calculate (xx)) min, L(x,, 11) at each epoch based on convex optimization on 7 until convergence (rather than using L(x, 1) with the current parameter directly).

---

Experimental result for x2 penalized DRO. Figure I(a) and Figure 1(b) plot the training curve of the DRO objective using different algorithms. It can seen that in both regression and classification, vanilla SGD converges slowly, and using normalized momentum algorithm significantly improves the convergence speed. For example, regression task SGD does not converge after 100 epochs while normalized momentum algorithm converges just after 25 epochs. These results highly consist with our theoretical findings, which shows that due to the non-smoothness the DRO loss, vanilla SGD may not be able to optimize the loss well; In contrast, normalized momentum utilizes the relationship between local smoothness and gradient magnitude, and achieves better performance.
Experimental result for smoothed CVaR. Figure 1(c) and Figure 1(d) plot the training curves for different training losses: CVaR and smoothed CVaR. Note that the evaluation metrics (y-axis) in these figures are all chosen to be CVaR, even when the training objective is smoothed CVaR. In this way we can make a fair comparison of optimization speed based on these training curves. Firstly, can be seen that the optimization of CVaR is very hard due to the non-smoothness, and the training curves have lots of spikes. In contrast, the optimization of smoothed CVaR much easier for both tasks, and the final loss is significantly lower. Such experimental results show the benefit of our proposed smoothed CVaR for optimization.
Test performance. We also measure the test performance of trained models to see whether a better optimizer can also improve test accuracy. Due to space limitation, in the main text we provide results of x2 penalized DRO problem for classification using unbalanced CIFAR- 10 dataset, which is listed in Table 2. Other results can found in Appendix E. can be seen that the model trained using normalized SGD with momentum achieves higher test accuracy on all class, and especially, the worst-performing class. Since the experiments in this paper is mainly designed to compare algorithms rather than to achieve best performance, better performance is likely to be reached if adjusting the hyper-parameters (e.g. X, the number of epochs, and the learning rate schedule).
Table 2:
Test performance of the x2 penalized DRO problem for unbalanced CIFAR- 10 classification. Each column corresponds to the performance of a particular class. The bolded column indicates the worst-performing class.
Class
3
4
6
9
10
Number of training samples
4020
2715
4985
2965
1950
1425
4795
4030
4835
3300
Test acc (SGD+Momentum)
76.7
80.1
70.2
55.0
54.6
44.8
84.9
77.7
85.5
76.8
Test acc (Normalized SGD+Mom.)
78.8
81.2
71.7
57.3
56.2
49.8
87.2
83.5
90.4
78.4
Discussion
Conclusion. In this paper we provide non-asymptotic analysis of first-order algorithms for the DRO problem with unbounded and non-convex loss. Specifically, we write the original DRO problem as a non-smooth non-convex optimization problem, and we propose an efficient normalization baased algorithm to solve it. The general result of Theorem 3.5 might be of independent value and is not limited to DRO setting. We hope that this work can also bring inspiration to the study of other non-smooth non-convex optimization problems.
Limitations. Despite the theoretical grounds and promising experimental justifications, there are some interesting questions that remain unexplored. Firstly, it may be possible to obtain better complexities on problem-dependent parameters, e.g. G and X. Secondly, while this paper mainly considers smooth v², in some cases sh* may be non-smooth (e.g. for KL-divergence) or even not continuous. In future we hope to discover approaches that can deal with more general classes of d--divergence Finally, we are looking forward to seeing more applications of DRO in real-world problems.
Acknowledgement
This work was supported by Key-Area Research and Development Program of Guangdong Province (No. 2019B 121 204008), National Key R&D Program of China (2018YFB I 402600), BJNSF (L.172037) and Beijing Academy of Artificial Intelligence. Project 2020B supported by PKU- Baidu Fund. Jikai Jin partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University.
10

---

References
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:1912.02365, 2019.
Kuang-Yu Yu Chang, Chu-Song Chen, and Yi-Ping Hung. Ordinal hyperplanes ranker with cost sensitivities for age estimation. In Proceedings of the IEEE conference on Computer Vision and Patter Recognition, 2011.
Ke Chen, Shaogang Gong, Tao Xiang, and Chen Change Loy. Cumulative attribute space for age and crowd density estimation. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, 2013.
Hsin-Ping Chou, mixup. In European Conference on Computer Vision, 2020.
Chang, Jia- Yu Pan, Wei Wei, and Da-Cheng Juan. Remix: Rebalanced
Frank H Clarke. Generalized gradients of lipschitz functionals. Advances in Mathematics, 40(1): 52-67, 1981.
Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. International Conference on Machine Learning. 2020.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 2019.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750 2018
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini- stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical P Programming, 2016.
Mert Gürbüzzalaban, Andrzej Ruszezyúski, and Landi Zhu. A stochastic subgradient method for distributionally robust non-convex learning. arXiv preprint arXiv:2006. 04873, 2020.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference Machine Learning, 2018.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, 2018
Dionysios S Kalogerias. Noisy linear convergence of stochastic gradient descent for cv@r statistical learning under polyak-ojasiewiczz conditions. arXiv preprint arXiv:20/2.07785, 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International
Conference on Learning Representations, 2015.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. In Conference on Neural Information Processing Systems, 2020.
Vien Mai and Mikael Johansson. Convergence of a stochastic gradient method with momentum for non-smooth non-convex optimization. In International Conference on Machine Learning, 2020.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Conference on Neural Information Processing Systems, 2016.
11

---

Zhenxing Niu, Mo Zhou, Le Wang. Xinbo Gao, and Gang Hua. Ordinal regression with multiple output enn for age estimation. In Proceedings of the IEEE conference on computer vision and paltern recognition, 2016.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review, arXiv preprint PrXiv:1908.056333 2019.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference Machine Learning, 2016.
Andrzej Ruszczynski. stochastic subgradient method for nonsmooth nonconvex multi-level composition optimization. arXiv preprint arXiv:2001.10669, 2020.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. International Conference on Learning Representations, 2020.
Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization, 27(4):2258-22 2275,
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
Tasuku Soma and Yuichi Yoshida. Statistical learning with conditional value at risk. arXiv preprint arXiv:2002.05826, 2020.
Bohang Zhang, Jikai Jin, Cong Fang. and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In Conference on Neural Information Processing Systems, 2020a.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why adam beats sgd for attention models. In International Conference on Learning Representations, 2019.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020b.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, 2020c.
Jingzhao Zhang, Aditya Krishna Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiv Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. In International Conference on Learning Representations 2021.
12


Reviews:
[{"review_id": "jQyw6vLH4BC", "reviewer": "Reviewer_u9sJ", "summary": "This paper bridges the gap by studying DRO algorithms for general smooth non-convex losses. By carefully exploiting the specific form of the DRO objective with $\\psi$ divergence, this paper provides non-asymptotic convergence guarantees even though the objective function is possibly non-convex, non-smooth, and has unbounded gradient noise. In particular, the authors prove that a special algorithm called mini-batch normalized gradient descent with momentum can find an $\\epsilon$-first-order stationary point within $O(\\epsilon^{-4})$ gradient complexity. Furthermore, for the conditional value-at-risk (CVaR) setting, this paper proposes a penalized DRO objective based on a smoothed version of the CVaR and obtains better complexity. The theoretical results are verified in several tasks, and the proposed algorithm can consistently achieve prominent acceleration.", "questions": "", "limitations": "", "rating": 8, "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": "Compared with the existing works, this paper provides the first non-asymptotic analysis of optimization algorithms for DRO with general smooth non-convex losses $\\ell(x,\\xi)$ and general $\\psi$-divergence. In this setting, there are two major difficulties : (i) the DRO objective $\\Psi(x)$ is non-convex and can become arbitrarily non-smooth, causing standard techniques in smooth non-convex optimization to fail to provide a good convergence guarantee; (ii) the noise of the stochastic gradient of $\\Psi(x)$ can be arbitrarily large and unbounded even if the gradient of the inner loss $\\ell(x,\\xi)$ is assumed to have bounded variance. Therefore, the core technique of this paper is to exploit the specific structure of $\\Psi(x)$, which shows that (i) the DRO objective satisfies a generalized smoothness condition [Zhang et al., 2020a,b] and (ii) the variance of the stochastic gradient can be bounded by the true gradient. This motivates the authors to adopt the special algorithm that combines gradient normalization and momentum techniques into SGD, by which both non-smoothness and unbounded noise can be tackled, finally resulting in an $O(\\epsilon^{-4})$ complexity similar to standard smooth non-convex optimization.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "9Yk03jazIOu", "reviewer": "Reviewer_uKhX", "summary": "The authors propose an algorithm that they call mini-batch normalized gradient descent with momentum. This algorithm can find an \\epislon-first-order stationary point under O(\\epsilon^{-4}) gradient complexity, even though the objective function is non-convex and non-smooth and has unbounded gradient noise. Their work is limited to where all loss functions are G−Lipschitz and L−smooth in x and conjugate function of a divergence function is M−smooth. Their main algorithm goes like: get a mini-batch gradient estimator (using mini-batch to ensure convergence) and update momentum using that estimator and update their variable w using normalized momentum. They presented two numerical results: one classification, the other regression. They compared their algorithm with vanilla SGD regarding convergence speed.", "questions": "", "limitations": "", "rating": 8, "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": "This is a high quality paper that appears to give the first non-asymptotic convergence results for DRO problems with general smooth *non-convex* losses and general divergence functions. The paper is well-written, clear, and the results (to the best of my knowledge) appear to be sound and mathematically correct. The contribution is clearly significant due to the importance of non-convex optimization and DRO. I have no major criticisms and am happy to see this paper accepted. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "9PHQ0WiajIp", "reviewer": "Reviewer_qgwb", "summary": "This paper studies the distributionally robust non-convex optimization for non-convex objectives. Authors provide a theorem for the convergence rate based on alternative assumption.", "questions": "", "limitations": "", "rating": 4, "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": "I would like to say that the paper is well-written and it is easy to follow; however, I have the following concerns:\n\n(1) In general optimization theory it is known that bounded gradient assumption does not hold in practice and it grows with the size of input unless the updating rule involves projection to a certain set to keep the size of gradient bounded. Therefore, I think the provided example 3.1 (while being insightful) is a known fact in optimization theory.\n\n(2) To deal with the issue (1) the reference [1] suggests the bounded variance assumption which is very similar to the assumption 3.2 in this paper. And using this assumption and careful choice of learning rate they can eliminate the effect of the growing norm of gradient. I believe this paper also follows the same approach and I found the results to be not surprising. \n\n[1]: Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. Siam Review, 60(2), 223-311.\n\nGiven (1) and (2) I am struggling to support the acceptance of this paper, and while having an interesting direction and problem in hand, I think authors can improve the results further.\n\nI also mention that I can be considered knowledgeable in optimization theory in general but I am totally new to the distributionally robust optimization area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the above comment!", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours more or less"}, "extra_text": {}}, {"review_id": "1GqNqYfEmve", "reviewer": "Reviewer_Fpn4", "summary": "This paper studies distributionally robust optimization with the loss function being nonconvex and the uncertainty set defined by a divergence function. Particularly, this paper gives a very interesting generalized smoothness condition, shows the connection of the normalized gradient descent with this smoothness condition, and gives a non-asymptotic convergence rate. Finally, experimental results verify the theory. ", "questions": "", "limitations": "", "rating": 7, "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": "I believe that this is a good paper in this area. Both the theoretical and experimental results are good. My main concern is that this paper can only address the soft constrained case. For the CVaR case or the hard constrained case, can we still apply the technique in this paper, such as the generalized smoothness condition? For instance, for the hard constrained case, we can get a similar reformulation about $(x,\\eta)$ and $\\lambda$ (see Namkoong & Duchi, 2016).  When $\\lambda$ is also changing, can the generalized smoothness condition still hold? \n\nThe O(\\epsilon^{-4}) may be further improved if we use some variance reduction approach based on SARAH/SPIDER. \n\nDoes the mini-batch setting really necessary? Can we only use one sample and get the same rate by decreasing the step size? \n\n\nSome minor comments: \n\n1. In Lemma 3.4, we may use $x', \\eta'$ to replace $x_2, \\eta_2$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides convergence guarantees for a stochastic method on a family of non-convex DRO problems, getting around the non-trivial challenge of lacking global smoothness and variance bounds. The reviewers appreciated the quality of the writing, relevance of the topic, and the technical novelty of the results, and from my own reading of the paper I received a similar impression. When revising the paper, please take care to thoroughly address the comments provided by the reviewer and myself. In particular, it is crucial to provide test performance of the model you train, in order to show that the problems and hyperparameters for which you solve DRO are such that it really provides an improvement in robustness.
Decision: Accept (Poster)