# Large-Scale Non-convex Stochastic Constrained Distributionally Robust
Optimization

Qi Zhang 1, Yi Zhou 2, Ashley Prater-Bennette 3, Lixin Shen 4, Shaofeng Zou 1

###### Abstract

Distributionally robust optimization (DRO) is a powerful framework for
training robust models against data distribution shifts. This paper focuses on
constrained DRO, which has an explicit characterization of the robustness
level. Existing studies on constrained DRO mostly focus on convex loss
function, and exclude the practical and challenging case with non-convex loss
function, e.g., neural network. This paper develops a stochastic algorithm and
its performance analysis for non-convex constrained DRO. The computational
complexity of our stochastic algorithm at each iteration is independent of the
overall dataset size, and thus is suitable for large-scale applications. We
focus on the general Cressie-Read family divergence defined uncertainty set
which includes $\chi^{2}$-divergences as a special case. We prove that our
algorithm finds an $\epsilon$-stationary point with a computational complexity
of $\mathcal{O}(\epsilon^{-3k_{*}-5})$, where $k_{*}$ is the parameter of the
Cressie-Read divergence. The numerical results indicate that our method
outperforms existing methods. Our method also applies to the smoothed
conditional value at risk (CVaR) DRO.

##  1 Introduction

Machine learning algorithms typically employ the approach of Empirical Risk
Minimization (ERM), which minimizes the expected loss under the empirical
distribution $P_{0}$ of the training dataset and assumes that test samples are
generated from the same distribution. However, in practice, there usually
exists a mismatch between the training and testing distributions due to
various reasons, for example, in domain adaptation tasks domains differ from
training to testing (Blitzer, McDonald, and Pereira 2006; Daume III and Marcu
2006); test samples were selected from minority groups which are
underrepresented in the training dataset (Grother et al. 2011; Hovy and
Søgaard 2015) and there might exist potential adversarial attacks (Goodfellow,
Shlens, and Szegedy 2014; Madry et al. 2017). Such a mismatch may lead to a
significant performance degradation.

This challenge spurred noteworthy efforts on developing a framework of
Distributionally Robust Optimization (DRO) e.g., (Ben-Tal et al. 2013; Shapiro
2017; Rahimian and Mehrotra 2019). Rather than minimizing the expected loss
under one fixed distribution, in DRO, one seeks to optimize the expected loss
under the worst-case distribution in an uncertainty set of distributions.

Specifically, DRO aims to solve the following problem:

$\displaystyle\inf_{x}\sup_{Q\sim\mathcal{U}(P_{0})}\mathbb{E}_{S\sim
Q}\left[\ell(x;S)\right],$ (1)

where $\mathcal{U}(P_{0})$ is an uncertainty set of distributions centered at
$P_{0}$, $P_{0}$ is the empirical distribution of the training dataset, $\ell$
is the loss function, and $x$ is the optimization variable. For example, the
uncertainty set can be defined as

$\displaystyle\mathcal{U}(P_{0}):=\\{Q:D(Q\|P_{0})\leq\rho\\},$ (2)

where $D$ is some distance-like metric, e.g., Kullback-Leibler (KL) divergence
and $\chi^{2}$ divergence, and $\rho$ is the uncertainty level. In practice,
for ease of implementation and analysis, a relaxed formulation of eq. 1, which
is referred to as the penalized DRO, is usually solved (Levy et al. 2020; Jin
et al. 2021; Qi et al. 2021; Sinha et al. 2017):

$\displaystyle\inf_{x}\sup_{Q}\mathbb{E}_{S\sim Q}\
\left[\ell(x;S)\right]-\lambda D(Q\|P_{0}),$ (3)

where $\lambda>0$ is a fixed hyperparameter that needs to be chosen manually.
In contrast to constrained DRO in eq. (1), a regularization term is added to
the objective function to keep the distribution $Q$ and the distribution
$P_{0}$ close, and the hyperparameter $\lambda$ is manually chosen beforehand
to control the tradeoff with minimizing the loss. Compared with the penalized
DRO setting, the constrained DRO problem in eq. 1 requires that the
distribution $Q$ to be strictly in the uncertainty set, and searches for the
optimal solution under the worst-case distribution in the uncertainty set.
Therefore, the obtained solution from the constrained DRO is minimax optimal
for distributions in the uncertainty set, whereas it is hard to get such a
guarantee for the penalized DRO relaxation. In this paper, we focus on the
challenging constrained DRO problem in eq. 1.

Existing studies on constrained DRO are limited to convex loss functions or
require some additional assumptions (Soma and Yoshida 2020; Hashimoto et al.
2018; Levy et al. 2020; Duchi and Namkoong 2018; Duchi, Glynn, and Namkoong
2021; Qi et al. 2022; Wang, Gao, and Xie 2021). Little understanding on the
practical non-convex loss functions, e.g., neural network, is known. In this
paper, we focus on the constrained DRO problem with non-convex loss.

DRO problems under different uncertainty sets are fundamentally different. As
will be discussed later in related works, there is a rich literature on DRO
with various uncertainty sets. In this paper, we focus on the general Cressie-
Read family divergence defined uncertainty set (Duchi and Namkoong 2018; Jin
et al. 2021), which includes, e.g., $\chi^{2}$ divergence, as a special case
(see Section 2 for more details). We also investigate the smoothed conditional
value at risk (CVaR) DRO problem.

More importantly, we focus on the practical yet challenging large-scale
scenario, where $P_{0}$ is the empirical distribution of $N$ samples and $N$
is very large. In classic stochastic optimization problems, e.g., ERM, it is
easy to get an unbiased estimate of the gradient using only a few samples, and
therefore the computational complexity at each iteration is independent of the
training dataset size. However, in the DRO problems, due to taking the worst-
case distributions in the objective, the problem becomes challenging. Many
existing DRO algorithms incur a complexity that increases linearly (or even
worse) in the training dataset size (Duchi and Namkoong 2018; Namkoong and
Duchi 2016; Ghosh, Squillante, and Wollega 2018), which is not feasible for
large-scale applications. In this paper, we will design a stochastic algorithm
with computational complexity at each iteration being independent of the
training dataset size (Qi et al. 2022; Wang, Gao, and Xie 2021; Levy et al.
2020).

###  1.1 Challenges and Contributions

The key challenges and main contributions in this paper are summarized as
follows.

  * •

For large-scale applications, the number of training samples is large, and
therefore directly computing the full gradient is not practical. Nevertheless,
as discussed above, it is challenging to obtain an unbiased estimate of the
gradient for DRO problems using only a few samples. For $\varphi$-divergence
DRO problem, the distributions in the uncertainty set are continuous w.r.t.
the training distribution. Thus the distributions in the uncertainty set can
be parameterized by an $N$-dimensional vector (Namkoong and Duchi 2016). Then
the DRO problem becomes a min-max problem and primal-dual algorithms (Rafique
et al. 2022; Lin, Jin, and Jordan 2020; Xu et al. 2023) can be used directly.
Subsampling methods in DRO were also studied in (Namkoong and Duchi 2016;
Ghosh, Squillante, and Wollega 2018). However, all the above studies require a
computational complexity linear or even worse in the training dataset size at
each iteration and thus is prohibitive in large-scale applications. In (Levy
et al. 2020), an efficient subsampling method was proposed, where the batch
size is independent of the training dataset size. However, they only showed
the sampling bias for $\chi^{2}$ and CVaR DRO problems. In this paper, we
generalize the analysis of the bias in (Levy et al. 2020) to the general
Cressie-Read family. We further develop a Frank-Wolfe update on the dual
variables in order to bound the gap between the objective and its optimal
value given the optimization variable $x$ and the biased estimate.

  * •

The second challenge is due to the non-convex loss function. Existing studies
for the Cressie-Read divergence family (Duchi and Namkoong 2018; Levy et al.
2020) are limited to the case with convex loss function, and their approach
does not generalize to the non-convex case. The key difficulty lies in that
the subgradient of the objective function can not be obtained via
subdifferential for non-convex loss functions. Instead of explicitly
calculating the worst-case distribution as in (Duchi and Namkoong 2018; Levy
et al. 2020), we propose to design an algorithm for the dual problem which
optimizes the objective under a known distribution. Thus the gradient of the
objective can be efficiently obtained.

  * •

The third challenge is that the dual form of constrained DRO is neither smooth
nor Lipschitz, making the convergence analysis difficult. Existing studies,
e.g., (Wang, Gao, and Xie 2021), assume that the optimal dual variable is
bounded away from zero, i.e., $\lambda^{*}>\lambda_{0}$ for some
$\lambda_{0}>0$, so that it is sufficient to consider
$\lambda\geq\lambda_{0}$. However, this assumption may not necessarily be true
as shown in (Wang, Gao, and Xie 2021; Hu and Hong 2013). In this paper, we
generalize the idea in (Qi et al. 2022; Levy et al. 2020) to the general
Cressie-Read divergence family. We design an approximation of the original
problem, and show that it is smooth and Lipschitz. The approximation error can
be made arbitrarily small so that the solution to the approximation is still a
good solution to the original. We add a regularizer to the objective and at
the same time we keep the hard constraint. In this way, we can guarantee that
its dual variable $\lambda$ has a positive lower bound.

  * •

We design a novel algorithm to solve the approximated problem and prove it
converges to a stationary point of the constrained DRO problem. The numerical
results show that our proposed algorithm outperforms existing methods.

###  1.2 Related Work

#### Various Uncertainty Sets.

$\varphi$-divergence DRO problems (Ali and Silvey 1966; Csiszár 1967) were
widely studied, for example, CVaR in (Rockafellar, Uryasev et al. 2000; Soma
and Yoshida 2020; Curi et al. 2020; Tamar, Glassner, and Mannor 2015),
$\chi^{2}$-divergence in (Hashimoto et al. 2018; Ghosh, Squillante, and
Wollega 2018; Levy et al. 2020), KL-divergence in (Qi et al. 2021, 2022; Hu
and Hong 2013) and Sinkhorn distance (Wang, Gao, and Xie 2021), a variant of
Wasserstein distance based on entropic regularization. However, the above
studies are for some specific divergence function and can not be extended
directly to the general Cressie-Read divergence family.

#### Penalized DRO.

The general $\varphi$-divergence DRO problem was studied in (Jin et al. 2021)
where the proposed algorithm works for any divergence function with a smooth
conjugate. The authors also designed a smoothed version of the CVaR problem
and showed their method converges to a stationary point. However, their method
is for the penalized formulation and does not generalize to the constrained
DRO. In this paper, we focus on the challenging constrained DRO, the solution
of which is minimax optimal over the uncertainty set. Our proposed algorithm
can also be applied to solve the smoothed CVaR problem in the constrained
setting.

#### Constrained DRO with Convex Loss.

The general $\varphi$-divergence constrained DRO problem was studied in
(Namkoong and Duchi 2016). Instead of optimizing from the dual form, the
authors treat the worst-case distribution as a $N$-dimentional vector and
implement a stochastic primal-dual method to solve the min-max problem.
However, the computational complexity at each iteration is linear in the
number of the training samples and can not be used in large-scale
applications. The same problem was further studied in (Duchi, Glynn, and
Namkoong 2021). The authors pointed out that minimizing constrained DRO with
$\varphi$-divergence is equivalent to adding variance regularization for the
Empirical Risk Minimization (ERM) objective. The general Cressie-Read
divergence family DRO problem was studied in (Duchi and Namkoong 2018), where
the basic idea is to calculate the worst-case distribution for the constrained
DRO first and then use the subdifferential to get the subgradient.
Furthermore, the $\chi^{2}$ and CVaR DRO problems were studied in (Levy et al.
2020). Compared with the method in (Duchi and Namkoong 2018), they calculate
the worst-case distribution for the penalized DRO and then optimize both the
Lagrange multiplier and the loss function. This approach converges to the
optimal solution with a reduced complexity. Their method can be extended to
the general Cressie-Read divergence family. However, all the above papers are
limited to the case with convex loss function. To the best of our knowledge,
our work is the first paper on large-scale non-convex constrained DRO with the
general Cressie-Read divergence family. We note that the KL DRO was studied in
(Qi et al. 2022), which however needs an exponential computational complexity.
We achieve a polynomial computational complexity for the Cressie-Read
divergence family.

##  2 Preliminaries and Problem Model

###  2.1 Notations

Let $s$ be a sample in $\mathbb{S}$ and $P_{0}$ be the distribution on the
points $\\{s_{i}\\}_{i=1}^{N}$, where $N$ is the size of the support. Denote
by $\Delta^{N}:=\\{\mathbf{p}\in\mathbb{R}^{n}|\sum_{i=1}^{N}p_{i}=1,p_{i}\geq
0\\}$ the ${N}$-dimensional probability simplex. Denote by
$x\in\mathbb{R}^{d}$ the optimization variable. We denote by
$\mathbb{1}_{\mathbb{X}}(x)$ the indicator function, where
$\mathbb{1}_{\mathbb{X}}(x)=0$ if $x\in\mathbb{X}$, otherwise
$\mathbb{1}_{\mathbb{X}}(x)=\infty$. Let
$\ell:\mathbb{R}^{d}\times\mathbb{S}\to\mathbb{R}$ be a non-convex loss
function. Let $\|\cdot\|$ be the Euclidean norm and $(t)_{+}:=\max\\{t,0\\}$
be the positive part of $t\in\mathbb{R}$. Denote $\nabla_{x}$ by the gradient
to $x$. For a function $f:\mathbb{R}^{d}\to\mathbb{R},$ a point
$x\in\mathbb{R}^{d}$ is said to be an $\epsilon$-optimal solution if
$|f(x)-f(x^{*})|\leq\epsilon$, where $f(x^{*})$ is the optimal value of $f$.
If the function $f$ is differentiable, a point $x\in\mathbb{R}^{d}$ is said to
be first-order $\epsilon$-stationary if $\|\nabla f(x)\|\leq\epsilon$.

