论文标题
Lipschitz和在线学习中的比较者 - 表现适应性
Lipschitz and Comparator-Norm Adaptivity in Online Learning
论文作者
论文摘要
我们在无限制的环境中研究在线凸优化，在该环境中，预测和梯度都没有受到限制。目的是同时适应梯度序列和比较器。我们首先为带有提示的简化设置开发无参数和无标度算法。我们提供两个版本：第一个版本适应了比较器和梯度的平方规范，每发$ O（d）$时间，第二个适应其平方内部产品（仅在比较方向上衡量方差），每回合$ O（d^3）$。然后，我们将两个先前的缩减概括为无界设置。一个不需要提示，第二次处理范围比问题（这在先前的工作中已经出现）。我们根据先验和新的下限讨论它们的最佳性。我们采用我们的方法来获得使用线性模型的规模不变在线预测的更清晰的后悔界限。
We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.
