# Fed-QSSL: A Framework for Personalized Federated Learning under Bitwidth and
Data Heterogeneity

Yiyue Chen1, Haris Vikalo1, Chianing Wang2 This work was supported by Toyota
Motor North America.

( 1The University of Texas at Austin
2Toyota InfoTech Lab USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>)

###### Abstract

Motivated by high resource costs of centralized machine learning schemes as
well as data privacy concerns, federated learning (FL) emerged as an efficient
alternative that relies on aggregating locally trained models rather than
collecting clients’ potentially private data. In practice, available resources
and data distributions vary from one client to another, creating an inherent
system heterogeneity that leads to deterioration of the performance of
conventional FL algorithms. In this work, we present a federated quantization-
based self-supervised learning scheme (Fed-QSSL) designed to address
heterogeneity in FL systems. At clients’ side, to tackle data heterogeneity we
leverage distributed self-supervised learning while utilizing low-bit
quantization to satisfy constraints imposed by local infrastructure and
limited communication resources. At server’s side, Fed-QSSL deploys de-
quantization, weighted aggregation and re-quantization, ultimately creating
models personalized to both data distribution as well as specific
infrastructure of each client’s device. We validated the proposed algorithm on
real world datasets, demonstrating its efficacy, and theoretically analyzed
impact of low-bit training on the convergence and robustness of the learned
models.

##  1 Introduction

Federated learning (FL) [27, 18] recently emerged in response to the
challenges in data privacy, storage cost and computation commonly faced by the
conventional (centralized) learning systems. In centralized learning, a server
collects and stores data to be used for model training, raising concerns
regarding potential leakage of sensitive information and inefficient
utilization of the storage and computation resources. Lately, advancements in
software and hardware technologies have equipped smart edge devices with
computational power that enables local data processing, allowing
implementation of distributed frameworks such as FL in a variety of real-world
applications [7]. In FL systems, participating devices collaboratively learn a
model while preserving privacy by training on local data that remains private.
A server aggregates local updates to obtain a global model which is then
distributed to the clients; in turn, the clients continue local training using
the latest global model as a starting point. In addition to the conventional
supervised learning, federated learning is suitable for meta-learning and
unsupervised learning problems [16, 31].

Heterogeneity in local data distribution, as well as imbalance in the
computation and memory capabilities of the participating devices, present
major challenges to federated learning [39, 36]. Practical scenarios where
both sources of heterogeneity occur include healthcare disorder prediction for
patients with different profiles and monitoring devices, transportation
systems over different vehicles and terrain, and indoor/outdoor air quality
detection, to name just a few. Several recent FL techniques aim to alleviate
the impact of data, model or device heterogeneity [15, 24, 9, 34]. However,
variations in bitwidth available to the clients that participate in training
have been much less studied [36]. To our knowledge, there exists no prior work
in literature investigating FL in setting where both the local data and device
bitwidth are heterogeneous – the focus of our work.

On one hand, clients’ devices collect and/or generate data at different times
and locations, leading to discrepancy in data amounts and distribution. When
distributed devices train locally, each learned model optimizes an objective
specified in regard to a local dataset. If the data across participating
devices is non-IID, the devices end up optimizing distinct objectives which
generally adversely affects training convergence and, ultimately, negatively
impacts performance of the resulting global model trained by classical FL
algorithms such as FedAvg [27, 23]. This is exacerbated when a client’s
dataset contains only a small subset of classes or few data points, leading to
an insufficiently expressive local model. In turn, using such models in the
aggregation step at the server leads to a global model that lacks robustness
and in general may significantly underperform its centrally trained
counterparts [39].

On the other hand, to satisfy the constraints on local compute and memory
footprint as well as on the communication bandwidth between clients and the
central server, each client needs to train a local model in low bitwidth
operations and store the updated model in low bitwidth [36]. When the clients’
devices have different bitwidth capabilities, a number of novel challenges
arise including: (1) Quantized training conducted at lower precision levels
does not necessarily lead to expressive local model; (2) the server needs to
aggregate local models that are represented by different number of bits; and
(3) following the aggregation of local updates, the server should communicate
to clients the new global model re-quantized at levels matching the
capabilities of different devices. Prior works that deploy model compression
in distributed settings focus on reducing the communication cost [30, 5, 6];
those methods utilize full precision weights in the training process rather
than trying to train under weight precision constraint. To address the problem
of aggregating models trained at different precision, [36] proposed a
progressive weight de-quantizer that transforms low precision models to their
full precision versions before aggregating them. The de-quantizer there
requires the server to train DenseNet for de-quantizing low precision models;
the method assumes the local data distribution is the same across different
clients and thus does not apply to the heterogeneous data settings studied in
this paper. Note that all of these methods are restricted to supervised
learning.

The contributions of this paper are summarized as follows:

  1. 1.

For the first time, a novel FL problem characterized by heterogeneous local
data distributions and varied capabilities of clients’ devices is studied.
This is the first work to consider the non-trivial task of aggregating models
which due to varied bitwidth and heterogeneous data have incompatible
parameters and different expressiveness. While prior work addresses either
source of heterogeneity in isolation of the other, to our knowledge the
combination of the two has not been investigated previously. Indeed, new
challenges set forth by the combination of the heterogeneity sources render
the prior techniques ineffective.

  2. 2.

We present a new FL framework, Fed-QSSL, that enables learning personalized
and robust low-bitwidth models in settings characterized by diverse
infrastructure and data distributions. Fed-QSSL combines low-bitwidth
quantization training with self-supervised learning at the client side, and
deploys de-quantization, weighted aggregation and re-quantization at the
server side.

  3. 3.

We theoretically analyze the impact of low-bit training on the convergence and
robustness of learned models. In particular, we present a bound on the
variance of the quantization errors in local and global training and
investigate the associated convergence speed. The analysis demonstrates that
low-bit training with Fed-QSSL on heterogeneous data allows learning
meaningful representations.

  4. 4.

Finally, the efficacy of the proposed algorithm is tested in a variety of
experiments.

###  1.1 Related work

Bitwidth heterogeneity in FL. To address local infrastructure constraints, [9]
rely on models with simple architectures and low-bit parameter representation.
However, existing prior work typically assumes that clients train models of
same precision, e.g., the same bitwidth, which may often be violated in
practice since the participating devices generally have different
computational power and/or memory footprint. The varying infrastructure
capabilities of the clients’ devices imply that the models they are able to
deploy differ in size, i.e., devices with more computational power and memory
allow models of higher precision (e.g., 16-bit and 32-bit) while less capable
devices may only handle low-precision models (e.g., those storing parameters
in 2-bit or 4-bit precision). To satisfy local infrastructure constraints, not
only should a model be represented and stored at reduced precision levels but
the training process should also rely on operations at such levels (i.e.,
perform quantized training in low-bitwidth). Recently, [36] studied the
bitwidth heterogeneity problem in FL and proposed a progressive de-
quantization of the received local models prior to their aggregation into a
global model.

Quantized neural network training. When the compute/storage resources are
limited, on-device training of deep neural networks at full precision is
rendered infeasible. To this end, recent works have explored model size
reduction and the training that leads to low bitwidth weights/activations.
These include binarized neural networks (BNN) and XNOR-Net which binarize the
weights and activations of convolutional layers to reduce the computation
complexity in the forward pass [13, 29]. Specifically, in the forward pass the
computationally expensive convolutional operations are implemented via bitwise
operation kernels that evaluate the dot product of binary vectors x and
$\mathbf{y}$

$\displaystyle{\textbf{x}}\cdot\mathbf{y}=\mathrm{bitcount}(\mathrm{and}({\textbf{x}},\mathbf{y})),x_{i},y_{i}\in\\{0,1\\}\
\forall i,$

where $\mathrm{bitcount}(\cdot)$ counts the number of bits in its argument.
Such a kernel can be generalized to accommodate operations on $M$-bit fixed-
point integer sequence $x$ and $K$-bit fixed-point integer sequence $y$,
incurring computation complexity of ${\mathcal{O}}(MK)$ (i.e., the complexity
is proportional to the vector bitwidths). Related work [40] presents DoReFa-
Net which reduces the backpropagation computation cost by quantizing gradients
in the backward pass, and studies the effect of the weight, activation and
gradient bitwidth choice on the model performance. Subsequent works include
techniques that deploy training without floating-point operations, gradient
clipping, and training under mixed precision [35, 37, 41, 38]. While all of
the aforementioned methods investigate quantization in supervised learning
settings, recently there has been interest in quantizing models for self-
supervised learning. In [2], the authors propose self-supervised and
quantization learning (SSQL), which contrasts features learned from the
quantized and full precision models in order to provide reasonable accuracy of
quantized models and boost the accuracy of the full precision model. While
this work can balance the accuracy and bitwidth in resource constrained
settings, it still requires full precision operations and gradient storage
during training.

Non-IID data and distributed self-supervised learning. There have been
multiple efforts to ameliorate the impact of data heterogeneity on the
performance of distributed learning systems [19, 10, 21]. Recently, self-
supervised learning (SSL) has been shown effective in distributed settings
where the data is large-scale and imbalanced [34]. In contrast to supervised
learning, which requires large amount of labeled data for model training,
self-supervised learning defines a pre-train task that enables extracting
expressive representations; those representations can then be utilized in
various downstream tasks in computer vision and natural language processing
[3, 4]. While the majority of self-supervised learning methods focus on the
centralized setting where the data is collected for central training, recent
works have attempted to bridge the self-supervised and federated learning [11,
42, 26].

##  2 Preliminaries

Let us consider a federated learning system with $n$ clients, where the
clients rely on privately owned data to collaboratively learn a global model.
Rather than communicating the data, the clients send to a coordinating central
server the models trained locally. In turn, the server forms a global model by
aggregating the received local models, and re-distributes the global model
back to the clients for further local training. Let
$D_{k}=\\{x_{k,i}\\}_{i=1}^{|D_{k}|}$ denote the data owned by client $k$,
where $x_{k,i}\sim\mathcal{D}_{k}$ is a $d$-dimensional data point in $D_{k}$
and $|D_{k}|$ denotes the number of local data points. The distribution
$\mathcal{D}_{k}$ of data varies from one client to another, leading to
system-wide data heterogeneity. The union $D=\bigcup_{k=1}^{n}D_{k}$ is
assumed to be a dataset of uniform distribution, i.e., the data classes in $D$
are balanced.

In self-supervised learning problems, an embedding function
$f_{{\textbf{w}}}(\cdot)$, parameterized by w, is learned as a feature
extractor for extracting expressive representations from data. In particular,
we will denote the representation vector for point $x$ by
$f_{{\textbf{w}}}(x)$; such a representation vector is then used for
downstream tasks such as image classification or object detection. Contrastive
learning is a popular methodology for identifying the embedding function
$f_{{\textbf{w}}}(\cdot)$ [3]. The aim of contrastive learning is to find an
embedding function such that the distance between the learned representations
of data point $x$ and its positive signal $x^{+}$ (generated from $x$) is
small, while the distance between the representations of $x$ and negative
samples $x^{-}$ (extracted from the training batch) is large.111Given a data
sample $x$, its positive signal may be a variant obtained by adding noise,
changing color, or clipping; negative signals include data samples from
different classes, or simply other data samples in the same training batch. A
commonly used objective in contrastive learning is the InfoNCE loss;
specifically, the local objective for client $k$ is

$\mathcal{L}_{CL,k}({\textbf{w}})=\frac{1}{|D_{k}|}\sum_{i=1}^{|D_{k}|}-\log(\frac{\mathbb{D}_{k,i}^{+}}{\mathbb{D}_{k,i}^{+}+\sum_{j}\mathbb{D}_{k,i,j}^{-}}),$

where
$\mathbb{D}_{k,i}^{+}=\exp(-\mathbb{D}(f_{{\textbf{w}}}(x_{k,i}),f_{{\textbf{w}}}(x_{k,i}^{+}))/\tau$,
$\mathbb{D}_{k,i,j}^{-}=\exp(-\mathbb{D}(f_{{\textbf{w}}}(x_{k,i}),f_{{\textbf{w}}}(x_{k,j}^{-}))/\tau$,
and $\tau>0$ is a temperature parameter controlling the sharpness of the
exponential term. The function $\mathbb{D}(\cdot)$ is typically defined as the
cosine distance, i.e., $\mathbb{D}(z_{1},z_{2})=-\frac{z_{1}\cdot
z_{2}}{\|z_{1}\|\|z_{2}\|}$. Note that instead of the negative sample term, an
alternative SSL strategy adds to the objective a feature prediction function
$g(\cdot)$ that helps avoid potential collapse i.e. low accuracy of the
trained classifier layer [4]; in that case, the objective becomes

$\mathcal{L}_{siam,k}({\textbf{w}})=\frac{1}{|D_{k}|}\sum_{i=1}^{|D_{k}|}\mathbb{D}(g(f_{{\textbf{w}}}(x_{k,i})),f_{{\textbf{w}}}(x_{k,i}^{+})).$

In federated learning, each client has a local data source $D_{k}$. The
clients collaboratively search for w that minimizes the global objective
function

$\displaystyle\mathcal{L}({\textbf{w}})=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}\mathcal{L}_{k}({\textbf{w}}).$
(1)

To solve this distributed optimization without data sharing, numerous
federated learning schemes have been proposed including the FedAvg algorithm
[27]. At each iteration of FedAvg, central server samples a subset of clients
which then run $E$ local update epochs. The server collects updated models
from the selected clients and aggregates them to form a global model, which is
distributed to all clients for further local training/inference. The number of
local training epochs, $E$, controls the computation-communication tradeoff,
i.e., larger $E$ leads to less frequent communication.

We further assume that participating clients have devices with varied compute,
memory and communication capabilities, and therefore train and deploy models
at different bitwidth precision. Let $s_{k}$ denote the number of bits used to
represent parameters ${\textbf{w}}_{k}$ of the model deployed by client $k$.
When training, client $k$ utilizes bit convolutional kernels and conducts
operations on $s_{k}$-bit objects rather than performing full precision (i.e.,
$32$-bit floating-point) operations. When aggregating the collected local
models into global model ${\textbf{w}}_{G}$, the server takes into
consideration that the models are trained at different precision levels. The
server itself is assumed to be capable of performing operations at full
precision. Finally, the global model is compressed to various low bitwidth
representations and sent to the corresponding clients, i.e., client $k$
receives updated model in $s_{k}$ bit representation.

In our proposed framework, client $k$ performs low-bit training to learn
parameters ${\textbf{w}}_{k}$ of its local model; note that the low-bit
training and quantization are deployed in all steps, including the forward
pass, backpropagation and model update. In each round of training, model
parameters in $s_{k}$-bit representation are fed into the forward pass via bit
convolution kernels, and the gradient computed from the backward propagation
is quantized and stored. After updating the model by using gradient descent,
the model parameters are quantized to $s_{k}$ bits and stored.

##  3 Algorithm

The proposed federated quantized self-supervised learning scheme consists of
training procedures deployed at clients’ devices and the server, as detailed
next.

At each client’s side, a feature extraction model is trained in low bitwidth
with layer-wise quantization in both forward and backward propagation pass. We
denote the model parameters of client $k$ in training epoch $t$ by
${\textbf{w}}^{(Q)}_{k,t}$; each parameter is represented using $s_{k}$ bits.
The codebook used for quantizing parameters of each layer of the model,
${\textbf{w}}^{(Q)}_{k,t}$, has cardinality $2^{s_{k}}$. The quantization
centers (i.e., codebook entries) are typically determined via uniform
quantization [40],

$\displaystyle
r_{o}=\mathrm{quantize}_{s}(r_{i})=\frac{1}{2^{s}-1}\mathrm{round}((2^{s}-1)r_{i}),$

which uses a uniform quantizer $\mathrm{quantize}_{s}$ to map a real-valued
input $r_{i}\in[0,1]$ to an $s$-bit output $r_{o}\in[0,1]$. In general,
parameters of deep neural networks do not follow uniform distribution and may
vary in range. Therefore, the parameters may first need to be non-linearly
transformed, e.g., by applying $\tanh$ function to limit their range to
$[-1,1]$. If $\tanh$ function is used, the quantized model weights are found
as

$\displaystyle
r_{o}=2\mathrm{quantize}_{s}(\frac{\tanh{r_{i}}}{2\max(\tanh{r_{i}})}+\frac{1}{2})-1,$

where the maximum is taken over all parameters in the same layer. In the
forward pass, we apply normalization to ensure that
$\frac{\tanh{r_{i}}}{2\max(\tanh{r_{i}})}+\frac{1}{2}\in[0,1]$, where
$\max(\tanh{r_{i}})$ represents the maximum taken over all parameters in this
layer. Following the quantization operation, output $r_{o}$ is in $[-1,1]$,
which improves the stability of training.

In addition to quantizing model parameters, the proposed scheme quantizes
activations as well. In particular, after the output of a layer passes through
an activation function that guarantees the output to be within $[0,1]$ range,
the activation is quantized using $\mathrm{quantize}_{s}$.

To quantize gradients in backward propagation, we use layer-wise quantile
quantization method. In particular, we rely on the inverse of the cumulative
distribution function $F_{{\textbf{g}}}$ of the gradients in a layer to define
the quantile function $Quantile_{{\textbf{g}}}=F^{-1}_{{\textbf{g}}}$. The
quantization centers are then specified by the end points of each histogram
bin, $Quantile_{{\textbf{g}}}(\frac{i}{2^{s}-1})$, for $i=0,\dots,2^{s}-1$. It
has been observed in prior work on low-bitwidth training [40] that to avoid
significant performance degradation, the number of bits for gradient
quantization should be no less than the number of bits for weight quantization
(and may in fact need to be greater). In our algorithm, local gradient
quantization uses $2$ bits more than local weight quantization, e.g., if
client $k$ uses $s_{k}$ bits for weight/activation quantization then it uses
$s_{k}+2$ bits for gradient quantization. Following the backward pass, the
computed estimate of stochastic gradient, ${\textbf{g}}_{k,t}$, is immediately
quantized to ${\textbf{g}}^{(Q)}_{k,t}$. Finally, updated weights are
quantized according to
${\textbf{w}}^{(Q)}_{k,t+1}=Q({\textbf{w}}^{(Q)}_{k,t}-\alpha_{t}{\textbf{g}}^{(Q)}_{k,t})$.

Algorithm 1 Fed-QSSL: Federated quantized self-supervised learning under
bitwidth and data heterogeneity

Initialization: Clients bitwidth configuration $\\{s_{k}\\}_{k=1}^{n}$, local
dataset $\\{D_{k}\\}_{k=1}^{n}$, initial models
$\\{{\textbf{w}}^{(Q)}_{k,0}\\}_{k=1}^{n}$, global data buffer $D_{g}$, $t=0$
Parameter: number of local training epoch $E$, step size $\\{\alpha_{t}\\}$

1: for each round $r=1,2,$ do

2: $\\{$Local training at clients $\\}$

3: for each client $k$ in parallel do

4: for $t=0,1,\cdots,E-1$ do

5: Compute the compressed gradient ${\textbf{g}}^{(Q)}_{k,t+(r-1)E}$

6: Update the low-bit weights
${\textbf{w}}^{(Q)}_{k,t+1+(r-1)E}=Q({\textbf{w}}^{(Q)}_{k,t+(r-1)E}-\alpha_{t+(r-1)E}{\textbf{g}}^{(Q)}_{k,t+(r-1)E})$

7: $t=t+1$

8: end for

9: end for

10: $\\{$Global operations at the server $\\}$

11: The server collects local models
$\\{{\textbf{w}}^{(Q)}_{k,rE}\\}_{k=1}^{n}$

12: The server de-quantizes $\\{{\textbf{w}}^{(Q)}_{k,rE}\\}$ using $D_{g}$ to
obtain $\\{{\textbf{w}}^{\prime(Q)}_{k,rE}\\}$ and loss $\\{L_{DQ_{k}}\\}$ for
all $k\in[n]$

13: The server aggregates
${\textbf{w}}_{rE,G}=\sum_{k=1}^{n}p_{k}{\textbf{w}}^{\prime(Q)}_{k,rE}$ using
DQ-based losses

14: The server re-quantizes the aggregation using $D_{g}$ to $s_{k}$-bit model
and distributes to client $k$ for all $k\in[n]$

15: end for

16: Post-training Each client freezes the trained feature extractor and trains
local linear probe (i.e., classification layer) for downstream tasks

In each communication round the server collects and de-quantizes local models,
aggregates the de-quantized models, re-quantizes the resulting model to low
bitwidth and finally distributes the models to clients. To elaborate, after
the central server collects local low-bitwidth models, it uses a small buffer
of unlabeled data $D_{g}$ to de-quantize the collected local models to full
precision. The de-quantization process differs from one local model to another
and can be performed in parallel. In the scenario without bitwidth
constraints, de-quantization can be viewed as a fine-tuning step on uniform
unlabeled data; simulation results presented in the next sections demonstrate
that such fine-tuning improves robustness in the full-precision model
scenario.

After de-quantizing the collected models, the server forms their weighted
average,
${\textbf{w}}_{t,G}=\sum_{k=1}^{n}p_{k}{\textbf{w}}^{\prime(Q)}_{k,t}$. The
weights reflect performance discrepancy among local models caused by both
local bitwidth and data heterogeneity, and are computed as

$\displaystyle
p_{k}=\frac{e^{-\mathcal{L}_{DQ_{k}}}}{\sum_{j=1}^{n}e^{-\mathcal{L}_{DQ_{j}}}}$

where $\mathcal{L}_{DQ_{k}}$ represents the last epoch loss in the de-
quantization process of model $k$. The server re-quantizes global model
${\textbf{w}}_{t,G}$ to an $s_{k}$-bit version denoted by
${\textbf{w}}^{(Q)}_{k,t}$ while running fine-tuning epochs on a uniformly
distributed dataset stored in the global buffer $D_{g}$. The fine-tuning
epochs use low-bit operations in order to guarantee that the fine-tuned model
stays in $s_{k}$-bit representation. Note: both de-quantization and re-
quantization use $D_{g}$ for fine-tuning but de-quantization runs full
precision operations while re-quantization runs low-bit operations.

After completing pre-training and learning the feature extractor model, each
client freezes parameters of the feature extractor model and trains a low-
bitwidth classifier on its local (labeled) data.

The described procedure, including both the steps executed by clients as well
as those executed by the server, is formalized as Algorithm 1.

Remark. While Algorithm 1 assumes full client participation at each
communication round, it is straightforward to incorporate random client
sampling as used by the vanilla FedAvg algorithm in settings with a large
number of clients. Moreover, when the number of clients is exceedingly large,
it may be beneficial to cluster clients with similar data distributions and
learn a model for each such cluster, ultimately allowing better utilization of
the available resources.

##  4 Theoretical Analysis

In this section, we present analytical results that provide insights into Fed-
QSSL, with a focus on the impact of low-bitwidth training on the convergence
and robustness. For the sake of tractability, we consider the SSL formulation
utilizing local objective defined as
$\mathcal{L}_{SSL,k}({\textbf{w}})=-\mathbb{E}[({\textbf{w}}(x_{k,i})+\xi_{k,i})^{T}({\textbf{w}}(x_{k,i})+\xi^{\prime}_{k,i})]+\frac{1}{2}\|{\textbf{w}}^{T}{\textbf{w}}\|^{2}$,
where $\xi_{k,i}$ and $\xi^{\prime}_{k,i}$ denote random noise added to the
data sample, while the global objective is defined as
$\mathcal{L}_{SSL}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}\mathcal{L}_{SSL,k}({\textbf{w}})$.
This objective is obtained from the InfoNCE loss $\mathcal{L}_{CL,k}$ by
replacing normalization via negative signals by an alternative regularization
term [34]. Optimizing $\mathcal{L}_{SSL}$ is equivalent to minimizing
$\mathcal{L}({\textbf{w}})=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$ where
$\bar{X}=\sum_{k}\frac{|D_{k}|}{|D|}X_{k}$ and $X_{k}=\mathbb{E}_{x\sim
D_{k}}(xx^{T})=\frac{1}{|D_{k}|}\sum_{i=1}^{|D_{k}|}x_{k,i}x_{k,i}^{T}$, the
empirical covariance matrix of client $k$’s data. Since the aim of this
analysis is to assess the impact of low-bitwidth operations at client devices
on the convergence and robustness of federated learning, we simplify
operations at the server by replacing the sophisticated de-quantizer in
Algorithm 1 by a layer-wise codebook mapping low-bitwidth weights to floating-
point values according to
${\textbf{w}}^{\prime(Q)}_{k,t}={\textbf{w}}^{(Q)}_{k,t}$. The subsequent
aggregation follows FedAvg and computes
${\textbf{w}}_{t,G}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}^{\prime(Q)}_{k,t}$,
while re-quantization uses a $\tanh$ based quantizer.

For simplicity, we assume that clients quantize weights/activations using the
same bitwidth, i.e., $s_{1}=s_{2}=\cdots=s_{n}=R$; moreover, local gradient
quantization is performed using the same number of bits. When bitwidth varies
across client devices, the devices with higher bitwidth typically have smaller
quantization error. Our forthcoming analysis can be viewed as providing error
bounds for a system in which clients deploy bitwidth no less than $R$. Local
datasets are generated in a distributed and $2n$-way manner, i.e., local
dataset at client $k$ is generated such that the labels of data samples are
skewed to classes $2k-1$ and $2k$, with a few samples coming from other
classes. This distribution is close to the pathologically non-iid case with
two dominant classes. More details about heterogeneous data generation are
provided in Appendix.

We consider three types of quantization errors: $\epsilon_{{\textbf{w}}}$
denotes the model parameter quantization error, $\epsilon_{g}$ denotes the
gradient quantization error, and $\epsilon_{r}$ denotes the quantization error
induced by the server when re-quantizing the aggregated model. Below we use
subscripts $k$ and $t$ to indicate the client and the epoch, respectively.
Quantization can be viewed as adding noise to the full precision values, i.e.,
${\textbf{g}}^{(Q)}_{k,t}={\textbf{g}}_{k,t}+\epsilon_{g_{k},t}$. In quantized
training at client $k$, the update can be expressed as

$\displaystyle{\textbf{w}}_{k,t+1}^{(Q)}={\textbf{w}}_{k,t}^{(Q)}-\alpha_{t}({\textbf{g}}_{k,t}+\epsilon_{g_{k},t})+\epsilon_{{\textbf{w}}_{k},t}$

where ${\textbf{w}}_{k,t}^{(Q)}$ denotes the low-bitwidth model parameters at
time $t$, $\epsilon_{g_{k},t}$ is the noise added to the gradient in the
quantization step, and $\epsilon_{{\textbf{w}}_{k},t}$ denotes the noise added
to the model parameters after gradient update as the parameters retain low-
bitwidth representation. After $E$ local training epochs, the server collects
the models and aggregates them according to

$\displaystyle{\textbf{w}}_{t+E,G}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}_{t+E,k}^{(Q)}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}_{k,t}^{{Q}}$
$\displaystyle\quad-\sum_{s=0}^{E-1}[\alpha_{t+s}({\textbf{g}}_{k,t+s}+\epsilon_{g_{k},t+s})-\epsilon_{{\textbf{w}}_{k},t+s}].$

Since the aggregated model is not necessarily in low bitwidth, an additional
re-quantization step is required to form its quantized version
${\textbf{w}}_{t+E,G}^{(Q)}={\textbf{w}}_{t+E,G}+\epsilon_{r,t+E}$, which is
then sent to the clients.

Quantization centers used for layer-wise scalar quantization of the model
parameters and gradients are found via companding quantization. Specifically,
full-precision input x is transformed by a nonlinear function $c$, e.g.,
$\tanh$ function, and then uniformly quantized. The output $Q({\textbf{x}})$
is generated by taking the value of the inverse function, $c^{-1}$, of the
quantized value [32]. Uniform quantization is a special case of companding
quantization obtained by setting $c({\textbf{x}})={\textbf{x}}$. In Fed-QSSL,
local quantizers can also be viewed as special cases of the companding
quantizers.

To proceed with the analysis, we make the following assumption on the
quantizers.

######  Assumption 1.

All quantization operators in the low-bit training are unbiased.

This assumption is commonly encountered in prior work (see, e.g., [30]); an
example is the stochastic quantizer, i.e., given a sequence of quantization
centers $Q_{1}\leq\cdots\leq Q_{2^{R}}$, for $x\in[Q_{j},Q_{j+1}]$ we have
$Q(x)=Q_{j}$ with probability $\frac{Q_{j+1}-x}{Q_{j+1}-Q_{j}}$ and
$Q(j)=Q_{j+1}$ with probability $\frac{x-Q_{j}}{Q_{j+1}-Q_{j}}$. This
assumption implies that quantization errors $\epsilon_{{\textbf{w}}}$,
$\epsilon_{g}$, and $\epsilon_{r}$ are zero-mean.

We further make the following assumption on gradient estimates, frequently
encountered in literature.

######  Assumption 2.

Expected gradient estimate is unbiased and bounded,
$\mathbb{E}_{t}\|{\textbf{g}}_{k,t}\|^{2}\leq G^{2}$.

The following lemma provides a bound on the quantization errors (for proof
please see Appendix).

######  Lemma 1.

Suppose Assumptions 1-2 hold, and that client $k$ computes update of the
quantized model parameters ${\textbf{w}}_{k,t+1}^{(Q)}$ at bitwidth $s_{k}=R$.
Then the gradient quantization error $\epsilon_{g_{k},t}$ satisfies
$\mathbb{E}_{t}[\|\epsilon_{g_{k},t}\|^{2}]={\mathcal{O}}(G^{2}/2^{2R})$, and
the local re-quantization error $\epsilon_{{\textbf{w}}_{k},t}$ satisfies
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]={\mathcal{O}}(\alpha_{t}G^{2}/2^{2R})$.

This lemma indicates that by viewing the gradient update
$\alpha_{t}({\textbf{g}}_{k,t}+\epsilon_{g_{k},t})$ as a perturbation of
${\textbf{w}}^{(Q)}_{k,t}$, the variance of the weight quantization error
$\epsilon_{{\textbf{w}}_{k},t}$ in the local update is of the order
${\mathcal{O}}(\alpha_{t}G^{2})$. It further implies that the variance of the
re-quantization error $\epsilon_{r,t}$ in the global update is of the order
${\mathcal{O}}(\alpha_{t}G^{2}E)$ when $\alpha_{t-E+1}=\cdots=\alpha_{t}$.

The next corollary readily follows from Lemma 1.

######  Corollary 1.

Instate the assumptions of Lemma 1, and let all clients use the same learning
rate $\alpha_{t-E+1}=\cdots=\alpha_{t}$. Then there exists
$G_{q}={\mathcal{O}}(G^{2}/2^{2R})$ such that
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$
and $\mathbb{E}_{t}[\|\epsilon_{r,t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$.

Next, we consider the convergence of the quantized SSL training. Note that
objective $\mathcal{L}=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$ is
generally a non-convex and non-smooth function. In our analysis, we consider a
class of functions that satisfies the $\rho$-weak convexity.

######  Definition 1.

A function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $\rho$-weakly convex if
$f(x)+\frac{\rho}{2}\|x\|^{2}$ is convex.

Generally, any function of the form $f(x)=g(h(x))$, where $g(\cdot)$ is convex
and Lipschitz and $h(\cdot)$ is a smooth map with Lipschitz Jacobian, is
weakly-convex. Clearly, the federated SSL objective satisfies $\rho$-weak
convexity with $\rho\geq 4\|\bar{X}\|$. To analyze weakly-convex objective
function $\mathcal{L}$, we introduce the Moreau envelope

$\displaystyle\phi_{\lambda}(x):=\min_{y}\\{\mathcal{L}(y)+\frac{1}{2\lambda}\|y-x\|^{2}\\}$

and define the corresponding proximal map as

$\displaystyle\mathrm{prox}_{\phi_{\lambda}(x)}:=\mathrm{argmin}_{y}\\{\mathcal{L}(y)+\frac{1}{2\lambda}\|y-x\|^{2}\\}.$

We use $\|\nabla\phi_{\lambda}(x)\|$ as the convergence indicator.
Intuitively, small norm of the gradient of $\phi_{\lambda}(x)$ implies that
$x$ is close to a point $\hat{x}$ that is stationary for $\phi$. For Fed-QSSL,
the following result holds.

######  Theorem 1.

Suppose all assumptions of Lemma 1 and Corollary 1 hold. For all
$\bar{\rho}>\rho$, after $T$ communication rounds of Fed-QSSL

$\displaystyle\frac{1}{\sum_{t=0}^{T}\alpha_{tE}}\sum_{t=0}^{T}\alpha_{tE}\mathbb{E}[\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{tE,G})\|^{2}]\leq\frac{E\bar{\rho}}{\bar{\rho}-\rho}\times$
$\displaystyle\frac{\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{0,G})-\min\phi+\bar{\rho}(G^{2}\sum_{t=0}^{T}\alpha^{2}_{tE}+3G_{q}^{2}\sum_{t=0}^{T}\alpha_{tE})}{\bar{\rho}\sum_{t=0}^{T}\alpha_{tE}},$

where $E$ denotes the number of local training epochs per communication round
(for a total of $tE$ training epochs after $t$ communication rounds) and
${\textbf{w}}^{(Q)}_{0,G}$ is the quantized parameter initialization.

Theorem 1 implies convergence of the algorithm to a nearly stationary state of
the objective function. When $\alpha_{t}$ decreases as
${\mathcal{O}}(1/\sqrt{t})$, the upper bound vanishes as $t\to\infty$. The
optimal solution ${\textbf{w}}^{*}$ of the global objective satisfies
$\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{*})\|^{2}=0$; the vanishing
upper bound implies proximity to a neighborhood of the optimal
solution.222While using gradient descent estimates with bounded variance
typically leads to converge to local minima [28], a property of the SSL
objective is that all local minima are global minima [17]. As the quantization
rate $R$ approaches full precision rate, $G_{q}$ vanishes and the upper bound
collapses to the value obtained by vanilla stochastic gradient descent
analysis.

It is further of interest to analyze robustness of the learned
representations. To this end, we first formally define the representation
vector.

######  Definition 2.

[34] Let $\mathcal{S}\subset{\mathbb{R}}^{d}$ be the subspace spanned by the
rows of the learned feature matrix ${\textbf{w}}\in{\mathbb{R}}^{m\times d}$
for the embedding function $f_{{\textbf{w}}}(x)={\textbf{w}}x$. The
representability of $\mathcal{S}$ is defined as the vector
$r=[r_{1},\cdots,r_{d}]^{T}$ such that
$r_{i}=\|\Pi_{\mathcal{S}}(e_{i})\|^{2}$ for $i\in[d]$, where
$\Pi_{\mathcal{S}}(e_{i})$ denotes the projection of standard basis $e_{i}$
onto $\mathcal{S}$ and thus $r_{i}=\sum_{j=1}^{s}\langle
e_{i},v_{j}\rangle^{2}$, $s=\dim(\mathcal{S})$ and $\\{v_{j}\\}$ is the set of
orthonormal bases of $\mathcal{S}$.

Vector $r$ introduced in this definition quantifies representability by
comparing unit bases of different feature spaces. A good feature space should
be such that the entries of $r$ are large, indicating its standard unit bases
can well represent $e_{1},\dots,e_{d}$, the unit bases in ${\mathbb{R}}^{d}$.

######  Theorem 2.

Suppose assumptions of Theorem 1 hold and $n=\Theta(d^{1/20})$. In a $2n$-way
classification task, when in local training the update is $\epsilon$ away from
the optimal solution ${\textbf{w}}_{k}^{*}$, the representation vector learned
by client $k$ with high probability satisfies
$\frac{d^{2/5}-{\mathcal{O}}(d^{-2/5})+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{d^{2/5}+{\mathcal{O}}(d^{-2/5})+\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|}\leq
r_{i}^{k}\leq 1$ for $i\in[n]\backslash\\{k\\}$. As for the global objective,
when the update is $\epsilon_{1}$ away from the optimal solution
${\textbf{w}}^{*}$, the learned representation vector $\bar{r}$ with high
probability satisfies
$\frac{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})-{\mathcal{O}}(d^{2/5})+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})+\|2({\textbf{w}}^{*})^{T}\epsilon_{1}+\epsilon_{1}^{T}\epsilon_{1}\|}\leq\bar{r}_{i}\leq
1$ for all $i\in[n]$.

Theorem 2 implies that as $\epsilon_{1}$ vanishes, the entries in
representation vectors have strictly positive lower bound and thus do not
vanish. This theorem states that the representation space learned from the SSL
objectives is such that for the $2n$ basis directions that generate the data,
any two clients have similar representability. The theorem further implies
that the learned representation vectors are not biased towards local data
distributions and are capable of performing well on uniformly distributed
data, indicating robustness of the scheme. For the proof of Theorem 2, please
see Appendix.

##  5 Experimental Results

We simulate an FL system with $10$ clients, where the participating clients
have different bitwidth configuration and local data distributions. We deploy
two bitwidth configurations: (1) the configuration with gradually increasing
bitwidth: $20\%4$-bit, $30\%6$–bit, $30\%8$-bit and $20\%12$-bit models; and
(2) the configuration with a skewed bitwidth: $50\%6$-bit and $50\%12$-bit
models. The experiments involve CIFAR-10 and CIFAR-100 datasets, both for
image classification tasks [20]. The datasets are distributed to clients in a
non-iid fashion according to Dirichlet$(0.1)$ distribution [1]. Simulations
were executed on AMD Vega $20$ GPUs. The learning rates were set as in the
following prior work: for the supervised learning schemes using low-bit
operations we deploy learning rates as in [40], while for self-supervised
learning schemes we follow [34]. In all simulations, the deployed neural
networks were based on ResNet-18 architecture [12]. The results are reported
after $100$ communication rounds, with clients running $E=20$ local epochs
between any two rounds in CIFAR-10 simulations and $E=5$ in CIFAR-100
simulations. In the implementation of Fed-QSSL, we rely on the SimCLR method
[3] for the self-supervision part of the algorithm.333The codes are available
at https://github.com/YiyueC/Fed-QSSL.

Algorithm | Global Acc | Local Acc
---|---|---
FedAvg | 17.70 | 64.98
FedProx | 14.51 | 68.46
FedPAQ | 16.68 | 62.96
Fed-SimCLR | 39.09 | 77.30
Fed-SimSiam | 36.73 | 76.87
Fed-QSSL | 59.31 | 82.50
Fed-SimCLR (Full) | 40.76 | 80.56
Fed-QSSL (Full) | 72.26 | 90.01
Table 1: Experiments on CIFAR-10 with model bitwidth configuration $20\%4$-bit, $30\%6$–bit, $30\%8$-bit and $20\%12$-bit. Algorithm | Global Acc | Local Acc
---|---|---
FedAvg | 20.77 | 66.64
FedProx | 18.70 | 75.60
FedPAQ | 18.56 | 76.57
Fed-SimCLR | 39.12 | 77.43
Fed-SimSiam | 36.44 | 75.21
Fed-QSSL | 62.26 | 83.03
Fed-SimCLR (Full) | 40.76 | 80.56
Fed-QSSL (Full) | 72.26 | 90.01
Table 2: Experiments on CIFAR-10 with model bitwidth configuration $50\%6$-bit and $50\%12$-bit. Algorithm | Global Acc | Local Acc
---|---|---
Fed-SimCLR | 14.79 | 23.46
Fed-SimSiam | 12.24 | 13.59
Fed-QSSL | 21.44 | 30.91
Fed-SimCLR (Full) | 15.18 | 30.26
Fed-QSSL (Full) | 28.75 | 43.56
Table 3: Experiments on CIFAR-100 with bitwidth configuration $50\%6$-bit and
$50\%12$-bit.

Figure 1: The left y-axis indicates the number of bitwise operations while the
right y-axis indicates the local accuracy achieved by Fed-QSSL.

Figure 2: The left y-axis indicates the memory consumption while the right
y-axis indicates the local accuracy achieved by Fed-QSSL.

Figure 3: Ablation study on Dirichlet distribution parameter $\beta$.

Figure 4: Ablation study on the ratio of the global buffer size and the local
dataset size.

Figure 5: Ablation study on the number of local training epochs $E$.

Baselines. We compare Fed-QSSL with two groups of algorithms: federated
supervised learning (SL) and self-supervised algorithms. The SL algorithms
include FedAvg [27], classic FL technique performing simple averaging of local
models at each communication round; FedProx [22], an FL scheme addressing
client data heterogeneity by adding an $\ell_{2}$-norm regularizer to local
objectives to prevent divergence of local updates from the global model; and
FedPAQ [30], a communication-efficient FL algorithm where clients transmit
quantized updates to reduce uplink communication cost. As for the SSL
algorithms, we consider Fed-SimCLR [3, 34] which uses contrastive learning
objective to learn a global feature extraction model; and Fed-SimSiam [4]
which considers only positive pairs of data points and learn meaningful
features by leveraging a feature predictor function and stop-gradient
operation. While the baseline algorithms are not originally meant to support
local low-bit training, we apply low-bitwidth operations to satisfy resource
constraints. In each table of results, the last two rows (labeled as “Full”)
correspond to full precision ($32$-bit) models, i.e., models with no bitwidth
constraints.

Metrics. Fed-QSSL is compared to the baselines in terms of global accuracy
(Global Acc), reflective of robustness, and local accuracy (Local Acc),
reflecting personalization. SSL methods train a universal linear classifier on
top of the frozen global feature extraction model and evaluate the
classification accuracy on a uniformly distributed test dataset. Training of a
linear classifier to be used for testing global model accuracy is conducted at
full precision on a centralized training dataset as in [34]; this is done only
to validate robustness of SSL methods, in real applications no such universal
linear classifier is required. SSL methods use the aggregated model and test
on uniform testing dataset. To evaluate local accuracy (i.e., the accuracy on
local, generally non-IID datasets), SSL methods train a local linear
classifier on top of the frozen low-bitwidth feature extractor while meeting
client’s bitwidth constraints and run it on a local non-iid testing dataset,
while SL methods use a local low-bitwidth classification model and compute the
accuracy on local testing data.

Results. The results on CIFAR-10 under the first bitwidth configuration are
reported in Table 1. Overall, the global accuracy of SSL schemes is higher
than SL methods, implying that SSL algorithms tend to learn more accurate
representations in data heterogeneous FL scenario. As for the personalization,
SSL algorithms achieve higher accuracy on local data, suggesting they learn
meaningful representations that are then used in the downstream classification
task. It is worth noting that SSL algorithms with higher global accuracy also
achieve higher local accuracy; this is because the learned robust feature
extractor extracts expressive representations from heterogeneous data which
help in downstream classification tasks. Among SL algorithms, however, there
exists a trade-off between robustness and personalization, where the
performance of models with high global accuracy may suffer locally.
Specifically, Fed-QSSL performs better in both bitwidth-heterogeneous and no-
constrained (full precision) scenarios due to the use of server-side
operations on the global buffer; operations on server facilitate learning
robust representations that further improve local performance. Table 2 reports
results on CIFAR-10 under the second bitwidth configuration. There, SSL
algorithms again demonstrate more robust and personalized performance in face
of bitwidth and data heterogeneity. As the permitted bitwidth grows, the
algorithms reach higher accuracy. Nevertheless, under the bitwidth constraints
Fed-QSSL still achieves the highest accuracy. Finally, Table 3 reports results
on the more challenging CIFAR-100 dataset. As can be seen there, Fed-QSSL
perform better than other SSL benchmarks under both low-bitwidth as well as
full precision scenarios.

Computation and Memory Saving. We next compare the computational cost and
memory requirements of Fed-QSSL to those of the full precision scheme. In
particular, for the two bitwidth configurations and the full precision
scenario considered above, we report the number of bitwise operations and
memory footprint in the local training (see Figure 2 and Figure 2). In Figure
2, we show the number of bitwise operations for the considered bitwidth
configurations; as can be seen there, in both forward and backward pass the
computational cost of Fed-QSSL is much smaller than that of the full precision
scheme. In low-bit configurations, the backward propagation is consuming more
computation because the gradient are represented using 2 bits more than the
weights. Figure 2 shows that Fed-QSSL achieves significant memory savings
while still providing competitive accuracy.

Ablation Study. Lastly, Figures 5-5 present results of ablation studies. When
increasing Dirichlet distribution parameter $\beta$, local data distributions
become more uniform and the global accuracy increases. The local accuracy,
however, decreases since the clients start facing more classes and thus need
to execute more challenging classification tasks (Fig. 3). When smaller size
global buffer is used and the ratio of the size of $D_{g}$ and the size of
local data decreases, the global accuracy deteriorates while the local
accuracy remains mostly unchanged (Fig. 4). Finally, as more training epochs
are used in local training, Fed-QSSL achieves higher accuracy (Fig. 5).

##  6 Conclusion and Future Work

We introduced the federated quantized self-supervised learning (Fed-QSSL)
algorithm, an effective framework for FL in bitwidth and data heterogeneity
settings. We analytically studied the impact of low-bit training on the
convergence and robustness of FL, and experimentally demonstrated that Fed-
QSSL achieves more robust and personalized performance than benchmarking
algorithms. Future work may include an extension to large-scale settings where
it is meaningful to cluster clients with similar data distributions, and train
per-cluster models. For such systems, it is of interest to develop schemes
that aim to optimally manage utilization of the available resources.

## A. Appendix

This section is organized as follows. Section A.1 provides notation and sets
up the stage for theoretical analysis. Section A.2-4 present proofs of Lemma
1, Theorem 1 and Theorem 2, respectively. Section A.5 contains details of the
local training under low bitwidth constraints.

### A.1. Preliminaries

#### Notation

Let $n$ denote the number of clients in a FL system. Client $k$ owns dataset
$D_{k}$ containing $|D_{k}|$ samples drawn independently from distribution
$\mathcal{D}_{k}$. Data sample $x\in{\mathbb{R}}^{d}$ is a $d$-dimensional
vector. Parameters of the learned SSL model are denoted by
${\textbf{w}}\in{\mathbb{R}}^{m\times d}$. We use $[n]$ to denote the set
$\\{1,2,\cdots,n\\}$. Let $\mathcal{L}$ denote the global objective function,
while $\mathcal{L}_{k}$ denotes local objective at client $k$. The inner
product of two vectors, x and z, is denoted by
$\langle{\textbf{x}},{\textbf{z}}\rangle$. Finally, let $\|\cdot\|$ be the
$\ell_{2}$-norm of a vector or Frobenius norm of a matrix, and let
$\|\cdot\|_{2}$ denote the $\ell_{2}$-norm of a matrix.

#### Background and settings

We consider a federated learning system with $n$ clients participating in
model learning via self-supervised learning (SSL). The local objective
function used by client $k$ is

$\displaystyle\mathcal{L}_{SSL,k}({\textbf{w}})=-\mathbb{E}[({\textbf{w}}(x_{k,i})+\xi_{k,i})^{T}({\textbf{w}}(x_{k,i})+\xi^{\prime}_{k,i})]+\frac{1}{2}\|{\textbf{w}}^{T}{\textbf{w}}\|^{2},$

where $\xi_{k,i}$ and $\xi^{\prime}_{k,i}$ denote random noise added to the
samples. Then the global objective function is defined as
$\mathcal{L}_{SSL}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}\mathcal{L}_{SSL,k}({\textbf{w}})$.
The goal of the FL system is to find w that minimizes the global objective.
The optimization problem can be written equivalently as
$\min\mathcal{L}({\textbf{w}})=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$,
where $\bar{X}=\sum_{k}\frac{|D_{k}|}{|D|}X_{k}$ and $X_{k}=\mathbb{E}_{x\sim
D_{k}}(xx^{T})=\frac{1}{|D_{k}|}\sum_{i=1}^{|D_{k}|}x_{k,i}x_{k,i}^{T}$
denotes the empirical data covariance matrix at client $k$. Minimization of
the local objective can equivalently be stated as
$\min\mathcal{L}_{k}({\textbf{w}})=\|X_{k}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$.

Recall that the focus of our analysis is on the impact of low-bit operations
deployed in local training on the convergence and robustness of Fed-QSSL. For
analytical tractability, we simplify operations at the server by replacing
sophisticated de-quantizer by a layer-wise codebook mapping low-bitwidth
weights to floating-point values according to
${\textbf{w}}^{\prime(Q)}_{k,t}={\textbf{w}}^{(Q)}_{k,t}$. The subsequent
aggregation follows FedAvg and computes
${\textbf{w}}_{t,G}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}^{\prime(Q)}_{k,t}$,
while re-quantization uses the $\tanh$-based quantizer. For simplicity, we
assume that the clients quantize weights/activations using the same bitwidth,
i.e., $s_{1}=s_{2}=\cdots=s_{n}=R$; moreover, local gradient quantization is
performed using the same number of bits (i.e., $s_{k}$).

Quantization centers used for layer-wise scalar quantization of the model
parameters and gradients are found via companding quantization. Specifically,
full-precision input x is transformed by a nonlinear function $c$, e.g.,
$\tanh$ function, and then uniformly quantized. The output $Q({\textbf{x}})$
is generated by taking the value of the inverse function, $c^{-1}$, of the
quantized value [32]. Uniform quantization is a special case of companding
quantization, obtained by setting $c({\textbf{x}})={\textbf{x}}$. In Fed-QSSL,
local quantizers can also be viewed as special cases of the companding
quantizers. We consider fixed rate quantization, where each codeword
(quantization center) used for quantization has the same length. When the
quantization rate is $R$, the codebook has $K=2^{R}$ codewords [32].

We further assume that the quantization noise has zero mean, which can be
achieved by adopting stochastic quantization: Given a sequence of quantization
centers $Q_{1}\leq\cdots\leq Q_{2^{R}}$, for $x\in[Q_{j},Q_{j+1}]$ we have
$Q(x)=Q_{j}$ with probability $\frac{Q_{j+1}-x}{Q_{j+1}-Q_{j}}$ and
$Q(j)=Q_{j+1}$ with probability $\frac{x-Q_{j}}{Q_{j+1}-Q_{j}}$.

### A.2. Proof of Lemma 1

We first review notation featured in the lemma. Let $\epsilon_{{\textbf{w}}}$
and $\epsilon_{g}$ denote the error induced by quantizing parameters and
gradients, respectively. Let $\epsilon_{r}$ be the quantization error induced
by the server when re-quantizing an aggregated model.

When training at full precision using gradient descent, assuming $E$ epochs of
local training per communication round, the global model update is formed as

$\displaystyle{\textbf{w}}_{t+E,G}=\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}({\textbf{w}}_{t,G}-\sum_{s=0}^{E-1}\alpha_{t+s}\frac{\partial\mathcal{L}_{SSL,k}}{\partial{\textbf{w}}_{t+s,k}}).$

When performing low-bit quantized training, quantized weights of the model
trained by client $k$ are found as

$\displaystyle{\textbf{w}}_{k,t+1}^{(Q)}={\textbf{w}}_{k,t}^{(Q)}-\alpha_{t}({\textbf{g}}_{k,t}+\epsilon_{g_{k},t})+\epsilon_{{\textbf{w}}_{k},t},$

where ${\textbf{w}}_{k,t}^{(Q)}$ denotes the low-bitwidth model parameters at
time $t$, $\epsilon_{g_{k},t}$ is the noise added to the gradient in the
quantization step, and $\epsilon_{{\textbf{w}}_{k},t}$ denotes the noise added
to the model parameters after gradient update as the parameters retain low
bitwidth representation. After $E$ local training epochs, the server collects
the models and aggregates them according to

$\displaystyle{\textbf{w}}_{t+E,G}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}_{t+E,k}^{(Q)}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{n}\frac{|D_{k}|}{|D|}{\textbf{w}}_{k,t}^{{Q}}-\sum_{s=0}^{E-1}[\alpha_{t+s}({\textbf{g}}_{k,t+s}+\epsilon_{g_{k},t+s})-\epsilon_{{\textbf{w}}_{k},t+s}].$

Since the aggregated model is not necessarily in low bit, an additional re-
quantization step is required to form its quantized version
${\textbf{w}}_{t+E,G}^{(Q)}={\textbf{w}}_{t+E,G}+\epsilon_{r,t+E}$, which is
then sent to clients.

We proceed to Lemma 1, an intermediate result characterizing the variance of
quantization errors, $\mathbb{E}_{t}[\|\epsilon_{g_{k},t}\|^{2}]$ and
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]$. The lemma shows that
given low-bitwidth model parameters and small gradient perturbation, the
variance of $\epsilon_{w}$ is proportional to the norm of the gradient
perturbation. In other words, when a small perturbation is added to low-
bitwidth model parameters, the noise induced by quantizing the perturbed
parameters has small variance.

For the result in Lemma 1, we need to make the following assumptions.

######  Assumption 1.

All quantization operators in the low-bit training are unbiased.

######  Assumption 2.

Expected gradient estimate is unbiased and bounded,

$\mathbb{E}_{t}\|{\textbf{g}}_{k,t}\|^{2}\leq G^{2}$.

######  Lemma 1.

Suppose Assumptions 1-2 hold, and that client $k$ computes update of the
quantized model parameters ${\textbf{w}}_{k,t+1}^{(Q)}$ at bitwidth $s_{k}=R$.
Then the gradient quantization error $\epsilon_{g_{k},t}$ satisfies
$\mathbb{E}_{t}[\|\epsilon_{g_{k},t}\|^{2}]={\mathcal{O}}(G^{2}/2^{2R})$, and
the local re-quantization error $\epsilon_{{\textbf{w}}_{k},t}$ satisfies
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]={\mathcal{O}}(\alpha_{t}G^{2}/2^{2R})$.

###### Proof.

Recall that the quantization in Algorithm 1 is conducted layer-wise. Thus, it
suffices to analyze quantization errors for the parameters in the first layer
– the results readily extend to the parameters in the remaining layers. Given
a local update

$\displaystyle{\textbf{w}}_{k,t+1}^{(Q)}={\textbf{w}}_{k,t}^{(Q)}-\alpha_{t}({\textbf{g}}_{k,t}+\epsilon_{g_{k},t})+\epsilon_{{\textbf{w}}_{k},t},$

the gradient update can be viewed as an
${\mathcal{O}}(\alpha_{t}\|{\textbf{g}}_{k,t}\|)$ perturbation of the
corresponding original codebook value. Since
$\mathbb{E}_{t}\|{\textbf{g}}_{k,t}\|^{2}\leq G^{2}$ and we use quantile
quantization for gradient compression, the gradient quantization error
$\epsilon_{g_{k},t}$ has range within ${\mathcal{O}}(\|{\textbf{g}}_{k,t}\|)$.
Therefore, variance of the gradient quantization error
$\mathbb{E}_{t}[\|\epsilon_{g_{k},t}\|^{2}]$ is ${\mathcal{O}}(G^{2})$.

To analyze weight quantization, let ${\textbf{w}}_{\min}$ and
${\textbf{w}}_{\max}$ be the minimal and maximal value in
${\textbf{w}}_{k,t}^{(Q)}$, respectively, and let
${\textbf{w}}^{\prime}_{\min}$ and ${\textbf{w}}^{\prime}_{\max}$ denote the
minimal and maximal value in
${\textbf{w}}_{k,t}^{(Q)}-\alpha_{t}({\textbf{g}}_{k,t}+\epsilon_{g_{k},t})$,
respectively. It then holds that
$|{\textbf{w}}_{\min}-{\textbf{w}}^{\prime}_{\min}|$ is
${\mathcal{O}}(\alpha_{t}\|{\textbf{g}}_{k,t}\|)$ and
$|{\textbf{w}}_{\max}-{\textbf{w}}^{\prime}_{\max}|$ is
${\mathcal{O}}(\alpha_{t}\|{\textbf{g}}_{k,t}\|)$. By leveraging fixed rate
companding quantization with $\tanh$ compander and the fact that the
derivative of $\tanh$ decreases from $1$ to $0$ as the absolute value of the
variable increases, it can be shown that the $k$-th codeword in the codebook
for ${\textbf{w}}^{(Q)}_{k,t+1}$ is at most
${\mathcal{O}}(\alpha_{t}\|{\textbf{g}}_{k,t}\|)$ away from the $k$-th
codeword in the codebook for ${\textbf{w}}^{(Q)}_{k,t}$, which implies that by
using stochastic quantization operator, the variance of
$\epsilon_{{\textbf{w}}_{k},t}$,
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]$, is
${\mathcal{O}}(\alpha_{t}G^{2})$.

In order to derive the relationship between the variance of the quantization
error and the quantization rate in Fed-QSSL, we consider two types of
quantizations: uniform quantization and companding quantization with optimal
compander. Since neural network weights are typically not uniformly
distributed but rather follow centered distributions such as Gaussian or
Laplacian [14], the uniform quantization MSE, which is
${\mathcal{O}}(1/2^{2R})$ with respect to $R$, can be used as an upper bound
on the quantization error. Regarding the lower bound, [32] has shown that the
lowest MSE for companding quantization is achieved by the optimal compander
with the corresponding MSE ${\mathcal{O}}(1/2^{2R})$ with respect to $R$.
Therefore, given the quantization rate $R$, the error of the weight quantizer
in Fed-QSSL is ${\mathcal{O}}(1/2^{2R})$. As for the gradient quantizer which
relies on the quantile quantization method, one can invoke the quantization
MSE of uniform quantization as an upper bound and the MSE of the optimal
companding quantization as a lower bound. By combining the two, it follows
that the gradient quantization error is ${\mathcal{O}}(1/2^{2R})$. Combining
the orders with respect to $G$ and $R$, we can complete the proof. ∎

The corollary below follows directly from the lemma.

######  Corollary 1.

Instate the assumptions of Lemma 1, and let all clients use the same learning
rate $\alpha_{t-E+1}=\cdots=\alpha_{t}$ within the same communication round.
Then there exists $G_{q}={\mathcal{O}}(G^{2}/2^{2R})$ such that
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$
and $\mathbb{E}_{t}[\|\epsilon_{r,t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$.

###### Proof.

From Lemma 1, when locally performing single-step gradient update, the
variance of $\epsilon_{{\textbf{w}}_{k},t}$ is
${\mathcal{O}}(\alpha_{t}G^{2}/2^{2R})$. As for the global update, since all
clients run $E$ local training epochs, each with constant learning rate, and
the update is formed by summing $E$ gradient update, the variance of the re-
quantization error $\epsilon_{r,t}$ is ${\mathcal{O}}(\alpha_{t}G^{2}E)$.
Therefore, there exists $G_{q}={\mathcal{O}}(G^{2}/2^{2R})$ such that
$\mathbb{E}_{t}[\|\epsilon_{{\textbf{w}}_{k},t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$
and $\mathbb{E}_{t}[\|\epsilon_{r,t}\|^{2}]\leq\alpha_{t}G_{q}^{2}$. ∎

### A.3. Proof of Theorem 1

We first review several key definitions and then re-state the theorem. Recall
that the global objective $\mathcal{L}$ is non-convex and non-smooth but
satisfies weakly-convex assumption. We thus proceed with convergence analysis
by relying on techniques encountered in dealing with weakly convex objectives
[8].

Recall that a function $f:{\mathbb{R}}^{d}\to{\mathbb{R}}$ is $\rho$-weakly
convex if $f(x)+\frac{\rho}{2}\|x\|^{2}$ is convex; this definition is readily
extended to matrix variable ${\textbf{w}}\in{\mathbb{R}}^{m\times d}$. In
general, any function of the form $f(x)=g(h(x))$, where $g(\cdot)$ is convex
and Lipschitz and $h(\cdot)$ is a smooth map with Lipschitz Jacobian, is
weakly-convex [8]. Since the global objective function is
$\mathcal{L}=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$, it is
straightforward to see that the global SSL objective satisfies weak convexity
with $\rho\geq 4\|\bar{X}\|$. For a weakly-convex function $\mathcal{L}$, the
key construction is the Moreau envelope,

$\displaystyle\phi_{\lambda}(x):=\min_{y}\\{\mathcal{L}(y)+\frac{1}{2\lambda}\|y-x\|^{2}\\},$

with the corresponding proximal map defined as

$\displaystyle\mathrm{prox}_{\phi_{\lambda}(x)}:=\mathrm{argmin}_{y}\\{\mathcal{L}(y)+\frac{1}{2\lambda}\|y-x\|^{2}\\}.$

The convergence can be quantified and tracked via
$\|\nabla\phi_{\lambda}(x)\|$; in particular, small norm of the gradient of
$\phi_{\lambda}(x)$ implies that $x$ is close to a point
$\hat{x}:=\mathrm{prox}_{\phi_{\lambda}}(x)$ which is stationary for $\phi$.

######  Theorem 1.

Suppose all assumptions in Lemma 1 and Corollary 1 hold. For all
$\bar{\rho}>\rho$, after $T$ communication rounds of Fed-QSSL

$\displaystyle\frac{1}{\sum_{t=0}^{T}\alpha_{tE}}\sum_{t=0}^{T}\alpha_{tE}\mathbb{E}[\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{tE,G})\|^{2}]$
$\displaystyle\leq\frac{E\bar{\rho}}{\bar{\rho}-\rho}\frac{\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{0,G})-\min\phi+\bar{\rho}(G^{2}\sum_{t=0}^{T}\alpha^{2}_{tE}+3G_{q}^{2}\sum_{t=0}^{T}\alpha_{tE})}{\bar{\rho}\sum_{t=0}^{T}\alpha_{tE}},$

where $E$ denotes the number of local training epochs per communication round
(for a total of $tE$ training epochs after $t$ communication rounds) and
${\textbf{w}}^{(Q)}_{0,G}$ is the quantized parameter initialization.

###### Proof.

To analyze the FedAvg-based aggregation with full device participation and $E$
local epochs per communication round, we introduce the following notations.
Let ${\textbf{w}}^{(Q)}_{k,t}$ denote the parameters of model deployed by
client $k$ at time $t$. When $t+1\in\mathcal{I}_{E}=\\{E,2E,\cdots\\}$, the
server collects local models and performs aggregation. Let us consider two
sequences,

$\displaystyle{\textbf{v}}_{k,t+1}$
$\displaystyle={\textbf{w}}^{(Q)}_{k,t}-\alpha_{t}{\textbf{g}}^{(Q)}_{k}({\textbf{w}}_{k,t})+\epsilon_{{\textbf{w}}_{k},t}$
$\displaystyle{\textbf{w}}^{(Q)}_{k,t+1}$
$\displaystyle=\begin{cases}{\textbf{v}}_{k,t+1}&t+1\notin\mathcal{I}_{E}\\\
\sum_{k=1}^{n}p_{k}{\textbf{v}}_{k,t+1}+\epsilon_{r,t+1}&t+1\in\mathcal{I}_{E}\end{cases}$

where the auxiliary variable ${\textbf{v}}_{t+1,k}$ is an intermediate result
of one-step quantized (stochastic) gradient descent update for
${\textbf{w}}^{(Q)}_{k,t}$ 444Please note that this notation is consistent
with the global update ${\textbf{w}}^{(Q)}_{k,t}$ in Algorithm 1 when
$t\in\mathcal{I}_{E}$. For all other time steps, global aggregation is not
accessible and has no bearing to real applications. and
$p_{k}=\frac{|D_{k}|}{|D|}$. As stated before, local quantized gradient
estimate ${\textbf{g}}^{(Q)}_{k}({\textbf{w}}_{k,t})$ is assumed to be an
unbiased estimate of the true gradient. For the global model analysis we
examine two virtual sequences, $\\{{\textbf{v}}_{t,G}\\}$ and
$\\{{\textbf{w}}^{(Q)}_{t,G}\\}$, with
${\textbf{v}}_{t,G}=\sum_{k=1}^{n}p_{k}{\textbf{v}}_{k,t}$ and
${\textbf{w}}^{(Q)}_{t,G}=\sum_{k=1}^{n}p_{k}{\textbf{w}}^{(Q)}_{k,t}$. In the
full participation scenario, it always holds that
${\textbf{v}}_{t,G}={\textbf{w}}^{(Q)}_{t,G}$ when $t\notin\mathcal{I}_{E}$
and ${\textbf{v}}_{t,G}+\epsilon_{r,t}={\textbf{w}}^{(Q)}_{t,G}$ otherwise.

Define $v_{t}=\mathbb{E}_{t}[{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})]$ where
${\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})=\sum_{k=1}^{n}p_{k}({\textbf{g}}^{(Q)}_{k,t}-\epsilon_{{\textbf{w}}_{k},t}/\alpha_{t})$
and
$\hat{{\textbf{x}}}:=\mathrm{prox}_{\phi_{\frac{1}{\bar{\rho}}}}({\textbf{x}})$
for any constant $\bar{\rho}>\rho$. Following Corollary 1, there exists
$G,G_{q}>0$ such that
$\mathbb{E}_{t}[\|{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})\|^{2}]\leq
G^{2}+2G_{q}^{2}$ and
$\mathbb{E}_{t}\|\epsilon_{r,t}\|^{2}\leq\alpha_{t}G_{q}^{2}$. When
$t\notin\mathcal{I}_{E}$, it holds that

$\displaystyle\mathbb{E}_{t}[\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t+1,G})]$
$\displaystyle\leq\mathbb{E}_{t}[\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\|\hat{{\textbf{w}}}_{t,G}-{\textbf{w}}^{(Q)}_{t+1,G}\|^{2}]$
$\displaystyle=\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\mathbb{E}_{t}[\frac{\bar{\rho}}{2}\|\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{v}}_{t+1,G}\|^{2}]$
$\displaystyle=\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\mathbb{E}_{t}[\|({\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G})-\alpha_{t}{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})\|^{2}]$
$\displaystyle\leq\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\|{\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G}\|^{2}+\bar{\rho}\alpha_{t}\mathbb{E}_{t}\langle\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{w}}^{(Q)}_{t,G},{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})\rangle+\bar{\rho}(\alpha_{t}^{2}G^{2}+2\alpha_{t}G_{q}^{2})$
$\displaystyle\leq\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})+\bar{\rho}\alpha_{t}\langle\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{w}}^{(Q)}_{t,G},v_{t}\rangle+\bar{\rho}(\alpha_{t}^{2}G^{2}+2\alpha_{t}G_{q}^{2})$
$\displaystyle\leq\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})+\bar{\rho}\alpha_{t}(\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})-\mathcal{L}({\textbf{w}}^{(Q)}_{t,G})+\frac{\rho}{2}\|{\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G}\|^{2})+\bar{\rho}(\alpha_{t}^{2}G^{2}+2\alpha_{t}G_{q}^{2}),$

where the second inequality follows from the Young’s inequality on the
gradient variance, while the last inequality follows from the property of
$\rho$-weakly convex functions.

When $t\in\mathcal{I}_{E}$, we recall that
${\textbf{v}}_{t,G}+\epsilon_{r,t}={\textbf{w}}_{t,G}$ and
$\mathbb{E}_{t}[\epsilon_{r,t}]=0$, leading to

$\displaystyle\mathbb{E}_{t}[\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t+1,G})]$
$\displaystyle\leq\mathbb{E}_{t}[\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\|\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{w}}^{(Q)}_{t+1,G}\|^{2}]$
$\displaystyle=\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\mathbb{E}_{t}[\frac{\bar{\rho}}{2}\|\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{v}}_{t+1,G}-\epsilon_{r,t}\|^{2}]$
$\displaystyle=\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\mathbb{E}_{t}[\|({\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G})-\alpha_{t}{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})-\epsilon_{r}\|^{2}]$
$\displaystyle\leq\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})+\frac{\bar{\rho}}{2}\|{\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G}\|^{2}+\bar{\rho}\alpha_{t}\mathbb{E}_{t}\langle\hat{{\textbf{w}}}^{(Q)}_{t,G}-{\textbf{w}}^{(Q)}_{t,G},{\textbf{g}}({\textbf{w}}^{(Q)}_{t,G})\rangle+\bar{\rho}(\alpha_{t}^{2}G^{2}+3\alpha_{t}G_{q}^{2})$
$\displaystyle\leq\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})+\bar{\rho}\alpha_{t}(\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})-\mathcal{L}({\textbf{w}}^{(Q)}_{t,G})+\frac{\rho}{2}\|{\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G}\|^{2})+\bar{\rho}(\alpha_{t}^{2}G^{2}+3\alpha_{t}G_{q}^{2}).$

Next, by using the fact that
$\mathcal{L}(x)+\frac{\bar{\rho}}{2}\|x-x_{t}\|^{2}$ is
$(\bar{\rho}-\rho)$-strongly convex we obtain

$\displaystyle\mathcal{L}(\hat{{\textbf{w}}}^{(Q)}_{t,G})-\mathcal{L}({\textbf{w}}^{(Q)}_{t,G})+\frac{\rho}{2}\|{\textbf{w}}^{(Q)}_{t,G}-\hat{{\textbf{w}}}^{(Q)}_{t,G}\|^{2}\leq\frac{\rho-\bar{\rho}}{\bar{\rho}^{2}}\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})\|^{2}.$

This further implies that

$\displaystyle\mathbb{E}_{t}[\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t+1,G})]$
$\displaystyle\leq\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})-\alpha_{t}\frac{\bar{\rho}-\rho}{\bar{\rho}}\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})\|^{2}+\bar{\rho}(\alpha_{t}^{2}G^{2}+3\alpha_{t}G_{q}^{2}).$

By telescoping and rearranging, we obtain

$\displaystyle\frac{1}{\sum_{t=0}^{T}\alpha_{t}}\sum_{t=0}^{T}\alpha_{t}\mathbb{E}[\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{t,G})\|^{2}]$
$\displaystyle\leq\frac{\bar{\rho}}{\bar{\rho}-\rho}\frac{\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{0,G})-\min\phi+\bar{\rho}(G^{2}\sum_{t=0}^{T}\alpha^{2}_{t}+3G_{q}^{2}\sum_{t=0}^{T}\alpha_{t})}{\bar{\rho}\sum_{t=0}^{T}\alpha_{t}}.$

Recall that ${\textbf{w}}_{t,G}$ is accessible only when
$t\in\mathcal{I}_{E}$; hence, we consider only these time steps. If we assume
that at each communication round the client uses the same learning rate
throughout $E$ local training epochs, we finally obtain that

$\displaystyle\frac{1}{\sum_{t=0}^{T}\alpha_{tE}}\sum_{t=0}^{T}\alpha_{tE}\mathbb{E}[\|\nabla\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{tE,G})\|^{2}]$
$\displaystyle\leq\frac{E\bar{\rho}}{\bar{\rho}-\rho}\frac{\phi_{\frac{1}{\bar{\rho}}}({\textbf{w}}^{(Q)}_{0,G})-\min\phi+\bar{\rho}(G^{2}\sum_{t=0}^{T}\alpha^{2}_{tE}+3G_{q}^{2}\sum_{t=0}^{T}\alpha_{tE})}{\bar{\rho}\sum_{t=0}^{T}\alpha_{tE}}.$

∎

While this result demonstrates convergence to a neighborhood of a stationary
point, the specific SSL objective,
$\mathcal{L}({\textbf{w}})=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$, has
property that all local minima are global minima [17]. The convergence to
local minima via gradient descent using bounded-variance gradient estimates
has been studied in [28] under more restrictive conditions including
smoothness. It has been shown that for $\Gamma\geq\lambda_{1}(\bar{X})$,
function $\mathcal{L}({\textbf{w}})$ is $16\Gamma$-smooth within the region
$\\{{\textbf{w}}|\|{\textbf{w}}\|_{2}^{2}\leq\Gamma\\}$. Thus a suitable
choice of $\Gamma$ and step size $\alpha_{t}$ guarantee that
${\textbf{w}}_{t}$ remains within the region as long as ${\textbf{w}}_{t-1}$
is within the region [17]. Therefore, Fed-QSSL approaches the neighborhood of
the local minima of $\mathcal{L}(\cdot)$ and, ultimately, that of the global
minima.

### A.4. Proof of Theorem 2

