An Enhanced Levenberg--Marquardt Method via Gram Reduction

Abstract

This paper studied the problem of solving the system of nonlinear equations $\mathbf{F}(\mathbf{x})=0$, where $\mathbf{F}:{\mathbb{R}}^d\to {\mathbb{R}}^d$. We propose Gram-Reduced Levenberg--Marquardt method which updates the Gram matrix $\mathbf{J}(\cdot {)}^{\top }\mathbf{J}(\cdot )$ in every $m$ iterations, where $\mathbf{J}(\cdot )$ is the Jacobian of $\mathbf{F}(\cdot )$. Our method has a global convergence guarantee without relying on any step of line-search or solving sub-problems. We prove our method takes at most $\mathcal{O}(m^2+m^{-0.5}\hat{I}{\mu }^{-2.5})$ iterations to find an $\hat{I}\mu$-stationary point of $\frac{1}{2}\Vert \mathbf{F}(\cdot ){\Vert }^2$, which leads to overall computation cost of $\mathcal{O}(d^3\hat{I}{\mu }^{-1}+d^2\hat{I}{\mu }^{-2})$ by taking $m=\hat{I}˜(\hat{I}{\mu }^{-1})$. Our results are strictly better than the cost of $\mathcal{O}(d^3\hat{I}{\mu }^{-2})$ for existing Levenberg--Marquardt methods. We also show the proposed method enjoys local superlinear convergence rate under the non-degenerate assumption. We provide experiments on real-world applications in scientific computing and machine learning to validate the efficiency of the proposed methods.

Accepted in AAAI 2025