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

Jun, 2024

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

An Equivalence Between Static and Dynamic Regret Minimization

Andrew Jacobsen, Francesco Orabona

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

Abstract

We study the problem of dynamic regret minimization in online convex optimization, in which the objective is to minimize the difference between the cumulative loss of an algorithm and that of an arbitrary sequence of comparators. While the literature on this topic is very rich, a unify

dynamic regret minimization online convex optimization unifying framework lower bounds variance of losses

发现论文，激发创造

凸光滑函数的动态遗憾

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

Jul, 2020

非退化函数的改进动态遗憾

本文介绍了一种通过多次查询函数梯度并减弱强凸性条件来优化在线学习器性能的方法，并引入了比路径长度更小的平方路径长度作为比较序列的新规则。

Aug, 2016

同时最小化动态遗憾和适应性遗憾

本文提出了一种在线学习算法，能同时最小化动态遗憾和自适应遗憾，具有更强的理论保证。

Feb, 2020

在线最小二乘及其拓展问题中平衡静态与动态遗憾

本文研究递归最小二乘算法中的遗忘因子对在线牛顿算法动态后悔的影响，对于指数凸和强凸目标，算法可实现动态后悔的界限，同时提出一种用于强凸函数的梯度下降步长规则以获得更高的计算效率。

Sep, 2019

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

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

Oct, 2018

在线优化：与动态比较器竞争

本文提出了一种完全自适应的方法，适用于在线学习中的动态比较基准，并且应用到了零和博弈中。

Jan, 2015

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

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

Jan, 2022

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

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

Jan, 2013

动态环境下的在线线性回归与折扣

我们开发了一种用于在线线性回归的算法，即使在完全没有先验知识的情况下，也能实现最佳的静态和动态遗憾保证。

May, 2024

追踪缓慢移动的预知者：真实梯度和噪声梯度下的在线学习最优动态遗憾

本研究关注在线凸优化的动态遗憾，通过探索称为路径变化的时间变化机制，提出了一些动态遗憾改进的变差上限，并证明他们在已有的下限条件下是最优的。

May, 2016