Research map / Optimization / Nonconvex and smooth optimization
Gradient Descent Can Take Exponential Time to Escape Saddle Points
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add episodic random perturbations to gradient descent | Gradient descent · Constructed smooth function with uniform initialization on [-1, 1]^d | iterations to reach a local minimum: e^{\Omega(d)} versus polynomial time | Helped |
| Add episodic random perturbations to gradient descent | Gradient descent · Constructed counter-example | iterations to escape successive saddle points: \left(\frac{L+\gamma}{\gamma}\right)^d versus polynomial time | Helped |
| Increase the ratio \frac{L+\gamma}{\gamma} | Gradient descent on the constructed counter-example · Constructed counter-example, d=5 and d=10 | iterations to escape a saddle point: \frac{L+\gamma}{\gamma} | Hurt |
| Increase the ratio \frac{L+\gamma}{\gamma} | Perturbed gradient descent on the constructed counter-example · Constructed counter-example, d=5 and d=10 | iterations to escape a saddle point | No clear effect |
Closest papers by meaning
- Faster Gradient-Free Methods for Escaping Saddle Points (ICLR 2023 · similarity 0.92)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.87)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.87)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.86)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.86)
- On the Unstable Convergence Regime of Gradient Descent (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.