A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
Provides near-optimal statistical query lower bounds for smoothed agnostic learning of halfspaces, complementing recent results in the continuous Gaussian setting.
This paper studies smoothed agnostic learning of halfspaces under the uniform distribution on the hypercube, showing that L1 polynomial regression achieves complexity Õ(n^{O(log(1/ε)/σ)}) and proving a nearly matching SQ lower bound of n^{Ω(log(1+σ/ε^2)/σ)}.
We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under the uniform distribution in the model of \citet{KM25} where each input coordinate is independently flipped with probability $σ\in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves 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 \citet{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.