# Efficient NTK using Dimensionality Reduction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 10 Oct 2022.

## Builds on (most cited first, 24 of 24)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [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)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [The Recurrent Neural Tangent Kernel](https://mlsanity.com/paper/2006.10246/) (2020)
- [Initialization and Regularization of Factorized Neural Layers](https://mlsanity.com/paper/2105.01029/) (2021)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Data-Independent Neural Pruning via Coresets](https://mlsanity.com/paper/1907.04018/) (2019)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Coresets for Robust Training of Neural Networks against Noisy Labels](https://mlsanity.com/paper/2011.07451/) (2020)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [On Coresets For Regularized Regression](https://mlsanity.com/paper/2006.05440/) (2020)
- [Streaming Coresets for Symmetric Tensor Factorization](https://mlsanity.com/paper/2006.01225/) (2020)
- [Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice](https://mlsanity.com/paper/2007.08864/) (2020)
- [Random Features for the Neural Tangent Kernel](https://mlsanity.com/paper/2104.01351/) (2021)
- [Coresets for Clustering with Missing Values](https://mlsanity.com/paper/2106.16112/) (2021)

## Abstract (arXiv)

Recently, neural tangent kernel (NTK) has been used to explain the dynamics of learning parameters of neural networks, at the large width limit. Quantitative analyses of NTK give rise to network widths that are often impractical and incur high costs in time and energy in both training and deployment. Using a matrix factorization technique, we show how to obtain similar guarantees to those obtained by a prior analysis while reducing training and inference resource costs. The importance of our result further increases when the input points' data dimension is in the same order as the number of input points. More generally, our work suggests how to analyze large width networks in which dense linear layers are replaced with a low complexity factorization, thus reducing the heavy dependence on the large width.