# On the Complexity of Finite-Sum Smooth Optimization
under the Polyak–Łojasiewicz Condition

Yunyan Bai Yuxing Liu Luo Luo
School of Data Science, Fudan University

###### Abstract

This paper considers the optimization problem of the form $\min_{{\bf
x}\in{\mathbb{R}}^{d}}f({\bf x})\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf
x})$, where $f(\cdot)$ satisfies the Polyak–Łojasiewicz (PL) condition with
parameter $\mu$ and $\\{f_{i}(\cdot)\\}_{i=1}^{n}$ is $L$-mean-squared smooth.
We show that any gradient method requires at least
$\Omega(n+\kappa\sqrt{n}\log(1/\epsilon))$ incremental first-order oracle
(IFO) calls to find an $\epsilon$-suboptimal solution, where $\kappa\triangleq
L/\mu$ is the condition number of the problem. This result nearly matches
upper bounds of IFO complexity for best-known first-order methods. We also
study the problem of minimizing the PL function in the distributed setting
such that the individuals $f_{1}(\cdot),\dots,f_{n}(\cdot)$ are located on a
connected network of $n$ agents. We provide lower bounds of
$\Omega(\kappa/\sqrt{\gamma}\,\log(1/\epsilon))$,
$\Omega((\kappa+\tau\kappa/\sqrt{\gamma}\,)\log(1/\epsilon))$ and
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ for communication
rounds, time cost and local first-order oracle calls respectively, where
$\gamma\in(0,1]$ is the spectral gap of the mixing matrix associated with the
network and $\tau>0$ is the time cost of per communication round. Furthermore,
we propose a decentralized first-order method that nearly matches above lower
bounds in expectation.

##  1 Introduction

We study the optimization problem of the form

$\displaystyle\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})\triangleq\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}}),$
(1)

where $\\{f_{i}(\cdot)\\}_{i=1}^{n}$ is $L$-mean-squared smooth but each
$f_{i}(\cdot)$ is possibly nonconvex. The complexity of finding stationary
points in Problem (1) has been widely studied in recent years [4, 48, 65, 17,
32]. However, finding the global solution is intractable for the general
nonconvex smooth optimization [41, 49]. This paper focuses on the minimization
Problem (1) under the Polyak–Łojasiewicz condition (PL) [45, 34], i.e., the
objective function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ satisfies

$\displaystyle
f({\bf{x}})-\inf_{{\bf{y}}\in{\mathbb{R}}^{d}}f({\bf{y}})\leq\frac{1}{2\mu}\left\|\nabla
f({\bf{x}})\right\|^{2}$

for any ${\bf{x}}\in{\mathbb{R}}^{d}$, where $\mu>0$ is a constant. This
inequality suggests the function value gap $f({\bf{x}})-f^{*}$ is dominated by
the square of gradient norm, which leads to the gradient descent (GD) method
linearly converge to the global minimum without the convexity [25]. The PL
condition covers a lot of popular applications, such as deep neural networks
[33, 5, 62], reinforcement learning [20, 2, 38, 60], optimal control [12, 18]
and matrix recovery [21, 31, 9].

We typically solve the finite-sum optimization Problem (1) by incremental
first-order oracle (IFO) methods [1], which can access the pair
$\\{f_{i}({\bf{x}}),\nabla f_{i}({\bf{x}})\\}$ for given
${\bf{x}}\in{\mathbb{R}}^{d}$ and $i\in[n]$. This class of methods can
leverage the structure of the objective [24, 15, 51, 64] to iterate with one
or mini-batch individual gradient, which is more efficient than the iteration
with the full-batch gradient. IFO methods have received a lot of attention in
recent years. For example, the stochastic variance reduced gradient (SVRG)
methods with negative momentum [46, 3, 26, 56, 1] achieve the (near) optimal
IFO complexity for convex optimization; the stochastic recursive gradient
methods [43, 17, 32, 44, 55, 65, 14] achieve the optimal IFO complexity for
finding approximate stationary points in general nonconvex optimization. For
the PL condition, Reddi et al. [48], Lei et al. [28] proposed SVRG-type
methods that find the $\epsilon$-suboptimal solution within at most
${\mathcal{O}}((n+n^{2/3}\kappa)\log(1/\epsilon))$ IFO calls, where
$\kappa\triangleq L/\mu$ is the condition number. Later, Zhou et al. [66],
Wang et al. [55], Li et al. [32] improved the upper bound to
${\mathcal{O}}((n+\kappa\sqrt{n})\log(1/\epsilon))$ by stochastic recursive
gradient estimator. Recently, Yue et al. [61] established a tight lower
complexity bound of the full-batch gradient methods for minimizing the PL
function. However, the optimality of existing IFO methods for the finite-sum
setting is still an open problem.

For large-scale optimization problems, we are interested in designing the
distributed algorithms. Specifically, we allocate individuals
$f_{1}(\cdot),\dots,f_{n}(\cdot)$ on $n$ different agents and desire the
agents solve the problem collaboratively. We focus on the decentralized
setting that agents are linked by a connected network, so that each agent can
only access its own local first-order oracle (LFO) and exchange messages with
its neighbours. Besides the LFO complexity, we also require considering the
communication complexity and the time complexity. It is worth noting that the
time complexity in distributed optimization does not directly corresponds to
the weighted sum of the LFO complexity and the communication complexity, since
some agents may skip the computation of local gradient during the iterations
[37, 39]. Most of work for decentralized optimization focus on the convex case
[52, 40, 47, 50, 27, 53, 58, 22, 30] or the general nonconvex case [36, 29,
57, 54, 35, 63]. Recently, Yuan et al. [59] studied the tightness of
complexity for decentralized optimization under the PL condition in online
setting, but the optimality of their result does not include the dependence on
condition number.

In this paper, we provide the nearly tight lower bounds for the finite-sum
optimization problem under the PL condition. We summarize our contributions as
follows:

  * •

We provide the lower bound of $\Omega(n+\kappa\sqrt{n}\log(1/\epsilon))$ for
IFO complexity, which nearly match the upper complexity bound of
${\mathcal{O}}((n+\kappa\sqrt{n})\log(1/\epsilon))$ [66, 55, 32].

  * •

We provide the lower bounds of
$\Omega(\kappa/\sqrt{\gamma}\,\log(1/\epsilon))$,
$\Omega((\kappa+\tau\kappa/\sqrt{\gamma}\,)\log(1/\epsilon))$ and
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ for communication
complexity, time complexity and LFO complexity for decentralized setting,
where $\gamma$ is the spectral gap of the mixing matrix for the network and
$\tau$ is the time cost of per communication round.

  * •

We propose a decentralized first-order algorithm within communication
complexity of $\tilde{\mathcal{O}}(\kappa/\sqrt{\gamma}\,\log(1/\epsilon))$,
time complexity of
$\tilde{\mathcal{O}}((\kappa+\tau\kappa/\sqrt{\gamma}\,)\log(1/\epsilon))$ and
the LFO complexity of
${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$ in
expectation, nearly matching the lower bounds.

We compare our results with related work in Table 1-2.

##  2 Preliminaries

In this section, we formalize the problem setting and the complexity of the
finite-sum optimization.

###  2.1 Notation and Assumptions

Given vector ${\bf{x}}\in{\mathbb{R}}^{d}$, we denote $x_{i}$ as the $i$-th
entry of ${\bf{x}}$ for $i\in[d]$ and denote ${\rm supp}({\bf{x}})$ as the
index set for nonzero entries of ${\bf{x}}$. Given matrix ${\bf
A}\in{\mathbb{R}}^{m\times n}$, we denote $a_{i,j}$ as the $(i,j)$-th entry of
${\bf A}$ for $i\in[m]$ and $j\in[n]$. We let ${\bf{1}}$ be the vectors (or
matrices) of all ones and ${\bf{0}}$ be the vector (or matrix) of all zeros.
Additionally, we let ${\bf I}$ be the identity matrix and denote its $i$-th
column as ${\bf{e}}_{i}$. We use $\|\cdot\|$ to present the Euclidean norm of
a vector or the Frobenius norm of a matrix.

Table 1: We present the IFO complexity for finding an $\epsilon$-suboptimal solution of Problem (1) on single machine. Algorithm | IFO | Reference
---|---|---
GD | ${\mathcal{O}}\big{(}\kappa n\log(1/\epsilon)\big{)}$ | Karimi et al. [25]
SVRG / SCSG | ${\mathcal{O}}\big{(}(n+\kappa n^{2/3}\,)\log(1/\epsilon)\big{)}$ | Reddi et al. [48], Lei et al. [28]
SPIDER / PAGE | ${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$ | Zhou et al. [66], Wang et al. [55], Li et al. [32]
Lower Bound | $\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ | Corollary 3.6

We consider the following assumptions for the finite-sum optimization Problem
(1).

######  Assumption 2.1.

We suppose the objective function $f(\cdot)$ is lower bounded, i.e, we have

$\displaystyle f^{*}=\inf_{{\bf{y}}\in{\mathbb{R}}^{d}}f({\bf{y}})>-\infty.$

######  Assumption 2.2.

We suppose the function set $\\{f_{i}(\cdot)\\}_{i=1}^{n}$ is $L$-mean-squared
smooth for some $L>0$, i.e., we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\right\|^{2}\leq L^{2}\left\|{\bf{x}}-{\bf{y}}\right\|^{2},$

for any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{d}$.

######  Assumption 2.3.

We suppose objective function $f(\cdot)$ is $\mu$-PL for some $\mu>0$, i.e.,
we have

$\displaystyle
f({\bf{x}})-\inf_{{\bf{y}}\in{\mathbb{R}}^{d}}f({\bf{y}})\leq\frac{1}{2\mu}\left\|\nabla
f({\bf{x}})\right\|_{2}^{2}$

for any ${\bf{x}}\in{\mathbb{R}}^{d}$.

Based on above assumptions, we define condition number and
$\epsilon$-suboptimal solution of our problem.

######  Definition 2.4.

We define $\kappa\triangleq L/\mu$ as the condition number of problem (1).

######  Definition 2.5.

We say $\hat{\bf{x}}$ is an $\epsilon$-suboptimal solution of Problem (1) if
it holds that $f(\hat{\bf{x}})-f^{*}\leq\epsilon$.

We use the notation $\tilde{\mathcal{O}}(\cdot)$ to hide the logarithmic
dependence on condition number $\kappa$ and individuals number $n$.

For the decentralized setting, the individual $f_{i}(\cdot)$ presents the
local function on the $i$-th agent. We define the aggregate variable and the
corresponding aggregated gradient as

$\displaystyle\begin{split}{\bf X}=\begin{bmatrix}{\bf{x}}(1)\\\ \vdots\\\
{\bf{x}}(n)\end{bmatrix}\in{\mathbb{R}}^{n\times
d}\qquad\text{and}\qquad\nabla{\bf F}({\bf X})=\begin{bmatrix}\nabla
f_{1}({\bf{x}}(1))\\\ \vdots\\\ \nabla
f_{n}({\bf{x}}(n))\end{bmatrix}\in{\mathbb{R}}^{n\times d}\end{split}$

respectively, where ${\bf{x}}(i)\in{\mathbb{R}}^{1\times d}$ is the local
variable on the $i$-th agent. For given ${\bf X}\in{\mathbb{R}}^{n\times d}$,
we also introduce the mean vector
${{\bar{\bf{x}}}}=\frac{1}{n}{\bf{1}}^{\top}{\bf
X}=\frac{1}{n}\sum_{i=1}^{n}{\bf{x}}(i)\in{\mathbb{R}}^{1\times d}$. For the
ease of presentation, we let the input of a function can also be organized as
a row vector, such as $f(\bar{\bf{x}})$ and $f_{i}({\bf{x}}(i))$.

We describe one communication round by multiplying the mixing matrix ${\bf
W}\in{\mathbb{R}}^{n\times n}$ on the aggregated variable. We give the
following assumption for matrix ${\bf W}$.

######  Assumption 2.6.

We suppose mixing matrix ${\bf W}\in{\mathbb{R}}^{n\times n}$ has the
following properties: (a) We have ${\bf W}={\bf W}^{\top}$, ${\bf
W}{\bf{1}}_{n}={\bf{1}}_{n}$ and ${\bf{0}}\preceq{\bf W}\preceq{\bf I}$; (b)
The entry of ${\bf W}$ holds that $w_{i,j}>0$ if and only if the $i$-th agent
and the $j$-th agent are connected or $i=j$, otherwise it holds that
$w_{ij}=0$. (c) The spectral gap of ${\bf W}$ is lower bounded by
$\gamma\in(0,1]$, i.e., it holds that $1-\lambda_{2}({\bf W})\geq\gamma$ for
some $\gamma\in(0,1]$, where $\lambda_{2}({\bf W})$ is the second-largest
eigenvalue of ${\bf W}$.

###  2.2 The Finite-Sum Optimization

The complexity of first-order methods for solving the finite-sum optimization
Problem (1) on single machine mainly depends on the number of access to the
incremental first-order oracle (IFO), which is defined as follows [1, 56].

######  Definition 2.7.

The incremental first-order oracle (IFO) takes the input $i\in[n]$ and
${\bf{x}}$, and returns the pair $(f_{i}({\bf{x}}),\nabla f_{i}({\bf{x}}))$.

Then we formally define the IFO algorithm.

######  Definition 2.8.

An IFO algorithm for given initial point ${\bf{x}}^{0}$ is defined as a
measurable mapping from functions $\\{f_{i}(\cdot)\\}_{i=1}^{n}$ to an
infinite sequence of point and index pairs
$\\{({\bf{x}}^{t},i_{t})\\}_{t=0}^{\infty}$ with random variable
$i_{t}\in[n]$, which satisfies

$\displaystyle{\bf{x}}^{t}\in\mathrm{Lin}\big{(}\\{{\bf{x}}^{0},\ldots,{\bf{x}}^{t-1},\nabla
f_{i_{0}}({\bf{x}}^{0}),\ldots,\nabla f_{i_{t-1}}({\bf{x}}^{t-1})\\}\big{)},$

where $\mathrm{Lin}(\cdot)$ denotes the linear span and $i_{t}$ denotes the
index of individual function chosen at the $t$-th step.

For the distributed optimization over a network of $n$ agents, the $i$-th
agent can only perform the computation on its local function $f_{i}(\cdot)$
directly. Hence, we describe the complexity of computational cost by the
number of access to the local first-order oracle (LFO).

######  Definition 2.9.

The local first-order oracle (IFO) takes the input $i\in[n]$ and ${\bf{x}}$ ,
and returns the pair $(f_{i}({\bf{x}}),\nabla f_{i}({\bf{x}}))$.

Recall that agents on network can only communicate with their neighbours,
which means the agent in decentralized algorithms cannot arbitrarily establish
the linear space of all local gradients. Additionally, one iteration of the
algorithm allows a mini-batch of agents to compute their local gradient in
parallel. Therefore, besides the LFO complexity, we also need to separately
consider the communication complexity and the time complexity. This motivates
the following definition for decentralized first-order oracle algorithm (DFO)
[50].

######  Definition 2.10.

A decentralized first-order oracle (DFO) algorithm over a network of $n$
agents satisfies the following constraints:

  * •

Local memory: Each agent $i$ can store past values in a local memory
$\mathcal{M}_{i,s}$ at time $s>0$. These values can be accessed and used at
time $s$ by running the algorithm on agent $i$. Additionally, for all
$i\in[n]$, we have

$\displaystyle\mathcal{M}_{i}^{s}\subset\mathcal{M}_{{\rm
comp},i}^{s}\bigcup\mathcal{M}_{{\rm comm},i}^{s},$

where $\mathcal{M}_{{\rm comp},i}^{s}$ and $\mathcal{M}_{{\rm comm},i}^{s}$
are the values come from the computation and communication respectively.

  * •

Local computation: Each agent $i$ can access its local first-order oracle
$\\{f_{i}({\bf{x}}),\nabla f_{i}({\bf{x}})\\}$ for given
${\bf{x}}\in\mathcal{M}_{i,s}$ at time $s$. That is, for all $i\in[n]$, we
have

$\displaystyle\mathcal{M}_{{\rm comp},i}^{s}={\rm
Lin}\big{(}\\{{\bf{x}},\nabla
f_{i}({\bf{x}}):x\in\mathcal{M}_{i}^{s-1}\\}\big{)}.$

  * •

Local communication: Each agent $i$ can share its value to all or part of its
neighbors at time $s$. That is, for all $i\in[n]$, we have

$\displaystyle\mathcal{M}_{{\rm comm},i}^{s}={\rm
Lin}\Bigg{(}\bigcup_{j\in{\rm nbr}(i)}\mathcal{M}_{j}^{s-\tau}\Bigg{)},$

where ${\rm nbr}(i)$ is the set consists of the indices for the neighbours of
agent $i$ and $\tau<s$.

  * •

Output value: Each agent $i$ can specify one vector in its memory as local
output of the algorithm at time $s$. That is, for all $i\in[n]$, we have
${\bf{x}}_{i}^{s}\in\mathcal{M}_{i}^{s}$.

Table 2: We present the complexity for finding an $\epsilon$-suboptimal solution of Problem (1) in decentralized setting. Algorithm | Communication | Time | LFO | Reference
---|---|---|---|---
DGD-GT | $\tilde{\mathcal{O}}\left({\kappa}/{\sqrt{\gamma}}\log(1/\epsilon)\right)$ | $\tilde{\mathcal{O}}\left(\kappa\left(1+{\tau}/{\sqrt{\gamma}\,}\right)\log(1/\epsilon)\right)$ | ${\mathcal{O}}\big{(}\kappa n\log(1/\epsilon)\big{)}$ |  Theorem 5.1
DRONE | $\tilde{\mathcal{O}}\left({\kappa}/{\sqrt{\gamma}}\log(1/\epsilon)\right)$ | $\tilde{\mathcal{O}}\left(\kappa\left(1+{\tau}/{\sqrt{\gamma}}\,\right)\log(1/\epsilon)\right)$ | ${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$ |  Corollary 5.3
Lower Bound | $\Omega\left({\kappa}/{\sqrt{\gamma}}\log(1/\epsilon)\right)$ | $\Omega\left(\kappa\left(1+{\tau}/{\sqrt{\gamma}}\,\right)\log(1/\epsilon)\right)$ | $\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ |  Theorem 4.3, Corollary 4.4

##  3 The Lower Bound on IFO Complexity

This section provides the lower bound on IFO complexity to show the optimality
(up to logarithmic factors) of existing first-order methods [66, 55, 32].
Without loss of generality, we always assume the IFO algorithm iterates with
the initial point ${\bf{x}}^{(0)}={\bf{0}}$ in our analysis for lower bound.
Otherwise, we can take the functions
$\\{f_{i}({\bf{x}}+{\bf{x}}^{(0)})\\}_{i=1}^{n}$ into consideration.

We first consider the case of $n={\mathcal{O}}(\kappa^{2})$. We introduce the
functions $\psi_{\theta}:{\mathbb{R}}\to{\mathbb{R}}$,
$q_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ and
$g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ provided by Yue et al. [61], that
is

$\displaystyle\psi_{\theta}(x)=\begin{cases}\frac{1}{2}x^{2},&x\leq\frac{31}{32}\theta,\\\\[3.00003pt]
\frac{1}{2}x^{2}-16(x-\frac{31}{32}\theta)^{2},&{\frac{31}{32}\theta<x\leq\theta,}\\\\[3.00003pt]
\frac{1}{2}x^{2}-\frac{1}{32}\theta^{2}+16(x-\frac{33}{32}\theta)^{2},&{\theta<x\leq\frac{33}{32}\theta,}\\\\[3.00003pt]
\frac{1}{2}x^{2}-\frac{1}{32}\theta^{2},&{x>\frac{33}{32}\theta,}\end{cases}$
$\displaystyle
q_{T,t}({\bf{x}})=\frac{1}{2}\sum_{i=0}^{t-1}\Big{(}\Big{(}\frac{7}{8}x_{iT}-x_{iT+1}\Big{)}^{2}+\sum_{j=1}^{T-1}(x_{iT+j+1}-x_{iT+j})^{2}\Big{)},$
$\displaystyle\text{and}\quad
g_{T,t}({\bf{x}})=q_{T,t}({\bf{b}}-{\bf{x}})+\sum_{i=1}^{Tt}\psi_{b_{i}}(b_{i}-x_{i}),$

where we define $x_{0}=0$ and ${\bf{b}}\in\mathbb{R}^{Tt}$ with
$b_{kT+\tau}=({7}/{8})^{k}$ for $k\in\\{0\\}\cup[T-1]$ and $\tau\in[T]$. We
can verify that

$\displaystyle
g_{T,t}^{*}\triangleq\inf_{{\bf{y}}\in{\mathbb{R}}^{Tt}}g_{T,t}({\bf{y}})=0.$

The following lemma shows the function $g_{T,t}$ holds the zero-chain property
[42, 13] and describes its smoothness, PL parameter and optimal function value
gap, which results the tight lower bound of full-batch first-order methods
[61, Section 4].

######  Lemma 3.1.

The function $g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ holds that:

  1. (a)

For any ${\bf{x}}\in{\mathbb{R}}^{Tt}$ satisfying ${\rm
supp}({\bf{x}})\subseteq\left\\{1,2,\cdots,k\right\\}$, it holds ${\rm
supp}(\nabla g_{T,t}({\bf{x}}))\subseteq\left\\{1,2,\cdots,k+1\right\\}$.

  2. (b)

The function $g_{T,t}$ is 37-smooth.

  3. (c)

The function $g_{T,t}$ is $1/(aT)$-PL with $a=19708$.

  4. (d)

The function $g_{T,t}$ satisfies that $g_{T,t}(\mathbf{0})-g_{T,t}^{*}\leq
3T$.

  5. (e)

For any $\delta<0.01$, $t=2\lfloor\log_{{8}/{7}}{2}/{(3\delta)}\rfloor$ and
${\bf{x}}\in{\mathbb{R}}^{Tt}$ satisfying ${\rm
supp}({\bf{x}})\subseteq\left\\{1,2,\cdots,Tt/2\right\\}$, it holds that
$g_{T,t}({\bf{x}})-g_{T,t}^{*}>3T\delta$.

We can establish the mean-squared smooth functions by the composition of
orthogonal transform. Compared with the study on convex and general nonconvex
problem [14, 65], we present the following lemma by additionally considering
the PL condition.

######  Lemma 3.2.

Given a function $g:\mathbb{R}^{m}\rightarrow\mathbb{R}$ that is
$\hat{L}$-smooth and $\hat{\mu}$-PL, define $f_{i}({\bf{x}})=g({\bf
U}^{(i)}{\bf{x}})$ with ${\bf{x}}\in{\mathbb{R}}^{mn}$, $i\in[n]$ and ${\bf
U}^{\left(i\right)}=[{\bf{e}}_{(i-1)m+1},\cdots,{\bf{e}}_{im}]^{\top}\in{\mathbb{R}}^{m\times
mn}$. Then the function set
$\\{f_{i}:\mathbb{R}^{mn}\rightarrow\mathbb{R}\\}_{i=1}^{n}$ is
$\hat{L}/\sqrt{n}$-mean-squared smooth, and the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\hat{\mu}/n$-PL with
$f(\mathbf{0})-\inf_{{\bf{y}}\in{\mathbb{R}}}f({\bf{y}})=g(\mathbf{0})-\inf_{{\bf{y}}\in{\mathbb{R}}}g({\bf{y}})$.

To achieve the hard instance functions with the desired smoothness and PL
parameters, we also require the scaling lemma as follows.

######  Lemma 3.3.

Suppose the function $g:\mathbb{R}^{m}\rightarrow\mathbb{R}$ is
$\hat{L}$-smooth, $\hat{\mu}$-PL and has lower bound
$g^{*}=\inf_{{\bf{y}}\in{\mathbb{R}}^{m}}g({\bf{y}})$, then the function
$\hat{g}({\bf{x}})=\alpha g(\beta{\bf{x}})$ is
$\alpha\beta^{2}\hat{L}$-smooth, $\alpha\beta^{2}\hat{\mu}$-PL and satisfies
that $\hat{g}(\mathbf{0})-\hat{g}^{*}=\alpha(g(\mathbf{0})-g^{*})$ for any
$\alpha,\beta>0$, where
$\hat{g}^{*}=\inf_{{\bf{y}}\in{\mathbb{R}}^{m}}\hat{g}({\bf{y}})$.

Based on above lemmas 3.1, 3.2 and 3.3, we provide the lower bound of
$\Omega\big{(}\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ on IFO complexity for
large $\kappa$.

######  Theorem 3.4.

For any $L,\mu,n,\Delta$ and $\epsilon$ with $\epsilon<0.005\Delta$ and $L\geq
37a\sqrt{n}\mu$, there exists $L$-mean-squared smooth function set
$\\{f_{i}:\mathbb{R}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ with
$d={\mathcal{O}}(\kappa\sqrt{n}\log(1/\epsilon))$ such that the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL with
$f({\bf{x}}^{0})-f^{*}\leq\Delta$. In order to find an $\epsilon$-suboptimal
solution of problem $\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})$, any IFO
algorithm needs at least $\Omega\big{(}\kappa\sqrt{n}\log(1/\epsilon)\big{)}$
IFO calls.

We present the proof sketch of Theorem 3.4 as follows and defer the details in
Appendix A.3. Specifically, we take the function
$g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ with $T=\lfloor
L/(37a\sqrt{n}\mu)\rfloor$ and
$t=2\lfloor\log_{{8}/{7}}{\Delta}/{(3\epsilon)}\rfloor$, and let
$\hat{g}({\bf{x}})=\alpha g_{T,t}(\beta{\bf{x}})$ with $\alpha=\Delta/(3T)$
and $\beta=\sqrt{3\sqrt{n}LT/(37\Delta)}$. We also define function set
$\\{f_{i}:{\mathbb{R}}^{nTt}\to{\mathbb{R}}\\}_{i=1}^{n}$ by following Lemma
3.2 with $g({\bf{x}})=\hat{g}({\bf{x}})$ and $m=Tt$. Then statements (b)-(d)
of Lemma 3.1 and the scaling property shown in Lemma 3.3 means such
construction results that the condition number of the problem is
$\kappa=L/\mu$ and the optimal function value is gap $\Delta$. Finally, the
statements (a) and (e) of Lemma 3.1 leads to the desired lower complexity
bound.

We then consider the case of $n=\Omega(\kappa^{2})$. Following the analysis by
Li et al. [32, Theorem 2], we establish the lower bound of $\Omega(n)$ for IFO
complexity by introducing
$\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ with
$f_{i}({\bf{x}})=c\left<\mathbf{u}_{i},{\bf{x}}\right>+\frac{L}{2}\|{\bf{x}}\|^{2}$,
where
$\mathbf{u}_{i}=[{\mathbb{I}}(\lceil{1}/{(2n)}\rceil=i),\cdots,{\mathbb{I}}(\lceil{2n^{2}}/{(2n)}\rceil=i)]^{\top}\in\mathbb{R}^{2n^{2}}$,
$d=2n^{2}$, $c=\sqrt{L\Delta}$ and ${\mathbb{I}}(\cdot)$ is the indicator
function. We can verify
$\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ is $L$-mean-squared
smooth and $f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL with
the optimal function value gap $\Delta$. Additionally, each $f_{i}(\cdot)$
holds zero-chain property, which leads to the lower bound of $\Omega(n)$ on
IFO complexity. We formally present this result in the following theorem and
leave the detailed proof in Appendix A.4.

######  Theorem 3.5.

For any $L,\mu,n,\Delta$ and $\epsilon$ with $\epsilon<{\Delta}/{2}$ and
$L\geq\mu$, there exists $L$-mean-squared smooth function set
$\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ with
$d={\mathcal{O}}(n^{2})$ such that the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL with
$f({\bf{x}}^{0})-f^{*}\leq\Delta$. In order to find an $\epsilon$-suboptimal
solution of problem $\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})$, any IFO
algorithm needs at least $\Omega(n)$ IFO calls.

We combine Theorem 3.4 and 3.5 to achieve the lower bound on IFO complexity
for the first-order finite-sum optimization under the PL condition.

######  Corollary 3.6.

For any $L,\mu,n,\Delta$ and $\epsilon$ with $\epsilon<0.005\Delta$ and
$L\geq\mu$. there exists $L$-mean-squared smooth function set
$\\{f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\\}_{i=1}^{n}$ with
$d={\mathcal{O}}(n^{2}+\kappa\sqrt{n}\log(1/\epsilon)$ such that the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL and satisfies
$f({\bf{x}}^{0})-f^{*}\leq\Delta$. In order to find an $\epsilon$-suboptimal
solution of problem $\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})$, any IFO
algorithm needs at least
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ IFO calls.

