#  HideNseek: Federated Lottery Ticket via
Server-side Pruning and Sign Supermask

###### Abstract

Federated learning alleviates the privacy risk in distributed learning by
transmitting only the local model updates to the central server. However, it
faces challenges including statistical heterogeneity of clients’ datasets and
resource constraints of client devices, which severely impact the training
performance and user experience. Prior works have tackled these challenges by
combining personalization with model compression schemes including
quantization and pruning. However, the pruning is data-dependent and thus must
be done on the client side which requires considerable computation cost.
Moreover, the pruning normally trains a binary supermask $\in\\{0,1\\}$ which
significantly limits the model capacity yet with no computation benefit.
Consequently, the training requires high computation cost and a long time to
converge while the model performance does not pay off. In this work, we
propose HideNseek which employs one-shot data-agnostic pruning at
initialization to get a subnetwork based on weights’ synaptic saliency. Each
client then optimizes a sign supermask $\in\\{-1,+1\\}$ multiplied by the
unpruned weights to allow faster convergence with the same compression rates
as state-of-the-art. Empirical results from three datasets demonstrate that
compared to state-of-the-art, HideNseek improves inferences accuracies by up
to 40.6% while reducing the communication cost and training time by up to
39.7% and 46.8% respectively.

##  1 Introduction

Federated learning 18 improves privacy protection by decoupling the need for a
central data repository from learning distributed datasets. Each client
uploads its local model trained with local datasets to a central server that
maintains a global model. The server updates the global model via aggregating
the clients’ updates and sends the new model to the clients. These processes
are iterated until the model converges or the predefined cycle ends.

While improving privacy protection, this paradigm also faces challenges such
as statistical heterogeneity, which refers to the non-IID distribution of the
data among clients, impacting the global model convergence if data from
different clients are too diverged. Some works address statistical
heterogeneity by introducing various learning techniques for personalization
8, 22, 17, 10, 26.

Another major challenge faced by federated learning is the resource
constraints, which refer to the limited computation capacity and transmission
bandwidth of the client devices. The limited resource restricts the model size
that can be trained in the client devices and transmitted timely to the server
for aggregation. Several recent works have surged to address this challenge by
adapting training procedures 16, 21 and employing model compression schemes 7,
13, 3.

Lately, FedMask 15 tackles both statistical heterogeneity and resource
constraints by employing a “masking is training” philosophy based on the
lottery ticket hypothesis (LTH) 9. FedMask prunes the local model to comply
with the resource constraints. Then, the client learns a sparse local binary
supermask for personalization to alleviate the statistical heterogeneity
across clients.

However, exiting methods face several challenges. First, current pruning
methods in federated setup are mostly data-dependent and thus have to be
performed on the client-side. Hence the client devices with limited resources
cannot avoid the considerable computation cost. Second, such pruning methods
commonly employ the binary supermask which essentially is unstructured pruning
that brings no computational advantage yet limits the model capacity.
Consequently, the model performance is limited, yet requires high computation
cost and a long convergence period.

Therefore, in this paper, we propose HideNseek, a statistical heterogeneity-
aware federated learning framework that provides computation and communication
efficiency powered by sign supermask 25. Specifically, we make the following
contributions.

  * •

HideNseek proposes a federated version of LTH with sign optimization for the
first time. Compared with the commonly used binary supermask, our approach
provides higher accuracy and faster convergence.

  * •

HideNseek performs server-side one-shot pruning at initialization by employing
an iterative data-agnostic approach based on synaptic saliency of the weights’
signs. As such, HideNseek greatly alleviates the computation burden and
communication cost for the clients with limited capacities.

  * •

Empirical results on varied datasets demonstrate that HideNseek outperforms
the state-of-the-art methods in inference accuracy by up to 40.6% while
reducing the communication cost and training time by up to 39.7% and 46.8%
respectively.

##  2 Background & Objective Formulation

In this section, we begin with the background on federated learning and LTH
and formulate the objective of data-agnostic pruning for federated learning.

###  2.1 Federated Learning

In federated learning, a deep neural network must be learned in a distributed
fashion. This is achieved by a central server aggregating copies of the
network weights learned among clients on their local datasets. The learning
objective is to find weights $w$ that minimize the empirical loss across
clients

$\min_{w}F(w)=\sum_{k=1}^{K}\frac{n_{k}}{n}\mathcal{L}[f(x_{k};w),y_{k}]$ (1)

where the network $f(\cdot;w)$ is a composite function of layers parametrized
by vectorized weights $w\in\mathbb{R}^{d}$ and $\mathcal{L}$ is the empirical
loss function which measures the ability to approximate the function
generating the local dataset $(x_{k},y_{k})$ of client $k$. $n_{k}$ is the
number of local samples and $n=\sum_{k}n_{k}$ is the total number of samples
across all the $K$ clients.

