Saeed Damadi, Erfan nouri, and Hamed Pirsiavash 11institutetext: Department of
Computer Science and Electrical Engineering
University of Maryland, Baltimore County
Baltimore, MD 21250
11email<EMAIL_ADDRESS>
# Amenable Sparse Network Investigator

Saeed Damadi  Erfan nouri  Hamed Pirsiavash

###### Abstract

We present “Amenable Sparse Network Investigator” (ASNI) algorithm that
utilizes a novel pruning strategy based on a sigmoid function that induces
sparsity level globally over the course of one single round of training. The
ASNI algorithm fulfills both tasks that current state-of-the-art strategies
can only do one of them. The ASNI algorithm has two subalgorithms: 1) ASNI-I,
2) ASNI-II. ASNI-I learns an accurate sparse off-the-shelf network only in one
single round of training. ASNI-II learns a sparse network and an
initialization that is quantized, compressed, and from which the sparse
network is trainable. The learned initialization is quantized since only two
numbers are learned for initialization of nonzero parameters in each layer L.
Thus, quantization levels for the initialization of the entire network is 2L.
Also, the learned initialization is compressed because it is a set consisting
of 2L numbers. The special sparse network that can be trained from such a
quantized and compressed initialization is called amenable. For example, in
order to initialize more than 25 million parameters of an amenable ResNet-50,
only 2x54 numbers are needed. To the best of our knowledge, there is no other
algorithm that can learn a quantized and compressed initialization from which
the network is still trainable and is able to solve both pruning tasks. Our
numerical experiments show that there is a quantized and compressed
initialization from which the learned sparse network can be trained and reach
to an accuracy on a par with the dense version. This is one step ahead towards
learning an ideal network that is sparse and quantized in a very few levels of
quantization. We experimentally show that these 2L levels of quantization are
concentration points of parameters in each layer of the learned sparse network
by ASNI-I. In other words, we show experimentally that for each layer of a
deep neural network (DNN) there are two distinct normal-like distributions
whose means can be used for initialization of an amenable network. To
corroborate the above, we have performed a series of experiments utilizing
networks such as ResNets, VGG-style, small convolutional, and fully connected
ones on ImageNet, CIFAR10, and MNIST datasets.

###### keywords:

pruning, initialization, nonconvex sparse optimization

Figure 1: Pruning tasks.

##  1 Introduction

As indicated in Fig. 1, pruning of a DNN is done to fulfill two tasks: (1)
obtaining an accurate sparse network, ready to use, whose test accuracy is on
a par with the dense version of the network, and (2) finding trainable sparse
structures that can be trained in isolation and reach test accuracy of the
dense network. The goal of the first task is to provide an accurate off-the-
shelf-network that can be used in small devices, such as smart phones.
Although algorithms that solve the first task are very mature by now, solving
the second pruning task is an ongoing research topic. Solving the latter task
is of importance because over-parameterization [3] has been an obstacle for
interpretability of parameters in the network. Therefore, finding a sparse
network that can fit to a data from scratch would help to interpret parameters
of a DNN.

To find a trainable sparse network, [6] was the first work that proposes an
algorithm that can solve the second task of pruning, i.e., the lottery ticket
algorithm. Since then search for finding a sparse trainable network has
attracted a lot of attention. However, the lottery ticket algorithm (LTA)
requires multiple rounds of training and it fails to find the ticket for large
networks, i.e., ResNet-50. Foresight pruning or pruning before training [25,
42, 40] tries to address the first issue. However, none of foresight pruning
methods perform as good as methods that obtain sparse structures using gradual
pruning [10]. The stabilized LTA, [8], shows that the second issue of LTA can
be solved. By changing the initialization that uses values different than the
original initialization, [8] shows a large sparse structure obtained from the
stabilized LTA reaches test accuracy approximately. The stabilized LTA uses
values of the learned parameters at $k$-th iteration of the first training
round. This change is equivalent to using another sparse initialization for
training of a sparse network. Also, it shows that there might be some other
initialization from which a sparse network is trainable. Inspired by that, we
learn another initialization that is quantized, compressed, and from that the
sparse network is trainable. To this end, we present the “Amenable Sparse
Network Investigator” (ASNI) which performs as well as the state-of-the-art
algorithms in solving the first task of pruning and solves the second task of
pruning by learning an amenable sparse network that is trainable from a
learned quantized and compressed initialization. To the best of our knowledge
there is no other algorithm that can solve both two tacks together. Also, the
ASNI algorithm is the first proposed algorithm that learns a quantized and
compressed initialization from which a sparse network is trainable.

Figure 2: Parameter distribution of ResNet-50 trained on ImageNet with ASNI-I.
ResNet-50 has 4 main stages where stages have 3, 4, 6, and 3 bottlenecks,
respectively. The first bottleneck of each stage has 3 convolution layers and
a skip connection. This picture shows parameter distribution of the first
bottleneck in the forth stage at overall sparsity percentage of $s=80\%$. Two
short bars indicate $c_{+}$ and $c_{-}$ of each layer. These bars are the
averages of parameters and used for the initialization of the learned amenable
sparse network. They are found by ASNI-II in lines 13 and 15 in Alg. 3. To see
all stages of the network, check Appendix.

In summary, the following are our contributions:

  * •

We present the ASNI algorithm (Alg. 3) that solves both pruning tasks via two
subalgorithms. In only one single round of training, ASNI-I utilizes a novel
simple pruning strategy based on a sigmoid function that induces sparsity
globally across the network and learns an accurate sparse network. Fig. 3
shows how one can select the parameters of the sigmoid function properly to
avoid harmful consequences of pruning during the training process.

  * •

ASNI-II solves the second task of pruning. It takes the output of ASNI-I and
learns an amenable sparse network with its corresponding quantized and
compressed initialization. We experimentally show that the learned
initialization is a set of averages; the average is taken over positive and
negative learned parameters by ASNI-I for each layer, i.e., lines 12 and 14 in
Alg. 3. Fig. 2 shows the parameter distribution of the output of ASNI-I for
ResNet-50 where each layer has two distinct normal-like distributions whose
means are used as the learned initialization. This pattern repeats for all
networks that we study.

  * •

Finally, as given in Tab. 2, we show that the amenable sparse network equipped
with the learned quantized and compressed initialization approximately
achieves the test accuracy of the dense network.

We compare ASNI-I against its counterparts [45, 21, 5] where the two last ones
are the state-of-the-art methods. We show numerically that ASNI-I solves the
first task of pruning with higher accuracy. Also, we show that the test
accuracy of a sparse amenable network learned by ASNI-I and initialized by the
quantized and compressed initialization learned by ASNI-II is higher than its
counterparts. This is the case either with methods that solve the second task
of pruning in one round [7, 9] or the ones that use foresight pruning, i.e.,
[25, 42]. Hence, the ASNI algorithm is capable of solving both tasks of
pruning.

Figure 3: This figure shows different global sparsity percentages obtained
from sigmoid function. The sparsity percentage is applied across the network
during $E=90$ training epochs. The value of $\gamma$ determines the transition
slope from a low sparsity percentage to a high one. For large $\gamma$, e.g.,
100, the slope is small and almost constant during all epochs. In this case,
the initial sparsity percentage is high which means a lot of pruning takes
place at the beginning. For small $\gamma$, e.g., 1, the transition slope is
very sharp which means at some epoch of training a lot of pruning happens. The
best one with $\beta=0.5$ and $\gamma=E/10=9$ allows the network to learn with
the full capacity at the early epochs, i.e., up to $e=10$. Then, the network
sparsity starts increasing with a very small slope to make sure learning of
the sparse structure is done properly, i.e., $e=10-30$. After learning the
structure of the network, pruning increases with a constant slope, i.e.,
$e=30-60$. Then, pruning decreases very rapidly to allow the network heal from
pruning, i.e., $e=60-80$. Finally, to fine tune the survived parameters
pruning is almost zero from $e=80-90$.

##  2 Related Work

In this section we will go over related work trying to solve the first and
second tasks of pruning as indicated in Fig. 1. We focus on the second task
since it is a newer task compare to the first one.

###  2.1 First task of pruning

Working on the first task of pruning started more than 30 years ago [15, 24,
16]. However, for deep neural networks, initially [14] showed that it is
possible to achieve off-the shelf-sparse networks simply by magnitude-wise
pruning. Since then, many works have been done using this concept, [13, 43,
12, 31, 26, 32] and [29, 28, 27, 41, 30, 4]. The current approach for solving
this task is learning an accurate sparse network in one single round of
training. [45] was the first work that tried to learn an accurate sparse
network in this way. The current state-of-the-art [21] and [5] solve this task
via one single round of training. The former starts from a dense network but
the latter starts from a sparse network that has desired sparsity and finds a
an accurate sparse network.

###  2.2 Second task of pruning

Solving the second task of pruning is to find a sparse trainable network. To
solve it, one needs to find a mask. This mask may be found in multiple rounds
of training or without training. We will go over both cases.

####  2.2.1 Multiple rounds of training

To solve the second task [6] proposes a practical way of finding a sparse
trainable network. The so-called lottery ticket algorithm learns a mask in
multiple rounds of training and then shows that the associated sparse network
is trainable from a specific sparse initialization. This initialization is
determined using the learned mask and the original initialization. However,
LTA is not able to find tickets for large networks like ResNet-50. The problem
is that the sparse network can not be trained from the sparse initialization.
Hence, the stabilized LTA, [8], uses parameters of the $k$-th step from the
first training round as the initialization to reach test accuracy of the dense
network approximately. Rewinding to an intermediate step $k$ in order to
obtain a sparse trainable network has also been observed by [44]. Necessity
for rewinding to the $k$-th step utilized by [8] and [44] corroborates the
observation in [1] that states “in the early stages of training, important
connectivity patterns among parameters of layers are discovered”. Also, it has
been observed that the learned connectivity patterns stay relatively fixed in
the later steps of training.

The LTA has an uncomplicated strategy to force more sparsity into the network.
It applies a specific sparsity percentage at the end of each round of
training. Although it is very easy to implement, it may not be an optimal
strategy for reducing the number of parameters. The pruning strategy of the
LTA can be improved as [38] uses a continuous strategy to remove parameters at
each round of training. However, this is done at the expense of doubling the
number of parameters.

####  2.2.2 Foresight pruning: zero round of training

[6], [8], and [38] all search for a sparse structure utilizing multiple rounds
of training which is very costly. The best way could be finding a sparse
structure even before training. This is called foresight pruning or pruning
before training. To this end, [25] (SNIP) was the first work that posited the
idea of foresight pruning which determines a mask before training. In this
approach, a connection sensitivity score is calculated before training and
parameters are removed based on the score vector. Others have tried to find
different scoring vectors. For example, [42] introduces GraSP which utilizes
Hessian-gradient product to find a score vector. As opposed to the previous
proposed methods, [40] finds a sparse structure using different scoring in $n$
rounds of pruning.

####  2.2.3 Multiple- and zero-round are extreme

It is true that finding the sparse structure before training is the ideal
approach and may have a negligible computational cost to find a mask, but the
performance of the methods that apply pruning before training is not
competitive with performance of networks whose initialization is obtained
using pruning far later in training [10, 9]. To avoid multi-round training
computation and loss accuracy in foresight pruning [9] uses magnitude based
pruning approach that learns a sparse structure in a single round. Similarly,
[7] uses one round plus some $k$ steps to find the new set of initialization.
Considering these two last methods, our approach learns a sparse structure in
one single round of training.

##  3 Finding a sparse trainable network

In this section we first define the exact optimization problem that solves the
first task of pruning. Then, we elaborate on how changing initialization
results in solving the second task of pruning.

###  3.1 Problem explanation

Finding a sparse network whose accuracy is on a par with a dense network
amounts to solving a bi-level, constrained, stochastic, nonconvex, and non-
smooth sparse optimization problem as follows:

$\displaystyle\bm{\theta}*$
$\displaystyle=\arg\min_{\hat{\bm{\theta}}}||\hat{\bm{\theta}}||_{0}$ (1)
$\displaystyle\text{ s.t.
}\hat{\bm{\theta}}=\arg\min_{\bm{\theta}}\mathbb{E}_{\mathbf{x}\sim\mathcal{D}}\Big{[}f\Big{(}\mathbf{y}(\mathbf{x}),\bm{h}(\mathbf{x};\bm{\theta})\Big{)}\Big{]}$

where $\bm{h}(\mathbf{x};\bm{\theta})$ is the vector-valued neural network
function whose input is a random vector $\mathbf{x}\sim\mathcal{D}$ labeled by
random vector $\mathbf{y}(\mathbf{x})$ and its parameters are denoted by
$\bm{\theta}\in\mathbb{R}^{d}$. The scalar-valued function $f$ is the cost or
loss function, also known as the criterion, $||\bm{\theta}||_{0}$ is the
number of nonzero elements of $\bm{\theta}$, or the $\ell_{0}$ norm
111$\ell_{0}$ is not mathematically a norm because for any norm $\|\cdot\|$
and $\alpha\in\mathbb{R}$, $\|\alpha\bm{\theta}\|=|\alpha|\|\bm{\theta}\|$,
while $\|\alpha\bm{\theta}\|_{0}=|\alpha|\|\bm{\theta}\|_{0}$ if and only if
$|\alpha|=1$. In Problem $(\ref{eq:1})$: having two optimizations
simultaneously makes it bi-level, $\mathcal{D}$ is the source of stochasticity
and is unknown, composition of $f$ and $\bm{h}$ make the objective function
nonconvex; since $\ell_{0}$ norm is not differentiable, one deals with a non-
smooth problem. If one can solve Problem $(\ref{eq:1})$, the energy
consumption reduces, hardware requirements are relaxed, and performing
inference become faster. Unfortunately, even a deterministic and convex sparse
optimization problem, e.g., least-squares problem, is a combinatorial and NP-
hard problem [2, 33]. Therefore, the best approach is to convert the current
bi-level optimization problem into another optimization problem that is
neither bi-level, stochastic, nor non-smooth. Solving the new optimization
problem will find an approximate solution to the original Problem (1), i.e.,
$\bm{\hat{\theta}}*$. However, the unanswered question is how to convert
Problem (1) to a solvable approximate problem. By trial and error, one can
find an upper bound for the sparsity of the vector parameter, i.e.,
$||\bm{\theta}*||_{0}\lessapprox\hat{s}$. Given the sparsity level $\hat{s}$,
we get the following optimization problem:

$\displaystyle(\tilde{\bm{\theta}}*\odot\tilde{\bm{m}}*)$
$\displaystyle=\arg\min_{\bm{\theta},\bm{m}}\mathbb{E}_{\mathbf{x}\sim\mathcal{D}}\Big{[}f\Big{(}\mathbf{y}(\mathbf{x}),\bm{h}(\mathbf{x};\bm{\theta}\odot\bm{m})\Big{)}\Big{]}$
(2) s.t. $\displaystyle||\bm{m}||_{0}\leq\hat{s}$

where $\bm{m}=\\{0,1\\}^{d}$ is a binary mask and $\odot$ denotes Hadamard
product operator. Unlike Problem (1) where a sparsity level is automatically
found, i.e., $s*$, here sparsity level $\hat{s}$ is given. Because of this
fact, solutions to Problem (1) and (2), that are $\bm{\theta}*$ and
$\tilde{\bm{\theta}}*\odot\tilde{\bm{m}}*$, may not be the same. Having an
accurate estimate for $\hat{s}\gtrapprox s*$ relaxes Problem (1) from being a
bi-level optimization problem to a single level problem. However, all the
other issues mentioned above still stay with Problem (2). Now from the
perspective of optimization, the first question would be whether this problem
is feasible or not. Empirically, [6] addressed this problem for the first time
and conjectures that such a solution exists and named their conjecture the
lottery ticket hypothesis. Mathematically speaking, the lottery ticket
hypothesis conjectures that Problem (2) for $\hat{s}\gtrapprox s*$ is feasible
and there exists a solution to that.

Once we know the solution exists, the most straightforward approach to find an
approximate solution to Problem (2) is to first find a mask $\hat{\bm{m}}$
which is a good estimate of $\tilde{\bm{m}}*$. To estimate $\hat{\bm{m}}$,
there are two extreme approaches. One approach finds $\hat{\bm{m}}$ using
multiple rounds of training [6, 8, 38], and the other finds it before training
[25, 42, 40]. As opposed to the latter, the former reaches test accuracy of
the dense network [10, 9], but it is computationally expensive. Once an
accurate mask, i.e., $\hat{\bm{m}}\approx\tilde{\bm{m}}*$ is at hand, the non-
smoothness and constraint of Problem (2) can be relaxed. Also, by assuming
large sample size and using stochastic approximation of the expected value in
the objective function [11], one can use the following unconstrained
optimization problem as a relaxation for Problem (2):

$\displaystyle(\hat{\bm{\theta}}*\odot\hat{\bm{m}})$
$\displaystyle=\arg\min_{\bm{\theta}}R(\mathbf{X};\bm{\theta}\odot\hat{\bm{m}})$
(3)

where $R(\mathbf{X};\bm{\theta}\odot\hat{\bm{m}})$ is the approximation of the
expected value as

$M^{-1}\sum_{i=1}^{M}f\Big{(}\boldsymbol{y}(\boldsymbol{x}^{(i)}),\bm{h}(\boldsymbol{x}^{(i)};\bm{\theta}\odot\hat{\bm{m}})\Big{)},$

$\mathbf{X}$ is the data matrix as
$\begin{bmatrix}\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(M)}\end{bmatrix}$,
$\boldsymbol{x}^{(i)}$ for $i=1,\dots,M$ is a realization of
$\mathbf{x}\sim\mathcal{D}$, and $\boldsymbol{y}(\boldsymbol{x}^{(i)})$ is the
realized target associated with $\boldsymbol{x}^{(i)}$.

###  3.2 Initialization of the stabilized LTA vs LTA

Algorithm 1 The LTA, [6]

1:$\bm{\theta}^{0}$, $\hat{\bm{m}}=\bm{1}$, $T$, $p\%$, $r$

2:for 1 to r do

3: Optimize $R(\mathbf{X};\bm{\theta}^{0}\odot\hat{\bm{m}})$ for T steps

4: Keep $p$-th percentile of $|\bm{\theta}^{T}|\neq 0\text{ and update
}\hat{\bm{m}}$

5: Rewind nonzero values of $\bm{\theta}^{T}$ to $\bm{\theta}^{0}$ and update
$\bm{\theta}^{0}$

6:end for

Algorithm 2 The stabilized LTA, [8]

1:$\bm{\theta}^{0}$, $\hat{\bm{m}}=\bm{1}$, $T$, $p\%$, $k$, $r$

2:for j=1 to r do

3: Optimize $R(\mathbf{X};\bm{\theta}^{0}\odot\hat{\bm{m}})$ for T steps

4: if $j=1$ then$\quad\text{save
}\tilde{\bm{\theta}}^{0}\leftarrow\bm{\theta}^{k}$

5: end if

6: Keep $p$-th percentile of $|\bm{\theta}^{T}|\neq 0\text{ and update
}\hat{\bm{m}}$

7: Rewind nonzero values of $\bm{\theta}^{T}$ to $\tilde{\bm{\theta}}^{0}$ and
create $\bm{\theta}^{0}$

8:end for

Given a mask $\hat{\bm{m}}$, every initialization from which Problem (3) can
be solved iteratively is an acceptable initialization. The LTA algorithm in
Alg. 1, proposes an initialization that is based on the original
initialization. On the other hand, the stabilized LTA in Alg. 1 uses the
learned parameters of the $k$-th step of training as the initialization. Our
algorithm will learn another acceptable initialization using ASNI-II.

To elaborate on the importance of the initialization notice that the LTA
proposes Alg. 1 that solves Problem (3) for $r$ rounds when $\hat{\bm{m}}$ is
assumed to be given in each round. It starts from a dense random
initialization and a mask whose elements are all one, i.e.,
$\hat{\bm{m}}=\bm{1}$. Then, it trains the network for $T$ steps. At the end
of training $p\%$ of nonzero parameters are zerod out and mask gets updated.
Finally, nonzero parameters are rewound to their associated entries in the
original initialization to update the initialization for the next round of
training.

The issue with Alg. 1 is that it fails to find the winner ticket for large
networks such as ResNet-50. This issue is solved by the stabilized LTA given
in Alg. 2. As one can see in Alg. 1, LTA rewinds the learned parameters to the
original initialization while the stabilized LTA rewinds the learned
parameters to the $k$-th step of the first round of training. This little
tweak stabilizes the LTA and makes it possible to find winning tickets for
large networks. As we will see later, ASNI-II rewinds the nonzero parameters
to the average of parameters learned by ASNI-I. This rewind is done so that
sign of each learned initialization element is in accordance with learned
parameters by ASNI-I.

##  4 Method

Algorithm 3 The ASNI

1:Initial parameter vector $\bm{\theta}^{0}$, training data $\mathbf{X}_{tr}$,
epochs $E$, optimizer’s parameters, e.g., initial learning rate
$\eta=\eta_{0}$, cosine scale $\delta$, mini-batch size $b$, initial mask
vector $\hat{\bm{m}}=\bm{1}$, sigmoid’s parameters $\alpha$, $\beta$,
$\gamma$.

2:ASNI-I:

3:for $e=1$ to $E$ do

4: for $k=1$ to $T$ do

5:
$\displaystyle{\bm{\theta}^{k}\leftarrow{\bm{\theta}}^{k-1}-\eta\left(\nabla
R(\mathbf{X}_{tr,b};\bm{\theta}^{k-1})\right)\odot\hat{\bm{m}}}$

6: end for

7: $\displaystyle{p=\alpha\,\text{sigmoid}((e-\beta E)/\gamma)}$

8: $\displaystyle{\tau_{g}=p\text{-th}\text{ percentile of
}\\{|\bm{\theta}|\\}}$

9: $\displaystyle{\hat{\bm{m}}=\bm{1}_{|s|\geq\tau_{g}}(|\mathbf{s}|)}$

10: $\displaystyle{\bm{\theta}^{0}\leftarrow\bm{\theta}^{T}\odot\hat{\bm{m}}}$

11:end for

12:$\displaystyle{\hat{\bm{\theta}}*\leftarrow\bm{\theta}^{0}}$

13:ASNI-II:

14:for $l=1$ to $L$ do

15:
$\displaystyle{\bar{c}_{+}^{[l]}=\text{mean}({\hat{\bm{\theta}}*}^{[l]}>0)}$

16:
$\displaystyle{{\bm{\theta}^{[l]}}_{+}^{0}=\bar{c}_{+}^{[l]}\bm{1}_{{\hat{\bm{\theta}}*}^{[l]}>0}({\hat{\bm{\theta}}*}^{[l]})}$

17:
$\displaystyle{\bar{c}_{-}^{[l]}=\text{mean}({\hat{\bm{\theta}}*}^{[l]}<0)}$

18:
$\displaystyle{{\bm{\theta}^{[l]}}_{-}^{0}=\bar{c}_{-}^{[l]}\bm{1}_{{\hat{\bm{\theta}}*}^{[l]}<0}({\hat{\bm{\theta}}*}^{[l]})}$

19:
$\displaystyle{{\bm{\theta}^{[l]}}^{0}={\bm{\theta}^{[l]}}_{-}^{0}+{\bm{\theta}^{[l]}}_{+}^{0}}$

20:end for

21:$\displaystyle{\textbf{Output:\quad}\hat{\bm{{\theta}}}*,\bm{{\theta}}^{0},\bar{\mathbf{c}}_{+},\bar{\mathbf{c}}_{-}\text{~{}and~{}}\hat{\bm{m}}}$

In this section we introduce the ASNI algorithm and explain how one can set
its parameters.

###  4.1 The ASNI algorithm

The ASNI algorithm first learns an off-the-shelf accurate sparse structure via
its subalgorithms ASNI-I. This learned sparse structure is trainable. Its
trainability depends on $L$ pairs of signed centroids that are sufficient for
its initialization. Being able to be trained from a compressed set of
initialization, makes the learned sparse network amenable. As Fig. (2) shows,
after learning parameters by ASNI-I, distribution of each layer $l$ has a pair
of signed centroids (positive and negative), i.e.,
$\bar{\mathbf{c}}_{+}^{[l]}$, $\bar{\mathbf{c}}_{-}^{[l]}$. These centroids
are at the mean values of two distinct normal-like distributions. Once these
centroids are replaced instead of positive and negative learned values, the
sparse network is amenable and reaches virtually the nominal test accuracy of
the dense network. Hence, the second task of pruning is solved using ASNI-II.

One crucial part of the ASNI algorithm is where the sigmoid function is
utilized because it determines the global sparsity percentage. This sparsity
percentage is initialized to be zero and is updated at line 5 of Alg. (3).
According to line 6, ASNI-I prunes nonzero parameters of the network with
respect to a global pruning threshold, i.e., $\tau_{g}>0$. This global pruning
threshold is obtained after each epoch of training. The global threshold is
calculated by gathering magnitudes of all parameters except the bias and batch
normalization parameters. We do not include bias and batch normalization
parameters since the number of these parameters is negligible. The global
threshold, i.e., $\tau_{g}$, is found such that the magnitude of $p\%$ of all
gathered parameters are less than $\tau_{g}$, and $(100-p)\%$ are above the
global threshold. Next in line 7 222$\bm{1}_{A}(x)=\\{1\text{ if }x\in
A\text{,}0\text{ if }x\notin A\\}$, ASNI-I zeros out the entries of the mask
vector for those parameters whose magnitudes are less than $\tau_{g}$. This is
where the mask vector $\hat{\bm{m}}$ gets updated. Once ASNI-I updates the
mask, retraining restarts for another epoch. As the last epoch finishes, the
vector of parameters would be the learned sparse vector, i.e.,
$\hat{\bm{{\theta}}}*$. This learned sparse vector together with its mask is
an approximate solution to Problem (2). When $\bm{\hat{\theta}}*$ is found, by
following lines 11-16, centroids
($\bar{\mathbf{c}}_{+}^{[l]},\bar{\mathbf{c}}_{-}^{[l]}$) are calculated to
learn the quantized and compressed initialization. Also, the mask
$\hat{\bm{m}}$ learned by ASNI-I identifies the sparse amenable network. Note
that initialization for batch normalization weights is one and initialization
for all biases would be zero.