###  2.2 Assumptions

In this paper, we take the following standard assumptions that are commonly
used in the DRO literature (Duchi and Namkoong 2018; Levy et al. 2020; Qi et
al. 2021, 2022; Wang, Gao, and Xie 2021; Soma and Yoshida 2020):

  * •

The non-convex loss function is bounded: $0\leq\ell(x;s)\leq B$ for some
$B>0$, $\forall x\in\mathbb{R}^{d},s\in\mathbb{S}$.

  * •

The non-convex loss function is $G$-Lipschitz such that
$|\ell(x_{1};s)-\ell(x_{2};s)|\leq G\|x_{1}-x_{2}\|$ and $L$-smooth such that
$\|\nabla_{x}\ell(x_{1};s)-\nabla_{x}\ell(x_{2};s)\|\leq L\|x_{1}-x_{2}\|$ for
any $x_{1},x_{2}\in\mathbb{R}^{d}$ and $s\in\mathbb{S}$.

###  2.3 DRO Objective and Its Dual Form

In ERM, the goal is to solve

$\displaystyle\inf_{x}\mathbb{E}_{S\sim P_{0}}\ \left[\ell(x;S)\right],$

where the objective function is the expectation of the loss function with
respect to the training distribution $P_{0}$. To solve the distributional
mismatch between training data and testing data, the formulation of DRO
(Goodfellow, Shlens, and Szegedy 2014; Madry et al. 2017; Rahimian and
Mehrotra 2019) was developed, where the goal is to minimize the expected loss
with respect to the worst distribution in an uncertainty set
$\mathcal{U}(P_{0})$:

$\displaystyle\inf_{x}\sup_{Q\sim\mathcal{U}(P_{0})}\mathbb{E}_{S\sim Q}\
\ell(x;S).$ (4)

DRO problems under different uncertainty sets are fundamentally different.
Consider the uncertainty set defined by $\varphi$-divergence
$D_{\varphi}(Q\|P_{0})$, which is one of the most common choices in the
literature and can be written as
$D_{\varphi}(Q\|P_{0}):=\int\varphi\left(\frac{dQ}{dP_{0}}\right)dP_{0},$
where $\varphi$ is a non-negative convex function such that $\varphi(1)=0$ and
$\varphi(t)=+\infty$ for ant $t<0$. Then let the uncertainty set
$\mathcal{U}(P_{0}):=\\{Q:D_{\varphi}(Q\|P_{0})\leq\rho\\}$ where $\rho>0$ is
the radius of the uncertainty set.

In this paper, we study the general Cressie-Read family of
$\varphi$-divergence (Cressie and Read 1984; Van Erven and Harremos 2014),
where

$\displaystyle\varphi_{k}(t):=\frac{t^{k}-kt+k-1}{k(k-1)},$ (5)

$k\in(-\infty,+\infty)\setminus\\{0,1\\}$. Let $k_{*}=\frac{k}{k-1}$. This
family includes as special cases $\chi^{2}$-divergence ($k=2$) and KL
divergence ($k\to 1$). When $k>2$, the conjugate function of $\varphi_{k}(t)$
(which will be introduced later) is not smooth, thus the problem becomes hard
to solve even in the penalized formulation (Jin et al. 2021). In this paper,
we focus on $k\in(1,2]$ ($k_{*}\in[2,\infty)$). The objective is

$\displaystyle\inf_{x}\sup_{Q:D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim
Q}\ \ell(x;S).$ (6)

Solving (6) directly is challenging due to the sup over $Q$. In (Namkoong and
Duchi 2016), a finite-dimensional vector q was used to parameterize the
distributions in the uncertainty set since $Q\ll P_{0}$ for
$\varphi$-divergence. Then the DRO problem becomes a convex concave min-max
problem. This method can be extended to the case with non-convex loss function
by applying the algorithms for non-convex concave min-max problems (Rafique et
al. 2022; Lin, Jin, and Jordan 2020; Xu et al. 2023). However, the dimension
of distribution in the uncertainty set is equal to the number of training
samples. Thus, the computational complexity at each iteration is linear in the
sample size and is prohibitive in large-scale applications.

To obtain a complexity independent of the sample size, one alternative is to
use its dual. By duality, we can show that the DRO objective (6) can be
equivalently written as (Levy et al. 2020; Shapiro 2017)

$\displaystyle\inf_{x}\inf_{\lambda\geq
0,\tilde{\eta}\in\mathbb{R}}\mathbb{E}_{S\sim
P_{0}}\left[\lambda\varphi_{k}^{*}\left(\frac{\ell(x;S)-\tilde{\eta}}{\lambda}\right)+\lambda\rho+\tilde{\eta}\right],$

where $\varphi_{k}^{*}(t^{\prime})=\sup_{t}\\{t^{\prime}t-\varphi_{k}(t)\\}$
is the conjugate function of $\varphi_{k}(t^{\prime})$. In this way, the
optimization problem under an unknown distribution is rewritten into one under
a known distribution. The subsampling method can then be used, which leads to
a complexity independent of the sample size (which will be introduced later).
For the Cressie-Read family in (5), the corresponding conjugate function
family is
$\varphi_{k}^{*}(t)=\frac{1}{k}\left[((k-1)t+1)_{+}^{k_{*}}-1\right].$
Therefore, the objective can be written as

$\displaystyle\inf_{x,\lambda\geq 0,\tilde{\eta}\in\mathbb{R}}$
$\displaystyle\mathbb{E}_{S\sim
P_{0}}\left[\frac{\lambda}{k}\left((k-1)\frac{\ell(x;S)-\tilde{\eta}}{\lambda}+1\right)_{+}^{k_{*}}\right]$
$\displaystyle+\lambda\left(\rho-\frac{1}{k}\right)+\tilde{\eta}.$

Let $\eta=\tilde{\eta}-\frac{\lambda}{k-1}$ and the corresponding objective is

$\displaystyle\inf_{x,\lambda\geq 0,\eta\in\mathbb{R}}\mathbb{E}_{S\sim
P_{0}}$
$\displaystyle\left[\frac{(k-1)^{k_{*}}}{k}({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{1-k_{*}}\right]$
$\displaystyle+\lambda\left(\rho+\frac{1}{k(k-1)}\right)+\eta.$

Define

$\displaystyle f(x;\lambda;\eta;s)=$
$\displaystyle\frac{(k-1)^{k_{*}}}{k}({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{1-k_{*}}$
$\displaystyle+\lambda\left(\rho+\frac{1}{k(k-1)}\right)+\eta.$ (7)

Thus the goal is to solve

$\displaystyle\inf_{x}\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F(x;\lambda;\eta),$ (8)

where $F(x;\lambda;\eta)$ is defined as $F(x;\lambda;\eta)=\mathbb{E}_{S\sim
P_{0}}\Big{[}f(x;\lambda;\eta;S)\Big{]}.$ Therefore, we reformulate the DRO
problem as one to minimize an objective function under a known distribution,
where subsampling method could be used to reduce the complexity.

##  3 Analysis of Constrained DRO

In this section, we analyze the constrained DRO problems under Cressie-Read
family divergence uncertainty sets with general smooth non-convex loss
function. We first discuss the challenges appearing in constrained
formulations, then we present how to construct the corresponding approximated
problem in order to overcome these challenges.

###  3.1 Smooth and Lipschitz Approximation

For $\lambda\in[0,+\infty),\eta\in\mathbb{R}$, the objective
$F(x;\lambda;\eta)$ is neither smooth nor Lipschitz. Thus it is difficult to
implement gradient-based algorithms. In the following, we will construct an
approximation of the original problem so that the objective function
$F(x;\lambda;\eta)$ becomes smooth and Lipschitz by constraining both
$\lambda$ and $\eta$ in some bounded intervals.

Denote by $\omega=(k(k-1)\rho+1)^{\frac{1}{k}}$. Since the loss function is
bounded such that $0\leq\ell\leq B$, we can show that there exists an upper
bound
$\bar{\lambda}=(k-1){(k(k-1)\rho+1)^{-\frac{1}{k_{*}}}}\left(1+\frac{(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}}{1-(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}}\right)B$
which only depends on $k,\rho$ and $B$ such that the optimal value
$\lambda^{*}\leq\bar{\lambda}$. In this paper, we do not assume that
$\lambda^{*}\geq\lambda_{0}>0$ as in (Wang, Gao, and Xie 2021). Instead, we
consider an approximation with $\lambda\in[\lambda_{0},\bar{\lambda}]$, and
show that the difference between the orignial and the approximation can be
bounded. We can show corresponding optimal $\eta^{*}\in[-\bar{\eta},B]$, where
$\bar{\eta}=\bar{\lambda}\left(\frac{k}{(k-1)^{k_{*}}k_{*}}\right)^{\frac{1}{k_{*}-1}}$.
The challenge lies in that the value of $\eta$ can be negative. Thus given
this $\eta$, the optimal value of $\lambda$ can be quite large then it is hard
to upper bound $\lambda$. In our proof, we change the objective to the
function that only depends on $\eta$ and find the lower bound on $\eta$. Based
on this lower bound, we get the bound on $\lambda$.

We show that the difference between the original and the approximation can be
bounded in the following lemma.

######  Lemma 1.

$\forall x\in\mathbb{R}^{d},0\leq\lambda_{0}\leq\bar{\lambda}$,

$\displaystyle\left|\inf_{\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[-\bar{\eta},B]}F(x;\lambda;\eta)-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F(x;\lambda;\eta)\right|\leq 2\lambda_{0}\rho.$

Note in the proof of this lemma, we derive an equivalent expression of

$\sup_{{Q:}D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim Q}\
\left[\ell(x;S)\right]-\lambda_{0}D_{\varphi_{k}}(Q\|P_{0}),$

where both the hard constraint and regularizer are kept. This is different
from the approach in Section 3.2 of (Shapiro 2017). Note that this equivalent
formulation holds for any $\varphi$-divergence DRO problem.

Lemma 1 demonstrates that the non-smooth objective function can be
approximated by a smooth objective function. A smaller $\lambda_{0}$ makes the
gap smaller but the function “less smooth”.

###  3.2 Convexity and Smoothness on Parameters

The advantage of our approximated problem is that the function is smooth in
all $x$, $\lambda$, and $\eta$. Moreover, We find that the objective function
is convex in $\lambda$ and $\eta$ though the loss function is non-convex in
$x$.

######  Lemma 2.

Define $z=(\lambda,\eta)\in\mathcal{M}$, where
$\mathcal{M}=\\{(\lambda,\eta):\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[-\bar{\eta},B]\\}$.
Then $\forall x\in\mathbb{R}^{d},z\in\mathcal{M}$, the objective function
$F(x;z)$ is convex and $L_{z}$-smooth in $z$, where
$L_{z}=\frac{1}{\lambda_{0}}+\frac{2(B+\bar{\eta})}{\lambda_{0}^{2}}+{\frac{(B+\bar{\eta})^{2}}{\lambda_{0}^{3}}}$
if $k_{*}=2$ and
$L_{z}=\frac{(k-1)^{k_{*}}}{k}k_{*}(k_{*}-1)\left(\frac{(B+\bar{\eta})^{k_{*}}}{\lambda_{0}^{k_{*}+1}}+\frac{(B+\bar{\eta})^{k_{*}-2}}{\lambda_{0}^{k_{*}-1}}\right)$
if $k_{*}>2$.

Moreover, the objective function $F(x;z)$ is $L_{x}$-smooth in $x$, where
$L_{x}=\frac{(k-1)^{k_{*}}}{k}k_{*}\lambda_{0}^{1-k_{*}}(B+\bar{\eta})^{k_{*}-2}((k_{*}-1)G^{2}+(B+\bar{\eta})L)$.

Note the first-order gradient of the objective function is non-differential at
some point when $k_{*}=2$. Therefore, we discuss in two cases: $k_{*}>2$ and
$k_{*}=2$. In the first case, we can get the Hessian matrix of the objective.
In the second case, we show the smoothness and convexity.

Algorithm 1 SFK-DRO

Input: Iteration number $T$, initial point $(x_{1},z_{1})$, sample numbers
$n_{x},n_{z}$, stepsize $\alpha$, and one constant $C$

1: Let $t=1$

2: while $t\leq{T}$ do

3: randomly select $n_{x}$ samples $S_{1},S_{2},...,S_{n_{x}}$ and compute
${\nabla_{x}f_{x}(x_{t},z_{t})}=\sum_{i=1}^{n_{x}}\frac{\nabla_{x}f(x_{t};z_{t};{S_{i}})}{n_{x}}$.

4: $x_{t+1}=x_{t}-\alpha{\nabla_{x}f_{x}}(x_{t},z_{t})$

5: randomly select $n_{z}$ samples $S_{1},S_{2},...,S_{n_{z}}$and compute
${\nabla_{z}f_{z}}(x_{t+1},z_{t})=\sum_{j=1}^{n_{z}}\frac{\nabla_{z}f(x_{t+1};z_{t};{S_{j}})}{n_{z}}$

6: $e_{t}$= $\arg\min_{e\in\mathcal{M}}\langle
e,{\nabla_{z}f_{z}}(x_{t+1};z_{t})\rangle$

7: $d_{t}=e_{t}-z_{t}$

8: $g_{t}=\langle d_{t},-{\nabla_{z}f_{z}}(x_{t+1};z_{t})\rangle$

9: $\gamma_{t}=\min\left\\{\frac{g_{t}}{C},1\right\\}$

10: $z_{t+1}=z_{t}+\gamma_{t}d_{t}$

11: $t=t+1$

12: end while

$t^{\prime}=\arg\min_{t}\|{\nabla_{x}f_{x}}(x_{t};z_{t})\|^{2}+g_{t}^{2}$
Output: $(x_{t^{\prime}+1},z_{t^{\prime}})$

##  4 Mini-Batch Algorithm

Existing constrained stochastic Proximal Gradient Descent (PGD) algorithm for
general non-convex functions (Ghadimi, Lan, and Zhang 2016) can be used to
solve the approximated problem directly. However, this method requires a small
fixed step size, leading to a 4slow convergence. Additionally, it involves a
projection step, making it less efficient for large-scale problems.

In this paper, we find that the objective $F(x;z)$ is convex in $z$ and non-
convex in $x$. This motivates us to consider a stronger convergence criterion:

$\displaystyle|\nabla_{x}F(x;\lambda;\eta)|\leq\epsilon,$
$\displaystyle|F(x;\lambda;\eta)-\inf_{\lambda^{\prime}\geq
0;\eta^{\prime}}F(x;\lambda^{\prime};\eta^{\prime})|\leq\epsilon.$

In this paper, we use the Frank-Wolfe method to update the variable $z$.
Compared with the PGD method, the Frank-Wolfe method can solve the stepsize
selection problem by adapting the stepsize through line search techniques and
does not require projection, making it efficient for large-scale applications.
We then provide our Stochastic gradient and Frank-Wolfe DRO algorithm (SFK-
DRO), which optimizes $x$ and $z$ separately (see Algorithm 1). Define
$D=\max_{z_{1},z_{2}\in\mathcal{M}}\|z_{1}-z_{2}\|$,
$\sigma_{0}=\frac{(k-1)^{k_{*}}}{k}k_{*}(B+\bar{\eta})^{k_{*}-1}G\lambda_{0}^{1-k_{*}}$,
$\sigma_{1}=\left(\rho+1+\frac{1}{k(k-1)}\right)+\frac{(k-1)^{k_{*}}\lambda_{0}^{-k_{*}}(B+\bar{\eta})^{k_{*}}}{k}\left(k_{*}-1+\frac{\lambda_{0}k_{*}}{B+\bar{\eta}}\right)$,
$\Delta=F(x_{1};z_{1})-\inf_{x,z\in\mathcal{M}}F(x;z)$ and $C$ is a constant
such that $C\geq{D^{2}}L_{z}$. The convergence rate is then provided in the
following theorem.

######  Theorem 1.

With mini-batch sizes
$n_{x}=\frac{{12L_{x}\sigma_{0}^{2}}}{C\epsilon^{2}}\sim\mathcal{O}(\lambda_{0}^{-2k_{*}+4}\epsilon^{-2})$,
$n_{z}\geq\frac{48D^{2}\sigma_{1}^{2}}{\epsilon^{2}}\sim\mathcal{O}(\epsilon^{-2k_{*}-2})$
such that
$3B\sqrt{1+k(k-1)\rho}\sqrt{\frac{4+\log(n_{z})}{4n_{z}}}<\frac{\epsilon}{4}$
if $k_{*}=2$ or
$3B{(1+k(k-1)\rho)^{\frac{1}{k}}}\left(\frac{1}{n_{z}}+\frac{1}{2^{k_{*}-1}(k_{*}-2)n_{z}}\right)^{\frac{1}{k_{*}}}<\frac{\epsilon}{4}$
if $k_{*}>2$ and $\alpha=\frac{1}{2C}$, $\lambda_{0}=\frac{\epsilon}{8\rho}$,
for any small $\epsilon>0$ such that
$\frac{{D^{2}}L_{z}}{L_{x}}\sim\mathcal{O}(\epsilon^{-2})\geq 2$ and
$\frac{{D\sigma_{1}}}{C}\sim\mathcal{O}(\epsilon)\leq 1$, at most
$T={48}C\Delta\epsilon^{-2}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1}\epsilon^{-2})$
iterations are needed to guarantee a stationary point
$(x_{t^{\prime}+1};z_{t^{\prime}})$ in expectation:

$\displaystyle\mathbb{E}\|\nabla_{x}F(x_{t^{\prime}+1};z_{t^{\prime}})\|$
$\displaystyle\leq\epsilon,$
$\displaystyle\mathbb{E}\Big{[}\Big{|}F(x_{t^{\prime}+1};z_{t^{\prime}})-\inf_{\lambda\geq
0;\eta\in\mathbb{R}}F(x_{t^{\prime}+1};\lambda;\eta)\Big{|}\Big{]}$
$\displaystyle\leq\epsilon.$

A proof sketch will be provided later. Before that, we introduce a lemma for
our subsampling method. Via this lemma, we can show the complexity is
independent of the sample size and thus is suitable for our large-scale
setting. When we optimize $z$, an estimator
${f_{z}}(x,z)=\sum_{j=1}^{n_{z}}\frac{f(x;z;{S_{j}})}{n_{z}}$ is build to
estimate $F(x;z)=\mathbb{E}_{S\sim P_{0}}\Big{[}f(x;z;S)\Big{]}$. Though the
estimator is unbiased, in our Frank-Wolfe update process (Jaggi 2013; Frank,
Wolfe et al. 1956; Lacoste-Julien 2016) we need to estimate $\min F(x;z)$ via
$\mathbb{E}\min f_{z}(x;z)$. Obviously, the expectation of minimum is not
equal to the minimum of expectation, thus it is a biased estimator. In the
following lemma, we show that this gap can be bounded by a decreasing function
of the sample batch $n_{z}$.

######  Lemma 3.

For any bounded loss function $\ell$, if $k_{*}=2$,

$\displaystyle\left|\inf_{{\lambda\geq
0,\eta\in\mathbb{R}}}\left[F(x_{t+1};\lambda;\zeta)\right]-\mathbb{E}\left[\inf_{{\lambda\geq
0,\eta\in\mathbb{R}}}f_{z}(x_{t+1};\lambda;\eta)\right]\right|$
$\displaystyle\leq 3B\sqrt{1+k(k-1)\rho}\sqrt{\frac{4+\log(n_{z})}{4n_{z}}};$

and if $k_{*}>2$,

$\displaystyle\left|\inf_{{\lambda\geq
0,\eta\in\mathbb{R}}}\left[F(x_{t+1};\lambda;\eta)\right]-\mathbb{E}\left[\inf_{{\lambda\geq
0,\eta\in\mathbb{R}}}f_{z}(x_{t+1};\lambda;\eta)\right]\right|$
$\displaystyle\leq
3B{(1+k(k-1)\rho)^{\frac{1}{k}}}\left(\frac{1}{n_{z}}+\frac{1}{2^{k_{*}-1}(k_{*}-2)n_{z}}\right)^{\frac{1}{k_{*}}}.$

Note that (Levy et al. 2020) only shows this lemma when $k_{*}=2$, and we
extend the results to $k_{*}>2$. This lemma shows that the gap is in the order
of $\mathcal{O}({n_{z}}^{-\frac{1}{k_{*}}})$ and is independent of the total
number of samples.

###  4.1 Proof Sketch of Theorem 1

We use a stochastic gradient descent method (Moulines and Bach 2011; Gower et
al. 2019; Robbins and Monro 1951) to update $x$. Since the objective function
is $L_{x}$-smooth in $x$, if $\alpha\leq\frac{1}{2L_{x}}$ we have that:

$\displaystyle\frac{\alpha}{2}$
$\displaystyle\mathbb{E}\left[\|\nabla_{x}F(x_{t};z_{t})\|^{2}\right]\leq\mathbb{E}[F(x_{t};z_{t})]-\mathbb{E}[F(x_{t+1};z_{t})]$
$\displaystyle+{\alpha^{2}L_{x}}\mathbb{E}[\|{\nabla_{x}f_{x}}(x_{t};z_{t})-\nabla_{x}F(x_{t};z_{t})\|^{2}],$
(9)

where $f_{x}(x,z)=\sum_{j=1}^{n_{x}}\frac{f(x;z;{S_{j}})}{n_{x}}$. Define
$\sigma_{0}=\frac{(k-1)^{k_{*}}}{k}k_{*}(B+\bar{\eta})^{k_{*}-1}G\lambda_{0}^{1-k_{*}}$
and we can show that

$\displaystyle\mathbb{E}[\|\nabla_{x}f_{x}(x_{t};z_{t})-\nabla_{x}F(x_{t};z_{t})\|^{2}]\leq\frac{\sigma_{0}^{2}}{n_{x}}.$
(10)

Since $z\in\mathcal{M}$, instead of the stochastic gradient descent method, we
employ the Frank-Wolfe method (Frank, Wolfe et al. 1956) to update $z$. Define
$e_{t}=\arg\min_{e\in\mathcal{M}}\langle
e,{\nabla_{z}f_{z}}(x_{t+1};z_{t})\rangle$ and $g_{t}=\langle
e_{t}-z_{t},-{\nabla_{z}f_{z}}(x_{t+1};z_{t})\rangle$. In addition, we have
that

$\displaystyle g_{t}\geq
f_{z}(x_{t+1};z_{t})-\min_{z\in\mathcal{M}}f_{z}(x_{t+1};z)$

since $f_{z}(x;z)$ is convex in $z$ (Jaggi 2013). We can show that
$\frac{g_{t}}{C}\sim\mathcal{O}(\lambda_{0})$ thus for small $\lambda_{0}$ we
have $\frac{g_{t}}{C}\leq 1$. Then due to the fact that the objective is
$L_{z}$-smooth in $z$ ((9) of (Lacoste-Julien 2016)), we have that

$\displaystyle\mathbb{E}\left[\frac{g_{t}^{2}}{{4}C}\right]\leq\mathbb{E}[F(x_{t+1};z_{t})]-\mathbb{E}[F(x_{t+1};z_{t+1})]{+\frac{D^{2}\sigma_{1}^{2}}{Cn_{z}}}.$
(11)

By recursively adding (9) and (11), we have that

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\frac{\alpha}{2}\mathbb{E}\left[\|\nabla_{x}F(x_{t};z_{t})\|^{2}\right]+\mathbb{E}\left[\frac{g_{t}^{2}}{{4}C}\right]$
$\displaystyle\leq\frac{F(x_{1};z_{1})-\mathbb{E}[F(x_{T+1};z_{T+1})]}{T}+{\alpha^{2}L_{x}}\frac{\sigma^{2}}{n_{x}}{+\frac{D^{2}\sigma_{1}^{2}}{Cn_{z}}}.$
(12)

Since $L_{z}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1})$ and
$L_{z}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1})$, for small $\lambda_{0}$ we
have $C\geq{D^{2}}L_{z}\geq 2L_{x}$. Then we set
$\alpha=\frac{1}{2C}\leq\frac{1}{2L_{x}}$,
$T={48}C\Delta\epsilon^{-2}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1}\epsilon^{-2}),n_{x}=\frac{{12}L_{x}\sigma^{2}}{C\epsilon^{2}},$
and denote $\Delta=F(x_{1};z_{1})-\min_{x,z\in\mathcal{M}}F(x;z)$, for some
${t^{\prime}}\in[1,T]$ we have that

$\displaystyle\mathbb{E}\left[\|\nabla_{x}F(x_{{t^{\prime}}};z_{t^{\prime}})\|\right]$
$\displaystyle\leq\frac{\epsilon}{2},$ (13)
$\displaystyle\mathbb{E}\left[F(x_{{t^{\prime}}+1};z_{t^{\prime}})-\inf_{z\in\mathcal{M}}{f_{z}}(x_{{t^{\prime}}+1};z)\right]\leq\mathbb{E}[g_{t^{\prime}}]$
$\displaystyle\leq\frac{\epsilon}{2}.$ (14)

We choose $(x_{{t^{\prime}}+1},z_{t^{\prime}})$ as our output and we need to
bound
$\mathbb{E}\left[\|\nabla_{x}F(x_{{t^{\prime}}+1};z_{t^{\prime}})\|\right]$
and
$\mathbb{E}\left[F(x_{{t^{\prime}}+1};z_{t^{\prime}})-\inf_{z\in\mathcal{M}}F_{z}(x_{{t^{\prime}}+1};z)\right]$.
Since $F(x;z)$ is $L_{x}$-smooth in $x$, we have that
$\mathbb{E}[\|\nabla_{x}F(x_{{t^{\prime}}+1};z_{t^{\prime}})\|]\leq\epsilon.$

