A Near-optimal {SQ} Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
We study the complexity of smoothed agnostic learning of halfspaces on ${\pm 1}^n$ under uniform marginals, where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\Omega(\log(1+\sigma/\varepsilon^2)/\sigma)}$. This complements the recent work, which established analogous bounds in the continuous setting under Gaussian marginals.
- Veröffentlicht in:
arXiv - Typ:
Article - Autoren:
- Jahr:
2026 - Source:
http://arxiv.org/abs/2605.02350
Informationen zur Zitierung
: A Near-optimal {SQ} Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces, arXiv, 2026, {arXiv}:2605.02350, May, {arXiv}, http://arxiv.org/abs/2605.02350, Sinen.2026a,
@Article{Sinen.2026a,
author={Sinen, Tim},
title={A Near-optimal {SQ} Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces},
journal={arXiv},
number={{arXiv}:2605.02350},
month={May},
publisher={{arXiv}},
url={http://arxiv.org/abs/2605.02350},
year={2026},
abstract={We study the complexity of smoothed agnostic learning of halfspaces on ${\pm 1}^n$ under uniform marginals, where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/\sigma)})$, and prove a nearly matching Statistical Query complexity lower...}}