论文标题
基于加速级别的广义levenberg-甲骨文的方法，具有Oracle复杂性绑定和局部二次收敛性
Accelerated-gradient-based generalized Levenberg--Marquardt method with oracle complexity bound and local quadratic convergence
论文作者
论文摘要
最小化凸函数和复合函数的总和出现在各个字段中。已开发出用于此类优化问题的广义Levenberg--Marquardt（LM）方法，也称为Prox-Linear方法。该方法迭代地用阻尼项求解了强烈凸出的子问题。这项研究提出了一种新的通用LM方法，用于通过平滑的复合函数解决问题。该方法享有三种理论保证：迭代复杂性结合，甲骨文复杂性结合以及在Hölderian生长条件下的局部收敛。局部收敛结果包括在二次生长条件下的局部二次收敛。这是第一个将最小二乘问题的经典结果扩展到一般平滑复合函数的经典结果。此外，这是第一个在标准假设下具有Oracle复杂性和局部二次收敛性的LM方法。这些结果是通过仔细控制阻尼参数并通过配备有特定终止条件的加速近端梯度方法来解决子问题。实验结果表明，该方法在几种情况下的实践中表现良好，包括与神经网络和非负矩阵分解的分类。
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ö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.
