An Online Method for A Class of Distributionally Robust Optimization with Non-convex Objectives
Authors: Qi Qi
Zhishuai Guo
Yi Xu
Rong Jin
Tianbao Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Non-convex Stochastic Optimization
Distirbutionally Robust Learning

Abstract: In this paper, we propose a practical online method for solving a class of distributional robust optimization (DRO) with non-convex objectives, which has important applications in machine learning for improving the robustness of neural networks. In the literature, most methods for solving DRO are based on stochastic primal-dual methods. However, primal-dual methods for DRO suffer from several drawbacks: (1) manipulating a high-dimensional dual variable corresponding to the size of data is time expensive; (2) they are not friendly to online learning where data is coming sequentially. To address these issues, we consider a class of DRO with an KL divergence regularization on the dual variables, transform the min-max problem into a compositional minimization problem, and propose practical duality-free online stochastic methods without requiring a large mini-batch size. We establish the state-of-the-art complexities of the proposed methods with and without a Polyak-Łojasiewicz (PL) condition of the objective. Empirical studies on large-scale deep learning tasks (i) demonstrate that our method can speed up the training by more than 2 times than baseline methods and save days of training time on a large-scale dataset with ∼ 265K images, and (ii) verify the supreme performance of DRO over Empirical Risk Minimization (ERM) on imbalanced datasets. Of independent interest, the proposed method can be also used for solving a family of stochastic compositional problems with state-of-the-art complexities.

An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives
Qi Qit; Zhishuai Guo Yi Xu', Rong Jin', Tianbao Yang! Department of Computer Science, University of Iowa, Iowa City, IA 52242
Machine Intelligence Technology, Alibaba Group (qi-qi, zhishuai-guo, tianbao-yang @uiowa.edul (yixu, jinrong.r] @alibaha-inc.com
Abstract
this paper, we propose a practical online method for solving a class of dis- tributionally robust optimization (DRO) with non-convex objectives, which has important applications in machine learning for improving the robustness of neural networks. In the literature, most methods for solving DRO are based on stochastic primal-dual methods. However, primal-dual methods for DRO suffer from several drawbacks: (I) manipulating the size of data is time expensive; (2) they are not friendly to online learning where data is coming sequentially. To address these issues, consider class of DRO with an KL divergence regularization on the dual variables, transform the min- max problem into a compositional minimization problem, and propose practical duality- frre online stochastic methods without requiring large mini-batch size. We establish the caat-offthee-an complexities of the proposed methods with and without Dolyak-Eojasiewiin (PL. condition of the objective. Empirical studies on large-scale deep learning tasks (i) demonstrate that our method can speed up the training by more than 2 times than baseline methods and save days of training time on a large-scale dataset with 265K images, and (ii) verify the supreme performance of DRO over Empirical Risk Minimization (ERM) on imbalanced datasets. Of independent interest, the proposed method can be also used for solving family of stochastic compositional problems with state-of -oe--o--tthhtttte complexities.
nigh-dimensional dual variable corresponding
Introduction
Distributionally robust optimization (DRO) has received tremendous attention in machine learning due to its capability to handle noisy data, adversarial data and imbalanced classification data 42] B3 4
Given a set of observed data (zi....,Z,, } where z, (x, y:), DRO formulation can be written as:
min max Fp(w)= = Σ pl((wz))) h(p. 1/n) + +rw), WER' PEAn
(1)
where w denotes the model parameter, An = E Σ, 1,p: 0} denotes a dimensional simplex, E(w; z) denotes a loss function on data z. h(p, 1/n) is divergence measure between and uniform probabilities 1/n,, and r(w) is convex regularizer of w. When e(w; z) is a convex function (e.g., for learning a linear model), many stochastic primal-dual methods can be employed for solving the above min-max problem 35 20 49
48 32] When f(w: z) is non-convex function (e.g.. for learning a deep neural network), some recent studies also proposed stochastic primal-dual methods [ 48).
"The first two authors make equal contributions. Correspondence to tianbao-yang @uiowa.edu.
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

