Stochastic gradient descent

Stochastic gradient descent updates an optimization parameter using a random estimate of the gradient:For a finite-sum objective $f(x)=m^{-1}{\sum }_{i=1}^m{f}_i(x)$, selecting an index uniformly and taking $G_k=\nabla f_{I_k}(x_k)$ gives an unbiased stochastic gradient. Averaging several selected gradients gives a mini-batch gradient. The saving is fewer component evaluations per update, while the randomness adds variance. Unbiasedness or a controlled bias is an assumption, rather than an automatic property of any approximate gradient.^[ref]

A simple noise example is $f(x)=x^2/2$ and $G_k=x_k+{\xi }_k$, where independent centered noises have variance ${\sigma }^2$. With a constant step size $0<\eta <2$,Its mean tends to zero, but its limiting variance is $\eta {\sigma }^2/(2-\eta )$: solve $v=(1-\eta {)}^{2}v+{\eta }^2{\sigma }^2$. Thus constant steps can leave a stochastic gradient noise floor even for this strictly convex quadratic. Smaller or diminishing steps change the balance between progress and noise; a nonconvex stationarity estimate must not be read as guaranteed convergence to a global minimum.

SGDR means stochastic gradient descent with warm restarts. Its learning rate schedule repeatedly lowers the learning rate along a cosine curve, then raises it to begin another cycle while retaining the current parameters. Ilya Loshchilov and Frank Hutter's method uses this warm restart to continue an existing optimization trajectory.^[ref]

In cycle $i$, let $s$ be elapsed training time since the last restart and $T_i>0$ the cycle duration, measured in the same units. The cosine learning rate schedule isIt starts at ${\eta }_{\max ,i}$, reaches the midpoint of the two bounds at $s=T_i/2$, and reaches ${\eta }_{\min ,i}$ at the cycle endpoint. The original implementation updates the elapsed training epoch count within each mini-batch, allowing fractional epoch progress.^[ref]

For an original schedule, choose bounds 0 and 0.1, initial duration $T_0=4$ epochs and duration multiplier 2. The successive cycle lengths are 4, 8 and 16 epochs, with restart boundaries at total elapsed times 4, 12 and 28. In the first continuous cycle, the rates at $s=0,2,4$ are respectively $0.1,0.05,0$.

A discrete convention must specify which update uses the endpoint. For example, sampling phases $s=0,1,2,3$ in the first cycle and restarting before the next step gives rates approximately $0.1,0.08536,0.05,0.01464$, followed by $0.1$. The zero endpoint in the continuous curve is then a limit, rather than an additional zero-rate optimizer step.

Retaining parameters also has a concrete meaning. In an original deterministic gradient descent example with $f(\theta )={\theta }^2/2$ and current $\theta =0.5$, resetting only the schedule leaves $\theta =0.5$. The next step at learning rate0.1 gives0.45; a step at0.01 would give0.495. The restart changes the next movement rather than drawing a new initial parameter. Handling a momentum buffer is a further state convention; restarting the schedule and discarding all optimizer state are different operations. Record cycle phase, durations and rate bounds with an optimization checkpoint.

A mini-batch is a group of training examples processed together in one iteration of a learning algorithm. Its batch size counts examples, while a training epoch usually counts one pass over the available training data. In stochastic gradient descent, a mini-batch gradient combines the component gradients from the selected examples; the group of examples and the resulting numerical estimate are distinct objects.^[ref]

For an original counting example, partition eight examples into mini-batches with nominal batch size three and retain the final partial group. The sizes are $3,3,2$, giving three updates in one training epoch if each group produces one update. Discarding the final partial group changes which observations participate.

Unequal group sizes also matter when reporting a loss function. At fixed model parameters, suppose the three mini-batch mean losses are $1,1,10$. Their unweighted mean is $4$, but the mean over all eight examples isThe smaller last group must not receive the same weight as a larger group when the intended statistic is a per-example sample mean. This bookkeeping issue is separate from the randomness used to select a mini-batch.

