Optimal Learning Under Tsybakov Noise

Steve Hanneke; Hongao Wang; Mingyue Xu

cs.LGAug 9, 2026

Optimal Learning Under Tsybakov Noise

Authors: Steve Hanneke, Hongao Wang, Mingyue Xu

Organizations: Department of Computer Science Purdue University

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].

Explore similar work

May 18, 2026cs.LG

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes

k

is at least

3

, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers

\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}

using at most

O(k^2\cdot (d\log d+\log k))

samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e.

k=2

, our result is strictly stronger than all prior works.

Rita Adhikari, Shiwei Zeng

Multiclass Classification Noise-Aware

Ask PDF

Sep 15, 2026cs.DS

Efficient Robust Learning at the Information-Theoretic Limit

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of

η+ \varepsilon

where

η

is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than

2η+ \varepsilon.

Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error

η+ \varepsilon

for any constant

\varepsilon

Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1

Topic pending

Ask PDF

Jun 9, 2026cs.LG

Efficiently Learning Drifting Halfspaces with Massart Noise

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error

η+ \tilde O(Δ^{1/3}/γ)

, where

η

upper bounds the Massart noise rate,

Δ

is the drift rate, and

γ

is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with

Δ^{1/2}

, we prove that

Δ^{1/3}

-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.

Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1

Scaling Laws

Ask PDF