High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
复制标题
DOI：
10.1109/cdc42340.2020.9304444
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Bo Sun;Jemin George;Solmaz S. Kia
中科院分区：
文献类型：
--
作者：
Bo Sun;Jemin George;Solmaz S. Kia
由于基于梯度的优化算法可以从极限常微分方程（ODE）的角度进行研究，本文推导了加速三动量（TM）算法的ODE表示.对于具有强凸代价的无约束优化问题，TM算法具有比Nesterov加速梯度（NAG）方法更快的收敛速度，但具有相同的计算复杂度。我们表明，类似于NAG方法，为了准确地捕捉TM方法的特点，我们需要使用高分辨率建模来获得TM算法的ODE表示。我们提出了一个李雅普诺夫分析调查的稳定性和收敛行为的建议的高分辨率常微分方程表示的TM算法。我们比较了TM方法的ODE表示的速度与NAG方法，以确认其更快的收敛速度。我们的研究还导致了更严格的限制的最差收敛速度的ODE模型的NAG方法。在本文中，我们还讨论了使用积分二次约束（IQC）的方法来建立一个估计的TM算法的收敛速度。一个数值例子验证了我们的结果。
Motivated by the fact that the gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs), here we derive an ODE representation of the accelerated triple momentum (TM) algorithm. For unconstrained optimization problems with strongly convex cost, the TM algorithm has a proven faster convergence rate than the Nesterov's accelerated gradient (NAG) method but with the same computational complexity. We show that similar to the NAG method, in order to accurately capture the characteristics of the TM method, we need to use a high-resolution modeling to obtain the ODE representation of the TM algorithm. We propose a Lyapunov analysis to investigate the stability and convergence behavior of the proposed high-resolution ODE representation of the TM algorithm. We compare the rate of the ODE representation of the TM method with that of the NAG method to confirm its faster convergence. Our study also leads to a tighter bound on the worst rate of convergence for the ODE model of the NAG method. In this paper, we also discuss the use of the integral quadratic constraint (IQC) method to establish an estimate on the rate of convergence of the TM algorithm. A numerical example verifies our results.