Almost sure convergence rates for Stochastic Gradient Descent and
  Stochastic Heavy Ball
  We study stochastic gradient descent (SGD) and the stochastic heavy ball
method (SHB, otherwise known as the momentum method) for the general stochastic
approximation problem.
  For SGD, in the convex and smooth setting, we provide the first \emph{almost
sure} asymptotic convergence \emph{rates} for a weighted average of the
iterates . More precisely, we show that the convergence rate of the function
values is arbitrarily close to $o(1/\sqrt{k})$, and is exactly $o(1/k)$ in the
so-called overparametrized case. We show that these results still hold when
using stochastic line search and stochastic Polyak stepsizes, thereby giving
the first proof of convergence of these methods in the non-overparametrized
regime.
  Using a substantially different analysis, we show that these rates hold for
SHB as well, but at the last iterate. This distinction is important because it
is the last iterate of SGD and SHB which is used in practice. We also show that
the last iterate of SHB converges to a minimizer \emph{almost surely}.
Additionally, we prove that the function values of the deterministic HB
converge at a $o(1/k)$ rate, which is faster than the previously known
$O(1/k)$.
  Finally, in the nonconvex setting, we prove similar rates on the lowest
gradient norm along the trajectory of SGD.
