# ZenoPS: A Distributed Learning System Integrating Communication Efficiency and Security
## 5 Theoretical Analysis
### Convergence  
Now we prove the convergence of the proposed algorithm in the synchronous mode. For simplicity, we take \(\alpha=1\) in the synchronous mode. **Theorem 2** (Error bound of ZenoPS in the synchronous mode without compression). : _In addition to Assumption 1 (smoothness), Assumption 2 (bounded variance), Assumption 3 (bounded gradients), and Assumption 4 (global minimum), we assume that the compressors are disabled and that the validation data is close to the training data \(\|\
abla F_{r}(x)-\
abla F(x)\|\leq r,\forall x\in\mathbb{R}^{d}\) where \(r\geq 0\) and \(F_{r}(x)=\mathbb{E}[f_{r}(x;z\sim\mathcal{D}_{r})]\) (the expectation is taken with respect to \(z\)). Taking \(\epsilon=cH^{2}\eta^{2}\), we have the following error bound for ZenoPS in the synchronous mode:_  
\[\frac{\sum_{t\in[T]}\mathbb{E}\|\
abla F(x_{t-1})\|^{2}}{T}\] \[\leq\frac{F(x_{0})-F(x_{*})}{TH\eta\rho}+\frac{3+3\gamma+4\rho}{ 2\rho}LH\eta V_{3}+\frac{(4+3\gamma+4\rho)r\sqrt{V_{3}}+r^{2}-2c}{2\rho}+ \frac{(1+\gamma)\sqrt{V_{3}}\sigma}{\rho\sqrt{s_{r}}}.\]  
_Taking \(\eta=\frac{1}{\sqrt{TH}}\), \(s_{r}\propto TH\), we have_\[\frac{\sum_{t\in[T]}\mathbb{E}\|\
abla F(x_{t-1})\|^{2}}{T}\] \[\leq\mathcal{O}\left(\frac{F(x_{0})-F(x_{*})}{\sqrt{TH}\rho}\right) +\mathcal{O}\left(\frac{H}{\sqrt{TH}\rho}\right)+\mathcal{O}\left(\frac{\sigma }{\sqrt{TH}\rho}\right)+\frac{(4+3\gamma+4\rho)r\sqrt{V_{3}}+r^{2}-2c}{2\rho}.\]  
The error bound of ZenoPS is composed of four parts: the gap to the initial value \([F(x_{0})-F(x_{*})]\), the error caused and the infrequent synchronization that is proportional to \(H\), the noise caused by variance \(\sigma\), and the validation error caused by Byzantine tolerance \(\frac{(4+3\gamma+4\rho)r\sqrt{V_{3}}+r^{2}-2c}{2\rho}\). A better validation dataset that is closer to the training dataset with a smaller \(r\) decreases the validation error. Increasing \(c\) and \(\rho\) or decreasing \(\gamma\) decreases the validation error, but also potentially decreases the chances that benign updates pass the validation procedure, which can slow down the optimization progress. In short, stronger security guarantees smaller validation error, but also slower convergence. When the compressors are enabled, there is an additional error term with the approximation factor \(\delta\). **Theorem 3** (Error bound of ZenoPS in the synchronous mode with compression). : _In addition to Assumption 1 (smoothness), Assumption 3 (bounded gradients), and Assumption 4 (global minimum), we assume that the compressors are disabled and the validation data is close to the training data \(\|\
abla F_{r}(x)-\
abla F(x)\|\leq r,\forall x\in\mathbb{R}^{d}\) where \(r\geq 0\) and \(F_{r}(x)=\mathbb{E}[f_{r}(x;z\sim\mathcal{D}_{r})]\) (the expectation is taken with respect to \(z\)). Taking \(\epsilon=cH^{2}\eta^{2}\) and \(\eta=\frac{1}{\sqrt{TH}}\), we have the following error bound for ZenoPS in the synchronous mode:_  
\[\frac{\sum_{t\in[T]}\mathbb{E}\|\
abla F(x_{t-1})\|^{2}}{T}\] \[\leq\mathcal{O}\left(\frac{F(x_{0})-F(x_{*})}{\sqrt{TH}\rho} \right)+\mathcal{O}\left(\frac{H}{\sqrt{TH}\rho}\right)+\mathcal{O}\left( \frac{\sigma}{\sqrt{TH}\rho}\right)+\frac{(4+3\gamma+4\rho)r\sqrt{V_{3}}+r^{2 }-2c}{2\rho}\] \[\quad+\frac{(1-\delta)(1+\gamma)L\sqrt{H}V_{3}}{2\rho\sqrt{T} \Big{(}1-\sqrt{1-\delta}\Big{)}^{2}}.\]  
Finally, we prove the convergence of the proposed algorithm in the asynchronous mode. **Theorem 4** (Error bound of ZenoPS in the asynchronous model with compression). : _In addition to Assumption 1 (smoothness), Assumption 2 (bounded variance), Assumption 3 (bounded gradients), and Assumption 4 (global minimum), we assume that the validation data is close to the training data \(\|\
abla F_{r}(x)-\
abla F(x)\|\leq r,\forall x\in\mathbb{R}^{d}\) where \(r\geq 0\) and \(F_{r}(x)=\mathbb{E}[f_{r}(x;z\sim\mathcal{D}_{r})]\) (the expectation is taken with respect to \(z\)).