Gradient Descent is an optimization algorithm that finds the set of input variables for a target function that results in a minimum value of the target function, called the minimum of the function.
As its name suggests, gradient descent involves calculating the gradient of the target function.
You may recall from calculus that the first-order derivative of a function calculates the slope or curvature of a function at a given point. Read left to right, a positive derivative suggests the target function is sloping uphill and a negative derivative suggests the target function is sloping downhill.
- Derivative: Slope or curvature of a target function with respect to specific input values to the function.
If the target function takes multiple input variables, they can be taken together as a vector of variables. Working with vectors and matrices is referred to linear algebra and doing calculus with structures from linear algebra is called matrix calculus or vector calculus. In vector calculus, the vector of first-order derivatives (partial derivatives) is generally referred to as the gradient of the target function.
- Gradient: Vector of partial derivatives of a target function with respect to input variables.
The gradient descent algorithm requires the calculation of the gradient of the target function with respect to the specific values of the input values. The gradient points uphill, therefore the negative of the gradient of each input variable is followed downhill to result in new values for each variable that results in a lower evaluation of the target function.
A step size is used to scale the gradient and control how much to change each input variable with respect to the gradient.
- Step Size: Learning rate or alpha, a hyperparameter used to control how much to change each input variable with respect to the gradient.
This process is repeated until the minimum of the target function is located, a maximum number of candidate solutions are evaluated, or some other stop condition.
Gradient descent can be adapted to minimize the loss function of a predictive model on a training dataset, such as a classification or regression model. This adaptation is called stochastic gradient descent.
- Stochastic Gradient Descent: Extension of the gradient descent optimization algorithm for minimizing a loss function of a predictive model on a training dataset.
The target function is taken as the loss or error function on the dataset, such as mean squared error for regression or cross-entropy for classification. The parameters of the model are taken as the input variables for the target function.
- Loss function: target function that is being minimized.
- Model parameters: input parameters to the loss function that are being optimized.
The algorithm is referred to as “stochastic” because the gradients of the target function with respect to the input variables are noisy (e.g. a probabilistic approximation). This means that the evaluation of the gradient may have statistical noise that may obscure the true underlying gradient signal, caused because of the sparseness and noise in the training dataset.
The insight of stochastic gradient descent is that the gradient is an expectation. The expectation may be approximately estimated using a small set of samples.
— Page 151, Deep Learning, 2016.
Stochastic gradient descent can be used to train (optimize) many different model types, like linear regression and logistic regression, although often more efficient optimization algorithms have been discovered and should probably be used instead.
Stochastic gradient descent (SGD) and its variants are probably the most used optimization algorithms for machine learning in general and for deep learning in particular.
— Page 294, Deep Learning, 2016.
Stochastic gradient descent is the most efficient algorithm discovered for training artificial neural networks, where the weights are the model parameters and the target loss function is the prediction error averaged over one, a subset (batch) of the entire training dataset.
Nearly all of deep learning is powered by one very important algorithm: stochastic gradient descent or SGD.
— Page 151, Deep Learning, 2016.
There are many popular extensions to stochastic gradient descent designed to improve the optimization process (same or better loss in fewer iterations), such as Momentum, Root Mean Squared Propagation (RMSProp) and Adaptive Movement Estimation (Adam).
A challenge when using stochastic gradient descent to train a neural network is how to calculate the gradient for nodes in hidden layers in the network, e.g. nodes one or more steps away from the output layer of the model.
This requires a specific technique from calculus called the chain rule and an efficient algorithm that implements the chain rule that can be used to calculate gradients for any parameter in the network. This algorithm is called back-propagation.