# Communication-Efficient Federated Learning Using Censored Heavy Ball Descent
††thanks: The work was supported by the U. S. Army Research Laboratory and the
U. S. Army Research Office under grant number W911NF-17-1-0331 and by the
Office of Naval Research grant number N00014-22-1-2626.

Yicheng Chen, Rick S. Blum, , and Brian M. Sadler  Yicheng Chen is with
Reality Labs Meta, Redmond, WA 98052 USA (email: chenggejiayou@gmail.com).
Rick S. Blum is with Lehigh University, Bethlehem, PA 18015 USA (email:
rblum@eecs.lehigh.edu). Brian M. Sadler is with DEVCOM ARL, Adelphi, MD 20878
USA (email: brian.m.sadler6.civ@mail.mil).

###### Abstract

Distributed machine learning enables scalability and computational offloading,
but requires significant levels of communication. Consequently, communication
efficiency in distributed learning settings is an important consideration,
especially when the communications are wireless and battery-driven devices are
employed. In this paper we develop a censoring-based heavy ball (CHB) method
for distributed learning in a server-worker architecture. Each worker self-
censors unless its local gradient is sufficiently different from the
previously transmitted one. The significant practical advantages of the HB
method for learning problems are well known, but the question of reducing
communications has not been addressed. CHB takes advantage of the HB smoothing
to eliminate reporting small changes, and provably achieves a linear
convergence rate equivalent to that of the classical HB method for smooth and
strongly convex objective functions. The convergence guarantee of CHB is
theoretically justified for both convex and nonconvex cases. In addition we
prove that, under some conditions, at least half of all communications can be
eliminated without any impact on convergence rate. Extensive numerical results
validate the communication efficiency of CHB on both synthetic and real
datasets, for convex, nonconvex, and nondifferentiable cases. Given a target
accuracy, CHB can significantly reduce the number of communications compared
to existing algorithms, achieving the same accuracy without slowing down the
optimization process.

###### Index Terms:

Censoring, communication-efficient, federated learning, heavy ball.

##  I Introduction

Traditional centralized optimization algorithms for machine learning
applications have a number of limitations when applied in networked settings.
This is especially clear in some applications where abundant distributed
processing resources are inherently available such as vehicular, mobile
cellular, and sensor networks. This motivates distributed optimization that
balances communications and processing. One popular distributed optimization
problem can be formulated as

$\displaystyle\min_{\bm{\theta}\in\mathbb{R}^{d}}f(\bm{\theta})\quad\text{
with }\quad
f(\bm{\theta})\buildrel\Delta\over{=}\sum_{m\in\mathcal{M}}f_{m}(\bm{\theta})$
(1)

where $\bm{\theta}\in\mathbb{R}^{d}$ is the model parameter vector to be
optimized, $f(\bm{\theta})$ is the objective function to be minimized, and
$f_{m}(\bm{\theta})$ is the local function for worker
$m\in\mathcal{M}=\\{1,2,...,M\\}$. The problem in (1) has been successfully
applied as a model in multi-agent systems [1, 2, 3], sensor networks [4, 5, 6,
7, 8], smart grids [9], and distributed learning [10, 11, 12, 13]. To relate
(1) to a distributed learning setting, let
$f_{m}(\bm{\theta})\buildrel\Delta\over{=}\sum_{n=1}^{N_{m}}\ell(\bm{\theta};\mathbf{x}_{n},y_{n})$
denote the loss function $\ell(\bm{\theta};\mathbf{x}_{n},y_{n})$ summed over
all the training data $\\{(\mathbf{x}_{n},y_{n}),n=1,2,...,N_{m}\\}$ at
worker/node $m$, where $\mathbf{x}_{n}$ is the $n$-th feature vector and
$y_{n}$ is the corresponding label. A common method to solve (1) uses a
worker-server architecture where a central server updates the model parameter
by aggregating the gradients computed at all workers and then transmits the
updated parameter back to the workers. The learning task is solved after many
communications between workers and the server. However, the communications
latency is generally orders of magnitude larger than local memory access,
e.g., about $2500$ times larger over a standard network connection [14]. For
this reason, the required communications can be a significant bottleneck on
overall performance, especially in federated learning and edge AI systems [15,
16, 17, 18, 19, 20, 21, 22]. The communications can also be a large drain on
the batteries of mobile nodes. Therefore, it is extremely important to develop
distributed optimization algorithms that are efficient in terms of
communications. In this paper we develop a communication-efficient server-
worker processing scheme to significantly reduce communications without
sacrificing convergence speed.

###  I-A Prior Art

The challenge of communication-efficient distributed optimization has been
addressed in several ways. Data compression is one popular solution to reduce
the bandwidth usage per transmission. The existing approaches mainly exploit
quantization and sparsification. Quantization aims to approximate a
continuous-valued quantity using a finite set of values to simplify processing
and storage, and has been successfully applied in many distributed
optimization algorithms [18, 23, 24, 25, 26, 27, 28]. Sparsification
techniques can also reduce bandwidth. For example some small gradient vector
coordinates can be assumed to be zero while the remaining coordinates can be
appropriately amplified to ensure the sparsified gradient is unbiased [17, 29,
30, 31]. However, the existing efforts for quantization and sparsification
reduce the bandwidth usage, not the number of communications. Additionally,
quantization and sparsification bring noise and errors which slow down the
optimization process in general.

In addition to reducing the number of bits per communication, accelerating
convergence is another straightforward method to enhance communication
efficiency. One-shot parameter averaging methods were proposed in [32, 33, 34,
35] to find the optimal minimizer using only one iteration. While the idea of
reducing the number of iterations is desirable, one-iteration approaches may
sacrifice too much performance to accomplish this goal in some cases [36]. As
an alternative to summing gradients, researchers have considered more
sophisticated methods where a worker can compute (or approximately compute)
its local Hessian. Examples of these approaches include quasi-Newton methods
[37, 38, 39, 40, 41] and approximated Newton methods [36, 42, 43]. On the
other hand, primal-dual methods [14, 44, 45, 46] are also shown to be
efficient in distributed optimization where the primal solution is obtained by
solving the dual problem. However, these algorithms save communications at the
cost of increasing local computation, unlike the method proposed in this paper
which does not increase local computation compared to the first-order
algorithms where only the local gradient is computed.

As an alternative to speeding up the optimization process, reducing the number
of transmissions per iteration is another efficient way to save
communications. An approach called censoring has previously been studied for
applications other than learning [47, 48, 49, 50]. Censoring eliminates
transmissions of less informative data, thus reducing worker communications.
The original work [47, 48, 49, 50] focused on hypothesis testing and the
censoring was applied to the worker likelihood ratios. Later, the ideas were
applied to distributed optimization, where the censoring was applied to
workers such that worker gradients are not transmitted if they do not change
significantly compared to previously transmitted ones. Distributed
optimization approaches employing censoring include the event-triggered zero-
gradient-sum algorithms [51], and the censoring-based subgradient algorithm
[52]. However, the step size of the algorithms in [51, 52] is reduced at each
iteration to guarantee convergence, which results in relatively slow progress
in the optimization process as the step size becomes smaller and smaller.
Distributed dual averaging with censoring was proposed in [53] but it does not
have theoretical justification for convergence or communication saving, unlike
this paper. Gradient descent (GD) with censoring was proposed in [54] to save
communications for machine learning in a comprehensive study that our paper
builds upon. In [54], each step is chosen according to the approximated
steepest descent direction without considering previous search directions,
whereas in our paper we propose a heavy ball (HB) method with a momentum term.
The significant practical advantages of the HB method for learning problems
are well known [55, 56], but the question of reducing communications,
including convergence, has not been addressed. The following proposed
censoring-based heavy ball (CHB) method accelerates convergence, as might be
expected from previous studies of heavy ball, but also takes advantage of the
momentum term to smooth the gradient and reduce changes resulting in further
communication savings.

Our contributions. In this paper we develop a censoring-based heavy ball (CHB)
method for distributed learning in the server-worker architecture where our
censoring threshold for each worker to decide whether to transmit or not at
each iteration is proposed in an intuitive and straightforward way. Combining
the censoring threshold with the CHB parameter update rule, a rigorous
convergence guarantee is derived in this paper for CHB under strongly convex,
convex and nonconvex cases. Our results also demonstrate that CHB can achieve
the same linear convergence rate as the classical HB method for a smooth and
strongly convex objective function. We show that more than half of the
communications can be saved without any impact on the convergence rate under
certain conditions. Numerical experimental results demonstrate that CHB is
able to significantly reduce the total number of communications while
maintaining a fast convergence rate to a target solution accuracy when
compared to other distributed learning algorithms for both synthetic and real
datasets.

Notation. Bold lower case letters are used throughout this paper to denote
column vectors. The notation $\|\bf{x}\|$ and $\bf{x^{\top}}$ is employed to
denote the $\ell_{2}$-norm and the transpose of a column vector $\bf{x}$,
respectively.

##  II Censoring-based heavy ball method

Before introducing our method for reducing communications, we begin with a
brief discussion of the classical HB method [57], a popular iterative
optimization algorithm, and focus on its parameter update rule in a
distributed system with a server and $M$ workers. Specifically, at iteration
$k$ of HB, the server broadcasts the current parameter $\bm{\theta}^{k}$ to
all workers; each worker $m$ computes the gradient $\nabla
f_{m}(\bm{\theta}^{k})$ based on its own local function
$f_{m}(\bm{\theta}^{k})$ and transmits $\nabla f_{m}(\bm{\theta}^{k})$ back to
the server. Upon receiving $\nabla f_{m}(\bm{\theta}^{k})$ from each worker,
the server updates $\bm{\theta}^{k}$ as [57]

$\displaystyle{\textbf{ HB-update }}\quad\bm{\theta}^{k+1}$
$\displaystyle=\bm{\theta}^{k}-\alpha\nabla
f(\bm{\theta}^{k})+\beta(\bm{\theta}^{k}-\bm{\theta}^{k-1})\text{ with }$
$\displaystyle\qquad\nabla
f(\bm{\theta}^{k})\buildrel\Delta\over{=}\sum_{m\in\mathcal{M}}\nabla
f_{m}(\bm{\theta}^{k})$ (2)

where $\alpha$ is the step size, $\beta$ is a constant, and $\nabla
f(\bm{\theta}^{k})$ is the gradient of $f(\bm{\theta}^{k})$. To implement (II)
requires $M$ communications from the workers to the server during each
iteration $k$.

Our communication-efficient CHB algorithm will be described next. Each worker
maintains two vectors concerning iteration $k$. One is the parameter vector
$\bm{\theta}^{k}$ sent by the server at the start of iteration $k$. The other
is the last gradient $\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k-1})$ transmitted
from worker $m$ to the server prior to iteration $k$. An important feature of
CHB is that a worker $m$ will not transmit to the server if the current
gradient $\nabla f_{m}(\bm{\theta}^{k})$ is not sufficiently different from
the previously transmitted gradient $\nabla
f_{m}(\hat{\bm{\theta}}_{m}^{k-1})$. Define

$\displaystyle\delta\nabla_{m}^{k}\buildrel\Delta\over{=}\nabla
f_{m}(\bm{\theta}^{k})-\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k-1}).$ (3)

It is worth mentioning that $\delta\nabla_{m}^{k}$ characterizes the “newness”
of the information contained in the gradient of worker $m$ at iteration $k$.
To implement the CHB algorithm, at the beginning of iteration $k$ the server
broadcasts $\bm{\theta}^{k}$ to all workers. Then only if worker $m$ has a
gradient which is sufficiently different from that previously transmitted will
it transmit $\delta\nabla_{m}^{k}$ back to the server. Immediately after
transmitting, worker $m$ will update its transmitted gradient $\nabla
f_{m}(\hat{\bm{\theta}}_{m}^{k})=\nabla f_{m}({\bm{\theta}}^{k})$ while others
keep their previous values $\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k})=\nabla
f_{m}(\hat{\bm{\theta}}_{m}^{k-1})$. At the end of iteration $k$, the server
updates the parameter $\bm{\theta}^{k}$ via

$\displaystyle{\textbf{ CHB-update }}\quad\bm{\theta}^{k+1}$
$\displaystyle=\bm{\theta}^{k}-\alpha\nabla^{k}+\beta(\bm{\theta}^{k}-\bm{\theta}^{k-1})\text{
with }$
$\displaystyle\nabla^{k}\buildrel\Delta\over{=}\sum_{m\in\mathcal{M}}\nabla
f_{m}(\hat{\bm{\theta}}^{k})$ (4)

where $\nabla^{k}$ is an approximation to the gradient at iteration $k$ which
is computed recursively using

$\displaystyle\nabla^{k}=\nabla^{k-1}+\sum_{m\in\mathcal{M}^{k}}\delta\nabla_{m}^{k}.$
(5)

Here $\mathcal{M}^{k}$ is a set which collects the indices of workers who have
transmitted during iteration $k$ and whose cardinality is denoted
$|\mathcal{M}^{k}|$. The number of communications are often reduced to
$|\mathcal{M}^{k}|<M$ during iteration $k$ in the CHB algorithm which explains
the term $\sum_{m\in\mathcal{M}^{k}}\delta\nabla_{m}^{k}$ in (5). In fact, if
we replace $\mathcal{M}^{k}$ in (5) with $\mathcal{M}$, plugging (5) into (II)
yields the classical HB update rule in (II).

Next we describe when a worker will skip a transmission, which we call the
CHB-skip-transmission condition. To make the principles behind the design of
the CHB-skip-transmission condition clear, the CHB update rule in (II) can be
rewritten as

$\displaystyle\bm{\theta}^{k+1}$
$\displaystyle=\bm{\theta}^{k}-\alpha\bigg{(}\nabla
f(\bm{\theta}^{k})-\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\bigg{)}+\beta(\bm{\theta}^{k}-\bm{\theta}^{k-1})$
(6) $\displaystyle=\bm{\theta}^{k}-\alpha\nabla
f(\bm{\theta}^{k})+\beta(\bm{\theta}^{k}-\bm{\theta}^{k-1})+\alpha\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}$
(7)

where $\mathcal{M}_{c}^{k}$ is a set which collects the indices of workers who
do not transmit during iteration $k$, and $\delta\nabla_{m}^{k}$ is defined in
(3). It is well known [57] that the update steps in HB tend to accumulate
contributions in directions of persistent descent while canceling directions
that oscillate. This interpretation provides some intuitive explanation as to
why the HB method often outperforms gradient descent (GD) [57]. Since the
update rule of CHB in (II) is very similar to that of the traditional HB
method (just drop less informative terms), it is not surprising that we have
observed that the CHB algorithm inherits the advantages from the HB method.
Compared with the classical HB update rule in (II), the result in (7) shows
that we can save transmissions by not allowing the workers in
$\mathcal{M}_{c}^{k}$ to transmit if $\delta\nabla_{m}^{k}$ for all
$m\in\mathcal{M}_{c}^{k}$ is very small compared to
$(\bm{\theta}^{k}-\bm{\theta}^{k-1})$. This takes advantage of the HB
smoothing and as will see, we can save transmissions with very little affect
on the optimization convergence rate. Therefore, the rule to determine if
worker $m$ will or will not transmit is called the CHB-skip-transmission
condition,

$\displaystyle\|\delta\nabla_{m}^{k}\|^{2}\leq\varepsilon_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}$
(8)

where $\varepsilon_{1}$ is a positive constant that allows us to tune the
convergence while saving communications. Intuitively, smaller
$\varepsilon_{1}$ leads to less communication censoring, e.g., CHB reduces to
the classical HB method when we set $\varepsilon_{1}=0$. On the other hand,
when $\varepsilon_{1}$ increases, the number of communications per iteration
is reduced at the cost of increasing the number of iterations. A favorable
communication-iteration trade-off can be achieved by CHB via tuning
$\varepsilon_{1}$; see the example in Figure 11. Finding a theoretically
optimal value of $\varepsilon_{1}$ is an interesting open problem. Note that
using similar steps to those shown in [54], the condition (8) can also be
derived based on the criterion which ensures that CHB has larger per-
communication descent than HB. At iteration $k$, after receiving
$\bm{\theta}^{k}$ from the server, each worker can independently check the
CHB-skip-transmission condition (8). If the CHB-skip-transmission condition is
not satisfied, then worker $m$ will immediately transmit
$\delta\nabla_{m}^{k}$ to the server. The CHB algorithm is summarized as
Algorithm 1.

1:step size $\alpha$, positive constants $\varepsilon_{1}$ and $\beta$.

2:${\bm{\theta}}^{1}$, {$\nabla\mathcal{L}_{m}(\hat{\bm{\theta}}_{m}^{0})$,
$\forall m$}

3:for $k=1,2,...,K$ do

4: Server broadcasts $\bm{\theta}^{k}$ at the starting time of iteration $k$.

5: for $m=1,2,...,M$ do

6: if the CHB-skip-transmission condition in (8) is not satisfied for worker
$m$ then

7: Worker $m$ transmits $\delta\nabla_{m}^{k}$ to the server and locally
updates $\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k})=\nabla
f_{m}({\bm{\theta}}^{k})$.

8: else

9: Worker $m$ does not transmit but locally updates $\nabla
f_{m}(\hat{\bm{\theta}}_{m}^{k})=\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k-1})$.

10: end if

11: end for

12: Server updates ${\bm{\theta}}^{k}$ via (II).

13:end for

Algorithm 1 CHB

##  III Convergence and communication analysis

In this section, convergence rate and communication reduction guarantees for
CHB are developed for the proper choice of the constants $\alpha$, $\beta$,
and $\varepsilon_{1}$. The following assumptions and definitions are needed
for the provided results.

######  Assumption 1.

In _( 1)_, $f(\bm{\theta})$ in is $L$-smooth and coercive. This implies there
exists a constant $L>0$ such that $\|\nabla f(\bm{\theta}_{1})-\nabla
f(\bm{\theta}_{2})\|\leq L\|\bm{\theta}_{1}-\bm{\theta}_{2}\|,\ \forall\
\bm{\theta}_{1},\bm{\theta}_{2}$ _[58]_ and
$\lim_{\|\bm{\theta}\|\rightarrow\infty}f(\bm{\theta})=+\infty$ _[59]_.

######  Definition 1.

The objective function $f(\bm{\theta})$ in _( 1)_ is $\mu$-strongly convex,
which implies the existence of a constant $\mu>0$ such that
$f(\bm{\theta}_{1})\geq f(\bm{\theta}_{2})+\nabla
f(\bm{\theta}_{2})^{\top}(\bm{\theta}_{1}-\bm{\theta}_{2})+\frac{\mu}{2}\|\bm{\theta}_{1}-\bm{\theta}_{2}\|^{2},\forall\
\bm{\theta}_{1},\bm{\theta}_{2}$ _[58]_.

######  Definition 2.

The objective function $f(\bm{\theta})$ in _( 1)_ is convex, which implies
$f(\bm{\theta})$ satisfies
$f(\lambda\bm{\theta}_{1}+(1-\lambda)\bm{\theta}_{2})\leq\lambda
f(\bm{\theta}_{1})+(1-\lambda)f(\bm{\theta}_{2}),\forall\
\bm{\theta}_{1},\bm{\theta}_{2}$ and $0\leq\lambda\leq 1$ _[59]_.

######  Assumption 2.

In _( 1)_, $f_{m}(\bm{\theta})$ is $L_{m}$-smooth for each worker $m$. This
implies there exists a constant $L_{m}>0$ such that $\|\nabla
f_{m}(\bm{\theta}_{1})-\nabla f_{m}(\bm{\theta}_{2})\|\leq
L_{m}\|\bm{\theta}_{1}-\bm{\theta}_{2}\|,\ \forall\
\bm{\theta}_{1},\bm{\theta}_{2}$ _[58]_.

Let

$\displaystyle\mathbb{L}(\bm{\theta}^{k})\buildrel\Delta\over{=}f(\bm{\theta}^{k})-f\left(\bm{\theta}^{*}\right)+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}$
(9)

define a Lyapunov function, where $\bm{\theta}^{*}$ is the optimal solution to
the optimization problem in (1), and $\eta_{1}$ is a non-negative constant. If
we allow all workers to transmit ($\mathcal{M}^{k}=\mathcal{M}$) and set
$\eta_{1}=0$, then CHB reduces to the classical HB method and
$\mathbb{L}(\bm{\theta}^{k})$ will describe the optimization process of the HB
method. However, when some communications are suppressed, the following lemma
describes the behavior of the Lyapunov function defined in (9).

######  Lemma 1.

Under _Assumption 1_, if the constants $\alpha$, $\beta$, and
$\varepsilon_{1}$ are chosen so that

$\displaystyle\sigma_{0}$ $\displaystyle\geq 0\ \mbox{with}\
\sigma_{0}\buildrel\Delta\over{=}\frac{\alpha}{2}-\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2}),$ (10)
$\displaystyle\sigma_{1}$ $\displaystyle\geq 0\ \mbox{with}\
\sigma_{1}\buildrel\Delta\over{=}-\gamma|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}-\frac{\beta^{2}}{2\alpha}(1+\rho_{3}^{-1})$
$\displaystyle\qquad\qquad-\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\beta^{2}(1+\rho_{1}^{-1})+\eta_{1},$ (11)
$\displaystyle\gamma$ $\displaystyle\geq\frac{\alpha}{2}(1+\rho_{3})\
\mbox{with}\ \gamma\buildrel\Delta\over{=}\frac{\alpha}{2}(1+\rho_{3})$
$\displaystyle\qquad\qquad+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2}^{-1}),$ (12)

where $\eta_{1}$ is the non-negative constant in (9), $|\mathcal{M}_{c}^{k}|$
is the cardinality of $\mathcal{M}_{c}^{k}$, and $\rho_{1}$, $\rho_{2}$,
$\rho_{3}>0$, then the Lyapunov function follows

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})\leq-\sigma_{0}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}-\sigma_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(13)