A prior work 18 provides the widely used FedAvg to solve this objective via
distributed SGD. In each communication round $t$, the central server selects a
subset of $c\ll K$ clients and sends them a copy of the global weights
$w^{t}$. The clients modify their local copy of the weights $w_{k}^{t}$ by
minimizing the empirical loss on local datasets to obtain $w_{k}^{t+1}$ and
transmit them back to the server. The server updates the global weights by
simply averaging the clients’ weights

$w^{t+1}=\frac{1}{c}\sum_{k=1}^{c}w_{k}^{t+1}$ (2)

Several problems arise in a real-world deployment. Firstly, the clients incur
communication costs due to weight transmission and computation costs due to
local weight optimization. Secondly, the local datasets are not independent
and identically distributed (non-IID) so the global weights must generalize
well among clients. Some works have modified their learning objective(s) to
address these problems (see Section 6).

###  2.2 Lottery Ticket Hypothesis

LTH 9 is a nascent avenue in machine learning that can tackle the
aforementioned issues in federated learning. It states that a randomly
initialized neural network contains a subnetwork called a winning ticket when
trained in isolation, performs as well as the original network. A more
ambitious extension comes from 20 which states that a sufficiently
overparametrized network contains a winning ticket at a randomly initialized
state. Furthermore, this winning ticket can be determined via freezing the
weights at random initialization $w^{0}$ and pruning a subset of these weights
to find a sparse subnetwork. To improve the learning performance, 5 suggest
applying a transform function $U\in\mathcal{U}$ to the weights to further
minimize the empirical loss. The learning objective is thus

$\min_{U\in\mathcal{U},||m||_{0}=S}\mathcal{L}[f(x;U(w^{0}\odot m)),y]$ (3)

where $m\in\\{0,1\\}^{d}$ is a binary supermask with sparsity level $S$ and
the same dimensionality as the weights. The winning ticket is represented as
the element-wise multiplication of the weights and the supermask, i.e.,
$w^{0}\odot m$. However, optimizing Eq. (3) is computationally intractable due
to the large dimensionality of weights and transformation space $\mathcal{U}$.
Hence, they propose to decouple the optimization into two stages. The first
stage is the pruning phase where a binary supermask must be found to sparsify
the model by optimizing the following

$\hat{m}\in\min_{||m||_{0}=S}R(f(x;w^{0}\odot m))$ (4)

where $R$ is a scoring function that measures the ability of the binary
supermask $m$ to isolate the winning ticket from the model. The second stage
is the training phase where a weight transformation is learned to minimize the
empirical loss

$\hat{U}\in\min_{U\in\mathcal{U}}\mathcal{L}[f(x;U(w^{0}\odot\hat{m})),y]$ (5)

###  2.3 Objective Formulation

In essence, LTH applies a “masking is training” philosophy where an optimal
sparse subnetwork must be learned without modifying the weights. Given the
communication and computation efficiency brought by this idea (discussed in
subsequent sections), we propose to adopt this hypothesis for the federated
setting. However, the weight transformation space $\mathcal{U}$ is very vast.
Following 5, we confine the space to sign flipping transformation space
$\mathcal{U}_{s}\in\mathcal{U}$ where a transformation $U(w,s)=w\odot s$
element-wise multiplication of the sign supermask $s\in\\{-1,+1\\}^{d}$ to the
weights $w$. The updated learning objective of our work is

$\min_{m,s}F(m,s)=\sum_{k=1}^{K}\frac{n_{k}}{n}\mathcal{L}[f(x_{k};w^{0}\odot
m\odot s),y_{k}]$ (6)

The subsequent sections elaborate on a federated learning algorithm to solve
the above objective.

##  3 Methodology

###  3.1 HideNseek

In this work, we propose an efficient federated learning algorithm called
HideNseek by solving for federated adaptation of the LTH. Figure 1 depicts an
overview of the framework. As mentioned earlier, the learning process can be
performed in two phases.

In the first phase, the server first performs pruning-at-initialization to
isolate the winning ticket (1). Since the server does not possess training
data, a data-agnostic pruning method is applied. Following 23, we measure the
score of the signs of weights via their synaptic saliency (see Section 3.4),
and employ global structured pruning for hardware efficiency.

In the second phase, an optimal weight transformation has to be learned to
minimize the empirical loss in a federated manner. In each training step $t$,
the server sends the global sign supermask $s^{t}$ to the selected clients (2)
which initializes a local sign supermask $s^{t+1}_{k}$. The clients then
freeze the model weights and optimize the local sign supermask by minimizing
the empirical loss using Eq. (6) (3). As such, a sign flipping transformation
is learned and sent back to the server (4). The server then aggregates these
local supermasks using Eq. (8) (5).

