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

CREATORHongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07239

Browse the full library · About the Tower of Babel