# Stochastic Gradient Descent

Stochastic gradient descent (SGD) is an iterative optimization method that estimates gradients from random data samples, widely used in machine learning to minimize objective functions efficiently.

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 thereof, 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] and related fields.

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_i(w), where the parameter w that minimizes Q(w) is to be estimated. Each summand function Q_i is typically associated with the i-th observation in the data set used for training. 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, in statistics, it has been long recognized that requiring even local minimization is too restrictive for some problems of maximum-likelihood estimation. Therefore, contemporary statistical theorists often consider stationary points of the likelihood function, or zeros of its derivative, the score function, and other estimating equations. The sum-minimization problem also arises for empirical risk minimization, where Q_i(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 the following iterations: w := w - η ∇Q(w) = w - (η/n) Σ ∇Q_i(w). The step size is denoted by η, sometimes called the learning rate in machine learning, and ":=" denotes the update of a variable in the algorithm. In many cases, the summand functions have a simple form that enables inexpensive evaluations of the sum-function and the sum gradient. For example, in statistics, one-parameter exponential families allow economical function-evaluations and gradient-evaluations. However, in other cases, evaluating the sum-gradient may require expensive evaluations of the gradients from all summand functions. When the training set is enormous and no simple formulas exist, evaluating the sums of gradients becomes very expensive, because evaluating the gradient requires evaluating all the summand functions' gradients. To economize on the computational cost at every iteration, stochastic gradient descent samples a subset of summand functions at every step. This is very effective in the case of 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_i(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 follows:

- Choose an initial parameter vector w and learning rate η.
- Repeat until convergence:
 - Shuffle the training samples.
 - For each training sample i:
  - Compute the gradient ∇Q_i(w).
  - Update the parameters: w := w - η ∇Q_i(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 described, because the code can make use of vectorization libraries rather than computing each step separately, as was first shown in a 1986 paper where it was called the "bunch-mode back-propagation algorithm". 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 in fact a consequence of the Robbins–Siegmund theorem.

## Linear Regression

Suppose we want to fit a straight line y = w^T x to a set of training examples (x_i, y_i). The objective function is the mean squared error: Q(w) = (1/n) Σ (y_i - w^T x_i)^2. The gradient for a single example is ∇Q_i(w) = -2 (y_i - w^T x_i) x_i. In stochastic gradient descent, the update rule becomes w := w + 2η (y_i - w^T x_i) x_i. This is equivalent to the least mean squares (LMS) algorithm, also known as the Widrow-Hoff rule, introduced by [bernard-widrow](https://www.wikiprompt.org/wiki/bernard-widrow) and Ted Hoff in 1960. The LMS algorithm is a classic example of stochastic approximation and has been widely used in adaptive signal processing.

## Applications in Machine Learning

Stochastic gradient descent is the core optimization algorithm for training [neural-network](https://www.wikiprompt.org/wiki/neural-network)s, including [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) models. In modern deep learning, SGD and its variants are used to minimize loss functions such as cross-entropy for classification or mean squared error for regression. The algorithm's efficiency in handling large datasets makes it essential for training models on massive corpora, such as those used in [large-language-model](https://www.wikiprompt.org/wiki/large-language-model)s. For instance, the training of transformer-based models, as introduced in the 2017 paper "Attention Is All You Need" by [jakob-uszkoreit](https://www.wikiprompt.org/wiki/jakob-uszkoreit), [lukasz-kaiser](https://www.wikiprompt.org/wiki/lukasz-kaiser), and others, relies on SGD or its adaptive variants like [adam-optimizer](https://www.wikiprompt.org/wiki/adam-optimizer).

SGD is also used in other areas of [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence), including computer vision, natural language processing, and reinforcement learning. In reinforcement learning, SGD is used to update policy and value function parameters, as in policy gradient methods. The algorithm's stochastic nature allows it to escape local minima in non-convex optimization problems, which is particularly important for training deep networks with complex loss landscapes.

## Variants and Improvements

Several variants of stochastic gradient descent have been developed to improve convergence and stability. One common improvement is the use of momentum, which accumulates a velocity vector to accelerate gradients in consistent directions and dampen oscillations. Another is Nesterov accelerated gradient, which computes the gradient at a lookahead position. Adaptive learning rate methods, such as [adam-optimizer](https://www.wikiprompt.org/wiki/adam-optimizer), adjust the learning rate per parameter based on estimates of first and second moments of the gradients. These methods are widely used in practice and are often considered as default optimizers for training neural networks.

Other related techniques include [learning-rate-schedule](https://www.wikiprompt.org/wiki/learning-rate-schedule)s, which adjust the learning rate over time, and [gradient-clipping](https://www.wikiprompt.org/wiki/gradient-clipping), which prevents exploding gradients by scaling down large gradients. [batch-normalization](https://www.wikiprompt.org/wiki/batch-normalization) and [layer-normalization](https://www.wikiprompt.org/wiki/layer-normalization) are often used in conjunction with SGD to stabilize training and allow higher learning rates. Additionally, [weight-initialization](https://www.wikiprompt.org/wiki/weight-initialization) strategies, such as Xavier or He initialization, are crucial for effective SGD training.

## Challenges and Considerations

One of the main challenges in stochastic gradient descent is the selection of the learning rate. If the learning rate is too high, the algorithm may diverge; if too low, convergence may be slow. In practice, learning rate schedules or adaptive methods are used to mitigate this issue. Another challenge is the noise introduced by using a subset of data, which can cause the loss to fluctuate. However, this noise can also be beneficial, as it may help the algorithm escape sharp minima and find flatter minima that generalize better.

SGD is sensitive to the scaling of features, so feature normalization is often recommended. The choice of mini-batch size also affects performance: smaller batches introduce more noise but require less memory, while larger batches provide smoother gradients but may lead to worse generalization. In distributed training, SGD can be parallelized using techniques like synchronous or asynchronous updates, as implemented in frameworks such as [tensorflow](https://www.wikiprompt.org/wiki/tensorflow) and PyTorch.

## Historical Context

The roots of stochastic gradient descent trace back to the Robbins–Monro algorithm, developed by Herbert Robbins and Sutton Monro in 1951, which introduced the idea of stochastic approximation for root-finding. In the 1960s, the LMS algorithm by [bernard-widrow](https://www.wikiprompt.org/wiki/bernard-widrow) and Ted Hoff applied similar principles to adaptive filtering. The connection to neural network training was established in the 1980s with the popularization of backpropagation. In 1986, David Rumelhart, Geoffrey Hinton, and Ronald Williams published a paper that demonstrated the effectiveness of backpropagation with SGD for learning internal representations. Since then, SGD has become a cornerstone of machine learning, enabling breakthroughs in areas such as image recognition, speech recognition, and natural language processing.

In the 2010s, the rise of deep learning and the availability of large datasets and powerful hardware, such as GPUs from [nvidia](https://www.wikiprompt.org/wiki/nvidia) and [amd](https://www.wikiprompt.org/wiki/amd), accelerated the adoption of SGD. Research institutions like [stanford-ai-lab](https://www.wikiprompt.org/wiki/stanford-ai-lab), [berkeley-ai-research](https://www.wikiprompt.org/wiki/berkeley-ai-research), and [university-of-toronto](https://www.wikiprompt.org/wiki/university-of-toronto) contributed to theoretical and practical advances. Today, SGD remains an active area of research, with ongoing work on understanding its generalization properties and developing new variants.

## See Also

- [adam-optimizer](https://www.wikiprompt.org/wiki/adam-optimizer)
- [sgd-variants](https://www.wikiprompt.org/wiki/sgd-variants)
- [learning-rate-schedule](https://www.wikiprompt.org/wiki/learning-rate-schedule)
- [gradient-clipping](https://www.wikiprompt.org/wiki/gradient-clipping)
- [batch-normalization](https://www.wikiprompt.org/wiki/batch-normalization)
- [layer-normalization](https://www.wikiprompt.org/wiki/layer-normalization)
- [loss-functions](https://www.wikiprompt.org/wiki/loss-functions)
- [neural-network](https://www.wikiprompt.org/wiki/neural-network)
- [deep-learning](https://www.wikiprompt.org/wiki/deep-learning)
- [machine-learning](https://www.wikiprompt.org/wiki/machine-learning)

---
Source: https://www.wikiprompt.org/wiki/sgd-stochastic-gradient-descent
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-13T03:59:20.557887+00:00