# Log-Scale Quantization in Distributed First-Order Methods: Gradient-based
Learning from Distributed Data

Mohammadreza Doostmohammadian, Muhammad I. Qureshi, Mohammad Hossein Khalesi,
Hamid R. Rabiee, , Usman A. Khan  M. Doostmohammadian and M. H. Khalesi are
with Mechanical Engineering Department, Semnan University, Semnan, Iran,
<EMAIL_ADDRESS>M. I. Qureshi is with Electrical and Computer
Engineering Department, Tufts University, Medford, USA
<EMAIL_ADDRESS>H. R. Rabiee is with Computer Engineering
Department, Sharif University of Technology, Tehran, Iran<EMAIL_ADDRESS>U. A. Khan holds concurrent appointments as a Professor of ECE/CS at Tufts
University and as an Amazon Scholar. This paper describes work performed at
Tufts University and is not associated with Amazon<EMAIL_ADDRESS>
###### Abstract

Decentralized strategies are of interest for learning from large-scale data
over networks. This paper studies learning over a network of geographically
distributed nodes/agents subject to quantization. Each node possesses a
private local cost function, collectively contributing to a global cost
function, which the proposed methodology aims to minimize. In contrast to many
existing literature, the information exchange among nodes is quantized. We
adopt a first-order computationally-efficient distributed optimization
algorithm (with no extra inner consensus loop) that leverages node-level
gradient correction based on local data and network-level gradient aggregation
only over nearby nodes. This method only requires balanced networks with no
need for stochastic weight design. It can handle log-scale quantized data
exchange over possibly time-varying and switching network setups. We analyze
convergence over both structured networks (for example, training over data-
centers) and ad-hoc multi-agent networks (for example, training over dynamic
robotic networks). Through analysis and experimental validation, we show that
(i) structured networks generally result in a smaller optimality gap, and (ii)
logarithmic quantization leads to smaller optimality gap compared to uniform
quantization.

###### Note to Practitioners

Motivated by recent developments in cloud-computing and parallel processing
along with low-cost CPUs and communication networks, this paper considers
distributed/decentralized algorithms for machine learning and optimization.
This work finds a wide range of practical applications in decentralized data
mining, where the data set is distributed among a network of computing nodes.
In the real-world scenarios, practical model nonlinearities such as data
quantization must be addressed for information-exchange among the computing
nodes. The primary emphasis of this work is to address log-scale quantization
and compare it versus uniform quantization. Further, the impact of the
structure of the data mining network is studied to reduce the optimality gap
and improve the convergence rate. As contemporary distributed and networked
data mining systems demand for more accurate algorithms with fast rate of
convergence for real-time applications, our research highlights the intricate
use of logarithmic quantization over structured networks. In particular, our
results can be extended to other machine learning algorithms for more accurate
and faster data mining solutions.

###### Index Terms:

Distributed Algorithm, data classification, quantization, graph theory,
optimization

##  I Introduction

Learning from geographically distributed data has emerged as a critical
challenge in various domains such as sensor networks, edge computing, and
decentralized systems [1, 2, 3]. The scenario involves individual nodes
possessing private local cost functions, collectively contributing to a global
cost that needs to be minimized [4, 5]. This paper focuses on addressing this
challenge through the lens of gradient-based optimization over networks,
targeting scenarios where the cost functions are locally known at distributed
nodes communicating over quantized channels. Data quantization, the process of
representing data with a reduced number of bits, is often employed to reduce
the communication load in such decentralized setups and is proven as an
effective way to reduce communication costs, for example, in machine learning
applications [6, 7]. One common type of quantization is logarithmic or log-
scale that efficiently assigns more bits to represent smaller values and fewer
bits to larger values [8, 9]. This is beneficial when dealing with gradients
or weights that often have a wide dynamic range. Smaller values, which might
be more critical for convergence, are represented with higher precision. This
may increase the complexity of the distributed learning algorithm as we move
from linear dynamics to non-linear dynamics due to quantization. Uniform
quantization, on the other hand, simplifies the representation of values,
which can lead to a faster communication process. However, the lack of
precision, especially for small values, might affect performance in scenarios
where accurate representation of gradients or weights is crucial, and lead to
residual error [10, 11]. In this paper, we study both uniform and log-scale
quantization for distributed optimization.

The existing literature on distributed optimization is mostly linear, where
the focus is mainly on reducing the optimality gap and improving the
convergence rate. The primary distributed optimization methods are GP [12] and
DGD algorithm [13], which are further extended to DSGD [14] and SGP [15, 16]
by adopting stochastic gradient methods. Algorithm ADDOPT [17] and its
stochastic version S-ADDOPT [18] further accelerate the convergence rate using
gradient tracking. Similarly, momentum-based approaches improve the
convergence rate using heavy-ball method [19], Nesterov gradient method [20,
21], or a combination of both [22]. On the other hand, PushSVRG [23] and
PushSAGA [24, 25] algorithms use variance reduction to eliminate the
uncertainty caused by the stochastic gradients. Few other distributed
optimization works use sign-based nonlinearity in the node dynamics to address
finite-time and fixed-time convergence [26, 27, 28]. All these methods assume
unlimited bandwidth to communicate arbitrary real numbers which in practice is
not possible as all realistic communication protocols rely on finite
precision. The effect of uniform quantization over channels with limited data-
rate and the associated optimality gap (or residual) is discussed in [29, 30,
31]. What is missing from the existing literature is the consideration of log-
scale quantization for distributed optimization. This is primarily addressed
for distributed resource allocation and constraint-coupled optimization [32],
but not for distributed learning over networks.

The main contributions of this paper are as follows: (i) we develop a log-
scale quantized first-order distributed optimization method that employs
network-level gradient tracking. This follows the real-world applications in
which quantization is prevalent in networking setups. The proposed solution
can be generalized to consider other sector-bound nonlinearities111A nonlinear
function $f(x)$ is called sector-bound if it lies in a sector typically
defined by two lines passing through the origin, creating an angular region.
In mathematical form, there exist positive factors $\overline{\mathcal{K}}$
and $\underline{\mathcal{K}}$ for which we have $\underline{\mathcal{K}}x\leq
f(x)\leq\overline{\mathcal{K}}x$. in the data-transmission channels. (ii) We
develop the convergence analysis of the proposed log-scale quantized algorithm
and provide the bound on the gradient-tracking step-size. (iii) Moreover,
unlike existing methods, our approach eliminates the need for weight-
stochastic design on the network. This is done by adopting a weight-balanced
design instead, simplifying implementation in the face of node/link failure
and enhancing adaptability to time-varying setups in the presence of link-
level nonlinearities. Through empirical validation, we analyze the convergence
of our method for both academic and real-world data-learning setups with
distributed and heterogeneous data while considering quantization. This work
further explores optimization methodologies that can adapt to both structured
networks and ad-hoc multi-agent networks. Structured networks embody a pre-
defined organized framework, imposing order and predefined communication
patterns on the participating nodes. In contrast, ad-hoc multi-agent networks
dynamically adapt and emerge based on the specific demands of the distributed
environment, for example, based on the nearest neighbour rule [33]. This paper
performs a comparative numerical analysis, unravelling the trade-offs and
advantages inherent in using log-scale quantization in contrast to uniform
quantization.

The rest of the paper is organized as follows. Section II states the problem
and terminologies. The proposed distributed algorithm and its convergence
analysis are presented in Section III. Experimental validations are given in
Section IV. Finally, we conclude the paper in Section V.

##  II Assumptions, Terminology, and Problem Statement

The distributed learning problem is defined as optimizing certain cost
functions as a sum of some local cost functions distributed over a network of
nodes/agents. In machine learning and data mining, the cost function (also
known as the loss function or objective function) measures the difference
between the predicted values of a model and the ground truth in the training
dataset. The cost function quantifies how well or poorly a model performs by
assigning a numerical value to the error or deviation between predicted and
actual values. The optimization algorithm then adjusts the model’s parameters
to minimize this cost, effectively improving the model’s performance. For
example, different loss functions are used for data classification,
regression, and support-vector-machine. The global cost is defined as the
average of local losses at different nodes; mathematically, this is defined as

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{p}}$ $\displaystyle
F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^{n}f_{i}(\mathbf{x})$ (1)

where each local loss $f_{i}(\mathbf{x})$ is private to node/agent $i$.
Particularly, each local loss $f_{i}$ might be decomposable into a finite sum
of $m_{i}$ component cost functions, i.e.,

$\displaystyle
f_{i}(\mathbf{x})=\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}f_{i,j}(\mathbf{x}).$ (2)

In distributed learning and optimization setup, the training cost might be
associated with error-back-propagation in Neural Networks [18], classification
gap in SVM [34], or regression training cost [35].

We assume that the nodes share data (local gradient information or auxiliary
variables) over a communication network $\mathcal{G}$. Each node locally
communicates with its neighbouring nodes $j\in\mathcal{N}_{i}$ and shares
relevant data over the links/channels. In real-world practical applications,
the information shared over the channels/links in $\mathcal{G}$ might be
subject to quantization (or other nonlinear functions). The nonlinear mapping
$h_{l}(\cdot)$ is sign-preserving, odd, and sector-bound, i.e., it satisfies

$\displaystyle
0<\underline{\mathcal{K}}\leq\frac{h_{l}(z)}{z}\leq\overline{\mathcal{K}}$ (3)

An example of such nonlinear mapping is logarithmic (or log-scale)
quantization defined as

$\displaystyle
q_{l}(z)=\mbox{sgn}(z)\exp\left(\rho\left[\dfrac{\log(|z|)}{\rho}\right]\right),$
(4)

with $[\cdot]$ as rounding to the nearest integer, and $\mbox{sgn}(\cdot)$,
$\mbox{exp}(\cdot)$, and $\mbox{log}(\cdot)$ as the sign, exponential, and
(natural) logarithm functions, respectively. The parameter $\rho$ is the
logarithmic quantization level for which we have

$\displaystyle\underline{\mathcal{K}}=1-\dfrac{\rho}{2}\leq\dfrac{q_{l}(z)}{z}\leq
1+\dfrac{\rho}{2}=\overline{\mathcal{K}}.$ (5)

Note that, as illustrated in Fig. 1, this nonlinearity is sector-bound, i.e.,
it is upper/lower-bounded by the two lines $(1\pm\dfrac{\rho}{2})z$. This is
in contrast to uniform quantization which is not sector-bound, as defined
below

$\displaystyle q_{u}(z)=\rho\left[\dfrac{z}{\rho}\right],$ (6)

where $\rho$ is the uniform quantization level. The two quantization functions
are represented in Fig. 1 for comparison. It can be observed that, in contrast
to the log-scale quantization, the upper/lower bounds of uniform quantization,
defined as $z\pm\dfrac{\rho}{2}$, are biased from the origin. In this work, we
study the convergence under log-scale quantization as compared to uniform
quantization. These two are the main types of the nonlinearity governing the
data-transmission setup.

Figure 1: Uniform quantization (as a non-sector-bound function) versus
logarithmic quantization (as a sector-bound function). The logarithmic case
leads to finer quantization around zero in contrast to the uniformly quantized
case.

The assumptions to ensure convergence to the unique minimum $\mathbf{x}^{*}$
of the global cost function $F$ are as follows.

######  Assumption 1.

The data-transmission network is connected (at all times), weight-balanced
(WB), and could be time-varying.

######  Assumption 2.

Each local cost function $f_{i}$ has $L$-smooth and is not necessarily convex,
while the global cost $F$ is strictly convex.

These standard assumptions imply that the global cost function is
differentiable and its second derivative is bounded above by $L$ and below by
$\mu$. Further, the global optimizer $\mathbf{x}^{*}$ of the cost $F$ exists
and is also unique. The followig subsection further motivates the study in
this paper.

###  II-A Effect of Network Structure and Quantization

This paper investigates the effect of network structure by numerical
experimentation. In distributed optimization and learning over networks, the
choice of network topology plays a crucial role in determining the convergence
rate and optimality gap of the learning algorithms [36, 37]. Different network
topologies can have varying effects on the efficiency and speed of
convergence. A general experimental comparison between structured networks
(such as exponential graphs222In exponential graphs, as the number of nodes
increases exponentially, the degree at each node increases linearly.) and ad-
hoc networking setups (such as geometric graphs333In geometric graphs, two
nodes are connected if they are in physical proximity.) is considered in this
paper. Examples of structured networks include networked data-centers or
hierarchical social networks, and examples of ad-hoc random networks include
collaborative robotic networks or wireless sensor networks. Structured
networks (such as exponential graphs), characterized by well-defined and
organized connections, can often lead to faster convergence rates. In
exponential graphs, where nodes have a hierarchical structure, information can
propagate more efficiently through the network. Furthermore, structured
networks may exhibit lower optimality gaps due to better coordination among
the nodes. The organized nature of the network facilitates synchronized
updates, potentially leading to quicker convergence to a near-optimal
solution. On the other hand, ad-hoc multi-agent networks (such as random
geometric graphs), which might lack a clear structure, can have a more complex
convergence behaviour. The convergence rate may be slower with a higher
optimality gap compared to structured networks because information propagation
might not follow an organized pattern. Nodes may require more iterations to
align their models and achieve a consensus on the optimal solution.

Another concern is to consider switching network topologies addressing time-
varying setups, for example, in mobile sensor networks and collaborative swarm
robotics. The change in the network topology might be due to packet drops or
link failures. Recall that most existing linear algorithms [12, 13, 14, 15,
16, 17, 18, 19, 21, 22, 23, 24] necessitate stochastic weight design which is
prone to change in the network topology. This is because any change in the
network structure violates the stochastic condition and requires the redesign
of stochastic weights, for example by applying the algorithms in [38, 39, 40].
In contrast, this work only requires WB design of matrices $A_{\gamma}$ and
$B_{\gamma}$ that allows handling possible changes in the network topology.
This is better illustrated in Fig. 2.

Figure 2: This figure gives an example graph topology which is both stochastic
and WB. The red link represents an unreliable channel that might be subject to
failure or packet drop. By removing this link, the network preserves the WB
condition but loses stochasticity. Therefore, many weight-stochastic
algorithms in the literature need to redesign the weights for convergence.

We address more findings in terms of data quantization over channels. First,
it should be noted that logarithmic quantization, as compared to uniform
quantization, is more efficient in scenarios where the optimization problem
involves a wide range of gradient magnitudes. This follows the sector-bound
nature of the log-scale quantization, as illustrated in Fig. 1. Smaller
values, which are key for convergence, can be represented more accurately with
logarithmic quantization. This may lead to a smaller optimality gap and more
efficient convergence. On the other hand, the lack of precision in uniform
quantization, especially for small values, might slow down convergence and
increase the optimality gap in the range of values where accurate
representation of gradients or weights is crucial. In terms of network
structure in the presence of quantization, although exponential graphs are
structured and can facilitate efficient quantized communication, their
optimality gap might be considerably affected by quantization inaccuracy. In
other words, the efficacy of the network structure might be dominated by the
effect of quantization. These comments are investigated by the numerical
experiments in Section IV.

##  III Distributed Optimization over Networks: Algorithm and Main Results

###  III-A Algorithm

This section presents our main algorithm for learning over networks. The
methodology is based on two WB matrices
$A_{\gamma}=[a^{\gamma}_{ij}]\in\mathbb{R}^{n\times n}$ and
$B_{\gamma}=[b^{\gamma}_{ij}]\in\mathbb{R}^{n\times n}$ that capture the
weights for data-sharing over the network, one for consensus on the states and
the other for gradient-tracking dynamics. The index $\gamma:k\mapsto\Gamma$
denotes the associated network topology that may change over time, whereas
$\Gamma$ denotes the set of all possible topologies of the data-sharing
network. The graph is all-time connected, i.e., all the netwotk topologies in
$\Gamma$ are connected. The two matrices $A_{\gamma}$ and $B_{\gamma}$ can be
designed independently, matrix $A_{\gamma}$ to characterize the weights on the
local state value $\mathbf{x}_{i}$ and matrix $B_{\gamma}$ to characterize the
weights on the auxiliary variable $\mathbf{y}_{i}$ for gradient tracking.
These weight matrices are WB over $\mathcal{G}$ as discussed before, where the
entries satisfy the following:

$\displaystyle
A_{\gamma}(i,j)=\left\\{\begin{array}[]{ll}a^{\gamma}_{ij}>0,&\text{If}~{}j\in\mathcal{N}_{i}\\\
0,&\text{Otherwise}.\end{array}\right.\sum_{j=1}^{n}a_{ij}^{\gamma}=\sum_{i=1}^{n}a_{ij}^{\gamma}$
(9) $\displaystyle
B_{\gamma}(i,j)=\left\\{\begin{array}[]{ll}b^{\gamma}_{ij}>0,&\text{If}~{}j\in\mathcal{N}_{i}\\\
0,&\text{Otherwise}.\end{array}\right.\sum_{j=1}^{n}b_{ij}^{\gamma}=\sum_{i=1}^{n}b_{ij}^{\gamma}$
(12)

Let $\overline{A}_{\gamma}$ and $\overline{B}_{\gamma}$ denote the Laplacian
matrices associated with $A_{\gamma}$ and $B_{\gamma}$, respectivly. The
definition follows as

$\displaystyle\overline{A}_{\gamma}(i,j)=\left\\{\begin{array}[]{ll}-\sum_{i=1}^{n}a^{\gamma}_{ij},&i=j\\\
a^{\gamma}_{ij},&i\neq j.\end{array}\right.$ (15)
$\displaystyle\overline{B}_{\gamma}(i,j)=\left\\{\begin{array}[]{ll}-\sum_{i=1}^{n}b^{\gamma}_{ij},&i=j\\\
b^{\gamma}_{ij},&i\neq j.\end{array}\right.$ (18)

It is known that for connected networks the eigenvalues of these Laplacian
matrices are all in the left-half-plane except one zero eigenvalue [41]. The
absolute value of the second largest eigenvalue of the laplacian matrices,
denoted by $|\lambda^{A}_{2}|$ and $|\lambda^{B}_{2}|$, play a key role in the
convergence and learning rate. These values are known as the algebraic
connectivity. Given the weight matrices and switching signal $\gamma$, the
local learning and optimization formulation is formally described below:

$\displaystyle\dot{\mathbf{x}}_{i}$
$\displaystyle=\sum_{j=1}^{n}a_{ij}^{\gamma}(h_{l}(\mathbf{x}_{j})-h_{l}(\mathbf{x}_{i}))-\alpha\mathbf{y}_{i},$
(19) $\displaystyle\dot{\mathbf{y}}_{i}$
$\displaystyle=\sum_{j=1}^{n}b_{ij}^{\gamma}(h_{l}(\mathbf{y}_{j})-h_{l}(\mathbf{y}_{i}))+\partial_{t}\nabla
f_{i}(\mathbf{x}_{i}),$ (20)

In contrast to most existing methods with weight-stochastic matrices
(introduced in Section I), the proposed dynamics work under WB design and
under switching network topologies. These make it easier to handle link-
failure as discussed in Fig. 2. Moreover, the link (or channel) nonlinearity
$h_{l}(\cdot)$ is not considered in the existing literature, which allows to
address log-scale data quantization by setting $h_{l}(z)=q_{l}(z)$ given in
Eq. (4). The discrete-time version of our methodology is summarized in
Algorithm 1.

1 Data: $f_{i,j}(\mathbf{x})$, $\mathcal{G}_{\gamma}$, $A_{\gamma}$,
$B_{\gamma}$, $\alpha$

2 Initialization: ${\mathbf{y}}_{i}(0)=\mathbf{0}_{p}$, random
${\mathbf{x}}_{i}(0)$

3 for  _$k=0,1,2,\dots$_ do

4 Each node $i$ receives $h_{l}(\mathbf{x}_{j}^{k})$ and
$h_{l}(\mathbf{y}^{k}_{j})$ from $j\in\mathcal{N}_{i}$;

5
$\mathbf{x}^{k+1}_{i}\leftarrow{\mathbf{x}}^{k}_{i}+\sum_{j=1}^{n}a_{ij}^{\gamma}(h_{l}(\mathbf{x}_{j}^{k})-h_{l}(\mathbf{x}_{i}^{k}))-\alpha\mathbf{y}^{k}_{i}$;

6 $w_{i}^{k}\leftarrow\nabla f_{i}({\mathbf{x}}^{k+1}_{i})-\nabla
f_{i}({\mathbf{x}}^{k}_{i})$;

7
$\mathbf{y}^{k+1}_{i}\leftarrow{\mathbf{y}}^{k}_{i}+\sum_{j=1}^{n}b_{ij}^{\gamma}(h_{l}(\mathbf{y}^{k}_{j})-h_{l}(\mathbf{y}^{k}_{i}))+w_{i}^{k}$;

8

9Return: optimal $\mathbf{x}^{*}$ and $F^{*}$;

Algorithm 1 Local learning at each node $i$.

Note that the learning rate tightly depends on the network topology and the
algebraic connectivity. Summing the states over all the nodes we have

$\displaystyle\sum_{i=1}^{n}{\mathbf{y}}_{i}^{k+1}$
$\displaystyle=\sum_{i=1}^{n}{\mathbf{y}}_{i}^{k}+\sum_{i=1}^{n}\nabla
f_{i}(\mathbf{x}^{k+1}_{i})-\sum_{i=1}^{n}\nabla f_{i}(\mathbf{x}^{k}_{i}),$
(21) $\displaystyle\sum_{i=1}^{n}{\mathbf{x}}_{i}^{k+1}$
$\displaystyle=\sum_{i=1}^{n}{\mathbf{x}}_{i}^{k}-\alpha\sum_{i=1}^{n}{\mathbf{y}}_{i}^{k}.$
(22)

This follows the WB assumption which implies that

$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}^{\gamma}(h_{l}(\mathbf{x}_{j}^{k})-h_{l}(\mathbf{x}_{i}^{k}))=0$
$\sum_{i=1}^{n}\sum_{j=1}^{n}b_{ij}^{\gamma}(h_{l}(\mathbf{y}^{k}_{j})-h_{l}(\mathbf{y}^{k}_{i}))=0$

By setting the initial condition as $\mathbf{y}_{i}(0)=\mathbf{0}_{p}$ we
obtain the following,

$\displaystyle\sum_{i=1}^{n}{\mathbf{x}}_{i}^{k+1}=-\alpha\sum_{i=1}^{n}{\mathbf{y}}_{i}^{k+1}=-\alpha\sum_{i=1}^{n}\nabla
f_{i}(\mathbf{x}^{k+1}_{i}),$ (23)

This represents the consensus-type gradient-tracking dynamics that capture the
essence of the proposed methodology. This formulation further allows for
addressing sector-bound odd nonlinearities $h_{l}$ (for example log-scale
quantization) without violating the tracking property. This along with the
time-varying network topology advances the recent state-of-the-art algorithms
for data-mining and optimization [18, 23, 24, 29, 30, 31].

Recall that most of the existing algorithms prove convergence for ideal
networking conditions and in the absence of nonlinearities (e.g., quantization
and clipping). However, in the presence of nonlinearities and non-ideal
networking conditions, the solution may result in a certain optimality gap,
which also depends on the structure of the underlying network
$\mathcal{G}_{\gamma}$. The role of the network structure and quantization is
also discussed in the simulation section.

###  III-B Proof of Convergence

This section proves the convergence of the distributed dynamics (19)-(20)
using eigen-spectrum perturbation-based analysis. We also state some relevant
lemmas. The proofs in this section hold for any sign-preserving, odd, sector-
bound nonlinear mapping $h_{l}(\cdot)$, wich also includes log-scale
quantization $h_{l}(z)=q_{l}(z)$ defined by (4). In the rest of the paper, for
notation simplicity, we drop the dependence $(t,\gamma)$ unless where it is
needed.

######  Lemma 1.

[42] Consider the square matrix $P(\alpha)$ of size $n$ which depends on
parameter ${\alpha\in\mathbb{R}_{\geq 0}}$. Let $P(0)$ has ${N<n}$ equal
eigenvalues $\lambda_{1}=\ldots=\lambda_{N}$, associated with right and left
unit eigenvectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{N}$ and
$\mathbf{u}_{1},\ldots,\mathbf{u}_{N}$ (which are linearly independent). Let
${P^{\prime}=\partial_{\alpha}P(\alpha)|_{\alpha=0}}$ and
$\lambda_{i}(\alpha)$ represent its $i$-th eigenvalue
${\lambda_{i},i\in\\{1,\ldots,N\\}}$. Then,
$\partial_{\alpha}\lambda_{i}|_{\alpha=0}$ is the $i$-th eigenvalue of,

$\left(\begin{array}[]{ccc}\mathbf{u}_{1}^{\top}P^{\prime}\mathbf{v}_{1}&\ldots&\mathbf{u}_{1}^{\top}P^{\prime}\mathbf{v}_{N}\\\
&\ddots&\\\
\mathbf{u}_{N}^{\top}P^{\prime}\mathbf{v}_{1}&\ldots&\mathbf{u}_{N}^{\top}P^{\prime}\mathbf{v}_{N}\end{array}\right).$

######  Lemma 2.

[43] Given the balanced digraph $\mathcal{G}$/ its Laplacian matrix
$\overline{A}$ (or $\overline{B}$) has all its eigenvalue in the left-half-
plane except one isolated zero eigenvalue with associated non-negative left
eigenvector $\mathbf{u}_{1}^{\top}$ satisfying $\sum_{i=1}^{n}u_{1,i}>0$.

######  Theorem 1.

Let Assumptions 1 and 2 hold. For sufficiently small $\alpha$, all eigenvalues
of the dynamics (19)-(20) are in the left-half-plane except $m$ zero
eigenvalue.

###### Proof.

For the linear case (i.e., setting $h_{l}(z)=z$) the proposed dynamics
(19)-(20) can be written in compact form as

$\displaystyle\left(\begin{array}[]{c}\dot{\mathbf{x}}\\\
\dot{\mathbf{y}}\end{array}\right)=M(\alpha)\left(\begin{array}[]{c}{\mathbf{x}}\\\
{\mathbf{y}}\end{array}\right),$ (28) $\displaystyle M(\alpha)=$
$\displaystyle\left(\begin{array}[]{cc}\overline{A}\otimes I_{m}&-\alpha
I_{mn}\\\ H(\overline{A}\otimes I_{m})&\overline{B}\otimes I_{m}-\alpha
H\end{array}\right).$ (31)

where $M(\alpha)=M_{0}+\alpha M_{1}$ with

$\displaystyle M_{0}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}\overline{A}\otimes
I_{m}&\mathbf{0}_{mn\times mn}\\\ H(\overline{A}\otimes
I_{m})&\overline{B}\otimes I_{m}\end{array}\right),$ (34) $\displaystyle
M_{1}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}\mathbf{0}_{mn\times mn}&-{I_{mn}}\\\
{\mathbf{0}_{mn\times mn}}&-H\end{array}\right),$ (37)

Now, considering the nonlinearity $h_{l}(z)=q_{l}(z)$444Note that the proof
holds for general sign-preserving sector-bound nonlinearities. We particularly
state the solution for log-scale quantization as an example., one can
linearize the nonlinear dynamics (19)-(20) at every time-instant $t$ as its
operating point. It is known that the stability of the linearization at every
operating point implies the stability of the nonlinear dynamics [44]. To study
the stability of the linearized dynamics, we have

$\displaystyle M_{q}(t,\alpha,\gamma)$ $\displaystyle=M_{q}^{0}+\alpha M^{1}$
(38) $\displaystyle\underline{\mathcal{K}}M^{0}$ $\displaystyle\preceq
M_{q}^{0}\preceq\overline{\mathcal{K}}M^{0}$ (39) $\displaystyle
M_{q}^{0}=Z(t)M^{0}$ $\displaystyle,~{}\underline{\mathcal{K}}I_{n}\preceq
Z(t)\preceq\overline{\mathcal{K}}I_{n}$ (40)

where $M_{q}^{0}$ is the linearized version of $M^{0}$ for the nonlinear
dynamics, $Z(t):=\mbox{diag}[\zeta(t)]$, column vector
$\zeta(t)=[\zeta_{1}(t);\zeta_{2}(t);\dots;\zeta_{n}(t)]$ with
$\zeta_{i}(t)=\frac{q_{l}(\mathbf{x}_{i})}{\mathbf{x}_{i}}$ (or equivalently
$q_{l}(\mathbf{x}(t))=Z(t)\mathbf{x}(t)$ at every time-instant $t$). Recall
from Eq. (3) that
$\underline{\mathcal{K}}\leq\zeta_{i}(t)\leq\overline{\mathcal{K}}$.
Therefore, we have

$\displaystyle\overline{A}_{Z}=\overline{A}Z(t),~{}\overline{B}_{Z}=\overline{B}Z(t)$
(41)

The above helps to relate the eigen-spectrum of the linear dynamics (28) to
that of the nonlinear case associated with $M_{q}$. Note that $Z(t)$ is a
diagonal matrix from its definition, and we have

$\displaystyle\mbox{det}(\overline{A}_{Z}-\lambda
I_{mn})=\mbox{det}(\overline{A}-\lambda Z(t)^{-1}),$ (42)
$\displaystyle\mbox{det}(\overline{B}_{Z}-\lambda
I_{mn})=\mbox{det}(\overline{B}-\lambda Z(t)^{-1}),$ (43)

with $\lambda$ denoting the eigenvalue. Therefore, from (39)-(40), one can
relate the eigenspectrum of the linearized version with that of the linear
case as

$\displaystyle\underline{\mathcal{K}}\sigma(M^{0})\leq\sigma(M^{0}_{q})\leq\overline{\mathcal{K}}\sigma(M^{0})$
(44)

where the eigenspectrum of the linear case follows the block triangular form
of $M_{0}$ as,

$\displaystyle\sigma(M^{0})=\sigma(\overline{A}\otimes
I_{m})\cup\sigma(\overline{B}\otimes I_{m})$ (45)

For the rest of the proof, we study the eigenspectrum perturbation of $M^{0}$
and then extend the results to $M^{0}_{q}$ using Eq. (44). From Lemma 2, both
Laplacian matrices $\overline{A}$ and $\overline{B}$ have one isolated zero
eigenvalue and the rest in the left-half-plane. Therefore, $m$ sets of
eigenvalues of $M_{0}$, associated with dimensions $j=\\{1,\ldots,m\\}$ are in
the form,

$\operatorname{Re}\\{\lambda_{2n,j}\\}\leq\ldots\leq\operatorname{Re}\\{\lambda_{3,j}\\}<\lambda_{2,j}=\lambda_{1,j}=0,$

Next, we consider $\alpha M_{1}$ as a perturbation to matrix $M_{0}$. This is
done using Lemma 1. In particular, we check how the perturbation term $\alpha
M_{1}$ affects the two zero eigenvalues $\lambda_{1,j}$ and $\lambda_{2,j}$ of
$M_{0}$. Denote the perturbed zero eigenvalues by $\lambda_{1,j}(\alpha)$ and
$\lambda_{2,j}(\alpha)$ associated to $M$. The right and left unit
eigenvectors of $\lambda_{1,j}$, $\lambda_{2,j}$ follow from Lemma 2 and [43]
as555The normalizing factors of the unit vectors might be ignored as in the
followings we only care about the sign of the terms in $U^{\top}M_{1}V$, not
the exact values. ,

$\displaystyle V$
$\displaystyle=[V_{1}~{}V_{2}]=\frac{1}{\sqrt{n}}\left(\begin{array}[]{cc}\mathbf{1}_{n}&\mathbf{0}_{n}\\\
\mathbf{0}_{n}&\mathbf{1}_{n}\end{array}\right)\otimes I_{m}$ (48)
$\displaystyle U^{\top}$
$\displaystyle=[U_{1}~{}U_{2}]^{\top}=\left(\begin{array}[]{cc}\mathbf{u}_{1}&\mathbf{0}_{n}\\\
\mathbf{0}_{n}&\mathbf{u}_{2}\end{array}\right)^{\top}\otimes I_{m}$ (51)

Recalling $M(\alpha)=M_{0}+\alpha M_{1}$ we have
$\partial_{\alpha}{dM(\alpha)}|_{\alpha=0}=M_{1}$. Then, Lemma 1 implies that,

$\displaystyle U^{\top}M_{1}V=\left(\begin{array}[]{cc}\mathbf{0}_{m\times
m}&\times\\\ \mathbf{0}_{m\times m}&-(\mathbf{u}_{2}\otimes
I_{m})^{\top}H(\frac{1}{\sqrt{n}}\mathbf{1}_{n}\otimes
I_{m})\end{array}\right).$ (54)

The definition of $H$, Lemma 2, and Assumption 2 implies that

$\displaystyle-(\mathbf{u}_{2}\otimes
I_{m})^{\top}H(\frac{1}{\sqrt{n}}\mathbf{1}_{n}\otimes
I_{m})=-\sum_{i=1}^{n}\frac{u_{2,i}}{\sqrt{n}}\boldsymbol{\nabla}^{2}f_{i}(\mathbf{x}_{i})\prec
0,$ (55)

where $u_{2,i}$ is the $i$th element of $\mathbf{u}_{2}$. Then, using Lemma 1,
the perturbations $\partial_{\alpha}d\lambda_{1,j}|_{\alpha=0}$ and
$\partial_{\alpha}d\lambda_{2,j}|_{\alpha=0}$ are defined based on the
eigenvalues of the matrix in (54). Since this matrix is triangular and from
Eq. (55), $\partial_{\alpha}\lambda_{1,j}|_{\alpha=0}=0$ and
$\partial_{\alpha}\lambda_{2,j}|_{\alpha=0}<0$. Therefore, from the
perturbation analysis, one can conclude that $\alpha M_{1}$ pushes $m$ zero
eigenvalues $\lambda_{2,j}(\alpha)$ of $M$ toward the left-half-plane and the
other $m$ zero eigenvalues $\lambda_{1,j}(\alpha)$ remain at zero. This
implies that sufficiently small $\alpha$ gives the eigen-spectrum of $M$ as

$\displaystyle\begin{aligned}
\operatorname{Re}\\{\lambda_{2n,j}(\alpha)\\}\leq\ldots\leq\operatorname{Re}\\{\lambda_{3,j}(\alpha)\\}\leq\lambda_{2,j}(\alpha)<\lambda_{1,j}(\alpha)=0,\end{aligned}$
(56)

This completes the proof. ∎

######  Theorem 2.

Given that the Assumptions (1)-(2) and conditions in Theorem 1 hold, for
$0<\alpha<\frac{\min\\{|\operatorname{Re}\\{\lambda_{2}^{A}\\}|,|\operatorname{Re}\\{\lambda_{2}^{B}\\}|\\}}{L\overline{\mathcal{K}}}$,
the proposed dynamics (19)-(20) converges to the optimizer
$[\mathbf{x}^{*}\otimes\mathbf{1}_{n};\mathbf{0}_{nm}]$.

###### Proof.

First, we determine the admissible bound on $\alpha$ for proof of convergence.
Recall from [45, Appendix] that one can relate the spectrum of $M(\alpha)$ in
(31) to $\alpha$. For ease of notation, from this point onward we derive the
bound for $m=1$ (but it holds for any $m>1$). Performing row/column
permutations in [45, Eq. (18)] $\sigma(M)$ can be determined from the
following,

$\displaystyle\mbox{det}(\alpha
I_{n})\mbox{det}(H(\overline{A})+(\overline{B}-\alpha H-\lambda
I_{n})(\frac{1}{\alpha})(\overline{A}-\lambda I_{n}))=0.$

which can be simplified as

$\displaystyle\mbox{det}(I_{n})\mbox{det}((\overline{A}-\lambda
I_{n})(\overline{B}-\lambda I_{n})+\alpha\lambda H)=0$ (57)

Similar to the proof of Theorem 1, for stability we need to find the
admissible range of $\alpha$ values for which the eigenvalues $\lambda$ remain
in the left-half-plane, except one zero eigenvalue. The analysis here is based
on the fact that the eigenvalues are continuous functions of the matrix
elements [46]. It is clear that $\alpha=0$ satisfies Eq. (57) and gives
$\mbox{det}((\overline{W}-\lambda I_{n})(\overline{A}-\lambda I_{n}))=0$. This
leads to the eigen-spectrum following as
$\sigma(M)=\sigma(\overline{A})\cup\sigma(\overline{W})$ with two zero
eigenvalues. We need to find the other root $\overline{\alpha}>0$, which gives
the admissible range as $0<\alpha<\overline{\alpha}$ for the stability of
$M(\alpha)$. This follows the continuity of $\sigma(M)$ as a function of
$\alpha$ [46]. With some abuse of notation, for any
$\operatorname{Re}\\{\lambda\\}<0$ one can reformulate (57) as

$\displaystyle\mbox{det}($ $\displaystyle(\overline{B}-\lambda
I_{n}\pm\sqrt{\alpha|\lambda|H})(\overline{A}-\lambda
I_{n}\mp\sqrt{\alpha|\lambda|H})$
$\displaystyle\pm\sqrt{\alpha|\lambda|H}(\overline{A}-\overline{B}))=0$ (58)

This follows the diagonal form of $H$. First, we consider the same consensus
matrix for both variables $\mathbf{x},\mathbf{y}$. Set
$\overline{A}=\overline{B}$ and we have

$\displaystyle\mbox{det}(\overline{A}-\lambda
I_{n}\mp\sqrt{\alpha|\lambda|H})=\mbox{det}(\overline{A}-\lambda(I_{n}\mp\sqrt{\frac{\alpha
H}{|\lambda|}}))=0$

This implies that fo $\lambda\in\sigma(\overline{A})$, its perturbed
eigenvalue is $\lambda(1\pm\sqrt{\frac{\alpha H}{|\lambda|}})$. Therefore, for
$\lambda\neq 0$, the min value of $\overline{\alpha}$ that makes this term
zero (at the edge of instability) satisfies the following,

$\displaystyle\overline{\alpha}=\operatorname*{argmin}_{\alpha}|1-\sqrt{\frac{\alpha
H}{|\lambda|}}|\geq\frac{\min\\{|\operatorname{Re}\\{\lambda_{j}\\}|\neq
0\\}}{\max\\{H_{ii}\\}}=\frac{|\operatorname{Re}\\{\lambda_{2}\\}|}{L}$ (59)

where we recalled $H\preceq LI_{n}$ from Assumption 2. Recalling perturbed
formulation in Theorem 1, this gives the admissible range for $\alpha$ for
which $M(\alpha)$ has all its eigenvalues at the left-half-plane except one
zero as

$\displaystyle
0<\alpha<\overline{\alpha}:=\frac{|\operatorname{Re}\\{\lambda_{2}\\}|}{L}$
(60)

For general nonlinear dynamics (19)-(20) satisfying Eq. (39)-(40), the
admissible range changes to

$\displaystyle
0<\alpha<\overline{\alpha}:=\frac{|\operatorname{Re}\\{\lambda_{2}\\}|}{L\overline{\mathcal{K}}}$
(61)

For the more general case of $\overline{A}\neq\overline{B}$, this is
generalized as,

$\displaystyle
0<\alpha<\frac{\min\\{|\operatorname{Re}\\{\lambda_{2}^{A}\\}|,|\operatorname{Re}\\{\lambda_{2}^{B}\\}|\\}}{L\overline{\mathcal{K}}}=:\overline{\alpha}$
(62)

This admissible range of $\alpha$ depends only on
$\sigma(\overline{A}),\sigma(\overline{B})$ and holds for any value of $m\geq
1$. Next, we prove convergence under this admissible bound. It is clear that
the optimizer
$[\mathbf{x}^{*}\otimes\mathbf{1}_{n};\mathbf{0}_{nm}]\in\mathbb{R}^{2mn}$is
the invariant set of dynamics (19)-(20) and belongs to null-space of $M_{q}$.
Recall that for
$0<\alpha<\frac{\min\\{|\operatorname{Re}\\{\lambda_{2}^{A}\\}|,|\operatorname{Re}\\{\lambda_{2}^{B}\\}|\\}}{L\overline{\mathcal{K}}}$,
the eigenvalues of the linearized system dynamics associated with $M_{q}$ are
stable except one isolated zero eigenvalue. This is irrespective of the time-
variation of $\mathcal{G}$ and $M_{q}$. Define the variable $\delta$ as the
distance between the system state and the optimizer,

$\delta=\left(\begin{array}[]{c}{\mathbf{x}}\\\
{\mathbf{y}}\end{array}\right)-\left(\begin{array}[]{c}{\mathbf{x}}^{*}\\\
\mathbf{0}_{mn}\end{array}\right)\in\mathbb{R}^{2mn}.$

and the positive-semi-definite Lyapunov function
${\mathcal{V}(\delta)=\frac{1}{2}\delta^{\top}\delta=\frac{1}{2}\lVert\delta\rVert_{2}^{2}}$.
As $\delta\rightarrow\mathbf{0}_{2mn}$ the state variables converge to the
optimizer. We have,

$\displaystyle\dot{\delta}=M_{q}\left(\begin{array}[]{c}\mathbf{x}\\\
\mathbf{y}\end{array}\right)-M_{q}\left(\begin{array}[]{c}\mathbf{x}^{*}\\\
\mathbf{0}_{mn}\end{array}\right)=M_{q}\delta.$ (67)

This implies that
$\dot{\mathcal{V}}={\delta}^{\top}\dot{\delta}=\delta^{\top}M_{q}{\delta}$ and
from [43, Sections VIII-IX], we have

$\displaystyle\dot{\mathcal{V}}=\delta^{\top}M_{q}\delta\leq\max_{1\leq j\leq
m}\operatorname{Re}\\{{\lambda}_{2,j}\\}\delta^{\top}\delta,$ (68)

where $\max_{1\leq j\leq m}\operatorname{Re}\\{{\lambda}_{2,j}\\}$ is the real
part of the largest negative eigenvalue of $M_{q}$ at all times (following
from Theorem 1). Note that $\dot{\mathcal{V}}$ is negative-definite for all
$\delta\neq\mathbf{0}_{2mn}$ and is zero for $\delta=\mathbf{0}_{2mn}$. From
Lyapunov theorem, this network of integrators is asymptotically globally
stable and $\delta\rightarrow\mathbf{0}_{2mn}$ implies that the solution
converges to the optimizer. ∎

###  III-C Discussions

We now provide some important remarks in the context of Theorems 1 and 2 and
the sector-bound property.

######  Remark 1.

For convergence we only need $(\mathbf{1}_{n}\otimes
I_{p})^{\top}H(\mathbf{1}_{n}\otimes I_{p})\succ 0$ (with
$H:=\mbox{diag}[\nabla^{2}f_{i}(\mathbf{x}_{i})]$), i.e., strong-convexity of
the global objective function $F(\mathbf{x})$. Thus, the local cost functions
$f_{i}(\mathbf{x}_{i})$ might be non-convex, i.e.,
$\nabla^{2}f_{i}(\mathbf{x}_{i})$ is not necessarily positive while their
summation is positive to ensure that $F(\mathbf{x})$ is strongly convex. An
academic example of such a case is given in the simulation. Therefore, the
convexity assumption in this paper is more relaxed as compared to many
existing literature. Note that the log-scale quantization in this work is
independent of Assumption 2.

######  Remark 2.

From Theorem 1, the proposed dynamics (19)-(20) has one zero eigenvalue
related to the agreement (or consensus) on the states, i.e., all the auxiliary
states reach consensus on $\mathbf{y}_{i}=0$ and all the main states reach
consensus on $\mathbf{x}_{i}=\mathbf{x}^{*}$. On the other hand, the rest of
eigenvalues remain in the left-half-plane which results in the stability of
the proposed dynamics and convergence toward optimal point.

######  Remark 3.

Consider the typical example of link nonlinearity $h_{l}(\cdot)$ as log-scale
quantization on the communication channels. Following Eq. (5), for
sufficiently small $\rho$ one can see that $q_{l}(\cdot)$ gets arbitrarily
close to the linear case. In this case, the convergence follows the
approximate rate of $\mathcal{O}(\frac{1}{k})$.

######  Remark 4.

Assume that the linear version of the proposed algorithm 1 with
$h_{l}(\mathbf{x}_{j}^{k})=\mathbf{x}_{j}^{k}$ and
$h_{l}(\mathbf{y}^{k}_{j})=\mathbf{y}^{k}_{j}$ gives certain optimality gap.
Then, recalling Eq. (3), one can see that
$\underline{\mathcal{K}}(\mathbf{x}_{j}^{k}-\mathbf{x}_{i}^{k}\leq
h_{l}(\mathbf{x}_{j}^{k})-h_{l}(\mathbf{x}_{i}^{k})\leq\overline{\mathcal{K}}(\mathbf{x}_{j}^{k}-\mathbf{x}_{i}^{k})$
and $\underline{\mathcal{K}}(\mathbf{y}_{j}^{k}-\mathbf{y}_{i}^{k}\leq
h_{l}(\mathbf{y}_{j}^{k})-h_{l}(\mathbf{y}_{i}^{k})\leq\overline{\mathcal{K}}(\mathbf{y}_{j}^{k}-\mathbf{y}_{i}^{k})$.
Therefore, the optimality gap is of the same order as in the linear case
multiplied by a factor of $\overline{\mathcal{K}}$ and
$\underline{\mathcal{K}}$. Thus, for the logarithmic quantization nonlinearity
with $\overline{\mathcal{K}}=1+\frac{\rho}{2}$ and
$\underline{\mathcal{K}}=1-\frac{\rho}{2}$, the optimality gap gets
arbitrarily close to the linear case by choosing sufficiently small $\rho$.
This is illustrated in the next section via numerical simulations.

######  Remark 5.

Uniform quantization in contrast to logarithmic quantization is not sector-
bound; as shown in Fig. 1, the bounds $x\pm\frac{\rho}{2}$ do not pass through
the origin. Therefore, the results on convergence and optimality do not hold
for uniformly quantized data. In fact, some literature show that uniform
quantization generally results in larger optimality gap, see an example for
quantized resource allocation in [47]. In the next section, we clearly show by
numerical simulation that log-scale quantization as compared to uniform
quantization results in smaller optimality gap.

##  IV Numerical Experiments

In this section, we perform simulations on both real and academic setups to
verify our results.

###  IV-A Academic Example

We consider a network of $n=16$ agents to minimize the following cost function
in a distributed and collaborative way:

$\displaystyle
f_{i,j}(x_{i})=4x_{i}^{2}+3\sin^{2}(x_{i})+a_{i,j}\cos(x_{i})+b_{i,j}x_{i},$
(69)

with random parameters $a_{i,j}$ and $b_{i,j}$ in the range $[-10,10]$ such
that $\sum_{i=1}^{n}\sum_{j=1}^{m}a_{i,j}=0$ and
$\sum_{i=1}^{n}\sum_{j=1}^{m}b_{i,j}=0$ and $a_{i,j},b_{i,j}\neq 0$. Note that
$f_{i,j}(x_{i})$ is not necessarily convex, i.e.,
$\nabla^{2}f_{i}(\mathbf{x})$ might be negative at some points, while the
global cost summing all $f_{i,j}(x_{i})$ is strongly convex. We apply
Algorithm 1 over random ad-hoc networks and structured exponential networks
for both uniform and log-scale quantization. First, we compare the convergence
rate and optimality gap over a time-varying exponential network (as a
structured network) versus a random Erdos-Renyi (ER) network subject to log-
scale quantization with $\rho=\frac{1}{128}$. The result is shown in Fig. 3.
Clearly, the structured network gives a smaller optimality gap and faster
convergence.

Figure 3: Logarithmically quantized distributed optimization over an
exponential network versus an ER random network of the same size.

Next, we compare distributed optimization over exponential graphs subject to
uniform quantization versus log-scale quantization in Fig. 4 for different
quantization levels $\rho$. Evidently from the figure, log-scale quantization
results in a smaller optimality gap as compared to uniform quantization.

Figure 4: Optimality gap of uniformly quantized versus logarithmically
quantized distributed learning over exponential network.

###  IV-B Real Data-Set Example

In this section, we analyze some real data from [23]. We randomly select some
images from the MNIST data set and classify them using logistic regression
with a convex regularizer. The set of $N=12000$ labelled images are used for
classification, distributed among the $n=16$ agents/nodes. The overall cost
function is defined as

$\displaystyle\min_{\mathbf{b},c}$ $\displaystyle
F(\mathbf{b},c)=\frac{1}{n}\sum_{i=1}^{n}f_{i}$ (70)

where each node $i$ has access to a batch of $m_{i}=750$ sample data and
locally minimizes the following training cost:

$\displaystyle
f_{i}(\mathbf{x})=\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}\ln(1+\exp(-(\mathbf{b}^{\top}x_{i,j}+c)y_{i,j}))+\frac{\lambda}{2}\|\mathbf{b}\|_{2}^{2}.$
(71)

with $\mathbf{b},c$ as the parameters of the separating hyperplane. We run and
compare the distributed training over both geometric graph (as an ad-hoc
network) and exponential graph (as a structured network). The optimality gap
(also known as the optimization residual) in the figures is defined as
$F(\overline{\mathbf{x}}^{k})-F(\mathbf{x}^{*})$ with
$\overline{\mathbf{x}}^{k}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}^{k}_{i}$.

First, we compare some existing algorithms in the literature with the proposed
Algorithm 1. The following algorithms are used for comparison: GP [12], SGP
[15, 16], S-ADDOPT [18], ADDOPT [17], and PushSAGA [24]. Fig. 5 presents the
comparison results.

Figure 5: Comparison between the performance of the proposed algorithm (in the
absence of quantization) with some existing algorithms in the literature.

Next, we compare training over exponential networks subject to uniform
quantization for different data quantization levels, see Fig. 6. As it can be
observed, the uniform quantization results in a larger optimality gap in the
training outcome.

Figure 6: Optimality gap of uniform quantization for distributed learning of
MNIST dataset over exponential graphs.

The same comparison is performed over the geometric network and the result is
shown in Fig. 7. As expected, uniform quantization results in a larger
optimality gap. It is worth noting from the figures that, the optimality gap
is generally larger over geometric networks as a non-structured topology.

Figure 7: Optimality gap of uniform quantization for distributed learning of
MNIST dataset over geometric graphs.

##  V Conclusions

###  V-A Concluding Remarks

This work proposes a distributed optimization setup for learning over
networks. We particularly address nonlinear channels to take into account, for
example, possible data quantization. We compare log-scale quantization (as a
sector-bound nonlinearity) with uniform quantization (as a non-sector-bound
nonlinearity) over both academic and real data. Our results show that the log-
scale quantization leads to a smaller optimality gap for distributed training.
We further compare the quantized setups over exponential and random (geometric
and ER) networks, and, as expected, the exponential graph as a structured
network results in a smaller optimality gap as compared to geometric and ER
graphs representing ad-hoc multi-agent networks.

###  V-B Future Directions

