提出近最优的半平面学习算法，有效应对马萨特噪声。
A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
- 用在线SGD和精心设计的凸损失序列实现高效学习
- 样本复杂度达近似最优的 $\widetilde{\Theta}(1/(γ^2 ε^2))$
- 适合需要高鲁棒性且关注计算效率的研究者
我们研究在马萨特噪声下学习 $γ$-边缘半平面的PAC学习问题。理论上，该问题的样本复杂度为 $\widetilde{\Theta}(1/(γ^2 ε))$。此前高效的算法样本复杂度为 $\tilde{O}(1/(γ^4 ε^3))$，可达到 $η+ε$ 的0-1误差，其中 $η<1/2$ 为噪声率上界。近期工作表明存在信息-计算权衡，暗示高效算法需至少 $1/ε^2$ 的依赖。本文提出一种计算高效算法，样本复杂度为 $\widetilde{\Theta}(1/(γ^2 ε^2))$，几乎达到此下界。算法简洁实用，基于在线随机梯度下降与精心设计的凸损失序列。
原文摘要 · Abstract (English)
We study the problem of PAC learning $γ$-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be $\widetildeΘ(1/(γ^2 ε))$. Prior computationally efficient algorithms for the problem incur sample complexity $\tilde{O}(1/(γ^4 ε^3))$ and achieve 0-1 error of $η+ε$, where $η<1/2$ is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on $1/ε$ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity $\widetildeΘ(1/(γ^2 ε^2))$, nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。