Moment Ambiguity and the Limits of Robust Stochastic Optimization
Andrés Cristi, Matteo Russo, Jiechen Zhang
cs.IT
Sep 25, 2026 · v3
cs.DS cs.GT math.OC
TL;DR
All results, including the moment-matching constructions and impossibility theorems, are formalized in Lean 4 with Mathlib, with a repository mapping results to declarations.
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 $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\ge1$, 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.
Problem
The question is how well a decision maker can do in robust stochastic optimization when a distribution is known only through its exact moment sequence. The benchmark is the decision available with full distributional knowledge, studied for newsvendor, posted pricing, secretary, and prophet inequality problems.
Approach
Two constructions produce distinct distributions with identical moments. A binary separator splits a moment-annihilating sequence, built from Vandermonde null vectors, into positive and negative parts. An N-way residue-class construction uses roots of unity. Quantitative control of atoms and tails turns these constructions into lower bounds for each decision problem, and all results are formalized in Lean 4 with Mathlib.
Results
Under moment ambiguity, any fixed or randomized newsvendor order quantity can fail arbitrarily badly, and no deterministic or randomized posted price achieves a nontrivial revenue approximation. The robust secretary success probability is the classical value s_m, which tends to 1/e. Prophet inequalities with moment knowledge allow at best a Θ(1/log m) competitive ratio, even against relaxed r-th order-statistic benchmarks.