# Incremental Gauss--Newton Methods with Superlinear Convergence Rates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 67 references that are in the map.
- First posted on arXiv 3 Jul 2024.

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

- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Practical Gauss-Newton Optimisation for Deep Learning](https://mlsanity.com/paper/1706.03662/) (2017)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization](https://mlsanity.com/paper/1901.05134/) (2019)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence](https://mlsanity.com/paper/2302.08580/) (2023)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [A globally convergent incremental Newton method](https://mlsanity.com/paper/1410.5284/) (2014)
- [A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization](https://mlsanity.com/paper/2103.15993/) (2021)
- [Communication Efficient Distributed Newton Method with Fast Convergence Rates](https://mlsanity.com/paper/2305.17945/) (2023)
- [Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equations](https://mlsanity.com/paper/2109.01974/) (2021)
- [Greedy and Random Broyden's Methods with Explicit Superlinear Convergence Rates in Nonlinear Equations](https://mlsanity.com/paper/2110.08572/) (2021)
- [Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates](https://mlsanity.com/paper/2402.02359/) (2024)
- [Sharpened Lazy Incremental Quasi-Newton Method](https://mlsanity.com/paper/2305.17283/) (2023)

## Abstract (arXiv)

This paper addresses the challenge of solving large-scale nonlinear equations with H"older continuous Jacobians. We introduce a novel Incremental Gauss--Newton (IGN) method within explicit superlinear convergence rate, which outperforms existing methods that only achieve linear convergence rate. In particular, we formulate our problem by the nonlinear least squares with finite-sum structure, and our method incrementally iterates with the information of one component in each round. We also provide a mini-batch extension to our IGN method that obtains an even faster superlinear convergence rate. Furthermore, we conduct numerical experiments to show the advantages of the proposed methods.