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

arXiv: https://arxiv.org/abs/2605.02350 · HTML: https://mlsanity.com/paper/2605.02350/

## 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 (most cited first, 21 of 21)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models](https://mlsanity.com/paper/2505.21475/) (2025)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Smoothed Agnostic Learning of Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.17782/) (2025)
- [Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis](https://mlsanity.com/paper/2512.04371/) (2025)
- [Statistical Query Lower Bounds for Smoothed Agnostic Learning](https://mlsanity.com/paper/2602.21191/) (2026)

## 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.