# New Perspectives on Regularization and Computation in
Optimal Transport-Based Distributionally Robust Optimization

Soroosh Shafieezadeh-Abadeh  Tepper School of Business, Carnegie Mellon
University, Pittsburgh, USA<EMAIL_ADDRESS>Liviu Aolaritei  Automatic
Control Lab, ETH Zürich, Zürich, Switzerland
<EMAIL_ADDRESS>Florian Dörfler  Automatic Control Lab, ETH Zürich,
Zürich, Switzerland
<EMAIL_ADDRESS>Daniel Kuhn  Risk Analytics and Optimization Chair,
EPFL Lausanne, Switzerland
<EMAIL_ADDRESS>
###### Abstract

We study optimal transport-based distributionally robust optimization problems
where a fictitious adversary, often envisioned as nature, can choose the
distribution of the uncertain problem parameters by reshaping a prescribed
reference distribution at a finite transportation cost. In this framework, we
show that robustification is intimately related to various forms of variation
and Lipschitz regularization even if the transportation cost function fails to
be (some power of) a metric. We also derive conditions for the existence and
the computability of a Nash equilibrium between the decision-maker and nature,
and we demonstrate numerically that nature’s Nash strategy can be viewed as a
distribution that is supported on remarkably deceptive adversarial samples.
Finally, we identify practically relevant classes of optimal transport-based
distributionally robust optimization problems that can be addressed with
efficient gradient descent algorithms even if the loss function or the
transportation cost function are nonconvex (but not both at the same time).

##  1 Introduction

Because of their relevance for empirical risk minimization in machine
learning, stochastic optimization methods are becoming increasingly popular
beyond their traditional application domains in operations research and
economics [77]. In the wake of the ongoing data revolution and the rapid
emergence of ever more complex decision problems, there is also a growing need
for stochastic optimization models outputting reliable decisions that are
insensitive to input misspecification and easy to compute.

A (static) stochastic optimization problem aims to minimize the expected value
$\mathbb{E}_{Z\sim\mathbb{P}}[\ell(\theta,Z)]$ of an uncertainty-affected loss
function $\ell:\Theta\times\mathcal{Z}\to(-\infty,\infty]$ across all feasible
decisions $\theta\in\Theta$, where $Z\in\mathcal{Z}$ is the random vector of
all uncertain problem parameters that is governed by some probability
distribution $\mathbb{P}$. To exclude trivialities, we assume throughout the
paper that the feasible set $\Theta\subseteq\mathbb{R}^{m}$ and the support
set $\mathcal{Z}\subseteq\mathbb{R}^{d}$ are non-empty and closed. Despite
their simplicity, static stochastic optimization problems are ubiquitous in
statistics and machine learning, among many other application domains.
However, their practical deployment is plagued by a fundamental challenge,
namely that the distribution $\mathbb{P}$ governing $Z$ is rarely accessible
to the decision-maker. In a data-driven decision situation, for instance,
$\mathbb{P}$ is only indirectly observable through a set of independent
training samples. In this case one may use standard methods from statistics to
construct a parametric or non-parametric reference distribution
$\widehat{\mathbb{P}}$ from the data. However, $\widehat{\mathbb{P}}$
invariably differs from $\mathbb{P}$ due to inevitable statistical errors, and
optimizing in view of $\widehat{\mathbb{P}}$ instead of $\mathbb{P}$ may lead
to decisions that display a poor performance on test data. For example, in
machine learning it is well known that deep neural networks trained in view of
the empirical distribution of the training data can easily be fooled by
adversarial examples, that is, test samples subject to seemingly negligible
noise that cause the neural network to make a wrong prediction. Even worse,
the decision problem at hand could suffer from a domain shift, that is, the
training data may originate form a distribution other than $\mathbb{P}$, under
which decisions are evaluated.

A promising strategy to mitigate the detrimental effects of estimation errors
in the reference distribution $\widehat{\mathbb{P}}$ would be to minimize the
worst-case expected loss with respect to all distributions in some
neighborhood of $\widehat{\mathbb{P}}$. There is ample evidence that, for many
natural choices of the neighborhood of $\widehat{\mathbb{P}}$, this
distributionally robust approach leads to tractable optimization models and
provides a simple means to derive powerful generalization bounds [60, 48, 15,
84, 28, 31, 27]. Specialized distributionally robust approaches may even
enable generalization in the face of domain shifts [29, 87, 51, 28] or may
make the training of deep neural networks more resilient against adversarial
attacks [79, 88, 83, 47].

More formally, distributionally robust optimization (DRO) captures the
uncertainty about the unknown distribution $\mathbb{P}$ through an ambiguity
set $\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$, that is, an
$\varepsilon$-neighborhood of the reference distribution
$\widehat{\mathbb{P}}$ with respect to a distance function on the space
$\mathcal{P}(\mathcal{Z})$ of all distributions supported on $\mathcal{Z}$.
Using this ambiguity set, the DRO problem of interest is formulated as the
minimax problem

$\displaystyle\inf_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}~{}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right].$
(1)

Problem (1) can be viewed as a zero-sum game between the decision-maker, who
chooses the decision $\theta$, and a fictitious adversary, often envisioned as
‘nature’, who chooses the distribution $\mathbb{Q}$ of $Z$. From now on we
define nature’s feasible set
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})=\\{\mathbb{Q}\in\mathcal{P}(\mathcal{Z}):d_{c}(\mathbb{Q},\widehat{\mathbb{P}})\leq\varepsilon\\}$
as a pseudo-ball of radius $\varepsilon\geq 0$ around $\widehat{\mathbb{P}}$
with respect to an optimal transport discrepancy
$d_{c}:\mathcal{P}(\mathcal{Z})\times\mathcal{P}(\mathcal{Z})\to[0,+\infty]$
defined through

$d_{c}(\mathbb{P},\widehat{\mathbb{P}})=\inf_{\pi\in\Pi(\mathbb{P},\widehat{\mathbb{P}})}\mathbb{E}_{\pi}[c(Z,\widehat{Z})].$

Here, $c:\mathcal{Z}\times\mathcal{Z}\to[0,+\infty]$ is a prescribed
transportation cost function satisfying the identity of indiscernibles
($c(z,\widehat{z})=0$ if and only if $z=\widehat{z}$), and
$\Pi(\mathbb{P},\widehat{\mathbb{P}})$ represents the set of all joint
probability distributions of $Z$ and $\widehat{Z}$ with marginals $\mathbb{P}$
and $\widehat{\mathbb{P}}$, respectively. It is conventional to refer to
elements of $\Pi(\mathbb{P},\widehat{\mathbb{P}})$ as couplings or
transportation plans. If the transportation cost function $c$ is symmetric,
then $d_{c}$ constitutes a semimetric on
$\mathcal{P}_{c}(\mathcal{Z})=\\{\mathbb{Q}\in\mathcal{P}(\mathcal{Z}):\mathbb{E}_{Z\sim\mathbb{Q}}[c(Z,\widehat{z}_{0})]<\infty\\}$,
where $\widehat{z}_{0}\in\mathcal{Z}$ is an arbitrary reference point. Thus,
$d_{c}$ satisfies all axioms of a metric but the triangle inequality.
Moreover, if $c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$ for some norm
$\|\cdot\|$ on (the span of) $\mathcal{Z}$ and for some exponent
$p\in\mathbb{N}$, then $W_{p}=\sqrt[p]{d_{c}}$ constitutes a metric on
$\mathcal{P}_{c}(\mathcal{Z})$ [86, § 6], which is termed the $p$-th
Wasserstein distance. Note that the ambiguity set
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ constructed in this way may
be interpreted as the family of all probability distributions $\mathbb{Q}$
that can be obtained by reshaping the reference distribution
$\widehat{\mathbb{P}}$ at a finite cost of at most $\varepsilon\geq 0$, where
the cost of moving unit probability from $\widehat{z}$ to $z$ is given by
$c(z,\widehat{z})$.

The following regularity conditions will be assumed to hold throughout the
paper.

######  Assumption 1.1 (Continuity assumptions).

  1. (i)

The transportation cost function $c(z,\widehat{z})$ is lower semi-continuous
in $(z,\widehat{z})$.

  2. (ii)

For any $\theta\in\Theta$, the loss function $\ell(\theta,\widehat{z})$ is
upper semi-continuous and $\widehat{\mathbb{P}}$-integrable in $\widehat{z}$.

Assumption 1.1 (i) ensures that the optimal transport problem in the
definition of $d_{c}(\mathbb{P},\widehat{\mathbb{P}})$ is solvable [86,
Theorem 4.1] and admits a strong dual linear program over a space of
integrable functions [86, Theorem 5.10]. Together, Assumptions 1.1 (i) and 1.1
(ii) ensure that the inner maximization problem in (1) admits a strong dual
minimization problem [14, Theorem 1]; see also Proposition 1.2 below. Optimal
transport-based DRO problems of the form (1) are nowadays routinely studied in
diverse areas such as statistical learning [75, 32, 21, 12, 13, 20, 74, 40,
2], estimation and filtering [76, 65, 64], control [90, 24], dynamical systems
theory [17, 1], hypothesis testing [34], inverse optimization [61], and chance
constrained programming [22, 89, 38, 39, 78] etc.; see [46] for a recent
survey. The existing literature focuses almost exclusively on Wasserstein
ambiguity sets, which are obtained by setting the transportation cost function
to $c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$ for some norm $\|\cdot\|$ on
$\mathbb{R}^{d}$. Allowing for more general transportation cost functions
enables the decision-maker to inject prior information about the likelihood of
certain subsets of $\mathcal{Z}$ into the definition of the ambiguity set. For
example, setting
$c(z,\widehat{z})=\infty\cdot\mathds{1}_{z\not\in\mathbb{A}(\widehat{z})}$ for
some measurable set $\mathbb{A}(\widehat{z})\subseteq\mathcal{Z}$ with
$\widehat{z}\in\mathbb{A}(\widehat{z})$ ensures that the probability mass
located at $\widehat{z}$ cannot be moved outside of $\mathbb{A}(\widehat{z})$.
More generally, assigning $c(z,\widehat{z})$ a large value for every
$\widehat{z}$ in the support of the reference distribution
$\widehat{\mathbb{P}}$ makes it expensive for nature to transport probability
mass to $z$. Thus, $z$ has a low probability under every distribution in the
ambiguity set. The following proposition describes a strong dual of nature’s
inner maximization problem in (1) and reveals how $c$ impacts the solution of
the underlying DRO problem. This strong duality result was first established
in [60, 92] for finite-dimensional problems with discrete reference
distributions and then generalized in [14, 33].

######  Proposition 1.2 (Strong duality).

If Assumption 1.1 holds, then we have

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\;\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]=\inf_{\lambda\geq
0}\;\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\ell_{c}(\theta,\lambda,\widehat{Z})\right]$
(2)

for any $\theta\in\Theta$ and $\varepsilon>0$, where
$\ell_{c}(\theta,\lambda,\widehat{z})=\sup_{z\in\mathcal{Z}:\,c(z,\widehat{z})<\infty}\;\ell(\theta,z)-\lambda
c(z,\widehat{z})$.

It is well known that checking whether a given distribution
$\mathbb{Q}\in\mathcal{P}(\mathcal{Z})$ belongs to
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is $\\#$P-hard even if
$\widehat{\mathbb{P}}$ is discrete [81, Theorem 2.2]. Thus, unless
$\\#\text{P}=\text{FP}$, there is no efficient algorithm to check feasibility
in the worst-case expectation problem on the left hand side of (2). Thanks to
Proposition 1.2, however, the optimal value of this problem can often be
computed efficiently by solving the dual problem on the right hand side of
(2), which constitutes a univariate convex stochastic program. Indeed, the
dual objective function involves the expected value of
$\ell_{c}(\theta,\lambda,\widehat{Z})$ with respect to the reference
distribution $\widehat{\mathbb{P}}$, which is convex in $\lambda$. In the
following, we will refer to $\ell_{c}$ as the $c$-transform of $\ell$. A key
challenge towards solving the dual problem lies in evaluating $\ell_{c}$ and
in establishing useful structural properties of $\ell_{c}$ as a function of
$\lambda$. If $-\ell$ and $c$ are (piecewise) convex in $z$ and if
$\mathcal{Z}$ is a convex set, for example, then robust optimization
techniques can be used to express $\ell_{c}(\theta,\lambda,\widehat{z})$ as
the optimal value of a finite convex minimization problem. If, additionally,
the reference distribution $\widehat{\mathbb{P}}$ has a finite support, then
the entire dual problem on the right hand side of (2) simplifies to a finite
convex minimization problem amenable to off-the-shelf solvers [60, 93].
Treating $\theta\in\Theta$ as an additional decision variable finally yields a
reformulation of the original DRO problem (1) as a single (possibly nonconvex)
finite minimization problem. This reformulation is convex if $\ell$ is convex
in $\theta$ and if $\Theta$ is a convex set.

If $-\ell$ or $c$ fail to be (piecewise) convex in $z$, $\mathcal{Z}$ fails to
be convex, or $\widehat{\mathbb{P}}$ fails to have a finite support, then
exact convex reformulation results are scarce (an exception is described in
[60, § 6.2]). In these cases, one may still attempt to attack the dual problem
in (2) directly with (stochastic) gradient descent-type algorithms [16, 79].
The efficacy of these methods is predicated on the structural properties of
the $c$-transform $\ell_{c}$. If the transportation cost function is
representable as $c(z,\widehat{z})=\Psi(z-\widehat{z})$ for some real-valued
univariate function $\Psi(\cdot)$, and if $\mathcal{Z}=\mathbb{R}^{d}$, for
instance, then $-\ell_{c}(\theta,\lambda,\cdot)$ is readily recognized as the
infimal convolution of $-\ell(\theta,\cdot)$ and $\lambda\Psi(\cdot)$. Hence,
it can be interpreted as an epigraphical regularization of
$-\ell(\theta,\cdot)$. Indeed, the epigraph of the infimal convolution
$-\ell_{c}(\theta,\lambda,\cdot)$ (essentially) coincides with the Minkowski
sum of the epigraphs of $-\ell(\theta,\cdot)$ and $\lambda\Psi(\cdot)$ [71,
Exercise 1.28 (a)]. Epigraphical regularizations are ubiquitous in
approximation theory, and it is known that, as $\lambda$ tends to infinity,
$-\ell_{c}(\theta,\lambda,\cdot)$ provides an increasingly accurate
approximation for $-\ell(\theta,\cdot)$ that inherits desirable regularity
properties from $\Psi(\cdot)$ such as uniform continuity or smoothness [3, 4,
18, 68]. Specifically, if $\Psi(\cdot)=\|\cdot\|^{2}$, then
$-\ell_{c}(\theta,\lambda,\cdot)$ reduces to the Moreau-Yosida regularization
(or Moreau envelope) [71, Chapter 1.G], which is at the heart of most proximal
algorithms [67]. In addition, if $\Psi(\cdot)=\|\cdot\|$, then
$-\ell_{c}(\theta,\lambda,\cdot)$ reduces to the Pasch-Hausdorff envelope (or
Lipschitz regularization) proposed in [71, Example 9.11] and [37], which
constitutes the largest $\lambda$-Lipschitz continuous function majorized by
$-\ell(\theta,\cdot)$.

This paper aims to develop a deeper understanding of optimal transport-based
DRO problems with general transportation cost functions, to showcase different
regularizing effects of robustification and to elucidate the connections
between DRO and game theory. Specifically, we show that robustification is
intimately related to various forms of variation and Lipschitz regularization
even if the transportation cost function is not (some power of) a metric. We
also derive conditions for the existence and the computability of a Nash
equilibrium between the decision-maker and nature in the DRO problem (1), and
we demonstrate that nature’s Nash strategy can be viewed as a distribution
that is supported on remarkably deceptive adversarial examples. Finally, we
identify practically relevant classes of optimal transport-based DRO problems
that can be addressed with efficient gradient descent algorithms even if the
loss function or the transportation cost function are nonconvex (but not both
at the same time).

The main contributions of this paper can be summarized as follows.

  1. i.

Existence of Nash equilibria. We establish weak conditions under which the DRO
problem (1), viewed as a zero-sum game between the decision-maker and nature,
admits a Nash equilibrium.

  2. ii.

Computation of Nash equilibria. We prove that the dual DRO problem, which is
obtained from (1) by interchanging the order of minimization and maximization,
can be reduced to a finite convex program under the same set of conditions
that already ensured that the primal DRO problem (1) admits a finite convex
reduction. We also show that any solutions of the primal and dual DRO problems
represent Nash strategies of the decision-maker and nature, respectively.

  3. iii.

Adversarial examples. Every Nash strategy of nature constitutes a best
response to a Nash strategy of the decision-maker, but not vice versa. In the
context of a binary classification task, we show experimentally that nature’s
Nash strategy as well as nature’s best response to the decision-maker’s Nash
strategy, as computed by Gurobi, encodes an adversarial dataset. While the
adversarial examples implied by nature’s best response can only deceive an
algorithm, the adversarial examples implied by nature’s Nash strategy can even
deceive a human.

  4. iv.

Higher-order variation and Lipschitz regularization. We show that, under
natural regularity conditions, the worst-case expected loss in (1) is bounded
above by the sum of the expected loss under the reference distribution and
several regularization terms that penalize certain $L^{p}$-norms or Lipschitz
moduli of the higher-order derivatives of the loss function. This result
generalizes and unifies several existing results, which have revealed intimate
connections between robustification and gradient regularization [32], Hessian
regularization [6] and Lipschitz regularization [60].

  5. v.