Batch size counts the examples combined in a mini-batch. In the simple stochastic gradient descent loop where each group produces one parameter update, it controls how many examples contribute to that update. It differs from a training epoch, which counts a pass over the available training data.^[ref]

For an original counting example, partition ten examples with nominal batch size $b=4$ and retain the remainder. The actual sizes are $4,4,2$, giving $\lceil 10/4\rceil =3$ updates per training epoch. Discarding the remainder instead gives two updates and uses only eight examples. More generally the retained-remainder update count is $\lceil n/b\rceil$ for $n$ examples, provided there is one update per group.

Batch size also changes gradient sampling noise. If independently sampled component gradients at a fixed parameter have scalar variance ${\sigma }^2$, their sample mean hasFor an original exact example, suppose one component gradient is equally likely to be 0 or 2. Its mean is 1 and variance is 1. A two-example mini-batch gradient takes values $0,1,2$ with probabilities $1/4,1/2,1/4$, giving variance $1/2$. This calculation holds parameters fixed and assumes independent sampling; sampling without replacement has a finite population correction.

With gradient accumulation, several groups may contribute before an update. Two full four-example groups then involve eight examples per update if their gradients are normalized consistently. State whether a reported size counts the processed group or all examples contributing to an update. Lower sampling variance alone does not establish faster training for a fixed computation budget.

Gradient accumulation combines gradient contributions from several processed mini-batches before one optimizer update. Parameters stay fixed while those contributions are evaluated. With consistent normalization, an additive per-example loss function can therefore use an effective batch size larger than the group processed at once.^[ref]

For an original example, let per-example scalar gradients be $1,3,8$ at the same parameter value. Process the first two together and the last separately. Their means are 2 and 8. The combined per-example mean isThe unweighted mean of group means is 5 and gives the smaller group too much weight. One implementation accumulates each group's summed loss divided by the total example count, then performs one update.

Accumulation is also different from consecutive updates. Let $f_i(\theta )=(\theta -a_i{)}^2/2$, with $a=(-1,-3,-8)$, starting at $\theta =0$ and using step size $0.1$. One accumulated mean-gradient step gives $\theta =-0.4$. Updating first on the two-example mean gives $\theta =-0.2$; the last example then has gradient $7.8$, and a second step gives $\theta =-0.98$.

The distinction is where the gradients are evaluated. Agreement with one larger group requires fixed parameters and compatible model state, additive losses and consistent weighting. A method whose calculations depend on the whole group can violate those assumptions. State whether batch size denotes a processed group or the complete set contributing to an update.

The effective batch size counts the example contributions combined in one optimizer update, including gradient accumulation and contributions from parallel workers. With $P$ workers, $a$ accumulated groups per worker and $b$ examples in each full group,The PyTorch documentation uses this count to specify when accumulated gradients are unscaled and the optimizer is stepped.^[ref]

For an original example, two workers each process three groups of four examples before updating: $b_{\mathrm{eff}}=2\cdot 3\cdot 4=24$. For an additive per-example loss function, the desired gradient is $24^{-1}{\sum }_{i=1}^{24}\nabla f_i(\theta )$, evaluated at unchanged parameters $\theta$. If each worker accumulates the three group-mean gradients divided by three, then averaging the two workers' results gives that normalization. Summing the workers instead would double the gradient.

Incomplete groups require their actual counts. Group sizes $4,4,2$ on each of two workers give $b_{\mathrm{eff}}=20$, and the combined mini-batch gradient weights each group mean by its example count. Dividing all six group means by six would overweight the two-example groups.

The count describes contributions, not necessarily distinct examples. If both workers process the same twelve example identifiers, there are 24 contributions but only twelve distinct examples. The usual inverse-count reduction of variance requires assumptions about independent random variables; duplication can violate them. Nor does this bookkeeping by itself establish a rule for changing the learning rate.

A mini-batch gradient averages gradients of several sampled components of a finite-sum objective. For $F(x)=n^{-1}{\sum }_{i=1}^n{f}_i(x)$ and batch indices $I_1,\dots ,I_b$,With independent uniform draws at fixed $x$, it is an unbiased stochastic gradient: $\mathbb{E}{G}_b(x)=\nabla F(x)$. Its covariance matrix is $\Sigma (x)/b$, where $\Sigma (x)$ is the covariance of one sampled gradient. The factor follows because centered independent cross terms have expectation zero.

