Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernels

Abstract

We establish a scale separation of Kolmogorov width type between subspaces of a given Banach space under the condition that a sequence of linear maps converges much faster on one of the subspaces. The general technique is then applied to show that reproducing kernel Hilbert spaces are poor $L^2$-approximators for the class of two-layer neural networks in high dimension, and that multi-layer networks with small path norm are poor approximators for certain Lipschitz functions, also in the $L^2$-topology.

References in corpus (9)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• A Priori Estimates of the Population Risk for Residual Networks
• Approximation spaces of deep neural networks
• On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspective

Cited by in corpus (4)

• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspective
• On the Convergence of Gradient Descent Training for Two-layer ReLU-networks in the Mean Field Regime
• A priori estimates for classification problems using neural networks