Research map / Optimization / Nonconvex and smooth optimization
Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
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.
Introduces a polynomial-growth sufficient condition that implies both (L0,L1)-smoothness and anisotropic smoothness, and proves that nonlinearly preconditioned (including clipped) gradient descent avoids strict saddle points and that a perturbed variant reaches second-order stationarity with logarithmic dimension dependence.
Problem
Gradient-based methods on nonconvex functions whose smoothness is only generalized (not Lipschitz): it is unclear when (L0,L1)-smoothness and anisotropic smoothness hold in practice, and whether nonlinearly preconditioned/clipped gradient descent still avoids saddle points.
Approach
A polynomial growth condition (Hessian Frobenius norm bounded by a polynomial of degree R, gradient norm bounded below by a polynomial of degree R+1) is shown to imply (L0,L1)-smoothness and the second-order characterization of anisotropic smoothness for isotropic reference functions, which are then used to extend stable-center manifold saddle avoidance and perturbed-GD complexity to nonlinearly p
Key results
- Proves that under the second-order characterization of anisotropic smoothness, nonlinearly preconditioned GD with gamma < 1/L avoids strict saddle points with probability one, extended to hard gradient clipping via a nonsmooth stable-center manifold theorem.
- Shows phase retrieval, symmetric and asymmetric matrix factorization, and Burer-Monteiro MaxCut augmented Lagrangians satisfy the proposed polynomial growth condition and hence (L0,L1)-smoothness and anisotropic smoothness.
- Perturbed preconditioned GD reaches an epsilon-second-order stationary point in about O~(L(f(x0)-inf f)/(Lbar eps^2)) iterations with logarithmic dependence on dimension; numerically it matches perturbed GD on the octopus function.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use nonlinear preconditioning with φ(x) = cosh(∥x∥) − 1 instead of vanilla gradient descent | symmetric matrix factorization · symmetric matrix factorization, n = 2 and r = 1 | iterations to convergence | Helped |
| use larger stepsizes enabled by nonlinear preconditioning | symmetric matrix factorization · symmetric matrix factorization, n = 2 and r = 1 | maximum stable stepsize | Helped |
| use perturbed preconditioned gradient descent instead of vanilla gradient descent | octopus objective · octopus function, n ∈ {5, 10} and L ∈ {1, 1.5, 2, 3} | saddle escape performance | Helped |
| use perturbed preconditioned gradient descent instead of perturbed vanilla gradient descent | octopus objective · octopus function, n ∈ {5, 10} and L ∈ {1, 1.5, 2, 3} | saddle escape performance | No clear effect |
| apply the proposed sufficient condition for generalized smoothness | phase retrieval, symmetric and asymmetric matrix factorization, and Burer-Monteiro MaxCut-type factorizations · the listed nonconvex optimization problems | generalized smoothness guarantee | Helped |
| use nonlinear preconditioning under the second-order characterization of anisotropic smoothness | preconditioned gradient method · strict saddle points | probability of convergence to a strict saddle | Helped |
| use hard gradient clipping under the stated measure-one condition | preconditioned gradient method · strict saddle points | probability of convergence to a strict saddle | Helped |
| add perturbations to the preconditioned gradient method | perturbed preconditioned gradient method · anisotropically smooth objectives | iterations to reach an ε-second-order stationary point: T = 8 max { ... } = Õ ( L (f(x⁰) − inf f) / (L̄ ε²) ) | Helped |
Surprising findings
- Multivariate polynomials can fail (L0,L1)-smoothness even though their gradient norm grows unboundedly, e.g. f(x,y)=x^4/4+y^4/4-x^2y^2/2 along y=-x.
- The asymmetric matrix factorization without regularization (kappa=0) fails the growth condition because gradient norm can stay zero as the norm of the variable diverges.
Limitations
- Lipschitz continuity of the Hessian-like map H_lambda is assumed, which is stronger than the main sufficient condition.
- Hard gradient clipping analysis requires the extra assumption that the set where the gradient norm equals Lbar has measure zero.
- Verification of the polynomial growth condition is limited to specific applications and univariate polynomials; no general characterization for multivariate settings.
Experimental setup
Metrics: iterations to escape saddle points stepsize tolerance
Baselines: gradient descent perturbed gradient descent
Builds on: (L0,L1)-smoothness anisotropic smoothness (Laude et al.) stable-center manifold theorem perturbed gradient descent (Jin et al.)
Closest papers by meaning
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.93)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.92)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.91)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.89)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.88)
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.