The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than 1/k²

The forward-backward algorithm is a powerful tool for solving optimization problems with an additively separable and smooth plus nonsmooth structure. In the convex setting, a simple but ingenious acceleration scheme developed by Nesterov improves the theoretical rate of convergence for the function values from the standard O(k⁻¹) down to O(k⁻²). In this short paper, we prove that the rate of convergence of a slight variant of Nesterov's accelerated forward-backward method, which produces convergent sequences, is actually o(k⁻²), rather than O(k⁻²). Our arguments rely on the connection between this algorithm and a second-order differential inclusion with vanishing damping.