Uniform empirical-risk sampling gives an unbiased bounded-variance gradient

Assume AC for the conditional-expectation stationarity bound below. Take instance space $(\{\ast \},2^{\{\ast \}})$, action and label spaces $(\mathbb{R},\mathcal{B}(\mathbb{R}))$, the population law $P_{\mathrm{p}\mathrm{o}\mathrm{p}}={\delta }_{(\ast ,0)}$, the nonempty predictor class $\mathcal{F}=\{h_{\theta }:\theta \in \mathbb{R}\}$ with $h_{\theta }(\ast )=\theta$, and squared loss $\mathrm{\ell }(a,y)=\frac{1}{2}(a-y{)}^2$. Fix an ordered sample $S=((\ast ,y_1),\dots ,(\ast ,y_m))$ of integer length $m\ge 1$ with $y_i\in \mathbb{R}$, and let $\bar{y}=m^{-1}{\sum }_i{y}_i$ and $v_S=m^{-1}{\sum }_i(y_i-\bar{y}{)}^2$. Fix a deterministic initial parameter ${\theta }_1\in \mathbb{R}$, a constant stepsize $0<\alpha \le 1$, an integer batch size $b\ge 1$, and an integer horizon $T\ge 1$. On the finite uniform probability space $(\mathrm{\Omega },2^{\mathrm{\Omega }},Q)$, where $\mathrm{\Omega }=\{1,\dots ,m{\}}^{bT}$ and each point has $Q$-mass $m^{-bT}$, write $I_{t,j}$ for the coordinate indices, independently uniform with replacement, for $1\le t\le T$ and $1\le j\le b$. Set ${\mathcal{F}}_t=\sigma (I_{s,j}:1\le s<t,1\le j\le b)$ for $1\le t\le T+1$, set ${\mathcal{F}}_0={\mathcal{F}}_1=\{\mathrm{\varnothing },\mathrm{\Omega }\}$, and set ${\mathcal{F}}_t={\mathcal{F}}_{T+1}$ for $t>T+1$. At each iteration $t=1,\dots ,T$, average the component gradients to form $G_t=b^{-1}{\sum }_{j=1}^b({\theta }_t-y_{I_{t,j}})$ and set ${\theta }_{t+1}={\theta }_t-\alpha G_t$. For the fixed-sample empirical risk ${\widehat{R}}_S(h_{\theta })$, this direction has conditional mean ${\mathbb{E}}_Q[G_t\mid {\mathcal{F}}_t]={\theta }_t-\bar{y}=\frac{d}{d\theta }{\widehat{R}}_S(h_{{\theta }_t})$ and conditional variance ${\mathrm{Var}}_Q(G_t\mid {\mathcal{F}}_t)=v_S\mathrm{/}b$. The objective has $1$-Lipschitz gradient and global infimum $v_S\mathrm{/}2$, so the expected-average theorem yields $\frac{1}{T}{\sum }_{t=1}^T{\mathbb{E}}_Q{\mid \frac{d}{d\theta }{\widehat{R}}_S(h_{{\theta }_t})\mid }^2\le \frac{\alpha v_S}{b}+\frac{({\theta }_1-\bar{y}{)}^2}{T\alpha }\mathrm{.}$ The sampling law here is over the fixed empirical sample; no population-risk gradient identity is asserted.

Supervised prediction-problem definition: fixes the measurable prediction and loss setting.

Population and empirical-risk definition: defines the fixed-sample empirical objective.

Minibatch SGD procedure: specifies the averaged direction and update.

Expected-average stationarity theorem: supplies the conditional-moment guarantee applied here.