# Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time

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

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 95 references that are in the map.
- First posted on arXiv 14 Dec 2021.

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [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)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [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 Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Practical Gauss-Newton Optimisation for Deep Learning](https://mlsanity.com/paper/1706.03662/) (2017)
- [On the linearity of large non-linear models: when and why the tangent kernel is constant](https://mlsanity.com/paper/2010.01092/) (2020)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [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)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [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)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)

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

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [ReLU Strikes Back: Exploiting Activation Sparsity in Large Language Models](https://mlsanity.com/paper/2310.04564/) (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)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trick](https://mlsanity.com/paper/2307.02419/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (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)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [A Sublinear Adversarial Training Algorithm](https://mlsanity.com/paper/2208.05395/) (2022)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (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)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [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)

## Abstract (arXiv)

We consider the problem of training a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-parametrization, the network width m is much larger than the data dimension d and the number of training samples n (m=poly(n,d)), which induces a prohibitive large weight matrix W∈ ℝm× m per layer. Naively, one has to pay O(m2) time to read the weight matrix and evaluate the neural network function in both forward and backward computation. In this work, we show how to reduce the training cost per iteration. Specifically, we propose a framework that uses m2 cost only in the initialization phase and achieves a truly subquadratic cost per iteration in terms of m, i.e., m2-Omega(1) per iteration. Our result has implications beyond standard over-parametrization theory, as it can be viewed as designing an efficient data structure on top of a pre-trained large model to further speed up the fine-tuning process, a core procedure to deploy large language models (LLM).