Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate that is dependent on the condition number of the problem. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework, which results in the condition-number-free local superlinear convergence rate. Furthermore, we can boost our method by applying the block update on the Hessian approximation, which leads to an even faster local convergence rate. The numerical experiments show the proposed methods significantly outperform the baseline methods.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate
The problem of minimizing an objective that can be written as the sum of a set of $n$ smooth and strongly convex functions is considered. The Incremental Quasi-Newton (IQN) method proposed here belongs to the family of s…
Sharpened Lazy Incremental Quasi-Newton Method
The problem of minimizing the sum of $n$ functions in $d$ dimensions is ubiquitous in machine learning and statistics. In many applications where the number of observations $n$ is large, it is necessary to use incrementa…
Second-order methodsGreedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
In this paper, we follow Rodomanov and Nesterov’s work to study quasi-Newton methods. We focus on the common SR1 and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence rates. First, ba…
Incremental Gauss--Newton Methods with Superlinear Convergence Rates
This paper addresses the challenge of solving large-scale nonlinear equations with H\"older continuous Jacobians. We introduce a novel Incremental Gauss--Newton (IGN) method within explicit superlinear convergence rate, …
Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence
Quasi-Newton algorithms are among the most popular iterative methods for solving unconstrained minimization problems, largely due to their favorable superlinear convergence property. However, existing results for these a…