Gradient Descent Avoids Strict Saddles with a Simple Line-Search Method Too

It is known that gradient descent (GD) on a $C^2$ cost function generically avoids strict saddle points when using a small, constant step size. However, no such guarantee existed for GD with a line-search method. We provide one for a modified version of the standard Armijo backtracking method with generic, arbitrarily large initial step size. The proof underlines the role of the Luzin $N^{-1}$ property for the iteration maps and allows us to forgo the habitual Lipschitz gradient assumption. We extend this to the Riemannian gradient descent (RGD) setting, assuming the retraction is real analytic (though the cost function still only needs to be $C^2$). In closing, we also improve guarantees for RGD with a constant step size in some scenarios.

Funding: This work was supported by the Swiss State Secretariat for Education, Research and Innovation [Grant MB22.00027].