Sample Complexity of Stochastic Optimization with Integer Variables
Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu · 2026
Read Sample Complexity of Stochastic Optimization with Integer Variables by Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07239.txt.
Description
Hongyu Cheng and three co-authors count how many samples stochastic optimization needs when variables must be whole numbers. Intuition might say integer problems are always harder than their continuous versions, but the picture depends on the objective's shape and the constraint set. The authors map out where each direction holds.
For Lipschitz objectives over box-shaped regions, mixed-integer complexity exactly matches plain linear optimization. Over round regions, integer problems can need strictly fewer samples in one regime. For strongly convex, smooth objectives, they need far more, with a lower bound that beats the classic continuous rate. New continuous results fill gaps along the way.
Catalog record
| CREATOR | Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07239