FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data

Introduction

Federated learning (FL)—a distributed machine learning approach proposed in —has gained popularity for applications involving learning from distributed data. In FL, a cloud server (the “server”) can communicate with distributed data sources (the “agents”). The goal is to train a global model that works well for all the distributed data, but without requiring the agents to reveal too much local information. Since its inception, the broad consensus on FL’s implementation appears to involve a generic “computation then aggregation” (CTA) protocol. This involves the following steps: S1) the server sends the model $\mathbf{x}$ to the agents; S2) the agents update their local models $\mathbf{x}_{i}$’s for several iterations based on their local data; S3) the server aggregates $\mathbf{x}_{i}$’s to obtain a new global model $\mathbf{x}$. It is widely acknowledged that multiple local steps save communication efforts, while only transmitting local models protects data privacy .

Even though the FL paradigm has attracted significant research from both academia and industry, and many algorithms such as Federated Averaging (FedAvg) have been proposed, several attributes are not clearly established. In particular, the commonly adopted CTA protocol poses significant theoretical and practical challenges to designing effective FL algorithms. This work attempts to provide a deeper understanding of FL, by raising and resolving a few theoretical questions, as well as by developing an effective algorithmic framework with several desirable features.

Problem Formulation. Consider the vanilla FL solving the following problem:

where $\mathcal{P}_{i}$ denotes the data distribution on the $i$-th agent. Throughout the paper, we will make the following blanket assumptions for problem (1):

Each $f_{i}(\cdot)$, as well as $f$ in (1) is $L$–smooth:

In addition to these standard assumptions, state-of-the-art efforts on analysis of FL algorithms oftentimes invoke a number of more restrictive assumptions.

(Bounded Gradient (BG)) The gradients $\nabla f_{i}$’s are upper bounded (by a constant $G>0$)

(I.I.D. Data) Either one of the following holds:

First, the BG assumption typically does not hold for (1), in particular, $f_{i}(\mathbf{x})=\|\mathbf{A}_{i}\mathbf{x}-\mathbf{b}_{i}\|^{2}$ (where $\mathbf{A}_{i}$ and $\mathbf{b}_{i}$ are related to data). However, the BG assumption is critical for analyzing FedAvg-type algorithms because it bounds the distance traveled after multiple local iterates. Second, (4) is typically used in FL to characterize homogeneity about local data . However, an assumption of this type does not hold for FL applications where the data (such as medical records, keyboard input data) are generated by the individual agents . A reasonable relaxation to this i.i.d. assumption is the following notion of $\delta$-non-i.i.d.-ness of the data distribution.

($\delta$-Non-I.I.D. Data) The local functions are called $\delta$-non-i.i.d. if either one of the equivalent conditions below holds:

By varying $\delta$ from to $\infty$, (6) provides a characterization of data non-i.i.d.-ness. In Appendix A, we give a few examples of loss functions with different values of $\delta$. Note that the second inequality in (6) is often used in decentralized optimization to quantify the similarity of local problems . Third, (5) does not hold for many practical problems. To see this, note that this condition is parameterized by $\epsilon$, which is typically the desired optimization accuracy . Since $\epsilon$ can be chosen arbitrarily small, (5) essentially requires that the problem is realizable, that is, $\|\nabla f(\mathbf{x})\|$ approaches zero only when all the local gradients approach zero at $\mathbf{x}$, that is, when the local data are “similar”.

Finally, we mention that our objective is to understand FL algorithm from an optimization perspective. So we say that a solution $\mathbf{x}$ is an $\epsilon$-stationary solution if the following holds:

We are interested in finding the minimum system resources required, such as the number of local updates, the number of times local variables are transmitted to the server, and the number of times local samples $F(\mathbf{x};\xi_{i})$’s are accessed, before computing an $\epsilon$-solution (7). These quantities are referred to as local computation, communication complexity, and sample complexities, respectively.

Questions to address Despite extensive recent research, the FL framework, and in particular, the CTA protocol is not yet well understood. Below, we list four questions regarding the CTA protocol.

Q1 (local updates). What are the best local update directions for the agents to take so as to achieve the best overall system performance (stability, sample complexity, etc.)?

Q2 (global aggregation). Can we use more sophisticated processing in the aggregation step to help improve the system performance (sample or communication complexity)?

Q3 (communication efficiency). If multiple local updates are preformed between two aggregation steps, will it reduce the communication overhead?

Q4 (assumptions). What is the best performance that the CTA type algorithms can achieve while relying on a minimum set of assumptions about the problem?

Although these questions are not directly related to data privacy, another important aspect of FL, we argue that answering these fundamental questions can provide much needed understanding on algorithms following the CTA, and thus the FL approach. A few recent works (to be reviewed shortly) have touched upon those questions, but to our knowledge, none of them has conducted a thorough investigation of the questions listed above.

Related Works. We start with a popular method following the CTA protocol, the FedAvg in Algorithm 1, which covers the original FedAvg , the Local SGD , PR-SGD and the RI-SGD among others.

In FedAvg, $T$ is the total stage number, $Q$ the number of local updates, $r$ the index of the stage, $q$ the index of the inner iteration, and $\eta^{r,q}$’s are the stepsizes. It has two options for local updates:

Many recent works are extensions of FedAvg. The algorithm proposed in adds momentum to the algorithm. In , the data on the local agents are separated into blocks and shared with other agents. In the local GD version (9) is studied. In , a cooperative-SGD is considered; it includes virtual agents, extra variables, and relaxes the parameter server topology.

It is pertinent to consider how these algorithms address questions Q1–Q4. For Q1, most FedAvg-type algorithms perform multiple local (stochastic) GD steps to minimize the local loss function. However, we will see shortly that in many cases, successive local GD steps lead to algorithm divergence. For Q2, most algorithms use simple averaging, and there is little discussion on whether other types of (linear) processing will be helpful. For Q3, a number of recent works such as show that, for non-convex problems, to achieve $\epsilon$-solution (7), a total of $O(1/\epsilon^{3/2})$ aggregation steps are needed. However, it is not clear if this achieves the best communication complexity. As for Q4, the FedAvg-type algorithm typically requires either some variant of the BG assumption, or some i.i.d. assumption, or both; See Table 1 rows 1–5 for detailed discussions.

A number of more recent works have improved upon FedAvg in various aspects. FedProx addresses Q1 and Q4 by perturbing the update direction. This algorithm does not need the BG, but it still requires the i.i.d. assumption (5). The VRL-SGD proposed in addresses Q1 and Q4 by using the variance reduction (VR) technique to update the directions for local agents and achieves $\mathcal{O}(1/\epsilon)$ communication complexity without the i.i.d. assumption. F-SVRG is another recent algorithm that uses VR. This algorithm does not follow the CTA protocol as the agents have to transmit the local gradients, but it does not require A3 and A4. The PR-SPIDER further improves upon FSVRG by reducing sample complexity (SC) from $\mathcal{O}(M/\epsilon)$ to $\mathcal{O}(\sqrt{M}/\epsilon)$ (where $M$ is typically larger than $1/\epsilon$). Although FSVRG and PR-SPIDER neither require the BG or the i.i.d. assumptions, they require the agents to transmit local gradients to the server and thus do not follow the CTA protocol. This is undesirable, as it has been shown that local gradient information can leak private data . Additionally, questions Q2-Q3 are not addressed in these works.

Our Main Contributions. First, we address Q1-Q4 and provide an in-depth examination of the CTA protocol. We show that algorithms following the CTA protocol that are based on successive local gradient updates, the best possible communication efficiency is $\mathcal{O}(1/\epsilon)$; neither additional local processing nor general linear processing can improve this rate. We then show that the BG and/or i.i.d. data assumption is important for the popular FedAvg to work as intended.

