Stochastic gradient descent replaces an exact gradient by a noisy but cheap estimate. Its analysis must balance deterministic contraction against the variance injected at every iteration.
Stochastic first-order oracle
Definition. Let \(\mathcal F_k\) contain the iterates and randomness observed through time \(k\). A stochastic gradient \(G_k\) at \(x_k\) is conditionally unbiased if \[ \mathbb E[G_k\mid\mathcal F_k]=\nabla f(x_k). \] Stochastic gradient descent is \[ x_{k+1}=x_k-\eta_kG_k. \] A common noise condition is \(\mathbb E[\|G_k-\nabla f(x_k)\|^2\mid\mathcal F_k]\le\sigma^2\).
For a finite-sum objective \(f(x)=n^{-1}\sum_{i=1}^nf_i(x)\), drawing \(I_k\) uniformly and setting \(G_k=\nabla f_{I_k}(x_k)\) is unbiased. A mini-batch average reduces the conditional variance approximately by the batch size when its draws are independent.
The basic squared-distance recursion
Robbins-Monro recursion. Suppose \(f\) is \(\mu\)-strongly convex with minimizer \(x^\star\), the oracle is unbiased, and \(\mathbb E[\|G_k\|^2\mid\mathcal F_k]\le G^2\). Then \[ \mathbb E[\|x_{k+1}-x^\star\|^2\mid\mathcal F_k] \le(1-2\mu\eta_k)\|x_k-x^\star\|^2+\eta_k^2G^2. \]
Proof. Expand the update: \[ \|x_{k+1}-x^\star\|^2 =\|x_k-x^\star\|^2 -2\eta_k\langle G_k,x_k-x^\star\rangle +\eta_k^2\|G_k\|^2. \] Take conditional expectation. Strong convexity and \(\nabla f(x^\star)=0\) imply \(\langle\nabla f(x_k),x_k-x^\star\rangle \ge\mu\|x_k-x^\star\|^2\). Substitute the moment bound.
Decreasing steps and almost-sure convergence
Robbins-Monro convergence. Under the preceding conditions, if \[ \sum_{k=0}^\infty\eta_k=\infty,\qquad \sum_{k=0}^\infty\eta_k^2<\infty, \] then \(x_k\to x^\star\) almost surely. With \(\eta_k=1/(\mu(k+1))\), one obtains \[ \mathbb E\|x_k-x^\star\|^2=O\!\left(\frac{G^2}{\mu^2k}\right). \]
Proof outline. The squared-distance recursion has the form \[ \mathbb E[V_{k+1}\mid\mathcal F_k] \le V_k-2\mu\eta_kV_k+\eta_k^2G^2. \] Since the final terms are summable, the Robbins-Siegmund almost-supermartingale theorem implies that \(V_k\) converges and \(\sum_k\eta_kV_k<\infty\). The divergent sum of \(\eta_k\) forces the limit of \(V_k\) to be zero. For \(\eta_k=1/(\mu(k+1))\), induction in the deterministic expectation recursion yields the stated \(1/k\) bound.
Constant steps reach a noise floor
Stationary error scale. With a constant step \(0<\eta<1/(2\mu)\), the same recursion gives \[ \mathbb E\|x_k-x^\star\|^2 \le(1-2\mu\eta)^k\|x_0-x^\star\|^2 +\frac{\eta G^2}{2\mu}. \] Thus a larger step contracts faster but leaves a larger asymptotic neighborhood.
Proof. Iterate the affine recursion and sum the geometric series: \[ \eta^2G^2\sum_{j=0}^{k-1}(1-2\mu\eta)^j \le\frac{\eta G^2}{2\mu}. \]
Polyak-Ruppert averaging
For smooth stochastic approximation, the averaged iterate \[ \bar x_k=\frac1k\sum_{j=1}^kx_j \] can attain the optimal \(1/k\) mean-square scale under less delicate step-size tuning. Locally, write \[ \nabla f(x)\approx H(x-x^\star),\qquad G_k=\nabla f(x_k)+\xi_k. \] After averaging, the asymptotic covariance is \[ \sqrt{k}(\bar x_k-x^\star) \ \Longrightarrow\ N(0,H^{-1}\Sigma H^{-1}), \] where \(\Sigma\) is the covariance of the gradient noise at the optimum. This is the same sandwich form that appears in asymptotic statistics.
Algorithmic subsampling noise and statistical data noise are distinct. One can drive the first to zero by more computation, while the second determines the inferential accuracy of the empirical objective itself.