# Longest Property-Preserved Common Factor

Lorraine A.K Ayad  Department of Informatics, King’s College London, London,
UK
<EMAIL_ADDRESS>Giulia Bernardini  Department of Informatics, Systems
and Communication (DISCo), University of Milan-Bicocca, Italy
<EMAIL_ADDRESS>Roberto Grossi  Department of Computer Science,
University of Pisa, Italy and ERABLE Team, INRIA, France
<EMAIL_ADDRESS>Costas S. Iliopoulos  Department of Informatics, King’s
College London, London, UK
<EMAIL_ADDRESS>Nadia Pisanti  Department of Computer Science,
University of Pisa, Italy and ERABLE Team, INRIA, France
<EMAIL_ADDRESS>Solon P. Pissis  Department of Informatics, King’s College
London, London, UK
<EMAIL_ADDRESS>Giovanna Rosone  Department of Computer Science,
University of Pisa, Italy
<EMAIL_ADDRESS>
###### Abstract

In this paper we introduce a new family of string processing problems. We are
given two or more strings and we are asked to compute a factor common to all
strings that preserves a specific property and has maximal length. Here we
consider three fundamental string properties: square-free factors, periodic
factors, and palindromic factors under three different settings, one per
property. In the first setting, we are given a string $x$ and we are asked to
construct a data structure over $x$ answering the following type of on-line
queries: given string $y$, find a longest square-free factor common to $x$ and
$y$. In the second setting, we are given $k$ strings and an integer
$1<k^{\prime}\leq k$ and we are asked to find a longest periodic factor common
to at least $k^{\prime}$ strings. In the third setting, we are given two
strings and we are asked to find a longest palindromic factor common to the
two strings. We present linear-time solutions for all settings. We anticipate
that our paradigm can be extended to other string properties or settings.

##  1 Introduction

In the longest common factor problem, also known as longest common substring
problem, we are given two strings $x$ and $y$, each of length at most $n$, and
we are asked to find a maximal-length string occurring in both $x$ and $y$.
This is a classical and well-studied problem in computer science arising out
of different practical scenarios. It can be solved in $\mathcal{O}(n)$ time
and space [10, 18] (see also [21, 26]). Recently, the same problem has been
extensively studied under distance metrics; that is, the sought factors (one
from $x$ and one from $y$) must be at distance at most $k$ and have maximal
length [8, 28, 27, 2, 25, 24] (and references therein).

In this paper we initiate a new related line of research. We are given two or
more strings and our goal is to compute a factor common to all strings that
preserves a specific property and has maximal length. An analogous line of
research was introduced in [11]. It focuses on computing a subsequence (rather
than a factor) common to all strings that preserves a specific property and
has maximal length. Specifically, in [11, 3, 19], the authors considered
computing a longest common palindromic subsequence and in [20] computing a
longest common square subsequence.

We consider three fundamental string properties: square-free factors,
periodic, and palindromic factors [23] under three different settings, one per
property. In the first setting, we are given a string $x$ and we are asked to
construct a data structure over $x$ answering the following type of on-line
queries: given string $y$, find a longest square-free factor common to $x$ and
$y$. In the second setting, we are given $k$ strings and an integer
$1<k^{\prime}\leq k$ and we are asked to find a longest periodic factor common
to at least $k^{\prime}$ strings. In the third setting, we are given two
strings and we are asked to find a longest palindromic factor common to the
two strings. We present linear-time solutions for all settings. We anticipate
that our paradigm can be extended to other string properties or settings.

###  1.1 Definitions and Notation

An alphabet $\Sigma$ is a non-empty finite ordered set of letters of size
$\sigma=|\Sigma|$. In this work we consider that $\sigma=\mathcal{O}(1)$ or
that $\Sigma$ is a linearly-sortable integer alphabet. A string $x$ on an
alphabet $\Sigma$ is a sequence of elements of $\Sigma$. The set of all
strings on an alphabet $\Sigma$, including the empty string $\varepsilon$ of
length $0$, is denoted by $\Sigma^{*}$. For any string $x$, we denote by
$x[i..j]$ the substring (sometimes called factor) of $x$ that starts at
position $i$ and ends at position $j$. In particular, $x[0..j]$ is the prefix
of $x$ that ends at position $j$, and $x[i..|x|-1]$ is the suffix of $x$ that
starts at position $i$, where $|x|$ denotes the length of $x$. A string $uu$,
$u\in\Sigma^{*}$, is called a square. A square-free string is a string that
does not contain a square as a factor.

A _period_ of $x[0..|x|-1]$ is a positive integer $p$ such that $x[i]=x[i+p]$
holds for all $0\leq i<|x|-p$. The smallest period of $x$ is denoted by
$\textsf{per}(x)$. String $u$ is called periodic if and only if
$\textsf{per}(u)\leq|u|/2$. A _run_ of string $x$ is an interval $[i,j]$ such
that for the smallest period $p=\textsf{per}(x[i..j])$ it holds that $2p\leq
j-i+1$ and the periodicity cannot be extended to the left or right, i.e.,
$i=0$ or $x[i-1]\neq x[i+p-1]$, and, $j=|x|-1$ or $x[j-p+1]\neq x[j+1]$.

We denote the reversal of $x$ by string $x^{R}$, i.e.
$x^{R}=x[|x|-1]x[|x|-2]\ldots x[0]$. A string $p$ is said to be a _palindrome_
if and only if $p=p^{R}$. If factor $x[i..j]$, $0\leq i\leq j\leq n-1$, of
string $x$ of length $n$ is a palindrome, then $\frac{i+j}{2}$ is the _center_
of $x[i..j]$ in $x$ and $\frac{j-i+1}{2}$ is the radius of $x[i..j]$. In other
words, a palindrome is a string that reads the same forward and backward, i.e.
a string $p$ is a palindrome if $p=yay^{R}$ where $y$ is a string, $y^{R}$ is
the reversal of $y$ and $a$ is either a single letter or the empty string.
Moreover, $x[i..j]$ is called a palindromic factor of $x$. It is said to be a
_maximal palindrome_ if there is no other palindrome in $x$ with center
$\frac{i+j}{2}$ and larger radius. Hence $x$ has exactly $2n-1$ maximal
palindromes. A maximal palindrome $p$ of $x$ can be encoded as a pair $(c,r)$,
where $c$ is the center of $p$ in $x$ and $r$ is the radius of $p$.

###  1.2 Algorithmic Toolbox

The maximum number of runs in a string of length $n$ is less than $n$ [4],
and, moreover, all runs can be computed in $\mathcal{O}(n)$ time [22, 4].

The suffix tree $\textsf{ST}(x)$ of a non-empty string $x$ of length $n$ is a
compact trie representing all suffixes of $x$. $\textsf{ST}(x)$ can be
constructed in $\mathcal{O}(n)$ time [14]. We can analogously define and
construct the generalised suffix tree
$\textsf{GST}(x_{0},x_{1},\ldots,x_{k-1})$ for a set of $k$ strings. We assume
the reader is familiar with these data structures.

The matching statistics capture all matches between two strings $x$ and $y$
[7]. More formally, the matching statistics of a string $y[0..|y|-1]$ with
respect to a string $x$ is an array $\textsf{MS}_{y}[0..|y|-1]$, where
$\textsf{MS}_{y}[i]$ is a pair $(\ell_{i},p_{i})$ such that (i)
$y[i..i+\ell_{i}-1]$ is the longest prefix of $y[i..|y|-1]$ that is a factor
of $x$; and (ii) $x[p_{i}..p_{i}+\ell_{i}-1]=y[i..i+\ell_{i}-1]$. Matching
statistics can be computed in $\mathcal{O}(|y|)$ time for
$\sigma=\mathcal{O}(1)$ by using $\textsf{ST}(x)$ [18, 6, 16].

Given a rooted tree $T$ with $n$ leaves coloured from $0$ to $k-1$, $1<k\leq
n$, the _colour set size_ problem is finding, for each internal node $u$ of
$T$, the number of different leaf colours in the subtree rooted at $u$. In
[10], the authors present an $\mathcal{O}(n)$-time solution to this problem.

In the weighted ancestor problem, introduced in [15], we consider a rooted
tree $T$ with an integer weight function $\mu$ defined on the nodes. We
require that the weight of the root is zero and the weight of any other node
is strictly larger than the weight of its parent. A weighted ancestor query,
given a node $v$ and an integer value $\ell\leq\mu(v)$, asks for the highest
ancestor $u$ of $v$ such that $\mu(u)\geq\ell$, i.e., such an ancestor $u$
that $\mu(u)\geq\ell$ and $\mu(u)$ is the smallest possible. When $T$ is the
suffix tree of a string $x$ of length $n$, we can locate the locus of any
factor of $x[i..j]$ using a weighted ancestor query. We define the weight of a
node of the suffix tree as the length of the string it represents. Thus a
weighted ancestor query can be used for the terminal node corresponding to
$x[i..n-1]$ to create (if necessary) and mark the node that corresponds to
$x[i..j]$. Given a collection $Q$ of weighted ancestor queries on a weighted
tree $T$ on $n$ nodes with integer weights up to $n^{\mathcal{O}(1)}$, all the
queries in $Q$ can be answered off-line in $\mathcal{O}(n+|Q|)$ time [5].

##  2 Square-Free-Preserved Matching Statistics