###  4.2 ASNI parameters

ASNI algorithm follows a simple intuitive and easy strategy for determining
the global sparsity percentage for each epoch. In line 5, ASNI-I determines
sparsity percentage by utilizing a sigmoid function as
$p=\alpha\,\text{sigmoid}((e-\beta E)/\gamma)$ for $e=1,\dots,E$, where $E$ is
the total number of epochs, $\alpha$ controls the final sparsity, $\beta$
governs how early and late pruning starts and stops, and $\gamma$ controls how
fast pruning should be done. Although the sigmoid function has three
parameters, by determining two of them the last one is determined. Thus, we
only need to search for two parameters. We will explain how to chose these
parameters in the order of their importance. Hence, we start with the most
important parameter which is $\beta$.

####  4.2.1 How to choose $\beta$?

To apply the ASNI-I algorithm one needs to set $\beta$ to 0.5 for all
experiments. The value of $\beta$ shifts the position of the inflection point
of the sigmoid curve to the left or right. In Fig. 3, the inflection point is
at $45^{th}$ epoch. Therefore, up to that point, the sparsity percentage curve
is increasing while after $45^{th}$ epoch the sparsity percentage decreases.
Setting $\beta$ to 0.5 creates a symmetric curve about the inflection point of
sigmoid function. Generally, every sparsity curve like the ones in Fig. 3 has
three phases: 1) small pruning associated with learning the structure, 2)
pruning and learning, 3) small pruning for healing from pruning. Any value
other than 0.5 will be biased towards either phase 1 or 3.

####  4.2.2 How to choose $\gamma$?

The value of $\gamma$ determines the transition slope from a low sparsity
percentage to a high one. The lower $\gamma$, the higher transition slope form
a mild pruning strategy to an aggressive one. For a small $\gamma$, e.g., 1,
the slope in Fig. 3 is very sharp and so many parameters would be pruned in a
very few number of epochs. On the other hand, for a large $\gamma$, e.g., 100,
the slope in Fig. 3 is small and the curve becomes a line starting from high
sparsity percentages. This means we have a lot of pruning at the beginning.
According to our experiments, $\gamma=E/10$ accompanied by $\beta=0.5$
provides the best result for all networks we experimented.

####  4.2.3 How to choose $\alpha$?

As we explained, given two parameters the third one is determined. Therefore,
by determining $\beta$ and $\gamma$, the value of $\alpha$ is determined from
a desired sparsity percentage.

Table 1: Datasets and networks combination together with their hyper
parameters.

Comb. | Dataset | Network | Params | E | B | LR/WD | Iter.
---|---|---|---|---|---|---|---
1 | MNIST | FC | 266,610 | 50 | 60 | 1.2e-3 | 1000
2 | MNIST | Conv2 | 3,317,450 | 20 | 60 | 2e-4 | 1000
3 | MNIST | Conv4 | 1,933,258 | 25 | 60 | 3e-4 | 1000
4 | MNIST | Conv6 | 1,802,698 | 30 | 60 | 3e-4 | 1000
5 | CIFAR-10 | Conv2 | 4,301,642 | 20 | 60 | 2e-4 | 1000
6 | CIFAR-10 | Conv4 | 2,425,930 | 25 | 60 | 3e-4 | 1000
7 | CIFAR-10 | Conv6 | 2,262,602 | 30 | 60 | 3e-4 | 1000
8 | CIFAR-10 | VGG-11 | 9,231,114 | 160 | 128 | 0.05/5e-4 | 391
9 | CIFAR-10 | VGG-13 | 9,416,010 | 160 | 128 | 0.05/5e-4 | 391
10 | CIFAR-10 | VGG-16 | 14,728,266 | 160 | 128 | 0.05/5e-4 | 391
11 | CIFAR-10 | ResNet-18 | 11,181,642 | 160 | 128 | 0.08/5e-4 | 391
12 | ImageNet | ResNet-50 | 25,557,032 | 90 | 820 | 0.35/1e-4 | 6252

##  5 Experiments setup

This section explains the setup of our experiments for training. Tab. 1
summarizes experiments (dataset and network combinations) and their hyper
parameters including number of trainable parameters, number of epochs for
training (E), mini-batch size (B), the initial learning rate together with
weight decay (LR/WD), and number of iterations to complete an epoch (Iter.).
Also, we will elaborate on the learning rate policy and the optimizer choice
in the following subsections.

###  5.1 Datasets

Our experiments involve image classification on well-known datasets including
the MNIST [22], CIFAR-10 [20], and the ImageNet-1K [37]. For ImageNet-1K our
training pipeline uses a standard data augmentation including random flips and
crops.

###  5.2 Networks

Network architectures that we utilize include a 3-layer fully-connected
network (LeNet-300-100) [23] named FC, convolutional neural networks (CNNs),
named Conv-2, Conv-4, and Conv-6 (small CNNs with 2/4/6 convolutional layers,
same as in [6]). We also use ResNet-18/50 [18]. Additionally, we utilize VGG-
style networks [39] named as VGG-11/13/16 with batch normalization and an
average pooling after convolution layers followed by a fully connected layer.
As a result of the average pooling, parameter count of VGG-style networks
decreases which mitigates the parameter inefficiency with original VGG
networks.

###  5.3 Optimizer

We use stochastic gradient descent [36] with momentum [34] (SGD+M), or Adam
[19] as our optimizers. the Adam optimizer is used for experiments involving
small networks such as FC, Conv2/4/6. The SGD+M optimizer is used for the VGG-
style and ResNet networks. We set the momentum coefficient to 0.9 for all
experiments the SGD+M is used.

Figure 4:  Parameter distribution considering all parameters in ResNet-50
network trained on ImageNet-1K. The orange plot shows distribution of the
dense network initialization. The red plot is the distribution of the learned
parameters when the network is dense. The blue one is the distribution of
parameters learned by ASNI-I at $s\approx 80\%$. The green one is the
distribution of parameters for the learned sparse amenable network ($s\approx
80\%$) initialized by centroids obtained from ASNI-I.

###  5.4 Learning rate policy

Three learning rate policy are used for different experiments: 1) constant, 2)
cosine, 3) cosine with warm-up.

####  5.4.1 Constant learning rate

For those experiments that we use the Adam optimizer, the learning rate is
constant throughout the training.

####  5.4.2 Cosine policy learning rate

For cases where the SGD+M is used, the learning rate follows a cosine policy.
This cosine policy reduces the learning rate following a cosine function that
has three parameters, i.e., $\eta=\eta_{0}\cos(\pi e/(1+\delta)E)$ where
$\eta_{0}$ is the initial learning rate, $E$ is the total number of epochs,
and nonzero $\delta$ controls the final learning rate. Parameter $\delta$ is
set to 0.05 for VGG-style and ResNet-18 networks and it is set to 0.04 for
training ResNet-50. Only for training of ResNet-50 we use 10 epochs to warm up
the value of learning rate. For the warm-up case learning rate increases
linearly in 10 steps so that it reaches the highest value after the $10^{th}$
epoch. Then, it starts decaying following the above cosine function.

###  5.5 Parameters initialization

Network parameters are initialized according to the Kaiming Normal
distribution [17].

###  5.6 Deep network framework

For all experiments we use Pytorch [35] and its native automatic mixed
precision (AMP) library to boost the speed of training. Networks are trained
using NVIDIA TITAN X (Pascal) 12GB GPUs.

##  6 Results

Table 2:  This table shows hyper parameters for pruning, final sparsity, and
top-1 test accuracy of four variants. Accuracy percentages are the average of
5 experiments. (T1-D): dense network with zero sparsity, (T1-A-I): sparse
network learned by ASNI-I, (T1-A-II) the sparse amenable network initialized
by the quantized and compressed initialization learned by ASNI-II, (T1-S) the
sparse amenable network initialized by the original initialization.

Comb. | $\alpha$ | $\gamma$ | s% | Nonzeros | T1-D% | T1-A-I% | T1-A-II% | T1-S%
---|---|---|---|---|---|---|---|---
1 | 98 | 5 | 96.87 | 8,335 | 96.88 | 96.72 | 96.93 | 96.75
2 | 99.2 | 2 | 98.18 | 86,363 | 98.09 | 98.12 | 98.14 | 98.03
3 | 98.5 | 2 | 97.94 | 39,828 | 98.33 | 98.46 | 98.52 | 98.27
4 | 98.5 | 3 | 97.15 | 51,420 | 98.25 | 98.54 | 98.53 | 98.36
5 | 98.5 | 2 | 96.71 | 141,364 | 76.10 | 74.61 | 76.4 | 75.26
6 | 95 | 2 | 94.47 | 134,185 | 84.34 | 84 | 83.76 | 83.24
7 | 94 | 3 | 92.72 | 164,624 | 86.69 | 86.1 | 85.72 | 85.55
8 | 97 | 16 | 96.14 | 356,230 | 92.40 | 91.51 | 91.18 | 89.94
9 | 98 | 16 | 97.14 | 269,221 | 94.23 | 92.98 | 92.29 | 91.67
10 | 99 | 16 | 98.15 | 272,626 | 93.90 | 93.45 | 92.13 | 91.94
11 | 97 | 16 | 96.14 | 451,216 | 90.11 | 88.93 | 88.52 | 87.95
12 | 81.04 | 10 | 80.12 | 5,080,737 | 76.08 | 75.23 | 75.17 | 70.91
12 | 91.05 | 10 | 90.08 | 2,535,257 | 76.08 | 74.28 | 73.97 | 68.41

In this section we will go over different aspects of our experiments like test
accuracy, network- and layer-wise distributions of the sparse network learned
by ASNI-I, and compare ASNI-I and learned initialization by ASNI-II with their
counterparts.

###  6.1 The overall network parameters distribution

Figure 5:  Layer-wise sparsity after training a ResNet-50 network. The network
has 4 main stages where stages have 3, 4, 6, and 3 bottlenecks respectively.
The stages are color-coded with blue (2-11), red (12-24), green (25-43), and
pink (44-53). Black bars are sparsity percentage of the first convolution
layer (not in stages) and the fully connected layer at the end. The first
convolution layer in each stage located in the first bottleneck of that stage
is hatched with lines. Skip connections of each stage is hatched with stars.
The least sparsity occurs at the last layer (54) which is a fully connected
one. Also, first convolution layers (2, 12, 25, 44) in the first bottleneck of
each stage are the ones with the smallest sparsity compared to other
convolutional layers in stages.

The ASNI-I algorithm uses a global threshold that considers the magnitude of
every parameter across the network. Therefore, it makes sense to look at the
distribution of all parameters at once and not in layer-wise fashion. Fig. 4
shows the network distribution for ResNet-50 trained on ImageNet-1K. As Fig. 4
shows, initial parameters (orange distribution) have the largest variance. On
the other hand, distribution of the learned parameters of a dense network (red
distribution) has the smallest variance among all four distributions.
Distribution of parameters learned by ASNI-I (blue one) includes two normal-
like distributions where small values (in the absolute value sense) have been
discarded. Ignoring small values is what ASNI-I forces but observing two
normal-like distribution is surprising. The more surprising phenomenon is the
parameter distribution of the amenable sparse network initialized by ASNI-II
(green one). This distribution covers the distribution of parameters learned
by ASNI-I and fills the gap between them. This means that the learned sparse
amenable structure initialized by centroids is also able to learn the learned
parameters by ASNI-I because they have the same parameter distribution.
Compare to the layer distribution of parameters learned ASNI-I in Fig. 2, one
can observe that these normal-like distributions also exist for each layer.
That motivated us to use the averages of positive and negative values to
initialize the amenable sparse network.

###  6.2 Test accuracy

Tab. 2 shows hyper parameters for pruning and test accuracy corresponding to
four different variants. These four variants are: 1) dense network, a sparse
network learned by ASNI-I, the amenable sparse network initialized by the
initialization from ASNI-II, the amenable sparse network initialized by the
original initialization. There are two observations in Tab. 2. First, the
accuracy of the dense network is not always the highest and sometimes the
network learned by ASNI-I performs better even if it has far less parameters
than the dense one. Another observation is that networks initialized by the
original initialization cannot reach test accuracy of the dense network. They
also fall short of the accuracy of the sparse amenable network which is
initialized by the initialization learned by ASNI-II.

###  6.3 Layer-wise sparsity distribution

ASNI-I prunes parameters of the network to reach a predefined sparsity
percentage for the entire network. After reaching this sparsity value the
question is which layers have been pruned more and which layers are denser
than others. As ASNI-I does not enforce any limitations on the sparsity of
layers, each layer can be pruned differently. According to Fig. 5 layers are
pruned non-uniformly. Among all layers the last layer (black one) is the most
dense one with least pouring. The second most dense one is the very first
convolutional layer. Another interesting observation is that, the first
convolutional layer in the first bottleneck of each stage is the layer with
the least pruning. To observe that notice stages are color-coded with blue
(2-11), red (12-24), green (25-43), and pink (44-53) in Fig. 5.

###  6.4 ASNI performance vs its counterparts

The ASNI algorithm solves both tasks of pruning in Fig. 1 simultaneously. The
subalgorithm ASNI-I solves the first task and finds an off-the-shelf accurate
sparse network in one round for ResNet-50 trained on ImageNet-1k. We compare
ASNI-I with [45, 21, 5] in Tab. 3. These methods are the ones that try to
solve the first task in one round of pruning. For the second task of the
pruning we compare the accuracy of foresight pruning methods in [25, 42] and
methods that utilize magnitude pruning like [7, 9] for solving the first task
in one single round.

##  7 Conclusion and discussion

We proposed the ASNI algorithm that solves two tasks of pruning simultaneously
using two subalgorithms. To solve the first task ASNI-I learns an accurate
sparse network in one round. This learned sparse network is amenable because
it reaches the test accuracy of the dense network starting from quantized and
compressed initialization. The ASNI algorithm owes its success to a simple
pruning strategy which utilizes sigmoid function which manages the sparsity
budget throughout the training process. By choosing parameters of sigmoid
function properly, ASNI symmetrically reduces pruning at the beginning and end
of the pruning.

Table 3:  First task of pruning at $s\approx 80\%$ (comb. 12)

Method | Nonzeros | Top-1
---|---|---
Gradual Magnitude Pruning, [45] | 5,120,000 | 74.68
Soft Threshold Reparameterization, [21] | 5,120,000 | 74.87
Rigging the Lottery, [5] | 5,120,000 | 74.55
ASNI-I | 5,080,737 | 75.23

Table 4:  Second task of pruning at $s\approx 80\%$ (comb. 12)

Method | Nonzeros | Top-1
---|---|---
Iterative magnitude pruning, [7] | 5,120,000 | 73.33
Magnitude pruning after training, [9] | 5,120,000 | 75.12
Single-shot network pruning, [25] | 5,120,000 | 69.29
Gradient Signal Preservation, [42] | 5,120,000 | 71.56
Amenable Sparse network initialized by ASNI-II | 5,080,737 | 75.17

## References

  * [1] Achille, A., Rovere, M., and Soatto, S. Critical learning periods in deep networks.  In International Conference on Learning Representations (2018).
  * [2] Davis, G., and Mallat, S. Adaptive nonlinear approximations.  PhD thesis, New York University, Graduate School of Arts and Science, 1994\.
  * [3] Denil, M., Shakibi, B., Dinh, L., Ranzato, M., and De Freitas, N. Predicting parameters in deep learning.  In Advances in neural info. processing systems (2013), pp. 2148–2156.
  * [4] Dettmers, T., and Zettlemoyer, L. Sparse networks from scratch: Faster training without losing performance.  arXiv preprint arXiv:1907.04840 (2019).
  * [5] Evci, U., Gale, T., Menick, J., Castro, P. S., and Elsen, E. Rigging the lottery: Making all tickets winners.  In International Conference on Machine Learning (2020), PMLR, pp. 2943–2952.
  * [6] Frankle, J., and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks.  arXiv preprint arXiv:1803.03635 (2018).
  * [7] Frankle, J., Dziugaite, G. K., Roy, D., and Carbin, M. Linear mode connectivity and the lottery ticket hypothesis.  In International Conference on Machine Learning (2020), PMLR, pp. 3259–3269.
  * [8] Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Stabilizing the lottery ticket hypothesis.  arXiv preprint arXiv:1903.01611 (2019).
  * [9] Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Pruning neural networks at initialization: Why are we missing the mark?  arXiv preprint arXiv:2009.08576 (2020).
  * [10] Gale, T., Elsen, E., and Hooker, S. The state of sparsity in deep neural networks.  arXiv preprint arXiv:1902.09574 (2019).
  * [11] Ghadimi, S., and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  SIAM Journal on Optimization 23, 4 (2013), 2341–2368.
  * [12] Guo, Y., Yao, A., and Chen, Y. Dynamic network surgery for efficient dnns.  arXiv preprint arXiv:1608.04493 (2016).
  * [13] Han, S., Mao, H., and Dally, W. J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  arXiv preprint arXiv:1510.00149 (2015).
  * [14] Han, S., Pool, J., Tran, J., and Dally, W. Learning both weights and connections for efficient neural network.  In Advances in neural info. processing systems (2015), pp. 1135–1143.
  * [15] Hanson, S. J., and Pratt, L. Y. Comparing biases for minimal network construction with back-propagation.  In Advances in neural info. processing systems (1989), pp. 177–185.
  * [16] Hassibi, B., and Stork, D. G. Second order derivatives for network pruning: Optimal brain surgeon.  In Advances in neural information processing systems (1993), pp. 164–171.
  * [17] He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision (2015), pp. 1026–1034.
  * [18] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2016), pp. 770–778.
  * [19] Kingma, D. P., and Ba, J. Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980 (2014).
  * [20] Krizhevsky, A., Nair, V., and Hinton, G. Cifar-10 and cifar-100 datasets.  URl: https://www. cs. toronto. edu/kriz/cifar. html 6, 1 (2009), 1.
  * [21] Kusupati, A., Ramanujan, V., Somani, R., Wortsman, M., Jain, P., Kakade, S., and Farhadi, A. Soft threshold weight reparameterization for learnable sparsity.  arXiv preprint arXiv:2002.03231 (2020).
  * [22] LeCun, Y. The mnist database of handwritten digits.  http://yann. lecun. com/exdb/mnist/ (1998).
  * [23] LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition.  Proceedings of the IEEE 86, 11 (1998), 2278–2324.
  * [24] LeCun, Y., Denker, J. S., and Solla, S. A. Optimal brain damage.  In Advances in neural information processing systems (1990), pp. 598–605.
  * [25] Lee, N., Ajanthan, T., and Torr, P. H. Snip: Single-shot network pruning based on connection sensitivity.  arXiv preprint arXiv:1810.02340 (2018).
  * [26] Li, H., Kadav, A., Durdanovic, I., Samet, H., and Graf, H. P. Pruning filters for efficient convnets.  arXiv preprint arXiv:1608.08710 (2016).
  * [27] Liu, Z., Sun, M., Zhou, T., Huang, G., and Darrell, T. Rethinking the value of network pruning.  arXiv preprint arXiv:1810.05270 (2018).
  * [28] Louizos, C., Welling, M., and Kingma, D. P. Learning sparse neural networks through $l\\_0$ regularization.  arXiv preprint arXiv:1712.01312 (2017).
  * [29] Luo, J.-H., Wu, J., and Lin, W. Thinet: A filter level pruning method for deep neural network compression.  In Proceedings of the IEEE international conference on computer vision (2017), pp. 5058–5066.
  * [30] Mocanu, D. C., Mocanu, E., Stone, P., Nguyen, P. H., Gibescu, M., and Liotta, A. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science.  Nature communications 9, 1 (2018), 1–12.
  * [31] Molchanov, P., Tyree, S., Karras, T., Aila, T., and Kautz, J. Pruning convolutional neural networks for resource efficient inference.  arXiv preprint arXiv:1611.06440 (2016).
  * [32] Narang, S., Elsen, E., Diamos, G., and Sengupta, S. Exploring sparsity in recurrent neural networks.  arXiv preprint arXiv:1704.05119 (2017).
  * [33] Natarajan, B. K. Sparse approximate solutions to linear systems.  SIAM journal on computing 24, 2 (1995), 227–234.
  * [34] Nesterov, Y. E. A method for solving the convex programming problem with convergence rate o (1/k^ 2).  In Dokl. akad. nauk Sssr (1983), vol. 269, pp. 543–547.
  * [35] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library.  arXiv preprint arXiv:1912.01703 (2019).
  * [36] Robbins, H., and Monro, S. A stochastic approximation method.  The annals of mathematical statistics (1951), 400–407.
  * [37] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge.  International journal of computer vision 115, 3 (2015), 211–252.
  * [38] Savarese, P., Silva, H., and Maire, M. Winning the lottery with continuous sparsification.  arXiv preprint arXiv:1912.04427 (2019).
  * [39] Simonyan, K., and Zisserman, A. Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556 (2014).
  * [40] Tanaka, H., Kunin, D., Yamins, D. L., and Ganguli, S. Pruning neural networks without any data by iteratively conserving synaptic flow.  arXiv preprint arXiv:2006.05467 (2020).
  * [41] Tartaglione, E., Lepsøy, S., Fiandrotti, A., and Francini, G. Learning sparse neural networks via sensitivity-driven regularization.  arXiv preprint arXiv:1810.11764 (2018).
  * [42] Wang, C., Zhang, G., and Grosse, R. Picking winning tickets before training by preserving gradient flow.  arXiv preprint arXiv:2002.07376 (2020).
  * [43] Wen, W., Wu, C., Wang, Y., Chen, Y., and Li, H. Learning structured sparsity in deep neural networks.  arXiv preprint arXiv:1608.03665 (2016).
  * [44] You, H., Li, C., Xu, P., Fu, Y., Wang, Y., Chen, X., Baraniuk, R. G., Wang, Z., and Lin, Y. Drawing early-bird tickets: Towards more efficient training of deep networks.  arXiv preprint arXiv:1909.11957 (2019).
  * [45] Zhu, M., and Gupta, S. To prune, or not to prune: exploring the efficacy of pruning for model compression.  arXiv preprint arXiv:1710.01878 (2017).

Figure 6: Appendix: ResNet50-ImageNet-1KParameter: Distribution of each layer.
Figure 7: Appendix: ResNet50-ImageNet-1KParameter: Distribution of each layer.


# On the role of network structure in learning to coordinate with bounded
rationality

Yifei Zhang and Marcos M. Vasconcelos Y. Zhang and M. M. Vasconcelos are with
the Department of Electrical and Computer Engineering, FAMU-FSU College of
Engineering, Florida State University, Tallahassee, FL 32306, USA. E-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Many socioeconomic phenomena, such as technology adoption, collaborative
problem-solving, and content engagement, involve a collection of agents
coordinating to take a common action, aligning their decisions to maximize
their individual goals. We consider a model for networked interactions where
agents learn to coordinate their binary actions under a strict bound on their
rationality. We first prove that our model is a potential game and that the
optimal action profile is always to achieve perfect alignment at one of the
two possible actions, regardless of the network structure. Using a stochastic
learning algorithm known as Log Linear Learning, where agents have the same
finite rationality parameter, we show that the probability of agents
successfully agreeing on the correct decision is monotonically increasing in
the number of network links. Therefore, more connectivity improves the
accuracy of collective decision-making, as predicted by the phenomenon known
as “Wisdom of Crowds.” Finally, we show that for a fixed number of links, a
regular network maximizes the probability of success. We conclude that when
using a network of irrational agents, promoting more homogeneous connectivity
improves the accuracy of collective decision-making.

##  I Introduction

In many networked decision systems, multiple agents collaborate to accomplish
a possibly complex task impossible for any individual agent to fulfill. To
successfully perform the task without a centralized control station, the
agents need to interact with each other to determine whether they will engage
with a task presented to them. The interactive process leading to a collective
decision to act together can be understood as a learning to coordinate
algorithm [1]. In an ideal environment, such systems operate assuming the
agents are fully rational entities, such as networks of programmable devices
such as sensors or robots. However, in many applications where unbounded
rationality may not be realistic nor achievable – biologically inspired swarm
robotic systems and social-economic networks are prime examples of such
settings.

Our work is motivated by the role that connectivity plays when agents are
learning to coordinate over a network with bounded rationality. Network
coordination games [2] provide a structured framework to study distributed
coordination of strategic agents. It has been empirically demonstrated that
networks can affect a group’s ability to solve a coordination problem [3].
Using an analytical approach, [4] provided a mathematical foundation to
determine what types of networks facilitate the propagation of decisions a
network system of homogeneous agents, obtaining a characterization of the rate
of convergence as a function of the graph structure. The work in [5] obtained
an upper bound on the time for decisions to spread over a network of any size
and degree distribution, both directed or undirected. Using a Threshold Model,
[6] provided a recursive equation that approximates the propagation of
decisions over large networks of heterogeneous agents. Heterogeneity was also
studied in [7], where necessary and sufficient conditions where established to
ensure perfect coordination within a group of two different classes of agents.
Robustness in network coordination is the focus of [8], in which the agents
may be externally influenced by an external field creating a bias towards
certain actions. The resilience of strategic networked coordination systems to
cybersecurity attacks has been considered [9, 10, 11] and the role of local
connectivity in stochastic coordination games [12, and references therein] has
been studied in [13, 14, 15].

The focus of our work is in settings where the agents have bounded
rationality, and therefore make imperfect decisions. There is a growing
literature of models of bounded rationality, including prospect theory and
cognitive hierarchy theory [16, 17, 18, 19], to name a few. Bounded
rationality in the context of evolutionary game theory and coordination was
studied in [20]. We specifically consider bounded rationality in the context
of Log Linear Learning (LLL) [21], which implies that actions are chosen with
a certain degree of imprecision/randomness, which also propagates over the
network preventing coordination to be perfectly achieved, i.e., with
probability one. In our previous work [22], we have established that in the
bounded rationality regime of agents using LLL for coordination over regular
networks, there exists a nontrivial trade-off between rationality and
connectivity. Therefore, the network structure may affect, for instance,
whether the achieving coordination with high probability is possible or not.

In this paper, we extend the analysis in [22] to irregular graphs. We show
that coordination games defined over irregular graphs are exact potential
games, and that the probability of successfully learning the optimal Nash
equilibrium (the one corresponding to a maximizer of the potential function)
is monotone increasing in the number of edges in the graph. In other words,
our result shows that lack of rationality can be compensated by increasing the
connectivity in the network, akin to a phenomenon popularly known as “Wisdom
of Crowds” [23]. Our second contribution is to establish that, in the bounded
rationality regime, regular networks maximize the probability of successfully
learning the optimal equilibrium. Therefore, establishing the result that
equal access to connectivity resources improves coordination accuracy.

##  II Problem setup

We begin by defining the class of binary networked coordination games that
will be the focus of this paper. Let $[N]:=\\{1,2,\ldots,N\\}$ denote the set
of agents in the network described by an undirected and connected graph
$\mathcal{G}:=([N],\mathcal{E})$. Two nodes $i,j\in[N]$ are connected if
$(i,j)\in\mathcal{E}$. The set of neighbors of agent $i$ is denoted by
$\mathcal{N}_{i}:=\\{j\in[N]\mid(i,j)\in\mathcal{E}\\}$. The number of
neighbors of agent $i$ is denoted by $|\mathcal{N}_{i}|$. We assume there are
no self loops, i.e., $(i,i)\notin\mathcal{E},$ $i\in[N]$.

###  II-A Two-agent binary coordination games

Let $(i,j)\in\mathcal{E}$, and suppose that $a_{i},a_{j}\in\\{0,1\\}$ are the
actions played by agents $i$ and $j$, respectively. For $\theta\in\mathbb{R}$,
the following bimatrix game specifies the payoffs for the pairwise interaction
between $i$ and $j$.

22[$a_{i}$][$a_{j}$] & $1$ $0$
$1$ $\Big{(}1-\frac{\theta}{N},1-\frac{\theta}{N}\Big{)}$
$\Big{(}-\frac{\theta}{N},0\Big{)}$
$0$ $\Big{(}0,-\frac{\theta}{N}\Big{)}$ $\Big{(}0,0\Big{)}$

Figure 1: A coordination game with parameter $\theta$ between two players.

######  Remark 1 (Payoff interpretation)

The payoff structure of the bimatrix game in Fig. 1 corresponds to a
coordination game between two agents. Notice the payoff matrix depends on a
parameter $\theta\in\mathbb{R}$, which we refer to as a task difficulty. The
difficulty is amortized over the total number of agents in the system, $N$.
Each agent works on a subtask of difficulty $\theta/N$. We are modeling
collaboration, therefore, when agent $i$ decides to take on a subtask, it
contributes $1$ unit of effort towards its own subtask and the subtasks of its
neighbors.

A binary coordination game between two players is characterized by the
existence of exactly two pure strategy Nash equilibria: $(0,0)$ and $(1,1)$.
The following result establishes the range of values of $\theta$ for which the
game in Fig. 1 corresponds to a coordination game.

###### Proposition 1

Consider the bimatrix game in Fig. 1, and $\mathcal{S}$ denote its set of
pure-strategy Nash equilibria. The following holds:

$\mathcal{S}=\begin{cases}\big{\\{}(0,0)\big{\\}}&\text{if}\ \ \theta>N\\\
\big{\\{}(0,0),(1,1)\big{\\}}&\text{if}\ \ 0\leq\theta\leq N\\\
\big{\\{}(1,1)\big{\\}}&\text{if}\ \ \theta\leq 0.\end{cases}$ (1)

###### Proof:

The proof can be obtained by inspection using the definition of a Nash
equilibrium [24]. ∎

Therefore, the range of values of task difficulty that we are interested in
analyzing is $\theta\in[0,N]$.

###  II-B Coordination games over networks

Extending the two-agent coordination game from Fig. 1 over a network, we
obtain the following network game with $N$ agents, where agent $i$
simultaneously plays the same action with all of its neighbors
$j\in\mathcal{N}_{i}$. Let $V_{ij}:\\{0,1\\}^{2}\rightarrow\mathbb{R}$ be
defined as:

$V_{ij}(a_{i},a_{j}):=a_{i}\Big{(}a_{j}-\frac{\theta}{N}\Big{)}.$ (2)

In a network coordination game, every agent receives the sum of all the
payoffs of the bimatrix games $V_{ij}(a_{i},a_{j})$ played with each of its
neighbors. Therefore for the $i$-th agent, the utility is determined as
follows:

$U_{i}(a_{i},a_{-i}):=\sum\limits_{j\in\mathcal{N}_{i}}V_{ij}(a_{i},a_{j}).$
(3)

Therefore, the payoff of the $i$-th agent in our game is

$U_{i}(a_{i},a_{-i})=a_{i}\Big{(}\sum_{j\in\mathcal{N}_{i}}a_{j}-\frac{|\mathcal{N}_{i}|}{N}\theta\Big{)}.$
(4)

Notice that the payoff in Eq. 4 reflects that more connected nodes face a
larger difficulty due to the collaboration with other agents in the network.
However, the effort is also aggregated, which leads to a potentially higher
utility.

##  III Potential Network Games

The class of potential games (PG) play an instrumental role in our analysis
[25]. PGs enjoy two desirable properties: 1. Every finite PG always admits a
Nash equilibrium (NE) in pure strategies; 2. If the agents adhere to LLL on a
potential network game, they are is guaranteed to converge to a NE in the
limit when their rationality goes to infinity [21]. We will first show that
the network game defined by Eq. 4 is an exact potential game. To proceed with
our analysis, we must first define this important class of games.

######  Definition 1 (Exact potential games)

Let $\mathcal{A}_{i}$ denote the action set of the $i$-th agent in a game with
payoff functions $U_{i}(a_{i},a_{-i})$, $i\in[N]$. Let
$\mathcal{A}=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}$. A game is an
exact potential game if there is a so-called potential function $\Phi$:
$\mathcal{A}\rightarrow\mathbb{R}$ such that

$U_{i}(a^{\prime}_{i},a_{-i})-U_{i}(a^{\prime\prime}_{i},a_{-i})=\Phi(a^{\prime}_{i},a_{-i})-\Phi(a^{\prime\prime}_{i},a_{-i}),$
(5)

for all $a_{i}^{\prime},a_{i}^{\prime\prime}\in\mathcal{A}_{i}$,
$a_{-i}\in\mathcal{A}_{-i}$, $i\in[N]$.

We proceed by showing that the game defined by Eq. 4 is a PG. We start our
analysis by restating a classical result by Monderer and Shapley [25, Theorem
4.5].

######  Lemma 1 (Monderer and Shapley)

Let $\Gamma$ be a game in which the strategy sets are intervals of real
numbers. Suppose the payoff functions are twice continuously differentiable.
Then $\Gamma$ is a potential game if and only if

$\frac{\partial^{2}(U_{i}-U_{j})}{\partial a_{i}\partial a_{j}}=0$ (6)

for every $i$,$j$ $\in[N]$.

###### Proposition 2

The network game defined by Eq. 4 on any connected undirected graph
$\mathcal{G}$ is potential. Let the adjacency matrix of $\mathcal{G}$ be
denoted by $\mathbf{A}$. The potential function of the network coordination
game is given by

$\Phi(a)=\frac{1}{2}a^{\mathsf{T}}\mathbf{A}a-\frac{\theta}{N}a^{\mathsf{T}}\mathbf{A}\mathbb{1}.$
(7)

###### Proof:

Relaxing $a_{i}\in\mathbb{R}$ for all $i\in[N]$, then the payoff function Eq.
5 is twice differentiable. If the continuous game is potential, then it
necessarily implies that the original game is potential, since we can define
the potential values on the vertices of the unit lattice in $\mathbb{R}^{N}$,
and assign those as the potential values of the original game. Plugging Eq. 5
into Eq. 6, we have:

$\frac{\partial^{2}(U_{i}-U_{j})}{\partial a_{i}\partial
a_{j}}=\mathbf{1}(i\in\mathcal{N}_{j})-\mathbf{1}(j\in\mathcal{N}_{i})$ (8)

where $\mathbf{1}(\mathfrak{S})$ is the indicator function of statement
$\mathfrak{S}$. Since $\mathcal{G}$ is undirected, then
$i\in\mathcal{N}_{j}\Leftrightarrow j\in\mathcal{N}_{i}$. Therefore,

$\mathbf{1}(i\in\mathcal{N}_{j})=\mathbf{1}(j\in\mathcal{N}_{i}),$ (9)

and Lemma 1 implies that the networked game is potential.

To obtain a potential function for our network game, define the following
function:

$\phi_{ij}(a_{i},a_{j}):=a_{i}a_{j}+(1-a_{i}-a_{j})\frac{\theta}{N}.$ (10)

The function $\phi_{ij}$ is a potential function for the two-agent
coordination game in Fig. 1, i.e.,

$\phi_{ij}(1,a_{j})-\phi_{ij}(0,a_{j})=V_{ij}(1,a_{j})-V_{ij}(0,a_{j}),$ (11)

for all $i,j\in[N]$ and $a_{j}\in\\{0,1\\}$. Let
$\Phi:\\{0,1\\}^{N}\rightarrow\mathbb{R}$ as follows:

$\tilde{\Phi}(a):=\frac{1}{2}\sum\limits_{i\in[N]}\sum\limits_{j\in\mathcal{N}_{i}}\phi_{ij}(a_{i},a_{j}).$
(12)

Plugging Eq. 10 into Eq. 12 and using the fact that the network is undirected,
we get:

$\tilde{\Phi}(a)=\underbrace{\frac{1}{2}a^{\mathsf{T}}\mathbf{A}a-\frac{\theta}{N}a^{\mathsf{T}}\mathbf{A}\mathbb{1}}_{:=\Phi(a)}+\frac{\theta}{2N}\mathbb{1}^{\mathsf{T}}\mathbf{A}\mathbb{1}.$
(13)

Since the last term in Eq. 13 is independent of $a$, we may disregard it.
Thus, obtaining Eq. 7.

∎

##  IV Network Coordination Games

Starting from a two-player binary coordination game, we obtained a network
game by extending it over a graph, and we showed that it is always potential.
In this section, we establish that our network game has the coordination
property, i.e., there are only two NE in pure strategies:
$\mathcal{S}=\\{\mathbb{0},\mathbb{1}\\}$. We proceed by analyzing the
potential function in Eq. 7.

###### Theorem 1

For all action profiles $a$ in the action space $\mathcal{A}:=\\{0,1\\}^{N}$,
the potential function $\Phi(a)$ attains its maximum at either
$a^{\star}=\mathbb{1}$ or $a^{\star}=\mathbb{0}$, regardless of the graph
structure.

###### Proof:

We use the following notation to split an action profile $a$ into three parts:
$a=(a_{i},a_{\mathcal{N}_{i}},a_{-i\backslash\mathcal{N}_{i}})$, where
$a_{i}\in\\{0,1\\}$ is the action of $i$-th agent,
$a_{\mathcal{N}_{i}}\in\\{0,1\\}^{|\mathcal{N}_{i}|}$ is the action vector of
$i$-th agent’s neighbors and
$a_{-i\backslash\mathcal{N}_{i}}\in\\{0,1\\}^{N-1-|\mathcal{N}_{i}|}$ is the
action vector of the remaining agents. Consider the following optimization
problem:

$\displaystyle\underset{a}{\mathrm{maximize}}$ $\displaystyle
f_{i}(a):=a_{i}\Big{(}\sum_{j\in\mathcal{N}_{i}}\frac{1}{2}a_{j}-\frac{|\mathcal{N}_{i}|}{N}\theta\Big{)}$
(14) subject to $\displaystyle a\in\mathcal{A}.$

Note that $f_{i}$ is a bilinear function of $a_{i}$ and $a_{\mathcal{N}_{i}}$.
Therefore, Problem (LABEL:f_i) always takes its maximizer in the set
$F_{0}^{i}:=\\{a\in\mathcal{A}\mid a_{i}=0\\}$ or the set
$F_{1}^{i}:=\\{a\in\mathcal{A}\mid
a_{i}=1,a_{\mathcal{N}_{i}}=\mathbb{1}_{|\mathcal{N}_{i}|}\\}$. More
precisely, we have:

  * •

Case 1: If $\theta>\frac{1}{2}N$, then for all $a\in F_{0}^{i}$, the objective
function $f_{i}(a)$ attains the maximum value of $0$.

  * •

Case 2: If $\theta<\frac{1}{2}N$, then for all $a\in F_{1}^{i}$, the objective
function $f_{i}(a)$ attains the maximum value of
$(\frac{1}{2}-\frac{\theta}{N})|\mathcal{N}_{i}|$.

  * •

Case 3: If $\theta=\frac{1}{2}N$, then for all $a\in F_{0}^{i}\cup F_{1}^{i}$,
$f_{i}(a)$ attains the maximum value of
$(\frac{1}{2}-\frac{\theta}{N})|\mathcal{N}_{i}|=0$.

For every index $i\in[N]$, the case-by-case analysis above is valid. Notice
that the optimality analysis of $f_{i}$ is independent of the graph structure.
Now, we consider the following:

$\displaystyle\underset{a}{\mathrm{maximize}}$
$\displaystyle\sum\limits_{i=1}^{N}f_{i}(a)=\frac{1}{2}a^{\mathsf{T}}\mathbf{A}a-\frac{\theta}{N}a^{\mathsf{T}}\mathbf{A}\mathbb{1}$
(15) subject to $\displaystyle a\in\mathcal{A}.$

The objective function in Eq. 15 is precisely $\Phi(a)$. As it is a finite sum
of local objective functions, which share the same optimality condition, the
optimizer of $\Phi$ should lie in the intersection of the individual optimal
sets (if the intersection is nonempty).

  * •

Case 1: If $\theta>\frac{1}{2}N$, then for all
$a\in\bigcap_{i=1}^{N}F_{0}^{i}$, the objective function $\Phi(a)$ attains the
maximum value of $0$. There is only one element in
$\bigcap_{i=1}^{N}F_{0}^{i}$, which is $\mathbb{0}$.

  * •

Case 2: If $\theta<\frac{1}{2}N$, then for all
$a\in\bigcap_{i=1}^{N}F_{1}^{i}$, the objective function $\Phi(a)$ attains the
maximum value of
$(\frac{1}{2}-\frac{\theta}{N})\mathbb{1}^{\mathsf{T}}\mathbf{A}\mathbb{1}$.
Since the graph is connected, $[N]\subseteq\bigcup_{i=1}^{N}\mathcal{N}_{i}$,
there is only one element in $\bigcap_{i=1}^{N}F_{1}^{i}$, which is
$\mathbb{1}$.

  * •

Case 3: If $\theta=\frac{1}{2}N$, then for all
$a\in\bigcap_{i=1}^{N}F_{0}^{i}\cup F_{1}^{i}$, the objective function
$\Phi(a)$ attains the maximum value of
$(\frac{1}{2}-\frac{\theta}{N})\mathbb{1}^{\mathsf{T}}\mathbf{A}\mathbb{1}=0$.
There are two elements in $\bigcap_{i=1}^{N}F_{0}^{i}\cup F_{1}^{i}$, which
are $\mathbb{1}$ and $\mathbb{0}$.

In conclusion, $\Phi(a)$ attains its maximum at either $a^{\star}=\mathbb{1}$
or $a^{\star}=\mathbb{0}$. Any action profile that contains both 1’s and 0’s
can never be optimal. ∎

The game defined by Eq. 4 is indeed a network coordination game, regardless of
the graph structure. Moreover, there is a threshold on the task difficulty
$\theta^{\mathrm{th}}$, which determines whether $a^{\star}=\mathbb{0}$ or
$a^{\star}=\mathbb{1}$, given by:

$\theta^{\mathrm{th}}=\frac{N}{2}.$ (16)

Although the graph structure does not play a role in the coordination
property, it does affect the properties of the stochastic learning process
applied to this game. In the next section, we show how the graph structure
influences the probability of all of the agents successfully playing the
optimal NE, $a^{\star}$, using LLL with bounded rationality.

##  V Learning to Coordinate over a Network

###  V-A Log Linear Learning

We assume that every agent in the network uses a learning algorithm known as
Log Linear Learning [21]. LLL is a widely used learning algorithm where each
agent updates its action at time $t$ based on its payoff given the actions
played by its neighbors at time $t-1$. At each time step $t>0$, one agent
$i\in[N]$ is chosen uniformly at random, and allowed to update its current
action. All other agents repeat the action taken at the previous time-step.
The probability that agent $i$ chooses action $a_{i}\in\\{0,1\\}$ is
determined as follows:

$\mathbb{P}\big{(}A_{i}(t)=a_{i}\big{)}=\frac{e^{\beta
U_{i}\big{(}a_{i},a_{-i}(t-1)\big{)}}}{\sum_{a^{\prime}_{i}\in\mathcal{A}_{i}}e^{\beta
U_{i}\big{(}a^{\prime}_{i},a_{-i}(t-1)\big{)}}},\ a_{i}\in\mathcal{A}_{i},$
(17)

where the parameter $\beta\geq 0$ captures the rationality of the agents. When
$\beta\rightarrow 0$, the agents select their actions uniformly at random,
whereas, when $\beta\rightarrow\infty$, the agents update their actions using
a best response policy to their neighbors actions. If the game is an exact
potential game, then the Markov chain induced by LLL has a unique stationary
distribution $\mu:\\{0,1\\}^{N}\rightarrow[0,1]$ given by

$\mu_{\mathcal{G}}(a\mid\beta):=\frac{e^{\beta\Phi(a)}}{\sum_{a^{\prime}\in\\{0,1\\}^{N}}e^{\beta\Phi(a^{\prime})}},$
(18)

where $\Phi:\\{0,1\\}^{N}\rightarrow\mathbb{R}$ is the game’s potential
function. The stationary distribution gives the probability of the agents
playing a certain action profile in the long run, when $t\rightarrow\infty.$
We say that the agents have successfully learned the optimal action profile
$a^{\star}$ if

$\lim_{\beta\rightarrow\infty}\mu(a^{\star}\mid\beta)=1.$ (19)

However, for $\beta<\infty$, the probability $\mu(a^{\star}\mid\beta)<1$. In
the next section, we investigate if the stationary probability of successful
learning can be improved without changing the rationality of the agents, but
by augmenting the connectivity of the network instead.

###  V-B Inductive improvement by increasing connectivity

The simplest metric of network connectivity is the number of edges in the
graph used to describe it. In fact, as shown in the next theorem, the steady
state probability of LLL learning to play the optimal action profile increases
as the number of edges in a graph increases.

###### Theorem 2

Consider an undirected connected graph $\mathcal{G}$, and denote by
$\mathcal{G}_{s}$ an augmented graph of $\mathcal{G}$ such that

$\mathcal{G}=([N],\mathcal{E})\hskip 5.0pt\text{and}\hskip
5.0pt\mathcal{G}_{s}=\big{(}[N],\mathcal{E}\cup(i,j)\big{)}$ (20)

where agents $i$ and $j$ are not connected in $\mathcal{G}$, i.e.,
$(i,j)\notin\mathcal{E}$. For the network coordination game defined by Eq. 4,
the probability of success using LLL is strictly larger on $\mathcal{G}_{s}$
than on $\mathcal{G}$ for the same rationality level $\beta$, i.e.,

$\mu_{\mathcal{G}_{s}}(a^{\star}\mid\beta)>\mu_{\mathcal{G}}(a^{\star}\mid\beta).$
(21)

###### Proof:

Let $\mathbf{A}$ and $\mathbf{A}_{s}$ denote the adjacency matrices of
$\mathcal{G}$ and $\mathcal{G}_{s}$, respectively. Let $\Phi_{s}(a)$ denote
the potential function of the action profile $a$, when the underlying graph
has adjacency matrix $\mathbf{A}_{s}$. We have:

$\mathbf{A}_{s}-\mathbf{A}=\mathbb{e}_{i}\mathbb{e}_{j}^{\mathsf{T}},$ (22)

where $\mathbb{e}_{i}$ and $\mathbb{e}_{j}$ are the $i$-th and the $j$-th
canonical basis vector in $\mathbb{R}^{N}$. We will prove the result for the
case $\theta<N/2$, $a^{\star}=\mathbb{1}$.

Assuming $\theta<N/2$, Theorem 1 guarantees that $a^{\star}=\mathbb{1}$, for
any graph. However, for $a^{\star}=\mathbb{1}$, the values of the potential
function for $\mathcal{G}_{s}$ and $\mathcal{G}$ satisfy:

$\Phi_{s}(a^{\star})-\Phi(a^{\star})=\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}\mathbb{1}^{\mathsf{T}}(e_{i}e_{j}^{\mathsf{T}})\mathbb{1}=\frac{1}{2}-\frac{\theta}{N}.$
(23)

For all $a\in\mathcal{A}$, the following holds:

$\Phi_{s}(a)-\Phi(a)=\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}a_{i}a_{j}.$
(24)

Therefore, for all $a\in\mathcal{A}\backslash\\{a\in\mathcal{A}\mid
a_{i}=a_{j}=1\\}$, we have:

$\Phi_{s}(a)=\Phi(a).$ (25)

Notice that the cardinality of the set
$\mathcal{A}\backslash\\{a\in\mathcal{A}\mid a_{i}=a_{j}=1\\}$ is $3\cdot
2^{N-2}$, and therefore, it is never empty.

Now, consider the following equation:

$\displaystyle\mu_{\mathcal{G}}(a^{\star}\mid\beta)$
$\displaystyle=\frac{e^{\beta\Phi(a^{\star})}}{\sum_{a\in\mathcal{A}}e^{\beta\Phi(a)}}.$
(26)

Then, using Eq. 23, we have:

$\displaystyle\mu_{\mathcal{G}}(a^{\star}\mid\beta)$
$\displaystyle=\frac{e^{\beta\Phi(a^{\star})}e^{\beta(\frac{1}{2}-\frac{\theta}{N})}}{\sum_{a\in\mathcal{A}}e^{\beta\Phi(a)}e^{\beta(\frac{1}{2}-\frac{\theta}{N})}}$
(27)
$\displaystyle=\frac{e^{\beta\Phi_{s}(a^{\star})}}{\sum_{a\in\mathcal{A}}e^{\beta\big{(}\Phi(a)+(\frac{1}{2}-\frac{\theta}{N})\big{)}}}.$

Denote the denominator in Eq. 27 by $(*)$. The following holds:

$\displaystyle(*)$ $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}}e^{\beta\big{(}\Phi(a)+(\frac{1}{2}-\frac{\theta}{N})\big{)}}$
(29) $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}\backslash\\{a\in\mathcal{A}\mid
a_{i}=a_{j}=1\\}}e^{\beta\big{(}\Phi(a)+(\frac{1}{2}-\frac{\theta}{N})\big{)}}$
$\displaystyle\qquad+\sum_{a\in\\{a\in\mathcal{A}\mid
a_{i}=a_{j}=1\\}}e^{\beta\big{(}\Phi(a)+(\frac{1}{2}-\frac{\theta}{N})\big{)}}.$

From Eq. 24, we have:

$(*)=\sum_{a\in\mathcal{A}\backslash\\{a\in\mathcal{A}\mid
a_{i}=a_{j}=1\\}}e^{\beta\big{(}\Phi_{s}(a)+(\frac{1}{2}-\frac{\theta}{N})\big{)}}\\\
\qquad+\sum_{a\in\\{a\in\mathcal{A}\mid
a_{i}=a_{j}=1\\}}e^{\beta\Phi_{s}(a)}.$ (30)

Finally, since $\theta<N/2$, we have:

$\Phi_{s}(a)+\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}>\Phi_{s}(a).$ (31)

Because $e^{x}$ is strictly increasing and
$\mathcal{A}\backslash\\{a\in\mathcal{A}\mid a_{i}=a_{j}=1\\}$ is nonempty, we
have:

$(*)>\sum_{a\in\mathcal{A}}e^{\beta\Phi_{s}(a)}.$ (32)

Therefore,

$\mu_{\mathcal{G}}(a^{\star}\mid\beta)<\frac{e^{\beta\Phi_{s}(a^{\star})}}{\sum_{a\in\mathcal{A}}e^{\beta\Phi_{s}(a)}}=\mu_{\mathcal{G}_{s}}(a^{\star}\mid\beta).$
(33)

The proof for the other case, $\theta\geq\frac{1}{2}N$, is analogous and thus
it is omitted here due to space constraints.

∎

The main implication of Theorem 2 is that we can improve the probability of
agents with bounded rationality to successfully learn to coordinate on the
optimal NE by increasing the connectivity of the network.

In [22, Theorem 3], it was established that for every connected $\mathcal{G}$,
the probability of successful learning is monotone increasing in the
rationality parameter, i.e.,

$\frac{\partial\mu_{\mathcal{G}}}{\partial\beta}(a^{\star}\mid\beta)>0.$ (34)

Since we are interested in the bounded rationality regime, for every graph
$\mathcal{G}$ there exists a minimum level of rationality that the agents must
have to guarantee a high enough probability of successful learning. We define
the following quantity:

$\beta_{\mathcal{G}}^{\min}(\delta)\operatorname{\overset{def}{=}}\min\Big{\\{}\beta\mid\mu_{\mathcal{G}}(a^{\star}\mid\beta)\geq
1-\delta\Big{\\}},$ (35)

where $\delta\in(0,1)$.

From a designer’s perspective, we are interested in choosing a network that
allows the agents to behave as irrationally as possible as long as they
converge to the optimal NE with high probability.

###  V-C Optimality of regular graphs

In this section, we will answer the following question: Assuming that the
agents adhere to updating their strategies according to LLL, for a given
$\delta$ and a fixed number of edges $|\mathcal{E}|$, find the graph
$\mathcal{G}$ that minimizes $\beta_{\mathcal{G}}^{\min}(\delta)$. We will
prove that the class of regular graphs trades-off connectivity for rationality
most effectively.

A regular graph is one where every node has the same number of neighbors. This
is a special class of graphs, which possess interesting robustness properties
in a variety of settings [26]. Figure 2 shows an irregular and a regular graph
with the same number of nodes and edges.

Consider two graphs with the same edge connectivity:
$\mathcal{G}_{R}\operatorname{\overset{def}{=}}([N],\mathcal{E}_{R})$ and
$\mathcal{G}_{I}\operatorname{\overset{def}{=}}([N],\mathcal{E}_{I})$, where
$|\mathcal{E}_{R}|=|\mathcal{E}_{I}|$. The subscript $R$ stands for regular
and the subscript $I$ stands for irregular. We use other notations in the same
manner. For instance, $\Phi_{R}(a)$ denotes the potential value of an action
profile $a$ on a regular graph and $\Phi_{I}(a)$ denotes the potential value
of an action profile $a$ on an irregular graph.

The following lemma states that for our network coordination games, the total
potential is invariant on graphs with the same number of nodes and edges.

###### Lemma 2

Let $\mathcal{G}_{R}=([N],\mathcal{E}_{R})$ and
$\mathcal{G}_{I}=([N],\mathcal{E}_{I})$, correspond to a regular and an
irregular graph, respectively. Consider the networked coordination game
determined by Eq. 4. If $|\mathcal{E}_{R}|=|\mathcal{E}_{I}|$, then

$\sum\limits_{a\in\mathcal{A}}\Phi_{R}(a)=\sum\limits_{a\in\mathcal{A}}\Phi_{I}(a).$
(36)

###### Proof:

Consider the map $\rho:\mathcal{A}\to\mathcal{A}$ defined as
$\rho(a)\operatorname{\overset{def}{=}}\mathbb{1}-a$. Since $\rho(\cdot)$ is a
one-to-one correspondence on $\mathcal{A}$, we have:

$\sum\limits_{a\in\mathcal{A}}\Phi(a)+\sum\limits_{a\in\mathcal{A}}\Phi\big{(}\rho(a)\big{)}=2\sum\limits_{a\in\mathcal{A}}\Phi(a).$
(37)

The following identity holds:

$\displaystyle\Phi(a)+\Phi\big{(}\rho(a)\big{)}$
$\displaystyle=\frac{1}{2}a^{\mathsf{T}}\mathbf{A}a-\frac{\theta}{N}a^{\mathsf{T}}\mathbf{A}\mathbb{1}$
(38) $\displaystyle\ \
+\frac{1}{2}(\mathbb{1}-a)^{\mathsf{T}}\mathbf{A}(\mathbb{1}-a)-\frac{\theta}{N}(\mathbb{1}-a)^{\mathsf{T}}\mathbf{A}\mathbb{1}$
$\displaystyle=\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}\mathbb{1}^{\mathsf{T}}\mathbf{A}\mathbb{1}+a^{\mathsf{T}}\mathbf{A}(a-\mathbb{1}).$

Denote the degree matrix of the associated graph by $\mathbf{D}$. We have
$\mathbf{D}=\mathrm{diag}(\mathbf{A}\mathbb{1})$. Observe that for any
diagonal matrix $\mathbf{H}$, we have:
$a^{\mathsf{T}}\mathbf{H}(a-\mathbb{1})=0$. Equation 38 becomes:

$\displaystyle\Phi(a)+\Phi\big{(}\rho(a)\big{)}$ $\displaystyle=$
$\displaystyle\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}\mathbb{1}^{\mathsf{T}}\mathbf{A}\mathbb{1}+a^{\mathsf{T}}\mathbf{A}(a-\mathbb{1})$
(39) $\displaystyle=$ $\displaystyle
2\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}|\mathcal{E}|+a^{\mathsf{T}}(\mathbf{A}-\mathbf{D})(a-\mathbb{1})$
$\displaystyle=$ $\displaystyle
2\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}|\mathcal{E}|+a^{\mathsf{T}}\mathbf{L}(a-\mathbb{1})$
$\displaystyle=$ $\displaystyle
2\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}|\mathcal{E}|-a^{\mathsf{T}}\mathbf{L}a,$

where $\mathbf{L}$ is the graph Laplacian matrix defined by
$\mathbf{L}\operatorname{\overset{def}{=}}\mathbf{D}-\mathbf{A}$. Note that in
the last step to derive Eq. (39), we used the fact that
$\mathbb{1}\in\mathrm{ker}(\mathbf{L})$ for any undirected unweighted graph.

Equation (39) implies that for any graph with $|\mathcal{E}|$ edges, we have:

$\sum\limits_{a\in\mathcal{A}}\Phi(a)=2^{N}\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}|\mathcal{E}|-\frac{1}{2}\sum\limits_{a\in\mathcal{A}}a^{\mathsf{T}}\mathbf{L}a.$
(40)

We proceed to show that

$\sum\limits_{a\in\mathcal{A}}a^{\mathsf{T}}\mathbf{L}a=2^{N-1}|\mathcal{E}|.$
(41)

To that end, we will use a probabilistic technique. Consider a sequence of $N$
i.i.d. Bernoulli random variables $X_{1}$, …, $X_{N}$, where each $X_{i}$ is
distributed according to
$\mathbb{P}(X_{i}=1)=\mathbb{P}(X_{i}=0)=\frac{1}{2}$. Consider the random
vector $X\operatorname{\overset{def}{=}}(X_{1},\dots,X_{N})^{\mathsf{T}}$. We
have:

$\mathbb{E}[X]=\mathbf{m}=\frac{1}{2}\mathbb{1}\hskip 5.0pt\text{and}\hskip
5.0pt\mathrm{Var}[X]=\Sigma=\frac{1}{4}\mathbf{I}.$ (42)

The random vector $X$ is uniformly distributed on the action space
$\mathcal{A}$ with probability $\frac{1}{2^{N}}$. Consider the expectation of
the following quadratic form:

$\displaystyle\mathbf{E}[X^{\mathsf{T}}\mathbf{L}X]$
$\displaystyle=\mathrm{trace}\big{(}\mathbf{L}\cdot\mathbf{E}[XX^{\mathsf{T}}]\big{)}$
(43)
$\displaystyle=\mathrm{trace}\big{(}\mathbf{L}\cdot(\Sigma+\mathbf{m}\mathbf{m}^{\mathsf{T}})\big{)}$
$\displaystyle=\mathrm{trace}(\mathbf{L}\Sigma)+\mathbf{m}^{\mathsf{T}}\mathbf{L}\mathbf{m}.$

Since $\mathbf{m}=\frac{1}{2}\mathbb{1}\in\mathrm{ker}(\mathbf{L})$, we have
$\mathbf{m}^{\mathsf{T}}\mathbf{L}\mathbf{m}=0$ and

$\mathrm{trace}(\mathbf{L}\Sigma)=\frac{1}{4}\mathrm{trace}(\mathbf{L})=\frac{1}{2}|\mathcal{E}|.$
(44)

Thus,

$\mathbf{E}[X^{\mathsf{T}}\mathbf{L}X]=\frac{1}{2}|\mathcal{E}|.$ (45)

On the other hand,

$\mathbf{E}[X^{\mathsf{T}}\mathbf{L}X]=\sum\limits_{a\in\mathcal{A}}a^{\mathsf{T}}\mathbf{L}a\cdot\mathbb{P}(X=a)=\frac{1}{2^{N}}\sum\limits_{a\in\mathcal{A}}a^{\mathsf{T}}\mathbf{L}a,$
(46)

which implies that:

$\sum\limits_{a\in\mathcal{A}}a^{\mathsf{T}}\mathbf{L}a=2^{N-1}|\mathcal{E}|.$
(47)

Plugging Eq. 47 back into Eq. 40, we get:

$\sum\limits_{a\in\mathcal{A}}\Phi(a)=\Big{(}\frac{1}{4}-\frac{\theta}{N}\Big{)}2^{N}|\mathcal{E}|.$
(48)

Therefore, the sum of the potential function over the entire action space only
depends on the number of edges in the graph. If
$|\mathcal{E}_{R}|=|\mathcal{E}_{I}|$, the results are the same for
$\mathcal{G}_{R}$ and $\mathcal{G}_{I}$. ∎

Lemma 2 states that the total potential value only depends on the number of
edges. However, the regularity of a graph affects the distribution of
potential values on the vertices of the unit lattice, as stated in the
following lemma, which establishes that the potential values are more evenly
distributed for regular graphs $\mathcal{G}_{R}$.

###### Lemma 3

Let $\mathcal{G}_{R}=([N],|\mathcal{E}_{R}|)$ and
$\mathcal{G}_{I}=([N],|\mathcal{E}_{I}|)$ be (connected) regular and irregular
graph with $N$ nodes, respectively. If
$|\mathcal{E}_{R}|=|\mathcal{E}_{I}|=|\mathcal{E}|$ is such that

$\frac{2|\mathcal{E}|}{N}\in\mathbb{Z}_{\geq 2},$ (49)

then

$\sum\limits_{a\in\mathcal{A}}\Bigg{(}\Phi_{R}(a)-\Big{(}\frac{1}{4}-\frac{\theta}{N}\Big{)}|\mathcal{E}|\Bigg{)}^{2}\\\
<\sum\limits_{a\in\mathcal{A}}\Bigg{(}\Phi_{I}(a)-\Big{(}\frac{1}{4}-\frac{\theta}{N}\Big{)}|\mathcal{E}|\Bigg{)}^{2},$
(50)

where $(\frac{1}{4}-\frac{\theta}{N})|\mathcal{E}|$ is the average potential
over the entire action space $\mathcal{A}$ for both $\mathcal{G}_{R}$ and
$\mathcal{G}_{I}$.

###### Proof:

Consider the uniformly distributed binary random vector $X$ with mean
$\mathbf{m}$ and variance $\Sigma$ as in Eq. 42. The statement in Eq. 50 is
equivalent to:

$\mathrm{Var}\big{[}\Phi_{R}(X)\big{]}<\mathrm{Var}\big{[}\Phi_{I}(X)\big{]},$
(51)

which is also equivalent to:

$\mathbf{E}\big{[}\Phi^{2}_{R}(X)\big{]}<\mathbf{E}\big{[}\Phi^{2}_{I}(X)\big{]}.$
(52)

We proceed by establishing Eq. 52. First, we obtain the following expression:

$\mathbf{E}\big{[}\Phi^{2}(X)\big{]}=\frac{1}{2}\mathrm{trace}(\mathbf{A}\Sigma\mathbf{A}\Sigma)+\mathbf{m}^{\mathsf{T}}\mathbf{A}\Sigma\mathbf{A}\mathbf{m}\\\
\hskip
20.0pt-\frac{2\theta}{N}\mathbb{1}^{\mathsf{T}}\mathbf{A}\Sigma\mathbf{A}\mathbf{m}+\frac{\theta^{2}}{N^{2}}\mathbb{1}^{\mathsf{T}}\mathbf{A}\Sigma\mathbf{A}\mathbb{1}.$
(53)

Let $\mathbf{d}\operatorname{\overset{def}{=}}\mathbf{A}\mathbb{1}$. Note that
$\mathbf{d}$ is the degree vector of the associated graph. After some algebra,
we rewrite Eq. 53 as:

$\mathbf{E}\big{[}\Phi^{2}(X)\big{]}=\frac{1}{32}|\mathcal{E}|+\Big{(}\frac{1}{4}-\frac{\theta}{2N}\Big{)}^{2}\|\mathbf{d}\|^{2}_{2}.$
(54)

Consider the following optimization problem:

$\displaystyle\underset{\mathbf{d}\in\mathbb{Z}^{N}}{\mathrm{minimize}}$
$\displaystyle\|\mathbf{d}\|_{2}$ (55) subject to
$\displaystyle\mathbf{d}\succeq\mathbb{1}$
$\displaystyle\mathbb{1}^{\mathsf{T}}\mathbf{d}=2|\mathcal{E}|.$

To solve this problem, we rewrite the equality constraint as follows:

$\mathbb{1}^{\mathsf{T}}\mathbf{d}=\|\mathbb{1}\|_{2}\|\mathbf{d}\|_{2}\cos(\tau)=2|\mathcal{E}|,$
(56)

where $\tau$ denotes the angle between the vectors $\mathbf{d}$ and
$\mathbf{1}$. Therefore, the minimum norm vector $\mathbf{d}^{\star}$ is
obtained by making $\cos(\tau)=1$, which implies that

$\mathbf{d}^{\star}=\alpha^{\star}\mathbb{1},\ \ \alpha^{\star}>0.$ (57)

Therefore,