Noticing that the lower bound of
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ on IFO complexity shown
in Corollary 3.6 nearly matches the upper bound of
${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$ achieved by
stochastic recursive gradient algorithms [66, 55, 32].

##  4 Lower Bounds in Decentralized Setting

This section provides lower bounds for decentralized setting. The main idea of
our construction is splitting the function
$g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ (defined in Section 3) as follows

$\displaystyle
g_{T,t}({\bf{x}})=q_{1}({\bf{b}}-{\bf{x}})+q_{2}({\bf{b}}-{\bf{x}})+r({\bf{x}}),$

where we define the functions $q_{1}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$,
$q_{2}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ and
$r:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ as

$\displaystyle\begin{split}&q_{1}({\bf{x}})=\frac{1}{2}\sum_{i=1}^{Tt/2}(x_{2i-1}-x_{2i})^{2},\\\
&q_{2}({\bf{x}})=\frac{1}{2}\sum_{i=0}^{t-1}\left[\Big{(}\frac{7}{8}x_{iT}-x_{iT+1}\Big{)}^{2}+\sum_{j=iT/2+1}^{(i+1)T/2-1}(x_{2j}-x_{2j+1})^{2}\right],\\\
&\text{and}\quad
r({\bf{x}})=\sum_{i=1}^{Tt}\psi_{b_{i}}(b_{i}-x_{i}),\end{split}$

Based on above decomposition for $g_{T,t}$, we can establish an hard instance
of $n$ individual functions for communication complexity and time complexity.
We let ${\mathcal{G}}=\\{{\mathcal{V}},{\mathcal{E}}\\}$ be the graph
associated to the network of the agents, where the node set
${\mathcal{V}}=\\{1,\dots,n\\}$ corresponds to the $n$ agents and the edge set
${\mathcal{E}}=\\{(i,j):\text{node $i$ and node $j$ are connected}\\}$
describes the topology for the network of agents. For given a subset
${\mathcal{C}}\subseteq\mathcal{V}$, we define the function
$h_{i}^{\mathcal{C}}({\bf{x}}):{\mathbb{R}}^{Tt}\rightarrow{\mathbb{R}}$ as

$\displaystyle
h_{i}^{\mathcal{C}}({\bf{x}})=\begin{cases}\frac{r({\bf{x}})}{n}+\frac{q_{1}({\bf{b}}-{\bf{x}})}{|{\mathcal{C}}|},&{i\in{\mathcal{C}}},\\\\[3.99994pt]
\frac{r({\bf{x}})}{n}+\frac{q_{2}({\bf{b}}-{\bf{x}})}{|{\mathcal{C}}_{\sigma}|},&{i\in{\mathcal{C}}_{\sigma}},\\\\[3.99994pt]
\frac{r({\bf{x}})}{n},&{\text{otherwise}},\end{cases}$

where ${\mathcal{C}}_{\sigma}=\left\\{v\in\mathcal{V}:{\rm
dis}({\mathcal{C}},v)\geq\sigma\right\\}$ and ${\rm dis}({\mathcal{C}},v)$ is
the distance between set ${\mathcal{C}}$ and node $v$.

We can verify the function sets
$\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\rightarrow{\mathbb{R}}\\}_{i=1}^{n}$
has the following properties.

######  Lemma 4.1.

We define $h(\cdot)=\frac{1}{n}\sum_{i=1}^{n}h_{i}^{\mathcal{C}}(\cdot)$, then
we have:

  1. (a)

The function sets
$\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\\}_{i=1}^{n}$ is
mean-squared smooth with parameter
$33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\}$.

  2. (b)

The function $h:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ is $1/\left(anT\right)$-PL.

  3. (c)

The function holds
$h(\mathbf{0})-\inf_{{\bf{y}}\in{\mathbb{R}}^{Tt}}h({\bf{y}})\leq 3T/n$.

Now we provide the lower bounds for communication complexity and time
complexity based on the scaling on the functions
$\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\rightarrow{\mathbb{R}}\\}_{i=1}^{n}$.

######  Lemma 4.2.

We let $f_{i}({\bf{x}})=\alpha h_{i}^{\mathcal{C}}(\beta{\bf{x}})$ with
${\bf{x}}\in{\mathbb{R}}^{Tt}$ and
$t=2\lfloor\log_{{8}/{7}}({2}/{3\delta})\rfloor$ for any $i\in[n]$ and some
$\alpha,\beta>0$. For given $\delta<0.01$, any DFO algorithm takes at least
$Tt\sigma/2$ communication complexity and $Tt(1+\sigma\tau)/2$ time complexity
to achieve an $3\alpha T\delta/n$-suboptimal solution of problem
$\min_{{\bf{x}}\in{\mathbb{R}}^{Tt}}\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}})$.

For given spectral gap $\gamma\in(0,1]$, we consider the linear graph
${\mathcal{G}}=\\{{\mathcal{V}},{\mathcal{E}}\\}$ with the node set
${\mathcal{V}}=\\{1,\dots,n\\}$ and the edge set
${\mathcal{E}}=\\{(i,j):|i-j|=1,i\in{\mathcal{V}}~{}~{}\text{and}~{}~{}j\in{\mathcal{V}}\\}$.
Combining with the function $f_{i}({\bf{x}})=\alpha
h_{i}^{\mathcal{C}}(\beta{\bf{x}})$ defined in Lemma 4.2, we achieve the lower
bounds of communication complexity and time complexity as follows.

######  Theorem 4.3.

For any $L,\mu,\Delta,\gamma$ and $\epsilon$ with $L\geq 194a\mu$,
$\gamma\in(0,1]$ and $\epsilon<0.01\Delta$, there exist matrix ${\bf
W}\in{\mathbb{R}}^{n\times n}$ with $1-\lambda_{2}({\bf W})\geq\gamma$ and
$L$-mean-squared smooth function set
$\\{f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\\}_{i=1}^{n}$ with
$d={\mathcal{O}}(\kappa\log(1/\epsilon))$ such that
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL with
$f(\mathbf{0})-f^{*}\leq\Delta$ and $\gamma({\bf W})=\gamma$. In order to find
an $\epsilon$-suboptimal solution of problem
$\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})$, any DFO algorithm needs at
least $\Omega\big{(}\kappa/\sqrt{\gamma}\log(1/\epsilon)\big{)}$ communication
rounds and $\Omega\big{(}\kappa\log(1/\epsilon)(1+\tau/\sqrt{\gamma})\big{)}$
time cost.

The lower complexity bound on LFO complexity for decentralized setting can be
achieved by applying Corollary 3.6 on fully connected network.

######  Corollary 4.4.

For any $L,\mu,n,\Delta,\gamma$ and $\epsilon$ with $\epsilon<0.005\Delta$,
$L\geq\mu$ and $\gamma\in(0,1]$ , there exist mixing matrix ${\bf
W}\in{\mathbb{R}}^{n\times n}$ with $1-\lambda_{2}({\bf W})\geq\gamma$ and
$L$-mean-squared smooth function set
$\\{f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\\}_{i=1}^{n}$ with
$d={\mathcal{O}}(n^{2}+\kappa\sqrt{n}\log(1/\epsilon)$ such that the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $\mu$-PL and satisfies
$f({\bf{x}}^{0})-f^{*}\leq\Delta$. In order to find an $\epsilon$-suboptimal
solution of problem $\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})$, any DFO
algorithm needs at least
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ LFO calls.

