A Hitchhiker's Guide to Momentum

Gradient Descent with Momentum

Gradient descent with momentum, also known as heavy ball or momentum for short, is an optimization method designed to solve unconstrained minimization problems of the form $$\begin{array}{}\text{(1)}& \underset{xx\in {\mathbb{R}}^d}{\arg \min }f(xx),\end{array}$$ where the objective function $f$ is differentiable and we have access to its gradient $\mathrm{\nabla }f$. In this method the update is a sum of two terms. The first term is the difference between the current and the previous iterate $(x{x}_t-x{x}_{t-1})$, also known as momentum term. The second term is the gradient $\mathrm{\nabla }f(x{x}_t)$ of the objective function.

Gradient Descent with Momentum
Input: starting guess $x{x}_0$, step-size $h>0$ and momentum parameter $m\in (0,1)$.
$x{x}_1=x{x}_0-{\displaystyle \frac{h}{m+1}}\mathrm{\nabla }f(x{x}_0)$
For $t=1,2,\dots$ compute $$\begin{array}{}\text{(2)}& x{x}_{t+1}=x{x}_t+m(x{x}_t-x{x}_{t-1})-h\mathrm{\nabla }f(x{x}_t)\end{array}$$

Despite its simplicity, gradient descent with momentum exhibits unexpectedly rich dynamics that we’ll explore on this post.

The origins of momentum can be traced back to Frankel’s method in the 1950s for solving linear system of equations. It was later generalized by Boris Polayk to non-quadratic objectives. In recent years there has been a resurgence in interest in this venerable method, as a stochastic variant of this method, where the gradient is replaced by a stochastic estimate, is one of the most popular methods for deep learning. This has led in recent years to a flurry fo research –and improved understanding – of this stochastic variant. Although this blog posts limits itself with the deterministic variant, the interested reader is encouraged to explore following references. A good starting point is the paper by Sutskever et al., which was among the firsts to highlight the importance of momentum for deep learning optimization. More recent progress include an analysis of the last iteration of the method by Tao et al. and a paper by Liu et al. that develops accelerated variants for over-parameterized models.

Coming back to the subject of our post, the (non-stochastic) gradient descendent with momentum method, a paper that also explores the dynamics of momentum is Gabriel Goh’s Why Momentum Really Works. There are subtle but important differences between both analysis. The landscape described in the section “The Dynamics of Momentum” describe the improvement along the direction of a single eigenvector. This partial view produces some misleading conclusions. For example, along the direction of a single eigenvector, the largest improvement is achieved with zero momentum and a step-size of 1 over the associated eigenvalue. This conclusion however doesn’t hold in higher dimensions, where as we will see, the momentum term that yields the fastest convergence is non-zero.

How fast is Momentum?

Momentum is fast. So fast that it’s often the default choice of machine learning practitioners. But can we quantify this more precisely?

Throughout the post we’ll assume that our objective function $f$ is a quadratic objective of the form $$\begin{array}{}\text{(3)}& f(xx)\stackrel{\text{def}}{=}\frac{1}{2}(xx-x{x}^{\star })HH(xx-x{x}^{\star }),\end{array}$$ where $HH$ is a symmetric positive definite matrix and $x{x}^{\star }$ is the minimizer of the objective. We’ll assume that the eigenvalues of $HH$ are in the interval $[\mu ,L]$.

The measure we’ll use to quantify the speed of convergence is the rate of convergence. This is the worst-case relative improvement in the iterate suboptimality at iteration $t$, defined as $$\begin{array}{}\text{(4)}& r_t\stackrel{\text{def}}{=}\underset{x{x}_0,\text{eigs}(HH)\in [\mu ,L]}{sup}\frac{\Vert x{x}_t-x{x}^{\star }\Vert }{\Vert x{x}_0-x{x}^{\star }\Vert }.\end{array}$$ This is a worst-case measure because of all problem instances, we take worst possible initialization $x{x}_0$ and matrix $HH$ with eigenvalues in the interval $[\mu ,L]$.

This is a measure of how much progress is made (in the worst-case) at iteration $t$. The smaller the value of $r_t$, the faster the algorithm converges. Since all algorithms that we consider converge exponentially fast, for large enough $t$ the error is of the order of $\mathcal{O}({\text{constant}}^t)$. Hence the most informative quantity is the value of $\text{constant}$ in this expression. We’ll call this quantity the asymptotic rate of convergence, and denote it: $$\begin{array}{}\text{(5)}& r_{\mathrm{\infty }}\stackrel{\text{def}}{=}\underset{t\to \mathrm{\infty }}{lim sup}\sqrt[t]{r_t}.\end{array}$$ This is the quantity we’ll be discussing throughout the post and what we’ll use to compare the speed of momentum for different values of its hyperparameters.

A connection between optimization methods and polynomials

To compute easily the asymptotic rate of convergence for all admissible values of step-size and momentum, we’ll use a connection between optimization of quadratic functions and the theory of orthogonal polynomials. This theory was extensively used in the early days of numerical analysis and provides an elegant and simple way to compute asymptotic rates (and non-asymptotic ones, althought not the topic of this blog post) from known results in the theory of orthogonal polynomials. We favor this technique for its simplicity and elegance, although ones ones that also be used with identical results. Other techniques include the linear operator technique used by Polyak, the estimate sequences technique pioneered by Nesterov or the use of Lyapunov functions.

The main result that will allow us to make the link between optimization and orthogonal polynomials is the following result. It’s origins seem unclear, although a proof can be found in the 1959 monograph of Rutishauser.

Consider the following polynomial $P_t$ of degree $t$, defined recursively as: $$\begin{array}{}\text{(6)}& \begin{array}{rl}& P_{t+1}(\lambda )=(1+m-h\lambda )P_t(\lambda )-m{P}_{t-1}(\lambda )\\ & P_1(\lambda )=1-\frac{h}{1+m}\lambda ,P_0(\lambda )=1,\end{array}\end{array}$$ Then we can write the suboptimality at iteration $t$ as $$\begin{array}{}\text{(7)}& x{x}_t-x{x}^{\star }=P_t(HH)(x{x}_0-x{x}^{\star }),\end{array}$$ where $P_t(HH)$ is the matrix obtained from evaluating the (originally rel-valued) polynomial $P_t$ at the matrix $HH$.

This last identity will allow us to easily compute convergence rates. In particular, plugging it into the definition of the convergence rate $\text{(4)}$ we get that the rate is determined by the absolute value of the residual polynomial over the $[\mu ,L]$ interval: $$\begin{array}{}\text{(8)}& r_t& =\underset{x{x}_0,\text{eigs}(HH)\in [\mu ,L]}{sup}\frac{\Vert P_t(HH)(x{x}_0-x{x}^{\star })\Vert }{\Vert x{x}_0-x{x}^{\star }\Vert }\text{(9)}& & =\underset{\text{eigs}(HH)\in [\mu ,L]}{sup}\Vert P_t(HH)\Vert \text{(10)}& & =\underset{\lambda \in [\mu ,L]}{sup}|P_t(\lambda )|.\end{array}$$ We’ve now reduced the problem of computing the convergence rate to the problem of computing the absolute value of a polynomial over a given interval. This is a problem that has been extensively studied in the theory of orthogonal polynomials. In particular, we’ll use known bounds on Chebyshev polynomials of the first and second kind, as the residual polynomial of momentum can be written as a convex combination of these two polynomials. This fact is proven in the next result, which is a generalization of equation (II.29) in (Rutishauser 1959).

The residual polynomial of momentum can be written in terms of Chebyshev polynomials of the first and second kind as $$\begin{array}{}\text{(11)}& P_t(\lambda )=m^{t/2}(\frac{2m}{1+m}{T}_t(\sigma (\lambda ))+\frac{1-m}{1+m}{U}_t(\sigma (\lambda ))).\end{array}$$ where $\sigma (\lambda )={\displaystyle \frac{1}{2\sqrt{m}}}(1+m-h\lambda )$ is a linear function that we'll refer to as the link function and $T_t$ and $U_t$ are the Chebyshev polynomials of the first and second kind respectively.

Tools of the trade: the two faces of Chebyshev polynomials

A key feature that we’ll use extensively about Chebyshev polynomials is that they behave very differently inside and outside the interval $[-1,1]$. Inside this interval (shaded blue region) the magnitude of these polynomials stays close to zero, while outside it explodes:

Let’s make this observation more precise.

Inside the $[-1,1]$ interval, Chebyshev polynomials admit the trigonometric definitions $T_t(\cos (\theta ))=\cos (t\theta )$ and $U_t(\cos (\theta ))=\sin ((t+1)\theta )/\sin (\theta )$ and so they have an oscillatory behavior with values bounded in absolute value by 1 and $t+1$ respectively.

