# Federated Geometric Monte Carlo Clustering to Counter Non-IID Datasets

Federico Lucchetti1, Maria Fernandes2, Lydia Y. Chen3, Jérémie Decouchant3,
Marcus Völp1  1SnT - University of Luxembourg, 2WHG - University of Oxford,
3Delft University of Technology,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Federated learning allows clients to collaboratively train models on datasets
that are acquired in different locations and that cannot be exchanged because
of their size or regulations. Such collected data is increasingly non-
independent and non-identically distributed (non-IID), negatively affecting
training accuracy. Previous works tried to mitigate the effects of non-IID
datasets on training accuracy, focusing mainly on non-IID labels, however
practical datasets often also contain non-IID features. To address both non-
IID labels and features, we propose FedGMCC111 Code and genome dataset
available at: https://figshare.com/s/dc2f4280ce012e12f414 , a novel framework
where a central server aggregates client models that it can cluster together.
FedGMCC clustering relies on a Monte Carlo procedure that samples the output
space of client models, infers their position in the weight space on a loss
manifold and computes their geometric connection via an affine curve
parametrization. FedGMCC aggregates connected models along their path
connectivity to produce a richer global model, incorporating knowledge of all
connected client models. FedGMCC outperforms FedAvg and FedProx in terms of
convergence rates on the EMNIST62 and a genomic sequence classification
datasets (by up to +63%). FedGMCC yields an improved accuracy (+4$\%$) on the
genomic dataset with respect to CFL, in high non-IID feature space settings
and label incongruency.

##  I Introduction