##  5 Decentralized First-Order Algorithms

Algorithm 1 GD

1: Input: initial point ${\bf{x}}^{0}\in{\mathbb{R}}^{d}$, iteration number
$T$ and stepsize $\eta>0$

2: for $t=0,1,\dots,T-1$ do

3: ${\bf{x}}^{t+1}={\bf{x}}^{t}-\eta\nabla f({\bf{x}}^{t})$

4: end for

5: Output: ${\bf{x}}^{T}$

Algorithm 2 ${{\rm AccGossip}}({\bf Y}^{0},{\bf W},K)$

1: Initialize: ${\bf Y}^{-1}={\bf Y}^{0}$

2: $\eta_{y}=1/\big{(}1+\sqrt{1-\lambda_{2}^{2}({\bf W})}\,\big{)}$

3: for $k=0,1,\dots,K$ do

4: ${\bf Y}^{k+1}=(1+\eta_{y}){\bf W}{\bf Y}^{k}-\eta_{y}{\bf Y}^{k-1}$

5: end for

6: Output: ${\bf Y}^{K}$

Algorithm 3 DGD-GT

1: Input: initial point ${{\bar{\bf{x}}}}_{0}\in{\mathbb{R}}^{1\times d}$,
iteration number $T$, stepsize $\eta>0$ and communication numbers $K$

2: ${\bf X}^{0}={\bf{1}}{{\bar{\bf{x}}}}^{0}$

3: ${\bf S}^{0}=\nabla{\bf F}({\bf X}^{0})$

4: for $t=0,\dots,T-1$ do

5: ${\bf X}^{t+1}={{\rm AccGossip}}({\bf X}^{t}-\eta{\bf S}^{t},{\bf W},K)$

6: ${\bf S}^{t+1}={{\rm AccGossip}}({\bf S}^{t}+\nabla{\bf F}({\bf
X}^{t+1})-\nabla{\bf F}({\bf X}^{t}),{\bf W},K)$

7: end for

8: Output: uniformly sample ${\bf{x}}^{\rm out}$ from
$\\{{\bf{x}}^{T}(i)\\}_{i=1}^{n}$

Algorithm 4 DRONE

1: Input: initial point ${{\bar{\bf{x}}}}^{0}\in{\mathbb{R}}^{1\times d}$,
mini-batch size $b$, iteration number $T$, stepsize $\eta>0$, probability
$p,q\in(0,1]$ and communication numbers $K$.

2: ${\bf X}^{0}={\bf{1}}{{\bar{\bf{x}}}}^{0}$

3: ${\bf S}^{0}={\bf G}^{0}=\nabla{\bf F}({\bf X}^{0})$

4: for $t=0,\dots,T-1$ do

5: $\zeta^{t}\sim{\rm Bernoulli}(p)$

6: $[\xi^{t}_{1},\cdots,\xi^{t}_{n}]^{\top}\sim{\rm Multinomial}(b,q{\bf{1}})$

7: ${\bf X}^{t+1}={{\rm AccGossip}}({\bf X}^{t}-\eta{\bf S}^{t},{\bf W},K)$

8: parallel for $i=1,\dots,n$ do

9: if $\zeta^{t}=1$ then

10: ${\bf{g}}^{t+1}(i)=\nabla f_{i}({\bf{x}}^{t+1}(i))$

11: else

12: ${\bf{g}}^{t+1}(i)={\bf{g}}^{t}(i)+\dfrac{\xi^{t}_{i}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}$

13: end if

14: end parallel for

15: ${\bf S}^{t+1}={{\rm AccGossip}}({\bf S}^{t}+{\bf G}^{t+1}-{\bf
G}^{t},{\bf W},K)$

16: end for

17: Output: uniformly sample ${\bf{x}}^{\rm out}$ from
$\\{{\bf{x}}^{T}(i)\\}_{i=1}^{n}$

It is well-known that GD achieves the linear convergence for minimizing the PL
function [25] on single machine. For decentralized optimization, it is natural
to integrate GD with gradient tracking [52, 40, 47] and Chebyshev acceleration
[6, 50, 53, 58], leading to Algorithm 3 which is called decentralized gradient
descent with gradient tracking (DGD-GT). The following theorem shows that the
communication complexity and the time complexity of DGD-GT nearly match the
lower bounds shown in Corollary 4.3.

######  Theorem 5.1.

We suppose that Assumption 2.1–2.6 hold, then running Algorithm 3 (DGD-GT)
with appropriate parameters setting achieves ${\mathbb{E}}[f({\bf{x}}^{\rm
out})-f^{*}]\leq\epsilon$ within communication complexity of
$\tilde{\mathcal{O}}\big{(}\kappa/\sqrt{\gamma}\log(1/\epsilon)\big{)}$, time
complexity of
$\tilde{\mathcal{O}}\big{(}\kappa(1+\tau/\sqrt{\gamma}\,)\log(1/\epsilon)\big{)}$
and LFO complexity of ${\mathcal{O}}\big{(}n\kappa\log(1/\epsilon)\big{)}$ in
expectation.

However, the upper bound on LFO complexity of DGD-GT (Algorithm 3) shown in
Theorem 5.1 does not match the lower bound of
$\Omega\big{(}n+\kappa\sqrt{n}\log(1/\epsilon)\big{)}$ provided by Corollary
4.4. Recall that the optimal IFO methods for non-distributed setting are based
on the stochastic recursive ‘gradient [32, 66, 55]. We borrow this idea to
construct the recursive gradient with respect to local agents, i.e., we update
the local gradient estimator by

$\displaystyle\begin{split}{\bf{g}}^{t+1}(i)=\begin{cases}\nabla
f_{i}({\bf{x}}^{t+1}(i)),&\zeta^{t}=1,\\\\[4.26773pt]
{\bf{g}}^{t}(i)+\dfrac{\xi^{t}_{i}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)},&\zeta^{t}=0,\end{cases}\end{split}$

where we introduce random variables $\zeta^{t}\sim{\rm Bernoulli}(p)$ and
$[\xi^{t}_{1},\cdots,\xi^{t}_{n}]^{\top}\sim{\rm Multinomial}(b,q{\bf{1}})$
with some small probabilities $p$ and $q$ which encourage only few of agents
compute local gradients in most of iterations. Similar to the procedure of
DGD-GT (Algorithm 3), we can also introduce steps of gradient tracking and
Chebyshev acceleration to improve the communication efficiency. Finally, we
achieve decentralized recursive local gradient descent (DRONE) method, which
is formally presented in Algorithm 4.

We analyze the complexity of DRONE by the following Lyapunov function

$\displaystyle\Phi^{t}=\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\alpha
U^{t}+\beta V^{t}+LC^{t},$

where $\alpha=2\eta/p$, $\beta=8L\rho^{2}n\eta^{2}$,

$\displaystyle
U^{t}=\mathbb{E}\Bigg{\|}\frac{1}{n}\sum_{i=1}^{n}\big{(}{\bf{g}}^{t}(i)-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\Bigg{\|}^{2},$ $\displaystyle
V^{t}=\frac{1}{n}\mathbb{E}\|{\bf G}^{t}-\nabla{\bf F}({\bf X}^{t})\|^{2},$
$\displaystyle\text{and}~{}~{}~{}~{}C^{t}={\mathbb{E}}\|{\bf
X}^{t}-\mathbf{1}{{\bar{\bf{x}}}}^{t}\|^{2}+\eta^{2}\mathbb{E}\|{\bf
S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}.$

Compared with the analysis of Luo and Ye [36], Li et al. [29], Xin et al. [57]
for general nonconvex case, we additionally introduce the term of $f^{*}$ into
our Lyapunov function to show the desired linear convergence under the PL
condition, i.e., we can show that

$\displaystyle\Phi^{T}\leq(1-\mu\eta)^{T}\Phi^{0}$

by taking $\eta=\Theta(1/L)$. We present the convergence result of DRONE
formally in the following theorem and corollary.

######  Theorem 5.2.

We suppose that Assumption 2.1–2.6 hold, then running DRONE (Algorithm 4) with
parameters setting

$\displaystyle\begin{split}&p\in\left[\frac{1}{n+1},\frac{1}{2}\right],~{}~{}~{}b\in\left[\frac{1-p}{p},n\right],~{}~{}~{}\eta\leq\min\left\\{\frac{1}{20L},\frac{p}{2\mu}\right\\},\\\
&~{}q=\frac{1}{n},~{}~{}K=\left\lceil\frac{\sqrt{2}\,(4+\log
n)}{(\sqrt{2}-1)\sqrt{\gamma}}\right\rceil~{}~{}\text{and}~{}~{}T\geq\left\lceil\frac{1}{\mu\eta}\log\frac{\Phi^{0}}{\epsilon}\right\rceil\end{split}$

achieves output satisfying ${\mathbb{E}}[f({\bf{x}}^{\rm
out})-f^{*}]\leq\epsilon$.

######  Corollary 5.3.

Under the setting of Theorem 5.2, running DRONE (Algorithm 4) by specifically
taking

$\displaystyle\begin{split}&p=\frac{1}{\min\\{\sqrt{n},\kappa\\}+1},~{}~{}b=\left\lceil\frac{1-p}{p}\right\rceil,~{}~{}\eta=\min\left\\{\frac{1}{20L},\frac{p}{2\mu}\right\\},\\\
&~{}q=\frac{1}{n},~{}~{}K=\left\lceil\frac{\sqrt{2}\,(4+\log
n)}{(\sqrt{2}-1)\sqrt{\gamma}}\right\rceil~{}~{}\text{and}~{}~{}T=\left\lceil\frac{1}{\mu\eta}\log\frac{\Phi^{0}}{\epsilon}\right\rceil\end{split}$

achieves output satisfying ${\mathbb{E}}[f({\bf{x}}^{\rm
out})-f^{*}]\leq\epsilon$ within communication complexity of
$\tilde{\mathcal{O}}\big{(}\kappa/\sqrt{\gamma}\log(1/\epsilon)\big{)}$, time
complexity of
$\tilde{\mathcal{O}}\big{(}\kappa(1+\tau/\sqrt{\gamma}\,)\log(1/\epsilon)\big{)}$
and LFO complexity of
${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$ in
expectation.

Note that the setting of $p=1/(\min\\{\sqrt{n},\kappa\\}+1)$ leads to
$b={\mathcal{O}}(\min\\{\sqrt{n},\kappa\\})$,
$\eta=\Theta\left({1}/{L}\right)$ and $T=\Theta(\kappa\log({1}/{\epsilon}))$,
guarantees the algorithm nearly match the LFO lower bound (Corollary 4.4) in
both cases of $n={\mathcal{O}}(\kappa^{2})$ and $n=\Omega(\kappa^{2})$.

As a comparison, the analysis of PAGE [32] (for single machine optimization)
takes $p=\Theta(1/\sqrt{n}\,)$, which leads to that $b=\Theta(\sqrt{n}\,)$,
$\eta=\Theta(\min\\{1/L,1/(\mu\sqrt{n}\,)\\})$ and
$T=\Theta((\kappa+\sqrt{n}\,)\log(1/\epsilon))$. If we directly apply these
parameters to DRONE, it will result LFO complexity of
${\mathcal{O}}\big{(}(n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big{)}$,
communication complexity of
$\tilde{\mathcal{O}}\big{(}(\kappa+\sqrt{n}\,)\log(1/\epsilon)/\sqrt{\gamma}\,\big{)}$
and time complexity of
$\tilde{\mathcal{O}}\big{(}({\kappa+\sqrt{n}\,)}(1+\tau/\sqrt{\gamma}\,)\log(1/\epsilon)\big{)}$
in expectation. In the case of $n=\Omega(\kappa^{2})$, such communication
complexity and time complexity do not match the corresponding lower bounds
(Theorem 4.3). Intuitively, our analysis for DRONE considers the larger
stepsize $\eta=\Theta(1/L)\geq\Theta(1/(\mu\sqrt{n}\,))$ than PAGE when
$n=\Omega(\kappa^{2})$, which is important to reduce the iteration numbers
$T=\lceil(1/\mu\eta)\log(\Phi^{0}/\epsilon)\rceil$, also reduce the overall
communication rounds $KT$ and the overall time cost $(1+K\tau)T$.

##  6 Numerical Experiments

We conduct numerical experiments to compare DRONE with centralized gradient
descent (CGD) and DGD-GT, where CGD is a distributed extension of GD in
client-server network. Please see Appendix D for details.

We test the algorithms on the following three problems:

  * •

Hard instance: We follow the instance in the proof of Theorem 4.3 (Appendix
B.3) and specifically let

$\displaystyle
f_{i}({\bf{x}})=\frac{16}{3}h_{i}^{\mathcal{C}}\big{(}\sqrt{12a}{\bf{x}}\big{)}$

for formulation (1). We set $T=2$, $t=72$, ${\mathcal{C}}=\left\\{1\right\\}$
and $\sigma=29$ for $h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$.

  * •

Linear regression: We consider the problem

$\displaystyle\begin{split}\min_{{\bf{x}}\in{\mathbb{R}}^{d}}f({\bf{x}})=\frac{1}{m}\sum_{j=1}^{m}\ell_{j}({\bf{x}})~{}\text{with}~{}\ell_{j}({\bf{x}})=({\bf{a}}_{j}^{\top}{\bf{x}}-b_{j})^{2}\end{split}$
(2)

where ${\bf{a}}_{j}\in{\mathbb{R}}^{d}$ is the feature vector of the $j$-th
sample and $b_{j}\in{\mathbb{R}}$ is its label. We allocate the $m$ individual
loss on the $n$ agents, which leads to

$\displaystyle f_{i}({\bf{x}})=\frac{n}{m}\sum_{j=\lceil
m/n\rceil(i-1)+1}^{\min\\{\lceil m/n\rceil
i,m\\}}({\bf{a}}_{j}^{\top}{\bf{x}}-b_{j})^{2}.$ (3)

We evaluate the algorithms on dataset “DrivFace” ($m=606$, $d=921,600$) [16]
for this problem.

  * •

Logistic regression: The objective function and local functions of this
problem are similar to the counterparts in formulation (2)–(3), but replace
the loss function by

$\displaystyle\hat{\ell}_{j}({\bf{x}})=\log\big{(}1+\exp(-b_{j}{\bf{a}}_{j}^{\top}{\bf{x}})\big{)}.$

and require $b_{j}\in\\{1,-1\\}$. We evaluate the algorithms on dataset “RCV1”
($m=20,242$, $d=47,236$) [16] for this problem.

For all above problems, we set $n=32$ and use linear graph for network of DGD-
GT and DRONE, leading to spectral gap
$\gamma=\left(1-\cos({\pi}/{32})\right)/\left(1+\cos({\pi}/{32})\right)\approx
0.0024$.

We present empirical results for CGD, DGD-GT and DRONE on problems of hard
instance, linear regression and logistic regression in Figure 1, 2 and 3,
which includes the comparisons on LFO calls, communication rounds and running
time.

We can observe that DRONE requires significantly less LFO calls, since we have
showed only DRONE matches the lower complexity bound on LFO calls. We also
observed CGD needs much less communication rounds than DGD-GT and DRONE, which
also leads to less running time. This is because of the client-server
framework in CGD does not suffers from the consensus error which cannot be
avoided in decentralized optimization. It also validate our theoretical
analysis that the linear graph heavily affect the convergence rate of
decentralized algorithms. Additionally, DGD-GT and DRONE have comparable
communication rounds and running time for all of these problems, which also
supports our theoretical results (see Table 2).

Figure 1: The results for the hard instance in the proof of Theorem 4.3.

Figure 2: The results for linear regression on dataset “DrivFace”.

Figure 3: The results for logistic regression on dataset “RCV1”.

##  7 Conclusion

We provide the lower complexity bound for smooth finite-sum optimization under
the PL condition, which implies the upper bound of IFO complexity archived by
existing first-order methods [55, 32, 66] is nearly tight. We also construct
the lower bounds of communication complexity, time complexity and LFO
complexity for minimizing the PL function in distributed setting and verify
their tightness by proposing decentralized recursive local gradient descent.

In future work, we would like to study the lower bound in more general
stochastic setting that the objective (or local functions) has the form of
expectation [59, 7]. We are also interested in extending our results to
address the functions that satisfy the Kurdyka–Łojasiewicz inequality [11, 10,
8, 67, 19, 23].

##  Appendix A The Proofs for Section 3

Without the loss of generality, we always assume the IFO algorithm iterates
with initial point ${\bf{x}}^{(0)}={\bf{0}}$. Otherwise, we can take functions
$\\{f_{i}({\bf{x}}+{\bf{x}}^{(0)}\\}_{i=1}^{n}$ into consideration.

Recall that we have defined the functions
$\psi_{\theta}:{\mathbb{R}}\to{\mathbb{R}}$,
$q_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ and
$g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ as [61]

$\displaystyle\psi_{\theta}(x)=\begin{cases}\frac{1}{2}x^{2},&x\leq\frac{31}{32}\theta,\\\\[5.0pt]
\frac{1}{2}x^{2}-16(x-\frac{31}{32}\theta)^{2},&{\frac{31}{32}\theta<x\leq\theta,}\\\\[5.0pt]
\frac{1}{2}x^{2}-\frac{1}{32}\theta^{2}+16(x-\frac{33}{32}\theta)^{2},&{\theta<x\leq\frac{33}{32}\theta,}\\\\[5.0pt]
\frac{1}{2}x^{2}-\frac{1}{32}\theta^{2},&{x>\frac{33}{32}\theta,}\end{cases}$
(4) $\displaystyle
q_{T,t}({\bf{x}})=\frac{1}{2}\sum_{i=0}^{t-1}\left(\left(\frac{7}{8}x_{iT}-x_{iT+1}\right)^{2}+\sum_{j=1}^{T-1}(x_{iT+j+1}-x_{iT+j})^{2}\right),$

and

$\displaystyle
g_{T,t}({\bf{x}})=q_{T,t}({\bf{b}}-{\bf{x}})+\sum_{i=1}^{Tt}\psi_{b_{i}}(b_{i}-x_{i}).$
(5)

where $x_{0}=0$ and ${\bf{b}}\in\mathbb{R}^{Tt}$ with
$b_{kT+\tau}=({7}/{8})^{k}$ for $k\in\\{0\\}\cup[t-1]$ and $\tau\in[T]$. We
can verify that

$\displaystyle
g_{T,t}^{*}\triangleq\inf_{{\bf{y}}\in{\mathbb{R}}^{Tt}}g_{T,t}({\bf{y}})=0.$

###  A.1 The Proof of Lemma 3.2

###### Proof.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{mn}$, the smoothness of
$g:{\mathbb{R}}^{m}\to{\mathbb{R}}$ implies

$\displaystyle\|\nabla f_{i}({\bf{x}})-\nabla f_{i}({\bf{y}})\|=$
$\displaystyle\Big{\|}({\bf U}^{(i)})^{\top}\nabla g(U^{(i)}{\bf{x}})-({\bf
U}^{(i)})^{\top}\nabla g(U^{(i)}{\bf{y}})\Big{\|}$ $\displaystyle=$
$\displaystyle\big{\|}\nabla g({\bf U}^{(i)}{\bf{x}})-\nabla g({\bf
U}^{(i)}{\bf{y}})\big{\|}$ $\displaystyle\leq$
$\displaystyle\hat{L}\big{\|}{\bf U}^{(i)}({\bf{x}}-{\bf{y}})\big{\|}$
$\displaystyle\leq$ $\displaystyle\hat{L}\|{\bf{x}}-{\bf{y}}\|,$

and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\|^{2}=$ $\displaystyle\frac{1}{n}\sum_{i=1}^{n}\Big{\|}({\bf
U}^{(i)})^{\top}\nabla g({\bf U}^{(i)}{\bf{x}})-({\bf U}^{(i)})^{\top}\nabla
g({\bf U}^{(i)}{\bf{y}})\Big{\|}^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\big{\|}\nabla g({\bf
U}^{(i)}{\bf{x}})-\nabla g({\bf U}^{(i)}{\bf{y}})\big{\|}^{2}$
$\displaystyle=$ $\displaystyle\frac{\hat{L}^{2}}{n}\sum_{i=1}^{n}\big{\|}{\bf
U}^{(i)}({\bf{x}}-{\bf{y}})\big{\|}^{2}$ $\displaystyle\leq$
$\displaystyle\frac{\hat{L}^{2}}{n}\|{\bf{x}}-{\bf{y}}\|^{2}.$

This implies each $f_{i}:{\mathbb{R}}^{mn}\to{\mathbb{R}}$ is $\hat{L}$-smooth
and $\\{f_{i}:{\mathbb{R}}^{mn}\to{\mathbb{R}}\\}_{i=1}^{n}$ is
$\hat{L}/\sqrt{n}$-average smooth.

For any ${\bf{x}}\in{\mathbb{R}}^{mn}$, the PL condition of
$g:{\mathbb{R}}^{m}\to{\mathbb{R}}$ implies

$\displaystyle\|\nabla f({\bf{x}})\|^{2}$
$\displaystyle=\frac{1}{n^{2}}\Big{\|}\sum_{i=1}^{n}\nabla
f_{i}({\bf{x}})\Big{\|}^{2}$
$\displaystyle=\frac{1}{n^{2}}\Big{\|}\sum_{i=1}^{n}({\bf
U}^{(i)})^{\top}\nabla g({\bf U}^{(i)}{\bf{x}})\Big{\|}^{2}$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\big{\|}\nabla g({\bf
U}^{(i)}{\bf{x}})\big{\|}^{2}$
$\displaystyle\geq\frac{\hat{\mu}}{n^{2}}\sum_{i=1}^{n}\Big{(}g({\bf
U}^{(i)}{\bf{x}})-\inf\limits_{{\bf{x}}\in\mathbb{R}^{mn}}g({\bf
U}^{(i)}{\bf{x}})\Big{)}$
$\displaystyle=\frac{\hat{\mu}}{n}(f({\bf{x}})-f^{*}),$

which means $f:{\mathbb{R}}^{mn}\to{\mathbb{R}}$ is $\hat{\mu}/n$-PL.

Consider the facts $f({\bf{0}})=g({\bf{0}})$ and

$\displaystyle\inf\limits_{{\bf{x}}\in\mathbb{R}^{mn}}\sum_{i=1}^{n}g({\bf
U}^{(i)}{\bf{x}})=\sum_{i=1}^{n}\inf\limits_{{\bf{x}}\in\mathbb{R}^{mn}}g({\bf
U}^{(i)}{\bf{x}})=n\inf\limits_{{\bf{x}}\in\mathbb{R}^{m}}g({\bf{x}}),$

then we have

$\displaystyle
f(\mathbf{0})-\inf_{{\bf{y}}\in{\mathbb{R}}}f({\bf{y}})=g(\mathbf{0})-\inf_{{\bf{y}}\in{\mathbb{R}}}g({\bf{y}}).$

∎

###  A.2 The Proof of Lemma 3.3

###### Proof.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{mn}$, the smoothness of
$g:{\mathbb{R}}^{m}\to{\mathbb{R}}$ implies

$\displaystyle\left\|\nabla\hat{g}({\bf{x}})-\nabla\hat{g}({\bf{y}})\right\|$
$\displaystyle=\alpha\beta\left\|\nabla g(\beta{\bf{x}})-\nabla
g(\beta{\bf{y}})\right\|$
$\displaystyle\leq\alpha\beta\hat{L}\left\|\beta{\bf{x}}-\beta{\bf{y}}\right\|$
$\displaystyle\leq\alpha\beta^{2}\hat{L}\left\|{\bf{x}}-{\bf{y}}\right\|,$

which means $\hat{g}$ is $\alpha\beta^{2}\hat{L}$-smooth.

For any ${\bf{x}}\in{\mathbb{R}}^{mn}$, the PL condition of
$g:{\mathbb{R}}^{m}\to{\mathbb{R}}$ implies

$\displaystyle\left\|\nabla\hat{g}({\bf{x}})\right\|^{2}=$
$\displaystyle\alpha^{2}\beta^{2}\left\|\nabla g(\beta{\bf{x}})\right\|^{2}$
$\displaystyle\geq$ $\displaystyle
2\alpha^{2}\beta^{2}\hat{\mu}(g(\beta{\bf{x}})-g^{*})$ $\displaystyle=$
$\displaystyle 2\alpha\beta^{2}\hat{\mu}(\hat{g}({\bf{x}})-\hat{g}^{*}),$

which means $\hat{g}$ is $\alpha\beta^{2}\hat{\mu}$-PL.

We can verify that $\hat{g}(\mathbf{0})=\alpha g(\mathbf{0})$ and
$\hat{g}^{*}=\alpha g^{*}$, which means

$\displaystyle\hat{g}(\mathbf{0})-\hat{g}^{*}=\alpha(g(\mathbf{0})-g^{*}).$

∎

###  A.3 The Proof of Theorem 3.4

###### Proof.

We first take $g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ by following equation
(5) with

$\displaystyle
T=\left\lfloor\frac{L}{37a\sqrt{n}\mu}\right\rfloor\qquad\text{and}\qquad
t=2\left\lfloor\log_{{7}/{8}}\frac{3\epsilon}{\Delta}\right\rfloor.$

The statements (b), (c) and (d) of Lemma 3.1 means the function $g_{T,t}$ is
$37$-smooth, $1/(aT)$-PL and satisfies

$\displaystyle g_{T,t}({\bf{0}})-g_{T,t}^{*}\leq 3T.$

We apply Lemma 3.3 with

$\displaystyle g({\bf{x}})=g_{T,t}({\bf{x}}),\quad
m=Tt,\quad\alpha=\frac{\Delta}{3T}\quad\text{and}\quad\beta=\sqrt{\frac{3\sqrt{n}LT}{37\Delta}},$

which means the function $\hat{g}({\bf{x}})=\alpha g_{T,t}(\beta{\bf{x}})$ is
$37\alpha\beta^{2}$-smooth, $\alpha\beta^{2}/(aT)$-PL and satisfies

$\displaystyle\alpha g_{T,t}(\mathbf{0})-\alpha g_{T,t}^{*}\leq 3\alpha T.$

Then we apply Lemma 3.2 with

$\displaystyle g({\bf{x}})=\hat{g}({\bf{x}})=\alpha
g_{T,t}(\beta{\bf{x}})\qquad\text{and}\qquad m=Tt,$

which achieves $f_{i}({\bf{x}})=\alpha g_{T,t}(\beta{\bf U}^{(i)}{\bf{x}})$
and $f({\bf{x}})=\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}})$ such that
$\left\\{f_{i}:{\mathbb{R}}^{nTt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$ is
$37\alpha\beta^{2}/\sqrt{n}$-mean-squared smooth and $f:nTt$ is
$\alpha\beta^{2}/(anT)$-PL with

$\displaystyle f({\bf{x}}^{0})-f^{*}=\alpha g_{T,t}(\mathbf{0})-\alpha
g_{T,t}^{*}\leq 3\alpha T.$

The choice of $\alpha=\Delta/(3T)$ and $\beta=\sqrt{3\sqrt{n}LT/(37\Delta)}$
and condition $L\geq 37a\sqrt{n}\mu$ implies

$\displaystyle\frac{37\alpha\beta^{2}}{\sqrt{n}}=L,\qquad\frac{\alpha\beta^{2}}{anT}\geq\mu\qquad\text{and}\qquad
3\alpha T=\Delta.$

Therefore, the function set $\left\\{f_{i}\right\\}_{i=1}^{n}$ is $L$-average
smooth and the function $f$ is $\mu$-PL with
$f({\bf{x}}^{0})-f^{*}\leq\Delta$.

Let $\delta=2\epsilon/\Delta$, then we can write
$t=2\lfloor\log_{{8}/{7}}{2}/{(3\delta)}\rfloor$. Moreover, the assumption
$\epsilon<0.005\Delta$ means $\delta<0.01$. Then the statement (e) of Lemma
3.1 and definition $f_{i}({\bf{x}})=\alpha g_{T,t}(\beta{\bf
U}^{(i)}{\bf{x}})$ implies if ${\bf{x}}\in{\mathbb{R}}^{nTt}$ satisfies

$\displaystyle{\rm supp}({\bf
U}^{(i)}{\bf{x}})\subseteq\left\\{1,2,\cdots,Tt/2\right\\},$

then

$\displaystyle f_{i}({\bf{x}})-\alpha g_{T,t}^{*}$ $\displaystyle=\alpha
g_{T,t}(\beta U^{(i)}{\bf{x}})-\alpha g_{T,t}^{*}$ $\displaystyle>3\alpha
T\delta$ $\displaystyle=2\epsilon.$

Now we show that any IFO algorithm require at least $\lfloor
nTt/4\rfloor+1=\Omega(\kappa\sqrt{n}\log(1/\epsilon))$ IFO calls to achieve an
$\epsilon$-suboptimal solution $\hat{\bf{x}}$ of the problem. We consider the
vector ${\bf{x}}\in{\mathbb{R}}^{nTt}$ achieved by an IFO algorithm with at
most $\lfloor nTt/4\rfloor$ IFO calls. The zero-chain property of $g_{Tt}$
(statement (a) of Lemma 3.1) means the vector ${\bf{x}}$ has at most $\lfloor
nTt/4\rfloor$ non-zero entries. We partition ${\bf{x}}\in{\mathbb{R}}^{nTt}$
into $n$ vectors ${\bf{y}}^{(1)},\dots,{\bf{y}}^{(n)}\in{\mathbb{R}}^{Tt}$
such that ${\bf{y}}^{(i)}={\bf U}^{(i)}{\bf{x}}\in{\mathbb{R}}^{Tt}$. Then
there at least $\lceil n/2\rceil$ vectors in $\\{{\bf{y}}^{(i)}\\}_{i=1}^{n}$
such that each of them has at least $Tt/2$ zero entries. The zero-chain
property means there exists index set ${\mathcal{I}}\subseteq[n]$ with
$|{\mathcal{I}}|\geq\lceil n/2\rceil$ such that each $i\in{\mathcal{I}}$
satisfies $y^{(i)}_{Tt/2+1}=\dots=y^{(i)}_{Tt}=0$. Therefor, the statement (e)
of Lemma 3.1 implies

$\displaystyle f_{i}({\bf{x}})-\alpha g_{T,t}^{*}$ $\displaystyle>2\epsilon,$

which leads to

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}})-f^{*}=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}})-\alpha g_{T,t}^{*}$
$\displaystyle\geq$
$\displaystyle\frac{1}{n}\sum_{i\in{\mathcal{I}}}(f_{i}({\bf{x}})-\alpha
g_{T,t}^{*})$ $\displaystyle>$
$\displaystyle\frac{1}{n}\cdot\lceil\frac{n}{2}\rceil\cdot 2\epsilon$
$\displaystyle\geq$ $\displaystyle\epsilon.$

Hence, finding an $\epsilon$-suboptimal solution of the problem requires at
least $\lfloor nTt/4\rfloor+1=\Omega(\kappa\sqrt{n}\log(1/\epsilon))$ IFO
calls. ∎

###  A.4 The Proof of Theorem 3.5

###### Proof.

We prove this theorem by following Li et al. [32, Theorem 2]. For any
$i\in[n]$, we define $f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}$ as

$\displaystyle
f_{i}({\bf{x}})=c\left<\mathbf{u}_{i},{\bf{x}}\right>+\frac{L}{2}\|{\bf{x}}\|^{2},$

where

$\displaystyle c=\sqrt{L\Delta},\qquad
d=2n^{2},\qquad\mathbf{u}_{i}=\Big{[}{\mathbb{I}}\Big{(}\Big{\lceil}\frac{1}{2n}\Big{\rceil}=i\Big{)},{\mathbb{I}}\Big{(}\Big{\lceil}\frac{2}{2n}\Big{\rceil}=i\Big{)}\cdots,{\mathbb{I}}\Big{(}\Big{\lceil}\frac{2n^{2}}{2n}\Big{\rceil}=i\Big{)}\Big{]}^{\top}\in\mathbb{R}^{d}$

and ${\mathbb{I}}(\cdot)$ is the indicator function.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{d}$, we have

$\displaystyle\nabla f_{i}({\bf{x}})=c{\bf{u}}_{i}+L{\bf{x}}$

for any $i\in[n]$, which implies

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\|(c\mathbf{u}_{i}+L{\bf{x}})-(c\mathbf{u}_{i}+L{\bf{y}})\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\|L({\bf{x}}-{\bf{y}})\|^{2}$
$\displaystyle=L^{2}\|{\bf{x}}-{\bf{y}}\|^{2}.$

Hence, we conclude $\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ is
$L$-mean-squared smooth.

We also have $\nabla^{2}f({\bf{x}})=L{\bf I}\succeq\mu{\bf I}$ for any
${\bf{x}}\in{\mathbb{R}}^{d}$. Hence, the function $\nabla^{2}f({\bf{x}})$ is
$\mu$-strongly convex, also is $\mu$-PL.

We have

$\displaystyle f^{*}=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(c\langle\mathbf{u}_{i},{\bf{x}}^{*}\rangle+\frac{L}{2}\|{\bf{x}}^{*}\|^{2}\right)$
$\displaystyle=$
$\displaystyle\frac{c}{n}\sum_{i=1}^{n}\langle\mathbf{u}_{i},{\bf{x}}^{*}\rangle+\frac{L}{2}\|{\bf{x}}^{*}\|^{2}$
$\displaystyle=$
$\displaystyle-\frac{c^{2}}{2Ln^{2}}\bigg{\|}\sum_{i=1}^{n}\mathbf{u}_{i}\bigg{\|}^{2}$
$\displaystyle=$ $\displaystyle-\frac{c^{2}}{L},$

where ${\bf{x}}^{*}=-({c}/{Ln}){\bf{1}}$ is the minima of
$f:{\mathbb{R}}^{d}\to{\mathbb{R}}$. Then the optimal function value gap holds

$\displaystyle f({\bf{x}}^{0})-f^{*}=0-f^{*}=\frac{c^{2}}{L}=\Delta.$

We consider any IFO algorithm with initial point ${\bf{x}}^{0}={\bf{0}}$.
After $t$ IFO calls, Definition 2.8 implies

$\displaystyle{\bf{x}}^{t}\in{\rm Lin}\big{(}\\{\nabla
f_{i_{0}}({\bf{x}}^{0}),\dots,\nabla
f_{i_{t-1}}({\bf{x}}^{t-1})\\}\big{)}={\rm
Lin}\big{(}\\{{\bf{u}}_{i_{0}},\dots,{\bf{u}}_{i_{t-1}}\\}\big{)},$

where $i_{\tau}\in[n]$ is the index of individual which is accessed at the
$\tau$-th IFO calls. Since each ${\bf{u}}_{i_{\tau}}$ has $2n$ nonzero
entries, any vector ${\bf{x}}\in{\mathbb{R}}^{d}$ achieved by at most $n/2$
IFO calls has at least

$\displaystyle d-\frac{n}{2}\cdot 2n=2n^{2}-n^{2}=n^{2}$

zero entries. Let ${\mathcal{I}}_{0}=\\{j\in[2n^{2}]:x_{j}=0\\}$, then we have
$|{\mathcal{I}}|\geq n^{2}$. Based on the construction of $f_{i}$ and
${\bf{u}}_{i}$, we have