Numerical solution of nonconvex DROs. By leveraging techniques from nonconvex
optimization such as Toland’s duality principle, we show that distributionally
robust linear prediction models, which emerge in portfolio selection,
regression, classification, newsvendor, linear inverse or phase retrieval
problems, can sometimes be solved efficiently by gradient descent-type
algorithms even if the loss function or the transportation cost function are
nonconvex.

The rest of this paper is organized as follows. In Section 2 we investigate
sufficient conditions for the existence and computability of Nash equilibria
between the decision-maker and nature, and in Section 3 we shed new light on
the intimate relations between regularization and robustification and discuss
the numerical solution of certain nonconvex DRO problems. Numerical results
are reported in Secion 4.

##### Notation

We denote the inner product of two vectors $x,y\in\mathbb{R}^{d}$ by $\langle
x,y\rangle$, and for any norm $\|\cdot\|$ on $\mathbb{R}^{d}$, we use
$\|\cdot\|_{*}$ to denote its dual norm defined through
$\|y\|_{*}=\sup\\{\langle x,y\rangle:\|x\|\leq 1\\}$. The domain of a function
$f:\mathbb{R}^{d}\to[-\infty,\infty]$ is defined as
$\operatorname*{dom}(f)=\\{x\in\mathbb{R}^{d}:f(x)<\infty\\}$. The function
$f$ is proper if $f(x)>-\infty$ and $\operatorname*{dom}(f)\neq\emptyset$. The
convex conjugate of $f$ is defined as
$f^{*}(y)=\sup_{x\in\mathbb{R}^{d}}\langle y,x\rangle-f(x)$. A function $f$ is
(positively) homogeneous of degree $p\geq 1$ if $f(\lambda x)=\lambda^{p}f(x)$
for any $x\in\mathbb{R}^{d}$ and $\lambda>0$. The perspective function of a
proper, convex and lower semi-continuous function
$f:\mathbb{R}^{d}\to(-\infty,\infty]$ is defined through $f(x,\lambda)=\lambda
f(x/\lambda)$ if $\lambda>0$ and
$f(x,\lambda)=\delta^{*}_{\operatorname*{dom}(f^{*})}(x)$ if $\lambda=0$,
where $\delta_{\operatorname*{dom}(f^{*})}$ is the indicator function of the
set $\operatorname*{dom}(f^{*})$. By slight abuse of notation, however, we use
$\lambda f(x/\lambda)$ to denote the perspective function $f(x,\lambda)$ for
all $\lambda\geq 0$. The set of all integers up to $n\in\mathbb{N}$ is denote
by $[n]$.

##  2 Nash Equilibria in DRO

By construction, the DRO problem (1) constitutes a zero-sum game between an
agent, who chooses the decision $\theta\in\Theta$, and some fictitious
adversary or ‘nature,’ who chooses the distribution
$\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$. In this section
we will show that, under some mild technical conditions, any optimal decision
$\theta^{\star}$ that solves the primal DRO problem (1) and any optimal
distribution $\mathbb{Q}^{\star}$ that solves the dual DRO problem

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}~{}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$
(3)

form a Nash equilibrium. Thus, $\theta^{\star}$ and $\mathbb{Q}^{\star}$
satisfy the saddle point condition

$\displaystyle\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta^{\star},Z)\right]\leq\mathbb{E}_{Z\sim\mathbb{Q}^{\star}}\left[\ell(\theta^{\star},Z)\right]\leq\mathbb{E}_{Z\sim\mathbb{Q}^{\star}}\left[\ell(\theta,Z)\right]\quad\forall\theta\in\Theta,~{}\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}}).$
(4)

In statistics, an optimal solution $\theta^{\star}$ of the DRO problem (1) is
sometimes referred to as a minimax estimator or a robust estimator. When
$\theta^{\star}$ and $\mathbb{Q}^{\star}$ satisfy the saddle point condition
(4), then the robust estimator $\theta^{\star}$ solves the stochastic program
$\min_{\theta\in\Theta}~{}\mathbb{E}_{Z\sim\mathbb{Q}^{\star}}\left[\ell(\theta,Z)\right]$,
which minimizes the expected loss under the crisp distribution
$\mathbb{Q}^{\star}$; see also [54, Chapter 5]. For this reason,
$\mathbb{Q}^{\star}$ is often referred to as a least favorable distribution.
The existence of $\mathbb{Q}^{\star}$ makes the robust estimator
$\theta^{\star}$ particularly attractive. Indeed, if $\mathbb{Q}^{\star}$
exists, then $\theta^{\star}$ solves a classical stochastic program akin to
the ideal learning problem one would want to solve if the true distribution
was known. In the remainder of this section, we will first identify mild
regularity conditions under which a Nash equilibrium is guaranteed to exist
(Section 2.1), and then we will show that if the reference distribution is
discrete and the loss function is convex-piecewise concave, then the dual DRO
problem (3) can be reformulated as a finite convex program (Section 2.2). This
reformulation will finally enable us to construct a least favorable
distribution.

###  2.1 Existence of Nash Equilibria

The following assumption is instrumental to prove the existence of a Nash
equilibrium.

######  Assumption 2.1 (Transportation cost).

  1. (i)

There exists a reference point $\widehat{z}_{0}\in\mathcal{Z}$ such that
$\mathbb{E}_{Z\sim\widehat{\mathbb{P}}}[c(Z,\widehat{z}_{0})]\leq C$ for some
constant $C<\infty$.

  2. (ii)

There exists a metric $d(z,\widehat{z})$ on $\mathcal{Z}$ with compact
sublevel sets such that $c(z,\widehat{z})\geq d^{p}(z,\widehat{z})$ for some
exponent $p\in\mathbb{N}$.

Assumption 2.1 will enable us to prove that the ambiguity set
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is weakly compact. We
emphasize that Assumption 2.1 (ii) is unrestrictive and allows for
transportation costs that fail to display common properties such as symmetry,
convexity, homogeneity, or the triangle inequality.

######  Example 2.2 (Local Mahalanobis transportation cost).

The local Mahalanobis transportation cost is defined as
$c(z,\widehat{z})=\langle z-\widehat{z},A(\widehat{z})(z-\widehat{z})\rangle$,
where $A(\widehat{z})$ represents a positive definite matrix for each
$\widehat{z}\in\mathcal{Z}$ [16]. This transportation cost satisfies
Assumption 2.1 (i) if the reference distribution $\widehat{\mathbb{P}}$ has
finite second moments, and it satisfies Assumption 2.1 (ii) for
$d(z,\widehat{z})=\alpha\|z-\widehat{z}\|_{2}$ and $p=2$ if
$\alpha=\inf_{\widehat{z}\in\mathcal{Z}}\lambda_{\min}(A(\widehat{z}))>0$.
However, the local Mahalanobis transportation cost fails to be symmetric.

######  Example 2.3 (Discrete metric).

If the transportation cost is identified with the (nonconvex) discrete metric
$c(z,\widehat{z})=\mathds{1}_{\\{z\neq\widehat{z}\\}}$, then the optimal
transport distance reduces to the total variation distance [86, § 6]. In this
case Assumption 2.1 (i) is trivially satisfied, and Assumption 2.1 (ii) holds
for $d(z,\widehat{z})=c(z,\widehat{z})$ and for any $p\geq 1$ provided that
the support set $\mathcal{Z}$ is compact.

To prove the existence of Nash equilibria, we also need the following
assumption on the loss function.

######  Assumption 2.4 (Loss function).

  1. (i)

For any $z\in\mathcal{Z}$, the function $\ell(\theta,z)$ is convex and lower
semi-continuous in $\theta$.

  2. (ii)

For any $\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ and any
$\bar{\theta}\in\Theta$, there exists a neighborhood $\mathcal{U}$ of
$\bar{\theta}$ such that the family of functions
$\ell^{-}(\theta,z)=-\min\\{0,\ell(\theta,z)\\}$ parametrized by
$\theta\in\mathcal{U}$ is uniformly $\mathbb{Q}$-integrable in $z$.

  3. (iii)

For any $\theta\in\Theta$, there are $g>0$, $\widehat{z}_{0}\in\mathcal{Z}$
and $r\in(0,p)$ with $\ell(\theta,z)\leq
g\left[1+d^{r}(z,\widehat{z}_{0})\right]$ for all $z\in\mathcal{Z}$.

As we will see below, Assumptions 2.4 (i) and 2.4 (ii) imply that
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ is lower semi-
continuous in $\theta$, while Assumption 2.4 (iii) implies that
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ is weakly upper
semi-continuous in $\mathbb{Q}$. Note that Assumption 2.4 (ii) trivially holds
for non-negative loss functions. The following proposition establishes that
the inner maximization problem in (1) is solvable, which is a key ingredient
needed to prove the existence of a Nash equilibrium. This proposition
generalizes [91, Theorems 1 and 2] to ambiguity sets defined in terms of
general optimal transport discrepancies.

######  Proposition 2.5 (Worst-case expectation).

If the transportation cost satisfies Assumptions 1.1 (i) and 2.1, then the
ambiguity set $\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is weakly
compact. If in addition the loss function satisfies Assumptions 1.1 (ii) and
2.4 (iii), then the supremum in (2) is finite and attained for any
$\theta\in\Theta$.

###### Proof.

Throughout this proof we use $W_{p}$ to denote the $p$-th Wasserstein distance
with respect to the metric $d$ from Assumption 2.1 (ii). Specifically, for any
probability distributions $\mathbb{Q}$ and $\widehat{\mathbb{P}}$ on
$\mathcal{Z}$ we set

$\displaystyle\textstyle
W_{p}(\mathbb{Q},\widehat{\mathbb{P}})=\left(\inf_{\pi\in\Pi(\mathbb{Q},\widehat{\mathbb{P}})}\mathbb{E}_{(Z,\widehat{Z})\sim\pi}[d(Z,\widehat{Z})^{p}]\right)^{1/p}.$
(5)

In addition, we define the Wasserstein space
$\mathcal{W}_{p}(\mathcal{Z})\subseteq\mathcal{P}(\mathcal{Z})$ as the family
of all probability distributions $\mathbb{Q}$ on $\mathcal{Z}$ with
$\mathbb{E}_{Z\sim\mathbb{Q}}[d(Z,\widehat{z}_{0})^{p}]<\infty$, where
$\widehat{z}_{0}\in\mathcal{Z}$ is the reference point from Assumption 1.1
(i). By using the triangle inequality for the metric $d$, one can show that
the Wasserstein space is in fact independent of the choice of
$\widehat{z}_{0}$. Next, we define the $p$-th Wasserstein ball of radius
$\varepsilon\geq 0$ around $\widehat{\mathbb{P}}$ as

$\displaystyle\mathbb{W}_{\varepsilon}(\widehat{\mathbb{P}})=\left\\{\mathbb{Q}\in\mathcal{P}(\mathcal{Z}):W_{p}(\mathbb{Q},\widehat{\mathbb{P}})\leq\varepsilon\right\\}.$

Assumptions 2.1 (i) and 2.1 (ii) imply that
$\widehat{\mathbb{P}}\in\mathcal{W}_{p}(\mathcal{Z})$, which in turn implies
via the triangle inequality for the $p$-th Wasserstein distance $W_{p}$ that
$\mathbb{W}_{\varepsilon}(\widehat{\mathbb{P}})\subseteq\mathcal{W}_{p}(\mathcal{Z})$;
see also [91, Lemma 1]. Assumption 2.1 (ii) further ensures that $d_{c}\geq
W_{p}^{p}$, and thus the ambiguity set
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ constructed from the optimal
transport discrepancy $d_{c}$ is covered by the ambiguity set
$\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$ constructed from the
Wasserstein distance $W_{p}$.

In order to prove that $\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is
weakly compact, note first that the Wasserstein ball
$\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$ is weakly sequentially
compact thanks to [91, Theorem 1]. Since the notions of sequential compactness
and compactness are equivalent on metric spaces [62, Theorem 28.2] and since
the weak topology on $\mathcal{P}(\mathcal{Z})$ is metrized by the Prokhorov
metric [11, Theorem 6.8],
$\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$ is also weakly compact.
Next, recall that the transportation cost $c$ is lower semi-continuous by
virtue of Assumption 1.1 (i). This implies via [23, Lemma 5.2] that
$W_{c}(\cdot,\widehat{\mathbb{P}})$ is lower semi-continuous with respect to
the weak topology on $\mathcal{P}(\mathcal{Z})$. Therefore,
$\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$ is weakly closed as a
sublevel set of a weakly lower semi-continuous mapping. As any weakly closed
subset of a weakly compact set is weakly compact,
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is indeed weakly compact.

Next, we prove that the supremum in (2) is finite. As
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})\subseteq\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$,
it is clear that

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]\leq\sup_{\mathbb{Q}\in\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right].$

The supremum on the right side of the above inequality is finite by [91,
Theorem 2], which applies thanks to Assumptions 1.1, 2.1 (i) and 2.4 (iii). In
particular, Assumption 2.4 (iii) ensures that there exist $g>0$,
$\widehat{z}_{0}\in\mathcal{Z}$, and $r\in(0,p)$ such that the loss function
satisfies the required growth condition

$\displaystyle\ell(\theta,z)\leq g\left[1+d^{r}(z,\widehat{z}_{0})\right]\leq
g\left[1+1+d^{p}(z,\widehat{z}_{0})\right]\leq
2g\left[1+d^{p}(z,\widehat{z}_{0})\right]\quad\forall z\in\mathcal{Z}.$

Thus, the suprema in (2) have a finite upper bound. On the other hand, the
suprema in (2) are bounded below by
$\mathbb{E}_{Z\sim\widehat{\mathbb{P}}}[\ell(\theta,Z)]$, which is finite by
virtue of Assumption 1.1 (ii).

It remains to be shown that the supremum in (2) is attained. To this end, we
first observe that the objective function
$\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]$ is weakly upper semi-continuous
in $\mathbb{Q}$ over the ambiguity set
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$. This follows immediately
from the proof of [91, Theorem 3], which reveals that
$\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]$ is weakly upper semi-continuous
over $\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$, and from the
observation that
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})\subseteq\mathbb{W}_{\varepsilon^{1/p}}(\widehat{\mathbb{P}})$.
As $\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is weakly compact,
Weierstrass’ theorem then guarantees that the supremum in (2) is indeed
attained. ∎

Armed with Proposition 2.5, we are now ready to state the main result of this
section.

######  Theorem 2.6 (Minimax theorem).

If Assumptions 1.1, 2.1 and 2.4 hold and $\Theta$ is convex, then we have

$\displaystyle\inf_{\theta\in\Theta}\max_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]=\max_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right].$
(6)

###### Proof.

The infimum and the maximum in (6) can be interchanged thanks to Sion’s
minimax theorem [80, Corollary 3.3]. To see that Sion’s minimax theorem
applies, note first that $\Theta$ is convex by assumption and that
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ is both convex as well as
weakly compact. The convexity of
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ follows from [86, Theorem
4.8], which applies because the transportation cost $c$ is non-negative and
lower semi-continuous by virtue of Assumption 1.1 (i). The weak compactness of
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ was established in
Proposition 2.5. Next, note that the objective function
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ inherits convexity
and lower-semicontinuity in $\theta$ from the loss function $\ell(\theta,z)$.
Specifically, lower semi-continuity holds because

$\displaystyle\liminf_{\theta_{n}\rightarrow\theta}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta_{n},Z)\right]\geq\mathbb{E}_{Z\sim\mathbb{Q}}\left[\liminf_{\theta_{n}\rightarrow\theta}\ell(\theta_{n},Z)\right]\geq\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right],$

where the two inequalities follow from Fatou’s lemma for random variables with
uniformly integrable negative parts, which applies thanks to Assumption 2.4
(ii), and from the lower semi-continuity of the loss function $\ell(\theta,z)$
in $\theta$ stipulated in Assumption 2.4 (i), respectively. Finally, one
readily verifies that the objective function
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ is concave (in fact,
linear) and weakly upper semi-continuous in $\mathbb{Q}$. This follows
directly from the proof Proposition 2.5. In summary, we have shown that all
assumptions of Sion’s minimax theorem are satisfied, which implies that the
infimum and the maximum in (6) may indeed be interchanged. It remains to be
shown that both maxima in (6) are attained. However, this follows immediately
from the weak compactness of $\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$
and the weak upper semi-continuity in $\mathbb{Q}$ of both the expected loss
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ and the optimal
expected loss
$\inf_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$.
∎

Theorem 2.6 generalizes [15, Theorem 2], which holds only for quadratic
transportation cost functions, non-negative loss functions and discrete
(empirical) reference distributions. Even though we use similar proof
techniques, we significantly relax the conditions of [15, Theorem 2] in that
we allow $c$ to be nonconvex, $\ell$ to adopt both positive and negative
values and $\mathbb{P}$ to be non-discrete. Theorem 2.6 implies that the
infimum of the primal DRO problem matches the maximum of the dual DRO problem
and that the maximum of the dual DRO problem is attained by some distribution
$\mathbb{Q}^{\star}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$. Without
imposing further conditions on $\Theta$, however, the infimum of the primal
DRO problem might not be attained. As
$\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]$ is lower semi-
continuous in $\theta$, a sufficient condition for the primal DRO problem to
be solved by some $\theta^{\star}\in\Theta$ is that the feasible set $\Theta$
is compact. In this case $\theta^{\star}$ and $\mathbb{Q}^{\star}$ form a Nash
equilibrium. These insights culminate in the following corollary.

