📊 statistics

Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks

This paper bridges the theoretical gap in deep learning by establishing the first minimax-optimal generalization rates for gradient descent and stochastic gradient descent methods applied to deep ReLU networks, demonstrating that with sufficient width, these methods achieve optimal performance comparable to kernel methods.

Original authors: Junyu Zhou, Puyu Wang, Yunwen Lei, Yiming Ying, Ding-Xuan Zhou

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Junyu Zhou, Puyu Wang, Yunwen Lei, Yiming Ying, Ding-Xuan Zhou

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

The Big Picture: The "Deep Learning" Mystery

Imagine you are trying to teach a robot to recognize cats in photos. You give it a massive brain (a Deep Neural Network) with millions of tiny connections. You show it thousands of pictures and let it learn by trial and error using a method called Gradient Descent (basically, "if I make a mistake, nudge my brain slightly in the opposite direction").

Surprisingly, even though this robot has a brain far too big for the job (it's "overparameterized"), it doesn't just memorize the photos; it learns the concept of a cat and can recognize new cats it has never seen before. This is called generalization.

For a long time, scientists were puzzled. They knew how the robot learned, but they couldn't mathematically prove why it was so good at generalizing, especially when the brain was very deep (many layers).

The Old Way vs. The New Way

The Old Theory (The "Shallow" View):
Previously, researchers could only prove that this learning magic worked for "shallow" networks (brains with just a few layers) or for very simple, smooth functions. They used a mathematical shortcut called the Neural Tangent Kernel (NTK). Think of the NTK as a "shadow" or a "simplified map" of the neural network. In this simplified world, the learning process looks like a classic, well-understood method called Kernel Methods.

The problem was: Does this "shadow" map work for deep, complex networks?
Previous attempts to prove this for deep networks hit a wall. To make the math work, they had to assume the network was so wide (had so many neurons) that the width had to grow exponentially with the depth.

Analogy: Imagine trying to build a skyscraper. The old theory said, "To build a 100-story building, you need a foundation that is 1,000,000 miles wide." That's impractical and unrealistic.

The New Discovery (This Paper):
This paper says: No, you don't need a foundation that wide.
The authors proved that for deep networks with "ReLU" activation (a specific type of switch that turns neurons on or off), the learning process behaves just like the ideal "shadow" map, provided the network is just polynomially wide.

Analogy: They proved you can build that 100-story skyscraper with a foundation that is only 1,000 miles wide. It's still huge, but it's actually buildable and realistic.

The Core Achievement: "Optimal Rates"

The paper's main claim is about speed and efficiency.

In statistics, there is a concept called the "Minimax-Optimal Rate." Think of this as the speed limit for learning. It's the fastest possible speed at which any algorithm can learn a specific type of problem without making mistakes.

The Claim: The authors proved that Gradient Descent (GD) and Stochastic Gradient Descent (SGD) on these deep networks hit this "speed limit."
The Metaphor: Imagine a race. The "Kernel Method" (the old, simple math) is a Ferrari that drives at the speed limit. The "Deep Neural Network" was thought to be a rusty truck that might be slower or unpredictable. This paper proves that, under the right conditions, the rusty truck (the deep network) is actually driving at the exact same speed as the Ferrari. It is just as fast and just as accurate.

How They Did It (The "Secret Sauce")

The authors had to overcome a major mathematical hurdle. In deep networks, the layers depend on each other in a messy, tangled way. If you change one weight in the first layer, it ripples through all the other layers.

The "Linear" Approximation: They treated the complex, non-linear network as if it were a simple, straight line (linear) near the starting point.
The "Gap" Problem: They had to prove that the "messy" deep network and the "clean" simple map (the NTK) stay very close to each other during the entire training process.
The Breakthrough: Previous math said these two would drift apart quickly unless the network was impossibly wide. The authors developed new, sharper tools to measure this drift. They showed that the drift stays small enough as long as the network is wide in a polynomial way (e.g., width = depth squared), rather than an exponential way.

Summary of Results

For Gradient Descent (GD): They proved it reaches the best possible accuracy for deep networks, provided the network isn't too narrow.
For Stochastic Gradient Descent (SGD): This is the version where the robot learns from one photo at a time (randomly). They proved this version also hits the "speed limit" of accuracy, and it does so with even less computational effort than the full GD method.
The Condition: The network width must scale with the depth, the data size, and the complexity of the data, but only in a manageable, polynomial way.

What This Means (According to the Paper)

The paper concludes that Deep Neural Networks are not magic black boxes. When trained with standard methods (GD/SGD), they are mathematically equivalent to the best possible classical learning methods (Kernel Methods) in terms of how well they generalize to new data.

They have closed the gap between the theory of "simple" learning and "deep" learning, proving that deep learning is just as theoretically sound as the old methods, as long as you give the network enough (but not impossibly huge) width.

Note: The paper focuses strictly on regression problems (predicting numbers, like house prices) and Deep ReLU networks. It does not claim these results apply to other types of networks (like Convolutional or Residual networks) or other activation functions, though it suggests those are interesting future directions.

Technical Summary: Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks

1. Problem Formulation

This paper addresses a critical gap in the theoretical understanding of deep neural networks (DNNs) trained via gradient descent. While recent progress within the Neural Tangent Kernel (NTK) regime has established statistical generalization performance for overparameterized networks, existing work on regression problems is largely limited to shallow architectures or requires restrictive assumptions (e.g., exponential width scaling with depth).

The authors focus on least-squares regression using deep ReLU networks trained by Gradient Descent (GD) and Stochastic Gradient Descent (SGD). The primary objective is to determine whether DNNs can achieve minimax-optimal rates of excess population risk comparable to classical kernel methods, specifically under the assumption that the network width scales polynomially with respect to the network depth ( $L$ ), sample size ( $n$ ), and data dimension ( $d$ ), rather than exponentially.

The excess population risk is defined as $\varepsilon_{\text{risk}}(f_W(T)) = L(f_W(T)) - L(f_\rho) = \frac{1}{2}\|f_W(T) - f_\rho\|_\rho^2$ , where $f_\rho$ is the target regression function. The analysis relies on two standard assumptions:

Effective Dimension: The capacity of the hypothesis space is characterized by a parameter $\gamma \in [0, 1]$ , such that the trace of the resolvent of the integral operator scales as $\lambda^{-\gamma}$ .
Source Condition: The target function $f_\rho$ possesses smoothness $\beta > 0$ , quantified by $\|L^{-\beta} f_\rho\|_\rho \leq B$ .

2. Methodology and Technical Approach

The core methodological contribution is a refined error decomposition strategy that bridges the gap between deep neural networks and kernel methods without relying on the structural properties valid only for shallow networks.

2.1 Refined Error Decomposition

For a network $f_W(T)$ after $T$ iterations, the authors decompose the error $\|f_W(T) - f_\rho\|_\rho^2$ into four terms:
$\|f_W(T) - f_\rho\|_\rho^2 \lesssim \|f_W(T) - f_W^{\text{lin}}(T)\|_\rho^2 + \|f_W^{\text{lin}}(T) - S_m g_T^m\|_\rho^2 + \|S_m g_T^m - S g_T\|_\rho^2 + \|S g_T - f_\rho\|_\rho^2$
where:

$f_W^{\text{lin}}(T)$ is the linear approximation of the network at initialization.
$g_T^m$ is the GD/SGD iterate in the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_m$ associated with the finite-width NTK $K_m$ .
$g_T$ is the GD iterate in the RKHS $\mathcal{H}_K$ associated with the infinite-width NTK $K$ .
$S_m$ and $S$ are inclusion mappings from the RKHSs to $L^2_{\rho_x}$ .

2.2 Key Technical Challenges and Solutions

The paper identifies and resolves three specific technical hurdles that prevented previous shallow-network analyses from extending to deep architectures:

Forward/Backward Propagation Bounds: Previous works (e.g., [53]) provided bounds on the deviation between the non-linear network and its linear approximation that scaled exponentially with depth $L$ . The authors extend the analysis of forward and backward propagation from the finite training set to the entire input space $\mathcal{X}$ . This allows them to establish a bound of $\|f_W(T) - f_W^{\text{lin}}(T)\|_\infty^2 \lesssim m^{-1/3} \text{Poly}(L, \eta T)$ , reducing the width requirement from exponential to polynomial in $L$ .
Kernel Concentration ( $K_m$ vs. $K$ ): In shallow networks, the finite-width kernel $K_m$ is a sum of i.i.d. random kernels, allowing for standard concentration arguments. In deep networks, gradients depend on weights across all layers, breaking the i.i.d. structure. The authors develop a refined analysis (Lemma 16) to bound the infinity norm difference $\|K_m - K\|_\infty$ . They prove $\|K_m - K\|_\infty \lesssim m^{-1/6}\sqrt{d}L$ under the condition $m \gtrsim dL^3$ , significantly relaxing the overparameterization requirement compared to previous exponential scaling results.
Effective Dimension Equivalence: For shallow networks, one can show the effective dimension of the finite-width RKHS matches the infinite-width limit. For deep networks, this is non-trivial. Instead of comparing dimensions directly, the authors introduce $g_T$ (the infinite-width iterate) as an intermediate term. They separately bound the distance between the finite-width iterate and the infinite-width iterate ( $\|g_T^m - g_T\|_\rho$ ) using the kernel discrepancy, and the distance between the infinite-width iterate and the target ( $\|g_T - f_\rho\|_\rho$ ) using standard kernel method results. This bypasses the need to prove $\tilde{\gamma} = \gamma$ directly for the deep case.

3. Key Contributions

The paper makes the following specific contributions:

Minimax-Optimal Rates for Deep Networks: It establishes the first known minimax-optimal excess population risk rates of $O(n^{-\frac{2\beta}{2\beta+\gamma}})$ for both GD and SGD with deep ReLU networks.
Polynomial Width Scaling: The results hold under the condition that the network width $m$ scales polynomially with $L, n,$ and $d$ (specifically $m \gtrsim \text{Poly}(L, n, d)$ ), removing the need for the exponential width scaling ( $m \gtrsim \exp(L)$ ) required by prior work on deep regression.
Removal of NTK Gram Matrix Assumptions: Unlike some previous works, the analysis does not require the smallest eigenvalue of the NTK Gram matrix to be strictly positive, a condition that often fails as sample size increases.
Unified Analysis for GD and SGD: The framework provides optimal rates for both full-batch GD and one-pass SGD, demonstrating that SGD can achieve similar rates with lower computational cost (gradient complexity).

4. Main Results

Under Assumptions 1 (Effective Dimension) and 2 (Source Condition), and with appropriate step sizes and iteration counts:

Gradient Descent (GD): With network width $m \gtrsim \text{Poly}(L, d, n)$ and $T \approx n^{\frac{1}{2\beta+\gamma}}$ , GD achieves an excess risk of:
$L(f_W(T)) - L(f_\rho) \lesssim n^{-\frac{2\beta}{2\beta+\gamma}} \log^4(n/\delta)$
This matches the optimal rate achievable by kernel methods in the RKHS setting.
Stochastic Gradient Descent (SGD): With similar width scaling and $T \approx n^{\frac{2\beta+1}{2\beta+\gamma}}$ , SGD achieves:
$\mathbb{E}[L(f_W(T)) - L(f_\rho)] \lesssim n^{-\frac{2\beta}{2\beta+\gamma}} \log^2(n) \log^{2\beta}(n/\delta)$
This confirms that SGD can also replicate classical kernel results for deep networks under mild overparameterization.

The results are summarized in Table 1 of the paper, contrasting with prior works that were limited to shallow networks, smooth activations, or required exponential width.

5. Significance and Claims

The paper claims to significantly advance the theoretical understanding of generalization in deep learning by:

Bridging the Depth Gap: It resolves the open question of whether DNNs trained by GD/SGD can achieve generalization performance on par with their kernel-based counterparts. The authors provide an affirmative answer, demonstrating that deep ReLU networks can indeed achieve minimax-optimal rates.
Practical Overparameterization: By reducing the required network width from exponential to polynomial in the depth, the results align more closely with practical deep learning scenarios where networks are deep but not exponentially wide.
Robustness to Activation Functions: The analysis specifically targets non-smooth ReLU activations, which are standard in practice, whereas previous optimal rate results were often restricted to smooth activation functions.

The authors note that their symmetric initialization is a technical tool to simplify analysis (ensuring $f_{W(0)}=0$ ) but discuss in Section 5 that the uniform concentration properties of the NTK hold for general non-symmetric initializations as well, suggesting the results are robust to this specific initialization choice.

The paper concludes by identifying future directions, such as extending these results to deep networks with smooth activations and other architectures like convolutional and residual networks, but does not propose experimental validations or specific application domains beyond the theoretical regression setting.