$\displaystyle=\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\left(\sum_{d\in\mathcal{B}^{(k),e}_{y}}\frac{\nabla
f(\mathbf{w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_{y}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})+\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right)\right\|^{2}\right]$
$\displaystyle\leq
2\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\underbrace{\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\left(\sum_{d\in\mathcal{B}^{(k),e}_{y}}\frac{\nabla
f(\mathbf{w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_{y}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right)\right\|^{2}\right]}_{(a)}$
$\displaystyle+2\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right\|^{2}\right].$

where the last inequality is obtained via Cauchy-Schwarz inequality. Note that
$\sum_{d\in\mathcal{B}^{(k),e}_{y}}\frac{\nabla
f(\mathbf{w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_{y}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})$ in the above expression corresponds to
the noise of SGD at local iteration $i$ at device $y$, which is zero mean and
iid across the devices and the iterations. Using these facts in term $(a)$ in
(55) implies

$\displaystyle\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}{\nabla{F}}_{y}^{\mathsf{C},(k)}\right\|^{2}\right]$
(56)
$\displaystyle=\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\right)^{2}\underbrace{\mathbb{E}_{k}\left[\left\|\sum_{e=1}^{e^{(k)}_{y}}\left(\sum_{d\in\mathcal{B}^{(k),e}_{y}}\frac{\nabla
f(\mathbf{w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_{y}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right)\right\|^{2}\right]}_{(a)}$
$\displaystyle+\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right\|^{2}\right].$

Using Lemma 2 (Appendix D) and the fact that SGD noise is zero mean, expanding
term $(a)$ in (56) yields

$\displaystyle\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}{\nabla{F}}_{y}^{\mathsf{C},(k)}\right\|^{2}\right]$
(57)
$\displaystyle\leq\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\right)^{2}\sum_{e=1}^{e^{(k)}_{y}}2\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}$
$\displaystyle+\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right\|^{2}\right].$

Replacing the above result back in (54), we get

$\displaystyle\mathbb{E}_{k}\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})-\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\bBigg@{4}[\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}+\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}$ (58)
$\displaystyle-\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}\bBigg@{4}]+\frac{\eta_{k}}{4}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}$
$\displaystyle+\eta_{k}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\right)^{2}\sum_{e=1}^{e^{(k)}_{y}}2\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}$
$\displaystyle+{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\mathbb{E}_{k}\left[\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right\|^{2}\right]$
$\displaystyle+{\beta\eta^{2}_{k}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right].$

With rearranging the terms in the above bound, we get

$\displaystyle\mathbb{E}_{k}\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})-\left(\frac{\eta_{k}}{4}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}$
(59)
$\displaystyle+\eta_{k}\left(\underbrace{\beta\eta_{k}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}-\frac{1}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}}_{(a)}\right)\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}$
$\displaystyle+\left(\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}$
$\displaystyle+{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\left(1+\beta{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]$
$\displaystyle+{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\right)^{2}\sum_{e=1}^{e^{(k)}_{y}}2\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$

Assuming
$\eta_{k}\leq\frac{{D}^{(k)}}{2\beta\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}$
makes term $(a)$ in the above expression negative and also implies
$1+\beta{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\leq\frac{3}{2}$.
Replacing these results in the above bound gives us

$\displaystyle\mathbb{E}_{k}\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})-\left(\frac{\eta_{k}}{4}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}$
(60)
$\displaystyle+\left(\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\underbrace{\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}}_{(a)}$
$\displaystyle+\frac{3}{2}{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+2{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$

We next aim to bound term $(a)$ in (60) as follows:

$\displaystyle\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}$ (61)
$\displaystyle=\left\|\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}}\nabla{F^{(k)}_{y}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}$
$\displaystyle{\leq}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\nabla{F^{(k)}_{y}(\mathbf{w}^{(k)})}-\frac{1}{e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}\right]$
$\displaystyle{\leq}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\sum_{e=1}^{e^{(k)}_{y}}\mathbb{E}_{k}\left[\left\|\nabla{F^{(k)}_{y}(\mathbf{w}^{(k)})}-{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}\right]\leq\beta^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\sum_{e=1}^{e^{(k)}_{y}}\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right],$

where we used Jensens's inequality and $\beta$-smoothness of the loss
functions.

We then bound the last term in the above bound as follows:

$\displaystyle\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right]{=}\eta_{k}^{2}\mathbb{E}_{k}\left[\left\|\sum_{e^{\prime}=1}^{e-1}\sum_{d\in\mathcal{B}^{(k),e^{\prime}}_{y}}{\frac{\nabla
f(\mathbf{w}^{(k),e^{\prime}-1}_{y},d)}{{B}^{(k)}_{y}}}\right\|^{2}\right]$
$\displaystyle=\eta_{k}^{2}\mathbb{E}_{k}\bBigg@{4}[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\Big{(}\sum_{d\in\mathcal{B}^{(k),e^{\prime}}_{y}}{\frac{\nabla
f(\mathbf{w}^{(k),e^{\prime}-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})+\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Big{)}\Bigg{\|}^{2}\bBigg@{4}]$
$\displaystyle{\leq}2\eta_{k}^{2}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\sum_{d\in\mathcal{B}^{(k),e^{\prime}}_{y}}{\frac{\nabla
f(\mathbf{w}^{(k),e^{\prime}-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]+2\eta_{k}^{2}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]$
$\displaystyle{=}{2\eta_{k}^{2}\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{d\in\mathcal{B}^{(k),e^{\prime}}_{y}}{\frac{\nabla
f(\mathbf{w}^{(k),e^{\prime}-1}_{y},d)}{{B}^{(k)}_{y}}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]}+{2\eta_{k}^{2}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]}$
$\displaystyle\leq
4(e-1)\eta_{k}^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}+\underbrace{2\eta_{k}^{2}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]}_{(a)},$
(62)

where we used Cauchy–Schwarz inequality, the fact that noise of SGD is zero
mean, and Lemma 2. We then bound term $(a)$ in (62) as follows:

$\displaystyle
2\eta_{k}^{2}\mathbb{E}_{k}\left[\Bigg{\|}\sum_{e^{\prime}=1}^{e-1}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})\Bigg{\|}^{2}\right]\leq
2\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})+\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}\right]$
$\displaystyle{\leq}4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}\right]+4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}$ $\displaystyle\leq
4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e^{\prime}-1}_{y})-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}\right]+4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}$ $\displaystyle\leq
4\eta_{k}^{2}\beta^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\mathbf{w}^{(k),e^{\prime}-1}_{y}-\mathbf{w}^{(k)}\Bigg{\|}^{2}\right]+4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2},$ (63)

where we used Cauchy-Schwarz inequality repeatedly and applied the
$\beta$-smoothness of the loss function. Replacing the above expression in
(62) yields

$\displaystyle\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right]\leq$
$\displaystyle
4(e-1)\eta_{k}^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}$
$\displaystyle+4\eta_{k}^{2}\beta^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\mathbf{w}^{(k),e^{\prime}-1}_{y}-\mathbf{w}^{(k)}\Bigg{\|}^{2}\right]+4\eta_{k}^{2}(e-1)\sum_{e^{\prime}=1}^{e-1}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2},$ (64)

which implies:

$\displaystyle\sum_{e=1}^{e_{y}^{(k)}}\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right]\leq
4\eta_{k}^{2}\sum_{e=1}^{e_{y}^{(k)}}(e-1)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}$
$\displaystyle+4\eta_{k}^{2}\beta^{2}\sum_{e=1}^{e_{y}^{(k)}}(e-1)\sum_{e^{\prime}=1}^{e-1}\mathbb{E}_{k}\left[\Bigg{\|}\mathbf{w}^{(k),e^{\prime}-1}_{y}-\mathbf{w}^{(k)}\Bigg{\|}^{2}\right]+4\eta_{k}^{2}\sum_{e=1}^{e_{y}^{(k)}}(e-1)\sum_{e^{\prime}=1}^{e-1}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}$ $\displaystyle\leq
4\eta_{k}^{2}\left(e_{y}^{(k)}\right)\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}$
$\displaystyle+4\eta_{k}^{2}\beta^{2}\left(e_{y}^{(k)}\right)\left(e_{y}^{(k)}-1\right)\sum_{e=1}^{e_{y}^{(k)}}\mathbb{E}_{k}\left[\Bigg{\|}\mathbf{w}^{(k),e-1}_{y}-\mathbf{w}^{(k)}\Bigg{\|}^{2}\right]+4\eta_{k}^{2}\left(e_{y}^{(k)}\right)\left(e_{y}^{(k)}-1\right)\sum_{e=1}^{e_{y}^{(k)}}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2},$ (65)

Assuming
$\eta_{k}\leq\left(2\beta\sqrt{e_{y}^{(k)}(e_{y}^{(k)}-1)}\right)^{-1},\forall
n$, we get

$\displaystyle\sum_{e=1}^{e_{y}^{(k)}}\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right]\leq$
$\displaystyle\frac{4\eta_{k}^{2}\left(e_{y}^{(k)}\right)\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\frac{4\eta_{k}^{2}\left(e_{y}^{(k)}\right)^{2}\left(e_{y}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}.$ (66)

Replacing the above expression in (61), we get:

$\displaystyle\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}-\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{{D}^{(k)}e^{(k)}_{y}}\sum_{e=1}^{e^{(k)}_{y}}{\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})}\right\|^{2}\leq\beta^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\sum_{e=1}^{e^{(k)}_{y}}\mathbb{E}_{k}\left[\left\|\mathbf{w}^{(k)}-\mathbf{w}^{(k),e-1}_{y}\right\|^{2}\right]$
(67)
$\displaystyle\leq\beta^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\bBigg@{4}[\frac{4\eta_{k}^{2}\left(e_{y}^{(k)}\right)\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\frac{4\eta_{k}^{2}\left(e_{y}^{(k)}\right)^{2}\left(e_{y}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}\bBigg@{4}]$
$\displaystyle=\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}$
$\displaystyle\leq\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}e_{y}^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\frac{4\beta^{2}\eta_{k}^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}\Bigg{\|}\nabla
F^{(k)}_{y}(\mathbf{w}^{(k)})\Bigg{\|}^{2}$
$\displaystyle\leq\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\frac{4\beta^{2}\eta_{k}^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}\left(\zeta_{1}\left\|\nabla
F^{(k)}(\mathbf{w}^{(k)})\right\|^{2}+\zeta_{2}\right),$

where we used
$e^{(k)}_{\mathsf{max}}=\max_{n\in\mathcal{N}}\\{e^{(k)}_{y}\\}$, and the
bounded dissimilarity of local gradients (Assumption 3). Replacing the above
expression in (60) gives us

$\displaystyle\mathbb{E}_{k}\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})-\left(\frac{\eta_{k}}{4}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}$
(68)
$\displaystyle+\left(\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\bBigg@{4}[\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{y}^{(k)}\left(e_{y}^{(k)}-1\right)}$
$\displaystyle+\frac{4\beta^{2}\eta_{k}^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e^{(k)}_{\mathsf{max}}\left(e^{(k)}_{\mathsf{max}}-1\right)}\left(\zeta_{1}\left\|\nabla
F^{(k)}(\mathbf{w}^{(k)})\right\|^{2}+\zeta_{2}\right)\bBigg@{4}]$
$\displaystyle+\frac{3}{2}{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+2{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y},$

which implies

$\displaystyle\mathbb{E}_{k}$
$\displaystyle\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})+\frac{\eta_{k}}{2}\sum_{n\in\mathcal{N}}\frac{{D}^{(k)}_{y}e^{(k)}_{y}}{{D}^{(k)}}\left(\frac{4\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)}\zeta_{1}-\frac{1}{2}\right)\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}$
$\displaystyle+\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\bBigg@{4}(\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}\frac{4\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}{1-4\eta_{k}^{2}\beta^{2}e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)}+\frac{4\zeta_{2}\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)}\bBigg@{4})$
$\displaystyle+\frac{3}{2}{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+2{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(69)

Assuming
$\frac{4\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}{1-4\eta_{k}^{2}\beta^{2}e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)}\zeta_{1}\leq\frac{1}{4}$,
implying
$\frac{1}{1-4\eta_{k}^{2}\beta^{2}e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)}\leq\frac{1+4\zeta_{1}}{\zeta_{1}}\leq
5$, which can be obtained under the step size choice of
$\eta_{k}\leq\frac{1}{2\beta}\sqrt{\frac{1}{(4\zeta_{1}+1)\left(e_{\mathsf{max}}^{(k)}\left(e_{\mathsf{max}}^{(k)}-1\right)\right)}}$,
we get

$\displaystyle\mathbb{E}_{k}$
$\displaystyle\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]\leq
F^{(k)}(\mathbf{w}^{(k)})-\frac{1}{8}{\eta_{k}}\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}\sum_{n\in\mathcal{N}}\frac{{D}^{(k)}_{y}e^{(k)}_{y}}{{D}^{(k)}}$
$\displaystyle+\frac{\eta_{k}}{2}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\bBigg@{4}(\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}{20\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}+{20\zeta_{2}\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}\bBigg@{4})$
$\displaystyle+\frac{3}{2}{\eta_{k}}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{{D}}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]$
$\displaystyle+2{\beta\eta^{2}_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)^{2}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(70)

Rearranging the terms of the above bound gives the following bound on the norm
of gradient:

$\displaystyle\left\|\nabla{F^{(k)}(\mathbf{w}^{(k)})}\right\|^{2}\leq\frac{F^{(k)}(\mathbf{w}^{(k)})-\mathbb{E}_{k}\left[F^{(k)}(\mathbf{w}^{(k+1)})\right]}{\eta_{k}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}/(8D^{(k)})}$
$\displaystyle+\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}{80\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}+{80\zeta_{2}\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}$
$\displaystyle+24\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+16{\beta\eta_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(71)

Note that $F^{(k)}(\mathbf{w}^{(k)})$ in the first term on the right hand side
of the above bound is in fact the loss under which the global aggregation
started from, i.e., $F^{(k)}(\mathbf{w}^{(k)}|,{\mathcal{D}}^{(k)})$ and
$F^{(k)}(\mathbf{w}^{(k+1)})$ is the loss under which the global aggregation
concludes, i.e., $F^{(k)}(\mathbf{w}^{(k+1)}|{\mathcal{D}}^{(k)})$. We next
find the connection between $F^{(k)}(\mathbf{w}^{(k)}|{\mathcal{D}}^{(k)})$
and the actual loss under which iteration $k-1$ has been concluded, i.e.,
$F^{(k-1)}(\mathbf{w}^{(k)}|{\mathcal{D}}^{(k-1)})$. Using the definition of
model/concept drift in Definition 3, since the global loss is defined as the
loss per data point we have:

$\displaystyle F^{(k)}(\mathbf{w}^{(k)}|{\mathcal{D}}^{(k)})$
$\displaystyle=\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}^{(k)}_{m}}\Bigg{[}\frac{{D}_{y}^{(k)}}{{D}^{(k)}}F_{y}^{(k)}(\mathbf{w}^{(k)}|{\mathcal{D}}_{y}^{(k)})-\frac{{D}_{y}^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf{w}^{(k)}|{{D}}_{y}^{(k-1)})+\frac{{D}_{y}^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf{w}^{(k)}|{{D}}_{y}^{(k-1)})\Bigg{]}$
$\displaystyle\leq\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}^{(k)}_{m}}\Delta_{y}^{(k)}+\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}^{(k)}_{m}}\frac{{D}_{y}^{(k-1)}}{{D}^{(k-1)}}F^{(k-1)}_{y}(\mathbf{w}^{(k)}|{{D}}_{y}^{(k-1)})$
$\displaystyle=\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}^{(k)}_{m}}\Delta_{y}^{(k)}+F^{(k-1)}(\mathbf{w}^{(k)}|{\mathcal{D}}^{(k-1)})=\Delta^{(k)}+F^{(k-1)}(\mathbf{w}^{(k)}),\leavevmode\nobreak\
k\geq 1.$ (72)

Taking total expectation from both hand sides of (A-B) and taking the
summation over global aggregation index implies

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]\leq\frac{1}{K}\frac{F^{(0)}(\mathbf{w}^{(0)})-F^{(0)}(\mathbf{w}^{(1)})}{\eta_{k}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}/(8D^{(k)})}+\frac{1}{K}\sum_{k=1}^{K-1}\frac{F^{(k-1)}(\mathbf{w}^{(k)})-F^{(k)}(\mathbf{w}^{(k+1)})}{\eta_{k}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}/(8D^{(k)})}$
$\displaystyle+\frac{1}{K}\sum_{k=1}^{K-1}\frac{\Delta^{(k)}}{\eta_{k}\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}/(8D^{(k)})}$
$\displaystyle+\frac{1}{K}\sum_{k=0}^{K-1}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}{80\beta^{2}\eta_{k}^{2}\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}+\frac{1}{K}\sum_{k=0}^{K-1}{80\zeta_{2}\eta_{k}^{2}\beta^{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}$
$\displaystyle+\frac{1}{K}\sum_{k=0}^{K-1}24\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]+\frac{1}{K}\sum_{k=0}^{K-1}16{\beta\eta_{k}}\left(\sum_{m\in\mathcal{M}}\sum_{y^{\prime}\in\mathcal{N}^{(k)}_{m}}\frac{{D}^{(k)}_{y^{\prime}}e^{(k)}_{y^{\prime}}}{{D}^{(k)}}\right)\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(73)

Assuming the choice of step size
$\eta_{k}=\frac{\alpha}{{\sqrt{Ke^{(k)}_{\mathsf{avg}}}}}$, where
$e^{(k)}_{\mathsf{avg}}$ denotes the average number of local iterations across
the participating devices, we get:

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]\leq\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\left({F^{(0)}(\mathbf{w}^{(0)})-F^{{(k)}^{\star}}}\right)+\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\sum_{k=1}^{K-1}{\Delta^{(k)}}$
$\displaystyle+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}\sum_{k=0}^{K-1}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}{\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}\sum_{k=0}^{K-1}{\zeta_{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}$
$\displaystyle+\frac{1}{K}\sum_{k=0}^{K-1}24\underbrace{\mathbb{E}_{k}\left[\left\|\bm{c}_{m_{k}}^{(k)}\right\|^{2}\right]}_{(a)}+\frac{16\beta\alpha\hat{e}^{\mathsf{max}}_{\mathsf{avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf{min}}_{\mathsf{avg}}}}\sum_{k=0}^{K-1}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(74)

We next aim to bound term $(a)$ in (A-B). Let $\widetilde{\nabla F}_{m}^{(k)}$
denote the initial local aggregated gradient at ES $m$, containing its own
gradient and the gradient of its associated users, and $\widehat{\nabla
F}_{m}^{(k)}$ denote the gradient at ES $m$ after the consensus through P2P
communications concludes.

As explained in (42), we have

${\nabla{F}}_{m}^{\mathsf{L},(k)}=\sum_{m\in\mathcal{M}}{\nabla{F}}_{m}^{\mathsf{A},(k)}+\bm{e}^{(k)}_{m}.$
(75)

On the other hand, the evolution of the local gradient during the consensus
process can be described as

${\nabla{F}}^{\mathsf{L},(k)}=\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}{\nabla{F}}^{\mathsf{A},(k)},$
(76)

