We study the problem of designing optimal learning and decision-making formulations when only historical data is available.
Prior work typically commits to a particular class of data-driven formulation and subsequently tries to establish out-of-sample performance guarantees.
We take here the opposite approach.
We define first a sensible yard stick with which to measure the quality of any data-driven formulation and subsequently seek to find an “optimal” such formulation.
Informally, any data-driven formulation can be seen to balance a measure of proximity of the estimated cost to the actual cost while guaranteeing a level of out-of-sample performance.
Given an acceptable level of out-of-sample performance, we construct explicitly a data-driven formulation that is uniformly closer to the true cost than any other formulation enjoying the same out-of-sample performance.
We show the existence of three distinct out-of-sample performance regimes (a superexponential regime, an exponential regime and a subexponential regime) between which the nature of the optimal data-driven formulation experiences a phase transition.
The optimal data-driven formulations can be interpreted as a classically robust formulation in the superexponential regime, an entropic distributionally robust formulation in the exponential regime and finally a variance penalized formulation in the subexponential regime.
This final observation unveils a surprising connection between these three, at first glance seemingly unrelated, data-driven formulations which until now remained hidden.

§ DATA-DRIVEN DECISION MAKING

We consider static decision problems in the face of uncertainty where the probability distribution of the uncertainty remains unobserved but rather must be learned from a finite number of independent samples.
Let $\mathcal{X}$ be a compact set of possible decisions and $\xi$ a random variable realizing in a set $\Sigma$ representing the uncertainty.
For a given scenario $i \in \Sigma$ of the uncertainty, and a decision $x \in \mathcal{X}$, the loss incurred for  decision $x$ in scenario $i$ is denoted here as $\loss(x, i) \in \Re$. We assume throughout that this loss function is continuous in the decision $x$ for any scenario $i$.
The random variable $\xi$ is distributed according to a probability distribution $\Pb$ in the probability simplex $\mathcal{P}$ over $\Sigma$.
The problem we wish to approximate is

\begin{equation}\label{eq: stochastic opt}
\min_{x \in \mathcal{X}}~ \mathbb{E}_{\Pb}(\loss(x, \xi)),
\end{equation}

where the cost function $c(x,\Pb) = \mathbb{E}_{\Pb}(\loss(x, \xi))$ represents an expected loss.
Whereas the loss $\loss(x, i)$ of each decision $x$ is known for each scenario $i$, the cost $c(x, \Pb)$ of each decision remains unknown as it is a function of the unknown probability distribution $\Pb$. The described class of problems is rather large as it describes both empirical risk minimization problems in machine learning as well as data-driven decision problems in operations research.

[Machine Learning]
Given covariates $(X,Y)\in \Re^n\times \Re$ following an unknown probability distribution $\Pb$, a set of parametrized functions $\{f_{\theta}\}_{\theta \in \Theta}$, and a loss function $L :\Re \times \Re \rightarrow \Re$, the goal is to learn the parameter $\theta$ that minimizes the expected out-of-sample error

\begin{equation}\label{eq: ML problem}
\min_{\theta \in \Theta}~\Eb_{ \Pb}[L(f_{\theta}(X),Y)].
\end{equation}

Such learning problem can be seen as a stochastic optimization problem of the form (<ref>) by letting $x:= \theta$, $\xi:=(X, Y)$, and $c(x,\Pb):= \Eb_{ \Pb}[L(f_{\theta}(X),Y)]$.

[Two-Stage Stochastic Optimization]
Consider a two-stage decision problem in which we need to make a first-stage decision $z_0\in \Re^{m_1}$ after which the random variable $\xi\in \Sigma$ with distribution $\Pb$ is observed. Subsequently, a second-stage decision $z(\xi)\in \Re^{m_2}$ needs to be made which may be a function of the observed event $\xi$. The total loss incurred is denoted here as $\ell(z_0, z(\xi), \xi)$.
The decision problem consists now of minimizing the expected overall cost

\[
\begin{array}{rl}
\min & \mathbb{E}_{ \Pb}(\ell(z_0, z(\xi), \xi))\\
\st  & z_0\in\Re^{m_1},~z:\Sigma\to\Re^{m_2}.
\end{array}
\]

This problem can be seen as a stochastic optimization problem (<ref>) by choosing $x:= (z_0, z: \Sigma \rightarrow \Re^{m_2})$ and  $c(x,\Pb) := \mathbb{E}_{ \Pb}(\ell(z_0, z(\xi), \xi))$.

In practice the unknown distribution is never observed directly but rather must be estimated from historical data.
Problem (<ref>) can hence not be solved directly. Typically, it is assumed instead that we observe independent samples $\{\xi_1, \ldots, \xi_T\} \in \Sigma^T$ identically distributed as the unknown distribution $\Pb$.
The most straightforward | and perhaps the most common | way to formulate a data-driven counterpart to Problem (<ref>) is to simply replace the unknown distribution with its empirical counterpart and to solve instead the problem

\begin{equation*}
\min_{x\in \cX}\, \mathbb{E}_{\hat{\Pb}_T} (\loss(x, \xi))
\min_{x\in \cX} \,\textstyle \frac{1}{T} \sum_{t=1}^T \loss(x, \xi_t),
\end{equation*}

where we denote with $\hat{\Pb}_T$ the empirical distribution of the observed data points,
$\hat{\Pb}_T(i) := \frac{1}{T}\sum_{t=1}^T \mathbb{1}_{\xi_t = i}$ for all $i \in \Sigma$.
This formulation is well known in the optimization community as the Sample Average Approximation (SAA) [Shapiro, 2003]. When applied to the machine learning problem discussed in Example <ref> this approach reduces to the well known Empirical Risk Minimization (ERM) principle [Vapnik, 2013].
SAA and ERM are motivated by the fact that the historical empirical cost is the simplest and perhaps most natural substitution for the unknown actual cost.
However, this naive substitution is well documented to yield decisions which are prone to adverse overfitting effects and may suffer disappointing out-of-sample performance.  It is particularly pronounced in machine learning, where it is known as “overfitting”. In decision analysis, Smith and Winkler, 2006 refer to it as the “optimizer's curse”, and in finance, Michaud, 1989 call it the “error maximization effect” of portfolio optimization.
This is perhaps not unsurprising as the empirical mean $c(x, \hat{\Pb}_T)$ indeed enjoys desirable properties as an estimator for the unknown cost $c(x, \Pb)$ but is not necessarily tailored for use in a subsequent optimization problem.
The observation that good estimators for prediction do not generally translate to good estimators for prescription recently spurred interest into “optimization aware” estimation approaches [Elmachtoub and Grigas, 2021]. To guard against this overfitting effect, two alternative approaches to simple ERM/SAA have sparked interest in the past years: regularized formulations and distributionally robust formulations.

Regularized Formulations.
The use of regularization to improve prediction is well established and was indeed studied already by Tikhonov, 1943 in the context of ill-posed inverse problems. Likewise, regularization for the benefit of prescription was proposed by [Mulvey et al., 1995] and has been tremendously influential. Decision formulations and their associated prescriptions can be guarded against overfitting by considering regularized cost estimators.
Such regularized formulations estimate the cost of any decision as

\begin{equation*}
\Eb_{\hat{\Pb}_T}(\ell(x, \xi)) + R(x, \hat{\Pb}_T, T),
\end{equation*}

where the contribution $R(x, \hat{\Pb}_T, T)$ is referred to as the regularization term.
For instance in the context of machine learning, c.f., Example <ref>, regularized ERM formulations typically take the form
\(
\frac{1}{T} \sum_{t=1}^T L(f_{\theta}(X_t),Y_t) + \lambda_T \mu(\theta)
\)
where $\lambda_T \in \mathbf{R}_+$ and $\mu: \Theta \rightarrow \mathbf{R}_+$. Identifying $\mu(\theta)$ for instance as $\|\theta\|_0$, $\|\theta\|_1$, $\|\theta\|_2$ yields respectively sparse regression, LASSO [Tibshirani, 1996], and Ridge [Hoerl and Kennard, 1970, Hoerl and Kennard, 1970].
These methods have been shown to enjoy strong out-of-sample performance both in theory [Koltchinskii et al., 2011, van de Geer, 2016] as well as in practice.

One particular example of regularization, which will come to play a protagonist role in this paper, is the Sample Variance Penalization (SVP) formulation which considers regularized estimates of the form

\begin{equation}\label{eq: exp SVP}
\Eb_{\hat{\Pb}_T}(\ell(x, \xi)) + \lambda_T \sqrt{\Var_{\hat{\Pb}_T}(\loss(x, \xi))},
\end{equation}

where $\Var_{\hat{\Pb}_T}(\loss(x, \xi))$ denotes the empirical variance of the loss. Although the term SVP was coined by Maurer and Pontil, 2009 in the context of machine learning, the benefits of variance regularization were documented much earlier by [Markowitz, 1952] in the context of portfolio selection. This regularized formulation is biased towards decisions for which the empirical variance of the cost is low rather than high. In particular, Maurer and Pontil, 2009 show that SVP enjoys out-of-sample performance guarantees of the form

\begin{equation}\label{eq: bound for SVP}
\Pb^{\infty}\left(
\Eb_{\Pb}(\ell(x, \xi))
\Eb_{\hat{\Pb}_T}(\ell(x, \xi)) + \sqrt{\frac{2a}{T}} \sqrt{\Var_{\hat{\Pb}_T}(\loss(x, \xi))}
+  C\frac{a}{T}
\right)
\leq
\end{equation}

for all $a>0$ and $T\in \integ$ with $C>0$ is a constant. As in the rest of the paper $\Pb^{\infty}$ denotes here the probability distribution of the independent identically distributed data on which the estimate $\hat{\Pb}_T$ is constructed.
Notice that the parameter $a$ controls here the level of out-of-sample performance we can expect the associated SVP estimator to enjoy.
Inequality (<ref>) hence guarantees that SVP provides an upper bound of the true error with high probability. Seeking to minimize an upper bound on the true error is a common strategy to derive estimation procedures with guaranteed out-of-sample performance in machine learning.

Distributionally Robust Formulations.
The use of robust formulations to guard against overfitting and to guarantee out-of-sample performance was popularized by Ben-Tal et al., 2009. During the last decade in particular, Distributionally Robust Optimization (DRO) formulations have witnessed a surge in popularity.
Such formulations consider an ambiguity set $\mathcal{U}_T(\hat{\Pb}_T)\subseteq \cP$ around the empirical distribution $\hat{\Pb}_T$ and protect against overfitting by considering decisions which minimize the worst-case cost over all considered probability distributions in $\mathcal{U}_T(\hat{\Pb}_T)$ instead of merely the empirical one.
That is, they estimate the cost of any decision as

\[
\sup_{\Pb' \in \cP} \set{\Eb_{\Pb'}(\loss(x,\xi))}{\Pb' \in \mathcal{U}_T(\hat{\Pb}_T)}.
\]

Evidently, the particular ambiguity set $\mathcal{U}_T(\hat{\Pb}_T)\subseteq \cP$ considered will ultimately determine the statistical properties and computational challenges of the associated robust data-driven formulation.
Much of the early literature [Delage and Ye, 2010, Wiesemann et al., 2014, Van Parys et al., 2016, Van Parys et al., 2016] focused on ambiguity sets consisting of probability measures sharing certain given moments and shape constraints.
More recent approaches [Bertsimas et al., 2018] however consider ambiguity sets which are based on a statistical distance  instead. For instance, Kuhn et al., 2019, Gao and Kleywegt, 2016 propose to consider ambiguity sets consisting of all distributions at distance at most $r$ to the empirical distribution in the Wasserstein metric.

The recent uptick in popularity of such robust formulations is in no small part due to the fact that they are often tractable and enjoy superior statistical guarantees.
<cit.> indicate for instance that the probability that the estimated cost of the Wasserstein DRO formulation does not upper bound the actual unknown cost decays as

\begin{equation}\label{eq: Wasserstein bound}
\Pb^\infty \left(
\Eb_{\Pb}(\loss(x,\xi))
\sup_{\Pb' \in \cP} \set{\Eb_{\Pb'}(\loss(x,\xi))}{\Pb' \in \mathcal{U}_T(\hat{\Pb}_T)}
\right)\leq
C_1 e^{-C_2 T r^{\max(2,\dim\Sigma)}}
\end{equation}

when $r<1$, where $C_1$, $C_2$ are positive constants.
Such result guarantees that the undesirable event in which the cost estimate does not perform well out-of-sample can be controlled by selecting an appropriate robustness radius $r$.

Regularization and robustness appear at first glance to be two distinct ideas with which to encourage a nominal formulation to enjoy better out-of-sample guarantees. However, intimate connections between both ideas have been reported before by [Xu et al., 2009].
In particular, Gao et al., 2017 state an equivalence between Wasserstein DRO formulations and a certain gradient-norm regularization formulation. In Proposition <ref>, we establish as an aside that the SVP formulation of [Maurer and Pontil, 2009] enjoys a robust interpretation with respect to a particular ellipsoidal $\chi^2$-divergence ambiguity set. Furthermore, from the previous discussion it is clear that adding robustness reduces to regularization with

\[
R(x, \hat{\Pb}_T, T) =  \sup_{\Pb' \in \cP} \set{\Eb_{\Pb'}(\loss(x,\xi))}{\Pb' \in \mathcal{U}_T(\hat{\Pb}_T)} - c(x, \hat{\Pb}_T)) \geq 0.
\]

While the addition of robustness or equivalently regularization may help to guard against overfitting, it is unclear what amount of regularization or robustness is necessary. More generally,
given multiple formulations which can help guard against overfitting, a pressing question is whether any such formulation should be preferred over all others.
Ultimately, the question which we want to address is as follows:

What is the best formulation for the purpose of data-driven decision-making and machine learning?

Let us formalize this question of optimal “optimization aware” estimation. For the purpose of decision-making in the context of problem (<ref>), we identify two fundamental parts of our problem: a prediction problem and a prescription problem. We believe that both problems are interesting in their own right and hence we will discuss them separately.

§.§ Prediction Problems

The prediction problem consists of estimating the unknown cost of a given decision|the unknown expectation in (<ref>)|based on data. That is, constructing an estimate of the cost function using only the observed data. Such an estimate is called a data-driven predictor. In our setting all statistical information of the observed data can be compressed into its empirical distribution $\hat{\Pb}_T$.
Indeed, the order of the observed data points is of no importance when the data samples are independent.
Hence, in full generality, the data-driven predictor can be written as a function of the decision, the observed empirical distribution and the data size.

A predictor $\hat c$ is a sequences of functions $\{\hat{c}(\cdot,\cdot,T) \in \mathcal{X}\times \mathcal{P} \to \Re\}_{T\in \integ}$. For each distribution of the uncertainty $\Pb \in \cP$, decision $x \in \cX$, and data size $T \in \integ$, $\hat{c}(x,\hat{\Pb}_T,T)$ estimates the true cost $c(x,\Pb) = \Eb_{\Pb}(\loss(x,\xi))$ of decision $x$ under distribution $\Pb$.

We will restrict our study to the class of smooth predictors $\cC$ which we discuss later. Our goal is to define a notion of optimality for data-driven predictors based on how well they balance two competing properties: out-of-sample performance and accuracy.

Out-of-Sample Performance.

The main issue with the naive estimator used in SAA or ERM formulations is its tendency to overfit the training data and consequently suffer poor out-of-sample performance. In the context of decision-making, disappointment events in which the actual cost is underestimated may result in high unexpected cost and should hence be avoided. In the context of machine learning,
when the in-sample error underestimates the out-of-sample error we say overfitting takes place. Indeed, a well performing regression on training data which however performs badly out-of-sample is said to overfit.
Hence, under both circumstances we desire predictors which upper bound the unknown out-of-sample cost with high probability.
Formally, the predictor is desired to have, for all decision $x \in \cX$ and underlying distribution $\Pb \in \cP$, a low probability of disappointment

\begin{equation}\label{eq: out-of-sample proba}
\Pb^\infty \left( c(x, \Pb) > \hat c(x, \hat{\Pb}_T,T)\right).
\end{equation}

Typically in the decision-making and statistical learning literature, one first considers a particular predictor and subsequently looks to establish out-of-sample disappointment guarantees of the form (<ref>) such as[Some bounds in the literature exhibit an additive constant in the inequality of bounds of the form (<ref>). This is equivalent to the form (<ref>) by incorporating the constant in the predictor $\hat{c}$.] those found in equations (<ref>) and (<ref>).
We take here precisely the opposite approach.
That is, we will impose a desired out-of-sample guarantee and only then seek to determine the “best” predictor verifying said imposed out-of-sample guarantee.

For a given sequence $(a_T)_{T\geq 1} \in \Re_+^{\integ}$ verifying $a_T \to \infty$, we are interested in predictors $(\hat{c}(\cdot,\cdot,T))_{T\geq 1}$ verifying the out-of-sample guarantee

\begin{equation}\label{eq: out-of-sample ganrantee}
\limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( c(x, \Pb) > \hat c(x, \hat{\Pb}_T,T)\right)\leq -1 \quad \forall x \in \mathcal{X}, \; \forall \Pb \in \mathcal{P}.
\end{equation}

Such guarantee imposes that the estimated cost bounds the out-of-sample cost from above, i.e., $c(x, \Pb) < \hat c(x, \hat{\Pb}_T,T)$, with probability at least $1-e^{-a_T+o(a_T)}$.
The sequence $(a_T)_{T\geq 1}$ quantifies the desired speed with which the predictor enjoys stronger out-of-sample performance as the amount of available data grows. We reiterate the generality of our setting: for any sequence $(a_T)_{T\geq 1}$ and associated desired out-of-sample guarantee, we seek to find what is the “best” predictor using data that provides the desired out-of-sample guarantee. Let us now precise rigorously what constitutes such “best” predictor.

It is easy to construct estimators with low probability of disappointment. Indeed, by simply inflating the empirical cost, i.e.,

\[
\hat{c}(x,\hat{\Pb}_T,T) = c(x, \hat{\Pb}_T) + R
\]

for some large $R > 0$, the probability of disappointment can be made arbitrarily small. The resulting cost estimate is however very conservative which is clearly undesirable. Moreover, we will indicate in the sequel that the imposed out-of-sample guarantee (<ref>) requires predictors to add a positive regularization. This suggests to compare predictors based on the amount of regularization they add to the empirical cost.

Among the predictors verifying the out-of-sample guarantee, we seek a predictor which adds the least amount of regularization to the empirical cost. Recall that $(\hat{c}(x,\hat{\Pb}_T,T))_{T\geq 1}$ is used to estimate $c(x,\Pb)$. Hence, the term $(\hat{c}(x,\hat{\Pb}_T,T) - c(x,\hat{\Pb}_T))_{T\geq 1}$ is precisely the amount of regularization added to the empirical cost $c(x,\hat{\Pb}_T)$ by the predictor $\hat{c}(x,\hat{\Pb}_T,T)$.
We seek predictors that add less regularization uniformly in all decisions $x\in \cX$ and realization of the empirical distribution $\hat{\Pb}_T$.
We introduce, therefore, the partial order $\preceq_{\mathcal{C}}$ on the set of predictors defined as[We indicate that dropping the absolute values in the definition of the order $\preceq_{\cC}$ leads to an equivalent order.]