In this section, we introduce the square-free-preserved matching statistics
problem and provide a linear-time solution. In the square-free-preserved
matching statistics problem we are given a string $x$ of length $n$ and we are
asked to construct a data structure over $x$ answering the following type of
on-line queries: given string $y$, find the longest square-free prefix of
$y[i..|y|-1]$ that is a factor of $x$, for all $0\leq i<|y|-1$. (For related
work see [12].) We represent the answer using an integer array
$\textsf{SQMS}_{y}[0..|y|-1]$ of lengths, but we can trivially modify our
algorithm to report the actual factors. It should be clear that a maximum
element in SQMS gives the length of some longest square-free factor common to
$x$ and $y$.

_Construction._ Our data structure over string $x$ consists of the following:

  * •

An integer array $L_{x}[0..n-1]$, where $L_{x}[i]$ stores the length of the
longest square-free factor starting at position $i$ of string $x$.

  * •

The suffix tree $\textsf{ST}(x)$ of string $x$.

The idea for constructing array $L_{x}$ efficiently is based on the following
crucial observation.

######  Observation 1.

If $x[i..n-1]$ contains a square then $L_{x}[i]+1$, for all $0\leq i<n$, is
the length of the shortest prefix of $x[i..n-1]$ (factor $f$) containing a
square. In fact, the square is a suffix of $f$, otherwise $f$ would not have
been the shortest. If $x[i..n-1]$ does not contain a square then
$L_{x}[i]=n-i$.

We thus shift our focus to computing the shortest such prefixes. We start by
considering the runs of $x$. Specifically, we consider squares in $x$
observing that a run $[\ell,r]$ with period $p$ contains $r-\ell-2p+2$ squares
of length $2p$ with the leftmost one starting at position $\ell$. Let
$r^{\prime}\\!=\\!\ell\\!+\\!2p\\!-\\!1$ denote the ending position of the
leftmost such square of the run. In order to find, for all $i$’s, the shortest
prefix of $x[i..n-1]$ containing a square $s$, and thus compute $L_{x}[i]$, we
have two cases:

  1. 1.

$s$ is part of a run $[\ell,r]$ in $x$ that starts after $i$. In particular,
$s=x[\ell..r^{\prime}]$ such that $r^{\prime}\leq r$, $\ell>i$, and
$r^{\prime}$ is minimal. In this case the shortest factor has length
$\ell+2p-i$; we store this value in an integer array $C[0..n-1]$. If no run
starts after position $i$ we set $C[i]=\infty$. To compute $C$, after
computing in $\mathcal{O}(n)$ time all the runs of $x$ with their $p$ and
$r^{\prime}$ [22, 4], we sort them by $r^{\prime}$. A right-to-left scan after
this sorting associates to $i$ the closest $r^{\prime}$ with $\ell>i$.

  2. 2.

$s$ is part of a run $[\ell,r]$ in $x$ and $i\\!\in\\![\ell,r]$. This implies
that if $i\\!\leq\\!r\\!-\\!2p\\!+\\!1$ then a square starts at $i$ and we
store the length of the shortest such square in an integer array $S[0..n-1]$.
If no square starts at position $i$ we set $S[i]=\infty$. Array $S$ can be
constructed in $\mathcal{O}(n)$ time by applying the algorithm of [13].

Since we do not know which of the two cases holds, we compute both $C$ and
$S$. By Observation 1, if $C[i]=S[i]=\infty$ ($x[i..n-1]$ does not contain a
square) we set $L_{x}[i]=n-i$; otherwise ($x[i..n-1]$ contains a square) we
set $L_{x}[i]=\min\\{C[i],S[i]\\}-1$.

Finally, we build the suffix tree $\textsf{ST}(x)$ of string $x$ in
$\mathcal{O}(n)$ time [14]. This completes our construction.

_Querying._ We rely on the following fact for answering the queries
efficiently.

######  Fact 1.

Every factor of a square-free string is square-free.

Let string $y$ be an on-line query. Using $\textsf{ST}(x)$, we compute the
matching statistics $\textsf{MS}_{y}$ of $y$ with respect to $x$. For each
$j\in[0,|y|-1]$, $\textsf{MS}_{y}[j]=(\ell_{i},i)$ indicates that
$x[i..i+\ell_{i}-1]=y[j..j+\ell_{i}-1]$. This computation can be done in
$\mathcal{O}(|y|)$ time [18, 6]. By applying Fact 1, we can answer any query
$y$ in $\mathcal{O}(|y|)$ time for $\sigma=\mathcal{O}(1)$ by setting
$\textsf{SQMS}_{y}[j]=\min\\{\ell_{i},L_{x}[i]\\}$, for all $0\leq
j\leq|y|-1$.

We arrive at the following result.

######  Theorem 1.

Given a string $x$ of length $n$ over an alphabet of size
$\sigma=\mathcal{O}(1)$, we can construct a data structure of size
$\mathcal{O}(n)$ in time $\mathcal{O}(n)$, answering $\textsf{SQMS}_{y}$ on-
line queries in $\mathcal{O}(|y|)$ time.

###### Proof.

The time complexity of our algorithm follows from the above discussion.

We next show the correctness of our algorithm. Let us first show the
correctness of computing array $L_{x}$. The square contained in the shortest
prefix of $x[i..n-1]$ (containing a square) starts by definition either at $i$
or after $i$. If it starts at $i$ this is correctly computed by the algorithm
of [13] which assigns the length of the shortest such square in $S[i]$. If it
starts after $i$ it must be the leftmost square of another run by the runs
definition. $C[i]$ stores the length of the shortest prefix containing such a
square. Then by Observation 1, $L_{x}[i]$ is computed correctly.

It suffices to show that, if $w$ is the longest square-free substring common
to $x$ and $y$ occurring at position $i_{x}$ in $x$ and at position $i_{y}$ in
$y$, then (i) $\textsf{MS}_{y}[i_{y}]=(\ell,i_{x})$ with $\ell\geq|w|$ and
$x[i_{x}..i_{x}+\ell-1]=y[i_{y}..i_{y}+\ell-1]$; (ii) $w$ is a prefix of
$x[i_{x}..i_{x}+L_{x}[i_{x}]-1]$; and (iii) $\textsf{SQMS}_{y}[i_{y}]=|w|$.
Case (i) directly follows from the correctness of the matching statistics
algorithm. For Case (ii), since $w$ occurs at $i_{x}$ and $w$ is square-free,
$L_{x}[i_{x}]\geq|w|$. For Case (iii), since $w$ is square-free we have to
show that $|w|=\min\\{\ell_{i},L_{x}[i]\\}$. We know from (i) that
$\ell\geq|w|$ and from (ii) that $L_{x}[i_{x}]\geq|w|$. If
$\min\\{\ell_{i},L_{x}[i]\\}=\ell$, then $w$ cannot be extended because the
possibly longer than $|w|$ square-free string occurring at $i_{x}$ does not
occur in $y$, and in this case $|w|=\ell$. Otherwise, if
$\min\\{\ell_{i},L_{x}[i]\\}=L_{x}[i_{x}]$ then $w$ cannot be extended because
it is no longer square-free, and in this case $|w|=L_{x}[i_{x}]$. Hence we
conclude that $\textsf{SQMS}_{y}[i_{y}]=|w|$. The statement follows. ∎

The following example provides a complete overview of the workings of our
algorithm.

######  Example 1.

Let $x=\texttt{aababaababb}$ and $y=\texttt{babababbaaab}$. The length of a
longest common square-free factor is 3, and the factors are bab and aba.

$i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|---
$x[i]$ | a | a | b | a | b | a | a | b | a | b | b |
$C[i]$ | 5 | 6 | 5 | 4 | 3 | 5 | 5 | 4 | 3 | $\infty$ | $\infty$ |
$S[i]$ | 2 | 4 | 4 | 6 | $\infty$ | 2 | 4 | $\infty$ | $\infty$ | 2 | $\infty$ |
$L_{x}[i]$ | 1 | 3 | 3 | 3 | 2 | 1 | 3 | 3 | 2 | 1 | 1 |
$j$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$
$y[j]$ | b | a | b | a | b | a | b | b | a | a | a | b
$\textsf{MS}_{y}[j]$ | (4,2) | (5,1) | (4,2) | (5,6) | (4,7) | (3,8) | (2,9) | (3,4) | (2,0) | (3,0) | (2,1) | (1,2)
$\textsf{SQMS}_{y}[j]$ | 3 | 3 | 3 | 3 | 3 | 2 | 1 | 2 | 1 | 1 | 2 | 1

##  3 Longest Periodic-Preserved Common Factor

In this section, we introduce the longest periodic-preserved common factor
problem and provide a linear-time solution. In the longest periodic-preserved
common factor problem, we are given $k\geq 2$ strings
$x_{0},x_{1},\dots,x_{k-1}$ of total length $N$ and an integer
$1<k^{\prime}\leq k$, and we are asked to find a longest periodic factor
common to at least $k^{\prime}$ strings. In what follows we present two
different algorithms to solve this problem. We represent the answer
$\textsf{LPCF}_{k^{\prime}}$ by the length of a longest factor, but we can
trivially modify our algorithms to report an actual factor. Our first
algorithm, denoted by lPcf, works as follows.

  1. 1.

Compute the runs of string $x_{j}$, for all $0\leq j<k$.

  2. 2.