Heterogeneous data construction.  The construction of heterogeneous data
follows [34]. Suppose there are $n=\Theta(d^{1/20})$ data sets/sources, one
for each client, consisting of points that belong to $2n$ classes. For the
data set at client $k$, the majority of points belong to classes $2k-1$ and
$2k$, while a few remaining points come from other classes. We use
$e_{1},\dots,e_{d}$ to denote the standard unit basis of ${\mathbb{R}}^{d}$. A
data sample from class $2k-1$ is generated as
$x^{(2k-1)}=e_{k}-\sum_{i=1,i\neq k}^{n}q^{(2k-1,i)}\tau
e_{i}+\mu\xi^{(2k-1)}$, where $q^{(2k-1,i)}\in\\{0,1\\}$ is uniformly sampled,
$\xi^{(2k-1)}\sim\mathcal{N}(0,I)$, $\tau=d^{1/5}$ and $\mu=d^{-1/5}$.
Likewise, a data sample from class $2k$ is generated as
$x^{(2k)}=-e_{k}-\sum_{i=1,i\neq k}^{n}q^{(2k,i)}\tau e_{i}+\mu\xi^{(2k-1)}$.
The numbers of data points in classes $2k-1$ and $2k$ are the same and of
order $poly(d)$. As for the other classes, a data sample from class $2i-1$ is
generated as $x^{(2i-1)}=e_{i}+\mu\xi^{(2i-1)}$ when $i\neq k$ and there are
no data samples in class $2i$. The numbers of data points in class $2k-1$ and
class $2k$ are the same and of order ${\mathcal{O}}(d^{\beta})$ for some
$\beta\in(0,1)$ such that
${\mathcal{O}}(nd^{\beta})\leq{\mathcal{O}}(d^{1/5})$, implying that the total
number of data samples in infrequent classes is much smaller than the number
of data samples in the frequent classes (i.e., in classes $2k-1$ and $2k$).
For simplicity, we assume that all data sets are of the same cardinality,
i.e., $\frac{|D_{k}|}{|D|}=\frac{1}{n}$ for all $k\in[n]$.

The following theorem quantifies the robustness property.

######  Theorem 2.

Suppose assumptions of Theorem 1 hold and $n=\Theta(d^{1/20})$. In a $2n$-way
classification task, when in local training the update is $\epsilon$ away from
the optimal solution ${\textbf{w}}_{k}^{*}$, the representation vector learned
by client $k$ with high probability satisfies
$\frac{d^{2/5}-{\mathcal{O}}(d^{-2/5})+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{d^{2/5}+{\mathcal{O}}(d^{-2/5})+\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|}\leq
r_{i}^{k}\leq 1$ for $i\in[n]\backslash\\{k\\}$. As for the global objective,
when the update is $\epsilon_{1}$ away from the optimal solution
${\textbf{w}}^{*}$, the learned representation vector $\bar{r}$ with high
probability satisfies

$\frac{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})-{\mathcal{O}}(d^{2/5})+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})+\|2({\textbf{w}}^{*})^{T}\epsilon_{1}+\epsilon_{1}^{T}\epsilon_{1}\|}\leq\bar{r}_{i}\leq
1$ for all $i\in[n]$.

Technical challenges. While the robustness of ${\textbf{w}}^{*}$ was analyzed
in [34], it is unclear how to extended it to quantifying robustness when the
update obtained by the proposed algorithm approaches the optimal solution. To
facilitate such analysis, we initiate it at the step the obtained update is
$\epsilon_{1}$ distance away from the optimal ${\textbf{w}}^{*}$; this maps
the problem to that of analyzing perturbed representation vectors and data
covariance matrix. We conduct such analysis by borrowing ideas from matrix
perturbation theory.

###### Proof.

For the local data set/source at client $k$,

$X_{k}=\mathbb{E}_{x\sim
D_{k}}(xx^{T})=\frac{1}{|D_{k}|}\sum_{i=1}^{|D_{k}|}x_{k,i}x_{k,i}^{T}$

is the empirical covariance matrix. Its expectation is

$\displaystyle\mathbb{E}[X_{k}]$
$\displaystyle=\mathrm{diag}(\tau^{2}+O(d^{-2/5}),\cdots,1+O(d^{-2/5}),\cdots,\tau^{2}+O(d^{-2/5}),O(d^{-2/5})$
(2) $\displaystyle\quad\cdots,O(d^{-2/5}))$
$\displaystyle=\mathrm{diag}(d^{2/5}+O(d^{-2/5}),\cdots,1+O(d^{-2/5}),\cdots,d^{2/5}+O(d^{-2/5}),O(d^{-2/5}),$
$\displaystyle\quad\cdots,O(d^{-2/5})),$

where the first $n$ diagonal entries in the first equality are
$\tau^{2}+O(d^{-2/5})$, except the $k$-th entry which is $1+O(d^{-2/5})$; the
remaining $d-n$ diagonal entries are $O(d^{-2/5})$.

Using matrix concentration bounds [33] and Weyl’s inequality, we have that
with high probability

$\displaystyle|\lambda_{k,i}-\lambda_{i}(\mathbb{E}X_{k})|\leq\|X_{k}-\mathbb{E}X_{k}\|_{2}\leq
O(d^{-2/5}),$ (3)

where $\lambda_{k,i}$ represents the $i$-th largest eigenvalue of $X_{k}$.

Since $|D_{k}|$ is of the order $poly(d)$, one can leverage Lemma E.1 in [25]
to obtain that
$\sum_{i=1}^{|D_{k}|}|\langle\xi_{k,i},e_{k}\rangle|/|D_{k}|\leq O(d^{1/10})$.
For $\mu=d^{-1/5}$,

$\displaystyle
e_{j}^{T}X_{k}e_{j}=\mathbb{E}[(e_{j}^{T}x)^{2}]\geq[\mathbb{E}(e_{j}^{T}x)]^{2}\geq(\frac{1}{3}\tau-\mu\sum_{i=1}^{|D_{k}|}\frac{1}{|D_{k}|}|e_{j}^{T}\xi_{k,i}|)=\Omega(\tau^{2})=\Omega(d^{2/5})$

with probability at least $1-\frac{1}{2}e^{-d^{1/10}}$. The second inequality
follows from the fact that for at least $1/3$ data points it holds that either
$q^{2k-1,j}$ or $q^{2k,j}$ is $1$. From (2) and (3), one can further obtain
that

$\displaystyle e_{j}^{T}X_{k}e_{j}$
$\displaystyle=e_{j}^{T}\mathbb{E}[X_{k}]e_{j}+e_{j}^{T}(X_{k}-\mathbb{E}(X_{k}))e_{j}$
(4) $\displaystyle\geq
d^{2/5}+{\mathcal{O}}(d^{-2/5})-\|X_{k}-\mathbb{E}(X_{k})\|\geq
d^{2/5}-{\mathcal{O}}(d^{-2/5}),$

and

$\displaystyle\lambda_{k,1}\leq\lambda_{1}(\mathbb{E}(X_{k}))+{\mathcal{O}}(d^{-2/5})=d^{2/5}+{\mathcal{O}}(d^{-2/5}).$
(5)

Recall that the local optimization problem can equivalently be written as the
minimization of a local objective function
$\mathcal{L}_{k}=\|X_{k}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$. By Eckart-Young-
Mirsky theorem, minimizing $\mathcal{L}_{k}$ leads to solution
${\textbf{w}}_{k}^{*}\in{\mathbb{R}}^{m\times d}$ whose rows are eigenvectors
of the first $m$ eigenvalues of $X_{k}$. Let $\\{v_{k,1},\cdots,v_{k,d}\\}$ be
the set of $d$ orthonormal eigenvectors of $X_{k}$,
$X_{k}=\sum_{i=1}^{d}\lambda_{k,i}v_{k,i}v_{k,i}^{T}$, and
$({\textbf{w}}^{*}_{k})^{T}({\textbf{w}}^{*}_{k})=\sum_{i=1}^{m}\lambda_{k,i}v_{k,i}v_{k,i}^{T}$.
We readily obtain that

$\displaystyle\lambda_{k,1}\sum_{i=1}^{d}(e_{j}^{T}v_{k,i})^{2}\geq
e_{j}^{T}X_{k}e_{j}=\sum_{i=1}^{d}\lambda_{k,i}(e_{j}^{T}v_{k,i})^{2}$ (6)

with probability of at least $1-\frac{1}{2}e^{-d^{1/10}}$. Suppose the update
is within $\epsilon$ distance from the optimal solution, i.e.,
${\textbf{w}}_{k,t}={\textbf{w}}_{k}^{*}+\epsilon$. Let
${\textbf{w}}_{k,t}^{T}{\textbf{w}}_{k,t}=\sum_{i=1}^{m}\lambda^{\prime}_{k,i}(v^{\prime}_{k,i})^{T}v^{\prime}_{k,i}$.
For $i>m$, we define $v^{\prime}_{k,i}=v_{k,i}$ and
$\lambda^{\prime}_{k,i}=\lambda_{k,i}$. Invoking result from matrix
perturbation theory,

$\displaystyle\max_{1\leq i\leq
d}|\lambda_{t}(A+E)-\lambda_{t}(A)|\leq\|E\|_{2}\leq\|E\|,$ (7)

which implies that $|\lambda_{k,i}-\lambda^{\prime}_{k,i}|$ is upper bounded
by $\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|$ for any
$i\in[n]$. From (4)-(6) and
${\textbf{w}}_{k,t}={\textbf{w}}_{k}^{*}+\epsilon$, it follows that

$\displaystyle\sum_{i=1}^{d}(e_{j}^{T}v^{\prime}_{k,i})^{2}$
$\displaystyle\geq\frac{e_{j}^{T}X_{k}e_{j}+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{\lambda^{\prime}_{k,1}}$
$\displaystyle\geq\frac{e_{j}^{T}X_{k}e_{j}+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{\lambda_{k,1}+\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|}$
$\displaystyle\geq\frac{d^{2/5}-{\mathcal{O}}(d^{-2/5})+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{d^{2/5}+{\mathcal{O}}(d^{-2/5})+\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|}.$

Let $r^{k}=[r_{1}^{k},\cdots,r_{d}^{k}]^{T}$ be the representation vector
learned at client $k$. Then $\forall i\in[n]/\\{k\\}$,

$\displaystyle\frac{d^{2/5}-{\mathcal{O}}(d^{-2/5})+2e_{j}^{T}({\textbf{w}}_{k}^{*})^{T}\epsilon
e_{j}+(e_{j}^{T}\epsilon)^{2}}{d^{2/5}+{\mathcal{O}}(d^{-2/5})+\|2({\textbf{w}}_{k}^{*})^{T}\epsilon+\epsilon^{T}\epsilon\|}\leq
r_{i}^{k}.$

Next we move to the global objective,
$\mathcal{L}=\|\bar{X}-{\textbf{w}}^{T}{\textbf{w}}\|^{2}$, where
$\bar{X}=\mathbb{E}_{x\sim
D}(xx^{T})=\sum_{k}\frac{|D_{k}|}{|D|}X_{k}=\frac{1}{|D|}\sum_{i=1}^{|D|}x_{i}x_{i}^{T}$
is the empirical global data covariance matrix. Following the linearity of
expectation and the fact that

$\displaystyle\frac{(n-1)d^{2/5}+1}{n}$
$\displaystyle=(1-\Theta(d^{-1/20}))d^{2/5}+{\mathcal{O}}(d^{-1/20})$
$\displaystyle=d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20}),$

we obtain the expectation of the covariance matrix as

$\displaystyle\mathbb{E}[{\bar{X}}]$
$\displaystyle=\mathrm{diag}(d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20}),\cdots,d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20}),$
$\displaystyle\quad{\mathcal{O}}(d^{-2/5}),\cdots,{\mathcal{O}}(d^{-2/5}))$

where the first $n$ entries are of the same order while the remaining $d-n$
entries are ${\mathcal{O}}(d^{-2/5})$. Let $\\{v_{1},\cdots,v_{d}\\}$ be the
set of $d$ orthonormal eigenvectors of
$\bar{X}=\sum_{i=1}^{d}\lambda_{i}v_{i}v_{i}^{T}$, and
$({\textbf{w}}^{*})^{T}({\textbf{w}}^{*})=\sum_{i=1}^{m}\lambda_{i}v_{i}v_{i}^{T}$.

