Imagine you are lost on a foggy mountain and want to reach the valley. You cannot see far, but you can feel the slope under your feet. A sensible plan : take a small step in the steepest downhill direction, then feel around again, and repeat. Do this patiently and you will end up at the bottom. That simple idea, follow the slope downhill, is gradient descent, the optimisation workhorse behind almost all of machine learning. It is how a neural network turns “here is how wrong you are” into “here is how to be a little less wrong”. This post builds it from the hiker’s intuition up to the update rule $\theta \leftarrow \theta - \eta\, \nabla L(\theta)$, and explains the one knob, the learning rate, that makes or breaks it.
1. The problem : minimise a loss
Training a model means choosing its parameters $\theta$ (all the weights) so that its predictions are good. We measure “badness” with a loss function $L(\theta)$, a single number that is large when the model is wrong and small when it is right. Learning is then just minimisation :
\[\begin{equation} \theta^{\ast} = \arg\min_{\theta}\; L(\theta). \label{eq:argmin} \end{equation}\]For anything but the simplest models we cannot solve this with a formula. There are millions of parameters and $L$ is a wildly complicated landscape. So instead of jumping to the answer, we walk to it.
2. The gradient : which way is downhill ?
The tool that tells us the slope is the gradient $\nabla L(\theta)$, the vector of partial derivatives
\[\begin{equation} \nabla L(\theta) = \left( \frac{\partial L}{\partial \theta_1}, \frac{\partial L}{\partial \theta_2}, \dots, \frac{\partial L}{\partial \theta_n} \right). \label{eq:grad} \end{equation}\]In plain words : the gradient is the compass that always points straight uphill. To go down, we simply walk the opposite way. That is the whole trick.
3. The update rule
Gradient descent turns “walk downhill” into one line of maths 1. Starting from a guess $\theta_0$, repeat :
\[\begin{equation} \theta_{t+1} = \theta_{t} - \eta\, \nabla L(\theta_{t}). \label{eq:gd} \end{equation}\]Each term has a plain meaning : $\nabla L$ is which way is uphill, the minus sign says go the other way, and $\eta > 0$ (the learning rate) is how big a step to take. The animation below drops a ball on a loss curve ; at every step it reads the local slope and moves against it, settling into the valley.
4. The learning rate : the one knob that matters
The step size $\eta$ is deceptively important. Get it wrong and the whole thing fails in one of two opposite ways.
- Too small. Progress is safe but painfully slow ; you inch down the mountain and training takes forever.
- Too large. You leap past the valley to the far slope, then leap back even further, overshooting and possibly diverging to infinity.
- Just right. A handful of well-sized steps land you near the bottom.
5. Stochastic gradient descent
There is a catch hiding in $\eqref{eq:gd}$ : computing $\nabla L$ exactly means averaging the error over the entire dataset, which can be millions of examples, for every single step. That is far too slow.
The fix is beautifully lazy : estimate the gradient from a small random mini-batch of examples instead. This is stochastic gradient descent (SGD) (Robbins & Monro, 1951). The estimate is noisy, so the path down the mountain wobbles rather than flows, but each step is thousands of times cheaper, and the noise even helps to escape shallow traps.
Modern optimisers refine this further. Momentum remembers past steps and keeps rolling, damping the wobble like a heavy ball. Adam (Kingma & Ba, 2015) adapts a separate step size for each parameter from the recent history of gradients. They are all, at heart, still $\eqref{eq:gd}$ with a smarter step.
6. The bumpy reality : non-convex landscapes
The bowl in Figure 1 is a convex loss : one valley, and downhill always leads to it. Neural-network losses are non-convex, a mountain range of many valleys, ridges and saddle points, so gradient descent only guarantees a local minimum, not the global best.
Remarkably, this matters far less than one would fear. In the huge parameter spaces of deep learning, most local minima turn out to be nearly as good as the global one, and the truly bad configurations are rare saddle points that noise helps to slip past. This empirical grace is a big part of why deep learning works, and it complements the Universal Approximation Theorem : that theorem promises a good set of weights exists, and gradient descent is the procedure that actually goes and finds one.
7. Conclusion
Gradient descent is the hiker’s rule written in calculus : read the slope with the gradient, step against it, and control your stride with the learning rate. Everything else, mini-batches, momentum, Adam, non-convex landscapes, is a refinement of that one move, $\theta \leftarrow \theta - \eta \nabla L$. But there is a missing piece : for a deep network, how do we even compute the gradient $\nabla L$ over millions of tangled weights ? That is the job of a wonderfully efficient algorithm called backpropagation, the subject of the next post.
References
- Kingma, D. P., & Ba, J. (2015). Adam: A Method for Stochastic Optimization. International Conference on Learning Representations (ICLR).
@inproceedings{Kingma2015, author = {Kingma, Diederik P. and Ba, Jimmy}, title = {Adam: A Method for Stochastic Optimization}, booktitle = {International Conference on Learning Representations (ICLR)}, year = {2015} } - Robbins, H., & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.
@article{Robbins1951, author = {Robbins, Herbert and Monro, Sutton}, title = {A Stochastic Approximation Method}, journal = {The Annals of Mathematical Statistics}, volume = {22}, number = {3}, pages = {400--407}, year = {1951} }
-
Gradient descent dates back to Cauchy in 1847. What is new in the deep-learning era is not the method but the scale, billions of parameters, and the automatic computation of the gradient by backpropagation. ↩