\hat{c}_1 \orderleq \hat{c}_2 \iff
\forall x,\Pb \in \cX\times \cPin \quad
\limsup_{T\to \infty} \frac{|\hat{c}_1(x,\Pb,T)-c(x,\Pb)|}{|\hat{c}_2(x,\Pb,T)-c(x,\Pb)|} \leq 1,

for $\hat{c}_1,\hat{c}_2 \in \cC$. Intuitively, $\hat{c}_1$ is preferred to $\hat{c}_2$ if asymptotically, $\hat{c}_1$ adds less regularization in its worst case than $\hat{c}_2$ adds in its best case. That is, informally, for every $x $ and $\Pb$ we have
\(
\sup_{t\geq T}{|\hat{c}_1(x,\Pb,t)-c(x,\Pb)|}
\lesssim
\inf_{t\geq T}{|\hat{c}_2(x,\Pb,t)-c(x,\Pb)|}.
\)
Moreover, as seen in the previous section, predictors verifying the out-of-sample guarantee provide a high probability upper bound on the true cost. Hence, when $\hat{c}_1$ and $\hat{c}_2$ verify the out-of-sample guarantee, and $\hat{c}_1 \preceq_{\cC} \hat{c}_2$, $\hat{c}_1$ is intuitively a uniformly better upper bound than $\hat{c}_2$ and hence ought to be preferred.
Notice finally that we can verify easily that $\orderleq$ is a partial order with the equivalence relation $\equiv$ defined as $\hat{c}_1 \equiv \hat{c}_2 \iff |\hat{c}_1(x,\Pb,T)-c(x,\Pb)| \sim |\hat{c}_2(x,\Pb,T)-c(x,\Pb)|, \; \forall x,\Pb \in \cX, \cP$ where $\sim$ denotes asymptotic equivalence when $T \to \infty$. Figure <ref> illustrates this order and the out-of-sample guarantee.

There are many other natural possible orders one could consider. For example, one can compare predictors in terms of their expected bias $\Eb_{
\Pb}(\hat{c}(x,\hat{\Pb}_T,T) - c(x,\Pb))$ or $L^1$ error $\Eb_{
\Pb}(|\hat{c}(x,\hat{\Pb}_T,T) - c(x,\Pb)|)$ for all decision $x\in \cX$ and underlying true distribution $\Pb \in \cP$. We prove, under mild assumptions, that our considered order is stronger than both alternative orders induced by expected bias and $L^1$ error (see Lemma <ref>): uniformally less regularization implies less expected bias and less $L^1$ error.

Each colored curve represents the nominal value of a predictor $\hat{c}(x,\Pb,T)$, for a fixed $T$, the black lower curve being the true cost $c(x,\Pb)$. The shaded region represents the random values of $\hat{c}(x,\hat{\Pb}_T,T)$ which occur with high probability $\sim 1-e^{-a_T}$. The predictor $\hat{c}_1$ on the left does not verify the out-of-sample guarantee as there is a set of probability larger than $e^{-a_T}$ where $\hat{c}_1(x,\hat{\Pb}_T,T)<c(x,\Pb)$ (the shaded region below the $c$ curve). The predictor $\hat{c}_2$ on the other hand verifies the out-of-sample as for all values of $\hat{\Pb}_T$ on the high probability set, $\hat{c}_2(x,\hat{\Pb}_T,T)\geq c(x,\Pb)$. The figure on the right illustrates the order $\preceq_{\cC}$. In the figure, $\hat{c}_1$ and $\hat{c}_2$ can not be compared as none is better uniformly than the other. The predictor $\hat{c}_3$ is uniformally closer to $c$ than $\hat{c}_1$ and $\hat{c}_2$, hence $\hat{c}_3 \preceq_{\cC} \hat{c}_1$ and $\hat{c}_3 \preceq_{\cC} \hat{c}_2$. Notice that as both our feasibility and order notions are asymptotic in $T$, the figure here is merely an illustration.

Optimal Prediction.
There is an inherent trade-off between closeness to the true cost (less regularization) and verifying the imposed out-sample guarantee. Due to the fluctuations of the empirical distribution $\hat{\Pb}_T$ around the true distribution $\Pb$, the prediction $\hat{c}(x,\hat{\Pb}_T,T)$ fluctuates around the nominal value $\hat{c}(x,\Pb,T)$. Therefore, the closer $\hat{c}(x,\Pb,T)$ is to the true cost $c(x,\Pb)$, the higher the probability that it disappoints, i.e., $\hat{c}(x,\hat{\Pb}_T,T) \leq c(x,\Pb)$ (see Figure <ref>). Hence, the more preferred a predictor is in terms of our introduced accuracy order $\preceq_{\cC}$, the weaker the out-of-sample guarantees it will verify.

Using the order $\orderleq$, we can formulate the problem of finding the optimal predictor verifying a given out-of-sample guarantee as the following meta-optimization problem:

\begin{equation}
\label{eq:optimal-predictor}
\begin{array}{ll}
\displaystyle\mathop{\text{minimize}}_{\hat c\in \mathcal{C}}{}_{\preceq_{\cC}} & \hat c \\
\text{subject to} & \displaystyle \limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( c(x, \Pb) > \hat c(x, \hat{\Pb}_T,T)\right)\leq -1 \quad \forall x\in \mathcal{X},\;\Pb\in \cPin.
\end{array}
\end{equation}

A feasible predictor $\hat{c}$ in problem (<ref>) is a predictor $\hat{c} \in \cC$ verifying the out-of-sample guarantee (<ref>).
A weakly optimal solution to problem (<ref>) is a feasible predictor $\hat{c}$ such that no other feasible predictor is prefered to $\hat{c}$.
A strongly optimal solution to problem (<ref>) is a feasible predictor $\hat{c}$ that is preferred to all feasible predictor $\hat{c}'$, ie $\hat{c} \orderleq \hat{c}'$. Typically, several weakly optimal solutions may be expected to exist, while there rarely exists a strongly optimal solution.
When a strongly optimal solution $\hat{c}$ exists, it means that for the purpose of data-driven prediction with the desired out-sample guarantee, there is no incentive to use a different predictor than $\hat{c}$ as it is preferred to all other predictors verifying the out-of-sample guarantee, for any uncertainty distribution $\Pb$ and decision $x$. We finally point out that strongly optimal solutions are unique in the sense that any two strongly optimal solutions $\hat{c}_1$ and $\hat{c}_2$ are necessarily equivalent in the sense that $\hat{c}_1 \equiv \hat{c}_2$.

§.§ Prescription Problems

Predicting the cost of any decision $x$ (or parameter choice $\theta$ in the context of machine learning, Example <ref>) is typically merely a means to derive an approximation of the optimal solution and its cost.
Out-of-sample guarantees of the form (<ref>),
which hold pointwise for any decision $x$, do not generally hold for the prescribed decision with minimal estimated cost
\argmin_{x \in \cX} \hat{c}(x,\hat{\Pb}_T,T)
An indirect way to impose out-of-sample guarantees on the prescribed decision is to derive a uniform counterpart to (<ref>) which holds uniformly for all decisions.
To do so in statistical learning, one typically restricts the considered function class $\{f_{\theta}\}_{\theta \in \Theta}$ to be of controlled bounded complexity, as measured by covering numbers or VC dimension [Vapnik, 2013, Vapnik and Chervonenkis, 2015].
When the purpose of decision-making is only to derive the optimal solution of problem (<ref>), seeking such uniform bounds seems unduly restrictive. We seek, therefore, to investigate cost estimates satisfying out-of-sample guarantees precisely at the prescribed decision instead of uniformly over all decisions. In the following, we formalize these observations in what we call the prescription problem.

Our prescription problem consist in using the observed data to choose a decision $x\in \cX$ minimizing the true cost $c(\cdot,\Pb)$. Unlike in the prediction problem, we are only interested in approximating the minimizer and minimum of Problem (<ref>) and not in estimating the cost of any alternative decision. A prescriptor $\hat x$ is  here any mapping from data to decisions which is consistent with some predictor $\hat c$, approximating the true cost.

A precriptor is a sequence of functions $\hat{x}_T(\cdot): \cP \longrightarrow \cX$, $T\in \integ$ such that there exists a predictor $\hat{c} \in \cC$ verifying

\hat{x}_T(\Pb) \in \argmin_{x \in \cX} \, \hat{c}(x,\Pb,T), \quad \forall \Pb \in \cP, \; T \in \integ.

For each empirical distribution $\hat{\Pb}_T$ and data size $T$, the prescription $\hat{x}_T(\hat{\Pb}_T)$ approximates the optimal solution of $\min_{x\in \cX} c(x,\Pb)$. We denote by $\hat{\cX}$ the set of prescriptors and their associated predictors.

Akin to the discussion in the predictor problem we will judge any prescriptor in terms of their out-of-sample performance and accuracy. Both quantities will be defined similarly as in the prediction problem but crucially only pertain to one particular decision | that is to say the suggested prescription.

Out-of-Sample Guarantee. In the prescription problem estimating the true expected value in Problem (<ref>) is only a means with which to find an associated decision with good out-of-sample cost.
We seek therefore to construct a predictor with an out-of-sample cost at least as good as its estimated cost with high probability.
In other words, the optimal cost of the predictor $\hat{c}^{\star}(\hat{\Pb}_T,T):= \hat{c}(\hat{x}_T(\hat{\Pb}_T),\hat{\Pb}_T,T)$ is an upper bound on the unknown out-of-sample cost of the prescribed decision $c(\hat{x}_T(\hat{\Pb}_T),\Pb)$ with high probability.
Formally, the estimator is desired to have a low probability of disappointment

\begin{equation}\label{eq: prec out-of-sample garantee prob}
\Pb^\infty
\left(
c(\hat{x}_T(\hat{\Pb}_T), \Pb) > \hat c^{\star}(\hat{\Pb}_T,T)
\right).
\end{equation}

For a given sequence $(a_T)_{T\geq 1} \in \Re_+^{\integ}$ verifying $a_T \to \infty$, we are interested in presciptors verifying the out-of-sample guarantee on the probability of disappointment:

\begin{equation}\label{eq: prescriptor out-of-sample ganrantee}
\limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( c(\hat{x}_T(\hat{\Pb}_T), \Pb) > \hat c^{\star}(\hat{\Pb}_T,T) \right)\leq -1, \quad \forall  \Pb \in \mathcal{P}.
\end{equation}

The sequence $(a_T)_{T\geq 1}$ quantifies yet again the desired speed with which the prescriptor enjoys stronger out-of-sample performance as the amount of available data grows. For any desired out-of-sample guarantee with probability $1-e^{-a_T+o(a_T)}$, we seek to find what is the “best” precriptor using data that provides the desired out-of-sample guarantee.

Similarly as in the prediction problem, among these prescriptors, we investigate which one constitutes the best approximation to the optimal cost $c^{\star}(\Pb) :=\min_{x\in\cX}c(x,\Pb)$. We introduce therefore the following partial order $\preceq_{\hat{\mathcal{X}}}$ on prescriptors and their associated predictors

(\hat{c}_1,\hat{x}_1) \preceq_{\hat{\mathcal{X}}} (\hat{c}_2,\hat{x}_2) \iff
\forall \Pb \in \cPin \quad
\limsup_{T\to \infty} \frac{|\hat{c}_1^{\star}(\Pb,T) - c^{\star}(\Pb)|}{|\hat{c}_2^{\star}(\Pb,T) - c^{\star}(\Pb)|} \leq 1.

Clearly, given two pairs of predictors $(\hat{c}_1,\hat{x}_1)$ and $(\hat{c}_2,\hat{x}_2)$ both of which satisfy the out-of-sample guarantee (<ref>) one ought to prefer $(\hat{c}_1,\hat{x}_1)$ to $(\hat{c}_2,\hat{x}_2)$ if $(\hat{c}_1,\hat{x}_1) \preceq_{\hat{\mathcal{X}}} (\hat{c}_2,\hat{x}_2)$ as the first pair enjoys the same out-of-sample guarantee but is more accurate in its cost prediction. We remark that our proposed order only takes into consideration the accuracy of the cost predictor at the associated prescribed action and is blind to its accuracy with respect to any other alternative decision.
It should be remarked that $\orderpresc$ is here a partial order with the equivalence relation $\equiv_{\hat{\cX}}$ defined as $(\hat{c}_1,\hat{x}_1) \equiv_{\hat{\cX}} (\hat{c}_2,\hat{x}_2) \iff |\hat{c}_1^{\star}(\Pb,T) - c^{\star}(\Pb)| \sim |\hat{c}_2^{\star}(\Pb,T) - c^{\star}(\Pb)|, \; \forall \Pb \in \cPin$, where $\sim$ denotes asymptotic equivalence as $T \to \infty$.

Optimal Prescription.
Designing the optimal prescriptor amounts therefore to balancing out-of-sample performance and accuracy at the prescribed decision. This balancing act is formalized as the meta-optimization prescription problem

\begin{equation}
\label{eq:optimal-prescriptor}
\begin{array}{ll}
\displaystyle\mathop{\text{minimize}}_{(\hat c, \hat x)\in \hat{\mathcal{X}}}{}_{\preceq_{\hat{\mathcal{X}}}} & (\hat c, \hat x) \\
\text{subject to} & \displaystyle \limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( c(\hat{x}_T(\hat{\Pb}_T), \Pb) > \hat c^{\star}(\hat{\Pb}_T,T) \right)\leq -1, \quad \forall \Pb \in \mathcal{P}.
\end{array}
\end{equation}

We define the notions of feasibility, weak optimality and strong optimality similarly as in the prediction problem.
We note that feasible solutions of the optimal prediction problem (<ref>) are not necessarily feasible in the optimal prescription problem (<ref>) as the prediction out-of-sample guarantee does not directly imply the prescription out-of-sample guarantee on the prescribed solution, as discussed earlier.
A key question is whether the prescription problem, where the guarantees are only enforced at the prescribed solution, admits “better” solutions for the purpose of prescription than the solutions of the prediction problem. More precisely, does requiring out-of-sample guarantees only at the prescribed decision instead of every decision provides predictors with better prescribed decisions?

§.§ Summary of Results

Solutions to the optimal prediction problem (<ref>) and the optimal prescription problem (<ref>) will come to depend heavily on the choice of the strength of the imposed out-of-sample performance via the choice of the sequence $(a_T)_{T\geq1}$. The larger $(a_T)_{T\geq1}$, the stronger the required guarantees and consequently the more conservative the feasible predictors and prescriptors. Perhaps surprisingly, in each scenario of the out-of-sample guarantee, there exists a strongly optimal solution which we can exhibit. To prove this result we will assume in this paper that the set of events $\Sigma$ has finite cardinality. Extending our results to the more general case of continuous event sets, along the lines of [Van Parys et al., 2020], is a possibility but would require a vastly more technical exposition. We believe that the results in the discrete event case which we present momentarily are sufficiently interesting to warrant this slightly restrictive assumption.

The exponential regime in which strong out-of-sample guarantees are imposed with $a_T/T \to r$ ($a_T \sim rT$) for $r>0$ has been studied by [Van Parys et al., 2020]. Here the decision-maker desires an exponentially decreasing probability of out-of-sample disappointment. They prove in a  less general setting|in which the considered formulations do not directly depend on the data size|that the DRO predictor with Kullback-Leibler ball

\begin{equation}\label{eq: KL predictor intro}
\hat{c}(x,\hat{\Pb}_T,T) = \sup_{\Pb'\in \Pb} \set{c(x,\Pb')}{\sum_{i\in \Sigma}\hat{\Pb}_T(i) \log \left( \frac{\hat{\Pb}_T(i)}{\Pb'(i)} \right)\leq r}
\end{equation}

is strongly optimal for both the optimal prediction and prescription problem. The optimal predictor $\hat{c}$ is in this regime not consistent as more data is observed. Indeed, their considered ambiguity set does not depend on the data size and hence can not shrink as more data is observed.

We will study here the entire spectrum of out-of-sample guarantees: the superexponential regime in which yet stronger out-of-sample guarantees are imposed, i.e., $a_T/T \to \infty$ ($a_T \gg T$), the exponential regime $a_T/T \to r$ ($a_T \sim rT$), as well as the subexponential regime where moderate out-of-sample guarantees suffice, i.e., $a_T/T \to 0$ ($a_T \ll T$). We explicitly construct in all three discussed regimes a strongly optimal solution in both the optimal prediction and prescription problems (<ref>) and (<ref>).

In the superexponential regime we prove that it is necassary to guard against all outcomes no matter the observed data. The robust predictor

\begin{equation*}
\hat{c}(x,\hat{\Pb}_T,T) = \sup_{\Pb' \in \cP} c(x,\Pb') \quad \forall x \in \cX,\; \forall T \in \integ,
\end{equation*}

is hence strongly optimal in both the optimal prediction and the prescription problems.

In the exponential regime, $a_T\sim rT$, $r>0$, we extend results in [Van Parys et al., 2020] to our more general setting and show that the DRO formulation (<ref>) with KL ambiguity set is strongly optimal in both the optimal prediction and prescription problems even when allowed to explicitly depend of the data size. This implies that consistency is impossible in both the exponential and superexponential regime, and imposing such out-of-sample guarantees yields rather conservative predictors.

Although perhaps similar at first glance to the other two regimes, the subexponential regime is more sophisticated and requires a much finer analysis. In the subexponential regime, $a_T\ll T$, we prove that the SVP formulation of [Maurer and Pontil, 2009] with cost

\begin{equation*}
\hat{c}(x,\hat{\Pb}_T,T)
c (x,\hat{\Pb}_T)
\sqrt{\frac{2a_T}{T}\Var_{\hat{\Pb}_T}(\loss(x, \xi))},
\quad \forall x \in \cX,\; \forall T \in \integ,
\end{equation*}

is strongly optimal in both the optimal prediction and prescription problems. We further prove that SVP enjoys a DRO interpretation with ellipsoid uncertainty or Pearson $\chi^2$-divergence set
$\mathcal{U}_T(\hat{\Pb}_T) = \{\Pb'\in \cP :\sum_{i\in \Sigma} (\Pb'(i)-\hat{\Pb}_T(i))^2/(2\hat{\Pb}_T(i))\leq {a_T}/{T}\}$. An interesting insight is that this ambiguity set can be identified with the second order term in the Taylor expansion of the KL-divergence ambiguity set of (<ref>) when $ \Pb' \approx \hat{\Pb}_T$ and  $r = a_T/T$.

We hence show the existence of three distinct out-of-sample performance regimes between which the nature of the optimal data-driven formulation, for the purpose of decision-making and machine learning, experiences a phase transition.
The optimal data-driven formulations can be interpreted as a classical robust formulation in the superexponential regime, a distributionally robust formulation in the exponential regime and finally a variance penalized formulation in the subexponential regime; see also Table <ref>.
This final observation unveils a surprising connection between these three, at first glance seemingly unrelated, data-driven formulations which until now remained hidden.

OOS Guarantee
$a_T \gg T$
$a_T \sim rT$
$a_T \ll T$

Ambiguity Set

$\Pb' : \displaystyle\sum_{i\in \Sigma} \hat{\Pb}_T(i) \log \left( \frac{\hat{\Pb}_T(i)}{\Pb'(i)} \right)\leq r$
$\Pb' :  \displaystyle \sum_{i\in \Sigma} \frac{(\Pb'(i)-\hat{\Pb}_T(i))^2}{2\hat{\Pb}_T(i)}
\leq
\frac{a_T}{T}$

