📊 statistics

Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods

This paper establishes a theoretical connection between gradient-based training of over-parameterized deep neural networks and kernel methods, deriving the first minimax-optimal generalization rates for both gradient descent and stochastic gradient descent in deep regression tasks.

Original authors: Junyu Zhou, Puyu Wang, Yunwen Lei, Marius Kloft, Yiming Ying

Published 2026-06-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Junyu Zhou, Puyu Wang, Yunwen Lei, Marius Kloft, Yiming Ying

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 Mystery: Why Do Giant Neural Networks Work?

Imagine you are trying to teach a student (a Deep Neural Network) to predict the weather. You give them a massive textbook with millions of pages (the training data).

In the world of math, there is a famous paradox: If a student has a memory so huge they can memorize every single page of the textbook perfectly, they usually fail the test when they see a new page they haven't seen before. This is called "overfitting."

However, in real life, Deep Neural Networks (DNNs) are like students with photographic memories who somehow still pass the test on new weather patterns. They are "over-parameterized" (they have way more neurons than data points), yet they generalize well.

The Question: How do these giant, messy, non-linear systems manage to learn the "rules" of the world instead of just memorizing the textbook?

The Tool: The "Neural Tangent Kernel" (NTK)

To solve this, researchers use a tool called the Neural Tangent Kernel (NTK).

Think of a Deep Neural Network as a complex, twisting mountain range. When you start training it (using Gradient Descent), you are essentially walking down the mountain to find the lowest point (the best prediction).

The NTK is like a flat map of that mountain. It says: "If the mountain is wide enough (has enough neurons), the path you take while walking down looks almost exactly like walking down a simple, smooth hill."

This "simple hill" is actually a Kernel Method, a much older, simpler, and well-understood type of machine learning algorithm. If we can prove that the giant neural network behaves exactly like this simple, well-behaved map, we can use the known rules of the map to predict how the giant network will perform.

What This Paper Did

Previous research proved this "flat map" idea worked for shallow networks (networks with only a few layers, like a small house). But nobody knew if it worked for deep networks (networks with many layers, like a skyscraper). Deep networks are much more complex, and the math gets messy because the layers interact in complicated ways.

This paper says: "Yes, it works for deep networks too, provided the network is wide enough."

Here is the breakdown of their findings:

1. The "Wide Enough" Condition

Imagine you are trying to approximate a jagged, complex shape with a smooth curve.

The Paper's Claim: If your neural network is wide enough (has enough neurons in each layer), the jagged shape of the deep network smooths out and becomes indistinguishable from the simple Kernel Method map.
The Catch: The width doesn't need to be infinite, but it must grow at a specific "polynomial" rate relative to the amount of data you have. If you have more data, you need a slightly wider network, but it's a manageable increase, not an impossible one.

2. The "Perfect Match" (Minimax Rates)

In statistics, there is a concept called the Minimax Rate. Think of this as the "Gold Standard Speed Limit." It is the absolute fastest speed at which any learning algorithm can possibly learn a specific type of problem, no matter how smart it is.

The Paper's Claim: The authors proved that when you train a wide, deep neural network using standard methods (Gradient Descent or Stochastic Gradient Descent), it hits this Gold Standard Speed Limit.
The Analogy: It's like proving that a Formula 1 car (the Deep Neural Network) can drive just as fast as the theoretical fastest car possible on that track. They don't just drive fast; they drive at the theoretical limit of speed.

3. The "Smoothness" Requirement

