# A data-driven approach to beating SAA out-of-sample

Jun-ya Gotoh$\dagger$ ,  Michael Jong Kim$\ddagger$ and  Andrew E.B. Lim$*$
$\dagger$Department of Data Science for Business Innovation, Chuo University,
Tokyo, Japan. Email<EMAIL_ADDRESS>
$\ddagger$Sauder School of Business, University of British Columbia,
Vancouver, Canada. Email<EMAIL_ADDRESS>
$*$Department of Analytics and Operations, Department of Finance, and
Institute for Operations Research and Analytics, National University of
Singapore, Singapore. Email<EMAIL_ADDRESS>
###### Abstract.

While solutions of Distributionally Robust Optimization (DRO) problems can
sometimes have a higher out-of-sample expected reward than the Sample Average
Approximation (SAA), there is no guarantee. In this paper, we introduce the
class of Distributionally Optimistic Optimization (DOO) models, and show that
it is always possible to “beat” SAA out-of-sample if we consider not just
worst-case (DRO) models but also best-case (DOO) ones. We also show, however,
that this comes at a cost: Optimistic solutions are more sensitive to model
error than either worst-case or SAA optimizers, and hence are less robust.

Keywords: Distributionally Optimistic Optimization (DOO), Distributionally
Robust Optimization (DRO), Sample Average Approximation (SAA), data-driven
optimization, model uncertainty, worst-case sensitivity, out-of-sample
performance.

##  1\. Introduction

It is well known that solutions of optimization problems calibrated from data
can perform poorly out-of-sample. This occurs due to errors in both the
modeling assumptions and the estimation of model parameters and has motivated
various optimization models which account for misspecification in the in-
sample model. Distributionally Robust Optimization (DRO), where the decision
maker optimizes against worst-case perturbations from the nominal (in-sample)
distribution, is one such approach. Similar models have been introduced in a
number of communities [2, 5, 6, 12, 20].

The performance of DRO is often evaluated by comparing its out-of-sample
expected reward to that of the SAA optimizer. This is often done
experimentally, and recent papers characterize finite-sample and asymptotic
properties of DRO solutions and the associated expected reward [3, 7, 8, 9,
14].

It has also been observed that solutions of DRO and other worst-case models
can sometimes have a higher out-of-sample expected reward than the Sample
Average Approximation (SAA) optimizer [1, 4, 9, 13]. However, there is no
guarantee that this will occur, and it is of interest whether a decision that
beats SAA out-of-sample can be found when DRO is unable to. In this paper, we
introduce a class of Distributionally Optimistic Optimization (DOO) problems,
where nature works together with the decision maker to optimize the in-sample
reward, and show under relatively mild assumptions that it is always possible
to “beat” the SAA optimizer out-of-sample if we consider best-case (DOO) and
worst-case (DRO) decisions.

As tempting as this may sound, there is a catch. While the out-of-sample
expected reward might be larger, the expected reward under a best-case
optimizer is always more sensitive to worst-case perturbations from the
nominal model than the SAA optimizer, and hence is less robust. More
generally, worst and best-case optimizers make a tradeoff between (in-sample)
expected reward and sensitivity to model error. If we are concerned about
robustness, we potentially miss the benefits of sensitivity reduction if we
only focus on the mean reward, and could even make things worse if this leads
to choosing a best-case solution.

In contrast to worst-case problems, the literature on DOO is small, though
recent activity suggests it is attracting interest. One related paper is [19]
where a best-case view of uncertainty is proposed as a way to reduce
conservatism, and shown to be related to certain non-convex regularizers used
in machine learning. Also related is [18], which uses optimistic optimization
over probability distributions to construct a nonparametric approximation of
the likelihood function that can be used in Bayesian statistics. However, it
does not consider decision making, though Optimistic Maximum Likelihood
Estimation is the natural step in this direction. The paper [21] uses DOO to
solve the Trust Region Policy Optimization problem in the context of
Reinforcement Learning. Best case problems are also used in the empirical
likelihood approach to generating confidence intervals of the optimal expected
reward under the population distribution [8, 16, 17, 23]. These papers do not
consider the out-of-sample performance of solutions of best-case problems.
Finally, we also note that the National Science Foundation recently awarded a
grant [24] on “Favorable optimization under distributional distortions”.

A recent paper [15] shows that it is impossible, asymptotically, for a large
class of data-driven problems, including DRO and DOO and popular
regularization techniques, to beat the out-of-sample expected reward of SAA.
While this appears to directly contradict our results, there is actually no
inconsistency. The main difference is that [15] considers the large data
limit, whereas our results apply to moderate data sets. Taken together, it is
always possible to beat SAA using DRO/DOO with a finite data set (us), but
impossible in the limit [15]. We discuss [15] in more detail at the end of
this paper.

### Organization

We introduce the Distributionally Optimistic Optimization (DOO) and
Distributionally Robust Optimization (DRO) models in Section 2. For
concreteness, we adopt a penalty framework with smooth $\phi$-divergence as
the penalty function. However, the key concepts are general and carry over to
different formulations (e.g. constrained) and uncertainty sets. We show in
Section 3 that the family of worst- and best-case solutions is continuously
differentiable in a neighborhood of the SAA solution and characterize their
distributional properties, that it is generally possible to find a DRO or DOO
solution with a higher out-of-sample expected reward than SAA in Section 4,
but that a best-case solution is always less robust than SAA in Section 5. The
key ideas are illustrated using a data-driven inventory problem.

##  2\. Setup

Let $f:{\mathbb{R}}^{d}\times{\mathbb{R}}^{l}\rightarrow{\mathbb{R}}$, and $Y$
be an $\mathbb{R}^{l}$-valued random vector with population distribution
$\mathbb{P}$. Consider the problem

$\displaystyle\max_{x}{\mathbb{E}}_{\mathbb{P}}\big{[}f(x,\,Y)\big{]}.$ (2.1)

Let

$x^{\star}(0):=\arg\max_{x}\,\Big{\\{}\mathbb{E}_{\mathbb{P}}\left[f(x,\,Y)\right]\Big{\\}}$
(2.2)

denote the solution of (2.1). We assume the following.

######  Assumption 2.1.

The function $f(x,\,Y)$ and random vector $Y\sim{\mathbb{P}}$ are such that

  * •

$f(x,\,Y)$ is strictly concave and twice continuously differentiable in
$x\in\mathbb{R}^{d}$ for ${\mathbb{P}}$-almost surely every
$Y\in\mathbb{R}^{l}$;

  * •

for each fixed $x\in\mathbb{R}^{d}$, the mappings $y\mapsto
f(x,y),\nabla_{x}f(x,y),\nabla^{2}_{x}f(x,y)$, $y\in\mathbb{R}^{l}$, are
measurable and all moments of the random variables $f(x,Y)$,
$\nabla_{x}f(x,Y)$, $\nabla^{2}_{x}f(x,Y)$ exist;

  * •

there exists a solution $x^{\star}(0)$ of (2.1).

In many applications, we do not know the population distribution
${\mathbb{P}}$ but only have independent and identically distributed (iid)
samples $Y_{1},\cdots,\,Y_{n}$ drawn from $\mathbb{P}$. This naturally leads
to replacing (2.1) with a Sample Average Approximation (SAA):

$\displaystyle\max_{x}\;{\mathbb{E}}_{{\mathbb{P}}_{n}}\left[f(x,\,Y)\right]\equiv\sum_{i=1}^{n}p_{i}^{n}f(x,\,Y_{i}).$
(2.3)

Here ${\mathbb{P}}_{n}=[p_{1}^{n},\cdots,\,p_{n}^{n}]$ is the empirical
distribution; we assume without loss of generality that $p^{n}_{i}>0$ for all
$i$. We denote the solution of the in-sample problem (2.3) by

$\displaystyle
x_{n}(0):=\operatorname*{arg\,max}_{x}\sum_{i=1}^{n}p_{i}^{n}f(x,\,Y_{i}).$

It is well known that the SAA solution $x_{n}(0)$ may not perform well out-of-
sample. This has motivated worst-case versions of SAA, called Distributionally
Robust Optimization (DRO), where the decision is chosen to maximize the
expected reward under worst-case perturbations of the probability distribution
(${\mathbb{Q}}$) from the empirical distribution ${\mathbb{P}}_{n}$:

$\displaystyle\max_{x}\min_{\mathbb{Q}}\sum_{i=1}^{n}q_{i}f(x,\,Y_{i})+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}_{n}),\;\delta>0$
(2.4)

where

