# Reflections of convex bodies and their sections

Jorge L. Arocha, Javier Bracho and Luis Montejano

###### Abstract.

The purpose of this paper is to study the reflections of a convex body. In
particular, we are interested in orthogonal reflections of its sections that
can be extended to reflections of the whole body. For this reason, we need to
study the case of a non-spherical ellipsoid, where a surprising structure
arises (Section 2). These results allow us to give a new characterization of
ellipsoids in terms of their reflections and, on the other hand, to prove a
result deeply related to a conjecture due to K. Bezdek.

##  1\. Introduction

Every nonempty planar section of a 3-dimensional ellipsoid is an ellipse.
Hence, it admits at least two orthogonal reflections because the axes of the
ellipse are reflection lines. Likewise, every nonempty planar section of a
3-dimensional body of revolution admits a reflection line (which is coplanar
with the axis of revolution). Karoly Bezdek conjectured in [2] that if every
nonempty planar section of a $3$-dimensional convex body admits an orthogonal
reflection then it must be either an ellipsoid or a body of revolution. Some
work has been done in the direction of, or inspired by, this conjecture:

Given a convex body $K$, let us define a _Bezdek_ plane (for $K$, it is
understood) to be a plane whose section with $K$ admits an orthogonal
reflection; observe that non-intersecting planes are Bezdek planes. We know
that if $K$ is a convex body for which every plane is a Bezdek plane (the
hypothesis of the conjecture) then, through every interior point of $K$ there
is a section which is a disk, [5]. Moreover, if every plane is a Bezdek plane
with a reflection line coplanar to a fixed line, then $K$ is a body of
revolution, [3]. For more related problems see [6].

Here we prove a weaker form of the conjecture. It leads to the proof of a
similar statement in higher dimensions. First, we need to establish some
terminology.

A convex body $K\subset\mathbb{R}^{n}$ is an _ellipsoid_ if it is the image of
a ball under an affine automorphism. We say that a convex body
$K\subset\mathbb{R}^{n}$ is a $\mathbb{S}^{1}$-_rotational body_ if there is a
$(n-2)$-dimensional flat $L$, called the _axis of rotation_ of $K$, with the
property that for every plane $P$ orthogonal to $L$: $P\cap K$ is either
empty, a single point or a disk centered at $L\cap P$. Clearly, in
$\mathbb{R}^{3}$ an $\mathbb{S}^{1}$-rotational body is a body of revolution.

Let $K$ be a convex body in $\mathbb{R}^{n}$ and let $\Gamma$ be a hyperplane.
Generalizing directly, we say that $\Gamma$ is a _Bezdek_ hyperplane if
$\Gamma\cap K$ admits an orthogonal reflection. If, in addition, this
orthogonal reflection in $\Gamma$ extends to a reflection $\bf{r}$ of $K$ we
say that $\Gamma$ is _strong-Bezdek_ and we call $\bf{r}$ the _strong
reflection_ associated to $\Gamma$. Observe that in $\mathbb{R}^{3}$, every
plane is strong-Bezdek for an ellipsoid or a body of revolution.

Our main purpose is to prove the following theorem which, in dimension $3$,
yields a weaker version of Bezdek’s Conjecture. The other variation is on the
set of planes considered.

######  Theorem 1.

Let $K$ be a $n$-dimensional convex body. If there exists an open subset of
the Grasmannian space whose elements are strong-Bezdek hyperplanes, then $K$
is either an ellipsoid or a $\mathbb{S}^{1}$-rotational body.

Given a reflection $\mathbf{r}:\mathbb{R}^{n}\to\mathbb{R}^{n}$, we must
distinguish the following associated elements: the _mirror_ is the hyperplane
which is pointwise fixed, and the _direction_ which is a line through the
origin all of whose parallel lines are rigidly inverted at their intersection
with the mirror. The direction line is complementary to the mirror hyperplane.
And if the direction is orthogonal to the mirror, the reflection is said to be
_orthogonal_.

We say that $\Gamma$ is a _ground_ hyperplane for the reflection $\mathbf{r}$
if $\Gamma$ contains the direction of $\mathbf{r}$ (which implies that
$\Gamma$ is invariant under $\mathbf{r}$) and $\mathbf{r}$ restricted to
$\Gamma$ is an orthogonal reflection in $\Gamma$. Observe that if $\Gamma$ is
a ground hyperplane of a reflection, so is any parallel hyperplane, so that a
ground hyperplane may be assumed to pass through the origin.

Let $\mathbf{r}$ be a reflection with direction $\ell$ and mirror $M$. If
$\ell$ is not orthogonal to $M$ then the hyperplane $\Gamma$ generated by
$M\cap\ell^{\perp}$ and $\ell$ is the unique ground plane for $\mathbf{r}$. On
the other hand, if $\mathbf{r}$ is an orthogonal reflection then all the
hyperplanes through $\ell$ are ground hyperplanes for $\mathbf{r}$.

Now, we can rephrase the definition of strong-Bezdek hyperplanes. First, a
convex body $K\subset\mathbb{R}^{n}$ has to be explicit in the context. Then,
a hyperplane $\Gamma$ is strong-Bezdek if it is a ground hyperplane of a
_reflection of_ $K$ (i.e., that leaves $K$ invariant). If this is the case,
all the parallel hyperplanes to $\Gamma$ are also strong-Bezdek because they
are ground hyperplanes of the same strong reflection associated to $\Gamma$.
So the notion of strong-Bezdek is defined up to parallelism. However, observe
that even if all the parallel hyperplanes to $\Gamma$ are Bezdek, for $\Gamma$
to be strong-Bezdek one still needs that they have mirrors that make them
Bezdek and align inside a hyperplane.

For the proof of Theorem 1, we need to understand the question of how many
reflections of a $n$-dimensional body $K$ are enough to prove that $K$ is an
ellipsoid? A possible answer to this question is given in Theorem 2 of the
next section.

##  2\. Characterizing ellipsoids by means of reflections

The main result of this section is the following characterization of
ellipsoids, which is critical for our proof of Theorem 1. To state it simply,
let us define a subset of a topological space to be _thick_ if it contains a
nonempty open set; that is, if it has non-empty interior. Let $G_{1,n}$ and
$G_{n-1,n}$ be the Grassmannian of lines and hyperplanes, respectively,
through the origin in $\mathbb{R}^{n}$.

######  Theorem 2.

A convex body $K\subset\mathbb{R}^{n}$ is an ellipsoid if one of the following
holds:

  1. i)

the lines $\ell$ whose midpoints of all chords of $K$ parallel to $\ell$ lie
in a hyperplane, are thick in $G_{1,n}$.

  2. ii)

the lines $\ell$ such that there is a reflection of $K$ with direction $\ell$,
are thick in $G_{1,n}$.

  3. iii)

the ground hyperplanes of non orthogonal reflections of $K$, are thick in
$G_{n-1,n}$.

First we need to study ellipsoids with special attention to the ground planes
of their non orthogonal reflections. Then we use that knowledge to prove
Theorem 2.

Let $\mathcal{E}\subset\mathbb{R}^{n}$ be an ellipsoid; we may assume it is
centered at the origin. Recall that $G_{1,n}=G_{1}(\mathbb{R}^{n})$ is the
Grassmannian of lines through the origin in $\mathbb{R}^{n}$. Any line
$\ell\in G_{1,n}$ is the direction of a unique reflection $\mathbf{r}_{\ell}$
of $\mathcal{E}$. Indeed, the midpoints of all non-trivial chords in
$\mathcal{E}$ parallel to $\ell$ generate its _mirror_
$M(\ell)=M_{\mathcal{E}}(\ell)$, which is also the parallel at the origin of
the tangent hyperplanes to $\mathcal{E}$ at the endpoints of the _chord_
$\ell\cap\mathcal{E}$. So that $\mathbf{r}_{\ell}$ is an orthogonal reflection
if and only if $\ell$ is a _binormal_ line to $\mathcal{E}$, that is, a line
$\ell$ whose tangent hyperplanes at the endpoints of $\ell\cap\mathcal{E}$ are
orthogonal to $\ell$; and this happens if and only if $M(\ell)$ is the
orthogonal hyperplane to $\ell$. These lines are also called _axes_ of the
ellipsoid.

We will use that the bijective assignment of mirror hyperplanes to lines given
by the ellipsoid $\mathcal{E}$ reverses inclusion; that is, given lines $\ell$
and $\ell^{\prime}$ in $G_{1,n}$, then

(1) $\ell^{\prime}\subset M(\ell)\quad\iff\quad\ell\subset
M(\ell^{\prime})\,.$

To see this, consider a quadratic form that defines $\mathcal{E}$. It has an
associated symmetric bilinear form. What determines if a vector lies in the
mirror of the line generated by another vector, is that the symmetric bilinear
form vanishes on that pair. Then, the assertion (1) easily follows.

Let $\mathbb{B}_{\mathcal{E}}\subset G_{1,n}$ be the set of binormal lines of
$\mathcal{E}$, and denote its complement by

(2) $\mathbb{D}_{\mathcal{E}}=G_{1,n}\setminus\mathbb{B}_{\mathcal{E}}\,;$

it is the set of directions of non orthogonal reflections of $\mathcal{E}$; we
refer to the elements of $\mathbb{D}_{\mathcal{E}}$ as _diagonal_ lines of
$\mathcal{E}$. Assume henceforth that $\mathcal{E}$ is not a sphere so that
$\mathbb{D}_{\mathcal{E}}$ is an open dense subset of $G_{1,n}$, instead of
being empty.

Denote by $G_{n-1,n}$, the Grasmannian space of hyperplanes through the origin
in $\mathbb{R}^{n}$. Our main goal is to understand the _ground map_

$\gamma:\mathbb{D}_{\mathcal{E}}\to G_{n-1,n}$

which sends $\ell\in\mathbb{D}_{\mathcal{E}}$ to the unique ground hyperplane
$\gamma(\ell)=\Gamma_{\ell}\in G_{n-1,n}$ of the reflection
$\mathbf{r}_{\ell}$ of $\mathcal{E}$ in the direction $\ell$. The binormals
$\mathbb{B}_{\mathcal{E}}$ had to be removed from $G_{1,n}$ to have the ground
map well defined as a function.

Note that $\gamma(\ell)$ varies continuously with $\ell$ because we can write

$\gamma(\ell)=(M(\ell)\cap\ell^{\perp})\oplus\ell\,,$

where “$\,{}^{\perp}$” denotes the orthogonal complement and “$\oplus$” the
sum of complementary subspaces of $\mathbb{R}^{n}$. And note also that
$\ell\subset\gamma(\ell)$ is an axis of the ellipsoid
$\gamma(\ell)\cap\mathcal{E}$, because the reflection $\mathbf{r}_{\ell}$
restricted to the hyperplane $\gamma(\ell)$ is an orthogonal reflection.

Indeed, given a diagonal line $\ell\in\mathbb{D}_{\mathcal{E}}$,
$\gamma(\ell)$ is the unique hyperplane $\Gamma$ containing $\ell$ for which
$\ell$ is a binormal of $\Gamma\cap\mathcal{E}$. To see this, observe that for
any $\ell\in G_{1,n}$ and $\Gamma\in G_{n-1,n}$ such that $\ell\subset\Gamma$,
the mirror of $\ell$ with respect to the ellipsoid $\Gamma\cap\mathcal{E}$ is
the intersection of $\Gamma$ with its mirror with respect to $\mathcal{E}$,
which we can write

$M_{\Gamma\cap\mathcal{E}}(\ell)=\Gamma\cap M(\ell)\,.$

So that a line which is an axis of two distinct hyperplane sections of
$\mathcal{E}$ has to be a binormal line of $\mathcal{E}$, and by definition it
is not a diagonal.

We can summarize these last remarks with the following:

######  Lemma 1.

Let $\Gamma\in G_{n-1,n}$, then $\gamma^{-1}(\Gamma)$ consists of the axes of
the ellipsoid $\Gamma\cap\mathcal{E}$ which are not axes of $\mathcal{E}$. ∎

######  Theorem 3.

There are open dense sets $\mathbb{G}\subset\mathbb{D}_{\mathcal{E}}$ and
$\mathbb{T}\subset G_{n-1,n}$ such that the ground map of $\mathcal{E}$
restricts to a covering map $\gamma:\mathbb{G}\to\mathbb{T}$.

###### Proof.

