Sample Complexity of Stochastic Optimization with Integer Variables

Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu

arXivarxiv/2605.07239May 8, 2026cs.LGscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.07239
curl -X POST /api/v1/records/arxiv/2605.07239/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.07239/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'