# Sample Complexity of Stochastic Optimization with Integer Variables

arXiv: https://arxiv.org/abs/2605.07239 · HTML: https://mlsanity.com/paper/2605.07239/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 5 of 5)

- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent](https://mlsanity.com/paper/1909.00843/) (2019)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [A unified framework for information-theoretic generalization bounds](https://mlsanity.com/paper/2305.11042/) (2023)

## Abstract (arXiv)

We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints. 1. For Lipschitz objectives over subsets of the ℓ_∞ ball, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints. 2. For Lipschitz objectives over subsets of the ℓ2 ball, we show that integer optimization can require strictly *smaller* sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work. 3. For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires Omega(1/ε2) samples to report an ε-approximate solution, compared to the well-known O(1/ε) sample complexity from the continuous optimization literature.