Deep Equals Shallow for ReLU Networks in Kernel Regimes

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.

References in corpus (16)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Neural Networks as Gaussian Processes
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• On Exact Computation with an Infinitely Wide Neural Net
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• On Lazy Training in Differentiable Programming
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Properties of Learning with Random Features
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• Diverse Neural Network Learns True Target Functions
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• A Fine-Grained Spectral Perspective on Neural Networks
• Depth Separation for Neural Networks
• A Spectral Analysis of Dot-product Kernels

Cited by in corpus (6)

• Learning with invariances in random features and kernel models
• Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks
• Deep Networks Provably Classify Data on Curves
• Uniform Generalization Bounds for Overparameterized Neural Networks
• The staircase property: How hierarchical structure can guide deep learning
• Neural Contextual Bandits without Regret