On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
复制标题
非凸优化的随机坐标梯度下降的全局收敛性
DOI：
10.1137/21m1460375
复制
发表时间：
2023
影响因子：
3.1
通讯作者：
Lu, Jianfeng
中科院分区：
文献类型：
--
作者：
Chen, Ziang;Li, Yingzhou;Lu, Jianfeng
在这项工作中，我们分析了非凸优化问题的坐标和步长随机选择的坐标梯度下降的全局收敛性。在一般的假设下，我们证明了该算法几乎肯定会逃脱严格的鞍点的目标函数。因此，如果所有鞍点都是严格的，则保证算法收敛到局部极小。我们的证明是基于将坐标下降算法视为一个非线性随机动力系统，并对其在鞍点附近的线性化进行了定量的有限块分析。
In this work, we analyze the global convergence property of a coordinate gradient descent with random choice of coordinates and stepsizes for nonconvex optimization problems. Under generic assumptions, we prove that the algorithm iterate will almost surely escape strict saddle points of the objective function. As a result, the algorithm is guaranteed to converge to local minima if all saddle points are strict. Our proof is based on viewing the coordinate descent algorithm as a nonlinear random dynamical system and a quantitative finite block analysis of its linearization around saddle points.
影响因子：
2.7
作者：
Mert Gurbuzbalaban;A. Ozdaglar;N. D. Vanli;Stephen J. Wright
通讯作者：
Mert Gurbuzbalaban;A. Ozdaglar;N. D. Vanli;Stephen J. Wright
影响因子：
2.1
作者：
Ching-pei Lee;Stephen J. Wright
通讯作者：
Ching-pei Lee;Stephen J. Wright