\section{Introduction}
\IEEEPARstart{C}{F}{ederated}  learning (FL), as an effective machine learning technique, gains popularity in recent years due to its ability to deal with various issues like data privacy, data security, and data access  to heterogeneous data. Typical applications include  vehicular communications \cite{samarakoon2019distributed, pokhrel2020federated,
elbir2020federated, posner2021federated}, digital health 
\cite{rieke2020future}, and  smart manufacturing \cite{fazel2013hankel}, just to name a few. The earliest work for FL can be traced back to \cite{konevcny2015federated} in 2015  and \cite{konevcny2016federated} in 2016. It is still undergoing development and also facing many challenges \cite{kairouz2019advances,li2020federated,qin2021federated}.
\subsection{Related work}
{\it Gradient descent-based learning.}  In recent years, there is an impressive body of work on developing FL algorithms. One of the most popular approaches benefits from the stochastic gradient descent (SGD). The general framework is to run certain steps of SGD in parallel by clients/devices and then average the resulting parameters from clients by a central server once in a while.
Representatives of SGD family consists of the  famous Federated averaging ({\tt FedAvg} \cite{mcmahan2017communication}) and Local SGD ({\tt LocalSGD} \cite{stich2018local, Lin2020Don}). Other state-of-the-art ones can be seen in \cite{DeepLearning2015, AsynchronousStochastic2017,  yu2019parallel, wang2021cooperative}. These algorithms execute global averaging/aggregation periodically and thus can reduce the communication rounds (CR), thereby saving resources (e.g., transmission power and bandwidth in wireless communication) for real-world applications. 

However, to establish the convergence theory, most SGD algorithms assume that the local data is identically and independently distributed (i.i.d.), which is unrealistic for FL applications where data is usually heterogeneous. More details can be referred to  the {\tt LocalSGD} \cite{stich2018local}, K-step averaging SGD \cite{zhou2017convergence},  and Cooperative SGD \cite{wang2021cooperative}.

A parallel line of research aims to investigate gradient descent (GD) based-FL algorithms. Since full data is used to construct the gradient, these algorithms do not impose assumptions on distributions of the involved data \cite{smith2018cocoa, LAG2018, wang2019adaptive, liu2021decentralized, tong2020federated}.  Nevertheless, strong conditions for the objective functions of the learning optimization problems are still required to guarantee the convergence. Typical assumptions are gradient Lipschitz continuity (also known as L-smoothness), strong smoothness, convexity, or strong convexity. 



{\it ADMM-based learning.} The alternating direction method of multipliers (ADMM) has shown its advances both in theoretical and numerical aspects over the last few decades, with extensive applications into various disciplines. In particular,  there is a success of implementation ADMM in distributed learning \cite{boyd2011distributed,song2016fast,
zhang2018improving,zheng2018stackelberg,elgabli2020fgadmm}. Fairly recently, ADMM-based FL draws much attention due to its simple structure and easy implementation. They can be categorized into two classes: exact and inexact ADMM. The former aims at updating local parameters through solving sub-problems exactly, which hence brings more computational burdens for local clients \cite{ zhang2016dynamic, Li2017RobustFL, guo2018practical, huang2019dp, zhang2018recycled}. 


Therefore, inexact ADMM is an alternative to reduce the computational complexity for clients \cite{ding2019stochastic, Inexact-ADMM2021, ryu2022differentially, zhang2020fedpd}, where clients update their parameters via solving sub-problems approximately, thereby alleviating the computational burdens and accelerating the learning speed. Again, we shall emphasize that those algorithms that have been established for convergence properties still impose some restrictive assumptions. Fairly recently,  an algorithm from the primal-dual optimization perspective was developed in \cite{zhang2020fedpd} and turned out to be a member of inexact ADMM-based FL. It is shown that the algorithm converges under weaker assumptions. Finally, it is worth mentioning that ADMM is very useful in FL for the purpose of data privacy \cite{zhang2016dynamic, guo2018practical, zhang2018recycled, ding2019stochastic, huang2019dp,  ryu2022differentially}.


 



\subsection{Our contributions}
 

The main contribution of this paper is to develop a new FL  algorithm that is capable of saving communication resources, reducing computational burdens, and converging under relatively weak assumptions. 

 I) The proposed algorithm, {\tt FedGiA}\ in Algorithm \ref{algorithm-CEADMM}, has a novel framework.  After each round of communication (i.e., iteration $k$ is a multiple of a given integer $k_0$), all clients are split into two groups randomly.  One group adopts the scheme of the inexact ADMM to update their parameters $k_0$ times. While the second group exploits the GD approach to update their parameters just once. Therefore, {\tt FedGiA}\ possesses three advantages as follows.
 \begin{itemize}
 \item It is communication-efficient since CR can be controlled by setting $k_0$. Our numerical experiments have shown that CR decline when $k_0$ increases, see Figure \ref{fig:effect-k0-diff}.

 \item It is computation-efficient due to the nature of inexact updates for all local clients. The communication efficiency has been demonstrated by our numerical comparisons with two state-of-the-art algorithms, see Table \ref{tab:com-linear}.

 \item It is possible to cope with scenarios where a portion of clients are in bad conditions. The sever could select them for the second group where less effort is required to update their parameters.
\end{itemize}  
 
  
II) The assumptions to guarantee the convergence are mild. We prove that  {\tt FedGiA}\ converges to a stationary point (see Definition \ref{def-sta}) of the learning optimization problem in \eqref{FL-opt} with a linear rate $O(k_0/k)$ only under two conditions: gradient Lipschitz continuity (also known for the L-smoothness in many publications)  and the boundedness of a level set, as shown in Theorem \ref{global-convergence-exact}. These conditions do not impose convexity or strong convexity. Hence, they are weaker than those used to establish convergence for  most current distributed learning and FL  algorithms. If we further assume the convexity, then  {\tt FedGiA}\  achieves the optimal solution, as shown in Corollary \ref{L-global-convergence}. 
 
 


\subsection{Organization and notation}
This paper is organized as follows.  In the next section, we introduce FL  and the framework of ADMM.  In  Section \ref{sec:ceadmm},  we present {\tt FedGiA}\ and highlight its advantages, followed by the establishment of its global convergence and convergence rate in Section \ref{sec:convergence}.  We  then conduct some numerical experiments and comparisons with two popular algorithms to demonstrate the performance of  {\tt FedGiA}\  in Section  \ref{sec:num}.  Concluding remarks are given in the last section.  



We end this section with summarizing the notation that will be employed throughout this paper. We use  plain,  bold, and capital letters to present scalars, vectors, and matrices, respectively, e.g., $m , r,$ and $\sigma$ are scalars, $\mathbf{x}, \mathbf{x}_i$ and $\mathbf{x}_i^k$  are vectors, $X $ and $X ^k$ are matrices. Let $\lfloor t\rfloor$ represent  the largest integer strictly smaller than $t+1$ and $[m]:=\{1,2,\ldots,m\}$ with `$:=$' meaning define.  In this paper, ${\mathbb  R}^n$ denotes the $n$-dimensional Euclidean space equipped with the inner product $\langle\cdot,\cdot\rangle$ defined by $\langle\mathbf{x},\mathbf{y}\rangle:=\sum_i x_iy_i$. Let $\|\cdot\|$ be the Euclidean norm for vectors (i.e., $\|\mathbf{x}\|^2=\langle\mathbf{x},\mathbf{x}\rangle$) and Spectral norm for matrices, and $\|\cdot\|_H$ be the  weighted norm defined by  $\|\mathbf{x}\|_H^2:=\langle H\mathbf{x},\mathbf{x}\rangle$.
 Write the identity matrix as $I$ and a positive semidefinite matrix $A$ as $A\succeq 0$. In particular, $A\succeq B$ represents $A-B\succeq 0$.  A function, $f$, is said to be gradient Lipschitz continuous with a constant $r>0$ if 
 \begin{eqnarray}\label{Lip-r} 
\|\nabla f(\mathbf{x})-\nabla f(\mathbf{z}  ) \|  \leq r\| \mathbf{x} -\mathbf{z}  \|.
  \end{eqnarray}
for any $\mathbf{x}$ and $\mathbf{z}$, where $\nabla  f(\mathbf{x})$  represents the gradient of $f$ with respect to $\mathbf{x}$.
 


 
 \section{GD and inexact ADMM-based FL}
Suppose we have $m$ local clients/edge nodes with datasets $\{{\mathcal D}_1,{\mathcal D}_2,\ldots,{\mathcal D}_m\}$. Each client has the total loss $f_i(\mathbf{x}) := \frac{1}{d_i}\sum_{(\mathbf{a},b)\in{\mathcal D}_i} \ell_i(\mathbf{x}; (\mathbf{a},b))$, where $\ell_i(\cdot; (\mathbf{a},b)):{\mathbb  R}^n\mapsto{\mathbb  R}$ is a continuous loss function and bounded from below, $d_i$ is the cardinality of ${\mathcal D}_i$,  and $\mathbf{x}\in{\mathbb  R}^n$ is the parameter to be learned. Below are two examples  used for our numerical experiments.


\begin{example}[Least square loss] \label{ex:lr} Suppose the $i$th client has data ${\mathcal D}_i=\{(\mathbf{a}^i_1,b^i_1),\ldots,(\mathbf{a}^i_{d_i},b^i_{d_i})\}$, where $\mathbf{a}^i_j\in{\mathbb  R}^n$, $b^i_j\in{\mathbb  R}$.  Then the least square loss is
\begin{eqnarray} \label{least-squares}
 \arraycolsep=1.4pt\def1.5{1.5}
\begin{array}{llll}
f_i(\mathbf{x})&=& \sum_{j=1}^{d_i} \frac{1}{2d_i}(\langle \mathbf{a}^i_j,\mathbf{x}\rangle-b^i_j)^2.
\end{array} 
\end{eqnarray}
\end{example}
\begin{example}[$\ell_2$ norm regularized logistic loss]    \label{ex:lg}
Similarly, the $i$th client has data ${\mathcal D}_i$ but with $b^i_j\in\{0,1\}$. The $\ell_2$ norm regularized logistic loss is given by 
\begin{eqnarray} \label{logist-loss}
 \arraycolsep=1.4pt\def1.5{1.5}
\begin{array}{llll}
f_i(\mathbf{x})&=
\frac{1}{d_i}\sum_{j=1}^{d_i}[\ln (1+e^{\langle\mathbf{a}^i_j,\mathbf{x}\rangle} )-b^i_j\langle\mathbf{a}^i_j,\mathbf{x}\rangle+\frac{\mu}{2}\|\mathbf{x}\|^2],
\end{array} 
\end{eqnarray}
where  $\mu>0$ is a penalty parameter.
\end{example}
The overall loss function  can be defined by 
\begin{eqnarray*}\begin{array}{lll}
f(\mathbf{x}) :=   \frac{1}{m}\sum_{i=1}^{m}   f_i(\mathbf{x}),
\end{array}\end{eqnarray*}
  Federated learning aims to learn a best parameter $\mathbf{x}^*$  that reaches  the minimal overall loss, namely,
\begin{eqnarray}\label{FL-opt}
 \arraycolsep=1.4pt\def1.5{1.5}
\begin{array}{lll}
 \mathbf{x}^*:={\rm argmin}_{\mathbf{x}\in{\mathbb  R}^n }~f(\mathbf{x}).
\end{array}\end{eqnarray}
Since $f_i$ is bounded from below, we have
\begin{eqnarray}\label{FL-opt-lower-bound}\begin{array}{lll}
 f^*:=f(\mathbf{x}^*)>-\infty.
\end{array}\end{eqnarray}
 By introducing auxiliary variables, $\mathbf{x}_i=\mathbf{x}$,  problem  \eqref{FL-opt} can be equivalently rewritten as
\begin{eqnarray}\label{FL-opt-ver1}
 \arraycolsep=1.4pt\def1.5{1.5}
\begin{array}{lll}
 \underset{ \mathbf{x}, \mathbf{x}_1, \ldots,\mathbf{x}_m\in{\mathbb  R}^n}{\min}~~  \frac{1}{m}\sum_{i=1}^{m}  f_i(\mathbf{x}_i),~~{\rm s.t.}~~\mathbf{x}_i=\mathbf{x},~i\in[m].
\end{array}\end{eqnarray}
Throughout the paper, we shall place our interest on the above optimization problem. For simplicity, we also denote $X:=(\mathbf{x}_1, \mathbf{x}_2,\ldots,\mathbf{x}_m)$ and 
\begin{eqnarray}\label{FX}
\begin{array}{lll}
F(X):= \frac{1}{m} \sum_{i=1}^{m}  f_i(\mathbf{x}_i).
\end{array}\end{eqnarray}
It is easy to see that $f(\mathbf{x})=F(X)$ if $X=(\mathbf{x},\mathbf{x},\ldots,\mathbf{x})$.


\subsection{ADMM}
The backgrounds of ADMM can be referred to the earliest work \cite{gabay1976dual} and a nice book \cite{boyd2011distributed}.
To apply ADMM for problem \eqref{FL-opt-ver1}, by letting $X :=(\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_m)$ ad $\Pi:=({\boldsymbol  \pi}_1,{\boldsymbol  \pi}_2,\ldots,{\boldsymbol  \pi}_m)$, we introduce the augmented Lagrange function  defined by, 
\begin{eqnarray}\label{Def-L}
\arraycolsep=0pt\def1.5{1.5}
\begin{array}{lll}
&&{\mathcal L}(\mathbf{x},X ,\Pi) \\
&:=& \sum_{i=1}^{m} (\underset{=:L(\mathbf{x},\mathbf{x}_i ,{\boldsymbol  \pi}_i)}{\underbrace{  f_i(\mathbf{x}_i)/m+    \langle \mathbf{x}_i-\mathbf{x}, {\boldsymbol  \pi}_i\rangle + ({\sigma}/{2})\|\mathbf{x}_i-\mathbf{x}\|^2}}).
\end{array}\end{eqnarray}
Here, ${\boldsymbol  \pi}_i\in{\mathbb  R}^n,i\in[m]$ are the Lagrange multipliers and $\sigma >0$. The framework of ADMM for problem \eqref{FL-opt-ver1} is given as follows:   for an initialized point  $(\mathbf{x}^0, X^0, \Pi^0)$, perform the following updates iteratively for every $k\geq0$,
\begin{eqnarray}\label{framework-ADMM}
 \arraycolsep=1.5pt\def1.5{1.5}
\left\{\begin{array}{llll} 
  \mathbf{x}^{k+1} &=&  \underset{\mathbf{x} \in{\mathbb  R}^n}{\rm argmin} ~{\mathcal L}(\mathbf{x},X^{k+1}, \Pi^{k+1})\\
  &=&   \frac{1}{m}\sum_{i=1}^{m}  (\mathbf{x}^{k+1}_i+ \frac{1}{\sigma} {{\boldsymbol  \pi}_i^{k+1}}),\\
    \mathbf{x}^{k+1}_i &=&  \underset{\mathbf{x}_i\in{\mathbb  R}^n}{\rm argmin} ~L(\mathbf{x}^{k},\mathbf{x}_i, {\boldsymbol  \pi}_i^k ),& i\in[m], \\
  {\boldsymbol  \pi}^{k+1}_i &=&    {\boldsymbol  \pi}_i^{k} + \sigma(\mathbf{x}_i^{k+1}-\mathbf{x}^{k}),& i\in[m].\\
\end{array} \right.
\end{eqnarray}

\subsection{Stationary points}
To end this section, we present the optimality conditions of problems \eqref{FL-opt-ver1} and (\ref{FL-opt}).
\begin{definition}\label{def-sta} A point $(\mathbf{x}^*, X^*,\Pi^*)$ is a stationary point of   problem  (\ref{FL-opt-ver1}) if it satisfies 
\begin{eqnarray}\label{opt-con-FL-opt-ver1}
 \arraycolsep=1.0pt\def1.5{1.25}
  \left\{\begin{array}{rcll}
 \frac{1}{m}\nabla  f_i(\mathbf{x}_i^*)+{\boldsymbol  \pi}_i^* &=&   0, ~~&i\in[m],  \\  
 \mathbf{x}_i^*-\mathbf{x}^* &=&0,&i\in[m],\\ 
  \sum_{i=1}^{m} {\boldsymbol  \pi}_i^* &=& 0.
\end{array} \right.
\end{eqnarray} 
A point $\mathbf{x}^*$ is  a stationary point of   problem  (\ref{FL-opt}) if it satisfies 
\begin{eqnarray}\label{opt-con-FL-opt}
 \begin{array}{llll}
\nabla  f(\mathbf{x}^*)=0.
\end{array}
\end{eqnarray} 
\end{definition}
Note that any locally optimal solution to  problem  \eqref{FL-opt-ver1} (resp. (\ref{FL-opt})) must satisfy \eqref{opt-con-FL-opt-ver1} (resp. \eqref{opt-con-FL-opt}). If  $f_i$ is convex for every $i\in[m]$, then a point  is a globally optimal solution to  problem  \eqref{FL-opt-ver1} (resp.(\ref{FL-opt})) if and only if it satisfies condition \eqref{opt-con-FL-opt-ver1} (resp. \eqref{opt-con-FL-opt}).   Moreover, it is easy to see that a stationary point $(\mathbf{x}^*, X^*,\Pi^*)$  of   problem  \eqref{FL-opt-ver1} indicates
\begin{eqnarray*}
\begin{array}{llll}
~~~~\nabla   f(\mathbf{x}^*) =\frac{1}{m}\sum_{i=1}^{m}  \nabla   f_i(\mathbf{x}^*) 
=-\frac{1}{m} \sum_{i=1}^{m}  {\boldsymbol  \pi}_i^*=0.\end{array}
\end{eqnarray*} 
That is, $\mathbf{x}^*$ is also a stationary point of the   problem  \eqref{FL-opt}.  

\section{Algorithmic Design}\label{sec:ceadmm}
The framework of ADMM in \eqref{framework-ADMM} encounters three drawbacks in reality. (i) It repeats the three updates in every step, leading to communication inefficiency. In FL,  the framework manifests that local clients and the central server have to communicate at every step. However, frequent communications would come at a huge price, such as a long learning time and large amounts of resources. (ii) Solving the second sub-problem in  \eqref{framework-ADMM} would incur expensive computational cost as it generally does not admit a closed-form solution.   (iii) In real applications, some clients may suffer from bad conditions, which leads to computational difficulties. It is necessary to leave  them more time to update their parameters.  Therefore, to overcome the above mentioned drawbacks, we cast a new algorithm in  Algorithm \ref{algorithm-CEADMM}, where 
\begin{eqnarray*}   
\arraycolsep=1.5pt\def1.5{1.5}
\begin{array}{lllrll}
 \overline{\boldsymbol  g}_i^{k+1}&:=&\frac{1}{m}\nabla f_i(\mathbf{x}^{\tau_{k+1}}).
    \end{array}  
 \end{eqnarray*} 
The merits of Algorithm \ref{algorithm-CEADMM} are highlighted as follows. 





\begin{algorithm} 
\SetAlgoLined
{\noindent \justifying Given an integer $k_0>0$ and a constant $\sigma>0$, every client $i$ initializes $H_i\succeq0, \mathbf{x}_i^0$, ${\boldsymbol  \pi}_i^0$ and $\mathbf{z}^{0}_i =   \mathbf{x}_i^{0} + {{\boldsymbol  \pi}^{0}_i}/{\sigma}$,  $i\in[m]$.
Let $\tau_k$ be a function of $k$ as $\tau_k:=\lfloor k/k_0 \rfloor.$ }

\For{$k=0,1,2,3,\ldots$}{

\If{$k\in\K:=\{0,k_0,2k_0,3k_0,\ldots\}$}{
\vspace{1mm}
  \underline{\it Weights upload: (Communication occurs)} 
  
  {\justifying \noindent All clients  upload  $\{\mathbf{z}^{k}_1,\ldots,\mathbf{z}_m^k\}$ to the server.}  
 
\vspace{1mm}
\underline{\it Global aggregation:} 

The server calculates average parameter  $\mathbf{x}^{\tau_{k+1}}$ by 
 \begin{eqnarray}\label{ceadmm-sub1}
 \begin{array}{llll}
\mathbf{x}^{\tau_{k+1}} =  \frac{1}{m}\sum_{i=1}^m   \mathbf{z}_i^{k}.
\end{array}
\end{eqnarray}

\underline{\it Weights broadcast: (Communication occurs)}

The server  broadcasts  $\mathbf{x}^{\tau_{k+1}}$ to all clients.

\vspace{1mm}
\underline{\it Clients selection:} 

{\justifying \noindent The server randomly selects a new set $\mathcal{C}^{\tau_{k+1}}\subseteq [m]$ of clients for training in the next round.}
 
} 

\For{every $i\in\mathcal{C}^{\tau_{k+1}}$}{
\underline{\it Local update:} Client $i$ updates its parameters by  
\begin{eqnarray} 
     \label{ceadmm-sub2}
\hspace{-18mm}&& \begin{array}{llll}
\mathbf{x}^{k+1}_i  
 =    \mathbf{x}^{\tau_{k+1}} - (H_i/m  + \sigma  I)^{-1} (\overline{\boldsymbol  g}_i^{k+1}+ {\boldsymbol  \pi}_i^{k}), 
    \end{array}\\[1ex] 
\label{ceadmm-sub3}  
\hspace{-18mm}&&\begin{array}{llll}   
{\boldsymbol  \pi}^{k+1}_i =   {\boldsymbol  \pi}_i^{k} +\sigma(\mathbf{x}_i^{k+1}-\mathbf{x}^{\tau_{k+1}}),  
\end{array}\\[1ex]
\label{ceadmm-sub4}  
\hspace{-18mm}&&\begin{array}{llll}   
\mathbf{z}^{k+1}_i =   \mathbf{x}_i^{k+1}+{\boldsymbol  \pi}^{k+1}_i/\sigma.  
\end{array}
\end{eqnarray} }
\For{every $i\notin\mathcal{C}^{\tau_{k+1}}$}{
\underline{\it Local invariance:} Client $i$ keeps  parameters by   
\begin{eqnarray} 
\label{ceadmm-sub6}
\hspace{-18mm}&& \begin{array}{llll}
\mathbf{x}^{k+1}_i  \equiv   \mathbf{x}^{\tau_{k+1}}, 
    \end{array}\\[1ex] 
\label{ceadmm-sub7}  
\hspace{-18mm}&&\begin{array}{llll}   
{\boldsymbol  \pi}^{k+1}_i \equiv - \overline{\boldsymbol  g}_i^{k+1} ,  
\end{array}\\[1ex]
\label{ceadmm-sub8}  
\hspace{-18mm}&&\begin{array}{llll}   
\mathbf{z}^{k+1}_i \equiv  \mathbf{x}^{\tau_{k+1}} - \overline{\boldsymbol  g}_i^{k+1}/\sigma.  
\end{array}
\end{eqnarray} 
}

}
\caption{FL via  GD and inexact ADMM ({\tt FedGiA}) \label{algorithm-CEADMM}}
\end{algorithm}

 {\it (i) Communication efficiency:}
Algorithm \ref{algorithm-CEADMM} shows that communications only occur  when $k\in\K=\{0,k_0,2k_0,\ldots\},$ where $k_0$ is a predefined positive integer. Therefore, CR can be reduced if setting a big $k_0$, thereby  saving the cost vastly.  In fact, such an idea has been extensively used in literature \cite{DeepLearning2015,AsynchronousStochastic2017, stich2018local, yu2019parallel, Lin2020Don, wang2021cooperative}.


{\it (ii) Fast computation using inexact updates:} We update $\mathbf{x}^{k+1}_i$ by \eqref{ceadmm-sub2} instead of solving the second sub-problem in  \eqref{framework-ADMM}. It can accelerate the computation for local clients significantly, as the computation is relatively cheap if $H_i$ is chosen properly (e.g, diagonal matrices).  We point out that \eqref{ceadmm-sub2} is a result of 
\begin{eqnarray} 
\label{iceadmm-sub2-0}
 \arraycolsep=1pt\def1.5{1.5}
\begin{array}{llll}
\mathbf{x}^{k+1}_i  
& = &  {\rm argmin}_{\mathbf{x}_i}~ (1/m)h_i(\mathbf{x}_i; \mathbf{x}^{\tau_{k+1}})\\
&& + \langle \mathbf{x}_i-\mathbf{x}^{\tau_{k+1}}, {\boldsymbol  \pi}_i^{k}\rangle +\frac{\sigma }{2}\|\mathbf{x}_i-\mathbf{x}^{\tau_{k+1}}\|^2\\
&=&  \mathbf{x}^{\tau_{k+1}} - ( H_i/m  + \sigma  I)^{-1} (\overline{\boldsymbol  g}_i^{k+1}+ {\boldsymbol  \pi}_i^{k}),
    \end{array}  
\end{eqnarray}  
where $h_i(\mathbf{x}_i;\mathbf{z})$ is an approximation of $f_i(\mathbf{x}_i )$, namely,
\begin{eqnarray} 
\label{f-i-h-i} 
 \arraycolsep=1pt\def1.5{1.5}
 \begin{array}{lll} 
f_i(\mathbf{x}_i ) &\approx&\underset{=:h_i(\mathbf{x}_i;\mathbf{z})}{\underbrace{f_i(\mathbf{z}) +  \langle \nabla f_i(\mathbf{z}), \mathbf{x}_i-\mathbf{z}\rangle + ({1}/{2})  \| \mathbf{x}_i-\mathbf{z}\|^2_{H_i}}}.
    \end{array}
\end{eqnarray}

{\it (iii) Mixed updates:} 
At every $k\in\K$ in  Algorithm \ref{algorithm-CEADMM}, all clients are divided into two groups. For clients in $\mathcal{C}^{\tau_{k+1}}$, they update their parameters $k_0$ times based on the inexact ADMM, while for clients not in $\mathcal{C}^{\tau_{k+1}}$, they update their parameters just once based on the GD. This suggests that, in real applications, the sever should try to select clients with good devices to form  $\mathcal{C}^{\tau_{k+1}}$ and put the rest as the second group. This would leave clients in the second group having more time to update their parameters since they only need to update them once. 

We would like to point out that {\tt FedAvg} \cite{mcmahan2017communication,li2019convergence} and {\tt FedProx} \cite{li2020federatedprox} select partial devices to join in the training in each communication round. That is, if $k\in\K$, they randomly select a subset $\mathcal{C}^{\tau_{k+1}}$ of clients and only clients in $\mathcal{C}^{\tau_{k+1}}$ update their parameters and the rest clients remain unchanged. However, differing from that, {\tt FediAG} asks clients outside $\mathcal{C}^{\tau_{k+1}}$ for updating their parameters only once during $k_0$ steps.








\section{Convergence Analysis}\label{sec:convergence}
To establish the convergence, we need one assumption. 
\begin{assumption}\label{ass-fi} Every $f_i, i\in[m]$ is gradient Lipschitz continuous with a constant $r_i>0$. 
\end{assumption}
Assumption \ref {ass-fi} implies that there is always a $\Theta_i$ satisfying $r_iI\succeq \Theta_i \succeq 0$ such that
\begin{eqnarray} \label{grad-lip-theta}
 \arraycolsep=0pt\def1.5{1.5}
 \begin{array}{l}
f_i(\mathbf{x}_i)\leq   f_i(\mathbf{z}_i )+\langle \nabla  f_i(\mathbf{z}_i ), \mathbf{x}_i-\mathbf{z}_i \rangle + \frac{1}{2}\| \mathbf{x}_i-\mathbf{z}_i \|^2_{\Theta_i},
\end{array}
\end{eqnarray} 
for any $\mathbf{x}_i,\mathbf{z}_i\in{\mathbb  R}^n$. Apparently, many $\Theta_i$s satisfy  the above condition (e.g.,  $\Theta_i=r_iI$). In the subsequent convergence analysis, we suppose that every client $i$  chooses  $H_i=\Theta_i$.   \subsection{Global convergence}\label{sec:gc}
For notational convenience, hereafter we  let   $\mathbf{a}^{k} \rightarrow \mathbf{a}$ stand for $\lim_{k\rightarrow\infty} \mathbf{a}^{k} = \mathbf{a}$ and denote
\begin{eqnarray} \label{def-L-r}
 \arraycolsep=0pt\def1.5{1.5}
 \begin{array}{l}
{\mathcal L}^k:={\mathcal L}(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k}),\qquad r:=\max_{i\in[m]} r_i.
\end{array}
\end{eqnarray} 

With the help of Assumption \ref{ass-fi}, our first result shows that  whole sequences of  $\{{\mathcal L}^{k}\}$, $\{ F(X^{k})  \}$, and $\{f (\mathbf{x}^{\tau_{k}})\}$ converge. 

\begin{theorem}\label{global-obj-convergence-exact}   Let $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ be the sequence generated by Algorithm \ref{algorithm-CEADMM} with $H_i=\Theta_i, i\in[m]$ and  $\sigma > 6r/m$. The following results hold under Assumption \ref{ass-fi}.
 \begin{itemize}
 \item[i)] 
  Three  sequences $\{{\mathcal L}^{k}\}$, $\{ F(X^{k})  \}$, and $\{f (\mathbf{x}^{\tau_{k}})\}$ converge to the same value, namely,
   \begin{eqnarray}  \label{L-local-convergence-limit-1}
   \arraycolsep=1.4pt\def1.5{1.5}
   \begin{array}{lll}
  \lim\limits_{k\rightarrow \infty}  {\mathcal L}^{k} =  \lim\limits_{k\rightarrow \infty} F(X^{k})  = \lim\limits_{k\rightarrow \infty} f(\mathbf{x}^{\tau_{k}}).
    \end{array} 
 \end{eqnarray} 
 \item[ii)]  $\nabla F(X^{k})$ and $\nabla f(\mathbf{x}^{\tau_{k}})$ eventually vanish, namely, 
    \begin{eqnarray}  \label{L-local-convergence-limit-grad}
   \arraycolsep=1.4pt\def1.5{1.5}
   \begin{array}{lll}
  \lim\limits_{k\rightarrow \infty}\nabla F(X^{k})  = \lim\limits_{k\rightarrow \infty} \nabla f(\mathbf{x}^{\tau_{k}}) =0.
    \end{array} 
 \end{eqnarray} 
 \end{itemize}
 \end{theorem}  
 
  Theorem \ref{global-obj-convergence-exact}  states that the objective function values converge, and its establishment does not relied on the random selection of $\mathcal{C}^{\tau_{k+1}}$.  In the below theorem, we would like to see the convergence
performance of sequence $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ itself. To proceed with that, we need the assumption on the boundedness of the following level set    \begin{eqnarray} \label{level-set-S} 
  \begin{array}{l}
  {\mathcal S}(\alpha):=\{\mathbf{x}\in{\mathbb  R}^n: f(\mathbf{x})\leq \alpha\}
     \end{array}
  \end{eqnarray} 
   for a given $\alpha>0$.  We point out that the boundedness of the level set is frequently used in establishing the convergence properties of optimization algorithms. There are many functions satisfying this condition, such as the coercive functions\footnote{A continuous function $f:{\mathbb  R}^n\mapsto {\mathbb  R}$  is coercive if $ f(\mathbf{x})\rightarrow+\infty$ when $\|\mathbf{x}\|\rightarrow +\infty$.}.
  
  \begin{theorem}\label{global-convergence-exact}   Let $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ be the sequence generated by Algorithm \ref{algorithm-CEADMM} with $H_i=\Theta_i, i\in[m]$ and  $\sigma > 6r/m$. The following results hold under Assumption \ref{ass-fi} and the boundedness of ${\mathcal S}({\mathcal L}^0)$.
 \begin{itemize}
\item[i)]  Then sequence $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ is bounded, and any its accumulating point,  $(\mathbf{x}^{\infty},X^{\infty},\Pi^{\infty})$, is a stationary point of    (\ref{FL-opt-ver1}), where $\mathbf{x}^{\infty}$ is a stationary point of   (\ref{FL-opt}).
\item[ii)] If further assume that $\mathbf{x}^{\infty}$ is isolated, then the whole sequence,  $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$, converges to $(\mathbf{x}^{\infty},X^{\infty},\Pi^{\infty})$. 
  \end{itemize}
   \end{theorem}  
It is noted that if $f$ is locally strongly convex at $\mathbf{x}^{\infty}$, then $\mathbf{x}^{\infty}$ is unique and hence is isolated. However, being isolated is a weaker assumption than locally strong convexity. It is worth mentioning that the establishment of Theorem \ref{global-convergence-exact} does not require the convexity of $f_i$ or $f$, because of this, the sequence is guaranteed to converge to the stationary point of problems (\ref{FL-opt-ver1}) and (\ref{FL-opt}). In this regard, if we further assume the convexity of $f$, then the sequence is capable of converging to the optimal solution to problems (\ref{FL-opt-ver1}) and (\ref{FL-opt}), which is stated by the following corollary.
 
\begin{corollary}\label{L-global-convergence}Let $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ be the sequence generated by Algorithm \ref{algorithm-CEADMM} with $H_i=\Theta_i, i\in[m]$ and  $\sigma > 6r/m$.    The following results hold under Assumption \ref{ass-fi}, the boundedness of ${\mathcal S}({\mathcal L}^0)$, and the convexity of $f$.
\begin{itemize}
\item[i)] Three  sequences $\{{\mathcal L}^{k}\}$, $\{ F(X^{k})\}$, and $\{ f (\mathbf{x}^{\tau_{k}})\}$ converge to the optimal function value of (\ref{FL-opt}), namely
 \begin{eqnarray}  \label{L-global-convergence-limit}
   \arraycolsep=1.4pt\def1.5{1.5}
   \begin{array}{lll}
 \lim\limits_{k\rightarrow \infty}  {\mathcal L}^{k} = \lim\limits_{k\rightarrow \infty}  F(X^{k})= \lim\limits_{k\rightarrow \infty} f(\mathbf{x}^{\tau_{k}}) =  f^*.
    \end{array} 
 \end{eqnarray}   
 \item[ii)] Any accumulating point  $(\mathbf{x}^{\infty},X^{\infty},\Pi^{\infty})$ of   sequence  $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ is an optimal solution to  (\ref{FL-opt-ver1}), where $\mathbf{x}^{\infty}$ is an optimal solution to   (\ref{FL-opt}). 
 
\item [iii)]  If further assume $f$ is strongly convex. Then whole sequence  $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ converges the unique optimal solution, $(\mathbf{x}^*,X^*,\Pi^*)$, to  (\ref{FL-opt-ver1}), where $\mathbf{x}^*$ is the unique optimal solution to  (\ref{FL-opt}).  
\end{itemize} 
\end{corollary} 
  \begin{remark}Regarding the assumption in Corollary \ref{L-global-convergence}, we note that $f$ being strongly convex does not require that every $f_i,i\in[m]$ is strongly convex. If one of $f_i$s is strongly convex and the remaining is convex, then $f=\sum_{i=1}^{m} w_if_i$ is strongly convex.    Moreover, the strongly convexity suffices to the boundedness of level set  ${\mathcal S}(\alpha)$ for any $\alpha$. Therefore, under the strongly convexity, the assumption on the boundedness of ${\mathcal S}({\mathcal L}^0)$ can be exempted.
  \end{remark}
 \subsection{Complexity analysis}\label{sec:cs}
Finally, we investigate the convergence speed of the proposed  Algorithm \ref{algorithm-CEADMM}. The following result states that the minimal value among $\|\nabla f (\mathbf{x}^{\tau_{j}})\|^2, j\in[k]$  vanishes with a linear rate $O(rk_0/k)$.
\begin{theorem}\label{complexity-thorem-gradient}   Let $\{(\mathbf{x}^{\tau_{k}},X^{k},\Pi^{k})\}$ be the sequence generated by Algorithm \ref{algorithm-CEADMM} with $H_i=\Theta_i, i\in[m]$ and  $\sigma > 6r/m$. If Assumption \ref{ass-fi} holds, then  it follows
       \begin{eqnarray*}
  \arraycolsep=1.4pt\def1.5{1.5}
  \begin{array}{lllll}
    {\min}_{j\in[k]}  \| \nabla f (\mathbf{x}^{\tau_{j}})\|^2 
 \leq  \frac{\rho k_0}{k}  ({\mathcal L}^0 -f^*).
   \end{array}
  \end{eqnarray*}  
   where $\rho:=5m\sigma^2/\eta$ with $\eta$ given by (\ref{def-ci}). 
 \end{theorem}
 We would like to point out that the establishment of such a convergence rate only requires  the assumption of gradient Lipschitz continuity, namely, Assumption \ref{ass-fi}. Moreover, if we take $\sigma = t r/m$ with $t>6$, then
       \begin{eqnarray*}
  \arraycolsep=1.4pt\def1.5{1.5}
  \begin{array}{lllll}
  \frac{\rho k_0}{k}  = \frac{10t^3}{t^2-5t-6}\cdot  \frac{rk_0}{ k} = O(\frac{rk_0}{k}).
   \end{array}
  \end{eqnarray*} 
This is what we expected. The larger $k_0$ is, the more iterations is required to converge stated as below.
\begin{remark}\label{remark-com} Theorem \ref{complexity-thorem-gradient} hints that Algorithm \ref{algorithm-CEADMM} should be terminated if   
       \begin{eqnarray}\label{stopping-tol}
  \arraycolsep=0pt\def1.5{1.5}
  \begin{array}{lllll}
\| \nabla f (\mathbf{x}^{\tau_{k}})\|^2 \leq   \epsilon,
   \end{array}
  \end{eqnarray} 
  where $\epsilon$ is a given tolerance. Therefore,  after 
         \begin{eqnarray}\label{stopping-iter}
  \arraycolsep=0pt\def1.5{1.5}
  \begin{array}{lllll}
k =  \left\lfloor \frac{\rho k_0({\mathcal L}^0 -f^*) }{\epsilon} \right\rfloor=O(\frac{rk_0}{\epsilon})
   \end{array}
  \end{eqnarray} 
  iterations,  Algorithm \ref{algorithm-CEADMM} meets  (\ref{stopping-tol}) and the total CR are
         \begin{eqnarray}\label{stopping-iter}
  \arraycolsep=0pt\def1.5{1.5}
  \begin{array}{lllll}
CR:=\left\lfloor \frac{2k}{k_0} \right\rfloor  = \left\lfloor \frac{2\rho({\mathcal L}^0 -f^*) }{\epsilon}  \right\rfloor=O(\frac{r}{\epsilon}).
   \end{array}
  \end{eqnarray}  
 \end{remark} 
 


\section{Numerical Experiments}\label{sec:num}
This section conducts some numerical experiments to demonstrate the performance of {\tt FedGiA}\ in Algorithm \ref{algorithm-CEADMM}. All numerical experiments are implemented through MATLAB (R2019a) on a laptop with 32GB memory and 2.3Ghz CPU. 

 \subsection{Testing example}
 We use Example  \ref{ex:lr} with synthetic data and Example \ref{ex:lg} with real data to conduct the numerical experiments
 \begin{example}[Linear regression with non-i.i.d. data]\label{ex-linear} For this problem, local clients have their objective functions as (\ref{least-squares}). We randomly generate $d$ samples $(\mathbf{a}^i_1, b^i_1), i\in[d]$  from three distributions: the standard normal distribution, the Student's $t$ distribution with degree $5$, and the uniform distribution in $[-5,5]$. Then we shuffle all samples and  divided them into $m$ parts $(A_i, \mathbf{b}_i)$ for $m$ clients, where $A_i=(\mathbf{a}_1,\ldots,\mathbf{a}_{d_i})^\top$ and $\mathbf{b}_i=(b_1,\ldots,b_{d_i})^\top$. Therefore, $d=d_1\ldots+ d_m$.  The data size of each part, $d_i$, is randomly chosen from  $[50,150]$. For simplicity, we fix $n=100$,  but choose $m\in\{64,96,128,196,256\}$. In the reagrd, each client has non-i.i.d. data $(A_i, \mathbf{b}_i)$.
\end{example}
\begin{example}[Logistic regression]\label{ex-logist} For this problem,  local clients have their objective functions as (\ref{logist-loss}), 
where $\mu=0.001$ in our  numerical experiments.  We use two real datasets described in Table \ref{tab:datasets}  to generate $\mathbf{a}^i_j $ and $b^i_j$. We  randomly split $d$ samples into $m$ groups corresponding to $m$ clients
\end{example}
\begin{table}[!th]
	\renewcommand{1.5}{1.25}\addtolength{\tabcolsep}{0pt}
	\caption{Descriptions of  two real datasets.}\vspace{-3mm}
	\label{tab:datasets}
	\begin{center}
		\begin{tabular}{lllrrrr }
			\hline
Data&Datasets&	Source	&	$n$	&	$d$\\\hline
\texttt{qot}&	Qsar oral toxicity	&	uci	&	1024 	&	8992 	\\
 \texttt{sct}&	Santander customer transaction	&	kaggle	&	200 	&	200000 	\\
\hline
 		\end{tabular}
	\end{center}
	\vspace{-5mm}
\end{table}

\subsection{Implementations}
As mentioned in Remark \ref{remark-com}, we terminate  {\tt FedGiA}\ if $k\geq 10^4$ or solution
 $\mathbf{x}^{\tau_{k}}$ satisfies 
 \begin{eqnarray} \label{stopping}
 \arraycolsep=1.0pt\def1.5{1.5}
\begin{array}{r}
{\tt Error}:=\|\nabla f(\mathbf{x}^{\tau_{k}})\|^2
 \leq n10^{-9}.
\end{array} 
\end{eqnarray}
and initialize $\mathbf{x}_i^0={\boldsymbol  \pi}_i^0=0$. For every $k\in\K$, we randomly select $sm$ clients to form $\mathcal{C}^{\tau_{k+1}}$, namely, $|\mathcal{C}^{\tau_{k+1}}|=sm$ and $s\in(0,1]$. Here, $s=1$ means all clients are chosen.  Parameters $\sigma, H_i$ and $\mathcal{C}^{\tau_{k+1}}$ are set as follows. Theorem  \ref{L-global-convergence}   suggests that $\sigma $ should be chosen to satisfy $\sigma=tr/m$, where $t$ is given in Table \ref{tab:choice-Hi}. Finally, $H_i$ is chosen as Table \ref{tab:choice-Hi}, where {\tt FedGiA$_{\tt G}$}\ and {\tt FedGiA$_{\tt D}$}\ represent {\tt FedGiA}\ under $H_i$ opted as a Gram and Diagonal matrix, respectively.
\begin{table}[H]
	\renewcommand{1.5}{1.25}\addtolength{\tabcolsep}{1pt}
	\caption{Choices of $t$ and $H_i$.}\vspace{-3mm}
	\label{tab:choice-Hi}
	\begin{center}
		\begin{tabular}{llrr } \hline
  &  &	{\tt FedGiA$_{\tt G}$}	&	{\tt FedGiA$_{\tt D}$} \\ 
   &$t$ &	 $H_i$ &	 $H_i$ \\\hline
Example \ref{ex-linear}&$0.15$&	$\frac{1}{d_i}A_i^\top A_i$&	$\frac{1}{d_i}\|A_i^\top A_i\| $	\\
Example \ref{ex-logist}&$\max\{0.1,\frac{8}{n}{\rm ln}(d)\}$	&	$\frac{1}{4d_i}A_i^\top A_i $&	$\frac{1}{4d_i}\|A_i^\top A_i\|$\\
\hline
 		\end{tabular}
	\end{center} \vspace{-5mm}
\end{table}  

\subsection{Numerical performance}
In this part, we conduct some simulation to demonstrate the performance of {\tt FedGiA}\  including  global convergence,   convergence rate, and  effect of  $k_0$ and $\mathcal{C}^{\tau_{k+1}}$. To measure the performance, we report the following factors: $f(\mathbf{x}^{\tau_{k}})$,  error  $\|\nabla f(\mathbf{x}^{\tau_{k}})\|^2$, CR, and computational time (in second). We only report results of {\tt FedGiA}\ solving Example \ref{ex-linear}  and omit ones for  Example \ref{ex-logist} as they show  the similar observations.

\subsubsection{Global convergence with rate $O(k_0/k)$}
We   fix  $m=64, s=0.5$, and $k_0\in\{1,5,10,15,20\}$ and present the results in Figure \ref{fig:iterations-objective}. From the left sub-figure, as expected, all lines eventually tend to the same objective function value, well testifying Theorem \ref{L-global-convergence}.  It is clear that the bigger values of $k_0>1$ (i.e., the wider gap between two global aggregations) are, the more iterations are required to reach the optimal function value.  From the  right sub-figure,  the trends show that  all errors vanish gradually along with the iterations rising, and the big values of $k_0$, the more iterations required to converge, which perfectly justifies Theorems \ref{complexity-thorem-gradient} that the convergence rate $O(k_0/k)$ relies on $k_0$.  
 \begin{figure}[!th]
	\centering
	\includegraphics[width=.99\linewidth]{f-err-iter-1-eps-converted-to.pdf}
\caption{Objective function values and errors v.s. iterations. {\tt FedGiA$_{\tt G}$}\ (solid lines) and {\tt FedGiA$_{\tt D}$}\ (dashed lines) solve Example \ref{ex-linear} with $m=64$ and $s=0.5$.\label{fig:iterations-objective}}
\end{figure}


 
 
\subsubsection{Effect of $k_0$}
Next, we would like to see how the choices of $k_0$ impact the performance of {\tt FedGiA}. To proceed with that, for each dimension $(m,d_1,\ldots,d_m)$ of the  dataset, we generate  20 instances of  Example \ref{ex-linear} solved by {\tt FedGiA}\ with fixing $s=0.5$ and $k_0\in[20]$ and report the average results in   Figure \ref{fig:effect-k0-diff}. With the increasing of $k_0$,  CR decreases first and then stabilize at a certain level.  To this end, it is efficient to save communication costs if we set a proper $k_0$. However, it is unnecessary to set a big value of $k_0$ as it results in longer computational time.  In comparison with {\tt FedGiA$_{\tt G}$}, {\tt FedGiA$_{\tt D}$}\ needs more CR for small $k_0$ and fewer CR for large $k_0$ but always rans faster.

\begin{figure}[!th]
\begin{subfigure}{.24\textwidth}
	\centering
	\includegraphics[width=1.02\linewidth]{cr-k0-eps-converted-to.pdf}

	\label{fig:k0-aggr-1}
\end{subfigure}  
\begin{subfigure}{.24\textwidth}
	\centering
	\includegraphics[width=1.02\linewidth]{time-k0-eps-converted-to.pdf}

	\label{fig:k0-time-1}
\end{subfigure} 
 \vspace{-5mm}
\caption{Effect of $k_0$ for {\tt FedGiA$_{\tt G}$}\ (solid lines) and {\tt FedGiA$_{\tt D}$}\ (dashed lines) solving Example \ref{ex-linear} with $s=0.5$.\label{fig:effect-k0-diff}}\vspace{-3mm}
\end{figure} 
 

\subsubsection{Effect of $\mathcal{C}^{\tau_{k+1}}$} Finally, we would like to see how choices of $\mathcal{C}^{\tau_{k+1}}$ impact the performance of {\tt FedGiA}. We alter $s\in(0.1,1]$ and report the average results in Figure \ref{fig:effect-s}. We observe that $s$ would not have a big influence on CR when $k_0>5$. As expected,  the larger $s$ the longer the computational time for most cases.   In general speaking, {\tt FedGiA$_{\tt D}$}\ needs fewer CR when $s$ is small and more CR when $s$ is large but always runs faster than {\tt FedGiA$_{\tt G}$}.

 \begin{figure}[!th]
	\centering
	\begin{subfigure}{.24\textwidth}
	\centering
	\includegraphics[width=1.01\linewidth]{cr-s-eps-converted-to.pdf}

	\label{fig:k0-aggr-1}
\end{subfigure}   
\begin{subfigure}{.24\textwidth}
	\centering
	\includegraphics[width=1.01\linewidth]{time-s-eps-converted-to.pdf}

	\label{fig:k0-time-1}
\end{subfigure}\vspace{-5mm}
\caption{Effect of $s$. {\tt FedGiA$_{\tt G}$}\ (solid lines) and {\tt FedGiA$_{\tt D}$}\ (dashed lines) solve Example \ref{ex-linear} with   $m=64$.\label{fig:effect-s}}
\vspace{-5mm}
\end{figure}
 \subsection{Numerical comparison}
 In this part, we will compare our proposed method with {\tt FedAvg}\ \cite{mcmahan2017communication} and {\tt LocalSGD}\ \cite{stich2018local,Lin2020Don}. For the former, we use its non-stochastic version. Precisely, we select all clients for the training in each round of communication and sue full local dataset to calculate the gradient.  The learning rate is set as $\gamma=\gamma_k(a):=a/{\rm log_2}(k+1)$ with $a=0.01$ for Example \ref{ex-linear} and $a=0.5d/m$ for Example \ref{ex-logist}, where $d= d_1+\ldots+d_m$. For {\tt LocalSGD}, as suggested by  \cite{Lin2020Don} using small mini-batch size to approximate the gradient for every local client,  we choose mini-batch  size $0.05d_i$ for the $i$th  client. Its learning rate is set as $\gamma=\gamma_k(a)$ with $a=0.005$ for Example \ref{ex-linear} and $a=0.1d/m$ for Example \ref{ex-logist}. For {\tt FedGiA}, we fix the size of $\mathcal{C}^{\tau_{k+1}}$ as $0.5m$ (i.e., $s=0.5$). To ensure relatively fair comparisons, we terminate all methods if condition \eqref{stopping} is satisfied or CR  are over $1000$. 
 \begin{figure*}
	\begin{subfigure}{.325\textwidth}
	\centering
	\includegraphics[width=1.01\linewidth]{compare-f-cr-linear-all-eps-converted-to.pdf}

	\label{fig:k0-aggr-1}
\end{subfigure} 
	\begin{subfigure}{.325\textwidth}
	\centering
	\includegraphics[width=1.01\linewidth]{compare-f-cr-log-all-qot-eps-converted-to.pdf}

	\label{fig:k0-aggr-1}
\end{subfigure}   
\begin{subfigure}{.325\textwidth}
	\centering
	\includegraphics[width=1.01\linewidth]{compare-f-cr-log-all-sct-eps-converted-to.pdf}

	\label{fig:k0-time-1}
\end{subfigure}\vspace{-5mm}
\caption{$f(\mathbf{x}^{\tau_{k}}) $  v.s. CR.\label{fig:com-grad-cr}}
\end{figure*} 
\subsubsection{Solving Example \ref{ex-linear}} For simplicity, we fix $m=64$ and $n=100$. From the left sub-figure in Figure \ref{fig:com-grad-cr}, we can see that (i) the objective function values for all methods eventually tend to be the same; (ii) Basically, the larger $k_0$ the faster the decline of the objective function values; (iii) {\tt FedGiA$_{\tt G}$}\ and {\tt FedGiA$_{\tt D}$}\ behave better than {\tt FedAvg}\ which outperforms {\tt LocalSGD}.  We then run 20 independent trials and report the average results in Table \ref{tab:com-linear}. We can conclude that  {\tt FedGIA}\ and  {\tt FedGIA}\ use the fewest CR and run the fastest.

 \begin{table}[!th]
	\renewcommand{1.5}{1.1}\addtolength{\tabcolsep}{-4pt}
	\caption{Comparison for four algorithms.}\vspace{-3mm}
	\label{tab:com-linear}
	\begin{center}
		\begin{tabular}{llccccccccccc }
			\hline
			&&\multicolumn{3}{c}{Ex. \ref{ex-linear}}&&\multicolumn{3}{c}{Ex. \ref{ex-logist} with {\tt qot}}&&\multicolumn{3}{c}{Ex. \ref{ex-logist} with {\tt sct}}\\\cline{3-5}\cline{7-9}\cline{11-13}
Alg.	&	$k_0$	&	Obj.	&	CR	&	Time	&&	Obj.	&	CR	&	Time	&&	Obj.	&	CR	&	Time	\\\hline
{\tt FedAvg}	&	1	&	1.684 	&	1000	&	1.17 	&&	0.260 	&	1000 	&	9.30 	&&	0.327 	&	96.6 	&	4.65 	\\
	&	5	&	1.684 	&	1000	&	3.27 	&&	0.237 	&	572 	&	14.5 	&&	0.327 	&	20.0 	&	2.75 	\\
	&	10	&	1.684 	&	1000	&	5.64 	&&	0.237 	&	289 	&	13.0 	&&	0.327 	&	10.0 	&	2.49 	\\
{\tt LocalSGD}	&	1	&	1.686 	&	1000	&	2.95 	&&	0.325 	&	1000 	&	13.2 	&&	0.333 	&	1000 	&	58.9 	\\
	&	5	&	1.685 	&	1000	&	11.0 	&&	0.302 	&	1000 	&	44.1 	&&	0.331 	&	1000 	&	196 	\\
	&	10	&	1.684 	&	1000	&	19.5 	&&	0.299 	&	1000 	&	81.5 	&&	0.330 	&	1000 	&	369 	\\
{\tt FedGiA$_{\tt G}$}	&	1	&	1.684 	&	13.6	&	0.16 	&&	0.236 	&	19.8 	&	0.60 	&&	0.326 	&	5.00 	&	0.59 	\\
	&	5	&	1.684 	&	7.40 	&	0.20 	&&	0.236 	&	19.9 	&	1.35 	&&	0.325 	&	5.00 	&	0.97 	\\
	&	10	&	1.684 	&	6.10 	&	0.25 	&&	0.236 	&	19.9 	&	2.10 	&&	0.325 	&	5.00 	&	1.45 	\\
{\tt FedGiA$_{\tt D}$}	&	1	&	1.684 	&	18.4	&	0.13 	&&	0.236 	&	19.9 	&	0.44 	&&	0.326 	&	5.00 	&	0.49 	\\
	&	5	&	1.684 	&	10.1	&	0.11 	&&	0.236 	&	19.9 	&	0.63 	&&	0.325 	&	4.90 	&	0.76 	\\
	&	10	&	1.684 	&	7.00 	&	0.11 	&&	0.236 	&	19.9 	&	0.87 	&&	0.325 	&	4.90 	&	1.05 	\\\hline
		\end{tabular}
	\end{center}
\end{table}

\subsubsection{Solving Example \ref{ex-logist}} Again, we fix $m=64$ for simplicity. From the two right sub-figures in Figure \ref{fig:com-grad-cr}, we can observe   the objective function values obtained by {\tt FedGiA}\ decline the fastest. In addition, {\tt FedGiA}\ uses the fewest CR to reach the optimal solutions, followed by {\tt FedAvg}, and {\tt LocalSGD}\ needs the most.  
We then run 20 independent trials and report the average results in Table \ref{tab:com-linear}, where {\tt FedGIA}\ outperforms the other two algorithms by consuming the fewest CR and running the fastest.


\section{Conclusion}
This paper developed a new FL algorithm and managed to address three key issues in FL, including saving communication resources, reducing computational complexity, and establishing convergence property under mild assumptions. These advantages hint that the proposed algorithm might be practical to deal with many real applications such as mobile edge computing \cite{mao2017survey,mach2017mobile}, over-the-air computation \cite{zhu2018mimo,yang2020federated}, vehicular
communications \cite{samarakoon2019distributed}, unmanned aerial vehicle online path control \cite{shiri2020communication} and so forth.  Moreover, we feel that the algorithmic schemes and techniques used to build the convergence theory could be also valid for tackling decentralized FL  \cite{elgabli2020fgadmm,ye2021decentralized}. We leave these for future research.




\bibliographystyle{IEEEtran}
