Testable Learning of General Halfspaces under Massart Noise

• URL: http://arxiv.org/abs/2602.22300v1
• Date: Wed, 25 Feb 2026 18:30:10 GMT
• Title: Testable Learning of General Halfspaces under Massart Noise
• Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu,
• Abstract summary: We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution.<n>In the testable learning setting, the aim is the design of a tester-learner pair satisfying the following properties.<n>Our main result is the first testable learning algorithm for general halfspaces with Massart noise and marginals.
• Score: 40.15176310729312
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-learner pair satisfying the following properties: (1) if the tester accepts, the learner outputs a hypothesis and a certificate that it achieves near-optimal error, and (2) it is highly unlikely that the tester rejects if the data satisfies the underlying assumptions. Our main result is the first testable learning algorithm for general halfspaces with Massart noise and Gaussian marginals. The complexity of our algorithm is $d^{\mathrm{polylog}(\min\{1/γ, 1/ε\})}$, where $ε$ is the excess error and $γ$ is the bias of the target halfspace, which qualitatively matches the known quasi-polynomial Statistical Query lower bound for the non-testable setting. The analysis of our algorithm hinges on a novel sandwiching polynomial approximation to the sign function with multiplicative error that may be of broader interest.

Related papers

• Efficient Testable Learning of General Halfspaces with Adversarial Label Noise [37.4323638115877]
  We study the task of testable learning of general halfspaces with adversarial label noise. In the testable learning framework, the goal is to develop a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data. At the heart of our approach is a new methodology to reduce testable learning of general halfspaces to testable learning of nearly homogeneous halfspaces that may be of broader interest.
  arXiv  Detail & Related papers  (2024-08-30T10:08:21Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
  In the recently introduced testable learning model, one is required to produce a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data. Our tester-learner runs in time $poly(d/eps)$ and outputs a halfspace with misclassification error $O(opt)+eps$, where $opt$ is the 0-1 error of the best fitting halfspace.
  arXiv  Detail & Related papers  (2023-03-09T18:38:46Z)
• An Efficient Tester-Learner for Halfspaces [13.13131953359806]
  We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023) In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes a test.
  arXiv  Detail & Related papers  (2023-02-28T18:51:55Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  We study the design of tester-learner pairs $(mathcalA,mathcalT)$. We show that if the distribution on examples in the data passes the tester $mathcalT$ then one can safely trust the output of the agnostic $mathcalA$ on the data.
  arXiv  Detail & Related papers  (2022-04-14T19:10:53Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  We study the problem of agnostically learning halfspaces under the Gaussian. Our main result is the em first proper learning algorithm for this problem.
  arXiv  Detail & Related papers  (2021-02-10T18:40:44Z)
• 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)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• 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.