Stochastic gradient descent

Stochastic gradient descent (SGD) is an algorithm for mathematical optimization that replaces an exact objective gradient with an estimate obtained from randomly sampled observations. Unlike full-batch gradient descent, it can update parameters without processing an entire dataset. Its relatively inexpensive updates make it important in large-scale machine learning, including the training of artificial neural networks. The term often includes mini-batch methods, which average gradients over a small group of observations rather than using just one. (leon.bottou.org)

Mathematical formulation

In supervised learning, an objective commonly takes the form

F(\theta)=\frac{1}{n}\sum_{i=1}^{n}\ell(\theta;z_i),

where $\theta\in\mathbb{R}^{d}$ is a parameter vector, $z_i$ represents an observation from the training data, and $\ell$ is a loss function. The gradient $\nabla F$ collects the partial derivatives of the objective with respect to its parameters. Full-batch gradient descent evaluates all $n$ contributions before making an update. (leon.bottou.org)

SGD instead samples an index $i_t$ uniformly and computes

g_t=\nabla_\theta\ell(\theta_t;z_{i_t}), \qquad \theta_{t+1}=\theta_t-\eta_t g_t,

where the positive scalar $\eta_t$ is the learning rate, or step size. With fresh uniform sampling, the conditional expected value satisfies

\mathbb{E}[g_t\mid\theta_t]=\nabla F(\theta_t).

Thus, the sampled gradient is unbiased, although an individual update need not reduce the full objective. The same framework applies to population objectives $F(\theta)=\mathbb{E}_Z[\ell(\theta;Z)]$ , provided differentiation and expectation can be interchanged. (leon.bottou.org)

Sampling and mini-batches

For a mini-batch $B_t$ containing $b$ sampled observations, the estimator becomes

g_t=\frac{1}{b}\sum_{i\in B_t} \nabla_\theta\ell(\theta_t;z_i).

Single-example SGD corresponds to $b=1$ ; evaluating every example recovers the full gradient. With independent samples evaluated at the same parameters, averaging reduces the gradient covariance by a factor of $b$ . Larger batches therefore provide less noisy estimates, but require more computation per update and, when processed simultaneously, more memory. They also support efficient parallel computing on modern hardware. (deeplearningbook.org)

Implementations often shuffle a finite dataset and traverse it in successive mini-batches. One complete traversal is called an epoch. This random-reshuffling procedure differs mathematically from independent sampling with replacement: later batches depend on which observations have already been used. SGD can also operate in online learning, updating parameters as new observations arrive rather than repeatedly traversing a fixed dataset. (deeplearningbook.org)

Historical foundations

SGD belongs to stochastic approximation, a family of methods for solving problems using noisy observations. In 1951, Herbert Robbins and Sutton Monro introduced a recursive procedure for finding a root of an unknown expected-response function. Their original problem was root finding, not neural-network training, but it established a theoretical foundation for iterative updates driven by random measurements. (columbia.edu)

Gradient-based optimization fits this framework by treating the equation $\nabla F(\theta)=0$ as a root-finding problem and replacing its exact value with a sampled estimate. The resulting parameter sequence is a stochastic process, whose convergence must account for both the objective’s geometry and the accumulated sampling noise. (leon.bottou.org)

Convergence and step sizes

Convergence guarantees require assumptions; unbiasedness alone is insufficient. Typical analyses impose conditions on objective smoothness, gradient-estimator moments, and the stability of the iterates. A classical diminishing-step-size condition is

\sum_{t=1}^{\infty}\eta_t=\infty, \qquad \sum_{t=1}^{\infty}\eta_t^2<\infty.

The first condition prevents the total possible movement from becoming prematurely finite, while the second limits accumulated noise. A schedule proportional to $1/t$ satisfies both conditions, but its suitability still depends on the problem. (leon.bottou.org)

For convex optimization, appropriate schedules and assumptions yield expected objective-error bounds of order $T^{-1/2}$ , commonly for averaged iterates. Strong convexity can improve the rate to order $T^{-1}$ . For smooth nonconvex objectives, guarantees generally concern approximate stationarity, such as a small expected squared gradient norm, rather than discovery of a global minimum. These distinctions matter in deep learning, where training objectives are usually nonconvex. (leon.bottou.org)

With persistent gradient noise, a fixed learning rate generally leaves fluctuations around a solution rather than ensuring exact convergence. Smaller steps, increasing batch sizes, or averaging iterates can improve final accuracy, subject to the relevant assumptions. (leon.bottou.org)

Related optimization methods

Momentum modifies SGD by accumulating a decaying history of gradients. One convention is

v_{t+1}=\mu v_t+g_t, \qquad \theta_{t+1}=\theta_t-\eta_t v_{t+1}.

This reinforces repeatedly aligned directions and can reduce oscillation across directions with different curvature. (deeplearningbook.org)

AdaGrad adjusts coordinate-wise step sizes using accumulated squared gradients, adapting updates to previously observed gradient geometry. Adam combines adaptive scaling with exponentially weighted estimates of first and second gradient moments and corrections for their initial bias. Both use stochastic gradients, but neither is identical to plain SGD. Their behavior and theoretical guarantees depend on the objective, assumptions, and implementation. (jmlr.org)

Optimization and generalization

SGD specifies how parameters change; backpropagation specifies how neural-network gradients are computed. The two are therefore complementary rather than interchangeable. SGD can also optimize models such as linear regression and logistic regression, without requiring a neural-network architecture. (deeplearningbook.org)

Reducing training loss is distinct from improving predictions on unseen observations. Regularization would be incorrectly capitalized as an ID; the relevant concept is regularization, which modifies learning to constrain model fitting. Early stopping limits training using validation performance and can help control overfitting. Stochastic updates do not, by themselves, guarantee good generalization. (deeplearningbook.org)