论文标题
连续时间Nesterov加速梯度方法，用于集中和分布式在线凸优化
A Continuous-Time Nesterov Accelerated Gradient Method for Centralized and Distributed Online Convex Optimization
论文作者
论文摘要
本文通过使用在线连续时间Nesterov加速梯度方法（OCT-NAG）来研究在线凸优化问题。我们表明，Bregman Lagrangian的在线版本生成的连续时间动力学实现了不断的静态遗憾$ \ frac {c}σ$独立于$ t $，但前提是对目标函数和最佳解决方案持有的某些有界假设。据作者所知，这是文献中最低的静态遗憾（低于$ o（\ text {log}（t））$）。我们进一步表明，在相同的假设下，算法的动态遗憾是$ o（t）$，与现有方法相媲美。仿真结果验证了该方法的有效性和效率。此外，模拟表明该算法在某些特定缩放条件下的动态遗憾方面表现良好。此外，我们考虑了所提出的在线优化方法在分布式在线优化问题中的应用，并表明所提出的算法实现了$ O（\ sqrt {t}）$ static遗憾，这与现有的分布式在线优化方法相媲美。与这些方法不同，所提出的方法既不需要梯度界限假设，也不需要紧凑的约束集假设，该假设允许不同的目标函数和文献中的问题不同。获得了可比的动态遗憾。仿真结果显示了分布式算法的有效性和效率。
This paper studies the online convex optimization problem by using an Online Continuous-Time Nesterov Accelerated Gradient method (OCT-NAG). We show that the continuous-time dynamics generated by the online version of the Bregman Lagrangian achieves a constant static regret $\frac{c}σ$ independent of $T$, provided that some boundedness assumptions on the objective functions and optimal solutions hold. To the best of the authors' knowledge, this is the lowest static regret in the literature (lower than $O(\text{log}(T))$). We further show that under the same assumptions, the dynamic regret of the algorithm is $O(T)$, which is comparable with the existing methods. Simulation results validate the effectiveness and efficiency of the method. Furthermore, the simulation shows that the algorithm performs well in terms of the dynamic regret for some specific scaling conditions. In addition, we consider the application of the proposed online optimization method in distributed online optimization problems, and show that the proposed algorithm achieves an $O(\sqrt{T})$ static regret, which is comparable with the existing distributed online optimization methods. Different from these methods, the proposed method requires neither the gradient boundedness assumption nor the compact constraint set assumption, which allows different objective functions and different optimization problems with those in the literature. A comparable dynamic regret is obtained. Simulation results show the effectiveness and efficiency of the distributed algorithm.
