Behavior of accelerated gradient methods near critical points of nonconvex functions
Behavior of accelerated gradient methods near critical points of nonconvex functions
复制标题
DOI：
10.1007/s10107-018-1340-y
复制
发表时间：
2017-06
影响因子：
2.7
通讯作者：
Michael O'Neill;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
Michael O'Neill;Stephen J. Wright
我们研究了光滑非凸无约束优化中加速梯度法的行为，特别关注它们在严格鞍点附近的行为。加速方法是迭代方法，其通常沿沿着方向步进，该方向是前一步和在当前步长处或附近的点处评估的函数的梯度的线性组合。(The前一步骤对来自迭代过程中的较早阶段的梯度信息进行编码）。我们表明，通过稳定的流形定理，重球方法是不太可能收敛到严格的鞍点，这是点的目标的梯度为零，但Hessian至少有一个负特征值。然后，我们研究了重球方法和其他加速梯度方法在非凸二次函数的严格鞍点附近的行为，表明这两种方法都可以比最速下降法更快地从这一点发散。
We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process). We show by means of the stable manifold theorem that the heavy-ball method is unlikely to converge to strict saddle points, which are points at which the gradient of the objective is zero but the Hessian has at least one negative eigenvalue. We then examine the behavior of the heavy-ball method and other accelerated gradient methods in the vicinity of a strict saddle point of a nonconvex quadratic function, showing that both methods can diverge from this point more rapidly than the steepest-descent method.