Federated learning (FL) frameworks [1, 2] are commonly used when regulations
(such as the GDPR222https://gdpr.eu/) or mere data volume prevent data
exchanges. Datasets are distributed across the members (clients) of the
federation and the global machine learning optimization problem can
approximately be split up into smaller sub-problems that are distributed
across independently acting clients. Client solutions are aggregated either by
a central server or in a distributed manner. However, this approximation only
holds in an idealised settings where client datasets are sampled from the same
distribution and data samples form independent events. Deviating from
independent and identically distributed datasets (IID) poses a challenge to
most FL approaches and results in global models that fail to accurately
represent the entire aggregated dataset [3, 4, 5, 6]. Sources of non-IID-ness
can be found in both the label space and the feature space. In the former, for
a given feature, different labels might be attributed due to regional
differences (e.g., different sentiments in fashion). This is also termed
concept shift and leads ultimately to clients with incongruent labelling
participating to the training of a common FL model. In addition, classes may
be imbalanced due to one class of labels being over-represented with respect
to others. This paper focuses on the latter, i.e., _feature space IID
violations_. They appear for example when a particular feature is over-
represented in a member’s dataset compared to other datasets. A biobank might
sample genes that bias towards a particular local population [7] with the
consequence of possibly overlooking regional differences, such as the well
known preponderance of a specific gene mutation coding for sickle cell disease
in the Sub-Saharan Africa population [8]. For a given label, features might
also vary across datasets, such as different handwriting styles for the same
alphanumeric character (e.g., 7 with and without bar). Non-IID-ness may lead
to feature and label skew [3] and accuracy degradation [4, 6, 9] by leaving
the choice between starting from different initialization weights, causing
models to diverge, or accepting diversity suppression when starting from the
same weights [5].

Besides statistical heterogeneity, FL algorithms need to cope with system
heterogeneity, leading to asynchronous model updates or incomplete local
training. The first proposed FL attempt, FedAvg [1], aggregates all client
models by averaging their weights, leading to the above inaccuracies in the
presence of non-IID-ness. Variations [6, 10] of FedAvg have been proposed,
with satisfactory results when the non-IID-ness is less pronounced and
exclusively in the label space (see Sec. II). Federated Clustering [11, 12,
13, 14] tackles this problem by assigning clients to separate clusters and
hence limiting the deleterious transfers of negative knowledge between member
models that have been trained on distinct datasets. These approaches result in
the construction of trained models with reasonable accuracy despite IID
violations, however, at the cost of significant communication and/or
computational overheads.

In this paper, focusing on non-IID-ness in the feature space, we propose a
novel Monte Carlo Clustering approach, called FedGMCC, to counter non-IID-ness
without compromising final model accuracy and while maintaining low
communication costs and data privacy. We show that in order to train a global
FL model in a non-IID setting, the objective function to be minimized has to
be conceptually split up into two components: the first encompasses the IID
component for which the usual FedAvg solution holds; the second captures the
non-IID contribution, which we show can be solved by introducing _interaction_
between client models. We derive this interaction by leveraging an observation
about the geometry of training loss manifolds [15, 16, 17, 18], namely that
seemingly different, stationary solutions to the training loss minimization
problem, obtained at the individual member sites, are often connected via
simple parametric curves where the training loss is approximately flat. The
existence of these curves reveals the pair-wise interaction between models
needed to solve the non-IID problem, which leads us to establish a criterion
for clustering seemingly different solutions and suppressing negative
knowledge transfer between non-connected ones. More importantly, we show that
drawing from [19], averaging models along the curve parametrization, can
produce global models with enhanced accuracy and generalization. As a summary,
we make the following contributions.

  1. 1.

We separate the FL objective in an IID and a non-IID components and, based on
the geometry of curved training loss manifolds, put forward an Ansatz solution
that simultaneously minimizes both components.

  2. 2.

We demonstrate how to construct this solution using a Monte Carlo sampling of
the received client model output spaces, and present novel model weight
clustering and aggregation rules.

  3. 3.

We evaluate FedGMCC using the EMNIST62 dataset and a genomic dataset with
different non-IID-ness. FedGMCC always outperforms FedAvg [1] and FedProx [6].
It outperforms CFL [13] in case of high non-IID-ness.

##  II Related Work

Among the myriad of published FL algorithms, most of them rely on clients to
upload model weight updates onto a central server that proceeds to aggregate
them and to redistribute the result back to clients. The main difference often
relies in the way the aggregation rule is applied. FedAvg [1] was first to
allow clients to train a global model locally, instead of transferring data.
FedAvg returns to a central server only for aggregating all local models by
averaging their weights. FedProx [6] inhibits local updates, by adding a
proximal term to the loss function, which restrains divergence between local
and global model weights. FedBn [10] achieves accurate results on non-IID
datasets by batch normalizing the local neural networks’ input layer before
aggregation. FedFV [20] detects inconsistent gradient updates and corrects
them before the aggregation step. Our approach (FedGMCC) aggregates models by
averaging weights along their geometric connection.

Federated clustering groups certain client models into separate clusters to
prevent negative knowledge transfer such as the iterative federated clustering
algorithm (IFCA) [11] which solves an incongruency that occurs when non-IID
datasets exhibit concept shifts by training multiple models on local data and
returning the one with the lowest aggregation loss. However, these works
primarily focus on label-space non-IID-ness, leading to inaccurate results in
the presence of feature-space non-IID-ness. Moreover, training multiple models
induce high communication and computation costs.

Merging local models with approximately the same weights (according to cosine
similarity, L1 or L2 norm) reduces the number of models in the ensemble [12,
13]. For example, clustered FL (CFL) [13] merges models if their weights (or
gradients) compare well enough based on a specified metric. Again CFL focuses
on label non-IID-ness. In contrast, FedGMCC explicitly considers feature-space
non-IID-ness. Among the aforementioned FL approaches, CFL is the most
reminiscent to our approach, with two differences. First in CFL, the central
server applies clustering after multiple FedAvg iterations whereas FedGMCC
clusters after each client-server communicating round. Second, CFL’s
clustering rule relies on measuring whether the gradients of individual
client-weight models are coherent (parallel) via the cosine similarity
measure. Our approach verifies that a parallel transport of one client model
weights to the other is feasible. Hence, FedGMCC extends CFL’s gradient
coherency measure to include intermediary models along the affine connection.

##  III Problem Description

We consider $K$ clients that aim to locally minimize a local objective
$\mathcal{L}_{k}{=}\mathcal{L}(\operatorname{\mathbf{X}}_{k},\operatorname{\mathbf{w}})$.
Clients send their respective solutions (client model weights)
$\operatorname{\mathbf{w}}_{k}^{*}{=}\arg\min_{\operatorname{\mathbf{w}}}\mathcal{L}_{k}$
to a central server to approximate with aggregate
$\operatorname{\mathbf{w}}_{t}^{f}$ a global solution for the loss
minimization problem
$\operatorname{\mathbf{w}}^{*}{=}\arg\min_{\operatorname{\mathbf{w}}}\mathcal{L}(\operatorname{\mathbf{x}},\operatorname{\mathbf{w}})$,
which maps the $C$ classes of the compact input space $\mathcal{X}$ into the
label space $\mathcal{Y}=[\mathbf{C}]$, where $[\mathbf{C}]={1,...,C}$. We
consider the neural network as a function
$f(\operatorname{\mathbf{w}}):\mathcal{X}\mapsto\mathcal{S}$, parametrized by
weights $\operatorname{\mathbf{w}}$, that maps $\operatorname{\mathbf{X}}$ to
the probability simplex
$\mathcal{S}{=}\left\\{\mathbf{z}|\sum_{i=1}^{C}z_{i}=1,z_{i}\geq 0,\forall
i\in[\mathbf{C}]\right\\}$. We write $f_{i}$ for the probability of the $i$-th
class and define the population loss
$\mathcal{L}(\operatorname{\mathbf{X}}_{k},\operatorname{\mathbf{w}}_{k})$ at
federation member $k$ as the cross-entropy loss
$\mathcal{L}(\operatorname{\mathbf{X}}_{k},\operatorname{\mathbf{w}}){=}\frac{1}{N}\sum_{x_{i}\in\operatorname{\mathbf{X}}}\sum_{j=1}^{C}p(y{=}j)\operatorname{\mathbb{E}_{\operatorname{\mathbf{x}}|y=i}}\left[\log
f_{j}(x_{i},\operatorname{\mathbf{w}}_{k})\right]$.

In an IID setting, the optimization problem minimizing $\mathcal{L}_{IID}$ can
be expressed as $K$ sub-problems that train local models via stochastic
gradient descent (SGD), which are then communicated to a server for
aggregation after each communication round (indexed by $t$):

$\mathcal{L}_{IID}=\sum_{k=1}^{K}\frac{n_{k}}{n}\mathcal{L}(\operatorname{\mathbf{X}}_{k},\operatorname{\mathbf{w}})=\mathbb{E}_{\operatorname{\mathbf{X}}_{k}}(\mathcal{L}(\operatorname{\mathbf{X}}_{k},\operatorname{\mathbf{w}}))$
(1)

FedAvg [1] makes use of the weighted averaging aggregation function
$\operatorname{\mathbf{w}}_{t}^{f}=\sum_{k}^{K}\frac{n_{k}}{n}\operatorname{\mathbf{w}}_{t,k}^{*}$,
where $\frac{n_{k}}{n}$ is the fraction of the $k$-th member’s local dataset
with repect to the overall dataset size. Unfortunately, in a non-IID setting,
this aggregation is not a valid approximation.

We follow [5] in quantifying non-IID-ness with the help of the Earth Mover
Distance (EMD) [21] and write $d(\mathcal{D}_{1},...,\mathcal{D}_{K})$ for the
EMD of $K$ distributions $\mathcal{D}_{1},...,\mathcal{D}_{K}$ obtained by
averaging the set of pairwise EMDs (cf. Apx. A).

Weighted averaging fails as an aggregation function under non-IID datasets [5]
because: (1) if weights in client models are all initialized identically, the
label-space non-IID-ness between client dataset distributions will be the
dominant factor and weights will diverge; and (2) if weights are initialized
differently, client models risk converging to different solutions 333Without a
formal proof,a third contribution term to weight divergence could be added in
terms of feature-space non-iid. The steepness of local loss function pockets
in relation to the local flatness of the loss manifold exacerbates the
divergence after aggregation and hence leads to sub-optimal global model
performance [22], which we address with Geometric Monte Carlo Clustering.

##  IV Geometric Monte Carlo Clustering

In a non-IID setting, individual client models are set to converge during
training towards distinct local minima, i.e., different coordinates in weight
space on the training loss manifold (see Fig. 1). In particular, when the non-
IID-ness lies exclusively in the feature space between two client datasets
$\\{\operatorname{\mathbf{X}}_{1},\operatorname{\mathbf{y}}_{1}\\}$ and
$\\{\operatorname{\mathbf{X}}_{2},\operatorname{\mathbf{y}}_{2}\\}$, we
hypothesize the existence of a continuous transformation $\mathcal{T}$ (e.g.
pixel rotation, color inversion, shape distortion, etc.) that maps, on
average, one subset of features
$\operatorname{\mathbf{X}}_{1}^{\prime}{\in}\operatorname{\mathbf{X}}_{1}$
detained by one client to a subset of features
$\operatorname{\mathbf{X}}_{2}^{\prime}{\in}\operatorname{\mathbf{X}}_{2}$ of
a different client
$\mathcal{T}{:}\operatorname{\mathbf{X}}_{1}{\rightarrow}\operatorname{\mathbf{X}}_{2}$.
As a consequence, we suppose that the model weights of one client are trained
to encode a set of transformed features with respect to another client. Hence
we hypothesize the existence of a continuous transformation $\Gamma$ that maps
one subset of weights to another one
$\Gamma:\operatorname{\mathbf{w}}^{\prime}_{1}\subseteq\operatorname{\mathbf{w}}_{1}\rightarrow\operatorname{\mathbf{w}}^{\prime}_{1}\subseteq\operatorname{\mathbf{w}}_{1}$
and that can alternatively be modeled by a continuous affine connection via a
curve parametrization $\gamma_{\theta}(u)$. This curve connects
$\operatorname{\mathbf{w}}_{1}$ and $\operatorname{\mathbf{w}}_{2}$ (with
$\gamma_{\theta}(0){=}\operatorname{\mathbf{w}}_{1}$ and
$\gamma_{\theta}(1){=}\operatorname{\mathbf{w}}_{2}$) ideally on a loss
surface where the loss value does not vary. That is, two neural nets
parametrized by $\operatorname{\mathbf{w}}_{1}$ and
$\operatorname{\mathbf{w}}_{2}$ agree on the output space given the same
input. Along this curve of invariant loss reside a family of intermediary
model weights that can be aggregated to produce a richer global model,
incorporating the knowledge of both client models. In contrast, under label-
space IID violations, particularly concept shifts, we expect no continuous
curve to be found (e.g. between $\operatorname{\mathbf{w}}_{3}$ and
$\operatorname{\mathbf{w}}_{4}$ on Fig. 1) since they disagree on the
classification of a same input feature. In this case, a well constructed
clustering rule should separate both models to avoid negative knowledge
transfer. This curve finding is at the heart of our novel Federated Geometric
Monte Carlo Clustering algorithm (FedGMCC).

Figure 1: Schematatization of the Geometric Monte Carlo Clustering applied on
4 trained clienz models where 1 and 2 have a feature space based IID, 3 and 4
have a label space concept shift based non-IID. Curved line connects
$\operatorname{\mathbf{w}}_{1}$ to $\operatorname{\mathbf{w}}_{2}$ where the
loss remains minimally low. No curve is found between
$\operatorname{\mathbf{w}}_{3}$ to $\operatorname{\mathbf{w}}_{4}$ where the
loss crossed the $\epsilon$ budget. Note that because of the curved loss
surface, the standard FedAvg aggregation
$\operatorname{\mathbf{w}}_{AVG}=0.5\cdot(\operatorname{\mathbf{w}}_{1}+\operatorname{\mathbf{w}}_{2})$
would lead to a suboptimal model (high loss).

###  IV-A Prerequisites

Key to FedGMCC is the treatment of non-IID datasets as perturbations of
probability distributions $\mathcal{D}_{k}$ from the ideal IID baseline
$\mathcal{D}$, where $\mathcal{D}_{k}\mapsto\mathcal{D}{+}\delta_{k}$ and
$d(\mathcal{D}_{k},\mathcal{D}){\neq}0$. Datasets that originally had
overlapping feature and label representations have, after perturbation, a
component that contributes to their non-IID-ness. Let us denote as
$\\{\operatorname{\mathbf{X}}_{k}^{U},\operatorname{\mathbf{y}}_{k}^{U}\\}$
the labeled dataset drawn from the distribution $\mathcal{D}_{k}^{U}$ such
that $\forall k{\neq}l,d(\mathcal{D}_{k}^{U},\mathcal{D}_{l}^{U}){=}0$ and as
$\\{\operatorname{\mathbf{X}}_{k}^{\delta},\operatorname{\mathbf{y}}_{k}^{\delta}\\}$
the datasets drawn from $\mathcal{D}_{k}^{\delta}$ such that $\forall
k{\neq}l,d(\mathcal{D}_{k}^{\delta},\mathcal{D}_{l}^{\delta})\neq 0$, where
$\\{\operatorname{\mathbf{X}}_{k}^{U},\operatorname{\mathbf{y}}_{k}^{U}\\}\cup\\{\operatorname{\mathbf{X}}_{k}^{\delta},\operatorname{\mathbf{y}}_{k}^{\delta}\\}=\\{\operatorname{\mathbf{X}}_{k}^{\prime},\operatorname{\mathbf{y}}_{k}^{\prime}\\}$.
The training objective is:

$\begin{array}[]{l}\sum_{k}^{K}\mathcal{L}(\tilde{\operatorname{\mathbf{X}}}_{k},\operatorname{\mathbf{w}})\\\
\qquad\approx\sum_{k}^{K}\mathcal{L}(\operatorname{\mathbf{X}}_{k}^{U},\operatorname{\mathbf{w}})+\sum_{k<l}^{K}\mathcal{L}(\operatorname{\mathbf{X}}_{k}^{\delta}\cup\operatorname{\mathbf{X}}_{l}^{\delta},\gamma_{k,l})\\\
\qquad=\mathcal{L}_{IID}+\mathcal{L}_{INT}\end{array}$ (2)

$\mathcal{L}_{IID}$ is the usual IID loss function (see Eq. 1). The _pairwise
interaction loss_ $\mathcal{L}_{INT}$ captures the training loss on a pair of
non-IID distributions. We use the solutions $\operatorname{\mathbf{w}}_{k}$ to
the pure IID objective to approximate the solution to
$\min_{\operatorname{\mathbf{w}}}\mathcal{L}_{INT}$.

###  IV-B Curve Finding

We intuit the solution to the minimization of Eq. 2 to be of the form
$\operatorname{\mathbf{w}}{=}(1-u)\operatorname{\mathbf{w}}^{f}+u\operatorname{\bm{\theta}}_{k,l}$
where $\operatorname{\bm{\theta}}_{k,l}$ introduces a pairwise _interaction_
between two client model weights and balances its contribution to the total
solution with a coupling constant $u{\in}[0,1]$. As we have already hinted in
the previous section on the possibility of connecting distinct model weights
via a transformation, we propose to model this interaction as an affine
connection between weights $\operatorname{\mathbf{w}}_{k}$ and
$\operatorname{\mathbf{w}}_{l}$ by a smooth curve
$\gamma_{\operatorname{\bm{\theta}}}(u){:}[0,1]{\mapsto}\mathcal{M}$ on the
loss function manifold $\mathcal{M}$ of dimension $|net|$ equal to the number
of parameters of the neural net and parametrized by
$\operatorname{\bm{\theta}}{\in}\mathbb{R}^{|net|}$. We need to find the
transport parameter $\operatorname{\bm{\theta}}$ that leaves the gradient of
the second term in Eq. 2 parallel for every $u{\in}[0,1]$. This amounts to
solving the geodesic equation
$\partial_{u}\nabla_{\operatorname{\bm{\theta}}}\mathcal{L}(\operatorname{\mathbf{X}}_{k}^{\delta}\cup\operatorname{\mathbf{X}}_{l}^{\delta},\gamma_{\operatorname{\bm{\theta}}}(u)){=}0$
with boundary conditions
$\gamma_{\operatorname{\bm{\theta}}}(0){=}\operatorname{\mathbf{w}}_{k}$ and
$\gamma_{\operatorname{\bm{\theta}}}(1){=}\operatorname{\mathbf{w}}_{l}$.
Ideally, the central server, which detains the individual client model
weights, should execute the curve finding procedure after every local update.
However, since the central server does not have access to the datasets in
order to explore the loss manifold, we sample a surrogate version of the
latter by generating a Monte Carlo type input dataset drawn from a uniform
distribution $\operatorname{\mathbf{X}}_{MC}\sim U(0,1)$ to reconstruct the
loss from the label-space output
$f(\operatorname{\mathbf{X}}_{MC},\operatorname{\mathbf{w}}_{k})$, using mean-
squared error (MSE) as loss function, since we merely compare raw outputs. The
curve is then derived by perturbing the parameter $\operatorname{\bm{\theta}}$
in the direction where the loss
$\mathcal{L}_{MSE}(\operatorname{\mathbf{w}}_{l},\gamma_{\operatorname{\bm{\theta}}}(u))$
does not vary. We rely on a polygonal chain as Ansatz, as it has been proven
to lead to optimal curve finding results [15].

$\gamma_{\operatorname{\bm{\theta}}}(u)=\begin{cases}2(u\operatorname{\bm{\theta}}+(0.5-u)\operatorname{\mathbf{w}}_{k})&u\in[0,0.5[\\\
2((u-0.5)\operatorname{\mathbf{w}}_{l})+(1-u)\operatorname{\bm{\theta}}&u\in[0.5,1]\\\
\end{cases}$ (3)

Following [15], we simplify the loss to be minimized to the expectation of
$\mathcal{L}_{MSE}(\operatorname{\mathbf{w}}_{l},\gamma_{\operatorname{\bm{\theta}}}(u))$
with respect to uniform distribution on the curve on $u\in[0,1]$, making the
loss computationally tractable.

$\begin{array}[]{l}\nabla_{\operatorname{\bm{\theta}}}\int_{0}^{1}\mathcal{L}_{MSE}(\operatorname{\mathbf{w}}_{l},\gamma_{\operatorname{\bm{\theta}}}(u))du=\\\
\qquad\qquad\nabla_{\operatorname{\bm{\theta}}}\mathbb{E}_{u\sim
U(0,1)}\mathcal{L}_{MSE}(\operatorname{\mathbf{w}}_{l},\gamma_{\operatorname{\bm{\theta}}}(u))\end{array}$
(4)

###  IV-C Model Weights Clustering and Aggregation

Garipov et. al [15] showed that two models initialized differently and trained
on the same dataset can be connected via a simple curve. Two models trained
independently on distributed datasets with only partially overlapping features
are also expected to converge to different stationary solutions. Nevertheless,
we expect these seemingly different solutions to be interlinked via an affine
connection in weight space i.e a smooth curve can be constructed that along a
approximately flat loss manifold. Hence, seeminly different solution form a
family of equivalent solutions to the loss minimization problem which leads us
to put forward the following clustering rule.

Proposition 1.1 $\operatorname{\mathbf{X}}_{MC}\sim U(0,1)$, two models with
weights $\operatorname{\mathbf{w}}_{k}$ and $\operatorname{\mathbf{w}}_{l}$
belong to the same cluster $\mathcal{S}$ if there exists a
$\operatorname{\bm{\theta}}\in\mathbb{R}^{|net|}$ that parametrizes the curve
$\gamma_{\operatorname{\bm{\theta}}}:u\in[0,1]\mapsto\mathbb{R}^{|net|}$ and
$\epsilon\geq 0$ such that

$\partial_{u}\mathbb{E}_{x\in\operatorname{\mathbf{X}}_{MC}}\Arrowvert
f(x,\operatorname{\mathbf{w}}_{l})-f(x,\gamma_{\operatorname{\bm{\theta}}}(u))\Arrowvert^{2}<\epsilon$
(5)

Because $\gamma_{\operatorname{\bm{\theta}}}(u)$ generates a family of
intermediary model weights, all approximate solutions to the optimization
problem (see Eq. 2), their sum must also be a solution. [19] showed that
averaging intermediary model weights on the constructed curve
$\gamma_{\operatorname{\bm{\theta}}}(t)$ along $t$ can lead to an aggregated
model with improved generalization.

Proposition 1.2 Model weights $\operatorname{\mathbf{w}}_{j}$ belonging to the
same cluster $\mathcal{S}_{j}$ are aggregated with

$\operatorname{\mathbf{w}}_{j}=\sum_{k,l\in\mathcal{S}_{j}}\mathbb{E}_{u\in[0,1]}\gamma_{\operatorname{\bm{\theta}}_{k,l}}(u)$
(6)

###  IV-D Algorithm

FedGMCC is described in Alg. 1 and schematized in Fig. 1. The server samples
the output space of each received client model by generating a Monte Carlo
input dataset and tests via Prop. 1.1 whether two models can be grouped
together. This procedure can be seen as a disjoint-set query in which model
weights that could not be connected to any other model weights are kept as
singleton sets (e.g.,
$\\{\operatorname{\mathbf{w}}_{1},\operatorname{\mathbf{w}}_{2}\\},\\{\operatorname{\mathbf{w}}_{3}\\},\\{\operatorname{\mathbf{w}}_{4}\\}$
on Fig. 1). With $M$ disjoint sets, the weights that belong to a same cluster
$\mathcal{S}_{j}$ are aggregated by averaging all pairwise interactions
leading to $M$ clustered global solutions to the non-IID problem (see
Proposition 1.2). $\operatorname{\mathbf{w}}_{j}$ is then sent to the clients
that contributed to it.

Algorithm 1 Geometric Monte Carlo Clustering

1:Parameters: $\epsilon>0$; $n$: Monte Carlo sample size; $K$: number of
client models; $M$: number of clusters; $\eta$: learning rate

2:Initialization: Random input dataset $\operatorname{\mathbf{X}}\leftarrow$
Uniform$(0,1,n)$

3:Server:
ModelClustering$(\operatorname{\mathbf{w}}_{1},...,\operatorname{\mathbf{w}}_{K})$:

4: clusters $\mathcal{S}\leftarrow\\{\\}$

5: for $k\in 1,...,K$, $l\in k+1,...,K$ do

6: if
$(\\{\operatorname{\mathbf{w}}_{k},\operatorname{\mathbf{w}}_{l}\\}\in\mathcal{S}_{j\leq
k})$ continue

7: else

8:
$\operatorname{\bm{\theta}}_{k,l}\leftarrow$Update$(\operatorname{\mathbf{w}}_{k},\operatorname{\mathbf{w}}_{l})$

9: if $(\operatorname{\bm{\theta}}_{k,l})$
$\mathcal{S}_{j}\leftarrow\mathcal{S}_{j}\\{\operatorname{\mathbf{w}}_{k},\operatorname{\bm{\theta}}_{k,l}\\}$

10:
$\operatorname{\mathbf{w}}_{1},...,\operatorname{\mathbf{w}}_{M}\leftarrow$
Aggregation$(\mathcal{S})$

11: Distribute
$\operatorname{\mathbf{w}}_{1},...,\operatorname{\mathbf{w}}_{M}$

12:Update$(\operatorname{\mathbf{w}}_{1},\operatorname{\mathbf{w}}_{2})$:

13:
$\operatorname{\bm{\theta}}\leftarrow\operatorname{\mathbf{w}}_{1}+\operatorname{\mathbf{w}}_{2}$

14: for $u\in U(0,1)$, $x\in\operatorname{\mathbf{X}}_{MC}$ do

15:
$\mathcal{L}(x,\operatorname{\mathbf{w}}_{2},\gamma_{\operatorname{\bm{\theta}}}(u))\leftarrow\Arrowvert
f(x,\operatorname{\mathbf{w}}_{2})-f(x,\gamma_{\operatorname{\bm{\theta}}}(u))\Arrowvert^{2}$

16:
$\operatorname{\bm{\theta}}_{u+1}\leftarrow\operatorname{\bm{\theta}}_{u}-\eta\nabla_{\operatorname{\bm{\theta}}}\mathcal{L}(x,\operatorname{\mathbf{w}}_{2},\gamma_{\operatorname{\bm{\theta}}}(u))$

17: if
$(\max_{u}\partial_{u}\mathbb{E}_{x\in\operatorname{\mathbf{X}}_{MC}}\mathcal{L}\leq\epsilon)$
return $\operatorname{\bm{\theta}}$

18:Aggregation$(\mathcal{S}_{1,..,M})$:

19: for $S_{j}\in S$ do
$\\{\operatorname{\mathbf{w}}_{j}\leftarrow\sum_{k,l\in\mathcal{S}_{j}}\mathbb{E}_{u\in
U(0,1)}\gamma_{\operatorname{\bm{\theta}}_{k,l}}(u)\\}$

20: return $\operatorname{\mathbf{w}}_{1},...,\operatorname{\mathbf{w}}_{M}$

21:Distribute$(\operatorname{\mathbf{w}}_{1},...,\operatorname{\mathbf{w}}_{M})$:

22: for $S_{j}\in S$, $k\in 1,...,K$ do

23: if $(k\in S_{j})$ send $\operatorname{\mathbf{w}}_{j}$ to client $k$

##  V Evaluation

To evaluate our approach, we show that real-life data is in fact non-IID in
the feature space and compare the accuracy of our approach — Federated
Geometric Monte-Carlo Clustering (FedGMCC) — against state-of-the art
federated learning approaches (FedAVG [1], FedProx [6], CFL [13] and standard
SGD). We leverage the well known image dataset EMNIST62 [23] and two
sequential genomic datasets (SENSG-A and SENSG-R) we created (see Appx. B).
EMNIST62 contains 814255 handwritten characters, labeled as 62 unbalanced
classes in 28x28 pixel format. The genomic dataset contains reads (i.e.,
sequences of the bases A, T, C, G) of size 150 and every position is labelled
according to whether or not it is part of a genomic variation. Such labelling
is important, for example, to filter out and protect private information in
the genomic information processing pipeline [24]. We introduce a concept shift
in SENSG-R by randomly flipping the label of the most recurrent genomic
features. EMNSIT62 and SENSG-A were distributed among $K$ clients following
the procedure detailed in Appx. B. This partitioning introduces non-IID-ness
in the feature space but also in the label space because certain classes might
be over-represented in some client datasets compared to others. The genomic
dataset SENSG-R is naturally partitioned using the populations of individuals
(Asian, European, African). In addition, we partition both sets artificially
into 10 client datasets to consider a wider range of non-IID-ness. Models were
trained on an AMD Ryzen7 3700x system with 8 3.6 GHz cores, a NVIDIA Geforce
RTX 3090 GPU with 10496 CUDA cores and 24 GB of GDDR6X memory. We used the
binary-cross entropy loss function for the training of all classifiers and
Tensorflow 2.6 [25].

###  V-A Network Architecture and Baselines

We construct two neural network architectures for the benchmarks: for
EMNIST62, we use 2 stacked CNN layers, activated by ReLu, and followed by a
fully connected neural network. The genomic datasets are classified with a
network comprised of 2 stacked bidirectional LSTMs that feed into a densely
connected neural network. We compare our approach FedGMCC against three
federated learning methods: FedAvg [1], FedProx [6] and CFL [13]. We assume a
federation of $K=10$ members for all experiments, each solving its local
optimization problem using SGD. FedAvg performs weighted average aggregation
in the central server after each local training round, which is performed on
the member datasets. FedProx [6] corrects FedAvg’s loss function by the
proximal term
$\mu\|\operatorname{\mathbf{w}}-\operatorname{\mathbf{w}}_{t}\|^{2}$, where
$\mu$ is a positive constant, $\operatorname{\mathbf{w}}$ the weights of the
most recent global model and $\operatorname{\mathbf{w}}_{t}$ the weights of
the local model at training step $t$. We implement CFL by following the
procedure laid out in [13]. With FedAvg the central server receives,
aggregates and distributes client updates until the average of received client
gradients decreases below $\epsilon_{1}=0.2$. FedGMCC applies the clustering,
aggregation and distribution scheme laid out in Alg. 1. In the first round,
the value of $\epsilon$ was set to the median value of the $\frac{1}{2}K(K-1)$
training losses associated with the curve finding procedure. This value is
subject to a 5 percentile increase if the number of clusters was higher than 1
and a 5 percentile decreases otherwise. The learning rate $\eta$ in the curve
finding procedure was set to 0.1. In addition, we train two central models
($cSDG_{0}$ and $cSDG_{1}$) on the combined genomic dataset using standard SGD
as baselines. Training of two models is necessary due to the concept shift we
introduce in SENSG-A. As usual, we separate the whole dataset into disjoint
training (80%) and validation sets (20%). Hyperparameters have been fine-tuned
for every training algorithm to give best possible results in terms of
convergence rate. The mini-batch size was set to 64, and learning rates were
set to 0.001. Local epoch numbers were respectively set to 10 and 5 for the
EMNIST62 and SENSG-A datasets.

Figure 2: The 10 client averaged train loss as along the curve
$\gamma_{\operatorname{\bm{\theta}}}(u)$ connecting two client models as a
function of multiple experimental setting (EMD, local epochs, datasets) and
curve parameters (type, Monte Carlo sample size $n_{MC}$). Dispersion
represents the standard deviation scaled down by a factor of 10.

###  V-B Results

Curve Fitting between Local Models: Fig. 2 shows the average training loss for
our curve-fitting approach for different parameters and setups. The top graph
compares a naive linear curve
$\gamma(t)=u\operatorname{\mathbf{w}}_{1}+(1-u)\operatorname{\mathbf{w}}_{2}$
with a polygonal one-bend chain curve (see 3). Using the latter we were able
to find a region of low loss and hence prove the existence of multiple simple
connections between pairs of client models, i.e., pairs of client models
belonging to the same cluster. Note that by setting $u=0.5$, the linear
parametrization reduces to the classical FedAvg aggregated model
$\operatorname{\mathbf{w}}_{1}+\operatorname{\mathbf{w}}_{2}$ situated in a
region of higher loss with respect to the chain curve loss
$\gamma_{\operatorname{\bm{\theta}}}(u=0.5)$. When clients train local models
with varying local epoch numbers (middle left) or EMD values (middle right)
the average loss is directly affected. When the number of local epochs is
decreased or the data distribution setting tends towards the ideal IID
setting, the GMCC losses flatten out and the inter-client variability
decreases. This is an important finding that could previously only be obtained
when computing loss surface manifold with real datasets. Our approach achieves
this on a generated dataset using Monte Carlo sampling. More interestingly,
increasing the sample size of the GMCC input dataset makes it easier to find
connections between client model weights with low training losses. For
EMNIST62, where no concept shift was present (bottom left), finding an optimal
curve parametrization is only a matter of increasing computational costs (due
to increased GMCC sample sizes). On the other hand, for the genomic datasets,
because the concept-shift introduced an incongruency in the output space
between two models, no amount of GMCC sample size will be able to connect
models hence leading to the splitting of client models into separate clusters.
We validate our approach, where the server substitutes the client datasets by
a surrogate Monte Carlo type generated dataset.

Figure 3: Validation loss for FedAvg, FedProx, CFL and FedGMCCfor three
different EMD values.

Loss: Fig. 3 reports the loss of the FL models for varying EMD values and for
the EMNIST62 and genomic datasets. Loss is computed on the validation set
after every communication round. For CFL and FedGMCC, where the aggregation
can lead to multiple models, the average loss is shown. We highlight the
increasing difficulty for FL models to converge when the EMD increases. As
expected, FedAvg shows the worst results for both datasets. FedProx is able to
deal with high EMD values in the EMNIST62 dataset but does not converge to a
lower loss value at high EMD compared to the FL clustering algorithms (CLF and
FedGMCC). The latter are able to cluster dissimilar models and avoid negative
transfer of knowledge between them, which allows them to obtain the two
aggregated final models with optimal loss.

Accuracy: For the EMNIST62 dataset the FL algorithms achieved a similar
performance with low EMD values than the one obtained in the centralized
setting (85$\%$) (see Table I). However, their accuracy degrades quickly when
the EMD increases, with values for FedAVG that dropped from 0.81 at EMD 17.1
to 0.43 at EMD 48.9. This drop was less pronounced for FedProx, CFL and
FedGMCC. The two latter maintained a 0.79 accuracy at high EMD. The situation
was different for the genomic datasets. The centralized SGD models cSGD0 and
cSGD1 achieved a 0.88 accuracy. CFL and FedGMCC attained comparable 0.85
accuracy, while FedProx and FedAvg respectively obtained 0.71 and 0.75 at low
EMD. As expected, FedAvg’s performance dramatically degraded at high EMD to
0.18. The drop in accuracy was less severe for FedProx and stayed around 0.79.
FedGMCC led to two global models, each of which maintained an accuracy of 0.85
at EMD 17.1 and 0.84 at higher EMD values. This high performance was also
achieved by CFL but FedGMCC yielded a better accuracy at high EMD. This is not
surprising because of CFL’s and FedGMCC’s aggregation rules, which enable them
to create multiple personalized models to accommodate a certain degree of IID-
ness in particular the incongruency due to the concept shift injected in the
genomic dataset.

TABLE I: FL algorithms accuracies in different EMD settings. Pair of values
for CFL and FedGMCC indicate accuracies associated to the final weight
clusters. EMNIST62
---
EMD | FedAvg | FedProx | CFL | FedGMCC
17.1 | 0.81 | 0.83 | 0.83 | 0.83
27.1 | 0.76 | 0.83 | 0.83 | 0.83
48.9 | 0.43 | 0.71 | 0.79 | 0.79
GENOMIC
EMD | FedAvg | FedProx | CFL | FedGMCC
6.2 (real) | 0.88 | 0.89 | 0.91 | 0.93
10.5 | 0.88 | 0.91 |  0.93$\mid$ 0.92 |  0.93$\mid$0.93
20.6 | 0.56 | 0.70 |  0.80$\mid$0.79 |  0.84$\mid$0.83
26.3 | 0.21 | 0.65 |  0.80$\mid$0.79 |  0.84$\mid$0.83

##  VI Conclusion

We presented FedGMCC, a federated learning framework that consists of novel
clustering rules and a new aggregation procedure. Substituting real datasets
by a surrogate Monte Carlo dataset, we show how the curve finding procure can
reveal the geometric connection between congruent models serving as a
clustering rule of client model weights. Furthermore, FedGMCC aggregation rule
averages all the intermediary model weights on the curve parametrization,
leading to better generalization and extending the classical FedAvg
aggregation rule to weight spaces of curves training loss manifold.

FedGMCC outperformed other FL training algorithms on the EMNSIT62 and genomic
sequence sensitivity classification tasks where we controlled the non-IID-ness
using an artificial partitioning technique and the EMD measure. In high non-
IID setting FedGMCC yielded convergence rates respectively 36% and 8% faster
than those of FedAvg and FedProx on EMNSIT62. FedGMCC outperformed FedAvg,
FedProx and CFL on the genomic datasets by 63$\%$, 19$\%$ and 4 $\%$.

## References

  * [1] H. McMahan, Eider Moore, Daniel Ramage and Blaise Agüera Arcas  “Federated Learning of Deep Networks using Model Averaging”  In _CoRR_ abs/1602.05629, 2016  arXiv: http://arxiv.org/abs/1602.05629
  * [2] He Yang  “H-FL: A Hierarchical Communication-Efficient and Privacy-Protected Architecture for Federated Learning”  In _Proc. of 13th Int. Conf. on Artificial Intelligence, IJCAI, Montreal, Canada, 19-27 August_ , 2021, pp. 479–485  DOI: 10.24963/ijcai.2021/67
  * [3] Peter Kairouz, H Brendan McMahan and Brendan Avent  “Advances and open problems in federated learning”  In _arXiv:1912.04977_ , 2019
  * [4] Kevin Hsieh, Amar Phanishayee, Onur Mutlu and Phillip Gibbons  “The non-iid data quagmire of decentralized machine learning”  In _Int. Conf. on Machine Learning_ , 2020, pp. 4387–4398  PMLR
  * [5] Yue Zhao et al.  “Federated learning with non-iid data”  In _arXiv preprint arXiv:1806.00582_ , 2018
  * [6] Tian Li et al.  “Federated Optimization in Heterogeneous Networks”  In _Proc. of Machine Learning and Systems (MLSys), Austin, TX, USA, March 2-4_ , 2020  URL: https://proceedings.mlsys.org/book/316.pdf
  * [7] Jeroen GJ Rooij, Mila Jhamai and Pascal P Arp  “Population-specific genetic variation in large sequencing data sets: why more data is still better”  In _Eu. J. of Human Genetics_ 25.10 Nature Publishing Group, 2017, pp. 1173–1175
  * [8] Thomas N Williams  “Sickle cell disease in sub-Saharan Africa”  In _Hematology/Oncology Clinics_ 30.2 Elsevier, 2016, pp. 343–358
  * [9] Qinbin Li, Yiqun Diao, Quan Chen and Bingsheng He  “Federated learning on non-iid data silos: An experimental study”  In _arXiv preprint arXiv:2102.02079_ , 2021
  * [10] Xiaoxiao Li et al.  “Fedbn: Federated learning on non-iid features via local batch normalization”  In _arXiv preprint arXiv:2102.07623_ , 2021
  * [11] Avishek Ghosh, Jichan Chung, Dong Yin and Kannan Ramchandran  “An efficient framework for clustered federated learning”  In _34th Conf. on Neural Information Processing Systems (NeurIPS)_ , 2020
  * [12] Christopher Briggs, Zhong Fan and Peter Andras  “Federated learning with hierarchical clustering of local updates to improve training on non-IID data”  In _IEEE Int. Conf. on Neural Networks (IJCNN 2020)_ , pp. 1–9
  * [13] Felix Sattler, Klaus-Robert Müller and Wojciech Samek  “Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints”  In _IEEE T. on neural net. and learning sys._ IEEE, 2020
  * [14] Kavya Kopparapu and Eric Lin  “Fedfmc: Sequential efficient federated learning on non-iid data”  In _arXiv preprint arXiv:2006.10937_ , 2020
  * [15] Timur Garipov et al.  “Loss surfaces, mode connectivity, and fast ensembling of dnns”  In _Proc. of the 32nd Int. Conf. on Neural Information Processing Systems_ , 2018, pp. 8803–8812
  * [16] C. Freeman and Joan Bruna  “Topology and Geometry of Half-Rectified Network Optimization”  In _5th Int. Conf. on Learning Representations, (ICLR), Toulon, France, April 24-26_ , 2017  URL: https://openreview.net/forum?id=Bk0FWVcgx
  * [17] Seyed Iman Mirzadeh et al.  “Linear mode connectivity in multitask and continual learning”  In _arXiv preprint arXiv:2010.04495_ , 2020
  * [18] Anna Choromanska et al.  “The loss surfaces of multilayer networks”  In _Artificial intelligence and statistics_ , 2015, pp. 192–204  PMLR
  * [19] Pavel Izmailov et al.  “Averaging weights leads to wider optima and better generalization”  In _Conf. on Uncertainty in Artificial Intelligence, Monterey, CA, USA_ , 2018
  * [20] Zheng Wang et al.  “Federated Learning with Fair Averaging”  In _Proc. of 13th Int. Conf. on Artificial Intelligence, IJCAI, Montreal, Canada, 19-27 August_ , 2021, pp. 1615–1623
  * [21] Yossi Rubner, Carlo Tomasi and Leonidas J Guibas  “A metric for distributions with applications to image databases”  In _6th Int. Conf. on Comp. Vision (IEEE Cat. No. 98CH36271)_ , 1998, pp. 59–66
  * [22] Nitish Shirish Keskar et al.  “On large-batch training for deep learning: Generalization gap and sharp minima”  In _arXiv preprint arXiv:1609.04836_ , 2016
  * [23] Gregory Cohen, Saeed Afshar, Jonathan Tapson and Andre Van Schaik  “EMNIST: Extending MNIST to handwritten letters”  In _Int. Conf. on Neural Networks (IJCNN)_ , 2017  DOI: 10.1109/ijcnn.2017.7966217
  * [24] Jérémie Decouchant et al.  “Accurate filtering of privacy-sensitive information in raw genomic data”  In _J. of Biomed. Informatics_ 82, 2018, pp. 1–12
  * [25] Martín Abadi et al.  “Tensorflow: A system for large-scale machine learning”  In _12th USENIX Symp. on Operating Systems Design and Implementation (OSDI 16)_ , 2016, pp. 265–283

##  Appendix A Earth Mover Distance

TABLE II: Parameters and network configuration for autoencoders to accelerate EMD computation. Training progressed at a rate of $0.01$ for EMNIST62 and with $0.001$ for the different genomic datasets. We trained in batches of size $128$. | Encoder Layers | dim(features) | Decoder layers | Learning rate | Reconstruction loss
---|---|---|---|---|---
EMNIST62 | 4 x CNN | 7x7x2 | 4 x TransCNN | 0.01 | $\leq 0.0001\%$
SENSG-* | 2 x CNN + 2 x LSTM | 30x1 | 2 x LSTM + 2xTransCNN | 0.001 | $\leq 0.0001\%$

Earth Mover Distance (EMD) is defined as a distance metric between two
distributions $\mathcal{A}$ and $\mathcal{B}$. It computes the minimal
distance for mapping all clusters of distribution $\mathcal{A}$ (set of
suppliers) to any cluster of distribution $\mathcal{B}$ (set of consumers).
The distributions are thereby characterized by signatures
$\mathcal{A}=\\{(p_{1},w_{p_{1}}),...,(p_{m},w_{p_{m}})\\}$ and likewise
$\mathcal{B}=\\{(q_{1},w_{q_{1}}),...,(q_{n},w_{q_{n}})\\}$, where clusters
are represented as bin centroids $p_{i}$ with weight $w_{p_{i}}$ (and $q_{j}$
with weight $w_{q_{i}}$, respectively). The overall cost for transferring all
clusters from $\mathcal{A}$ to $\mathcal{B}$ is:

$C=\sum_{i\in\mathcal{A}}\sum_{j\in\mathcal{B}}c_{ij}f_{ij}$ (7)

where $c_{ij}$ is the ground distance between the supports $p_{i}$ and $q_{j}$
and $f_{ij}$ is the flow between $p_{i}$ and $q_{j}$ that needs to be
minimized under the constraints:

  1. 1.

$f_{ij}\geq 0$ (unidirectional flow),

  2. 2.

$\sum_{(p_{i},w_{i})\in\mathcal{A}}f_{ij}\leq q_{j}$ (limited consumer
storage),

  3. 3.

$\sum_{(q_{j},w_{j})\in\mathcal{B}}f_{ij}\leq p_{i}$ (limited supply), and

  4. 4.

$\sum_{(p_{i},w_{i})\in\mathcal{A}}\
\sum_{(q_{j},w_{j})\in\mathcal{B}}f_{ij}=\sum_{(p_{i},w_{i})\in\mathcal{A}}w_{i}=\sum_{(q_{j},w_{j})\in\mathcal{B}}w_{j}$
(transfer all).

With optimal flow $f^{*}=\arg\min_{f}(C)$, EMD for a pair of distributions
follows as:

$d(\mathcal{A},\mathcal{B})=\frac{\sum_{i\in\mathcal{A}}\sum_{j\in\mathcal{B}}c_{ij}f_{ij}^{*}}{\sum_{i\in\mathcal{A}}\sum_{j\in\mathcal{B}}f_{ij}^{*}}$
(8)

We extend $d(\mathcal{A},\mathcal{B})$ to a set of $K$ distributions
$\\{\mathcal{D}_{1},...,\mathcal{D}_{K}\\}$ by averaging the set of pairwise
EMDs between the $k$-th distribution $\mathcal{D}_{k}$ and the distribution
over the whole population $\mathcal{D}$ $\mathcal{D}_{k}$, using

$d(\mathcal{D}_{1},...,\mathcal{D}_{K})=\frac{1}{N}\sum_{k=1}^{K}n_{k}d(\mathcal{D}_{k},\mathcal{D})$
(9)

where $n_{k}$ is the sample size of the dataset generated by distribution
$\mathcal{D}_{k}$, $N$ is the total population size and
$\mathcal{D}=\frac{1}{N}\sum_{k}^{K}n_{k}\mathcal{D}_{k}$. In the context
where $\mathcal{D}_{k}$ models a labeled dataset with $C$ classes, the joint
probability distribution is factorized in terms of its conditional and
marginal probability distribution
$\mathcal{D}_{k}=p_{k}(\operatorname{\mathbf{X}},\operatorname{\mathbf{y}})=\\{p_{k}(y=i,\operatorname{\mathbf{X}})\cdot
p_{k}(\operatorname{\mathbf{X}})\\}$ for $i=1,...,C$, i.e, the EMD is computed
over all the classes for a given feature $\operatorname{\mathbf{X}}$.

To accelerate EMD computation we reduce datasets to their essentials by
training autoencoders using a SGD optimizer and mean square error as
reconstruction loss function. Table II shows the parameters for the
autoencoders for the two benchmarks we used to evaluate our approach.

##  Appendix B Datasets

###  B-A Image Datasets

EMNIST62 444https://colab.research.google.com/drive/1r-c6UTkJEQx3Pi-
Hl9q_MoveIF_0h03M is an image dataset for simulating non-IID image
classification [23]. It comprises a set of 814255 handwritten alpha-numeric
characters, labeled as 62 unbalanced classes, formatted in 28x28 pixel images.

###  B-B Genomic Datasets

We used two different genomic datasets: SENSG-R and SENSG-S.
SENSG-R is composed of 7 500 000 reads from four randomly selected genomes
from each of the three major populations represented in the 1000 Genomes
Project (1000GP) 555https://www.internationalgenome.org/: African, European
and Asian(see Table III). With this we intend to resemble the natural
representation one would obtain when sampling in regions where these
populations are dominant.
SENSG-S is composed of one million reads generated from twenty individual
genomes ($10^{5}$ reads for each genome) and the randomly selected individuals
are the following: HG00096, HG00097, HG00099, HG00100, HG00101, HG00102,
HG00103, HG00105, HG00106, HG00107, NA21128, NA21129, NA21130, NA21133,
NA21135, NA21137, NA21141, NA21142, NA21143, and NA21144.

TABLE III: Genomes used per population dataset. ASIA | AFRI | EURO
---|---|---
HG00543 | HG02703 | HG00315
HG00559 | HG02769 | HG00327
HG00566 | HG02715 | HG00334
HG00578 | HG02771 | HG00339
HG00581 | HG02722 | HG00341
HG00580 | HG02676 | HG00346
HG00593 | HG02808 | HG00353
HG00598 | HG02810 | HG00358
HG00592 | HG02614 | HG00360
HG00613 | HG02839 | HG00365

For generating these datasets, we follow three steps:
Step 1 - Genomic sequence generation:  We compiled the chromosome 1 sequence
of each individual selected by combining the human reference genome GRCh37 and
the individual’s variants in the 1000 GP. Second, we randomly select positions
in the sequence to use as seed for obtaining 150 character sequences (reads),
comprised of the nucleotides A, T, G, and C. Reads constitute the first
digitized information obtained from next generation sequencing machines, which
are subsequently processed to extract variations (i.e., what distinguishes us
one from another and what might carry sensitive information, like, disease
prepositions). Therefore, genomic data is a practical example where data is
generated in multiple geo-distributed locations, e.g., hospitals in different
continents, and it must not be shared among different locations for privacy
reasons.
Step 2 – Labeling: We labeled each nucleotide by deeming it as sensitive if a
genomic variation reported in the 1000 GP or insensitive otherwise,
respectively, 1 or 0. For SENSG-S only, we simulate a concept shift by
flipping some labels manually in order to obtain non-IID-ness.
Step 3 – Reads encoding: Next, we used word2vect encoding to convert the
genomic sequence in a vector. After, this step the reads are ready to be used
for the training. In this step we consider a vocabulary (word size) of 5
letters and we generated all the consecutive 5 nucleotides sequences of each
read.

###  B-C Artificial Partitioning

SENSG-A and EMNIST62 are partitioned artificially into $K$ subsets using our
iterative clustering and distribution algorithm, which we describe in the
following. We first apply $k$-mean clustering to divide the dataset into $K$
subsets with maximal EMD. Then, computing the center of gravity (COG) of all
subsets, we randomly select elements from the farthest subset $D_{i}$ and
assign them to other subsets $D_{j}$. This reduces the inter-subset distance
$d(D_{i},D_{j})$ and hence the overall EMD. We retain the current partition if
pairwise EMD values ($d(D_{i},D_{j})$) are normally distributed (according to
the Shapiro normality test). We repeat this process until a we found a
partition with a total EMD value that is low enough.


# Measuring the Transferability of Adversarial Examples

Deyan V. Petrov  Timothy M. Hospedales

###### Abstract

Adversarial examples are of wide concern due to their impact on the
reliability of contemporary machine learning systems. Effective adversarial
examples are mostly found via white-box attacks. However, in some cases they
can be transferred across models, thus enabling them to attack black-box
models. In this work we evaluate the transferability of three adversarial
attacks - the Fast Gradient Sign Method, the Basic Iterative Method, and the
Carlini & Wagner method, across two classes of models - the VGG class(using
VGG16, VGG19 and an ensemble of VGG16 and VGG19), and the Inception
class(Inception V3, Xception, Inception Resnet V2, and an ensemble of the
three). We also outline the problems with the assessment of transferability in
the current body of research and attempt to amend them by picking specific
”strong” parameters for the attacks, and by using a L-Infinity clipping
technique and the SSIM metric for the final evaluation of the attack
transferability.

Machine Learning, ICML

##  1 Introduction

Image classification is the task of assigning an image a specific class based
on the image contents. Convolutional neural networks (CNNs) (LeCun et al.,
1999) are state-of-the-art neural networks widely used for this purpose.
However, neural networks are vulnerable to adversarial examples(Szegedy et
al., 2013).

Adversarial examples are inputs created with the purpose of fooling a machine
learning model. In the context of image classification, this means distorting
the pixel values of an initially correctly classified image until
misclassification.

Adversarial examples pose challenging questions, such as how neural networks
and humans differ in classifying images. Adding noise to an image does not
usually deceive a human annotator, however, neural networks can be easily
fooled in many cases.

From a security perspective, adversarial examples are a potential risk when
introduced to a variety of machine learning applications, such as self-driving
cars, drone control, facial and speech recognition systems and more. For
example, (Finlayson et al., 2018) elaborates on how bad actors in the heavily
funded healthcare sector are able to take advantage of adversarial attacks for
misdiagnoses, leading to unnecessary and expensive medical procedures.

Adversarial images are created via adversarial attacks. Adversarial attacks
target a specific model, and look to change the input of this model until
misclassification. In a ”white-box” setting, the attacker has access to the
architecture and parameters of the model. Adding random noise without taking
advantage of the available knowledge of the model will produce adversarial
inputs of much lower quality.

Knowing the parameters and/or architecture of a model, however, is not always
possible. A malicious agent attacking a web service, for example, will not
typically know the inner details of the algorithm employed by the service. In
this ”black-box” setting, the agent may attempt to attack the service by
running an adversarial attack on either a custom local model, or on a publicly
available model, in a white-box way, and then sending the adversarially
created input over to the remote service. An example of this is the attack on
Clarifai.com (Liu et al., 2016). The property of an adversarial example
created by one system with known architecture and parameters, to transfer to
another unknown black-box system, is called transferability.

In this work we focus on the ”one-shot” black-box transferability of
adversarial attacks. By this we mean that an attacker does not receive
feedback from the black-box system, and therefore cannot make any further
modifications of the adversarial image depending on this feedback. More
specifically, we attempt to measure the transferability of three different
adversarial attacks for risk assessment across five standard image
classification models pre-trained on the ImageNet dataset: VGG16, VGG19,
Inception V3, Xception and Inception Resnet V2, and across two ensembles. Do
small differences in the model architecture account for small differences in
the transferability? Since the models are well-known, highly-performant, free,
and publicly available, web services have an incentive to adapt them to the
services’ specific use-cases via transfer learning. This could lead to overuse
of the models in the public space and motivates the choice of models explored
in this work.

In the context of previous work, research has been done on our explored
standard models to evaluate the effectiveness or transferability of
adversarial attacks (Su et al., 2018; Liu et al., 2016). However, this is
usually done only for single or multiple parameter settings of the attacks.
The parameters are usually chosen, so that the visual change in the attacked
images is imperceptible. This ”parameter overfitting” may lead to unfair or
inexhaustive comparisons due to insufficient values of the parameters being
tested and the varying importances and roles of the parameters used in the
different algorithms. This gives motivation for using a different way of
assessing transferability(sec. 3) and for further exploration into the problem
of assessing how attacks can be calibrated in order to draw consistent and
fair conclusions.

##  2 Background

###  2.1 Adversarial Attacks Frameworks

Two out-of-the-box adversarial attacks frameworks were tested in this work.
The versions of the frameworks with the necessary modifications used for the
experiments can be found here111https://github.com/deqncho2/foolbox and
here222https://github.com/deqncho2/art.

####  2.1.1 Adversarial Robustness Toolbox

The Adversarial Robustness Toolbox (ART) (Nicolae et al., 2018) is a tool
developed by IBM supporting various attacking and defensive techniques, such
as adversarial training, defensive distillation (Papernot et al., 2015), and
denoisers. The library was used in its raw format for the experiments.

####  2.1.2 Foolbox

Foolbox is library which also implements a variety of attacks such as informed
noise attacks, gradient based attacks, and attacks optimizing different norms.
This package was slightly modified for the experiment setup.

###  2.2 Standard Image Classification Networks

The following models were the default Keras implementations pre-trained on the
ImageNet dataset.

####  2.2.1 VGG Family

The first evaluated family of models is the VGG family. The VGG16 architecture
was first introduced in (Simonyan & Zisserman, 2014). For accurate
classification, the networks expect a RGB image to be preprocessed by flipping
the R and B dimensions and subtracting 103.939 from the blue, 116.779 from the
green, and 123.68 from the red channel.

##### VGG16

The VGG16 implementation in Keras consists of five blocks. The first two
blocks use two consecutive convolutional layers of filter size 3, and same
padding. The last three blocks have the same specifics, but use three
convolutions instead of two. The activation function is Relu. The number of
convolutional filters doubles each block. After the convolutions there is a
max pooling layer of size and stride 2. At the end of the blocks there are two
fully connected layers with Relu activation of size 4096 and finally a Softmax
layer for the 1000 ImageNet categories.

The network has achieved 7.3% top-5 error rate on the 2014 ImageNet challenge.

##### VGG19

The VGG19 architecture has the same architecture as VGG16, but instead of
three, it has four convolutional layers in the last three blocks. It allows
for deeper feature representations than VGG16, but does not yield much more
accurate results than VGG16 on the ImageNet challenge.

An ensemble of the two models was also evaluated against the attacks.

Figure 1: VGG Ensemble

####  2.2.2 Inception Family

GoogLeNet, also known as Inception-V1 was first introduced in 2014 (Szegedy et
al., 2014) and exploited the idea of an ”inception modules”(Lin et al., 2013).
The inception modules are feature maps combining contexts of different sizes
to obtain different types of patterns, which removes the need for manual
selection of filter sizes and reduces computational and memory cost via
convolution dimensionality reductions.

The GoogLeNet architecture combines these modules and has 6.7% error rate on
the 2014 ImageNet challenge and outperforms VGG16 despite being a lot
smaller(55 MB vs 490 MB).

The inception models’ preprocessing require the pixels of an image to be
divided by 255, subtracted by 2, and multiplied by 2, so the original [0-255]
pixel range is mapped to [-1-1].

##### Inception V3

Inception V2 and V3 were introduced in the same paper(Szegedy et al., 2015).
In it, several improvements were done to the original Inception architecture.
5x5 convolutions were factorized to two 3x3 convolutions, which sped up
computation. Furthermore, the authors found that deeper representations lose
information due to loss of dimensions and thus information. Therefore, they
made the inception modules wider to keep the number of channels high. For
version 3, RMSProp Optimizer and batch normalization(Ioffe & Szegedy, 2015)
were added, 7x7 convolutions were factorized, and label smoothing was done on
the class predictions to prevent the network from growing too confident and to
avoid overfitting.

##### Xception

Xception was introduced in (Chollet, 2016) and replaces the Inception network
convolutions with depthwise separable convolutions. It has roughly the same
number of parameters as Inception-V3, but slightly outperforms it on the
ImageNet dataset. It is based on the strong assumption that spatial and
depthwise correlations can be decoupled, leading to the name of the network
Xception (from ”Extreme Inception”). After performing a 1x1 convolution on a
feature map, it uses n convolutional filters, where n is the number of
channels of the input, and each filter iterates only over the specific
channel, instead of using filters that iterate over all channels. The network
also makes use of residual blocks and takes into account previous feature
maps. Xception has slightly smaller memory requirements than Inception V3.

##### Inception Resnet V2

Our final model is Inception Resnet V2. It incorporates elements of Residual
Networks (He et al., 2015) into the Inception V4 architecture. It has the same
architecture as Inception Resnet V1 with the exception of the ”stem”, but has
different hyperparameter settings. Both versions were introduced in the same
paper (Szegedy et al., 2016). Inception V4 and Inception Resnet V2 have
similar computational complexity despite the latter being deeper. They both
utilize reduction blocks which reduce the size of the output, and Block A is
the same in both architectures. Inception V4 and Inception Resnet V2 also
differ by the types of modules they use. The Inception Resnet versions
incorporate residual connections in their modules.

For network stability, activation scaling is used for residual layers deeper
in the architecture.

Out of the three models, Inception Resnet V2 is the deepest and the differs
the most from the other two. It requires twice the memory and computational
operations as compared to Inception V3. However, it outperforms Inception V3
on the ILSVRC 2012 image classification benchmark with a top-5 accuracy of
95.3%(with 93.9% for Inception V3) and top-1 accuracy of 80.4%(compared to
78.0%).

Finally, as before, the concatenation of these models was also evaluated by
averaging their predictions(using the argument $use\\_logits=True$ in ART and
$predicts="logits"$ in Foolbox).

Figure 2: Inception Ensemble.

###  2.3 Adversarial Attacks and Defense

Statistics were gathered for three attacks - the Fast Gradient Sign Method,
the Basic Iterative Method,and the Carlini Wagner method.

##### Fast Gradient Sign Attack Method

The Fast Gradient Sign Method was first introduced in (Goodfellow et al.,
2015) and exploits the linear nature of neural networks. It is an attack which
adds noise to the original input by taking the sign of the gradient of the
loss function J of a trained model with respect to the inputs, and adding it
to the original input. A distortion parameter $\epsilon$ controls how much the
input is perturbed. The attack is defined by the equation:

$x^{adv}=x+\epsilon*\textit{sign}(\nabla_{x}J(x,y_{true}))$

where $x^{adv}$ is the calculated adversarial image, $x$ is the original
image, $y_{true}$ is the true label of the image, and $\nabla_{x}J$ is the
Jacobian of the loss function with respect to the image.

It is a fast and reliable method to find adversarial examples, although not
the most widely used for finding realistic looking adversarials, as high-
success rate attacks yield more noticeable perturbations than other more
advanced methods.

##### Iterative Fast Gradient Sign Attack Method

The Iterative Fast Gradient Sign Method takes T gradient steps of magnitude
$\alpha=\epsilon/T$ instead of a single step. It is also called Basic
Iterative Method (Kurakin et al., 2016) in ART and does not apply clipping
after each iteration(however, there is an argument for that, which is the
algorithm described in (Kurakin et al., 2016)). The equations are:

$x_{0}^{adv}=x$
$x_{t+1}^{adv}=x_{t}^{adv}+\alpha*\textit{sign}(\nabla_{x}J(x_{t}^{adv},y_{true}))$

where $x_{t}^{adv}$ is the adversarial found at iteration $t$.

##### Carlini and Wagner Attack Method

The Carlini and Wagner (Carlini & Wagner, 2016) method is currently one of the
strongest adversarial attacks. It was used to break defensive distillation(a
method of defense that was able to reduce the success rate of previous
attacks’ ability to find adversarial examples from 95% to 0.5%). It achieved
success rate of 100% on both distilled and undistilled networks for all three
norms of the attack. The attack solves the optimization problem of minimizing
the distance D between the original image and the adversarial:

D(x, x + μ) f(x+μ)≤0

The optimization function f is

$f(x+\mu)=max(max\\{Z(x+\mu)_{i}:i\neq t\\}-Z(x+\mu)_{t},-k)$

where Z is the softmax output for the most probable class different from the
targeted class.

The k parameter controls the confidence with which the misclassification
occurs. The attack uses the Adam optimizer which allows for the tuning of the
learning rate. Several other parameters are available in the frameworks, which
did not seem to affect the attack success as much as the learning rate(most
contributory) and the confidence constant(second most contributory).

##  3 Experiments and Evaluation

A large body of research has so far concentrated on finding attacks and
parameters with high success rate for low perturbations. These evaluations may
sometimes find adversarial examples within one pixel L-infinity distance from
the original image(i.e. each pixel of the adversarial is within a value of one
of the original image). Many papers compare attacks by, for example, listing a
small number of L2/L-infinity norm thresholds for the perturbations and
reporting accuracy percentages.

Though useful for evaluation of minimal perturbations, these comparisons are
not universally practical due to the wide-spread image formats using integer
representation. Converting an adversarially found numpy floating point array
to an image is not possible, except if very specific and not widely spread
floating point image formats, such as .tiff are used. These formats provide
high-quality images and are usually employed in niche domains(e.g. X-ray
imaging). A majority of common formats such as the .png and .jpg format use
8-bit integer representation for their color channels and pixel values[0-255].
Many papers take this into account and measure minimal perturbations from
images rounded to integer values, though some do not mention it explicitly.

This means that until floating point image formats are widely used, an
attacker has to round the pixel values, which could potentially overturn the
adversarial training process and make the prediction of the white-box-attacked
classifier correct again, which makes evaluation of minimal perturbations not
valuable in some cases. The effects of rounding the values may vary. For this
work, metrics were gathered on valid images that were mapped back to their
original [0-255] ranges. In order to examine transferability fairly, a fair
metric is needed. An attack might be more transferable than another just
because it changes the image more, not because the changes are necessarily
better or ”stronger”. An initial idea for a fair metric was to pick several
thresholds for some L-norm distance from the original image and compare the
transferability across these thresholds.

This is the method used by many works in the literature. However, a problem
with this is that the ranges of perturbations found by different attacks can
vary by orders of magnitude, which makes picking appropriate thresholds to
evaluate transferability problematic. Table 1 shows normalized MSE distances
for iterations from runs for some of the different tested attacking algorithms
for a sample image using the Foolbox. It can be seen that different attacks
start finding adversarials at different distances(first entries of the table),
some start to converge, and others take different-sized steps.

Saliency Map | Blended Noise | DeepFool | Iterative Gradient | Contrast Reduction
---|---|---|---|---
6.07e-04 | 3.49e-02 | 7.96e-06 | 1.09e-03 | 9.48e-02
6.16e-04 | 3.50e-02 | 1.02e-05 | 1.24e-03 | 9.50e-02
6.20e-04 | 3.52e-02 | 1.04e-05 | 1.40e-03 | 9.52e-02
6.21e-04 | 3.54e-02 | 1.18e-05 | 1.54e-03 | 9.54e-02
6.22e-04 | 3.55e-02 | 1.19e-05 | 1.73e-03 | 9.56e-02
6.25e-04 | 3.57e-02 | 1.19e-05 | 1.87e-03 | 9.58e-02
6.29e-04 | 3.58e-02 | 1.19e-05 | 2.05e-03 | 9.60e-02
6.30e-04 | 3.60e-02 | 1.19e-05 | 2.22e-03 | 9.62e-02
6.34e-04 | 3.62e-02 | 1.19e-05 | 2.40e-03 | 9.63e-02
6.39e-04 | 3.63e-02 | 1.19e-05 | 2.57e-03 | 9.64e-02
6.44e-04 | 3.65e-02 | 1.19e-05 | 2.77e-03 | 9.66e-02
6.49e-04 | 3.67e-02 | 1.19e-05 | 2.96e-03 | 9.68e-02
6.54e-04 | 3.68e-02 | 1.19e-05 | 3.16e-03 | 9.69e-02
… | … | … | … | …
6.58e-02 | 9.43e-02 | 1.19e-05 | 9.62e-02 | 9.70e-02
6.58e-02 | 9.46e-02 | 1.19e-05 | 9.63e-02 | 9.72e-02
6.58e-02 | 9.48e-02 | 1.19e-05 | 9.64e-02 | 9.74e-02
6.58e-02 | 9.51e-02 | 1.19e-05 | 9.65e-02 | 9.76e-02
6.59e-02 | 9.54e-02 | 1.19e-05 | 9.67e-02 | 9.78e-02
6.59e-02 | 9.56e-02 | 1.19e-05 | 9.68e-02 | 9.80e-02
6.59e-02 | 9.59e-02 | 1.19e-05 | 9.70e-02 | 9.82e-02
6.59e-02 | 9.62e-02 | 1.19e-05 | 9.70e-02 | 9.84e-02
6.59e-02 | 9.64e-02 | 1.19e-05 | 9.72e-02 | 9.86e-02
Interrupted | Interrupted | Interrupted | Interrupted | Interrupted
Table 1: Normalized MSE for adversarials across iterations

A way to amend this problem is to restrict the comparison to a family of
similar algorithms which modify the image in comparable ranges. However, this
method is too restrictive in general as new attacks emerge, and thresholds for
existing attacks are difficult to choose.

Another method is to let an attack run its course and then post-process the
adversarial image by clipping it to the closest point on a ball of a given
radius away from the original image. This method is how the experiments were
set up. For the experiments, a dataset of 496 images, all classified correctly
with 0.98 confidence or more than all five classifiers, was composed. Images
as far away from the decision boundaries were preferred in order to discourage
the effectiveness of random attacks.

The images were ”trained” for the seven classifiers in a white-box way using
an untargeted attack(the attack changes the image to any other class instead
of a specific target class). Then, each of the models was attacked in a black-
box manner by simply taking the accuracy of the predictions of the classifiers
for the clipped trained images.

The experiment setup and technical details are as follows. The dataset was
created by gathering five random classes of images with a total of 497 images
(about 100 images of each class) which were passed through the VGG or
Inception preprocessing functions. They were center-cropped to have dimensions
of 224x224x3 and were ensured to have correct and confident predictions for
all five models after the preprocessing(during the course of this work, the
Keras version was updated to not allow 224x224 images for the Inception
models, but only 299x299. Older Keras versions work for this, e.g. 2.1.5).

For the training stage, the images were passed through the preprocessing
functions for the VGG or Inception models. Then, the attacking algorithms were
run, and were left to ”wonder around”. After, reverse preprocessing was
performed, the images were clipped to a minimum pixel value of 0, and maximum
of 255, in case they were out of the allowed range after the reverse
processing operation(as the API of the attacks did not allow for different
color channels to have different minimum and maximum values, which is the case
for the VGG preprocessed numpy arrays). Then, the images were clipped again to
different L-infinity norm ranges, as described below. Finally, the images were
rounded to the nearest integer and results are gathered. The clipping
procedure used was numpy’s function ”clip”.

Using this methodology a strong attack which fools most of the images in the
source model had to be found right after the preprocessing steps. Parameter
search for the attacks was done manually, due to slow training times that
discouraged standard parameter search procedures.

Different L-infinity clipping ranges - 0, 5, 10, 15, until 150 (each pixel
value of the adversarial must be within a maximum of each of these values from
the original image, consult figs. 5, 6 and 7 for images of different noise
levels) were used in the presented results.

###  3.1 Attack Parameters

In this section we present the parameters and the toolboxes used for the
experiments. Parameters other than the mentioned ones were left to their
default values. Table 2 shows the different classifiers’ accuracies in
percentages right after the preprocessing and attack end, and before the
postprocessing operations described in the section 3.

####  3.1.1 FGSM Attack - ART

For the L-Infinity FGSM implementation, ART was used with the parameter
$\epsilon=100$.

####  3.1.2 I-FGSM Attack - ART

The parameters used were a step size of 1, and number of iterations of 100 to
match FGSM’s distortion. The attack optimizes L-Infinity as well.

####  3.1.3 Carlini & Wagner Attack - Foolbox

For this L2-norm version of the attack, Foolbox was used with parameters
$\textit{max\ iterations}=100$, $\textit{learning rate}=7$, and
$\textit{confidence}=50$. The rest of the parameters were left to default at
$\textit{initial const}=1e-2$ and $\textit{binary search steps}=5$.

Classifier | FGSM | I-FGSM | C&W
---|---|---|---
VGG16 | 0.0% | 1.609% | 0.0%
VGG19 | 0.6% | 2.01% | 0.0%
Inception V3 | 0.0% | 0.0% | 0.0%
Xception | 0.0% | 0.0% | 0.0%
Inception Resnet 2 | 0.0% | 0.0% | 0.0%
VGG Ensemble | 0.0% | 1.207% | 0.0%
Inception Ensemble | 0.0% | 0.0% | 0.603%
Table 2: Accuracy of the classifiers under different attacks before
postprocessing (smaller numbers indicate a more successful attack)

###  3.2 Visual Metrics Motivation

The results(after postprocessing) when using L-Infinity as a metric for visual
perturbation are shown in fig. LABEL:fig:_linf. However, since the L-Infinity
metric is not indicative of noticeable visual perturbation(for example, an
adversarial which has 1 pixel distorted by a value of 100 is the same as an
adversarial which has all of its pixels distorted by a value of 100 under the
L-Infinity metric), we aim to gather results more correlated with human
perception of noise levels. Therefore, visual metrics other than L-Infinity
were considered when reorganizing the results for the L-Infinity-clipped
images.

###  3.3 Visual Metrics

Three other metrics were considered to reorganise the L-Infinity results in
terms of metrics which are more correlated with how human perceive images.

####  3.3.1 Inception Score

The first tested visual metric was the Inception Score (IS), first introduced
in (Salimans et al., 2016). It serves as a measure for the performance of
Generative Adversarial Networks(GANs). The IS takes a list of images as input
and returns a score. The IS was calculated using the implementation available
here333https://github.com/tsc2017/Inception-Score, where the lists of the
clipped images of the different various L-Infinity clipping ranges were passed
through the scoring function. After examination of the images, the
perturbation for the clipping ranges appeared to be gradually increasing.

However, there was no pattern to the IS(fig. 3). Therefore the metric was not
chosen to reorganize the results. The IS is not typically used in the
literature to measure the levels of adversarial noise. We observe that this
metric is ineffective for this purpose.

####  3.3.2 Mean Absolute Distance (MAD)

Commonly used metrics in the literature to measure minimum perturbations of
adversarial examples include the Mean Squarred Distance(MSD) and Mean Absolute
Distance(MAD). MAD was chosen as another potential metric for reorganization
of the results (fig. 3) and measures the mean absolute difference between the
clipped images of the different maximum ranges and the originals.

####  3.3.3 Structural Similarity Index (SSIM)

The final metric tested was the SSIM(fig. 3) and can be used to measure the
quality degradation between 2 images, commonly reported from 1(no degradation)
to 0 or from 100 to 0. This measure has been mentioned in the image analysis
literature to correlate more with human perception than MAD(Wang et al.,
2004).

Therefore, it was chosen for reorganization of the results(fig.
LABEL:fig:ssimreorg). Scikit-image was used for the calculation of the SSIM.
For the different clipping ranges, the mean SSIM between the adversarial
images, and their corresponding originals was calculated.

Figure 3: The three visual metrics considered for the reorganization of
results - Inception Score of the adversarials of varying clip strengths(top),
Average Mean Absolute Distance of adversarials of varying clip strengths from
the original images(middle), and Average Structural Similarity Index of
adversarials of varying clip strengths from the originals(bottom).

###  3.4 Discussion

Using SSIM analysis(fig. LABEL:fig:ssimreorg) we are able to gather results
which are more correlated with human perception than when using the L-Infinity
metric. However, due to the fact that the pixels of an image are changed in
uniform ranges(figs. 5, 6 and 7), the L-Infinity plots and the SSIM plots are
consistent with each other, although differences in performances are more
pronounced in the SSIM plots. When assessing attacks such as the Single-Pixel
attack(Su et al., 2017) or ”local” attacks, differences between the L-Infinity
and SSIM results are more substantial. SSIM is the superior method of
evaluation of adversarial attacks to the L-Infinity measure in the general
case. However, it is still weak in evaluating certain classes of attacks such
as adversarial scaling or rotations.

We find that, with the exception of the ensembles, for all attacks, similar
architectures have similar ”fooling” capacities. The adversarials found by
similar architectures appear very similar as well.

For the FGSM attack, the most powerful and transferable model is the VGG-
Ensemble, followed by VGG19/16, the Inception Ensemble, Inception Resnet V2,
and Inception V3 and Xception respectively. For the I-FGSM attack, the VGG-
Ensemble is the most transferable as well for small perturbations. However,
due to its quick convergence it is unable to change the image enough to to
generalize to the Inception family for larger ranges of perturbation. After
the VGG Ensemble, the remaining most transferable models are VGG19, VGG16,
followed by the Inception family. We observe that using an ensemble of
Inception models does not improve the success of the attack for both the
Inception and the VGG models. For C&W with LR=7, the ensembles perform the
worst of all models. VGG19 and 16 are again the top performing models,
followed by Inception Resnet V2, Xception and Inception V3.

In order to compare the ”best-case” transferability across the attacks, we
present the average transferability of the strongest attacking model for each
attack across all models, including the source.

In order to compare the average-case transferability, results are averaged
across the other models as well, and the averaged results are averaged over
each attack. The SSIM ranges of the models for each attack are averaged as
well:

Figure 4: Comparison of the transferability of the three attacks under the
chosen parameters

##  4 Conclusion

Transferable adversarial examples are a potential risk to a variety of
applications employing machine learning methods by using the examples created
using a local model to attack a remote service. In this work we evaluate the
transferability of adversarial examples using the setting of strong untargeted
attacks for the source models, which introduce high visual perturbation to the
images. We measure the accuracy of the classifications of the source and
target models using different sets of L-Infinity clipped images. The results
are presented with respect to both L-Infinity, and SSIM as metrics for visual
perturbation. We find that Inception Score is not a reliable way of measuring
the quality of adversarial images.We observe that for all attacks, the VGG
models are a stronger attacker than the Inception models, which is consistent
with findings in the literature. Moreover, ensembles have been used before in
the Clarifai.com black-box attack with high success rate(Liu et al., 2016). We
find that using ensembles of parallel models with averaged predictions does
not improve the attack success for all attack methods with an arbitrary
parameter setting for the attack. The presented method for evaluation of
transferability is not exhaustive, but significantly reduces the search space
of possible parameters for the attacks by restricting them to only those which
make the source misclassify most of the images, without worrying about high
visual perturbation, which is amended by the clipping mechanism. Evaluating
the algorithms in the presented way could lead to a more systematic and
quantifiable way to compare attack tranferability than the methods currently
used in the literature. More research is needed in finding ways to evaluate
transferability in a consistent and fair manner.

## References

  * Carlini & Wagner (2016) Carlini, N. and Wagner, D. A.  Towards evaluating the robustness of neural networks.  _CoRR_ , abs/1608.04644, 2016.
  * Chollet (2016) Chollet, F.  Xception: Deep learning with depthwise separable convolutions.  _CoRR_ , abs/1610.02357, 2016.  URL http://arxiv.org/abs/1610.02357.
  * Finlayson et al. (2018) Finlayson, S. G., Kohane, I. S., and Beam, A. L.  Adversarial attacks against medical deep learning systems.  _CoRR_ , abs/1804.05296, 2018.  URL http://arxiv.org/abs/1804.05296.
  * Goodfellow et al. (2015) Goodfellow, I. J., Shlens, J., and Szegedy, C.  Explaining and harnessing adversarial examples.  _CoRR_ , abs/1412.6572, 2015.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  _CoRR_ , abs/1512.03385, 2015.  URL http://arxiv.org/abs/1512.03385.
  * Ioffe & Szegedy (2015) Ioffe, S. and Szegedy, C.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  _CoRR_ , abs/1502.03167, 2015.  URL http://arxiv.org/abs/1502.03167.
  * Kurakin et al. (2016) Kurakin, A., Goodfellow, I. J., and Bengio, S.  Adversarial examples in the physical world.  _CoRR_ , abs/1607.02533, 2016.  URL http://arxiv.org/abs/1607.02533.
  * LeCun et al. (1999) LeCun, Y., Haffner, P., Bottou, L., and Bengio, Y.  Object recognition with gradient-based learning.  In _Shape, Contour and Grouping in Computer Vision_ , pp. 319–, London, UK, UK, 1999. Springer-Verlag.  ISBN 3-540-66722-9.  URL http://dl.acm.org/citation.cfm?id=646469.691875.
  * Lin et al. (2013) Lin, M., Chen, Q., and Yan, S.  Network in network.  _CoRR_ , abs/1312.4400, 2013.  URL http://arxiv.org/abs/1312.4400.
  * Liu et al. (2016) Liu, Y., Chen, X., Liu, C., and Song, D.  Delving into transferable adversarial examples and black-box attacks.  _CoRR_ , abs/1611.02770, 2016.
  * Nicolae et al. (2018) Nicolae, M., Sinn, M., Minh, T. N., Rawat, A., Wistuba, M., Zantedeschi, V., Molloy, I. M., and Edwards, B.  Adversarial robustness toolbox v0.2.2.  _CoRR_ , abs/1807.01069, 2018.  URL http://arxiv.org/abs/1807.01069.
  * Papernot et al. (2015) Papernot, N., McDaniel, P. D., Wu, X., Jha, S., and Swami, A.  Distillation as a defense to adversarial perturbations against deep neural networks.  _CoRR_ , abs/1511.04508, 2015.  URL http://arxiv.org/abs/1511.04508.
  * Salimans et al. (2016) Salimans, T., Goodfellow, I. J., Zaremba, W., Cheung, V., Radford, A., and Chen, X.  Improved techniques for training gans.  _CoRR_ , abs/1606.03498, 2016.  URL http://arxiv.org/abs/1606.03498.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  _ArXiv e-prints_ , September 2014.
  * Su et al. (2018) Su, D., Zhang, H., Chen, H., Yi, J., Chen, P., and Gao, Y.  Is robustness the cost of accuracy? - A comprehensive study on the robustness of 18 deep image classification models.  _CoRR_ , abs/1808.01688, 2018.
  * Su et al. (2017) Su, J., Vargas, D. V., and Sakurai, K.  One pixel attack for fooling deep neural networks.  _CoRR_ , abs/1710.08864, 2017.  URL http://arxiv.org/abs/1710.08864.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. J., and Fergus, R.  Intriguing properties of neural networks.  _CoRR_ , abs/1312.6199, 2013.
  * Szegedy et al. (2014) Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S. E., Anguelov, D., Erhan, D., Vanhoucke, V., and Rabinovich, A.  Going deeper with convolutions.  _CoRR_ , abs/1409.4842, 2014.  URL http://arxiv.org/abs/1409.4842.
  * Szegedy et al. (2015) Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., and Wojna, Z.  Rethinking the inception architecture for computer vision.  _CoRR_ , abs/1512.00567, 2015.  URL http://arxiv.org/abs/1512.00567.
  * Szegedy et al. (2016) Szegedy, C., Ioffe, S., and Vanhoucke, V.  Inception-v4, inception-resnet and the impact of residual connections on learning.  _CoRR_ , abs/1602.07261, 2016.  URL http://arxiv.org/abs/1602.07261.
  * Wang et al. (2004) Wang, Z., Bovik, A., Rahim Sheikh, H., and Simoncelli, E.  Image quality assessment: From error visibility to structural similarity.  _Image Processing, IEEE Transactions on_ , 13:600 – 612, 05 2004.  doi: 10.1109/TIP.2003.819861.

|
---|---
Original images | Clip range - 10, avg. transferability - 49%
|
Clip range - 20, avg. transferability - 63% | Clip range - 30, avg. transferability - 71%
|
Clip range - 40, avg. transferability - 77% | Clip range - 50, avg. transferability - 83%
|
Clip range - 60, avg. transferability - 87% | Clip range - 70, avg. transferability - 90%
Figure 5: Images for the FGSM attack trained on the VGG-Ensemble of different L-Infinity clipping ranges and the average transferability(rounded) of these ranges across all models, including the source |
---|---
Original images | Clip range \- 10, avg. transferability - 48%
|
Clip range - 20, avg. transferability - 70% | Clip range - 30, avg. transferability - 81%
|
Clip range - 40, avg. transferability - 86% | Clip range - 50, avg. transferability - 88%
|
Clip range - 60, avg. transferability - 89% | Clip range - 70, avg. transferability - 89%
Figure 6: Images for the I-FGSM attack trained on the VGG19 nework of different L-Infinity clipping ranges and the average transferability(rounded) of these ranges across all models, including the source |
---|---
Original images | Clip range - 10, avg. transferability - 48%
|
Clip range - 20, avg. transferability - 62% | Clip range - 62%, avg. transferability - 71%
|
Clip range - 40, avg. transferability - 77% | Clip range - 50, avg. transferability - 81%
|
Clip range - 60, avg. transferability - 85% | Clip range - 70, avg. transferability - 88%
Figure 7: Images for the C&W attack with LR=7, trained on the VGG19 network of
different L-Infinity clipping ranges and the average transferability(rounded)
of these ranges across all models, including the source