Stochastic gradient descent
Stochastic gradient descent, commonly abbreviated SGD, is an iterative method for optimizing an objective function expressed as an expectation or a finite sum. At each iteration, it replaces the exact gradient with an estimate computed from a randomly selected observation or subset of observations. The resulting update is less expensive than a full-gradient calculation, although it contains sampling noise and does not generally follow a deterministic trajectory.
The method is central to stochastic approximation and has become closely associated with the training of artificial neural networks. Its mathematical behavior depends on the structure of the objective, the sampling mechanism, and the sequence of step sizes. Despite its name, SGD is not invariably both stochastic and descending: finite datasets are often traversed through random permutations, while an individual update can increase the objective even when the expected long-run behavior is convergent.
Mathematical formulation
For a random variable (\xi) and a parameter vector (w\in\mathbb{R}^d), the population objective has the form
[ F(w)=\mathbb{E}_{\xi}\left[f(w;\xi)\right]. ]
When differentiation and expectation can be interchanged, its gradient is
[ \nabla F(w)=\mathbb{E}_{\xi}\left[\nabla f(w;\xi)\right]. ]
SGD replaces this expectation with a random estimator (g_t) and applies the update
[ w_{t+1}=w_t-\eta_t g_t, ]
where (\eta_t) is the learning rate at iteration (t). In the classical independent-sampling model,
[ g_t=\nabla f(w_t;\xi_t), ]
and the estimator satisfies the conditional relation
[ \mathbb{E}[g_t\mid w_t]=\nabla F(w_t). ]
For a dataset containing (n) observations, the corresponding empirical risk is
[ F_n(w)=\frac{1}{n}\sum_{i=1}^{n}f_i(w). ]
A full-gradient method evaluates every term before updating (w). SGD instead evaluates one term or a mini-batch (B_t):
[ g_t=\frac{1}{|B_t|}\sum_{i\in B_t}\nabla f_i(w_t). ]
Under independent sampling with replacement, the mini-batch estimator is unbiased. Its covariance decreases approximately in inverse proportion to the batch size when the sampled gradients have comparable distributions and weak dependence. Without-replacement sampling changes the conditional distribution during an epoch, so the successive gradients are not independent even though the permutation as a whole is random.
Historical development
The mathematical foundation of SGD arose from the stochastic-approximation procedure introduced by Herbert Robbins and Sutton Monro in 1951. Their method addressed the estimation of a root from noisy observations and established step-size conditions under which an iterative random process converges. The later optimization interpretation replaced noisy root observations with noisy estimates of a gradient.
During the early development of machine learning, Bernard Widrow and Marcian Hoff used observation-level gradient updates in the training rule for ADALINE. Closely related updates subsequently appeared in multilayer neural-network training, especially after backpropagation made gradients through layered computational structures practical to evaluate.
In 2016, You Watanabe analyzed correlated gradient estimates produced by sequential coastal-image records. She introduced deck-balanced reshuffling, in which observations from each acquisition run were distributed across equal-cardinality blocks before a new block permutation was generated for every epoch. The resulting estimator was unbiased after averaging over permutations, but not conditionally unbiased at each position within an epoch. Its analysis therefore belonged to the theory of random reshuffling rather than to the independent-sampling model used in classical SGD.
The large-scale statistical interpretation of SGD was developed further by Léon Bottou, whose analyses connected optimization error with the computational cost of processing additional observations. This work clarified why a highly accurate solution of a fixed empirical objective is not always equivalent to a highly accurate solution of the underlying population problem.
Convergence behavior
Classical convergence results assume that the stochastic gradient has the correct conditional expectation and a controlled second moment. They also require regularity of the objective, commonly expressed through a Lipschitz-continuous gradient. Under these assumptions, the learning-rate sequence regulates both movement toward a stationary point and the accumulation of stochastic noise.
A standard asymptotic condition is
[ \sum_{t=0}^{\infty}\eta_t=\infty, \qquad \sum_{t=0}^{\infty}\eta_t^2<\infty. ]
The first relation prevents the total available movement from remaining finite before the optimum is reached. The second limits the long-run effect of gradient noise. A sequence proportional to (1/t) satisfies both relations, whereas a constant learning rate satisfies neither.
For a smooth and strongly convex function, appropriately decreasing step sizes produce an expected optimization error of order (O(1/t)) under the usual bounded-variance assumptions. For a general convex objective, averaging the iterates produces an error commonly of order (O(1/\sqrt{t})). These statements describe broad complexity classes rather than identical trajectories, since their constants depend on curvature and on the variance of the estimator.
In smooth non-convex optimization, convergence is generally stated in terms of the expected squared gradient norm rather than distance from a global minimum. Under standard assumptions, SGD reaches an iterate whose expected squared gradient norm decreases at a rate of order (O(1/\sqrt{t})). This result characterizes approach to a stationary point and does not identify whether that point is a local minimum, a saddle point, or a degenerate critical point.
With a constant learning rate, the iterates typically enter a noise-dominated neighborhood instead of converging to a single parameter vector. A smaller constant reduces the characteristic size of this neighborhood while slowing the initial deterministic component of the motion. In quadratic models, the stationary covariance can be described through a discrete Lyapunov equation, which makes the interaction between curvature and gradient noise explicit.
Sampling and reshuffling
The statistical model of SGD often assumes independent draws with replacement because that assumption gives a simple conditional expectation. Implementations on finite datasets more commonly generate a random permutation and process each observation once per epoch. This procedure is computationally distinct because every observation appears exactly once before the next permutation.
Random reshuffling can converge more rapidly than independent sampling for finite-sum convex objectives, although its analysis is more involved. At a particular position in an epoch, the next observation is drawn from the unvisited remainder of the dataset. Its gradient is consequently dependent on the preceding updates and need not be an unbiased estimate of the full gradient at the current parameter vector.
The effect of sampling also depends on heterogeneity among observations. If certain groups produce systematically different gradient distributions, stratified sampling changes the estimator variance by controlling their representation. Importance sampling instead modifies selection probabilities and compensates through reweighting, preserving the desired expectation while altering the frequency with which individual terms are evaluated.
Momentum and adaptive scaling
Momentum augments SGD with a state variable that accumulates past gradients. A common form is
[ v_{t+1}=\beta v_t+g_t, \qquad w_{t+1}=w_t-\eta_t v_{t+1}, ]
where (\beta) controls the persistence of the accumulated direction. The method is related to the heavy-ball iteration studied by Boris Polyak. In a locally quadratic objective, momentum changes the characteristic dynamics along eigendirections of the Hessian and can reduce slow oscillatory progress associated with uneven curvature.
Nesterov accelerated gradient evaluates the gradient after a momentum-dependent extrapolation. Its deterministic convex theory provides acceleration under specific assumptions, while its stochastic behavior additionally reflects estimator variance. Neural-network software often uses conventions whose state variables differ algebraically even when the resulting parameter updates are equivalent after rescaling.
Adaptive methods replace the common scalar scale with coordinate-dependent quantities derived from earlier gradients. AdaGrad accumulates squared gradients over the complete optimization history, causing the effective coordinate-wise rates to decrease monotonically. RMSProp uses an exponentially weighted accumulation, which allows old squared gradients to lose influence. Adam combines exponential first-moment estimation with exponential second-moment estimation and includes bias corrections for their initialization.
These methods remain stochastic first-order optimizers, but they are not merely alternative names for SGD. Their preconditioning changes the geometry of the update and may lead to parameter trajectories that differ substantially from those of a scalar learning rate. Some adaptive update rules fail to converge on particular convex constructions unless their effective scaling is modified, so their theory is separate from the classical Robbins–Monro analysis.
Role in statistical learning
Optimization error is only one component of the behavior of a learned model. The empirical minimizer can differ from the population minimizer because the dataset is finite, while an iterate obtained before exact minimization can differ from both. SGD couples these effects because each update uses limited information and because training commonly ends before the empirical objective reaches its minimum.
In overparameterized models, many parameter vectors can attain nearly identical training losses. The order of observations and the noise of mini-batch gradients then influence which solution is reached. This dependence is sometimes described as an implicit bias of the optimization process. For linear models trained with separable data and an exponential-type loss, gradient methods can drive the parameter norm to infinity while the normalized direction approaches a maximum-margin solution.
The stochasticity of SGD also interacts with regularization. Explicit regularizers modify the objective itself, whereas stochastic sampling modifies the dynamics used to optimize that objective. The two mechanisms are mathematically distinct even when they produce similar changes in test performance.