An Enhanced Levenberg-Marquardt Method via Gram Reduction

This paper studied the problem of solving the system of nonlinear equations F(x) = 0, where F : R d → R d . We propose Gram-Reduced Levenberg-Marquardt method which updates the Gram matrix J(•) ⊤ J(•) in every m iterations, where J(•) is the Jacobian of 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(m 2 + m -0.5 ϵ -2.5 ) iterations to find an ϵ-stationary point of 1 2 ∥F(•)∥ 2 , which leads to overall computation cost of O(d 3 ϵ -1 + d 2 ϵ -2 ) by taking m = Θ(ϵ -1 ). Our results are strictly better than the cost of O(d 3 ϵ -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.