Summary of the optimal predictors for the three out-of-sample guarantee regimes.

§.§ Further Related Work

The study of optimal estimation has a long and distinguished history in statistics [Lehmann and Casella, 2006]. However, literature on “optimization aware” optimal estimation is considerably shorter.

Adopting a Bayesian perspective, Gupta, 2019 determines the smallest convex ambiguity sets that contain the unknown data-generating distribution with a prescribed level of confidence as the sample size increases. Both the Pearson divergence and relative entropy ambiguity sets with properly scaled radii are optimal in this setting. Gupta, 2019 however restricts attention to the subclass of distributionally robust predictors with convex ambiguity sets whereas here a much richer class of predictors is considered. Lam, 2019 also seeks distributionally robust predictors which trade conservatism for out-of-sample performance. Lam, 2019 studies in particular the probability that the estimated expected cost function dominates the actual expected cost function uniformly across all decisions, and he calls a predictor optimal if this probability is asymptotically equal to a prescribed confidence level. Using the empirical likelihood theorem of Owen, 1988, he shows that Pearson divergence and relative entropy ambiguity sets with properly scaled radii are optimal in this sense.

Perhaps the work most closely related to ours is [Van Parys et al., 2020] in which the framework of optimal predictors and prescriptors which we employ was first introduced. Sutter et al., 2020 generalize this framework to allow for data generating processes which may exhibit dependence over time such as Markov chains and auto-regressive models. However, in both works only the exponential regime ($a_T \sim rT$) as defined earlier is considered. Consequently, the resulting optimal formulations are necessarily all conservatively biased. Technically, many of the results in this line of work rely quite heavily on the mathematical machinery of large deviation theory [Zeitouni and Dembo, 1998] which has proven very useful also in several related fields such as control [Jongeneel et al., 2021, Jongeneel et al., 2021] and queuing theory [Puhalskii and Vladimirov, 2007].

Notations $\Re_+$ and $\integ$ denote respectively the set of non-negative real numbers and the set of positive integers. We denote by $\|\cdot\|_{\infty}$ the infinity norm and $\|\cdot\|$ the euclidean norm. For a function of two variables $f$ on a set $\mathcal{Y}\times \mathcal{Z}$ and $y \in \mathcal{Y}$, we denote by $f(y,\cdot)$ the induced function on $\mathcal{Z}$ by fixing the first argument to $y$. The notation generalizes to functions of multiple variables, on each of their coordinates. Finally, for a given set $\Gamma$, we denote its complement by $\Gamma^c$, its closure by $\bar{\Gamma}$ and its interior by $\Gamma^{\into}$.

§ OPTIMAL DATA-DRIVEN PREDICTION

We study in this section the problem of optimal prediction as formally stated in problem (<ref>). We first indicate with the help of a small counterexample that among the set of all possible predictors as defined in Definition <ref> there exists some pathological predictors, of no practical significance, which might prevent the existence of optimal solutions.

Consider the example illustrated in Figure <ref> where we assume the existence of an optimal predictor $\hat{c}$.
We can derive another predictor $\hat c'$ by subtracting a spike function that vanishes to $0$ on $\{\frac{0}{T}, \frac{1}{T}, \ldots, \frac{T}{T}\}^d$. For all practical purposes hence both predictors are the same as both predict the same cost whatever the empirical distribution $\hat \Pb_T$. In particular, $\hat{c}'$ still verifies the out-of-sample guarantee as it only concerns its values in $\hat{\Pb}_T$. However, the predictor $\hat c'$ can be shown to be a strictly better predictor as quantified by the partial order $\orderleq$.

Such discussed pathological predictors are possible as there is no explicit restriction on the smoothness of the predictors. For instance, in the example of Figure <ref>, the spike that needs to be added has variations that explode with large $T$.
To avoid such pathological predictors, we will consider exclusively regular predictors.

The set of regular predictors $\cC$ is the set of predictors verifying verifying the following two properties[We recall the definition of these properties in Definition <ref> and <ref>.]:

* The sequence of functions $(\hat{c}(\cdot,\cdot,T))_{T\geq 1}$ is uniformly bounded and equicontinuous.

* The function $\hat{c}(\cdot,\cdot,T)$ is differentiable in the second argument $\Pb$ for all $T \in \mathbf{N}$. Furthermore, the sequence of its derivatives is uniformly bounded and equicontinuous.

The differentiability of regular predictors in $\Pb$ is without much loss of generality as the predictor is in essence characterized completely by the values it takes on the discrete support $\{\frac{0}{T},\frac{1}{T}, \ldots,\frac{T}{T}\}^d$. Any non-differentiable predictor can therefore always be substituted by an equivalent predictor that is differentiable by smoothly extending its values from $\{\frac{0}{T},\frac{1}{T}, \ldots,\frac{T}{T}\}^d$ to $\cP$.
The fact that regular predictors should be bounded is also natural in this context as we assume here that the unknown actual cost $c(x, \Pb) < \infty$ remains bounded. The equicontinuity and the uniform boundedness of derivatives condition is precisely what allows us to avoid the pathological asymptotic behaviors of sequences of functions constituting predictors. We will show the existence
of an optimal predictor among the class of regular predictors in each of the three regimes discussed in Section <ref>.

Illustration of the construction of a pathological predictor dominating a given predictor. The solid line represents the regular predictor $\hat{c}$, while the dashed line represents the perturbed predictor into a pathological predictor $\hat{c}'$.
Here $i\in \Sigma$, $k\in \{0,\ldots,T\}$ is an integer, and the pointed vertical lines represent the possible values of the empirical distribution $\hat{\Pb}_T(i) \in \{\frac{0}{T}, \ldots, \frac{T}{T}\}$.

§.§ The Exponential Regime ($a_T\sim rT$)

We say that the prediction problem is in the exponential regime when the desired out-of-sample disappointment speed satisfies $a_T\sim rT$, i.e., $\lim_{T\to\infty} a_T/T = r > 0$.
That is, admissible predictors can suffer an out-of-sample disappointment probability as defined in Equation (<ref>) which decays exponentially at rate $r$ with increasing amount $T$ of observed data points.

In this exponential regime the appropriate distance notion between distributions seems to be the relative entropy sometimes also better known as the KL-divergence.
The relative entropy of a distribution $\Pb\in\cP$ with respect to a distribution $\Pb'\in\cP$ is defined as

\begin{align}\label{eq: KL divergence.}
\D{\Pb}{\Pb'} = \sum_{i\in\Sigma} \Pb(i) \log\left(\frac{\Pb(i)}{\Pb'(i)}\right),
\end{align}

where we use the conventions $0 \log(0/p)=0$ for any $p\geq 0$ and $p' \log(p'/0)=\infty$ for any $p'> 0$. We can define an associated DRO predictor as

\begin{equation}\label{eq: KL predictor}
\cKL(x,\Pb,T)
\sup_{\Pb' \in \cP} \set{c(x,\Pb')}{\D{\Pb} {\Pb'}\leq r},
\quad \forall x \in \cX, \; \forall \Pb \in \cP, \; \forall T \in \integ.
\end{equation}

[Van Parys et al., 2020] have shown indeed that in the exponential regime this DRO predictor should be preferred to any other predictor which does not explicitely depend on data size $T$. We generalize this result and show that in fact it should be preferred to any other regular predictor. The key component of the proofs establishing this claim is the large deviation property of our the empirical distribution $\hat{\Pb}_T$ which we review in Appendix <ref> for completeness.

We first prove that the DRO predictor is in fact regular and enjoys our imposed out-of-sample guarantee.
The full proof of the subsequent result is deferred to Appendix <ref>.

The predictor $\cKL\in \cC$ verifies the out-of-sample guarantee (<ref>) when $a_T \sim rT$.

Let $x,\Pb \in \cX\times \cPin$. Denoting $\Gamma = \set{\Pb' \in \mathcal{P}}{I(\Pb',\Pb) > r}$, we have by definition of $\cKL$, for all $T\in \integ$

\[
\hat{\Pb}_T \not \in \Gamma \implies c(x,\Pb) \leq \cKL(x,\hat{\Pb}_T,T).
\]

Hence, using the Large Deviation Principle, Theorem <ref>, we get

\begin{align*}
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
c(x,\Pb) > \cKL(x,\hat{\Pb}_T,T)
\right)
\leq&
\limsup_{T\to\infty}
\frac{1}{rT} \log \Pb^{\infty}
\left(
\hat{\Pb}_T \in \Gamma
\right)
\leq -\frac{1}{r}\inf_{\Pb'\in \bar{\Gamma}}
\end{align*}

Finally, using the convexity of the relative entropy $I(\cdot,\cdot)$ we show that $\overline{\Gamma}  \subset \set{\Pb' \in \mathcal{P}}{I(\Pb',\Pb) \geq r}$ and therefore $-\inf_{\Pb'\in \bar{\Gamma}}
I(\Pb',\Pb) \leq -r$.

To prove the regularity of $\cKL$, we show its differentiability by rewriting $\cKL$ in a dual form as

\begin{equation*}
\cKL(x,\mb P, T)= \min_{\alpha\geq \max_{i\in \Sigma} \ell(x, i)} ~\{f(\alpha; x,\Pb, T)\defn \alpha - e^{-r} \exp(\textstyle\sum_{i\in \Sigma} \log \left(\alpha-\loss(x, i) \right) {\mb P(i)})\}
\end{equation*}

and subsequently use the implicit function theorem. The equicontinuity  property holds then simply as the predictor does not depend on $T$.

We now show that the proposed predictor is strongly optimal in the optimal predictor Problem (<ref>) and consequently should be preferred to any other regular predictor in the exponential regime.

Consider the exponential regime in which $a_T\sim rT$. The predictor $\cKL$ is feasible in the prediction problem (<ref>) and
for any predictor $\hat{c} \in \cC$ satisfying the out-of-sample guarantee (<ref>), we have $\cKL \orderleq \hat{c}$. That is, $\cKL$ is a strongly optimal predictor in the exponential regime.

Proposition <ref> ensures feasiblity.
Assume that $\cKL$ is not strongly optimal. Then, there must exist a predictor $\hat{c}\in \cC$ verifying the out-of-sample guarantee (<ref>) and $x_0,\Pb_0 \in \cX \times \cPin$ such that

\begin{equation}\label{proof eq: dro ineq 1}
\limsup_{T\to \infty} \frac{|\cKL(x_0,\Pb_0,T)-c(x_0,\Pb_0)|}{|\hat{c}(x_0,\Pb_0,T)-c(x_0,\Pb_0)|} > 1
\end{equation}

with the convention $\frac{0}{0} =1$. From the definition of superior limit there must exist an increasing sequence $(t_T)_{T\geq 1} \in \integ^{\integ}$ and $\varepsilon>0$ such that

\begin{equation}\label{proof eq: dro ineq 2}
|\cKL(x_0,\Pb_0,t_T)-c(x_0,\Pb_0)| \geq (1+\varepsilon)|\hat{c}(x_0,\Pb_0,t_T)-c(x_0,\Pb_0)|, \quad \forall T \in \integ.
\end{equation}

Let $\bar{\Pb} \in \argmax_{\Pb'\in\cP} \{c(x_0,\Pb') \; : \; I(\Pb_0,\Pb') \leq r\}$ which exists as $\cP$ is compact and $\Pb'\mapsto I(\Pb_0,\Pb')$ lower semicontinuous. We have $\cKL(x_0,\Pb_0,T) = c(x_0,\bar{\Pb})$ for all $T\in \integ$ and $I(\Pb_0,\bar{\Pb}) \leq r$. Using this equality in inequality (<ref>) and the fact that $c(x_0,\bar{\Pb}) \geq c(x_0,\Pb_0)$ by definition of $\bar{\Pb}$, we get

\begin{equation}\label{proof eq: dro ineq 3}
c(x_0,\bar{\Pb}) \geq \hat{c}(x_0,\Pb_0,t_T) + \varepsilon |\hat{c}(x_0,\Pb_0,t_T) - c(x_0,\Pb_0)|,
\quad \forall T \in \integ.
\end{equation}

We use this inequality to prove successively the following claims.

There exists $\varepsilon_1>0$ and $(l_T)_{T\geq 1} \in \integ^{\integ}$ such that $c(x_0,\bar{\Pb}) \geq \hat{c}(x_0,\Pb_0,l_T) + \varepsilon_1$, for all $T\in \integ$.

There exists $\bar{\Pb}_1 \in \cPin$ verifying $I(\Pb_0,\bar{\Pb}_1)<r$, and an open set $U \subset \cPin$ containing $\Pb_0$ such that for all $\Pb'\in U$ and $T \in \integ$, we have $c(x_0,\bar{\Pb}_1) > \hat{c}(x_0,\Pb', l_T)$.

We defer their proofs to Appendix <ref>. The proof of the second claim uses the continuity of $c$ and equicontinuity of $\hat{c}$ to perturb $\bar{\Pb} \in \cP$ into $\bar{\Pb}_1 \in \cPin$ verifying $I(\Pb_0,\bar{\Pb}_1)<r$, and $\Pb_0$ into an open neighborhood $U$, while only losing a gap less than $\varepsilon_1$ in the inequality of the first claim.
Using Claim <ref> and then the Large Deviation Principle (Theorem <ref>) we get

\begin{align*}
\limsup_{T\to\infty} \frac{1}{rT} \log \bar{\Pb}_1^\infty \left( c(x_0, \bar{\Pb}_1) > \hat c(x_0, \hat{\Pb}_T,T)\right)
\limsup_{T\to\infty} \frac{1}{rl_T} \log \Pb_1^\infty
\left(
\hat{\Pb}_{l_T} \in U
\right) \\
& \geq
\liminf_{T\to\infty} \frac{1}{rT} \log \Pb_1^\infty
\left(
\hat{\Pb}_{T} \in U
\right)\\
- \frac{1}{r}\inf_{\Pb' \in U^{\into}}I(\Pb',\Pb_1)
\geq - \frac{1}{r}I(\Pb_0,\bar{\Pb}_1) > -1
\end{align*}

where the last two inequalities use $\Pb_0 \in U^{\into}$ and $I(\Pb_0,\bar{\Pb}_1)<r$ from Claim <ref>. This inequality contradicts the feasibility of $\hat{c}$ as it does not verify the out-of-sample guarantee (<ref>), which completes the proof.

The proof of strong optimality in the exponential regime does not require differentiability and equicontinuity of the derivatives of the predictors. In fact, the optimality results in the exponential (and superexponential) regimes hold even when the considered set of predictors are predictors verifying only the first but not necessarily the second regularity condition in Definition <ref>.

Theorem <ref> establishes that consistent estimator for which $\lim_{T\to\infty} \hat c(x, \Pb, T) = c(x, \Pb)$ are not compatible with the exponential regime. That is, even the optimal predictor in this regime is typically biased in that we may have $\lim_{T\to\infty} \cKL(x, \Pb, T) > c(x, \Pb)$. This is undesirable as we may hope to recover the unknown cost at least when an increasing amount of data becomes available [Bertsimas et al., 2018]. We can attribute this undesirable outcome by our insistence on imposing an exponentially decaying out-of-sample disappointment as we will show later. We first show however that imposing even stronger out-of-sample guarantees – perhaps unsurprisingly – does not alleviate this issue.

§.§ The Superexponential Regime ($a_T \gg T$)

We consider now the superexponential regime, in which the desired out-of-sample guarantee speed is stronger than exponential, $a_T\gg T$, i.e., $\lim_{T\to\infty} a_T/T = \infty$.
This implies that admissible predictors suffer an out-of-sample disappointment probability which decays faster than exponential in the number of samples $T$. We will show that we can not escape fully conservative predictors with such strong guarantees.

Consider a robust predictor taking the worst case scenario of the uncertainty

\begin{equation}\label{eq: overly robust predictor}
\hat{c}_{R}(x,\Pb,T)
\max_{i\in \Sigma} \,\ell(x,i),
\quad \forall x \in \cX, \; \forall \Pb \in \cP.
\end{equation}

The previous predictor can also be seen as a DRO predictor with the whole simplex $\cP$ as ambiguity set, $\hat{c}_{R}(x,\Pb,T) = \sup_{\Pb' \in \cP} c(x,\Pb')$ for all $x,\Pb$ and $T$.
We remark that this predictor does not actually use the observed data at all and only depends on the support of its potential outcomes instead. We first prove that this robust predictor is indeed regular and enjoys our imposed out-of-sample guarantee.

The predictor $\cRob\in \cC$ verifies the out-of-sample guarantee (<ref>) when $a_T \gg T$.

The predictor $\cRob$ is constant in $\Pb$ and $T$. Therefore, the required regularity conditions follow immediately and $\cRob \in \cC$. Let us now verify the out-of-sample guarantee. Let $(x,\Pb) \in \cX \times \cP$. We have $\hat{c}_{R}(x,\Pb,T) = \sup_{\Pb' \in \cP} c(x,\Pb')$ for all $T\in \integ$, therefore, $\Pb^\infty ( c(x, \Pb) > \hat{c}_{R}(x, \hat{\Pb}_T,T)) =0$ for all $T\in \integ$.

Consider the superexponential regime in which $a_T \gg T$. The predictor $\cRob$ is feasible in the prediction problem (<ref>) and
for any predictor $\hat{c} \in \cC$ satisfying the out-of-sample guarantee (<ref>), we have $\cRob \orderleq \hat{c}$. That is, $\cRob$ is a strongly optimal predictor in the superexponential regime.

We present two proofs of this theorem. The first one, which we sketch next and can be found in Appendix <ref>, shows that it is essentially implied by Theorem <ref>. The second one, in Appendix <ref>, is a self contained proof that does not require Theorem <ref>.

Proposition <ref> ensures the feasibility of $\cRob$. Let $\hat{c}\in \cC$ be a feasible predictor in Problem (<ref>) with $a_T\gg T$. Notice that $\hat{c}$ is also feasible for $a_T \sim rT$, for all $r>0$. In fact, verifying a guarantee with a given speed implies verifying all weaker guarantees. Hence Theorem <ref> implies that $\cKL \preceq_{\cC} \hat{c}$, for $\cKL$ with an ambiguity set with any $r>0$. The ambiguity set of $\cKL$, $\{\Pb'\in \cP\; : \; \D{\Pb} {\Pb'}\leq r\}$ “converges" with $r\to \infty$ to $\cP$ which is the ambiguity set of $\cRob$. Hence, intuitively, taking $r\to \infty$ in the inequality $\cKL \preceq_{\cC} \hat{c}$ leads to $\cRob \preceq_{\cC} \hat{c}$.

The optimality of the robust predictor shows that for a predictor to satisfy superexponential out-of-sample performance guarantees, it necessarily needs to hedge against all possible distributions of the uncertainty. That is, it needs to take into account the worst-case cost in all scenarios which is independent of the data observed.

The presented optimality results in the exponential and superexponential regimes reveal an interesting insight. In both regimes, the optimal predictors are not consistent. That is, they do not converge to the true cost with increasing data size $T$. This shows that when exponential or stronger guarantees are imposed, consistent data-driven formulations are not possible. In other words, predictors must necessarily remain conservatively biased even when the amount of available data is large.

§.§ The Subexponential Regime ($a_T \ll T$)

We study now the subexponential regime in which the desired out-of-sample guarantee speed is slower than exponential, $a_T\ll T$, i.e., $\lim_{T\to\infty} a_T/T = 0$.
Admissible predictors may suffer an out-of-sample disappointment probability which decays to zero slower than exponential in the number of samples $T$. While consistent predictors were not possible in the previous exponential and superexponential regimes, we will observe a phase transition when moving into the subexponential regime. Because of the weaker requirements imposed on the out-of-sample performance, we will show that consistent predictors are not only a possibility but a necessity for optimality. The next result indeed indicates that, in the subexponential regime, any weakly optimal predictor in Problem (<ref>) must necessarily be consistent.

Consider the subexponential regime in which $a_T\ll T$. Every weakly optimal predictor in the optimal prediction Problem (<ref>) is consistent. That is, for every predictor $\hat{c}\in \cC$ verifying the out-of-sample guarantee (<ref>), either $(\hat{c}(\cdot,\cdot,T))_{T\geq1}$ converges point-wise to $c(\cdot,\cdot)$, i.e.,

\lim_{T\to\infty} \hat{c}(x,\Pb,T) = c(x,\Pb), \quad \forall x\in \cX, \; \forall \Pb \in \cP,

or there exists a predictor $\hat{c}'\in \cC$ verifying the out-of-sample guarantee that is strictly preferred to $\hat{c}$, i.e., $\hat{c}' \orderleq \hat{c}$ and $\hat{c}' \not\equiv \hat{c}$.

Suppose that there exists a predictor $\hat{c} \in \cC$ which satisfies the out-of-sample guarantee and does not converge point-wise to $c$.
We first show that non-consistency combined with equicontinuity (as $\hat{c} \in \cC$) implies that the predictor is larger than the true cost by a constant gap in an open ball for an infinite number of $T$: there exists $\epsilon>0$, a ball of center $(x_0,\Pb_0)$ and radius $\rho>0$, $\mathcal{B}((x_0,\Pb_0),\rho)$, and an infinite set $\mathcal{T} \subset \integ$ such that

\begin{equation*}
\forall T \in \mathcal{T}, \;
\forall (x,\Pb) \in \mathcal{B}((x_0,\Pb_0),\rho), \quad
\hat{c}(x_0,\Pb_0,T) - c(x_0,\Pb_0) > \frac{\varepsilon}{4}
\end{equation*}

We next show, using the Moderate Deviation Principle, Theorem <ref>, that it suffices to have a constant gap with the true cost to verify subexponential guarantees. We seek, therefore, to perturb $\hat{c}$ in the ball $\mathcal{B}((x_0,\Pb_0),\rho)$ into a strictly preferred predictor while ensuring to maintain a constant gap with the true cost. We consider $\eta: \cX \times \cP \longrightarrow [0,\frac{\varepsilon}{8}]$ an infinitely differentiable bump function of support $\mathcal{B}((x_0,\Pb_0),\frac{\rho}{2})$ such that $\eta(x_0,\Pb_0) = \frac{\varepsilon}{8}$ and perturb $\hat{c}$ into $\hat{c}'$ defined as $\hat{c}'(x,\Pb,T) = \hat{c}(x,\Pb,T) - \eta(x,\Pb) \mathbf{1}_{T \in \mathcal{T}}$. Figure <ref> illustrates this construction. Note that it is crucial that $\eta$ is independent of $T$|and more precicely has variations not exploding with $T$|as otherwise $\hat{c}'$ might not preserve the necessary regularity of $\hat{c}$. Non-consistency, combined with equicontinuity provides a sufficient gap with the true cost $c$ to substract a bump function independent of $T$ while preserving a constant gap.

Illustration of the construction of $\hat{c}' \preceq_{\cC} \hat{c}$ and $\hat{c}' \not\equiv \hat{c}$ when $\hat{c}$ is not consistent.

Notice that consistency in the sense of Proposition <ref> implies consistency of the estimator $(\hat{c}(x,\hat{\Pb}_T,T))_{T\geq 1}$ of the true cost $c(x,\Pb) = \Eb_{\Pb}(\loss(x,\xi))$, for each $x\in \cX$ and $\Pb \in \cP$. In fact, point-wise convergence of $(\hat{c}(x,\cdot,T))_{T\geq 1}$ with the equicontinuity of $\hat{c}$ (as $\hat{c} \in \cC$) implies its uniform convergence. Combined with the almost sure convergence of $(\hat{\Pb}_T)_{T\geq 1}$ to $\Pb$, a consequence of the strong law large numbers, it implies almost sure convergence of $(\hat{c}(x,\hat{\Pb}_T,T))_{T\geq 1}$ to $c(x,\Pb)$.

We will show that a strongly optimal solution to the optimal prediction Problem (<ref>) exists also in the subexponential regime. Consider the sample variance penalization (SVP) predictor defined as

\begin{equation}\label{eq: Robust predictor SVP.}
\cSVP(x,{\mb P},T)
c (x,\Pb)
\sqrt{\frac{2a_T}{T}\Var_{\Pb}(\loss(x, \xi))},
\quad \forall x \in \cX, \; \forall \Pb \in \cP,\; \forall T \in \integ,
\end{equation}

where $\Var_{\Pb}(\loss(x, \xi)) := \mathbb E_{\Pb}((\loss(x, \xi) - \mathbb E_{ \Pb}(\loss(x, \xi)) )^2)$ is the variance of the cost under distribution $\Pb$.
SVP predictors were considered previously by [Maurer and Pontil, 2009] as an alternative to naive ERM. Their consideration of SVP may be understood through the perspective of a classical “bias-variance” trade-off between minimizing an empirical risk and a variance-sensitive regularization term motivated by concentration inequalities such as the one found in Equation (<ref>). We will show that also in our framework the SVP predictor will play a protagonist role in the subexponential regime.

For all $\Pb \in \cP$ consider the local ellipsoid norm associated to $\Pb$

\begin{equation*}
\|\Delta\|_{\Pb}^2 := \frac{1}{2} \sum_{i\in \Sigma} \frac{1}{\Pb(i)}\Delta_i^2, \quad \forall \Delta \in \Re^d.
\end{equation*}

Whereas the KL divergence $I(\Pb', \Pb)$ has been shown to be the right notion of distance in the exponential regime between distributions, we will indicate that the local ellipsoidal norm or $\chi^2$-divergence induces the right notion of distance $\Pb' \rightarrow \|\Pb'-\Pb\|_{\Pb}$ in the subexponential regime. We first indicate that the SVP predictor can alternatively be understood as a DRO predictor with ellipsoid uncertainty set. This alternative perspective will also shed light on key properties of SVP such as the tractability of its associated prescription problem which we discuss in Section <ref>. The proof of the next result is deferred to Appendix <ref>.

For all $x, \Pb\in \mathcal{X}\times \cPin$ and $T \in \integ$ sufficiently large such that $\sqrt{2a_T/T} \leq \min_{i\in \Sigma}\Pb(i) \min_{i\in \Sigma} \min(\Pb(i),1-\Pb(i))$, the robust predictor (<ref>) can be written as

\begin{equation}\label{eq: robust predictor DRO.}
\cSVP(x,{\mb P},T) = \sup_{\Pb' \in \mathcal{P}}
\left\{
c(x,\Pb')\; : \;
\norm{\Pb'-\Pb}^2_\Pb
\leq
\frac{a_T}{T}
\right\},
\end{equation}

The supremum in (<ref>) is in fact attained, i.e.,

\[
\cSVP(x,{\mb P},T) = c(x, \Pb + \sqrt{2a_T/T}\varphi_x(\Pb)) \quad {\rm{for}} \quad \varphi_x(\Pb) := {(\loss(x,\cdot) \odot \Pb - c(x,\Pb)\Pb)}/{\sqrt{\Var_{\Pb}(\loss(x,\xi))}}.
\]

where $\loss(x,\cdot) = (\loss(x,1),\ldots,\loss(x,d))$, $\odot$ denotes the Hadamard product and when $\Var_{\Pb}(\loss(x,\xi))=0$, $\varphi_x(\Pb)$ is taken by convention as any vector in the boundary of[Take for example the vector $\sqrt{\frac{2\Pb(1)}{1-\Pb(1)}}(e_1 - \Pb)$ where $e_1= (1,0,\ldots,0)^\top$.] $\{\Delta \in \Re^d\; : \; e^\top \Delta =0, \; 2\|\Delta\|_{\Pb}^2\leq a_T/T\}$.
Moreover, $\varphi_x(\Pb)$ verifies the identities $\|\sqrt{2}\varphi_x(\Pb)\|_{\Pb} =1$ and $c(x,\varphi_x(\Pb)) = \sqrt{\Var_{\Pb}(\loss(x,\xi))}$ for all $\Pb \in \cPin$.

The underlying optimization problem of the DRO form (<ref>) is a linear optimization in the intersection of the simplex $\cP$ and an ellipsoid. The condition of the proposition corresponds to $T$ such that the projection of the ellipsoid on the hyperplane supporting the simplex is contained in the simplex. We show that when such an inclusion is verified, the linear optimization problem can be solved explicitly and gives exactly the SVP form (<ref>).

Illustration of the DRO expression of the robust predictor in the subexponential regime. The shrinking ellipsoids around the blue points represent the ambiguity set of (<ref>) around $\hat{\Pb}_T$ for increasing values of $T$. The arrow gives the cost at the pointed distribution, attaining the maximum cost in the ellipsoid.

Intuitively, the DRO perspective shows that given the observed empirical distribution $\hat{\Pb}_T$, the SVP predictor guards against all distribution in the ellipsoidal ambiguity set $\{ \Pb'\in \cP \; : \; \|\Pb'-\hat{\Pb}_T\|^2_{\hat{\Pb}_T}
\leq
a_T/T \}$ when the imposed out-of-sample disappointment (<ref>) is of order $e^{-a_T}$.
Proposition <ref> identifies the distribution $\hat{\Pb}_T + \sqrt{2a_T/T}\varphi_x(\hat{\Pb}_T)$ as the worst-case probability distribution which is still sufficiently likely to have generated the data.
Figure <ref> illustrates this perspective.

We now show that the SVP predictor $\cSVP$ is strongly optimal in the optimal prediction Problem (<ref>) in the subexponential regime. We first show that the predictor $\cSVP$ has the desired regularities of predictors (Definition <ref>). We defer the proof to Appendix <ref>.

The predictor $\cSVP \in \cC$ is regular, i.e., $\cSVP$ verifies the regularity conditions of predictors (Definition <ref>).

We next show that SVP satisfied the desired out-of-sample guarantee (<ref>). We note that existing finite sample guarantees, c.f., <cit.> and <cit.> and Proposition <ref> in this paper, do not directly imply the desired asymptotic guarantee (<ref>) for SVP. A finer analysis will hence be required. Interestingly, our proof uses completely different techniques than [Maurer and Pontil, 2009] and [Audibert et al., 2009].
While their proofs rely on concentration inequalities on the empirical standard deviation, our proof uses the DRO form (<ref>) of SVP combined with the Moderate Deviation Principle (Theorem <ref>) from Large Deviation Theory.

The predictor $\cSVP\in \cC$ verifies the out-of-sample guarantee (<ref>) when $a_T \ll T$.

Let $\Pb \in \cPin$ and $x \in \mathcal{X}$. Let $T_0 \in \integ$ be such that for all $T\geq T_0$ the DRO form (<ref>) of $\cSVP$ holds. Observe that (<ref>) implies that for all $T\geq T_0$

\[
\hat{\Pb}_T \in E_T :=\set{\Pb' \in \mathcal{P}}{\norm{\Pb-\Pb'}^2_{\Pb'}\leq \frac{a_T}{T}} \implies c(x,\Pb) \leq \cSVP(x,\hat{\Pb}_T,T).
\]

Hence, we have

\begin{align*}
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
c(x,\Pb) > \cSVP(x,\hat{\Pb}_T,T)
\right)
\leq&
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
\hat{\Pb}_T \not\in E_T
\right)\\
\leq & \limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
\hat{\Pb}_T - \Pb \in \sqrt{ \frac{a_T}{T}}\Gamma_T
\right)
\end{align*}

where $\Gamma_T := \sqrt{T/a_T} (E_T^c -\Pb) = \{\Delta \in \sqrt{T/a_T} \mathcal{P}_0(\Pb) : \norm{\Delta}^2_{\Pb+\Delta\sqrt{a_T/T}}>1\}$, $\mathcal{P}_0(\Pb) = \set{\Pb - \Pb'}{\Pb' \in \mathcal{P}}$.
The goal now is to apply an MDP (Theorem <ref>). In other to do that, we need to analyse the asymptotic behavior of the sequence of sets $\Gamma_T$.
We show in the following claim that it converges in a precise sense to $\Gamma := \set{\Delta \in \mathcal{P}_{0,\infty}}{\norm{\Delta}^2_{\Pb}\geq 1}$ where $\mathcal{P}_{0,\infty}:= \{ \Delta \in \Re^d\; : \; e^\top \Delta =0 \}$ is the hyperplane containing differences of distributions.

There exists a sequences $(\varepsilon_T)_{T\geq 1}\in \Re^{\integ}_+$ decreasing to $0$ and $T_1\in \integ$ such that $\sqrt{1+\varepsilon_T}\Gamma \subset \Gamma_T \subset \sqrt{1-\varepsilon_T}\Gamma$ for all $T \geq T_1$.

See Appendix <ref>.

Let $(\varepsilon_T)_{T\geq 1}$ and $T_1$ given by Claim <ref>. We have $\Gamma_T \subset \sqrt{1-\varepsilon_T}\Gamma$ for all $T \geq \max(T_0,T_1)$.
Hence, using the MDP, Theorem <ref>, we have for all $t \geq \max(T_0,T_1)$

\begin{align*}
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
c(x,\Pb) > \cSVP(x,\hat{\Pb}_T,T)
\right)
\leq & \limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
\hat{\Pb}_T - \Pb \in \sqrt{\frac{a_T}{T}}\Gamma_{t}
\right) \\
\leq& -\inf_{\Delta\in \bar\Gamma_{t}}\norm{\Delta}^2_{\Pb}
= -(1-\varepsilon_t) \inf_{\Delta\in \bar\Gamma}\norm{\Delta}^2_{\Pb}
= -(1-\varepsilon_t)
\end{align*}

\(
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^{\infty}
\left(
c(x,\Pb) > \cSVP(x,\hat{\Pb}_T,T)
\right)
\leq -1.
\)

We now prove that the SVP predictor (<ref>) is preferred to any other predictor verifying the out-of-sample guarantee in the subexponential regime establishing therefore strong optimality.

Consider the subexponential regime in which $a_T\ll T$. The predictor $\cSVP$ is feasible in the prediction problem (<ref>) and
for any predictor $\hat{c} \in \cC$ satisfying the out-of-sample guarantee (<ref>), we have $\cSVP \orderleq \hat{c}$. That is, $\cSVP$ is a strongly optimal predictor in the subexponential regime.

To prove Theorem <ref>, we show that in order to verify an out-of-sample guarantee with speed $(a_T)_{T\geq1}$, a predictor must necessarily add a regularization to the empirical cost larger than $\sqrt{2a_T/T} \sqrt{\Var_{\Pb}(\loss(x,\xi))}$. This quantity is therefore a fundamental minimal amount of regularization for predictors with out-of-sample guarantee.
It also happens to be exactly the regularization added by the SVP predictor.

Let $\hat{c} \in \mathcal{C}$. If $\hat{c}$ is feasible in (<ref>) with $a_T \ll T$, then for all $x \in \mathcal{X}$, for all $\Pb \in \cPin$,

\begin{equation*}
\liminf_{T \to \infty} \sqrt{\frac{T}{a_T}}(\hat{c}(x,\Pb,T)-c(x,\Pb)) \geq \limsup_{T \to \infty} \sqrt{\frac{T}{a_T}}|\cSVP(x,\Pb,T)-c(x,\Pb)| = \sqrt{2\Var_{\Pb}(\loss(x, \xi))}.
\end{equation*}

Assume for the sake of contradiction that there exists $\hat{c} \in \mathcal{C}$ feasible in (<ref>) not verifying the result. There hence exists $(x_0, \Pb_0) \in \mathcal{X}\times \cPin$ such that

\liminf_{T \to \infty} \sqrt{\frac{T}{a_T}}(\hat{c}(x_0,\Pb_0,T)-c(x_0,\Pb_0)) <\limsup_{T \to \infty} \sqrt{\frac{T}{a_T}}|\cSVP(x_0,\Pb_0,T)-c(x_0,\Pb_0)|

We start the proof by showing in the following claim that this inequality extends to an open ball. This will allow us to examine $\hat{c}$ in an open neighborhood.
In what follows and throughout the proof $\alpha_T \defn 2a_T/T$ for all $T \in \integ$.

There exists $\Pb_1 \in \cPin$, $\varepsilon>0$, and an increasing sequence $(t_T)_{T\geq 1} \in \integ^\integ$, such that for all $\varepsilon'>0$, there exists an open ball $\mathcal{B}(\Pb_1,r)$ around $\Pb_1$ of radius $r>0$ such that

$$\hat{c}(x_0,\Pb,t_T) + \varepsilon \sqrt{\alpha_{t_T}}
\leq
\cSVP(x_0,\Pb,t_T)
+ \varepsilon' \|\Pb - \Pb_1\|,
\quad \forall \Pb \in \mathcal{B}(\Pb_1,r),\;
\forall T \in \integ

See Appendix <ref>.

Let $\Pb_1 \in \cPin$, $\varepsilon>0$, and $(t_T)_{T\geq 1} \in \integ^\integ$ given by Claim <ref>. In the reminder of the proof, we will show that the out-of-sample guarantee (<ref>) condition for $\hat{c}$ fails to hold at $(x_0,\Pb_1)$, which contradicts the feasibility of $\hat{c}$. We first construct key elements for the proof.
Set $\varepsilon'>0$ verifying
$\varepsilon' \leq \varepsilon/3$. Let $r>0$ given by Claim <ref> such that

\begin{equation}\label{eq: robustOpt: uniformoty ineq.}
\hat{c}(x_0,\Pb,t_T)
\leq
\cSVP(x_0,\Pb,t_T)
+ \varepsilon' \|\Pb - \Pb_1\|
-\varepsilon \sqrt{\alpha_{t_T}}
\quad \forall \Pb \in \mathcal{B}(\Pb_1,r),
\; \forall T \in \integ.
\end{equation}

Without loss of generality, we can chose $r<1$.

Denote $\varphi:= \varphi_{x_0}$ given by Proposition <ref>. The proposition ensures that $\norm{\sqrt{2}\varphi(\Pb_1)}_{\Pb_1}=1$, therefore $\norm{\varphi(\Pb_1)} \neq 0$.
Let $\eta \in (0,1)$ such that
$\eta \sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))}< \varepsilon/6$
and define

