证明了在平滑噪声下学习布尔半空间的近最优统计查询下界。
A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
- 提出在独立翻转噪声下学习半空间的统计查询复杂度分析方法。
- 证明下界为 $n^{Ω(/log(1+σ/ε^2)/σ)}$，接近上界 $\tilde{O}(n^{O(\log(1/ε)/σ)})$。
- 适用于研究学习复杂性下界与噪声鲁棒性之间的关系的理论研究者。
我们研究在均匀边际分布下，对 \{\pm 1\}^n 上的半空间进行平滑对抗性学习的复杂性，其中每个输入坐标以概率 $σ \in (0, 1/2)$ 独立翻转。我们证明 $L^1$ 多项式回归可实现运行时间和样本复杂度 $\tilde{O}(n^{O(\log(1/\varepsilon)/σ)})$，并建立了几乎匹配的统计查询复杂度下界 $n^{Ω(\log(1+σ/\varepsilon^2)/σ)}$。该结果补充了近期工作 [DK26] 在高斯边际下的连续情形中建立的类似边界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。