Our investigation suggests that the existing FedAvg-based algorithms are (provably) insufficient in dealing with many practical problems, calling for a new design strategy. We then propose a meta-algorithm called Federated Primal-Dual (FedPD), which also follows the CTA protocol and can be implemented in several different forms with desirable properties. In particular, it i) can deal with the general non-convex problem, ii) achieve the best possible optimization and communication complexity when data is non-i.i.d., iii) achieve convergence under only Assumptions A1– A2.

Most importantly, the communication pattern of the proposed algorithm can be adapted to the degree of non-i.i.d.-ness of the local data. That is, we show that under the $\delta$-non-i.i.d. condition (6), communication saving and data heterogeneity interestingly exhibit a linear-logarithmic relationship; see Fig. 1 for an illustration. To our knowledge, this is the first algorithm for FL that achieves all the above properties.

Addressing Open Questions

We focus on the case where the $V^{t}(\cdot)$’s and $W^{t}_{i}(\cdot)$’s are linear operators, which implies that $x^{t,q}_{i}$ can use all past iterates and (sample) gradients for its update. Clearly, (10) covers both the local-GD and local-SGD versions of FedAvg as special cases. In the following, we provide an informal statement of the result. The formal statement and the full proof are given in Appendix B and Theorem 2.

(Informal) Consider any algorithm $A$ that belongs to the class described in (10), with $V^{t}(\cdot)$ and $W^{t}_{i}(\cdot)$’s being linear and possibly time-varying operators. Then, there exists a non-convex problem instance satisfying Assumptions 1–2 such that for any $Q>0$, algorithm $A$ takes at least $\mathcal{O}(1/\epsilon)$ communication rounds to reach an $\epsilon$-stationary solution satisfying (7).

Remark 1. The proof technique is related to those developed from both classical and recent works that characterize lower bounds for first-order methods, in both centralized and decentralized settings. The main technical difference is that our processing model (10) additionally allows local processing iterations, and there is a central aggregator. Our goal is not to establish lower bounds on the number of (centralized) gradient access, nor to show the optimal graph dependency, but to characterize (potential) communication savings when allowing multiple steps of local processing.

In the proof, we construct difficult problem instances in which $f_{i}$’s are not i.i.d. (more precisely, $\delta$ in assumption (4) grows with the total number of iterations $T$). Then we show that it is necessary to aggregate (thus communicate) to make any progress. On the other hand, it is obvious that in another extreme case where the data are -non-i.i.d., only $\mathcal{O}(1)$ communication rounds are needed. An open question is: when the local data are related to each other, i.e., $\delta$ lies between and infinity, is it possible to reduce the total communication rounds? This question is addressed below in Sec. 3. $\blacksquare$

We now address Q1 and Q4. We consider the FedAvg Algorithm 1, and show that BN and/or i.i.d. assumptions are critical for them to perform well. Our result suggests that, despite its popularity, components in FedAvg, such as the pure local (stochastic) gradient directions and linear aggregation are not compatible with each other. The proof of the results below are given in Appendix C.

Fix any constant $\eta>0$, $Q>1$ for Algorithm 1. There exists a problem that satisfies A1 and A2 but fails to satisfy A3 and A4, on which FedAvg diverges to infinity.

Remark 2. A recent work has shown that FedAvg with constant stepsize $\eta>0$ can only converge to a neighborhood of the global minimizer for convex problems. Moreover, the error to the global optima is related to $Q$ and the degree of non-i.i.d.-ness as measured by the size of $\sum^{N}_{i=1}\left\lVert\nabla f_{i}(\mathbf{x}^{\star})\right\rVert^{2}$ where $\mathbf{x}^{\star}$ is the global optimal solution. On the other hand, our result indicates that when $f_{i}$’s are non-convex, FedAvg can perform much worse without the BN and the i.i.d. assumption. Even if $Q=2$ and there exists a solution such that $\sum_{i=1}^{N}\|f_{i}(\hat{\mathbf{x}})\|^{2}=0$, FedAvg (with constant stepsize $\eta$) diverges and the iteration can go to $\infty$. $\blacksquare$

One may think that using a constant stepsize is the culprit for the divergence in Claim 2.2. In fact, we can show that having BG or not can still impact the performance of FedAvg, even when diminishing stepsize is used. In particular, we show in Appendix D, that FedAvg converges under the BG assumption for any diminishing stepsize, but without it, the choice of the stepsize can be significantly restricted.

The FedPD Framework

The previous section reveals a number of properties about FedAvg and, broadly speaking, the CTA protocol. But why does FedAvg only work under very restrictive conditions? Is it because the local update directions are not chosen correctly? Is it possible to make it work without any additional assumptions? Can we reduce communication effort when the local data becomes more i.i.d.?

In this section, we propose a meta-algorithm called Federated Primal-Dual (FedPD), which can be specialized into different sub-variants to address the above questions. These algorithms possess a few desirable features: They can achieve the best optimization and communication complexity when data is non-i.i.d. (i.e., achieving the bounds in Claim 2.1); they only require A1 –A2, while being able to utilize both full or sampled local gradients. Most importantly, the communication pattern of the proposed algorithm can be made adaptive to the degree of data non-i.i.d.-ness across the agents.

Our algorithm is based on the following global consensus reformulation of the original problem (1):

Similar to traditional primal-dual based algorithms , the idea is that, when relaxing the equality constraints, the resulting problem is separable across different nodes. However, different from ADMM, the agents can now perform either a single (or multiple) local update(s) between two communication rounds. Importantly, such flexibility makes it possible to adapt the communication frequency to the degree of $\delta$-non-i.i.d.-ness of the local data. In particular, we identify that under $\delta$-non-i.i.d. (4), the fraction $\epsilon/\delta^{2}$ is the key quantity that determines communication saving; see Fig. 1. Intuitively, significant reduction can be achieved when $\delta$ is smaller than $\epsilon$; otherwise, the reduction goes to zero linearly as $\delta$ increases. To our knowledge, none of the existing ADMM based algorithms, nor FL based algorithms, are able to provably achieve such a reduction.

To present our algorithm, let us define the augmented Lagrangian (AL) function of (11) as

Fixing $\mathbf{x}_{0}$, the AL is separable over all local pairs $\{(\mathbf{x}_{i},\lambda_{i})\}$. The key technique in the design is to specify how each local AL $\mathcal{L}_{i}(\cdot)$ should be optimized, and when to perform model aggregation.

Federated primal-dual algorithm (FedPD) captures the main idea of the classical primal-dual based algorithm while meeting the flexibility need of FL; see Algorithm 2. In particular, its update rules share a similar pattern as ADMM, but it does not specify how the local models are updated. Instead, an oracle $\mbox{\rm Oracle}_{i}(\cdot)$ is used as a placeholder for local processing, and we will see that careful instantiations of these oracles lead to algorithms with different properties. Importantly, we introduce a critical constant $p\in[0,1)$, which determines the frequency at which the aggregation and communication steps are skipped. In Algorithm 3 and Algorithm 4, we provide two useful examples of the local oracles.

In Algorithm 3, $Q_{i}$’s are chosen so that the local problems are solved accurately enough to satisfy:

We provide two ways for solving this subproblem by using GD and SGD, but any other solver that achieves (12) can be used. For the SGD version, the stochastic gradient is defined as

where $\sim$ denotes uniform sampling. Despite the simplicity of the local updates, we will show that using Oracle I makes FedPD adaptive to the non-i.i.d. parameter $\delta$.

In Algorithm 4, the oracle applies the variance reduction technique to reduce the sample complexity. The detailed descriptions and the analyses are given in Appendix G due to the space limitation.

2 Convergence and Complexity Analysis

We analyze the convergence of FedPD with Oracle I. The detailed proofs are given in Appendix F. The convergence analysis of FedPD with an alternative Oracle is given in Appendix G

Suppose A1 –A2 hold. Consider FedPD with Oracle I, where $Q_{i}$ are selected by (12).

