Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
复制标题
DOI：
10.1093/imaiai/iaac025
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Rishabh Dixit;W. Bajwa
中科院分区：
文献类型：
--
作者：
Rishabh Dixit;W. Bajwa
本文研究了在某些初始边界条件下，从鞍域出发理解梯度相关一阶方法轨迹的退出时间问题。考虑到鞍点周围的“平坦”几何形状，由于遇到的梯度幅度较小，一阶方法在快速逃离这些区域时可能会遇到困难。特别是，虽然已知梯度相关的一阶方法逃避严格鞍域，但现有文献并未明确利用鞍点周围的局部几何来控制梯度轨迹的行为。在此背景下，本文利用矩阵摄动理论对严格鞍域附近的梯度下降法进行了严格的几何分析。在这样做的过程中，它提供了一个关键的结果，可以用来在任何给定的初始条件下生成近似的梯度轨迹。此外，分析还得到了一类严格鞍函数的梯度下降法在一定初始条件下的线性存在解。
This paper considers the problem of understanding the exit time for trajectories of gradient-related first-order methods from saddle neighborhoods under some initial boundary conditions. Given the `flat' geometry around saddle points, first-order methods can struggle in escaping these regions in a fast manner due to the small magnitudes of gradients encountered. In particular, while it is known that gradient-related first-order methods escape strict-saddle neighborhoods, existing literature does not explicitly leverage the local geometry around saddle points in order to control behavior of gradient trajectories. It is in this context that this paper puts forth a rigorous geometric analysis of the gradient-descent method around strict-saddle neighborhoods using matrix perturbation theory. In doing so, it provides a key result that can be used to generate an approximate gradient trajectory for any given initial conditions. In addition, the analysis leads to a linear exit-time solution for gradient-descent method under certain necessary initial conditions for a class of strict-saddle functions.