\{u \in \mathcal{P}_{0,\infty} \; : \; \|u\|<2 \|\varphi(\Pb_1)\|, \;
(1-\eta)c(x_0,u) - \sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))} > -\varepsilon/3\}.$$

The set $\Gamma$ is clearly open in $\mathcal{P}_{0,\infty} := \{\Delta \in \Re^d \; : \; e^\top \Delta =0\}$ and contains $\varphi(\Pb_1)$.
In fact, $(1-\eta)c(x_0,\varphi(\Pb_1))  = (1- \eta) \sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))} > \sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))} - \varepsilon/6$.
For $u \in \Gamma$, consider the sequence

$$\Pb_T(u) := \Pb_1 - (1-\eta)\sqrt{\alpha_T} \cdot u,$$

for all $T \in \integ$. See Figure <ref> for an illustration of this construction.

Illustration of the construction of $\Gamma$ and $\Pb_T(u)$, $u\in \Gamma$. $\Gamma$ is an open set of directions around $\varphi(\Pb_1)$. When $\eta =0$, the blue point represents the distribution $\Pb'_T:= \Pb_1 -\sqrt{\alpha_T} \varphi(\Pb_1)$ such that $ \cSVP(x_0,\Pb'_T,T) = c(x_0,\Pb_1)$.

Let $T_0 \in \integ$ such that for all $T\geq T_0$ the DRO expression of $\cSVP$ (Proposition <ref>) holds and  $\sqrt{\alpha_{t_T}} \leq r/ (2\|\varphi(\Pb_1)\|)$. The later condition ensures that for $T\geq T_0$ and $u \in \Gamma$, $\Pb_{t_T}(u) \in \mathcal{B}(\Pb_1,r)$, and therefore (<ref>) holds in $\Pb_{t_T}(u)$. We will show that $(\hat{c}(\cdot,\cdot,t_T))_{T\geq 1}$ always disappoints at $(x_0,\Pb_{t_T}(u))_{T\geq 1}$.  That is, $c(x_0,\Pb_1) > \hat{c}(x_0,\Pb_{t_T}(u),t_T)$, for all $T\geq T_0$ and $u\in \Gamma$. We then use the Moderate Deviation Principle, Theorem <ref>.

Let $T\geq T_0$ and $u \in \Gamma$. Let us examine the sign of $c(x_0,\Pb_1) - \hat{c}(x_0,\Pb_{t_T}(u),t_T)$. $\Pb_{t_T}(u)$ verifies (<ref>), therefore,

\begin{align}\label{eq: robustOpt: computations.}
c(x_0,\Pb_1) - \hat{c}(x_0,\Pb_{t_T}(u),t_T)
c(x_0,\Pb_1) - \cSVP(x_0,\Pb_{t_T}(u),t_T) + \varepsilon \sqrt{\alpha_{t_T}}
- \varepsilon' \|\Pb_{t_T}(u) - \Pb_1 \|.
\end{align}

We first analyse the term $c(x_0,\Pb_1) - \cSVP(x_0,\Pb_{t_T}(u),t_T)$. We have

\begin{align*}
c(x_0,\Pb_1) - \cSVP(x_0,\Pb_{t_T}(u),t_T)
c(x_0,\Pb_1) - c(x_0,\Pb_{t_T}(u))
- \sqrt{\alpha_{t_T}} \sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}
\\
c(x_0,\Pb_1-\Pb_{t_T}(u)) - \sqrt{\alpha_{t_T}} \sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}
\\
&= (1-\eta)\sqrt{\alpha_{t_T}}c(x_0,u) - \sqrt{\alpha_{t_T}} \sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}.
\end{align*}

Plugging this result in (<ref>) and using
$- \varepsilon' \|\Pb_{t_T}(u) - \Pb_1 \|
\geq
-\varepsilon'r \geq -\varepsilon'$, which results from $\Pb_{t_T}(u) \in \mathcal{B}(\Pb_1,r)$,
we get,

\begin{align*}
c(x_0,\Pb_1) - \hat{c}(x_0,\Pb_{t_T}(u),t_T)
\sqrt{\alpha_{t_T}} \bigg[(1-\eta)c(x_0,u)
- \sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}
+ \varepsilon
\bigg]\\
\sqrt{\alpha_{t_T}} \bigg[(1-\eta)c(x_0,u)
- \sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}
+ 2\varepsilon/3 \bigg]
\end{align*}

where the last inequality is by definition of $\varepsilon'$. As $\Pb_{t_T}(u)$ converges to $\Pb_1$, this inequality becomes

\begin{align*}
c(x_0,\Pb_1) - \hat{c}(x_0,\Pb_{t_T}(u),t_T)
\sqrt{\alpha_{t_T}}
\bigg[
- \sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))} +o(1)
\bigg] \\
\sqrt{\alpha_{t_T}}
\varepsilon/3 +o(1)
] >0
\end{align*}

where the last inequality is by definition of $\Gamma$.
This inequality is uniform in $u$ as
$u \in \Gamma \rightarrow\sqrt{\Var_{\Pb_{t_T}(u)}(\loss(x_0,\xi))}$ converges uniformly to the constant function equal to $\sqrt{\Var_{\Pb_1}(\loss(x_0,\xi))}$, therefore,
there exists $T_1>T_0$ such that

\begin{equation}\label{eq: main proof: disap in seq t_T.}
c(x_0,\Pb_1) > \hat{c}(x_0,\Pb_{t_T}(u),t_T),
\quad \forall T \geq T_1,
\; \forall u \in \Gamma.
\end{equation}

Denote $\mathcal{D}_T = \{\Pb'\; : \; c(x_0,\Pb_1)> \hat{c}(x_0,\Pb',T) \}$ the set of disappointing distributions at time $T$ when the true distribution is $\Pb_1$. The inequality (<ref>) implies that for all $T\geq T_1$,
$\Pb_1 -(1-\eta)\sqrt{\alpha_{t_T}} \Gamma \subset \mathcal{D}_{t_T}$.
We have therefore

\begin{align}
\limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( c(x, \Pb_1) > \hat c(x, \hat{\Pb}_T,T)\right)
\limsup_{T\to\infty} \frac{1}{a_T} \log \Pb^\infty \left( \hat{\Pb}_T \in \mathcal{D}_T\right) \nonumber\\
\limsup_{T\to\infty} \frac{1}{a_{t_T}} \log \Pb^\infty \left( \hat{\Pb}_{t_T} \in \mathcal{D}_{t_T}\right) \nonumber\\
&\geq \limsup_{T\to\infty} \frac{1}{a_{t_T}} \log \Pb^\infty \left( \hat{\Pb}_{t_T} - \Pb_1 \in -\sqrt{\alpha_{t_T}}(1-\eta) \sqrt{2}\Gamma\right) \nonumber \\
&= \limsup_{T\to\infty} \frac{1}{a_{t_T}} \log \Pb^\infty \left( \hat{\Pb}_{t_T} - \Pb_1 \in \sqrt{\frac{a_{t_T}}{t_T}}\cdot -(1-\eta) \sqrt{2}\Gamma\right) \nonumber\\
&\geq \liminf_{T\to\infty} \frac{1}{a_{T}} \log \Pb^\infty \left( \hat{\Pb}_{T} - \Pb_1 \in \sqrt{\frac{a_T}{T}}\cdot -(1-\eta) \sqrt{2}\Gamma\right)
\nonumber \\
&\geq - \inf_{\Delta \in \Gamma^{\into}} \|(1-\eta)\sqrt{2}\Delta\|_{\Pb_1}^2
\label{proof eq: series of ineq 3} \\
&\geq - (1-\eta)^2 \|\sqrt{2}\varphi(\Pb_1)\|_{\Pb_1}^2 =  - (1-\eta)^2 >-1
\label{proof eq: series of ineq 4}
\end{align}

where (<ref>) uses the Moderate Deviation principle (Theorem <ref>) and  (<ref>) is justified by $\varphi(\Pb_1) \in \Gamma = \Gamma^{\into}$ and $\|\sqrt{2}\varphi(\Pb_1)\|_{\Pb_1}=1$. This inequality contradicts the feasibility of $\hat{c}$ which completes the proof.

Let $\hat{c}\in \cC$ be a feasible predictor in the optimal prediction Problem (<ref>). Let $(x,\Pb) \in \cX \times \cPin$. The goal is to show that

\limsup_{T\to \infty} \frac{|\cSVP(x,\Pb,T)-c(x,\Pb)|}{|\hat{c}(x,\Pb,T)-c(x,\Pb)|} \leq 1.

It suffices to show that
for all sequence $(\beta_T)_{T\geq 1} \in \Re_+^{\integ}$ we have[This is actually equivalent to the desired result, see Lemma <ref>.]

\begin{equation*}
\limsup_{T\to\infty} \frac{1}{\beta_T} |\hat{c}(x,\Pb,T) - c(x,\Pb)| \geq \limsup_{T\to\infty} \frac{1}{\beta_T} |\cSVP(x,\Pb,T) - c(x,\Pb)|.
\end{equation*}

The result indeed follows with $\beta_T = |\hat{c}(x,\Pb,T)-c(x,\Pb)|$ for all $T$.
We distinguish two cases depending on whether $\Var_{\Pb}(\loss(x,\xi)) = 0$. If $\Var_{\Pb}(\loss(x,\xi)) = 0$, then  $\cSVP(x,\Pb,T) = c(x,\Pb)$ for all $T$ and therefore the desired inequality becomes trivial.

Suppose now $\Var_{\Pb}(\loss(x,\xi)) > 0$. Denote $\alpha_T = 2a_T/T$ for all $T$.
We have

\begin{equation*}
\limsup_{T\to\infty} \frac{1}{\beta_T} |\hat{c}(x,\Pb,T) - c(x,\Pb)|
\limsup_{T\to\infty}  \frac{\sqrt{\alpha_T}}{\beta_T} \cdot \frac{1}{\sqrt{\alpha_T}} |\hat{c}(x,\Pb,T) - c(x,\Pb)|
\end{equation*}

Proposition <ref> ensures that

\begin{align*}
\liminf_{T\to\infty} \frac{1}{\sqrt{\alpha_T}} |\hat{c}(x,\Pb,T) - c(x,\Pb)|
\geq
\limsup_{T\to\infty} \frac{1}{\sqrt{\alpha_T}} |\cSVP(x,\Pb,T) - c(x,\Pb)|
\sqrt{\Var_{\Pb}(\loss(x,\xi))} >0
\end{align*}

We can apply, therefore, a $\limsup$-$\liminf$ inequality (Lemma <ref>) to get

\begin{align*}
% \limsup_{T\to\infty} \beta_T |\hat{c}(x,\Pb,T) - c(x,\Pb)|
% &=
\limsup_{T\to\infty} \frac{\sqrt{\alpha_T}}{\beta_T} \cdot \frac{1}{\sqrt{\alpha_T}} |\hat{c}(x,\Pb,T) - c(x,\Pb)| %\\
\limsup_{T\to\infty} \frac{\sqrt{\alpha_T}}{\beta_T} \cdot
\liminf_{T\to\infty} \frac{1}{\sqrt{\alpha_T}}  |\hat{c}(x,\Pb,T) - c(x,\Pb)|
\end{align*}

Using Proposition <ref>, we have

\begin{align*}
\limsup_{T\to\infty} \frac{\sqrt{\alpha_T}}{\beta_T} \cdot
\liminf \frac{1}{\sqrt{\alpha_T}}  |\hat{c}(x,\Pb,T) - c(x,\Pb)|
\limsup_{T\to\infty} \frac{\sqrt{\alpha_T}}{\beta_T} \cdot
\limsup_{T\to\infty} \frac{1}{\sqrt{\alpha_T}}  |\cSVP(x,\Pb,T) - c(x,\Pb)| \\
\limsup_{T\to\infty} \frac{\sqrt{\alpha_T}}{\beta_T} \cdot
\lim_{T\to\infty} \frac{1}{\sqrt{\alpha_T}}  |\cSVP(x,\Pb,T) - c(x,\Pb)|
\\
\limsup_{T\to\infty} \frac{1}{\beta_T} |\cSVP(x,\Pb,T) - c(x,\Pb)|,
\end{align*}

where the last equality is justified by Lemma <ref> and the fact that $\lim \frac{1}{\sqrt{\alpha_T}} |\cSVP(x,\Pb,T) - c(x,\Pb)| = \sqrt{\Var_{\Pb}(\loss(x,\xi))} \not \in \{0,\infty\}$.

We finally point-out that although our required out-of-sample guarantee on the predictor is asymptotic (Proposition <ref>), SVP does enjoy also finite sample guarantees.

Let $x,\Pb \in \cX \times \cPin$. For all $T\in \integ$, the following holds

\begin{align*}
\Pb^{\infty}\left(c(x,\Pb) \leq \cSVP(x,\hat{\Pb}_T,T) +  \frac{7K}{3}\frac{a_T}{T}\right)
&\geq 1- 2e^{-a_T} \\
\Pb^{\infty}\left(
\geq
\cSVP(x,\hat{\Pb}_T,T)
- \sqrt{\frac{8a_T}{T}\Var_{\Pb}(\loss(x,\xi))}
\right)
&\geq 1- 2e^{-a_T}
\end{align*}

where $K = 2\sup_{x\in \cX}\|\loss(x,\cdot)\|_{\infty}$.

The proof of these bounds relies essentially on concentration inequalities on the empirical standard deviation shown by [Maurer and Pontil, 2009] and [Audibert et al., 2009]. See Appendix <ref> for a full proof.

§ OPTIMAL DATA-DRIVEN PRESCRIPTION

In this section we study the problem of optimal data-driven prescription as formalized in Problem (<ref>).
The key question can informally be stated as one of optimal approximation of the unknown objective function of Problem (<ref>) who's minimum provides the best approximation to its optimal solution.
Typically in machine learning and decision making, predictors (approximating the expectation) are first established with provable prediction guarantees as was done in Section <ref>.
Subsequently, these guarantees are extended to the prescribed solution using the structure of the decision set $\cX$.
A key questions is whether circumventing the prediction step results in better formulations.
In particular, would such a formulation improve the quality of the cost of the prescribed solution at the expense of a reduced quality of the overall cost prediction of any other decision?
We prove that this is not the case.

We will show that in each regime, the strongly optimal predictors identified in Section <ref> induce strongly optimal prescriptors as well. This result suggests that the classical approach in machine learning and decision-making of constructing estimators with guarantees on prediction and then extending such guarantees to the prescription is justified: the optimal predictor also induces an optimal prescriptor.

§.§ The Exponential Regime

Consider the exponential regime in which $a_T \sim rT$, $r>0$. [Van Parys et al., 2020] showed that the distributionally robust  predictor (<ref>) and its associated prescriptor

