# Communication-Efficient Federated Learning through Adaptive Weight
Clustering and Server-Side Distillation

Vasileios Tsouvalas1 Aaqib Saeed1 Tanir Ozcelebi1 Nirvana Meratnia1
1Eindhoven University of Technology, The Netherlands

###### Abstract

Federated Learning (FL) is a promising technique for the collaborative
training of deep neural networks across multiple devices while preserving data
privacy. Despite its potential benefits, FL is hindered by excessive
communication costs due to repeated server-client communication during
training. To address this challenge, model compression techniques, such as
sparsification and weight clustering are applied, which often require
modifying the underlying model aggregation schemes or involve cumbersome
hyperparameter tuning, with the latter not only adjusts the model’s
compression rate but also limits model’s potential for continuous improvement
over growing data. In this paper, we propose
FedCompress111https://github.com/FederatedML/FedCompress, a novel approach
that combines dynamic weight clustering and server-side knowledge distillation
to reduce communication costs while learning highly generalizable models.
Through a comprehensive evaluation on diverse public datasets, we demonstrate
the efficacy of our approach compared to baselines in terms of communication
costs and inference speed.

Federated learning (FL) enables collaborative training of neural network
models directly on edge devices (referred to as clients), preserving on-device
data locally Konečný et al. (2016). FL is composed of multiple federated
rounds, which involve server-to-client model updates dispatch, local training
by clients, and server-side aggregation (e.g., FedAvg McMahan et al. (2017))
of clients’ model updates, iteratively performed until model convergence.
Despite its appealing properties for users’ privacy, FL requires constant
model transportation between server and clients, which poses a challenge in
terms of communication efficiency. This becomes even more critical when the
clients are resource-constrained edge devices with limited computational
capabilities and strict energy constraints.

To address the communication overhead in FL, recent studies have explored
model compression schemes on the exchanged model updates to minimize the
communication overhead. Sparsification Stich et al. (2018) involves discarding
network segments to reduce the overall model’s complexity based on a threshold
value. FedSparsify Stripelis et al. (2022) utilizes magnitude pruning with a
gradually increasing threshold during training to learn a highly-sparse model
in a communication-efficient FL scheme. Alternatively, weight clustering Han
et al. (2015) converts the weight matrices elements into a discrete set of
values (clusters) to achieve high model compression ratio. MUCSC Cui et al.
(2021) utilizes layer-wise weight clustering using a fixed number of clusters
to communicate compressed model updates from clients to server. Likewise,
FedZip Malekijoo et al. (2021) employs a sequence of pruning and weight
clustering to further improve the compression ratio. Apart from these model
compression schemes, knowledge distillation Wu et al. (2022) and sub-model
training Rabbani et al. (2023); Niu et al. (2023) have being explored to
reduce communication costs. However, the aforementioned techniques require
modifications to the underlying model aggregation algorithm and solely focus
in optimizing the client-to-server (upstream) communication route.
Furthermore, existing weight clustering schemes in FL rely on a fixed set of
clusters, limiting model’s potential for continuous improvement over growing
data.

Figure 1: Illustration of FedCompress for communication-efficient FL. A dual-
stage compression scheme is proposed: (i) weight clustering across clients
during on-device training, and (ii) self-compression on server-side combining
weight clustering with knowledge distillation on out-of-distribution data.

We propose FedCompress (Federated Learning with Dynamic Weight Clustering for
Model Compression) to achieve significant communication reductions in the
bidirectional communication route during FL training, while maintaining the
representational power of models and achieving highly compressed models.
Naively applying weight clustering during local updates in FL yields limited
compression benefits for the aggregated model, as clients’ models form diverse
clusters during compression due to the statistical heterogeneity among
clients. Consequently, the centroid-based structure of the aggregated model
weights is compromised, once the server-side aggregation is applied Briggs et
al. (2020). To overcome this issue with no modifications in the underlying
aggregation strategy, we apply the knowledge distillation Hinton et al. (2015)
scheme using out-of-distribution data after model aggregation at the server.
In this way, we perform self-compression on the aggregated model, enforcing
the centroid-like structure and reducing communication costs in the downstream
communication channel for the next federated round.

Aside from the server-side compression, we balance the trade-off between model
performance and communication efficiency by finding a suitable number of
clusters during the FL process. To this end, we start with a small number of
clusters for each layer and dynamically adjust them as federated rounds
progress by monitoring the representational power of clients’ models. In
particular, we propose a representation quality score, which is computed
locally at each client using a small unlabelled set of clients’ available
data. Concisely, the main contributions of our work are as follows:

  * •

We propose FedCompress, a communication efficient FL approach that combines
weight clustering and knowledge distillation on out-of-distribution data to
achieve highly compressed models, with no modifications to the underlying
weights’ aggregation algorithm.

  * •

We introduce a representation quality score, locally computed based on
clients’ unlabelled data, to dynamically adjust the number of clusters
utilized during weight clustering.

  * •

We demonstrate that proposed method is highly effective for learning
generalizable compressed federated models on diverse public datasets from both
vision and audio domains, namely CIFAR-10 Krizhevsky et al. (2009), CIFAR-100
Krizhevsky et al. (2009), PathMNIST Yang et al. (2021), SpeechCommands Warden
(2018) and VoxForge MacLean (2018).

  * •

Our evaluation of FedCompress shows on average a 4.5-fold reduction in
communication costs during training and a 1.13-fold speedup during inference
on edge accelerator devices when compared to FedAvg across considered
datasets.

##  1 Methodology

###  1.1 Problem Formulation

