# The Limits and Potentials of Local SGD for Distributed Heterogeneous
Learning with Intermittent Communication

Kumar Kshitij Patel
Toyota Technological Institute, Chicago
<EMAIL_ADDRESS>
&Margalit Glasgow
Stanford University
<EMAIL_ADDRESS>
&Ali Zindari
CISPA Helmholtz Center
<EMAIL_ADDRESS>
&Lingxiao Wang
Toyota Technological Institute, Chicago
<EMAIL_ADDRESS>
&Sebastian U. Stich
CISPA Helmholtz Center
<EMAIL_ADDRESS>
&Ziheng Cheng
Peking University
<EMAIL_ADDRESS>
&Nirmit Joshi
Toyota Technological Institute, Chicago
<EMAIL_ADDRESS>
&Nathan Srebro
Toyota Technological Institute, Chicago
<EMAIL_ADDRESS>
Corresponding author. This paper is an extended version of a conference paper
at the 37th Annual Conference on Learning Theory (COLT 2024). Preliminary
versions of this work also appeared at the Federated Learning and Analytics in
Practice: Algorithms, Systems, Applications, and Opportunities workshop at
ICML 2023 and the 15th International OPT Workshop on Optimization for Machine
Learning at NeurIPS 2023.

###### Abstract

Local SGD is a popular optimization method in distributed learning, often
outperforming other algorithms in practice, including mini-batch SGD. Despite
this success, theoretically proving the dominance of local SGD in settings
with reasonable data heterogeneity has been difficult, creating a significant
gap between theory and practice (Wang et al., 2022). In this paper, we provide
new lower bounds for local SGD under existing first-order data heterogeneity
assumptions, showing that these assumptions are insufficient to prove the
effectiveness of local update steps. Furthermore, under these same
assumptions, we demonstrate the min-max optimality of accelerated mini-batch
SGD, which fully resolves our understanding of distributed optimization for
several problem classes. Our results emphasize the need for better models of
data heterogeneity to understand the effectiveness of local SGD in practice.
Towards this end, we consider higher-order smoothness and heterogeneity
assumptions, providing new upper bounds that imply the dominance of local SGD
over mini-batch SGD when data heterogeneity is low.

_Keywords_ Distributed Optimization $\cdot$ Local SGD $\cdot$ Intermittent
Communication $\cdot$ Min-max Optimal

##  1 Introduction

We consider the following distributed optimization problem on $M$ machines,

$\displaystyle\min_{x\in\mathbb{R}^{d}}\left(F(x):=\frac{1}{M}\sum_{m\in[M]}F_{m}(x)\right),$
(1)

where $F_{m}:=\mathbb{E}_{z_{m}\sim\mathcal{D}_{m}}[f(x;z_{m})]$ is a
stochastic objective on machine $m$, defined using a smooth, convex and
differentiable loss function $f(\cdot;z\in\mathcal{Z})$ and a data
distribution $\mathcal{D}_{m}\in\Delta(\mathcal{Z})$. Problem (1) is
ubiquitous in machine learning—from training in a data center on multiple GPUs
(Krizhevsky et al., 2012), to decentralized training on millions of devices
(McMahan et al., 2016a, b). Perhaps the simplest, most basic, and most
important distributed setting for solving Problem (1) is that of intermittent
communication (IC) (Woodworth et al., 2018), where $M$ machines work in
parallel over $R$ communication rounds to optimize objective (1), and during
each round of communication, each machine may sequentially compute $K$
stochastic gradient estimates (see Figure 1 for an illustration).

$\bm{M}$machines$\bm{t=0}$$\bm{K}$local updates$\bm{t=K}$$\bm{K}$local
updates$\bm{t=2K}$

Figure 1: Illustration of the intermittent communication setting.

While several stochastic gradient descent (SGD) methods have been proposed for
solving problem (1) in the IC setting, most of them (Kairouz et al., 2019;
Wang et al., 2021) are variants of local SGD (update (5)) or mini-batch SGD
(update (6)). In local SGD, each machine computes $K$ sequential stochastic
gradients in parallel, and then the resulting updates are averaged across the
machines at each round of communication. In practice, this simple algorithm
often outperforms all other first-order optimization algorithms (Charles et
al., 2021; Wang et al., 2022), including mini-batch SGD (Lin et al., 2018;
Woodworth et al., 2020a). As such, there has been a concerted effort to
understand the effectiveness of local SGD for more than a decade (Mcdonald et
al., 2009; Zinkevich et al., 2010; Zhang et al., 2016; Stich, 2018; Dieuleveut
and Patel, 2019; Khaled et al., 2020; Koloskova et al., 2020; Woodworth et
al., 2020a; Karimireddy et al., 2020a; Woodworth et al., 2020b; Yuan and Ma,
2020; Woodworth et al., 2021; Glasgow et al., 2022; Wang et al., 2022; Patel
et al., 2023).

In the homogeneous setting, when $\mathcal{D}_{m}=\mathcal{D}$ for each
$m\in[M]$, Woodworth et al. (2021) showed that the min-max optimal algorithm
for optimizing problem (1) with smooth and convex objectives, is the best of
(accelerated) local and mini-batch SGD. Unfortunately, their results also
implied that local SGD can outperform mini-batch SGD only when even SGD on a
single machine (i.e., without any collaboration) also outperforms mini-batch
SGD! This result was surprising because, in practice, local SGD almost always
outperforms both single-machine SGD and mini-batch SGD (McMahan and Ramage,
2017; Charles et al., 2021). The most likely reason for this disparity between
theory and practice is that the homogeneous setting is too simplistic. In
practice, the data distributions of different machines are “similar" but not
the same, making collaboration pivotal.

Towards this end, several works (Khaled et al., 2020; Karimireddy et al.,
2020a; Koloskova et al., 2020; Woodworth et al., 2020b; Yuan and Ma, 2020;
Glasgow et al., 2022; Wang et al., 2022) have tried to capture the similarity
between machine’s distributions by using “data heterogeneity” assumptions.
However, most of these works either fail to show a theoretical advantage of
local SGD over mini-batch SGD (Khaled et al., 2020; Karimireddy et al., 2020a;
Koloskova et al., 2020) or they need to make restrictive assumptions that do
not allow any interesting data heterogeneity (c.f., Assumption 2 of Woodworth
et al. (2020b)). This inability to theoretically explain the effectiveness of
local SGD presents a big gap between the theory and practice of distributed
optimization. Recently, Wang et al. (2022) called this the “unreasonable
effectiveness of local SGD”. In this paper, we contribute to this discourse
about the usefulness of local SGD by providing new lower and upper bounds for
solving problem (1) in the IC setting. Our key theoretical insights are as
follows:

#### 1\. Existing first-order heterogeneity assumptions are insufficient for
local SGD.

We provide a new lower bound for local SGD (Theorem 1) in the general convex
setting. Our core finding can be stated as:

> There is a smooth, convex, and quadratic problem instance such that local
> SGD can not get arbitrarily close to the shared optimum of the clients with
> finite communication.

Our lower bound precludes dominance of local SGD over mini-batch SGD under the
following heterogeneity assumption considered by several existing works
(Koloskova et al., 2020; Woodworth et al., 2020b; Glasgow et al., 2022).

######  Assumption 1 (Bounded First-Order Heterogeneity at Optima).

A set of objectives $\\{F_{m}\\}_{m\in[M]}$ satisfy $\zeta_{\star}$-first-
order heterogeneity at the optima if for all minimizers of the average
objective $x^{\star}\in\arg\min_{x\in\mathbb{R}^{d}}F(x)$,

$\frac{1}{M}\sum_{m\in[M]}\left\lVert\nabla
F_{m}(x^{\star})\right\rVert_{2}^{2}\leq\zeta_{\star}^{2}.$

We show that the above assumption, while a natural measure of data-
heterogeneity, can not avoid some basic pathologies of distributed learning
with convex objectives. Our lower bound also precludes any dominance of local
SGD over mini-batch SGD under another similar assumption postulated by Wang et
al. (2022) (Assumption 7 in Appendix C).

#### 2\. Accelerated mini-batch SGD is min-max optimal when machines have
shared optima.

We provide a new algorithm-independent lower bound (Theorem 2) under
Assumption 1 (and Assumption 7), showing that accelerated mini-batch SGD is
min-max optimal under this assumption! This conclusion is surprising, and
while it further deepens the theory-practice disparity, it concludes a recent
line of work on identifying the min-max optimal algorithm in the general
convex setting under related first-order heterogeneity assumptions (Khaled et
al., 2020; Koloskova et al., 2020; Woodworth et al., 2020b; Glasgow et al.,
2022; Wang et al., 2022).

Together our lower bounds (Theorems 1 and 2) imply that existing first-order
assumptions are insufficient to understand the effectiveness of local SGD, in
that they do not characterize a measure of data heterogeneity, reducing which
would allow local update steps to be useful. This motivates us to consider
higher-order assumptions in addition to first-order ones.

#### 3\. Local SGD shines under higher-order heterogeneity and smoothness
assumptions.

We provide a new upper bound (Theorem 3) for local SGD improving the analysis
of Woodworth et al. (2020b) by capturing the effect of second-order
heterogeneity (Assumption 3) and third-order smoothness (Assumption 4). While
our upper bound depends on the restrictive Assumption 2 of Woodworth et al.
(2021), it relaxes local SGD’s dependence on the assumption, i.e., our
analysis implies a benefit of local updates with much larger data
heterogeneity than that implied by the analysis of Woodworth et al. (2020b).
This hints that higher-order assumptions indeed enhance the benefit of local
updates. We explore this further by considering the special case when all the
client objectives are strongly convex quadratics. In this setting, we provide
a new upper bound (Theorem 4) for local SGD, underlining that Assumptions 1
and 3 control the discrepancy between the fixed point of local SGD and the
minimizer of $F$ in problem (1).

#### Notation.

We use $\cong$, $\preceq$, and $\succeq$ to refer to equality and inequality
up to absolute numerical constants. We denote the set $\\{i,i+1,\dots,n\\}$ by
$[i,n]$ and when $i=1$ by $[n]$. $\left\lVert.\right\rVert_{2}$ refers to the
$L_{2}$ norm when applied to vectors in $\mathbb{R}^{d}$ and the spectral norm
when applied to matrices in $\mathbb{R}^{d\times d}$.

##  2 Setting and Preliminaries

Type of Result (Reference) | Convergence bound on $\mathbb{E}[F(\hat{x})-F(x^{\star})]\preceq/\succeq$
---|---
Local SGD Upper Bound | $\boldsymbol{\frac{HB^{2}}{R}}+\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}+\frac{\sigma B}{\sqrt{MKR}}+\frac{(H\zeta_{\star}^{2}B^{4})^{1/3}}{R^{2/3}}$
(Koloskova et al., 2020)
Local SGD Lower Bound | $\frac{HB^{2}}{KR}+\min\left\\{\frac{\sigma B}{\sqrt{KR}},\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}\right\\}+\frac{\sigma B}{\sqrt{MKR}}+\min\left\\{\frac{\zeta_{\star}^{2}}{H},\frac{(H\zeta_{\star}^{2}B^{4})^{1/3}}{R^{2/3}}\right\\}$
(Glasgow et al., 2022)
Local SGD Lower Bound | $\boldsymbol{\frac{HB^{2}}{R}}+\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}+\frac{\sigma B}{\sqrt{MKR}}+\frac{(H\zeta_{\star}^{2}B^{4})^{1/3}}{R^{2/3}}$
(Theorem 1)
Mini batch SGD Upper Bound | $\boldsymbol{\frac{HB^{2}}{R}}+\frac{\sigma B}{\sqrt{MKR}}$
(Dekel et al., 2012)
Acc. MB SGD Upper Bound | $\boldsymbol{\frac{HB^{2}}{R^{2}}}+\frac{\sigma B}{\sqrt{MKR}}$
(Ghadimi and Lan, 2012)
Algo. Independent Lower Bound | $\min\left\\{\boldsymbol{\frac{HB^{2}}{R^{2}}},\frac{\zeta_{\star}^{2}}{HR^{2}},\frac{\zeta_{\star}B}{R}\right\\}+\frac{\sigma B}{\sqrt{MKR}}$
(Woodworth et al., 2020b)
Algo. Independent Lower Bound | $\boldsymbol{\frac{HB^{2}}{R^{2}}}+\frac{\sigma B}{\sqrt{MKR}}$
(Theorem 2)

Table 1: Summary of old and new results (up to logarithmic factors) for
problem instances in the class $\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$,
i.e., under Assumption 2 on $S^{\star}$. Throughout we assume $\frac{\sigma
B}{\sqrt{MKR}}\leq HB^{2}$.

Note that an instance of problem (1) can be characterized by the client
distributions $\\{\mathcal{D}_{m}\in\Delta(\mathcal{Z})\\}_{m\in[M]}$ and a
differentible loss function
$f(\cdot;z\in\mathcal{Z}):\mathbb{R}^{d}\to\mathbb{R}$. We will denote the set
of all such problem instances by $\mathcal{P}$. To further restrict the
problems we will study, we assume that for all $m\in[M]$, the objective
function $F_{m}$ is convex, and $H$-smooth, i.e., for all $m\in[M],\
x,y\in\mathbb{R}^{d}$,

$\displaystyle F_{m}(x)\leq F_{m}(y)+\left\langle\nabla
F_{m}(y),x-y\right\rangle+\frac{H}{2}\left\lVert
x-y\right\rVert_{2}^{2}\enspace.$ (2)

We also assume that each machine $m\in[M]$ computes stochastic gradients of
$F_{m}$ in the IC setting by sampling from its distributions
$z\sim\mathcal{D}_{m}$, and that for all $x\in\mathbb{R}^{d}$,

$\displaystyle\mathbb{E}_{z\sim\mathcal{D}_{m}}\left[\nabla
f(x;z)\right]=\nabla F_{m}(x),\text{ and
}\mathbb{E}_{z\sim\mathcal{D}_{m}}\left[\left\lVert\nabla f(x;z)-\nabla
F_{m}(x)\right\rVert_{2}^{2}\right]\leq\sigma^{2}\enspace.$ (3)

Finally, we assume that the average objective $F$ has bounded optima, i.e.,

$\displaystyle\left\lVert x^{\star}\right\rVert_{2}\leq B,\ \forall\
x^{\star}\in S^{\star}:=\arg\min_{x\in\mathbb{R}^{d}}F(x).$ (4)

We will denote the class of all the problems satisfying these
assumptions111Note that when $\sigma=0$, i.e., in the noiseless setting, then
the problem instance is characterized by $\\{F_{m}\\}_{m\in[M]}$. by
$\mathcal{P}^{H,B,\sigma}$. With this, we are ready to describe our algorithms
with intermittent communication. We can write the update for local SGD
(initialized at $x_{0}$) for round $r\in[R]$ as follows,

$\displaystyle x_{r,0}^{m}$ $\displaystyle=x_{r-1},$ $\displaystyle\forall\
m\in[M]$ (5) $\displaystyle x_{r,k+1}^{m}$
$\displaystyle=x_{r,k}^{m}-\eta\nabla f(x_{r,k};z_{r,k}^{m}),\
z_{r,k}^{m}\sim\mathcal{D}_{m},$ $\displaystyle\forall\ m\in[M],k\in[0,K-1]$
$\displaystyle x_{r}$
$\displaystyle=x_{r-1}+\frac{\beta}{M}\sum_{m\in[M]}\left(x_{r,K}^{m}-x_{r-1}\right).$

Above $x_{r,k}^{m}$ is the $k^{th}$ local model on machine $m$, leading up to
the $r^{th}$ round of communication, while $x_{r}$ is the consensus model at
the end of the $r^{th}$ communication. For local SGD, $\eta$ is referred to as
the inner step size, while $\beta$ is the outer step size. Setting $\beta=1$
recovers “vanilla local SGD” with a single step size which has been analyzed
in several earlier works (Stich, 2018; Dieuleveut and Patel, 2019; Khaled et
al., 2020; Woodworth et al., 2020a). Vanilla local SGD is equivalent to
averaging the machine’s models after $K$ local updates. Similarly, we can
write the updates of mini-batch SGD (initialized at $x_{0}$) for round
$r\in[R]$ as follows,

$\displaystyle g_{r,k}^{m}$ $\displaystyle=\nabla f(x_{r-1};z_{r,k}^{m}),\
z_{r,k}^{m}\sim\mathcal{D}_{m},$ $\displaystyle\forall\ m\in[M],k\in[0,K-1]$
(6) $\displaystyle x_{r}$
$\displaystyle=x_{r-1}-\frac{\beta}{M}\sum_{m\in[M],k\in[0,K-1]}g_{r,k}^{m}.$

The main difference in the mini-batch update compared to vanilla local SGD is
that its local gradient is computed at the same point for the entire
communication round. Due to this, mini-batch SGD is not impacted by data
heterogeneity, as it optimizes $F$ without getting affected by the multi-task
nature of problem (1) (for more discussion, see Woodworth et al. (2020b)).
However, this is also why local SGD can intuitively outperform mini-batch SGD:
it has more effective updates than mini-batch SGD. For e.g., without noise,
i.e., $\sigma=0$, mini-batch SGD keeps obtaining the gradient at the same
point, thus making only $R$ updates instead of $KR$ updates of local SGD.

When the data heterogeneity is “low”, the iterates on different machines would
not go too far between communication rounds, a.k.a., local SGD will have a
small “consensus error”. In the extreme homogeneous setting, the iterates on
different machines will be the same in expectation. We will denote the class
of homogeneous problems by
$\mathcal{P}_{hom}^{H,B,\sigma}\subset\mathcal{P}^{H,B,\sigma}$. Most
heterogeneity assumptions are variants of first-order assumptions, which
impose restrictions on the gradients of functions and thus aid the analysis of
local SGD by controlling how far the machines’ iterates can go between two
communication rounds. These assumptions can be generalized as follows.

######  Assumption 2 (Bounded First-Order Heterogeneity).

A set of objectives $\\{F_{m}\\}_{m\in[M]}$ satisfy $\zeta$-first-order
heterogeneity on the domain $\mathcal{X}\subseteq\mathbb{R}^{d}$ if,

$\sup_{x\in\mathcal{X},m\in[M]}\left\lVert\nabla F_{m}(x)-\nabla
F(x)\right\rVert_{2}^{2}\leq\zeta(\mathcal{X})^{2}.$

We will refer to problems satisfying Assumption 2 on $\mathcal{X}$ by
$\mathcal{P}_{\zeta(\mathcal{X})}^{H,B,\sigma}$ and omit the dependence on
$\mathcal{X}$ when it is clear from the context. Woodworth et al. (2020b)
showed an advantage of vanilla local SGD over mini-batch SGD under Assumption
2 on the unbounded domain $\mathcal{X}=\mathbb{R}^{d}$ (see Table 2).
Unfortunately, assuming $\mathcal{X}$ to be $\mathbb{R}^{d}$ makes the above
assumption too restrictive, for e.g., quadratic functions in the class
$\mathcal{P}^{H,B,\sigma}_{\zeta(\mathbb{R}^{d})}$ must have the same Hessian.

######  Proposition 1.

Let $F_{m}(x)=\frac{1}{2}x^{T}A_{m}x+b_{m}^{T}x+c_{m}$ for all $m\in[M]$. If
$\\{F_{m}\\}_{m\in[M]}$ satisfy Assumption 2 for $\mathcal{X}=\mathbb{R}^{d}$
for $\zeta<\infty$ then for any two machines $m,n\in[M]$, $A_{m}=A_{n}$.

######  Remark 1
($\bm{\mathcal{P}_{hom}^{H,B,\sigma=0}\approx\mathcal{P}_{\zeta(\mathbb{R}^{d})<\infty}^{H,B,\sigma=0}}$).

Essentially, Assumption 2 on $\mathbb{R}^{d}$ only allows heterogeneity in
linear terms. In the noiseless setting, i.e., when $\sigma=0$, such
heterogeneity can be adjusted for using one round of communication at the
beginning of optimization by computing the gradient at $0$ on all machines and
transmitting $\nabla F(0)$ to the machines. At each round, the machines add
the correction $\nabla F(0)-\nabla F_{m}(0)$ to their gradients and behave as
if the problem were homogeneous!

The restrictiveness of Assumption 2 with $\mathcal{X}=\mathbb{R}^{d}$ is
precisely why several works (Khaled et al., 2020; Karimireddy et al., 2020a;
Koloskova et al., 2020) have considered relaxed versions of the assumption. A
natural relaxation is to assume Assumption 2 on $\mathcal{X}=S^{\star}$, the
set of optima of $F$, which is precisely Assumption 1. We will denote
$\zeta_{\star}:=\zeta(S^{\star})$, and define the problem class of problems
satisfying Assumption 1 by
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}:=\mathcal{P}_{\zeta(S^{\star})}^{H,B,\sigma}$.
We can make several interesting remarks related to interpretations of
Assumption 1.

######  Remark 2
($\bm{\mathcal{P}^{H,B,\sigma=0}_{hom}\approx\mathcal{P}_{\zeta(\mathbb{R}^{d})<\infty}^{H,B,\sigma=0}\subset\mathcal{P}_{\zeta_{\star}=0}^{H,B,\sigma=0}}$).

Note that $\zeta_{\star}=0$ does not imply we are in the homogeneous
regime—all it says is that the machines should have some shared optimum. This
is in contrast to Assumption 2 with $\mathcal{X}=\mathbb{R}^{d}$, where
$\zeta=0$ implies that $F_{m}$’s have to be the same except for constants.
Thus assuming $\zeta_{\star}<\infty$ (or even $\zeta_{\star}=0$) does allow
for interesting data heterogeneity.

######  Remark 3 (Approximate Simultaneous Realizability).

In a learning setting, Assumption 1 can be interpreted as an approximate
_simultaneous realizability_ assumption for $\mathcal{D}_{m}$’s, measuring how
good is the solution for the average objective $F$ for any individual machine.
Besides literature on data heterogeneity in distributed optimization, the
simultaneous realizability assumption also appears in the collaborative PAC
learning literature (Blum et al., 2017; Nguyen and Zakynthinou, 2018;
Haghtalab et al., 2022) and in the context of avoiding defections in federated
learning (Han et al., 2023).

######  Remark 4 (Local SGD’s Fixed Point).

Denote the set of optima of machine $m\in[M]$ by
$S_{m}^{\star}:=\arg\min_{x\in\mathbb{R}^{d}}F_{m}(x)$. Assume the machines
have some shared optimum $x^{\star}\in\cap_{m\in[M]}S_{m}^{\star}$, then in
fact all their optima should be shared, i.e.,
$S^{\star}=\cap_{m\in[M]}S_{m}^{\star}$. This observation implies that all
points in $S^{\star}=\cap_{m\in[M]}S_{m}^{\star}$ are fixed points of local
gradient descent with any $K\geq 1$ (Pathak and Wainwright, 2020).
Interestingly beyond the setting of shared optima, for $K>1$ there is no
simple closed form for the fixed points of local gradient descent. Since
$\zeta_{\star}=0$ implies that the machines do have a shared optimum,
Assumption 1 intimately “controls” the convergence behavior of local gradient
descent.

Hopefully, the above remarks motivate the importance to understand local SGD’s
performance on the problem class $\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$.
Unfortunately, no known analysis has provably shown that local SGD improves
over mini-batch SGD on this class (see Table 1). Based on the best known lower
bound by Glasgow et al. (2022) (see Table 1), it is still possible that local
SGD could improve upon (accelerated) mini-batch SGD when $\zeta_{\star}$ and
$\sigma$ are small, but $K$ is large. For instance, in the extreme case when
$\sigma=\zeta_{\star}=0$, even if $K\to\infty$ but $R$ is small, accelerated
large mini-batch SGD will not have zero function sub-optimality. In contrast,
if the lower bound by Glasgow et al. (2022) were tight, local SGD would get
zero function sub-optimality in such a regime. This raises the following
question:

> Can local SGD dominate mini-batch SGD on the class
> $\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$ for small $\zeta_{\star}$?

We will answer this question negatively in the next section, and also
establish the min-max optimality of mini-batch SGD amongst zero-respecting
algorithms in the IC setting on the class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$.

##  3 Middling Utility of First-order Heterogeneity Assumptions in the Convex
Setting

Our lower bounds in this section are based on the key insight presented in
Remark 2, i.e., even if the machines have a shared optimum, i.e.,
$S^{\star}=\cap_{m\in[M]}S_{m}^{\star}\neq\emptyset$ (see Remark 4), the
problem instance need not be homogeneous. As a motivating example, assume
there are two machines, we do not have any noise, i.e., $\sigma=0$ and the
objectives of the machines for all $x=(x[1],x[2])\in\mathbb{R}^{2}$ are given
by,

$\displaystyle F_{1}(x)=\frac{H}{2}\left(x[1]-x^{\star}[1]\right)^{2}\text{
and }F_{2}(x)=\frac{H}{2}\left(x[2]-x^{\star}[2]\right)^{2},$ (7)

where $x^{\star}=(x^{\star}[1],x^{\star}[2])\in\mathbb{R}^{2}$ is the unique
optimum of $F(x)=\frac{H}{4}\left\lVert x-x^{\star}\right\rVert_{2}^{2}$. Note
that each machine’s objective is $H$-smooth and satisfies Assumption 2 on
$S^{\star}=\\{x^{\star}\\}$ with $\zeta_{\star}=0$. Assuming we run local SGD
on both machines initialized at $(0,0)$, then the iterate after $R$ rounds is
given by (proved in Appendix B),

$\displaystyle x_{R}=x^{\star}\left(1-\left(1-\frac{\beta}{2}\left(1-(1-\eta
H)^{K}\right)\right)^{R}\right).$ (8)

Let us first consider vanilla local SGD, i.e., $\beta=1$. The above expression
simplifies to,

$\displaystyle x_{R}=x^{\star}\left(1-\left(\frac{1+(1-\eta
H)^{K}}{2}\right)^{R}\right).$ (9)

Thus, even if $K\to\infty$, $x_{R}$ does not converge to $x^{\star}$ for
finite $R$. This implies that the lower bound from Glasgow et al. (2022),
which goes to $0$ when $K\to\infty$, must be loose.

######  Remark 5 (The Role of the Outer Step-size).

Note that for Example 7, if we set $\beta=2$, $x_{R}$ will converge to
$x^{\star}$ in a single communication round when $K\to\infty$! Thus, at least
in this example, we can not rule out the lower bound by Glasgow et al. (2022)
if we use the correct outer step size. This example re-emphasizes the role of
outer step-size (Charles and Konecny, 2020; Jhunjhunwala et al., 2023) and
provides a separation between vanilla local SGD and local SGD with two step-
sizes.

In the following proposition, we extend this idea to obtain a lower bound for
any outer step size $\beta$ (and not just $1$).

######  Proposition 2.

For any $K\geq 2,R,M,H,B$, and $\sigma=0$ there exist $\\{F_{m}\\}_{m\in[M]}$
in the problem class $\mathcal{P}^{H,B,\sigma=0}_{\zeta_{\star}=0}$, s.t. the
local GD iterate $x_{R}$ with any step-size $\eta,\beta>0$, and initialized at
zero has:

$\displaystyle\mathbb{E}\left[F(\hat{x}_{R})\right]-F(\boldsymbol{x}^{\star})$
$\displaystyle\succeq\frac{HB^{2}}{R}\,.$

The above proposition formalizes the idea presented in our motivating example
(7), showing that local GD can not reach arbitrary function sub-optimality
with finite $R$ but infinite $K$ for any $\beta$. In fact, we also use a
quadratic construction to prove the proposition. This lower bound also
precludes any domination over gradient descent on $F$ with $R$ updates, which
is indeed the noiseless variant of mini-batch SGD (see update (6)). Finally,
note that the proposition can not benefit from simultaneous realizability,
i.e., non-empty $\cap_{m\in[M]}S_{m}^{\star}$. This highlights the hardness of
general convex optimization in the intermittent communication model. To prove
the above proposition for arbitrary step sizes, we reduce the local GD updates
over a single communication round to a single gradient descent (GD) update on
$F$ and then use the following lemma (proved in Appendix B) for GD.

######  Lemma 1.

Let $F(x)$ be a convex quadratic function whose Hessian has top eigenvalue
$H$, bottom eigenvalue $\mu$, and condition number $\kappa=\frac{H}{\mu}\geq
6$. Let $\hat{x}_{R}$ be the $R^{th}$ gradient descent iterate initialized at
zero. Then for any $B$, there exists some $x^{\star}$ with
$\|x^{\star}\|_{2}\leq B$ such that for any step size $\eta$,
$F(\hat{x}_{R})-F(x^{\star})\geq HB^{2}\frac{1}{\kappa}e^{-R/\kappa}$. In
particular, if $\kappa=\Omega(R)$, then
$F(\hat{x}_{R})-F(x^{\star})\geq\Omega\left(\frac{HB^{2}}{R}\right)$.

To get a lower bound in terms of $\zeta_{\star}$ from Assumption 2 as well as
understand the effect of noise level $\sigma$, we combine proposition 2 with
the previous lower bound by Glasgow et al. (2022), to get the following lower
bound result.

######  Theorem 1.

For any $K\geq 2,R,M,H,B,\sigma,\zeta_{\star}$, there exists a problem
instance in $\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}$ such that the final
iterate $x_{R}$ of local SGD initialized at zero with any step size satisfies:

$\displaystyle\mathbb{E}\left[F(x_{R})\right]-F(x^{\star})$
$\displaystyle\succeq\frac{HB^{2}}{R}+\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}+\frac{\sigma
B}{\sqrt{MKR}}+\frac{(H\zeta_{\star}^{2}B^{4})^{1/3}}{R^{2/3}}.$

Combining Theorem 1 with the upper bound by Koloskova et al. (2020), we
characterize the optimal convergence rate for local SGD for problems in class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$. Thus, our lower bound concludes
the line of work trying to analyze local SGD under the first-order
heterogeneity assumption on the set $S^{\star}$ (Koloskova et al., 2020;
Woodworth et al., 2020b; Glasgow et al., 2022).

######  Remark 6 (Proposed Assumption of Wang et al. (2022)).

Proposition 2 also implies that the first-order assumption of Wang et al.
(2022) (see Assumption 7 and discussion in Appendix C) can not be used to show
a domination of local SGD over mini-batch SGD. This is because when
$S^{\star}\neq\emptyset$, the data heterogeneity assumption of Wang et al.
(2022) implies zero heterogeneity.

Overall, the results of this section imply that none of the existing
assumptions besides the Assumption 2 on the unbounded domain $\mathbb{R}^{d}$
provides the necessary control on data heterogeneity, for local SGD to beat
mini-batch SGD in the general convex setting.

###  3.1 The Min-max Optimality of Mini-batch SGD

While we can not show the effectiveness of local SGD on the class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$, can we say which algorithm is min-
max optimal for this class of problems? It turns out that the answer is
surprisingly simple: accelerated large mini-batch SGD (Ghadimi and Lan, 2012)!
To show this, we prove the following new algorithm-independent lower bound,
which does not improve with a small $\zeta_{\star}$.

######  Theorem 2 (Algorithm independent lower bound).

For any $K\geq 2,R,M,H,B,\sigma,\zeta_{\star}$, there exists a problem
instance in the class $\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}$, s.t. the
final iterate $\hat{x}$ of any distributed zero-respecting algorithm (see
Appendix B.5) initialized at zero with $R$ rounds of communication and $K$
stochastic gradient computations per machine per round satisfies,

$\displaystyle\mathbb{E}\left[F(\hat{x})\right]-F(x^{\star})\succeq\frac{HB^{2}}{R^{2}}+\frac{\sigma
B}{\sqrt{MKR}}\,.$ (10)

The above lower bound fully characterizes the min-max complexity of
distributed optimization on the class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$, showing that accelerated mini-
batch SGD is the min-max optimal algorithm. This conclusion is surprising, but
it closes a recent line of work investigating the intermittent communication
setting under Assumption 2 (Khaled et al., 2020; Karimireddy et al., 2020a;
Koloskova et al., 2020; Woodworth et al., 2020b; Glasgow et al., 2022; Wang et
al., 2022). The above lower bound also implies the min-max optimality of large
mini-batch SGD under Assumption 7 proposed by Wang et al. (2022) (see Appendix
C).

Compared to Woodworth et al. (2021) who showed that for problem class
$\mathcal{P}_{hom}^{H,B,\sigma}$ (and by implication for
$\mathcal{P}_{\zeta=0}^{H,B,\sigma}$), either accelerated SGD on a single
machine or accelerated local SGD can improve over accelerated mini-batch SGD,
we have shown that for the problem class
$\mathcal{P}_{\zeta_{\star}=0}^{H,B,\sigma}$ such an improvement is not
possible222Note that on Example (7) also showed that single machine SGD must
incur a sub-optimality of order $HB^{2}$, making it much worse than local SGD,
and highlighting that $\mathcal{P}^{H,B,\sigma}_{hom}$ is a very special sub-
class of $\mathcal{P}_{\zeta=0}^{H,B,\sigma}$ with regards to the utility of
collaboration.. Thus, we can not hope to show the benefit of using
(accelerated) local SGD on any super-class of
$\mathcal{P}_{\zeta_{\star}=0}^{H,B,\sigma}$. In other words, we need
additional assumptions on top of Assumption 2 for $\mathcal{X}=S^{\star}$ to
avoid the pathologies of our hard instances. In the remainder of this paper we
will explore how additional higher-order assumptions can help improve local
SGD’s convergence.

##  4 Beating Mini-batch SGD with Higher-order Heterogeneity and Smoothness

Type of Result (Reference) | Convergence bound on $\mathbb{E}[F(\hat{x})-F(x^{\star})]\preceq/\succeq$
---|---
$\mu$-Strongly Convex $F$
Local SGD Upper Bound | $\frac{HB^{2}}{HKR+\lambda K^{2}R^{2}}+\frac{\sigma^{2}}{\mu MKR}+\frac{H\zeta^{2}}{\mu^{2}R^{2}}+\frac{H\sigma^{2}}{\mu^{2}KR^{2}}$
(Woodworth et al., 2020b)
Local SGD Upper Bound | $\exp\left(-\frac{\mu KR}{H}\right)HB^{2}+\frac{\sigma^{2}}{\mu MKR}+\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}$
(Yuan and Ma, 2020) ($\star$)
Local SGD Upper Bound | $\exp\left(-\frac{\mu KR}{H}\right)HB^{2}+\frac{\sigma^{2}}{\mu MKR}+\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}+\frac{Q^{2}\zeta^{4}}{\mu^{5}R^{4}}+\frac{\tau^{2}\sigma^{2}}{\mu^{3}KR^{2}}+\frac{\tau^{2}\zeta^{2}}{\mu^{3}R^{2}}$
(Theorem 5, Appendix D)
General Convex $F$
Local SGD Upper Bound | $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MKR}}+\frac{(H\zeta^{2}B^{4})^{1/3}}{R^{2/3}}+\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}$
(Woodworth et al., 2020b)
Local SGD Upper Bound | $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MKR}}+\frac{(Q\sigma^{2}B^{5})^{1/3}}{K^{1/3}R^{2/3}}$
(Yuan and Ma, 2020) ($\star$)
Local SGD Upper Bound | $\frac{HB^{2}}{KR}+\frac{\sigma B}{\sqrt{MKR}}+\frac{(\tau\sigma B^{3})^{1/2}}{K^{1/4}R^{1/2}}+\frac{(\tau\zeta B^{3})^{1/2}}{R^{1/2}}+\frac{(Q\sigma^{2}B^{5})^{1/3}}{K^{1/3}R^{2/3}}+\frac{(Q\zeta^{2}B^{5})^{1/3}}{R^{2/3}}$
(Theorem 3)
Alg. Independent Lower Bound | $\frac{HB^{2}}{K^{2}R^{2}}+\min\left\\{\frac{\sigma B}{\sqrt{MKR}},HB^{2}\right\\}+\min\left\\{\frac{HB^{2}}{R^{2}\log^{2}M},\frac{\sqrt{Q\sigma}B^{2}}{K^{1/4}R^{2}\log^{7/4}M},\frac{\sigma B}{\sqrt{KR}}\right\\}$
(Woodworth et al., 2021) ($\star$)

Table 2: Summary of old and new results for the problem class
$\mathcal{P}_{\tau}^{H,Q,B,\sigma}~{}\cap~{}\mathcal{P}_{\zeta(\mathbb{B}_{2}(D))}^{H,B,\sigma}$
for $\mu$-strongly-convex and convex average objective $F$. Rows with
($\star$) include results for the homogeneous setting.

In the previous section, we showed that we can not prove the effectiveness of
local SGD over mini-batch SGD if we consider the entire class
$\mathcal{P}^{H,B,\sigma}_{\zeta(S^{\star})}=\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}$.
On the other hand, recall that Woodworth et al. (2020b) did show such a result
over the “nearly homogeneous" class
$\mathcal{P}^{H,B,\sigma}_{\zeta(\mathbb{R}^{d})}$ (see Table 2). This prompts
us to ask the following question:

> Can local SGD dominate mini-batch SGD on the class
> $\mathcal{P}^{H,B,\sigma}_{\zeta(\mathbb{B}_{2}(D))}$, where
> $\mathbb{B}_{2}(D)$ is the $L_{2}$ ball of radius $D$ around $0$ for some
> sufficiently large $D$, and small $\zeta(\mathbb{B}_{2}(D))$?

Intuitively, if our problem has a low (but meaningful) heterogeneity, and we
can ensure that the local SGD iterates never leave the ball
$\mathbb{B}_{2}(D)$, for some large enough $D$, then we can recover the result
of Woodworth et al. (2020b), to show the effectiveness of local SGD on a much
larger problem class $\mathcal{P}_{\zeta(\mathbb{B}_{2}(D))}^{H,B,\sigma}$. To
enable this, we would need the following second-order heterogeneity
assumption, which controls how far the hessians on each machine can be from
the average hessian:

######  Assumption 3 (Bounded Second-order Heterogeneity).

A set of doubly-differentiable objectives $\\{F_{m}\\}_{m\in[M]}$ satisfy
$\tau$-second-order heterogeneity if for all $x\in\mathbb{R}^{d}$,

$\sup_{m,n\in[M]}\left\lVert\nabla^{2}F_{m}(x)-\nabla^{2}F_{n}(x)\right\rVert_{2}^{2}\leq\tau^{2}.$

######  Remark 7.

Assumption 3 has recently received attention in the non-convex setting
(Karimireddy et al., 2020b; Murata and Suzuki, 2021; Patel et al., 2022).
Patel et al. (2022) show that it is possible to show the dominance of local
update algorithms, essentially local SGD with variance reduction over mini-
batch algorithms when $\tau$ is much smaller than $H$.

Assumption 3 can always be satisfied by choosing $\tau\geq 2H$ for smooth
functions. We will denote the problems satisfying Assumption 3 by
$\mathcal{P}_{\tau}^{H,B,\sigma}$. Given Assumption 3, we note that on the set
$\mathbb{B}_{2}(D)$, we can bound $\zeta$ in terms of $\tau,\zeta_{\star}$ and
$D$ using the following upper bound (proved in Appendix D).

######  Proposition 3.

Given a problem instance in the class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}~{}\cap~{}\mathcal{P}_{\tau}^{H,B,\sigma}$
with objectives $\\{F_{m}\\}_{m\in[M]}$,

$\displaystyle\sup_{x\in\mathbb{B}_{2}(D),m\in[M]}\left\lVert\nabla
F_{m}(x)-\nabla F(x)\right\rVert_{2}^{2}\leq(\zeta_{\star}+\tau D)^{2}.$

The above proposition implies that for some level of first-order heterogeneity
$\zeta$ when $\tau$ is small, we can allow for a much larger $D$.
Alternatively, if we know our algorithm will be inside a ball
$\mathbb{B}_{2}(D)$, the smaller the second-order heterogeneity of our
problem, the smaller the bound on its first-order heterogeneity. In the
extreme case of $\tau=0$, we can replace $\zeta$ with $\zeta_{\star}$ (i.e.,
the converse of Proposition 1)! And as a sanity check, in the homogeneous
setting the right hand side is zero. Finally, we will also define a third-
order smoothness assumption in synergy with Assumption 3.

######  Assumption 4 (Third-order Smoothness).

The average function $F$ has a $Q$ Lipschitz hessian if

$\forall\
x,y\in\mathbb{R}^{d},\quad\left\lVert\nabla^{2}F(x)-\nabla^{2}F(y)\right\rVert_{2}\leq
Q\left\lVert x-y\right\rVert_{2}\enspace.$

The above assumption intuitively upper bounds the gap between a function and
its second-order approximation and is meaningful for smooth function only when
for a given $x,y\in\mathbb{R}^{d}$, $H\gg Q\left\lVert x-y\right\rVert_{2}$,
i.e., the bound implied by smoothness is loose. For sanity check, note that
when $Q=0$, then $F$ must be a quadratic function. We will denote the problems
satisfying Assumptions 3 and 4 by $\mathcal{P}^{H,Q,B,\sigma}_{\tau}$.

######  Remark 8.

For quadratic problems in the class $\mathcal{P}^{H,B,\sigma}_{hom}$,
Woodworth et al. (2020a) showed that accelerated local SGD is min-max optimal.
In particular, their result implies that local SGD can achieve an arbitrary
accuracy for a fixed number of communication rounds $R$ by increasing the
number of local steps $K$ per round. Given this result, several works (Yuan
and Ma, 2020; Bullins et al., 2021) have tried to use higher-order smoothness
assumptions to interpolate between the min-max optimal bounds for the
quadratic and convex homogeneous setting (Table 2).

We can obtain the following informal convergence result for the problem class
$\mathcal{P}^{H,Q,B,\sigma}_{\tau}\cap\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}$.
We state the full version of the above bound, and the step-size used to obtain
it, in Appendix D.

######  Theorem 3 (Informal).

For any $K,R,M\geq 1$ and $H,B,Q,\sigma,\tau\geq 0$ consider a problem
instance in the class
$\mathcal{P}^{H,Q,B,\sigma}_{\tau}~{}\cap~{}\left(\mathcal{P}^{H,B,\sigma}_{\zeta(\mathbb{B}_{2}(D))}~{}\cup~{}\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}\right)$,
where we assume $D$ is large-enough such that the local SGD iterates stay
inside the ball $\mathbb{B}_{2}(D)$. Then, for a fixed inner stepsize of
$\eta\leq\frac{1}{2H}$, and outer stepsize of $\beta=1$, we have the following
convergence rate (up to logarithmic factors) for local SGD (initialized at
zero):

$\displaystyle\mathbb{E}\left[F\left(\frac{1}{MKR}\sum_{m=1}^{M}\sum_{r=1}^{R}\sum_{k=0}^{K-1}x^{m}_{r,k}\right)-F(x^{\star})\right]\preceq\frac{HB^{2}}{KR}+\frac{\sigma
B}{\sqrt{MKR}}+\frac{(\tau\sigma
B^{3})^{1/2}}{K^{1/4}R^{1/2}}+\frac{(Q\sigma^{2}B^{5})^{1/3}}{K^{1/3}R^{2/3}}$
$\displaystyle+\min\left\\{\frac{(\tau\zeta
B^{3})^{1/2}}{R^{1/2}}+\frac{(Q\zeta^{2}B^{5})^{1/3}}{R^{2/3}},\frac{(\tau\zeta_{\star}B^{3})^{1/2}}{R^{1/2}}+\frac{(Q\zeta_{\star}^{2}B^{5})^{1/3}}{R^{2/3}}+\frac{(\tau^{2}DB^{3})^{1/2}}{R^{1/2}}+\frac{(Q\tau^{2}D^{2}B^{5})^{1/3}}{R^{2/3}}\right\\}\,.$

######  Remark 9.

Note that the bound implied by Proposition 3 is a worst-case bound for
problems in the class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}\cap\mathcal{P}_{\tau}^{H,B,\sigma}$.
And in general, there might exist an upper bound
$\zeta(\mathbb{B}_{2}(D))\ll\zeta_{\star}+\tau D$. For this reason, we have
stated our upper bounds in terms of $\zeta$ as well as only in terms of
$\tau,\zeta_{\star},D$.

To prove Theorem 3 we first obtain a convergence rate in the strongly convex
setting (Theorem 5) and then use the standard convex to strongly convex
reduction by adding appropriate regularization to our original problem. To the
best of our knowledge, Theorem 3 is the only upper bound for local SGD for
problems in the class
$\mathcal{P}^{H,Q,B,\sigma}_{\tau}~{}\cap~{}\mathcal{P}^{H,B,\sigma}_{\zeta(\mathbb{B}_{2}(D))}$
even for $D=\infty$, i.e., $\mathcal{X}=\mathbb{R}^{d}$ in Assumption 2. Note
that the upper bound can benefit from second-order heterogeneity, i.e.,
Assumption 3. In the extreme case, i.e., the homogeneous setting where
$\tau,\zeta=0$, our rate recovers the convergence rate by Yuan and Ma (2020)
(see Table 2). To compare our result to existing results in the heterogeneous
setting by Woodworth et al. (2020b), and to highlight the benefit of
Assumptions 3 and 4, we will now compare requirements on
$\zeta(\mathbb{B}_{2}(D))$ to reach some target sub-optimality $\epsilon$. For
simplicity, we will assume that $K$ is large enough to ignore all the terms in
the convergence bound with $K$ in the denominator. Then the requirements on
$\zeta$ are,

$\displaystyle\zeta_{old}\preceq\frac{\epsilon^{3/2}R}{H^{1/2}B^{2}}\qquad\text{
v/s
}\qquad\zeta_{our}\preceq\min\left\\{\frac{\epsilon^{3/2}R}{(QB)^{1/2}B^{2}},\frac{\epsilon^{2}R}{\tau
B^{3}}\right\\}.$ (11)

In the regime when $Q,\tau$ are small, this highlights that our requirements
are much less stringent on $\zeta$. The main limitation of our upper bound,
however, is that we assume there exists a $D$ such that,

$\sup_{m\in[M],r\in[R],k\in[0,K-1]}\left\lVert x_{r,K}^{m}\right\rVert_{2}\leq
D,$

and prove the upper bound in terms of such a $D$. In fact, we require this for
all (random) sequences of local SGD iterates. This is a strong assumption, but
we believe it can be avoided by choosing appropriate $\eta,\beta$ in terms of
problem-dependent quantities such as $\zeta_{\star},\tau,Q$ so that we can
control the norm of local SGD iterates (with high probability). We leave this
task for future work. For now, we conjecture the following result.

######  Conjecture 1 (Effectiveness of Local SGD).

Local SGD can dominate mini-batch SGD over the problem class
$\mathcal{P}_{\tau}^{H,Q,B,\sigma}~{}\cap~{}\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$
in the regime when $\tau,QB\ll H$ and $\sigma,\zeta_{\star}$ are small.

######  Remark 10.

In our setting, mini-batch SGD can not improve from additional assumptions on
top of convexity and smoothness (at least in the worst case). To see this, we
assume all the machines have the same objective $F$, a quadratic function
(which will be determined later). In this simple setup, note that all data
heterogeneity measures are zero, and since the objective is quadratic, $Q=0$
also. Essentially, mini-batch SGD reduces to optimizing $F$ with $R$ mini-
batch updates, each with batch size $MK$. Using Lemma 1 and standard sample
complexity lower bounds for mean-estimation (also a quadratic problem), we can
argue that the convergence rate for mini-batch SGD in this setting is
$\frac{HB^{2}}{R}+\frac{\sigma B}{\sqrt{MKR}}$, which does not benefit from
$\tau,\zeta_{\star},Q=0$. On the other hand, we conjecture above that local
SGD can significantly benefit from these low measures of heterogeneity and
sharpness. Thus, if the conjecture is true, we would identify a regime of low
data heterogeneity where local SGD dominates mini-batch SGD.

######  Remark 11 (Breaking our lower bound).

Another motivation for our conjecture is the observation that in Example 7 as
well as our construction for proving Theorem 1, the Hessians on the different
machines must be dissimilar. We can not cause the machines to drift between
communication rounds if they are not dissimilar, which is, in fact, not
possible when $\tau=0$. This is precisely why we believe controlling the
distance between the machines’ Hessians can break our lower bond.

While we do not yet know how to prove Conjecture 1 for the entire class
$\mathcal{P}_{\tau}^{H,Q,B,\sigma}~{}\cap~{}\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$,
we will prove a very special case of this conjecture in the next section for
strongly convex quadratic objectives on each machine which lie in the problem
class
$\mathcal{P}_{\tau}^{H,Q=0,B,\sigma=0}~{}\cap~{}\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma=0}$.
Quadratic objectives are analytically simpler, and we rely on a new fixed-
point perspective to understand the behavior of local SGD.

##  5 Fixed Point of Local SGD for Strongly Convex Objectives

Throughout this section, we will assume the objectives of each machine are of
the following form:

$\displaystyle
F_{m}(x)=\frac{1}{2}(x-x_{m}^{\star})^{T}A_{m}(x-x_{m}^{\star}),\ \forall
m\in[M]\,,$ (12)

where $A_{m}$ has minimum and maximum eigenvalues $\mu,H>0$ respectively and
$x_{m}^{\star}$ is the unique minimizer of $F_{m}$. We will denote the optimum
of the average objective $x^{\star}$ and the average of the optima of the
machines $\bar{x}^{\star}$ as follows where
$A:=\frac{1}{M}\sum_{m\in[M]}A_{m}$ is the average hessian:

$\displaystyle
x^{\star}:=\frac{1}{M}\sum_{m\in[M]}A^{-1}A_{m}x_{m}^{\star},\quad\text{ and
}\quad\bar{x}^{\star}:=\frac{1}{M}\sum_{m\in[M]}x_{m}^{\star},$ (13)

We will only consider the noiseless setting in this section. Given the
quadratic form of the machines’ objectives, we can also find a closed-form
expression for the fixed point of local gradient descent.

$5$$10$$15$$5$$10$$15$$20$$25$$\bm{x_{1}^{\star}}$$\bm{x_{2}^{\star}}$$\bm{x_{3}^{\star}}$$\bm{x_{4}^{\star}}$$\bm{x_{5}^{\star}}$$\bm{\bar{x}^{\star}}$$\bm{x^{\star}}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$F_{1}$$F_{2}$$F_{3}$$F_{4}$$F_{5}$$\bm{F}$$\leq\bm{\frac{\zeta_{\star}\tau}{H\mu}}$

$10$$10.5$$11$$11.5$$11$$11.5$$12$$12.5$$\bm{\bar{x}^{\star}}$$\bm{x^{\star}}$$\bm{F}$$\bm{K\to\infty}$ $\bullet$ | $\eta=\frac{1}{7}$
---|---
$\bullet$ | $\eta=\frac{1}{7K}$
$\bullet$ | $\eta=\frac{1}{7K^{2}}$

Figure 2: Illustration of a two-dimensional optimization problem with $M=5$
machines, each with a $1$-strongly convex, and $6$-smooth objective. On the
left figure, we draw the contour lines for each of the machine’s objective as
well as for the average objective. We also indicate the two relevant solution
concepts $\bar{x}^{\star}$ and $x^{\star}$ in the same figure, noting that
their distance is bounded by Proposition 5. On the right figure, we zoom into
the convex hull of the machines’ optima, noting the sequence of fixed points
for local GD as a function of $\eta$ and increasing $K\in[10]$. We plot the
fixed points for three different choices of $\eta$ each demonstrating a
different trend for $\lim_{K\to\infty}x_{\infty}(K,\eta,\beta)$.

######  Proposition 4.

Consider an instance of the problem of the form (12) with strongly convex and
smooth machines’ objectives. Let $x_{R}{K,\eta,\beta}$ be the local gradient
descent iterate after $R$ communication rounds, using exact gradient calls
(i.e., $\sigma=0$), $K$ local updates, and step-sizes, $\eta,\beta$. Then the
fixed point for local GD (whenever it exists) is given by,

$\displaystyle
x_{\infty}{K,\eta,\beta}:=\lim_{R\to\infty}x_{R}{K,\eta,\beta}=\frac{1}{M}\sum_{m\in[M]}C^{-1}C_{m}x_{m}^{\star}$

where $C_{m}=I-{I-\eta A_{m}}^{K}$ and $C=\frac{1}{M}\sum_{m\in[M]}C_{m}$.

######  Remark 12.

Note that the fixed point might not be defined for all choices of
$\eta,\beta,K$. Intuitively, it should be well defined when $\eta,\beta$ are
“small enough" relative to how $R$ increases. Also note that since $\sigma=0$,
the fixed point is non-random. When $\sigma>0$, we instead need to look at the
expected local SGD iterate.

Figure 3: Illustration of the same distributed problem as Figure 2 to
understand the where the fixed point converges as $K$ grows. We consider $7$
different choices of $\eta$ (as a function of $K$) and plot $\log\left\lVert
x_{\infty}(K,\eta,1)-x^{\star}\right\rVert_{2}$ as a function of $K\in[100]$.
We notice that for $\eta>\frac{1}{HK}$, the fixed point goes to
$\bar{x}^{\star}$ as $K$ increases, while for $\eta<\frac{1}{HK}$, the fixed
point gets progressively closer to $x^{\star}$.

Using the closed form of $x_{\infty}$ from Proposition 4 we can make two
observations (c.f., Figure 2):

#### 1\. The correct fixed point.

When $K=1$, for any choice of $\eta,\beta>0$ that ensures convergence of local
GD, $x_{\infty}=x^{\star}$. This is unsurprising because with $K=1$, local GD
reduces to GD on the averaged objective, so the fixed point must be a
stationary point of $F$, i.e., $x^{\star}$. We also observe in Figure 3 that
as $\eta$ decreases as a function of $K$, and $K\to\infty$ we recover the
correct fixed point. This is also expected, as the effect of local updates
diminishes with smaller $\eta$.

#### 2\. The incorrect fixed point.

On the other hand when $K\to\infty$ and we pick $\eta=\omega{\frac{1}{KH}}$
but $\eta<\frac{1}{H}$ we get that
$\lim_{K\to\infty}x_{\infty}(K,\eta,\beta)=\bar{x}^{\star}$. This makes
intuitive sense (at least for $\beta=1$) because for a large step-size $\eta$,
that also ensures convergence of GD on each machine, local GD between
communication rounds would converge to machines’ optima, and then averaging
the optima would yield $\bar{x}^{\star}$. In fact, using Assumptions 3 and 5
(a strongly convex variant of Assumption 2 on $S^{\star}$), we can show that
the distance between $\bar{x}^{\star}$, $x^{\star}$ and $x_{\infty}$ are
bounded as follows (see Figure 2).

######  Proposition 5.

Consider a problem instance of the form (12) with $\mu$-strongly convex and
$H$-smooth machines’ objectives satisfying Assumptions 3 and 5, then for
$K>1$,

$\displaystyle\left\lVert
x^{\star}-\bar{x}^{\star}\right\rVert_{2}\leq\frac{\zeta_{\star}\tau}{H\mu}\quad\text{
and }\quad\left\lVert
x_{\infty}(K,\eta,\beta)-\bar{x}^{\star}\right\rVert_{2}\leq\frac{\zeta_{\star}\tau}{H\mu}\cdot\frac{\eta\mu
K{1-\eta\mu}^{K-1}}{1-(1-\eta\mu)^{K}}\preceq\enspace\frac{\zeta_{\star}\tau}{H\mu}$

Using triangle inequality Proposition 5 bounds the fixed point discrepancy for
local SGD by some constant times $\frac{\zeta_{\star}\tau}{H\mu}$. Combining
it with a convergence guarantee for local SGD to its fixed point, we can get
the following convergence guarantee in the noise-less setting. To do so,
however, we will use the following stronger version of Assumption 1, which
makes more sense for strongly convex objectives.

######  Assumption 5 (Bounded Optima Heterogeneity).

A set of $H$-smooth and strongly convex objectives $\\{F_{m}\\}_{m\in[M]}$,
satisfy $\zeta_{\star}$-optima-heterogeneity if,

$\frac{1}{M}\sum_{m\in[M]}\left\lVert
x_{m}^{\star}-x^{\star}\right\rVert_{2}^{2}\leq\frac{\zeta_{\star}^{2}}{H^{2}},$

where $x_{m}^{\star}$ is the optimum of $F_{m}$ for all $m\in[M]$ and
$x^{\star}\in S^{\star}$ is the optimum of the average objective $F$.

Note that using smoothness along with Assumption 5 implies Assumption 2 for
$\mathcal{X}=S^{\star}$. Intuitively, when the machines have unique optima,
the most natural measure of heterogeneity is the distance between these optima
and the optima of the average objective, which the above assumption measures.
Note that a problem instance with objectives of the form (12) satisfying
Assumption 5 lies in the problem class
$\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$. With this assumption, we can give
the following convergence guarantee for local SGD (compare to Wang et al.
(2022) in Appendix C).

######  Theorem 4 (Local GD with Strongly Convex Objectives).

Consider a problem instance of the form (12) with $\mu$-strongly convex and
$H$-smooth machines’ objectives satisfying Assumptions 3 and 5, then for
$\beta=1$ and $\eta=\frac{1}{2H}$ we get the following convergence for local
GD initialized at zero,

$\displaystyle\left\lVert x_{R}-x^{\star}\right\rVert_{2}$
$\displaystyle\preceq
e^{-\frac{KR}{\kappa}}\cdot\frac{1-{\frac{1}{2}}^{K}}{1-{1-\frac{1}{2\kappa}}^{K}}B+\frac{\zeta_{\star}\tau}{H\mu}$

Assuming $K\geq\frac{1}{-\log_{2}{1-\frac{1}{2\kappa}}}$ this simplifies to,

$\displaystyle\left\lVert x_{R}-x^{\star}\right\rVert_{2}$
$\displaystyle\preceq Be^{-\frac{KR}{\kappa}}+\frac{\zeta_{\star}\tau}{H\mu}.$

Comparing this bound to the rate for GD (i.e., the noiseless variant of mini-
batch SGD), we see that when $\zeta_{\star},\tau$ are small local GD has a
much better optimization term v/s the optimization term $Be^{-R/\kappa}$ of
GD. This implies that we have identified a $\mu$-strongly sub-class of
$\mathcal{P}_{\tau}^{H,Q,B,\sigma=0}~{}\cap~{}\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma=0}$,
where local GD dominates GD. This further motivates us to believe that
Conjecture 1 is correct.

###  5.1 Two Stage Algorithms

Based on the discussion in this section, a natural question is how to reduce
the fixed-point discrepancy of local SGD. One approach based on the
observation in Figure 2 is to reduce the inner step-size of local SGD as
iterations proceed so that we get the benefit of more aggressive updates at
the beginning of training but can also avoid the fixed-point discrepancy at
the end of training. Note that reducing the inner step size actually reduces
local SGD to mini-batch SGD in the limit. Thus, an even easier approach to
fixing the fixed point issue is sharply transitioning from running local SGD
to mini-batch SGD (which has no fixed point issues) at the end of training.

Such a two-stage algorithm has been considered by Hou et al. (2021), motivated
by the results of Woodworth et al. (2020b). Theorem 4 provides a more fine-
grained perspective on this two-stage algorithm by capturing the effect of
$\zeta_{\star},\tau$ as opposed to $\zeta(\mathbb{R}^{d})$ in Hou et al.
(2021). In particular, we run local GD for the first phase until the
optimization (first) term in Theorem 4 dominates the convergence, i.e.,
$R_{1}=\theta{\frac{\kappa}{K}\ln{\frac{H\mu}{\zeta_{\star}\tau B}}}$ rounds.
At this point, we switch to running GD, i.e., the noiseless variant of mini-
batch SGD, for
$R_{2}=\theta{\kappa\ln{\frac{\zeta_{\star}\tau}{H\mu\epsilon}}}$, for some
target accuracy $\epsilon$. Thus, in total, the communication complexity of
this algorithm is given by,

$R(\epsilon)=R_{1}+R_{2}=\theta{\kappa\ln{{\frac{H\mu}{\zeta_{\star}\tau}\cdot\frac{1}{B}}^{1/K}{\frac{\zeta_{\star}\tau}{H\mu}\cdot\frac{1}{\epsilon}}}}.$

This communication complexity exemplifies the effect of local update steps,
where we notice that in the limit $K\to\infty$ the communication complexity of
the two-stage algorithm local GD->GD is much better than running GD alone as
long as $\frac{\zeta_{\star}\tau}{\mu}<<HB$.

###  5.2 Interpreting the Heterogeneity Assumptions

So far, we have introduced several heterogeneity assumptions in this paper. We
end this discussion by considering a simple linear regression model to
highlight how these assumptions might appear in real-world problems relating
to actual distribution shifts between clients. We will consider a linear
regression problem, where each data point is a co-variate label pair
$z_{m}:=(\beta_{m},y_{m})\sim\mathcal{D}_{m}$ on each client such that:

  * •

The covariates are sampled from a Gaussian distribution, i.e.,
$\beta_{m}\sim\mathcal{N}(\mu_{m},\Sigma_{m})\in\mathbb{R}^{d}$; and

  * •

The labels are generated as $y_{m}\sim\left\langle
x_{m}^{\star},\beta_{m}\right\rangle+\mathcal{N}(0,\sigma^{2}_{noise})\in\mathbb{R}$
for some ground truth model $x_{m}^{\star}\in\mathbb{R}^{d}$ on machine $m$.

The goal of each client is to minimize the mean squared error, i.e.,
$f(x;(\beta_{m},y_{m}))=\frac{1}{2}{y_{m}-\left\langle
x,\beta_{m}\right\rangle}^{2}$ and the expected loss function is given by,

which clearly fits in the model of smooth and strongly convex quadratic
functions we have considered in this section, as long as
$\mu_{m}\mu_{m}^{T}+\Sigma_{m}$ is positive semi-definite and
$\left\lVert\mu_{m}\mu_{m}^{T}+\Sigma_{m}\right\rVert_{2}\leq H$.
Interestingly, Assumptions 3 and 5 have a very nice interpretation in this
setting,

  * •

Note that for any $m,n\in[M]$,

$\left\lVert
A_{m}-A_{n}\right\rVert_{2}\leq(\left\lVert\mu_{m}\right\rVert_{2}+\left\lVert\mu_{n}\right\rVert_{2})\left\lVert\mu_{m}-\mu_{n}\right\rVert_{2}+\left\lVert\Sigma_{m}-\Sigma_{n}\right\rVert_{2}=:\tau_{m,n},$

Thus this problem satisfies Assumption 3 with
$\tau^{2}:=\sup_{m,n}\tau^{2}_{m,n}$ which in turn can be thought of as a
measure of the “co-variate shift" between the machines.

  * •

Similarly, note that for any $m,n\in[M]$,

$\left\lVert x_{m}^{\star}-x_{n}^{\star}\right\rVert_{2}^{2}\leq 2\left\lVert
x_{m}^{\star}-x^{\star}\right\rVert_{2}^{2}+2\left\lVert
x_{m}^{\star}-x^{\star}\right\rVert_{2}^{2},$

for $x\in S^{\star}$. Thus Assumption 5 controls the average “concept-shift"
between the clients as,

$\frac{1}{M^{2}}\sum_{m,n\in[M]}\left\lVert
x_{m}^{\star}-x_{n}^{\star}\right\rVert_{2}^{2}\leq\frac{4}{M}\sum_{m\in[M]}\left\lVert
x_{m}^{\star}-x^{\star}\right\rVert_{2}\leq 4\frac{\zeta_{\star}^{2}}{H^{2}}.$

In light of this interpretation, note that Theorem 4 implies that the local
SGD can approach a fast convergence rate, i.e., not suffer due to the fixed
point discrepancy, as long as either the co-variate shift ($\tau$) or the
concept shift ($\zeta_{\star}$) is low. We believe this provides a useful
interpretation for these heterogeneity assumptions, and this simple learning
problem might pave the way to a better understanding of distributed learning
algorithms. In particular, we posit the following problem, which is largely
open:

######  Open Problem 1.

For the distributed linear regression problem described in this setting, and
for different regimes of heterogeneity/distribution shift parameters
$\tau,\zeta_{\star}$ as well as problem dependent parameters $H,\mu,\sigma,B$
identifying the min-max optimal algorithms.

Answering the above problem requires analyzing other algorithms, such as the
two-stage algorithm mentioned in the previous sub-section, reconciling
existing literature in low heterogeneity regimes, including the homogeneous
regime, and identifying relevant lower bounds for the problem. Most
importantly, the insights from answering the above question might have many
useful prescriptions for the practice of distributed/federated learning in the
face of different natures of heterogeneity, such as co-variate/concept shift.
We hope to address this problem more comprehensively in future work.

##  6 Discussion

In this paper, we further the discussion around the convergence rate of local
SGD and establish the min-max optimal convergence rate for the much-studied
problem class $\mathcal{P}^{H,B,\sigma}_{\zeta_{\star}}$. While the lower
bound results of our paper seem to paint a negative picture for local SGD, we
believe their real message is to help us identify what additional
heterogeneity assumptions are required to show the effectiveness of local SGD.
Based on the paper’s upper bound results and our current insights, we believe
that combining first-order heterogeneity assumption with higher-order
assumptions is key to understanding the “real" behavior of local SGD. Towards
this end, we believe the main message of our paper is the following conjecture
(restated from Section 3):

######  Conjecture 2 (Effectiveness of Local SGD).

Local SGD can dominate mini-batch SGD over the problem class
$\mathcal{P}_{\tau}^{H,Q,B,\sigma}~{}\cap~{}\mathcal{P}_{\zeta_{\star}}^{H,B,\sigma}$
in the regime when $\tau,QB\ll H$ and $\sigma,\zeta_{\star}$ are small.
Proving this conjecture is an important future direction, and we believe it
can both enhance our understanding of local SGD and help design a better
algorithm for practice.

#### Acknowledgemnts.

We thank the anonymous reviewers at COLT, ICML, and NeurIPS, who helped
significantly improve the paper. We also thank Blake Woodworth and Brian
Bullins for several useful discussions. KKP was supported through the NSF
TRIPOD Institute on Data, Economics, Algorithms and Learning (IDEAL) and other
awards from DARPA and NSF. AZ and SUS acknowledge partial funding from a
Google Scholar Research Award.

## References

  * Wang et al. [2022] Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang.  On the unreasonable effectiveness of federated averaging with heterogeneous data.  _arXiv preprint arXiv:2206.04723_ , 2022.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25, 2012.
  * McMahan et al. [2016a] H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas.  Federated learning of deep networks using model averaging.  _arXiv preprint arXiv:1602.05629_ , 2016a.
  * McMahan et al. [2016b] H Brendan McMahan, Eider Moore, Daniel Ramage, S Hampson, and B Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data (2016).  _arXiv preprint arXiv:1602.05629_ , 2016b.
  * Woodworth et al. [2018] Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro.  Graph oracle models, lower bounds, and gaps for parallel stochastic optimization.  _Advances in neural information processing systems_ , 31, 2018.
  * Kairouz et al. [2019] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning. corr.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Wang et al. [2021] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al.  A field guide to federated optimization.  _arXiv preprint arXiv:2107.06917_ , 2021.
  * Charles et al. [2021] Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith.  On large-cohort training for federated learning.  _Advances in neural information processing systems_ , 34:20461–20475, 2021.
  * Lin et al. [2018] 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.
  * Woodworth et al. [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_ , pages 10334–10343. PMLR, 2020a.
  * Mcdonald et al. [2009] Ryan Mcdonald, Mehryar Mohri, Nathan Silberman, Dan Walker, and Gideon Mann.  Efficient large-scale distributed training of conditional maximum entropy models.  _Advances in neural information processing systems_ , 22, 2009.
  * Zinkevich et al. [2010] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola.  Parallelized stochastic gradient descent.  _Advances in neural information processing systems_ , 23, 2010.
  * Zhang et al. [2016] Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré.  Parallel sgd: When does averaging help?  _arXiv preprint arXiv:1606.07365_ , 2016.
  * Stich [2018] Sebastian U Stich.  Local sgd converges fast and communicates little.  _arXiv preprint arXiv:1805.09767_ , 2018.
  * Dieuleveut and Patel [2019] Aymeric Dieuleveut and Kumar Kshitij Patel.  Communication trade-offs for local-sgd with large step size.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Khaled et al. [2020] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local sgd on identical and heterogeneous data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4519–4529. PMLR, 2020.
  * Koloskova et al. [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_ , pages 5381–5393. PMLR, 2020.
  * Karimireddy et al. [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_ , pages 5132–5143. PMLR, 2020a.
  * Woodworth et al. [2020b] Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro.  Minibatch vs local sgd for heterogeneous distributed learning.  _Advances in Neural Information Processing Systems_ , 33:6281–6292, 2020b.
  * Yuan and Ma [2020] Honglin Yuan and Tengyu Ma.  Federated accelerated stochastic gradient descent.  _Advances in Neural Information Processing Systems_ , 33:5332–5344, 2020.
  * Woodworth et al. [2021] Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro.  The min-max complexity of distributed stochastic convex optimization with intermittent communication.  In _Conference on Learning Theory_ , pages 4386–4437. PMLR, 2021.
  * Glasgow et al. [2022] Margalit R Glasgow, Honglin Yuan, and Tengyu Ma.  Sharp bounds for federated averaging (local sgd) and continuous perspective.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9050–9090. PMLR, 2022.
  * Patel et al. [2023] Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, and Nathan Srebro.  Federated online and bandit convex optimization.  In _International Conference on Machine Learning_ , pages 27439–27460. PMLR, 2023.
  * McMahan and Ramage [2017] Brendan McMahan and Daniel Ramage.  Federated learning: Collaborative machine learning without centralized training data, Apr 2017.  URL https://ai.googleblog.com/2017/04/federated-learning-collaborative.html.
  * Dekel et al. [2012] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao.  Optimal distributed online prediction using mini-batches.  _Journal of Machine Learning Research_ , 13(1), 2012.
  * Ghadimi and Lan [2012] 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.
  * Blum et al. [2017] Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao.  Collaborative pac learning.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Nguyen and Zakynthinou [2018] Huy Nguyen and Lydia Zakynthinou.  Improved algorithms for collaborative pac learning.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Haghtalab et al. [2022] Nika Haghtalab, Michael Jordan, and Eric Zhao.  On-demand sampling: Learning optimally from multiple distributions.  _Advances in Neural Information Processing Systems_ , 35:406–419, 2022.
  * Han et al. [2023] Minbiao Han, Kumar Kshitij Patel, Han Shao, and Lingxiao Wang.  On the effect of defections in federated learning and how to prevent them.  _arXiv preprint arXiv:2311.16459_ , 2023.
  * Pathak and Wainwright [2020] Reese Pathak and Martin J Wainwright.  Fedsplit: An algorithmic framework for fast federated optimization.  _Advances in neural information processing systems_ , 33:7057–7066, 2020.
  * Charles and Konecny [2020] Zachary Charles and Jakub Konecny.  On the outsized importance of learning rates in local update methods.  _arXiv preprint arXiv:2007.00878_ , 2020.
  * Jhunjhunwala et al. [2023] Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi.  Fedexp: Speeding up federated averaging via extrapolation.  _arXiv preprint arXiv:2301.09604_ , 2023.
  * Karimireddy et al. [2020b] 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_ , 2020b.
  * Murata and Suzuki [2021] Tomoya Murata and Taiji Suzuki.  Bias-variance reduced local sgd for less heterogeneous federated learning.  _arXiv preprint arXiv:2102.03198_ , 2021.
  * Patel et al. [2022] Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nathan Srebro.  Towards optimal communication complexity in distributed non-convex optimization.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Bullins et al. [2021] Brian Bullins, Kumar Kshitij Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth.  A stochastic newton algorithm for distributed convex optimization.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Hou et al. [2021] Charlie Hou, Kiran K Thekumparampil, Giulia Fanti, and Sewoong Oh.  Fedchain: Chained algorithms for near-optimal communication cost in federated learning.  _arXiv preprint arXiv:2108.06869_ , 2021.
  * Carmon et al. [2020] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.  Lower bounds for finding stationary points i.  _Mathematical Programming_ , 184(1):71–120, 2020.
  * Zhao et al. [2021] Haoyu Zhao, Zhize Li, and Peter Richtárik.  Fedpage: A fast local stochastic gradient method for communication-efficient federated learning.  _arXiv preprint arXiv:2108.04755_ , 2021.
  * Khanduri et al. [2021] Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney.  Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Golub [2005] Gene H Golub.  Cme 302: Numerical linear algebra fall 2005/06 lecture 10.  2005\.
  * Kovalev et al. [2019] Dmitry Kovalev, Konstantin Mishchenko, and Peter Richtárik.  Stochastic newton and cubic newton methods with simple local linear-quadratic rates.  _arXiv preprint arXiv:1912.01597_ , 2019.
  * Stich [2019] Sebastian U Stich.  Unified optimal analysis of the (stochastic) gradient method.  _arXiv preprint arXiv:1907.04232_ , 2019.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.

##  Appendix A Missing Details from Section 2

###  A.1 Another First-order Heterogeneity Assumption

Karimireddy et al. [2020a] looked at a following relaxed first-order
heterogeneity assumption, but they were not able to show that local SGD
dominates large mini-batch SGD under this assumption.

######  Assumption 6 (Relaxed First-Order Heterogeneity Everywhere).

A set of objectives $\\{F_{m}\\}_{m\in[M]}$ satisfy $(\zeta_{\star},D)$-first-
order heterogeneity everywhere if for all $x\in\mathbb{R}^{d}$,

$\frac{1}{M}\sum_{m\in[M]}\left\lVert\nabla
F_{m}(x)\right\rVert_{2}^{2}\leq\zeta_{\star}^{2}+D^{2}\left\lVert\nabla
F(x)\right\rVert_{2}^{2}.$

This assumption “interpolates" between Assumption 2 over the unbounded domain
$\mathcal{X}=\mathbb{R}^{d}$ v/s at the optima $\mathcal{X}=S^{\star}$ for
different values of $D$. Furthermore, the restrictiveness of Assumption 2
pointed out in Proposition 1 does not extend to this assumption as long as
$D>0$. While we did not look at this assumption in this paper, it is also
promising for future work.

###  A.2 Proof of Proposition 1

###### Proof.

Note the following for any $m\in[M]$ using triangle inequality,

$\displaystyle sup_{x\in\mathbb{R}^{d}}\left\lVert\nabla F_{m}(x)-\nabla
F(x)\right\rVert_{2}$
$\displaystyle=sup_{x\in\mathbb{R}^{d}}\left\lVert(A_{m}-A)x+b_{m}-b\right\rVert_{2},$
$\displaystyle\geq
sup_{x\in\mathbb{R}^{d}}\left\lVert(A_{m}-A)x\right\rVert_{2}-\left\lVert
b_{m}-b\right\rVert_{2}.$

Denote the matrix $C_{m}:=A_{m}-A=[c_{m,1},\dots,c_{m,d}]$ using its column
vectors. Then take $x=\delta e_{i}$ where $e_{i}$ is the $i$-th standard basis
vector to note in the above inequality,

$\displaystyle sup_{x\in\mathbb{R}^{d}}\left\lVert\nabla F_{m}(x)-\nabla
F(x)\right\rVert_{2}$
$\displaystyle\geq\delta\left\lVert(A_{m}-A)e_{i}\right\rVert_{2}-\left\lVert
b_{m}-b\right\rVert_{2},$ $\displaystyle\geq\delta\left\lVert
c_{m,i}\right\rVert_{2}-\left\lVert b_{m}\right\rVert_{2}-\left\lVert
b\right\rVert_{2}.$

Assuming $\left\lVert b_{m}\right\rVert_{2},\left\lVert b\right\rVert_{2}$ are
finite, since we can take $\delta\to\infty$ we must have $\left\lVert
c_{m,i}\right\rVert_{2}=0$ for all $i\in[d]$ if $\zeta<\infty$. This implies
that $c_{m,i}=0$ for all $i\in[d]$, or in other words $A_{m}=A$. Since this is
true for all $m\in[M]$, the machines must have the same Hessians, and thus
they can only differ upto linear terms. ∎

##  Appendix B Missing Details from Section 3

###  B.1 Proof of Equation 7

###### Proof.

Note that the update on machine $m$ leading up to communication round $r$ is
as follows for $k\in[0,K-1]$ and $m=1$,

$\displaystyle x_{r,k+1}^{1}[1]=x_{r,k}^{1}[1]-\eta
H(x_{r,k}^{1}[1]-x^{\star}[1]),$ $\displaystyle\Rightarrow
x_{r,k+1}^{1}[1]=x^{\star}[1]+(1-\eta H)^{k+1}(x_{r,0}^{1}[1]-x^{\star}[1]),$
$\displaystyle\Rightarrow x_{r,K}^{1}[1]=x^{\star}[1]+(1-\eta
H)^{K}(x_{r-1}[1]-x^{\star}[1]),$ $\displaystyle\Rightarrow
x_{r,K}^{1}[1]-x_{r-1}[1]=(1-(1-\eta H)^{K})(x^{\star}[1]-x_{r-1}[1]).$

On the second dimension, the iterates don’t move at all for $m=1$,

$\displaystyle x_{r,K}^{1}[2]-x_{r-1}[2]=0.$

Writing a similar expression for the second machine and averaging these
updates we get,

$\displaystyle\frac{1}{2}\sum_{m\in[2]}(x_{r,K}^{m}-x_{r-1})=\frac{1}{2}(1-(1-\eta
H)^{K})(x^{\star}-x_{r-1}).$

This gives the update for communication round $r$ as follows,

which finishes the proof. ∎

###  B.2 Proof of Lemma 1

###### Proof.

Let $A$ be the Hessian of $F$. Observe that we have
$F(x)-F(x^{\star})=\frac{1}{2}(x-x^{\star})^{T}A(x-x^{\star}).$

Let $v_{1}$ and $v_{2}$ be the eigenvectors of norm $1$ of $A$ with the
greatest and least eigenvalues, respectively. Assume
$x^{\star}:=-B\left(\frac{v_{1}+v_{2}}{\sqrt{2}}\right)$, which ensures
$\|x^{\star}\|_{2}=B$. Then, solving for the GD iterates in closed form, we
have

$x_{R}-x^{*}=\frac{B}{\sqrt{2}}\left(1-\eta
H\right)^{R}v_{1}+\frac{B}{\sqrt{2}}\left(1-\eta\frac{H}{\kappa}\right)^{R}v_{2}.$
(14)

Observe that if $\eta\geq\frac{3}{H}$, then the iterates explode and we have
$F(x_{R})\geq F(x_{0})\geq\Omega\left(HB^{2}\right)$.

If $\eta\leq\frac{3}{H}$, then using the fact that $\kappa\geq 6$, we have

$\displaystyle F(x_{R})-F(x^{\star})$
$\displaystyle\geq\frac{1}{2}\left(\frac{B}{\sqrt{2}}\left(1-\frac{3}{\kappa}\right)^{R}v_{2}\right)^{T}A\left(\frac{B}{\sqrt{2}}\left(1-\frac{3}{\kappa}\right)^{R}v_{2}\right)$
(15)
$\displaystyle=\frac{B^{2}}{4}\left(1-\frac{3}{\kappa}\right)^{2R}v_{2}^{T}Av_{2}$
(16)
$\displaystyle=\frac{B^{2}}{4}\left(1-\frac{3}{\kappa}\right)^{2R}\frac{H}{\kappa}$
(17) $\displaystyle\geq\frac{HB^{2}}{4\kappa}e^{-12R/\kappa}.$ (18)

The result follows. ∎

###  B.3 Proof of Proposition 2

###### Proof.

We will consider a two-dimensional problem in the noiseless setting for this
proof, as we do not want to understand the dependence on $\sigma$ or $d$.
Define $A_{1}:=\left(\begin{array}[]{cc}1&0\\\ 0&0\end{array}\right)$ and
$A_{2}:=vv^{T}$, where $v=(\alpha,\sqrt{1-\alpha^{2}})$ and $\alpha\in(0,1)$.
For even $m$, let

$F_{m}(x):=\frac{H}{2}(x-x^{*})^{T}A_{1}(x-x^{*})\enspace.$

For odd $m$, let

$F_{m}(x):=\frac{H}{2}(x-x^{*})^{T}A_{2}(x-x^{*})\enspace.$

Note that $A_{1}$ and $A_{2}$ are rank-1 and have eigenvalues $0$ and $1$, and
thus they satisfy Assumption 2. Furthermore, both the functions have a shared
optimizer $x^{\star}$. It is easy to verify that,

$(I-\eta HA_{i})^{K}=I-(1-(1-\eta H)^{K})A_{i}=:I-\widetilde{\eta}HA_{i},$

where $\widetilde{\eta}:=(1-(1-\eta H)^{K})/H$. Note that the above property
will be crucial for our construction, and we can not satisfy this property if
our matrices are not ranked one. For any $x$, let us denote the centered
iterate by $\tilde{x}:=x-x^{\star}$. Then, for any $r\in[R]$ and $m\in[M]$ we
have

$\tilde{x}^{m}_{r,K}=(I-\eta
HA_{m})^{K}\tilde{x}_{r-1}=(I-\widetilde{\eta}HA_{m})\tilde{x}_{r-1}.$

Using this, we can write the updates between two communication rounds as,

where we used that $F(x)=\frac{H}{2}(x-x^{\star})^{T}A(x-x^{\star})$, for
$A=(1-a)A_{1}+aA_{2}$ and

$a:=\left\\{\begin{array}[]{ll}1/2&\text{if $M$ is even},\\\
(M+1)/2M&\text{otherwise}.\end{array}\right.$

This implies the iterates of local GD across communication rounds are
equivalent to GD on $F(x)$ with step size $\beta(1-(1-\eta H)^{K})/H$.
Combining this observation with Lemma 1 about the function sub-optimality of
gradient descent updates will finish the proof. To use the lemma, however, we
need to verify our average function $F$ has condition number $\Omega(R)$. We
can explicitly compute the eigenvalues of $A$ as follows,

$\displaystyle\lambda_{1}$
$\displaystyle=\frac{1}{2}+\sqrt{\frac{1}{4}-(a-a^{2})(1-\alpha^{2})},$
$\displaystyle\lambda_{2}$
$\displaystyle=\frac{1}{2}-\sqrt{\frac{1}{4}-(a-a^{2})(1-\alpha^{2})}.$

Note that $\lim_{\alpha\rightarrow 1}\lambda_{1}=1$, and
$\lim_{\alpha\rightarrow 1}\lambda_{2}=0$ and thus $\lim_{\alpha\rightarrow
1}\lambda_{1}/\lambda_{2}=\infty$. Since $\lambda_{1}/\lambda_{2}=1$ when
$\alpha=0$, by the intermediate value theorem, we can choose $\alpha$ to get
$\kappa=\Omega(R)$ for the average objective $F$. Thus, we can use Lemma 1 and
finish the proof. ∎

Note that in the construction used in the above proof, the machines share an
optimum point $x^{\star}$, which ensures that $\zeta_{\star}=0$.

###  B.4 Proof of Theorem 1

###### Proof.

To combine the hard instance in Proposition 2 with the previous hard instance
of Glasgow et al. [2022] we simply place the two instances on disjoint co-
ordinates increasing the dimensionality of our hard instance. This is a
standard technique to combine lower bounds. To get rid of the terms with the
minimum function in the lower bound of Glasgow et al. [2022], we note the
following,

  * •

$\frac{\sigma
B}{\sqrt{KR}}\geq\frac{(H\sigma^{2}B^{4})^{1/3}}{K^{1/3}R^{2/3}}$ implies that
$\frac{\sigma B}{\sqrt{KR}}\leq\frac{HB^{2}}{R}$, and

  * •

$\frac{\zeta_{\star}^{2}}{H}\geq\frac{(H\zeta_{\star}^{2}B^{4})^{1/3}}{R^{2/3}}$
implies that $\frac{\zeta_{\star}^{2}}{H}\leq\frac{HB^{2}}{R}$.

These observations allow us to avoid the minimum operations, thus concluding
the proof. ∎

###  B.5 Distributed Zero-respecting Algorithms

Intermittent communication is motivated by the sizeable gap between the wall-
clock time $\mathcal{C}$ required for a single synchronous communication and
the time required per unit of computation $\mathcal{T}$, say a single oracle
call [McMahan et al., 2016b, Kairouz et al., 2019]. For an efficient
implementation, typically, we want our local computation budget $K$ to be
comparable to $\mathcal{C}/\mathcal{T}$, i.e., we want to increase our
computation load per communication to match the time required for a single
communication round. We consider a generalization of zero respecting
algorithms [Carmon et al., 2020] denoted by $\mathcal{A}_{ZR}$ in the
intermittent communication (IC) setting defined as follows.

######  Definition 1 (Distributed Zero-respecting Algorithms).

Consider $M$ machines in the IC setting, each endowed with an oracle
$\mathcal{O}_{m}:\mathcal{I}\times\mathcal{Z}\to\mathcal{V}$ and a
distribution $\mathcal{D}_{m}$ on $\mathcal{Z}$. Let $I_{r,k}^{m}$ denote the
input to the $k^{th}$ oracle call, leading up to the $r^{th}$ communication
round on machine $m$. An optimization algorithm initialized at $0$ is
distributed zero-respecting if:

  1. 1.

for all $\ r\in[R],k\in[K],m\in[M]$, $I_{r,k}^{m}$ is in

$\left\\{\bigcup_{l\in[k-1]}supp\left(\mathcal{O}_{F_{m}}(I_{r,l}^{m};z_{r,l}^{m}\sim\mathcal{D}_{m})\right)\right\\}\cup\left\\{\bigcup_{n\in[M],s\in[r-1],l\in[K]}supp\left(\mathcal{O}_{F_{n}}(I_{s,l}^{n};z_{s,l}^{n}\sim\mathcal{D}_{n})\right)\right\\},$

  2. 2.

for all $\ r\in[R],k\in[K],m\in[M]$, $I_{r,k}^{m}$ is a deterministic function
(which is same across all the machines) of

$\left\\{\bigcup_{l\in[k-1]}\mathcal{O}_{F_{m}}(I_{r,l}^{m};z_{r,l}^{m}\sim\mathcal{D}_{m})\right\\}\cup\left\\{\bigcup_{n\in[M],s\in[r-1],l\in[K]}\mathcal{O}_{F_{n}}(I_{s,l}^{n};z_{s,l}^{n}\sim\mathcal{D}_{n})\right\\},$

  3. 3.

at the $r^{th}$ communication round, the machines only communicate vectors in

$\left\\{\bigcup_{n\in[M],s\in[r],l\in[K]}supp\left(\mathcal{O}_{F_{n}}(I_{s,l}^{n};z_{s,l}^{n}\sim\mathcal{D}_{n})\right)\right\\},$

where $supp\left(.\right)$ denotes the co-ordinate support/span of its
arguments. We denote this class of algorithms by
$\boldsymbol{\mathcal{A}_{ZR}}$. Furthermore, if all the oracle inputs are the
same between two communication rounds, i.e., $I_{r,k}^{m}=I_{r}\in\mathcal{I}$
for all $m\in[M],k\in[K],r\in[R]$, then we say that the algorithm is
centralized, and denote this class of algorithms by
$\boldsymbol{\mathcal{A}_{ZR}^{cent}}\subset\mathcal{A}_{ZR}$.

This class captures a very wide variety of distributed optimization
algorithms, including mini-batch SGD [Dekel et al., 2012], accelerated mini-
batch SGD [Ghadimi and Lan, 2012], local SGD [McMahan et al., 2016b], as well
as all the variance-reduced algorithms [Karimireddy et al., 2020b, Zhao et
al., 2021, Khanduri et al., 2021]. Non-distributed zero-respecting algorithms
are those whose iterates have components in directions about which the
algorithm has no information, meaning that, in some sense, it is just “wild
guessing”. We have also defined the smaller class of centralized algorithms
$\mathcal{A}_{ZR}^{cent}$. These algorithms query the oracles at the same
point within each communication round and use the combined $MK$ oracle queries
each round to get a “mini-batch” estimate of the gradient. Thus, the class
$\mathcal{A}_{ZR}^{cent}$ includes algorithms such as mini-batch SGD [Dekel et
al., 2012, Woodworth et al., 2020b], but doesn’t include local-update
algorithms in $\mathcal{A}_{ZR}$ such as local-SGD.

###  B.6 Proof of Theorem 2

For even $m$, let

$F_{m}(x):=\frac{H}{2}\left((q^{2}+1)(q-x_{1})^{2}+\sum_{i=1}^{\lfloor{(d-1)/2}\rfloor}(qx_{2i}-x_{2i+1})^{2}\right),$
(21)

and for odd $m$, let

$F_{m}(x)=\frac{H}{2}\left(\sum_{i=1}^{\lfloor{d/2}\rfloor}(qx_{2i-1}-x_{2i})^{2}\right).$
(22)

Thus we have

$F(x)=\mathbb{E}_{m}[F_{m}(x)]=\frac{H}{2}\left((q^{2}+1)(q-x_{1})^{2}+\sum_{i=1}^{\boldsymbol{d}}(qx_{i}-x_{i+1})^{2}\right).$
(23)

Observe that the optimum of $F$ is attained at $x^{\star}$, where
$x^{\star}_{i}=q^{i}$. Theorem 2 improves on the previous best lower bounds by
introducing the term $\frac{HB^{2}}{R^{2}}$. Combining the following lemma
with standard arguments to achieve the $\frac{\sigma B}{\sqrt{MKR}}$ suffices
to prove Theorem 2.

######  Lemma 2.

For any $K\geq 2,R,M,H,B,\sigma$, there exist $f(x;xi)$ and distributions
$\\{\mathcal{D}_{m}\\}$, each satisfying assumptions 2, 4, 3, and together
satisfying $\frac{1}{M}\sum_{m=1}^{M}\|\nabla F_{m}(x^{\star})\|_{2}^{2}=0$,
such that for initialization $x^{(0,0)}=0$, the final iterate $\hat{x}$ of any
zero-respecting with $R$ rounds of communication and $KR$ gradient
computations per machine satisfies

$\displaystyle\mathbb{E}\left[F(\hat{x})\right]-F(x^{\star})\succeq\frac{HB^{2}}{R^{2}}.$
(24)

###### Proof.

Consider the division of functions onto machines described above for some
sufficiently large $d$.

Let $q=1-\frac{1}{R}$, and let
$t=\frac{1}{2}\log_{q}\left(\frac{B^{2}}{R}\right)$. We begin at the iterate
$x_{0}$, where the coordinate $(x_{0})_{i}=q^{i}$ for all $i<t$, and
$(x_{0})_{i}=0$ for $i\geq t$. Observe that
$\|x_{0}-x^{\star}\|^{2}\leq\sum_{i=t}^{\infty}q^{2i}\leq\frac{q^{2t}}{1-q^{2}}\leq
Rq^{2t}\leq B^{2}$.

Observe that for any zero-respecting algorithm, on odd machines, if for any
$i$, we have $x_{2i}^{m}=x_{2i+1}^{m}=0$, then after any number of local
computations, we still have $x_{2i+1}=0$. Similarly, on even machines, if for
any $i$, we have $x_{2i-1}^{m}=x_{2i}^{m}=0$, then after any number of local
computations, we still have $x_{2i}=0$.

Thus, after $R$ rounds of communication, on all machines, we have
$x_{i}^{m}=0$, for all $i>t+R$. Thus for $d$ sufficiently large, we have
$\|\hat{x}-x^{\star}\|^{2}\geq\sum_{i=t+R+1}^{d}{q^{2i}}\geq\frac{q^{2t+2R+2}-q^{2d}}{1-q^{2}}=\Omega\left(B^{2}q^{2R+2}\right)=\Omega(B^{2})$
since $q=1-\frac{1}{R}$.

Now observe that the Hessian of $F$ is a tridiagonal Toeplitz matrix with
diagonal entries $H(q^{2}+1)$ and off-diagonal entries $-Hq$. It is well-known
(see e.g., Golub [2005]) that the $d$ eigenvalues of $\tilde{M}$ are
$(1+q^{2})H+2qH\cos\left(\frac{i\pi}{d+1}\right)$ for $i=1,\ldots,d$. Thus
since $\cos(x)\geq-1$, we know that $F$ has strong-convexity parameter at
least $H(q^{2}+1-2q)=\Omega\left(\frac{H}{R^{2}}\right)$, so we have
$F(\hat{x})-F(x^{*})\geq\Omega\left(B^{2}\right)\Omega\left(\frac{H}{R^{2}}\right),$
which gives the desired result. ∎

##  Appendix C On the Assumption of Wang et al. [2022]

We will now consider the first-order assumption introduced by Wang et al.
[2022]. As discussed in Section 2, Assumption 2 is very restrictive when
$\mathcal{X}=\mathbb{R}^{d}$ . Wang et al. [2022] claim that even with
$\mathcal{X}=S^{\star}$, the optima of $F(x)$, Assumption (2) (and by
implication Assumption 6) can be restrictive in some settings. They propose an
alternative assumption that instead tries to capture how much the local
iterates move when initialized at an optimum of the averaged function $F$.

######  Assumption 7 (Movement at Optima).

Given an inner step-size $\eta$, local steps $K$, and
$x^{\star}\in\arg\min_{x\in\mathbb{R}^{d}}F(x)$ assume,

$\frac{1}{M\eta
K}\left\lVert\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{K}\right\rVert_{2}\leq\rho,$

where $\hat{x}^{m}_{K}$ is the iterate on machine $m$ after making $K$ local
steps (using exact gradients) initialized at $x^{\star}$.

Unlike all other assumptions, note that $\rho$ in Assumption 7 can be a
function of the hyper-parameters $\eta$ and $K$ despite normalizing with $\eta
K$. Wang et al. [2022] argue that Assumption 7 is much less restrictive than
the other first-order assumptions (Assumption 2 with
$\mathcal{X}=\mathbb{R}^{d}$ or with $\mathcal{X}=S^{\star}$). And, when the
client’s objectives are strongly convex, they show a provable domination over
large-mini-batch SGD in a regime of low heterogeneity (see the discussion in
Section 3). However, it is unclear if the assumption is useful in the general
convex setting, where we often empirically see that local SGD outperforms
mini-batch SGD. We show in Section 3 that this assumption is not useful in the
convex setting because of the following connection with Assumption 2 for
$\mathcal{X}=S^{\star}$.

######  Proposition 6.

If the functions of the machines $\\{F_{m}\\}_{m\in[M]}$ satisfy Assumption 2
for $\mathcal{X}=S^{\star}$ with $\zeta_{\star}$, then we have,

$\left\lVert\frac{1}{M\eta
K}\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{K}\right\rVert_{2}\leq\zeta_{\star}{{1+\eta
H}^{K-1}-1}.$

###### Proof.

Define $\phi(k):=\left\lVert\frac{1}{M\eta
K}\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{k}\right\rVert_{2}$ where
$\hat{x}^{m}_{k}$ is the $k$th gradient descent iterate on machine $m$
initialized at $\hat{x}^{m}_{0}=x^{\star}$. Then note the following,

$\displaystyle\phi(K)$ $\displaystyle=\left\lVert\frac{1}{M\eta
K}\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{K}\right\rVert_{2},$
$\displaystyle=\left\lVert\frac{1}{M\eta
K}\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{K-1}+\eta\nabla
F_{m}(\hat{x}^{m}_{K-1})\right\rVert_{2},$
$\displaystyle\leq\left\lVert\frac{1}{M\eta
K}\sum_{m\in[M]}x^{\star}-\hat{x}^{m}_{K-1}\right\rVert_{2}+\left\lVert\frac{1}{MK}\sum_{m\in[M]}\nabla
F_{m}(\hat{x}^{m}_{K-1})\right\rVert_{2},$
$\displaystyle=\phi(K-1)+\left\lVert\frac{1}{MK}\sum_{m\in[M]}\nabla
F_{m}(\hat{x}^{m}_{K-1})-\nabla F_{m}(x^{\star})\right\rVert_{2},$
$\displaystyle\leq\phi(K-1)+\frac{1}{MK}\sum_{m\in[M]}\left\lVert\nabla
F_{m}(\hat{x}^{m}_{K-1})-\nabla F_{m}(x^{\star})\right\rVert_{2},$
$\displaystyle\leq\phi(K-1)+\frac{H}{MK}\sum_{m\in[M]}\left\lVert\hat{x}^{m}_{K-1}-x^{\star}\right\rVert_{2},$
$\displaystyle=\phi(K-1)+\frac{H}{K}\delta(K-1),$ (25)

where we define
$\delta(k):=\frac{1}{M}\sum_{m\in[M]}\left\lVert\hat{x}^{m}_{k}-x^{\star}\right\rVert_{2}$.
Now we consider another recursion on $\delta(k)$ to introduce the
$\zeta_{\star}$ assumption:

Plugging (LABEL:eq:recursion_2) back into 25 we get,

which proves the claim. ∎

######  Remark 13.

When Assumption 2 for $\mathcal{X}=S^{\star}$ can be satisfied with
$\zeta_{\star}=0$, we can satisfy Assumption 7 with $\rho=0$.

As might be evident already, Proposition 2 has implications for the
heterogeneity assumption by Wang et al. [2022]. This is because the
construction used in the proposition satisfies Assumption 7 with $\rho=0$. In
particular, in the general convex setting under Assumption 7, local SGD can
not hope to benefit in the optimization term from a large $K$. This implies
that it is not possible to explain the effectiveness of local SGD by
controlling the movement of the local iterates at the optima, as postulated by
Wang et al. [2022]. Note that Theorem 2 also applies to Assumption 7. Thus,
large mini-batch SGD is also min-max optimal under Assumptions 2, 4, and 7 for
convex objectives.

To reconcile this negative result with the upper bound of Wang et al. [2022],
we note that their analyses crucially rely on the strong convexity of each
machine’s objective and not just the strong convexity of the average function,
something which is lacking in our hard instance in Proposition 2. This
highlights that controlling the client drift for local SGD between
communication rounds in the general convex setting is much more challenging
due to potential directions of no information on each machine (both
$A_{1},A_{2}$ are rank one in Proposition 2).

###  C.1 Beating Mini-batch SGD

Finally, we note that for quadratic functions of the form discussed in Section
5, we can bound the average movement at optimum as follows,

If $\eta=\frac{1}{2HK^{p}}$ for $p<1$, and $K\to\infty$ we get that,

$\displaystyle\lim_{K\to\infty}\rho$
$\displaystyle\leq\lim_{K\to\infty}\frac{1-(1-\eta H)^{K}}{\eta
K}\zeta_{\star},$
$\displaystyle\leq\lim_{K\to\infty}\frac{1-{1-\frac{1}{2K^{p}}}^{K}}{K^{1-p}}\cdot
2L\zeta_{\star}$ $\displaystyle=0.$

On the other hand, if $\eta=\frac{1}{2HK}$, then we get that,

This suggests that the Corollary 2 in Wang et al. [2022] must use
$\eta=\Omega{\frac{1}{K}}$ to ensure that $\rho$ can reach arbitrarily small
values. Unfortunately the corollary can only be obtained by setting
$\eta<\min\left\\{\frac{1}{\mu K},\frac{1}{L}\right\\}$. Thus, in their
existing result, it seems impossible to improve the convergence w.r.t. MB-SGD
unconditionally. This also highlights that our result in Theorem 4 is much
cleaner, depends on only problem-dependentth parameters, and can improve over
mini-batch SGD.

##  Appendix D Missing Proofs from Section 4

###  D.1 Proof of Poposition 3

###### Proof.

Denote the function $G_{m}:=F_{m}-F$ for all $m\in[M]$. Then note that using
Taylor expansion, we can write for any $x\in_{2}(D)$ and $x^{\star}\in S$,

$\displaystyle\nabla G_{m}(x)-\nabla
G_{m}(x^{\star})=\left[\int_{0}^{1}\nabla^{2}G_{m}(x^{\star}+s(x-x^{\star}))ds\right](x-x^{\star}).$

Re-arranging, taking norm, and applying triangle inequality implies,

$\displaystyle\left\lVert\nabla G_{m}(x)\right\rVert_{2}$
$\displaystyle=\left\lVert\nabla
G_{m}(x^{\star})+\left[\int_{0}^{1}\nabla^{2}G_{m}(x^{\star}+s(x-x^{\star}))ds\right](x-x^{\star})\right\rVert_{2},$
$\displaystyle\leq\left\lVert\nabla
F_{m}(x^{\star})\right\rVert_{2}+\left\lVert\int_{0}^{1}\nabla^{2}G_{m}(x^{\star}+s(x-x^{\star}))ds\right\rVert_{2}\left\lVert
x-x^{\star}\right\rVert_{2},$ $\displaystyle\leq\left\lVert\nabla
F_{m}(x^{\star})\right\rVert_{2}+\left[\int_{0}^{1}\left\lVert\nabla^{2}G_{m}(x^{\star}+s(x-x^{\star}))\right\rVert_{2}ds\right]\left\lVert
x-x^{\star}\right\rVert_{2},$ $\displaystyle\leq\left\lVert\nabla
F_{m}(x^{\star})\right\rVert_{2}+\left[\int_{0}^{1}\tau ds\right]D,$
$\displaystyle\leq\left\lVert\nabla F_{m}(x^{\star})\right\rVert_{2}+\tau D.$

Averaging over the machines and noting the definition of $\zeta_{\star}$ gives
us the desired result. ∎

###  D.2 Convergence in the Strongly Convex Setting

Recall that the average objective $F$ is $\mu$-strongly convex, if for all
$x,y\in\mathbb{R}^{d}$,

$F(y)+\left\langle\nabla F(y),x-y\right\rangle+\frac{\mu}{2}\left\lVert
x-y\right\rVert_{2}^{2}\leq F(x).$

We can give the following upper bound for local SGD for optimizing problems in
the class $\mathcal{P}^{H,Q,B,\sigma}_{\tau}$ with $\mu$-strongly convex
average objective.

######  Theorem 5 (Informal, Strongly Convex).

For any $K,R,M\geq 1$ and $H,B,Q,\sigma,\tau,\geq 0,\ \mu>0$ consider a
problem instance in the class $\mathcal{P}^{H,Q,B,\sigma}_{\tau}$, with
$\mu$-strongly convex average objective $F$. Then there exists a sequence of
weights $w_{r,k}\geq 0$, for $r\in[R],k\in[0,K-1]$ and a fixed inner stepsize
of $\eta\leq\frac{1}{2H}$ such that with outer stepsize of $\beta=1$ we have
the following convergence rate (up to logarithmic factors) for local SGD where
$W_{R,K}=\sum_{r\in[R],k\in[0,K-1]}w_{r,k}$:

$\displaystyle\mathbb{E}$
$\displaystyle\left[F\left(\frac{1}{MW_{R,K}}\sum_{m=1}^{M}\sum_{r=1}^{R}\sum_{k=0}^{K-1}w_{r,k}x^{m}_{r,k}\right)-F(x^{\star})+\mu\left\lVert\frac{1}{M}\sum_{m\in[M]}x_{R,K}^{m}-x^{\star}\right\rVert_{2}^{2}\right]\preceq$
$\displaystyle\qquad\qquad\qquad\qquad HB^{2}\exp\left(-\frac{\mu
KR}{H}\right)+\frac{\sigma^{2}}{\mu
MKR}+\frac{\tau^{2}\sigma^{2}}{\mu^{3}KR^{2}}+\frac{\tau^{2}\zeta^{2}}{\mu^{3}R^{2}}+\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}+\frac{Q^{2}\zeta^{4}}{\mu^{5}R^{4}}\,.$

Proof of this Theorem can be found in D.4.

###  D.3 Useful Lemmas

In this section, we provide a list of useful lemmas which will be used in the
proofs. We use the notation $\mathbb{E}_{t}$ for expectation conditioned on
$x^{1}_{t},...,x^{M}_{t}$ and $\mathbb{E}$ for the unconditional expectation.

######  Lemma 3.

For a convex function $F$ we have:

$F\left(\frac{1}{M}\sum_{m=1}^{M}x_{m}\right)\leq\frac{1}{M}\sum_{m=1}^{M}F(x_{m})\,.$
(26)

######  Lemma 4.

For a set of $M$ vectors $a_{1},a_{2},...,a_{M}\in\mathbb{R}^{d}$ we have:

$\left\lVert\sum_{m=1}^{M}a_{m}\right\rVert_{2}\leq\sum_{m=1}^{M}\left\lVert
a_{m}\right\rVert_{2}\,.$ (27)

######  Lemma 5.

For a set of $M$ vectors $a_{1},a_{2},...,a_{M}\in\mathbb{R}^{d}$ we have:

$\left\lVert\sum_{m=1}^{M}a_{m}\right\rVert_{2}^{2}\leq
M\sum_{m=1}^{M}\left\lVert a_{m}\right\rVert_{2}^{2}\,.$ (28)

######  Lemma 6.

For two arbitrary vectors $a,b\in\mathbb{R}^{d}$ and $\forall\gamma>0$ we
have:

$\left\lVert a+b\right\rVert_{2}^{2}\leq(1+\gamma)\left\lVert
a\right\rVert_{2}^{2}+(1+\gamma^{-1})\left\lVert b\right\rVert_{2}^{2}\,.$
(29)

######  Lemma 7.

Let Assumption 3 hold. Then we have:

$\displaystyle\mathbb{E}_{t}\left\lVert\frac{1}{M}\sum_{m=1}^{M}g^{m}_{t}-\frac{1}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})\right\rVert_{2}^{2}\leq\frac{\sigma^{2}}{M}\,.$ (30)

######  Lemma 8.

Let $F$ be a convex and $H$-smooth function. Then for any
$x,y\in\mathbb{R}^{d}$ we have:

$\frac{1}{2H}\left\lVert\nabla F(x)-\nabla F(y)\right\rVert_{2}^{2}\leq
F(y)-F(x)+\langle\nabla F(x),x-y\rangle\,.$ (31)

######  Lemma 9.

Let Assumption 3 hold and $F(x)=\frac{1}{M}\sum_{m=1}^{M}F_{m}(x)$. Then for
any $x,y\in\mathbb{R}^{d}$ we have the following inequality:

$\displaystyle\left\lVert\nabla F_{m}(x)-\nabla F(x)+\nabla F(y)-\nabla
F_{m}(y)\right\rVert_{2}^{2}\leq\tau^{2}\left\lVert
x-y\right\rVert_{2}^{2}\,.$ (32)

###### Proof.

We define the function $\Psi(z)=F_{m}(z)-F(z)$ so
$\nabla^{2}\Psi(z)=\nabla^{2}F_{m}(z)-\nabla^{2}F(z)$. By Assumption 3 we know
that $\forall
z\in\mathbb{R}^{d},\left\lVert\nabla^{2}\Psi(z)\right\rVert_{2}\leq\tau$ which
means $\Psi(z)$ is $\tau$-smooth. From the smoothness property we know:

$\displaystyle\left\lVert\nabla\Psi(x)-\nabla\Psi(y)\right\rVert_{2}$
$\displaystyle\leq\tau\left\lVert x-y\right\rVert_{2}\,.$

By replacing the definition of $\Psi$ we get:

$\displaystyle\left\lVert\nabla F_{m}(x)-\nabla F(x)-\nabla F_{m}(y)+\nabla
F(y)\right\rVert_{2}\leq\tau\left\lVert x-y\right\rVert_{2}\,.$

∎

######  Lemma 10 (Kovalev et al. 2019, Definition 2).

Let function $F$ satisfy Assumption 4, then for any $x,y\in\mathbb{R}^{d}$, we
have the following inequality:

$\displaystyle\left\lVert\nabla F(x)-\nabla
F(y)-\nabla^{2}F(y)(x-y)\right\rVert_{2}\leq\frac{Q}{2}\left\lVert
x-y\right\rVert_{2}^{2}\,.$ (33)

######  Lemma 11.

Let Assumptions 3 and 2 hold. We can upper bound the consensus error
$\varXi_{t}$ using the lemma from Woodworth et al. [2020b]. With a fixed
learning rate of $\eta_{t}=\eta$ we have:

$\displaystyle\varXi_{t}:=\frac{1}{M}\sum_{m=1}^{M}\left\lVert
x^{m}_{t}-\bar{x}_{t}\right\rVert_{2}^{2}\leq
3K\sigma^{2}\eta^{2}+6K^{2}\eta^{2}\zeta^{2}\,,$ (34)

where $x^{m}_{t}$ is the parameters of client $m$ at time step $t$ and
$\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$.

######  Lemma 12 (Stepsize Tuning).

Our upper bound has the following recursive form:

$\displaystyle
r_{t+1}\leq(1-A\eta_{t})r_{t}-\eta_{t}e_{t}+C\eta_{t}^{2}+E\eta_{t}^{3}+G\eta_{t}^{5}\,,$
(35)

where $\\{r_{t}\\}_{t\geq 0}$ and $\\{e_{t}\\}_{t\geq 0}$ are two non-negative
sequences and $\eta_{t}\leq\frac{1}{D}$ for a $D>0$. With the following choice
of parameters we recover our recursive upper bound used in the proof of
Theorem 5 (see below):

$\displaystyle
r_{t}=\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2},\quad
e_{t}=\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]},\quad
C=\frac{\sigma^{2}}{M},\quad D=2H,\quad A=\frac{\mu}{2}\,,$ $\displaystyle
E=\frac{24K\tau^{2}\sigma^{2}}{\mu}+\frac{48K^{2}\tau^{2}\zeta^{2}}{\mu}\,,\quad
G=\frac{36K^{2}Q^{2}\sigma^{4}}{\mu}+\frac{144Q^{2}K^{4}\zeta^{4}}{\mu}\,.$

The recursion (35) can be solved as follows:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}+Ar_{T+1}$
$\displaystyle\leq
Dr_{0}\exp{\left(\frac{-AT}{D}\right)}+\tilde{\mathcal{O}}\left(\frac{C}{AT}\right)+\tilde{\mathcal{O}}\left(\frac{E}{A^{2}T^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{G}{A^{4}T^{4}}\right)\,,$

where we define the coefficient $w_{t}=(1-A\eta)^{-(t+1)}$ and
$W_{T}=\sum_{t=0}^{T}w_{t}$.

###### Proof.

The proof is similar to the works [Stich, 2019, Koloskova et al., 2020]. We
divide both sides of the recursive inequality by $\eta_{t}$ and rearrange the
terms:

$\displaystyle e_{t}$
$\displaystyle\leq\frac{(1-A\eta_{t})}{\eta_{t}}r_{t}-\frac{1}{\eta_{t}}r_{t+1}+C\eta_{t}+E\eta_{t}^{2}+G\eta_{t}^{4}$

Note that learning rate is fixed $\eta_{t}=\eta$. Then we multiply both sides
of the inequality by $w_{t}$ and sum over $t$ which gives us:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}$
$\displaystyle\leq\frac{1}{W_{T}}\sum_{t=0}^{T}\left[\frac{(1-A\eta)^{-(t+1)}(1-A\eta)}{\eta}r_{t}-\frac{(1-A\eta)^{-(t+1)}}{\eta}r_{t+1}\right]+C\eta+E\eta^{2}+G\eta^{4}$
$\displaystyle=\frac{1}{W_{T}}\sum_{t=0}^{T}\left[\frac{(1-A\eta)^{-t}}{\eta}r_{t}-\frac{(1-A\eta)^{-(t+1)}}{\eta}r_{t+1}\right]+C\eta+E\eta^{2}+G\eta^{4}$
$\displaystyle=\frac{1}{W_{T}}\sum_{t=0}^{T}\left[\frac{w_{t-1}}{\eta}r_{t}-\frac{w_{t}}{\eta}r_{t+1}\right]+C\eta+E\eta^{2}+G\eta^{4}$
$\displaystyle=\left[\frac{r_{0}}{\eta W_{T}}-\frac{w_{T}}{\eta
W_{T}}r_{T+1}\right]+C\eta+E\eta^{2}+G\eta^{4}\,.$

So we have:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}+\frac{w_{T}}{\eta
W_{T}}r_{T+1}\leq\frac{r_{0}}{\eta W_{T}}+C\eta+E\eta^{2}+G\eta^{4}\,.$

Also using the fact that $W_{T}\leq\frac{w_{T}}{a\eta}$ and
$W_{T}\geq(1-A\eta)^{-(T+1)}$ we have:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}+ar_{T+1}$
$\displaystyle\leq\frac{(1-A\eta)^{-(T+1)}r_{0}}{\eta}+C\eta+E\eta^{2}+G\eta^{4}$
$\displaystyle\leq\frac{r_{0}\exp{\left(-a\eta(T+1)\right)}}{\eta}+C\eta+E\eta^{2}+G\eta^{4}\,.$

Now we consider two cases:

  * 1)

$\frac{1}{D}\geq\frac{\ln\left(\max\left\\{2,\frac{A^{2}T^{2}r_{0}}{C}\right\\}\right)}{AT}$:
We choose
$\eta=\frac{\ln\left(\max\left\\{2,\frac{A^{2}T^{2}r_{0}}{C}\right\\}\right)}{AT}$.
With this choice we get a rate of:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}+Ar_{T+1}$
$\displaystyle\leq\frac{r_{0}AT}{\ln\left(\max\left\\{2,\frac{A^{2}T^{2}r_{0}}{C}\right\\}\right)}\exp\left(-\ln\left(\max\left\\{2,\frac{A^{2}T^{2}r_{0}}{C}\right\\}\right)\right)+\tilde{\mathcal{O}}\left(\frac{C}{AT}\right)$
$\displaystyle\quad+\tilde{\mathcal{O}}\left(\frac{E}{A^{2}T^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{G}{A^{4}T^{4}}\right)$
$\displaystyle\leq\tilde{\mathcal{O}}\left(\frac{r_{0}A}{T^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{C}{AT}\right)+\tilde{\mathcal{O}}\left(\frac{E}{A^{2}T^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{G}{A^{4}T^{4}}\right)\,.$

  * 2)

$\frac{1}{D}\leq\frac{\ln\left(\max\left\\{2,\frac{A^{2}T^{2}r_{0}}{C}\right\\}\right)}{AT}$:
We choose $\eta=\frac{1}{D}$. With this choice we get a rate of:

$\displaystyle\frac{1}{W_{T}}\sum_{t=0}^{T}w_{t}e_{t}+Ar_{T+1}$
$\displaystyle\leq
Dr_{0}\exp{\left(\frac{-AT}{D}\right)}+\frac{C}{D}+\frac{E}{D^{2}}+\frac{G}{D^{4}}$
$\displaystyle\leq
Dr_{0}\exp{\left(\frac{-AT}{D}\right)}+\tilde{\mathcal{O}}\left(\frac{C}{AT}\right)+\tilde{\mathcal{O}}\left(\frac{E}{A^{2}T^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{G}{A^{4}T^{4}}\right)\,.$

∎

###  D.4 Proof of Theorem 5

###### Proof.

The proof follows a similar approach to Yuan and Ma [2020] while we assume
that we have heterogeneity. In the following proof, we use the same notation
as the work Woodworth et al. [2020b]. We drop the subscript $r$ for simplicity
and use $t$ instead which is in the range $[0,KR-1]$. We use the notation
$x^{m}_{t}$ as the parameters of client $m$ at time step $t$ and $g^{m}_{t}$
as the stochastic gradient on client $m$ at time step $t$. Also because
$\beta=1$, the update rule
$x_{r+1}=x_{r}+\frac{\beta}{M}\sum_{m}(x^{m}_{r,K}-x_{r})$ reduces to
$x_{r+1}=\frac{1}{M}\sum_{m}x^{m}_{r,K}$. We also define
$\bar{x}_{t}=\frac{1}{M}\sum_{m=1}^{M}x^{m}_{t}$ as the average of parameters
over all clients at time step $t$. Starting with the distance from the optimal
point and taking the conditional expectation on the previous iterate
$x^{m}_{t},\forall m\in[M]$ we have:

$\displaystyle\mathbb{E}_{t}\left\lVert\bar{x}_{t+1}-x^{\star}\right\rVert_{2}^{2}$
$\displaystyle=\mathbb{E}_{t}\left\lVert\bar{x}_{t}-x^{\star}-\frac{\eta_{t}}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})+\frac{\eta_{t}}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})-\frac{\eta_{t}}{M}\sum_{m=1}^{M}g^{m}_{t}\right\rVert_{2}^{2}$
$\displaystyle\overset{(\text{Lemma \ref{lemma: noise of gradient
differences}})}{\leq}\left\lVert\bar{x}_{t}-x^{\star}-\frac{\eta_{t}}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})\right\rVert_{2}^{2}+\frac{\eta_{t}^{2}\sigma^{2}}{M}$
$\displaystyle=\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})+\eta_{t}\nabla
F(\bar{x}_{t})-\frac{\eta_{t}}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})\right\rVert_{2}^{2}+\frac{\eta_{t}^{2}\sigma^{2}}{M}$
$\displaystyle\overset{(\text{Lemma \ref{Lemma: generalized triangle
inequality}})}{\leq}\left(1+\frac{\eta_{t}\mu}{2}\right)\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}+\eta_{t}^{2}\left(1+\frac{2}{\eta_{t}\mu}\right)\left\lVert\nabla
F(\bar{x}_{t})-\frac{1}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})\right\rVert_{2}^{2}+\frac{\eta_{t}^{2}\sigma^{2}}{M}\,.$ (36)

For the first term in (36) we have:

$\displaystyle\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}=\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}+\eta_{t}^{2}\left\lVert\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}-2\eta_{t}\Bigr{\langle}\bar{x}_{t}-x^{\star},\nabla
F(\bar{x}_{t})\Bigr{\rangle}\,.$

For the second term in the above equation we have:

$\displaystyle\eta_{t}^{2}\left\lVert\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle=\eta_{t}^{2}\left\lVert\nabla F(\bar{x}_{t})-\nabla
F(x^{\star})\right\rVert_{2}^{2}$ $\displaystyle\overset{(\text{Lemma
\ref{lemma: co-coercivity of
gradients}})}{\leq}2H\eta_{t}^{2}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}\,.$

For the third term in the equality we have:

$\displaystyle-2\eta_{t}\Bigr{\langle}\bar{x}_{t}-x^{\star},\nabla
F(\bar{x}_{t})\Bigr{\rangle}\leq-2\eta_{t}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}-\eta_{t}\mu\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}$

Now by putting everything together we have:

$\displaystyle\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}+\eta_{t}^{2}\left\lVert\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}-2\eta_{t}\Bigr{\langle}\bar{x}_{t}-x^{\star},\nabla
F(\bar{x}_{t})\Bigr{\rangle}$
$\displaystyle\leq\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}+2H\eta_{t}^{2}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}-2\eta_{t}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}-\eta_{t}\mu\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}\,.$

With the choice of $\eta_{t}\leq\frac{1}{2H}$ we have:

$\displaystyle\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}\leq(1-\eta_{t}\mu)\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\eta_{t}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}\,.$

Then we multiply both sides by the coefficient $(1+\frac{\eta_{t}\mu}{2})$ and
we have:

$\displaystyle\left(1+\frac{\eta_{t}\mu}{2}\right)\left\lVert\bar{x}_{t}-x^{\star}-\eta_{t}\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle\leq\left(1+\frac{\eta_{t}\mu}{2}\right)(1-\eta_{t}\mu)\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\eta_{t}\left(1+\frac{\eta_{t}\mu}{2}\right)\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}$
$\displaystyle\leq\left(1-\frac{\eta_{t}\mu}{2}\right)\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\eta_{t}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}$

For the second term in (36) we have:

$\displaystyle\eta_{t}^{2}\left(1+\frac{2}{\eta_{t}\mu}\right)\left\lVert\frac{1}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})-\nabla F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{4\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\nabla
F_{m}(x^{m}_{t})-\nabla F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle=\frac{4\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\Bigr{(}\nabla
F_{m}(x^{m}_{t})-\nabla F(x^{m}_{t})+\nabla F(\bar{x}_{t})-\nabla
F_{m}(\bar{x}_{t})\Bigr{)}+\frac{1}{M}\sum_{m=1}^{M}\nabla F(x^{m}_{t})-\nabla
F(\bar{x}_{t})\right\rVert_{2}^{2}$ $\displaystyle\overset{(\text{Lemma
\ref{Lemma: jensen's inequality},\ref{Lemma: triangle
inequality}})}{\leq}\frac{8\eta_{t}}{\mu M}\sum_{m=1}^{M}\left\lVert\nabla
F_{m}(x^{m}_{t})-\nabla F(x^{m}_{t})+\nabla F(\bar{x}_{t})-\nabla
F_{m}(\bar{x}_{t})\right\rVert_{2}^{2}+\frac{8\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\nabla
F(x^{m}_{t})-\nabla F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle\overset{(\text{Lemma \ref{lemma: mime's
inequality}})}{\leq}\frac{8\eta_{t}}{\mu}\tau^{2}\varXi_{t}+\frac{8\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\nabla
F(x^{m}_{t})-\nabla F(\bar{x}_{t})\right\rVert_{2}^{2}\,.$

For the second term in the above inequality we have:

$\displaystyle\frac{8\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\nabla
F(x^{m}_{t})-\nabla F(\bar{x}_{t})\right\rVert_{2}^{2}$
$\displaystyle=\frac{8\eta_{t}}{\mu}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\Bigr{(}\nabla
F(x^{m}_{t})-\nabla
F(\bar{x}_{t})-\nabla^{2}F(\bar{x}_{t})^{\top}(x^{m}_{t}-\bar{x}_{t})\Bigr{)}+\underbrace{\frac{1}{M}\sum_{m=1}^{M}\nabla^{2}F(\bar{x}_{t})^{\top}(x^{m}_{t}-\bar{x}_{t})}_{=0}\right\rVert_{2}^{2}$
$\displaystyle=\frac{8\eta_{t}}{\mu}\Biggr{(}\left\lVert\frac{1}{M}\sum_{m=1}^{M}\Bigr{(}\nabla
F(x^{m}_{t})-\nabla
F(\bar{x}_{t})-\nabla^{2}F(\bar{x}_{t})^{\top}(x^{m}_{t}-\bar{x}_{t})\Bigr{)}\right\rVert_{2}\Biggr{)}^{2}$
$\displaystyle\overset{(\text{Lemma \ref{Lemma: base triangle
inequality}})}{\leq}\frac{8\eta_{t}}{\mu
M^{2}}\Biggr{(}\sum_{m=1}^{M}\left\lVert\nabla F(x^{m}_{t})-\nabla
F(\bar{x}_{t})-\nabla^{2}F(\bar{x}_{t})^{\top}(x^{m}_{t}-\bar{x}_{t})\right\rVert_{2}\Biggr{)}^{2}$
$\displaystyle\overset{(\text{Lemma \ref{lemma: quadratic function
approximation inequality}})}{\leq}\frac{8\eta_{t}}{\mu
M^{2}}\Biggr{(}\sum_{m=1}^{M}\frac{Q}{2}\left\lVert
x^{m}_{t}-\bar{x}_{t}\right\rVert_{2}^{2}\Biggr{)}^{2}$
$\displaystyle=\frac{2Q^{2}\eta_{t}}{\mu}\Biggr{(}\frac{1}{M}\sum_{m=1}^{M}\left\lVert
x^{m}_{t}-\bar{x}_{t}\right\rVert_{2}^{2}\Biggr{)}^{2}$
$\displaystyle\leq\frac{2Q^{2}\eta_{t}}{\mu}\varXi_{t}^{2}\,.$

Now by plugging everything back into (36) we have:

$\displaystyle\mathbb{E}_{t}\left\lVert\bar{x}_{t+1}-x^{\star}\right\rVert_{2}^{2}\leq\left(1-\frac{\eta_{t}\mu}{2}\right)\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\eta_{t}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}+\frac{8\tau^{2}\eta_{t}}{\mu}\varXi_{t}+\frac{2Q^{2}\eta_{t}}{\mu}\varXi_{t}^{2}+\frac{\eta_{t}^{2}\sigma^{2}}{M}\,.$

Then we divide both sides by $\eta_{t}=\eta$, rearrange the terms and take the
unconditional expectation, and we have:

$\displaystyle\mathbb{E}\Bigr{[}F(\bar{x}_{t})-F(x^{\star})\Bigr{]}$
$\displaystyle\leq\left(\frac{1}{\eta}_{t}-\frac{\mu}{2}\right)\mathbb{E}\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\frac{1}{\eta}_{t}\mathbb{E}\left\lVert\bar{x}_{t+1}-x^{\star}\right\rVert_{2}^{2}+\frac{8\tau^{2}}{\mu}\varXi_{t}+\frac{2Q^{2}}{\mu}\varXi_{t}^{2}+\frac{\eta\sigma^{2}}{M}$
$\displaystyle\overset{(\text{Lemma \ref{lemma: weight variance upper
bound}})}{\leq}\left(\frac{1}{\eta}-\frac{\mu}{2}\right)\mathbb{E}\left\lVert\bar{x}_{t}-x^{\star}\right\rVert_{2}^{2}-\frac{1}{\eta}\mathbb{E}\left\lVert\bar{x}_{t+1}-x^{\star}\right\rVert_{2}^{2}+\frac{\eta\sigma^{2}}{M}+$
$\displaystyle\hskip
99.58464pt\frac{24K\tau^{2}\sigma^{2}\eta^{2}}{\mu}+\frac{48K^{2}\tau^{2}\zeta^{2}\eta^{2}}{\mu}+\frac{36K^{2}Q^{2}\sigma^{4}\eta^{4}}{\mu}+\frac{144Q^{2}K^{4}\zeta^{4}\eta^{4}}{\mu}\,.$

After tuning the stepsize using the Lemma 12 with the weights
$w_{t}=(1-\frac{\mu\eta}{2})^{-(t+1)}$ and $W_{T}=\sum_{t=0}^{KR-1}w_{t}$ and
by summing over $t=0,..,KR-1$ we have:

$\displaystyle\mathbb{E}\left[F\left(\frac{1}{W_{T}}\sum_{t=0}^{KR-1}w_{t}\bar{x}_{t}\right)-F(x^{\star})\right]+\frac{\mu}{2}\left\lVert\bar{x}_{T+1}-x^{\star}\right\rVert_{2}^{2}$
$\displaystyle\leq 2HB^{2}\exp\left(-\frac{\mu
T}{4H}\right)+\tilde{\mathcal{O}}\left(\frac{\sigma^{2}}{\mu
MKR}\right)+\tilde{\mathcal{O}}\left(\frac{\tau^{2}\sigma^{2}}{\mu^{3}KR^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{\tau^{2}\zeta^{2}}{\mu^{3}R^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}\right)+\tilde{\mathcal{O}}\left(\frac{Q^{2}\zeta^{4}}{\mu^{5}R^{4}}\right)\,.$

It is worth mentioning that the notation $\tilde{\mathcal{O}}(.)$ means the
bound holds up to some logarithmic factors appearing in the nominator for the
last five terms. The logarithmic factor is in the form of
$\ln\left(\max\left\\{2,T^{2}\right\\}\right)$ (some absolute constants are
ignored). In the literature, it is also common to ignore these factors [Yuan
and Ma, 2020, Koloskova et al., 2020]. ∎

###  D.5 Proof of Corollary 3

We use the regularization technique to derive the convergence rate for the
convex case from the strongly-convex result. This technique is standard in the
literature, see e.g. [Hazan et al., 2016]. For the sake of completeness, we
repeat the argument here.

Let $F(x)$ be a convex function. We construct a regularized version of this
function $F_{\mu}(x)$ as:

$\displaystyle F_{\mu}(x)=F(x)+\frac{\mu}{2}\left\lVert
x-x_{0}\right\rVert_{2}^{2}\,.$

Next we define:

$\displaystyle x^{\star}_{\mu}$ $\displaystyle=\underset{x}{\arg\min}\hskip
2.84526ptF_{\mu}(x)\,,$ $\displaystyle x^{\star}$
$\displaystyle=\underset{x}{\arg\min}\hskip 2.84526ptF(x)\,.$

We have that $F_{\mu}(x^{\star}_{\mu})\leq F_{\mu}(x^{\star})$. Then we upper
bound the function sub-optimality for the convex function $F(x)$:

$\displaystyle F(\bar{x}_{t})-F(x^{\star})$ $\displaystyle\leq
F_{\mu}(\bar{x}_{t})-\frac{\mu}{2}\left\lVert\bar{x}_{t}-x_{0}\right\rVert_{2}^{2}-F_{\mu}(x^{\star})+\frac{\mu}{2}\left\lVert
x^{\star}-x_{0}\right\rVert_{2}^{2}$ $\displaystyle\leq
F_{\mu}(\bar{x}_{t})-F_{\mu}(x^{\star})+\frac{\mu}{2}\left\lVert
x^{\star}-x_{0}\right\rVert_{2}^{2}$ $\displaystyle\leq
F_{\mu}(\bar{x}_{t})-F_{\mu}(x^{\star}_{\mu})+\frac{\mu}{2}\left\lVert
x^{\star}-x_{0}\right\rVert_{2}^{2}$ $\displaystyle\leq
F_{\mu}(\bar{x}_{t})-F_{\mu}(x^{\star}_{\mu})+\frac{\mu}{2}B^{2}\,.$

The last step is to tune the $\mu$. We assume that we want to achieve
$\epsilon$-accuracy when running local SGD on the convex function $F$ so we
have:

$\displaystyle F(\bar{x}_{t})-F(x^{\star})$
$\displaystyle\leq\left(F_{\mu}(\bar{x}_{t})-F_{\mu}(x^{\star}_{\mu})\right)+\frac{\mu}{2}B^{2}\leq\epsilon\,.$

To satisfy this condition, it is enough to ensure that both terms in the rate
are less than $\frac{\epsilon}{2}$. We solve this for the regularization term
and we get:

$\displaystyle\frac{\mu}{2}B^{2}\leq\frac{\epsilon}{2}\,,$

which results in:

$\displaystyle\mu\leq\frac{\epsilon}{B^{2}}\,.$

Now we proceed by replacing $\mu$ in all terms and deriving the rate.

###### Proof.

By assuming $\mu=\frac{\epsilon}{B^{2}}$, we will find the condition on $K$
and $R$ to reach $\epsilon$-accuracy using Theorem 5. For simplicity, we drop
all constant numbers which do not affect the rate. To recall, in the strongly
convex case we had proven a rate of:

$\displaystyle HB^{2}\exp\left(-\frac{\mu
KR}{H}\right)+\tilde{\mathcal{O}}\left(\frac{\sigma^{2}}{\mu
MKR}\right)+\tilde{\mathcal{O}}\left(\frac{\tau^{2}\sigma^{2}}{\mu^{3}KR^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{\tau^{2}\zeta^{2}}{\mu^{3}R^{2}}\right)+\tilde{\mathcal{O}}\left(\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}\right)+\tilde{\mathcal{O}}\left(\frac{Q^{2}\zeta^{4}}{\mu^{5}R^{4}}\right)\,.$

For the first term we solve the inequality:

$\displaystyle HB^{2}\exp\left(-\frac{\epsilon
KR}{HB^{2}}\right)\leq\epsilon\quad\Longrightarrow\quad
KR\geq\frac{HB^{2}}{\epsilon}\ln\left(\frac{\epsilon}{HB^{2}}\right)=\tilde{\mathcal{O}}\left(\frac{HB^{2}}{\epsilon}\right)\,.$

For the second term we solve the inequality:

$\displaystyle\frac{\sigma^{2}B^{2}}{\epsilon
MKR}\leq\epsilon\quad\Longrightarrow\quad
KR\geq\frac{\sigma^{2}B^{2}}{M\epsilon^{2}}\,.$

For the third term we solve the inequality:

$\displaystyle\frac{\tau^{2}\sigma^{2}B^{6}}{\epsilon^{3}KR^{2}}\leq\epsilon\quad\Longrightarrow\quad
KR^{2}\geq\frac{\tau^{2}\sigma^{2}B^{6}}{\epsilon^{4}}\,.$

For the fourth term we solve the inequality:

$\displaystyle\frac{\tau^{2}\zeta^{2}B^{6}}{\epsilon^{3}R^{2}}\leq\epsilon\quad\Longrightarrow\quad
R^{2}\geq\frac{\tau^{2}\zeta^{2}B^{6}}{\epsilon^{4}}\,.$

For the fifth term we solve the inequality:

$\displaystyle\frac{Q^{2}\sigma^{4}}{\mu^{5}K^{2}R^{4}}\leq\epsilon\quad\Longrightarrow\quad
K^{2}R^{4}\geq\frac{Q^{2}\sigma^{4}B^{10}}{\epsilon^{6}}\,.$

And for the last term:

$\displaystyle\frac{Q^{2}\zeta^{4}B^{10}}{\epsilon^{5}R^{4}}\leq\epsilon\quad\Longrightarrow\quad
R^{4}\geq\frac{Q^{2}\zeta^{4}B^{10}}{\epsilon^{6}}\,.$

Finally, the rate would be the maximum of above terms which we can write:

$\displaystyle\tilde{\mathcal{O}}\left(\max\left\\{\frac{HB^{2}}{\epsilon},\frac{\sigma^{2}B^{2}}{M\epsilon^{2}},\frac{\tau^{2}\sigma^{2}B^{6}}{\epsilon^{4}},\frac{\tau^{2}\zeta^{2}B^{6}}{\epsilon^{4}},\frac{Q^{2}\sigma^{4}B^{10}}{\epsilon^{6}},\frac{Q^{2}\zeta^{4}B^{10}}{\epsilon^{6}}\right\\}\right)\leq$
$\displaystyle\tilde{\mathcal{O}}\left(\frac{HB^{2}}{\epsilon}+\frac{\sigma^{2}B^{2}}{M\epsilon^{2}}+\frac{\tau^{2}\sigma^{2}B^{6}}{\epsilon^{4}}+\frac{\tau^{2}\zeta^{2}B^{6}}{\epsilon^{4}}+\frac{Q^{2}\sigma^{4}B^{10}}{\epsilon^{6}}+\frac{Q^{2}\zeta^{4}B^{10}}{\epsilon^{6}}\right)\,.$

Or in terms of $K$ and $R$:

$\displaystyle\tilde{\mathcal{O}}\left(\frac{HB^{2}}{KR}+\frac{\sigma
B}{\sqrt{MKR}}+\frac{(\tau\sigma
B^{3})^{1/2}}{K^{1/4}R^{1/2}}+\frac{(\tau\zeta
B^{3})^{1/2}}{R^{1/2}}+\frac{(Q\sigma^{2}B^{5})^{1/3}}{K^{1/3}R^{2/3}}+\frac{(Q\zeta^{2}B^{5})^{1/3}}{R^{2/3}}\right)\,.$

It’s worth mentioning that during the process of deriving rate for convex
regime from strongly convex regime, we also ignore some logarithmic factors
which is why we used the notation $\tilde{\mathcal{O}}(.)$. In fact the term
$\frac{\ln\left(\max\left\\{2,\frac{M\mu^{2}T^{2}B^{2}}{\sigma^{2}}\right\\}\right)}{\mu
T}$ (some constants are dropped for simplicity) that we use for tuning the
stepsize depends on $\mu$. By the choice of $\mu=\frac{\epsilon}{B^{2}}$ this
term becomes
$\frac{B^{2}\ln\left(\max\left\\{2,\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}\right\\}\right)}{\epsilon
T}$ which will be used to upper bound the terms in our rate which are in the
form of $\frac{C}{D}+\frac{E}{D^{2}}+\frac{G}{D^{4}}$ (refer to D.3). We use
the fact that
$\frac{1}{D}\leq\frac{B^{2}\ln\left(\max\left\\{2,\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}\right\\}\right)}{\epsilon
T}$. If $2\geq\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}$, then there is no
extra logarithmic factor appearing in our rate. Only in the case of
$2\leq\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}$ we get an extra factor of
$\ln(T^{2})$. In this case, for the term $\frac{C}{D}$ as an example we have:

$\displaystyle\frac{C}{D}\leq\frac{CB^{2}\ln\left(\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}\right)}{\epsilon
T}$

And to achieve $\epsilon$-accuracy we want this term to be less that
$\epsilon$ so we have:

$\displaystyle\frac{CB^{2}\ln\left(\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}\right)}{\epsilon
T}\leq\epsilon$

So we need to set $T$ in the following way:

$\displaystyle T$
$\displaystyle\geq\frac{CB^{2}\ln\left(\frac{M\epsilon^{2}T^{2}}{B^{2}\sigma^{2}}\right)}{\epsilon^{2}}$
$\displaystyle\geq\frac{CB^{2}\ln\left(\frac{M\epsilon^{2}}{B^{2}\sigma^{2}}\right)}{\epsilon^{2}}=\tilde{\mathcal{O}}(\frac{1}{\epsilon^{2}})$

And for the other terms we do the same.

∎

##  Appendix E Missing Details from Section 5

###  E.1 Proof of Proposition 4

Assuming the local SGD algorithm converges, i.e., the hyper-parameters are set
to achieve that and $R\to\infty$, we would like to calculate its fixed point.
Let’s denote the fixed point by $x_{\infty}$. Then $x_{\infty}$ must satisfy
the following requirements,

$\displaystyle
x_{\infty}=x_{\infty}+\frac{\beta}{M}\sum_{m\in[M]}\Delta^{m}(x_{\infty})\equiv\sum_{m\in[M]}\Delta^{m}(x_{\infty})=0,$

where $\Delta^{m}(x_{\infty})$ is the update on machine $m$ for a
communication round starting at the fixed point $x_{\infty}$. Note that the
above equation does not depend on $\beta$. Also, note that this is very
similar to the average drift assumption of Wang et al. [2022]. Unwinding the
update, we get the following,

$\displaystyle\sum_{m\in[M]}\sum_{k\in[K]}A_{m}(I-\eta
A_{m})^{k-1}(x_{\infty}-x_{m}^{\star})=0,$
$\displaystyle\Leftrightarrow^{\text{if
$\eta=0$}}x_{\infty}=\frac{1}{M}\sum_{m\in[M]}A^{-1}A_{m}x_{m}^{\star}=x^{\star},$
$\displaystyle\Leftrightarrow^{\text{if
$\eta>0$}}x_{\infty}=\frac{1}{M}\sum_{m\in[M]}C^{-1}C_{m}x_{m}^{\star},$

where $C_{m}:=I-(I-\eta C_{m})^{K}$, and $C:=\frac{1}{M}\sum_{m\in[M]}C_{m}$.
Note that $x_{\infty}(\eta,K)$ is a function of $\eta,K$ and is unaffected by
the choice of $\beta$. The above proof also highlights a key limitation of the
assumption 7; they assume that local SGD is going to converge to $x^{\star}$
as opposed to any other fixed point, defining the average drift at the
optimum. This makes their analysis more complicated than it should have been.

###  E.2 Proof of Proposition 5

###### Proof.

We first bound the distance between $x^{\star}$ and $\bar{x}^{\star}$,

We now bound the distance between $x_{\infty}(K>1,\eta)$ and $\bar{x}^{\star}$
similarly,

where to get the second last inequality, we note the following sequence of
inequalities with a clever adding and subtracting of several terms,

$\displaystyle(I-\eta A_{m})^{K}-(I-\eta A_{n})^{K}$ $\displaystyle=(I-\eta
A_{m})^{K}-\sum_{k\in[K]}(I-\eta A_{n})^{k}(I-\eta
A_{m})^{K-k}+\sum_{k\in[K]}(I-\eta A_{n})^{k}(I-\eta A_{m})^{K-k}-(I-\eta
A_{n})^{K}$ $\displaystyle=(I-\eta A_{m})^{K}-\sum_{k\in[K]}(I-\eta
A_{n})^{k}(I-\eta A_{m})^{K-k}+\sum_{k\in[K-1]}(I-\eta A_{n})^{k}(I-\eta
A_{m})^{K-k}$ $\displaystyle\quad+(I-\eta A_{n})^{K}-(I-\eta A_{n})^{K},$
$\displaystyle=(I-\eta A_{m})^{K}+\sum_{k\in[K-1]}(I-\eta A_{n})^{k}(I-\eta
A_{m})^{K-k}-\sum_{k\in[K]}(I-\eta A_{n})^{k}(I-\eta A_{m})^{K-k}$
$\displaystyle=\sum_{k\in[0,K-1]}(I-\eta A_{n})^{k}(I-\eta
A_{m})^{K-k}-\sum_{k\in[K]}(I-\eta A_{n})^{k}(I-\eta A_{m})^{K-k}$
$\displaystyle=\sum_{k\in[K]}(I-\eta A_{n})^{k-1}(I-\eta
A_{m})^{K-k+1}-\sum_{k\in[K]}(I-\eta A_{n})^{k}(I-\eta A_{m})^{K-k}$
$\displaystyle=\sum_{k\in[K]}\left[(I-\eta A_{n})^{k-1}(I-\eta
A_{m})^{K-k+1}-(I-\eta A_{n})^{k}(I-\eta A_{m})^{K-k}\right]$
$\displaystyle=\sum_{k\in[K]}\left[\eta(I-\eta
A_{n})^{k-1}(A_{n}-A_{m})(I-\eta A_{m})^{K-k}\right],$

which upon taking the norm implies,

$\displaystyle\left\lVert(I-\eta A_{m})^{K}-(I-\eta
A_{n})^{K}\right\rVert_{2}$ $\displaystyle\leq\sum_{k\in[K]}\eta\left\lVert
I-\eta A_{n}\right\rVert_{2}^{k-1}\left\lVert A-n-
A_{m}\right\rVert_{2}\left\lVert I-\eta A_{m}\right\rVert_{2}^{K-k},$
$\displaystyle\leq\eta\sum_{k\in[K]}(1-\eta\mu)^{k-1}\tau(1-\eta\mu)^{K-k},$
$\displaystyle\leq\eta\tau K(1-\eta\mu)^{K-1},$

which finishes the proof of the inequality and hence the proof as well. ∎

###  E.3 Proof of Theorem 4

Having identified the convergence point of local SGD in the previous section
as $x_{\infty}(\eta,K)$, in this section, we will characterize the rate of
convergence to this point.

###### Proof.

We first write the inner loop iterated on machine $m$ as follows,

Subtracting $x_{r-1}$ from both sides,

With this in hand, we can write the update across communication rounds as
follows,

Subtracting the fixed point $\hat{x}$ on both sides, we get,

Unrolling this recursion for $R$ communication rounds,

$\displaystyle x_{R}-x_{\infty}={I-\beta B}^{R}{x_{0}-x_{\infty}}$

Noting the initialization $x_{0}=0$ we get,

In particular, we can bound the distance between $x_{R}$ and $x_{\infty}$ as
follows,

If we ensure that $\beta<1/\left\lVert C\right\rVert_{2}$, then the distance
contracts with more communication rounds. Note that,

This implies that we will have contraction with communication if
$\beta<\frac{1}{1-(1-\eta H)^{K}}$. In this regime, we can calculate the
overall convergence as follows,

We can note that when $\beta=1$ this simplifies to,

$\displaystyle\left\lVert x_{R}-x_{\infty}\right\rVert_{2}$
$\displaystyle\leq{1-\eta\mu}^{KR}\cdot\frac{1-{1-\eta
L}^{K}}{1-{1-\eta\mu}^{K}}B\enspace$

When $\beta=\frac{1}{c}\cdot\frac{1}{1-(1-\eta L)^{K}}$ for some $c>1$ this
reduces to,

where we define,

$\kappa^{\prime}:=\frac{1-{1-\eta L}^{K}}{1-{1-\eta\mu}^{K}}.$

This finishes the convergence proof for local GD. To finish the proof of the
theorem, we combine this result with the fixed point discrepancy implied by
Proposition 5. ∎