Case I) Suppose A5 holds with $\delta=\infty$. Set $0<\eta<\frac{\sqrt{5}-1}{4L}$, $p=0$. Then we have:

Case II) Suppose $0<\eta<\frac{\sqrt{5}-1}{4L}$, $0\leq p<1$, and A5 holds with a finite $\delta$. Then we have:

Here $C_{2},C_{4},C_{5}>0$ are constants independent of $T,\delta,p$; C_{3}:={\color[rgb]{0,0,0}\frac{{p(1+L\eta)+L\eta}}{1-L\eta}}\geq 0.

Remark 3. (Communication complexity) Case I says if one does not skip communication ($p=0$), then to achieve $\epsilon$-stationarity (i.e., $\left\lVert\nabla f(\mathbf{x}^{t}_{0})\right\rVert^{2}\leq\epsilon$ for some $r\in(1,T)$), they need to set $T=1/(2C_{2}D_{0}\epsilon)$, $\epsilon_{1}=\epsilon/(2C_{4})$, and the total communication rounds is $T$.

In Case II, the second term on the right hand side of (14) involves both $\delta$ and $p$, so we can select them appropriately to reduce communication while maintaining the same accuracy. Specifically, we choose $\epsilon_{1}=\min\{\epsilon/(4C_{4}),\delta^{2}\}$ and $T=1/(2C_{2}D_{0}\epsilon)$. Then we have

Then we can achieve the same $\epsilon$-accuracy as Case I. The communication rounds here is $T(1-p)$.

The relation between the saving $p$ and $\frac{\epsilon}{\delta^{2}}$ is showed in Table 2. Roughly speaking, $p$ is inversely proportional to degree of non-i.i.d-ness $\delta^{2}$ when $\delta^{2}\in(\mathcal{O}(\epsilon),\infty)$; further, $p\rightarrow 1$ at a log-rate when $\delta^{2}\rightarrow 0$. Our result also indicates that, when using stage-wise training for neural networks, the algorithm can communicate less at the early stages since they typically have lower accuracy target to enable larger stepsizes .

Remark 4. (Computation complexity) To achieve $\epsilon$ accuracy, we need both $T=\mathcal{O}(1/\epsilon)$ and $\epsilon_{1}=\mathcal{O}(\epsilon)$. As the local AL is strongly convex with respect to $\mathbf{x}_{i}$, optimizing it to $\epsilon$ accuracy requires $\mathcal{O}(\log(\epsilon))$ iterations for GD and $\mathcal{O}(1/\epsilon)$ for SGD . So the total number of times that the local gradients (respectively, stochastic gradients) are accessed is given by $\mathcal{\mathcal{O}(\text{1}/\epsilon\times\log(\text{1}/\epsilon))}$ (respectively, $\mathcal{O}(1/\epsilon^{2})$).

We conclude this section by noting that the above communication and computation complexity results we have obtained are the best so far among all FL algorithms for non-convex problems satisfying A1 – A2. Please see the last three rows of Table 1 for a summary of the results.

3 Connection with Other Algorithms

Before we close this section, we discuss the relation of FedPD with a few existing algorithms.

The FedProx/FedDANE In FedProx the agents optimize the following local objective: $f_{i}(\mathbf{x}_{i})+\frac{\rho}{2}\left\lVert\mathbf{x}_{i}-\mathbf{x}^{r}_{0}\right\rVert^{2}$. This fails to converge to the global stationary solution. In contrast, FedPD introduces extra local dual variables $\{\lambda_{i}\}$ that record the gap between the local model $\mathbf{x}_{i}$ and the global model $\mathbf{x}_{0}$ which help the global convergence. FedDANE also proposes a way of designing the subproblem by using the global gradient, but this violates the CTA protocol. Compared with these two algorithms, the proposed FedPD has weaker assumptions, and it achieves better sample and/or communication complexity.

Event Triggering Algorithms. A number of recent works such as Lazily Aggregated Gradient (LAG) and COLA have been proposed to occasionally skip message exchanges among the agents to save communication. In LAG, each agent receives the global model every iteration, and decides whether to send some local gradient differences by checking certain conditions. Since gradient information is transmitted, LAG does not belong to the algorithm class (10). When the local problems are unbalanced, in the sense that the discrepancy between the local Lipschitz gradients $L_{i}$’s is large, then the agents with smaller $L_{i}$’s can benefit from the lazy aggregation. Meanwhile, instead of measuring whether the local problems are balanced, the $\delta$-non-i.i.d. criteria characterizes if local problems are similar by measuring the uniform difference between arbitrary pairs of the local problems. If the data is i.i.d., then the agents benefit equally from the communication reduction.

Numerical Experiments

In the first experiment, we show the convergence of the proposed algorithms on synthetic data with FedAvg and FedProx as baselines. We use the non-convex penalized logistic regression as the loss function. We use two ways to generate the dataset, in the first case (referred to as the “weakly non-i.i.d” case), the data is generated in an i.i.d. way. In the second case (referred to as the “strongly non-i.i.d” case), we generate the data using non-i.i.d. distribution. In both cases there are $400$ samples on each agent with total $100$ agents.

We run FedPD with Oracle I (FedPD-SGD and FedPD-GD) and Oracle II (FedPD-VR). For FedPD-SGD, we set $Q=600$, and for FedPD-GD and FedPD-VR we set $Q=8$. For FedPD-GD we set $p=0$ and $p=0.5$, wherein the later case the agents skips half of the communication rounds. For FedPD-VR, we set mini-batch size $B=1$ and gradient computation frequency $I=20$. For comparison, we also run FedAvg with local GD/SGD and FedProx. For FedAvg with GD, $Q=8$, and for FedAvg with SGD, $Q=600$. For FedProx, we solve the local problem using variance reduction for $Q=8$ iterations. The total number of iterations $T$ is set as $600$ for all algorithms.

Fig. 2 shows the results with respect to the number of communication rounds. In Fig. 2(a), we compare the convergence of the tested algorithms on weakly non-i.i.d. data set. It is clear that FedProx and FedPD with $p=0$ (i.e., no communication skipping) are comparable. Meanwhile, FedAvg with local GD will not converge to the stationary point with a constant stepsize when local update step $Q>1$. By skipping half of the communication, FedPD with local GD can still achieve a similar error as FedAvg, but using fewer communication rounds. In Fig. 2(b), we compare the convergence results of different algorithms with the strongly non-i.i.d. data set. We can see that the algorithms using stochastic solvers become less stable compared with the case when the data sets are weakly non-i.i.d. Further, FedPD-VR and FedPD-GD with $p=0$ are able still to converge to the global stationary point while FedProx will achieve a similar error as the FedAvg with local GD.

We included more details on the experimental results and additional experiments in Appendix H.

Conclusion

We study federated learning under the CTA protocol. We explore a number of theoretical properties of this protocol, and design a meta-algorithm called FedPD, which contains various algorithms with desirable properties, such achieving the best communication/computation complexity, as being able to adapt its communication pattern with data heterogeneity.

References

Appendix A Examples of Cost Functions Satisfy A5

In this part, we provide a commonly used function that satisfies A5.

Define the scalar $\frac{\exp(b_{k}-\mathbf{a}^{T}_{k}\mathbf{x})}{(1+\exp(b_{k}-\mathbf{a}^{T}_{k}\mathbf{x}))^{2}}$ as $v(\mathbf{a}_{k},b_{k},\mathbf{x})$, we have $v(\mathbf{a}_{k},b_{k},\mathbf{x})\in(0,1),\;\forall x,\mathbf{a}_{k},b_{k}$. Further stack $v(\mathbf{a}_{k},b_{k},\mathbf{x})$ as $\mathbf{v}(\mathcal{D}_{i},\mathbf{x})$, that is $\mathbf{v}(\mathcal{D}_{i},\mathbf{x})=[v(\mathbf{a}_{1},b_{1},\mathbf{x});\dots,;v(\mathbf{a}_{|\mathcal{D}_{i}|},b_{|\mathcal{D}_{i}|},\mathbf{x})]$. Further we define $A_{i}$ as the stacked matrix of all $\mathbf{a}_{k}\in\mathcal{D}_{i}$ (i.e., $A_{i}=[\mathbf{a}_{1},\dots,\mathbf{a}_{|\mathcal{D}_{i}|}]$), then we can express $\nabla f_{i}(\mathbf{x})$ as

The difference between the gradients of $f_{i}$ and $f_{j}$ is

As $v(\mathbf{a},b,\mathbf{x})\in(0,1)$, we know $\left\lVert\mathbf{v}(\mathcal{D}_{i},\mathbf{x})\right\rVert\leq\left\lVert[1,\dots,1]\right\rVert=\sqrt{|\mathcal{D}_{i}|}$, which implies:

Utilizing the above inequality in (18), we obtain:

So we can define $\delta=\max_{i,j}\left\{\frac{1}{\sqrt{|\mathcal{D}_{i}|}}\left\lVert A_{i}\right\rVert+\frac{1}{\sqrt{|\mathcal{D}_{j}|}}\left\lVert A_{j}\right\rVert\right\}$ which is a finite constant. Note that the above analysis holds true for any $D_{i}$ and $\mathbf{x}$. Note that with finer analysis we can obtain better bounds for $\delta$.

Similar to logistic regression, we can also show that A5 holds for hyperbolic tangent function which is commonly used in neural network models. First, notice that the hyperbolic tangent is a rescaled version of logistic regression:

So, $\delta$ for $\tanh$ is $4$ times that applicable to the logistic regression problem. Note that this analysis can further cover a wide range of neural network training problems that uses cross entropy loss and sigmoidal activation functions (e.g. MLP, CNN and RNN).

Then if the feature $A_{i}$’s satisfy $A_{i}^{T}A_{i}=A_{j}^{T}A_{j},\forall~{}i\neq j,$ we have

Appendix B Proof of Claim 2.1

The proof is related to techniques developed in classical and recent works that characterize lower bounds for first-order methods in centralized and decentralized settings. Technically, our computational / communication model is different compared to the aforementioned works, since we allow arbitrary number of local processing iterations, and we have a central aggregator. The difference here is that our goal is not to show the lower bounds on the number of total (centralized) gradient access, nor to show the optimal graph dependency. The main point we would like to make is that there exist constructions of local functions $f_{i}$’s such that no matter how many times that local first-order processing is performed, without communication and aggregation, no significant progress can be made in reducing the stationarity gap of the original problem.

For notational simplicity, we will assume that the full local gradients $\{\nabla f_{i}(x^{k}_{i})\}$ can be evaluated. Later we will comment on how to extend this result to enable access to the sample gradients $\nabla F(x^{k}_{i};\xi_{i})$. In particular, we consider the following slightly simplified model for now:

In this section, we will call each $t$ a “stage,” and call each local iteration $q$ an “iteration.” We use $x$ to denote the variable located at the server. We use $x_{i}$ (and sometimes $x_{q}$) to denote the local variable at node $i$, and use $x_{i}[j]$ and $x_{i}[k]$ to denote its $j$th and $k$th elements, respectively. We use $g_{i}(\cdot)$ and $f_{i}(\cdot)$ to denote some functions related to node $i$, and $g(\cdot)$ and $f(\cdot)$ to denote the average functions of $g_{i}$’s and $f_{i}$’s, respectively. We use $N$ to denote the total number of nodes.

B.2 Main Constructions.

Suppose there are $N$ distributed nodes in the system, and they can all communicate with the server. To begin, we construct the following two non-convex functions

where we have defined the following functions

Clearly, each $\Theta(x,j)$ is only related to two components in $x$, i.e., $x[j-1]$ and $x[j]$.

By the above definition, the average function becomes:

See Fig. 3 for an illustration of the construction discussed above.

Further, for a given error constant $\epsilon>0$ and a given the Lipschitz constant $L$, let us define

B.3 Properties.

First we present some properties of the component functions $h_{i}$’s.

The functions $\Psi$ and $\Phi$ satisfy the following:

For all $w\leq 0$, $\Psi(w)=0$, $\Psi^{\prime}(w)=0$.

The following bounds hold for the functions and their first- and second-order derivatives:

The function $h$ is lower bounded as follows:

To prove Property 2), note that following holds for $w>0$:

Obviously, $\Psi(w)$ is an increasing function over $w>0$, therefore the lower and upper bounds are $\Psi(0)=0,\Psi(\infty)=1$; $\Psi^{\prime}(w)$ is increasing on $[0,\frac{1}{\sqrt{2}}]$ and decreasing on $[\frac{1}{\sqrt{2}},\infty]$, where $\Psi^{\prime\prime}(\frac{1}{\sqrt{2}})=0$, therefore the lower and upper bounds are $\Psi^{\prime}(0)=\Psi^{\prime}(\infty)=0,\Psi^{\prime}(\frac{1}{\sqrt{2}})=\sqrt{\frac{2}{e}}$; $\Psi^{\prime\prime}(w)$ is decreasing on $(0,\sqrt{\frac{3}{2}}]$ and increasing on $[\sqrt{\frac{3}{2}},\infty)$ (this can be verified by checking the signs of $\Psi^{\prime\prime\prime}(w)=4e^{-w^{2}}w(2w^{2}-3)$ in these intervals). Therefore the lower and upper bounds are $\Psi^{\prime\prime}(\sqrt{\frac{3}{2}})=-\frac{4}{e^{\frac{3}{2}}},\Psi^{\prime\prime}(0^{+})=2$, i.e.,

Similarly, as above, we can obtain the following bounds:

To show Property 3), note that for all $w\geq 1$ and $|v|<1$,

where the first inequality is true because $\Psi(w)$ is strictly increasing and $\Phi^{\prime}(v)$ is strictly decreasing for all $w>0$ and $v>0$, and that $\Phi^{\prime}(v)=\Phi^{\prime}(|v|)$.

Next we show Property 4). Note that $0\leq\Psi(w)<1$ and $0<\Phi(w)<4\pi$. Therefore we have ${g}(0)=-\Psi(1)\Phi(0)<0$ and using the construction in (22)

where the first inequality follows from $\Psi(w)\Phi(v)>0$, the second follows from $\Psi(w)\Phi(v)<4\pi$, and the last is true because $T/N\geq 1$.

Finally, we show Property 5), using the fact that a function is Lipschitz if it is piecewise smooth with bounded derivative. Before proceeding, let us note a few properties of the construction in (24) (also see Fig. 3). First, for a given node $q$, its local function $h_{q}$ is only related to the following $x[j]$’s

Then the first-order partial derivative of $g_{q}(y)$ can be expressed below.

From the above derivation, it is clear that for any $j,q$, $\frac{\partial g_{q}}{\partial x[j]}$ is either zero or is a piecewise smooth function separated at the non-differentiable point $x[j]=0$, because the function $\Psi^{\prime}(\cdot)$ is not differentiable at .

By using (32) and the above facts, the second-order partial derivative of $g_{q}(x)$ ($\forall x\neq 0$) is given as follows when $j\neq 1$:

By applying Lemma 1 – i) [i.e., $\Psi(w)=\Psi^{\prime}(w)=\Psi^{\prime\prime}(w)=0$ for $\forall\;w\leq 0$], we can obtain that at least one of the terms $\Psi\left(-x[j-1]\right)\Phi^{\prime\prime}\left(-x[j]\right)$ or $-\Psi\left(x[j-1]\right)\Phi^{\prime\prime}\left(x[j]\right)$ is zero. It follows that

Taking the maximum over equations (34) to (40) and plug in the above inequalities, we obtain

where the equality comes from Lemma 1 – ii).

When $j=1$, by using (33), we have the following:

Summarizing the above results, we obtain:

The following lemma is a simple extension of the previous result.

We have the following properties for the functions $f$ defined in (26) and (25):

The first-order derivatives of ${f}$ and that for each $f_{i},i\in[N]$ are Lipschitz continuous, with the same constant $U>0$.

Proof. To show that property 1) is true, note that we have the following:

Then by applying Lemma 1 we have that for any $T\geq 1$, the following holds

Property 2) is true is due to the definition of $f_{i}$, so that we have:

Property 3) is true because the following:

where the last inequality comes from Lemma 1 – (5). This completes the proof. $\blacksquare$

Next let us analyze the size of $\nabla{g}$. We have the following result.

If there exists $k\in[T]$ such that $|x[k]|<1$, then

Proof. The first inequality holds for all $k\in[T]$, since $\frac{1}{N}\sum_{i=1}^{N}\frac{\partial}{\partial y[k]}g_{i}(x)$ is one element of $\frac{1}{N}\sum_{i=1}^{N}\nabla g_{i}(x)$. We divide the proof for the second inequality into two cases.

Case 1. Suppose $|x[j-1]|<1$ for all $2\leq j\leq k$. Therefore, we have $|x|<1$. Using (33), we have the following inequalities:

where ${\rm(i)}$ is true because $\Psi^{\prime}(w),\Phi(w)$ are all non-negative from Lemma 1 -(2); ${\rm(ii)}$ is true due to Lemma 1 – (3). Therefore, we have the following

Case 2) Suppose there exists $2\leq j\leq k$ such that $|x[j-1]|\geq 1$.

We choose $j$ so that $|x[j-1]|\geq 1$ and $|x[j]|<1$. Therefore, depending on the choices of $(i,j)$ we have three cases:

First, note that $\frac{\partial g_{i}(x)}{\partial x[j]}\leq 0$, for all $i,j$, by checking the definitions of $\Psi(\cdot),\Phi^{\prime}(\cdot),\Psi^{\prime}(\cdot),\Phi(\cdot)$.

Then for $(i,j)$ satisfying the first condition, because $|x[j-1]|\geq 1$ and $|x[j]|<1$, using Lemma 1 – (3), and the fact that the negative part is zero for $\Psi$, and $\Phi^{\prime}$ is even function, the expression further simplifies to:

If the second condition holds true, the expression is obviously non-positive because both $\Psi^{\prime}$ and $\Phi$ are non-negative. Overall, we have

Consider using an algorithm of the form (20) to solve the following problem:

Assume the initial solution: $x_{i}=0,\;\forall~{}i\in[N]$. Let $\bar{x}=\frac{1}{N}\sum_{i=1}^{N}\alpha_{i}x_{i}$ denote some linear combination of local variables, where $\{\alpha_{i}>0\}$ are the coefficients (possibly time-varying and dependent on $t$). Then no matter how many local computation steps (20b) are performed, at least $T$ communication steps (20a) are needed to ensure $\bar{x}[T]\neq 0$.

Proof. For a given $j\geq 2$, suppose that $x_{i}[j],x_{i}[j+1],...,x_{i}[T]=0$, $\forall i$, that is, $\mbox{support}\{x_{i}\}\subseteq\{1,2,3,...,j-1\}$ for all $i$. Then $\Psi^{\prime}\left(x_{i}[j]\right)=\Psi^{\prime}\left(-x_{i}[j]\right)=0$ for all $i$, and $g_{i}$ has the following partial derivative (see (32))

Clearly, if $x_{i}[j-1]=0$, then by the definition of $\Psi(\cdot)$, the above partial gradient is also zero. In other words, the above partial gradient is only non-zero if $x_{i}[j-1]\neq 0$.

Recall that we have assumed that the server aggregation is performed using a linear combination $\bar{x}=\frac{1}{N}\sum_{i=1}^{N}\alpha_{i}x_{i}$, with the coefficients $\alpha_{i}$’s possibly depending on the stage $t$ (but such a dependency will be irrelevant for our purpose, as will be see shortly). Therefore, at a given stage $t$, for a given node $i$, when $j\geq 3$, its $j$th element will become nonzero only if one of the following two cases hold true:

If before the aggregation step (i.e., at stage $t-1$), some other node $q$ has $x_{q}[j]$ being nonzero.

If $\frac{\partial g_{i}(x_{i})}{\partial x_{i}[j]}$ is nonzero at stage $t$.

Now suppose that the initial solution is $x_{i}[j]=0$ for all $(i,j)$. Then at the first iteration only $\frac{\partial g_{i}(x_{i})}{\partial x_{i}}$ is non-zero for all $i$, due to the fact that $\frac{\partial g_{i}(x_{i})}{\partial x_{i}}=\Psi(1)\Phi^{\prime}(0)=4(1-e^{-1})$ for all $i$ from (33). It is also important to observe that, if all nodes $i\neq 1$ were to perform subsequent local updates (20b), the local variable $x_{j}$ will have the same support (i.e., only the first element is non-zero). To see this, suppose $k=2$, then for $i=2$, we have

since $x=0$ implies $\Psi^{\prime}\left(-x\right)=0$. Similarly reasoning applies when $i=2$, $k\geq 3$.

If $i\geq 3$, then these local functions are not related to $x_{i}$, so the partial derivative is also zero.

Now let us look at node $i=1$. For this node, according to (46), we have

Since $x_{1}$ can be non-zero, then this partial gradient can also be non-zero. Further, with a similar argument as above, we can also confirm that no matter how many local computation steps that node $1$ performs, only the first two elements of $x_{1}$ can be non-zero.

So for the first stage $t=1$, we conclude that, no matter how many local computation that the nodes perform (in the form of the computation step given in (20b)), only $x_{1}$ can have two non-zero entries, while the rest of the local variables only have one non-zero entries.

Then suppose that the communication and aggregation step is performed once. It follows that after broadcasting $\bar{x}=\frac{1}{N}\sum_{i=1}^{N}\alpha_{i}x_{i}$ to all the nodes, everyone can have two non-zero entries. Then the nodes proceed with local computation, and by the same argument as above, one can show that this time only $x_{2}$ can have three non-zero entries. Following the above procedure, it is clear that each aggregation step can advance the non-zero entry of $\bar{x}$ by one, while performing multiple local updates does not advance the non-zero entry. Then we conclude that we need at least $T$ communication steps, and local gradient computation steps, to make $x_{i}[T]$ possibly non-zero. $\blacksquare$

B.4 Main Result for Claim 2.1.

Below we state and prove a formal version of Claim 2.1 given in the main text.

Let $\epsilon$ be a positive number. Let $x_{i}^{0}[j]=0$ for all $i\in[N]$, and all $j=1,\cdots,T+1$. Consider any algorithm obeying the rules given in (10), where the $V^{t}(\cdot)$ and $W^{t}_{i}(\cdot)$’s are linear operators. Then regardless of the number of local updates there exists a problem satisfying Assumption 1 – 2, such that it requires at least the following number of stages $t$ (and equivalently, aggregation and communications rounds in (20a))

Proof of Claim 2.1. First, let us show that the algorithm obeying the rules given in (20) has the desired property. Note that the difference between two rules is whether the sampled local gradients are used for the update, or the full local gradients are used.

By Lemma 4 we have $\bar{x}[T]=0$ for all $t<T$. Then by applying Lemma 2 – (2) and Lemma 3, we can conclude that the following holds

where the second inequality follows that there exists $k\in[T]$ such that $|\frac{\bar{x}[k]U}{\pi\sqrt{2\epsilon}}|=0<1$, then we can directly apply Lemma 3.

The third part of Lemma 2 ensures that $f_{i}$’s are $L$-Lipschitz continuous gradient, and the first part shows

Second, consider the algorithm obeying the rules give in (10), in which local sampled gradients are used. By careful inspection, the result for this case can be trivially extended from the previous case. We only need to consider the following local functions

where each sampled loss function $F(x;\xi_{i})$ is defined as

where $\delta(\xi_{i})$’s satisfy $\delta(\xi_{i})>0$ and $\sum_{\xi_{i}\in D_{i}}\delta(\xi_{i})=1$. It is easy to see that, the local sampled gradients have the same dependency on $x$ as their averaged version (by dependency we meant the structure that is depicted in Fig. 3). Therefore, the progression of the non-zero pattern of the average $\bar{x}=\frac{1}{N}\sum_{i=1}^{N}x_{i}$ is exactly the same as the batch gradient version. Additionally, since the local function $\hat{f}(x)$ is exactly the same as the previous local function $f(x)$, so other estimates, such as the one that bounds $f(0)-\inf f(x)$, also remain the same.

Appendix C Proof of Claim 2.2

First let us consider FedAvg with local-GD update (9). We consider the following problem with $N=2$, which satisfies both Assumptions 1 and 2, with $f(\mathbf{x})=0,\;\forall~{}\mathbf{x}$

Each local iteration of the FedAvg is given by

For simplicity, let us define $\mathbf{y}=[\mathbf{x}_{1},\mathbf{x}_{2}]^{T}$, and define the matrix $\mathbf{D}=[1-\eta,0;0,1+\eta]$. Then running $Q$ rounds of the FedAvg algorithm starting with $r=kQ$ for some non-negative integer $k\geq 0$, can be expressed as

It is easy to show that for any $Q>1$, the eigenvalues of the matrix $\frac{1}{2}\mathbf{D}^{Q-1}\mathbf{1}\mathbf{1}^{T}\mathbf{D}$ are and $\frac{(1+\eta)^{Q}+(1-\eta)^{Q}}{2}>1$.

It follows that the above iteration will diverge for any $Q>1$ starting from any non-zero initial point.

Moreover, when the sample on one agent are the same (e.g., agent 1 has two samples that both has loss function $x^{2}$), then using SGD as local update will be identical to the update of GD.

Appendix D Results showing the role of GB for FedAvg with diminishing stepsizes

This section is used to show the role of A3 in FedAvg. First we prove that with A3, FedAvg can use arbitrary stepsize as long as it diminishes to zero. Next, we show by a simple example that without A3, FedAvg will diverge with the same diminishing stepsize choice.

Suppose A1–A3 hold and the stepsizes satisfy: 1) $\eta^{r,0}=\eta\in(0,1/L)$ for all $r$; 2) set $0<\eta^{r,q}\leq\min\{\frac{1}{2(Q-1)L},\frac{\eta}{Q}\},\;\lim_{r\rightarrow\infty}\eta^{r,q}=0,~{}q\neq 0$. Then the average gradient converges to zero for FedAvg with local-GD update (9):

Suppose that all the assumptions made in Claim D.1 hold, except that A3 does not hold. Then FedAvg with local-GD can diverge for any $Q>1$.

Before we prove Claim D.1, the following lemma is needed.

Under A1 and A3, following the update steps in Algorithm 1, between each outer iterations we have:

where $(a)$ comes from the update rule in Algorithm 1, in $(b)$ we use Jensen’s inequality and notice $\mathbf{x}^{r,0}_{i}=\mathbf{x}^{r}$ so in $(c)$ we extract the terms with index $(r,0)$ from the inner product.

Note that for any vector $a,b$ of the same length, the equality $2\left\langle a,b\right\rangle=\left\lVert a\right\rVert^{2}+\left\lVert b\right\rVert^{2}-\left\lVert a-b\right\rVert^{2},$ holds, we have

where we use Jensen’s inequality in $(a)$ and A1 in $(b)$.

The first equality comes from the update rule of $\mathbf{x}^{r,q}_{i}$, which basically performs $q$ steps of updates on $\mathbf{x}^{r}$; $(a)$ comes from Jensen’s inequality; in $(b)$ we use A3.

Substitute (63) to (62) and then to (61), rearrange the terms we obtain (60), which ends the proof of the lemma. $\blacksquare$

Proof: By choosing $\eta^{r,0}=\eta_{1}=\in(0,1/L)$ as constant and $\eta^{r,q}\leq 1/(2QL)\;,\forall~{}q\neq 0$ then applying Lemma 5 we have

where $C_{1}=\eta_{1}(1-L\eta_{1})>0$. Using telescope sum from $r=0$ to $r=T-1$ we have

Rearrange the terms and multiply both side by $2/(TC_{1})$, then we have

Choose $\eta^{r,q}\leq\eta_{1}/Q$, then $(\eta_{1})^{2}+\sum^{Q-1}_{q=1}(\eta^{r,q})^{2}\leq 2(\eta_{1})^{2}$. Choose $\{\eta^{r,q}\}$ as a sequence that diminishes to , then for all $q\neq 0$, as $T\rightarrow\infty$, $\frac{2\eta_{1}Q^{2}G^{2}}{C_{1}}\frac{1}{QT}\sum^{T-1}_{r=0}\sum^{Q-1}_{q=1}\eta^{r,q}\rightarrow 0$. Therefore the right hand side converges to 0, Claim D.1 is proved.

Appendix E Proof of Claim D.2

Proof. We consider the following problem with $N=2$, which satisfies both Assumptions 1 and 2, with $f(\mathbf{x})=0,\;\forall~{}\mathbf{x}$

Each local iteration of the FedAvg is given by

For simplicity, let us define $\mathbf{y}=[\mathbf{x}_{1},\mathbf{x}_{2}]^{T}$, and define the matrix $\mathbf{D}_{r}=[1-\eta^{r},0;0,1+\eta^{r}]$. Then running $Q$ rounds of the FedAvg algorithm starting with $r=kQ$ for some non-negative integer $k\geq 0$, can be expressed as

In particular, we pick $\eta^{r}=\frac{1}{\sqrt{r}}$ when $r\neq kQ+1$ and $\eta^{kQ+1}=1/2$. Then for $Q>1$, it is easy to compute the eigenvalues of the matrix $\frac{1}{2}\prod_{r=kQ+1}^{(k+1)Q-1}\mathbf{D}_{r}\mathbf{1}\mathbf{1}^{T}\mathbf{D}_{kQ}$ to be:

It is clear that $\lambda_{2}$ is strictly larger than one which indicates that the algorithm will diverge. $\blacksquare$

Appendix F Proofs for Results in Section 3

First let us prove Theorem 1 about the FedPD algorithm with Oracle I.

Towards this end, let us first introduce some notations. First recall that when Oracle I is used, the local problem is solved such that the following holds true:

Note that if SGD is applied in Oracle I to solve the local problem, then this condition (71) is replaced with the following

The difference does not significantly change the proofs and the results. So throughout the proof of Theorem 1, we use (71) as the condition.

Then we define the error between different nodes as

Here, $\triangle\mathbf{x}^{r}_{0}$ denotes the maximum difference of estimated center model among all the nodes and $\triangle\mathbf{x}^{r}$ denotes the maximum difference of local models among all nodes.

From the termination condition that generates $\mathbf{x}^{r+1}_{i}$ (given in (71)), we have

where the first equality holds because of the update rule of $\lambda_{i}$. Furthermore, from the update step of $\lambda^{r+1}_{i}$, we can explicitly write down the following expression

The main lemmas that we need are outlined below. Their proofs can be found in Sec. F.1.1– F.1.4.

The first lemma shows the sufficient descent of the local AL function.

Suppose A1 holds true. Consider FedPD with Algorithm 4 (Oracle I) as the update rule. When the local problem is solved such that (71) is satisfied, the difference of the local augmented Lagrangian is bounded by

Then we derive a key lemma about how the error propagates if the communication step is skipped.

Suppose A1 and A5 hold. Consider FedPD with Algorithm 4 (Oracle I) as the update rule. When the local problem is solved such that (71) is satisfied, the difference between the local models $\mathbf{x}^{r}_{i}$’s and the difference between local copies of the global models $\mathbf{x}^{r}_{0,i}$’s are bounded by

is a rank $1$ matrix with eigenvalues $(0,L\eta+p(1+L\eta))$ and $B=[p(3+L\eta),2]^{\scriptscriptstyle T}$.

We define a virtual sequence $\{\overline{\mathbf{x}}^{r}_{0}\}$ where $\overline{\mathbf{x}}^{r}_{0}\triangleq\frac{1}{N}\sum^{N}_{i=1}\mathbf{x}^{r}_{0,i}$ which is the average of the local $\mathbf{x}^{r}_{0,i}$ and we know that $\mathbf{x}^{r}_{0,i}=\mathbf{x}^{r}_{0}$ when $r\mod R=1$, that is, when the communication and aggregation step is performed. Next, we bound the error between the local AL and the global AL evaluated at the virtual sequence.

Suppose A1 holds. Consider FedPD with Algorithm 4 (Oracle I) as the update rule. When the local problem is solved such that (71) is satisfied, the difference between local AL and the global AL is bounded as below:

Lastly we bound the original objective function using the global AL.

Under A1 and A2, when the local problem is solved to $\epsilon_{1}$ accuracy, the difference between the original loss and the augmented Lagrangian is bounded.

Using the previous lemmas, we can then prove Theorem 1.

We divide the left hand side (LHS) of (75), i.e., $\mathcal{L}_{i}(\mathbf{x}^{r+1}_{i},\mathbf{x}^{r+}_{0,i},\lambda^{r+1}_{i})-\mathcal{L}_{i}(\mathbf{x}^{r}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})$, into the sum of three parts:

which correspond to the three steps in the algorithm’s update steps.

We bound the first difference by first applying A1 to $-f(\cdot)$:

and obtain the following series of inequalities:

In the above equation, in $(a)$ we use the fact that $\left\lVert a\right\rVert^{2}-\left\lVert b\right\rVert^{2}=\left\langle a+b,a-b\right\rangle$ when vector $a,b$ has the same length to the last two terms; in $(b)$ we split the last term into $2\mathbf{x}^{r+1}_{i}-2\mathbf{x}^{r}_{0,i}$ and $-\mathbf{x}^{r+1}_{i}+\mathbf{x}^{r}_{i}$; in $(c)$ we use the fact that $\left\langle a,b\right\rangle\leq\frac{L}{2}\left\lVert a\right\rVert^{2}+\frac{1}{2L}\left\lVert b\right\rVert^{2})$; in $(d)$ we apply the fact that $\mathbf{x}^{r+1}_{i}$ is the inexact solution; see (74).

Then we bound the second difference in (79) by the following:

where $(a)$ directly comes from the update rule of $\lambda^{r+1}_{i}$.

Further we bound the third difference in (79) by the following:

where, in $(a)$, we use the same reasoning as in (80) $(a)$ and $(b)$; in $(b)$ we apply the update rule of $\mathbf{x}^{r+}_{0,i}$ in the FedPD algorithm, which implies that the first term becomes zero.

Finally we sum up (80), (81), (82) and Lemma 6 is proved.

F.1.2 Proof of Lemma 7

First we derive the relation between $\left\lVert\mathbf{x}^{r+1}_{i}-\mathbf{x}^{r+1}_{j}\right\rVert$ for arbitrary $i\neq j$ and $\triangle^{r}$ by using the definition of $\epsilon_{1}$ (74):

where in $(a)$ we plug the definition of $\triangle\mathbf{x}^{r}_{0}$ and $\mathbf{e}^{r+1}_{i}$; in $(b)$ we use A1; $(c)$ comes form A5; in $(d)$ we move the second term to the left and divide both side by $1-L\eta$.

Then we bound the difference $\left\lVert\lambda^{r}_{i}-\lambda^{r}_{j}\right\rVert$ by plugging in the expression of $\lambda^{r}_{i}$ in (74), and note that $\lambda^{r}_{i}+\frac{1}{\eta}(\mathbf{x}^{r+1}_{i}-\mathbf{x}^{r}_{0,i})=\lambda^{r+1}_{i}$:

where $(a)$ and $(b)$ follow the same argument in $(a)$, $(b)$ and $(c)$ of (83) ; in $(c)$ we plug in the definition of $\triangle\mathbf{x}^{r}$.

Next we bound the difference $\left\lVert\mathbf{x}^{r+1}_{0,i}-\mathbf{x}^{r+1}_{0,j}\right\rVert$. With probability $1-p$ the aggregation step has just been done at iteration $r$, $\mathbf{x}^{r+1}_{0,i}=\mathbf{x}^{r+1}_{0,j}$.With probability $p$, they are not equal, then we take expectation with communication probability $p$, and get

where in $(a)$ we plug in the definition of $\triangle\mathbf{x}^{r+1}$ and (84). As these relations hold true for arbitrary $(i,j)$ pairs, they are also true for the maximum of $\left\lVert\mathbf{x}^{r+1}_{i}-\mathbf{x}^{r+1}_{j}\right\rVert$ and $\left\lVert\mathbf{x}^{r+1}_{0,i}-\mathbf{x}^{r+1}_{0,j}\right\rVert$.

Therefore stacking (83) and (85) and plug in (84), we have

Rewrite it into matrix form then we complete the proof of Lemma 7.

F.1.3 Proof of Lemma 8

Let us first recall that the definition of local AL is given below:

where $(a)$ follows the same argument in (82); in $(b)$,we plug in the definition of $\overline{\mathbf{x}}^{r+1}_{0}$; in $(c)$ we use Jensen’s inequality and we bound the term with $\triangle\mathbf{x}^{r+1}_{0}$. Then the lemma is proved.

F.1.4 Proof of Lemma 9

Taking an average over $N$ agents we are able to prove Lemma 9.

F.1.5 Proof of Theorem 1

First notice that from the optimality condition (74), the following holds:

Then we bound the gradients of $\mathcal{L}(\mathbf{x}^{r}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})$.

Further, we note that, when no aggregation has been performed at iteration $r$, then $\mathbf{x}^{r}_{0,i}=\mathbf{x}^{r}_{i}+\eta\lambda^{r}_{i}$, so the following holds

When there the aggregation has been performed at iteration $r$, then $\mathbf{x}^{r}_{0,i}=\frac{1}{N}\sum^{N}_{j=1}(\mathbf{x}^{r}_{j}+\eta\lambda^{r}_{j}),~{}\forall i$, so we have

Summing (90) and (93), denote $\left\lVert\nabla_{\mathbf{x}_{i}}\mathcal{L}_{i}(\mathbf{x}^{r}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})\right\rVert+\left\lVert\nabla_{\lambda_{i}}\mathcal{L}_{i}(\mathbf{x}^{r}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})\right\rVert$ as $\left\lVert\nabla\mathcal{L}_{i}(\mathbf{x}^{r}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})\right\rVert$ we have

Squaring both sides of the above inequality, we obtain:

where $C_{6}\geq\max\{(\frac{1+L\eta}{\eta})^{2},(1+2\eta)^{2},L^{2}\eta^{2}\}$.

Notice that when communication is not performed $\left\lVert\mathbf{x}^{r}_{0,i}-\mathbf{x}^{r+1}_{0,i}\right\rVert^{2}{\leq}\left\lVert\mathbf{x}^{r}_{0,i}-\mathbf{x}^{r+}_{0,i}\right\rVert^{2}$, and when communication is performed

where the last inequality holds due to the use of Jensen’s inequality, and the definition of $\triangle\mathbf{x}^{r+1}_{0}$ in (73). It follows that summing both sides of (96) over $i$, we have

Taking the expectation over the randomness in $p$, conditioning on the information before the communication the successive difference of $\mathcal{L}_{i}$,

where (a) expands the expectation on $p$, and use the fact that with probability $p$, $\mathbf{x}^{r+1}_{0,i}=\mathbf{x}^{r+}_{0,i}$, and with probability $(1-p)$ $\mathbf{x}^{r+1}_{0}$ will be updated; in (b) we apply Lemma 8 to the last term.

Combining (95), (98) and (100), define $C_{7}=2C_{6}/\min\{\frac{1-2L\eta-4L^{2}\eta^{2}}{2\eta},\frac{1}{2\eta},\frac{1+8L\eta}{2L}\}$ and sum up the iterations, we have

Next we bound the last term. By iteratively applying Lemma 7 from $\tau=0$ to $r$ and use the fact that $\Delta^{0}=0$, we have

So by taking norm square on both side of (102), we have

Substitute (103) into (101) and divide both side by $T$ we have

From the initial conditions we have $\mathcal{L}(\mathbf{x}^{0}_{0},\mathbf{x}^{0}_{i},\lambda^{0}_{i})=f(\mathbf{x}^{0}_{0})$ and apply Lemma 9 we obtain

Finally we bound $\left\lVert\nabla f(\mathbf{x}^{r}_{0})\right\rVert^{2}$ by

where in $(a)$ we use the same argument in (91) and (92).

Therefore Theorem 1 is proved. During the proof, we need all $C_{2},\dots,C_{7},C_{8}>0$, therefore, $0<\eta<\frac{\sqrt{5}-1}{4L}$.

Finally, let us note that if the local problems are solved with SGD, then the local problem needs to be solved such that the condition (72) holds true. As no other information of the local solvers except error term $\mathbf{e}^{r}_{i}$ is used in the proof, the proofs and results of FedPD with SGD as local solver will not change much, except that all the results hold in expectation. Therefore we skip the proof for the SGD version.

F.1.6 Constants used in the proofs

In this subsection we list all the constants $C_{2},\dots,C_{8}$ used in the proof of Theorem 1.

we can see that when $0<\eta<\frac{\sqrt{5}-1}{4L}$, all the terms are positive.

Appendix G FedPD with Variance Reduction

In this section we provided an alternative oracle for FedPD which has a lower sample complexity.

Alternatively, when instantiating the local oracle using Algorithm 4, the original local problems are not required to solve to $\epsilon_{1}$ accuracy. Instead, we successively optimize a linearized AL function:

In the above expression, we linearize $f_{i}(\mathbf{x}_{i})$ at inner iteration $\mathbf{x}^{r,q}_{i}$ as ($\gamma$ is a constant)

where $g^{r,q}_{i}$ is an approximation of $\nabla f_{i}(\mathbf{x}^{r,q}_{i})$. The optimizer has a closed-form expression:

In Oracle II, an agent $i$ first decides whether to compute the full gradient $\nabla f_{i}(\mathbf{x}^{r,0}_{i})$, or to keep using the previous estimate $g^{r-1,Q}_{i}$. Then $Q$ local steps are performed, each requires $B$ local data samples. In this scheme, $Q$ can be chosen as any positive integer.

It is important to note that this oracle does not simply apply the VR technique (such as F-SVRG) to solve the subproblem of optimizing $\mathcal{L}_{i}(\mathbf{x}_{i},\mathbf{x}^{r}_{0,i},\lambda^{r}_{i})$. That is, it is not a variation of Oracle I. Instead, the VR technique is applied to the entire primal-dual iteration, and the full gradient evaluation $\nabla f_{i}(\mathbf{x}^{r,0}_{i})$ is only needed every $I$ iteration $r$. Later we will see that if $I$ is large enough, then there is an $\mathcal{O}(\sqrt{M})$ reduction of sample complexity.

G.2 Algorithm Convergence and Complexity

The convergence result of FedPD with Oracle II is given as follows:

Suppose A1–A2 hold, and consider FedPD with Oracle II. Choose $p=0$, \eta\in\big{(}0,\frac{1}{3(Q+\sqrt{QI/B})L}\big{)}, and $\gamma>\frac{5\eta}{B\sqrt{L}}$. Then, the following holds (where $C_{9}>0$ is a constant):

Remark 5. (Communication complexity): As $p=0$, the communication round to achieve $\epsilon$ accuracy is $T=\mathcal{O}(1/\epsilon)$ which is independent of $Q$.

Remark 6. (Computation complexity): Note that the total number full gradient evaluation is $T/I+1$, each uses $M$ samples. Meanwhile, the total number of mini-batch stochastic gradient evaluation is $TQ$, each uses $2B$ samples per node. So the total sample complexity is $\mathcal{O}(M+MT/I+2TQBN)$. In order to keep the same convergence speed, we need stepsize $\eta$ to be unchanged. Therefore, we choose $I=\sqrt{M},B=I/QN=\sqrt{M}/QN$, then the SC of Algorithm 4 is $\mathcal{O}(M+\frac{\sqrt{M}}{\epsilon})$.

G.3 Proof of Theorem 3

Following the similar proof of Theorem 1, we first analyze the descent between each outer iteration. Notice throughout the proof, we assume that $p=0$, that is, there is no delayed communication. It follows that the following holds:

We also recall that $r$ is the (outer) stage index, and $q$ is the local update index. First we provide a series of lemmas.

Under Assumption 1, consider FedPD with Algorithm 4 (Oracle II) as the update rule. The difference of the local AL is bounded by:

Then we deal with the variance of the stochastic gradient estimations.

Suppose A1 holds true and the samples are randomly sampled according to (13), consider FedPD with Algorithm 4 (Oracle II) as the update rule. The expected norm square of the difference between $g^{r,q+1}_{i}$ and $\nabla f_{i}(\mathbf{x}^{r,q+1}_{i})$ is bounded by

Lastly we upper bound the original loss function.

Under A1 and A2, the difference between the original loss and the AL is bounded as below:

Let us first express the difference of the local AL as following:

where the above three differences respectively correspond to the three steps in the algorithm’s update steps.

Let us bound the above three differences one by one. First, note that we have the following decomposition (by using the fact that $\mathbf{x}^{r,Q+1}_{i}=\mathbf{x}^{r+1}_{i}$ and $\mathbf{x}^{r,1}_{i}=\mathbf{x}^{r}_{i}$):

Each term on the right hand side (RHS) of the above equality can be bounded by (see a similar arguments in (80)):

in $(b)$ we use the fact that $2\left\langle a,b\right\rangle\leq L\left\lVert a\right\rVert^{2}+\frac{1}{L}\left\lVert b\right\rVert^{2}$. Therefore, the first difference in the RHS of (108) is given by

The other two differences in (108) can be explicitly expressed as:

Next we bound $\left\lVert\lambda^{r+1}_{i}-\lambda^{r}_{i}\right\rVert^{2}$. Notice that the from the update rule the following holds:

where in $(a)$ we apply Cauchy-Schwarz inequality. Next we bound $\left\lVert g^{r,Q-1}_{i}-g^{r-1,Q-1}_{i}\right\rVert^{2}$ by

where in $(a)$ and $(b)$ we both apply Cauchy-Schwarz inequality, in $(a)$ we use A1 to the last term and in $(b)$ we notice $\mathbf{x}^{r-1,Q}_{i}=\mathbf{x}^{r,0}_{i}$.

Substitute (G.3.1) to (116) and sum the three parts, we have

G.3.2 Proof of Lemma 11

That is, $r_{0}$ is a multiple of $I$ and there is no more than $IQ$ local update steps between step $\{r_{0},0\}$ and step $\{r,q\}$. By the update rule of $g^{r,q}_{i}$, we have

Iteratively taking expectation until $\{r,q\}=\{r_{0},0\}$, we have

G.3.3 Proof of Lemma 12

where in $(a)$ we apply Cauchy-Schwarz inequality twice, that is

in $(b)$ we apply Lemma 11 to the first term and apply A1 to the second term.