Stochastic gradient descent (often abbreviated SGD) is an iterative method for optimizing an objective function with suitable smoothness properties, such as differentiability or subdifferentiability. It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient, calculated from the entire data set, with an estimate calculated from a randomly selected subset of the data. Especially in high-dimensional optimization problems, this reduces the very high computational burden, achieving faster iterations in exchange for a lower convergence rate.
The basic idea behind stochastic approximation can be traced back to the Robbins–Monro algorithm of the 1950s. Today, stochastic gradient descent has become an important optimization method in Machine learning, particularly for training neural networks and other Deep learning models.
Background
Both statistical estimation and machine learning consider the problem of minimizing an objective function that has the form of a sum: Q(w) = (1/n) Σᵢ Qᵢ(w), where the parameter w that minimizes Q(w) is to be estimated. Each summand function Qᵢ is typically associated with the i-th observation in the training data set.
In classical statistics, sum-minimization problems arise in least squares and in maximum-likelihood estimation for independent observations. The general class of estimators that arise as minimizers of sums are called M-estimators. However, it has long been recognized that requiring even local minimization is too restrictive for some maximum-likelihood problems, so contemporary statistical theorists often consider stationary points of the likelihood function or zeros of its derivative, the score function.
The sum-minimization problem also arises for empirical risk minimization. There, Qáµ¢(w) is the value of the loss function at the i-th example, and Q(w) is the empirical risk.
When used to minimize the above function, a standard (or "batch") gradient descent method would perform iterations of the form: w := w - η ∇Q(w) = w - (η/n) Σᵢ ∇Qᵢ(w). The step size η is sometimes called the learning rate in machine learning. In many cases, the summand functions have a simple form that enables inexpensive evaluations of the sum-function and the sum gradient, such as in one-parameter exponential families. However, when the training set is enormous and no simple formulas exist, evaluating the sums of gradients becomes very expensive because it requires evaluating all summand functions' gradients. To economize on computational cost, stochastic gradient descent samples a subset of summand functions at every step, which is very effective in large-scale machine learning problems.
Iterative Method
In stochastic (or "on-line") gradient descent, the true gradient of Q(w) is approximated by a gradient at a single sample: w := w - η ∇Qᵢ(w). As the algorithm sweeps through the training set, it performs the above update for each training sample. Several passes can be made over the training set until the algorithm converges. If this is done, the data can be shuffled for each pass to prevent cycles. Typical implementations may use an adaptive learning rate so that the algorithm converges.
In pseudocode, stochastic gradient descent can be presented as:
- Initialize parameters w and learning rate η.
- Repeat until convergence:
- Shuffle the training data.
- For each training example i:
- Compute gradient ∇Qᵢ(w).
- Update w := w - η ∇Qᵢ(w).
A compromise between computing the true gradient and the gradient at a single sample is to compute the gradient against more than one training sample, called a "mini-batch", at each step. This can perform significantly better than true stochastic gradient descent because the code can make use of vectorization libraries rather than computing each step separately, as first shown in the context of back-propagation. It may also result in smoother convergence, as the gradient computed at each step is averaged over more training samples.
The convergence of stochastic gradient descent has been analyzed using the theories of convex minimization and of stochastic approximation. Briefly, when the learning rates decrease with an appropriate rate and subject to relatively mild assumptions, stochastic gradient descent converges almost surely to a global minimum when the objective function is convex or pseudoconvex, and otherwise converges almost surely to a local minimum. This is a consequence of the Robbins–Siegmund theorem.
Linear Regression
Suppose we want to fit a straight line ŷ = w·x to a set of training examples (xᵢ, yᵢ). A common objective is to minimize the mean squared error: Q(w) = (1/n) Σᵢ (ŷᵢ - yᵢ)². The gradient for a single example is ∇Qᵢ(w) = 2(ŷᵢ - yᵢ)xᵢ. In stochastic gradient descent, the update becomes w := w - η(ŷᵢ - yᵢ)xᵢ. This simple example illustrates how SGD uses one sample at a time, making it computationally efficient for large datasets.
Applications in Machine Learning
Stochastic gradient descent is the core optimization algorithm for training many machine learning models, including deep learning models such as transformers and large language models. It is used in training neural networks for tasks like image recognition, natural language processing, and generative AI. Variants like Adam and other SGD variants have been developed to improve convergence and stability. The choice of learning rate schedule is crucial for effective training.
Challenges and Extensions
SGD faces challenges such as choosing an appropriate learning rate, dealing with noisy gradients, and avoiding poor local minima. Extensions include momentum, adaptive learning rates (e.g., Adam), and techniques like gradient clipping to prevent exploding gradients. In deep learning, methods like batch normalization and dropout are often used in conjunction with SGD to improve training.
Historical Context
The Robbins–Monro algorithm of the 1950s laid the foundation for stochastic approximation. In the 1980s and 1990s, SGD became popular in neural network training, particularly with back-propagation. Today, it remains a fundamental tool in artificial intelligence research and industry, used by major AI labs and companies.
See Also
- Gradient descent (not in list, but related)
- Loss Functions
- Data Augmentation
- Model Pruning