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.
65,685 characters · 19 sections · 32 citation commands
Worst-case sensitivity
{\bf Key words:} Distributionally robust optimization, worst-case sensitivity, generalized measure of deviation, model uncertainty, uncertainty sets, regularizer.
Consider a cost function $f(x, Y)$ where $x$ is the decision and $Y$ is a discrete random variable with (nominal) distribution ${\mathbb P}=[p_1,\cdots, p_n]$. For example, $\mathbb P$ could be the empirical distribution associated with a historical sample of $Y$'s generated {\it iid} from some unknown distribution. We would like to find a decision that performs well out-of-sample, a candidate for which is the minimizer of the sample average approximation (SAA)
In many situations, the solution of this problem does not perform well out-of-sample because the in-sample model is misspecified. If the expected cost of the in-sample optimizer is sensitive to perturbations of this model, the out-of-sample expected cost may increase significantly because of differences between the in- and out-of-sample distributions. One approach to account for model misspecification is Distributionally Robust Optimization (DRO), where decisions are obtained by optimizing the worst-case expected cost over a family of alternative models. More generally, we would like to find a decision that performs well (in-sample) and continues to perform well when the in-sample model is incorrect.
Let ${\mathcal Q}(\varepsilon)$ be an {\it uncertainty set} of size $\varepsilon$, specifically, a set of probability distributions containing the nominal distribution $\mathbb P$ that is increasing in $\varepsilon$ and degenerates to the nominal distribution ${\mathcal Q}(0) = \{{\mathbb P}\}$ when $\varepsilon=0$. For example, ${\mathcal Q}(\varepsilon)$ could be a set of the form $\{{\mathbb Q}\,| d({\mathbb Q}\,|{\mathbb P})\leq \varepsilon\}$ where $d({\mathbb Q}\,|{\mathbb P})$ is $\phi$-divergence or the Wasserstein metric. The worst-case expected cost with respect to ${\mathcal Q}(\varepsilon)$ is
Distributionally Robust Optimization (DRO) is the worst-case problem
We refer to $V$ as the {\it value function} of the worst-case problem which, under the assumptions in this paper, is increasing, continuous and concave in $\varepsilon$. When it is clear from the context, we write $V(\varepsilon) \equiv V(\varepsilon; f(x,\cdot))$ if $f$ and $x$ are fixed and we are concerned about the dependence of $V$ on $\varepsilon$, or $V(\varepsilon, x)\equiv V(\varepsilon; f(x,\cdot))$ if we are interested in an optimization problem over $x$. The solution of the DRO problem is denoted by $x(\varepsilon)$.
Suppose $x$ is fixed and $V(\varepsilon, x)$ has a finite right derivative in $\varepsilon$ at $\varepsilon=0$. The {\it worst-case sensitivity} is the right derivative of the value function at $\varepsilon=0$:
When the sensitivity is large, small deviations from the nominal distribution can result in a large increase in the expected cost; such a decision is not robust.
We show under mild conditions that a large class of DRO problems can be interpreted as multi-objective problems that tradeoff between expected cost and some measure of sensitivity. This measure of sensitivity is bounded above by worst-case sensitivity (ref) where the bound is tight when $\varepsilon$ vanishes. This shows that DRO is fundamentally a tradeoff between mean and sensitivity, generalizing an interpretation of the “variance regularizer" from gotoh2018robust where the penalty form of DRO with smooth $\phi$-divergence was shown to be equivalent to a mean-variance problem when uncertainty sets were small, and unifying recent results connecting various DRO models and “regularized SAA".
We derive explicit expressions for worst-case sensitivity (ref) for a number of popular uncertainty sets including smooth $\phi$-divergence, total variation, “budgeted uncertainty" (i.e. hard constraints on the likelihood ratio), and the Wasserstein distance, which are summarized in Table (ref). Under standard assumptions, worst-case sensitivity is a {\it generalized measure of deviation} rockafellar2006generalized. Intuitively, sensitivity is large if small errors in the nominal model---particularly, the probability of extreme costs---have a big impact on the mean, which will be the case if the spread of the cost distribution is large. Sensitivity can be reduced by selecting a decision with a smaller spread, and the equivalence between DRO mean-sensitivity (spread) optimization shows that this is precisely what it is doing. Different uncertainty sets correspond to different measures of spread, which determines the nature of the DRO solutions, while the tradeoff between expected cost and sensitivity is determined by the size of the uncertainty set.
The closed-form expressions we derive for worst-case sensitivity can be used to {\it select the uncertainty set} that is most appropriate for any given application. For example, DRO with “budgeted uncertainty" controls the spread of the “good" side of the cost distribution (Table (ref)). Doing so, however, may result in solutions that increase the length of the “bad" side of the tail, making it a poor choice in applications where losses can be large. Indeed, it is possible for the DRO solution under one uncertainty set (e.g., “budgeted uncertainty") to be less robust than SAA from the perspective of another (e.g., smooth $\phi$-divergence); an inappropriate choice of uncertainty set can result in the SAA optimizer being replaced by a decision that is even less robust. Finally, for the inventory problem, $L_1$ Wasserstein sensitivity is independent of the decision, which makes it a poor choice of uncertainty set for this application.
We review the relevant literature in Section (ref). In Section (ref), we show how well-known duality results for DRO allow us to view all DRO problems as a tradeoff between mean cost and worst-case sensitivity when uncertainty sets are small. Under standard assumptions, these sensitivity measures are also measures of spread. We derive explicit expressions for worst-case sensitivity for a number of different uncertainty sets in Section (ref). Examples are presented in Section (ref).
\remark There are uncertainty sets where the right derivative $V'(0^+)$ of the worst-case problem is unbounded. For example, when $d({\mathbb Q}\,|\,{\mathbb P})$ is sufficiently smooth $\phi$-divergence, $V(\varepsilon)-V(0)$ is $O(\sqrt \varepsilon)$ and $V'(0^+)$ is unbounded, so the definition (ref) is not helpful. If $V(\varepsilon) - V(0) \sim O(g(\varepsilon))$, where $g(\varepsilon)$ is strictly concave and increasing in $\varepsilon$ with $g(0)=0$, we define worst-case sensitivity (with growth rate $g(\varepsilon)$) as
in which case
As in (ref), optimizing the worst-case cost $V(\varepsilon, x)$ is again a tradeoff between expected cost and sensitivity, the only difference being that that robustness parameter $\varepsilon$ no longer appears linearly. Since $V(\varepsilon)$ is concave and increasing, so too is $g(\varepsilon)$, and $g(0)=0$.
While the DRO (and robust optimization) literature is very large, the focus has been on methodology for solving worst-case problems for a diverse range of uncertainty sets and applications ben1989,ben2013robust,ber2004,del2010,hansen2008robustness,lim2007pricing,george2006ROsurvey,pet2000,Guzin2019newsvendorTV. While the motivation for DRO is to find decisions that are insensitive to model uncertainty, worst-case solutions can be sensitive to the choice of the uncertainty set, and “robust" solutions under one uncertainty set can be less robust than the SAA solution under another. There is little guidance on how the uncertainty set should be chosen for a given application.
When it comes to size, much of the literature suggests that $\varepsilon$ be chosen so that the uncertainty set ${\mathcal Q}(\varepsilon)$ contains the true model with high probability (e.g., $95\%$). This ignores the multi-objective nature of DRO, and there is also little reason to believe that a pre-ordained confidence level selected independently of data and objective always leads to a “good" decision for all applications\footnote{Indeed, extensive calculations with a state of the art data science methods and otherworldly computational power adams1995hitch suggests that the answer is more likely to be $42\%$.}. A second approach treats $\varepsilon$ as a free parameter, like the regularization parameter in regression, chosen to optimize an estimate of out-of-sample expected cost obtained from cross-validation or the bootstrap. While this accounts for both data and the objective, it ignores the sensitivity reduction objective intrinsic to DRO. It is easy to construct examples with high levels of model uncertainty where $\varepsilon=0$ (SAA) optimizes the resampled estimate of the out-of-sample cost lim2020calibration. If sensitivity is ignored, this approach recommends that it is optimal not to be robust.
Worst-case sensitivity (ref) is defined in lam2016robust where it is used to study the accuracy of simulated estimates of the mean of a random variables. However, this paper does not consider implications for robust optimization, and only considers uncertainty sets defined in terms of relative entropy (a special case of smooth $\phi$-divergence).
The connection between worst-case sensitivity and “minimally robust" DRO with smooth $\phi$-divergence penalty functions is discussed in gotoh2018robust,lim2020calibration, with gotoh2018robust showing that worst-case sensitivity corresponds to the variance of the reward, and lim2020calibration studying the out-of-sample properties of the associated mean-variance frontier. The paper Duchi2017variance derives high-probability performance bounds for the out-of-sample expected reward for solutions of variance-regularized loss minimization. The present paper derives worst-case sensitivity {\it for uncertainty sets beyond smooth $\phi$-divergence}, provides elementary arguments linking DRO and mean-sensitivity optimization under very mild assumptions, and shows that worst-case sensitivity is generally a measure of spread. The mean-sensitivity connection shows that DRO is intrinsically a tradeoff between minimizing the expected cost and controlling the spread of the cost distribution under the nominal, with different uncertainty sets giving rise to different measures of spread. Closed form expressions for worst-case sensitivity make this tradeoff explicit, and can also be used to select the family and size of the uncertainty set in any given application.
Several papers discuss the relationship between DRO and “regularized SAA". For example, blanchet2019,gao2017wasserstein,kuhn2020WassersteinSurvey,abadeh2015distributionally show that worst-case regression and classification problems with the Wasserstein metric are equivalent to regularized versions of these problems. More generally, bertsimas2018,blanchet2019,Duchi2017variance,gao2017wasserstein,kuhn2020WassersteinSurvey,abadeh2015distributionally,Xu2010 consider worst-case optimization for a particular uncertainty set and derive the corresponding “regularized SAA" problem. We unify these ideas by showing that the “regularizer" is worst-case sensitivity. We also show that it is a “generalized measure of deviation" rockafellar2006generalized and derive an explicit expression for several popular uncertainty sets. These expressions show how an uncertainty set affects the solution of a DRO model, and can be used to select the family and size of the uncertainty set in a given application.
Variance (sensitivity) reduction properties of DRO solutions have also been observed empirically in the literature. In a network model of project management karthik2019crashing, simulations show that robustness prioritizes reducing the variance of the cost (activity duration) over its mean, while kim2015MAB shows variance reduction of the out-of-sample cost under the solution of a dynamic DRO problem. The solution of a worst-case newsvendor application karthik2020inventory is shown to be optimal for a risk-neutral model with a heavy-tailed demand distribution for the demand, thus controlling the impact of extreme events on the cost.
As a final note, while DRO controls the spread (sensitivity) of the cost, robustness can reduce but also increase the out-of-sample variance of the solution (e.g. solution variability decreases for robust classification and regression models that are equivalent to $L_p$ solution regularization bertsimas2018,blanchet2019,gao2017wasserstein,abadeh2015distributionally,Xu2010 while gotoh2018robust gives an example where solution variability increases).
We reinterpret duality results from the perspective of mean-sensitivity tradeoffs and show, under mild conditions, that DRO problems are mean-sensitivity problems, that worst-case sensitivity is a tight upper bound of “DRO sensitivity" being equal in the limit $\varepsilon\downarrow 0$, and that worst-case sensitivity is a measure of the spread of the cost distribution. The purpose of this section is to motivate our study of worst-case sensitivity by putting it in the context of classical results and highlighting the cost-sensitivity tradeoff is intrinsic to DRO.
Recall the worst-case objective (ref). Since uncertainty sets ${\mathcal Q}(\varepsilon)$ are increasing in $\varepsilon$ and contain the nominal $\mathbb P$, the worst-case expected cost is equal to the nominal expected cost when $\varepsilon=0$ and monotonically increasing in $\varepsilon$ (see Figure (ref)). It follows that there is a function ${\mathcal A}\big(\varepsilon; f(x, Y)\big)$, which we refer to as the {\it ambiguity cost}, that is non-negative and increasing in $\varepsilon$ such that ${\mathcal A}\big(0; f(x, Y)\big)=0$ and
For every $\varepsilon$, we define {\it average sensitivity}
It follows that the worst-case problem is a mean-sensitivity problem:
When $\varepsilon=0$, the robust decision maker optimizes the SAA. As $\varepsilon$ increases, he/she absorbs a larger expected cost in return for a lower sensitivity, as illustrated in Figure (ref).
Suppose that $V(\varepsilon)$ is right differentiable at $\varepsilon=0$. By (ref), average sensitivity equals worst-case sensitivity in the limit as $\varepsilon \downarrow 0$
In particular, DRO is a tradeoff between mean and worst-case sensitivity when $\varepsilon$ is small
In many situations, ${\mathcal A}\big(\varepsilon; f(x, Y)\big)$ is also concave in $\varepsilon$ in addition to being increasing and non-negative. This is true for all models considered in this paper\footnote{$V(\varepsilon; f(x, \cdot))$, and hence ${\mathcal A}\big(\varepsilon; f(x, Y)\big)$, is concave in $\varepsilon$ if the set of alternative probability measures can be written in the form ${\mathcal Q}(\varepsilon) = \{{\mathbb Q}\,|\, d({\mathbb Q})\leq \varepsilon\}$ for some convex function $d$ of ${\mathbb Q}$.}. In this case, average sensitivity ${\mathcal S}\big(\varepsilon;f(x, Y)\big)$ is decreasing in $\varepsilon$ and worst-case sensitivity is a tight upper bound:
A {\it Generalized Measure of Deviation} rockafellar2006generalized measures the spread of a random variable, generalizing the notion of the standard deviation.
The following result shows that worst-case sensitivity is a {\it generalized measure of deviation}, and hence, measures the spread of the cost distribution under the nominal. It is well known that ${\mathcal A}(\varepsilon;f)$ and ${\mathcal S}(\varepsilon;f)$ are generalized measures of deviation, which we include in the statement for completeness. The proof is in the Appendix.
When the uncertainty set is a constraint on smooth $\phi$-divergence, $g(\varepsilon)=\sqrt{\varepsilon}$ in the definition (ref) of worst-case sensitivity and (ref) holds with $k=2$. It is linear in $\varepsilon$ in all other cases considered in this paper. Proposition (ref) shows that $g(\varepsilon)$ is determined by the continuity property (ref) of the uncertainty set.
We derive explicit expressions for worst-case sensitivity for uncertainty sets associated with smooth $\phi$-divergence, Total Variation, budgeted uncertainty sets, uncertainty sets corresponding to a convex combination of the nominal distribution and a CVaR-type uncertainty set, and the Wasserstein metric. For the purposes of readability, all proofs can be found in the Appendix.
{
Consider the worst-case objective
where
We assume the following.
Since $p_i>0$ for all $i$, Assumption (ref) and convex duality imply that for small $\varepsilon>0$,
The following result characterizes the solution $(c(\varepsilon), \delta(\varepsilon))$ of the dual problem and the associated worst-case distribution ${\mathsf q}(\varepsilon)=\big(q_1(\varepsilon),\cdots,\,q_n(\varepsilon)\big)^\top$ when $\varepsilon$ is small.
The worst-case expected cost is the expected cost under the worst-case distribution
It follows that $V_{\phi}(\varepsilon)-V_{\phi}(0)$ is $O(\sqrt \varepsilon)$, so worst-case sensitivity (ref) with $g(\varepsilon)=\sqrt \varepsilon$ is as follows.
A closely related result for the case $\phi(z)$ is relative entropy was derived in lam2016robust, while gotoh2018robust derives worst-case sensitivity for the “penalty formulation" of the DRO model.
Consider the worst-case expected cost \[ V_{\rm TV}(\varepsilon;\mathsf{f}) := \max_{\mathsf{q}\in\mathcal{Q}_\mathrm{TV}(\varepsilon)}~\mathbb{E}_{\mathsf{q}}(\mathsf{f}) \] with uncertainty set \[ \mathcal{Q}_\mathrm{TV}(\varepsilon):=\Big\{\mathsf{q}\in\mathbb{R}^{n}\,\Big|\, \mathsf{1}^\top|\mathsf{q}-\mathsf{p}|\leq\varepsilon,~ \mathsf{1}^\top\mathsf{q}=1,~\mathsf{q}\geq\mathsf{0}\Big\}, \] for $\varepsilon\geq 0$, where $|\mathsf{z}|:=(|z_1|,...,|z_n|)^\top$. (We can focus on $\varepsilon\leq 2$ since the set coincides with the unit simplex $\{\mathsf{q}\in\mathbb{R}^{n}|\mathsf{1}^\top\mathsf{q}=1,~\mathsf{q}\geq\mathsf{0}\}$ otherwise.) This uncertainty set is equivalent to a constraint on $\phi$-divergence with $\phi(z)=|z-1|$. Note however that $\phi(z)$ it is not differentiable at $z=1$ so the results from Section (ref) do not apply.
Consider an ordering of the components of the cost vector $\mathsf{f}=(f_1,...,f_n)^\top\in\mathbb{R}^n$ from largest to smallest and denote the $i^{th}$ largest component by $f_{(i)}$, i.e.,
and let $p_{(i)}$ denote the probability mass corresponding to $f_{(i)}$. The following lemma characterizes the worst-case objective for sufficiently small $\varepsilon$.
The expression for worst-case sensitivity follows immediately.
It is known (e.g. shiffler1980) that for any $\mathsf{f}$ and $\mathsf{p}=\mathsf{1}/n$, \[ \sqrt{\mathbb{V}_{\mathsf{p}}(\mathsf{f})}\leq \frac{1}{2}\mbox{Range}(\mathsf{f}), \] and, accordingly, we have
This suggests that when $\varepsilon$ is small, the solution of the DRO problem with the Total Variation uncertainty set will be close to optimal for DRO with smooth $\phi$-divergence.
Consider the uncertainty set
and worst-case expected cost
for $\varepsilon\geq 0$. (We can focus on $\varepsilon\leq \max_i\{\frac{1}{p_i}-1\}$ since ${\mathcal Q}_{\rm b}(\varepsilon)$ is a set of probability distributions otherwise.) For $\varepsilon\in(0,\min_i\{\frac{1}{p_{i}}-1\})$, the worst-case distribution is given by \[ (q_{(1)},..., q_{(k)},q_{(k+1)},q_{(k+2)},...,q_{(n)})= \big((1+\varepsilon)p_{(1)},...,(1+\varepsilon)p_{(k)},1-(1+\varepsilon)\sum_{i=1}^kp_{(i)},0,...,0\big). \] The set (ref) can be referred to as the budgeted uncertainty set and is related to the {\it Conditional Value-at-Risk} with parameter $\alpha\in(0, 1)$ ($\alpha$-CVaR)
Obviously, $V_{\rm b}(\varepsilon)=\mathrm{CVaR}_{\mathsf{p},\frac{\varepsilon}{1+\varepsilon}}(\mathsf{f})$.
$V_{\rm b}(\varepsilon )$ is piecewise linear, concave, and increasing in $\varepsilon$. The following result characterizes the slope of the worst-case expected cost $V_{\rm b}(\varepsilon)$ for all values of $\varepsilon$.
(ref) defines the constant slope of the linear piece over the interval (ref). Let
For $\varepsilon\in[\varepsilon_{(k)},\varepsilon_{(k+1)})$,
Since $V_{\rm b}(\varepsilon )$ is concave and increasing, its slope is the largest over the left-most piece $(0,\frac{p_{(n)}}{1-p_{(n)}})$. For $\varepsilon\in(0,\frac{p_{(n)}}{1-p_{(n)}})$ and $\Delta$ sufficiently small, (ref) becomes
The following expression for worst-case sensitivity follows immediately.
While worst-case sensitivity (ref) is a measure of spread, it only depends on the “good" side of the cost distribution. In contrast, smooth $\phi$-divergence (ref) and Total Variation (ref) depend on the entire distribution. We now see an uncertainty set where worst-case sensitivity depends on the spread of the “bad" part of the cost-distribution.
Let $\mathsf{p}$ be the nominal distribution, $\alpha\in[0,1)$ be a fixed parameter, and consider the uncertainty set
parameterized by $\varepsilon\in[0, 1]$ where
is the feasible set of (ref). The worst-case expected cost is
Observe that $\mathcal{Q}_{\rm c}(0)=\{\mathsf{p}\}$, so there is no robustness if $\varepsilon=0$ and the worst-case expected cost is SAA. The uncertainty set (ref) was considered in anderson2019robust and is equivalent to
Adopting the convention (ref), the worst-case probability distribution is given by
It can be shown that the worst-case objective satisfies \[ V_{{\rm c}}(\varepsilon;\mathsf{f}) :=(1-\varepsilon)\mathbb{E}_\mathsf{p}(\mathsf{f})+\varepsilon\mathrm{CVaR}_{\mathsf{p},\alpha}(\mathsf{f}). \] It follows that for any non-uniform vector $\mathsf{f}$ and $\varepsilon\in(0,1]$, the function $V_{\rm c}(\varepsilon)$ is linearly increasing at a rate of its CVaR Deviation rockafellar2006generalized
The following expression for worst-case sensitivity is obtained by letting $\varepsilon\searrow 0$.
Since $\mathrm{CVaR}_{\mathsf{p},\alpha}(\mathsf{f})=\max(\mathsf{f}):=\max\{f_1,...,f_n\}$ for $\alpha\in[1-p_{(1)},1)$, worst-case sensitivity is the spread of the “bad" part of the cost distribution, $\mathcal{S}_{\mathsf{p}}(\mathsf{f})=\max(\mathsf{f})-\mathbb{E}_\mathsf{p}(\mathsf{f})$, which contrasts with (ref).
We can associate CVaR deviation with the standard deviation.
Note that $C_{\alpha,n}\leq\sqrt{\frac{\alpha}{1-\alpha}}$ for all $\alpha\in[0,1)$, and especially when $n(1-\alpha)\in\mathbb{Z}$, the equality holds. Accordingly, (ref) suggests a relation between $\alpha$-CVaR and Mean-Standard Deviation:
or
The inequality (ref) is applicable to the worst-case sensitivity results. First of all,
where $V'_{\phi}(0^+)$ is the worst sensitivity of the DRO objective with the smooth $\phi$ divergence. This inequality suggests that the sensitivity of the DRO with the convex combination of mean and CVaR is bounded above by that with any smooth $\phi$ divergence. Second, recalling Corollary (ref), we have a tight bound:
for $\mathsf{p}=\mathsf{1}/n$. Since (ref) holds for any $\varepsilon\in(0,\frac{p_{(n)}}{1-p_{(n)}})=(0,\frac{1}{n-1})$, taking $\varepsilon=\frac{1}{n-1}$, we have a (loose) bound \[ V'_{\rm b}(0^+)<\sqrt{\frac{(n-1)\phi''(1)}{2}}V'_{\phi}(0^+). \] From this we see that when $n$ is large, the difference between the smooth $\phi$ and the budgeted uncertainty $\phi=\delta_{[0,1+\varepsilon]}$ can be large for small uncertainty sets. In contrast, the bounds (4.13) and (4.26) relating the sensitivities $V'_{\rm TV}(0^+)$, $V'_{\rm c}(0^+)$ and $V'_{\phi}(0^+)$ are tight and independent of $n$. The potentially large difference likely reflects the fact that the sensitivity of “budgeted uncertainty" depends only on the lower part of the cost distribution whereas $V'_{\phi}(0^+)$ depends on the entire distribution. More generally, this suggests the possibility that solutions of DRO problems with “budgeted uncertainty" may differ quite substantially from those for other uncertainty sets.
Consider the worst-case expected cost with a constraint on the Wasserstein metric blanchet2019,esfahani2018data,gao2017wasserstein:
where
We are thinking of $1\leq p \leq \infty$ for the norm in the Wasserstein metric. Note that the cost and constraint functionals
are linear in $\gamma$, so (ref) is a convex optimization problem, and $V_{\rm w}(\varepsilon)$ is concave, increasing and differentiable in $\varepsilon$ almost everywhere luenberger1997optimization.
Since solutions of the dual problem of (ref) are supergradients of the value function $V_{\rm w}(\varepsilon)$ luenberger1997optimization, we study worst-case sensitivity $V_{\rm w}'(0^+)$ by studying dual solutions when $\varepsilon\downarrow 0$.
Let $\lambda\geq 0$ be the Lagrange multiplier for the Wasserstein constraint. The dual problem is
where to ease notation, we drop the decision variable from the notation and write $f(z) \equiv f(x,\,z)$. This can be written
Intuitively, for every given transportation cost $\lambda$, the inner maximization in (ref) defines a worst-case measure that moves probability mass $p_i$ from $Y_i$ to
If $\lambda(\varepsilon)$ is any solution of the dual problem at $\varepsilon$, $\lambda(\varepsilon)$ is a super-gradient of $V_{\rm w}(\varepsilon)$ at $\varepsilon$ luenberger1997optimization, so concavity of $V_{\rm w}(\varepsilon)$ means that worst-case sensitivity $V_{\rm w}'(0^+)\leq \lambda(0)$. We compute the sensitivity at $\varepsilon=0$ by characterizing the solutions of the dual problem of (ref) when $\varepsilon=0$, and showing that one of these actually equals the right derivative $V_{\rm w}'(0^+)$.
By Lemma (ref), strong duality holds when $\varepsilon>0$. The following result shows that strong duality also holds when $\varepsilon=0$, and characterizes the set of optimal dual variables.
Proposition (ref) implies that if
then $\lambda$ is a supergradient of $V_{\rm w}$ at $\varepsilon=0$, and hence is an upper bound of the right derivative
The following result shows that this inequality is actually an equality, so $V_{\rm w}'(0^+)$ is also a solution of the dual problem at $\varepsilon=0$. This allows us to identify the identify worst-case sensitivity with the lower bound of the set of dual solutions at $\varepsilon=0$. The proof can be found in the Appendix.
It follows that when $\varepsilon$ is small
and that the DRO problem is (almost) the same as the following mean-sensitivity problem:
Consider once again the inventory cost function (ref). In this experiment, we generated $n=100$ demand realizations $\{Y_1,\cdots,\,Y_n\}$ by sampling from a mixture of two exponential distributions with means $\mu_L=10$ and $\mu_H=100$, where the probability of a sample from population $L$ is 0.9. We assume $r=10$, $c=2$, $q=0$ and $s=4$. Note that $\varepsilon=0$ is equivalent to SAA.
We begin by comparing the solutions of SAA, the robust inventory problem with a “budgeted" uncertainty set gotoh2007newsvendor ($\varepsilon=0.45$), and the robust problem with a modified $\chi^2$ uncertainty set ($\varepsilon=1.7$). Note first that the order quantity under “budgeted" uncertainty ($x(\varepsilon)=18$) is smaller than SAA ($x(0)=24$), while that for the modified $\chi^2$ uncertainty set ($x(\varepsilon)=44)$ is larger. Indeed, the worst-case expected cost of the “budgeted" solution ($x(\varepsilon)=18$) is larger than that of SAA when evaluated under the modified $\chi^2$ uncertainty set (and vice versa); in the eyes of the modified $\chi^2$ DRO model, solutions of the “budgeted" DRO problem are less robust than SAA.
These observations can be explained by considering the worst-case sensitivity associated with each uncertainty set. For “budgeted" uncertainty, worst-case sensitivity is the spread of the “good" part of the reward distribution (ref), while for modified $\chi^2$ (and any smooth $\phi$-divergence) it is the standard deviation (ref) which depends on the entire cost distribution. For “budgeted" uncertainty, DRO trades off expected cost in return for a reduction in the spread of the good side of the reward distribution, which is achieved by reducing the order quantity. This comes at the cost of a longer right tail, but this does not affect the sensitivity measure; see Figure (ref). On the other hand, the modified $\chi^2$ robust optimizer controls the standard deviation of the cost distribution; a larger order quantity reduces the standard deviation of the distribution and the length of the right tail, but the width of the body increases.
We now compare solutions generated by all the uncertainty sets we have discussed. Let $\{x^u(\epsilon)\,\vert\,\epsilon\geq 0\}$ denote the family of worst-case solutions where the uncertainty set $u$ is either KL-divergence, modified $\chi^2$-deviation, Total variation, “budgeted" uncertainty, or the convex-combination uncertainty set. In Figure (ref) (a), we plot mean-sensitivity frontiers for each family of solution where sensitivity is measured by the standard deviation (ref) (worst-case sensitivity for smooth $\phi$-divergence). The other plots show frontiers with sensitivity associated with (b) Total Variation (ref), (c) “budgeted uncertainty" (ref), and (d) $CVaR$-deviation of the cost (ref).
While DRO solutions reduce the worst-case sensitivity corresponding to its uncertainty set, they may increase other measures of worst-case sensitivity. When the shortage cost $s=4$, “budgeted" uncertainty produces solutions that increase the other measures of worst-case sensitivity (and vice versa). This can be seen in Figure (ref) where frontiers for “budgeted" uncertainty moves in the opposite direction to the others. Concurrently, robust order quantities are decreasing in $\varepsilon$ while those for other uncertainty sets are increasing. When $s=0$, however, the order quantities from all DRO models are decreasing in $\epsilon$ and the resulting frontiers are the same, as seen in Figure (ref). Finally, as shown in Example (ref), the Wasserstein sensitivity is independent of the order quantity when $p=1$, so the DRO solution is the SAA optimizer.
Mean-sensitivity frontiers can also be used to select the size $\varepsilon$ of an uncertainty set. For example, we can use (a) from Figure (ref) and the modified $\chi^2$ frontier to select $\varepsilon$ for a DRO model with a modified $\chi^2$ uncertainty set (the other frontiers are not needed). More importantly, the uncertainty set is an important modelling choice in a DRO model as it determines the measure of sensitivity that is being controlled when solving the worst-case problem.
We now consider a higher dimensional example. Fig.\,(ref) shows the four mean-sensitivity frontiers of the seven DROs for the logistic regression using the heart failure clinical records dataset chicco2020machine, which consists of 299 samples having 12 covariates.
The ordinary logistic regression is SAA where the cost of the $i$-th sample is defined as
where $\mathsf{x}_i\in\mathbb{R}^{d}$ and $y_i\in\{\pm 1\}$ denote the input vector and binary label of the $i$-th sample, respectively, and $\mathsf{w}\in\mathbb{R}^{d}$ is the vector of decision variables. (For the heart failure dataset, the all-one vector is added to the covariates, and thus $d=13$.) For details on the Wasserstein DRO model for this application, see Appendix (ref). For this example, all frontiers in Figure (ref) are similar, which suggests that solutions produced by the seven DRO models we consider are similar.
We have derived worst-case sensitivities for the expected reward for several commonly used worst-case models. The results are summarized in Table (ref).
Worst-case sensitivity is a measure of the spread of the cost distribution $f(x, Y)$. Mathematically, this is a consequence of classical duality results for DRO. Intuitively, the expected cost under the nominal distribution is sensitive to changes in the probability assigned to extreme values so a cost distribution with a large spread is sensitive to misspecification and not robust. DRO is a tradeoff between expected cost and sensitivity, where the measure of sensitivity, and hence the resulting solution, depends on the uncertainty set.
Practically, our analysis provides a list of sensitivity measures, each corresponding to a different uncertainty set, that can be used to compare the worst-case cost sensitivity for different decisions. That is, worst-case sensitivity serves as a quantitative measure of robustness, which to our knowledge has not been proposed in the literature. The expressions for worst-case sensitivity make explicit the measure of spread that DRO is trying to control for each uncertainty set, and can be used to select the uncertainty set for a given application. Mean-sensitivity frontiers can also be used to select its size.
\paragraph{\bf Acknowledgments} J. Gotoh is supported in part by JSPS KAKENHI Grant 19H02379, 19H00808, and 20H00285. He also thanks Mr. Koichi Fujii for his instruction for the use of RNUOPT, a numerical optimization package of NTT DATA Mathematical Systems Inc., with which the DRO examples in Section (ref) are solved.