The chapter opens with a warning: “Ultimately, what we really care about is producing a model that performs well on data that we have never seen before. But we can only fit the model to data that we can actually see.”
Optimization algorithms matter for a blunt practical reason: training a complex DL model can take hours, days or even weeks, and the performance of the optimization algorithm directly affects the model training efficiency. Understanding the principles of the different algorithms and the role of their hyper-parameters lets us tune the trainable parameters in a targeted manner.
But the goals of optimization and of deep learning are fundamentally different, and confusing them is a classic error:
| Optimization | Deep learning | |
|---|---|---|
| Concern | Minimizing an objective | Finding a suitable model, given a finite amount of data |
| Objective function | A loss based on the training dataset | — |
| Goal | Reduce the training error | Minimize the generalization error, producing models whose validity extends beyond the data used to train them |
The two minima do not coincide: the minimum of the training error sits at a different place from the minimum of the test error. So we need to pay attention to overfitting in addition to using the optimization algorithm to reduce the training error.
There are many challenges in DL optimization. The slides single out three of the most vexing.
| Challenge | Definition | Worked example from the slides |
|---|---|---|
| Local minima | The smallest values of a function within a given range. A global minimum is the smallest value on the entire domain. | For f(x) = x · cos(πx) on [−1, 2], f(−0.25) is a local minimum while f(1.1) is the global minimum. |
| Saddle points | Any location where all gradients of a function vanish but which is neither a global nor a local minimum. | For f(x, y) = x² − y², the point (0, 0) is a maximum with respect to y and a minimum with respect to x; both ∂f/∂x = 2x and ∂f/∂y = −2y are zero there. |
| Vanishing gradients | The gradient becomes vanishingly small, effectively preventing the weight from changing its value. | For f(x) = tanh(x), the output changes very little when the input is very high or very low, so the gradient is close to zero. |
Two consequences the slides stress:
For vanishing gradients the outcome is the same but the cause is different: optimization gets stuck for a long time before making progress, and in the worst case this may completely stop the network from further training.
Gradient descent is an iterative optimization algorithm for finding a local minimum of a differentiable function. To find that minimum we take steps proportional to the negative of the gradient of the function at the current point:
x ← x − η · ∇fThe slides run it on f(x) = x², whose gradient is ∇f = 2x, starting from x₀ = 10 with f(x₀) = 100. With η = 0.2:
x₁ = x₀ − η · 2x₀ = 10 − 0.2 · 2 · 10 = 6 f(x₁) = 36
…
x₁₀ = 0.06 f(x₁₀) = 0.004η determines how large a step is taken in the opposite direction of the gradient and is called the Learning Rate (LR). It is one of the most crucial hyper-parameters of an ANN, since it represents the speed at which the network “learns”. The slides show all three regimes on the same parabola:
| Learning rate | After 1 step | After 10 steps | Diagnosis |
|---|---|---|---|
η = 0.05 (too small) | x₁ = 9, f = 81 | x₁₀ = 3.5, f = 12.16 | Updates x very slowly, requiring more iterations to get a better solution. |
η = 0.2 (good) | x₁ = 6, f = 36 | x₁₀ = 0.06, f = 0.004 | Converges quickly to the minimum. |
η = 1.1 (too large) | x₁ = −12, f = 144 | x₁₀ = 61.9, f = 3833.7 | x overshoots the optimal solution and gradually diverges. |
Reproduce all three yourself: set the learning rate, then step down the parabola.
Analysing the loss trend during training gives the same diagnosis without knowing the true minimum. The slides describe four curves:
Gradient descent finds the global minimum if the loss function is convex. Unfortunately, almost all optimization problems arising in DL are non-convex, and the slides identify the culprit precisely:
Introducing non-linearity in the network, by adding hidden layers, makes the loss function non-convex and local minima appear. The very thing that gives a deep network its expressive power (Chapter 3) is the thing that destroys the convergence guarantee. In such cases gradient descent only guarantees finding a local minimum, which can be worse than the global one.
There are three variants of gradient descent, differing in how much data we use to compute the gradient of the loss function. Depending on the amount of data, we trade off the accuracy of the parameter update against the time it takes to perform an update.
Computes the gradient of the loss function for the entire training set and then updates the parameters.
for i in range(num_epochs):
grad = compute_gradient(data, params)
params = params - learning_rate * gradOne epoch is when the entire training set is passed forward and backward through the neural network only once.
Performs a parameter update for each training example.
for i in range(num_epochs):
np.random.shuffle(data)
for example in data:
grad = compute_gradient(example, params)
params = params - learning_rate * gradThe training examples are shuffled to avoid pre-existing order. SGD is usually much faster than batch gradient descent, but it performs frequent updates with a high variance that cause the loss function to fluctuate heavily. That fluctuation cuts both ways:
It has been demonstrated that when we slowly decrease the learning rate, SGD shows the same convergence behaviour as batch gradient descent.
Takes the best from both and performs an update for every mini-batch of training examples.
for i in range(num_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size=64):
grad = compute_gradient(batch, params)
params = params - learning_rate * gradThe batch size is the total number of training examples present in a single mini-batch. One iteration is when all the training examples of a single mini-batch are passed forward and backward through the network once, so the number of iterations needed to complete one epoch equals the number of batches.
Typical starting values are 64, 128, 256 or 512. Increasing the batch size:
| Stochastic | Mini-batch | Batch | |
|---|---|---|---|
| Batch size | 1 | 64 – 512 | the whole training set |
| Update path | Heavily fluctuating | Moderately noisy | Smooth |
| Computational resources per epoch | High | Moderate | Low |
| Epochs required | Few | Moderate | Many |
Mini-batch gradient descent does not guarantee good convergence and presents a few challenges that need to be addressed — each of which motivates one of the algorithms in the rest of this chapter:
SGD has trouble navigating areas where the surface curves much more steeply in one dimension than in another, which are common around local optima. In these scenarios, SGD oscillates across the slopes of the cliff while only making small progress along the bottom towards the local optimum.
The slides make this concrete with f(x, y) = 0.1x² + 2y², whose gradient is ∇fT = [0.2x, 4y], starting from (−5, −2) where f = 10.5, with η = 0.4. Plain gradient descent produces:
| Step | Update | Position | f |
|---|---|---|---|
| 1 | x₁ = −5 − 0.4 · 0.2 · (−5), y₁ = −2 − 0.4 · 4 · (−2) | (−4.6, 1.2) | 5 |
| 2 | same rule | (−4.2, −0.7) | 2.7 |
| 3 | same rule | (−3.9, 0.4) | 1.8 |
| 4 | same rule | (−3.6, −0.2) | 1.4 |
Look at the y column: −2, 1.2, −0.7, 0.4, −0.2. It flips sign every step, wasting the budget on oscillation, while x crawls from −5 to −3.6.
Momentum is a method that accelerates SGD in the relevant direction and reduces oscillations. It adds a fraction β of the update vector of the past step to the current update vector:
vt = β · vt−1 + ∇f
x ← x − η · vtThe momentum term vt:
β is usually set to 0.9 or a similar value. Essentially, when using momentum we push a ball down a hill: the ball accumulates momentum as it rolls downhill, becoming faster and faster on the way. The same thing happens to our parameter updates.
With β = 0.5 and η = 0.4 on the same function, the slides get:
| Step | vx | vy | Position | f |
|---|---|---|---|---|
| 1 | 0.5·0 + 0.2·(−5) = −1 | 0.5·0 + 4·(−2) = −8 | (−4.6, 1.2) | 5 |
| 2 | −1.4 | 0.8 | (−4, 0.9) | 3.2 |
| 3 | −1.5 | 4 | (−3.4, −0.7) | 2.1 |
| 4 | −1.4 | −0.8 | (−2.8, −0.4) | 1.1 |
After four steps, momentum has reached f = 1.1 where plain gradient descent reached 1.4, and x has travelled from −5 to −2.8 instead of −3.6: the vx component keeps growing because its gradient always points the same way.
The slides then criticise their own metaphor: “a ball that rolls down a hill, blindly following the slope, is highly unsatisfactory.”
Nesterov Accelerated Gradient (NAG) uses a smarter momentum term, one that has a notion of where it is going, so that it knows to slow down before the function slopes up again:
vt = β · vt−1 + ∇f(x − η · β · vt−1)
x ← x − η · vtThe change is entirely in where the gradient is evaluated. The quantity x − η · β · vt−1 is an approximation of the next position of the parameter x, so we can look ahead by calculating the gradient with respect to the approximate future position rather than the current one.
| Momentum | NAG | |
|---|---|---|
| Gradient evaluated at | x (where we are) | x − ηβvt−1 (where we are heading) |
| Behaviour approaching a wall | Keeps accelerating, then overshoots | Sees the upslope early and brakes |
With η = 0.3 and β = 0.9 on f(x, y) = 0.1x² + 2y² from (−5, −2), the slides trace: (−4.7, 0.4) with f = 2.5; (−4.2, −0.5) with f = 2.3; (−3.5, 0.3) with f = 1.4; (−2.7, −0.2) with f = 0.8.
Adjusting the learning rate during training is often just as important as the selection of the optimizer. The reasoning is geometric:
Three aspects have to be considered:
| Aspect | The trade-off |
|---|---|
| Magnitude | If the LR is too large, optimization diverges; if too small, it takes too long to train or we end up with a suboptimal result. |
| Rate of decay | If the LR remains large we may bounce around the minimum without reaching it. |
| Initialization | How the parameters are set initially and how they evolve. Large steps at the beginning might not be useful, because the initial parameters are random and so the initial update directions might be meaningless too. |
Knowing when to decay is itself delicate: decay it slowly and you waste computation bouncing around with little improvement; decay it too aggressively and the system cools too quickly, unable to reach the best position it can.
| Schedule | Formula | Hyper-parameters |
|---|---|---|
| Step decay | η = η₀ · δt/s |
Reduces the initial LR η₀ by a factor δ every predefined number of epochs or iterations s; t is the number of executed epochs or iterations. |
| Exponential decay | η = η₀ · e−k·t |
η₀ and k; t is the current epoch or iteration number. |
| Time-based decay | η = η₀ / (1 + k · t) |
η₀ and k. |
The slides plot all three over 30 epochs with η₀ = 0.1, δ = 0.2, s = 10, k = 0.05. Compare them below with those exact values, then change them.
In some cases the random initialization of the parameters does not guarantee a good solution, especially if a large LR is used at the beginning, leading to divergence. Choosing a sufficiently small LR to prevent early divergence works, but then progress is very slow.
A simple solution is a warmup period, during which the LR increases to its initial maximum, after which we cool the rate down until the end of the optimization process. The slides plot a warmup rising to about 0.3 over the first 10 epochs before the decay begins.
δ every s epochs); exponential and time-based fall continuously; warmup inverts the start, rising to the maximum before any decay begins.Schedules have two weaknesses. First, their hyper-parameters have to be defined in advance and they heavily depend on the type of model and problem. Second, the same LR is applied to all weight updates — but with sparse data we may want to update the weights to different extents.
We need to decrease the value of the LR differently for each weight as training proceeds. There are four representative methods: Adagrad, RMSProp, Adadelta and Adam.
The slides motivate it with a single neuron with three inputs and a sigmoid activation. The gradient of out with respect to a particular weight is:
∇wi = ∂out/∂wi = (∂σ/∂net) · ini = (1 − σ(net)) · σ(net) · iniIf there are n data points, the total gradient is the sum over all of them. Now ask: what happens if the feature ini is very sparse, that is, its value is 0 for most of the n data points? It is fair to assume that ∇wi will be 0 for most data points, and hence wi will not get enough updates. This is a problem if ini is both sparse and important. We would like to take those rare updates seriously — but choosing a different LR for each weight by hand is unfeasible with thousands or millions of weights.
Adaptive Gradients adapts the LR to the parameters, performing larger updates for infrequent parameters and smaller updates for frequent ones. For this reason it is well suited to large-scale sparse data. It adjusts the LR in proportion to the update history: more updates means more decay.
st = st−1 + (∇f)²
x ← x − η / √(st + ε) · ∇fThe history of the gradient is accumulated in st, and ε is a smoothing term to avoid division by zero. The smaller the accumulated gradient, the smaller st and therefore the bigger the effective learning rate, since st divides η.
| Benefit | Weakness |
|---|---|
| Eliminates the need to manually tune the learning rate. | The accumulation of the squared gradients: during training the accumulated sum grows, the LR decreases, becoming infinitesimally small until the network is no longer able to acquire additional knowledge. |
Slide example with η = 0.4, ε = 10−6 on f(x, y) = 0.1x² + 2y² from (−5, −2): (−4.6, −1.6) with f = 7.2, then (−4.3, −1.3) with f = 5.2, then (−4.1, −1.1) with f = 4.1.
Root Mean Squared Propagation was introduced to reduce the aggressive decreasing of the LR of Adagrad. It changes the gradient accumulation part from a sum of squared gradients to an exponential weighted average of squared gradients:
st = γ · st−1 + (1 − γ) · (∇f)²
x ← x − η / √(st + ε) · ∇fγ is a hyper-parameter usually set to 0.9. Because old contributions decay geometrically instead of accumulating forever, st stops growing without bound and the learning rate stops collapsing.
Slide example with η = 0.4, γ = 0.9, ε = 10−6: (−3.7, −0.7) with f = 2.3, then (−2.8, −0.2) with f = 0.9, then (−2.1, −0.1) with f = 0.5 — markedly faster than Adagrad on the same problem.
Another variant of Adagrad, proposed to overcome its main drawback. Like RMSProp it computes the gradient accumulation as an exponential weighted average of squared gradients, but differently from RMSProp it does not require a learning rate to be set, since it uses the amount of change itself as calibration for future change:
st = γ · st−1 + (1 − γ) · (∇f)²
∇f̃ = √(Δxt−1 + ε) / √(st + ε) · ∇f
x ← x − ∇f̃
Δxt = γ · Δxt−1 + (1 − γ) · (∇f̃)²Slide example with γ = 0.9, ε = 10−2: (−4.7, −1.7) with f = 8, then (−4.4, −1.4) with f = 5.8. Note that no η appears anywhere.
Adaptive Moment Estimation combines the techniques described before into a very efficient learning algorithm. It keeps an exponential weighted average of past gradients, like Momentum:
vt = β1 · vt−1 + (1 − β1) · ∇fand an exponential weighted average of squared gradients, like RMSProp and Adadelta:
st = β2 · st−1 + (1 − β2) · (∇f)²β1 and β2 are nonnegative weighting hyper-parameters usually set to 0.9 and 0.999.
The authors observe that both vt and st are biased towards zero, during the initial time steps and when the decay rates are small (that is, when the betas are close to 1). To counter these biases a normalization is applied:
v̂t = vt / (1 − β1t)
ŝt = st / (1 − β2t)and the update equation is:
x ← x − η / √(ŝt + ε) · v̂tSlide example with η = 0.4, β1 = 0.9, β2 = 0.999, ε = 10−6: from (−5, −2) the first step gives v̂1x = −1, ŝ1x = 1 and lands at (−4.6, −1.6) with f = 7.2.
Read the family as one lineage. Momentum smooths the gradient. Adagrad scales the step by accumulated squared gradients but never forgets. RMSProp makes that memory exponential so it can forget. Adadelta removes η entirely by calibrating on past changes. Adam keeps both a smoothed gradient and a smoothed squared gradient, and corrects both for their initial bias towards zero.
The slides give practical guidance rather than a ranking:
Three caveats follow, and they are the kind of detail that separates a good answer from an excellent one:
“Which optimizer would you use and why?” expects a conditional answer, not a name. Adam as the default; an adaptive method whenever the data is sparse (because SGD, Momentum and NAG handle sparsity badly); SGD, possibly with momentum and a simple schedule, for fine-tuning where an adaptive method would be too aggressive. Add the state-saving caveat and the answer is complete.
Optimization is primarily concerned with minimizing an objective; its objective function is a loss based on the training dataset, so its goal is to reduce the training error. Deep learning is concerned with finding a suitable model given a finite amount of data, producing models whose validity extends beyond the training data, so its goal is to minimize the generalization error. The two minima are at different places, which is why overfitting must be watched alongside the optimizer.
A saddle point is any location where all gradients vanish but which is neither a global nor a local minimum — for f(x, y) = x² − y², the origin is a minimum in x and a maximum in y. There are many more saddle points than minima or maxima, and they are usually surrounded by a plateau of the same error, so escaping is difficult because the gradient is close to zero in all dimensions.
∇f = 2x, so x ← x − η·2x. With η = 0.2: x₁ = 6 and after ten steps x₁₀ = 0.06 with f = 0.004 — good convergence. With η = 0.05: x₁ = 9, and after ten steps only x₁₀ = 3.5 with f = 12.16 — too slow. With η = 1.1: x₁ = −12 and after ten steps x₁₀ = 61.9 with f = 3833.7 — it overshoots and diverges.
Because introducing non-linearity by adding hidden layers makes the loss function non-convex and local minima appear. Gradient descent finds the global minimum only for convex functions; on a non-convex surface it guarantees only a local minimum, which can be worse than the global one.
Batch computes the gradient over the entire training set: it converges to the global minimum for convex problems and a local one otherwise, but it is very slow, intractable when the data does not fit in memory, and suffers particularly from local minima and saddle points. SGD updates for each example after shuffling: much faster, with high-variance updates whose fluctuation both enables jumps to better minima and complicates exact convergence. Mini-batch updates per batch (typically 64–512): reduced variance, more stable convergence, efficient matrix operations, and it is the algorithm typically used to train ANNs.
An epoch is when the entire training set is passed forward and backward through the network once. An iteration is when all the training examples of a single mini-batch are passed forward and backward once. The number of iterations needed to complete one epoch equals the number of batches.
It buys a computational boost from matrix multiplication in the training calculations and requires fewer epochs to find a good solution. It costs more memory for the training process and generally more computational resources.
SGD has trouble where the surface curves much more steeply in one dimension than another: it oscillates across the slopes while making only small progress along the bottom. Momentum adds a fraction β of the previous update to the current one, vt = βvt−1 + ∇f and x ← x − ηvt. The momentum term increases for dimensions whose gradients point the same way and reduces updates for dimensions whose gradients change direction. β is usually 0.9.
Only in where the gradient is evaluated. NAG computes vt = βvt−1 + ∇f(x − ηβvt−1), using the gradient at an approximation of the next position rather than the current one. This look-ahead gives it a notion of where it is going, so it knows to slow down before the function slopes up again, instead of blindly following the slope like a rolling ball.
Step decay: η = η₀ · δt/s, reducing the initial LR by a factor δ every s epochs. Exponential decay: η = η₀ · e−kt. Time-based decay: η = η₀ / (1 + kt). In all three, t is the number of executed epochs or iterations.
A period at the start of training during which the LR increases to its initial maximum, before being cooled down until the end of optimization. It exists because the random initialization of the parameters does not guarantee a good solution: a large LR at the very beginning can diverge, while a permanently small one makes progress very slow. Warmup avoids both.
The gradient for a weight is proportional to its input, so a sparse feature produces a zero gradient on most data points and its weight never gets enough updates. Adagrad divides the LR by √(st + ε) where st accumulates squared gradients, so rarely updated parameters keep a large effective LR. The weakness is that this accumulation is a sum: it grows monotonically, the LR becomes infinitesimally small, and the network is no longer able to acquire additional knowledge.
RMSProp replaces the sum of squared gradients with an exponential weighted average (γ usually 0.9), so the accumulator can forget and the LR stops collapsing. Adadelta does the same but additionally removes the learning rate entirely, using the amount of past change Δxt−1 as calibration for future change. Adam keeps both an exponential average of gradients (like momentum, β1 = 0.9) and of squared gradients (like RMSProp, β2 = 0.999), and applies a bias correction because both are biased towards zero during the initial time steps.
In a fine-tuning process: adaptive methods can be too aggressive there because of the high initial LR, and SGD often performs better. Also remember that Adam must store its internal state if training is to be paused and resumed, otherwise it operates differently on restart.