证明平滑版半空间学习的下界，揭示现有方法已接近最优。
Statistical Query Lower Bounds for Smoothed Agnostic Learning
- 通过统计查询框架构造难题分布，基于对偶线性规划找匹配矩的分布。
- 首次给出平滑学习半空间的下界：复杂度至少为 d^{Ω(1/σ² + log(1/ε))}。
- 结果表明 L1 多项式回归在平滑模型中几乎无法被超越，适合理论学习研究者。
我们研究了近期提出的平滑版抗扰学习（smoothed agnostic learning）的复杂性，该任务中学习者需在输入受微小高斯扰动时，逼近目标分类器类中的最优分类器。重点考察在亚高斯分布下，对半空间进行平滑版抗扰学习的典型问题。目前已知的最佳上界依赖于 L1-多项式回归，复杂度为 d^{~O(1/σ²) log(1/ε)}，其中 σ 为平滑参数，ε 为额外误差。本文的主要成果是给出了首个非平凡的统计查询（SQ）下界，表明此上界接近最优：即使对于高斯边缘，任何用于平滑版半空间学习的 SQ 算法复杂度至少为 d^{Ω(1/σ² + log(1/ε))}。我们通过线性规划对偶构造了一个矩匹配的难例分布，其对偶形式等价于寻找目标函数平滑版本的低次近似多项式——这正是 L1-多项式回归有效性的条件。最终的下界来源于对半空间类在此平滑版本下的近似次数的分析。
原文摘要 · Abstract (English)
We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on $L_1$-polynomial regression and has complexity $d^{\tilde{O}(1/σ^2) \log(1/ε)}$, where $σ$ is the smoothing parameter and $ε$ is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity $d^{Ω(1/σ^{2}+\log(1/ε))}$. This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying $L_1$-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the $L_1$-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。