\begin{align*}
\xKL{,T}(\Pb) \in & \argmin_{x\in \cX} \cKL(x,\Pb,T),
\quad \forall \Pb \in \cP, \; \forall T \in \integ
\\
\in & \argmin_{x\in \cX} \sup_{\Pb' \in \cP} \set{c(x,\Pb')}{\D{\Pb} {\Pb'}\leq r},
\quad \forall \Pb \in \cP, \; \forall T \in \integ
\end{align*}

are also optimal among all prescriptors which are not an explicit function of the data size $T$. Notice that the minimizer $\xKL{}$ exists as $\cX$ is compact and $\cKL$ is continuous in the first argument.
We will extend this result and show that also our more general setting where predictors can be a function of $T$ this distributionally robust predictor remains optimal.

The prescriptor $(\cKL,\xKL{}) \in \cC \times \hat{\cX}$ verifies the prescription out-of-sample guarantee (<ref>) when $a_T \sim rT$.

Let $\Pb \in \cPin$. Denote $\Gamma = \set{\Pb' \in \mathcal{P}}{I(\Pb',\Pb) > r}$. Observe that, by definition of $\cKL$ (<ref>), for all $T\geq T_0$ we have

\[
\hat{\Pb}_T \not \in \Gamma \implies c(\xKL{,T},\Pb) \leq \cKL(\xKL{,T}(\Pb),\hat{\Pb}_T,T) = \cKL^{\star}(\Pb,T).
\]

Hence, we have

\begin{align*}
\limsup_{T\to\infty}
\frac{1}{T} \log \Pb^{\infty}
\left(
c(\xKL{,T}(\Pb),\Pb) > \cKL^{\star}(\hat{\Pb}_T,T)
\right)
\leq&
\limsup_{T\to\infty}
\frac{1}{T} \log \Pb^{\infty}
\left(
\hat{\Pb}_T \in \Gamma
\right)
\leq -\inf_{\Pb'\in \bar{\Gamma}}
\end{align*}

where the last equality uses the Large Deviation Principle, Theorem <ref>.
The convexity of the continuity of the relative entropy $I(\cdot,\cdot)$ in $\cPin \times \cPin$ implies that $\bar{\Gamma} \subset \set{\Pb' \in \mathcal{P}}{I(\Pb',\Pb) \geq r}$ (see Lemma <ref>).
$\inf_{\Pb'\in \bar{\Gamma}}
I(\Pb',\Pb) \geq r$,
and therefore, using the previous inequality, we get

\[
\limsup_{T\to\infty}
\frac{1}{T} \log \Pb^{\infty}
\left(
c(\xKL{,T}(\Pb),\Pb) > \cKL^{\star}(\hat{\Pb}_T,T)
\right)
\leq
\]

Consider the exponential regime in which $a_T\sim rT$. The pair of predictor and prescriptor $(\cKL,\xKL{})\in \cC \times \hat{\cX}$ is feasible in the prescription problem (<ref>) and
for any pair of predictor and prescriptor $(\hat{c},\hat{x})\in \cC \times \hat{\cX}$ satisfying the out-of-sample guarantee (<ref>), we have $(\cKL,\xKL{}) \orderpresc (\hat{c},\hat{x})$. That is, $(\cKL,\xKL{})$ is a strongly optimal prescriptor in the exponential regime.

Suppose for the sake of contradiction that there exists $(\hat{c},\hat{x})$ feasible in (<ref>) such that $(\cKL,\xKL{}) \not \orderpresc (\hat{c},\hat{x})$. There must exist $\Pb_0 \in \cPin$ such that

\begin{equation}\label{proof eq: dro prescriptor 1}
\limsup_{T\to \infty} \frac{|\cKL^{\star}(\Pb_0,T) - c^{\star}(\Pb_0)|}{|\hat{c}^{\star}(\Pb_0,T) - c^{\star}(\Pb_0)|} > 1,
\end{equation}

with the convention $\frac{0}{0} =1$.

As $\cKL$ does not depend on $T$, we denote $\cKL(x,\Pb) := \cKL(x,\Pb,T)$, and $\cKL^{\star}(\Pb) := \inf_{x\in\cX}\cKL(x,\Pb)$ for all $x,\Pb \in \cX \times\cP$ and $T\in \integ$.
Inequality (<ref>) implies that there exists $\varepsilon>0$ and $(t_T) \in \integ^{\integ}$ such that
$|\cKL^{\star}(\Pb_0) - c^{\star}(\Pb_0)|
\geq
(1+\varepsilon) |\hat{c}^{\star}(\Pb_0,t_T) - c^{\star}(\Pb_0)|$. This inequality can be rewritten as

\begin{equation}\label{proof eq: dro prescriptor 2}
\cKL^{\star}(\Pb_0) \geq \hat{c}^{\star}(\Pb_0,t_T) + \varepsilon |\hat{c}^{\star}(\Pb_0,t_T) - c^{\star}(\Pb_0)|
\end{equation}

where we used $\cKL^{\star}(\Pb_0) = \inf_{x\in \cX} \sup_{\Pb': I(\Pb_0,\Pb')\leq r} c(x,\Pb') \geq \inf_{x\in \cX} c(x,\Pb_0) = c^{\star}(\Pb_0)$ to drop the absolute values. We use this inequality to derive the following claim which we prove in Appendix <ref>.

There exists $\varepsilon_1>0$ and $(l_T)_{T\geq 1} \in \integ^{\integ}$ such that $\cKL^{\star}(\Pb_0) \geq \hat{c}^{\star}(\Pb_0,l_T) +\varepsilon_1$, for all $T\in\integ$.

Let $\varepsilon_1$ and $(l_T)_{T\geq1}$ given by the previous claim.
Using a probabilistic characterisation of the compactness of $\cX$ (Lemma <ref>), there exists $x_{\infty} \in \cX$ such that for all $\rho>0$

\begin{equation}\label{proof eq: dro precriptor 4}
\limsup_{T \to \infty} \Pb_0^{\infty}
\left(
\| \hat{x}_T(\Pb_0) - x_{\infty}\| \leq \rho
\right) >0.
\end{equation}

Let $\bar{\Pb} \in \cP$ be the maximizer in the definition of $\cKL$ (<ref>) such that $\cKL(x_{\infty},\Pb_0) = c(x_{\infty},\bar{\Pb})$ and $I(\Pb_0,\bar{\Pb})\leq r$.
By continuity of $c(x_{\infty},\cdot)$, we can perturb $\bar{\Pb}$ into $\bar{\Pb}_1 \in \cPin$ such that $\cKL(x_{\infty},\Pb_0) \leq c(x_{\infty},\bar{\Pb}_1) + \varepsilon_1/2$ and $I(\Pb_0,\bar{\Pb}_1)<r$.
The minimality of $\cKL^{\star}(\Pb_0)$ implies that $\cKL^{\star}(\Pb_0) \leq \cKL(x_{\infty},\Pb_0) \leq c(x_{\infty},\bar{\Pb}_1) + \varepsilon_1/2$.
Combining this result with Claim <ref>, we get $\hat{c}^{\star}(\Pb_0,l_T) + \varepsilon_1/2 \leq c(x_{\infty},\bar{\Pb}_1)$ for all $T \in \integ$. Finally, by the continuity of $c(\cdot, \bar{\Pb}_1)$ and the equicontinuity of $\hat{c}^{\star}$ (due to the compactness of $\cX$ and equicontinuity of $\hat{c}$, see Lemma <ref>), there exists $\rho>0$ and an open set $U\subset \cPin$ containing $\Pb_0$ such that

\begin{equation}\label{proof eq: dro prescriptor 3}
\hat{c}^{\star}(\Pb',l_T) + \varepsilon_1/3 \leq c(x,\bar{\Pb}_1),
\quad \forall T \in \integ,
\; \forall x \in \cX \; : \; \|x-x_{\infty}\| \leq \rho,
\; \forall \Pb' \in U.
\end{equation}

Armed with these results, we will now prove that $\hat{c}$ violates the out-of-sample guarantee (<ref>) in $\bar{\Pb}_1$. We have

\begin{align*}
\limsup_{T\to \infty}
&\frac{1}{T} \log \bar{\Pb}_1^{\infty}
\left(
c(\hat{x}_T(\hat{\Pb}_T),\bar{\Pb}_1) > \hat{c}^{\star}(\hat{\Pb}_T,T)
\right) \\
& \geq
\limsup_{T\to \infty}
\frac{1}{T} \log \bar{\Pb}_1^{\infty}
\left(
c(\hat{x}_T(\hat{\Pb}_T),\bar{\Pb}_1) > \hat{c}^{\star}(\hat{\Pb}_T,T)
\; \cap \;
\|\hat{x}_T(\hat{\Pb}_T) - x_{\infty}\|\leq \rho
\right) \\
\limsup_{T\to \infty}
\frac{1}{l_T} \log \bar{\Pb}_1^{\infty}
\left(
c(\hat{x}_T(\hat{\Pb}_{l_T}),\bar{\Pb}_1) > \hat{c}^{\star}(\hat{\Pb}_{l_T},l_T)
\; \cap \;
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho
\right) \\
\limsup_{T\to \infty}
\frac{1}{l_T} \log \bar{\Pb}_1^{\infty}
\left(
\hat{\Pb}_{l_T} \in U
\; \cap \;
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho
\right)
\end{align*}

where the last inequality uses (<ref>). Using an exponential change of measure, Lemma <ref>, we have

\begin{align*}
\limsup_{T\to \infty}
&\frac{1}{l_T} \log \bar{\Pb}_1^{\infty}
\left(
\hat{\Pb}_{l_T} \in U
\; \cap \;
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho
\right) \\
- I(\Pb_0,\bar{\Pb}_1) +
\limsup_{T\to \infty}
\frac{1}{l_T} \log \Pb_0^{\infty}
\left(
\hat{\Pb}_{l_T} \in U
\; \cap \;
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho
\right)
\end{align*}

We show now that the second term of the LHS is zero.
We have $\lim_{T\to \infty} \Pb_0^{\infty} (\hat{\Pb}_{l_T} \in U) =1$ as $\Pb_0 \in U^{\into}$ and $\limsup_{T\in \integ}\Pb_0^{\infty} (\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho)>0$ by (<ref>), therefore,

\begin{align*}
\limsup_{T\to \infty}
&\frac{1}{l_T} \log \Pb_0^{\infty}
\left(
\hat{\Pb}_{l_T} \in U
\; \cap \;
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho
\right)\\
\limsup_{T\to \infty}
\frac{1}{l_T} \log
\left[
\Pb_0^{\infty}
\hat{\Pb}_{l_T} \in U)
\Pb_0^{\infty}
\|\hat{x}_{l_T}(\hat{\Pb}_{l_T}) - x_{\infty}\|\leq \rho)
\right] = 0.
\end{align*}

Moreover we have $I(\Pb_0,\bar{\Pb}_1)<r$ by construction of $\bar{\Pb}_1$. Hence, we have shown that

\begin{align*}
\limsup_{T\to \infty}
\frac{1}{T} \log \bar{\Pb}_1^{\infty}
\left(
c(\hat{x}_T(\hat{\Pb}_T),\bar{\Pb}_1) > \hat{c}^{\star}(\hat{\Pb}_T,T)
\right)
\geq
\end{align*}

This implies that $\hat{c}$ violates the prescription out-of-sample guarantee (<ref>) which contradicts our feasibility assumption.

§.§ The Superexponential Regime

We prove the same result for the superexponential regime where $a_T \gg T$. Even when the out-of-sample guarantee is required only for the prescribed solution, superexponential guarantees require the predictor to cover the worst scenario of the uncertainty, no matter the data size. Consider a prescriptor associated to the robust predictor $\cRob$ defined in (<ref>)

\begin{align*}
\xRob{,T}(\Pb) &\in \argmin_{x\in \cX} \cRob(x,\Pb,T),
\quad \forall \Pb \in \cP, \; \forall T \in \integ, \\
&\in \argmin_{x\in \cX} \max_{i\in \Sigma} \,\ell(x,i),
\quad \forall \Pb \in \cP, \; \forall T \in \integ.
\end{align*}

This minimizer exists as $\cX$ is compact and $\cRob$ is continuous in the first argument.

The prescriptor $(\cRob,\xRob{}) \in \cC \times \hat{\cX}$ verifies the prescription out-of-sample guarantee (<ref>) when $a_T \gg T$.

Let $\Pb \in \cPin$. The guarantee is directly implied by

\left(
c(\xRob{,T}(\hat{\Pb}_T), \Pb) > \cRob^{\star}(\hat{\Pb}_T,T)
\right) = \Pb^\infty
\left(
c(\xRob{,T}(\hat{\Pb}_T), \Pb) > \sup_{\Pb' \in \cP} c(\xRob{,T}(\hat{\Pb}_T),\Pb')
\right) = 0.

Consider the superexponential regime in which $a_T\gg T$. The pair of predictor and prescriptor $(\cRob,\xRob{})\in \cC \times \hat{\cX}$ is feasible in the prescription problem (<ref>) and
for any pair of predictor and prescriptor $(\hat{c},\hat{x})\in \cC \times \hat{\cX}$ satisfying the out-of-sample guarantee (<ref>), we have $(\cRob,\xRob{}) \orderpresc (\hat{c},\hat{x})$. That is, $(\cRob,\xRob{})$ is a strongly optimal prescriptor in the superexponential regime.

We defer the proof to Appendix <ref>. The proof is in essence the same as the proof of Theorem <ref> with $r \to \infty$.

§.§ The Subexponential Regime

We now turn to the subexponential regime where $a_T \ll T$. Akin the prediction problem, consistency is a necessary condition for optimality in the optimal prescription problem in the subexponential regime.

Consider the subexponential regime in which $a_T\ll T$. Every weakly optimal pair of predictor-precriptor in (<ref>) is consistent. That is, for every pair of predictor-precriptor $(\hat{x},\hat{c})$ verifying the prescription out-of-sample guarantee (<ref>), either $(\hat{c}(\cdot,\cdot,T))_{T\geq1}$ converges point-wise to $c(\cdot,\cdot)$,
or there exists a pair of predictor precriptor $(\hat{x}',\hat{c}')$ verifying the out-of-sample guarantee that is strictly preferred to $(\hat{x},\hat{c})$, ie $(\hat{x}',\hat{c}') \orderpresc (\hat{x},\hat{c})$ and $(\hat{x}',\hat{c}') \not \equiv_{\hat{\cX}} (\hat{x},\hat{c})$.

The full proof is deferred to Appendix <ref>. Suppose $(\hat{x},\hat{c})$ is weakly optimal and not consistent. There exists $x_0\in \mathcal{X}$ and $\Pb_0 \in \mathcal{P}$ such that $\limsup |\hat{c}(x_0,\Pb_0,T) - c(x,\Pb_0)| = \varepsilon>0$. We consider the same exact construction of $\hat{c}'$ as in the proof of Proposition <ref> (illustrated in Figure <ref>).
Among the possible prescriptors $\hat{x}'$ associated to $\hat{c}'$, we consider the closest one to the prescriptor $\hat{x}_T$ of $\hat{c}$. We then show that $(\hat{x}',\hat{c}')$ is a feasible pair of predictor prescriptor and that $(\hat{x}',\hat{c}')$ is strictly preferred to $(\hat{x},\hat{c})$. The latter result follows essentially from the construction of $\hat{c}'$: $\hat{c}'$ is less or equal to $\hat{c}$ at every point, hence, its minimum is also lower than the minimum of $\hat{c}$. Furthermore, we show that a feasible predictor is necessarily larger than the true cost $c$ asymptotically, hence, $\hat{c}'$ and its minimum $\hat{c}'^{\star}$ are closer to the true cost $c$ and the optimal cost $c^{\star}$ respectively.

To show feasibility of the pair $(\hat{x}',\hat{c}')$, we prove that they verify the out-of-sample guarantee. In order to do that, we examine the pair in two regions of $\cP$. The first region consist of distributions $\Pb$ such that $(\hat{x}'_T(\Pb),\Pb)$ does not fall in the ball $\mathcal{B}\left((x_0,\Pb_0),\frac{\rho}{2} \right)$ where $\hat{c}$ was perturbed into $\hat{c}'$ (see Figure <ref>). In this region, $\hat{c}'$ is exactly $\hat{c}$, and as $\hat{x}'$ is chosen as the closest minimizer of $\hat{c}'$ to $\hat{x}$, we prove that $\hat{x}'$ is also exactly $\hat{x}$. Hence, $(\hat{x}',\hat{c}')$ inherits the out-of-sample guarantee of $(\hat{x},\hat{c})$ in this region. The second region is where $(\hat{x}'_T(\Pb),\Pb)$ falls in the ball $\mathcal{B}\left((x_0,\Pb_0),\frac{\rho}{2} \right)$ where $\hat{c}$ was perturbed into $\hat{c}'$. We show that a constant gap with the true cost suffices to verify a prescription subexponential guarantee. As $\hat{c}'$ is constructed such that in this region, it maintains a constant gap with the true cost, it follows that $(\hat{x}',\hat{c}')$ verifies the desired subexponential guarantee.

As pointed out out in Remark <ref>, the consistency of predictors in the sense of Proposition <ref> implies the consistency of the estimator $(\hat{c}(x,\hat{\Pb}_T,T))_{T\geq 1}$ of the true cost $c(x,\Pb)$. Notice that it also implies the consistency of the estimator $(\hat{c}^{\star}(\hat{\Pb}_T,T))_{T\geq 1}$ of the optimal cost $c^{\star}(\Pb)$, in the prescription problem. In fact, the point-wise convergence of $(\hat{c}(\cdot,\cdot,T))_{T\geq 1}$ to $c(\cdot,\cdot)$ along with equicontinuity of $(\hat{c}(\cdot,\cdot,T))_{T\geq 1}$ implies its uniform convergence. Uniform convergence of $(\hat{c}(\cdot,\cdot,T))_{T\geq 1}$ to $c(\cdot,\cdot)$ implies point-wise convergence of $(\hat{c}^{\star}(\cdot,T))_{T\geq 1}$ to $c^{\star}(\cdot)$ (see Lemma <ref>), which combined with compactness of $\cX$, implies its uniform convergence (see Lemma <ref>). Uniform convergence combined with the almost sure convergence of $\hat{\Pb}_T$ to $\Pb$ implies almost sure convergence of $(\hat{c}^{\star}(\hat{\Pb}_T,T))_{T\geq 1}$ to the optimal cost $c^{\star}(\Pb)$.

Consider a prescriptor associated to the SVP predictor $\cSVP$ defined in Equation (<ref>)

\begin{align*}
\xSVP{,T}(\Pb) &\in \argmin_{x\in \cX} \cSVP(x,\Pb,T),
\quad \forall \Pb \in \cPin,\; \forall T \in \integ,\\
&\in \argmin_{x\in \cX} c (x,\Pb)+ \sqrt{\frac{2a_T}{T}\Var_{\Pb}(\loss(x, \xi))},
\quad \forall \Pb \in \cPin,\; \forall T \in \integ.
\end{align*}

The minimum of $\cSVP(\cdot,\Pb,T)$ is indeed attained as $\cX$ is compact and $\cSVP(\cdot,\Pb,T)$ is continuous. The SVP predictor $\cSVP$ emerges in our frameworks |as we will prove momentarily| as the optimal prescriptor.
Our framework considers only the out-of-sample performance and accuracy of the considered prescriptors.
Nevertheless, the tractability of the resulting prescriptor is a key practical issue.
The following proposition shows that minimizing the SVP predictor $\cSVP$ is essentially a convex optimization problem when the loss function is convex.

Suppose the loss function $x\rightarrow \loss(x,i)$ of each uncertain scenario $i\in \Sigma$ is convex. Let $T\in \integ$ and $\hat{\Pb}_T$ the observed empirical distribution.  If $a_T$ is chosen such that
\sqrt{2a_T/T} \leq \min_{i\in \Sigma}\hat{\Pb}_T(i) \min_{i\in \Sigma} \min(\hat{\Pb}_T(i),1-\hat{\Pb}_T(i))
then $x\rightarrow c(x,\hat{\Pb}_T) + \sqrt{\frac{2a_T}{T} \Var_{\hat{\Pb}_T}(\loss(x,\xi))}$ is convex in $\cX$.

Notice that for all $\Pb' \in \cP$, $x\rightarrow c(x,\Pb)$ is convex as a convex combination of the loss function on each uncertainty.
Under the condition on $a_T$, Proposition <ref> implies that the considered function, SVP $\cSVP$, is equal to $\sup_{\Pb'\in \cP} \{c(x,\Pb') \; : \; \|\Pb'-\hat{\Pb}_T \|^2_{\hat{\Pb}_T} \leq a_T/T\}$ which is the supremum of convex functions, and is therefore convex.

This result is rather surprising. While the empirical expectation is clearly convex when the loss is convex, the empirical standard deviation $x \rightarrow \sqrt{\Var_{\hat{\Pb}_T}(\loss(x,\xi))}$ is in general non-convex even when the loss is convex [Maurer and Pontil, 2009, Duchi and Namkoong, 2016, Lam, 2019]. This implies that SVP is a sum of a convex and a non-convex function which is, in general, not convex. However, Proposition <ref> shows that when the scaling $\sqrt{2a_T/T}$ of the standard deviation is small enough, the SVP predictor becomes convex (see Figure <ref> for an illustration). Furthermore, the threshold of scaling for convexity is exactly the scaling for which the ellipsoid $\left\{
\Pb'\; : \;
\|\Pb'-\hat{\Pb}_T\|^2_{\hat{\Pb}_T}
\leq
\frac{a_T}{T}
\right\}$ of the DRO expression of the SVP predictor (<ref>) is contained in the probability simplex $\cP$.
This result admits also a probabilistic interpretation which can be traced back to [Duchi and Namkoong, 2016]. As the empirical distribution $\hat{\Pb}_T$ is close to $\Pb \in \cPin$ with increasing probability with $T$, and the scaling $\sqrt{2a_T/T}$ converges to $0$ (subexponential regime), the convexity condition is verified with increasingly high probability with $T$. Hence, the SVP predictor is convex with high probability.

Plot of $x\rightarrow \cSVP(x,\hat{\Pb}_T,T) = c(x,\hat{\Pb}_T) + \sqrt{\frac{2a_T}{T} \Var_{\hat{\Pb}_T}(\loss(x,\xi))}$ for different values of empirical standard deviation scaling $a_T/T$. Here $\loss(x,\xi) = |x-\xi|$ and $\hat{\Pb}_T$ is a uniform distribution on $\{-2,1,0,1,2\}$. The higher curves correspond to higher scaling $a_T/T$. The curves transition from non-convexity to convexity when the scaling decreases illustrating Proposition <ref>.

The following proposition quantifies the amount of regularization the prescription of SVP adds. It also highlights how SVP naturally favors solutions with lower variance, and ultimately converges to the optimal solution with the lowest variance.

For all $\Pb \in \cPin$,

\begin{equation*}
|\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)| \leq \sqrt{\frac{2a_T}{T}\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}, \quad \forall T \in \integ,
\end{equation*}

where $x^{\star}(\Pb)$ is a minimizer of $c(\cdot,\Pb)$ that has the lowest variance, that is, $x^{\star}(\Pb) \in \argmin \{\Var_{\Pb}(\loss(x,\xi)) \; : \; x\in \argmin c(\cdot,\Pb)\}$. Furthermore

\begin{equation*}
\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb) = \sqrt{\frac{2a_T}{T}\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))} + o\left(\sqrt{\frac{a_T}{T}}\right),
\end{equation*}

