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.

对于凸目标函数，研究了梯度流、加速梯度下降和随机梯度下降优化。我们证明了梯度流收敛缓慢（如果函数没有最小值），其超出能量在时间上是可积的，对于希尔伯特空间而言，这是最优的；在有限维空间中，存在凸函数的梯度流曲线，其减小速度比任何单调递减且在无穷远处可积的给定函数更慢。在相关设置中，类似的结果也适用于离散时间梯度下降、具有乘积噪声的随机梯度下降和重球 ODE 问题。