Gradient Descent Avoidance of Strict Saddle Points via Stable Manifold Theorem

Gradient Descent Avoidance of Strict Saddle Points via Stable Manifold Theorem is a dynamical-systems and non-convex optimization analysis introduced by Lee, Simchowitz, Jordan, and Recht (2016) proving that deterministic gradient descent x_{k+1} = g(x_k) = x_k - alpha grad f(x_k) with constant step size 0 < alpha < 1 / L on any twice continuously differentiable, L-gradient-Lipschitz function f: R^d -> R converges to a strict saddle point x^* (where grad f(x^*) = 0 and lambda_min(grad^2 f(x^*)) < 0) only from a set of initial conditions W_s of Lebesgue measure zero. The proof proceeds in two key steps: Proposition 4.5 proves via the proximal envelope and inverse function theorem that for 0 < alpha < 1 / L the gradient map g(x) = x - alpha grad f(x) is a global bi-Lipschitz C^1 diffeomorphism whose Jacobian Dg(x) = I - alpha grad^2 f(x) has det(Dg(x)) != 0 everywhere and satisfies lambda_max(Dg(x^*)) = 1 - alpha lambda_min(grad^2 f(x^*)) > 1 at every strict saddle x^*; Theorem 4.1 then applies the Shub (1987) Local Center-Stable Manifold Theorem (Theorem 4.2) to show that the local stable set W_{loc}^{cs}(x^*) is a C^1 submanifold of codimension at least 1 (hence Lebesgue measure zero), and countable pullbacks union_{k>=0} g^{-k}(W_{loc}^{cs}) preserve measure zero even when the strict saddle set A^* is uncountably infinite via Lindelof's lemma.