Rates of superlinear convergence for classical quasi-Newton methods
Anton Rodomanov, Yurii Nesterov
Abstract
Abstract We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $$(\frac{n L^2}{\mu ^2 k})^{k/2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow> <mml:msup> <mml:mi>μ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>k</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:math> and $$(\frac{n L}{\mu k})^{k/2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>nL</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>μ</mml:mi> <mml:mi>k</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:math> respectively, where k is the iteration counter, n is the dimension of the problem, $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> is the strong convexity parameter, and L is the Lipschitz constant of the gradient.