Research map / Optimization / Nonconvex and smooth optimization
Toward a Unified Theory of Gradient Descent under Generalized Smoothness
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.
Derives an optimal gradient descent step size under l-generalized smoothness (Hessian norm bounded by a function of gradient norm), giving improved nonconvex and convex rates and new results for superquadratic growth.
Problem
Gradient descent analysis is mostly limited to L-smoothness or (L0,L1)-type generalized smoothness, which fails to cover functions whose Hessian grows faster than linearly in the gradient norm (e.g., -log x, exponential growth), and existing rates for generalized smoothness are loose or unavailable.
Approach
Under l-smoothness (Hessian norm <= l(gradient norm)), the upper bound from the generalized descent lemma is minimized by a step size gamma_k = integral_0^1 dv / l(||g_k|| + ||g_k|| v), a universal GD rule that recovers the L-smooth and (L0,L1) rules and extends to superquadratic growth and stochastic settings.
Key results
- Nonconvex (rho,L0,L1)-smoothness with rho<=2: rate L0*Delta/eps + L1*Delta/eps^((2-rho)/2), giving a finite L1*Delta term at rho=2 where prior work gives no guarantee.
- Convex (L0,L1)-smoothness: new rate L0 R^2/eps + min{L1 Delta^(1/2) R/eps^(1/2), L1^2 R^2, L1 M0 R^2/eps}, improving prior bounds.
- For small eps, convex GD complexity is dominated by ell(0)R^2/eps instead of ell(||grad f(x0)||)R^2/eps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed step size with ℓ(s) = 800 + 2s² instead of γ_k = 1 / (800 + 2 (2 f'(x_0))²) | GD · f(x) = -log x - log(0.1 - x) | iterations to reach f(x̄) - f(x*) ≤ 10^-5: at least 20.000 -> 75 | Helped |
| Replace ℓ(s) = 800 + 2s² with ℓ(s) = 800 + 2s (ablation) | GD with the proposed step size rule · f(x) = -log x - log(0.1 - x) | convergence | Hurt |
| Use the proposed step size with ℓ(s) = 3.3 + s instead of ℓ(s) = 3.3 + s² (ablation) | GD · f(x) = e^x + e^(1-x) | iterations to converge: at least 200 -> at most 20 | Helped |
| Use the proposed step size with ℓ(s) = 3.3 + s instead of γ_k = (3.3 + 2 |f'(x_0)|)^-1 | GD · f(x) = e^x + e^(1-x) | iterations to converge: at least 200 -> at most 20 | Helped |
Surprising findings
- The optimal step size can be obtained without explicitly computing the inverse of the q-function; final results do not depend on q^{-1}.
- GD with the step size from prior l-smoothness work fails to converge quickly on -log x - log(0.1-x), where the new rule converges in about 75 iterations.
Limitations
- Superquadratic growth results require a bounded gradients assumption.
- Stochastic results require light-tailed gradient noise; heavy tails are left open.
- Acceleration and the exponential dependence on L1 and R remain open.
Experimental setup
Metrics: iterations to epsilon-stationary point iterations to epsilon-solution
Baselines: GD with step size 1/l(||grad f(x0)||) clipped GD normalized GD Polyak step size GD l-smoothness GD (Chen et al.)
Builds on: L-smoothness descent lemma (L0,L1)-smoothness clipped gradient descent l-smoothness (Chen et al. 2023)
Closest papers by meaning
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.93)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.92)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.90)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.90)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.90)
- 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.