Hardness of Learning Halfspaces with Massart Noise

Ilias Diakonikolas, Daniel M. KanearXiv 2020 · arXiv · OpenReview

Abstract

We study the problem of PAC learning halfspaces with Massart noise. Given labeled samples $(x, y)$ from a distribution $D$ on $\mathbb{R}^{d} \times \{ \pm 1\}$ such that the marginal $D_x$ on the examples is arbitrary and the label $y$ of example $x$ is generated from the target halfspace corrupted by a Massart adversary with flipping probability $\eta(x) \leq \eta \leq 1/2$, the goal is to compute a hypothesis with small misclassification error. The best known $\mathrm{poly}(d, 1/\epsilon)$-time algorithms for this problem achieve error of $\eta+\epsilon$, which can be far from the optimal bound of $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT} = \mathbf{E}_{x \sim D_x} [\eta(x)]$. While it is known that achieving $\mathrm{OPT}+o(1)$ error requires super-polynomial time in the Statistical Query model, a large gap remains between known upper and lower bounds. In this work, we essentially characterize the efficient learnability of Massart halfspaces in the Statistical Query (SQ) model. Specifically, we show that no efficient SQ algorithm for learning Massart halfspaces on $\mathbb{R}^d$ can achieve error better than $\Omega(\eta)$, even if $\mathrm{OPT} = 2^{-\log^{c} (d)}$, for any universal constant $c \in (0, 1)$. Furthermore, when the noise upper bound $\eta$ is close to $1/2$, our error lower bound becomes $\eta - o_{\eta}(1)$, where the $o_{\eta}(1)$ term goes to $0$ when $\eta$ approaches $1/2$. Our results provide strong evidence that known learning algorithms for Massart halfspaces are nearly best possible, thereby resolving a longstanding open problem in learning theory.

Introduction

Learning linear classifiers, or halfspaces, is a fundamental task in machine learning. In an ideal PAC (Probably Approximately Correct) learning setting, data is perfectly separable by a hyperplane. However, real-world data is rarely clean. To model this, researchers use various noise models. The Massart noise model is a particularly interesting "semi-random" model: for any given data point $x$, an adversary can flip its label with a probability $\eta(x)$, provided that this probability never exceeds a fixed upper bound $\eta < 1/2$.

For decades, a significant gap has existed between the information-theoretic limits of learning and the performance of efficient algorithms. While it is theoretically possible to achieve an error rate close to the actual average noise ($OPT + \epsilon$) given enough samples, the most efficient polynomial-time algorithms have only been able to guarantee an error of $\eta + \epsilon$. This paper investigates whether this gap is a result of algorithmic limitations or an inherent computational barrier.

The Computational-Statistical Gap

The core of the problem lies in the discrepancy between $OPT$ (the average noise) and $\eta$ (the maximum noise). If an adversary caps their noise at $\eta = 0.4$ but only actually corrupts $1\%$ of the data ($OPT = 0.01$), current efficient algorithms might still return a model with nearly $40\%$ error.

This work provides a definitive answer within the Statistical Query (SQ) model. The SQ model is a standard framework for analyzing the complexity of learning problems. In this model, algorithms do not access individual samples but instead receive estimates of expectations of functions over the distribution. Since most standard optimization techniques—including Gradient Descent, Support Vector Machines, and the Method of Moments—can be implemented as SQ algorithms, a lower bound in this model serves as powerful evidence of general computational hardness.

Methodology: Constructing "Diabolical" Distributions

