# A Parameter Communication Optimization Strategy for Distributed Machine Learning in Sensors
## 3 Communication Optimization
### Theoretical Analysis  
Most of the machine learning programs can be transformed to iterative-convergent programs. They can be expressed as follows:  
\[L=f(X,M)=f(l_{i=1}^{N}\{x_{i},y_{i}\},M) \tag{1}\]  
where \(N\) is the total number of the dataset, \(\{x_{i},y_{i}\}\) is a sample of the dataset that \(y_{i}\) only in the labeled dataset, \(M\) is the machine learning model. The scale of the dataset and the model is very large, so the parallel strategy and distributed training are needed. If the stale threshold is set to \(s\), the worker node \(p\) with \(t\) iterations can access the model \(\widetilde{M}_{p,t}\) which is composed of the initial model and the updates. The model of SSP is as follows:  
\[\widetilde{M}_{p,t}=M_{0}+\left[\sum_{i=1}^{t-s-1}\sum_{j=1}^{p}u_{j,i}\right] +\left[\sum_{(i,j)\in U_{p,t}}u_{j,i}\right] \tag{2}\]\(U_{p,t}\) is the subset of the updates submitted by all P worker nodes from iteration \(t-s\) to \(t+s-1\). \(\left[\sum\limits_{i=1}^{t-s-1}\sum\limits_{j=1}^{P}u_{j,i}\right]\) is the correct updates of the previous iteration, \(\left[\sum\limits_{(i,j)\in U_{p,t}}u_{j,i}\right]\) is the best-effort updates of the current iteration. Next, we analyze the feasibility of SGD in DSP. For a convex function \(L=f(M)=\sum_{c=1}^{C}f_{c}(M)\), we use SGD to compute the minimizer \(M^{*}\) of the model. The gradient of each worker node is represented by \(\
abla f_{c}\), we assume \(f_{c}\) is convex, the stale threshold is set to s, and the performance factor of worker nodes is \(\alpha\). The updates of c iterations is \(u_{c}:=-\eta_{c}\
abla_{c}f_{c}(\widetilde{M}_{c})\). Then, similar to the derivation in [38; 39], we obtain the regret \(\mathrm{R}[M]\) as follows :  
\[\mathrm{R}[M]:=\left[\frac{1}{C}\sum\limits_{c=1}^{C}f_{c}(\widetilde{M}_{c}) \right]-f(M^{*})\leq\sum\limits_{c=1}^{C}\left\langle\
abla f_{c}(\widetilde{ M}_{c}),\widetilde{M}_{c}-M^{*}\right\rangle \tag{3}\]  
Under suitable conditions (\(f_{c}\) is \(L\)-Lipschitz and bounded diameter \(D(x\|x\prime)\leq F^{2}\)), the regret of DSP is bounded by:  
\[\mathrm{R}[M]\leq\sigma\mathrm{L}^{2}\sqrt{C}+F^{2}\frac{\sqrt{C}}{\sigma}+2 \sigma\mathrm{L}^{2}\Big{[}\Big{(}\frac{s}{\alpha}+1\Big{)}P\Big{]}^{2}+4 \sigma\mathrm{L}^{2}\Big{(}\frac{s}{\alpha}+1\Big{)}P\sqrt{C} \tag{4}\]  
And the step size is set to \(\eta_{c}=\frac{\sigma}{\sqrt{c}}\), where \(\sigma=\frac{\mathrm{F}}{\mathrm{L}\sqrt{2\big{(}\frac{s}{\alpha}+1\big{)}P}}\) with constants \(F\) and \(L\), we obtain the DSP theorem as follows:  
\[\mathrm{R}[M]\leq 4 FL\sqrt{2\Big{(}\frac{s}{\alpha}+1\Big{)}PC} \tag{5}\]  
The method shows that the model trained by DSP can converge to \(O(\sqrt{C})\), which means that DSP can ensure the convergence of distributed machine learning. The theorem in [38] only considers the upper limit of the number of error updates, and does not take the DEFT into the consideration, the convergence rate needs to be guaranteed by strict constant adjustment. The proposed method (Equation (5)) improves SSP based on the DEFT, and solves the two problems mentioned in Section 2.3. In our paper, the weak threshold \(w\) is used to represent the number of iterations performed by the worker node with the worst performance, and the performance factor \(\alpha\) is used to represent the difference in the performance of worker nodes. If the performance of each worker node in the cluster is similar, \(\alpha\) is close to 1, and the stale threshold \(s\) cannot be effectively converged, we take the weak threshold \(w\) instead of the stale threshold \(s\) as the constraint condition of SSP. If the performance of worker nodes is largely different, then \(\alpha\) is large, at this time, we can increase the stale threshold \(s\) according to Equation (5) which can also ensure a certain convergence rate, then Equation (5) can be amended to:  
\[\mathrm{R}[M]\leq\left\{ \begin{array}{l}4 FL\sqrt{2\big{(}\frac{s}{\alpha}+1 \big{)}PC},\ \alpha\gg 1\\ 4 FL\sqrt{2(w+1)PC},\alpha\approx 1\end{array} \right.