######  Corollary 2.7 (Existence of Nash equilibria).

If Assumptions 1.1, 2.1 and 2.4 hold and if $\Theta$ is both convex and
compact, then we have

$\displaystyle\min_{\theta\in\Theta}\max_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right]=\max_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\min_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(\theta,Z)\right].$

###  2.2 Computation of Nash Equilibria

At first sight, the dual DRO problem (3) appears intractable as it constitutes
a challenging maximin problem that maximizes the optimal value of a parametric
minimization problem over an infinite-dimensional space of probability
distributions. It is well known that the primal DRO problem (1) can be
reformulated as a finite convex program if the loss function $\ell(\theta,z)$,
the support set $\mathcal{Z}$, the feasible set $\Theta$ and the
transportation cost $c(z,\widehat{z})$ display certain convexity properties
and if the reference distribution $\widehat{\mathbb{P}}$ is discrete; see,
e.g., [60, § 4.1] or [93, § 6]. In the remainder of this section we will
demonstrate that essentially the same regularity conditions also enable us to
reformulate the dual DRO problem (3) as a finite convex program. The solutions
of the emerging convex programs can be used to construct a robust decision
$\theta^{\star}$ and a least favorable distribution $\mathbb{Q}^{\star}$ that
form a Nash equilibrium.

As we will explain below, knowledge of both $\theta^{\star}$ and
$\mathbb{Q}^{\star}$ offers valuable insights into the decision problem at
hand. To date, however, dual DRO problems have only been investigated in
specific applications. For example, it is known that the least favorable
distribution in distributionally robust minimum mean square error estimation
and Kalman filtering problems with a type-$2$ Wasserstein ambiguity set
centered at a Gaussian reference distribution is Gaussian and can be computed
efficiently by solving a semidefinite program [65, 76]. When the ambiguity set
is defined in terms of the Kullback-Leibler divergence instead of the
Wasserstein distance, the least favorable distribution remains Gaussian and
can be found in quasi-closed form [55, 56]. Similar results are available for
generalized $\tau$-divergence ambiguity sets [95, 94]. In addition, Nash
equilibria for distributionally robust pricing and auction design problems
with rectangular ambiguity sets can sometimes also be derived in closed form
[43, 44].

We will now show that general dual DRO problems of the form (3) can often be
addressed with methods from convex optimization. To this end, we restrict
attention to discrete reference distributions.

######  Assumption 2.8 (Reference distribution).

We have $\widehat{\mathbb{P}}=\sum_{j\in[J]}p_{j}\delta_{\widehat{z}_{j}}$ for
some $J\in\mathbb{N}$, where each probability $p_{j}$ is strictly positive and
$\delta_{\widehat{z}_{j}}$ denotes the Dirac measure at the atom
$\widehat{z}_{j}\in\mathcal{Z}$.

We also need the following assumption, which constrains the shape of the
transportation cost function, the loss function, the support set and the
feasible set. Thus, it limits modeling flexibility.

######  Assumption 2.9 (Convexity conditions).

  1. (i)

The transportation cost function $c(z,\widehat{z})$ is lower semi-continuous
in $(z,\widehat{z})$ and convex in $z$.

  2. (ii)

The loss function is representable as a pointwise maximum of finitely many
saddle functions, that is, we have
$\ell(\theta,z)=\max_{i\in[I]}\ell_{i}(\theta,z)$ for some $I\in\mathbb{N}$,
where $\ell_{i}(\theta,z)$ is proper, convex and lower semi-continuous in
$\theta$, while $-\ell_{i}(\theta,z)$ is proper, convex and lower semi-
continuous in $z$.

  3. (iii)

The support set is representable as
$\mathcal{Z}=\\{z\in\mathbb{R}^{d}:f_{k}(z)\leq 0~{}\forall k\in[K]\\}$ for
some $K\in\mathbb{N}$, where each function $f_{k}(z)$ is proper, convex and
lower semi-continuous.

  4. (iv)

The feasible set is representable as
$\Theta=\\{\theta\in\mathbb{R}^{m}:g_{l}(\theta)\leq 0~{}\forall l\in[L]\\}$
for some $L\in\mathbb{N}$, where each function $g_{l}(\theta)$ is proper,
convex and lower semi-continuous.

Recall that the transportation cost function $c(z,\widehat{z})$ is non-
negative and satisfies the identity of indiscernibles. Together with
Assumption 2.9 (i), this immediately implies that $c(z,\widehat{z})$ is
proper, convex and lower semi-continuous in $z$ for every fixed $\widehat{z}$
and that it is proper and lower semi-continuous in $\widehat{z}$ for every
fixed $z$. Assumption 2.9 (ii) requires both $\ell_{i}(\theta,z)$ and
$-\ell_{i}(\theta,z)$ to be proper, which implies that the saddle function
$\ell_{i}(\theta,z)$ can adopt only finite values. However, the convex
functions $f_{k}(z)$ and $g_{l}(\theta)$ introduced in Assumptions 2.9 (iii)
and 2.9 (iv), respectively, may adopt the value $\infty$.

In the remainder, we adopt the following definition of a Slater point for a
minimization problem.

######  Definition 2.10 (Slater point).

A Slater point of the set $\mathcal{X}=\\{x\in\mathbb{R}^{d}:h_{m}(x)\leq
0~{}\forall m\in[M]\\}$ represented via $M$ generic inequality constraints is
any vector $x^{s}\in\mathcal{X}$ with
$x^{s}\in\operatorname*{ri}(\operatorname*{dom}(h_{m}))$ for all $m\in[M]$ and
$h_{m}(x^{s})<0$ for all $m\in[M]$ such that $h_{m}$ is nonlinear. In
addition, $x^{s}$ is a Slater point of the minimization problem
$\inf\\{h_{0}(x):x\in\mathcal{X}\\}$ if it is a Slater point of $\mathcal{X}$
and if $x^{s}\in\operatorname*{ri}(\operatorname*{dom}(h_{0}))$.

Our results also rely on the following technical Slater conditions. Even
though they are indispensable for the proofs of our convex reformulation
results below, they do not critically limit modeling flexibility.

######  Assumption 2.11 (Slater conditions).

  1. (i)

For every $j\in[J]$,
$\widehat{z}_{j}\in\operatorname*{ri}(\operatorname*{dom}(c(\cdot,\widehat{z}_{j})))$
is a Slater point for the support set $\mathcal{Z}$.

  2. (ii)

The feasible set $\Theta$ admits a Slater point.

Before addressing the dual DRO problem (3), we show that the primal DRO
problem (1) admits a finite convex reformulation when the above regularity
conditions are satisfied. This reformulation was first derived under the
simplifying assumption that $c(z,\widehat{z})=\|z-\widehat{z}\|$ is defined in
terms of a norm on $\mathcal{Z}$ [60, Theorem 4.2] and later generalized to
arbitrary convex transportation cost functions [93, § 6]. Proposition 2.12
below re-derives this reformulation under the Assumptions 2.8, 2.9 and 2.11
(i), which can be checked ex ante. In contrast, the regularity conditions used
in [93] can only be checked ex post by solving a convex program. To keep this
paper self-contained, we provide a simple proof of Proposition 2.12, which
will also allow us to streamline the proof of Proposition 2.14 below.

######  Proposition 2.12 (Primal reformulation).

If Assumptions 2.8, 2.9 and 2.11 (i) hold and if $\varepsilon>0$, then the
primal DRO problem (1) has the same infimum as the finite convex program

$\displaystyle\begin{array}[]{cll}\inf&\displaystyle\lambda\varepsilon+\sum_{j\in[J]}p_{j}s_{j}\\\\[6.45831pt]
\operatorname*{s.t.}&\theta\in\Theta,\,\lambda,\tau_{ijk}\in\mathbb{R}_{+},\,s_{j}\in\mathbb{R},\,\zeta^{\ell}_{ij},\zeta^{c}_{ij},\zeta^{f}_{ijk}\in\mathbb{R}^{d}&\forall
i\in[I],\,j\in[J],\,k\in[K]\\\\[8.61108pt]
&\displaystyle(-\ell_{i})^{*2}(\theta,\zeta^{\ell}_{ij})+\lambda
c^{*1}(\zeta^{c}_{ij}/\lambda,\widehat{z}_{j})+\sum_{k\in[K]}\tau_{ijk}f_{k}^{*}(\zeta^{f}_{ijk}/\tau_{ijk})\leq
s_{j}&\forall i\in[I],\,j\in[J]\\\\[6.45831pt]
&\displaystyle\zeta^{\ell}_{ij}+\zeta^{c}_{ij}+\sum_{k\in[K]}\zeta^{f}_{ijk}=0&\forall
i\in[I],\,j\in[J],\end{array}$ (11)

where $(-\ell_{i})^{*2}(\theta,\zeta)$ denotes the conjugate of
$-\ell_{i}(\theta,z)$ with respect to its second argument $z$ for fixed
$\theta$, and where $c^{*1}(\zeta,\widehat{z})$ denotes the conjugate of
$c(z,\widehat{z})$ with respect to its first argument $z$ for fixed
$\widehat{z}$.

###### Proof.

Note first that Assumptions 2.8 and 2.9 (i)–(ii) strengthen Assumption 1.1. In
particular, Assumption 2.9 (i) trivially implies Assumption 1.1 (i). In
addition, Assumption 2.8 requires $\widehat{\mathbb{P}}$ to be discrete, and
Assumption 2.9 (ii) implies that $\ell(\theta,z)$ is finite-valued. As any
finite-valued function is integrable with respect to any discrete
distribution, Assumption 1.1 (ii) trivially holds. Thus, Proposition 1.2
applies and allows us to reformulate the inner supremum in (1) as

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}~{}\mathbb{E}_{\mathbb{Q}}\left[\ell(\theta,Z)\right]=\left\\{\begin{array}[]{cll}\inf&\displaystyle\lambda\varepsilon+\sum_{j\in[J]}p_{j}s_{j}\\\\[4.30554pt]
\operatorname*{s.t.}&\lambda\in\mathbb{R}_{+},~{}s_{j}\in\mathbb{R}&\forall
j\in[J]\\\\[4.30554pt]
&\displaystyle\sup_{z\in\mathcal{Z}}~{}\ell(\theta,z)-\lambda
c(z,\widehat{z}_{j})\leq s_{j}&\forall j\in[J],\end{array}\right.$

where the epigraphical decision variable $s_{j}$ coincides with
$\ell_{c}(\theta,\lambda,\widehat{z}_{j})=\sup_{z\in\mathcal{Z}}~{}\ell(\theta,z)-\lambda
c(z,\widehat{z}_{j})$ at optimality. Note that since $\ell(\theta,z)$ is
finite-valued, there is no need to make the constraint
$c(z,\widehat{z})<\infty$ explicit. By Assumption 2.9 (ii), the loss function
$\ell$ can be expressed in terms of the saddle functions $\ell_{i}$,
$i\in[I]$, and thus the resulting dual problem is equivalent to the following
robust convex program.

$\displaystyle\begin{array}[]{cll}\inf&\displaystyle\lambda\varepsilon+\sum_{j\in[J]}p_{j}s_{j}\\\\[4.30554pt]
\operatorname*{s.t.}&\lambda\in\mathbb{R}_{+},~{}s_{j}\in\mathbb{R}&\forall
j\in[J]\\\\[4.30554pt]
&\displaystyle\sup_{z\in\mathcal{Z}}~{}\ell_{i}(\theta,z)-\lambda
c(z,\widehat{z}_{j})\leq s_{j}&\forall i\in[I],\,j\in[J]\end{array}$ (15)

By the convexity of the support set $\mathcal{Z}$ imposed by Assumption 2.9
(iii) and thanks to an explicit convex duality result [93, Theorem 2], the
embedded maximization problems in (15) can be recast as

$\displaystyle\sup_{z\in\mathcal{Z}}~{}\ell_{i}(\theta,z)-\lambda
c(z,\widehat{z}_{j})=\left\\{\begin{array}[]{cl}\min&\displaystyle(-\ell_{i})^{*2}(\theta,\zeta^{\ell}_{ij})+\lambda
c^{*1}(\zeta^{c}_{ij}/\lambda,\widehat{z}_{j})+\sum_{k\in[K]}\tau_{ijk}f_{k}^{*}(\zeta^{f}_{ijk}/\tau_{ijk})\\\\[8.61108pt]
\operatorname*{s.t.}&\tau_{ijk}\in\mathbb{R}_{+},~{}\zeta^{\ell}_{ij},\zeta^{c}_{ij},\zeta^{f}_{ijk}\in\mathbb{R}^{d}\quad\forall
k\in[K]\\\\[6.45831pt]
&\displaystyle\zeta^{\ell}_{ij}+\zeta^{c}_{ij}+\sum_{k\in[K]}\zeta^{f}_{ijk}=0\end{array}\right.$

for all $i\in[I]$ and $j\in[J]$. Indeed, Assumption 2.11 (i) and the
finiteness of $\ell_{i}$ implied by Assumption 2.9 (ii) ensure that the primal
maximization problem admits a Slater point. This implies both strong duality
as well as solvability of the dual minimization problem. Substituting all
resulting dual minimization problems into (15) and eliminating the
corresponding minimization operators yields (11).

Note that the conjugate $(-\ell_{i})^{*2}$ of the negative saddle function
$-\ell_{i}$ with respect to its second argument is convex by construction.
Similarly, when $\widehat{z}_{j}$ is kept fixed, the perspectives of the
conjugates $c^{*1}(\cdot,\widehat{z}_{j})$ and $f^{\star}_{k}$ are readily
seen to be convex. Thus, problem (11) is indeed a convex program. ∎

Next, we prove that the dual DRO problem (3) also admits a finite convex
reformulation if all assumptions of Proposition 2.8 are satisfied and if at
least one out of three regularity conditions holds.

######  Assumption 2.13 (Self service condition).

At least one of the following three conditions is satisfied: (i) $\Theta$ is
compact, (ii) $\mathcal{Z}$ is compact or (iii) $c(z,\widehat{z})$ grows
superlinearly with $z$.

Assumption 2.13 is unrestrictive in practice, and we will later see that it
can be further relaxed.

######  Proposition 2.14 (Dual reformulation).

If Assumptions 2.8, 2.9, 2.11 and 2.13 hold and if $\varepsilon>0$, then the
dual DRO problem (3) has the same supremum as the finite convex program

$\displaystyle\begin{array}[]{cl@{\,}l}\max&\displaystyle-\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\ell_{i}^{*1}(\alpha_{ij}/q_{ij},\widehat{z}_{j}+\xi_{ij}/q_{ij})-\sum_{l\in[L]}\nu_{l}&g^{*}_{l}(\beta_{l}/\nu_{l})\\\\[4.30554pt]
\operatorname*{s.t.}&\displaystyle
q_{ij},\nu_{l}\in\mathbb{R}_{+},~{}\xi_{ij}\in\mathbb{R}^{d},~{}\alpha_{ij},\beta_{l}\in\mathbb{R}^{m}&\forall
i\in[I],\,j\in[J],\,l\in[L]\\\\[4.30554pt]
&q_{ij}f_{k}(\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}})\leq 0&\forall
i\in[I],\,j\in[J],\,k\in[K]\\\\[4.30554pt]
&\displaystyle\sum_{i\in[I]}q_{ij}=p_{j}&\forall j\in[J]\\\\[4.30554pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}\alpha_{ij}+\sum_{l\in[L]}\beta_{l}=0\\\\[4.30554pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\,c\big{(}\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}},\widehat{z}_{j})\leq\varepsilon,\end{array}$
(22)

where $\ell_{i}^{*1}(\alpha,z)$ denotes the conjugate of $\ell_{i}(\theta,z)$
with respect to its first argument $\theta$ for fixed $z$.

###### Proof.

We first establish that the infimum of the primal DRO problem (1) equals the
maximum of the finite convex program (22) and that (22) is indeed solvable
(Step 1). Using the insights from Step 1, we then show that any optimal
solution of the convex program (22) can be used to construct a near-optimal
solution of the dual DRO problem (3) and that the two problems have the same
supremum (Step 2).

Step 1. By Proposition 2.12 for $\Theta=\\{\theta\\}$, which applies thanks to
Assumptions 2.8, 2.9 and 2.11 (i) and because $\varepsilon>0$, the supremum of
the inner maximization problem in (1) equals

$\displaystyle\begin{array}[]{cll}\inf&\displaystyle\lambda\varepsilon+\sum_{j\in[J]}p_{j}s_{j}\\\\[6.45831pt]
\operatorname*{s.t.}&\lambda,\tau_{ijk}\in\mathbb{R}_{+},~{}s_{j}\in\mathbb{R},~{}\zeta^{\ell}_{ij},\zeta^{c}_{ij},\zeta^{f}_{ijk}\in\mathbb{R}^{d}&\forall
i\in[I],/,j\in[J],\,k\in[K]\\\\[8.61108pt]
&\displaystyle(-\ell_{i})^{*2}(\theta,\zeta^{\ell}_{ij})+\lambda
c^{*1}(\zeta^{c}_{ij}/\lambda,\widehat{z}_{j})+\sum_{k\in[K]}\tau_{ijk}f_{k}^{*}(\zeta^{f}_{ijk}/\tau_{ijk})\leq
s_{j}&\forall i\in[I],\,j\in[J]\\\
&\displaystyle\zeta^{\ell}_{ij}+\zeta^{c}_{ij}+\sum_{k\in[K]}\zeta^{f}_{ijk}=0&\forall
i\in[I],\,j\in[J].\end{array}$ (27)

