How Boundary Proximity Dictates Sample Complexity

63 concepts51 papers1 proposal

When making decisions based on noisy data, we are almost always drawing a line in the sand. Whether we are classifying an image, selecting the top candidates for a job, or admitting traffic into a network slice, we establish a boundary that separates success from failure, or inclusion from exclusion.

Intuitively, if an object is far from that line, a few noisy observations are more than enough to know which side it falls on. But as an object inches closer to the boundary, its signal-to-noise ratio plummets. This phenomenon underpins a core truth across machine learning and optimization: the statistical difficulty of a task is not uniformly distributed; it is highly concentrated around its decision thresholds. Understanding this "boundary proximity complexity" explains why certain problems require massive amounts of data while others collapse into simplicity.

The Inverse-Square Law of Thresholds

To understand why proximity to a boundary causes sample complexity to explode, consider the classic Thresholding Bandit Problem. We are given a set of options (arms) with unknown mean rewards, and our goal is to identify every arm whose mean is above a fixed threshold $\tau$.

In An optimal algorithm for the Thresholding Bandit Problem, Andrea Locatelli et al. demonstrate that the probability of making an error scales exponentially with the sampling budget divided by a sum of squared gaps:

$$\sum_{i} \frac{1}{(\mu_i - \tau)^2}$$

This inverse-square relationship stems directly from standard concentration inequalities. To distinguish an arm's true mean $\mu_i$ from the threshold $\tau$ with high statistical confidence, the number of samples required is proportional to $1/\Delta_i^2$, where $\Delta_i = |\mu_i - \tau|$. As an arm's mean approaches the threshold ($\Delta_i \to 0$), the required sample size approaches infinity.

This sensitivity is a major bottleneck in real-world engineering systems:

Multidimensional Constraints and Pareto Fronts

What happens when the decision boundary isn't a single number, but a complex geometric shape?

In Feasible Arm Identification, Julian Katz-Samuels et al. expand the thresholding problem to multi-dimensional polyhedral constraints. They prove that the sample complexity scales with the sum of the inverse squared distances from each candidate's multi-dimensional mean vector to the nearest constraint boundary. If a candidate is nearly feasible but slightly invalid, it consumes the vast majority of the exploration budget.

        Feasible Region (Polyhedron)
       +-------------------------+
       |                         |    o <-- Far from boundary
       |                         |          (Easy to reject)
       |      o                  |
       |  Far from boundary      |
       |  (Easy to accept)       |
       |                    o    |
       +--------------------x----+
                           / \
                          /   \
                         o     o  <-- Near-boundary candidates
                                      (Requires massive sampling)

The same principle governs multi-objective optimization. When searching for options that balance competing goals (like a drug that is both highly effective and low in toxicity), we look for a Pareto front. In Constrained Pareto Set Identification with Bandit Feedback, Cyrille Kone et al. show that the hardest candidates to classify are those that are nearly feasible and nearly optimal. These boundary-dwelling options require an exceptional volume of observations to confidently include or exclude from the final Pareto set.

The Top-K Bottleneck: The Gap at the Cut-off

In ranking and selection tasks, we often do not care about a fixed external threshold. Instead, we want to find the top $K$ items out of a pool. Here, the "boundary" is dynamic—it is defined by the quality of the items themselves.

Minje Jang proves in Optimal Sample Complexity of M-wise Data for Top-K Ranking that the fundamental information-theoretic limit for top-$K$ selection is governed entirely by the utility gap between the last item included in the top set and the first item excluded (the $K$-th and $(K+1)$-th items). If the 10th best item and the 11th best item are nearly identical, the sample complexity explodes, even if the top 9 items are blindingly obvious.

This exact bottleneck appears across various ranking paradigms:

The Margin Dividend: When Sparsity Accelerates Learning

If proximity to the boundary makes learning hard, what happens when the boundary is completely clear of data? This is known as a "hard margin."

In Multiclass learning with margin: exponential rates with no bias-variance trade-off, Stefano Vigogna et al. prove that when there is a clear separation (a margin) between classes in multiclass classification, the classification error can drop to zero exponentially fast as more data is added.

Crucially, this accelerated learning happens without the traditional bias-variance trade-off. This provides a powerful theoretical explanation for why massive, overparameterized models can achieve near-perfect performance in practice: if the real-world data exhibits low density or a clear margin near the decision boundaries, the statistical complexity of the problem collapses, allowing the model to lock onto the correct classification boundary with remarkable speed.

Key Foundational Work

Numerical vs. Statistical Probabilistic Model Checking: An Empirical Study (2004) — contributed 1 concept elements to this direction.
Insights from Machine Learning Applied to Human Visual Classification (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_utility_gap_sensitivity_6e418d83,
  title = {utility gap sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/utility-gap-sensitivity/rdr_6e418d83deed436eb61797133f28acce},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_utility_gap_sensitivity_6e418d83_v1,
  title = {utility gap sensitivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/utility-gap-sensitivity/rdr_6e418d83deed436eb61797133f28acce/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake