Learning with Neural Tangent Kernels in Near Input Sparsity Time

Abstract

The Neural Tangent Kernel (NTK) characterizes the behavior of infinitely wide neural nets trained under least squares loss by gradient descent. However, despite its importance, the super-quadratic runtime of kernel methods limits the use of NTK in large-scale learning tasks. To accelerate kernel machines with NTK, we propose a near input sparsity time algorithm that maps the input data to a randomized low-dimensional feature space so that the inner product of the transformed data approximates their NTK evaluation. Our transformation works by sketching the polynomial expansions of arc-cosine kernels. Furthermore, we propose a feature map for approximating the convolutional counterpart of the NTK, which can transform any image using a runtime that is only linear in the number of pixels. We show that in standard large-scale regression and classification tasks a linear regressor trained on our features outperforms trained Neural Nets and Nystrom approximation of NTK kernel.

References in corpus (11)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Neural Networks as Gaussian Processes
• On Exact Computation with an Infinitely Wide Neural Net
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• 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
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• On the Similarity between the Laplace and Neural Tangent Kernels