Stochastic Constrained DRO with a Complexity Independent of Sample Size
Authors: Qi Qi
Jiameng Lyu
Kung-Sik Chan
Er-Wei Bai
Tianbao Yang
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (06/2023)
Stochastic Constrained DRO with Complexity Independent of Sample Size
Qi Qi
q qi-qiouiowa edu
Deportment of Computer Science The University of lowa, Iowa City, 1A 52242, USA Jiameng Lyu"
lyjm21 @mails tsinghua edu.cn cn
Department of Mathematical Sciences
Tsinghua University, Beijiing 100084, China
Kung-Sik Chan
kung-sik- sik-chan whawwai edu
Deportment of Statistics and Actuarial Science
The University of Iowa, Iowa Cily, IA 52242, USA
Er-Wei
Wei Bai
er-wci--uri@uiieee..com edu
Department of Electrical and Computer Engineering The University of Towa, Towa City, TA 52242, USA Tianbao Yang
tianbao-yang Staamnnnnnntttnnao edu
Department Computer Science & Engineering Texas ABM University, College Station, TX 77849, USA
Reviewed on OpenReview: https: // openreview. net/ formmf id= VpaXrBFYZ9
Abstract
Distributionally Robust Optimization (DRO), popular method to train robust models against distribution shift between training and test sets, has received tremendous attention in recent years. In this paper, we propose and analyze stochastic algorit hins that apply to both non-convex and convex losses for solving Kullback-Leibler divergence constrained DRO problem. Compared with existing methods solving this problem, our stochastic algorithms not only enjoy competitive if not better complexity independent of sample size but also just require constant batch size at every iteration, which is more practical for broad applications. We establish nearly optimal complexity bound for finding e-stationary solution for non-convex losses and optimal complexity for finding an e-optimal solution for convex losses. Empirical studies demonstrate the effectiveness of the proposed algorithms for solving non-convex and convex constrained DRO problems.
1 Introduction
Large-scale optimization of DRO has recently garnered increasing attention due to its promising performance on handling noisy labels, imbalanced data and adversarial data (Namkoong & Duchi 2017 Zhu et al. 2019 Qi al. 2020al Chen & Paschalidis 2018). Various primal-dual algorithms can be used for solving various DRO problems (Rafique et al.) 2021 Nemirovski al.] 2009). However, primal-dual algorithms inevitably suffer from additional overhead for handling dimensionality dual variable, where is the sample size. This is an undesirable feature for large-scale deep learning, where n could be in the order of millions even billions. Hence, recent trend is to design dual-free algorithms for solving various DRO problems (Qi et al. 2021 Jin et al. 2021 Levy et al. 2020
In this paper, we provide efficient dual-free algorithms solving the following constrained DRO problem, which are still lacking in the literature,
min WEW
max : 1/pp1//)Spl
Σ pilí(w) XoD 1/n),
(1)
"Equal Contribution.

---

