mlsanityData to 14 Oct 2026

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

arXiv 2605.02350 ↗First posted 4 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the complexity of smoothed agnostic learning of halfspaces on ± 1n under uniform marginals in the model of~citeKM25, where each input coordinate is independently flipped with probability σ ∈ (0, 1/2). We show that L1 polynomial regression achieves runtime and sample complexity tildeO(nO(log(1/varepsilon)/σ)), and prove a nearly matching Statistical Query complexity lower bound of nOmega(log(1+σ/varepsilon2)/σ). This complements the recent work of~citeDK26, which established analogous bounds in the continuous setting under Gaussian marginals.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 47 references that are in the map. First posted on arXiv 4 May 2026.

Builds on

21 of 47 references.

References · 21

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  4. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  5. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  6. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  7. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  8. 2016A General Characterization of the Statistical Query Complexitycited by 27
  9. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  10. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  11. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  12. 2014Approximate resilience, monotonicity, and the complexity of agnostic learningcited by 16
9 more
  1. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  2. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  3. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  4. 2022Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginalscited by 6
  5. 2025Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Modelscited by 5
  6. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  7. 2025Smoothed Agnostic Learning of Halfspaces over the Hypercubecited by 3
  8. 2025Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysiscited by 3
  9. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1

Built on by

Not cited yet.