强凸损失理论在适当在线学习中的最优动态遗憾及其扩展

Jan, 2022

强凸损失理论在适当在线学习中的最优动态遗憾及其扩展

Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond

Dheeraj Baby, Yu-Xiang Wang

TL;DR本文研究了强凸损失函数下的动态遗憾最小化框架，通过利用 KKT 条件所施加的许多新约束条件，我们回答了 Baby 和 Wang 2021 年提出的一个开放性问题，并展示了强适应算法在适当的学习设置下可以同时针对任何比较序列达到几乎最优的动态遗憾。此外，在处理非平滑损失和改善回避维度依赖性等方面，我们还取得了 Baby 和 Wang 2021 年工作的其他改进，并针对 exp-concave 损失和一个 L∞受限决策集的特殊情况导出了几乎最优的动态遗憾率。

Abstract

We study the framework of universal dynamic regret minimization with strongly convex losses. We answer an open problem in Baby and Wang 2021 by showing that in a proper learning setup, strongly adaptive algorithms

dynamic regret minimization strongly adaptive algorithms total variation kkt conditions exp-concave losses

发现论文，激发创造

指数凸在线学习的最优动态遗憾

使用先进的证明技术和 Zinkevich-style 动态遗憾最小化框架，本研究提出了一个强适应的在线学习算法，其总变化控制下的动态遗憾为 O (n^(1/3)*C_n^(2/3))，并且可以扩展到局部自适应非参数回归问题中。

Apr, 2021

凸光滑函数的动态遗憾

本文提出了一种在线凸优化算法，该算法在非稳态环境中表现出优异的动态后悔表现，通过充分利用流畅性条件，能够在动态后悔中代替对 T 的依赖，而采用问题相关的数量：损失函数的梯度变化、比较序列的累积损失和前两个 term 的最小值，从而使问题的复杂度自适应问题的困难程度，即在简单问题上使界限更紧，同时保证了最坏情况下相同的界限。

Jul, 2020

动态环境下的自适应在线学习

本文研究动态环境下的在线凸优化问题，通过提出一种自适应学习的方法 Ader，利用专家跟踪算法结合一组专家来最小化动态遗憾，并扩展到可用于表征比较器的动态模型序列的情形。

Oct, 2018

动态环境下的在线优化：强凸问题改进遗憾率

本文提出一种基于在线梯度下降方法的动态调参算法，以降低动态遗憾（dynamic regret），进而优化强凸且未知动力学的损失函数。

Mar, 2016

在线凸规划的动态模型和跟踪遗憾度

本研究提出了一种新的在线凸优化方法，利用候选动态模型家族建立新的跟踪后悔界，并通过追踪和基于模型的预测相结合，相对于高变化比较序列生成低的后悔。

Jan, 2013

静态和动态遗憾最小化之间的等价关系

动态遗憾最小化在在线凸优化中是一个重要问题。本文提出了一个新的统一框架来分析和设计这些算法，证明了适应任意比较序列的动态遗憾达到 O (根号下 T 总和的局部平滑化平方路径长度) 的算法是可行的，并且提供了一个替代路径长度计算方式的新概念来实现更好的适应性。