We study the dynamic regret of a new class of online learning problems, in which the gradient of the loss function changes continuously across rounds with respect to the learner's decisions. This setup is motivated by the use of online learning as a tool to analyze the performance of iterative algorithms. Our goal is to identify interpretable dynamic regret rates that explicitly consider the loss variations as consequences of the learner's decisions as opposed to external constraints. We show that achieving sublinear dynamic regret in general is equivalent to solving certain variational inequalities, equilibrium problems, and fixed-point problems. Leveraging this identification, we present necessary and sufficient conditions for the existence of efficient algorithms that achieve sublinear dynamic regret. Furthermore, we show a reduction from dynamic regret to both static regret and convergence rate to equilibriums in the aforementioned problems, which allows us to analyze the dynamic regret of many existing learning algorithms in few steps.

通过建立连续在线学习（COL）这种新的设置，连续轮次中在线损失函数的梯度会随着学习者的决策而连续变化，我们可以更完整地描述许多有趣的应用，特别地，证明了满足单调EPs（经济平衡问题）能够在COL中实现子线性的静态遗憾。 由此得出的启示是，我们提供了实现子线性动态遗憾的有效算法的条件，即使选择的损失在先验变化预算中没有适应性。 此外，我们还展示了一个从动态遗憾到静态遗憾和相关EP（经济平衡问题）收敛的COL之间的简化，从而允许我们分析许多现有算法的动态遗憾。

连续变化的在线学习：动态遗憾和缩减