# Stochastic Gradient Descent (SGD)

Stochastic gradient descent (SGD) is an iterative optimization method that approximates gradient descent by using a randomly selected subset of data to estimate the gradient, reducing computational cost in large-scale machine learning.

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 [[artificial-intelligence] more broadly.

## 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) * sum_{i=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. There, 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 iterations of the form w := w - eta * nabla Q(w) = w - (eta/n) * sum_{i=1}^{n} nabla Q_i(w). The step size is denoted by eta, sometimes called the learning rate in machine learning, and the symbol ":=" 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 - eta * nabla 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.

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 the context of 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 eta 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 = a + b*x to a set of training examples (x_i, y_i) using least squares. The objective function is Q(a, b) = (1/n) * sum_{i=1}^{n} (y_i - (a + b*x_i))^2. Batch gradient descent would compute the gradient of Q with respect to a and b using all n examples. Stochastic gradient descent, in contrast, picks a random example i and updates a and b using only the gradient of the squared error for that example: a := a - eta * (-2)*(y_i - (a + b*x_i)), and b := b - eta * (-2*x_i)*(y_i - (a + b*x_i)). This is much cheaper per iteration, especially when n is large.

## Applications in Machine Learning

Stochastic gradient descent is the cornerstone of training [[neural-network]s and [[deep-learning] models. In these contexts, the objective function is typically the empirical risk, and the loss function measures the discrepancy between predicted and actual outputs. For example, in training a [[transformer] model for natural language processing, SGD or its variants are used to update the weights of the network based on mini-batches of text data. The method is particularly effective for large-scale problems, such as those encountered in [[large-language-model]s, where the training data may consist of billions of tokens.

SGD has also been applied in other domains, including [[computer-vision] (though not in the provided slugs, it is a common application), [[reinforcement-learning], and [[generative-ai]. In [[generative-ai], models like [[openai]'s GPT series and [[anthropic]'s Claude are trained using stochastic optimization techniques. The choice of optimizer, often SGD with momentum or [[adam-optimizer], significantly affects the speed and quality of convergence.

## Variants and Improvements

Several variants of stochastic gradient descent have been developed to address its limitations, such as slow convergence and sensitivity to learning rate. These include [[sgd-variants] like momentum, Nesterov accelerated gradient, AdaGrad, RMSProp, and [[adam-optimizer]. Each variant modifies the update rule to improve convergence properties. For instance, momentum adds a fraction of the previous update to the current update, helping to accelerate gradients in the right direction and dampen oscillations. Adam, which stands for Adaptive Moment Estimation, maintains per-parameter learning rates that are adapted based on estimates of the first and second moments of the gradients.

Another important improvement is the use of [[learning-rate-schedule]s, which adjust the learning rate during training. Common schedules include step decay, exponential decay, and cosine annealing. These schedules help the algorithm converge more reliably by reducing the step size as the optimization progresses.

Other techniques that interact with SGD include [[gradient-clipping], which prevents exploding gradients by scaling down gradients that exceed a threshold, and [[batch-normalization] and [[layer-normalization], which stabilize the distribution of inputs to each layer, often allowing higher learning rates.

## Convergence and Challenges

While SGD is computationally efficient, it introduces variance in the gradient estimates, which can cause the loss to fluctuate. The convergence rate of SGD is generally slower than that of batch gradient descent in terms of the number of iterations, but the per-iteration cost is much lower, leading to faster overall training in large-scale settings. The choice of mini-batch size is a critical hyperparameter: smaller batches introduce more noise but require less memory, while larger batches provide smoother gradients but may converge to sharper minima, which can generalize worse.

SGD can also get stuck in saddle points or local minima, especially in non-convex problems like [[deep-learning]. Various strategies, such as restarting, using momentum, or employing adaptive learning rates, help mitigate these issues. In practice, SGD and its variants have been remarkably successful in training deep networks, achieving state-of-the-art results on many tasks.

## Historical Context

The roots of stochastic gradient descent lie in the Robbins-Monro algorithm, introduced by Herbert Robbins and Sutton Monro in 1951 for stochastic approximation. The method was later adapted to machine learning in the 1980s, particularly in the context of backpropagation for [[neural-network]s. The term "stochastic gradient descent" became widely used as the field of [[machine-learning] grew. Today, it is a fundamental tool in the toolkit of every machine learning practitioner, and it is implemented in all major deep learning frameworks, including those used by companies like [[google-deepmind], [[amazon-web-services], and [[microsoft-azure].

## 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)
- [neural-network](https://www.wikiprompt.org/wiki/neural-network)
- [deep-learning](https://www.wikiprompt.org/wiki/deep-learning)

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