论文标题
没有Lipschitz的连续性的遗憾界限：在线学习与相对lipschitz的损失
Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses
论文作者
论文摘要
在在线凸优化（OCO）中，通常假定功能的Lipschitz连续性是为了获得额定性遗憾。此外，当这些功能也很强时，许多算法只有对数遗憾。最近，凸优化的研究人员提出了“相对Lipschitz连续性”和“相对强凸度”的概念。这两个概念都是其经典同行的概括。已经表明，相对设置中的亚级别方法具有类似于其经典环境的性能的性能。 在这项工作中，我们考虑了相对Lipschitz和相对强烈凸功能的OCO。我们将已知的经典OCO算法的遗憾范围扩展到相对设置。具体来说，我们为“正规领导者算法”和在线镜像下降的变体显示了遗憾的界限。由于这些方法的普遍性，这些结果对多种OCO算法产生了遗憾的界限。此外，我们将结果进一步扩展到具有额外正规化的算法，例如正则双重平均。
In online convex optimization (OCO), Lipschitz continuity of the functions is commonly assumed in order to obtain sublinear regret. Moreover, many algorithms have only logarithmic regret when these functions are also strongly convex. Recently, researchers from convex optimization proposed the notions of "relative Lipschitz continuity" and "relative strong convexity". Both of the notions are generalizations of their classical counterparts. It has been shown that subgradient methods in the relative setting have performance analogous to their performance in the classical setting. In this work, we consider OCO for relative Lipschitz and relative strongly convex functions. We extend the known regret bounds for classical OCO algorithms to the relative setting. Specifically, we show regret bounds for the follow the regularized leader algorithms and a variant of online mirror descent. Due to the generality of these methods, these results yield regret bounds for a wide variety of OCO algorithms. Furthermore, we further extend the results to algorithms with extra regularization such as regularized dual averaging.