In [93, § 6] it is shown that the maximization problem dual to the above
minimization problem can be simplified by eliminating auxiliary epigraphical
decision variables and applying a linear variable substitution; see problem
(19) in [93]. In our notation, this simplified dual convex program is given by

$\displaystyle\begin{array}[]{cll}\max&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}/q_{ij})\\\\[2.15277pt]
\operatorname*{s.t.}&\displaystyle
q_{ij}\in\mathbb{R}_{+},~{}\xi_{ij}\in\mathbb{R}^{d}&\forall
i\in[I],\,j\in[J]\\\\[2.15277pt]
&q_{ij}f_{k}(\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}})\leq 0&\forall
i\in[I],\,j\in[J],\,k\in[K]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}q_{ij}=p_{j}&\forall j\in[J]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\,c\big{(}\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}},\widehat{z}_{j})\leq\varepsilon.\end{array}$
(33)

Strong duality holds thanks to Assumption 2.11 (i), which implies that the
dual maximization problem admits a Slater point
$(\\{q_{ij}^{s},\xi_{ij}^{s}\\}_{i,j})$ with $q_{ij}^{s}=p_{j}/J$ and
$\xi_{ij}^{s}=0$ for all $i\in[I]$ and $j\in[J]$. In addition, [93,
Proposition 20] implies that the dual problem has a compact feasible set and
is thus solvable. Hence, its maximum is indeed attained. Substituting this
dual problem back into (1) and interchanging the infimum and the maximum,
which is allowed by Sion’s minimax theorem [80], we then obtain

$\displaystyle\begin{array}[]{cll}\max&\displaystyle\inf_{\theta\in\Theta}~{}\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}/q_{ij})\\\\[2.15277pt]
\operatorname*{s.t.}&\displaystyle
q_{ij}\in\mathbb{R}_{+},~{}\xi_{ij}\in\mathbb{R}^{d}&\forall
i\in[I],\,j\in[J]\\\\[2.15277pt]
&q_{ij}f_{k}(\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}})\leq 0&\forall
i\in[I],\,j\in[J],\,k\in[K]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}q_{ij}=p_{j}&\forall j\in[J]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\,c\big{(}\widehat{z}_{j}+{\xi_{ij}}/{q_{ij}},\widehat{z}_{j})\leq\varepsilon.\end{array}$
(39)

The inner minimization problem in (39) has a Slater point because of
Assumptions 2.9 (ii) and 2.11 (ii). By [93, Theorem 2], this minimization
problem therefore admits a strong dual of the form

$\displaystyle\begin{array}[]{cl}\max&\displaystyle-\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}\ell_{i}^{*1}(\alpha_{ij}/q_{ij},\widehat{z}_{j}+\xi_{ij}/q_{ij})-\sum_{l\in[L]}\nu_{l}g^{*}_{l}(\beta_{l}/\nu_{l})\\\\[4.30554pt]
\operatorname*{s.t.}&\alpha_{ij}\in\mathbb{R}^{m},~{}\beta_{l}\in\mathbb{R}^{m},~{}\nu_{l}\in\mathbb{R}_{+}\quad\forall
i\in[I],\,j\in[J],\,l\in[L]\\\\[4.30554pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}\alpha_{ij}+\sum_{l\in[L]}\beta_{l}=0,\end{array}$
(43)

which is solvable. Substituting this dual maximization problem back into (39)
finally yields (22). Note that the maximum in (22) is indeed attained because
problem (39) as well as the dual of the parametric minimization problem in its
objective function are both solvable.

Step 2. Fix now any maximizer
$(\\{q_{ij}^{\star},\xi_{ij}^{\star},\alpha_{ij}^{\star}\\}_{i,j},\\{\nu_{l}^{\star},\beta_{l}^{\star}\\}_{l})$
of problem (22), which exists thanks to the results of Step 1. In Step 2 we
will show that this maximizer can be used to construct a maximizer of the dual
DRO problem (3) (if (3) is solvable) or a sequence of distributions that are
feasible and asymptotically optimal in (3) (if (3) is not solvable). To this
end, define three disjoint index sets

$\displaystyle\mathcal{I}_{j}^{+}=\left\\{i\in[I]:q_{ij}^{\star}>0\right\\},\quad\mathcal{I}_{j}^{0}=\left\\{i\in[I]:q_{ij}^{\star}=0,\,\xi_{ij}^{\star}=0\right\\}\quad\text{and}\quad\mathcal{I}_{j}^{\infty}=\left\\{i\in[I]:q_{ij}^{\star}=0,\,\xi_{ij}^{\star}\neq
0\right\\},$

which form a partition of $[I]$ for every fixed $j$. Assume first that
$\mathcal{I}_{j}^{\infty}=\emptyset$ for every $j\in[J]$. In this case, we can
use similar arguments as in [46, § 2.2] and [93, § 6] to show that the
discrete distribution

$\mathbb{Q}^{\star}=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}\delta_{\widehat{z}_{j}+{\xi_{ij}^{\star}}/{q_{ij}^{\star}}}$

solves the dual DRO problem (3). Note first that $\mathbb{Q}^{\star}$ is
indeed a probability distribution because

$\mathbb{Q}^{\star}(z\in\mathbb{R}^{d})=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}=\sum_{j\in[J]}\sum_{i\in[I]}q_{ij}^{\star}=\sum_{j\in[J]}p_{j}=1,$

where the second equality holds because $q^{\star}_{ij}=0$ for all
$i\in\mathcal{I}_{j}^{0}\cup\mathcal{I}_{j}^{\infty}$, while the third
equality follows from the constraints of problem (22). More precisely, we have
$\mathbb{Q}^{\star}(z\in\mathcal{Z})=1$ because the constraints of (22) imply
that $f_{k}(\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})\leq 0$ whenever
$i\in\mathcal{I}^{+}_{j}$. In addition, one readily verifies that

$d_{c}(\mathbb{Q}^{\star},\widehat{\mathbb{P}})\leq\sum_{j\in[J]}\sum_{i\in\mathcal{I}^{+}_{j}}q_{ij}^{\star}c(\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star},\widehat{z}_{j})=\sum_{j\in[J]}\sum_{i\in[I]}q_{ij}^{\star}c(\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star},\widehat{z}_{j})\leq\varepsilon,$

where the first inequality holds because the transportation plan that moves
mass $q_{ij}^{\star}$ from $\widehat{z}_{j}$ to
$\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star}$ for all $j\in[J]$ and
$i\in\mathcal{I}^{+}_{j}$ is an admissible coupling of $\widehat{\mathbb{P}}$
and $\mathbb{Q}^{\star}$, the equality holds because
$\mathcal{I}_{j}^{\infty}=\emptyset$ and because
$q_{ij}^{\star}c(\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star},\widehat{z}_{j})=0c(\widehat{z}_{j}+0/0,\widehat{z}_{j})=0$
for all $i\in\mathcal{I}_{j}^{0}$ thanks to our conventions for perspective
functions, and the second inequality follows from the constraints of problem
(22). In summary, we have thus shown that
$\mathbb{Q}^{\star}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$. It
remains to be shown that $\mathbb{Q}^{\star}$ is optimal in (3). To this end,
note that

$\displaystyle\begin{aligned}
\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]\,&\geq\inf_{\theta\in\Theta}~{}\mathbb{E}_{\mathbb{Q}^{\star}}[\ell(\theta,Z)]\\\
&\geq\inf_{\theta\in\Theta}~{}\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})\\\
&=\inf_{\theta\in\Theta}~{}\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}^{\star}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})\\\
&\geq-\sum_{i\in[I]}\sum_{j\in[J]}q_{ij}^{\star}\ell_{i}^{*1}(\alpha_{ij}^{\star}/q_{ij}^{\star},\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})-\sum_{l\in[L]}\nu_{l}^{\star}g^{*}_{l}(\beta_{l}^{\star}/\nu_{l}^{\star})\\\
&=\inf_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]\geq\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)],\end{aligned}$
(44)

where the first inequality holds because
$\mathbb{Q}^{\star}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$, the
second inequality exploits Assumption 2.9 (ii), which implies that $\ell$
majorizes $\ell_{i}$ for every $i\in[I]$, and the first equality follows from
the properties of perspective functions and from our assumption that
$\mathcal{I}^{\infty}_{j}$ is empty. The third inequality then holds because
$(\\{\alpha_{ij}^{\star}\\}_{i,j},\\{\nu_{l}^{\star},\beta_{l}^{\star}\\}_{l})$
is feasible in (43), which is dual to the resulting minimization problem over
$\theta$, and because any dual feasible solution provides a lower bound on the
infimum of the primal problem. The second equality holds because the primal
DRO problem (1) and the finite convex program (22) share the same optimal
value, which was established in Step 1, while the fourth and last inequality
follows from weak duality. Hence, all inequalities in (44) are in fact
equalities, which proves that the optimal values of the primal and dual DRO
problems (1) and (3) coincide and that $\mathbb{Q}^{\star}$ solves (3).

Assume now that $\mathcal{I}_{j}^{\infty}\neq\emptyset$ for some $j\in[J]$,
and select any $i\in\mathcal{I}_{j}^{\infty}$. Since $q_{ij}^{\star}=0$, [70,
Theorem 8.6] implies that $\xi^{\star}_{ij}$ is a recession direction of
$\mathcal{Z}$ (see also [93, Lemma B.7 (ii)]), and since $\xi_{ij}^{\star}\neq
0$, the support set $\mathcal{Z}$ cannot be compact. Similarly, one readily
verifies that $c(z,\widehat{z})$ cannot grow superlinearly with $z$ for
otherwise the left hand side of the last constraint in (22) would evaluate to
infinity [93, Remark 6], which contradicts the feasibility of
$(\\{q_{ij}^{\star},\xi_{ij}^{\star},\alpha_{ij}^{\star}\\}_{i,j},\\{\nu_{l}^{\star},\beta_{l}^{\star}\\}_{l})$.
By Assumption 2.13, we may thus conclude that the feasible set $\Theta$ is
compact. Next, consider the discrete distributions

$\displaystyle\mathbb{Q}(n)=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}^{\infty}_{j}}q_{ij}(n)\,\delta_{z_{ij}(n)}$

indexed by $n\in\mathbb{N}$, where

$\displaystyle
q_{ij}(n)=\begin{cases}q_{ij}^{\star}(1-|\mathcal{I}_{j}^{\infty}|/n)&\text{if
}i\in\mathcal{I}_{j}^{+}\\\ p_{j}/n&\text{if
}i\in\mathcal{I}_{j}^{\infty}\end{cases}\quad\text{and}\quad
z_{ij}(n)=\begin{cases}\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star}&\text{if
}i\in\mathcal{I}_{j}^{+}\\\ \widehat{z}_{j}+n\hskip
0.43057pt\xi_{ij}^{\star}/p_{j}&\text{if
}i\in\mathcal{I}_{j}^{\infty}.\end{cases}$

Following [93, § 5], we now prove that $\mathbb{Q}(n)$ is feasible and
asymptotically optimal in (3) as $n$ increases. To this end, we first show
that $\mathbb{Q}(n)\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ for all
$n>\underline{n}=\max_{j\in[J]}|\mathcal{I}_{j}^{\infty}|$. It is easy to
verify that $\mathbb{Q}(n)$ is indeed a probability distribution for every
$n>\underline{n}$ because
$\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}^{\infty}_{j}}q_{ij}(n)=1$
and $q_{ij}(n)\geq 0$ for all
$i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}$ and $j\in[J]$ thanks to
the constraints of problem (22). In addition, $\mathbb{Q}(n)$ is supported on
$\mathcal{Z}$, that is, $z_{ij}(n)\in\mathcal{Z}$ for each $j\in[J]$ and
$i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}$. In particular, the
constraints of problem (22) imply that $\xi_{ij}^{\star}$ is a recession
direction of $\mathcal{Z}$ for every $i\in\mathcal{I}_{j}^{\infty}$ (see,
e.g., [93, Lemma B.7]). Hence, for any fixed $j\in[J]$ and
$i\in\mathcal{I}^{\infty}_{j}$, the distribution $\mathbb{Q}(n)$ sends a
decreasing probability mass $q_{ij(n)}=p_{j}/n$ along the ray emanating from
$\widehat{z}_{j}$ in the direction of $\xi_{ij}^{\star}$ without ever leaving
the support set $\mathcal{Z}$ as $n$ grows. Finally, for all
$n>\underline{n}$, one readily verifies that

$\displaystyle d_{c}(\mathbb{Q}(n),\widehat{\mathbb{P}})$
$\displaystyle\leq\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}}q_{ij}(n)\,c\big{(}z_{ij}(n),\widehat{z}_{j}\big{)}$
$\displaystyle=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}\left(1-\frac{|\mathcal{I}_{j}^{\infty}|}{n}\right)c\left(\widehat{z}_{j}+\frac{\xi_{ij}^{\star}}{q_{ij}^{\star}},\widehat{z}_{j}\right)+\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{\infty}}\frac{p_{j}}{n}c\left(\widehat{z}_{j}+n\frac{\xi_{ij}^{\star}}{p_{j}},\widehat{z}_{j}\right)$
$\displaystyle\leq\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}c\left(\widehat{z}_{j}+\frac{\xi_{ij}^{\star}}{q_{ij}^{\star}},\widehat{z}_{j}\right)+\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{\infty}}\lim_{n\to\infty}\frac{p_{j}}{n}c\left(\widehat{z}_{j}+n\frac{\xi_{ij}^{\star}}{p_{j}},\widehat{z}_{j}\right)$
$\displaystyle=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}}q_{ij}^{\star}c\left(\widehat{z}_{j}+\frac{\xi_{ij}^{\star}}{q_{ij}^{\star}},\widehat{z}_{j}\right)\leq\varepsilon,$

where the first inequality holds because the transportation plan that moves
mass $q_{ij}(n)$ from $\widehat{z}_{j}$ to $z_{ij}(n)$ for all $j\in[J]$ and
$i\in\mathcal{I}^{+}_{j}\cup\mathcal{I}^{\infty}_{j}$ is an admissible
coupling of $\widehat{\mathbb{P}}$ and $\mathbb{Q}(n)$, and the second
inequality holds because the transportation cost function is non-negative and
convex (see Assumption 2.9 (i)), which implies that both terms in the second
line of the above expression are non-decreasing in $n$. The last equality
follows from the definition of the perspective function
$q_{ij}^{\star}c(\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star},\widehat{z}_{j})$
for $q_{ij}^{\star}=0$, and the last inequality uses the constraints of (22).
Hence, $\mathbb{Q}(n)\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ for
all $n>\underline{n}$. It remains to be shown that $\mathbb{Q}(n)$ is
asymptotically optimal in (22). Using a similar reasoning as in (44), we
obtain

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}\;$
$\displaystyle\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]\geq\lim_{n\to\infty}\inf_{\theta\in\Theta}\mathbb{E}_{\mathbb{Q}(n)}[\ell(\theta,Z)]$
$\displaystyle\geq\lim_{n\to\infty}\inf_{\theta\in\Theta}\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}}q_{ij}(n)\ell_{i}\left(\theta,z_{ij}(n)\right)$
$\displaystyle=\inf_{\theta\in\Theta}\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}}q_{ij}^{\star}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})$
$\displaystyle=\inf_{\theta\in\Theta}\sum_{j\in[J]}\sum_{i\in[I]}q_{ij}^{\star}\ell_{i}(\theta,\widehat{z}_{j}+\xi_{ij}^{\star}/q_{ij}^{\star})$
$\displaystyle\geq\left\\{\begin{array}[]{cl}\max&\displaystyle-\sum_{j\in[J]}\sum_{i\in[I]}q_{ij}^{\star}\ell_{i}^{*1}(\alpha_{ij}/q_{ij}^{\star},\widehat{z}_{j}+\xi^{\star}_{ij}/q^{\star}_{ij})-\sum_{l\in[L]}\nu_{l}g^{*}_{l}(\beta_{l}/\nu_{l})\\\\[4.30554pt]
\operatorname*{s.t.}&\alpha_{ij}\in\mathbb{R}^{m},~{}\beta_{l}\in\mathbb{R}^{m},~{}\nu_{l}\in\mathbb{R}_{+}\quad\forall
i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty},\,j\in[J],\,l\in[L]\\\\[4.30554pt]
&\displaystyle\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}\cup\mathcal{I}_{j}^{\infty}}\alpha_{ij}+\sum_{l\in[L]}\beta_{l}=0\end{array}\right.$
$\displaystyle\geq-\sum_{i\in[I]}\sum_{j\in[J]}q^{\star}_{ij}\ell_{i}^{*1}(\alpha^{\star}_{ij}/q_{ij}^{\star},\widehat{z}_{j}+\xi^{\star}_{ij}/q^{\star}_{ij})-\sum_{l\in[L]}\nu^{\star}_{l}g^{*}_{l}(\beta^{\star}_{l}/\nu^{\star}_{l})$
$\displaystyle=\inf_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)]\geq\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\inf_{\theta\in\Theta}~{}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(\theta,Z)].$