where ${\nabla{F}}^{\mathsf{L},(k)}\in\mathbb{R}^{d\times d}$ denotes a
matrix,333$d$ denotes the size/length of the gradient vector. with its row $m$
containing the final vector of gradient at ES $m$ (i.e.,
${\nabla{F}}_{m}^{\mathsf{L},(k)}$), and
$\nabla{F}^{\mathsf{A},(k)}\in\mathbb{R}^{d\times d}$ denotes a matrix, with
its row $m$ containing the initial gradient vector at ES $m$ (i.e.,
${\nabla{F}}_{m}^{\mathsf{A},(k)}$). In (76),
$\bm{\Lambda}^{(k)}=[\lambda^{(k)}_{i,j}]_{i,j\in\mathcal{M}}$ is the
consensus matrix across the ES network and $\varphi^{(k)}$ denotes the rounds
of P2P communications at the aggregation round $k$.

Let matrix ${{\nabla{F}}^{\mathsf{P},(k)}}$ denote the matrix of true/perfect
average of the gradient vectors across the ESs, which is given by

${{\nabla{F}}^{\mathsf{P},(k)}}=\frac{\textbf{1}_{M}\textbf{1}_{M}^{\top}{\nabla{F}}_{m}^{\mathsf{A},(k)}}{M}.$
(77)

Also, let ${{\nabla{F}}^{\mathsf{P},(k)}}_{m}$ denote the $m$-th row of
${{\nabla{F}}^{\mathsf{P},(k)}}$. Since the consensus error is zero mean [30]
across the ESs, we have
$\mathbf{1}^{\top}\left({\nabla{F}}^{\mathsf{L},(k)}-{\nabla{F}}^{\mathsf{A},(k)}\right)=\mathbf{0}$
implying that
$(\mathbf{1}\mathbf{1}^{\top})\left({\nabla{F}}^{\mathsf{L},(k)}-{\nabla{F}}^{\mathsf{A},(k)}\right)=\mathbf{0}$.
Thus, we get

$\displaystyle{\nabla{F}}^{\mathsf{L},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}$
$\displaystyle=\left(\mathbf{I}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right)\left({\nabla{F}}^{\mathsf{L},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)=\left(\mathbf{I}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right)\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}{\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)$
(78)
$\displaystyle=\left(\mathbf{I}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right)\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}{\nabla{F}}^{\mathsf{A},(k)}-\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}{{\nabla{F}}^{\mathsf{P},(k)}}\right)$
$\displaystyle=\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right)\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right),$

where the above derivations are obtained based on the following properties:
(i)
$\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}{{\nabla{F}}^{\mathsf{P},(k)}}={{\nabla{F}}^{\mathsf{P},(k)}}$,
and (ii)
$\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}=\frac{\mathbf{1}\mathbf{1}^{\top}}{M}$.
We finally get

$\displaystyle\big{\|}\bm{c}^{(k)}_{m}\big{\|}^{2}$
$\displaystyle\leq\textrm{trace}\left(\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)^{\top}\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right)^{2}\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)\right)$
(79)
$\displaystyle=\textrm{trace}\left(\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)^{\top}\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}\left[\mathbf{I}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right]\right)^{2}\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)\right)$
$\displaystyle=\textrm{trace}\left(\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)^{\top}\left(\left(\mathbf{\Lambda}^{(k)}\right)^{\varphi^{(k)}}\left[\mathbf{I}-\frac{\mathbf{1}\mathbf{1}^{\top}}{M}\right]^{\varphi^{(k)}}\right)^{2}\left({\nabla{F}}^{\mathsf{A},(k)}-{{\nabla{F}}^{\mathsf{P},(k)}}\right)\right)$
$\displaystyle\leq(\lambda^{(k)})^{2\varphi^{(k)}}\sum_{m^{\prime}\in\mathcal{M}}\|{\nabla{F}}^{\mathsf{A},(k)}_{m^{\prime}}-\nabla{F}^{\mathsf{P},(k)}_{m^{\prime}}\big{\|}^{2}$
$\displaystyle\leq\frac{1}{M}(\lambda^{(k)})^{2\varphi^{(k)}}\sum_{m^{\prime},m^{\prime\prime}\in\mathcal{M}}\|{\nabla{F}}^{\mathsf{A},(k)}_{m^{\prime}}-\nabla{F}^{\mathsf{A},(k)}_{m^{\prime\prime}}\big{\|}^{2}$
$\displaystyle\leq{M}(\lambda^{(k)})^{2\varphi^{(k)}}\max_{m^{\prime},m^{\prime\prime}\in\mathcal{M}}\|{\nabla{F}}^{\mathsf{A},(k)}_{m^{\prime}}-\nabla{F}^{\mathsf{A},(k)}_{m^{\prime\prime}}\big{\|}^{2}\leq{M}(\lambda^{(k)})^{2\varphi^{(k)}}\left(\Xi^{(k)}\right)^{2}.$

Replacing the above result back in (A-B), we get the final result

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]\leq\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\left({F^{(0)}(\mathbf{w}^{(0)})-F^{{(k)}^{\star}}}\right)+\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\sum_{k=1}^{K-1}{\Delta^{(k)}}$
$\displaystyle+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}\sum_{k=0}^{K-1}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\frac{{D}^{(k)}_{y}}{D^{(k)}}{\left(e_{y}^{(k)}-1\right)\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}}+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}\sum_{k=0}^{K-1}{\zeta_{2}\left(e_{\mathsf{max}}^{(k)}\right)\left(e_{\mathsf{max}}^{(k)}-1\right)}$
$\displaystyle+\frac{1}{K}\sum_{k=0}^{K-1}24{M}(\lambda^{(k)})^{2\varphi^{(k)}}\left(\Xi^{(k)}\right)^{2}+\frac{16\beta\alpha\hat{e}^{\mathsf{max}}_{\mathsf{avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf{min}}_{\mathsf{avg}}}}\sum_{k=0}^{K-1}\sum_{m\in\mathcal{M}}\sum_{y\in\mathcal{N}_{m}^{(k)}}\left(\frac{{D}^{(k)}_{y}}{{D}^{(k)}\sqrt{e^{(k)}_{y}}}\right)^{2}\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y}.$
(80)

##  Appendix B Proof of Corollary 1

Assuming $\Delta^{(k)}\leq\frac{\Upsilon}{K}$ and considering the assumption
$\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta_{y}^{2}\leq\vartheta$
simplifies the bound in (II-B) as follows:

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]\leq\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\left({F^{(0)}(\mathbf{w}^{(0)})-F^{{(k)}^{\star}}}\right)+\frac{8\Upsilon\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}$
$\displaystyle+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}K\left(e_{\mathsf{max}}-1\right)\vartheta+\frac{80\beta^{2}\alpha^{2}}{K^{2}{e}^{\mathsf{min}}_{\mathsf{avg}}}K{\zeta_{2}\left(e_{\mathsf{max}}\right)\left(e_{\mathsf{max}}-1\right)}$
$\displaystyle+\frac{1}{K}\sum_{k=0}^{K-1}24{M}(\lambda^{(k)})^{2\varphi^{(k)}}\left(\Xi^{(k)}\right)^{2}+\frac{16\beta\alpha\hat{e}^{\mathsf{max}}_{\mathsf{avg}}}{K\sqrt{K}\sqrt{{e}^{\mathsf{min}}_{\mathsf{avg}}}}K\vartheta.$
(81)

Assuming
${\varphi^{(k)}}\geq\frac{1}{2}\left[\log_{\lambda^{(k)}}\left(\frac{\xi}{\sqrt{K}\left(\Xi^{(k)}\right)^{2}{M}^{(k)}}\right)\right]^{+}$
implies that (note that $\lambda^{(k)}<1$)

$\displaystyle{2\varphi^{(k)}}\geq\log_{\lambda^{(k)}}\left(\frac{\xi}{\sqrt{K}\left(\Xi^{(k)}\right)^{2}{M}^{(k)}}\right)$
$\displaystyle\Rightarrow(\lambda^{(k)})^{2\varphi^{(k)}}\leq\frac{\xi}{\sqrt{K}\left(\Xi^{(k)}\right)^{2}{M}^{(k)}}$
(82)
$\displaystyle\Rightarrow{M}^{(k)}(\lambda^{(k)})^{2\varphi^{(k)}}\left(\Xi^{(k)}\right)^{2}\leq\xi/\sqrt{K}.$