Outside of this interval the Chebyshev polynomials of the first kind admit the explicit form for $|\xi |\ge 1$: $$\begin{array}{}\text{(19)}& T_t(\xi )& ={\displaystyle \frac{1}{2}}(\xi -\sqrt{{\xi }^2-1}{)}^t+{\displaystyle \frac{1}{2}}(\xi +\sqrt{{\xi }^2-1}{)}^t\text{(20)}& U_t(\xi )& =\frac{(\xi +\sqrt{{\xi }^2-1}{)}^{t+1}-(\xi -\sqrt{{\xi }^2-1}{)}^{t+1}}{2\sqrt{{\xi }^2-1}}.\end{array}$$ We’re interested in convergence rates, so we’ll look into $t$-th root asymptotics of the quantities.With little extra effort, it would be possible to derive non-asymptotic convergence rates, although I won't pursue this analysis here. Luckily, these asymptotics are the same for both polynomialsAlthough we won't use it here, this $t$-th root asymptotic holds for (almost) all orthogonal polynomials, not just Chebyshev polynomials. See for instance reference below and taking limits we have that $$\begin{array}{}\text{(21)}& \underset{t\to \mathrm{\infty }}{lim}\sqrt[t]{|T_t(\xi )|}=\underset{t\to \mathrm{\infty }}{lim}\sqrt[t]{|U_t(\xi )|}=|\xi |+\sqrt{{\xi }^2-1}.\end{array}$$

The Robust Region

Let’s start first by considering the case in which the image of $\sigma$ is in the $[-1,1]$ interval. This is the most favorable case. In this case, the Chebyshev polynomials are bounded in absolute value by 1 and $t+1$ respectively. Since the Chebsyshev polynomials are evaluated at $\sigma (\cdot )$, this implies that $|\sigma (\lambda )|\le 1$. We’ll call the set of step-size and momentum parameters for which the previous inequality is verified the robust region.

Let’s visualize this region in a map. Since $\sigma$ is a linear function, its extremal values are reached at the edges: $$\begin{array}{}\text{(22)}& \underset{\lambda \in [\mu ,L]}{max}|\sigma (\lambda )|=max|\sigma (\mu )|,|\sigma (L)|.\end{array}$$ Using $\mu \le L$ and that $\sigma (\lambda )$ is decreasing in $\lambda$, we can simplify the condition $|\sigma (\lambda )|\le 1$ to $\sigma (\mu )\le 1$ and $\sigma (L)\ge -1$, which in terms of the step-size and momentum correspond to: $$\begin{array}{}\text{(23)}& \frac{(1-\sqrt{m}{)}^2}{\mu }\le h\le \frac{(1+\sqrt{m}{)}^2}{L}.\end{array}$$ These two conditions provide the upper and lower bound of the robust region.

Asymptotic rate

Let $\sigma (\lambda )=\cos (\theta )$ for some $\theta$, which is always possible since $\sigma (\lambda )\in [-1,1]$. In this regime, Chebyshev polynomials verify the identities $T_t(\cos (\theta ))=\cos (t\theta )$ and $U_t(\cos (\theta ))=\sin ((t+1)\theta )/\sin (\theta )$ , which replacing in the definition of the residual polynomial gives $$\begin{array}{}\text{(24)}& P_t({\sigma }^{-1}(\cos (\theta )))=m^{t/2}[\frac{2m}{1+m}\cos (t\theta )+\frac{1-m}{1+m}\frac{\sin ((t+1)\theta )}{\sin (\theta )}].\end{array}$$

Since the expression inside the square brackets is bounded in absolute value by $t+2$, taking $t$-th root and then limits we have $\underset{t\to \mathrm{\infty }}{lim sup}\sqrt[t]{|P_t({\sigma }^{-1}(\cos (\theta )))|}=\sqrt{m}$ for any $\theta$. This gives our first asymptotic rate:

The asymptotic rate in the robust region is $r_{\mathrm{\infty }}=\sqrt{m}$.

This is nothing short of magical. It would seem natural –and this will be the case in other regions– that the speed of convergence should depend on both the step-size and the momentum parameter. Yet, this result implies that it’s not the case in the robust region. In this region, the convergence only depends on the momentum parameter \mom. Amazing.This insensitivity to step-size has been leveraged by Zhang et al. 2018 to develop a momentum tuner

This also illustrates why we call this the robust region. In its interior, perturbing the step-size in a way that we stay within the region has no effect on the convergence rate. The next figure displays the asymptotic rate (darker is faster) in the robust region.

The Lazy Region

Let’s consider now what happens outside of the robust region. In this case, the convergence will depend on the largest of $\{|\sigma (\mu )|,|\sigma (L)|\}$. We’ll consider first the case in which the maximum is $|\sigma (\mu )|$ and leave the other one for next section.

This region is determined by the inequalities $|\sigma (\mu )|>1$ and $|\sigma (\mu )|\ge |\sigma (L)|$. Using the definition of $\sigma$ and solving for $h$ gives the equivalent conditions $$\begin{array}{}\text{(25)}& h\le \frac{2(1+m)}{L+\mu }\text{ and }h\le \frac{(1-\sqrt{m}{)}^2}{\mu }.\end{array}$$ Note the second inequality is the same one as for the robust region $\text{(23)}$ but with the inequality sign reversed, and so the region will be on the oposite side of that curve. We’ll call this the lazy region, as in increasing the momentum will take us out of it and into the robust region.