Construct the generalised suffix tree
$\textsf{GST}(x_{0},x_{1},\ldots,x_{k-1})$ of $x_{0},x_{1},\ldots,x_{k-1}$.

  3. 3.

For each string $x_{j}$ and for each run $[\ell,r]$ with period $p_{\ell}$ of
$x_{j}$, augment GST with the explicit node spelling $x_{j}[\ell..r]$,
decorate it with $p_{\ell}$, and mark it as a _candidate_ node. This can be
done as follows: for each run $[\ell,r]$ of $x_{j}$, for all
$0\\!\leq\\!j\\!<\\!k$, find the leaf corresponding to
$x_{j}[\ell..|x_{j}|\\!\\!-\\!\\!1]$ and answer the weighted ancestor query in
GST with weight $r\\!-\\!\ell\\!+\\!1$. Moreover, mark as candidates all
explicit nodes spelling a prefix of length $d$ of any run $[\ell,r]$ with
$2p_{\ell}\leq d$.

  4. 4.

Mark as _good_ the nodes of the tree having at least $k^{\prime}$ different
colours on the leaves of the subtree rooted there. Let aGST be this augmented
tree.

  5. 5.

Return as $\textsf{LPCF}_{k^{\prime}}$ the string depth of a candidate node in
aGST which is also a good node, and that has maximal string depth (if any,
otherwise return 0).

######  Theorem 2.

Given $k$ strings of total length $N$ on alphabet
$\Sigma=\\{1,\ldots,N^{\mathcal{O}(1)}\\}$, and an integer $1<k^{\prime}\leq
k$, algorithm lPcf returns $\textsf{LPCF}_{k^{\prime}}$ in time
$\mathcal{O}(N)$.

###### Proof.

Let us assume wlog that $k^{\prime}=k$, and let $w$ with period $p$ be the
longest periodic factor common to all strings. By the construction of aGST
(Steps 1-4), the path spelling $w$ leads to a good node $n_{w}$ as $w$ occurs
in all the strings. We make the following observation.

######  Observation 2.

Each periodic factor with period $p$ of string $x$ is a factor of $x[i..j]$,
where $[i,j]$ is a run with period $p$.

By Observation 2, in all strings, $w$ is included in a run having the same
period. Observe that for at least one of the strings, there is a run ending
with $w$, otherwise we could extend $w$ obtaining a longer periodic common
factor (similarly, for at least one of the strings, there is a run starting
with $w$). Therefore $n_{w}$ is both a good and a candidate node. By
definition, $n_{w}$ is at string depth at least $2p$ and, by construction,
$\textsf{LPCF}_{k^{\prime}}$ is the string depth of a deepest such node; thus
$|w|$ will be returned by Step 5.

As for the time complexity, Step 1 [22, 4] and Step 2 [14] can be done in
$\mathcal{O}(N)$ time. Since the total number of runs is less than $N$ [4],
Step 3 can be done in $\mathcal{O}(N)$ time using off-line weighted ancestor
queries [5] to mark the runs as candidate nodes; and then a post-order
traversal to mark their ancestor explicit nodes as candidates, if their
string-depth is at least $2p_{\ell}$ for any run $[\ell,r]$ with period
$p_{\ell}$. The size of the aGST is still in $\mathcal{O}(N)$. Step 4 can be
done in $\mathcal{O}(N)$ time [10]. Step 5 can be done in $\mathcal{O}(N)$ by
a post-order traversal of aGST. ∎

The following example provides a complete overview of the workings of our
algorithm.

######  Example 2.

Consider $x=$ababbabba, $y=$ababaab, and $k\\!=\\!k^{\prime}\\!=\\!2$. The
runs of $x$ are: $r_{0}=[0,3]$, $\textsf{per}(\texttt{abab})=2$,
$r_{1}=[1,8]$, $\textsf{per}(\texttt{babbabba})=3$, $r_{2}=[3,4]$,
$\textsf{per}(\texttt{bb})=1$, and $r_{3}=[6,7]$,
$\textsf{per}(\texttt{bb})=1$; those of $y$ are $r_{4}=[0,4]$,
$\textsf{per}(\texttt{ababa})=2$ and $r_{5}=[4,5]$,
$\textsf{per}(\texttt{aa})=1$. Fig 1 shows aGST for $x$, $y$, and
$k\\!=\\!k^{\prime}\\!=\\!2$. Algorithm lPcf outputs $4=|\texttt{abab}|$, with
$\textsf{per}(\texttt{abab})=2$, as the node spelling abab is the deepest good
one that is also a candidate.

Figure 1: aGST for $x=\texttt{ababbabba}$, $y=$ababaab, and
$k\\!=\\!k^{\prime}\\!=\\!2$.

We next present a second algorithm to solve this problem with the same time
complexity but without the use of off-line weighted ancestor queries. The
algorithm works as follows.

  1. 1.

Compute the runs of string $x_{j}$, for all $0\leq j<k$.

  2. 2.

Construct the generalised suffix tree
$\textsf{GST}(x_{0},x_{1},\ldots,x_{k-1})$ of $x_{0},x_{1},\ldots,x_{k-1}$.

  3. 3.

Mark as _good_ the nodes of GST having at least $k^{\prime}$ different colours
on the leaves of the subtree rooted there.

  4. 4.

Compute and store, for every leaf node, the _nearest_ ancestor that is good.

  5. 5.

For each string $x_{j}$ and for each run $[\ell,r]$ with period $p_{\ell}$ of
$x_{j}$, check the nearest good ancestor for the leaf corresponding to
$x_{j}[\ell..|x_{j}|-1]$. Let $d$ be the string-depth of the nearest good
ancestor. Then:

    1. (a)

If $r-\ell+1\leq d$, the entire run is also good.

    2. (b)

If $r-\ell+1>d$, check if $2p_{\ell}\leq d$, and if so the string for the good
ancestor is periodic.

  6. 6.

Return as $\textsf{LPCF}_{k^{\prime}}$ the maximal string depth found in Step
5 (if any, otherwise return 0).

Figure 2: GST for $x=\texttt{ababaa}$, $y=\texttt{bababb}$, and
$k\\!=\\!k^{\prime}\\!=\\!2$. Good nodes are marked red.

Let us analyse this algorithm. Let us assume wlog that $k^{\prime}=k$, and let
$w$ with period $p$ be the longest periodic factor common to all strings. By
the construction of GST (Steps 1-3), the path spelling $w$ leads to a good
node $n_{w}$ as $w$ occurs in all the strings.

By Observation 2, in all strings, $w$ is included in a run having the same
period. Observe that for at least one of the strings, there is a run starting
with $w$, otherwise we could extend $w$ obtaining a longer periodic common
factor. So the algorithm should check, for each run, if there is a periodic-
preserved common prefix of the run and take the longest such prefix.
$\textsf{LPCF}_{k^{\prime}}$ is the string depth of a deepest good node
spelling a periodic factor; thus $|w|$ will be returned by Step 6.

As for the time complexity, Step 1 [22, 4] and Step 2 [14] can be done in
$\mathcal{O}(N)$ time. Step 3 can be done in $\mathcal{O}(N)$ time [10] and
Step 4 can be done in $\mathcal{O}(N)$ time by using a tree traversal. Since
the total number of runs is less than $N$ [4], Step 5 can be done in
$\mathcal{O}(N)$ time. We thus arrive at Theorem 2 with a different algorithm.

The following example provides a complete overview of the workings of our
algorithm.

######  Example 3.

Consider $x=$ababaa, $y=$bababb, and $k\\!=\\!k^{\prime}\\!=\\!2$. The runs of
$x$ are: $r_{0}=[0,4]$, $\textsf{per}(\texttt{ababa})=2$, $r_{1}=[4,5]$,
$\textsf{per}(\texttt{aa})=1$; those of $y$ are $r_{2}=[0,4]$,
$\textsf{per}(\texttt{babab})=2$ and $r_{3}=[4,5]$,
$\textsf{per}(\texttt{bb})=1$. Fig 2 shows GST for $x$, $y$, and
$k\\!=\\!k^{\prime}\\!=\\!2$. Consider the run $r_{0}=[0,4]$. The nearest good
node of leaf spelling $x[0..|x|-1]$ is the node spelling abab. We have that
$r-\ell+1=5>d=4$, and $2p=4\leq d=4$. The algorithm outputs
$4=|\texttt{abab}|$ as abab is a longest periodic-preserved common factor.
Another longest periodic-preserved common factor is baba.

##  4 Longest Palindromic-Preserved Common Factor

In this section, we introduce the longest palindromic-preserved common factor
problem and provide a linear-time solution. In the longest palindromic-
preserved common factor problem, we are given two strings $x$ and $y$, and we
are asked to find a longest palindromic factor common to the two strings. (For
related work in a dynamic setting see [17, 1].) We represent the answer LPALCF
by the length of a longest factor, but we can trivially modify our algorithm
to report an actual factor. Our algorithm is denoted by lPalcf. In the
description below, for clarity, we consider odd-length palindromes only.
(Even-length palindromes can be handled in an analogous manner.)

  1. 1.

Compute the maximal odd-length palindromes of $x$ and the maximal odd-length
palindromes of $y$.

  2. 2.

Collect the factors $x[i..i^{\prime}]$ of $x$ (resp. the factors
$y[j..j^{\prime}]$ of $y$) such that $i$ ($j$) is the center of an odd-length
maximal palindrome of $x$ ($y$) and $i^{\prime}$ ($j^{\prime}$) is the ending
position of the odd-length maximal palindrome centered at $i$ ($j$).

  3. 3.

