Stochastic gradient descent and random-iterate guarantees — Examples

For a fixed horizon $N$, let ${\mathcal{F}}_t$ be generated by ${\xi }_0,\dots ,{\xi }_{t-1}$, with ${\mathcal{F}}_0$ trivial and ${\mathcal{F}}_t={\mathcal{F}}_N$ for $t>N$. Apply [F1] with $y_s=x_{s-1}$, $H_s=G_{s-1}$, and ${\mathcal{H}}_s={\mathcal{F}}_{s-1}$ for $s\ge 1$, setting ${\mathcal{H}}_0={\mathcal{F}}_0$; this gives exactly the zero-based recurrence in the Example. For $0\le t<N$ and each prefix atom $A$, define $C_{t}H$ on $A$ as the average of $H$ over its $2^{N-t}$ extensions. This is an explicit ${\mathcal{F}}_t$-measurable function, and finite summation gives ${\int }_B{C}_{t}HdP={\int }_{B}HdP$ for every $B\in {\mathcal{F}}_t$, since $B$ is a union of prefix atoms. Half the extensions of each prefix have each next sign, so $C_t{\xi }_t=0$ and $C_t({\xi }_t^2)=1$. The recurrence makes $x_t$ constant on each prefix, hence $C_t{G}_t=x_t+b$ and $C_t[(G_t-(x_t+b){)}^2]={\sigma }^2$ for $G_t=x_t+b+\sigma {\xi }_t$. All variables have finite moments on the finite space; these averages and identities require no AC.

Put $m_t=\mathbb{E}[x_t]$. The update is $x_{t+1}=q{x}_t-\alpha b-\alpha \sigma {\xi }_t$, hence $m_{t+1}=q{m}_t-\alpha b$ with $m_0=x_0$. Induction gives $m_t=q^t{x}_0-b(1-q^t)$ for every $t\le N$.

Let $V_t=\mathbb{E}[(x_t-m_t{)}^2]$. Averaging first over each prefix atom as in step 1.1 gives $\mathbb{E}[(x_t-m_t){\xi }_t]=0$ and $\mathbb{E}[{\xi }_t^2]=1$, so the cross term vanishes and $V_{t+1}=q^2{V}_t+{\alpha }^2{\sigma }^2$, with $V_0=0$. Thus $V_t={\alpha }^2{\sigma }^2{\sum }_{j=0}^{t-1}{q}^{2j}=\frac{\alpha {\sigma }^2}{2-\alpha }(1-q^{2t})$, since $1-q^2=\alpha (2-\alpha )$. Adding $m_t^2$ proves the displayed moment formula, and it is independent of the chosen horizon whenever $N\ge t$.

Now assume AC for the published bounds. The event-integral identities in step 1.1 identify its finite averages with the conditional-expectation classes [F5] and their conditional variances [F6]. Here $f^{\mathrm{\prime }}(x)=x$ and $\mathrm{\mid }{f}^{\mathrm{\prime }}(u)-f^{\mathrm{\prime }}(v)\mathrm{\mid }=\mathrm{\mid }u-v\mathrm{\mid }$, so the gradient is $1$-Lipschitz. The deterministic start and all directions are square-integrable by step 1.1, and $f(x)\ge 0$. In the unbiased case, $L=1$, $f_{\inf }=0$, $\mathrm{\Delta }=x_0^2\mathrm{/}2$, and step 1.1 verifies conditional unbiasedness and variance ${\sigma }^2$; $\alpha \le 1\mathrm{/}4\le 1\mathrm{/}L$. Use [F8] with $p_k=1\mathrm{/}N$ and apply [F9] to obtain $\mathbb{E}\mathrm{\mid }{x}_{R_N}{\mathrm{\mid }}^2\le x_0^2\mathrm{/}(\alpha N)+\alpha {\sigma }^2$.

Here $q=1-\alpha \in [3\mathrm{/}4,1)$, so [F7] gives $q^t\to 0$. The formula in step 2.1 therefore yields $\mathbb{E}[x_t^2]\to b^2+\alpha {\sigma }^2\mathrm{/}(2-\alpha )$; if $b=0<\sigma$, this limit is strictly positive. This proves the exact constant-step noise-floor claim without using AC.

