Testable Learning of General Halfspaces under Massart Noise

Ilias Diakonikolas; Giannis Iakovidis; Daniel M. Kane; Sihan Liu

cs.DSFeb 25, 2026

Testable Learning of General Halfspaces under Massart Noise

Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu

Organizations: UW Madison · UC San Diego

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.

Figures & tables

\widehat{\mathbf{M}}\coloneqq\E_{(\mathbf{x},y)\sim\widehat{D}}[H(\mathbf{U}^{\top}\mathbf{x})H^{\top}(\mathbf{U}^{\top}\mathbf{x})\left(yh(\mathbf{x})-\beta+\epsilon\right)\mid\mathbf{x}\in S].

Algorithm 1 Testable Learner for

\gamma

-Biased halfspaces.

Panel of Figure 1 — Figure 1: Illustration of a learned halfspace $h$ , a competing halfspace $f$ , the slices on which the tests are performed, and their disagreement region (shaded).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: This figure shows our approximation procedure. Top left: $\dfrac{T_{m}(x)}{mx}$ ; we see that it is a polynomial with a bump-function shape. Top right: $f(x)=\left(\dfrac{T_{m}(x)}{mx}\right)^{k}$ ( Equation 1 ); as the power $k$ increases, $f$ becomes increasingly concentrated and approximates $\delta$ . Bottom: the integral $p$ of $f$ over a sliding window ( Equation 3 ), which approximates a step function. The sliding-window length is chosen according to the desired accuracy; consequently, our approximation is forced to drop to $0$ outside the window. In all examples, the plotted curves grow polynomially to infinity beyond the figure, but this effect is controlled because the Gaussian tails dominate.

Halfspace Learning

See all 13 papers

Efficiently Learning Drifting Halfspaces with Massart Noise
Jun 9, 2026Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1Noisy-Label Learning Low-Degree Polynomial Method
University of Wisconsin-Madison
Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Apr 29, 2026Jizhou Huang, Brendan JubaAgnostic Learning Statistical Learning Theory
Meta · Washington Universtiy in St. Louis

Jun 9, 2026J/K move · Enter open · S save

Efficiently Learning Drifting Halfspaces with Massart Noise

Mingchen Ma, Guyang Cao, Jelena Diakonikolas, Ilias Diakonikolas

University of Wisconsin-Madison

Noisy-Label Learning Low-Degree Polynomial Method Learning with Noisy Labels Halfspace Learning Adaptive Learning Margin-Based Learning

Open paper AskPDF arXiv

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.

Abstract

Halfspace Learning

Explore similar work

Efficiently Learning Drifting Halfspaces with Massart Noise

Actively Learning Halfspaces without Synthetic Data

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals