Moment Ambiguity and the Limits of Robust Stochastic Optimization
Abstract
We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our binary and N-way moment-matching constructions separate quantiles, threshold regions, and online selection opportunities while preserving every moment. For the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. For revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. For the secretary problem with cardinal observations, the optimal robust success probability under exact moment disclosure is the classical finite-horizon value sm, even for i.i.d. observations. This value converges to 1/e, compared with the full-information limit of approximately $0.5801$ due to Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. For every fixed r≥1, exact moment knowledge can yield at best a Θ(1/log m) competitive ratio, even when competing against relaxed benchmarks based on expected r-th order statistics or when the algorithm is allowed to select r items.
Related
- A Composite Bayesian Risk--Distributionally Robust Optimization Model for Stochastic Programming with Elliptical Distribution Ambiguity
- Conformal-DRO: Distributionally Robust Optimization with Conformalized Ambiguity Set
- Calibrating Ambiguity Set via Diagnostic Transport for Distributionally Robust Optimization
- Local-discrepancy ambiguity sets for distributionally robust optimization
- Distributionally robust chance-constrained standard quadratic optimization with Wasserstein ambiguity
BibTeX
@misc{cristi2026moment,
title = {{Moment Ambiguity and the Limits of Robust Stochastic Optimization}},
author = {Andrés Cristi and Matteo Russo and Jiechen Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.31090},
eprint = {2609.31090},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31090},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Moment Ambiguity and the Limits of Robust Stochastic Optimization
AU - Andrés Cristi
AU - Matteo Russo
AU - Jiechen Zhang
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2609.31090
UR - https://arxiv.org/abs/2609.31090
AB - We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our binary and N-way moment-matching constructions separate quantiles, threshold regions, and online selection opportunities while preserving every moment. For the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. For revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. For the secretary problem with cardinal observations, the optimal robust success probability under exact moment disclosure is the classical finite-horizon value s_m, even for i.i.d. observations. This value converges to 1/e, compared with the full-information limit of approximately $0.5801$ due to Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. For every fixed r≥1, exact moment knowledge can yield at best a Θ(1/log m) competitive ratio, even when competing against relaxed benchmarks based on expected r-th order statistics or when the algorithm is allowed to select r items.
ER -