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

Faruk Alpay, Hamdi Alakkad · 2025

Read Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation by Faruk Alpay, Hamdi Alakkad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16540.txt.

Introduction

Faruk Alpay and Hamdi Alakkad tackle a known weak point of training methods in a 2025 paper on optimization. Gradient descent can stall at saddle points, spots that slope down in some directions and up in others. The pair present an algorithm called Perturbed Saddle-escape Descent, which adds a nudge sized to the local curvature when progress stalls. All constants in their bounds are written out in full, with no hidden terms.

The paper proves how many gradient steps the method needs to reach a near-stationary point, split into a descent phase and an escape phase. Tests on synthetic tasks and real machine learning jobs match the predicted pattern, including the slow growth of cost with dimension. Two variants cover cases where gradients must be probed or sampled in small batches.

Catalog record

CREATORFaruk Alpay, Hamdi Alakkad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-16540

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation Faruk Alpay, Hamdi Alakkad Abstract 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 → ℝ f:\mathbb{R}^{d}\to\mathbb{R} with ℓ \ell -Lipschitz gradient and ρ \rho -Lipschitz Hessian, we prove that PSD finds an ( ϵ , ρ ​ ϵ ) (\epsilon,\sqrt{\rho\epsilon}) -approximate second-order stationary point with high probability using at most O ⁡ ( ℓ ​ Δ f / ϵ 2 ) O(\ell\Delta_{f}/\epsilon^{2}) gradient evaluations for the descent phase plus O ⁡ ( ( ℓ / ρ ​ ϵ ) ​ log ⁡ ( d / δ ) ) O((\ell/\sqrt{\rho\epsilon})\log(d/\delta)) evaluations per escape episode, with at most O ⁡ ( ℓ ​ Δ f / ϵ 2 ) O(\ell\Delta_{f}/\epsilon^{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. All code and experimental details are available at: https://github.com/farukalpay/PSD/ . 1 Introduction Non-convex optimization problems pervade machine learning, from neural network training to matrix factorization and tensor decomposition. A fundamental challenge in these problems is the presence of saddle points—stationary points where the Hessian has negative eigenvalues. While gradient descent can efficiently decrease the function value when the gradient is large, it can stagnate near saddle points where the gradient is small but the Hessian indicates negative curvature [ 11 , 9 ] . Recent theoretical advances have shown that simple modifications to gradient descent, particularly the addition of occasional random perturbations, suffice to escape strict saddle points efficiently. However, existing analyses often hide important constants in \tilde{O}(\cdot) notation, making it difficult to understand the actual computational requirements or to verify theoretical predictions empirically. 1.1 Our Contributions • Explicit constant analysis: We provide a complete analysis of perturbed gradient descent with all constants instantiated, showing exactly how the episode length scales as T=8(\ell/\sqrt{\rho\epsilon})\log(16dM/\delta) where M bounds the number of episodes. • Decomposed complexity bound: We separate the iteration complexity into gradient-descent steps and escape episodes, making the dimension dependence transparent: only the per-episode cost depends logarithmically on d . • Complete algorithmic specifications: We provide detailed pseudocode for three variants: basic PSD, finite-difference PSD-Probe, and stochastic PSGD, with all parameters derived from theory. • Comprehensive empirical validation: Through experiments on multiple test functions across dimensions 10–1000 and real-world machine learning tasks, we confirm the predicted \log d scaling, the per-episode function decrease of \Omega(\epsilon^{2}/\ell) , and the superiority over vanilla gradient descent. • Failure mode analysis: We characterize when the method fails (degenerate saddles, unknown parameters, extreme noise) and provide concrete mitigations. • Reproducibility: We provide complete implementation details, code, and hyperparameter settings to ensure full reproducibility. 1.2 Related Work Gradient flow perspective. Lee et al. 2016 showed that gradient flow almost surely avoids strict saddles, as the stable manifold has measure zero, offering intuition but not finite-time guarantees. Perturbed gradient methods. Ge et al. 2015 introduced perturbed gradient descent for online settings; Jin et al. 2017 refined the analysis for the offline case, achieving \tilde{O}(\epsilon^{-2}) iteration complexity with hidden constants. Our work extends this line of research by providing explicit constants and a clean separation of the complexity components. Second-order and accelerated methods. Cubic-regularized Newton achieves O(\epsilon^{-3/2}) iterations but requires Hessians [ 12 ] ; acceleration-based methods such as NEON2 and the Carmon–Duchi–Hinder–Sidford framework provide alternative routes [ 1 , 3 ] . Distributed and quantised optimisation. Recent work in distributed optimisation has explored the role of communication-induced quantisation in escaping saddle points. In particular, Bo and Wang [ 16 ] propose a stochastic quantisation scheme that leverages rounding errors in networked systems to avoid saddle points. Their analysis shows that quantisation can be exploited to ensure convergence to second-order stationary points in distributed nonconvex optimisation, with empirical validation on benchmark tasks. Complementing this line of work, Chen et al. [ 17 ] present a communication-compressed stochastic gradient method for heterogeneous federated learning. Their PowerEF–SGD algorithm provably escapes saddle points and achieves convergence to second-order stationary points with a linear speed-up in the number of workers and subquadratic dependence on the spectral gap. Escaping saddles in neural network training. While the classical results on gradient flow and perturbations apply to generic non-convex problems, recent studies have specialised to neural network training. Cheridito et al. [ 18 ] analyse the dynamics of gradient descent in shallow ReLU networks and prove that gradient descent almost surely circumvents saddle points and converges to global minimisers under mild initialisation conditions. Their analysis draws on dynamical systems tools and shows that gradient descent avoids the measure-zero set of saddles without requiring perturbations. High-dimensional non-convex landscapes. Katende and Kasumba [ 19 ] survey contemporary techniques for escaping local minima and saddle points in high-dimensional settings. They emphasise strategies such as stochastic gradient perturbations, Hessian-spectrum analysis and subspace optimisation, and highlight the role of adaptive learning rates in enhancing robustness to saddle points. Their work synthesises insights across optimisation and dynamical systems to provide practical guidelines. Randomised coordinate descent. Most analyses of saddle-escape algorithms focus on full-gradient methods. Chen, Li and Li [ 20 ] take a random dynamical systems perspective on randomised coordinate gradient descent and prove that, under standard smoothness assumptions, this simple method almost surely escapes strict saddles. Their proof uses a centre–stable manifold theorem to show that the set of initial conditions leading to saddles has measure zero. Asynchronous and privacy-aware escapes. Bornstein et al. [ 21 ] propose an asynchronous coordinate-gradient descent algorithm equipped with a kinetic energy term and perturbation subroutine. Their method circumvents the convergence slowdown caused by parallelisation delays and provably steers iterates away from saddle points while achieving polylogarithmic dimension dependence. On the privacy front, Tao et al. [ 22 ] develop a perturbed stochastic gradient framework that injects Gaussian noise and monitors model drift to locate approximate second-order stationary points under differential privacy. They provide the first formal guarantees for distributed, heterogeneous data settings. Physics-inspired and bilevel methods. Hu, Cao and Liu [ 23 ] adapt the Dimer method from molecular dynamics to design a first-order optimizer that approximates the Hessian’s smallest eigenvector using only gradient evaluations. By periodically projecting gradients away from low-curvature directions, their dimer-enhanced optimiser accelerates neural-network training and avoids saddle points. In bilevel optimisation, Huang et al. [ 24 ] analyse perturbed approximate implicit differentiation (AID) and propose iNEON, a first-order algorithm that escapes saddle points and finds local minima in nonconvex–strongly-convex bilevel problems, offering nonasymptotic convergence guarantees. Zeroth-order escapes. Ren, Tang and Li [ 25 ] investigate zeroth-order optimisation and show that two-point estimators augmented with isotropic perturbations can escape strict saddle points efficiently. Their analysis demonstrates that a gradient-free algorithm using a small number of function evaluations per iteration finds second-order stationary points in polynomial time. 2 Mathematical Framework 2.1 Notation Let f:\mathbb{R}^{d}\to\mathbb{R} be a twice continuously

Read the complete text