#  Likelihood Equilibria in the Ising Game 111This work was supported by a
grant for research centers in the field of artificial intelligence, provided
by the Analytical Center for the Government of the Russian Federation in
accordance with the subsidy agreement (agreement identifier
000000D730324P540002) and the agreement with the Moscow Institute of Physics
and Technology dated November 1, 2021 No. 70-2021-00138.

Andrey Leonidov(a,b) (a) P.N. Lebedev Physical Institute, Moscow, Russia
(b) Moscow Institute of Physics and Technology, Dolgoprudny, Russia

###### Abstract

A description of static equilibria in the noisy binary choice (Ising) game on
complete and random graphs resulting from maximisation of the likelihood of
system configurations is presented. An equivalence of such likelihood
equilibria to the competitive Bayes-Nash quantal response expectation
equilibria in the special case of consistent agents expectations is
established. It is shown that the same likelihood equilibria are obtained by
considering the system’s partition function.

##  1 Introduction

One of the key challenges in building a quantitative description of multiagent
systems is incorporating, to the maximal degree possible, ideas and results
from game theory [1, 2, 3]. A particularly important role is played by
developing various interpretations of game-theoretic equilibria as natural
states of mutiagent systems.

A description of static game-theoretic equilibria is in many cases of
probabilistic nature. At the fundamental level probabilities provide the most
natural interpretation of Nash equilibria in mixed strategies, see e.g. [4].
Probabilities can also directly appear in the description of a game under
consideration. This is in particular the case with games in which agent’s
utilities include random components. Of direct relevance to the present paper
is the corresponding formulation of noisy discrete choice problems [5] and the
particular version of Nash mixed strategies equilibria in such problems, the
Quantal Response Equilibria (QRE) [6, 7]. A quantitative description of QRE is
based on describing agent’s choice as dependent on their expectations with
respect to that of neighbouring agents. The QRE can thus be alternatively
described as expectation equilibria. Static QRE/expectation equilibria in the
noisy binary choice games were studied in [8, 9, 10, 12, 11] and, in a more
general case of noisy multinomial choice, in [13, 14].

A description of a fully heterogeneous game in which one needs to keep track
of idiosyncratic characterstics of every agent is although formally possible
but does not allow to construct its interpretable solution. The way out is to
include into consideration only a few attributes describing heterogeneity of
agent’s properites. For example, in graphical games a usual choice is to
distinguish agents by a degree of a vertex in which an agent resides, see e.g.
[17]. The key quantity reflecting the resulting redundancy is entropy and,
indeed it does explicitly appear in describing the dynamical evolution of
noisy binary choice (Ising) games towards their equilibria which turn out to
be the QRE/expectation ones [9, 11] . At the same time available descriptions
of static QRE/expectation equilibria are based on describing individual
expectations so that the above-mentioned redundancy is reflected only in
assuming their appropriate equivalence. In probabilistic terms this means that
only expectation values for marginal distributions depending on expectations
with respect to neighbour’s choices as parameters are considered.

To construct a collective description of game-theoretic equilibria in the
presence of random effects one should consider a full multivariate probability
distribution of strategies configuration, construct its reduced version
appropriate for the problem under consideration and define game-theoretic
equilibria in its terms. The most natural candidates for equilibrium
configurations are here those maximising the likelihood (i.e. the above-
described probability distribution) . In the present paper we continue the
analysis of [11] by explicitly constructing the static likelihood equilibria
for the Ising game on complete and random graphs for arbitrary noise and
demonstrate their equivalence to entropic equilibria as well as to those
constructed through maximising the system’s partition function.

##  2 Likelihood Equilibria

###  2.1 Likelihood Equilibria in the Ising Game: General formulae

An Ising game considered in the present paper is a noisy binary choice game
played by $N$ agents placed in the vertices of an undirected graph and
equipped with two pure strategies $\\{s_{i}=\pm 1\\}$, $i=1,\dots,N$. A
general description of such a system is given by the probability distribution
(likelihood) ${\cal P}(s_{1},\dots,s_{N}|\Theta)$, where $\Theta$ denotes a
set of parameters, both idiosyncratic and global, that reflect a particular
chosen description of the noisy decision-making process. It is then natural to
define a likelihood equilibrium $(s_{1}^{\rm eq},\dots,s_{N}^{\rm eq})$ of the
game under consideration as a configuration having maximal probability of
realisation, i.e.

$(s_{1}^{\rm eq},\dots,s_{N}^{\rm
eq})=\text{arg}\;\underset{s_{1},\dots,s_{N}}{\text{max}}\;{\cal
P}(s_{1},\dots,s_{N}|\Theta)$ (1)

An analysis of static equilibria in games on graphs with noisy discrete
response is based on consideration of expected utilities
${\mathbb{E}}_{(i)}\left[U_{i}(s_{i})\right]$ reflecting the value of choosing
$s_{i}$ depending in particular on expectations of an agent with respect to
choices made by his neighbours. For an Ising game for an agent $i$ the
expected utility of choosing the strategy $s_{i}$ is assumed to have the form
[8, 9, 11]

${\mathbb{E}}_{(i)}\left[U_{i}(s_{i})\right]=\left(H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right)s_{i}+\epsilon_{s_{i}}$ (2)

where $\\{a_{ij}\\}$ are matrix elements of the adjacency matrix $a$ with
$a_{ij}=1$ corresponding to an edge $j\leftrightarrow i$ and $a_{ij}=0$
otherwise, ${\mathbb{E}}_{(i)}\left[s_{j}\right]$ stands for the expected
value of the choice $s_{j}$ as perceived by the agent $i$, $J>0$ is a constant
characterising mutual influence of agents and $\epsilon_{s_{i}}$ are
idiosyncratic strategy-dependent random additive contributions to utility with
the distribution $f(\epsilon_{s_{i}}|\beta)$ assumed to be the same for all
agents where, in turn, the parameter $\beta$ characterises the level of noise.
The particular set of parameters $\Theta$ used in this description is thus

$\Theta=\left(J,\beta,H,\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\}\right)$ (3)

From equation (2) it follows that the probability of choosing the strategy
$s_{i}$ by an agent $i$ is

$\displaystyle p(s_{i}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})$
$\displaystyle=\text{Prob}\left[{\mathbb{E}}_{(i)}\left[U_{i}(s_{i})\right]>{\mathbb{E}}_{(i)}\left[U_{i}(-s_{i})\right]\right]$
$\displaystyle=F\left(2\beta\left[H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]s_{i}\right)$ (4)

where

$F(x)={\rm Prob}\left[\epsilon_{-s_{i}}-\epsilon_{s_{i}}<x\right]$ (5)

In what follows we will use a log-odds parametrisation of $F(x)$ for which

$F(x)=\frac{e^{\frac{1}{2}g(x)}}{2\cosh\left[\frac{1}{2}g(x)\right]}$ (6)

where for symmetric noise distributions $f(\epsilon_{s_{i}}|\beta)$ the
function $g(x)$ is an odd function of its argument. In terms of the
parametrisation (6) equation (2.1) takes the form

