The Nesterov-Spokoiny Acceleration Achieves Strict $o(1/k^2)$ Convergence

Weibin Peng, Yu Liu, Tianyu Wang

This paper studies the Nesterov-Spokoiny Acceleration (NSA), a variant of the accelerated gradient method by Nesterov and Spokoiny. For smooth convex optimization, NSA achieves a s…