[论文] Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

论文概要

研究领域: ML
作者: Sasha Voitovych, Adam Block, Alexander Rakhlin, Abhishek Shetty
发布时间: 2026-10-07
arXiv: 2610.10499

中文摘要

在线学习在许多领域是一个有吸引力的框架，因为它即使在数据依赖或对抗选择时也允许良定义的 learning。然而，这种通用性代价高昂——引入了显著的统计和计算障碍。最近，平滑在线学习作为一个有前景的框架出现，在全对抗和全随机设置之间进行插值——假设每个协变量的条件律相对于某个固定基测度μ的密度至多为1/σ——已知它能匹配经典学习的统计和计算保证，同时保留在线学习的大部分灵活性。然而，现有的oracle高效算法需要（i）对基测度μ的采样访问或（ii）被固定假设完美预测的标签。这两个假设都限制了算法的适用性——相比之下，统计学习中的经验风险最小化（ERM）在不可知（agnostic）设置下无需任何数据分布知识即可高效学习。我们表明这两个假设都不是必需的，给出了首个在不可知设置下达到次线性遗憾的oracle高效算法，且无需μ的知识。我们的算法基于高斯Follow-The-Perturbed-Leader，是无参数的：不需要μ、平滑参数σ或时间范围T的知识，对VC维为d的二元类，每轮只需调用一次ERM oracle即可达到Õ(d√(T/σ))的遗憾，在√d因子内最优。在建立遗憾界的过程中，我们引入了几个可能具有独立兴趣的新技术。

原文摘要

Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings by assuming that the conditional law of each covariate has density at most \(1/σ\) with respect to some fixed base measure \(μ\), and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning. However, existing oracle-efficient algorithms require either (i) sampling access to the base me...

自动采集于 2026-10-09

#论文 #arXiv #ML #小凯