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

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

{\bf 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.

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 BN2,DGKF,EL,Hansen3,PJD.

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 bgk-SAA,DN,DGN16,GKL-cal,KENS.

It has 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 AP,BLSZZ2013,GKL-cal,KL. However, there is no guarantee, 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 {\it 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. 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 an uptick in interest that is generally centered around the concern that worst-case optimization is “too pessimistic." One disadvantage of optimistic optimization, however, is that convexity can be lost, making it potentially more difficult to solve (computationally) than its worst-case cousin. Non-convexity is considered in NTM where optimistic optimization problems are shown to be related to non-convex regularizers used in machine learning. A majorization minimization algorithm is employed in NTM to efficiently obtain a critical point of their nonconvex optimization problem by making use of its “difference of convex" structure. Also related is NSYKW, which uses optimistic optimization over probability distributions to construct a nonparametric approximation of the likelihood function that can be used in Bayesian statistics. The paper SZ uses DOO to solve the Trust Region Policy Optimization problem in the context of Reinforcement Learning, while optimistic optimization is also proposed in CR for online contextual decision making. Finally, a recent paper CR considers best-case optimization in stochastic optimization with model uncertainty using the “Rockafellian" framework for perturbation analysis. Best-case problems are also used in the empirical likelihood approach to generating confidence intervals of the optimal expected reward under the population distribution DGN16,Lam1,LamZhou,WGY. We also note that the National Science Foundation recently awarded a grant Xie on “Favorable optimization under distributional distortions". These papers do not consider the out-of-sample performance of solutions of best-case problems, nor the impact on the sensitivity of the out-of-sample expected reward to errors in the in-sample model.

A recent paper Lam2 shows that it is impossible, {\it 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 Lam2 considers the large data limit, whereas our results apply to data sets of moderate size. Taken together, it is always possible to beat SAA using DRO/DOO with a finite data set (us), but impossible in the limit Lam2. We discuss Lam2 in more detail at the end of this paper.

Organization

We introduce the {\it Distributionally Optimistic Optimization} (DOO) and {\it Distributionally Robust Optimization} (DRO) models in Section (ref). For concreteness, we adopt a penalty framework with smooth $\phi$-divergence as the penalty function. We show in Section (ref) 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 (ref), but that a best-case solution is always less robust than SAA in Section (ref). The key ideas are illustrated using a data-driven inventory problem.

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

Let

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

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 (ref) with a Sample Average Approximation (SAA):

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 (ref) by

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$:

where

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 (ref) where nature {\it works together} with the decision maker to optimize the expected reward. The Distributionally Optimistic Optimization (DOO) model is

Here, nature selects $\mathbb Q$ to maximize the expected reward and incurs a (negative) penalty for deviating from the nominal ${\mathbb P}_n$; the parameter $\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 NSYKW has the form of the inner problem in (ref). They do not consider optimization, though an optimistic version of Maximum Likelihood Estimation is natural step in this direction and an example of (ref). 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

denotes $\phi$-divergence, where $\frac{\mathrm{d}\mathbb Q}{\mathrm{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

and

is the best-case problem.

We denote the solutions of (ref), (ref) and (ref) by $x^\star(\delta)$ with $\delta=0$, $\delta>0$ and $\delta<0$, respectively, and $x_n(\delta)$ for the sample versions (ref), (ref) and (ref). It will be shown in Section (ref) that $x^\star(\delta)$ and $x_n(\delta)$ are continuously differentiable in a neighborhood of $\delta=0$. We consider the case where the decision variable $x$ is unconstrained as this allows us to directly connect changes to the SAA solution from DRO/DOO to out-of-sample performance. We defer analysis of the constrained case to future work.

Dual characterization of worst/best-case objective

Let

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

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

Characterization of the solution

In-sample problems

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

while by Proposition (ref), the best case problems (ref) and (ref) become

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.

The first order conditions for the sample and population problems in (ref) and (ref) can be written in the form

and

respectively, where $\delta>0$ for DRO and $\delta<0$ for DOO, and

(see Appendix (ref) for a derivation). Since

(see Theorem 3.2 in GKL), it follows that

and

To ease notation, we suppress the dependence on $\delta$ in the function $\psi(x,\,c,\,Y)$; 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 (ref) and population (ref) 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 GKL-cal though the focus there is limited to DRO problems ($\delta\geq 0$). Proposition (ref) shows that the continuation to negative values of $\delta$ are solutions of DOO problems. The proof is in the Appendix.

Proposition (ref) 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 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.

Statistical properties of the SAA solution

The following regularity assumptions on $f(x, Y)$ will be needed to characterize the statistical properties of $x_n(0)$.

We now characterize the statistical properties of the SAA solution. Let

and random vectors

where

By condition (1) of Assumption (ref), $\nabla^2_x\big(\frac{\partial f}{\partial x_i}(x^\star(0),\, Y)\big)$ is guaranteed to exist.

The following result gives the statistical properties of the solution of the SAA problem.

Equation (ref) shows that the SAA solution has a bias $\frac{1}{n}\overline{V}(0)$ relative to the solution $x^\star(0)$ of the population problem.

Statistical properties of the DRO/DOO solution

The following assumptions for $\psi(x, c, Y)$ are a direct parallel of Assumption (ref) for $f(x, Y)$.

Condition (1) guarantees that the Hessian $\nabla_{(x, c)}^2 \psi^{(i)}(x, c, Y)$ exists. The third condition implies that $\delta$ is such that the first order conditions (ref) for the population problem has a unique solution. Under Assumptions (ref) and (ref), this is satisfied for every $\delta\geq 0$ (i.e. for SAA and the worst-case problems), and for all $\delta$ in an open neighborhood of $0$, which includes negative values.

The following result characterizes the statistical properties of the DRO/DOO solution $x_n(\delta)$.

As in the case of the variance of $W_n(0)$ and the mean of $V_n(0)$ for SAA, $\xi(\delta)$ and $\overline{V}(\delta)$ do not depend on $n$. There is a bias of $\frac{1}{n}\overline{V}(\delta)$ relative to the population DRO/DOO optimizer $x^\star(\delta)$ and the variance $\frac{1}{n}\xi(\delta)$ is different from that of the SAA solution.

Out-of-sample expected reward

Let $x_n(\delta)$ be a solution of the best- or worst-case model, ${\mathbb E}_{\mathbb P}\big[f(x_n(\delta),\,Y_{n+1})\,|\,x_n(\delta)\big]$ the out-of-sample expected reward given $x_n(\delta)$, and

be the expected out-of-sample reward after averaging over datasets $\{Y_1,\cdots,\,Y_n\}$ of size $n$ and outcome $Y_{n+1}$. Under the assumptions of our model, $Y_{n+1}$ has distribution $\mathbb P$, the distribution of $x_n(\delta)$ is characterized in Proposition (ref), and $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)$.

We denote the expected out-of-sample reward given $x$ by the function $g: {\mathbb R}^d \rightarrow {\mathbb R}$ defined by

Observe that $\mu_n(\delta) = {\mathbb E}_{\mathbb P}[g(x_n(\delta))]$. Concavity of $f(x, Y)$ in $x$ also implies that $g(x)$ is concave.

Sample Average Approximation

Independence of $x_n(0)$ and $Y$, the concavity of $f(x, Y)$ and hence $g(x)$ in $x$, and Jensen's inequality imply that the out-of-sample expected reward under the SAA optimizer $x_n(0)$ is less than that of its mean ${\mathbb E}_{\mathbb P}[x_n(0)]$

This inequality is strict if $g(x) = {\mathbb E}_{\mathbb P}[f(x, Y)]$ is strictly concave and $x_n(0)$ is random.

Equation (ref) suggests that we write the out-of-sample expected reward as a sum of the reward under the mean of the decision ${\mathbb E}_{\mathbb P}[x_n(0)]$ and a loss that we call the Jensen gap:

The Jensen gap is negative when $g(x)$ is concave (and not linear) on the support of $x_n(0)$, while the optimality of $x^\star(0)$ for the population problem implies that ${\mathbb E}_{\mathbb P}[g(x_n(0))]$ is less than $g(x^\star(0))$ if the solution is biased (${\mathbb E}_{\mathbb P}[x_n(0)] \neq x^\star(0)$).

Additional regularity (Assumptions (ref) and (ref)) allows us to characterize the mean and variance of the SAA solution and to study each component in the decomposition (ref) separately. Specifically, we know from Proposition (ref) that

We make the assumption that the second-order error terms of the expectation and variance of $x_n(0)$ are $o(n^{-1})$. Sufficient conditions for this additional level of regularity are provided in Appendix (ref).

Under Assumption (ref), a Taylor series expansion of the first component of (ref) around the population optimizer $x^\star(0)$ gives:

which shows that the expected out-of-sample loss due to the finite-sample bias $\frac{1}{n} \overline{V}(0)$ is small, being on the order of $n^{-2}$. In the case of the Jensen gap, a Taylor series expansion around ${\mathbb E}_{\mathbb P}[x_n(0)]$ gives

where the second and third equalities follow from (ref) and (ref). The Jensen gap is negative because $g(x)$ is concave and becomes more negative when the variance $\frac{1}{n}\xi(0)$ of $x_n(0)$ increases or the curvature $\nabla^2_x g(x^\star(0))$ becomes more negative.

Adding (ref) and (ref) we obtain an expression for the out-of-sample expected reward in terms of the population optimizer:

This expression shows that the loss in expected reward is of order $n^{-1}$ and comes from the uncertainty in the solution through the Jensen gap. There is also a loss due to the finite-sample bias in the SAA solution, but this is an order of magnitude smaller.

Distributionally Robust/Optimistic Optimization

To compare the out-of-sample expected reward of the DRO solution with that of SAA, we write ${\mathbb E}_{\mathbb P}[g(x_n(\delta))]$ in terms of the SAA reward ${\mathbb E}_{\mathbb P}[g(x_n(0))]$ and additional terms that show how changes in the mean and variance of the solution affect the expected reward:

The term (A) shows how a change in the expected value of the solution changes the reward, while (B) is the associated change in the Jensen gap.

DRO and DOO add a bias and change the variance of the SAA optimizer. Specifically, it follows from Proposition (ref) and equations (ref) and (ref) (under Assumptions (ref), (ref) that (ref) holds. As in the case of the SAA solution, we make the additional assumption that the second-order error terms of the mean and variance of $x_n(\delta)$ is $o(n^{-1})$. A sufficient condition is given in Appendix (ref).

Under this assumption and for $n$ sufficiently large, there is an open neighborhood of $\delta=0$ such that

Here, $\overline{V}_\delta(0) = \frac{\mathrm{d}}{\mathrm{d}\delta}\overline{V}(0)$ and $\xi_\delta(0) = \frac{\mathrm{d}}{\mathrm{d}\delta}\xi(0)$ denote derivatives of $\xi(\delta)$ and $\overline{V}(\delta)$ at $\delta=0$, which exist because $\xi(\delta)$ and $\overline{V}(\delta)$ are continuously differentiable at $\delta=0$ (Proposition (ref)).

To the first order, the change in the bias relative to the SAA solution is $\delta\big(\pi + \frac{1}{n}\overline{V}_\delta(0)\big)$ and $\frac{\delta}{n} \xi_\delta(0)$ is the change in the variance. The expression for ${\mathbb E}_{\mathbb P}[x_n(\delta)]$ follows from the previous equation together with (ref) and (ref) and shows that the difference between the mean of $x_n(\delta)$ and $x_n(0)$ comes from two sources, the change in the population solution from $x^\star(0)$ to $x^\star(\delta)$ due to robustness which contributes the $\pi$, and the change in the finite-sample bias which gives $\frac{1}{n}\overline{V}_\delta(0)$. The variance of the solution also changes by $\frac{1}{n}\xi_\delta(0)$. An explicit relationship between terms (A) and (B) in (ref) and the robustness parameter can be obtained by substituting (ref) into each term in (ref).

For the first term (A), it is shown in Appendix (ref) that

In the case of the Jensen gap (B):

where

This expression shows that the change in the Jensen gap comes from the change in the curvature of the objective function due to the DRO/DOO bias (first term) and the change in the variance of the solution (second term).

The out-of-sample expected reward under a DRO/DOO solution can be written in terms of the expected reward under the SAA optimizer by adding (ref) and (ref).

It is worth reiterating the origins of each term in $\rho$. The first is the change in the expected reward (ref) that results from the change to the mean of the SAA solution, while the second is the change in the Jensen gap that results from the change in the variance of the solution. The last term is the change in the Jensen gap resulting from a change in the curvature of the objective function due to the DRO/DOO bias (ref). When $f(x, Y)$ is concave but not linear, it is clear from (ref) that $\rho$ is unlikely to be zero, except in pathological cases.

The following result shows that it is always possible to select $\delta$ so that the out-of-sample expected reward under the DRO/DOO solution $x_n(\delta)$ exceeds that of $x_n(0)$ and provides an estimate of the size of the outperformance.

Although we can always out-perform SAA, (ref) suggests that it is on the order of $n^{-2}$, regardless of whether it was achieved by best-case or worst-case optimization. Out-performance from either DRO or DOO is unlikely to be large if $n$ is large or $\rho$ is small. More generally, $\frac{\rho}{n}$ is the sensitivity of the sum of (A) and (B) in (ref) to changes in $\delta$. Our assumptions allow us to estimate this explicitly. (A) and (B) may depend differently on $n$ and $\delta$ in applications where our assumptions do not hold, though we have not explored this issue.

It is difficult to compute $\rho$ because it depends on the solution of the population problem $x^\star(0)$ and the population distribution $\mathbb P$, both of which are unknown, and hence to determine {\it a priori} whether the optimistic or worst-case solution will out-perform SAA. This can be sidestepped by optimizing a bootstrap or cross-validation estimate of the out-of-sample reward over $\delta$, which we explore in an inventory problem in Section (ref).

One limitation of our analysis is that we make strong assumptions about the differentiability of $f(x, Y)$. These assumptions enable us to characterize the statistical properties of the SAA and DRO/DOO solutions and to analyze out-of-sample performance. However, there are many applications where they are not satisfied, the inventory problem below being one such case. Our assumptions enable us to illustrate what is possible with DOO and to provide insight into why it occurs. We do not rule out the possibility that either DRO or DOO will out-perform SAA when the differentiability assumptions we impose are not satisfied. All predictions that stem from our analysis, both in Theorem (ref) and later sections, are observed in the inventory example, where the objective function violates Assumption (ref).

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 AP,GKL-cal. 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.

So, what is the catch?

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 GKL-cal,GKL,GKL-WCS. 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 GKL. 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

Here, the penalty $\sfrac{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

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 GKL-WCS. However, they all capture a similar idea.

Worst-case sensitivity is an in-sample {\it 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 {\it generalized measure of deviation (spread)} GKL-WCS. 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 {\it 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 (ref). 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 (ref), the in-sample variance of the reward under $x_n(\delta)$ is

where

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

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

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.

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.

Other remarks

The paper Lam2\footnote{The paper Lam2 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

where $x^\star(0)$ is the population optimizer (ref), 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).

To evaluate performance (ref), Lam2 considers the difference (regret) between the expected reward of the data-driven and population optimizers

where $g(x)$ was defined in (ref), and shows that the weak limit ($n\rightarrow\infty$) of the scaled regret $n{\mathcal G}(\tilde{x}_n(\delta_n))$ is second-order stochastically larger than the weak limit of the scaled regret $n{\mathcal G}(\tilde{x}_n(0))$ of the SAA optimizer. In this sense it is impossible to beat SAA asymptotically when an algorithm has solutions of the form (ref).

While this appears to contradict Theorem (ref), which says that it is always possible to beat SAA using DRO/DOO, there is actually no inconsistency. Lam2 shows the optimality of the {\it limiting reward distribution} of SAA under second order stochastic dominance, whereas we use the asymptotic distribution of the DRO/DOO and SAA solutions to estimate the difference between the out-of-sample expected rewards for finite $n$ (ref).This difference is of order $\delta/n$, and the advantage of DRO/DOO over SAA vanishes at a rate faster than $1/n$ if $\delta \equiv \delta_n$ itself is going to $0$. Indeed, it was shown in Theorem (ref) that the optimal choice of $\delta$ is of order $1/n$ and the improvement over SAA is 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 Lam2.

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 bit: It also reduces the sensitivity of the expected reward to misspecification in the nominal which, as the reader may recall, was the point of robust decision making in the first place. More generally, it captures the tradeoff between maximizing expected reward and controlling sensitivity which is relevant in many applications of data-driven decision making.

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 $n^{-2}$) relative to the robustness cost. 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.