However, stochastic primal-dual methods for solving DRO problems with a non-convex <(w; loss function (e.g., the predictive model is a deep neural network) suffer from several drawbacks. First, primal-dual methods need to maintain and update high-dimensional dual variable p E TR for large-scale data, whose memory cost is as high as ((n) per-iteration. Second, existing primal-dual methods usually need to sample data according to probabilities in order to update w, which brings additional costs than random sampling. Although random sampling can be used for computing the stochastic gradient in terms of the resulting stochastic gradient could have n-times larger variance than using non-uniform sampling according to P (please refer to the supplement for simple illustration). Third, due to the constraint on p Ans the min-max formulation (I) is not friendly to online learning in which the data is received sequentially and n is rarely known in prior.
Can we design an efficient online algorithm to address the DRO formulation without dealing with p E R for a non-convex objective that is applicable to deep learning?
To address this question, we restrict our attention divergence hpp 1/n) = E; P3 (ng( ) is used for regularizing the dual variables p. where À > 0 regularization parameter. We note that this consideration does not impose strong restriction to the modeling capability. It has been shown that for a family of divergence functions h(p, 1/n), different DRO formulations are statistically equivalent to a certain degree [12]. The proposed method is based on an equivalent minimization formulation for h(p. 1/n) = X >E Pt log(np;). In particular, by maximizing over p exactly. ① is equivalent
family of DRO problems, in which the KL
(Frro (w) A log WERd
min
1/n
Σ
exp((((:z)\\1) + r(wl].
In an online learning setting, we can consider more general formulation:
min
(Faro()= A log (E& exp
+ r(w)).
WERdd
The above problem is an instance of stochastic compositional problems of the following form:
min F(w) == (2)](] + r(w), WERd
by setting f(() À log(s), 21 and (x()) = exp(f((::))) w: 2 /). Stochastic algorithms have been developed for solving the above compositional problems. 44 proposed the first stochastic algorithms for solving 4.. which are easy to implement. However, their sample complexities are sub-optimal for solving (4). Recently, a series of works have tried to improve the convergence rate by using advanced variance reduction techniques (e.g., SVRG [19), SPIDER 13] SARAH (3)).. However, most of them require using a mega mini-batch size in the order of ((n) or O(1/eP I at every iteration or many iterations for updating which hinders their applications on large-scale problems. In addition, these algorithms usually use a constant step size, which may harm the generalization performance.
This paper aims to develop more practical stochastic algorithms for solving (3) without suffering from the above issues order enable practitioners to explore the capability DRO for deep learning with irregular data (e.g.. imbalanced data, noisy data). To this end, we proposed an online stochastic method (COVER) and its restarted variant (RECOVER). We establish state-of-the art complexity of COVER for finding an c-stationary solution and a state-of-the- art complexity of RECOVER under a Polyak-Lojasiewerr
(PL) condition of the problem. PL condition has been widely explored for developing practical optimization algorithms for deep learning [52) Compared with other stochastic algorithms, the practical advantages of RECOVER are:
1. RECOVER is an online duality- algorithm for addressing large-scale KL regularized DRO problem that is independent of the high dimensional dual variable p E IR", which makes it suitable for deep learning applications.
2. RECOVER also enjoys the benefits of stagewise training similar to existing stochastic methods for deep learning [52], i.c., the step size is decreased geometrically in stagewise manner.
2e is either the objective gap accuracy F(w)- min F(w) < or the gradient norm square bound [VF(w)] <

---

Table 1: Summary of properties of state-of-the-eee art algorithms for solving DRO problem. The sample complexity is measured in terms of finding an e-stationary point w/o PL condition, i.e.
[VF(())l < e, or achieving e-objective gap, i.c, F(w) minw F(w) S with PL condition. Ö omits a logarithmic dependence over e, n represents the size of datasets for a finite sum problem, denotes the dimension of w. GDS represents whether the step size is geometrically decreased.
Memory
Settings
Algorithms
Sample Complexity
batch size
GDS
Style
Cost
PG-SMD2 [4]
O(n/c 1/c)
O[]]
Oin + d) O(d)
Primal Dual
ASC-PG 45
0(1/2)
0(1)
Compusitional
w/o PL
CTVR 33
0(1/65))
O(1/c)
((d)
Compositional
COVER (This paper)
0(1/63/2)
0(1)
O(d)
Compositional
Stoc-AGDA [50
O(1/u²e)
0(1)
O(n +
Primal-Dual
PES-SGDA 1S
O(1/a²e)
0(1)
O(n d)
Primal-Dual
w/ PL
RCIVR 53
Ó(L/ue)
0(1/))
O(d)
Compositional
RECOVER (This paper)
O(1/pe)
0(1)
O(d)
Compositional
In addition, this paper also makes several important theoretical contributions for stochastic non-convex optimization, including
1. We establish nearly optimal complexity for finding e-stationary point, i.c., for a class two-level compositional problems in the order of (11/c without large
/VF(w)]l S e.
mini-bace batch size, which is better than existing results 44
45
14 51.
2. We etablish optimal complexity for finding c-optimal solution under an p-PL condition for a class of two-level compositional problems in the order of 0(1 ((1/(we) without large mini-batch size, which is better than existing results 533
A theoretical comparison between our results and existing results is shown in Table I Empirical studies vividly demonstrate the effectiveness of RECOVER for deep learning on imbalanced data.
Related Work
DRO has been extensively studied in machine learning [3] 1I 40). statistics, and operations re- search 42 In [3 the authors proved that minimizing the DRO formulation with quadratic regularization in a constraint form is equivalent to minimizing the sum of the empirical loss and a variance regularization defined on itself. Variance regularization can enjoy better generalization error compared with the empirical loss minimization (33), and was also observed to effective for imbalanced data 33 [56.. Recently, [22 also establishes this equivalence for broader family of regularization function (p, 1/n) including the KI. divergence.
Several recent studies have developed stochastic primal-dual methods for solving DRO with non- convex loss function ((w;z) assuming is smooth or weakly convex [4] 26 30 48). 44 proposed the first primal-dual methods for solving weakly convex concave problems. For online problems, their algorithms for finding an c-stationary solution whose gradient norm square is less than e have a sample complexity of ((1/²) O(1/²²) with or without leveraging the strong concavity of h(p, 1 1/n) for finding an c-stationary point. Recently Liu al. 28 proposed leverage the PL condition of the objective function improve the convergence for non-convex min-max formulation of AUC maximization. Then, a PES-SGDA algorithm is proposed to solve a more general class of non-convex min-max problems by leveraging the PI. condition [15] Both (8 and [15] have used geometrically decreasing step sizes in a stagewise manner. However, their algorithms' complexity is in the order of O(1/u²e), which is worse than O(1/pe) achieved in this paper. Similarly, (50) also leveraged PL conditions to solve non-convex min-max problems and has a sample complexity of O(1/xe)). Nevertheless, the step size of their algorithm is decreased polynomially in the order of O(1/t), which usually yields poor performance for deep learning.
All the methods reviewed above require maintaining and updating both the primal variable w and high dimensional dual variable p E RR, Recently, Levy et al. 23 considered different formulations of DRO, which includes our considered KL-rregllarzed DRO formulation assumed that the loss function convex and proposed a stochastie method with a sample complexity (()/²²) for sovling the KL-regularized DRO formulation. In contrast, we provide better sample
special case. Their
3

---

complexity in the order of O(1/e) under PL condition without convexity assumption. Additionally. their method requires large batch size in the order of O(1/e), while our method only requires a constant batch size which is more practical. We also notice that recent work (24) and its extended
version [25] have considered formulation similar to (2) and proposed a stochastic algorithm. However, their algorithm has a slower convergence rate with an ( complexity for finding an c-
stationary point and an (11(((²)) complexity for finding an e-optimal solution under PL condition. Our work is concurrent work appearing online earlier than 124). To the best of our knowledge, this the first work trying to solve the non-convex DRO problem with a duality-free stochastic method by formulating the min-max formulation into an equivalent stochastic compositional problem.
There are extensive studies for solving stochastic compositional problems. 44 considered a more general family of stochastic compositional problems and proposed two algorithms. When the objective function is non-convex, their algorithm'ss 's complexity is ((1/c?/2) for finding an e-stationary solution. This complexity was improved in their later works (14), reducing to O(1/e²). When the objective is smooth, several papers proposed to use variance reduction techniques (e.g.. SPIDER, SARAH) improve the complexity for finding stationary point [53
The best sample also considered the PL. condition for developing a faster algorithm called restarted CIVR, whose sample complexity is O(1/ However, these variance reduction-baas size at many iterations, which has detrimental influence on training deep neural networks [43]. To address this issue, [9] proposed a new technique called STORM that integrates momentum and the recursive variance reduction technique for solving stochastic smooth non- con-convex optimization. Their algorithm does not require a large mini-batch size at every iterations and enjoys a sample complexity of (log2//(1//e /t1/c///2 3632) for finding an e-stationary point. However, their algorithm uses polynomially decreasing step size, which is not practical for deep learning, and is not directly applicable to stochastic composite problems.
g
55
complexity achieved for online problems is 0(1/c8/2) [53
55
53
methods require using a very large mini-batch
Preliminaries
In this section, provide some definitions and assumptions for next section. For more generality, we consider the stochastic compositional problem (4):
min F(w) ff ((Ee(gz(w) + r(w)
(5)
WERd
where Is (w) Rd + R.. Define g(w) = Ez (w))]] Let || || denote the Euclidean norm of a vector the Frobenius norm of a matrix. We make the following standard assumptions regarding the problem (5).
T,,, Cg and Ty be positive constants. Assume that Assumption 1. Let Cj,
(a) RP + R a C--iiscchitz finctinn and its gradient f is Lipsschit
(b) 9z Rd + RR satisfies EE] (=(1)) 9u (w2) S C W1 well2 for any W1, w2 and its Jacobian Vgz satisfies ((( V (w2 < L2llw] w2ll2.
(c) r: Rd + R U (00) a convex and lower--eemiconiinuuu function.
(d) F. inf F(w)= -o and F(wi) - F. - AF for the initial solution W1-
Remark: When f(s) = s is a linear function, the assumption [l]g2((1)) Iu [1 < C?
w2ll2 is not needed. To upper bound continuity and smoothness of function F, we denote L = 2 max CjCyLy, C.L.L.CC CyL,, CyLs, O7. Cg Cg,CZ133 for simple derivation in the appendix.
Assumption 2. Let og and og' be positive constants and 0² = og + tzz Assume that
Exll s()) S oū Ezll (g)()) Vg(w) og.
Remark:
We remark how the minimization formulation of DRO problem B can satisfy Assump- tion I in particular Assumption [[) and (b). In order to satisfy Assumption I [b,, we can define a bounded loss function f(w, 2) E [0, Lmax] and then use shifted loss E(w;
Laxx in (3) Then Ge (w) = exp((E(w; z) (max) )/2) is Lipchitz continuous and smooth if ((w; z) Lipchitz and
smooth. f(s) = À log(s) ) is Lipschitz continuous and smooth since s 2 exp(-fmax/ A)).

---

For more generality, we allow for non-smooth regularizer r(-) in this section. To handle non- smoothmess of r, we can use the proximal operator of prox. (W) = arg min -/w-w//++rrww
When 0, the above operator reduces to the standard Fuclidean projection. Correspondingly. we define the proximal gradient measure for the compositional problem (5)
G, (w) (w prox,( [Vg(w)]F(gg(w))
When r = O, the proximal gradient reduces to the standard gradient measure, i.e., (w) = VF(w). To facilitate discussion, define sample complexity below.
Definition 1. The sample complexity is defined as the number of samples z in order to achieve [ S forr certain yj > or (() - F.]
4 Basic Algorithm: COVER
We present our Algorithm Twhich serves as the foundation for proving the the convergence of the objective gap under PL condition in next section. The convergence results in this section might be of independent interest to those who are interested in convergence analysis without a PL condition. The motivation is to develop stochastic algorithm with fast convergence in terms of gradient norm. We refer to the algorithm as Compositional Optimal VariancE Reduction (COVER). It will be clear shortly why it is called optimal variance reduction. Note that in order compute stochastic estimator of the gradient f [g(( (w) given by Vg(w) ()) " f ([(()), we maintain and update two estimators denoted by [u] t and (v] )== sequence, respectively. The {u,}r= sequence maintains estimation of {o( we)) and the {ve)== sequence maintains an estimation of (Vg( (w(w) w The strategy of
maintaining and updating two individual sequences was first proposed in [44] and has been widely
used for solving compositional problems [55] [53]. However, the key difference from previous
algorithms lies in the method for updating the two sequences. COVER is inspired by the STORM
technique 19] To understand the update, let us consider update that applied to the DRO problem (3)
by let f()) A log(-)) 9-(-) exp( ((-:z) and ignoring for the moment. Plugging the gradient of f()) and (.), we have
We+1 = We - 17t V
V1+1 = exp( C( ((e++1;Z++1 (7((W++132e4) (1 a (v. exp(
l ((wr; ((11)
Ve(w,, Zc- 1)),
A
where becomes a scalar, which is an online variance-reduced estimator of Eg [exp(((ww;; /)A)]
and V, is scaled version of Vo. which is an online variance-reduced estimator of Eg (e))p(((::
Finally, we notice that similar method for updating the u, sequence for estimating g( (.) has been adopted in a recent work (6. However, different from the present work they just use an unbiased stochastic gradient estimate Vg(w.),, which yields worse convergence rate.
4.1 Convergence of Proximal Gradient
In this section, we present the convergence result of COVER.
Theorem 1. Assume the Assumption 1 and for any C > 0, k
C/a/3
, 1281 + 07/(7
max((161x") 202 ) and T)t k/(w + 021)2/3, The output of COVER satisfies
AF
o²
El|Ig (wr. )1. S
(6)
72/3
T2/3
where l,, fampledfrom (1....,T}.
Remark: Theorem I implies that with polynomially decreasing step size, COVER is able to find an
c-stationary point, i.e., Ei (w,,) )1 < for a regularized objective and Ell F [w) < c for non-regularized objective, with near-optimal sample complexity Ō ). Note that the complexity 0(1))3/2 is optimal up to a logarithmic factor for making the (proximal) gradient's norm smaller than in expectation for solving non-convex smooth optimization problems [2].
5

---

Algorithm 1: COVER (W1, u1, V1, (m),TT P.PL.
PL = False)
1: Let = cNi
2: if not then
3: Draw samples and construct the estimates: u1 (w(ww)) Vyga (wi)
4: end if
5:
for L 1,..,,, .......T---.. - do
6:
Wi-1 f prox." (we no, f(()))
7: Draw samples z++1, and update
u 92ct1 (We+1) + (1 au+1)(u++ g (we))
V++1 = Vgze+z (We+1) + (1 av+ - Vgeesi (Wr))
8: end for
9: Return: (Wr, Ur, V-) for randomly selected (1,...,7).
A Practical Variant (RECOVER) under a PL condition
The issue of COVER is that the polynomially decreasing step size is not practical for deep learning applications and obstacles its generalization performance [52]. A stagewise step size is widely and commonly used [7 22 52 for deep learning optimization. To this end, we develop a multi-stage REstarted version of COVER, called RECOVER, which uses a geometrically decreasing step size in stagewise manner. In oder to analyze RECOVER, we assume the following PL condition of the objective with a smooth regularization y term [52).
Assumption 3. F F(w) satisfies the p-PL condition if there exists μ >> 0 such that
2p(F(w)=
min F(w)) < [[F(()]]
WEB
In the following, we simply consider the objective F(w) = f(Ezlg2 where r(-) is absorbed into [Ez [.2 (w))). As result, (,(w) (F()).
Although the PL condition has been considered in various papers for developing stagewise algorithms and improving the convergence rate of non-convex optimization [53 52
28 15 In order establish the improved rate, we have innovations in twofold (i) at the algorithmic level, we utilize the variance reduction techniques at the inner and outer level without using mega large mini-bate batch size at any iterations; (ii) at the analysis level, we innovatively prove that the estimation error of the two sequences, u and v, are decreasing geometrically after stage (Lemma 3). These innovations two levels yield the optimal convergence rate in the order of O(1((p)))
5.1 Theoretical Verification of PL Assumption for KL-regularized DRO
Before presenting the proposed algorithm and its convergence, we discuss how the Fãro can satisfy Assumption 3 First, we note that a PL condition of the weighted loss implies that the primal objective.
Lemma 1. Let (w = Ei p:((;; If any p E A. (p(w) satisfies a Jt-PL condition, then Fav.(w) = Alog( E exp((((;; satisfies the p-PL condition.
The assumption that the weighted loss satisfies PL condition can be proven for simple square loss f(w; 2,) = (w") X; y,)², where z, = (x;, yi) consists a feature vector x; and a label y:- In order see this, we can write (w( Σi=
Remark:
xiyPi yiv/p)²2 = ||Aw bll2 where It has been shown many previous Hence, the above lemma indicates
(PI.PI..... Xn pp)) b = (9) .PI...... ........e Vn Pa
studies that such Fp satisfies PL condition 47
34
Faro (w) satisfies a PL condition.
We can also justify that (w) satisfies PL condition for deep learning with ReLU activation function in a neighborhood around a random initialized point following the result in ①
Lemma 2. Assume that input ((x1,))),... (Xn, Yn)} satisfies ||x:]| 1 and ||x: x; 2 8, where
Xn E RRd Yi do and ||y] < O(1). Consider deep neural network with h4 = o(Ax,), his

---

Algorithm 2: RECOVER(WA) Wo, C)
Initialization: Draw a sample Zo and construct the estimates uo 9z. (Wo), Vo Vg (Wo)
2: for & = 1,.... K do
3: (Wg, Ug, V+)= COVER(WE-I U,-1, Vk-1, 1, [k, Tk, True)
4: change 7). T3 according to Theorem
5: end for
6: Return: wk
((Wihg,-1). 1....,,, L, Bhgf where A E Rddxxd Wi E Rdaxdd, B E Rdoxds, & is the ReLU activation function. and E(W;z,) (9: y:)² is square loss. Suppose that for any
W. p. = exp(e(W; //)/)/ Ei= exp(E(W;: /2)/A) 2 Pa > 0, then with high probability over randomness Wo, A, B for every W with IIW Woll I O11ppoly(n, Lo L,yp' 1,811 ,8-1), there exists small > O such that F (W) I O(+) 2 ((Faro(W) minw (W)).
The (e)) term the left side of the PL condition is caused by using the covering net argument for proving the high probability result. Nevertheless, it does not affect the final convergence rate.
Remark:
5.2 Theoretical Analysis of RECOVER
Now, we are ready to present the proposed algorithm under the condition and convergence result. The algorithm is described in Algorithm
The first key feature of RECOVER equipped with the practical geometrical decreases step size between stages. At each stage, we adopt a constant step size rather than the polynomial decreases step size used by COVER as Theorem I Another key feature of RECOVER is that it uses not only We for restarting but also Ug, Vk. the corresponding online estimator of g(Wx) and V9(wa)) for restarting the next stage. this feature that allows us avoid the large batch size required in other variance reduction methods to achieve the optimal sample complexity. With this feature, we can show that the variance of Ug, V&. is decreased by constant factor stagewisely as shown in the following lemma.
Lemma 3. Define constants 61 d²o²
64p13 and = =1/22-1, with =minf L 1
161, J. Tp
200
96cr ( (aL. pL satisfies:
166²a²
Ar }), the variance of the stochastic estimator of Algorithm al Wt oz
u g(wx)))l +l Vg(ww)))l3] pek.
With the above lemma and the convergence bound for that the objective gap ([F(w:) - F.] is decreased by factor of 2 after each stage under the PL condition. Hence, we have the following convergence for RECOVER.
the k-th stage, can show
c²a² Theorem 2. Assume that assumption 1 3 hold. Define constants E1 64pL4 and EN /1/2*
By setting Mp minf SpeeL 11. Tk Omnax 1e/2 ( pL (f)), 104L2, then after 2cc
96ca
20
K = O(log(e1/e)) stages, the oulput of RECOVER satisfies ((((KK) - F.] S..
Remark: is not difficult to derive the sample complexity of RECOVER Ommxx (.. :
12) =
( for < μ.. notable this complexity is optimal for the considered general stochastic compositional problem, which includes stochastic strongly convex optimization as a special case, whose lower bound is ((1((ue) [16].
In addition, it is notable that the proposed multi- stage algorithm is very different from many other multi-stage algorithms for non- optimization that are based on the proximal point framework [7] 48 [.]. particular, these previous studies, quadratic function 7/2l| Wk-1 1|2 with an appropriate regularization parameter is added into the objective function at the k-th stage in order to convextify the objective function. In RECOVER, no such regularization is manually added. Nevertheless, can still obtain strong convergence guarantee.
7

---

CIFARIO
CIPAR1100
24
400
500
20
700
38 100 1500
3000
2500
180 350
200 3000 300 -000 2005
(000
700 8000
34
Figure Testing accuracy (%) vs running time
Fel www.eeoooeee
Figure 2: Testing accuracy (%) vs # of processed training examples
Experimental Results
We focus on the task of classification with imbalanced data in our experiments. Firstly, we compare RECOVER with five State-Of-The-Ar (SOTA) baselines from two categories: (i) primal-dual algorithms for solving the primal-dual formulation of DRO (T) and (ii) algorithms that are designed for the stochastic compositional formulation of DRO (3). Secondly, we verify the advantages of DRO over Emperical Risk Minimization (ERM) for imbalanced data problems by comparing the test accuracy learned by optimizing DRO using RECOVER and optimizing ERM using SGD on the imbalanced datasets. Then we show the RECOVER is also an effective fine-tuning algorithm for large-scale imbalanced data training. The code for reproducing the results released here (39
6.1 Comparison with SOTA DRO Baselines
We compare RECOVER with five baselines: Restarted CIVR (53) (RCIVR), ASC-PG 45 Stoc- AGDA [50], PG-SMD2 [I]] and PES- SGDA [15]. RCIVR and ASC-PG are the state-of-the -rrt algorithms for solving stochastic compositional problems. RCVIR uses variance reduction techniques and leverages the PL condition, while ASC-PG does neither. Stoc-AGDA and PG-SMD2 are the primal-dual algorithms with and without leveraging the PL. condition explicitly, respectively. PES- SGDA is a variant of PG-SMD2 and was proposed by leveraging the PL condition for achieving faster convergence. Please note that ASC-PG and Stoc-AGDA use polynomially decreasing step sizes, RECOVER, PG-SMD2 and PES-SGDA use stagewise decreasing step size, and RCIVR uses constant step size. The parameters of each algorithm are appropriately tuned for the best performance. All the algorithms implemented using Pytorch and run GeForce GTX 1080 Ti GPU.
We conduct experiments on four datasets, namely STL10 R. CIFARIO, CIFAR100 [1]] and NNtuuralis20199 [46). The original STL10, and CIFARIO. 10, CIFAR 100 are balanced data, where STL has 10 classes and each class has 500 training images, CIFARIO (resp. CIFARIO0 has (resp. 100) classes and each class has 5K (resp. 500) training images. For STI.10, CIFAR10 and CIFAR 100, we artificially construct imbalanced training data, where we only keep the last 100 images of each class for the first half classes. 1Nturaallss20199 itself is an imbalanced dataset that contains 265,213 images with 1010 classes. We train ResNet-20 on STL1O, CIFARIO, CIFARI00, and Inception V3 on iNaturalist2019.
For fair comparison, we use the same constant batch size b for all methods except for RCIVR in which the inner loop batch size b' and outer loop batch size B₁ are hyperparameters that relate to convergence. We use the constant batch size b 128 on CIFARIO, CIFARIO0, and = 64 on iNaturalist2019, and b = 32 on STL. For RCIVR, both the fixed inner loop batch size / and the initial outer loop batch size Bg are tuned (32, 64, 128). The outer loop mini-batch size Bg also increased by factor of 10 per-stage according to the theory.
8

---

Table 2: Test accuracy (%), mean (variance), of SGD for ERM and RECOVER for DRO. Bold numbers represent better performance.
STL1O
CIFARTO
CIFARTOO
IMRATIO
SGD
RECOVER
SGD
RECOVER
SGD
RECOVER
0.02
(0.78)
38.08 (0.59)
65.36(0.64)
66.14 (0.48)
38.99 (0.62)
39.45 (0.56)
0.05
41.12 (0.94)
42.68 (0.60)
74.74 (0.71)
75.90 (0.33)
45.79 (0.69)
46.47 (0.66)
0.1
46.03 (0.96)
48.94 (0.86)
79.32 (0.42)
80,93 (0.31)
49.45 (0.50)
50.84 (0.86)
0.2
51.75 (1.14)
56.06 (1.26)
84.84 (0.51)
85,93 (0.14)
55.80 (0.74)
56.90 (0.42)
CIFARIO
Model
ImageNet-LT
Places-LT
CF (SGD)
41.29 (3e-3)
27.47 (1e-3)
Focal (SGD)
41.10 (2e-2)
27.64 (6e-3)
CATTICAL
DRO (RECOVER)
42.30 (4c-4)
28.75 (4e-5)
100
Figure 3: Left: Test Accuracy vs À on CIFARIO data; Right: Test accuracy (%) of finetuned models by different methods.
For RECOVER, the initial step size 77u and the momentum parameter dg at the first stage are tuned in 0..1,0.2.... 1), and 77 is divided by 10 after each stage and a is updated accordingly. For RCIVR, the constant step size is tuned 1) E {0.1, 0.2, ... ,1]. For the ASC-PG, the step size is set to be r = co/t², and the momentum parameter is set to be 3 = 20o/t², where co tuned from 0.01 ~ 1 and a, b are tuned ranging from 0.1 to 0.9 by grid search, is the number of iterations. For Stoc-AGDA, the step size for primal variable is set to be /,/(T. + 1) and the step size for dual variable p is set to be B2/ (T2 + (). 31, .3 are tuned in [10-1, 10, 10 500, 10x) and TI, 72 are tuned in [1, 10, 1 500, 10 For DESD and PG-SMD2, the algorithm have multiple stages, where each stage solves strongly- stage. For PES-SGDA, the number of iteration per-stage is increased by a factor of 10 and step sizes for the primal and the dual variables
strongly-concan
subproblem, and step size decrease after each
decreased by 10 times after each stage, with their initial values tuned. In particular, 7h (for primal variable) is tuned in 1.21, ..,... 1}
and Ta (for the dual variable) is tuned in {10-5, 6, 10-4, 10-3), To (the number of iterations for the first stage) is tuned in (5, 10, 30, 60} 8. where n is the number of training examples.
As we aim to compare the optimization for the same objective in this section, À is set to 5 both in the compositional objective (3) and min-max formulation of (I) with regularizer h(,, 1/n)) = E, p; log(np;). Following the standard training strategy, we run all algorithms 120 epochs and set the time threshold 150 hours for early stopping on iNaturalist data.
We compare testing accuracy vs running time and vs the number of processed training examples separately. We present the convergence of testing accuracy terms of running time in Figure [ and in terms of processed training examples in Figure 2 From the results, we can observe that: ()) in terms of running time RECOVER converges faster than all baselines on all data except on the smallest data STL10, which PES-SGDA has similar running time performance as RECOVER. The reason is that STL1O is the smallest data, which only has 3000 imbalanced training data samples and hence PES-SGDA has marginal overhead per-iteration; (ii) when the training data size is moderately large. the primal dual methods (PES SGDA, PG-SMD2, Stoc-AGDA) have significant overhead, which makes them converge much slower than RECOVER in terms of running time. On the large iNtturalis20199 data, RECOVER can save days of training time; (iii RECOVER is much faster than RCIVR all datasets; (iv) ASC-PG performs reasonably well but is still not as good as RECOVER in terms of both running time and sample complexity. The convergence instability of ASC-PG verifies the robustness of RECOVER for addressing the compositional problems.
6.2 Comparison between SGD and DRO.
We compare the generalization performance of DRO optimized by RECOVER with traditional ERM optimized by SGD for imbalance multi-classification tasks on STL.10, CIFAR10, CIFAR100. The IMbalance RATIO (IMRATIO) is defined as the number of samples in the minority classes over
9

---

the number of samples in the majority classes. We mannually construct different training sets with different IMRATIO, i.e, we only keep the last IMRATIO portion of images in the first half of classes.
Different from previous experiments, we tune À in a certain of range (1,5, 10, 20, 100) } by a cross- validation approach and report the best testing results. Other parameters of RECOVER is tuned according to the setting in previous experiments. We use ResNet-32 for CIFARIO, CIFARI00, and ResNet-20 for STL10. For SGD, the step size is set as no in the first 60 epochs, and is decreased by factor of 10 at 60, and 90 epochs following the practical strategy where 7oo is tuned in {0.1, 0.5, 1} and epoch means one pass of training data.
We report averaged test accuracy over runs with mean (variance) in Table We can see that DRO with RECOVER achieves higher test accuracy with smaller variance over multiple runs on all datasets than ERM with SGD. In addition, we report the results over 5 runs of different À on CIFARI 10 with different ATIO in Figure 3 (left). It is obvious to see that an appropriate regularization on the dual variable can improve the performance.
6.3 Effectiveness of RECOVER as a Fine-tuning Method
Fine-tuning high level layers from a pertained model is widely used for transfer learning and is also an effective method to update the models without increasing the computational cost too much when receiving new samples. For this purpose, we demonstrate that DRO is a better objective than the Cross Entropy (CE) loss and focal loss for fine-tuning on imbalanced datasets.
ImageNet-LT 29 and Places-LT 29 are two popular imbalanced data sets and are the Long-Taill Tailed (LT) version of ImageNet-2012
10 and Places-2 [54] by sampling a subset following the Pareto distribution with the power value 6. ImageNet-LT has 155.K images from 1000 categories, and Places-LT contains 62.5K training images from 365 classes. The head class is 4980 images and the tail class contains 5 images in both datasets.
To verify that DRO is a better objective and that RECOVER is an efficient optimization algorithm, we compare the test accuracy of the model trained with different objectives: DRO, CE loss and focal loss, where DRO is optimized by RECOVER and the other two losses are optimized by SGD. All methods start from the same pretrained model. We apply the ImangeNet pretrained ResNet152 as the pre- rre-trained model for Places-LT. For ImageNet-LT, we train ResNet50 using CE loss for 90 epochs following the standard training strategy proposed in [17] as the pre-trained model. We then fine tune the last block of the convolutions layer and the classifier layer for 30 epochs by using RECOVER for optimizing DRO and using SGD for optimizing ERM, respectively. The initial step size for RECOVER and SGD are both tuned in nJo {0.1, 0.5, 1}. For DRO, À is tunes in {1, 5, 10).
The test accuracy over runs with mean (variance) is reported in Figure (right). is clear to see that DRO optimized by RECOVER outperforms ERM with the CE loss and focal loss optimized by SGD more than 1(%) on both datasets. This vividly verifies the effectiveness of RECOVER as fine-tuning method on imbalanced data.
7 Conclusion
In this paper, we proposed a duality-free online method for solving a class of distributionally robust optimization problems. We used a KL divergence regularization on the dual variable and transformed the problem into two-level stochastic compositional problem. By leveraging a practical PL condition, we developed a practical method RECOVER based on recursive variance-reduced estimators and established optimal sample complexity. Experiments verify the effectiveness of the proposed algorithm in terms of both running time and prediction performance on large-scale imbalanced data. An open question remains is how solve the DRO problem with a KL constraint on the dual variable by a pratical stochatic algorithm without maintaining and updating the high dimensional dual variable. We plan to address this challenge in the future work.
Acknowledgments
The authors thank anonymous reviewers for constructive comments. This work was supported by NSF Career Award #1844403, NSF Award #2110045 and NSF Award #1933212.
10

---

References
[1] Zeyuan Ahu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameteriiation.. arXiv preprint 0rXiv:/8/1.03922 2018.
[2] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365, 2019.
[3] Barry C Arnold. Pareto distribution. Wiley StatsRef: Statistics Reference Online, pages 1-10, 2014.
[4] Robert S Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. In Advances in Neural Information Processing Systems, pages 2017.
[5] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly easy solving stochastic optimization. arXiv preprint arXiv:2008. 20Xi::0008.0047, 2020.
[6] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021.
[7] Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianhao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In International Conference Learning Representations, 2018.
[8] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Geoffrey J. Gordon, David B. Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS), pages 215-223 2011.
[9] Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pages 15210-15219, 2019.
[10] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image datahase. In 2009 IEEE conference computer vision and pattern recognition, pages 248-255. leee, 2009.
[11] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances in Neural Information Processing Systems, 33, 2020.
[12] C. John Duchi, W. Peter Glynn, and Hongseok Namkoong. Statistics robust optimization: generalized empirical likelihood approach. Mathematics Operations Research, 2016.
[13] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
[14] Saeed Ghadimi, Andrzej Ruszezynski, and Mengdi Wang. single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960 979, 2020.
[15] Zhishuai Guo, Zhuoning Yuan, Yan Yan, and Tianbao Yang. Fast objective and duality gap con- vergence for non-convex strongly-concave min-max problems. arXiv preprint arXiv:2006.06880 2020.
[16] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1)2248--2512,, 2014.
[17] 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, pages 770-778, 2016.

---

[18] Zhouyuan Huo, Bin Gu, Ji Liu, and Heng Huang. Accelerated method for stochastic composi- tion optimization with nonsmooth regularization. In Proceedings of the Thirty-Secone AAAI Conference Artificial Intelligence, (AAAI), pages 3287-3294, 2018.
[19] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances neural information processing systems, pages 315-323, 2013.
[20] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[21] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[22] Alex Krizhevsky, Ily Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
[23] Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[24] Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2020.
[25] Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. On tilted losses in machine learning: Theory and applications. arXiv preprint arXiv:2 (09.00144 2021.
[26] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for snnconvex-concaa minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
[27] Liu Liu, Ji Liu, Cho-Jui Hsieh, and Dacheng Tao. Stochastically controlled stochastic gradient for the convex and non-convex composition problem. CoRR, abs/1809.02505, 2018.
[28] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. arXiv preprint arXiv: 1908. 10831, 2019.
[29] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large- scale loig-tailed recognition in an open world. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 2537-2546, 2019.
[30] Luo Luo, Haishan Ye, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strroglyy-coom
minimax problems. CoRR, abs/2001.0377 1.37244, 2020.
[31] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint arXiv:1902.0000 /902.00/46. 2019.
[32] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in neural information processing systems, pages 2008-2216, 2016.
[33] Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in neural information processing systems, pages 1971-2980, 2017.
[34] Ion Necoara, Yurii Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. LIDAM Reprints CORE 3000, Universite catholique de Louvain, Center for Operations Research and Econometrics (CORE), 2019.
[35] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimizaaion, 19(4):5574- 1609, 2009.
[36] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takac. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning, pages 2613-2621, 2017.
12

---

[37] Gilles Pisier. The volume of convex bodies and Banach space geometry, volume 94. Cambridge University Press, 1999.
[38] Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Com- munications on Pure and Applied Mathematics, 6668):1275-1297, 2013.
[39] Qi Qi. Recover code for the paper. http://gghhaa.ooooooohhheeooooer 2021.
2021.
[40] Qi Qi, Yan Yan, Zixuan Wu, Xiaoyu Wang, and Tianbao Yang. A simple and effective framework for pairwise deep metric learning. In Computer Vision-ECCV 2020: 16th European Conference. Glasgow, UK, August 23-28, 2020, Proceedings. Part XXVII 16, pages 375-391. Springer, 2020.
[41] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max op- timization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02066 2018.
[42] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv: /908. 05659, 2019.
[43] Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018.
[44] Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2)4199449, 2017.
[45] Mengdi Wang, Ji Liu, and Ethan X Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, 18(1):3721-3743, 2017.
[46] Julie Wittmann, Derek Girman, and Daniel Crocker. Using inaturalist in coverboard protocol to measure data quality: Suggestions for project design. Citizen Science: Theory and Practice, 4(1) 2019.
[47] Yi Xu, Qihang Lin, and Tianbao Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Leurning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 3821-3830. PMLR, 2017.
[48] Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic gradient descent ascent methods for min-max optimization. arXiv preprint arXiv:2002.05300 2020.
[49] Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual algorithms with faster convergence than O(1/ /T) for problems without bilinear structure. arXiv preprint 1904: 10112, 2019.
[50] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimiza- tion for a class of nonconvex-nonconee minimax problems. arXiv preprint arXiv:2002.0066 09621, 2020.
[51] Tianbao Yang and Qihang Lin. RSG: beating subgradient method without smoothness and strong convexity. J. Mach. Learn. Res., 19:6:1-6:33, 2018
[52] Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates conver- gence of testing error over sgd. In Advances in Neural Information Processing Systems, pages 2604-2614, 2019.
[53] Junyu Zhang and Lin Xiao, A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pages 9075-9085, 2019.
[54] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A
10 million image database for scene recognition. IEFE transactions on pattern analysis and machine intelligence, 40(6):1452-1466: 2017.
13

---

[55] Yi Zhou, Zhe Wang, Kaiyi Ji, Yingbin Liang, and Vahid Tarokh. Momentum schemes with stochastic variance reduction for nonconvex composite optimization. arXiv preprint arXiv: 1902.02715, 2019.
[56] Dixian Zhu, Zhe Li, Xiaoyu Wang, Boqing Gong, and Tianbao Yang. A robust sem game framework for pool-based based active learning. In The 22nd international conference on artificial intelligence and statistics, pages 517-526, 2019.
14


Reviews:
[{"review_id": "xNZVT9IkpiV", "reviewer": "Reviewer_nTG1", "summary": "A new two sequence distributionally robust optimization algorithm and some modifications presented for a class of KL divergence regularized problems.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrength: + Online algorithm to solve compositional optimization problem in the context of deep learning.\n+ Does not require to store the high dimensional variable p.\n\nWeakness: - Writing can be improved quite a bit, and is some times unclear how exactly reformulations are defined or derived. \n\n\nJustification: The overall idea is that the inner maximization problem, under some technical assumptions, can be solved in closed form. The paper mentions this but does not provide. This part of the paper is not fully clear -- -- the optimal solution of the inner maximization problem depends on w, and so it is not clear how we obtain F_dro from (1). In particular, it is not clear how r(w) changes from (1) to (2). I believe it is correct, essentially it follows from convex duality but there is no justification given in the paper.\n\n\nIt is very interesting to see that simple estimators such as the one proposed where they maintain two sequences to compute the gradient of the composite optimization problem can provide optimal convergence for the overall optimization problem. And moreover, the paper also shows how to exploit smooth in terms of PL condition to match the practical deep network instantiations of the training algorithm.\n\nExperiments: The paper has fairly detailed experiments on a well studied classification task. The paper considers several other first order methods, and compares with some standard datasets including imbalanced datasets. The hyperparameters settings are described well and the algorithm may be implemented on standard deep learning frameworks by a practitioner from the description given in the paper. However, the experiments presented have nothing in connection with the theory presented. For example, the theoretical justifications presented are for the (expected) gradient norm and objective function values, whereas the experiments presented show convergence in test error. In this sense, in fact, (i) there are no experiments presented from an optimization perspective to valid the algorithm presented; (ii) even from the machine learning (generalization) perspective in the deep network context, the paper shows no experiments or even attempt to address some of the dependency relationship between the loss landscape and convergence, see https://papers.nips.cc/paper/2019/file/95e1533eb1b20a97777749fb94fdb944-Paper.pdf for example.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Have addressed them appropriately.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "rhcQO_0p-si", "reviewer": "Reviewer_pWxx", "summary": "This paper studies the family of distributionally robust optimization (DRO) problems with non-convex objectives and KL-divergence. With the motivation of improving the computational efficiency on existing methods and applying to online settings, the authors proposed a new duality-free online stochastic methods for solving the considered DRO problem. Theoretical analyses on complexities are provided for the proposed algorithm with and without a PL condition. Comparisons with state-of-the-art DRO methods are presented over ERM on imbalanced datasets.", "questions": "", "limitations": "", "rating": 7, "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": "The paper has a clear motivation of improving the complexities of existing DRO methods from a theoretical perspective. Comparisons are summarized clearly in Table 1 in the related work section. The structure of the paper is generally easy to follow, though many parameters and variables are defined to simplify the arguments. I appreciate that the authors lay out the list of required assumptions in Section 3. Overall, I think this paper is written with good quality and has theoretical contributions to the field of DRO. \n\nOne question I have for the paper is regarding the algorithmic design of COVER in Section 4. I have a hard time understand why the update rules of u and v designed in line 7 of Algorithm 1 lead to a better convergence result, compared with existing state-of-the-art methods for DRO. Can you briefly discuss the motivations for this algorithmic design?\n\nMoreover, I think the notations introduced in this paper seem to be a little bit complicated. It would be better to include a table to summarize the core parameters. Other suggestions regarding the paper are listed below:\n\n1.\tIt would be better to introduce some specific examples of typical DRO problems, apart from the general framework. This will help readers better understand the assumptions and the user cases for the proposed framework.\n\n2.\tAs for the experiments, is there any reason why you only focus on the imbalanced datasets? It would be great if you can provide empirical studies on other types of DRO problems, such as noisy data and adversarial data. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "lgkPGagOiMr", "reviewer": "Reviewer_WK9G", "summary": "This paper propose an online algorithm to solve a class of Distributionally Robust Optimization problem with non-convex objective functions. The standard primal-dual method typically suffer from optimization over high dimensional variable, which is impractical in many real world applications. The sota complexity of proposed method is provided with and without the PL condition. Empirical experiments demonstrate the superiority of the proposed algorithm.", "questions": "", "limitations": "", "rating": 6, "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": "This paper is in general well written, the complexity analyses and numerical experiments are seems to be promising. I only have some comments related to the model.\n\n1. The problem studied in this paper seems to be slightly different from the standard literature. For example, the problem in [1] aims to maximize probability distribution p over a KL-ball center at the empirical distribution, while the problem in this paper maximize p over probability simplex. As a result, the \\lambda in eq(2) is a fixed parameter, while in [1] we still need to optimize over \\lambda. So, intuitively, the problem in this paper should be easier to solve compare to standard KL-based DRO problem. From the modeling prospective, the model in this paper is less informative if we want to understand the relationship between regularization parameter \\lambda and the level of distributional robustness. \n\n2. Have the authors thought about generalizing the current framework to Wasserstein-based DRO (where the inner maximization typically do not have a closed form representation)? What would be the main challenges for doing so? ", "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": "2"}, "extra_text": {}}, {"review_id": "B_WjXJy2yyJ", "reviewer": "Reviewer_Hg8V", "summary": "This work proposes a practical online optimization method COVER and RECOVER for solving DRO with f-divergence, see eq(1).  They propose an online algorithm (RECOVER) for solving a more general formulation, by recasting the formulation into a composition minimization problem via fully exploiting the hidden structure. Moreover, they present the convergence result for the proposed method under the PL condition. Finally, the authors conduct experiments for several deep learning problems.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\nIn this paper, the authors consider an online method for distributionally robust optimization, which gets rid of the difficulty of high dimensional dual variable, which is usually used in the primal-dual type methods. The paper is overall well written and easy to follow. The main concerns raised by the reviewer are listed as follows:\n\n\n1. The title misleads the contents of the paper. The paper shows a particular regularized version of distributionally robust optimization (DRO) with f-divergence--which is not the general DRO problem, and develops a online method for this. Although the studied problem (the author claimed) is a generalization of the DRO problem, it seems that the problem eq(1) in this paper is a relaxed/ regularized form, which may sacrifice the advantages of DRO’s modeling power. Actually, the algorithm scheme developed in this paper doesn't actually really tackle DRO in the constrained case (i.e. when one constrains $D_{KL}(P||P_0) \\leq \\delta$, rather than a regularization-based formulation), which is the hard case and the case that most researchers in DRO actually consider.\n\nIn details, I think the paper [11] cannot support your claim. It shows that the DRO formulation is equivalent to a variance-based regularization form in an asymptotic sense. Compared to the formulation (1) in Namkoong & Duchi, 2016, the considered formulation in eq (1) penalizes the divergence measure into the objective function and adds a convex regularizer. Then, are these two formulations equivalent? We can only obtain the equivalence result under certain conditions, see the reference [1, section 4] for details. \n\n[1] Friedlander M P, Tseng P. Exact regularization of convex programs[J]. SIAM Journal on Optimization, 2008, 18(4): 1326-1350.\n\n2. The author claims that the proposed method can be applied to eq(3) with a non-smooth regularizer, the theoretical analysis using the PL conditions requires the regularization term to be smooth. In Assumption 3, the gradient notion has been invoked in the PL inequality. Could you please elaborate the details how your analysis can be trivially extended to non-smooth problems? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although there is some concern about how to best compare this work with prior efforts on robust optimization, overall it seems there are some interesting ideas and a new contribution presented that provides a more efficient alternative to standard distributionally robust methods.
Decision: Accept (Poster)