  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 increasing momentum
and 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.
