# Communication-Efficient Federated Learning with Adaptive Consensus ADMM
## 4 Analysis  
The goal of this section is to establish the global convergence for FedACADMM. We initially assert that the chosen stopping criterion is reasonable. Let \(\{(w_{i},y_{i}^{t},\theta^{t})\}\) be the sequence created by our approach in the following analysis. We try to prove that \(\{(w_{i},y_{i}^{t},\theta_{i})\}\) converges to a solution point \(\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\). We rewrite the task of FL to find the optimal parameter \(\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\) that minimizes the overall loss,  
\[\min_{w_{i},\theta^{t}}\sum_{i=1}^{m}\alpha_{i}f_{i}(w_{i}),\text{ s.t. }w_{i}=\theta^{t},i\in[m]. \tag{12}\]  
we also denote \(F(W):=\sum_{i=1}^{m}\alpha_{i}f_{i}(\mathbf{w}_{i})\), where \(F(w,w,...,w)=f(w)\). The solution point \(\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\) is a stationary point of (12) if it satisfies,  
\[\left\{ \begin{aligned} a_{i}\
abla f_{i}(w_{i}^{*})+y_{i}^{*}& =0,& i\in[m]\\ w_{i}^{*}-\theta^{*}&=0,& i\in[m]\\ \sum_{i=1}^{m}y_{i}^{*}&=0\end{aligned} \right. \tag{13}\]  
It is not difficult to prove that any locally optimal solution to problem (12) must satisfy (13). If \(f_{i}\) is a convex function, then there is one and only one point that is a globally optimal solution when satisfying (13). Moreover, a solution point \(\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\) of (12) indicates  
\[\
abla f(\mathbf{w}^{*})=\sum_{i=1}^{m}\alpha_{i}\
abla f_{i}(\mathbf{w}^{*}) =-\sum_{i=1}^{m}\pi_{i}^{*}=0 \tag{14}\]  
So, \(w_{i}^{*}\) is also a solution point of  
\[\mathbf{w}_{i}^{*}:=\underset{\mathbf{w}\in\mathbb{R}^{n}}{\operatorname{ argmin}}f(\mathbf{w}) \tag{15}\]  
Let us consider the differences between \(\|y^{t}-y^{*}\|^{2}\) and \(\|y^{t+1}-y^{*}\|^{2}\). Combine \(\|y^{t}-y^{*}\|^{2}\) with the third equality of (7) and perform some modifications to get:  
\[\left\|y^{t}-y^{*}\right\|^{2}= \left\|y^{t+1}-y^{*}\right\|^{2}-\gamma^{2}(\rho^{t+1})^{2}\left\| w_{i}^{t+1}-\theta^{t+1}\right\|^{2}+2\gamma\rho^{t+1}(y^{t}-y^{*})^{\top}(w_{i} ^{t+1}-\theta^{t+1})\] (16) We provide some lemmas to help prove the main convergence theory and the following lemma provides a desirable property of the last term of (16). **Lemma 1**. : _For \(\forall\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\), we have_  
\[(y^{t}-y^{*})^{\top}(w_{i}^{t+1}-\theta^{t+1})\geq\rho^{t+1}\Big{\|}w_{i}^{t+1}- \theta^{t+1}\Big{\|}^{2}+\rho^{t+1}\times(w_{i}^{t+1}-w_{i}^{*})^{\top}(\theta^ {t+1}-\theta^{t}) \tag{17}\]  
Proof of Lemma 1.: For \(\forall\{(w_{i}^{*},y_{i}^{*},\theta^{*})\}\), we have  
\[(w_{i}^{t+1}-w_{i}^{*})^{\top}[fw_{i}^{*})-y_{i}^{*}]\geq 0 \tag{18}\]  
\[(\theta^{t+1}-\theta^{*})^{\top}[g(\theta^{*})-y_{i}^{*}]\geq 0 \tag{19}\]  
\[w_{i}^{t+1}-\theta^{t+1}=0 \tag{20}\]  
In the previous local update:  
\[(w_{i}^{t}-w_{i}^{t+1})^{\top}\Big{\{}f(w_{i}^{t+1})-\Big{[}y_{i}^{t}-\rho^{t+ 1}(w_{i}^{t+1}-\theta^{t})\Big{]}\Big{\}}\geq 0 \tag{21}\]  
\[(\theta^{t}-\theta^{t+1})^{\top}\Big{\{}g(\theta^{t+1})-\Big{[}y_{i}^{t}-\rho ^{t+1}(w_{i}^{t+1}-\theta^{t+1})\Big{]}\Big{\}}\geq 0 \tag{22}\]  
Similarly, we can get:  
\[(w_{i}^{*}-w_{i}^{t+1})^{\top}\Big{\{}f(w_{i}^{t+1})-\Big{[}y_{i}^{t}-\rho^{t+ 1}(w_{i}^{t+1}-\theta^{t})\Big{]}\Big{\}}\geq 0 \tag{23}\]  
\[\mathbf{w}_{i}^{*}:=\underset{\mathbf{w}\in\mathbb{R}^{n}}{\operatorname{ argmin}}f(\mathbf{w}) \tag{15}\]0  
We obtain by adding (18) and (23), and using the monotonicity of the operator \(f\):  
\[\mathbf{w}_{i}^{*}:=\underset{\mathbf{w}\in\mathbb{R}^{n}}{\operatorname{ argmin}}f(\mathbf{w}) \tag{15}\]1  
The same can be obtained by adding (19) and (24):  
\[\mathbf{w}_{i}^{*}:=\underset{\mathbf{w}\in\mathbb{R}^{n}}{\operatorname{ argmin}}f(\mathbf{w}) \tag{15}\]2  
Now that (25) and (26) have been combined, together with (20), we have the statement of this lemma. So, we can obtain the inequality:  
\[ \begin{split}&\big{\|}y^{t}-y^{*}\big{\|}^{2}\geq\Big{\|}y^{t+1}-y^{* }\Big{\|}^{2}-\gamma(2-\gamma)(\rho^{t+1})^{2}\Big{\|}w_{i}^{t+1}-\theta^{t+1} \Big{\|}^{2}\\ &+2\gamma\rho^{t+1}(w_{i}^{t+1}-w_{i}^{*})^{\top}(w_{i}^{t+1}- \theta^{t+1})\end{split}