🤖 machine learning

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

This paper establishes that under a non-uniform smoothness assumption where curvature is an affine function of the objective value, steepest descent and adaptive methods like Adam and RMSProp achieve provably faster linear convergence rates than traditional gradient descent and other variants for problems such as logistic regression, softmax policy gradient, and specific neural networks.

Original authors: Sharan Vaswani, Yifan Sun, Reza Babanezhad

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sharan Vaswani, Yifan Sun, Reza Babanezhad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. This valley represents the "loss landscape" of a machine learning problem, and your goal is to get to the bottom (the best possible solution) as quickly as possible.

For a long time, scientists assumed this valley was like a smooth, predictable bowl. They thought that no matter where you were, the steepness of the ground was roughly the same. This made it easy to calculate the best way to walk down.

However, this paper argues that real-world machine learning valleys are much more chaotic. They aren't uniform bowls; they are jagged, uneven terrains where the steepness changes wildly depending on how high up you are. Sometimes the ground is flat, and sometimes it's a sheer cliff.

The authors of this paper introduce a new way to describe this messy terrain. They call it Non-Uniform Smoothness. Instead of saying "the ground is always this steep," they say, "the steepness of the ground is directly related to how high up you are." If you are high up, the ground might be very steep. If you are low, it might be flatter.

Here is what they discovered about how to navigate this specific type of terrain:

1. The "Sign" Strategy vs. The "Full Step" Strategy

Imagine you have two ways to walk down this hill:

Gradient Descent (GD): You look at the ground, feel the slope, and take a full step in that direction. The size of your step depends on how steep it is.
Sign Gradient Descent (Sign GD): You ignore the size of the slope and only look at the direction. You just take a small, fixed-size step in the direction the ground is going down.

The paper shows that for certain types of valleys (like those found in logistic regression or reinforcement learning), the "Sign" strategy is actually faster. Because the terrain is so uneven, taking a full step based on the slope can sometimes make you overshoot or get stuck. By just taking a steady, small step in the right direction, you cut through the chaos more efficiently. It's like navigating a rocky path: sometimes it's better to take small, steady steps than to try to leap based on how steep the rock looks.

2. The "Adaptive" Hikers (RMSProp and Adam)

You also have two other hikers: RMSProp and Adam. These are "smart" hikers who keep a memory of the terrain they've seen recently.

If they just walked over a very steep, bumpy section, they remember it and take smaller steps next time to stay safe.
If they walked over a flat section, they remember that and take bigger steps to move faster.

The paper proves that for a specific class of problems (like training certain two-layer neural networks on data that can be easily separated), these smart hikers can run at a constant, fast speed all the way to the bottom. They don't need to slow down or change their strategy as much as the other methods. They are "provably faster" than the older, less adaptive methods like AdaGrad or AMSGrad, which tend to slow down too much as they get closer to the bottom.

3. The "Lower Bound" (Why the others are slower)

To prove their point, the authors set up a specific, simple test case: a one-dimensional logistic loss (a very basic math problem). They showed that for this specific terrain:

Gradient Descent, Heavy-Ball Momentum, AdaGrad, and AMSGrad are mathematically forced to move very slowly. Their speed drops off significantly as they get closer to the goal.
RMSProp and Adam, however, maintain a fast, linear speed.

Think of it like a race where the other runners are tied to a rope that gets tighter and tighter as they approach the finish line, forcing them to slow down. RMSProp and Adam, however, have a special mechanism that lets them keep sprinting at full speed right up to the finish line.

Summary of the "Big Wins"

New Map: They created a better map (the (H0, H1)-NS assumption) that describes how the steepness of the ground relates to your height. This map fits many real-world machine learning problems better than the old maps.
Faster Hikers: They proved that "Sign GD" and the smart adaptive methods (RMSProp/Adam) are the best tools for this specific type of map.
The Verdict: For problems like separating data with logistic regression or training simple neural networks, the adaptive methods (RMSProp/Adam) are theoretically guaranteed to be faster than the traditional methods (GD, AdaGrad).

In short, the paper explains why the adaptive algorithms we use in AI today work so well: they are perfectly suited for the specific, uneven, "non-uniform" shape of the valleys we are trying to climb down.

Technical Summary: Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

Problem Formulation

This paper addresses the convergence analysis of first-order optimization methods for unconstrained minimization problems of the form $\min_{\theta \in \mathbb{R}^D} f(\theta)$ . The authors focus on a specific class of objectives characterized by Non-Uniform Smoothness (NS) and Gradient Domination (also known as the Łojasiewicz condition).

The core assumption, termed $(H_0, H_1)$ -NS, posits that the spectral norm of the Hessian is upper-bounded by an affine function of the objective value:
$\|\nabla^2 f(\theta)\|_{p \to q} \leq H_0 + H_1 f(\theta)$
where $H_0, H_1 \geq 0$ and $p, q \geq 1$ are dual norms. This assumption generalizes previous NS assumptions (e.g., Zhang et al., 2020b) which bounded the Hessian by the gradient norm. The authors argue that $(H_0, H_1)$ -NS better models loss landscapes in machine learning, including logistic regression, generalized linear models, softmax policy gradients, and certain two-layer neural networks.

Additionally, the analysis assumes the objective satisfies a Non-uniform Łojasiewicz (NL) condition, which lower-bounds the gradient norm in terms of the function sub-optimality:
$\|\nabla f(\theta)\|_q \geq \mu(\theta) [f(\theta) - f^*]^\tau$
This condition implies that minimizing the gradient norm leads to minimizing the function value, a property satisfied by many convex and structured non-convex problems.

Methodology

The paper derives convergence guarantees for three classes of algorithms under the $(H_0, H_1)$ -NS and NL assumptions:

Normalized Steepest Descent (NSD): Including Sign Gradient Descent (Sign GD), Normalized Gradient Descent, and Sign Coordinate Descent with the Gauss-Southwell rule.
Deterministic, Diagonal RMSProp: Analyzed without bias correction.
Deterministic, Diagonal Adam: Analyzed without bias correction, specifically under the condition $\beta_1 \leq \beta_2$ .

The methodology relies on establishing structural properties of $(H_0, H_1)$ -NS functions, such as multiplicative Lipschitz bounds for the function and gradient norms. These properties allow the authors to bound the descent of the objective function without requiring dimension-dependent constants or global convexity. The proofs utilize a two-phase analysis:

Phase 1: When the sub-optimality is large (specifically $f(\theta) > H_0/H_1$ ), the $H_1 f(\theta)$ term dominates, allowing for linear convergence with constant step sizes.
Phase 2: When the sub-optimality is small ( $f(\theta) \leq H_0/H_1$ ), the $H_0$ term dominates, requiring smaller step sizes and resulting in slower, sub-linear convergence rates dependent on the Łojasiewicz exponent $\tau$ .

Key Contributions

1. Structural Properties of $(H_0, H_1)$ -NS Functions
The authors generalize existing results beyond Euclidean norms to arbitrary $(p, q)$ operator norms. They prove that $(H_0, H_1)$ -NS implies multiplicative Lipschitz bounds for both the function and gradient norms. This framework enables the analysis of RMSProp and Adam without assuming bounded gradients or convexity.

2. Convergence of Normalized Steepest Descent (NSD)
The paper establishes that NSD methods (including Sign GD and Sign CD-GS) achieve dimension-free convergence rates.

For problems where $H_0 = 0$ (e.g., separable logistic regression, exponential loss), NSD converges linearly with a constant step size.
For problems where $H_0 > 0$ , NSD converges linearly to an $O(H_0/H_1)$ neighborhood, followed by a slower phase.
Significance: For separable logistic regression and softmax policy gradients, Sign GD is proven to converge linearly with a constant step size, matching the performance of GD with line-search and outperforming constant-step-size GD.

3. Convergence of RMSProp and Adam
The authors derive the first dimension-free linear convergence rates for deterministic, diagonal variants of RMSProp and Adam under these assumptions.

Results: For a class of two-layer neural networks on separable data, RMSProp and Adam converge at a linear rate with constant step sizes and momentum parameters.
Novelty: Unlike prior works that often require convexity or bounded gradients, these results hold for non-convex objectives satisfying the specific NS and NL conditions.

4. Separation of Adaptive Methods
The paper presents a theoretical lower bound demonstrating that, under the $(H_0, H_1)$ -NS assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, Gradient Descent (GD), and Heavy-Ball momentum.

Example: For the one-dimensional logistic loss, the authors prove that GD, Heavy-Ball, AdaGrad, and AMSGrad suffer from a sub-linear $\Omega(1/T)$ lower bound.
Contrast: In the same setting, RMSProp and Adam achieve an exponential (linear) convergence rate. This provides a theoretical justification for the practical dominance of RMSProp and Adam over AdaGrad and AMSGrad in specific machine learning tasks.

Results and Implications

The paper's theoretical results apply to several canonical machine learning problems:

Logistic Regression on Separable Data: Sign GD and Sign CD-GS achieve linear convergence with constant step sizes. RMSProp and Adam also achieve linear convergence, whereas GD is provably slower.
Softmax Policy Gradient: NSD methods achieve linear convergence rates matching specialized algorithms designed for this problem.
Two-Layer Neural Networks: For networks with specific activation functions and separable data, RMSProp and Adam converge linearly with constant hyperparameters.

Significance

The paper claims to provide the first convergence guarantees for RMSProp and Adam under $(H_0, H_1)$ -NS assumptions that are dimension-free and do not rely on convexity or bounded gradients. By identifying a natural class of functions where adaptive methods (RMSProp, Adam) strictly outperform non-adaptive methods (GD, Heavy-Ball) and other adaptive variants (AdaGrad, AMSGrad), the work offers a theoretical foundation for the empirical success of these optimizers in deep learning. The authors suggest these techniques can be extended to other methods like momentum-based steepest descent and Lion, and plan to generalize the results to stochastic settings in future work.