# Wasserstein distributionally robust optimization
and its tractable regularization formulations

Hong T. M. Chu111Department of Mathematics, National University of Singapore,
Singapore<EMAIL_ADDRESS>Meixia Lin222Engineering Systems and Design,
Singapore University of Technology and Design, Singapore,
<EMAIL_ADDRESS>444Corresponding author, Kim-Chuan Toh333Department of
Mathematics and Institute of Operations Research and Analytics, National
University of Singapore, Singapore<EMAIL_ADDRESS>
###### Abstract

We study a variety of Wasserstein distributionally robust optimization (WDRO)
problems where the distributions in the ambiguity set are chosen by
constraining their Wasserstein discrepancies to the empirical distribution.
Using the notion of weak Lipschitz property, we derive lower and upper bounds
of the corresponding worst-case loss quantity and propose sufficient
conditions under which this quantity coincides with its regularization scheme
counterpart. Our constructive methodology and elementary analysis also
directly characterize the closed-form of the approximate worst-case
distribution. Extensive applications show that our theoretical results are
applicable to various problems, including regression, classification and risk
measure problems.

AMS subject classification: 90C15, 90C17, 90C47

Keywords: Wasserstein discrepancy, Wasserstein distributionally robust
optimization, regularized optimization, worst-case loss quantity, data-driven
decision making.

##  1 Introduction

A central question of interest in many machine learning and operations
research applications is the selection of an appropriate decision variable
$\beta$ from a decision space $\mathcal{B}$. This often involves minimizing
the expected risk of prediction errors, that is,

$\inf_{\beta\in\mathcal{B}}\
\mathrm{E}_{\mathbb{P}_{\mathrm{true}}}[\ell(Z;\beta)],$

where $Z$ is a random variable in a given space $\mathcal{Z}$, with the
probability distribution $\mathbb{P}_{\mathrm{true}}$, and
$\ell\colon\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ is a loss
function. In practice, the ground-truth distribution
$\mathbb{P}_{\mathrm{true}}$ is usually unknown. Instead, one only has access
to an empirical distribution
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}$,
where $\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$
is a training dataset, $\\{\mu_{i}\\}_{i=1}^{N}$ are nonnegative weights
satisfying $\sum_{i=1}^{N}\mu_{i}=1$, and
${\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}$ is the point mass at $Z^{(i)}$. The
associated optimization problem

$\displaystyle\inf_{\beta\in\mathcal{B}}\left\\{\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]=\sum_{i=1}^{N}\mu_{i}\ell(Z^{(i)};\beta)\right\\}$
(1)

is often known as the empirical risk minimization (ERM) problem (Vapnik and
Chervonenkis 2015).

Robustness approach. One major criticism of the ERM problem is that the
empirical distribution $\mathbb{P}_{N}$ might differ from the ground-truth
distribution $\mathbb{P}_{\mathrm{true}}$ considerably, and $\mathcal{Z}_{N}$
might be unreliable due to errors in the data collection. This motivated the
study of the corresponding distributionally robust optimization problem.
Rather than relying on one single distribution $\mathbb{P}_{N}$, it hedges
against a set of distributions ${\mathfrak{M}}$ in the space of all
probabilities on $\mathcal{Z}$, denoted as $\mathcal{P}(\mathcal{Z})$.
Formally, the distributionally robust optimization (DRO) problem takes the
form of solving a minimax problem

$\inf_{\beta\in\mathcal{B}}\ \sup_{\mathbb{P}\in{\mathfrak{M}}}\
\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)].$

Here, the set ${\mathfrak{M}}\subset\mathcal{P}(\mathcal{Z})$ is referred to
as the ambiguity set or uncertainty set, which is often constructed by
imposing some statistical conditions on the set of probability distributions
under consideration. For example, the moment-based ambiguity set can be
defined via certain moment constraints as in Delage and Ye (2010), Goh and Sim
(2010), Wiesemann et al. (2014), or as the confidence region of a goodness-of-
fit hypothesis test (Bertsimas et al. 2018). Alternatively, the ambiguity set
can be constructed as
${\mathfrak{M}}=\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{D}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$,
where $\delta$ is a nonnegative tuning parameter, and
$\mathcal{D}(\cdot,\cdot)$ defines a certain discrepancy on
$\mathcal{P}(\mathcal{Z})$, such as the Prohorov and total variation metric
(Gibbs and Su 2002, Erdoğan and Iyengar 2006), Kullback-Leibler and $\chi^{2}$
divergence (Hu and Hong 2013, Jiang and Guan 2016), or Wasserstein metric
(Shafieezadeh-Abadeh et al. 2015, Mohajerin Esfahani and Kuhn 2018, Blanchet
and Murthy 2019, Gao 2022). These choices of ${\mathfrak{M}}$ are often named
as discrepancy-based ambiguity sets.

In this work, we focus on the ambiguity set based on the Wasserstein
discrepancy. Given two probability distributions
$\mathbb{P},\mathbb{Q}\in\mathcal{P}(\mathcal{Z})$ and an extended
nonnegative-valued function
$d\colon\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$, the Wasserstein
discrepancy111In this work, we use the term “Wasserstein discrepancy” instead
of the commonly-used “Wasserstein metric” in the literature, since
$d(\cdot,\cdot)$ here is not required to be a metric. with respect to
$d(\cdot,\cdot)$ and an exponent $r\in[1,\infty)$ is defined via the optimal
transport problem (Villani 2009, Peyré and Cuturi 2017) as

$\displaystyle\mathcal{W}_{d,r}(\mathbb{P},\mathbb{Q})\coloneqq\left(\inf_{\pi\in\Pi(\mathbb{P},\mathbb{Q})}\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(z^{\prime},z)\mathrm{d}\pi(z^{\prime},z)\right)^{\frac{1}{r}},$
(2)

where $\Pi(\mathbb{P},\mathbb{Q})$ (Villani 2009, Definition 1.1) denotes the
set of all joint probability distributions between $\mathbb{P}$ and
$\mathbb{Q}$, that is, by letting $\sigma(\mathcal{Z})$ denote the set of all
measurable sets in $\mathcal{Z}$,

$\Pi(\mathbb{P},\mathbb{Q})=\left\\{\begin{matrix}\pi\in\mathcal{P}(\mathcal{Z}\times\mathcal{Z})\,\text{such
that}\,\forall\,A,B\in\sigma(\mathcal{Z})\\\
\pi(A\times\mathcal{Z})=\mathbb{P}(A),\pi(\mathcal{Z}\times
B)=\mathbb{Q}(B)\end{matrix}\right\\}.$

Intuitively, the Wasserstein discrepancy (2) can be understood as finding the
minimum cost to move the mass of $\mathbb{P}$ to that of $\mathbb{Q}$.
Accordingly, the Wasserstein distributionally robust optimization (WDRO)
problem considers the ambiguity set
${\mathfrak{M}}=\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$,
where $\delta$ is a nonnegative scalar. Formally, the WDRO problem takes the
form as

$\displaystyle\inf_{\beta\in\mathcal{B}}\
\sup_{\mathbb{P}:\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\
\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)].$ (3)

Regularization approach. Another criticism of the ERM problem is that the
resulting estimator $\hat{\beta}$ might exhibit unsatisfactory out-of-sample
performance or overfitting phenomena (Plan and Vershynin 2012, Feng et al.
2014). To overcome this deficiency, a common approach is to modify the
objective function in the ERM problem (1) by adding a regularization term.
Specifically, the regularization scheme takes the form as

$\inf_{\beta\in\mathcal{B}}\
\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+\delta\varpi(\beta),$

where $\delta$ is a nonnegative tuning parameter,
$\varpi:\mathcal{B}\rightarrow(-\infty,+\infty]$ is a regularization function.
When $\mathcal{B}\subset\mathbb{R}^{n}$, there are some popular options for
$\varpi(\cdot)$, such as the ridge penalty $\|\cdot\|^{2}_{2}$ (Horel 1962,
Hoerl and Kennard 1970), the Lasso penalty $\|\cdot\|_{1}$ or its variant
combining with a group or a fused penalty (Belloni et al. 2011, Bunea et al.
2013, Stucky and Van De Geer 2017, Jiang et al. 2021). In addition, it is also
a topic of interest to study the appropriate value for the tuning parameter
$\delta$. In certain scenarios such as the Lasso and group Lasso problems
(Bickel et al. 2009, Lounici et al. 2011), it has been shown that appropriate
values of $\delta$ depend on the noise level of the dataset. In response,
several works have shown that the optimal $\delta$ can be made independent of
the noise level if the original expectation term
$\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]$ is replaced by
$\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{2}}$ when
$\ell(\cdot)$ is the squared loss function (Belloni et al. 2011, Bunea et al.
2013, Stucky and Van De Geer 2017).

Equivalence interpretation. In both the robustness and regularization
approaches, one of the key ingredients is the tuning parameter $\delta$, which
essentially controls how conservative the new scheme is compared to the
original ERM problem. While the regularization scheme is more tractable and
preferable in terms of computational consideration, the WDRO scheme (3) is
more favorable in accommodating the geometric structure of the data space via
the cost function $d(\cdot,\cdot)$ and the intuitive understanding of the
level of robustness via the radius $\delta$. In order to draw the connections
and take into account the advantages of both of them, the equivalence between
the WDRO problem and the regularization scheme has received increasing
attention over the last few years. Specifically, let

$\displaystyle\mathcal{S}\coloneqq\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)],$
(4)

then it aims to study sufficient conditions under which the following
equivalence holds:

$\displaystyle\mathcal{S}=\left[\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+{\boldsymbol{L}}(\beta)\delta\right]^{r},$
(5)

where $r\in[1,\infty)$, and ${\boldsymbol{L}}(\beta)$ acts as a penalty on
$\beta$ which might also depend on other factors such as $\mathbb{P}_{N}$ and
$d(\cdot,\cdot)$. In particular, the equivalence (5) gives a probabilistic
explanation of the penalty parameter in the regularization model based on the
WDRO interpretation. Compared to (4) which involves a minimax problem, solving
problem (5) appears to be more tractable and computationally favorable in
certain circumstances, thanks to the efficient algorithms studied in Li et al.
(2018a, b), Luo et al. (2019), Zhang et al. (2020), Tang et al. (2020), Chu et
al. (2022).

There are typically two main streams of works to tackle (5) in the literature.
First, the worst-case loss quantity $\mathcal{S}$ defined in (4) can be viewed
as an optimization problem with a single inequality constraint, thus its dual
counterpart can be inspected as a univariate optimization problem. In
addition, the complications in verifying the interchangeability condition for
$\sup$ and $\inf$ also suggest that it might be beneficial to replace (2) with
its dual problem. Consequently, to guarantee the equality (5) instead of just
the inequality derived from weak duality, many existing works impose
relatively strong assumptions on the underlying problem in order to prove/use
the strong duality and/or guarantee the existence of the dual optimal
variables (Mohajerin Esfahani and Kuhn 2018, Blanchet and Murthy 2019,
Blanchet et al. 2019, Chu et al. 2022, Zhang et al. 2022, Gao and Kleywegt
2023, Zhen et al. 2023). Second, when $r=1$, (5) can be rewritten as
${\boldsymbol{L}}(\beta)\delta=\sup\left\\{\mathrm{E}_{(Z^{\prime},Z)\sim\pi}[\ell(Z^{\prime};\beta)-\ell(Z;\beta)]\mid\pi\in\Pi(\mathbb{P},\mathbb{P}_{N})\mbox{
with
}\mathbb{P}\in\mathcal{P}(\mathcal{Z}),\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$.
This observation suggests that ${\boldsymbol{L}}(\beta)$ is related to certain
Lipschitz-type properties of the loss function $\ell(\cdot,\beta)$
(Shafieezadeh-Abadeh et al. 2015, 2019, An and Gao 2021, Gao 2022). However,
the usual Lipschitz condition is not enough to guarantee (5) since the
Lipschitz constant can always be chosen arbitrarily large. Thus, one often
needs some other conditions such as the tightness at certain points
(Shafieezadeh-Abadeh et al. 2019, Gao 2022), the convexity of $\ell$ (Wu et
al. 2022) or the differentibility of $\ell$ almost-everywhere with
nonexpansive gradients (An and Gao 2021).

In this paper, we study sufficient conditions to establish the equivalence
between the worst-case loss quantity in the WDRO problem and its associated
regularization scheme. Our proposed sufficient conditions generalize the
existing results from various perspectives, particularly by relaxing the
required assumptions on the loss function and cost function. Moreover, our
constructive approaches and elementary proofs directly characterize the closed
forms of the approximate worst-case distributions. The generality of our
theoretical results are demonstrated through their applications to various
problems, including regression, classification and risk measure problems.

The remaining part of this paper is organized as follows. In Section 2, we
summarize our main contributions and compare them with the existing results in
the literature. We derive our main theoretical results in Section 3 and
present their applications in Section 4 and Section 5. The conclusion is given
in Section 6.

Notations. Throughout this paper, $(\mathcal{Z},\mathcal{A})$ or $\mathcal{Z}$
denotes a measurable space, where $\mathcal{A}$ is a given $\sigma$-algebra on
$\mathcal{Z}$ such that $\\{z\\}\in\mathcal{A}$ for any $z\in\mathcal{Z}$
(Cohn 2013, Section 1.2). In particular, when
$\mathcal{Z}\in\mathfrak{B}(\mathbb{R}^{n})$, where
$\mathfrak{B}(\mathbb{R}^{n})$ is the Borel $\sigma$-algebra on
$\mathbb{R}^{n}$, then $\mathcal{A}$ is always understood as
$\mathcal{A}\coloneqq\left\\{A\mid
A\subset\mathcal{Z},A\in\mathfrak{B}(\mathbb{R}^{n})\right\\}$. A set
$A\subset\mathcal{Z}$ is called measurable if $A\in\mathcal{A}$; a function
$f\colon\mathcal{Z}\rightarrow[-\infty,\infty]$ is called measurable if
$\\{z\in\mathcal{Z}\mid f(z)\leq t\\}\in\mathcal{A}$ for any $t\in\mathbb{R}$
(Cohn 2013, Proposition 2.1.1); and $\mathcal{Z}\times\mathcal{Z}$ denotes the
Cartesian product measurable space with $\sigma$-algebra
$\mathcal{A}\times\mathcal{A}$ (Cohn 2013, Section 5.1).

In this work, the function
$\ell\colon\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ is assumed that
$\ell(\cdot,\beta)\colon\mathcal{Z}\rightarrow\mathbb{R}$ is measurable for
any $\beta\in\mathcal{B}$. A function
$\mathbb{P}\colon\mathcal{A}\rightarrow[0,\infty]$ is a probability if it is
countably additive, $\mathbb{P}(\emptyset)=0$ and $\mathbb{P}(\mathcal{Z})=1$;
the space of all probabilities on $\mathcal{Z}$ is denoted by
$\mathcal{P}(\mathcal{Z})$; and the expectation of a measurable function $f$
of a real-valued random variable $Z$ on $(\mathcal{Z},\mathcal{A},\mathbb{P})$
is denoted by
$\mathrm{E}_{\mathbb{P}}[f(Z)]=\int_{\mathcal{Z}}f(z)\mathrm{d}\mathbb{P}(z)$
(Cohn 2013, Section 10.1).

Define the indicator function
${\boldsymbol{\delta}}_{S}\colon\mathcal{Z}\rightarrow\mathbb{R}$ of a set
$S\subset\mathcal{Z}$ as ${\boldsymbol{\delta}}_{S}(z)=0$ if $z\in S$, and
$\infty$ otherwise. Define the point mass function (Dirac measure)
${\boldsymbol{\chi}}_{\\{\hat{z}\\}}\in\mathcal{P}(\mathcal{Z})$ at point
$\hat{z}\in\mathcal{Z}$ as ${\boldsymbol{\chi}}_{\\{\hat{z}\\}}(A)=1$ if
$\hat{z}\in A$, and $0$ otherwise, for any measurable set
$A\subset\mathcal{Z}$. Given two functions
$f\colon\mathcal{X}\rightarrow\mathbb{R}$ and
$g\colon\mathcal{Y}\rightarrow\mathbb{R}$, we define the function $f\otimes
g\colon\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ as $(x,y)\rightarrow
f(x)\cdot g(y)$ for any $(x,y)\in\mathcal{X}\times\mathcal{Y}$. We adopt the
convention of extended arithmetic such that $0\cdot\infty=0$. Denote the inner
product on $\mathbb{R}^{n}$ by $\langle x,y\rangle=\sum_{i=1}^{n}x_{i}y_{i}$
for any $x,y\in\mathbb{R}^{n}$. Let $\|\cdot\|_{\mathbb{R}^{n}}$ be an
arbitrary norm on $\mathbb{R}^{n}$ and $\|\cdot\|_{{\mathbb{R}^{n}},*}$ be its
dual norm defined as
$\|x\|_{\mathbb{R}^{n},*}\coloneqq\max_{y\in\mathbb{R}^{n}}\left\\{\langle
x,y\rangle\mid\|y\|_{\mathbb{R}^{n}}=1\right\\}$. Given matrices
$A\in\mathbb{R}^{n_{1}\times n_{2}},B\in\mathbb{R}^{n_{1}\times
n_{3}},C\in\mathbb{R}^{n_{3}\times n_{2}}$, we denote the horizontal
concatenation of $A$ and $B$ by
$[A,B]\in\mathbb{R}^{n_{1}\times(n_{2}+n_{3})}$, and the vertical
concatenation of $A$ and $C$ by $[A;C]\in\mathbb{R}^{(n_{1}+n_{3})\times
n_{2}}$. Let $\mathbb{R}_{+}\coloneqq[0,\infty)$. For any real number $t$, the
sign function is defined as ${\rm sgn}(t)=-1$ if $t<0$, and ${\rm sgn}(t)=1$
otherwise.

##  2 Main contributions

In this section, we shall summarize our main contributions and compare them
with the existing results in the literature. We first state some notations
which will be used. Let
$\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$ be a
given dataset and
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z})$
be the corresponding empirical distribution. In addition, let $r\in[1,\infty)$
be a scalar and $d\colon\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$ be
a measurable function on $\mathcal{Z}\times\mathcal{Z}$. Suppose the loss
function $\ell:\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ takes the
form as

$\ell\colon(z;\beta)\mapsto\psi_{\beta}^{r}(z),\text{ with
}\begin{cases}\psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}\ \ \text{ if
}r=1,\\\ \psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}_{+}\text{ if
}r>1.\end{cases}$

For notational simplicity, let $\mathcal{I}$ and $\mathcal{U}$ (depending on
some scalar $L_{\beta}^{\mathcal{Z}_{N}}$, which will be discussed in detail
later in Section 3) be defined as:

$\begin{array}[]{ll}\mathcal{I}&\coloneqq\inf\limits_{\rho\geq
0}\left\\{\rho\delta^{r}+\mathrm{E}_{\mathbb{P}_{N}}\left[\sup\limits_{z^{\prime}\in\mathcal{Z}}\left\\{\ell(z^{\prime};\beta)-\rho
d^{r}(z^{\prime},Z)\right\\}\right]\right\\},\\\
\mathcal{U}&\coloneqq\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta\right)^{r}.\end{array}$

In particular,
$\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}$ is
well-defined as $\psi_{\beta}$ is assumed to be nonnegative when $r>1$. It can
be seen that $\mathcal{S}$ defined in (4) satisfies
$\mathcal{S}\leq\mathcal{I}$, whose proof can be found in Appendix A.1. Since
$\mathcal{S}$ is a supremum quantity over a feasible set, there exists a
sequence of feasible distributions $\\{\mathbb{P}_{k}\\}_{k=1}^{\infty}$ whose
expectations $\\{\mathrm{E}_{\mathbb{P}_{k}}[\ell(Z;\beta)]\\}_{k=1}^{\infty}$
converge to $\mathcal{S}$ as $k\rightarrow\infty$. More precisely, for any
$\epsilon>0$, we are interested in characterizing
$\tilde{\mathbb{P}}_{\epsilon}\in\mathcal{P}(\mathcal{Z})$ which satisfies
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}}_{\epsilon},\mathbb{P}_{N})\leq\delta$
and
$\mathcal{S}-\mathrm{E}_{\tilde{\mathbb{P}}_{\epsilon}}[\ell(Z;\beta)]\leq\epsilon$.
In particular, when $\mathcal{S}$ is attainable, one might even characterize
$\tilde{\mathbb{P}}_{0}$ satisfying
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}}_{0},\mathbb{P}_{N})\leq\delta$ and
$\mathcal{S}=\mathrm{E}_{\tilde{\mathbb{P}}_{0}}[\ell(Z;\beta)]$. Note that,
in general, it is not guaranteed that $\tilde{\mathbb{P}}_{0}$ exists, see for
example in Mohajerin Esfahani and Kuhn (2018, Example 2). In this work, we
call $\tilde{\mathbb{P}}_{\epsilon}$ as an approximate worst-case distribution
(Gao and Kleywegt 2023).

Table 1: (Informal) comparison of our results with the existing results. Assumptions | Conclusions | References
---|---|---
$d(\cdot,\cdot)$ | $\psi_{\beta}$ | $r$ | Others | $\mathcal{S},\mathcal{U},\mathcal{I}$ | $\tilde{\mathbb{P}}_{\epsilon},\tilde{\mathbb{P}}_{0}$
norm | max-of-concave | 1 | convex $\mathcal{Z}\subset\mathbb{R}^{n}$ | $\mathcal{S}=\mathcal{I}$ | $\tilde{\mathbb{P}}_{\epsilon}$ | Mohajerin Esfahani and Kuhn (2018, Thm 4.2, 4.4)
extended norm | absolute/logistic | 2 or 1 | $\mathcal{Z}=\mathbb{R}^{n}$ | $\mathcal{S}=\mathcal{U}$ | $\tilde{\mathbb{P}}_{0}{}^{(\natural)}$ | Blanchet et al. (2019, Thm 1,2)
extended semi-norm | absolute | 2 | $\mathcal{Z}=\mathbb{R}^{n}$ | $\mathcal{S}=\mathcal{U}$ | $\tilde{\mathbb{P}}_{0}{}^{(\natural)}$ | Chu et al. (2022, Thm 4)
metric | globally Lipschitz | 1 |  tightness at infinity(⨝) | $\mathcal{S}=\mathcal{U}$ | $\tilde{\mathbb{P}}_{\epsilon}$ | Gao et al. (2022, Col 2)
lower semicontinuous |  upper semicontinuous | $[1,\infty)$ |  $d(\cdot,\cdot)$ positive definite(♢) | $\mathcal{S}=\mathcal{I}$ | $\tilde{\mathbb{P}}_{0}$ | Blanchet and Murthy (2019, Thm 1)
cost function |  interchangeability principle | $[1,\infty)$ |  $d(\cdot,\cdot)$ positive definite(♢) | $\mathcal{S}=\mathcal{I}$ |  –(♭) | Zhang et al. (2022, Thm 1)
cost function(♯) | measurable | $[1,\infty)$ |  $(\mathcal{Z},d)$ locally compact(♯) | $\mathcal{S}=\mathcal{I}$ | $\tilde{\mathbb{P}}_{0}$ | Gao and Kleywegt (2023, Thm 1, Col 1)
cost function(†) | smooth | $[1,\infty)$ | $\mathcal{Z}=\mathbb{R}^{n}$ | $\mathcal{S}=\mathcal{U}$ |  –(♭) | (Shafieezadeh-Abadeh et al. 2023, Thm 3.2)
extended norm |  convex, piecewise linear | $[1,\infty)$ | $\mathcal{Z}=\mathbb{R}^{n}$ | $\mathcal{S}=\mathcal{U}$ | $\tilde{\mathbb{P}}_{\epsilon}{}^{(\natural)}$ | Wu et al. (2022, Thm 5,6,7)
cost function |  $(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz | $[1,\infty)$ |  tightness conditionally(⊛) | $\mathcal{S}=\mathcal{U}$ | $\tilde{\mathbb{P}}_{\epsilon}{}^{(\natural)}$ | this work
(♯) As commented in Blanchet and Murthy (2019, Section 1), the proof given in
Gao and Kleywegt (2023, Lemma 2) implicitly assumes that $(\mathcal{Z},d)$ is
locally compact. We also notice from Gao and Kleywegt (2023, Remark 2, Remark
5) that Gao and Kleywegt (2023, Lemma 2, Corollary 2) requires
$d(\cdot,\cdot)$ to be a metric. (♮) The analytical formula of
$\tilde{\mathbb{P}}_{\epsilon}$ (or $\tilde{\mathbb{P}}_{0}$) is not given
explicitly in the result, but can be constructed directly from the proof. (♭)
The analytical formula of $\tilde{\mathbb{P}}_{\epsilon}$ (or
$\tilde{\mathbb{P}}_{0}$) is not a trivial implication from the corresponding
result, as far as we understand. (♢) Positive definiteness/point-separating:
$d(z^{\prime},z)=0$ if and only if $z^{\prime}=z$. (†) $d$ is required to be
lower bounded by a metric with compact sublevel set (Assumption 2.1(ii)),
hence it must be positive definite. (⨝) See the discussion after Remark 3.1.
(⊛) See Theorem 3.2 and Theorem 3.3.

In recent years, it has been an emerging topic to study the relationships
among $\mathcal{S}$, $\mathcal{I}$ and $\mathcal{U}$. Table 1 shows an
informal comparison of our results with the existing results in the
literature; for detailed discussions, see Section 3. We should note that while
$\mathcal{U}$ is a computationally tractable quantity, $\mathcal{I}$ is less
computationally friendly as its evaluation involves solving a one-dimensional
minimization problem with a complicated objective function. Thus the
equivalence $\mathcal{S}=\mathcal{U}$ is much more desirable than the
equivalence $\mathcal{S}=\mathcal{I}$. Correspondingly, the conditions needed
for the equivalence $\mathcal{S}=\mathcal{U}$ to hold are also stronger.

We summarize our main contributions in this paper as follows.

  * •

We first propose a lower bound $\mathcal{L}$ for $\mathcal{S}$ (see Theorem
3.1(a)). Then, we characterize a certain property named as the weak
$(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz property and prove that under this
condition, we have $\mathcal{S}\leq\mathcal{U}$ (see Theorem 3.1(b)). The
bounds $\mathcal{L}$ and $\mathcal{U}$ are demonstrated to exhibit some
characteristics that are consistent with the existing literature (see the
discussions after Theorem 3.1).

  * •

We propose sufficient conditions for $\mathcal{S}=\mathcal{U}$ in the cases
where $r=1$ (see Theorem 3.2) and $r>1$ (see Theorem 3.3). Our result is a
generalization of many existing results in the literature, which is discussed
in detail in Section 3. It is worth noting that our proofs do not involve
verifying the validity of interchangeability of $\inf$ and $\sup$. In
particular, we do not use the strong duality result and/or the existence of
primal-dual optimizer of the Wasserstein problem $\mathcal{W}_{d,r}$, which
relaxes the assumptions needed for $d(\cdot,\cdot)$. As a byproduct, our
constructive approach directly characterizes the analytic formulation of
$\tilde{\mathbb{P}}_{\epsilon}$.

  * •

Although studying sufficient conditions for $\mathcal{S}=\mathcal{U}$ is a
widely explored topic, we state certain scenarios in which the existing
results do not apply. But our results still can cover theses circumstances
under suitable conditions, for instance, even when the globally Lipschitz
condition fails (see Example 3.1); $\ell$ is not convex (see Example 3.2 and
Example 4.6); $d(\cdot,\cdot)$ is not a metric, not positive definite, not
convex (see Example 4.4); and $(\mathcal{Z},d)$ is not a locally compact
metric space (see Example 4.2).

  * •

We demonstrate the versatility of our theoretical results by applying them to
various applications, including regression, classification and risk measure
problems (see Section 4 and Section 5). Table LABEL:table:supper-long-table
shows an informal summary of some applications.

[caption = (Informal) summary of our applications., label = table:supper-long-
table, ] colspec = —l—l—l—, Application Formulation Remark
Regression loss functions
Higher-order regression
$\mathrm{E}_{\mathbb{P}}[\left|Y-\langle\beta,X\rangle\right|^{r}]$, $r\geq 1$
(1) $(X,Y,\beta)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))$ takes one of $\boldsymbol{\cdot}$
$\|[x^{\prime}-x;y^{\prime}-y]\|_{\mathbb{R}^{n+1}}$ $\boldsymbol{\cdot}$
$\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
$\boldsymbol{\cdot}$ ${\boldsymbol{\delta}}_{\\{{\bf
0}_{\mathbb{R}^{|\mathcal{I}^{c}|+1}}\\}}([x^{\prime}_{\mathcal{I}^{c}}-x_{\mathcal{I}^{c}};y^{\prime}-y])$
$+\|x^{\prime}_{\mathcal{I}}-x_{\mathcal{I}}\|_{\mathbb{R}^{|\mathcal{I}|}}$,
where $\mathcal{I}\subset\\{1,2,\hfil\dots,n\\}$ $\boldsymbol{\cdot}$
$\inf_{\bar{x}\in\mathbb{R}^{s}}\left\\{\|\bar{x}\|_{\mathbb{R}^{s}}\mid
B^{T}\bar{x}=x^{\prime}-x\right\\}$
$+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$, where
$B\in\mathbb{R}^{s\times n}$
Lower partial moments
$\mathrm{E}_{\mathbb{P}}[(Y-\langle\beta,X\rangle-\tau)_{+}^{r}]$, $r\geq 1$,
$\tau\in\mathbb{R}$
Higher-order $\tau$-insensitive regression
$\mathrm{E}_{\mathbb{P}}[(\left|Y-\langle\beta,X\rangle\right|-\tau)_{+}^{r}]$,
$r\geq 1$, $\tau\in\mathbb{R}$
Nonparametric scalar-on-function linear regression
$\mathrm{E}_{\mathbb{P}}\left[h^{r}(Y-\int\limits_{0}^{1}\left(X(t)\beta(t))\mathrm{d}t\right)\right]$,
$\beta\in\mathfrak{L}^{2}[0,1]$, $r\geq 1$ (1)
$(X,Y)\in\mathfrak{L}^{2}[0,1]\times\mathbb{R}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))={\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
$+\left(\int_{0}^{1}\left|x^{\prime}(t)-x(t)\right|^{2}\mathrm{d}t\right)^{1/2}$
(3) For $s\in\mathbb{R}$ ,$h(s)$ takes one of $\left|s\right|$, $(s-\tau)_{+}$
or $(\left|s\right|-\tau)_{+}$, $\tau\in\mathbb{R}$
Parametric scalar-on-function linear regression
$\mathrm{E}_{\mathbb{P}}\left[h^{r}(Y-\int\limits_{0}^{1}(X(t)\sum\limits_{j=1}^{n}\beta_{j}{\boldsymbol{g}}_{j}(t))\mathrm{d}t)\right]$,
$\beta\in\mathbb{R}^{n}$,
$\\{{\boldsymbol{g}}_{j}\\}_{j=1}^{n}\subset\mathfrak{L}^{2}[0,1]$, $r\geq 1$
Log-cosh loss regression
$\mathrm{E}_{\mathbb{P}}[\log(\cosh(Y-\langle\beta,X\rangle))]$ (1)
$(X,Y,\beta)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))$ takes one of $\boldsymbol{\cdot}$
$\|[x^{\prime}-x;y^{\prime}-y]\|_{\mathbb{R}^{n+1}}$ $\boldsymbol{\cdot}$
$\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
Huber loss regression $\mathrm{E}_{\mathbb{P}}[h(Y-\langle\beta,X\rangle)]$
where $h(t)=\begin{cases}t^{2}/2&\text{if }\left|t\right|\leq 1,\\\
\left|t\right|-\frac{1}{2}&\text{otherwise}\end{cases}$

Quantile loss regression $\mathrm{E}_{\mathbb{P}}[h(Y-\langle\beta,X\rangle)]$
where $h(t)=\begin{cases}\gamma t&\text{if }t\geq 0,\\\
-t&\text{otherwise},\end{cases}$ $\gamma\in(0,1)$

Ridge linear ordinary regression
$\mathrm{E}_{\mathbb{P}}[(Y+\langle\beta,X\rangle)^{2}]$ (1)
$(X,Y,\beta)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}$, $Z=(X,Y)$
(2) $d(z^{\prime},z)=\|z^{\prime}-z\|_{2}\|z^{\prime}+z\|_{2}$
Hard sigmoid /HardTanh
$\mathrm{E}_{\mathbb{P}}\left[\max\left\\{0,\min\left\\{1,\frac{\langle\beta,Z\rangle+1}{2}\right\\}\right\\}\right]$
(1) $(Z,\beta)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ (2)
$d(z^{\prime},z)=\|z^{\prime}-z\|_{\mathbb{R}^{n}}$ (3) Equivalence holds
conditionally
Classification loss functions
Higher-order hinge loss binary classification
$\mathrm{E}_{\mathbb{P}}[\left(1-Y\cdot\langle\beta,X\rangle\right)_{+}^{r}]$,
$r\geq 1$ (1)
$(X,Y,\beta)\in\mathbb{R}^{n}\times\\{-1,1\\}\times\mathbb{R}^{n}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}$
$+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
Higher-order support vector machine classification
$\mathrm{E}_{\mathbb{P}}[\left|1-Y\cdot\langle\beta,X\rangle\right|^{r}]$,
$r\geq 1$
Log-exponential loss
$\mathrm{E}_{\mathbb{P}}[\log(1+\exp(-Y\cdot\langle\beta,X\rangle))]$
Smooth hinge loss  $\mathrm{E}_{\mathbb{P}}[h(Y\cdot\langle\beta,X\rangle)]$
with $h(t)=\left\\{\begin{array}[]{ll}0&\text{if }t\geq 1,\\\
(1-t)^{2}/2&\text{if }0<t<1,\\\ 1/2-t&\text{otherwise}\end{array}\right.$
Truncated pinball loss
$\mathrm{E}_{\mathbb{P}}[h(Y\cdot\langle\beta,X\rangle)]$ with
$h(t)=\begin{cases}1-t&\text{if }t\leq 1,\\\ \tau_{1}(t-1)&\text{if
}1<t<\tau_{2}+1,\\\ \tau_{1}\tau_{2}&\text{otherwise},\end{cases}$
$\tau_{1}\in[0,1],\tau_{2}\geq 0$
Binary cross-entropy loss $\mathrm{E}_{\mathbb{P}}[\beta Z\log(\beta
Z)+(1-\beta Z)\log(1-\beta Z)]$ (1) $(Z,\beta)\in(0,1)\times(0,1)$ (2)
$d(z^{\prime},z)=\left|z^{\prime}-z\right|$ (3) Equivalence holds
conditionally
Generalization to risk measure
$\nu$-support vector regression
$\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(\left|Y-\langle\beta,X\rangle\right|)$
(1) $(X,Y,\beta)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))$
$=\|(x^{\prime},y^{\prime})-(x,y)\|_{\mathbb{R}^{n+1}}$ (3) $\alpha\in(0,1)$
$\nu$-support vector machine
$\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(-Y\cdot\langle\beta,X\rangle)$ (1)
$(X,Y,\beta)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}$ (2)
$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}$
$+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$ (3) $\alpha\in(0,1)$
Higher moment coherent risk measures
$\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\left(\mathrm{E}_{\mathbb{P}}[\left(\langle\beta,Z\rangle-t\right)_{+}^{r}]\right)^{\frac{1}{r}}\Big{\\}}$
$r\geq 1$ (1) $(Z,\beta)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ (2)
$d(z^{\prime},z)=\|z^{\prime}-z\|_{\mathbb{R}^{n}}$ (3) $\alpha\in(0,1)$

##  3 Theoretical analysis of the equivalence

In this section, we will establish our main results for deriving the
equivalence between the worst-case loss quantity in the WDRO problem and its
regularization scheme counterpart. We first give the following lemma, with the
proof in Appendix A.2, to quantify the Wasserstein discrepancy between any
distribution and a singleton, which will be used in the subsequent analysis.

######  Lemma 3.1.

Given any distribution $\mathbb{P}\in\mathcal{P}(\mathcal{Z})$ and any point
$\hat{z}\in\mathcal{Z}$, for any scalar $r\geq 1$ and any extended
nonnegative-valued measurable function
$d\colon\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$, we have

$\mathcal{W}_{d,r}(\mathbb{P},{\boldsymbol{\chi}}_{\\{\hat{z}\\}})=\left(\int_{\mathcal{Z}}d^{r}(z,\hat{z})\mathrm{d}\mathbb{P}(z)\right)^{\frac{1}{r}}.$

Before stating our main results, we need the following definition of the cost
function.

######  Definition 3.1.

The function $d(\cdot,\cdot)$ defined on $\mathcal{Z}\times\mathcal{Z}$ is
called a cost function if it is extended nonnegative-valued, measurable, and
vanishes whenever two arguments are the same, that is, for any
$z^{\prime},z\in\mathcal{Z}$, $d(z^{\prime},z)\in[0,\infty]$ and $d(z,z)=0$.

Next, we introduce a weak Lipschitz property for functions on $\mathcal{Z}$
with respect to a given cost function $d(\cdot,\cdot)$, where the weak
Lipschitz constant depends on the second input of $d(\cdot,\cdot)$. Note that
it is different from the Lipschitz property used in Shafieezadeh-Abadeh et al.
(2015), An and Gao (2021), Gao (2022), as the latter does not depend on the
input variables.

######  Definition 3.2 (Weak Lipschitz property).

Given a function $f\colon\mathcal{Z}\rightarrow\mathbb{R}$, a cost function
$d(\cdot,\cdot)$ on $\mathcal{Z}\times\mathcal{Z}$ and a subset
$\mathcal{S}\subset\mathcal{Z}$, $f$ is called
$(L_{f}^{\mathcal{S}},d)$-Lipschitz at $\mathcal{S}$ if for any
$z\in\mathcal{S},z^{\prime}\in\mathcal{Z}$, one has