Future research efforts will focus on considering the effect of quantization
on different machine learning techniques, for example, distributed
minimization of error-back-propagation in Neural-Networks and distributed
reinforcement learning. Application to distributed optimal control is another
direction of research interest.

## References

  * [1] H. Raja and W. U. Bajwa,  “Cloud K-SVD: a collaborative dictionary learning algorithm for big, distributed data,”  IEEE Transactions on Signal Processing, vol. 64, no. 1, pp. 173–188, 2015.
  * [2] S. Abbasian Dehkordi, K. Farajzadeh, J. Rezazadeh, R. Farahbakhsh, K. Sandrasegaran, and M. Abbasian Dehkordi,  “A survey on data aggregation techniques in IoT sensor networks,”  Wireless Networks, vol. 26, pp. 1243–1263, 2020.
  * [3] M. A. Rahimian, F. Yu, and C. Hurtado,  “Differentially private network data collection for influence maximization,”  in Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2023, pp. 2795–2797.
  * [4] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson,  “A survey of distributed optimization,”  Annual Reviews in Control, vol. 47, pp. 278–305, 2019.
  * [5] S. Hashempour, A. A. Suratgar, and A. Afshar,  “Distributed nonconvex optimization for energy efficiency in mobile ad hoc networks,”  IEEE Systems Journal, vol. 15, no. 4, pp. 5683–5693, 2021.
  * [6] S. Oh, H. Sim, S. Lee, and J. Lee,  “Automated log-scale quantization for low-cost deep neural networks,”  in IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 742–751.
  * [7] 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.
  * [8] N. Khademi Kalantari and S. M. Ahadi,  “A logarithmic quantization index modulation for perceptually better data hiding,”  IEEE Transactions on Image Processing, vol. 19, no. 6, pp. 1504–1517, 2010.
  * [9] J. Cai, M. Takemoto, and H. Nakajo,  “A deep look into logarithmic quantization of model parameters in neural networks,”  in Proceedings of the 10th International Conference on Advances in Information Technology, 2018, pp. 1–8.
  * [10] T. C. Aysal, M. Coates, and M. Rabbat,  “Distributed average consensus using probabilistic quantization,”  in IEEE/SP 14th Workshop on Statistical Signal Processing. IEEE, 2007, pp. 640–644.
  * [11] S. S. Pereira and A. Pages-Zamora,  “Distributed consensus in wireless sensor networks with quantized information exchange,”  in IEEE 9th Workshop on Signal Processing Advances in Wireless Communications. IEEE, 2008, pp. 241–245.
  * [12] A. Nedić and A. Olshevsky,  “Distributed optimization over time-varying directed graphs,”  IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014.
  * [13] C. Hadjicostis and T. Charalambous,  “Average consensus in the presence of delays in directed graph topologies,”  IEEE Transactions on Automatic Control, vol. 59, no. 3, pp. 763–768, 2013.
  * [14] S. Sundhar Ram, A. Nedić, and V. V. Veeravalli,  “Distributed stochastic subgradient projection algorithms for convex optimization,”  Journal of optimization theory and applications, vol. 147, pp. 516–545, 2010.
  * [15] A. Spiridonoff, A. Olshevsky, and I. Paschalidis,  “Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions,”  Journal of machine learning research, vol. 21, no. 58, 2020.
  * [16] A. Nedić and A. Olshevsky,  “Stochastic gradient-push for strongly convex functions on time-varying directed graphs,”  IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3936–3947, 2016.
  * [17] C. Xi, R. Xin, and U. A Khan,  “ADD-OPT: accelerated distributed directed optimization,”  IEEE Transactions on Automatic Control, vol. 63, no. 5, pp. 1329–1339, 2017.
  * [18] M. I. Qureshi, R. Xin, S. Kar, and U. A. Khan,  “S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs,”  IEEE Control Systems Letters, vol. 5, no. 3, pp. 953–958, 2020\.
  * [19] D. T. A. Nguyen, D. T. Nguyen, and A. Nedić,  “Geometric convergence of distributed heavy-ball nash equilibrium algorithm over time-varying digraphs with unconstrained actions,”  IEEE Control Systems Letters, 2023.
  * [20] Y. Nesterov,  Introductory lectures on convex optimization: A basic course, vol. 87,  Springer Science & Business Media, 2013.
  * [21] G. Qu and N. Li,  “Accelerated distributed nesterov gradient descent,”  IEEE Transactions on Automatic Control, vol. 65, no. 6, pp. 2566–2581, 2019.
  * [22] D. T. A. Nguyen, D. T. Nguyen, and A. Nedić,  “Accelerated ab/push-pull methods for distributed optimization over time-varying directed networks,”  IEEE Transactions on Control of Network Systems, 2023.
  * [23] M. I. Qureshi and U. A. Khan,  “Stochastic first-order methods over distributed data,”  in IEEE 12th Sensor Array and Multichannel Signal Processing Workshop (SAM), 2022, pp. 405–409.
  * [24] M. I. Qureshi, R. Xin, S. Kar, and U. A. Khan,  “Push-SAGA: a decentralized stochastic algorithm with variance reduction over directed graphs,”  IEEE Control Systems Letters, vol. 6, pp. 1202–1207, 2021.
  * [25] R. Xin, U. A. Khan, and S. Kar,  “A fast randomized incremental gradient method for decentralized nonconvex optimization,”  IEEE Transactions on Automatic Control, vol. 67, no. 10, pp. 5150–5165, 2021.
  * [26] X. Gong, Y. Cui, J. Shen, J. Xiong, and T. Huang,  “Distributed optimization in prescribed-time: Theory and experiment,”  IEEE Transactions on Network Science and Engineering, vol. 9, no. 2, pp. 564–576, 2021.
  * [27] L. Liu and G. Yang,  “Distributed fixed-time optimal resource management for microgrids,”  IEEE Transactions on Automation Science and Engineering, vol. 20, no. 1, pp. 404–412, 2022.
  * [28] S. Chen, H. Jiang, Z. Yu, and F. Zhao,  “Distributed optimization of single-integrator systems with prescribed-time convergence,”  IEEE Systems Journal, 2022.
  * [29] Y. Pu, M. N. Zeilinger, and C. N. Jones,  “Quantization design for distributed optimization,”  IEEE Transactions on Automatic Control, vol. 62, no. 5, pp. 2107–2120, 2016.
  * [30] S. Horváth, D. Kovalev, K. Mishchenko, P. Richtárik, and S. Stich,  “Stochastic distributed learning with gradient quantization and double-variance reduction,”  Optimization Methods and Software, vol. 38, no. 1, pp. 91–106, 2023\.
  * [31] M. G. Rabbat and R. D. Nowak,  “Quantized incremental algorithms for distributed optimization,”  IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 798–808, 2005.
  * [32] M. Doostmohammadian, A. Aghasi, M. Vrakopoulou, H. R. Rabiee, U. A. Khan, and T. Charalambous,  “Distributed delay-tolerant strategies for equality-constraint sum-preserving resource allocation,”  Systems & Control Letters, vol. 182, pp. 105657, 2023.
  * [33] A. Jadbabaie, J. Lin, and A. S. Morse,  “Coordination of groups of mobile autonomous agents using nearest neighbor rules,”  IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988–1001, 2003.
  * [34] M. Doostmohammadian, A. Aghasi, T. Charalambous, and U. A. Khan,  “Distributed support vector machines over dynamic balanced directed networks,”  IEEE Control Systems Letters, vol. 6, pp. 758–763, 2021.
  * [35] K. Scaman, F. Bach, S. Bubeck, Y. Lee, and L. Massoulié,  “Optimal algorithms for smooth and strongly convex distributed optimization in networks,”  in international conference on machine learning. PMLR, 2017, pp. 3027–3036.
  * [36] A. Nedić, A. Olshevsky, and M. G. Rabbat,  “Network topology and communication-computation tradeoffs in decentralized optimization,”  Proceedings of the IEEE, vol. 106, no. 5, pp. 953–976, 2018.
  * [37] B. Ying, K. Yuan, Y. Chen, H. Hu, P. Pan, and W. Yin,  “Exponential graph is provably efficient for decentralized deep training,”  Advances in Neural Information Processing Systems, vol. 34, pp. 13975–13987, 2021.
  * [38] F. Fagnani and S. Zampieri,  “Average consensus with packet drop communication,”  SIAM Journal on Control and Optimization, vol. 48, no. 1, pp. 102–133, 2009.
  * [39] N. H. Vaidya, C. N. Hadjicostis, and A. D. Dominguez-Garcia,  “Robust average consensus over packet dropping links: Analysis via coefficients of ergodicity,”  in 51st IEEE Conference on Decision and Control, 2012, pp. 2761–2766.
  * [40] A. Datar, D. Schneider, F. Mirali, H. Werner, and H. Frey,  “A memory weighted protocol for sampled-data systems subjected to packet dropouts,”  in American Control Conference (ACC). IEEE, 2018, pp. 2485–2490.
  * [41] R. Olfati-Saber, J. A. Fax, and R. M. Murray,  “Consensus and cooperation in networked multi-agent systems,”  IEEE Proceedings, vol. 95, no. 1, pp. 215–233, January 2007.
  * [42] K. Cai and H. Ishii,  “Average consensus on general strongly connected digraphs,”  Automatica, vol. 48, no. 11, pp. 2750–2761, 2012.
  * [43] R. Olfati-Saber and R. M. Murray,  “Consensus problems in networks of agents with switching topology and time-delays,”  IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520–1533, Sept. 2004.
  * [44] J. E. Slotine and W. Li,  Applied nonlinear control,  Prentice hall Englewood Cliffs, NJ, 1991.
  * [45] M. Doostmohammadian, M. Pirani, U. A. Khan, and T. Charalambous,  “Consensus-based distributed estimation in the presence of heterogeneous, time-invariant delays,”  IEEE Control Systems Letters, vol. 6, pp. 1598 – 1603, 2021.
  * [46] G. W. Stewart and J. Sun,  Matrix perturbation theory,  Academic Press, 1990.
  * [47] M. Doostmohammadian, A. Aghasi, A. I. Rikos, A. Grammenos, E. Kalyvianaki, C. Hadjicostis, K. H. Johansson, and T. Charalambous,  “Distributed CPU scheduling subject to nonlinear constraints,”  in IEEE Conference on Control Technology and Applications (CCTA). IEEE, 2022, pp. 746–751.

