Randomized Quasi-Gauss--Newton Methods for Solving General Nonlinear Equations

Abstract

This paper considers the local convergence for solving general nonlinear equations. We establish randomized quasi-Gauss--Newton methods based on the approximation of the Gram matrix, addressing both the underdetermined and the overdetermined settings. For the underdetermined case, we show that our methods achieve local superlinear convergence to the optimal solution. For the overdetermined case, we show that our methods achieve local condition-number-free convergence to the stationary point of the nonlinear least-square formulation of the problem. In contrast, existing quasi-Newton methods mostly focus on square systems and additionally require the initial Jacobian estimate to be sufficiently close to the exact one.

The conference version was in the proceedings of NeurIPS 2022, where we focus on the special case $n=d$. The results that are generalized to general nonlinear equations were presented at ICCOPT 2025 and ICOTA 2026