Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

2026/08/04 by Junwen Qiu, Bohao Ma, Andre Milzarek +1
Computer Science · Mathematics · #cs.LG #math.DS #math.OC #msc:37C60 #msc:37D10 #msc:90C06 #msc:90C26 #stat.ML

paper · pdf

39 pages

arxiv created 2026/08/06 · arxiv updated 2026/08/07

Abstract

Unit excitation (UE) is a common assumption in stochastic saddle avoidance: the stochastic error must have a uniformly positive component along every direction, in expectation. This condition gives a direct way to rule out convergence to strict saddles, but it also oversimplifies the actual noise structure, and does not match many stochastic optimization regimes. In overparameterized or interpolation models, the noise may vanish near stationarity. In finite-sum problems, the stochastic gradient noise may lie in a low-dimensional, data-dependent subspace. In these (common) scenarios, UE is naturally not satisfied. In this paper, we prove an abstract almost sure avoidance theorem for stochastic recursions without UE. The theorem replaces UE-type requirements by verifiable pathwise conditions. In applications, these conditions follow, e.g., from local smoothness and finite-moment assumptions under standard i.i.d. sampling, or from the finite-sum structure under without-replacement sampling. Since the stochastically sampled maps generally do not share a fixed point, the celebrated center-stable manifold argument used in deterministic analyses is not directly applicable. Instead, we use a path-dependent change of variables together with a pathwise Lyapunov--Perron-based proof strategy. As applications, we obtain strict saddle avoidance for stochastic mirror descent (including SGD) and for random reshuffling. For nonsmooth composite objectives, we prove avoidance results for a proximal-type stochastic gradient method. Combining these insights with suitable iterate convergence guarantees, this allows establishing convergence to local minimizers of the original objective function.

Citations

• Proximal random reshuffling under local Lipschitz continuity
• Random Reshuffling with Momentum: Complexity Bounds and Last-iterate Convergence
• On the Trajectories of SGD Without Replacement
• A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization
• High Probability Guarantees for Random Reshuffling
• Variational Properties of Decomposable Functions. Part I: Strict Epi-Calculus and Applications
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties
• Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption
• On the local convergence of the semismooth Newton method for composite optimization
• A Unified Convergence Theorem for Stochastic Optimization Methods
• Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality
• Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
• Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions
• A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Random Reshuffling: Simple Analysis with Vast Improvements
• Closing the convergence gap of SGD without replacement
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• How Good is SGD with Random Shuffling?
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems
• How to Escape Saddle Points Efficiently
• Relatively-Smooth Convex Optimization by First-Order Methods, and Applications
• Optimization Methods for Large-Scale Machine Learning
• Global Optimality of Local Search for Low Rank Matrix Recovery
• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• When Are Nonconvex Problems Not Scary?
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods
• Optimality, identifiability, and sensitivity
• Self-concordant analysis for logistic regression
• Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• A Stochastic Approximation Method