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.