Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

Shai Ben-David, Steve Hanneke, Farnam Mansouri, Amirreza ShaeiriarXiv 2026 · arXiv

TL;DR

This paper settles a long-standing question in learning theory by determining the near-optimal sample complexity for "deterministic agnostic" PAC learning. By using a hybrid strategy that combines standard empirical risk minimization with explicit memorization of training labels, the authors prove that the number of samples required scales as $\widetilde{O}(K^{1/3}d^{2/3}/\varepsilon)$, bridging the gap between the easy "realizable" setting and the hard "fully agnostic" setting.

What Problem Does This Paper Address?

In classical Computational Learning Theory, we usually talk about two regimes:

  1. Realizable: The "ground truth" function belongs to your hypothesis class $\mathcal{C}$. This is easy; sample complexity scales with $1/\varepsilon$.
  2. Agnostic: The labels can be anything (even stochastic noise). This is hard; sample complexity scales with $1/\varepsilon^2$.

This paper investigates a middle ground: Deterministic Agnostic Learning. Here, labels are generated by a fixed, deterministic function $f^*$, but $f^*$ is not in your class $\mathcal{C}$ (model misspecification).

Previous work showed that if the class $\mathcal{C}$ has a finite diameter $K$ (the maximum number of points where any two functions in the class can disagree), you can do better than the $1/\varepsilon^2$ agnostic bound. However, there was a massive gap between the known upper bound ($\widetilde{O}(K/\varepsilon)$) and the lower bound ($\Omega(d/\varepsilon)$). The authors set out to find the true "price" of misspecification when labels are deterministic.

Methods

The authors introduce a surprisingly simple but powerful algorithmic framework: the Memorizing Empirical Risk Minimizer (MERM).

  • The Algorithm: First, find a standard Empirical Risk Minimizer (ERM) from the class $\mathcal{C}$ based on the training data. Then, for any future query, if the point was seen during training, simply output the stored training label (memorization). If the point is new, output the ERM's prediction.
  • The Analysis: The technical heavy lifting involves analyzing the "missing mass"—the probability weight of points the learner hasn't seen yet. They use concentration inequalities for discrete distributions to bound how much error the memorization strategy can "save."
  • Lower Bounds: To prove their bound is tight, they use information-theoretic arguments. They construct a scenario where a small amount of probability mass is spread over many "rare" points. They show that unless the learner has enough samples, it's impossible to distinguish the "best" hypothesis from a slightly worse one in these rare regions.

Datasets

As a theoretical research paper, no empirical datasets (like ImageNet or MNIST) were used. Instead, the authors used:

  • Synthetic Concept Classes: They mathematically constructed specific concept classes with fixed VC dimension $d$ and diameter $K$ to prove that their upper bounds are tight.
  • Combinatorial Benchmarks: They evaluated their results against complexity measures like VC dimension, Diameter, and two newly refined parameters: SET-VC and PERT-VC.

Key Insights and Ideas

  • Memorization is Optimal: In many modern deep learning contexts, memorization is seen as a sign of overfitting. However, this paper shows that in the deterministic agnostic setting, memorizing the training data is actually a provably optimal strategy to minimize excess risk.
  • The Power of Determinism: Because labels are deterministic, seeing a point once tells you its label forever. This "certainty" allows the sample complexity to scale with $1/\varepsilon$ rather than $1/\varepsilon^2$, even when the model is misspecified.
  • The "Aha" Moment on Complexity: The discovery that the complexity is governed by the geometric mean-like term $K^{1/3}d^{2/3}$ is the paper's centerpiece. It shows that the "hardness" of the problem is a specific interaction between the flexibility of the class ($d$) and its internal disagreement ($K$).
  • Online Learning Connection: The authors show that in the online (sequential) version of this problem, the "regret" (how much worse you do than the best fixed hypothesis) is directly controlled by the diameter $K$, independent of the time horizon $T$.

Key Results

  • Optimal Sample Complexity: For a class with VC dimension $d$ and diameter $K$, the number of samples $m$ needed for error $\varepsilon$ is: $$m \approx \frac{K^{1/3} d^{2/3}}{\varepsilon}$$ (ignoring logarithmic factors and confidence parameters).

  • Tightness: They proved this is the best possible bound by showing that for any $d$ and $K$, there exists a class that requires this many samples.

  • Online Regret: They established that the minimax expected regret for this setting is $\Theta(K)$. This means a learner will make at most $O(K)$ more mistakes than the best hypothesis in the class, regardless of how long the game lasts.

Limitations and Future Work

  • Binary vs. Multiclass: The current work is strictly for binary classification. Extending these "diameter-based" bounds to multiclass learning remains an open challenge.
  • Active Learning: The authors suggest that "Active Learning" (where the learner chooses which points to label) might offer even better speedups in this deterministic setting, potentially reaching a complexity of $O(K/\varepsilon)$ or better.
  • Infinite Diameter: For classes with infinite diameter, the authors introduced a parameter called PERT-VC, but it's not yet clear if this perfectly matches the lower bound (SET-VC). Resolving whether these two combinatorial parameters are identical is a key open question left for the community.

Summary updated

Abstract

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class $C$. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when $C$ has finite diameter $K$ and VC dimension $d$, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee $O(d/\varepsilon^2)$ to $\widetilde{O}(K/\varepsilon)$, but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension $d$ and finite diameter $K$ is learnable with sample complexity $\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right)$, and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.
BibTeX
@misc{bendavid2026near,
  author = {Shai Ben-David and Steve Hanneke and Farnam Mansouri and Amirreza Shaeiri},
  title = {{Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning}},
  year = {2026},
  eprint = {2611.13210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13210},
}
Figure