where constants $\sigma_{0}\geq 0$ and $\sigma_{1}\geq 0$ depend on $\alpha$,
$\beta$ and $\varepsilon_{1}$. The result in (13) implies
$\mathbb{L}(\bm{\theta}^{k+1})\leq\mathbb{L}(\bm{\theta}^{k})$.

###### Proof:

Please refer to Appendix B. ∎

From (11), we know that $\sigma_{1}=\sigma_{1}(|\mathcal{M}_{c}^{k}|)$ but for
simplicity, we omit $|\mathcal{M}_{c}^{k}|$ here. Note that if we set
$\big{(}\eta_{1}-\frac{1-\alpha L}{2\alpha}\big{)}=0$, then (10)–(12) are
equivalent to

$\displaystyle\alpha\leq\frac{1}{L},\quad\beta$
$\displaystyle\leq\sqrt{\frac{1-\alpha L}{1+\rho_{3}^{-1}}},\quad\mbox{and}$
$\displaystyle\qquad\varepsilon_{1}\leq\frac{(1-\alpha
L)-\beta^{2}(1+\rho_{3}^{-1})}{\alpha^{2}(1+\rho_{3})|\mathcal{M}_{c}^{k}|^{2}}.$
(14)

It can be shown that (III) admits an uncountable number of solutions for
$\alpha$, $\beta$ and $\varepsilon_{1}$ which would guarantee (10)–(12). Some
examples of other parameter choices can be found at the end of Appendix B.
Next, we will show that the Lyapunov function in (9) has a linear convergence
rate under certain conditions.

######  Theorem 1.

(strongly convex) Under _Assumption 1_ and _Definition 1_, if constants
$\alpha$, $\beta$ and $\varepsilon_{1}$ are properly selected such that
(10)–(12) are satisfied with $\sigma_{0}>0$ in (10) and $\sigma_{1}>0$ in
(11), then the Lyapunov function in (9) converges Q-linearly; that is, there
exists a constant $c(\alpha,\beta,\varepsilon_{1})\in(0,1)$ such that at
iteration $k$,

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})\leq\big{(}1-c(\alpha,\beta,\varepsilon_{1})\big{)}\mathbb{L}(\bm{\theta}^{k})$
(15)

where
$c(\alpha,\beta,\varepsilon_{1})=\min\big{\\{}2\sigma_{0}\mu,\min_{k}\\{\sigma_{1}\\}/\eta_{1}\big{\\}}$
with $\sigma_{0}$ and $\sigma_{1}$ defined in (10) and (11), respectively. The
result in (15) implies

$\displaystyle
f(\bm{\theta}^{k})-f\left(\bm{\theta}^{*}\right)\leq\big{(}1-c(\alpha,\beta,\varepsilon_{1})\big{)}^{k}\mathbb{L}(\bm{\theta}^{0}).$
(16)

###### Proof:

Please refer to Appendix C. ∎

Theorem 1 implies CHB can achieve a linear convergence rate which is of the
same order as that for HB [60] under Assumption 1 and Definition 1. If we set
$\rho_{3}=1$, $\delta\in(0,1)$,
$\alpha=\frac{1-\delta}{L},\eta_{1}=\frac{1-\alpha
L}{2\alpha},\varepsilon_{1}=\frac{(1-\alpha
L)(1-\alpha\mu)}{4\alpha^{2}M^{2}},\mbox{and}\
\beta=\frac{1}{2}\sqrt{(1-\alpha L)(1-\alpha\mu)},$ then

$\displaystyle c(\alpha,\beta,\varepsilon_{1})=\frac{1-\delta}{L/\mu},$ (17)

which is exactly the same value we obtain in HB if we also choose
$\alpha={(1-\delta)}/{L}$ [60]. There are an uncountable number of other
parameter settings in CHB that provide the same order convergence rate as HB.
However, the just predicted theoretical convergence rates of CHB and HB are
very conservative compared to what is observed in numerical examples.
Numerical results in Section IV indicate that CHB with $\alpha=1/L$ and
$\beta>0$ typically requires almost the same number of iterations as HB to
achieve the same value of the left-hand-side of (16) and often outperforms GD.
Convergence guarantees for CHB under general convex and nonconvex objective
function cases are given next. The proofs are provided in Appendix D and
Appendix E respectively.

######  Theorem 2.

(convex) Under _Assumption 1_ and _Definition 2_, if the constants $\alpha$,
$\beta$, and $\varepsilon_{1}$ are chosen so that (10)–(12) are satisfied with
$\sigma_{0}>0$ in (10) and $\sigma_{1}>0$ in (11), then

$\displaystyle
f(\bm{\theta}^{k})-f\left(\bm{\theta}^{*}\right)=\mathcal{O}(1/k).$ (18)

For nonconvex objective functions, the following convergence guarantee can be
established.

######  Theorem 3.

(nonconvex) Under _Assumption 1_, if the constants $\alpha$, $\beta$, and
$\varepsilon_{1}$ are chosen so that (10)–(12) are satisfied with
$\sigma_{0}>0$ in (10) and $\sigma_{1}>0$ in (11), then

$\displaystyle\lim_{k\rightarrow\infty}\left\|\nabla
f(\bm{\theta}^{k})\right\|^{2}\rightarrow 0.$ (19)

The following lemma illustrates a communication saving bound for the CHB
algorithm. As indicated in Figure 1, worker $m$ with a small smoothness
constant $L_{m}$ tends to transmit less frequently. The following lemma
formally describes the impact of $L_{m}$ on the communication savings of
worker $m$.

(a) Comm. of $9$ workers in CHB.

(b) Comm. of $9$ workers in HB.

Figure 1: Number of communications of different workers for the first $24$
iterations of CHB and HB in linear regression with $\alpha=1/L$,
$\varepsilon_{1}=0.1/(\alpha^{2}M^{2})$ and smoothness constants satisfying
$L_{1}<L_{2}<...<L_{9}$ with $L_{m}=(1.3^{m-1})^{2}$.

######  Lemma 2.

Under _Assumption 2_, if the smoothness constant $L_{m}$ of worker $m$
satisfies

$\displaystyle L_{m}^{2}\leq\varepsilon_{1},$ (20)

then after iteration $k$ in CHB, the number of communications between worker
$m$ and the server, denoted as $S_{m}$, can be upper bounded by

$\displaystyle S_{m}\leq\frac{k}{2}.$ (21)

###### Proof:

Please refer to Appendix F. ∎

The result in Lemma 2 indicates the smoothness of the local function decides
the number of communications needed by worker $m$. It makes sense that worker
$m$ with a small smoothness constant $L_{m}$ tends to transmit less frequently
because  $L_{m}$ indicates the maximum rate of change of worker $m$’s
gradient. It is worth mentioning that if (20) is true for all workers and the
conditions in (10)–(12) are satisfied with $\sigma_{0}>0$ in (10) and
$\sigma_{1}>0$ in (11), then we can save at least half of the transmissions
but we still achieve the same convergence rate as HB, which is known to be
good.

##  IV Numerical experiments

To validate the theoretical results on convergence analysis and communication
savings, the empirical performance of CHB is evaluated for (1) linear
regression (convex), (2) regularized logistic regression (strongly convex),
(3) lasso regression (nondifferentiable) and (4) training a neural network
(nonconvex). The objective error $f(\bm{\theta}^{k})-f(\bm{\theta}^{*})$
evaluates the algorithm progress for linear regression, regularized logistic
regression, and lasso regression. For training a neural network with one
hidden layer with $30$ nodes and the sigmoid activation function, we use the
norm of the gradient $\|\nabla^{k}\|$ as a figure of merit of the progress. We
consider a scenario with one server and nine workers. To benchmark CHB, we
compare its performance with GD [58], censoring-based GD (called LAG-WK) [54],
and the classical HB method [57] using synthetic datasets and real datasets.
Except as stated elsewhere, we set the constant $\beta=0.4$ for HB and CHB and
choose the same skip-transmission condition (8) for CHB and censoring-based
GD. Note that hereafter in the paper we refer to regularized logistic
regression as logistic regression. The specific loss function formats of the
above machine learning tasks can be found in [61]. For clarity of
presentation, we divide the experiments into two sets.

###  IV-A Experiment Set 1

Synthetic dataset tests. Let us initially consider the impact of the
smoothness constant on communication savings in synthetic datasets for linear
regression and logistic regression. Specifically, we consider linear
regression with increasing smoothness constants $L_{m}=(1.3^{m-1})^{2}$ for
$m=1,2,...,9$ in Figure 2 (same setting as Figure 1) and logistic regression
with common smoothness constants $L_{1}=L_{2}=...=L_{9}=4$ in Figure 3. For
these two cases, we randomly generate an independent sequence of labels (over
$n$), each with equal probability of $y_{n}=1$ or $y_{n}=-1$ for each worker
$m$. Then we randomly generate 50 independent instances
$\mathbf{x}_{n}\in\mathbb{R}^{50}$ (to pair with the labels) from a standard
normal distribution and use the same approach as [54] to rescale the data to
change the value of smoothness constants. To enable useful comparison, we set
$\alpha=1/L$ for all algorithms. For censoring-based GD and CHB, we choose
$\varepsilon_{1}=0.1/(\alpha^{2}M^{2})$ in (8). In Figure 2, it is not
surprising that CHB requires a fewer number of communications compared to HB
since we know from Figure 1 that workers with smaller smoothness constants
tend to transmit less frequently such that communications can be saved for
these workers. Interestingly, Figure 3 indicates that even when workers have
the same smoothness constants, CHB can still save communications. Both Figure
2 and Figure 3 indicate CHB outperforms the alternatives in terms of the
number of communications saved while still employing nearly the same number of
iterations as HB to achieve the same objective error. In these cases, CHB
requires not only a smaller number of communications but also a smaller number
of iterations, compared to censoring-based GD, to attain the same objective
error, .

Figure 2: Objective error versus the number of communications and iterations
for linear regression with increasing smoothness constant
$L_{m}=(1.3^{m-1})^{2}$ for $m=1,2,...,9$ in synthetic datasets.

Figure 3: Objective error versus the number of communications and iterations
for logistic regression with common smoothness constants
$L_{1}=L_{2}=...=L_{9}=4$ in synthetic datasets.

(a) Linear regression

(b) Linear regression

(c) Logistic regression

(d) Logistic regression

Figure 4: Objective error versus the number of communications and iterations
for linear regression and logistic regression in the _ijcnn1_ dataset.

(a) Lasso regression

(b) Lasso regression

(c) Neural network

(d) Neural network

Figure 5: Objective error versus the number of communications and iterations for lasso regression and training a neural network in the _ijcnn1_ dataset. Table I: Performance comparison for the _ijcnn1_ dataset. The objective error is $10^{-7}$, $10^{-7}$ and $10^{-5}$ for linear regression, lasso regression and logistic regression, respectively. The fixed number of iterations for training a neural network is $500$. | Linear regression | Lasso regression | Logistic regression | Neural network
---|---|---|---|---
Name | Comm. | Iter. | Comm. | Iter. | Comm. | Iter. | Comm. | Norm square grad.
CHB | 465 | 109 | 424 | 108 | 546 | 5324 | 1083 | $\mathbf{6.2402\times 10^{-6}}$
HB | $1071$ | $119$ | ${1071}$ | ${119}$ | $53244$ | $5916$ | $4500$ | $6.3354\times 10^{-6}$
LAG | $799$ | $203$ | ${608}$ | ${197}$ | $864$ | $9248$ | $1361$ | $3.7549\times 10^{-5}$
GD | $1917$ | $213$ | ${1899}$ | ${211}$ | $88866$ | $9874$ | $4500$ | $3.7885\times 10^{-5}$

Real dataset tests. We also test the performance on the real dataset _ijcnn1_
[62] which has 49990 samples and 22 features per sample. All samples are
evenly split between nine workers. In addition to linear regression and
logistic regression, we also consider lasso regression where we employ a
subgradient to replace the gradient. In each of these three regression tasks,
we set $\alpha=10^{-4}$ for HB, CHB, GD and censoring-based GD. For CHB and
censoring-based GD, we choose $\varepsilon_{1}=0.1/(\alpha^{2}M^{2})$. We set
the regularization parameter to $\lambda=0.001$ and $\lambda=0.5$ for logistic
regression and lasso regression, respectively. We stop the training process
when the objective error $f(\bm{\theta}^{k})-f(\bm{\theta}^{*})$ is less than
$10^{-7}$, $10^{-5}$, $10^{-7}$ for linear regression, logistic regression,
and lasso regression, respectively. Figure 4 indicates that given a target
accuracy, the number of iterations needed for CHB is almost the same as that
for HB for linear regression and logistic regression, and it also verifies
that CHB requires a smaller number of communications than the other methods.
Even for the nondifferentiable lasso regression task, the variant of CHB shows
similar performance in Figure 5(a) and Figure 5(b) as in linear regression and
logistic regression. In all regression tasks, CHB reduces the communications
compared to HB, by up to several orders of magnitude.

We also evaluate the performance of CHB for training a relatively small neural
network with one hidden layer with $30$ nodes. For training the neural
network, all algorithms are stopped after $500$ iterations with the step size
$\alpha=0.02$ while employing the regularization parameter $\lambda=1/49990$.
For CHB and censoring-based GD, we choose $\varepsilon_{1}=0.01$. Compared to
HB, GD, and censoring-based GD, Figure 5(c) and Figure 5(d) illustrate that
CHB has competitive convergence performance for this nonconvex problem with
the smallest number of communications. Table I summarizes the number of
communications and iterations to attain a given objective error which
indicates the desirable performance of CHB in terms of communication savings
and convergence rate. For linear and lasso regression, CHB reduces the
communications to less than half that needed for HB, and for logistic
regression the communications are reduced by two orders of magnitude compared
to HB. For the neural network training example, CHB and HB reduce the norm
square of the gradient by an order of magnitude compared to censoring-based GD
and GD, and CHB uses only $24\%$ of the communications needed for HB.
Additional numerical results on other real datasets and discussion of the
impact of step size are given next.

###  IV-B Experiment Set 2

To promote comparison, we first use the same real datasets with the same setup
as [54]. Specifically, we consider linear regression with the _Housing_ ,
_Body fat_ , and _Abalone_ datasets and logistic regression with the
_Ionosphere_ , _Adult fat_ , and _Derm_ datasets. We evenly split each dataset
into three workers and employ the minimal number of features among all
datasets as the number of features used in the test. Additionally, we also
consider lasso regression with the _Ionosphere_ , _Adult fat_ , and _Derm_
datasets. In all these regression tasks, we choose $\alpha=1/L$ for all four
algorithms. For CHB and censoring-based GD, we choose
$\varepsilon_{1}=0.1/(\alpha^{2}M^{2})$. For HB and CHB, we choose
$\beta=0.4$. The values of the regularization parameter for logistic
regression and lasso regression are $\lambda=0.001$ and $\lambda=0.1$,
respectively. All regression tasks stop when the objective error is less than
$10^{-7}$. Furthermore, we consider training a neural network with _Adult fat_
dataset where we choose $\alpha=0.01$ for all algorithms. For CHB and
censoring-based GD, we choose $\varepsilon_{1}=0.01$. Again, for HB and CHB,
we choose $\beta=0.4$. The regularization parameter we choose for the neural
network is $\lambda=1/1605$. The optimization process is stopped after $500$
iterations for training the neural network. Figure 6 and Figure 7 indicate the
effectiveness of CHB in terms of communication reduction for the four learning
tasks considered in this paper. The specific results are summarized in Table
II.

(a) Linear regression

(b) Linear regression

(c) Logistic regression

(d) Logistic regression

Figure 6: Objective error for linear regression and logistic regression in the
_Housing_ , _Body fat_ , _Abalone_ , _Ionosphere_ , _Adult fat_ , and _Derm_
datasets.

(a) Lasso regression

(b) Lasso regression

(c) Neural network

(d) Neural network

Figure 7: Objective error for lasso regression and training a neural network in the _Ionosphere_ , _Adult fat_ , and _Derm_ datasets. Table II: Performance comparison in the _Ionosphere, Adult,_and_ Derm_ dataset. The objective error is $10^{-7}$ for all linear regression tasks. The fixed number of iterations for training the neural network is $500$. | Linear regression | Lasso regression | Logistic regression | Neural network
---|---|---|---|---
Name | Comm. | Iter. | Comm. | Iter. | Comm. | Iter. | Comm. | Norm square grad.
CHB | 559 | 287 | 329 | 70 | 772 | 1842 | 1436 | $\mathbf{2.3566\times 10^{-4}}$
HB | $2808$ | $312$ | ${675}$ | ${75}$ | $17595$ | $1955$ | $4500$ | $2.3547\times 10^{-4}$
LAG | $762$ | $507$ | ${522}$ | ${130}$ | $1179$ | $3152$ | $1899$ | $2.9703\times 10^{-4}$
GD | $4824$ | $536$ | ${1224}$ | ${136}$ | $29439$ | $3271$ | $4500$ | $2.9752\times 10^{-4}$

We next test the performance of CHB on a larger dataset _MNIST_ [63]. In all
regression tasks, we set $\varepsilon_{1}=0.1/(\alpha^{2}M^{2})$ for CHB and
censoring-based GD. For HB and CHB, we set $\beta=0.4$. The largest number of
iterations for each algorithm in each regression task is fixed to be $2000$.
For linear regression and lasso regression, we set $\alpha=10^{-8}$. For
logistic regression, we use $\alpha=10^{-6}$. The values of regularization
parameter for lasso regression and logistic regression are $\lambda=0.5$ and
$\lambda=0.001$, respectively. In training a neural network with the
regularization parameter $\lambda=1/60000$, we choose $\alpha=0.02$ for all
algorithms. For CHB and censoring-based GD, we choose $\varepsilon_{1}=0.01$.
For HB and CHB, we choose the constant $\beta=0.4$. The largest number of
iterations is set to be $500$ in training a neural network. In Figure 8 and
Figure 9, for the fixed total number of iterations, CHB shows a competitive
communication saving performance while maintaining a relatively smaller
objective error compared to GD and censoring-based GD. Specific results are
summarized in Table III.

Furthermore, with the same parameter setting in the linear regression task on
the MNIST dataset except for the step size, we consider the impact of the step
size $\alpha$ on the number of communications needed to attain a target
objective error. Figure 10(a) and Figure 10(b) indicates that choosing a large
step size might speed up the optimization process (compare $\alpha=2.2\times
10^{-7}$ and $\alpha=2.2\times 10^{-8}$ at iteration $2000$ which corresponds
to the end point of each curve), but choosing a large step size might not save
the largest number of communications for CHB and censoring-based GD, e.g., to
attain the fixed objective error $\approx 10^{4}$, the number of
communications of censoring-based GD for $\alpha=2.2\times 10^{-7}$ is $303$
which is larger than that for $\alpha=2.2\times 10^{-8}$ with its number of
communications being $205$. Note that to attain the objective error $\approx
10^{4}$, even through censoring-based GD can save more communications than CHB
for the case when $\alpha=2.2\times 10^{-7}$, this step size is not a good
choice in term of communication savings. It is clear that censoring-based GD
can save more communications if we choose $\alpha=2.2\times 10^{-8}$ and in
this case CHB still outperforms censoring-based GD. In order to reduce the
total number of communications, a relatively small step size is preferable for
CHB and censoring-based GD. This illustrates the basic trade-off between the
number of iterations and the number of communication in some cases, which is
interesting. Communications can be saved using a relatively small step size
which results in more iterations to attain a target accuracy. Additionally,
Figure 10(d) illustrates that compared to GD and censoring-based GD, the
momentum term can help CHB converge for a relatively large step size case.

Now we consider the impact of $\varepsilon_{1}$ on the communication savings
and convergence of CHB. Specifically, with the same setting as Figure 3 except
$\varepsilon_{1}$, Figure 11 indicates that CHB with
$\varepsilon_{1}=0.01/(\alpha^{2}M^{2})$ performs similarly to the classical
HB in terms of the number of iterations while saving some communications for a
given objective error. This is reasonable since smaller $\varepsilon_{1}$
indicates less communication censoring. When we increase $\varepsilon_{1}$ to
$0.1/(\alpha^{2}M^{2})$, we can save more communications without too much
impact on convergence. However, when $\varepsilon_{1}$ is too large, e.g.,
$\varepsilon_{1}=1/(\alpha^{2}M^{2})$, increased communication censoring will
occur such that more iterations are required to attain a given objective
error. Figure 11 also indicates that CHB is able to achieve a good
communication-iteration trade-off by tuning $\varepsilon_{1}$.

From the previous numerical results where we plot the objective error versus
the number of iterations for CHB and censoring-based GD, e.g., Figure 3, we
can see that CHB provides faster convergence in these cases compared to
censoring-based GD due to the momentum term in the update rule. The averaged
per-communication descent is defined by
$(f(\bm{\theta}^{0})-f(\bm{\theta}^{k}))/(\text{the total number of
communications})$. Figure 12 shows that CHB has a larger averaged per-
communication descent than censoring-based GD for a given objective error in
this case. The results in Figure 12 also indicate that as the objective error
becomes smaller (iteration $k$ becomes larger), the averaged per-communication
descent for both CHB and censoring-based GD becomes smaller for both
algorithms. This is reasonable since the descent typically becomes smaller for
larger $k$ for both algorithms.

(a) Linear regression

(b) Linear regression

(c) Logistic regression

(d) Logistic regression

Figure 8: Objective error for linear regression and logistic regression in the
_MNIST_ dataset.

(a) Lasso regression

(b) Lasso regression

(c) Neural network

(d) Neural network

Figure 9: Objective error for lasso regression and training a neural network
in the _MNIST_ dataset.

(a) $\alpha=2.2\times 10^{-8}$

(b) $\alpha=2.2\times 10^{-7}$

(c) $\alpha=5.5\times 10^{-7}$

(d) $\alpha=8.8\times 10^{-7}$

Figure 10: Objective error for linear regression with different step sizes in
the _MNIST_ dataset.

Figure 11: Objective error versus the number of communications and iterations for logistic regression with different $\varepsilon_{1}$ in synthetic datasets. Figure 12: The averaged per-communication descent versus objective error for logistic regression with exactly the same setting as Figure 3. Table III: Performance comparison in the _MNIST_ dataset at the accomplishment of the largest number of iterations. | Linear regression | Lasso regression | Logistic regression | Neural network
---|---|---|---|---
Name | Comm. | Obj. error | Comm. | Obj. error | Comm. | Obj. error | Comm. | Norm square grad.
CHB | 191 | $\mathbf{3.1077\times 10^{3}}$ | 191 | $\mathbf{3.0901\times 10^{3}}$ | 45 | 0.5621 | 1123 | $\mathbf{5.4545\times 10^{-5}}$
HB | $18000$ | $3.6170\times 10^{3}$ | ${18000}$ | ${3.5995\times 10^{3}}$ | $18000$ | $4.0102$ | $4500$ | $5.4850\times 10^{-5}$
LAG | $179$ | $8.6826\times 10^{3}$ | ${184}$ | ${8.6483\times 10^{3}}$ | $90$ | $12.6540$ | $1532$ | $7.5920\times 10^{-5}$
GD | $18000$ | $9.1365\times 10^{3}$ | ${18000}$ | ${9.1007\times 10^{3}}$ | $18000$ | $16.1719$ | $4500$ | $7.6681\times 10^{-5}$

##  V Conclusion

This paper proposed a censoring-based heavy ball (CHB) method to optimize an
objective function which is a sum of local functions in a communication-
efficient manner. The key to save communications is to employ a censoring
strategy where a worker is not allowed to transmit if its gradient is not
sufficiently different from its previously transmitted one. The HB method
provides smoothing and so it is well matched with gradient censoring. Compared
to the classical HB method, CHB is able to significantly reduce the number of
communications while maintaining a fast convergence rate for strongly convex,
convex, and nonconvex objective functions. As we have shown, CHB can provide
significant communications savings with very little impact on convergence
rate, and CHB can also be tuned to trade-off communications and convergence
rate if desired. In all cases numerical results validate the communication
efficiency of CHB on both synthetic and real datasets. The CHB approach
provides a new tool for reducing communications, and so it can potentially be
applied along with other complementary techniques such as quantization,
compression, and gradient sparsification, to make CHB more efficient in terms
of bandwidth per communication as well as the number of communications.
Additionally, finding an optimal approach to tune the parameters of CHB, e.g.,
$\varepsilon_{1}$, is also very interesting. Finally, we note that worker
privacy and security are important considerations, and this should be combined
with CHB.

##  Appendix A Proof of a Useful Lemma

######  Lemma 3.

Suppose $f(\bm{\theta})$ is $L$-smooth and let ${\bm{\theta}}^{k+1}$ be
generated by (II), then the CHB algorithm yields the following descent

$\displaystyle
f(\bm{\theta}^{k+1})-f(\bm{\theta}^{k})\leq-\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}-\frac{1-\alpha
L}{2\alpha}\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle\qquad+\Big{\|}\sqrt{\frac{\alpha}{2}}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}+\frac{\beta}{\sqrt{2\alpha}}(\bm{\theta}^{k}-\bm{\theta}^{k-1})\Big{\|}^{2}.$
(22)

###### Proof:

From Assumption 1 we know [58]

$\displaystyle f\left(\bm{\theta}^{k+1}\right)-f\left(\bm{\theta}^{k}\right)$
$\displaystyle\leq\left\langle\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\rangle+\frac{L}{2}\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}.$
(23)

Using (6) in $\left\langle\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\rangle$
yields

$\displaystyle\left\langle\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\rangle$
$\displaystyle=-\alpha\Big{\langle}\nabla f\left(\bm{\theta}^{k}\right),\nabla
f\left(\bm{\theta}^{k}\right)-\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\rangle}$
$\displaystyle\qquad\qquad+\beta\left\langle\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\rangle$
(24) $\displaystyle=-\alpha\left\|\nabla
f(\bm{\theta}^{k})\right\|^{2}+\Big{\langle}\sqrt{\alpha}\nabla
f(\bm{\theta}^{k}),\sqrt{\alpha}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\rangle}$
$\displaystyle\qquad\qquad+\beta\left\langle\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\rangle$
(25) $\displaystyle=-\alpha\left\|\nabla
f(\bm{\theta}^{k})\right\|^{2}+\frac{\alpha}{2}\left\|\nabla
f(\bm{\theta}^{k})\right\|^{2}+\frac{\alpha}{2}\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\quad-\frac{\alpha}{2}\Big{\|}\nabla
f(\bm{\theta}^{k})-\\!\\!\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}+\beta\big{\langle}\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\big{\rangle}.$
(26)

To go from (25) to (26), the quality
$\left\langle\bm{x},\bm{y}\right\rangle=\frac{1}{2}\|\bm{x}\|^{2}+\frac{1}{2}\|\bm{y}\|^{2}-\frac{1}{2}\|\bm{x-y}\|^{2}$
is employed for the term $\langle\sqrt{\alpha}\nabla
f(\bm{\theta}^{k}),\sqrt{\alpha}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\rangle$.

From (6), we obtain that

$\displaystyle\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle=\alpha^{2}\Big{\|}\nabla
f\left(\bm{\theta}^{k}\right)-\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}+\beta^{2}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
$\displaystyle\qquad-2\alpha\beta\Big{\langle}\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}$
$\displaystyle\qquad+2\alpha\beta\Big{\langle}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k},\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}.$
(27)

Plugging (26) and (3) into (3), we obtain

$\displaystyle f\left(\bm{\theta}^{k+1}\right)-f\left(\bm{\theta}^{k}\right)$
$\displaystyle\leq-\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}-\frac{\alpha(1-\alpha
L)}{2}\Big{\|}\nabla
f\left(\bm{\theta}^{k}\right)-\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\quad+\frac{\alpha}{2}\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}+\frac{L\beta^{2}}{2}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
$\displaystyle\quad+\beta(1-\alpha L)\Big{\langle}\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}$
$\displaystyle\quad+\alpha\beta
L\Big{\langle}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k},\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}.$
(28)

Multiplying both sides of (3) by a constant $(1-\alpha L)/(2\alpha)$ implies

$\displaystyle\frac{1-\alpha
L}{2\alpha}\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle=\frac{\alpha(1-\alpha L)}{2}\Big{\|}\nabla
f\left(\bm{\theta}^{k}\right)\\!\\!-\\!\\!\\!\\!\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\quad\qquad+\frac{(1-\alpha
L)\beta^{2}}{2\alpha}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
$\displaystyle\quad\qquad-\beta(1-\alpha L)\Big{\langle}\nabla
f\left(\bm{\theta}^{k}\right),\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}$
$\displaystyle\quad\qquad+(1-\alpha
L)\beta\Big{\langle}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k},\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}.$
(29)

Adding (3) to (3) yields

$\displaystyle f\left(\bm{\theta}^{k+1}\right)\\!+\\!\frac{1-\alpha
L}{2\alpha}\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle\leq f\left(\bm{\theta}^{k}\right)-\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\frac{\beta^{2}}{2\alpha}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
$\displaystyle\quad+\frac{\alpha}{2}\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}+\beta\Big{\langle}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k},\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{\rangle}$
(30) $\displaystyle\\!\leq
f\left(\bm{\theta}^{k}\right)-\\!\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}$
$\displaystyle\quad+\Big{\|}\sqrt{\frac{\alpha}{2}}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}+\frac{\beta}{\sqrt{2\alpha}}(\bm{\theta}^{k}-\bm{\theta}^{k-1})\Big{\|}^{2}.$
(31)

The result in (3) follows after rearranging terms in (31). ∎

##  Appendix B Proof of Lemma 1

With $\mathbb{L}(\bm{\theta}^{k})$ in (9), it can be shown that

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle=f(\bm{\theta}^{k+1})-f(\bm{\theta}^{k})+\eta_{1}\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}-\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}.$
(32)

Plugging (3) into (B) yields

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq-\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\left(\eta_{1}-\frac{1-\alpha
L}{2\alpha}\right)\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle\qquad+\Big{\|}\sqrt{\frac{\alpha}{2}}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}+\frac{\beta}{\sqrt{2\alpha}}(\bm{\theta}^{k}-\bm{\theta}^{k-1})\Big{\|}^{2}$
$\displaystyle\qquad-\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(33) $\displaystyle\leq-\frac{\alpha}{2}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\left(\eta_{1}-\frac{1-\alpha
L}{2\alpha}\right)\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle\qquad+\frac{\alpha}{2}(1+\rho_{3})\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\qquad+\frac{\beta^{2}}{{2\alpha}}(1+\rho^{-1}_{3})\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}-\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(34)

where $\rho_{3}$ is any positive number. In going from (33) to (34), we employ
Young’s inequality:
$\|\bm{x+y}\|^{2}\leq(1+\rho)\|\bm{x}\|^{2}+(1+\rho^{-1})\|\bm{y}\|^{2},\forall\rho>0$.
From (6), we have

$\displaystyle\left\|\bm{\theta}^{k+1}-\bm{\theta}^{k}\right\|^{2}$
$\displaystyle=\Big{\|}-\alpha\Big{(}\nabla
f(\bm{\theta}^{k})-\\!\\!\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{)}+\beta\Big{(}\bm{\theta}^{k}-\bm{\theta}^{k-1}\Big{)}\Big{\|}^{2}$
(35)
$\displaystyle\leq\alpha^{2}(1+\rho_{1})\Bigg{(}(1+\rho_{2})\Big{\|}\nabla
f(\bm{\theta}^{k})\Big{\|}^{2}$
$\displaystyle\qquad\qquad+(1+\rho_{2}^{-1})\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}\Bigg{)}$
$\displaystyle\qquad+\beta^{2}(1+\rho_{1}^{-1})\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(36)

where $\rho_{1}$ and $\rho_{2}$ are any positive numbers, and the inequality
in (36) is obtained using Young’s inequality. Using (36) in (34) along with
$\eta_{1}-\frac{1-\alpha L}{2\alpha}\geq 0$, yields

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq\left(-\frac{\alpha}{2}+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2})\right)\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}$
$\displaystyle\quad+\Bigg{(}\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2}^{-1})$
$\displaystyle\qquad\qquad+\frac{\alpha}{2}(1+\rho_{3})\Bigg{)}\left\|\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\right\|^{2}$
$\displaystyle\quad+\Bigg{(}\frac{\beta^{2}}{2\alpha}(1+\rho_{3}^{-1})-\eta_{1}$
$\displaystyle\qquad+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\beta^{2}(1+\rho_{1}^{-1})\Bigg{)}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}.$
(37)

