Abstract: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 $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves 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 of \citet{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.
| Subjects: | Machine Learning (cs.LG) |
| MSC classes: | 68Q32, 68Q17, 41A10 |
| ACM classes: | F.2.2; I.2.6 |
| Cite as: | arXiv:2605.02350 [cs.LG] |
| (or arXiv:2605.02350v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.02350 arXiv-issued DOI via DataCite (pending registration) |
From: Tim Sinen [view email]
[v1]
Mon, 4 May 2026 08:53:40 UTC (49 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。