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 unifying
framework for the analysis and design of these algorithms is still missing. In
this paper, \emph{we show that dynamic regret minimization is equivalent to
static regret minimization in an extended decision space}. Using this simple
observation, we show that there is a frontier of lower bounds trading off
penalties due to the variance of the losses and penalties due to variability of
the comparator sequence, and provide a framework for achieving any of the
guarantees along this frontier. As a result, we prove for the first time that
adapting to the squared path-length of an arbitrary sequence of comparators to
achieve regret $R_{T}(u_{1},\dots,u_{T})\le O(\sqrt{T\sum_{t}
\|u_{t}-u_{t+1}\|^{2}})$ is impossible. However, we prove that it is possible
to adapt to a new notion of variability based on the locally-smoothed squared
path-length of the comparator sequence, and provide an algorithm guaranteeing
dynamic regret of the form $R_{T}(u_{1},\dots,u_{T})\le \tilde
O(\sqrt{T\sum_{i}\|\bar u_{i}-\bar u_{i+1}\|^{2}})$. Up to polylogarithmic
terms, the new notion of variability is never worse than the classic one
involving the path-length.

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