An Enhanced Levenberg–Marquardt Method via Gram Reduction

Chengchang Liu, Luo Luo, John C.S. Lui · 2024

Read An Enhanced Levenberg–Marquardt Method via Gram Reduction by Chengchang Liu, Luo Luo, John C.S. Lui (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08561.txt.

Introduction

Chengchang Liu, Luo Luo, and John Lui speed up a workhorse method for solving systems of nonlinear equations. The Levenberg-Marquardt method is a standard solver, but its cost grows steeply with problem size because it rebuilds a costly matrix product at every step. Their Gram-reduced variant refreshes that product, the Gram matrix of the Jacobian, only every m steps instead.

The method converges globally without line searches or sub-problem solving, a first for this family. The authors prove an iteration bound that beats the known cost of existing versions, and under a non-degeneracy assumption the method converges superlinearly near a solution. Experiments on scientific computing and machine learning problems confirmed the efficiency gains in practice.

Catalog record

CREATORChengchang Liu, Luo Luo, John C.S. Lui
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08561

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Enhanced Levenberg–Marquardt Method via Gram Reduction Chengchang Liu, Luo Luo, John C.S. Lui Abstract This paper studied the problem of solving the system of nonlinear equations 𝐅 ⁡ ( 𝐱 ) = 𝟎 {\bf F}({{\bf x}})={\bf{0}} , where 𝐅 : ℝ d → ℝ d {\bf F}:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d} . We propose Gram-Reduced Levenberg–Marquardt method which updates the Gram matrix 𝐉 ​ ( ⋅ ) ⊤ ​ 𝐉 ​ ( ⋅ ) {\bf J}(\cdot)^{\top}{\bf J}(\cdot) in every m m iterations, where 𝐉 ⁡ ( ⋅ ) {\bf J}(\cdot) is the Jacobian of 𝐅 ⁡ ( ⋅ ) {\bf 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 𝒪 ⁡ ( m 2 + m − 0.5 ​ ϵ − 2.5 ) {\mathcal{O}}(m^{2}+m^{-0.5}\epsilon^{-2.5}) iterations to find an ϵ \epsilon -stationary point of 1 2 ​ ‖ 𝐅 ⁡ ( ⋅ ) ‖ 2 \frac{1}{2}\|{\bf F}(\cdot)\|^{2} , which leads to overall computation cost of 𝒪 ⁡ ( d 3 ​ ϵ − 1 + d 2 ​ ϵ − 2 ) {\mathcal{O}}(d^{3}\epsilon^{-1}+d^{2}\epsilon^{-2}) by taking m = Θ ⁡ ( ϵ − 1 ) m=\Theta(\epsilon^{-1}) . Our results are strictly better than the cost of 𝒪 ⁡ ( d 3 ​ ϵ − 2 ) {\mathcal{O}}(d^{3}\epsilon^{-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. 1 Introduction We consider solving the system of nonlinear equations \displaystyle{\bf F}({\bf x})={\bf 0}, (1) where {\bf x}\in{\mathbb{R}}^{d} and {\bf F}({\bf x})\triangleq[F_{1}({\bf x}),\dots,F_{d}({\bf x})]^{\top}\!:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d} with differentiable F_{i}({{\bf x}}):{\mathbb{R}}^{d}\to{\mathbb{R}} for all i\in[d] . This problem can also be reformulated by the nonlinear least-square problem: \displaystyle\min_{{\bf x}\in{\mathbb{R}}^{d}}\phi({\bf x})\triangleq\frac{1}{2}\|{\bf F}({\bf x})\|^{2}. (2) Solving nonlinear equations is one of the most fundamental problems in scientific computing [ 36 , 52 ] . It has wide applications in machine learning [ 13 , 8 , 4 , 29 ] , control system [ 7 ] , data assimilation [ 44 ] , and game theory [ 19 , 40 ] . First-order methods are popular to solve nonlinear equations. Specifically, one can perform the gradient descent on problem ( 2 ), that is \displaystyle\begin{split}{\bf x}_{t+1}={\bf x}_{t}-\eta\nabla\phi({\bf x}_{t})={\bf x}_{t}-\eta{\bf J}({\bf x}_{t})^{\top}{\bf F}({\bf x}_{t}),\end{split} (3) where \eta>0 is the step-size, \phi({\bf x}_{t})={\bf J}({\bf x}_{t})^{\top}{\bf F}({\bf x}_{t}) and {\bf J}(\cdot)\triangleq[\nabla F_{1}(\cdot),\dots,\nabla F_{d}(\cdot)]^{\top}\in{\mathbb{R}}^{d\times d} is the Jacobian of {\bf F}(\cdot) . The iteration scheme ( 3 ) takes {\mathcal{O}}(d^{2}) flops in general. By assuming the Lipschitz continuity on \nabla\phi(\cdot) , it requires {\mathcal{O}}(\epsilon^{-2}) iterations to find an \epsilon -stationary point of \phi(\cdot) , then the overall computation cost is {\mathcal{O}}(d^{2}\epsilon^{-2}) . Gauss–Newton methods [ 5 , 39 ] consider the estimation \nabla^{2}\phi(\cdot)\approx{\bf J}(\cdot)^{\top}{\bf J}(\cdot) and establish the iteration \displaystyle{\bf x}_{t+1}={\bf x}_{t}-\big({\bf J}({\bf x}_{t})^{\top}{\bf J}({\bf x}_{t})\big)^{\dagger}{\bf J}({{\bf x}}_{t})^{\top}{\bf F}({\bf x}_{t}) with local superlinear convergence, while such needs the flops of {\mathcal{O}}(d^{3}) to compute the matrix (pseudo) inverse. Recently, Liu and Luo [30] introduced Broyden family updates [ 41 , 28 ] to estimate {\bf J}(\cdot)^{\top}{\bf J}(\cdot) , which leads to the Quasi-Newton methods with local superlinear convergence and reduces the computation cost in per iteration to {\mathcal{O}}(d^{2}) flops. However, both Gauss–Newton method and its quasi-Newton variants lack global convergence guarantees. In this paper, we are interested in Levenberg–Marquardt (LM) methods [ 26 , 34 ] , which iterates according to \displaystyle{\bf x}_{t+1}={\bf x}_{t}-\big({\bf J}({\bf x}_{t})^{\top}{\bf J}({\bf x}_{t})+\lambda_{t}{\bf I}\big)^{-1}{\bf J}({\bf x}_{t})^{\top}{\bf F}({\bf x}_{t}), (4) where \lambda_{t}>0 is the regularization parameter. This method globalizes the Gauss–Newton iteration, and also maintains local superlinear convergence by properly choosing the regularization term \lambda_{t} [ 47 , 18 ] . However, the iteration scheme ( 4 ) takes {\mathcal{O}}(d^{3}) flops since it contains matrix inversion like Gauss–Newton update. Moreover, the upper bound on iteration numbers for existing global convergent LM methods are no better than {\mathcal{O}}(\epsilon^{-2}) [ 45 , 53 , 20 , 6 , 43 ] , which makes the total computation cost be {\mathcal{O}}(d^{3}\epsilon^{-2}) . Besides, these methods require the line-search step or solving trust-region sub-problem [ 50 ] to achieve a descent direction, which leads their implementation be complicated. Recently, Mishchenko [35] proposed an adaptive LM method without any line-search step nor sub-problem solver, which determine the regularization term by \displaystyle\lambda_{t}\propto\sqrt{\|{\bf J}({\bf x}_{t})^{\top}{\bf F}({\bf x}_{t})\|}\,. (5) This method can find an \epsilon -stationary within at most \tilde{{\mathcal{O}}}(\epsilon^{-2.5}) iterations under the cubic-growth condition, which is worse than line-search or trust-region based LM methods. Furthermore, its overall computation cost {\mathcal{O}}(d^{3}\epsilon^{-2.5}) is worse than classical LM methods, and the existence of its local superlinear convergence is unknown. Build upon this, there raises a natural question that: Can we design a computation efficient and globally convergent LM method with local superlinear convergence? We give an affirmative answer to the above question by proposing the Gram-Reduced Levenberg–Marquardt (GRLM) method. Instead of existing LM methods that compute the Gram matrix {\bf J}({\bf x}_{t})^{\top}{\bf J}({\bf x}_{t}) at every iteration, our method only updates {\bf J}(\cdot)^{\top}{\bf J}(\cdot) at the snapshot point and reuse it in next m iterations. The update of our method can be formulated by \displaystyle\begin{split}\!\!{\bf x}_{t+1}\!=\!{\bf x}_{t}\!-\!\Big(\!{\bf J}\big({{\bf x}}_{\pi(t)}\big)\!^{\top}{\bf J}\big({{\bf x}}_{\pi(t)}\big)\!+\!\lambda_{t}{\bf I}\Big)^{-1}\!{\bf J}({\bf x}_{t})\!^{\top}\!{\bf F}({\bf x}_{t}),\end{split} (6) where \pi(t)\triangleq m{\left\lfloor t/m\right\rfloor} and \lambda_{t} is chosen according to equation ( 5 ). Note that the scheme ( 6 ) only needs to compute the matrix {\bf J}({{\bf x}}_{\pi(t)})^{\top}{\bf J}({{\bf x}}_{\pi(t)}) in the case of t\equiv 0~({\rm mod}~m) , which significantly reduces the time of computing the Gram matrix and leads to a better algorithmic complexity. For the global behavior, our method takes at most overall computation cost of {\mathcal{O}}(d^{3}\epsilon^{-1}+d^{2}\epsilon^{-2}) to find an \epsilon -stationary point under the cubic-growth condition, which improves the results of {\mathcal{O}}(d^{3}\epsilon^{-2}) of existing LM methods. For the local behavior, our method has the superlinear rate when the solution has non-degenerate Jacobian, which goes beyond the theory of Mishchenko [35] . We summarize the main theoretical results of GRLM and related work in Table 1 . Paper Organization The remainder of the paper is organized as follows. In Section 2 and 3 , we introduce preliminaries and related work respectively. In Section 4 , we provide the Algorithm details and convergence analysis of GRLM. In Section 5 , we validate our methods by numerical experiments. We conclude our work and discuss the future directions in Section 6 . Table 1: We summarize the globally convergent algorithms for solving the nonlinear equations by their total computation cost for finding the \epsilon -stationary point of \phi(\cdot) ( Globally Computation Cost ), if they enjoy local superlinear rates ( Local Superlinear ), and if they are line-search free ( Line-search Free ). Method Globally Computation Cost Local superlinear Line-search Free References Gradient Descent {\mathcal{O}}(d^{2}\epsilon^{-2}) ✗ ✓ Nesterov [38] Levernberg–Marquardt (v1) {{\mathcal{O}}(d^{3}\epsilon^{-2}}\log(\epsilon^{-1})) ✓ ✗ Bergou et al. [6] Levernberg–Marquardt (v2) {{\mathcal{O}}(d^{3}\epsilon^{-2.5}\log(\epsilon^{-1}))} {\dagger} ✗ {\ddagger} ✓ Mishchenko [35] GRLM (ours) {{\mathcal{O}}(d^{2}\epsilon^{-2}+d^{3}\epsilon^{-1})} ✓ ✓ Algorithm 1 {\dagger} This results can be improved to {\mathcal{O}}(d^{3}\epsilon^{-2.5}) by using our analysis framework. We present a discussion in Remark 10 . {\ddagger} Our analysis can also provide the local superlinear convergence rate for Levernberg–Marquardt (v2), which is not

Read the complete text