Revisiting Large-Scale Non-convex Distributionally Robust Optimization
Authors: Qi Zhang
Yi Zhou
Simon Khan
Ashley Prater-Bennette
Lixin Shen
Shaofeng Zou
Venue: ICLR 2025 Poster (2025)
Keywords: distributionally robust optimization
generalized smoothness
non-convex optimization
variance-reduced method
Primary area: optimization

Abstract: Distributionally robust optimization (DRO) is a powerful technique to train robust machine learning models that perform well under distribution shifts. Compared with empirical risk minimization (ERM), DRO optimizes the expected loss under the worst-case distribution in
an uncertainty set of distributions. This paper revisits the important problem of DRO with non-convex smooth loss functions. For this problem, Jin et al. (2021) showed that its dual problem is generalized $(L_0, L_1)$-smooth condition and gradient noise satisfies the affine variance condition, designed an algorithm of mini-batch normalized gradient descent with momentum, and proved its convergence and complexity.   In this paper, we show that the dual problem and the gradient noise satisfy simpler yet more precise partially generalized smoothness condition and partially affine variance condition by studying the optimization variable and dual variable separately, which further yields much simpler algorithm design and convergence analysis. We develop a double stochastic gradient descent with clipping (D-SGD-C) algorithm that converges to an $\epsilon$-stationary point with $\mathcal O(\epsilon^{-4})$ gradient complexity, which matches with results in Jin et al. (2021). Our algorithm does not need to use momentum, and the proof is much simpler, thanks to the more precise characterization of partially generalized smoothness and partially affine variance noise. We further design a variance-reduced method that achieves a lower gradient complexity of $\mathcal O(\epsilon^{-3})$. Our theoretical results and insights are further verified numerically on a number of tasks, and our algorithms outperform the existing DRO method (Jin et al., 2021).