Employing the inequality $\left\|\sum_{n=1}^{N}\bm{x}_{n}\right\|^{2}\leq
N\sum_{n=1}^{N}\left\|\bm{x}_{n}\right\|^{2}$,
$\left\|\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\right\|^{2}$ can be
bounded by

$\displaystyle\Big{\|}\sum_{m\in\mathcal{M}_{c}^{k}}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\leq|\mathcal{M}_{c}^{k}|\sum_{m\in\mathcal{M}_{c}^{k}}\Big{\|}\delta\nabla_{m}^{k}\Big{\|}^{2}$
$\displaystyle\leq|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}$
(38)

where (38) is obtained using the CHB-skip-transmission condition in (8).

Plugging (38) into (B) with
$\gamma\buildrel\Delta\over{=}\frac{\alpha}{2}(1+\rho_{3})+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2}^{-1})$ and
$\eta_{1}-\frac{1-\alpha L}{2\alpha}\geq 0$, we obtain

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq\left(-\frac{\alpha}{2}+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2})\right)\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}$
$\displaystyle\qquad+\Bigg{(}\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\beta^{2}(1+\rho_{1}^{-1})+|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}\gamma$
$\displaystyle\qquad+\frac{\beta^{2}}{2\alpha}(1+\rho_{3}^{-1})-\eta_{1}\Bigg{)}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}.$
(39)

Note that $\eta_{1}-\frac{1-\alpha L}{2\alpha}\geq 0$ implies
$\gamma\geq\frac{\alpha}{2}(1+\rho_{3})>0$. The proof is complete after
defining the non-negative constants $\sigma_{0}$ and $\sigma_{1}$ as shown in
(10) and (11), respectively. Since the expressions of $\sigma_{0}$ and
$\sigma_{1}$ are complicated, we provide several choices of parameters in the
following.

####  Parameter Choices

First note that (10)–(12) are equivalent to

$\displaystyle\frac{1}{2\eta_{1}+L}\leq\alpha\leq\frac{1+(1+\rho_{1})(1+\rho_{2})}{(2\eta_{1}+L)(1+\rho_{1})(1+\rho_{2})},$
(40)
$\displaystyle\beta\leq\sqrt{\frac{2\alpha\eta_{1}}{(1+\rho_{3}^{-1})+(1+\rho_{1}^{-1})(2\alpha\eta_{1}-1+\alpha
L)}},$ (41)
$\displaystyle\varepsilon_{1}\leq\frac{\eta_{1}-\beta^{2}\big{(}\frac{1+\rho_{3}^{-1}}{2\alpha}+(\eta_{1}-\frac{1-\alpha
L}{2\alpha})(1+\rho_{1}^{-1})\big{)}}{|\mathcal{M}_{c}^{k}|^{2}\gamma}.$ (42)

$\bullet$ Setting $\eta_{1}=\frac{1-\alpha L}{2\alpha}$, (40)–(42) are
equivalent to

$\displaystyle\alpha$
$\displaystyle\leq\frac{1}{L},\quad\beta\leq\sqrt{\frac{1-\alpha
L}{1+\rho_{3}^{-1}}},\quad\varepsilon_{1}\leq\frac{(1-\alpha
L)-\beta^{2}(1+\rho_{3}^{-1})}{\alpha^{2}(1+\rho_{3})|\mathcal{M}_{c}^{k}|^{2}}.$
(43)

$\bullet$ Imposing $\eta_{1}=0$, $\rho_{1}=0$, and $\rho_{2}=0$ shows that
(40)–(42) degenerate to $1/L\leq\alpha\leq 2/L$, $\beta=0$, and
$\varepsilon_{1}=0$.

$\bullet$ For $\alpha=1/L$ and $\eta_{1}>0$, we find (40)–(42) are equivalent
to

$\displaystyle 0$
$\displaystyle\leq\eta_{1}\leq\frac{L}{2(1+\rho_{1})(1+\rho_{2})},$
$\displaystyle\beta^{2}$
$\displaystyle\leq\frac{2\eta_{1}}{2\eta_{1}(1+\rho_{1}^{-1})+L(1+\rho_{3}^{-1})},$
$\displaystyle\varepsilon_{1}$
$\displaystyle\leq\frac{L^{2}\Big{(}2\eta_{1}-\beta^{2}\big{(}{L}(1+\rho_{3}^{-1})+2\eta_{1}(1+\rho_{1}^{-1})\big{)}\Big{)}}{|\mathcal{M}_{c}^{k}|^{2}\Big{(}L(1+\rho_{3})+2\eta_{1}(1+\rho_{1})(1+\rho_{2}^{-1})\Big{)}}.$
(44)

##  Appendix C Proof of Theorem 1

From strong convexity from Definition 1, $f(\bm{\theta})$ satisfies [58]

$\displaystyle
2\mu\left(f\left(\bm{\theta}^{k}\right)-f\left(\bm{\theta}^{*}\right)\right)\leq\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}$ (45)

where $\bm{\theta}^{*}$ denotes the minimizer of (1). Using (45) in (B) with
$\sigma_{0}\geq 0$ in (10) and $\eta_{1}\neq 0$ yields

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq\Bigg{(}2\mu\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\alpha^{2}(1+\rho_{1})(1+\rho_{2})$
$\displaystyle\qquad\qquad-\alpha\mu\Bigg{)}\left(f(\bm{\theta}^{k})-f(\bm{\theta}^{*})\right)$
$\displaystyle\qquad+\Bigg{(}\frac{\beta^{2}}{2\alpha}(1+\rho_{3}^{-1})-\eta_{1}+\Big{(}\eta_{1}-\frac{1-\alpha
L}{2\alpha}\Big{)}\beta^{2}(1+\rho_{1}^{-1})$
$\displaystyle\qquad\qquad+|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}\gamma\Bigg{)}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(46) $\displaystyle=-\Bigg{(}-\Big{(}2\eta_{1}-\frac{1-\alpha
L}{\alpha}\Big{)}\alpha^{2}\mu(1+\rho_{1})(1+\rho_{2})$
$\displaystyle\qquad\qquad+\alpha\mu\Bigg{)}\left(f(\bm{\theta}^{k})-f(\bm{\theta}^{*})\right)$
$\displaystyle\qquad-\Bigg{(}1-\frac{\beta^{2}}{2\alpha\eta_{1}}(1+\rho_{3}^{-1})-\Big{(}1-\frac{1-\alpha
L}{2\alpha\eta_{1}}\Big{)}\beta^{2}(1+\rho_{1}^{-1})$
$\displaystyle\qquad\qquad-\frac{|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}\gamma}{\eta_{1}}\Bigg{)}\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(47)

Define

$\displaystyle c\left(\alpha,\beta,\varepsilon_{1}\right)$
$\displaystyle\buildrel\Delta\over{=}\min\Bigg{\\{}{\alpha}\mu-\Big{(}2\eta_{1}-\frac{1-\alpha
L}{\alpha}\Big{)}\alpha^{2}\mu(1+\rho_{1})(1+\rho_{2}),$
$\displaystyle\qquad\min_{k}\big{\\{}1-\frac{\beta^{2}}{2\alpha\eta_{1}}(1+\rho_{3}^{-1})-\Big{(}1-\frac{1-\alpha
L}{2\alpha\eta_{1}}\Big{)}\beta^{2}(1+\rho_{1}^{-1})$
$\displaystyle\qquad\qquad\qquad-\frac{|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}\gamma}{\eta_{1}}\big{\\}}\Bigg{\\}}$
(48)
$\displaystyle=\min\big{\\{}2\sigma_{0}\mu,\min_{k}\\{\sigma_{1}\\}/\eta_{1}\big{\\}}.$
(49)

The result in (49) follows from the expressions for $\sigma_{0}$ and
$\sigma_{1}$ in (10) and (11), respectively. Using (47) and (48) yields

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq-c\left(\alpha,\beta,\varepsilon_{1}\right)\left(f(\bm{\theta}^{k})-f\left(\bm{\theta}^{*}\right)+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}\right)$
(50)
$\displaystyle=-c\left(\alpha,\beta,\varepsilon_{1}\right)\mathbb{L}(\bm{\theta}^{k})$
(51)

which implies

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})\leq\left(1-c\left(\alpha,\beta,\varepsilon_{1}\right)\right)\mathbb{L}(\bm{\theta}^{k}).$
(52)

It is clear that when (10)–(11) are satisfied with $\sigma_{0}>0$ in (10) and
$\sigma_{1}>0$ in (11), we have
$c\left(\alpha,\beta,\varepsilon_{1}\right)>0$. If (12) is satisfied, then we
can obtain $c\left(\alpha,\beta,\varepsilon_{1}\right)<1$ from (48). Thus, we
have $c\left(\alpha,\beta,\varepsilon_{1}\right)\in(0,1)$. The result in (52)
indicates the Q-linear convergence of $\mathbb{L}(\bm{\theta}^{k})$. Since
$\eta_{1}$ is non-negative in the definition of $\mathbb{L}(\bm{\theta}^{k})$,
the result in (52) implies that

$\displaystyle
f\left(\bm{\theta}^{k}\right)-f\left(\bm{\theta}^{*}\right)\leq\left(1-c\left(\alpha,\beta,\varepsilon_{1}\right)\right)^{k}\mathbb{L}(\bm{\theta}^{0}),$
(53)

which completes the proof. Consider a case with $\eta_{1}-\frac{1-\alpha
L}{2\alpha}=0$ with $\eta_{1}\neq 0$. Then (12) yields
$\gamma=\alpha(1+\rho_{3})/2$, and (48) yields

$\displaystyle c\left(\alpha,\beta,\varepsilon_{1}\right)$
$\displaystyle=\min_{k}\Bigg{\\{}{\alpha}\mu,1-\frac{\beta^{2}}{1-\alpha
L}(1+\rho_{3}^{-1})-\frac{\alpha^{2}(1+\rho_{3})|\mathcal{M}_{c}^{k}|^{2}\varepsilon_{1}}{1-\alpha
L}\Bigg{\\}}.$ (54)

Setting $\rho_{3}=1$, $\delta\in(0,1)$, and $\alpha=\frac{1-\delta}{L}$, gives

$\displaystyle\eta_{1}=\frac{1-\alpha
L}{2\alpha},\varepsilon_{1}=\frac{(1-\alpha
L)(1-\alpha\mu)}{4\alpha^{2}M^{2}},$ $\displaystyle\qquad\mbox{and}\
\beta=\frac{1}{2}\sqrt{(1-\alpha L)(1-\alpha\mu)},$ (55)

and (C) yields

$\displaystyle c\left(\alpha,\beta,\varepsilon_{1}\right)$
$\displaystyle=\min_{k}\Bigg{\\{}\alpha\mu,1-\frac{1-\alpha\mu}{2}\left(1+\frac{|\mathcal{M}_{c}^{k}|^{2}}{M^{2}}\right)\Bigg{\\}}$
$\displaystyle=\alpha\mu.$ (56)

It follows that

$\displaystyle\frac{\mathbb{L}(\bm{\theta}^{k+1})}{\mathbb{L}(\bm{\theta}^{1})}\leq\left(1-\frac{1-\delta}{L/\mu}\right)^{k}\leq\epsilon.$
(57)

Rearranging terms in (57), yields

$\displaystyle\log(\frac{1}{\epsilon})\leq
k\log\left(1+\frac{1}{\frac{L/\mu}{1-\delta}-1}\right)\leq\frac{k}{\frac{L/\mu}{1-\delta}-1}$
(58)

such that the iteration complexity $\mathbb{I}_{CHB}(\epsilon)$ is

$\displaystyle\mathbb{I}_{CHB}(\epsilon)=\frac{L/\mu}{1-\delta}\log(\frac{1}{\epsilon}).$
(59)

##  Appendix D Proof of Theorem 2

The following is inspired by the previous work in [54] which can be regarded
as a special case of CHB without the momentum term (with $\beta=0$). We start
with a lemma that will be helpful later.

######  Lemma 4.

Under Definition 2, the Lyapunov function $\mathbb{L}(\bm{\theta}^{k})$
satisfies

$\displaystyle\mathbb{L}(\bm{\theta}^{k})\leq\sqrt{\Big{(}\|\nabla
f(\bm{\theta}^{k})\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}}$
$\displaystyle\qquad\qquad\cdot\sqrt{\Big{(}\|\bm{\theta}^{k}-\bm{\theta}^{*}\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}}.$
(60)

###### Proof:

Using Definition 2 (convexity)

$\displaystyle f(\bm{\theta}^{k})-f(\bm{\theta}^{*})\leq\left\langle\nabla
f(\bm{\theta}^{k}),\bm{\theta}^{k}-\bm{\theta}^{*}\right\rangle.$ (61)

Thus

$\displaystyle\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle=f(\bm{\theta}^{k})-f\left(\bm{\theta}^{*}\right)+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}$
$\displaystyle\leq\left\langle\nabla
f(\bm{\theta}^{k}),\bm{\theta}^{k}-\bm{\theta}^{*}\right\rangle$
$\displaystyle\qquad+\left\langle\sqrt{\eta_{1}}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|,\sqrt{\eta_{1}}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|\right\rangle$
(62) $\displaystyle=\Big{\langle}\left[\nabla
f(\bm{\theta}^{k}),\sqrt{\eta_{1}}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|\right]^{\top},$
$\displaystyle\qquad\qquad\left[\bm{\theta}^{k}-\bm{\theta}^{*},\sqrt{\eta_{1}}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|\right]^{\top}\Big{\rangle}$
(63) $\displaystyle\leq\sqrt{\Big{(}\|\nabla
f(\bm{\theta}^{k})\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}}$
$\displaystyle\qquad\qquad\cdot\sqrt{\Big{(}\|\bm{\theta}^{k}-\bm{\theta}^{*}\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}}.$
(64)

We obtained (62) by using (61). We use (63) and the inequality
$\langle\bm{x},\bm{y}\rangle\leq\|\bm{x}\|\|\bm{y}\|$ to obtain (64). This
completes the proof. ∎

Given Assumption 1 and assuming the constants $\alpha$, $\beta$, and
$\varepsilon_{1}$ satisfy (10)–(12) while $\sigma_{0}>0$ and $\sigma_{1}>0$,
then (13) of Lemma 1 suggests that

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq-\sigma_{0}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}-\sigma_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(65)
$\displaystyle\leq-\min_{k}\\{\sigma_{0},\frac{\sigma_{1}}{\eta_{1}}\\}\left(\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}\right).$
(66)

Further, $\min_{k}\\{\sigma_{0},\frac{\sigma_{1}}{\eta_{1}}\\}>0$ with
$\sigma_{0}$ and $\sigma_{1}$ provided in (10) and (11). Note that (66) yields

$\displaystyle\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
$\displaystyle\leq\frac{1}{\min_{k}\\{\sigma_{0},\sigma_{1}/\eta_{1}\\}}\left(\mathbb{L}(\bm{\theta}^{k})-\mathbb{L}(\bm{\theta}^{k+1})\right).$
(67)

Assumption 1 implies that
$\left\|\bm{\theta}^{k}-\bm{\theta}^{*}\right\|<+\infty$ and
$\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|<+\infty$. It follows that

$\displaystyle\|\bm{\theta}^{k}-\bm{\theta}^{*}\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\leq
N.$ (68)

for finite $N$. We can use (D) and (68) in (64) to show that

$\displaystyle(\mathbb{L}(\bm{\theta}^{k}))^{2}$
$\displaystyle\leq\Big{(}\|\nabla
f(\bm{\theta}^{k})\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}$
$\displaystyle\qquad\quad\Big{(}\|\bm{\theta}^{k}-\bm{\theta}^{*}\|^{2}+\eta_{1}\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\|^{2}\Big{)}$
(69)
$\displaystyle\leq\frac{N}{\min_{k}\\{\sigma_{0},\sigma_{1}/\eta_{1}\\}}\left(\mathbb{L}(\bm{\theta}^{k})-\mathbb{L}(\bm{\theta}^{k+1})\right).$
(70)

Lemma 1 implies that
$\mathbb{L}(\bm{\theta}^{k})\mathbb{L}(\bm{\theta}^{k+1})\leq(\mathbb{L}(\bm{\theta}^{k}))^{2}$
so that (70) yields

$\displaystyle\mathbb{L}(\bm{\theta}^{k})\mathbb{L}(\bm{\theta}^{k+1})\leq\frac{N}{\min_{k}\\{\sigma_{0},\sigma_{1}/\eta_{1}\\}}\left(\mathbb{L}(\bm{\theta}^{k})-\mathbb{L}(\bm{\theta}^{k+1})\right)$
(71)

or

$\displaystyle\frac{1}{\mathbb{L}(\bm{\theta}^{k+1})}-\frac{1}{\mathbb{L}(\bm{\theta}^{k})}\geq\frac{\min_{k}\\{\sigma_{0},\sigma_{1}/\eta_{1}\\}}{N}.$
(72)

It follows that

$\displaystyle\frac{1}{\mathbb{L}(\bm{\theta}^{K})}\geq\frac{1}{\mathbb{L}(\bm{\theta}^{K})}-\frac{1}{\mathbb{L}(\bm{\theta}^{0})}\geq\frac{K\min_{k}\\{\sigma_{0},\sigma_{1}/\eta_{1}\\}}{N},$
(73)

which completes the proof.

##  Appendix E Proof of Theorem 3

This section again builds on [54]. From Lemma 1

$\displaystyle\mathbb{L}(\bm{\theta}^{k+1})-\mathbb{L}(\bm{\theta}^{k})$
$\displaystyle\leq-\sigma_{0}\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}-\sigma_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}$
(74)
$\displaystyle\leq-\min_{k}\\{\sigma_{0},\frac{\sigma_{1}}{\eta_{1}}\\}\left(\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}\right).$
(75)

The last equation is summed over $k$ from $1$ to $K$ to yield

$\displaystyle\mathbb{L}(\bm{\theta}^{1})-\mathbb{L}(\bm{\theta}^{K+1})$
$\displaystyle\geq\min_{k}\\{\sigma_{0},\frac{\sigma_{1}}{\eta_{1}}\\}\sum_{k=1}^{K}\left(\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}\right).$
(76)

Note that
$\mathbb{L}(\bm{\theta}^{1})-\mathbb{L}(\bm{\theta}^{K+1})\leq\mathbb{L}(\bm{\theta}^{1})<\infty$
so that

$\displaystyle\lim_{K\rightarrow\infty}\sum_{k=1}^{K}\left(\left\|\nabla
f\left(\bm{\theta}^{k}\right)\right\|^{2}+\eta_{1}\left\|\bm{\theta}^{k}-\bm{\theta}^{k-1}\right\|^{2}\right)<\infty$
(77)

or

$\displaystyle\lim_{K\rightarrow\infty}\left\|\nabla
f\left(\bm{\theta}^{K}\right)\right\|^{2}\rightarrow 0.$ (78)

##  Appendix F Proof of Lemma 2

Suppose that worker $m$ has communicated with the server at iteration $(k-1)$
which means $\hat{\bm{\theta}}_{m}^{k-1}=\bm{\theta}^{k-1}$, we can obtain

$\displaystyle\left\|\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k-1})-\nabla
f_{m}({\bm{\theta}}^{k})\right\|^{2}\leq
L_{m}^{2}\left\|\hat{\bm{\theta}}_{m}^{k-1}-\bm{\theta}^{k}\right\|^{2}$ (79)
$\displaystyle=L_{m}^{2}\left\|\bm{\theta}^{k-1}-\bm{\theta}^{k}\right\|^{2}$
(80)

where (79) is obtained using the definition of the smoothness constant in
Assumption 1.

If (20) is true, then
$L_{m}^{2}\left\|\bm{\theta}^{k-1}-\bm{\theta}^{k}\right\|^{2}$ can be bounded
by $\varepsilon_{1}\left\|\bm{\theta}^{k-1}-\bm{\theta}^{k}\right\|^{2}$.
Thus, we have

$\displaystyle\left\|\nabla f_{m}(\hat{\bm{\theta}}_{m}^{k-1})-\nabla
f_{m}({\bm{\theta}}^{k})\right\|^{2}\leq\varepsilon_{1}\left\|\bm{\theta}^{k-1}-\bm{\theta}^{k}\right\|^{2}$
(81)

which is equivalent to the CHB-skip-transmission condition in (8). The result
in (81) indicates that worker $m$ will not transmit at iteration $k$ since the
CHB-skip-transmission condition is satisfied. Thus, in the first $k$
iterations, the worker $m$ communicates with the server at most $k/2$ times if
(20) holds.

