Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond
Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond
复制标题
DOI：
10.1609/aaai.v34i04.6149
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Jianjun Yuan;Andrew G. Lamperski
中科院分区：
文献类型：
--
作者：
Jianjun Yuan;Andrew G. Lamperski
递归最小二乘算法通常使用遗忘因子作为启发式算法来适应非平稳数据流。本文的第一个贡献是严格刻画了遗忘因子对一类在线牛顿算法的影响。对于指数凹目标和强凸目标，算法的动态遗憾度为$\max\{O（\log T），O（\sqrt{TV}）\}$，其中V$是比较序列路径长度的一个界.特别是，我们展示了如何经典的递归最小二乘遗忘因子实现这个动态的遗憾界。通过改变$V$，我们得到了静态和动态后悔之间的权衡。为了获得更高的计算效率的算法，我们的第二个贡献是一个新的梯度下降步长规则的强凸函数。我们的梯度下降规则恢复了上述顺序最优动态遗憾界限。对于光滑问题，我们也可以得到静态后悔为O（T^{1-\beta}）$和动态后悔为O（T^\beta V^*）$，其中$\beta \in（0，1）$和$V^*$是极小点序列的路径长度。通过改变$\beta$，我们得到了静态和动态后悔之间的权衡。
Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms achieve the dynamic regret of $\max\{O(\log T),O(\sqrt{TV})\}$, where $V$ is a bound on the path length of the comparison sequence. In particular, we show how classic recursive least-squares with a forgetting factor achieves this dynamic regret bound. By varying $V$, we obtain a trade-off between static and dynamic regret. In order to obtain more computationally efficient algorithms, our second contribution is a novel gradient descent step size rule for strongly convex functions. Our gradient descent rule recovers the order optimal dynamic regret bounds described above. For smooth problems, we can also obtain static regret of $O(T^{1-\beta})$ and dynamic regret of $O(T^\beta V^*)$, where $\beta \in (0,1)$ and $V^*$ is the path length of the sequence of minimizers. By varying $\beta$, we obtain a trade-off between static and dynamic regret.