Research map / Optimization / Nonconvex and smooth optimization

Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity

ICLR 2025 · Optimization › Nonconvex and smooth optimization · approach: Adaptive first-order convex methods · 0 citations (OpenAlex)

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 improved convergence rates for gradient descent with smoothed clipping and Polyak stepsizes under convex (L0,L1)-smoothness without L-smoothness, proposes an accelerated (L0,L1)-STM, and gives new AdGD rates, extending GD variants to stochastic over-parameterized finite-sum settings.

Problem

Convergence of gradient-based methods for convex (and strongly convex) functions satisfying (L0,L1)-smoothness, where the gradient Lipschitz constant can be unbounded and existing bounds depend on L, exponential factors in R0, or stepsizes requiring knowledge of gradient bounds.

Approach

Shows that (L0,L1)-GD (smoothed clipping) has non-increasing gradient norm and two-phase behavior, yielding rates depending only on L0, L1, R0; applies analogous analysis to GD with Polyak stepsizes, a similar-triangles accelerated method with monotone G_k, and a refined AdGD analysis with a new potential function.

Key results

• (L0,L1)-GD achieves O(max{L0 R0^2/eps, L1^2 R0^2}) complexity for convex (L0,L1)-smooth functions without requiring L-smoothness.
• (L0,L1)-STM achieves O(sqrt(L0(1+L1R0exp(L1R0))R0^2/eps)) accelerated complexity without stepsizes depending on R0 or f(x0)-f(x*).
• Refined AdGD analysis improves the constant over prior bounds by a factor of roughly (1+L1D exp(L1D))exp(sqrt(2)L1D), e.g. ~8e6 for L1=1, D=10.

Surprising findings

• GD-PS may behave non-monotonically in function value even for L-smooth functions, as observed with PEPit, so it lacks last-iterate guarantees in the convex case.
• The accelerated (L0,L1)-STM rate is not always better than the GD rate: it can be worse when L1 and R0 are large and epsilon is not too small.

Limitations

• Accelerated (L0,L1)-STM rate is not provably better than GD-type rates for large L1R0 and moderate epsilon; optimal lower bounds remain open.
• Stochastic results only cover finite-sum problems with a common minimizer (over-parameterization) and give non-standard convergence criteria.

Experimental setup

Metrics: iteration complexity suboptimality f(x)-f(x*)

Baselines: Clip-GD GD-PS NAG AdGD SGD-PS

Builds on: (L0,L1)-smoothness Clip-GD Similar Triangles Method Adaptive Gradient Descent GD with Polyak stepsizes

Closest papers by meaning

• Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.94)
• Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.93)
• Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.92)
• 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)
• Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.91)