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

It is known that gradient descent (GD) on a [Formula: see text] 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 [Formula: see text] 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 [Formula: see text]). 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].