On Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
On Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
复制标题
DOI：
10.1609/aaai.v35i8.16858
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Ting-Jui Chang;Shahin Shahrampour
中科院分区：
文献类型：
--
作者：
Ting-Jui Chang;Shahin Shahrampour
动态在线学习算法的后悔界限通常用函数序列 (V_T) 的变化和/或 T 轮后最小化序列的路径长度来表示。对于强凸函数和平滑函数，Zhang 等人。 (2017) 建立最小化序列 (C*_{2,T}) 的平方路径长度作为后悔的下限。他们还表明，在线梯度下降（OGD）每轮使用多个梯度查询来实现这个下限。在本文中，我们重点关注无约束在线优化。我们首先证明 OGD 的预处理变体每轮一次梯度查询可实现 O(min{C*_T,C*_{2,T}})（C*_T 指正常路径长度）。然后，我们针对函数序列的一阶和二阶信息可预测的情况提出在线乐观牛顿（OON）方法。 OON 的后悔界限是通过最小化序列 (C*_{4,T}) 的四次路径长度捕获的，该长度可能比 C*_{2,T} 小得多。我们最终证明，通过使用 OGD 的多个梯度，我们可以在后悔上实现 O(min{C*_{2,T},V_T}) 的上限。
The regret bound of dynamic online learning algorithms is often expressed in terms of the variation in the function sequence (V_T) and/or the path-length of the minimizer sequence after T rounds. For strongly convex and smooth functions, Zhang et al. (2017) establish the squared path-length of the minimizer sequence (C*_{2,T}) as a lower bound on regret. They also show that online gradient descent (OGD) achieves this lower bound using multiple gradient queries per round. In this paper, we focus on unconstrained online optimization. We first show that a preconditioned variant of OGD achieves O(min{C*_T,C*_{2,T}}) with one gradient query per round (C*_T refers to the normal path-length). We then propose online optimistic Newton (OON) method for the case when the first and second order information of the function sequence is predictable. The regret bound of OON is captured via the quartic path-length of the minimizer sequence (C*_{4,T}), which can be much smaller than C*_{2,T}. We finally show that by using multiple gradients for OGD, we can achieve an upper bound of O(min{C*_{2,T},V_T}) on regret.