When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective
Abstract
Two-stage sample robust optimization with linear decision rules is a standard data-driven approach to two-stage stochastic linear programs with unknown distributions. \cite{bertsimas2022two} established that this approach is asymptotically optimal under several conditions. Most conditions are mild, but one imposes a technical requirement on the recourse system. Whether this condition is implied by the others was left as an open question. We resolve this open question through a geometric feature of the support set: simpleness, the property that every vertex is incident to exactly as many edges as the dimension of the support. For simple support sets, the technical condition is automatic, and asymptotic optimality holds under the remaining standard assumptions. For every non-simple support, we construct a recourse system that is feasible everywhere in the support but violates the technical condition, and this construction resolves the open question. We further characterize the simpleness of one-sided and two-sided budgeted uncertainty sets and identify when budget perturbations can restore simpleness. We also develop a polynomial-time algorithm that certifies the technical condition at a given vertex using its incident edge directions. Numerical experiments on newsvendor and network lot-sizing problems illustrate the characterization and the effectiveness of the verification algorithm.
Related
- Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing
- A New Perspective on Optimal Power Flow: From Control Theory to Numerical Optimization
- A Unified Perspective on Conformal Prediction and Wasserstein Distributionally Robust Optimization for Uncertainty Quantification
- A class of asymptotically optimal authentication codes with secrecy
- Asymptotically optimal bracketing covers for anchored boxes with applications to star discrepancy
BibTeX
@misc{dai2026when,
title = {{When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective}},
author = {Ling Dai and Chin Pang Ho},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.22999},
eprint = {2608.22999},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.22999},
}
RIS
TY - UNPB
TI - When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective
AU - Ling Dai
AU - Chin Pang Ho
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2608.22999
UR - https://arxiv.org/abs/2608.22999
AB - Two-stage sample robust optimization with linear decision rules is a standard data-driven approach to two-stage stochastic linear programs with unknown distributions. \cite{bertsimas2022two} established that this approach is asymptotically optimal under several conditions. Most conditions are mild, but one imposes a technical requirement on the recourse system. Whether this condition is implied by the others was left as an open question. We resolve this open question through a geometric feature of the support set: simpleness, the property that every vertex is incident to exactly as many edges as the dimension of the support. For simple support sets, the technical condition is automatic, and asymptotic optimality holds under the remaining standard assumptions. For every non-simple support, we construct a recourse system that is feasible everywhere in the support but violates the technical condition, and this construction resolves the open question. We further characterize the simpleness of one-sided and two-sided budgeted uncertainty sets and identify when budget perturbations can restore simpleness. We also develop a polynomial-time algorithm that certifies the technical condition at a given vertex using its incident edge directions. Numerical experiments on newsvendor and network lot-sizing problems illustrate the characterization and the effectiveness of the verification algorithm.
ER -