Here, the first two inequalities hold because
$\mathbb{Q}(n)\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ for all
$n>\underline{n}$ and because $\ell$ majorizes $\ell_{i}$ for all $i\in[I]$.
The first equality follows from [71, Corollary 7.18], which applies because
$\Theta$ is compact, and from the observation that the uniform convergence of
a sequence of functions implies the convergence of their infima. The second
equality follows from the properties of perspective functions. The third
inequality follows from weak duality; see also problem (43). The fourth
inequality holds because
$(\\{\alpha_{ij}^{\star}\\}_{i,j},\\{\nu_{l}^{\star},\beta_{l}^{\star}\\}_{l})$
is feasible in the emerging dual maximization problem. The third equality
exploits our insight from Step 1 that the optimal values of the primal DRO
problem (1) and the finite convex program (22) match, and the fifth inequality
follows from weak duality. Again, we may conclude that all inequalities in the
above expression are in fact equalities, which proves that the optimal values
of the primal and dual DRO problems (1) and (3) coincide and that
$\mathbb{Q}(n)$ is asymptotically optimal in (3). ∎

As a byproduct, the proof of Proposition 2.14 reveals that if Assumptions 2.8,
2.9, 2.11 and 2.13 hold and if $\varepsilon>0$, then the infimum of the primal
DRO problem (1) equals the supremum of the dual DRO problem (3). Hence, strong
duality holds. The proof of Proposition 2.14 also reveals that the convex
reformulation (22) of the dual DRO problem (3) is always solvable and that any
maximizer of (22) can be used to construct a least favorable distribution that
is optimal in (3), if $\mathcal{I}^{\infty}_{j}=\emptyset$ for all $j\in[J]$,
or a sequence of distributions that are asymptotically optimal in (3), if
$\mathcal{I}^{\infty}_{j}\neq\emptyset$ for some $j\in[J]$. Finally, the proof
of Proposition 2.14 shows that Assumption 2.13 can be replaced with the
following condition.

######  Assumption 2.15 (Relaxed self service condition).

At least one of the following two conditions is satisfied: (i) $\Theta$ is
compact or (ii) the index set
$\mathcal{I}_{j}^{\infty}=\\{i\in[I]:q_{ij}^{\star}=0,\,\xi_{ij}^{\star}\neq
0\\}$ is non-empty for every $j\in[J]$, where
$(\\{q_{ij}^{\star},\xi_{ij}^{\star},\alpha_{ij}^{\star}\\}_{i,j},\\{\nu_{l}^{\star},\beta_{l}^{\star}\\}_{l})$
is a maximizer of problem (22).

The next theorem formalizes the above insights, thus identifying conditions
under which one can compute Nash equilibra for the DRO problem (1) by solving
the finite convex programs (11) and (22).

######  Theorem 2.16 (Computing Nash equilibria).

If Assumptions 2.8, 2.9, 2.11 and 2.15 hold and $\varepsilon>0$, then the
optimal values of the primal and dual DRO problems (1) and (3) match, and the
following hold.

  1. (i)

If
$(\theta^{\star},\lambda^{\star},\\{s_{j}^{\star}\\}_{j},\\{\zeta^{\ell\star}_{ij},\zeta^{c\star}_{ij}\\}_{i,j},\\{\tau_{ijk}^{\star},\zeta^{f\star}_{ijk}\\}_{i,j,k})$
solves (11), then $\theta^{\star}$ solves the primal DRO problem (1).

  2. (ii)

If
$(\\{\beta_{l}^{\star}\\}_{l},\\{\nu_{l}^{\star}\\}_{l},\\{q_{ij}^{\star}\\}_{i,j},\\{\xi_{ij}^{\star}\\}_{i,j},\\{\alpha_{ij}^{\star}\\}_{i,j})$
solves (22) with $\mathcal{I}_{j}^{\infty}=\emptyset$ for every $j\in[J]$,
then the discrete distribution
$\mathbb{Q}^{\star}=\sum_{j\in[J]}\sum_{i\in\mathcal{I}_{j}^{+}}q_{ij}^{\star}\delta_{\widehat{z}_{j}+{\xi_{ij}^{\star}}/{q_{ij}^{\star}}}$
solves the dual DRO problem (3).

###### Proof.

The claim follows from the proofs of Propositions 2.12 and 2.14 and the above
discussion. ∎

The conditions of Theorem 2.16 do not ensure that (11) is solvable and, even
though they guarantee the solvability of (22), they do not ensure that (22)
has a solution with $\mathcal{I}_{j}^{\infty}=\emptyset$ for every $j\in[J]$;
see the proofs of Propositions 2.12 and 2.14. However, Theorem 2.16 implies
that if (11) is solvable and (22) has a solution with
$\mathcal{I}^{\infty}_{j}=\emptyset$ for all $J\in[J]$, then the DRO problem
(1) admits a Nash equilibrium $(\theta^{\star},\mathbb{Q}^{\star})$, which can
be computed from the solutions of the finite convex programs (11) and (22).
The following lemma identifies easily checkable sufficient conditions for
problem (11) to be solvable.

######  Lemma 2.17 (Existence of $\theta^{\star}$).

Suppose that Assumptions 2.8, 2.9 and 2.11 hold and that $\varepsilon>0$.
Then, the finite convex program (11) is solvable if $\Theta$ is compact or if
(22) admits a Slater point.

###### Proof.

Assume first that $\Theta$ is compact. From the proof of Proposition 2.14 we
know that (27) and (33) are dual convex programs and that (33) admits a Slater
point. This implies via [93, Theorem 2 (i)] that (27) is solvable irrespective
of $\theta$. As (11) minimizes the minimum of (27) across all
$\theta\in\Theta$ and as $\Theta$ is compact, we may conclude that problem
(11) is solvable. Assume next that (22) admits a Slater point. As (22) is dual
to (11), it follows again from [93, Theorem 2 (i)] that (11) must be solvable.
∎

The next lemma identifies conditions ensuring that (22) has a solution with
$\mathcal{I}^{\infty}_{j}=\emptyset$ for all $J\in[J]$.

######  Lemma 2.18 (Existence of $\mathbb{Q}^{\star}$).

Suppose that Assumptions 2.8, 2.9 and 2.11 hold and that $\varepsilon>0$.
Then, the finite convex program (22) has a solution with
$\mathcal{I}^{\infty}_{j}=\emptyset$ for all $J\in[J]$ if the support set
$\mathcal{Z}$ is compact or if the transportation cost function
$c(z,\widehat{z})$ grows superlinearly with $z$.

###### Proof.

This is an immediate consequence of the proof of Proposition 2.14. ∎

Under the conditions of Lemma 2.17, any solution of (11) gives rise to a
robust decision $\theta^{\star}$, and under the conditions of Lemma 2.18, any
solution of (22) gives rise to a least favorable distribution
$\mathbb{Q}^{\star}$. By construction, $\theta^{\star}$ and
$\mathbb{Q}^{\star}$ form a Nash equilibrium for the DRO problem (1). The
constructive results of this section thus strengthen and complement the
existential results of Theorem 2.6 and Corollary 2.7. We emphasize, in
particular, that the conditions of Lemma 2.18 are reminiscent of the growth
condition specified in Assumption 2.1 (ii), which was instrumental in Theorem
2.6 to prove that the dual DRO problem (3) is solvable. Similarly, the
conditions of Lemma 2.17 are reminiscent of the compactness condition that was
needed in Corollary 2.7 to prove that the primal DRO problem (1) is solvable.

The results of this section readily extend to decision problems with loss
functions that display an arbitrary dependence on some of the uncertain
problem parameters provided that nature cannot perturb their marginal
distribution. Such decision problems naturally arise in machine learning
applications (see Section 4). Propositions 2.12 and 2.14 as well as Theorem
2.16 remain valid in this generalized setting with obvious minor modifications
but at the expense of a higher notational overhead; see Appendix A.

##  3 Regularization by Robustification

It is well known that many regularization schemes in statistics and machine
learning admit a robustness interpretation. Apart from carrying an aesthetic
appeal, such interpretations often lead to generalization bounds for the
optimizers of regularized learning models. This prompts us to seek a
comprehensive theory of regularization and optimal transport-based
robustification that unifies various specialized results scattered across the
existing literature and that rationalizes, for the first time, a broad range
of higher-order variation regularization schemes. In Section 3.1 we first
study the primal regularizing effects of robustification by relating the
worst-case expected loss to the expected loss under the reference distribution
adjusted by Lipschitz and higher-order variation regularization terms. In
Section 3.2 we then study the dual regularizing effects of robustification by
relating the worst-case expected loss to the expected value of a regularized
(e.g., smoothed) loss function under the reference distribution.

###  3.1 Primal Regularizating Effects of Robustification

In this section we will show that, under natural regularity conditions, the
worst-case expected loss across all distributions in a generic optimal
transport-based ambiguity set is bounded above by the sum of the expected loss
under the reference distribution and several regularization terms that
penalize $L^{p}$-norms and Lipschitz moduli of the higher-order derivatives of
the loss function. Our results generalize and unify several existing results,
which have revealed intimate connections between robustification and gradient
regularization [32], Hessian regularization [6] and Lipschitz regularization
[60]; see also [13, 32, 74, 75].

The subsequent discussion focuses on the inner maximization problem in (1),
where $\theta$ is fixed. For ease of exposition, we thus temporarily suppress
the dependence of the loss function on $\theta$ and use the shorthand notation
$\ell(z)$ throughout this section. In addition, we will also adopt the
following notational conventions. For any $k\in\mathbb{Z}_{+}$, we use
$D^{k}\ell(z)$ to denote the totally symmetric tensor of all $k$-th order
partial derivatives of $\ell(z)$. Accordingly,
$D^{k}\ell(z)[\xi_{1},\ldots,\xi_{k}]$ stands for the directional derivative
of $\ell(z)$ along the directions $\xi_{i}\in\mathbb{R}^{d}$ for $i\in[k]$. If
$\xi_{i}=\xi$ for all $i\in[k]$, then we use the shorthand
$D^{k}\ell(z)[\xi]^{k}$. Any norm $\|\cdot\|$ on $\mathbb{R}^{d}$ induces a
norm on the space of totally symmetric $k$-th order tensors through

$\displaystyle\|D^{k}\ell(z)\|$
$\displaystyle=\sup_{\xi_{1},\ldots,\xi_{k}}\left\\{\left|D^{k}\ell(z)[\xi_{1},\ldots,\xi_{k}]\right|:\|\xi_{i}\|\leq
1~{}\forall
i\in[k]\right\\}=\sup_{\xi}\left\\{\left|D^{k}\ell(z)[\xi]^{k}\right|:\|\xi\|\leq
1\right\\},$

where the second equality follows from the symmetry of $D^{k}\ell(z)$ [5, Satz
1]. By slight abuse of notation, we use the same symbol $\|\cdot\|$ for the
tensor norm induced by the vector norm $\|\cdot\|$.

The results of this section will depend on the following smoothness
conditions.

######  Assumption 3.1 (Smoothness properties of the loss function).

  1. (i)

The loss function $\ell(z)$ is $p$ times continuously differentiable, and
there exist $G>0$ and $p\in\mathbb{N}$ with $\ell(z)\leq G(1+\|z\|^{p})$,
$\|D^{k}\ell(z)\|\leq G(1+\|z\|^{p-k})$, $k\in[p-1]$, and
$\|D^{p}\ell(z)\|\leq G$ for all $z\in\mathcal{Z}$.

  2. (ii)

The tensor $D^{k}\ell(z)$ of $k$-th order partial derivatives is Lipschitz
continuous in $z$ for all $k\in[p-1]$.

We are now ready to state the main result of this section.

######  Theorem 3.2 (Regularization by robustification).

Suppose that Assumption 2.1 (i) holds. If there exists a norm $\|\cdot\|$ on
$\mathbb{R}^{d}$ such that $c(z,\widehat{z})$ satisfies Assumption 2.1 (ii)
for $d(z,\widehat{z})=\|z-\widehat{z}\|$ and such that $\ell(z)$ satisfies
Assumption 3.1 (i) with respect to $\|\cdot\|$, then the worst-case expected
loss satisfies

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]+\sum_{k=1}^{p-1}\frac{\varepsilon^{\frac{1}{p_{k}}}}{k!}\,\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\|D^{k}\ell(\widehat{Z})\|^{q_{k}}\right]^{\frac{1}{q_{k}}}+\frac{\varepsilon}{p!}\,\operatorname*{lip}(D^{p-1}\ell)<\infty,$
(45)

where $p_{k}=p/k$ and $q_{k}=p/(p-k)$ for all $k\in[p-1]$.

###### Proof.

Fix any $\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$, and use
$\pi^{\star}$ to denote an optimal coupling of $\mathbb{Q}$ and
$\widehat{\mathbb{P}}$, which exists thanks to [86, Theorem 4.1]. By the
defining properties of couplings, we have

$\displaystyle\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]-\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]=\int_{\mathcal{Z}\times\mathcal{Z}}\left[\ell(z)-\ell(\widehat{z})\right]\mathrm{d}\pi^{\star}(z,\widehat{z}).$

Representing the integrand as a Taylor series with Lagrange remainder yields

$\displaystyle\ell(z)-\ell(\widehat{z})$
$\displaystyle=\sum_{k=1}^{p-1}\frac{1}{k!}D^{k}\ell(\widehat{z})\left[z-\widehat{z}\right]^{k}+\frac{1}{p!}D^{p}\ell(\widehat{z}+t\cdot(z-\widehat{z}))\left[z-\widehat{z}\right]^{p}$
$\displaystyle\leq\sum_{k=1}^{p-1}\frac{1}{k!}\|D^{k}\ell(\widehat{z})\|\|z-\widehat{z}\|^{k}+\frac{1}{p!}\|D^{p}\ell(\widehat{z}+t\cdot(z-\widehat{z}))\|\|z-\widehat{z}\|^{p}$

for some $t\in(0,1)$ that depends (measurably) on $z$ and $\widehat{z}$ [45,
Theorem 2.2.5]. The inequality in the second line follows directly from the
multi-linearity of tensors and the definition of the tensor norm. By Hölder’s
inequality, the integral of the $k$-th term in the above sum against
$\pi^{\star}$ admits the estimate

$\displaystyle\int_{\mathcal{Z}\times\mathcal{Z}}\|D^{k}\ell(\widehat{z})\|\|z-\widehat{z}\|^{k}\mathrm{d}\pi^{\star}(z,\widehat{z})$
$\displaystyle\leq\left(\int_{\mathcal{Z}\times\mathcal{Z}}\|z-\widehat{z}\|^{p}\mathrm{d}\pi^{\star}(z,\widehat{z})\right)^{\frac{1}{p_{k}}}\left(\int_{\mathcal{Z}}\|D^{k}\ell(\widehat{z})\|^{q_{k}}\mathrm{d}\widehat{\mathbb{P}}(\widehat{z})\right)^{\frac{1}{q_{k}}}$
$\displaystyle\leq\varepsilon^{\frac{1}{p_{k}}}\left(\int_{\mathcal{Z}}\|D^{k}\ell(\widehat{z})\|^{q_{k}}\mathrm{d}\widehat{\mathbb{P}}(\widehat{z})\right)^{\frac{1}{q_{k}}},$

where $p_{k}=p/k$ and $q_{k}=p/(p-k)$. The second inequality follows from
Assumption 2.1 (ii), which ensures that
$c(z,\widehat{z})\geq\|z-\widehat{z}\|^{p}$ for all
$z,\widehat{z}\in\mathcal{Z}$, and from the definition of $\pi^{\star}$ as an
optimal coupling of $\widehat{\mathbb{P}}$ and
$\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$. A similar
reasoning based on Hölder’s inequality implies that

$\displaystyle\int_{\mathcal{Z}\times\mathcal{Z}}\|D^{p}\ell(\widehat{z}+t\cdot(z-\widehat{z}))\|\|z-\widehat{z}\|^{p}\mathrm{d}\pi^{\star}(z,\widehat{z})$
$\displaystyle\leq\sup_{\widehat{z}\in\mathcal{Z}}\|D^{p}\ell(\widehat{z})\|\int_{\mathcal{Z}\times\mathcal{Z}}\|z-\widehat{z}\|^{p}\mathrm{d}\pi^{\star}(z,\widehat{z})$
$\displaystyle\leq\varepsilon\sup_{\widehat{z}\in\mathcal{Z}}\|D^{p}\ell(\widehat{z})\|=\varepsilon\operatorname*{lip}(D^{p-1}\ell),$

where the dependence of $t$ on $z$ and $\widehat{z}$ is notationally
suppressed to avoid clutter. In summary, the above reasoning readily implies
that

$\displaystyle\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]-\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]\leq\sum_{k=1}^{p-1}\frac{\varepsilon^{\frac{1}{p_{k}}}}{k!}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\|D^{k}\ell(\widehat{Z})\|^{q_{k}}\right]^{\frac{1}{q_{k}}}+\frac{\varepsilon}{p!}\operatorname*{lip}(D^{p-1}\ell).$