Given a line $\ell\subset\mathbb{R}^{n}$, let us denote by $\lambda(\ell)$ the
_length_ of $\ell$, that is, the length of the segment $\ell\cap\mathcal{E}$.
Let

$\mathbb{B}_{\mathcal{E}}=\mathbb{B}_{1}\cup\dots\cup\mathbb{B}_{k}$

be the partition of the binormal lines of $\mathcal{E}$ given by their
_lengths_ ; that is, two binormals of $\mathcal{E}$, belong to the same class
$\mathbb{B}_{i}$ if and only if they have the same length $\lambda_{i}$.
Denote by $V_{i}\subset\mathbb{R}^{n}$ the subspace generated by the lines in
$\mathbb{B}_{i}\subset G_{1,n}$; so that $\mathbb{B}_{i}=G_{1}(V_{i})$. We
then have that

$\mathbb{R}^{n}=V_{1}\oplus\dots\oplus V_{k}$

is the orthogonal partition of $\mathbb{R}^{n}$ by the eigenspaces of the
symmetric matrix associated to a quadratic form that defines $\mathcal{E}$;
so, we may refer to the $V_{i}$ as the _eigenspaces_ of $\mathcal{E}$. Observe
that the partitions are non-trivial ($k\geq 2$) because we are assuming that
$\mathcal{E}$ is not a sphere.

Let us define the _generic_ diagonals

(3) $\mathbb{G}=\\{\,\ell\in G_{1,n}\,\mid\,\ell\not\subset
V_{i}^{\perp}\,\,\text{and}\,\,\lambda(\ell)\neq\lambda_{i}\,,i=1,\dots,k\,\\}\,.$

Observe that $\mathbb{G}\subset\mathbb{D}_{\mathcal{E}}$ because if
$\ell\not\in\mathbb{D}_{\mathcal{E}}$ then $\ell\subset V_{j}$ for some $j$
and $V_{j}\subset V_{i}^{\perp}$ for all $i\neq j$. So that the ground map
$\gamma$ is well defined on $\mathbb{G}$.

Define the _generic_ hyperplanes to be

(4) $\mathbb{T}=\\{\,\Gamma\in
G_{n-1,n}\,\mid\,V_{i}\not\subset\Gamma,i=1,\dots,k\,\\}\,.$

First note that $\mathbb{G}\subset G_{1,n}$ and $\mathbb{T}\subset G_{n-1,n}$
are open dense subsets. We will prove that the ground map restricted to
$\mathbb{G}$ is a covering map of $k-1$ sheets over $\mathbb{T}$, and in
particular that

$\gamma(\mathbb{G})=\mathbb{T}.$

To see that $\gamma(\mathbb{G})\subset\mathbb{T}$ consider
$\ell\in\mathbb{G}$, and suppose $\Gamma=\gamma(\ell)\notin\mathbb{T}$. This
implies that $V_{i}\subset\Gamma$ for some $i$. Since any two binormals of an
ellipsoid having different lengths are orthogonal and both $\ell$ and the
lines of $V_{i}$ are binormals of the ellipsoid $\Gamma\cap\mathcal{E}$, then
$\lambda(\ell)\neq\lambda_{i}$ implies that $\ell\subset
V_{i}^{\perp}\cap\Gamma\subset V_{i}^{\perp}$, which contradicts
$\ell\in\mathbb{G}$.

Now consider a fixed hyperplane $\Gamma\in\mathbb{T}$. For each $i=1,\dots,k$,
since $V_{i}\not\subset\Gamma$, we can choose a line $e_{i}\subset V_{i}$
which is not in $\Gamma$: if $V_{i}$ is a line, then $e_{i}=V_{i}$ and if
$V_{i}$ is more than a line we choose $e_{i}\subset V_{i}$ to be the
orthogonal line to $\Gamma\cap V_{i}$. Let us assume that $e_{1},\dots,e_{k}$
correspond to the first coordinate axes of $\mathbb{R}^{n}$ so that we can
refer to the subspace they generate as $\mathbb{R}^{k}$, but observe, for
later on, that it really depends continuously on $\Gamma$. By construction,
the binormal lines of $\mathcal{E}$ inside $\mathbb{R}^{k}$ are exactly the
coordinate axis $e_{1},\dots,e_{k}$ and they all have different lengths. We
will now prove that in $\mathbb{R}^{k}$ there are exactly $k-1$ generic lines
of different lengths which are the axes of $\Gamma\cap\mathcal{E}$. This
implies, by Lemma 1, that $\\#\gamma^{-1}(\Gamma)=k-1$ because generic lines
are not binormal to $\mathcal{E}$.

Let $\ell\subset\Gamma\cap\mathbb{R}^{k}$ be a binormal line to
$\Gamma\cap\mathcal{E}$, that is, such that
$M_{\Gamma\cap\mathcal{E}}(\ell)=M(\ell)\cap\Gamma$ is orthogonal to $\ell$.
To prove that $\ell$ is generic, we first see that $\ell\not\subset
V_{i}^{\perp}$. For this, it suffices to prove that $\ell\not\subset
e_{i}^{\perp}$ because $V_{i}^{\perp}\subset e_{i}^{\perp}$. So suppose
$\ell\subset e_{i}^{\perp}$. Since $e_{i}^{\perp}=M(e_{i})$ ($e_{i}$ is
binormal to $\mathcal{E}$) then, (1) implies that $e_{i}\subset M(\ell)$. On
the other hand, $e_{i}\not\subset\Gamma$ yields by simple dimension arguments
that

$M(\ell)=(M(\ell)\cap\Gamma)\oplus e_{i}\,.$

So that $M(\ell)$ is orthogonal to $\ell$ because both summands are orthogonal
to $\ell$. Then $\ell$ is binormal to $\mathcal{E}$, but being inside
$e_{i}^{\perp}\cap\mathbb{R}^{k}$, $\ell$ has to be $e_{j}$ for some $j\neq
i$, which contradicts that $e_{j}\not\subset\Gamma$. So, we have that
$\ell\not\subset V_{i}^{\perp}$ for $i=1,\dots,k$.

We are left to prove $\lambda(\ell)\neq\lambda_{i}$ to conclude that
$\ell\in\mathbb{G}$. Suppose not; that is, assume $\lambda(\ell)=\lambda_{i}$.
Consider the plane $P=\ell\oplus e_{i}$ which intersects $\Gamma$ in $\ell$.
The ellipse $P\cap\mathcal{E}$ has $e_{i}$ as an axis (because it is an axis
of $\mathcal{E}$). Then if another chord through its center has the same
length, it has to be a circle; because the length function of an ellipse
reaches its unique extremes at the axes unless it is constant. This implies
that the orthogonal line to $\ell$ in the plane $P$,
$\ell^{\prime}=P\cap\ell^{\perp}$, is contained in $M(\ell)$ but it is not in
$\Gamma$, so that $M(\ell)=(M(\ell)\cap\Gamma)\oplus\ell^{\prime}$ is
orthogonal to $\ell$. Then, $\ell$ is a binormal of $\mathcal{E}$, which
implies, because of its length, that $\ell\subset V_{i}$; but this contradicts
that $\ell\in\mathbb{R}^{k}$.

So, we have proved that any axis of
$(\Gamma\cap\mathcal{E})\cap\mathbb{R}^{k}$ is a generic line.

Now consider two different lines $\ell$ and $\ell^{\prime}$ in
$\Gamma\cap\mathbb{R}^{k}$ which are binormal to $\Gamma\cap\mathcal{E}$.
Suppose they have the same length $\lambda$. Let
$P=\ell\oplus\ell^{\prime}\subset\Gamma\cap\mathbb{R}^{k}$ be the plane
generated by them. All of the lines in $G_{1}(P)$ are binormal to
$\Gamma\cap\mathcal{E}$ and have length $\lambda$. This implies, in
particular, that $\ell^{\prime\prime}=P\cap
e_{1}^{\perp}\subset\mathbb{R}^{k}$ is a binormal line of
$\Gamma\cap\mathcal{E}$. But $\ell^{\prime\prime}$ is not generic (it is
contained in $V_{1}^{\perp}$), contradicting the conclusion of the previous
paragraph. And therefore, $\lambda(\ell)\neq\lambda(\ell^{\prime})$.

Summarizing, given $\Gamma\in\mathbb{T}$, since
$\Gamma\cap\mathcal{E}\cap\mathbb{R}^{k}$ is an ellipsoid of dimension $k-1$,
it has $k-1$ mutually orthogonal axes. We have proved that they are generic
lines with different lengths, so that, by Lemma 1, $\gamma^{-1}(\Gamma)$
consists of exactly $k-1$ isolated points in $\mathbb{G}$ because all the
other binormal lines to $\Gamma\cap\mathcal{E}$ are also binormal lines to
$\mathcal{E}$.

Finally note that in a small neighborhood of $\Gamma$ the order of the lengths
of the axes of the corresponding sections of $\mathcal{E}$ is well determined,
which implies not only that $\\#\gamma^{-1}(\Gamma)=k-1$ but also that
$\gamma:\mathbb{G}\to\mathbb{T}$ is a $(k-1)$-covering space, as we wished. ∎

Now, we can prove Theorem 2. It will ease reading to restate it:

######  Theorem 2.

A convex body $K\subset\mathbb{R}^{n}$ is an ellipsoid if one of the following
holds:

  1. i)

the lines $\ell$ whose midpoints of all chords of $K$ parallel to $\ell$ lie
in a hyperplane, are thick in $G_{1,n}$.

  2. ii)

the lines $\ell$ such that there is a reflection of $K$ with direction $\ell$,
are thick in $G_{1,n}$.

  3. iii)

the ground hyperplanes of non orthogonal reflections of $K$, are thick in
$G_{n-1,n}$.

###### Proof.

With hypothesis (i) this theorem is a generalization of Brunn’s
characterization of ellipsoids (see Theorem 2.12.1 of [4] and [1]), in the
sense that only thickness of such lines is asked instead of being all of them.

First observe that hypothesis (i) and (ii) are equivalent because there is a
reflection of $K$ in the direction $\ell$ if and only if the midpoints of all
the chords of $K$ parallel to $\ell$ lie in a hyperplane (the mirror). So, it
is enough to consider (ii).

Let $\mathcal{E}$ be the unique ellipsoid of minimal volume containing $K$,
see e.g. [1]. Observe that any affine symmetry of $K$ is also an affine
symmetry of $\mathcal{E}$. Indeed, if $g:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is
an affine map such that $K=g(K)$, then $g(\mathcal{E})$ is an ellipsoid that
contains $K$, but since $g$ preserves volume ($K$ is a body), the uniqueness
of $\mathcal{E}$ implies that $\mathcal{E}=g(\mathcal{E})$.

Let $\Lambda_{K}\subset G_{1,n}$ be the set of lines which are the direction
of a reflection of $K$. As in the beginning of this section, let
$\mathbf{r}_{\ell}$ be the reflection of $\mathcal{E}$ with direction $\ell$,
so that $\mathbf{r}_{\ell}$ is well defined for all $\ell\in G_{1,n}$. But
observe that only for $\ell\in\Lambda_{K}$ we have that $\mathbf{r}_{\ell}$ is
also a reflection of $K$ (that is,
$\ell\in\Lambda_{k}\iff\mathbf{r}_{\ell}(K)=K$).

Suppose (ii) is true, that is, assume $\Lambda_{K}$ is thick. We will prove
$K=\mathcal{E}$.

To see that $K=\mathcal{E}$, it is enough to prove that
$K\cap\partial\mathcal{E}$ is open in $\partial\mathcal{E}$. Indeed, since
$K\cap\partial\mathcal{E}=\partial K\cap\partial\mathcal{E}$ is non-empty and
closed in $\partial\mathcal{E}$, if it is also open it has to be all of
$\partial\mathcal{E}$, which implies that $K=\mathcal{E}$ because both sets
are convex.

Consider a point $p\in K\cap\partial\mathcal{E}$, and let $T_{p}$ be the
tangent plane to $\mathcal{E}$ at $p$ (which is also a support plane to $K$ at
$p$). Denote by $W_{p}\subset G_{1,n}$ the set of lines not parallel to the
hyperplane $T_{p}$; it is an open dense set of $G_{1,n}$ homeomorphic to
$\mathbb{R}^{n-1}$, also known as an _affine chart_ of $G_{1,n}$. For any line
$\ell\in W_{p}$, we have that $\mathbf{r}_{\ell}(p)\neq p$ because the
parallel to $\ell$ through $p$, which we will denote $\ell(p)$, intersects
$\partial\mathcal{E}$ in another point which is $\mathbf{r}_{\ell}(p)$; that
is, $\ell(p)\cap\partial\mathcal{E}=\\{p,\mathbf{r}_{\ell}(p)\\}$. Since
$\Lambda_{K}$ is thick in $G_{1,n}$, there clearly exists an open set
$V\subset\Lambda_{K}\cap W_{p}$. Consider the set

$V_{p}=\\{\,\mathbf{r}_{\ell}(p)\,|\,\ell\in V\,\\}\,.$

It is contained in $K\cap\partial\mathcal{E}$ because $p\in
K\cap\partial\mathcal{E}$ and $V\subset\Lambda_{K}$. And it is homeomorphic to
$V$ because it can be identified with its image under the _stereographic
projection from $p$_ that sends a line $\ell\in W_{p}$ to the point different
from $p$ in $\ell(p)\cap\partial\mathcal{E}$, and which is a homeomorphism
between $W_{p}$ and $\partial\mathcal{E}\setminus\\{p\\}$. So that $V_{p}$ is
an open set in $\partial\mathcal{E}$. Finally, fix any line $\ell_{0}\in
V\subset\Lambda_{K}$. Since $\mathbf{r}_{\ell_{0}}$ restricts to a
homeomorphism of $K$ and of $\partial\mathcal{E}$, we have that
$\mathbf{r}_{\ell_{0}}(V_{p})\subset K\cap\partial\mathcal{E}$ is an open
neighborhood of $p$ in $\partial\mathcal{E}$ and therefore
$K\cap\partial\mathcal{E}$ is open in $\partial\mathcal{E}$: which proves
$K=\mathcal{E}$.

Next, assume (iii) and we will prove $K=\mathcal{E}$ showing that (ii) holds.
Let $\Omega_{K}\subset G_{n-1,n}$ be the set of hyperplanes that are ground
hyperplanes of non orthogonal reflections of $K$ (hypothesis (iii) is that
$\Omega_{K}$ is thick). That it is non-empty, implies that $\mathcal{E}$ is
not a sphere and so Theorem 3 with its notation applies. Since $\Omega_{K}$ is
thick, there exists a set $U\subset\Omega_{K}\cap\mathbb{T}$ which is open in
$G_{n-1,n}$ and evenly covered by the ground map $\gamma$, so that

$\gamma^{-1}(U)=U_{1}\cup\cdots\cup U_{k-1}$

with each $U_{i}$ homeomorphic to $U$ via $\gamma$. Consider $\Gamma\in U$,
the $k-1$ reflexions $\mathbf{r}_{\ell}$ with $\ell\in\gamma^{-1}(\Gamma)$ are
all the non orthogonal reflexions of $\mathcal{E}$ with ground hyperplane
$\Gamma$. At least one of them is a reflexion of $K$ because
$\Gamma\in\Omega_{K}$ so that at least one of the lines in
$\gamma^{-1}(\Gamma)$ is also in $\Lambda_{K}$. This implies that

$U=\gamma(U_{1}\cap\Lambda_{K})\cup\cdots\cup\gamma(U_{k-1}\cap\Lambda_{K})\,.$

Observe that $\Lambda_{K}$ is closed, so that by Baire’s category theorem at
least one of the $U_{i}\cap\Lambda_{K}$ has non empty interior. This implies
that $\Lambda_{K}$ is thick and therefore, by (ii), that $K$ is an ellipsoid.
∎

##  3\. Proof of the main theorem

For the proof of Theorem 1, we need first the following lemma:

######  Lemma 2.

Let $K\subset\mathbb{R}^{3}$ be a convex body which is not
$\mathbb{S}^{1}$-rotational. Then the set of orthogonal reflections of $K$ is
finite

###### Proof.

Let $G$ be the group of isometries of $K$. We may assume that $G\subset
O_{n}$. Note that $K$ is an $\mathbb{S}^{1}$-rotational body if and only if
the group $G$ contains a copy of the group $O_{2}$ of isometries of
$\mathbb{S}^{1}\subset\mathbb{R}^{2}$. Therefore, $G$ does not contain a copy
of the group $SO_{2}\subset O_{2}$ and, since it is a compact subgroup of
$O_{n}$, it is a finite group. This implies that the set of orthogonal
reflections of $K$ is finite. ∎

_Proof of Theorem 1_. Recall that a hyperplane $\Gamma\in G_{n-1,n}$ is
strong-Bezdek if it is the ground plane of a reflection of $K$, and by
assumption there is an open subset $U\subset G_{n-1,n}$ of such hyperplanes.

Suppose $K$ is not a $\mathbb{S}^{1}$-rotational body. By Lemma 2, the set of
orthogonal reflections of $K$ is finite. For each of them, the set of ground
hyperplanes is homeomorphic to $\mathbb{R}\mathbb{P}^{n-2}\cong
G_{n-2,n-1}\subset G_{n-1,n}$ (the hyperplanes that contain the direction of
the reflection). So that the set of ground hyperplanes of orthogonal
reflections of $K$ is, at most, a finite collection of flats
$\mathbb{R}\mathbb{P}^{n-2}$ contained in $\mathbb{R}\mathbb{P}^{n-1}\cong
G_{n-1,n}$. In its complement, there clearly is an open set $U^{\prime}\subset
U$ of ground hyperplanes of non orthogonal reflections of $K$. Therefore, by
item (iii) of Theorem 2, $K$ is an ellipsoid. ∎

## References

  * [1] J.L. Arocha, J. Bracho and L. Montejano,  _Extremal inscribed and circumscribed ellipsoids_ .
  * [2] K. Bezdek, Z. Lángi, M. Naszódi and P. Papez, _Ball-polyhedra_. Discrete Comput. Geom. 38 (2007), no. 2, 201–230.
  * [3] J. Jeronimo, L. Montejano and E. Morales,  _Only solid spheres admit a false axis of revolution._ Journal of Convex Analysis 18 No.2 Â (2011), 505-511.
  * [4] H. Martini, L. Montejano, D. Oliveros, _Bodies of constant width. An Introduction to convex geometry_ Birkhäuser, Boston-Bassel-Sttugart, 2019.
  * [5] L. Montejano, _Two applications of topology to convex geometry_. Proceedings of the Steklov Institute of Mathematics, Vol. 247, (2004), 1-4.
  * [6] D. Ryabogin, _On symmetries of projections and sections of convex bodies._ Discrete Geometry and Symmetry, Springer International Publishing. (2018), 297-309.


Figure 2 visualizes specific worst-case and least favorable distributions
found by Gurobi for different radii $\varepsilon$ of the ambiguity set. The
ten images corresponding to $\varepsilon=0$ represent the features of the ten
unperturbed training samples. For any $\varepsilon>0$, both the worst-case
distribution as well as the least favorable distribution are obtained by
moving probability mass from some of the training samples to corresponding
adversarial samples with the same labels but perturbed features. Whenever this
happens, Figure 2 shows the adversarial samples instead of repeating the
corresponding training samples, and underneath each adversarial sample we
indicate the probability mass—as a percentage of $1/J$—inherited from the
underlying training sample. We emphasize that the adversarial samples differ
from all training samples and were thus ‘invented by nature’ with the goal to
confuse the statistician. The adversarial samples of the worst-case
distribution differ from the corresponding training samples only in a few
pixels that look like noise to the human eye. Some adversarial samples of the
least favorable distribution, however, are truly deceptive. For example, the
feature of the sixth training sample arguably shows the number 8, but for any
$\varepsilon>0$ this 8 is ostensibly converted to a 3 that was not present in
the training dataset. We conclude that nature’s best response to the optimal
classifier with weight vector $\theta^{\star}$ is at best suitable to deceive
an algorithm, whereas nature’s Nash strategy can even deceive a human. A
possible explanation for this observation is that nature’s Nash strategy aims
to fool every possible classifier and not only one single optimal classifier.

(a) Worst-case distributions (b) Least favorable distributions

Figure 2: Comparison of worst-case and least favorable distributions for
different values of $\varepsilon$.

###  4.2 Distributionally Robust Log-Optimal Portfolio Selection

Assume now that the components of the random vector
$Z\in\mathcal{Z}=\mathbb{R}^{d}$ represent the total returns of $d$ assets
over the next month, say. If the asset returns over consecutive months are
serially independent and governed by the same distribution
$\mathbb{P}\in\mathcal{P}(\mathcal{Z})$ satisfying some plausible mild
regularity conditions (such as $\mathbb{P}[Z\in\mathbb{R}^{d}_{++}]=1$), and
if $\Theta$ represents the probability simplex in $\mathbb{R}^{d}$, then one
can show that the constantly rebalanced portfolio $\theta\in\Theta$ that
maximizes the expected log-utility
$\mathbb{E}_{Z\sim\mathbb{P}}[\log(\langle\theta,Z\rangle)]$ generates more
wealth than any other causal portfolio strategy with probability 1 in the long
run [25, Theorem 15.3.1]. Unfortunately, however, the asset return
distribution $\mathbb{P}$ is unknown in practice. It is therefore natural to
study a distributionally robust problem formulation. In contrast to [73],
where $\mathbb{P}$ is assumed to be unknown except for its first- and second-
order moments, we model distributional ambiguity here via an optimal
transport-based ambiguity set centered at the empirical distribution
$\widehat{\mathbb{P}}=(1/J)\sum_{j\in[J]}\delta_{\,\widehat{z}_{j}}$ on $J$
training samples $\widehat{z}_{j}\in\mathbb{R}^{d}_{++}$, $j\in[J]$. Thus, we
aim to solve

$\displaystyle\min_{\theta\in\Theta}\sup_{\mathbb{Q}\in\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})}~{}\mathbb{E}_{Z\sim\mathbb{Q}}\left[-\log(\langle\theta,Z\rangle)\right],$
(65)

which is an instance of (48) with $L(s)=-\log(s)$ if $s>0$ and $L(s)=+\infty$
if $s\leq 0$. If the transportation cost function is set to
$c(z,\widehat{z})=\|z-\widehat{z}\|^{p}$ for some norm $\|\cdot\|$ on
$\mathbb{R}^{d}$ and exponent $p\geq 1$, then
$\mathbb{B}_{\varepsilon}(\widehat{\mathbb{P}})$ reduces to the $p$-th
Wasserstein ball of radius $\varepsilon^{p}$ around $\widehat{\mathbb{P}}$.
One readily verifies that any such Wasserstein ball contains distributions
that assign a strictly positive mass to 0. Thus, the worst-case expected log-
utility of any portfolio $\theta\in\Theta$ is unbounded from above, which
implies that problem (65) is infeasible. To ensure that problem (65) is well-
defined, the cost of moving any fixed probability mass towards 0 must tend to
infinity. This can be ensured, for example, by setting
$c(z,\widehat{z})=\sum_{i\in[d]}|\log(z_{i}/\widehat{z}_{i}))|$ with
$\operatorname*{dom}(c(\cdot,\widehat{z}))=\mathbb{R}^{d}_{++}$ for every
$\widehat{z}\in\mathbb{R}^{d}_{++}$. Even though it is nonconvex in both of
its arguments, this transportation cost function defines a metric on
$\mathcal{Z}$ that gives rise to a valid optimal transport discrepancy.
Elementary calculations show that $L^{*}(s)=-1-\log(-s)$ and that
$c^{*1}(s,\widehat{z})=\sum_{i\in[d]}h(s_{i}\widehat{z}_{i})$, where the
auxiliary function $h:\mathbb{R}\rightarrow(-\infty,+\infty]$ is defined
through $h(s)=-1-\log(-s)$ if $s<-1$, $h(s)=s$ if $-1\leq s\leq 0$ and
$h(s)=+\infty$ if $s>0$. Note that the proper convex function $h$ is
differentiable on its domain. By Theorem 3.8 (i) and as
$\operatorname*{dom}(L^{*})=(-\infty,0)$, the $c$-transform (50) can thus be
reformulated as

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})=\sup_{\gamma<0}\;1+\log(-\gamma)+\sum_{i\in[d]}\lambda\,h(\gamma\theta_{i}\widehat{z}_{i}/\lambda).$
(66)

The next proposition shows that the maximization problem in (66) can be solved
efficiently by sorting.