$\displaystyle f({\bf{x}})-f^{*}=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(c\langle{\bf{u}}_{i},{\bf{x}}\rangle+\frac{L}{2}\left\|{\bf{x}}\right\|_{2}\right)-\left(-\frac{c^{2}}{L}\right)$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{2n^{2}}\left(\frac{c}{n}x_{j}+\frac{L}{2}x_{j}^{2}+\frac{c^{2}}{2Ln^{2}}\right)$
$\displaystyle=$
$\displaystyle\sum_{j\in{\mathcal{I}}_{0}}\left(\frac{c}{n}x_{j}+\frac{L}{2}x_{j}^{2}+\frac{c^{2}}{2Ln^{2}}\right)+\sum_{j\not\in{\mathcal{I}}_{0}}\left(\frac{c}{n}x_{j}+\frac{L}{2}x_{j}^{2}+\frac{c^{2}}{2Ln^{2}}\right)$
$\displaystyle\geq$ $\displaystyle
n^{2}\cdot\frac{c^{2}}{2Ln^{2}}+\sum_{j\not\in{\mathcal{I}}_{0}}\left(x_{j}+\frac{c}{nL}\right)^{2}$
$\displaystyle\geq$ $\displaystyle\frac{\Delta}{2}>\epsilon,$

Hence, achieving an $\epsilon$-suboptimal solution requires at least
$n/2+1=\Omega(n)$ IFO calls. ∎

###  A.5 The Proof of Corollary 3.6

###### Proof.

This result can be achieved by directly combining Theorem 3.4 and 3.5. ∎

##  Appendix B The Proofs for Section 4

Without loss of generality, we always assume that all agents start with the
internal memory of null space, i.e., we have
$\mathcal{M}_{i}^{0}=\left\\{\mathbf{0}\right\\}$ for any $i\in[n]$.

The main idea in our lower bound analysis splitting the function
$g_{T,t}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ defined in equation (5) by
introducing the functions $q_{1}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$,
$q_{2}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ and
$r:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ as

$\displaystyle
q_{1}({\bf{x}})=\frac{1}{2}\sum_{i=1}^{Tt/2}(x_{2i-1}-x_{2i})^{2},$ (6)
$\displaystyle
q_{2}({\bf{x}})=\frac{1}{2}\sum_{i=0}^{t-1}\left[\Big{(}\frac{7}{8}x_{iT}-x_{iT+1}\Big{)}^{2}+\sum_{j=iT/2+1}^{(i+1)T/2-1}(x_{2j}-x_{2j+1})^{2}\right],$
(7) $\displaystyle r({\bf{x}})=\sum_{i=1}^{Tt}\psi_{b_{i}}(b_{i}-x_{i}),$ (8)

where we suppose $T$ is even and let $x_{0}=0$. Then we can verify that the
function $g_{T,t}(\cdot)$ can be written as

$\displaystyle
g_{T,t}({\bf{x}})=q_{1}({\bf{b}}-{\bf{x}})+q_{2}({\bf{b}}-{\bf{x}})+r({\bf{x}}).$

We let ${\mathcal{G}}=\\{{\mathcal{V}},{\mathcal{E}}\\}$ be the graph
associated to the network of the agents in decentralized optimization, where
the node set ${\mathcal{V}}=\\{1,\dots,n\\}$ corresponds to the $n$ agents and
the edge set ${\mathcal{E}}=\\{(i,j):\text{node $i$ and node $j$ are
connected}\\}$ describes the topology of the agents network.

For given a subset ${\mathcal{C}}\subseteq\mathcal{V}$, we define the function
$h_{i}^{\mathcal{C}}({\bf{x}}):{\mathbb{R}}^{Tt}\rightarrow{\mathbb{R}}$ as

$\displaystyle
h_{i}^{\mathcal{C}}({\bf{x}})=\begin{cases}\frac{r({\bf{x}})}{n}+\frac{q_{1}({\bf{b}}-{\bf{x}})}{|{\mathcal{C}}|}&{i\in{\mathcal{C}}},\\\\[1.99997pt]
\frac{r({\bf{x}})}{n}+\frac{q_{2}({\bf{b}}-{\bf{x}})}{|{\mathcal{C}}_{\sigma}|}&{i\in{\mathcal{C}}_{\sigma}},\\\\[1.99997pt]
\frac{r({\bf{x}})}{n},&{\text{otherwise}},\\\ \end{cases}$ (9)

where ${\mathcal{C}}_{\sigma}=\left\\{v\in\mathcal{V}:{\rm
dis}({\mathcal{C}},v)\geq\sigma\right\\}$ and ${\rm dis}({\mathcal{C}},v)$ is
the distance between set ${\mathcal{C}}$ and node $v$.

We introduce the following property [61, Lemma 4] of function
$\psi_{\theta}:{\mathbb{R}}\to{\mathbb{R}}$ to analyze the smoothness of
$h_{i}^{\mathcal{C}}(\cdot)$ and the communication complexity for hard
instance.

######  Lemma B.1.

For any $\theta>0$, the function $\psi_{\theta}:{\mathbb{R}}\to{\mathbb{R}}$
defined in equation (4) is 33-smooth and holds
$\psi_{\theta}^{\prime}(\theta)=0$.

Now we present the proofs for lower bounds in decentralized setting, which is
based on our construction (6)–(8).

###  B.1 Proof of Lemma 4.1

###### Proof.

We can observed that the function $q_{1}({\bf{x}})$ is quadratic and holds
$q_{1}({\bf{x}})\leq 1$ for any ${\bf{x}}\in{\mathbb{R}}^{Tt}$, then it is
$2$-smooth. Similarly, the function $q_{2}({\bf{x}})$ is also $2$-smooth.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{Tt}$, we have

$\begin{split}\left\|\nabla r({\bf{x}})-\nabla
r({\bf{y}})\right\|^{2}&=\sum_{i=1}^{Tt}\left(v^{\prime}_{b_{i}}(b_{i}-x_{i})-v^{\prime}_{b_{i}}(b_{i}-y_{i})\right)^{2}\\\
&\leq\sum_{i=1}^{Tt}\left(33(x_{i}-y_{i})\right)^{2}\\\
&=33^{2}\left\|{\bf{x}}-{\bf{y}}\right\|^{2},\\\ \end{split}$

where inequality is based on the Lemma B.1. This implies the function
$r:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ is 33-smooth.

Combing above smoothness properties and the definition of
$h_{i}^{\mathcal{C}}(\cdot)$, we conclude each $h_{i}^{\mathcal{C}}$ is
$(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-smooth
and thus
$\big{\\{}h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\big{\\}}_{i=1}^{n}$
is
$(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-mean-
squared smooth.

The definition of $h(\cdot)$ and $h_{i}^{\mathcal{C}}(\cdot)$ implies

$\displaystyle
h({\bf{x}})=\frac{1}{n}\sum_{i=1}^{n}h_{i}^{\mathcal{C}}({\bf{x}})=\frac{q_{1}({\bf{b}}-{\bf{x}})+q_{2}({\bf{b}}-{\bf{x}})+r({\bf{x}})}{n}=\frac{g_{T,t}({\bf{x}})}{n}.$
(10)

Then applying statements (c) and (d) of Lemma 3.1 and Lemma 3.3 finish the
proof for the last two statements. ∎

###  B.2 Proof of Lemma 4.2

###### Proof.

The definitions $f_{i}({\bf{x}})=\alpha h_{i}^{\mathcal{C}}(\beta{\bf{x}})$
and $f({\bf{x}})=\frac{1}{n}\sum_{i=1}^{n}f_{i}({\bf{x}})$ and equation (10)
implies $f({\bf{x}})=\alpha g_{T,t}(\beta{\bf{x}})/n$. Then the statement (e)
of Lemma 3.1 implies when
$\text{supp}({\bf{x}})\subseteq\left\\{1,2,\cdots,Tt/2\right\\}$, we have

$\displaystyle
f({\bf{x}})-f^{*}=\frac{\alpha}{n}(g_{T,t}(\beta{\bf{x}})-g_{T,t}^{*})>\frac{3\alpha
T\delta}{n},$ (11)

since we have assumed $\delta<0.01$ and
$t=2\lfloor\log_{{8}/{7}}({2}/{3\delta})\rfloor$.

We define

$\displaystyle{\rm nnz}(s,i)\triangleq\max\left\\{m\in{\mathbb{N}}:\text{there
exists ${\bf{y}}\in\mathcal{M}_{i}^{s}$ such that $y_{m}\neq 0$}\right\\}.$

Then statements (a) of Lemma 3.1 implies achieving an $3\alpha
T\delta/n$-suboptimal solution requires

$\displaystyle\mathop{\max}_{i\in[n]}\left\\{{\rm
nnz}(s,i)\right\\}\geq\frac{Tt}{2}+1.$ (12)

Now we consider how much local computation steps and local communication steps
we need to attain the condition (12).

According to Lemma B.1 and equation (8), for any
${\bf{x}}\in\mathcal{M}_{i}^{s}$, we have

$(\nabla r({\bf{x}}))_{k}=0,\qquad\text{for any}\quad k>{\rm nnz}(s,i).$ (13)

According to equation (6), for any ${\bf{x}}\in\mathcal{M}_{i}^{s}$, we have

$(\nabla q_{1}({\bf{b}}-{\bf{x}}))_{k}=0,\qquad\text{for any}\quad k>{\rm
nnz}(s,i)+{\mathbb{I}}\left\\{{\rm nnz}(s,i)\equiv 1\pmod{2}\right\\}.$ (14)

According to equation (7), for any ${\bf{x}}\in\mathcal{M}_{i}^{s}$, we have

$(\nabla q_{2}({\bf{b}}-{\bf{x}}))_{k}=0,\qquad\text{for any}\quad k>{\rm
nnz}(s,i)+{\mathbb{I}}\left\\{{\rm nnz}(s,i)\equiv 0\pmod{2}\right\\}.$ (15)

Combining (9), (13), (14), (15) and Definition 2.10, we know that for any DFO
algorithm:

  1. 1.

If $i\in{\mathcal{C}}$ and ${\rm nnz}(s,i)$ is odd, one step of local
computation can increase at most one dimension for memory of node $i$.

  2. 2.

If $i\in{\mathcal{C}}_{\sigma}$ and ${\rm nnz}(s,i)$ is even, one step of
local computation can increase at most one dimension for memory of node $i$.

  3. 3.

Otherwise, one step of local computation cannot increase the dimension for
memory of node $i$.

In summary, we have

$\displaystyle{\rm nnz}(s+1,i)\leq\begin{cases}{\rm
nnz}(s,i)+1,&\text{if}~{}~{}i\in{\mathcal{C}},\ {\rm nnz}(s,i)\equiv
1\pmod{2},\\\ {\rm nnz}(s,i)+1,&\text{if}~{}~{}i\in{\mathcal{C}}_{\sigma},\
{\rm nnz}(s,i)\equiv 0\pmod{2},\\\ {\rm
nnz}(s,i),&\text{otherwise}.\end{cases}$ (16)

We consider the cost to reach the second coordinate from the initial status
that ${\mathcal{M}}_{i}^{0}=\\{{\bf{0}}\\}$ for all $i\in[n]$. According to
equation (16), we need to let a node in ${\mathcal{C}}$ reach the first
coordinate, which requires at least one local computation step on some node in
${\mathcal{C}}_{\sigma}$ first. Then, according to definitions of DFO
algorithm (Definition 2.10) and ${\mathcal{C}}_{\sigma}$, one must perform at
least $\sigma$ local communication steps for a node in ${\mathcal{C}}$ to
receive the information of the first coordinate from some node in
${\mathcal{C}}_{\sigma}$. After above steps, we can perform at least 1
computation on nodes in ${\mathcal{C}}$ to reach the second coordinate. In
summary, to reach the second coordinate requires at least 2 local computation
step and $\sigma$ local communication step.

Similarly, to reach the $k$-th coordinate, a DFO algorithm must perform at
least $k$ local computation steps and $(k-1)\sigma$ local communication steps.
Thus, to attain the condition (12), one needs at least $Tt/2+1$ local
computation steps and $Tt\sigma/2$ local communication steps, which
corresponds to $Tt\sigma/2$ communications round and $Tt(1+\sigma\tau)/2$ time
cost. ∎

######  Remark B.2.

Noticing that one computation step corresponds to one unit of time cost.
However, some of agents (maybe not all agents) can parallel compute their
local gradient, which means the computational time cost may be not proportion
to the number of local gradient oracle calls.

###  B.3 Proof of Theorem 4.3

###### Proof.

We consider the instance graph provided by Scaman et al. [50], which
associated to the specific spectral gap. Concretely, we let
$\iota_{m}=\left(1-\cos({\pi}/{m})\right)/\left(1+\cos({\pi}/{m})\right)$. For
given $\gamma\in(0,1]$, let
$m=\big{\lfloor}{\pi}/{\arccos{{((1-\gamma)}/{(1+\gamma))}}}\big{\rfloor}$,
then we have $m\geq 2$ and $\iota_{m+1}<\gamma\leq\iota_{m}$. We study the
cases of $m\geq 3$ and $m=2$ separately.

We first consider the case of $m\geq 3$. Let the agent number $n=m$, take
$\mathcal{G}=\\{{\mathcal{V}},{\mathcal{E}}\\}$ be the undirected linear graph
of size $n$ ordered from node $1$ to node $n$ such that
${\mathcal{V}}=\\{1,\dots,n\\}$ and
${\mathcal{E}}=\\{(i,j):|i-j|=1,i\in{\mathcal{V}}~{}~{}\text{and}~{}~{}j\in{\mathcal{V}}\\}$.
We define a weighted matrix $\hat{\bf W}_{l}\in{\mathbb{R}}^{n\times n}$ for
${\mathcal{G}}$ such that
$\hat{w}_{i+1,i}=\hat{w}_{i,i+1}=1-l{\mathbb{I}}(i=1)$ and $\hat{w}_{ij}=0$
for other entries. Let $\hat{\bf R}_{l}\in{\mathbb{R}}^{n\times n}$ be the
Laplacian matrix of graph $\mathcal{G}$ associated to weighted matrix
$\hat{\bf W}_{l}$. We define $\lambda_{1}(\hat{\bf
R}_{l}),\dots,\lambda_{n}(\hat{\bf R}_{l})$ be eigenvalues of $\hat{\bf
R}_{l}$ such that $0=\lambda_{n}(\hat{\bf R}_{l})\leq\lambda_{n-1}(\hat{\bf
R}_{l})\leq\cdots\leq\lambda_{1}(\hat{\bf R}_{l})$. A simple calculation gives
that

$\displaystyle\lambda_{n-1}(\hat{\bf
R}_{0})=2\left(1-\cos({\pi}/{m})\right),\quad\lambda_{1}(\hat{\bf
R}_{0})=2\left(1+\cos({\pi}/{m})\right),\quad\lambda_{n-1}(\hat{\bf
R}_{1})=0\qquad\text{and}\qquad\lambda_{1}(\hat{\bf R}_{l})>0$

for any $l\in[0,1]$, then we have $\lambda_{n-1}(\hat{\bf
R}_{0})/\lambda_{1}(\hat{\bf R}_{0})=\iota_{m}$ and $\lambda_{n-1}(\hat{\bf
R}_{1})/\lambda_{1}(\hat{\bf R}_{1})=0$. By the continuity of the eigenvalues
of a matrix and the fact $0<\gamma\leq\iota_{m}$, there exists some
$l\in\left[0,1\right)$ such that $\lambda_{n-1}(\hat{\bf
R}_{l})/\lambda_{1}(\hat{\bf R}_{l})=\gamma$. Let ${\bf W}=1-\hat{\bf
R}_{l}/\lambda_{1}(\hat{\bf R}_{l})$, then the spectral gap satisfies
$\gamma({\bf W})=\lambda_{n-1}(\hat{\bf R}_{l})/\lambda_{1}(\hat{\bf
R}_{l})=\gamma$. According to basic properties of Laplacian matrix, the matrix
${\bf W}\in{\mathbb{R}}^{n\times n}$ is a mixing matrix satisfies Assumption
2.6.

We take
$\left\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$
by following equation (9) with

$\displaystyle{\mathcal{C}}=\left\\{1,\dots,\left\lceil\frac{n}{32}\right\rceil\right\\},\qquad\sigma=\left\lceil\frac{15n}{16}\right\rceil-1,\qquad
T=2\left\lfloor\frac{\kappa}{194a}\right\rfloor\qquad\text{and}\qquad
t=2\left\lfloor\log_{\frac{8}{7}}\frac{2\Delta}{3\epsilon}\right\rfloor.$

Let $h(\cdot)=\frac{1}{n}\sum_{i=1}^{n}h_{i}^{\mathcal{C}}(\cdot)$. Lemma 4.1
means the function set
$\left\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$
is
$(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-mean-
squared smooth, and the function $h$ is $1/\left(anT\right)$-PL and satisfies

$\displaystyle h(\mathbf{0})-h^{*}\leq\frac{3T}{n}.$

Let $f_{i}({\bf{x}})=\alpha h_{i}^{\mathcal{C}}(\beta{\bf{x}})$,
$f({\bf{x}})=\sum_{i=1}^{n}f_{i}({\bf{x}})/n$ and apply Lemma 3.3 with
$\alpha=n\Delta/(3T)$ and $\beta=\sqrt{3LT/(97\Delta)}$, then the function set
$\left\\{f_{i}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$ is
$\alpha\beta^{2}(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-mean-
squared smooth, and the function $f:{\mathbb{R}}^{Tt}\to{\mathbb{R}}$ is
$\alpha\beta^{2}/\left(anT\right)$-PL and satisfies

$\displaystyle f(\mathbf{0})-f^{*}\leq\frac{3\alpha T}{n}.$

The values of $\alpha$ and $\beta$ means

$\displaystyle\alpha\beta^{2}\left(\frac{33}{n}+\frac{2}{|{\mathcal{C}}_{\sigma}|}\right)\leq\alpha\beta^{2}\left(\frac{33}{n}+\frac{2}{|{\mathcal{C}}|}\right)\leq\frac{nL}{97}\left(\frac{33}{n}+\frac{64}{n}\right)=L,$
$\displaystyle\frac{\alpha\beta^{2}}{anT}=\frac{L}{97aT}\geq\mu\qquad\text{and}\qquad\frac{3\alpha
T}{n}=\Delta.$

According to Lemma 3.3 and Lemma 4.1, we conclude
$\left\\{f_{i}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$ is
$L$-mean-squared smooth and $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $\mu$-PL
with $f(\mathbf{0})-f^{*}\leq\Delta$.

Applying Lemma 4.2 with $\delta=\epsilon/\Delta<0.01$, any DFO algorithm needs
at least $Tt\sigma/2$ communication steps and $Tt(1+\sigma\tau)/2$ time cost
to achieve an $\epsilon$-suboptimal solution since $3\alpha
T\delta/n=\epsilon$. The setting $n=m$ implies

$\displaystyle\frac{2}{(n+1)^{2}}\leq\iota_{n+1}<\gamma\leq\iota_{3}=\frac{1}{3},$

which means

$\displaystyle\sigma=\left\lceil\frac{15n}{16}\right\rceil-1\geq\frac{15}{16}\left(\sqrt{\frac{2}{\gamma}}-1\right)-1\geq\frac{1}{5\sqrt{\gamma}}.$

Hence, we achieve the lower bounds for communication complexity and time
complexity of
$Tt\tau/2=\Omega\big{(}\kappa/\sqrt{\gamma}\log(1/\epsilon)\big{)}$ and
$Tt(1+\sigma\tau)/2=\Omega\big{(}\kappa(1+\tau/\sqrt{\gamma})\log(1/\epsilon)\big{)}$
respectively.

We then consider the case of $m=2$. We let the agent number be $n=3$ and take
$\mathcal{G}=\\{{\mathcal{V}},{\mathcal{E}}\\}$ be the totally connected graph
of size $n$ such that ${\mathcal{V}}=\\{1,\dots,n\\}$ and
${\mathcal{E}}=\\{(i,j):i\in{\mathcal{V}}~{}~{}\text{and}~{}~{}j\in{\mathcal{V}}\\}$.
We define a weighted matrix $\hat{\bf W}_{l}\in{\mathbb{R}}^{n\times n}$ for
${\mathcal{G}}$ such that $\hat{w}_{1,3}=\hat{w}_{3,1}=l$ and $w_{ij}=1$ for
other entries. Let $\hat{\bf R}_{l}\in{\mathbb{R}}^{n\times n}$ be the
Laplacian matrix of graph $\mathcal{G}$ associated to weighted matrix
$\hat{\bf W}_{l}$. We define $\lambda_{1}(\hat{\bf
R}_{l}),\dots,\lambda_{n}(\hat{\bf R}_{l})$ be eigenvalues of $\hat{\bf
R}_{l}$ such that $0=\lambda_{n}(\hat{\bf R}_{l})\leq\lambda_{n-1}(\hat{\bf
R}_{l})\leq\cdots\leq\lambda_{1}(\hat{\bf R}_{l})$. A simple calculation gives
that

$\displaystyle\lambda_{n-1}(\hat{\bf R}_{1})=\lambda_{1}(\hat{\bf
R}_{1})=3,\quad\lambda_{n-1}(\hat{\bf
R}_{0})=2\left(1-\cos({\pi}/{n})\right),\quad\lambda_{1}(\hat{\bf
R}_{0})=2\left(1+\cos({\pi}/{n})\right)\quad\text{and}\quad\lambda_{1}(\hat{\bf
R}_{l})>0$

for any $l\in[0,1]$. Then we have $\lambda_{n-1}(\hat{\bf
R}_{0})/\lambda_{1}(\hat{\bf R}_{0})=\iota_{n}=\iota_{3}$ and
$\lambda_{n-1}(\hat{\bf R}_{1})/\lambda_{1}(\hat{\bf R}_{1})=1$. By continuity
of the eigenvalues of a matrix and the fact $\iota_{3}<\gamma\leq 1$, there
exists some $l\in\left(0,1\right]$ such that $\lambda_{n-1}(\hat{\bf
R}_{l})/\lambda_{1}(\hat{\bf R}_{l})=\gamma$. Let ${\bf W}=1-\hat{\bf
R}_{l}/\lambda_{1}(\hat{\bf R}_{l})$, then the spectral gap satisfies
$\gamma({\bf W})=\lambda_{n-1}(\hat{\bf R}_{l})/\lambda_{1}(\hat{\bf
R}_{l})=\gamma$. According to basic properties of Laplacian matrix, the matrix
${\bf W}\in{\mathbb{R}}^{n\times n}$ is a mixing matrix satisfies Assumption
2.6.

We take
$\left\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$
by following equation (9) with

$\displaystyle{\mathcal{C}}=\left\\{1\right\\},\qquad\sigma=1,\qquad
T=2\left\lfloor\frac{\kappa}{78a}\right\rfloor\qquad\text{and}\qquad
t=2\left\lfloor\log_{\frac{8}{7}}\frac{2\Delta}{3\epsilon}\right\rfloor.$

Let $h(\cdot)=\frac{1}{n}\sum_{i=1}^{n}h_{i}^{\mathcal{C}}(\cdot)$. Lemma 4.1
means the function set
$\left\\{h_{i}^{\mathcal{C}}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$
is
$(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-mean-
squared smooth, $h$ is $1/\left(anT\right)$-PL and satisfies

$\displaystyle h(\mathbf{0})-h^{*}\leq 3T/n.$

Let $f_{i}({\bf{x}})=\alpha h_{i}^{\mathcal{C}}(\beta{\bf{x}})$,
$f({\bf{x}})=\sum_{i=1}^{n}f_{i}({\bf{x}})/n$ and apply Lemma 3.3 with
$\alpha=n\Delta/(3T)$ and $\beta=\sqrt{LT/(13\Delta)}$, then we conclude
$\left\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\right\\}_{i=1}^{n}$ is
$\alpha\beta^{2}(33/n+\max\left\\{2/|{\mathcal{C}}|,2/|{\mathcal{C}}_{\sigma}|\right\\})$-mean-
squared smooth and $f$ is $\alpha\beta^{2}/\left(anT\right)$-PL and satisfies

$\displaystyle f(\mathbf{0})-f^{*}\leq\frac{3\alpha T}{n}.$

The values of $\alpha$ and $\beta$ means

$\displaystyle\alpha\beta^{2}\left(\frac{33}{n}+\frac{2}{|{\mathcal{C}}_{\sigma}|}\right)<\alpha\beta^{2}\left(\frac{33}{n}+\frac{2}{|{\mathcal{C}}|}\right)=\frac{nL}{39}\left(\frac{33}{n}+\frac{6}{n}\right)=L,\qquad\frac{\alpha\beta^{2}}{anT}=\frac{L}{39aT}\geq\mu\qquad\text{and}\qquad\frac{3\alpha
T}{n}=\Delta.$

According to Lemma 3.3 and Lemma 4.1, we conclude
$\left\\{f_{i}:{\mathbb{R}}^{Tt}\to{\mathbb{R}}\right\\}_{i=1}^{n}$ is
$L$-mean-squared smooth, and $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $\mu$-PL
with $f(\mathbf{0})-f^{*}\leq\Delta$.

Applying Lemma 4.2 with $\delta=\epsilon/\Delta<0.01$, any DFO algorithm needs
at least $Tt\sigma/2$ communications and $Tt(1+\sigma\tau)/2$ time to reach an
$\epsilon$-suboptimal solution since $3\alpha T\delta/n=\epsilon$. The setting
$n=3$ means $\gamma>\iota_{3}=1/3$ and $\sigma=1>1/\sqrt{3\gamma}$, which
results the lower bounds for communication complexity and time complexity of
$Tt\tau/2=\Omega\big{(}\kappa/\sqrt{\gamma}\log(1/\epsilon)\big{)}$ and
$Tt(1+\sigma\tau)/2=\Omega\big{(}\kappa(1+\tau/\sqrt{\gamma})\log(1/\epsilon)\big{)}$
respectively.

∎

##  Appendix C The Proofs in Section 5

Recall that we define the Lyapunov function

$\displaystyle\Phi^{t}=\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\alpha
U^{t}+\beta V^{t}+LC^{t},$

where $\alpha=2\eta/p$, $\beta=8L\rho^{2}n\eta^{2}$,

$\displaystyle
U^{t}=\mathbb{E}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\big{(}{\bf{g}}^{t}(i)-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2},~{}~{}V^{t}=\frac{1}{n}\mathbb{E}\|{\bf
G}^{t}-\nabla{\bf F}({\bf
X}^{t})\|^{2}~{}~{}\text{and}~{}~{}C^{t}={\mathbb{E}}\|{\bf
X}^{t}-\mathbf{1}{{\bar{\bf{x}}}}^{t}\|^{2}+\eta^{2}\mathbb{E}\|{\bf
S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}.$

Compared with the analysis of Luo and Ye [36], Li et al. [29] for general
nonconvex case, we introduce the term of $f^{*}$ into the Lyapunov function to
show the linear convergence under the PL condition. Different with previous
work [36, 29] suppose each $f_{i}(\cdot)$ is $L$-smooth, our analysis only
require $\\{f_{i}(\cdot)\\}_{i=1}^{n}$ is $L$-smooth that allows each
$f_{i}(\cdot)$ to be $\sqrt{n}L$-smooth (see Lemma C.3).

The remainder of this section first provide some technical Lemmas, then give
the detailed proofs for the results in Section 4.

###  C.1 Some Technical Lemmas

We introduce some lemmas for our later analysis.

######  Lemma C.1 (Ye et al. [58, Proposition 1]).

Under Assumption 2.6, Algorithm 2 holds

$\displaystyle\frac{1}{n}{\bf{1}}^{\top}{\bf
Y}^{K}=\bar{\bf{y}}^{0}\qquad\text{and}\qquad\big{\|}{\bf
Y}^{K}-\mathbf{1}\bar{\bf{y}}^{0}\big{\|}\leq\sqrt{14}\left(1-\left(1-\frac{1}{\sqrt{2}}\right)\sqrt{1-\lambda_{2}({\bf
W})}\right)^{K}\big{\|}{\bf Y}^{0}-\mathbf{1}\bar{\bf{y}}^{0}\big{\|},$

where $\bar{\bf{y}}^{0}=\frac{1}{n}\mathbf{1}^{\top}{\bf
Y}^{0}=\frac{1}{n}\sum_{i=1}^{n}{\bf Y}^{0}(i)$.

######  Lemma C.2 ([58, Lemma 3]).

For any ${\bf X}\in{\mathbb{R}}^{n\times d}$, we have $\left\|{\bf
X}-{\bf{1}}{{\bar{\bf{x}}}}\right\|\leq\left\|{\bf X}\right\|$ where ${\bf
X}=\frac{1}{n}{\bf{1}}^{\top}{\bf X}$.

######  Lemma C.3.

Under Assumption 2.2, the function
$f(\cdot)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\cdot)$ is $L$-smooth and each
$f_{i}(\cdot)$ is $\sqrt{n}L$-smooth.

###### Proof.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{d}$, the mean-square smoothness of
$\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ implies

$\displaystyle\left\|\nabla f({\bf{x}})-\nabla f({\bf{y}})\right\|_{2}^{2}=$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}(\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}}))\right\|_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\right\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle
L\left\|{\bf{x}}-{\bf{y}}\right\|_{2}^{2},$

which means $f(\cdot)$ is $L$-smooth.

For any ${\bf{x}},{\bf{y}}\in{\mathbb{R}}^{d}$ and $i\in[n]$, the mean-square
smoothness of $\\{f_{i}:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}_{i=1}^{n}$ implies

$\displaystyle\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\|\leq\sqrt{\sum_{i=1}^{n}\left\|\nabla f_{i}({\bf{x}})-\nabla
f_{i}({\bf{y}})\right\|^{2}}\leq\sqrt{nL^{2}\left\|{\bf{x}}-{\bf{y}}\right\|^{2}}\leq\sqrt{n}L\left\|{\bf{x}}-{\bf{y}}\right\|,$

which means $f_{i}(\cdot)$ is $\sqrt{n}L$-smooth. ∎

######  Lemma C.4 (Li et al. [32, Lemma 2]).

Suppose the function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $L$-smooth and the
vectors ${\bf{x}}_{t},{\bf{x}}_{t+1},{\bf{v}}_{t}\in{\mathbb{R}}^{d}$ satisfy
${\bf{x}}_{t+1}={\bf{x}}_{t}-\eta{\bf{v}}_{t}$ for $\eta>0$. Then we have

$\displaystyle f({\bf{x}}_{t+1})\leq
f({\bf{x}}_{t})-\frac{\eta}{2}\left\|\nabla
f({\bf{x}}_{t})\right\|^{2}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\left\|{\bf{x}}_{t+1}-{\bf{x}}_{t}\right\|^{2}+\frac{\eta}{2}\left\|{\bf{v}}_{t}-\nabla
f({\bf{x}}_{t})\right\|^{2}.$ (17)

We establish the decrease of function value as follows.

######  Lemma C.5.

Under Assumption 2.1-2.6, Algorithm 4 holds that

$\displaystyle\mathbb{E}[f({{\bar{\bf{x}}}}^{t+1})-f^{*}]\leq(1-\mu\eta)\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\eta
U^{t}+L^{2}\eta
C^{t}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}.$

###### Proof.

Lemma C.1 and the update ${\bf X}^{t+1}={{\rm AccGossip}}({\bf X}^{t}-\eta{\bf
S}^{t},{\bf W},K)$ means

$\displaystyle\begin{split}{{\bar{\bf{x}}}}^{t+1}=&\frac{1}{n}{\bf{1}}^{\top}{{\rm
AccGossip}}({\bf X}^{t}-\eta{\bf S}^{t},{\bf W},K)\\\
=&\frac{1}{n}{\bf{1}}^{\top}({\bf X}^{t}-\eta{\bf S}^{t})\\\
=&{{\bar{\bf{x}}}}^{t}-\eta{{\bar{\bf{s}}}}^{t}.\end{split}$ (18)

Lemma C.3 shows the function $f(\cdot)$ is $L$-smooth, then Lemma C.4 with
${\bf{x}}^{t}={{\bar{\bf{x}}}}^{t}$, ${\bf{x}}^{t+1}={{\bar{\bf{x}}}}^{t+1}$
and ${\bf{v}}^{t}={{\bar{\bf{s}}}}^{t}$ means

$\displaystyle\begin{split}f({{\bar{\bf{x}}}}^{t+1})\leq
f({{\bar{\bf{x}}}}^{t})-\frac{\eta}{2}\left\|\nabla
f({{\bar{\bf{x}}}}^{t})\right\|^{2}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}+\frac{\eta}{2}\left\|{{\bar{\bf{s}}}}^{t}-\nabla
f({{\bar{\bf{x}}}}^{t})\right\|^{2}.\end{split}$ (19)

We also have

$\displaystyle{\mathbb{E}}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}\nabla
f_{i}({\bf{x}}^{t}(i))-\nabla
f_{i}({{\bar{\bf{x}}}}^{t})\big{)}\right\|^{2}\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}\left\|\nabla
f_{i}({\bf{x}}^{t}(i))-\nabla f_{i}({{\bar{\bf{x}}}}^{t})\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{m}nL^{2}{\mathbb{E}}\left\|{\bf{x}}^{t}(i)-{{\bar{\bf{x}}}}^{t}\right\|^{2}$
$\displaystyle=$ $\displaystyle
L^{2}{\mathbb{E}}\left\|{\bf{x}}^{t}-{\bf{1}}{{\bar{\bf{x}}}}^{t}\right\|^{2}\leq
L^{2}C^{t},$

where we use the inequality
$\left\|\frac{1}{n}\sum_{i=1}^{n}{\bf{a}}_{i}\right\|^{2}\leq\frac{1}{n}\sum_{i=1}^{n}\left\|{\bf{a}}_{i}\right\|^{2}$
for ${\bf{a}}_{1},\dots,{\bf{a}}_{n}\in{\mathbb{R}}^{d}$ and Lemma C.3.
Consequently, we have

$\displaystyle\begin{split}{\mathbb{E}}\left\|{{\bar{\bf{s}}}}^{t}-\nabla
f({{\bar{\bf{x}}}}^{t})\right\|^{2}=&{\mathbb{E}}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}{\bf{g}}^{t}(i)-\nabla
f_{i}({{\bar{\bf{x}}}}^{t})\big{)}\right\|^{2}\\\
\leq&2{\mathbb{E}}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}{\bf{g}}^{t}(i)-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\right\|^{2}+2{\mathbb{E}}\left\|\frac{1}{n}\sum_{i=1}^{n}\big{(}\nabla
f_{i}({\bf{x}}^{t}(i))-\nabla
f_{i}({{\bar{\bf{x}}}}^{t})\big{)}\right\|^{2}\\\
\leq&2U^{t}+2L^{2}C^{t}.\end{split}$ (20)

Combining the results of (19) and (20), we have

$\displaystyle{\mathbb{E}}[f({{\bar{\bf{x}}}}^{t+1})-f^{*}]\leq$
$\displaystyle{\mathbb{E}}\left[f({{\bar{\bf{x}}}}^{t})-f^{*}-\frac{\eta}{2}\left\|\nabla
f({{\bar{\bf{x}}}}^{t})\right\|^{2}+\eta U^{t}+L^{2}\eta
C^{t}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle(1-\mu\eta)\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\eta
U^{t}+L^{2}\eta
C^{t}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2},$

where the last step is based on the PL condition in Assumption 2.3. ∎

Then we provide the recursion for $U_{t}$, $V_{t}$ and $C_{t}$ in the
following lemma.

######  Lemma C.6.

Under the setting of Theorem 5.2, we have

$\displaystyle C^{t+1}\leq
20\rho^{2}n^{2}C^{t}+4\rho^{2}np\eta^{2}V^{t}+12\rho^{2}n^{2}\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2},$
$\displaystyle
U^{t+1}\leq(1-p)U^{t}+4pL^{2}C^{t}+3pL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2},$

and

$\displaystyle
V^{t+1}\leq(1-p)V^{t}+4pnL^{2}C^{t}+3pnL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2},$

where
$\rho=\sqrt{14}\left(1-\big{(}1-{1}/{\sqrt{2}}\big{)}\sqrt{1-\lambda_{2}}\,\right)^{K}$.

###### Proof.

The setting Lemma C.1 implies

$\displaystyle\rho^{2}\leq\frac{1}{80n^{2}}\leq\frac{1}{80}.$ (21)

We first consider $C^{t+1}={\mathbb{E}}\|{\bf
X}^{t+1}-\mathbf{1}{{\bar{\bf{x}}}}^{t+1}\|^{2}+\eta^{2}\mathbb{E}\|{\bf
S}^{t+1}-\mathbf{1}{{\bar{\bf{s}}}}^{t+1}\|^{2}$. For the term
${\mathbb{E}}\|{\bf X}^{t+1}-\mathbf{1}{{\bar{\bf{x}}}}^{t+1}\|^{2}$, we have

$\displaystyle\begin{split}\mathbb{E}\|{\bf
X}^{t+1}-\mathbf{1}{{\bar{\bf{x}}}}^{t+1}\|^{2}&\leq\rho^{2}\mathbb{E}\|({\bf
X}^{t}-\eta{\bf
S}^{t})-\mathbf{1}({{\bar{\bf{x}}}}^{t}-\eta{{\bar{\bf{s}}}}^{t})\|^{2}\\\
&\leq 2\rho^{2}\big{(}\mathbb{E}\|{\bf
X}^{t}-\mathbf{1}{{\bar{\bf{x}}}}^{t}\|^{2}+\eta^{2}\mathbb{E}\|{\bf
S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}\big{)}\\\
&=2\rho^{2}C^{t},\end{split}$ (22)

where we use the definition of $\rho$ and Lemma C.1 in the first inequality
and Young’s inequality in the second inequality.

For the term $\eta^{2}\|{\bf S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}$, we
have

$\displaystyle\begin{split}\eta^{2}\mathbb{E}\|{\bf
S}^{t+1}-\mathbf{1}{{\bar{\bf{s}}}}^{t+1}\|^{2}\leq&\rho^{2}\eta^{2}\mathbb{E}\|{\bf
S}^{t}+{\bf G}^{t+1}-{\bf
G}^{t}-\mathbf{1}({{\bar{\bf{s}}}}^{t}+{{\bar{\bf{g}}}}^{t+1}-{{\bar{\bf{g}}}}^{t})\|^{2}\\\
\leq&2\rho^{2}\eta^{2}\mathbb{E}\|{\bf
S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}+2\rho^{2}\eta^{2}\mathbb{E}\|{\bf
G}^{t+1}-{\bf
G}^{t}-\mathbf{1}({{\bar{\bf{g}}}}^{t+1}-{{\bar{\bf{g}}}}^{t})\|^{2}\\\
\leq&2\rho^{2}\eta^{2}\mathbb{E}\|{\bf
S}^{t}-\mathbf{1}{{\bar{\bf{s}}}}^{t}\|^{2}+2\rho^{2}\eta^{2}\mathbb{E}\|{\bf
G}^{t+1}-{\bf G}^{t}\|^{2}\\\
\leq&2\rho^{2}C^{t}+2\rho^{2}\eta^{2}\mathbb{E}\|{\bf G}^{t+1}-{\bf
G}^{t}\|^{2},\\\ \end{split}$ (23)

where we use the definition of $\rho$ and Lemma C.1 in the first inequality,
Young’s inequality in the second inequality, Lemma C.2 in the third inequality
and definition of $C^{t}$ in the last inequality.

We bound the term $\|{\bf G}^{t+1}-{\bf G}^{t}\|^{2}$ in inequality (23) as

$\displaystyle\small\begin{split}&\mathbb{E}\|{\bf G}^{t+1}-{\bf
G}^{t}\|^{2}\\\ =&p\mathbb{E}\|\nabla{\bf F}({\bf X}^{t+1})-{\bf
G}^{t}\|^{2}+(1-p)\sum_{i=1}^{n}\mathbb{E}\Big{\|}\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2}\\\
\leq&2p\mathbb{E}\|\nabla{\bf F}({\bf X}^{t+1})-\nabla{\bf F}({\bf
X}^{t})\|^{2}+2p\mathbb{E}\|\nabla{\bf F}({\bf X}^{t})-{\bf
G}^{t}\|^{2}+(1-p)\sum_{i=1}^{n}\mathbb{E}\Big{\|}\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2}\\\
\leq&2p\mathbb{E}\|\nabla{\bf F}({\bf X}^{t+1})-\nabla{\bf F}({\bf
X}^{t})\|^{2}+2p\mathbb{E}\|\nabla{\bf F}({\bf X}^{t})-{\bf
G}^{t}\|^{2}+\frac{(1-p)(b+n)}{b}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}\\\
=&2pnV^{t}+\Big{(}2p+\frac{(1-p)(b+n)}{b}\Big{)}\mathbb{E}\|\nabla{\bf F}({\bf
X}^{t+1})-\nabla{\bf F}({\bf X}^{t})\|^{2}\\\
\leq&2pnV^{t}+\big{(}2p+p(b+n)\big{)}\mathbb{E}\|\nabla{\bf F}({\bf
X}^{t+1})-\nabla{\bf F}({\bf X}^{t})\|^{2}\\\
\leq&2pnV^{t}+4pn\mathbb{E}\|\nabla{\bf F}({\bf X}^{t+1})-\nabla{\bf F}({\bf
X}^{t})\|^{2}\end{split}$ (24)

where the first inequality is based on Cauchy–Schwarz inequality, the second
inequality is based on

$\displaystyle\mathbb{E}\Big{\|}\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2}\leq\frac{\mathbb{E}[(\xi_{i}^{t})^{2}]}{b^{2}q^{2}}\mathbb{E}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}$

and the fact $\xi_{i}^{t}\sim{\rm Binomial}(b,q)$ that leads to

$\displaystyle\frac{\mathbb{E}[(\xi_{i}^{t})^{2}]}{b^{2}q^{2}}=\frac{b^{2}q^{2}+bq(1-q)}{b^{2}q^{2}}=\frac{b+n-1}{b}\leq\frac{b+n}{b},$

the third inequality is based on the fact $b\geq(1-p)/p$ and the last step is
based on the fact that $1\leq b\leq n$.

We bound the term $\mathbb{E}\|\nabla{\bf F}({\bf X}^{t+1})-\nabla{\bf F}({\bf
X}^{t})\|^{2}$ in inequality (24) as

$\displaystyle\begin{split}&\mathbb{E}\|\nabla{\bf F}({\bf
X}^{t+1})-\nabla{\bf F}({\bf X}^{t})\|^{2}\\\
=&\sum_{i=1}^{n}{\mathbb{E}}\left\|\nabla f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}({\bf{x}}^{t}(i))\right\|^{2}\\\
\leq&3\sum_{i=1}^{n}{\mathbb{E}}\big{(}\left\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}({{\bar{\bf{x}}}}^{t+1})\right\|^{2}+\left\|\nabla
f_{i}({{\bar{\bf{x}}}}^{t+1})-\nabla
f_{i}({{\bar{\bf{x}}}}^{t})\right\|^{2}+\left\|\nabla
f_{i}({{\bar{\bf{x}}}}^{t})-\nabla
f_{i}({\bf{x}}^{t}(i))\right\|^{2}\big{)}\\\
\leq&3(\sqrt{n}L)^{2}\sum_{i=1}^{n}{\mathbb{E}}\left\|{\bf{x}}^{t+1}(i)-{{\bar{\bf{x}}}}^{t+1}\right\|^{2}+3nL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}+3(\sqrt{n}L)^{2}\sum_{i=1}^{n}{\mathbb{E}}\left\|{\bf{x}}^{t}(i)-{{\bar{\bf{x}}}}^{t}\right\|^{2}\\\
=&3nL^{2}\big{(}{\mathbb{E}}\left\|{\bf
X}^{t+1}-{\bf{1}}{{\bar{\bf{x}}}}^{t+1}\right\|^{2}+{\mathbb{E}}\left\|{\bf
X}^{t}-{\bf{1}}{{\bar{\bf{x}}}}^{t}\right\|^{2}+{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}\big{)}\\\
\leq&3nL^{2}\big{(}2\rho^{2}C^{t}+C^{t}+{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}\big{)}\\\
\leq&4nL^{2}C^{t}+3nL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2},\\\
\end{split}$ (25)

where the the second inequality is based on Lemma C.3, the third inequality is
based on inequality (22) and last step is based on the the fact $\rho^{2}\leq
1/6$.

Combining inequalities (22) – (25), we achieve

$\displaystyle C^{t+1}\leq
20\rho^{2}n^{2}C^{t}+4\rho^{2}np\eta^{2}V^{t}+12\rho^{2}n^{2}\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}.$

We then consider
$U^{t+1}=\mathbb{E}\big{\|}\frac{1}{n}\sum_{i=1}^{n}\big{(}{\bf{g}}^{t+1}(i)-\nabla
f_{i}({\bf{x}}^{t+1}(i))\big{)}\big{\|}^{2}$. We let $\xi$ be the random
variable satisfying $P(\xi=i)=q$. The update rule for ${\bf{g}}_{t+1}(i)$
implies

$\displaystyle U^{t+1}$
$\displaystyle=(1-p)\mathbb{E}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\Big{(}{\bf{g}}^{t}(i)+\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}-\nabla
f_{i}({\bf{x}}^{t+1}(i))\Big{)}\Big{\|}^{2}$
$\displaystyle=(1-p)U^{t}+(1-p)\mathbb{E}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\Big{(}\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}-\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i)))-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\Big{)}\Big{\|}^{2}$
$\displaystyle=(1-p)U^{t}+(1-p)\mathbb{E}\Big{\|}\sum_{i=1}^{n}\Big{(}\dfrac{\xi_{i}^{t}}{b}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}-\frac{1}{n}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i)))-\nabla
f_{i}({\bf{x}}^{t}(i))\big{)}\Big{)}\Big{\|}^{2}$
$\displaystyle=(1-p)U^{t}+\frac{1-p}{b}\mathbb{E}\Big{\|}\big{(}\nabla
f_{\xi}({\bf{x}}^{t+1}(\xi))-\nabla
f_{\xi}({\bf{x}}^{t}(\xi))\big{)}-\frac{1}{n}\sum_{i=1}^{n}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2}$
$\displaystyle\leq(1-p)U^{t}+\frac{1-p}{b}\mathbb{E}\Big{\|}\big{(}\nabla
f_{\xi}({\bf{x}}^{t+1}(\xi))-\nabla
f_{\xi}({\bf{x}}^{t}(\xi))\big{)}\Big{\|}^{2}$
$\displaystyle=(1-p)U^{t}+\frac{1-p}{nb}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\right\|^{2}$
$\displaystyle\leq(1-p)U^{t}+\frac{p}{n}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\right\|^{2}$
$\displaystyle\leq(1-p)U^{t}+4pL^{2}C^{t}+3pL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2},$

where the second equality is based on the property of Martingale [17,
Proposition 1], the third equality is based on the choice of $q$, the fourth
equality is based on the fact $[\xi^{t}_{1},\cdots,\xi^{t}_{n}]^{\top}\sim{\rm
Multinomial}(b,\frac{1}{n}{\bf{1}})$ and

$\displaystyle{\mathbb{E}}\left[\nabla f_{\xi}({\bf{x}}^{t+1}(\xi))-\nabla
f_{\xi}({\bf{x}}^{t}(\xi))\right]=\frac{1}{n}\sum_{i=1}^{n}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)},$ (26)

the first inequality is also based on (26), the second inequality is based on
the setting of $b\geq(1-p)/p$ and the last step is because of the following
inequality.

$\displaystyle\begin{split}&\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\right\|^{2}\\\
\leq&\frac{3}{n}\sum_{i=1}^{n}\left(\mathbb{E}\left\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla
f_{i}(\bar{\bf{x}}^{t+1})\right\|^{2}+\mathbb{E}\left\|\nabla
f_{i}(\bar{\bf{x}}^{t+1})-\nabla
f_{i}(\bar{\bf{x}}^{t})\right\|^{2}+\mathbb{E}\left\|\nabla
f_{i}(\bar{\bf{x}}^{t})-\nabla f_{i}({\bf{x}}^{t}(i))\right\|^{2}\right)\\\
\leq&\frac{3}{n}\sum_{i=1}^{n}\left(nL^{2}\mathbb{E}\left\|{\bf{x}}^{t+1}(i)-\bar{\bf{x}}^{t+1}\right\|^{2}+\mathbb{E}\left\|\nabla
f_{i}(\bar{\bf{x}}^{t+1})-\nabla
f_{i}(\bar{\bf{x}}^{t})\right\|^{2}+nL^{2}\mathbb{E}\left\|\bar{\bf{x}}^{t}-{\bf{x}}^{t}(i)\right\|^{2}\right)\\\
\leq&3L^{2}{\mathbb{E}}\left\|{\bf
X}^{t+1}-{\bf{1}}{{\bar{\bf{x}}}}^{t+1}\right\|^{2}+3L^{2}\mathbb{E}\left\|\bar{\bf{x}}^{t+1}-\bar{\bf{x}}^{t}\right\|^{2}+3L^{2}{\mathbb{E}}\left\|{\bf
X}^{t}-{\bf{1}}{{\bar{\bf{x}}}}^{t}\right\|^{2}\\\
\leq&4L^{2}C^{t}+3L^{2}\mathbb{E}\left\|\bar{\bf{x}}^{t+1}-\bar{\bf{x}}^{t}\right\|^{2},\end{split}$
(27)

where the second inequality is based on Lemma C.3, the third inequality is
based on Assumption 2.2 and the last step is based on inequalities (21) and
(22).

We finally consider $V^{t+1}=\frac{1}{n}\mathbb{E}\|{\bf G}^{t+1}-\nabla{\bf
F}({\bf X}^{t+1})\|^{2}$. The update rule for ${\bf{g}}_{t+1}(i)$ implies

$\displaystyle\begin{split}V^{t+1}&=\frac{1-p}{n}\sum_{i=1}^{n}\mathbb{E}\Big{\|}{\bf{g}}^{t}(i)+\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}-\nabla
f_{i}({\bf{x}}^{t+1}(i))\Big{\|}^{2}\\\
&=(1-p)V^{t}+\frac{1-p}{n}\sum_{i=1}^{n}\mathbb{E}\Big{\|}\dfrac{\xi_{i}^{t}}{bq}\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}-\big{(}\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\big{)}\Big{\|}^{2}\\\
&\leq(1-p)V^{t}+\frac{1-p}{n}\sum_{i=1}^{n}\dfrac{\mathrm{Var}[\xi_{i}^{t}]}{b^{2}q^{2}}{\mathbb{E}}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}\\\
&=(1-p)V^{t}+\frac{1-p}{n}\sum_{i=1}^{n}\dfrac{bq(1-q)}{b^{2}q^{2}}\mathbb{E}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}\\\
&\leq(1-p)V^{t}+\frac{1-p}{b}\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}\\\
&\leq(1-p)V^{t}+p\sum_{i=1}^{n}\mathbb{E}\|\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))\|^{2}\\\
&\leq(1-p)V^{t}+4pnL^{2}C^{t}+3pnL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2},\end{split}$

where the second equality is based on the property of Martingale [17,
Proposition 1], the first inequality is based on the fact $\xi_{i}^{t}\sim{\rm
Binomial}(b,q)$ and the independence between $\xi_{i}^{t}$ and $\nabla
f_{i}({\bf{x}}^{t+1}(i))-\nabla f_{i}({\bf{x}}^{t}(i))$, the second and third
and inequalities are based on the settings $q=1/n$ and $b\geq(1-p)/p$, and the
last step is based on the inequality (27). ∎

###  C.2 The Proof of Theorem 5.2

###### Proof.

Recall that Lemma C.5 says

$\displaystyle\mathbb{E}[f({{\bar{\bf{x}}}}^{t+1})-f^{*}]\leq(1-\mu\eta)\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\eta
U^{t}+L^{2}\eta
C^{t}-\left(\frac{1}{2\eta}-\frac{L}{2}\right)\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}.$

Combining above inequality with Lemma C.6, we have

$\displaystyle\begin{split}\Phi^{t+1}=&\mathbb{E}[f({{\bar{\bf{x}}}}^{t+1})-f^{*}]+\alpha
U^{t+1}+\beta V^{t+1}+LC^{t+1}\\\
\leq&(1-\mu\eta)\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\eta U^{t}+L^{2}\eta
C^{t}-(\frac{1}{2\eta}-\frac{L}{2})\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}\\\
&+\alpha(1-p)U^{t}+4\alpha pL^{2}C^{t}+3\alpha
pL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}\\\
&+\beta(1-p)V^{t}+4\beta pnL^{2}C^{t}+3\beta
pnL^{2}{\mathbb{E}}\left\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\right\|^{2}\\\
&+20L\rho^{2}n^{2}C^{t}+4L\rho^{2}np\eta^{2}V^{t}+12L\rho^{2}n^{2}\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}\\\
\leq&(1-\mu\eta)\mathbb{E}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+\big{(}\eta+\alpha(1-p)\big{)}U^{t}+\big{(}\beta(1-p)+4L\rho^{2}np\eta^{2}\big{)}V^{t}\\\
&+(L^{2}\eta+4\alpha pL^{2}+4\beta pnL^{2}+20L\rho^{2}n^{2})C^{t}\\\
&-\left(\frac{1}{2\eta}-\frac{L}{2}-3\alpha pL^{2}-3\beta
pnL^{2}-12L\rho^{2}n^{2}\right)\mathbb{E}\|{{\bar{\bf{x}}}}^{t+1}-{{\bar{\bf{x}}}}^{t}\|^{2}.\\\
\end{split}$

The setting of $p,\eta,b,\rho,\alpha$ and $\beta$ implies

$\displaystyle\eta+\alpha(1-p)$ $\displaystyle\leq\alpha(1-\mu\eta),$
$\displaystyle\beta(1-p)+4L\rho^{2}np\eta^{2}$
$\displaystyle\leq\beta(1-\mu\eta),$ $\displaystyle L^{2}\eta+4\alpha
pL^{2}+4\beta pnL^{2}+20L\rho^{2}n^{2}$ $\displaystyle\leq L(1-\mu\eta),$