$\displaystyle p(s_{i}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})=$ (7)
$\displaystyle\frac{\exp\left[s_{i}\frac{1}{2}g\left(2\beta\left[H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]\right)\right]}{2\cosh\left[\frac{1}{2}g\left(2\beta\left[H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]\right)\right]},$

where we have taken into account that $(s_{i})^{k}=s_{i}$ for $k$ odd and
$(s_{i})^{k}=1$ for $k$ even. In the special case of the Gumbel noise

$f(\epsilon_{s_{i}}|\beta)=\beta
e^{-\beta\epsilon_{s_{i}}+e^{-\beta\epsilon_{s_{i}}}}$ (8)

the function $g(x)=x$ so that

$p(s_{i}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})=\frac{\exp\left[s_{i}\left(\beta
H+\beta J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right)\right]}{2\cosh\left[\beta
H+\beta J\sum_{j\neq i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]}$ (9)

For given sets of expectations $\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\}$
for all $i=1,\dots,N$ equation (7) does fully describe an equilibrium set of
probabilities $\\{p(s_{i}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})\\}$
defining the corresponding Bayes-Nash competitive equilibrium in mixed
strategies. Further simplifications are possible through specifying a
structure of the set of expectations. In particular, the quantal response
equilibrium [6, 7] is defined by the expectation self-consistency conditions

${\mathbb{E}}_{(i)}\left[s_{i}\right]={\mathbb{E}}_{(j)}\left[s_{i}\right]\;\;\;\forall
i,j$ (10)

In the competitive game under consideration agents form their expectations
independently, so from (7) it follows that the likelihood ${\cal
P}(s_{1},\dots,s_{N}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})$222Here and
in what follows we omit explicit indication of the parameters $J,\beta,H$ in
the formulae for the likelihood. of a configuration $(s_{1},\dots,s_{N})$ for
a given set of expectations $\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\}$
equals

$\displaystyle{\cal
P}(s_{1},\dots,s_{N}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})=\prod_{i=1}^{N}p(s_{i}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})$
$\displaystyle=\prod_{i=1}^{N}\frac{\exp\left[s_{i}\frac{1}{2}g\left(2\beta\left[H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]\right)\right]}{2\cosh\left[\frac{1}{2}g\left(2\beta\left[H+J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]\right)\right]}$ (11)

For the Gumbel noise

$\displaystyle{\cal
P}(s_{1},\dots,s_{N}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})=$ (12)
$\displaystyle\prod_{i=1}^{N}\frac{\exp\left[s_{i}\left(\beta H+\beta
J\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right)\right]}{2\cosh\left[\beta
H+\beta J\sum_{j\neq i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\right]}$

The likelihood equilibrium $(s_{1}^{\rm eq},\dots,s_{N}^{\rm eq})$ of the game
under consideration is thus defined by

$(s_{1}^{\rm eq},\dots,s_{N}^{\rm eq})=\underset{s_{1},\dots,s_{N}}{\text{arg
max}}\;{\cal P}(s_{1},\dots,s_{N}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})$
(13)

where ${\cal P}(s_{1},\dots,s_{N}|\\{{\mathbb{E}}_{(i)}\left[s_{j}\right]\\})$
is defined in (2.1).

In what follows we consider the properties of likelihood equilibria for the
special cases of complete and random graphs, the latter described in the
framework of the configuration model.

###  2.2 Likelihood Equilibria: Complete Graph

In the case of complete graph

$\sum_{j\neq
i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\;\;\;\rightarrow\;\;\;\frac{1}{N}\sum_{j\neq
i}{\mathbb{E}}_{(i)}\left[s_{j}\right]$ (14)

It is natural to assume that an agent $i$’s expectations with respect to the
choices of its $N-1$ neighbours are equivalent, i.e.

${\mathbb{E}}_{(i)}\left[s_{j}\right]=m^{(e)}_{(i)}\;\;\;\forall j,$ (15)

so that in the limit of large $N$

$\frac{1}{N}\sum_{j\neq i}{\mathbb{E}}_{(i)}\left[s_{j}\right]=m^{(e)}_{(i)}$
(16)

The likelihood is thus dependent on a set of expectations
$\\{m^{(e)}_{(i)}\\}$,

$\displaystyle{\cal P}(s_{1},\dots,s_{N}|\\{m^{(e)}_{(i)}\\})=$ (17)
$\displaystyle\prod_{i=1}^{N}\frac{\exp\left[s_{i}\frac{1}{2}g\left(2\beta\left[H+Jm^{(e)}_{(i)}\right]\right)\right]}{2\cosh\left[\frac{1}{2}g\left(2\beta\left[H+Jm^{(e)}_{(i)}\right]\right)\right]}$

In the considered case of the complete graph topology there is nothing
idiosyncratic about the agents. It is therefore natural to assume that their
expectations $m^{(e)}_{(i)}$ are (narrowly) centered around some common value
$m^{(e)}$333Let us note that a standard assumption in the literature on
graphical games is that expectations of equivalent agents are also equivalent,
i.e. that $m^{(e)}_{(i)}=m^{(e)}$:

$m^{(e)}_{(i)}=m^{(e)}+\delta m^{(e)}_{(i)}$ (18)

From the structure of (17) it is clear that in the limit of large $N$ the
contribution of possible idiosyncratic expectation shifts $\\{\delta
m^{(e)}_{(i)}\\}$ is heavily suppressed, so that the expression for the
likelihood (17) does read

$\displaystyle{\cal
P}(s_{1},\dots,s_{N}|m^{(e)})=\prod_{i=1}^{N}\frac{\exp\left[s_{i}\frac{1}{2}g\left(2\beta\left[H+Jm^{(e)}\right]\right)\right]}{2\cosh\left[\frac{1}{2}g\left(2\beta\left[H+Jm^{(e)}\right]\right)\right]}$
$\displaystyle=\frac{\exp\left[Nm\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]\right)^{N}}$
(19)

where we have introduced an average choice $m$

$m=\frac{1}{N}\sum_{i=1}^{N}s_{i}$ (20)

As ${\cal P}(s_{1},\dots,s_{N}|m^{(e)})$ depends on $(s_{1},\dots,s_{N})$ only
through $m$, the probability distribution (2.2) can be rewritten as

$\displaystyle{\cal P}(s_{1},\dots,s_{N}|m^{(e)})\to{\cal P}(m|m^{(e)})$ (21)
$\displaystyle={\mathcal{N}}(m)\frac{\exp\left[Nm\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]\right)^{N}}$
$\displaystyle=\frac{\exp\left[N\left(m\frac{1}{2}g(2\beta[H+Jm^{(e)}])+{\mathcal{H}}(m)\right)\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]\right)^{N}},$

where ${\mathcal{N}}(m)$ is a number of configurations $(s_{1},\dots,s_{N})$
such that $(\sum_{i}s_{i})/N=m$ and ${\mathcal{H}}(m)=\ln{\mathcal{N}}(m)$ is
the Bernoulli entropy

${\mathcal{H}}(m)=-\frac{1-m}{2}\ln\left(\frac{1-m}{2}\right)-\frac{1+m}{2}\ln\left(\frac{1+m}{2}\right)$
(22)