Published in Transactions on Machine Learning Research (06/2023)
where w denotes the model parameter, W is closed convex set, An {p R" denotes a n-dimenniooal simplex, 4 (ww denotes a loss function on the i-th data, Díp. -m)=E;= P: log(pm)) represents the Kullback-Leti and p is the constraint parameter, and Ao > is a small constant. A small KL regularization on p is added to ensure the objective in terms of w is smooth for deriving fast. convergence.
Ei= P: = 1.p, 2 0F
(KL) divergence measure between and uniform probabilities 1/n n E IR",
There are several reasons for considering the above constrained DRO problem. First, existing dual-free algorithms are not satisfactory (Qi et al.) 2021; Jin et al. 2021 Levy et al., 2020 Hu et al 2021). They are either restricted to problems with no additional constraints on the dual variable p except for the simplex constraint [Q ct al., 2021 Jin et al. 2021), or restricted to convex analysis or have a requirement on the batch size that depends on accuracy level (Levy et al. 2020 Hu et al., 2021). Second, the Kullback Leibler divergence measure is a more natural metric for measuring the distance between two distributions than other divergence measures, e.g., Euclidean distance. Third, compared with the KI-regularized DRO problem without constraints, the above KL-constrained DRO formulation allows it automatically decide a proper regularization effect that depends the optimal solution by tuning the constraint upper bound p. In other words, solving the constrained DRO with p offers the capability of optimizing the temperature parameter À in Eq. (2), which corresponds to the log-sum-cxponentinn
form with a temperature parameter À is widely used in many ML/A AI methods, e.g., constrastive self-supervised learning (Yuan et al. 2022 Qiu et al. 2023b Empirical studies have demonstrated that selecting an appropriate value for À is crucial for achieving good performance (Goel et al. 2022 Li et al. 2021a Radford et al.) 2021). Therefore, solving the constrained distributionally robust optimization problem provides the added advantage of identifying an optimal temperature during the training process.
The question to be addressed is the following:
Can we develop stochastic algorithos whose oracle complerity is optimal for both conver and non-conwex losses, and its per-iteration complerity is independent of sample size without imposing any requirements the (large) batch size in the meanlime?
We address the above question by (i) deriving an equivalent primal-only formulation that is of a compositional form; (ii) designing two algorithms for non-convex losses and extending them for convex losses; (iii) establishing an optimal complexity for both convex and non-convex losses. In particular, for a non-convex and smooth loss function (w), we achieve an oracle complexity of ((1/=² for finding an e-stationary solution; and for a convex and smooth loss function, we achieve an oracle complexity of O(1/²) for finding an c-optimal solution. We would like to emphasize that these results are on par with the best complexities that can be achieved by primal-dual algorithms (Huang et al. 2020; Namkoong & Duchi 2016). But our algorithms have per-iteration complexity of (d). which is independent of the sample size n. The convergence comparison of different methods for solving ( is shown in Table
To achieve these results, we first convert the problem
1 into an equivalent problem:
1 exp
(.(WW)
min min F(w, A) == Alog WEW A2
+ () Ao)p.
==ww]]ppm -w A E [R++1 as a single variable to be optimized, the objective function is a compositional function of x in the form of [(((x), where g(x) = En exp (((()) E R²2 and (()) = 91 log(g2) + 912. However, there are several challenges to be addressed for achieving optimal complexities for both convex and non-convex loss functions ((w). First, the problem F(x) is non-smooth in terms of x given the domain constraint w E W and X 2 Ao- Second, the outer function [g])ss gradient is non- non-Lipschtiz continuous in terms of the second coordinate 92 if À is unbounded, which is essential for all existing stochastic compositional optimization algorithms. Third, to the best of our knowledge, no optimal complexity in the order of ((1e²) has been achieved for a convex compositional function except for Zhang & LLa 2021 , which assumes f is convex and component-wisely non-decreasing and hence is not applicable to
By considering x =
16 omits a logarithmic dependence over
2

---

Published in Transactions on Machine Learning Research (06/2023)
Table 1: Summary of algorithms solving KL-constrained DRO problem. Complexity represents the oracle complexity for achicving E dist OF(x))] I other first-order stationarity convergence for the non-convex setting and [x -xx.)) S for the convex setting. Per Iter Cost denotes the per-iteration computational complexity. The algorithm styles include primal-dual (PD), primal only (P), and compositional (COM).
means not available in the original paper.
Sctting
Algorithms
Reference
Complexity
Batch Size
Per Iter Cost
Style
PG-SMD
(Rafique et al.
2021
O11/+t)
0(1)
O(n d)
PD
AccMDA
Huuang et al.
2020
0(1/6")
O[]
O + d)
PD
Non-convex
Dual SGM
Levv et al.
2020
O[1]
O(d)
P
SCDRO
(11/E*)
0(1)
O(d)
COM
This work
ASCDRO
0(1/e)
O(1)
O(d)
COM
FastDRC
Levy et al. 2020
O(1/e)
O(1/e)
0(2)
P
SPD
Namkoong & Duchi 2016
0(1/2)
0(1)
O(n + d)
PD
Convex
Dual SGM
Levy et al. 2020
O(1/2)
O(1)
O(d)
P
RSCDRO
0(1/2)
O(1)
O(d)
COM
This work
RASCDRO
O(1/E)
O(1)
O(d)
COM
To address the first two challenges, we derive an upper bound for the optimal À assuming that (((w) is bounded
for w E W, ie., E [No, λ], which allows us to establish the smoothness condition of F(x) and f()). Then we consider optimizing F(x)= = F(x) + 6x(x), where 6x(xx) = if X' = {x (AT w E W, E [Ao, Ål]. By leveraging the smoothness conditions of F and f, design stochastic algorithms by utilizing a recursive rarietio-reduction tochnique to compute stochastic estimator of the gradient of F(x), which allows to achieve complexity of Ō(L/e²) for finding a solution X such that E[dist(O, åF(x)) S e. To address the third challenge, we consider optimizing (x) F(x) /||x|| /2 for small μa. We prove that F,, (x) satisfics Kurdyla--ojjaiewwizz inequality, which allows to boost the convergence of the aforementioned algorithm to enjoy an optimal complexity of (11/<2 for finding e-optimal solution to F(x). Besides the optimal algorithms, we also present simpler algorithms with worse complexity, which are more practical for deep
learning applications without requiring two backpropagations at two different points per iteration as in the optimal algsrithms.
In the existing analysis of compositional optimization algorithms, either (i) the problem is assumed to be unconstrained, e.g., Qi et al. 20200a 2021), (ii) the complexity is sub-optimal, e.g., Ghadimi et al. (0200). or (iii) the problem is restricted, e.g., the outer function f is convex and non-decreasing assumed in (Zhang & Lan 2021 ). To the best of our knowledge, this is the first result for stochastic compositional optimization with a domain constraint that enjoys the optimal complexities for both convex and non-convex objectives.
2 Related Work
DRO springs from the robust optimization literature |Bertsimas et al.
2018 Ben- Tal et al.
2013 and has
been extensively studied in machine learning and statistics [Ahmadi-Javal
2012
Namkoong & Duchi 2017
Duchi et al. 2016 Staib & Jegolka, 2019: Deng et al., 2020 Qi et al. 2020b Duchi & Namkoong 2021 and
operations research (Rahimian & Mehrotra 2019 Delage & Ye 2010). Depending on how to const rain or regularize the uncertain variables, there are constrained DRO formulations that specify a constraint set for the uncertain variables, and regularized DRO formulations that use regularization term in the objective for regularizing the uncertain variables (Levy et al., 2020). Duchi et al. (2016) showed that minimizing constrained DRO with f-divergence including a x--divereence constraint and a. KT.-divergence constraint, is equivalent to adding variance regularization for the Empirical Risk Minimization (ERM) objective, which is able to reduce the uncertainty and improve the generalization performance of the model.
Primal-Dual Algorithms. Many primal-dual algorithms designed for the min-max problems Nemirovski
et al.) 2009 Juditsky et al. 2011 Yan et al. 2019 Namkoong & Duchi 2016 Yan et al.) 2020 Song et al.
2021
Alacaoglu el. al. 2022 are applicable to solving (1) when E is a convex function. For non-convex loss
2PG-SMD2 refers to PG-SMD algorithm under Assumption D2 Ratique al. 2021
FastDRO name of the GitHub repository of Levy al. (2020). we the name FRattDRO" th refer to the algorithm
based on mini-batch gradient estimator in Levy el (202
3

---

Published in Transactions on Machine Learning Research (06/2023)
functions, recently, Rafique et al. (2021) and Yan et al. 2020 proposed non-convex stochastic algorithms for solving non-convex strongly convex min-max problems, which are applicable to solving ( when e is a weakly convex function or smooth. Many primal-dual stochastic algorithms have been proposed for solving non-convex strongly concave problems with a state of the art oracle complexity of ((1/c²) for finding a
stationary solution (Huang et al. 2020 Luo et al. 2020 Tran-Dinh et al.; 2020). However, the primal-dual algorithms require maintaining and updating an (() dimensional vector for updating the dual variable.
Constrained DRO. Wang et al. 2021) studies the Sinkhorn distance constraint DRO, variant of Wasserstein distance based on entropic regularization. An efficient batch gradient descent with bisection search algorithm has been proposed to obtain a near-optimal solution with an arbitrarily small sub-optimality gap. However, no non-asymptotic convergence results are established in their paper. Duchi & Namkoong (202)) developed a convex DRO framework with f-divergence constraints to improve model robustness. The author developed the finite-sample minimax upper and lower bounds and the non-asymptotic convergence rate of (z) and provided the empirical studies on real distributional shifts tasks with existing interior point solver (Udell et al. 2014) and gradient descent with backtracking Armijo line-searches (Boyd et al.) 2004). However, no stochastic algorithms that directly optimize the considered constrained DRO with non-asymptotic convergence rates are provided in their paper.
Recently, Levy et al. 22000) proposed sample independent algorithms based on gradient estimators for solving a group of DRO problems in the convex setting. To be more specific, they achieved a convergence rate of tennsttrrann//egularrriini
Ø(1/e)) for the size of logarithmically dependent on the inverse accuracy level (log(1//)) with the help of multi-level Monte-Carlo (MLMC) gradient estimator. For the KT-constrained DRO objective and other more general setting, they achieve convergence rate of O11/e²) under a Lipschitz continuity assumption on the inverse CDF of the loss function and a mini- batch gradient estimator with a batch size in the order ((1/e) (please refer to Table 3 in Levy et al. (2020)). In addition, Levy et al. (2020) also proposed simple stochastic gradient method for solving the dual expression of the DRO formulation, which is called Dual SGM. In terms of convergence, they only discussed the convergence guarantee for the x"-regularized and CVaR penalized convex DRO problems (cf. Claim 3 in their paper). However, there is still gap for proving the convergence rate of Dual SGM for non-convex KT-constrained DRO problems due to similar challenges mentioned in the previous section, in particular establishing the smoothness condition in terms of the primal variable and the Lagrangian multipliers (denoted as x, U2 respectively in their paper). This paper makes unique contributions for addressing these challenges by (i) removing 1) in Dual SGM and deriving the box constraint for our Lagrangian multiplier À for proving the smoothness condition; (ii) establishing an optimal complexity in the order of ((1/e)) in the presence of non-smooth box constraints, which, to the best of our knowledge, is the first time for solving a non-convex constrained compositional optimization problem.
and CVaR-constrained convex DRO problems and the batch
Furthermore, it is noteworthy that the KL-constrained DRO formulation offers a distinct advantage over the KL-regularized DRO problem without constraints. Specifically, the proposed algorithms enable automatic determination of an optimal regularization effect for the constrained DRO (2) upon the optimizing of X, through the fine-tuning of the constraint upper bound p. This innovative approach has been empirically demonstrated to yield significant efficacy in the realm of contrastive learning, as substantiated by the findings of Qiu et al Qiu et al. 2023b).
Regularized DRO. DRO with KL divergence regularization objective has shown superior performance for addressing data imbalanced problems (Qi et al. 2021 2020a Li et al., 2020 2021b). Jin et al. [2021] proposed mini-batch normalized gradient descent with momentum that can find first-order e stationary point with an oracle complexity of (11c²)) for KL-regularized DRO and x² regularized DRO with a non-convex loss. They solve the challenge that the loss function could be unbounded. Qi et al. (2021) proposed online stochastic compositional algorithms to solve KL-regularized DRO, They leveraged a recursive variance reduction technique (STORM (Cutkosky & Orabona 2019 ) to compute a gradient estimator for the model parameter w only. They derived a complexity of O(1/e²) for a general non-convex problem and improved it to ((L((E)) for a problem that satisfies an p-PL condition. Qi et al. (2020a) reports a worse complexity for a simpler algorithm for solving KI-regularized DRO. Li el al. 2002 2021b) studied the effectiveness of KL regularized objective on different applications, such as enforcing fairness between subgroups, and handling the class imbalance.
4

---

Published in Transactions on Machine Learning Research (06/2023)
Compositional Functions and DRO. The connection between compositional functions and DRO formu- lations have been observed and leveraged in the literature. Dentcheva et al. (2017) studied the statistical estimation of compositional functionals with applications to estimating aanditional-valu--a--ri which is closcly related to the CVaR. constrained DRO. However, they do not consider stochastic optimization algorithms. To the best of our knowledge, Qi et al. (2021) was the first to use stochastic compositional optimization algorithms to solve KT-regularized DRO problems. Our work is different in that we solve KL-constrained DRO problems, which is more challenging than KI-regularized DRO problems. The benefits of using compositional optimization for solving DRO include (i) we do not need to maintain and update high dimensional dual variable as in the primal-dual methods (Rafique et al. worry about the batch size as in MLMC-based stochastic methods (Levy et al. 2020 Hu et al. 2021
measures,
2021): (i) we do not need to
Optimizing the Temperature Parameter. Our formulation and algorithm can be applied to optimizing the temperature parameter in the temperature-scaled cross-entropy loss, which has wide applications machine learning and artificial intelligence, c.g., knowledge distillation Hinton al.) (2015) and self-supervisod learning (Chen el. al. 2020). Recently, Qiu et al. (2023a) leveraged the optimization technique proposed in this paper for optimizing the individualized temperature parameter in the global contrastive loss of self self-superivsed learning.
3 Preliminaries
Let ||. denotes the Euclidean norm of a vector or the spectral norm of a matrix. And x= (wT Rd+1, (x) = exp(
Notations:
(i(w) X and g(x) E [exp(( (w))] where D denotes the training set and denotes the index of the sample randomly generated from D. Let fx(+) = Alog(-) + Ap, and V.x(gg) denotes the gradient of f in terms of g. Let (-) denote an Fuclidean projection onto the domain X'. Let
[ = (1..... T and T ~ [T] denotes a random selected index. We make the following standard assumptions regarding the problem (2).
Assumption 1. There erisls R, G, C, and L such that
(a) The domaón of model parometer W bounded such that there erists R > O it holds || R for ony E W
(b) (ww) is L-smooth, i.c., [[ve,())) -V(())) s L|w well. VW1, W2 W,iED.
(c) ((w) is G-Lipschitz continuous function and bounded by C, i.e., [V][( S G and [e((w)] S C for all W and i D.
(d) There exists positive constant A oo and an initial solution (W1.A1) such that F(W1,A1) min min F(w, A) A.
WEW AΝ
Assumption 2. Let og. Ovg be positive constants and 0² max(og,, For i E D, assume that (x) -xx)) og [ [ oz
Remark: Assumption (a), i.e., the boundness condition of W is also assumed in Levy al. 2020)) which is mainly used for convex analysis. Assumption bb, (c), i.e, the Lipstchiz continuity and smoothness of loss function, and the variance bounds for 9; and its gradient in Assumption 2 can be derived from Assumption (b), such that E[]lx((x) - = < (x]lg(())][] < exp( ()) and [x - (g(x)] < (x)
exp( 2C No (G² C
However, F(W,)) A) is not necessarily smooth in terms of x (w (wT.)) A) if X is unbounded. To address this concern, prove that optimal À is indeed bounded.
Lemma 1. The optimal solution of the dual variable X* to the problem is upper bounded by À -= No + CCpp where C is the upper bound of the loss function and is the construint parameter.
We would like to point out that the variance bound and the smoothness coustant LF exponentially dependent the problem parameters, so these constants in some other stochastic methods solving constrained DRO, like Dual SGM in Levy (202)).
5

---

Published in Transactions on Machine Learning Research (06/2023)
Thus, could constrain the domain of À in the DRO formulation the following equivalent formulation:
2
with the upper bound X and obtain
(((w)
))
exp Σe t=1
min min Aog wEW Áo
+ Ap.
(3)
The upper bound À guarantees the smoothness of F(w, A) and the smoothness of fx(),, which critical for the proposed algorithms to enjoy fast convergence rates.
Lemma 2. F(w, X) is Lp-ssmoth for any w E W and X E [An, λ}, where L. X + 2L + N&s, + +1+1 X. Lg and LV, are constants independent of sample size n and explicitly derived Lemma
Below, we let X' = {x/w= E W, Ao 0x(x) = 0 if E X, and 6x(x) oo if $ R. The problem 3 is oquivalent to
min xER0F1
F(x) = F(x) 5x(x),
(4)
Since is non-smooth, we define the regular subgradient as follows.
Definition (Regular Subgradient). Consider funccion T R - R and ((x) is finile at point &. For regular subgradient of t at x, written (0(x), if
vector V E I""
lim inf ((x) T(x) v (x x 0.
x X
Since F(x) is differentiable, we use 0F(x) VF(x) + 0xx(x) (see Exercise 8.8 Rockafellar & Wets (1988) in the analysis. Recall the definition of subgradient of convex function F which denoted by OF. When F(x) convex, we have åF(x) (F(x) (see Proposition 8.2 Rockafellar Wets (1998) The
dist(0, (x)) measures the distance between the origin and the regular subgradient set of at x. The oracle complexity is defined below:
Definition (Oracle Complexity). Let e O a small constant, the oracle complezity is defined as the number of processing samples z in order to achieve E0, OF())) S e for a non-convez loss function or E[F(x) - Fxx.)] S e for a convex loss function.
3.1
Equivalence Derivation
Before we move to the proposed algorithms in the next section, we derive the equivalence between equation between equations
and 3 Recall the original KL-constrained DRO problem:
Σ pili(w) D(p. 1=1
min WEW
max A 1/n)spt
where A, {p F" constant.
: R P: 1,0 S. 1), 1/n, is the KL divergence and Ao small positive EE
In order to lackle this problem, let first consider the robust loss
Σ [pl((w) A/pp
max D.p...Dpp.Ivi
And then we invoke the dual variable to transform this primal problem to the following form
min [pll(w)- - X(D(p, p) Do,
PEA, XZO ==1

---

Published in Transactions on Machine Learning Research (06/2023)
Since this problem is concave in term of p given w, by strong duality theorem, we have
Σ pili(w) X(D(p, 1/n) p) - AoD(p, 1/n)
max min Addn A20
min max A20 PEA,
Σ peli(w) - 1(D(p, - p) - 1/n(
i=1
Let = A Ao. we have
min max X20 PEA,
Σ
- (DD()))) pp) -10((p,1/m)
min max X PE
Σ pil((w) A(D(p, p) Aop.
Then the original problem is equivalent to the following problem
min min max WEW λ PEA,
E((((w) - A(D(p, 1/n) - p) dop.
Next we fix x (wT,X) T and derive an optimal solution pa (xxx which depends on x and solves the inner maximization problem. We consider the following problem
min PE
Σ pil((w) + AD(p.1/n).
which has the same optimal solution px(x) with our problem.
There are three constraints handle, i.e., p: 2 O, Vi and p; 1, and P:=pP: Note that the constraint p: enforced by the term pı log(p;)), otherwise the above objective will become infinity. As a result, the constraint Ps < is automatically satisfied due to Σ Ps = 1 and pi 2 0. Hence, we only need to explicitly tackle the constraint E Pi = 1. To this end, we define the following Lagrangian function
Lx(p, = - Eple(()
-E + log + Σ pt log(p))
+ M
P 1),
1=1
1=1
where y is the Lagrangian multiplier for the constraint E. 1 1. The optimal solutions satisfy the KKT conditions:
n
(w) A (log(p) (x)) + 1) + 0 and Σ (x) 1.
From the first equation, we can derive p7 (x) exp(e, (w)/A). Due to the second equation, we can conclude that p (x) (w)(A((w)/A) Plugging this optimal p" (w) into the inner maximization problem, we have
(w)(A)
(.(w) )) A
Σ p. (x)(((w) > logn n + Σ ps (w) log(p; Alog
Σ exp
i=1
Therefore, we get the following equivalent problem to the original problem
Σ exp (<(w)
)
)) Ap.
min min Alog
wEW A2
which is Eq. 2 the paper.
4 Stochastic Constrained DRO with Non-convex Losses
In this section, we present two stochastic algorithms for solving 4 The first algorithm simpler yet practical for deep learning applications. The second algorithm is an accelerated one with better complexity, which is more complex than the first algorithm.

---

Published in Transactions on Machine Learning Research (06/2023)
4.1 Basic Algorithm: SCDRO
A major concern of the algorithm design is to compute a stochastic gradient estimator of the gradient of F(x). At iteration t, the gradient of Fxx)) is given by
Fw = (ox,
(5)
vxF(x) (oxx)) log(g(X)) + p.
Both Vxg(x;) and (xx( can be estimated by unbiased estimator denoted by Vgi(x.). The concern lies at how to estimate g(xx) inside (-), The first algorithm SCDRO applying existing techniques for two-level compositional function. In particular, we estimate g(xx) by a sequence of st, which is updated by moving average 8t = (1 - 9)s, + (xt) Then we substitute g(x,) in Vw and (x)(x) with st and invoke the following moving average to obtain the gradient estimators in terms of we and de, respectively,
Vi (1 3)v + fx, (#t) Vwg((x))
(6)
Ut (1 - 3)4 (VV fx, (8t) Vxgi(x)) + log(ss) + p)-
Finally we complete the update step of x, by x (xx r7z)), where z, (v: uT)
Algorithm SCDRO(X,, V1, T1)
Algorithm 2 ASCDRO
T1)
Input: W1 E W, 2 λo, x1 (w],
1: Input: wi W, 2 Ao xi (WI ;T)
Initialization: Draw sample &1 ~ D, and caleu- 2: Initialization: Draw sample &1 ~ D, and calcu- late 81
late 81 exp((((w))/M))
VSa V E Rd
V1 (w)((x)) E ER, U1 (X)
"1 V (s) (51) (x) log(s1) +
3: for t = I,... ,T do
4: Update X = [Ixxx; r7z,), where is given
3: for t 1.... T. do
in
4: Update Xx+1 = 11xxxxx - 112))
Ze = (V ( V/A, V/A, + log(()) + D)
5: Draw a sample E D
5: Draw a sample & ~ D
6:
Let 81+1 = (1 3)8x + 3g, (x++1)
6: Update se+1, Vi+1, u141:
7:
Update Vi+1, u according to
V. = Vwgi(x;) + (1 -
V, (1 -3v,,-1+ OV JA (8t) (x.)
4, Vxgi(x,) +11 (8) (x
Ue (1 - 3)
8: (xx) + (1-B)(ss-1 - (x:(x(-))
+ (x) + log(s:) +
7: end for
8: end for
8: return: (x,, Vr, U, ,,,87, 87), where J ~ [T]
9: return: Vr, 87), where ~~ [T)
We would like to point out the moving average estimator for tracking the inner function g(w) is widely used
for solving compositional optimization problems (Wang et al. 2017 Qi et al.) 2021 Zhang & Xiao [019 Zhou et al. 2019). Using the moving average for computing stochastic gradient estimator of a compositional function first used in the NASA method proposed in Ghadimi al. (2020). The proposed method SCDRO is presented in Algorithm [ It is similar to NASA but with simpler design on the update of x We directly use projection after an SGD-tyle update. In contrast, NASA uses two steps to update X/+1- As a consequence, NASA has two parameters for updating X while SCDRO only has one parameter 17 for updating X(+1- It is this simple change that allows us to extend SCDRO for convex problems in the next section. Below, we present the convergence rate of our basic algorithu SCDRO for non-convex loss function.
Theorem 1. Suppose the Assumption and hold, and set B V 7i 2012 1 201
Then after running
Algorithum T iterations, we have E[dist(O, OF )) (624g² + 280A)
VT
Remark: Theorem shows that SCDRO achieves complexity of (11(c) for finding an e-stationary point, i.., (0,ist(O, (F(xx)) S e for a non-convex loss function. Note that NASA (Gaadimi et al. 2020) enjoys the same oracle complexity but for different convergence mcasure, i.c., E E|lly 2) xI z VF(x)]l < for a returned primal-dual pair (x,z), where y(x, z) X z). We can see that our convergence measure is more intuitive. In addition, we able to leverage our convergence measure to establish the
8

---

Published in Transactions on Machine Learning Research (06/2023)
convergence for convex functions by using Kurdyka-Lojasiewice (KL) incquality and the restarting trick shown in next section. In contrast, such convergence for NASA is missing in their paper. Compared with stochastic primal-dual methods (Rafique et al. 2021 Yan et al. 2020) for the min-max formulation ( their algorithms are double looped and have the same oracle complexity for a different convergence measure, i..,, [O (x(x))) S >21|x - x 1 S 6 for some returned solution x, where x, a reference point that not. computable. Our convergence measure is stronger as we diroctly mcasure E[dist(O, (l,ist(),,F(xx)) (x()))) on a returned solution X,. This is due to that we leverage the smoothness of F(.).
4.2 Accelerated Algorithm: ASCDRO
Our second algorithm presented in Algorithm 2 is inspired by Qi al. 2021 for solving the KT-regularized DRO by leveraging recursive variance reduced technique (i.e., STORM) to estimate g(w,) and Vg(w,) for computing V F(xe) and V in (5). In particular, we use v, for tracking V Vwg(xe), use ue for tracking Vxg(x;), and use 8t for tracking g (x),, which are updated by:
V. Vigi(x; + (1 -)
W1 (x.
(x,) + (1 (s 9x(x(-1)).
A similar update 8, has been used in Chen et al. (2021) for tracking the inner function values for two-level compositional optimization. However, they do not use similar updates for tracking the gradients Va, Us- Hence, their algorithm has worse complexity.
Then we invoke these estimators into V F(x,) and F(F( to obtain the gradient estimator
2: = (V/a, (s)( + log(s;) + +)
Below, we show ASCDRO can achieve better convergence rate in the non-convex loss function.
Theorem 2. Under Assumption and 2 for any a > 1, let k 2/2/3
Ly w = max(2o² (16T2,,:)) and
C= 14Lp3 + 1. Then after running Algorithm 2 for T iterations with (w+te2y173 and Br = =n we have Eldist (0, (F(x O
log T9/3
2 implies that with a polynomial decreasing step size, ASCDRO is able to find an esstationary solution such that EO (x())) S with a near-optimal complexity O(1/e)). Note that the complexity ()) is optimal up to a logarithmic factor for solving non-convex smooth optimization problems (Arjevani et al.) 2019). Statc-of-tho-art primal-dual methods with varianco-reduction for min- max problems (Huang et al.) 20200) have the same complexity but for a different convergence measure, i.e,
Remark:
Theorem
|| - 111--VF( (F
< e for a returned solution
5 Stochastic Algorithms for Convex Problems
In this section, we presented restarted algorithms for solving 3 with a convex loss function (w). The key is to restart SCDRO and ASCDRO by using a stagewise step size scheme. We define a new objective (x)x) = F(x)+ =||x1// and correspondingly Fx(x) = Fx(x) + (x(), where μ is a constant to be determined later. With this new objective, we have the following lemma.
Lemma 3. Suppose that lz(w) is conver for all then for all x E E, Fx(x) salisfies the following Kurdyka- Lojasiewicz (KL) inequality dist(0, (x)()))) 2 (x(FF((x) inf Fx(x)). xEX
Lemmna allows to obtain the convergence guarantee for convex losses. The idea of the restarted algorithm is to apply SCDRO and ASCDRO to the new objective (x) by adding µux, to
(V.2, ( (x) (s.) (s.)) + +ogg(+) + p) in Eq. {1) of Algorithm [ and substituting z, in (8) of +ux, and restarting SCDRO or ASCDRO with
(s:)u, + log(s;) + + a stagewise step size to enjoy the benefit of KL incquality of F,(x). It notable that stagewisc step size is widely and commonly used in practice. The multi-stage restarted version SCDRO and ASCDRO are shown A Algorithm 3 to which we refer restarted-SCDRO (RSCDRO) and restarted-ASCDRRO (RASSOD (RASCDRO).
Algorithm by z, = (Vfx, [ fA,

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm RSCDRO or RASCDRO
1: Input: W1 E W X = A
2: Initialization: The same as in SCDRO or ASCDRO
Let Aς = (xx: Vk: uks 8k)
for k: = 1,... K do
AR+1 SCDRO(A&, Il,; T&) Ak+1 ASCDRO(As, f]k Tk)
Change 17, Th according to Lemma 4 Lemma 5
7: end for
8: return: XK
5.1
Restarted SCDRO for Convex Problems
In this subsection, we present the convergence rate of RSCDRO for convex losses. We first present a lemma that states (xx) is stagewiscly decreasing.
Lemma 4. Suppose Assumptions and hold, (ww) is convex for alli, and
Fx(x) AA oc. 381c11
381e130 parx " },
1 and Tę- max ( Let 6 4u C ck-1/2, BR min 2a21 ,), T) min 12e13,021 12c13,
where 3. Run RSCDRO, then we have [X(F inf Fx(x)] S Ek for each stage k.
The above lemma implics that the objective gap (x+) infxxx (x) is decrcased by factor of 2 after each stage. Based on the above lemma, RSCDRO has the following convergence rate
Theorem 3. Under the same assumptions and parameter settings Lemma 4 after K = (c1(c)/((//)) slages, the oulpul of RSCDRO salisfies [F(F,(xx) - infxex (x)) S e, and the ovucle complexity is (11/p²))
As (xK)) - (x.)) S (x(xx) infxex (xxx,, where x, = arg F(x). Therefore, if after K stages it holds that (xF) - infxex F2 [x)] I c/2 with an oracle complexity of O(1/)²c), we have (xxx Fx S c/2, i.., B[F(xk) + μ |||x|| 11/2 /2- F(x.) [ulx)l -||xx_1///2 I c/2. By Assumption M W
is bounded by R, and then by setting = (2 + +X2)), with ||x||2 S (R² + 12) we have
(( - F(x.)] S c + (2(R² + +X2) < c <e
with an oracle complexity of O(1/E)), ie, the following corollary holds.
Corollary 1. Let μ = e/((((11 + +X)). Then under the same assumptions and perometer settings as Lemma 4 after K (log, (e)/)) stages, the output of RSCDRO satisfies [[ innfxxx F(x)] S and the oracle complecity is ((1/e).
Corollary shows that RSCDRO achieves oracle complexity of O(1/e²) for finding e-optimal solution. i.c., [[ - F(x.)] < for the convex loss function with a geometrically decrcasing step size in a
Remark:
stagewise manner.
5.2 Restarted ASCDRO for Convex Problems
In this subsection, we establish better convergence rate of RASCDRO for convex losses. Lemma 5. Suppose Assumplions
7 and hold, (,(w) is convex for all i, and Fx(x1) - infxex Fx(x) S MER
ypec Aμ < OC. Let G An,, Ck Ck-1/2, By = min ca c), Tkk minf 21cLPo2 21c22 and Ti max 192cLpg 192e1.p0² 192e1.2 }, where c 768L2. Run RASCDRO, then we have (xFx(x)) /e/" infxEx (x)) < ex for each slage k.
Mek
The above Jemma implies that the objective gap (x+, infxex F, (x)x]] is decreased by factor of 2 after each stage. Hence we have the following convergence rate for the RASCDRO.
Theorem 4. Under the same assumptions and parameter settings as Lemma 5. after K = ((ogz((/()) stages, the output of RASCDRO satisfies [E[F,(xx) - infxex [x(x] S 6, and the oracle complexity is O (max (1/pe, 1/23/2
By the same method of derivation of Corollary 1 the following corollary of Theorem 4 holds.
10

---

Published in Transactions on Machine Learning Research (06/2023)
Corollary 2. Let μ ( Then under the same ossumptions and porameter settings Lemma 5 after K = +0 (logg(<1/()) slages, the oulput of RASCDRO salisfies [F(((x)) - infxex F(x) S e and the oracle complezity is ((1/e))
Remark: Corollary 2 shows that RASCDRO achieves the claimed oracle complexity (L1/²) for finding an
<oppimal solution, which is optimal for solving convex smooth optimization problems (Nmirovsky & Yudin Finally, we note that a similar complexity was established in (Zhang & Lan 2021 for constrained convex compositional optimization problems. However, their analysis requires each level function to be convex, which does not apply to our case as the outer function fx(+) is non-convex.
1983
6 Experiments
In this section, we verify the effectiveness of the proposed algorithms in solving imbalanced classification problems. We show that the proposed methods outperform baselines under both the convex and non-convex settings in terms of convergence speed, and generalization performance. In addition, we study the influence of p to the robustness of different optimization methods in the supplement. All our results are conducted on Tesla V100.
Baselines. For the comparison of convergence speed, we compare with different algorithms for optimizing the same objective [ including, stochastic primal-dual algorithmms, namely PG-SMD2 (Raiqque et al. 2021 for a non-convex loss, and SPD (Namkoong & Duchi 2016) for a convex loss, Dual SGM (Levy et al. 2020 and mini-batch based SGD named FastDRO (Levy et al. 2020) for both convex and non-convex losses. For the comparison of gencralization performance, we compare with different methods for optimizing different objectives, including the traditional ERM with CE loss by SGD with momentum (SGDM), KL-regularized
DRO solved by RECOVER (Qi et al. 2021 ABSGD (Qi et al. 2020a Li et al. 2021b and Conat-oonttraieed, x" "erregulariiee//coonttttaii
DRO optimized by FastDRO.
Datasets. We conduct experiments on four imbalanced datasets, namely CIFARIO-ST, CIFAR100-ST (Qi et al., 2020b), ImageNet-ILT (Liu et al. 2019); ; and NNauualiss20188 (iNaturalist 2018 competition dataset ). The original CIFARIO, CIFARIO0 are balanced data, where CIFARIO (resp. CIFAR100) has 10 (resp. 100) classes and each class has 5K (resp. 500) training images. For constructing CIFARIO-ST and CIFAR100-ST, we artificially construct imbalanced training data, where we only keep the last 100 images of each class for the first half classes, and keep other classes and the test data unchanged. ImageNet-LT is a long-tailed subset of the original ImageNet-2012 by sampling a subset following the Parelo distribution with the power value 6. It has 115.8K images from 1000 categories, which include 4980 for head class and 5 images for tail class. iNaturalist 2018 is a real-world dataset whose class-frequency follows a heavy-tail distribution. It contains 437K images from 8142 classes.
Models. For a non-convex setting (deep model), we learn ResNet20 for CIFARIO-ST, CIFAR100-ST, and ResNet50 for ImageNet-LT and INaturalist2018, respectively. On CIFAR1O-ST, CIFAR100-ST, we optimize the network from scratch by different algorithms. For the large-scale ImageNet-LT and iNaturalist2018 datasets, we optimize the last block of the feature layers and the classifier weight with other layers frozen of a pretrained 5e model. This is a common training strategy in the literature (Kang et al. 2019 Qi et al. 2020a). For a convex setting (lincar model), we freeze the feature layers of the pretrained models, and only fine-tune the last classifier weight.. The pretrained models for ImageNet-LT, CIFARIO-ST, CIFAR100-ST are trained from scratch by optimizing the standard cross-entropy (CE) loss using SGD with momentum 0.9 for 90 epochs. The pretrained ResNet550 model for iNaturalis22018 is from the released model by Kang al. (2019).
Parameters and Settings. For all experiments, the batch size is 128 for CIFAR10-ST and CIFAR100-ST, and 512 for ImageNet-LT and iatuuralis12018. The loss function is the CE loss. The Xn is set to le-3. The (primal) learning rates for all methods are tuned in {0.01, 0.05, 0.1, 0.5, 1}. The learning rate for updating the dual variable in PG PG_SMD and SPD tuned in (le-5, 5c-5, 1e-4, 5e-4)). The momentum parameter & in our proposed algorithms and RECOVER are tuned {0.1: : 0.1 : 0.9). For RECOVER, the aaper-parameter À is tuned in (1,50, 100). The constrained parameter p is tuned in {0.1, 0.5, 1} for the comparison of generalization
11

---

Published in Transactions on Machine Learning Research (06/2023)
CIAARISST
CIARROOSST
Nesll
900 000
MOUR
04
8000
2-04 Pooccotnn Eximato
Figure Training accuracy (%) Testing accuracy (%) vs # of processed training samples for the convex setting. p fixed to 0.5 on CIFARIO-ST and CIFAR100-ST, and 0.1 on ImageNet-LT and iNaturalis(2018. The results are averaged over 5 independent runs.
CIARISST
CIFARIOSST
InageNNoAT
Niteralal018
TraapoNNer
Figure 2: Training accuracy (%), Testing accuracy (%) vs # of processed training samples for the non-convex setting. p is fixed to 0.5 on all datasets. The results are averaged over independent runs. performance unless specified otherwise. The initial X and Larange multiplier in Dual SGM are both tuned in 10.1, 10). All our results are conducted on Tesla V100.
Convergence comparison between different baselines. In the convex setting, we compare RSCDRO and RASCDRO with SPD, FastDRO and Dual SGM baselines. We report the training accuracy and testing accuracy terms of the number (#) of processing samples. We denote 1 pass of training data by epoch. We total of 3 epochs for CIFAR10-ST and CIFAR100-ST and decay the learning rate by factor of 10 at the end of 2nd epoch. Similarly, run 60 epochs and decay the learning rate at the 30th epochs for the ImageNet-LT, and run 30 epochs and decay the learning rate at the 20th epoch for iNaturalist2018. In the nonconvex setting, we compare SCDRO with two baselines, PG-SMD2 and FastDRO. We run 120 epochs for CIFAR10-ST and CIFAR100-ST, and decay the learning rate by a factor of 10 at the 90th epoch. And we run 30 epochs for ImageNet-LT and iNtturalist2018, and decay the learning rate at the 20th epoch.
Results. We first report the results for convex setting in Figures I It is obvious to see that RSCDRO and RASCDRO are consistently better than baselines CIFAR10-ST, CIFARI00-ST, and ImageNet-LT. PD-SMD2 and Dual SGM have comparable results with our proposed algorithms on the iNaturalis in terms of training accuracy, but is worse in terms of testing accuracy. FastDRO has the worst performance on all the datasets. RSCDRO and RASCDRO achieve comparable results on all datasets, however, the stochastic estimator in RASCDRO requires two gradient computations per itcration, which incurs more computational cost than RSCDRO. Hence, the non-convex setting, we focus on SCDRO. Figure 2 reports the results
12

---

Published in Transactions on Machine Learning Research (06/2023)
Table 2: Testing Accuracy in Convex Setting
ImageNet-LI
iNaturalist2018
KL-Constraint + SCDRO
24.08 (# 0.01)
55.63 (# 0.03)
Cant-Constraint + FastDRO
17.23 (#: 0.03)
54.52 (# 0.11)
x" --Rgularization + FastDRO
23.98 (#: 0.01)
55.03 (# 0.03)
X--Constraint FastDRO
23.61 (+ 0.01)
53.71 (+ 0.05)
Table 3: Testing Accuracy in Non-Convex Setting
ImageNet-LT
iNaturalist2018
KI-Constraint + SCDRO
43.74
65.59
ERM+SGDM
43.36
64.42
KI-Regulaiization + RECOVER
42.68
64.57
Kl-Reaularization ABSGD
43.44
65.01
for non-convex setting. We can see that SCDRO achieves the best performance on all the datasets. The margin increases the large scale ImageNct-LLT and iNtuualist2018 datasets. For the three basclines, Dual SGM has better testing performance than FastDRO and PD-SGM2 on CIFAR1O-ST and CIPARI00-ST. On the large scale data ImageNet-LTT and INaturalist2018, however, Dual SGM has the worst performance in terms of the testing accuracy. Furthermore, SCDRO is more stable than FastDRO and Dual SGM in different settings as the training of Dual SGM and FastDRO is comparable to SCDRO in convex settings and much worse than SCDRO in non-convex settings.
Comparison with ERM and KL-regularized DRO. Next, we compare our method for solving KL- constrained DRO (KL-CDRO) with 1) ERM+SGDM, and KL-regularized DRO (KL-RDRO) optimized by RECOVER, ABSGD in the non-convex setting 2) CVaR-constraineel DRO, x-rrgularized DRO x²- constrained DRO optimized by FRO in the convex setting. We conduct the experiments on the large-scale ImageNet-LT and INaturalist2018 datasets. The results shown in Table 2 and 3 vividly demonstrate that our method for constrained DRO outperforms the ERM-based method and other popular f f-divergence constrained//regulriiee DRO different settings.
Sensitivity to p. We study the sensitivity of different methods p. The results on CIFARIO-ST and CIFAR100-ST are shown in Table 4 in the supplement, which demonstrates that the testing performance is sensitive to p. However, our method SCDRO is better than basclines PG-SMD2 and FastDRO for different. values of p.
Table 4: Test accuracy (%) of different methods for different constraint parameter in the non-convex setting. The results are averaged over 5 independent runs.
P
0.01
0.05
0.1
0.5
PG-SMD2
67.09 (# 0.59)
66.96
(# 0.71)
67.12 (= 0.61)
67.36 (# 0.36)
67.10 (+ 0.61)
CIFAR1O-ST
FastDRO
65.41 (1: 0.33)
66.15
(1 0.09)
66.24 (= 0.63)
65.98 (1 0.45)
65.68
(1 0.52)
SCDRO
67.73 (1: 0.39)
67.58
(1: 0.48)
67.71 (1 0.43)
67.57 (4: 0.28)
67.96
(1 0.50)
PG-SMD2
57.31 (# 0.09)
56.44
(+: 0.17)
55.85 (= 0.19)
52.68 (+ 0.40)
48.72 (+ 0.25)
CIFAR100-ST
FastDRO
57.60 (#: 0.32)
57.20
(+ 0.42)
56.78 (= 0.40)
55.58 (+ 0.62)
52.39
(+ 0.31)
SCDRO
57.84 (+ 0.15)
57.60
(+ 0.15)
58.32 (# 0.43)
57.90 (+ 0.26)
57.71
(+ 0.24)
13

---

Published in Transactions on Machine Learning Research (06/2023)
7 Conclusions
In this paper, proposed dual-frre stochastic algorithms for solving KL-constrained distributionally robust optimization problems for both convex and non-convex losses. The proposed algorithms have nearly optimal complexity in both settings. Empirical studies vividly demonstrate the effectiveness of the proposed algorithm for solving non-convex and convex constrained DRO problems.
References
Amir Ahmadi-Javid. Entropic value-at-risk: A new coherent risk measure. Journal of Optimization Theory and Applications, 155:1105-1123, 2012.
Ahmet Alacaoglu, Volkan Cevher, and Stephen J Wright. On the complexity of a practical primal-dual coordinate method. arXiv preprint XXi:2201.0008, 2022.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint Xix: 02365, 2019.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions optimization problems affected by uncertain probabilities. Management Science, 59(2):34113) 357-7 2013.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Programming, (67( 292, 2018.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convez optimization. Cambridge university press, 2004.
Ruidi Chen and Ioannis Paschalidis. A robust learning approach for regression models based on distribu- tionally robust optimization. Journal of Machine Learning Research, 19(13), 2018.
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. doi: 00.1009/ssp.202133092333 URL https: org/ 1109/2Ftsp..p.o 2021 3092887
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference Machine Learning, pp. 1597 1607, 2020.
Ashok Cutkosky and Francesco Orabona. Moaeetummbbssd variance reduction in non-convex sgd. Advances in Neural Information Processing Systems, 11115236-15244 2019.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application data-driven problems. Operations research, 58(3):595- 612, 2010.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. Advances in Neural Information Processing Systems, 33, 2020.
Darinka Dentcheva, Spiridon Penev, and Andrzej Ruszczynski. Statistical estimation of composite risk functionals and risk optimization problems. Annals of the Institute of Statistical Mathematics, 69(4))737- 760, 2017. URL htttps://Ecopappeeteet wwwpaappeee.rreeeeeeeeeeeeeeeeee repec. org/ Re RePEc:spr:::: spr aistmt: 10 110463-016-0599-
C. John Duchi, W. Peter Glymn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 2016.
John C Duchi and Hongsook Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378-144) 2021.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Saced Ghadimi, Andrzej Ruszezynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. STAM Journal on Oplimization, (0(11)960-99) 19000-99,,99 2020.
Shashank Goel, Hritik Bansal, Sumit Bhatia, Ryan Rossi, Vishwa Vinay, and Aditya Grover. Cyclip: Cyclic
contrastive languago-image pretraining. Advances in Neural Information Processing Systems, 35:6704-6718 2022.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.0255 2015. URL https://arxiv httpps///rraii.orr//b///5...... 2tg/abbs/55030225111
Yifan Hu, Xin Chen, and Niao He. On the varinncciat tradeoff of stochastic optimization, In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Adoances Neural
Information Processing Systems, volume 34, pp. 22119 22131. Curran Associates, Inc., 2021. URL https;
pdf
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order momentum methods from mini to minimax optimization. arXiv e-prints, pp. arXiv-2008, 2020.
iNaturalist 2018 competition dataset. iNaturalist 2018 competition dataset.
https://giihubb.com
visipedia/inat. tetpeediaiiaattcoopteeeeeeeeeeee coopp/treeemaster/20188 2018.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization:
Non-asymplotic analysis. Advances in Newral Information Processing Systems, 34, 2021.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational incqualities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. arXiv preprint arXic:1910.08 0.09017,911 2019.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33, 2020.
Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi. Align before fuse: Vision and language representation learning with momentum distillation. Advances in neural information processing systems, 11:699497705 2021a.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. On tilted losses in machine learning: Theory and applications. arXiv preprint arXiv:2109.0614 2021b.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella Yu. Large-scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 2537-2546, 2019.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongg-coneee. minimax problems. Advances in Newral Information Processing Systems, 33, 2020.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization 2016.
with f-divergences. In NIPS, volume 29, pp.
Hongseok Namkoong and John C Duchi. Mariance-based regularization with convex objectives. In Advances in neural information processing systems, pp. 2971-2980, 2017.
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for paint problems. Journal of optimization theory and applications, 142(1 (1: 228, 2009.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. STAM Journal on oplimization, 19(4):1574-1609, 2009.
A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. A Wiley- Interscience publication. Wiley, 1983. ISBN 9780471103455. URL http:://books.ggggee..oooo id=6ULVAMAMMAAJ
Qi Qi, Yi Xu, Rong Jin, Wotao Yin, and Tianbao Yang. Attentional biased stochastic gradient for imbalanced classification. arXio preprinl or (ixx:X012206990 2020a.
Qi Qi, Yan Yan, Zixuan Wu, Xiaoyu Wang, and Tianbao Yang. simple and effective framework for pairwise deep metric learning. In Computer Vision-FCCCV 2020: 16th European Conference, Glasgow, UK, August. 23 28, 2020, Proceedings, Port XXVII 16, pp. 375 391. Springer, 2020b.
Qi Qi Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for a class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34, 2021.
Zi-Hao Qiu, Quanqi Hu, Zhuoning Yuan, Denny Zhou, Lijun Zhang, and Tianbao Yang. Not all semantics are created equal: Contrastive self-supervised learning with automatic temperature individualization. In Proceedings of International Conference on Machine Learning, volume abs/2300 22305.11963 2023a. doi: 10.48550/ 111555//aXXiv2222/2 aat/aa.ivv....1.111
URL https:///oi.ors
18550/arXiv. 2305 11965
Zi-Hao Qiu, Quanqi Hu, Zhuoning Yuan, Denny Zhou, Lijun Zhang, and Tianbao Yang. Not all semantics are created equal: Contrastive self-supervise learning with automatic temperature individualization. ar preprint Xiv:22335 1 11965, 2023b.
Alec Radford, Jong Wook Kim, Chris Hallacy Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. Tn International conference on machine learning, pp. 8748 8763. PMTR, 2021.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex concave min max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, pp. 1-35, 2021.
Hamed Rahimian and Sanjay Mchrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:190s. 056659 2019.
RT Rockafellar and RJB Wets. Variational analysis springer. MR1491362, 1998.
Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In International Conference on Machine Learning, pp. 9824 9834. PMLR, 2021.
Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems, 32:9134 9144, 2019.
Quoe Tran-Dinh, Deyi Liu, and Lam M Nguyen. Hybrid variance-reduced sgd algorithms for minimax problems with nonconvex-linear function. In NewrIPS, 2020.
Madeleine Udell, Karanveer Mohan, David Zeng, Jenny Hong, Steven Diamond, and Stephen Boyd. Couvex optimization julia. In 2014 First Workshop for High Performance Technical Computing Dynamic Languages, pp. 18 28. IEEE, 2014.
Jie Wang, Rui Gao, and Yao Xic. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109. 11926, 2021.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, (61(1-2):419-44 449, 2017.
16

---

Published in Transactions on Machine Learning Research (06/2023)
Yi Xu, Rong Jin, and Tianbao Yang. Non-asymptotic analysis of stochastic methods for non-smooth non- convex regularized problems. In Proceedliggs of the 33rd International Conference on Neural Information Processing Systems, pp. 2630 2640, 2019.
Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual algorithms with faster convergence than O(1/VT) for problems without bilinear structure. arXiv preprint arXi::1944.10112, 2019.
Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for min-max optimization. In Conference on Newral Information Processing Systems, 2020.
Zhuoning Yuan, Yuexin Wu, Zi- Qiu, Xianzhi Du, Lijun Zhang, Denny Zhou, and Tianbao Yang. Provable stochastic optimization for global contrastive learning: Small batch does not harm performance. International Conference on Machine Learning, pp. 25760-25782. PMLR, 2022.
Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pp. 9075 9085, 2019.
Zhe Zhang and Guanghui Lan. Optimal algorithms for convex nested stochastic composite optimization. Ar e-prinls, arXiv:2011.10076, 2021.
Zhou, Zhe Wang, Kaiyi Ji, Yingbin Liang, and Vahid Tarokh. um schemes with stochastic variance reduction for nonconvex composite optimization. arXiv preprint orXiv:1902.02715, 2019.
Dixian Zhu, Zhe Li, Xiaoyu Wang, Boqing Gong, and Tianbao Yang. A robust zero-sun game framework for pool-based active learning. The 22nd international conference on artificial intelligence and statistics, pp. 517 526. PMLR, 2019.
17

---

Published in Transactions on Machine Learning Research (06/2023)
A
Preliminary Lemmas
Lemma 6. For 1, fx(9) = Alg((g) + Ap is Lss -Lipschitz continuous and L -smooth, where L
L/2- =
Remark: gi(w, A) exp( ( 2 1 as 1 Ao E R and ((w) 2 0 in problem Thus g(x) 1 - gi (w( A) 2 Then by this lemma we have [Vxx(((x)) S X and [Vfx(g(x)) {[ [(x)]| for X1, X2 X.
vfx(g(x)))] -
Proof. For any q 2 1, we have
Vf((g) = S
And for any Q1 92 2 we have
A 1 S
m (2)
Vix(()) - V=2(12))1 -
S 221
91
This complete the proof.
Lemma 7. Let LA = expl exp(x) + 1b),, LB = ex + $ Lo exp( (xp(()( ( and LD
exp( C (00 (0"-22nC) 9e (w, is L Lipschtz continuous and -myoth in terms of (w, A), where L. exp( ( (( C + )) and Lv, = L + 1 + L3 + D.
Au
Proof. The gradient of gi (w, X) is given as
V ww,A9:(W (w, A) = WWwi:(W A) V (w, A])
(((w)
V [wl((w)
(((w)
(((w)
exp
exp
X2
Then by Assumption 1 we have
(((w)
(
[w(((W)
(w)
w/V.,gg.W, A)ll S exp
+
x2
AZAO
C
G
C
exp
+
Ao
Ag
x
Thus, Lg exp exp (2))
C
C xg
For for all (w, A), (w', X²) E X, we have
V w. (w, - V Vw,AdilW', (1))
((w)
Vwl(ww)
(((w')
V
(ww'(w')
exp
+exp
X
X
((())
(((w)
(4(w")
(s(w) 12
+
exp
12 exp
X22
4 (ww)
V
(wl((w)
(c(wW)
(wee(w") 12
1
exp
exp
A
(a(w')
Vwli(w") exp
L (w('))
Vwl((w")
+
exp
X
X
X
((w)
((w)
(((w')
(((w))
2
+
cxp
exp
X2
(x(w')
L((w')
(e((w)
(((w")
+
exp
exp
X2
X
X/2
18

---

Published in Transactions on Machine Learning Research (06/2023)
To bound the first term, we first check the Lipschitz continuous of exp( ( (w) with respect to w,
V
exp
((()
(wf((W)
Vw
(:(w)
V Vwli(w) )
V (wwli())
(((W)
1/
exp
+
oxp
À
A
A
11
((w)
V (wl
V (wl((w))
){
(i(WW
[
exp
exp
A
A
A
(.(w))
[wl((w)
||xp exp
(((W)
(((((w) A
exp
+
A
A
1
C
G²
exp
A
+
Ao
LA.
where equality (a) is due to the property of the norm of rank-one symmetric matrix and inequality (b) is due to Cauchy-Schwarz inequality.
Therefore, we have
|oxpl (i(w), Vili(w) A
Vnta(w')/ (((w'), exp(
- LA ||
w/1 ww1?
A
A
A
Furthermore, it holds that
(w) (wfi(w) A
exp
((W))
((w)Vwl((N)
(((w)
V [wl((w)
exp
+ +exp
(
V V
13
X2
C
CG
G
S exp
+
= LB
to
1/
X
V
exp
(.(w)
(((w) x
Li(w)
(((W) V (W))
(((w)
Vwla(w
exp
exxp
Vw
A3
X2
C
CGG + Ao
S
eepp
LC
A0
V
exp
<:(w)
((w) x²
(i(w)
((())
((((w)
28,
exp
A + +exp
V
23
C
O 2ApC
S Sexp
= Ln.
An
21
As a result, we obtain
W,,,A9:WW, A) - Ww.Ag((w', x')1?
LA | -w'l2 13 /| -X112 13 |w w'12 +LD M1A -XI?
(T'3 + [26) |w-w//" + +T/ + +13))))00 M| -X12
< (I') + 12 + 12 + +1) (w (wT,)) ,) -WWT, .x)112
Thus Lv, = L 11 + 12 + T.P.
Lemma 8. F(W,)) A) is Lp-smooth, where LF XL3++ + +24 + XLV + +1+ X.
Remark: Lemma
6 7 and Lemma g imply that TNiA Lia Top, Ty S Tp and L 2 1.
19

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. For all X1 (wi A1) X2 (w2. A2) E X, and let d(x) (0, 0,,0g(((()) + p) eRot! by
expansion we have
[V - VF(x))]
( d(x)) (
(V -/4.0//))))))/////0o/oo////1/))0 1og((((2))))
& (1
+ (1 - (oxx (gxx)) - g(x2))
Noting the Lipschtiz continuous of g(r)) and Vg(x), obtain
[V FF(x)]l
$ (L Lg + ()))(x1) - g(x2)و + [Vg(x,]]
11 - >ell + 1s, [VV([1))))) - Vo(xe)]
g(x2)
(4)
IL fn1 L3 + |1] x211 + [| )Il A21l + Ling L7, ||,1 xx21
< (I
1,9 + 2T. + T1 |,, )1,) x2
(6)
2 (AL 2g + ÄLV, +1+ X) |x| -22l--
where the incquality (a) is duc to g(x2) 2 and the incquality (b) is due to the upper bound of Thus,
Lp XL2 g + 2Lg + Nlv +1+
A.1 Proof of Lemma
Proof. Recall the primal problem:
p¹
max D(p.,,.Dp..//sss 1=1
Σ
( + DDp, 1/m).
Invoking dual variable X, we obtain the dual problem:
9 min max
End((w CiDi--(DDppppi 1/n) - p) Ao 1/n).
(9)
X20 PEA..
Set p= (1/n...., 1/n), which is Slater vector satisfying 1(p.1/m) P 0. Applying Lemma 3 in Nedić
& Ozdaglar 2009), we have
1 P 9 - 1/n)
Since the primal problem concave in term of p given w, we have p' = q² Thorefore,
A² <
p p,l)(w)
Σ (ww) Do - --ree (w)
i=
(10)
where the last inoquality because [e)(w) S C E W. Let X = A do: we have
Eplli(w) - X(D(p, 1/n) - p) - -App.
min max x PEAn
Section will also show
1
n
A (((w)) + +Npp - -po).
9"
min X log
exp
X
ni
By Eq. (10,, we have the optimal solution of above optimization problem |사*| < [5+++ Ao do + C which p.
complete the proof
20

---

Published in Transactions on Machine Learning Research (06/2023)
B Proofs in Section 4
B.1 Technical Lemmas
Lemma 9. Suppose Assumption holds and DD and s are initialized with 81 = exp( (
Then for
every (T) we have
2L Xe+1 xr|1 + 8 0²02
B[llg(x+1)) - s1+1119 s E
(1 (1- ()1lg(x)) - ssll? +
Taking summation of (lllg(x(+11 s1+1l1 from to T, we have
Σ [lll((x)) =s S (x1) - s1ll2
2L T
+
9
Σ
|x++1 - x BTO2
(11)
8
Proof. Note that 80+1 = 0(1=0(1--0) B)st + Boi (x++1) and [[(((x++)) - 9 (x++)]]=0, then by simple expansion we have
B[llg(x++1) 82+1|1²]
1=1118(((x++1) 9i (X++1) + +11 (1- (xx((+)))+ - st)
19(x+))( D: (x(+1)) )1 + (1 - 3)9119(x(+1) se 2
+ (g (x(+1))) - (x(x(+1) g(x++1) st5
| (g((++1) 9: (x++))ll + -1- (1-13)(lg(x++)) g(xx) g(xx) - -
(12)
Invkoing Lemma
Eq. 12
and recalling Assumption we obtain
E (111)(x++1)
s
1888 [g (x(+++))== - g (x(++))) (1- 6) ())l((()) sell
+ (1 + )1 (19(((( -
2I [ xil1?
E
8 (11(( (x++1)) (11 (1))))(((xi)) - -8e12
3
(1 (1--8) ())o())) s1112 213 x - xxll2 + 1202
E
B
where the inequality (a) is due to b)² < (1+ (1+ (1+ 1)b,, the inequality (b) is because of (1- < 1,
(1 + }) < and the Lemma and the inequality (c) is from Assumption
Lemma 10. Under Assumption 1 Algorithm with MLF 1/4, and then the output XR of Algorithm satisfies
2 + 40L Exldist(O, (F()))
2A
40
||z VF(x))1 +
T/T' +
(13)
T
T
Proof. The proof of this lemma follow the proof of Theorem 2 in Xu et al. 2019
Recall the update of X is
X
(xx 172))
arg min + (z.. xi) + - -|1x x x2
xerdi1
2n
21

---

Published in Transactions on Machine Learning Research (06/2023)
then by Exercise 8.8 and Theorem 10.1 of Rockafellar & Wets 1998 we know
2t (xi+1 Xx) E ddx (x++1),
which implies that
VF ((+1)
(x1-1 xx) E VF (x++1 + 06x (x(+1) = O (x++1).
(14)
"
By the update of X++1, we also have,
(x(xx+1) + (2+11+11 Xc+1 - x1) + 21
||x+1 xxel2 S oxx(x)).
Since F(x) is smooth with parameter LF, then
F(x+11) S F(x,) + (VF(xx), - -x,) + LF || - xx11²
2
Combing the above two inequalities, we get
Z VF(xx), X1+1 x1) (1/n- - 1) x112 S =F(x)) F(x(+1).
That is
2 (1/n Lr)lx(+1 - x1113 F(x.) - F(x++1) - (z. - VF(X,), X4+1 -xi)
F(x)) F(x(+1) + +m|lz - VF(x))]1 + 4n ||x x+t1l1
where the last inequality uses Young's inequality (a, S ||a||2 + lbb inequality and summing it across t = 1,............. -.. T, we have
Then by rearranging the above 1
2 |xc+1 xil1? s F(xi) F(XT+1)
41)
- F(x))
inf F(x) + Σ 71/2 VF(x:)1
XEX
T
$ A +
Σ
nllz - VF(x)111
(15)
t=1
By the same method used in the proof of Theorem in
Xu al. (2019).
we have the following inequality,
T
T
24
1t VF(x++1) + (x x1)11 <
(x(x111
t
1=1
(16)
3LF
(2L
X441 x1112.
Recalling nLe S 1 and combining Eq. 15 and Eq.
16
we obtain
1
1 12 VF(x++1) + (xx+1 - xx)
1
2
|z, 22(x))1
24
+
5LF
M + 17 Σ
mp pollz -VF(x))11)
17
1/4 M/FF/
1=1
(b)
T
2A
|Zz VF(x))1
+ 40 4F Σ |zz - VF(x))1
(17)
where inequality (a) is due to (2L 3Le)
GLE and inequality (b) is due to 1/4-q1.772
1 S 8.
Recalling Eq. 14 and the output rule of Algorithm we have
1
1 VF(x++1) 1 -x)111x)))1 x2)
(0,0Fst
(18)
T
22

---

Published in Transactions on Machine Learning Research (06/2023)
Then by combining Eqs.
17 18
together have the Lemma.
Lemma 11. Under Assumption
1
2
run Algorithm
with v S
B
S 1- 4L.
and then we have
1hr 142012
2E
[
VF(x))]1
A
20L 1E| g[ s1l1?1 24.T.p0p?
- VF(x))1)
BT
n/T
3T
Proof. To facilitate our proof statement, we define the following notations:
(x(x)) P(x) VAF(x))) (V/2. VIx (xx
+ log(g(x))) +o +p)
T (V.5. + log(o(x)))+
G(x,) = -Gw,, (x,) GA. (x.)
(V, (x, (s log(s,) + +p).
It is worth notice that (x:)l = (x.)).
For every iteration I, by simple expansion we have
I F[I[V z: [
= =E||V (x,) - (1 - -) BG
= =B]I[(1 - (VF(())) - VF(x + (1 (1--8)VFF) 3)V
-VFxx- 3G(x:)
=B]I(1 B) (VF(x)) (F(x-1)) + (1 B) (VF (x(x))1)) Z:-1) 1
+ BBIIB((F(( - C(x,)) + 3 (VF(xx) F((x)) 12]
= =[((1 | + (1 -
+ 2 () C)- 23(1 - (), + - ()3(B. C) +2 -)
+ 28
(0) [1((1 - 2 (00_:
+
2,3 D)}, + 2 - (A, B) 2 - -3)3(C, B) - C) +
where the equality (a) is due to E(VF(x)) - VF(xx)) - VF(x)) = 0 and B(2-11 VF(x,.), VF(x) Fxx))) =0
By Young's 's inequality, we have (1 (1-3) B) (1, 1 ULMي' |B 28 B)C <
---0)2 | + 23 2. C)) < (1 11 BC and 2,2 D) < + D11
2 Therefore, noting (1 - B) 1 and 1/8> 1,
obtain
4 s E[ (11))) (1 B)| + 11 + DD1
+ 3 11412 + (1 (1-8)33 1B | + (1- 3)23 (1-3)23
2
||B112
2
+1 - 11-8) + + +
$ E[( - 3) | ||11p+5511011 53 23 D
4
(19)
23

---

Published in Transactions on Machine Learning Research (06/2023)
Thus recalling the defintion of G(x,), FF(x)), VF(x)) and applying the smoothness and Lipschitz contimuity
of fa and y, we have
C -
= V...(((())) [x)
< ( +og(g(x))) - (s:) - log(s;)]1
+ (V
VfA (x)) + fx. (o(x,))Vaa( (x, + log( 1=)
(
21 /x. || - (xx))11 + 21 -
(20)
where the inequality (a) is due to [log(((x))) log(s:)) I |st g(xx)l since g(x,) 1, N for all
t= (1,... 7 by the definition and initialzation of (x,x)), 82, and the inequality (b) is due to L 1/,1,1 fx,
+1 S DTp
And by the similar method, also have
D = I|VF(x,) Fx())
+ [o [IV (x)e)
+ log(g(xx)) - V. (l log(o(x;)) pll
+ (x)) - (g(x))
< 4,,, (x())) - (xx)) 2 < | (x( - [x,(11
(21)
Thus combining the Eqs.
19
20
21 and applying Assumption 2 we can obtain
[F[|2 2 (x,)))
4
= E[( - B) 11 VF )1
VF - VF(X
558 G(x.) + 2 [F(x) (1x
4 - - x (l((x)) - -ell? 2,3 2,32L 13.02
< E[(1 1)1 (x( +
Taking summation of E[[ V Fx ||9] from 1 to T and invoking Lemma
have
T
E Elllz, VF(x))111
[((x)(()))
21113)
4
+
E[[ [[11 x1 10L
Σ B[llo(x)) s 23² Lyo²
82
E[1 V Fx))) 21113
A
[[| x
3
8
[g ) - 81 11
2L
T Σ
+ +10L
E
+
g
|x+1 - x11
+ +STT²² +23L,TT0
3
g
1=1
24

---

Published in Transactions on Machine Learning Research (06/2023)
Taking Eq.
15 into the above inequality, we have
T
El 24 - V1(
(x1 - 21
A
20L
1
A+n Σ
T
Blll VF(xx)1191)
B
B2
B2
1/4 nbr
t=1
(x) - -11131
+ 10T
BT
23
8
(4)
B[I)F((x1)
2i 11
20
817
+ 11
Bl zz VF(x))11))
3
82
82
[x1g - $1
+ 1
+ "T622
+ 2322
8
(6)
21
FF(x))113
+
+
T
zt - VF(x:)1
21
2
t=1
[x1] - =11
+ 10L7
+ BTo²
+ 201
(22)
where the inequality (a) is due nLf S 1/4 and the inequality (b) is due to 8(4L3
2
8 S 2
Rearranging terms and dividing T on both sides of Eq. 22 we compelte the proof.
B.2 Proof of Theorem 1
Proof. Since 2013.
8
Lr 2 and LF S Lg, it holds that S
4LF which satisfy the
ALFY /
2020
assumptions of in Lemma 10 and Lemma 11 Therefore, combining Lemma 10 and Lemma 11 [O,ist {x())))
we have
2 40L0P
2A nT
40L T
Blllz
VF(x,))
+
T
t=1
12
24
20Lr
E 1t
VF(x))]11
T/
T
24E 1 VF(x))1
12A T
240 [llgg(x)) s1
2A
20L A
288173300
(23)
BT
3T
nT
T
By the definition of 81 and Assumption 2 it holds that
B[[ls1 [|x < -
(24)
Since g fs1 S 13 and 212 fM1
12
L3, we have
Ellla1 [
(oxx
(
- XAAp:///)DDAAA////////..///////1 V.A. (
(a)
<
- vg(x1))
< <(21 2T.,, )0² < 0Z
(25)
where the inequality (a) is due to la bll < 2||a|| 2
25

---

Published in Transactions on Machine Learning Research (06/2023)
Combining Eqs. 23
24
25
we obtain
(0 (xx))
24E
VF(x))
12A
2401 - -111
2A
2013
+
+
3T
nf'
BT
T
12A
240L
2A
20
+288L
3T
n/T
3T
1/
T
240
52
40
20
F
F
VT
VT
VT
vT
T
LE
20
$ (6240 280A)
+
VT
This complete the proof.
C Proofs in Section 4.2
C.1 Technical Lemmas
Lemma 12. Let 2, VSx, (8t q + 94, where qe = (v, u.) 9x = -0 log(s1) + P)T and 0 E Let
| = ||:: g(xx)]12 [|v, vwg(xx)]1= +lu -Vag(x)12 Under Assumption 1 run Algorithm and then
for every t t (1, ..} we have
1zc (
Proof. By simple expansion, it holds that
|zz
FF(x))11 (olx (s).vvl
([ - ()), + log(g(x:)) - log(s:)]1
2 V wx) - V/A 2/lp:////2
(s),uul)
-x]g((x)) 12
(o ( Vg(x:) V/2 (x)) 2 + s1113
(26)
where the inequality (a) is because ||a + b s 2 b and log(x> - log(t)) S |r vl for all x, 2 1.
Applying the smoothness and Lipschitz contimuity of fA and 9, we obtain (o(x)) (s)
(Vs,()())))VV((() V v/)
S (1( - V
< 22/24 || 2xx))12 2 + 2T, //q 2 - 121..
(27)
Noting |/q. [ = || V gw:(x:))l" 1 -xg(x))) and combining Eqq.
26
27
have
1z: - VF(x))11
< (4L34E, fx. + +2)]1ss: - g(xx))1 + 4L2 |/ Vg(x1)11
< 41211s1 - g(x:) 41711q: - Vg(xx)
(1 - g(x,) ) 2 + I02 1 -wwg(x)) )112 + +lue 1 vxg(x))
This complete the proof.
Lemma 13. Under Assumption
run Algorithem and then for every 1 {1, (1....T) we have
< (1 [.) 8(1 L [E[||x++1 11 +65,0?
26

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. Since St+1 (g:(x(+1) + (1 (s: (x(x))) ) it holds that
|||| [xx++)]]]
- = (x+l)((x++1) + (1 1 -t 9x(x)) s(x
I BiIl(1 - (.) - gxx)) + (x
- (x(+1))
+ (1 - (x)((())++) (x(()) - (0(x(+1) g(xx))))11
= E[(1 11) 9(xx) (g (x(+1) 9(xx-1))
(28)
+ (1 (x((() (x()) - (9(x(+1) -g(x))))l
where the last inequality is due to (x+x()++1) [(x++1)] = 0.
Noting (x((()++1) - (x(x+)))
- g(xx)))) = (g - g(xx)))11 and applying the Lipschitz contin-
uty of 9i (x), we have (x(1x(((+11) -
- (g(x++ ((xx))11
(x(((=((x+1)) 9: (x++1)11 [[(((x+1) - (xx)))]1 -2 2 (gx(xx-1) (xx+1)), g(x)))]
(x((() -
(x: (x(+1))) (1((((+))++))))))))))))))))))))) -
S (xxx)))1
S [|xx11 - xz 13.
(29)
Combining Eqs. (28 29 and invoking the Lipschitz continuty of g((x), under Assumption
we have
B[||s++1 1(x++1)l1
$ (1 B[]s =1
+ -20 ((1)))/9++((-))))((((((((( (xx+1)) (0(x(+1) - g(xx))11
-
+ $ (1 - B.) Bills - -l -, - xx.
(30)
In the same way, also have
E|[lv++1 (wg 1 )1 $ (1 ) + F + 2( - B,)2 Bil| [1||x ,
- xe|1"1.
(31)
El (xg(x(+1)) ) || < (1 - B VxO(x;) ) 2 +
- -
B ,
x011
(32)
Therefore, combining Eqs. 30 32
31 we obtaín
|[|| || S (1
[ x 1|3] 6.9 + 4(1 3,) 3 (T + 1, |x++1 - xx x2
$ (1 [ x [1 8(1 3 X+++ x, || 6,330²
where the last inequality applies
(r& + 12)) < 2 This complete the proof.
Lemma 14.
Under Assumption and for any a > 1, let k ad 2/3
LF w = max(20? (16L3k)) and
o² c= 141.ph + 130L4. Then with me (1) 3r = en and after running T iterations, Algrithm satisfies
E | |
E 1 3
4L4 T B| x 1915
Σ
66 162 + 6413A.
Yo
T/
Proof. Since 2 (16L},))3, it is easy to note that
1
M
S no S
S
16L2 ALF
In addition,
Br = oni < cT. <
+ 1100
14L
256
O²L3
65
1
65
<
1.
14 256L
128
14a 25561
128
27

---

Published in Transactions on Machine Learning Research (06/2023)
With 77 (w+to2)1:33 obtain
&
1
1
(w + +wo2/222/3 - (w (t - 1)02)//8 (a)
a²
7)
7/-1
k
3k(w + (t 1)02)2/3
(6)
0²
0²
22/3
3k(w/2 2 + to2)2/3
3k(w/2 + to /2)2/3
3k(w + to2)2/3
22
(0)
22/3
3/3 n
12Lpk3 S
7Lk n!:
where the inequality (a) uses the inequality (x + y) 1/3 13 v
y 2/3
the inequality (b) is due to w 2 20
and the inequality (c) is due to Tp S ILP
Noting 3t en and 0 S (1 Be) I 1, by Lemma
13 have
|| x |
[
T)-1
(1 3,)3
8(1 - B,)
||
6c21)/02
TE X,+1 x,11
77-1
8(1 - 3,) B11 X - xx|1
< (mi 11 11,-1 - 20Th 2c1x)BB(l1 x
1 + 6c 66211 1/002 +
+ 8(1 - 2
-260T x 11 6220)000
| X - x,113}
(33)
where the last inequality is due to 1/2 Taking sunmation Eq.
n-11
2cn S FL
2(
IaLpk3 + 13004))m S -600L4
o²
33
from to T, we have
E
x ||
E X7 1 [1
T
260 n E[|
24
11
6o
Ge2 0²
8L3
110x441xx1110
(34)
i]u
7T
17
1=1
In the same way with Eq.
15
and Te S 11 Vt 2 1, we could also have
1 1 2m
2mp
Xx- xe112
||x++1 x1|
Th 1 VF(x:)11
(35)
41/-
Noting LF S 1/ and invoking Lemma 12
we obtain
T
T Er VF(x))1
4
B[||x++1 x111
(A +
1
20p L,p
[=1
84 +
mELll [
$ 8A + 32L Σ ncBil>>1111 112).
(36)
Combining Eqs.
34 36
we have
Ri[l [||1
E 1||10+++11? [|
1
4
EeE x4 19]
+ Σ
Gc 1020 + 64I3A
(37)
This complete the proof.
C.2 Proof of Theorem 2
Proof. Noting the monotonity of ne and dividing
1/4 1/4-m/.f/2 on both sides of Eq. (35 we have
1
X141 x11
m m
Iz
VF(x))12
(38)
1/4
LF
1=1
28

---

Published in Transactions on Machine Learning Research (06/2023)
By the same method used in the proof of Theorem 2 in Xu al. (2019)
have the following incquality,
( F(xx))
1 VF(x++1)+ + T
(x, xx+1)ll < 21|z [F(x))1
+
7t
3LF
+ (2L
||x(+1 x11
Multiplying Th on both sides of the above inequality and taking summation from to T, we have
T
Me 1zl VF(x++1) + 1
-x xx)11
(a)
1
M + m Σ np Zz VF(X))) ))
T7 ll|ze VF(x))]1 + +2 + 5LF 1/4 MLF/2
12
ne nel1z: VF(x,)11 + 12A,
(39)
where incquality (a) due to (2 aLg) s 5Lg, inequality (b) due m Lr S and 1/2-m S
Combining Eqs.
37
39
and invoking Lemma 12 we have
ne|1z: - V Fx(++)) + (x1+1 x1
1}t
T
S L
Σ
1 x4/1 13] + 12A
t=1
E |||1>1 ||
E +
T + 641.7
< 12
Σ
6o
+ 124
(40)
1/0
T/
Noting the monotonity of n and dividing Tyr on both sides of Eq.
we obtain
1 - -(x++1 x1)]
[x(+++))+ +
T/t
t=1
B B|1|20++111 [||| 121
TWT Σ 6c 6 0 64L7A
12A
12
(41)
To
Tur
TuT
Combining Eqs.
18
41 and noting Σ
v/2 S Ologg T), we get the conclusion that
El (F(x)))
El|lz VF(x++1) + (xx+1 x;)
7
E B|||21 [|
+ Tur Σ 1p2 + 64L2A
12A
< 12
+ Tmm
Tirroo
Tnp
log T
$ 0
72/3
This complete the proof.
D Proofs in Section 5
D.1 Technical Lemmas
Lemma 15. If ((w) is conver for all i, can show that F F(w, A) is jointly conver in terms of (w, X).
29

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. We have
F(w, A) max pE
pili (w) A
Σ ps log(nps) p) Aop.
G(w.A.p)
Since G(w, P) is jointly convex in terms of (w, X) for every fixed p. F(w, A) is jointly convex in terms of A).
Lemma 16. Under Assumption 1 run Algorithm with S 41. SIFV9Hi 94201 S GLF and apply SCDRO to
the new objective (x) by adding pxt to V.J.(())) V.A, (s+) V (x.( + log(s1) + p)T in Eg. 7 of Algorithm [ where y is a small constant determined later. Without loss of the generality, we assume and then we have
K 2
2B[
(F,(())
A nT
20 2 s1 + 24.I220²
E Blll - (x)())
+
3T
ST
Proof. To facilitate proof statement, define the following notations:
[x)(x)) = (xx)) T,
(xFu(xx))
(o(x) aw,, log(0(x pdx))
(X.)
=
+
pdve)
Gx(X))
(V. + uww V (x)(())) + log(s:) + + pde). It is worth to notice that (x,) = (x,)(x)).
= (Gw,
Since F(x) Lmsothhh then we have (x(x) is LF,, -smooth, where LF, = (LF + p). Noting LF > 1 and a S 2 we obtain Lr + μ S 3 T.p. For every iteration i, by simple expansion we have
VI (x:) 1=
||||| VIIIFAA (x,))) - (1 -
= [E] ()(VF, - VF, + (-- -
-E]]I(1 ()(VF, - (x,(xx + (VF, - 2111)11
+ ((II - Gx(x)) + (VF - (x
= [1 B) VF (X.) VF, (x,-)) + - B) (VF(((-1) - zc-1) 119
B
+ E ( G(xx)) + 3 (VF(x)) - F((x)) 1.3.
The above inequality shows that the only difference between 4 the proof of Lemma II and 4 in the proof of Lemma 16 term A.
Therefore, by the same method used in the proof of Lemma 11 have
z (x;
V. (x1) 12
4L2
20L2,L3
F
A +
3
B2
182
1/4
LL
12
[=]
[x]lg((x)) - 1
10
STO2
+.3.33
30

---

Published in Transactions on Machine Learning Research (06/2023)
By LF LB and nLF, I ZnLF I 1/4, it holds that
Billz (x+(()))1
B|ll F(Il))((x1) 2111
201
T
E Blllz VEL((x)191)
817
A 1?
8
B2
B2
B1)lg(x1)
s1113]
+ 101
+ +,TT0²
+ 2T3
B
Z
An
T
+
Σ
Billz - (F)(X))1
8
21
2
1=1
B(llg(x))
- 81
+ 10L3
+ STO²
+ +23L2TTO
(42)
where the last inequality is due 899 20L Rearranging terms and dividing T' on both sides of Eq.
42
we complete the proof of this Lemma.
Lemma 17. At the k-th stage of RASCDRO, let Bg cn and c 512L we have
=1 Ta + 6,,0²² 647
E Ellz (x.,(x))
(43)
T
TR
where 4 = (x((s)) - inf infxex Fx(x).
Proof. Recall the definition of || and by the same proof of Lemma. 12 we have
|| Iz
(xx))) < 4 111
(44)
Denote at kth-stage x and by Lemma
13 at the kth-stage in RASCDRO we have
B||l
x
++1 1|2 z (1 - 3x) x + 63302² 2 8 3x) X - x,|?
s (1 - (1- x 1 + 6300
(1 2(0)
+ +8T7 B2)
11 B& Bz)2(1- 1((-0))|xx+1 x;11
1=1
S (1 - 22 |1
+ 6.
(45)
+ 811 3a)² Σ
(1 3x)
2(t b) || x:1
Combining Eqs. 44 45
we obtain
T
1
E 2
(x,(1)
4L2. Tk
Th
<
- B1113a) 11 + 63 + (1 -B,)71(xe+1 [
T
< Tx
1
Σ
(1 - (1- 2 2 x 11 68.02 + 8I,2 -
(1 - 3x)
xx11
31

---

Published in Transactions on Machine Learning Research (06/2023)
Noting Σ/= (1 2x)
11/3g and invoking Eq. (38 we have
Tv.
1
Elllz (x:()111
T
t=1
8L7 - Bx)2
6.3g0²
Σ
Blll x[11 xcll²]
Tx
+ 8 - -3x)2
63,00²
77
B| + 17k
E El V VFL(2)1111)
BxTK
1/4 - The P222
21
6 Tr
+ 6,,,0²
+
1z
V (x
BxTK
B&Tr
8xTI's
where the last inequality is due to 1/(1/4- - T7 22)
S 8, (1 3x)² S 1, 2g + L - 213..
Invoking 3x = =c and c 576L4 to above inequality, we get the conclusion that E 2 1
Th
B Blllz - (F((x))11
Ta + 6,,0²
8 T
Bx Tk
D.2 Proof of Lemma 3
we know F(x) is convex. And thus by the definition of (x) we have (x) is a strongly convex function. Then by strong convexity, we have
Proof. Since (:w)) is convex for all i, by Temma
15
Fu(y) (x) + (y -y-x)
" x) / x vx,y E xF
v X,
Then
inf F (x) XEX
2 min Fx((X) v (y x) + 11
2 fly x
yEA
2 min Fy (x) + v (y x)
2 lly x||²
y
|
(x(
Vv (F,
24
Hence,
|v||
2 Fx(x) - infxex Fy (x), Vv (x),,), which implies 24
dist(0, OF, (x))² 2 2p (Fx(x) - F2 (xx))
D.3 Proof of Lemma 4
Proof. We use inductions to prove [[[[2 - V (xx))) S pex/4, B(llg(xx) sx|P9 S uex/4 and B(Fu(xx)) inf F2 [x)] S Ek. Let's consider the first stage in the beginning. xEx
Let 6 = A., thus (x) - infxex (x)] I é1. And we can use a batch size 4/pe, for initialization.to make sure ((, - 2 2 < p60 1 81 g(x1) & /4.
Suppose that Elllg (x) -4-11 || < /4,-1/4, El|la-1 (x,((xx-)) < μEg-1/4 14 and EXF
1Ek 1 infxex Fx(()] S 6k-1 By setting Bk-1 min 3841300 381L } 7 min 4008L.022 4608 and T
uck
max 17ee
1474561 14
}. it is easy to obtain that 7h-1 5
8 4LF 9
Therefore, invoking Lemma 16 we
32

---

Published in Transactions on Machine Learning Research (06/2023)
have
2k V (xx)
Tk-1
Blllz b2
(x)(()))
E 1
(F
B
1k-1 11
+
+ +4 L3,0²
8x 1
7T k-
3x TT
1
6k-1
5 Rk-1
1
2 Tk-IT
Without loss of the generality, we consider the case 1 I 1. By definition have Bk-1
pC p (M3-1/38413.00) Ikk-1 = peck (MGx1/(46088770)) and Th-1 = / (12 which imply
1
and 243x- 11700 < μ
B S
38
Tk-176-1
32
16
Then, note LF 1, 1 and EY Ek-1/ 1/2 we have
Ellla- - [F(((x)]1]
p
PACk-1
5p ck-
JACK-1
768L7
16
384LF
8
μ
5YEER
μEE 1
768
32
192
16
PACk:
j.c
J.Ck
J.C
+
192
16
40
8
U.C
Next we need to show Bill((x)) sx|13] ues/4 under the assumption that [[]gg(x--1) -k-11131 S uck
By Lemma
g have
Blllg( xx) - sk 1x
T
Tk-1 [[]gg(x)) stll3]
[E (x119(xx-1) - 8k-1 11:1
2L3
Tw-1
B[[xx+1-- -x,1 + Bx-102
B
1 1
2L2
Tx-1
Billz VFL(x()111) ))
1EE
B[AK-1] + MJ
4 Tx-1
TK-1
1/4
7h 1
+ 10²
where 1/1 = F2, (xx-1) infxex (x(x). With 1/(1/4-1) - 1114--nk-LFF/)) 88 [.[[[[(xx-]] - sk-11121 s pEk-
and (x inf x (x)] $ Ek-1; it holds that
1613
B (x]g((x*) sx1l 1111 2.8--IT-- 1
-Bk-102
Th-TT
B3
1221Ex11
1-quEk-1
μeg
MEE-1
384177
288T17
361.p
192T.7
33

---

Published in Transactions on Machine Learning Research (06/2023)
Invoking Lemma
10
at (k- 1)-th stage (k > 1) we have
E diiss (x
+ 40Lr,, 1K
Tk
2 k-
40 B
Eiilz - (x)(1))
Tk-1
17- 1T-
Tk-1
1=1
(2 F0LF, MKk
PEE--
2ck-1
40LFF ck-1
4
1A-17A-1
Tk-1
197
u.k.
(OLF,,URK1
+
192
8
147456L
$
2pck:
where the second inequality is due to Lr, 1k-1 S (3/2)Tr7)-1 S 11/1536.
Since (xx:)) S (xxx and infxex (x) infxex (x), applying Lemma we have
1 _ E[diitt(O, (xx,
2/1ER
(x,) - inf (x)] - (xx) inf [x(x]] - xEX
Ek
xeX
2/1
2/1
This complete the proof of this Lemma.
D.4 Proof of Theorem
Proof. Invoking Lemma then after K = (logg((1/ee) stages, we have
(xF) inf xEX (x)] SeK= 2K-1
Since Ek= 2 = -1(/e), the overall oracle complexity is
Th + μe1
S 36864 L1
+
1.
k=2
36864o
K
1
+
life
2
JA61
k=1
1
$
00(
1126
D.5 Proof of Corollary [
It is easy to note that (xxx - (x.) S (x(x) - infxex (x),,, where x, = argmin F(x). Therefore,
if after K stages it holds that B[F2 infxxx Fz S c/2 with an oracle complexity of O(1/p²c), we have (xk) (x.)) S <e/2,
i.e., B[F((x) + + /2- F(x)) - [2/2 S Se/2. By Assumption
W is bounded by R, and then by sctting μ </ x2)), with ||x < RR² +²) we have
E[F(xx) F(x.)] - 2
E + (2(R² + x2)) s + Sc
with oracle complexity of 0(1/e)).
D.6 Proof of Lemma 5
Proof. We use inductions to prove [|] 11 < μel/16Lž and [[F,(xx)
inf Px(x)] Eg. Let's consider XEX
the first stage the beginning.
Let é An, thus [[F infxex (x)) 61. And can use a batch size of 48T, uud for initialization to make sure Elll > | E[[ls: ((x)) + [[ Vwg(x1) 1|1 |u1 vxO(x:)) < uel /1662
Suppose that El| -4 1 < 166-1/16L2 and (x - infxex (x(x < Ck-1. By setting 8 V/
min ( 168-1 7651 768t., }, 7/K-1 min 74 184321 and TR-1 = max 1.772 /ER-T"
1474562
14745611.0
147456L
p66-1
34

---

Published in Transactions on Machine Learning Research (06/2023)
Then following the above Lemma 17 for & 2
1,
Tk
E
Blilz - (x;))11
4L Th
1=1
2E x
112]
128L E E
k- 7h
+ 12
B 1
3 38-1Tx-1
1 + -2
pek
1002
128 E 1111-111
3k-1
Without loss of the generality, consider the case 1EE-1/02 S 1. By definition we have 3x-1 which imply
(Ex-1/(76SL2o0*)) Mパ-1 /
1
M and 1233o²
MCB-1
3x-1 T--
96L
Th- TT-1Th-1
8
64L7
Then, noting LF 2 1, f1 < 1 and Ej 1x-1/2
we have |(
166-1
E
384L +
64L
6912L
F
pkck
Juck
1.6.
1
32L
3456L2
juck
16L7
Then by Eq. 444. we have ||z (k: 1) we have
(FF((x)111 & 4 1|2 - pcx/4. Invoking Lemma 10 at (k: - 1)-th stage
E Eddist (0, (x.(F(()))))))
2 + F0LF 17k
T2-1
2 k-1 1]
40LF B
Billz - (x,)))
Th-1
7TK Tx-1
T
(2 + 40Tr, MK
1)NEK-1
26k-1
40T 6k-1
7--1
Tx-1
773μER
μER
40LF.HER-1
768
73728T.7
< 2pck:
where the second inequality is due to Lp, 7 7k-11 S (3/2) S 1/3072.
Since (xxx S (xx) and infxex (x(x) infxex Fx(x), applying Lemma have
E[F, inf [x)] (x+) inf Fx(x)] 1
211ER 24
E|dist(0, OF (x+))
Ck.
xEX
xEX 24
This complete the proof of this Lemma.
0
D.7 Proof of Theorem 4
Proof. Invoking Lemma then after ((log2((/()) stages, we have
[lF,(x)) inf (x)] S EK 2K-I =c.
E1
xEX
Since Σk= 2 O(1/c), the overall oracle complexity is
K
T
48L7
o
Σ
max
1 11122 (Ex
48L7
pel
pec
JACI
K
2tt
f 11312 ((ch ))
V2"
48L2
0
Σ
max
Lal
0
max
juc we
35

---

Published in Transactions on Machine Learning Research (06/2023)
This complete the proof.
E
Derivation of the Compositional Formulation
Recall the original KL-constrained DRO problem:
Σ - Ao, 1/n),
min WEW (PEA, 1pppp//5M))
max
i=1
where A, = (p E R" E = 1,0 & ps S 1), D(p, 1/n) is the KL divergence and An a small positive constant.
In order tackle this problem, let first consider the robust loss
max D 1/ pil((w) Ae 1/n).
And then we invoke the dual variable to transform this primal problem to the following form
max min [illi()- - X(D(p, 1/nn) - p) - DD, 1/n). PEAn A20 i=1
Since this problem is concave in term of given by strong duality theorem, we have
max min pil((w) A(D(p, 1/n) - p) - >oD(p, 1/n) PÊcn X20
1=1
Σ pil((w) X(D(p,1/m) - p) 1/D(p.1/m)
min max A20 PEA,
Let = X Ao we have
min max
Σ pili(w) - X(D(D, p) ADD 1/n) X20 PEA.
min max Σ pl((w) X(D--(DDPppp) 1/m) p) Aop. λ PEA, f=1
Then the original problem is equivalent to the following problem
min min max wEW AZA PEA.
I((((w) A(D(,, p) Aop,
Next we x (w (TT maximization problem. We consider the following problem
A)T and derive optimal solution p p*(x) which depends and solves the inner
Eml((w) + AD(p,
min DEA,
which has the same optimal solution (x) with our problem.
There are three constraints handle, i.c., P: 0, Vi and p: 1, Vi and D Note that the constraint pi 2 0 is enforced by the term pı log(p:), otherwise the above objective will become infinity. As result, the constraint p; < is automatically satisfied due to Σ = 1 and 2 0. Hence, we only need to explicitly tackle the constraint Σ i- P: = 1. To this end, we define the following Lagrangian function
Lx n1) Σ Evll(w)= +
log n Σ pi log(ps)
p 1),
where j is the Lagrangian multiplier for the constraint conditions:
P= =1
The optimal solutions satisfy the KKT
- ((()) + A (log(p; + 1) + 0 and
p (x) 1.
36

---

Published in Transactions on Machine Learning Research (06/2023)
From the first equation, can derive (x) (x)(() Due to the second equation, conclude that p. (x) (x)((;(w)/A) Plugging this optimal p" (w) into the inner maximization problem, we have (x)(()(W)/A)
(((WW) 2=1 A
))
(x),,((w) - A log n + Σ pl (w) log(p, = Aog
exp
1=1
Therefore, we get the following equivalent problem to the original problem
(((WW)
))
min min Alog wEW A2
Σ
cxp
+ Ap.
n
which is Eq. 2 in the paper.
37


Reviews:
[{"review_id": "rj72FO73KR", "reviewer": "Reviewer_SDL7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nInstead of directly solving the constrained DRO problem, the paper focuses on an equivalent formulation and solves a composite optimization problem. The paper derives an upper bound for lambda in eq(2) to address the challenge of nonsmoothness of the objective function. Stochastic algorithms are proposed for solving the composite optimization problem of nonconvex loss and are further extended to the convex setting by applying a multistage restart strategy. The paper uses the moving average technique to compute stochastic estimators for both gradients and function values of the inner function. The proposed algorithms achieve complexity results independent of sample size, which is also comparable to state-of-the-art algorithms for solving constrained DRO problems with KL divergence.\n\n Weaknesses\n\n- This paper considers a particular formulation of the DRO problem eq(1), which has a KL divergence constraint as well as a KL regularization term in the objective function. This KL regularization term helps ensure the smoothness of the objective function and thus achieves a fast convergence rate. The paper argues that this new form is not studied in the literature. However, the intuition and benefits of doing this are still not very clear to me, as the KL regularization term basically has the same effect as the KL constraint. Why having both of them?\n- It appears (from Lemma 7) that the condition number crucially depends $L_0$, which further **exponentially depends** on $1/\\lambda_0$. Although I am not an expert in DRO, this looks surprising to me. For example, in the experiment you take $\\lambda_0=1e-3$. In this case, shouldn't the condition number make the complexity bound trivial?\n- The main techniques used in this paper include estimating inner function values and gradients by moving average and a restart strategy for solving problems with convex losses. The accelerated version of the algorithm is inspired by Qi et al. (2021), and other techniques are not highly innovative.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates a class of constrained Distributionally Robust Optimization (DRO) problems with KL divergence and proposes a dual-free stochastic algorithm for both non-convex and convex losses. The paper achieves nearly optimal complexity for non-convex losses and optimal complexity for convex losses, independent of the sample size. Experiments are presented on solving imbalanced classification problems, demonstrating the performance of the proposed algorithms in terms of convergence speed and generalization ability.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Goes back to my technical concern, can you further improve the complexity bound dependence on $\\lambda_0$?\n\nStronger motivation to study the proposed problems should be provided. \n\n\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BNhlDycCGF", "reviewer": "Reviewer_J7uW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The motivations, constructions and the proofs are very understandable, and the paper itself is written in an educational manner. I was able to navigate my way through the numerous steps of the constructions  without much problem [My only complaint is that the description of the equivalence between (1) and (2) is included in the notations paragraph, whereas it is one of the key here]\n- The effectiveness of the proposed algorithm for solving non-convex and convex constrained DRO problems is clearly demonstrated by empirical work.\nWeaknesses\n- A relative weakness, but the subject has given rise to a great deal of work, the proposed solution is an improvement of the existing but does not \"change\" the game. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Due to its promising performance on noisy labels, imbalanced data, and adversarial data, large-scale DRO optimization is gaining interest. Primal-dual algorithms solve DRO problems but incur overhead for managing a $n$-dimensional dual variable, where $n$ is the sample size. For large-scale deep learning, where $n$ could be millions or billions, this is undesirable. Thus, dual-free methods for DRO issues have become popular. This work develops  dual-free algorithms for solving the following constrained DRO problem, \n$$\n\\min _{\\mathbf{w} \\in \\mathcal{W}} \\max _{\\left}{\\mathbf{p} \\in \\delta_n: D(\\mathbf{p}, \\mathbf{1} / n) \\leq \\rho\\right\\}} \\sum_{i=1}^n p_i \\ell_i(\\mathbf{w})-\\lambda_0 D(\\mathbf{p}, \\mathbf{1} / n),\n$$\nwhere $\\mathbf{w}$ denotes the model parameter, $\\mathcal{W}$ is a closed convex set, $\\Delta_n=\\left\\{\\mathbf{p} \\in \\mathbb{R}^n: \\sum_{i=1}^n p_i=1, p_i \\geq 0\\right\\}$ denotes an $n$-dimensional simplex, $\\ell_i(\\mathbf{w})$ denotes a loss function on the $i$-th data, $D(\\mathbf{p}, \\mathbf{1} / n)=\\sum_{i=1}^n p_i \\log \\left(p_i n\\right)$ is the Kullback-Leibler (KL)-divergence measure between $\\mathbf{p}$ and uniform probabilities $\\mathbf{1} / n \\in \\mathbb{R}^n$, and $\\rho$ is the constraint parameter, and $\\lambda_0 > 0$ is a small constant.  KL regularization ensures smoothness of the objective function.\n\nThe main contributions are \n- derivation of  an equivalent primal-only formulation that is compositional; \n- development of two algorithms for non-convex losses and extending them for convex losses; \n- establishing an optimal complexity for both convex and non-convex losses. In particular, for a non-convex and smooth loss function $\\ell_i(\\mathbf{w})$, the algorithm achieves an oracle complexity of $\\widetilde{\\mathcal{O}}\\left(1 / \\epsilon^3\\right)^1$ for finding a $epsilon$-stationary solution, and for a convex and smooth loss function, we achieve $\\mathcal{O}\\left(1 / \\epsilon^2\\right)$ for finding a $epsilon$-optimal solution. These results match primal-dual algorithms best complexities but have a per-iteration complexity of $\\mathcal{O}(d)$, regardless of sample size $n$. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- include a discussion of the equivalence (1)-(3) in the main text: this is really one of the essential points in your contribution, even if the derivation is quite elementary. \n- The domain of model parameter $\\mathcal{W}$ is bounded by $R$, i.e., for all $\\mathbf{w} \\in \\mathcal{W}$, we have $\\|\\mathbf{w}\\| \\leq R$: Clumsy, to be reformulated\n- I do not like $$i \\sim \\mathcal{D}$\" in the assumption. Say for all $i \\in \\mathca{D}$ this is more correct [of course, I have understood what is meant]\n- The descriptions of the algorithm should include all the updates.  We are half way there, we would prefer to have all the equations in front of us", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "y68cnKYa9l", "reviewer": "Reviewer_6JEJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n* The paper studies an important problem on distributionally robust optimization and provides principled methods to solve it.\n\n* The paper provides convergence guarantees for the proposed solver, and also provides an accelerated version with optimal oracle complexity. The paper studies such guarantees both for convex and non-convex losses.\n\n* The paper shows several (large-scale) experiments where they show their proposed algorithms cobverges faster and achieves a better solution compared to several baselines.\n\nWeaknesses\n\n* It is not clear what the objective in (1) offers beyond the unconstrained DRO problem. In particular, the impact of $\\rho$ and $\\lambda_0$ is similar practically, and I am not sure if $\\rho$ has an operational meaning for practitioners that $\\lambda_0$ cannot offer. \n\n* The objective in (1) is also slightly different from those of the prior work in their Table 1 (Levy et al; Namkoong & Duchi et al); hence I am not sure if the comparison of the convergence rate is apples-to-apples.\n\n* The duality between constrained DRO and the formulation in (2) that is at the heart of this paper is observed previously in several works and has been extensively studied, cf. (Föllmer & Knispel, 2011)(Shapiro et al), and has been recently of interest by others, e.g., (Qi et al., 2020) and (Li et al., 2021). This has not been sufficiently highlighted here as what is being offered on top of the rich literature.\n\nFöllmer, Hans, and Thomas Knispel. \"Entropic risk measures: Coherence vs. convexity, model ambiguity and robust large deviations.\" Stochastics and Dynamics 11, no. 02n03 (2011): 333-351.\n\nShapiro, Alexander, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics, 2021.\n\nQi, Qi, Yi Xu, Rong Jin, Wotao Yin, and Tianbao Yang. \"Attentional biased stochastic gradient for imbalanced classification.\" arXiv preprint arXiv:2012.06951 (2020).\n\nLi, Tian, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. \"On tilted losses in machine learning: Theory and applications.\" arXiv preprint arXiv:2109.06141 (2021).\n\n* A simple solver for (2) would be to use the solvers by (Qi et al, 2020, Li et al, 2021) and add an additional gradient step on $\\lambda$ (perhaps with a momentum term). It is unclear what the compositional view offers on top of this simple solver theoretically and empirically. In fact, in Eq (6), the gradients to update $w$ is the same as that of (Qi et al, 2020, Li et al, 2021) if we ignore the moving average on $v$ because $\\nabla f_{\\lambda} (s)$ is just $\\lambda * (1/s).$\n\n\n\n* Given the rich experimental setup of (Li et al. 2021), it is not clear why that baseline is missing.\n\n* It seems to me that for non-convex problem in (2) can be solved for all $\\lambda_0$ and should not need $\\lambda_0>0$. Is this constraint needed? \n\n* The formula in (2) has a resemblance to Entropic Value at Risk (Ahmadi-Javid, 2021) and Tilted Value at Risk, see (Li et. al, 2021), as both of those works offer recipes to optimize $\\lambda$ in addition to the tilted risk. That connection has not been explored.\n\nAhmadi-Javid, Amir. \"Entropic value-at-risk: A new coherent risk measure.\" Journal of Optimization Theory and Applications 155 (2012): 1105-1123.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a constrained DRO with a KL regularizer and constraint, where the main goal of the paper is to derive a solver with optimal complexity for both convex and nonconvex losses that is independent of the sample size. The main tool in this paper is to rewrite the dual form of the problem, which leads to a primal only compositional problem, and then two algorithms (one of which is the accelerated variant) are presented for solving the problem. The authors analyze the convergence rate and compare that against several existing solvers. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, this is a paper on an important research area with a rich set of results. However, there are several issues with framing and experimental/theoretical comparisons that have been pointed out in the weaknesses, which I would like to see addressed in a revision.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "g5sj9HY3hz", "reviewer": "Reviewer_YnCn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n\n- If we start from The basic problem of interest and desire to have per-iteration overhead free of $n$ is stated clearly, and so are the techniques (and assumptions) employed by the authors to obtain algorithms with formal guarantees.\n- The authors provide a concrete optimization procedure suited to their problem of interest that is straightforward to implement and enjoys competitive theoretical guarantees, up to the formal assumptions.\n\n*Weaknesses:*\n\nI found the motivations for their problem of interest really hard to parse. The \"unconstrained\" case (with $\\\\rho = \\\\infty$) is easy, just minimize the tilted loss in $\\\\mathbf{w}$. If we won't want the KL divergence to be too big, setting $\\\\lambda\\_{0}$ accordingly large is thus the easy/implicit way of doing this. Adding the explicit condition in terms of $\\\\rho$ on top of this seems to add a lot of complexity with no real clear motivation. In paragraph 3 of the intro, the authors give three (!!) reasons for this, none of which are convincing or really have anything to do with the reason to use (1) instead of the tilted ERM objective (aka the objective of Qi et al. NeurIPS 2021).\n\nClosely related to the preceding weakness, the writing is quite bloated. The \"three reasons\" just mentioned are not really relevant to the actual problem. The authors then give a central question (box at top of p.2), with once again \"three\" qualifications, that correspond roughly to the (i)~(iii) in the following paragraph. Furthermore, in the next paragraph, there are \"three\" challenges to (2). I get these challenges and the techniques to deal with them, but all these lists are conceptual overload. Moreover, it makes it hard to really see what is new and interesting here. Especially considering sections 4 and 5, the authors make comments about novelty in the context of stochastic learning algorithms for compositional functions - if there is such novelty here, why stick to the special case of DRO-like formulation? Again this clouds the overall story, making it hard to evaluate what is new/interesting.\n\nI think the results here are strictly speaking novel and appear to be correct, with claims that are essentially sound (i.e., aligned with the results presented). On the other hand, the constrained version of the KL-regularized DRO objective here seems to come out of nowhere and be very poorly motivated, save for the fact that \"there don't exist any results for this setting yet\". Perhaps I have misunderstood something, but my feeling is that if the SO results for compositional functions stand on their own as contributions, there is no need to latch on to the rather unnatural constrained variant used here. Since the results appear solid, I am left on the borderline, but with some re-writing I think the paper might have an audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Broadly, this paper is concerned with empirical risk minimization using non-traditional notions of \"risk\" such as distributionally robust optimization (DRO) risk. They consider a rather particular case of DRO-like risk, namely the \"worst\" re-weighted average loss, where the weights are constrained not to be too far from a uniform distribution.\n\nMy understanding of the main claims of the authors is as follows. The most orthodox approach to tackling objectives of the form given in their (1) is to use primal-dual optimizers \"out of the box\", and this works, but when the number of samples $n$ grows large, this becomes computationally prohibitive. A very similar problem has also been studied fairly recently by Qi et al. (NeurIPS 2021); this is essentially identical to an exponential smoothing or \"tilting\" approximation to the worst-case loss, e.g. as in Li et al. (ICLR 2021; \"tilted ERM\" paper). The key difference here is that here the authors consider a constraint on the $\\\\max$ over the weights inside their objective (1), which leads to a joint minimization in both the original parameters $\\\\mathbf{w}$ and the \"tilting\" parameter $\\\\lambda$; see their (2). Without additional assumptions, the joint problem need not be smooth (gradients can become arbitrarily sharp as $\\\\lambda$ gets too large). The most straightforward way of dealing with this is to just assume the losses are bounded - this is the approach taken by the authors. This lets the authors attack (2) as a constrained (but smooth) problem, to which (primal) stochastic gradient-based methods can be applied. The \"inner\" part of the compositional objective has a sum of $n$ terms, and so to avoid the $n$-dependent overhead at each iteration, they make use of a moving average estimator, as well-established but convenient technique.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see my comments above.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a constrained DRO with a KL regularizer and constraint, where the main goal of the paper is to derive a solver with optimal complexity for both convex and nonconvex losses that is independent of the sample size. In general, the paper is well written, technically sounded, and experimental results are convincing.  It has nice theoretical findings that could be useful beyond the constrained DRO problem. During the discussion, the authors have successfully addressed some of reviewer concerns. As a result, three reviewers are positive on the paper.  There are still some minor comments which can be addressed by minor revision.  
- While the current limited set of experimental results don't fully support the claim that the formulation could be used to tune 
λ in tilted loss (2), I think it is okay if the authors add a disclaimer/limitation that this is a motivation for the work, and this paper takes a step towards that goal.
- There are still some issues with the density of the material, the authors have addressed some of these points in the revised version. 
Decision: Accept (poster)