Asymptotic rate

As we saw earlier, outside of the $[-1,1]$ interval both Chebyshev have simple $t$-th root asymptotics. Using this and that both kinds of Chebyshev polynomials agree in sign outside of the $[-1,1]$ interval we can compute the asymptotic rate as $$\begin{array}{}\text{(26)}& \underset{t\to \mathrm{\infty }}{lim}\sqrt[t]{r_t}& =\sqrt{m}\underset{t\to \mathrm{\infty }}{lim}\sqrt[t]{\frac{2m}{m+1}{T}_t(\sigma (\mu ))+\frac{1-m}{1+m}{U}_t(\sigma (\mu ))}\text{(27)}& & =\sqrt{m}(|\sigma (\mu )|+\sqrt{\sigma (\mu {)}^2-1})\end{array}$$ This gives the asymptotic rate for this region

In the lazy region the asymptotic rate is $r_{\mathrm{\infty }}=\sqrt{m}(|\sigma (\mu )|+\sqrt{\sigma (\mu {)}^2-1})$.

Unlike in the robust region, this rate depends on both the step-size and the momentum parameter, which enters in the rate through the link function $\sigma$. This can be observed in the color plot of the asymptotic rate

Knife’s Edge

The robust and lazy region occupy most (but not all!) of the region for which momentum converges. There’s a small region that sits between the lazy and robust regions and the region where momentum diverges. We call this region the Knife’s edge

For parameters not in the robust or lazy region, we have that $|\sigma (L)|>1$ and $|\sigma (L)|>|\sigma (\mu )|$. Using the asymptotics of Chebyshev polynomials as we did in the previous section, we have that the asymptotic rate is $\sqrt{m}(|\sigma (L)|+\sqrt{\sigma (L{)}^2-1})$. The method will only converge when this asymptotic rate is below 1. Enforcing this results in $h<2(1+m)/L$. Combining this condition with the one of not being in the robust or lazy region gives the characterization: $$\begin{array}{}\text{(28)}& h<\frac{2(1+m)}{L}\text{ and }h\ge max\{\frac{2(1+m)}{L+\mu },\frac{(1+\sqrt{m}{)}^2}{L}\}.\end{array}$$

Asymptotic rate

The asymptotic rate can be computed using the same technique as in the lazy region. The resulting rate is the same as in that region but with $\sigma (L)$ replacing $\sigma (\mu )$:

In the Knife's edge region the asymptotic rate is $\sqrt{m}(|\sigma (L)|+\sqrt{\sigma (L{)}^2-1})$.

Pictorially, this corresponds to

Putting it All Together

This is the end of our journey. We’ve visited all the regions on which momentum converges.There's a small convergent region with negative momentum parameter that we haven't visited. Although not typically used for minimization, negative momentum has found applications in smooth games (Gidel et al., 2020). The only thing left to do is to combine all the asymptotic rates we’ve gathered along the way.

The asymptotic rate $\underset{t\to \mathrm{\infty }}{lim sup}\sqrt[t]{r_t}$ of momentum is $$\begin{array}{}\text{(29)}& & \sqrt{m}& & \text{ if }h\in [\frac{(1-\sqrt{m}{)}^2}{\mu },\frac{(1+\sqrt{m}{)}^2}{L}]\text{(30)}& & \sqrt{m}(|\sigma (\mu )|+\sqrt{\sigma (\mu {)}^2-1})& & \text{ if }h\in [0,min\{\frac{2(1+m)}{L+\mu },\frac{(1-\sqrt{m}{)}^2}{\mu }\}]\text{(31)}& & \sqrt{m}(|\sigma (L)|+\sqrt{\sigma (L{)}^2-1})& & \text{ if }h\in [max\{\frac{2(1+m)}{L+\mu },\frac{(1+\sqrt{m}{)}^2}{L}\},\frac{2(1+m)}{L})\text{(32)}& & \ge 1\text{ (divergence)}& & \text{ otherwise.}\end{array}$$

Plotting the asymptotic rates for all regions we can see that Polyak momentum (the method with momentum \mom = \left(\frac{\sqrt{L} - \sqrt{\lmin}}{\sqrt{L} + \sqrt{\lmin}}\right)^2 and step-size \step = \left(\frac{2}{\sqrt{L} + \sqrt{\lmin}}\right)^2 which is asymptotically optimal among the momentum methods with constant coefficients) is at the intersection of the three regions.

Reproducibility

All plots in this post were generated using the following Jupyer notebook: [HTML] [IPYNB]