We focus on the problem of federated model compression to overcome the high
communication-burden in FL and offer notable inference speedup on edge devices
as a by-product. Formally, we assume that each of the $K$ clients has a
labeled and a small validation (unlabeled) dataset, denoted by
$\mathcal{D}_{l}^{k}$ = $\\{x{i},y_{i}\\}_{i=1}^{N_{l}^{k}}$, and
$\mathcal{D}_{u}^{k}=\\{x_{i}\\}_{i=1}^{N_{u}^{k}}$, respectively.
Furthermore, server possesses an OOD dataset,
$\mathcal{S}=\\{x_{i}\\}_{i=1}^{N_{s}}$, which can have no statistical
similarity with clients locally stored data. We aim to learn a compressed
global model, $p_{\tilde{\theta}}$ without clients sharing locally stored
data, $\mathcal{D}_{l}$ and $\mathcal{D}_{u}$, with the server and reduce the
communication burden during FL training phase. Here, we denote with
$p_{\theta}$ a neural network with weights $\theta$, while
$\tilde{p}_{\theta}^{k}$ and $\tilde{\theta}$ refer to the weight-clustered
(compressed) versions of $p_{\theta}$ and $\theta$, respectively.

###  1.2 Federated Model Compression

We propose FedCompress, a two-stage compression scheme for bi-directional
communication reduction during training in FL. During local model training, we
simultaneously train and compress clients’ models using weight-clustering to
reduce the upstream communication costs. To maintain a highly compressed model
once server-side model aggregation is complete, we employ a novel model
compression scheme that utilizes OOD data to minimize the downstream
communication burden, while maintaining high model performance. Furthermore,
To strike a balance between model performance and communication efficiency
trade-off, we propose a dynamically adaptive weight-clustering approach to
monitor and update the number of clusters based on the representational power
of clients’ models, allowing FedCompress to adapt to the underlying task’s
complexity.

Client-side Model Compression: During the local model update step, we
initially apply standard cross-entropy to each of the $k$ client’s labeled
datasets, $\mathcal{D}_{l}^{k}$, while simultaneously enforcing the weights
$\theta$ to cluster around a set of $C$ learnable centroids, $\mu$.
Specifically, each client’s minimization objective is defined as follows:

$\min_{\theta}\mathcal{L}_{k}(\theta_{k})=\mathcal{L}_{ce}(p_{\theta_{k}}(\mathcal{D}_{l}^{k}))+\beta\cdot\mathcal{L}_{wc}(\theta_{k},\mu,C)$

(1)

Here, $\mathcal{L}_{ce}$ is the cross-entropy loss function for the model
$p_{\theta}$ on the labeled dataset $\mathcal{D}_{l}^{k}$. We use $\beta$ to
control the relative impact of $\mathcal{L}_{ce}$ and $\mathcal{L}_{wc}$. As
the initial centroids are important to maintain model’s high representational
power, we allow for a few training rounds using $\mathcal{L}_{ce}$ before
introducing $\mathcal{L}_{wc}$. In essence, we start each local FL training
step with $\beta$=$0$ for a few epochs and afterwards setting $\beta$=$1$.

Self-Compression on Server: Once the server has constructed a new global model
from the received model updates, the centroid-shape structure of model weights
is compromised, making it challenging to maintain a compressed model for
downstream communication. To solve this problem, we propose a self-compression
mechanism that combines weight clustering and knowledge distillation on OOD
data, $\mathcal{S}$, at the server side. This mechanism involves training a
compressed version of the original global model (i.e., the teacher), which
acts as a student that aims to mimic the behavior of its teacher on the OOD
data.

In this way, we enforce the model weights to cluster around a set of $C$
learnable centroids, similar to the client-side compression, while recovering
any performance degradation due to weight-clustering. As a loss function to
this teacher-student architecture, we utilize the Kullback-Leibler divergence
(KLD) loss, which aims to match the output distributions of the models.
Specifically, the objective function of the proposed server-side self-
compression approach is as follows:

$\begin{aligned}
\min_{\theta}\mathcal{L}_{s}(\theta)=&~{}\mathcal{L}_{kl}\left(p_{\theta_{T}}~{}||~{}p_{\theta}\right)+\beta\cdot\mathcal{L}_{wc}(\theta,\mu,C)\\\
=&~{}\lambda^{2}\cdot\sum_{x\in\mathcal{S}}p_{\theta_{T}}^{\lambda}(x)\log\frac{p_{\theta_{T}}^{\lambda}(x)}{p_{\theta}^{\lambda}(x)}+\beta\cdot\sum_{j=1}^{C}\sum_{i=1}^{N_{s}}u_{ij}||\theta_{i}-\mu_{j}||^{2}~{}~{}\end{aligned}$

(2)

where $\lambda$ is a temperature scalar, $\mathcal{L}_{wc}$ is the cross-
entropy loss, $\mathcal{L}_{kl}$ is the KLD loss being computed using
$p_{\theta_{T}}^{\lambda}$ and $p_{\theta}^{\lambda}$ the $\lambda$-scaled
logits of teacher and student models, respectively.

One may note that no labels are required to enforce the alignment of
distributions, thus any unlabelled dataset available on the server can be
utilized to perform the self-compression. Furthermore, with no modifications
required to the underlying model aggregation mechanism (e.g., FedAvg), our
method provides a readily usable solution to any existing FL systems to reduce
the downstream communication costs.

Dynamic Weight-Clustering: While model compression via weight clustering can
result in highly accurate compressed models, its performance is directly
affected by selecting a proper number of clusters, $C$. Especially, in FL,
where clients have heterogeneous data distributions, a suitable number of
clusters can vary significantly based on the heterogeneity of clients and
their local data distributions. We propose dynamically adjusting the number of
clusters based on clients models’ representational power. In particular, we
assess model’s performance using embeddings from the penultimate layer of the
model, where we use the rank of embeddings as a proxy of their generalization
quality Roy and Vetterli (2007). This representation quality score is computed
locally on client’s unlabeled dataset $\mathcal{D}_{u}^{k}$.

Formally, with the completion of the local training step on $k$-th client, we
extract the embeddings $\mathcal{Z}^{k}$ from $\mathcal{D}_{u}^{k}$ using
client’s model $p_{\theta_{k}}$, and afterwards compute the score,
$\mathcal{E}_{k}$ using $\exp(-\sum_{j=1}^{m_{\mathcal{Z}^{k}}}r_{j}\log
r_{j})$, where $r_{j}$ denoting the ranking of $j$-th singular value of
$\mathcal{Z}^{k}$ ($\frac{\sigma_{j}}{|\sigma_{\mathcal{Z}^{k}}|_{1}}$) and
$m_{\mathcal{Z}^{k}}$ denotes the minimum dimension of embeddings. To ensure
numerical stability, we add a small constant equal to $1e^{-7}$ in the
computation of $r_{j}$. During the server-side model aggregation step in each
federated round, we compute the weighted-averaged representation quality score
$\mathcal{E}$ of participating clients models, similar to FedAvg.

To ensure that the model is compressed efficiently, we start with a small
value for $C$ (i.e., minimum number of clusters - $C_{min}$), incrementing it
when the moving average of $\mathcal{E}$ over a window $W$ shows no
improvement in the previous $P$ rounds. We fix $W$=$3$ and $P$=$3$, which we
determine to be working well during our initial exploration. Furthermore, our
approach allows for a maximum communication budget to be specified prior to FL
training (e.g. based on an energy consumption profile) to update $C$ between
two boundary values, $\left[C_{min},C_{max}\right]$. Further details and an
overview of our proposed FedCompress approach for communication-efficient FL
can be found in Algorithm 1.

##  2 Evaluation

Datasets: We use publicly available datasets from both the vision and audio
domains with their standard training/test splits. Specifically, we use the
CIFAR-10/100 Krizhevsky et al. (2009) and PathMNIST Yang et al. (2021)
datasets, where the tasks of interests are object detection and pathology
reporting, respectively. Likewise, from the audio domain, we use
SpeechCommands Warden (2018) for keyword spotting (12 classes in total), and
VoxForge MacLean (2018) for language identification. As OOD datasets for self-
compression on server, we use StyleGAN (Oriented) Baradad Jurjo et al. (2021)
and Librispeech Panayotov et al. (2015) for our vision and audio recognition
tasks, respectively. However, we note that augmented patches (or segments in
case of audio) from a single image can also be used as OOD data Asano and
Saeed (2023).

Experimental Setup: We utilize ResNet-20 He et al. (2016) for the vision
domain, while we choose MobileNet Howard et al. (2017) for the considered
audio recognition task. These models were chosen based on their performance,
suitability for on-device learning, where computational resources are limited
compared to centralized settings, and extensive validation in previous
research Tsouvalas et al. (2022). To simulate a federated environment, we use
Flower Beutel et al. (2020) with FedAvg McMahan et al. (2017) to construct the
global model from clients’ local updates. We control the federated setting in
our experiments with the following parameters:  1) number of clients -
$M$=$20$,  2) number of rounds - $R$=$20$,  3) local train epochs -
$E_{c}$=$10$, server self-compression training epochs - $E_{s}$=$10$,  4) data
distribution variance across clients - $\sigma$=$25\%$.  We randomly
partitioned the datasets across the available clients in a non-overlapping
fashion.

From the related approaches in the literature, we performed experiments using
FedZip Malekijoo et al. (2021) with number of clusters fixed to $15$ (which we
find to work well for the considered tasks after preliminary experimentation),
while compared both FedCompress and FedZip performances in terms of test set
accuracy, communication-cost reduction (CCR), and model compression ratio
(MCR) with respect to the standard FedAvg. For a rigorous review, we manage
any randomness during data partitioning and training procedures with a seed
value and performed two distinct trials, reporting the average accuracy on
test sets.

Table 1: Experimental results reporting Communication Compression Reduction
(CCR), Model Compression Ratio (MCR) and accuracy difference $\delta$-Acc
versus standard FedAvg for FedZip Malekijoo et al. (2021) and FedCompress
(with and without Self-Compression on Server - SCS). Results are reported
across five datasets, while CCR and MCR are indicating an $n$-fold reduction
from the standard FedAvg results. Federated parameters are set to $R$=20,
$M$=20, $E_{c}$=$10$, $E_{s}$=$10$, and $\sigma$=25%.

Dataset |  FedAvg Accuracy |  FedZip Malekijoo et al. (2021) |  FedCompress (w/o SCS) | FedCompress
---|---|---|---|---
$\delta$-Acc | CCR | MCR |  $\delta$-Acc | CCR | MCR |  $\delta$-Acc | CCR | MCR
CIFAR-10 | 86.26 | -1.89 | 1.91 | 2.08 | -1.47 | 1.02 | 1.77 | -1.83 | 4.53 | 5.18
CIFAR-100 | 60.68 | -2.57 | 1.94 | 2.11 | -2.67 | 1.02 | 1.62 | -1.88 | 3.80 | 3.93
PathMNIST | 88.22 | -3.04 | 1.92 | 2.10 | -3.57 | 1.06 | 1.82 | -1.72 | 4.79 | 5.27
SpeechCommands | 95.75 | -0.82 | 1.66 | 1.88 | -0.72 | 1.06 | 1.72 | -0.42 | 5.04 | 5.09
VoxForge | 81.05 | -1.04 | 1.69 | 1.91 | 0.75 | 1.11 | 1.81 | -0.31 | 5.41 | 5.64

Results: In Table 1, we report our findings across all datasets and compare
FedCompress performance with the considered baselines. As indicated from
$\delta$-Acc (accuracy versus standard FedAvg) columns in Table 1, FedCompress
outperforms FedZip across all considered datasets and yields compressed
federated models with comparable performance to FedAvg, while achieving
significant reductions in communication costs. On audio-based tasks, where the
MobileNet model was utilized, we observe over a $5$-fold reduction in
communication costs (CCR), while keeping models’ accuracy within $0.5$% of the
standard FL process. In the vision domain, our approach remains equally
effective, with a CCR of $4.28$, while suffering an accuracy drop of
approximately $2.14$% across all image dataset.

