Stochastic Gradient Descent (SGD)
- Introduced by
- Robbins, H. & Monro, S.
- Year
- 1951
- Type
- First-order iterative optimization algorithm
What does it do?
Stochastic Gradient Descent (SGD) is a first-order iterative optimization algorithm, rooted in the stochastic approximation framework introduced by Robbins and Monro in 1951, that minimizes an objective function by updating model parameters using the gradient computed on a single randomly selected training example (or a small mini-batch) at each step.
It is the core optimization engine behind modern machine learning and deep learning, enabling the training of models on datasets too large to fit in memory.
The intuition behind the method
Ordinary gradient descent computes the exact gradient of the loss over all training examples before making a single parameter update — correct but prohibitively slow on large datasets. SGD trades exactness for speed: it picks one example (or a small batch) at random, computes a noisy estimate of the gradient, and immediately updates the parameters. The noise is not merely a nuisance; it acts as implicit regularization, helping the optimizer escape shallow local minima and saddle points. Over many iterations the noisy steps average out and the parameters converge toward a minimum of the loss, much like a drunkard's walk that still arrives at the destination.
History
The theoretical foundation for SGD was laid by Herbert Robbins and Sutton Monro in their 1951 paper 'A Stochastic Approximation Method', which proved that iterative noisy updates with a decaying step size converge to the root of a regression function. The connection to gradient-based optimization was made explicit by Kiefer and Wolfowitz (1952) and later by Widrow and Hoff's LMS rule (1960) for adaptive filtering. SGD gained prominence in machine learning through the work of LeCun and collaborators in the late 1980s and 1990s for training neural networks via backpropagation. The publication of large-scale experiments by Bottou and collaborators in the 2000s demonstrated SGD's superiority over batch methods on industrial datasets. The modern mini-batch SGD formulation became universal with the deep learning renaissance around 2012 (AlexNet), and the algorithm remains the dominant optimizer in the field, with variants such as Adam (Kingma & Ba, 2014) built directly on its update rule.
When to use it
SGD is the method of choice whenever the training set is large enough that computing the full gradient per update is too costly, which encompasses virtually all modern neural network training and large-scale linear model fitting. It applies to any differentiable loss function. Key assumptions: the loss is differentiable (or sub-differentiable) with respect to the parameters, data points are sampled independently, and the gradient estimator is unbiased. For strongly convex objectives SGD achieves O(1/T) convergence; for general non-convex objectives (e.g., deep networks) it finds stationary points in practice, though no global optimality guarantee exists. Mini-batch SGD (batch sizes 32–512) is typically preferred over pure single-example SGD because it provides lower-variance gradient estimates and exploits parallelism on modern hardware. When the dataset is small enough for full-batch gradient descent and the objective is well-conditioned, second-order methods such as L-BFGS may converge faster.
Limitations and considerations
- Gradient estimates are noisy, which causes the loss to fluctuate rather than decrease monotonically, making convergence harder to diagnose.
- Highly sensitive to the learning rate: too large causes divergence; too small makes training prohibitively slow.
- Convergence to a global minimum is not guaranteed for non-convex objectives such as deep neural networks.
- Isotropic updates treat all parameter dimensions equally, making it poorly suited to loss surfaces with very different curvatures along different axes — motivating adaptive-rate variants.
- Requires careful tuning of the learning rate schedule; poor schedules substantially degrade final performance.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Scales to arbitrarily large datasets because each update requires only one example or a mini-batch, keeping memory and compute per step constant.
- Built-in noise provides implicit regularization and helps escape shallow local minima and saddle points in non-convex landscapes.
- Extremely general: applicable to any differentiable loss, including cross-entropy, mean squared error, hinge loss, and custom objectives.
- Forms the foundation of nearly all modern optimizers (Adam, RMSProp, AdaGrad, Nesterov momentum) — understanding SGD is prerequisite to understanding them.
- Straightforward to implement and parallelize across GPUs using mini-batches.
Applications
- Training deep neural networks for image classification, speech recognition, and natural language processing.
- Fitting large-scale logistic regression and linear SVM models in text classification and recommendation systems.
- Online learning settings where examples arrive sequentially and the model must be updated in real time.
- Reinforcement learning policy gradient methods, where the expected return is optimized using sampled trajectories.
- Matrix factorization for collaborative filtering in recommender systems.
How it works
How it works
The training objective is the average loss over all n examples. For tasks such as classification with cross-entropy or regression with squared error, this sum can have billions of terms, making full evaluation at every iteration impractical.
Formula
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)At step t, a single training example (or mini-batch) is sampled uniformly at random. The gradient of the loss on that sample is an unbiased estimator of the true gradient, so on average the update points in the right direction even though it is noisy for any individual step.
Formula
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})The parameter vector is moved in the direction opposite to the gradient estimate, scaled by the learning rate eta_t. A smaller learning rate makes updates cautious but slow; a larger rate speeds convergence but risks overshooting. This single line — the Robbins–Monro update — is the heart of nearly every modern optimizer.
Formula
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_tThe Robbins–Monro conditions (sum of rates diverges, sum of squared rates converges) guarantee convergence for convex objectives. In practice, common schedules include step decay, cosine annealing, and warm restarts; the conditions provide the theoretical grounding for why a decaying schedule is necessary.
Formula
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \inftyCommon pitfalls
- Using a constant learning rate throughout training without any decay schedule, causing the optimizer to oscillate around the minimum rather than settle into it.
- Choosing the batch size without considering the implicit regularization effect: very large batches reduce noise and can harm generalization compared to smaller batches at the same number of epochs.
- Forgetting to shuffle the training data before each epoch, which can introduce systematic bias when data are ordered by class or time.
- Tuning the learning rate on validation loss only once rather than monitoring training curves, missing signs of divergence or premature plateau.
- Treating SGD as a black-box optimizer without understanding its convergence properties, then switching blindly to Adam when convergence seems slow without diagnosing the root cause.
Frequently asked questions
What is the difference between SGD, mini-batch SGD, and full-batch gradient descent?
Full-batch gradient descent computes the exact gradient over all n training examples per update — accurate but O(n) cost per step. Pure SGD uses exactly one randomly chosen example per update — O(1) cost but very noisy. Mini-batch SGD uses a small random subset (typically 32–512 examples) — a practical compromise that reduces noise while keeping cost manageable and exploiting GPU parallelism. In modern usage, 'SGD' almost always means mini-batch SGD.
How should I set the learning rate?
There is no universal answer, but a common practice is to start with a moderate value (e.g., 0.01 or 0.1), monitor the training loss curve, and apply a decay schedule such as step decay, cosine annealing, or warm restarts. Learning rate finders (sweeping rates over a few batches and observing the loss) can identify a good initial value. The Robbins–Monro theory requires the rate to decay to zero, but in practice the decay is often applied gently to avoid premature slowdown.
Why does SGD sometimes generalize better than Adam?
Adaptive-rate optimizers like Adam often converge faster but can overfit more, particularly on image classification tasks. The higher noise in SGD — especially at small batch sizes — acts as implicit regularization, helping the model find flatter minima that generalize better. Several empirical studies (e.g., Wilson et al., 2017) have documented this phenomenon, which is why SGD with momentum is still preferred for training computer vision models such as ResNet.
Does SGD guarantee finding the global minimum?
Only for strictly convex objectives, under the Robbins–Monro step-size conditions. For non-convex objectives (virtually all deep networks), SGD provides convergence to a stationary point (where the gradient is zero), which in practice tends to be a good local minimum rather than a saddle point or the global minimum. Empirically, the solutions found are often good enough for state-of-the-art performance.
Related methods
Sources
Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.
Open DOI referenceCopied.Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.
ISBN: 978-0-262-03561-3Copied.