Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods

Taiji Suzuki, Shunta Akiyama

Authors: Taiji Suzuki and Shunta Akiyama (ICLR 2021)

Deep learning consistently outperforms traditional kernel methods in practice, yet explaining why remains one of the most significant challenges in deep learning theory. While recent theoretical frameworks like the Neural Tangent Kernel (NTK) have attempted to explain neural networks by approximating them as linear models, this ICLR 2021 paper argues that such approximations miss the very "magic" that makes deep learning superior.

By evaluating the excess risk of a deep learning estimator trained via noisy gradient descent, the authors provide a rigorous theoretical foundation proving that deep learning can achieve significantly faster learning rates than any linear estimator—especially in high-dimensional settings.

The Problem: The NTK Paradox and the Curse of Dimensionality

For several years, the NTK regime dominated deep learning theory, suggesting that highly overparameterized networks behave like linear models (kernels) during training. However, this creates a paradox: if neural networks are merely kernels, why do they so consistently outperform traditional kernel methods?

Traditional kernel methods and other "linear estimators" (such as Random Feature Models, $k$-Nearest Neighbors, and Nadaraya-Watson estimators) suffer from the curse of dimensionality. As the input dimension ($d$) increases, the volume of data required to maintain predictive accuracy grows exponentially.

This paper seeks to prove that "beyond-kernel" deep learning—where the model retains its non-convexity and features are dynamically learned rather than fixed—can escape this curse and achieve "fast" convergence rates that linear methods mathematically cannot match.

Theoretical Framework and Methodology

Because this is a purely theoretical paper, the authors do not rely on empirical datasets like MNIST or CIFAR-10. Instead, they analyze a mathematical teacher-student regression model using a mildly overparameterized two-layer neural network. The setup involves a target function (the teacher) that the model (the student) attempts to recover from $n$ noisy samples.

The theoretical framework relies on three core pillars:

  1. Noisy Gradient Descent (NGD): The network is trained using a variant of Stochastic Gradient Langevin Dynamics (SGLD) with ridge regularization. The injected noise is crucial; it allows the algorithm to explore the highly non-convex loss landscape and eventually behave like a Bayes estimator, reaching a near-global optimal solution.
  2. Broad Comparison Class: The neural network's performance is evaluated against a massive class of linear estimators, ensuring the superiority claim is robust and broadly applicable.
  3. Local Rademacher Complexity: Instead of using standard Rademacher complexity—which typically yields slower $O(1/\sqrt{n})$ learning rates—the authors employ local Rademacher complexity. By focusing on the geometry of the function class near the optimal solution, they derive "fast" learning rates closer to $O(1/n)$.

Key Insights: Why Non-Convexity is a Feature, Not a Bug

The paper's most profound takeaway is that the non-convexity of neural networks, often viewed as an optimization hurdle, is actually the key to their adaptability.

  • The Convex Hull Argument: Linear estimators are effectively restricted to the convex hull of their basis functions. If the true function class is highly non-convex, this convex hull becomes "fat" and statistically inefficient. Neural networks, by remaining non-convex, can "shrink" to fit the true function class much more tightly.
  • Adaptive Feature Learning: Linear methods must pre-prepare a massive, redundant set of basis functions to cover all possibilities in high dimensions. In contrast, neural networks adaptively select and refine their basis functions (the hidden units) during the training process.
  • Independence from Dimension: The convergence rate for the neural network is largely independent of the input dimension $d$. Meanwhile, the lower bound for linear estimators shows severe degradation as $d$ grows.

Main Results: Mathematical Proof of Superiority

The authors successfully establish minimax optimal rates demonstrating the superiority of deep learning:

  • Linear Estimator Lower Bound: For any linear estimator, the excess risk is lower-bounded by a rate that approaches $O(n^{-1/2})$ as the dimension $d$ increases. This mathematically formalizes the curse of dimensionality.
  • Neural Network Upper Bound: The neural network trained with NGD achieves a fast learning rate of $O(n^{-\text{constant}})$, where the constant does not depend on $d$.
  • Asymptotic Superiority: In high-dimensional settings ($d \to \infty$), the ratio of the neural network's risk to the linear estimator's risk converges to zero. This definitively proves the benefit of deep learning over shallow linear methods.

Limitations and Future Directions

While groundbreaking, the theoretical analysis has a few constraints:

  • Architectural Limits: The formal proofs are currently restricted to two-layer (one hidden layer) models, though the authors suggest the techniques could extend to deeper architectures.
  • Computational Complexity: The analysis assumes the NGD algorithm reaches a stationary distribution. In practice, the time required to reach this state (the "spectral gap") can be exponentially large depending on the inverse temperature, which may not perfectly reflect standard training timelines.
  • Standard SGD vs. SGLD: The proof specifically requires the explicit Gaussian noise of SGLD. While standard Stochastic Gradient Descent (SGD) possesses "internal noise" from mini-batching, it is not mathematically identical to Langevin noise, leaving a slight theoretical gap between this proof and everyday deep learning practice.

Summary updated

Abstract

Establishing a theoretical analysis that explains why deep learning can outperform shallow learning such as kernel methods is one of the biggest issues in the deep learning literature. Towards answering this question, we evaluate excess risk of a deep learning estimator trained by a noisy gradient descent with ridge regularization on a mildly overparameterized neural network, and discuss its superiority to a class of linear estimators that includes neural tangent kernel approach, random feature model, other kernel methods, $k$-NN estimator and so on. We consider a teacher-student regression model, and eventually show that {\it any} linear estimator can be outperformed by deep learning in a sense of the minimax optimal rate especially for a high dimension setting. The obtained excess bounds are so-called fast learning rate which is faster than $O(1/\sqrt{n})$ that is obtained by usual Rademacher complexity analysis. This discrepancy is induced by the non-convex geometry of the model and the noisy gradient descent used for neural network training provably reaches a near global optimal solution even though the loss landscape is highly non-convex. Although the noisy gradient descent does not employ any explicit or implicit sparsity inducing regularization, it shows a preferable generalization performance that dominates linear estimators.
BibTeX
@inproceedings{suzuki2021benefit,
  author = {Taiji Suzuki and Shunta Akiyama},
  title = {{Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=wYOfBHI6iOF},
}
Figure