Statistical Limit Theorems in Distributionally Robust Optimization

In order to analyze the statistical error in the difference between the optimal values $\vartheta_{n}-\vartheta$, we start from enforcing a functional Central Limit Theorem (CLT) for $f_{n}\left(\cdot\right)$. In particular, one imposes assumptions which guarantee an expansion of the form²²2Recall that $\epsilon_{n}(\cdot)$ denotes a random field satisfying condition (1.8).

$$f_{n}\left(\theta\right)=f\left(\theta\right)+n^{-1/2}r_{n}\left(\theta\right)+n^{-1/2}\epsilon_{n}\left(\theta\right),$$

(2.3)

where we have functional weak convergence

$$r_{n}\left(\cdot\right){\rightsquigarrow}{\mathfrak{g}}\left(\cdot\right)$$

(2.4)

in the uniform topology on compact sets, with ${\mathfrak{g}}\left(\cdot\right)$ being a mean zero Gaussian random field with covariance function

$$\mathrm{Cov}\left({\mathfrak{g}}\left(\theta\right),{\mathfrak{g}}\left(\theta^{\prime}\right)\right)=\mathrm{Cov}_{P_{\ast}}\big{(}l\left(X,\theta\right),l\left(X,\theta^{\prime}\right)\big{)}.$$

(2.5)

There are several ways to enforce (2.3); a simple set of sufficient conditions satisfying this is given next (cf., [18, example 19.7]).

In particular under this assumption, it follows that the expectation function $f(\theta)$ and variance

$$\sigma^{2}(\theta):=\mathrm{Var}_{P_{\ast}}(l(X,\theta))$$

(2.7)

are finite valued and continuous on $\Theta$. Furthermore, since the set $\Theta$ is compact, it follows that the optimal value $\vartheta_{n}$, of the ERM problem, converges to $\vartheta$ in probability (in fact almost surely). Moreover, it is not difficult to show from (2.3) that the distance from $\theta_{n}$ to $\Theta_{\ast}$ converges in probability to zero (actually, the convergence occurs almost surely) as $n\rightarrow\infty$. Finally, since the functional $V(\phi):=\inf_{\theta\in\Theta}\phi(\theta)$, mapping continuous functions $\phi:\Theta\to{\mathbb{R}}$ to the real line, is directionally differentiable, the following classical result is a direct consequence of the (functional) Delta Theorem (cf., [14]).

We assume now that $\Theta^{\ast}=\{\theta^{\ast}\}$ is the singleton, i.e., $\theta^{\ast}$ is the unique optimal solution of the true (population) problem (1.3). We also assume that for a.e. $X$, the function $l(X,\cdot)$ is continuously differentiable³³3Unless stated otherwise all first and second order derivatives will be taken with respect to vector $\theta$.. As it was argued in the previous section, asymptotics of the optimal value is governed by the asymptotics of the objective function. On the other hand, asymptotics of the optimal solutions can be derived from the asymptotics of the gradients of the objective function.

Let us consider the following parametrisation of problem (1.3):

$$\min_{\theta\in\Theta}f\left(\theta\right)+v^{T}\theta,$$

(2.9)

with parameter vector $v\in{\mathbb{R}}^{m}$. Denote by $\theta_{*}(v)$ an optimal solution of the above problem (2.9) viewed as a function of vector $v$. Of course, we have that $\theta_{*}(0)=\theta^{*}$.

The following assumption can be viewed as a counterpart of Assumption 2.1 applied to the gradients of the objective function.

By the functional CLT it follows that

$$\nabla f_{n}\left(\theta\right)=\nabla f\left(\theta\right)+n^{-1/2}d_{n}\left(\theta\right)+n^{-1/2}\epsilon_{n}\left(\theta\right),$$

(2.12)

