# Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation

arXiv: https://arxiv.org/abs/2508.16540 · HTML: https://mlsanity.com/paper/2508.16540/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 22 Aug 2025.

## Builds on (most cited first, 12 of 12)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Dimer-Enhanced Optimization: A First-Order Approach to Escaping Saddle Points in Neural Network Training](https://mlsanity.com/paper/2507.19968/) (2025)
- [Escaping From Saddle Points Using Asynchronous Coordinate Gradient Descent](https://mlsanity.com/paper/2211.09908/) (2022)
- [Randomized coordinate gradient descent almost surely escapes strict saddle points](https://mlsanity.com/paper/2508.07535/) (2025)

## Abstract (arXiv)

We present a comprehensive theoretical analysis of first-order methods for escaping strict saddle points in smooth non-convex optimization. Our main contribution is a Perturbed Saddle-escape Descent (PSD) algorithm with fully explicit constants and a rigorous separation between gradient-descent and saddle-escape phases. For a function f:ℝd→ℝ with ℓ-Lipschitz gradient and ρ-Lipschitz Hessian, we prove that PSD finds an (ε,√ρε)-approximate second-order stationary point with high probability using at most O(ℓDeltaf/ε2) gradient evaluations for the descent phase plus O((ℓ/√ρε)log(d/δ)) evaluations per escape episode, with at most O(ℓDeltaf/ε2) episodes needed. We validate our theoretical predictions through extensive experiments across both synthetic functions and practical machine learning tasks, confirming the logarithmic dimension dependence and the predicted per-episode function decrease. We also provide complete algorithmic specifications including a finite-difference variant (PSD-Probe) and a stochastic extension (PSGD) with robust mini-batch sizing.