mlsanityData to 7 Oct 2026

SQ Lower Bounds for Learning Single Neurons with Massart Noise

arXiv 2210.09949 ↗First posted 18 Oct 2022cs.LG cs.DS math.STcited by 5

Not on the map. Why?

Abstract (arXiv)

We study the problem of PAC learning a single neuron in the presence of Massart noise. Specifically, for a known activation function f: ℝ → ℝ, the learner is given access to labeled examples (x, y) ∈ ℝd × ℝ, where the marginal distribution of x is arbitrary and the corresponding label y is a Massart corruption of f(langle w, x rangle). The goal of the learner is to output a hypothesis h: ℝd → ℝ with small squared loss. For a range of activation functions, including ReLUs, we establish super-polynomial Statistical Query (SQ) lower bounds for this learning problem. In more detail, we prove that no efficient SQ algorithm can approximate the optimal error within any constant factor. Our main technical contribution is a novel SQ-hard construction for learning ± 1-weight Massart halfspaces on the Boolean hypercube that is interesting on its own right.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 16 of its 33 references that are in the map. First posted on arXiv 18 Oct 2022.

Builds on

16 of 33 references.

References · 16

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2017Learning ReLUs via Gradient Descentcited by 54
  3. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  4. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  5. 2020Learning a Single Neuron with Gradient Methodscited by 50
  6. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  7. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  8. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  9. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  10. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  11. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  12. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
4 more
  1. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  2. 2021ReLU Regression with Massart Noisecited by 10
  3. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  4. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 2.

5 papers.

  1. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  2. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  3. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  4. 2024Online Learning of Halfspaces with Massart Noisecited by 1
  5. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0