Figure 2: Relationship between mean representation quality score and mean
validation accuracy across clients during FL training for FedCompress on
CIFAR-10 and SpeechCommmands. Strong positive correlation is observed,
indicating that the representation quality score is a useful indicator of the
clients models’ representational power.

Overall, an average $4.5$-fold CCR is achieved throughout all five datasets,
suggesting thatFedCompress can effectively reduce the communication costs in
FL without sacrificing models’ accuracy. These results indicate the potential
for significant energy savings and reduced communication bandwidth
requirements in FL, both crucial for resource-constrained devices and Internet
of Things (IoT). Apart from the reduction in communication costs, FedCompress
demonstrates a significant reduction in resulting model size. We observe an
average MCR of $4.14$ across all datasets, indicating that our approach can
effectively compress models without sacrificing their accuracy. The highly
compressed models offer additional benefits to edge devices, such as lower
memory requirements and reduced energy consumption during training and
inference. This, in turn, allows for more complex models to be deployed on
edge devices with limited resources.

To validate the utilization of our representation quality score as an
indicator of models’ representation power, we compute the score and the
validation accuracy across clients in each federated round on CIFAR-10 and
SpeechCommands and compared their progression. Figure 2 shows a strong
correlation between the two metrics, indicating that the models’
representation quality metric is a valuable alternative to the validation
accuracy, while it can be efficiently computed from clients models’ embeddings
with no need for having labeled data. Since unlabeled data are often readily
available on edge devices, our score can effectively act as a proxy to
dynamically set the number of clusters during training, providing a
lightweight and fast alternative for measuring models’ representational power.

We also conducted experiments on various edge devices to evaluate the impact
of our compression approach on inference time. Table 2 shows that our approach
can accelerate the inference time on all these devices, while maintaining
comparable accuracy to FedAvg as shown in Table 1. Notably, FedCompress models
demonstrate an acceleration of up to 1.15$\times$ across the edge devices,
while quantizing the models to uint8 achieves an inference speedup up to
1.24$\times$. Consequently, FedCompress provides the ability to achieve faster
inference times with minimal effect on federated models’ accuracy, providing
significant benefits for resource-constrained edge devices, where low power
consumption and reduced inference time are crucial.

Table 2: Inference time acceleration of diverse edge devices for ResNet-20 and
MobileNet on CIFAR-10 and SpeechCommands datasets, respectively. The reported
inference time acceleration is achieved by comparing to FL models using
FedAvg.

Model | Device | float32 | uint8 (Quantized)
---|---|---|---
ResNet-20 | Pixel 6 |  $\times$1.103 |  $\times$1.165
Jetson Nano |  $\times$1.127 |  $\times$1.169
| Coral TPU |  $\times$1.113 |  $\times$1.191
MobileNet | Pixel 6 |  $\times$ 1.114 |  $\times$1.248
Jetson Nano |  $\times$1.137 |  $\times$1.161
| Coral TPU |  $\times$1.152 |  $\times$1.194

##  3 Conclusion

We presented FedCompress, a communication-efficient FL approach based on
model-compression via weight clustering and knowledge distillation. It can be
easily integrated with existing FL frameworks, requiring no modifications to
the FL aggregation strategy. Our experiments across multiple datasets showed
that our approach can achieve significant reductions in communication costs
and model sizes, while maintaining comparable accuracy to the standard FL
process. Moreover, we have shown that our proposed embeddings-based
representation quality score can effectively act as a proxy for models’
representational power, allowing for a dynamic adjustment of the number of
clusters during training based on the underlying task’s complexity.

## Acknowledgement

This research is partially funded by the DAIS project, which has received
funding from KDTJU under grant agreement No 101007273.

## References

  * Asano and Saeed (2023) Yuki M Asano and Aaqib Saeed.  The augmented image prior: Distilling 1000 classes by extrapolating from a single image.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Baradad Jurjo et al. (2021) Manel Baradad Jurjo, Jonas Wulff, Tongzhou Wang, Phillip Isola, and Antonio Torralba.  Learning to see by looking at noise.  _Advances in Neural Information Processing Systems_ , 34:2556–2569, 2021.
  * Beutel et al. (2020) Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D Lane.  Flower: A friendly federated learning research framework.  _arXiv preprint arXiv:2007.14390_ , 2020.
  * Briggs et al. (2020) Christopher Briggs, Zhong Fan, and Peter Andras.  Federated learning with hierarchical clustering of local updates to improve training on non-iid data.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–9. IEEE, 2020.
  * Cui et al. (2021) Laizhong Cui, Xiaoxin Su, Yipeng Zhou, and Yi Pan.  Slashing communication traffic in federated learning by transmitting clustered model updates.  _IEEE Journal on Selected Areas in Communications_ , 39(8):2572–2589, 2021.
  * Han et al. (2015) Song Han, Huizi Mao, and William J. Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  2015\.  doi: 10.48550/ARXIV.1510.00149.  URL https://arxiv.org/abs/1510.00149.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ , 2017.
  * Konečný et al. (2016) Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  In _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016.  URL https://arxiv.org/abs/1610.05492.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * MacLean (2018) Ken MacLean.  Voxforge.  _Ken MacLean.[Online]. Available: http://www.voxforge.org/home.[Acedido em 2012]_ , 2018.
  * Malekijoo et al. (2021) Amirhossein Malekijoo, Mohammad Javad Fadaeieslam, Hanieh Malekijou, Morteza Homayounfar, Farshid Alizadeh-Shabdiz, and Reza Rawassizadeh.  Fedzip: A compression framework for communication-efficient federated learning.  _arXiv preprint arXiv:2102.01593_ , 2021.
  * 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 Aarti Singh and Jerry Zhu, editors, _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 1273–1282. PMLR, 20–22 Apr 2017.  URL https://proceedings.mlr.press/v54/mcmahan17a.html.
  * Niu et al. (2023) Yue Niu, Saurav Prakash, Souvik Kundu, Sunwoo Lee, and Salman Avestimehr.  Federated learning of large models at the edge via principal sub-model training, 2023.
  * Panayotov et al. (2015) Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur.  Librispeech: An asr corpus based on public domain audio books.  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5206–5210, 2015.  doi: 10.1109/ICASSP.2015.7178964.
  * Rabbani et al. (2023) Tahseen Rabbani, Brandon Feng, Marco Bornstein, Kyle Rui Sang, Yifan Yang, Arjun Rajkumar, Amitabh Varshney, and Furong Huang.  Comfetch: Federated learning of large networks on constrained clients via sketching, 2023.
  * Roy and Vetterli (2007) Olivier Roy and Martin Vetterli.  The effective rank: A measure of effective dimensionality.  In _2007 15th European Signal Processing Conference_ , pages 606–610, 2007.
  * Stich et al. (2018) Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified sgd with memory.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 4452–4463, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Stripelis et al. (2022) Dimitris Stripelis, Umang Gupta, Greg Ver Steeg, and Jose Luis Ambite.  Federated progressive sparsification (purge, merge, tune)+.  _arXiv preprint arXiv:2204.12430_ , 2022.
  * Tsouvalas et al. (2022) Vasileios Tsouvalas, Aaqib Saeed, Tanir Ozcelebi, and Nirvana Meratnia.  Federated learning with noisy labels.  _arXiv preprint arXiv:2208.09378_ , 2022.  doi: 10.48550/ARXIV.2208.09378.
  * Warden (2018) P. Warden.  Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition.  _ArXiv e-prints_ , apr 2018.  URL https://arxiv.org/abs/1804.03209.
  * Wu et al. (2022) Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Yongfeng Huang, and Xing Xie.  Communication-efficient federated learning via knowledge distillation.  _Nature Communications_ , 13(1), April 2022.  ISSN 2041-1723.  doi: 10.1038/s41467-022-29763-x.  URL http://dx.doi.org/10.1038/s41467-022-29763-x.
  * Yang et al. (2021) Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni.  Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification.  _arXiv preprint arXiv:2110.14795_ , 2021.

##  Appendix A FedCompress Algorithm

We provide the pseudocode for FedCompress in Algorithm 1.

Algorithm 1 FedCompress: Federated Learning with Adaptive Weight Clustering
and Server-Side Distillation for Model Compression. We develop a two-stage
model compression approach to reduce the communication burden in FL and offer
inference speedups in edge devices. FedAvg McMahan et al. (2017) is the base
algorithm, whereas $\eta_{s}$ and $\eta_{c}$ refers to the learning rates of
server and clients, respectively.

1:Server initialization of model with model weights $\theta^{0}$,
$C$=$C_{min}$

2:for $i=1,\dots,R$ do

3: Randomly select $K$ clients to participate in round $i$

4: for each client $k\in K$ in parallel do

5: ($\theta_{k}^{i+1}$, $\mathcal{E}_{k}^{i+1}$) $\leftarrow$
ClientUpdate($\theta^{i}$,$C_{i}$)

6: end for

7:
$\theta^{i+1}\leftarrow\sum\nolimits_{k=1}^{K}\frac{N_{k}}{N}~{}~{}\theta_{k}^{i+1}$,
$\mathcal{E}^{i+1}\leftarrow\sum\nolimits_{k=1}^{K}\frac{N_{k}}{N}~{}~{}\mathcal{E}_{k}^{i+1}$

8: $\theta^{i+1}$ $\leftarrow$ SelfCompress($\theta^{i}$,$C_{i}$)

9: $C_{i+1}\leftarrow
C_{i}+\operatorname{sgn}\left|\operatorname{MA}(\mathcal{E}^{i+1})-\min\limits_{j=1}^{P}\operatorname{MA}(\mathcal{E}^{i-j+1})\right|$

10:end for

11:procedure ClientUpdate($\theta$,$C$)

12: for epoch $e=1,2,\dots,E_{c}$ do

13: for batch $b\in\mathcal{D}_{l}$ do

14:
$\theta\leftarrow\theta-\eta_{c}\cdot\nabla_{\theta}\left(\mathcal{L}_{ce}\left(p_{\theta}\left(b\right)\right)+\beta\cdot\mathcal{L}_{wc}\left(\theta,\mu,C\right)\right)$

15: end for

16: end for

17: $\mathcal{E}\leftarrow\mathcal{E}(p_{\theta}(\mathcal{D}_{u}))$

18: return ($\theta$, $\mathcal{E}$)

19:end procedure

20:procedure SelfCompress($\theta$,$C$)

21: for epoch $e=1,2,\dots,E_{s}$ do

22: $\theta^{\star}\leftarrow\theta$

23: for batch $b\in\mathcal{S}$ do

24:
$\theta\leftarrow\theta-\eta_{s}\cdot\nabla_{\theta}\left(\mathcal{L}_{kl}\left(p_{\theta^{\star}}(b)~{}||~{}p_{\theta}(b)\right)+\beta_{s}\cdot\mathcal{L}_{wc}(\theta,\mu,C)\right)$

25: end for

26: end for

27: return $\theta$

28:end procedure


# Greedy Gray Codes for some Restricted
Classes of Binary Words

Nathanaël Hassler Vincent Vajnovszki Laboratoire d’Informatique de Bourgogne
Dijon, France<EMAIL_ADDRESS><EMAIL_ADDRESS>Macao Polytechnic University
Macao, China Dennis Wong Macao Polytechnic University
Macao, China<EMAIL_ADDRESS>
###### Abstract

We investigate the existence of greedy Gray codes, based on the choice of the
first element in the code, for two classes of binary words: generalized
Fibonacci words and generalized Dyck words.

##  1 Introduction

###  1.1 Constrained binary words

#### 1’s run constrained binary words

Let $n,p\in\mathbb{N}$, $p\geq 2$, and $F_{n}(p)$ be the set of length $n$
binary words with no $p$ consecutive 1’s. $F_{n}(2)$ is counted by the
Fibonacci numbers $f_{n}$, and in general, $F_{n}(p)$ is counted by the
$p$-order Fibonacci numbers $f_{n}^{(p)}$. Now let $k\in\mathbb{N}$, and
$F_{n}(p,k)$ be the subset of words in $F_{n}(p)$ of weight $k$ (i.e., with
exactly $k$ 1’s). $F_{n}(p,k)$ is counted by the univariate $p$-nomial
coefficient.

#### Prefix constrained binary words

Let $k,n,p\in\mathbb{N}$ with $(p+1)k\leq n$, and $C_{n}(p,k)$ be the set of
length $n$ binary words of weight $k$ with the property that any prefix
contains at least $p$ times as many $0$’s as 1’s. In particular:

  * •

$C_{n}(0,k)$ is the set of length $n$ binary words of weight $k$ (combinations
in binary word representation),

  * •

$C_{2n}(1,n)$ is the set of length $2n$ Dyck words, and it is counted by the
Catalan numbers $\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}$,

  * •

$C_{3n}(2,n)$ is in bijection with size $3n$ ternary trees (see A001764 in
[5]).

More generally, $C_{(p+1)n}(p,n)$ is counted by
$\frac{1}{pn+1}\binom{(p+1)n}{n}$, known as the Pfaff–Fuss–Catalan numbers,
and the cardinality of $C_{n}(p,k)$ is established for instance in [6,
Equation (2)], using generating functions:

$|C_{n}(p,k)|=\binom{n}{k}-p\binom{n}{k-1}.$ (1)

###  1.2 Gray codes and greedy algorithms

A Gray code for a class of combinatorial objects is a list that contains each
object from the class exactly once such that any two consecutive objects in
the list differ only by a ‘small change’ [4]. In this paper we restrict
ourselves to Gray codes for restricted classes of same length and same weight
binary words (the weight of a binary word being its number of $1$’s). The
‘small changes’ we consider here are homogeneous transpositions: two binary
words differ by a homogeneous transposition if one can be obtained from the
other by transposing a $1$ with a $0$, and there are no $1$’s between the
transposed bits. A Gray code is called homogeneous if consecutive words differ
in a such a way. A list of words is suffix partitioned if words with the same
suffix are consecutive in the list.

The next definition of the greedy Gray code algorithm is a specialisation of
that introduced in [7] to particular cases of binary words, see also [8].

######  Definition 1.1.

For a set $S$ of same length and same weight binary words the greedy Gray code
algorithm to obtain a Gray code list $\mathcal{L}$ for the set $S$ is:

  1. 1.

Initialize $\mathcal{L}$ with a particular word in $S$.

  2. 2.

For the last word in $\mathcal{L}$, homogeneously transposes the leftmost
possible 1 with the leftmost possible $0$, such that the obtained word is in
$S$ but not in $\mathcal{L}$.

  3. 3.

If at point 2. a new word is obtained, then append it to the list
$\mathcal{L}$ and return to point 2.

In the following we will say that the list $\mathcal{L}$ is obtained by
applying the greedy algorithm for $S$ to $\alpha$, where $\alpha$ is the
initial word of $\mathcal{L}$. Depending on the choice of $\alpha$, it can
happen that the obtained list $\mathcal{L}$ is not an exhaustive one for $S$.

##  2 Tail partitioned lists

The tail of a binary word is its unique suffix of the form $011\cdots 1$, and
the only words with no tail have the form $11\cdots 1$. Note that $0$ is also
a tail, for the words ending by $0$.

A list of binary words is increasing (decreasing) tail partitioned if words
with tails of length $\ell$ appear before (after) words with tail of length
$\ell+1$, for any $\ell\geq 1$.

######  Definition 2.1.

A list $\mathcal{L}$ of same length binary words is recursive tail partitioned
if it is empty, or

  * •

it is increasing or decreasing tail partitioned, and

  * •

for any tail $t$, the list obtained by: (i) considering the sublist of
$\mathcal{L}$ of words with tail $t$, then (ii) erasing the tail $t$ in each
word of this sublist, is in turn recursive tail partitioned.

In the following $\cdot$ denotes the concatenation (of two words, or of each
word in a list with a word) and the comma appends lists. With this notation,
$\mathcal{L}$ is a recursive tail partitioned list if it is empty or has the
form

$\mathcal{L}=\mathcal{L}_{1}\cdot 01^{u},\mathcal{L}_{2}\cdot
01^{u+1},\mathcal{L}_{3}\cdot 01^{u+2},\cdots,\mathcal{L}_{\ell+1}\cdot
01^{u+\ell}$ (2)

or the form

$\mathcal{L}=\mathcal{L}_{1}\cdot 01^{u+\ell},\mathcal{L}_{2}\cdot
01^{u+\ell-1},\mathcal{L}_{3}\cdot
01^{u+\ell-2},\cdots,\mathcal{L}_{\ell+1}\cdot 01^{u}\\\ $ (3)

for some $u,\ell\geq 0$, and each list $\mathcal{L}_{i}$, is in turn recursive
tail partitioned.

We remark that the list in (2) is not necessarily the reverse of that in (3).
Clearly, a recursive tail partitioned list (r-t partitioned list for short) is
a suffix partitioned list.

