🤖 machine learning

Sample Complexity of Stochastic Optimization with Integer Variables

This paper establishes that the sample complexity of stochastic optimization with integer variables can be strictly greater than, equal to, or even smaller than that of its continuous counterpart, depending on the specific geometry of the feasible set and the properties of the objective function.

Original authors: Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongyu Cheng, Yinghao Zheng, Marco Molinaro, Amitabh Basu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the best spot to set up a lemonade stand in a city. You don't have a map of the whole city (the "distribution"), but you can send out scouts to check specific locations and report back on how much money they think you'd make there. The goal is to figure out the absolute best spot using as few scouts as possible.

This paper is about a specific twist on that problem: What if your scouts can only check integer coordinates (like street corners 1, 2, 3) instead of any spot on the map (like 1.5, 2.7, 3.1)?

The authors, a team of mathematicians, wanted to know: Does restricting your search to "whole numbers" (integers) make the job harder, easier, or the same compared to searching the whole continuous map?

Here is what they found, broken down into three main scenarios:

1. The "Box" Scenario (The Square City)

Imagine your city is a giant square box. You can go anywhere inside it, but you are limited by the walls.

The Finding: It doesn't matter if your scouts can only check street corners (integers) or any spot on the grid (continuous). The number of scouts you need is exactly the same.
The Analogy: Think of a maze where the walls are the only thing that matters. Whether you are allowed to walk through the grass (continuous) or only on the paved paths (integers), the "hardness" of finding the exit is determined by the size of the box, not the type of path you take. Even if the rules of the game are messy and non-linear (like a complex, bumpy terrain), the number of samples needed doesn't change just because you added the "integer" rule.

2. The "Ball" Scenario (The Round City)

Now, imagine the city is a perfect circle (a ball).

The Finding: Here, things get weird. If you restrict your scouts to integer coordinates (street corners), you might actually need fewer scouts than if they could check any spot in the circle.
The Analogy: Imagine a round table with a few scattered coins on it. If you are allowed to look anywhere on the table (continuous), there are infinite spots to check, and the "shape" of the table is smooth and complex. But if you are only allowed to look at the coins (integers), there are suddenly very few spots to check.
Why it happens: In a round shape, the "integer" spots (the coins) are sparse. They don't fill the space like a continuous surface does. Because there are fewer distinct "whole number" spots to worry about, the problem becomes statistically easier to solve in certain situations. It's like finding a needle in a haystack: if you are only allowed to look at the tips of the hay (integers), there are fewer tips to check than the whole volume of the haystack.

3. The "Smooth Hill" Scenario (The Perfect Slope)

Finally, imagine the terrain is a perfectly smooth, bowl-shaped hill (mathematically, "strongly convex and smooth"). This is usually the easiest type of problem to solve in the continuous world.

The Finding: In this specific case, forcing the scouts to look only at integer spots makes the job much harder. You need significantly more scouts (samples) to find the bottom of the bowl if you are restricted to integers.
The Analogy: Imagine sliding down a smooth slide to find the bottom. In the continuous world, you can glide right to the exact bottom. But if you are forced to jump from one integer "step" to the next, you might overshoot the bottom or get stuck on a step that looks like the bottom but isn't.
The Cost: In the continuous world, you can find the solution with a certain number of scouts. In the integer world, you need many more (specifically, the number of samples grows much faster as you demand higher accuracy). The "rounding error" of being forced to land on a whole number creates a new kind of difficulty that doesn't exist in the smooth, continuous version.

The Big Picture

The paper challenges the old idea that "discrete" (integer) problems are always harder than "continuous" ones.

Sometimes, they are just as hard (the Box).
Sometimes, they are actually easier because there are fewer options to check (the Ball).
Sometimes, they are much harder because the "steps" get in the way of a smooth solution (the Smooth Hill).

The authors also looked at different ways of measuring success:

Uniform Convergence: Making sure every single spot is estimated correctly.
Empirical Risk Minimization (ERM): Just finding the best spot based on the data you have.
Any Algorithm: Using any clever trick to find the answer.

They found that for the "Smooth Hill" with integers, the clever tricks (ERM) work much better than trying to estimate every single spot perfectly. It's like realizing you don't need to map the whole city to find the best lemonade stand; you just need to focus your energy on the neighborhood that looks promising.