and any prescriptor $\xSVP{,T}(\Pb)$ associated to the SVP predictor verifies
$$\Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi)) \xrightarrow[T\to \infty]{}  \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi)).$$

Let $\Pb \in \cPin$ and $T\in \integ$. Set $\alpha_T = 2a_T/T$. By minimality of $c^{\star}(\Pb)$, we have

\begin{align*}
\cSVP^{\star}(\Pb,T) &= c(\xSVP{,T}(\Pb),\Pb) + \sqrt{\alpha_T \Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi))} \numberthis \label{proof eq: robust precriptor eq 1}\\
&\geq c^{\star}(\Pb) + \sqrt{\alpha_T \Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi))} \numberthis \label{proof eq: robust precriptor ineq 1}
\end{align*}

Let $x^{\star}(\Pb)$ as defined in the proposition.
By minimality of $\cSVP^{\star}$, we have

\begin{align*}
\cSVP^{\star}(\Pb,T) &\leq \cSVP(x^{\star}(\Pb),\Pb,T) = c^{\star}(\Pb) + \sqrt{\alpha_T \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))} \numberthis \label{proof eq: robust precriptor ineq 2}
\end{align*}

Hence, combining (<ref>) and (<ref>), we get,

\begin{equation}\label{proof eq: gendarmes}
\sqrt{\frac{a_T}{T}\Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi))} \leq
\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)
\leq
\sqrt{\frac{a_T}{T}\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}.
\end{equation}

which proves the desired inequality. It remains to prove the convergence of $(\Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi)))_{T\geq 1}$ to $\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$ and the asymptotic development of $|\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)|$. Notice that the convergence of the variance along with (<ref>) implies the asymptotic development, hence it suffices to prove the converenge of the variance.

Inequality (<ref>) implies that $\limsup_{T\to \infty} \Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi)) \leq \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$.  It remains to the show that $\liminf_{T\to \infty} \Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi)) \geq \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$.
As the sequence $\xSVP{,T}(\Pb)$ lives in the compact set $\cX$, it has accumulation points. Let $(\xSVP{,t_T}(\Pb))_{T\geq 1}$ be subsequence converging to a limit $x_{\infty} \in \cX$. Let us show that $x_{\infty}$ is a minimizer of $c(\cdot,\Pb)$. Inequality (<ref>) implies that $\cSVP^{\star}(\Pb,T) \xrightarrow[T\to \infty]{} c^{\star}(\Pb)$, therefore using (<ref>), we have $c(\xSVP{,T}(\Pb),\Pb)\xrightarrow[T\to \infty]{} c^{\star}(\Pb)$. Hence, by continuity of $c(\cdot,\Pb)$, we have $c(x_{\infty},\Pb) = c^{\star}(\Pb)$ which proves that $x_{\infty}$ is a minimizer of $c(\cdot,\Pb)$. As $x^{\star}(\Pb)$ is a minimizer of $c(\cdot,\Pb)$ with the lowest variance by definition, we have $\Var_{\Pb}(\loss(x_{\infty},\xi)) \geq \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$. We have therefore shown that every accumulation point $v$ of $\Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi))$ verifies $v \geq \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$. Hence $\liminf_{T\to \infty} \Var_{\Pb}(\loss(\xSVP{,T}(\Pb),\xi)) \geq \Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))$ which completes the proof.

We now prove the strong optimality of the SVP prescriptor. As before, we first establish its feasibility.

The prescriptor $(\cSVP,\xSVP{}) \in \cC \times \hat{\cX}$ verifies the prescription out-of-sample guarantee (<ref>) when $a_T \ll T$.

Let $\Pb \in \cPin$ and $T_0 \in \integ$ be such that for all $T\geq T_0$ the DRO form (<ref>) of $\cSVP$ holds. For $T \in \integ$, we have

\hat{\Pb}_T \in E_T:= \set{\Pb' \in \mathcal{P}}{\norm{\Pb'-\Pb}^2_{\Pb'}\leq \frac{a_T}{T}} \implies
c(\xSVP{,T}(\hat{\Pb}_T)) \leq
\cSVP(\xSVP{,T}(\hat{\Pb}_T), \hat{\Pb}_T,T) =\cSVP^{\star}(\hat{\Pb}_T,T)

$$\frac{1}{a_T} \log \Pb^\infty
\left(
c(\hat{x}_T(\hat{\Pb}_T), \Pb) > \hat c^{\star}( \hat{\Pb}_T,T)
\right)
\leq
\frac{1}{a_T} \log \Pb^{\infty}
\left(
\hat{\Pb}_T \not\in E_T
\right)

We have shown in the proof of Proposition <ref> that $\limsup_{T\to\infty}
\frac{1}{a_T}  \log \Pb^{\infty}
\left(
\hat{\Pb}_T \not\in E_T
\right) \leq -1$ which gives the desired result.

To establish strong optimality in the sub-exponential regime we will need to impose further regularity on problem (<ref>) which we wish to approximate. In order to establish the following theorem, we suppose that the minimizer $x^{\star}(\Pb)$ of the true cost $c(\cdot,\Pb)$ is unique, for all $\Pb \in \cPin$. This is the  case for instance when the loss of each uncertain scenario $i$, $x \rightarrow \loss(x,i)$ is strictly convex. Notice that the imposed assumption is only on the actual cost $c$ and not on the predictors $\hat{c}$ which can have multiple minima. The imposed restriction is necessary as $x^{\star}(\Pb)$ can behave very erratically at any distribution $\Pb$ where $\argmin c(x, \Pb)$ should fail to be single-valued and consequently seems too be hard to approximate optimally.

Consider the subexponential regime in which $a_T\ll T$. The pair of predictor and prescriptor $(\cSVP,\xSVP{})\in \cC \times \hat{\cX}$ is feasible in the prescription problem (<ref>) and
for any pair of predictor and prescriptor $(\hat{c},\hat{x})\in \cC \times \hat{\cX}$ satisfying the out-of-sample guarantee (<ref>), we have $(\cSVP,\xSVP{}) \orderpresc (\hat{c},\hat{x})$. That is, $(\cSVP,\xSVP{})$ is a strongly optimal prescriptor in the subexponential regime.

The key step to prove Theorem <ref> is to show that in order to verify an out-of-sample guarantee with speed $(a_T)_{T\geq1}$, a prescriptor must minimize a cost that necessarily adds a regularization to the empirical cost larger than $\sqrt{2a_T/T}\sqrt{\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}$, where $x^{\star}(\Pb)$ is a minimizer of the cost $c(x,\Pb)$. This quantity happens to be exactly the regularization added by the SVP prescriptor by Proposition <ref>.

Let $(\hat{c}, \hat{x}) \in \hat{\cX}$ be a pair of predictor prescriptor verifying the out-of-sample guarantee (<ref>). The following inequality holds

\begin{equation*}
\liminf_{T\to \infty} \sqrt{\frac{T}{a_T}}|\hat{c}^{\star}(\Pb,T) - c^{\star}(\Pb)|
\geq
\limsup_{T\to \infty} \sqrt{\frac{T}{a_T}}|\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)| = \sqrt{\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}, \quad \forall \Pb \in \cPin.
\end{equation*}

Suppose for the sake of argument that there exists $\Pb_0 \in \cPin$ such that

\begin{equation} \label{proof eq: initial assumption presc}
\liminf_{T\to \infty} \sqrt{\frac{T}{a_T}}|\hat{c}^{\star}(\Pb_0,T) - c^{\star}(\Pb_0)|
\limsup_{T\to \infty} \sqrt{\frac{T}{a_T}}|\cSVP^{\star}(\Pb_0,T) - c^{\star}(\Pb_0)|.
\end{equation}

We start the proof by showing how this inequality extends to an open ball. This will allow us then to examine $\hat{c}$ in an open neighborhood. In all what follow, we denote $\alpha_T = 2a_T/T$, for all $T$.

There exists $\Pb_1 \in \cPin$, $\varepsilon>0$, and an increasing sequence $(t_T)_{T\geq 1} \in \integ^\integ$, such that for all $\varepsilon'>0$, there exists an open ball $\mathcal{B}(\Pb_1,r)$ around $\Pb_1$ of radius $r>0$ such that

\hat{c}^{\star}(\Pb,t_T)
+\varepsilon  \sqrt{\alpha_{t_T}}
-\varepsilon' \|\Pb-\Pb_1\| + c(\xSVP{,t_T}(\Pb_1),\Pb_1-\Pb)
- c(\hat{x}_{t_T}(\Pb),\Pb_1- \Pb)
\leq
\cSVP^{\star}(\Pb,t_T),

for all $\Pb \in \mathcal{B}(\Pb_1,r)$ and $T\in \integ$.

See Appendix <ref>.

Let $\varepsilon$, $\Pb_1$ and $(t_T)_{T \geq 1}$ given by Claim <ref>. Set $\varepsilon'>0$ to be specified later. Let $r>0$ given by Claim <ref>, such that for all $\Pb \in \mathcal{B}(\Pb_1,r)$ and $T\geq 1$

\begin{equation}\label{eq: robustOpt precriptor: uniformoty ineq. }
\hat{c}^{\star}(\Pb,t_T)
\leq
\cSVP^{\star}(\Pb,t_T)
- \varepsilon \sqrt{\alpha_{t_T}}
+ \varepsilon' \|\Pb - \Pb_1\|
+c(\xSVP{,t_T}(\Pb),\Pb_1- \Pb)
- c(\hat{x}_{t_T}(\Pb_1),\Pb_1-\Pb).
\end{equation}

In the reminder of the proof, we will show that the out-of-sample guarantee (<ref>) for $\hat{c}$ fails at $\Pb_1$, which contradicts the feasibility of $(\hat{c},\hat{x})$. In order to do that, we will construct a sequence of distributions $(\Pb_T)_{T\geq1}$ converging sufficiently slowly to $\Pb_1$ and where the out-of-sample guarantee always fails. We will then use the Moderate Deviation Principle, Theorem <ref>.

Let us first recall some notions that will be used in this proof. Recall the function $\varphi$ defined in Proposition <ref>. The proposition ensures that $\cSVP(x,\Pb,T) = c(x,\Pb + \sqrt{\alpha_T} \varphi_x(\Pb))$ for all $x,\Pb \in \cX \times \cPin$ and $T\in \integ$. Moreover, immediate computations[See Lemma <ref>] imply that $c(x_1,\varphi_{x_2}(\Pb)) = \Cov_{\Pb}(\loss(x_1,\xi),\loss(x_2,\xi)) / \sqrt{\Var_{\Pb}(\loss(x_2,\xi))}$ where
$\Cov_{\Pb}(\loss(x_1,\xi),\loss(x_2,\xi)):= \Eb_{\Pb}(\loss(x_1,\xi)\loss(x_2,\xi)) - \mathbb{E}_{\Pb}(\loss(x_1,\xi))\mathbb{E}_{\Pb}(\loss(x_2,\xi))$ for all $x_1,x_2 \in \cX$, when $\Var_{\Pb}(\loss(x_2,\xi)) >0$.

We start by setting key ingredients in constructing the sequence $\Pb_T$. $(\hat{x}_T(\Pb_1))_{T\geq 1}$ lives in the compact $\cX$, we can therefore assume without loss of generality that $(\hat{x}_{t_T}(\Pb_1))_{T\geq 1}$ converges to a limit $x_1 \in \cX$.

$x_1 \in \argmin_{x \in \cX}c(x,\Pb_1)$.

We have $|c(\hat{x}_{t_T}(\Pb_1),\Pb_1)-c^{\star}(\Pb_1)| \leq |c(\hat{x}_{t_T}(\Pb_1), \Pb_1)-\hat{c}(\hat{x}_{t_T}(\Pb_1),\Pb_1,t_T)| + |\hat{c}^{\star}(\Pb_1,t_T) -c^{\star}(\Pb_1)| \xrightarrow[T\to \infty]{} 0$ by uniform convergence of $\hat{c}(\cdot,\cdot,t_T)$ to $c(\cdot,\cdot)$ (see Lemma <ref> for details on the convergence of the second term).  This implies by continuity of $c(\cdot,\Pb_1)$ and convergence of $(\hat{x}_{t_T}(\Pb_1))_{T\geq 1}$ to $x_1$ that $c(x_1,\Pb_1) = c^{\star}(\Pb_1)$ which gives the desired result.

Let $\eta \in (0,1)$ and $\delta>0$ to be specified later.
$\Gamma = \mathcal{B}(\varphi_{x_1}(\Pb_1), \frac{\delta}{\sup_x \|\loss(x,\cdot)\|})$ the open ball in the set of measures that sum to zero, $\cP_{0,\infty}$, centered around $\varphi_{x_1}(\Pb_1)$ of radius $\frac{\delta}{\sup_x \|\loss(x,\cdot)\|}$.
For all $u \in \Gamma$ and $T \in \integ$, we consider the sequence

$$\Pb_T(u) = \Pb_1 - (1-\eta)\sqrt{\alpha_T} u,$$

for we which we show that $(\hat{x},\hat{c})$ is always disappointing, i.e., the guarantee (<ref>) fails to hold, in the subsequence $(t_T)_{T\geq 1}$. See Figure <ref> for an illustration of the construction.

Fix $u\in \Gamma$. Let us examine the sign of $c(\hat{x}_{t_T}(\Pb_{t_T}(u)),\Pb_1) - \hat{c}^{\star}(\Pb_{t_T}(u),t_T)$. To simplify notations, we denote $\Pb_T:= \Pb_T(u)$.
As $\Pb_T \to \Pb_1$, we can assume without loss of generality that $\Pb_{t_T} \in \mathcal{B}(\Pb_1,r)$ for all $T$ by extraction accordingly from $(t_T)_{T\geq 1}$. Using (<ref>) to bound $\hat{c}^{\star}(\Pb_{t_T},t_T)$, we have for all $T \in \integ$

\begin{align*}
c(\hat{x}_{t_T}(\Pb_T),\Pb_1) - \hat{c}^{\star}(\Pb_{t_T},t_T)
c(\hat{x}_{t_T}(\Pb_{t_T}),\Pb_1) - \cSVP^{\star}(\Pb_{t_T},t_T) \\
&  \;  + \varepsilon \sqrt{\alpha_{t_T}} - \varepsilon' \|\Pb_{t_T} - \Pb_1\| \\
&   \;  - c(\xSVP{,t_T}(\Pb_{t_T}), \Pb_1 - \Pb_{t_T})
+c(\hat{x}_{t_T}(\Pb_1),\Pb_1 - \Pb_{t_T}). \numberthis \label{proof eq: prescriptor main ineq}
\end{align*}

We start by analyzing the first term $c(\hat{x}_{t_T}(\Pb_{t_T}),\Pb_1)
- \cSVP^{\star}(\Pb_{t_T},t_T)$. Using the minimality of $c^{\star}(\Pb_1)$, we have for all $T \in \integ$

\begin{align}\label{proof eq: first term}
- \cSVP^{\star}(\Pb_{t_T},t_T)
c^{\star}(\Pb_1) - \cSVP^{\star}(\Pb_{t_T},t_T)
\end{align}

In all what follow, the $o$ notation hides constants independent of $u$, therefore, the asymptotic notation is uniform in $u$.

The follow inequalities hold

$$\eta \sqrt{\Var_{\Pb_1}(\loss(\xSVP{,T}(\Pb_T),\xi))}
- \delta
+ o(1)
\leq
\frac{1}{\sqrt{\alpha_T}}[\cSVP^{\star}(\Pb_T,T) - c^{\star}(\Pb_1)]
\leq
\eta  \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
+ \delta
+ o(1).

Let $T\in \integ$. Let us first prove the LHS inequality.

\begin{align*}
\cSVP^{\star}(\Pb_T,T)
c(\xSVP{,T}(\Pb_T),\Pb_T) + \sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(\xSVP{,T}(\Pb_T),\xi))} \\
&= c(\xSVP{,T}(\Pb_T),\Pb_1)
- (1-\eta)\sqrt{\alpha_T} c(\xSVP{,T}(\Pb_T),u)
+\sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(\xSVP{,T}(\Pb_T),\xi))}
\\
&\geq c(\xSVP{,T}(\Pb_T),\Pb_1)
- (1-\eta)\sqrt{\alpha_T} c(\xSVP{,T}(\Pb_T),\varphi_{x_1}(\Pb_1))
+\sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(\xSVP{,T}(\Pb_T),\xi))}
-\delta  \sqrt{\alpha_T}
\\
&\geq c^{\star}(\Pb_1)
- (1-\eta)\sqrt{\alpha_T}\frac{\Cov_{\Pb_1}(\loss(\xSVP{,T}(\Pb_T),\xi),\loss(x_1,\xi))}{\sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}}
+\sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(\xSVP{,T}(\Pb_T),\xi))}
-\delta  \sqrt{\alpha_T}
\\
&\geq c^{\star}(\Pb_1)
- (1-\eta)\sqrt{\alpha_T} \sqrt{\Var_{\Pb_1}(\loss(\xSVP{,T}(\Pb_T),\xi))}
+\sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(\xSVP{,T}(\Pb_T),\xi))}
-\delta  \sqrt{\alpha_T}
\\
&= c^{\star}(\Pb_1) + \eta \sqrt{\alpha_T} \sqrt{\Var_{\Pb_1}(\loss(\xSVP{,T}(\Pb_T),\xi))}
-\delta  \sqrt{\alpha_T}
+ o(\sqrt{\alpha_T})
\end{align*}

