arXiv:2605.02350 · v3

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

首次提交 2026-05-04 16:53

版本更新 2026-11-11 10:07

雷达观测 2026-11-13 11:11

摘要

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.

作者备注：Conference version; 21 pages + 7 pages checklist