By Lemma 3, we pick small $n_{z}$ such that

$\left|\inf_{{\lambda\geq
0;\eta\in\mathbb{R}}}\left[F(x_{{t^{\prime}}+1};\lambda;\eta)\right]-\mathbb{E}\left[\inf_{{\lambda\geq
0;\eta\in\mathbb{R}}}{f_{z}}(x_{{t^{\prime}}+1};\lambda;\eta)\right]\right|\leq\frac{\epsilon}{4}.$

Lemma 1 also works for $f_{z}$. When $\lambda_{0}=\frac{\epsilon}{8\rho}$, we
have that

$\displaystyle\left|\inf_{\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[-\bar{\eta},B]}f_{z}(x;\lambda;\eta)-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}f_{z}(x;\lambda;\eta)\right|\leq\frac{\epsilon}{4}.$

Thus we have

$\displaystyle{\mathbb{E}[}F(x_{{t^{\prime}}+1};z_{t^{\prime}})-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F(x_{{t^{\prime}}+1};\lambda;\eta){]}\leq\epsilon,$ (15)

which completes the proof.

##  5 Smoothed CVaR

Our algorithm can also solve other DRO problems efficiently, for example, the
Smoothed CVaR proposed in (Jin et al. 2021). The CVaR DRO is an important
$\varphi$-divergence DRO problem, where
$\varphi(t)=\mathbb{1}_{[0,\frac{1}{\mu})}$ if $0\leq t<\frac{1}{\mu}$, and
$0<\mu<1$ is some constant. The dual expression of CVaR can be written as

$\displaystyle\mathcal{L}_{CVaR}(x;P_{0})=\inf_{\eta\in\mathbb{R}}\frac{1}{\mu}\mathbb{E}_{S\sim
P_{0}}\left[(\ell(x;S)-\eta)_{+}+\eta\right].$

The dual of CVaR is non-differentiable, which is undesirable from an
optimization viewpoint. To solve this problem, (Jin et al. 2021) proposed a
new divergence function, which can be seen as a smoothed version of the CVaR.
Their experiment results show the optimization of smoothed CVaR is much
easier. However, (Jin et al. 2021)’s method only works for the penalized
formulation of DRO. We will show that our method can solve the constrained
smoothed CVaR.

Here, the divergence function is

$\displaystyle\varphi_{s}(t)=\begin{cases}t\log(t)+\frac{1-\mu
t}{\mu}\log(\frac{1-\mu t}{1-\mu}),&t\in[0,\frac{1}{\mu});\\\ +\infty,&\text{
otherwise.}\end{cases}$ (16)

The corresponding conjugate function is

$\displaystyle\varphi_{s}^{*}(t)=\frac{1}{\mu}\log(1-\mu+\mu\exp(t)).$ (17)

The objective function is then written as

$\displaystyle\inf_{x}\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F_{s}(x;\lambda;\eta)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{S\sim
P_{0}}\left[{\lambda}\varphi_{s}^{*}(\frac{\ell(x;S)-\eta}{\lambda})+\lambda\rho+\eta\right].$
(18)

We can show that there exist upper bounds for the optimal values $\lambda^{*}$
and $\eta^{*}$. There exists a $\bar{\lambda}>0$ only depends on $\mu,B$ and
$\rho$ such that $\lambda^{*}\in[0,\bar{\lambda}]$ and $\eta^{*}\in[0,B]$. The
proof can be found in Appendix F.

This objective function is non-smooth when $\lambda\to 0$. Therefore, we take
a similar approach as the one in Section 3.1 to approximate the original
problem with $\lambda\in[\lambda_{0},\bar{\lambda}]$. We bound the difference
in the following lemma.

Class | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
EMR | 77.64 | 86.19 | 69.33 | 54.03 | 51.53 | 47.05 | 87.66 | 85.35 | 87.12 | 83.15
SFK-DRO | 76.11 | 84.71 | 66.18 | 54.95 | 58.65 | 49.36 | 89.06 | 84.03 | 88.41 | 83.09
PAN-DRO | 74.92 | 85.62 | 65.72 | 52.69 | 55.83 | 49.50 | 88.85 | 84.06 | 88.68 | 81.29
Table 1: Test Accuracy of each class for imbalanced CIFAR 10.

######  Lemma 4.

$\forall x\in\mathbb{R}^{d},\lambda_{0}\geq 0$,

$\displaystyle\left|\inf_{\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[0,B]}F_{s}(x;\lambda;\eta)-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F_{s}(x;\lambda;\eta)\right|\leq 2\lambda_{0}\rho.$

The proof is similar to Lemma 1 thus is omitted here. In addition, we can show
that $F_{s}(x;z)$ is $L_{z}^{\prime}$-smooth and convex in $z$, where
$L_{z}^{\prime}\sim\mathcal{O}(\lambda_{0}^{-3})$ if
$\lambda\in[\lambda_{0},\bar{\lambda}].$ Also it is easy to get $F_{s}(x;z)$
is $L_{x}^{\prime}$-smooth in $x$, where
$L_{x}^{\prime}\sim\mathcal{O}(\lambda_{0}^{-2})$.

Similar to eq. (42) and Remark 1 in (Levy et al. 2020), we can prove that
$\Big{|}\min_{{\lambda\geq
0,\eta\in\mathbb{R}}}\left[F_{s}(x_{t+1};\lambda;\eta)\right]-\mathbb{E}\left[\min_{{\lambda\geq
0,\eta\in\mathbb{R}}}f_{s}(x_{t+1};\lambda;\eta)\right]\Big{|}\sim\mathcal{O}(n_{s}^{-0.5})$.
We then use Algorithm 1 directly and the complexity to get an
$\epsilon$-stationary point is ${\mathcal{O}(\epsilon^{-9})}$. The detailed
proof can be found in Appendix F.

##  6 Numerical Results

In this section, we verify our theoretical results in solving an imbalanced
classification problem. In the experiment, we consider a non-convex loss
function and $k$ is set to be $2$ for the Cressie-Read family. We will show
that 1) although the computational complexity of PGD (Ghadimi, Lan, and Zhang
2016) is of the same order as that of our SFK-DRO algorithm, our numerical
results indicate that our proposed algorithm achieves faster convergence in
practice; 2) The performance proposed algorithm for the constrained DRO
problem outperforms or is close to the performance of the penalized DRO with
respect to the worst classes. Both of them outperform the baseline.
Tasks. We conduct experiments on the imbalanced CIFAR-10 dataset, following
the experimental setting in (Jin et al. 2021; Chou et al. 2020). The original
CIFAR-10 test dataset consists of $10$ classes, where each of the classes has
5000 images. We randomly select training samples from the original set for
each class with the following sampling ratio:
$\\{0.804,0.543,0.997,0.593,0.390,0.285,0.959,0.806,\\\ 0.967,0.660\\}$. We
keep the test dataset unchanged.
Models. We learn the standard Alexnet model in (Krizhevsky, Sutskever, and
Hinton 2012) with the standard cross-entropy (CE) loss. For the comparison of
convergence rate, we optimize the same dual objective with the PGD algorithm
in (Ghadimi, Lan, and Zhang 2016). To compare robustness, we optimize the ERM
via vanilla SGD. In addition, we propose an algorithm PAN-DRO, which fixes
$\lambda$ and only optimizes $\eta$ and the neural network. Thus it gets the
solution for the penalized DRO problem.
Training Details. We set $\lambda_{1}=1,\eta_{1}=0$,
$\lambda_{0}=0.1,-\bar{\eta}=-10$, and the upper bounds
$\bar{\lambda}=10,B=10$. To achieve a faster optimization rate, we set the
learning rate $\alpha=0.01$ before the first $40$ epochs and $\alpha=0.001$
after. The mini-batch size is chosen to be $128$. All of the results are
moving averaged by a window with size $5$. The simulations are repeated by 4
times.
Results. In Figure 1, we plot the value of the CE loss using different
algorithms through the training process. It can be seen that to optimize the
same dual objective function with the same learning rate, the PGD algorithm
converges slower than our proposed DRO algorithms. Moreover, compared with
ERM, the DRO algorithms have higher training losses but lower test losses,
which demonstrates they are robust.

Figure 1: Training curve of classification task.

We also provide the test accuracy of trained models in Table 1. It can be
shown that for class $3,4,5$, the accuracies are the lowest due to the limited
samples. For these classes, the performance of our SFK-DRO algorithm for the
constrained DRO is better or close to the performance of PAN-DRO for the
penalized DRO. Both DRO algorithms outperform the vanilla ERM algorithm.

##  7 Conclusion

In this paper, we developed the first stochastic algorithm for large-scale
non-convex stochastic constrained DRO problems in the literature with
theoretical convergence and complexity guarantee. We developed a smooth and
Lipschitz approximation with bounded approximation error to the original
problem.Compared with existing algorithms, the numerical results show that our
proposed algorithm converges faster. The computational complexity at each
iteration is independent of the size of the training dataset, and thus our
algorithm is applicable to large scale applications. Our results hold for a
general family of Cressie-Read divergences.

## Acknowledgments

This work of Q. Zhang and S. Zou is supported by the National Science
Foundation under Grants CCF-2106560. Department of Education. Y. Zhou’s work
is supported by the National Science Foundation under Grants CCF-2106216,
DMS-2134223 and ECCS-2237830 (CAREER). L. Shen’s work is supported by the NSF
under Grant DMS-2208385.

This material is based upon work supported under the AI Research Institutes
program by National Science Foundation and the Institute of Education
Sciences, U.S. Department of Education through Award No. 2229873 - National AI
Institute for Exceptional Education. Any opinions, findings and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation, the
Institute of Education Sciences, or the U.S.

