# ZenoPS: A Distributed Learning System Integrating Communication Efficiency and Security
## 3 Preliminaries
### Distributed SGD  
In this paper, we use distributed SGD to solve the optimization problem (1). In each iteration, a random mini-batch of data \(z_{i}\) is sampled from the training dataset of any worker \(i\), which is used to compute the local stochastic gradient \(g_{i}\). We then rescale \(g_{i}\) with the learning rate \(\eta\) and update the model parameters \(x\).  
There are typically two strategies to execute distributed training with SGD: synchronous and asynchronous. In synchronous training, the combination of the updates aggregated from all workers are applied to the global model parameters in every step. In contrast, for asynchronous training, the global model parameters are immediately updated by any single worker without waiting for the other workers [36; 37; 38]. Typically, synchronous training is more stable with less noise, but it is also slower due to the global barrier across all workers. Asynchronous training is faster, but any asynchronous training technique needs to address instability and noisiness due to staleness.  
The detailed distributed synchronous SGD algorithm is shown in Algorithm 1. In each iteration, every worker computes the stochastic gradient on a random mini-batch of data and then takes the average over the gradients from all workers. The averaged gradient is used to update the global model parameters in the same way as vanilla SGD. The global averaging incurs communication overhead.  
```
1:Initialize \(x_{0}\in\mathbb{R}^{d}\)
2:for all iteration \(t\in[T]\)do
3:for all workers \(i\in[n]\) in parallel do
4:\(g_{i,t}\leftarrow\
abla f(x_{t-1};z_{i,t})\)
5:endfor
6: Synchronization: \(\bar{g}_{t}\leftarrow\frac{1}{n}\sum_{j\in[n]}g_{j,t}\)
7:\(x_{t}\gets x_{t-1}-\eta g_{t}\)
8:endfor
```  
**Algorithm 1** Distributed synchronous stochastic gradient descent (DS-SGD).  
The detailed distributed asynchronous SGD algorithm is shown in Algorithm 2. In each iteration, the global model parameters are updated by the stochastic gradient from an arbitrary worker. Note that such a stochastic gradient is based on the model parameters from any previous iteration instead of the last iteration. There is a central node that maintains the latest version of the global model parameters. Pushing the stochastic gradient from any worker to the central node and pulling the model parameters from the central node to any worker incur communication overhead.  
In brief, if the same number of stochastic gradients are applied to the global model parameters, then synchronous SGD and asynchronous SGD have the same communication overhead. The main difference is that the global updates are blocked until all gradients are collected for synchronous training, while for asynchronous training, the global updates are executed whenever the stochastic gradients arrive. Furthermore, since the stochastic gradients are potentially based on the model parameters previous to the latest version, such staleness incurs additional noise to the convergence.  
```
1:Initialize \(x_{0}\in\mathbb{R}^{d}\)
2:for all iteration \(t\in[T]\)do
3: arbitrary worker \(i\in[n]\):
4:\(g_{t}\leftarrow\
abla f(x_{t};z_{i,t^{\prime}}),t^{\prime}<t\)
5:\(x_{t}\gets x_{t-1}-\eta g_{t}\)
6:endfor
```  
**Algorithm 2** Distributed asynchronous stochastic gradient descent (DA-SGD).