Replacing this result back in (B) yields

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]\leq\frac{8\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\left({F^{(0)}(\mathbf{w}^{(0)})-F^{{(k)}^{\star}}}\right)+\frac{8\Upsilon\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}$
$\displaystyle+\frac{80\beta^{2}\alpha^{2}}{K{e}^{\mathsf{min}}_{\mathsf{avg}}}\left(e_{\mathsf{max}}-1\right)\vartheta+\frac{80\beta^{2}\alpha^{2}}{K{e}^{\mathsf{min}}_{\mathsf{avg}}}{\zeta_{2}\left(e_{\mathsf{max}}\right)\left(e_{\mathsf{max}}-1\right)}+24\frac{\xi}{\sqrt{K}}+\frac{16\beta\alpha\hat{e}^{\mathsf{max}}_{\mathsf{avg}}}{\sqrt{K}\sqrt{{e}^{\mathsf{min}}_{\mathsf{avg}}}}\vartheta,$

and thus

$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\|\nabla
F^{(k)}(\mathbf{w}^{({k})})\|^{2}\right]=\mathcal{O}\left(\frac{\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\right)+\mathcal{O}\left(\frac{\Upsilon\sqrt{{e}^{\mathsf{max}}_{\mathsf{avg}}}}{\alpha\hat{e}^{\mathsf{min}}_{\mathsf{avg}}\sqrt{K}}\right)+\mathcal{O}\left(\frac{\beta^{2}\alpha^{2}}{K{e}^{\mathsf{min}}_{\mathsf{avg}}}\left(e_{\mathsf{max}}-1\right)\vartheta\right)$
$\displaystyle+\mathcal{O}\left(\frac{\beta^{2}\alpha^{2}}{K{e}^{\mathsf{min}}_{\mathsf{avg}}}{\zeta_{2}\left(e_{\mathsf{max}}\right)\left(e_{\mathsf{max}}-1\right)}\right)+\mathcal{O}\left(\frac{\xi}{\sqrt{K}}\right)+\mathcal{O}\left(\frac{\beta\alpha\hat{e}^{\mathsf{max}}_{\mathsf{avg}}}{\sqrt{K}\sqrt{{e}^{\mathsf{min}}_{\mathsf{avg}}}}\vartheta\right)$
$\displaystyle=\mathcal{O}\left(1/\sqrt{K}\right),$ (83)

which concludes the proof.

##  Appendix C Characterization of the Gradient of the Critic's Loss

Inspired by [44], our proof for the Lipschitz continuity property of the MSPBE
loss function's gradient is presented as below. First, the loss function in
(39) can be re-written as

$E_{\theta}(\omega)=\frac{1}{2}||V_{\omega}-\Lambda(B_{\theta}V_{\omega})||^{2}=\frac{1}{2}||\Lambda(V_{\omega}-B_{\theta}V_{\omega})||^{2},(since\leavevmode\nobreak\
V_{\omega}=\Lambda V_{\omega}),$ (84)

which is upper-bounded by its expectation value given by the loss across the
entire system state vector $H$:

$E_{\theta}(\omega)\leq\frac{1}{2}||\Lambda(V_{\omega}-B_{\theta}V_{\omega})||^{2}_{H},$
(85)

where $H$ is the diagonal matrix whose elements are within the stationary
system state distribution $d^{\pi_{\theta}(s)}$, $\forall s\in\mathcal{S}$ as
defined in section IV-D. Under this stationary condition, (85) can be further
analyzed as:

$\displaystyle
E_{\theta}(\omega)=\frac{1}{2}\left[\Lambda(V_{\omega}-B_{\theta}V_{\omega})\right]^{\top}H\left[\Lambda(V_{\omega}-B_{\theta}V_{\omega})\right]$
(86)
$\displaystyle=\frac{1}{2}(V_{\omega}-B_{\theta}V_{\omega})^{\top}\Lambda^{\top}\raisebox{0.0pt}{\scalebox{1.0}{$H$}}\Lambda(V_{\omega}-B_{\theta}V_{\omega})$
(87)
$\displaystyle=\frac{1}{2}||\bar{\Lambda}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}(V_{\omega}-B_{\theta}V_{\omega})||_{2}^{2},$
(88)

where
$\bar{\Lambda}=\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}(\upphi\raisebox{0.0pt}{\scalebox{1.0}{$H$}}\upphi^{\top})^{-1}\upphi\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}$
is an orthogonal projector of a column element of
$\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}$. Then, the Hessian
product of the loss function is given by

$\mathds{H}(\omega)=\upphi(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})^{\top}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\bar{\Lambda}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})\upphi^{\top},$
(89)

where $I\in\mathds{R}^{|\mathcal{S}|\times|\mathcal{S}|}$ is the identity
matrix, and  $P$ is the transition probability as defined in Section IV-A.
Since $E_{\theta}(\omega)$ is convex, its gradient is $\ell$-Lipschitz if

$\omega^{\top}\mathds{H}(\omega)\omega\leq l||\omega||^{2}_{2}$ (90)

holds. Indeed, we have

$\omega^{\top}\mathds{H}(\omega)\omega=\omega^{\top}\upphi(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})^{\top}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\bar{\Lambda}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})\upphi^{\top}\omega\\\
=||\bar{\Lambda}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})\upphi^{\top}\omega||^{2}_{2}\\\
=||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi\omega||_{2}^{2}-2\gamma\omega^{\top}\upphi\raisebox{0.0pt}{\scalebox{1.0}{$H$}}\raisebox{0.0pt}{\scalebox{1.0}{$P$}}\upphi^{\top}\omega+\gamma^{2}||\bar{\Lambda}\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\raisebox{0.0pt}{\scalebox{1.0}{$P$}}\upphi^{\top}\omega||^{2}_{2}\\\
\leq||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi\omega||_{2}^{2}-2\gamma\omega^{\top}\upphi\raisebox{0.0pt}{\scalebox{1.0}{$H$}}\raisebox{0.0pt}{\scalebox{1.0}{$P$}}\upphi^{\top}\omega+\gamma^{2}||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\raisebox{0.0pt}{\scalebox{1.0}{$P$}}\upphi^{\top}\omega||^{2}_{2}\\\
=||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}(I-\gamma\raisebox{0.0pt}{\scalebox{1.0}{$P$}})\upphi^{\top}\omega||^{2}_{2}.$
(91)

Using the Cauchy-Schwartz inequality, we have

$\omega^{\top}\mathds{H}(\omega)\omega\leq\left(||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}\omega||_{2}+\gamma||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\raisebox{0.0pt}{\scalebox{1.0}{$P$}}\upphi^{\top}\omega||_{2}\right)^{2}\leq\left(||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}\omega||_{2}^{2}+\gamma||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}\omega||_{2}\right)^{2}=(1+\gamma)^{2}||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}\omega||_{2}^{2}.$
(92)

Here, we have

$||\sqrt{\raisebox{0.0pt}{\scalebox{1.0}{$H$}}}\upphi^{\top}\omega||_{2}^{2}=||\upphi^{\top}\omega||^{2}_{\raisebox{0.0pt}{\scalebox{1.0}{$P$}}}=\sum_{i\in|\mathcal{S}|}d^{i}\left({(\upphi^{i})}^{\top}\omega\right)^{2}\\\
\leq\sum_{i\in|\mathcal{S}|}d^{i}||\omega^{i}||^{2}_{2}||\theta^{i}||^{2}_{2}\leq\left(\underset{i}{\max}||\upphi^{i}||^{2}_{2}\right)||\theta^{i}||^{2}_{2}.$
(93)

Thus, we get

$\omega^{\top}\mathds{H}(\omega)\omega\leq(1+\gamma)^{2}\left(\underset{i}{\max}||\upphi^{i}||^{2}_{2}\right)||\theta^{i}||^{2}_{2},$
(94)

which leads to 90, and completes our proof.

##  Appendix D Mini-Batch SGD Noise Characterization

######  Lemma 2.

During each aggregation round $t$, for each MD/ES
$y\in\mathcal{N}\cup\mathcal{M}$, the variance of stochastic gradient during
mini-batch gradient descent iteration $k$, i.e.,
$\widetilde{\nabla}F_{y}^{(t)}(\mathbf{x})$ is upper-bounded by

$\displaystyle\mathbb{E}\left[\left\|\sum_{d\in\mathcal{B}^{(k),e}_{y}}\frac{\nabla
f(\mathbf{w}^{(k),e-1}_{y},d)}{{{B}}^{(k)}_{y}}-\nabla
F^{(k)}_{y}(\mathbf{w}^{(k),e-1}_{y})\right\|^{2}\right]$ $\displaystyle\leq
2\left(1-\frac{{B}^{(k)}_{y}}{{D}^{(k)}_{y}}\right)\frac{({\sigma}_{y}^{(k)})^{2}}{{B}^{(k)}_{y}}\Theta^{2}_{y},\leavevmode\nobreak\
\forall e,$ (95)

where $\sigma_{y}^{(k)}$ denotes the sampled variance of data at the
respective node.

###### Proof.

The proof can be easily carried out using the result on the variance of of
simple random sampling in [45] and our definition of the data variability in
Definition 2, and thus omitted for brevity. ∎


# Conformal perturbation theory from open string field theory

Jaroslav Scheinpflug  CEICO, Institute of Physics of the Czech Academy of
Sciences  Martin Schnabl  CEICO, Institute of Physics of the Czech Academy of
Sciences

###### Abstract

Conformal boundary conditions in two-dimensional conformal field theories
manifest lots of mathematical beauty and complexity and in many aspects
present uncharted territory. Even less is known about the relevant boundary
deformations that connect them. A natural approach to the problem is via
conformal perturbation theory, which however becomes quickly intractable and
possibly ambiguous. Relying on the internal consistency of open string field
theory, which has been proven to be a consistent theory of conformal boundary
conditions, we show how to construct nearby fixed points of the two-
dimensional renormalization group flow triggered by weakly relevant operators.
As a simple illustration we calculate the boundary degeneracy $g$ to next-to-
leading order for a generic theory.

##  I Introduction and Conclusion

Study of consistent boundary conditions in two-dimensional conformal field
theory (CFT) is a long and fascinating subject with many applications. There
is a number of stringent constraints on the spectrum of boundary operators and
operator product expansion (OPE) coefficients [1, 2, 3]. Flurry of work
towards the end of the last millennium culminated in fairly complete
characterization of boundary conditions in rational conformal field theories.
[4]. Little is known for the non-rational case. Except in few examples [5, 6]
where for special points in the moduli space rational structure may emerge,
one has to resort either to perturbative or numerical approaches. Numerically
one can use the truncated conformal space approach or level truncation in open
string field theory (OSFT) [7, 8]. Perturbatively, one can start with a given
consistent conformal boundary condition and perturb it by a weakly relevant
operator with dimension $h$ close to 1. Such flows were first studied by
Affleck and Ludwig [9] who showed that for a nearby fixed point

$\frac{\Delta g}{g}=-\frac{\pi^{2}}{3}\frac{y^{3}}{C_{VVV}^{2}}+O(y^{4}),$ (1)

where $g$ is the universal ground state degeneracy or boundary entropy. It is
the single most elementary characterizing quantity of a given boundary
condition given by the disk partition function. They conjectured that the
corresponding $g$-function decreases along the RG flow which was later proved
[10]. These flows have been applied to minimal models in [11].

