Accelerated-gradient-based generalized Levenberg-Marquardt method with oracle complexity bound and local quadratic convergence

• 成果类型: Article
• 署名作者: Marumo, Naoki; Okuno, Takayuki; Takeda, Akiko
• 署名单位: University of Tokyo; Seikei University; RIKEN
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02154-4
• 发表日期: 2025
• 页码: 771-822
• 关键词: gauss-newton method; trust-region method; Nonlinear equations; optimization; algorithm; systems

摘要

Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg-Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a H & ouml;lderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.