# Statistical Query Lower Bounds for Smoothed Agnostic Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 18 of 18)

- [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)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models](https://mlsanity.com/paper/2505.21475/) (2025)
- [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)

## Built on by (most cited first, 1 of 1)

- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)

## Abstract (arXiv)

We study the complexity of smoothed agnostic learning, recently introduced by~citeCKKMS24, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on L1-polynomial regression and has complexity d^tildeO(1/σ2) log(1/ε), where σ is the smoothing parameter and ε is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity d^Omega(1/σ2+log(1/ε)). This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying L1-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the L1-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.