## References

  * Ali and Silvey (1966) Ali, S. M.; and Silvey, S. D. 1966.  A general class of coefficients of divergence of one distribution from another.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 28(1): 131–142.
  * Ben-Tal et al. (2013) Ben-Tal, A.; Den Hertog, D.; De Waegenaere, A.; Melenberg, B.; and Rennen, G. 2013\.  Robust solutions of optimization problems affected by uncertain probabilities.  _Management Science_ , 59(2): 341–357.
  * Blitzer, McDonald, and Pereira (2006) Blitzer, J.; McDonald, R.; and Pereira, F. 2006.  Domain adaptation with structural correspondence learning.  In _Proceedings of the 2006 conference on empirical methods in natural language processing_ , 120–128.
  * Chou et al. (2020) Chou, H.-P.; Chang, S.-C.; Pan, J.-Y.; Wei, W.; and Juan, D.-C. 2020.  Remix: rebalanced mixup.  In _Proceedings of Computer Vision–ECCV 2020 Workshops: Glasgow, UK, August 23–28, 2020, Proceedings, Part VI 16_ , 95–110. Springer.
  * Cressie and Read (1984) Cressie, N.; and Read, T. R. 1984.  Multinomial goodness-of-fit tests.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 46(3): 440–464.
  * Csiszár (1967) Csiszár, I. 1967.  On information-type measure of difference of probability distributions and indirect observations.  _Studia Sci. Math. Hungar._ , 2: 299–318.
  * Curi et al. (2020) Curi, S.; Levy, K. Y.; Jegelka, S.; and Krause, A. 2020.  Adaptive sampling for stochastic risk-averse learning.  In _Proceedings of Advances in Neural Information Processing Systems_ , volume 33, 1036–1047.
  * Daume III and Marcu (2006) Daume III, H.; and Marcu, D. 2006.  Domain adaptation for statistical classifiers.  _Journal of artificial Intelligence research_ , 26: 101–126.
  * Duchi and Namkoong (2018) Duchi, J.; and Namkoong, H. 2018.  Learning models with uniform performance via distributionally robust optimization.  _arXiv preprint arXiv:1810.08750_.
  * Duchi, Glynn, and Namkoong (2021) Duchi, J. C.; Glynn, P. W.; and Namkoong, H. 2021.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 46(3): 946–969.
  * Frank, Wolfe et al. (1956) Frank, M.; Wolfe, P.; et al. 1956.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2): 95–110.
  * Ghadimi, Lan, and Zhang (2016) Ghadimi, S.; Lan, G.; and Zhang, H. 2016.  Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization.  _Mathematical Programming_ , 155(1-2): 267–305.
  * Ghosh, Squillante, and Wollega (2018) Ghosh, S.; Squillante, M.; and Wollega, E. 2018.  Efficient stochastic gradient descent for distributionally robust learning.  _arXiv preprint arXiv:1805.08728_.
  * Goodfellow, Shlens, and Szegedy (2014) Goodfellow, I. J.; Shlens, J.; and Szegedy, C. 2014.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_.
  * Gower et al. (2019) Gower, R. M.; Loizou, N.; Qian, X.; Sailanbayev, A.; Shulgin, E.; and Richtárik, P. 2019.  SGD: General analysis and improved rates.  In _Proceedings of International conference on machine learning_ , 5200–5209. PMLR.
  * Grother et al. (2011) Grother, P. J.; Grother, P. J.; Phillips, P. J.; and Quinn, G. W. 2011.  _Report on the evaluation of 2D still-image face recognition algorithms_.  US Department of Commerce, National Institute of Standards and Technology.
  * Hashimoto et al. (2018) Hashimoto, T.; Srivastava, M.; Namkoong, H.; and Liang, P. 2018.  Fairness without demographics in repeated loss minimization.  In _Proceedings of International Conference on Machine Learning_ , 1929–1938. PMLR.
  * Hovy and Søgaard (2015) Hovy, D.; and Søgaard, A. 2015.  Tagging performance correlates with author age.  In _Proceedings of the 53rd annual meeting of the Association for Computational Linguistics and the 7th international joint conference on natural language processing (volume 2: Short papers)_ , 483–488.
  * Hu and Hong (2013) Hu, Z.; and Hong, L. J. 2013.  Kullback-Leibler divergence constrained distributionally robust optimization.  _Available at Optimization Online_ , 1(2): 9.
  * Jaggi (2013) Jaggi, M. 2013.  Revisiting Frank-Wolfe: Projection-free sparse convex optimization.  In _Proceedings of International conference on machine learning_ , 427–435. PMLR.
  * Jin et al. (2021) Jin, J.; Zhang, B.; Wang, H.; and Wang, L. 2021.  Non-convex distributionally robust optimization: Non-asymptotic analysis.  In _Proceedings of Advances in Neural Information Processing Systems_ , volume 34, 2771–2782.
  * Krizhevsky, Sutskever, and Hinton (2012) Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012.  Imagenet classification with deep convolutional neural networks.  In _Proceedings of Advances in neural information processing systems_ , volume 25.
  * Lacoste-Julien (2016) Lacoste-Julien, S. 2016.  Convergence rate of frank-wolfe for non-convex objectives.  _arXiv preprint arXiv:1607.00345_.
  * Levy et al. (2020) Levy, D.; Carmon, Y.; Duchi, J. C.; and Sidford, A. 2020.  Large-scale methods for distributionally robust optimization.  In _Proceedings of Advances in Neural Information Processing Systems_ , volume 33, 8847–8860.
  * Lin, Jin, and Jordan (2020) Lin, T.; Jin, C.; and Jordan, M. 2020.  On gradient descent ascent for nonconvex-concave minimax problems.  In _Proceedings of International Conference on Machine Learning_ , 6083–6093. PMLR.
  * Madry et al. (2017) Madry, A.; Makelov, A.; Schmidt, L.; Tsipras, D.; and Vladu, A. 2017.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_.
  * Moulines and Bach (2011) Moulines, E.; and Bach, F. 2011.  Non-asymptotic analysis of stochastic approximation algorithms for machine learning.  _Advances in neural information processing systems_ , 24.
  * Namkoong and Duchi (2016) Namkoong, H.; and Duchi, J. C. 2016.  Stochastic gradient methods for distributionally robust optimization with f-divergences.  In _Proceedings of Advances in neural information processing systems_ , volume 29.
  * Nesterov (2003) Nesterov, Y. 2003.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media.
  * Qi et al. (2021) Qi, Q.; Guo, Z.; Xu, Y.; Jin, R.; and Yang, T. 2021.  An online method for a class of distributionally robust optimization with non-convex objectives.  In _Proceedings of Advances in Neural Information Processing Systems_ , volume 34, 10067–10080.
  * Qi et al. (2022) Qi, Q.; Lyu, J.; Bai, E. W.; Yang, T.; et al. 2022.  Stochastic constrained dro with a complexity independent of sample size.  _arXiv preprint arXiv:2210.05740_.
  * Rafique et al. (2022) Rafique, H.; Liu, M.; Lin, Q.; and Yang, T. 2022.  Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning.  _Optimization Methods and Software_ , 37(3): 1087–1121.
  * Rahimian and Mehrotra (2019) Rahimian, H.; and Mehrotra, S. 2019.  Distributionally robust optimization: A review.  _arXiv preprint arXiv:1908.05659_.
  * Robbins and Monro (1951) Robbins, H.; and Monro, S. 1951.  A stochastic approximation method.  _The annals of mathematical statistics_ , 400–407.
  * Rockafellar, Uryasev et al. (2000) Rockafellar, R. T.; Uryasev, S.; et al. 2000.  Optimization of conditional value-at-risk.  _Journal of risk_ , 2: 21–42.
  * Rockafellar and Wets (1998) Rockafellar, R. T.; and Wets, R. J. 1998.  _Variational Analysis_.  Springer.
  * Shapiro (2017) Shapiro, A. 2017.  Distributionally robust stochastic programming.  _SIAM Journal on Optimization_ , 27(4): 2258–2275.
  * Sinha et al. (2017) Sinha, A.; Namkoong, H.; Volpi, R.; and Duchi, J. 2017.  Certifying some distributional robustness with principled adversarial training.  _arXiv preprint arXiv:1710.10571_.
  * Soma and Yoshida (2020) Soma, T.; and Yoshida, Y. 2020.  Statistical learning with conditional value at risk.  _arXiv preprint arXiv:2002.05826_.
  * Tamar, Glassner, and Mannor (2015) Tamar, A.; Glassner, Y.; and Mannor, S. 2015.  Optimizing the CVaR via sampling.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29.
  * Van Erven and Harremos (2014) Van Erven, T.; and Harremos, P. 2014.  Rényi divergence and Kullback-Leibler divergence.  _IEEE Transactions on Information Theory_ , 60(7): 3797–3820.
  * Wang, Gao, and Xie (2021) Wang, J.; Gao, R.; and Xie, Y. 2021.  Sinkhorn distributionally robust optimization.  _arXiv preprint arXiv:2109.11926_.
  * Xu et al. (2023) Xu, Z.; Zhang, H.; Xu, Y.; and Lan, G. 2023.  A unified single-loop alternating gradient projection algorithm for nonconvex–concave and convex–nonconcave minimax problems.  _Mathematical Programming_ , 1–72.

##  Appendix A Bounds on the parameters

###### Proof.

Firstly, we show for bounded loss function $\ell$, the optimal value
$\lambda^{*}$ has an upper bound. If $\lambda^{*}=0$, then absolutely it has
an upper bound. Otherwise, denote by $\lambda^{*}(\eta)$ for the optimal value
of $\lambda$ given $\eta$ and $\lambda^{*}=\lambda^{*}(\eta^{*})$. We then
have $\nabla_{\lambda}F(x;\lambda^{*}(\eta);\eta)=0$ since $F(x;\lambda;\eta)$
is convex in $\lambda$ and $\eta$ (which will be shown in ). It then follows
that

$\displaystyle\lambda^{*}(\eta)=(k-1)\omega^{-1}\mathbb{E}_{S\sim
P_{0}}\left[(\ell(x;S)-\eta)_{+}^{k_{*}}\right]^{\frac{1}{k_{*}}}.$ (19)

If $\eta^{*}\geq 0$, then $\lambda^{*}(\eta^{*})\leq(k-1)\omega^{-1}B$.
If $\eta^{*}<0$, combine (8) and (19), the objective changes into

$\displaystyle\inf_{x;\eta\in\mathbb{R}}\bar{F}(x;\eta)=\omega\left(\mathbb{E}_{S\sim
P_{0}}(\ell(x;S)-\eta)_{+}^{k_{*}}\right)^{1/k_{*}}+\eta.$

For the optimal value $\eta^{*}$, we have
$\nabla_{\eta}\bar{F}(x;\eta^{*})=0$. It follows that

$\displaystyle\nabla_{\eta}\bar{F}(x;\eta^{*})$ $\displaystyle=$
$\displaystyle-\omega\left(\mathbb{E}_{S\sim
P_{0}}(\ell(x;S)-\eta^{*})_{+}^{k_{*}}\right)^{\frac{1-k_{*}}{k_{*}}}$
$\displaystyle\times\left(\mathbb{E}_{S\sim
P_{0}}(\ell(x;S)-\eta^{*})_{+}^{k_{*}-1}\right)+1=0.$

Therefore, we have

$\displaystyle\frac{1}{\omega}$ $\displaystyle=\frac{\mathbb{E}_{S\sim
P_{0}}(\ell(x;S)-\eta^{*})_{+}^{k_{*}-1}}{\left[\mathbb{E}_{S\sim
P_{0}}(\ell(x;S)-\eta^{*})_{+}^{k_{*}}\right]^{1-\frac{1}{k_{*}}}}$
$\displaystyle\geq\frac{|\eta^{*}|^{k_{*}-1}}{(B+|\eta^{*}|)^{k_{*}-1}},$

where the last inequality is due to the fact that $\ell(x;S)$ is bounded.
Since $\omega>1$, we have that

$\displaystyle|\eta^{*}|\leq\frac{(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}B}{1-(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}}.$

Thus, from (19) we have that

$\displaystyle\lambda^{*}\leq(k-1)\omega^{-1}\left(1+\frac{(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}}{1-(\frac{1}{\omega})^{\frac{1}{k_{*}-1}}}\right)B=\bar{\lambda},$
(20)

where $\bar{\lambda}$ only depands on the parameter $k$ and the upper bound on
the loss function $B$. In addition, for any fixed $\lambda$, for the optimal
value $\eta^{*}(\lambda)$, we have
$\nabla_{\eta}F(x;\lambda;\eta^{*}(\lambda))=0$. Thus, we have

$\displaystyle\mathbb{E}_{S\sim P_{0}}\Big{[}$
$\displaystyle({\ell(x;S)-\eta^{*}(\lambda)})_{+}^{k_{*}-1}\Big{]}=\lambda^{k_{*}-1}\frac{k}{(k-1)^{k_{*}}k_{*}}.$

Since $\lambda\in[\lambda_{0},\bar{\lambda}],$ we have
$\eta^{*}\in[-\bar{\eta},B]$, where
$\bar{\eta}=\bar{\lambda}\left(\frac{k}{(k-1)^{k_{*}}k_{*}}\right)^{\frac{1}{k_{*}-1}}$.
This completes the proof. ∎

##  Appendix B Proof of Lemma 1

###### Proof.

We consider the following question first:

$\sup_{D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim Q}\
\ell(x;S)-\lambda_{0}D_{\varphi_{k}}(Q\|P_{0}).$

Suppose $\zeta(s)=\frac{dQ(s)}{dP_{0}(s)}$, then the question can be written
as

$\displaystyle\sup_{\zeta\succeq
0}\int\ell(x;S)\zeta-\lambda_{0}\varphi_{k}(\zeta)dP_{0}$ $\displaystyle
s.t.\int\varphi_{k}(\zeta)dP_{0}\leq\rho,\int\zeta dP_{0}=1.$

The Lagrangian of the above problem can be written as

$\displaystyle\mathcal{L}(x;\zeta;\lambda;\eta)=$
$\displaystyle\int\ell(x;S)\zeta-(\lambda_{0}+\lambda)\varphi_{k}(\zeta)-\eta\zeta
dP_{0}$ $\displaystyle+\lambda\rho+\eta.$

The problem is equivalent to

$\displaystyle\sup_{\zeta\succeq 0}\inf_{\lambda\geq
0,\eta}\mathcal{L}(x;\zeta;\lambda;\eta).$

Since the Slater condition holds, we can exchange the positions of $\sup$ and
$\inf$ thus getting the dual form

$\displaystyle\inf_{\lambda\geq 0,\eta}\lambda\rho+\eta+\sup_{\zeta\succeq
0}\int\ell(x;S)\zeta-(\lambda_{0}+\lambda)\varphi_{k}(\zeta)-\eta\zeta
dP_{0}.$

Since the maximum operation can be moved inside the integral ( Theorem 14.60
of (Rockafellar and Wets 1998)), we have that

$\displaystyle\sup_{\zeta\succeq
0}\int\ell(x;S)\zeta-(\lambda_{0}+\lambda)\varphi_{k}(\zeta)-\eta\zeta dP_{0}$
$\displaystyle=\int\sup_{\zeta\succeq
0}\ell(x;S)\zeta-(\lambda_{0}+\lambda)\varphi_{k}(\zeta)-\eta\zeta dP_{0}$
$\displaystyle=\int\sup_{\zeta\succeq
0}\zeta[\ell(x;S)-\eta]-(\lambda_{0}+\lambda)\varphi_{k}(\zeta)dP_{0}$
$\displaystyle=\int((\lambda_{0}+\lambda)\varphi_{k})^{*}(\ell(x;S)-\eta)dP_{0}.$

For each $\lambda>0$ we get
$(\lambda\varphi(\ell))^{*}=\lambda\varphi^{*}(\frac{\ell}{\lambda})$.
Therefore, the objective function changes into

$\displaystyle\inf_{\lambda\geq
0,\eta}\lambda\rho+\eta+(\lambda_{0}+\lambda)\mathbb{E}_{S\sim
P_{0}}\varphi_{k}^{*}\left(\frac{\ell(x;S)-\eta}{\lambda_{0}+\lambda}\right).$

We then have

$\displaystyle\inf_{\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[-\bar{\eta},B]}F(x;\lambda;\eta)-\lambda_{0}\rho$
$\displaystyle=\inf_{\lambda\geq\lambda_{0},\tilde{\eta}\in\mathbb{R}}\mathbb{E}_{S\sim
P_{0}}\left[\lambda\varphi_{k}^{*}(\frac{\ell(x;S)-\tilde{\eta}}{\lambda})+(\lambda-\lambda_{0})\rho+\tilde{\eta}\right]$
$\displaystyle=\sup_{D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim Q}\
\ell(x;S)-\lambda_{0}D_{\varphi_{k}}(Q\|P_{0}),$ (21)