Note that the right hand side of the resulting inequality is independent of
$\mathbb{Q}$. Thus, the inequality remains valid if we maximize its left hand
side across all $\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$,
which finally yields the upper bound in (45). To demonstrate that this upper
bound is finite, we observe that

$\displaystyle\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\|D^{k}\ell(\widehat{Z})\|^{q_{k}}\right]$
$\displaystyle\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[G(1+\|\widehat{Z}\|^{p-k})^{q_{k}}\right]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[G(2+\|\widehat{Z}\|)^{p}\right]$
$\displaystyle\leq
G^{\prime}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\|\widehat{Z}-\widehat{z}_{0}\|^{p}\right]\leq
G^{\prime}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[c(\widehat{Z},\widehat{z}_{0})\right]\leq\infty\quad\forall
k\in[p-1],$

where the first two inequalities follow from Assumption 3.1 (i) and the
definition of $q_{k}$, respectively. By the triangle inequality and the
binomial theorem, there is $G^{\prime}>0$ with $G(2+\|z\|)^{p}\leq
G^{\prime}(1+\|z-\widehat{z}_{0}\|^{p})$ for all $z\in\mathcal{Z}$, and this
justifies the third inequality. The fourth inequality exploits Assumption 2.1
(ii), which holds for $d(z,\widehat{z})=\|z-\widehat{z}\|$, and the fifth
inequality follows from Assumption 2.1 (i). Similarly, Assumption 3.1 (i)
implies that $\operatorname*{lip}(D^{p-1}\ell)\leq G<\infty$. Thus, the upper
bound in (45) is finite. ∎

Theorem 3.2 asserts that the worst-case expected loss with respect to a
generic optimal transport-based ambiguity set is bounded above by the sum of
the expected loss under the reference distribution, $p-1$ different variation
regularization terms, and a Lipschitz regularization term. The $k$-th
variation regularization term penalizes the $L^{q_{k}}$-norm of the tensor of
$k$-th order partial derivatives, and the Lipschitz regularization term
penalizes the Lipschitz modulus of the tensor of $(p-1)$-st order partial
derivatives of the loss. Variation regularizers such as regularizers
penalizing the gradients, Hessians or tensors of higher-order partial
derivatives are successfully used in various applications in machine learning.
For example, they emerge in the adversarial training of neural networks [36,
42, 57, 66, 85, 30] or in the stabilizing training of generative adversarial
networks [72, 63, 35]. In the context of image recovery, regularizers that
penalize higher-order partial derivatives are sometimes preferred to total
variation regularizers because they prevent undesirable staircase artifacts
[19]. For example, the ability of Hessian regularizers (or their finite
difference approximations) to mitigate staircase effects has been documented
in [53, 52]. More generally, regularizers based on higher-order partial
derivatives (or their finite difference approximations) can be used to
preserve or enhance various image features such as edges or ridges [41].
Theorem 3.2 gives these heuristic regularization schemes a theoretical
justification.

The next corollary shows that the estimate (45) can be simplified by upper
bounding all variation regularization terms by corresponding Lipschitz
regularizers.

######  Corollary 3.3 (Lipschitz regularization).

If all assumptions of Theorem 3.2 as well as Assumption 3.1 (ii) hold, then
the worst-case expected loss satisfies

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}[\ell(Z)]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]+\sum_{k=1}^{p-1}\frac{\varepsilon^{\frac{1}{p_{k}}}}{k!}\operatorname*{lip}(D^{k-1}\ell)<\infty.$
(46)

###### Proof.

Assumption 3.1 (ii) implies that
$D^{k}\ell(\widehat{Z})\leq\sup_{\widehat{z}\in\mathcal{Z}}\|D^{k}\ell(\widehat{z})\|=\operatorname*{lip}(D^{k-1}\ell)<\infty$
$\widehat{\mathbb{P}}$-almost surely for all $k\in[p-1]$. Substituting these
conservative upper bounds into (45) yields (46). ∎

We now specialize the results of Theorem 3.2 and Corollary 3.3 to Wasserstein
ambiguity sets.

######  Corollary 3.4 (Regularization by robustification over Wasserstein
balls).

If all assumptions of Theorem 3.2 hold and
$\mathbb{W}_{\varepsilon}(\widehat{\mathbb{P}})=\\{\mathbb{Q}\in\mathcal{P}(\mathcal{Z}):W_{p}(\mathbb{Q},\widehat{\mathbb{P}})\leq\varepsilon\\}$
is the $p$-th Wasserstein ball, then

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{W}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]+\sum_{k=1}^{p-1}\frac{\varepsilon^{k}}{k!}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\|D^{k}\ell(\widehat{Z})\|^{q_{k}}\right]^{\frac{1}{q_{k}}}+\frac{\varepsilon^{p}}{p!}\sup_{\widehat{z}\in\mathcal{Z}}\|D^{p}\ell(\widehat{z})\|<\infty,$
(47a) where $q_{k}=p/(p-k)$ for all $k\in[p-1]$. If additionally Assumption
3.1 (ii) holds, then
$\displaystyle\sup_{\mathbb{Q}\in\mathbb{W}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell(\widehat{Z})]+\sum_{k=1}^{p}\frac{\varepsilon^{k}}{k!}\operatorname*{lip}(D^{k-1}\ell)<\infty.$
(47b)

The proof of Corollary 3.4 follows from those of Theorem 3.2 and Corollary 3.3
and is thus omitted. To conclude, we show that the results of this section
generalize several bounds from the extant literature.

######  Remark 3.5 (Gradient regularization).

Corollary 3.4 is reminiscent of [32, Theorem 1], which shows that
robustification with respect to a Wasserstein ball
$\mathbb{W}_{\varepsilon_{J}}(\widehat{\mathbb{P}}_{J})$ of radius
$\varepsilon_{J}=\varepsilon/\sqrt{J}$ around the empirical distribution
$\widehat{\mathbb{P}}_{J}$ on $J$ independent training samples is
approximately equivalent to gradient regularization. Specifically, if $p>1$,
if the loss function $\ell(z)$ is piecewise smooth and its gradient $D\ell(z)$
obeys two growth conditions, and if the data-generating distribution has a
bounded density, we have

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{W}_{\varepsilon_{J}}(\widehat{\mathbb{P}}_{J})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[\ell(Z)\right]\;\approx\;\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}_{J}}[\ell(\widehat{Z})]+\varepsilon_{J}\,\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}_{J}}[\|D\ell(\widehat{Z})\|^{q}]^{\frac{1}{q}},$

where $q=p/(p-1)$ is the Hölder conjugate of $p$, and the approximation error
is bounded by a constant multiple of
$\max\\{\varepsilon_{J}^{2},\varepsilon_{J}^{p}\\}$ with high probability
under the data-generating distribution. Corollary 3.4 readily implies that the
right hand side of the above expression provides an upper bound on the worst-
case expected loss. This can be seen from (47a) by ignoring all terms of the
order $\mathcal{O}(\varepsilon_{J}^{k})$ for $k>1$.

######  Remark 3.6 (Hessian regularization).

Corollary 3.4 also generalizes [6, Remark 10], which establishes an upper
bound on the worst-case expected loss across all distributions in a
Wasserstein ball with $p>2$ and $d(z,\widehat{z})=\|z-\widehat{z}\|_{2}$. This
bound penalizes the gradient and the Hessian of the loss function and holds
only asymptotically for small $\varepsilon$. One readily verifies that this
bound can be obtained from (47a) by ignoring all terms of the order
$\mathcal{O}(\varepsilon^{k})$ for $k>2$ and by noting that
$\|D^{2}\ell(\widehat{z})\|_{2}=\lambda_{\text{max}}\left(D^{2}\ell(\widehat{z})\right)$.

######  Remark 3.7 (Lipschitz regularization).

For $p=1$ the upper bound in (47b) collapses to the sum of the expected loss
under the reference distribution and the Lipschitz modulus of $\ell(z)$
weighted by the Wasserstein radius $\varepsilon$. This bound is exact if
$\mathcal{Z}=\mathbb{R}^{d}$ and the loss function is convex [60, § 6.2], and
it gives classical regularization schemes in statistics and machine learning a
robustness interpretation [13, 32, 74, 75]. Note that the upper bound in (47b)
fails to be tight for $p>1$ even if $\ell(z)$ is convex.

###  3.2 Dual Regularizing Effects of Robustification

A distributionally robust learning model over linear hypotheses is a DRO
problem of the form

$\displaystyle\inf_{\theta\in\Theta}\;\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[L(\langle\theta,Z\rangle)\right],$
(48)

where $L:\mathbb{R}\to(-\infty,+\infty]$ is a univariate loss function. Thus,
(48) is a special case of (1) with $\ell(\theta,z)=L(\langle\theta,z\rangle)$.
Several important problems in operations research and machine learning can be
framed as instances of (48). Examples include portfolio optimization and
newsvendor problems, plain vanilla or kernelized regression and classification
problems, (linear) inverse problems, and phase retrieval problems. For problem
(48) to be well-defined, we assume throughout this section that Assumption 1.1
holds. Proposition 1.2 thus implies that the DRO problem (48) is equivalent to
the stochastic program

$\displaystyle\inf_{\theta\in\Theta,\,\lambda\geq
0}\;\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\ell_{c}(\theta,\lambda,\widehat{Z})\right],$
(49)

whose objective function involves the expectation of the $c$-transform
$\ell_{c}(\theta,\lambda,\widehat{Z})$ under the reference distribution
$\widehat{\mathbb{P}}$. Throughout this section we also assume that
$\mathcal{Z}=\mathbb{R}^{d}$, and thus the $c$-transform satisfies

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})=\sup_{z\in\operatorname*{dom}(c(\cdot,\widehat{z}\,))}L(\langle\theta,z\rangle)-\lambda
c(z,\widehat{z}).$ (50)

While the conservative bound (45) derived in Section 3.1 exposes the primal
regularizing effects, the reformulation (49) exposes the dual regularizing
effects of robustification. Indeed, from a primal perspective, robustification
essentially amounts to adding various regularization terms to the expected
loss, and from a dual perspective, robustification essentially amounts to
replacing the loss with its $c$-transform, which is best viewed as a
regularized version of the loss function, and tuning the corresponding
regularization parameter $\lambda$. The main goal of this section is to shed
more light on this dual perspective on robustification. Specifically, we will
show that the $c$-transform $\ell_{c}$ can often be expressed in terms of a
suitable envelope of $L$ such as the Pasch-Hausdorff envelope or the Moreau
envelope. In addition, we will show how the formulas (49) and (50) can be
exploited algorithmically. Indeed, in Section 2.2 we showed that problem (48)
is equivalent to a finite convex program if all convexity conditions of
Assumption 2.9 are satisfied. In this section we will show that, as its
objective function depends only on a one-dimensional projection of $z$,
problem (48) can sometimes be solved efficiently even if $L$ fails to be
(piecewise) concave or even if $c$ fails to be convex.

We now leverage techniques from nonconvex optimization to recast the (possibly
nonconvex) problem (50) for evaluating the $c$-transform as a univariate
optimization problem.

######  Theorem 3.8 (Nonconvex duality).

The $c$-transform (50) admits the following dual reformulations.

  1. (i)

If $L$ is proper, convex and lower semi-continuous, while $c$ is proper and
lower semi-continuous, then
$\ell_{c}(\theta,\lambda,\widehat{z})=\sup_{\gamma\in\operatorname*{dom}(L^{*})}\;\lambda
c^{*1}(\gamma\theta/\lambda,\widehat{z})-L^{*}(\gamma)$, which is convex in
$(\theta,\lambda)$ for any $\widehat{z}$.

  2. (ii)

If $c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$ for a norm $\|\cdot\|$ and $p\geq
1$, then
$\ell_{c}(\theta,\lambda,\widehat{z})=\sup_{\gamma\in\mathbb{R}}\;L\big{(}\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*}\big{)}-\lambda\hskip
0.43057pt|\gamma|^{p}.$

The reformulations of the nonconvex problem (50) derived in Theorem 3.8 are
generically also nonconvex. As these reformulations involve conjugate
functions and dual norms, respectively, we refer to them as dual problems even
though they constitute maximization problems like the primal problem (50).
These dual problems may be preferable to the primal problem (50) as they
involve only a scalar decision. We remark that Theorem 3.8 (ii) generalizes
[16, Theorem 1], where $\|\cdot\|$ is a Mahalanobis norm and $p=2$. Indeed,
Theorem 3.8 (ii) holds for arbitrary norms $\|\cdot\|$ and exponents $p$.

###### Proof of Theorem 3.8.

If $\lambda>0$, then assertion (i) follows from a classical duality result for
nonconvex optimization problems due to Toland [82, § 3.1]. In order to keep
this paper self-contained, we nevertheless provide a short proof. Note first
that $L^{**}=L$ thanks to [70, Theorem 12.2], which applies because $L$ is
proper, convex and lower semi-continuous. Thus, the $c$-transform can be
reformulated as

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle=\sup_{z\in\operatorname*{dom}(c(\cdot,\widehat{z}))}\;L^{**}(\langle\theta,z\rangle)-\lambda
c(z,\widehat{z})$
$\displaystyle=\sup_{z\in\operatorname*{dom}(c(\cdot,\widehat{z}))}\;\sup_{\gamma\in\operatorname*{dom}(L^{*})}\;\gamma\langle\theta,z\rangle-L^{*}(\gamma)-\lambda
c(z,\widehat{z})$
$\displaystyle=\sup_{\gamma\in\operatorname*{dom}(L^{*})}\;\sup_{z\in\operatorname*{dom}(c(\cdot,\widehat{z}))}\langle\gamma\theta,z\rangle-\lambda
c(z,\widehat{z})-L^{*}(\gamma)$
$\displaystyle=\sup_{\gamma\in\operatorname*{dom}(L^{*})}\;\lambda
c^{*1}(\gamma\theta/\lambda,\widehat{z})-L^{*}(\gamma).$

where the second equality holds because the biconjugate $L^{**}$ is defined as
the conjugate of $L^{*}$ and the last equality follows from the elementary
insight that the partial conjugate of $\lambda c(\cdot,\widehat{z})$ coincides
with $\lambda c^{*1}(\cdot/\lambda,\widehat{z})$. This establishes the claim
for $\lambda>0$. Note that the restriction to $\operatorname*{dom}(L^{*})$ in
the last maximization problem is necessary because the objective is undefined
if $\lambda c^{*1}(\gamma\theta/\lambda,\widehat{z})=L^{*}(\gamma)=\infty$.

Assume now that $\lambda=0$. For clarity of exposition we define
$\Phi(z)=c(z,\widehat{z})$ for $\widehat{z}$ fixed. As $L^{**}=L$ and as
$0c(z,\widehat{z})=0\Phi(z)=0$ throughout $\operatorname*{dom}(\Phi)$, the
$c$-transform can now be reformulated as

$\displaystyle\ell_{c}(\theta,0,\widehat{z})=\sup_{z\in\operatorname*{dom}(\Phi)}L^{**}(\langle\theta,z\rangle)=\sup_{z\in\operatorname*{dom}(\Phi)}\;\sup_{\gamma\in\operatorname*{dom}(L^{*})}\langle\gamma\theta,z\rangle-L^{*}(\gamma)=\sup_{\gamma\in\operatorname*{dom}(L^{*})}\delta^{*}_{\operatorname*{dom}(\Phi)}(\gamma\theta)-L^{*}(\gamma).$

The desired reformulation follows if we can show that
$\delta^{*}_{\operatorname*{dom}(\Phi)}(\gamma\theta)=0\Phi^{*}(\gamma\theta/0)=0c^{*1}(\gamma\theta/0,\widehat{z})$.
To this end, note first that $0\in\operatorname*{dom}(\Phi^{*})$ because
$\Phi$ is non-negative. Thus, we have

$\displaystyle\delta^{*}_{\operatorname*{dom}(\Phi)}(\gamma\theta)$
$\displaystyle=\sup_{\Delta\in\mathbb{R}^{d}}\gamma\langle\theta,\Delta\rangle-\inf_{\alpha>0}\Phi(\Delta)/\alpha\;=\;\sup_{\alpha>0}\sup_{\Delta\in\mathbb{R}^{d}}\gamma\langle\theta,\Delta\rangle-\Phi(\Delta)/\alpha$
$\displaystyle=\lim_{\alpha\to+\infty}\alpha^{-1}\sup_{\Delta\in\mathbb{R}^{d}}\alpha\gamma\langle\theta,\Delta\rangle-\Phi(\Delta)\;=\;\lim_{\alpha\to+\infty}\Phi^{*}(\alpha\gamma\theta)/\alpha$
$\displaystyle=\;0\Phi^{*}(\gamma\theta/0)\;=\;0c^{*1}(\gamma\theta/0,\widehat{z}),$

where the first equality exploits the definition of the support function and
the non-negativity of $\Phi$, which implies that
$\inf_{\alpha>0}\Phi(\Delta)/\alpha=\delta_{\operatorname*{dom}(\Phi)}$,
whereas the second, third and fourth equalities follow from elementary
reformulations and from the definition of the conjugate. The fifth equality
holds thanks to [70, Corollary 8.5.2 & Theorem 13.3]. As
$0\in\operatorname*{dom}(\Phi^{*})$, these results ensure that the recession
function $\lim_{\alpha\to+\infty}\Phi^{*}(\alpha\gamma\theta)/\alpha$ of
$\Phi^{*}$ coincides with the support function
$\delta^{*}_{\operatorname*{dom}(\Phi^{**})}(\gamma\theta)$ of the domain of
$\Phi^{**}$, which in turn is our definition of $0\Phi^{*}(\gamma\theta/0)$.
The last equality follows from the definition of $\Phi$.