$\alpha^{\star}=\frac{2|\mathcal{E}|}{N}.$ (58)

Our assumption in Eq. 49, guarantees the feasibility of
$\mathbf{d}^{\star}=\alpha^{\star}\mathbf{1},$ which implies that the graph
that minimizes Eq. 53 is regular. ∎

Equipped with Lemmas 2 and 3, we are ready to present our final Theorem, which
qualifies a regular graph as the best candidate for LLL in other to achieve
the smallest $\beta^{\min}_{\mathcal{G}}(\delta)$.

###### Theorem 3

Let $\mathcal{G}_{R}$ and $\mathcal{G}_{I}$ be a regular graph and an
irregular graph with the same number of vertices and edges, respectively.
Suppose LLL is performed on both networks with the same rationality level
$\beta$. The corresponding steady-state success probabilities satisfy:

$\mu_{R}(a^{\star}\mid\beta)>\mu_{I}(a^{\star}\mid\beta)$ (59)

###### Proof:

We prove the result for $a^{\star}=\mathbb{1}$. The other case,
$a^{\star}=\mathbb{0}$, is analogous, and it is omitted for brevity. Consider
the following quantities:

$\mu_{R}(a^{\star}\mid\beta)=\frac{e^{\beta\Phi_{R}(a^{\star})}}{\sum_{a\in\mathcal{A}}e^{\beta\Phi_{R}(a)}}$
(60)

and

$\mu_{I}(a^{\star}\mid\beta)=\frac{e^{\beta\Phi_{I}(a^{\star})}}{\sum_{a\in\mathcal{A}}e^{\beta\Phi_{I}(a)}}.$
(61)

Comparing the numerators of Eq. 60 and Eq. 61, we find that they are equal,
since:

$\Phi_{R}(\mathbb{1})=2\Big{(}\frac{1}{2}-\frac{\theta}{N}\Big{)}|\mathcal{E}|=\Phi_{I}(\mathbb{1}).$
(62)

Before we proceed to evaluate the denominators, consider the following
optimization problem:

$\displaystyle\underset{x_{1},\dots,x_{M}}{\mathrm{minimize}}$
$\displaystyle\sum\limits_{i=1}^{M}e^{\beta x_{i}}$ (63) subject to
$\displaystyle\sum\limits_{i=1}^{M}x_{i}=c,$

where $c$ and $\beta$ are constants. The unique minimizer of Problem
(LABEL:sumofexp) is

$x^{\star}_{1}=\dots=x^{\star}_{M}=\frac{c}{M}.$ (64)

Using Majorization Theory [27], the following result can be derived: Consider
the set $\mathcal{C}\operatorname{\overset{def}{=}}\\{x\in\mathbb{R}^{M}\mid
x_{1}+\cdots+x_{M}=c\\}$. Let $\mathbf{x},\mathbf{y}\in\mathcal{C}$. If

$\sum\limits_{i=1}^{M}\Big{(}x_{i}-\frac{c}{M}\Big{)}^{2}\leq\sum\limits_{i=1}^{M}\Big{(}y_{i}-\frac{c}{M}\Big{)}^{2}$
(65)

then

$\sum\limits_{i=1}^{M}e^{\beta x_{i}}\leq\sum\limits_{i=1}^{M}e^{\beta
y_{i}}.$ (66)

For $\mathcal{G}_{R}$ and $\mathcal{G}_{I}$ with the same number of edges,
from Lemma 2, we have:

$\sum\limits_{a\in\mathcal{A}}\Phi_{R}(a)=\sum\limits_{a\in\mathcal{A}}\Phi_{I}(a),$
(67)

and, from Lemma 3, we have:

$\sum\limits_{a\in\mathcal{A}}\bigg{(}\Phi_{R}(a)-\Big{(}\frac{1}{4}-\frac{\theta}{N}\Big{)}|\mathcal{E}|\bigg{)}^{2}\\\
<\sum\limits_{a\in\mathcal{A}}\bigg{(}\Phi_{I}(a)-\Big{(}\frac{1}{4}-\frac{\theta}{N}\Big{)}|\mathcal{E}|\bigg{)}^{2}.$
(68)

Let $M=2^{N}$, $c=(\frac{1}{4}-\frac{\theta}{N})2^{N}|\mathcal{E}|$ and
$x_{i}$’s are the potential values at the action profiles $a\in\mathcal{A}$.
Plugging these back into Problem (LABEL:sumofexp), it is immediate to see
that:

$\sum_{a\in\mathcal{A}}e^{\beta\Phi_{R}(a)}<\sum_{a\in\mathcal{A}}e^{\beta\Phi_{I}(a)}$
(69)

since on the action space $\mathcal{A}$, a regular graph has the most evenly
distributed potential values compared to any irregular graph. Finally, notice
that $\mu_{R}(a^{\star}\mid\beta)$ and $\mu_{I}(a^{\star}\mid\beta)$ have the
same numerator, while the latter has a strictly larger denominator. Therefore,

$\mu_{R}(a^{\star}\mid\beta)>\mu_{I}(a^{\star}\mid\beta).$ (70)

∎

###### Remark 2

Theorem 3 implies that any irregular graph with the same number of edges as a
regular graph yields a lower probability of learning success when the agents
have the same bounded rationality level. In practical settings such as the
design of robotic, sensor or satellite networks, the cost of operating the
system is likely to be increasing in the number of edges in the graph. Thus,
if learning is to be performed, we should always choose to employ a regular
network structure if the parameters allow it. In the case that
$2|\mathcal{E}|/N$ is not an integer, we should design the network according
to a “near-regular” graph, such that most of the nodes have the same degree.

##  VI Numerical Results

To provide a visual representation of our results, consider a network
coordination game with $N=20$ agents, over connected graphs with
$|\mathcal{E}|=100$ edges, and parameter $\theta=9$. Since
$\theta<\theta^{\mathrm{th}}=N/2=10$, the optimal strategy according to
LABEL:{01irregular} is $a^{\star}=\mathbb{1}$. The probability of successfully
learning $a^{\star}$ as a function of the rationality parameter $\beta$ for
different graphs is shown in Fig. 3. Our base line for comparison in Fig. 3 is
the regular graph, whose probability of learning success is strictly larger
that any of the other 100 randomly generated graphs obtained for this
simulation. The average performance and the standard deviation of these
randomly generated graphs is shown in the shaded region strictly below the
curve for the regular graph. This is an illustration of Theorem 3, which holds
for any number of nodes and edges, provided that there exists a regular graph
with such parameters.

Figure 2: Two graphs with equal number of nodes and edges.

##  VII Conclusions and future work

Figure 3: Most papers should have a block diagram that summarizes the problem
we are addressing.

Network coordination games have been used to model many interesting
applications in economics and engineering. A large number of works focus on
the convergence analysis of learning in settings with perfectly rational
agents. Instead, we studied the case when the agents have bounded rationality,
and the effect that connectivity in the network structure has on the
probability that the system will converge to the optimal Nash equilibrium
solution. We have shown that connectivity can be used to compensate for the
lack of rationality, in the sense that adding communication links increase the
probability of convergence. Then, we proved that among all irregular networks
with the same number of nodes and edges, regular networks (when one exists),
have a strictly larger probability of success that irregular networks. The
design implication is that, when the system designer is interested in
enhancing learning success, it should enable equal access to connectivity by
every agent.

There are many interesting research directions stemming from this work. The
first is to introduce randomness in this game, by considering a Bayesian
setting with random task difficulty $\theta$. A second would be to consider a
heterogeneous setting where the agents engage in LLL (or an equivalent
algorithm) with different levels of rationality. Finally, we would like to
consider the coordination problem with multiple tasks where agents have
different affinities over tasks, and study the effect of network structure in
learning in this case.

## References

  * [1] C. Chamley, Rational herds: Economic models of social learning.  Cambridge University Press, 2004.
  * [2] D. López-Pintado, “Contagion and coordination in random networks,” International Journal of Game Theory, vol. 34, pp. 371–381, 2006.
  * [3] M. D. McCubbins, R. Paturi, and N. Weller, “Connected coordination: Network structure and group coordination,” American Politics Research, vol. 37, no. 5, pp. 899–920, 2009.
  * [4] A. Montanari and A. Saberi, “The spread of innovations in social networks,” Proceedings of the National Academy of Sciences, vol. 107, no. 47, pp. 20196–20201, 2010.
  * [5] I. Arieli, Y. Babichenko, R. Peretz, and H. P. Young, “The speed of innovation diffusion in social networks,” Econometrica, vol. 88, no. 2, pp. 569–594, 2020.
  * [6] W. S. Rossi, G. Como, and F. Fagnani, “Threshold models of cascades in large-scale networks,” IEEE Transactions on Network Science and Engineering, vol. 6, no. 2, pp. 158–172, 2017.
  * [7] L. Zhou, J. Wang, M. Ye, B.-L. Zhang, and Y. Zheng, “Consensus of hybrid behavior for graphical coordination games,” IEEE Transactions on Circuits and Systems II: Express Briefs, 2023.
  * [8] L. Arditti, G. Como, F. Fagnani, and M. Vanelli, “Robust coordination of linear threshold dynamics on directed weighted networks,” IEEE Transactions on Automatic Control, 2024.
  * [9] B. Canty, P. N. Brown, M. Alizadeh, and J. R. Marden, “The impact of informed adversarial behavior in graphical coordination games,” in IEEE Conference on Decision and Control (CDC), pp. 1923–1928, 2018.
  * [10] K. Paarporn, B. Canty, P. N. Brown, M. Alizadeh, and J. R. Marden, “The impact of complex and informed adversarial behavior in graphical coordination games,” IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 200–211, 2020.
  * [11] K. Paarporn, M. Alizadeh, and J. R. Marden, “A risk-security tradeoff in graphical coordination games,” IEEE Transactions on Automatic Control, vol. 66, no. 5, pp. 1973–1985, 2021.
  * [12] M. M. Vasconcelos and B. Touri, “On the coordination efficiency of strategic multi-agent robotic teams,” in 62nd IEEE Conference on Decision and Control (CDC), pp. 8130–8137, 2023.
  * [13] M. A. Dahleh, A. Tahbaz-Salehi, J. N. Tsitsiklis, and S. I. Zoumpoulis, “Coordination with local information,” Operations Research, vol. 64, no. 3, pp. 622–637, 2016.
  * [14] C. M. Leister, Y. Zenou, and J. Zhou, “Social connectedness and local contagion,” The Review of Economic Studies, vol. 89, no. 1, pp. 372–410, 2022.
  * [15] Y. Wei and M. M. Vasconcelos, “Strategic multi-task coordination over regular networks of robots with limited computation and communication capabilities,” in 57th Annual Conference on Information Sciences and Systems (CISS), pp. 1–6, 2023.
  * [16] A. Sanjab, W. Saad, and T. Başar, “A game of drones: Cyber-physical security of time-critical UAV applications with cumulative prospect theory perceptions and valuations,” IEEE Transactions on Communications, vol. 68, no. 11, pp. 6990–7006, 2020.
  * [17] V. Leon, S. Rasoul Etesami, and R. Nagi, “Diffusion of innovation under limited-trust equilibrium,” in IEEE 61st Conference on Decision and Control (CDC), pp. 3145–3150, 2022.
  * [18] A. Kanellopoulos and K. G. Vamvoudakis, “Bounded rationality in byzantine sensors under attacks,” IEEE Transactions on Automatic Control, vol. 67, no. 7, pp. 3606–3613, 2022.
  * [19] N. Abuzainab, W. Saad, C. S. Hong, and H. V. Poor, “Cognitive hierarchy theory for distributed resource allocation in the internet of things,” IEEE Transactions on Wireless Communications, vol. 16, no. 12, pp. 7687–7702, 2017\.
  * [20] K. Paarporn, “The madness of people: rational learning in feedback-evolving games,” arXiv preprint arXiv:2311.02745, 2023.
  * [21] J. R. Marden and J. S. Shamma, “Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation,” Games and Economic Behavior, vol. 75, no. 2, pp. 788–808, 2012.
  * [22] Y. Zhang and M. M. Vasconcelos, “Rationality and connectivity in stochastic learning for networked coordination games,” American Control Conference (to appear) – arXiv preprint arXiv:2309.16931, 2024.
  * [23] J. Becker, D. Brackbill, and D. Centola, “Network dynamics of social influence in the wisdom of crowds,” Proceedings of the national academy of sciences, vol. 114, no. 26, pp. E5070–E5076, 2017.
  * [24] J. P. Hespanha, Noncooperative game theory: An introduction for engineers and computer scientists.  Princeton University Press, 2017.
  * [25] D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior, vol. 14, no. 1, pp. 124–143, 1996.
  * [26] A. Y. Yazıcıoğlu, M. Egerstedt, and J. S. Shamma, “Formation of robust multi-agent networks through self-organizing random regular graphs,” IEEE Transactions on Network Science and Engineering, vol. 2, no. 4, pp. 139–151, 2015.
  * [27] A. W. Marshall, I. Olkin, and B. C. Arnold, “Inequalities: theory of majorization and its applications,” 1979.