The Connection Between Approximation, Depth Separation and Learnability in Neural Networks

Abstract

Several recent works have shown separation results between deep neural networks, and hypothesis classes with inferior approximation capacity such as shallow networks or kernel classes. On the other hand, the fact that deep networks can efficiently express a target function does not mean that this target function can be learned efficiently by deep neural networks. In this work we study the intricate connection between learnability and approximation capacity. We show that learnability with deep networks of a target function depends on the ability of simpler classes to approximate the target. Specifically, we show that a necessary condition for a function to be learnable by gradient descent on deep neural networks is to be able to approximate the function, at least in a weak sense, with shallow neural networks. We also show that a class of functions can be learned by an efficient statistical query algorithm if and only if it can be approximated in a weak sense by some kernel class. We give several examples of functions which demonstrate depth separation, and conclude that they cannot be efficiently learned, even by a hypothesis class that can efficiently approximate them.

arXiv commentCOLT 2021 camera ready version

References in corpus (15)

• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Benefits of depth in neural networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Depth Separation for Neural Networks
• On the Approximation Properties of Random ReLU Features
• Agnostic Learning of a Single Neuron with Gradient Descent
• Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
• Learning a Single Neuron with Gradient Methods
• Learning Parities with Neural Networks
• Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
• Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
• Poly-time universality and limitations of deep learning
• Neural Networks with Small Weights and Depth-Separation Barriers
• Learning Boolean Circuits with Neural Networks

Cited by in corpus (4)

• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Size and Depth Separation in Approximating Benign Functions with Neural Networks
• Depth separation beyond radial functions
• On the Approximation Power of Two-Layer Networks of Random ReLUs