← All papers
First page of Moment Ambiguity and the Limits of Robust Stochastic Optimization

Moment Ambiguity and the Limits of Robust Stochastic Optimization

Andrés Cristi, Matteo Russo, Jiechen Zhang

cs.IT Sep 25, 2026 · v1 cs.DS cs.GT math.OC
The main impossibility results on moment-equivalent distributions are formalized in Lean 4 with Mathlib, with the development released in a GitHub repository.
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 approach gives two explicit constructions: a binary and an $N$-way construction showing that distributions with identical moment sequences can nevertheless exhibit arbitrarily different quantiles, order-statistics and threshold regions, forcing incompatible optimal actions. These families of distributions yield, in fact, strong impossibility results across several stochastic optimization problems. First, for the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. Second, for revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. Third, for the secretary with cardinal observations setting, the worst-case robust value over all exact moment disclosures is exactly the classical $1/e$ finite-horizon value as opposed to the celebrated result of $0.58$ success probability with full-information by 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. Indeed, exact moment knowledge can yield at best a $Θ(1/\log n)$ 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.

The paper asks how well decisions can be made when a distribution is known only through its exact full moment sequence. Problems considered include the newsvendor, posted pricing, the secretary problem with cardinal observations, and prophet inequalities.

Two constructions produce distinct distributions with identical moment sequences. A binary separator splits Vandermonde null vectors on rapidly separated nodes into positive and negative parts. An N-way construction uses roots of unity so that N residue classes share all moments. Quantitative control of designated atoms and tails then turns these families into lower bounds for each decision problem. The main results are formalized in Lean 4 using Mathlib.

Every fixed or randomized newsvendor order quantity can fail arbitrarily badly, and no deterministic or randomized posted pricing scheme achieves a nontrivial approximation. The robust secretary value drops to the classical 1/e from the full-information value of about 0.58. Prophet inequalities are limited to a Θ(1/log n) competitive ratio, even against r-th order-statistic benchmarks.