mlsanityData to 7 Oct 2026

Learning with Neural Tangent Kernels in Near Input Sparsity Time

arXiv 2104.00415 ↗First posted 1 Apr 2021cs.LG cs.AI cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 36 references that are in the map. First posted on arXiv 1 Apr 2021.

Builds on

24 of 36 references.

References · 24

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2017Deep Neural Networks as Gaussian Processescited by 617
  5. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  8. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  9. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  10. 2018Gaussian Process Behaviour in Wide Deep Neural Networkscited by 314
  11. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  12. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
12 more
  1. 2018Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processescited by 164
  2. 2019Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivationcited by 146
  3. 2018Deep Convolutional Networks as shallow Gaussian Processescited by 137
  4. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  5. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  6. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  7. 2019Width Provably Matters in Optimization for Deep Linear Neural Networkscited by 52
  8. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  9. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  10. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  11. 2020Near Input Sparsity Time Kernel Embeddings via Adaptive Samplingcited by 12
  12. 2020Scaling up Kernel Ridge Regression via Locality Sensitive Hashingcited by 8

Built on by

Not cited yet.