######  Proposition 4.2.

Given $\theta\in\Theta$, $\lambda\in\mathbb{R}_{+}$ and
$\widehat{z}\in\mathbb{R}^{d}_{++}$, set $u_{i}=\theta_{i}\widehat{z}_{i}$ for
every $i\in[d]$, let $\sigma$ be a permutation of $[d]$ with
$u_{\sigma(1)}\leq u_{\sigma(2)}\leq\cdots\leq u_{\sigma(d)}$, and define

$\displaystyle
k=\max\left\\{i\in[d]\;:\;(1-(d-i)\lambda)u_{\sigma(i)}\leq\lambda\sum_{j\in[i]}u_{\sigma(j)}\right\\}\quad\text{and}\quad\gamma^{\star}=\frac{(d-k)\lambda-1}{\sum_{i\in[k]}u_{\sigma(i)}}.$

If $\lambda\geq 1/\|\theta\|_{0}$, then problem (66) is solved by
$\gamma^{\star}$. Otherwise, we have
$\ell_{c}(\theta,\lambda,\widehat{z})=+\infty$.

###### Proof.

Assume first that $\lambda<1/\|\theta\|_{0}$. Then, we have

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle\geq\lim_{\gamma\to-\infty}~{}1+\log(-\gamma)+\sum_{i\in[d]}\lambda
h(\gamma\theta_{i}\widehat{z}_{i}/\lambda)$
$\displaystyle=\lim_{\gamma\to-\infty}~{}1+\log(-\gamma)+\sum_{i\in[d]:\,\theta_{i}>0}-\lambda-\lambda\log(-\gamma\theta_{i}\widehat{z}_{i}/\lambda)$
$\displaystyle=\lim_{\gamma\to-\infty}~{}(1-\lambda\,\|\theta\|_{0})(1+\log(-\gamma))-\sum_{i\in[d]:\,\theta_{i}>0}\lambda\log(\theta_{i}\widehat{z}_{i}/\lambda)=+\infty,$

where the first equality follows from the definition of $h$, and the third
equality holds because $\lambda<1/\|\theta\|_{0}$.

Next, assume that $\lambda>1/\|\theta\|_{0}$. Using a similar reasoning as
above, one can then show that the objective function of problem (66) drops to
$-\infty$ as $\gamma$ either tends to $-\infty$ or to $0$. Therefore, problem
(66) has a maximizer. In addition, as the objective function of problem (66)
is strictly concave and differentiable, this maximizer is unique and fully
determined by the first-order optimality condition

$\displaystyle\frac{1}{\gamma}+\sum_{i\in\mathcal{D}(\gamma)}u_{i}-\sum_{i\in[d]\backslash\mathcal{D}(\gamma)}\frac{\lambda}{\gamma}=0\quad\iff\quad\gamma=\frac{(d-|\mathcal{D}(\gamma)|)\lambda-1}{\sum_{i\in\mathcal{D}(\gamma)}u_{i}},$
(67)

where $\mathcal{D}(\gamma)=\\{i\in[d]:\gamma u_{i}\geq-\lambda\\}$ and
$u_{i}=\theta_{i}\widehat{z}_{i}$ for every $i\in[d]$. To show that
$\gamma^{\star}$ solves (67) and (66), it thus suffices to prove that
$\mathcal{D}(\gamma^{\star})=\\{\sigma(i):i\in[k]\\}$. To this end, we first
verify that the critical index $k$ is well-defined as the maximal element of a
non-empty finite set. This is indeed the case because

$\displaystyle(1-(d-1)\lambda)u_{\sigma(1)}\leq\left(1-\frac{d-1}{d}\right)u_{\sigma(1)}=\frac{u_{\sigma(1)}}{d}\leq\lambda
u_{\sigma(1)},$

where both inequalities follow from our assumption that
$\lambda>1/\|\theta\|_{0}>1/d$ and from the non-negativity of $u_{\sigma(1)}$.
We may thus conclude that $k\geq 1$. Next, we use induction to show that
$\sigma(i)\in\mathcal{D}(\gamma^{\star})$ for every $i\in[k]$. As for the base
step corresponding to $i=k$, we may use the definition of $k$ to find

$\displaystyle(1-(d-k)\lambda)u_{\sigma(k)}\leq\lambda\sum_{j\in[k]}u_{\sigma(j)}\quad\iff\quad\gamma^{\star}u_{\sigma(k)}\geq-\lambda,$

where the equivalence exploits the definition of $\gamma^{\star}$ in the
proposition statement. Hence, $\sigma(k)\in\mathcal{D}(\gamma^{\star})$. As
for the induction step, assume that $\sigma(i)\in\mathcal{D}(\gamma^{\star})$
for some $i\in[k]$ with $i>1$. Thus, we have

$\displaystyle(1-(d-i)\lambda)u_{\sigma(i)}\leq\lambda\sum_{j\in[i]}u_{\sigma(j)}\quad\implies\quad(1-(d-(i-1))\lambda)u_{\sigma(i)}\leq\lambda\sum_{j\in[i-1]}u_{\sigma(j)}.$

Since the permutation $\sigma$ sorts the parameters $\\{u_{i}\\}_{i\in[d]}$ in
ascending order, the last inequality implies

$\displaystyle(1-(d-(i-1))\lambda)u_{\sigma(i-1)}\leq(1-(d-(i-1))\lambda)u_{\sigma(i)}\leq\lambda\sum_{j\in[i-1]}u_{\sigma(j)}.$

This in turn allows us to conclude that

$\displaystyle(1-(d-k)\lambda)u_{\sigma(i-1)}\leq\lambda\sum_{j\in[k]}u_{\sigma(j)}\quad\implies\quad\gamma^{\star}u_{\sigma(i-1)}\geq-\lambda,$

where the implication follows again from the definition of $\gamma^{\star}$.
Hence, $\sigma(i-1)\in\mathcal{D}(\gamma^{\star})$, which completes the
induction step. We have thus shown that
$\sigma(i)\in\mathcal{D}(\gamma^{\star})$ for all $i\leq k$. In addition, it
is clear from the definition of the critical index $k$ that any $i>k$
satisfies

$\displaystyle(1-(d-i)\lambda)u_{\sigma(i)}>\lambda\sum_{j\in[i]}u_{\sigma(j)}\quad\implies\quad(1-(d-k)\lambda)u_{\sigma(i)}>\lambda\sum_{j\in[k]}u_{\sigma(j)}\quad\implies\quad\gamma^{\star}u_{\sigma(i)}<-\lambda,$

and thus $\sigma(i)\in[d]\backslash\mathcal{D}(\gamma^{\star})$. In summary,
we have thus shown that $\mathcal{D}(\gamma^{\star})=\\{\sigma(i):i\in[k]\\}$,
which confirms via the optimality condition (67) that $\gamma^{\star}$ solves
indeed the maximization problem (66).

Finally, assume that $\lambda=1/\|\theta\|_{0}$. By using similar arguments as
in the last part of the proof, one can show that $\gamma^{\star}$ remains
optimal in (66) but is no longer unique. Details are omitted for brevity. ∎

By Proposition 1.2, the distributionally robust portfolio selection problem
(65) is equivalent to the convex stochastic optimization problem
$\inf_{\theta\in\Theta,\,\lambda\geq
0}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[f(\theta,\lambda,\widehat{Z})]$
with
$f(\theta,\lambda,\widehat{z})=\lambda\varepsilon+\ell_{c}(\theta,\lambda,\widehat{z})$,
and Proposition 4.2 implies that $f(\theta,\lambda,\widehat{z})=+\infty$
unless $\lambda\geq 1/\|\theta\|_{0}$, which we may thus impose as an explicit
constraint. Proposition 4.2 further enables us to solve the equivalent
stochastic program by ordinary or stochastic gradient descent. Indeed,
Proposition 4.2 implies via the envelope theorem [26, Theorem 2.16] that if
$\lambda\geq 1/\|\theta\|_{0}$, then the gradients of $f$ with respect to
$\theta$ and $\lambda$ are given by

$\displaystyle\nabla_{\theta}f(\theta,\lambda,\widehat{Z})$
$\displaystyle=\left(\gamma^{\star}\widehat{Z}_{1}\,h^{\prime}(\gamma^{\star}\theta_{1}\widehat{Z}_{1}/\lambda),\ldots,\gamma^{\star}\widehat{Z}_{d}\,h^{\prime}(\gamma^{\star}\theta_{d}\widehat{Z}_{d}/\lambda)\right)$
$\displaystyle\nabla_{\lambda}f(\theta,\lambda,\widehat{Z})$
$\displaystyle=\varepsilon+\sum_{i\in[d]}h(\gamma^{\star}\theta_{i}\widehat{Z}_{i}/\lambda)-\frac{1}{\lambda}\sum_{i\in[d]}\gamma^{\star}\theta_{i}\widehat{Z}_{i}\,h^{\prime}(\gamma^{\star}\theta_{i}\widehat{Z}_{i}/\lambda),$

where $\gamma^{\star}$ is defined in as Proposition 4.2, and
$h^{\prime}(s)=-1/s$ if $s<-1$; $=1$ if $-1\leq s<0$. Under a mild local
uniform integrability condition, these random gradients represent unbiased
estimators for the deterministic gradients
$\nabla_{\theta}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[f(\theta,\lambda,\widehat{Z})]$
and
$\nabla_{\lambda}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[f(\theta,\lambda,\widehat{Z})]$,
respectively. In principle, these estimators can thus be used in stochastic
gradient descent algorithms. However, they may fail to be Lipschitz continuous
in $(\theta,\lambda)$ unless the support of $\widehat{\mathbb{P}}$ is a
compact subset of $\mathbb{R}_{++}^{d}$. Hence, stochastic gradient descent
may fail to converge. Even if $\mathbb{\widehat{P}}$ is discrete, the
Lipschitz modulus of the gradient estimators depends on the atoms of
$\mathbb{\widehat{P}}$ and may thus become arbitrarily large, in which case
classical as well as stochastic gradient descent suffer from numerical
instability and poor convergence rates. We therefore suggest to solve the
equivalent stochastic program with the adaptive Golden Ratio Algorithm
introduced in [58, § 2]. If $\mathbb{\widehat{P}}$ is discrete, this algorithm
finds a $\delta$-suboptimal solution in $\mathcal{O}(1/\delta)$ iterations.

