gradient descent
In plain wordsA method for training models by repeatedly nudging every setting a small step in whichever direction most reduces the error, like a hiker who cannot see the valley but keeps stepping wherever the ground tilts down.
The basic first-order optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible. recipe for driving a differentiable function down: compute the gradientgradient, n.: A list of slopes showing which way, and how steeply, a quantity rises as each of its inputs changes. Training nudges an AI's settings in the opposite direction, downhill. at the current point, which points along the steepest uphill direction, move a small distance the opposite way, and repeat; in symbols θ ← θ − η∇L(θ), where η is the learning ratelearning rate, n.: How big a step a model takes each time it adjusts its settings during training. Too large and learning goes haywire; too small and it crawls.. In machine learning, L is the loss functionloss function, n.: A score that measures how wrong a model's predictions are. Training means adjusting the model, step by step, to push this number down. averaged over training data and the gradient is computed by backpropagationbackpropagation, n.: The method neural networks use to learn from mistakes: it works backward from the error to figure out how much each internal connection contributed, so every connection can be adjusted in the right direction.. Plain or full-batch gradient descent uses the whole dataset at every step; deep learning instead uses stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset. on mini-batchesmini-batch, n.: A small random handful of training examples that a model learns from in a single step. Training works through many such handfuls instead of studying the whole dataset at once., usually with momentummomentum, n.: A training trick that lets each update keep part of the previous update's direction, like a ball rolling downhill that builds up speed and coasts over small bumps. or an adaptive optimizeroptimizer, n.: The rule a training program uses to turn measured errors into actual changes to a model's internal numbers, deciding the direction and size of each adjustment. such as AdamAdam, prop. n.: The most widely used method for training neural networks. It smooths the direction of updates over time and automatically sets a separate step size for each setting based on how large its recent changes have been.. On smooth convex problems a small enough step size guarantees convergence to the global minimum. On the non-convex losses of neural networks it guarantees only approach to a stationary point, which could in principle be a poor local minimumlocal minimum, n.: A spot lower than everything immediately around it, like the bottom of a small valley, even though a deeper valley may exist somewhere else. or saddle pointsaddle point, n.: A spot on a surface that is a low point in one direction but a high point in another, like the middle of a horse's saddle or a mountain pass.; in practice large networks trained this way reach low training loss and generalize well, a fact still only partly explained. Behavior depends sharply on η: too small is slow, too large oscillates or diverges (see edge of stabilityedge of stability, n.: A surprising pattern in how neural networks train: the error landscape keeps getting steeper until it is just steep enough to make training wobble, then stays balanced at that edge while the error still falls.).
Full-batch gradient descent is too expensive here, so we sample mini-batches of 512.
Origin
Augustin-Louis Cauchy described the method in an 1847 note to the Paris Academy of Sciences, as a way to solve systems of simultaneous equations. Jacques Hadamard proposed a similar scheme in a memoir on elastic plates (1907; published 1908), and Haskell Curry studied its convergence for nonlinear minimization in 1944. Stochastic versions entered neural computing with Bernard Widrow and Marcian Hoff's LMS rule (1960) and became the engine of deep learning through backpropagation in the 1980s.
Usage note
'Gradient descent' is often used loosely for the whole family of gradient-based optimizers, including SGD and Adam. Not to be confused with gradient boostinggradient boosting, n.: A method that builds a strong predictor by adding small decision trees one at a time, each trained to correct the errors that remain after all the trees before it., which adds new models fitted to the loss gradient rather than updating one model's parameters.
Related
- stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset.
- learning ratelearning rate, n.: How big a step a model takes each time it adjusts its settings during training. Too large and learning goes haywire; too small and it crawls.
- backpropagationbackpropagation, n.: The method neural networks use to learn from mistakes: it works backward from the error to figure out how much each internal connection contributed, so every connection can be adjusted in the right direction.
- loss landscapeloss landscape, n.: A way of picturing training as a journey across hilly terrain, where position stands for the model's settings and height for its error. Training searches for low valleys.
- momentummomentum, n.: A training trick that lets each update keep part of the previous update's direction, like a ball rolling downhill that builds up speed and coasts over small bumps.
- optimizeroptimizer, n.: The rule a training program uses to turn measured errors into actual changes to a model's internal numbers, deciding the direction and size of each adjustment.
- convergenceconvergence, n.: The point at which training settles down and further steps no longer meaningfully improve the model — and, in theory, a guarantee that a method will reach a solution, and how fast.
- gradient boostinggradient boosting, n.: A method that builds a strong predictor by adding small decision trees one at a time, each trained to correct the errors that remain after all the trees before it.
- second-order optimizationsecond-order optimization, n.: Training methods that use not only the slope of the error but also how that slope is changing — its curvature — to choose better-sized steps. They can need far fewer steps, but each costs more.
Sources
- Cauchy, A.-L. (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. Comptes rendus de l'Académie des sciences 25, 536–538.
- Curry, H. B. (1944). The method of steepest descent for non-linear minimization problems. Quarterly of Applied Mathematics 2, 258–261.
Mentioned in
backpropagationbackpropagation, n.: The method neural networks use to learn from mistakes: it works backward from the error to figure out how much each internal connection contributed, so every connection can be adjusted in the right direction., deep learningdeep learning, n.: Machine learning done with neural networks built from many stacked layers: raw data such as pixels, sound or text goes in at one end, and each layer turns what it receives into something more abstract., loss functionloss function, n.: A score that measures how wrong a model's predictions are. Training means adjusting the model, step by step, to push this number down., neural networkneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain., optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible., algorithmalgorithm, n.: A precise, step-by-step procedure for solving a problem or doing a task, like a recipe a computer can follow. In the news, 'the algorithm' often means software that ranks what you see online., convergenceconvergence, n.: The point at which training settles down and further steps no longer meaningfully improve the model — and, in theory, a guarantee that a method will reach a solution, and how fast., convex optimizationconvex optimization, n.: Finding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy., derivativederivative, n.: How fast something changes as one of its inputs changes — the steepness of a curve at a point. Training an AI means repeatedly following such slopes downhill., feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units., genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve., gradientgradient, n.: A list of slopes showing which way, and how steeply, a quantity rises as each of its inputs changes. Training nudges an AI's settings in the opposite direction, downhill., hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., learning ratelearning rate, n.: How big a step a model takes each time it adjusts its settings during training. Too large and learning goes haywire; too small and it crawls., local minimumlocal minimum, n.: A spot lower than everything immediately around it, like the bottom of a small valley, even though a deeper valley may exist somewhere else., loss landscapeloss landscape, n.: A way of picturing training as a journey across hilly terrain, where position stands for the model's settings and height for its error. Training searches for low valleys., mean squared errormean squared error, n.: A way of scoring numerical predictions: square each prediction's error, then average them, so big misses count much more than small ones. Lower is better., momentummomentum, n.: A training trick that lets each update keep part of the previous update's direction, like a ball rolling downhill that builds up speed and coasts over small bumps., multilayer perceptronmultilayer perceptron, n.: A neural network made of several layers of artificial neurons, each connected to every neuron in the next layer. It is the simplest kind of deep network and a component of almost every modern model., Software 2.0Software 2.0, n.: Andrej Karpathy's 2017 name for software whose behavior is learned from examples by a neural network instead of being written line by line by programmers., stochastic gradient descentstochastic gradient descent, n.: A faster version of gradient descent that estimates which way is downhill from a small random sample of the training data at each step, instead of checking the whole dataset., t-SNEt-SNE, n.: A technique for drawing data that have many measurements per item as a flat map in which similar items land close together, widely used to look for groups in AI models' internal data or in genetic data., universal approximation theoremuniversal approximation theorem, n.: A mathematical result showing that a neural network with enough neurons can imitate essentially any smooth input-to-output relationship as closely as you like, though it does not say how to find that network., ADALINEADALINE, prop. n.: An early learning machine from 1960 that adjusted its settings to shrink its errors step by step, the same basic idea used to train today's neural networks.