Research map / Optimization / Nonconvex and smooth optimization
How to Escape Saddle Points Efficiently
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 phased random perturbations when the gradient is small | Gradient descent · General non-convex optimization | iterations to an ε-second-order stationary point: O(\text{polylog}(d)/\epsilon^2) versus O(d^3\cdot\text{poly}(1/\epsilon)) | Helped |
| Use PGD under a robust strict-saddle assumption | Perturbed Gradient Descent (PGD) · Functions satisfying the strict-saddle property | convergence to a neighborhood of a local minimum: O\left(\frac{\ell(f(\vect{x}_0) - f^\star)}{\tilde{\epsilon}^2}\log^{4}\left(\frac{d\ell\Delta_f}{\tilde{\epsilon}^2\del | Helped |
| Add a local gradient-descent phase using step size 1/β | PGD after reaching a local-minimum neighborhood · Functions with local strong convexity or regularity | iterations for local convergence: \frac{\beta}{\alpha}\log \frac{\zeta}{\epsilon} | Helped |
| Use PGDli for symmetric low-rank matrix factorization | Symmetric low-rank matrix factorization · Matrix factorization | iterations to an ε-close point in the global-minimum set: O\left(r(\kappa^\star)^4\log^{4}(d\kappa^\star /\delta) + \kappa^\star \log(\sigma^\star_r/\epsilon) \right) | Helped |
Closest papers by meaning
- Faster Gradient-Free Methods for Escaping Saddle Points (ICLR 2023 · similarity 0.93)
- Gradient Descent Can Take Exponential Time to Escape Saddle Points (NeurIPS 2017 · similarity 0.92)
- Escape saddle points by a simple gradient-descent based algorithm (NeurIPS 2021 · similarity 0.92)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.89)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.88)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.87)
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.