# Learning Halfspaces with Tsybakov Noise

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 15 of 15)

- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Online Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/2405.12958/) (2024)
- [Reliable Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2411.11238/) (2024)
- [Enhancing PAC Learning of Half spaces Through Robust Optimization Techniques](https://mlsanity.com/paper/2410.16573/) (2024)
- [Testable Learning of General Halfspaces under Massart Noise](https://mlsanity.com/paper/2602.22300/) (2026)

## Abstract (arXiv)

We study the efficient PAC learnability of halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, each label is independently flipped with some probability which is controlled by an adversary. This noise model significantly generalizes the Massart noise model, by allowing the flipping probabilities to be arbitrarily close to 1/2 for a fraction of the samples. Our main result is the first non-trivial PAC learning algorithm for this problem under a broad family of structured distributions -- satisfying certain concentration and (anti-)anti-concentration properties -- including log-concave distributions. Specifically, we given an algorithm that achieves misclassification error ε with respect to the true halfspace, with quasi-polynomial runtime dependence in 1/epsilin. The only previous upper bound for this problem -- even for the special case of log-concave distributions -- was doubly exponential in 1/ε (and follows via the naive reduction to agnostic learning). Our approach relies on a novel computationally efficient procedure to certify whether a candidate solution is near-optimal, based on semi-definite programming. We use this certificate procedure as a black-box and turn it into an efficient learning algorithm by searching over the space of halfspaces via online convex optimization.