# Scaling Neural Tangent Kernels via Sketching and Random Features

arXiv: https://arxiv.org/abs/2106.07880 · HTML: https://mlsanity.com/paper/2106.07880/

## 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 (most cited first, 30 of 30)

- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation](https://mlsanity.com/paper/1902.04760/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Implicit Regularization of Random Feature Models](https://mlsanity.com/paper/2002.08404/) (2020)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Generalized Leverage Score Sampling for Neural Networks](https://mlsanity.com/paper/2009.09829/) (2020)
- [Predicting Training Time Without Training](https://mlsanity.com/paper/2008.12478/) (2020)
- [Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling](https://mlsanity.com/paper/2007.03927/) (2020)
- [Experimental Design for Overparameterized Learning with Application to Single Shot Deep Active Learning](https://mlsanity.com/paper/2009.12820/) (2020)
- [Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix](https://mlsanity.com/paper/1905.11616/) (2019)

## Built on by (most cited first, 30 of 32)

- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [A Framework and Benchmark for Deep Batch Active Learning for Regression](https://mlsanity.com/paper/2203.09410/) (2022)
- [Deep Active Learning by Leveraging Training Dynamics](https://mlsanity.com/paper/2110.08611/) (2021)
- [Fast Neural Kernel Embeddings for General Activations](https://mlsanity.com/paper/2209.04121/) (2022)
- [Few-shot Backdoor Attacks via Neural Tangent Kernels](https://mlsanity.com/paper/2210.05929/) (2022)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [Understanding Reconstruction Attacks with the Neural Tangent Kernel and Dataset Distillation](https://mlsanity.com/paper/2302.01428/) (2023)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Kernel Regression with Infinite-Width Neural Networks on Millions of Examples](https://mlsanity.com/paper/2303.05420/) (2023)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)
- [Fast-NTK: Parameter-Efficient Unlearning for Large-Scale Models](https://mlsanity.com/paper/2312.14923/) (2023)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Fast Generalized Neural Tangent Kernel Statistics via Trace Estimation](https://mlsanity.com/paper/2511.10796/) (2025)
- [Single-level Adversarial Data Synthesis based on Neural Tangent Kernels](https://mlsanity.com/paper/2204.04090/) (2022)
- [Convergence and Sketching-Based Efficient Computation of Neural Tangent Kernel Weights in Physics-Based Loss](https://mlsanity.com/paper/2511.15530/) (2025)
- [Empirical analysis of representation learning and exploration in neural kernel bandits](https://mlsanity.com/paper/2111.03543/) (2021)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Learning Expressive Random Feature Models via Parametrized Activations](https://mlsanity.com/paper/2411.19468/) (2024)
- [On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions](https://mlsanity.com/paper/2510.15327/) (2025)
- [Efficient Analysis of the Distilled Neural Tangent Kernel](https://mlsanity.com/paper/2602.11320/) (2026)
- [Spectral Reach: Understanding Neural Scaling as Progress into the Spectral Tail](https://mlsanity.com/paper/2605.31244/) (2026)
- [Near Optimal Reconstruction of Spherical Harmonic Expansions](https://mlsanity.com/paper/2202.12995/) (2022)
- [A Simple Algorithm For Scaling Up Kernel Methods](https://mlsanity.com/paper/2301.11414/) (2023)
- [Controlled Descent Training](https://mlsanity.com/paper/2303.09216/) (2023)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Kernel Approximation using Analog In-Memory Computing](https://mlsanity.com/paper/2411.03375/) (2024)

## 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.