mlsanityData to 14 Oct 2026

Scaling Neural Tangent Kernels via Sketching and Random Features

arXiv 2106.07880 ↗First posted 15 Jun 2021cs.LG cs.CV cs.DScited by 32

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). Builds on 30 of its 44 references that are in the map. First posted on arXiv 15 Jun 2021.

Builds on

30 of 44 references.

References · 30

  1. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  2. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  3. 2018On Lazy Training in Differentiable Programmingcited by 675
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2017Deep Neural Networks as Gaussian Processescited by 622
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  8. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  9. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  10. 2018Gaussian Process Behaviour in Wide Deep Neural Networkscited by 317
  11. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  12. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
18 more
  1. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  2. 2018Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processescited by 167
  3. 2016Generalization Properties of Learning with Random Featurescited by 164
  4. 2019Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivationcited by 149
  5. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  6. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  7. 2018Deep Convolutional Networks as shallow Gaussian Processescited by 138
  8. 2020Infinite attention: NNGP and NTK for deep attention networkscited by 121
  9. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  10. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  11. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  12. 2020Implicit Regularization of Random Feature Modelscited by 54
  13. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  14. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  15. 2020Predicting Training Time Without Trainingcited by 22
  16. 2020Near Input Sparsity Time Kernel Embeddings via Adaptive Samplingcited by 12
  17. 2020Experimental Design for Overparameterized Learning with Application to Single Shot Deep Active Learningcited by 9
  18. 2019Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrixcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 8; 2023: 9; 2024: 4; 2025: 4; 2026: 4.

32 papers.

Sort:

By area:

  1. 2021Dataset Distillation with Infinitely Wide Convolutional Networkscited by 218
  2. 2022Efficient Dataset Distillation Using Random Feature Approximationcited by 111
  3. 2022A Framework and Benchmark for Deep Batch Active Learning for Regressioncited by 49
  4. 2021Deep Active Learning by Leveraging Training Dynamicscited by 32
  5. 2022Fast Neural Kernel Embeddings for General Activationscited by 18
  6. 2022Few-shot Backdoor Attacks via Neural Tangent Kernelscited by 15
  7. 2023Tanimoto Random Features for Scalable Molecular Machine Learningcited by 15
  8. 2023Understanding Reconstruction Attacks with the Neural Tangent Kernel and Dataset Distillationcited by 14
  9. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  10. 2023Kernel Regression with Infinite-Width Neural Networks on Millions of Examplescited by 9
  11. 2022Random Gegenbauer Features for Scalable Kernel Methodscited by 6
  12. 2022Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Timecited by 6
20 more
  1. 2023Fast-NTK: Parameter-Efficient Unlearning for Large-Scale Modelscited by 5
  2. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  3. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  4. 2025Fast Generalized Neural Tangent Kernel Statistics via Trace Estimationcited by 3
  5. 2022Single-level Adversarial Data Synthesis based on Neural Tangent Kernelscited by 2
  6. 2025Convergence and Sketching-Based Efficient Computation of Neural Tangent Kernel Weights in Physics-Based Losscited by 2
  7. 2021Empirical analysis of representation learning and exploration in neural kernel banditscited by 1
  8. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  9. 2024Learning Expressive Random Feature Models via Parametrized Activationscited by 1
  10. 2025On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functionscited by 1
  11. 2026Efficient Analysis of the Distilled Neural Tangent Kernelcited by 1
  12. 2026Spectral Reach: Understanding Neural Scaling as Progress into the Spectral Tailcited by 1
  13. 2022Near Optimal Reconstruction of Spherical Harmonic Expansionscited by 0
  14. 2023A Simple Algorithm For Scaling Up Kernel Methodscited by 0
  15. 2023Controlled Descent Trainingcited by 0
  16. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  17. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  18. 2024Kernel Approximation using Analog In-Memory Computingcited by 0
  19. 2026Improving TensorSketch Using Complex Random Variablescited by 0
  20. 2026Kernel Reboot: Breaking the Boundaries of Neural Tangent Kernels for Neural Fieldscited by 0