In the last experiment we assess the out-of-sample performance of various log-
optimal portfolios with $d=10$ assets. To this end, we assume that the unknown
true asset return distribution $\mathbb{P}$ is lognormal and that its mean and
covariance matrix coincide with the empirical mean and the Ledoit-Wolf
covariance shrinkage estimator [50] corresponding to the 600 most recent
monthly returns in the ‘$10$ Industry Portfolios’ dataset from the Fama-French
online data
library.111http://mba.tuck.dartmouth.edu/pages/faculty/ken.french/data_library.html
Our experiment consists of $1{,}000$ independent trials. In each trial we
construct $\widehat{\mathbb{P}}$ as the empirical distribution on $100$
training samples from $\mathbb{P}$. Different distributionally robust log-
optimal portfolios are then obtained by solving the stochastic programming
reformulation of (65) with the adaptive Golden Ratio Algorithm for different
values of $\varepsilon\in\\{a\cdot
10^{b}:a\in\\{1,\dots,10\\},\;b\in\\{-4,\cdots,-1\\}\\}$. The sample average
approximation (SAA) portfolio is obtained similarly by setting
$\varepsilon=0$. Finally, the out-of-sample performance
$\mathbb{E}_{Z\sim\mathbb{P}}[-\log(\langle\theta,Z\rangle]$ of any fixed
portfolio $\theta\in\Theta$ is evaluated empirically by using $10^{6}$ test
samples from $\mathbb{P}$. Figure 3 (a) plots the out-of-sample performance of
the distributionally robust portfolios as a function of $\varepsilon$ averaged
across all $1{,}000$ trials. We conclude that one can indeed improve on SAA by
accounting for distributional ambiguity. Figure 3 (b) visualizes the
distribution of the out-of-sample performance (which reflects the uncertainty
of the $100$ training samples) of the SAA portfolio and the DRO portfolio
corresponding to $\varepsilon=10^{-2}$. The picture suggests that accounting
for distributional ambiguity not only reduces the expected logarithmic
disutility but also (significantly) reduces the dispersion of the disutility.

Figure 3: (Left) Average out-of-sample performance of the distributionally
robust log-optimal portfolios as a function of $\varepsilon$. (Right)
Distribution of the out-of-sample performance for $\varepsilon=0$ and
$\varepsilon=10^{-2}$.

Acknowledgements. This research was supported by the Swiss National Science
Foundation under the NCCR Automation (grant agreement 51NF40_180545) and under
an Early Postdoc.Mobility Fellowship awarded to the first author (grant
agreement P2ELP2_195149).

## References

  * Aolaritei et al. [2022a] L. Aolaritei, N. Lanzetti, H. Chen, and F. Dörfler.  Uncertainty propagation via optimal transport ambiguity sets.  _arXiv preprint arXiv:2205.00343_ , 2022a.
  * Aolaritei et al. [2022b] L. Aolaritei, S. Shafieezadeh-Abadeh, and F. Dörfler.  The performance of wasserstein distributionally robust m-estimators in high dimensions.  _arXiv preprint arXiv:2206.13269_ , 2022b.
  * Attouch and Azé [1993] H. Attouch and D. Azé.  Approximation and regularization of arbitrary functions in Hilbert spaces by the Lasry-Lions method.  _Annales de l’Institut Henri Poincaré_ , 10(3):289–312, 1993.
  * Attouch and Wets [1989] H. Attouch and R.-B. Wets.  Epigraphical analysis.  _Annales de l’Institut Henri Poincaré_ , 6:73–100, 1989\.
  * Banach [1938] S. Banach.  Über homogene Polynome in ($L^{2}$).  _Studia Mathematica_ , 7(1):36–44, 1938.
  * Bartl et al. [2021] D. Bartl, S. Drapeau, J. Obłój, and J. Wiesel.  Sensitivity analysis of Wasserstein distributionally robust optimization problems.  _Proceedings of the Royal Society A_ , 477:20210176, 2021\.
  * Bauschke et al. [2011] H. H. Bauschke, P. L. Combettes, et al.  _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_.  Springer, 2011.
  * Ben-Tal and Nemirovski [2001] A. Ben-Tal and A. Nemirovski.  _Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications_.  SIAM, 2001.
  * Bertsekas [1973] D. P. Bertsekas.  Stochastic optimization problems with nondifferentiable cost functionals.  _Journal of Optimization Theory and Applications_ , 12(2):218–231, 1973.
  * Bertsekas [2009] D. P. Bertsekas.  _Convex Optimization Theory_.  Athena Scientific, 2009.
  * Billingsley [2013] P. Billingsley.  _Convergence of Probability Measures_.  Wiley, 2013.
  * Blanchet et al. [2019a] J. Blanchet, P. W. Glynn, J. Yan, and Z. Zhou.  Multivariate distributionally robust convex regression under absolute error loss.  In _Advances in Neural Information Processing Systems_ , pages 11817–11826, 2019a.
  * Blanchet et al. [2019b] J. Blanchet, Y. Kang, and K. Murthy.  Robust Wasserstein profile inference and applications to machine learning.  _Journal of Applied Probability_ , 56(3):830–857, 2019b.
  * Blanchet and Murthy [2019] J. Blanchet and K. Murthy.  Quantifying distributional model risk via optimal transport.  _Mathematics of Operations Research_ , 44(2):565–600, 2019.
  * Blanchet et al. [2022a] J. Blanchet, K. Murthy, and N. Si.  Confidence regions in Wasserstein distributionally robust estimation.  _Biometrika_ , 109(2):295–315, 2022a.
  * Blanchet et al. [2022b] J. Blanchet, K. Murthy, and F. Zhang.  Optimal transport-based distributionally robust optimization: Structural properties and iterative schemes.  _Mathematics of Operations Research_ , 47(2):1500–1529, 2022b.
  * Boskos et al. [2021] D. Boskos, J. Cortes, and S. Martinez.  Data-driven ambiguity sets with probabilistic guarantees for dynamic processes.  _IEEE Transactions on Automatic Control_ , 66(7):2991–3006, 2021.
  * Bougeard et al. [1991] M. Bougeard, J.-P. Penot, and A. Pommellet.  Towards minimal assumptions for the infimal convolution regularization.  _Journal of Approximation Theory_ , 64(3):245–270, 1991.
  * Bredies et al. [2010] K. Bredies, K. Kunisch, and T. Pock.  Total generalized variation.  _SIAM Journal on Imaging Sciences_ , 3(3):492–526, 2010.
  * Chen and Paschalidis [2019] R. Chen and I. Paschalidis.  Selecting optimal decisions via distributionally robust nearest-neighbor regression.  In _Advances in Neural Information Processing Systems_ , pages 749–759, 2019.
  * Chen and Paschalidis [2018] R. Chen and I. C. Paschalidis.  A robust learning approach for regression models based on distributionally robust optimization.  _Journal of Machine Learning Research_ , 19(1):517–564, 2018.
  * Chen et al. [2022] Z. Chen, D. Kuhn, and W. Wiesemann.  Data-driven chance constrained programs over Wasserstein balls.  _Operations Research (Forthcoming)_ , 2022.
  * Clément and Desch [2008] P. Clément and W. Desch.  Wasserstein metric and subordination.  _Studia Mathematica_ , 1(189):35–52, 2008.
  * Coulson et al. [2021] J. Coulson, J. Lygeros, and F. Dörfler.  Distributionally robust chance constrained data-enabled predictive control.  _IEEE Transactions on Automatic Control_ , 67(7):3289–3304, 2021.
  * Cover and Thomas [2006] T. Cover and J. Thomas.  _Elements of Information Theory_.  Wiley, 2006.
  * De la Fuente [2000] A. De la Fuente.  _Mathematical Methods and Models for Economists_.  Cambridge University Press, 2000.
  * Duchi et al. [2021] J. C. Duchi, P. W. Glynn, and H. Namkoong.  Statistics of robust optimization: A generalized empirical likelihood approach.  _Mathematics of Operations Research_ , 46(3):946–969, 2021.
  * Duchi and Namkoong [2021] J. C. Duchi and H. Namkoong.  Learning models with uniform performance via distributionally robust optimization.  _Annals of Statistics_ , 49(3):1378–1406, 2021\.
  * Farnia and Tse [2016] F. Farnia and D. Tse.  A minimax approach to supervised learning.  In _Advances in Neural Information Processing Systems_ , pages 4240–4248, 2016.
  * Finlay and Oberman [2021] C. Finlay and A. M. Oberman.  Scaleable input gradient regularization for adversarial robustness.  _Machine Learning with Applications_ , 3:100017, 2021.
  * Gao [2022] R. Gao.  Finite-sample guarantees for Wasserstein distributionally robust optimization: Breaking the curse of dimensionality.  _Operations Research (Forthcoming)_ , 2022.
  * Gao et al. [2022] R. Gao, X. Chen, and A. J. Kleywegt.  Wasserstein distributionally robust optimization and variation regularization.  _Operations Research (Forthcoming)_ , 2022.
  * Gao and Kleywegt [202316] R. Gao and A. J. Kleywegt.  Distributionally robust stochastic optimization with Wasserstein distance.  _Mathematics of Operations Research (Forthcoming)_ , 202316.
  * Gao et al. [2018] R. Gao, L. Xie, Y. Xie, and H. Xu.  Robust hypothesis testing using Wasserstein uncertainty sets.  In _Advances in Neural Information Processing Systems_ , pages 7902–7912, 2018.
  * Gulrajani et al. [2017] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville.  Improved training of Wasserstein GANs.  In _Advances in Neural Information Processing Systems_ , pages 5769–5779, 2017.
  * Hein and Andriushchenko [2017] M. Hein and M. Andriushchenko.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In _Advances in Neural Information Processing Systems_ , pages 2263–2273, 2017.
  * Hiriart-Urruty [1980] J.-B. Hiriart-Urruty.  Extension of Lipschitz functions.  _Journal of Mathematical Analysis and Applications_ , 77(2):539–554, 1980.
  * Ho-Nguyen et al. [2022a] N. Ho-Nguyen, F. Kılınç-Karzan, S. Küçükyavuz, and D. Lee.  Distributionally robust chance-constrained programs with right-hand side uncertainty under Wasserstein ambiguity.  _Mathematical Programming_ , 196(1–2):641–672, 2022a.
  * Ho-Nguyen et al. [2022b] N. Ho-Nguyen, F. Kılınç-Karzan, S. Küçükyavuz, and D. Lee.  Strong formulations for distributionally robust chance-constrained programs with left-hand side uncertainty under Wasserstein ambiguity.  _Operations Research (Forthcoming)_ , 2022b.
  * Ho-Nguyen and Wright [2022] N. Ho-Nguyen and S. J. Wright.  Adversarial classification via distributional robustness with Wasserstein ambiguity.  _Mathematical Programming (Forthcoming)_ , 2022.
  * Hu et al. [2014] Y. Hu, G. Ongie, S. Ramani, and M. Jacob.  Generalized higher degree total variation (HDTV) regularization.  _IEEE Transactions on Image Processing_ , 23(6):2423–2435, 2014.
  * Jakubovitz and Giryes [2018] D. Jakubovitz and R. Giryes.  Improving DNN robustness to adversarial attacks using Jacobian regularization.  In _European Conference on Computer Vision_ , pages 514–529, 2018\.
  * Koçyiğit et al. [2020] Ç. Koçyiğit, N. Rujeerapaiboon, and D. Kuhn.  Regret minimization and separation in multi-bidder multi-item auctions.  _Optimization Online_ , 2020.
  * Koçyiğit et al. [2022] Ç. Koçyiğit, N. Rujeerapaiboon, and D. Kuhn.  Robust multidimensional pricing: Separation without regret.  _Mathematical Programming_ , 196(1–2):841–874, 2022.
  * Krantz and Parks [2002] S. G. Krantz and H. R. Parks.  _A Primer of Real Analytic Functions_.  Springer, 2002.
  * Kuhn et al. [2019] D. Kuhn, P. Mohajerin Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadeh.  Wasserstein distributionally robust optimization: Theory and applications in machine learning.  In _Operations Research & Management Science in the Age of Analytics_, pages 130–166. INFORMS, 2019.
  * Kwon et al. [2020] Y. Kwon, W. Kim, J.-H. Won, and M. C. Paik.  Principled learning method for Wasserstein distributionally robust optimization with local perturbations.  In _International Conference on Machine Learning_ , pages 5567–5576, 2020.
  * Lam [2019] H. Lam.  Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization.  _Operations Research_ , 67(4):1090–1105, 2019\.
  * LeCun et al. [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Ledoit and Wolf [2004] O. Ledoit and M. Wolf.  A well-conditioned estimator for large-dimensional covariance matrices.  _Journal of Multivariate Analysis_ , 88(2):365–411, 2004.
  * Lee and Raginsky [2018] J. Lee and M. Raginsky.  Minimax statistical learning with Wasserstein distances.  In _Advances in Neural Information Processing Systems_ , pages 2687–2696, 2018.
  * Lefkimmiatis and Unser [2013] S. Lefkimmiatis and M. Unser.  Poisson image reconstruction with Hessian Schatten-norm regularization.  _IEEE Transactions on Image Processing_ , 22(11):4314–4327, 2013.
  * Lefkimmiatis et al. [2013] S. Lefkimmiatis, J. P. Ward, and M. Unser.  Hessian Schatten-norm regularization for linear inverse problems.  _IEEE Transactions on Image Processing_ , 22(5):1873–1888, 2013.
  * Lehmann and Casella [2006] E. L. Lehmann and G. Casella.  _Theory of Point Estimation_.  Springer, 2006.
  * Levy and Nikoukhah [2004] B. C. Levy and R. Nikoukhah.  Robust least-squares estimation with a relative entropy constraint.  _IEEE Transactions on Information Theory_ , 50(1):89–104, 2004.
  * Levy and Nikoukhah [2012] B. C. Levy and R. Nikoukhah.  Robust state space filtering under incremental model perturbations subject to a relative entropy tolerance.  _IEEE Transactions on Automatic Control_ , 58(3):682–695, 2012.
  * Lyu et al. [2015] C. Lyu, K. Huang, and H.-N. Liang.  A unified gradient regularization family for adversarial examples.  In _International Conference on Data Mining_ , pages 301–309, 2015\.
  * Malitsky [2020] Y. Malitsky.  Golden ratio algorithms for variational inequalities.  _Mathematical Programming_ , 184(1):383–410, 2020\.
  * Milgrom and Segal [2002] P. Milgrom and I. Segal.  Envelope theorems for arbitrary choice sets.  _Econometrica_ , 70(2):583–601, 2002.
  * Mohajerin Esfahani and Kuhn [2018] P. Mohajerin Esfahani and D. Kuhn.  Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations.  _Mathematical Programming_ , 171(1–2):115–166, 2018.
  * Mohajerin Esfahani et al. [2018] P. Mohajerin Esfahani, S. Shafieezadeh-Abadeh, G. A. Hanasusanto, and D. Kuhn.  Data-driven inverse optimization with imperfect information.  _Mathematical Programming_ , 167(1):191–234, 2018\.
  * Munkres [2000] J. R. Munkres.  _Topology_.  Prentice Hall, 2000.
  * Nagarajan and Kolter [2017] V. Nagarajan and J. Z. Kolter.  Gradient descent GAN optimization is locally stable.  In _Advances in Neural Information Processing Systems_ , pages 5591–5600, 2017.
  * Nguyen et al. [2022] V. A. Nguyen, D. Kuhn, and P. Mohajerin Esfahani.  Distributionally robust inverse covariance estimation: The Wasserstein shrinkage estimator.  _Operations Research_ , 70(1):490–515, 2022.
  * Nguyen et al. [2021] V. A. Nguyen, S. Shafieezadeh-Abadeh, D. Kuhn, and P. Mohajerin Esfahani.  Bridging Bayesian and minimax mean square error estimation via Wasserstein distributionally robust optimization.  _Mathematics of Operations Research (Forthcoming)_ , 2021.
  * Ororbia II et al. [2017] A. G. Ororbia II, D. Kifer, and C. L. Giles.  Unifying adversarial training algorithms with data gradient regularization.  _Neural Computation_ , 29(4):867–887, 2017.
  * Parikh and Boyd [2014] N. Parikh and S. Boyd.  Proximal algorithms.  _Foundations and Trends in Optimization_ , 1(3):127–239, 2014.
  * Penot [1998] J.-P. Penot.  Proximal mappings.  _Journal of Approximation Theory_ , 94(2):203–221, 1998.
  * Polyak [1987] B. Polyak.  _Introduction to Optimization_.  Optimization Software, Inc., 1987.
  * Rockafellar [1970] R. T. Rockafellar.  _Convex Analysis_.  Princeton University Press, 1970.
  * Rockafellar and Wets [2009] R. T. Rockafellar and R. J.-B. Wets.  _Variational Analysis_.  Springer, 2009.
  * Roth et al. [2017] K. Roth, A. Lucchi, S. Nowozin, and T. Hofmann.  Stabilizing training of generative adversarial networks through regularization.  In _Advances in Neural Information Processing Systems_ , pages 2018–2028, 2017.
  * Rujeerapaiboon et al. [2016] N. Rujeerapaiboon, D. Kuhn, and W. Wiesemann.  Robust growth-optimal portfolios.  _Management Science_ , 62(7):2090–2109, 2016\.
  * Shafieezadeh-Abadeh et al. [2019] S. Shafieezadeh-Abadeh, D. Kuhn, and P. Mohajerin Esfahani.  Regularization via mass transportation.  _Journal of Machine Learning Research_ , 20(103):1–68, 2019.
  * Shafieezadeh-Abadeh et al. [2015] S. Shafieezadeh-Abadeh, P. Mohajerin Esfahani, and D. Kuhn.  Distributionally robust logistic regression.  In _Advances in Neural Information Processing Systems_ , pages 1576–1584, 2015.
  * Shafieezadeh-Abadeh et al. [2018] S. Shafieezadeh-Abadeh, V. A. Nguyen, D. Kuhn, and P. Mohajerin Esfahani.  Wasserstein distributionally robust Kalman filtering.  In _Advances in Neural Information Processing Systems_ , pages 8474–8483, 2018.
  * Shapiro et al. [2014] A. Shapiro, D. Dentcheva, and A. Ruszczyński.  _Lectures on Stochastic Programming: Modeling and Theory_.  SIAM, 2014.
  * Shen and Jiang [2022] H. Shen and R. Jiang.  Chance-constrained set covering with Wasserstein ambiguity.  _Mathematical Programming (Forthcoming)_ , 2022.
  * Sinha et al. [2018] A. Sinha, H. Namkoong, and J. Duchi.  Certifying some distributional robustness with principled adversarial training.  In _International Conference on Learning Representations_ , 2018.
  * Sion [1958] M. Sion.  On general minimax theorems.  _Pacific Journal of Mathematics_ , 8(1):171–176, 1958.
  * Taşkesen et al. [2022] B. Taşkesen, S. Shafieezadeh-Abadeh, and D. Kuhn.  Semi-discrete optimal transport: Hardness, regularization and numerical solution.  _Mathematical Programming (Forthcoming)_ , pages 1–74, 2022.
  * Toland [1978] J. F. Toland.  Duality in nonconvex optimization.  _Journal of Mathematical Analysis and Applications_ , 66(2):399–415, 1978.
  * Tu et al. [2019] Z. Tu, J. Zhang, and D. Tao.  Theoretical analysis of adversarial learning: A minimax approach.  In _Advances in Neural Information Processing Systems_ , pages 12280–12290, 2019.
  * Van Parys et al. [2021] B. P. Van Parys, P. Mohajerin Esfahani, and D. Kuhn.  From data to decisions: Distributionally robust optimization is optimal.  _Management Science_ , 67(6):3387–3402, 2021\.
  * Varga et al. [2018] D. Varga, A. Csiszárik, and Z. Zombori.  Gradient regularization improves accuracy of discriminative models.  _Schedae Informaticae_ , 27:31–45, 2018.
  * Villani [2008] C. Villani.  _Optimal Transport: Old and New_.  Springer, 2008.
  * Volpi et al. [2018] R. Volpi, H. Namkoong, O. Sener, J. Duchi, V. Murino, and S. Savarese.  Generalizing to unseen domains via adversarial data augmentation.  In _Advances in Neural Information Processing Systems_ , pages 5339–5349, 2018.
  * Wang et al. [2019] Y. Wang, X. Ma, J. Bailey, J. Yi, B. Zhou, and Q. Gu.  On the convergence and robustness of adversarial training.  In _International Conference on Machine Learning_ , pages 6586–6595, 2019.
  * Xie [2021] W. Xie.  On distributionally robust chance constrained programs with Wasserstein distance.  _Mathematical Programming_ , 186(1):115–155, 2021\.
  * Yang [2020] I. Yang.  Wasserstein distributionally robust stochastic control: A data-driven approach.  _IEEE Transactions on Automatic Control_ , 66(8):3863–3870, 2020.
  * Yue et al. [2022] M.-C. Yue, D. Kuhn, and W. Wiesemann.  On linear optimization over Wasserstein balls.  _Mathematical Programming_ , 195(1–2):1107–1122, 2022.
  * Zhao and Guan [2018] C. Zhao and Y. Guan.  Data-driven risk-averse stochastic optimization with Wasserstein metric.  _Operations Research Letters_ , 46(2):262–267, 2018.
  * Zhen et al. [2021] J. Zhen, D. Kuhn, and W. Wiesemann.  Mathematical foundations of robust and distributionally robust optimization.  _arXiv:2105.00760_ , 2021.
  * Zorzi [2016] M. Zorzi.  Robust Kalman filtering under model perturbations.  _IEEE Transactions on Automatic Control_ , 62(6):2902–2907, 2016.
  * Zorzi [2017] M. Zorzi.  On the robustness of the Bayes and Wiener estimators under model uncertainty.  _Automatica_ , 83:133–140, 2017.

##  Appendix A Computation of Nash Equilibria Revisited

All results of Section 2.2 generalize to decision problems where $Z=(X,Y)$
consists of two random vectors $X\in\mathbb{R}^{d_{x}}$ and
$Y\in\mathbb{R}^{d_{y}}$ with $d_{x}+d_{y}=d$ and where the loss function is
piecewise concave in $X$ but may display an arbitrary dependence on
$Y$—provided that the adversary cannot move probability mass along the
$Y$-space. Propositions 2.12 and 2.14 as well as Theorem 2.16 immediately
carry over to this generalized setting with obvious minor modifications at the
expense of a higher notational overhead that could obfuscate the proof ideas.
For this reason, said generalizations of Propositions 2.12 and 2.14 and of
Theorem 2.16, which are needed for the numerical experiments in Section 4.1,
are stated below without proofs. These generalizations rely on the following
updated version of Assumption 2.9.

######  Assumption A.1 (Convexity conditions revisited).

  1. (i)

The cost of moving probability mass from $(x,y)$ to
$(\widehat{x},\widehat{y})$ is given by $c(x,\widehat{x})$ if $y=\widehat{y}$
and amounts to $+\infty$ if $y\neq\widehat{y}$. We also assume that
$c(x,\widehat{x})$ is lower semi-continuous in $(x,\widehat{x})$ and convex in
$x$.

  2. (ii)

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

  3. (iii)

The support set of the random vector $X$ is representable as
$\mathcal{X}=\\{x\in\mathbb{R}^{d_{x}}:f_{k}(x)\leq 0~{}\forall k\in[K]\\}$
for some $K\in\mathbb{N}$, where each function $f_{k}(x)$ 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.

We also maintain Assumption 2.8, whereby the reference distribution
$\widehat{\mathbb{P}}$ is discrete, and we use
$\widehat{z}_{j}=(\widehat{x}_{j},\widehat{y}_{j})$ for $j\in[J]$ to denote
its atoms. Using this convention, we update Assumption 2.11 as follows.

######  Assumption A.2 (Slater conditions).

  1. (i)

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

  2. (ii)

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

We are now ready to generalize Proposition 2.12.

######  Proposition A.3 (Primal reformulation revisited).

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

$\displaystyle\begin{array}[]{cl@{\,}l}\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_{x}}&\forall
i\in[I],\,j\in[J],\,k\in[K]\\\\[8.61108pt]
&\displaystyle(-\ell_{i})^{*2}(\theta,\zeta^{\ell}_{ij},\widehat{y}_{j})+\lambda
c^{*1}(\zeta^{c}_{ij}/\lambda,\widehat{x}_{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}$ (72)

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

Proposition A.4 below generalizes Proposition 2.14 from the main text.

######  Proposition A.4 (Dual reformulation revisited).

If Assumptions 2.8, 2.13, A.1 and A.2 hold and $\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},\widehat{x}_{j}+\xi_{ij}/q_{ij},\widehat{y}_{j})-\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_{x}},~{}\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{x}_{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{x}_{j}+{\xi_{ij}}/{q_{ij}},\widehat{x}_{j})\leq\varepsilon,\end{array}$
(79)

where $\ell_{i}^{*1}(\alpha,x,y)$ denotes the conjugate of
$\ell_{i}(\theta,x,y)$ with respect to $\theta$ for fixed $x$ and $y$.

Given Propositions A.3 and A.4, we are finally ready to generalize Theorem
2.16.

######  Theorem A.5 (Computing Nash equilibria revisited).

If Assumptions 2.8, 2.15, A.1 and A.2 hold and $\varepsilon>0$, then the
optima 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^{h\star}_{ij}\\}_{i,j},\\{\tau_{ijk}^{\star},\zeta^{f\star}_{ijk}\\}_{i,j,k})$
solves (72), 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 (79) 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{x}_{j}+{\xi_{ij}^{\star}}/{q_{ij}^{\star}},\widehat{y}_{j})}$
solves the dual DRO problem (3), where

$\displaystyle\mathcal{I}_{j}^{+}=\left\\{i\in[I]:q_{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\\}.$

##  Appendix B On the Solution of Distributionally Robust Learning Models over
Linear Hypotheses with Quadratic Transportation Costs

Consider a distributionally robust learning model over linear hypotheses of
the form (48), and assume that the ambiguity set is defined in terms of the
transportation cost function $c(z,\widehat{z})=\|z-\widehat{z}\|^{2}$, where
$\|\cdot\|$ is an arbitrary norm on $\mathbb{R}^{d}$. By Proposition 1.2, the
inner maximization problem in (48) over the probability distributions has the
same optimal value as the univariate minimization problem

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

and by Theorem 3.8 (ii), the $c$-transform satisfies

$\displaystyle\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^{2}.$ (81)

In the following we will establish easily checkable sufficient conditions for
problem (81) to be convex. To this end, we first recall some key definitions
from convex analysis. A differentiable loss function $L$ with derivative
$L^{\prime}$ is called $M$-smooth for some $M\geq 0$ if
$|L^{\prime}(s_{1})-L^{\prime}(s_{2})|\leq M|s_{1}-s_{2}|$ for all $s_{1}$ and
$s_{2}$ in the domain of $L$. The quadratic growth rate of a loss function $L$
is defined as
$G=\inf\\{g\in\mathbb{R}_{+}:\sup_{s\in\mathbb{R}}L(s)-gs^{2}<\infty\\}$. The
quadratic growth rate $G$ of an $M$-smooth function satisfies $G\leq M/2$.

We first provide easily checkable sufficient conditions for problem (81) to be
convex and solvable.

######  Proposition B.1 (Convexity and solvability of problem (81)).

If the univariate loss function $L$ is convex, differentiable and $M$-smooth
with quadratic growth rate $G$, then the following hold.

  1. (i)

If $\lambda<G\|\theta\|_{*}^{2}$, then problem (81) is unbounded.

  2. (ii)

If $\lambda>G\|\theta\|_{*}^{2}$, then problem (81) is solvable, and any
maximizer $\gamma^{\star}$ satisfies
$|\gamma^{\star}|\geq\frac{\|\theta\|_{*}}{2\lambda}|L^{\prime}(\langle\theta,\widehat{z}\rangle)|$.

  3. (iii)

If $\lambda>M\|\theta\|_{*}^{2}/2$, then problem (81) is convex and admits a
unique maximizer.

###### Proof.

As for assertion (i), assume that $\lambda<G\|\theta\|^{2}_{*}$. Thus, there
exist two strictly positive constants $g$ and $\delta$ such that
$\lambda<g\|\theta\|^{2}_{*}$ and $g+\delta<G$. The definition of the
$c$-transform in (81) then implies that

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle=\sup_{s\in\mathbb{R}}L(s)-\lambda\left(\frac{s-\langle\theta,\widehat{z}\rangle}{\|\theta\|_{*}}\right)^{2}\geq\sup_{s\in\mathbb{R}}L(s)-g(s-\langle\theta,\widehat{z}\rangle)^{2}$
$\displaystyle=\sup_{s\in\mathbb{R}}L(s)-(g+\delta)s^{2}+g\left(s^{2}-(s-\langle\theta,\widehat{z}\rangle)^{2}\right)+\delta
s^{2}$
$\displaystyle\geq\sup_{s\in\mathbb{R}}L(s)-(g+\delta)s^{2}+\inf_{s\in\mathbb{R}}\delta
s^{2}-g\langle\theta,\widehat{z}\rangle^{2}+2gs\langle\theta,\widehat{z}\rangle=+\infty,$

where the first equality exploits the variable substitution
$s\leftarrow\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*}$, and the
first inequality holds because $\lambda<g\|\theta\|^{2}_{*}$. The second
equality as well as the second inequality are elementary. The last equality,
finally, holds because the supremum in the last line of the above expression
evaluates to $+\infty$ (as $g+\delta<G$) and because the infimum is finite (as
$\delta>0$). Thus, the claim follows.

As for assertion (ii), assume that $\lambda>G\|\theta\|^{2}_{*}$. Thus, there
exist two strictly positive constants $g$ and $\delta$ such that
$\lambda>g\|\theta\|^{2}_{*}$ and $g-\delta>G$. The definition of the
$c$-transform in (81) then implies that

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})$
$\displaystyle\leq\sup_{s\in\mathbb{R}}L(s)-(g-\delta)s^{2}+g\left(s^{2}-(s-\langle\theta,\widehat{z}\rangle)^{2}\right)-\delta
s^{2}$
$\displaystyle\leq\sup_{s\in\mathbb{R}}L(s)-(g-\delta)s^{2}+\sup_{s\in\mathbb{R}}-\delta
s^{2}-g\langle\theta,\widehat{z}\rangle^{2}+2gs\langle\theta,\widehat{z}\rangle<+\infty,$

where the first inequality follows from our assumption that
$\lambda>g\|\theta\|^{2}_{*}$ and from elementary rearrangements familiar from
the proof of assertion (i), while the second inqueality exploits the sub-
additivity of the supremum. The two suprema in the last line, finally, are
both finite because $g-\delta>G$ and $\delta>0$, respectively. Thus,
$\ell_{c}(\theta,\lambda,\widehat{z})$ is indeed finite. By slightly adapting
the above arguments, one can further show that the objective function of the
maximization problem in (81) is continuous and bounded above by a function
with compact superlevel sets, which implies that this problem admits indeed a
maximizer $\gamma^{\star}$. Details are omitted for brevity. The stipulated
lower bound on $|\gamma^{\star}|$ is trivial if
$L^{\prime}(\langle\theta,\widehat{z}\rangle)=0$. From now on we may thus
assume without loss of generality that
$L^{\prime}(\langle\theta,\widehat{z}\rangle)>0$ (the case
$L^{\prime}(\langle\theta,\widehat{z}\rangle)<0$ can be handled similarly).
Clearly, $\gamma^{\star}$ must satisfy the first-order optimality condition

$\displaystyle
L^{\prime}(\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*})\|\theta\|_{*}-2\lambda\gamma^{\star}=0.$
(82)

In the following we distinguish two cases depending on sign of
$\gamma^{\star}$. First, if $\gamma^{\star}\geq 0$, then we have

$\displaystyle|\gamma^{\star}|=\gamma^{\star}=\textstyle\frac{\|\theta\|_{*}}{2\lambda}L^{\prime}(\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*})\geq\frac{\|\theta\|_{*}}{2\lambda}L^{\prime}(\langle\theta,\widehat{z}\rangle),$

where the second equality follows from (82), and the inequality exploits the
convexity of $L$, which ensures that $L^{\prime}$ is non-decreasing. If
$\gamma^{\star}<0$, on the other hand, then we have

$\displaystyle\ell_{c}(\theta,\lambda,z)$
$\displaystyle=L\big{(}\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*}\big{)}-\lambda\hskip
0.43057pt(\gamma^{\star})^{2}$
$\displaystyle=L(\langle\theta,\widehat{z}\rangle)+\int_{0}^{\gamma^{\star}}\left[L^{\prime}(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})\|\theta\|_{*}-2\lambda\gamma\right]\mathrm{d}\gamma$
$\displaystyle\leq
L(\langle\theta,\widehat{z}\rangle)+\int_{0}^{\gamma^{\star}}\left[L^{\prime}(\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*})\|\theta\|_{*}-2\lambda\gamma\right]\mathrm{d}\gamma$
$\displaystyle=L(\langle\theta,\widehat{z}\rangle)+\int_{0}^{\gamma^{\star}}\left[2\lambda\gamma^{\star}-2\lambda\gamma\right]\mathrm{d}\gamma=L(\langle\theta,\widehat{z}\rangle)+\lambda(\gamma^{\star})^{2},$

where the first two equalities follow from the optimality of $\gamma^{\star}$
and the fundamental theorem of calculus, respectively, the inequality holds
due to the monotonicity of $L^{\prime}$ and the assumption that
$\gamma^{\star}<0$, and the third equality follows from (82). By the first-
order convexity condition of $L$, we further obtain

$\displaystyle\ell_{c}(\theta,\lambda,\widehat{z})\geq\sup_{\gamma\in\mathbb{R}}~{}L(\langle\theta,\widehat{z}\rangle)+L^{\prime}(\langle\theta,\widehat{z}\rangle)\gamma\|\theta\|_{*}-\lambda\gamma^{2}=\textstyle
L(\langle\theta,\widehat{z}\rangle)+\frac{1}{4\lambda}[L^{\prime}(\langle\theta,\widehat{z}\rangle)\|\theta\|_{*}]^{2}.$

Combining the upper and lower bounds on $\ell_{c}(\theta,\lambda,\widehat{z})$
derived above then yields

$\displaystyle
L(\langle\theta,\widehat{z}\rangle)+\lambda(\gamma^{\star})^{2}\geq\ell_{c}(\theta,\lambda,\widehat{z})\geq\textstyle
L(\langle\theta,\widehat{z}\rangle)+\frac{1}{4\lambda}[L^{\prime}(\langle\theta,\widehat{z}\rangle)\|\theta\|_{*}]^{2}\implies|\gamma^{\star}|\geq\frac{\|\theta\|_{*}}{2\lambda}|L^{\prime}(\langle\theta,\widehat{z}\rangle)|.$

This completes the proof of assertion (ii).

As for assertion (iii), assume that $\lambda>M\|\theta\|_{*}^{2}/2$. Since $L$
is $M$-smooth by assumption, one readily verifies that the objective function
$L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda\gamma^{2}$
of problem (81) is strongly concave in $\gamma$ for any
$\lambda>M\|\theta\|_{*}^{2}/2$. Therefore, problem (81) must have a unique
maximizer. ∎

The next proposition provides a priori bounds on the minimizers of problem
(80).

######  Proposition B.2 (Bounds on the minimizers of (80)).

If $L$ is convex, upper semi-continuous, differentiable and $M$-smooth with
quadratic growth rate $G$, $L(\langle\theta,\widehat{Z}\rangle)$ is
$\widehat{\mathbb{P}}$-integrable, $c(z,\widehat{z})=\|z-\widehat{z}\|^{2}$
for some norm $\|\cdot\|$, and $\varepsilon>0$, then (80) has a minimizer

$\lambda^{\star}\in\Big{[}\sqrt{\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\big{[}|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\big{]}\|\theta\|_{*}^{2}/(4\varepsilon)},~{}\sqrt{\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\big{[}|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\big{]}\|\theta\|_{*}^{2}/\varepsilon}+M\|\theta\|_{*}^{2}/2\Big{]}.$

###### Proof.

Let $\lambda^{\star}$ be any minimizer of problem (80), which is guaranteed to
exist for the following reasons. First, $\ell_{c}(\theta,\lambda,\widehat{Z})$
is convex and lower semi-continuous in $\lambda$. In addition, lower semi-
continuity is preserved by taking expectations with respect to
$\widehat{\mathbb{P}}$ thanks to Fatou’s lemma, which can be applied since
$\ell_{c}(\theta,\lambda,\widehat{Z})$ is bounded below by the
$\widehat{\mathbb{P}}$-integrable random variable
$L(\langle\theta,\widehat{Z}\rangle)$. Finally, the objective function of
problem (80) is bounded below by
$\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[L(\langle\theta,\widehat{Z}\rangle]$,
which grows linearly with $\lambda$. Thus, the minimum of problem (80) must be
attained at some point $\lambda^{\star}\in[0,+\infty)$. Consequently, we have

$\displaystyle\lambda^{\star}\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[L(\langle\theta,\widehat{Z}\rangle]\leq\lambda^{\star}\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell_{c}(\theta,\lambda^{\star},\widehat{Z})]=\inf_{\lambda\geq
0}\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[\ell_{c}(\theta,\lambda,\widehat{Z})].$

By rearranging the above inequality and recalling the definition of
$\ell_{c}$, we then obtain

$\displaystyle\lambda^{\star}\varepsilon$ $\displaystyle\leq\inf_{\lambda\geq
0}\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\sup_{\gamma\in\mathbb{R}}~{}L(\langle\theta,\widehat{Z}\rangle+\gamma\|\theta\|_{*})-L(\langle\theta,\widehat{Z}\rangle)-\lambda\gamma^{2}\right]$
$\displaystyle\leq\inf_{\lambda\geq
0}\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\sup_{\gamma\in\mathbb{R}}~{}\frac{M}{2}\gamma^{2}\|\theta\|_{*}^{2}-\gamma\|\theta\|_{*}L^{\prime}(\langle\theta,\widehat{Z}\rangle)-\lambda\gamma^{2}\right]$
$\displaystyle\leq\inf_{\lambda>{M\|\theta\|_{*}^{2}}/{2}}\lambda\varepsilon+\frac{\|\theta\|_{*}^{2}}{4\lambda-2M\|\theta\|_{*}^{2}}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\right]$
$\displaystyle=\frac{\varepsilon
M\|\theta\|_{*}^{2}}{2}+\sqrt{\varepsilon}\|\theta\|_{*}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\right]^{\frac{1}{2}},$