## References

  * [1] S. Liu, N. Gupta, and N. H. Vaidya, “Approximate byzantine fault-tolerance in distributed optimization,” in _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_ , 2021, pp. 379–389.
  * [2] B. Turan, C. A. Uribe, H.-T. Wai, and M. Alizadeh, “Robust distributed optimization with randomly corrupted gradients,” _IEEE Transactions on Signal Processing_ , 2022.
  * [3] X. Li, L. Xie, and Y. Hong, “Distributed aggregative optimization over multi-agent networks,” _IEEE Transactions on Automatic Control_ , 2021.
  * [4] Y. Zhang, Y. Lou, Y. Hong, and L. Xie, “Distributed projection-based algorithms for source localization in wireless sensor networks,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 6, pp. 3131–3142, 2015\.
  * [5] Y. Chen, R. S. Blum, B. M. Sadler, and J. Zhang, “Testing the structure of a gaussian graphical model with reduced transmissions in a distributed setting,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 20, pp. 5391–5401, 2019.
  * [6] Y. Chen, B. M. Sadler, and R. S. Blum, “Ordered transmission for efficient wireless autonomy,” in _2018 52nd Asilomar Conference on Signals, Systems, and Computers_. IEEE, 2018, pp. 1299–1303.
  * [7] Y. Chen, R. S. Blum, and B. M. Sadler, “Optimal quickest change detection in sensor networks using ordered transmissions,” in _2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2020, pp. 1–5.
  * [8] ——, “Ordering for communication-efficient quickest change detection in a decomposable graphical model,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 4710–4723, 2021.
  * [9] G. Binetti, A. Davoudi, F. L. Lewis, D. Naso, and B. Turchiano, “Distributed consensus-based economic dispatch with transmission losses,” _IEEE Transactions on Power Systems_ , vol. 29, no. 4, pp. 1711–1720, 2014.
  * [10] J. Park, S. Samarakoon, A. Elgabli, J. Kim, M. Bennis, S.-L. Kim, and M. Debbah, “Communication-efficient and distributed learning over wireless networks: Principles and applications,” _Proceedings of the IEEE_ , vol. 109, no. 5, pp. 796–819, 2021.
  * [11] S. Vlaski and A. H. Sayed, “Distributed learning in non-convex environments—part i: Agreement at a linear rate,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 1242–1256, 2021.
  * [12] A. Imteaj, U. Thakker, S. Wang, J. Li, and M. H. Amini, “A survey on federated learning for resource-constrained iot devices,” _IEEE Internet of Things Journal_ , vol. 9, no. 1, pp. 1–24, 2021.
  * [13] Y. Chen, R. S. Blum, and B. M. Sadler, “Communication efficient federated learning via ordered admm in a fully decentralized setting,” in _2022 56th Annual Conference on Information Sciences and Systems (CISS)_. IEEE, 2022, pp. 96–100.
  * [14] V. Smith, S. Forte, C. Ma, M. Takáč, M. I. Jordan, and M. Jaggi, “Cocoa: A general framework for communication-efficient distributed optimization,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 8590–8638, 2017.
  * [15] Y. Chen, “Ordered transmissions, estimation, and parameter learning,” Ph.D. dissertation, Lehigh University, 2021.
  * [16] Y. Zhou, Q. Ye, and J. Lv, “Communication-efficient federated learning with compensated overlap-fedavg,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 33, no. 1, pp. 192–205, 2021.
  * [17] E. Ozfatura, K. Ozfatura, and D. Gündüz, “Time-correlated sparsification for communication-efficient federated learning,” in _2021 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2021, pp. 461–466.
  * [18] D. Jhunjhunwala, A. Gadhikar, G. Joshi, and Y. C. Eldar, “Adaptive quantization of model updates for communication-efficient federated learning,” in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 3110–3114.
  * [19] C. Li, G. Li, and P. K. Varshney, “Communication-efficient federated learning based on compressed sensing,” _IEEE Internet of Things Journal_ , vol. 8, no. 20, pp. 15 531–15 541, 2021.
  * [20] H. Gao, A. Xu, and H. Huang, “On the convergence of communication-efficient local sgd for federated learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 9, 2021, pp. 7510–7518.
  * [21] Y. Chen, R. S. Blum, M. Takáč, and B. M. Sadler, “Distributed learning with sparsified gradient differences,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 16, no. 3, pp. 585–600, 2022.
  * [22] Y. Chen, B. M. Sadler, and R. S. Blum, “Ordered gradient approach for communication-efficient distributed learning,” in _2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2020, pp. 1–5.
  * [23] F. Sattler, A. Marban, R. Rischke, and W. Samek, “Cfd: Communication-efficient federated distillation via soft-label quantization and delta coding,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 4, pp. 2025–2038, 2021.
  * [24] R. Hönig, Y. Zhao, and R. Mullins, “Dadaquant: Doubly-adaptive quantization for communication-efficient federated learning,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 8852–8866.
  * [25] X. Fan, Y. Wang, Y. Huo, and Z. Tian, “Communication-efficient federated learning through 1-bit compressive sensing and analog aggregation,” in _2021 IEEE International Conference on Communications Workshops (ICC Workshops)_. IEEE, 2021, pp. 1–6.
  * [26] Y. Wang, Y. Xu, Q. Shi, and T.-H. Chang, “Quantized federated learning under transmission delay and outage constraints,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 1, pp. 323–341, 2021.
  * [27] A. R. Elkordy and A. S. Avestimehr, “Heterosag: Secure aggregation with heterogeneous quantization in federated learning,” _IEEE Transactions on Communications_ , vol. 70, no. 4, pp. 2372–2386, 2022.
  * [28] S. Chen, C. Shen, L. Zhang, and Y. Tang, “Dynamic aggregation for heterogeneous quantization in federated learning,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 10, pp. 6804–6819, 2021.
  * [29] A. Panda, S. Mahloujifar, A. N. Bhagoji, S. Chakraborty, and P. Mittal, “Sparsefed: Mitigating model poisoning attacks in federated learning with sparsification,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2022, pp. 7587–7624.
  * [30] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani, “Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 606–14 619, 2021.
  * [31] S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified sgd with memory,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 4447–4458.
  * [32] M. Zinkevich, M. Weimer, L. Li, and A. J. Smola, “Parallelized stochastic gradient descent,” in _Advances in neural information processing systems_ , 2010, pp. 2595–2603.
  * [33] Y. Zhang, J. C. Duchi, and M. J. Wainwright, “Communication-efficient algorithms for statistical optimization,” _The Journal of Machine Learning Research_ , vol. 14, no. 1, pp. 3321–3363, 2013.
  * [34] R. Mcdonald, M. Mohri, N. Silberman, D. Walker, and G. S. Mann, “Efficient large-scale distributed training of conditional maximum entropy models,” in _Advances in neural information processing systems_ , 2009, pp. 1231–1239.
  * [35] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas, “Federated learning of deep networks using model averaging. corr abs/1602.05629 (2016),” _arXiv preprint arXiv:1602.05629_ , 2016.
  * [36] O. Shamir, N. Srebro, and T. Zhang, “Communication-efficient distributed optimization using an approximate newton-type method,” in _International conference on machine learning_ , 2014, pp. 1000–1008.
  * [37] A. Agarwal, O. Chapelle, M. Dudík, and J. Langford, “A reliable effective terascale linear learning system,” _The Journal of Machine Learning Research_ , vol. 15, no. 1, pp. 1111–1133, 2014.
  * [38] A. Bordes, L. Bottou, and P. Gallinari, “Sgd-qn: Careful quasi-newton stochastic gradient descent,” _Journal of Machine Learning Research_ , vol. 10, no. Jul, pp. 1737–1754, 2009.
  * [39] R. H. Byrd, S. L. Hansen, J. Nocedal, and Y. Singer, “A stochastic quasi-newton method for large-scale optimization,” _SIAM Journal on Optimization_ , vol. 26, no. 2, pp. 1008–1031, 2016.
  * [40] P. Moritz, R. Nishihara, and M. Jordan, “A linearly-convergent stochastic l-bfgs algorithm,” in _Artificial Intelligence and Statistics_ , 2016, pp. 249–258.
  * [41] R. Gower, D. Goldfarb, and P. Richtárik, “Stochastic block bfgs: Squeezing more curvature out of data,” in _International Conference on Machine Learning_ , 2016, pp. 1869–1878.
  * [42] Y. Zhang and X. Lin, “Disco: Distributed optimization for self-concordant empirical loss,” in _International conference on machine learning_ , 2015, pp. 362–370.
  * [43] S. J. Reddi, J. Konečnỳ, P. Richtárik, B. Póczós, and A. Smola, “Aide: Fast and communication efficient distributed optimization,” _arXiv preprint arXiv:1608.06879_ , 2016.
  * [44] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” _IEEE Transactions on Automatic control_ , vol. 57, no. 3, pp. 592–606, 2011.
  * [45] K. Scaman, F. Bach, S. Bubeck, L. Massoulié, and Y. T. Lee, “Optimal algorithms for non-smooth distributed optimization in networks,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 2740–2749.
  * [46] L. He, A. Bian, and M. Jaggi, “Cola: Decentralized linear learning,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 4536–4546.
  * [47] C. Rago, P. Willett, and Y. Bar-Shalom, “Censoring sensors: A low-communication-rate scheme for distributed detection,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 32, no. 2, pp. 554–568, 1996.
  * [48] S. Appadwedula, V. V. Veeravalli, and D. L. Jones, “Energy-efficient detection in sensor networks,” _IEEE Journal on Selected areas in communications_ , vol. 23, no. 4, pp. 693–702, 2005.
  * [49] S. Marano, V. Matta, P. Willett, and L. Tong, “Cross-layer design of sequential detectors in sensor networks,” _IEEE Transactions on Signal Processing_ , vol. 54, no. 11, pp. 4105–4117, 2006.
  * [50] N. Patwari, A. Hero, and B. M. Sadler, “Hierarchical censoring sensors for change detection,” in _IEEE Workshop on Statistical Signal Processing, 2003_. IEEE, 2003, pp. 21–24.
  * [51] W. Chen and W. Ren, “Event-triggered zero-gradient-sum distributed consensus optimization over directed networks,” _Automatica_ , vol. 65, pp. 90–97, 2016.
  * [52] Q. Lü and H. Li, “Event-triggered discrete-time distributed consensus optimization over time-varying graphs,” _Complexity_ , vol. 2017, 2017.
  * [53] K. I. Tsianos, S. F. Lawlor, J. Y. Yu, and M. G. Rabbat, “Networked optimization with adaptive communication,” in _2013 IEEE Global Conference on Signal and Information Processing_. IEEE, 2013, pp. 579–582.
  * [54] T. Chen, G. Giannakis, T. Sun, and W. Yin, “Lag: Lazily aggregated gradient for communication-efficient distributed learning,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 5050–5060.
  * [55] T. K. Leen and G. B. Orr, “Optimal stochastic search and adaptive momentum,” in _Advances in neural information processing systems_ , 1994, pp. 477–484.
  * [56] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and momentum in deep learning,” in _International conference on machine learning_ , 2013, pp. 1139–1147.
  * [57] L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” _Siam Review_ , vol. 60, no. 2, pp. 223–311, 2018.
  * [58] Y. Nesterov, _Lectures on convex optimization_. Springer, 2018, vol. 137.
  * [59] A. L. Peressini, F. E. Sullivan, and J. J. Uhl, _The mathematics of nonlinear programming_. Springer-Verlag New York, 1988.
  * [60] E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson, “Global convergence of the heavy-ball method for convex optimization,” _arXiv preprint arXiv:1412.7457_ , 2014.
  * [61] A. Géron, _Hands-on machine learning with Scikit-Learn, Keras, and TensorFlow: Concepts, tools, and techniques to build intelligent systems_. O’Reilly Media, 2019.
  * [62] D. Prokhorov, “Ijcnn 2001 neural network competition,” _Slide presentation in IJCNN_ , vol. 1, no. 97, p. 38, 2001.
  * [63] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.