After the training phase, each client multiplies the aggregated sign supermask
to its weights to get the final local model (6). Algorithm 1 (in Appendix A)
summarizes the processes with highlighted details elaborated in the following
paragraphs.

Figure 1: Overview of HideNseek framework

###  3.2 Personalization

The output layer of the model cannot be simply optimized for its signs because
the weight magnitudes must be scaled for stable training. We thus split our
models into feature extractors which constitute all the hidden layers and
classifier which is the output layer. The weights are frozen and the sign
supermask is learned only for the feature extractor while the weights of the
classifier are modifiable, as the optimization of the local data. Aligned with
prior works 26, our work further reinforces personalization among clients.

###  3.3 Sign Flipping Transformation

Optimizing the sign supermask is crucial to learning in our algorithm. As
such, we handle certain preliminaries to achieve the optimization. As
mentioned earlier, a model can be expressed as a composition of layers
performing operations of vectorized weights. As an example, let us consider
the fully connected layer. Note that the bias term has been omitted for
brevity. A fully-connected layer $l$ can be expressed as
$y^{[l]}=(w^{[l]}\odot s^{[l]})\cdot x^{[l]}$, where
$y^{[l]}\in\mathbb{R}^{i}$ is the output, $x^{[l]}\in\mathbb{R}^{j}$ is the
input, and $w^{[l]}\in\mathbb{R}^{i\times j}$ is the weights. We thus handle
the learning of a sign supermask $s^{[l]}\in\\{-1,+1\\}^{i\times j}$ with the
same dimensionality as the weights.

However, the traditional SGD optimization cannot be applied to the sign
supermasks due to their discrete nature. Hence, we implement a straight-
through estimator 2 with a real-valued sign supermask
$\hat{s}^{[l]}\in\mathbb{R}^{i\times j}$. In the forward pass, $\hat{s}$ is
quantized using the piecewise sign function

$s_{ij}=\operatorname{sign}({\hat{s}_{ij}})=\begin{cases}+1&\hat{s}_{ij}\geq
0\\\ -1&\hat{s}_{ij}<0\end{cases}$ (7)

where $s_{ij}$ is an element in the $i$-th row and $j$-th column of the sign
supermask $s$. The gradients of $s$ in the backward pass are computed as
$\nabla_{s}\mathcal{L}=(\nabla_{y}\mathcal{L}\cdot x^{T})\odot w$. Given that
the sign function is not differentiable, directly assigning the gradients from
the quantized sign supermask to the real sign supermask (i.e.,
$\nabla_{\hat{s}}\mathcal{L}=\nabla_{s}\mathcal{L}$) would lead to large
gradient variance 6. Hence, we employ a hyperbolic tangent function, denoted
as $\tanh(\cdot)$, for a continuous approximation of the sign function for the
backward pass, $s_{ij}=\tanh(\hat{s}_{ij})$. This would allow us to compute
the gradients of the real sign supermask $\hat{s}$ from the binary sign
supermask $s$ as $\nabla_{\hat{s}}\mathcal{L}=\Psi\odot\nabla_{s}\mathcal{L}$,
where $\Psi$ is the gradient matrix of the hyperbolic tangent function with
values explicitly calculated as $\Psi_{ij}=(1-\hat{s}_{ij}^{2}$).

Since the clients transmit quantized sign supermasks to the server for
communication efficiency, we employ the following sign aggregation scheme to
obtain the real-valued sign supermask at the server

$\hat{s}=\operatorname*{arctanh}\Bigg{(}\sum_{k}\frac{n_{k}}{n}s_{k}\Bigg{)}$
(8)

###  3.4 Server-side Pruning

Another crucial aspect in HideNseek is the pruning phase where the winning
ticket must be isolated from the network. Following 15, we employ one-shot
pruning at initialization but perform it on the server-side to reduce the load
on the clients. As the server does not contain any training data, we employ a
data-agnostic iterative pruning approach 23 where the prune scores are
determined based on the weight’s synaptic saliency. Given that the weights are
frozen during training the sign supermask, we measure the synaptic saliency of
the sign of a given weight in a model with $L$ layers is as follows

$R_{\text{SF}}(s^{[l]}_{ij})=\left[\mathds{1}^{\intercal}\prod_{h=l+1}^{L}\left|s^{[h]}\odot
w^{[h]}\right|\right]_{i}\left|s^{[l]}_{ij}\odot
w^{[l]}_{ij}\right|\left[\prod_{h=1}^{l-1}\left|s^{[h]}\odot
w^{[h]}\right|\mathds{1}\right]_{j}$ (9)

