Scaling Neural Tangent Kernels via Sketching and Random Features
arXiv:2106.07880
Abstract
The Neural Tangent Kernel (NTK) characterizes the behavior of infinitely-wide neural networks trained under least squares loss by gradient descent. Recent works also report that NTK regression can outperform finitely-wide neural networks trained on small-scale datasets. However, the computational complexity of kernel methods has limited its use in large-scale learning tasks. To accelerate learning with NTK, we design a near input-sparsity time approximation algorithm for NTK, by sketching the polynomial expansions of arc-cosine kernels: our sketch for the convolutional counterpart of NTK (CNTK) can transform any image using a linear runtime in the number of pixels. Furthermore, we prove a spectral approximation guarantee for the NTK matrix, by combining random features (based on leverage score sampling) of the arc-cosine kernels with a sketching algorithm. We benchmark our methods on various large-scale regression and classification tasks and show that a linear regressor trained on our CNTK features matches the accuracy of exact CNTK on CIFAR-10 dataset while achieving 150x speedup.
arXiv commentThis is a merger of arXiv:2104.01351, arXiv:2104.00415
References in corpus (17)
- 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
- 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
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
- Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
- Recursive Sampling for the Nyström Method
- Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
- Infinite attention: NNGP and NTK for deep attention networks
- Predicting Training Time Without Training
- Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix