## FEDCHAIN: CHAINED ALGORITHMS FOR NEAR-OPTIMAL COMMUNICATION COST
### IN FEDERATED LEARNING


**Charlie Hou**
Department of Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, Pennsylvania, USA
charlieh@andrew.cmu.edu

**Giulia Fanti**
Department of Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, Pennsylvania, USA
gfanti@andrew.cmu.edu

ABSTRACT


**Kiran K. Thekumparampil**
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
Champaign, Illinois, USA
thekump2@illinois.edu

**Sewoong Oh**
Allen School of Computer Science and Engineering
University of Washington
Seattle, Washington, USA
sewoong@cs.washington.edu


Federatedd learning (FL) aims to minimize the communication complexity of
training a model over heterogeneous data distributed across many clients. A
common approach is local update methods, where clients take multiple optimization
steps over local data before communicating with the server (e.g., FedAvg). Local
update methods can exploit similarity between clients’ data. However, in existing
analyses, this comes at the cost of slow convergence in terms of the dependence
on the number of communication rounds R. On the other hand, global update
methods, where clients simply return a gradient vector in each round (e.g., SGD),
converge faster in terms of R but fail to exploit the similarity between clients even
when clients are homogeneous. We propose FedChain, an algorithmic framework
that combines the strengths of local update methods and global update methods to
achieve fast convergence in terms of R while leveraging the similarity between
clients. Using FedChain, we instantiate algorithms that improve upon previously
known rates in the general convex and PL settings, and are near-optimal (via an
algorithm-independent lower bound that we show) for problems that satisfy strong
convexity. Empirical results support this theoretical gain over existing methods.

1 INTRODUCTION

In federated learning (FL) (McMahan et al., 2017; Kairouz et al., 2019; Li et al., 2020), distributed
clients interact with a central server to jointly train a single model without directly sharing their data
with the server. The training objective is to solve the following minimization problem:


_F_ (x) = [1]


_Fi(x)_ (1)
_i=1_

X i


min


where variable x is the model parameter, i indexes the clients (or devices), N is the number of
clients, and Fi(x) is a loss that only depends on that client’s data. Typical FL deployments have two
properties that make optimizing Eq. (1) challenging: (i) Data heterogeneity: We want to minimize
the average of the expected losses Fi(x) = Ezi _i_ [f (x; zi)] for some loss function f evaluated on
_∼D_
client data zi drawn from a client-specific distribution Di. The convergence rate of the optimization
depends on the heterogeneity of the local data distributions, {Di}i[N]=1[, and this dependence is captured]
by a popular notion of client heterogeneity, ζ [2], defined as follows:

_ζ_ [2] := max (2)
_i∈[N_ ] [sup]x

_[∥∇][F]_ [(][x][)][ −∇][F][i][(][x][)][∥][2][ .]


-----

This captures the maximum difference between a local gradient and the global gradient, and is a
standard measure of heterogeneity used in the literature (Woodworth et al., 2020a; Gorbunov et al.,
2020; Deng et al., 2020; Woodworth et al., 2020a; Gorbunov et al., 2020; Yuan et al., 2020; Deng et al.,
2021; Deng & Mahdavi, 2021). (ii) Communication cost: In many FL deployments, communication
is costly because clients have limited bandwidths. Due to these two challenges, most federated
optimization algorithms alternate between local rounds of computation, where each client locally
processes only their own data to save communication, and global rounds, where clients synchronize
with the central server to resolve disagreements due to heterogeneity in the locally updated models.

Several federated algorithms navigate this trade-off between reducing communication and resolving
data heterogeneity by modifying the amount and nature of local and global computation (McMahan
et al., 2017; Li et al., 2018; Wang et al., 2019b;a; Li et al., 2019; Karimireddy et al., 2020b;a;
Al-Shedivat et al., 2020; Reddi et al., 2020; Charles & Konecnˇ y, 2020; Mitra et al., 2021; Woodworth`
et al., 2020a). These first-order federated optimization algorithms largely fall into one of two camps:
(i) clients in local update methods send updated models after performing multiple steps of model
updates, and (ii) clients in global update methods send gradients and do not perform any model
updates locally. Examples of (i) include FedAvg (McMahan et al., 2017), SCAFFOLD (Karimireddy
et al., 2020b), and FedProx (Li et al., 2018). Examples of (ii) include SGD and Accelerated SGD
(ASG), where in each round r the server collects from the clients gradients evaluated on local data at
the current iterate x[(][r][)] and then performs a (possibly Nesterov-accelerated) model update.

As an illustrating example, consider the scenario when Fi’s are µ-strongly convex and β-smooth such
that the condition number is κ = β/µ as summarized in Table 1, and also assume for simplicity that
all clients participate in each communication round (i.e., full participation). Existing convergence
analyses show that local update methods have a favorable dependence on the heterogeneity ζ. For
example, Woodworth et al. (2020a) show that FedAvg achieves an error bound of _O[˜]((κζ_ [2]/µ)R[−][2])
after R rounds of communication. Hence FedAvg achieves theoretically faster convergence for
smaller heterogeneity levels ζ by using local updates. However, this favorable dependency on ζ
comes at the cost of slow convergence in R. On the other hand, global update methods converge
faster in R, with error rate decaying as _O[˜](∆exp(−R/[√]κ)) (for the case of ASG), where ∆_ is the
initial function value gap to the (unique) optimal solution. This is an exponentially faster rate in R,
but it does not take advantage of small heterogeneity even when client data is fully homogeneous.

Our main contribution is to design a novel family of algorithms that combines the strengths of local
and global methods to achieve a faster convergence while maintaining the favorable dependence on
the heterogeneity, thus achieving an error rate of _O[˜]((ζ_ [2]/µ) exp(−R/[√]κ)) in the strongly convex
scenario. By adaptively switching between this novel algorithm and the existing best global method,
we can achieve an error rate of _O[˜](min{∆, ζ_ [2]/µ} exp(−R/[√]κ)). We further show that this is nearoptimal by providing a matching lower bound in Thm. 5.4. This lower bound tightens an existing
one from (Woodworth et al., 2020a) by considering a smaller class of algorithms that includes those
presented in this paper.

We propose FedChain, a unifying chaining framework for federated optimization that enjoys the
benefits of both local update methods and global update methods. For a given total number of rounds
_R, FedChain first uses a local-update method for a constant fraction of rounds and then switches_
to a global-update method for the remaining rounds. The first phase exploits client homogeneity
when possible, providing fast convergence when heterogeneity is small. The second phase uses the
unbiased stochastic gradients of global update methods to achieve a faster convergence rate in the
heterogeneous setting. The second phase inherits the benefits of the first phase through the iterate
output by the local-update method. An instantiation of FedChain consists of a combination of a
specific local-update method and global-update method (e.g., FedAvg → SGD).

**Contributions. We propose the FedChain framework and analyze various instantiations under**
strongly convex, general convex, and nonconvex objectives that satisfy the PL condition.[1] Achievable
rates are summarized in Tables 1, 2 and 4. In the strongly convex setting, these rates nearly match the
algorithm-independent lower bounds we introduce in Theorem 5.4, which shows the near-optimality of
FedChain. For strongly convex functions, chaining is optimal up to a factor that decays exponentially
in the condition number κ. For convex functions, it is optimal in the high-heterogeneity regime, when

1F satisfies the µ-PL condition if 2µ(F (x) − _F_ (x∗)) ≤∥∇F (x)∥2.


-----

**Algorithm 1 Federated Chaining (FedChain)**

**Input: Alocal local update algorithm, Aglobal centralized algorithm, initial point ˆx0, K, rounds R**

_▷_ **Run Alocal for R/2 rounds**

_xˆ1/2_ local(ˆx0)

_▷_ **Choose the better point between ←A** ˆx0 and ˆx1/2

Sample S clients S ⊆ [N ]
Draw ˆzi,k _i, i_, k 0, . . ., K 1

_xˆ1_ arg min ∼Dx _∈Sxˆ0,xˆ1/2_ _∈{SK1_ _i_ _−Kk=0−1}[f]_ [(][x][; ˆ]zi,k)
_←_ _∈{_ _}_ _∈S_

_▷_ **Finish convergence with** global for R/2 rounds
_AP_ P

Returnxˆ2 ←A ˆxglobal2 (ˆx1)


_ζ > βDR[1][/][2]. For nonconvex PL functions, it is optimal for constant condition number κ. In all_
three settings, FedChain instantiations improve upon previously known worst-case rates in certain
regimes of ζ. We further demonstrate the empirical gains of our chaining framework in the convex
case (logistic regression on MNIST) and in the nonconvex case (ConvNet classification on EMNIST
(Cohen et al., 2017) and ResNet-18 classification on CIFAR-100 (Krizhevsky, 2009)).

1.1 RELATED WORK

The convergence of FedAvg in convex optimization has been the subject of much interest in the
machine learning community, particularly as federated learning (Kairouz et al., 2019) has increased in
popularity. The convergence of FedAvg for convex minimization was first studied in the homogeneous
client setting (Stich, 2018; Wang & Joshi, 2018; Woodworth et al., 2020b). These rates were
later extended to the heterogeneous client setting (Khaled et al., 2020; Karimireddy et al., 2020b;
Woodworth et al., 2020a; Koloskova et al., 2020), including a lower bound (Woodworth et al., 2020a).
The only current known analysis for FedAvg that shows that FedAvg can improve on SGD/ASG
in the heterogeneous data case is that of Woodworth et al. (2020a), which has been used to prove
slightly tighter bounds in subsequent work Gorbunov et al. (2020).

Many new federated optimization algorithms have been proposed to improve on FedAvg and
SGD/ASG, such as SCAFFOLD (Karimireddy et al., 2020b), S-Local-SVRG (Gorbunov et al.,
2020), FedAdam (Reddi et al., 2020), FedLin (Mitra et al., 2021), FedProx (Li et al., 2018). However,
under full participation (where all clients participate in a communication round; otherwise the setting
is partial participation) existing analyses for these algorithms have not demonstrated any improvement over SGD (under partial participation, SAGA (Defazio et al., 2014)). In the smooth nonconvex
full participation setting, MimeMVR (Karimireddy et al., 2020a) was recently proposed, which
improves over SGD in the low-heterogeneity setting. Currently MimeMVR and SGD are the two best
algorithms for worst-case smooth nonconvex optimization with respect to communication efficiency,
depending on client heterogeneity. In partial participation, MimeMVR and SAGA are the two best
algorithms for worst-case smooth nonconvex optimization, depending on client heterogeneity.

Lin et al. (2018) proposed a scheme, post-local SGD, opposite ours by switching from a globalupdate method to a local-update method (as opposed to our proposal of switching from local-update
method to global-update method). They evaluate the setting where ζ = 0. The authors found that
while post-local SGD has a training accuracy worse than SGD, the test accuracy can be better (an
improvement of 1% test accuracy on ResNet-20 CIFAR-10 classification), though theoretical analysis
was not provided. Wang & Joshi (2019) decrease the number (K) of local updates to transition from
FedAvg to SGD in the homogeneous setting. This is conceptually similar to FedChain, but they do
not show order-wise convergence rate improvements. Indeed, in the homogeneous setting, a simple
variant of ASG achieves the optimal worst-case convergence rate (Woodworth et al., 2021).

2 SETTING

Federated optimization proceeds in rounds. We consider the partial participation setting, where at the
beginning of each round, S ∈ Z+ out of total N clients are sampled uniformly at random without


-----

replacement. Between each global communication round, the sampled clients each access either (i)
their own stochastic gradient oracle K times, update their local models, and return the updated model,
or (ii) their own stochastic function value oracle K times and return the average value to the server.
The server aggregates the received information and performs a model update. For each baseline
optimization algorithm, we analyze the sub-optimality error after R rounds of communication between
the clients and the server. Suboptimality is measured in terms of the function value EF (ˆx) − _F_ (x[∗]),
where ˆx is the solution estimate after R rounds and x[∗] = arg minx F (x) is a (possibly non-unique)
optimum of F . We let the estimate for the initial suboptimality gap be ∆ (Assumption B.9), and the
initial distance to a (not necessarily unique) optimum be D (Assumption B.10). If applicable, ϵ is the
target expected function value suboptimality.

We study three settings: strongly convex Fi’s, convex Fi’s and µ-PL F ; for formal definitions, refer
to App. B. Throughout this paper, we assume that the Fi’s are β-smooth (Assumption B.4). If Fi’s
are µ-strongly convex (Assumption B.1) or F is µ-PL (Assumption B.3), we denote κ = β/µ as the
condition number. Di is the data distribution of client i. We define the heterogeneity of the problem
as ζ [2] := maxi [N ] supx _F_ (x) _Fi(x)_ in Assumption B.5. We assume unless otherwise
_∈_ _∥∇_ _−∇_ _∥[2]_
specified that ζ [2] _> 0, i.e., that the problem is heterogeneous. We assume that the client gradient_
variance is upper bounded by σ[2] (Assumption B.6). We also define the analogous quantities for
function value oracle queries: ζF[2] [Assumption B.8,][ σ]F[2] [Assumption B.7. We use the notation][ ˜]O, Ω[˜] to
hide polylogarithmic factors, and O, Ω if we are only hiding constant factors.

3 FEDERATED CHAINING (FEDCHAIN) FRAMEWORK

We start with a toy example (Fig. 1) to illustrate FedChain. Consider two strongly convex client objectives: F1(x) = (1/2)(x 1)[2]
_−_
and F2(x) = (x + 1)[2]. The global objective
_F_ (x) = (F1(x) + F2(x))/2 is their average.
Fig. 1 (top) plots the objectives, and Fig. 1 (bottom) displays their gradients. Far from the optimum, due to strong convexity, all client gradients point towards the optimal solution; specifically, this occurs when x ∈ (−∞, −1] _∪_ [1, ∞).
In this regime, clients can use local steps (e.g.,
FedAvg) to reduce communication without sacrificing the consistency of per-client local updates.
On the other hand, close to the optimum, i.e.,
when x ∈ (−1, 1), some client gradients may
point away from the optimum. This suggests
that clients should not take local steps to avoid
driving the global estimate away from the optimum. Therefore, when we are close to the
optimum, we use an algorithm without local
steps (e.g. SGD), which is less affected by client
gradient disagreement.


This intuition seems to carry over to the non- Figure 1: A toy example illustrating FedChain. We
convex setting: Charles et al. (2021) show that have two client objectives: F1(x) and F2(x). F (x)
over the course of FedAvg execution on neural is their average. The top plot displays the objecnetwork StackOverflow next word prediction, tives and the bottom plot displays the gradients. In
client gradients become more orthogonal. regions where client gradients agree in direction,

i.e. ( _,_ 1] [1, ) it may be better to use an

**FedChain: To exploit the strengths of both local** _−∞_ _−_ _∪_ _∞_

algorithm with local steps (like FedAvg), and in

and global update methods, we propose the fed
the region where the gradient disagree in direction,

erated chaining (FedChain) framework in Alg. 1.

i.e. ( 1, 1) it may be better to use an algorithm

There are three steps: (1) Run a local-update _−_

without local steps (like SGD).

method Alocal, like FedAvg. (2) Choose the better point between the output of Alocal (which we denote ˆx1/2), and the initial point ˆx0 to initialize (3)
a global-update method Aglobal like SGD. Note that when heterogeneity is large, Alocal can actually


-----

Table 1: Rates for the strongly convex case. _[♣]_ Rate requires R ≥ _N/S._ _[♠]_ Rate requires S = N .

**Method/Analysis** EF (ˆx) − _F_ (x[∗]) ≤ _O[˜](·)_

_Centralized Algorithms_


∆exp( _κ[−][1]R) + (1_ _N_ [)][ ζ]µSR[2]
_−_ _−_ _[S]_

∆exp( _κ[−]_ 2[1] R) + (1 _N_ [)][ ζ]µSR[2]
_−_ _−_ _[S]_

∆exp(−κ[−][1]R) + κ( _[ζ]µ[2]_ [)][R][−][2]

_κ(_ _[ζ]µ[2]_ [)][R][−][2][♠]

∆exp( min _κ[−][1],_ _N[S]_
_−_ _{_ _[}][R][)][♣]_


SGD

ASG

_Federated Algorithms_

FedAvg (Karimireddy et al., 2020b)

FedAvg (Woodworth et al., 2020a)

SCAFFOLD (Karimireddy et al., 2020b)

_This paper_

FedAvg → SGD (Thm. 4.1)

FedAvg → SAGA (Thm. 4.3)

FedAvg → ASG (Thm. 4.2)

FedAvg → SSNM (Thm. 4.4)

Algo.-independent LB (Thm. 5.4)


min ∆, _[ζ]µ[2]_ _N_ [)][ ζ]µSR[2]
_{_ _[}][ exp(][−][κ][−][1][R][) + (1][ −]_ _[S]_

min ∆, _[ζ]µ[2]_ _N_

min{∆, _[ζ]µ[2]_ _[}][ exp(][−]_ [min]2 R[{][κ]) + (1[−][1][,][ S] _[}][R]N[)][♣][)][ ζ]µSR[2]_

_κ min{_ ∆, _[ζ]µ[}][2][ exp(][−][κ][−]_ [1] _NκS −[,][ S]N[S]_
_{_ _[}][ exp(][−]_ [min][{] _[}][R][)][♣]_

min{∆, κ[−] [3]2 ( _[ζ]β[2]_ [)][}][ exp(][−][κ]q[−] [1]2 R)


output an iterate with higher suboptimality gap than ˆx0. Hence, selecting the point (between ˆx0
and ˆx1/2) with a smaller F allows us to adapt to the problem’s heterogeneity, and initialize global
_A_
appropriately to achieve good convergence rates. To compare ˆx1/2 and the initial point ˆx0, we
approximate F (ˆx0) and F (ˆx1/2) by averaging; we compute _SK1_ _i_ _,k_ [K] _[f]_ [(][x][; ˆ]zi,k) for ˆx1/2, ˆx0,

_∈S_ _∈_
where K is also the number of local steps per client per round in local, and is a sample of S

P _A_ _S_

clients. In practice, one might consider adaptively selecting how many rounds of Alocal to run, which
can potentially improve the convergence by a constant factor. Our experiments in App. J.1 show
significant improvement when using only 1 round of Alocal with a large enough K for convex losses.

4 CONVERGENCE OF FEDCHAIN

We first analyze FedChain (Algo. 1) when Alocal is FedAvg and Aglobal is (Nesterov accelerated) SGD.
The first theorem is without Nesterov acceleration and the second with Nesterov acceleration.

**Theorem 4.1 (FedAvg →** **SGD). Suppose that client objectives Fi’s and their gradient queries**
_satisfy Assumptions B.4, B.5, B.6, B.7 and B.8. Then running FedChain (Algo. 1) with Alocal as_
_FedAvg (Algo. 4) with the parameter choices of Thm. E.1, and Aglobal as SGD (Algo. 2) with the_
_parameter choices of Thm. D.1, we get the following rates_ [2]:

-  Strongly convex: If Fi’s satisfy Assumption B.1 for some µ > 0 then there exists a fi_nite K above which we get, EF_ (ˆx2) − _F_ (x[∗]) ≤ _O[˜](min{∆, ζ_ [2]/µ} exp(−R/κ) + (1 −
_S/N_ )ζ [2]/(µSR)) .

-  General convex: _If Fi’s satisfy Assumption B.2, then there exists a finite K_
_above which we get the rate4_ EF (ˆx2) − _F_ (x[∗]) ≤ _O˜(min{βD[2]/R,_ _βζD[3]/√R} +_

( [4] 1 _S/N_ )( _βζD[3]/√SR)) ._

_−_ p

-  PL condition:p _Ifp Fi’s satisfy Assumption B.3 for µ > 0, then there exists a finite K above_
_which we get the rate the rate EF_ (ˆx2) − _F_ (x[∗]) ≤ _O[˜](min{∆, ζ_ [2]/µ} exp(−R/κ) + (1 −
_S/N_ )(κζ [2]/µSR)) .

2We ignore variance terms and ζF2 [= max]i [N ] [sup]x[(][F][i][(][x][)][ −] _[F]_ [(][x][))][2][ as the former can be made negligible]
_∈_
by increasing K and the latter can be made zero by running the better of FedAvg → SGD and SGD instead of
choosing the better of ˆx1/2 and ˆx0 as in Algo. 1. Furthermore, ζF[2] [terms are similar to the][ ζ] [2][ terms. The rest of]
the theorems in the main paper will also be stated this way. To see the formal statements, see App. F.


-----

Table 2: Rates for the general convex case. _[♣]_ Rate requires R ≥ _[N]S_ [.][ ♠] [Rate requires][ S][ =][ N] [.][ ♦]

Analysis from Karimireddy et al. (2020b).

**Method/Analysis** EF (ˆx) − _F_ (x[∗]) ≤ _O[˜](·)_

_Centralized Algorithms_


_βDR_ [2] + 1 _N_ _√ζDSR_

_−_ _[S]_

_βDR[2][2][ +]_ q1 _N_ _√ζDSR_

_−_ _[S]_

q


SGD

ASG

_Federated Algorithms_

FedAvg[♦]

FedAvg (Woodworth et al., 2020a)

SCAFFOLD[♦]

_This paper_

FedAvg → SGD (Thm. 4.1)

FedAvg → ASG (Thm. 4.2)

Algo.-independent LB (Thm. 5.4)


_βDR_ [2] + 3 _βζR[2][2]D[4]_ + 1 _N_ _√ζDSR_

_−_ _[S]_

3 _βζ[2]Dq[4]_ q

_R[2]_

qN _βD[2]_

_S_ _R_ _♣_

q

min{ _[βD]R_ [2] _[,]_ _√√βζDR_ [3] _} +_ 4 1 − _N[S]_ _√√4βζDSR_ [3]

min{ _[βD]R[2][2][,]_ _√βζDR_ [3] _} +_ 4q1 − _N[S]_ _√√4βζDSR[3]_ + 1 − _N[S]_ _√ζDSR_

min{ _[βD]R[2][2][,]_ _√ζDR[5][ }]_ q q


For the formal statement, see Thm. F.1.

**Theorem 4.2 (FedAvg →** **ASG). Under the hypotheses of Thm. 4.1 with a choice of Aglobal as ASG**
_(Algo. 3) and the parameter choices of Thm. D.3, we get the following guarantees:_

-  Strongly convex: If Fi’s satisfy Assumption B.1 for µ > 0 then there exists a finite K
_above which we get the rate, EF_ (ˆx2) − _F_ (x[∗]) ≤ _O[˜](min{∆, ζ_ [2]/µ} exp(−R/[√]κ) + (1 −
_S/N_ )ζ [2]/µSR).

-  General convex: _If Fi’s satisfy Assumption B.2 then there exists a finite K_
_above which we get the rate,4_ EF (ˆx2) − _F_ (x[∗])4 ≤ _O˜(min{βD[2]/R[2],_ _βζD[3]/R} +_

1 _S/N_ (ζD/√SR) + 1 _S/N_ ( _βζD[3]/√SR) )._
_−_ _−_ p

p p p


For the formal statement, see Thm. F.2. We show and discuss the near-optimality of FedAvg →
ASG under strongly convex and PL conditions (and under full participation) in Section 5, where
we introduce matching lower bounds. Under strong-convexity shown in Table 1, FedAvg → ASG,
when compared to ASG, converts the ∆exp(−R/[√]κ) term into a min{∆, ζ [2]/µ} exp(−R/[√]κ)
term, improving over ASG when heterogeneity moderately small: ζ [2]/µ < ∆. It also significantly
improves over FedAvg, as min{∆, ζ [2]/µ} exp(−R/[√]κ) is exponentially faster than κ(ζ [2]/µ)R[−][2].
Under the PL condition (which is not necessarily convex) the story is similar (Table 4), except we use
FedAvg → SGD as our representative algorithm, as Nesterov acceleration is not known to improve
under non-convex settings.

In the general convex case (Table 2), let β = D = 1 for the purpose of comparisons. Then FedAvg

4 4 _→_

ASG’s convergence rate is1 min{1/R[2], ζ [1][/][2]/R} + 1 − _S/N4_ (ζ/√SR) + 4 1 − _S/N_ _[√]ζ/√SR._

If ζ < _R[2][, then][ ζ]_ [1][/][2][/R <][ 1][/R][2][ and if][ ζ <] _S/Rp[7], then_ 1 − _S/N_ _[√]ζ/p√SR < 1/R[2], so the_

FedAvg → ASG convergence rate is better than the convergence rate of ASG under the regimep p
_ζ < min{1/R[2],_ _S/R[7]}. The rate of Karimireddy et al. (2020b) for FedAvg (which does not_

require S = N ) is strictly worse than ASG, and so has a worse convergence rate than FedAvg

p

_→_ ASG if ζ < min{1/R[2], _S/R[7]}. Altogether, if ζ < min{1/R[2],_ _S/R[7]}, FedAvg →_ ASG

achieves the best known worst-case rate. Finally, in thep _S = N case, FedAvgp_ _→_ ASG does not have a
regime in ζ where it improves over both ASG and FedAvg (the analysis of Woodworth et al. (2020a),
which requires S = N ) at the same time. It is unclear if this is due to looseness in the analysis.

Next, we analyze variance reduced methods that improve convergence when a random subset of the
clients participate in each round (i.e., partial participation).


-----

Figure 2: Plot titles denote data homogeneity (§ 6). “X→Y” denotes a FedChain instantiation with X
as Alocal and Y as Aglobal, circle markers denote stepsize decay events and plusses denote switching
from Alocal to Aglobal. Across all heterogeneity levels, the multistage algorithms perform the best.
Stepsize decayed baselines are left out to simplify the plots; we display them in App. J.2.

**Theorem 4.3 (FedAvg →** **SAGA). Suppose that client objectives Fi’s and their gradient queries**
_satisfy Assumptions B.4, B.5, B.6, B.7 and B.8. Then running FedChain (Algo. 1) with Alocal as_
_FedAvg (Algo. 4 ) with the parameter choices of Thm. E.1, and Aglobal as SAGA (Algo. 5) with the_
_parameter choices of Thm. D.4, we get the following guarantees as long as R ≥_ Ω( _[N]S_ [)][:]

-  Strongly convex: If Fi’s satisfy Assumption B.1 for µ > 0, then there exists a finite K above
_which we get the rate EF_ (ˆx2) − _F_ (x[∗]) ≤ _O[˜](min{∆, ζ_ [2]/µ} exp(− min{S/N, 1/κ}R)) .

-  PL condition: If Fi’s satisfy Assumption B.3 for µ > 0, then there exists a finite K above
2
_which we get the rate EF_ (ˆx2) − _F_ (x[∗]) ≤ _O[˜](min{∆, ζ_ [2]/µ} exp(−(S/N ) 3 R/κ)) .

For the formal statement, see Thm. F.3.

**Theorem 4.4 (FedAvg →** **SSNM). Suppose that client objectives Fi’s and their gradient queries**
_satisfy Assumptions B.4, B.5, B.6 and B.8. Then running FedChain (Algo. 1) with Alocal as FedAvg_
_(Algo. 4) with the parameter choices of Thm. E.1, and Aglobal as SSNM (Algo. 6) with the parameter_
_choices of Thm. D.5, we get the following guarantees as long as R ≥_ Ω( _[N]S_ [)][:]

-  Strongly convex: If Fi’s satisfy Assumption B.1 for µ > 0, then there exists a finite
_K (same as in FedAvg →_ _SGD) above which we get the rate EF_ (ˆx2) − _F_ (x[∗]) ≤
_O˜(min{∆, ζ_ [2]/µ} exp(− min{S/N, _S/(Nκ)}R)) ._
p

For the formal statement, see Thm. F.4. SSNM (Zhou et al., 2019) is the Nesterov accelerated version
of SAGA (Defazio et al., 2014).

The main contribution of using variance reduced methods in Aglobal is the removal of the sampling error (the terms depending on the sampling heterogeneity error (1 − _S/N_ )(ζ [2]/S)) from
the convergence rates, in exchange for requiring a round complexity of at least N/S. To illustrate this, observe that in the strongly convex case, FedAvg → SGD has convergence rate
min{∆, ζ [2]/µ} exp(−R/κ)+(1−S/N )(ζ [2]/SR) and FedAvg → SAGA (FedAvg → SGD’s variancereduced counterpart) has convergence rate min{∆, ζ [2]/µ} exp(− min{1/κ, S/N _}R), dropping the_
(1 − _S/N_ )(ζ [2]/µSR) sampling heterogeneity error term in exchange for harming the rate of linear
convergence from 1/κ to min{1/κ, S/N _}._

This same tradeoff occurs in finite sum optimization (the problem minx(1/n) _i=1_ _[ψ][i][(][x][)][, where]_
_ψi’s (typically) represent losses on data points and the main concern is computation cost), which is_
what variance reduction is designed for. In finite sum optimization, variance reduction methods such

[P][n]
as SVRG (Johnson & Zhang, 2013) and SAGA (Defazio et al., 2014; Reddi et al., 2016) achieve
linear rates of convergence (given strong convexity of ψi’s) in exchange for requiring at least N/S
updates. Because we can treat FL as an instance of finite-sum optimization (by viewing Eq. (1) as a
finite sum of objectives and ζ [2] as the variance between Fi’s), these results from variance-reduced
finite sum optimization can be extended to federated learning. This is the idea behind SCAFFOLD
(Karimireddy et al., 2020b).

It is not always the case that variance reduction in Aglobal achieves better rates. In the strongly convex
case if (1 − _S/N_ )(ζ [2]/µSϵ) > N/S, then variance reduction gets gain, otherwise not.


-----

5 LOWER BOUNDS

Our lower bound allows full participation. It assumes deterministic gradients and the following class
from (Woodworth et al., 2020a; Woodworth, 2021; Carmon et al., 2020):

**Definition 5.1. For a v ∈** R[d], let supp(v) = {i ∈ [d] : vi ̸= 0}. An algorithm is distributed
_zero-respecting if for any i, k, r, the k-th iterate on the i-th client in the r-th round x[(]i,k[r][)]_ [satisfy]


supp(∇Fi′ (x[(]i[′][r],k[′][)][′] [))] (3)
_i[′]∈[N_ ],0≤k[′][≤K−1,0≤r[′]<r


supp(x[(]i,k[r][)][)][ ⊆]


supp(∇Fi(x[(]i,k[r][)][′] [))]
0≤[k[′]<k


Distributed zero-respecting algorithms’ iterates have components in coordinates that they have any
information on. As discussed in (Woodworth et al., 2020a), this means that algorithms which are not
distributed zero-respecting are just “wild guessing”. Algorithms that are distributed zero-respecting
include SGD, ASG, and FedAvg. We assume the following class of algorithms in order to bound the
heterogeneity of our construction for the lower bound proof.

**Definition 5.2. We say that an algorithm is distributed distance-conserving if for any i, k, r, we have**
for the k-th iterate on the i-th client in the r-th round x[(]i,k[r][)] [satisfies][ ∥][x]i,k[(][r][)] _[−]_ _[x][∗][∥][2][ ≤]_ [(][c/][2)[][∥][x][init][ −]

_xinitial iterate, and[∗]∥[2]_ + _i=1_ _[∥][x][init] c is some scalar parameter.[ −]_ _[x]i[∗][∥][2][]][, where][ x]j[∗]_ [:= arg min]x _[F][j][(][x][)][ and][ x][∗]_ [:= arg min]x _[F]_ [(][x][)][ and][ x][init][ is the]

[P][N]

Algorithms which do not satisfy Definition 5.2 with c at most logarithmic in problem parameters (see
§ 2) are those that move substantially far away from x[∗], even farther than the x[∗]i [’s are from][ x][∗][. With]
this definition in mind, we slightly overload the usual definition of heterogeneity for the lower bound:

**Definition** **5.3.** A distributed optimization problem is (ζ, c)-heterogeneous if
maxi [N ] supx _A_ _Fi(x)_ _F_ (x) _ζ_ [2], where we define A := _x :_ _x_ _x[∗]_
_∈_ _∈_ _∥∇_ _−∇_ _∥[2]_ _≤_ _{_ _∥_ _−_ _∥[2]_ _≤_
(c/2)( _xinit_ _x[∗]_ + _i=1_
_∥_ _−_ _∥[2]_ _[∥][x][init][ −]_ _[x][∗][∥][2][)][}][ for some scalar parameter][ c][.]_

Those achievable convergence rates in FL that assume Eq. (2) can be readily extended to account for

[P][N]

Definition 5.3 as long as the algorithm satisfies Definition 5.2. We show that the chaining algorithms
we propose satisfy Definition 5.3 in Thm. D.1, Thm. D.3, and Thm. E.1 for c at most polylogarithmic
in the problem parameters defined in § 2. [3]. Other FL algorithms also satisfy Definition 5.2, notably
FedAvg analyzed in Woodworth et al. (2020a) for c an absolute constant, which is the current tightest
known analysis of FedAvg in the full participation setting.

**Theorem 5.4. For any number of rounds R, number of local steps per-round K, and (ζ, c)-**
_heterogeneity (Definition 5.3), there exists a global objective F which is the average of two β-smooth_
_(Assumption B.4) and µ(≥_ 0)-strongly convex (Assumption B.1) quadratic client objectives F1 and
_F2 with an initial sub-optimality gap of ∆, such that the output ˆx of any distributed zero-respecting_
_(Definition 5.1) and distance-conserving algorithm (Definition 5.2) satisfies_

-  Strongly convex: F (ˆx) − _F_ (x[∗]) ≥ Ω(min{∆, 1/(cκ[3][/][2])(ζ [2]/β)} exp(−R/[√]κ).) when
_µ > 0, and_

-  General Convex F (ˆx) − _F_ (x[∗]) ≥ Ω(min{βD[2]/R[2], ζD/(c[1][/][2][√]R[5])}) when µ = 0.

**Corollary 5.5. Under the hypotheses of Theorem 5.4, there exists a global objective F which is µ-PL**
_and satisfies F_ (ˆx) − _F_ (x[∗]) ≥ Ω(min{∆, 1/(cκ[3][/][2])(ζ [2]/β)} exp(−R/[√]κ)).

A proof of the lower bound is in App. G, and the corollary follows immediately from the fact that
_µ-strong convexity implies µ-PL. This result tightens the lower bound in Woodworth et al. (2020a),_
which proves a similar lower bound but in terms of a much larger class of functions with heterogeneity
bounded in ζ∗ = (1/N ) _i=1_
can take advantage of heterogeneity require[∥∇][F][i][(][x][∗][)][∥][2][. To the best of our knowledge, all achievable rates that] (ζ, c)-heterogeneity (which is a smaller class than ζ - 
_∗_
heterogeneity), which are incomparable with the existing lower bound from (Woodworth et al., 2020a)

[P][N]
that requires ζ -heterogeneity. By introducing the class of distributed distance-conserving algorithms
_∗_

3We do not formally show it for SAGA and SSNM, as the algorithms are functionally the same as SGD and
ASG under full participation.


-----

Table 3: Test accuracies (↑). “Constant” means the stepsize does not change during optimization,
while “w/ Decay” means the stepsize decays during optimization. Left: Comparison among algorithms in the EMNIST task. Right: Comparison among algorithms in the CIFAR-100 task. “SCA.”
abbreviates SCAFFOLD.

**Algorithm** **Constant** **w/ Decay** **Algorithm** **Constant** **w/ Decay**

_Baselines_ _Baselines_

SGD 0.7842 0.7998 SGD 0.1987 0.1968
FedAvg 0.8314 0.8224 FedAvg 0.4944 0.5059
SCAFFOLD 0.8157 0.8174 SCAFFOLD – –

_FedChain_ _FedChain_

FedAvg → SGD 0.8501 0.8355 FedAvg → SGD **0.5134** **0.5167**
SCA. → SGD **0.8508** **0.8392** SCA. → SGD – –

(which includes most of the algorithms we are interested in), Thm. 5.4 allows us, for the first time, to
identify the optimality of the achievable rates as shown in Tables 1, 2, and 4.

Note that this lower bound allows full participation and should be compared to the achievable rates
with S = N ; comparisons with variance reduced methods like FedAvg → SAGA and FedAvg →
SSNM are unnecessary. Our lower bound proves that FedAvg → ASG is optimal up to condition
number factors shrinking exponentially in _κ among algorithms satisfying Definition 5.2 and_

_[√]_
Definition 5.3. Under the PL-condition, the situation is similar, except FedAvg → SGD loses _[√]κ in_
the exponential versus the lower bound. On the other hand, there remains a substantial gap between
FedAvg → ASG and the lower bound in the general convex case. Meaningful progress in closing the
gap in the general convex case is an important future direction.

6 EXPERIMENTS

We evaluate the utility of our framework on strongly convex and nonconvex settings. We compare the
communication round complexities of four baselines: FedAvg, SGD, ASG, and SCAFFOLD, the
stepsize decaying variants of these algorithms (which are prefixed by M- in plots) and the various
instantiations of FedChain (Algo. 1).

**Convex Optimization (Logistic Regression)** We first study federated regularized logistic regression, which is strongly convex (objective function in App. I.1). In this experiment, we use the MNIST
dataset of handwritten digits (LeCun et al., 2010). We (roughly) control client heterogeneity by
creating “clients” through shuffling samples across different digit classes. The details of this shuffling
process are described in App. I.1; if a dataset is more shuffled (more homogeneous), it roughly
corresponds to a lower heterogeneity dataset. All clients participate in each round.

Fig. 2 compares the convergence of chained and non-chained algorithms in the stochastic gradient
setting (minibatches are 1% of a client’s data), over R = 100 rounds (tuning details in App. I.1).
We observe that in all heterogeneity levels, FedChain instantiations (whether two or more stages)
outperform other baselines. We also observe that SCAFFOLD→SGD outperforms all other curves,
including SCAFFOLD→ASG. This can be explained by the fact that acceleration increases the effect
of noise, which can contribute to error if one does not take K large enough (we set K = 20 in the
convex experiments). The effect of large K is elaborated upon in App. J.1.

**Nonconvex Optimization (Neural Networks)** We also evaluated nonconvex image classification
tasks with convolutional neural networks. In all experiments, we consider client sampling with
_S = 10. We started with digit classification over EMNIST (Cohen et al., 2017) (tuning details in_
App. I.2.1), where handwritten characters are partitioned by author. Table 3 (Left) displays test
accuracies on the task. Overall, FedChain instantiations perform better than baselines.

We also considered image classification with ResNet-18 on CIFAR-100 (Krizhevsky, 2009) (tuning
details in App. I.2.2). Table 3 (Right) displays the test accuracies on CIFAR-100; SCAFFOLD is not
included due to memory constraints. FedChain instantiations again perform the best.


-----

ACKNOWLEDGMENTS

This work is supported by Google faculty research award, JP Morgan Chase, Siemens, the Sloan
Foundation, Intel, NSF grants CNS-2002664, CA-2040675, IIS-1929955, DMS-2134012, CCF2019844 as a part of NSF Institute for Foundations of Machine Learning (IFML), and CNS-2112471
as a part of NSF AI Institute for Future Edge Networks and Distributed Intelligence (AI-EDGE).
Most of this work was done prior to the second author joining Amazon, and it does not relate to his
current position there.

REFERENCES

Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated
learning via posterior averaging: A new perspective and practical algorithms. arXiv preprint
_arXiv:2010.05273, 2020._

Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and
optimization. arXiv preprint arXiv:1506.01900, 2015.

Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally
optimal multistage accelerated stochastic gradient method. arXiv preprint arXiv:1901.08022, 2019.

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary
points i. Mathematical Programming, 184(1):71–120, 2020.

Zachary Charles and Jakub Konecnˇ y. On the outsized importance of learning rates in local update`
methods. arXiv preprint arXiv:2007.00878, 2020.

Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On
large-cohort training for federated learning. arXiv preprint arXiv:2106.07820, 2021.

Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist
to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN), pp.
2921–2926. IEEE, 2017.

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method
with support for non-strongly convex composite objectives. Advances in neural information
_processing systems, 27, 2014._

Yuyang Deng and Mehrdad Mahdavi. Local stochastic gradient descent ascent: Convergence analysis
and communication efficiency. In International Conference on Artificial Intelligence and Statistics,
pp. 1387–1395. PMLR, 2021.

Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated
learning. arXiv preprint arXiv:2003.13461, 2020.

Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated
averaging. arXiv preprint arXiv:2102.12660, 2021.

Alireza Fallah, Asuman Ozdaglar, and Sarath Pattathil. An optimal multistage stochastic gradient
method for minimax problems. In 2020 59th IEEE Conference on Decision and Control (CDC),
pp. 3573–3579. IEEE, 2020.

Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly
convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on
_Optimization, 22(4):1469–1492, 2012._

Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex
stochastic composite optimization, ii: shrinking procedures and optimal algorithms. SIAM Journal
_on Optimization, 23(4):2061–2089, 2013._

Eduard Gorbunov, Filip Hanzely, and Peter Richtarik. Local sgd: Unified theory and new efficient´
methods. arXiv preprint arXiv:2011.02828, 2020.


-----

Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance
reduction. Advances in neural information processing systems, 26:315–323, 2013.

Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin´
Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances
and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.

Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U
Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in
federated learning. arXiv preprint arXiv:2008.03606, 2020a.

Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and
Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In
_International Conference on Machine Learning, pp. 5132–5143. PMLR, 2020b._

Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local sgd on identical´
and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp.
4519–4529. PMLR, 2020.

Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified
theory of decentralized sgd with changing topology and local updates. In International Conference
_on Machine Learning, pp. 5381–5393. PMLR, 2020._

Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, ., 2009.

Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online].
_Available: http://yann.lecun.com/exdb/mnist, 2, 2010._

Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06127, 2018.

Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy.
Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Systems,
_and Computers, pp. 1227–1231. IEEE, 2019._

Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges,
methods, and future directions. IEEE Signal Processing Magazine, 37(3):50–60, 2020.

Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don’t use large mini-batches, use
local sgd. arXiv preprint arXiv:1808.07217, 2018.

Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data. In Artificial Intelli_gence and Statistics, pp. 1273–1282. PMLR, 2017._

Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear Convergence in
Federated Learning: Tackling Client Heterogeneity and Sparse Gradients. arXiv e-prints, art.
arXiv:2102.07053, February 2021.

Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer
Science & Business Media, 2003.

Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecnˇ y,`
Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint
_arXiv:2003.00295, 2020._

Sashank J Reddi, Suvrit Sra, Barnabas P´ oczos, and Alex Smola. Fast incremental method for´
nonconvex optimization. arXiv preprint arXiv:1603.06159, 2016.

Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767,
2018.

Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of
communication-efficient sgd algorithms. arXiv preprint arXiv:1808.07576, 2018.


-----

Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime
trade-off in local-update sgd. In SysML, 2019.

Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up
decentralized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference
_(ICC), pp. 299–300. IEEE, 2019a._

Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
communication-efficient distributed sgd with slow momentum. arXiv preprint arXiv:1910.00643,
2019b.

Blake Woodworth. The minimax complexity of distributed optimization. _arXiv preprint_
_arXiv:2109.00534, 2021._

Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous
distributed learning. arXiv preprint arXiv:2006.04735, 2020a.

Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan,
Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International
_Conference on Machine Learning, pp. 10334–10343. PMLR, 2020b._

Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity
of distributed stochastic convex optimization with intermittent communication. arXiv preprint
_arXiv:2102.01583, 2021._

Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. arXiv preprint
_arXiv:2006.08950, 2020._

Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. arXiv preprint
_arXiv:2011.08474, 2020._

Kaiwen Zhou, Qinghua Ding, Fanhua Shang, James Cheng, Danli Li, and Zhi-Quan Luo. Direct
acceleration of saga using sampled negative momentum. In The 22nd International Conference on
_Artificial Intelligence and Statistics, pp. 1602–1610. PMLR, 2019._


-----

# Appendices

**A Additional Related Work** **14**

**B** **Definitions** **14**

**C Omitted Algorithm Definitions** **15**

**D Proofs for global update methods** **17**

D.1 SGD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

D.2 ASG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

D.3 SAGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

D.4 SSNM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

**E** **Proofs for local update methods** **34**

E.1 FedAvg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

**F** **Proofs for FedChain** **37**

F.1 FedAvg → SGD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

F.2 FedAvg → ASG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

F.3 FedAvg → SAGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

F.4 FedAvg → SSNM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39


**G Lower Bound** **39**

G.1 Strong convexity and smoothness of F, F1, F2 . . . . . . . . . . . . . . . . . . . . 41

G.2 The solutions of F, F1, F2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

G.3 Initial suboptimality gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

G.4 Suboptimality gap after R rounds of communication . . . . . . . . . . . . . . . . 41

G.5 Computation of ζ [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

G.6 Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

**H Technical Lemmas** **44**

**I** **Experimental Setup Details** **47**

I.1 Convex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

I.2 Nonconvex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

**J** **Additional Convex Experiments** **48**

J.1 Verifying the effect of increased K and R = 1 . . . . . . . . . . . . . . . . . . . . 48

J.2 Including Stepsize Decay Baselines . . . . . . . . . . . . . . . . . . . . . . . . . 49


-----

Table 4: Rates under the PL condition. _[♣]_ Rate requires R ≥ _[N]S_ [.]

**Method/Analysis** EF (ˆx) − _F_ (x[∗]) ≤ _O[˜](·)_

_Centralized Algorithms_

SGD ∆exp( _κ[−][1]R) + (1_ _N_ [)][ κζ]µSR[2]
_−_ _−_ _[S]_

_Federated Algorithms_

FedAvg (Karimireddy et al., 2020a) _κ∆exp(_ _κ[−][1]R) +_ _[κ]µR[2][ζ][2][2]_
_−_

_This paper_


min ∆, _[ζ]µ[2]_ _N_ [)][ κζ]µSR[2]

minmin{{{∆∆, κ, _[ζ]µ[2][−][}][}]2[3][ exp(][ exp(] (_ _[ζ]β[2]_ [)][−][−][}][ exp(][κ][((][−][ N]S[1][R][)][−]23[) + (1] κ[κ][−])[−][1]2 R[1]R[ −]))[♣][S]


FedAvg → SGD (Thm. 4.1)

FedAvg → SAGA (Thm. 4.3)

Algo.-independent LB (Corollary 5.5)


A ADDITIONAL RELATED WORK

**Multistage algorithms. Our chaining framework has similarities in analysis to multistage algorithms**
which have been employed in the classical convex optimization setting (Aybat et al., 2019; Fallah
et al., 2020; Ghadimi & Lan, 2012; Woodworth et al., 2020a). The idea behind multistage algorithms
is to manage stepsize decay to balance fast progress in “bias” error terms while controlling variance
error. However chaining differs from multistage algorithms in a few ways: (1) We do not necessarily
decay stepsize (2) In the heterogeneous FL setting, we have to accomodate error due to client drift
(Reddi et al., 2020; Karimireddy et al., 2020b), which is not analyzed in prior multistage literature.
(3) Our goal is to minimize commuincation rounds rather than iteration complexity.

B DEFINITIONS

**Assumption B.1. Fi’s are µ-strongly convex for µ > 0, i.e.**

_Fi(x), y_ _x_ (Fi(x) _Fi(y) +_ _[µ]_ (4)
_⟨∇_ _−_ _⟩≤−_ _−_ 2 _[∥][x][ −]_ _[y][∥][2][)]_

for any i, x, y.
**Assumption B.2. Fi’s are general convex, i.e.**

_Fi(x), y_ _x_ (Fi(x) _Fi(y))_ (5)
_⟨∇_ _−_ _⟩≤−_ _−_

for any i, x, y.
**Assumption B.3. F is µ-PL for µ > 0, i.e.**

2µ(F (x) − _F_ (x[∗])) ≤∥∇F (x)∥[2] (6)

for any x.
**Assumption B.4. Fi’s are β-smooth where**

_Fi(x)_ _Fi(y)_ _β_ _x_ _y_ (7)
_∥∇_ _−∇_ _∥≤_ _∥_ _−_ _∥_

for any i, x, y.
**Assumption B.5. Fi’s are ζ** [2]-heterogeneous, defined as

_ζ_ [2] := sup (8)
_x_ _i[max][N_ ]
_∈_ _[∥∇][F]_ [(][x][)][ −∇][F][i][(][x][)][∥][2]

**Assumption B.6. Gradient queries within a client have a uniform upper bound on variance and are**
also unbiased.

Ezi _i_ _f_ (x; zi) _Fi(x)_ _σ[2],_ Ezi _i_ [ _f_ (x; zi)] = _Fi(x)_ (9)
_∼D_ _∥∇_ _−∇_ _∥[2]_ _≤_ _∼D_ _∇_ _∇_

**Assumption B.7. Cost queries within a client have a uniform upper bound on variance and are also**
unbiased.

Ezi _i_ (f (x; zi) _Fi(x))[2]_ _σF[2]_ _[,]_ Ezi _i_ _f_ (x; zi) = Fi(x) (10)
_∼D_ _−_ _≤_ _∼D_


-----

**Assumption B.8. Cost queries within a client have an absolute deviation.**

_ζF[2]_ [= sup] (11)
_x_ _i[max][N_ ][(][F] [(][x][)][ −] _[F][i][(][x][))][2]_
_∈_

**Assumption B.9. The initial suboptimality gap is upper bounded by ∆, where x0 is the initial**
feasible iterate and x[∗] is the global minimizer.

EF (x0) − _F_ (x[∗]) ≤ ∆ (12)

**Assumption B.10. The expected initial distance from the optimum is upper bounded by D, where**
_x0 is the initial feasible iterate and x[∗]_ is one of the global minimizers:

E∥x0 − _x[∗]∥[2]_ _≤_ _D[2]_ (13)

C OMITTED ALGORITHM DEFINITIONS

**Algorithm 2 SGD**

**Input: initial point x[(0)], stepsize η, loss f**
**for r = 0, . . ., R −** 1 do

_▷_ **Run a step of SGD**
Sample S clients _r_ [1, . . ., N ]
_S_ _⊆_
**Send x[(][r][)]** to all clients in Sr
**Receive** _gi[(][r][)]_ _i_ _r = Grad(x[(][r][)],_ _r, z[(][r][)]) (Algo. 7)_
_{_ _}_ _∈S_ _S_

_g[(][r][)]_ = _S[1]_ _i_ _r_ _[g]i[(][r][)]_

_∈S_

_x[(][r][+1)]_ = x[(][r][)] _η_ _g[(][r][)]_

P _−_ _·_

**end for**


**Algorithm 3 ASG**

**Input: initial point x[(0)]** = x[(0)]ag [,][ {][α]r[}]1 _r_ _R[,][ {][γ]r[}]1_ _r_ _R[, loss][ f]_
_≤_ _≤_ _≤_ _≤_

**for r = 1, . . ., R do**

_▷_ **Run a step of ASG**
Sample S clients _r_ [1, . . ., N ]
_S_ _⊆_
**Send x[(][r][)]** to all clients in Sr
_x[(]md[r][)]_ [=][ (1]γ[−]r+(1[α][r][)(]−[µ]α[+][2]r[γ][)][µ][r][ x][)] ag[(][r][−][1)] + _[α][r]γ[[(1]r+(1[−][α]−[r][)]α[µ][2]r[+][)][µ][γ][r][]]_ _x[(][r][−][1)]_

**Receive {gi[(][r][)]}i∈Sr = Grad(x[(]md[r][)][,][ S][r][, z][(][r][)][)][ (Algo. 7)]**

_g[(][r][)]_ = _S[1]_ _i_ _r_ _[g]i[(][r][)]_

_∈S_

_x[(][r][)]_ = arg minP _x{αr[⟨g[(][r][)], x⟩_ + _[µ]2_ _[∥][x]md[(][r][)]_ _[−]_ _[x][∥][2][] + [(1][ −]_ _[α][r][)][ µ]2_ [+][ γ]2[r] _[∥][x][(][r][−][1)][ −]_ _[x][∥][2][]][}]_

_x[(]ag[r][)]_ [=][ α]r[x][(][r][)][ + (1][ −] _[α]r[)][x][(]ag[r][−][1)]_

**end for**


-----

**Algorithm 4 FedAvg**

**Input: Stepsize η, initial point x[(0)]**
**for r = 0, . . ., R −** 1 do

Sample S clients _r_ [1, . . ., N ]
_S_ _⊆_
**Send x[(][r][)]** to all clients in Sr, all clients set x[(]i,[r]0[)] [=][ x][(][r][)]

**for client i ∈Sr in parallel do**

**forClient samples k = 0, ...,** _√ gKi,k[(] −[r][)]_ [=]1 do√1K _k[′]K=0−1_ _f_ (x[(]i,k[r][)][;][ z]i,k[(][r][)]

_∇_

_x[(]i,k[r][)]+1_ [=][ x][(]i,k[r][)] _[−]_ _[η][ ·][ g]i,k[(][r][)]_ P[√]

**end for**
**Receive gi[(][r][)]** = _k=0K−1_ _gi,k[(][r][)]_ [from client]

**end for**
_g[(][r][)]_ = _S[1]_ _i_ _r_ _[g]i[(][P][r][)]_ _[√]_

_∈S_

_x[(][r][+1)]_ _x[(][r][)]_ _η_ _g[(][r][)]_
_←P_ _−_ _·_

**end for**


_K+k[′]_ [)][ where][ z]i,k[(][r][)]


_K+k[′][ ∼D][i]_


**Algorithm 5 SAGA**

**Input: stepsize η, loss f**, initial point x[(0)]

**Send φ[(0)]i** = x[(0)] to all clients i

**forReceive r = 0 c, . . ., R[(0)]i** = _K[1] −P1 doKk=0−1_ _[∇][f]_ [(][φ]i[(0)][;][ z]i,k[(][−][1)][)][,][ z]i,k[(][−][1)] _∼Di from all clients, c[(0)]_ = _N[1]_ PNi=1 _[c]i[(0)]_

Sample S clients _r_ [1, . . ., N ]
_S_ _⊆_
**Send x[(][r][)]** to all clients in _r, Receive_ _gi[(][r][)]_ _i_ _r = Grad(x[(][r][)],_ _r, z[(][r][)]) (Algo. 7)_
_S_ _{_ _}_ _∈S_ _S_

_g[(][r][)]_ = _S[1]_ _i∈Sr_ _[g]i[(][r][)]_ _−_ _S[1]_ _i∈Sr_ _[c]i[(][r][)]_ + c[(][r][)]

_x[(][r][+1)]_ = x[(][r][)] _η_ _g[(][r][)]_

P _−_ _·_ P

**Option I: Set c[(]i[r][+1)]** = gi[(][r][)], φ[(]i[r][+1)] = x[(][r][)] for i _r_
_∈S_

**Option II: New independent sample of clients Sr[′]** [,][ send][ x][(][r][)][ to all clients in][ S]r[′] [,][ receive]

_{g˜i[(][r][)]}i∈Sr′_ [=][ Grad][(][x][(][r][)][,][ S]r[′] _[,][ ˜]z[(][r][)]), set c[(]i[r][+1)]_ = ˜gi[(][r][)], φ[(]i[r][+1)] = x[(][r][)] for i ∈Sr[′]


_c[(]i[r][+1)]_ = c[(]i[r][)] and φ[(]i[r][+1)] = φ[(]i[r][)] for any i not yet updated

_c[(][r][+1)]_ = _N[1]_ _Ni=1_ _[c]i[(][r][+1)]_

**end for**

P


-----

**Algorithm 6 SSNM**

**Input: stepsize η, momentum τ**, client losses are Fi(x) = Ezi _i_ [f (x; zi)]+h(x) = F[˜]i(x)+h(x)
_∼D_
where _F[˜]i can be general convex and h(x) is µ-strongly convex, initial point x[(0)]_

**Send φ[(0)]i** = x[(0)] to all clients i

**forReceive r = 0 c, . . ., R[(0)]i** = _K[1] −P1 doKk=0−1_ _[∇][f]_ [(][φ]i[(0)][;][ z]i,k[(][−][1)][)][,][ z]i,k[(][−][1)] _∼Di from all clients c[(0)]_ = _N[1]_ PNi=1 _[c]i[(0)]_

Sample S clients _r_ [1, . . ., N ]
_S_ _⊆_
**SendReceive x[(][r] g[)]i[(]to all clients inr[r][)]** [=][ 1]K _Kk=0−1 S[∇]r[f], y[(][y]i[(]r[r]i[(]r[)][r][)][=][;][ z][ τx]i[(]r[r],k[)][(][)][r][ for][)][ + (1][ i][r][ ∈S][ −]_ _[τ]_ [)][r][φ][,][ z]i[(]r[r]i[(][)]r[r],k[)][for][∼D][ i][r][ ∈S][i] _[r]_

_g[(][r][)]_ = _S[1]_ _ir_ _r_ _[g]Pi[(]r[r][)]_ _S_ _ir_ _r_ _[c]i[(]r[r][)]_ [+][ c][(][r][)]

_x[(][r][+1)]_ = arg min∈S _x_ _h([−]x) +[1]_ _g[(][r]∈S[)], x_ + 21η _[∥][x][(][r][)][ −]_ _[x][∥][2][}]_

P _{_ P ⟨ _⟩_

Sample new independent sample of S clients _r_
_S_ _[′]_ _[⊆]_ [[1][, . . ., N] []]

**SendReceive x[(][r] g[)]I[(]to all clients in[r]r[)]** [=][ 1]K _Kk=0−1 S[∇]r[′][f][,][ φ][(][φ][(]I[r]rI[(][+1)][r]r[+1)]=; ˜z τxI[(]r[r][)],k[(][r][)][+1)][ for][ I]+ (1[r][ ∈S] −r[′]τ[,][ ˜])zφI[(]r[r][(]I[r][)],kr[)]_ [for][∼D][ I][r][i][ ∈S]r[′]

_c[(]i[r][+1)]_ = gI[(][r]r[)] [for][ I][r]P[ ∈S]r[′]

_c[(]i[r][+1)]_ = c[(]i[r][)] and φ[(]i[r][+1)] = φ[(]i[r][)] for any i not yet updated

_c[(][r][+1)]_ = _N[1]_ _Ni=1_ _[c]i[(][r][+1)]_

**end for**

P


**Algorithm 7 Grad(x, S, z)**

**for client i ∈S in parallel do**

Client samples gi,k[(][r][)] [=][ ∇][f] [(][x][(][r][)][;][ z]i,k[(][r][)][)][ where][ z]i,k[(][r][)]

_K_ 1 _[∼D][i][,][ k][ ∈{][0][, . . ., K][ −]_ [1][}]

_gi[(][r][)]_ = _K[1]_ _k=0−_ _[g]i,k[(][r][)]_

**end for**

P

**return {gi[(][r][)]}i∈Sr**

D PROOFS FOR GLOBAL UPDATE METHODS

D.1 SGD

**Theorem D.1. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4**
_and Assumption B.6. Then running Algo. 2 gives the following for returned iterate ˆx:_



-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. If we return ˆx = _W1R_ _Rr=0_ _[w][r][x][(][r][)]_

_with wr = (1 −_ _ηµ)[1][−][(][r][+1)]_ _and WR =_ _r=0_ _[w][r][,][ η][ = ˜]O(min{_ _β[1]_ _[,]_ _µR1_ _[}][)][, and]P[ R > κ][,]_

_σ[2]_

EF (ˆx) _F_ (x[∗]) (∆exp([P][R]
_−_ _≤_ _O[˜]_ _−_ _[R]κ_ [) +] _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]

E∥x[(][r][)] _−_ _x[∗]∥[2]_ _≤_ _O[˜](D[2]) for any 0 ≤_ _r ≤_ _R_



-  General convex (grad norm): Fi’s satisfy Assumption B.2. If we return the average iterate
_xˆ =_ _R[1]_ _Rr=1_ _[x][(][r][)][, and][ η][ = min][{][ 1]β_ _[,][ (][ ∆]βcR_ [)][1][/][2][}][ where][ c][ is the update variance]

P

_βσD_ _βζD_

E∥∇F (ˆx)∥[2] _≤_ _O[˜](_ _[β]R[∆]_ [+] _√SKR_ + 1 − _N[S]_ _√SR_ )

r

E∥x[(][r][)] _−_ _x[∗]∥[2]_ _≤O(D[2]) for any 0 ≤_ _r ≤_ _R_


-----

-  PL condition: Fi’s satisfy Assumption B.3. If we return the final iterate ˆx = x[(][R][)], set
_η = O[˜](min{_ _β[1]_ _[,]_ _µR1_ _[}][)][, then]_

_κσ[2]_

EF (x[(][R][)]) _F_ (x[∗]) (∆exp(
_−_ _≤_ _O[˜]_ _−_ _[R]κ_ [) +] _µSKR_ [+ (1][ −] _N[S]_ [)][ κζ]µSR[2] [)]


**Lemma D.2 (Update variance). For SGD, we have that**

Er _g[(][r][)]_ _F_ (x[(][r][)]) + _[σ][2]_
_∥_ _∥[2]_ _≤∥∇_ _∥[2]_ _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_

_−_


(14)


_Proof. Observing that_

Er∥g[(][r][)]∥[2] = Er∥g[(][r][)] _−∇F_ (x[(][r][)])∥[2] + ∥∇F (x[(][r][)])∥[2] (15)

and using Lemma H.1, we have


Er _g[(][r][)]_ _F_ (x[(][r][)])
_∥_ _−∇_ _∥[2]_ _≤_ _SK[σ][2]_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_

_−_

D.1.1 CONVERGENCE OF SGD FOR STRONGLY CONVEX FUNCTIONS

_Proof. Using the update of SGD,_


(16)


_∥x[(][r][+1)]_ _−_ _x[∗]∥[2]_ _≤∥x[(][r][)]_ _−_ _x[∗]∥[2]_ _−_ 2η⟨g[(][r][)], x[(][r][)] _−_ _x[∗]⟩_ + η[2]∥g[(][r][)]∥[2] (17)

Taking expectation up to the r-th round

Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ _≤∥x[(][r][)]_ _−_ _x[∗]∥[2]_ _−_ 2η⟨∇F (x[(][r][)]), x[(][r][)] _−_ _x[∗]⟩_ + η[2]Er∥g[(][r][)]∥[2] (18)

By Assumption B.1,

_−2η⟨∇F_ (x[(][r][)]), x[(][r][)] _−_ _x[∗]⟩≤−2η(F_ (x[(][r][)]) − _F_ (x[∗])) − _ηµ∥x[(][r][)]_ _−_ _x[∗]∥[2]_ (19)

Using Lemma D.2, Assumption B.4, and setting η ≤ 21β [,]

Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (20)

(1 _ηµ)_ _x[(][r][)]_ _x[∗]_ _η(F_ (x[(][r][)]) _F_ (x[∗])) + η[2]( _[σ][2]_ (21)
_≤_ _−_ _∥_ _−_ _∥[2]_ _−_ _−_ _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Rearranging and taking full expectation,

EF (x[(][r][)]) _F_ (x[∗]) + η( _[σ][2]_
_−_ _≤_ [(1][ −] _[ηµ][)][E][∥][x][(][r][)][ −]_ _[x][∗]η[∥][2][ −]_ [E][∥][x][(][r][+1)][ −] _[x][∗][∥][2]_ _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

(22)

letting wr = (1 _µη)[1][−][(][r][+1)], WR =_ _r=0[,][ ˆ]x =_ _W1R_ _Rr=0_ _[x][(][r][)][, then]_
_−_

P

EF (ˆx) _F_ (x[∗]) [P][R] + η( _[σ][2]_ (23)
_−_ _≤_ [E][∥][x][(0)]ηW[ −]R[x][∗][∥][2] _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

From (Karimireddy et al., 2020b) Lemma 1, if R > κ and η = min{ 2[1]β _[,][ log(max(1]µR[,µ][2][RD][2][/c][))]_ _} where_

_σ[2]_
_c =_ _NK_ [+ (1][ −] _N[S][−][1]1_ [)][ ζ]S[2] [,]

_−_

_σ[2]_

EF (ˆx) _F_ (x[∗]) (∆exp( (24)
_−_ _≤_ _O[˜]_ _−_ _[R]κ_ [) +] _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]

Which finishes our work on the convergence rate. Next we consider the distance bound. Returning to
the recurrence

Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (25)

(1 _ηµ)_ _x[(][r][)]_ _x[∗]_ _η(F_ (x[(][r][)]) _F_ (x[∗])) + η[2]( _[σ][2]_ (26)
_≤_ _−_ _∥_ _−_ _∥[2]_ _−_ _−_ _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_


-----

Taking full expectation and unrolling,

E∥x[(][r][)] _−_ _x[∗]∥[2]_ (27)

E _x[(0)]_ _x[∗]_ exp( _ηµr) +_ _[η]_ (28)
_≤_ _∥_ _−_ _∥[2]_ _−_ _µ_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Note that Karimireddy et al. (2020b) chose η so that η( _SK[σ][2]_ [+ (1][ −] _N[S][−]−[1]1_ [)][ ζ]S[2] [)][ ≤] _O[˜](µD[2]_ exp(−µηR))

And so

E∥x[(][r][)] _−_ _x[∗]∥[2]_ _≤_ _O[˜](D[2])_ (29)

D.1.2 CONVERGENCE OF SGD FOR GENERAL CONVEX FUNCTIONS

_Proof. By smoothness (Assumption B.4), we have that_

_F_ (x[(][r][+1)]) _F_ (x[(][r][)]) _η_ _F_ (x[(][r][)]), g[(][r][)] + _[βη][2]_ (30)
_−_ _≤−_ _⟨∇_ _⟩_ 2 _[∥][g][(][r][)][∥][2]_

Taking expectation conditioned up to r and using Lemma D.2,

ErF (x[(][r][+1)]) − _F_ (x[(][r][)]) ≤−(η − _[βη]2 [2]_ [)][∥∇][F] [(][x][(][r][)][)][∥][2][ +][ βη]2 [2] [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)] (31)

_−_

If η ≤ _β[1]_ [,]

ErF (x[(][r][+1)]) _F_ (x[(][r][)]) (32)
_−_ _≤−_ _[η]2_ _[∥∇][F]_ [(][x][(][r][)][)][∥][2][ +][ βη]2 [2] [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Taking full expectation and rearranging,

1

+ _[βη]_ (33)

2 [E][∥∇][F] [(][x][(][r][)][)][∥][2][ ≤] [E][F] [(][x][(][r][+1)][)]η[ −] [E][F] [(][x][(][r][)][)] 2 [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Summing both sides over r and averaging,


1 1 _R−1_

E _F_ (x[(][r][)]) + _[βη]_ (34)

2 _R_ _∥∇_ _∥[2]_ _≤_ [E][F] [(][x][(0)][)][ −]ηR[E][F] [(][x][(][R][)][)] 2 [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_r=0_

_−_

X

Lettingchoosing ˆx η be an average of all the = min{ _β[1]_ _[,][ (][ ∆]βcR_ [)][1][/][2][}][ where] x[(][r][)]’s, noting that[ c][ =] _SKσ[2]_ [+ (1] E[ −]F (N[S]x[−]−[(0)][1]1 [)])[ ζ] −S[2] [,] EF (x[(][R][)]) ≤ ∆, ∆ _≤_ _βD[2], and_


_βσD_

E∥∇F (ˆx)∥[2] _≤_ _O[˜](_ _[β]R[∆]_ [+] _√SKR_


1
_−_ _N[S]_


_βζD_
_√SR_ ) (35)


So we have our convergence rate. Next, for the distance bound,

_∥x[(][r][+1)]_ _−_ _x[∗]∥[2]_ = ∥x[(][r][)] _−_ _x[∗]∥[2]_ _−_ 2η⟨g[(][r][)], x[(][r][)] _−_ _x[∗]⟩_ + η[2]∥g[(][r][)]∥[2] (36)

Taking expectation up to r, we know from Lemma D.2,


Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (37)

_x[(][r][)]_ _x[∗]_ 2η _g[(][r][)], x[(][r][)]_ _x[∗]_ + η[2] _F_ (x[(][r][)]) + η[2]( _[σ][2]_ (38)
_≤∥_ _−_ _∥[2]_ _−_ _⟨_ _−_ _⟩_ _∥∇_ _∥[2]_ _SK_ [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


By Assumption B.2 and Assumption B.4,

Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (39)

_x[(][r][)]_ _x[∗]_ 2η(1 _βη)(F_ (x[(][r][)]) _F_ (x[∗])) + η[2]( _[σ][2]_ (40)
_≤∥_ _−_ _∥[2]_ _−_ _−_ _−_ _SK_ [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


-----

And with η ≤ _β[1]_ [,]


Er _x[(][r][+1)]_ _x[∗]_ _x[(][r][)]_ _x[∗]_ + η[2]( _[σ][2]_ (41)
_∥_ _−_ _∥[2]_ _≤∥_ _−_ _∥[2]_ _SK_ [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


Unrolling and taking full expectation,

E _x[(][r][)]_ _x[∗]_ E _x[(0)]_ _x[∗]_ + η[2]R( _[σ][2]_ (42)
_∥_ _−_ _∥[2]_ _≤_ _∥_ _−_ _∥[2]_ _SK_ [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


We chose η so that βη( _SK[σ][2]_ [+ (1][ −] _N[S]_ [)][ ζ]S[2] [)][ ≤]


∆

_ηR_ [. Therefore]


E _x[(][r][)]_ _x[∗]_ E _x[(0)]_ _x[∗]_ + [∆] (43)
_∥_ _−_ _∥[2]_ _≤_ _∥_ _−_ _∥[2]_ _β_ _[≤]_ [2][D][2]

D.1.3 CONVERGENCE OF SGD UNDER THE PL-CONDITION

_Proof. Using Assumption B.4 we have that_


_F_ (x[(][r][+1)]) _F_ (x[(][r][)]) _η_ _F_ (x[(][r][)]), g[(][r][)] + _[βη][2]_ (44)
_−_ _≤−_ _⟨∇_ _⟩_ 2 _[∥][g][(][r][)][∥][2]_

Taking expectations of both sides conditioned on the r-th step,

ErF (x[(][r][+1)]) _F_ (x[(][r][)]) _η_ _F_ (x[(][r][)]) + _[βη][2]_ (45)
_−_ _≤−_ _∥_ _∥[2]_ 2 [E][r][∥][g][(][r][)][∥][2]


Using Lemma D.2,

ErF (x[(][r][+1)]) _F_ (x[(][r][)]) (46)
_−_ _≤−_ _[η]2_ _[∥][F]_ [(][x][(][r][)][)][∥][2][ +][ βη]2 [2] [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Using Assumption B.3, we have that

ErF (x[(][r][+1)]) − _F_ (x[(][r][)]) ≤−ηµ(F (x[(][r][)]) − _F_ (x[∗])) + _[βη]2 [2]_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)] (47)

_−_

Rearranging,

ErF (x[(][r][+1)]) − _F_ (x[∗]) ≤ (1 − _ηµ)(F_ (x[(][r][)]) − _F_ (x[∗])) + _[βη]2 [2]_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)] (48)

_−_

_σ[2]_
Letting c = _SK_ [+ (1][ −] _N[S][−][1]1_ [)][ ζ]S[2] [and subtracting][ βcη]2µ [from both sides,]

_−_

ErF (x[(][r][+1)]) _F_ (x[∗]) (49)
_−_ _−_ _[βcη]2µ_ 2µ [)]

_[≤]_ [(1][ −] _[ηµ][)(][F]_ [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)][ −] _[βcη]_

Which, upon unrolling the recursion, gives us


EF (x[(][R][)]) _F_ (x[∗]) ∆exp( _ηµR) +_ _[βcη]_ (50)
_−_ _≤_ _−_ 2µ

Now, if we choose stepsize


log(max _e,_ _[µ][2]βc[∆][R]_

_η = min_ [1] _{_ _[}][)]_ (51)
_{_ _β [,]_ _µR_ _}_

Then the final convergence rate is


_κσ[2]_

EF (x[(][R][)]) _F_ (x[∗]) (∆exp( (52)
_−_ _≤_ _O[˜]_ _−_ _[R]κ_ [) +] _µSKR_ [+ (1][ −] _N[S]_ [)][ κζ]µSR[2] [)]


-----

D.2 ASG

The precise form of accelerated stochastic gradient we run is AC-SA(Ghadimi & Lan, 2012; 2013).
The following specification is taken from Woodworth et al. (2020a):

We run Algo. 3 for Rs iterations using x[(0)] = ps 1, _αt_ _t_ 1 and _γt_ _t_ 1, with definitions
_−_ _{_ _}_ _≥_ _{_ _}_ _≥_



-  Rs = ⌈max{4


_⌈max{4_ 4µβ _[,]_ 3µ∆2128[−][(]c[s][+1)][ }⌉]

2 q 4φs

_r+1_ [,][ γ][r][ =] _r(r+1)_ [,]



-  αr =



-  φs = max 2β, [ 3∆2[−][(][s][−][1)]Rsµc(Rs+1)(Rs+2) []][1][/][2][}]
_{_


_σ[2]_
Where c = _SK_ [+ (1][ −] _N[S][−][1]1_ [)][ ζ]S[2] [. Set][ p][s][ =][ x][(]ag[R][s][)] where x[(]ag[R][s][)] is the solution obtained in the previous

_−_

step.
**Theorem D.3. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4**
_and Assumption B.6. Then running Algo. 3 gives the following for returned iterate ˆx:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. If we return ˆx = x[(]ag[R][s][)] _after R_
_rounds of the multistage AC-SA specified above,_


_σ[2]_
EF (ˆx) − _F_ (x[∗]) ≤O(∆exp(− _√[R]κ_ ) + _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]


_σ[2]_ _ζ_ [2]
E∥xˆ − _x[∗]∥[2]_ _≤O(κE∥x[(0)]_ _−_ _x[∗]∥[2]_ exp(− _√[R]κ_ ) + _µ[2]SKR_ [+ (1][ −] _N[S]_ [)] _µ[2]SR_ [)]

_And given no randomness, for any 0 ≤_ _r ≤_ _R_

_∥x[(][r][)]_ _−_ _x[∗]∥[2]_ _≤∥x[(0)]_ _−_ _x[∗]∥[2]_


_x[(]ag[r][)]_
_∥_ _[−]_ _[x][∗][∥][2][ ≤∥][x][(0)][ −]_ _[x][∗][∥][2]_

_x[(]md[r][)]_
_∥_ _[−]_ _[x][∗][∥][2][ ≤∥][x][(0)][ −]_ _[x][∗][∥][2]_


_and for any 1 ≤_ _r ≤_ _R_



-  General convex (grad norm): Fi’s satisfy Assumption B.2. If we return ˆx = x[(]ag[R][s][)] _after_
_R rounds of the multistage AC-SA specified above on the regularized objective Fµ(x) =_


_F_ (x) + _[µ]2_ _[∥][x][(0)][ −]_ _[x][∥][2][ with][ µ][ = max][{][ 2]R[β][2][ log][2][(][e][2][ +][ R][2][)][,]_


(1−∆N[S]SR[)][βζ][2] _, we have_

_}_


_βσ[2]_

∆SKR _[,]_


_σ[2]_ _βσD_

E∥∇F (ˆx)∥[2] _≤_ _O[˜](_ _[β]R[∆][2][ +]_ _SKR_ [+ (1][ −] _N[S]_ [)][ ζ]SR[2] [+] _√SKR_


1
_−_ _N[S]_


_ζD_
_√SR_


E∥xˆ − _x[∗]∥[2]_ _≤_ _O[˜](D[2])_

D.2.1 CONVERGENCE OF ASG FOR STRONGLY CONVEX FUNCTIONS

_Proof. The convergence rate proof comes from Woodworth et al. (2020a) Lemma 5. What remains is_
to show the distance bound.

From Proposition 5, (Eq. 3.25, 4.25) of Ghadimi & Lan (2012), we have that the generic (nonmultistage) AC-SA satisfies (together with Lemma H.1)

EF (x[(]ag[r][)][) +][ µ][E][∥][x][(][r][)][ −] _[x][∗][∥][2][ −]_ _[F]_ [(][x][)] (53)

_r_

_γτ_ 4r

Γr [E _x[(][τ]_ _[−][1)]_ _x[∗]_ E _x[(][τ]_ [)] _x[∗]_ ] + Γr (54)
_≤_ Γτ _∥_ _−_ _∥[2]_ _−_ _∥_ _−_ _∥[2]_ _µ_ [(][ σ]SK[2] [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]

_τ_ =1

X


-----

1, r = 1
Where Γr = Notice that
(1 _αr)Γr_ 1 r 2
 _−_ _−_ _≥_


_γτ_

[E _x[(][τ]_ _[−][1)]_ _x[∗]_ E _x[(][τ]_ [)] _x[∗]_ ] = Γtγ1[ _x[(0)]_ _x[∗]_ _x[(][r][)]_ _x[∗]_ ] (55)
Γτ _∥_ _−_ _∥[2]_ _−_ _∥_ _−_ _∥[2]_ _∥_ _−_ _∥[2]_ _−∥_ _−_ _∥[2]_


Γr


_τ_ =1


So


4r
(µ + Γtγ1)E _x[(][r][)]_ _x[∗]_ Γtγ1E _x[(0)]_ _x[∗]_ + Γr (56)
_∥_ _−_ _∥[2]_ _≤_ _∥_ _−_ _∥[2]_ _µ_ [(][ σ]SK[2] [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]

Which implies


4r
E _x[(][r][)]_ _x[∗]_ E _x[(0)]_ _x[∗]_ + Γr (57)
_∥_ _−_ _∥[2]_ _≤_ _∥_ _−_ _∥[2]_ _µ[2][ (][ σ]SK[2]_ [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


Furthermore, Γr =


2

_r(r+1)_ [so]


8

(58)

_µ[2](r + 1)_ [(][ σ]SK[2] [+ (1][ −] _N[S]_ [)] _[ζ]S[2]_ [)]


E∥x[(][r][)] _−_ _x[∗]∥[2]_ _≤_ E∥x[(0)] _−_ _x[∗]∥[2]_ +

If there is no gradient variance or sampling,


_∥x[(][r][)]_ _−_ _x[∗]∥[2]_ _≤∥x[(0)]_ _−_ _x[∗]∥[2]_ (59)

Next, we show the above two conclusions hold for x[(]md[r][)] [and][ x]ag[(][r][)][.]

For x[(]ag[r][)][, we show by induction:]

**Base case: x[(]ag[r][)]** [=][ x][(0)][, so it is true]

**Inductive case: x[(]ag[r][)]** [is a convex combination of][ x][(][r][)][ and][ x][(]ag[r][−][1)], so the above statements hold for
_x[(]ag[r][)]_ [as well.]

For x[(]md[r][)][, note it is a convex combination of][ x][(]ag[r][−][1)] and x[(][r][−][1)], so the above statements on distance
also hold for x[(]md[r][)][.]

For the distance bound on the returned solution, use strong convexity on the convergence rate:


E∥xˆ − _x[∗]∥[2]_ _≤O(κE∥x[(0)]_ _−_ _x[∗]∥[2]_ exp(− _√[R]κ_ ) +


_c_

(60)
_µ[2]R_ [)]


D.2.2 CONVERGENCE OF ASG FOR GENERAL CONVEX FUNCTIONS

For the general convex case, we use Nesterov smoothing. Concretely, we will run Algo. 3 assuming
strong convexity by optimizing instead a modified objective

_Fµ(x) = F_ (x) + _[µ]_ (61)

2

_[∥][x][(0)][ −]_ _[x][∥][2]_

Define x[∗]µ [= arg min]x _[F][µ][(][x][)][ and][ ∆][µ]_ [=][ E][F][µ][(][x][(0)][)][ −] _[F]_ [(][x][∗]µ[)][. We will choose][ µ][ carefully to balance]
the error introduced by the regularization term and the better convergence properties of having larger
_µ._

_Proof. Observe that_


E∥∇F (ˆx)∥[2] = E∥∇Fµ(ˆx) − _µ(ˆx −_ _x[(0)])∥[2]_ _≤_ 2E∥∇Fµ(ˆx)∥[2] + 2µ[2]E∥xˆ − _x[(0)]∥[2]_ (62)

We evaluate the second term first. We know that from the theorem statement on strongly convex
functions and letting κ[′] = _[β][+]µ[µ]_ and κ = _[β]µ_ [because][ F][ is now][ β][ +][ µ][-smooth,]

_σ[2]_

EFµ(ˆx) _Fµ(x[∗]µ[)][ ≤O][((][E][F][µ][(][x][(0)][)][ −]_ _[F][µ][(][x][∗]µ[)) exp(][−]_ _[R]_
_−_ _√κ[′][ ) +]_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)][ (63)]


-----

Which implies

So it is true that

If we rearrange,


_σ[2]_
EFµ(ˆx) (EFµ(x[(0)]) + (64)
_≤O_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]

_σ[2]_
= (EF (x[(0)]) + (65)
_O_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]


EFµ(ˆx) = E[F (ˆx) + _[µ]_ _x_ _x[(0)]_ ] (66)

2 _[∥][ˆ] −_ _∥[2]_

_σ[2]_
= (EF (x[(0)]) + (67)
_O_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]


_µ_ _σ[2]_

_x_ _x[(0)]_ (EF (x[(0)]) _F_ (ˆx) + (68)
2 [E][∥][ˆ] − _∥[2]_ _≤O_ _−_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]


_σ[2]_
(EF (x[(0)]) _F_ (x[∗]) + (69)
_≤O_ _−_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]

_σ[2]_
(∆+ (70)
_≤O_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]

Next we evaluate 2E∥∇Fµ(ˆx)∥[2]. Observe that the smoothness of Fµ is β + µ. Returning to the
convergence rate,


_σ[2]_

EFµ(ˆx) _Fµ(x[∗]µ[)][ ≤O][(∆][µ]_ [exp(][−] _[R]_ (71)
_−_ _√κ[′][ ) +]_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)]


We have that

_Fµ(x[(0)])_ _Fµ(x[∗]µ[) =][ F]_ [(][x][(0)][)][ −] _[F]_ [(][x]µ[∗] [)][ −] _[µ]_ _µ[∥][2][ ≤]_ _[F]_ [(][x][(0)][)][ −] _[F]_ [(][x][∗][)] (72)
_−_ 2 _[∥][x][(0)][ −]_ _[x][∗]_

So ∆µ ∆. By Assumption B.4,
_≤_

_σ[2]_

E∥∇Fµ(ˆx)∥[2] _≤_ (β + µ)O(∆exp(− _√[R]κ[′][ ) +]_ _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [)] (73)

_βσ[2]_ _σ[2]_

_≤O(β∆exp(−_ _√[R]κ[′][ ) +][ µ][∆+]_ _µSKR_ [+] _SKR_ [+ (1][ −] _N[S]_ [)][ ζ]SR[2] [+ (1][ −] _N[S]_ [)][ βζ]µSR[2] [)]

(74)


So altogether,

E∥∇F (ˆx)∥[2] _≤O(β∆exp(−_ _√[R]κ[′][ ) + (1 +][ κ][)][ σ]SKR[2]_ [+ (1 +][ κ][)(1][ −] _N[S]_ [)][ ζ]SR[2] [+][ µ][∆)] (75)


Choose µ = max _R[2][β][2][ log][2][(][e][2][ +][ R][2][)][,]_ ∆βσSKR[2] _[,]_ (1−∆N[S]SR[)][βζ][2] . By Theorem E.1’s proof in Yuan &
_{_ _}_

Ma (2020), q q


_σ[2]_ _βσD_

E∥∇F (ˆx)∥[2] _≤_ _O[˜](_ _[β]R[∆][2][ +]_ _SKR_ [+ (1][ −] _N[S]_ [)][ ζ]SR[2] [+] _√SKR_


1
_−_ _N[S]_


_ζD_
_√SR_ ) (76)


Next we evaluate the distance bound for the returned iterate. Observe that from the distance bound in
the strongly convex case,


_σ[2]_ _ζ_ [2]
E _x[(0)]_ _x[∗]µ[∥][2][ exp(][−]_ _[R]_ ) + (77)
_∥_ _−_ _√κ_ _µ[2]SKR_ [+ (1][ −] _N[S]_ [)] _µ[2]SR_ [)]


E _xˆ_ _x[∗]µ[∥][2][ ≤O][(]_ _[β][ +][ µ]_
_∥_ _−_ _µ_


Given that µ = max _R[2][β][2][ log][2][(][e][2][ +][ R][2][)][,]_ ∆βσSKR[2] _[,]_ (1−∆N[S]SR[)][βζ][2],
_{_ _}_

q q

E∥xˆ − _x[∗]µ[∥][2][ ≤O][(][E][∥][x][(0)][ −]_ _[x][∗]µ[∥][2][ +][ ∥]x[ˆ] −_ _x[∗]µ[∥][2][)]_ (78)

_≤_ _O[˜](E∥x[(0)]_ _−_ _x[∗]µ[∥][2][)]_ (79)


-----

Now we look at the actual distance we want to bound:

E _xˆ_ _x[∗]_ (E _xˆ_ _x[∗]µ[∥][2][ +][ E][∥][x][∗]µ_ (80)
_∥_ _−_ _∥[2]_ _≤_ _O[˜]_ _∥_ _−_ _[−]_ _[x][(0)][∥][2][ +][ E][∥][x][∗]_ _[−]_ _[x][(0)][∥][2][)]_

(81)


Observe that

_Fµ(x[∗]µ[) =][ F]_ [(][x][∗]µ[) +][ ∥][x][(0)][ −] _[x][∗]µ[∥][2][ ≤]_ _[F]_ [(][x][∗][) +][ ∥][x][(0)][ −] _[x][∗][∥][2][ =][ F][µ][(][x][∗][)]_ (82)

which implies that


_∥x[(0)]_ _−_ _x[∗]µ[∥][2][ ≤∥][x][(0)][ −]_ _[x][∗][∥][2]_ (83)

E∥xˆ − _x[∗]∥[2]_ _≤_ _O[˜](D[2])_ (84)


So altogether

D.3 SAGA


**Theorem D.4. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4**
_and Assumption B.6. Then running Algo. 5 gives the following for returned iterate ˆx:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. If we return ˆx = _W1R_ _Rr=0_ _[w][r][x][(][r][)]_

_with wr = (1 −_ _ηµ)[1][−][(][r][+1)]_ _and WR =_ _r=0_ _[w][r][,][ η][ = ˜]O(min{_ _β[1]_ _[,]_ _µR1_ _[}][)][,][ R > κ]P_ _[, and we]_

_use Option I,_

[P][R]

_σ[2]_

EF (ˆx) − _F_ (x[∗]) ≤ _O[˜](∆exp(−_ min{ _β [µ]_ _[, S]N_ _µRKS_ [)]

_[}][R][) +]_

-  PL condition: Fi’s satisfy Assumption B.3. If we set η = 3β(N/S1 )[2][/][3][, use Option II in a]

_multistage manner (details specified in proof), and return a uniformly sampled iterate from_
_the final stage,_


_R_ _σ[2]_

(85)

_κ(N/S)[2][/][3][ ) +]_ _µSK_ [)]


EF (ˆx) − _F_ (x[∗]) ≤O(∆exp(−


D.3.1 CONVERGENCE OF SAGA FOR STRONGLY CONVEX FUNCTIONS

The proof of this is similar to that of Karimireddy et al. (2020b, Theorem VII).

_Proof. Following the standard analysis,_


Er∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (86)

= ∥x[(][r][)] _−_ _x[∗]∥[2]_ _−_ 2ηEr⟨g[(][r][)], x[(][r][)] _−_ _x[∗]⟩_ + Er∥ηg[(][r][)]∥[2] (87)
(88)

We treat each of these terms separately.

**Second term: Observe first that**

_K−1_

Erg[(][r][)] = Er( [1] [ [1] _f_ (x[(][r][)]; zi,k[(][r][)][)][ −] _[c]i[(][r][)][] +][ c][(][r][)][)]_ (89)

_S_ _K_ _∇_

_iX∈Sr_ _kX=0_

= ∇F (x[(][r][)]) (90)

And so the middle term has, by (strong) convexity,

_−2ηEr⟨g[(][r][)], x[(][r][)]_ _−_ _x[∗]⟩_ = −2η⟨∇F (x[(][r][)]), x[(][r][)] _−_ _x[∗]⟩_ (91)

2η(F (x[(][r][)]) _F_ (x[∗]) + _[µ]_ (92)
_≤−_ _−_ 2 _[∥][x][(][r][)][ −]_ _[x][∗][∥][2][)]_


-----

**Third term:**

Er∥ηg[(][r][)]∥[2] (93)

_K−1_

= Er _η( [1]_ [ [1] _f_ (x[(][r][)]; zi,k[(][r][)][)][ −] _[c]i[(][r][)][] +][ c][(][r][)][)][∥][2]_ (94)
_∥_ _S_ _K_ _∇_

_iX∈Sr_ _kX=0_

= η[2]Er _f_ (x[(][r][)]; zi,k[(][r][)][)][ −] _[c]i[(][r][)]_ + c[(][r][)] (95)
_∥_ _KS[1]_ _∇_ _∥[2]_

_k,iX∈Sr_

4η[2]Er _f_ (x[(][r][)]; zi,k[(][r][)][)][ −∇][F][i][(][x][(][r][)][)][∥][2][ + 4][η][2][E][r][∥][c][(][r][)][∥][2] (96)
_≤_ _∥_ _KS[1]_ _∇_

_k,iX∈Sr_

+ 4η[2]Er∥ _KS[1]_ _k,iX∈Sr_ _∇Fi(x[∗]) −_ _c[(]i[r][)][∥][2][ + 4][η][2][E][r][∥]_ _KS[1]_ _k,iX∈Sr_ _∇Fi(x[(][r][)]) −∇Fi(x[∗])∥[2]_ (97)

(98)


Where the last inequality comes from the relaxed triangle inequality. Then, by using Assumption B.6,
Assumption B.4, and Assumption B.2,

Er∥ηg[(][r][)]∥[2] (99)

_≤_ 4η[2]Er∥c[(][r][)]∥[2] + 4η[2]Er∥ _KS[1]_ _k,iX∈Sr_ _∇Fi(x[∗]) −_ _c[(]i[r][)][∥][2][ + 8][βη][2][[][F]_ [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)] + 4]KS[η][2][σ][2]

(100)


Taking full expectation and separating out the variance of the control variates,

E∥ηg[(][r][)]∥[2] (101)

_≤_ 4η[2]∥Ec[(][r][)]∥[2] + 4η[2]∥ _KS[1]_ _k,iX∈Sr_ _∇Fi(x[∗]) −_ Ec[(]i[r][)][∥][2][ + 8][βη][2][E][[][F] [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)] + 12]KS[η][2][σ][2]

(102)


Now observe that because c[(][r][)] = _N[1]_ _Ni=1_ _[c]i[(][r][)][,]_

_N_

P

E∥ηg[(][r][)]∥[2] _≤_ [8]N[η][2] _i=1_ _∥∇Fi(x[∗]) −_ Ec[(]i[r][)][∥][2][ + 8][βη][2][E][[][F] [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)] + 12]KS[η][2][σ][2] (103)

X

8η[2] _r + 8βη[2]E[F_ (x[(][r][)]) _F_ (x[∗])] + [12][η][2][σ][2] (104)
_≤_ _C_ _−_ _KS_


**Bounding the control lag:**

Recall that

_c[(]i[r][+1)]_ = _c1[(]i[r][)]_ w.p.K− 11 _−_ _N[S]_ (105)

( _K_ _k=0_ _[∇][f]_ [(][x][(][r][)][;][ z]i,k[(][r][)][)][ w.p.][ S]N

Therefore P

Ec[(]i[r][+1)] = (1 _i_ [] +][ S] (106)
_−_ _N[S]_ [)][E][[][c][(][r][)] _N_ [E][∇][F][i][(][x][(][r][)][)]

Returning to the definition of _r+1,_
_C_


_r+1 = [1]_
_C_ _N_

= [1]


E E[c[(]i[r][+1)]] _Fi(x[∗])_ (107)
_∥_ _−∇_ _∥[2]_
_i=1_

X

_N_

E (1 _i_ []][ −∇][F][i][(][x][∗][)) +][ S] (108)
_∥_ _−_ _N[S]_ [)(][E][[][c][(][r][)] _N_ [(][E][∇][F][i][(][x][(][r][)][)][ −∇][F][i][(][x][∗][))][∥][2]
_i=1_

X


(1
_≤_ _−_ _N[S]_ [)][C][r][ +][ S]N [2]


E∥∇Fi(x[(][r][)]) −∇Fi(x[∗])∥[2] (109)
_i=1_

X


-----

where in the last inequality we applied Jensen’s inequality twice. By smoothness of Fi’s (Assumption B.4),


_r+1_ (1 (110)
_C_ _≤_ _−_ _N[S]_ [)][C][r][ + 2]N[βS] [[][E][F] [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)]]


**Putting it together:**


So putting it all together, we have

E∥x[(][r][+1)] _−_ _x[∗]∥[2]_ (111)

(1 _ηµ)E_ _x[(][r][)]_ _x[∗]_ _η(2_ 8βη)(EF (x[(][r][)]) _F_ (x[∗])) + 8η[2] _r + [12][η][2][σ][2]_ (112)
_≤_ _−_ _∥_ _−_ _∥[2]_ _−_ _−_ _−_ _C_ _KS_

From our bound on the control lag,
9η[2]N

_r+1_ (1 (113)
_S_ _C_ _≤_ [9][η]S[2][N] _−_ _N[S]_ [)][C][r][ + 18][βη][2][[][E][F] [(][x][(][r][)][)][ −] _[F]_ [(][x][∗][)]]

= (1 _ηµ)_ [9][η][2][N] _r + 9η[2](_ _[ηµN]_ 1) _r + 18βη[2][EF_ (x[(][r][)]) _F_ (x[∗])] (114)
_−_ _S_ _C_ _S_ _−_ _C_ _−_

Adding both inequalities, we have


E _x[(][r][+1)]_ _x[∗]_ + [9][η][2][N] _r+1_ (115)
_∥_ _−_ _∥[2]_ _S_ _C_

(1 _ηµ)[E_ _x[(][r][)]_ _x[∗]_ + [9][η][2][N] _r]_ _η(2_ 26βη)(EF (x[(][r][)]) _F_ (x[∗])) (116)
_≤_ _−_ _∥_ _−_ _∥[2]_ _S_ _C_ _−_ _−_ _−_


1) _r + [12][η][2][σ][2]_ (117)
_−_ _C_ _KS_

_S_

9µN [, then]


+ η[2]( [9][ηµN]


Let η ≤


1 _S_

26β [,][ η][ ≤] 9µN [, then]

E _x[(][r][+1)]_ _x[∗]_ + [9][η][2][N]
_∥_ _−_ _∥[2]_ _S_


_r+1_ (118)
_C_


(1 _ηµ)[E_ _x[(][r][)]_ _x[∗]_ + [9][η][2][N] _r]_ _η(EF_ (x[(][r][)]) _F_ (x[∗])) + [12][η][2][σ][2] (119)
_≤_ _−_ _∥_ _−_ _∥[2]_ _S_ _C_ _−_ _−_ _KS_

Then by using Lemma 1 in (Karimireddy et al., 2020b), setting ηmax = min{ 261β _[,]_ 9µNS _[}][,][ R][ ≥]_ 2ηmax1 _µ_ [,]

and choosing η = min [log(max(1]µR[,µ][2][Rd][0][/c][))] _, ηmax_ where d0 = E _x[(0)]_ _x[∗]_ + [9][Nη]S [2] 0 and
_{_ _}_ _∥_ _−_ _∥[2]_ _C_

_c =_ 12KSσ[2] [, we have that by outputting][ ˆ]x = _W1R_ _Rr=0_ _[w][r][x][(][r][)][ with][ W][R][ =][ P]r[R]=0_ _[w][r][ and][ w][r][ =]_

(1 _µη)[1][−][r], we have_
_−_ P


EF (ˆx) − _F_ (x[∗]) ≤ _O[˜](µd0 exp(−µηmaxR) +_

= O[˜](µd0 exp(−µηmaxR) +


_c_

(120)
_µR_ [)]

_c_

(121)
_µR_ [)]


_σ[2]_

= [˜](µ[E _x[(0)]_ _x[∗]_ + _[Nη][2]_ (122)
_O_ _∥_ _−_ _∥[2]_ _S_ _[C][0][] exp(][−][µη][max][R][) +]_ _µRKS_ [)]

We use a warm-start strategy to initialize all control variates in the first N/S rounds such that


_K−1_

_∇f_ (x[(0)]; zi,k[(][−][1)][)]
_k=0_

X


_c[(0)]i_ = K[1]

By smoothness of Fi’s (Assumption B.4),


0 = [1]
_C_ _N_

= [1]


E Ec[(0)]i _Fi(x[∗])_ (123)
_∥_ _−∇_ _∥[2]_
_i=1_

X

_N_

E∥∇Fi(x[(0)]) −∇Fi(x[∗])∥[2] (124)
_i=1_

X


_≤_ _βE(F_ (x[(0)]) − _F_ (x[∗])) (125)


-----

And recalling that η ≤ min{


_S_
_β_ _[,]_ 9µN _[}][, we know that]_

_βE(F_ (x[(0)]) _F_ (x[∗])) (126)
_−_ _≤_ _[ηβ]µ_ [(][F] [(][x][(0)][)][ −] _[F]_ [(][x][∗][))][ ≤] _µ[1]_ [∆]


1

26β _[,]_


9Nη[2]

_S_

So altogether,


0
_C_ _≤_ [9][Nη]S [2]


_σ[2]_
EF (ˆx) _F_ (x[∗]) (∆exp( _µηmaxR) +_ (127)
_−_ _≤_ _O[˜]_ _−_ _µRKS_ [)]

D.3.2 CONVERGENCE OF SAGA UNDER THE PL CONDITION

This proof follows Reddi et al. (2016).

_Proof. We start with Assumption B.4_


EF (x[(][r][+1)]) E[F (x[(][r][)]) + _F_ (x[(][r][)]), x[(][r][+1)] _x[(][t][)]_ + _[β]_ (128)
_≤_ _⟨∇_ _−_ _⟩_ 2 _[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2][]]_

Using the fact that g[(][r][)] is unbiased,

EF (x[(][r][+1)]) E[F (x[(][r][)]) _η_ _F_ (x[(][r][)]) + _[βη][2]_ (129)
_≤_ _−_ _∥∇_ _∥[2]_ 2 _[∥][g][(][r][)][∥][2][]]_

Now we consider the Lyapunov function

_N_

_Lr = E[F_ (x[(][r][)]) + _N[c][r]_ _i=1_ _∥x[(][r][)]_ _−_ _φ[(]i[r][)][∥][2][]]_ (130)

X

We bound Lr+1 using

_N_

1

_N_ E∥x[(][r][+1)] _−_ _φ[(]i[r][+1)]∥[2]_ (131)

_i=1_

X


= [1]


_N_

[ _[S]_
_i=1_ _N_ [E][∥][x][(][r][+1)][ −] _[x][(][r][)][∥][2][ +][ N][ −]N_ _[S]_

X


E _x[(][r][+1)]_ _φ[(]i[r][)]_ (132)
_∥_ _−_ _[∥][2][]]_


Where the equality comes from how φ[(]i[r][+1)] = x[(][r][)] with probability S/N and is φ[(]i[r][)] otherwise.
Observe that we can bound

E _x[(][r][+1)]_ _φ[(]i[r][)]_ (133)
_∥_ _−_ _[∥][2]_

= E[ _x[(][r][+1)]_ _x[(][r][)]_ + _x[(][r][)]_ _φ[(]i[r][)]_ _i_ (134)
_∥_ _−_ _∥[2]_ _∥_ _−_ _[∥][2][ + 2][⟨][x][(][r][+1)][ −]_ _[x][(][r][)][, x][(][r][)][ −]_ _[φ][(][r][)][⟩][]]_

_≤_ E[∥x[(][r][+1)] _−_ _x[(][r][)]∥[2]_ + ∥x[(][r][)] _−_ _φ[(]i[r][)][∥][2][] + 2][η][E][[ 1]2b_ _[∥∇][F]_ [(][x][(][r][)][)][∥][2][ + 1]2 _[b][∥][x][(][r][)][ −]_ _[φ]i[(][r][)][∥][2][]]_ (135)

Where we used unbiasedness of g[(][r][)] and Fenchel-Young inequality. Plugging this into Lr+1,

_Lr+1_ E[F (x[(][r][)]) _η_ _F_ (x[(][r][)]) + _[βη][2]_ (136)
_≤_ _−_ _∥∇_ _∥[2]_ 2 _[∥][g][(][r][)]N[∥][2][]]_

_N_ _S_
+ E[cr+1∥x[(][r][+1)] _−_ _x[(][r][)]∥[2]_ + cr+1 _N −[2]_ _i=1_ _∥x[(][r][)]_ _−_ _φ[(]i[r][)][∥][2][]]_ (137)

X


+ [2(][N][ −] _[S][)][c][r][+1][η]_

_N_ [2]


_N_

_i=1_ E[ 2[1]b _[∥∇][F]_ [(][x][(][r][)][)][∥][2][ + 1]2 _[b][∥][x][(][r][)][ −]_ _[φ]i[(][r][)][∥][2][]]_ (138)

X


E[F (x[(][r][)]) (η ) _F_ (x[(][r][)]) + ( _[βη][2]_
_≤_ _−_ _−_ _[c][r][+1][η]bN[(][N][ −]_ _[S][)]_ _∥∇_ _∥[2]_ 2


+ cr+1η[2])E∥g[(][r][)]∥[2]] (139)


+ ( _[N][ −]_ _[S]_


_cr+1 +_ _[c][r][+1][ηb][(][N][ −]_ _[S][)]_


) [1]


E _x[(][r][)]_ _φ[(]i[r][)]_ (140)
_i=1_ _∥_ _−_ _[∥][2]_

X


-----

Now we must bound E∥g[(][r][)]∥[2].

E ( [1] [ [1] _K−1_ _f_ (x[(][r][)]; zi,k[(][r][)][)][ −∇][f] [(][φ]i[(][r][)][; ˜]zi,k[(][r][)][)] +] 1 _N_ _f_ (φ[(]i[r][)][; ˜]zi,k[(][r][)][))][∥][2] (141)
_∥_ _S_ _K_ _∇_ _NK_ _∇_

_iX∈Sr_ _kX=0_ Xi=1

_K−1_

2E ( [1] [ [1] _f_ (x[(][r][)]; zi,k[(][r][)][)][ −∇][f] [(][φ]i[(][r][)][; ˜]zi,k[(][r][)][)]] (142)
_≤_ _∥_ _S_ _K_ _∇_

_iX∈Sr_ _kX=0_


_N_

[ _f_ (x[(][r][)]; zi,k[(][r][)][)][ −∇][f] [(][φ]i[(][r][)][; ˜]zi,k[(][r][)][))]][∥][2][ + 2][E][∥] [1]
_∇_ _NK_
_i=1_

X


_∇f_ (x[(][r][)]; zi,k[(][r][)][)][∥][2] (143)
_i=1_

X


_NK_


_Fi(x[(][r][)])_ _Fi(φ[(]i[r][)][)][∥][2][ + 2][E][∥∇][F]_ [(][x][(][r][)][)][∥][2][ +][ νσ][2] (144)
_∇_ _−∇_ _SK_
_iX∈Sr_


2E
_≤_ _∥_ _S[1]_


Where the second to last inequality is an application of Var(X) ≤ E[X [2]], and separating out the
variance (taking advantage of the fact that ˜z’s and z’s are independent), and ν is some constant.

We use Assumption B.4 and take expectation over sampled clients to get


E _g[(][r][)]_
_∥_ _∥[2]_ _≤_ [2]N[β][2]

Returning to our bound on Lr+1,


_N_

_i=1_ E∥x[(][t][)] _−_ _φ[(]i[r][)][∥][2][ + 2][E][∥∇][F]_ [(][x][(][r][)][)][∥][2][ +][ νσ]SK[2] (145)

X


_Lr+1_ EF (x[(][r][)]) (η _η[2]β_ 2cr+1η[2])E _F_ (x[(][r][)]) (146)
_≤_ _−_ _−_ _[c][r][+1][η]bN[(][N][ −]_ _[S][)]_ _−_ _−_ _∥∇_ _∥[2]_


+ (cr+1( _[N][ −]_ _[S]_


+ _[ηb][(][N][ −]_ _[S][)]_


+ 2η[2]β[2]) + η[2]β[3]) [1]


E _x[(][r][)]_ _φ[(]i[r][)]_ (147)
_i=1_ _∥_ _−_ _[∥][2]_

X


+ _[νη][2][σ][2]_ (148)

_SK_ [(][c][r][+1][ +][ β]2 [)]


+ _[ηb][(][N]N[−][S][)]_


We set cr = cr+1( _[N]N[−][S]_


+ 2η[2]β[2]) + η[2]β[3], which results in


_Lr+1_ (149)

_Lr_ (η _η[2]β_ 2cr+1η[2])E _F_ (x[(][r][)]) + _[νη][2][σ][2]_ (150)
_≤_ _−_ _−_ _[c][r][+1][η]bN[(][N][ −]_ _[S][)]_ _−_ _−_ _∥∇_ _∥[2]_ _SK_ [(][c][r][+1][ +][ β]2 [)]

Let Γr = η _bN_ _η[2]β_ 2cr+1η[2]. Then by rearranging
_−_ _[c][r][+1][η][(][N]_ _[−][S][)]_ _−_ _−_

ΓrE _F_ (x[(][r][)]) _Lr_ _Lr+1 +_ _[νη][2][σ][2]_ (151)
_∥∇_ _∥[2]_ _≤_ _−_ _SK_ [(][c][r][+1][ +][ β]2 [)]

Letting γn = min0 _r_ _R_ 1 Γr,
_≤_ _≤_ _−_


_R−1_

E∥∇F (x[(][r][)])∥[2] _≤_
_r=0_

X


_R−1_

ΓrE∥∇F (x[(][r][)])∥[2] (152)
_r=0_

X


_γn_


_R−1_

_r=0_

X


_νη[2]σ[2]_

(153)

_SK_ [(][c][r][+1][ +][ β]2 [)]


_≤_ _L0 −_ _LR +_


Implying


_R−1_

E _F_ (x[(][r][)]) + [1]
_∥∇_ _∥[2]_ _≤_ _γ[∆]n_ _γn_
_r=0_

X


_R−1_

_r=0_

X


_νη[2]σ[2]_

(154)

_SK_ [(][c][r][+1][ +][ β]2 [)]


Therefore, if we take a uniform sample from all the x(r), denoted ¯x[R],


_R−1_

_r=0_

X


_νη[2]σ[2]_

(155)

_SK_ [(][c][r][+1][ +][ β]2 [)]


E∥∇F (¯x[(][R][)])∥[2] _≤_


_γnR_ [+]


_γnR_


-----

We start by bounding cr. Take η = 31β 4[(][ S]NS [)][2][/][3][ and][ b][ =][ β][(][ S]N [)][1][/][3][. Let][ θ][ =] _NS_ _[−]_ _[ηb][(][N]N[−][S][)]_ _−_

2η[2]β[2]. Observe that θ < 1 and θ > 9 _N_ [. Then][ c][r][ =][ c][r][+1][(1][ −] _[θ][) +][ η][2][β][3][, which implies]_

_cr = η[2]β[3 1][−][(1][−]θ[θ][)][R][−][r]_ _≤_ _[η][2]θ[β][3]_ _≤_ _[β]4_ [(][ S]N [)][1][/][3]

So we can conclude that


_γn = min_
_r_ [(][η][ −] _[c][r][+1]β_ _[η]_


1

(156)

12β [(][ S]N [)][2][/][3]


_η[2]β_ 2cr+1η[2])
_−_ _−_ _≥_


So altogether,

E _F_ (¯x[(][R][)])
_∥∇_ _∥[2]_ _≤_ [12]R[β][∆]

= [12][β][∆]

_R_

_≤_ [12]R[β][∆]


( _[N]_

_S_ [)][2][/][3][ +][ νη]SK[2][βσ][2]


1

(157)
12β(N/S)[2][/][3][ )]


( _[N]_

_S_ [)][2][/][3][ +][ νβσ]SK[2] [(12][β][(][N/S][)][2][/][3][)(]


1

(158)
9β[2](N/S)[4][/][3][ )]


( _[N]_ (159)

_S_ [)][2][/][3][ + 2]SK[νσ][2]


Now we run Algo. 5 in a repeated fashion, as follows:

1. Set x[(0)] = ps−1

2. Run Algo. 5 for Rs iterations

3. Set ps to the result of Algo. 5

Repeat for s stages. Let p0 be the initial point. Letting Rs = ⌈24κ( _[N]S_ [)][2][/][3][⌉] [this implies that]


2µ(EF (ps) _F_ (x[∗])) E _F_ (ps)
_−_ _≤_ _∥∇_ _∥[2]_ _≤_ _[µ][(][E][F]_ [(][p][s][−][1]2[)][ −] _[F]_ [(][x][∗][))]

Which gives


+ [2][νσ][2] (160)

_SK_


_σ[2]_
EF (ps) _F_ (x[∗]) (∆exp( _s) +_ (161)
_−_ _≤O_ _−_ _µSK_ [)]

If the total number of rounds is R, then

_σ[2]_

EF (ˆx) _F_ (x[∗]) (∆exp( (162)
_−_ _≤O_ _−_ _[R]κ_ [) +] _µSK_ [)]


D.4 SSNM

Note that our usual assumption Fi(x) is µ-strongly convex can be straightforwardly converted into
the assumption that our losses are Fi(x) = F[˜]i(x) + h(x) where _F[˜]i(x) is merely convex and h(x) is_
_µ-strongly convex (see (Zhou et al., 2019) section 4.2)._

**Theorem D.5. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4**
_and Assumption B.6. Then running Algo. 6 gives the following for returned iterate ˆx:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. If we return the final iterate
_and set η =_ 2µ(N/S1 ) _[, τ][ =][ (][N/S]1+ηµ[)][ηµ]_ _if_ [(][N/S]κ [)] _>_ 4[3] _[and][ η][ =]_ 3µ(N/S1 )β _[, τ][ =][ (][N/S]1+ηµ[)][ηµ]_ _if_

q


(N/S)


_≤_ 4[3] _[,]_

EF (x[(][R][)]) − _F_ (x[∗]) ≤O(κ∆exp(− min{ _N [S]_ _[,]_


_S_

_Nκ_ _[}][R][) +][ κσ]µKS[2]_ [)]


-----

D.4.1 CONVERGENCE OF SSNM ON STRONGLY CONVEX FUNCTIONS

Most of this proof follows that of (Zhou et al., 2019) Theorem 1.

First, we compute the variance of the update g[(][r][)].


E[ _g[(][r][)]_
_∥_ _−_ _N[1]_


_∇F[˜]i(yi[(]r[r][)][)][∥][2][]]_ (163)
_i=1_

X


_N_

( _Fi(yi[(][r][)])_ _Fi(φ[(]i[r][)][))][∥][2][ +][ νσ][2]_ (164)
_∇_ [˜] _−∇_ [˜] _KS_
_i=1_

X


E
_≤_ _∥_ _S[1]_

E
_≤_ _∥_ _S[1]_


_N_

E _Fir_ (yi[(]r[r][)][)][ −∇]F[˜]ir (φ[(]ir[r][)][)][ −] [1] ( _Fi(yi[(][r][)])_ _Fi(φ[(]i[r][)][))][∥][2][ +][ νσ][2]_ (164)
_≤_ _∥_ _S[1]_ _∇_ [˜] _N_ _∇_ [˜] _−∇_ [˜] _KS_

_irX∈Sr_ Xi=1

E _Fir_ (yi[(]r[r][)][)][ −∇]F[˜]ir (φ[(]ir[r][)][)][∥][2][ +][ νσ][2] (165)
_≤_ _∥_ _S[1]_ _∇_ [˜] _KS_

_irX∈Sr_

2βE[ [1] _F˜ir_ (φ[(]ir[r][)][)][ −] _F[˜]ir_ (yi[(]r[r][)][)][ −⟨∇]F[˜]ir (yi[(]r[r][)][)][, φ]i[(]r[r][)] _ir_ (166)
_≤_ _S_ _irX∈Sr_ _[−]_ _[y][(][r][)][⟩][] +][ νσ]KS[2]_

_N_ _N_

= 2β[ [1] _F˜i(φ[(]i[r][)][)][ −]_ _F[˜]i(yi[(][r][)])_ _Fi(yi[(][r][)]), φ[(]i[r][)]_ _yi[(][r][)]_ ] + _[νσ][2]_ (167)

_N_ _−_ _N[1]_ _⟨∇_ [˜] _−_ _⟩_ _KS_

_i=1_ _i=1_

X X


For some constant ν. In the first inequality we separated out the gradient variance, second inequality
we use the fact that Var(X) ≤ E[X [2]], third inequality used Assumption B.4, and fourth we took
expectation with respect to the sampled clients. From convexity we have that

_F˜ir_ (yi[(]r[r][)][)][ −] _F[˜]ir_ (x[∗]) (168)

_≤⟨∇F[˜]ir_ (yi[(]r[r][)][)][, y]i[(]r[r][)] _[−]_ _[x][∗][⟩]_ (169)

= [1][ −] _[τ]_ _Fir_ (yi[(]r[r][)][)][, φ]i[(]r[r][)] _ir_ _Fir_ (yi[(]r[r][)][)][, x][(][r][)][ −] _[x][∗][⟩]_ (170)

_τ_ _⟨∇_ [˜] _[−]_ _[y][(][r][)][⟩]_ [+][ ⟨∇] [˜]

= [1][ −] _[τ]_ _Fir_ (yi[(]r[r][)][)][, φ]i[(]r[r][)] _ir_ _Fir_ (yi[(]r[r][)][)][ −] _[g][(][r][)][, x][(][r][)][ −]_ _[x][∗][⟩]_ (171)

_τ_ _⟨∇_ [˜] _[−]_ _[y][(][r][)][⟩]_ [+][ ⟨∇] [˜]

+ ⟨g[(][r][)], x[(][r][)] _−_ _x[(][r][+1)]⟩_ + ⟨g[(][r][)], x[(][r][+1)] _−_ _x[∗]⟩_ (172)

where the second to last inequality comes from the definition that yi[(]r[r][)] [=][ τx][(][r][)][ + (1][ −] _[τ]_ [)][φ]i[(]r[r][)][. Taking]
expectation with respect to the sampled clients, we have


_N_

_F˜i(yi[(][r][)]) −_ _F[˜](x[∗]) ≤_ [1]τN[ −] _[τ]_
_i=1_

X


_⟨∇F[˜]i(yi[(][r][)]), φ[(]i[r][)]_ _−_ _yi[(][r][)]⟩_ + ESr _⟨g[(][r][)], x[(][r][)]_ _−_ _x[(][r][+1)]⟩_ (173)
_i=1_

X


+ E _r_ _g[(][r][)], x[(][r][+1)]_ _x[∗]_ (174)
_S_ _⟨_ _−_ _⟩_

For ESr _⟨g[(][r][)], x[(][r][)]_ _−_ _x[(][r][+1)]⟩, we can employ smoothness at (φ[(]I[r]r[+1)], yI[(][r]r[)][)][, which holds for any]_
_Ir ∈Sr[′]_ [:]

_F˜Ir_ (φ[(]I[r]r[+1)]) − _F[˜]Ir_ (yI[(][r]r[)][)][ ≤⟨∇]F[˜]Ir (yI[(][r]r[)][)][, φ]I[(][r]r[+1)] _−_ _yI[(][r]r[)][⟩]_ [+][ β]2 _[∥][φ]I[(][r]r[+1)]_ _−_ _yI[(][r]r[)][∥][2]_ (175)

using φ[(]I[r]r[+1)] = τx[(][r][+1)] + (1 − _τ_ )φ[(]I[r]r[)] [and][ y]I[(][r]r[)] [=][ τx][(][r][)][ + (1][ −] _[τ]_ [)][φ]I[(][r]r[)] [(though the second is never]
explicitly computed and only implicitly exists)

_F˜Ir_ (φ[(]I[r]r[+1)]) − _F[˜]Ir_ (yI[(][r]r[)][)][ ≤] _[τ]_ _[⟨∇]F[˜]Ir_ (yI[(][r]r[)][)][, x][(][r][+1)][ −] _[x][(][r][)][⟩]_ [+][ βτ]2[ 2] _[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2]_ (176)


Taking expectation over Sr[′] [and using][ φ]I[(][r]r[+1)] = τx[(][r][+1)] +(1−τ )φ[(]I[r]r[)] [and][ y]I[(][r]r[)] [=][ τx][(][r][)] [+(1][−][τ] [)][φ]I[(][r]r[)]
we see that


E _r′_ [[ 1]
_S_ _S_


_F˜Ir_ (φ[(]I[r]r[+1)])] − _N[1]_


_N_

_F˜i(yi[(][r][)]) ≤_ _τ_ _⟨_ _N[1]_
_i=1_

X


_Fi(yi[(][r][)]), x[(][r][+1)]_ _x[(][r][)]_ (177)
_∇_ [˜] _−_ _⟩_
_i=1_

X


_Ir_ _r_
_∈S_ _[′]_


+ _[βτ][ 2]_ (178)

2

_[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2]_


-----

and rearranging,

_⟨g[(][r][)], x[(][r][)]_ _−_ _x[(][r][+1)]⟩_ (179)


_N_

_F˜i(yi[(][r][)])_ _r_ [[]
_i=1_ _−_ _τS[1]_ [E][S] _[′]_ _Ir_ _r_

X X∈S _[′]_


_F˜Ir_ (φ[(]I[r]r[+1)])] (180)


_≤_ _τN_

+
_⟨_ _N[1]_


_N_

_∇F[˜]i(yi[(][r][)]) −_ _g[(][r][)], x[(][r][+1)]_ _−_ _x[(][r][)]⟩_ + _[βτ]2_ (181)
_i=1_ _[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2]_

X


Substituting this into Eq. (173) after taking expectation over _r, and observing that from (Zhou et al.,_
_S_
2019, Lemma 2) we have identity

_g[(][r][)], x[(][r][+1)]_ _u_ (182)
_⟨_ _−_ _⟩≤−_ 2[1]η 2η

_[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2][ + 1]_ _[∥][x][(][r][)][ −]_ _[u][∥][2]_

_x[(][r][+1)]_ _u_ + h(u) _h(x[(][r][+1)])_ (183)

_−_ [1 +]2η[ ηµ] _∥_ _−_ _∥[2]_ _−_


so with u = x[∗], we get

_N_

1

_N_ _F˜i(yi[(][r][)]) −_ _F[˜](x[∗])_ (184)

_i=1_

X


_≤_ [1]τN[ −] _[τ]_


_Fi(yi[(][r][)]), φ[(]i[r][)]_ _yi[(][r][)]_ +
_⟨∇_ [˜] _−_ _⟩_
_i=1_

X


_F˜i(yi[(][r][)])_ (185)
_i=1_

X


_τN_


_r_ [[]

_−_ _τS[1]_ [E][S][r][,][S] _[′]_ _Ir_ _r_

X∈S _[′]_


_F˜Ir_ (φ[(]I[r]r[+1)])] (186)


+ E _r_
_S_ _⟨_ _N[1]_


_N_

_i=1_ _∇F[˜]i(yi[(][r][)]) −_ _g[(][r][)], x[(][r][+1)]_ _−_ _x[(][r][)]⟩_ + _[βτ]2_ [E][S][r] _[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2]_ (187)

X


E _r_ _x[(][r][+1)]_ _x[∗]_ (188)

_−_ 2[1]η [E][S][r] _[∥][x][(][r][+1)][ −]_ _[x][(][r][)][∥][2][ + 1]2η_ 2η _S_ _∥_ _−_ _∥[2]_

_[∥][x][(][r][)][ −]_ _[x][∗][∥][2][ −]_ [1 +][ ηµ]

+ h(x[∗]) E _r_ _h(x[(][r][+1)])_ (189)
_−_ _S_


1

2c _[∥][a][∥][2][ +][ c]2_ _[∥][b][∥][2][ with]_


We use the constraint thatc = 1βτ−τ [on][ E][S][r] _[⟨]_ _N[1]_ _Ni=1_ _βτ[∇]F[˜] ≤i(yi[(]η[1][r][)][−]) −1βτ−gτ[(][r][)][plus Young’s inequality], x[(][r][+1)]_ _−_ _x[(][r][)]⟩_ to get _[ ⟨][a, b][⟩≤]_

P


_F˜i(yi[(][r][)])_ _F_ (x[∗]) (190)
_−_ [˜]
_i=1_

X


_≤_ [1]τN[ −] _[τ]_

1
+

_τN_


_Fi(yi[(][r][)]), φ[(]i[r][)]_ _yi[(][r][)]_ (191)
_⟨∇_ [˜] _−_ _⟩_
_i=1_

X


_N_

_F˜i(yi[(][r][)])_ _r_ [[]
_i=1_ _−_ _τS[1]_ [E][S][r][,][S] _[′]_ _Ir_ _r_

X X∈S _[′]_


_F˜Ir_ (φ[(]I[r]r[+1)])] (192)


+ [1][ −] _[τ]_

2βτ [E][S][r] _[∥]_ _N[1]_


_N_

_∇F[˜]i(yi[(][r][)]) −_ _g[(][r][)]∥[2]_ + 2[1]η (193)
_i=1_ _[∥][x][(][r][)][ −]_ _[x][∗][∥][2]_

X


E _r_ _x[(][r][+1)]_ _x[∗]_ + h(x[∗]) E _r_ _h(x[(][r][+1)])_ (194)

_−_ [1 +]2η[ ηµ] _S_ _∥_ _−_ _∥[2]_ _−_ _S_


-----

using the bound on variance, we get

_N_

1

_N_ _F˜i(yi[(][r][)]) −_ _F[˜](x[∗])_ (195)

_i=1_

X


_N_ _N_

1

_F˜i(yi[(][r][)])_ _r_ [[] _F˜Ir_ (φ[(]I[r]r[+1)])] + [1][ −] _[τ]_ _F˜i(φ[(]i[r][)][)][ −]_ _F[˜]i(yi[(][r][)])_ (196)

_τN_ _i=1_ _−_ _τS[1]_ [E][S][r][,][S] _[′]_ _Ir_ _r_ _τN_ _i=1_

X X∈S _[′]_ X

+ [1] E _r_ _x[(][r][+1)]_ _x[∗]_ (197)

2η _[∥][x][(][r][)][ −]_ _[x][∗][∥][2][ −]_ [1 +]2η[ ηµ] _S_ _∥_ _−_ _∥[2]_

+ h(x[∗]) E _r_ _h(x[(][r][+1)]) + [(1][ −]_ _[τ]_ [)][νσ][2] (198)
_−_ _S_ 2βτKS


combining terms,
1

_r_ [[]
_τS_ [E][S][r][,][S] _[′]_ _Ir_ _r_
X∈S _[′]_


_F˜Ir_ (φ[(]I[r]r[+1)])] _F_ (x[∗]) (199)
_−_


_N_

_≤_ [1]τN[ −] _[τ]_ _F˜i(φ[(]i[r][)][) + 1]2η_ 2η ESr _∥x[(][r][+1)]_ _−_ _x[∗]∥[2]_ (200)

Xi=1 _[∥][x][(][r][)][ −]_ _[x][∗][∥][2][ −]_ [1 +][ ηµ]

E _r_ _h(x[(][r][+1)]) + [(1][ −]_ _[τ]_ [)][νσ][2] (201)
_−_ _S_ 2βτKS


Using convexity of h and φ[(]I[r]k[+1)] = τx[(][r][+1)] + (1 − _τ_ )φ[(]I[r]k[)] [for][ I][k][ ∈S]r[′] [,]

_h(φ[(]I[r]k[+1)]) ≤_ _τh(x[(][r][+1)]) + (1 −_ _τ_ )h(φ[(]I[r]k[)][)] (202)

After taking expectation with respect to Sr and Sr[′] [,]


E _r_ [h(x[(][r][+1)])]
_−_ _S_ _≤_ [1]τN[ −] _[τ]_


_N_

_h(φ[(]i[r][)][)][ −]_ [1] _r_ [[ 1]
_i=1_ _τ_ [E][S][r][,][S] _[′]_ _S_

X


_h(φ[(]I[r]k[+1)])]_ (203)
_Ir_ _r_

X∈S _[′]_


and plugging this back in, multiplying by S/N on both sides, and adding both sides by
1

_τN_ [E][S]r[′] [[][P]i/∈Sr[′] [(][F][i][(][φ][(]i[r][)][)][ −] _[F][i][(][x][∗][))]]_

_N_

1
_r_ [[ 1] _Fi(φ[(]i[r][+1)])_ _Fi(x[∗])]_ (204)
_τ_ [E][S][r][,][S] _[′]_ _N_ _i=1_ _−_

X

_N_

( [1] _Fi(φ[(]i[r][)][)][ −]_ _[F][i][(][x][∗][)) +]_ 1 _r_ [[] (Fi(φ[(]i[r][)][)][ −] _[F][i][(][x][∗][))]]_ (205)

_≤_ [(1][ −]τN[τ] [)][S] _N_ _i=1_ _τN_ [E][S] _[′]_ _i/_ _r_

X X∈S _[′]_

_S_
+ E _r_ _x[(][r][+1)]_ _x[∗]_ + [(1][ −] _[τ]_ [)][νσ][2] (206)

2ηN _[∥][x][(][r][)][ −]_ _[x][∗][∥][2][ −]_ [(1 +]2ηN[ ηµ][)][S] _S_ _∥_ _−_ _∥[2]_ 2βτKN

Observe that the probability of choosing any client index happens with probability S/N, so


( [1]

_≤_ [(1][ −]τN[τ] [)][S] _N_


_Fi(φ[(]i[r][)][)][ −]_ _[F][i][(][x][∗][)) +]_
_i=1_

X


1

_r_ [[] (Fi(φ[(]i[r][)][)][ −] _[F][i][(][x][∗][))] =][ N][ −]_ _[S]_ ( [1]
_τN_ [E][S] _[′]_ _τN_ _N_

_i/_ _r_

X∈S _[′]_

which implies


_Fi(φ[(]i[r][)][)][ −]_ _[F][i][(][x][∗][))]_ (207)
_i=1_

X


1
_r_ [[ 1]
_τ_ [E][S][r][,][S] _[′]_ _N_


_Fi(φ[(]i[r][+1)])_ _Fi(x[∗])]_ (208)
_−_
_i=1_

X


_N_

_≤_ [1][ −]τ _[τS]_


( [1]


_Fi(φ[(]i[r][)][)][ −]_ _[F][i][(][x][∗][))]_ (209)
_i=1_

X


_S_

E _r_ _x[(][r][+1)]_ _x[∗]_ + [(1][ −] _[τ]_ [)][νσ][2] (210)

2ηN _[∥][x][(][r][)][ −]_ _[x][∗][∥][2][ −]_ [(1 +]2ηN[ ηµ][)][S] _S_ _∥_ _−_ _∥[2]_ 2βτKN


-----

To complete our Lyapunov function so the potential is always positive, we need another term:


_−_ _N[1]_


_Fi(x[∗]), φ[(]i[r][+1)]_ _x[∗]_ (211)
_⟨∇_ _−_ _⟩_
_i=1_

X


= − _N[1]_ _⟨∇FIr_ (x[∗]), φ[(]I[r]r[+1)] _−_ _x[∗]⟩−_ _N[1]_ _⟨∇Fj(x[∗]), φ[(]j[r][)]_ _−_ _x[∗]⟩_ (212)

_IrX∈Sr[′]_ _j /X∈Sr[′]_

= _−_ _N[τ]_ _N_ _Ir_ (213)

_IrX∈Sr[′]_ _[⟨∇][F][I][r]_ [(][x][∗][)][, x][(][r][+1)][ −] _[x][∗][⟩]_ [+][ τ] _[⟨∇][F][I][r]_ [(][x][∗][)][, φ][(][r][)] _[−]_ _[x][∗][⟩]_


_−_ _N[1]_


_Fi(x[∗]), φ[(]i[r][)]_ _x[∗]_ (214)
_⟨∇_ _−_ _⟩_
_i=1_

X


Taking expectation with respect to Sr, Sr[′] [,]


_N_ _N_

E _r,_ _r′_ [[][−] [1] _Fi(x[∗]), φ[(]i[r][+1)]_ _x[∗]_ ] = (1 _Fi(x[∗]), φ[(]i[r][)]_ _x[∗]_ ) (215)
_S_ _S_ _N_ _⟨∇_ _−_ _⟩_ _−_ _−_ _[τS]N_ [)( 1]N _⟨∇_ _−_ _⟩_

_i=1_ _i=1_

X X

Let Br := _N1_ _Ni=1_ _[F][i][(][φ]i[(][r][)][)][ −]_ _[F]_ [(][x][∗][)][ −] _N[1]_ _Ni=1[⟨∇][F][i][(][x][∗][)][, φ]i[(][r][)]_ _−_ _x[∗]⟩_ and Pr := ∥x[(][r][)] _−_ _x[∗]∥[2],_

then we can write

P P

1 _r_ [[][B][r][+1][] + (1 +][ ηµ][)][S] E _r_ [Pr+1] _N_ _Br +_ _S_ (216)
_τ_ [E][S][r][,][S] _[′]_ 2ηN _S_ _≤_ [1][ −]τ _[τS]_ 2ηN [P][r][ + (1]2[ −]βτKN[τ] [)][νσ][2]


(N/S)

3κ1 _<_ [1]2 [,]

3(N/S)κ


**Case 1: Suppose that** [(][N/S]κ [)]


1

3µ(N/S)β [,][ τ][ =][ (][N/S]1+ηµ[)][ηµ]


_≤_ 4[3] [, then choosing][ η][ =]


1+


we evaluate the parameter constraint βτ ≤ _η[1]_ _[−]_ 1βτ−τ [:]


(N/S)

3κ

1

3(N/S)κ


_βτ_

_βτ_ (1 +
_≤_ _η[1]_ _[−]_ 1 − _τ_ [=]⇒


1

1 _τ_ [)][τ][ ≤] _βη[1]_ [=]⇒ 1[2][ −] _τ[τ]_
_−_ _−_


3(N/S)


(217)


1 +


which shows our constraint is satisfied. We also know that


1 _N_

_τ_ (1 + ηµ) [= 1][ −]τ _[τS]_


1

(218)
(N/S)ηµ


So we can write


1 1

_r_ [[][B][r][+1][] +] (219)
(N/S)ηµ [E][S][r][,][S] _[′]_ 2η(N/S) [E][S][r] [[][P][r][+1][]]


1 1

(220)

(N/S)ηµ _[B][r][ +]_ 2η(N/S) _[P][r][) + (1]2[ −]βτKN[τ]_ [)][νσ][2]


_≤_ (1 + ηµ)[−][1](


Telescoping the contraction and taking expectation with respect to all randomness, we have


1

(N/S)ηµ [E][[][B][R][] +]


1

(221)
2η(N/S) [E][[][P][R][]]


1 1

( [1 +][ ηµ] ) (222)

(N/S)ηµ [E][B][0][ +] 2η(N/S) [E][P][0][) + (1]2[ −]βτKN[τ] [)][νσ][2] _ηµ_


_≤_ (1 + ηµ)[−][R](


variance term.B0 = F (x[(0)]) − _F_ (x[∗]) and EBR ≥ 0 based on convexity. Next, we calculate the coefficient of the
1 _τ_ 1 + ηµ
_−_ = ( [1] (223)

_τ_ _ηµ_ _τ_ _[−]_ [1)(1 + 1]ηµ [) = (][ S]N [(1 + 1]ηµ [)][ −] [1)(1 + 1]ηµ [)]

_N_ _N_

= (( _[S]_ (224)
_O_ _N_ [(1 +][ √][κ][(] _S_ [))][ −] [1)(1 +][ √][κ][(] _S_ [)))]

r r

= (( _[S]_ (225)
_O_ _N_ [+][ √][κ][(][ S]N [)][1][/][2][ −] [1)(1 +][ √][κ][(] _[N]S_ [)][1][/][2][))]

= O(κ) (226)


-----

Substituting the parameter choices and using strong convexity,


1 _σ[2]_

(227)

3(N/S)κ [)][−][R][( 2]µ [∆+][ D][2][) +][ O][(] _µ[2]KN_ [)]


E∥x[(][R][)] _−_ _x[∗]∥[2]_ _≤_ (1 +


**Case 2: On the other hand, we can have** [(][N/S]κ [)] _>_ [3]4 [and choose][ η][ =] 2µ(N/S1 ) [,][ τ][ =][ (][N/S]1+ηµ[)][ηµ]

(1/2) _βτ_

1+ 2(N/S1 ) _[<][ 1]2_ [. One can check that the constraint][ βτ][ ≤] _η[1]_ _[−]_ 1−τ [is satisfied.]

After telescoping and taking expectation,


2E[BR] +


1

(228)
2η(N/S) [E][[][P][R][]]


1

( [1 +][ ηµ] ) (229)

2η(N/S) [E][P][0][) + (1]2[ −]βτKN[τ] [)][νσ][2] _ηµ_


_≤_ (1 + ηµ)[−][R](2EB0 +


Next, we calculate the coefficient of the variance term.
1 _τ_ 1 + ηµ
_−_ = ( [1] (230)

_τ_ _ηµ_ _τ_ _[−]_ [1)(1 + 1]ηµ [) = (][ S]N [(1 + 1]ηµ [)][ −] [1)(1 + 1]ηµ [)]

= (( _[S]_ (231)
_O_ _N_ [(1 +][ N]S [)][ −] [1)(1 +][ N]S [))]

= ( _[N]_ (232)
_O_ _S_ [)]


which gives us


1 _σ[2]_
E _x[(][R][)]_ _x[∗]_ (1 + (233)
_∥_ _−_ _∥[2]_ _≤_ 2(N/S) [)][−][R][( 2]µ [∆+][ D][2][) +][ O][(] _βµKS_ [)]


Altogether, supposing we choose our parameters as stated in the two cases, we have:


_S_

(234)

_Nκ_ _[}][R][) +][ κσ]µKS[2]_ [)]


EF (x[(][R][)]) − _F_ (x[∗]) ≤O(κ∆exp(− min{ _N [S]_ _[,]_


E PROOFS FOR LOCAL UPDATE METHODS

E.1 FEDAVG

**Theorem E.1. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4**
_and Assumption B.6. Then running Algo. 4 gives the following for returned iterate ˆx:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. If we return the final iterate, set
_η =_ _β[1]_ _[, and sample][ S][ clients per round arbitrarily,]_


_σ[2]_

) + _[ζ]_ [2]

_µ_ [+] _µ√_


EF (x[(][R][)]) − _F_ (x[∗]) ≤O(∆exp(− _[R]_


_Further, if there is no gradient variance and only one client i is sampled the entire algorithm,_

_x[(][r][)]_ _x[∗]_ ( _x[(0)]_ _x[∗]_ + _x[(0)]_ _x[∗]i_
_∥_ _−_ _∥[2]_ _≤O_ _∥_ _−_ _∥[2]_ _∥_ _−_ _[∥][2][)][ for any][ 0][ ≤]_ _[r][ ≤]_ _[R]_

-  General convex: Fi’s satisfy Assumption B.2. If we return the last iterate after run_ning the algorithm on Fµ(x) = F_ (x) + _[µ]2_ _R[2][ log][2][(][e][2][ +]_

_R[2]),_ _D[ζ]_ _[,]_ _DKσ[1][/][4][ }][)][, and][ η][ =]_ _β+1_ _µ_ _[,]_ _[∥][x][(0)][ −]_ _[x][∥][2][ with][ µ][ = Θ(max][{][ β]_

EF (x[(][R][)]) − _F_ (x[∗]) ≤ _O[˜](_ _√[βD]KR[2]_ + _K[σD][1][/][4][ +][ ζD][)]_


_and for any 0 ≤_ _r ≤_ _R,_


E∥x[(][r][)] _−_ _x[∗]∥[2]_ _≤_ _O[˜](D[2])_


-----

-  PL condition: Fi’s satisfy Assumption B.3 for µ > 0. If we return the final iterate, set
_η =_ _β[1]_ _[, and sample one client per round,]_


_σ[2]_

) + _[ζ]_ [2]

2µ [+] 2µ√


EF (x[(][R][)]) − _F_ (x[∗]) ≤O(∆exp(− _[R]_


E.1.1 CONVERGENCE OF FEDAVG FOR STRONGLY CONVEX FUNCTIONS

_Proof. By smoothness of F (Assumption B.4), we have for k ∈{0, . . .,_ _√K −_ 1}

_F_ (x[(]i,k[r][)]+1[)][ −] _[F]_ [(][x][(]i,k[r][)][)][ ≤−][η][⟨∇][F] [(][x][(]i,k[r][)][)][, g]i,k[(][r][)] 2 _i,k_ (235)

_[⟩]_ [+][ βη][2] _[∥][g][(][r][)][∥][2]_

Using the fact that for any a, b we have −2ab = (a − _b)[2]_ _−_ _a[2]_ _−_ _b[2],_

_F_ (x[(]i,k[r][)]+1[)][ −] _[F]_ [(][x][(]i,k[r][)][)][ ≤−] _[η]_ _i,k_ [)][∥][2][ +][ βη][2][ −] _[η]_ _gi,k[(][r][)]_ _i,k_ _i,k_ [)][∥][2] (236)

2 _[∥∇][F]_ [(][x][(][r][)] 2 _∥_ _[∥][2][ +][ η]2_ _[∥][g][(][r][)]_ _[−∇][F]_ [(][x][(][r][)]

Letting η ≤ _β[1]_ [,]

_F_ (x[(]k[r]+1[)] [)][ −] _[F]_ [(][x][(]i,k[r][)][)][ ≤−] _[η]_ _i,k_ [)][∥][2][ +][ η] _i,k_ _i,k_ [)][∥][2] (237)

2 _[∥∇][F]_ [(][x][(][r][)] 2 _[∥][g][(][r][)]_ _[−∇][F]_ [(][x][(][r][)]

Conditioning on everything up to the k-th step of the r-th round,


Er,kF (x[(]i,k[r][)]+1[)][ −] _[F]_ [(][x][(]i,k[r][)][)][ ≤−] _[η]_ _i,k_ [)][∥][2][ +][ η] _i,k_ _i,k_ [)][∥][2] (238)

2 _[∥∇][F]_ [(][x][(][r][)] 2 [E][r,k][∥][g][(][r][)] _[−∇][F]_ [(][x][(][r][)]

_i,k_ [)][∥][2][ +][ ηζ] [2] + _[ησ][2]_ (239)

_≤−_ _[η]2_ _[∥∇][F]_ [(][x][(][r][)] 2 2√K

Where the last step used the fact that E[X [2]] = Var(X) + E[X], the assumption on heterogeneity
(Assumption B.5), and the assumption on gradient variance (Assumption B.6) along with the fact
that gi,k[(][r][)] [is an average over] _√K client gradient queries. Next, using µ-strong convexity of F_

(Assumption B.1),


Er,kF (x[(]i,k[r][)]+1[)][ −] _[F]_ [(][x][(]i,k[r][)][)][ ≤−][ηµ][(][F] [(][x][(]i,k[r][)][)][ −] _[F]_ [(][x][∗][)) +][ ηζ] [2] + _[ησ][2]_

2 2√K

which after taking full expectation gives

EF (x[(]i,k[r][)]+1[)][ −] _[F]_ [(][x][∗][)][ ≤] [(1][ −] _[ηµ][)(][E][F]_ [(][x][(]i,k[r][)][)][ −] _[F]_ [(][x][∗][)) +][ ηζ] [2] + _[ησ][2]_

2 2√K

Unrolling the recursion over k we get


(240)

(241)


EF (x[(]i,K[r][)] [)][ −] _[F]_ [(][x][∗][)] (242)

(1 _ηµ)√K(EF_ (xi,[(][r]0[)][)][ −] _[F]_ [(][x][∗][)) + (] _[ηζ]_ [2] + _[ησ][2]_ ) _√K−1(1_ _ηµ)[k]_ (243)
_≤_ _−_ 2 2√K _−_

_k=0_

X

Also note that x[(][r][+1)] = _S[1]_ _i_ _r_ _[x][(]i,[r]√[)]_ _K[. So by convexity of][ F]_ [,]

_∈S_

EF (x[(][r][+1)]) −PF (x[∗]) (244)

_≤_ _S[1]_ EF (x[(]i,[r]√[)] _K[)][ −]_ _[F]_ [(][x][∗][)] (245)

_iX∈Sr_


_K−1_

(1 − _ηµ)[k]_ (246)
_k=0_

X


_K(EF_ (x(r)) _F_ (x∗)) + ( _[ηζ]_ [2]
_−_ 2


+ _[ησ][2]_

_√_


_≤_ (1 − _ηµ)_


Unrolling the recursion over R, we get

EF (x[(][r][)]) − _F_ (x[∗]) (247)

_≤_ (1 − _ηµ)[r]√K(F_ (x(0)) − _F_ (x∗)) + ( _[ηζ]2[2]_ + 2[ησ]√K[2] ) _τr−=01_ _√kK=0−1(1 −_ _ηµ)[τ]_ _√K+k_ (248)

X X


-----

Which can be upper bounded as

EF (x[(][r][)]) − _F_ (x[∗]) ≤ (1 − _ηµ)[R]_


_K(F_ (x(0)) − _F_ (x∗)) + 2[ζ]µ[2] [+] 2µσ√[2]


(249)


The final statement comes from the fact that _x_ _η_ _Fi(x)_ _x[∗]i_ _i_ _β_
_∥_ _−_ _∇_ _−_ _[∥≤∥][x][ −]_ _[x][∗][∥]_ [because of][ η][ ≤] [1]

and applying triangle inequality.

E.1.2 CONVERGENCE OF FEDAVG FOR GENERAL CONVEX FUNCTIONS

For the general convex case, we use Nesterov smoothing. Concretely, we will run Algo. 3 assuming
strong convexity by optimizing instead a modified objective

_Fµ(x) = F_ (x) + _[µ]_ (250)

2

_[∥][x][(0)][ −]_ _[x][∥][2]_

Define x[∗]µ [= arg min]x _[F][µ][(][x][)][ and][ ∆][µ]_ [=][ E][F][µ][(][x][(0)][)][ −] _[F]_ [(][x][∗]µ[)][. We will choose][ µ][ carefully to balance]
the error introduced by the regularization term and the better convergence properties of having larger
_µ._


_Proof. We know that running Algo. 4 with η =_


1

_β+µ_ [gives (from the previous proof)]


_σ[2]_

) + _[ζ]_ [2]

2µ [+] 2µ√


_K_

EFµ(x[(][R][)]) _Fµ(x[∗]µ[)][ ≤]_ [∆][µ] [exp(][−] _[R]β+µ_
_−_

_µ_

We have that by (Yuan & Ma, 2020, Proposition E.7)


(251)


EF (x[(][R][)]) _F_ (x[∗]) EFµ(x[(][R][)]) _Fµ(x[∗]µ[) +][ µ]_ (252)
_−_ _≤_ _−_ 2 _[D][2]_

So we have (because ∆µ ∆ as shown in Thm. D.3),
_≤_

_√K_ _σ[2]_
EF (x[(][R][)]) _F_ (x[∗]) ∆exp( _β+µ_ ) + _[ζ]_ [2] + _[µ]_ (253)
_−_ _≤_ _−_ _[R]_ 2µ [+] 2µ√K 2 _[D][2]_


_β_

_KR_ [log][2][(][e][2][ +]


_KR)), µ ≥_ Θ( _D[ζ]_ [)][, and][ µ][ ≥] [Θ(] _DKσ[1][/][4][ )][,]_


Then if we choose µ ≥ Θ(


EF (x[(][R][)]) − _F_ (x[∗]) ≤ _O[˜](_ _√[βD]KR[2]_ + _K[σD][1][/][4][ +][ ζD][)]_ (254)

Now we show the distance bound. Recall that


_σ[2]_

) + _[ζ]_ [2]

2µ [+] 2µ√


_√K_
EFµ(x[(][R][)]) _Fµ(x[∗]µ[)][ ≤]_ [∆][µ] [exp(][−] _[R]β+µ_
_−_


(255)


By smoothness, strong convexity of Fµ, and the choice of µ (as we chose each term above divided by
_µ to match D[2]_ up to log factors), we have that


E∥x[(][R][)] _−_ _x[∗]µ[∥][2][ ≤]_ _O[˜](D[2])_ (256)


So,


E∥x[(][R][)] _−_ _x[∗]∥[2]_ _≤_ 3E∥x[(][R][)] _−_ _x[∗]µ[∥][2][ + 3][E][∥][x][(0)][ −]_ _[x][∗]µ[∥][2][ + 3][E][∥][x][∗]_ _[−]_ _[x][(0)][∥][2][ ≤]_ _O[˜](D[2])_ (257)

Where the last inequality follows because

_F_ (x[∗]µ[) +][ µ] _µ[∥][2][ ≤]_ _[F]_ [(][x][∗][) +][ µ] (258)

2 2

_[∥][x][(0)][ −]_ _[x][∗]_ _[∥][x][(0)][ −]_ _[x][∗][∥][2]_


E.1.3 CONVERGENCE OF FEDAVG UNDER THE PL CONDITION

_Proof. The same proof follows as in the strongly convex case, except Eq. (244), where we avoid_
having to use convexity by only sampling one client at a time. This follows previous work such as
Karimireddy et al. (2020a). Averaging when the functions are not convex can cause the error to blow
up, though in practice this is not seen (as mentioned in Karimireddy et al. (2020a)).


-----

F PROOFS FOR FEDCHAIN

F.1 FEDAVG → SGD

F.1.1 CONVERGENCE OF FEDAVG → SGD ON STRONGLY CONVEX FUNCTIONS

**Theorem F.1. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4,**
_Assumption B.6, Assumption B.7, Assumption B.5, Assumption B.8. Then running Algo. 1 where_
_Alocal is Algo. 4 in the setting of Thm. E.1 and Aglobal is Algo. 2 in the setting Thm. D.1:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. Then there exists a lower bound of
_K such that we have the rate_


_σ[2]_

_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ _[R]κ_ [) +] _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [+]


1
_−_ _N[S]_


_ζF_



-  General convex: Fi’s satisfy Assumption B.2. Then there exists a lower bound of K such
_that we have the rate_

˜( min _, [βD][2]_
_O_ _{_ _[β][1][/][2]R[ζ]_ [1][1][/][/][2][2][D][3][/][2] _R_ (SKR)[1][/][4]

_[}][ +][ β][1][/][2][σ][1][/][2][D][3][/][2]_

+ (1 _F_ _D_ )
_−_ _N[S]_ [)][1][/][4][ β]S[1][1][/][/][2][4][ζ]R[1][/][1][2][/][2][ + (1][ −] _N[S]_ [)][1][/][4][ β][1][/]([2]SR[ζ] [1][/])[2][1][D][/][4][3][/][2]



-  PL condition: Fi’s satisfy Assumption B.3 for µ > 0. Then there exists a lower bound of K
_such that we have the rate_


_κσ[2]_

_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ _[R]κ_ [) +] _µNKR_ [+ (1][ −] _N[S]_ [)][ κζ]µSR[2] [+]


1
_−_ _N[S]_


_ζF_


_Proof. From Thm. E.1, we know that with K > max{_ _[σ]ζ[4][4][,][ κ]R[2][2][ log][2][(][ ∆]ζ[2][µ][ )][}]_

EF (ˆx1/2) _F_ (x[∗]) ( _[ζ]_ [2] (259)
_−_ _≤O_ _µ_ [)]


From Lemma H.2, if K > _σF[2]_

_S min{∆,_ _[ζ]µ[2]_ _[}]_

EF (ˆx1) − _F_ (x[∗]) ≤O(min{ _[ζ]µ [2]_ _[,][ ∆][}][ +]_


_ζF_

1 − _N[S][ −] −_ [1]1 _√S_


(260)


And so from Thm. D.1, we know that


EF (ˆx2) − _F_ (x[∗]) (261)

_σ[2]_ _ζF_

_≤_ _O[˜](min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ _[R]κ_ [) +] _µNKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [+] 1 − _N[S]_ _√S_ )) (262)

r

F.1.2 CONVERGENCE OF FEDAVG → SGD ON GENERAL CONVEX FUNCTIONS

_Proof. From Thm. E.1, we know that with K > max_ _[σ]ζ[4][4][,][ β]ζR[2][D][2]_
_{_ _[}]_

EF (x[(][R][)]) − _F_ (x[∗]) ≤ _O[˜](ζD)_

From Lemma H.2, if K > _σF[2]_

_S min{∆,_ _[ζ]µ[2]_ _[}]_


_ζF_

1 − _N[S][ −]_ [1]1 _√_

_−_


EF (ˆx1) − _F_ (x[∗]) ≤ _O[˜](min{ζD, ∆} +_


(263)


-----

And so from Thm. D.1, we know that

E _F_ (ˆx2) ( _[β][ min][{][ζD,][ ∆][}]_
_∥∇_ _∥[2]_ _≤_ _O[˜]_ _R_


1
_−_ _N[S]_


_βζF_ _βσD_
_√SR_ + _√SKR_


1
_−_ _N[S]_


_βζD_
_√SR_ ) (264)


Next, using that E∥xˆ2 − _x[∗]∥≤_ _O[˜](D[2]) from Thm. E.1 and Thm. D.1 as well as convexity,_

EF (ˆx2) − _F_ (x[∗]) (265)

_≤_ E∥∇F (ˆx2)∥[2][p]E∥xˆ2 − _x[∗]∥[2]_ (266)
p

( _[β][1][/][2][ min][{][ζ]_ [1][/][2][D][3][/][2][,][ ∆][1][/][2][D][}] (267)
_≤_ _O[˜]_ _R[1][/][2]_

+ _[β][1][/][2][σ][1][/][2][D][3][/][2]_ + (1 _F_ _D_ ) (268)

(SKR)[1][/][4] _−_ _N[S]_ [)][1][/][4][ β]S[1][1][/][/][2][4][ζ]R[1][/][1][2][/][2][ + (1][ −] _N[S]_ [)][1][/][4][ β][1][/]([2]SR[ζ] [1][/])[2][1][D][/][4][3][/][2]


One can pre-run SGD before all of this for a constant fraction of rounds so that (Woodworth et al.,
2020a, Section 7):


∆ ( _[βD][2]_
_≤_ _O[˜]_ _R_


_σD_

_SKR_


1
_−_ _N[S]_


_ζD_
_√SR_ ) (269)


This likely not practically necessary § 6. Altogether,

EF (ˆx2) − _F_ (x[∗]) (270)

_≤_ E∥∇F (ˆx2)∥[2][p]E∥xˆ2 − _x[∗]∥[2]_ (271)
p

(min _, [βD][2]_ (272)
_≤_ _O[˜]_ _{_ _[β][1][/][2]R[ζ]_ [1][1][/][/][2][2][D][3][/][2] _R_

_[}]_

+ _[β][1][/][2][σ][1][/][2][D][3][/][2]_ + (1 _F_ _D_ ) (273)

(SKR)[1][/][4] _−_ _N[S]_ [)][1][/][4][ β]S[1][1][/][/][2][4][ζ]R[1][/][1][2][/][2][ + (1][ −] _N[S]_ [)][1][/][4][ β][1][/]([2]SR[ζ] [1][/])[2][1][D][/][4][3][/][2]


F.1.3 CONVERGENCE OF FEDAVG → SGD UNDER THE PL-CONDITION

_Proof. The proof is the same as in the strongly convex case._

F.2 FEDAVG → ASG

**Theorem F.2. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4,**
_Assumption B.6, Assumption B.7, Assumption B.5, Assumption B.8. Then running Algo. 1 where_
_Alocal is Algo. 4 in the setting of Thm. E.1 and Aglobal is Algo. 3 in the setting Thm. D.1:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. Then there exists a lower bound of
_K (same as in FedAvg →_ _SGD) such that we have the rate_


_σ[2]_

_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ _√[R]κ_ ) + _µSKR_ [+ (1][ −] _N[S]_ [)][ ζ]µSR[2] [+]


1
_−_ _N[S]_


_ζF_



-  General convex: Fi’s satisfy Assumption B.2. Then there exists a lower bound of K (same
_as in FedAvg →_ _SGD) such that we have the rate_

_σD_ _ζD_

˜( min _, [βD][2]_ +
_O_ _{_ _[β][1][/][2][ζ]_ [1]R[/][2][D][3][/][2] _R[2][ }][ +][ β][1]([/]SKR[2][σ][1][/][2])[D][1][/][3][4][/][2]_ (SKR)[1][/][2][ + (1][ −] _N[S]_ [)][1][/][2] (SR)[1][/][2]

+ (1 _F_ _D_ )
_−_ _N[S]_ [)][1][/][4][ β]S[1][1][/][/][2][4][ζ]R[1][/][1][2][/][2][ + (1][ −] _N[S]_ [)][1][/][4][ β][1][/]([2]SR[ζ] [1][/])[2][1][D][/][4][3][/][2]

Proof follows those of FedAvg → SGD (Thm. F.1).


-----

F.3 FEDAVG → SAGA

**Theorem F.3. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4,**
_Assumption B.6, Assumption B.7, Assumption B.5, Assumption B.8. Then running Algo. 1 where_
_Alocal is Algo. 4 in the setting of Thm. E.1 and Aglobal is Algo. 5 in the setting Thm. D.4:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. Then there exists a lower bound of
_K (same as in FedAvg →_ _SGD) such that we have the rate_

_σ[2]_

_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ [max][{] _[N]S [, κ][}][−][1][R][) +]_ _µSKR_ [)]

-  PL condition: Fi’s satisfy Assumption B.3 for µ > 0. Then there exists a lower bound of K
_such that we have the rate_


_σ[2]_

_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−][(][κ][(]_ _[N]S_ [)][2][/][3][)][−][1][R][) +] _µSK_ [)]

Proof follows those of FedAvg → SGD (Thm. F.1) and using Lemma H.2 with S = N as the
algorithm already requires R > _[N]S_ [.]

F.4 FEDAVG → SSNM

**Theorem F.4. Suppose that client objectives Fi’s and their gradient queries satisfy Assumption B.4,**
_Assumption B.6, Assumption B.5, Assumption B.8. Then running Algo. 1 where Alocal is Algo. 4 in_
_the setting of Thm. E.1 and Aglobal is Algo. 6 in the setting Thm. D.5:_

-  Strongly convex: Fi’s satisfy Assumption B.1 for µ > 0. Then there exists a lower bound of
_K (same as in FedAvg →_ _SGD) such that we have the rate_


_O˜(min{_ _[ζ]µ [2]_ _[,][ ∆][}][ exp(][−]_ [max][{] _[N]S [,]_


_κ(_ _[N]_

_S_ [)][}][−][1][R][) +][ κσ]µKS[2] [)]


Proof follows those of FedAvg → SGD (Thm. F.1) and using Lemma H.2 with S = N as the
algorithm already requires R > _[N]S_ [.]

G LOWER BOUND


In this section we prove the lower bound. All gradients will be noiseless, and we will allow full
communication to all clients every round. There will be only two functions in this lower bound: F1
and F2. If N > 2, then F1 is assigned to the first ⌊N/2⌋ clients and F2 to the next ⌊N/2⌋ clients. If
there is an odd number of machines we let the last machine be F3(x) = _[µ]2_

the lower bound by a factor of at most _[N]N[−][1]_ [. So we look at the case][ N][ = 2][.][∥][x][∥][2][. This only reduces]

Let ℓ2, C, _ζ[ˆ] be values to be chosen later. Let d be even. At a high level, ℓ2 essentially controls the_
smoothness of F1 and F2, C is basically a constant, and _ζ[ˆ] is a quantity that affects the heterogeneity,_
initial suboptimality gap, and initial distance. We give the instance:


_d_
2

_[−][1]_

(x2i+1 _x2i)[2]_ + _[µ]_ (274)
_i=1_ _−_ 2 _[∥][x][∥][2]_

X


_F1(x) =_ _ℓ2ζx[ˆ]_ 1 + _[Cℓ][2]_ _d_ [+][ ℓ][2]
_−_ 2 _[x][2]_ 2


_d/2_

_i=1(x2i −_ _x2i−1)[2]_ + _[µ]2_ _[∥][x][∥][2]_ (275)

X


_F2(x) =_ _[ℓ][2]_


Where F = _[F][1][+]2_ _[F][2]_ .

These functions are the same as those used in (Woodworth et al., 2020a; Woodworth, 2021) for
lower bounds in distributed optimization. They are also similar to the instances used to prove convex


-----

optimization lower bounds (Nesterov, 2003) and distributed optimization lower bounds (Arjevani &
Shamir, 2015).

These two functions have the following property

_F1(xeven)_ span _e1, e2, . . ., e2i+1_
_xeven_ span _e1, e2, . . ., e2i_ = _∇_ _∈_ _{_ _}_ (276)
_∈_ _{_ _}_ _⇒_ _F2(xeven)_ span _e1, e2, . . ., e2i_
∇ _∈_ _{_ _}_

_xodd ∈_ span{e1, e2, . . ., e2i−1} =⇒ _∇FF21((xxoddodd)) ∈_ spanspan{ee11, e, e22, . . ., e, . . ., e22ii−1} (277)
∇ _∈_ _{_ _}_

What the property roughly says is the following. Suppose we so far have managed to turn an
even number of coordinates nonzero. Then we can only use gradient queries of F1 to access the
next coordinate. After client 1 queries the gradient of F1, it now has an odd number of unlocked
coordinates, and cannot unlock any more coordinates until a communication occurs. Similar is true if
the number of unlocked coordinates is odd. And so each round of communication can only unlock a
single new coordinate.

We start by writing out the gradients of F1 and F2. Assume that d is even. Then:



[∇F1(x)]1 = −ℓ2ζ[ˆ] + µx1 (278)

[∇F1(x)]d = Cℓ2xd + µxd (279)

[ _F1(x)]i = ℓ2(xi_ _xi_ 1) + µxi i odd, 2 _i_ _d_ 1
_∇_ _−_ _−_ _≤_ _≤_ _−_ (280)

[ _F1(x)]i =_ _ℓ2(xi+1_ _xi) + µxi i even, 2_ _i_ _d_ 1
 _∇_ _−_ _−_ _≤_ _≤_ _−_

[∇F2(x)]1 = −ℓ2(x2 − _x1) + µx1_ (281)

[ _F2(x)]d = ℓ2(xd_ _xd_ 1) + µxd (282)
_∇_ _−_ _−_

[ _F2(x)]i =_ _ℓ2(xi+1_ _xi) + µxi i odd, 2_ _i_ _d_ 1
_∇_ _−_ _−_ _≤_ _≤_ _−_ (283)

[ _F2(x)]i = ℓ2(xi_ _xi_ 1) + µxi i even, 2 _i_ _d_ 1
 _∇_ _−_ _−_ _≤_ _≤_ _−_


and


We define the class of functions that our lower bound will apply to. This definition follows (Woodworth et al., 2020a; Woodworth, 2021; Carmon et al., 2020):
**Definition G.1 (Distributed zero-respecting algorithm). For a vector v, let supp(v) = {i ∈**
1, . . ., d : vi = 0 . We say that an optimization algorithm is distributed zero-respecting if
_{_ _}_ _̸_ _}_
for any i, k, r, the k-th iterate on the i-th client in the r-th round x[(]i,k[r][)] [satisfy]


supp(∇Fi′ (x[(]i[′][r],k[′][)][′] [))] (284)
_i[′]∈[N_ ],0≤k[′][≤K−1,0≤r[′]<r


supp(x[(]i,k[r][)][)][ ⊆]


supp(∇Fi(x[(]i,k[r][)][′] [))]
0≤[k[′]<k


Broadly speaking, distributed zero-respecting algorithms are those whose iterates have components
in only dimensions that they can possibly have information on. As discussed in (Woodworth et al.,
2020a), this means that algorithms which are not distributed zero-respecting are just ”wild guessing”.
Algorithms that are distributed zero-respecting include SGD, ASG, FedAvg, SCAFFOLD, SAGA,
and SSNM.

Next, we define the next condition we require on algorithms for our lower bound.
**Definition G.2. We say that an algorithm is distributed distance-conserving if for any i, k, r, we have**
for the k-th iterate on the i-th client in the r-th round x[(]i,k[r][)] [satisfies][ ∥][x]i,k[(][r][)] _[−]_ _[x][∗][∥][2][ ≤]_ [(][c/][2)[][∥][x][init][ −]

_xinitial iterate, for some scalar parameter[∗]∥[2]_ + _i=1_ _[∥][x][init][ −]_ _[x]i[∗][∥][2][]][, where][ x]j[∗]_ [:= arg min] c. _x_ _[F][j][(][x][)][ and][ x][∗]_ [:= arg min]x _[F]_ [(][x][)][ and][ x][init][ is the]

[P][N]

Algorithms which do not satisfy Definition 5.2 for polylogarithmic c in problem parameters (see § 2)
are those that move substantially far away from x[∗], even farther than the x[∗]i [’s are from][ x][∗][. With this]
definition in mind, we slightly overload the usual definition of heterogeneity for the lower bound:
**Definition** **G.3.** A distributed optimization problem is (ζ, c)-heterogeneous if
maxi [N ] supx _A_ _Fi(x)_ _F_ (x) _ζ_ [2], where we define A := _x :_ _x_ _x[∗]_
_∈_ _∈_ _∥∇_ _−∇_ _∥[2]_ _≤_ _{_ _∥_ _−_ _∥[2]_ _≤_
(c/2)( _xinit_ _x[∗]_ + _i=1_
_∥_ _−_ _∥[2]_ _[∥][x][init][ −]_ _[x][∗][∥][2][)][}][ for some scalar parameter][ c][.]_

[P][N]


-----

While convergence rates in FL are usually proven under Assumption B.5, the proofs can be converted
to work under Definition G.3 as well, so long as one can prove all iterates stay within A as defined
in Definition G.3. We show that our algorithms satisfy Definition G.3 as well as a result (Thm. E.1,
Thm. D.3, Thm. D.1)[4]. Other proofs of FL algorithms also satisfy this requirement, most notably the
proof of the convergence of FedAvg in Woodworth et al. (2020a).

Following (Woodworth et al., 2020a), we start by making the argument that, given the algorithm is
distributed zero-respecting, we can only unlock one coordinate at a time. Let Ei = span{e1, . . ., ei},
and E0 be the null span. Then
**Lemma G.4. Let ˆx be the output of a distributed zero-respecting algorithm optimizing F =** 2[1] [(][F][1][ +]

_F2) after R rounds of communication. Then we have_

supp(ˆx) _ER_ (285)
_∈_

_Proof. A proof is in Woodworth et al. (2020a, Lemma 9)._

We now compute various properties of this distributed optimization problem.

G.1 STRONG CONVEXITY AND SMOOTHNESS OF F, F1, F2

From Woodworth (2021, Lemma 25), as long asµ-strongly convex. _ℓ2 ≤_ _[β][−]4_ _[µ]_ [, we have that][ F, F][1][, F][2][ are][ β][-smooth and]

G.2 THE SOLUTIONS OF F, F1, F2

First, observe that from the gradient of F2 computed in Eq. (281), x[∗]2 [= arg min]x _[F][2][(][x][) =][ ⃗]0. Next_
observe that from the gradient of F1 computed in Eq. (278), x[∗]1 [= arg min]x _[F][1][(][x][) =][ ℓ]µ[2][ ˆ]ζ_ _[e][1][. Thus]_

2ζ[ˆ][2]
_∥x[∗]2[∥][2][ = 0][ and][ ∥][x][∗]1[∥][2][ =][ ℓ]µ[2]_ [2][ .]

From Woodworth (2021, Lemma 25), if we let α = 1 + [2]µ[ℓ][2] [,][ q][ =] _αα−+11_ [,][ C][ = 1][ −] _[q][, then]_

_x[∗]_ = (1 _ζˆ[2]q)[2]_ _di=1_ _[q][2][i][ =]_ (1ζˆ[2]qq[2])(1[2](1−q[2]q[d][2])) [.] q
_∥_ _∥[2]_ _−_ _−_ _−_

P

G.3 INITIAL SUBOPTIMALITY GAP

_qℓ2ζ[ˆ][2]_
From Woodworth (2021, Lemma 25), F (0) − _F_ (x[∗]) ≤ 4(1−q) [.]


G.4 SUBOPTIMALITY GAP AFTER R ROUNDS OF COMMUNICATION

_ζˆ[2]µq[2]_
From (Woodworth, 2021, Lemma 25),log 2 _F_ (ˆx) − _F_ (x[∗]) ≥ 16(1−q)[2](1−q[2]) _[q][2][R][, as long as][ d][ ≥]_ _[R][ +]_

2 log(1/q) [.]


G.5 COMPUTATION OF ζ [2]

We start by writing out the difference between the gradient of F1 and F2, using Eq. (278) and
Eq. (281).


_d−1_

_ℓ[2]2[(][x][i][+1]_
_i=2_ _[−]_ _[x][i][−][1][)][2]_

X

(286)


_F1(x)_ _F2(x)_ = ℓ[2]2[(][−]ζ[ˆ] + x2 _x1)[2]_ + ℓ[2]2[(][Cx][d] [+][ x][d][−][1][)][2][ +]
_∥∇_ _−∇_ _∥[2]_ _−_ _[−]_ _[x][d]_

We upper bound each of the terms:


(xi+1 _xi_ 1)[2] = x[2]i+1 [+][ x][2]i 1 _i+1_ [+ 2][x]i[2] 1 (287)
_−_ _−_ _[−]_ [2][x][i][+1][x][i][−][1] _−_ _[≤]_ [2][x][2] _−_

4We do not formally show it for SAGA and SSNM, as the algorithms are functionally the same as SGD and
ASG under full participation.


-----

(−ζ[ˆ] + x2 − _x1)[2]_ = ζ[ˆ][2] + x[2]2 [+][ x]1[2] _[−]_ [2ˆ]ζx2 + 2ζx[ˆ] 1 − 2x2x1 (288)

_≤_ 3ζ[ˆ][2] + 3x[2]2 [+ 3][x]1[2] (289)


(Cxd − _xd + xd−1)[2]_ = C [2]x[2]d [+][ x]d[2] [+][ x]d[2]−1 _[−]_ [2][Cx]d[2] [+ 2][Cx][d][x][d][−][1] _[−]_ [2][x][d][x][d][−][1] (290)

_C_ [2]x[2]d [+ 2][x]d[2] [+ 2][x]d[2] 1 [+ 2][Cx]d[2] 1 (291)
_≤_ _−_ _−_

So altogether, using the fact that C ≤ 1,

1

_F1(x)_ _F2(x)_ (292)
_ℓ[2]2_ _∥∇_ _−∇_ _∥[2]_


_d−1_

2x[2]i+1 [+ 2][x]i[2] 1 (293)
_−_
_i=2_

X


3ζ[ˆ][2] + 3x[2]2 [+ 3][x]1[2] [+ 3][x]d[2] [+ 3][x]d[2] 1 [+]
_≤_ _−_


_≤_ 3ζ[ˆ][2] + 7∥x∥[2] (294)

_≤_ 3ζ[ˆ][2] + 14∥x − _x[∗]∥[2]_ + 14∥x[∗]∥[2] (295)

_ζˆ[2]q[2]_ 2ζ[ˆ][2]
5ζ[ˆ][2] + 28c (296)
_≤_ (1 _q)[2](1_ _q[2]) [+ 28][cℓ]µ[2]_ [2]

_−_ _−_

Next we use Definition G.2 which says that ∥x − _x[∗]∥≤_ 2[c] [[][∥][x][init][ −] _[x][∗][∥][2][ +][ P]i[N]=1_ _[∥]ζˆ[x][2]q[init][2]_ _[ −]_ _[x]i[∗][∥][2][]][. For]_

ease of calculation, we assume c ≥ 1. Recall that we calculated ∥x[∗]∥[2] _≤_ (1−q)[2](1−q[2]) [(because]

2ζ[ˆ][2]
0 < q < 1), ∥x[∗]2[∥][2][ = 0][,][ ∥][x][∗]1[∥][2][ =][ ℓ]µ[2] [2][ .]

1

_F1(x)_ _F2(x)_ 3ζ[ˆ][2] + 24c _x[∗]_ + 7c _x[∗]1[∥][2][ + 7][c][∥][x]2[∗][∥][2]_ (297)
_ℓ[2]2_ _∥∇_ _−∇_ _∥[2]_ _≤_ _∥_ _∥[2]_ _∥_


24cζ[ˆ][2]q[2] 2ζ[ˆ][2]
3ζ[ˆ][2] + (298)
_≤_ (1 _q)[2](1_ _q[2]) [+ 7][cℓ]µ[2][2]_

_−_ _−_

24cℓ[2]2ζ[ˆ][2]q[2] 2ζ[ˆ][2]
_F1(x)_ _F2(x)_ 3ℓ[2]2ζ[ˆ][2] + (299)
_∥∇_ _−∇_ _∥[2]_ _≤_ (1 _q)[2](1_ _q[2]) [+ 7][cℓ]µ[4][2]_

_−_ _−_


Altogether,

G.6 THEOREM


With all of the computations earlier, we are now prepared to prove the theorem.
**Theorem G.5. For any number of rounds R, number of local steps per-round K, and (ζ, c)-**
_heterogeneity (Definition 5.3), there exists a global objective F which is the average of two β-smooth_
_(Assumption B.4) and µ(≥_ 0)-strongly convex (Assumption B.1) quadratic client objectives F1 and
_F2 with an initial sub-optimality gap of ∆, such that the output ˆx of any distributed zero-respecting_
_(Definition 5.1) and distance-conserving algorithm (Definition 5.2) satisfies_

-  Strongly convex: F (ˆx) − _F_ (x[∗]) ≥ Ω(min{∆, 1/(cκ[3][/][2])(ζ [2]/β)} exp(−R/[√]κ).) when
_µ > 0, and_

-  General Convex F (ˆx) − _F_ (x[∗]) ≥ Ω(min{βD[2]/R[2], ζD/(c[1][/][2][√]R[5])}) when µ = 0.

_Proof. The convex case: By the previous computations, we know that after R rounds,_


_µζ[ˆ][2]q[2]_
_F_ (ˆx) _F_ (x[∗]) (300)
_−_ _≥_ 16(1 _q)[2](1_ _q[2])_ _[q][2][R]_

_−_ _−_

_ζˆ[2]q[2]_
_x[∗]_ (301)
_∥_ _∥[2]_ _≤_ (1 _q)[2](1_ _q[2])_

_−_ _−_

24cℓ[2]2ζ[ˆ][2]q[2] 2ζ[ˆ][2]
_F1(x)_ _F2(x)_ 3ℓ[2]2ζ[ˆ][2] + (302)
_∥∇_ _−∇_ _∥[2]_ _≤_ (1 _q)[2](1_ _q[2]) [+ 7][cℓ]µ[4][2]_

_−_ _−_


-----

To maintain the property that ∥x[(0)] _−_ _x[∗]∥_ = ∥x[∗]∥≤ _D and Definition G.3, Choose_ _ζ[ˆ] s.t._

_ζˆ[2]_ = ν min _,_ [(1][ −] _[q][)][2][(1][ −]_ _[q][2][)][ζ]_ [2] _, [µ][2][ζ]_ [2] _,_ [(1][ −] _[q][)][2][(1][ −]_ _[q][2][)][D][2]_ (303)
_{_ _[ζ]ℓ[2]2[2]_ _cℓ[2]2[q][2]_ _cℓ[4]2_ _q[2]_ _}_


For an absolute constant ν.

This leads to (throughout we use _ℓ[µ]2_ [=][ (1][−]2q[q][)][2], (Woodworth, 2021, Eq 769))


_F_ (ˆx) − _F_ (x[∗]) (304)

_µζ[ˆ][2]q[2]_

(305)

_≥_ 16(1 _q)[2](1_ _q[2])_ _[q][2][R]_

_−_ _−_

_q[2]_

_ν min_ _, [µ][(1][ −]_ _[q][)][2][(1][ −]_ _[q][2][)][ζ]_ [2] _, [µ][3][ζ]_ [2] _, [µ][(1][ −]_ _[q][)][2][(1][ −]_ _[q][2][)][D][2]_
_≥_ _{_ _[µζ]ℓ[2]2[2]_ _cℓ[2]2[q][2]_ _cℓ[4]2_ _q[2]_ _}_ 16(1 _q)[2](1_ _q[2])_ _[q][2][R]_

_−_ _−_

(306)

_ν min_ _, [µ][(1][ −]_ _[q][)][2][(1][ −]_ _[q][2][)][ζ]_ [2] _,_ (307)
_≥_ _{_ [(1][ −]2ℓ[q]2[)]q[2][ζ] [2] _cℓ[2]2[q][2]_

_µζ_ [2](1 − _q)[4]_ _, [µ][(1][ −]_ _[q][)][2][(1][ −]_ _[q][2][)][D][2]_ _q[2]_ (308)

4cℓ[2]2[q][2] _q[2]_ _}_ 16(1 − _q)[2](1 −_ _q[2])_ _[q][2][R]_

_ζ_ [2]q
_ν min_ _, [µζ]_ [2][(1][ −] _[q][)]_ (309)
_≥_ _{_ 32ℓ2(1 _q[2])_ _[, µζ]16cℓ[2][2]2_ 64cℓ[2]2[(1 +][ q][)] _[, µD]16[2]_

_−_ _[}][q][2][R]_

(310)


We choose µ = 64ℓR2 [2][, which ensures][ α][ ≥] [2][. So noting that][ (1][ −] _[q][2][) = (1][ −]_ _[q][)(1 +][ q][)][ ≤]_ [(1 +][ q][)][,]

1 + q = _α2+1α_ [,][ 1][ −] _[q][ =]_ _α+12_ [:]

_F_ (ˆx) − _F_ (x[∗]) (311)

_α + 1_ 2 _α + 1_

_ν min_ _[ζ]_ [2] ( _[α][ −]_ [1] _, [µζ]_ [2] ( (312)
_≥_ _{_ 32ℓ2 _α + 1_ 2α [)][, µζ]16cℓ[2][2]2 64cℓ[2]2 _α + 1_ 2α [)][, µD]16[2]

_[}][q][2][R]_

_α + 1_ 2 _α + 1_

_ν min_ _[ζ]_ [2] ( _[α][ −]_ [1] _, [µζ]_ [2] (
_≥_ _{_ 32ℓ2 _α + 1_ 2α [)][, µζ]16cℓ[2][2]2 64cℓ[2]2 _α + 1_ 2α [)][, µD]16[2] _α_ 1 [))]

_[}][ exp(][−][2][R][ log(]_ _[α][ + 1] −_

(313)

_ν min_ _[ζ]_ [2] _, [µζ]_ [2] _, [µζ]_ [2] ( [1] (314)
_≥_ _{_ 64ℓ2 16cℓ[2]2 64cℓ[2]2 _α_ [)][, µD]16[2] _α_ 1 [)]

_[}][ exp(][−]_ [4] −[R]


So,


_F_ (ˆx) − _F_ (x[∗]) (315)

_≥_ _ν min{_ 64[ζ] [2]ℓ2 _, 16[µζ]cℓ[2][2]2_ _, 64[µζ]cℓ[2][2]2_ ( 3[µ]ℓ2 )[1][/][2], [µD]16[2] _√ℓ2_ ) (316)

_[}][ exp(][−]_ [8][R][√][µ]

_ζ_ [2] _ζ_ [2]

Ω(min _,_ (317)
_≥_ _{_ _[ζ]ℓ2[2]_ _cℓ2R[2][,]_ _cℓ2R[3][, ℓ][2]R[D][2][ }][2]_ [)]

_ζ_ [2]
Ω( (318)
_≥_ _cℓ2R[3][, ℓ][2]R[D][2][ }][2]_ [)]

(319)


Where we used c > 1. Setting ℓ2 = Θ(min{β, _c[1][/][2]DRζ_ [1][/][2][ }][)][ (which will ensure that][ ℓ][2][ ≤] _[β][−]4_ _[µ]_ with

appropriate constants chosen), Which altogether gives us

_ζD_
_F_ (ˆx) _F_ (x[∗]) Ω(min (320)
_−_ _≥_ _{_ _c[1][/][2]R[5][/][2][, βD]R[2][2][ }][)]_


**Strongly Convex Case:**


-----

By the previous computations, we know that after R rounds,

_µζ[ˆ][2]q[2]_
_F_ (ˆx) _F_ (x[∗]) (321)
_−_ _≥_ 16(1 _q)[2](1_ _q[2])_ _[q][2][R]_

_−_ _−_

_qℓ2ζ[ˆ][2]_
_F_ (ˆx) _F_ (x[∗]) (322)
_−_ _≤_ 4(1 _q)_

_−_

24cℓ[2]2ζ[ˆ][2]q[2] 2ζ[ˆ][2]
_F1(x)_ _F2(x)_ 3ℓ[2]2ζ[ˆ][2] + (323)
_∥∇_ _−∇_ _∥[2]_ _≤_ (1 _q)[2](1_ _q[2]) [+ 7][cℓ]µ[4][2]_

_−_ _−_

To maintain the property that F (ˆx) _F_ (x[∗]) ∆ and that _F1(x)_ _F2(x)_ _ζ_ [2] for all x
_−_ _≤_ _∥∇_ _−∇_ _∥[2]_ _≤_
encountered during the execution of the algorithm,


Choose _ζ[ˆ] s.t._

For some constant ν.


_ζˆ[2]_ = ν min _,_ [(1][ −] _[q][)][2][(1][ −]_ _[q][2][)][ζ]_ [2] _, [µ][2][ζ]_ [2] _,_ [(1][ −] _[q][)∆]_ (324)
_{_ _[ζ]ℓ[2]2[2]_ _cℓ[2]2[q][2]_ _cℓ[4]2_ _qℓ2_ _}_


Again using _ℓ[µ]2_ [=][ (1][−]2q[q][)][2] ) and following the same calculations as in the convex case, we use the fact

that 9µ ≤ _β, and that it is possible to choose ℓ2 s.t. 2µ ≤_ _ℓ2 ≤_ _[β][−]4_ _[µ]_ [, which ensures][ β][ ≥] [2][.]

_F_ (ˆx) − _F_ (x[∗]) (325)

_µζ[ˆ][2]q[2]_

(326)

_≥_ 16(1 _q)[2](1_ _q[2])_ _[q][2][R]_

_−_ _−_

_ν min_ _[ζ]_ [2] _, [µζ]_ [2] _, [µζ]_ [2] ( [1] (327)
_≥_ _{_ 64ℓ2 16cℓ[2]2 64cℓ[2]2 _α_ [)][,][ ∆]4 _α_ 1 [)]

_[}][ exp(][−]_ [4] −[R]

(328)

We use 9µ _β and because it is possible to choose ℓ2 such that 2µ_ _ℓ2_ 4 (Woodworth, 2021,

Eq. 800), which ensures ≤ _α_ 2 and _α[1]_ 3µℓ2 _≤_ _≤_ _[β][−][µ]_
_≥_ _[≥]_

q

_F_ (ˆx) − _F_ (x[∗]) (329)

_≥_ Ω(min{ _[ζ]ℓ2[2]_ _, [µζ]cℓ[2]2[2]_ _, [µζ]cℓ[2]2[2]_ ( _ℓ[µ]2_ )[1][/][2], ∆} exp(− [8][R]√[√]ℓ2[µ] )) (330)

_≥_ Ω(min{ _[µζ]cℓ[2]2[2]_ ( _ℓ[µ]2_ )[1][/][2], ∆} exp(− [8][R]√[√]ℓ2[µ] )) (331)

Next we note that ℓ2 ≤ _β and ℓ2 ≥_ _[β]5_ [(Woodworth, 2021, Eq 801), which gives us]

_F_ (ˆx) − _F_ (x[∗]) ≥ Ω(min{ _[µ]cβ[3][/][5][2][/][ζ][2][2][,][ ∆][}][ exp(][−]_ [18]√[R]κ )) (332)

H TECHNICAL LEMMAS

**Lemma H.1. Let**


_g[(][r][)]_ :=


1
_g[(][r][)]_ := _SK_ _gi,k[(][r][)]_ (333)

_iX∈Sr_ _kX=1_

_Given Assumption B.6, Assumption B.5, and uniformly sampled clients per round,_


_SK_


_K_

_gi,k[(][r][)]_ _SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_
_k=1_ _[−∇][F]_ [(][x][(][r][)][)][∥][2][ ≤] _[σ][2]_ _−_

X


E
_∥_ _SK[1]_


(334)


_i∈Sr_


-----

_If instead the clients are arbitrarily (possibly randomly) sampled and there is no gradient variance,_


_∥_ _SK[1]_


_gi,k[(][r][)]_ (335)
_k=1_ _[−∇][F]_ [(][x][(][r][)][)][∥][2][ ≤] _[ζ]_ [2]

X


_i∈Sr_


_Proof._


E
_∥_ _SK[1]_

= E
_∥_ _S[1]_

E
_≤_ _∥_ _S[1]_


_f_ (x; zi) _F_ (x) (336)
_∇_ _−∇_ _∥[2]_

_iX∈Sr_ _kX=1_


_K−1_

_f_ (x; zi) _Fi(x)_ (337)
_∇_ _−∇_ _∥[2]_
_k=0_

X


_Fi(x)_ _F_ (x) + E _r_
_∇_ _−∇_ _∥[2]_ _S_ _∥_ _SK[1]_
_iX∈Sr_


_i∈Sr_


_Fi(x)_ _F_ (x) +
_∇_ _−∇_ _∥[2]_
_iX∈Sr_


1

(338)
_SK_ [E][∥∇][f] [(][x][;][ z][i][)][ −∇][F][i][(][x][)][∥][2]

(339)


Where the first inequality uses the fact that E[X [2]] = Var(X) + E[X][2], and the second equality
uses the fact that the variance is i.i.d across i and k. Note that E∥∇f (x; zi) −∇Fi(x)∥[2] _≤_ _σ[2]_ by
Assumption B.6. On the other hand by Assumption B.5


_Fi(x)_ _F_ (x) (1
_∇_ _−∇_ _∥[2]_ _≤_ _−_ _N[S][ −]_ [1]1 [)] [E][∥∇][F][i][(][x][)][ −∇]S _[F]_ [(][x][)][∥][2]
_iX∈Sr_ _−_


(1
_≤_ _−_ _N[S][ −]_ [1]1 [)] _[ζ]S[2]_

_−_

(340)


E
_∥_ _S[1]_


So altogether


_K_

_f_ (x; zi) _F_ (x)
_∇_ _−∇_ _∥[2]_ _≤_ _SK[σ][2]_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_
_k=1_ _−_

X


E
_∥_ _SK[1]_


(341)


_i∈Sr_


The second conclusion follows by noting


_∥_ _S[1]_


_Fi(x)_ _F_ (x)
_∇_ _−∇_ _∥[2]_ _≤_ _S[1]_
_iX∈Sr_


_Fi(x)_ _F_ (x) (342)
_∥∇_ _−∇_ _∥[2]_
_iX∈Sr_


**Lemma** **H.2.** _Let_ _u, v_ _be_ _arbitrary_ _(possibly_ _random)_ _points._ _Define_ _Fˆ(x)_ =

_SK1_ _i_ _Kk=0−1_ _[f]_ [(][x][; ˆ]zi,k) where ˆzi,k _i. Let_

_∈S_ _∼D_

P P _w = arg min_ _Fˆ(x)_

_x∈{u,v}_

_Then_

E[F (w) − _F_ (x[∗])] (343)

_ζF_

_≤_ min{F (u) − _F_ (x[∗]), F (v) − _F_ (x[∗])} + 4 _√[σ]SK[F]_ + 4 1 − _N[S][ −]_ [1]1 _√S_ (344)

r _−_

_and_

E[F (w) − _F_ (x[∗])] (345)

_ζF_

_≤_ min{EF (u) − _F_ (x[∗]), EF (v) − _F_ (x[∗])} + 4 _√[σ]SK[F]_ + 4 1 − _N[S][ −]_ [1]1 _√S_ (346)

r _−_


_Proof. Suppose that F_ (u) + 2a = F (v), where a ≥ 0. Then,

E[F (w) − _F_ (x[∗])] = P (w = u)(F (u) − _F_ (x[∗])) + P (w = v)(F (v) − _F_ (x[∗])) (347)


-----

Substituting F (v) = F (u) + 2a,
E[F (w) − _F_ (x[∗])] = P (w = u)(F (u) − _F_ (x[∗])) + P (w = v)(F (u) + 2a − _F_ (x[∗])) (348)
_≤_ _F_ (u) − _F_ (x[∗]) + 2a (349)

_F_ _F_
Observe that E( F[ˆ](x) − _F_ (x))[2] _≤_ _SK[σ][2]_ [+ (1][ −] _N[S][−]−[1]1_ [)][ ζ]S[2] [by Assumption B.7 and Assumption B.8.]

Therefore by Chebyshev’s inequality,

_P_ ( _F[ˆ](x)_ _F_ (x) _a)_ _F_ _F_ (350)
_|_ _−_ _| ≥_ _≤_ _a[1][2][ (][ σ]SK[2]_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Observe that
_P_ (w = v) ≤ _P_ ( F[ˆ](u) > F (u) + a) + P ( F[ˆ](v) < F (v) − _a)_ (351)

_F_ _F_ (352)

_≤_ _a[2][2][ (][ σ]SK[2]_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

And so it is also true that
E[F (w) − _F_ (x[∗])] = F (u) − _F_ (x[∗]) + 2aP (w = v) (353)

_F_ (u) _F_ (x[∗]) + 2a( [2] _F_ _F_ (354)
_≤_ _−_ _a[2][ (][ σ]SK[2]_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [))]

_−_

= F (u) _F_ (x[∗]) + [4] _F_ _F_ (355)
_−_ _a_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_

Therefore altogether we have that

E[F (w) _F_ (x[∗])] _F_ (u) _F_ (x[∗]) + max min _F_ _F_ (356)
_−_ _≤_ _−_ _a_ _{_ _a[4]_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)][,][ 2][a][}]

_−_

So by maximizing for a


4 _F_ _F_ _a =_
_a_ [(][ σ]SK[2] [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [) = 2][a][ =]⇒

_−_

which gives us


2( _[σ]F[2]_ _F_ (357)

_SK_ [+ (1][ −] _N[S][ −]_ [1]1 [)] _[ζ]S[2]_ [)]

_−_


_ζF_

E[F (w) − _F_ (x[∗])] ≤ _F_ (u) − _F_ (x[∗]) + 4 _√[σ]SK[F]_ + 4 1 − _N[S][ −]_ [1]1 _√S_ (358)

r _−_

Then proof also holds if we switch the roles of u and v, and so altogether we have that: if F (u) <
_F_ (v),


E[F (w) − _F_ (x[∗])] ≤ _F_ (u) − _F_ (x[∗]) + 4 _√[σ]SK[F]_ + 4

if F (u) > F (v),


_ζF_

1 − _N[S][ −] −_ [1]1 _√S_

_ζF_

1 − _N[S][ −] −_ [1]1 _√S_


(359)

(360)


E[F (w) − _F_ (x[∗])] ≤ _F_ (v) − _F_ (x[∗]) + 4 _√[σ]SK[F]_ + 4

implying the first part of the theorem.


_ζF_

E[F (w) − _F_ (x[∗])] ≤ min{F (u) − _F_ (x[∗]), F (v) − _F_ (x[∗])} + 4 _√[σ]SK[F]_ + 4 1 − _N[S][ −]_ [1]1 _√S_

r _−_

(361)
For the second part,

E[min{F (u) − _F_ (x[∗]), F (v) − _F_ (x[∗])}|v] = ZF (u)≤F (v) _F_ (u) − _F_ (x[∗]) (362)

_≤_ min{EF (u) − _F_ (x[∗]), F (v) − _F_ (x[∗])} (363)
and then


E[min{EF (u) − _F_ (x[∗]), F (v) − _F_ (x[∗])}] = ZF (v)≤EF (u) _F_ (u) − _F_ (x[∗]) (364)

_≤_ min{EF (u) − _F_ (x[∗]), EF (v) − _F_ (x[∗])} (365)


-----

I EXPERIMENTAL SETUP DETAILS

I.1 CONVEX OPTIMIZATION

We empirically evaluate FedChain on federated regularized logistic regression. Let (xi,j, yi,j) be the
_jth datapoint of the ith client and ni is the number of datapoints for the i-th client. We minimize_
Eq. (1) where


_ni_

_yi,j log(w[⊤]xi,j)_ (1 _yi,j) log(1_ _w[⊤]xi,j))) +_ _[µ]_
_−_ _−_ _−_ _−_ 2
_j=1_ _[∥][w][∥][2][.]_

X


_Fi(w) = [1]_

_ni_


**Dataset. We use the MNIST dataset of handwritten digits (LeCun et al., 2010). We model a federated**
setting with five clients by partitioning the data into groups. First, we take 500 images from each
digit class (total 5,000). Each client’s local data is a mixture of data drawn from two digit classes
(leading to heterogeneity), and data sampled uniformly from all classes.

We call a federated dataset X% homogeneous if the first X% of each class’s 500 images is shuffled
and evenly partitioned to each client. The remaining (100 − _X)% is partitioned as follows: client_
_i ∈{1, . . ., 5} receives the remaining non-shuffled data from classes 2i −_ 2 and 2i − 1. For example,
in a 50% homogeneous setup, client 3 has 250 samples from digit 4, 250 samples from digit 5, and
500 samples drawn uniformly from all classes. Note that 100% homogeneity is not the same thing as
setting heterogeneity ζ = 0 due to sampling randomness; we use this technique for lack of a better
control over ζ. To model binary classification, we let even classes represent 0’s and odd classes
represent 1’s, and set K = 20. All clients participate per round.

**Hyperparameters. All experiments initialize iterates at 0 with regularization µ = 0.1. We fix the**
total number of rounds R (differs across experiments). For algorithms without stepsize decay, the
tuning process is as follows.

We tune all stepsizes η in the range below:

_{10[−][3], 10[−][2][.][5], 10[−][2], 10[−][1][.][5], 10[−][1]}_ (366)

We tune the percentage of rounds before switching from Alocal to Aglobal (if applicable) as

_{10[−][2], 10[−][1][.][625], 10[−][1][.][25], 10[−][0][.][875], 10[−][0][.][5]}_ (367)

For algorithms with acceleration, we run experiments using the more easily implementable (but less
mathematically tractable for our analysis) version in Aybat et al. (2019) as opposed to Algo. 3.

For algorithms with stepsize decay, we instead use the range Eq. (367) to decide the percentage
of rounds to wait before decreasing the stepsize by half–denote this number of rounds as Rdecay.
Subsequently, every factor of 2 times Rdecay we decrease the stepsize by half.

We use the heuristic that when the stepsize decreases to η/K, we switch to Aglobal and begin the
stepsize decay process again. All algorithms are tuned to the best final gradient norm averaged over
1000 runs.

I.2 NONCONVEX OPTIMIZATION

I.2.1 EMNIST

In this section we detail how we use the EMNIST (Cohen et al., 2017) dataset for our nonconvex
experiments, where the handwritten characters are partitioned by their author. In this dataset, there
are 3400 clients, with 671,585 images in the train set and 77,483 in the test set. The task is to train a
convolutional network with two convolutional layers, max-pooling, dropout, and two dense layers as
in the Federated Learning task suite from (Reddi et al., 2020).

**Hyperparameters. We set R = 500, and rather than fixing the number of local steps, we fix the**
number of local client epochs (the number of times a client performs gradient descent over its own
dataset) to 20. The number of clients sampled per round is 10. These changes were made in light of
the imbalanced dataset sizes across clients, and is standard for this dataset-task (Reddi et al., 2020;
Charles & Konecnˇ y, 2020; Charles et al., 2021). For all algorithms aside from (M-SGD), we tune`


-----

_η in the range {0.05, 0.1, 0.15, 0.2, 0.25}. We tune the percentage of rounds before switching from_
_Alocal to Aglobal in {0.1, 0.3, 0.5, 0.7, 0.9}, where applicable._

We next detail the way algorithms with stepsize decay are run. We tune the stepsize η in
_{0.1, 0.2, 0.3, 0.4, 0.5}. Let Rdecay be the number of rounds before the first decay event. We_
tune2 of R Rdecaydecay, we halve the stepsize/ After ∈⌈{0.1R, 0.275R, 0.45R}⌉ R. Whenever the number of passed rounds is a power of[′] rounds have passed, we enter Aglobal, where we tune
_R[′]_ _∈⌈{0.5R, 0.7R, 0.9R}⌉. We restart the decay process upon entering Aglobal._

For M-SGD we tune
_η ∈{0.1, 0.2, 0.3, 0.4, 0.5}_

and
_Rdecay ∈⌈{10[−][2]R, 10[−][1][.][625]R, 10[−][1][.][25]R, 10[−][0][.][875]R, 10[−][0][.][5]R}⌉_

For stepsize decaying SCAFFOLD and FedAvg, we tune⌈{0.1R, 0.275R, 0.45R}⌉. When evaluating a particular metric the algorithms are tuned according η ∈{0.1, 0.2, 0.3, 0.4, 0.5} and Rdecay ∈
to the mean of the last 5 evaluated iterates of that particular metric. Reported accuracies are also the
mean of the last 5 evaluated iterates, as the values mostly stabilized during training.

I.2.2 CIFAR-100

For the CIFAR-100 experiments, we use the CIFAR-100 (Krizhevsky, 2009) dataset, where the
handwritten characters are partitioned via the method proposed in (Reddi et al., 2020). In this dataset,
there are 500 train clients, with a total of 50,000 images in the train set. There are 100 test clients and
10,000 images in the test set. The task is to train a ResNet-18, replacing batch normalization layers
with group normalization as in the Federated Learning task suite from (Reddi et al., 2020). We leave
out SCAFFOLD in all experiments because of out of memory issues.

**Hyperparameters.** We set R = 5000, and rather than fixing the number of local steps, we fix
the number of local client epochs (the number of times a client performs gradient descent over its
own dataset) to 20. The number of clients sampled per round is 10. These changes were made
in light of the imbalanced dataset sizes across clients, and is standard for this dataset-task (Reddi
et al., 2020; Charles & Konecnˇ y, 2020; Charles et al., 2021). For all algorithms we tune` _η in_
_{0.1, 0.2, 0.3, 0.4, 0.5}. Algorithms without stepsize decay tune the percentage of rounds before_
switching to Aglobal in {0.1, 0.3, 0.5, 0.7, 0.9}. Algorithms with stepsize decay (aside from M-SGD)
tune the number of rounds before the first decay event in {0.1, 0.275, 0.45} (and for every power of 2
of that percentage, the stepsize decays in half), and the number of rounds before swapping to Aglobal
in {0.5, 0.7, 0.9} if applicable (stepsize decay process restarts after swapping). M-SGD tunes the
number of rounds before the first decay event in {0.01, 0.0237, 0.0562, 0.1334, 0.3162}. We tune for
and return the test accuracy of the last iterate, as accuracy was still improving as we trained.

J ADDITIONAL CONVEX EXPERIMENTS

In this section, we give supplemental experimental results to verify the following claims:

1. Higher K allows (1) accelerated algorithms to perform better than non-accelerated algorithms, and furthermore (2) allows us to run Alocal for one round to get satisfactory results.

2. Our FedChain instantiations outperform stepsize decaying baselines

J.1 VERIFYING THE EFFECT OF INCREASED K AND R = 1

Our proofs of FedChain all also work if we run Alocal for only one communication round, so long as
_K is sufficiently large (exact number is in the formal theorem proofs). In this section we verify the_
effect of large K in conjunction with running Alocal for only one round. The setup is the same as in
App. I.1, except we tune the stepsize η in a larger grid:

_η ∈{10[−][3], 10[−][2][.][5], 10[−][2], 10[−][1][.][5], 10[−][1], 10[−][0][.][5], 10[0]}_ (368)

The plots are in Fig. 3. For algorithms that are “1-X→Y”, we run algorithm X for one round and
algorithm Y for the rest of the rounds. These algorithms are tuned in the following way. Algorithm X


-----

Figure 3: We investigate the effect of high K (K = 100). “1-X→Y” denotes a chained algorithm
with X run for one round and Y run for the rest of the rounds. Chained algorithms, even with one
round allocated to Alocal, perform the best. Furthermore, accelerated algorithms outperform their
non-accelerated counterparts.

Figure 4: The same as Fig. 2, except we include stepsize decay for baseline algorithms. Chained
algorithms still perform the best.

has its stepsize tuned in Eq. (368), and Algorithm Y independently has its stepsize tuned in Eq. (368).
We require these to be tuned separately because local update algorithms and centralized algorithms
have stepsizes that depend on K differently if K is large (see, for example, Thm. D.1 and Thm. E.1).
The baselines have a single stepsize tuned in Eq. (368). These are tuned for the lowest final gradient
norm averaged over 1000 runs.

Overall, we see that in the large K regime, algorithms that start with a local update algorithm and
then finish with an accelerated centralized algorithm have the best communication complexity. This
is because larger K means the error due to variance decreases, for example as seen in Thm. F.2.
Acceleration increases instability (if one does not perform a carefully calibrated stepsize decay,
as we do not in the experiments), so decreasing variance helps accelerated algorithms the most.
Furthermore, a single round forexpected, because both the “bias” term (the Alocal suffices to see large improvement as seen in Fig. 3. This is ∆exp( _√κK_ ) term in Thm. E.1) and the variance term
_−_ _[R]_

become negligible, leaving just the heterogeneity term as desired.

J.2 INCLUDING STEPSIZE DECAY BASELINES

In this section, we compare the performance of the algorithms against learning rate decayed SGD,
FedAvg, ASG, and SCAFFOLD. We use the same setting as App. I.1 for the decay process and
the stepsize. In this case, we still see that the chained methods outperform their non-chained
counterparts.


-----