Open string field theory is a consistent theory of open strings ending on the
D-branes. The string degrees of freedom describe collective degrees of freedom
for these nonperturbative objects, such as its position and shape in the
spacetime, or fields living on them. To formulate open string field theory one
needs a reference D-brane. The vector space of quantum open strings ending on
the D-brane is given by the Hilbert space of boundary conformal field theory.
The classical field $\Psi$ of open string field theory is an element from this
space. Different backgrounds correspond to different classical solutions of
the equation of motion $Q\Psi+\Psi*\Psi=0$. The value of the Witten’s action

$S=-\frac{1}{2}\left\langle\,\Psi,Q\Psi\,\right\rangle-\frac{1}{3}\left\langle\,\Psi,\Psi*\Psi\,\right\rangle$
(2)

for a given classical solution has been conjectured by Sen [12] and later
proved by others [13, 14] to correspond to a change in the given boundary
degeneracy between the new an old boundary conditions. For a recent review see
[15]

$S=-\frac{\Delta g}{2\pi^{2}}.$ (3)

In this work we construct perturbatively the solution corresponding to a
nearby fixed point and as an illustration we show that

$\frac{\Delta
g}{g_{0}}=-\frac{\pi^{2}}{3}\left(\frac{y^{3}}{C_{VVV}^{2}}+\frac{3\mathcal{\tilde{A}}}{C_{VVV}^{4}}y^{4}+O(y^{5})\right),$
(4)

where

$\displaystyle\mathcal{\tilde{A}}$ $\displaystyle=$
$\displaystyle\int_{0}^{1/2}d\xi\biggr{[}\frac{1}{g_{0}}\left\langle\,V|V(1)V(\xi)|V\,\right\rangle$
(6)
$\displaystyle-\sum_{V^{\prime}}C_{VVV^{\prime}}^{2}\left(\frac{1}{\xi^{2-h^{\prime}}}+\frac{1}{(1-\xi)^{2-h^{\prime}}}\right)$
$\displaystyle+\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\left(\frac{1}{h^{\prime}-1}+\frac{1}{2}\delta_{h^{\prime}=0}\right)\biggr{]}.$

and $g_{0}$ is the $g$-function of the undeformed theory. The sum on the first
line over the relevant fields in the OPE of two $V$’s renders the integral
fully convergent. The subtraction of powers of $1-\xi$ has been introduced for
mere convenience. The second line arises as a simple correction due to the
relevant modes, whose structure stems from OSFT calculations. We have applied
(4) to RG flows of $c=2$ free bosons and we got a high precision match with
[22]. The KMS correspondence [18] also allows us to compute the leading order
correction to the coefficient of a bulk primary $\phi$ in the boundary state

$\displaystyle\frac{\Delta B_{\phi}}{g_{0}}$ $\displaystyle=-2\pi\frac{B_{\phi
V}}{C_{VVV}}y+O(y^{2})$ (7)

where $B_{\phi V}$ is a bulk-boundary structure constant. The next-to-leading
correction should be obtainable with the methods of this paper.

##  II General setup

Let us write the general solution as $\Psi=R+X$, where
$R=\sum_{i}T_{i}V^{i}c_{1}|0\rangle$ is a finite sum of states corresponding
to the relevant operators $V^{i}$ with conformal weights ${h_{i}<1}$. The
results we find are interesting even in the case when there is a single
relevant operator. Formally, one need not insist on the operator being
relevant, one can consider in fact any finite combination of states. The $X$
stands for all other fields.

We start by observing that the Siegel gauge equations of motion

$L_{0}\Psi+b_{0}(\Psi*\Psi)=0$ (8)

can be rewritten as

$\displaystyle R+\frac{b_{0}}{L_{0}}P(R+X)^{2}$ $\displaystyle=$
$\displaystyle 0,$ (9) $\displaystyle X+\frac{b_{0}}{L_{0}}{\bar{P}}(R+X)^{2}$
$\displaystyle=$ $\displaystyle 0,$ (10)

where $P$ is a projector onto the vector space spanned by
$V^{i}c_{1}|0\rangle$ and $V^{i}c_{1}c_{0}|0\rangle$, and ${\bar{P}}=1-P$. The
second equation can be solved perturbatively:

$X=hR^{2}+h\left\\{R,hR^{2}\right\\}+\cdots,$ (11)

where

$h=-\frac{b_{0}}{L_{0}}\bar{P}.$ (12)

The right hand side of (11) corresponds to all possible binary diagrams, where
each vertex denotes star multiplication, each internal line an action of $h$
and each external line $R$. For a given number $n$ of external lines (number
of $R$’s), there is $C_{n-1}$ number of such terms where $C_{n}=1,2,5,\ldots$
are the Catalan numbers. The numbers would appear as coefficients of the
Taylor series of the solution to (10) if one treated the string fields $R$ and
$X$ and the operator $h$ as plain numbers.

The Catalan numbers grow asymptotically only as
$C_{n}\sim\frac{4^{n}}{n^{3/2}\sqrt{\pi}}$, so we see that the series (11)
should be convergent, for sufficiently small $R$ (in some convenient norm)
assuming that the action of $h$ is bounded from above. This should be the case
since the least relevant state $Vc\partial c|0\rangle$ is projected out from
the ghost number two Hilbert space on which $h$ acts in (11). The key is that
the projector ${\bar{P}}$ projects out the nearly marginal states for which
$L_{0}$ would have the biggest eigenvalue. From this rough argument it is
clear that the coefficients of $R$ and hence also $\Psi$ should be
parametrically smaller than $1-h$, where $h$ is the dimension of the nearest
marginal operator in the theory. For theories with exactly marginal operators,
we would need either to guarantee that those operators are not excited in our
solution, or alternatively, change the definition of the projector ${\bar{P}}$
so that it would project out such states as well.

Plugging the solution (11) into (9) we find a system of finite number of
equations (generally non-polynomial if we do not truncate to finite order in
$R$). This has the interpretation of the fixed point equations for the
relevant couplings $T_{i}$.

While it is immediately obvious that the full equations for $R$ are obeyed

$QR+P(R+X)^{2}=0$ (13)

as a consequence of (9) it is not a priori obvious that

$QX+\bar{P}(R+X)^{2}=0.$ (14)

In fact, in general it is not true, that any given solution of the gauge-fixed
equations of motion obeys the full equation of motion [16]. In the case of
perturbatively constructed solutions, however, one can prove it [17]. To show
this, note that from (10) and (13)

$\displaystyle Q\Psi+\Psi^{2}$ $\displaystyle=$
$\displaystyle\frac{b_{0}}{L_{0}}{\bar{P}}Q(\Psi^{2})=\frac{b_{0}}{L_{0}}{\bar{P}}[Q\Psi,\Psi]$
(15) $\displaystyle=$
$\displaystyle\frac{b_{0}}{L_{0}}{\bar{P}}[\frac{b_{0}}{L_{0}}{\bar{P}}Q(\Psi^{2}),\Psi]=\cdots,$

where in the last step we used the already proven part of the equation of
motion. Now assuming that $\Psi$ is parametrically small enough in some
convenient norm, and that repeated action of $h=\frac{b_{0}}{L_{0}}{\bar{P}}$
does not give rise to divergent factors, one can argue that the right hand
side vanishes. Unlike in the discussion below (11), here $h$ acts always on
$Q$-exact states at ghost number 3. The state of the form $c\partial
c\partial^{2}c$ with lowest possible value of $L_{0}$ is excluded since it is
not $Q$-exact. States of the form $c\partial c\partial^{2}cV$ for $V$ of low
conformal weight (most relevant) are $Q$-exact, so it is important that there
is a gap between the identity operator with $h=0$ and the next most relevant
operator in the matter CFT vector space. Practically the bounds are even
better, since states of the form are excluded by twist symmetry which is often
imposed for useful solutions.

##  III Conformal perturbation theory

We take $\Psi_{1}=\lambda cV|0\rangle$, where $V$ is a relevant operator on
the UHP of weight $1>h>0$ with the following correlators

$\displaystyle\langle V(z_{1})\rangle_{UHP}$ $\displaystyle=$ $\displaystyle
0$ (16) $\displaystyle\langle V(z_{1})V(z_{2})\rangle_{UHP}$ $\displaystyle=$
$\displaystyle z_{12}^{-2h}$ (17) $\displaystyle\langle
V(z_{1})V(z_{2})V(z_{3})\rangle_{UHP}$ $\displaystyle=$ $\displaystyle
C_{VVV}z_{12}^{-h}z_{13}^{-h}z_{23}^{-h}$ (18)

where in the rest of paper we write $z_{ij}\equiv\absolutevalue{z_{i}-z_{j}}$
for bosons and $z_{ij}\equiv z_{i}-z_{j}$ for fermions.

To make contact with conformal perturbation theory we would like to compute
observables in an exact perturbation series with an expansion parameter
$y\equiv 1-h$. To do this we first need to compute the SFT coupling $\lambda$
as a function of $y$.

###  III.1 Calculation of the SFT coupling

The equation of motion in the direction of $R\equiv\Psi_{1}$ is after
explicitly applying $P$

$\langle cV,Q\Psi_{1}\rangle+\langle cV,\Psi_{1}*\Psi_{1}\rangle+\langle
cV,\anticommutator{\Psi_{1}}{\Psi_{2}}\rangle+\cdots=0$ (19)

using

$Q\Psi_{1}=y\lambda c\partial cV|0\rangle$ (20)

and plugging in the definition of $\Psi_{1}$ and $\Psi_{2}$ this is equal to

$\displaystyle y\lambda\langle cV,c\partial cV\rangle+\lambda^{2}\langle
cV,cV,cV\rangle$ (21) $\displaystyle-2\lambda^{3}\langle
cV*cV,\frac{b_{0}}{L_{0}}\bar{P}cV*cV\rangle+\cdots=0$

Defining the open string four-point amplitude

$\mathcal{A}\equiv\langle cV*cV,\frac{b_{0}}{L_{0}}\bar{P}cV*cV\rangle$ (22)

and using the correlators (17),(18) and

$\langle c(z_{1})c(z_{2})c(z_{3})\rangle_{UHP}=z_{12}z_{13}z_{23}$ (23)