where the first equality uses the robust predictor's formula (<ref>), the first inequality uses the definition of $\Gamma$, the second inequality uses the minimality of $c^{\star}$, the last inequality Cauchy-Schartz inequality  and the last equality uses the fact that $\Var_{\Pb_T}(\loss(x_T,\xi)) = \Var_{\Pb_1}(\loss(x_T,\xi)) + o(1)$ for all $(x_T)_{T\geq 1} \in \cX^\integ$ (see Lemma <ref> for details).

We now turn to the RHS. Similarly, we have

\begin{align*}
\cSVP^{\star}(\Pb_T,T)
\leq
\cSVP(x_1,\Pb_T,T)
&= c(x_1,\Pb_T) + \sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(x_1,\xi))}\\
&= c(x_1,\Pb_1)
-(1-\eta)\sqrt{\alpha_T} c(x_1,u)
+ \sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(x_1,\xi))}\\
&\leq c(x_1,\Pb_1)
-(1-\eta)\sqrt{\alpha_T} c(x_1,\varphi_{x_1}(\Pb_1))
+ \sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(x_1,\xi))}
+ \delta \sqrt{\alpha_T} \\
&= c(x_1,\Pb_1)
-(1-\eta)\sqrt{\alpha_T} \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
+ \sqrt{\alpha_T} \sqrt{\Var_{\Pb_T}(\loss(x_1,\xi))}
+ \delta \sqrt{\alpha_T}
\\
&= c(x_1,\Pb_1) + \eta \sqrt{\alpha_T} \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
+ \delta \sqrt{\alpha_T}
+ o(\sqrt{\alpha_T})
\end{align*}

Using Claim <ref>, we have $c(x_1,\Pb_1) = c^{\star}(\Pb_1)$, therefore, the last inequality gives the desired result.

Using the RHS of Claim <ref> with (<ref>), we get

\begin{align*}
- \cSVP^{\star}(\Pb_{t_T},t_T)
-\eta \sqrt{\alpha_{t_T}} \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
- \delta  \sqrt{\alpha_{t_T}}
+o(\sqrt{\alpha_{t_T}}). \numberthis \label{proof eq: first term ineq}
\end{align*}

The second term of (<ref>) can be written as

\begin{equation}\label{proof eq: second term}
\varepsilon \sqrt{\alpha_{t_T}}
- \varepsilon' \|\Pb_{t_T} - \Pb_1\|
= (\varepsilon - \varepsilon'(1-\eta)\|u\|) \sqrt{\alpha_{t_T}}.
\end{equation}

Let us now examine the last term of (<ref>). We have

\begin{align*}
c(\hat{x}_{t_T}(\Pb_1),&\Pb_1 - \Pb_{t_T}) - c(\xSVP{,t_T}(\Pb_{t_T}), \Pb_1 - \Pb_{t_T}) \\
\sqrt{\alpha_{t_T}}
\left(
c(\xSVP{,t_T}(\Pb_{t_T}), u)
\right)\\
\sqrt{\alpha_{t_T}}
\left(
c(\xSVP{,t_T}(\Pb_{t_T}), \varphi_{x_1}(\Pb_1))
- 2\delta
\right)  \\
\sqrt{\alpha_{t_T}}
\left(
\sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
\frac{\Cov_{\Pb_1}(\loss(\xSVP{,T}(\Pb_{t_T}),\xi), \loss(x_1,\xi))}{\sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}}
\right)
- 2\delta \sqrt{\alpha_{t_T}}
\\
\sqrt{\alpha_{t_T}}
\left(
\sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
\sqrt{\Var_{\Pb_1}(\loss(\xSVP{,t_T}(\Pb_{t_T}),\xi))}
\right)
- 2\delta \sqrt{\alpha_{t_T}}
\end{align*}

where the first inequality is by definition of $\Gamma$ and the last inequality is due to Cauchy–Schwarz inequality. Hence, using Claim <ref>, we have[Notice that we can also show that this quantity is non-positive, giving therefore upper and lower bounds.]

\begin{equation}\label{proof eq: presc third term}
c(\hat{x}_{t_T}(\Pb_1),\Pb_1 - \Pb_{t_T}) - c(\xSVP{,t_T}(\Pb_{t_T}), \Pb_1 - \Pb_{t_T})
\geq
-\left(2\delta/\eta + 2\delta \right) \sqrt{\alpha_{t_T}}  +o(\sqrt{\alpha_{t_T}})
\end{equation}

Combining the lower bounds (<ref>), (<ref>), (<ref>) on the three terms of (<ref>), we get

\begin{align*}
c(\hat{x}_{t_T}(\Pb_{t_T}),\Pb_1) - \hat{c}^{\star}(\Pb_{t_T},t_T)
% &\geq
% -\eta \sqrt{\alpha_{t_T}} \sqrt{\Var_{\Pb_1}(\loss_{\xSVP{,t_T}(\Pb_{t_T})})} +
% (\varepsilon - \varepsilon'(1-\eta)\|u\|) \sqrt{\alpha_{t_T}}
% -\left(3\delta+2\delta/\eta\right) \sqrt{\alpha_{t_T}}
% +o(\sqrt{\alpha_{t_T}}) \\
% &=
\sqrt{\alpha_{t_T}}
\left(
\varepsilon
\varepsilon'(1-\eta)\|u\|
\eta \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
-3\delta - 2\delta/\eta
+ o(1)
\right)\\
\sqrt{\alpha_{t_T}}
\left(
\varepsilon
\varepsilon'\frac{(1-\eta)\delta}{\sup_x \|\loss(x,\cdot)\|}
\eta \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
-3\delta - 2\delta/\eta
+ o(1)
\right)
\end{align*}

By choosing $\eta>0$ such that $\eta \sup_{x\in \cX}\sqrt{\Var_{\Pb_1}(\loss(x,\xi))}< \varepsilon/4$ (which is possible as $\cX$ is compact, $\loss(\cdot,i)$ is continuous for all $i\in \Sigma$, and therefore the $\sup$ is finite), then $\delta>0$ such that $\delta (3+2/\eta) < \varepsilon/4$ and then $\varepsilon'>0$ such that $\varepsilon'\frac{(1-\eta)\delta}{\sup_x \|\loss(x,\cdot)\|} < \varepsilon/4$ we get

\varepsilon
\varepsilon'\frac{(1-\eta)\delta}{\sup_{x\in \cX} \|\loss(x,\cdot)\|}
\eta \sqrt{\Var_{\Pb_1}(\loss(x_1,\xi))}
-3\delta - 2\delta/\eta.

Hence, there exist $T_0 \in \integ$ such that for all $T\geq T_0$ and $u\in \Gamma$, we have
$\Pb_{t_T}(u) \in \mathcal{D}_{t_T}$

\mathcal{D}_{T} :=
\set{\Pb'\in \cP}{c(\hat{x}_{T}(\Pb'),\Pb_1) - \hat{c}^{\star}(\Pb',T) >0}, $$

is the set of disappointing distributions at time $T$. This implies that $\Pb_1 -(1-\eta)\sqrt{\alpha_{t_T}} \cdot\Gamma \subset \mathcal{D}_{t_T}$ for all $T\geq T_0$.
We have

\begin{align}
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^\infty
\left(
c(\hat{x}_T(\hat{\Pb}_T), \Pb_1) > \hat c^{\star}(\hat{\Pb}_T,T)
\right)
\limsup_{T\to\infty}
\frac{1}{a_T} \log \Pb^\infty \left( \hat{\Pb}_T \in \mathcal{D}_T\right) \nonumber\\
\limsup_{T\to\infty}
\frac{1}{a_{t_T}} \log \Pb^\infty \left( \hat{\Pb}_{t_T} \in \mathcal{D}_{t_T}\right) \nonumber\\
&\geq \limsup_{T\to\infty}
\frac{1}{a_{t_T}}  \log \Pb^\infty \left( \hat{\Pb}_{t_T} - \Pb_1 \in -\sqrt{\alpha_{t_T}}(1-\eta) \Gamma\right) \nonumber \\
&= \limsup_{T\to\infty}
\frac{1}{a_{t_T}} \log \Pb^\infty \left( \hat{\Pb}_{t_T} - \Pb_1 \in \sqrt{\frac{a_{t_T}}{t_T}}\cdot -(1-\eta) \sqrt{2}\Gamma\right) \nonumber\\
&\geq \liminf_{T\to\infty}
\frac{1}{a_{T}} \log \Pb^\infty \left( \hat{\Pb}_{T} - \Pb_1 \in \sqrt{\frac{a_{T}}{T}}\cdot -(1-\eta) \sqrt{2}\Gamma\right)
\nonumber \\
&\geq - \inf_{\Delta \in \Gamma^{\into}} \|(1-\eta)\sqrt{2}\Delta\|_{\Pb_1}^2
\label{proof eq: precriptor series of ineq 3} \\
&\geq - (1-\eta)^2 \|\sqrt{2}\varphi_{x_1}(\Pb_1)\|_{\Pb_1}^2 =  - (1-\eta)^2 >-1     \label{proof eq: precriptor series of ineq 4}
\end{align}

where (<ref>) uses the MDP (Theorem <ref>) and  (<ref>) is justified by $\varphi_{x_1}(\Pb_1) \in \Gamma = \Gamma^{\into}$ and $\|\sqrt{2}\varphi_{x_1}(\Pb_1)\|_{\Pb_1} =1$. This inequality contradicts the feasibility of $(\hat{x},\hat{c})$ which completes the proof.

Let $(\hat{x},\hat{c})\in \cX \times \cC$ be a feasible pair of predictor-prescriptor in (<ref>). Let $\Pb \in \cPin$. The goal is to show that

\limsup_{T\to \infty} \frac{|\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)|}{|\hat{c}^{\star}(\Pb,T) - c^{\star}(\Pb)|} \leq 1.

It suffices to show that
for all sequence $(\beta_T)_{T\geq 1} \in \Re_+^{\integ}$ we have[Similarly to the case of predictors, this is equivalent to the desired result, see Lemma <ref>.]

\begin{equation*}
\limsup_{T\to\infty} \frac{1}{\beta_T} |\hat{c}^{\star}(\Pb,T) - c^{\star}(\Pb)| \geq \limsup_{T\to\infty} \frac{1}{\beta_T} |\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)|.
\end{equation*}

The result follows with $\beta_T = |\hat{c}^{\star}(\Pb,T) - c^{\star}(\Pb)|$ for all $T$.
Let $\Pb \in \cPin$. Proposition <ref> ensures that $\lim_{T\to \infty} \sqrt{T/a_T}(\cSVP^{\star}(\Pb,T) - c^{\star}(\Pb)) = \sqrt{2\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}$ where $x^{\star}(\Pb)$ is a minimizer of $c(\cdot,\Pb)$ that has the lowest variance. When $\sqrt{\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}>0$, the proof is analogue to the proof of Theorem <ref> using Proposition <ref>. Suppose $\sqrt{\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))}=0$. For every $x\in \cX$, we have
\cSVP(x,\Pb,T) = c(x,\Pb) + \sqrt{2a_T/T}\sqrt{\Var_{\Pb}(\loss(x,\xi))} \geq c(x^{\star}(\Pb),\Pb) = c(x^{\star}(\Pb),\Pb)+ \sqrt{2a_T/T}\sqrt{\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))} = \cSVP(x^{\star}(\Pb),\Pb,T)$, where the first inequality uses the minimality of $c(x^{\star}(\Pb),\Pb)$ and the second equality uses $\Var_{\Pb}(\loss(x^{\star}(\Pb),\xi))=0$. Hence $\cSVP^{\star}(\Pb,T) = \cSVP(x^{\star}(\Pb),\Pb,T) = c^{\star}(\Pb)$ which implies that the RHS of the desired inequality is 0 and the result is immediate.

Finally, as in the prediction case, SVP prescription enjoys also finite sample guarantees. These guarantees usually depend on complexity measures of the decision set $\cX$ (function class in machine learning). We refer to Theorem 6 of [Maurer and Pontil, 2009] for such a finite sample bound.

§ DISCUSSION AND GENERALIZATIONS

In this paper we propose a framework to construct optimal data-driven learning and decision-making formulations.
We prove that within our framework such optimal formulations do indeed exist and can be made explicit.
In this section we discuss the limitations of our approach and discuss potential directions of generalization.

Perhaps the most restrictive assumption we make is that the set of possible uncertain scenarios $\Sigma$ is finite.
We believe that this assumption is warranted as it avoids intricate topological problems which arise when working with continuous probability measures.
It allows us in particular to state optimal formulations and discuss interesting phase transitions using mostly elementary arguments.
That being said, we suspect that our optimality results can be at least partially generalized to the continuous setting following the strategy proposed by [Van Parys et al., 2020].
Indeed, our constructed optimal predictors and prescriptors have each a natural continuous generalization in all of the considered regimes.
We must point out however, that the subexponential regime considered here requires more delicate arguments than the exponential regime considered in [Van Parys et al., 2020] and hence we stop short from claiming that this generalization is straightforward.

We assume in our paper, as is common, that the data samples are independent and identically distributed. We note though that we took some care in our proofs to not exploit this fact explicitly. Indeed, we merely use that the empirical distribution $\hat{\Pb}_T$ constructed enjoys certain deviation principles (Theorem <ref> and <ref>).
Hence, our analysis should with some effort remain applicable in case the data is generated by any process for which $\hat{\Pb}_T$ verifies the appropriate deviation principles. We refer to [Zeitouni and Dembo, 1998] for several examples of such processes.

Naturally, our optimal formulations depend on the precise notion of optimality considered. The optimality criteria related to the considered out-of-sample guarantee and our considered particular partial order. As for the out-of-sample guarantee, this is a rather standard choice for enforcing out-of-sample performance and is widely adopted by the operations research and machine learning community as we do point out in Section <ref>. For the partial order, other choices may be of interest too as we discuss in Section <ref>. An interesting question is whether the optimal formulations we identify remain optimal also for slightly different partial order and perhaps more fundamentally whether such alternatives even admit a similar notion of strong optimal formulation. Our chosen order has the benefit of being stronger than some other natural orders, such as bias and $L^1$ error. This implies that at the very least our formulations remain optimal also when considering any such weaker orders.

[Shapiro, 2003]
A. Shapiro.
Monte carlo sampling methods.
Handbooks in operations research and management science,
10:0 353–425, 2003.

[Vapnik, 2013]
V.N. Vapnik.
The nature of statistical learning theory.
Springer science & business media, 2013.

[Smith and Winkler, 2006]
J.E. Smith and R.L. Winkler.
The optimizer's curse: Skepticism and postdecision surprise in
decision analysis.
Management Science, 520 (3):0 311–322, 2006.

[Michaud, 1989]
R.O. Michaud.
The Markowitz optimization enigma: Is `optimized' optimal?
Financial Analysts Journal, 450 (1):0 31–42,

[Elmachtoub and Grigas, 2021]
A.N. Elmachtoub and P. Grigas.
Smart “predict, then optimize”.
Management Science, 2021.

[Tikhonov, 1943]
A.N. Tikhonov.
On the stability of inverse problems.
Doklady Akademii Nauk SSSR, 390 (5):0
195–198, 1943.

[Mulvey et al., 1995]
J.M. Mulvey, R.J Vanderbei, and S.A Zenios.
Robust optimization of large-scale systems.
Operations research, 430 (2):0 264–281, 1995.

[Tibshirani, 1996]
R. Tibshirani.
Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society: Series B
(Methodological), 580 (1):0 267–288, 1996.

[Hoerl and Kennard, 1970]
A.E. Hoerl and R.W. Kennard.
Ridge regression: applications to nonorthogonal problems.
Technometrics, 120 (1):0 69–82,

[Hoerl and Kennard, 1970]
A.E. Hoerl and R.W. Kennard.
Ridge regression: Biased estimation for nonorthogonal problems.
Technometrics, 120 (1):0 55–67,

[Koltchinskii et al., 2011]
V. Koltchinskii, K. Lounici, and A.B. Tsybakov.
Nuclear-norm penalization and optimal rates for noisy low-rank matrix
The Annals of Statistics, 390 (5):0
2302–2329, 2011.

[van de Geer, 2016]
S.A. van de Geer.
Estimation and testing under sparsity.
Springer, 2016.

[Maurer and Pontil, 2009]
A. Maurer and M. Pontil.
Empirical bernstein bounds and sample variance penalization.
arXiv preprint arXiv:0907.3740, 2009.

[Markowitz, 1952]
H. Markowitz.
Portfolio selection.
The Journal of Finance, 70 (1):0 77–91, 1952.

[Ben-Tal et al., 2009]
A. Ben-Tal, L. El Ghaoui, and A. Nemirovski.
Robust optimization.
Princeton university press, 2009.

[Delage and Ye, 2010]
E. Delage and Y. Ye.
Distributionally robust optimization under moment uncertainty with
application to data-driven problems.
Operations research, 580 (3):0 595–612, 2010.

[Wiesemann et al., 2014]
W. Wiesemann, D. Kuhn, and M. Sim.
Distributionally robust convex optimization.
Operations Research, 620 (6):0 1358–1376,

[Van Parys et al., 2016]
B. P.G. Van Parys, P.J. Goulart, and D. Kuhn.
Generalized Gauss inequalities via semidefinite programming.
Mathematical Programming, 1560 (1-2):0
271–302, 2016a.

[Van Parys et al., 2016]
B. P.G. Van Parys, P.J. Goulart, and D. Kuhn.
Generalized gauss inequalities via semidefinite programming.
Mathematical Programming, 1560 (1-2):0
271–302, 2016b.

[Bertsimas et al., 2018]
D. Bertsimas, V. Gupta, and N. Kallus.
Data-driven robust optimization.
Mathematical Programming, 1670 (2):0 235–292,

[Kuhn et al., 2019]
D. Kuhn, P.M. 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.

[Gao and Kleywegt, 2016]
R. Gao and A.J. Kleywegt.
Distributionally robust stochastic optimization with wasserstein
arXiv preprint arXiv:1604.02199, 2016.

[Xu et al., 2009]
H. Xu, C. Caramanis, and S. Mannor.
Robustness and regularization of support vector machines.
Journal of machine learning research, 100 (7), 2009.

[Gao et al., 2017]
R. Gao, X. Chen, and A. J. Kleywegt.
Wasserstein distributional robustness and regularization in
statistical learning.
arXiv e-prints, pages arXiv–1712, 2017.

[Vapnik and Chervonenkis, 2015]
V.N. Vapnik and A.Y. Chervonenkis.
On the uniform convergence of relative frequencies of events to their
In Measures of complexity, pages 11–30. Springer, 2015.

[Van Parys et al., 2020]
B. P.G. Van Parys, P.M. Esfahani, and D. Kuhn.
From data to decisions: Distributionally robust optimization is
Management Science, 2020.

[Lehmann and Casella, 2006]
E.L. Lehmann and G. Casella.
Theory of point estimation.
Springer Science & Business Media, 2006.

[Gupta, 2019]
V. Gupta.
Near-optimal bayesian ambiguity sets for distributionally robust
Management Science, 650 (9):0 4242–4260,

[Lam, 2019]
H. Lam.
Recovering best statistical guarantees via the empirical