Create a lexicographically sorted list $L$ of these strings from $x$ and $y$.

  4. 4.

Compute the longest common prefix of consecutive entries (strings) in $L$.

  5. 5.

Let $\ell$ be the maximal length of longest common prefixes between any string
from $x$ and any string from $y$. For odd lengths, return LPALCF$=2\ell-1$.

######  Theorem 3.

Given two strings $x$ and $y$ on alphabet
$\Sigma=\\{1,\ldots,(|x|+|y|)^{\mathcal{O}(1)}\\}$, algorithm lPalcf returns
LPALCF in time $\mathcal{O}(|x|+|y|)$.

###### Proof.

The correctness of our algorithm follows directly from the following
observation.

######  Observation 3.

Any longest palindromic-preserved common factor is a factor of a maximal
palindrome of $x$ with the same center and a factor of a maximal palindrome of
$y$ with the same center.

Step 1 can be done in $\mathcal{O}(|x|+|y|)$ time [18]. Step 2 can be done in
$\mathcal{O}(|x|+|y|)$ time by going through the set of maximal palindromes
computed in Step 1. Step 3 and Step 4 can be done in $\mathcal{O}(|x|+|y|)$
time by constructing the data structure of [9]. Step 5 can be done in
$\mathcal{O}(|x|+|y|)$ time by going through the list of computed longest
common prefixes.

∎

The following example provides a complete overview of the workings of our
algorithm.

######  Example 4.

Consider $x=$ababaa and $y=$bababb. In Step 1 we compute all maximal
palindromes of $x$ and $y$. Considering odd-length palindromes gives the
following factors (Step 2) from $x$: $x[0..0]=\texttt{a}$,
$x[1..2]=\texttt{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}ba}}$,
$x[2..4]=\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}ab}a}$,
$x[3..4]=\texttt{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}ba}}$,
$x[4..4]=\texttt{a}$, and $x[5..5]=\texttt{a}$. The analogous factors from $y$
are: $y[0..0]=\texttt{b}$,
$y[1..2]=\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}ab}}$,
$y[2..4]=\texttt{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}ba}b}$,
$y[3..4]=\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}ab}}$,
$y[4..4]=\texttt{b}$, and $y[5..5]=\texttt{b}$. We sort these strings
lexicographically and compute the longest common prefix information (Steps
3-4). We find that $\ell=2$: the maximal longest common prefixes are ba and
ab, denoting that aba and bab are the longest palindromic-preserved common
factors of odd length. In fact, algorithm lPalcf outputs $2\ell-1=3$ as aba
and bab are the longest palindromic-preserved common factors of any length.

##  5 Final Remarks

In this paper, we introduced a new family of string processing problems. The
goal is to compute factors common to a set of strings preserving a specific
property and having maximal length. We showed linear-time algorithms for
square-free, periodic, and palindromic factors under three different settings.
We anticipate that our paradigm can be extended to other string properties or
settings.

## Acknowledgements

We would like to acknowledge an anonymous reviewer of a previous version of
this paper who suggested the second linear-time algorithm for computing the
longest periodic-preserved common factor. Solon P. Pissis and Giovanna Rosone
are partially supported by the Royal Society project IE 161274 “Processing
uncertain sequences: combinatorics and applications”. Giovanna Rosone and
Nadia Pisanti are partially supported by the project Italian MIUR-SIR
CMACBioSeq (“Combinatorial methods for analysis and compression of biological
sequences”) grant n. RBSI146R5L.

## References

  * [1] Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common factor made fully dynamic.  CoRR, abs/1804.08731, 2018.
  * [2] Lorraine A. K. Ayad, Carl Barton, Panagiotis Charalampopoulos, Costas S. Iliopoulos, and Solon P. Pissis.  Longest common prefixes with $k$-errors and applications.  In SPIRE, volume 11147 of LNCS, pages 27–41. Springer, 2018\.
  * [3] Sang Won Bae and Inbok Lee.  On finding a longest common palindromic subsequence.  Theoretical Computer Science, 710:29–34, 2018.  Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos).
  * [4] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta.  The “runs” theorem.  SIAM Journal on Computing, 46(5):1501–1514, 2017.
  * [5] Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis, and Jakub Radoszewski.  Indexing weighted sequences: Neat and efficient.  CoRR, abs/1704.07625, 2017.
  * [6] Djamal Belazzougui and Fabio Cunial.  Indexed matching statistics and shortest unique substrings.  In Edleno Silva de Moura and Maxime Crochemore, editors, 21st International Symposium on String Processing and Information Retrieval (SPIRE), volume 8799 of LNCS, pages 179–190, 2014.
  * [7] W. I. Chang and E. L. Lawler.  Sublinear approximate string matching and biological applications.  Algorithmica, 12(4):327–344, 1994.
  * [8] Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Linear-time algorithm for long LCF with k mismatches.  In CPM, volume 105 of LIPIcs, pages 23:1–23:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
  * [9] Panagiotis Charalampopoulos, Costas S. Iliopoulos, Chang Liu, and Solon P. Pissis.  Property suffix array with applications.  In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 290–302. Springer, 2018\.
  * [10] Lucas Chi and Kwong Hui.  Color set size problem with applications to string matching.  In Combinatorial Pattern Matching, pages 230–243. Springer Berlin Heidelberg, 1992.
  * [11] Shihabur Rahman Chowdhury, Md. Mahbubul Hasan, Sumaiya Iqbal, and M. Sohel Rahman.  Computing a longest common palindromic subsequence.  Fundam. Inf., 129(4):329–340, 2014.
  * [12] Marius Dumitran, Florin Manea, and Dirk Nowotka.  On prefix/suffix-square free words.  In Costas S. Iliopoulos, Simon J. Puglisi, and Emine Yilmaz, editors, 22nd International Symposium, on String Processing and Information Retrieval (SPIRE), volume 9309 of LNCS, pages 54–66, 2015.
  * [13] Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq, and Arnaud Lefebvre.  Linear-time computation of local periods.  Theoretical Computer Science, 326(1):229–240, 2004.
  * [14] Martin Farach.  Optimal suffix tree construction with large alphabets.  In 38th Annual Symposium on Foundations of Computer Science (FOCS), pages 137–143, 1997.
  * [15] Martin Farach and S. Muthukrishnan.  Perfect hashing for strings: Formalization and algorithms.  In 7th Symposium on Combinatorial Pattern Matching (CPM), pages 130–140. 1996.
  * [16] Maria Federico and Nadia Pisanti.  Suffix tree characterization of maximal motifs in biological sequences.  Theor. Comput. Sci., 410(43):4391–4401, 2009.
  * [17] Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest substring palindrome after edit.  In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors, Annual Symposium on Combinatorial Pattern Matching (CPM 2018), volume 105 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [18] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology.  Cambridge University Press, 1997.
  * [19] Shunsuke Inenaga and Heikki Hyyrö.  A hardness result and new algorithm for the longest common palindromic subsequence problem.  Information Processing Letters, 129:11–15, 2018.
  * [20] Takafumi Inoue, Shunsuke Inenaga, Heikki Hyyrö, Hideo Bannai, and Masayuki Takeda.  Computing longest common square subsequences.  In 29th Symposium on Combinatorial Pattern Matching (CPM), volume 105 of LIPIcs, pages 15:1–15:13, 2018.
  * [21] Tomasz Kociumaka, Tatiana A. Starikovskaya, and Hjalte Wedel Vildhøj.  Sublinear space algorithms for the longest common substring problem.  In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 605–617, 2014.
  * [22] Roman Kolpakov and Gregory Kucherov.  Finding maximal repetitions in a word in linear time.  In 40th Symposium on Foundations of Comp Science, pages 596–604, 1999.
  * [23] M. Lothaire.  Applied Combinatorics on Words.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2005.
  * [24] Pierre Peterlongo, Nadia Pisanti, Frédéric Boyer, Alair Pereira do Lago, and Marie-France Sagot.  Lossless filter for multiple repetitions with hamming distance.  J. Discr. Alg., 6(3):497–509, 2008.
  * [25] Pierre Peterlongo, Nadia Pisanti, Frédéric Boyer, and Marie-France Sagot.  Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array.  In 12th International Symposium String Processing and Information Retrieval, 12th International Conference (SPIRE), pages 179–190, 2005.
  * [26] Tatiana A. Starikovskaya and Hjalte Wedel Vildhøj.  Time-space trade-offs for the longest common substring problem.  In 24th Symposium on Combinatorial Pattern Matching (CPM), pages 223–234, 2013.
  * [27] Sharma V. Thankachan, Chaitanya Aluru, Sriram P. Chockalingam, and Srinivas Aluru.  Algorithmic framework for approximate matching under bounded edits with applications to sequence analysis.  In RECOMB, volume 10812 of LNCS, pages 211–224, 2018.
  * [28] Sharma V. Thankachan, Alberto Apostolico, and Srinivas Aluru.  A provably efficient algorithm for the _k_ -mismatch average common substring problem.  Journal of Computational Biology, 23(6):472–482, 2016.


# CatFedAvg: Optimising Communication-efficiency and
Classification Accuracy in Federated Learning

Dipankar Sarkar,1 Sumit Rai, 2 Ankur Narang 1

###### Abstract

