论文标题
改进了强烈凸出和光滑功能的动态遗憾的分析
Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
论文作者
论文摘要
在本文中，我们提出了对强烈凸出和平滑功能的动态遗憾的改进分析。具体而言，我们研究了Zhang等人提出的在线多重梯度下降（OMGD）算法。 （2017）。原始分析表明，OMGD的动态遗憾最多是$ \ MATHCAL {O}（\ min \ {\ Mathcal {p} _t，\ Mathcal {s} _t _T \}）$在线功能的最小化器的运动。我们证明，通过改进的分析，可以将OMGD的动态遗憾提高到$ \ Mathcal {o}（\ min \ {\ Mathcal {p} _t，\ Mathcal {s} _t，\ Mathcal，\ Mathcal {v}请注意，$ \ MATHCAL {P} _T，\ MATHCAL {S} _t，\ MATHCAL {V} _T $的数量基本上反映了环境非平稳性的不同方面 - 它们在一般情况下不可比拟，并且在不同的场景中受到青睐。因此，本文所表现出的动态遗憾实际上实现了\ emph {三分之二 - 世界的保证}的保证，并且严格比以前的结果更紧密。
In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T\})$, where $\mathcal{P}_T$ and $\mathcal{S}_T$ are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T,\mathcal{V}_T\})$, where $\mathcal{V}_T$ is the function variation of the online functions. Note that the quantities of $\mathcal{P}_T, \mathcal{S}_T, \mathcal{V}_T$ essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a \emph{best-of-three-worlds} guarantee and is strictly tighter than previous results.
