Expected-average stationarity under aligned stochastic directions

Given: AC; the objective, filtered process, SGD updates, conditional direction moments, pathwise lower bound, and either stepsize regime in the Statement.

The Axiom of Choice: AC supplies the conditional-expectation classes used in this theorem.

The local alignment hypothesis is $⟨g_t,m_t⟩\ge \mu \mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2^2$ almost surely, with $\mu >0$.

The local conditional-mean norm hypothesis is $\mathrm{\parallel }{m}_t{\mathrm{\parallel }}_2\le {\mu }_G\mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2$ almost surely, with ${\mu }_G\ge \mu$.

The local conditional-variance hypothesis is $\mathrm{Var}(G_t\mid {\mathcal{F}}_t)\le M+M_V\mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2^2$ almost surely, with $M,M_V\ge 0$.

The objective lower bound is $f(x_t)\ge F_{\inf }$ almost surely at each iterate.

Stochastic gradient descent: the algorithm uses $x_{t+1}=x_t-{\alpha }_t{G}_t$ and imposes no moment or unbiasedness conclusion by itself.

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: oracle vectors are adapted; conditional means and vector conditional variances are coordinatewise; the second-moment identity is $\mathbb{E}[\mathrm{\parallel }{G}_t{\mathrm{\parallel }}_2^2\mid {\mathcal{F}}_t]=\mathrm{\parallel }{m}_t{\mathrm{\parallel }}_2^2+\mathrm{Var}(G_t\mid {\mathcal{F}}_t)$.

Filtration and filtered probability space: ${\mathcal{F}}_t\subseteq {\mathcal{F}}_{t+1}\subseteq \mathcal{F}$.

Adapted and integrable stochastic process: an adapted vector process is measurable at its stated time, and integrability is timewise.

Random elements and real random variables: a vector-valued random element is a measurable map into ${\mathbb{R}}^d$.

Conditional expectation as an ae class: under AC, conditional expectations are almost-sure classes and their equalities are almost-sure equalities.

Conditional variance and Conditional variance is well-defined and has the second-moment formula: conditional variance is the sum of coordinate variances and yields the vector second-moment identity in [F2].

Martingale difference sequence: an integrable adapted sequence with conditional mean zero at the preceding filtration time is a martingale-difference sequence.

Descent inequality for a Lipschitz gradient: $f(y)\le f(x)+⟨\mathrm{\nabla }f(x),y-x⟩+(L\mathrm{/}2)\mathrm{\parallel }y-x{\mathrm{\parallel }}_2^2$.

Taking out what is known: an integrable product with a finite measurable factor may be taken outside conditional expectation when both products are integrable.

Basic algebra and order properties of conditional expectation: conditional expectation is linear, preserves order, and preserves ordinary expectation.

Tower property of conditional expectation: nested conditional expectations satisfy the tower identity.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the inner product and norm are the coordinatewise Euclidean ones.

Cauchy-Schwarz $\mid ⟨x,y⟩\mid \le \parallel x{\parallel }_2\parallel y{\parallel }_2$ with its equality case, the triangle inequality for $\parallel \cdot {\parallel }_2$, the parallelogram law and polarisation: $\mathrm{\mid }⟨u,v⟩\mathrm{\mid }\le \mathrm{\parallel }u{\mathrm{\parallel }}_2\mathrm{\parallel }v{\mathrm{\parallel }}_2$ and the Euclidean norm satisfies the triangle inequality.

Expectation of a nonnegative or integrable random variable: expectation is the Lebesgue integral, finite for integrable real random variables.

Finite-horizon SGD trajectories have integrable objectives: finite-horizon SGD iterates, their gradients, and objective values have the integrability needed for conditional expectations and telescoping.