Research map / Optimization / Nonconvex and smooth optimization
Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops a decrease-procedure framework showing first-order methods (GD, adaptive GD, SGD, Perturbed GD, Restarted SGD) find FOSPs and SOSPs under second- and third-order self-bounding regularity (generalized smoothness) with non-asymptotic rates.
Problem
Finding first- and second-order stationary points with first-order methods for non-convex functions whose gradient and Hessian are not globally Lipschitz (generalized smoothness, e.g. (L0,L1)-smoothness).
Approach
Replaces global smoothness with self-bounding assumptions where the Hessian (and third derivative) norm is bounded by a function of the function value; shows that standard algorithms decrease F locally within the initial sublevel set and chains these decreases via a general decrease-procedure framework, with step sizes depending only on F(w0).
Key results
- Perturbed GD finds an (ε, √ε)-SOSP within O(ε^-2 log^4(d/(εδ))) gradient oracle calls under third-order self-bounding regularity.
- Restarted SGD finds an SOSP with T = Õ(ε^-3.5) stochastic gradient calls under third-order self-bounding regularity and gradient-oracle assumptions.
- GD, adaptive GD and SGD find FOSPs under self-bounding regularity with rates matching the smooth setting (e.g. GD T=O(F(w0)L1/ε^2)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gradient Descent under second-order self-bounding regularity | Gradient Descent · FOSP | oracle calls: T=\frac{2 F(\pmb{w}_0) L_1(\pmb{w}_0)}{\varepsilon^2} | Helped |
| Use an adaptive step size | Adaptive GD · FOSP | oracle calls: T=\frac{2 F(\pmb{w}_0)}{\min\crl*{\frac{L_1'(\pmb{w}_0)}{\rho_0(F(\pmb{w}_0)+1)^2}, \frac{\varepsilon^2}{L'_1(\pmb{w}_0) | Helped |
| Use SGD with a fixed step size under the stated stochastic-gradient assumptions | SGD · FOSP | oracle calls: T=\tilde{O}\prn*{\frac{1}{\varepsilon^4} \cdot \polylog(1/\varepsilon, 1/\delta)} | Helped |
| Use Perturbed GD under third-order self-bounding regularity | Perturbed GD · SOSP | oracle calls: T=O\prn*{\frac{1}{\varepsilon^2} \log^4\prn*{\frac{d}{\varepsilon \delta}}} | Helped |
| Use Restarted SGD under third-order self-bounding regularity and the stated oracle assumptions | Restarted SGD · SOSP | oracle calls: T=\tilde{O}\prn*{\frac1{\varepsilon^{3.5}}} | Helped |
Surprising findings
- Under generalized smoothness, a larger initial loss F(w0) forces smaller working step sizes, so practitioners should tune step size based on initial suboptimality.
Limitations
- Results are for non-adaptive step sizes that depend on F(w0) through upper bounds on rho functions, which are not necessarily known in practice.
- Simulations are limited to simple functions F(w)=||Aw||^p.
Experimental setup
Metrics: oracle complexity gradient norm function value decrease
Baselines: Cubic regularization Trust region methods Perturbed GD (smooth setting)
Builds on: Perturbed gradient descent Restarted SGD (L0,L1)-smoothness Cubic regularization
Closest papers by meaning
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.93)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.91)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.91)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.91)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.91)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.90)
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.