It remains to be shown that $\ell_{c}(\theta,\lambda,\widehat{z})$ is convex
in $(\theta,\lambda)$. This is evident from our dual reformulation of
$\ell_{c}(\theta,\lambda,\widehat{z})$, however, because convexity is
preserved by maximization. Hence, assertion (i) follows.

As for assertion (ii), define the auxiliary function $\Psi(z)=\|z\|^{p}$ for
$z\in\mathbb{R}^{d}$, and recall that $L$ is an arbitrary (possibly nonconvex)
proper function. In this case, the $c$-transform can be reformulated as

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle=\sup_{z\in\mathbb{R}^{d}}\;L(\langle\theta,z\rangle)-\lambda\Psi(z-\widehat{z})$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;\sup_{\Delta\in\mathbb{R}^{d}}\big{\\{}L(\langle\theta,\widehat{z}\rangle+\gamma)-\lambda\Psi(\Delta):\langle\theta,\Delta\rangle=\gamma\big{\\}}$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;\sup_{\Delta\in\mathbb{R}^{d}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)-\lambda\Psi(\Delta)+\beta\langle\theta,\Delta\rangle-\beta\gamma.$

In order to justify the third equality, consider the two maximization problems
over $\gamma$ in the second and the third lines of the above expression. If
$\theta=0$, then $\gamma=0$ is the only feasible solution in both problems,
and one readily verifies that the corresponding objective function values
coincide. If $\theta\neq 0$, on the other hand, then the objective functions
of the two problems coincide for every fixed $\gamma\in\mathbb{R}^{d}$ due to
strong Lagrangian duality [10, Proposition 5.3.1], which applies because the
primal maximization problem over $\Delta$ in the second line is convex and
feasible and because every feasible solution constitutes a Slater point.
Recalling the definitions of conjugates and perspectives then yields

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)+\Big{(}\displaystyle\sup_{\Delta\in\mathbb{R}^{d}}\;\beta\langle\theta,\Delta\rangle-\lambda\Psi(\Delta)\Big{)}-\beta\gamma$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)+\lambda\Psi^{*}(\beta\theta/\lambda)-\beta\gamma.$
(51)

To simplify (51), we assume first that $p=1$ (Case I) and later that $p>1$
(Case II).

Case I ($p=1$): As $\Psi(\cdot)=\|\cdot\|$ is a norm, one can show that
$\Psi^{*}(\cdot)=\delta_{C}(\cdot)$ is the indicator function of the dual norm
ball $C=\\{\theta\in\mathbb{R}^{d}:\|\theta\|_{*}\leq 1\\}$. If $\lambda>0$
and $\theta\neq 0$, we can thus re-express (51) as

$\displaystyle\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)+\lambda\delta_{C}(\beta\theta/\lambda)-\beta\gamma$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;\left\\{L(\langle\theta,\widehat{z}\rangle+\gamma)-\beta\gamma:\|\beta\theta\|_{*}\leq\lambda\right\\}$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)-\lambda|\gamma|/\|\theta\|_{*}$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|,$

where the second equality holds because the constraint
$\|\beta\theta\|_{*}\leq\lambda$ is equivalent to
$|\beta|\leq\lambda/\|\theta\|_{*}$, while the third equality follows form the
variable substitution $\gamma\leftarrow\gamma/\|\theta\|_{*}$. If $\lambda>0$
and $\theta=0$, on the other hand, then
$\lambda\Psi^{*}(\beta\theta/\lambda)=\lambda\Psi^{*}(0)=0$, and thus we can
re-express (51) as

$\displaystyle\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;\beta\gamma-L(\gamma)=-L(0)=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,z\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|.$

Here, the first equality holds because $\gamma=0$ is the only feasible
solution of the maximization problem on the left hand side, and the second
equality holds because $\theta=0$, which implies that the maxization problem
on the right hand side is also solved by $\gamma=0$. If $\lambda=0$ and
$\theta\neq 0$, then $\lambda\Psi^{*}(\beta\theta/\lambda)$ simplifies to
$0\Psi^{*}(\beta\theta/0)=\delta^{*}_{\mathbb{R}^{d}}(\beta\theta)=\delta_{\\{0\\}}(\beta\theta)$
thanks to our conventions for perspective functions, and (51) becomes

$\displaystyle\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|,$

where the first equality exploits the substitution
$\gamma\leftarrow\gamma/\|\theta\|_{*}$, and the second equality holds because
$\lambda=0$. If $\lambda=0$ and $\theta=0$, finally, then a similar reasoning
reveals that (51) reduces to
$L(\gamma)=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|$.
This completes the proof of assertion (ii) for $p=1$.

Case II ($p>1$): By [93, Lemma B.8 (ii)], the conjugate of
$\Psi(\cdot)=\|\cdot\|^{p}$ is given by
$\Psi^{*}(\cdot)=h(q)\|\cdot\|_{*}^{q}$, where $h(p)=(p-1)^{p-1}/p^{p}$ and
$q>0$ is the Hölder conjugate of $p$. If $\lambda>0$ and $\theta\neq 0$, (51)
reduces to

$\displaystyle\sup_{\gamma\in\mathbb{R}}\;\inf_{\beta\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)+h(q)\lambda^{1-q}\|\theta\|_{*}^{q}|\beta|^{q}-\beta\gamma$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma)-\lambda\left|\gamma/\|\theta\|_{*}\right|^{p}$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|^{p},$

where the two equalities follow from a tedious analytical calculation and form
the substitution $\gamma\leftarrow\gamma/\|\theta\|_{*}$, respectively. If
$\lambda=0$ or $\theta=0$, then we can proceed exactly as in Case I to prove
that (51) is equivalent to
$\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|^{p}$.
This completes the proof of assertion (ii). ∎

Theorem 3.8 shows that, in the context of linear prediction models, evaluating
the $c$-transform $\ell_{c}$ is quite generally equivalent to solving a
univariate maximization problem. If this maximization problem is easy to
solve, then the stochastic program (49) equivalent to the DRO problem (48) can
be addressed with stochastic gradient descent-type algorithms even if the
reference distribution fails to be discrete and even if the convexity
assumptions of Section 2.2 fail to hold. Specifically, if the univariate
maximization problem that evaluates the $c$-transform $\ell_{c}$ can be solved
analytically, then one may use the envelope theorem [26, Theorem 2.16] to
generate stochastic subgradients for the objective function of (49). In this
case, the stochastic program (49) is amenable to standard (projected)
stochastic subgradient methods; see, e.g., [69]. If the $c$-transform
evaluation problem can only be solved approximately via a numerical procedure
such as a grid-search method, a bisection algorithm or a sequential convex
optimization approach, then the envelope theorem only provides inexact
stochastic subgradients. In this case, and provided that $L$ is convex, one
can use the stochastic subgradient descent algorithms with inexact gradient
oracles studied in [16, § 3] and [81, § 4] to solve problem (49). As an
example, in Appendix B we identify conditions under which the univariate
$c$-transform evaluation problem purported in Theorem 3.8 (ii) is a convex
maximization problem even if $L$ is convex instead of concave.

The $c$-transform $\ell_{c}(\theta,\lambda,\widehat{z})$ defined in (50) can
be viewed as an approximation of
$\ell(\theta,\widehat{z})=L(\langle\theta,\widehat{z}\rangle)$, where the
parameter $\lambda$ controls the approximation error. If
$c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$ for some $p\geq 1$, then the
$c$-transform is closely related to the $p$-th envelope
$L_{p}:\mathbb{R}\times\mathbb{R}_{+}\to[-\infty,+\infty]$ of $L$, which is
defined via

$\displaystyle
L_{p}(s,\lambda)=\sup_{s^{\prime}\in\mathbb{R}}\;L(s^{\prime})-\lambda|s-s^{\prime}|^{p}.$

The next proposition uses Theorem 3.8 (ii) to formalize this relation and
specializes the strong duality result of Proposition 1.2 to DRO problems of
the form (48) with norm-based transportation costs.

######  Proposition 3.9 (Strong duality for DRO problems of the form (48)).

Assume that $\mathcal{Z}=\mathbb{R}^{d}$, that
$c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$, where $p\geq 1$ and $\|\cdot\|$ is
an arbitrary norm, and that $\ell(\theta,z)=L(\langle\theta,z\rangle)$, where
the univariate loss function $L$ is proper and upper semi-continuous and
satisfies $L(s)\leq C(1+|s|^{p})$ for some $C\geq 0$ and all $s\in\mathbb{R}$.
If additionally Assumption 1.1 holds, then we have

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[L(\langle\theta,Z\rangle)\right]=\inf_{\lambda\geq
0}\lambda\varepsilon\|\theta\|_{*}^{p}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[L_{p}(\langle\theta,\widehat{Z}\rangle,\lambda)\right].$
(52)

###### Proof.

If $\theta=0$, then the left hand side of (52) equals $L(0)$, and the right
hand side of (52) evaluates to

$\inf_{\lambda\geq
0}L_{p}(0,\lambda)=\lim_{\lambda\to+\infty}L_{p}(0,\lambda)=L(0),$

where the first equality holds because $L_{p}(s,\lambda)$ is non-increasing in
$\lambda$ for any fixed $s$, whereas the second equality follows from Lemma
C.1. This establishes the claim for $\theta=0$. In the remainder of the proof
we may thus assume that $\theta\neq 0$. By Proposition 1.2, which applies
thanks to Assumption 1.1, the worst-case expected loss on the left hand side
of (52) matches the optimal value of the stochastic program in (2), which
involves the $c$-transform (50). By Theorem 3.8 (ii), we further have

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle=\sup_{\gamma\in\mathbb{R}}\;L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda|\gamma|^{p}=\sup_{\gamma\in\mathbb{R}}\;L(\gamma)-\frac{\lambda}{\|\theta\|_{*}^{p}}|\gamma-\langle\theta,\widehat{z}\rangle|^{p}=L_{p}\left(\langle\theta,\widehat{z}\rangle,{\lambda}/{\|\theta\|_{*}^{p}}\right),$

where the second and the third equalities follow the variable substitution
$\gamma\leftarrow\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*}$ and
the definition of $L_{p}$, respectively. Substituting this expression for the
$c$-transform into (2) finally yields

$\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim{\mathbb{Q}}}\left[L(\langle\theta,Z\rangle)\right]=\inf_{\lambda\geq
0}\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[L_{p}\left(\langle\theta,\widehat{z}\rangle,{\lambda}/{\|\theta\|_{*}^{p}}\right)\right]=\inf_{\lambda\geq
0}\lambda\varepsilon\|\theta\|_{*}^{p}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[L_{p}(\langle\theta,\widehat{Z}\rangle,\lambda)\right],$

where the second equality follows from the variable substitution
$\lambda\leftarrow\lambda/\|\theta\|_{*}^{p}$. This establishes the claim for
$\theta\neq 0$. In summary, we have thus shown that (52) holds indeed for
every $\theta\in\mathbb{R}^{d}$. ∎

####  3.2.1 Pasch-Hausdorff Envelope

Throughout this section we assume that all conditions of Proposition 3.9 hold
and that $p=1$. In this case, $L_{1}(\cdot,\lambda)$ is usually called the
Pasch-Hausdorff envelope of $L$. One can show that $L_{1}(\cdot,\lambda)$
coincides with the smallest $\lambda$-Lipschitz continuous majorant of $L$ or
evaluates to $+\infty$ if no such majorant exists [7, Proposition 12.17].
Under the conditions of this section, the univariate minimizaton problem on
the right hand side of (52) can sometimes be solved analytically. This allows
us to recover—in a unified and simplified manner—several reformulation results
from the recent literature on Wasserstein DRO.

######  Example 3.10 (Aymptotically steep Lipschitz continuous loss).

If the asymptotic linear growth rate of the loss function $L$, which is
defined as $\limsup_{|s|\to\infty}L(s)/|s|$, coincides with the Lipschitz
modulus of $L$, then the Pasch-Hausdorff envelope of $L$ satisfies
$L_{1}(s,\lambda)=L(s)$ if $\lambda\geq\operatorname*{lip}(L)$ and
$L_{1}(s,\lambda)=+\infty$ otherwise. To see this, assume first that
$\lambda\geq\operatorname*{lip}(L)$. In that case, we have

$\displaystyle L(\langle\theta,\widehat{z}\rangle)$
$\displaystyle\leq\sup_{\gamma\in\mathbb{R}}\;L(\gamma)-\lambda|\gamma-\langle\theta,\widehat{z}\rangle|\leq\sup_{\gamma\in\mathbb{R}}\;L\big{(}\langle\theta,\widehat{z}\rangle\big{)}-\big{(}\lambda-\operatorname*{lip}(L)\big{)}|\gamma-\langle\theta,\widehat{z}\rangle|=L\big{(}\langle\theta,\widehat{z}\rangle\big{)},$

where the second inequality holds because the loss function $L$ is Lipschitz
continuous with Lipschitz modulus $\operatorname*{lip}(L)$. If
$\lambda<\operatorname*{lip}(L)$, on the other hand, then we have

$\displaystyle L_{1}(\langle\theta,\widehat{z}\rangle,\lambda)$
$\displaystyle\geq\limsup_{|\gamma|\to\infty}\;L(\gamma)-\lambda|\gamma-\langle\theta,\widehat{z}\rangle|$
$\displaystyle=L(\langle\theta,\widehat{z}\rangle)+\limsup_{|\gamma|\to\infty}|\gamma-\langle\theta,\widehat{z}\rangle|\left(\frac{L(\gamma)-L(\langle\theta,\widehat{z}\rangle)}{|\gamma-\langle\theta,\widehat{z}\rangle|}-\lambda\right)$
$\displaystyle=L(\langle\theta,\widehat{z}\rangle)+\limsup_{|\gamma|\to\infty}|\gamma-\langle\theta,\widehat{z}\rangle|\left(\operatorname*{lip}(L)-\lambda\right)=+\infty,$

where the second inequality holds because the asymptotic linear growth rate of
$L$ coincides with $\operatorname*{lip}(L)$. Hence, the objective function in
the minimization problem on the right hand side of (52) evaluates to $+\infty$
whenever $\lambda<\operatorname*{lip}(L)$. As $\varepsilon\|\theta\|_{*}\geq
0$, we thus have $\lambda=\operatorname*{lip}(L)$ at optimality, and (52)
simplifies to

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[L(\langle\theta,Z\rangle)\right]=\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[L(\langle\theta,\widehat{Z}\rangle)]+\varepsilon\operatorname*{lip}(L)\|\theta\|_{*}.$
(53)

Hence, the worst-case expected loss over a 1-Wasserstein ball of radius
$\varepsilon$ coincides exactly with the expected loss under the reference
distribution adjusted by the regularization term
$\varepsilon\operatorname*{lip}(L)\|\theta\|_{*}$. This result strengthens the
inequality derived in Corollary 3.4 for $p=1$ to an equality. It was first
discovered in the context of distributionally robust linear regression [74],
where the random vector $Z=(X,Y)\in\mathbb{R}^{d}$ consists of a multi-
dimensional input $X\in\mathbb{R}^{d-1}$ and a scalar output $Y\in\mathbb{R}$,
the decision $\theta=(\theta_{x},\theta_{y})\in\mathbb{R}^{d}$ consists of the
weight vector $\theta_{x}\in\mathbb{R}^{d-1}$ of a linear predictor and the
constant $\theta_{y}=-1$, while the prediction loss
$L(\langle\theta,Z\rangle)=L(\langle\theta_{x},X\rangle-Y)$ is determined by a
Lipschitz continuous convex function $L$. Note that convexity is a simple
sufficient condition for the asymptotic linear growth rate of $L$ to coincide
with $\operatorname*{lip}(L)$. In the context of distributionally robust
linear classification, where the output $Y$ is restricted to $+1$ or $-1$ and
the prediction loss is given by $L(Y\langle\theta,X\rangle)$, it has further
been shown that

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{(X,Y)\sim\mathbb{Q}}\left[L(Y\langle\theta,X\rangle)\right]=\mathbb{E}_{(\widehat{X},\widehat{Y})\sim\widehat{\mathbb{P}}}\left[L(\widehat{Y}\langle\theta,\widehat{X}\rangle)\right]+\varepsilon\operatorname*{lip}(L)\|\theta\|_{*}$

whenever the transportation cost function satisfies
$c((x,y),(\widehat{x},\widehat{y}))=\|x-\widehat{x}\|$ if $y=\widehat{y}$;
$=+\infty$ if $y\neq\widehat{y}$, where $\|\cdot\|$ is an arbitrary norm on
the input space [74, 75]. In this case, the output $Y$ has the same marginal
under every distribution
$\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ as under the
reference distribution $\widehat{\mathbb{P}}$. The above identity can be
derived by repeating the arguments that led to (53) with obvious minor
modifications. Details are omitted for brevity. The general identity (53) for
nonconvex loss functions whose asymptotic linear growth rate coincides with
their Lipschitz modulus was first established in [32, Corollary 2].

######  Example 3.11 (Zero-one loss).

