# Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [Improved architectures and training algorithms for deep operator networks](https://mlsanity.com/paper/2110.01654/) (2021)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping](https://mlsanity.com/paper/2110.01765/) (2021)
- [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)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [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)
- [Credit Assignment in Neural Networks through Deep Feedback Control](https://mlsanity.com/paper/2106.07887/) (2021)
- [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)
- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [On the Parameterization of Second-Order Optimization Effective Towards the Infinite Width](https://mlsanity.com/paper/2312.12226/) (2023)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [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)
- [Achieving High Accuracy with PINNs via Energy Natural Gradients](https://mlsanity.com/paper/2302.13163/) (2023)
- [Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum](https://mlsanity.com/paper/2307.14531/) (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)
- [Appearance of Random Matrix Theory in Deep Learning](https://mlsanity.com/paper/2102.06740/) (2021)
- [TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion](https://mlsanity.com/paper/2106.03947/) (2021)
- [ANaGRAM: A Natural Gradient Relative to Adapted Model for efficient PINNs learning](https://mlsanity.com/paper/2412.10782/) (2024)
- [Provable Regret Bounds for Deep Online Learning and Control](https://mlsanity.com/paper/2110.07807/) (2021)
- [Rethinking Gauss-Newton for learning over-parameterized models](https://mlsanity.com/paper/2302.02904/) (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)
- [SCORE: Approximating Curvature Information under Self-Concordant Regularization](https://mlsanity.com/paper/2112.07344/) (2021)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Regularized Gauss-Newton for Optimizing Overparameterized Neural Networks](https://mlsanity.com/paper/2404.14875/) (2024)

## Abstract (arXiv)

First-order methods such as stochastic gradient descent (SGD) are currently the standard algorithm for training deep neural networks. Second-order methods, despite their better convergence rate, are rarely used in practice due to the prohibitive computational cost in calculating the second-order information. In this paper, we propose a novel Gram-Gauss-Newton (GGN) algorithm to train deep neural networks for regression problems with square loss. Our method draws inspiration from the connection between neural network optimization and kernel regression of neural tangent kernel (NTK). Different from typical second-order methods that have heavy computational cost in each iteration, GGN only has minor overhead compared to first-order methods such as SGD. We also give theoretical results to show that for sufficiently wide neural networks, the convergence rate of GGN is quadratic. Furthermore, we provide convergence guarantee for mini-batch GGN algorithm, which is, to our knowledge, the first convergence result for the mini-batch version of a second-order method on overparameterized neural networks. Preliminary experiments on regression tasks demonstrate that for training standard networks, our GGN algorithm converges much faster and achieves better performance than SGD.