Published as a conference paper at ICLR 2025
REVISITING LARGE-SCALE NON-CONVEX DISTRIBU- TIONALLY ROBUST OPTIMIZATION
Qi Zhang', Yi Simon Simon Khan', Ashley School of Electrical, Computer and Energy Engineering, Arizona State University' Department of Computer Science and Engineering, Texas A&M University"
Ashley Prater-Bennette' Lixin Shen' & Shaofeng Zou'
Information Directorate, Air Force Research Laboratory Department of Mathematics, Syracuse University"
{qzhan261, zou 2 @asu. edu, yi zhou wwwoouuttau.eeeeee 1sshe036syr.een (s (simon. khan, ashley, ceatter-benntteeeee wasssaf.nn af.mil
ABSTRACT
Distributionally robust optimization (DRO) is a powerful technique to train robust machine learning models that perform well under distribution shifts. Compared with empirical risk minimization (ERM), DRO optimizes the expected loss under the worst-case distribution in uncertainty set of distributions. This paper revis- its the important problem of DRO with non-convex smooth loss functions. For this problem, Jin al. (2021) showed that its dual problem is generalized (To, I-)- smooth condition and gradient noise satisfies the affine variance condition, de- signed an algorithm of mini-batch normalized gradient descent with momentum, and proved its convergence and complexity. In this paper, we show that the dual problem and the gradient noise satisfy simpler yet more precise partially gener- alized smoothness condition and partially affine variance condition by studying the optimization variable and dual variable separately, which further yields much simpler convergence analysis. We develop a double stochastic gradient descent with clipping (D-SGD-C) algorithm that converges to an e-stationary point with O(E=t) gradient complexity, which matches with results in Jin et al. (2021). Our proof is much simpler, thanks to the more precise charactcrization of partially generalized smoothness and partially affine variance noise. We further design a variance-reduced method that achieves a lower gradient complexity of ((c-²). Our theoretical results and insights are further verified numerically on number of tasks, and our algorithms outperform the existing DRO method (Jin et al. 2021)
INTRODUCTION
Empirical risk minimization (ERM) minimizes the expected loss under the empirical distribution Po of the training dataset with the goal of achieving good performance on a test dataset. Though this approach yields good performance in most cases, it often times fails due mismatch be- tween training and test data distributions, e.g., domain difference from training to testing in domain adaptation problems (Blitzer al.) 2006 Daume III Marcu 2006), imbalanced classes in the training dataset (Sagawa et al.) (2019) where performance of underrepresented minority groups is important due fairness considerations (Hashimoto al.) 2018 Grother et al. 2011;; and potential adversarial attacks to the deployed model (Goodfellow et al. 20.1 Sinha et al. 2017 Madry et al.) 2017]. For models trained using ERM, such distribution shifts will lead to significant performance degradation on test datasets.
To deal with the above challenge of potential distribution shift, distributionally robust optimization (DRO) was developed and has been widely studied in recent years (Ben-Tal et al. 2013 Shapiro 2017 Rahimian & Mehrotra 2019). Instead of merely optimizing the expectation of the loss func- tion under fixed distribution, DRO optimizes the performance over set of probability distri- butions, aiming at good model performance under potential distribution shifts. Specifically, DRO assumes the test distribution lies in uncertainty centered in the empirical distribution Po of the

---

Published as a conference paper at ICLR 2025
training dataset. Typically, the uncertainty set ((P)) is defined as follows:
u(P)) = D(Q)PP)) S p),
(I)
where D measures the distance between Q and Po. e.g., Kullback-Leite (KL) divergence, x² divergence or Wasserstein distance, and p is the radius of this uncertainty set. Then the goal of DRO is to optimize the expectation of the loss function under the worst-case distribution within the uncertainty set ((P)) (Rahimian & Mchrotra 2019, Shapiro 2017):
inf sup # QEi((T))
Es-o [c(x, S)];
where a: is the trainable model parameter, ((x, 5) is the loss function for the model with parameter
x and sample S. The formulation in equation 2 requires the optimized distribution Q strictly to be inside the uncertainty set (PP). which is relatively hard to solve. In practice, it is usually preferred
to use soft penalty term, resulting in the following penalized DRO problem (Levy et al. 2020 Jin
et al. 2021
Qi al. 2021 Sinha et al. 20177:
inf (x)) sup R [M S)] XD(
This removes the hard constraint on Q and controls the distance between the optimized distribution Q and training distribution Po by a regularizer. The hyperparameter À is pre-selected and fixed during the training.
The DRO problems with differrnnt types of uncertainty sets, i.e., D's, are fundamentally different. In this paper, we focus on a general class of distance: vi-divergence distance, which includes e.g., diveerggen and Cressie-Re Reas family divergence (Cressie & Read 1984 Van Erven & Harremos 2014). The di-divergence is widely studied in the DRO literature (Namkoong & Duchi 2016):
IQ
D(Q -
dPo.
(4)
dPo
where e is a non-negative convex function such that (1) = 0 and (t) = +oo for any t < O.
The penalized formulation of DRO shown in equation 3 is minimax optimization problem and is usually hard to solve. For di-divergence defined DRO problems, a popular approach to investigate its dual formulation. By strong duality (Levy et al. 22200] [Shapiro 2017), the solution of equation is equivalent to the solution of the following dual problem:
inf 1 (x) = inf L(x, m1) == EE ( ((s..)) 17
+ n7.
(5)
Z,ERR
where E R is a dual variable, 20" is the conjugate function of sb and is defined as (t) = supeER - (a)) In this paper, we study this dual formulation, which has the following three advantages compared with the previous penalized form shown in equation 3 (i) the objective is optimized under the known training distribution Po; (ii) it easy to get an unbiased estimate of the gradient of the objective to x since we do not need to take the supremum for Q; and (iii) it converts
a minimax problem to minimization problem, which is easier solve.
In this paper, we focus on the DRO problem in equation and equation with non-convex L-smooth loss function l (see Definition ( We consider the large-scale setting. where the training dataset consists of a large number of N samples. We aim to characterize the fundamental structure of this problem and develop efficient first-order algorithms with comprehensive convergence analysis.
The same problem was studied in Jin et al. (2021). It was shown that the dual objective in equation not T--smooth if the loss function not bounded. They further show that the corresponding dual ((x, v) satisfies the generalized smoothness condition (see Definition 3 where the Lipschitz constant grows linearly with the gradient norm [/Vannfil- Similarly, in the stochastic setting, they prove the variance of gradient estimate grows linearly with the gradient norm square (I,,, ie., affine variance noise (see discussion under Lemma 33.. To solve this problem, a normalized momentum method was used and shown to converge with O(e=t) gradient complexity. Note that algorithms and analyses for generalized smooth optimization problems, e.g., Adagrad and Adam (Li et al. 2023 Wang et al. 2023 Zhang al. 2024b), can also be used to solve this problem.
2

---

Published as a conference paper at ICLR 2025
However, solving the problem in equation as generalized (Lo, L1) -smoth optimization problem typically requires more involved convergence analysis.
In this paper, we answer the following question: Are generalized (Lo, L, smoothness and afline variance noise an overkill to characterize the dual [(x,, 1)) in equation 5
1.1
OUR CONTRIBUTIONS
Our main contributions are summarized as follows.
We prove that the dual objective of DRO problems in equation i partially generalized smooth (see Lemma [ and the noise satisfies a partially affine variance noise condition in the stochastic setting (see Lemma 3). The above
conditions provide a much more precise and fundamental characterization of the dual in equation [ than the generalized smoothness and affine variance noise derived in Din et al. (2021). Such precise character- ization yields much simpler convergence analysis. Our proposed more precise conditions circumvent the unbounded Lipschitz constant and unbounded noise variance challenges in the generalized (Lo, L1) -smoothness problems with affine variance noises. Our conditions first show the dual problem is standard L- L-mohhhh in the dual variable r) and the noise of gradient on has bounded variance. Then under our partially generalized smoothness and partially affine variance noise condition, the Lipschitz constant and noise variance on the model parameter are also bounded, making the objective easy to solve.
We show that in the deterministic setting, an algorithm as simple as gradient descent can solve the problem with iteration complexity of O(c-)): 3) and in the stochastic setting, algorithm as simple as double stochastic gradient descent with clipping (D-SGD-C) can solve the problem with gradient complexity of O(c-t). We further design double spider with clipping (D-Spider-C) algorithm and show its convergence with an improved O gradient complexity. Thanks to our more precise characterizations of partially generalized smooth and partially affine variance noise, our analyses are much simpler than those in Jin et al. (2021) and those for Spider algorithms (Chen al., [223)] Reisizadeh et al.) (023). which are developed merely for general generalized smooth problems with affine variance noise and are not tailored specially for DRO problems.
Our methods converge with computational complexities independent of the number of training samples N. and thus are applicable to large-scale training datasets.
Numerical results conducted to verify theoretical results. We observe that our pro- posed algorithms outperform the existing DRO method (Jin et al. 2021)
1.2
RELATED WORKS
DRO. Scalability: Many existing approaches are not scalable when the training dataset large. The method (Namkoong & Duchi 2016) is not feasible for large-scale problems, which parameterizes the unknown distribution by vector of dimension N and models the DRO problem minimax optimization problem. Following this method, many minimax methods such as Rafique et al. (2022);
Lin et al. (2020); Xu et al. (2023) can be used to address the DRO problem. However, a compu- tational complexity that is linear (or even worse) in the size of the training set is not preferable for large-scale problems. In this paper, our stochastic algorithms have a per-iteration complexity that independent of the training dataset.
Convex loss functions: Some existing methods (Duchi & Namkoong 2018 Levy et al. 2020 Wang et al. 2021 2024, Hashimoto et al.] (2018) require the loss function to be convex, which, however, fail to capture wide range of machine learning problems where the loss function is non-convex, e.g., neural networks. In this paper, focus the general non-convex smooth loss function.
Bounded loss functions: For the non-convex DRO problem, existing studies, e.g., Qi et al. 2201 2022); Zhang et al. (2024a); Soma & Yoshida (2020) require the loss function é to be bounded (or even more restricted assumptions). In this paper, we focus on non-convex smooth loss functions, which may potentially be unbounded.
Non-convex smooth loss functions: Jin et al. (222) is the first study for non-convex DRO problems with general vi-divergence defined uncertainty sets large-scale settings. By combining all trainable
3

---

Published as a conference paper at ICLR 2025
parameters together (ar, A), the authors prove that the dual objective shown in equation 5 generalized (Lu, L1) -smooth in 2. Then a gormalized-momente
method is designed and an c- stationary point is guaranteed with a computational complexity of O(e**), In this paper, we share the same setting with JJin et al. (202)) and we provide a simpler yet more precise characterization of the dual problem: partially generalized smoothness and partially affine variance noise. We show that a simple SGD type algorithm finds an e-stationary point with a complexity of OEe*)). Moreover, we design a Spider algorithm, reducing the complexity to O(E
Generalized (Lo, L >smoothness.. As Jin et al. (2021) pointed out, the non-convex DRO problem can be solved as generalized (Lo, -smoohh optimization problem, which, however, introduces unnecessary complications to theoretical analysis for the DRO problem in this paper. Nevertheless, we briefly review algorithms and analyses for generalized smooth optimization problems in the literature below. The generalized (To. -mm-oootts problem is first introduced in Zhang et al. (211)) where clipping method investigated. However, for the stochastic setting, the gradient estimation error is required to be bounded almost surely. In this paper, our method works for noise with partially affine variance (shown in Lemma
3), which is a much weaker condition and more cormalized-momentuum momentum (Jin et al., (021). Adagrad (Wang et al.) (023). and Adam (Li et al.] 2023) Zhang et al., (202bb) studied for generalized (Ta, L1)-smmothness problem, and they can also be used to solve the DRO problem in this paper. In our paper, we show that for the DRO problem, simple SGD can get the same stationary point with the same gradient complexity. To reduce the complexity. Spider (Fang et al. (2018) is studied for the generalized (Lo. Lsmooothesssss problem (Chen et al. [2023 Reisizadeh al. 2023). In this paper, based on our precise characterizations of partially generalized smoothness and partially affine variance noise, our proof is much simpler than Chen et al. (2023). Moreover, we show the gradient converges in expectation, which is stronger than the convergence with high probability in Reisizadeh et al. (2023).
precise characterization for this DRO problem. Modern methods such
2 PRELIMINARIES
Denote by sample in S and let Po be the empirical distribution of the N training samples (8; he1- In the large-scale setting studied in this paper, we assume the number of training samples N is extremely large. We use || to denote the Fuclidean norm and () to denote the standard dot product. Define a function (a)+ = max(a, 0). For a set C, le is an indicator function such that lc(a) = 0 if E C' and (a(a) +o otherwise. Let E Rd be the trainable parameters where is the dimension. The loss function is defined as l: Rd x S + R. For a differentiable function Rd + R, is c-stationary point if [ S c, where Vaf(z) is the gradient of f to x. For a random vector X, denote by E the expectation and V the sum of its element-vise variance, where V(X)= [[]] X [[[]][]] We further provide some definitions.
Definition 1 (Lipschitz continuous). A function f Rdd + R is called G-Lipschitz continuous if for any y, E R ff()) f(y] < G||z - vll, where G > 0 is some finite constant.
Definition 2 (Standard L-smotth). differentiable function f Rdd + R L-smooth if for any 2, E R4, |V (z) - V ff((v) - L|| - yIl, where L > 0 is some finite constant.
These two definitions cover a wide range of problems in optimization studies. Recently, gener- alized (Lo, In) -mmothheesss condition is proposed (Zhang et al. 2019 Chen et al. 2023 Li al. 2023). which is strictly weaker than the standard T-smoothness condition.
Definition 3 (Generalized (Lo, L smooth).. A differentiable function f Rd + R is generalized (Lo, -mooth for any z, y Rdd, we have that V=f(=)-Vxffll < L. y/l. where Lo, L1 > 0 are some finite constants.
Note that there are two version of the (Lo. L1) -mooothness, one requires that the inequality only applies to || yll < To (Zhang et al.] 2019) and one does not require that (Chen et al. (203)). In DRO setting, it can be proved that for the dual objective Jin et al. (2021), the mequality holds for any x, y E 1dd thus in this paper we follow the second definition.
In this paper, we focus on a non-convex and smooth loss function E. Assumption 1. For any sample s E S, the loss function f(2, s) G-Lipchhizz continuous and T-smooth in
4

---

Published as a conference paper at ICLR 2025
We further make the following assumption on the ei-divergence. Assumption 2. The conjugate function x/* of is M -smooth.
Assumption can be satisfied by wide range of di-divergences (see Table
Divergence
(t2
(t)
-1 [t + 2) KL-regularized CVaR 10.0-11 t #log(t) - 1,00 (0,1) min(e', (1 log(a)))
(t 1)
Cressie-Read
1 R(6-1)
KER
((k 1)
Table 1: Commonly used divergences with L-smooth conjugates.
The goal of this paper is to find an e-stationary point of the penalized DRO problem in equation 3 which minimax optimization problem and usually hard solve. For di-iivereence defined DRO problems, popular approach is to investigate its dual formulation. By strong duality (Levy et al. 2020, Shapiro 2017). we have that
(xx) = inf [(z, m) == AESwPO (e(x, - + y/
(6)
Under Assumptions D and
it can be shown that (xx is differentiable (Jin et al. 2021 l).
Define
[(z, 7) (iz, Gr)) Then V V2.nf(2, nl S e/ v/v2 implies that [V)(l) S (Jin et al.
2021
Thus, is equivalent find an e-stationary point of ((x,1).
MAIN RESULTS
3.1 PARTIALLY GENERALIZED SMOOTHNESS
Let = = (x) Approach in Jin et al. 2021 directly optimizes over z, where it was shown that L(z)
generalized (Lo, --m-smo in with Lo L + 2G2X-1 and L1 L/G. In the following, we provide a more precise characterization of C by separately studying x and 17.
Lemma (Partially generalized (Lo, L1, L2) smoothness). Under Assumptions and C(x, 7) is
(Lo, L1) --a-paatillly smooth in x and Ls-soooth in r7 such that for any x, x,x' E IR and 77, n' e R we
have that
[V VoL(a', m)1l s (Lo L() -011,
2'1,
tema (a)
V, -,,(x,, S Tal1 v/b
(8)
where Lg G GMM L and L2 G.M
The proof is available in Appendix A. Observe that C(x, is smooth in for any Thus, optimizing over 7) should not be hard as solving generalized smooth problem. Moreover, in equation 7 the Lipschitz constant in x (term (a)) is linear in the gradient to Vz, 1)). but does not depend on the gradient x: V.C(x,)) n.) Compared with the generalized (Lo. L1 -mmoohhessss used in Jin et al. (202T), Lemma I provides more precise characterization of L. Intuitively, due to the smoothness in 7) one can expect quick find of a point with bounded gradient to 1). Con- sequently, the Lipschitz constant in will also become bounded, which circumvents the unbounded Lipschitz constant challenges in generalized (Lo, L1) -smoothness problems and makes the objective easier to optimize.
Remark 1. This partially generalized (Lo, L1, L2) smoothness condition is weaker than the stan- dard L-smoothness condition but stronger than the generalized (Lo, s1)-smoothness condition.
3.2 DETERMINISTIC SETTING
To warm up, we first consider the deterministic setting. We first propose a double gradient descent (D-GD) algorithm, which updates æ and y alternatively (see Algorithm T). This is in contrast to
5

---

Published as a conference paper at ICLR 2025
the approach in Jiin al. (2021 where and 7 optimized jointly. The key idea is to leverage the standard L-smoothness property in to bound Vz 17), to reduce equation to a smooth condition, and then to bound (z)
Algorithm D-GD
Input: initialization To, No. step sizes az Sr, number of iterations T
1: 0
2: while -
do
3: M/+1 7t 04 V C(x,, nd)
4: 21+1 f- 2t 3e (rr, 7(+1)
5: { [++
6: end while
3.2.1 DOUBLE GRADIENT DESCENT (D-GD)
In this section, we choose constant step sizes at, 3r in Algorithm 1 the following theorem, we show that D-GD converges to an e-stationary point with iteration complexity of ((E-2). Theorem 1. Let H 2L2(E(20, no) infa,, ((x, and L' = Lo L LIVH. Set 0r." L Br
Lo T 2 8 maxx L2, L') ((zo.no)-ine inf.. Cla.n) For Algorithm [ we then have that
Cln, S 22.
The proof is available in Appendix A.2 One key step in the proof is the following descent lemma: Lemma 2 (Descent lemma). For the partially generalized (Lo: Lı, L22-smoothh function L(x, n) defined in Lemmal ?
we huve that for any x. x. R.d and IR,
Lo + L V C(x, 7)1 || 2'11?.
C(2', n) S ((x,n) (V)
(9)
2
The proof be found in Appendix A.3 In the proof, by setting 04 ts and using the standard La-ssmoohhness in 17, at each step we can show that L(xe, M(t1) I C(x,, Moreover, since is Lmooth in 17, we have that for any
- inf ((x,n)) s 2L ((x,n) inf L(x And. 2"
V Cxx m) < 2L2
()
(10)
of
which indicates that a bounded function value implies a bounded gradient of 17.
We then prove this by mathematical induction. It can be easily shown using equation that at 0, [,, me)l VH and (,,,, 1t+1)l I VH. By Lemmal I it can be shown that the Lipschitz constant at (Ie, 71+1) is upper bounded by L' Lo + LIVH. By setting 8, 1. we can show C(Ir+1, Mh++1 1) S [(x,, 1)) Thus at L + 1 we also have that V, 7++1) S H and V,, ( < /H. This further implies that the Lipschitz constant to x at (æ++1, 7/++2) +2) is upper bounded by L'. Therefore, by induction, along the training trajectory, the objective function C(x, is Lo-smooth in 17 and L'-smooth in We then convert the DRO problem to standard L-smooth optimization problem, which is much easier to address.
3.2.2 DOUBLE GRADIENT DESCENT WITH CLIPPING (D-GD-C)
Algorithm with fixed stepsizes straightforward and convenient to be employed in practice. How- ever, Theorem indicates that the computational complexity is linear in L'. In this section, we study Algorithm with an adaptive step size for the update of x, which we refer as Double Gradient Descent with Clipping (D-GD-C). In the following theorem, we provide the convergence guarantee:
Theorem 2. Set
04t
1 B
min 20.'t (lr,,,
T
>
((va. - inf. L(x,n) max(812, 16Ln) for Algorithm Fore L., we then have that
min
|V a. (((,
/2e.

---

Published as a conference paper at ICLR 2025
The detailed proof is available in Appendix A.4 Due to the adaptive design of Bt. the step size is small when the gradient to 7j is large. Thus the function value is decreasing and we can prove that for some & < T, az (V, m:))
me-1) ( O(e*).
using the analysis for generalized (Lo. --moootthh optimization, c.g. in Jin et al. (2021),
can be shown that V [(=]] < (c where of is adaptive step size and is function of [[V=[(=)]I- Thus, V/lVV.L(z)) is a function of | [ and it will need non-trivial ef- forts show that ||v](z)]| is bounded. In contrast, using our more precise partial (Lo, L1, L2)- smoothness characterization since a is constant and L is L2-smooth in 7), it can be shown that [V, Mc+1)] bounded. We then obtain lower bound on Sy: from [V, Tc=1) S E follows that 3 2h. which is a constant. Thus, one can easily prove V 7++1)l Ill is bounded if [el V (12,, M 1++1)ll is bounded. This implies e-stationary point.
V/lV==
3.3 STOCHASTIC SETTING
In the deterministic setting, the per-iteration gradient complexity is N, and therefore, the approach may not be scalable when N is large. In this section, we develop stochastic gradient algorithms that have per-iteration gradient complexity independent of the training dataset size N. For the loss function, we follow the most relaxed bounded variance assumption in the vi-divergence DRO literature (Jin et al. 2021):
Assumption (Bounded variance). For any x E Rdd and S Po. the variance of the loss function is bounded:
Eg Po. -
(11)
where a is constant and f(x) Es Dos-Polll00 ()].
We note that stronger assumptions bounded loss function, i.e. {(x, 3) 3)33))))) bounded for any 2;
are used in ei-divergence DRO literature (Qi et al. 2022 Levy et al. 20200 Zhang et al. (024a)) However, their approaches cannot be easily extended unbounded loss functions.
We then provide the following lemma to characterize the variance of the stochastic gradient of [(x, 7) to x and Define C(r, S) >up" (M( + Gnj.
Lemma 3 (Partially affine variance noise). Under Assumptions 7) E I, we have that
and for any x E Rd and
Vs [,L(,,, < Do + D1 (V, Va- (1r S D2
(12)
(13)
where Do = 8G2 + 100 202 D 8 and D2 = GPM2X-302
The proof is available in Appendix A.5 Note that Lemma provides much more precise charac-
terization of the stochastic gradient variance than the affine variance condition in equation 14 (Jin
al. 202T):
Vs-P, V (22 S)] S D + ,
(14)
where Dú, Dj are some positive constants. The affine variance condition in Jin et al. 2022 is challenging to analyze since L is (Lo, -mm-shhtt in z and [[)][ is non-trivial to bound. In contrast, our Lemma indicates that the stochastic gradient to 7 has a bounded variance, and the variance of the stochastic gradient to x is linear only in (V, Since the dual objective is standard Lm-smooth in r and the gradient noise has a bounded variance, we can easily bound (), and show the variance of the stochastic gradient to is also bounded.
3.3.1 DOUBLE STOCHASTIC GRADIENT DESCENT WITH CLIPPING (D-SGD-C)
In this section, we develop D D-SGD-C algorithm that updates and y alternatively (Algorithm 2) In the stochastic setting, we use a mini-batch of samples to estimate the gradient, and N,, N₂ are |8|
the batch sizes. For a mini-batch of samples B (g(0) /= denote by
( ((x, -Gn
) + +Gn
L(x, 11,
Σ
A13
[
X
1=1
7

---

Published as a conference paper at ICLR 2025
an estimate of C(x, 1),, where [B] is the batch size.
Algorithm 2 D-SGD-C
Input:
initialization (7), step sizes a4,, St. number of interactions T, batch sizes
N2
++0
2: while / < -
-1 do Draw N1 i.i.d. samples B1 from Po and compute gr <- Vif((11, M1. B1)
3:
4:
T++1 1tt 0zgr
5:
Draw N2 iid. samples B2 from Po and compute et + VzC(x,, M1t1, B2)
6:
24+1 <- 2t 3,4
7:
t +
8:
end while
The following theorem establishes the convergence and complexity of Algorithm
T, N1, N2 = 2) for Algorithm Theorem 3. Set a = zt. Sc = min( 21. Lo
We then
have that
min B
S 6c.
Exact expressions of T, .N,, N2 and the proof are available in Appendix A.6
Algorithm 2 we
choose adaptive 3, < -ool in order to bound the additional term of V,, 1) xx+ || term in Lemma [ introduced by partially generalized smoothness. The rest terms in the decent lemma are the same as standard L-smooth problems; thus, we can find some < T such that B[ O(²)). By the definition of Be it can be shown that Sel/vel12 2 <|l=ell 2Lg for any t. Thus can find some T such that [ I O(e).
Using this fact, we now show that E[]l,, v,L(I,, 14 < O(e). Based on Lemma and N2 = O(E-3) 3), we have that Vivll I ( +e (V,((((((,, Billu VzL(a,, (c(()) 7+41) I Bllluz V,L(E, 11+1
Moreover, VVlu... implying that B[[]ur VaC(a, 1++1)ll I Ol el V,,,(ae, M++1))). In Lemma 1 we show the dual objective is Ly- smooth in ny; thus, it is less challenging to bound V,, 7+1)).. ). We then can find some T such that V 11l < Bi[le, VzC(x, 7++1) + E[llvlll S O(e) and can complete the proof. We also provide Algorithm 4 which momentum method and does not require mini- batches (See Appendix A.11).
3.3.2 DOUBLE SPIDER WITH CLIPPING (D-SPIDER-C)
Theorem
3 indicates computational complexity of O(c-+) is required by D-SGD-C to find an e-stationary point of (x)) This complexity can be further improved by our following variance- reduced method (Algorithm 3). which call Double Spider with Clipping (D-Spider-CC.. In this method, we first compute our estimate of the gradient to (x) with large batch of samples with size of N2 (Ng). We then update our estimate with a small batch of samples with size of N2 (N4). For every iteration, we refresh our estimate with a large batch of samples with size of N1 (N3).
To analyze Algorithm v,C((x, s).
further develop the following property of gradients VaL(x, 1,8) and
Lemma 4. For any x. x' nn,n R and & S, V,L(o, 17, is Lagcontinuous in a::
VV, n. V, n, s) < Lellx z'll
(15)
and V. L(x, T, is La-continouus in qp
V C(x, n.
(f $ L217 7''.
(16)
The proof available in Appendix A.7 Lemma theoretically characterize how the update on x (or v7) changes the gradient to 7) (or x). We then provide the theorectical result.
8

---

Published as a conference paper at ICLR 2025
Algorithm 3 D-Spider-C
Input: initialization (o), step sizes att, Sr, epoch size q, number of iterations T, batch sizes
N2, N3, 44
1: while T - do
2: if mod q === then
3:
Draw N1 i..d. samples B1 from Po and compute Si Vn ne. B1)
4:
else
5:
Draw N₂ i..d. samples B2 from Po and compute gt - VyL(Fr, Me. B2) + -1-1
V
6:
end if
7:
1h++1
1/- 0: if mod q == then
8:
9:
Draw N3 i..d. samples B3 from Po and compute V VzL(zi, 1s11
10:
else
11:
Draw Na i.i.d samples B4 from Po and compute Te
[ 7t, Ba) + U--1
end if
13:
Fe++1 f- Et Be
++++1
15:
end while
Theorem 4. Set 1 Be min(
To Follor (): T, .1, N3 = O(c and N2, Na = O for
4Tg2
2T.0 20.0
Algorithm 3
We have that for some constant C₁
min Ell V 1+41) S C4c.
K<
The full version and its proof are available in Appendix A.8 From the result we can show that the total gradient complexity is - + - By choosing g O(e=1), we can reduce the total
gradient complexity from OEE to ((e-)) Compared with Algorithm 2 the biggest difference how we design our estimators It and Rather than using unbiased gradient estimators, Algo- rithm 3 introoduees momentum in the updates of 9r and Ut, which, however, leads to biased gradient estimates. The key challenge in our proof is to bound such bias (see the following lemma).
Lemma 5. Using the same parameters as in Theorem for any to T such that to mod 0. we have that
to
q22
tot--1
E
[(: - V, 0
q
+
q
(gi)²
(17)
N1
N2
N2
t=
1=1
2262
q²e²
l0+g-1
Σ
Bllly, - V.L(xr, M4 11
50
q
+
q
+
Σ
(g:)²
N3
N4
N₂
N
N₂
(18)
The full version and its proof can be found in Appendix update of gt. if mod * O, we can show that
A.9
The key idea is as follows. From the
Elig. V,,((Ee)))) [E((V, ne BB)
1, B2) V,,((1r-1,0-1
1--1)
- -V, [))
v,,
(19)
The first term in RHS of equation 19 corresponds to the variance of unbiased estimate of V, 7-1) - v,,(E,, m)) using N₂ samples. This term can further bounded by E[( ([ n,, B2) - V,r,,,,1,9 - 1I) which small due to our designed step sizes and Lemma This bounds the first term in RHS of equation 19 Then, applying equation 19 recursiveyy, we get the bound equation 17 This method applies to 2; too.
From the descent lemma and Lemma 2 similar to the previous proof in Theorem 3 can show that DD- -1 (g) [e] is bounded by the mean square errors of gt and 1 plus some constants.

---

Published as a conference paper at ICLR 2025
Using Lemma where the mean square errors upper bounded by a function of Et= I9a and ar = 12g" -. we can show that - [[())) 2 3, || is bounded by some constants. We then can show that for some t < T, [g) ) is bounded. Moreover, with [g)) bounded, we can further show the mean square errors Sr and ft are bounded. We then obtain an e-stationary point.
NUMERICAL RESULTS
In this section, we conduct numerical studies on set of regression tasks (Chen et al. 2023) on the life expectancy data | This dataset consists of N 2413 samples, where we select the first 2000 samples for training and the rest samples for testing. After removing redundant features, for the i-th sample in our dataset, we have input 2; E IR and output Y/i E I. The non-convex original loss function is set f(z, (24, 3/)) 1 (y: 2 z)² 0.1 2j=1 In(1 [zy]),, where (z1, D2 .... T31) is the trainable parameter. For the DRO model, is set to 0.01, and the initial value To is set to 0.1.
200
GD
SGD
175
Normalized
5.5
Normalized-SPIDER
Clipped GD
Nomalized-SGDDm
125
D-GD
5.0-
D-SPIDER-C
D-GD-C
D-SGD-C
4.5
75
50-
4.0
3.5
0-
10
0.0
0.5
lteration
Computation Complexity
Figure I: Deterministic setting.
Figure 2: Stochastic setting.
In Figure we provide the training curves with fine-tuned learning rate for the original GD, Nor- malized GD (Chen al. 2023). Clipped GD (Zhang et al. 2019) and our proposed D-GD, D-GD-C methods. The x-axis stands for the training iteration, and the y-axis stands for the DRO objective (x)). From the results of GD and D-GD Figure 1
show that updating and 1) alterna- tively has the same empirical performance compared with training them together. Our D-GD-C also has similar performance compared with other methods.
In Figure 2 we provide the training curves with fine-tuned learning rate for SGD, Normalized- SPIDER (Chnn al. 2023), Normalized-SGD with momentum (Jin et al. (02I) and our proposed D-SGD-C and D-SPIDER-C methods. Our D-SPIDER-C has similar performance compared with Normalized- -PIDEERR---RER and both our two algorithms outperform the SGD and Normalized-SGii with A0.10
momentum methods. The details can be found in Appendix A.10
5 CONCLUSION
In this paper, we revisit the DRO problem with non-convex smooth loss functions. Instead of solving this problem as a generalized (Lo, L1)ssooothtteeeee smmootheess problem, we first show that this DRO problem satisfies a simpler yet more precise partially generalized smoothness condition and partially general- ized affine noise condition. Under these conditions, our theoretical analyses are much simpler than existing studies. Our results provide new insights into the fundamental structure of DRO problems with non-convex loss functions, which could be useful for DRO problems beyond the one studied in this paper.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work of Q. Zhang and S. Zou was partially supported by NSF under Grant CCF-2438429, Y. Zhou's work was supported by the National Science Foundation under grants DMS-2134223 and ECCS-2237830 L. Shen's s work was supported by the National Science Foundation under grant DMS-2208385. This work also partially supported by AFRL VERP program.
REFERENCES
Krizhevsky Alex. Learning multiple layers of features from tiny images. https://www. cs. toronto. faaiirri/ttaannnn--uueeeeee-eeee
pdf. 2009.
Aharon Ben-Tal Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions optimization problems affected by uncertain probabilities. Management Sci- ence, 59(2):341-3577 2013.
John Blitzer, Ryan McDonald, and Fermando Pereira. Domain adaptation with structural correspon- dence learning. In Proceedings of the 2006 conference on empirical methods in natural language processing, pp. 120-128, 2006.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized nonconvex optimization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.02854 2023.
Noel Cressie and Timothy RC Read. Multinomial goodness-of-fit tests. Journal of the Royal Statis- tical Society Series B: Statistical Methodology, 46(3):440-464, 1984.
Hal Daume IIII and Daniel Marcu. Domain adaptation for statistical classifiers. Journal of artificial Intelligence research, 26: 101-126, 2006.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribution- ally robust optimization. arXiv preprint arXiv:/810.08850, 2018.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Proceedings of Advances in Neural Information Processing Systems, volume 31, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 2014.
Patrick J Grother, Patrick J Grother, P Jonathon Phillips, and George W Quinn. Report on the evaluation of 2D still-image face recognition algorithms. US Department of Commerce, National Institute of Standards and Technology, 2011.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In Proceedings of International Conference on Machine Learning. pp. 1929-1938 PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In Proceedings of Advances in Neural Information Pro- cessing Systems, volume 34, pp. 2771-2782 2021.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distribution- ally robust optimization. In Proceedings of Advances Neural Information Processing Systems, volume 33, pp. 8847-8860, 2020.
Haochuan Li. Ali Jadbabaie, and Alexander Rakhlin. Convergence of adam under relaxed assump- tions. arXiv preprini arXiv:2304 /3972, 2023.
11

---

Published as a conference paper at ICLR 2025
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave mini- max problems. In Proceedings of International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0600 2017.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Proceedings of Advances in neural information processing systems, volume 29, 2016.
Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for class of distribu- tionally robust optimization with non-convex objectives. In Proceedings of Advances in Neural Information Processing Systems, volume 34, pp. 10067-10080, 2021.
Qi Qi, Jiameng Lyu, Er Wei Bai, Tianbao Yang, et al. Stochastic constrained dro with complexity independent of sample size. arXiv preprint arXiv:2210.05740, 2022.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-conaat min-max
optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3):1087-1121, 2022.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.0566 2019.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303. 00883, 2023.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprini 19XXv::911..073/ 2019.
Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization, 27(4):2258-22755 2017. 2017.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Centifying some distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2017.
Tasuku Soma and Yuichi Yoshida. Statistical learning with conditional value at risk. arXiv preprint arXiv:2002.05882 2020.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theoor, 60(7):3797-382) 2014.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
Jie Wang, Rui Gao, and Yao Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109.1 1196,, 2021.
Jie Wang, Rui Gao, and Yao Xie. Regularization for adversarial robust learning. arXiv preprint 2008022408.09672, 2024.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcavy minimax problems. Math- ematical Programming, pp. 1-72, 2023.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint urXiv: 1881, 2019.
12

---

Published as a conference paper at ICLR 2025
Qi Zhang, Yi Zhou, Ashley Prater- Better-Bennette,, Lixin Shen, and Shaofeng Zou. Large-scale non- convex stochastic constrained distributionally robust optimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 8217-8225, 2024a.
Qi Zhang, Yi Zhou, and Shaofeng Zou. Convergence guarantees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance. arXiv preprint 0144434 2024b. b024b.
13

---

Published as a conference paper at ICLR 2025
A
APPENDIX
A.1 PROOF OF LEMMA T
Proof. Based the formulation in equation and the fact that L(x, m1) L(x,, Gn), we first have
that
VL(x, ()) = En (usty (Rc..) - Gn Ve(r,))
(((x,))
G G GEP, (wyy (1(x,,)- - Gn }
(20)
We first prove that the function VL(x,n) is L2-smooth in n. For any E R and n. E R, have that
V ,,,
V,,((,n7')
(6**) ((x,5) ((e,))-Gi))
[1x, S) ((z,S)-Gi) Gil
=G Bp
X ((x, 5) SGG Gn
X
(1sty
((xx (055)-Gh) Gn/
SGTEp
(1²*)
A
A
G2M 1n-111,
(21)
where the inequality is due to the Mssmoothness of the conjugate function. We further show the partially generalized smoothness in x. For any x, Rd and á R, first have
2 0. This is due to the fact that (1²*) is monotonically increasing and 0 S. no (v* y(a) S 1, where the details can be found in Proposition B.2 in Jin et al. (2021).
(ab*)) (((a' (((a",))-0 S
It then follows that
| C(x, 7)
VzL(2', .1)1
((x, 5) - Gn
(1 - Gt)
Ero
(w*
Ve(r, - -10
Ve(o', .)
X
((x,5) Gn
Ve(r, - -( ((x,5)- Gn)
Epb
Ve(d', S)
A
[(x,, 5) -Gn)
G1)
(((x' Gn)
+
Er
(
VE(x', - (4*))
Ve(2', .))
A
(wty' (8(x, S)
(
-
+ +GM G
SLIle
A || - x'll
A
I
G
S < (VV, m)1 + GG) GGM
G.M
À || - x'll
S(Lo + I, V [<,
(22)
where the second inequality is because that l(x, 8) is L-smooth and G-continuous in x for any S, and the conjugate function e is M-smooth, the third inequality due to the fact that f(a' ())
(w*)
> 0. and the fourth inequality is because that GEE, (15 (((.S))Gnn
V ((,, GG V, + G. This completes the proof.
A.2 PROOF OF THEOREM
Proof. Let Hl 2L2(C(ro no) inf L(x, and L' Lo LIVH. In the following, we show that under our selected step sizes, C(,, m+11) upper bounded by VH for by induction.
Base Case: for = 0, since L(x, n) La-smooth in n, from the descent lemma for standard L-smooth function can show that
La (as C(wo, no)) (23)
C( m)) S C(ro, no) - (V,, no). au V, C(au, nu)) +
2
14

---

Published as a conference paper at ICLR 2025
Since ag Ln
1. it follows that
1
(V,,(rn,, no))² & C(xu, no) ( 77)-
(24)
2L2
By Lemma 3.5 Li al.
2024). can be shown that
(V,[(xo.m)) m))² 2L2
[(ro, m)
inf ((xu:)) 2L2 [(xo, - inf ((x, 2.0
(25)
"
According to equation 24 and equation [,)((oo VH.
25
show that L( I L(xo, and
Inductive Step: Assume V Vx,((z=;+++1) S VII holds for sts v. In the following, we show that [ M+11)l VH holds for 1 1.
Due to the Lz-smoothness of [(x, 7)) and o₁ Le it can be shown that
L(z,, 1+41) & f(I,, n)) (V, V,,, an ((r, + La (a,V, ((r,,))))))))
(26)
2
and
2L (V,,((,,,))) s ((anm)) - ((E6))4))
(27)
hold for all 2 0. Based on Lemma we have that
[(r+11, M1+1) < <L( 7111) (Val(re Mt+1) Br C( 7--1))
Lo + L W M )) +
3 v L( Mt )|
< <L(2, M+11) - VV Cf M(41), B, [(x,,
+ Lo L1 V
holds for all 0 1... S... L', By setting Br Lo+LiVH t. it can further imply that
2T. VVL((,, m+11) C(x,, [(F441, 7641)
(28)
holds for all 0 1 d. By taking the sum of equation 27 from O l' + and equation 28 from t = 0 to t', we can show that
< t=
(V ((I,,))))))
IV
m+1)ll < C(1o, no)
2L2
27
By Lemma 3.5 Li al. 2024), follows that
((144154442) inf ((oe41.n)
<2L₂
<2La [(zo, inl L(x, H,
2.
which completes the inductive step. Since both the base case and the inductive step are proven, by the principle of mathematical induction, v,, Te41) < /H holds for any t 2 0. This further
implies that equation 28 holds for any 2 Then, we take the sum of equation 27 and equation 28 from /. = 0 to T - 1, and show that
m)) - L(xr, mr) 2T.) (Vv,L(E, + Laa (+1)) S max
< (T.
[(zo, 70) - -in L(x, mn),)) (29)
15

---

Published as a conference paper at ICLR 2025
Thus for T 8 3max(L L2, L') ((aa. mo)-mon)-nni C(a.n) can find some such that
(V,f(az, 11))2
m+11) S c²
(30)
4
Thus we have | VV 7 )l| 1 and V , n1)) S 2. Moreover, we can show that
V (,,, < ( ut) + V,,((x, M++1) V,,( Te)
<(1 + L2a,) V, 7/)) S,,,
(31)
where the second inequality is due to the standard Lsssmohthssss on This completes the proof.
A.3 PROOF OF LEMMA 2
Proof. From Taylor's Theorem, we have that
C( n) ((x,n)) S [V + + - "),,))a o' x).0.
(32)
It follows that
C(x', n1) -[(x, 11) - (V,[(z, 7), x - -x)
(V.L(x + 0(x' - =),,)) - VzL(x, 1), -x) x)
/ (In L. V,IV,,(0,, m)) 011' ==|2a00
Lo + L1 V, 7)1 ||= - 111
(33)
2
where the first incquality is due to the partially generalized smoothness condition and this completes the proof.
A.4 PROOF OF THROREM 2
Proof. Since C(x,n) is L2-smooth in n,, we have that
La C(x1,704) S [(x,, nd - (V, C(z,, m)) a (, + (ar V, n.))
2
For az t we have that
at (V (Vx,,(n,,))) ((x),))) L(xe, 1+11)
(34)
For the update of by Lemma 2 we have that
L(x 0++1) SC(r,, Tt- M--1) 1) - (VzL(wt, mh+1) 1,,3, V.VV&laa ml41))
Lo + Li V, 1(+1))
B V.L((. M
m++1)l 1|
(35)
2
For Br = min 1
2Lo
2L VL. (lx
S LotLil ((we from equation 35 it follows that
B, V C(x,, 11 C(x,, 1- C(x+41,7t+1
(36)
2
By taking the sum of equation 34 and equation from f = 0 T 1, 1, we then have that
T-
ax (V,
(V,L(zm
m))² 3t V <C(ro. no) - C(xr,
2
<L(xo, no) inf [(x, 17). 2.
(37)
16

---

Published as a conference paper at ICLR 2025
For T 2 (lao:no)-inff... ((a.)) max(8L2, 16Lo), can find some < T such that
a
B. V (e:t))l) = min
(38)
L2 2Lo
For this t, we have that
2
((V,,C(( 4h-²
which leads to v,, 2 and
V,, , ne) + V,,(2x,, M+t1) V v,f((r)
5(1 + V ma) Se.
(39)
Moreover, since ((t S - La we have that B min 2Ln 2L, (00 1 follows that
=
27.0"
1
2
| (x+1) - 2Lo 4
(40)
2Lo
which implies that ((z, S 5. This completes the proof.
A.5
PROOF OF LEMMA 3
Proof.
We first consider the variance of the gradient to 17. We first have that
Vs- (,,
=ESAP [V, - V (()()n)))
SspP B (V, (,,((a,"; S2))
(109)) ((x, Gm (
(1xx G17
27
G Es
x
SG 122x - S- S))
D2.
(41)
where the first inequality is due to the Mssmoothness in 1), S1, S2 are independent random variables with the same distribution Po and the last inequality is due Assumption 3 We then provide the proof for the variance of the gradient to x. Similarly, we have that
V s- L(x S)]
S V.L(a, S1) - (2
[(xz (4(a, ) 2 (0")
(V((z, V2(x,
Po
((1,, ((e))(le..))) Gm)
((x, ((x Gn) )) ||V((z S2)
(wa)
S1) Si) -Gn) ((x,,
<
2202M22
X <8(G² + [V, 12 D2) 2G 2 222
n)
(42)
where the second inequality is due to the G-continuous property of f, M-smoothness of ot* and Assumption 3 The third inequality is due to the fact that Es
((w Ciy ))
EsS,Poo (wty ((ix.S))CCn) )1) + V VS (vrry ((..s)) Gy ]. This completes the proof.
A
17

---

Published as a conference paper at ICLR 2025
A.6 FULL VERSION OF THEOREM 3 AND ITS PROOF
Theorem 5. Let a
21 3: min
2h0 Lollval|
and
361
Ser-
ting
T N
max(8L2,
4Lo)
b cla.n) N1 z max
e²
10D:400
Liz²²
N2
2
max
10DoL2 Lipe
5Dn
Da+4r" L2
La
and e² = 87L0 min
8L
aLo
we have that
min
E 2, m KT
7+11)ll I 6c.
Proof.
Since L(x, 1) is Ly-smooth in 7, we have that
[(a,, 7++1) (L(r,, ne) (V, n.) + L2 2 (ar9)))
<L(s, mt) (V (, n1) agge) + T.2 ((r,, n))) + (gc v, ne))
Taking the expectation on both sides of the above inequality, we can further show that
E[A(ae, <E([(xt, m:) - Ela.( [V
+ EEaaa L2 m))² (gt V,, ne))
(43)
since de is unbiased estimate of v,,( m.). According Lemma for any y O, have that
Lo + I,IV, 1011) ||
C(1 M++1) SC(2,, Mc+1) ( ) Brer)
2
<L(z,, M1+1) Lo + L1 v m)) + L1 augel ||3;ve112 +
Br
<l(es, 11+1)
(1|vel1 + | L M 1))2 - Ilul - V V.L(r. 1)1
2
Lu + (L1 + L2
V -( m.)1 + L, L2adle V C(x,, (1)) 1e
+
2
<L(x,, 71+1) 2/1
Br +
-
Be
V
Lo 38
2
2
+T(Li + L2ar) (2V, 11))
||
167
.1
+ (22
v, m)))
||02|1
(44)
167
where the second inequality is due to the Lz-smoothness in 17, and the last inequality is due to that 2ab < a² + 122 for any a, E R. Taking the expectation on both sides equation 44 and adding with equation 43 it follows that
( Logf 2
E
(a. L2a 7(L + L2Z2))))) (V, ((x,,
||vall"
C[(C mi) [(x m111]
El(a + (2L
(g:
()f())))))
8t
+
2 ||: V C(x,, 11+1) 2
+ IE
||
(45)
87
According to a
1
Br = min
2Lo Lolleell and Lemma
1
3
we can further show that
2L
1
9L9
(V, ((),
+
||:g
1|
4L2
4
4
1
?L7
D2
<E(L( nh) ((F24117441))
+
+
4Lz
4
N
18

---

Published as a conference paper at ICLR 2025
Do
D1(V, 7c+1 1)2
d
(46)
4L0
N2
8YL8
Moreover, have that
E[(V 7(+1))
S (V, m1)) ((
m++1) v,,((xe,
<VE ạ (Tr, + 2L3
(2 ( (1,, 4 - v m2))
D2
33E (V, ( m1)) N1 ạ
(47)
Let 36
and N₂
12D, La
By equation 46
and equation
we then have that
1
Bt |1ee1
E
(V,((x,, m))
8L2
4
D2
Do
D2 e 4LoN2 N1
DI
<E[C(Z,, m+) [((4)1 2L2N1
(48)
4LoN2
8Y
Taking the sum of equation 48 from i = too T - 1, we have that
T
31
(V (V C(r,, n)))
111a11?
T
8T,2
4
D2
Do +
DI
D2
[[(xx no) [(IT, mT)
+
(49)
T
2L
4L
4Lo N1
8yL
Let T 2 max(8L2, 4Lo)
(c((aamm)))3 - ((v.))
N1 2 max 200D=
10DzL0 Liee
N₂
>
max
10DoL2 5Dn 120, Lge²
2,
and e² < 84 min
8L. )
Then equation 49
can be further
bounded as follows:
Σ
E
(V
((x, ? + 3t ||or1 < <min
1
c.
(50)
T
8L2
8L2 4Lo
t=0
Thus we can find some < T such that E sLa (V C(z,, m m1)) S 81g
and E
Be
c.
4
4h.0
Based on equation 47 Moreover, we have that
we then have that (E C,,,, 1))1)))
< E[(( (12,,
< 4e
2
2 min Lo
||
|0x||
E [e|lv:]] ||
2
2
E
E
(51)
Lo
2c
Lu
2Lu
where the second inequality is due to the fact that min
a2
2 a
2/2 holds for any 2 0. Asa
2 2
result, we have that B[]lu,]| [] S 3c. For N₂ 2 Dot1e3D,
we have that
Do + DI(V, 7++1))
(Billu - VaL(Ie 111))) <
CaC(Ir m+11ll SE E
< E
N2
can be further shown that E V V V,L((,, B[ [I] + Blllu; - V.L(a,, 1)]l < 4e
and E[|| 21,/V,,,C(( M(11)l < E V C(,, 7+11) V m++1 < 6c. This completes the proof.
A.7 PROOF OF LEMMA
Proof. For any x, x' Rd 17 E R and s S, we have that
(,,((,,, V,L(x', s))
=G (15r)
[(xx, [[xx,)) Gn ) - (4b*) (f(x', - Gn
A
19

---

Published as a conference paper at ICLR 2025
G2M I A
||
2'11,
(52)
where the inequality is due to that v0 is M-smooth and ((z, is G-continuous in æ. Similarly, for any x Rd n7.r R and s 3, we have that
V x (ar, 77 8) - VoL(x, .())
= | ((2, Gn
V[(x,)) (1b") (Mx,)) Grf Ve(a,))
A (1**) (((x,)) Grf )
((x1,) - Gn
<G (wey
A
G M - 1 n/
(53)
where the first inequality is because that ((r, 8) is G-continuous in and the last one due the M-smoothness of 6²
A.8 FULL VERSION AND ITS PROOF OF THEOREM 4
Let co
max(32L2, (0,22,,, c1
(4 44+ SLID:
Lg
+
32
N1
+
162
5D, Lg
C2 max
8L2
1
+
L
C3
+
Le TOLo
LaDi to
L2
5Lo42
331;
LnD:
1517
2L.
L3
and C4
17
03
G0L
For
N1
6Da0n02
N2
max
20g La
20qe2 L2,
12
18
N3
max
L2
Lo
30ol
Do-1D,Da)
2Loe
N4
max
5gLa La
69 Lo
and
2
min
1480L, Loq" 4201c0 1). we have the following theorem:
LAN.
Theorem 6. Let a BT. = min (2t . ) for Algorithum
Setting T
2
Goo (Cz ) inff.. C(a.n)) we have that
min
El| Van T++1)ll S c4c.
K<T
Proof. Similar to equation 43 for the update of 7,, we have that
<E C(a,, mh) - (V, m1), aest) + (arga)))
L2
[[[ 11+1)]
2
L2 Ela
E (((,,, - B(an (9 Blan (.
2
(54)
Similar to equation 44 for the update of x and any 7 0, have that
C(E m+1) S S(x,, m++1 - (V (14.))00))))
Lo + L, 1,,,V,,,,..... mc) + L2 a.gh ||
2
3,
SL(x,, (1|vz|1 11 - || v L(x,, T 1 1P-11l1;- 110,
VaL(Ie, 1++1)11
+ To + Ln V V,fL(rr, m1)
- grl + (In + To To2c2c 199d 11
2
31 1|
3
Lo
+
llue - Me))l1
11
2
2
84
+v(L1 + )
167
34
+ g. V, 11)1
| 1|
(55)
167
20

---

Published as a conference paper at ICLR 2025
Combine equation 54
and equation 55 and it follows that
1
Lya 7Ta + T20)))) (0x)²
( Lus?
E
2 04
|10 1|x|13
[[ me)
[(
8y |luell*
Br 11u- (x+1))
+
(gr
713(9- v,, m.)
2
Setting a
1
and B: = min
2L. Ioliva]]
1
we have that
3
2512
31 |1a11
[
(g:)²
32L2
16
el
<Bi[(r, mi) ((1(+1. + 8
+ Bllle V Va,, M+1)1l1
4Lo
+
1
+ t
El(g: - V,,((ze, m))
(56)
8L2
yet = 501, then have that
1 and take the sum of equation 55 from 0 to T 1. According to Lemma
we
31
T-1
E((ge) 2] Bl
||01122]
0
16L₂
4
LIT
B[C(ro, 70)
L(TT, [[)
1.b
T
Do
4D,D2
qe²
(A+ (4+
8L3D2
32L3D2
G4qE-L9L2
E
+
4T.0
N33
N1
N4
T
N1TO
No1.
T
D1
339e L3
qD1
Σ
E
+
(g.)²
4L0
N3
8N3
N.
8N
2N,N2
N2N
1=0
1
L
Σ
E [
D2
2q12
+
2 +
(g:)²
(57)
8L2
50
N1
N2L0
8N
t=
Let cD m2xx32 8Lo), 01
4 +
81. D2
321 D2
161.
and 62 max
+ 50 1).
N1
50,L3
8La
For
Na
z
max
L0
La
300l DD+DD
2Lar"
N4
2
max
(اgL2 La
Egerca To
62
S
min
LEN.
L
1), N2 2 max
20gD; Lg Lo
20qe2 Lzz,
12 48
and N₁ 2 6D20p02 we
12802, Leg² 42h100
then have that
(g.)² +
31
110.111
32L₂
4
2T
Do +
D2
<B[[(zo, no) - L((T, TTT) +
+
6co
4LoNo
+ 2T 9
4+
81,
32T D2
L2
N₂Lo
L3
N2
Li
L
D&T
L
20L3
+
+
+
+
2T
8I.2
50
N1
8L,
50
N2L2
2T
< E E[[o na)
[(xr. mrr)
+
(58)
6co
we can find some to mod = such that Grg (ro(C[oo)))) inf on f(x.n)))
For T = nq 2
to
Br
< ge²
E
(gv)
||
(59)
32L2
32L2
21

---

Published as a conference paper at ICLR 2025
Moreover find some t [to. to + 1) such that
1
2²
(l( )1 E8
Ur
(60)
327,2
60
Based equation 60 and co max(32L2, &Lo)) have that [(()))]] S c² and equation 68 we can further show that
Based on equation 67
to totg-1
D2
2
2 2
El(g. v,,((,,,,)))
E
(g N2L
e²
+
N1
N2
2²
2²
2²
+
+
S
(61)
6c0
60p
160L₂
60L2
Thus we have that
V ((T, 71+1)ll S Bi(9
V f( me)l + Igel + L2 gell
1
+
c.
4
60Lz
Moreover, we can show that
e²
E²
|| 12
|oall
[e] [e][vg]] ||
e²
min
E
(62)
T
To
2,2
To
2T
where the second inequality due to the fact that min
2
a
2 a
holds for any a 2 0. As
result, we have that B[[[0;]] [] S 3e. Based on equation 71 and equation
72
we can further show that
E By - C( 7 |
Do + 4D 2 + 2D, Lzaf, (9
4Di - v, 1)
<E
+
N₂
N₂
lot--1
Σ
2
2 8
13L3
ap
2
(1)-1)²
-4 1z
L3
+
2
L2an (gv)
N4
Lg
Lg
N4
1==o+1
2ca fotg-1
16 L3
L2
E
(9t- -12 1)
16
V
- 90 1)
NA
L
t'=t++1 1
Do
4D1 + +22,L
TT.
T
32e21.7)
1049-1
+
+
+
Σ
B((gr)
N3
N3
NaIğ
8N
NoL.
N=
Aqe 2
8qe DT
4Dr
32 T
+
+
L(V,,Lize ne)
gv )
NA
NA
N₂
NLL
t'to
DILo
33L3
L
4L 2
8LobDD2 2
LD
32L
2
<62 +
+
2
T,2
5I. L2
40T.
5T22
5
5l22
5T
15
T,
Do
+
Lo
+ 2T
L2
331
LoD:
1
+
40Lo
L
5L
15L2
2L
<ege?
(63)
Thus have that
V 7 Il < E1ll V ((, || < (3+ vesle.
then follows that E|Il n. C(x,, 7c-1)11| < ((), L(C,, ((1,,,++1111 7++1)ll c.c. This completes the proof.
22

---

Published as a conference paper at ICLR 2025
A.9 FULL VERSION AND ITS PROOF OF LEMMA
Lemma 6. With the parameters selected in Theorem for each 4g < T that can be divided by 4.
have that
to totq
to
D2
2q
2q13
El(g - (x
2 +
an a(()))))
(64)
N1
N2L
N2
t=
t=
and
B Val(Ir, 7++1)11
la ta+--1
t=
Do
4D
qc²
(44
B2
321
64qc²
E
N3
N1N1
N1
LT
N2L0
to 4
4D1
Dr
33qe 2 L2
qDi
2
E
(9.)²
(65)
N3
8N3
NLL
8N1
2N,N3
N2N,L
t=
Proof. If mod 0, ge is an unbiased estimate of V f me) and according to Lemma have that
we
D2 Bl(a v,,((se)))))
(66)
N₂
Otherwise, we have that
[g: Vn No)) )=
=B(( V (( nh B2) 1, -t-1 v,f((r, n))
=B(( V V,,,,,, mh B2) 1,- B2) + V (1,, 7--1)
v,,((z,, mo) )] E((9c-1- -
(67)
where the last inequality is due the fact that V ((x,, 11: B2) V 7/- B2) an unbiased estimate of v,,((z,, m7.) V,,((r--1,1 We now focus on the first term of equation 67 which can be further bounded follows:
[[(V,,((x,, B2) V V + (n - - v,L(x,, m))
E(( V
((I,,, 71. nr. S) V V,,((1111.71111157))
N2
< E[(V (((V,((I,,,) nr 5) V (x) (V 71-1
N2
2
<R
1 + 83 11
N2
2T3
2 N₂
<E
2 +
2 1
(68)
NoL3
where the first inequality is due the fact that the square of expectation is not larger than the expectation of square, the third inequality is due to the continuous properties shown in Lemma 4
and the last inequality is due to the fact that 3, = min 20 Iafezal) Combining equation 66
equation 67 and equation 68 for to mod g O, we have that
totg11
tot--1
2g 2 N2L3
Bl(g. ()))
Σ
E
(g.)
(69)
8N,
t=
We then focus on the estimate of the gradient to æ. If mod g 0, we have that
Elllyz 11
VaL(Ie, 21
Do + Dj D1 (,
(Iz. 1
<
Ng
23

---

Published as a conference paper at ICLR 2025
< Do + (V, m:)) + 22, 12
N₂
Do + (D)( 2D, (9))
4D1 - V ,,,( m,))
<
(70)
N3
N3
where the second inequality is due to the Lg-smoothness on and the update of n, Otherwise, we have that
Ello - VnL( ne ]]]
=Ill V a (Ire 7 BB) - V BI, - 2 - Vz V
= af (1=,, 11 B4) Vx
Ba) - vaL((xe-11)) (.
+ -1
(71)
since VnL(I,, 7e+1; BB) (ar-,1 Re: Ba) is an unbiased estimate of Va 11+1
VoL(re-1, mt). We now focus on the first term of equation 71 which can be further bounded as follows:
A.V. B.) C Nr B2) + VxL(x=-11n)) (x
1
N4
2
V
M- S) V C Mr S)1 IV= - 11
no
N
<B
2
El(LZa)(0) ) (2L + 14 S) [31]
N
<
2
2
4
V C C(I-1, m2)2 1
12
D2
+
2
L2a
N4
L
13
N4
<E
2
2
8
L7
(
1, (It- 1, Mh- 1))2 + 8
L9L1
a
(st-1)
+)
+172/
D2
+
2
12a2(11)))
N
T
N4
ST.
2
8
11
0
+
D2
+
2
oz (o:)
N
L
I
N
2e
I22 (V VV, (( 1-11) - 9)-1)
+ N4
E
16
(9- 19 + 16
(72)
1
where the third inequality is due to Lemma the fourth inequality is due to Be
min 2L Loller and Lemma Combine equation 70 equation 71 and equation 72 and for mod q O. have that
Σ
to Bllle t=to
to
Do
qc²
D2
E
4+
N3
N1
Li
1=0
to to+--1 1
ADD
D1
33qe2 L3
E
+
(gt)
N3
8Ng
NaT.
8N,
t=
l---1
[4D,
32
E
(g: (9:- -.,(((
N₂
NaL.
to
Do
qe²
8T D2
E
+
4+
Ng
NA
L3
to+g-1
E
4DD
D
33qe² 3 L3
q
(g.)²
N₂
8N
N4Iă
8N,
24

---

Published as a conference paper at ICLR 2025
+
4D1
32qe L3
totg-1
Σ
B
D2
2qL2
2 +
20L3
o2(or)))
N3
NaLi
Ni
N2L.
N₂
t=to
t0+-9-1
Da
4D1 D2
qr²
813
3212 D2
649c213T1
6Aqe
1.13.
E
+
+
Ns
NgN1
N4
Li
N2L0
To fo+g-1
4D1
D1
33qe
qD1
Agp
E
+
(0x)
(73)
N3
8Ng
NaLo
8N4
2N
N2NaL.
This completes the proof.
A.10 DETAILS OF THE EXPERIMENT
A.10.1
LIFE EXPECTANCY DATA
This life expectancy data includes health factors from 193 countries (input features) and the life expectancy (target) from the World Health Organization and United Nations websites. We follow the same data pre-processing as in Chen et al. (2023) to fill the missing data with the medians, censorize and standardize all the features remove redundant features, and a standard Gaussian noise is added to the target for model robustness. Each element of the initial parameter zn is generated by a standard Gaussian distribution. In our deterministic setting, we compare the methods with fine-tuned learning rates. The iteration number is set to 50. For existing methods, we follow the fine-tuned learning rates in (Chen et al. 2023), where the step size 33 = 10-4 for GD, 3, = 0.2 for normalized GI)
and B. 0.3 min
10 [V For our D-GD method, we or B, 10-1 and for our
D-GD-C method, we set a2 10-4 and B. 0.35 min 2000 [(
In our stochastic setting, we run the experiments for 5000 iterations. We generate the initial Zo. To by running a normalized GD method with step size 3r 0.2 for 30 iterations. For existing methods, we follow the same setting in (Chen et al., 2023). We set the mini-batch size to 50. For SGD, the step size is B, = x 10-1 For the normalized SGD with momentum method, the momentum coefficient is set 10 and the step size is set to 8 x 10 For the normalized SPIDER method, we have that step size 3, = 4 x 10 3 and epoch size q = 20. For our D-SGD-C, we set at = 8 x 10 and B. 0.05 min(
[=]]]) For our D-SPIDER-C, we have that 0 = 8 x 10 and
3 = 7.5 x 10-3 min 22.5, |
1
A.10.2 CIFFAR- 10 DATASET
In this part, we conduct experiments on the famous CIFAR-10 dataset (Alex 2009), which includes 50000 training samples. We employ DRO model to construct linear classifier. After extracting features from a pre-trained ResNet-50 model (He et al.] 2016). for the i-th sample in our dataset, have input 2/ E 2049 and output y: [10]. The non-convex original loss function is set as f(x, (z,, = In E exp(x] 2 - x 2)) 0.001 Σ₁ Ek= In(1 + [=),,e),, where æ 100x2019 is the trainable parameter, and xy is the j-th row. For the DRO model, À is set to 0.05, and the initial value 7jo is set to 0.1. Each element of the initial parameter xo is generated by a standard Gaussian distribution.
In Figure 3 we provide the training curves with fine-tuned learning rate for SGD, Normalized- SPIDER CCen et al. 2023), Normalized-SGD with momentum QJin et al. 2021) and our proposed D-SGD-C and D-SPIDER-C methods. The x-axis stands for the training iteration, and y-axis stands for the DRO dual function value. For Figure 3 we can observe that the Cormalized-SPIDER and our D-SPIDER-C have similar performance and converge faster than other methods. Our D-SGD-C has similar performance compared with the Normalized-SGGi with momentum method but our D-SPIDER-C outperforms the Normalized-SGii with momentum method.
We set the mini-batch size to 200. For SGD, the step size is 3, 1.5 x 10-3, For the normalized SGD with momentum method, the momentum coefficient is set to 0.1 and the step size is set to
25

---

Published as a conference paper at ICLR 2025
Loss Comparison Across Methods
2.0
Method
SGD
1.9
Normalized-SGDD
D-SGD-C
Normalized-SPIDER
D-SPIDER-C
DRO Dual
1.5
1.4
1.3
20
60
80
100
Epoch
Figure 3: The numerical results for Cifar- 10 dataset.
x 10-3 3 For the normalized SPIDER method, we have that step size Br = 3.5 10-3 and epoch size 10 and large batch size 2 x 1 For our D-SGD-C, set ag 1 X 10 3
and Be = min( 1000 T. For our D-SPIDER-C, we have that 04 = x 10 and Br =
min 2000 20
A.11 RESULTS FOR NORMALIZED MOMENTUM
Algorithm 4 D-SGD-M
Input: initialization Tu, Tlu step sizes a, B, ri, P2 number of interactions T
1
2: while t < T do
3: Draw one sample from Po and compute It-1 + 7t-111
4: if t==1 then
5: Draw one sample from Po and mo (111,111, end if
6:
7:
m. 4- -174-11 + (1 - r r1)
8:
M) 7/- ||
9:
Draw one sample s from Po and compute vt-1 f- V.L(II-11 Me,
10:
t= then
11:
Draw one sample from Po and wp <- V=L(x1-1:1155)
12:
end if
13:
Wi + T2W + (1-r2)
14:
Ft-1 Tw
1 1+1+1
16: end while
In this section, we provide result for the normalized momentum method, which is shown Algo- rithm q The following proposition establishes the convergence and complexity of Algorithm
26

---

Published as a conference paper at ICLR 2025
Proposition 1. Set 1 - r1. 11:1-17 S O(e)) 8 Olc ) O(vDi3) and T 2 O(e f for
Algorithm 4
We then have that
min B 2., Me+1 MI 5(()). [<T
Note that compared with the normalized momentum algorithm for generalized smooth objective (Jin et al. 202T), Algorithm 3 does require the full gradient information for initialization or the of mini-batches. This because that due to our partially generalized smoothness, the expectations of [| C(zo, ]] and |/vo [(ro, 77) ]I no longer unbounded thus the requirement on full gradient is not needed. Moreover, the partially generalized smoothness allows the Lipschitz constant
on bounded by linear function of gradient on 7). Thus by setting a O(v D23) we can remove the mini-batch required in Jin et al. (221).
27


Reviews:
[{"review_id": "r9lkicMnNz", "reviewer": "Reviewer_4jhU", "summary": "In this paper, the authors consider a distributionally robust optimization (DRO) problem with non-convex smooth losses. The previous work of Jin et al studied the same problem and showed that the dual problem satisfies a notion of generalized smoothness and bounded variance. They then used a normalized momentum algorithm that provably converges to stationary points under these conditions. By contrast, this paper shows that one can provide a more fine-grained analysis of the smoothness and variance. The authors that propose alternative optimization methods based on these refined properties. Finally, experimental results show that the proposed methods outperform the algorithm in Jin et al.", "questions": "I do not have questions for this work.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors conduct an improved analysis of the non-convex DRO problem and the analysis leads to simpler algorithms and theory. The partial generalized smoothness condition might be of interest in other settings as well.\n\n2. Theoretical results are presented in a clear manner, and the authors provide detailed comparison with the previous work by Jin et al, thereby hightlighting the contribution of this work.\n\n3. Besides improving over the normalized momentum method in Jin et al, the authors also provide an extension of the well-known spyder algorithm to the DRO setting. I'm not aware of such type of existing results in the literature.", "weaknesses": "1. In some paragraphs the authors seem to misuse \\citet instead of \\citep (e.g. the first paragraph in page 4)\n\n2. The authors only run experiments at a relatively small scale. It would be interesting to compare different methods by running a large-scale experiments.", "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": "", "extra_scores": {}}, {"review_id": "pUk3EuT8du", "reviewer": "Reviewer_oGQa", "summary": "This paper studies the penalized distributionally robust optimization (DRO) problem where the loss function $\\ell(x, s)$ is $G$-Lipschitz and $L$-smooth in $x$ for any given sample $s$. In particular, the authors consider $\\psi$-divergence distance in the penalty term and solve the DRO problem from its dual optimization. The authors refines the generalized smoothness used in prior work [1], and proposed alternating gradient methods (in terms of the dual variables and the primal variables) by noticing that the dual problem is actually smooth with respect to the dual variables. By this refined perspective of generalized smoothness, the authors achieve the same complexities as ones in [1] by simpler algorithms. Further convergence analysis under stochastic settings and variance reduction is conducted.\n\n[1] Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In Proceedings of Advances in Neural Information Processing Systems, volume 34, pp. 2771–2782, 2021.", "questions": "- The paper title is quite vague. I suggest that the authors could rephrase it to make it more precise, like in terms of generalized smoothness.\n- Could the authors discuss the technical challenges of this work, compared to the prior work [1]? It seems that the write-up and the analysis are mostly similar.\n- It seems that generalized smoothness condition heavily relies on the Lipschitzness of the primal function. Am I understanding correctly, or it can be relaxed?\n- In the stochastic settings, the step sizes $\\beta_t = O(\\varepsilon / L_0||v_t||)$. Could the authors discuss the dependence on $\\varepsilon$?\n\n\n[1] Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. In Proceedings of Advances in Neural Information Processing Systems, volume 34, pp. 2771–2782, 2021.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The write-up of this paper is good and easy to follow.\n- It is interesting to see that one can refine the smoothness on the dual problem of penalized DRO and develop simpler algorithms by exploiting the refined smoothness.\n- The analysis is provided under both deterministic and stochastic settings. Improved complexity is achieved by recursive variance reduction.", "weaknesses": "- The generalized smoothness on the dual side depends on the strict assumptions on the primal loss function: assuming Lipschitzness and smoothness at the same time and for any sample $s \\in S$; the bounded variance of the function values.\n- The deterministic setting would be restricted, as one usually cannot access the full gradient of the stochastic objective like $\\mathcal{L}$.\n- Although the authors propose simpler algorithms, the step size requirements are actually strict: $\\beta_t$ either dependents on the initial function gap (Theorem 1) or requires full gradient evaluation (Theorem 2). \n- I would not say optimizing $x$ and $\\eta$ separately; instead the algorithms are performing alternating gradient steps with respect to these two blocks of variables.", "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": "", "extra_scores": {}}, {"review_id": "2XlcU5EJtB", "reviewer": "Reviewer_Rvfr", "summary": "This paper studies the Distributionally robust optimization (DRO) problem. The paper first shows an observation that the specific DRO problem satisfies a stronger smoothness and noise condition than existing work showed. Then the paper designs multiple algorithms to solve the problem making use of the stronger assumptions, together with corresponding convergence guarantees.", "questions": "1. It seems that the citation of the original spider paper (Fang et. al.) is missing. I kindly suggest the authors to add it.\n\n2. Definition 3 actually indicates a much stronger version of the $(L_0,L_1)$-smoothness, as the inequality only applies to $||x-y|| \\le 1/L_1$ for initial $(L_0,L_1)$-smoothness. Therefore, some expressions and citations in the paper regarding the assumption may be inappropriate (e.g. citations in line 192). I suggest the authors to add some discussions on this.\n\n3. I think possibly momentum is also helpful for convergence with smaller batch sizes in your case. Have you tried this?\n\n[1] Cong Fang, Chris Junchi Li, Zhouchen Lin, and T. Zhang, “SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.” In NeurIPS 2018.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written, with a clear introduction to the studied problem and well-defined notations. I enjoy reading it.\n\n2. The theory is neat and complete, taking 3 algorithms into consideration. \n\n3. I appreciate the idea of finding that the problem actually satisfies stronger assumptions and designing approaches based on this observation.", "weaknesses": "1. The convergence in Theorem 3 is not strong enough, requiring a very large batch size. As a comparison, (Jin et. al.) achieved a convergence bound with a much more reasonable batch size requirement. In fact, I think this is partially why they used this more complex method, as momentum is proven to help handle noise in normalized gradient descent and enable convergence with small batch size (Cutkosky \\& Mehta, 2020). \n\n2. All the convergence results seem to require a large batch, and I don't see benefits compared to the results in (Jin et. al.). This makes me wonder whether the observation in Sections 3.1 and 3.3 that DRO satisfies stronger conditions really helpful for designing algorithms. I will be happy to raise my score if the authors can address my concerns.\n\n[1] Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex Distributionally Robust Optimization: Non-Asymptotic Analysis. In NeurIPS, 2021.\n\n[2] Ashok Cutkosky and Harsh Mehta. Momentum Improves Normalized SGD. In ICML, 2020.", "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": "", "extra_scores": {}}, {"review_id": "i08HNOoaj7", "reviewer": "Reviewer_khoB", "summary": "This paper studies Distributionally Robust Optimization (DRO) with non-convex smooth functions, which optimizes the expected loss under the worst-case distribution in an uncertainty set of distributions, which is different from the tradition Empirical Risk Minimization (ERM). In particular, the paper improves Jin et al (2021) which treats the same problem, working with the dual formulation. The authors show that the dual problem and the gradient noise satisfy simpler yet more precise partially generalized smoothness condition and partially affine variance condition by studying the optimization variable and dual variable separately. This also yields simpler algorithm design and convergence analysis, based on which the authors propose D-SGD-C algorithm and variance reduced SGD versions.", "questions": "After reading the paper, I feel that the main context is a dry list of theorems referring to the proofs in the appendix. So the mathematical innovations can be lost if there is no better overview of the ideas. Can the authors provide one in a revision?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) Proposed an improvement of Jin et al (2021) and showed that by studying the optimization variable and the dual variable separately, one can derive the fact that the dual problem and the gradient noise satisfy simpler yet more precise partially generalized smoothness condition and partially affine variance condition;\n\n(2) Based on this idea, they also propose new and simpler algorithms like D-SGD-C etc.", "weaknesses": "(1) This is an almost pure math paper, so a better explanation of the main mathematical ideas at the introductory part would be nice\n\n(2) no experimental validations", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)