In essence, the synaptic saliency of a weight’s sign is the product of all the
weights multiplied by their respective sign supermasks that have the weight’s
sign within the path from the input to the output layer. To further promote
hardware efficiency, we employ global structured pruning by scoring groups of
weights by channels in convolutional layers and nodes in fully-connected
layers. The prune score for the $i$-th channel or node in a layer as $\lVert
w^{[l]}_{i}\odot\nabla_{s}R_{SF,i}^{[l]}\rVert_{2}$. Additionally, we keep the
first few layers and only prune from the latter layers of the model with a
prune rate $p_{r}$.

###  3.5 State of the Art

FedMask 15 is the closest in spirit to our work. However, its pruning method
is data-dependent, and hence, have to be performed on client devices,
resulting in increased computational load on the resource-constrained clients.
Additionally, its weight transformation space is confined to the binary
supermasking $\mathcal{U}_{b}\in\mathcal{U}$, where a local binary supermask
$m_{k}\in\\{0,1\\}$ is learned in the training stage in contrast to the binary
sign supermask. Effectively, FedMask further performs unstructured pruning
during the training stage with no communication or computation advantage.
Contrarily, HideNseek maintains all the weights after the pruning stage
allowing for a greater model capacity.

##  4 Experimental Setup

###  4.1 Datasets & Models

We evaluate HideNseek on two applications, including image classification and
human activity recognition, using the EMNIST 4 and HAR 1 datasets,
respectively. EMNIST is a handwritten character recognition task involving
28$\times$28 grayscale images belonging to 62 classes (upper and lower case
letters and digits) already partitioned according to the writers. Thus, each
writer is considered a client. The HAR dataset consists of sensor data
(flattened into an 1152-valued vector) generated by users performing six
possible actions (i.e., classes). To further study the impact of statistical
heterogeneity on the performance, we follow prior works 26 and simulate Non-
IID data on MNIST 14 dataset via Dirichlet sampling $Dir(\alpha)$, where a
smaller value of $\alpha$ denotes greater heterogeneity (see Figure 5 in
Appendix B). We employ the VGG9 and multilayer perceptron (MLP) for the image
classification and activity recognition tasks, respectively, with model
configurations (see Table 5 in Appendix C). We enable pruning for the last
four convolutional layers in VGG9 and the first two hidden layers in MLP.

###  4.2 System Implementation

We implement HideNseek and baselines with PyTorch (v1.8.0) 19 on a server
equipped with a single Nvidia RTX 3090 GPU. We experiment with a total of $K$
clients set to 160 and 320 for MNIST and EMNIST datasets and 30 for the HAR
dataset. We randomly sample $\rho=10\%$ of participating clients that perform
$E=5$ local epochs during each communication round with a total of 300 rounds
for MNIST and EMNIST and 200 rounds for HAR. Weights and sign supermasks are
initialized using Kaiming uniform 11 and uniform distribution $U(-1,1)$
respectively. We perform one-shot pruning for 100 iterations in HideNseek
(according to 23) and one epoch for FedMask and Signed on the last four layers
of the VGG9 and the first two hidden layers of the MLP with the pruning rate
$p_{r}=0.8$ (80% of the weights are kept). We employ the SGD optimizer with a
learning rate $\eta=0.001$ for FedAvg, FedMask and Signed, $\eta=0.01$ for
BNNAvg and $\eta=10$ for HideNseek, and momentum $\mu=0.9$ for all algorithms
chosen empirically. We repeat every experiment thrice with different seeds for
reproducibility.

###  4.3 Baselines

We evaluate HideNseek by comparing its performance against several baselines.
We include FedAvg 18 to realize the performance of the model when trained at
full capacity. FedMask 15 is the closest in spirit to our work and state-of-
the-art when it comes to applying LTH for the federated setting with client-
side pruning and learning binary supermasks. We also borrow their BNNAvg
baseline which applies FedAvg to train binarized neural networks (BNN) 6 with
the weights and activations quantized by their signs. We also implement an
extension of FedMask we call Signed where we replace binary supermask with
sign supermask and change their binarizing function from sigmoid to tanh.

##  5 Results

###  5.1 Training performance

We first compare the training performance by reporting the inference
accuracies in Table 1 between HideNseek and the baselines. The inference
accuracies were measured by taking a weighted average of the client’s
inference accuracies based on their local test data, which are weighted based
on the number of test samples in their local dataset. While HideNseek performs
expectedly worse than the FedAvg which trains the full model and serves as the
upper bound in training performance, HideNseek in general, outperforms
FedMask, Signed and BNNAvg across tasks. It is worthwhile to mention that the
performance improvements are significant for HAR and MNIST datasets with lower
heterogeneity at $\alpha=\\{1,10\\}$ with inference accuracies higher by
24.1-40.6% for HideNseek compared to FedMask. HideNseek performance gradually
degrades for MNIST ($\alpha=0.1$) with higher heterogeneity and EMNIST with a
large number of classes. This finding can be attributed to the fact that
HideNseek employs a shared global feature extractor among the baselines that
utilize pruning. While it is challenging to learn generalized features among
clients, the performance is still approximate to both FedMask and Signed which
learn a more personalized feature extractor. Yet, HideNseek scores higher than
FedMask by 2.09% and 19.62% for EMNIST and MNIST($\alpha=0.1$).