where we have a functional weak convergence $d_{n}\left(\cdot\right){\rightsquigarrow}\,{\mathfrak{G}}\left(\cdot\right)$ in the uniform topology on a closed neighborhood of $\theta^{\ast}$, with ${\mathfrak{G}}\left(\cdot\right)$ being a continuous mean zero Gaussian random field with covariance function

$$\mathrm{Cov}\left[{\mathfrak{G}}(\theta),{\mathfrak{G}}(\theta^{\prime})\right]={\mathbb{E}}_{P_{\ast}}[(\nabla l(X,\theta)-\nabla f(\theta))(\nabla l(X,\theta^{\prime})-\nabla f(\theta^{\prime}))^{T}].$$

It follows from (2.12) that

$$\left[\nabla f_{n}(\theta)-\nabla f(\theta)\right]-\left[\nabla f_{n}(\theta^{\ast})-\nabla f(\theta^{\ast})\right]=n^{-1/2}\left[d_{n}\left(\theta\right)-d_{n}\left(\theta^{\ast}\right)+\epsilon_{n}\left(\theta\right)-\epsilon_{n}\left(\theta^{\ast}\right)\right].$$

(2.13)

Also since $\rho_{n}:=\|\theta_{n}-\theta^{\ast}\|$ tends in probability to zero, we have

$$\sup_{\theta:\|\theta-\theta^{\ast}\|\leq\rho_{n}}\left[d_{n}\left(\theta\right)-d_{n}\left(\theta^{\ast}\right)+\epsilon_{n}\left(\theta\right)-\epsilon_{n}\left(\theta^{\ast}\right)\right]=o_{p}(1).$$

(2.14)

Thus we have the following result from [15, Theorem 2.1], where the respective regularity conditions are ensured by the above property (2.14).

The above result reduces the analysis of asymptotic properties of the optimal solutions to investigation of asymptotic behavior of the optimal solutions of the finite dimensional problem (2.9). By the (finite dimensional) Central Limit Theorem, $n^{1/2}Z_{n}$ converges in distribution to normal $N(0,\Sigma)$ with covariance matrix $\Sigma=\mathrm{Cov}(\nabla l(X,\theta^{*}))$. Moreover, if the mapping $\theta_{*}(v)$ is directionally differentiable at $v=0$ (in the Hadamard sense), then by the finite dimensional Delta Theorem it follows from (2.15) that

$$n^{1/2}(\theta_{n}-\theta^{*})\,{\rightsquigarrow}\,\theta_{*}^{\prime}(0,Z),$$

(2.16)

where $Z\sim N(0,\Sigma)$. In particular, if $\theta_{*}^{\prime}(0,w)=Aw$ is linear (i.e., $\theta_{*}(v)$ is differentiable at $v=0$ with Jacobian matrix $A$), then $n^{1/2}(\theta_{n}-\theta^{*})$ converges in distribution to normal with null mean vector and covariance matrix $A\Sigma A^{T}$.

Directional differentiability of optimal solutions of parameterized problems is well investigated. For example, if $\theta^{\ast}$ is an interior point of $\Theta$, $f(\theta)$ is twice continuously differentiable at $\theta^{*}$ and the Hessian matrix $H:=\nabla^{2}f(\theta^{\ast})$ is nonsingular, then the uniform second order growth (Assumption 2.2) holds, and $\theta_{\ast}\left(v\right)$ is differentiable at $v=0$ with $\theta_{\ast}^{\prime}\left(0,w\right)=H^{-1}w$. When $\theta^{\ast}$ is on the boundary of the set $\Theta$, the sensitivity analysis of the parameterized problem (2.9) is more delicate and involves a certain measure of the curvature of the set $\Theta$ at the point $\theta^{\ast}$. This is discussed extensively in [6]. We also refer to [17, sections 5.1.3 and 7.1.5] for a basic summary of such results.

It is worthwhile to note at this point that the regularity conditions of assumptions 2.2 and 2.3 address different properties of the considered setting. Assumption 2.2 deals with the limiting optimization problem and is of deterministic nature. The uniform second order growth condition was introduced in [15], and in a more general form was discussed in [6, section 5.1.3]. On the other hand Assumption 2.3 is related to the stochastic behavior of the ERM problem (1.2).