If the indices are sampled uniformly without replacement, the covariance is instead $(n-b)\Sigma (x)/(b(n-1))$ for $n>1$, when $\Sigma$ uses the uniform-population normalization. At $b=n$ this gives the exact full gradient. Larger batches reduce sampling variance but require more component evaluations per update; biased sampling or data dependence requires its own analysis.

Suppose a fixed-step size stochastic gradient descent iteration satisfiesand $f$ has a global minimizer $x^{\ast }$. Taking expectations and forming a telescoping sum proves the displayed bound with ${\Delta }_0=f(X^0)-f(x^{\ast })$ and deterministic $X^0$. The Cauchy-Schwarz inequality then bounds the averaged, or the best, expected gradient Euclidean norm by $\sqrt{M+2L{\Delta }_0/k}$. This is a guarantee of stationarity in the indicated senses, rather than a last-iterate convergence assertion. The additive $M$ is a stochastic gradient noise floor.

Target: real-analysis.bigb, under Strongly convex function.

A residual accuracy level in a bound for stochastic gradient descent with a fixed step size and nonvanishing gradient noise. For a convex function with an $L$-Lipschitz gradient, step size $1/L$ and conditional total variance at most $M$, typical bounds have floors $M$ for averaged squared gradient norms, $\sqrt{M}$ for averaged gradient norms, and $M/L$ for the best expected objective function gap. Such floors are upper bounds depending on the analysis and assumptions, rather than claims that these exact values are attained or that every last iterate converges.

Target: gradient-descent.bigb, under Stochastic gradient descent.

Projected stochastic gradient descent combines a random gradient step with the Euclidean projection onto a convex set:In a finite-dimensional Euclidean space, a nonempty closed convex set $C$ has a unique projection. This ensures that the iteration is well defined and feasible. For the scalar constraint $C=[0,\infty )$, the update is simply $x_{k+1}=\max (0,x_k-{\eta }_k{G}_k)$.

For every feasible $x^{\ast }$, projection is nonexpansive and fixes $x^{\ast }$, so $\Vert x_{k+1}-x^{\ast }{\Vert }_2\le \Vert x_k-{\eta }_k{G}_k-x^{\ast }{\Vert }_2$. This inequality underlies convergence estimates after taking conditional expectations. On a general closed nonconvex feasible set, nearest points may not be unique and this convex projection argument does not apply.

A random vector $G_k$ is an unbiased stochastic gradient at an iterate $x_k$ ifFor an adaptive iteration it is often useful to require the stronger historical condition $\mathbb{E}[G_k\mid {\mathcal{F}}_k]=\nabla f(x_k)$, where ${\mathcal{F}}_k$ contains all information available before drawing the new sample. This states explicitly which information is held fixed in the conditional expectation.

For $f=m^{-1}{\sum }_i{f}_i$, a conditionally uniform index $I_k$ gives $G_k=\nabla f_{I_k}(x_k)$. If index $i$ instead has positive sampling probability $p_i$, then $\nabla f_i(x_k)/(m{p}_i)$ is the correctly weighted estimate. Omitting these factors generally changes its expectation.

For example, average $f_1(x)=(x-1{)}^2/2$ and $f_2(x)=(x+1{)}^2/2$. The two sampled gradients are $x-1$ and $x+1$, whose average is the true gradient $x$. At the minimizer zero, each sample is nonzero even though its mean vanishes; unbiasedness does not mean zero variance.

For an unbiased stochastic gradient $H$ at $X$ with finite conditional second moment, expand $H=\nabla f(X)+(H-\nabla f(X))$ in the squared Euclidean norm. The cross term has zero conditional expectation, which proves the displayed identity. It separates the squared true gradient from the total conditional variance of its random estimate.

Target: gradient-descent.bigb, under Stochastic gradient descent.