Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
109,177 characters · 27 sections · 51 citation commands
Calibration of distributionally robust empirical optimization models
Empirical optimization (or sample average approximation (SAA)) is an approach for expected value optimization using the empirical distribution as an alternative model to the unknown true distribution. Misspecification can occur because of incorrect modeling assumptions or estimation uncertainty, and decisions that are made on the basis of an incorrect model can perform poorly out-of-sample if misspecification is ignored. Distributionally robust optimization (DRO) accounts for misspecification in the in-sample problem by optimizing against worst-case perturbations from the “nominal model."
DRO models are typically parameterized by an “ambiguity parameter" $\delta$ that controls the size of the deviations from the nominal model in the worst-case problem. The ambiguity parameter may appear as the confidence level of an uncertainty set or a penalty parameter that multiplies some measure of deviation between alternative probability distributions and the nominal in the worst-case objective. The parameter $\delta$ defines a family of worst-case solutions $\{x_n(\delta) : \delta\geq 0\}$, where $\delta=0$ is empirical/sample-average optimization (i.e., no robustness) with solutions becoming increasingly conservative as $\delta$ increases. (Here, $n$ denotes the size of the historical data set used to construct the robust optimization problem.) The choice of $\delta$ clearly determines the out-of-sample performance of the robust solution. The goal of this paper is to study the out-of-sample properties of DRO and to develop a theory for data-driven calibration of the “robustness parameter" for worst-case maximization problems with concave reward functions.
Several papers DGN16,GKL,Lam,DN discuss DRO from the perspective of empirical optimization with the variance of the reward as a regularizer. Most related is GKL which studies the connection between DRO with (sufficiently smooth) $\phi$-divergence penalties and mean-variance problems when the robustness parameter is small. The most important difference is that GKL studies the in-sample DRO problem while this paper is an out-of-sample analysis. Specifically, we characterize the impact of data variability on the DRO solution and the mean and variance of the out-of-sample reward, which forms the basis of resampling-based calibration methods for selecting the robustness parameter $\delta$. Our analysis also reveals the mechanism by which the out-of-sample expected reward under DRO solutions can exceed that of SAA, a phenomena that has been observed empirically in a number of papers but not fully explained (we discuss this in more detail below).
A common theme in DGN16,GKL,Lam,DN and the present paper is the relationship between DRO and variance regularization of SAA, and it is natural to ask {\it why} such a relationship even exists. In this regard, we show that the in-sample variance of the reward is equal to the sensitivity of the mean under worst-case deviations from the nominal, so optimizing against the worst-case in DRO is almost the same as maximizing the expected reward while controlling worst-case sensitivity to model misspecification (variance). This formalizes discussion in GKL and provides insight into why DRO and variance regularization of SAA are related. Variance regularization is also proposed in ELV as a way to reduce the impact of data variability of the out-of-sample performance of the solution of mean-CVaR portfolio choice problems, though connections to worst-case optimization are not discussed; see also GKL for the relationship between worst-case CVaR and variance regularization.
Also related is DN which develops finite sample probabilistic guarantees for the out-of-sample expected reward generated by robust solutions. One important difference is that DN studies the out-of-sample expected reward while the focus of our paper is the variance/sensitivity reduction properties of DRO and the implications for calibration. Additionally, while the probabilistic guarantees in DN formalize the relationship between data size, model complexity, robustness, and out-of-sample expected reward, these results depend on quantities that are difficult to compute (e.g., the covering number or the VC Dimension), require a bounded objective function, and come with the usual concerns that performance bounds of this nature are loose AML. Note too that DN is a finite sample analysis whereas ours is asymptotic (large sample size), though calibration experiments for small data sets produce results that are consistent with our large sample theory. We also mention DGN16, which provides confidence intervals for the optimal objective value and shows consistency of solutions using Owen's empirical likelihood theory, and Lam which studies the sensitivity of estimates of the expected value of random variables to worst-case perturbations of a simulation model.
Connections between robustness and regularization are studied in BC,BM,GCK,XCM where various worst-case regression and classification problems are shown to be equivalent to the regularized regression and classification problems (Ridge, Lasso, etc.). Compared to this paper and also DN,DGN16,GKL,Lam, one important difference is that the regularizers in BC,BM,GCK,XCM act on the solution while the sensitivity/variance penalty in this paper acts on the reward. The equivalence with solution regularization in BC,BM,GCK,XCM implies that worst-case regression and classification reduces the variance of the {\it solution} (regression estimate) by shrinking it towards the origin. It turns out, however, that this is not a general property of DRO, but is driven by the objective function associated with regression and classification. Indeed, we show in Section (ref) that there are well behaved concave reward functions where the impact of DRO on the SAA solution is opposite to that of a solution regularizer, biasing it away from the origin and increasing its variance.
We comment briefly on various approaches to calibrating DRO models in the literature. One approach is to use {\it high confidence uncertainty sets} that include the true data generating model with high probability, where the confidence level (typically $90\%$, $95\%$, or $99\%$) is a primitive of the model ben2013,bgk-SAA,DY-2010,DGN16,Lam. This has been refined by bgk13 which develops methods for finding the smallest such uncertainty set, though the confidence level remains a primitive of the model. One concern with this approach is that it is “open loop", with confidence levels chosen independent of the data and the objective function. There is, however, no reason why these particular confidence levels should have anything to do with good out-of-sample performance.
A second approach selects the robustness parameter $\delta$ by {\it optimizing an estimate of out-of-sample expected reward} using a resampling procedure like bootstrap or cross-validation. While $\delta$ now depends on the data and the objective function (it is no longer “open loop"), it ignores the multi-objective character of DRO. Indeed, our results show that sensitivity/variance reduction is the first-order benefit in DRO, so optimizing just the mean corresponds to selecting $\delta$ on the basis of (almost) a second-order effect. While optimizing the mean can produce a solution that has a higher out-of-sample expected reward than empirical optimization in certain applications, there are other applications where, by the same criteria, it is optimal not to be robust (i.e., $\delta=0$). In either case, there are typically larger values of $\delta$ where further reduction in the sensitivity/variance is possible with negligible impact on the mean. In contrast to the “high-confidence" approach where classical confidence levels of $90\%$, $95\%$, or $99\%$ produce overly conservative solutions, this approach is likely to be insufficiently robust.
Finally, in the {\it satisfycing approach} of BDS, the decision maker specifies a target level $T$ and finds the “most robust" decision that achieves this target under the worst case {\it in-sample} alternative model. That is, he/she chooses the largest robustness parameter $\delta$ under which the worst-case expected reward exceeds the target $T$, so the target $T$ is a primitive of the problem and the confidence level $\delta$ is optimized.
One surprising property of DRO is that the out-of-sample expected reward can sometimes exceed that of the SAA solution, even though it is a worst-case approach. This has been observed empirically BLSZZ2013,KL,LorcaSun, and is studied in AP for a quadratic reward and one-dimensional decision variable. We show that the difference between the out-of-sample expected reward under its “true" maximizer and the SAA decision is nothing but the “gap" in Jensen's inequality due to the variability of the solution (cf. Figure (ref)), and that the improvement in the out-of-sample expected reward under DRO, should it occur, is precisely the reduction in this “gap" under the DRO solution. Our results show that the change in the expected reward is likely to be small relative to the reduction in worst-case sensitivity, which is the primary benefit of the DRO model.
Finally, we mention the paper WZZ which studies the asymptotic properties of stochastic optimization problems with risk-sensitive objectives.
Given any function $f$ defined over the positive reals, we write $f(\delta) = o(\delta)$ (as $\delta \rightarrow 0)$ provided $\lim_{\delta\rightarrow0}f(\delta)/\delta = 0$, and we write $f(\delta) = O(\delta)$ (as $\delta \rightarrow 0)$ provided there exists $M, \delta_{0} > 0$ such that $f(\delta) \leq M\delta$ for all $\delta \leq \delta_{0}$. Given two stochastic processes $\{X_{n}\}$ and $\{Y_{n}\}$ defined on a common probability space, we write $X_{n} = o_{P}(Y_{n})$ provided for any $\epsilon > 0$, $\lim_{n\rightarrow\infty}\mathbb{P}(|X_{n}/Y_{n}|>\epsilon) = 0$.
We introduce the in-sample DRO model and the notion of worst-case sensitivity in Section (ref). We also show that worst-case sensitivity is equal to the variance of the reward for all sufficiently smooth $\phi$-divergence and that our DRO problem is equivalent to a multi-objective mean-sensitivity problem when the robustness parameter is small. We characterize the statistical properties of the in-sample solutions in Section (ref). We also show that it is possible for DRO to increase the variance of the solution relative to empirical optimization. We characterize the mean and variance of the associated out-of-sample rewards for empirical optimization ($\delta = 0$) in Section (ref) and robust optimization ($\delta > 0$) in Section (ref). In the case of DRO, we show that out-of-sample variance reduction is almost an order of magnitude larger than any change in the mean when the robustness parameter is small. We introduce our calibration method, which is based on resampled estimates of the mean and variance, in Section (ref), and apply this to three examples in Section (ref). We conclude in Section (ref).
Let $f(x,\,Y)$ be a real-valued reward function, where $x\in{\mathbb R}^{d}$ is the decision variable and $Y\in\mathbb{R}^{l}$ a random vector with distribution ${\mathbb P}$. If the distribution $\mathbb P$ of $Y$ is known, we can solve
(assumptions on $f$ will be given later). In many situations, the distribution $\mathbb P$ is not known. Instead, we have historical data $Y_1,\cdots,\,Y_n$ generated {\it i.i.d.} from $\mathbb P$, and would like to use this data set to make a decision that performs well out-of-sample.
When the distribution $\mathbb P$ of $Y$ is not known, it is natural to optimize a sample average approximation of the objective
where ${\mathbb P}_n$ is the empirical distribution associated with $Y_1,\cdots,\,Y_n$. In many situations, however, $x_n(0)$ performs poorly out-of-sample due to differences between the empirical estimate ${\mathbb P}_n$ and the actual population distribution $\mathbb P$.
One approach to this problem is to optimize worst-case versions of the empirical optimization problem (ref). Specifically, let $\delta>0$ be a positive constant and
be the solution of the DRO problem where
is the $\phi$-divergence of ${\mathbb Q}=[q_1,\cdots,\,q_n]$ relative to ${\mathbb P}_n = [p_1^{n},\cdots,\,p_n^{n}]$. While there are important examples of $\phi$-divergence that are not smooth, we assume throughout this paper that $\phi$ is a convex function such that
(additional assumptions will be stated as required). The $\phi$-divergence $\mathcal{H}_\phi(\mathbb{Q} \,|\, {\mathbb{P}}_n)$ measures the deviation of the alternative distribution $\mathbb Q$ from the nominal ${\mathbb P}_n$ and the worst-case model (ref) accounts for errors in the empirical distribution ${\mathbb P}_n$ by optimizing against worst-case perturbations. The size of the perturbations in (ref) is controlled by the robustness parameter $\delta$ which determines the penalty on the adversary for deviating from the nominal. Note that $\delta=0$ gives the empirical model (ref) and solutions become “more conservative" as $\delta$ increases.
It is shown in GKL that if $\phi(z)$ is sufficiently smooth, the worst-case optimization problem (ref) is almost the same as an empirical mean-variance problem. Specifically, if $\phi(z)$ satisfies (ref) and is also twice continuously differentiable in the neighborhood of $z=1$, then
where
is the variance of the reward under the empirical distribution. This shows that worst-case optimization (ref) is actually a multi-objective problem that trades off between maximizing the expected reward ${\mathbb E}_{{\mathbb P}_n}[f(x,\,Y)]$ and minimizing its variance $\mathbb{V}_{{\mathbb P}_n}\big[f(x,\,Y)\big]$.
While the mean-variance objective has been widely adopted, it is generally for reasons unrelated to model uncertainty, and it is natural to ask {\it why} it now appears in relation to a worst-case problem. It turns out that the variance of the reward measures worst-case sensitivity of the nominal model to misspecification. Intuitively, a decision $x$ is sensitive to misspecification if small deviations from the nominal ${\mathbb P}_n$ can have a big impact on the expected reward ${\mathbb E}_{{\mathbb P}_n}[f(x,\,Y)]$. Sensitivity is large if the reward distribution has a large spread since perturbations that affect the tail can have a big impact on the mean. The worst-case optimizer (ref) tries to optimize the expected reward while controlling the worst-case sensitivity to misspecification (spread).
This intuition can be formalized. Given a nominal model ${\mathbb P}_n$ and reward $f(x,\,Y)$, consider the family of distributions $\{{\mathbb Q}(\delta):\,\delta\geq 0\}$ where
Intuitively, $\{{\mathbb Q}(\delta):\,\delta\geq 0\}$ is a family of worst-case deviations from the nominal, with the size of the deviation increasing in $\delta$ (corresponding to a smaller penalty on the $\phi$-divergence in (ref)). Although we have suppressed this from the notation, $\{{\mathbb Q}(\delta):\,\delta\geq 0\}$ depends on the nominal ${\mathbb P}_n$ as well as the reward $f(x,\,Y)$. Given (ref), we define the worst-case sensitivity of the expected reward ${\mathbb E}_{{\mathbb P}_n}[f(x,\,Y)]$ relative to nominal model ${\mathbb P}_n$ as
The following result shows that the worst-case sensitivity is equal to the variance. We require the following assumption.
The proof of the following result can be found in Appendix (ref).
It can be also shown that the sensitivity of the expected reward under different models of misspecification (e.g., Wasserstein and CVaR) corresponds to different measures of spread, and that the associated worst-case problems are mean-sensitivity problems. These results will be reported elsewhere. Worst-case sensitivity is also discussed in Lam for simulated estimates on an expectation when the family of alternative models is defined through a constraint on relative entropy. In this regard, Theorem (ref) holds for all sufficiently smooth $\phi$-divergence and not just for relative entropy. Variance penalties are proposed in ELV as a way to control the sensitivity of solutions of an empirical mean-CVaR portfolio choice problem to data variability, but the connection to worst-case optimization is not discussed.
Robust optimization (ref) defines a family of policies $\{x_n(\delta):\,\delta\geq 0\}$ that balance between expected reward and sensitivity, with the weight on sensitivity increasing in $\delta$. Our eventual goal is to identify values of the parameter $\delta$ such that the corresponding solution $x_n(\delta)$ performs well out-of-sample. While parameters like $\delta$ are commonly chosen by optimizing some estimate of the out-of-sample expected reward using bootstrap or cross-validation (e.g., the regularization parameter in Lasso or Ridge regression), the characterization (ref) shows that worst-case optimization is a multi-objective problem, which suggests that estimates of both the mean and the variance (i.e., sensitivity) should be used to select $\delta$. We provide guidance for this approach by characterizing the impact of the robustness parameter on the mean and the variance of the out-of-sample reward.
An alternative to the “penalty version" of the DRO model (ref) defines set of alternative models defined in terms of a hard constraint on the deviation measure
As in the penalty version, this leads to a family of decisions $\{x_n(\epsilon):\,\epsilon \geq 0\}$ parameterized by the constraint threshold $\epsilon$ in (ref). With sufficient regularity the penalty and constrained versions are related via convex duality in that the solution of (ref) solves (ref) for some choice of $\epsilon$ and vice versa; see Corollary 3 of ben2013 for more details. Specifically, the solution of (ref) is obtained by solving (ref) with $\delta\equiv\delta_n(\epsilon)$
where
and both models generate the same family of solutions. For this reason, we focus on developing an approach to selecting $\delta$ in the penalty formulation of the model with the understanding that it can be applied to selecting $\epsilon$ in the constrained problem.
For the remainder of the paper, unless otherwise stated, all claims, findings, and insights provided are for DRO problems of the form ((ref)). Conditions for the $\phi$-divergence penalty and the reward function $f(x,\,Y)$ will be stated as needed.
The results in Section (ref) show that robust optimization is a multi-objective problem that balances between maximizing the expected reward and minimizing its variance. In this section, we characterize the statistical properties of the robust solution $x_n(\delta)$. These results will be used in the following sections to study the out-of-sample mean and variance (sensitivity) of the reward.
The results in this section use general results on the consistency (Theorem 5.4, SDR) and asymptotic normality (Theorem 5.21, vdV) of sample average optimizers, which are reproduced in Appendix (ref). The following regularity assumptions on $f(x,\,Y)$ will generally be imposed. The results from SDR and vdV can be applied under more relaxed assumptions, though this does not lead to additional insights.
Let $f:{\mathbb R}^d\times{\mathbb R}^l \rightarrow {\mathbb R}$, $Y$ is an $\mathbb{R}^{l}$-valued random vector with distribution $\mathbb{P}$, and
be the maximizer of the expected reward under the population distribution $\mathbb P$.
It follows from Assumption (ref) is that the Hessian matrix $\mathbb{E} _{\mathbb P}\big[\nabla_x^2 f (x,\,Y)\big]$ is negative definite for every $x$, and that $x^\star(0)$ is unique. Observe too that Assumption (ref) is not required for (ref) to hold. Likewise, the relationship between worst-case optimization and mean-variance optimization still holds if $x$ is constrained, though constraints will affect the efficiency of the mean-sensitivity trade-off for the reward that can be achieved.
The following result characterizes the asymptotic properties of the solution of the empirical optimization problem, and follows immediately from results in SDR and vdV which are stated in Appendix (ref).
We now consider the asymptotic distribution of the solution $x_n(\delta)$ of the robust problem (ref). The dual characterization of $\phi$-divergence implies that $x_n(\delta)$ can be obtained by solving
where
is the convex conjugate of $\phi(z)$. If $\psi:{\mathbb R}^d \times {\mathbb R}\rightarrow {\mathbb R}^{d+1}$ is given by
the first-order conditions for $(x_n(\delta),\,c_n(\delta))$ are\footnote{We have added a scaling constant $-\frac{\phi''(1)}{\delta} $ in the second equation. This does not affect the solution of the first-order conditions, but makes the subsequent analysis more convenient.}
Similarly, let
be the solution of the population version of the robust problem (ref) with first-order conditions
Let $\xi(\delta) \in {\mathbb R}^{d\times d}$,\,$\eta(\delta)\in{\mathbb R}$, and $\kappa(\delta)\in{\mathbb R}^{d\times 1}$ be the entries of the matrix
where
and $J_\psi$ denotes the Jacobian matrix of $\psi$.
The first part of the following result shows that $(x_n(\delta),\,c_n(\delta))$ is consistent and jointly asymptotically normal while the second part characterizes its limiting distribution in terms of the limiting distribution of the empirical distribution $x_n(0)$ when $\delta$ is small. Consistency and asymptotic normality can be established using the general results from SDR and vdV (Appendix (ref)). However, both $f(x,\,Y)$ as well as $\phi(x)$ need to be sufficiently regular, so in contrast to Proposition (ref), Assumption (ref) will be required in addition to Assumption (ref).
Theorem (ref) shows (asymptotically) that robust optimization adds a bias $\pi$ to the empirical solution where the magnitude of the bias is determined by the robustness parameter $\delta$. It can be shown that $\pi$ optimizes a trade-off between the loss of expected reward and the reduction in variance:
It has been shown BC,BM,GCK,XCM that various worst-case regression and classification problems are equivalent to regularized versions of these problems (i.e., regression/classification with Ridge, Lasso, etc.). One implication is that robustness induces the bias-variance trade-off associated with regularization, leading to a reduction in the variance of the {\it solution} by shrinking it towards the origin. On the other hand, we showed in Theorem (ref) that robustness adds a bias to the SAA solution in the direction $\pi$ and changes its variance from ${\xi(0)}/{n}$ to ${\xi(\delta)}/{n}$. It is natural to ask whether this corresponds to shrinkage towards the origin and a reduction in the variance of the solution (perhaps when the reward function is concave).
The following example shows that this is not the case, and that robustness can simultaneously bias the SAA solution away from the origin and increase its variance, even when the reward function is concave. More generally, (ref) shows that DRO controls the variance (sensitivity) of the reward, but is only equivalent to regularizing the solution in certain special cases.
Let
where the random variable $Y$ is positive with distribution $\mathbb P$. We assume $h(x) = {x^{-a}}/{(-a)}$ ($a>0$), though we will only substitute this expression for $h(x)$ later in the example.
Given samples $Y_1,\cdots,\,Y_n\sim {\mathbb P}$ of $Y$, the solution $x_n(0)$ of the empirical problem (ref) is the solution of the equation
where the random variable $\hat{Y}_n=(Y_1+\cdots+Y_n)/n$.
For concreteness, suppose that the deviation measure in the robust problem (ref) is the modified $\chi^2$ (see, e.g., GKL). Writing $x_n(\delta) = x_n(0)+ \pi_n\delta + o(\delta)$ for some $\pi_n$, the first-order conditions for (ref) imply
where $\hat{\sigma}_n^Y$ is the sample standard deviation of $Y$ and $\hat{\sigma}_n^Y/\hat{Y}_n$ is an estimate of its coefficient of variation. When $h(x) = {x^{-a}}/{(-a)}$, we have $h'(x)=x^{-a-1}$ and $h''(x) = -(a+1)x^{-a-2}$, so
Observe that $x_n(0)=\hat{Y}^{\frac{1}{a+1}}$. In contrast to Lasso or Ridge, which shrinks the sample average solution towards the origin, robustness introduces a positive bias which pushes it away.
The variance of the robust solution is given by
Therefore, if the covariance of $x_n(0)$ and $x_n(0)^2\big(\frac{\hat{\sigma}_n^Y}{\hat{Y}_n}\big)^2$ is positive, i.e., $\mbox{Cov}_{\mathbb P}[x_n(0),\,x_n(0)^2\big(\frac{\hat{\sigma}_n^Y}{\hat{Y}_n}\big)^2]>0$, robustness increases the variance of the solution.
The upper plot in Figure (ref) shows the distribution of $x_n(0)$ and $x_n(\delta)$ when $Y$ is exponentially distributed with mean $1$, $a=0.05$, and there are $n=10$ data points. The lower plot shows the objective function ${\mathbb E}_{\mathbb P}[f(x,\,Y)]$. When $\delta=0.04$, the variance of the robust solution $x_n(\delta)$ is $0.8$ which is larger than the variance of the solution of the empirical problem, which is $0.1$.
Let ${\mathcal D} = \{Y_1,\cdots,\,Y_n\}$ be data generated i.i.d. under $\mathbb P$, $x_n(0)$ be the solution of the empirical optimization problem (ref) constructed using $\mathcal D$, and $Y_{n+1}$ be an additional sample generated under $\mathbb P$ independent of the original sample. Since $x_{n}(0)$ depends only the data ${\mathcal D}$ and is therefore independent of $Y_{n+1}$ under the population distribution $\mathbb{P}$, it follows that $x_n(0)-x^\star(0)$ is also independent of $Y_{n+1}$ under $\mathbb P$. Proposition (ref) implies
In particular, $x_n(0)$ deviates from $x^{\star}(0)$ because of data variability which is captured by the term involving $Z$ and terms of $o_P(\frac{1}{\sqrt{n}})$, which for our purposes turn out to be negligible. We study out-of-sample performance of $x_n(0)$ by evaluating the mean and variance of the reward $f(x_n(0),\,Y_{n+1})$ over random samples of the data ${\mathcal D}$ and $Y_{n+1}$ generated under $\mathbb P$.
Our subsequent results characterize the impact of robustness through a Taylor series expansion of the mean and variance of the out-of-sample reward when the robustness parameter is small. The following result is a general statement of this expansion, which will streamline some of these derivations. The smoothness and integrability conditions are the same as those stated in Assumption (ref) and guarantee that Taylor series expansions are defined and expected values and variances exist. The proof of this result can be found in Appendix (ref).
We now derive an expansion of the out-of-sample expected reward and variance under the empirical optimal solution, which will serve as a baseline case when studying the out-of-sample performance of robust optimization.
To ease notation, we denote the mean and variance of the out-of-sample reward under $x_n(\delta)$ and the population solution $x^{\star}(\delta)$ as
($\delta=0$ corresponds to empirical optimization). The curvature of the expected reward and the second derivative of the variance of the reward at $x^\star(\delta)$ also appear. We denote these as
where $\nabla_x^2 {\mathbb V}_{\mathbb P}\big[f(x^{\star}(\delta),\,Y_{n+1})\big]$ is defined in (ref).
The mean and variance of the out-of-sample reward depend on the variability of the empirical solution $x_n(0)$ and the properties of the reward function. The following result relates the mean and variance of the out-of-sample reward for the empirical optimizer to those of the population optimizer $x^{\star}(0)$.
Proposition (ref) quantifies the difference between the out-of-sample means and out-of-sample variances for the solution $x^\star(0)$ of the population problem and the empirical solution $x_n(0)$. In particular, (ref) shows that the difference between the expected rewards is increasing in the variance $\frac{\xi(0)}{n}$ of the solution $x_n(0)$ and the curvature $H(0)$ of the expected reward around $x^{\star}(0)$:
This performance gap can be attributed to Jensen's inequality. Specifically, if
denotes the out-of-sample expected reward, then $F(x)$ is strictly concave in $x$ (Assumption (ref)) and
by Jensen's inequality. Since ${\mathbb E}_{\mathbb P}[x_n(0)]=x^{\star}(0) + o(1/\sqrt{n})$
which is precisely the performance gap in (ref) (or equivalently, (ref)).
An illustration of Proposition (ref) is shown in Figure (ref) where (A) is the expected reward $F(x)$ under the population distribution on which $\times$ is the optimal value $\mu^\star(0)$; (B1) is the distribution of $x_n(0)$ and (B2) is the distribution of the out-of-sample reward $f(x_n(0),\,Y)$. The expected out-of-sample reward $\mu_n(0)$ is marked $\times$ at (D) and at the point labelled $\mu_n(0)$. We can see that when $F(x)$ is strictly concave, variability in $x_n(0)$ around its asymptotic mean $x^\star(0)$ leads to a gap between $\mu^\star(0)$ and $\mu_n(0)$ from Jensen's inequality that is shown at (B3). This gap is quantified in Proposition (ref).
We now study the mean and variance of the out-of-sample reward generated by solutions of robust optimization problems $x_n(\delta)$ and characterize the impact of the robustness parameter $\delta$. Our analysis consists of two parts. To begin, we derive expressions analogous to (ref) and (ref) in which the out-of-sample mean (variance) of the reward $f(x_n(\delta),\,Y_{n+1})$ is decomposed into the mean (variance) of the reward associated with the solution $x^\star(\delta)$ of the population problem and an additional component that is determined by the variability of the solution around the asymptotic mean and the curvature of the reward function; see (ref) and (ref). Next, we evaluate the impact of the robustness parameter on the mean and variance of the out-of-sample reward.
We analyze the impact of robustness on the mean of the out-of-sample reward by expanding $\mu_n(\delta) = {\mathbb E}_{\mathbb P}\big[f(x_n(\delta),\,Y_{n+1})\big]$ around $\delta=0$.
To begin, we evaluate the impact of solution variability and the curvature of the expected reward on the out-of-sample expected reward under the robust solution. Suppose that $\phi(z)$ satisfies Assumption (ref) and $f(x,\,Y)$ satisfies Assumption (ref). Recall from Theorem (ref) that the robust solution is asymptotically normal
It follows that the out-of-sample expected reward
Noting (ref), robustness changes the mean of the solution from $x^\star(0)$ to $x^\star(\delta)$ and its asymptotic variance from ${\xi(0)}/{n}$ to ${\xi(\delta)}/{n}$. The expression (ref) is analogous to (ref) but reflects the new mean and variance of the solution. Specifically, the first term is the expected reward under asymptotic mean $x^{\star}(\delta)$ while the second term is the Jensen effect, namely, the reduction in the expected reward ${\mathbb E}_{\mathbb P}\big[f(x^{\star}(\delta),\,Y_{n+1})\big] - {\mathbb E}_{\mathbb P}\big[f(x_n(\delta),\,Y_{n+1})\big]$ due to fluctuations of the robust solution $x_n(\delta)$ around the asymptotic mean $x^{\star}(\delta)$ and the curvature of the expected reward.
To understand the impact of robustness on the out-of-sample expected reward, we expand both terms in (ref) around $\delta=0$ (i.e., the SAA solution). By (ref) and Proposition (ref) (with $\Delta=\pi$) we have
Robustness changes the asymptotic mean of the solution $x_n(\delta)$ from $x^{\star}(0)$ to $x^{\star}(\delta)=x^{\star}(0)+\delta\pi +o(\delta)$ which changes the expected reward. However, (ref) shows that this change is of order $\delta^2$ which is small when $\delta$ is small.
In the case of the Jensen effect we have
The first term is the Jensen effect associated with the empirical solution (ref), while the remaining terms are adjustments to the Jensen effect for $x_n(0)$ due to the change in the variance of the solution from $\xi(0)/n$ to $\xi(\delta)/n$ and the change in the curvature due to the shift in the mean of the solution from $x^{\star}(0)$ to $x^{\star}(\delta)$. If $f(x,\,Y)$ is such that for any matrix $Q\in\mathbb{R}^{d\times d}$, the function $L:{\mathbb R^d}\rightarrow {\mathbb R}$ where
is continuously differentiable, it follows from the definition (ref) of $H(\delta)$ and the expansion (ref) of $x^{\star}(\delta)$ that
where
where $\xi'(0)$ is the derivative of $\xi(\delta)$ with respect to $\delta$ evaluated at $\delta=0$ (Theorem (ref)). Compared to (ref), where the impact of robustness is $O(\delta^2)$, the impact of robustness on the Jensen effect (ref) is $O(\delta)$, coming from the adjustment $\frac{\rho\delta}{2n}$. This term is scaled by a factor $1/n$, so although it is linear in $\delta$, the net effect is small when $\delta$ is small. The expansion of the out-of-sample expected reward is obtained by combining (ref), (ref), and (ref).
We analyze the impact of robustness on the variance of the out-of-sample reward by expanding $v_n(\delta) = {\mathbb V}_{\mathbb P}\big[f(x_n(\delta),\,Y_{n+1})\big]$ around $\delta=0$.
Under Assumptions (ref) and (ref), it is shown in Theorem (ref) that robustness changes the mean of the solution from $x^\star(0)$ to $x^\star(\delta)$ and its asymptotic variance from ${\xi(0)}/{n}$ to ${\xi(\delta)}/{n}$ (see also (ref) and (ref)). To see the impact on the variance of the out-of-sample reward, observe from (ref) that
where $\nabla_x^2 {\mathbb V}_{\mathbb P}\big[f(x^{\star}(\delta),\,Y_{n+1})\big]$ is given in (ref). The first term in (ref) is the variance of the reward $v^{\star}(\delta)$ at the optimal solution $x^{\star}(\delta)$ of the population robust model. The second term is the impact of the variability of the robust solution $x_n(\delta)$ on the variance of the reward. The expansion (ref) is analogous to the expansion (ref) of the variance for the empirical problem, the difference being that it is for the robust solution $x_n(\delta)$ instead of $x_n(0)$.
To see the impact of robustness on the variance of the reward, we expand (ref) around $\delta=0$. Noting (ref), it follows from Proposition (ref) that the first term
where $\nabla_x {\mathbb V}_{\mathbb P}\big[f(x^{\star}(0),\,Y_{n+1})\big]$ is defined in (ref).
As for the second term in (ref) observe that
If $f(x,\,Y)$ is such that for any matrix $Q\in\mathbb{R}^{d\times d}$, the function $M:{\mathbb R^d}\rightarrow {\mathbb R}$ where
is continuously differentiable, the expansion (ref) of $x^{\star}(\delta)$ and the definition of $G(\delta)$ in ((ref)) implies
Since
it follows that
where
The first term in (ref) is from the empirical optimizer (ref) while the term $\frac{\theta\delta}{2n}$ reflects the impact of robustness on the out-of-sample variance. An expansion of the out-of-sample variance $v_n(\delta) = {\mathbb V}_{\mathbb P}\big[f(x_n(\delta),\,Y_{n+1})\big]$ around $\delta=0$ is obtained by combining (ref) and (ref).
Let
be the robust mean-variance frontier (ref). The following result characterizes the frontier in the asymptotic regime when $n$ is large and $\delta$ is small. In addition to Assumption (ref), following assumption is required.
For some perspective on Proposition (ref), note that the mean and variance of the reward under the solution $x^{\star}(0)$ of the robust population problem are given by
(we also get these equations when we let $n\rightarrow\infty$ in ((ref)) and ((ref))) from which it follows that
Since $f(x,\,Y)$ is strictly concave in $x$, the curvature $H(0)$ is negative definite so variance decreases linearly around $\delta=0$. In fact, (ref) shows that both the mean and variance are decreasing in $\delta$ but variance reduction is an order of magnitude larger than the reduction in the mean when $\delta$ is small ($O(\delta)$ vs. $O(\delta^2)$). As $\delta$ increases, however, the quadratic term becomes significant and the mean decreases at an increasing rate. This suggests that the choice of $\delta$ has a significant impact on the out-of-sample reward, and that calibration of $\delta$ should therefore account for both the mean and the variance.
When $n$ is finite, the robust mean-variance frontier $\big\{(\mu_n(\delta),v_n(\delta)):\delta\geq 0\big\}$ deviates from the population frontier (ref) because the solution $x_{n}(\delta)$ is a random variable. Indeed, (ref) and (ref) can be written
showing that difference in out-of-sample expected rewards $\mu_n(\delta)-\mu^{\star}(\delta)$ comes from the variability in $x_n(\delta)$ via the Jensen effect, with a similar interpretation for the variance. The first term in the Jensen effect is from the variability of $x_{n}(0)$ around $x^{\star}(0)$ (see (ref)) while the second term is the modification to the Jensen effect due to the bias that is added to the solution by robustness, which was discussed in (ref)--(ref).
Another interpretation of Proposition (ref) can be obtained by writing the robust mean-variance frontier $(\mu_n(\delta), \, v_n(\delta))$ in terms the mean and variance $(\mu_n(0),\,v_n(0))$ of the out-of-sample reward for the empirical optimal $x_{n}(0)$, which was derived in Proposition (ref).
In this case
so in contrast the population frontier, derivatives are non-zero at $\delta=0$. In the case of the variance, $\beta' H(0)^{-1}\beta < 0$. Since the term $\frac{\theta}{2n}$ is scaled by a factor $1/n$, for $n$ sufficiently large, the derivative is negative and variance reduces linearly around $\delta=0$. The rate of change of the mean is also linear but, for $n$ sufficiently large, $\frac{\rho}{2n}$ is small and variance reduction will dominate. As $\delta$ increases, the quadratic term in (ref) eventually dominates at which point the mean decreases at an increasing rate since the coefficient is negative. Interestingly, the marginal change in the mean is equal to the adjustment to the Jensen effect from robustness (see (ref), (ref) and (ref)).
In summary, (ref) and (ref) show that when $\delta$ is small and $n$ large, the reduction in the variance of the out-of-sample reward under $x_n(\delta)$ is significantly larger than the impact on the mean. These results apply when $x$ is unconstrained. If $x$ is constrained, the mean-sensitivity relationship (ref) still holds, so worst-case optimization is still making a trade-off between expected reward and sensitivity, but the constraints will affect the efficiency that can be achieved.
The term $\frac{\rho}{2n}\delta$ in (ref) is related to the Jensen effect. In particular, robustness changes the mean of the empirical solution from $x_n(0)$ to $x_n(\delta)$ and its variance from $\xi(0)$ to $\xi(\delta)$, and it was shown in (ref)--(ref) that this changes the Jensen effect from
for the empirical solution $x_n(0)$ to
Note that $\rho$ can be positive or negative. It is positive if the bias $\delta\pi$ that is introduced by robustness reduces the loss from the Jensen effect. When this happens, $\mu_n(\delta)$ is larger than $\mu_n(0)$ when $\delta$ is sufficiently small for the linear term in (ref) to dominate the quadratic. That is, although DRO is a worst-case problem, the robust solution can have a larger out-of-sample expected reward than the SAA solution.
While there is no guarantee that $\rho$ will be positive, improvement in the expected reward under robust decisions has been documented empirically in the literature BLSZZ2013,KL,LorcaSun and it will be seen in some of our examples. Regardless of its sign, $\frac{\rho}{2n}\delta$ is small relative to variance reduction, and disappears when $n\rightarrow \infty$.
Figure (ref) illustrates the key theoretical insights from this paper. Here, (A) is the expected reward ${\mathbb E}_{\mathbb P}[f(x,\,Y)]$ under the population distribution, (B1) is the distribution of the solution of the empirical problem $x_n(0)$, (B2) is the distribution of the out-of-sample reward $f(x_n(0),\, Y_{n+1})$, and (B3) is the “Jensen effect" for the empirical problem; (B1), (B2), and (B3) were previously shown in Figure (ref). (C1), (C2), and (C3) are counterparts for the robust problem. Specifically, (C1) is the distribution of the robust solution, $x_n(\delta)$; (C2) is the distribution of the out-of-sample reward $f(x_n(\delta),\,Y)$ under the robust solution; (C3) shows the Jensen effect $\mu^\star(\delta)-\mu_n(\delta)$. Indicated on (A) are the optimal rewards $\mu^\star(0)$ and $\mu^\star(\delta)$ of the population problems (see (ref), (ref) and (ref)).
DRO makes a trade-off between expected reward and sensitivity. For the example in Figure (ref), this corresponds to adding a bias to the empirical solution that pushes $x_n(0)$ towards the flat part of the reward function. This changes the distribution of the solution from (B1) to (C1) and the distribution of the out-of-sample reward from (B2) and (C2). In particular, pushing the solution towards the flat part of the objective reduces the variance of the out-of-sample reward (compare the spread of (B2) and (C2)) and changes the mean reward from $\mu_n(0)$ to $\mu_n(\delta)$. Theorem (ref) quantifies the dependence of the mean and variance on $\delta$.
Robustness changes the Jensen effect from $\mu^\star(0)-\mu_n(0)$ for the SAA problem to $\mu^\star(\delta)-\mu_n(\delta)$ for the robust problem, indicated at (B3) and (C3). As indicated in the equation (ref) for $\rho$, the change in the magnitude of the Jensen effect is determined by the change in the variability of the solution and the change in the curvature of the reward, which can also be see in this plot. For this example, the Jensen effect for the robust problem is smaller (i.e., $\rho>0$) and robustness improves the out-of-sample expected reward ($\mu_n(\delta)>\mu_n(0)$) when $\delta$ is sufficiently small, which was discussed in Section (ref) . This is shown at (D).
Our analysis shows that relative to the SAA solution, substantial sensitivity reduction is possible with minimal impact on the expected reward when the robustness parameter (uncertainty set) is small. These results say nothing about this trade-off when $\delta$ is large, but the benefits of robustness in all of our experiments (Section (ref)) are diminishing in $\delta$. This suggests that the “small $\delta$" regime is the one that is most interesting.
Proposition (ref) shows that when the ambiguity parameter $\delta$ is small, variance reduction is the first-order benefit of robust optimization while the impact on the mean is (almost) an order of magnitude smaller. This implies that $\delta$ should be calibrated by trading off between the out-of-sample mean and variance and not just by optimizing the mean alone, as is commonly done when tuning the free parameters (e.g., in Machine Learning applications).
Observe, however, that the robust mean-variance frontier
cannot be computed by the decision maker because he/she does not know the data generating model $\mathbb P$, so it is natural to approximate the frontier using resampling methods. One such approach uses the well known {\it bootstrap} procedure ET, which we now describe, and formally state in Algorithm (ref).
Specifically, suppose the decision maker has a data set $\mathcal{D} = \{Y_1,\cdots,\,Y_n\}$ and the associated empirical distribution ${\mathbb{P}}_{n}$. To approximate the out-of-sample behavior of different possible data sets (of size $n$), one may generate a so-called bootstrap data set, call it $\mathcal{D}^{(1)}$, by simulating $n$ new i.i.d. data points from the empirical distribution ${\mathbb{P}}_{n}$. Associated with this bootstrap data set is the bootstrap empirical distribution ${\mathbb{P}}^{(1)}_{n}$ ET. This process can be repeated as many times as desired, with $\mathcal{D}^{(j)}$ and ${\mathbb{P}}^{(j)}_{n}$ denoting the bootstrap data set and bootstrap empirical distribution generated at repeat $j$. We denote the number of bootstrap samples by $k$ in Algorithm (ref).
For each $\mathcal{D}^{(j)}$ and ${\mathbb{P}}^{(j)}_{n}$, we can compute (a family of) robust decisions $x^{(j)}(\delta)$ by solving the robust optimization problem defined in terms of the bootstrap empirical distribution ${\mathbb{P}}^{(j)}_{n}$ over a specified set of $\delta$ (step 4). The mean and variance of the reward for $x^{(j)}(\delta)$ under the {\it original empirical distribution} ${\mathbb{P}}_{n}$, which we denote by $\mu^{(j)}(\delta)$ and $v^{(j)}(\delta)$ in steps 5 and 6, can then be computed. The $k$ bootstrap samples produces the mean-variance pairs $(\mu^{(j)}(\delta),\,v^{(j)}(\delta))$, $j=1,\cdots,\,k$. Averaging these gives an estimate of the out-of-sample mean-variance frontier (steps 7 and 8).
In the next section, we consider three applications, inventory control, portfolio optimization, and logistic regression. We illustrate various aspects of our theory and show how the bootstrap robust mean-variance frontier given in Algorithm (ref) can be used to effectively calibrate ambiguity parameters in such settings.
We consider three examples. The first is a simulation experiment of the robust inventory control problem that illustrates key elements of our theory, while the next two examples are out-of-sample tests with real data. For these experiments, the penalty function ${\mathcal H}_\phi$ is relative entropy.
We first consider a simulation example with reward
This is a so-called inventory problem where $x$ is the order quantity (decision), $Y$ is the random demand, and $r$ and $c$ are the revenue and cost parameters.
The demand distribution $\mathbb{P}$ is a mixture of two exponential distributions, ${\rm Exp}(\lambda_{L})$ and ${\rm Exp}(\lambda_{H})$, where $\lambda_{L}$ and $\lambda_{H}$ are the rate parameters. This may correspond to two demand regimes (high and low) with different demand characteristics. For this numerical example, we set the mean values as $\lambda_{L}^{-1} = 10$ and $\lambda_{H}^{-1} = 100$, and revenue and cost parameters $r = 30$ and $c = 2$. The probability that demand is drawn from the low segment is $0.7$ (or equivalently, the probability that demand is drawn from the high segment is $0.3$).
We run the following experiment. The decision maker is initially shown $n$ data points $Y_{1},\ldots,Y_{n}$ drawn i.i.d. from the mixture distribution $\mathbb{P}$. The decision maker then optimizes the robust objective function under the empirical distribution ${\mathbb{P}}_n$ to produce the optimal robust order quantity $x^{\star}_{n}(\delta)$. Another data point $Y_{n+1}$ is then generated from $\mathbb{P}$, independent of the previous data points, and the objective value $f(x^{\star}_{n}(\delta),Y_{n+1})$ is recorded. The out-of-sample mean and variance $\mathbb{E}_{\mathbb{P}}\big[f(x^{\star}_{n}(\delta),Y_{n+1})\big]$ and $\mathbb{V}_{\mathbb{P}}\big[f(x^{\star}_{n}(\delta),Y_{n+1})\big]$ are approximated by running the experiment $K$ times, where $K$ is some large number, each time using a newly generated data set $Y_{1},\ldots,Y_{n},Y_{n+1} \sim \mathbb{P}$; the sample mean and variance are computed over the $K$ repeats.
In Figure (ref), we plot the pair $(\mathbb{E}_{\mathbb{P}}\big[f(x^{\star}_{n}(\delta),Y_{n+1})\big], \mathbb{V}_{\mathbb{P}}\big[f(x^{\star}_{n}(\delta),Y_{n+1})\big])$ for different sample sizes $n = 10, 30, 50$ with the marks on a given line correspond to different values of $\delta$; the right-most mark corresponds to $\delta = 0$ (empirical). We also plot the “true" robust mean-variance frontier, i.e., the pair $(\mathbb{E}_{\mathbb{P}}\big[f(x^{\star}(\delta),Y)\big], \mathbb{V}_{\mathbb{P}}\big[f(x^{\star}(\delta),Y)\big])$, which is independent of $n$.
Consistent with Theorem (ref), we observe significant out-of-sample sensitivity (variance) reduction when $\delta$ is small with minimal impact on the out-of-sample expected reward. Our theory says nothing about the impact of large values of $\delta$, though we see that the benefit of robustness is diminishing as $\delta$ increases, with the rate of sensitivity reduction diminishing and the expected reward being reduced at an increasing rate, as $\delta$ increases.
Figure (ref) shows that as the sample size $n$ increases, the gap between the out-of-sample mean-variance frontiers and the “true" robust mean-variance frontier gets smaller. This gap can be explained by Proposition (ref) which shows that the difference between these frontiers should go to zero like $O(n^{-1})$. This is shown in Figure (ref) which plots the maximum gap (over $\delta$) between the out-of-sample frontier and the true frontier under the true frontier for different values of $n$.
In the previous section, we proposed the bootstrap frontier as an approximation to the out-of-sample frontier. We next investigate the quality of this approximation for various sample sizes $n$. From the perspective of calibration, it is not necessary for the bootstrap frontier to equal the out-of-sample frontier, it need only preserve the relative shape. For example, if the only difference between the bootstrap frontier and the out-of-sample frontier was that it was double its size (in both the mean and variance), the choice of $\delta$ should be the same when using either frontier since the relative trade-off between mean and variance is identical. In light of this observation, in Figures (ref) (A), (B), and (C) we plot the normalized bootstrap and out-of-sample frontiers, where the change in the mean and variance has been normalized to 1, for various sample sizes $n = 10, 30, 50$, respectively. It is clear that as the sample size increases, the bootstrap frontier more closely approximates the relative shape of the out-of-sample frontier.
In our second application, we consider real monthly return data from the “10 Industry Portfolios” data set of French. The reward function is exponential utility of returns
where $x\in\mathbb{R}^{d}$ is the portfolio vector (decision variables), $R\in\mathbb{R}^{d}$ is the vector of random returns, and $\gamma$ is the risk-aversion parameter. To simplify the experiments, we choose a risk-aversion parameter $\gamma = 1$. For the purposes of this example, we impose a budget constraint $1' x = 1$ and assume that asset holdings are bounded, $-1\leq x_{i}\leq 1$, $i=1,...,d$.
We conduct the following experiment. We have $d = 10$ assets and are interested to see how robust optimization and our approach for calibrating $\delta$ perform when we estimate the $10$-dimensional joint distribution with relatively few data points ($n = 50$, for the time period April 1968 to June 1972). The robust portfolios will be tested on the empirical distributions for monthly returns of future 50 month windows, July 1972 to September 1976, October 1976 to December 1980 and January 1981 to March 1985 that do not overlap with the training set.
To begin, we solve the robust portfolio choice problem using the 50 monthly returns for the period April 1968 to June 1972 for different values of $\delta$ and construct the robust mean-variance frontier using the bootstrap procedure described in Algorithm (ref). Figure (ref) shows this frontier, around which we also mark the $+/-$ one standard deviations of the bootstrap samples in both the mean and variance dimensions. Empirical optimization corresponds to the point $\delta = 0$, and as predicted by Theorem (ref), there is significantly more reduction in the variance as compared to the mean when $\delta$ is close to $0$. Our theory does not apply when $\delta$ is large. However, it shows that significant out-of-sample sensitivity reduction with minimal impact on the mean should be expected when $\delta$ is small, while Figure (ref) suggests that the benefits of robustness are diminishing in $\delta$, with the rate of sensitivity (variance) reduction decreasing and the rate of mean reduction increasing at $\delta$ increases\footnote{While our results apply in the regime when $\delta$ is small, we believe that similar methods can be used to derive expansions of the solution and out-of-sample reward in orders of $\eta\equiv 1/\delta$ around the solution of the DRO problem when $\eta=0$ ($\delta=\infty$), and to study the out-of-sample performance of DRO solutions in this regime. Our experiments suggest that this is the less interesting part of the robust mean-variance frontier.}.
Calibration and Out-of-sample Tests: The bootstrap frontier estimates the out-of-sample mean and variance for different decisions and can be used to calibrate $\delta$. For this example, the rate of variance reduction relative to the loss in the mean is substantial for $\delta\leq 5$, but this begins to diminish (and the cost of robustness increases) once $\delta$ exceeds $5$. A value of $\delta$ between $2$ and $5$ seems reasonable. While values of $\delta > 10$ may be preferred by some, the balance clearly tips towards loss in mean reward relative to variance reduction/robustness improvement.
Note also that a classical approach to calibration which optimizes the bootstrap estimate of the expected reward and ignores objective variability would select $\delta = 0$. This corresponds to empirical optimization and completely nullifies all the benefits of the robust model. More generally, while it is possible for DRO to produce solutions that out-perform empirical optimization in terms of the out-of-sample expected reward, as proven in Theorem (ref) such improvements are in general small relative to that of the variance reduction (when $\delta$ is small), and such solutions cannot be guaranteed even when model uncertainty is substantial, as shown by the portfolio choice example.
It is also interesting to compare calibration using the bootstrap frontier with the decisions obtained by solving the robust optimization problem
where the threshold $Q_{n}(\alpha)$ in the uncertainty set
is the $(1-\alpha)$-quantile of the distribution of $\mathcal{H}(\mathbb{Q}\,|\,\mathbb{P}_{n})$ that we generate by simulating distributions ${\mathbb Q}$ by bootstrapping from ${\mathbb P}_n$. Confidence levels $1 - \alpha$ with value $90\%$, $95\%$, or $99\%$ are commonly suggested in the robust optimization literature.
It follows from duality that for any threshold $Q_n(\alpha)$ there is a unique ambiguity parameter value $\delta=\delta_{\alpha} > 0$, for which the solution of (ref) coincides with our robust solution $x(\delta_{\alpha})$; see Corollary 3 in ben2013 and also Appendix (ref). In Table (ref) we report the ambiguity parameter values $\delta_{\alpha}$ for significance levels $\alpha$ corresponding to different points on the robust mean-variance frontier in Figure (ref).
{
}
While robust decisions associated with the “classical" significance levels of $\alpha=0.01, 0.05, 0.1$ in Table (ref) may or may not perform well out-of-sample in any given application, it is clear that the range of $\delta_\alpha$ associated with these significant levels is limited. This directly impacts the range of possible solutions available to the decision maker, which in this example are concentrated on the “extremely conservative" region of the bootstrap frontier (Figure (ref)). The values of $\delta \leq 10$ associated with the desirable part of the frontier in Figure (ref) correspond to significance levels $\alpha$ very close to $1$. These significance levels are difficult to estimate using simulation because the associated quantiles of ${\mathcal H}({\mathbb Q}\,|\,{\mathbb P}_n)$ are very close to $0$. While the asymptotic properties of ${\mathcal H}({\mathbb Q}\,|\,{\mathbb P}_n)$ can be used to estimate $\alpha$ when the support of the data generating distribution $\mathbb P$ is finite and $\phi(z)$ is sufficiently regular, this seems pointless if we treat $\alpha$ as a parametrization of the trade-off between mean and sensitivity and accept that there is nothing special about classical significance levels when it comes to out-of-sample performance.
We next analyze the out-of-sample performance of the robust solutions obtained by solving the in-sample problem with $\delta = 1, 2, 3, 5, 10$ (as suggested by the bootstrap frontier in Figure (ref)), the solutions of (ref) corresponding to $\delta_{\alpha} = 30$ ($\alpha = 0.10)$, $\delta_{\alpha} = 31$ ($\alpha = 0.05)$, $\delta_{\alpha} = 33$ ($\alpha = 0.01)$, and the solution of the empirical optimization problem (i.e., the robust solution with $\delta = 0$). We test each of the solutions on three out-of-sample test sets of data size $n = 50$ that do not overlap with the training data. Out-of-sample results are shown in Figure (ref). Note that in the figure we report the mean and variance of the utility function $f(x,R)$ defined in (ref), which is consistent with the framework of the robust optimization model in this paper.
Figure (ref) consistently shows that as the value of $\delta$ (“robustness") increases from zero, the mean performance degrades but the objective variability reduces, which is expected from our theory. Consistent with the bootstrap frontier (Figure (ref)), the portfolios associated with “high confidence uncertainty sets" have low variance though the impact on expected utility is substantial.
As final application we apply robust optimization to logistic regression which we evaluate on the WDBC breast cancer diagnosis data set Lichman.
The reward function for logistic regression is given by
where $Y_0\in\{-1,\,1\}$ is the binary label, $Y$ is the vector of covariates, and $x$ and $x_0$ are decision variables representing coefficients and intercept, respectively, of the linear model for classification. Ordinary logistic regression is formulated as the maximization of the sample average of (ref).
To demonstrate the out-of-sample behavior of robust maximum likelihood, we solve the ordinary/robust likelihood maximization problem using the first half of the WDBC breast cancer diagnosis data set Lichman, i.e., 285 out of the 569 samples, and compute the log-likelihood and the variance of the log-likelihood of the resulting model using the remaining half of the samples, i.e., 284 out of 569. Figure (ref) shows both the bootstrap frontier and the frontier obtained from the out-of-sample test. Once again, choices of $\delta$ that deliver good out-of-sample log-likelihood can be obtained using the bootstrap estimate of the robust frontier with small values of $\delta$ delivering significant sensitivity (variance) reduction with minimal impact on the expected reward. As in the case of Figure (ref), the benefits of robustness diminish as $\delta$ increases.
Proper calibration of DRO models requires a principled understanding of how the distribution of the out-of-sample reward depends on the “robustness parameter." In this paper, we studied out-of-sample properties of robust empirical optimization and developed a theory for data-driven calibration of the robustness parameter.
Robustness is closely related to controlling the variance of the reward distribution as this reduces sensitivity of the mean reward to misspecification. Our main results show that the first-order benefit of “little bit of robustness" is a significant reduction in the variance of the out-of-sample reward while the impact on the mean is almost an order of magnitude smaller. Our results imply that the robustness parameter should be calibrated by making trade-offs between estimates of the out-of-sample mean and variance.
To calibrate the robustness parameter, we introduced the robust mean-variance frontier and showed that it can be approximated using resampling methods like the bootstrap. We applied the robust mean-variance frontiers to three applications: inventory control, portfolio optimization and logistic regression. Our results showed that classical calibration methods that match “standard" confidence levels (e.g., $95\%$) are typically associated with an excessively large robustness parameter and overly pessimistic solutions that perform poorly out-of-sample, while ignoring the variance and calibrating purely on the basis of the mean can lead to a robustness parameter that is too small and a solution that misses out on the first-order benefits of robust optimization.
J. Gotoh is supported in part by JSPS KAKENHI Grant 19H02379, 19H00808, and 16H01833. M.J. Kim is supported in part by the Natural Sciences and Engineering Research Council (NSERC) Discovery Grant RGPIN-2015-04019. A.E.B. Lim is supported in part by the Singapore Ministry of Education Academic Research Fund Tier 2 MOE2016-T2-1-086.