Similar to the ERM case, in the DRO setting, we will typically have an expansion of the form

$$\mathcal{F}_{n}(\theta,\delta_{n})=f_{n}\left(\theta\right)+\delta_{n}^{\gamma}R_{n}\left(\theta\right)+\delta_{n}^{\gamma}\epsilon_{n}\left(\theta\right),$$

(3.2)

for some $\gamma>0$, where $R_{n}(\cdot)$ converges in probability in the uniform topology over $\Theta$ to a continuous deterministic process $\varrho(\cdot)$,

$$R_{n}(\theta)=\varrho(\theta)+\epsilon_{n}(\theta).$$

(3.3)

Since $\mathcal{F}_{n}(\cdot,\delta_{n})\geq f_{n}(\cdot)$, it follows then that $\varrho(\cdot)\geq 0$. We will characterize $\gamma>0$ and $\varrho\left(\cdot\right)$ explicitly in the next sections in the context of phi-divergence and Wasserstein DRO formulations under suitable conditions on the distributional uncertainty set – in addition to Assumption 2.1 (which is clearly independent of the distributional uncertainty). The following result, which is immediate from the application of the functional Delta Theorem summarizes the type of behavior that we expect in DRO formulations depending on the geometry of the distributional uncertainty set and the rate of decay to zero of the uncertainty size $\delta_{n}$. Recall that ${\mathfrak{g}}(\theta)$ denotes a mean zero Gaussian random field with covariance function (2.5).

Proof. Part (a). By (3.2) and (3.3) we have that in the considered case

$${\cal F}_{n}(\theta,\delta_{n})=f_{n}(\theta)+o(n^{-1/2})\epsilon_{n}\left(\theta\right),$$

where $\epsilon_{n}\left(\theta\right)$ is the generic term satisfying (1.8). Thus (3.4) follows.

Part (b). By (3.2) and (3.3) in the considered case we can write

$$n^{1/2}\left(\mathcal{F}_{n}(\theta,\delta_{n})-f(\theta)\right)=n^{1/2}(f_{n}(\theta)-f(\theta))+\varrho(\theta)+\epsilon_{n}\left(\theta\right).$$

Under Assumption 2.1, by the functional CLT we have that $n^{1/2}(f_{n}(\theta)-f(\theta))+\varrho(\theta)$ converges in distribution to ${\mathfrak{g}}(\theta)+\varrho(\theta)$, and hence (3.6) follows by the Delta Theorem.

Part (c) may appear somewhat different because the right hand side is deterministic but, under case (c) note that we can simply write

$$\mathcal{F}_{n}(\theta,\delta_{n})=f\left(\theta\right)+\delta_{n}^{\gamma}R_{n}\left(\theta\right)+\delta_{n}^{\gamma}\epsilon_{n}\left(\theta\right),$$

so case (c) also follows from the standard analysis since $R_{n}\left(\cdot\right)$ converges uniformly to $\varrho\left(\cdot\right)$ in probability (thus it converges weakly in the uniform topology). $\hfill\square$

As in the ERM development, in addition to Assumptions 2.2, it is convenient to guarantee that for all $n$ large enough, $\mathcal{F}_{n}(\theta,\delta_{n})$ is differentiable in a neighborhood $\mathcal{V}$ of $\theta^{\ast}$ and

$$\nabla\mathcal{F}_{n}(\theta,\delta_{n})=\nabla f_{n}\left(\theta\right)+\delta_{n}^{\gamma}D_{n}\left(\theta\right)+\delta_{n}^{\gamma}\epsilon_{n}\left(\theta\right),$$

(3.8)

