0

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
Attribution policy →

Abstract

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.