Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms
Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms
复制标题
基于动量的加速优化算法的收敛速度和噪声放大之间的权衡
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mihailo R. Jovanovi'c
中科院分区：
文献类型：
--
作者：
Hesameddin Mohammadi;Meisam Razaviyayn;Mihailo R. Jovanovi'c
我们研究了基于动量的一阶优化算法，其中迭代利用来自前两个步骤的信息，并受到加性白噪声的影响。这类算法包括Polyak的heavy-ball和Nesterov的加速方法，作为特殊情况和噪声在梯度计算或迭代更新中的不确定性。对于强凸二次问题，我们使用优化变量中误差的稳态方差来量化噪声放大并确定基本的随机性能权衡。我们的方法利用陪审团稳定性准则提供了线性收敛条件的一种新的几何表征，并阐明了噪声放大与收敛速率之间的关系以及它们对条件数和恒定算法参数的依赖关系。这种几何洞察力导致标准收敛结果的简单替代证明，并允许我们建立与条件数成二次比例的稳定时间和噪声放大之间乘积的解析下界。我们的分析还确定了梯度和迭代噪声模型之间的一个关键区别：虽然通过充分减速算法可以使梯度噪声的放大任意小，但迭代噪声模型可实现的最佳方差放大随减速状态下的沉降时间线性增加。此外，我们引入了两个参数化的算法族，它们在噪声放大和稳定时间之间取得平衡，同时保持两种噪声模型的有序Pareto最优性。最后，通过分析一类加速梯度流动力学，其适当的离散化产生两步动量算法，我们建立了随机性能权衡也可以扩展到连续时间。
We study momentum-based first-order optimization algorithms in which the iterations utilize information from the two previous steps and are subject to an additive white noise. This class of algorithms includes Polyak's heavy-ball and Nesterov's accelerated methods as special cases and noise accounts for uncertainty in either gradient evaluation or iteration updates. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification and identify fundamental stochastic performance tradeoffs. Our approach utilizes the Jury stability criterion to provide a novel geometric characterization of conditions for linear convergence, and it clarifies the relation between the noise amplification and convergence rate as well as their dependence on the condition number and the constant algorithmic parameters. This geometric insight leads to simple alternative proofs of standard convergence results and allows us to establish analytical lower bounds on the product between the settling time and noise amplification that scale quadratically with the condition number. Our analysis also identifies a key difference between the gradient and iterate noise models: while the amplification of gradient noise can be made arbitrarily small by sufficiently decelerating the algorithm, the best achievable variance amplification for the iterate noise model increases linearly with the settling time in decelerating regime. Furthermore, we introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time while preserving order-wise Pareto optimality for both noise models. Finally, by analyzing a class of accelerated gradient flow dynamics, whose suitable discretization yields the two-step momentum algorithm, we establish that stochastic performance tradeoffs also extend to continuous time.
登录
查看更多内容
强凸二次优化问题的加速一阶算法的方差放大
DOI：
10.1109/cdc.2018.8619183
发表时间：
2018
期刊：
2018 IEEE Conference on Decision and Control (CDC
影响因子：
--
作者：
Mohammadi, Hesameddin;Razaviyayn, Meisam;Jovanovic, Mihailo R.
通讯作者：
Jovanovic, Mihailo R.
影响因子：
5.9
作者：
通讯作者：
--
影响因子：
2.2
作者：
Jianchao Bai;W. Hager;Hongchao Zhang
通讯作者：
Jianchao Bai;W. Hager;Hongchao Zhang
影响因子：
2.7
作者：
Bin Hu;P. Seiler;Laurent Lessard
通讯作者：
Bin Hu;P. Seiler;Laurent Lessard
影响因子：
3.1
作者：
Fazlyab, Mahyar;Ribeiro, Alejandro;Preciado, Victor M.
通讯作者：
Preciado, Victor M.