pipette
ESEspañol

Linear Convergence of Nesterov's Acceleration for All Momentum Parameter

Hongda Li, Xianfu Wang

Preprint

In the authors' words

We study the convergence rate of the Nesetrov's accelerated proximal gradient method for a smooth, strongly convex composite minimization objective across a range of value of the momentum extrapolation. The literature proves a convergence rate of the method for a specific momentum extrapolation parameter choice based on the knowledge of strong convexity and Lipschitz smoothness constants. For the heavy ball method it is established that every choice of the momentum parameter either fails to accelerate or fails to converge on the same function class. We prove in this paper that a range of Nesterov style constant momentum extrapolation parameters produces a linear convergence rate. We corroborate these results numerically via performance estimation which computes a method's exact worst case rate as a semidefinite program.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: with appendix, 35 pages. It's already submitted at the time of uploading to arxiv