Bounds for the Tracking Error of First-Order Online Optimization Methods
Bounds for the Tracking Error of First-Order Online Optimization Methods
复制标题
DOI：
10.1007/s10957-021-01836-9
复制
发表时间：
2020-03
影响因子：
1.9
通讯作者：
Liam Madden;Stephen Becker;E. Dall’Anese
中科院分区：
文献类型：
--
作者：
Liam Madden;Stephen Becker;E. Dall’Anese
本文研究了平滑时变优化问题的在线算法，首先关注具有恒定步长、动量和外推长度的方法。假设强凸性，得出在线梯度下降的跟踪迭代误差（最优解与迭代之间的范数的极限上限值）的精确结果。然后，本文考虑了一个通用的一阶框架，其中建立了跟踪迭代误差的通用下界。此外，还提出并展示了一种使用“长步长”的方法来实现固定常数的下界。然后针对具体示例将该方法与在线梯度下降进行比较。最后，论文分析了代价非强凸时正则化的效果。通过正则化，可以实现无悔界限。本文最后分别测试了合成时变最小二乘问题和逻辑回归问题的加速方法和正则化方法。
This paper investigates online algorithms for smooth time-varying optimization problems, focusing first on methods with constant step-size, momentum, and extrapolation-length. Assuming strong convexity, precise results for the tracking iterate error (the limit supremum of the norm of the difference between the optimal solution and the iterates) for online gradient descent are derived. The paper then considers a general first-order framework, where a universal lower bound on the tracking iterate error is established. Furthermore, a method using “long-steps” is proposed and shown to achieve the lower bound up to a fixed constant. This method is then compared with online gradient descent for specific examples. Finally, the paper analyzes the effect of regularization when the cost is not strongly convex. With regularization, it is possible to achieve a non-regret bound. The paper ends by testing the accelerated and regularized methods on synthetic time-varying least-squares and logistic regression problems, respectively.