$\displaystyle\mathcal{H}_{\phi}(\mathbb{Q}\,|\,{\mathbb{P}}_{n}):=\sum\limits_{i=1}^{n}{p}^{n}_{i}\phi\left(\frac{q_{i}}{{p}^{n}_{i}}\right),$
$\displaystyle\sum\limits_{i=1}^{n}q_{i}=1,q_{i}\geq 0$ (2.5)

is the $\phi$-divergence of ${\mathbb{Q}}=[q_{1},\cdots,\,q_{n}]$ relative to
${\mathbb{P}}_{n}=[p_{1}^{n},\cdots,\,p_{n}^{n}]$. We assume throughout that
$\phi:{\mathbb{R}}\rightarrow{\mathbb{R}}\cup\\{+\infty\\}$ is a convex lower
semi-continuous function such that $\phi(z)\geq\phi(1)=0$ for $z\geq 0$ and
$\phi(z)=+\infty$ for $z<0$.

### Distributionally optimistic optmization (DOO)

We now consider an optimistic version of (2.3) where nature works together
with the decision maker to optimize the expected reward. The Distributionally
Optimistic Optimization (DOO) model is

$\displaystyle\max_{x}\max_{\mathbb{Q}}\sum_{i=1}^{n}q_{i}f(x,\,Y_{i})+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}_{n}),\;\delta<0.$
(2.6)

Here, nature selects $\mathbb{Q}$ to maximize the expected reward and incurs a
(negative) penalty for deviating from the nominal ${\mathbb{P}}_{n}$, where
$\delta$ controls the size of the deviations. The decision maker accepts that
${\mathbb{P}}_{n}$ may be misspecified, and makes a decision that maximizes
the expected reward if nature is cooperative. DOO may be of interest to
applications where the decision maker is looking for upside opportunities and
does not wish to be conservative in the face of model uncertainty. We also
note that one of the likelihood approximations in [18] has the form of the
inner problem in (2.6). They do not consider optimization, though an
optimistic version of Maximum Likelihood Estimation is natural step in this
direction and an example of (2.6). Though our results provide insights about
general properties of DOO and its solutions, applications of DOO are not the
focus of this paper.

It is convenient to introduce population versions of the worst-case and best-
case problems. If

$\displaystyle\mathcal{H}_{\phi}(\mathbb{Q}\,|\,{\mathbb{P}}):={\mathbb{E}}_{\mathbb{P}}\Big{[}\phi\Big{(}\frac{d{\mathbb{Q}}}{d{\mathbb{P}}}\Big{)}\Big{]}$
(2.7)

denotes $\phi$-divergence, where $\frac{d\mathbb{Q}}{d\mathbb{P}}$ is the
Radon-Nikodym derivative (likelihood ratio) of $\mathbb{Q}$ with respect to
$\mathbb{P}$, then the population version of the worst-case problem is

$\displaystyle\max_{x}\min_{\mathbb{Q}}{\mathbb{E}}_{\mathbb{Q}}[f(x,\,Y)]+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}),\;\delta>0$
(2.8)

and

$\displaystyle\max_{x}\max_{\mathbb{Q}}{\mathbb{E}}_{\mathbb{Q}}[f(x,\,Y)]+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}),\;\delta<0$
(2.9)

is the best-case problem.

We denote the solutions of (2.2), (2.8) and (2.9) by $x^{\star}(\delta)$ with
$\delta=0$, $\delta>0$ and $\delta<0$, respectively, and $x_{n}(\delta)$ for
the sample versions (2.3), (2.4) and (2.6). It will be shown in Section 3 that
$x^{\star}(\delta)$ and $x_{n}(\delta)$ are continuously differentiable in a
neighborhood of $\delta=0$.

### Dual characterization of worst/best-case objective

Let

$\displaystyle\phi^{*}(\zeta)=\min_{z}\Big{\\{}\zeta z-\phi(z)\Big{\\}}$

denote the convex conjugate of $\phi(z)$. We have the following dual
representation of the worst-case problems (2.4) and (2.8), which is well known
and can be established using convex duality. We state it without proof.

######  Proposition 2.2 (Dual characterization for DRO).

Suppose that $\phi:{\mathbb{R}}\rightarrow{\mathbb{R}}\cup\\{+\infty\\}$ is a
convex lower-semicontinuous function such that $\phi(z)\geq\phi(1)=0$ for
$z\geq 0$ and $\phi(z)=+\infty$ for $z<0$. If $\delta>0$, then

$\displaystyle\min_{\mathbb{Q}}\Big{\\{}{\mathbb{E}}_{\mathbb{Q}}[f(x,\,Y)]+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}})\Big{\\}}=\max_{c}\Big{\\{}-\frac{1}{\delta}{\mathbb{E}}_{\mathbb{P}}\Big{[}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y)+c\big{]}\Big{)}\Big{]}-c\Big{\\}}$
(2.10)

and

$\displaystyle\min_{\mathbb{Q}}\Big{\\{}\sum_{i=1}^{n}q_{i}f(x,\,Y_{i})+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}_{n})\Big{\\}}=\max_{c}\Big{\\{}-\frac{1}{\delta}\sum_{i=1}^{n}p_{i}^{n}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y_{i})+c\big{]}\Big{)}-c\Big{\\}}.$
(2.11)

Similarly, we can derive the dual representation for the optimistic problems
(2.6) and (2.9).

######  Proposition 2.3 (Dual characterization for DOO).

Suppose that $\phi:{\mathbb{R}}\rightarrow{\mathbb{R}}\cup\\{+\infty\\}$ is a
convex lower-semicontinuous function such that $\phi(z)\geq\phi(1)=0$ for
$z\geq 0$ and $\phi(z)=+\infty$ for $z<0$. If $\delta<0$, then

$\displaystyle\max_{\mathbb{Q}}\Big{\\{}{\mathbb{E}}_{\mathbb{Q}}[f(x,\,Y)]+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}})\Big{\\}}=\min_{c}\Big{\\{}-\frac{1}{\delta}{\mathbb{E}}_{\mathbb{P}}\Big{[}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y)+c\big{]}\Big{)}\Big{]}-c\Big{\\}}$
(2.12)

and

$\displaystyle\max_{\mathbb{Q}}\sum_{i=1}^{n}q_{i}f(x,\,Y_{i})+\frac{1}{\delta}{\mathcal{H}}_{\phi}({\mathbb{Q}}\,|\,{\mathbb{P}}_{n})=\min_{c}\Big{\\{}-\frac{1}{\delta}\sum_{i=1}^{n}p_{i}^{n}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y_{i})+c\big{]}\Big{)}-c\Big{\\}}.$
(2.13)

##  3\. Characterization of the solution

###  3.1. In-sample problems

It follows from Proposition 2.2 that the worst-case problems (2.4) and (2.8)
are equivalent to

$\displaystyle\max_{x}\max_{c}\Big{\\{}-\frac{1}{\delta}{\mathbb{E}}_{\mathbb{P}}\Big{[}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y)+c\big{]}\Big{)}\Big{]}-c\Big{\\}},\;\delta>0$
$\displaystyle\max_{x}\max_{c}\Big{\\{}-\frac{1}{\delta}\sum_{i=1}^{n}p_{i}^{n}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y_{i})+c\big{]}\Big{)}-c\Big{\\}},\;\delta>0$

while by Proposition 2.3, the best case problems (2.6) and (2.9) become

$\displaystyle\max_{x}\min_{c}\Big{\\{}-\frac{1}{\delta}{\mathbb{E}}_{\mathbb{P}}\Big{[}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y)+c\big{]}\Big{)}\Big{]}-c\Big{\\}},\;\delta<0$
$\displaystyle\max_{x}\min_{c}\Big{\\{}-\frac{1}{\delta}\sum_{i=1}^{n}p_{i}^{n}\phi^{*}\Big{(}-\delta\big{[}f(x,\,Y_{i})+c\big{]}\Big{)}-c\Big{\\}},\;\delta<0.$

We study properties of the solution of these problems using the first-order
conditions. The assumptions about the function $\phi(z)$ need to be
strengthened.

######  Assumption 3.1.

$\phi:{\mathbb{R}}\rightarrow{\mathbb{R}}\cup\\{+\infty\\}$ is a convex lower-
semicontinuous function such that $\phi(z)\geq\phi(1)=0$ for $z\geq 0$,
$\phi(z)=+\infty$ for $z<0$, and is twice continuously differentiable around
$z=1$ with $\phi^{\prime\prime}(1)>0$.

Let

