Yesterday I posted the following picture on Twitter and it quickly became my most visible tweet ever (by far):
I thought this would be a good opportunity to revisit the proof of Nesterov’s momentum, especially since as it turns out I really don’t like the way I described it back in 2013 (and to this day the latter post also remains my most visible post ever…). So here we go, for what is hopefully a short and intuitive proof of the convergence rate for Nesterov’s momentum (disclaimer: this proof is merely a rearranging of well-known calculations, nothing new is going on here).
We assume that is -smooth convex function, and we take in the gradient step. The momentum term will be set to a very particular value, which comes out naturally in the proof.
The two basic inequalities
Let us denote and (note that ). Now let us write our favorite inequalities (using and ):
On the way to a telescopic sum
Recall now that , so it would be nice to somehow combine the two above inequalities to obtain a telescopic sum thanks to this simple formula. Let us try to take a convex combination of the two inequalities. In fact it will be slightly more elegant if we use the coefficient on the second inequality, so let us do times the first inequality plus times the second inequality. We obtain an inequality whose right hand side is given by times
Recall that our objective is to obtain a telescopic sum, and at this point we still have flexibility both to choose and . What we would like to have is:
Observe that (since ) the right hand side can be written as , and thus we see that we simply need to have:
Setting the parameters and concluding the proof
Writing we now obtain as a result of the combination of our two starting inequalities:
It only remains to select such that (i.e., roughly is of order ) so that by summing the previous inequality one obtains which is exactly the rate we were looking for.