we solve for the SFT coupling to obtain

$\lambda=\frac{y}{C_{VVV}}+\frac{1}{C_{VVV}}\left(\frac{2\mathcal{A}\rvert_{y=0}}{C_{VVV}^{2}}-\ln
K^{3}\right)y^{3}+O(y^{4})$ (24)

where $K\equiv\frac{3\sqrt{3}}{4}$ and $\mathcal{A}$ is evaluated at zero
since it depends on $h$. To leading order this is precisely the result
obtained by Affleck and Ludwig [9] modulo a sign convention so to leading
order the SFT and CFT coupling are equal in magnitude. Next we move on to the
calculation of gauge invariant observables.

###  III.2 Calculation of gauge invariant observables

In this section we evaluate the perturbative shift in the $g$-function
triggered by a deformation by $V$ to next-to-leading order in $y$. It turns
out that the OSFT action is very efficient in accomplishing this. We also
calculate the corresponding leading order shift in the boundary state
coefficients by calculating the Ellwood invariant and envoking the KMS
correspondence [18].

####  III.2.1 Leading order calculation of $g$

The on-shell value of the action (2) of a solution $\Psi$ can be written as

$S=-\frac{1}{6}\langle\Psi,Q\Psi\rangle$ (25)

so that the corresponding shift in the $g$-function is

$\Delta g=\frac{\pi^{2}}{3}\langle\Psi,Q\Psi\rangle$ (26)

To obtain the leading order correction to $g$ we simply use the fact that
$\lambda=O(y)$ and thus since $\bar{P}$ acts as to eliminate possible inverse
powers of $y$ coming from $\frac{1}{L_{0}}$ in $\Psi_{n}$ so that
$\Psi_{n}=O(y^{n})$, we can calculate the $n$-th order contribution by
accounting for string fields up to $\Psi_{n}$. For the leading contribution to
$\Delta g$ this implies that

$\Delta g=\frac{\pi^{2}}{3}\langle\Psi_{1},Q\Psi_{1}\rangle+O(y^{4})$ (27)

and since

$\langle\Psi_{1},Q\Psi_{1}\rangle=-g_{0}y\lambda^{2}$ (28)

we reproduce (1) by simply plugging in (24) for the coupling.

####  III.2.2 Next-to-leading order calculation of $g$

In the next-to-leading order we have

$\displaystyle\Delta g=$
$\displaystyle\frac{\pi^{2}}{3}\biggr{(}\langle\Psi_{1},Q\Psi_{1}\rangle+\langle\Psi_{2},Q\Psi_{2}\rangle\biggr{)}+O(y^{5})$
(29)

by the BPZ-orthogonality of $P$ the off-diagonal terms vanish and we can also
write

$\langle\Psi_{2},Q\Psi_{2}\rangle=-\langle\Psi_{2},\bar{P}\Psi_{1}*\Psi_{1}\rangle=-\langle\Psi_{2},\Psi_{1}*\Psi_{1}\rangle=-\lambda^{4}\mathcal{A}$
(30)

And so expanding the couplings in (28) to next-to-leading order and in (30) to
leading order we find

$\displaystyle\frac{\Delta g}{g_{0}}$
$\displaystyle=-\frac{\pi^{2}}{3}\biggr{(}\frac{y^{3}}{(C_{VVV})^{2}}$ (31)
$\displaystyle+\biggr{(}3\frac{\mathcal{A}}{g_{0}C_{VVV}^{4}}-6\frac{1}{C_{VVV}^{2}}\ln
K\biggr{)}y^{4}\biggr{)}+O(y^{5})$

so that we only need to calculate the open string four-point amplitude
$\mathcal{A}$ in the marginal limit.

We start by explicitly writing down $\mathcal{A}$

$\displaystyle\mathcal{A}=\langle
cV\left(-\sqrt{3}\right)cV\left(\sqrt{3}\right)U_{3}$ (32)
$\displaystyle\left(\frac{b_{0}}{L_{0}}\bar{P}\right)U_{3}^{*}cV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)\rangle$

Then we use a variant of the trick of [20] by using the Hodge-Kodaira
decomposition

$1=\anticommutator{Q}{\frac{b_{0}}{L_{0}}\bar{P}}+P$ (33)

behind the $U_{3}^{*}$ and by the fact that $cV$ is $Q$-closed up to $O(y)$
terms and $\bar{P}$ protects us from inverse powers of $y$ we get

$\displaystyle\mathcal{A}$ $\displaystyle=\langle
cV\left(-\sqrt{3}\right)cV\left(\sqrt{3}\right)U_{3}\bar{P}U_{3}^{*}$ (34)
$\displaystyle\left(\frac{b_{0}}{L_{0}}\bar{P}\right)cV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)\rangle$
$\displaystyle+\langle cV\left(-\sqrt{3}\right)cV\left(\sqrt{3}\right)U_{3}$
$\displaystyle\left(\frac{b_{0}}{L_{0}}\bar{P}\right)U_{3}^{*}PcV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)\rangle+O(y)$

In the second term we again use the Hodge-Kodaira decomposition behind the
$U_{3}$ following the same logic, that is to move $\frac{b_{0}}{L_{0}}$ behind
the $U$-factors, to get

$\displaystyle\mathcal{A}$ $\displaystyle=\langle
cV\left(-\sqrt{3}\right)cV\left(\sqrt{3}\right)(1+P)U_{3}U_{3}^{*}$ (35)
$\displaystyle\left(\frac{b_{0}}{L_{0}}\bar{P}\right)cV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)\rangle$
$\displaystyle+\langle cV\left(-\sqrt{3}\right)cV\left(\sqrt{3}\right)PU_{3}$
$\displaystyle\left(\frac{b_{0}}{L_{0}}\bar{P}\right)U_{3}^{*}PcV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)\rangle+O(y)$

We now focus on the second term starting by noting that

$PcV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)=-C_{VVV}\left(\frac{2}{\sqrt{3}}\right)^{1-h}c\partial
cV|0\rangle$ (36)

as can be seen for example by explicitly BPZ-projecting or by the OPE

$cV(x)cV(-x)\sim-\sum_{V^{\prime}}C_{VVV^{\prime}}\frac{c\partial
cV^{\prime}(0)}{(2x)^{2h-h^{\prime}-1}}$ (37)

where $V$ are relevant operators and noting that by (16), (17) the overlap
with $cV|0\rangle$ is nonvanishing only for the case $V^{\prime}=V$. So that
it becomes

$C_{VVV}^{2}\left(\frac{4}{3}\right)^{y}\langle c\partial
cV|U_{3}\frac{b_{0}}{L_{0}}\bar{P}U_{3}^{*}|c\partial cV\rangle$ (38)

Writing out $\bar{P}=1-P$ and noting that by the explicit Virasoro formulas
[23] for $U_{n}^{*}$ we have

$PU_{3}^{*}|c\partial cV\rangle=\left(\frac{2}{3}\right)^{h-1}|c\partial
cV\rangle$ (39)

and by commuting the $U$s as
$U_{3}^{*}U_{3}=U_{\frac{8}{3}}U_{\frac{8}{3}}^{*}$ [23] we get

$\displaystyle-
g_{0}C_{VVV}^{2}\left(\frac{4}{3}\right)^{y}\frac{1}{y}\left(\left(\frac{3}{4}\right)^{-2y}-\left(\frac{2}{3}\right)^{-2y}\right)$
(40) $\displaystyle=g_{0}C_{VVV}^{2}\ln\frac{81}{64}+O(y)$

It is expected on general grounds that there exists a geometric constant
$\gamma$ independent of the underlying matter CFT such that

$\langle c\partial
cV|U_{3}\left(\frac{b_{0}}{L_{0}}\bar{P}\right)U_{3}^{*}|c\partial
cV\rangle=\gamma\langle c\partial cV|b_{0}|c\partial cV\rangle$ (41)

and we have proved by (40) that $\gamma=\ln\frac{81}{64}$ which agrees with
level truncation [21] to seven decimal places. This computation was made
possible by the fact that our field was not marginal making intermediate
expressions such as $\frac{1}{h-1}$ well-defined. That is, we do not rely on
$\bar{P}$ to make $\frac{1}{L_{0}}$ well-defined, it is present only for power
counting purposes.

We continue with the first term in (35) and to do this we first calculate

$\displaystyle
U_{\frac{8}{3}}\frac{b_{0}}{L_{0}}\bar{P}cV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)|0\rangle=$
(42) $\displaystyle
U_{\frac{8}{3}}\frac{b_{0}}{L_{0}}\bar{P}\biggr{(}cV\left(\frac{1}{\sqrt{3}}\right)cV\left(-\frac{1}{\sqrt{3}}\right)$
$\displaystyle\pm\sum_{V^{\prime}}C_{VVV^{\prime}}\left(\frac{2}{\sqrt{3}}\right)^{1+h^{\prime}-2h}c\partial
cV^{\prime}(0)\biggr{)}|0\rangle$

where the OPE (37) was used so that we can Schwinger parametrise the action of
$L_{0}$ as

$\frac{1}{L_{0}}=\int_{0}^{1}\,\frac{ds}{s}s^{L_{0}}$ (43)

meaning that we use the Schwinger parametrisation on the plus branch and we
explicitly divide by weight on the minus branch. Doing so we obtain

$\displaystyle\int_{0}^{1}\,ds\biggr{[}\left(\derivative{\mu}{s}\right)^{2h-1}\frac{s^{2h-2}}{\sqrt{3}}\left(c\left(\mu\right)+c\left(-\mu\right)\right)V\left(\mu\right)V\left(-\mu\right)$
(44) $\displaystyle-\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}\left(\frac{2}{\sqrt{3}}\right)^{1+h^{\prime}-2h}\left(\frac{4}{3}\right)^{1-h^{\prime}}\biggr{(}\frac{1}{s^{2-h^{\prime}}}+\frac{1}{1-h^{\prime}}\biggr{)}$
$\displaystyle
cV^{\prime}(0)-C_{VVV}\left(\frac{2}{\sqrt{3}}\right)^{1-h}\left(\frac{4}{3}\right)^{1-h}\frac{1}{s^{2-h}}cV(0)\biggr{]}|0\rangle$

