Optimal Learning Under Tsybakov Noise

Steve Hanneke, Hongao Wang, Mingyue XuarXiv 2026 · arXiv

TL;DR

This paper resolves a 20-year-old open problem in statistical learning theory by establishing the minimax optimal error rate for learning under Tsybakov noise. The authors introduce a novel algorithm called MERIT that adaptively partitions the data space into regions of differing noise levels, successfully eliminating a long-standing logarithmic gap using a proper learner.

What Problem Does This Paper Address?

In Probably Approximately Correct (PAC) learning, a classic assumption is "realizability"—the idea that there is a perfect, noise-free target function that labels the data. Because real-world data is rarely pristine, researchers use noise models to make the theory more practical.

The simplest model is Massart noise, where the probability of a label being flipped is strictly bounded away from a random coin toss (1/2). However, in reality, data points near a decision boundary are often extremely ambiguous and noisy. To capture this, the Tsybakov noise model allows for highly noisy points but constrains how frequently they can occur using a parameter $\alpha \in (0,1)$.

In 2006, Massart and Nédélec established the foundational upper and lower bounds for learning general concept classes under Tsybakov noise. However, a frustrating gap remained: the upper bound was larger than the lower bound by a logarithmic factor ($\log(n/d)$). For two decades, learning theorists did not know if this gap was an artifact of loose mathematical analysis or a fundamental limitation of learning algorithms. This paper finally closes that gap.

Methods

The authors introduce an algorithm called MERIT (Massart Error Regions Isolation under Tsybakov noise).

Instead of treating the entire dataset uniformly, MERIT adaptively decomposes the instance space into distinct regions based on their effective noise levels. The key steps include:

  1. Adaptive Space Partitioning: The algorithm recursively isolates regions of the instance space where pairs of hypotheses disagree significantly but yield similar empirical errors. By slicing away these high-disagreement zones, the algorithm forces the remaining space to behave like a cleaner "Massart-like" environment.
  2. Concept Class Pruning: MERIT maintains a candidate pool of hypotheses and systematically prunes away sub-optimal concepts round-by-round using a carefully scheduled sequence of error thresholds ($\gamma_t$) and noise resolutions ($\beta_t$).
  3. Sample Splitting: To maintain statistical independence and avoid overfitting during the partitioning process, the algorithm splits the training sample into three disjoint subsets ($S_1, S_2, S_3$) dedicated to risk estimation, region isolation, and final hypothesis selection, respectively.
  4. Proper Learning: Unlike many modern optimal learners that rely on complex ensembles or majority votes (improper learners), MERIT is a proper learner—it outputs a single hypothesis belonging strictly to the original concept class $\mathcal{H}$.

Datasets

Not discussed in the paper. This work is entirely theoretical and mathematical; it focuses on proving minimax learning rates using statistical mechanics and uniform concentration inequalities rather than empirical validation on benchmark datasets.

Key Insights and Ideas

  • Localizing Tsybakov Noise: The core "aha moment" is realizing that while Tsybakov noise is globally complex, it can be localized. By adaptively partitioning the space, the algorithm treats a Tsybakov noise distribution as a collection of localized regions that each satisfy a simpler, linear Bernstein (Massart-like) condition.
  • The Surprising Optimality of Proper Learners: In the simpler realizable setting, it is well-known that proper learners (like standard Empirical Risk Minimization) cannot always avoid a logarithmic overhead; one must use improper learners to achieve optimal rates. Surprisingly, this paper demonstrates that under the more complex Tsybakov noise setting, a proper learner can actually achieve absolute optimality.
  • Fine-Grained Variance Control: By leveraging a refined uniform Bernstein inequality, the authors avoid loose global variance bounds, allowing them to optimize sample complexity dynamically across different noise regimes.

Key Results

The primary mathematical achievement of the paper is proving that the excess risk of the hypothesis ($h_{\text{ALG}}$) returned by MERIT satisfies:

$$ \mathbb{P}_{\mathcal{D}}(\text{ER}(h_{\text{ALG}})) - \mathbb{P}_{\mathcal{D}}(\text{ER}(h^*_{\mathcal{D}})) \le \mathcal{O} \left( \left( \frac{d + \log(1/\delta)}{n} \right)^{\frac{1}{2-\alpha}} \right) $$

where $n$ is the sample size, $d$ is the VC dimension of the concept class, and $\delta$ is the failure probability. This upper bound perfectly matches the known statistical lower bound, effectively eliminating the $\log(n/d)$ factor gap that stood for 20 years.

Limitations and Future Work

  • Parameter Dependence: The MERIT algorithm requires prior knowledge of the Tsybakov noise parameters ($a$ and $\alpha$). In practice, these parameters are rarely known. Developing an adaptive algorithm that achieves the same optimal rate without knowing the noise parameters beforehand is a crucial next step.
  • Confidence Dependence: The algorithm is $\delta$-dependent, meaning it must know the target confidence parameter in advance to structure its sample splitting and partitioning thresholds.
  • Computational Efficiency: MERIT is an existential proof of optimal sample complexity but relies on an abstract Empirical Risk Minimization (ERM) oracle across recursive loops. Whether this approach can be translated into a computationally efficient, polynomial-time algorithm for practical concept classes (like Halfspaces) remains an open question.

Summary updated

Abstract

Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model, $\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}$ is a concept class, and $h^*\in\mathcal{H}$ is the target concept to be learned. Having access to i.i.d. labeled examples from a distribution $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$, which admits $h^*$ as the best concept in $\mathcal{H}$, the goal is to design a learning algorithm that outputs a hypothesis having low error competitive to $h^{*}$ with high probability. This model was initially studied under the realizable setting, which assumes that $h^*$ has no error. A natural relaxation is to allow label noise, that is, the true label can be flipped with probability $η\in(0,1/2)$. In reality, certain labels might be extremely noisy, especially for those points near the decision boundary. Hence, it is natural to allow very noisy points, though only rarely. This is quantified by a noise model introduced by [MT99] and [Tsy04], now known as Tsybakov noise. For learning general concept classes, [MN06] gave the general upper and lower bounds for error guarantees under Tsybakov noise. However, their upper and lower bounds differ by a logarithmic factor. Resolving this gap has remained a well-known open question for the past twenty years. In this work, we resolve this open question by improving the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise. Our learning algorithm operates by adaptively partitioning the instance space into regions, roughly corresponding to different noise levels, and returning a hypothesis in the concept class satisfying a specific error constraint for each region. Our technique shares a conceptual foundation with several recent advances in non-realizable learning, such as [HLZ24] and [Han25].
BibTeX
@misc{hanneke2026optimal,
  author = {Steve Hanneke and Hongao Wang and Mingyue Xu},
  title = {{Optimal Learning Under Tsybakov Noise}},
  year = {2026},
  eprint = {2608.08416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.08416},
}
Figure