for some $\gamma>0$, where $D_{n}\left(\theta\right)$ converges in probability to $\nabla\varrho\left(\theta\right)$ uniformly around a closed neighborhood $\mathcal{\bar{V}}$ of $\theta^{\ast}$. In consequence, we obtain the following analog of Theorem 3.1, which follows from the finite dimensional Delta Theorem. Recall that $\theta_{*}(v)$ is an optimal solution of problem (2.9) and $\theta^{\prime}_{*}(0,\cdot)$ is its directional derivative at $v=0$.

We recall the definition of the distributional uncertainty set for the phi-divergence case. Consider a convex lower semi-continuous function $\phi\colon{\mathbb{R}}\rightarrow{\mathbb{R}}_{+}\cup\{+\infty\}$ such that $\phi(1)=0$ and $\phi(t)=+\infty$ for $t<0$. For probability measures $Q,P\in{\mathfrak{P}}$ such that $Q$ is absolutely continuous with respect to $P$ with the corresponding density $dQ/dP$, the $\phi$-divergence is defined as (cf., [7],[12])

$$D_{\phi}(Q\|P):={\mathbb{E}}_{P}[\phi(dQ/dP)]=\int\phi(dQ/dP)dP.$$

(4.1)

In particular, for $\phi(t):=t\log\left(t\right)-t+1$, $t\geq 0$, this becomes the Kullback–Leibler (KL) divergence of $Q$ from $P$. The ambiguity set ${\mathfrak{M}}_{\delta}(P)$ associated with $D_{\phi}(\cdot\|P)$ is defined as

$${\mathfrak{M}}_{\delta}\left(P\right):=\{Q\ll P:D_{\phi}(Q\|P)\leq\delta\}.$$

(4.2)

By duality arguments the corresponding distributionally robust functional can be written in the form (cf., [2], [3], [16])

$$\sup_{Q\in{\mathfrak{M}}_{\delta}\left(P\right)}{\mathbb{E}}_{Q}[Y]=\inf_{\mu,\lambda>0}\left\{\lambda\delta+\mu+\lambda{\mathbb{E}}_{P}[\phi^{\ast}((Y-\mu)/\lambda)]\right\},$$

(4.3)

where $\phi^{\ast}(y)=\sup_{t\in{\mathbb{R}}}\{yt-\phi(t)\}$ is the convex conjugate of $\phi$. Using this representation we can obtain an asymptotic expansion for (4.3) as a function of $\delta$. This expansion can be helpful to suggest the form of the expansion in (3.2) and (3.8). For this, we need to assume certain regularity properties of $\phi\left(t\right)$ around $t=1$.

Under this condition we have the following expansion, which is obtained, in order to simplify our exposition, under the assumption that the probability measure $P$ has compact support. See also the results in [11], which provide additional correction terms under a fixed $P$. The uniform feature of the statement below is helpful in the statistical analysis. Our development here will also be used in the expansion of the optimal solutions.

Proof. Note that we can write

$$\sup_{Q\in{\mathfrak{M}}_{\delta}\left(P\right)}{\mathbb{E}}_{Q}[Y]=\sup_{{\mathbb{E}}_{P}\left(Z\right)=1,{\mathbb{E}}_{P}\left(\phi\left(Z\right)\right)\leq\delta}{\mathbb{E}}_{P}[YZ],$$

where the sup is taken over the set of positive random variables $Z$ satisfying the specified moment constraints. We may assume that ${\mathbb{E}}_{P}\left[Y\right]=0$ for simplicity since we can always center the objective function around ${\mathbb{E}}_{P}\left[Y\right)]$. In turn, by letting $\bar{\Delta}=(Z-1)/\delta^{1/2}$, the previous optimization problem is equivalent to

$$\delta^{1/2}\sup_{{\mathbb{E}}_{P}\left(\bar{\Delta}\right)=0,\bar{\Delta}\geq-\delta^{-1/2},{\mathbb{E}}_{P}(\phi(1+\delta^{1/2}\bar{\Delta}))\leq\delta}{\mathbb{E}}_{P}[Y\bar{\Delta}].$$

(4.5)