where $\mu(s)=\tan\frac{3}{4}\arctan\frac{s}{\sqrt{3}}$ is present since
$U_{\frac{8}{3}}$ implements the conformal transformation
$z\rightarrow\tan\frac{3}{4}\arctan z$.

The subterm in the first term of (35) containing $P$ can then be calculated as

$\displaystyle-C_{VVV}\left(\frac{8}{3\sqrt{3}}\right)^{1-h}$ (45)
$\displaystyle\langle c\partial
cV|\int_{0}^{1}\,ds\biggr{[}\left(\derivative{\mu}{s}\right)^{2h-1}\frac{s^{2h-2}}{\sqrt{3}}\left(c\left(\mu\right)+c\left(-\mu\right)\right)V\left(\mu\right)V\left(-\mu\right)$
$\displaystyle-\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}\left(\frac{2}{\sqrt{3}}\right)^{1+h^{\prime}-2h}\left(\frac{4}{3}\right)^{1-h^{\prime}}\biggr{(}\frac{1}{s^{2-h^{\prime}}}+\frac{1}{1-h^{\prime}}\biggr{)}$
$\displaystyle
cV^{\prime}(0)-C_{VVV}\left(\frac{2}{\sqrt{3}}\right)^{1-h}\left(\frac{4}{3}\right)^{1-h}\frac{1}{s^{2-h}}cV(0)\biggr{]}|0\rangle$
$\displaystyle=g_{0}C_{VVV}^{2}\ln\frac{4}{\sqrt{3}}a+O(y)$

where $a\equiv\tan\frac{\pi}{8}=\sqrt{2}-1$ and $\innerproduct{c\partial
cV}{cW}=0$.

The final term to calculate is then

$\displaystyle\langle
cV\left(\sqrt{3}\right)cV\left(-\sqrt{3}\right)U_{\frac{8}{3}}^{*}$ (46)
$\displaystyle\int_{0}^{1}\,ds\biggr{[}\left(\derivative{\mu}{s}\right)^{2h-1}\frac{s^{2h-2}}{\sqrt{3}}\left(c\left(\mu\right)+c\left(-\mu\right)\right)V\left(\mu\right)V\left(-\mu\right)$
$\displaystyle-\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}\left(\frac{2}{\sqrt{3}}\right)^{1+h^{\prime}-2h}\left(\frac{4}{3}\right)^{1-h^{\prime}}\biggr{(}\frac{1}{s^{2-h^{\prime}}}+\frac{1}{1-h^{\prime}}\biggr{)}cV^{\prime}(0)$
$\displaystyle-
C_{VVV}\left(\frac{2}{\sqrt{3}}\right)^{1-h}\left(\frac{4}{3}\right)^{1-h}\frac{1}{s^{2-h}}cV(0)\biggr{]}\rangle$
$\displaystyle=\int_{0}^{1}\,ds\biggr{[}\frac{4}{\sqrt{3}a}\left(\frac{1}{a^{2}}-\mu^{2}\right)\derivative{\mu}{s}\langle
V\left(-\frac{1}{a}\right)V\left(\frac{1}{a}\right)V\left(\mu\right)V\left(-\mu\right)\rangle$
$\displaystyle-g_{0}\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\left(\sqrt{3}a\right)^{h^{\prime}-1}\biggr{(}\frac{1}{s^{2-h^{\prime}}}+\frac{1}{1-h^{\prime}}\biggr{)}-C_{VVV}^{2}\frac{g_{0}}{s}\biggr{]}$
$\displaystyle+O(y)$

It turns out that we can exploit the generic form of the 4-pt function [24]

$\displaystyle\langle V(z_{1})V(z_{2})V(z_{3})V(z_{4})\rangle=$ (47)
$\displaystyle\left(z_{12}z_{13}z_{14}z_{23}z_{24}z_{34}\right)^{-\frac{2}{3}h}G(\xi)$

where $\xi$ is the cross-ratio

$\xi=\frac{z_{12}z_{34}}{z_{13}z_{24}}$ (48)

and $G(\xi)$ is an invariant part of the 4-pt function to dramatically
simplify

$\displaystyle\int_{0}^{1}\,ds\biggr{[}\frac{4}{\sqrt{3}a}\left(\frac{1}{a^{2}}-\mu^{2}\right)\derivative{\mu}{s}\langle
V\left(-\frac{1}{a}\right)V\left(\frac{1}{a}\right)V\left(\mu\right)V\left(-\mu\right)\rangle\biggr{]}$
(49) $\displaystyle=\int_{0}^{\frac{1}{2}}\,d\xi\langle V|V(1)V(\xi)|V\rangle$

We could now transform the subtractions via inverting $\xi(s)$, where the
cross-ratio depends on $s$ as follows

$\xi(s)=4a\frac{\tan\left(\frac{3}{4}\arctan\left(\frac{s}{\sqrt{3}}\right)\right)}{\biggr{[}1+a\tan\left(\frac{3}{4}\arctan\left(\frac{s}{\sqrt{3}}\right)\right)\biggr{]}^{2}}$
(50)

We employ however a different procedure, that is, we imagine that we employ a
near-zero cutoff $\tilde{\epsilon}$ of the manisfestly finite contribution
(46) to separate the subtractions from the 4-pt function into two integrals
and in the end we take $\epsilon\equiv\xi(\tilde{\epsilon})$ to zero. One
finds that

$\tilde{\epsilon}(\epsilon)=\sqrt{1+\frac{2\sqrt{2}}{3}}\epsilon+\sqrt{\frac{1}{4}+\frac{1}{3\sqrt{2}}}\epsilon^{2}+O(\epsilon^{3})$
(51)

The integral of the subtractions is then easily evaluated to be

$\displaystyle\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\left(\sqrt{3}a\right)^{h^{\prime}-1}\frac{\tilde{\epsilon}^{h^{\prime}-1}}{h^{\prime}-1}+C_{VVV}^{2}\ln\tilde{\epsilon}$
(52) $\displaystyle=\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\biggr{(}\frac{\epsilon^{h^{\prime}-1}}{h^{\prime}-1}+\frac{1}{2}\delta_{h^{\prime}=0}\biggr{)}$
$\displaystyle+C_{VVV}^{2}(\ln\epsilon+\ln\frac{\sqrt{2}+1}{\sqrt{3}})+O(\epsilon)$

The integral over cross-ratio $\xi$ can be easily regulated by the OPE
structure of (37)

$\displaystyle\int_{\epsilon}^{\frac{1}{2}}\,d\xi\biggr{(}\langle
V|V(1)V(\xi)|V\rangle-
g_{0}\sum_{V^{\prime}}C_{VVV^{\prime}}^{2}\frac{1}{\xi^{2-h^{\prime}}}\biggr{)}$
(53) $\displaystyle+g_{0}\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\left(\frac{2^{1-h^{\prime}}}{h^{\prime}-1}-\frac{\epsilon^{h^{\prime}-1}}{h^{\prime}-1}\right)$
$\displaystyle+g_{0}C_{VVV}^{2}\left(\ln 2-\ln\epsilon\right)$

We see that the divergent terms cancel each other out and we can take
$\epsilon\rightarrow 0$. Putting all contributions together we obtain

$\displaystyle\mathcal{A}=\int_{0}^{\frac{1}{2}}\,d\xi\biggr{[}\langle
V|V(1)V(\xi)|V\rangle$ (54) $\displaystyle-
g_{0}\sum_{V^{\prime}}C_{VVV^{\prime}}^{2}\biggr{(}\frac{1}{\xi^{2-h^{\prime}}}+\frac{1}{(1-\xi)^{2-h^{\prime}}}\biggr{)}\biggr{]}$
$\displaystyle+g_{0}\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\biggr{(}\frac{1}{h^{\prime}-1}+\frac{1}{2}\delta_{h^{\prime}=0}\biggr{)}$
$\displaystyle+g_{0}C_{VVV}^{2}\left(\ln\frac{\sqrt{2}+1}{\sqrt{3}}+\ln\frac{81}{64}+\ln\frac{4a}{\sqrt{3}}\right)+O(y)$

where the $1-\xi$ subtractions were added for convenience. As a trivial
illustration of this formula we can take the exactly marginal free boson
$V=\partial X$ for which

$\langle\partial X|\partial X\left(1\right)\partial X\left(\xi\right)|\partial
X\rangle=1+\frac{1}{(1-\xi)^{2}}+\frac{1}{\xi^{2}}$ (55)

so that the four-point amplitude vanishes

$\mathcal{A}=\left(\int_{0}^{\frac{1}{2}}\,d\xi\right)-1+\frac{1}{2}=0$ (56)

as it should since (21) is then automatically satisfied for all $\lambda$ to
the next-to-leading order.

The final result for $\Delta g$ then simplifies to

$\frac{\Delta
g}{g_{0}}=-\frac{\pi^{2}}{3}\biggr{(}\frac{y^{3}}{C_{VVV}^{2}}+3\frac{\mathcal{\tilde{A}}}{C_{VVV}^{4}}y^{4}\biggr{)}+O(y^{5})$
(57)

where

$\displaystyle\mathcal{\tilde{A}}=\int_{0}^{\frac{1}{2}}\,d\xi\biggr{[}\frac{1}{g_{0}}\langle
V|V(1)V(\xi)|V\rangle$ (58)
$\displaystyle-\sum_{V^{\prime}}C_{VVV^{\prime}}^{2}\biggr{(}\frac{1}{\xi^{2-h^{\prime}}}+\frac{1}{(1-\xi)^{2-h^{\prime}}}\biggr{)}\biggr{]}$
$\displaystyle+\sum_{V^{\prime}\neq
V}C_{VVV^{\prime}}^{2}\biggr{(}\frac{1}{h^{\prime}-1}+\frac{1}{2}\delta_{h^{\prime}=0}\biggr{)}$