and

$\displaystyle\frac{1}{2\eta}-\frac{L}{2}-3\alpha pL^{2}-3\beta
pnL^{2}-12L\rho^{2}n^{2}\geq 0.$

Therefore, we have

$\displaystyle\Phi^{t+1}\leq(1-\mu\eta)\Phi^{t},$

and the setting

$T\geq\left\lceil\frac{1}{\mu\eta}\log\frac{\Phi^{0}}{\epsilon}\right\rceil$

leads to

$\displaystyle\Phi^{T}\leq(1-\mu\eta)^{T}\Phi^{0}\leq\epsilon.$ (28)

The output ${\bf{x}}^{\rm out}$ holds that

$\displaystyle{\mathbb{E}}[f({\bf{x}}^{\rm out})-f^{*}]$
$\displaystyle={\mathbb{E}}[f({{\bar{\bf{x}}}}^{T})-f^{*}]+{\mathbb{E}}[f({\bf{x}}^{\rm
out})-f({{\bar{\bf{x}}}}^{T})]$
$\displaystyle={\mathbb{E}}[f({{\bar{\bf{x}}}}^{T})-f^{*}]+\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}[f({\bf{x}}^{T}(i))-f({{\bar{\bf{x}}}}^{T})]$
$\displaystyle\leq{\mathbb{E}}[f({{\bar{\bf{x}}}}^{T})-f^{*}]+\frac{1}{n}\sum_{i=1}^{n}\left({\mathbb{E}}\left[\langle\nabla
f({{\bar{\bf{x}}}}^{T}),{\bf{x}}^{T}(i)-{{\bar{\bf{x}}}}^{T}\rangle+\frac{L}{2}{\mathbb{E}}\left\|{\bf{x}}^{T}(i)-{{\bar{\bf{x}}}}^{T}\right\|^{2}\right]\right)$
$\displaystyle={\mathbb{E}}[f({{\bar{\bf{x}}}}^{T})-f^{*}]+\frac{L}{2n}\sum_{i=1}^{n}{\mathbb{E}}\left\|{\bf{x}}^{T}(i)-{{\bar{\bf{x}}}}^{T}\right\|^{2}$
$\displaystyle\leq{\mathbb{E}}[f({{\bar{\bf{x}}}}^{T})-f^{*}]+\frac{L}{2n}C^{T}$
$\displaystyle\leq\Phi^{T}\leq\epsilon,$

where the first inequality is based on Lemma C.3, the second inequality is
based on the definition of $C^{t}$, the third inequality is based on the
definition of $\Phi^{t}$ and the last step is based on inequality (28). ∎

###  C.3 The Proof of Corollary 5.3

###### Proof.

The parameters setting in this corollary means

$\displaystyle\begin{split}&p=\Theta\left(\max\left\\{\frac{1}{\sqrt{n}},\frac{1}{\kappa}\right\\}\right),\qquad
b=\Theta\left(\min\\{\sqrt{n},\kappa\\}\right),\qquad\eta=\Theta\left(\frac{1}{L}\right),\\\
&K=\Theta\left(\frac{\sqrt{2}\,(4+\log
n)}{(\sqrt{2}-1)\sqrt{\gamma}}\right)\qquad\text{and}\qquad
T=\Theta\left(\kappa\log\left(\frac{1}{\epsilon}\right)\right).\end{split}$

At each iteration, the algorithm takes
$pn+(1-p)b={\mathcal{O}}\big{(}n/\min\\{\kappa,\sqrt{n}\\}\big{)}$ LFO calls
(in expectation), $K$ communication rounds and $1+K\tau$ time cost.
Multiplying the overall iteration numbers $T$ on these quantities completes
the proof. ∎

######  Remark C.7.

We omit the detailed proof of Theorem 5.1, since it can be easily achieved by
following Theorem 5.2 and Corollary 5.3 with $p=1$, $U^{t}=V^{t}=0$ and
showing the linear convergence of
${\mathbb{E}}[f({{\bar{\bf{x}}}}^{t})-f^{*}]+LC^{t}$.

##  Appendix D More Details for Experiments

All of our experiments are performed on PC with Intel(R) Core(TM) i7-8550U
<EMAIL_ADDRESS>processor and we implement the algorithms by MPI for Python 3.9.

We formally present the details of centralized gradient descent (CGD) in
Algorithm 5. The network in CGD has sever-client architecture, which allows
the server to communicate with all clients. The convergence of CGD can be
described by gradient descent step

$\displaystyle\tilde{\bf{x}}^{t+1}=\tilde{\bf{x}}^{t}-\eta\nabla
f(\tilde{\bf{x}}^{t}),$

which can find an $\epsilon$-suboptimal solution within
${\mathcal{O}}(\kappa\log(1/\epsilon))$ iterations [25]. Therefore, it
requires the LFO complexity of ${\mathcal{O}}(\kappa n\log(1/\epsilon))$.
Since the sever-client architecture does not suffer from consensus error, it
has communication complexity of
${\mathcal{O}}\left(\kappa\log(1/\epsilon)\right)$ and time complexity of
${\mathcal{O}}\left(\kappa\left(1+{\tau}\right)\log(1/\epsilon)\right)$.

The objective functions for linear regression and logistic regression are not
strongly convex when $d>m$, while they satisfy the PL conditions. Please refer
to Section 3.2 of Karimi et al. [25].

Algorithm 5 Centralized GD

1: Input: initial point $\tilde{\bf{x}}^{0}\in{\mathbb{R}}^{d}$, iteration
number $T$ and stepsize $\eta>0$

2: for $t=0,1\cdots T-1$ do

3: for $i=1,\dots,n$ do in parallel

4: $i$-th client:

5: receive $\tilde{\bf{x}}^{t}$

6: compute ${\bf{g}}^{t}(i)=\nabla f_{i}({\bf{x}}^{t})$

7: send ${\bf{g}}^{t}(i)$

8: end for

9: server:

10: receive ${\bf{g}}^{t}(1),\dots,{\bf{g}}^{t}(n)$

11: compute
$\tilde{\bf{x}}^{t+1}=\tilde{\bf{x}}^{t}-\eta\cdot\frac{1}{n}\sum_{i=1}^{n}{\bf{g}}^{t}(i)$

12: broadcast $\tilde{\bf{x}}^{t+1}$

13: end for

14: Output: $\tilde{\bf{x}}^{T}$

## References

  * Agarwal and Bottou [2015] Alekh Agarwal and Leon Bottou.  A lower bound for the optimization of finite sums.  In _ICML_ , 2015.
  * Agarwal et al. [2021] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  _Journal of Machine Learning Research_ , 22(1):4431–4506, 2021.
  * Allen-Zhu [2017] Zeyuan Allen-Zhu.  Katyusha: The first direct acceleration of stochastic gradient methods.  _Journal of Machine Learning Research_ , 18(1):8194–8244, 2017.
  * Allen-Zhu and Hazan [2016] Zeyuan Allen-Zhu and Elad Hazan.  Variance reduction for faster non-convex optimization.  In _ICML_ , 2016.
  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _ICML_ , 2019.
  * Arioli and Scott [2014] Mario Arioli and Jennifer Scott.  Chebyshev acceleration of iterative refinement.  _Numerical Algorithms_ , 66(3):591–608, 2014.
  * Arjevani et al. [2022] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth.  Lower bounds for non-convex stochastic optimization.  _Mathematical Programming_ , pages 1–50, 2022.
  * Attouch and Bolte [2009] Hedy Attouch and Jérôme Bolte.  On the convergence of the proximal algorithm for nonsmooth functions involving analytic features.  _Mathematical Programming_ , 116:5–16, 2009.
  * Bi et al. [2022] Yingjie Bi, Haixiang Zhang, and Javad Lavaei.  Local and global linear convergence of general low-rank matrix recovery problems.  In _AAAI_ , 2022.
  * Bolte et al. [2007] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis.  The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.  _SIAM Journal on Optimization_ , 17(4):1205–1223, 2007.
  * Bolte et al. [2014] Jérôme Bolte, Shoham Sabach, and Marc Teboulle.  Proximal alternating linearized minimization for nonconvex and nonsmooth problems.  _Mathematical Programming_ , 146(1-2):459–494, 2014.
  * Bu et al. [2019] Jingjing Bu, Afshin Mesbahi, Maryam Fazel, and Mehran Mesbahi.  LQR through the lens of first order methods: Discrete-time case.  _arXiv preprint arXiv:1907.08921_ , 2019.
  * Carmon and Duchi [2020] Yair Carmon and John C. Duchi.  First-order methods for nonconvex quadratic minimization.  _SIAM Review_ , 62(2):395–436, 2020.
  * 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.
  * Defazio et al. [2014] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien.  SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.  In _NIPS_ , 2014.
  * Diaz-Chito et al. [2016] Katerine Diaz-Chito, Aura Hernández-Sabaté, and Antonio M. López.  A reduced feature set for driver head pose estimation.  _Applied Soft Computing_ , 45:98–107, 2016.
  * Fang et al. [2018] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang.  SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  In _NeurIPS_ , 2018.
  * Fatkhullin and Polyak [2021] Ilyas Fatkhullin and Boris Polyak.  Optimizing static linear feedback: Gradient method.  _SIAM Journal on Control and Optimization_ , 59(5):3887–3911, 2021.
  * Fatkhullin et al. [2022] Ilyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash.  Sharp analysis of stochastic optimization under global Kurdyka-Łojasiewicz inequality.  _NeurIPS_ , 2022.
  * Fazel et al. [2018] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator.  In _ICML_ , 2018.
  * Hardt and Ma [2016] Moritz Hardt and Tengyu Ma.  Identity matters in deep learning.  In _ICLR_ , 2016.
  * Hendrikx et al. [2021] Hadrien Hendrikx, Francis Bach, and Laurent Massoulie.  An optimal algorithm for decentralized finite-sum optimization.  _SIAM Journal on Optimization_ , 31(4):2753–2783, 2021.
  * Jiang and Li [2022] Rujun Jiang and Xudong Li.  Hölderian error bounds and Kurdyka-Łojasiewicz inequality for the trust region subproblem.  _Mathematics of Operations Research_ , 47(4):3025–3050, 2022.
  * Johnson and Zhang [2013] Rie Johnson and Tong Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  In _NIPS_ , 2013.
  * Karimi et al. [2016] Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition.  In _ECML/PKDD_ , 2016.
  * Kovalev et al. [2020a] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik.  Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop.  In _ALT_ , 2020a.
  * Kovalev et al. [2020b] Dmitry Kovalev, Adil Salim, and Peter Richtárik.  Optimal and practical algorithms for smooth and strongly convex decentralized optimization.  _NeurIPS_ , 2020b.
  * Lei et al. [2017] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I. Jordan.  Non-convex finite-sum optimization via SCSG methods.  In _NIPS_ , 2017.
  * Li et al. [2022a] Boyue Li, Zhize Li, and Yuejie Chi.  DESTRESS: Computation-optimal and communication-efficient decentralized nonconvex finite-sum optimization.  _SIAM Journal on Mathematics of Data Science_ , 4(3):1031–1051, 2022a.
  * Li et al. [2022b] Huan Li, Zhouchen Lin, and Yongchun Fang.  Variance reduced EXTRA and DIGing and their optimal acceleration for strongly convex decentralized optimization.  _Journal of Machine Learning Research_ , 23:1–41, 2022b.
  * Li et al. [2018] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang.  Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations.  In _Conference On Learning Theory_ , pages 2–47. PMLR, 2018.
  * Li et al. [2021] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik.  PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization.  In _ICML_ , 2021.
  * Liu et al. [2022] Chaoyue Liu, Libin Zhu, and Mikhail Belkin.  Loss landscapes and optimization in over-parameterized non-linear systems and neural networks.  _Applied and Computational Harmonic Analysis_ , 59:85–116, 2022.
  * Łojasiewicz [1963] Stanislaw Łojasiewicz.  A topological property of real analytic subsets.  _Coll. du CNRS, Les équations aux dérivées partielles_ , 117(87-89):2, 1963.
  * Lu and De Sa [2021] Yucheng Lu and Christopher De Sa.  Optimal complexity in decentralized training.  In _ICML_ , 2021.
  * Luo and Ye [2022] Luo Luo and Haishan Ye.  An optimal stochastic algorithm for decentralized nonconvex finite-sum optimization.  _arXiv preprint arXiv:2210.13931_ , 2022.
  * Maranjyan et al. [2022] Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik.  GradSkip: Communication-accelerated local gradient methods with better computational complexity.  _arXiv preprint arXiv:2210.16402_ , 2022.
  * Mei et al. [2020] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.  On the global convergence rates of softmax policy gradient methods.  In _International Conference on Machine Learning_ , pages 6820–6829. PMLR, 2020.
  * Mishchenko et al. [2022] Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik.  Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!  In _ICML_ , 2022.
  * Nedic and Ozdaglar [2009] Angelia Nedic and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Nemirovskij and Yudin [1983] Arkadij Semenovič Nemirovskij and David Borisovich Yudin.  _Problem complexity and method efficiency in optimization_.  Wiley-Interscience, 1983.
  * Nesterov [2018] Yurii Nesterov.  _Lectures on convex optimization_ , volume 137.  Springer, 2018.
  * Nguyen et al. [2017] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč.  SARAH: A novel method for machine learning problems using stochastic recursive gradient.  In _ICML_ , 2017.
  * Pham et al. [2020] Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoc Tran-Dinh.  ProxSARAH: An efficient algorithmic framework for stochastic composite nonconvex optimization.  _Journal of Machine Learning Research_ , 21(110):1–48, 2020.
  * Polyak [1963] Boris Teodorovich Polyak.  Gradient methods for minimizing functionals.  _Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki_ , 3(4):643–653, 1963.
  * Qian et al. [2021] Xun Qian, Zheng Qu, and Peter Richtárik.  L-SVRG and L-Katyusha with arbitrary sampling.  _Journal of Machine Learning Research_ , 22(1):4991–5039, 2021.
  * Qu and Li [2017] Guannan Qu and Na Li.  Harnessing smoothness to accelerate distributed optimization.  _IEEE Transactions on Control of Network Systems_ , 5(3):1245–1260, 2017.
  * Reddi et al. [2016] Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola.  Stochastic variance reduction for nonconvex optimization.  In _ICML_ , 2016.
  * Roux et al. [2012] Nicolas Roux, Mark Schmidt, and Francis Bach.  A stochastic gradient method with an exponential convergence rate for finite training sets.  In _NIPS_ , 2012.
  * Scaman et al. [2017] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié.  Optimal algorithms for smooth and strongly convex distributed optimization in networks.  In _ICML_ , 2017.
  * Schmidt et al. [2017] Mark Schmidt, Nicolas Le Roux, and Francis Bach.  Minimizing finite sums with the stochastic average gradient.  _Mathematical Programming_ , 162(1-2):83–112, 2017.
  * Shi et al. [2015] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin.  EXTRA: An exact first-order algorithm for decentralized consensus optimization.  _SIAM Journal on Optimization_ , 25(2):944–966, 2015.
  * Song et al. [2023] Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan.  Optimal gradient tracking for decentralized optimization.  _Mathematical Programming_ , pages 1–53, 2023.
  * Sun et al. [2020] Haoran Sun, Songtao Lu, and Mingyi Hong.  Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking.  In _ICML_ , 2020.
  * Wang et al. [2019] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh.  SpiderBoost and momentum: Faster variance reduction algorithms.  In _NeurIPS_ , 2019.
  * Woodworth and Srebro [2016] Blake E Woodworth and Nati Srebro.  Tight complexity bounds for optimizing composite objectives.  In _NIPS_ , 2016.
  * Xin et al. [2022] Ran Xin, Usman A. Khan, and Soummya Kar.  Fast decentralized nonconvex finite-sum optimization with recursive variance reduction.  _SIAM Journal on Optimization_ , 32(1):1–28, 2022.
  * Ye et al. [2023] Haishan Ye, Luo Luo, Ziang Zhou, and Tong Zhang.  Multi-consensus decentralized accelerated gradient descent.  _Journal of Machine Learning Research_ , 24(306):1–50, 2023.
  * Yuan et al. [2022a] Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, and Pan Pan.  Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization.  In _NeurIPS_ , 2022a.
  * Yuan et al. [2022b] Rui Yuan, Robert M Gower, and Alessandro Lazaric.  A general sample complexity analysis of vanilla policy gradient.  In _AISTATS_ , 2022b.
  * Yue et al. [2023] Pengyun Yue, Cong Fang, and Zhouchen Lin.  On the lower bound of minimizing Polyak-Łojasiewicz functions.  In _COLT_ , 2023.
  * Zeng et al. [2018] Jinshan Zeng, Shikang Ouyang, Tim Tsz-Kit Lau, Shaobo Lin, and Yuan Yao.  Global convergence in deep learning with variable splitting via the Kurdyka-Łojasiewicz property.  _arXiv preprint arXiv:1803.00225_ , 9, 2018.
  * Zhan et al. [2022] Wenkang Zhan, Gang Wu, and Hongchang Gao.  Efficient decentralized stochastic gradient descent method for nonconvex finite-sum optimization problems.  In _AAAI_ , 2022.
  * Zhang et al. [2013] Lijun Zhang, Mehrdad Mahdavi, and Rong Jin.  Linear convergence with condition number independent access of full gradients.  In _NIPS_ , 2013.
  * Zhou and Gu [2019] Dongruo Zhou and Quanquan Gu.  Lower bounds for smooth nonconvex finite-sum optimization.  In _ICML_ , 2019.
  * Zhou et al. [2019] Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng.  Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds.  In _AISTATS_ , 2019.
  * Zhou et al. [2018] Yi Zhou, Zhe Wang, and Yingbin Liang.  Convergence of cubic regularization for nonconvex optimization under KL property.  _NeurIPS_ , 2018.