Cheat Sheet: Acceleration from First Principles

Posts in this series (so far). My apologies for incomplete references--this should merely serve as an overview. Acceleration in smooth convex optimization has been met with awe and has been subject to extensive research over the last years. In a nutshell, what acceleration does is that it provides an "unexpected" speedup in smooth convex optimization; we will be concerned with acceleration in the Nesterov sense [N1], [N2]. Then with standard arguments that we review below we can show that we need roughly $t(\varepsilon) \Theta(\frac{\mu}{L} \log \frac{1}{ \varepsilon})$ iterations (of e.g., gradient descent) to achieve a primal gap Accelerated methods achieve the same accuracy in $\Theta(\sqrt{\frac{\mu}{L}} \log \frac{1}{ \varepsilon})$ iterations, which can be a huge improvement in running time.