$\left|f(z^{\prime})-f(z)\right|\leq L_{f}^{\mathcal{S}}d(z^{\prime},z),$

where $L_{f}^{\mathcal{S}}\in[0,\infty)$ is a constant depending on $f$ and
$\mathcal{S}$.

The classical Lipschitz property can be seen as a special case of Definition
3.2 when $(\mathcal{Z},d)$ is a metric space and $\mathcal{S}=\mathcal{Z}$. In
other words, any Lipschitz function is weak Lipschitz, while the reverse is
not always true, for example, see Example 3.1.

###  3.1 Lower and Upper bounds of the worst-case loss quantity

We now derive a lower bound and an upper bound of the worst-case loss quantity
for a certain class of loss functions in the following theorem.

######  Theorem 3.1.

Let $\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$ be
a given dataset and
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z})$
be the corresponding empirical distribution. In addition, let $r\in[1,\infty)$
be a scalar and $d(\cdot,\cdot)$ be a cost function on
$\mathcal{Z}\times\mathcal{Z}$. Suppose the loss function
$\ell:\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ takes the form as

$\ell\colon(z;\beta)\mapsto\psi_{\beta}^{r}(z),\text{ with
}\begin{cases}\psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}\ \ \text{ if
}r=1,\\\ \psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}_{+}\text{ if
}r>1.\end{cases}$

Let $\mathcal{S}$ be defined as in (4). Then the following statements hold for
any $\delta\geq 0$.

  1. (a)

Let
$\mathcal{L}_{i}\coloneqq\sup_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\left\\{\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\middle|\mathcal{W}_{d,r}(\mathbb{P},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})\leq\delta\right\\}$
for $i=1,\dots,N$. Then

$\mathcal{S}\geq\mathcal{L}\coloneqq\sum_{i=1}^{N}\mu_{i}\mathcal{L}_{i}\geq\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)].$

  2. (b)

Suppose $\psi_{\beta}$ is $(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz at
$\mathcal{Z}_{N}$ with $L_{\beta}^{\mathcal{Z}_{N}}\in(0,\infty)$, then

$\mathcal{S}\leq\mathcal{U}=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta\right)^{r}.$

  3. (c)

Suppose $\psi_{\beta}$ is $(0,d)$-Lipschitz at $\mathcal{Z}_{N}$, then

$\mathcal{S}=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)].$

Proof. (a) For any collection
$\left\\{\tilde{\mathbb{P}}^{(i)}\right\\}_{i=1}^{N}\subseteq\mathcal{P}(\mathcal{Z})$
such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}}^{(i)},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})\leq\delta$
for all $i=1,\cdots,N$. It follows from Lemma 3.1 that for any $i=1,\cdots,N,$

$\mathcal{W}_{d,r}(\tilde{\mathbb{P}}^{(i)},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})=\left(\int_{\mathcal{Z}}d^{r}(z,Z^{(i)})\mathrm{d}\tilde{\mathbb{P}}^{(i)}(z)\right)^{\frac{1}{r}}\leq\delta.$

Hence we can construct

$\displaystyle\tilde{\mathbb{P}}\coloneqq\sum_{i=1}^{N}\mu_{i}\tilde{\mathbb{P}}^{(i)}\quad\text{and}\quad\tilde{\pi}\coloneqq\sum_{i=1}^{N}\left(\mu_{i}\tilde{\mathbb{P}}^{(i)}\otimes{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\right).$
(6)

Then we have
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z}),\tilde{\pi}\in\mathcal{P}(\mathcal{Z}\times\mathcal{Z})$,
and $\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$, since for any
measurable sets $A,B\subset\mathcal{Z}$,

$\begin{array}[]{llll}\tilde{\pi}(\mathcal{Z}\times
B)&=\sum_{i=1}^{N}\mu_{i}\tilde{\mathbb{P}}^{(i)}(\mathcal{Z}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)=\mathbb{P}_{N}(B),\\\
\tilde{\pi}(A\times\mathcal{Z})&=\sum_{i=1}^{N}\mu_{i}\tilde{\mathbb{P}}^{(i)}(A){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(\mathcal{Z})&=\sum_{i=1}^{N}\mu_{i}\tilde{\mathbb{P}}^{(i)}(A)=\tilde{\mathbb{P}}(A).\end{array}$

Therefore, we can see that

$\begin{array}[]{ll}\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})&\leq\left(\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}=\left(\sum_{i=1}^{N}\mu_{i}\int_{\mathcal{Z}}{d}^{r}(\tilde{z},Z^{(i)})\mathrm{d}\tilde{\mathbb{P}}^{(i)}(\tilde{z})\right)^{\frac{1}{r}}\\\
&=\left(\sum_{i=1}^{N}\mu_{i}\left(\mathcal{W}_{d,r}(\tilde{\mathbb{P}}^{(i)},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})\right)^{r}\right)^{\frac{1}{r}}\leq\delta.\end{array}$

Moreover, according to (6), we have

$\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]=\sum_{i=1}^{N}\mu_{i}\mathrm{E}_{\tilde{\mathbb{P}}^{(i)}}[\ell(Z;\beta)].$

By taking supremum on all possible
$\left\\{\tilde{\mathbb{P}}^{(i)}\right\\}_{i=1}^{N}$ such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}}^{(i)},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})\leq\delta$
for all $i=1,\cdots,N$, we have

$\begin{array}[]{ll}\mathcal{S}=\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\geq\sum\limits_{i=1}^{N}\mu_{i}\sup\limits_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\left\\{\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\middle|\mathcal{W}_{d,r}\left(\mathbb{P},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\right)\leq\delta\right\\}=\sum_{i=1}^{N}\mu_{i}\mathcal{L}_{i}=\mathcal{L}.\end{array}$

Besides, since
$\mathcal{W}_{d,r}({\boldsymbol{\chi}}_{\\{Z^{(i)}\\}},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}})=0\leq\delta$
by Lemma 3.1, we have that

$\begin{array}[]{ll}\mathcal{L}_{i}=\sup\limits_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\left\\{\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\middle|\mathcal{W}_{d,r}\left(\mathbb{P},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\right)\leq\delta\right\\}\geq\mathrm{E}_{{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}}[\ell(Z;\beta)]=\ell(Z^{(i)};\beta),\end{array}$

and hence
$\mathcal{L}=\sum_{i=1}^{N}\mu_{i}\mathcal{L}_{i}\geq\sum_{i=1}^{N}\mu_{i}\ell(Z^{(i)};\beta)=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]$.

(b) Let $\epsilon>0$ be an arbitrary scalar. Fix any
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})\leq\delta$. By the
definition of $\mathcal{W}_{d,r}(\cdot,\cdot)$, there exists
$\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$ such that

$\left(\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\leq\delta+\frac{\epsilon}{L_{\beta}^{\mathcal{Z}_{N}}}.$

Besides, by the definition of the loss function $\ell(\cdot,\cdot)$, we have

$\begin{array}[]{ll}\left(\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}&=\left(\int_{\mathcal{Z}}\psi_{\beta}^{r}(\tilde{z})\mathrm{d}\tilde{\mathbb{P}}(\tilde{z})\right)^{\frac{1}{r}}=\left(\int_{\mathcal{Z}\times\mathcal{Z}}\psi_{\beta}^{r}(\tilde{z})\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\\\
&=\left(\int_{\mathcal{Z}\times\mathcal{Z}}\left(\psi_{\beta}(z)+\psi_{\beta}(\tilde{z})-\psi_{\beta}(z)\right)^{r}\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\\\
&\leq^{(*)}\left(\int_{\mathcal{Z}\times\mathcal{Z}}\psi_{\beta}^{r}(z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}+\left(\int_{\mathcal{Z}\times\mathcal{Z}}\left|\psi_{\beta}(\tilde{z})-\psi_{\beta}(z)\right|^{r}\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\\\
&=\left(\int_{\mathcal{Z}}\psi_{\beta}^{r}(z)\mathrm{d}\mathbb{P}_{N}(z)\right)^{\frac{1}{r}}+\left(\int_{\mathcal{Z}\times\mathcal{Z}}\left|\psi_{\beta}(\tilde{z})-\psi_{\beta}(z)\right|^{r}\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\\\
&=\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+\left(\int_{\mathcal{Z}\times\mathcal{Z}}\left|\psi_{\beta}(\tilde{z})-\psi_{\beta}(z)\right|^{r}\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}},\end{array}$

where the inequality (∗) holds naturally if $r=1$, and follows from the
Minkowski inequality if $r>1$. Since $\psi_{\beta}$ is
$(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz at $\mathcal{Z}_{N}$, it holds
that

$\begin{array}[]{ll}\left(\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}\leq\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\left(\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}\leq\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta+\epsilon.\end{array}$

This means that for any $\epsilon>0$, we have

$\begin{array}[]{ll}\mathcal{S}^{\frac{1}{r}}=\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\left(\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}\leq\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta+\epsilon.\end{array}$

By letting $\epsilon\rightarrow 0$, we get the desired inequality.

(c) Since $\psi_{\beta}$ is $(0,d)$-Lipschitz at $\mathcal{Z}_{N}$, by the
convention that $0\cdot\infty=0$, one has
$\psi_{\beta}(z^{\prime})=\psi_{\beta}(z)$ for any
$z^{\prime}\in\mathcal{Z},z\in\mathcal{Z}_{N}$. In particular,
$\psi_{\beta}(\bar{z})=\psi_{\beta}(z)$ for any $\bar{z},z\in\mathcal{Z}_{N}$.
Therefore, $\psi_{\beta}(\cdot)$ is a constant function on $\mathcal{Z}$, and
so is $\ell(\cdot;\beta)$. Thus, we have

$\mathcal{S}=\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)].$

This completes the proof. $\square$

For better understanding, we give an intuitive explanation of the above
theorem. The first conclusion shows that the worst-case loss quantity
$\mathcal{S}=\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]$
is lower bounded by the weighted average of $N$ worst-case loss quantities
with respect to $N$ point masses ${\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}$,
$i=1,\cdots,N$, which is easier to calculate according to Lemma 3.1. The
second conclusion shows that the worst-case loss quantity can be upper bounded
by using the weak Lipschitz property of the kernel function $\psi_{\beta}$.
The third conclusion shows that when the weak Lipschitz constant is zero, then
the upper bound is met. In addition, from (a) and (b), we have that if
$\delta=0$, then
$\mathcal{S}\geq\mathcal{L}\geq\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]=\mathcal{U}\geq\mathcal{S}$.
That is to say, if $\psi_{\beta}$ is
$(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz at $\mathcal{Z}_{N}$ and
$\delta=0$, then
$\mathcal{S}=\mathcal{U}=\mathcal{L}=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]$.
Therefore, in the remaining part of this work, we shall only consider the case
when $L_{\beta}^{\mathcal{Z}_{N}}\in(0,\infty)$ and $\delta\in(0,\infty)$.

Note that if one fixes the input data while varying $\delta$, the worst-case
loss quantity $\mathcal{S}(\cdot)$, the lower bound $\mathcal{L}(\cdot)$ and
the upper bound $\mathcal{U}(\cdot)$ are all functions of $\delta$ on
$[0,\infty)$. A few remarks are in order. First, the lower bound
$\mathcal{L}(\cdot)$ is larger than the trivial lower bound
$\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]$ given in Zhang et al. (2022,
Lemma 1). Second, the upper bound $\mathcal{U}(\cdot)$ is continuous on
$[0,\infty)$ and in particular, right-continuous at $\delta=0$. This is
similar to the continuity of another existing upper bound $\mathcal{I}(\cdot)$
(Zhang et al. 2022, Remark 2). Third, if we have
$\mathcal{S}(\delta)=\mathcal{U}(\delta)$ for each $\delta\in(0,\infty)$ (for
example, when Theorem 3.2 or Theorem 3.3 holds true), then
$\mathcal{S}(\cdot)$ is continuous on $[0,\infty)$. It is worth noting that
another sufficient condition for the continuity of $\mathcal{S}(\cdot)$ has
been studied in Zhang et al. (2022, Remark 2), where the loss function $\ell$
is required to be a composition of a non-decreasing concave function and the
cost function $d(\cdot,\cdot)$.

Next, we will analyse various cases on when the lower or upper bound for the
worst-case loss quantity provided in Theorem 3.1 is achievable.

###  3.2 Equivalence in (5) when $r=1$

We first consider the case when $r=1$. The following theorem provides a
sufficient condition on when the lower and upper bounds in Theorem 3.1 will
coincide.

######  Theorem 3.2.

Let $\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$ be
a given dataset and
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z})$
be the corresponding empirical distribution. In addition, let $d(\cdot,\cdot)$
be a cost function on $\mathcal{Z}\times\mathcal{Z}$ and $\delta\in(0,\infty)$
be a scalar. Suppose the loss function
$\ell:\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ takes the form as

$\ell\colon(z;\beta)\mapsto\psi_{\beta}(z),$

where the function $\psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}$
satisfies the following assumptions:

  1. (A1)

$\psi_{\beta}$ is $(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz at
$\mathcal{Z}_{N}$ with $L_{\beta}^{\mathcal{Z}_{N}}\in(0,\infty)$;

  2. (A2)

for any $\epsilon\in(0,L_{\beta}^{\mathcal{Z}_{N}})$ and each
$Z^{(i)}\in\mathcal{Z}_{N}$, there exists
$\tilde{Z}^{(i)}_{\epsilon}\in\mathcal{Z}$ such that $\delta\leq
d(\tilde{Z}^{(i)}_{\epsilon},Z^{(i)})<\infty$ and

$\psi_{\beta}(\tilde{Z}^{(i)}_{\epsilon})-\psi_{\beta}(Z^{(i)})\geq(L_{\beta}^{\mathcal{Z}_{N}}-\epsilon)d(\tilde{Z}^{(i)}_{\epsilon},Z^{(i)}).$

Then we have that $\mathcal{L}=\mathcal{S}=\mathcal{U}$ in Theorem 3.1, that
is,

$\displaystyle\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+L_{\beta}^{\mathcal{Z}_{N}}\delta.$
(7)

Proof. Since $\psi_{\beta}$ is $(L_{\beta}^{\mathcal{Z}_{N}},d)$-Lipschitz at
$\mathcal{Z}_{N}$, by Theorem 3.1, we have that

$\begin{array}[]{ll}\mathcal{L}\leq\mathcal{S}=\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\\\
\leq\mathcal{U}=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+L_{\beta}^{\mathcal{Z}_{N}}\delta.\end{array}$

Hence, in order to prove (7), it suffices to show that
$\mathcal{L}\geq\mathcal{U}$.

Let $\epsilon\in\left(0,\min\\{L_{\beta}^{\mathcal{Z}_{N}},\delta
L_{\beta}^{\mathcal{Z}_{N}}\\}\right)$ be an arbitrary scalar. By Assumption
(A2), for any $Z^{(i)}\in\mathcal{Z}_{N}$, there exists
$\tilde{Z}^{(i)}\in\mathcal{Z}$ such that $\delta\leq
d(\tilde{Z}^{(i)},Z^{(i)})<\infty$ and

$\psi_{\beta}(\tilde{Z}^{(i)})-\psi_{\beta}(Z^{(i)})\geq\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)d(\tilde{Z}^{(i)},Z^{(i)}).$

Let $\eta^{(i)}\coloneqq\delta/d(\tilde{Z}^{(i)},Z^{(i)})\in(0,1]$ and choose

$\tilde{\mathbb{P}}^{(i)}\coloneqq\eta^{(i)}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}+(1-\eta^{(i)}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z}).$

Then one has

$\begin{array}[]{ll}\mathcal{W}_{d,1}\left(\tilde{\mathbb{P}}^{(i)},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\right)=\eta^{(i)}d(\tilde{Z}^{(i)},Z^{(i)})+(1-\eta^{(i)})d(Z^{(i)},Z^{(i)})=\eta^{(i)}d(\tilde{Z}^{(i)},Z^{(i)})=\delta,\end{array}$

and

$\begin{array}[]{ll}\mathrm{E}_{\tilde{\mathbb{P}}^{(i)}}[\ell(Z;\beta)]&=\eta^{(i)}\psi_{\beta}(\tilde{Z}^{(i)})+(1-\eta^{(i)})\psi_{\beta}(Z^{(i)})=\psi_{\beta}(Z^{(i)})+\eta^{(i)}\left[\psi_{\beta}(\tilde{Z}^{(i)})-\psi_{\beta}(Z^{(i)})\right]\\\
&\geq\psi_{\beta}(Z^{(i)})+\eta^{(i)}\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)d(\tilde{Z}^{(i)},Z^{(i)})=\ell(Z^{(i)};\beta)+L_{\beta}^{\mathcal{Z}_{N}}\delta-\epsilon.\end{array}$

Let $\epsilon\rightarrow 0$, we have that for any $i=1,\cdots,N$,

$\begin{array}[]{ll}\mathcal{L}_{i}=\sup\limits_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\left\\{\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\middle|\mathcal{W}_{d,1}\left(\mathbb{P},{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\right)\leq\delta\right\\}\geq\ell(Z^{(i)};\beta)+L_{\beta}^{\mathcal{Z}_{N}}\delta.\end{array}$

Therefore, it holds that

$\begin{array}[]{ll}\mathcal{L}=\sum_{i=1}^{N}\mu_{i}\mathcal{L}_{i}\geq\sum_{i=1}^{N}\mu_{i}\left(\ell(Z^{(i)};\beta)+L_{\beta}^{\mathcal{Z}_{N}}\delta\right)=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+L_{\beta}^{\mathcal{Z}_{N}}\delta=\mathcal{U}.\end{array}$

This completes the proof. $\square$

For better illustration, we give a visualization of Assumptions (A1-A2) in
Figure 1 under the setting where
$\mathcal{Z}=\mathbb{R},\mathcal{Z}_{N}=\\{Z^{(1)},Z^{(2)}\\}$ and
$d(z^{\prime},z)=\left|z^{\prime}-z\right|$. Assumption (A1) says that for any
$z\in\mathbb{R}$, we have $\left|\ell(z;\beta)-\ell(Z^{(i)};\beta)\right|\leq
L_{\beta}^{\mathcal{Z}_{N}}\left|z-Z^{(i)}\right|$ for $i=1,2$, which is
equivalent to the condition that the graph of $\ell(\cdot;\beta)$ must stay
inside two blue double cones with the opening angle
$\alpha=\operatorname{arctan}\left(L_{\beta}^{\mathcal{Z}_{N}}\right)$.
Assumption (A2) says that for any $\epsilon\in(0,L_{\beta}^{\mathcal{Z}_{N}})$
and $i=1,2$, there exists $\tilde{Z}^{(i)}$ depending on $\epsilon$ such that
$\left|\tilde{Z}^{(i)}-Z^{(i)}\right|\geq\delta$ and
$\ell(\tilde{Z}^{(i)};\beta)-\ell(Z^{(i)};\beta)\geq(L_{\beta}^{\mathcal{Z}_{N}}-\epsilon)\left|\tilde{Z}^{(i)}-Z^{(i)}\right|$.
This is equivalent to requiring the existence of a point $\tilde{Z}^{(i)}$
such that the green slope $\tan(\tilde{\alpha}_{i})$ of the line passing
through $\left(\tilde{Z}^{(i)},\ell(\tilde{Z}^{(i)};\beta)\right)$ and
$\left({Z}^{(i)},\ell({Z}^{(i)};\beta)\right)$ satisfies
$\tan(\tilde{\alpha}_{i})\geq\tan(\alpha)-\epsilon$, while the distance
between $\tilde{Z}^{(i)}$ and ${Z}^{(i)}$ is at least $\delta$.

Figure 1: An illustration of Assumptions (A1-A2) (best viewed in color) when
$\mathcal{Z}=\mathbb{R},\mathcal{Z}_{N}=\\{Z^{(1)},Z^{(2)}\\}$ and
$d(z^{\prime},z)=\left|z^{\prime}-z\right|$.

######  Remark 3.1.

In Theorem 3.2, it is required that the condition (A2) holds for any
$i=1,\dots,N$, with respect to the same Lipschitz constant
$L_{\beta}^{\mathcal{Z}_{N}}$. To relax this condition, one might assume that
Assumptions (A1-A2) hold at each $Z^{(i)}$ with a Lipschitz constant
$L_{\beta}^{\\{Z^{(i)}\\}}$, for $i=1,\cdots,N$. Even though it might not
guarantee that the lower bound and upper bound for $\mathcal{S}$ coincide as
in Theorem 3.2, we show in Appendix C that one still has closed forms for the
lower and upper bounds given by

$\begin{array}[]{ll}\widehat{\mathcal{L}}=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+\sum_{i=1}^{N}\mu_{i}L_{\beta}^{\\{Z^{(i)}\\}}\delta,\\\
\widehat{\mathcal{U}}=\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]+\max_{i=1,\dots,N}L_{\beta}^{\\{Z^{(i)}\\}}\delta.\end{array}$