In summary: Whether integer constraints make a problem harder or easier depends entirely on the shape of the "city" you are searching in and the shape of the "terrain" (the objective function). There is no single rule; it's a mix of geometry and statistics.

Technical Summary: Sample Complexity of Stochastic Optimization with Integer Variables

1. Problem Statement

The paper investigates the sample complexity of stochastic optimization problems where the decision variable $x$ is constrained to be an integer vector. The fundamental problem is formulated as:
$\min_{x \in X} F_D(x) := \mathbb{E}_{z \sim D}[f(x; z)]$
where $X \subseteq \mathbb{R}^d$ is a constraint set (specifically focusing on integer subsets of balls), $f: X \times Z \to \mathbb{R}$ is a loss function, and $D$ is an unknown probability distribution on a measurable space $Z$ . The goal is to find an $\epsilon$ -approximate solution with high probability ( $1-\delta$ ) using a finite number of i.i.d. samples from $D$ .

The authors aim to characterize how the requirement for integrality affects the number of samples needed compared to the corresponding continuous optimization problem. They analyze three standard notions of sample complexity:

Uniform Convergence (UC): The number of samples required such that the empirical risk $F_S(x)$ uniformly approximates the population risk $F_D(x)$ within $\epsilon$ over the entire domain.
Empirical Risk Minimization (ERM): The number of samples required to ensure that minimizing the empirical risk yields an $\epsilon$ -optimal solution for the population risk.
Any Data-Driven Algorithm: The optimal sample complexity achievable by any algorithm (not just ERM) that outputs a solution based on the samples.

2. Methodology and Framework

The authors employ a combination of information-theoretic lower bounds and empirical process theory for upper bounds.

Lower Bounds: The proofs rely on constructing hard instances of distributions (often involving hidden sign vectors or biased coin flips) and reducing the optimization problem to hypothesis testing or parameter estimation tasks. Tools include Fano's inequality, KL-divergence bounds (Pinsker's inequality), and packing arguments (constructing sets of points with large pairwise distances).
Upper Bounds: The authors utilize bracketing and chaining arguments to bound the uniform deviation of the empirical process. For strongly convex settings, they leverage localization phenomena, showing that the error is controlled by the behavior of the stochastic process in a small neighborhood of the optimum, rather than the entire domain.
Anchored Uniform Convergence: To handle the shift-invariance of optimization (where adding a constant to the objective does not change the minimizer), the authors define "anchored" objectives $\bar{f}(x; z) = f(x; z) - f(0; z)$ , ensuring the sample complexity is finite and well-defined.

3. Key Contributions and Results

The paper establishes tight sample complexity bounds (up to constant factors) for three distinct regimes, revealing that the impact of integrality depends heavily on the geometry of the domain and the smoothness/convexity of the objective.

A. Lipschitz Objectives over the $\ell_\infty$ Ball (Box Constraints)

Setting: $X \subseteq B^{(\infty)}_R$ (a box of radius $R$ ), with $f(\cdot; z)$ being 1-Lipschitz with respect to the $\ell_\infty$ norm.
Result: The sample complexity is $\Theta\left(\frac{R^2}{\epsilon^2}(d + \log(1/\delta))\right)$ .
Significance:

This rate holds for any feasible subset of the box, including mixed-integer sets ( $X = C \cap (\mathbb{Z}^n \times \mathbb{R}^{d-n})$ ) and purely integer sets ( $X = B^{(\infty)}_R \cap \mathbb{Z}^d$ ).
Crucially, integrality does not change the sample complexity. The complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization in this setting is exactly the same as simple stochastic linear programming with bound constraints.
The lower bound is achieved even by linear functions, implying that the "hardness" comes from the geometry of the box vertices, which are the same for both continuous and integer cases.

B. Lipschitz Objectives over the $\ell_2$ Ball (Euclidean Constraints)

Setting: $X \subseteq B^{(2)}_R$ (Euclidean ball of radius $R$ ), with $f(\cdot; z)$ being 1-Lipschitz with respect to the $\ell_2$ norm.
Result:

