Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed

Abstract

A recent series of theoretical works showed that the dynamics of neural networks with a certain initialisation are well-captured by kernel methods. Concurrent empirical work demonstrated that kernel methods can come close to the performance of neural networks on some image classification tasks. These results raise the question of whether neural networks only learn successfully if kernels also learn successfully, despite neural networks being more expressive. Here, we show theoretically that two-layer neural networks (2LNN) with only a few hidden neurons can beat the performance of kernel learning on a simple Gaussian mixture classification task. We study the high-dimensional limit where the number of samples is linearly proportional to the input dimension, and show that while small 2LNN achieve near-optimal performance on this task, lazy training approaches such as random features and kernel methods do not. Our analysis is based on the derivation of a closed set of equations that track the learning dynamics of the 2LNN and thus allow to extract the asymptotic performance of the network as a function of signal-to-noise ratio and other hyperparameters. We finally illustrate how over-parametrising the neural network leads to faster convergence, but does not improve its final performance.

arXiv commentThe accompanying code for this paper is available at https://github.com/mariaref/rfvs2lnn_GMM_online

References in corpus (20)

• 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
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Enhanced Convolutional Neural Tangent Kernels
• On the Computational Efficiency of Training Neural Networks
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• The Gaussian equivalence of generative models for learning with shallow neural networks
• Neural Kernels Without Tangents
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• A Solvable High-Dimensional Model of GAN
• High Dimensional Classification via Regularized and Unregularized Empirical Risk Minimization: Precise Error and Optimal Loss
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods

Cited by in corpus (7)

• Data-driven emergence of convolutional structure in neural networks
• The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold
• Relative stability toward diffeomorphisms indicates performance in deep nets
• Neural Tangent Kernel Maximum Mean Discrepancy
• The impact of memory on learning sequence-to-sequence tasks
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions
• Deep Networks Provably Classify Data on Curves