It is worth mentioning that our Assumptions (A1) and (A2) are weaker than
those made in the literature. First, in the existing works such as
Shafieezadeh-Abadeh et al. (2015, Theorem 4), Shafieezadeh-Abadeh et al.
(2019, Theorem 9, Theorem 14), An and Gao (2021, Assumption 1) and Gao (2022,
Assumption 1(I)), the Lipschitz assumption on the function $\psi_{\beta}$
needs to hold globally, while our Assumption (A1) only requires it to hold
when the second argument of the cost function $d(\cdot,\cdot)$ is one of the
empirical points. Later, Example 3.1 will provide an instance wherein the loss
function lacks the global Lipschitz continuity property, but it satisfies our
weak Lipschitz property in certain scenarios. Second, Gao (2022, Assumption
1(II)) requires that the Lipschitz constant is attained at infinity222This
means that for any $i=1,\cdots,N$, there exists a sequence
$\left\\{\tilde{Z}^{(i)}_{k}\right\\}$ such that
$\lim\limits_{k\rightarrow\infty}d(\tilde{Z}^{(i)}_{k},Z^{(i)})=\infty$ and
$\lim\limits_{k\rightarrow\infty}\frac{\psi_{\beta}(\tilde{Z}^{(i)}_{k})-\psi_{\beta}(Z^{(i)})}{d(\tilde{Z}^{(i)}_{k},Z^{(i)})}=L_{\beta}^{\mathcal{Z}_{N}}$.,
and Shafieezadeh-Abadeh et al. (2019, Assumption 10, Assumption 21) requires
that the Lipschitz constant is attained exactly at a certain point where the
derivative also exists, while our Assumption (A2) only requires it to be
(approximately) attained at points far enough from the empirical points.
Third, we do not assume any convexity of $\psi_{\beta}$ as in Wu et al.
(2022). In the subsequent contexts, Example 3.2 will provide an instance where
the Lipschitz constant is not attained at infinity and the loss function is
not convex but the equivalence (7) holds conditionally according to our
Theorem 3.2. Fourth, we do not require $d(\cdot,\cdot)$ to be positive
definite (that is, $d(z^{\prime},z)=0$ if and only if $z^{\prime}=z$) as in
Blanchet and Murthy (2019, Assumption (A1)) and Zhang et al. (2022, Assumption
1).

Another important observation of Assumption (A2) is that for any
$i=1,\cdots,N$, $d(\tilde{Z}^{(i)}_{\epsilon},Z^{(i)})$ is required to be at
least $\delta$. That is to say, one requires the knowledge of $\delta$ to tell
whether Assumption (A2), and further the equivalence (7), hold or not in
practice. At first glance, it seems restrictive, compared with the existing
results where the equivalence (7) has been studied with arbitrary $\delta>0$.
Fortunately, as it will be shown later in Section 4, our Assumption (A2)
indeed holds for most of the commonly-used loss functions for any $\delta>0$.
In particular, Propositions 4.1, 4.2, 4.3, and 4.4 serve as guidance on
finding $L_{\beta}^{\mathcal{Z}_{N}}$ and checking the validity of Assumption
(A2) (and Assumption (B) later in Theorem 3.3).

We give the following two examples to show that the two assumptions in Theorem
3.2 are not removable. Specifically, we will see that with the same loss
function $\ell(\cdot,\cdot)$, the equivalence (7) holds for some values of
$\delta$ and fails for some other values, which indicates that the condition
$d(\tilde{Z}^{(i)},Z^{(i)})\geq\delta$ in Assumption (A2) is not removable. In
addition, Example 3.2 also shows that our weak Lipschitz property in
Assumption (A1) needs to depend on the empirical distribution
$\mathbb{P}_{N}$, which provides the evidence that our generalization is
essential compared with the existing results which rely on the global
Lipschitz property of $\psi_{\beta}$. Specifically, these two examples
illustrate that the classical Lipschitz terminology fails to capture the exact
reformulation of certain WDRO problems. Similar to (Kuhn et al. 2019, Remark
3), one can see in Example 3.1 and Example 3.2 that the value of
$L_{\beta}^{\mathcal{Z}_{N}}$ is not simple in general cases. Nevertheless,
this notion of the weak Lipschitz constant is better (i.e., lower) than the
classical Lipschitz constant, and applicable for more generic class of loss
functions. Efficient scheme to compute $L_{\beta}^{\mathcal{Z}_{N}}$ is an
interesting topic to explore, and we leave it for future research. The
detailed proofs corresponding to these two examples are given in Appendix B.1
and Appendix B.2.

######  Example 3.1 (Binary cross-entropy (Yi-de et al. 2004, Scott 2012,
Hurtik et al. 2022)).

Let the univariate function $h\colon(0,1)\rightarrow\mathbb{R}$ be defined as

$h(t)=t\log(t)+(1-t)\log(1-t).$

Define the loss function $\ell:(0,1)\times(0,1)\rightarrow\mathbb{R}$ as
$\ell(z;\beta)=\psi_{\beta}(z):=h(\beta z)$. Consider the cost function
$d\colon(0,1)\times(0,1)\rightarrow[0,1)$ defined as
$d(z^{\prime},z)=\left|z^{\prime}-z\right|$ for any $z^{\prime},z\in(0,1)$.
Then the following statements hold true.

  1. (a)

$h$ is convex, continuously differentiable, but not globally Lipschitz on
$(0,1)$.

  2. (b)

Given any $\beta\in(0,1)$ and $\hat{z}\in(0,\frac{1}{2}]$. We have that
$\psi_{\beta}$ is $(L_{\beta}^{\\{\hat{z}\\}},d)$-Lipschitz at
$\\{\hat{z}\\}$, where
$L_{\beta}^{\\{\hat{z}\\}}=-\beta\log(\beta\hat{z})-(1/\hat{z}-\beta)\log(1-\beta\hat{z})$.
Moreover, for $\mathbb{P}_{N}={\boldsymbol{\chi}}_{\\{\hat{z}\\}}$, we have
the following two results:

    1. (b1)

if $0<\delta<\hat{z}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\ell(\hat{z};\beta)+L_{\beta}^{\\{\hat{z}\\}}\delta$;

    2. (b2)

if $\delta\geq\hat{z}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=0$.

######  Example 3.2 (Hard sigmoid (Howard et al. 2019) / HardTanh (Collobert
2004)).

Let the univariate function $h\colon\mathbb{R}\rightarrow\mathbb{R}$ be
defined as

$h(t)=\max\left\\{0,\min\left\\{1,\frac{t+1}{2}\right\\}\right\\}.$

Define the loss function
$\ell:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ as
$\ell(z;\beta)=\psi_{\beta}(z):=h(\langle\beta,z\rangle)$. Consider the cost
function $d\colon\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow[0,\infty)$ as
$d(z^{\prime},z)=\|z^{\prime}-z\|_{{\mathbb{R}^{n}}}$. For any
$\beta\in\mathbb{R}^{n}$, we denote $\alpha_{\beta}$ to be a vector in
$\mathbb{R}^{n}$ satisfying $\|\alpha_{\beta}\|_{{\mathbb{R}^{n}}}=1$ and
$\langle\alpha_{\beta},\beta\rangle=\|\beta\|_{\mathbb{R}^{n},*}$.

  1. (a)

Given scalars $0<\vartheta_{1}\leq\vartheta_{2}<\infty$ and any vector
$\beta\in\mathbb{R}^{n}$ satisfying
$\vartheta_{1}\leq\|\beta\|_{\mathbb{R}^{n},*}\leq\vartheta_{2}$. Suppose
$\mathbb{P}_{N}={\boldsymbol{\chi}}_{\\{\hat{z}\\}}$ with
$\hat{z}={\boldsymbol{0}}_{\mathbb{R}^{n}}$, then $\psi_{\beta}$ is
$\left(\frac{\|\beta\|_{\mathbb{R}^{n},*}}{2},d\right)$-Lipschitz at
$\\{\hat{z}\\}$. Moreover,

    1. (a1)

if $0<\delta\leq\frac{1}{\vartheta_{2}}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\ell(\hat{z};\beta)+\frac{\|\beta\|_{\mathbb{R}^{n},*}}{2}\delta$;

    2. (a2)

if $\delta\geq\frac{1}{\vartheta_{1}}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\ell(\hat{z};\beta)+\frac{1}{2}$.

  2. (b)

Given any $\beta\in\mathbb{R}^{n}$ such that
$\|\beta\|_{\mathbb{R}^{n},*}=\vartheta>0$. Suppose
$\mathbb{P}_{N}={\boldsymbol{\chi}}_{\\{\bar{z}\\}}$ with
$\bar{z}=-\frac{3}{\vartheta}\alpha_{\beta}$, then $\psi_{\beta}$ is
$(\frac{\vartheta}{4},d)$-Lipschitz at $\\{\bar{z}\\}$. Moreover,

    1. (b1)

if $0<\delta\leq\frac{4}{\vartheta}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\ell(\bar{z};\beta)+\frac{\vartheta}{4}\delta$;

    2. (b2)

if $\delta\geq\frac{4}{\vartheta}$, then
$\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\ell(\bar{z};\beta)+1$.

###  3.3 Equivalence in (5) when $r>1$

Next, we derive a sufficient condition on when the equivalence (5) holds for
$r>1$.

######  Theorem 3.3.

Let $\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$ be
a given dataset and
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z})$
be the corresponding empirical distribution. In addition, let $d(\cdot,\cdot)$
be a cost function on $\mathcal{Z}\times\mathcal{Z}$ and $\delta\in(0,\infty)$
be a scalar. Suppose the loss function
$\ell:\mathcal{Z}\times\mathcal{B}\rightarrow\mathbb{R}$ takes the form as

$\ell\colon(z;\beta)\mapsto\psi_{\beta}^{r}(z),\mbox{ with }r\in(1,\infty),$

where $\psi_{\beta}\colon\mathcal{Z}\rightarrow\mathbb{R}_{+}$ satisfies
Assumption (A1) in Theorem 3.2 with
$L_{\beta}^{\mathcal{Z}_{N}}\in(0,\infty)$, and also satisfies the following
assumption:

  1. (B)

for any $\epsilon\in(0,L_{\beta}^{\mathcal{Z}_{N}})$ and
$Z^{(i)}\in\mathcal{Z}_{N}$, there exists
$\tilde{Z}^{(i)}_{\epsilon}\in\mathcal{Z}$ such that
$d(\tilde{Z}^{(i)}_{\epsilon},Z^{(i)})\in\mathcal{D}(Z^{(i)})$ and

$\psi_{\beta}(\tilde{Z}^{(i)}_{\epsilon})-\psi_{\beta}(Z^{(i)})\geq(L_{\beta}^{\mathcal{Z}_{N}}-\epsilon)d(\tilde{Z}^{(i)}_{\epsilon},Z^{(i)}),$

where the set $\mathcal{D}(Z^{(i)})\subset\mathbb{R}$ is defined as

$\begin{cases}\left\\{\frac{\psi_{\beta}(Z^{(i)})}{\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}}\delta\right\\}&\text{if
}\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\neq 0,\\\ [\delta,\infty)&\text{if
}\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]=0.\end{cases}$

Then we have $\mathcal{S}=\mathcal{U}$ in Theorem 3.1, that is,

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta\right)^{r}.$

Proof. Let $\epsilon\in\left(0,\min\\{L_{\beta}^{\mathcal{Z}_{N}},\delta
L_{\beta}^{\mathcal{Z}_{N}}\\}\right)$ be a scalar. According to Assumption
(B), for any $Z^{(i)}\in\mathcal{Z}_{N}$, there exists $\tilde{Z}^{(i)}$ such
that $d(\tilde{Z}^{(i)},Z^{(i)})\in\mathcal{D}(Z^{(i)})$ and
$\psi_{\beta}(\tilde{Z}^{(i)})-\psi_{\beta}(Z^{(i)})\geq\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)d(\tilde{Z}^{(i)},Z^{(i)})$.
We consider two cases.

#### Case 1.

When $\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\neq 0$, we know that for each
$i=1,\cdots,N$,

$d(\tilde{Z}^{(i)},Z^{(i)})=\frac{\psi_{\beta}(Z^{(i)})}{\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}}\delta.$

Let
$\tilde{\mathbb{P}}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}$and
$\tilde{\pi}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}\otimes{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}$.
Then it can be seen that $\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$,
$\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$, since for any
measurable sets $A,B\subset\mathcal{Z}$,

$\begin{array}[]{llll}\tilde{\pi}(A\times\mathcal{Z})&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}(A){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(\mathcal{Z})&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}(A)=\tilde{\mathbb{P}}(A),\\\
\tilde{\pi}(\mathcal{Z}\times
B)&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}(\mathcal{Z}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)=\mathbb{P}_{N}(B).\end{array}$

In addition, it can be seen that

$\begin{array}[]{ll}\mathcal{W}_{d,r}\left(\tilde{\mathbb{P}},\mathbb{P}_{N}\right)\leq\left(\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}=\left(\sum_{i=1}^{N}\mu_{i}d^{r}(\tilde{Z}^{(i)},Z^{(i)})\right)^{\frac{1}{r}}=\delta.\end{array}$

Moreover, we have that

$\begin{array}[]{ll}\left(\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}&=\left(\sum_{i=1}^{N}\mu_{i}\psi_{\beta}^{r}(\tilde{Z}^{(i)})\right)^{\frac{1}{r}}=\left(\sum_{i=1}^{N}\mu_{i}\left(\psi_{\beta}(Z^{(i)})+\psi_{\beta}(\tilde{Z}^{(i)})-\psi_{\beta}(Z^{(i)})\right)^{r}\right)^{\frac{1}{r}}\\\
&\geq\left(\sum\limits_{i=1}^{N}\mu_{i}\left(\psi_{\beta}(Z^{(i)})+\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)d(\tilde{Z}^{(i)},Z^{(i)})\right)^{r}\right)^{\frac{1}{r}}\\\
&=^{(\Delta)}\left(\sum_{i=1}^{N}\mu_{i}\psi_{\beta}^{r}(Z^{(i)})\right)^{\frac{1}{r}}+\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)\left(\sum_{i=1}^{N}\mu_{i}d^{r}(\tilde{Z}^{(i)},Z^{(i)})\right)^{\frac{1}{r}}\\\
&=\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+(L_{\beta}^{\mathcal{Z}_{N}}\delta-\epsilon),\end{array}$

where the equality (Δ) follows from the fact that for any
$i\in\\{1,\cdots,N\\}$, we always have
$\psi_{\beta}(Z^{(i)})=\left[\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}/\delta\right]d(\tilde{Z}^{(i)},Z^{(i)})$.

#### Case 2.

When $\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]=0$, we have
$d(\tilde{Z}^{(i)},Z^{(i)})\in[\delta,\infty)$ for any $i=1,\cdots,N$. Set
$\eta^{(i)}\coloneqq\delta^{r}/d^{r}(\tilde{Z}^{(i)},Z^{(i)})\in(0,1]$ for
each $i=1,\dots,N$, and define

$\begin{array}[]{lll}\tilde{\mathbb{P}}&\coloneqq\sum_{i=1}^{N}\mu_{i}\eta^{(i)}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}+\mu_{i}(1-\eta^{(i)}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}},\\\
\tilde{\pi}&\coloneqq\sum_{i=1}^{N}\mu_{i}\eta^{(i)}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}\otimes{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}+\mu_{i}(1-\eta^{(i)}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\otimes{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}.\end{array}$

Then we can see that $\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ and
$\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$, as for any measurable
sets $A,B\subset\mathcal{Z}$,

$\begin{array}[]{lll}\tilde{\pi}(A\times\mathcal{Z})&=\sum_{i=1}^{N}\mu_{i}\eta^{(i)}{\boldsymbol{\chi}}_{\\{\tilde{Z}^{(i)}\\}}(A)+\mu_{i}(1-\eta^{(i)}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(A)&=\tilde{\mathbb{P}}(A),\\\
\tilde{\pi}(\mathcal{Z}\times
B)&=\sum_{i=1}^{N}\mu_{i}\eta^{(i)}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)+\mu_{i}(1-\eta^{(i)}){\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)&=\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}(B)=\mathbb{P}_{N}(B).\end{array}$

Moreover, we have
$\int\limits_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)=\sum\limits_{i=1}^{N}\mu_{i}\eta^{(i)}d^{r}(\tilde{Z}^{(i)},Z^{(i)})+\mu_{i}(1-\eta^{(i)})d^{r}(Z^{(i)},Z^{(i)})=\sum\limits_{i=1}^{N}\mu_{i}\eta^{(i)}d^{r}(\tilde{Z}^{(i)},Z^{(i)})$.
Thus, it holds that

$\begin{array}[]{ll}\mathcal{W}_{d,r}\left(\tilde{\mathbb{P}},\mathbb{P}_{N}\right)\leq\left(\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(\tilde{z},z)\mathrm{d}\tilde{\pi}(\tilde{z},z)\right)^{\frac{1}{r}}=\left(\sum_{i=1}^{N}\mu_{i}\eta^{(i)}d^{r}(\tilde{Z}^{(i)},Z^{(i)})\right)^{\frac{1}{r}}=\delta.\end{array}$

The fact that $\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]=0$ together with the
nonnegativity of the function $\psi_{\beta}$ implies that
$\psi_{\beta}(Z^{(i)})=0$ for any $i=1,\cdots,N$, which further indicates that

