Option II controls track gradients at stored client anchors

At initialization, ${\alpha }_{i,k}^0=x_0$, [given] ${\gamma }_{i,k}^0=\mathrm{\nabla }{f}_i(x_0)$ and $c_i^0=\mathrm{\nabla }{f}_i(x_0)$, so all three client-control assertions hold for $r=0$. Suppose client $i$ is selected in round $r$. Telescoping its $K$ local updates from [F1] gives $x_{r-1}-y_{i,K}^r={\eta }_l{\sum }_{k=1}^K(g_i(y_{i,k-1}^r)-c_i^{r-1}+c^{r-1})\mathrm{.}$ Substitute this into Option II and cancel the old controls. The result is $c_i^r=K^{-1}{\sum }_k{\gamma }_{i,k}^r$. For ${\xi }_{i,k}={\gamma }_{i,k}^r-\mathrm{\nabla }{f}_i({\alpha }_{i,k}^r)$, conditional unbiasedness gives zero conditional mean at the query, and the sequential ${\xi }_{i,k}$ form martingale differences. Thus $\mathbb{E}⟨{\xi }_{i,k},{\xi }_{i,j}⟩=0$ for $k\mathrm{\ne }j$ by conditioning on the later query history, and $\mathbb{E}{\parallel \frac{1}{K}{\sum }_k{\xi }_{i,k}\parallel }_2^2=\frac{1}{K^2}{\sum }_k\mathbb{E}\mathrm{\parallel }{\xi }_{i,k}{\mathrm{\parallel }}_2^2\le \frac{{\sigma }^2}{K}\mathrm{.}$ Taking expectation in the exact control identity also gives the stated mean identity.

If client $i$ is unselected, [F1] leaves $c_i^r=c_i^{r-1}$ and [F2] leaves every stored anchor and draw unchanged. Write $e_i^r=c_i^r-K^{-1}{\sum }_k\mathrm{\nabla }{f}_i({\alpha }_{i,k}^r)$ and $p=S\mathrm{/}N$. The fresh client sample is independent of the preceding history, so the retained residual contributes $(1-p)\mathbb{E}[e_i^{r-1}]$ to its mean and $(1-p)\mathbb{E}\mathrm{\parallel }{e}_i^{r-1}{\mathrm{\parallel }}_2^2$ to its second moment. Conditional on selection, step 1.1 gives a newly sampled residual of mean zero and second moment at most ${\sigma }^2\mathrm{/}K$. Therefore $\mathbb{E}[e_i^r]=(1-p)\mathbb{E}[e_i^{r-1}]=0$ and $\mathbb{E}\mathrm{\parallel }{e}_i^r{\mathrm{\parallel }}_2^2\le (1-p)\mathbb{E}\mathrm{\parallel }{e}_i^{r-1}{\mathrm{\parallel }}_2^2+p{\sigma }^2\mathrm{/}K\le {\sigma }^2\mathrm{/}K$ by induction from $e_i^0=0$. The realized control identity persists in both cases. This proves the three assertions; no conditional-mean identity given the stored adaptive anchors is asserted.

Initially $c^0=N^{-1}{\sum }_i{c}_i^0$. In a round, the server changes its control by $(S\mathrm{/}N)(S^{-1}{\sum }_{i\in \mathcal{S}}(c_i^r-c_i^{r-1}))$, which equals $N^{-1}{\sum }_i(c_i^r-c_i^{r-1})$ because unselected clients do not change their controls. Therefore $c^r=N^{-1}{\sum }_i{c}_i^r$ whenever the identity held before the round. Induction proves it for every round.