Research map / Optimization / Nonconvex and smooth optimization
Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods
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.
Studies gradient methods for (L0,L1)-smooth functions, deriving new stepsizes (optimal, simplified, clipping), improved complexity for GM in nonconvex and convex cases, parameter-free NGM and Polyak-stepsize GM, and an accelerated AGMsDR method.
Problem
Gradient methods for (L0,L1)-smooth functions, whose Hessian norm is bounded by L0 + L1 times the gradient norm; existing complexity bounds are suboptimal or depend on the initial gradient norm or exponentially on L0, L1.
Approach
Derive tighter upper and lower bounds on function growth for (L0,L1)-smooth functions via exponential-type bounds, giving principled optimal stepsizes whose simplified forms coincide with clipping/normalized stepsizes; combine with AGMsDR (monotone accelerated method with small-dimensional relaxation) for faster convex rates.
Key results
- Gradient method with new stepsizes achieves O(L0 F0/eps^2 + L1 F0/eps) nonconvex complexity matching best known bounds.
- Convex GM complexity improves to O(L0 R^2/eps + L1 R ln(F0/eps)), versus prior bounds with exponential or gradient-norm dependence.
- AGMsDR achieves nu*O(sqrt(L0 R^2/eps) + ceil((L1 R)^{2/3}) ceil(ln(F0/eps))) complexity, claimed best currently available for convex (L0,L1)-smooth problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use NGM or PS-GM instead of GM with the stated stepsizes | Optimization of f(x) = (1/p)||x||^p · Numerical experiment; various p | convergence speed | Helped |
| use an initial-distance estimate closer to R for NGM | NGM on f(x) = (1/p)||x||^p · Numerical experiment; various p | convergence speed | Helped |
| use the proposed AGMsDR method instead of STM or STM-Max | Accelerated methods on f(x) = (1/p)||x||^p · Numerical experiment; smaller p | convergence speed | Helped |
| vary the (L0, L1) pair used by GM | GM with the stated stepsize rule on f(x) = (1/p)||x||^p · Numerical experiment; target accuracy epsilon | convergence speed | Mixed |
Surprising findings
- Clipping stepsizes are shown to be a convenient approximation of the optimal stepsizes derived from the upper bound on function growth.
- The gradient method on f(x)=(1/p)||x||^p performs better with NGM and PS-GM than with GM using the stepsizes from the theory.
Limitations
- AGMsDR requires a one-dimensional minimization subproblem with nu oracle queries per iteration, adding a factor nu.
- Theoretical results are for deterministic, mostly convex settings; numerical experiments are limited to a single synthetic function family.
- Whether the second term of the accelerated bound is optimal remains open.
Experimental setup
Benchmarks: f(x)=(1/p)||x||^p synthetic function logistic-type ln(1+e^x) examples
Metrics: function residual vs iterations
Baselines: clipped GM (Zhang et al. 2019) Koloskova et al. 2023 clipped GM NAG (Li et al. 2023) STM-Max (Gorbunov et al. 2024) PS-GM (Takezawa et al. 2024) STM
Builds on: AGMsDR (L0,L1)-smoothness clipped gradient method
Closest papers by meaning
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.94)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.91)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.91)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.90)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.89)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.89)
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.