Since $\left|Y\right|\leq\nu$ and ${\mathbb{E}}_{P}\left[Y\right]=0$, then $\bar{\Delta}=aY$ is feasible for any $a>0$ provided that $a\nu\leq\delta^{-1/2}$ and

$${\mathbb{E}}_{P}[\phi(1+\delta^{1/2}\bar{\Delta})]\leq\delta.$$

In turn, since $\phi\left(t\right)$ is two times continuously differentiable at $t=1$, we have that

$$\delta^{-1}\phi(1+\delta^{1/2}ay))\rightarrow a^{2}y^{2}\phi^{\prime\prime}\left(1\right)/2$$

as $\delta\rightarrow 0$ uniformly over compact sets. Therefore, we conclude that there exists $\delta_{0}>0$ such that for any $\delta<\delta_{0}$

	$\displaystyle\sup_{{\mathbb{E}}_{P}\left(\bar{\Delta}\right)=0,\bar{\Delta}\geq-\delta^{-1/2},{\mathbb{E}}_{P}(\phi(1+\delta^{1/2}\bar{\Delta}))\leq\delta}{\mathbb{E}}_{P}[Y\bar{\Delta}]$
	$\displaystyle\geq\sup_{a>0,a^{2}{\mathbb{E}}_{P}\left(Y^{2}\right)/2\leq\left(1-\delta_{0}\right)/\phi^{\prime\prime}\left(1\right)}{\mathbb{E}}_{P}[aY^{2}]=\sqrt{\kappa\left(1-\delta_{0}\right)}\cdot\sqrt{{\mathbb{E}}_{P}[Y^{2}]}.$

Since $\delta_{0}>0$ can be chosen to be arbitrarily small, we conclude an asymptotic lower bound which retrieves (4.4). For the upper bound, we apply the duality result (4.3) in the form corresponding to (4.5), we obtain

	$\displaystyle\sup_{{\mathbb{E}}_{P}\left(\bar{\Delta}\right)=0,\bar{\Delta}\geq-\delta^{-1/2},\delta^{-1}{\mathbb{E}}_{P}(\phi(1+\delta^{1/2}\bar{\Delta}))\leq 1}{\mathbb{E}}_{P}[Y\bar{\Delta}]$
	$\displaystyle=\min_{\bar{\lambda}>0,\bar{\mu}}\{\bar{\lambda}+{\mathbb{E}}_{P}[\sup_{\bar{\Delta}\geq-\delta^{-1/2}}\{\left(Y+\bar{\mu}\right)\bar{\Delta}-\bar{\lambda}\delta^{-1/2}\phi(1+\delta^{1/2}\bar{\Delta})\}]\}$
	$\displaystyle\leq\min_{\bar{\lambda}>0}\{\bar{\lambda}+{\mathbb{E}}_{P}[\sup_{\bar{\Delta}\geq-\delta^{-1/2}}\{Y\bar{\Delta}-\bar{\lambda}\delta^{-1/2}\phi(1+\delta^{1/2}\bar{\Delta})\}]\}.$		(4.6)

We will plug in

$$\bar{\lambda}_{0}=\arg\min\{\bar{\lambda}+\kappa{\mathbb{E}}_{P}[Y^{2}]/4\bar{\lambda}:\bar{\lambda}>0\}=2^{-1}\sqrt{\kappa{\mathbb{E}}_{P}[Y^{2}]}>0$$

into (4.6) to obtain our upper bound. Using that $\bar{\lambda}_{0}>0$ and that $\phi$ is convex with $\phi^{\prime\prime}\left(1\right)>0$, we have that the family of (continuous) functions

$$s_{\delta}\left(y\right):=\sup_{\bar{\Delta}\geq-\delta^{-1/2}}\{y\bar{\Delta}-\bar{\lambda}\delta^{-1/2}\phi(1+\delta^{1/2}\bar{\Delta})\}$$

converges uniformly on compact sets to

