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 (4)

• A Priori Estimates of the Population Risk for Residual 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 (3)

• 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