Deep Equals Shallow for ReLU Networks in Kernel Regimes

Alberto Bietti, Francis R. Bach

Abstract

Deep networks are often considered to be more expressive than shallow ones in terms of approximation. Indeed, certain functions can be approximated by deep networks provably more efficiently than by shallow ones, however, no tractable algorithms are known for learning such deep models. Separately, a recent line of work has shown that deep networks trained with gradient descent may behave like (tractable) kernel methods in a certain over-parameterized regime, where the kernel is determined by the architecture and initialization, and this paper focuses on approximation for such kernels. We show that for ReLU activations, the kernels derived from deep fully-connected networks have essentially the same approximation properties as their shallow two-layer counterpart, namely the same eigenvalue decay for the corresponding integral operator. This highlights the limitations of the kernel framework for understanding the benefits of such deep architectures. Our main theoretical result relies on characterizing such eigenvalue decays through differentiability properties of the kernel function, which also easily applies to the study of other kernels defined on the sphere.

Introduction

A central mystery in deep learning theory is explaining why deep networks perform so much better than shallow (two-layer) networks. Recently, theorists have made significant strides by studying over-parameterized networks in the "lazy training" or "kernel" regime. In this regime, infinitely wide neural networks trained with gradient descent behave mathematically like kernel methods, specifically using the Neural Tangent Kernel (NTK) or Random Features (RF) kernel.

Because kernel methods are mathematically well-understood, this provided a tractable way to study neural networks. However, a lingering question remained: does this kernel framework actually capture the "magic" of depth? If an NTK is constructed from a 100-layer network, is it fundamentally more expressive than one built from a 2-layer network? This research definitively answers that question for fully-connected ReLU networks.

Methodology: The Endpoint Rule

The study analyzes the approximation properties of dot-product kernels on a hypersphere, where the similarity between two inputs depends only on the angle between them. To determine what functions a kernel can approximate, the authors examine the "eigenvalue decay" of its associated integral operator. A fast decay indicates the kernel can only approximate very smooth functions, while a slower decay suggests it can capture rougher, more complex functions.

Theorem 1: Differentiability and Decay

The authors prove a novel, general theorem (Theorem 1) that links eigenvalue decay directly to the differentiability of the kernel function at its endpoints. Specifically, the expressivity is governed by the fractional Taylor expansion of the kernel when two inputs are perfectly aligned or anti-aligned. This "Endpoint Rule" simplifies the analysis of complex compositional kernels by focusing on their behavior at the extremes.

The Equivalence of Deep and Shallow ReLU

When layers are added to a network in the kernel regime, the resulting kernel function is mathematically composed with itself. The core theoretical contribution of this work is the proof that for ReLU activations, this composition does not change the leading fractional exponent at the endpoints.

Consequently, the eigenvalue decay remains identical regardless of depth:

  • Random Features (RF) Kernel: Decay rate of $k^{-d-2}$
  • Neural Tangent Kernel (NTK): Decay rate of $k^{-d}$

This implies that deep and shallow ReLU networks share the same Reproducing Kernel Hilbert Space (RKHS) in this regime. Interestingly, the authors also use their theorem to show that the standard Laplace kernel shares the exact same $k^{-d}$ decay as the ReLU NTK, explaining why the two often perform similarly in empirical benchmarks.

Empirical Results

The theoretical findings were tested using both synthetic and real-world datasets:

  • Synthetic Data: Randomly sampled inputs on a 4D sphere ($S^3$) were mapped to target functions to test approximation limits.
  • Image Classification: On MNIST and Fashion-MNIST, depth provided no significant performance boost for the NTK. For example, on MNIST, a 2-layer NTK achieved 98.49% accuracy, while a 5-layer NTK achieved a nearly identical 98.46%.

Discussion and Limitations

While the results show that depth does not improve expressivity for ReLU networks in the kernel regime, the authors identify an exception: step activations. Unlike ReLU, kernels derived from step activations do become more expressive with depth. However, step networks are notoriously difficult to optimize with gradient descent, making them less practical.

The most significant implication of this work is the identification of a "Kernel Blindspot." The kernel framework fundamentally fails to explain why deep fully-connected networks outperform shallow ones in practice. To understand the true power of depth, the field must look beyond "lazy training" and focus on "active" or "mean-field" regimes where weights move significantly to learn hierarchical features.

Finally, the authors note that this study focuses on fully-connected architectures. Future research may explore whether depth provides measurable benefits in the kernel regime for convolutional architectures (CNNs), such as improved stability to image deformations.

Summary updated

Abstract

Deep networks are often considered to be more expressive than shallow ones in terms of approximation. Indeed, certain functions can be approximated by deep networks provably more efficiently than by shallow ones, however, no tractable algorithms are known for learning such deep models. Separately, a recent line of work has shown that deep networks trained with gradient descent may behave like (tractable) kernel methods in a certain over-parameterized regime, where the kernel is determined by the architecture and initialization, and this paper focuses on approximation for such kernels. We show that for ReLU activations, the kernels derived from deep fully-connected networks have essentially the same approximation properties as their shallow two-layer counterpart, namely the same eigenvalue decay for the corresponding integral operator. This highlights the limitations of the kernel framework for understanding the benefits of such deep architectures. Our main theoretical result relies on characterizing such eigenvalue decays through differentiability properties of the kernel function, which also easily applies to the study of other kernels defined on the sphere.
BibTeX
@inproceedings{bietti2021deep,
  author = {Alberto Bietti and Francis R. Bach},
  title = {{Deep Equals Shallow for ReLU Networks in Kernel Regimes}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=aDjoksTpXOP},
}
Figure