One readily verifies that the Pasch-Hausdorff envelope of the zero-one loss
$L(s)=\mathds{1}_{\\{s\leq 0\\}}$ satisfies
$L_{1}(s,\lambda)=\max\\{0,1-\max\\{0,\lambda s\\}\\}$. By Proposition 3.9, we
thus have

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{Q}\left(\langle\theta,Z\rangle\leq
0\right)$
$\displaystyle=\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[L(\langle\theta,Z\rangle)\right]$
$\displaystyle=\min_{\lambda\geq
0}\;\lambda\varepsilon\|\theta\|_{*}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\max\\{0,1-\max\\{0,\langle\lambda\theta,\widehat{Z}\rangle\\}\\}\right].$

If $\Theta$ is a cone, then the scaling factor $\lambda$ can be eliminated by
using the variable substitution $\theta^{\prime}\leftarrow\lambda\theta$. In
this case, the DRO problem reduces a stochastic program under the reference
distribution, that is,

$\displaystyle\inf_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{Q}\left(\langle\theta,Z\rangle\leq
0\right)=\inf_{\theta^{\prime}\in\Theta}\varepsilon\|\theta^{\prime}\|_{*}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\max\\{0,1-\max\\{0,\langle\theta^{\prime},\widehat{Z}\rangle\\}\\}\right].$

The above identity was first derived in the context of distributionally robust
linear classification [40] using recent results on ambiguous chance
constraints and their relation to conditional value-at-risk constraints [89].
Our derivation based on the Pasch-Hausdorff envelope is new and shorter.

####  3.2.2 Moreau Envelope

Throughout this section we assume that all conditions of Proposition 3.9 hold
and that $p=2$. In this case, $L_{2}(s,\lambda)$ is termed the Moreau envelope
of $L$. Under the conditions of this section, the univariate minimizaton
problem on the right hand side of (52) can be solved analytically in
interesting special cases, which leads again to simplified derivations of
existing reformulation results.

######  Example 3.12 (Quadratic loss).

The Moreau envelope of the quadratic loss function $L(s)=s^{2}$ satisfies
$L_{2}(s,\lambda)=\lambda s^{2}/(\lambda-1)$ if $\lambda>1$,
$L_{2}(s,\lambda)=+\infty\cdot\mathds{1}_{\\{s\neq 0\\}}$ if $\lambda=1$, and
$L_{2}(s,\lambda)=+\infty$ if $0\leq\lambda\leq 1$. If we assume that
$\widehat{\mathbb{P}}(\langle\theta,\widehat{Z}\rangle\neq 0)>0$ to rule out
trivialities, then Proposition 3.9 implies that

$\displaystyle\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{E}_{Z\sim\mathbb{Q}}\left[L(\langle\theta,Z\rangle)\right]=\min_{\lambda>1}\;\lambda\varepsilon\|\theta\|_{*}^{2}+\frac{\lambda}{\lambda-1}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[(\langle\theta,\widehat{Z}\rangle)^{2}\right]=\left(\sqrt{\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[(\langle\theta,\widehat{Z}\rangle)^{2}\right]}+\sqrt{\varepsilon}\|\theta\|_{*}\right)^{2}.$

The second equality in the above expression holds because the minimization
problem over $\lambda$ is solved analytically by
$\lambda^{\star}=1+\sqrt{\varepsilon}\|\theta\|_{*}(\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[(\langle\theta,\widehat{Z}\rangle)^{2}])^{-1/2}$.
This identity was first discovered in the context of distributionally robust
least squares regression; see [13, Proposition 2].

######  Example 3.13 (Zero-one loss).

The Moreau envelope of the zero-one loss $L(s)=\mathds{1}_{\\{s\leq 0\\}}$ is
given by
$L_{2}(s,\lambda)=\max\\{0,1-\sqrt{\lambda}s\max\\{0,\sqrt{\lambda}s\\}\\}$.
If $\Theta$ is a cone, then, in analogy to Example 3.11, we can use
Proposition 3.9 and the variable substitution
$\theta^{\prime}\leftarrow\sqrt{\lambda}\theta$ to conclude that

$\displaystyle\inf_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}\mathbb{Q}\left(\langle\theta,Z\rangle\leq
0\right)$
$\displaystyle=\inf_{\theta^{\prime}\in\Theta}\varepsilon\|\theta^{\prime}\|_{*}^{2}+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\max\left\\{0,1-\langle\theta^{\prime},\widehat{Z}\rangle\max\\{0,\langle\theta^{\prime},\widehat{Z}\rangle\\}\right\\}\right].$

##  4 Numerical Experiments

All linear and second-order cone programs considered in our experiments are
implemented in Python and solved with Gurobi 10.0.0 on a $2.4$ GHz quad-core
machine with $8$ GB RAM. To ensure reproducibility, all source codes are made
available at https://github.com/sorooshafiee/regularization_with_OT.

###  4.1 Nash Equilibria

We first illustrate the computation of Nash equilibria between a statistician
and nature in the context of a distributionally robust support vector machine
problem. We thus assume that $Z=(X,Y)\in\mathbb{R}^{d}$ consists of a feature
vector $X\in\mathcal{X}\subseteq\mathbb{R}^{d-1}$ and a label
$Y\in\mathcal{Y}=\\{-1,+1\\}$. In addition, $\theta\in\Theta=\mathbb{R}^{d-1}$
is the weight vector of a linear classifier, and
$\ell(\theta,Z)=\max\\{0,1-Y\langle\theta,X\rangle\\}$ is the hinge loss
function, which represents the pointwise maximum of $I=2$ saddle functions.
Finally, the reference distribution $\widehat{\mathbb{P}}$ is set to the
empirical (uniform) distribution on $J$ training samples
$\widehat{z}_{j}=(\widehat{x}_{j},\widehat{y}_{j})$, $j\in[J]$, and the
transportation cost function is defined as
$c((x_{1},y_{1}),(x_{2},y_{2}))=\|x_{1}-x_{2}\|$ if $y_{1}=y_{2}$, where
$\|\cdot\|$ is an arbitrary norm on $\mathbb{R}^{d-1}$, and
$c((x_{1},y_{1}),(x_{2},y_{2}))=+\infty$ if $y_{1}\neq y_{2}$. In this
setting, the Nash equilibrium between the statistician and nature can be
computed by using the techniques that were developed in Section 2.2 and
further generalized in Appendix A. Indeed, one readily verifies that
Assumptions 2.8, A.1 and A.2 hold. In addition, as we will see below, one can
also show that Assumption 2.15 is satisfied. This implies that Nash strategies
for the statistician and nature can be computed by solving the finite convex
programs (72) and (79), which generalize problems (11) and (22), respectively;
see Theorem A.5. Specifically, under the given assumptions about the loss and
transportation cost functions as well as the reference distribution, one can
show that if $\mathcal{X}=\mathbb{R}^{d-1}$, then (72) simplifies to

$\displaystyle\begin{array}[]{cll}\min&\displaystyle\varepsilon\lambda+\frac{1}{J}\sum_{j\in[J]}s_{j}\\\
\operatorname*{s.t.}&\theta\in\mathbb{R}^{d-1},~{}\lambda,s_{j}\in\mathbb{R}&\forall
j\in[J]\\\ &\lambda\geq\|\theta\|_{*},~{}s_{j}\geq 0,~{}s_{j}\geq
1-\widehat{y}_{j}\langle\theta,\widehat{x}_{j}\rangle&\forall
j\in[J],\end{array}$ (57)

while problem (79) reduces to

$\displaystyle\begin{array}[]{cll}\max&\displaystyle\sum_{j\in[J]}q_{2j}\\\\[2.15277pt]
\operatorname*{s.t.}&\displaystyle
q_{ij}\in\mathbb{R}_{+},~{}\xi_{ij}\in\mathbb{R}^{d-1}&\forall
i\in[I],\,j\in[J]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}q_{ij}=1/J&\forall j\in[J]\\\\[2.15277pt]
&\displaystyle\sum_{i\in[I]}\sum_{j\in[J]}\left\|\xi_{ij}\right\|\leq\varepsilon\\\\[2.15277pt]
&\displaystyle\sum_{j\in[J]}\widehat{y}_{j}(q_{2j}\widehat{x}_{j}+\xi_{2j})=0.\end{array}$
(63)

The following proposition shows that distributionally robust support vector
machine problem under consideration admits a continuum of least favorable
distributions, which represent different Nash strategies of nature. This
implies that there is in fact a continuum of many different Nash equilibria.

######  Proposition 4.1 (Non-uniqueness of Nash equilibria).

If $(\\{\tilde{q}^{\star}_{j}\\}_{j})$ solves the maximization problem

$\displaystyle\max_{\tilde{q}_{j},\,j\in[J]}\left\\{\sum_{j\in[J]}\tilde{q}_{j}:\left\|\sum_{j\in[J]}\tilde{q}_{j}\widehat{y}_{j}\widehat{x}_{j}\right\|\leq\varepsilon,\,0\leq\tilde{q}_{j}\leq\frac{1}{J}~{}\forall
j\in[J]\right\\},$ (64)

and if $\mathcal{J}_{0}=\\{j\in[J]:\tilde{q}^{\star}_{j}=0\\}$,
$\mathcal{J}_{+}=\\{j\in[J]:\tilde{q}^{\star}_{j}>0\\}$ and
$\tilde{\xi}=-\sum_{j\in[J]}\tilde{q}^{\star}_{j}\widehat{y}_{j}\widehat{x}_{j}$,
then the distribution

$\displaystyle\mathbb{Q}^{\star}(\alpha)=\frac{1}{J}\sum_{j\in\mathcal{J}_{0}}\delta_{(\hskip
0.70004pt\widehat{x}_{j},\widehat{y}_{j})}+\sum_{j\in\mathcal{J}_{+}}\left(\frac{1}{J}-\tilde{q}^{\star}_{j}\right)\delta_{(\hskip
0.70004pt\widehat{x}_{j},\widehat{y}_{j})}+\sum_{j\in\mathcal{J}_{+}}\tilde{q}^{\star}_{j}\delta_{(\hskip
0.70004pt\widehat{x}_{j}+\alpha_{j}\widehat{y}_{j}\tilde{\xi}/\tilde{q}_{j}^{\star},\widehat{y}_{j})}$

constitutes a Nash strategy of nature for any $\alpha\in
A=\\{\alpha\in\mathbb{R}_{+}^{J}:\sum_{j\in[J]}\alpha_{j}=1,~{}\alpha_{j}=0~{}\forall
j\in\mathcal{J}_{0}\\}$.

###### Proof.

The conic duality theorem [8, Theorem 1.4.2] ensures that the minimization
problem (57), which trivially admits a Slater point, and the maximization
problem (64) are strong duals. Thus, problem (64) is solvable and has the same
optimal value as problem (57). Theorem A.5 further implies that problems (64)
and (63) share the same optimal values, too. In the following we use any
maximizer $(\\{\tilde{q}^{\star}_{j}\\}_{j})$ of (64) to construct a family of
optimal solutions
$(\\{q_{ij}^{\star}(\alpha),\xi^{\star}_{ij}(\alpha)\\}_{i,j})$ for problem
(63) parametrized by $\alpha\in A$. Specifically, we set
$q_{1j}^{\star}(\alpha)={1}/{J}-\tilde{q}_{j}^{\star}$,
$q_{2j}^{\star}(\alpha)=\tilde{q}_{j}^{\star}$ and
$\xi_{1j}^{\star}(\alpha)=0$ for all $j\in[J]$, $\xi_{2j}^{\star}(\alpha)=0$
for all $j\in[J]$ with $\tilde{q}_{j}^{\star}=0$, and
$\xi_{2j}^{\star}(\alpha)=\alpha_{j}\widehat{y}_{j}\tilde{\xi}$ for all
$j\in[J]$ with $\tilde{q}_{j}^{\star}>0$. By construction,
$(\\{q_{ij}^{\star}(\alpha),\xi^{\star}_{ij}(\alpha)\\}_{i,j})$ is feasible in
(63), and its objective function value in (63) matches the optimal value of
problem (64), which equals the optimal value of problem (63). Hence,
$(\\{q_{ij}^{\star}(\alpha),\xi^{\star}_{ij}(\alpha)\\}_{i,j})$ solves (63)
for any $\alpha\in A$. In addition, one readily verifies that
$\mathcal{I}_{j}^{\infty}(\alpha)=\\{i\in[I]:q_{ij}^{\star}(\alpha)=0,\,\xi_{ij}^{\star}(\alpha)\neq
0\\}=\emptyset$ for all $j\in[J]$ and $\alpha\in A$. This implies that
Assumption 2.15 is satisfied irrespective of $\alpha\in\mathcal{A}$. By
Theorem A.5 (ii) and the definitions of $\mathcal{J}_{0}$ and
$\mathcal{J}_{+}$, the discrete distribution $\mathbb{Q}^{\star}(\alpha)$
therefore represents a Nash strategy of nature for every $\alpha\in A$. This
observation completes the proof. ∎

Consider now an instance of the distributionally robust support vector machine
problem with $d=3$, $\varepsilon=0.1$ and $J=20$, where $\widehat{y}_{j}=1$
and $\widehat{x}_{j}$ is sampled independently from
$\mathcal{N}((1,-1),\frac{1}{2}I_{2})$ for $j=1,\ldots,10$, while
$\widehat{y}_{j}=-1$ and $\widehat{x}_{j}$ is sampled independently from
$\mathcal{N}((-1,1),\frac{1}{2}I_{2})$ for $j=11,\ldots,20$. In addition, we
use the $p$-norm to quantify the transportation cost in the feature space for
$p\in\\{1,2,\infty\\}$. We then solve problem (57) to find an optimal weight
vector $\theta^{\star}$, and we solve problem (64) to construct the index sets
$\mathcal{J}_{0}$ and $\mathcal{J}_{+}$, the transportation budget
$\tilde{\xi}$ as well as different least favorable distributions
$\mathbb{Q}^{\star}(\alpha)$ with $\alpha\in\mathcal{A}$. Figure 1 represents
all training samples with $\widehat{y}_{j}=1$ and $\widehat{y}_{j}=-1$ as blue
and red dots, respectively. The optimal classifier is visualized by the
separating hyperplane
$\\{x\in\mathbb{R}^{2}:\langle\theta^{\star},x\rangle=0\\}$ (solid line) and
the maximum margin hyperplanes
$\\{x\in\mathbb{R}^{2}:\langle\theta^{\star},x\rangle=\pm 1\\}$ (dashed
lines). By Proposition 4.1, there are infinitely many least favorable
distributions, which are obtained from the empirical distribution by moving
probability mass from the samples in $\mathcal{J}_{+}$ in a direction of
increasing hinge loss at a total transportation budget $\tilde{\xi}$. The left
charts of Figure 1 show the empirical distribution, where all training samples
in $\mathcal{J}_{+}$ are designated by a solid circle. The middle charts show
a least favorable distribution obtained by assigning the transportation budget
$\tilde{\xi}$ to a single training sample in $\mathcal{J}_{+}$, and the right
charts show the least favorable distribution obtained by evenly distributing
the transportation budget $\tilde{\xi}$ across all training samples in
$\mathcal{J}_{+}$.

(a) 1-norm transportation cost

(b) 2-norm transportation cost

(c) $\infty$-norm transportation cost

Figure 1: Different feature distributions in a distributionally robust support
vector machine problem: Empirical distribution (left), a least favorable
distribution obtained by perturbing a single sample in $\mathcal{J}_{+}$
(center) and the least favorable distribution obtained by perturbing all
samples in $\mathcal{J}_{+}$ (right).

In the second experiment we use a distributionally robust support vector
machine to distinguish greyscale images of handwritten numbers 3 and 8 from
the MNIST $3$-vs-$8$ dataset [49]. Any such image consists of 786 pixels with
an intensity ranging from 0 (black) to 1 (white) and thus represents a feature
vector $X\in\mathcal{X}=[0,1]^{d-1}$ with $d=787$. The corresponding label $Y$
is set to $+1$ if the image shows the number 3 and to $-1$ if the image shows
the number 8. For ease of visualization, we use the first $J=10$ records of
the dataset as the training samples. In addition, we use the $\infty$-norm to
quantify the transportation cost in the feature space. The goal of this
experiment is to compare the least favorable distributions that solve the dual
DRO problem (i.e., the Nash strategies of nature) against the worst-case
distributions that maximize the expected hinge loss when the classifier’s
weight vector is fixed to a minimizer $\theta^{\star}$ of the primal DRO
problem (i.e., the best response strategies of nature when the statistician
plays $\theta^{\star}$). Specifically, we construct a least favorable
distribution as in Theorem A.5 (ii), which is possible because
$\mathcal{I}_{j}^{\infty}=\emptyset$ for every $j\in[J]$ thanks to the
compactness of $\mathcal{X}$. In addition, we compute $\theta^{\star}$ as in
Theorem A.5 (i) and construct a worst-case distribution for $\theta^{\star}$
as in [74, § 3.2]. As every Nash strategy is a best response to the
adversary’s Nash strategy, it is clear that every least favorable distribution
is a worst-cast distribution for $\theta^{\star}$. If the finite convex
program used to construct the worst-case distribution has multiple optimal
solutions, then the reverse implication is generally false. The optimization
algorithm used to solve this convex program thus outputs an arbitrary worst-
case distribution that generically fails to be a least favorable distribution.