We study the complexity of smoothed agnostic learning of halfspaces on {\pm 1}^n under uniform marginals in the model of \cite{KM25}, where each input coordinate is independently flipped with probability σ\in (0, {1}/{2}). We show that L^1 polynomial regression achieves runtime and sample complexity \tilde{O}(n^{O(\log(1/\varepsilon)/σ)}), and prove a nearly matching Statistical Query complexity lower bound of n^{Ω(\log(1+σ/\varepsilon^2)/σ)}. This complements the recent work of \cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.
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 in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability $σ\in (0, {1}/{2})$.
- Preview

- Year
- 2026
- Hosting
- Excerpt onlyCC-BY-NC-SA-4.0
Cite
Notes
Only stored in your browser.
Attribution
- Abstract & full text
- arxiv.org/abs/2605.02350CC-BY-NC-SA-4.0
- TL;DR
- Semantic Scholar