$\displaystyle\psi(x,\,c,\,Y)\equiv\left[\begin{array}[]{c}\psi_{1}(x,\,c,\,Y)\\\
\psi_{2}(x,\,c,\,Y)\end{array}\right]:=\left[\begin{array}[]{c}\displaystyle[\phi^{*}]^{\prime}\big{(}-\delta\big{[}f(x,\,Y)+c\big{]}\big{)}\nabla_{x}f(x,\,Y)\\\\[5.0pt]
\displaystyle-\frac{\phi^{\prime\prime}(1)}{\delta}\Big{\\{}[\phi^{*}]^{\prime}\big{(}-\delta\left(f(x,\,Y)+c\right)\big{)}-1\Big{\\}}\end{array}\right].$
(3.5)

The first-order conditions for the sample problems are

$\displaystyle{\mathbb{E}}_{{\mathbb{P}}_{n}}\big{[}\psi(x,\,c,\,Y)\big{]}=\left[\begin{array}[]{cc}0\\\
0\end{array}\right]$ (3.8)

where $\delta>0$ for (2.11) and $\delta<0$ for (2.13), and

$\displaystyle{\mathbb{E}}_{{\mathbb{P}}}\big{[}\psi(x,\,c,\,Y)\big{]}=\left[\begin{array}[]{cc}0\\\
0\end{array}\right]$ (3.11)

for the population problems. To ease notation, we suppress the dependence on
$\delta$ in the function $\psi(x,\,c,\,Y)$, though it should be clear from the
context whether we are talking about the worst-case ($\delta>0$) or the best-
case ($\delta<0$) problem.

Let $(x_{n}(\delta),\,c_{n}(\delta))$ and
$(x^{\star}(\delta),\,c^{\star}(\delta))$ denote the solutions of the in-
sample (3.8) and population (3.11) problems, respectively. The following
result shows that the family of solutions parameterized by $\delta$ exists and
is continuously differentiable in a neighborhood of $\delta=0$. There is a
similar result in [9] though the focus there is limited to DRO problems
($\delta\geq 0$). Proposition 3.2 shows that the continuation to negative
values of $\delta$ are solutions of DOO problems. The proof is in the
Appendix.

######  Proposition 3.2.

Suppose that $f(x,\,Y)$ satisfies Assumption 2.1 and $\phi(z)$ satisfies
Assumption 3.1. Then there is an open neighborhood of $\delta=0$ where the
solutions $(x_{n}(\delta),\,c_{n}(\delta))$ and
$(x^{\star}(\delta),\,c^{\star}(\delta))$ of (3.8) and (3.11), respectively,
exist and are continuously differentiable. In particular,

$\displaystyle\left\\{\begin{array}[]{l}x_{n}(\delta)=x_{n}(0)+\pi_{n}\delta+o(\delta),\\\\[5.0pt]
c_{n}(\delta)=-{\mathbb{E}}_{{\mathbb{P}}_{n}}[f(x_{n}(0),\,Y)]+O(\delta),\end{array}\right.$
(3.14)

where111If $\phi(z)$ is three times continuously differentiable, it can be
shown that  $\displaystyle
c_{n}(\delta)=-{\mathbb{E}}_{{\mathbb{P}}_{n}}[f(x_{n}(0),\,Y)]-\frac{\delta}{2}\frac{\phi^{\prime\prime\prime}(1)}{\left[\phi^{\prime\prime}(1)\right]^{2}}\mathbb{V}_{{\mathbb{P}}_{n}}\big{[}f(x_{n}(0),\,Y)\big{]}+o(\delta).$
However, the first-order term is not needed in our analysis.

$\displaystyle\pi_{n}:=\frac{1}{\phi^{{}^{\prime\prime}}(1)}\,\Big{(}{\mathbb{E}_{{\mathbb{P}}_{n}}[\nabla^{2}_{x}f(x_{n}(0),\,Y)]}\Big{)}^{-1}\mathrm{Cov}_{{\mathbb{P}_{n}}}\Big{[}{\nabla_{x}f(x_{n}(0),\,Y)},\,f(x_{n}(0),\,Y)\Big{]},$
(3.15)

and

$\displaystyle\left\\{\begin{array}[]{l}x^{\star}(\delta)=x^{\star}(0)+\pi\delta+o(\delta),\\\\[5.0pt]
c^{\star}(\delta)=-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)]+O(\delta),\end{array}\right.$
(3.18)

where

$\displaystyle\pi:=\frac{1}{\phi^{{}^{\prime\prime}}(1)}\,\Big{(}{\mathbb{E}_{{\mathbb{P}}}[\nabla^{2}_{x}f(x^{\star}(0),\,Y)]}\Big{)}^{-1}\mathrm{Cov}_{{\mathbb{P}}}\Big{[}{\nabla_{x}f(x^{\star}(0),\,Y)},\,f(x^{\star}(0),\,Y)\Big{]}.$
(3.19)

Proposition 3.2 shows that worst- and best-case optimization adds a bias in
the direction $\pi_{n}$ to the SAA maximizer $x_{n}(0)$ (and similarly for
$x^{\star}(\delta)$).

Clearly, the in-sample expected reward under the robust optimizer is smaller
than that of the empirical optimizer, no matter what the sign of $\delta$.
When applied out-of-sample, however, this might not be the case because the
solutions are random variables under the population distribution $\mathbb{P}$.
To compare the out-of-sample reward of the best and worst-case solutions and
the SAA optimizer, we need to understand the impact of data variability on the
solution.

###  3.2. Out-of-sample properties of the solution

We make the following regularity assumption about the function
$\psi(x,\,c,\,Y)$.

######  Assumption 3.3.

The parameter $\delta$ is such that for every $\epsilon>0$

$\displaystyle\sup_{(x,\,c)}\Big{|}{\mathbb{E}}_{{\mathbb{P}}_{n}}[\psi(x,\,c,\,Y)]-{\mathbb{E}}_{{\mathbb{P}}}[\psi(x,\,c,\,\,Y)]\Big{|}\overset{P}{\longrightarrow}0$
$\displaystyle\inf_{(x,\,c):\|(x,\,c)-(x^{\star}(\delta),\,c^{\star}(\delta))\|\geq\epsilon}\Big{|}{\mathbb{E}}_{\mathbb{P}}[\psi(x,\,c,\,Y)]\Big{|}>0=\Big{|}{\mathbb{E}}_{\mathbb{P}}[\psi(x^{\star}(\delta),\,c^{\star}(\delta),\,Y)]\Big{|}.$

The second condition implies that the first order conditions (3.11) for the
population problem associated with $\delta$ has a unique solution. Under
Assumptions 2.1 and 3.1, this is satisfied for all $\delta$ in an open
neighborhood of $0$, which includes negative values, and for every $\delta\geq
0$ (i.e. for SAA and the worst-case problems). We have the following
consistency result ([22], Theorem 5.9).

######  Proposition 3.4.

Suppose that data $\\{Y_{1},\cdots,\,Y_{n}\\}$ is drawn iid from $\mathbb{P}$
and Assumption 3.3 holds. Then
$(x_{n}(\delta),\,c_{n}(\delta))\overset{P}{\longrightarrow}(x^{\star}(\delta),\,c^{\star}(\delta))$.

Let

$\displaystyle
J_{\psi}(x^{\star}(\delta),\,c^{\star}(\delta),Y)=\left[\begin{array}[]{ccc|c}\nabla_{x_{1}}\psi_{1}&\ldots&\nabla_{x_{m}}\psi_{1}&\nabla_{c}\psi_{1}\\\
\hline\cr\nabla_{x_{1}}\psi_{2}&\ldots&\nabla_{x_{m}}\psi_{2}&\nabla_{c}\psi_{2}\\\
\end{array}\right](x^{\star}(\delta),\,c^{\star}(\delta),Y),$

be the Jacobian of $\psi(x,c,Y)$ and

$\displaystyle A(\delta)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{\mathbb{P}}[J_{\psi}(x^{\star}(\delta),\,c^{\star}(\delta),Y)]\in{\mathbb{R}}^{(d+1)\times(d+1)},$
$\displaystyle B(\delta)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{\mathbb{P}}[\psi(x^{\star}(\delta),\,c^{\star}(\delta),Y)\,\psi(x^{\star}(\delta),\,c^{\star}(\delta),Y)^{\prime}]\in{\mathbb{R}}^{(d+1)\times(d+1)}.$

The following result characterizes the distribution of $x_{n}(\delta)$. The
proof is in the Appendix.

######  Proposition 3.5.