Table 1: Inferences accuracies of baselines and HideNseek on different datasets.  Algorithm | EMNIST | MNIST | HAR
---|---|---|---
| Non-IID | $\alpha=0.1$ | $\alpha=1$ | $\alpha=10$ | Non-IID
FedAvg |  94.41 $\pm$ 0.06 |  98.81 $\pm$ 0.10 |  99.23 $\pm$ 0.05 |  99.38 $\pm$ 0.05 |  93.37 $\pm$ 0.22
BNNAvg |  29.09 $\pm$ 1.27 |  51.80 $\pm$ 0.45 |  54.39 $\pm$ 0.16 |  64.62 $\pm$ 0.15 |  66.50 $\pm$ 0.57
FedMask |  67.09 $\pm$ 0.23 |  57.73 $\pm$ 0.21 |  67.46 $\pm$ 0.40 |  84.41 $\pm$ 0.12 |  81.93 $\pm$ 0.55
Signed |  69.99 $\pm$ 0.76 |  59.45 $\pm$ 0.26 |  72.17 $\pm$ 0.19 |  86.69 $\pm$ 0.12 |  76.30 $\pm$ 1.04
HideNseek | 69.18 $\pm$ 5.58 | 77.35 $\pm$ 0.81 | 94.97 $\pm$ 0.64 | 96.69 $\pm$ 0.56 | 90.60 $\pm$ 0.30

We further compare the training performances by plotting the inference
accuracies against the communication round. In the case of HAR dataset in
Figure 2(a) and MNIST dataset in Figure 3, HideNseek converges faster than
FedMask, Signed and BNNAvg. Whereas HideNseek experiences higher volatility in
training compared to the baselines in EMNIST dataset in Figure 2(b) and to
some extent in MNIST dataset with higher heterogeneity at $\alpha=0.1$ in
Figure 3(a). Both of which again point to the difficulty in training a shared
global sign supermask under heterogeneous conditions.

(a) HAR

(b) EMNIST

Figure 2: Performance on Non-IID EMNIST and HAR datasets.

(a) $\alpha=0.1$

(b) $\alpha=1$

(c) $\alpha=10$

Figure 3: Performance on MNIST with different data heterogeneities.

###  5.2 Communication Cost

We then compare the communication cost for each client by measuring the upload
and download sizes in MB for each client during each communication round as
shown in Table 2. First, BNNAvg with binary parameters is four times smaller
than FedAvg because 1 byte is the smallest element size to represent a
parameter in PyTorch. FedMask and Signed have a lower upload cost compared to
BNNAvg due to client-side pruning. HideNseek further reduces the download cost
thanks to server-side pruning. Furthermore, prune scores are more granular in
HideNseek compared to FedMask and Signed. This leads to smaller subnetworks
since we drop all weights with scores equal to the threshold (see line 1 in
Algorithm 1). Overall, HideNseek demonstrates a reduction in communication
cost compared to the second-best performance (FedMask) by 20.9-39.7% times
across all tasks.

