Iteration Complexity of Fixed-Step Methods by Nesterov and Polyak for Convex Quadratic Functions
研究了Polyak动量法和Nesterov加速梯度法在固定步长下用于强凸二次函数的迭代次数上界，该上界在常数因子内最优，并建立了两种方法之间的联系。
Abstract This note considers the momentum method by Polyak and the accelerated gradient method by Nesterov, both without line search but with fixed step length applied to strongly convex quadratic functions assuming that exact gradients are used and appropriate upper and lower bounds for the extreme eigenvalues of the Hessian matrix are known. Simple 2-d-examples show that the Euclidean distance of the iterates to the optimal solution is non-monotone. In this context, an explicit bound is derived on the number of iterations needed to guarantee a reduction of the Euclidean distance to the optimal solution by a factor $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> . For both methods, the bound is optimal up to a constant factor, it complements earlier asymptotically optimal results for the momentum method, and it establishes another link of the momentum method and Nesterov’s accelerated gradient method.