where the second inequality exploits Taylor’s theorem and the $M$-smoothness
of $L$, the third inequality holds because we restrict the feasible set of a
minimization problem and because the inner maximization problem is solved by
$\gamma^{\star}=-L^{\prime}(\langle\theta,\widehat{Z})\|\theta\|_{*}/(2\lambda-M\|\theta\|_{*}^{2})\rangle$
whenever $\lambda>M\|\theta\|_{*}^{2}/2$, and the last equality follows from
the analytical solution of the minimization problem over $\lambda$. The
desired upper bound on $\lambda^{\star}$ is then obtained by dividing both
sides of the above inequality by $\varepsilon$.

Note that the desired lower bound on $\lambda^{\star}$ trivially holds if
$\theta=0$. From now on we may thus assume without loss of generality that
$\theta\neq 0$. From Proposition B.1 we know that $\lambda^{\star}\geq
G\|\theta\|_{*}^{2}$. Below we assume without much loss of generality that
$\lambda^{\star}>G\|\theta\|_{*}^{2}$. Indeed, the case
$\lambda^{\star}=G\|\theta\|_{*}^{2}$ can be handled similarly to Case $2$ in
the proof of [16, Lemma 4]. In addition, we temporarily denote the objective
function of problem (80) by $f(\lambda)$. The first-order optimality condition
of problem (80) then implies that the right derivative of $f$ at
$\lambda^{\star}$, which we denote by
$\partial_{\lambda}f((\lambda^{\star})^{+})$, must be non-negative, that is,

$\displaystyle
0\leq\partial_{\lambda}f((\lambda^{\star})^{+})=\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\partial_{\lambda}\ell_{c}(\theta,(\lambda^{\star})^{+},\widehat{Z})\right],$
(83)

where the right derivative and the expectation may be interchanged thanks to
[9, Proposition 2.1]. Next, we can use the envelope theorem [59, Corollary 4]
to demonstrate that

$\displaystyle\partial_{\lambda}\ell_{c}(\theta,(\lambda^{\star})^{+},\widehat{z})=\max_{\gamma^{\star}\in\Gamma^{\star}(\lambda^{\star},\widehat{z})}-(\gamma^{\star})^{2}$
(84)

with
$\Gamma^{\star}(\lambda^{\star},\widehat{z})=\operatorname*{arg\,max}\\{L(\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*})-\lambda^{\star}\gamma^{2}:\gamma\in\mathbb{R}\\}$.
The envelope theorem applies because
$L\big{(}\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*}\big{)}-\lambda\hskip
0.43057pt\gamma^{2}$ is upper semi-continuous in $\gamma$,
$\partial_{\lambda}(L\big{(}\langle\theta,\widehat{z}\rangle+\gamma\|\theta\|_{*}\big{)}-\lambda\hskip
0.43057pt\gamma^{2})=-\gamma^{2}$ is trivially continuous in $\gamma$ and
$\lambda$, and $\Gamma^{\star}(\lambda^{\star},\widehat{z})$ is compact. To
see that $\Gamma^{\star}(\lambda^{\star},\widehat{z})$ is compact, we need to
show that it is closed as well as bounded. Closedness follows immediately from
the upper semi-continuity of $L$. To show boundedness, select any
$\gamma^{\star}\in\Gamma^{\star}(\lambda^{\star},\widehat{z})$. Since $L$ has
quadratic growth rate $G$ and since $\lambda^{\star}>G\|\theta\|_{*}^{2}$ by
assumption, there exist $\delta>0$ and $C>0$ such that
$L(u)\leq(G+\delta)u^{2}+C$ and
$\lambda^{\star}\geq(G+2\delta)\|\theta\|_{*}^{2}$. In addition, since $L$ is
convex, we have $L(\langle\theta,\widehat{z}\rangle)\geq
L(0)+L^{\prime}(0)\langle\theta,\widehat{z}\rangle$. Substituting these three
estimates into the inequality
$\ell_{c}(\theta,\lambda^{\star},\widehat{z})=L(\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*})-\lambda(\gamma^{\star})^{2}\geq
L(\langle\theta,\widehat{z}\rangle)$, we obtain

$\displaystyle(G+\delta)(\langle\theta,\widehat{z}\rangle+\gamma^{\star}\|\theta\|_{*})^{2}+C-(G+2\delta)(\gamma^{\star})^{2}\|\theta\|_{*}^{2}\geq
L(0)+L^{\prime}(0)\langle\theta,\widehat{z}\rangle,$

which is equivalent to

$\displaystyle\left(\gamma^{\star}\|\theta\|_{*}-\frac{G+\delta}{\delta}\langle\theta,\widehat{z}\rangle\right)^{2}\leq\frac{C-L(0)-L^{\prime}(0)\langle\theta,\widehat{z}\rangle}{\delta}+\left(\frac{G+\delta}{\delta}+\frac{(G+\delta)^{2}}{\delta^{2}}\right)(\langle\theta,\widehat{z}\rangle)^{2}.$

Recalling that $\theta\neq 0$, we may conclude that $\gamma^{\star}$ belongs
to the sublevel set of a strictly convex quadratic function and is therefore
bounded. As $\gamma^{\star}\in\Gamma^{\star}(\lambda^{\star},\widehat{z})$ was
chosen freely, $\Gamma^{\star}(\lambda^{\star},\widehat{z})$ is indeed
bounded.

We are now ready to construct the desired lower bound on $\lambda^{\star}$.
Proposition B.1 (ii) implies that every maximizer
$\gamma^{\star}\in\Gamma^{\star}(\lambda^{\star},\widehat{z})$ satisfies
$|\gamma^{\star}|\geq\frac{\|\theta\|_{*}}{2\lambda^{\star}}|L^{\prime}(\langle\theta,\widehat{z}\rangle)|$,
and thus we have

$\displaystyle\frac{\|\theta\|_{*}^{2}}{4(\lambda^{\star})^{2}}\,\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\right]\leq\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\min_{\gamma^{\star}\in\Gamma^{\star}(\lambda^{\star},\widehat{Z})}(\gamma^{\star})^{2}\right]=-\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\partial_{\lambda}\ell_{c}(\theta,(\lambda^{\star})^{+},\widehat{Z})\right]\leq\varepsilon,$

where the equality and the second inequality follow from (84) and (83),
respectively. The desired lower bound on $\lambda^{\star}$ finally follows
from elementary rearrangements of the above inequality. ∎

######  Corollary B.3.

Suppose that all assumptions of Proposition B.2 hold, and define the constants

$\underline{L}=\inf_{\theta\in\Theta}\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}[|L^{\prime}(\langle\theta,\widehat{Z}\rangle|^{2}]\quad\text{and}\quad
R=\sup_{\theta\in\Theta}\|\theta\|_{*}.$

If $0<\varepsilon<\underline{L}/(RM)^{2}$, then problem (80) is solved by some
$\lambda^{\star}>M\|\theta\|_{*}^{2}/2$.

###### Proof.

By Proposition B.2, problem (80) has a minimizer $\lambda^{\star}$ that
satisfies

$\displaystyle\lambda^{\star}\geq\sqrt{\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\big{[}|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\big{]}}\frac{\|\theta\|_{*}}{2\sqrt{\varepsilon}}>\sqrt{\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\big{[}|L^{\prime}(\langle\theta,\widehat{Z}\rangle)|^{2}\big{]}}\frac{RM\|\theta\|_{*}}{2\sqrt{\underline{L}}}\geq\frac{RM\|\theta\|_{*}}{2}\geq\frac{M\|\theta\|_{*}^{2}}{2},$

where the second inequality holds because
$\varepsilon<\underline{L}/(RM)^{2}$, the third inequality follows from the
definition of $\overline{L}$, and the last inequality follows from the
definition of $R$. Thus the claim follows. ∎

Corollary B.3 implies that if $0<\varepsilon<\underline{L}/(RM)^{2}$, then
problem (80) is equivalent to

$\displaystyle\inf_{\lambda>M\|\theta\|_{*}^{2}/2}\;\lambda\varepsilon+\mathbb{E}_{\widehat{Z}\sim\widehat{\mathbb{P}}}\left[\ell_{c}(\theta,\lambda,\widehat{Z})\right].$
(85)

By Proposition B.1 (iii), evaluating the $c$-transform
$\ell_{c}(\theta,\lambda,\widehat{z})$ at any feasible $\lambda$ thus amounts
to solving a univariate convex maximization problem. Thanks to the envelope
theorem [26, Theorem 2.16], the solution of this maximization problem also
provides a subgradient of $\ell_{c}(\theta,\lambda,\widehat{z})$. Thus,
problem (85) is amenable to stochastic subgradient descent algorithms, where
all subgradients can be computed by solving univariate convex optimization
problems. By extension, the same conclusions apply to the distributionally
robust learning model (48) if we replace the inner maximization problem with
(85).

##  Appendix C Technical Background Results

######  Lemma C.1.

If $p\geq 1$ and $L:\mathbb{R}\to\mathbb{R}$ is an upper semi-continuous
function satisfying the growth condition $L(s)\leq C(1+|s|^{p})$ for some
$C\geq 0$, then the $p$-th envelope
$L_{p}(s,\lambda)=\sup_{s^{\prime}\in\mathbb{R}}\;L(s^{\prime})-\lambda|s-s^{\prime}|^{p}$
converges to $L(s)$ as $\lambda$ grows, that is,
$\lim_{\lambda\to+\infty}L_{p}(s,\lambda)=L(s)$ for all $s\in\mathbb{R}$.

###### Proof.

By the definition of $L_{p}$, for any $\lambda>0$ there exists
$s_{\lambda}\in\mathbb{R}$ with

$\displaystyle L_{p}(s,\lambda)\leq
L(s_{\lambda})-\lambda|s-s_{\lambda}|^{p}+\frac{1}{\lambda}.$

In the following we prove that $s_{\lambda}$ converges to $s$ as $\lambda$
tends to infinity. To this end, note first that

$\displaystyle L(s)$ $\displaystyle\leq L_{p}(s,\lambda)\leq
L(s_{\lambda})-\lambda|s-s_{\lambda}|^{p}+\frac{1}{\lambda}\leq
C(1+|s_{\lambda}|^{p})-\lambda|s-s_{\lambda}|^{p}+\frac{1}{\lambda}$
$\displaystyle\leq
C\left(1+(|s|+|s-s_{\lambda}|)^{p}\right)-\lambda|s-s_{\lambda}|^{p}+\frac{1}{\lambda}\leq
C(1+2^{p-1}|s|^{p})-(\lambda-C2^{p-1})|s-s_{\lambda}|^{p}+\frac{1}{\lambda},$

where the first and the second inequalities exploit the definitions of $L_{p}$
and $s_{\lambda}$, respectively, whereas the third and the fourth inequalities
follow from the growth condition on $L$ and the triangle inequality,
respectively. The last inequality, finally, holds because $p\geq 1$, which
implies via Jensen’s inequality that

$\textstyle(|s|+|s-s_{\lambda}|)^{p}=2^{p}\left(\frac{1}{2}|s|+\frac{1}{2}|s-s_{\lambda}|\right)^{p}\leq
2^{p-1}\left(|s|^{p}+|s-s_{\lambda}|^{p}\right).$

Rearranging terms thus yields

$\displaystyle|s-s_{\lambda}|^{p}\leq\left(C(1+2^{p-1}|s|^{p})-L(s)+\frac{1}{\lambda}\right)/(\lambda-C2^{p-1}),$

which ensures that $s_{\lambda}$ converges to $s$ as $\lambda$ grows.
Recalling the definition of $L_{p}(x,\lambda)$, we finally obtain

$\displaystyle
L(s)\leq\lim_{\lambda\to+\infty}L_{p}(s,\lambda)\leq\limsup_{\lambda\to+\infty}L(s_{\lambda})-\lambda|s-s_{\lambda}|^{p}+\frac{1}{\lambda}\leq\limsup_{\lambda\to+\infty}L(s_{\lambda})\leq
L(s),$

where the second and the third inequalities follow from the definition of
$s_{\lambda}$ and the upper semicontinuity of $L$, respectively. As both sides
of the above expression coincide with $L(s)$, we conclude that all
inequalities are in fact equalities. This proves that
$\lim_{\lambda\to+\infty}L_{p}(s,\lambda)=L(s)$ for all $s\in\mathbb{R}$. ∎