$\begin{array}[]{ll}\left(\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}&=\left(\sum_{i=1}^{N}\mu_{i}\eta^{(i)}\psi_{\beta}^{r}(\tilde{Z}^{(i)})+\mu_{i}(1-\eta^{(i)})\psi_{\beta}^{r}(Z^{(i)})\right)^{\frac{1}{r}}\\\
&=\left(\sum_{i=1}^{N}\mu_{i}\eta^{(i)}\left(\psi_{\beta}(\tilde{Z}^{(i)})-\psi_{\beta}(Z^{(i)})\right)^{r}\right)^{\frac{1}{r}}\\\
&\geq\left(L_{\beta}^{\mathcal{Z}_{N}}-\frac{\epsilon}{\delta}\right)\left(\sum_{i=1}^{N}\mu_{i}\eta^{(i)}d^{r}(\tilde{Z}^{(i)},Z^{(i)})\right)^{\frac{1}{r}}=L_{\beta}^{\mathcal{Z}_{N}}\delta-\epsilon=\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta-\epsilon.\end{array}$

Therefore, combining the above two cases, for any given
$0<\epsilon<\min\\{L_{\beta}^{\mathcal{Z}_{N}},\delta
L_{\beta}^{\mathcal{Z}_{N}}\\}$, we can construct
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,r}\left(\tilde{\mathbb{P}},\mathbb{P}_{N}\right)\leq\delta$
and

$\mathrm{E}_{\tilde{\mathbb{P}}}[\ell(Z;\beta)]\geq\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta-\epsilon\right)^{r}.$

By letting $\epsilon\rightarrow 0$ and recalling that
$\mathcal{U}=\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]^{\frac{1}{r}}+L_{\beta}^{\mathcal{Z}_{N}}\delta\right)^{r}$,
we can conclude that

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\geq\mathcal{U}.$

The fact that $\psi_{\beta}$ satisfies Assumption (A1) together with Theorem
3.1 also implies that

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]\leq\mathcal{U},$

which completes the proof. $\square$

Note that when the loss quantity at the empirical distribution
$\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]$ vanishes, one can see that
Assumption (A2) and Assumption (B) are the same. On the other hand, when
$\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\neq 0$, if
$\psi_{\beta}(Z^{(i)})=0$ for some $i=1,\cdots,N$, one can always choose
$\tilde{Z}^{(i)}_{\epsilon}=Z^{(i)}$ for this $i$.

##  4 Applications to different function classes

In this section, we present the applications of Theorem 3.2 and Theorem 3.3 in
various regression and classification problems. We first give the definition
of an absolutely homogeneous function, which will be used in the remaining
part of this section.

######  Definition 4.1.

An extended-valued function $\Upsilon\colon\mathcal{Z}\rightarrow[0,\infty]$
on a real vector space $\mathcal{Z}$ is called absolutely homogeneous if one
has $\Upsilon(tz)=\left|t\right|\Upsilon(z)$ for any $t\in\mathbb{R}$ and
$z\in\mathcal{Z}$. In addition, $\Upsilon$ is called proper if there exists
$z_{0}\in\mathcal{Z}$ such that $\Upsilon(z_{0})=1$.

From the above definition, we can see that if $\Upsilon$ is absolutely
homogeneous, then $\Upsilon(0_{\mathcal{Z}})=0$ and
$\Upsilon^{-1}(0)=\left\\{z\in\mathcal{Z}\mid\Upsilon(z)=0\right\\}$ is a cone
on $\mathcal{Z}$. Besides, the following two functions

  * •

$z\mapsto+\infty$ for all $0\neq z\in\mathcal{Z}$ and $z\mapsto 0$ for $z=0$;

  * •

$z\mapsto 0$ for all $z\in\mathcal{Z}$,

are absolutely homogeneous, but not proper.

###  4.1 Applications to simple piecewise linear regression loss functions

We start from the applications of our results to simple piecewise linear
regression loss functions as follows.

######  Proposition 4.1 (Linear loss).

Let $\mathcal{Z}$ be a (finite or infinite dimensional) real vector space.
Suppose that
$\left\llbracket\cdot\right\rrbracket\colon\mathcal{Z}\rightarrow[0,\infty]$
is absolutely homogeneous and proper,
$\phi\colon\mathcal{Z}\rightarrow\mathbb{R}$ is linear,
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$ and

$L_{\phi}\coloneqq\sup_{z\in\mathcal{Z}}\left\\{\left|\phi(z)\right|\mid\left\llbracket
z\right\rrbracket=1\right\\}\in[0,+\infty).$

Let the cost function $d:\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$ be
defined as $d(z^{\prime},z)\coloneqq\left\llbracket
z^{\prime}-z\right\rrbracket$ for any $z^{\prime},z\in\mathcal{Z}$. Given any
scalar $\tau\in\mathbb{R}$, then the functions $\left|\phi\right|$,
$\max\\{0,\phi-\tau\\}$ and $\max\\{0,\left|\phi\right|-\tau\\}$ are
$(L_{\phi},d)$-Lipschitz at $\mathcal{Z}$. Furthermore, they also satisfy
Assumptions (A1), (A2) and (B) at $\mathcal{Z}$ for any $\delta>0$ if
$L_{\phi}>0$.

Proof. In order to prove that $|\phi|$, $\max\\{0,\phi-\tau\\}$ and
$\max\\{0,|\phi|-\tau\\}$ are $(L_{\phi},d)$-Lipschitz at $\mathcal{Z}$, by
noting the fact that for any $z^{\prime},z\in\mathcal{Z}$,

$\begin{array}[]{lll}\left||\phi(z^{\prime})|-|\phi(z)|\right|&\leq\left|\phi(z^{\prime})-\phi(z)\right|;\\\
\lx@intercol\left|\max\\{0,\phi(z^{\prime})-\tau\\}-\max\\{0,\phi(z)-\tau\\}\right|\hfil\lx@intercol&\leq\left|\phi(z^{\prime})-\phi(z)\right|;\\\
\lx@intercol\left|\max\\{0,|\phi(z^{\prime})|-\tau\\}-\max\\{0,|\phi(z)|-\tau\\}\right|\hfil\lx@intercol&\leq\left||\phi(z^{\prime})|-|\phi(z)|\right|\leq\left|\phi(z^{\prime})-\phi(z)\right|;\end{array}$

we only need to prove that

$\left|\phi(z^{\prime})-\phi(z)\right|=\left|\phi(z^{\prime}-z)\right|\leq
L_{\phi}d(z^{\prime},z).$

This can be seen as follows:

  * •

if $d(z^{\prime},z)=\left\llbracket z^{\prime}-z\right\rrbracket=\infty$, then
it holds true immediately;

  * •

if $d(z^{\prime},z)=\left\llbracket z^{\prime}-z\right\rrbracket=0$, since
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$, one also
has $\left|\phi(z^{\prime}-z)\right|=0$;

  * •

if $0<d(z^{\prime},z)=\left\llbracket z^{\prime}-z\right\rrbracket<\infty$,
then

$\begin{array}[]{ll}\left|\phi(z^{\prime}-z)\right|=\left\llbracket
z^{\prime}-z\right\rrbracket\left|\phi\left(\frac{z^{\prime}-z}{\left\llbracket
z^{\prime}-z\right\rrbracket}\right)\right|\leq\left\llbracket
z^{\prime}-z\right\rrbracket L_{\phi}=L_{\phi}d(z^{\prime},z).\end{array}$

Thus, $|\phi|$, $\max\\{0,\phi-\tau\\}$ and $\max\\{0,|\phi|-\tau\\}$ are all
$(L_{\phi},d)$-Lipschitz at $\mathcal{Z}$.

Suppose that $L_{\phi}>0$. From the previous discussion, we have that
$|\phi|$, $\max\\{0,\phi-\tau\\}$ and $\max\\{0,|\phi|-\tau\\}$ satisfy
Assumption (A1) at $\mathcal{Z}$ with any $\delta>0$. By the definition of
$L_{\phi}$, for any $0<\epsilon<L_{\phi}$, there exists
$\tilde{v}\in\mathcal{Z}$ such that
$\left\llbracket\tilde{v}\right\rrbracket=1$ and
$\left|\phi(\tilde{v})\right|\geq L_{\phi}-\epsilon/2$. Since $\phi$ is linear
and $\left\llbracket\cdot\right\rrbracket$ is absolutely homogeneous, for any
$v\in\mathcal{Z}$, we have $\left\llbracket-v\right\rrbracket=\left\llbracket
v\right\rrbracket$ and $\phi(-v)=-\phi(v)$. Hence, one can always choose
$\tilde{v}\in\mathcal{Z}$ such that

$\left\llbracket\tilde{v}\right\rrbracket=1\quad\text{and}\quad\phi(\tilde{v})\geq
L_{\phi}-\epsilon/2>L_{\phi}-\epsilon>0.$

Next we prove that the functions $|\phi|$, $\max\\{0,\phi-\tau\\}$ and
$\max\\{0,|\phi|-\tau\\}$ satisfy Assumptions (A2) and (B) at $\mathcal{Z}$
for any $\delta>0$.

  * •

For the function $|\phi|$, given any $z\in\mathcal{Z}$ and any $\sigma>0$, by
letting $\tilde{z}=z+{\rm sgn}(\phi(z))\sigma\tilde{v}$, we have
$d(\tilde{z},z)=\left\llbracket{\rm
sgn}(\phi(z))\sigma\tilde{v}\right\rrbracket=\sigma$ and

$\begin{array}[]{ll}\left|\phi(\tilde{z})\right|-\left|\phi(z)\right|=\left|\phi(z)+{\rm
sgn}(\phi(z))\sigma\phi(\tilde{v})\right|-\left|\phi(z)\right|=\sigma\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z).\end{array}$

Therefore, $|\phi|$ satisfies Assumption (A2) at $\mathcal{Z}$ for any
$\delta>0$. Using some similar analysis as above, we can also show that
$|\phi|$ satisfies Assumption (B) at $\mathcal{Z}$.

  * •

For the function $\max\\{0,\phi-\tau\\}$, we first prove that
$\max\\{0,\phi-\tau\\}$ satisfies Assumption (A2) at $\mathcal{Z}$. For any
$z\in\mathcal{Z}$ and $\delta>0$, let

$\tilde{z}=\left\\{\begin{array}[]{ll}z+\delta\tilde{v}&\text{if
}\phi(z)\geq\tau\\\
z+\left(2(\tau-\phi(z))/\epsilon+\delta\right)\tilde{v}&\text{otherwise}\end{array}\right..$

Then if $\phi(z)\geq\tau$, we have
$d(\tilde{z},z)=\left\llbracket\delta\tilde{v}\right\rrbracket=\delta$ and

$\begin{array}[]{ll}\max\\{0,\phi(\tilde{z})-\tau\\}-\max\\{0,\phi(z)-\tau\\}\geq\phi(z+\delta\tilde{v})-\phi(z)=\delta\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z);\end{array}$

if $\phi(z)<\tau$, we have
$d(\tilde{z},z)=\left\llbracket\left(2(\tau-\phi(z))/\epsilon+\delta\right)\tilde{v}\right\rrbracket=2(\tau-\phi(z))/\epsilon+\delta\geq\delta$
and

$\begin{array}[]{lll}\max\\{0,\phi(\tilde{z})-\tau\\}-\max\\{0,\phi(z)-\tau\\}\\\
\geq\phi(z)-\tau+d(\tilde{z},z)\phi(\tilde{v})\geq-\frac{\epsilon}{2}d(\tilde{z},z)+d(\tilde{z},z)\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z).\end{array}$

Therefore, $\max\\{0,\phi-\tau\\}$ satisfies Assumptions (A2) at $\mathcal{Z}$
for any $\delta>0$.

Next, we turn to Assumption (B). Fix $r>1$, $\delta>0$, a dataset
$\mathcal{Z}_{N}\subset\mathcal{Z}$ and the corresponding empirical
distribution $\mathbb{P}_{N}$. For any $\hat{z}\in\mathcal{Z}_{N}$, we
consider the following cases.

    * –

If $\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,\phi(Z)-\tau\right\\}^{r}]=0$,
then (A2) and (B) are equivalent.

    * –

If $\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,\phi(Z)-c\right\\}^{r}]\neq 0$
and $\phi(\hat{z})>\tau$, for any $\sigma\geq\delta$, we can set
$\tilde{z}=\hat{z}+\sigma\tilde{v}$. Then we have
$\phi(\tilde{z})=\phi(\hat{z})+\sigma\phi(\tilde{v})>\tau+\sigma(L_{\phi}-\epsilon/2)>\tau$.
Therefore,
$d(\tilde{z},\hat{z})=\left\llbracket\sigma\tilde{v}\right\rrbracket=\sigma$
and

$\begin{array}[]{ll}\max\left\\{0,\phi(\tilde{z})-\tau\right\\}-\max\left\\{0,\phi(\hat{z})-\tau\right\\}=\phi(\tilde{z})-\phi(\hat{z})=\sigma\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},\hat{z}).\end{array}$

    * –

If $\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,\phi(Z)-\tau\right\\}^{r}]\neq
0$ and $\phi(\hat{z})\leq\tau$, then $\max\\{0,\phi(\hat{z})-\tau\\}=0$ and
one can choose $\tilde{z}=\hat{z}$ such that (B) holds.

This means that $\max\\{0,\phi-\tau\\}$ satisfies Assumptions (B) at
$\mathcal{Z}$ for any $\delta>0$.

  * •

Finally, we consider the function $\max\\{0,|\phi|-\tau\\}$. For any
$z\in\mathcal{Z}$ and $\delta>0$, let

$\tilde{z}=\left\\{\begin{array}[]{ll}z+{\rm
sgn}(\phi(z))\delta\tilde{v}&\text{if }|\phi(z)|\geq\tau,\\\ z+{\rm
sgn}(\phi(z))\left(\frac{2(\tau-|\phi(z)|)}{\epsilon}+\delta\right)\tilde{v}&\text{otherwise}.\end{array}\right.$

Then if $|\phi(z)|\geq\tau$, we have $d(\tilde{z},z)=\left\llbracket{\rm
sgn}(\phi(z))\delta\tilde{v}\right\rrbracket=\delta$ and

$\begin{array}[]{lll}\max\\{0,\left|\phi(\tilde{z})\right|-\tau\\}-\max\\{0,|\phi(z)|-\tau\\}\geq\left|\phi(z+{\rm
sgn}(\phi(z))\delta\tilde{v})\right|-|\phi(z)|=\delta\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z);\end{array}$

if $|\phi(z)|<\tau$, we have $d(\tilde{z},z)=\left\llbracket{\rm
sgn}(\phi(z))\left(2(\tau-|\phi(z)|)/\epsilon+\delta\right)\tilde{v}\right\rrbracket=2(\tau-|\phi(z)|)/\epsilon+\delta\geq\delta$
and

$\begin{array}[]{llll}&\max\\{0,\left|\phi(\tilde{z})\right|-\tau\\}-\max\\{0,|\phi(z)|-\tau\\}\geq\left|\phi(\tilde{z})\right|-\tau\\\
&=\left|\phi(z)+{\rm
sgn}(\phi(z))d(\tilde{z},z)\phi(\tilde{v})\right|-\tau=|\phi(z)|-\tau+d(\tilde{z},z)\phi(\tilde{v})\\\
&\geq-\frac{\epsilon}{2}d(\tilde{z},z)+d(\tilde{z},z)\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z).\end{array}$

Thus $\max\\{0,|\phi|-\tau\\}$ satisfies Assumptions (A2) at $\mathcal{Z}$ for
any $\delta>0$.

Fix $r>1$, $\delta>0$, a dataset $\mathcal{Z}_{N}\subset\mathcal{Z}$ and the
corresponding empirical distribution $\mathbb{P}_{N}$. For each
$\hat{z}\in\mathcal{Z}_{N}$, since the cases when (1)
$\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,|\phi(Z)|-\tau\right\\}^{r}]=0$ or
(2)
$\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,|\phi(Z)|-\tau\right\\}^{r}]\neq 0$
and $\left|\phi(\hat{z})\right|\leq\tau$, are easy to check, we only need to
consider the case when
$\mathrm{E}_{\mathbb{P}_{N}}[\max\left\\{0,|\phi(Z)|-\tau\right\\}^{r}]\neq 0$
and $|\phi(\hat{z})|>\tau$. For any $\sigma\geq\delta$, let
$\tilde{z}=\hat{z}+{\rm sgn}(\phi(z))\sigma\tilde{v}$. Then we can see that

$\begin{array}[]{ll}|\phi(\tilde{z})|&=\left|\phi(\hat{z})+{\rm
sgn}(\phi(z))\sigma\phi(\tilde{v})\right|=|\phi(\hat{z})|+\sigma\phi(\tilde{v})>\tau.\end{array}$

Moreover, we have $d(\tilde{z},\hat{z})=\left\llbracket{\rm
sgn}(\phi(z))\sigma\tilde{v}\right\rrbracket=\sigma$ and

$\begin{array}[]{lll}\max\left\\{0,|\phi(\tilde{z})|-\tau\right\\}-\max\left\\{0,|\phi(\hat{z})|-\tau\right\\}=\left|\phi(\hat{z})+{\rm
sgn}(\phi(z))\sigma\phi(\tilde{v})\right|-|\phi(\hat{z})|=\sigma\phi(\tilde{v})\\\
\geq(L_{\phi}-\epsilon)d(\tilde{z},\hat{z}).\end{array}$

Therefore, $\max\\{0,|\phi|-\tau\\}$ satisfies Assumptions (B) at
$\mathcal{Z}_{N}$ for any $\delta>0$.

This completes the proof. $\square$

######  Remark 4.1.

Proposition 4.1 can be viewed as a guidance to find the weak Lipschitz
constant $L_{\phi}$ when certain properties of the loss and cost functions are
given.

Based on Proposition 4.1, Theorem 3.1(c), Theorem 3.2 and Theorem 3.3, we
obtain the following corollary stating the equivalence (5) for simple
piecewise linear regression loss functions.

######  Corollary 4.1.

Under the setting of Proposition 4.1, given any scalar $\delta>0$ and any
empirical distribution $\mathbb{P}_{N}$ on $\mathcal{Z}$, it holds that for
any $r\geq 1,\tau\in\mathbb{R}$,

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z)]\right)^{\frac{1}{r}}+L_{\phi}\delta\right)^{r},$

where $\ell:\mathcal{Z}\rightarrow\mathbb{R}$ takes one of the following
forms: $\ell(\cdot)=\left|\phi(\cdot)\right|^{r}$,
$\ell(\cdot)=\max\\{0,\phi(\cdot)-\tau\\}^{r}$ or
$\ell(\cdot)=\max\\{0,\left|\phi(\cdot)\right|-\tau\\}^{r}$.

Here are some specific examples of the above corollary. Note that some of the
following results have been studied in the literature, whereas we have
provided a unified framework to study the equivalence between the worst-case
loss quantity in the WDRO problem and the regularization scheme for simple
piecewise linear regression and scalar-on-function linear regression
functions.

