Near-Optimal Methods for Generalized Lipschitz Convex Optimization

Dmitry Kovalev, Grigory MalinovskyarXiv 2026 · arXiv

TL;DR

This paper establishes the fundamental theoretical limits for solving convex optimization problems where the gradient's magnitude grows relative to the objective value (a property called "generalized Lipschitzness"). The authors prove a new lower complexity bound and introduce two near-optimal algorithms—a specialized Gradient Descent and a simplified clipped AdamW—that match this bound while providing theoretical justification for common practices like learning rate warm-up and gradient clipping.

What Problem Does This Paper Address?

In classical optimization theory, we often assume a function is Lipschitz continuous, meaning its gradients never exceed a fixed constant. However, many modern machine learning models don't play by these rules; gradients can explode as we move away from the optimum.

To bridge this gap, researchers use the Generalized Lipschitz assumption. Here, the bound on the gradient's norm is not a constant but a function of the current objective gap (how far we are from the minimum). While previous work has explored specific instances of this (like $(L_0, L_1)$-smoothness), a unified theory was missing. This paper asks:

  1. What is the absolute minimum number of iterations any first-order method needs to solve these problems?
  2. Can we design algorithms that reach this theoretical "speed limit"?

Methods

The authors approach the problem from two angles:

1. Establishing the "Speed Limit" (Lower Bounds)

The authors construct a "hard instance"—a specific mathematical function that is particularly difficult to optimize. By analyzing how any algorithm restricted to the "linear span" of previous gradients performs on this function, they derive a lower bound on the number of iterations $K$ required to reach a target accuracy $\epsilon$.

2. Designing Near-Optimal Algorithms

  • For Deterministic Settings: They propose a Projected Gradient Descent (GD) with a sophisticated recursive stepsize schedule. Unlike standard GD, which often uses a constant or simple decaying stepsize, this schedule incorporates both warm-up (increasing steps) and decay phases.
  • For Stochastic Settings: They introduce a Scalar-stepsize Clipped AdamW. This is a simplified version of the popular AdamW optimizer. Instead of adapting the learning rate for every single coordinate, it uses a single scalar stepsize and a global clipping mechanism based on moving averages of the gradient and its square.

Datasets

Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs and algorithmic complexity analysis. No empirical experiments on specific datasets were conducted.

Key Insights and Ideas

  • Theoretical Support for Warm-up: One of the most striking "aha moments" is that the near-optimal deterministic algorithm requires a stepsize schedule with a warm-up phase. This provides a rigorous mathematical justification for why learning rate warm-up is so effective in training large-scale models like Transformers.
  • The Universality of Assumption (A1): The authors show that their "Generalized Lipschitz" assumption is a powerful umbrella. It covers several existing, more restrictive assumptions, meaning their near-optimal bounds apply to a very wide class of optimization problems.
  • Clipping is Essential: In the stochastic setting, the authors show that clipping isn't just a heuristic to prevent "exploding gradients"—it is a mathematically necessary component to achieve near-optimal convergence when gradients are not globally bounded.
  • AdamW's Efficiency: The paper demonstrates that a simplified version of AdamW is theoretically "near-optimal" for stochastic convex problems, matching the lower bound up to logarithmic factors.

Key Results

  • The Lower Bound: The authors prove that any first-order method requires at least $K = \Omega\left(\left[\frac{R \ell(\epsilon^2)}{\epsilon}\right]^2\right)$ iterations (ignoring log factors), where $R$ is the distance to the start and $\ell$ describes the gradient growth.
  • Matching Upper Bounds: Both the proposed scheduled GD (deterministic) and the clipped AdamW (stochastic) achieve an iteration complexity of $\tilde{O}\left(\left[\frac{R \ell(\epsilon^2)}{\epsilon}\right]^2\right)$.
  • Stochastic Robustness: The clipped AdamW algorithm achieves these bounds using only two parameters ($\alpha$ and $R$), making it significantly easier to implement than the complex recursive schedule required for the deterministic version.

Limitations and Future Work

  • Convexity Constraint: The entire analysis assumes the objective function is convex. While this is standard for establishing fundamental bounds, most modern deep learning problems are non-convex. Extending these near-optimal guarantees to non-convex landscapes remains a major open challenge.
  • Linear Span Assumption: The lower bound is proven for algorithms that generate new points within the span of previous gradients. While most practical algorithms fit this description, some "randomized" or "second-order" methods do not, leaving a small gap in the theory.
  • Parameter Sensitivity: The deterministic stepsize schedule is mathematically elegant but relies on knowing certain properties of the function (like the growth rate $\ell$) which might be difficult to estimate accurately in real-world applications.

Summary updated

Abstract

In this paper, we consider a convex optimization problem, where the upper bound on the subgradient norm depends on the objective function. We establish a lower bound on the number of iterations required by any first-order method to find an approximate solution to the problem. Furthermore, we present two near-optimal algorithms that can match the lower bound up to logarithmic factors. The first algorithm is a projected GD with a carefully designed stepsize schedule which incorporates warm-up and decay phases. The second algorithm is scalar-stepsize clipped AdamW which extends the near-optimal guarantees to the stochastic setting, where only a noisy unbiased estimator of the subgradient is available.
BibTeX
@misc{kovalev2026near,
  author = {Dmitry Kovalev and Grigory Malinovsky},
  title = {{Near-Optimal Methods for Generalized Lipschitz Convex Optimization}},
  year = {2026},
  eprint = {2611.20318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20318},
}
Figure