# Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 100 references that are in the map.
- First posted on arXiv 25 Nov 2022.

## Builds on (most cited first, 30 of 49)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [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)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks](https://mlsanity.com/paper/1905.10961/) (2019)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound](https://mlsanity.com/paper/1906.03593/) (2019)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems](https://mlsanity.com/paper/1905.11675/) (2019)
- [Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality](https://mlsanity.com/paper/2002.06668/) (2020)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Generalized Leverage Score Sampling for Neural Networks](https://mlsanity.com/paper/2009.09829/) (2020)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)

## Built on by (most cited first, 29 of 29)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [A Unified Scheme of ResNet and Softmax](https://mlsanity.com/paper/2309.13482/) (2023)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation](https://mlsanity.com/paper/2502.00500/) (2025)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent](https://mlsanity.com/paper/2310.11291/) (2023)
- [Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression](https://mlsanity.com/paper/2311.15390/) (2023)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Fast and Efficient Matching Algorithm with Deadline Instances](https://mlsanity.com/paper/2305.08353/) (2023)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study](https://mlsanity.com/paper/2410.11279/) (2024)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK](https://mlsanity.com/paper/2301.00327/) (2023)

## Abstract (arXiv)

Over the last decade, deep neural networks have transformed our society, and they are already widely applied in various machine learning applications. State-of-art deep neural networks are becoming larger in size every year to deliver increasing model accuracy, and as a result, model training consumes substantial computing resources and will only consume more in the future. Using current training methods, in each iteration, to process a data point x ∈ ℝd in a layer, we need to spend Theta(md) time to evaluate all the m neurons in the layer. This means processing the entire layer takes Theta(nmd) time for n data points. Recent work [Song, Yang and Zhang, NeurIPS 2021] reduces this time per iteration to o(nmd), but requires exponential time to preprocess either the data or the neural network weights, making it unlikely to have practical usage. In this work, we present a new preprocessing method that simply stores the weight-data correlation in a tree data structure in order to quickly, dynamically detect which neurons fire at each iteration. Our method requires only O(nmd) time in preprocessing and still achieves o(nmd) time per iteration. We complement our new algorithm with a lower bound, proving that assuming a popular conjecture from complexity theory, one could not substantially speed up our algorithm for dynamic detection of firing neurons.