Superfast Second-Order Methods for Unconstrained Convex Optimization
Yurii Nesterov
Abstract
Abstract In this paper, we present new second-order methods with convergence rate $$O\left( k^{-4}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> </mml:mfenced> </mml:mrow> </mml:math> , where k is the iteration counter. This is faster than the existing lower bound for this type of schemes (Agarwal and Hazan in Proceedings of the 31st conference on learning theory, PMLR, pp. 774–792, 2018; Arjevani and Shiff in Math Program 178(1–2):327–360, 2019), which is $$O\left( k^{-7/2} \right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>7</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mfenced> </mml:mrow> </mml:math> . Our progress can be explained by a finer specification of the problem class. The main idea of this approach consists in implementation of the third-order scheme from Nesterov (Math Program 186:157–183, 2021) using the second-order oracle. At each iteration of our method, we solve a nontrivial auxiliary problem by a linearly convergent scheme based on the relative non-degeneracy condition (Bauschke et al. in Math Oper Res 42:330–348, 2016; Lu et al. in SIOPT 28(1):333–354, 2018). During this process, the Hessian of the objective function is computed once, and the gradient is computed $$O\left( \ln {1 \over \epsilon }\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mo>ln</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>ϵ</mml:mi> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> times, where $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> is the desired accuracy of the solution for our problem.