Federated learning has allowed the training of statistical models over remote
devices without the transfer of raw client data. In practice, training in
heterogeneous and large networks introduce novel challenges in various aspects
like network load, quality of client data, security and privacy. Recent works
in FL have worked on improving communication efficiency and addressing uneven
client data distribution independently, but none have provided a unified
solution for both challenges. We introduce a new family of Federated Learning
algorithms called CatFedAvg which not only improves the communication
efficiency but improves the quality of learning using a category coverage
maximization strategy.

We use the FedAvg framework and introduce a simple and efficient step every
epoch to collect meta-data about the client’s training data structure which
the central server uses to request a subset of weight updates. We explore two
distinct variations which allow us to further explore the tradeoffs between
communication efficiency and model accuracy. Our experiments based on a vision
classification task have shown that an increase of 10% absolute points in
accuracy using the MNIST dataset with 70% absolute points lower network
transfer over FedAvg. We also run similar experiments with Fashion MNIST,
KMNIST-10, KMNIST-49 and EMNIST-47. Further, under extreme data imbalance
experiments for both globally and individual clients, we see the model
performing better than FedAvg. The ablation study further explores its
behaviour under varying data and client parameter conditions showcasing the
robustness of the proposed approach.

In this era of computing, we have seen an explosion of connected personal
devices and IoT (Lueth 2018). We see tremendous progress in Deep Learning
(LeCun, Bengio, and Hinton 2015), which has partially been driven by the
growth of data that we collect. This combination has lead to exciting research
and applications in the area of distributed model training.

The conventional data processing approach has been centralized with all these
devices, uploading their data into cloud servers or data centres (Li et al.
2017). This data is then processed to provide insights or training various
inference models. Recently, consumers and business alike have questioned data
centralization. Governments are responding by the enactment of legislation
like GDPR (Custers et al. 2019) in the EU, and Consumer Privacy Bill of Rights
(Gaff, Sussman, and Geetter 2014) in the US. These laws focus on limiting data
collection and storage to what the consumer has consented for and required for
processing. As data collection happens at scale, there are other technical
issues like latency (Mao et al. 2017) for real-time use cases and network
loads.

So, we see the emergence of Mobile Edge Computing (MEC) that use the storage
and processing capabilities of the edge servers and edge devices to train
models closer to the data generators (Shi et al. 2016). In this solution, we
transmit data to the edge servers for training a few layers, and the cloud
servers do more computationally heavy tasks. This approach has shown
challenges with managing communication costs and models that require
continuous training (Han et al. 2020). We see the application of Differential
Privacy (DP) (Abadi et al. 2016) for privacy preservation, but many users are
unwilling to expose their private data.

In this regard, we see the introduction of a decentralized ML approach called
Federated Learning (McMahan et al. 2016). It guarantees that the data remains
on the personal devices and allows collaborative machine learning of complex
models. A high-level view of the approach is that we cooperatively train an ML
model on a mobile device using its local data. We send the client trained
model’s weight to the FL server for aggregation. We repeat the steps until to
reach some target accuracy. This approach is network bandwidth-efficient as
only model weights are sent instead of raw data. As the model is on the mobile
device, it enables privacy and makes low inference latency.

We see its successful application in production with like the Federated
Averaging Algorithm (FedAvg) (McMahan et al. 2016) used in Google’s GBoard
(Hard et al. 2018) to improve next-word predictions. There are other examples
like recommendations (Chen et al. 2018) and training of health diagnosis
models which allows many hospitals and government agencies can collaborate
without explicit data sharing (Brisimi et al. 2018).

The Federated learning problem has a few challenges; for example, with
federated networks comprising of a massive number of devices, the network data
transfer costs can be humongous. There is much variability in the device
capabilities in the network that leads to uncertain client behaviour. The
client also generates data in a non-identically distributed manner across the
network. Finally, privacy is a concern even when model weights are shared as
they can reveal sensitive information about the client data.

In this paper, we take on the dual challenge of communication efficiency and
model training accuracy under client non-IID conditions. We see the use of two
strategies for improving the communication efficiency, current work (McMahan
et al. 2017) uses the static selection of a fraction of client models, and the
other is the compression of the model updates (Alistarh et al. 2017). We
further see that FedAvg performs badly when the client datasets are non-IID
(Zhao et al. 2018) in the experiments performed. Our proposed approach
improves model accuracy significantly. The contributions of the paper can be
summarized as follows

  * •

We propose a new family of algorithms called CatFedAvg with two proposed
variants that significantly improve communication efficiency by up to 70AP
while boosting model accuracy by up to 22AP.

  * •

We build a framework that uses a simple and efficient client categorical
coverage strategy identify the best client combinations for training. This
allows us to tradeoff communication overheads for accuracy and vice-versa.

  * •

Our experiments show that we outperform the baseline FedAvg and VIRTUAL MTL
algorithm. We solve an image classification problem using multiple image
datasets under various client distribution conditions. We perform an ablation
study to further show the robustness of our approach.

## Related Works

### Federated Learning

Federated learning (McMahan et al. 2016) is a decentralized machine learning
method, which uses distributed training on clients without sending the raw
data to the central server. We can split this into three categories of
vertical federated learning, horizontal federated learning and federated
transfer learning.

There have been improvements proposed which, for example, improve privacy
protection by the usage of differential privacy techniques (Abadi et al. 2016)
or remove the bias of client models using agnostic federated learning (Mohri,
Sivek, and Suresh 2019).

### Communication Cost

In FL, there are several rounds of communication between the clients and the
server during training. We have DL models that have millions of parameters.
Thus, the larger size of the updates will lead to higher communication costs,
which can be a training bottleneck. Further, unreliable network conditions and
asymmetric net connection speeds will result in delays from the client.

We can use model compression (Wang et al. 2018) which is used widely in
distributed learning where techniques like sparsification, quantization or
subsampling (Stich, Cordonnier, and Jaggi 2018) are to reduce the model update
size. However, our goal is to maintain the quality of the trained models
(Caldas et al. 2018).

Alternatively, we can use selective communication where only relevant or
essential updates are transmitted back (Tao and Li 2018). This technique saves
communication costs and at times, improves the Global performance. We see the
usage of random subsampling of clients in the sketched updating method
(Konecný et al. 2016) to improve communication efficiency.

### Statistical Heteroginity

Federated learning has a few statistical challenges. In traditional
distributed ML, the central server has access to the complete dataset.
Allowing the server to split it into subsets with similar distributions; we
transfer these to the clients for distributed training. However, this approach
is impractical for FL, as the dataset is local to the client.

In this setting, the clients may have datasets with variable distributions,
i.e. the datasets are non-IID. We have cases (Zhao et al. 2018) where FedAvg
is unable to achieve the desired accuracy in these conditions. When the
dataset is highly skewed and non-IID, we have a solution where a common
dataset is sent to the clients by the central server. However, this may not be
possible in all cases.

We also see the challenge of global imbalance where the collection of data
held across all the clients is class imbalanced, which leads to a decrease in
model accuracy. We see the Astrea framework (Duan 2019) trying to solve this
problem, where clients initially send their data distribution to the server.
Then we have a rebalancing step where each client performs data augmentation
on minority classes. There is a mediator that selects the best clients that
contribute to the uniform distributions. This approach has shown accuracy
improvements.

There have been solutions like FEDPER (Arivazhagan et al. 2019) using concepts
from Multi-task learning to learn separate but structurally related models for
each participant. We see the training of another set of personalization layers
being trained by the client locally on its data. This has been used for
building recommender systems, and testing on Flickr-AES dataset (Deng et al.
2017) has shown it to outperform FedAvg. Even though federated multi-task
learning has been shown to be an effective paradigm for real-world datasets,
it has been applied only to convex models. We compare our algorithm
performance with VIRTUAL algorithm (32) with that has been designed for the
federated multi-task learning with non-convex models in non-IID conditions.

## CatFedAvg

We introduce the category maximization federated averaging algorithm
(CatFedAvg) for classification models whose primary objective is to ensure the
usage of model updates which have been trained with the most number of
categories.

This is based on the FedAvg Algorithm as shown. Here C denotes fraction of
selected clients, while K selected clients are indexed by k; B is the local
minibatch size, E is the number of local epochs, and $\mathbf{\eta}$ is the
learning rate.

1 Server Executes:

2 initialize $w_{0}$

3 for  _$i\leftarrow 1$ to $M$_ do

4 m $\leftarrow$ max(C.K,1)

5 $S_{t}\leftarrow$ (random set of K clients)

6 for  _each client k $\in S_{t}$ in parallel_ do

7 $w_{t+1}^{k}\leftarrow$ ClientUpdate(k,$w_{t}$)

8 end for

9 $w_{t+1}\leftarrow\sum\limits_{k=1}^{k=K}\frac{n_{k}}{n}w_{t+1}$

10 end for

11

12 ClientUpdate(k,w): // Run on client k

13 $\beta\leftarrow$ (split $P_{k}$ into batches of size B)

14 for  _each local epoch i $\leftarrow$ 1 to E_ do

15 for  _batch b $\in\beta$ _ do

16 w $\leftarrow w-\eta\nabla l(w;b)$

17 end for

18

19 end for

return $w$ to server

Algorithm 1 Federated Averaging Algorithm

Our proposal is the introduction of a meta-data collection round that makes
the central system aware of what is the data distribution at the client’s end.
We then select a set of clients instead of the random strategy taken in FedAvg
such that we maximize the coverage of categories.

We choose a classification problem that has $C$ categories, where $F$ is the
total number of federated clients. In this, a random subset of $M$ is
selected. This represents the larger subset whose meta-data we request. We use
$N$ to denote a limiting parameter which is the maximum number of clients that
we can sample.

All the clients share their $\eta$, which is a client mask of $C$ bits, where
a bit on denotes that a category is present in the new client dataset. The
algorithm selects $S$ clients to maximize the coverage of $\Psi$ at the
central server level. Assuming that all categories are present in the system,
if we set $N=C$, we can guarantees coverage of all categories under both modes
of operation.

These represent the updated client subset selection executed in line 1 of the
Federated Averaging Algorithm.

Input: Clients Masks $\eta_{1}\dots\eta_{M}$, Global Mask $\Psi$ = 0, N, S,
K=0

Output: Set S of indices of selected Clients

1 Sort $\eta_{1}\dots\eta_{M}$ in decreasing order of number of set bits. for
_$i\leftarrow 1$ to $C$_ do

2 if  _K = N_ then

3 break

4 for  _$j\leftarrow 1$ to $M$_ do

5 if  _$\eta_{ji}=1$ AND $\eta_{j}\cap S=\phi$_ then

6 $S\leftarrow S\cup\eta_{j}$ $K\leftarrow K+1$ break

7

8 end for

9

10 end for

return _$S$_

Algorithm 2 CatFedAvg - performance strategy

We introduce the first client selection strategy, in which select a fixed
number of $C$ clients. We collect the category bitmasks, sort them in
decreasing order of set bits. We then try and cover each category with one
client.

If $N\geq C$ then all categories will be covered. Further, it is possible that
each category is covered more than once in the sampled model updates. This
will lead to adequate data coverage for training and leads to better model
accuracy.

Input: Clients Masks $\eta_{1}\dots\eta_{M}$, Global Mask $\Psi$ = 0, N, S,
K=0

Output: Set S of indices of selected Clients

1 Sort $\eta_{1}\dots\eta_{M}$ in decreasing order of number of set bits.

2for  _$j\leftarrow 1$ to $M$_ do

3 if  _K = N OR $\Psi=2^{C}-1$_ then

4 break

5 if  _$\Psi$ AND $\eta_{j}<\eta_{j}$_ then

6 $S\leftarrow S\cup\eta_{j}$

7 $K\leftarrow K+1$

8 $\Psi\leftarrow\Psi$ OR $\eta_{j}$

9

10 end for

11

return _$S$_

Algorithm 3 CatFedAvg - cost strategy

In the cost strategy, we select a variable number of clients depending on the
distribution. Similar to the first strategy, we pick a category and then
select a client. However, we know that a client may have more than one
category covered. That means we can skip those categories that have been
covered and continue selection for the uncovered ones. We will select a
maximum of C clients.

If we have $N\geq C$ then each category is covered at least once with the
least probability of having a particular category covered more than once. It
optimizes cost with maximum category coverage with the goal of minimizing the
number of clients required to cover all categories.

## Analysis

### Federated Averaging

We have a federated system with $M$ clients with datasets
$D_{1},D_{2},D_{3}\dots D_{M}$ with a central server $S$. A fixed number of
$K$ clients can be sampled from $M$ clients to participate in updating the
global cloud model. The global loss function $F_{s}$ is related with $K$
participating clients with loss function $F_{i}$ for $i_{th}$ client as shown
below.

$F_{s}=\frac{\sum\limits_{i=1}^{i=K}F_{i}}{K}$ (1)

Let $F_{i}c_{j}$ denote loss contribution of $j^{th}$ class id from $i^{th}$
client. The loss contribution from $i^{th}$ client can be expressed in terms
of losses of each category for a global problem with C categories, as shown
below.

$F_{i}=\sum\limits_{i=1}^{i=C}F_{i}c_{j}$ (2)

Using eqs. (1, 2) we have,

$F_{s}=\frac{\sum\limits_{i=1}^{i=K}\sum\limits_{j=1}^{j=C}F_{i}c_{j}}{K}\\\
KF_{s}=\sum\limits_{i=1}^{i=K}\sum\limits_{j=1}^{j=C}F_{i}c_{j}$ (3)

Ideally, $KF_{s}$ should have loss contribution from all categories, but in
real-world skewed Non-IID conditions, some classes may not be covered by the
usual random sampling technique of FedAvg technique. Hence, there may exist
cases where $F_{i}c_{j}$ is not defined for any value of $i$ $\in[1,K]$

### Category coverage-based aggregation

We define a novel method of aggregation which is focused on maximizing
category coverage. Let $G_{ji}$ denote loss contribution of $j^{th}$ class
from $i^{th}$ client and let $G_{j}$ denote the total loss of $j^{th}$ class
id for all clients $i\in[1,K]$.

$G_{j}=\sum\limits_{j=1}^{j=C}G_{ji}$ (4)

We select clients in such a way that $G_{j}$ is defined for atleast one client
with id $i\in[1,K]$. This is ensured using bitmasking strategy. Hence, global
loss function of server $G_{s}$ can be represented as shown below.

$G_{s}=\frac{\sum\limits_{j=1}^{j=C}G_{j}}{K}$ (5)

Using eqs. (4, 5) we have,

$G_{s}=\frac{\sum\limits_{j=1}^{j=C}\sum\limits_{i=1}^{i=K}G_{ji}}{K}$ (6)

We can state that (3, 5) are equal. The inherent nature of averaging the loss
contribution remains unchanged with our formulation.

### Understanding Tradeoffs

#### Communication Cost

Let $C_{s}$ be the cost of updating the global model, assuming extra cost
introduced by each client while averaging the weights to be negligible. Let
$C_{c}$ be the cost incurred at the server end while interacting with a single
client. The total cost for one single round with K participating clients can
be approximately expressed as shown below.

$C_{1}=KC_{c}+C_{s}$ (7)

The total cost for R rounds of global updates can expressed as:

$\displaystyle C_{R}=\sum\limits_{i=1}^{i=R}(KC_{c}+C_{s})$ (8) $\displaystyle
C_{R}=\sum\limits_{i=1}^{i=R}KC_{c}+\sum\limits_{i=1}^{i=R}C_{s}$ (9)
$\displaystyle C_{R}=RKC_{c}+RC{s}$ (10)

The cost per client interaction for R rounds can be obtained by
differentiating eq (8) with respect to $C_{c}$.

$\displaystyle\frac{dC_{R}}{dC{c}}=\frac{d(RKC_{c})}{dC{c}}+\frac{d(RC_{s})}{dC{c}}$
(11) $\displaystyle\frac{dC_{R}}{dC{c}}=RK+0$ (12)

Dividing eq (13) by R yields cost incurred per client per round

$\bigg{(}\frac{1}{R}\bigg{)}\frac{dC_{R}}{dC{c}}=K$ (13)

Eq (14) depends directly on K. Hence, the cost incurred at the server end,
increasing proportionately with the number of incorporating clients (K).

#### Model performance

Let the number of data samples with each of the participating client be
$n_{1}\dots n_{K}$. Let the total number of data samples seen by the server be
D.

$D=\sum\limits_{i=1}^{i=K}n_{i}$ (14)

Hence, D increases with K. Increasing value of D help in generalizing the
global model.

From eqs. (13,14) we can conclude that both cost and performance increases
with number of participating clients K.

We see that a tradeoff between high model accuracy and low cost.

## Experiments

|  | Total Samples | Samples per class
---|---|---|---
Dataset | Number of Classes | Training | Validation | Training | Validation
|  |  |  | Mean | Std | Mean | Std
MNIST | 10 | 60000 | 10000 | 6000 | 322 | 1000 | 59
FMNIST | 10 | 60000 | 10000 | 6000 | 0 | 1000 | 0
KMNIST-10 | 10 | 60000 | 10000 | 6000 | 0 | 1000 | 0
FEMNIST | 47 | 112800 | 18800 | 2400 | 0 | 400 | 0
KMNIST-49 | 49 | 232365 | 38547 | 4742 | 1839 | 786 | 309
Table 1: Description of datasets used in the experiments

We present a set of experiments that take compare our algorithms with FedAvg
and Virtual MTL. We use five datasets and varying categories along with client
data distribution. We further perform an ablation study to dissect the various
parameters that show it as a clear improvement over FedAvg.

### Datasets

We have primarily used vision datasets, and all details of the datasets used
for our experiments have been summarized in Table 1.

  * •

MNIST: (Deng 2012) The dataset contains a total of 70,000 small square 28x28
pixels grayscale images of handwritten single digits between 0 and 9. The
subdivision of dataset is 60,000 training samples and 10,000 testing samples.
We federated the dataset amongst the clients to simulate client conditions.

  * •

FMNIST Fashion MNIST (Xiao, Rasul, and Vollgraf 2017) abbreviated as FMNIST is
a dataset of Zalando’s article images consisting of a training set of 60,000
examples and a test set of 10,000 examples. Each example is a 28x28 grayscale
image, associated with a label from 10 classes. It is relatively challenging
dataset and simulates the everyday computer vision tasks. The classes consist
of fashion objects T-shirt/top, Trouser, Pullover, Dress, Coat, Sandal, Shirt,
Sneaker, Bag and Ankle Boot.

  * •

