Sample Complexity of Stochastic Optimization with Integer Variables
This work provides foundational theoretical insights into the sample complexity of stochastic integer optimization, clarifying when integer constraints increase or decrease statistical difficulty compared to continuous optimization.
This paper establishes sample complexity results for stochastic optimization over integers, showing that integer optimization can require strictly more or fewer samples than continuous optimization depending on the objective and constraints. For Lipschitz objectives over subsets of the ℓ∞ ball, the complexity matches linear optimization; for ℓ2 ball, integer optimization can require smaller sample sizes; for strongly convex smooth objectives, integer optimization requires Ω(1/ε²) samples versus O(1/ε) for continuous.
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 $\ell_\infty$ 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 $\ell_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 $Ω(1/ε^2)$ samples to report an $ε$-approximate solution, compared to the well-known $O(1/ε)$ sample complexity from the continuous optimization literature.