Closing the Sample Complexity Gap in Efficient Learning

19 concepts8 papers1 proposal

In machine learning theory, there is a fundamental tension between what is mathematically possible and what is computationally feasible. Information theory tells us how many samples are strictly necessary to identify a target function from a given class—often achieved via Empirical Risk Minimization (ERM). However, ERM is frequently NP-hard to compute.

When we restrict ourselves to polynomial-time algorithms, we often pay a steep penalty: a sample complexity gap. Computationally efficient algorithms regularly require significantly more data than the information-theoretic minimum to achieve the same level of accuracy. A vibrant line of recent research focuses on understanding the root causes of this gap and designing novel algorithmic paradigms to close it.

The Statistical-Computational Dichotomy

The gap between information-theoretic requirements and computational constraints manifests clearly when learning complex, non-linear structures. For instance, a small number of samples may uniquely define a high-degree polynomial, but extracting that polynomial using standard optimization techniques is a different story.

Santosh Vempala et al. quantified this barrier in Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds. They demonstrated that while a target function might be easily identifiable from a handful of samples, any algorithm operating within the Statistical Query (SQ) framework—which captures standard gradient descent variants—requires a number of queries that scales exponentially with the polynomial degree of the target function ($n^{O(k)}$).

To formalize what makes a concept class efficiently learnable when data is noisy and imperfect, Pravesh K Kothari et al. introduced the framework of "refutation complexity" in Improper Learning by Refuting. They proved that a concept class is efficiently agnostically learnable if and only if one can efficiently refute the hypothesis that a random dataset contains a structured pattern. This established a direct mathematical bridge between computational complexity and statistical sample requirements.

Why Classical Boosting Falls Short of Optimality

This sample complexity gap is particularly pronounced in boosting, a paradigm designed to convert "weak" learners (rules of thumb slightly better than random guessing) into "strong" learners (highly accurate classifiers).

For decades, AdaBoost was celebrated as the textbook boosting algorithm. Yet, as K. Larsen et al. pointed out in Optimal Weak to Strong Learning, a persistent gap remained between the sample complexity of standard boosting algorithms and the theoretical lower bounds. Specifically, classical methods suffer from an extra logarithmic overhead in their data requirements.

To understand why, we must look at how AdaBoost interacts with data. In AdaBoost is not an Optimal Weak to Strong Learner, Mikael Møller Høgsgaard et al. proved that this logarithmic sub-optimality is an inherent structural flaw rather than a loose mathematical bound. Because traditional boosting algorithms feed the entire training set to the weak learner at every iteration, they introduce complex adaptive dependencies across iterations. A clever, adversarial weak learner can exploit these dependencies, forcing the final booster to require a logarithmic factor more samples to guarantee generalization.

Breaking Dependencies via Data Splitting

To eliminate this logarithmic overhead and achieve true sample optimality, algorithms must break the feedback loop between iterations.

In The Many Faces of Optimal Weak-to-Strong Learning, Mikael Møller Høgsgaard et al. introduced a remarkably elegant solution called MAJORITY-OF-5. Instead of running a single boosting chain over the entire dataset, the algorithm partitions the training data into five disjoint chunks. It trains an independent AdaBoost model on each chunk and aggregates their predictions via a simple majority vote.

[Training Data] ---> Split into 5 Disjoint Chunks
                         |
      +------------------+------------------+
      |          |       |          |       |
   [Chunk 1]  [Chunk 2] ...     ...     [Chunk 5]
      |          |                          |
  AdaBoost   AdaBoost                   AdaBoost
      |          |                          |
      +------------------+------------------+
                         |
               [Majority Vote Ensembling] 
                         |
              ==> Optimal Sample Complexity

Because the chunks are completely independent, the adversarial weak learner cannot exploit cross-iteration dependencies across the different models. This simple architectural change completely eliminates the logarithmic overhead, matching the theoretical lower bounds for weak-to-strong learning while remaining computationally efficient and highly parallelizable.

The Agnostic Frontier: Conquering Noise

The sample complexity gap widens into a chasm in agnostic learning—settings where the data is inherently noisy and no perfect classifier exists in the target class. In this domain, direct ERM requires roughly $O(1/\epsilon^2)$ samples to reach an error rate of $\epsilon$. Traditional efficient agnostic boosting algorithms, however, scaled poorly, often requiring $O(1/\epsilon^4)$ samples.

Udaya Ghai and Karan Singh began narrowing this gap in Sample-Efficient Agnostic Boosting. By designing a novel algorithm that reuses samples across iterations according to a carefully calibrated schedule, they improved the sample complexity from $O(1/\epsilon^4)$ to $O(1/\epsilon^3)$.

To determine exactly how far this could be pushed, Arthur da Cunha et al. mapped out the fundamental statistical limits of the field in Revisiting Agnostic Boosting. They proved a tight lower bound showing that the statistical sample complexity for agnostic boosting is fundamentally constrained by the inverse square of both the target error ($\epsilon$) and the weak learner's advantage ($\gamma$).

The final breakthrough that completely closed the gap to the $O(1/\epsilon^2)$ ERM gold standard involved changing the data paradigm itself. In Sample-Optimal Agnostic Boosting with Unlabeled Data, Udaya Ghai and Karan Singh demonstrated that the gap could be bridged by leveraging a polynomial amount of cheap, unlabeled data.

The intuition behind this approach is powerful: the booster uses the unlabeled data to evaluate the performance and maintain the alignment of the weak learners across iterations. This prevents the algorithm from burning through expensive labeled samples just to navigate the noise, allowing it to achieve the optimal labeled sample complexity of $O(1/\epsilon^2)$ without sacrificing the computational advantages of boosting.

Key Foundational Work

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2019) — contributed 3 concept elements to this direction.
Improper Learning by Refuting (2018) — 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_sample_complexity_gap_sample_complexity__cc1e6e00,
  title = {sample complexity gap (sample complexity sub-optimality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sample-complexity-gap-sample-complexity-sub-optimality/rdr_cc1e6e00cb0546b0ac7e82dd8d5f8775},
  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_sample_complexity_gap_sample_complexity__cc1e6e00_v1,
  title = {sample complexity gap (sample complexity sub-optimality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sample-complexity-gap-sample-complexity-sub-optimality/rdr_cc1e6e00cb0546b0ac7e82dd8d5f8775/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