The Gabor model has two parameters, so we could find the global minimum by either
exhaustively searching the parameter space or
repeatedly starting gradient descent from different positions and choosing the result with the lowest loss.
However, neural network models can have millions of parameters, so neither approach is practical.
In short, using gradient descent to find the global optimum of a high-dimensional loss function is challenging. We can find a minimum, but there is no way to tell whether this is the global minimum or even a good one.
One of the main problems is that the final destination of a gradient descent algorithm is entirely determined by the starting point.
Stochastic gradient descent (SGD) attempts to remedy this problem by adding some noise to the gradient at each step. The solution still moves downhill on average, but at any given iteration, the direction chosen is not necessarily in the steepest downhill direction.
Indeed, it might not be downhill at all. The SGD algorithm has the possibility of moving temporarily uphill and hence jumping from one “valley” of the loss function to another.
Gradient descent vs. stochastic gradient descent.
Gradient descent with line search. As long as the gradient descent algorithm is initialized in the right “valley” of the loss function (e.g., points 1 and 3), the parameter estimate will move steadily toward the global minimum.
However, if it is initialized outside this valley (e.g., point 2), it will descend toward one of the local minima.
Stochastic gradient descent adds noise to the optimization process, so it is possible to escape from the wrong valley (e.g., point 2) and still reach the global minimum.
Alternative view of SGD for the Gabor model with a batch size three.
Loss function for the entire training dataset. At each iteration, there is a probability distribution of possible parameter changes (inset shows samples). These correspond to different choices of the three batch elements.
Loss function for one possible batch. The SGD algorithm moves in the downhill direction on this function for a distance that is determined by the learning rate and the local gradient magnitude. The current model (dashed function in inset) changes to better fit the batch data (solid function).
A different batch creates a different loss function and results in a different update.
For this batch, the algorithm moves downhill with respect to the batch loss function but in the locally uphill direction with respect to the global loss function in panel (a). This is how SGD can escape local minima.
Batches and epochs
The mechanism for introducing randomness is simple. At each iteration, the algorithm chooses a random subset of the training data and computes the gradient from these examples alone. This subset is known as a minibatch or batch for short.
The update rule for the model parameters \(\phi_t\) at iteration \(t\) is hence:
where \(\mathcal{B}_t\) is a set containing the indices of the input/output pairs in the current batch and, as before, \(ℓ_i\) is the loss due to the \(i^{th}\) pair. The term \(\alpha\) is the learning rate, and together with the gradient magnitude, determines the distance moved at each iteration.
The learning rate is chosen at the start of the procedure and does not depend on the local properties of the function.
The batches are usually drawn from the dataset without replacement.
The algorithm works through the training examples until it has used all the data, at which point it starts sampling from the full training dataset again.
A single pass through the entire training dataset is referred to as an epoch.
A batch may be as small as a single example or as large as the whole dataset.
The latter case is called full-batch gradient descent and is identical to regular (non-stochastic) gradient descent.
An alternative interpretation of SGD is that it computes the gradient of a different loss function at each iteration; the loss function depends on both the model and the training data and hence will differ for each randomly selected batch.
In this view, SGD performs deterministic gradient descent on a constantly changing loss function. However, despite this variability, the expected loss and expected gradients at any point remain the same as for gradient descent.
Properties of stochastic gradient descent
SGD has several attractive features.
Although SGD adds noise to the trajectory, it still improves the fit to a subset of the data at each iteration. Hence, the updates tend to be sensible even if they are not optimal.
Because it draws training examples without replacement and iterates through the dataset, the training examples all still contribute equally.
It is less computationally expensive to compute the gradient from just a subset of the training data.
It can (in principle) escape local minima.
It reduces the chances of getting stuck near saddle points; it is likely that at least some of the possible batches will have a significant gradient at any point on the loss function.
Finally, there is some evidence that SGD finds parameters for neural networks that cause them to generalize well to new data in practice (see section 9.2).
SGD does not necessarily “converge” in the traditional sense. However, the hope is that when we are close to the global minimum, all the data points will be well described by the model.
Consequently, the gradient will be small, whichever batch is chosen, and the parameters will cease to change much. In practice, SGD is often applied with a learning rate schedule.
The learning rate \(\alpha\) starts at a high value and is decreased by a constant factor every N epochs.
The logic is that in the early stages of training, we want the algorithm to explore the parameter space, jumping from valley to valley to find a sensible region.
In later stages, we are roughly in the right place and are more concerned with fine-tuning the parameters, so we decrease α to make smaller changes.