Suppose that data $\\{Y_{1},\cdots,\,Y_{n}\\}$ is drawn iid from $\mathbb{P}$,
$f(x,\,Y)$ satisfies Assumption 2.1, $\phi(z)$ satisfies Assumption 3.1, and
$\delta$ is such that Assumption 3.3 holds. Then there is a unique solution
$(x^{\star}(\delta),\,c^{\star}(\delta))$ of the first-order conditions
(3.11), the matrix $A(\delta)$ is invertible,
$(x_{n}(\delta),\,c_{n}(\delta))\overset{P}{\longrightarrow}(x^{\star}(\delta),\,c^{\star}(\delta))$,
and

$\displaystyle\sqrt{n}\left[\begin{array}[]{c}x_{n}(\delta)-x^{\star}(\delta)\\\
c_{n}(\delta)-c^{\star}(\delta)\end{array}\right]=W_{n}(\delta)+o_{P}(1)$

where

$\displaystyle
W_{n}(\delta)=-A(\delta)^{-1}\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\psi(x^{\star}(\delta),\,c^{\star}(\delta),\,Y_{i}).$

$W_{n}(\delta)$ has mean $0$ and covariance matrix
$V(\delta)=A(\delta)^{-1}B(\delta){A(\delta)^{-1}}^{\prime}$. Furthermore

$\displaystyle
V(\delta)=\left[\begin{array}[]{cc}\xi(\delta)&\kappa(\delta)\\\
\kappa(\delta)^{\prime}&\eta(\delta)\end{array}\right]=\left[\begin{array}[]{cc}\xi(0)&\kappa(0)\\\
\kappa(0)^{\prime}&\eta(0)\end{array}\right]+O(\delta),$

where

$\displaystyle\xi(0)$
$\displaystyle={\mathbb{V}}_{\mathbb{P}}\Big{[}\Big{(}{\mathbb{E}}\big{[}\nabla^{2}_{x}f(x^{\star}(0),\,Y)\big{]}\Big{)}^{-1}{\nabla_{x}f(x^{\star}(0),\,Y)}\Big{]},$
$\displaystyle\eta(0)$
$\displaystyle={\mathbb{V}}_{\mathbb{P}}[f(x^{\star}(0),\,Y)],$
$\displaystyle\kappa(0)$
$\displaystyle=\Big{(}{\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),\,Y)]\Big{)}^{-1}\mathrm{Cov}_{\mathbb{P}}\big{[}{\nabla_{x}f(x^{\star}(0),\,Y)},\,f(x^{\star}(0),\,Y)\big{]}=\phi^{{}^{\prime\prime}}(1)\pi.$

The random vector $W_{n}(\delta)$ is asymptotically normal with mean $0$ and
covariance matrix $V(\delta)$, though asymptotic normality is not required in
our analysis.

##  4\. Out-of-sample expected reward

Let $x_{n}(\delta)$ be a solution of the best- or worst-case model and

$\displaystyle\mu_{n}(\delta):={\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(\delta),\,Y_{n+1})\big{]}$

be the out-of-sample expected reward. Note that the expectation is over the
in-sample and out-of-sample data, so $Y_{n+1}$ has distribution $\mathbb{P}$
while the distribution of $x_{n}(\delta)$ is characterized in Proposition 3.5.
Under the distribution $\mathbb{P}$, $x_{n}(\delta)$ and $Y_{n+1}$ are
independent. We now explore the relationship between $\mu_{n}(\delta)$ and the
out-of-sample expected reward of the SAA optimizer, $\mu_{n}(0)$.

Since the SAA solution satisfies

$\displaystyle
x_{n}(0)=x^{\star}(0)+\frac{1}{\sqrt{n}}W_{n}(0)+o_{P}(\frac{1}{\sqrt{n}})$

(Proposition 3.5), a Taylor series expansion of the out-of-sample expected
reward gives

$\displaystyle\underbrace{{\mathbb{E}}_{\mathbb{P}}[f(x_{n}(0),Y)]}_{\tiny\mu_{n}(0)}={\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(0),Y)]+\frac{1}{2n}\underbrace{\mbox{tr}\big{\\{}\xi(0){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\big{\\}}}_{\tiny{\mathbb{E}}_{\mathbb{P}}[W_{n}(0)^{\prime}\nabla^{2}_{x}f(x^{\star}(0),Y)W_{n}(0)]<0}+o\Big{(}\frac{1}{n}\Big{)}.$
(4.1)

That is, the out-of-sample expected reward of the SAA optimizer $x_{n}(0)$ is
less than that of the population optimizer $x^{\star}(0)$. Indeed, since
$x_{n}(0)$ and $Y$ are independent and $f(x,Y)$ is concave in $x$, Jensen’s
inequality implies

$\displaystyle{\mathbb{E}}_{\mathbb{P}}[f(x_{n}(0),Y)]\leq{\mathbb{E}}_{\mathbb{P}}\Big{[}f\big{(}{\mathbb{E}}_{\mathbb{P}}[x_{n}(0)],Y\big{)}\Big{]}={\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(0),Y)]+o\Big{(}\frac{1}{n}\Big{)},$

so the second term in (4.1) is the size of this gap, which depends on the
variance of the solution $\frac{1}{n}\xi(0)$ and the curvature of the reward
${\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]$.

Similarly, the DRO/DOO solution

$\displaystyle
x_{n}(\delta)=x^{\star}(\delta)+\frac{1}{\sqrt{n}}W_{n}(\delta)+o_{P}\Big{(}\frac{1}{\sqrt{n}}\Big{)}$

and the out-of-sample expected reward

$\displaystyle\underbrace{{\mathbb{E}}_{\mathbb{P}}[f(x_{n}(\delta),Y)]}_{\tiny\mu_{n}(\delta)}={\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(\delta),Y)]+\underbrace{\frac{1}{2n}\mbox{tr}\Big{\\{}\xi(\delta){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(\delta),Y)]\Big{\\}}}_{\tiny\mbox{gap
in Jensen's inequality}}+o\Big{(}\frac{1}{n}\Big{)}$ (4.2)

has the same form as (4.1), being the sum of the expected reward under the
population DRO/DOO optimizer and an adjustment for Jensen’s inequality that
depends on the variance of the solution and the curvature of the expected
reward, differing only because the mean and variance of the solution have
changed.

To characterize the impact of DRO/DOO on the out-of-sample reward, we evaluate
the impact of $\delta$ on both terms in (4.2). Since
$x^{\star}(\delta)=x^{\star}(0)+\delta\pi+o(\delta)$ (3.18), the first term
can be written

$\displaystyle{\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(\delta),Y)]={\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(0),Y)]+\frac{\delta^{2}}{2}\pi^{\prime}{\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\pi+o(\delta^{2}).$
(4.3)

The impact of $\delta$ is $O(\delta^{2})$ so the derivative vanishes at
$\delta=0$

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\delta}{\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(\delta),Y)]\Big{|}_{\delta=0}=0.$

The second term in (4.2) can be written

$\displaystyle\mbox{tr}\Big{\\{}\xi(\delta){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(\delta),Y)]\Big{\\}}$
(4.4) $\displaystyle=$
$\displaystyle\mbox{tr}\Big{\\{}\xi(0){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\Big{\\}}+\delta\,\frac{\mathrm{d}}{\mathrm{d}\delta}\mbox{tr}\big{\\{}\xi(\delta){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(\delta),Y)]\big{\\}}\Big{|}_{\delta=0}+o(\delta).$

The derivative is generally non-zero so the Jensen adjustment changes linearly
around $\delta=0$.

In summary, the out-of-sample expected reward of SAA is equal to the expected
reward under the mean of the solution and an adjustment for Jensen’s
inequality that depends on the variance of the solution and the curvature of
the expected reward (4.1). DRO/DOO adds a bias to the SAA solution and changes
its variance, which changes both components of the expected reward (4.2).
Equation (4.3) shows that the impact of DRO/DOO on the population expected
reward term is negligible relative to the change in the Jensen adjustment
(4.4) resulting from the change in the variance of the solution and curvature
of the reward. This can be summarized as follows.

######  Proposition 4.1.

Suppose $\\{Y_{1},\cdots,\,Y_{n}\\}$ and $Y_{n+1}$ are drawn iid from
$\mathbb{P}$, $f(x,Y)$ satisfies Assumption 2.1, $\phi(z)$ satisfies
Assumption (3.1), and
$(x_{n}(\delta),\,c_{n}(\delta))\overset{P}{\longrightarrow}(x^{\star}(\delta),\,c^{\star}(\delta))$.
Then

$\displaystyle\mu_{n}(\delta)=\underbrace{{\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(0),\,Y_{n+1})\big{]}}_{\mu_{n}(0)}+\frac{\rho\delta}{2n}+o(\delta)+o(1/n)$
(4.5)