Table 2: Communication cost in MB for each client in a communication round  Algorithm | EMNIST | MNIST | HAR
---|---|---|---
| upload | download | upload | download | upload | download
FedAvg | 4.53 | 4.53 | 4.33 | 4.33 | 1.44 | 1.44
BNNAvg | 1.07 | 1.07 | 1.07 | 1.07 | 0.36 | 0.36
FedMask | 0.74 | 1.07 | 0.70 | 1.07 | 0.27 | 0.36
Signed | 0.74 | 1.07 | 0.70 | 1.07 | 0.27 | 0.36
HideNseek | 0.70 | 0.70 | 0.70 | 0.70 | 0.19 | 0.19
Table 3: Training times in seconds of baselines and HideNseek measure on Nvidia RTX 3090.  Algorithm | EMNIST | MNIST | HAR
---|---|---|---
FedAvg |  475.61 $\pm$ 0.54 |  587.43 $\pm$ 0.50 |  49.31 $\pm$ 0.15
BNNAvg |  580.64 $\pm$ 0.42 |  693.76 $\pm$ 1.82 |  61.10 $\pm$ 0.42
FedMask |  1150.77 $\pm$ 5.53 |  1200.71 $\pm$ 3.86 |  83.52 $\pm$ 0.12
Signed |  979.90 $\pm$ 1.78 |  908.93 $\pm$ 3.46 |  76.34 $\pm$ 0.48
HideNseek | 612.33 $\pm$ 2.35 | 705.16 $\pm$ 2.61 | 64.44 $\pm$ 0.72
Table 4: Inference accuracies when varying the number of active clients per communication round.  Algorithm | K=10 | K=20 | K=40
---|---|---|---
FedAvg |  99.23 $\pm$ 0.05 |  99.19 $\pm$ 0.05 |  99.25 $\pm$ 0.07
BNNAvg |  54.39 $\pm$ 0.16 |  58.17 $\pm$ 0.16 |  61.78 $\pm$ 0.24
FedMask |  67.46 $\pm$ 0.40 |  69.51 $\pm$ 0.22 |  72.31 $\pm$ 0.05
Signed |  72.17 $\pm$ 0.19 |  73.02 $\pm$ 0.15 |  73.48 $\pm$ 0.01
HideNseek | 94.97 $\pm$ 0.64 | 93.40 $\pm$ 0.61 | 91.05 $\pm$ 0.87

(a) $\alpha=0.1$

(b) $\alpha=1$

(c) $\alpha=10$

Figure 4: Performance on MNIST with different pruning rates.

###  5.3 Computation Cost

We report the computation cost by measuring the total training time on a
single Nvidia RTX 3090 GPU (Table 3). FedAvg is the fastest primarily because
of that it does not utilize any latent weights, such as the masks in the case
of Signed, FedMask and HideNseek. Even BNNAvg is slower than FedAvg since the
quantization must be performed at runtime and there is no built-in
optimization in PyTorch when dealing with 1-bit parameters. Still, HideNseek
has lower training time compared to FedMask and Signed because these baselines
require the client-side one-shot pruning each time a new client participates
in the training. Additionally, FedMask is more computationally expensive as it
employs sparsity regularization term. Overall, HideNseek demonstrates a
reduction in computation costs compared to FedMask by 22.8-46.8% across all
tasks.

###  5.4 Active Clients

We now evaluate the impact of the number of active clients per communication
round on the training performance. Table 4 demonstrates the inference
accuracies among clients on the MNIST ($\alpha=1$) with different numbers of
active clients $K=\\{10,20,40\\}$. While most baselines experience an
improvement in accuracy with more active clients, HideNseek experiences a
minor drop of 3.92% in performance when $K$ quadruples. Still, HideNseek
demonstrates better performance compared to BNNAvg, FedMask and Signed by a
significant margin. This signifies the scalability and partly backs up the
robustness of heterogeneity demonstrated in Figure 3.

###  5.5 Pruning Rate

From the results discussed above, it is evident that the VGG9 model is
overparametrized for the MNIST dataset proven by the high inference accuracies
of FedAvg and HideNseek. Hence, we tried a drastically more aggressive pruning
rate of $p_{r}=0.2$ compared to previous experiments where $p_{r}=0.8$. As
shown in Figure 4, the drop in performance is very marginal in the less
heterogeneous datasets $\alpha=\\{1,10\\}$, while there is a significant drop
in the more heterogeneous dataset $\alpha={0.1}$. This demonstrates that the
computation and communication advantage of HnS over baselines is larger than
the prior results without a noticeable accuracy drop in some cases when using
a high prune rate.

##  6 Related Work

Statistical Heterogeneity. After the seminal work on federated learning 18,
immediate advancements sought to tackle the problem of statistical
heterogeneity in federated learning by adapting personalization schemes.
PerFedAvg 8 integrates a model-agnostic meta-learning approach into FedAvg for
personalization. MOCHA 22 introduces federated multi-task learning where each
client is considered as a task. A plethora of works 17, 10, 26 has also
applied knowledge distillation to learn a global surrogate model which teaches
the clients’ local models. 15 performs personalization by allowing each client
to learn a local binary supermask. In contrast, we employ personalization by
globally sharing all hidden layers of the model while fine-tuning the final
layer to the clients’ local data. This allows HideNseek to stably train the
model by modifying weight magnitudes for a small subset of the weights while
quantizing the updates transmitted for all the hidden layers. As such,
HideNseek reduces the communication cost while maintaining better ability in
terms of learning data with varied heterogeneities as shown in Figure 3.

Communication and Computation Cost. Another significant issue in federated
learning is the increased communication and computation cost on client devices
when optimizing and transmitting the weights. FedProx 16 alleviates this issue
via allowing training preemption and partial updates, and FedPAQ 21 allows
periodic averaging and quantizing model updates. Several works have also
introduced variations of pruning and dropout 7, 13, 3 for model compression.
For example, FedMask applies LTH 9 by performing one-shot pruning at the
client-side and learning a local binary supermask that is quantized during
communication. However, the binary supermask learned is essentially
unstructured pruning with no computational advantage and limits model
capacity. We thus replace the binary supermask with a sign supermask for
faster convergence and employ data-agnostic pruning at the server to reduce
computational load on the client.

##  7 Conclusion & Future Work

In this work, we have introduced HideNseek which applies the lottery ticket
hypothesis under the federated setting by optimizing the signs of a
synaptically salient subnetwork of the model. To further reduce computation
load on the client, we perform one-shot pruning at initialization on the
server-side using the data-agnostic approach and optimize a sign supermask
that is quantized when transmitting model updates. Empirical results suggest
that HideNseek demonstrates better inference accuracy than the state-of-the-
art in general while considerably reducing the communication cost and training
time. Nevertheless, an imminent challenge faced is that the memory cost
incurred by employing straight-through-estimators is substantial. Therefore,
in the future, we will explore the efficacy brought by employing a binary
optimizer 12 that only modifies signs of weights without the need for latent
parameters like the sign supermasks.

##  8 Broader Impact

In this work, we propose an algorithm in the field of federated learning which
originated from the need to develop deep learning applications in the wake of
recent advances in data protection regulations such as the GDPR 24.
Furthermore, we explore an approach to reduce communication and computation
costs on battery-powered mobile devices to reduce environmental impact. While
our work demonstrates energy-saving implications from a theoretical
standpoint, we hope future works will further delve into system optimization
geared towards energy conservation.

## References

  * Anguita et al. [2013] Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra Perez, and Jorge Luis Reyes Ortiz.  A public domain dataset for human activity recognition using smartphones.  In _Proceedings of the 21th international European symposium on artificial neural networks, computational intelligence and machine learning_ , 2013\.
  * Bengio et al. [2013] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _arXiv preprint arXiv:1308.3432_ , 2013.
  * Bouacida et al. [2021] Nader Bouacida, Jiahui Hou, Hui Zang, and Xin Liu.  Adaptive federated dropout: Improving communication efficiency and generalization for federated learning.  In _IEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2021.
  * Caldas et al. [2018] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečnỳ, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar.  Leaf: A benchmark for federated settings.  _arXiv preprint arXiv:1812.01097_ , 2018.
  * Chen et al. [2022] Xiaohan Chen, Jason Zhang, and Zhangyang Wang.  Peek-a-boo: What (more) is disguised in a randomly weighted neural network, and how to find it efficiently.  In _International Conference on Learning Representations_ , 2022.
  * Courbariaux et al. [2016] Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1.  _arXiv preprint arXiv:1602.02830_ , 2016.
  * Diao et al. [2021] Enmao Diao, Jie Ding, and Vahid Tarokh.  HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients.  In _International Conference on Learning Representations_ , 2021.
  * Fallah et al. [2020] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Frankle and Carbin [2018] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  _arXiv preprint arXiv:1803.03635_ , 2018.
  * Gong et al. [2021] Xuan Gong, Abhishek Sharma, Srikrishna Karanam, Ziyan Wu, Terrence Chen, David Doermann, and Arun Innanje.  Ensemble attention distillation for privacy-preserving federated learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1026–1034, 2015.
  * Helwegen et al. [2019] Koen Helwegen, James Widdicombe, Lukas Geiger, Zechun Liu, Kwang-Ting Cheng, and Roeland Nusselder.  Latent weights do not exist: Rethinking binarized neural network optimization.  _Advances in neural information processing systems_ , 32, 2019.
  * Horvath et al. [2021] Samuel Horvath, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos Venieris, and Nicholas Lane.  Fjord: Fair and accurate federated learning under heterogeneous targets with ordered dropout.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11), 1998.
  * Li et al. [2021] Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen.  Fedmask: Joint computation and communication-efficient personalized federated learning via heterogeneous masking.  In _Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems_ , pages 42–55, 2021.
  * Li et al. [2020] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  In _Proceedings of Machine Learning and Systems_ , volume 2, pages 429–450, 2020.
  * Lin et al. [2020] Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi.  Ensemble distillation for robust model fusion in federated learning.  volume 33, pages 2351–2363, 2020.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , 2017.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Ramanujan et al. [2020] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari.  What’s hidden in a randomly weighted neural network?  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Reisizadeh et al. [2020] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani.  Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2021–2031. PMLR, 2020.
  * Smith et al. [2017] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar.  Federated multi-task learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Tanaka et al. [2020] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  33:6377–6389, 2020.
  * Viorescu et al. [2017] Razvan Viorescu et al.  2018 reform of eu data protection rules.  _European Journal of Law and Public Administration_ , 4(2):27–39, 2017.
  * Zhou et al. [2019] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski.  Deconstructing lottery tickets: Zeros, signs, and the supermask.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhu et al. [2021] Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou.  Data-free knowledge distillation for heterogeneous federated learning.  In _International Conference on Machine Learning_ , pages 12878–12889. PMLR, 2021.

