9
$\begingroup$

A clear article on Nesterov’s Accelerated Gradient Descent (S. Bubeck, April 2013) says

The intuition behind the algorithm is quite difficult to grasp, and unfortunately the analysis will not be very enlightening either.

This seems odd, for such a powerful method ("you do not really understand something unless you can explain it to your grandmother").

Can anyone point to plots / visualizations of alternating M-steps and G-steps (momentum and gradient), on real or tutorial problems ?
In particular, are "Nesterov ripples" (oscillations) common, and if so, what to do ?

$\endgroup$

2 Answers 2

3
$\begingroup$

I just posted an answer on stats.stackexchange that is meant to help with gaining intuition about the difference between Classical Momentum (CM) and Nesterov's Accelerated Gradient (NAG), which also contains a visualization, though it isn't real or from a tutorial, but made up by me.

Following is a copy of my answer. (This meta.stackexchange answer seems to approve of this copy-paste pattern.)



tl;dr
Just skip to the image at the end.
NAG_ball's reasoning is another important part, but I am not sure it would be easy to understand without all of the rest.



CM and NAG are both methods for choosing the next vector $\theta$ in parameter space, in order to find a minimum of a function $f(\theta)$.

In other news, lately these two wild sentient balls appeared:
CM_ball NAG_ball

It turns out (according to the observed behavior of the balls, and according to the paper On the importance of initialization and momentum in deep learning, that describes both CM and NAG in section 2) that each ball behaves exactly like one of these methods, and so we would call them "CM_ball" and "NAG_ball":
(NAG_ball is smiling, because he recently watched the end of Lecture 6c - The momentum method, by Geoffrey Hinton with Nitish Srivastava and Kevin Swersky, and thus believes more than ever that his behavior leads to finding a minimum faster.)

Here is how the balls behave:

  • Instead of rolling like normal balls, they jump between points in parameter space.
    Let $\theta_t$ be a ball's $t$-th location in parameter space, and let $v_t$ be the ball's $t$-th jump. Then jumping between points in parameter space can be described by $\theta_t=\theta_{t-1}+v_t$.
  • Not only do they jump instead of roll, but also their jumps are special: Each jump $v_t$ is actually a Double Jump, which is the composition of two jumps:
    • Momentum Jump - a jump that uses the momentum from $v_{t-1}$, the last Double Jump.
      A small fraction of the momentum of $v_{t-1}$ is lost due to friction with the air.
      Let $\mu$ be the fraction of the momentum that is left (the balls are quite aerodynamic, so usually $0.9 \le \mu <1$). Then the Momentum Jump is equal to $\mu v_{t-1}$.
      (In both CM and NAG, $\mu$ is a hyperparameter called "momentum coefficient".)
    • Slope Jump - a jump that reminds me of the result of putting a normal ball on a surface - the ball starts rolling in the direction of the steepest slope downward, while the steeper the slope, the larger the acceleration.
      Similarly, the Slope Jump is in the direction of the steepest slope downward (the direction opposite to the gradient), and the larger the gradient, the further the jump.
      The Slope Jump also depends on $\epsilon$, the level of eagerness of the ball (naturally, $\epsilon>0$): The more eager the ball, the further the Slope Jump would take it.
      (In both CM and NAG, $\epsilon$ is a hyperparameter called "learning rate".)
      Let $g$ be the gradient in the starting location of the Slope Jump. Then the Slope Jump is equal to $-\epsilon g$.
  • So for both balls the Double Jump is equal to:$$v_t=\mu v_{t-1} -\epsilon g$$ The only difference between the balls is the order of the two jumps in the Double Jump.
  • CM_ball didn't think it mattered, so he decided to always start with the Slope Jump.
    Thus, CM_ball's Double Jump is: $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}\right)$$
  • In contrast, NAG_ball thought about it for some time, and then decided to always start with the Momentum Jump.
    Therefore, NAG_ball's Double Jump is: $$v_{t}=\mu v_{t-1}-\epsilon\nabla f\left(\theta_{t-1}+\mu v_{t-1}\right)$$

    NAG_ball's reasoning

    • Whatever jump comes first, my Momentum Jump would be the same.
      So I should consider the situation as if I have already made my Momentum Jump, and I am about to make my Slope Jump.
    • Now, my Slope Jump is conceptually going to start from here, but I can choose whether to calculate what my Slope Jump would be as if it started before the Momentum Jump, or as if it started here.
    • Thinking about it this way makes it quite clear that the latter is better, as generally, the gradient at some point $\theta$ roughly points you in the direction from $\theta$ to a minimum (with the relatively right magnitude), while the gradient at some other point is less likely to point you in the direction from $\theta$ to a minimum (with the relatively right magnitude).

Finally, yesterday I was fortunate enough to observe each of the balls jumping around in a 1-dimensional parameter space.
I think that looking at their changing positions in the parameter space wouldn't help much with gaining intuition, as this parameter space is a line.
So instead, for each ball I sketched a 2-dimensional graph in which the horizontal axis is $\theta$.
Then I drew $f(\theta)$ using a black brush, and also drew each ball in his $7$ first positions, along with numbers to show the chronological order of the positions.
Lastly, I drew green arrows to show the distance in parameter space (i.e. the horizontal distance in the graph) of each Momentum Jump and Slope Jump.

CM_ball vs NAG_ball example


