On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
复制标题
DOI：
10.48550/arxiv.2305.08658
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
P. Dobson;J. Sanz-Serna;K. Zygalakis
中科院分区：
文献类型：
--
作者：
P. Dobson;J. Sanz-Serna;K. Zygalakis
我们重新审视Fazylab等人（SIAM J. Optim. 28，2018）构造离散和连续时间优化算法的李雅普诺夫函数。对于光滑的，强凸的目标函数，我们放松了必要的要求，这样的建设。其结果是，我们能够证明Polyak的常微分方程和一个双参数家族的Nesterov算法的收敛速度，改善那些在文献中。我们分析解释Nesterov算法的离散化的Polyak方程。我们表明，该算法的情况下，添加剂的龙格-库塔积分，并讨论了为什么大多数离散的微分方程不导致优化算法与加速的原因。我们还引入了一个修改的Polyak方程，并研究了它的收敛性。最后，我们扩展的一般框架的随机情况下，并考虑应用随机算法加速overparameterized模型，再次，我们能够证明收敛速度，提高在文献中。
We revisit the general framework introduced by Fazylab et al. (SIAM J. Optim. 28, 2018) to construct Lyapunov functions for optimization algorithms in discrete and continuous time. For smooth, strongly convex objective functions, we relax the requirements necessary for such a construction. As a result we are able to prove for Polyak's ordinary differential equations and for a two-parameter family of Nesterov algorithms rates of convergence that improve on those available in the literature. We analyse the interpretation of Nesterov algorithms as discretizations of the Polyak equation. We show that the algorithms are instances of Additive Runge-Kutta integrators and discuss the reasons why most discretizations of the differential equation do not result in optimization algorithms with acceleration. We also introduce a modification of Polyak's equation and study its convergence properties. Finally we extend the general framework to the stochastic scenario and consider an application to random algorithms with acceleration for overparameterized models; again we are able to prove convergence rates that improve on those in the literature.