##  Appendix A Algorithm

Algorithm 1 summarizes the training procedure of HideNseek. Note that
$\mathds{1}$ in line 1 is a threshold function (as opposed to the identity
matrix in Equation 9).

1 Procedure  _ServerRuns_ :

Input: set of K clients $S\leftarrow\\{C_{1},C_{2},\dots,C_{K}\\}$ with data
$(x_{k},y_{k})$ on $k$-th client device

2 randomly intialize DNN with weights $w^{0}$

3 initialize the global sign mask $s^{0}$ with signs of $w^{0}$

$w^{0}\leftarrow$ ServerPruning($w^{0},s^{0}$)

// one-shot pruning 1 in Figure 1

4 for  _each round $t=1,2,\dots,T$_ do

$c\leftarrow\max(K\times\rho,1)$

// select $c$ active clients from $K$ available clients with random sampling
rate $\rho$

$S_{t}\leftarrow\\{C_{1},C_{2},\dots,C_{c}\\}$

// selected clients

5 for  _$C_{k}\in S_{t}$ in parallel_ do

$s_{k}^{t+1}\leftarrow$ ClientUpdate($C_{k},s^{t}\odot s^{t}_{k}$)

// 2 and 4 in Figure 1

6

$s^{t+1}\leftarrow$ aggregate($\\{s^{t+1}_{1},\dots,s^{t+1}_{c}\\}$)

// using Eq. (8) (5 in Figure 1)

7

8

9Function  _ServerPruning( $w,s$)_:

// No. of iterations set to recommended value following [Tanaka et al., 2020]

10 for  _each round $e=1,2,\dots 100$_ do

11 $S_{SF,i}^{[l]}\leftarrow\lVert
w_{i}^{[l]}\odot\nabla_{s}R_{SF,i}^{[l]}\rVert_{2}$

12 $\tau\leftarrow p_{r}$ percentile score in $S_{SF}$

13 $m_{i}^{[l]}\leftarrow\mathds{1}(S_{SF,i}^{[l]}>\tau)$

14 $w_{i}^{[l]}\leftarrow w_{i}^{[l]}\odot m_{i}^{[l]}$

15 return $w$

16Function  _ClientUpdate( $C_{k},s^{t-1}_{k}$)_:

// ( performs 3 in Figure 1)

17 $\hat{s}^{t}_{k}\leftarrow$ initialize real-valued sign mask from
$s^{t-1}_{k}$

18 $\mathcal{B}\leftarrow$ split local data into batches

19 for  _batch $(x_{b},y_{b})\in\mathcal{B}$_ do

$\hat{s}^{t}_{k}\leftarrow\hat{s}^{t}_{k}-\eta\nabla_{\hat{s}^{t}_{k}}\mathcal{L}[f(x_{b};w^{0}\odot\operatorname{sign}(\hat{s}^{t}_{k})),y_{b}]$

// $\eta$ is the learning rate

20

$s^{t}_{k}\leftarrow\operatorname{sign}(\hat{s}^{t}_{k})$

// binarize the real-valued sign mask

21 return $s^{t}_{k}$

Algorithm 1 HideNseek

##  Appendix B Simulating Non-IID Data

Figure 5 depicts the effect of the parameter $\alpha$ on the label
distribution among clients when employing Dirichlet sampling to partition
MNIST dataset in Non-IID manner.

(a) $\alpha=0.1$

(b) $\alpha=1$

(c) $\alpha=10$

Figure 5: Label distribution among 20 clients for MNIST dataset with dirichlet
sampling at different $\alpha$.

##  Appendix C Model Configurations

The model configurations employed in this work are depicted in Table 5. For
VGG9, each ConvBlock(N) is composed a convolutional layer with N channels with
size 3, a BatchNorm layer followed by ReLU activation. Each MaxPool2d layer
has a kernel size and stride length of 2. The number of nodes in the final
fully connected layer are 62 or 10 depending on EMNIST or MNIST dataset.

VGG9 | MLP
---|---
ConvBlock(32) | Linear(300)
MaxPool2d | ReLU
ConvBlock(64) | Liner(100)
MaxPool2d | ReLU
ConvBlock(128) | Linear(6)
ConvBlock(128) |
MaxPool2d |
ConvBlock(256) |
ConvBlock(256) |
MaxPool2d |
Flatten |
Linear(62 or 10) |
Table 5: Model configurations.