We note that the SFT constant $K$ does not decouple from the expression for
the SFT coupling

$\lambda=\frac{y}{C_{VVV}}+\frac{1}{C_{VVV}}\left(\frac{2\mathcal{\tilde{A}}}{C_{VVV}^{2}}+\ln
K\right)y^{3}+O(y^{4})$ (59)

This is expected since this is just an auxilliary normalisation factor of the
string field $\Psi_{1}$ and not a CFT coupling constant.

####  III.2.3 Leading order calculation of boundary state coefficients

By the KMS correspondence [18] we have for the shift in the boundary state
coefficient of the bulk primary $\phi$

$\Delta B_{\phi}=2\pi i\langle I|\tilde{\phi}(i)|\Psi\rangle$ (60)

where $\tilde{\phi}$ is $\phi$ dressed with ghosts and auxilliary CFT factors
that make it weight 1 and $\langle I|=\langle 0|U_{f}$ implements the
conformal transformation from the unit disk to the UHP
$f(z)=\frac{2z}{1-z^{2}}$. To leading order we can write

$\displaystyle\Delta B_{\phi}$ $\displaystyle=2\pi i\lambda\langle
I|U_{f}\tilde{\phi}(i)|cV\rangle+O(y^{2})$ (61) $\displaystyle=2\pi i\lambda
2i2^{\Delta_{\phi}-2}2^{h-1}\langle\phi(i)V(0)\rangle+O(y^{2})$
$\displaystyle=-2\pi g_{0}\frac{B_{\phi V}}{C_{VVV}}y+O(y^{2})$

where $\Delta_{\phi}$ is the weight of $\phi$ and in the derivation we used
the generic form of the bulk-boundary correlator

$\langle\phi(x+iy)V(r)\rangle_{UHP}=g_{0}\frac{B_{\phi
V}}{(2y)^{\Delta_{\phi}-h}\left((x-r)^{2}+y^{2}\right)^{h}}$ (62)

For the case of $\phi$ being identity we expect (61) to calculate $\Delta g$
to $O(y)$ and indeed it gives the expected result of zero by the virtue of
$B_{\phi 1}=0$. In the next-to-leading correction $\mathcal{A}$ enters through
$\lambda$ and we need to calculate the open-open-closed amplitude
$\langle\tilde{\phi}|\frac{b_{0}}{L_{0}}\bar{P}|cV*cV\rangle$ which can be
calculated by again using the trick of [20].

##  IV Outlook

We have shown that string field tames naturally divergences found in conformal
perturbation theory [27]. This is quite analogous to observation made by Sen
in [26]. It would be interesting to carry our calculations to higher orders
and see how far one can follow the RG flow and whether nice patterns emerge.
For this probably different gauges in string field theory might be useful,
such as the $\mathcal{B}_{0}$-gauge, possibly modified accounting for the
${\cal L}_{0}=0$ terms found in [28] or the pseudo-$\mathcal{B}_{0}$ gauge
introduced in [29]. Similar calculations have been reported in [30].
Interestingly our calculations seem to allow for possibility to follow the RG
flow in the opposite direction contrary to general expectations, but in line
with numerical calculations in OSFT [7].

Finally let us mention, that our calculations are entirely feasible in closed
string field theory where one should be able to learn about the elusive vacuum
of the closed string. Our preliminary results show that the value of the
closed string classical action $S$ evaluated on the solution is proportional
in the leading order to the change in the central charge $\Delta c$ of the CFT
where the condensation happens. Dilaton couplings seem to affect only the
higher order contributions, so the result to be in contradiction with recent
results in [31]. One possible resolution is that one has to incorporate the
Liouville sector even for the critical string.

## Acknowledgments

We thank Matěj Kudrna, Jakub Vošmera, Tomáš Procházka and Xi Yin for useful
discussions. This work has been supported by Grant Agency of the Czech
Republic, under the grant EXPRO 20-25775X.

## References

  * [1] J. L. Cardy, Nucl. Phys. B 275, 200-218 (1986) doi:10.1016/0550-3213(86)90596-1
  * [2] J. L. Cardy, Nucl. Phys. B 324, 581-596 (1989) doi:10.1016/0550-3213(89)90521-X
  * [3] D. C. Lewellen, Nucl. Phys. B 372, 654-682 (1992) doi:10.1016/0550-3213(92)90370-Q
  * [4] R. E. Behrend, P. A. Pearce, V. B. Petkova and J. B. Zuber, Nucl. Phys. B 570, 525-589 (2000) doi:10.1016/S0550-3213(99)00592-1 [arXiv:hep-th/9908036 [hep-th]].
  * [5] I. Affleck, M. Oshikawa and H. Saleur, Nucl. Phys. B 594, 535-606 (2001) doi:10.1016/S0550-3213(00)00499-5 [arXiv:cond-mat/0009084 [cond-mat]].
  * [6] M. Schnabl and J. Vošmera, [arXiv:1903.00487 [hep-th]].
  * [7] M. Kudrna, M. Rapcak and M. Schnabl, [arXiv:1401.7980 [hep-th]].
  * [8] M. Kudrna, [arXiv:2112.12213 [hep-th]].
  * [9] I. Affleck and A. W. W. Ludwig, Phys. Rev. Lett. 67, 161-164 (1991) doi:10.1103/PhysRevLett.67.161
  * [10] D. Friedan and A. Konechny, Phys. Rev. Lett. 93, 030402 (2004) doi:10.1103/PhysRevLett.93.030402 [arXiv:hep-th/0312197 [hep-th]].
  * [11] A. Recknagel, D. Roggenkamp and V. Schomerus, Nucl. Phys. B 588, 552-564 (2000) doi:10.1016/S0550-3213(00)00519-8 [arXiv:hep-th/0003110 [hep-th]].
  * [12] A. Sen, JHEP 12, 027 (1999) doi:10.1088/1126-6708/1999/12/027 [arXiv:hep-th/9911116 [hep-th]].
  * [13] M. Schnabl, Adv. Theor. Math. Phys. 10, no.4, 433-501 (2006) doi:10.4310/ATMP.2006.v10.n4.a1 [arXiv:hep-th/0511286 [hep-th]].
  * [14] T. Erler and C. Maccaferri, JHEP 10, 029 (2014) doi:10.1007/JHEP10(2014)029 [arXiv:1406.3021 [hep-th]].
  * [15] T. Erler, Phys. Rept. 980, 1-95 (2022) doi:10.1016/j.physrep.2022.06.004 [arXiv:1912.00521 [hep-th]].
  * [16] M. Kudrna and M. Schnabl, [arXiv:1812.03221 [hep-th]].
  * [17] H. Erbin, C. Maccaferri, M. Schnabl and J. Vošmera, JHEP 11, 123 (2020) doi:10.1007/JHEP11(2020)123 [arXiv:2006.16270 [hep-th]].
  * [18] M. Kudrna, C. Maccaferri and M. Schnabl, “Boundary State from Ellwood Invariants,” JHEP 07 (2013), 033 doi:10.1007/JHEP07(2013)033 [arXiv:1207.4785 [hep-th]].
  * [19] P. V. Larocca and C. Maccaferri, “BCFT and OSFT moduli: an exact perturbative comparison,” Eur. Phys. J. C 77 (2017) no.11, 806 doi:10.1140/epjc/s10052-017-5379-3 [arXiv:1702.06489 [hep-th]].
  * [20] N. Berkovits and M. Schnabl, “Yang-Mills action from open superstring field theory,” JHEP 09 (2003), 022 doi:10.1088/1126-6708/2003/09/022 [arXiv:hep-th/0307019 [hep-th]].
  * [21] M. Kudrna, C. Maccaferri, “Unpublished”
  * [22] M. Kudrna, M. Schnabl, J. Vošmera, “Unpublished”
  * [23] M. Schnabl, “Wedge states in string field theory,” JHEP 01 (2003), 004 doi:10.1088/1126-6708/2003/01/004 [arXiv:hep-th/0201095 [hep-th]].
  * [24] P. Di Francesco, P. Mathieu and D. Senechal, “Conformal Field Theory,” Springer-Verlag, 1997, ISBN 978-0-387-94785-3, 978-1-4612-7475-9 doi:10.1007/978-1-4612-2256-9
  * [25] T. Erler, JHEP 10, 055 (2022) doi:10.1007/JHEP10(2022)055 [arXiv:2204.12863 [hep-th]].
  * [26] A. Sen, JHEP 10, 119 (2019) doi:10.1007/JHEP10(2019)119 [arXiv:1902.00263 [hep-th]].
  * [27] Z. Komargodski and D. Simmons-Duffin, J. Phys. A 50, no.15, 154001 (2017) doi:10.1088/1751-8121/aa6087 [arXiv:1603.04444 [hep-th]].
  * [28] M. Kiermaier, Y. Okawa, L. Rastelli and B. Zwiebach, JHEP 01, 028 (2008) doi:10.1088/1126-6708/2008/01/028 [arXiv:hep-th/0701249 [hep-th]].
  * [29] M. Schnabl, Phys. Lett. B 654, 194-199 (2007) doi:10.1016/j.physletb.2007.08.023 [arXiv:hep-th/0701248 [hep-th]].
  * [30] P. V. Larocca and C. Maccaferri, Eur. Phys. J. C 77, no.11, 806 (2017) doi:10.1140/epjc/s10052-017-5379-3 [arXiv:1702.06489 [hep-th]].
  * [31] T. Erler, JHEP 10, 055 (2022) doi:10.1007/JHEP10(2022)055 [arXiv:2204.12863 [hep-th]].