Sample Average Approximation for Distributionally Robust Optimization with $ϕ$-divergences
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913066576248832 |
|---|---|
| author | Li, Yan |
| author_facet | Li, Yan |
| contents | It is well known that estimating the expectation of any given bounded random variable with values in $[-B, B]$ has a sample complexity of $\mathrm{O}(B^2/ε^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 $ϕ$-divergence ball centered at some nominal measure $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 $ϕ$ exhibits superlinear growth, a $P$-independent sample complexity can be obtained for sample average approximation, which depends only on the growth of $ϕ$, 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 $ϕ$-divergences. On the other hand, when superlinear growth does not hold for $ϕ$, we show that for any estimation method, evaluating the worst-case expectation has a $P$-dependent sample complexity lower bound that can be made arbitrarily large by changing $P$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10855 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sample Average Approximation for Distributionally Robust Optimization with $ϕ$-divergences Li, Yan Optimization and Control Statistics Theory It is well known that estimating the expectation of any given bounded random variable with values in $[-B, B]$ has a sample complexity of $\mathrm{O}(B^2/ε^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 $ϕ$-divergence ball centered at some nominal measure $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 $ϕ$ exhibits superlinear growth, a $P$-independent sample complexity can be obtained for sample average approximation, which depends only on the growth of $ϕ$, 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 $ϕ$-divergences. On the other hand, when superlinear growth does not hold for $ϕ$, we show that for any estimation method, evaluating the worst-case expectation has a $P$-dependent sample complexity lower bound that can be made arbitrarily large by changing $P$. |
| title | Sample Average Approximation for Distributionally Robust Optimization with $ϕ$-divergences |
| topic | Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2604.10855 |