An Enhanced Levenberg--Marquardt Method via Gram Reduction

This paper studied the problem of solving the system of nonlinear equations bf F(bf x)=bf 0, where bf F:mathbb Rd→mathbb Rd. We propose Gram-Reduced Levenberg--Marquardt method which updates the Gram matrix bf J(·)^topbf J(·) in every m iterations, where bf J(·) is the Jacobian of bf F(·). 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 O(m2+m-0.5ε-2.5) iterations to find an ε-stationary point of frac12|bf F(·)|2, which leads to overall computation cost of O(d3ε-1+d2ε-2) by taking m=Theta(ε-1). Our results are strictly better than the cost of O(d3ε-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.