🤖 machine learning

Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothness

This paper establishes convergence guarantees for gradient descent on general feedforward neural networks of arbitrary depth and width by introducing a novel generalized Lipschitz smoothness condition that relies solely on standard properties of common activation functions and the loss, proving that the minimum squared gradient norm converges to zero at a rate of $O(1/T^{1/L})$ without requiring special initialization or dataset assumptions.

Original authors: Siqiao Mu, Diego Klabjan

Published 2026-08-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Siqiao Mu, Diego Klabjan

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 teach a robot how to recognize a cat in a photo. You don't program the robot with a list of rules; instead, you let it learn by trial and error. You show it a picture, it guesses "dog," you say "wrong," and it tweaks its internal settings slightly to do better next time. This process of tweaking is called gradient descent. Think of the robot's settings as a hiker trying to find the bottom of a foggy valley. The hiker feels the slope under their feet and takes a step downhill. If the valley is smooth and predictable, the hiker can easily find the bottom. But if the valley is a jagged, chaotic mess of cliffs and spikes, the hiker might get stuck, fall off a cliff, or wander forever without ever finding the lowest point.

For decades, scientists have been puzzled by the "valleys" inside modern AI. These valleys are the loss landscapes—the mathematical map of how wrong the AI is. The problem is that these landscapes are incredibly bumpy and strange. In many other fields of math, we have rules that say, "If you move a little bit, the slope changes a little bit." This is called Lipschitz smoothness. It's like walking on a gentle hill where the ground doesn't suddenly turn into a vertical wall. But in deep neural networks, the ground can change wildly; a tiny step might lead to a massive, unpredictable jump in the slope. Because of this, mathematicians have struggled to prove that the hiker (the AI) will actually reach the bottom, or even stop wandering, without making very specific, unrealistic assumptions about how the robot starts or what the data looks like.

This paper, titled "Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothness," steps into this foggy valley with a new map. The authors, Siqiao Mu and Diego Klabjan, argue that while the landscape is indeed wild, it isn't chaotic in a way that breaks the rules of math. They discovered a hidden pattern they call "double polynomial smoothness."

Here is the core of their discovery: In the past, researchers tried to prove that the AI's settings (the parameters) would stay within a safe, bounded area, like a hiker staying on a marked trail. But in real-world AI, the settings often wander far away, learning complex features. The authors realized that even when the hiker wanders far out, the "steepness" of the hill doesn't explode randomly. Instead, it grows in a very specific, predictable way. They found that the change in the slope is limited by the size of the step taken, multiplied by a polynomial (a fancy math term for a curve like $x^2$ or $x^3$ ) of how far the hiker has wandered.

Think of it like this: If you are walking on a normal hill, the steepness is constant. If you are walking on a "double polynomial" hill, the steepness gets steeper the further you go, but it follows a strict recipe. If you double your distance from the start, the steepness doesn't go to infinity; it goes up by a specific power, like squaring or cubing that distance. Because this growth is predictable, the authors proved that as long as the hiker takes small enough steps (a learning rate adjusted to the current steepness), they will eventually stop wandering and settle down.

The paper proves that for a neural network with $L$ layers, the "wandering" (measured by the gradient norm) will shrink to zero at a rate of $O(1/T^{1/L})$ , where $T$ is the number of steps taken. In plain English, this means the AI will learn to stop making big mistakes, even if it starts with random settings and the data is messy, provided the activation functions (the switches that turn neurons on and off) behave nicely. The authors explicitly show that this works for networks of any width or depth, without needing the "infinite width" or "perfectly balanced data" assumptions that previous theories required. Specifically, their proof requires activation functions to be Lipschitz smooth, a property that holds for linear, tanh, softplus, and sigmoid functions.

However, the paper is careful not to promise magic. It proves that the AI will reach a "stationary point"—a place where it stops improving significantly—but it does not guarantee that this point is the perfect global best (the absolute bottom of the valley). Crucially, the authors note that their mathematical proof does not apply to the ReLU activation function. Because ReLU has a sharp corner where it is not "Lipschitz smooth," it fails the core assumption of the proof, leaving the convergence behavior of ReLU networks largely undetermined by this specific framework. The authors have provided a rigorous mathematical proof, not just a simulation, showing that the hiker can indeed find a stopping point in this complex, jagged landscape, provided they adjust their step size according to the "double polynomial" rules of the terrain and use smooth activation functions.

Technical Summary: Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothness

Problem Statement

The theoretical understanding of gradient descent (GD) on neural network (NN) loss landscapes has long been hindered by the lack of global Lipschitz smoothness. Unlike standard optimization settings where the gradient change is linearly bounded by the parameter change, NN loss landscapes are highly non-convex, and their local Lipschitz constants can grow arbitrarily large as parameters approach infinity.

Existing convergence analyses typically rely on restrictive assumptions to bypass this issue:

Over-parameterization/Infinite-width regimes: Assuming the network is sufficiently wide or infinitely wide (e.g., Neural Tangent Kernel regime), ensuring iterates remain in a bounded set near initialization.
Specific architectures or datasets: Requiring balanced/Gaussian initialization, orthogonal datasets, or specific activation functions.
Generalized smoothness relaxations: Prior works have proposed conditions like $(L_0, L_1)$ -smoothness or relative smoothness, but these are often empirically motivated, apply only to specific cases (e.g., frozen layers, linear networks), or fail to capture the recursive structure of deep networks with nonlinear activations.

Consequently, a fundamental gap remains: popular optimization methods are analyzed under smoothness assumptions that do not hold for general, finite-width, deep neural networks, particularly in the "feature learning" regime where parameters move significantly from initialization.

Methodology

This paper introduces a novel analytical framework based on Double Polynomial Smoothness, a generalized Lipschitz smoothness condition that characterizes the gradient behavior of general feedforward neural networks without requiring bounded iterates or specific initialization schemes.

Core Assumptions

The analysis relies on mild, standard assumptions:

Activation Functions: Must be Lipschitz smooth, Lipschitz continuous, and linearly bounded. This class includes linear, tanh, softplus, and sigmoid functions.
Loss Function: Must be Lipschitz smooth with respect to the model outputs (satisfied by Mean Squared Error).
Data/Architecture: No restrictions on width, depth, or dataset structure (beyond normalization for algebraic convenience).

Theoretical Framework

The authors establish that the Lipschitz properties of activation functions are partially preserved through repeated compositions in deep networks. By recursively relating the Lipschitz properties of one layer to the next, they derive a bound on the change in the gradient of the model function.

Key to the methodology is the definition of Double Polynomial Smoothness:

Gradient Change Bound: The change in the gradient of the model function (and subsequently the loss function) is upper-bounded by the change in the parameter space ( $\|W_2 - W_1\|$ ), multiplied by polynomial terms of the parameter norms at both endpoints ( $\|W_1\|$ and $\|W_2\|$ ).
Descent Lemma: This condition allows for the derivation of a descent lemma where the loss decreases, provided the learning rate is sufficiently small relative to the current parameter norms and loss value.
Parameter Growth Control: The authors prove that while parameters may grow, they do so sublinearly. Specifically, the parameter norm grows at a rate of $O(T^{(L-1)/L})$ for an $L$ -layer network.

Key Contributions

Double Polynomial Smoothness: The paper establishes that feedforward neural networks and their loss functions satisfy a "double polynomial smoothness" condition. This condition explicitly bounds the gradient variation by the parameter distance scaled by polynomials of the parameter norms at both the current and previous steps.
Convergence Rate Proof: The authors prove that gradient descent on the loss function of an $L$ -layer neural network converges to a stationary point (where the squared gradient norm approaches zero) at a rate of $O(1/T^{1/L})$ .
General Applicability: The analysis applies to networks of arbitrary width and depth with standard activation functions (linear, tanh, softplus, sigmoid) and standard loss functions (e.g., MSE), without requiring over-parameterization, specific initialization, or bounded iterates.

Results

Convergence Guarantee: Under the proposed learning rate schedule (which depends on the current parameter norm and loss value), the minimum squared gradient norm over $T$ iterations satisfies:
$\min_{t=0,\dots,T-1} \|\nabla L(W_t)\|^2 = O\left(\frac{1}{T^{1/L}}\right)$
The hidden constants in the $O(\cdot)$ notation depend polynomially on the loss smoothness constant, network width, initial loss, and initial parameter norm, and exponentially on the number of layers $L$ .
Parameter Dynamics: The proof demonstrates that the parameter norms grow sublinearly to infinity, specifically at a rate of $T^{(L-1)/L}$ , which is crucial for establishing the convergence rate.
Learning Rate Adaptivity: The required learning rate is explicitly computable based on current state variables ( $\|W_t\|$ and $L(W_t)$ ) and does not require solving implicit equations or subroutines.

Significance and Claims

The paper claims to close a significant theoretical gap in deep learning optimization by providing convergence guarantees for gradient descent on general neural networks without the restrictive assumptions of prior work.

Beyond "Lazy Training": Unlike analyses relying on the Neural Tangent Kernel (NTK) or "feature learning" regimes where parameters stay near initialization, this framework accounts for the "feature learning" regime where parameters evolve significantly.
Generalization of Smoothness: The work moves beyond standard Lipschitz smoothness and existing generalized smoothness conditions (like $(L_0, L_1)$ -smoothness) by deriving a condition that naturally arises from the recursive structure of deep networks with nonlinear activations.
Limitations and Future Directions: The authors modestly note that their bounds depend polynomially on the network width and exponentially on the depth, and they leave open the question of whether these dependencies can be tightened. Furthermore, the framework currently relies on smoothness assumptions that exclude ReLU networks, leaving the behavior of GD on ReLU networks largely undetermined by this specific analysis.

In summary, this work provides a rigorous theoretical foundation for the convergence of gradient descent in deep learning, demonstrating that even without global Lipschitz smoothness or bounded iterates, the specific structure of neural networks ensures convergence to stationary points under mild conditions.