Sample Average Approximation for Distributionally Robust Optimization with ϕ \phi -divergences
Yan Li · 2026
Read Sample Average Approximation for Distributionally Robust Optimization with ϕ \phi -divergences by Yan Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10855.txt.
Introduction
Li shows two facts about bounded variable expectations fail for worst-case expectations over a phi-divergence ball around P. Counts need not scale as B squared over epsilon squared, nor stay independent of measure. When phi grows superlinearly, sample averaging gains P-independent sample complexity set by phi's growth, ball radius, and target precision, with matching lower bounds for common phi-divergences. Without superlinear growth, any method faces a P-dependent bound that grows without limit, though a broader phi-divergence definition restores P-independence, showing absolute continuity matters.
Catalog record
| CREATOR | Yan Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70851 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.10855
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sample Average Approximation for Distributionally Robust Optimization with ϕ \phi -divergences Yan Li Abstract It is well known that estimating the expectation of any given bounded random variable with values in [ − B , B ] [-B,B] has a sample complexity of 𝒪 ( B 2 / ϵ 2 ) \mathcal{O}(B^{2}/\epsilon^{2}) that is independent of the underlying probability measure. We show that this property can no longer hold when evaluating the worst-case expectation of the random variable, where the probability measures defining the expectation belong to a ϕ \phi -divergence ball centered at some nominal measure P P . Specifically, the sample complexity and its dependence on the nominal measure can be completely characterized by the growth of the divergence function. When the divergence function ϕ \phi exhibits superlinear growth, a P P -independent sample complexity can be obtained for sample average approximation, which depends only on the growth of ϕ \phi , the radius of the divergence ball, and the target precision. We also provide sample complexity lower bounds and demonstrate the optimality of the obtained bounds for commonly used ϕ \phi -divergences. On the other hand, when superlinear growth does not hold for ϕ \phi , we show that for any estimation method, evaluating the worst-case expectation has a P P -dependent sample complexity lower bound that can be made arbitrarily large by changing P P . 1 Introduction Let (\Omega,\mathcal{F}) be a measurable space and P be a probability measure on (\Omega,\mathcal{F}) . Let \phi:\mathbb{R}\to\mathbb{R}_{+}\cup\left\{+\infty\right\} be a convex lower semicontinuous function with \phi(1)=0 and \phi(x)=+\infty for x<0 . For \tau\geq 0 , consider \displaystyle\mathfrak{M}_{\tau}(P)=\left\{\zeta\in\mathfrak{D}:\int_{\Omega}\phi(\zeta(w))dP(w)\leq\tau\right\}, where \mathfrak{D} denotes the set of probability density functions with respect to P . Let X:\Omega\to[-B,B] be \mathcal{F} -measurable for some B\geq 0 . The distributionally robust functional corresponding to \phi is defined as \displaystyle\mathcal{R}(X)=\sup_{\zeta\in\mathfrak{D}}\int_{\Omega}X(\omega)\zeta(\omega)dP(\omega),~\mathrm{s.t.}~\zeta\in\mathfrak{M}_{\tau}(P). (1.1) Going forward, we refer to \phi as the divergence function associated with \mathcal{R}(X) . Consider the following sample average approximation (SAA) of ( 1.1 ). That is, for any n>0 , let \omega_{1},\ldots,\omega_{n} denote the samples drawn independently from P , and let P_{n} be the corresponding empirical distribution. Define \displaystyle\mathcal{R}_{n}(X)=\sup_{\zeta\in\mathfrak{D}}\int_{\Omega}X(\omega)\zeta(\omega)dP_{n}(\omega),~\mathrm{s.t.}~\zeta\in\mathfrak{M}_{\tau}(P_{n}). (1.2) We are interested in the number of samples n needed for ( 1.2 ) to be an accurate approximation of ( 1.1 ). Clearly, when \tau=0 , \mathcal{R}(X) reduces to the expectation, and from Hoeffding’s inequality one can take no more than \mathcal{O}(B^{2}/\epsilon^{2}) samples to estimate \mathcal{R}(X) via \mathcal{R}_{n}(X) up to an \epsilon -accuracy. The situation seems to become unclear for \tau>0 . Sample complexity bounds have been obtained for various concrete \phi -divergences (e.g., total variation, Kullback-Leibler, \chi^{2} -distance, conditional value-at-risk) in the context of distributionally robust optimization [ 3 , 4 ] or Markov decision processes (MDPs) [ 9 , 7 , 8 ] . It is worth mentioning here that in the context of MDPs, the obtained sample complexity bounds typically depend on the nominal measure P via its minimal probability, and hence are intrinsically restricted to finite sample spaces. On the other hand, for a class of Cressie-Read divergence functions, [ 3 ] obtains the sample complexity lower and upper bounds independent of nominal measure P . Our problem of interest is to provide a relatively complete characterization for the sample complexity when estimating \mathcal{R}(X) with general divergence functions. The essential observation in this manuscript is that the sample complexity and its dependence on the nominal measure can be completely characterized by the growth of the divergence function. Definition 1.1 . We say that \phi has sublinear growth if \lim_{x\to\infty}\phi(x)/x<\infty , and superlinear growth if \lim_{x\to\infty}\phi(x)/x=\infty . Indeed, if \phi grows superlinearly at infinity, we establish a P -independent sample complexity bound for the sample average approximation \mathcal{R}_{n}(X) that only depends on the growth of \phi and the radius \tau . On the other hand, if \phi grows sublinearly, then one can construct a class of problems for which we can obtain an information-theoretic sample complexity lower bound that depends on P , which can be further made arbitrarily large by changing the nominal measure P . 2 Sample Complexity for Sublinear Growth Throughout our discussion in this section, we make the following assumption on the divergence function \phi . Assumption 2.1 . There exists \delta>0 such that [1-\delta,1+\delta]\subseteq\mathrm{int}(\mathrm{dom}(\phi)) . 2.1 Sample Complexity Lower Bound We begin with the following lower bound on \mathcal{R}(X) for a family of reference measures P supported over \Omega with two elements. Lemma 2.1 . Consider \Omega=\left\{\omega_{1},\omega_{2}\right\} , \mathcal{F}=2^{\Omega} , X(\omega_{1})=1 and X(\omega_{2})=0 . Suppose \lim_{x\to\infty}{\phi(x)}/{x}<\infty , then for any \tau>0 , there exist r_{\phi,\tau},p_{\phi,\tau}>0 such that for any P on (\Omega,\mathcal{F}) with 0<P(\omega_{1})\leq p_{\phi,\tau} , \displaystyle\mathcal{R}(X)\geq r_{\phi,\tau}. Here r_{\phi,\tau} and p_{\phi,\tau} are constants depending only on the divergence function \phi and radius \tau . Proof. Let p_{i}=P(\omega_{i}) and \zeta_{i}=\zeta(\omega_{i}) for i\in\left\{1,2\right\} . Recall that the constraint \zeta\in\mathfrak{M}_{\tau}(P) requires \displaystyle\phi(\zeta_{1})p_{1}+\phi(\zeta_{2})p_{2}\leq\tau;~\zeta_{1}p_{1}+\zeta_{2}p_{2}=1,~\zeta_{1},\zeta_{2}\geq 0. (2.1) Since \lim_{x\to\infty}\phi(x)/x<\infty , there exist L_{\phi},G_{\phi}\geq 1 such that \phi(x)/x\leq G_{\phi} for x\geq L_{\phi} . In addition, given Assumption 2.1 , \phi(1)=0 and the fact that \phi is convex, for any \tau>0 , there exists r_{\phi,\tau}>0 such that \sup_{x\in[1-r_{\phi,\tau},1+r_{\phi,\tau}]}\phi(x)\leq\tfrac{\tau}{2}. Note that without loss of generality we can assume r_{\phi,\tau}\leq\min\left\{{\tau}/{2G_{\phi}},1\right\} . Our goal is to show the existence of p_{\phi,\tau}>0 such that for any probability measure P with p_{1}\in(0,p_{\phi,\tau}] , one can construct a corresponding \zeta\in\mathfrak{M}_{\tau}(P) with \mathbb{E}_{P}[\zeta X] (and hence \mathcal{R}(X) ) bounded away from 0 . Let k\geq 1 be some constant to be determined later. Denote p_{\phi,\tau}=\tfrac{\tau}{kG_{\phi}L_{\phi}} , and let \zeta_{1}=\tfrac{\tau}{kG_{\phi}p_{1}} . Note that for any p_{1}\in(0,p_{\phi,\tau}] , we have \zeta_{1}\geq L_{\phi}, and hence \phi(\zeta_{1})p_{1}=\phi\left(\tfrac{\tau}{kG_{\phi}p_{1}}\right)\cdot\tfrac{kG_{\phi}p_{1}}{\tau}\cdot\tfrac{\tau}{kG_{\phi}}\leq\tfrac{\tau}{k}, where the last inequality follows from the definition of G_{\phi} and L_{\phi} . Given this observation and the choice of \zeta_{1} , to satisfy ( 2.1 ), it suffices to have \displaystyle\tfrac{\tau}{kG_{\phi}}\leq 1,~\sup_{p_{2}\in[1-p_{\phi,\tau},1]}\phi\left(\tfrac{1-{\tau}/\left(kG_{\phi}\right)}{p_{2}}\right)p_{2}\leq\tfrac{(k-1)\tau}{k}. By choosing k=\tfrac{\tau}{G_{\phi}r_{\phi,\tau}} , given the definition of r_{\phi,\tau} , we have k\geq 2 and \tfrac{\tau}{kG_{\phi}}=r_{\phi,\tau}\leq 1 . Since \phi is convex, to satisfy the above condition, it suffices to have \displaystyle\max\left\{\phi\left(\tfrac{1-r_{\phi,\tau}}{1-p_{\phi,\tau}}\right),\phi\left(1-r_{\phi,\tau}\right)\right\}\leq\tfrac{\tau}{2}. Note that the choice of k implies p_{\phi,\tau}=\tfrac{r_{\phi,\tau}}{L_{\phi}}\leq r_{\phi,\tau} , and hence the above condition is immediately satisfied by the definition of r_{\phi,\tau} . In this case, we have \displaystyle R(X)\geq\mathbb{E}_{P}\left[\zeta X\right]=\zeta_{1}p_{1}=\tfrac{\tau}{kG_{\phi}p_{1}}\cdot p_{1}=\tfrac{\tau}{kG_{\phi}}=r_{\phi,\tau}, where the last inequality follows from the choice of k . ∎ With Lemma 2.1 , we proceed to establish the sample complexity lower bound for sample average approximation ( 1.2 ). Theorem 2.1 . Under the same setup as in Lemma 2.1 , let \mathcal{R}_{n}(X) be defined as in ( 1.2 ). For any p\in(0,p_{\phi,\tau}) , there exists P over (\Omega,\mathcal{F}) such that \displaystyle\left\lvert{\mathcal{R}}_{n}(X)-\mathcal{R}(X)\right\rvert\geq{r_{\phi,\tau}}, with probability at least 1/2 , if n\leq 1/(2p) . Proof. Let us adopt the same notation as in Lemma 2.1 . For any p\in(0,p_{\phi,\tau}) , define P over (\Omega,\mathcal{F}) with P(\omega_{1})=p\in(0,p_{\phi,\tau}) . From Lemma 2.1 , we have \mathcal{R}(X)\geq r_{\phi,\tau} . Given the definition of X , it is clear that \mathcal{R}_{n}(X)=0 if P_{n}(\omega_{1})=0 , and consequently \left\lvert{\mathcal{R}}_{n}(X)-\mathcal{R}(X)\right\rvert\geq{r_{\phi,\tau}}. Note that \displaystyle P^{\otimes n}\left(P_{n}(\omega_{1})=0\right)=(1-p)^{n}\geq 1-pn\geq 1/2, where the last inequality follows from n\leq 1/(2p) . ∎ We can indeed strengthen the lower bound for SAA to the following information-theoretic lower bound for estimating \mathcal{R}(X) . Theorem 2.2 . Under the same setup as in Lemma 2.1 , for any p\in(0,p_{\phi,\tau}) , and