We have therefore

$\displaystyle{\cal P}(m|m^{(e)})$
$\displaystyle=\exp\left\\{N\left[m\frac{1}{2}g(2\beta[H+Jm^{(e)}])+{\cal
H}(m)\right.\right.$
$\displaystyle-\left.\left.\ln\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]\right)\right]\right\\}$
(23)

The likelihood equilibrium $m^{\rm eq}$ is defined by

$m^{\rm eq}=\text{arg}\;\underset{m}{\text{max}}\;{\cal P}(m|m^{(e)})$ (24)

The relevant log-likelihood ${\cal V}(m|m^{(e)})$ reads

$\displaystyle{\cal V}(m|m^{(e)})$
$\displaystyle=N\left[m\frac{1}{2}g(2\beta[H+Jm^{(e)}])+{\cal H}(m)\right]$
$\displaystyle\equiv N{\it v}(m|m^{(e)})$ (25)

We have

$\frac{d{\it
v}(m|m^{(e)})}{dm}=\frac{1}{2}g(2\beta[H+Jm^{(e)]})-\text{atanh}(m)$ (26)

The likelihood equilibria $m^{\rm eq}$ do therefore satisfy the equation

$\text{atanh}(m^{\rm eq})=\frac{1}{2}g(2\beta[H+Jm^{(e)}])$ (27)

or, equivalently,

$m^{\rm eq}=\tanh\left[\frac{1}{2}g(2\beta[H+Jm^{(e)}])\right]$ (28)

Let us note that

$\left.\frac{d^{2}{\it v}(m|m^{(e)})}{dm^{2}}\right|_{m=m^{\rm
eq}}=-\frac{1}{1-(m^{\rm eq})^{2}}<0,$ (29)

so that all the found values of $m^{\rm eq}$ correspond to the maxima of the
log-likelihood ${\it v}(m|m^{(e)})$.

It is easy to check that the distribution ${\cal P}(m|m^{(e)})$ defined in
(21) is correctly normalised and that

${\mathbb{E}}_{m}[m]=\tanh\left[\frac{1}{2}g\left(2\beta[H+Jm^{(e)}]\right)\right]$
(30)

From from equations (28,32) we see that in the case under consideration

$m^{\rm eq}={\mathbb{E}}_{m}[m]$ (31)

An additional assumption of consistency between the configuration equilibrium
and expectations $m^{\rm eq}={\mathbb{E}}_{m}[m]=m^{(e)}$ defining
expectation/QRE equilibria leads to an equation on $m^{\rm eq}$ of the form

$m^{\rm eq}=\tanh\left[\frac{1}{2}g(2\beta[H+Jm^{\rm eq}])\right]$ (32)

The above results can be rederived by analysing, in analogy with the approach
developed in statistical physics, the system’s partition function. The
partition function is computed using unnormalized probabilities of system’s
configurations. In the case under consideration we get from (21)

${\cal P}(m|m^{(e)})\sim e^{N\left(m\frac{1}{2}g(2\beta[H+Jm^{(e)}])+{\cal
H}(m)\right)}\equiv e^{Nv(m|m^{(e)})}$ (33)

where the function $v(m|m^{(e)})$ was defined in (2.2) The expression for the
partition function ${\cal Z}$ does thus read

${\cal Z}=\sum_{m=-1}^{1}e^{Nv(m|m^{(e)})}$ (34)

In the partition function-related approach equilibrium states $m^{\rm eq}$ are
those giving dominant contribution to ${\cal Z}$. In the limit $N\to\infty$
these are

$m^{\rm eq}=\text{arg}\;\underset{m}{\text{max}}\;v(m|m^{(e)}),$ (35)

i.e. exactly the same equilibria as described by equation (28).

###  2.3 Likelihood Equilibria: Random Graph

Let us now consider likelihood equilibria for the Ising game on undirected
random graphs described in the framework of the configuration model, see e.g.
[16]. In this model a random graph with a given vertex degree distribution
$\\{\pi_{k}\\}$ is constructed by randomly creating edges between vertices $i$
and $j$ with degrees $k_{i}$ and $k_{j}$ with a probabiliity

${\rm
Prob}(a_{ij}=1)={\mathbb{E}}[a_{ij}]=\frac{k_{i}k_{j}}{{\mathbb{E}}_{\pi}[k]}$
(36)

We will consider the game in the annealed approximation in which we make the
following replacement in (7)

$\displaystyle\sum_{j\neq i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]\;\;\;$
$\displaystyle\rightarrow\;\;\;\sum_{j\neq
i}{\mathbb{E}}[a_{ij}]{\mathbb{E}}_{(i)}\left[s_{j}\right]$
$\displaystyle=\frac{1}{N}\sum_{j\neq
i}\frac{k_{i}k_{j}}{{\mathbb{E}}_{\pi}[k]}{\mathbb{E}}_{(i)}\left[s_{j}\right]$
(37)

The only source of heterogeneity in this model is a degree distribution of the
vertices. Generically the choice of an agent $i$ is driven by his expectations
with respect to then neighbours choices ${\mathbb{E}}_{(i)}[s_{j}]$. In the
case under consideration it is assumed, following the standard approach [17],
that an expectation value ${\mathbb{E}}_{(i)}[s_{j}]$ depends only on the
degree $k$ of the vertex $j$. In what follows we will use the notation

${\mathbb{E}}_{(i)}[s_{j}]=m^{(e)}_{k}\;\;\;\;\forall i,\;\;k_{j}=k$ (38)

The probabiility $p_{i}^{(k)}$ of choosing the strategy $s_{i}^{(k)}$ by the
agent $i$ located at one of the vertices with the degree $k$ is the same for
all such vertices. Using (2.3,38) the argument in (7) can be rewritten [11] in
the following form

$H+J\sum_{j\neq i}a_{ij}{\mathbb{E}}_{(i)}\left[s_{j}\right]=H+Jkm^{(e)}_{w}]$
(39)

where

$m^{(e)}_{w}=\sum_{k}\frac{k\pi_{k}}{{\mathbb{E}}_{\pi}[k]}m^{(e)}_{k}$ (40)

The explicit expression for the probability does therefore read [11]

$p_{i}^{(k)}(s_{i}^{(k)}|m^{(e)}_{w})=\frac{e^{\frac{1}{2}s_{i}^{(k)}g(2\beta[H+Jkm^{(e)}_{w}])}}{2\cosh\left[\frac{1}{2}g(2\beta[H+Jkm^{(e)}_{w}])\right]}$
(41)

Using the expression (41), we get the following expression for the
distribution function of the system (2.1):

$\displaystyle{\cal P}(s_{1},\dots,s_{N}|m^{(e)}_{w})$ (42)
$\displaystyle=\prod_{k=1}^{\infty}\frac{\exp\left[N_{k}m_{k}\frac{1}{2}g(2\beta[H+Jkm^{(e)}_{w}])\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jkm^{(e)}_{w}])\right]\right)^{N_{k}}}$

where $N_{k}$ is a number of vertices having degree $k$ and

$m_{k}=\frac{1}{N_{k}}\sum_{i\in\Xi_{k}}s_{i}^{(k)}$ (43)

