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

References

• [1] Absil PA, Mahony R, Andrews B (2005) Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2):531–547.Crossref, Google Scholar
• [2] Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [3] Cheeger J, Ebin DG (1975) Comparison Theorems in Riemannian Geometry, vol. 9 (North-Holland, Amsterdam).Google Scholar
• [4] Cohn DL (2013) Measure Theory, 2nd ed. (Springer, New York).Crossref, Google Scholar
• [5] Criscitiello C, Boumal N (2019) Efficiently escaping saddle points on manifolds. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 ((Curran Associates Inc., Red Hook, NY), 5985–5995.Google Scholar
• [6] Davis D, Drusvyatskiy D (2021) Proximal methods avoid active strict saddles of weakly convex functions. Foundations Comput. Math. 22(2):561–606.Crossref, Google Scholar
• [7] Davis D, Drusvyatskiy D, Jiang L (2025) Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization. Foundations Comput. Math. 26(2):779–861.Crossref, Google Scholar
• [8] Dixit R, Gürbüzbalaban M, Bajwa WU (2023) Boundary conditions for linear exit time gradient trajectories around saddle points: Analysis and algorithm. IEEE Trans. Inform. Theory 69(4):2556–2602.Crossref, Google Scholar
• [9] Dixit R, Gürbüzbalaban M, Bajwa WU (2026) Accelerated gradient methods for nonconvex optimization: Escape trajectories from strict saddle points and convergence to local minima. Foundations Comput. Math., ePub ahead of print April 1, https://doi.org/10.1007/s10208-026-09745-x.Crossref, Google Scholar
• [10] Du S, Jin C, Lee J, Jordan M, Singh A, Poczos B (2017) Gradient descent can take exponential time to escape saddle points. Guyon I, von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan SVN, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates Inc., Red Hook, NY), 1067–1077. Google Scholar
• [11] Dudek E, Holly K (1994) Nonlinear orthogonal projection. Ann. Polonici Math. 59(1):1–31.Crossref, Google Scholar
• [12] Ge R, Huang F, Jin C, Yuan Y (2015) Escaping from saddle points—Online stochastic gradient for tensor decomposition. Grünwald P, Hazan E, Kale S, eds. Proc. 28th Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 40 (PMLR, New York), 797–842.Google Scholar
• [13] Geshkovski B, Letrouit C, Polyanskiy Y, Rigollet P (2025) A mathematical perspective on transformers. Bull. Amer. Math. Soc. 62(3):427–479.Crossref, Google Scholar
• [14] Goudou X, Munier J (2007) The gradient and heavy ball with friction dynamical systems: The quasiconvex case. Math. Programming 116(1–2):173–191.Crossref, Google Scholar
• [15] Hencl S, Koskela P (2014) Lectures on Mappings of Finite Distortion (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• [16] Hirsch MW (1976) Differential Topology (Springer, New York).Crossref, Google Scholar
• [17] Hirsch MW, Pugh CC, Shub M (1977) Invariant Manifolds (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [18] Hou TY, Li Z, Zhang Z (2020) Analysis of asymptotic escape of strict saddle sets in manifold optimization. SIAM J. Math. Data Sci. 2(3):840–871.Crossref, Google Scholar
• [19] Hsieh YP, Jaghargh MRK, Krause A, Mertikopoulos P (2023) Riemannian stochastic optimization methods avoid strict saddle points. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates Inc., Red Hook, NY), 29580–29601.Google Scholar
• [20] Jin C, Netrapalli P, Jordan M (2018) Accelerated gradient descent escapes saddle points faster than gradient descent. Bubeck S, Perchet V, Rigollet P, eds. Proc. 31st Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 75 (PMLR, New York), 1042–1085.Google Scholar
• [21] Jin C, Ge R, Netrapalli P, Kakade S, Jordan M (2017) How to escape saddle points efficiently. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (PMLR, New York), 1724–1732.Google Scholar
• [22] Jost J (2017) Riemannian Geometry and Geometric Analysis, 7th ed. (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• [23] Krantz SG, Parks HR (2002) A Primer of Real Analytic Functions, 2nd ed. (Birkhäuser, Boston).Crossref, Google Scholar
• [24] Lee J (2012) Introduction to Smooth Manifolds, Graduate Texts in Mathematics, vol. 218, 2nd ed. (Springer-Verlag, New York).Crossref, Google Scholar
• [25] Lee J (2018) Introduction to Riemannian Manifolds. Graduate Texts in Mathematics, vol. 176, 2nd ed. (Springer, Cham, Switzerland).Google Scholar
• [26] Lee J, Simchowitz M, Jordan M, Recht B (2016) Gradient descent only converges to minimizers. Feldman V, Rakhlin A, Shamir O, eds. 29th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 49 (PMLR, New York), 1246–1257.Google Scholar
• [27] Lee J, Panageas I, Piliouras G, Simchowitz M, Jordan M, Recht B (2019) First-order methods almost always avoid strict saddle points. Math. Programming 176(1–2):311–337.Crossref, Google Scholar
• [28] Li Q, Zhu Z, Tang G (2019) Alternating minimizations converge to second-order optimal solutions. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (PMLR, New York), 3935–3943. Google Scholar
• [29] Mataigne S, Absil PA, Miolane N (2026) Bounds on the geodesic distances on the Stiefel manifold for a family of Riemannian metrics. Linear Algebra Appl. 730:1–34.Crossref, Google Scholar
• [30] Mertikopoulos P, Hallak N, Kavis A, Cevher V (2020) On the almost sure convergence of stochastic gradient descent in non-convex problems. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates Inc., Red Hook, NY), 1117–1128.Google Scholar
• [31] Milnor J (1963) Morse Theory (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [32] Nocedal J, Wright S (2006) Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. (Springer Science & Business Media, New York).Google Scholar
• [33] Panageas I, Piliouras G (2017) Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. Papadimitriou CH, ed. 8th Innovations Theoret. Comput. Sci. Conf. (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 67 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 2:1–2:12.Google Scholar
• [34] Panageas I, Piliouras G, Wang X (2019) First-order methods almost always avoid saddle points: The case of vanishing step-sizes. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32, (Curran Associates Inc., Red Hook, NY), 6474–6483.Google Scholar
• [35] Pemantle R (1990) Nonconvergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18(2):698–712. Crossref, Google Scholar
• [36] Pennec X (2018) Supplement A to “Barycentric subspace analysis on manifolds”: Hessian of the Riemannian squared distance. Ann. Statist. 46(6A):2711–2746.Google Scholar
• [37] Ponomarev SP (1987) Submersions and preimages of sets of measure zero. Siberian Math. J. 28(1):153–163.Crossref, Google Scholar
• [38] Schaeffer H, McCalla SG (2020) Extending the step-size restriction for gradient descent to avoid strict saddle points. SIAM J. Math. Data Sci. 2(4):1181–1197.Crossref, Google Scholar
• [39] Shi B, Iyengar SS (2020) Mathematical Theories of Machine Learning—Theory and Applications (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• [40] Shub M (1987) Global Stability of Dynamical Systems (Springer, New York).Crossref, Google Scholar
• [41] Sun Y, Flammarion N, Fazel M (2019) Escaping from saddle points on Riemannian manifolds. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Proc. Systems, vol. 32 (Curran Associates Inc., Red Hook, NY), 7276–7286.Google Scholar
• [42] Truong TT (2025) Some iterative algorithms on Riemannian manifolds and Banach spaces with good global convergence guarantee. Preprint submitted May 28, https://arxiv.org/abs/2505.22180.Google Scholar
• [43] Villani C (2009) Optimal Transport (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [44] Villani C (2011) Regularity of optimal transport and cut locus: From nonsmooth analysis to geometry to smooth analysis. Discrete Continuous Dynam. Systems 30(2):559–571.Crossref, Google Scholar
• [45] Zimmermann R, Stoye J (2025) High curvature means low rank: On the sectional curvature of Grassmann and Stiefel manifolds and the underlying matrix trace inequalities. SIAM J. Matrix Anal. Appl. 46(1):748–779.Crossref, Google Scholar
• [46] Zimmermann R, Stoye J (2025) The injectivity radius of the compact Stiefel manifold under the Euclidean metric. SIAM J. Matrix Anal. Appl. 46(1):298–309.Crossref, Google Scholar