Research map / Optimization / Nonconvex and smooth optimization

Sample complexity of stochastic optimization with integer variables

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes sample complexity of stochastic optimization with integer variables: matches continuous rates for Lipschitz objectives over l_inf boxes, shows integer l_2-ball problems can need fewer samples (H_2(d,R)), and shows integer strongly convex smooth problems need Omega(1/eps^2) vs O(1/eps) continuous.

Problem

Sample complexity of stochastic optimization when decision variables are integer-constrained, compared with continuous counterparts, under uniform convergence, ERM, and general data-driven algorithms.

Approach

Tight minimax sample complexity characterizations via covering/bracketing chaining for upper bounds and Fano/two-point and KL-based lower bounds; shows integrality can reduce samples (l_2 ball, via sparsity of integer points) or increase them (strongly convex smooth, via rounding loss in localization).

Key results

• Over the l_inf box, anchored UC, ERM and any algorithm all have sample complexity Theta(R^2/eps^2 (d+log(1/delta))) for Lipschitz losses, same as linear optimization with bound constraints.
• Over integer points in the l_2 ball, sample complexity is Theta(R^2/eps^2 (H_2(d,R)+log(1/delta))), strictly smaller than continuous rate when R^2 < d.
• For mu-strongly convex, L-smooth losses over integer box, ERM/any algorithm requires order sigma^2 lfloor R rfloor^2 d/eps^2 samples, versus O(1/eps) for continuous ERM.

Surprising findings

• Integer constraints can reduce sample complexity relative to continuous constraints for nonconvex Lipschitz losses over the l_2 ball when R^2 < d.
• Anchored uniform convergence can have infinite sample complexity for unbounded strongly convex integer problems, while ERM remains finite.

Limitations

• Results are minimax-style and up to absolute constants; the paper does not give algorithms achieving the integer bounds efficiently.
• Strongly convex results require a sub-Gaussian increment assumption on the distribution rather than plain Lipschitzness on unbounded domains.

Experimental setup

Metrics: sample complexity (minimax, UC, ERM, any algorithm)

Baselines: continuous stochastic convex optimization sample complexity ERM sample complexity for convex Lipschitz losses SGD

Builds on: chaining / bracketing uniform convergence Fano's inequality sub-Gaussian increment condition

Closest papers by meaning

• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.91)
• New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.90)
• Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.89)
• Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.88)
• Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.88)
• High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.87)