The paper focuses on neural networks that use smooth activation functions (mathematical curves that don't have sharp corners, like the Sigmoid or Swish functions).

Why it matters: Think of a smooth road vs. a road full of potholes. Smooth roads are easier to drive on and easier to map. The authors used this "smoothness" to prove that the deep network's behavior stays close to the simple Kernel map.
Note: They did not prove this for "ReLU" networks (which have sharp corners) in this specific paper, though they mention it as a related area of study.

The "Secret Sauce": How They Did It

The authors had to overcome a major mathematical hurdle. In shallow networks, you can treat the layers as simple, independent blocks. In deep networks, the layers are like a chain reaction; a change in the first layer ripples through all the others in a complex way.

To solve this, they developed a new way of breaking down the error:

Old Way: Compare the Deep Network to a "Medium" Kernel (a slightly imperfect map).
New Way: Compare the Deep Network directly to the Perfect Infinite Map (the ideal Kernel).

They showed that if the network is wide enough, the "gap" between the Deep Network and the Perfect Map is so tiny that it disappears. This allowed them to borrow the proven speed limits from the Perfect Map and apply them to the Deep Network.

Summary of Results

The Problem: We didn't know if giant, deep neural networks could learn as efficiently as the best possible mathematical theory allowed.
The Solution: By proving that wide deep networks act just like simple, well-understood "Kernel" methods, they bridged the gap.
The Result: Deep Neural Networks trained with standard methods (GD and SGD) achieve the best possible learning speed (Minimax optimal rates) for regression tasks, as long as the network is wide enough.

What This Does Not Say (Based Strictly on the Text)

It does not claim that deeper networks are better than shallow ones; in fact, the math suggests that as the network gets deeper, the constants in the equations get worse (harder to train), even if the speed limit is the same.
It does not discuss clinical applications, self-driving cars, or specific real-world deployments. It is purely a theoretical proof about how these algorithms behave mathematically.
It does not claim this works for all types of networks (like those with sharp corners/ReLU) without modification; it specifically targets "smooth" activation functions.

In a nutshell: This paper proves that if you build a deep neural network wide enough, it stops behaving like a chaotic, unpredictable monster and starts behaving like a well-behaved, predictable machine that learns at the absolute fastest speed mathematically possible.

Technical Summary: Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods

Problem Formulation

The paper addresses a central open problem in deep learning theory: understanding the statistical generalization properties of Deep Neural Networks (DNNs) trained via gradient-based methods (Gradient Descent, GD, and Stochastic Gradient Descent, SGD). While the Neural Tangent Kernel (NTK) framework has successfully explained the behavior of shallow networks and established minimax-optimal rates for them, the generalization performance of deep architectures with smooth activation functions remains less understood.

The specific goal is to determine whether over-parameterized DNNs trained by GD or SGD can achieve minimax-optimal excess population risk rates comparable to their kernel-based counterparts. The authors focus on least-squares regression tasks where the target function $f_\rho$ possesses specific smoothness properties ( $\beta$ ) and the Reproducing Kernel Hilbert Space (RKHS) has a specific capacity characterized by a parameter $\gamma$ .

Methodology

The authors develop a theoretical framework that bridges the learning dynamics of DNNs with those of kernel methods in the infinite-width limit. The core methodology involves three main technical pillars:

Refined NTK Uniform Concentration:
Unlike prior works that focused on concentration over finite data points or specific layers, the authors establish that the NTK for deep smooth networks at Gaussian initialization uniformly concentrates to a deterministic kernel $K$ over the entire input space and across all layers.
- They improve the uniform convergence rate from $O(m^{-1/6})$ (previously established for ReLU networks) to $O(m^{-1/2})$ for smooth activations. This sharper rate is critical for deriving optimal risk bounds.
Novel Error Decomposition:
Existing error decompositions for shallow networks typically compare the DNN dynamics to a finite-width kernel method ( $g_T^m$ ) and then bound the distance to the target. The authors argue this approach fails for deep networks due to complex inter-layer dependencies that prevent treating the finite-width kernel as a simple sum of i.i.d. random kernels.
- Instead, they propose a decomposition that directly compares the DNN dynamics ( $f_{W(T)}$ ) to the infinite-width kernel GD iteration ( $g_T$ ) in the RKHS $\mathcal{H}_K$ :
  $\varepsilon_{\text{risk}}(f_{W(T)}) \lesssim \|f_{W(T)} - Sg_T\|_\rho^2 + \|Sg_T - f_\rho\|_\rho^2$
- The first term measures the deviation of the DNN from the idealized kernel dynamics, while the second term is the well-understood error of the kernel method itself.
Trajectory Control via Double Induction:
To bound the first term (the gap between DNN and kernel dynamics), the authors employ a carefully designed double induction argument. This allows them to control the distance the GD/SGD trajectory moves away from the initialization without the bound depending exponentially on the network width $m$ , ensuring the network remains in the "NTK regime" for a sufficient number of iterations.

Key Contributions

The paper makes the following specific contributions:

First Minimax-Optimal Rates for Deep Networks: The authors provide the first known minimax-optimal excess risk rates for both GD and SGD applied to deep neural networks with smooth activation functions.
Bridging Shallow and Deep Architectures: They establish a crucial connection showing that over-parameterized DNNs trained by gradient methods fully inherit the favorable learning dynamics of their infinite-width kernel counterparts.
Polynomial Width Requirement: They demonstrate that these optimal rates are achievable provided the network width $m$ scales polynomially with the sample size $n$ and dimension $d$ , specifically $m \gtrsim \text{Poly}(n, d)$ . This is a significant improvement over previous results for shallow networks that required exponential width.
General Applicability: The results hold for arbitrary smoothness parameters $\beta > 0$ and capacity parameters $\gamma \in [0, 1]$ , covering cases where the target function may not lie within the RKHS ( $\beta < 1/2$ ).

Main Results

Under standard assumptions on the activation function (smoothness and bounded derivatives), the effective dimension of the RKHS (Assumption 2), and the source condition of the target function (Assumption 3), the paper proves:

Optimal Risk Rate: For both GD and SGD, the excess population risk converges at the rate:
$O\left(n^{-\frac{2\beta}{2\beta + \gamma}}\right)$
provided that $2\beta + \gamma > 1$ .
Width Scaling: This rate is achieved when the network width satisfies:
$m \gtrsim C_\sigma^L d n^{\frac{2\beta+4}{2\beta+\gamma}} \log^2\left(\frac{dLn}{\delta}\right)$
where $L$ is the number of layers and $C_\sigma$ is a constant depending on the activation function.
Comparison to Kernel Methods: The derived rates match the classical minimax-optimal rates for kernel methods under the same assumptions, confirming that DNNs do not suffer from a generalization penalty compared to kernel methods when sufficiently wide.

Significance and Claims

The paper claims to substantially advance the understanding of how gradient methods generalize in deep neural networks by:

Answering an Open Question: It provides a positive answer to whether DNNs trained via GD/SGD can achieve generalization performance comparable to kernel-based counterparts.
Overcoming Depth Limitations: By refining the error decomposition and concentration analysis, the authors overcome the technical barriers that previously prevented extending minimax-optimal results from shallow to deep networks.
Theoretical Justification for Over-parameterization: The results theoretically justify the use of over-parameterized deep networks, showing that with sufficient width, they can replicate the optimal statistical performance of kernel methods.

The authors note that while their results rely on the NTK regime (linear approximations around initialization), which holds for a moderate number of iterations, this framework provides a rigorous foundation for understanding generalization in the over-parameterized setting. They acknowledge that reducing the exponential dependence on depth $L$ in the generalization bounds remains a direction for future work.