Appendix 1 - A demonstration of NAG_ball's reasoning

In this mesmerizing gif by Alec Radford, you can see NAG performing arguably better than CM ("Momentum" in the gif).
(The minimum is where the star is, and the curves are contour lines. For an explanation about contour lines and why they are perpendicular to the gradient, see videos 1 and 2 by the legendary 3Blue1Brown.)

NAG better than CM (Momentum)

An analysis of a specific moment demonstrates NAG_ball's reasoning:

CM vs NAG in a specific moment

  • The (long) purple arrow is the momentum sub-step.
  • The transparent red arrow is the gradient sub-step if it starts before the momentum sub-step.
  • The black arrow is the gradient sub-step if it starts after the momentum sub-step.
  • CM would end up in the target of the dark red arrow.
  • NAG would end up in the target of the black arrow.

Appendix 2 - things/terms I made up (for intuition's sake)

  • CM_ball
  • NAG_ball
  • Double Jump
  • Momentum Jump
  • Momentum lost due to friction with the air
  • Slope Jump
  • Eagerness of a ball
  • Me observing the balls yesterday

Appendix 3 - terms I didn't make up

$\endgroup$
1
$\begingroup$

Added: the following approach separates position steps and gradient steps, from a digital filter point of view.

Put the pair of equations for momentum gradient descent:
$\qquad y_t = (1 + m) x_t - m x_{t-1} \ $ -- momentum, predictor
$\qquad x_{t+1} = y_t + h\ g(y_t) \qquad$ -- gradient
in a form with $y_t$ only, the points at which the gradients $g_t \equiv - \nabla f(y_t)$ are evaluated:
$\qquad y_{t+1} = (1 + m)\, x_{t+1} - m\, x_t $
$\qquad \qquad = (1 + m)\, y_t - m\, y_{t-1} \ + \ (1 + m)\, h g_t - m\, h g_{t-1} $
$\qquad \qquad \approx Position\_filter( y_t, y_{t-1} ...; m_t ) $
$\qquad \qquad \quad + Gradient\_filter( g_t, g_{t-1} ...; h_t )\quad$ -- extrapolate ?

Why filters ? There's a large body of digital filter know-how, which might give some insight.
For example, the 2-term extrapolator $1.9 x_t - 0.9 x_{t-1}$, which is commonly used for both $Position\_filter$ and $Gradient\_filter$, almost triples high-frequency noise [1 -1 1 -1 ...] .
So, use a longer, low-pass filter, matched to the noise. (This may be naive; I'm no expert.)

Why separate filters for positions and for gradients ? If $y_t$ and $g_t$ have very different noise patterns, analyzing and controlling each one by itself may be easier than doing both together. Real gradients can be very noisy, so need smoothing, either outside or inside the descent loop.

To see if filters are at all useful for momentum gradient descent, we need examples and plots of real, noisy data, before and after smoothing, on the web. (Complete programs would be better, but cost time to put up; start with files of $y_t$ and $g_t$, to filter and plot.)
Comments and links are welcome.


About the simplest case that makes sense to plot is 1d, here with $\nabla f(x) = x - 100$ .
1d is trivial, but shows how steps keep growing until, for large values of momentum, they overshoot. (It's also easy to play with gradient noise and gradient smoothing in 1d.)

enter image description here

stepper: x - 100  momentum 0.5  h 0.1 
...
15: x 96.5   + m 0.57   + g 0.29   
16: x 97.4   + m 0.43   + g 0.22   
17: x 98     + m 0.32   + g 0.17   
18: x 98.5   + m 0.24   + g 0.12   
19: x 98.9   + m 0.18   + g 0.093  
20: x 99.2   + m 0.14   + g 0.07   

stepper: x - 100  momentum 0.7  h 0.1 
 1: x 0      + m 0      + g 10     
 2: x 10     + m 7      + g 8.3    
 3: x 25.3   + m 11     + g 6.4    
 4: x 42.4   + m 12     + g 4.6    
 5: x 58.9   + m 12     + g 2.9    
 6: x 73.5   + m 10     + g 1.6    
 7: x 85.3   + m 8.3    + g 0.65   
 8: x 94.2   + m 6.2    + g -0.042 

stepper: x - 100  momentum 0.9  h 0.1 
 1: x 0      + m 0      + g 10     
 2: x 10     + m 9      + g 8.1    
 3: x 27.1   + m 15     + g 5.8    
 4: x 48.2   + m 19     + g 3.3    
 5: x 70.5   + m 20     + g 0.94   
 6: x 91.6   + m 19     + g -1     

The code, in outline:

x = x0
prevstep = 0
for iter in range( 1, maxiter+1 ):
    momstep = momentum * prevstep
    y = x + momstep
    gradstep = - h * gradfunc( y )  # h aka stepsize aka learning rate
    step = momstep + gradstep
    xnew = x + step
    print "%2d: x %-6.3g + m %-6.2g + g %-6.2g " % (iter, x, momstep, gradstep)
    if plot: ...
    if gradstep <= 0:  # back where we came from ?
        break  # restart
    x = xnew
    prevstep = step

Notice that this code is exactly the same with N-dimensional numpy vectors instead of scalars, except for plotting, and restarting when gradstep <= 0. For the latter, see no-U-turn restart.

See also: whats-the-difference-between-momentum-based-gradient-descent-and-nesterov on stats.stackexchange.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .