SGD with momentum

ImplementEasy20 min12 checks

Lesson: Optimizers Cheat sheet Track: Optimizers

Plain gradient descent steps by the current gradient only. On a long narrow valley it moves from side to side and makes slow progress. Momentum keeps a velocity that adds up past gradients, so the steps in a consistent direction grow and the side to side steps cancel. You write the momentum update from the optimizers lesson and use it to minimize a quadratic.

Task

Write two functions.

momentum_step(params, grads, velocity, lr, beta) does one update and returns (new_params, new_velocity).
minimize_quadratic(A, b, x0, lr, beta, steps, nesterov) runs steps momentum updates on $inline$ and returns every point.

Use the velocity convention of the lesson. The gradient is not scaled by $inline$ :

display

The parameters move with the new velocity, not the old velocity.

The gradient of the quadratic is $inline$ . The velocity starts at 0. With nesterov=False the gradient is computed at the current point $inline$ . With nesterov=True the gradient is computed at the lookahead point $inline$ , where $inline$ is the velocity before the update. The update of $inline$ and $inline$ is then the same momentum step.

Input and output

Name	Type	Shape	Meaning
`params`	float array	any shape	the current parameters
`grads`	float array	same as `params`	the gradient at the current parameters
`velocity`	float array	same as `params`	the velocity before this step
`lr`	float	scalar	the learning rate $inline$
`beta`	float	scalar	the momentum coefficient $inline$ , from 0 to below 1
`A`	float array	`(D, D)`	a symmetric positive definite matrix
`b`	float array	`(D,)`	the linear term
`x0`	float array	`(D,)`	the start point
`steps`	int	scalar	the number of updates, 0 or more
`nesterov`	bool	scalar	use the lookahead gradient

momentum_step returns a tuple of two float arrays with the shape of params: the new parameters and the new velocity.
minimize_quadratic returns a float array of shape (steps + 1, D). Row 0 is x0. Row k is the point after k updates.

Constraints

1 <= D <= 10 and 0 <= steps <= 1000.
Do not change the input arrays.
Use numpy only.

Examples

pythonmomentum_step(np.array([1.0, -2.0]), np.array([0.5, 0.5]), np.array([1.0, 0.0]), lr=0.1, beta=0.9)

text(array([ 0.86, -2.05]), array([1.4, 0.5]))

pythonA = np.array([[3.0, 0.0], [0.0, 1.0]])
b = np.array([3.0, -1.0])
minimize_quadratic(A, b, np.array([0.0, 0.0]), lr=0.1, beta=0.9, steps=3)

text[[ 0.     0.   ]
 [ 0.3   -0.1  ]
 [ 0.78  -0.28 ]
 [ 1.278 -0.514]]

pythonminimize_quadratic(A, b, np.array([0.0, 0.0]), lr=0.1, beta=0.9, steps=3, nesterov=True)

text[[ 0.       0.     ]
 [ 0.3     -0.1    ]
 [ 0.699   -0.271  ]
 [ 1.04067 -0.48241]]

The minimum of this quadratic is at $inline$ .

Hints

4 hints

Solution and notes

Locked

Pass every check with Submit to open the reference solution and the notes.

Run it on your computer

Clone the repository, install numpy and run the same checks in a terminal:

python3 scripts/practice/run.py sgd-momentum my_answer.py
python3 scripts/practice/run.py sgd-momentum my_answer.py --examples

Start my_answer.py from starter.py.

Your code is saved in this browser as you type. On a phone you can read and edit the code, but the checks are easier to use on a desktop.

Keyboard shortcuts

Ctrl Enter: Run the examples
Ctrl Shift Enter: Submit
Tab / Shift Tab: Indent or outdent the lines
Esc then Tab: Move the focus out of the editor
Alt H: Show the next hint

On a Mac, use Cmd in place of Ctrl.

Select Run to check the examples, or Submit to run every check.

Problem