Follow similar techniques to analyze local objectives leads to

$\displaystyle e_{j}^{T}\bar{X}e_{j}$ $\displaystyle\geq
d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})-{\mathcal{O}}(d^{2/5})$
$\displaystyle\lambda_{1}(\bar{X})$
$\displaystyle\leq\lambda_{1}(\mathbb{E}(\bar{X}))+{\mathcal{O}}(d^{2/5})=d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20}).$

Next, we consider perturbation
${\textbf{w}}_{t}={\textbf{w}}^{*}+\epsilon_{1}$ of the global optimal
solution ${\textbf{w}}^{*}$. Let
${\textbf{w}}_{t}^{T}{\textbf{w}}_{t}=\sum_{i=1}^{m}\lambda^{\prime}_{i}(\bar{v}^{\prime}_{i})^{T}\bar{v}^{\prime}_{i}$.
For $i>m$, denote $\bar{v}^{\prime}_{i}=\bar{v}_{i}$ and
$\lambda^{\prime}_{i}=\lambda_{i}$. Then

$\displaystyle\sum_{i=1}^{d}(e_{j}^{T}\bar{v^{\prime}}_{i})^{2}$
$\displaystyle\geq\frac{e_{j}^{T}\bar{X}e_{j}+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{\lambda^{\prime}_{1}}$
$\displaystyle\geq\frac{e_{j}^{T}\bar{X}e_{j}+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{\lambda_{1}+\|2({\textbf{w}}^{*})^{T}\epsilon_{1}+\epsilon_{1}^{T}\epsilon_{1}\|}$
$\displaystyle\geq\frac{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})-{\mathcal{O}}(d^{2/5})+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})+\|2({\textbf{w}}^{*})^{T}\epsilon_{1}+\epsilon_{1}^{T}\epsilon_{1}\|}$

where the second inequality is due to the matrix perturbation result (7)
applied to the global data covariance matrix.

We then let $\bar{r}=[\bar{r}_{1},\cdots,\bar{r}_{d}]^{T}$ be the
representation vector learned from the global objective and $\forall i\in[n]$,

$\displaystyle\frac{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})-{\mathcal{O}}(d^{2/5})+2e_{j}^{T}({\textbf{w}}^{*})^{T}\epsilon_{1}e_{j}+(e_{j}^{T}\epsilon_{1})^{2}}{d^{2/5}-\Theta(d^{7/20})+{\mathcal{O}}(d^{-1/20})+\|2({\textbf{w}}^{*})^{T}\epsilon_{1}+\epsilon_{1}^{T}\epsilon_{1}\|}\leq\bar{r}_{i}$

∎

Algorithm 2 Fed-QSSL local training: client $k$ trains on $L$-layer network
with $s_{k}$-bit weights and activations using $s_{k}+2$-bit gradients.

Require: a minibatch of inputs $a_{0}$ , previous weights
${\textbf{w}}^{(Q)}_{k,t}$ in $s_{k}$-bit, learning rate $\alpha_{t}$,
activation function $h$

1: $\\{$ Forward pass $\\}$

2: for $l=1$ to $L$ do

3: $\tilde{a}_{l}\leftarrow$ forward($a_{l-1},({\textbf{w}}^{(Q)}_{k,t})_{l}$)

4: $a_{l}\leftarrow h(\tilde{a}_{l})$

5: Compute $a^{(Q)}_{l}$ through $\tanh$-based quantizer

6: end for

7: $\\{$ Back propagation $\\}$

8: Compute the gradient $g_{a_{L}}$ at the last layer and then compress to
$g^{(Q)}_{a_{L}}$

9: for $l=L$ to $1$ do

10: $g_{a_{l-1}}\leftarrow$ inputs
backpropagation$(g^{(Q)}_{a_{l}},({\textbf{w}}^{(Q)}_{k,t})_{l})$

11: $(g_{{\textbf{w}}_{k,t}})_{l}\leftarrow$ weights
backpropagation$(g^{(Q)}_{a_{l}},a^{(Q)}_{l-1})$

12: Compute $g^{(Q)}_{a_{l-1}}$ via quantile quantization

13: Compute $(g^{(Q)}_{k,t})_{l}$ via quantile quantization

14: end for

15: $\\{$ Weight update $\\}$

16:
${\textbf{w}}^{(Q)}_{k,t+1}=Q({\textbf{w}}^{(Q)}_{k,t}-\alpha_{t}{\textbf{g}}^{(Q)}_{k,t})$

### A.5. Local Training Implementation Details

Details of local quantized training (steps 5-6 in Fed-QSSL in the main
manuscript) are specified in Algorithm 2. In particular, in the forward pass
we go from the first layer to the last one, obtain quantized activations along
the way; in the backward propagation, we go from the last layer back to the
first layer, computing and quantizing gradients in the process.

## References

  * [1] Bibikar, S., Vikalo, H., Wang, Z., and Chen, X. Federated dynamic sparse training: Computing less, communicating less, yet learning better.  In Proceedings of the AAAI Conference on Artificial Intelligence (2022), vol. 36, pp. 6080–6088.
  * [2] Cao, Y.-H., Sun, P., Huang, Y., Wu, J., and Zhou, S. Synergistic self-supervised and quantization learning.  In European Conference on Computer Vision (2022), Springer, pp. 587–604.
  * [3] Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations.  In International conference on machine learning (2020), PMLR, pp. 1597–1607.
  * [4] Chen, X., and He, K. Exploring simple siamese representation learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (2021), pp. 15750–15758.
  * [5] Chen, Y., Hashemi, A., and Vikalo, H. Communication-efficient variance-reduced decentralized stochastic optimization over time-varying directed graphs.  IEEE Transactions on Automatic Control 67, 12 (2021), 6583–6594.
  * [6] Chen, Y., Hashemi, A., and Vikalo, H. Decentralized optimization on time-varying directed graphs under communication constraints.  In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2021), IEEE, pp. 3670–3674.
  * [7] Chen, Y., Sun, X., and Jin, Y. Communication-efficient federated deep learning with layerwise asynchronous model update and temporally weighted aggregation.  IEEE transactions on neural networks and learning systems 31, 10 (2019), 4229–4238.
  * [8] Davis, D., and Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions.  SIAM Journal on Optimization 29, 1 (2019), 207–239.
  * [9] Diao, E., Ding, J., and Tarokh, V. Heterofl: Computation and communication efficient federated learning for heterogeneous clients.  arXiv preprint arXiv:2010.01264 (2020).
  * [10] Ghosh, A., Chung, J., Yin, D., and Ramchandran, K. An efficient framework for clustered federated learning.  Advances in Neural Information Processing Systems 33 (2020), 19586–19597.
  * [11] He, C., Yang, Z., Mushtaq, E., Lee, S., Soltanolkotabi, M., and Avestimehr, S. Ssfl: Tackling label deficiency in federated learning via personalized self-supervision.  arXiv preprint arXiv:2110.02470 (2021).
  * [12] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition (2016), pp. 770–778.
  * [13] Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and Bengio, Y. Quantized neural networks: Training neural networks with low precision weights and activations.  The Journal of Machine Learning Research 18, 1 (2017), 6869–6898.
  * [14] Isik, B., Weissman, T., and No, A. An information-theoretic justification for model pruning.  In International Conference on Artificial Intelligence and Statistics (2022), PMLR, pp. 3821–3846.
  * [15] Jiang, D., Shan, C., and Zhang, Z. Federated learning algorithm based on knowledge distillation.  In 2020 International Conference on Artificial Intelligence and Computer Engineering (ICAICE) (2020), IEEE, pp. 163–167.
  * [16] Jiang, Y., Konevcnỳ, J., Rush, K., and Kannan, S. Improving federated learning personalization via model agnostic meta learning.  arXiv preprint arXiv:1909.12488 (2019).
  * [17] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. How to escape saddle points efficiently.  In International conference on machine learning (2017), PMLR, pp. 1724–1732.
  * [18] Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning.  Foundations and Trends® in Machine Learning 14, 1–2 (2021), 1–210.
  * [19] Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averaging for federated learning.  In International conference on machine learning (2020), PMLR, pp. 5132–5143.
  * [20] Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images.
  * [21] Li, Q., Diao, Y., Chen, Q., and He, B. Federated learning on non-iid data silos: An experimental study.  In 2022 IEEE 38th International Conference on Data Engineering (ICDE) (2022), IEEE, pp. 965–978.
  * [22] Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks.  Proceedings of Machine learning and systems 2 (2020), 429–450.
  * [23] Li, X., Huang, K., Yang, W., Wang, S., and Zhang, Z. On the convergence of fedavg on non-iid data.  arXiv preprint arXiv:1907.02189 (2019).
  * [24] Lin, T., Kong, L., Stich, S. U., and Jaggi, M. Ensemble distillation for robust model fusion in federated learning.  Advances in Neural Information Processing Systems 33 (2020), 2351–2363.
  * [25] Liu, H., HaoChen, J. Z., Gaidon, A., and Ma, T. Self-supervised learning is more robust to dataset imbalance.  arXiv preprint arXiv:2110.05025 (2021).
  * [26] Makhija, D., Ho, N., and Ghosh, J. Federated self-supervised learning for heterogeneous clients.  arXiv preprint arXiv:2205.12493 (2022).
  * [27] McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data.  In Artificial Intelligence and Statistics (2017), pp. 1273–1282.
  * [28] Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V. On the almost sure convergence of stochastic gradient descent in non-convex problems.  Advances in Neural Information Processing Systems 33 (2020), 1117–1128.
  * [29] Rastegari, M., Ordonez, V., Redmon, J., and Farhadi, A. Xnor-net: Imagenet classification using binary convolutional neural networks.  In European conference on computer vision (2016), Springer, pp. 525–542.
  * [30] Reisizadeh, A., Mokhtari, A., Hassani, H., Jadbabaie, A., and Pedarsani, R. Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization.  In International Conference on Artificial Intelligence and Statistics (2020), PMLR, pp. 2021–2031.
  * [31] Servetnyk, M., Fung, C. C., and Han, Z. Unsupervised federated learning for unbalanced data.  In GLOBECOM 2020-2020 IEEE Global Communications Conference (2020), IEEE, pp. 1–6.
  * [32] Sun, J. Z., and Goyal, V. K. Scalar quantization for relative error.  In 2011 Data Compression Conference (2011), IEEE, pp. 293–302.
  * [33] Vershynin, R. High-dimensional probability: An introduction with applications in data science, vol. 47.  Cambridge university press, 2018.
  * [34] Wang, L., Zhang, K., Li, Y., Tian, Y., and Tedrake, R. Does learning from decentralized non-iid unlabeled data benefit from self supervision?  In The Eleventh International Conference on Learning Representations (2022).
  * [35] Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. Terngrad: Ternary gradients to reduce communication in distributed deep learning.  Advances in neural information processing systems 30 (2017).
  * [36] Yoon, J., Park, G., Jeong, W., and Hwang, S. J. Bitwidth heterogeneous federated learning with progressive weight dequantization.  In International Conference on Machine Learning (2022), PMLR, pp. 25552–25565.
  * [37] Zhang, H., Li, J., Kara, K., Alistarh, D., Liu, J., and Zhang, C. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning.  In International Conference on Machine Learning (2017), PMLR, pp. 4035–4043.
  * [38] Zhang, X., Liu, S., Zhang, R., Liu, C., Huang, D., Zhou, S., Guo, J., Guo, Q., Du, Z., Zhi, T., et al. Fixed-point back-propagation training.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (2020), pp. 2330–2338.
  * [39] Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., and Chandra, V. Federated learning with non-iid data.  arXiv preprint arXiv:1806.00582 (2018).
  * [40] Zhou, S., Wu, Y., Ni, Z., Zhou, X., Wen, H., and Zou, Y. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  arXiv preprint arXiv:1606.06160 (2016).
  * [41] Zhu, F., Gong, R., Yu, F., Liu, X., Wang, Y., Li, Z., Yang, X., and Yan, J. Towards unified int8 training for convolutional neural network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (2020), pp. 1969–1979.
  * [42] Zhuang, W., Wen, Y., and Zhang, S. Divergence-aware federated self-supervised learning.  arXiv preprint arXiv:2204.04385 (2022).