KMNIST-10: Kuzushiji-MNIST-10 (KMNIST-10) (Clanuwat et al. 2018)consists of
70,000 28x28 pixels grayscale images of handwritten Japanese characters of
Hiragana. The subdivision of this dataset is 60,000 training samples and
10,000 testing samples. It is a well-balanced dataset across all classes and
is relatively difficult to learn as compared to MNIST. We use this to simulate
the federated settings.

  * •

FEMNIST: The FEMNIST dataset is the federated version of EMNIST dataset (Cohen
et al. 2017). It is a set of handwritten character digits derived from the
NIST Special Database 19 and converted to a 28x28 pixel image format and
dataset structure that directly matches the MNIST dataset. We used the
balanced version with ten single-digit classes between 0 and 9 inclusive, 26
uppercase alphabets and 11 lowercase alphabets. We federated this 47 classes
dataset for the simulation of real-world federated settings.

  * •

KMNIST 49: Kuzushiji-MNIST 49 is a much larger, but imbalanced dataset
containing 48 Hiragana characters and one Hiragana iteration mark. It is an
excellent example to simulate the universal problem of an imbalanced class
problem under federated settings. It consists of 49 classes 28x28 grayscale
images. It is a comparatively much larger dataset.

### Data distributions

(a) D1

(b) D2

(c) D3

(d) D4

(e) D5

Figure 1: Distribution of Categories across clients (Category ids on x-axis
and number of clients on y-axis)

We simulate various client data distribution conditions to compare the
algorithm. We take a total of 100 clients in the Federated system. We vary the
number of clients having a particular category. In all of our experiments, all
clients have a proper subset of categories varying from clients having a
single category to clients having half the number of total categories. There
are five distribution conditions (D1, D2, D3, D4, D5) which we use and have
been shown in figure 1. We share specific details in the Appendix.

### Settings

Figure 2: Performance comparison of proposed algorithms on distribution D5

All networks employed are multilayer perceptrons (MLP) with two hidden dense
Flipout layers with 100 units in case of MNIST, single hidden layer of 512
units in case of FMNIST and KMNIST-10 and a single hidden layer of 784 units
in case of FEMNIST-47 and KMNIST-49. Activation function Rectified Linear Unit
(ReLU) is employed between the hidden layers and input layers, while the
softmax activation function is employed in the final output layer. The final
output layer consists of 10 units in case of MNIST, FMNIST and KMNIST-10. In
FEMNIST and KMNIST-49 number of final layer units are 47 and 49 respectively.

We define two modes of experiments per algorithm where we set the value of the
maximum number of clients to sample. We define Mode A where N is kept at ten
and Mode B, where we keep N as equal to the number of categories in the
dataset. This allows us to explore conditions where we may want to sample as
few clients as possible. We will denote the algorithms for performance
strategy to be A1 and cost strategy to be A2.

Each client has 600 training samples, and batch size is 32 is used in the
execution of subroutine of local refinements for all experiments. In the case
of a random client selection method, which is the default FedAvg case, a total
of 10 clients are selected for participation in global training.

For all cases, the learning rate is used as 0.003, and a total of 50 rounds of
global refinements are performed using Stochastic Gradient Descent (SGD) with
Federated Averaging (FedAvg) method of updating the global model.

### Results

Dataset | FedAvg | Mode A - A1 | Mode A - A2 | Mode B - A1 | Mode B - A2 | Virtual MTL
---|---|---|---|---|---|---
MNIST | 0.7285$\pm$0.0092 | 0.9202$\pm$0.0007 | 0.8343$\pm$0.0080 | 0.9445$\pm$0.004 | 0.8371$\pm$0.0060 | 0.5711$\pm$0.0060
FMNIST | 0.5622$\pm$0.0230 | 0.7937$\pm$0.0020 | 0.7084$\pm$0.0050 | 0.8087$\pm$0.003 | 0.6829$\pm$0.0010 | 0.4432$\pm$0.0060
KMNIST-10 | 0.5776$\pm$0.0070 | 0.8071$\pm$0.0004 | 0.7586$\pm$0.0030 | 0.8129$\pm$0.007 | 0.7498$\pm$0.0040 | 0.4721$\pm$0.0060
Table 2: Accuracy of global model on test set using random and proposed algorithms on distribution D1 Dataset | Distribution | FedAvg | Mode A - A1 | Mode A - A2 | Mode B - A1 | Mode B - A2
---|---|---|---|---|---|---
FEMNIST | D2 | 0.5573$\pm$0.0130 | 0.4123$\pm$0.0005 | 0.6903$\pm$0.006 | 0.7537$\pm$0.002 | 0.6921$\pm$0.002
| D4 | 0.4123$\pm$0.023 | 0.2712$\pm$0.0007 | 0.5818$\pm$0.008 | 0.7023$\pm$0.001 | 0.6446$\pm$0.002
KMNIST-49 | D3 | 0.5211$\pm$0.0150 | 0.3972$\pm$0.0050 | 0.6213$\pm$0.004 | 0.6753$\pm$0.001 | 0.6286$\pm$0.001
| D5 | 0.4236$\pm$0.0270 | 0.2653$\pm$0.0080 | 0.5325$\pm$0.008 | 0.6157$\pm$0.005 | 0.5795$\pm$0.005
Table 3: Accuracy of global model on test set using random and proposed algorithms on KMNIST-49 and FEMNIST Distribution/(Classes) | Mode A-A1 | Mode A-A2 | Mode B-A1 | Mode B-A2
---|---|---|---|---
| Selected | Covered | Selected | Covered | Selected | Covered | Selected | Covered
D1 (10) | 10 | 10 | 3 | 10 | 10 | 10 | 3 | 10
D2 (47) | 10 | 24 | 6 | 47 | 47 | 47 | 6 | 47
D3 (49) | 10 | 24 | 6 | 49 | 49 | 49 | 6 | 49
D4 (47) | 10 | 14 | 10 | 39 | 47 | 47 | 19 | 47
D5 (49) | 10 | 14 | 10 | 39 | 49 | 49 | 19 | 49
Table 4: Description of clients selected (Selected) in each round and
categories covered (Covered) using the proposed algorithms on various
distributions. ( Highest number of clients selected is marked red and all
categories covered is marked in blue )

Here we describe the various insights about the experimental results as
presented in Tables 2 and 3.

We discuss the number of clients selected, as that reflects the communication
efficiency along with the model accuracy numbers under various conditions. We
further performed an ablation study which has been shared in the Appendix.

#### FedAvg

We pick a subset of 10 clients is selected randomly for global refinement. It
performs well when the distribution of classes is not skewed. However, for the
skewed environments of D1 with ten categories, we see a dip in performance as
depicted in Table 2. The deterioration is pronounced when a large number of
categories (47 and 49) are there as seen in distributions D2 and D3. The
primary reason is the lack of data coverage of all categories in the simulated
skewed environment is not guaranteed. The dataset conditions D4 and D5 show
the worst performance.

#### CatFedAvg - performance strategy

Here we primarily discuss the algorithm A1 which implements the model
performance strategy.
Mode A : We limit the total number of clients selected to $N=10$. In this
scenario, all ten categories were covered in case of MNIST, FMNIST and
KMNIST-10 under distribution D${1}$. In case of distribution D2, and D3 using
FEMNIST and KMNIST-49 only 24 categories out of 47 and 49 respectively were
covered while in D4 and D5 only 14 categories were covered as described in 4.
This results in poor performance of this strategy as the category coverage is
not enough.

Mode B: We don’t limit the number of clients selected in this mode. Hence,
coverage of all categories is guaranteed by this algorithm. We see that
clients are specifically selected for each category which leads to the
selection of 10 clients in distribution D1, 47 clients in distributions D2 and
D4 and 49 clients in distributions D3 and D5. This performs the best in
comparison to other algorithms as evident from Tables 2 and 3.

#### CatFedAvg - cost strategy

Here we primarily discuss the algorithm A2 which implements the communication
efficiency strategy.
Mode A: We limit the total number of clients selected to $N=10$. It is seen
that only three clients are selected in case of distribution D1 while six
clients are selected in case of D2 and D3. In D4 and D$,_{5}$ total clients,
selected are ten which is the maximum limit (N=10). Hence the coverage of all
categories is not guaranteed here, and only 39 categories were covered in each
round, but it performs better than the performance strategy variant in the
same mode.

Mode B: We don’t limit the number of clients selected in this mode. All
categories are covered with minimal probability of a category being selected
more than once. In this case, three clients are selected in distribution D1
while six clients are selected in distributions D2 and D3. In the extremely
skewed distributions D4 and D5, selected of 19 clients is sufficient for
complete coverage.

## Observations

### Model Accuracy

As described in 2 and 3, the performance of Algorithm 1 under mode B is the
best across the entire spectrum under all conditions.

If we denote the number of categories in global problem begin solved as C, the
relative performance of proposed algorithms is as below.

If N$\geq$C: Mode A-A1 $\approx$ Mode A-A2 $\approx$ Mode B-A1 $\approx$ Mode
B-A2

If N$<$C: Mode B-A1 $\geq$ Mode B-A2 $\geq$ Mode A-A2 $\geq$ Mode A-A1

### Communication Cost

Communication cost is related to the efficiency of a particular algorithm when
it comes to deployment, and the cost of refining the global model increases
with the number of clients participating in the training round. 4 describes
the number of clients selected in various distributions.