where

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\delta}\mbox{tr}\big{\\{}\xi(\delta){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(\delta),Y)]\big{\\}}\Big{|}_{\delta=0}$
$\displaystyle=$
$\displaystyle\mathrm{tr}\Big{(}\xi^{\prime}(0){\mathbb{E}_{{\mathbb{P}}}[\nabla^{2}_{x}f(x^{\star}(0),\,Y)]}\Big{)}+\pi^{\prime}\nabla_{x}\Big{[}\mathrm{tr}\Big{(}\xi(0)\,{\mathbb{E}}_{{\mathbb{P}}}\big{[}\nabla_{x}^{2}f(x^{\star}(0),\,Y_{n+1})\big{]}\Big{)}\Big{]}$

and $\pi$ is given by (3.19).

The following result is an immediate consequence of Proposition 4.1.

######  Theorem 4.2.

Suppose that the assumptions of Proposition 4.1 hold. If $\rho\neq 0$, then
$\delta$ can always be selected so that the expected reward under
$x_{n}(\delta)$ exceeds that of the SAA optimizer out-of-sample

$\displaystyle{\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(\delta),\,Y_{n+1})\big{]}>{\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(0),\,Y_{n+1})\big{]}.$

A worst-case optimizer (i.e. $\delta>0$) will beat SAA out-of-sample if
$\rho>0$, and best-case otherwise.

######  Remark 4.3.

If we include terms of order $\delta^{2}$ from (4.3)–(4.4) in (4.2), and
assume sufficient smoothness for the required derivatives to exist,

$\displaystyle\mu_{n}(\delta)={\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(0),\,Y_{n+1})\big{]}+\frac{1}{2n}\big{(}\delta\rho+\frac{1}{2}\delta^{2}\theta\big{)}+\frac{\delta^{2}}{2[\phi^{{}^{\prime\prime}}(1)]^{2}}\pi^{\prime}{\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\pi+o(\delta^{2})+o(1/n)$

where

$\displaystyle\theta=\frac{\mathrm{d}^{2}}{\mathrm{d}\delta^{2}}\mbox{tr}\big{\\{}\xi(\delta){\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(\delta),Y)]\big{\\}}\Big{|}_{\delta=0}.$

The optimal choice of $\delta$ is

$\displaystyle\delta_{n}=-\frac{1}{2n}\Big{(}\frac{[\phi^{{}^{\prime\prime}}(1)]^{2}\rho}{\pi^{\prime}{\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\pi}\Big{)}+o(1/n)$

which may be positive or negative, depending on the sign of $\rho$, and

$\displaystyle\mu_{n}(\delta_{n})$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(0),\,Y_{n+1})\big{]}-\frac{1}{4n^{2}}\underbrace{\Big{(}\frac{[\phi^{{}^{\prime\prime}}(1)]^{2}\rho^{2}}{\pi^{\prime}{\mathbb{E}}_{\mathbb{P}}[\nabla^{2}_{x}f(x^{\star}(0),Y)]\pi}\Big{)}}_{\tiny\mbox{negative}}+o(1/n^{2})$
$\displaystyle>$
$\displaystyle{\mathbb{E}}_{\mathbb{P}}\big{[}f(x_{n}(0),\,Y_{n+1})\big{]}$

for $n$ sufficiently large.

######  Example 4.4.

If $f(x,Y)$ is strictly concave quadratic in $x$, then $\nabla^{2}_{x}f(x,Y)$
is constant and negative definite and $\rho$ is positive if DRO ($\delta>0$)
reduces the variance of the SAA solution. If DRO increases the variance of the
solution (see [9] for an example where this happens), $\rho$ is negative and a
DOO solution will have a higher out-of-sample expected reward.

######  Example 4.5.

The paper [1] considers DRO of a convex quadratic function and provides
conditions for different population distributions and uncertainty sets where
the solution beats SAA out-of-sample. Optimistic optimization should beat SAA
in their examples when DRO does not.

######  Example 4.6.

Consider an inventory problem with reward

$\displaystyle f(x,Y)=r\min\\{x,Y\\}+q\max\\{x-Y,0\\}-s\max\\{Y-x,0\\}-cx$

where the selling price $r=10$, the purchase cost $c=9$, and the shortage and
scrap costs, $s$ and $q$, are zero. Under the population distribution, demand
$Y=\max\\{m+IX_{1}-(1-I)X_{2},0\\}$, where $X_{i}$ is exponential with mean
$\mu_{i}$ ($i=1,2$), $I$ is Bernoulli with $p=P[I=1]$, and $m$ is a constant;
$X_{1},X_{2}$ and $I$ are independent. In this experiment, $m=250$,
$\mu_{1}=10$, $\mu_{2}=60$ and $p=0.9$.

We generated $5,000$ datasets, each of size $n=30$, and solved the DRO/DOO
problems with a modified-$\chi^{2}$ penalty function
($\phi(z)=\frac{1}{2}(z-1)^{2}$) over a range of $\delta$ for each dataset. We
then computed the out-of-sample expected reward for the family of DRO/DOO
decisions $x_{n}(\delta)$, giving $5,000$ conditional expected-reward
functions. The out-of-sample expected reward
$\mu_{n}(\delta)={\mathbb{E}}_{\mathbb{P}}[f(x_{n}(\delta),Y_{n+1})]$ shown in
Figure 4.1 was estimated by averaging these $5,000$ functions.

If we restrict ourselves to worst-case solutions (DRO), the SAA solution
($\delta=0$) is optimal and the out-of-sample expected reward is $189$.
However, the out-of-sample expected reward is maximized with an optimistic
solution $x_{n}(\delta)$ with $\delta=-1.3\times 10^{-3}$ and has value $193$.
With different parameter values and/or population distribution, a worst-case
model $(\delta>0$) could be optimal.

Figure 4.1. The plot shows the out-of-sample expected reward
$\mu_{n}(\delta)={\mathbb{E}}_{\mathbb{P}}[f(x_{n}(\delta),Y_{n+1})]$ as a
function of $\delta$. The optimistic solution $x_{n}(\delta)$ with
$\delta=-1.3\times 10^{-3}$ maximizes the expected reward ($193$). The
expected reward associated with SAA ($\delta=0$) is $189$.

In summary, DRO models typically come with a free parameter – the size of the
uncertainty set or the robustness parameter $\delta$ – which many select by
optimizing an estimate of the out-of-sample expected reward via cross-
validation or the bootstrap. However, it is not always possible to beat SAA if
we restrict ourselves to worst-case models [1, 9]. If the ultimate goal is to
beat SAA out-of-sample, it is reasonable to consider worst- and best-case
models to ensure this is possible.

##  5\. So, what is the catch?

###  5.1. Best-case solutions are not robust

We have focused on the out-of-sample expected reward of solutions of best- and
worst-case problems. However, it has also been shown that DRO is intrinsically
a tradeoff between (in-sample) expected reward and worst-case sensitivity [9,
10, 11]. Worst-case sensitivity is a quantitative measure of robustness and it
is natural to evaluate the worst-case sensitivity of the best-case optimizer.

We recall the definition of worst-case sensitivity [10]. Suppose decision $x$
is fixed and ${\mathbb{E}}_{{\mathbb{P}}_{n}}[f(x,Y)]$ be the expected reward
under the nominal distribution ${\mathbb{P}}_{n}$. Worst-case sensitivity
${\mathcal{S}}_{{\mathbb{P}}_{n}}(f(x,\,Y))$ is the rate of decrease of the
in-sample expected reward under “worst-case deviations” from the nominal
distribution. When the difference between probability distributions is
measured by smooth $\phi$-divergence, it is natural to define the worst-case
distribution as the minimizer