######  Example 4.1 (Linear-type regression).

Let $\mathcal{Z}=\mathbb{R}^{n}\times\mathbb{R}$. Given any $\delta>0$,
$\beta\in\mathbb{R}^{n}$ and any empirical distribution $\mathbb{P}_{N}$ on
$\mathbb{R}^{n}\times\mathbb{R}$. For any $r\geq 1$ and $\tau\in\mathbb{R}$,
we have

$\sup_{\mathbb{P}\in\mathfrak{M}_{r}}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+L_{\phi}(\beta)\delta\right)^{r},$

where $Z=(X,Y)$,
$\mathfrak{M}_{r}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$
and $\ell(Z;\beta)$ takes one of the following forms:

  1. (a)

$\ell(Z;\beta)=\left|Y-\langle\beta,X\rangle\right|^{r}$;

  2. (b)

$\ell(Z;\beta)=\left(Y-\langle\beta,X\rangle-\tau\right)_{+}^{r}$;

  3. (c)

$\ell(Z;\beta)=\left(\left|Y-\langle\beta,X\rangle\right|-\tau\right)_{+}^{r}$;

and $d(\cdot,\cdot)$ and $L_{\phi}(\beta)$ take one of the following forms:

  1. (i)

$d((x^{\prime},y^{\prime}),(x,y))=\|[x^{\prime}-x;y^{\prime}-y]\|_{\mathbb{R}^{n+1}}$
and $L_{\phi}(\beta)=\|[-\beta;1]\|_{\mathbb{R}^{n+1},*}$;

  2. (ii)

$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
and $L_{\phi}(\beta)=\|\beta\|_{\mathbb{R}^{n},*}$;

  3. (iii)

$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}_{\mathcal{I}}-x_{\mathcal{I}}\|_{\mathbb{R}^{|\mathcal{I}|}}+{\boldsymbol{\delta}}_{\\{{\bf
0}^{\mathbb{R}^{|\mathcal{I}^{c}|+1}}\\}}([x^{\prime}_{\mathcal{I}^{c}}-x_{\mathcal{I}^{c}};y^{\prime}-y])$
and $L_{\phi}(\beta)=\|\beta_{\mathcal{I}}\|_{\mathbb{R}^{|\mathcal{I}|},*}$
where $\mathcal{I}\subset\\{1,2,\dots,n\\}$ and
$\mathcal{I}^{c}=\\{1,2,\dots,n\\}\setminus\mathcal{I}$;

  4. (iv)

$d((x^{\prime},y^{\prime}),(x,y))=\inf_{\bar{x}\in\mathbb{R}^{s}}\left\\{\|\bar{x}\|_{\mathbb{R}^{s}}\mid
B^{T}\bar{x}=x^{\prime}-x\right\\}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
and $L_{\phi}(\beta)=\|B\beta\|_{\mathbb{R}^{s},*}$ where
$B\in\mathbb{R}^{s\times n}$ is a given matrix.

The proof associated with the above example is given in Appendix B.3. Note
that this example covers many commonly-used regression problems. Specifically,
we list some of them here.

  * •

Higher-order regression:
$\mathrm{E}_{\mathbb{P}}[|Y-\langle\beta,X\rangle|^{r}]$, $r\geq 1$. When
$r=2$, the regularized problem
$\sqrt{\mathrm{E}_{\mathbb{P}_{N}}[|Y-\langle\beta,X\rangle|^{2}]}+L_{\phi}(\beta)\delta$
is often referred as a variant of the square-root Lasso model, where
$L_{\phi}(\beta)$ is a function of $\beta$ which promotes specific structures
in $\beta$, such as smoothness, sparsity, and clustering of coordinates
(Belloni et al. 2011, Bunea et al. 2013, Stucky and Van De Geer 2017, Jiang et
al. 2021).

  * •

Lower partial moments (Bawa 1975, Fishburn 1977, Chen et al. 2011):
$\mathrm{E}_{\mathbb{P}}[\left(\langle\beta,X\rangle-\tau\right)_{+}^{r}]$,
$r\geq 1$, $\tau\in\mathbb{R}$.

  * •

Higher-order $\tau$-insensitive regression:
$\mathrm{E}_{\mathbb{P}}[\left(|Y-\langle\beta,X\rangle|-\tau\right)_{+}^{r}]$,
$r\geq 1$, $\tau\geq 0$. When $r=1$, it is the $\tau$-insensitive support
vector regression (Drucker et al. 1996, Wang et al. 2020); when $r=2$, it is
the $\tau$-smooth support vector regression (Lee et al. 2005).

In the existing literature, the equivalence between the worst-case loss
quantity in the WDRO problem and the regularization scheme for the above
problems has been studied for some specific settings. For instances, Blanchet
et al. (2019, Proposition 2, Theorem 1) studied variants of the square-root
Lasso model when $d(\cdot,\cdot)$ is an extended norm and Chu et al. (2022,
Theorem 1) covered the cases when $d(\cdot,\cdot)$ is an extended semi-norm;
Kuhn et al. (2019) studied tractable reformulation of the WDRO problem where
$\ell$ satisfies certain convex/concave properties; Gao et al. (2022,
Corollary 2) investigated more general linear models when $d(\cdot,\cdot)$ is
a metric and Wu et al. (2022) explored the piecewise linear convex loss
function when $d(\cdot,\cdot)$ is an extended norm. Moreover, when $r\geq 1$,
Montiel Olea et al. (2023) considered a similar model but with the max-sliced
Wasserstein ball.

As a natural extension of the ordinary linear regression problem, the scalar-
on-function linear regression problem has received increasing attention
nowadays, where the feature space $\mathcal{X}$ is a functional space
$\mathfrak{L}^{2}[0,1]$ instead of $\mathbb{R}^{n}$, endowed with the inner
product $\langle
x^{\prime},x\rangle=\int_{0}^{1}x^{\prime}(t)x(t)\mathrm{d}t$. We refer the
readers to Ramsay and Dalzell (1991), Ramsay and Silverman (2005), Wang et al.
(2016) for more details and discussions about the functional linear regression
problem. To the best of our knowledge, the equivalence between the worst-case
loss quantity in the WDRO problem and the regularization scheme for this class
of problems has not been established in the literature. Fortunately, based on
our results, we can give the following equivalence for the scalar-on-function
linear regression problems, whose proof can be found in Appendix B.4. It is
worth mentioning that the nonparametric model (a) has been studied in Cardot
et al. (1999), Cai and Yuan (2012) and the regularizer involving
$\int_{0}^{1}|\beta(t)|^{2}\mathrm{d}t$ has been considered in Tong and Ng
(2018, (2)). In addition, the parametric model (b) has been introduced to
reduce the degree of freedoms.

######  Example 4.2 (Scalar-on-function linear regression).

Denote the set of real-valued, square-integrable functions on $[0,1]$ as
$\mathfrak{L}^{2}[0,1]$. Given any empirical distribution $\mathbb{P}_{N}$ on
$\mathcal{Z}:=\mathfrak{L}^{2}[0,1]\times\mathbb{R}$ and any scalar
$\delta>0$, the following equality holds for any $r\geq 1$ and
$\tau\in\mathbb{R}$:

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z)]\right)^{\frac{1}{r}}+L_{\phi}\delta\right)^{r},$

where
$d((x^{\prime},y^{\prime}),(x,y))=\left(\int_{0}^{1}|x^{\prime}(t)-x(t)|^{2}\mathrm{d}t\right)^{1/2}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
for any
$(x^{\prime},y^{\prime}),(x,y)\in\mathfrak{L}^{2}[0,1]\times\mathbb{R}$;
$\ell(Z)=|\phi(Z)|^{r}$, $\ell(Z)=\max\\{0,\phi(Z)-\tau\\}^{r}$ or
$\ell(Z)=\max\\{0,|\phi(Z)|-\tau\\}^{r}$; and $\phi$, $L_{\phi}$ take one of
the following forms.

  1. (a)

(Nonparametric) Given $\beta\in\mathfrak{L}^{2}[0,1]$ and let
$\phi:\mathfrak{L}^{2}[0,1]\times\mathbb{R}\rightarrow\mathbb{R}$ defined as

$\phi\colon(x,y)\mapsto y-\int\limits_{0}^{1}x(t)\beta(t)\mathrm{d}t,$

for any $(x,y)\in\mathfrak{L}^{2}[0,1]\times\mathbb{R}$. Let
$L_{\phi}=\left(\int_{0}^{1}|\beta(t)|^{2}\mathrm{d}t\right)^{1/2}$.

  2. (b)

(Parametric) Let $\beta\in\mathbb{R}^{n}$,
$\\{{\boldsymbol{g}}_{1},\cdots,{\boldsymbol{g}}_{n}\\}\subset\mathfrak{L}^{2}[0,1]$.
Define $\phi:\mathfrak{L}^{2}[0,1]\times\mathbb{R}\rightarrow\mathbb{R}$ as

$\phi\colon(x,y)\mapsto
y-\int\limits_{0}^{1}x(t)\sum_{j=1}^{n}\beta_{j}{\boldsymbol{g}}_{j}(t)\mathrm{d}t,$

for any $(x,y)\in\mathfrak{L}^{2}[0,1]\times\mathbb{R}$. Let
$L_{\phi}=\left(\int_{0}^{1}|\sum_{j=1}^{n}\beta_{j}{\boldsymbol{g}}_{j}(t)|^{2}\mathrm{d}t\right)^{1/2}$.

###  4.2 Applications to nonlinear regression loss functions

Next, we move on to study nonlinear regression problems.

######  Proposition 4.2 (Nonlinear regression loss).

Let $\mathcal{Z}$ be a (finite or infinite dimensional) real vector space.
Suppose that
$\left\llbracket\cdot\right\rrbracket\colon\mathcal{Z}\rightarrow[0,\infty]$
is absolutely homogeneous and proper,
$\phi\colon\mathcal{Z}\rightarrow\mathbb{R}$ is linear,
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$ and

$L_{\phi}\coloneqq\sup_{z\in\mathcal{Z}}\left\\{|\phi(z)|\mid\left\llbracket
z\right\rrbracket=1\right\\}\in[0,+\infty).$

In addition, given $\delta>0$, suppose a univariate function
$h\colon\mathbb{R}\rightarrow\mathbb{R}$ satisfies the following assumptions:

  1. (H1)

$h$ is globally $L_{h}$-Lipschitz on $\mathbb{R}$ with $L_{h}>0$;

  2. (H2)

for any $t_{0}\in\mathbb{R}$, there exists $\\{t_{k}\\}_{k=1}^{\infty}$ such
that $|t_{k}|\in[L_{\phi}\delta,\infty)\setminus\\{0\\}$ and

$\lim_{k\rightarrow\infty}\frac{h(t_{k}+t_{0})-h(t_{0})}{|t_{k}|}=L_{h}.$

Then the function $\psi\colon\mathcal{Z}\rightarrow\mathbb{R}$ defined by
$\psi(z)=h(\phi(z))$ is $(L_{h}L_{\phi},d)$-Lipschitz at $\mathcal{Z}$, where
the cost function $d:\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$ is
defined as $d(z^{\prime},z)\coloneqq\left\llbracket
z^{\prime}-z\right\rrbracket$ for any $z^{\prime},z\in\mathcal{Z}$. Moreover,
$\psi$ also satisfies Assumptions (A1) and (A2) at $\mathcal{Z}$ with $\delta$
if $L_{\phi}>0$.

Proof. By Proposition 4.1, one has that $\phi$ is $(L_{\phi},d)$-Lipschitz at
$\mathcal{Z}$. According to (H1), for any $z^{\prime},z\in\mathcal{Z}$, we
have

$\begin{array}[]{ll}\left|\psi(z^{\prime})-\psi(z)\right|=\left|h(\phi(z^{\prime}))-h(\phi(z))\right|\leq
L_{h}\left|\phi(z^{\prime})-\phi(z)\right|\leq
L_{h}L_{\phi}d(z^{\prime},z).\end{array}$

Hence, $\psi$ is $(L_{h}L_{\phi},d)$-Lipschitz at $\mathcal{Z}$.

Next, suppose that $L_{\phi}>0$. Then we have $\psi$ satisfies Assumption (A1)
at $\mathcal{Z}$ with $\delta$. For any $\hat{z}\in\mathcal{Z}$, denote
$t_{0}=\phi\left(\hat{z}\right)$, then we have $\psi(\hat{z})=h(t_{0})$. Let
$0<\epsilon<L_{h}L_{\phi}$ be any scalar. As in the proof of Proposition 4.1,
there exists $\tilde{v}\in\mathcal{Z}$ such that
$\left\llbracket\tilde{v}\right\rrbracket=1$ and
$0<L_{\phi}-\frac{\epsilon}{2L_{h}}<\phi(\tilde{v})\leq L_{\phi}$. We know
from (H2) that there exists $|\tilde{t}|\geq L_{\phi}\delta$ such that

$\left|\frac{h(\tilde{t}+t_{0})-h(t_{0})}{|\tilde{t}|}-L_{h}\right|\leq\frac{\epsilon}{2\phi(\tilde{v})}.$

Since $h$ is globally $L_{h}$-Lipschitz continuous, we have
$\left|h(\tilde{t}+t_{0})-h(t_{0})\right|\leq L_{h}|\tilde{t}|$. Thus, we have

$\begin{array}[]{ll}\left|\frac{h(\tilde{t}+t_{0})-h(t_{0})}{|\tilde{t}|}-L_{h}\right|=L_{h}-\frac{h(\tilde{t}+t_{0})-h(t_{0})}{|\tilde{t}|}\leq\frac{\epsilon}{2\phi(\tilde{v})},\end{array}$

which implies that

$h(\tilde{t}+t_{0})-h(t_{0})\geq\left(L_{h}-\frac{\epsilon}{2\phi(\tilde{v})}\right)|\tilde{t}|.$

Let $\tilde{z}\coloneqq\hat{z}+\tilde{t}\tilde{v}/\phi(\tilde{v})$. Then we
have

$d\left(\tilde{z},\hat{z}\right)=\left\llbracket\frac{\tilde{t}}{\phi(\tilde{v})}\tilde{v}\right\rrbracket=\frac{|\tilde{t}|}{\phi(\tilde{v})}\geq\frac{|\tilde{t}|}{L_{\phi}}\geq\delta,$

and

$\begin{array}[]{lllll}&\psi(\tilde{z})-\psi(\hat{z})=h\left(\phi\left(\hat{z}+\frac{\tilde{t}\tilde{v}}{\phi(\tilde{v})}\right)\right)-h(\phi(\hat{z}))=h(t_{0}+\tilde{t})-h(t_{0})\\\
&\geq\left(L_{h}-\frac{\epsilon}{2\phi(\tilde{v})}\right)|\tilde{t}|=\left(L_{h}\phi(\tilde{v})-\frac{\epsilon}{2}\right)\frac{|\tilde{t}|}{\phi(\tilde{v})}\\\
&\geq\left(L_{h}\left(L_{\phi}-\frac{\epsilon}{2L_{h}}\right)-\frac{\epsilon}{2}\right)\frac{|\tilde{t}|}{\phi(\tilde{v})}=(L_{\phi}L_{h}-\epsilon)d(\tilde{z},\hat{z}).\end{array}$

Therefore, $\psi$ satisfies Assumption (A2) at $\mathcal{Z}$ with the given
$\delta$. This completes the proof. $\square$

######  Remark 4.2.

Proposition 4.2 characterizes a certain case where $\ell$ is nonlinear but
Theorem 3.2 still holds true. In this case, the loss function $\ell$ can be
written as a composition of a linear map $\phi$ and a univariate
$L_{h}$-Lipschitz function $h$, where the Lipschitz constant $L_{h}$ is
approximately attainable on $[L_{\phi}\delta,\infty)\setminus\\{0\\}$. In
particular, if $L_{h}$ is approximately attainable at infinity, then
Assumption (H2) holds regardless of the choice of $\phi$, as long as
$L_{\phi}$ is finite.

Thanks to Proposition 4.2, Theorem 3.1(c) and Theorem 3.2, we now can cover a
broader class of nonlinear regression loss functions in the following
corollary.

######  Corollary 4.2.

Under the setting of Proposition 4.2, for any empirical distribution
$\mathbb{P}_{N}$ on $\mathcal{Z}$, the following equivalence holds for any
given $\delta>0$:

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[h(\phi(Z))]=\mathrm{E}_{\mathbb{P}_{N}}[h(\phi(Z))]+L_{h}L_{\phi}\delta,$

where
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$.

We give the following example as an application of Corollary 4.2 to show the
equivalence of the worst case loss quantity in the WDRO problem and the
regularization scheme for nonlinear regression loss functions, including the
log-cosh loss, the quantile loss and Huber loss (Huber 1973, Koenker and
Bassett Jr 1978, Koenker and Hallock 2001, Wang et al. 2020), whose proof can
be found in Appendix B.5.

######  Example 4.3.

Given any $\delta>0$, $\beta\in\mathbb{R}^{n}$ and any empirical distribution
$\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\mathbb{R}$, we have

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[h(Y-\langle\beta,X\rangle)]=\mathrm{E}_{\mathbb{P}_{N}}[h(Y-\langle\beta,X\rangle)]+L_{\phi}\delta,$

where
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z}\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$
and $h$ takes one of the following forms:

  1. (a)

log-cosh loss: $h\colon t\mapsto\log(\cosh(t))$;

  2. (b)

Huber loss: $h\colon t\mapsto\begin{cases}\frac{1}{2}t^{2}&\text{if }|t|\leq
1,\\\ |t|-\frac{1}{2}&\text{otherwise};\end{cases}$

  3. (c)

quantile loss: $h\colon t\mapsto\begin{cases}\gamma t&\text{if }t\geq 0,\\\
-t&\text{otherwise},\end{cases}$ with $\gamma\in(0,1)$;

and $d(\cdot,\cdot)$ and $L_{\phi}$ take one of the following forms

  1. (i)

$d((x^{\prime},y^{\prime}),(x,y))=\|[x^{\prime}-x;y^{\prime}-y]\|_{\mathbb{R}^{n+1}}$
and $L_{\phi}=\|[-\beta;1]\|_{\mathbb{R}^{n+1},*}$;

  2. (ii)

$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
and $L_{\phi}=\|\beta\|_{\mathbb{R}^{n},*}$.

###  4.3 A special regression model

In this subsection, we introduce an interesting example wherein our results
can be applied to the cases when the cost function $d(\cdot,\cdot)$ is
nonconvex, not positive definite and the weak Lipschitz constant is not in the
popular form of the norm of the regression vector $\beta$. In Shafieezadeh-
Abadeh et al. (2019, Remark 19), it has been pointed out that the Tikhonov-
regularized problem with respect to a Lipschitz loss function can not be
explained by a distributionally robust learning problem. In addition, it has
been shown in Li et al. (2022) that the Tikhonov-regularized problem with
respect to the squared loss has an equivalence interpretation as a martingale
DRO problem with respect to the quadratic cost
$d(z^{\prime},z)=\|z^{\prime}-z\|^{2}$. Nevertheless, according to Example
4.4, whose proof is in Appendix B.6, we show that with the notion of the weak
Lipschitz property in Definition 3.2, the Tikhonov-regularized squared loss
problem is equivalent to a WDRO problem swith a specifically designed cost
function $d(\cdot,\cdot)$ on the sample space. In particular, unlike
$d(z^{\prime},z)=\|z^{\prime}-z\|^{2}$, our designed cost function is
nonconvex and not positive definite.

