Optimal Learning Under Tsybakov Noise

• URL: http://arxiv.org/abs/2608.08416v1
• Date: Sun, 09 Aug 2026 02:20:51 GMT
• Title: Optimal Learning Under Tsybakov Noise
• Abstract summary: We design a learning algorithm that outputs a hypothesis having low error competitive to $h*$ with high probability.<n>Our technique shares a conceptual foundation with several recent advances in non-realizable learning.
• Score: 31.74405851825694
• License: http://creativecommons.org/licenses/by/4.0/
• 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].

Related papers

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice.<n>Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable.<n>Larsen, Pabbaraju, and Shetty, who introduced this model, show that empirical risk minimization attains expected error $O((d/n)log(n/d))$ for classes of VC dimension $d$.
  arXiv  Detail & Related papers  (2026-08-06T17:45:32Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Revisiting Agnostic PAC Learning [30.67561230812141]
  PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. Empirical Risk Minimization (ERM) is a natural learning algorithm, where one simply outputs the hypothesis from $mathcalH$ making the fewest mistakes on the training data. We revisit PAC learning and first show that ERM is in fact sub-optimal if we treat the performance of the best hypothesis, denoted $tau:=Pr_mathcalD[hstar_math
  arXiv  Detail & Related papers  (2024-07-29T08:20:49Z)
• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible. We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
  arXiv  Detail & Related papers  (2024-06-26T18:19:10Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  We study the task of online learning in the presence of Massart noise. We present a computationally efficient algorithm that achieves mistake bound $eta T + o(T)$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k) Delta T - o(T)$ bigger than choosing a random action at every round.
  arXiv  Detail & Related papers  (2024-05-21T17:31:10Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  We revisit the classical problem of multiclass classification with bandit feedback. We present a new bandit classification algorithm that guarantees regret $smashwidetildeO(|H|+sqrtT)$.
  arXiv  Detail & Related papers  (2024-05-16T12:11:09Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.