Continuous Case: The sample complexity is $\Theta\left(\frac{R^2}{\epsilon^2}(d + \log(1/\delta))\right)$ .
Integer Case: The sample complexity is $\Theta\left(\frac{R^2}{\epsilon^2}(H_2(d, R) + \log(1/\delta))\right)$ , where $H_2(d, R)$ is a geometric term defined as:
$H_2(d, R) = \begin{cases} 0 & 0 < R < 1 \\ \min\{d, \lfloor R^2 \rfloor\} \log\left(\frac{ed}{\min\{d, \lfloor R^2 \rfloor\}}\right) & R \ge 1 \end{cases}$
Significance:
Integrality can be easier: When $R^2 < d$ , the term $H_2(d, R) < d$ . This implies that integer-constrained stochastic optimization can require strictly fewer samples than the continuous counterpart.
Mechanism: This advantage arises because the convex hull of integer points in a small Euclidean ball has a different (sparser) geometry than the ball itself. The integer points have sparse support (at most $\lfloor R^2 \rfloor$ non-zero coordinates), reducing the effective dimensionality of the search space compared to the full continuous ball.
Nonconvexity: Unlike the convex setting where ERM can be strictly more efficient than Uniform Convergence, in this nonconvex Lipschitz setting, the sample complexities for UC, ERM, and any algorithm are identical.

C. Strongly Convex and Smooth Objectives

Setting: $f(\cdot; z)$ is $\mu$ -strongly convex and $L$ -smooth. The domain is either a box $B^{(\infty)}_R$ or the entire space $\mathbb{R}^d$ . The authors introduce a sub-Gaussian increment condition to handle unbounded domains, as standard Lipschitz assumptions fail for unbounded strongly convex functions.
Result:

Integer Case: The sample complexity for ERM is $\Theta\left(\frac{\sigma^2 d \min\{\kappa, \lfloor R \rfloor^2\}}{\epsilon^2}(d + \log(1/\delta))\right)$ , where $\kappa = L/\mu$ is the condition number.
Continuous Case: The sample complexity for ERM is $\Theta\left(\frac{\sigma^2 d}{\mu \epsilon}(d + \log(1/\delta))\right)$ .
Significance:
Integrality makes the problem harder: In this regime, integer optimization requires $\Omega(1/\epsilon^2)$ samples, whereas continuous optimization achieves the faster $O(1/\epsilon)$ rate.
Localization vs. Rounding: The continuous case benefits from "accelerated" rates because the strong convexity allows the algorithm to localize the search to a small region without incurring a rounding error. In the integer case, the "localization" is limited by the discrete grid; the algorithm must resolve the specific integer point, which incurs an additional loss that prevents the $1/\epsilon$ rate.
Uniform Convergence vs. ERM: For unbounded integer domains, Uniform Convergence has infinite sample complexity (it is impossible to uniformly approximate the objective over all integers with finite samples), yet ERM succeeds with finite samples. This is a unique separation where ERM is strictly more powerful than Uniform Convergence due to the localization phenomenon.

4. Significance and Claims

The paper claims to close a gap in the literature regarding the statistical (sample complexity) aspects of integer stochastic optimization, which has historically focused on algorithmic or asymptotic complexity.

Contextualizing Difficulty: The authors demonstrate that the difficulty of integer stochastic optimization is not monolithic. It depends entirely on the interplay between the geometry of the constraint set ( $\ell_\infty$ vs. $\ell_2$ ) and the regularity of the objective (Lipschitz vs. Strongly Convex/Smooth).
Counter-Intuitive Findings:
- In the $\ell_\infty$ setting, integrality is statistically neutral.
- In the $\ell_2$ setting, integrality can be statistically advantageous (requiring fewer samples) due to sparsity.
- In the strongly convex setting, integrality is statistically disadvantageous (slower convergence rates) due to the inability to avoid rounding errors in the localization step.
Methodological Contribution: The paper provides the first tight sample complexity bounds for nonconvex continuous stochastic optimization (matching the $\ell_\infty$ and $\ell_2$ Lipschitz results) and establishes the necessity of sub-Gaussian increment conditions for unbounded strongly convex problems.

The authors maintain a modest tone, stating that their results provide a "quantitative" understanding of the relative difficulty of continuous versus discrete stochastic optimization, rather than proposing new algorithms or applications. The work serves as a theoretical benchmark for what is statistically achievable in these settings.