######  Example 4.4 (Ridge linear ordinary regression (Horel 1962, Hoerl and
Kennard 1970)).

For any
$z^{\prime}=(x^{\prime},y^{\prime}),z=(x,y)\in\mathbb{R}^{n}\times\mathbb{R}$,
define $d(z^{\prime},z)=\|z^{\prime}-z\|_{2}\|z^{\prime}+z\|_{2}$. Given any
$\delta>0$, $\beta\in\mathbb{R}^{n}$ and any empirical distribution
$\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\mathbb{R}$. For
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$,
we have

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[(Y+\langle\beta,X\rangle)^{2}]=\mathrm{E}_{\mathbb{P}_{N}}[(Y+\langle\beta,X\rangle)^{2}]+\|\beta\|_{2}^{2}\delta+\delta.$

###  4.4 Applications to classification loss functions

Next we turn our attention to linear-type classification loss functions. For
the detailed proof of the following proposition, see Appendix A.3.

######  Proposition 4.3 (Linear classification loss).

Let $\mathcal{Z}=\mathcal{X}\times\\{-1,1\\}$, where $\mathcal{X}$ is a
(finite or infinite dimensional) real vector space. Suppose that
$\left\llbracket\cdot\right\rrbracket\colon\mathcal{X}\rightarrow[0,\infty]$
is absolutely homogeneous and proper,
$\phi\colon\mathcal{X}\rightarrow\mathbb{R}$ is linear,
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$, and

$L_{\phi}\coloneqq\sup_{x\in\mathcal{X}}\left\\{|\phi(x)|\mid\left\llbracket
x\right\rrbracket=1\right\\}\in[0,+\infty).$

Let the cost function $d:\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$ be
defined as $d(z^{\prime},z)\coloneqq\left\llbracket
x^{\prime}-x\right\rrbracket+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
and the function $\psi:\mathcal{Z}\rightarrow\mathbb{R}$ be defined as
$\psi(z)=y\cdot\phi(x)$ for any
$z^{\prime}=(x^{\prime},y^{\prime}),z=(x,y)\in\mathcal{Z}$. Then for any
$\tau\in\mathbb{R}$, the functions $\left|\tau-\psi\right|$ and
$\max\\{0,\tau-\psi\\}$ are $(L_{\phi},d)$-Lipschitz at $\mathcal{Z}$.
Furthermore, they also satisfy Assumptions (A1), (A2) and (B) at $\mathcal{Z}$
for any $\delta>0$ if $L_{\phi}>0$.

Together with Theorem 3.1(c), Theorem 3.2 and Theorem 3.3, we have the
following corollary on the equivalence (5) for linear-type classification loss
functions.

######  Corollary 4.3.

Under the setting of Proposition 4.3, given any scalars $r\geq 1$, $\delta>0$
and any empirical distribution $\mathbb{P}_{N}$ on $\mathcal{Z}$. We have that
for any $\tau\in\mathbb{R}$,

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z)]\right)^{\frac{1}{r}}+L_{\phi}\delta\right)^{r},$

where $\ell(Z)=\left|\tau-\phi(Z)\right|^{r}$ or
$\ell(Z)=\max\\{0,\tau-\phi(Z)\\}^{r}$.

Now we give an example of the higher-order hinge loss binary classification
and the higher-order support vector machine classification, which is an
application of the above corollary. The detailed proof can be found in
Appendix B.7. Note that the second conclusion in Blanchet et al. (2019,
Theorem 2) can be viewed as a special case of this example with $r=1$.

######  Example 4.5 (Higher-order hinge loss /Higher-order support vector
machine).

For any $(x^{\prime},y^{\prime}),(x,y)\in\mathbb{R}^{n}\times\\{-1,1\\}$,
define the cost function
$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$.
Given any $\delta>0$, $\beta\in\mathbb{R}^{n}$ and any empirical distribution
$\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\mathbb{R}$, we have

$\sup_{\mathbb{P}\in\mathfrak{M}_{r}}\mathrm{E}_{\mathbb{P}}[\ell(Z;\beta)]=\left(\left(\mathrm{E}_{\mathbb{P}_{N}}[\ell(Z;\beta)]\right)^{\frac{1}{r}}+\|\beta\|_{\mathbb{R}^{n},*}\delta\right)^{r},$

where
$\mathfrak{M}_{r}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$
and $\ell(Z;\beta)$ takes one of the following forms:

  1. (a)

$\ell(Z;\beta)=\left|1-Y\cdot\langle\beta,X\rangle\right|^{r}$;

  2. (b)

$\ell(Z;\beta)=\left(1-Y\cdot\langle\beta,X\rangle\right)_{+}^{r}$.

Then, we consider the applications of our results to nonlinear classification
loss functions in the following proposition, whose proof can be found in
Appendix A.4.

######  Proposition 4.4 (Nonlinear classification loss).

Let $\mathcal{Z}=\mathcal{X}\times\\{-1,1\\}$, where $\mathcal{X}$ is a
(finite or infinite dimensional) real vector space. Suppose that
$\left\llbracket\cdot\right\rrbracket\colon\mathcal{X}\rightarrow[0,\infty]$
is absolutely homogeneous and proper,
$\phi\colon\mathcal{X}\rightarrow\mathbb{R}$ is linear,
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$, and

$L_{\phi}\coloneqq\sup_{x\in\mathcal{X}}\left\\{|\phi(x)|\mid\left\llbracket
x\right\rrbracket=1\right\\}\in[0,+\infty).$

Let the cost function $d:\mathcal{Z}\times\mathcal{Z}\rightarrow[0,\infty]$ be
defined as $d(z^{\prime},z)\coloneqq\left\llbracket
x^{\prime}-x\right\rrbracket+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$
and the function $\psi:\mathcal{Z}\rightarrow\mathbb{R}$ be defined as
$\psi(z)=h(y\cdot\phi(x))$ for any
$z^{\prime}=(x^{\prime},y^{\prime}),z=(x,y)\in\mathcal{Z}$. Given $\delta>0$
and suppose $h$ satisfies Assumptions (H1-H2) in Proposition 4.2, then $\psi$
is $(L_{h}L_{\phi},d)$-Lipschitz at $\mathcal{Z}$. Moreover, $\psi$ also
satisfies Assumptions (A1) and (A2) at $\mathcal{Z}$ with $\delta$ if
$L_{\phi}>0$.

The following corollary allows us to establish the equivalence of the worst-
case loss quantity in the WDRO problem and the regularization scheme for
nonlinear classification loss functions, based on Proposition 4.4, Theorem
3.1(c) and Theorem 3.2.

######  Corollary 4.4.

Under the setting of Proposition 4.4, for any empirical distribution
$\mathbb{P}_{N}$ on $\mathcal{Z}$, the following equivalence holds for any
given $\delta>0$:

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[h(Y\cdot\phi(X))]=\mathrm{E}_{\mathbb{P}_{N}}[h(Y\cdot\phi(X))]+L_{h}L_{\phi}\delta.$

where
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$.

Nonlinear classification loss functions have gained widespread popularity due
to their efficacy in handling real-world datasets where the relationships
between the variables are intricate and nonlinear. We give the following
example to show that our results are applicable in many popular instances,
whose proof can be found in Appendix B.8. Here, the log-exponential loss
example is equivalent to the first conclusion in Blanchet et al. (2019,
Theorem 2) and a tractable reformulation of the worst-case loss quantity with
respect to the smooth hinge loss function has also been studied in
Shafieezadeh-Abadeh et al. (2019, Corollary 16).

######  Example 4.6.

For any $(x^{\prime},y^{\prime}),(x,y)\in\mathbb{R}^{n}\times\\{-1,1\\}$,
define the cost function
$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$.
Given any $\delta>0$, $\beta\in\mathbb{R}^{n}$ and any empirical distribution
$\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\\{-1,1\\}$. We have

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[h(Y\cdot\langle\beta,X\rangle)]=\mathrm{E}_{\mathbb{P}_{N}}[h(Y\cdot\langle\beta,X\rangle)]+\|\beta\|_{\mathbb{R}^{n},*}\delta,$

where
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$
and $h$ takes one of the following forms.

  1. (a)

Log-exponential loss: $h\colon t\mapsto\log(1+\exp(-t))$;

  2. (b)

Smooth hinge loss: $h\colon t\mapsto\begin{cases}0&\text{if }t\geq 1,\\\
\frac{1}{2}(1-t)^{2}&\text{if }0<t<1,\\\
\frac{1}{2}-t&\text{otherwise};\end{cases}$

  3. (c)

Truncated pinball loss (Shen et al. 2017): $h\colon
t\mapsto\begin{cases}1-t&\text{if }t\leq 1,\\\ \tau_{1}(t-1)&\text{if
}1<t<\tau_{2}+1,\\\ \tau_{1}\tau_{2}&\text{otherwise},\end{cases}$
where $\tau_{1}\in[0,1],\tau_{2}\geq 0$ are two given constants.

##  5 Generalization to risk measure

In this section, we shall generalize the expectation function in the
equivalence (5) to a risk measure, which might be nonlinear in distribution.

Given any cost function $d(\cdot,\cdot)$ and any scalar $r\geq 1$, it can be
easily seen that $\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P})=0$ for any
$\mathbb{P}\in\mathcal{P}(\mathcal{Z})$ by choosing
$\pi=\mathbb{P}\otimes\mathbb{P}$. In addition, we use the convention that
$\mathcal{W}_{d,r}(\mathbb{P},\mathbb{Q})=\infty$ when
$\Pi(\mathbb{P},\mathbb{Q})=\emptyset$. Then we can see that
$\mathcal{W}_{d,r}(\cdot,\cdot)$ is a cost function on
$\mathcal{P}(\mathcal{Z})$. Moreover, one can define the weak Lipschitz
property on $\mathcal{P}(\mathcal{Z})$ with respect to the cost function
$\mathcal{W}_{d,r}(\cdot,\cdot)$. Inspired by Wu et al. (2022), we propose the
following sufficient condition under which a supremum on the Wasserstein
neighborhood of $\mathbb{P}_{N}$ and an infimum on $\mathbb{R}$ are
interchangeable.

######  Theorem 5.1.

Given any empirical distribution $\mathbb{P}_{N}$ on
$\mathcal{P}(\mathcal{Z})$ and any given $r\geq 1$. Suppose that a function
$\mathcal{F}\colon\mathcal{P}(\mathcal{Z})\times\mathbb{R}\rightarrow\mathbb{R}$
satisfies the following conditions:

  * •

$\mathcal{F}$ on $\mathcal{P}(\mathcal{Z})\times\mathbb{R}$ is concavelike in
$\mathcal{P}(\mathcal{Z})$, i.e., for any
$\mathbb{P}_{1},\mathbb{P}_{2}\in\mathcal{P}(\mathcal{Z})$ and $0\leq\nu\leq
1$, there exists $\mathbb{P}\in\mathcal{P}(\mathcal{Z})$ such that for all
$t\in\mathbb{R}$,

$\nu\mathcal{F}(\mathbb{P}_{1},t)+(1-\nu)\mathcal{F}(\mathbb{P}_{2},t)\leq\mathcal{F}(\mathbb{P},t);$

  * •

$\mathcal{F}(\mathbb{P},\cdot)$ is convex, coercive and lower semi-continuous
for each $\mathbb{P}\in\mathcal{P}(\mathcal{Z})$;

  * •

$\mathcal{F}(\cdot,t)$ is
$\left(L_{\mathcal{F}},\mathcal{W}_{d,r}\right)$-Lipschitz at
$\\{\mathbb{P}_{N}\\}$ for some $L_{\mathcal{F}}\in(0,\infty)$ which does not
depend on $t$.

Then we have that for any $\delta>0$,

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t)=\inf_{t\in\mathbb{R}}\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathcal{F}(\mathbb{P},t).$

Proof. Since $\mathcal{F}(\cdot,t)$ is
$\left(L_{\mathcal{F}},\mathcal{W}_{d,r}\right)$-Lipschitz at
$\\{\mathbb{P}_{N}\\}$, for any
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})\leq\delta$, we have for
any $t\in\mathbb{R}$,

$\displaystyle\left|\mathcal{F}(\tilde{\mathbb{P}},t)-\mathcal{F}(\mathbb{P}_{N},t)\right|\leq
L_{\mathcal{F}}\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})\leq
L_{\mathcal{F}}\delta.$ (8)

As $\mathcal{F}(\mathbb{P}_{N},\cdot)$ is convex and coercive, it admits at
least one minimizer. Let $t_{N}$ be a minimizer of
$\mathcal{F}(\mathbb{P}_{N},\cdot)$, i.e.,
$t_{N}\in\arg\min_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P}_{N},t)$. Since
$\mathcal{F}(\mathbb{P}_{N},\cdot)$ is coercive, there exists $\Delta_{N}>0$
such that for any $t\notin[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]$,

$\mathcal{F}(\mathbb{P}_{N},t)\geq\mathcal{F}(\mathbb{P}_{N},t_{N})+3L_{\mathcal{F}}\delta.$

This together with (8) implies that for any
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})\leq\delta$ and any
scalar $t\notin[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]$, it holds that

$\displaystyle\mathcal{F}(\tilde{\mathbb{P}},t)\geq\mathcal{F}(\mathbb{P}_{N},t)-L_{\mathcal{F}}\delta\geq\mathcal{F}(\mathbb{P}_{N},t_{N})+2L_{\mathcal{F}}\delta.$
(9)

On the other hand, (8) also implies that

$\displaystyle\mathcal{F}(\tilde{\mathbb{P}},t_{N})\leq\mathcal{F}(\mathbb{P}_{N},t_{N})+L_{\mathcal{F}}\delta.$
(10)

Thus, according to (9) and (10), we have for any
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,r}(\tilde{\mathbb{P}},\mathbb{P}_{N})\leq\delta$,

$\inf_{t\in\mathbb{R}}\mathcal{F}(\tilde{\mathbb{P}},t)=\inf_{t\in[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]}\mathcal{F}(\tilde{\mathbb{P}},t).$

This further means that

$\begin{array}[]{ll}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf\limits_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t)=\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf\limits_{t\in[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]}\mathcal{F}(\mathbb{P},t).\end{array}$

By Sion (1958, Theorem 4.2’), since $\mathcal{F}(\cdot,\cdot)$ is a concave-
convexlike on
$\mathcal{P}(\mathcal{Z})\times[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]$ and
$\mathcal{F}(\mathbb{P},\cdot)$ is lower semi-continuous for each
$\mathbb{P}\in\mathcal{P}(\mathcal{Z})$ on the compact set
$[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]$, we have

$\begin{array}[]{ll}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf\limits_{t\in[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]}\mathcal{F}(\mathbb{P},t)=\inf\limits_{t\in[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathcal{F}(\mathbb{P},t).\end{array}$

Therefore, it holds that

$\begin{array}[]{lll}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf\limits_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t)=\inf\limits_{t\in[t_{N}-\Delta_{N},t_{N}+\Delta_{N}]}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathcal{F}(\mathbb{P},t)\geq\inf\limits_{t\in\mathbb{R}}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathcal{F}(\mathbb{P},t).\end{array}$

As it is obvious that

$\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t)\leq\inf_{t\in\mathbb{R}}\sup_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathcal{F}(\mathbb{P},t),$

we complete the proof. $\square$

Based on the above theorem, we give the following corollary, which generalizes
the expectation function in the equivalence (5) to a risk measure.

######  Corollary 5.1.

Given any scalar $\alpha\in(0,1)$. Let $d(\cdot,\cdot)$ be a cost function on
$\mathcal{Z}\times\mathcal{Z}$. Suppose the function
$G:\mathcal{Z}\rightarrow\mathbb{R}$ is $(L_{G},d)$-Lipschitz at $\mathcal{Z}$
with $L_{G}\in(0,\infty)$. Let
$\mathcal{Z}_{N}\coloneqq\\{Z^{(1)},\dots,Z^{(N)}\\}\subset\mathcal{Z}$ be a
given dataset and
$\mathbb{P}_{N}\coloneqq\sum_{i=1}^{N}\mu_{i}{\boldsymbol{\chi}}_{\\{Z^{(i)}\\}}\in\mathcal{P}(\mathcal{Z})$
be the corresponding empirical distribution. Then we have the following
conclusions.

  1. (a)

Denote
$\mathfrak{M}_{1}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$.
Given $\delta>0$, suppose that for all $t\in\mathbb{R}$,

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}]=\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}]+L_{G}\delta.$

Then it holds that

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(G(Z))=\mathrm{CVaR}_{\alpha}^{\mathbb{P}_{N}}(G(Z))+\frac{1}{1-\alpha}L_{G}\delta.$

  2. (b)

Given $r\geq 1$, let
$\mathfrak{M}_{r}\coloneqq\left\\{\mathbb{P}\in\mathcal{P}(\mathcal{Z})\mid\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta\right\\}$.
Given $\delta>0$, suppose that for any $t\in\mathbb{R}$,

$\sup_{\mathbb{P}\in\mathfrak{M}_{r}}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}^{r}]=\left[\left(\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}^{r}]\right)^{\frac{1}{r}}+L_{G}\delta\right]^{r}.$

Then it holds that

$\begin{array}[]{ll}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{r}}\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\left(\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}^{r}]\right)^{\frac{1}{r}}\Big{\\}}=\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\left(\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}^{r}]\right)^{\frac{1}{r}}\Big{\\}}+\frac{1}{1-\alpha}L_{G}\delta.\end{array}$

Proof. (a) Define the function
$\mathcal{F}\colon\mathcal{P}(\mathcal{Z})\times\mathbb{R}\rightarrow\mathbb{R}$
by

$\mathcal{F}(\mathbb{P},t)\coloneqq
t+\frac{1}{1-\alpha}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}].$

By the definition of $\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(\cdot)$, we have
that

$\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(G(Z))=\inf_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t).$

Now we verify that the function $\mathcal{F}(\cdot,\cdot)$ satisfies the three
conditions in Theorem 5.1. It is easy to verify that the first two conditions
hold. Next we turn to the third condition. Fix $t\in\mathbb{R}$ and any
$\tilde{\mathbb{P}}\in\mathcal{P}(\mathcal{Z})$ such that
$\mathcal{W}_{d,1}(\tilde{\mathbb{P}},\mathbb{P}_{N})<\infty$. For any
$\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$, we have

$\begin{array}[]{lllllll}\left|\mathcal{F}(\tilde{\mathbb{P}},t)-\mathcal{F}(\mathbb{P}_{N},t)\right|&=\frac{1}{1-\alpha}\left|\mathrm{E}_{\tilde{\mathbb{P}}}[\left(G(Z)-t\right)_{+}]-\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}]\right|\\\
&=\frac{1}{1-\alpha}\Big{|}\int\limits_{\mathcal{Z}\times\mathcal{Z}}\left(G(z^{\prime})-t\right)_{+}\mathrm{d}\tilde{\pi}(z^{\prime},z)-\int\limits_{\mathcal{Z}\times\mathcal{Z}}\left(G(z)-t\right)_{+}\mathrm{d}\tilde{\pi}(z^{\prime},z)\Big{|}\\\
&\leq\frac{1}{1-\alpha}\int\limits_{\mathcal{Z}\times\mathcal{Z}}\left|\left(G(z^{\prime})-t\right)_{+}-\left(G(z)-t\right)_{+}\right|\mathrm{d}\tilde{\pi}(z^{\prime},z)\\\
&\leq\frac{1}{1-\alpha}\int\limits_{\mathcal{Z}\times\mathcal{Z}}\left|G(z^{\prime})-G(z)\right|\mathrm{d}\tilde{\pi}(z^{\prime},z)\\\
&\leq\frac{L_{G}}{1-\alpha}\int\limits_{\mathcal{Z}\times\mathcal{Z}}d(z,z^{\prime})\mathrm{d}\tilde{\pi}(z^{\prime},z).\end{array}$

By taking infimum over all
$\tilde{\pi}\in\Pi(\tilde{\mathbb{P}},\mathbb{P}_{N})$, we can see that

$\left|\mathcal{F}(\tilde{\mathbb{P}},t)-\mathcal{F}(\mathbb{P}_{N},t)\right|\leq\frac{L_{G}}{1-\alpha}\mathcal{W}_{d,1}(\tilde{\mathbb{P}},\mathbb{P}_{N}),$

which means that $\mathcal{F}(\cdot,t)$ is
$\left(\frac{L_{G}}{1-\alpha},\mathcal{W}_{d,1}\right)$-Lipschitz at
$\\{\mathbb{P}_{N}\\}$. Then according to Theorem 5.1, for any $\delta>0$, we
have that

$\begin{array}[]{ll}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(G(Z))&=\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\inf\limits_{t\in\mathbb{R}}\mathcal{F}(\mathbb{P},t)=\inf\limits_{t\in\mathbb{R}}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\mathcal{F}(\mathbb{P},t).\end{array}$

Thus, it holds that for any $\delta>0$,

$\begin{array}[]{lllll}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(G(Z))&=\inf\limits_{t\in\mathbb{R}}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\Big{\\{}t+\frac{1}{1-\alpha}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}]\Big{\\}}\\\
&=\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\sup\limits_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}]\Big{\\}}\\\
&=\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}]+\frac{1}{1-\alpha}L_{G}\delta\Big{\\}}\\\
&=\mathrm{CVaR}_{\alpha}^{\mathbb{P}_{N}}(G(Z))+\frac{1}{1-\alpha}L_{G}\delta,\end{array}$

where the third equality following from the fact that for all
$t\in\mathbb{R}$,

$\sup_{\mathbb{P}\in\mathfrak{M}_{1}}\mathrm{E}_{\mathbb{P}}[\left(G(Z)-t\right)_{+}]=\mathrm{E}_{\mathbb{P}_{N}}[\left(G(Z)-t\right)_{+}]+L_{G}\delta.$

(b) The proof of this part is similar to the one for part (a). We omit the
details here. $\square$

As applications of the above corollary, we give the following three examples,
stating the equivalence between the worst case loss quantity in the WDRO
problem and the regularization scheme for $\nu$-support vector regression,
$\nu$-support vector machine, and higher moment coherent risk measures. The
proof of these examples can be found in Appendices B.9-B.11.

######  Example 5.1 ($\nu$-support vector regression (Schölkopf et al. 1998)).

For any $(x^{\prime},y^{\prime}),(x,y)\in\mathbb{R}^{n}\times\mathbb{R}$,
define the cost function
$d((x^{\prime},y^{\prime}),(x,y))=\|(x^{\prime},y^{\prime})-(x,y)\|_{\mathbb{R}^{n+1}}$.
Given $\alpha\in(0,1)$, $\delta>0$, $\beta\in\mathbb{R}^{n}$ and any empirical
distribution $\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\mathbb{R}$, we have

$\begin{array}[]{ll}\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(\left|Y-\langle\beta,X\rangle\right|)=\mathrm{CVaR}_{\alpha}^{\mathbb{P}_{N}}(\left|Y-\langle\beta,X\rangle\right|)+\frac{1}{1-\alpha}\|[-\beta;1]\|_{\mathbb{R}^{n+1},*}\delta.\end{array}$

######  Example 5.2 ($\nu$-support vector machine (Schölkopf et al. 2000)).

For any $(x^{\prime},y^{\prime}),(x,y)\in\mathbb{R}^{n}\times\mathbb{R}$,
define the cost function
$d((x^{\prime},y^{\prime}),(x,y))=\|x^{\prime}-x\|_{\mathbb{R}^{n}}+{\boldsymbol{\delta}}_{\\{0\\}}(y^{\prime}-y)$.
Given any $\alpha\in(0,1)$, $\delta>0$, $\beta\in\mathbb{R}^{n}$ and any
empirical distribution $\mathbb{P}_{N}$ on $\mathbb{R}^{n}\times\mathbb{R}$,
we have

$\begin{array}[]{ll}\sup_{\mathbb{P}\colon\mathcal{W}_{d,1}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{CVaR}_{\alpha}^{\mathbb{P}}(-Y\cdot\langle\beta,X\rangle)=\mathrm{CVaR}_{\alpha}^{\mathbb{P}_{N}}(-Y\cdot\langle\beta,X\rangle)+\frac{1}{1-\alpha}\|\beta\|_{\mathbb{R}^{n},*}\delta.\end{array}$

######  Example 5.3 (Higher moment coherent risk measures (Krokhmal 2007)).

For any $z^{\prime},z\in\mathbb{R}^{n}$, define the cost function
$d(z^{\prime},z)=\|z^{\prime}-z\|_{\mathbb{R}^{n}}$. Given $\alpha\in(0,1)$,
$\delta>0$, $r\geq 1$, $\beta\in\mathbb{R}^{n}$ and any empirical distribution
$\mathbb{P}_{N}$ on $\mathbb{R}^{n}$, we have

$\begin{array}[]{ll}\sup\limits_{\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\left(\mathrm{E}_{\mathbb{P}}[\left(\langle\beta,Z\rangle-t\right)_{+}^{r}]\right)^{\frac{1}{r}}\Big{\\}}=\inf\limits_{t\in\mathbb{R}}\Big{\\{}t+\frac{1}{1-\alpha}\left(\mathrm{E}_{\mathbb{P}_{N}}[\left(\langle\beta,Z\rangle-t\right)_{+}^{r}]\right)^{\frac{1}{r}}\Big{\\}}+\frac{1}{1-\alpha}\|\beta\|_{\mathbb{R}^{n},*}\delta.\end{array}$

##  6 Conclusion

In this paper, we studied a variety of the Wasserstein distributionally robust
optimization problems and proposed certain conditions to quantify the
corresponding worst-case loss quantity. Specifically, we drew connections and
established the equivalence between the worst-case loss quantity and its
associated regularization scheme. Our proposed results generalized the
existing results from various perspectives, particularly by relaxing the
required assumptions on the loss function and the cost function. Moreover, our
constructive approaches and elementary proofs directly characterized the
closed forms of the approximate worst-case distributions. Extensive examples
demonstrated that our theoretical results can be applied to various problems,
including regression, classification and risk measure problems.

Following the presented results, there are some possible topics for future
studies on the WDRO problems. For example, by similar arguments as in our
proposed weak Lipschitz property, the notion of the growth rate in Gao and
Kleywegt (2023, Lemma 2) can be readily extended to be dependent on the cost
function and its variables. On the other hand, recent works on the WDRO
problems such as Blanchet and Murthy (2019), Zhang et al. (2022), Gao and
Kleywegt (2023), suggest that further assumptions might be required when the
empirical distribution is not discrete. In summary, we hope our results can
inspire more fruitful studies on the behavior of the worst-case loss quantity
and the applications of the associated regularization scheme in the machine
learning and operations research.

## Acknowledgement

Meixia Lin is supported by The Singapore University of Technology and Design
under MOE Tier 1 Grant SKI 2021_02_08. Kim-Chuan Toh is supported by the
Ministry of Education, Singapore, under its Academic Research Fund Tier 3
grant call (MOE-2019-T3-1-010).

##  Appendix A Proof of auxiliary results

###  A.1 Proof of $\mathcal{S}\leq\mathcal{I}$

We can see that

$\begin{array}[]{lllllllllllll}&\mathcal{S}=\sup_{Z^{\prime}\sim\mathbb{P}\colon\mathcal{W}_{d,r}(\mathbb{P},\mathbb{P}_{N})\leq\delta}\mathrm{E}_{\mathbb{P}}[\ell(Z^{\prime};\beta)]\\\
&=\sup_{Z^{\prime}\sim\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\ \inf_{\rho\geq
0}\Big{\\{}\mathrm{E}_{\mathbb{P}}[\ell(Z^{\prime};\beta)]\\\
&\quad+\rho\left(\delta^{r}-\mathcal{W}^{r}_{d,r}(\mathbb{P},\mathbb{P}_{N})\right)\Big{\\}}\\\
&=\sup_{Z^{\prime}\sim\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\ \inf_{\rho\geq
0}\Big{\\{}\mathrm{E}_{\mathbb{P}}[\ell(Z^{\prime};\beta)]\\\
&\quad+\rho\left(\delta^{r}-\inf_{\pi\in\Pi(\mathbb{P},\mathbb{P}_{N})}\left\\{\mathrm{E}_{(Z^{\prime},Z)\sim\pi}\left[d^{r}(Z^{\prime},Z)\right]\right\\}\right)\Big{\\}}\\\
&=\sup_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\ \inf_{\rho\geq 0}\
\sup_{\pi\in\Pi(\mathbb{P},\mathbb{P}_{N})}\Big{\\{}\rho\delta^{r}\\\
&\quad+\mathrm{E}_{(Z^{\prime},Z)\sim\pi}\left[\ell(Z^{\prime};\beta)-\rho
d^{r}(Z^{\prime},Z)\right]\Big{\\}}\\\ &\leq\inf_{\rho\geq 0}\
\sup_{\mathbb{P}\in\mathcal{P}(\mathcal{Z})}\
\sup_{\pi\in\Pi(\mathbb{P},\mathbb{P}_{N})}\Big{\\{}\rho\delta^{r}\\\
&\quad+\mathrm{E}_{(Z^{\prime},Z)\sim\pi}\left[\ell(Z^{\prime};\beta)-\rho
d^{r}(Z^{\prime},Z)\right]\Big{\\}}\\\ &\leq\inf_{\rho\geq 0}\
\sup_{\mathbb{P}\in\mathcal{P}(\mathcal{Z}),\pi\in\Pi(\mathbb{P},\mathbb{P}_{N})}\Big{\\{}\rho\delta^{r}\\\
&\quad+\mathrm{E}_{(Z^{\prime},Z)\sim\pi}\left[\sup_{z^{\prime}\in\mathcal{Z}}\left\\{\ell(z^{\prime};\beta)-\rho
d^{r}(z^{\prime},Z)\right\\}\right]\Big{\\}}\\\ &=\inf_{\rho\geq
0}\left\\{\rho\delta^{r}+\mathrm{E}_{\mathbb{P}_{N}}\left[\sup_{z^{\prime}\in\mathcal{Z}}\left\\{\ell(z^{\prime};\beta)-\rho
d^{r}(z^{\prime},Z)\right\\}\right]\right\\}\\\ &=\mathcal{I},\end{array}$

which completes the proof.

###  A.2 Proof of Lemma 3.1

For any $\pi\in\Pi(\mathbb{P},{\boldsymbol{\chi}}_{\\{\hat{z}\\}})$, we have
$\pi(A\times\mathcal{Z})=\mathbb{P}(A),\pi(\mathcal{Z}\times
B)={\boldsymbol{\chi}}_{\\{\hat{z}\\}}(B)$ for any measurable sets
$A,B\subset\mathcal{Z}$. In particular, it holds that

$\displaystyle\pi(\mathcal{Z}\times\left(\mathcal{Z}\setminus\\{\hat{z}\\}\right))={\boldsymbol{\chi}}_{\\{\hat{z}\\}}(\mathcal{Z}\setminus\\{\hat{z}\\})=0.$
(11)

This implies that for any measurable set $A\subset\mathcal{Z}$,
$\pi(A\times\left(\mathcal{Z}\setminus\\{\hat{z}\\}\right))=0$ and hence

$\begin{array}[]{ll}\pi(A\times\\{\hat{z}\\})&=\pi(A\times\mathcal{Z})-\pi(A\times\left(\mathcal{Z}\setminus\\{\hat{z}\\}\right))\\\
&=\pi(A\times\mathcal{Z})=\mathbb{P}(A).\end{array}$

Moreover, (11) also implies that

$\int_{\mathcal{Z}\times\left(\mathcal{Z}\setminus\\{\hat{z}\\}\right)}d^{r}(z^{\prime},z)\mathrm{d}\pi(z^{\prime},z)=0.$

Therefore, one has that

$\begin{array}[]{ll}\int_{\mathcal{Z}\times\mathcal{Z}}d^{r}(z^{\prime},z)\mathrm{d}\pi(z^{\prime},z)&=\int_{\mathcal{Z}\times\\{\hat{z}\\}}d^{r}(z^{\prime},z)\mathrm{d}\pi(z^{\prime},z)\\\
&=\int_{\mathcal{Z}}d^{r}(z^{\prime},\hat{z})\mathrm{d}\mathbb{P}(z^{\prime}).\end{array}$

This completes the proof.

###  A.3 Proof of Proposition 4.3

For any $z,z^{\prime}\in\mathcal{Z}$, we have

$\begin{array}[]{lll}&\left|\left|\tau-\psi(z^{\prime})\right|-\left|\tau-\psi(z)\right|\right|\leq\left|\psi(z^{\prime})-\psi(z)\right|,\\\
&\left|\max\\{0,\tau-\psi(z^{\prime})\\}-\max\\{0,\tau-\psi(z)\\}\right|\\\
&\quad\leq\left|\psi(z^{\prime})-\psi(z)\right|.\end{array}$

Moreover, we can see that

$\begin{array}[]{ll}\left|\psi(z^{\prime})-\psi(z)\right|&=\left|y^{\prime}\cdot\phi(x^{\prime})-y\cdot\phi(x)\right|\\\
&=\left|\phi(y^{\prime}x^{\prime}-yx)\right|\leq
L_{\phi}d(z^{\prime},z),\end{array}$

where the last inequality holds as follows.

  * •

If $d(z^{\prime},z)=\infty$, then it holds true;

  * •

If $d(z^{\prime},z)=0$, then $y^{\prime}=y$ and $\left\llbracket
x^{\prime}-x\right\rrbracket=0$. Since
$\left\llbracket\cdot\right\rrbracket^{-1}(0)\subseteq\phi^{-1}(0)$, this
implies that
$|\psi(z^{\prime})-\psi(z)|=\left|\phi(y^{\prime}x^{\prime}-yx)\right|=\left|\phi(x^{\prime}-x)\right|=0$;

  * •

If $0<d(z^{\prime},z)<\infty$, then we have $y^{\prime}=y$, $\left\llbracket
x^{\prime}-x\right\rrbracket\neq 0$ and

$\begin{array}[]{lll}&\left|\phi(y^{\prime}x^{\prime}-yx)\right|=\left|\phi(x^{\prime}-x)\right|\\\
&=\left\llbracket
x^{\prime}-x\right\rrbracket\left|\phi\left(\frac{x^{\prime}-x}{\left\llbracket
x^{\prime}-x\right\rrbracket}\right)\right|\\\ &\leq\left\llbracket
x^{\prime}-x\right\rrbracket L_{\phi}=L_{\phi}d(z^{\prime},z).\end{array}$

Therefore, $|\tau-\psi|$ and $\max\\{0,\tau-\psi\\}$ are
$(L_{\phi},d)$-Lipschitz at $\mathcal{Z}$.

Suppose that $L_{\phi}>0$. Then it can be seen that $\left|\tau-\psi\right|$
and $\max\\{0,\tau-\psi\\}$ satisfy Assumption (A1) at $\mathcal{Z}$ for any
$\delta>0$ thanks to previous discussions. By the definition of $L_{\phi}$,
for any $0<\epsilon<L_{\phi}$, there exists $\tilde{v}\in\mathcal{X}$ such
that $\left\llbracket\tilde{v}\right\rrbracket=1\text{ and
}\phi(\tilde{v})\geq L_{\phi}-\epsilon/2>0$. For any $z=(x,y)\in\mathcal{Z}$
and $\sigma>0$, define $\tilde{z}=(\tilde{x},\tilde{y})$ as

$\tilde{x}=x-{\rm sgn}(\tau-y\cdot\phi(x))y\sigma\tilde{v},\quad\tilde{y}=y.$

Then we can see that $d(\tilde{z},z)=\left\llbracket{\rm
sgn}(\tau-y\cdot\phi(x))y\sigma\tilde{v}\right\rrbracket=\sigma$ and

$\begin{array}[]{llll}&\left|\tau-\psi(\tilde{z})\right|-\left|\tau-\psi(z)\right|\\\
&=\left|\tau-y\cdot\phi(x-{\rm
sgn}(\tau-y\cdot\phi(x))y\sigma\tilde{v})\right|-\left|\tau-y\cdot\phi(x)\right|\\\
&=\left|\tau-y\cdot\phi(x)+{\rm
sgn}(\tau-y\cdot\phi(x))\sigma\phi(\tilde{v})\right|-\left|\tau-y\cdot\phi(x)\right|\\\
&\geq\sigma\phi(\tilde{v})\geq(L_{\phi}-\epsilon)d(\tilde{z},z).\end{array}$

Therefore, for any $\delta>0$ and $z\in\mathcal{Z}$, by setting
$\sigma\in[\delta,\infty)$ or $\sigma\in\mathcal{D}(z)$, we can see that
$|\tau-\psi|$ satisfies both Assumption (A2) and (B) at $\mathcal{Z}$.

Finally, we are going to prove that $\max\\{0,\tau-\psi\\}$ satisfy
Assumptions (A2) and (B) when $L_{\phi}>0$. For any $z\in\mathcal{Z}$ and
$\delta>0$, define $\tilde{z}=(\tilde{x},\tilde{y})$ as $\tilde{y}=y$ and

$\tilde{x}=\left\\{\begin{array}[]{ll}x-y\delta\tilde{v}&\text{if
}\tau-y\cdot\phi(x)\geq 0\\\
x-\left(2(y\cdot\phi(x)-\tau)/\epsilon+\delta\right)y\tilde{v}&\text{otherwise.}\end{array}\right.$

Then if $\tau-y\cdot\phi(x)\geq 0$, we have $d(\tilde{z},z)=\left\llbracket
y\delta\tilde{v}\right\rrbracket=\delta$ and

$\begin{array}[]{lll}&\max\\{0,\tau-\psi(\tilde{z})\\}-\max\\{\tau-\psi(z)\\}\\\