Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates

Fix a finite dimension $d\ge 1$ and a discrete filtered probability space $(\mathrm{\Omega },\mathcal{F},({\mathcal{F}}_k{)}_{k\ge 0},P)$ as in Filtration and filtered probability space. A sequence $x_k:\mathrm{\Omega }\to {\mathbb{R}}^d$ is an iterate process when each coordinate is ${\mathcal{F}}_k$-measurable; a sequence $G_k:\mathrm{\Omega }\to {\mathbb{R}}^d$ is an oracle process when each coordinate is ${\mathcal{F}}_{k+1}$-measurable. These are coordinatewise instances of Random elements and real random variables and Adapted and integrable stochastic process. Assume the coordinates used in a conditional moment are square-integrable.

For deterministic stepsizes ${\alpha }_k>0$, the unconstrained Robbins–Monro/SGD update is $x_{k+1}=x_k-{\alpha }_k{G}_k\mathrm{.}$ For a differentiable objective $f:{\mathbb{R}}^d\to \mathbb{R}$, the oracle is conditionally unbiased when $\mathbb{E}[G_k\mid {\mathcal{F}}_k]=\mathrm{\nabla }f(x_k)$ coordinatewise almost surely; it has conditional bias $b_k$ when $\mathbb{E}[G_k\mid {\mathcal{F}}_k]=\mathrm{\nabla }f(x_k)+b_k$. The conditional variance of a vector is the sum of the scalar conditional variances of its coordinates, using Conditional variance. By Conditional variance is well-defined and has the second-moment formula, it satisfies $\mathbb{E}[\mathrm{\parallel }{G}_k{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_k]=\mathrm{\parallel }\mathbb{E}[G_k\mid {\mathcal{F}}_k]{\mathrm{\parallel }}_2^2+\mathrm{Var}(G_k\mid {\mathcal{F}}_k)$ almost surely. All conditional expectations are coordinatewise instances of Conditional expectation as an ae class, whose existence assumes the The Axiom of Choice. No independence across iterations is part of this definition.

The conditional second-moment bound $\mathbb{E}[\mathrm{\parallel }{G}_k{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_k]\le M_k^2$ and the conditional variance bound $\mathrm{Var}(G_k\mid {\mathcal{F}}_k)\le {\sigma }_k^2$ are distinct hypotheses; the latter combines with conditional unbiasedness through the displayed identity.