For general $b$, step 1.1 verifies conditional mean $f^{\mathrm{\prime }}(x_t)+b$, bias bound $\beta =\mathrm{\mid }b\mathrm{\mid }$, variance bound ${\sigma }^2$, and $f(x)\ge 0$. The step restriction is $\alpha \le 1\mathrm{/}(4L)$ because $L=1$. Apply [F10] with $\mathrm{\Delta }=x_0^2\mathrm{/}2$ to obtain $N^{-1}{\sum }_{t=0}^{N-1}\mathbb{E}[x_t^2]\le x_0^2\mathrm{/}(\alpha N)+(5\mathrm{/}2)b^2+\alpha {\sigma }^2$. The exact limiting floor from step 3.1 is at most $b^2+\alpha {\sigma }^2$, since $2-\alpha \ge 1$, and is therefore consistent with this bound.

Each $h_{\theta }$ is measurable on the singleton instance space, and the squared loss is continuous, hence measurable; with the stated nonempty predictor class and probability law, these data satisfy the supervised-problem interface [F1]. By the empirical-risk definition [F2], $F_S(\theta )={\widehat{R}}_S(h_{\theta })=\frac{1}{2m}{\sum }_{i=1}^m(\theta -y_i{)}^2$. For $h\mathrm{\ne }0$, $[F_S(\theta +h)-F_S(\theta )]\mathrm{/}h=m^{-1}{\sum }_i(\theta -y_i)+h\mathrm{/}2=\theta -\bar{y}+h\mathrm{/}2$, whose limit as $h\to 0$ is $\theta -\bar{y}$ by [F3]. Expanding around $\bar{y}$ also gives $F_S(\theta )=\frac{1}{2}(\theta -\bar{y}{)}^2+v_S\mathrm{/}2$, so $F_S^{\mathrm{\prime }}(\theta )=\theta -\bar{y}$, its gradient is $1$-Lipschitz, and its global infimum is $v_S\mathrm{/}2$.

Conditional on any past index batches, each new batch tuple is uniform on $\{1,\dots ,m{\}}^b$. For each component, $\mathbb{E}[{\theta }_t-y_{I_{t,j}}\mid {\mathcal{F}}_t]={\theta }_t-\bar{y}$. Its centered value is $\bar{y}-y_{I_{t,j}}$, with conditional second moment $v_S$; for $i\mathrm{\ne }j$, the cross moment is $m^{-2}({\sum }_r(\bar{y}-y_r){)}^2=0$. Therefore the average direction has conditional mean ${\theta }_t-\bar{y}$ and conditional variance $b^{-2}(b{v}_S)=v_S\mathrm{/}b$.

The mean and variance in step 1.2 satisfy the unbiased branch of [F10] with $\mu ={\mu }_G=1$, $M=v_S\mathrm{/}b$, $M_V=0$, $L=1$, and $F_{\inf }=v_S\mathrm{/}2$. Since $0<\alpha \le 1=\mu \mathrm{/}(L{M}_G)$, substitute these values into [F10] to obtain the displayed expected-average bound. The data sample $S$ is fixed throughout; no expectation over a population law is used.

The singleton measure has total mass one and is countably additive because at most one set in any disjoint sequence can be nonempty [F5]. By [F3], $\mathrm{\nabla }f(x)=x$ and $f(x)=x^2\mathrm{/}2$. The deterministic direction has conditional mean $-x_t$ and conditional variance zero on the trivial filtration. For any finite horizon, apply [F1] with $y_s=x_{s-1}$, $H_s=-y_s=G_{s-1}$ for $s\ge 1$, and ${\mathcal{H}}_s=\mathcal{F}$ for $s\ge 0$. Its positive-time update $y_{s+1}=y_s-\alpha H_s$ becomes $x_{t+1}=x_t-\alpha (-x_t)=(1+\alpha )x_t$ for $t=s-1\ge 0$.

The recurrence in step 1.1 and $1+\alpha >0$ give $x_t=(1+\alpha {)}^t{x}_0\mathrm{\ne }0$ for every $t\ge 0$ by [F4]. In particular, $f(x_1)=(1+\alpha {)}^2{x}_0^2\mathrm{/}2>x_0^2\mathrm{/}2=f(x_0)$, so this direction can increase the objective in one step.

For every $t$, step 2.1 gives $x_t\mathrm{\ne }0$, so $\mathrm{\nabla }f(x_t)\mathbb{E}[G_t\mid {\mathcal{F}}_t]=x_t(-x_t)=-x_t^2<0$, whereas $\mu \mathrm{\mid }\mathrm{\nabla }f(x_t){\mathrm{\mid }}^2=\mu x_t^2>0$ for every $\mu >0$. Therefore the local positive-alignment hypothesis [F2] fails at every iterate, despite the direction norm equaling the gradient norm and the variance being zero. This comparison invokes the theorem only in its AC branch [A1]; the displayed deterministic calculation does not use AC.