To prove that no efficient SQ algorithm can beat the $\eta$ error barrier, the authors construct a specific, difficult distribution that hides the true classification boundary from any algorithm limited to statistical queries. The construction involves several sophisticated steps:

  1. Hidden Direction and Moment Matching: The authors create a high-dimensional distribution that appears to be standard Gaussian noise in almost every direction. Along one secret "hidden" direction, the distribution is carefully engineered so that its first several statistical moments (mean, variance, skewness, etc.) perfectly match those of a standard Gaussian. This makes the hidden direction invisible to any low-degree statistical probe.
  2. The Massart Constraint: The primary challenge is ensuring this distribution satisfies the Massart noise condition. The authors utilize a "miracle" construction involving a mixture of offset discrete Gaussians. By carefully spacing a grid of points, they create a distribution where the labels are ambiguous enough to satisfy the $\eta$ bound while keeping the true $OPT$ error extremely small.
  3. Veronese Mapping (Lifting): To translate the hardness of learning complex boundaries back to the simple case of halfspaces, the authors use a mathematical "lifting" trick. They first prove hardness for high-degree Polynomial Threshold Functions (PTFs) and then use the Veronese mapping to project these into a higher-dimensional space where they appear as linear halfspaces.

Key Results

The paper establishes that the $\eta$ barrier is essentially fundamental for efficient algorithms. The key findings include:

  • Super-Polynomial Hardness: No efficient SQ algorithm can achieve an error better than $\Omega(\eta)$, even if the optimal classifier has an exponentially small error (e.g., $OPT = 2^{-\log^c(d)}$).
  • Tightness at High Noise: As the noise bound $\eta$ approaches $1/2$ (the point where the signal is completely lost to noise), the lower bound tightens to $\eta - o(1)$. This shows that as the problem becomes harder, the gap between the best possible algorithm and the $\eta$ bound vanishes.
  • Optimality of Current Algorithms: This result confirms that the algorithm proposed by Diakonikolas et al. (2019), which achieves $\eta + \epsilon$ error, is nearly optimal for distribution-independent learning.

Discussion and Future Work

This research essentially resolves a long-standing open problem by showing that the difficulty of learning Massart halfspaces is not due to a lack of algorithmic ingenuity, but rather the inherent structure of the SQ model.

However, some avenues remain open. While SQ hardness covers most practical ML algorithms, it does not rule out non-SQ methods like Gaussian elimination (which is rarely used in practice due to its sensitivity to noise). Future research may look toward establishing NP-hardness or average-case hardness based on cryptographic assumptions to provide an even broader proof of intractability. Additionally, tightening the constant factor in the $\Omega(\eta)$ bound to exactly $\eta$ for all noise levels remains a final technical hurdle in fully characterizing this problem space.

Summary updated

Abstract

We study the problem of PAC learning halfspaces with Massart noise. Given labeled samples $(x, y)$ from a distribution $D$ on $\mathbb{R}^{d} \times \{ \pm 1\}$ such that the marginal $D_x$ on the examples is arbitrary and the label $y$ of example $x$ is generated from the target halfspace corrupted by a Massart adversary with flipping probability $\eta(x) \leq \eta \leq 1/2$, the goal is to compute a hypothesis with small misclassification error. The best known $\mathrm{poly}(d, 1/\epsilon)$-time algorithms for this problem achieve error of $\eta+\epsilon$, which can be far from the optimal bound of $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT} = \mathbf{E}_{x \sim D_x} [\eta(x)]$. While it is known that achieving $\mathrm{OPT}+o(1)$ error requires super-polynomial time in the Statistical Query model, a large gap remains between known upper and lower bounds. In this work, we essentially characterize the efficient learnability of Massart halfspaces in the Statistical Query (SQ) model. Specifically, we show that no efficient SQ algorithm for learning Massart halfspaces on $\mathbb{R}^d$ can achieve error better than $\Omega(\eta)$, even if $\mathrm{OPT} = 2^{-\log^{c} (d)}$, for any universal constant $c \in (0, 1)$. Furthermore, when the noise upper bound $\eta$ is close to $1/2$, our error lower bound becomes $\eta - o_{\eta}(1)$, where the $o_{\eta}(1)$ term goes to $0$ when $\eta$ approaches $1/2$. Our results provide strong evidence that known learning algorithms for Massart halfspaces are nearly best possible, thereby resolving a longstanding open problem in learning theory.
BibTeX
@misc{diakonikolas2020hardness,
  author = {Ilias Diakonikolas and Daniel M. Kane},
  title = {{Hardness of Learning Halfspaces with Massart Noise}},
  year = {2020},
  eprint = {2012.09720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.09720},
}
Figure