# Optimal Learning Under Tsybakov Noise

arXiv: https://arxiv.org/abs/2608.08416 · HTML: https://mlsanity.com/paper/2608.08416/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 57 references that are in the map.
- First posted on arXiv 9 Aug 2026.

## Builds on (most cited first, 19 of 19)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [On the Value of Target Data in Transfer Learning](https://mlsanity.com/paper/2002.04747/) (2020)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [A No-Free-Lunch Theorem for MultiTask Learning](https://mlsanity.com/paper/2006.15785/) (2020)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)

## Abstract (arXiv)

Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model, H subseteq 0,1X is a concept class, and h^*∈H is the target concept to be learned. Having access to i.i.d. labeled examples from a distribution D over X×0,1, which admits h^* as the best concept in 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 η∈(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].