Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm
Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm
复制标题
DOI：
10.1109/tit.2022.3213607
复制
发表时间：
2021-01
影响因子：
2.5
通讯作者：
Rishabh Dixit;M. Gürbüzbalaban;W. Bajwa
中科院分区：
文献类型：
--
作者：
Rishabh Dixit;M. Gürbüzbalaban;W. Bajwa
相关的一阶方法已成为大规模数值优化问题的主力。许多这些问题涉及非凸目标函数与多个鞍点，这需要了解的行为的离散轨迹的一阶方法内的几何景观，这些功能。本文讨论了一阶离散方法收敛到非凸优化问题的局部极小值的问题，这些问题包括几何景观中的严格鞍点。为此，重点分析了鞍点邻域附近的离散梯度轨迹，推导了这些轨迹在线性时间内逃离严格鞍点邻域的充分条件，探讨了这些轨迹在严格鞍点邻域中的收缩和扩张动力学，这些轨迹的特征是具有中等大小的梯度，描述了这些轨迹的非弯曲性质，并强调了这些轨迹在离开它们之后不能重新进入严格鞍点周围的邻域。基于这些见解和分析，本文然后提出了一个简单的变种香草梯度下降算法，称为曲率条件正则梯度下降（CCRGD）算法，它利用检查初始边界条件，以确保其轨迹可以逃脱严格的鞍邻域在线性时间。文中还对CCRGD算法的收敛性进行了分析，包括收敛到局部极小值的速度。数值实验测试功能，以及低秩矩阵分解问题，以评估所提出的算法的有效性。
Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict-saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.