On the Last Iterate Convergence of Momentum Methods
  SGD with Momentum (SGDM) is a widely used family of algorithms for
large-scale optimization of machine learning problems. Yet, when optimizing
generic convex functions, no advantage is known for any SGDM algorithm over
plain SGD. Moreover, even the most recent results require changes to the SGDM
algorithms, like averaging of the iterates and a projection onto a bounded
domain, which are rarely used in practice. In this paper, we focus on the
convergence rate of the last iterate of SGDM. For the first time, we prove that
for any constant momentum factor, there exists a Lipschitz and convex function
for which the last iterate of SGDM suffers from a suboptimal convergence rate
of $\Omega(\frac{\ln T}{\sqrt{T}})$ after $T$ iterations. Based on this fact,
we study a class of (both adaptive and non-adaptive)
Follow-The-Regularized-Leader-based SGDM algorithms with \emph{increasing
momentum} and \emph{shrinking updates}. For these algorithms, we show that the
last iterate has optimal convergence $O(\frac{1}{\sqrt{T}})$ for unconstrained
convex stochastic optimization problems without projections onto bounded
domains nor knowledge of $T$. Further, we show a variety of results for
FTRL-based SGDM when used with adaptive stepsizes. Empirical results are shown
as well.
