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
| CREATOR | Chengchang Liu, Luo Luo, John C.S. Lui |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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