在噪声中学习动态线性分类器，效率与精度兼顾。
Efficiently Learning Drifting Halfspaces with Massart Noise
- 设计高效算法应对概念漂移与Massart噪声
- 误差率逼近理论下限，达η + O(Δ^{1/3}/γ)
- 适合研究在线学习与鲁棒性优化的学者
我们研究在Massart噪声下学习漂移概念的问题。在线学习者每轮访问一组独立样本，其标签是可能随轮次变化的目标概念的带噪版本。目标是每轮输出预测误差小的假设。针对可分半空间这一基础分类类，我们提出一个计算高效的算法，误差为η + Õ(Δ^{1/3}/γ)，其中η为Massart噪声率上界，Δ为漂移率，γ为间隔。在可实现情形下，该方法改进了先前工作。另一方面，我们证明存在信息-计算权衡：即使在随机分类噪声的特例中，低次多项式测试也无法突破Δ^{1/3}量级，暗示算法性能近乎最优。理论上最优误差为Δ^{1/2}量级。
原文摘要 · Abstract (English)
We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error $η+ \tilde O(Δ^{1/3}/γ)$, where $η$ upper bounds the Massart noise rate, $Δ$ is the drift rate, and $γ$ is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with $Δ^{1/2}$, we prove that $Δ^{1/3}$-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。