where the first equality is due to the definition of $F$,
$\lambda^{*}\in[\lambda_{0},\bar{\lambda}],\eta^{*}\in[-\bar{\eta},B]$, and
the second equality is due to the strong duality we provide above. Moreover,
we have

$\displaystyle\sup_{D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim Q}\
\ell(x;S)$
$\displaystyle-\sup_{D_{\varphi_{k}}(Q\|P_{0})\leq\rho}\mathbb{E}_{S\sim Q}\
\ell(x;S)-\lambda_{0}D_{\varphi_{k}}(Q\|P_{0})$
$\displaystyle\leq\lambda_{0}\rho.$ (22)

Combining (8),(21) and (22), we complete the proof. ∎

##  Appendix C Proof of Lemma 2

###### Proof.

From (7), (8) we only need to prove $\phi(x;z)=\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{1-k_{*}}\right]$ is convex
and smooth in $z$ and smooth in $x$.

Firstly, we have

$\nabla_{\lambda}\phi(x;z)=(1-k_{*})\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{-k_{*}}\right]$

and

$\nabla_{\eta}\phi(x;z)=-k_{*}\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}-1}\lambda^{1-k_{*}}\right].$

If $k_{*}=2$, the problem becomes a $\chi^{2}$-DRP problem and
$\nabla_{\eta}\phi(z)$ is not differentiable when $\ell(x;S)-\eta=0$. For any
$z_{1}=(\lambda_{1};\eta_{1}),z_{2}=(\lambda_{2};\eta_{2})$ where
$\lambda_{1},\lambda_{2}\in[\lambda_{0},\bar{\lambda}]$, we have that for any
fixed $s\in\mathbb{S}$ and $a\in[0,1]$

$\displaystyle
2\lambda_{1}\lambda_{2}(\ell(x;s)-\eta_{1})_{+}(\ell(x;s)-\eta_{2})_{+}$
$\displaystyle\leq\lambda_{1}^{2}(\ell(x;s)-\eta_{2})_{+}^{2}+\lambda_{2}^{2}(\ell(x;s)-\eta_{1})_{+}^{2}.$

Thus, we have

$\displaystyle\lambda_{1}\lambda_{2}\big{(}a^{2}(\ell(x;s)-\eta_{1})_{+}^{2}+(1-a)^{2}(\ell(x;s)-\eta_{2})_{+}^{2}$
$\displaystyle+2a(1-a)(\ell(x;s)-\eta_{1})_{+}(\ell(x;s)-\eta_{2})_{+}\big{)}$
$\displaystyle\leq$
$\displaystyle(a(1-a)\lambda_{1}^{2}+(1-a)^{2}\lambda_{1}\lambda_{2})(\ell(x;s)-\eta_{2})_{+}^{2}$
$\displaystyle+(a(1-a)\lambda_{2}^{2}+a^{2}\lambda_{1}\lambda_{2})(\ell(x;s)-\eta_{1})_{+}^{2}.$
(23)

In addition, we have

$\displaystyle\left(\ell(x;s)-{a\eta_{1}+(1-a)\eta_{2}}\right)_{+}^{2}$
$\displaystyle\leq$ $\displaystyle
a^{2}(\ell(x;s)-\eta_{1})_{+}^{2}+(1-a)^{2}(\ell(x;s)-\eta_{2})_{+}^{2}$
$\displaystyle+2a(1-a)(\ell(x;s)-\eta_{1})_{+}(\ell(x;s)-\eta_{2})_{+}.$ (24)

Combine (23) and (24), we can get

$\displaystyle\frac{1}{a\lambda_{1}+(1-a)\lambda_{2}}\left(\ell(x;s)-{a\eta_{1}-(1-a)\eta_{2}}\right)^{2}_{+}$
$\displaystyle\leq$
$\displaystyle\left(\frac{a}{\lambda_{1}}(\ell(x;s)-\eta_{1})_{+}^{2}+\frac{1-a}{\lambda_{2}}(\ell(x;s)-\eta_{2})_{+}^{2}\right).$
(25)

Take expectations for both sides, we have

$\displaystyle\phi\left(x;az_{1}+(1-a)z_{2}\right)\leq
a\phi(x,z_{1})+(1-a)\phi(x,z_{2}),$

which demonstrates both $\phi(x;z)$ and $F(x;z)$ is convex in $z$. We then
show $F$ is smooth in $z$. We have that

$\displaystyle\|$
$\displaystyle\nabla_{z}\phi(x;z_{1})-\nabla_{z}\phi(x;z_{2}))\|$
$\displaystyle=$ $\displaystyle\left|2\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{1})_{+}}{\lambda_{1}}-\frac{(\ell(x;s)-\eta_{2})_{+}}{\lambda_{2}}\right]\right|$
$\displaystyle+\left|\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{1})_{+}^{2}}{\lambda_{1}^{2}}-\frac{(\ell(x;s)-\eta_{2})_{+}^{2}}{\lambda_{2}^{2}}\right]\right|$
$\displaystyle\leq$ $\displaystyle\left|2\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{1})_{+}}{\lambda_{1}}-\frac{(\ell(x;s)-\eta_{2})_{+}}{\lambda_{1}}\right]\right|$
$\displaystyle+\left|2\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{2})_{+}}{\lambda_{1}}-\frac{(\ell(x;s)-\eta_{2})_{+}}{\lambda_{2}}\right]\right|$
$\displaystyle+\left|\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{1})_{+}^{2}}{\lambda_{1}^{2}}-\frac{(\ell(x;s)-\eta_{2})_{+}^{2}}{\lambda_{1}^{2}}\right]\right|$
$\displaystyle+\left|\mathbb{E}_{s\sim
P_{0}}\left[\frac{(\ell(x;s)-\eta_{2})_{+}^{2}}{\lambda_{1}^{2}}-\frac{(\ell(x;s)-\eta_{2})_{+}^{2}}{\lambda_{2}^{2}}\right]\right|$
$\displaystyle\leq$
$\displaystyle\frac{2|\eta_{1}-\eta_{2}|}{\lambda_{0}}+\frac{2(B+\bar{\eta})}{\lambda_{0}^{2}}|\lambda_{1}-\lambda_{2}|+\frac{2(B+\bar{\eta})}{\lambda_{0}^{2}}|\eta_{1}-\eta_{2}|$
$\displaystyle+\frac{(B+\bar{\eta})^{2}}{\lambda_{0}^{3}}|\lambda_{1}-\lambda_{2}|$
$\displaystyle\leq$
$\displaystyle\left(\frac{2}{\lambda_{0}}+\frac{4(B+\bar{\eta})}{\lambda_{0}^{2}}+\frac{{2}(B+\bar{\eta})^{2}}{\lambda_{0}^{3}}\right)|z_{1}-z_{2}|.$

Therefore, $\phi(x;z)$ is
$\frac{2}{\lambda_{0}}+\frac{4(B+\bar{\eta})}{\lambda_{0}^{2}}+\frac{{2}(B+\bar{\eta})^{2}}{\lambda_{0}^{3}}$-smooth
and $F(x,z)$ is
$\frac{1}{\lambda_{0}}+\frac{2(B+\bar{\eta})}{\lambda_{0}^{2}}+\frac{(B+\bar{\eta})^{2}}{\lambda_{0}^{3}}$-smooth
in $z$.
If $k_{*}>2$, $\nabla_{\eta}\phi(z)$ is differentiable. We can get the Hessian
matrix of $\phi$ with respect to $z$ as:

$\displaystyle H=\begin{bmatrix}k_{*}(k_{*}-1)\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{-k_{*}-1}\right],\\\
k_{*}(k_{*}-1)\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}-1}\lambda^{-k_{*}}\right];\\\
k_{*}(k_{*}-1)\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}-1}\lambda^{-k_{*}}\right],\\\
k_{*}(k_{*}-1)\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}-2}\lambda^{1-k_{*}}\right]\end{bmatrix}.$

Suppose $a_{1},a_{2}$ are the eigenvalues of $H$. We have

$\displaystyle a_{1}+a_{2}$
$\displaystyle=tr(H)=k_{*}(k_{*}-1)\mathbb{E}_{S\sim P_{0}}\Big{[}$
$\displaystyle({\ell(x;S)-\eta})_{+}^{k_{*}}\lambda^{-k_{*}-1}+({\ell(x;S)-\eta})_{+}^{k_{*}-2}\lambda^{1-k_{*}}\Big{]}$
$\displaystyle\geq 0$

and

$\displaystyle a_{1}a_{2}$
$\displaystyle=det(H)=k_{*}^{2}(k_{*}-1)^{2}\lambda^{-2k_{*}}$
$\displaystyle\times$ $\displaystyle\Big{(}\mathbb{E}_{S\sim
P_{0}}({\ell(x;S)-\eta})_{+}^{k_{*}}\mathbb{E}_{S\sim
P_{0}}({\ell(x;S)-\eta})_{+}^{k_{*}-2}$ $\displaystyle-$
$\displaystyle\left(E_{S\sim
P_{0}}({\ell(x;S)-\eta})_{+}^{k_{*}-1}\right)^{2}\Big{)}\geq 0.$

Thus $H$ is semi-positive definite which demonstrates $\phi$ is convex in $z$.
Moreover, the smooth constant should be the largest eigenvalue. Therefore we
get

$\displaystyle
L_{z}=\frac{(k-1)^{k_{*}}}{k}k_{*}(k_{*}-1)\left(\frac{(B+\bar{\eta})^{k_{*}}}{\lambda_{0}^{k_{*}+1}}+\frac{(B+\bar{\eta})^{k_{*}-2}}{\lambda_{0}^{k_{*}-1}}\right)$

Now we prove the objective is $L_{x}$-smooth in $x$. Firstly, we have

$\nabla_{x}\phi(x;z)=k_{*}\lambda^{1-k_{*}}\mathbb{E}_{S\sim
P_{0}}\left[({\ell(x;S)-\eta})_{+}^{k_{*}-1}\nabla_{x}\ell\right].$

For any $x_{1},x_{2}$ we have that

$\displaystyle\|$
$\displaystyle\nabla_{x}\phi(x_{1};z)-\nabla_{x}\phi(x_{2};z))\|$
$\displaystyle\leq$ $\displaystyle
k_{*}\lambda^{1-k_{*}}\big{\|}\mathbb{E}_{S\sim
P_{0}}\big{[}({\ell(x_{1};S)-\eta})_{+}^{k_{*}-1}\nabla_{x}\ell(x_{1};S)$
$\displaystyle-({\ell(x_{2};S)-\eta})_{+}^{k_{*}-1}\nabla_{x}\ell(x_{1};S)\big{]}\big{\|}$
$\displaystyle+k_{*}\lambda^{1-k_{*}}\big{\|}\mathbb{E}_{S\sim
P_{0}}\big{[}({\ell(x_{2};S)-\eta})_{+}^{k_{*}-1}$
$\displaystyle\times(\nabla_{x}\ell(x_{2};S)-\nabla_{x}\ell(x_{1};S))\big{]}\big{\|}.$

Since we have

$\displaystyle\|({\ell(x_{1};S)-\eta})_{+}^{k_{*}-1}-({\ell(x_{2};S)-\eta})_{+}^{k_{*}-1}\|$
$\displaystyle\leq$
$\displaystyle(B+\bar{\eta})^{k_{*}-2}\|\ell(x_{1};S)-\ell(x_{2};S)\|$
$\displaystyle\leq$
$\displaystyle(k_{*}-1)(B+\bar{\eta})^{k_{*}-2}G\|x_{1}-x_{2}\|,$

where the first inequality is because both $\ell(x;S)$ and $\eta$ are bounded.
And the second inequality is due to the fact that $\ell$ is smooth. Thus we
have that

$\displaystyle\|({\ell(x_{1};S)-\eta})_{+}^{k_{*}-1}-({\ell(x_{2};S)-\eta})_{+}^{k_{*}-1}\|$
$\displaystyle\leq$ $\displaystyle
k_{*}\lambda^{1-k_{*}}(B+\bar{\eta})^{k_{*}-2}(k_{*}-1)G^{2}\|x_{1}-x_{2}\|$
$\displaystyle+k_{*}\lambda^{1-k_{*}}(B+\bar{\eta})^{k_{*}-1}L\|x_{1}-x_{2}\|.$

Therefore, $\phi(x;z)$ is
$k_{*}\lambda^{1-k_{*}}(B+\bar{\eta})^{k_{*}-2}((k_{*}-1)G^{2}+(B+\bar{\eta})L)$-smooth
and $F(x,z)$ is
$\frac{(k-1)^{k_{*}}}{k}k_{*}\lambda^{1-k_{*}}(B+\bar{\eta})^{k_{*}-2}((k_{*}-1)G^{2}+(B+\bar{\eta})L)$-smooth
in $x$.

∎

##  Appendix D Proof of Theorem 1

###### Proof.

For the update of $x$, we have that

$\displaystyle x_{t+1}=x_{t}-\alpha\nabla_{x}f_{x}(x_{t};z_{t}).$

Since $F(x,z)$ is $L_{x}$-smooth in $x$, we have

$\displaystyle F(x_{t+1};z_{t})$ $\displaystyle\leq$ $\displaystyle
F(x_{t};z_{t})+\langle\nabla_{x}F(x_{t};z_{t}),x_{t+1}-x_{t}\rangle$
$\displaystyle+\frac{L_{x}}{2}\|x_{t+1}-x_{t}\|^{2}$ $\displaystyle=$
$\displaystyle
F(x_{t};z_{t})-\alpha\nabla_{x}f_{x}(x_{t};z_{t})^{\top}\nabla_{x}F(x_{t};z_{t})$
$\displaystyle+\frac{\alpha^{2}L_{x}}{2}\|\nabla_{x}f_{x}(x_{t};z_{t})\|^{2}$
$\displaystyle=$ $\displaystyle
F(x_{t};z_{t})-\alpha\nabla_{x}f_{x}(x_{t};z_{t})^{\top}\nabla_{x}F(x_{t};z_{t})$
$\displaystyle+\frac{\alpha^{2}L_{x}}{2}\|\nabla_{x}f_{x}(x_{t};z_{t})-\nabla_{x}F(x_{t};z_{t})+\nabla_{x}F(x_{t};z_{t})\|^{2}$
$\displaystyle\leq$ $\displaystyle
F(x_{t};z_{t})-\alpha\nabla_{x}f_{x}(x_{t};z_{t})^{\top}\nabla_{x}F(x_{t};z_{t})$
$\displaystyle+{\alpha^{2}L_{x}}\|\nabla_{x}f_{x}(x_{t};z_{t})-\nabla_{x}F(x_{t};z_{t})\|^{2}$
$\displaystyle+{\alpha^{2}L_{x}}\|\nabla_{x}F(x_{t};z_{t})\|^{2}.$ (26)

Given $x_{t}$ and $z_{t}$, take the expectation for both sides of (24), we
have that

$\displaystyle\mathbb{E}[F(x_{t+1};z_{t})|x_{t},z_{t}]$ $\displaystyle\leq$
$\displaystyle F(x_{t};z_{t})-\alpha\|\nabla_{x}F_{x}(x_{t};z_{t})\|^{2}$
$\displaystyle+{\alpha^{2}L_{x}}\mathbb{E}[\|\nabla_{x}f_{x}(x_{t};z_{t})-\nabla_{x}F(x_{t};z_{t})\|^{2}|x_{t},z_{t}]$
$\displaystyle+{\alpha^{2}L_{x}}\|\nabla_{x}F(x_{t};z_{t})\|^{2}.$ (27)

If $\alpha\leq\frac{1}{2L_{x}}$ we have that
$\alpha^{2}L_{x}\leq\frac{\alpha}{2}$ and

$\displaystyle\frac{\alpha}{2}\|\nabla_{x}F_{x}(x_{t};z_{t})\|^{2}\leq$
$\displaystyle F(x_{t};z_{t})-\mathbb{E}[F(x_{t+1};z_{t})|x_{t},z_{t}]$
$\displaystyle+{\alpha^{2}L_{x}}\frac{\sigma_{0}^{2}}{n_{x}},$

where the inequality is because
$\nabla_{x}f(x;z;s)\leq\frac{(k-1)^{k_{*}}}{k}k_{*}(B+\bar{\eta})^{k_{*}-1}G\lambda_{0}^{1-k_{*}}=\sigma_{0}$
is bounded. After that, we take expectations for both sides and we have

$\displaystyle\frac{\alpha}{2}\mathbb{E}\left[\|\nabla_{x}F_{x}(x_{t};z_{t})\|^{2}\right]\leq$
$\displaystyle\mathbb{E}[F(x_{t};z_{t})]-\mathbb{E}[F(x_{t+1};z_{t})]$
$\displaystyle+{\alpha^{2}L_{x}}\frac{\sigma_{0}^{2}}{n_{x}}.$ (28)

For the update of $z$ and $\forall\gamma_{t}\in[0,1]$, we get an affine
invariant version of the standard descent Lemma ((1.2.5) in (Nesterov 2003))

$\displaystyle F(x_{t+1};z_{t+1})$ $\displaystyle\leq$ $\displaystyle
F(x_{t+1};z_{t})+\gamma_{t}\langle\nabla_{z}f_{z}(x_{t+1};z_{t}),d_{t}\rangle+\gamma_{t}\langle\nabla_{z}F(x_{t+1};z_{t})-\nabla_{z}f_{z}(x_{t+1};z_{t}),d_{t}\rangle+\frac{\gamma_{t}^{2}}{2}C,$

where $C\geq D^{2}L_{z}$. In our algorithm we have
$\gamma_{t}=\min\left\\{\frac{g_{t}}{C},1\right\\}$ and

$\displaystyle\frac{g_{t}}{C}$
$\displaystyle\leq\frac{D\|\nabla_{z}f_{z}(x_{t+1};z_{t})\|}{D^{2}L_{z}}$
$\displaystyle\leq\frac{(\rho+\frac{1}{k(k-1)})+\frac{(k-1)^{k_{*}}(k_{*}-1)}{k}\lambda_{0}^{-k_{*}}}{DL_{z}}.$

Since $L_{z}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1})$ thus for small
$\lambda_{0}$ we have $\frac{g_{t}}{C}\leq 1$. Consequently, we can assume
$\gamma=\frac{g_{t}}{C}$ and we have

$\displaystyle F(x_{t+1};z_{t+1})$ $\displaystyle\leq$ $\displaystyle
F(x_{t+1};z_{t})-\frac{g_{t}}{C}g_{t}+\frac{g_{t}^{2}}{4C}+\frac{D^{2}\|\nabla_{z}F(x_{t+1};z_{t})-\nabla_{z}f_{z}(x_{t+1};z_{t})\|^{2}}{C}+\frac{(\frac{g_{t}}{C})^{2}}{2}C.$
(29)

Since $f_{z}(x;z)$ is convex in $z$, we have that $g_{t}\geq
f_{z}(x_{t+1};z_{t})-\min_{z\in\mathcal{M}}f_{z}(x_{t+1};z).$ Take
expectations for both sides of (29), we have that

$\displaystyle\mathbb{E}\left[\frac{g_{t}^{2}}{4C}\right]\leq\mathbb{E}[F(x_{t+1};z_{t})]-\mathbb{E}[F(x_{t+1};z_{t+1})]+\frac{D^{2}\sigma_{1}^{2}}{Cn_{z}}.$
(30)

By recursively adding (28) and (30), we have that

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\frac{\alpha}{2}\mathbb{E}\left[\|\nabla_{x}F_{x}(x_{t};z_{t})\|^{2}\right]+\mathbb{E}\left[\frac{g_{t}^{2}}{4C}\right]$
$\displaystyle\leq\frac{F(x_{1};z_{1})-\mathbb{E}[F(x_{T+1};z_{T+1})]}{T}+{\alpha^{2}L_{x}}\frac{\sigma^{2}}{n_{x}}+\frac{D^{2}\sigma_{1}^{2}}{Cn_{z}}.$

Since $D^{2}L_{z}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1})$ and
$L_{x}\sim\mathcal{O}(\lambda_{0}^{-k_{*}+1})$, we can find $\lambda_{0}$
small enough such that $C\geq D^{2}L_{z}\geq 2L_{x}$. Set
$\alpha=\frac{1}{2C}$, we then have that

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\|\nabla_{x}F_{x}(x_{t};z_{t})\|^{2}\right]+\mathbb{E}\left[{g_{t}^{2}}\right]\leq\frac{4C\Delta}{T}+\frac{L_{x}\sigma^{2}}{n_{x}C}+\frac{4D^{2}\sigma_{1}^{2}}{n_{z}}.$

From Jensen’s inequality, we have that

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\|\nabla_{x}F_{x}(x_{t};z_{t})\|\right]^{2}+\mathbb{E}\left[{g_{t}}\right]^{2}\leq\frac{2C\Delta}{T}+\frac{L_{x}\sigma^{2}}{n_{x}C}+\frac{4D^{2}\sigma_{1}^{2}}{n_{z}}.$

When we set
$T=48C\Delta\epsilon^{-2}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1}\epsilon^{-2}),n_{x}=\frac{12L_{x}\sigma^{2}}{C\epsilon^{2}},$
for some $t^{\prime}\in[1,T]$ we have

$\mathbb{E}\left[\|\nabla_{x}F(x_{t^{\prime}};z_{t^{\prime}})\|\right]\leq\frac{\epsilon}{2}$

and

$\mathbb{E}[g_{t^{\prime}}]\leq\frac{\epsilon}{2}$

Since $F(x;z)$ is $L_{x}$-smooth in $x$, we have that

$\displaystyle\|\nabla_{x}F(x_{t^{\prime}+1};z_{t^{\prime}})-\nabla_{x}F(x_{t^{\prime}};z_{t^{\prime}})\|$
$\displaystyle\leq L_{x}\|x_{t^{\prime}+1}-x_{t^{\prime}}\|$
$\displaystyle\leq
L_{x}\alpha\|\nabla_{x}f_{x}(x_{t^{\prime}};z_{t^{\prime}})\|.$

In addition,

$\displaystyle\mathbb{E}[\|\nabla_{x}f_{x}(x_{t^{\prime}};z_{t^{\prime}})\|^{2}]$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}[\|\nabla_{x}f_{x}(x_{t^{\prime}};z_{t^{\prime}})-\nabla_{x}F(x_{t^{\prime}};z_{t^{\prime}})\|^{2}|x_{t^{\prime}},z_{t^{\prime}}]$
$\displaystyle+2\mathbb{E}[\|\nabla_{x}F(x_{t^{\prime}};z_{t^{\prime}})\|^{2}]$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon^{2}}{2}+\frac{C\epsilon^{2}}{4L_{x}}$

Thus

$\displaystyle\mathbb{E}\left[L_{x}\alpha\|\nabla_{x}f_{x}(x_{t^{\prime}};z_{t^{\prime}})\|\right]\leq\frac{L_{x}}{C}\sqrt{\frac{\epsilon^{2}}{2}+\frac{C\epsilon^{2}}{4L_{x}}}\leq\frac{\epsilon}{2}$

since $C\geq 2L_{x}$. Therefore, we have

$\displaystyle\mathbb{E}[\|\nabla_{x}F(x_{t^{\prime}+1};z_{t^{\prime}})\|]\leq\epsilon.$

In addition, we have

$\displaystyle g_{t^{\prime}}\geq
f_{z}(x_{t^{\prime}+1};z_{t^{\prime}})-\min_{z\in\mathcal{M}}f_{z}(x_{t^{\prime}+1};z).$

Given $x_{t^{\prime}+1}$ and $z_{t^{\prime}}$, take expectations for both
sides and we have

$\displaystyle\mathbb{E}[g_{t^{\prime}}|x_{t^{\prime}+1},z_{t^{\prime}}]\geq
F(x_{t^{\prime}+1};z_{t^{\prime}})-\mathbb{E}\left[\min_{z\in\mathcal{M}}f_{z}(x_{t^{\prime}+1};z)\right].$

Lemma 1 also works for $\widehat{F}_{z}$. By Lemma 1, when
$\lambda_{0}=\frac{\epsilon}{8\rho}$, we have

$\displaystyle\left|\inf_{\lambda\in[\lambda_{0},\bar{\lambda}],\eta\in[-\bar{\eta},B]}f_{z}(x;\lambda;\eta)-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}f_{z}(x;\lambda;\eta)\right|\leq\frac{\epsilon}{4}.$

By Lemma 3 we can get a small $n_{z}$ such that
$3B\sqrt{1+k(k-1)\rho}\sqrt{\frac{4+\log(n_{z})}{4n_{z}}}<\frac{\epsilon}{4}$
if $k_{*}=2$ or
$3B{(1+k(k-1)\rho)^{\frac{1}{k}}}\left(\frac{1}{n_{z}}+\frac{1}{2^{k_{*}-1}(k_{*}-2)n_{z}}\right)^{\frac{1}{k_{*}}}<\frac{\epsilon}{4}$
if $k_{*}>2$. We then have that

$\left|\inf_{\lambda\geq
0,\eta\in\mathbb{R}}\left[F(x_{t^{\prime}+1};\lambda;\eta)\right]-\mathbb{E}\left[\inf_{\lambda\geq
0,\eta\in\mathbb{R}}f_{z}(x_{t^{\prime}+1};\lambda;\eta)\right]\right|\leq\frac{\epsilon}{4}.$

Thus we have

$\displaystyle\mathbb{E}\left[F(x_{t^{\prime}+1};z_{t^{\prime}})-\inf_{\lambda\geq
0,\eta\in\mathbb{R}}F(x_{t^{\prime}+1};\lambda;\eta)\right]\leq\epsilon.$ (31)

which completes the proof. ∎

##  Appendix E Proof of Lemma 3

The (20) of (Levy et al. 2020) provides an inverse-cdf formulation of the DRO
problem. By implementing the inverse-cdf formulation, the (42) and remark 1 of
(Levy et al. 2020) show that

$\displaystyle\left|\min_{\lambda\geq
0,\eta\in\mathbb{R}}\left[F(x;\lambda;\eta)\right]-\mathbb{E}\left[\min_{\lambda\geq
0,\eta\in\mathbb{R}}\widehat{F}_{z}(x;\lambda;\eta)\right]\right|$
$\displaystyle\leq\int_{0}^{1}(r(\beta)-r(1))(\beta\cdot
h(\beta))^{\prime}d\beta$ $\displaystyle\leq\|r\|_{k}\|(\beta\cdot
h(\beta))^{\prime}\|_{k_{*}},$ (32)

where
$r\in\mathcal{R}:=\\{r:[0,1]\to\mathbb{R}_{+}|\int_{0}^{1}r(\beta)d\beta=1\text{
and }\int_{0}^{1}\varphi_{k}(r(\beta))d\beta\leq\rho\\}$,
$h=3B\min\left\\{\sqrt{\frac{1}{\beta n_{z}}},1\right\\}$ and the second
inequality is due to the Hölder’s inequality. Note this inequality holds for
any fixed $x$, no matter whether the loss function is convex or not.
Since $\int_{0}^{1}\varphi_{k}(r(\beta))d\beta\leq\rho$, we have that

$\displaystyle\|r\|_{k}^{k}\leq 1+k(k-1)\rho.$ (33)

Moreover, we have that

$\displaystyle\|(\beta\cdot h(\beta))^{\prime}\|_{k_{*}}^{k_{*}}$
$\displaystyle=\int_{0}^{\frac{1}{n_{z}}}(3B)^{k_{*}}d\beta+\int_{\frac{1}{n_{z}}}^{1}(\frac{3B}{2})^{k_{*}}\sqrt{\frac{1}{(\beta
n_{z})^{k_{*}}}}d\beta.$ (34)

For $k_{*}=2$, we have

$\displaystyle\|(\beta\cdot
h(\beta))^{\prime}\|_{2}^{2}=(3B)^{2}\frac{4+\log(n_{z})}{4n_{z}}$ (35)

and if $k_{*}>2$, we have that

$\displaystyle\|(\beta\cdot h(\beta))^{\prime}\|_{k_{*}}^{k_{*}}$
$\displaystyle\leq(3B)^{k_{*}}\left(\frac{1}{n_{z}}+\frac{1}{2^{k_{*}}}\frac{2}{{k_{*}}{}-2}\frac{n^{0.5k_{*}-1}-1}{n^{0.5k_{*}}}\right)$
$\displaystyle\leq(3B)^{k_{*}}\left(1+\frac{1}{2^{k_{*}-1}(k_{*}-2)}\right)\frac{1}{n_{z}}.$
(36)

Combine (32),(33),(35) and (36), we can get the lemma and complete the proof.

##  Appendix F Proof of smoothed CVaR

###### Proof.

Bounded parameters: We have

$\displaystyle\nabla_{t}\varphi_{s}^{*}(t)=\frac{1}{\mu}\frac{\mu\exp(t)}{1-\mu+\mu\exp(t)}\leq\frac{1}{\mu}$

and

$\displaystyle\nabla_{t}^{2}\varphi_{s}^{*}(t)=\frac{1}{\mu}\frac{\mu(1-\mu)\exp(t)}{(1-\mu+\mu\exp(t))^{2}}\leq\frac{1}{4\mu}$
$\displaystyle\nabla_{\eta}F_{s}(x;\lambda;\eta)=1-\mathbb{E}_{S\sim
P_{0}}{\varphi_{s}^{*}}^{\prime}(\frac{\ell(x;S)-\eta}{\lambda}).$
$\displaystyle\nabla_{\eta}^{2}F_{s}(x;\lambda;\eta)=\frac{1}{\lambda}\mathbb{E}_{S\sim
P_{0}}{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda}).$

If $\eta>B$, then $\nabla_{\eta}F_{s}(x;\lambda;\eta)<0$. If $\eta<0$, then
$\nabla_{\eta}F_{s}(x;\lambda;\eta)>0$. Thus $\eta^{*}\in[0,B]$.

$\displaystyle\nabla_{\lambda}F_{s}(x;\lambda;\eta)=$
$\displaystyle\rho+\mathbb{E}_{S\sim
P_{0}}\Big{[}{\varphi_{s}^{*}}(\frac{\ell(x;S)-\eta}{\lambda})$
$\displaystyle-{\varphi_{s}^{*}}^{\prime}(\frac{\ell(x;S)-\eta}{\lambda})\frac{\ell(x;S)-\eta}{\lambda}\Big{]}.$
$\displaystyle\nabla_{\lambda}^{2}F_{s}(x;\lambda;\eta)=\frac{1}{\lambda^{3}}\mathbb{E}_{S\sim
P_{0}}\left[{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda})(\ell(x;S)-\eta)^{2}\right].$

The second-order demonstrates that the $F_{s}(x;\lambda;\eta)$ is convex in
$\lambda$. We then show that $\lambda^{*}$ has an upper bound. If
$\nabla_{\lambda}F_{s}(x;\lambda;\eta)\geq 0$ when $\lambda\to 0$, then
$\lambda^{*}=0.$ If $\nabla_{\lambda}F_{s}(x;\lambda;\eta)<0$ when $\lambda\to
0$, since both ${\varphi_{s}^{*}}(t),{\varphi_{s}^{*}}^{\prime}(t)$ are
increaing with $t$, we have that

$\displaystyle\nabla_{\lambda}F_{s}(x;\lambda;\eta)>\rho+{\varphi_{s}^{*}}(\frac{-B}{\lambda})-\frac{B}{\mu\lambda}.$
(37)

Since we know
$g(\lambda)=\rho+{\varphi_{s}^{*}}(\frac{-B}{\lambda})-\frac{B}{\mu\lambda}$
is increasing with $\lambda$ and $g(\lambda)<0$ when $\lambda\to 0$,
$g(\lambda)=\rho>0$ when $\lambda\to\infty.$ Thus we can find
$\bar{\lambda}>0$ that $g(\bar{\lambda})=0$. Moreover, the value of
$\bar{\lambda}$ only depends on $\mu,B$ and $\rho$.
Smoothness: fix $x$, the Hessian matrix of $F_{s}(x;z)$ with respect to $z$
as:

$\displaystyle H_{s}=\begin{bmatrix}\frac{1}{\lambda}\mathbb{E}_{S\sim
P_{0}}{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda}),\\\
\frac{1}{\lambda^{2}}\mathbb{E}_{S\sim
P_{0}}\left[{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda})(\ell(x;S)-\eta)\right];\\\
\frac{1}{\lambda^{2}}\mathbb{E}_{S\sim
P_{0}}\left[{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda})(\ell(x;S)-\eta)\right],\\\
\frac{1}{\lambda^{3}}\mathbb{E}_{S\sim
P_{0}}\left[{\varphi_{s}^{*}}^{\prime\prime}(\frac{\ell(x;S)-\eta}{\lambda})(\ell(x;S)-\eta)^{2}\right]\end{bmatrix}.$

Suppose $a_{3},a_{4}$ are the eigenvalues of $H_{s}$. We have $a_{3}+a_{4}>0$
and $a_{3}a_{4}\geq 0$. And the function is $L_{z}^{\prime}$-smooth and convex
in $z$, where $L_{z}^{\prime}\sim\mathcal{O}(\lambda_{0}^{-3})$ if
$\lambda\in[\lambda_{0},\bar{\lambda}].$ Also it is easy to get
$F_{s}(x;\lambda;\eta)$ is $L_{x}^{\prime}$-smooth in $x$, where
$L_{x}^{\prime}\sim\mathcal{O}(\lambda_{0}^{-1})$.
Bounded gap: denote $f_{s}(x,z)=\sum_{i=1}^{n_{s}}\frac{f(x;z;S_{i})}{n_{s}}$,
in order to use algorithm 1 directly, we need to estimate $\min F(x;z)$ via
$\mathbb{E}\min f_{z}(x;z)$ and bound the gap. From the (42) and remark 1 of
(Levy et al. 2020), we have that

$\displaystyle\left|\min_{z\in\mathcal{M}}\left[F_{s}(x_{t+1};z)\right]-\mathbb{E}\left[\min_{z\in\mathcal{M}}f_{s}(x_{t+1};z)\right]\right|$
$\displaystyle\leq\int_{0}^{1}(r(\beta)-r(1))(\beta\cdot
h(\beta))^{\prime}d\beta$ (38)

where
$r\in\mathcal{R}:=\\{r:[0,1]\to\mathbb{R}_{+}|\int_{0}^{1}r(\beta)d\beta=1\text{
and }\int_{0}^{1}\varphi_{s}(r(\beta))d\beta\leq\rho\\}$,
$h=3B\min\left\\{\sqrt{\frac{1}{\beta n_{s}}},1\right\\}$ Since
$\int_{0}^{1}\varphi_{s}(r(\beta))d\beta\leq\rho\\}$, we have that
$r(\beta)\leq\frac{1}{\mu}$ for any Moreover, we have that

$\displaystyle\int_{0}^{1}(\beta\cdot
h(\beta))^{\prime}d\beta=\int_{0}^{\frac{1}{n_{s}}}3Bd\beta+3B\int_{\frac{1}{n_{s}}}^{1}\sqrt{\frac{1}{\beta
n_{s}{}}}d\beta$
$\displaystyle=\frac{3B}{n_{s}}+6B(\sqrt{\frac{1}{n_{s}}}-\frac{1}{n_{s}})$

Thus the gap $\Big{|}\min_{\lambda\geq
0,\eta\in\mathbb{R}}\left[F_{s}(x_{t+1};\lambda;\eta)\right]-\mathbb{E}\left[\min_{\lambda\geq
0,\eta\in\mathbb{R}}f_{s}(x_{t+1};\lambda;\eta)\right]\Big{|}\sim\mathcal{O}(n_{s}^{-0.5})$.
We then can use algorithm 1 directly and the complexity to get the
$\epsilon$-stationary point is $\mathcal{O}(\epsilon^{-9})$. ∎

##  Appendix G Complexity of PGD

###  G.1 Cressie-Read family

In the PGD algorithm (Ghadimi, Lan, and Zhang 2016), $y=(x;\lambda;\eta)$ is
optimized as a whole. From Lemma 2, we know $F(y)=F(x;z)$ is $L_{z}$-smooth in
$z$ and $L_{x}$-smooth in x. Moreover, it is not hard to show that
$\nabla_{x}F(x;z)$ is $L_{xz}$-Lipschitz in $z$ and $\nabla_{z}F(x;z)$ is
$L_{xz}$-Lipschitz in $x$, where
$L_{zx},L_{xz}\sim\mathcal{O}(\lambda_{0}^{-k_{*}})$. Therefore, we have

$\displaystyle\|\nabla_{y}F(y_{1})-\nabla_{y}F(y_{2})\|=$
$\displaystyle\|\nabla_{x}F(x_{1};z_{1})-\nabla_{x}F(x_{2};z_{2})\|+\|\nabla_{z}F(x_{1};z_{1})-\nabla_{z}F(x_{2};z_{2})\|$
$\displaystyle\leq$
$\displaystyle\|\nabla_{x}F(x_{1};z_{1})-\nabla_{x}F(x_{1};z_{2})\|+\|\nabla_{z}F(x_{1};z_{1})-\nabla_{z}F(x_{1};z_{2})\|$
$\displaystyle+\|\nabla_{x}F(x_{1};z_{2})-\nabla_{x}F(x_{2};z_{2})\|+\|\nabla_{z}F(x_{1};z_{2})-\nabla_{z}F(x_{2};z_{2})\|$
$\displaystyle\leq$ $\displaystyle
L_{xz}\|z_{1}-z_{2}\|+L_{z}\|z_{1}-z_{2}\|+L_{zx}\|x_{1}-x_{2}\|+L_{x}\|x_{1}-x_{2}\|$
$\displaystyle\leq$ $\displaystyle(L_{x}+L_{z}+L_{xz}+L_{zx})\|y_{1}-y_{2}\|.$

Thus, $F(y)$ is $L_{y}$-smooth in $y$, where
$L_{y}=L_{x}+L_{z}+L_{xz}+L_{zx}\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1}).$
According to Corollary 3 in (Ghadimi, Lan, and Zhang 2016) and
$\lambda_{0}\sim\mathcal{O}(\epsilon)$, we can get the $\epsilon$\- stationary
point with the number of iterations
$T\sim\mathcal{O}(\lambda_{0}^{-k_{*}-1}\epsilon^{-2})$ and batch size
$n_{p}\sim\mathcal{O}(\lambda^{-2k_{*}}\epsilon^{-2}).$ Thus, the total
complexity is $\mathcal{O}(\epsilon^{-3k_{*}-5}).$

###  G.2 Smoothed CVaR

Similar to Cressie-Read family, we can show that $F_{s}(y)$ is
$L_{y}^{\prime}$-smooth in $y$, where
$L_{y}^{\prime}\sim\mathcal{O}(\lambda_{0}^{-3}).$ According to Corollary 3 in
(Ghadimi, Lan, and Zhang 2016), we can get the $\epsilon$\- stationary point
with the number of iterations
$T\sim\mathcal{O}(\lambda_{0}^{-3}\epsilon^{-2})$ and batch size
$n_{p}\sim\mathcal{O}(\lambda^{-2}\epsilon^{-2}).$ Thus, the total complexity
is $\mathcal{O}(\epsilon^{-9}).$