$\displaystyle{\mathbb{Q}}(\varepsilon)$
$\displaystyle:=\left\\{\begin{array}[]{cl}\displaystyle\arg\min_{\mathbb{Q}}\Big{\\{}\sum_{i=1}^{n}q_{i}f(x,\,Y)+\frac{1}{\varepsilon}\sum_{i=1}^{n}{p}^{n}_{i}\phi\Big{(}\frac{q_{i}}{{p}^{n}_{i}}\Big{)}\Big{\\}},&\varepsilon>0,\\\\[10.0pt]
{\mathbb{P}}_{n},&\varepsilon=0.\end{array}\right.$

Here, the penalty $\nicefrac{{1}}{{\varepsilon}}>0$ on $\phi$-divergence
controls the size of the deviation of ${\mathbb{Q}}(\varepsilon)$ from
${\mathbb{P}}_{n}$, which is increasing in $\varepsilon$. Worst-case
sensitivity is

$\displaystyle{\mathcal{S}}_{{\mathbb{P}}_{n}}(f(x,\,Y))$ $\displaystyle:=$
$\displaystyle-\frac{\mathrm{d}}{\mathrm{d}\varepsilon}{\mathbb{E}}_{{\mathbb{Q}}(\varepsilon)}[f(x,\,Y)]\Big{|}_{\varepsilon=0}$
(5.1) $\displaystyle=$ $\displaystyle-\lim_{\varepsilon\downarrow
0}\frac{{\mathbb{E}}_{{\mathbb{Q}}(\varepsilon)}[f(x,\,Y)]-{\mathbb{E}}_{{\mathbb{P}}_{n}}[f(x,\,Y)]}{\varepsilon}$
$\displaystyle=$
$\displaystyle\frac{1}{\phi^{\prime\prime}(1)}{\mathbb{V}}_{{\mathbb{P}}_{n}}[f(x,\,Y)],$

which, in the case of smooth $\phi$-divergence, is equal to the in-sample
variance of the reward. There are other ways to define worst-case sensitivity:
we can use a different divergence measure, or we can control the “distance” of
$\mathbb{Q}$ from ${\mathbb{P}}_{n}$ through a constraint and look at the
limit when it vanishes [11]. However, they all capture a similar idea.

Worst-case sensitivity is an in-sample measure of robustness. Given a nominal
model ${\mathbb{P}}_{n}$ and a decision $x$, it quantifies the sensitivity of
the expected reward to errors in the nominal model and is one way to evaluate
whether a given decision is more or less robust than another. Worst-case
sensitivity depends on the choice of uncertainty set, though it is always a
generalized measure of deviation (spread) [11]. Intuitively, the expected
reward is sensitive to mis-specification when it has a large spread because
small changes in the probability of extreme rewards (positive or negative) can
have a big impact on the mean.

Instead of $x$, we can substitute the solution $x_{n}(\delta)$ of the
best/worst-case problem into (5.1). To see the impact of best/worst case
optimization on the “robustness” of the solution, we write the sensitivity of
$x_{n}(\delta)$ in terms of the sensitivity of the SAA solution $x_{n}(0)$.
Using the expansion (3.14), the in-sample variance of the reward under
$x_{n}(\delta)$ is

$\displaystyle{\mathbb{V}}_{{\mathbb{P}}_{n}}[f(x_{n}(\delta),\,Y)]={\mathbb{V}}_{{\mathbb{P}}_{n}}[f(x_{n}(0),\,Y)]+2\frac{\delta}{\phi^{{}^{\prime\prime}}(1)}\,\beta_{n}^{\prime}\Big{(}{\mathbb{E}}_{{\mathbb{P}}_{n}}\big{[}\nabla_{x}^{2}f(x_{n}(0),\,Y)\big{]}\Big{)}^{-1}\beta_{n}+O(\delta^{2})$

where

$\displaystyle\beta_{n}$ $\displaystyle=$
$\displaystyle\mathrm{Cov}_{\mathbb{P}_{n}}\Big{[}{\nabla_{x}f(x_{n}(0),\,Y)},\,f(x_{n}(0),\,Y)\Big{]}.$

It now follows from (5.1) that worst-case sensitivity

$\displaystyle{\mathcal{S}}_{{\mathbb{P}}_{n}}(f(x_{n}(\delta),\,Y))$ (5.2)
$\displaystyle=$
$\displaystyle\underbrace{{\mathcal{S}}_{{\mathbb{P}}_{n}}(f(x_{n}(0),\,Y))}_{\tiny\mbox{Sensitivity
of SAA
solution}}+2\frac{\delta}{[\phi^{{}^{\prime\prime}}(1)]^{2}}\,\beta_{n}^{\prime}\Big{(}{\mathbb{E}}_{{\mathbb{P}}_{n}}\big{[}\nabla_{x}^{2}f(x_{n}(0),\,Y)\big{]}\Big{)}^{-1}\beta_{n}+O(\delta^{2}).$

Strict concavity of $f(x,Y)$ in $x$ implies that

$\displaystyle\beta_{n}^{\prime}\Big{(}{\mathbb{E}}_{{\mathbb{P}}_{n}}\big{[}\nabla_{x}^{2}f(x_{n}(0),\,Y)\big{]}\Big{)}^{-1}\beta_{n}<0$

so solutions of the optimistic DOO problem ($\delta<0$) have a larger
sensitivity than SAA, while worst-case solutions ($\delta>0$) have a smaller
sensitivity and are therefore more robust.

###  5.2. The optimal value of $\delta$ may be difficult to estimate

Although there exists an optimal DOO or DRO decision that has a larger out-of-
sample expected reward than SAA, the parameter $\delta$ corresponding to this
decision needs to be estimated. It is natural to use bootstrap or cross-
validation, though the estimate will depend on the data set so there will be
estimation error. If the optimal value of $\delta$ is positive but we
erroneously select a negative value of $\delta$ (i.e. DOO), not only do we
lose a little out-of-sample expected reward but we increase worst-case
sensitivity and the solution will be less robust than SAA.

######  Example 5.1 (Inventory control (continued)).

For each of the $5,000$ sampled datasets (each with $n=30$ datapoints), we
compute worst-case sensitivity
${\mathcal{S}}_{{\mathbb{P}}_{n}}(f(x_{n}(\delta),\,Y))$ as a function of
$\delta$. Figure 1(a) is obtained by averaging these. As shown in (5.2)
optimistic solutions have a larger sensitivity than SAA and DRO solutions in
the neighborhood of $\delta=0$ and sensitivity is linear in $\delta$. For each
of the $5,000$ datasets, we can compute the in-sample mean-sensitivity
frontier corresponding to the DRO/DOO solutions over a range of $\delta$.
Figure 1(b) is obtained by averaging these frontiers.

Figure 1(c) shows that out-of-sample mean-variance frontier. SAA can be beaten
by an optimistic decision, but this comes at the cost of a large increase in
the out-of-sample sensitivity (variance).

Figure 1(d) shows the distribution of bootstrap estimates of the optimal
$\delta$ as a function of the number of data points. Here we simulated $500$
independent datasets of size $n=15$ and $n=30$, and used 50 boostrap samples
for each dataset to estimate of the out-of-sample expected reward which we
optimized over $\delta$. When $n=15$, $\delta=-1.6\times 10^{-3}$ is optimal;
when $n=30$, $\delta=-1.3\times 10^{-3}$. The bootstrap estimates are not very
accurate when $n=15$ (mean = $1.4\times 10^{-2}$, SD = $2.8\times 10^{-2}$),
with only $49\%$ of experiments giving an estimate with the correct sign, and
there is a long right tail. This is not very surprising given that a sample of
size $n=15$ is a small when the population demand has a standard deviation of
$28$. The chance of getting a data set that is not representative of the
population is high, leading to poor estimates of $\delta$ (e.g. the extreme
values in the right tail of the distribution). Accuracy improves with $n=30$
data points (mean = $-1.3^{-2}$, SD = $4.7\times 10^{-3}$), with estimates
having the correct sign $88\%$ of the time and a smaller skew.

(a) Worst-case sensitivity

(b) Average in-sample mean-sensitivity frontier

(c) Out-of-sample mean-sensitivity frontier.

(d) Density of bootstrap estimates of $\delta$.

Figure 5.1. (A) shows the average worst-case sensitivity as a function of
$\delta$. Consistent with (5.2), it changes linearly around $\delta=0$. (B)
shows the (average) in-sample mean-sensitivity frontier corresponding to a
range of $\delta$. The change in the in-sample expected reward around
$\delta=0$ (SAA) is small compared to changes in the worst-case sensitivity.
(C) shows the out-of-sample mean-sensitivity (variance) frontier that is
mapped out when $\delta$ is varied. Out-of-sample expected reward is maximized
when $\delta=-1.3\times 10^{-3}$, which is on the optimistic part of the
frontier. The expected reward is $193$ which exceeds that of the SAA optimizer
(189). (D) shows the distribution of bootstrap estimates of the optimal
$\delta$ when there are $n=15$ data points (optimal value $\delta=-1.6\times
10^{-3}$) and $n=30$ data points (optimal value $\delta=-1.3\times 10^{-3}$).
Estimation error is large when $n=15$ and there is a long right tail. Accuracy
improves significantly when there are $n=30$ data points.

###  5.3. Other remarks

The paper [15]222The paper [15] was posted on arXiv one day after the first
version of this paper. Both were written independently. studies data-driven
algorithms that admit solutions of the form

$\displaystyle\tilde{x}_{n}(\delta)=x^{\star}(0)+\delta\tilde{\pi}+\frac{1}{\sqrt{n}}\tilde{W}_{n}+o_{P}(\delta+1/\sqrt{n}),$
(5.3)

where $x^{\star}(0)$ is the population optimizer (2.2), and
$\tilde{x}_{n}(\delta)$ is the data-driven solution when there are $n$ data
points, and $\delta$ is the free parameter of the algorithm (e.g. a
regularization parameter, the size of an uncertainty set, robustness
parameter)333The model (5.3) from [15] assumes that $\delta$ does not affect
the variance of the solution (i.e. $\tilde{W}_{n}$), which is not the case for
DRO/DOO (Proposition 3.5). Indeed, Proposition 4.1 shows that DRO/DOO has a
higher out-of-sample expected reward than SAA precisely because the parameter
$\delta$ induces a change in the curvature of the expected reward and the
variance of the solution, which changes the size of the “Jensen gap” (4.2).
The assumption in (5.3) removes one of these pathways (probably the key one).
If the objective function is concave quadratic in $x$, the curvature of the
reward is constant and it would not be possible to beat SAA out-of-sample if
there was no change in the variance of the solution, as assumed in (5.3).
Since the analysis is asymptotic, it appears that the “impossibility” results
in [15] continue to hold even if the variance of the solution is linear in
$\delta$.

To evaluate performance (5.3), [15] defines the expected out-of-sample reward

$\displaystyle Z(x):={\mathbb{E}}_{\mathbb{P}}[f(x,Y)|x].$

and considers the difference (regret) between that of the population optimizer
and the data-driven decision444Observe that $Z(x)$ is a conditional
expectation which averages out the random variable $Y$, so
$Z(\tilde{x}_{n}(\delta))$ is random because $\tilde{x}_{n}(\delta)$ is
random. In contrast, we consider $f(\tilde{x}_{n}(\delta),Y)$ which is random
because of both $\tilde{x}_{n}(\delta)$ and $Y$. While this does not affect
the analysis of the expected reward, it makes a difference when evaluating the
impact of $\delta$ on the sensitivity.

$\displaystyle{\mathcal{G}}(\tilde{x}_{n}(\delta)):=Z(x^{\star}(0))-Z(\tilde{x}_{n}(\delta)).$

The weak limit ($n\rightarrow\infty$) of the scaled regret
$n{\mathcal{G}}(\tilde{x}_{n}(\delta_{n}))$ associated with the data-driven
solution $\tilde{x}_{n}(\delta_{n})$ is shown to be second-order
stochastically larger than the weak limit of the scaled regret
$n{\mathcal{G}}(\tilde{x}_{n}(0))$ of the SAA optimizer, and in this sense it
is impossible to beat SAA asymptotically when an algorithm has solutions of
the form (5.3).

While this appears to contradict Theorem 4.2, which says that it is always
possible to beat SAA using DRO/DOO, there is actually no inconsistency. The
main difference is because [15] considers the large data limit, whereas our
results apply to moderately sized data sets. We see from (4.5) that the
difference between the reward from the DRO/DOO solution and the SAA optimizer
is on the order of $\delta/n$, and the advantage over SAA is small and
vanishes at a rate faster than $1/n$ if $\delta\equiv\delta_{n}$ itself is
going to $0$. Indeed, if we include the terms of order $\delta^{2}$ in (4.5),
it was noted in Remark 4.3 that the optimal choice of $\delta$ is of order
$1/n$ and the improvement over SAA if of the order $1/n^{2}$. If the goal is
to beat the expected reward of SAA out-of-sample, the improvement from DRO/DOO
is at best modest when data sets are moderate and diminishes quickly in $n$.
There is no advantage in the limit, consistent with [15].

We have argued, however, that the advantage of DRO is more than the
possibility that it can sometimes, but not always, beat SAA out-of-sample by
just a little bit555 Some have argued that these improvements, though modest,
have made all the difference in the success of DRO in certain applications,
and perhaps, in some paper publication decisions as well. We do not disagree.:
It also reduces the sensitivity of the expected reward to misspecification in
the nominal. More generally, it captures the tradeoff between maximizing
expected reward and controlling sensitivity which is relevant in many
applications of data-driven decision making.

##  6\. Conclusion

Solutions of DRO problems can sometimes have a larger out-of-sample expected
reward than SAA. Indeed, much of the literature seems to suggest that this is
the aspiration of DRO; uncertainty sets are often calibrated by optimizing an
estimate of the out-of-sample expected reward, and recent papers focus on
theoretically characterizing the out-of-sample expected reward of DRO
solutions; applications of DRO are hailed a success when the out-of-sample
mean exceeds that of SAA. However, beating SAA may not be possible if we only
consider worst-case models.

We have shown that it is always possible to beat SAA out-of-sample if we
consider both optimistic (DOO) and pessimistic (DRO) perturbations of the
nominal model. If the only concern is beating the out-of-sample expected
reward of the SAA optimizer, a decision maker should consider best-case and
worst-case models.

As tempting as this may sound, there is a catch. While the out-of-sample
expected reward might be larger, the worst-case sensitivity of a best-case
(DOO) optimizer is larger than that of SAA so it will also be less robust.
Indeed, the improvement in the expected reward from using the optimal DOO
optimizer is small (of order $1/n^{2}$) relative to the robustness cost.
Finally, the optimal value of the parameter $\delta$ also needs to be
estimated, and bootstrap or cross-validation estimates may be unreliable if
the training data set is small.

## References

  * [1] Anderson, E.J., Philpott, A. 2020. Improving sample average approximation using distributional robustness. Working paper: http://www.epoc.org.nz/papers/AndersonPhilpottDRO2020.pdf
  * [2] Ben-Tal, A., A. Nemirovski. 1999. Robust solutions to uncertain programs. Oper. Res. Lett. 25 1–13.
  * [3] Bertsimas, D., Gupta, V., Kallus, N. 2014. Robust SAA. arXiv:1408.4445 (https://arxiv.org/abs/1408.4445).
  * [4] Bertsimas, D., Litvinov, E., Sun, A.X., Zhao, J., Zheng, T. 2013. Adaptive robust optimization for the security constrained unit commitment problem. IEEE Transactions on Power Systems, 28(1), 52–63.
  * [5] Doyle, J.C., Glover, K., Khargonekar, P.P., Francis, B.A. 1989. State-space solutions to standard ${\mathcal{H}}_{2}$ and ${\mathcal{H}}_{\infty}$ control problems. IEEE Transactions on Automatic Control, 34(8), 831–847.
  * [6] El Ghaoui, L., Lebret, H. 1997. Robust solutions to least-square problems to uncertain data matrices. SIAM Journal on Matrix Analysis and Applications, 18, 1035–1064.
  * [7] Duchi, J.C., Namkoong, H. 2016. Variance-based regularization with convex objectives. arXiv:1610.02581v2 (https://arxiv.org/abs/1610.02581).
  * [8] Duchi, J.C., Glynn, P.W., Namkoong, H. 2016. Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach. arXiv:1610.03425 (https://arxiv.org/abs/1610.03425).
  * [9] Gotoh, J., Kim, M.J., Lim, A.E.B. 2020. Calibration of robust empirical optimization models. Forthcoming, Operations Research, https://doi.org/10.1287/opre.2020.2041.
  * [10] Gotoh, J., Kim, M.J., Lim, A.E.B. 2018. Robust empirical optimization is almost the same as mean-variance optimization. Operations Research Letters, 46 (4), 448–452, https://doi.org/10.1016/j.orl.2018.05.005.
  * [11] Gotoh, J., Kim, M.J., Lim, A.E.B. 2020. Worst-case sensitivity. arXiv:2010.10794 (https://arxiv.org/abs/2010.10794).
  * [12] Hansen, L.P., Sargent, T.J. 2008. Robustness. Princeton University Press, Princeton, New Jersey.
  * [13] Kim, M.J., Lim, A.E.B. 2014. Robust multi-armed bandit problems. Management Science, 62(1), 264–285.
  * [14] Kuhn, D., Esfahani, P.M., Nguyen,V.A., Shafieezadeh-Abadeh, S. 2019. Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning. INFORMS TutORials in Operations Research, 130-166, https://doi.org/10.1287/educ.2019.0198.
  * [15] Lam, H. 2021. On the Impossibility of Statistically Improving Empirical Optimization: A Second-Order Stochastic Dominance Perspective. arXiv:2105.13419 (https://arxiv.org/pdf/2105.13419.pdf).
  * [16] Lam, H. 2019. Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization. Operations Research, 67(4), pp 1090 – 1105.
  * [17] Lam H., Zhou E. 2017. The empirical likelihood approach to quantifying uncertainty in sample average approximation. Operations Research Letters 45(4), pp 301 – 307.
  * [18] Nguyen, V.A., Shafieezadeh-Abadeh, S., Yue, M.C., Kuhn, D., Wiesemann, W. 2019. Optimistic Distributionally Robust Optimization for Nonparametric Likelihood Approximation. arXiv:1910.10583 (https://arxiv.org/abs/1910.10583).
  * [19] Norton, M., Takeda, A., Mafusalov, A. 2017. Optimistic robust optimization with applications to machine learning. arXiv:1711.07511 (https://arxiv.org/abs/1711.07511).
  * [20] Peterson, I.R., James, M.R., Dupuis, P. 2000. Minimax optimal control of stochastic uncertain systems with relative entropy constraints. IEEE Transactions on Automatic Control, 45, 398–412.
  * [21] Song, J., Zhao, C. 2020. Optimistic Distributionally Robust Policy Optimization. arXiv:2006.07815v1, https://arxiv.org/pdf/2006.07815.pdf.
  * [22] van der Vaart, A.W. 2000. Asymptotic Statistics. Cambridge University Press.
  * [23] Wang, Z., Glynn, P.W., Ye. Y. (2016). Likelihood robust optimization for data-driven problems. Computational Management Science, 13(2), pp. 241 – 261.
  * [24] Xie, W. 2021. CAREER: Favorable Optimization under Distributional Distortions: Frameworks, Algorithms, and Applications (Award Number 2046426). Division of Civil, Mechanical & Manufacturing Innovation, National Science Foundation.

##  Appendix A Proof of Proposition 3.2

We use the Implicit Function Theorem to show existence of the solution
$(x^{\star}(\delta),\,c^{\star}(\delta))$ of (3.11) and to characterize its
smoothness. (Existence and smoothness of $(x_{n}(\delta),\,c_{n}(\delta))$ can
be shown in a similar way). With a mild abuse of notation, let

$\displaystyle
g(\delta,\,x,\,c)\equiv\left[\begin{array}[]{c}g_{1}(\delta,\,x,\,c)\\\
g_{2}(\delta,\,x,\,c)\end{array}\right]:={\mathbb{E}}_{\mathbb{P}}[\psi(x,\,c,\,Y)].$

The first-order conditions for the population problems (3.11) are

$\displaystyle g(\delta,\,x,\,c)=\left[\begin{array}[]{cc}0\\\
0\end{array}\right].$ (A.4)

Under the assumptions of $\phi(z)$ (see Theorem 3.2 in [10]) the convex
conjugate $\phi^{*}(\zeta)$ is twice continuously differentiable in the
neighborhood of $\zeta=0$ and satisfies

$\displaystyle\phi^{*}(\zeta)=\zeta+\frac{\alpha_{2}}{2!}\zeta^{2}+o(\zeta^{2}),$
(A.5)

where $\alpha_{2}=\nicefrac{{1}}{{\phi^{\prime\prime}(1)}}$. It follows that

$[\phi^{*}]^{\prime}(\zeta)=1+\alpha_{2}\zeta+o(\zeta)$

is continuously differentiable in a neighborhood of $\zeta=0$. This implies
that for every fixed $(x,\,c)$, $g(\delta,\,x,\,c)$ is continuously
differentiable in $\delta$ in some open neighborhood of $\delta=0$, that

$\displaystyle
g(\delta,\,x,\,c)=\left[\begin{array}[]{c}{\mathbb{E}}_{{\mathbb{P}}}\Big{[}\nabla_{x}f(x,Y)\Big{]}-\frac{\delta}{\phi^{\prime\prime}(1)}{\mathbb{E}}_{\mathbb{P}}\Big{[}\Big{(}f(x,Y)+c\Big{)}\nabla_{x}f(x,Y)\Big{]}+o(\delta)\\\\[10.0pt]
\mathbb{E}_{{\mathbb{P}}}\Big{[}f(x,Y)+c\Big{]}+O(\delta)\end{array}\right],$

and that

$\displaystyle
g\big{(}0,\,x^{\star}(0),\,-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)]\big{)}=0,$
(A.7)

where $x^{\star}(0)$ is the solution of the empirical problem. Since
$f(x,\,Y)$ is twice continuously differentiable in $x$, $g(\delta,\,x,\,c)$ is
continuously differentiable in a neighborhood of
$\big{(}0,\,x^{\star}(0),\,-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)]\big{)}$,
and

$\displaystyle
J_{g,\,(x,\,c)}(\delta,\,x,\,c)\Big{|}_{(0,\,x^{\star}(0),\,-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)])}$
$\displaystyle\equiv$
$\displaystyle\left.\left[\begin{array}[]{cc}\nabla_{x}g_{1}(\delta,\,x,\,c)&\nabla_{c}g_{1}(\delta,\,x,\,c)\\\
\nabla_{x}g_{2}(\delta,\,x,\,c)&\nabla_{c}g_{2}(\delta,\,x,\,c)\end{array}\right]\right|_{(0,\,x^{\star}(0),\,-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)])}$
$\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}{\mathbb{E}}_{\mathbb{P}}[\nabla_{x}^{2}f(x^{\star}(0),\,Y)]&0\\\
0&1\end{array}\right]$

is invertible. It follows from the Implicit Function Theorem that
$(x^{\star}(\delta),\,c^{\star}(\delta))$ exists and is continuously
differentiable in an open neighborhood of
$\big{(}0,\,x^{\star}(0),\,-{\mathbb{E}}_{{\mathbb{P}}}[f(x^{\star}(0),\,Y)]\big{)}$
so we can write

$\displaystyle x^{\star}(\delta)$ $\displaystyle=$ $\displaystyle
x^{\star}(0)+\delta\pi+o(\delta)$ $\displaystyle c^{\star}(\delta)$
$\displaystyle=$
$\displaystyle-{\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(0),Y)+\delta\kappa+o(\delta)$

where $\pi\in{\mathbb{R}}^{d}$ and $\kappa$ is a constant. Substituting into
the first equation in (A.7), a Taylor series expansion around $\delta=0$ gives

$\displaystyle{\mathbb{E}}_{\mathbb{P}}\big{[}\nabla_{x}f(x^{\star}(0),Y)\big{]}+\delta\pi^{\prime}{\mathbb{E}}_{\mathbb{P}}\big{[}\nabla^{2}_{x}f(x^{\star}(0),Y)\big{]}$
$\displaystyle-\frac{\delta}{\phi^{{}^{\prime\prime}}(1)}{\mathbb{E}}_{\mathbb{P}}\Big{[}\Big{(}f(x^{\star}(0),Y)-{\mathbb{E}}_{\mathbb{P}}[f(x^{\star}(0),Y)\Big{)}\nabla_{x}f(x^{\star}(0),Y)\Big{]}+o(\delta)=0.$

Optimality of $x^{\star}(0)$ for the population problem implies
${\mathbb{E}}_{\mathbb{P}}\big{[}\nabla_{x}f(x^{\star}(0),Y)\big{]}=0$ while
the coefficient of the $\delta$ term is zero if

$\displaystyle\pi=\frac{1}{\phi^{{}^{\prime\prime}}(1)}\Big{(}{\mathbb{E}}_{\mathbb{P}}\big{[}\nabla^{2}_{x}f(x^{\star}(0),Y)\big{]}\Big{)}^{-1}\mbox{Cov}_{\mathbb{P}}\Big{(}f(x^{\star}(0),Y),\nabla_{x}f(x^{\star}(0),Y)\Big{)}.$

Smoothness of $(x_{n}(\delta),\,c_{n}(\delta))$ and the expression
(3.14)-(3.15) can be established in a similar manner.

##  Appendix B Proof: Proposition 3.5

By Proposition 3.4,
$(x_{n}(\delta),\,c_{n}(\delta))\overset{P}{\longrightarrow}(x^{\star}(\delta),\,c^{\star}(\delta))$.

The second condition in Assumption 3.3 implies that the first order conditions
(3.11) for the population problem associated with $\delta$ has a unique
solution. Under Assumptions 2.1 and 3.1, the matrix $A(\delta)$ is invertible
so $W_{n}(\delta)$ is well defined.

The distributional properties of $(x_{n}(\delta),c_{n}(\delta))$ follows from
Theorem 5.21 in [22].

A Taylor series expansion of $V(\delta)$ around $\delta=0$ gives the
expressions for $\xi(0)$, $\kappa(0)$ and $\eta(0)$.