|  Mohammadreza Doostmohammadian received his B.Sc. and M.Sc. in Mechanical
Engineering from Sharif University of Technology, Iran, respectively in 2007
and 2010, where he worked on applications of control systems and robotics. He
received his PhD in Electrical and Computer Engineering from Tufts University,
MA, USA in 2015. During his PhD in Signal Processing and Robotic Networks
(SPARTN) lab, he worked on control and signal processing over networks with
applications in social networks. From 2015 to 2017 he was a postdoc researcher
at ICT Innovation Center for Advanced Information and Communication Technology
(AICT), School of Computer Engineering, Sharif University of Technology, with
research on network epidemic, distributed algorithms, and complexity analysis
of distributed estimation methods. He was a researcher at Iran
Telecommunication Research Center (ITRC), Tehran, Iran in 2017 working on
distributed control algorithms and estimation over IoT. Since 2017 he has been
an Assistant Professor with the Mechatronics Department at Semnan University,
Iran. From 2021 to 2022, he was a visiting researcher at the School of
Electrical Engineering and Automation, Aalto University, Espoo, Finland,
working on constrained and unconstrained distributed optimization techniques
and their applications. His general research interests include distributed
estimation, control, learning, and optimization over networks. He was the
chair of the robotics and control session at the ISME-2018 conference, the
session chair at the 1st Artificial Intelligent Systems Conference of Iran,
2022, and the Associate Editor of IEEE/IFAC CoDIT2024 conference.
---|---
|  Muhammad I. Qureshi received the B.S. degree in electrical engineering from
the University of Engineering and Technology Lahore, Pakistan, in 2017, and
the Ph.D. degree in electrical and computer engineering from Tufts University,
USA, in 2024. He was working as a Research Scientist at Tufts University under
the supervision of Prof. Usman A. Khan. Currently, he is a researcher at Intel
corporation.
---|---
|  Mohammad Hossein Khalesi received his B.Sc. degree in Mechanical
Engineering and also in Aerospace Engineering, M.Sc. degree in Mechanical
Engineering, and Ph.D. in Mechanical Engineering all from Sharif University of
Technology, Tehran, Iran, respectively in 2011, 2013, and 2019. Currently, he
is an assistant professor of Mechanical Engineering at Semnan University,
Semnan, Iran.
---|---
|  Hamid R. Rabiee received his BS and MS degrees (with Great Distinction) in
Electrical Engineering from CSULB, Long Beach, CA (1987, 1989), his EEE degree
in Electrical and Computer Engineering from USC, Los Angeles, CA (1993), and
his Ph.D. in Electrical and Computer Engineering from Purdue University, West
Lafayette, IN, in 1996. From 1993 to 1996 he was a Member of Technical Staff
at AT&T Bell Laboratories. From 1996 to 1999 he worked as a Senior Software
Engineer at Intel Corporation. He was also with PSU, OGI and OSU universities
as an adjunct professor of Electrical and Computer Engineering from 1996-2000.
Since September 2000, he has joined Sharif University of Technology, Tehran,
Iran. He was also a visiting professor at the Imperial College of London for
the 2017-2018 academic year. He is the founder of Sharif University Advanced
Information and Communication Technology Research Institute (AICT), ICT
Innovation Center, Advanced Technologies Incubator (SATI), Digital Media
Laboratory (DML), Mobile Value Added Services Laboratory (VASL),
Bioinformatics and Computational Biology Laboratory (BCB) and Cognitive
Neuroengineering Research Center. He has also been the founder of many
successful High-Tech start-up companies in the field of ICT as an
entrepreneur. He is currently a Professor of Computer Engineering at Sharif
University of Technology, and Director of AICT, DML, and VASL. He has been the
initiator and director of many national and international level projects in
the context of Iran National ICT Development Plan and UNDP International Open
Source Network (IOSN). He has received numerous awards and honors for his
Industrial, scientific and academic contributions. He has acted as chairman in
a number of national and international conferences, and holds three patents.
He is also a Member of IFIP Working Group 10.3 on Concurrent Systems, and a
Senior Member of IEEE. His research interests include statistical machine
learning, Bayesian statistics, data analytics and complex networks with
applications in social networks, multimedia systems, cloud and IoT privacy,
bioinformatics, and brain networks.
---|---
|  Usman A. Khan is a Professor of Electrical and Computer Engineering (ECE)
at Tufts University with a secondary appointment in Computer Science. He is
also an Amazon Scholar with Amazon Robotics. His research interests include
artificial intelligence, machine learning, robotics, optimization and control,
and stochastic dynamical systems. He has published extensively in these topics
with more than 125 articles in journals and conference proceedings and holds
multiple patents. Recognition of his work includes the prestigious National
Science Foundation (NSF) Career award, several federally funded projects and
NSF REU awards, an IEEE journal cover, and several news articles including two
in IEEE Spectrum. He received the 2023 Tufts Inventor award, the 2022 EURASIP
Best Paper Award for articles published in the EURASIP Journal on Advances in
Signal Processing over 2017-2021, and Best Student Paper awards at the IEEE
International Conference on Networking, Sensing and Control (2014), and at the
IEEE Asilomar Conference (2014 and 2016). Dr. Khan received his B.S. degree in
2002 from University of Engineering and Technology, Pakistan, M.S. degree in
2004 from University of Wisconsin-Madison, USA, and Ph.D. degree in 2009 from
Carnegie Mellon University, USA, all in ECE. He was a postdoctoral researcher
in the GRASP robotics lab at the University of Pennsylvania and also has held
a Visiting Professor position at KTH, Sweden. Dr. Khan is an IEEE Senior
Member and was an elected full member of the Sensor Array and Multichannel TC
with the IEEE Signal Processing Society from 2019-2022, where he was an
Associate member from 2010 to 2019. He was an elected full member of the IEEE
Big Data Special Interest Group from 2017 to 2019, and has served on the IEEE
Young Professionals Committee and on the IEEE Technical Activities Board. He
has served as an Associate Editor on several top-tier IEEE publications: IEEE
Transactions on Smart Grid (2014-2017); IEEE Control System Letters
(2018-2020), IEEE Transactions on Signal and Information Processing over
Networks (2019-current), where he received the 2023 Outstanding Editorial
Member award; IEEE Open Journal of Signal Processing (2019-current); and IEEE
Transactions on Signal Processing (2021-2023), where currently he is a Senior
Area Editor. He served as the Chief Editor for the Proceedings of the IEEE
special issue on Optimization for Data-driven Learning and Control (Nov.
2020), and as a Guest Associate Editor for the IEEE Control System Letters
special issue on Learning and Control (Nov. 2020). He served as the Technical
Area Chair for the Networks track in 2020 IEEE Asilomar Conference on Signals
Systems and Computers and for the Signal Processing for Self Aware and Social
Autonomous Systems track at the 1st IEEE International Conference on
Autonomous Systems (Aug. 2021).
---|---