= Stochastic gradient descent
{wiki}
<Stochastic gradient descent> updates an optimization parameter using a random estimate of the <gradient>:
$$
x_{k+1}=x_k-\eta_kG_k,\qquad \eta_k>0.
$$
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.https://leon.bottou.org/publications/pdf/sirev-2018.pdf[Bottou, Curtis and Nocedal, Optimization Methods for Large-Scale Machine Learning, §4, stochastic-gradient formulation and noise/stepsize trade-offs]{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$,
$$
x_{k+1}=(1-\eta)x_k-\eta\xi_k.
$$
Its mean tends to zero, but its limiting <variance> is $\eta\sigma^2/(2-\eta)$: solve $v=(1-\eta)^2v+\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>.
Back to article page
