Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911116998737920 |
|---|---|
| author | Alpay, Faruk Alakkad, Hamdi |
| author_facet | Alpay, Faruk Alakkad, Hamdi |
| contents | 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:\mathbb{R}^d\to\mathbb{R}$ with $\ell$-Lipschitz gradient and $ρ$-Lipschitz Hessian, we prove that PSD finds an $(ε,\sqrt{ρε})$-approximate second-order stationary point with high probability using at most $O(\ellΔ_f/ε^2)$ gradient evaluations for the descent phase plus $O((\ell/\sqrt{ρε})\log(d/δ))$ evaluations per escape episode, with at most $O(\ellΔ_f/ε^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16540 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation Alpay, Faruk Alakkad, Hamdi Machine Learning Optimization and Control 90C26, 90C30, 68T05, 65K05 G.1.6; F.2.1; I.2.6 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:\mathbb{R}^d\to\mathbb{R}$ with $\ell$-Lipschitz gradient and $ρ$-Lipschitz Hessian, we prove that PSD finds an $(ε,\sqrt{ρε})$-approximate second-order stationary point with high probability using at most $O(\ellΔ_f/ε^2)$ gradient evaluations for the descent phase plus $O((\ell/\sqrt{ρε})\log(d/δ))$ evaluations per escape episode, with at most $O(\ellΔ_f/ε^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. |
| title | Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation |
| topic | Machine Learning Optimization and Control 90C26, 90C30, 68T05, 65K05 G.1.6; F.2.1; I.2.6 |
| url | https://arxiv.org/abs/2508.16540 |