$$s_{0}\left(y\right)=\sup_{\bar{\Delta}}\{y\bar{\Delta}-\bar{\lambda}\bar{\Delta}^{2}/\kappa\}=\frac{\kappa y^{2}}{4\bar{\lambda}}.$$

Therefore we obtain that

	$\displaystyle\min_{\bar{\lambda}>0}\{\bar{\lambda}+{\mathbb{E}}_{P}[\sup_{\bar{\Delta}\geq-\delta^{-1/2}}\{Y\bar{\Delta}-\bar{\lambda}\delta^{-1/2}\phi(1+\delta^{1/2}\bar{\Delta})\}]\}$
	$\displaystyle\leq\bar{\lambda}_{0}+{\mathbb{E}}_{P}[\sup_{\bar{\Delta}\geq-\delta^{-1/2}}\{Y\bar{\Delta}-\bar{\lambda}_{0}\delta^{-1/2}\phi(1+\delta^{1/2}\bar{\Delta})\}]\rightarrow\sqrt{\kappa}\cdot\sqrt{{\mathbb{E}}_{P}[Y^{2}]}.$

These estimates, which are uniform given that $\left|Y\right|\leq\nu$, yield the estimate in the proposition. The uniqueness is standard, it follows from the local strong convexity of $\phi\left(\cdot\right)$ at the origin. $\hfill\square$

Recall that $\sigma^{2}(\theta):=\mathrm{Var}_{P_{\ast}}(l(X,\theta))$, and that ${\mathfrak{g}}\left(\cdot\right)$ is a mean zero Gaussian random field. Expansion (4.4) immediately yields, at least when $\sup_{\theta\in\Theta}\left|l\left(X,\theta\right)\right|$ is $P_{\ast}$-bounded, that

$$\mathcal{F}_{n}(\theta,\delta_{n})=f_{n}\left(\theta\right)+\delta_{n}^{1/2}\kappa^{1/2}\sigma(\theta)+\delta_{n}^{1/2}\epsilon_{n}\left(\theta\right).$$

(4.7)

Consequently, we obtain the following result.

Proof. Proof of this theorem is quite standard (cf., [17, proof of Theorem 5.7]). For the sake of completeness we briefly outline proof of case (b-phi). Note that our assumptions imply Assumption 2.1, and hence $\sigma^{2}(\theta)$ is a continuous function of $\theta$. Therefore there is a compact neighborhood $\bar{\Theta}$ of $\Theta^{*}$ such that $\sigma^{2}(\theta)>0$ for all $\theta\in\bar{\Theta}$. We can restrict the minimization to $\bar{\Theta}$ for which the expansion (4.7) holds.

Consider the space $C(\bar{\Theta})$ of continuous functions $g:\bar{\Theta}\to{\mathbb{R}}$ equipped with the sup-norm, and functional $V(g):=\inf_{\theta\in\bar{\Theta}}g(\theta)$, mapping $C(\bar{\Theta})$ into the real line. This functional is directionally differentiable in the Hadamard sense with the directional derivative at a point $\mu\in C(\bar{\Theta})$ given by $V^{\prime}(\mu,h)=\inf_{\theta\in\bar{\Theta}(\mu)}h(\theta)$, where $\bar{\Theta}(\mu):=\mathop{\rm arg\,min}_{\theta\in\bar{\Theta}}\mu(\theta)$. We have that $\bar{\vartheta}_{n}=V(\mathcal{F}_{n})$ and $\vartheta=V(f)$, where $\mathcal{F}_{n}(\cdot):=\mathcal{F}_{n}(\cdot,\delta_{n})$. By the functional CLT and (4.7) it follows that $n^{1/2}(\mathcal{F}_{n}-f)$ converges in distribution (weakly) to ${\mathfrak{g}}(\theta)+\kappa^{1/2}\beta^{1/2}\sigma(\theta)$. We can apply now the functional Delta Theorem to conclude (4.9). $\hfill\square$