  We consider gradient flow/gradient descent and heavy ball/accelerated
gradient descent optimization for convex objective functions. In the gradient
flow case, we prove the following:
  1. If $f$ does not have a minimizer, the convergence $f(x_t)\to \inf f$ can
be arbitrarily slow.
  2. If $f$ does have a minimizer, the excess energy $f(x_t) - \inf f$ is
integrable/summable in time. In particular, $f(x_t) - \inf f = o(1/t)$ as
$t\to\infty$.
  3. In Hilbert spaces, this is optimal: $f(x_t) - \inf f$ can decay to $0$ as
slowly as any given function which is monotone decreasing and integrable at
$\infty$, even for a fixed quadratic objective.
  4. In finite dimension (or more generally, for all gradient flow curves of
finite length), this is not optimal: We prove that there are convex monotone
decreasing integrable functions $g(t)$ which decrease to zero slower than
$f(x_t)-\inf f$ for the gradient flow of any convex function on $\mathbb R^d$.
For instance, we show that any gradient flow $x_t$ of a convex function $f$ in
finite dimension satisfies $\liminf_{t\to\infty} \big(t\cdot \log^2(t)\cdot
\big\{f(x_t) -\inf f\big\}\big)=0$.
  This improves on the commonly reported $O(1/t)$ rate and provides a sharp
characterization of the energy decay law. We also note that it is impossible to
establish a rate $O(1/(t\phi(t))$ for any function $\phi$ which satisfies
$\lim_{t\to\infty}\phi(t) = \infty$, even asymptotically.
  Similar results are obtained in related settings for (1) discrete time
gradient descent, (2) stochastic gradient descent with multiplicative noise and
(3) the heavy ball ODE. In the case of stochastic gradient descent, the
summability of $\mathbb E[f(x_n) - \inf f]$ is used to prove that $f(x_n)\to
\inf f$ almost surely - an improvement on the convergence almost surely up to a
subsequence which follows from the $O(1/n)$ decay estimate.