It is convenient to rewrite the distribution in terms of variables
$\\{m_{k}\\}$ such that

${\cal P}(s_{1},\dots,s_{N}|m^{(e)}_{w})=\prod_{k=1}^{\infty}{\cal
P}(m_{k}|m_{w}^{(e)})$ (44)

where, in the limit of large $\\{{\cal N}_{k}\\}$

$\displaystyle{\cal P}(m_{k}|m^{(e)})={\cal
N}(m_{k})\frac{\exp\left[N_{k}m_{k}\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])\right]\right)^{N_{k}}}$
$\displaystyle=\frac{\exp\left[N_{k}\left(m_{k}\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])+{\mathcal{H}}(m_{k})\right)\right]}{\left(2\cosh\left[\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])\right]\right)^{N_{k}}}$
(45)

Maximisation of (2.3) wiht respect to $m_{k}$ leads to equations on the
equilibrium values of $m_{k}^{\rm eq}$ describing the corresponding likelihood
equilibria. We have

$\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])=\text{atanh}(m^{\rm eq}_{k})$ (46)

or, equivalently

$m^{\rm eq}_{k}=\tanh\left[\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])\right]$ (47)

From (47) one gets the following equation for $m^{\rm eq}_{w}$

$\displaystyle m^{\rm eq}_{w}$
$\displaystyle=\sum_{k}\frac{k\pi_{k}}{{\mathbb{E}}_{\pi}[k]}m_{k}$ (48)
$\displaystyle=\sum_{k}\frac{k\pi_{k}}{{\mathbb{E}}_{\pi}[k]}\tanh\left[\frac{1}{2}g(2\beta[H+Jkm_{w}^{(e)}])\right]$
(49)

In the particular case of QRE $m^{(e)}_{k}=m^{\rm eq}_{k}$, so that

$\displaystyle m^{\rm eq}_{k}$ $\displaystyle=$
$\displaystyle\tanh\left[\frac{1}{2}g(2\beta[H+Jkm^{\rm eq}_{w}])\right]$ (50)
$\displaystyle m^{\rm eq}_{w}$ $\displaystyle=$
$\displaystyle\sum_{k}\frac{k\pi_{k}}{{\mathbb{E}}_{\pi}[k]}\tanh\left[\frac{1}{2}g(2\beta[H+Jkm_{w}])\right]$

Equations (47,48,50,2.3) coincide with those obtained in [12, 11] where
competitive static Bayes-Nash QRE on random graphs were studied.

##  3 Conclusions

Let us summarise the results obtained in the paper:

  * •

A description of likelihood equilibria in the Ising game on complete graph is
presented and its equivalence to the earlier studied quantal response
equilibrium corresponding to a special case of consistent expectations [12,
11] is established.

  * •

A description of likelihood equilibria in the Ising game on random graphs in
hte framework of annealed approximation to the configuration model is
presented and its equivalence to the earlier studied quantal response
equilibrium corresponding to a special case of consistent expectations [12,
11] is established.

  * •

An equivalence of equilibria obtained by considering the system’s partition
function to the likelihood equilibria for the Ising game on complete graph is
established.

## References

  * [1] Y. Shoham, K. Leyton-Brown, _Multiagent systems: Algorithmic, game-theoretic, and logical foundations_ New York, NY, USA: Cambridge University Press, 2008
  * [2] Y. Lu, K. Yan, “Algorithms in multi-agent systems: a holistic perspective from reinforcement learning and game theory,” arXiv preprint arXiv:2001.06487, Jan. 31, 2020
  * [3] N. Vlassis, _A concise introduction to multiagent systems and distributed artificial intelligence_ , Springer Nature Switzerland, 2022
  * [4] D. Fudenberg, J. Tirole, _Game theory_ , New Dehli, India: Ane Books Pvt. Ltd, 2015
  * [5] S.P. Anderson, A. De Palma, J.-F. Thisse, _Discrete choice theory of product differentiation_ Cambridge, MA, USA: MIT press, 1992
  * [6] J.K. Goeree, C.A. Holt and T.R. Palfrey, _Quantal response equilibria_ , Princeton. NJ, USA: Princeton University Press, 2016
  * [7] R.D. McKelvey, T.R. Palfrey, “Quantal response equilibria for normal form games”, _Games and economic behavior_ , vol. 10, p.p. 6–38, Jul. 1995
  * [8] W.A. Brock, S.N. Durlauf, “Discrete choice with social interactions”, _The Review of Economic Studies_ , vol. 68, p.p. 235–260, Apr. 2001
  * [9] L. Blume, S. Durlauf, “Equilibrium concepts for social interaction models”, _International Game Theory Review_ , vol. 5, p.p. 193–209, 2003
  * [10] S.N. Durlauf, Y.M. Ioannides, “Social interactions”, _Annu. Rev. Econ._ , vol. 2, p.p. 451–458, Apr. 2010
  * [11] A. Leonidov, A. Savvateev, A. Semenov, “Ising game on graphs”, _Chaos, Solitons & Fractals_, vol. 180, p. 114540, March 2024
  * [12] A. Leonidov, A. Savvateev, A. Semenov, “QRE in the Ising Game”, CEUR Workshop Proceedings MACSPro’2020, 2020
  * [13] W.A. Brock, S.N. Durlauf, “A multinomial-choice model of neighborhood effects”, _American Economic Review_ , vol. 92, p.p. 298-303, May 2002
  * [14] A. Leonidov, “Potts game on graphs: static equilibria”, _Computational Management Science_ , vol. 9, p. 9, 2024
  * [15] A. Leonidov, A. Savvateev, A. Semenov, “Quantal response equilibria in binary choice games on graphs”, arXiv preprint arXiv:1912.09584, Dec. 2019
  * [16] M. Newman, _Networks_ , Oxford, UK: Oxford University Press, 2018, p.p 369-416
  * [17] S. Goyal, _Connections: an introduction to the economics of networks_ , Princeton, NJ, USA: Princeton University Press, 2012


# Multi-Objective Hardware Aware Neural Architecture Search using Hardware
Cost Diversity

Nilotpal Sinha, Peyman Rostami, Abd El Rahman Shabayek, Anis Kacem, Djamila
Aouada
{nilotpal.sinha, peyman.rostami, abdelrahman.shabayek, anis.kacem,
<EMAIL_ADDRESS>
SnT, University of Luxembourg

###### Abstract

Hardware-aware Neural Architecture Search approaches (HW-NAS) automate the
design of deep learning architectures, tailored specifically to a given target
hardware platform. Yet, these techniques demand substantial computational
resources, primarily due to the expensive process of assessing the performance
of identified architectures. To alleviate this problem, a recent direction in
the literature has employed representation similarity metric for efficiently
evaluating architecture performance. Nonetheless, since it is inherently a
single objective method, it requires multiple runs to identify the optimal
architecture set satisfying the diverse hardware cost constraints, thereby
increasing the search cost. Furthermore, simply converting the single
objective into a multi-objective approach results in an under-explored
architectural search space. In this study, we propose a Multi-Objective method
to address the HW-NAS problem, called MO-HDNAS, to identify the trade-off set
of architectures in a single run with low computational cost. This is achieved
by optimizing three objectives: maximizing the representation similarity
metric, minimizing hardware cost, and maximizing the hardware cost diversity.
The third objective, _i.e_. hardware cost diversity, is used to facilitate a
better exploration of the architecture search space. Experimental results
demonstrate the effectiveness of our proposed method in efficiently addressing
the HW-NAS problem across six edge devices for the image classification task.

##  1 Introduction

Advancements in deep learning systems have brought about a revolutionary
impact on various domains, particularly in computer vision [25, 24, 33, 23,
20, 13, 19], natural language processing [7, 31, 9], and more. These
remarkable achievements were made possible by the creation of meticulously
designed architectures that are specifically tailored for individual tasks.

Figure 1: An illustration of the difference between a single objective
approach to HW-NAS problem and our proposed method MO-HDNAS.

In response to the growing need for more advanced architectures, researchers
have turned their focus towards developing algorithms that can effectively
explore the extensive space of neural architectures. These algorithms,
collectively known as Neural Architecture Search (NAS) [11, 36, 37], are
specifically designed to discover the most optimal architecture for a given
task.

Figure 2: Results of a naive conversion from a single objective to a multi-
objective NAS with two objectives: maximize representation similarity and
minimizing device latency. It fails to identify the best architecture within
the search space. The architecture search is performed in the search space,
NAS-Bench-201 [10] on CIFAR10 dataset. More details about the search space are
given in Section 4.1.

The rise in the utilization of edge devices, characterized by low energy
consumption, necessitated adaptations to NAS algorithms to incorporate
performance considerations from the particular hardware being employed. These
customized NAS algorithms are referred to as Hardware-aware Neural
Architecture Search (HW-NAS) [1, 2]. While NAS focuses on finding the optimal
architecture for a specific task, HW-NAS aims to find architectures with
minimal trade-offs between task performance and targeted hardware cost.
However, HW-NAS algorithms face a bottleneck due to the extensive time
required for evaluating the architecture performance metrics within the search
space [22, 37]. This challenge has led to the development of methods that
utilize a supernet-based solution [17, 3, 4], treating all architectures in
the search space as sub-networks of the supernet. While employing this
strategy reduces computational cost, it compromises architecture search
performance due to inaccurate performance estimations by the supernet.

To address the mentioned challenge, [30] has recently proposed the use of a
representation similarity metric [15, 35], which significantly reduced the
search cost while finding the best matching architecture under a single
hardware cost constraint. This was achieved by using the single objective of
maximizing the representation similarity metric with respect to a reference
model, while penalizing the search whenever the given architecture constraint
is not satisfied (illustrated in Figure 1). However, if multiple different
constraints need to be satisfied, the search cost adds up as the algorithm
must run multiple times to fulfill each one. Additionally, the naive
conversion of the single objective method of [30] to a multi-objective one
with two objectives (_i.e_. maximizing representation similarity metric and
minimizing hardware cost) fails to identify the best architecture. In this
regard, Figure 2 illustrates the hardware costs, measured in terms of device
latency, of the set of architectures discovered after performing the multi-
objective architecture search. It is evident from the figure that the
architectures discovered through the architecture search do not exhibit
similar performance (test accuracy) to the best architecture found within the
search space. This failure is attributed to the high hardware cost of the best
architecture, contradicting the second objective aimed at minimizing hardware
costs. Note that best architecture in the figure refers to the architecture
with the highest accuracy in the search space.

Figure 3: A depiction of the accuracy (y-axis) of all architectures against
their respective hardware costs measured in terms of latency (x-axis), in a
population size of 5. As the value of diversity increases, the architectures
in the population exhibit a spread in hardware costs along the latency axis.

To address these challenges, we propose a Multi-Objective method to address
HW-NAS called Multi-Objective Hardware Aware Neural Architecture Search using
Hardware Cost Diversity (MO-HDNAS). Our approach aims to identify a set of
high-performing architectures with diverse hardware costs in a single run. It
achieves this goal by optimizing three objectives (illustrasted in Figure 1):
(1) Maximizing the representation similarity metric. (2) Minimizing hardware
cost. (3) Maximizing hardware cost diversity. Our contributions can be
summarized as follows:

  * •

We generalize the single objective HW-NAS framework proposed in [30] to a
multi-objective one in order to address the issue of increased search cost
when multiple hardware cost constraints are present.

  * •

We propose a hardware cost diversity term aimed at encouraging the
consideration of architectures with diverse hardware costs. This allows the
search algorithm to explore architectures with higher hardware costs, as high-
performing architectures typically tend to have higher hardware cost
requirements.

  * •

The robustness of the proposed method is demonstrated on six different edge
devices for classification tasks.

##  2 Related Works

Any NAS method, as described in [12], consists of three key components: search
space, search strategy, and performance estimation. The search space generally
outlines the potential architectures that can be theoretically represented.
Performance estimation involves assessing the expected performance of a neural
architecture for a specified task. The search strategy dictates the approach
used to explore the defined search space, utilizing architecture performance
estimation to find the optimal architecture. It involves techniques such as
reinforcement learning (RL)-based methods [37, 21], evolutionary algorithm
(EA)-based methods [22, 26, 27, 28, 29], and gradient-based methods [17, 34].

Hardware-aware NAS (HW-NAS) is a specialized version of NAS aimed at
identifying the optimal architecture tailored for a specific task and target
device. HW-NAS typically involves addressing multiple objectives, such as
maximizing the architecture performance metric while minimizing the associated
hardware cost for the target hardware [1].

Addressing the challenge of multiple objectives can be pursued through two
distinct approaches [2]. The first method entails converting the multiple
objective problem into a single objective one and solving the latter instead.
This can be achieved via rejection sampling [3], which eliminates any
architecture that fails to meet the hardware cost constraint during the search
process. However, rejection sampling is susceptible to the halting problem, as
indicated by [30], particularly when it rejects all candidate architectures
for failing to meet a low hardware cost constraint. An alternative solution to
rejection sampling involves employing a penalty term that reduces the
performance metric of an architecture whenever it does not satisfy the
hardware cost constraint. Yet, this latter solution suffers from high
computational cost. Specifically, when multiple hardware constraints are
present, the same single objective problem has to be solved multiple times to
accommodate all hardware constraints. The second method to address multiple
objectives in HW-NAS employs techniques to identify the pareto optimal
solutions [32, 6]. Pareto optimal solutions are those that cannot be improved
in one objective without compromising at least one other objective. For
instance, improving the accuracy of an architecture may require increasing
network parameters, thereby elevating the hardware cost. The pareto approach
effectively tackles the elevated search cost issue linked to the single-
objective relaxation. Hence, it will be exploited in this work as it provides
a set of architectures (pareto optimal set) in a single run, in contrast to
multiple runs required by the single objective approach. Our method also
ensures that these architectures have diverse hardware costs. This stands in
contrast to previous multi-objective methods [32, 6], where the diversity of
architecture hardware cost was not considered as one of the objectives.

##  3 Proposed Method

###  3.1 Search Method

Our proposed architecture search method employs a meta-heuristic optimization
technique falling under the category of genetic algorithms [14]. These
algorithms have demonstrated their effectiveness in addressing the NAS problem
[26, 28, 27, 30]. They mimic biological adaptation to find optimal solutions
in non-differentiable spaces. Starting with an initial population of random
neural network architectures, the algorithm iteratively updates/evolves the
population, ensuring that the new population $\mathcal{P}$ consists of better
performing architectures as compared to previous one. After running the
algorithm for a certain number of iterations/generations, the best
architecture in the current population is returned as the final solution.

To solve the multi-objective problem of HW-NAS, we employed a popular variant
of the genetic algorithm called NSGA-II [8]. It is a well-known Pareto-based
Multi-objective Evolutionary Algorithm (MOEA), where selection of individuals
is based on Pareto Efficiency. In this context, a solution that outperforms
others in all objectives is termed “non-dominated”. Conversely, one that is
inferior to others in at least one objective is consistently labeled as
“dominated”. During the selection phase, solutions undergo a sorting process
using non-dominated sorting and crowding distance. This technique has been
previously employed in the NAS [18, 28] literature, offering a suitable
solution for optimizing a neural network architecture based on various
objectives.

###  3.2 Problem Formulation

Let $\alpha^{*}$ denote a pre-trained reference model with a desired
performance metric (_e.g_. accuracy for classification task). Also, let
$\mathcal{A}$ be the architecture search space in which NAS is performed with
$\alpha$ denoting an architecture in the search space. Further, let $\Psi(.)$
denote the function that measures the hardware cost (_e.g_. latency).
Formally, the multi-objective hardware-aware architecture search problem can
be written as:

$\displaystyle\max_{\alpha\in\mathcal{A}}\quad$
$\displaystyle\phi(\alpha^{*},\alpha),$ $\displaystyle\min\quad$
$\displaystyle\Psi(\alpha),$ (1) $\displaystyle\max\quad$
$\displaystyle\chi(\alpha,\mathcal{P}).$

This formulation involves solving for three objectives, including:

  1. 1.

Maximizing performance similarity metric, $\phi(\alpha^{*},\alpha)$: Finding
an architecture $\alpha$ in the search space with similar performance to the
reference model $\alpha^{*}$. More specifically, the performance similarity
metric calculates the mutual information between hidden layer representation
of an architecture and that of the reference model. In other words,

$\displaystyle\phi(\alpha^{*},\alpha)=\sum_{i=1}^{L}I(X^{i*},X^{i}),$ (2)

where $X^{1*},X^{2*},..,X^{L*}$ and $X^{1},X^{2},..,X^{L}$ represent the
random variables of feature maps in each layer of $\alpha^{*}$ and $\alpha$,
respectively. More details are available in [30, 35].

  2. 2.

Minimizing hardware cost, $\Psi(\alpha)$: Finding an architecture $\alpha$
with minimum hardware cost.

  3. 3.

Maximizing hardware cost diversity, $\chi(\alpha,\mathcal{P})$: Maximizing the
diversity of the architecture $\alpha$ in terms of the hardware cost, _i.e_.
$\chi(\Psi(\alpha,\mathcal{P}))$, as will be discussed in Section 3.3. Note
that $\mathcal{P}$ refers to the current generation population of
architectures.

###  3.3 Hardware Cost Diversity

For the current generation population $\mathcal{P}$, the hardware cost
diversity term for each architecture $\alpha$ is calculated as

$\displaystyle\chi(\alpha,\mathcal{P})=\sum_{\alpha^{\dagger}\in\mathcal{P}}(\Psi(\alpha)-\Psi(\alpha^{\dagger}))^{2}.$
(3)

This formulation measures the difference between the hardware cost of a given
architecture $\alpha$, and those of the remaining architectures
$\alpha^{\dagger}$ in the given population $\mathcal{P}$. Maximizing this term
leads to a population characterized by architectures with diverse hardware
costs. This is illustrated in Figure 3 which plots the hardware costs of
architectures in a population of size five and the impact of the diversity
term. This allowed the discovery of architectures with lower latency that
preserve the same level of accuracy.

To measure the diversity of the population, we introduce a term called
population diversity, $\bar{\chi}(\mathcal{P})$, formalized as

$\displaystyle\bar{\chi}(\mathcal{P})=\frac{1}{N}\sum_{\alpha\in\mathcal{P}}\chi(\alpha,\mathcal{P}),$
(4)

where $N$ is the population size. It is worth mentioning that
$\bar{\chi}(\mathcal{P})$ measures the average hardware cost diversity of
architectures within the population.

The leftmost plot in Figure 3 shows the population of architectures with the
same hardware cost, consequently resulting in the population diversity term
being zero. As we progress to the right on the plots in the figure, we observe
an increase in the population diversity term. This ensures that the search
algorithm explores the architecture search space, encompassing architectures
with varying hardware costs. Please note that the hardware cost used in Figure
3 represents latency. However, the proposed method is agnostic to the specific
type of hardware cost utilized for the architecture search.

Input: Reference model $\alpha*$, Search space $\mathcal{A}$, Total
generations $N_{gen}$, Population size $N_{pop}$, training epochs $N_{train}$

Output: Pareto optimal front of architectures, $P_{optimal}$

1 $\mathcal{P}\leftarrow$ Initialize population for NSGA-II algorithm;

2 $g\leftarrow 0$ (Initialize the generation counter);

3 $archive\leftarrow$ Initialize to empty set;

4 while  _ $g\leq N_{gen}$ _ do

5 for  _each individual architecture ( $\alpha$) in $\mathcal{P}$_ do

6 $F_{rs}\leftarrow\phi(\alpha^{*},\alpha)$ (using Equation 2);

7 $F_{hw}\leftarrow\Psi(\alpha)$ ;

8 $F_{div}\leftarrow\chi(\alpha,\mathcal{P})$ (using Equation 3);

9

10 end for

11 UpdateArchive($\mathcal{P}$, $archive$);

12 $g\leftarrow g+1$;

13 $\mathcal{P}\leftarrow$ NSGA-II($F_{rs}$, $F_{hw}$, $F_{div}$);

14

15 end while

Algorithm 1 MO-HDNAS Figure 4: Results of MO-HDNAS for 6 different edge
devices performed with only 3 objectives: maximize representation similarity,
minimizing device latency and maximizing the hardware cost diversity. (a),
(b), (c) show the results for image classification task on CIFAR10, CIFAR100
and ImageNet16-120 respectively.

###  3.4 MO-HDNAS

The pseudo-code of the proposed MO-HDNAS is presented in Algorithm 1. It
begins by initializing a population $\mathcal{P}$ consisting of $N_{pop}$
architectures randomly sampled from $\mathcal{A}$. MO-HDNAS iterates for
$N_{gen}$ generations. During each generation, the performance of every
architecture $\alpha$ ($F_{rs}$) in the current population, in terms of
similarity to reference model, is evaluated in line 1 using Equation 2. Next,
hardware cost $F_{hw}$ and hardware cost diversity $F_{div}$ of the
architectures are calculated in lines 1, 1 respectively. Then, the archive is
updated in line 1 to include the new architectures from the current
population. Finally, NSGA-II is used to generate the next generation
population in line 1. MO-HDNAS returns a pareto optimal front of architectures
$P_{optimal}$ (_i.e_. set of possible neural architecture solutions) after
$N_{gen}$ generations.

##  4 Experiments

We adopt the architecture representation introduced in [26] and conduct the
architecture search using a single NVIDIA RTX A4000 GPU, with a population
size ($N_{pop}$) set to 20. Following [35], we employ ResNet-20 as the
reference model. The representation similarity score is calculated in
accordance to the procedure outlined in [30] and the architecture search is
performed for 100 generations ($N_{gen}$).

Further details on the experiments, such as the search space and datasets are
presented in Section 4.1 and Section 4.2, respectively. Section 4.3 reports
the architecture search performance for six different edge devices,
considering various hardware cost settings for each. Finally, an ablation
study is performed on the hardware cost diversity objective in Section 4.4.

###  4.1 Search Space

The effectiveness of the proposed method is demonstrated on the NAS-Bench-201
[10] benchmark search space. It provides a unified benchmark for fair
comparison of NAS algorithms by providing the results on CIFAR-10, CIFAR-100
and ImageNet16-120 for image classification task. Given that any NAS algorithm
aims to search for the type of the operation present between two nodes in a
neural architecture, the search space of NAS-Bench-201 includes convolution
3x3, convolution 1x1, max pooling 3x3, skip connection, and none. Note that
none indicates the absence of any operation between the two nodes.
Nevertheless, NAS-Bench-201 lacks information about the hardware cost
associated with its architectures. Consequently, we utilize the HW-NAS-Bench
[16] benchmark. It is an extension of NAS-Bench-201, containing various
hardware costs for all architectures in its search space across six edge
devices including, NVIDIA Edge GPU Jetson TX2, Raspberry Pi 4, Edge TPU, Pixel
3, ASIC-Eyeriss, and FPGA.

Figure 5: Comparison of architecture search results for FPGA on CIFAR-100
dataset between HW-EvRSNAS [30] and MO-HDNAS.

| Search cost
---|---
Methods | (GPU hours)
HW-EvRSNAS [30] | $20.87$
MO-HDNAS (Ours) | $0.65$

Table 1: Search cost comparison of architecture search results for FPGA on
CIFAR-100 dataset between HW-EvRSNAS [30] and our method.

Figure 6: The average hardware costs diversity across different generation
population for (a) two objectives (b) three objectives. Note that the search
was conducted for the FPGA device using the CIFAR-10 dataset. The x-axis
represents the architecture latency on FPGA, while the y-axis depicts the test
accuracy of the architecture on CIFAR-10.

###  4.2 Datasets

We test the effectiveness of the proposed method on three different datasets:
CIFAR-10, CIFAR-100, and ImageNet-16-120. CIFAR-10 consists of 50,000 train
and 10,000 test images, categorized into 10 classes. As for the CIFAR-100, the
number of images in the train and test sets are the same as CIFAR-10, but
instead coming from 100 classes. On the other hand, the ImageNet-16-120 [5] is
a modified version of ImageNet containing 120 out of the 1000 total labels,
and with each image being downsampled to $16\times 16$ pixels.

###  4.3 Results

Architecture search results obtained by the proposed MO-HDNAS method are shown
in Figure 4. It shows the pareto fronts for the multi-objective architecture
search performed on six different edge devices and their hardware cost
measured in terms of latency. It is observed that the architectures present in
the pareto front of MO-HDNAS are closer to the best architecture. Notably, the
pareto front contains architectures with diverse latencies.

To further evaluate the effectiveness of our proposed method, we compare our
architecture search results with those of HW-EvRSNAS [30], which treats the
HW-NAS problem as a single objective optimization (Figure 1). Results are
illustrated in Figure 5, presenting the pareto front discovered by MO-HDNAS
and the architecture search results of HW-EvRSNAS under nine different
hardware cost constraints. Note that these results are obtained for the image
classification task on the CIFAR100 dataset using FPGA. From the figure, it is
evident that our method is able to identify a more diverse set of high-
performing architectures, ranging from those with low latency to those with
high latency.

Furthermore, We compare the search cost of our method with that of HW-EvRSNAS
[30] in Table 1. Search costs are reported in terms of GPU hours, indicating
the number of hours each method spent to perform the architecture search on a
single GPU. These results demonstrate that our method finds the pareto set of
architectures at a search cost that is $32\times$ lower than that of HW-
EvRSNAS. This is attributed to the fact that HW-EvRSNAS requires nine separate
runs to find the optimal architecture for nine different hardware cost
constraints. In contrast, our method finds the pareto set of 20 architectures
in just a single run.

###  4.4 Ablation Study

To illustrate the influence of the third objective in the Eq 3.2 (_i.e_.
maximizing hardware cost diversity $\chi(\alpha,\mathcal{P})$), we visualize
the population diversity, $\bar{\chi}(\mathcal{P})$, of 6 different
generations (1, 10, 30, 50, 70, 100) in Figure 6. $\bar{\chi}(\mathcal{P})$
measures the average hardware cost diversity for a generation, as showcased in
Equation 4. It is computed by taking the average of the
$\chi(\alpha,\mathcal{P})$ term across all architectures within that
generation’s population. Figure 6(a) illustrates the progression of the
population diversity term across generations when the objective of maximizing
hardware cost diversity is not applied in Equation 3.2 (_i.e_. only the first
two objectives employed). In this case, we observe a decline in population
diversity as generations progress. This results in architectures within the
population being inclined towards regions with high accuracy and lower
hardware costs. Consequently, it hinders the discovery of the best
architecture within the search area characterized by high hardware cost.

On the other hand, Figure 6(b) shows the progression of the population
diversity term across generations when all three objectives in Equation 3.2
are utilized in the search process. In this scenario, we observe an increase
in population diversity as generation advances. Hence, architectures within
the population exhibit diverse hardware costs, spanning from low to high
latencies. This enhances the explorability of the search process, facilitating
the discovery of high-performing architectures within regions characterized by
high hardware cost.

##  5 Conclusion

In this work, we presented a multi-objective hardware aware neural
architecture search method, which performs the architecture search with
reduced computational cost. This is achieved by searching for architectures
with similar internal representation to a reference model, and simultaneously,
with minimum hardware cost. Additionally, we introduced a third search
objective, hardware cost diversity, to facilitate a better exploration of the
architecture search space. The effectiveness of the proposed method is
demonstrated on six edge devices for image classification task on three
different datasets.

##  6 Acknowledgement

This work is supported by the Luxembourg National Research Fund (FNR), under
the project reference C21/IS/15965298/ELITE.

## References

  * Benmeziane et al. [2021a] Hadjer Benmeziane, Kaoutar El Maghraoui, Hamza Ouarnoughi, Smail Niar, Martin Wistuba, and Naigang Wang.  Hardware-aware neural architecture search: Survey and taxonomy.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pages 4322–4329. International Joint Conferences on Artificial Intelligence Organization, 2021a.  Survey Track.
  * Benmeziane et al. [2021b] Hadjer Benmeziane, Kaoutar El Maghraoui, Hamza Ouarnoughi, Smail Niar, Martin Wistuba, and Naigang Wang.  A comprehensive survey on hardware-aware neural architecture search.  _arXiv preprint arXiv:2101.09336_ , 2021b.
  * Cai et al. [2019a] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han.  Once-for-all: Train one network and specialize it for efficient deployment.  _arXiv preprint arXiv:1908.09791_ , 2019a.
  * Cai et al. [2019b] Han Cai, Ligeng Zhu, and Song Han.  ProxylessNAS: direct neural architecture search on target task and hardware.  In _International Conference on Learning Representations_ , 2019b.
  * Chrabaszcz et al. [2017] Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter.  A downsampled variant of imagenet as an alternative to the cifar datasets.  _arXiv preprint arXiv:1707.08819_ , 2017.
  * Chu et al. [2020] Xiangxiang Chu, Bo Zhang, and Ruijun Xu.  Multi-objective reinforced evolution in mobile neural architecture search.  In _European Conference on Computer Vision_ , pages 99–113. Springer, 2020.
  * Collobert et al. [2011] Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa.  Natural language processing (almost) from scratch.  _Journal of machine learning research_ , 12(ARTICLE):2493–2537, 2011.
  * Deb et al. [2002] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  _IEEE transactions on evolutionary computation_ , 6(2):182–197, 2002.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dong and Yang [2020] Xuanyi Dong and Yi Yang.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  In _International Conference on Learning Representations_ , 2020.
  * Elsken et al. [2018] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter.  Neural architecture search: A survey.  _arXiv preprint arXiv:1808.05377_ , 2018.
  * Elsken et al. [2019] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al.  Neural architecture search: A survey.  _J. Mach. Learn. Res._ , 20(55):1–21, 2019.
  * Garcia et al. [2021] Albert Garcia, Mohamed Adel Musallam, Vincent Gaudilliere, Enjie Ghorbel, Kassem Al Ismaeil, Marcos Perez, and Djamila Aouada.  Lspnet: A 2d localization-oriented spacecraft pose estimation neural network.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2048–2056, 2021.
  * Goldberg [2013] David E Goldberg.  _Genetic algorithms_.  pearson education India, 2013.
  * Kornblith et al. [2019] Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton.  Similarity of neural network representations revisited.  In _International conference on machine learning_ , pages 3519–3529. PMLR, 2019.
  * Li et al. [2021] Chaojian Li, Zhongzhi Yu, Yonggan Fu, Yongan Zhang, Yang Zhao, Haoran You, Qixuan Yu, Yue Wang, and Yingyan (Celine) Lin.  {HW}-{nas}-bench: Hardware-aware neural architecture search benchmark.  In _International Conference on Learning Representations_ , 2021.
  * Liu et al. [2019] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  DARTS: Differentiable architecture search.  In _International Conference on Learning Representations_ , 2019.
  * Lu et al. [2019] Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf.  Nsga-net: neural architecture search using multi-objective genetic algorithm.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , pages 419–427, 2019.
  * Musallam et al. [2021] Mohamed Adel Musallam, Vincent Gaudilliere, Enjie Ghorbel, Kassem Al Ismaeil, Marcos Damian Perez, Michel Poucet, and Djamila Aouada.  Spacecraft recognition leveraging knowledge of space environment: Simulator, dataset, competition design and analysis.  In _2021 IEEE International Conference on Image Processing Challenges (ICIPC)_ , pages 11–15, 2021.
  * Perez et al. [2021] Marcos Perez, Mohamed Adel Mohamed Ali, Albert Garcia Sanchez, Enjie Ghorbel, Kassem Al Ismaeil, Paul Le Henaff, and Djamila Aouada.  Detection & identification of on-orbit objects using machine learning.  In _European Conference on Space Debris_ , 2021.
  * Pham et al. [2018] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean.  Efficient neural architecture search via parameters sharing.  In _Proceedings of the 35th International Conference on Machine Learning_ , pages 4095–4104, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
  * Real et al. [2019] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 4780–4789, 2019.
  * Rostami et al. [2022] Peyman Rostami, Hojatollah Zamani, Mohammad Fakharzadeh, Arash Amini, and Farokh Marvasti.  A deep learning approach for reconstruction in millimeter-wave imaging systems.  _IEEE Transactions on Antennas and Propagation_ , 71(1):1180–1184, 2022.
  * Sermanet et al. [2013] Pierre Sermanet, David Eigen, Xiang Zhang, Michaël Mathieu, Rob Fergus, and Yann LeCun.  Overfeat: Integrated recognition, localization and detection using convolutional networks.  _arXiv preprint arXiv:1312.6229_ , 2013.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Sinha and Chen [2021] Nilotpal Sinha and Kuan-Wen Chen.  Evolving neural architecture using one shot model.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , pages 910–918, 2021.
  * Sinha and Chen [2022a] Nilotpal Sinha and Kuan-Wen Chen.  Neural architecture search using progressive evolution.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , pages 1093–1101, 2022a.
  * Sinha and Chen [2022b] Nilotpal Sinha and Kuan-Wen Chen.  Novelty driven evolutionary neural architecture search.  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , pages 671–674, 2022b.
  * Sinha and Chen [2023] Nilotpal Sinha and Kuan-Wen Chen.  Neural Architecture Search Using Covariance Matrix Adaptation Evolution Strategy.  _Evolutionary Computation_ , pages 1–28, 2023.
  * Sinha et al. [2024] Nilotpal Sinha, Abd El Rahman Shabayek, Anis Kacem, Peyman Rostami, Carl Shneider, and Djamila Aouada.  Hardware aware evolutionary neural architecture search using representation similarity metric.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 2628–2637, 2024.
  * Wu et al. [2016] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ , 2016.
  * Ying et al. [2020] Weiqin Ying, Kaijie Zheng, Yu Wu, Junhui Li, and Xin Xu.  Neural architecture search using multi-objective evolutionary algorithm based on decomposition.  In _Artificial Intelligence Algorithms and Applications: 11th International Symposium, ISICA 2019, Guangzhou, China, November 16–17, 2019, Revised Selected Papers 11_ , pages 143–154. Springer, 2020.
  * Zamani et al. [2021] Hojatollah Zamani, Peyman Rostami, Arash Amini, and Farokh Marvasti.  Elliptical shape recovery from blurred pixels using deep learning.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 2775–2779. IEEE, 2021.
  * Zela et al. [2020] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter.  Understanding and robustifying differentiable architecture search.  In _International Conference on Learning Representations_ , 2020.
  * Zheng et al. [2022] Xiawu Zheng, Xiang Fei, Lei Zhang, Chenglin Wu, Fei Chao, Jianzhuang Liu, Wei Zeng, Yonghong Tian, and Rongrong Ji.  Neural architecture search with representation mutual information.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11912–11921, 2022.
  * Zoph and Le [2017] Barret Zoph and Quoc Le.  Neural architecture search with reinforcement learning.  In _International Conference on Learning Representations_ , 2017.
  * Zoph et al. [2018] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 8697–8710, 2018.