Considering all distributions, $D_{1}\dots D_{5}$, we can see that number of
clients participating is least in case of Mode A-A2. We limit the clients
participating in mode A-A1 to N. In contrast; Mode B-A2 has a comparatively
higher number of participating clients when the number of global categories is
less than N in mode A-A2.

Let C be the number of global categories. The following is the relative order
of algorithms in terms of communication cost expense.

If N$\geq$C: Mode A-A1 $\approx$ Mode B-A1 $\geq$ Mode A-A2 $\approx$ Mode
B-A2

If N$<$C: Mode B-A1 $\geq$ Mode B-A2 $\geq$ Mode A-A1 $\geq$ Mode A-A2

### Trade Off : Accuracy versus Communication

We can see that the better performance of mode B-A1 comes at a higher
communication cost. If we want the best performance, we need to compromise
with communication cost. Alternatively, if we desire a communication
efficiency, then Mode A-A2 is desirable. A better compromise is achieved with
both performance and communication cost may suggest Mode B-A2 as the best one.

## Conclusions & Future Work

In this work, we have proposed an approach that can help tradeoff
communication overheads with model accuracy with the usage of a simple and
efficient technique. This family of algorithm CatFedAvg has been shown to
perform better by 10AP in some cases than existing well-proven methods like
FedAvg and VIRTUAL MTL. The communication efficiency has seen a jump of 70AP
in some cases. We show a formal analysis that gives a framework to understand
how to work with the critical parameters for the tradeoff between
communication efficiency and model accuracy.

We have also shown the robustness of the approach with various statistical
heterogeneous conditions like global class imbalance and client distribution
variations. We believe that existing techniques that involve data augmentation
may not be feasible in production conditions. We would see this approach
combined with compression to deliver even more communication efficiency. It
would be interesting to use latency to be factored in when the initial larger
set of random clients are selected. We offer a technique that can possibly
work easily with Differential Privacy due to its inherent simplicity offering
privacy as well.

## References

  * Abadi et al. (2016) Abadi, M.; Chu, A.; Goodfellow, I. J.; McMahan, H. B.; Mironov, I.; Talwar, K.; and Zhang, L. 2016.  Deep Learning with Differential Privacy.  _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ .
  * Alistarh et al. (2017) Alistarh, D.; Grubic, D.; Li, J.; Tomioka, R.; and Vojnovic, M. 2017.  QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding.  In Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 30_ , 1709–1720. Curran Associates, Inc.  URL http://papers.nips.cc/paper/6768-qsgd-communication-efficient-sgd-via-gradient-quantization-and-encoding.pdf.
  * Arivazhagan et al. (2019) Arivazhagan, M. G.; Aggarwal, V.; Singh, A.; and Choudhary, S. 2019.  Federated Learning with Personalization Layers.  _ArXiv_ abs/1912.00818.
  * Auger et al. (2018) Auger, N.; Jugé, V.; Nicaud, C.; and Pivoteau, C. 2018.  On the Worst-Case Complexity of TimSort.  _ArXiv_ abs/1805.08612.
  * Brisimi et al. (2018) Brisimi, T. S.; Chen, R.; Mela, T.; Olshevsky, A.; Paschalidia, I. C.; ; and Shi, W. 2018.  Federated learning of predictive models from federated electronic health records.  _International journal of medical informatics_ vol. 112, pp. 59–67.
  * Caldas et al. (2018) Caldas, S.; Konecný, J.; McMahan, H.; and Talwalkar, A. 2018.  Expanding the Reach of Federated Learning by Reducing Client Resource Requirements.  _ArXiv_ abs/1812.07210.
  * Chen et al. (2018) Chen, F.; Luo, M.; Dong, Z.; Li, Z.; and He, X. 2018.  Federated Meta-Learning with Fast Convergence and Efficient Communication.  _arXiv: Learning_ .
  * Clanuwat et al. (2018) Clanuwat, T.; Bober-Irizar, M.; Kitamoto, A.; Lamb, A.; Yamamoto, K.; and Ha, D. 2018.  Deep Learning for Classical Japanese Literature.  _ArXiv_ abs/1812.01718.
  * Cohen et al. (2017) Cohen, G.; Afshar, S.; Tapson, J.; and Schaik, A. 2017.  EMNIST: an extension of MNIST to handwritten letters.  _ArXiv_ abs/1702.05373.
  * Custers et al. (2019) Custers, B.; Sears, A.; Dechesne, F.; Georgieva, I.; Tani, T.; and van der Hof, S. 2019.  EU Personal Data Protection in Policy and Practice .
  * Deng (2012) Deng, L. 2012.  The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web].  _IEEE Signal Processing Magazine_ 29: 141–142.
  * Deng et al. (2017) Deng, X.; Cui, C.; Fang, H.; Nie, X.; and Yin, Y. 2017.  Personalized Image Aesthetics Assessment.  In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_ , CIKM ’17, 2043–2046. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450349185.  doi:10.1145/3132847.3133052.  URL https://doi.org/10.1145/3132847.3133052.
  * Duan (2019) Duan, M. 2019.  Astraea: Self-Balancing Federated Learning for Improving Classification Accuracy of Mobile Deep Learning Applications.  _2019 IEEE 37th International Conference on Computer Design (ICCD)_ 246–254.
  * Gaff, Sussman, and Geetter (2014) Gaff, B. M.; Sussman, H. E.; and Geetter, J. 2014.  Federated Learning of Deep Networks using Model Averaging.  _Privacy and big data_ Computer, vol. 47, no. 6, pp. 7–9.
  * Han et al. (2020) Han, Y.; Wang, X.; Leung, V. C. M.; Niyato, D.; Yan, X.; and Chen, X. 2020.  Convergence of Edge Computing and Deep Learning: A Comprehensive Survey.  _IEEE Communications Surveys & Tutorials_ 22: 869–904.
  * Hard et al. (2018) Hard, A.; Rao, K.; Mathews, R.; Beaufays, F.; Augenstein, S.; Eichner, H.; Kiddon, C.; and Ramage, D. 2018.  Federated Learning for Mobile Keyboard Prediction.  _ArXiv_ abs/1811.03604.
  * Konecný et al. (2016) Konecný, J.; McMahan, H.; Yu, F.; Richtárik, P.; Suresh, A. T.; and Bacon, D. 2016.  Federated Learning: Strategies for Improving Communication Efficiency.  _ArXiv_ abs/1610.05492.
  * LeCun, Bengio, and Hinton (2015) LeCun, Y.; Bengio, Y.; and Hinton, G. 2015.  Deep learning.  _nature_ 521(7553): 436–444.
  * Li et al. (2017) Li, P.; Li, J.; Huang, Z.; Li, T.; Gao, C.-Z.; Yiu, S.-M.; and Chen, K. 2017.  Multi-key privacy-preserving deep learning in cloud computing.  _Future Generation Computer Systems_ 74: 76 – 85.  ISSN 0167-739X.  doi:https://doi.org/10.1016/j.future.2017.02.006.  URL http://www.sciencedirect.com/science/article/pii/S0167739X17302005.
  * Lueth (2018) Lueth, K. L. 2018.  State of the iot 2018: Number of iot devices now at 7b market accelerating .
  * Mao et al. (2017) Mao, Y.; C.You; J.Zhang; K.Huang; and B.Letaief, K. 2017.  A Survey on Mobile Edge Computing: The Communication Perspective.  _IEEE Communications Surveys Tutorials_ 19(4): 2322–2358.
  * McMahan et al. (2017) McMahan, H.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In _AISTATS_.
  * McMahan et al. (2016) McMahan, H.; Moore, E.; Ramage, D.; and y Arcas, B. A. 2016.  Federated Learning of Deep Networks using Model Averaging.  _ArXiv_ abs/1602.05629.
  * Mohri, Sivek, and Suresh (2019) Mohri, M.; Sivek, G.; and Suresh, A. T. 2019.  Agnostic Federated Learning.  In _ICML_.
  * Shi et al. (2016) Shi, W.; J.Cao; Q.Zhang; Y.Li; and L.Xu. 2016.  Edge Computing: Vision and Challenges.  _IEEE Internet of Things Journal_ 3(5): 637–646.
  * Stich, Cordonnier, and Jaggi (2018) Stich, S.; Cordonnier, J.-B.; and Jaggi, M. 2018.  Sparsified SGD with Memory.  In _NeurIPS_.
  * Tao and Li (2018) Tao, Z.; and Li, Q. 2018.  eSGD: Communication Efficient Distributed Deep Learning on the Edge.  In _USENIX Workshop on Hot Topics in Edge Computing (HotEdge 18)_. Boston, MA: USENIX Association.  URL https://www.usenix.org/conference/hotedge18/presentation/tao.
  * Wang et al. (2018) Wang, H.; Sievert, S.; Liu, S.; Charles, Z. B.; Papailiopoulos, D.; and Wright, S. 2018.  ATOMO: Communication-efficient Learning via Atomic Sparsification.  _ArXiv_ abs/1806.04090.
  * Xiao, Rasul, and Vollgraf (2017) Xiao, H.; Rasul, K.; and Vollgraf, R. 2017.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms.  _ArXiv_ abs/1708.07747.
  * Zhao et al. (2018) Zhao, Y.; Li, M.; Lai, L.; Suda, N.; Civin, D.; and Chandra, V. 2018.  Federated Learning with Non-IID Data.  _ArXiv_ abs/1806.00582.