######  Theorem 2.2.

If the list $\mathcal{L}$ is a homogeneous and suffix partitioned Gray code
for a set of (same length and same weight) binary words, then $\mathcal{L}$ is
an r-t partitioned list.

##  3 Main results

###  3.1 Fibonacci words $F_{n}(2,k)$

In this subsection we show that for any $\alpha\in F_{n}(2,k)$, by applying
the greedy algorithm for $F_{n}(2,k)$ to $\alpha$, a suffix partitioned list
is obtained, and we characterize the words $\alpha$ such that the greedy
algorithm yields an exhaustive list for $F_{n}(2,k)$. Moreover, for every
$\alpha\in F_{n}(2,k)$ we characterize the last word in the obtained list.

For $n<2k-1$, $F_{n}(2,k)$ is empty and in two particular cases $F_{n}(2,k)$
is a singleton set.

######  Fact 3.1.

If $k=0$, then $F_{n}(2,k)=\\{0^{n}\\}$, and if $n=2k-1$, then
$F_{n}(2,k)=\\{1(01)^{k-1}\\}$.

For $\alpha\in F_{n}(2,k)$ we denote by $\mathcal{F}(\alpha)$ the list
obtained by applying the greedy algorithm for $F_{n}(2,k)$ to $\alpha$.

For $n,k$ with $n\geq 2k$, let
$\alpha_{n,k}^{i}=0^{i}1(01)^{k-1}0^{n-2k+1-i}$, for $0\leq i\leq n-2k+1$.
Furthermore, let $\gamma_{n,k}:=\alpha_{n,k}^{n-2k+1}=0^{n-2k}(01)^{k}$. We
denote by $\textit{GenF}(n,k)$ the set of words $\alpha\in F_{n}(2,k)$ such
that $\mathcal{F}(\alpha)$ is a homogeneous Gray code for $F_{n}(2,k)$.
Equivalently, $\alpha\in\textit{GenF}(n,k)$ if and only if
$\mathcal{F}(\alpha)$ contains every word of $F_{n}(2,k)$.

######  Theorem 3.2.

Let $n\in\mathbb{N}^{\star}$. Then for all $k$ with $n\geq 2k$, we have

  1. 1.

$\alpha_{n,k}^{i}\in\textit{GenF}(n,k)$ for all $0\leq i\leq n-2k$, and
$\mathcal{F}(\alpha_{n,k}^{i})$ is a suffix partitioned list, with
$\gamma_{n,k}$ as last word.

  2. 2.

$\gamma_{n,k}\in\textit{GenF}(n,k)$, $\mathcal{F}(\gamma_{n,k})$ is a suffix
partitioned list and its last word is

    1. (i)

$\alpha_{n,k}^{0}$ if $k$ is even,

    2. (ii)

$\alpha_{n,k}^{n-2k}$ if $k$ is odd.

In the next lemma, we extend the result of 1. in Theorem 3.2 concerning the
last element of $\mathcal{F}(\alpha)$ to each $\alpha\in F_{n}(2,k)$.

######  Lemma 3.3.

Let $n\geq 2k$. For any $\alpha\in F_{n}(2,k)$ with $\alpha\neq\gamma_{n,k}$,
the last word of $\mathcal{F}(\alpha)$ is $\gamma_{n,k}$.

Now we generalise the property for $\mathcal{F}(\alpha)$ to be suffix
partitioned to each word of $F_{n}(2,n)$.

######  Lemma 3.4.

Let $n\geq 2k-1$. For any $\alpha\in F_{n}(2,k)$, $\mathcal{F}(\alpha)$ is a
suffix partitioned list.

Now we are able to completely describe the set $\textit{GenF}(n,k)$.

######  Proposition 3.5.

Let $n\geq 2k-1$. Then

$\textit{GenF}(n,k)=\\{0^{i}1(01)^{k-1}0^{n-2k+1-i}\ |\ 0\leq i\leq
n-2k+1\\}.$

In particular, $|\textit{GenF}(n,k)|=n-2k+2$.

###  3.2 $C_{n}(p,k)$

For $n,p,k$ such that $n\geq(p+1)k$ and $\alpha\in C_{n}(p,k)$, we denote by
$\mathcal{D}_{p}(\alpha)$ the list obtained by applying the greedy algorithm
for $C_{n}(p,k)$ to $\alpha$. Let also $\textit{Gen}_{p}(n,k)$ be the set of
words $\alpha\in C_{n}(p,k)$ such that $\mathcal{D}_{p}(\alpha)$ is a
homogeneous Gray code for $C_{n}(p,k)$. Equivalently,
$\alpha\in\textit{Gen}_{p}(n,k)$ if and only if $\mathcal{D}_{p}(\alpha)$
contains every word of $C_{n}(p,k)$. Since the situation is a bit more
complicated than the one for Fibonacci words, for clarity we first investigate
the case $p\in\mathbb{N}$, explaining every details of the proofs. Then we
explain how the results are generalised to any $p\in\mathbb{R}$, not
necessarily describing each proof.

####  3.2.1 $p\in\mathbb{N}$

We start by investigating the case $p\in\mathbb{N}$. We fix such a $p$
throughout this section. For $n\geq(p+1)k$, let
$\alpha_{n,k}^{i,j}:=0^{pj-i}1^{j-1}0^{i}1(0^{p}1)^{k-j}0^{n-(p+1)k}$ (resp.
$\alpha_{n,k}=1^{k}0^{n-k}$) for $i=0,\ldots,p-1$ and $j=1,\ldots,k$ if $p\geq
1$ (resp. if $p=0$), and $\beta_{n,k}^{i}:=0^{i}1^{k}0^{n-i-k}$ for
$i=pk+1,\ldots,n-k$. Because it plays a special role, we will use different
notation for $\beta_{n,k}^{n-k}$, so we set
$\gamma_{n,k}:=\beta_{n,k}^{n-k}=0^{n-k}1^{k}$.

######  Theorem 3.6.

Let $n\geq(p+1)k$, with $k\geq 1$.

  1. 1.

For all $0\leq i\leq p-1$ and $1\leq j\leq k$, we have
$\alpha_{n,k}^{i,j}\in\textit{Gen}_{p}(n,k)$ (resp.
$\alpha_{n,k}\in\textit{Gen}_{0}(n,k)$), and
$\mathcal{D}_{p}(\alpha_{n,k}^{i,j})$ (resp. $\mathcal{D}_{0}(\alpha_{n,k})$)
is a suffix partitioned list with $\gamma_{n,k}$ as last word.

  2. 2.

For all $j$, $pk+1\leq j\leq n-k-1$, we have
$\beta_{n,k}^{j}\in\textit{Gen}_{p}(n,k)$, and
$\mathcal{D}_{p}(\beta_{n,k}^{j})$ is a suffix partitioned list with
$\gamma_{n,k}$ as last word.

  3. 3.

$\gamma_{n,k}\in\textit{Gen}_{p}(n,k)$, $\mathcal{D}_{p}(\gamma_{n,k})$ is a
suffix partitioned list and its last word is

    1. (i)

$0^{p}1$ if $(n,k)=(p+1,1)$,

    2. (ii)

$\beta_{n,k}^{n-k-1}=0^{n-k-1}1^{k}0$ if $k$ is odd and $n\neq(p+1)k$,

    3. (iii)

$\alpha_{n,k}^{1,k-1}=0^{(k-1)p-1}1^{k-2}010^{p}1$ if $k\geq 3$ is odd and
$n=(p+1)k$ (resp. $\alpha_{n,k}=1^{k}$ if $p=0$),

    4. (iv)

$\alpha_{n,k}^{1,k}=0^{kp-1}1^{k-1}010^{n-(p+1)k}$ if $k$ is even (resp.
$\alpha_{n,k}=1^{k}0^{n-k}$ if $p=0$).

######  Lemma 3.7.

Let $n\geq(p+1)k$. For all $\alpha\in C_{n}(p,k)$, with
$\alpha\neq\gamma_{n,k}$, $\mathcal{D}_{p}(\alpha)$ ends with $\gamma_{n,k}$.

######  Lemma 3.8.

Let $n\geq 1$. Then for all $k$ with $n\geq(p+1)k$, and for each $\alpha\in
C_{n}(p,k)$, $\mathcal{D}_{p}(\alpha)$ is a suffix partitioned list.

######  Proposition 3.9.

Let $n\geq(p+1)k$. If $p\geq 1$ then

$\displaystyle\textit{Gen}_{p}(n,k)=\bigcup_{j=1}^{k}\\{0^{pj-i}$
$\displaystyle 1^{j-1}0^{i}1(0^{p}1)^{k-j}0^{n-(p+1)k}\ |\ 0\leq i\leq p-1\\}$
$\displaystyle\cup\\{0^{i}1^{k}0^{n-i-k}\ |\ pk+1\leq i\leq n-k\\}.$

If $p=0$ then $\textit{Gen}_{0}(n,k)=\\{0^{i}1^{k}0^{n-i-k}\ |\ 0\leq i\leq
n-k\\}$. In particular,

$|\textit{Gen}_{p}(n,k)|=n-k+1-p.$

######  Remark 3.10.

Propositions 3.5 and 3.9 highlight the fact that the choice of the first
element for the greedy algorithm is crucial. Indeed, only a few elements will
produce a Gray code for $F_{n}(2,k)$ or $C_{n}(p,k)$ with this algorithm.

####  3.2.2 $p\in\mathbb{R}_{+}$

The previous results can be generalized to $C_{n}(p,k)$ for any
$p\in\mathbb{R}_{+}$. In particular we have the following result:

######  Theorem 3.11.

Let $p\in\mathbb{R}_{+}$ and $n\geq(p+1)k$. Then

$|\textit{Gen}_{p}(n,k)|=n-k+1-\lceil p\rceil.$

###  3.3 Algorithmic considerations

Building on the previous results, the last part presents CAT algorithms that
greedily generate Gray code for $C_{n}(p,k)$ and $F_{n}(2,k)$, which we omit
in this abstract.

## References

  * [1]
  * [2] A. Bultena & F. Ruskey (1998): _An Eades-McKay algorithm for well-formed parentheses strings_.  Information Processing Letters 68, pp. 255–259, 10.1016/S0020-0190(98)00171-9.
  * [3] P. Eades & B. McKay (1984): _An algorithm for generating subsets of fixed size with a strong minimal change property_.  Information Processing Letters 19, pp. 131–133, 10.1016/0020-0190(84)90091-7.
  * [4] Torsten Mütze (2023): _Combinatorial Gray codes – an updated survey_.  Electronic Journal of Combinatorics 30(3):DS26, 10.37236/11023.
  * [5] N.J.A. Sloane: _The On-Line Encyclopedia of Integer Sequences_.  Available at http://oeis.org/.
  * [6] V. Vajnovszki & T. Walsh (2006): _A loop-free two-close Gray code algorithm for listing $k$-ary Dyck words_.  Journal of Discrete Algorithms 4(4), pp. 633–648, 10.1016/j.jda.2005.07.003.
  * [7] A. Williams (2013): _The greedy Gray code algorithm_.  In: Proceedings of the 13th international conference on Algorithms and Data Structures, p. 525–536, 10.1007/978-3-642-40104-6_46.
  * [8] D. Wong & V. Vajnovszki (2023): _Greedy Gray codes for Dyck words and ballot sequences_.  In: Computing and Combinatorics. COCOON 2023, Lecture Notes in Computer Science 14423, Springer, pp. 29–40, 10.1007/978-3-031-49193-1_3.