# Spectral Co-Distillation for Personalized Federated Learning

Zihan Chen1, Howard H. Yang2, Tony Q.S. Quek1, and Kai Fong Ernest Chong1
1Singapore University of Technology and Design (SUTD)
2Zhejiang University/University of Illinois Urbana-Champaign Institute,
Zhejiang University
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Personalized federated learning (PFL) has been widely investigated to address
the challenge of data heterogeneity, especially when a single generic model is
inadequate in satisfying the diverse performance requirements of local clients
simultaneously. Existing PFL methods are inherently based on the idea that the
relations between the generic global and personalized local models are
captured by the similarity of model weights. Such a similarity is primarily
based on either partitioning the model architecture into generic versus
personalized components, or modeling client relationships via model weights.
To better capture similar (yet distinct) generic versus personalized model
representations, we propose spectral distillation, a novel distillation method
based on model spectrum information. Building upon spectral distillation, we
also introduce a co-distillation framework that establishes a two-way bridge
between generic and personalized model training. Moreover, to utilize the
local idle time in conventional PFL, we propose a wait-free local training
protocol. Through extensive experiments on multiple datasets over diverse
heterogeneous data settings, we demonstrate the outperformance and efficacy of
our proposed spectral co-distillation method, as well as our wait-free
training protocol.

##  1 Introduction

With the rapid rise in mainstream popularity of artificial intelligence (AI)
models such as ChatGPT [1] and LoRA [2], there has been an increasing shift
towards the development of personalized AI assistants [3]. Hence, in a future
where personalized AI services become mainstream, training AI models on
personal data while preserving data privacy would become increasingly
important [4], and maintaining the quality for such models would require
collaborative training across multiple models. Personalized federated learning
(PFL) emerges as a promising privacy-preserving distributed learning paradigm
that is well-equipped to meet such requirements [3]. As an extension of
federated learning (FL), PFL aims to train a customized machine learning model
for each client or each group of clients with similar preferences [5]. When
faced with inconsistencies in the objective functions of different clients,
conventional FL fails to generalize well with just a single model, while in
contrast PFL promises to generalize well across all clients, even in the
presence of data heterogeneity (e.g., label distribution skew and label
quantity skew) [6, 7, 8, 9, 10, 11, 12, 13, 14].

To tackle the challenges of personalization, numerous works have focused on
designing new PFL systems, or enhancing the performance of personalized models
from different aspects, such robustness, fairness, and model convergence[15,
16, 17, 18]. Under federated settings, personalization is achieved through
capturing the (dis-)similarity of the local versus globally shared model
representations. In practical FL/PFL applications of collaboratively training
deep neural networks (DNNs), only the model parameters (e.g., model weights or
gradients) are exchanged between the clients and the server [8, 19]. Existing
DNN-based PFL methods capture this (dis-)similarity either by decoupling the
model architecture into groups of layers/channels[20, 21, 22, 23, 24, 25], or
by designing local optimization methods with regularization based directly on
model weights [17, 15]. Unfortunately, the motivations for such approaches are
based on empirical observations, without an overarching theory to explain
model (dis-)similarity in relation to training dynamics.

In deep learning theory, the training dynamics of DNNs have been studied from
the lens of Fourier analysis [26]. A crucial insight from this analysis is
that there is an implicit self-regularization effect arising from the training
process itself. Given a target function $f$ to learn, the model tends to learn
the lower frequencies of the Fourier spectrum of $f$ first before learning the
respective higher frequencies. Such a bias in this training process is called
spectral bias [27, 28]. Informally, spectral bias describes the commonly
encountered phenomenon that DNNs first learn low-level features before
learning high-level features.

Motivated by this insight, we can distinguish different levels of features in
a model representation by looking at its Fourier spectrum. Intuitively,
diverse personalized models would still share the same low-level features, and
a global generic model would contain the same low-level features. Hence,
despite any inconsistencies in the objective functions of different clients,
there would be no conflict in learning low-level features for both the generic
and personalized models. Consequently, with the expected similarity in the
lower frequency components of the Fourier spectra of both the generic and
personalized models, we can distill the knowledge of the lower Fourier
coefficients to boost the performance of the generic model. Dually, the entire
Fourier spectrum of the generic model, which includes the “averaged” high-
level features across all clients, would benefit the training of the
personalized models. By combining both perspectives, we shall propose a co-
distillation framework for PFL that captures (dis-)similarity in models via
spectral information.

Typically, when designing PFL systems, a compute-and-wait protocol is
implicitly assumed for local training [15, 23]. This means that the locally
updated generic models would be sent by the clients to the server after all
local computation tasks have been completed. Such a protocol would yield a
period of idle waiting where clients have to wait for the next aggregated
model to be broadcasted. By circumventing this compute-and-wait protocol, we
shall utilize the local idle time for training to reduce the total PFL
runtime.

Overall, our contributions can be summarized as follows:

  * •

We propose a spectral co-distillation framework for PFL. In particular, this
is the first ever use of spectral distillation in PFL to capture the
(dis-)similarity of the generic and personalized models. Also, this is the
first ever bi-directional knowledge distillation directly between the generic
and personalized models.

  * •

We propose a wait-free local training protocol for our spectral co-
distillation framework, where we utilize the idle time during global
communication so as to reduce the total PFL runtime.

  * •

Through extensive experiments on multiple datasets with heterogeneous data
settings, we demonstrate the outperformance and efficacy of our proposed
spectral co-distillation framework with the wait-free communication protocol
design for PFL, with respect to model generalizability and the total PFL
runtime.

##  2 Related work

PFL. In PFL, prior efforts have focused on training multiple personalized
models via leveraging the similarity and relationships between the global
generic model and the local personalized models, such as via model
interpolation/mixture [29], model decoupling [22], and personalized
optimization with customized regularizers [15]. In DNN-based FL applications,
decoupling-based approaches divide the model into a private part (kept at the
local side) and a shared part (exchanged between the server and clients) [3,
25, 23]. In particular, FedPer [22] and FedRep [24] share the shallow layers
and train personalized deep layers, while in contrast, LG-Fed [20] and
CD2-pFed maintain personalized shallow layers and channels [21], respectively.
Moreover, Fed-RoD proposes a framework to achieve state-of-the-art (SOTA)
performance for generic and personalized models simultaneously, based on the
“two-loss, two-predictor” design[23]. APFL [5] and L2GD [29] consider using a
mixture of local and global models to achieve personalization, in which the
mixture weight controls the personalization level. Personalized local training
methods have been recently explored, which include local fine-tuning in
FedBABU [30], bi-level optimization in Ditto [15], feature alignment in FedPAC
[31], and personalized model sparsification in FedMask [16, 32] and PerFedMask
[33]. More broadly, meta-learning [34, 35], gaussian processes [36], and
hyper-network-based approaches [37] have been investigated in PFL.
Specifically, there is another type of PFL that aims to train personalized
models at the level of clusters of clients with similar preferences [38, 39,
40].

Knowledge Distillation (KD) in FL. KD has been widely explored in knowledge
transfer scenarios, which usually is used to transfer knowledge from the pre-
trained teacher model to the student model via minimizing the distance from
the latent or logit outputs of the two models [41, 42]. KD-based FL frameworks
have been developed with diverse setups, such as FedMD [43] and FedDF [44]. On
the other hand, knowledge-transfer-based PFL frameworks are investigated in
[45, 46] with different model structures at the local clients, which could
address the system heterogeneity and improve communication efficiency.
However, such methods rely on the assumption of having access to a public
labeled/unlabelled dataset, which may not be a realistic assumption in FL
applications [3]. Moreover, co-distillation methods have been investigated in
communication-efficient decentralized scenarios to improve generalizability
[45].

Figure 1: Spectral co-distillation framework with wait-free local training for
PFL, in which the generic model (GM) training and the personalized model (PM)
training are carried out via spectral distillation in two different stages.

##  3 Proposed framework

The main goal of this work is to train a generic global model and multiple
personalized models simultaneously. As summarized in Sec. 1, our proposed
framework consists of three major components: spectral distillation-based
personalized model training, spectral co-distillation-based generic model
training, and the wait-free sequential computation-communication protocol. In
this section, we first provide the preliminary and problem formulation for PFL
and model spectrum in Sec. 3.1. Next, we present our proposed spectral
distillation approach for PFL in Sec. 3.2, co-distillation-based generic model
training in Sec. 3.3, and the wait-free local training protocol in Sec. 3.4,
accordingly. Moreover, the summarized algorithm is given in Sec. 3.5.

###  3.1 Preliminaries

Problem formulation for FL and PFL. Consider an FL system consisting of a
server and $N$ clients, in which client $i$ has a loss function
$f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ used for training on its local
private dataset $\mathcal{D}_{i}=\\{(x_{i}^{j},y_{i}^{j})\\}_{j=1}^{n_{i}}$,
where $n_{i}=|\mathcal{D}_{i}|$ denotes the size of the local dataset of
client $i$. In conventional FL, the objective of all the participating clients
in this system is to find a global model $w\in\mathbb{R}^{d}$ that solves the
following minimization problem [19]:

$\operatorname*{minimize\
}_{w\in\mathbb{R}^{d}}\left\\{F(w):=\sum_{i=1}^{N}\frac{n_{i}}{n}f_{i}(w)\right\\},$
(1)

where $n=\sum_{i=1}^{N}n_{i}$ is the total number of training samples across
the $N$ clients. In a typical communication round $t$, a subset
$\mathcal{S}_{t}$ of clients is selected to conduct local training, starting
from the latest global model weights $w_{\text{G}}^{t}$. Let $w_{i}^{t}$
denote the weights of client $i$’s model after local training. At the end of
communication round $t$, the server would collect local models from the
selected clients to update the global model via Federated Averaging (FedAvg),
i.e.
$w_{\text{G}}^{t+1}\leftarrow\sum_{i\in\mathcal{S}_{t}}p_{i}^{t}w_{i}^{t}$, in
which $p_{i}^{t}=n_{i}/\sum_{k\in\mathcal{S}_{t}}n_{k}$ represents the ratio
of the local data samples in client $i$ over the total number of data samples
in the selected subset $\mathcal{S}_{t}$ of clients for communication round
$t$.

There are two general types of PFL: a) training $N$ personalized models for
all $N$ clients; and b) training $1$ generic model and $N$ personalized models
simultaneously. In this work, we investigate the latter one, which we term as
“PFL+”. This means each client $i$ has a local personalized model
$w_{\text{p},i}$ for its private dataset $\mathcal{D}_{i}$, and all clients
jointly participate in the training of the generic model $w_{\text{G}}$. After
local training at client $i$, the updated generic model is denoted by
$w_{\text{G},i}$. Thus, PFL can be formulated using a regularized loss
function with regularization term
$R_{\text{p}}(w_{\text{p},i},w_{\text{G},i})$. For example,
$R_{\text{p}}(w_{\text{p},i},w_{\text{G},i})$ could represent the
similarity/divergence between the global and local models’ features, such as
model weights, feature centroids, and prototypes. In our method,
$R_{\text{p}}(w_{\text{p},i},w_{\text{G},i})$ represents cross-model
distillation during the training of client $i$’s personalized model.
Therefore, the objective of personalized model training in PFL+ can be
formally formulated as a bi-level optimization problem [17]:

$\displaystyle\text{({P1}):}\quad\operatorname*{minimize\
}_{w_{\text{p},i}\in\mathbb{R}^{d}}$
$\displaystyle\quad\Big{\\{}f_{\text{p},i}(w_{\text{p},i}):=f_{i}(w_{\text{p},i})+\lambda_{\text{p}}R_{\text{p}}(w_{\text{p},i},w_{\text{G},i})\Big{\\}}\text{
\quad for each client $i$}$ (2) subject to $\displaystyle\quad
w_{\text{G},i}\leftarrow\text{ updated generic model from $w_{\text{G}}$,}$
(3)

where the regularization coefficient $\lambda_{\text{p}}$ is used to control
the level of personalization. For client $i$, when referring to a specific
communication round $t$, we shall denote the untrained personalized model and
updated generic model by $w_{\text{p},i}^{t-1}$ and $w_{\text{G},i}^{t}$,
respectively.

###  3.2 Personalized local model training

Motivated by both theoretical and empirical insights of the spectral bias
inherent in the training dynamics of DNNs, we explore the use of the Fourier
spectrum of the generic model for knowledge distillation to enhance the
training of personalized local models. In particular, we propose a
distillation regularization term representing the divergence between the full
model spectra of the generic and personalized models.

First, we introduce some notation. Given vectors $p=(p_{1},\dots,p_{d})$,
$q=(q_{1},\dots,q_{d})$ in $\mathbb{R}^{d}$, define the divergence function
$\mathfrak{D}(p\|q):=\sum_{i=1}^{d}p_{i}\log p_{i}-p_{i}\log q_{i}$. (By
convention, $0\log 0:=0$.) Note that when $p$ and $q$ are stochastic vectors
representing parameter vectors of multinomial distributions $P$ and $Q$, then
$\mathfrak{D}(p\|q)$ is identically the Kullback–Leibler (KL) divergence from
$P$ to $Q$. Next, let $\texttt{DFT}:\mathbb{C}^{d}\to\mathbb{C}^{d}$ denote
discrete Fourier transform, let $\varrho:\mathbb{C}^{d}\to\mathbb{R}^{d}$ be
the map given by $(z_{1},\dots,z_{d})\mapsto(\|z_{1}\|,\dots,\|z_{d}\|)$, and
define the function $s:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ by
$s:=\varrho\circ\texttt{DFT}$. For an input vector of the weights of a DNN
model, the output vector after applying $s$ shall be called the spectrum
vector of that model [28]. Thus, in communication round $t$, the spectrum
vectors of the personalized model $w_{\text{p},i}^{t-1}$ of client $i$ and
updated generic model $w_{\text{G},i}^{t}$ are written as
$s(w_{\text{G}}^{t})$ and $s(w_{\text{p},i}^{t-1})$, respectively. We shall
represent the divergence of the personalized and generic models by
$\mathfrak{D}(s(w_{\text{p},i}^{t-1})\|s(w_{\text{G},i}^{t}))$, the divergence
of their spectrum vectors.

Concretely, we define
$R_{\text{p}}(w_{\text{p},i},w_{\text{G},i}):=\mathfrak{D}(s(w_{\text{p},i}^{t-1})\|s(w_{\text{G},i}^{t}))$,
and let $f_{i}$ be the cross-entropy loss $\mathcal{L}_{\text{CE}}$ for all
$i$. Then the personalized objective function $f_{\text{p},i}$ of client $i$
in communication round $t$ (cf. (2)) is given by:

$\mathcal{L}^{\text{p}}(w_{\text{p},i}^{t-1}|w_{\text{G},i}^{t}):=\mathcal{L}_{\text{CE}}(w_{\text{p},i}^{t-1}|\mathcal{D}_{i})+\lambda_{\text{p}}\mathfrak{D}(s(w_{\text{p},i}^{t-1})\|s(w_{\text{G},i}^{t})).$
(4)

For simplicity, we use a common time-invariant $\lambda_{\text{p}}$ for all
clients throughout training. Since we are distilling the knowledge of the
spectrum vector $s(w_{\text{G},i}^{t})$ in (4), we term our approach as
spectral distillation.

###  3.3 Generic model training

Given a PFL+ training framework, it is natural to connect the roles of generic
and personalized models to the roles of the teacher and student models in
distillation, where the training of one model is guided by the knowledge
distilled by the other. Co-distillation extends this idea. Intuitively, the
role of each model alternates between teacher and student for knowledge
distillation during training. In PFL+, since we are concurrently training both
the generic and personalized models, either of them could be used for
knowledge distillation. The key challenge for applying co-distillation to PFL+
is that it is not obvious what knowledge should be distilled from the
personalized models to enhance the training performance of the generic model.

In the theory of deep learning, it is well-known that when training a DNN,
there is a learning bias towards the lower frequencies of its Fourier spectrum
[27, 28]. In fact, the lower-frequency components of this spectrum are robust
to random weight perturbations. Hence, with diverse personalized models, we
would still expect the lower-frequency components of the spectra of all models
(both generic and personalized) to be similar. Consequently, we could use such
lower-frequency components for knowledge distillation to enhance generic model
training.

Motivated by this, we propose a truncated spectrum-based distillation loss as
the regularizer for generic model training. Given $0<\tau\leq 1$, let
$\imath_{\tau}:\mathbb{R}^{d}\to\mathbb{R}^{\lceil\tau d\rceil}$ be the
projection map onto the first $\lceil\tau d\rceil$ entries, and define
$\widehat{s}:=\imath_{\tau}\circ s$. Then the loss function for generic model
training, which depends on the truncated spectrum vectors
$\widehat{s}(w_{\text{G},i}^{t})$ and $\widehat{s}(w_{\text{p},i}^{t-1})$, is
given by:

$\mathcal{L}^{\text{G}}(w_{\text{G},i}^{t}|w_{\text{p},i}^{t-1}):=\mathcal{L}_{\text{CE}}(w_{\text{G},i}^{t}|\mathcal{D}_{i})+\lambda_{\text{g}}\mathfrak{D}(\widehat{s}(w_{\text{G},i}^{t})\|\widehat{s}(w_{\text{p},i}^{t-1})),$
(5)

where the regularization term
$R_{\text{G}}(w_{\text{G},i}^{t},w_{\text{p},i}^{t-1}):=\mathfrak{D}(\widehat{s}(w_{\text{G},i}^{t})\|\widehat{s}(w_{\text{p},i}^{t-1}))$
depends on the hyperparameter $\tau$, and $\lambda_{\text{g}}$ is the
coefficient of this regularization term. Analogous to (P1), the objective of
generic model training in PFL+ could be formulated as the following bi-level
optimization problem:

$\displaystyle\text{{(P2)}:}\quad\operatorname*{minimize\
}_{w_{\text{G}}\in\mathbb{R}^{d}}$
$\displaystyle\quad\left\\{f(w_{\text{G}}):=\sum_{i=1}^{N}\frac{n_{i}}{n}\left(f_{i}(w_{\text{G}})+\lambda_{\text{G}}R_{\text{G}}(w_{\text{G}},w_{\text{p},i})\right)\right\\}$
(6) subject to $\displaystyle\quad w_{\text{p},i}\leftarrow\text{output of
{(P1)} for client }i,\text{for }i=1,\dots,N.$ (7)

Overall, by combining the two spectral distillation approaches together, we
get a training framework for PFL+, which we shall call spectral co-
distillation.

Figure 2: A comparison of the (a) conventional compute-and-wait protocol with
the (b) proposed wait-free training protocol.

###  3.4 Wait-free Local Training Protocol

In the context of federated computing, the total runtime, which includes both
local computation and communication time throughout the entire training
process, is a direct indicator of communication efficiency. However, current
PFL frameworks adopt a compute-and-wait protocol for local training. This
means that in each round, the client performs both generic and personalized
model updates only after all local computation tasks have been completed, and
resumes local training upon receiving the latest global model broadcasted from
the server. In consequence, there is idle waiting time between model update
and model broadcast; see Fig. 2(a).

To improve the communication efficiency of PFL training with respect to the
total runtime, we propose a wait-free local training protocol, as depicted in
Fig. 2(b). In our protocol, the client updates the generic model according to
the conventional generic FL training and trains the personalized model during
the global communication time period. Unlike existing PFL frameworks, local
clients would send the updated generic model to the server before the start of
the personalized model training. Thus, our protocol eliminates idle waiting
time, thereby dramatically reducing total runtime. Furtherfore, it could be
easily incorporated into existing PFL frameworks, such as Ditto [15], to
further improve the efficiency; see Tab. 4.

Discussion on the proposed protocol and related work. Our proposed wait-free
local training protocol is specially designed for the PFL+ scenario, where
each client trains two models locally. For simplicity, we use this protocol in
our experiments, under the assumption of synchronized PFL+. For comparison in
the asynchronized PFL+ setting [47], see Appendix. Related work that reduce
the total training runtime, such as delayed gradient averaging [48] and wait-
free decentralized FL training [49], are designed for conventional FL and does
not deal with the PFL+ scenario. Furthermore, we also provide a discussion on
how our wait-free local training protocol could be adapted to the partial
client participation scheme in FL in the Appendix.

Algorithm 1 Spectral Co-Distillation with Wait-free Training for PFL+

Inputs: $N$, $T$, $\eta_{\text{p}}$, $\eta_{\text{G}}$, $w_{\text{G}}^{0}$,
{$w_{\text{p},i}^{0}$}${}_{i=0}^{N}$, $E_{\text{G}}$, $E_{\text{p}}$
Outputs: Generic model $w_{\text{G}}^{T}$, personalized models
{$w_{\text{p},i}^{T}$}${}_{i=1}^{N}$

1:for $t=1$ to $T$ do

2: for each client $k=1$ to $N$ in parallel do

3: // Generic model training and update

4: $w_{\text{G},k}^{t}\leftarrow$
GmUpdate($w_{\text{G}}^{t-1},w_{\text{p},k}^{t-1}$)

5: Upload weights $w_{\text{G},k}^{(t)}$ to server

6: // Personalized model training (Task 1: Line 5)

7: $w_{\text{p},k}^{t}\leftarrow$
PmUpdate($w_{\text{p},k}^{t-1},w_{\text{G},k}^{t}$)

8: do sequentially (Task 2: Lines 7–8) $\left.\rule{0.0pt}{30.0pt}\right\\}\
\mbox{Perform {Tasks
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}} \&
{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}} in
parallel}$

9: Uplink communication of generic model to server

10: Generic model aggregation to obtain $w_{\text{G}}^{t}$ at server

11:return $w_{\text{G}}^{T}$, {$w_{\text{p},i}^{T}$}${}_{i=1}^{N}$

1:GmUpdate($w_{\text{G}}^{t-1},w_{\text{p},k}^{t-1}$)

2:Require: $w_{\text{G}}^{t-1},w_{\text{p},k}^{t-1}$ are the latest generic
model and personalized model.

3:$w_{0}\leftarrow w_{\text{G}}^{t-1}$

4:for $j=1$ to $E_{\text{G}}$ do

5: $w_{j}\leftarrow
w_{j-1}-\eta_{\text{G}}\nabla\mathcal{L}^{\text{G}}(w_{j-1}|w_{\text{p},k}^{t-1})$
// Using truncated low frequency spectrum information

6:return $w_{j}$

1:PmUpdate($w_{\text{p},k}^{t-1},w_{\text{G},k}^{t}$)

2:Require: $w_{\text{p},k}^{t-1},w_{\text{G},k}^{t}$ are the latest
personalized model and updated generic model of client $k$.

3:$w_{0}\leftarrow w_{\text{p},k}^{t-1}$

4:for $j=1$ to $E_{\text{p}}$ do

5: $w_{j}\leftarrow
w_{j-1}-\eta_{\text{p}}\nabla\mathcal{L}^{\text{p}}(w_{j-1}|w_{\text{G},k}^{t})$
// Using full model spectrum information

6:return $w_{j}$

###  3.5 Algorithm Summary

Our proposed spectral co-distillation framework combined with our wait-free
local training protocol, is given in Algorithm 1. As an overview, we begin
every communication round $t$ with the server broadcasting the global generic
model $w_{\text{G}}^{t-1}$ to each client for local computation. Each client
$i$ would send back the updated generic model $w_{\text{G},i}^{t}$ after
$E_{\text{G}}$ local computation steps for global model aggregation, then
immediately start the personalized model training and continue until the
global generic model $w_{\text{G}}^{t}$ is received, which marks the start of
the next communication round $t+1$.

Remark on convergence analysis. Note that the global loss function includes a
weighted sum of the local loss functions and a regularizer. The regularizer is
given in the form of the divergence function $\mathfrak{D}$, which is
equivalent to KL divergence; cf. Sec. 3.2. As demonstrated in [50], the KL
divergence usually exhibits convexity in terms of the model parameters.
Consequently, since the model training undergoes (stochastic) gradient
descent, it is possible to establish a convergence rate for the training of
the global model (under the commonly employed assumption of smoothness of the
local loss functions).

Methods $\alpha=1$ $\alpha=0.5$ $\alpha=0.1$ GM PM GM PM GM PM FedAvg 85.35
$\pm$ 0.11 (80.33 $\pm$ 0.38) 80.76 $\pm$ 0.13 (74.51 $\pm$ 0.48) 73.51 $\pm$
0.17 (72.68 $\pm$ 0.39) FedProx 85.61 $\pm$ 0.08 (86.28 $\pm$ 0.21) 80.54
$\pm$ 0.14 (76.88 $\pm$ 0.30) 71.96 $\pm$ 0.12 (73.77 $\pm$ 0.30) FedDyn 86.03
$\pm$ 0.13 (85.33 $\pm$ 0.19) 80.88 $\pm$ 0.18 (78.93 $\pm$ 0.25) 73.62 $\pm$
0.14 (74.25 $\pm$ 0.58) FedGen 86.17 $\pm$ 0.32 ( 85.24 $\pm$ 0.47) 79.86
$\pm$ 0.34 (77.52 $\pm$ 0.43) 71.36 $\pm$ 0.28 (71.42 $\pm$ 0.63) FedAvgM
85.44 $\pm$ 0.05 (82.85 $\pm$ 0.28) 81.04 $\pm$ 0.09 (75.71 $\pm$ 0.33) 72.87
$\pm$ 0.06 (72.96 $\pm$ 0.14) pFedMe 85.58 $\pm$ 0.23 88.17 $\pm$ 0.17 79.33
$\pm$ 0.14 84.66 $\pm$ 0.17 72.11 $\pm$ 0.23 81.18 $\pm$ 0.15 Ditto 85.34
$\pm$ 0.10 87.55 $\pm$ 0.09 80.70 $\pm$ 0.13 83.39 $\pm$ 0.12 73.45 $\pm$ 0.18
80.08 $\pm$ 0.20 FedRep (85.61 $\pm$ 0.19) 87.32 $\pm$ 0.11 (80.33 $\pm$0.23)
84.10 $\pm$ 0.10 (73.50 $\pm$ 0.24) 79.74 $\pm$ 0.31 FedRoD 86.02 $\pm$ 0.12
91.67 $\pm$ 0.16 81.31 $\pm$ 0.15 85.91 $\pm$ 0.15 74.64 $\pm$ 0.07 81.37
$\pm$ 0.17 FedBABU (85.67 $\pm$ 0.24) 91.34 $\pm$ 0.19 (79.57 $\pm$ 0.23)
83.22 $\pm$ 0.33 (73.88 $\pm$0.19) 80.58 $\pm$ 0.22 Ours 86.37 $\pm$ 0.15
92.25 $\pm$ 0.21 81.27 $\pm$ 0.18 86.59 $\pm$ 0.17 75.52 $\pm$ 0.11 82.69
$\pm$ 0.16

Table 1: Average (3 trials) and standard deviation of the best test accuracies
for generic/personalized models of various methods on CIFAR-10 with different
non-IID settings. See also Remark 4.1.

Methods $\alpha=1$ $\alpha=0.1$ GM PM GM PM FedAvg 48.37 $\pm$ 0.22 (52.64
$\pm$ 0.48) 38.61 $\pm$ 0.27 (39.27 $\pm$ 0.42) FedProx 47.33 $\pm$ 0.15
(53.85 $\pm$ 0.33) 39.55 $\pm$ 0.18 (41.33 $\pm$ 0.38) FedDyn 49.24 $\pm$ 0.27
(57.20 $\pm$ 0.35) 40.43 $\pm$ 0.14 (40.92 $\pm$ 0.26) FedAvgM 48.55 $\pm$
0.19 (55.60 $\pm$ 0.26) 39.03 $\pm$ 0.08 (40.85 $\pm$ 0.19) pFedMe 47.29 $\pm$
0.27 61.52 $\pm$ 0.25 38.22 $\pm$ 0.23 45.88 $\pm$ 0.32 Ditto 48.37 $\pm$ 0.25
60.47 $\pm$ 0.27 39.61 $\pm$ 0.19 43.12 $\pm$ 0.28 FedRep (46.32 $\pm$ 0.23)
58.76 $\pm$ 0.36 (40.11$\pm$ 0.35) 45.22 $\pm$ 0.19 FedRoD 50.07 $\pm$ 0.16
62.51 $\pm$ 0.15 40.58 $\pm$ 0.22 45.99 $\pm$ 0.14 FedBABU (48.52 $\pm$ 0.30)
60.33 $\pm$ 0.28 (37.35 $\pm$ 0.29) 44.72 $\pm$ 0.28 Ours 51.39 $\pm$ 0.22
63.15 $\pm$ 0.16 40.67 $\pm$ 0.14 46.82 $\pm$ 0.23

Table 2: Average (3 trials) and standard deviation of the best test accuracies
for generic/personalized models of various methods on CIFAR-100 with different
non-IID settings. See also Remark 4.1.

##  4 Experiments

###  4.1 Experiment setup

Datasets, DNN models, federated settings, and evaluation metrics. We evaluated
our proposed PFL+ framework with $N$ clients on CIFAR-10/100 [51], and
iNaturalist-2017, using model architectures ResNet-18/34 [52] and ResNet-50,
respectively. For the experiments on CIFAR-10 (resp. CIFAR-100), we used
$N=100$ (resp. $N=50$). For experiments on iNaturalist-2017 [53], we used
$N=20$. For dataset partition, we used the symmetric Dirichlet distribution to
emulate real-world heterogeneous data distributions [9, 11], where the
heterogeneity is controlled by the concentration parameter $\alpha$. (A
smaller $\alpha$ indicates a higher degree of data heterogeneity.) For
evaluation, we used two performance metrics:

  * •

Generic model evaluation: global test accuracy (same metric in conventional
FL).

  * •

Personalized model evaluation: weighted average of local test accuracies.

For every client, the PM is evaluated on a local test set, whose underlying
distribution is the same as that for the local training set. All the
experiments are implemented with a full client participation scheme. Further
experiment details, results on partial client participation, and the
computation overhead discussion are provided in the Appendix.

######  Remark 4.1.

For generic FL methods, personalized model (PM) accuracies are obtained by
evaluating the generic model (GM) on local test sets. For PFL methods without
GM training, GM accuracies are obtained by evaluating the averaged PM on the
global test set.

Baselines. We compared our proposed method with the following SOTA PFL
methods: pFedMe [17], Ditto [15], FedRoD [36], FedRep [24], and FedBABU [30].
Moreover, to have a fair performance evaluation of the generic models, we also
include methods designed for conventional FL as baselines: FedAvg [19],
FedProx [10], FedDyn [11], FedGen[54], and FedAvgM [9].

Methods FedProx FedDyn Ditto FedRep FedRoD FedBABU Ours GM 39.46$\pm$0.39
39.35$\pm$0.27 39.33$\pm$0.33 39.81$\pm$0.41 40.16$\pm$0.35 39.23$\pm$0.53
41.75$\pm$0.37 PM 41.58$\pm$0.27 40.99$\pm$0.35 41.88$\pm$0.41 42.07$\pm$0.24
44.54$\pm$0.29 42.36$\pm$0.44 45.87$\pm$0.21

Table 3: Average (3 trials) and standard deviation of the best test accuracies
for generic/personalized models of various methods on iNaturalist-2017 with
non-IID setting $\alpha=0.1$. See also Remark 4.1.

###  4.2 Performance comparison with state-of-the-art methods

We evaluated the generalizability of our proposed spectral co-distillation
framework, as well as the communication cost performance of our wait-free
training protocol for PFL+.

Generalizability over heterogeneous settings. We compared the best test
accuracies with multiple baselines over the different levels of data
heterogeneity, using the same system configuration. Tab. 1 and Tab. 2 give the
main results on CIFAR-10 and CIFAR-100, respectively. In summary, our proposed
framework achieves the best test accuracies across diverse heterogeneous data
settings, outperforming all PFL and conventional FL baselines on both PM and
GM test accuracies concurrently. We also investigated the performance on the
real-world dataset iNaturalist2017 in Tab. 3, where our proposed method also
achieves the best GM/PM test accuracies.We attribute such consistent
outperformance to the bi-directional co-distillation design.

Methods | 3 epochs | 5 epochs
---|---|---
40% | 80% | 40% | 80%
Speedup
Ours (w/ WF) | 1.82 $\times$ | 1.56 $\times$ | 2.21$\times$ | 1.85$\times$
Ditto w/ WF | 1.97$\times$ | 1.38 $\times$ | 2.87$\times$ | 1.93$\times$
FedRoD w/ WF | 1.75$\times$ | 1.54 $\times$ | 2.42$\times$ | 2.19$\times$

Table 4: Communication cost comparison of various methods for personalized
model accuracies on CIFAR-10 to reach target accuracy (40%/80%) with non-IID
setting $\alpha=0.1$. The speedup factors are with respect to the performance
of the corresponding methods without WF.

This demonstrates that: a) the spectral information of the generic model is
useful for knowledge distillation during personalized model training; and b)
using truncated spectral information of the personalized models could boost
the performance of the generic model via careful spectrum truncation. (See
Appendix for a sensitivity analysis of the truncation ratio $\tau$ and other
hyper-parameters.)

Communication cost comparison. To demonstrate the superiority of the wait-free
training protocol (WF), we evaluated the communication cost performance of
SOTA methods with/without the protocol on non-IID CIFAR-10 ($\alpha=0.1$), in
terms of the total runtime $\zeta_{\text{total}}$ for PM to reach the target
test accuracy (40%/80%). A smaller $\zeta_{\text{total}}$ indicates higher
communication efficiency. For PFL methods that train generic and personalized
models using the compute-and-wait local training protocol, we evaluated Ditto
and FedRoD. We conduct experiments with different numbers of epochs for local
PM training (3 or 5 epochs). As shown in Tab. 4, our proposed wait-free
training protocol could significantly improve the efficiency of convergence
time and has the potential to boost the time efficiency of PFL+ methods.

Method $\alpha=1$ $\alpha=0.1$ GM PM GM PM Ours 86.37 $\pm$ 0.15 92.25 $\pm$
0.21 75.52 $\pm$ 0.11 82.69 $\pm$ 0.16 Ours w/o SCD-GM 85.35 $\pm$ 0.11 91.86
$\pm$ 0.17 73.51 $\pm$ 0.17 81.03 $\pm$ 0.20 Ours w/o SCD-PM 82.74 $\pm$ 0.39
79.65 $\pm$ 0.83 68.96 $\pm$ 0.47 70.51 $\pm$ 1.21 Ours w/o Both 85.35 $\pm$
0.11 79.65 $\pm$ 0.83 73.51 $\pm$ 0.17 70.51 $\pm$ 1.21

Table 5: Ablation study results on non-IID CIFAR-10 (average and standard
deviation of 3 trials). SCD-GM (resp. SCD-PM) represents the spectral
distillation approaches adopted during the training of generic (resp.
personalized) model.

###  4.3 Ablation results

Ablation study. In our proposed spectral co-distillation framework, we
introduce the bi-directional spectrum knowledge distillation to bridge the
training of generic and personalized models with the target for training good
generic and personalized models simultaneously. To achieve the target,
truncated and full model spectrum information are adopted in different
training stages. Here, we conduct an ablation study to evaluate the
effectiveness of these two components (see Tab. 5 for the effects of each
component), in which we apply the distillation approaches in the two training
stages separately. In the setup where both SCD-PM and SCD-GM are removed (Case
I), the GM training is identical to FedAvg. In the case of removing only SCD-
PM while keeping SCD-GM (Case II), each PM would be trained locally without
any knowledge distilled from the GM. This is akin to the client training its
model by itself, separately from the server. Naturally, the PM performance
would be drastically lower. As SCD-GM is kept in Case II, where the GM is the
student and the PM is the teacher, since the PM’s performance is drastically
lower, we would expect a drop in the GM’s performance. Informally, the model
would be worse off with the distillation of bad knowledge, than without
distillation.

As demonstrated in Tab. 5, both the distillation methods can boost the
accuracy performance of generic and personalized models, whereas the bi-
directional distillation can bridge the training performance of the generic
and personalized models. Specifically, we can observe that, the SCD-PM module
effectively transfers the knowledge from the generic model to the personalized
model and avoids over-fitting during local training.

Figure 3: Performance comparison for generalizability on new clients of
various methods.

Generalizability on new joining clients. In a real-world PFL system, dynamic
client participation should be regarded as an important factor to consider
during algorithm design, in which there would be continually new clients
joining the system during training. The PFL system needs to rapidly train a
good personalized model that could generalize well on the new client’s local
data. To evaluate the generalizability of the system, we simulate a dynamic
participation system with $80$ in-training clients and $20$ new clients on
CIFAR-10 (partitioned by the Dirichlet distribution with $\alpha=0.1$), and
deal with new clients with the global model-based fine-tuning approach. Fig. 3
gives the results of the average test accuracies of the new clients. Among all
evaluated methods, our method has the best average test accuracies,
illustrating the fast adaptive capability of our method.

##  5 Conclusion

In this work, we propose a spectral co-distillation framework for PFL to learn
better generic and personalized models simultaneously. As far as we know, this
is the first work in PFL that represents the (dis-)similarity of models via
their Fourier spectra. Even without co-distillation, there have been no other
works that explore spectral distillation in PFL (or even in FL). The advantage
of this new approach is clear from our experiments: We achieved outperformance
in both generic and personalized model training. Our framework also
incorporates a simple yet effective wait-free local training protocol to
reduce the overall local training time.

Limitations. Our proposed spectral co-distillation framework, as currently
formulated, does not deal with stragglers and adversarial attacks. Their
influence on performance would require further investigation. Also, our
protocol assumes a synchronized network connection, which may not be practical
for scenarios with large system/network heterogeneity. Moreover, it would be
good to consider a more realistic local training protocol design that takes
into account the issues of network/system heterogeneity; we leave the
extension as future work.

## References

  * [1] E. A. Van Dis, J. Bollen, W. Zuidema, R. van Rooij, and C. L. Bockting, “Chatgpt: five priorities for research,” Nature, vol. 614, no. 7947, pp. 224–226, 2023.
  * [2] E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen, “Lora: Low-rank adaptation of large language models,” arXiv preprint arXiv:2106.09685, 2021.
  * [3] A. Z. Tan, H. Yu, L. Cui, and Q. Yang, “Towards personalized federated learning,” IEEE Transactions on Neural Networks and Learning Systems, 2022\.
  * [4] J. P. Albrecht, “How the gdpr will change the world,” Eur. Data Prot. L. Rev., vol. 2, p. 287, 2016.
  * [5] Y. Deng, M. M. Kamani, and M. Mahdavi, “Adaptive personalized federated learning,” arXiv preprint arXiv:2003.13461, 2020.
  * [6] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, M. Al-Shedivat, G. Andrew, S. Avestimehr, K. Daly, D. Data, et al., “A field guide to federated optimization,” arXiv preprint arXiv:2107.06917, 2021.
  * [7] J. Xu, Z. Chen, T. Q. Quek, and K. F. E. Chong, “Fedcorr: Multi-stage federated learning for label noise correction,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10184–10193, 2022.
  * [8] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 10, no. 2, pp. 1–19, 2019.
  * [9] T.-M. H. Hsu, H. Qi, and M. Brown, “Measuring the effects of non-identical data distribution for federated visual classification,” in International Workshop on Federated Learning for Data Privacy in Conjunction with NeurIPS, 2019.
  * [10] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” Proceedings of Machine Learning and Systems, vol. 2, pp. 429–450, 2020.
  * [11] D. A. E. Acar, Y. Zhao, R. Matas, M. Mattina, P. Whatmough, and V. Saligrama, “Federated learning based on dynamic regularization,” in International Conference on Learning Representations, 2020.
  * [12] Z. Chen, K. F. E. Chong, and T. Q. Quek, “Dynamic attention-based communication-efficient federated learning,” in International Workshop on Federated and Transfer Learning for Data Sparsity and Confidentiality in Conjunction with IJCAI (FTL-IJCAI’2021), 2021.
  * [13] H. Tang, C. Yuan, Z. Li, and J. Tang, “Learning attention-guided pyramidal features for few-shot fine-grained recognition,” Pattern Recognit., vol. 130, p. 108792, 2022.
  * [14] Z. Chen, S. Liu, H. Wang, H. H. Yang, T. Q. Quek, and Z. Liu, “Towards federated long-tailed learning,” in International Workshop on Trustworthy Federated Learning in Conjunction with IJCAI 2022 (FL-IJCAI’22), 2022\.
  * [15] T. Li, S. Hu, A. Beirami, and V. Smith, “Ditto: Fair and robust federated learning through personalization,” in International Conference on Machine Learning, pp. 6357–6368, PMLR, 2021.
  * [16] A. Li, J. Sun, X. Zeng, M. Zhang, H. Li, and Y. Chen, “Fedmask: Joint computation and communication-efficient personalized federated learning via heterogeneous masking,” in Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems, pp. 42–55, 2021.
  * [17] C. T Dinh, N. Tran, and J. Nguyen, “Personalized federated learning with moreau envelopes,” Advances in Neural Information Processing Systems, vol. 33, pp. 21394–21405, 2020.
  * [18] D. Chen, D. Gao, W. Kuang, Y. Li, and B. Ding, “pfl-bench: A comprehensive benchmark for personalized federated learning,” Advances in Neural Information Processing Systems, vol. 35, pp. 9344–9360, 2022.
  * [19] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial intelligence and statistics, pp. 1273–1282, PMLR, 2017.
  * [20] P. P. Liang, T. Liu, L. Ziyin, N. B. Allen, R. P. Auerbach, D. Brent, R. Salakhutdinov, and L.-P. Morency, “Think locally, act globally: Federated learning with local and global representations,” in International Workshop on Federated Learning for Data Privacy in Conjunction with NeurIPS, 2019\.
  * [21] Y. Shen, Y. Zhou, and L. Yu, “Cd2-pfed: Cyclic distillation-guided channel decoupling for model personalization in federated learning,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10041–10050, 2022.
  * [22] M. G. Arivazhagan, V. Aggarwal, A. K. Singh, and S. Choudhary, “Federated learning with personalization layers,” arXiv preprint arXiv:1912.00818, 2019.
  * [23] H.-Y. Chen and W.-L. Chao, “On bridging generic and personalized federated learning for image classification,” in International Conference on Learning Representations, 2022.
  * [24] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai, “Exploiting shared representations for personalized federated learning,” in International Conference on Machine Learning, pp. 2089–2099, PMLR, 2021.
  * [25] K. Pillutla, K. Malik, A.-R. Mohamed, M. Rabbat, M. Sanjabi, and L. Xiao, “Federated learning with partial model personalization,” in International Conference on Machine Learning, pp. 17716–17758, PMLR, 2022.
  * [26] Z.-Q. J. Xu, Y. Zhang, and T. Luo, “Overview frequency principle/spectral bias in deep learning,” arXiv preprint arXiv:2201.07395, 2022.
  * [27] N. Rahaman, A. Baratin, D. Arpit, F. Draxler, M. Lin, F. Hamprecht, Y. Bengio, and A. Courville, “On the spectral bias of neural networks,” in International Conference on Machine Learning, pp. 5301–5310, PMLR, 2019.
  * [28] S. Fridovich-Keil, R. Gontijo Lopes, and R. Roelofs, “Spectral bias in practice: The role of function frequency in generalization,” Advances in Neural Information Processing Systems, vol. 35, pp. 7368–7382, 2022.
  * [29] F. Hanzely and P. Richtárik, “Federated learning of a mixture of global and local models,” arXiv preprint arXiv:2002.05516, 2020.
  * [30] J. Oh, S. Kim, and S.-Y. Yun, “FedBABU: Toward enhanced representation for federated image classification,” in International Conference on Learning Representations, 2022.
  * [31] J. Xu, X. Tong, and S.-L. Huang, “Personalized federated learning with feature alignment and classifier collaboration,” in The Eleventh International Conference on Learning Representations, 2023.
  * [32] A. Li, J. Sun, B. Wang, L. Duan, S. Li, Y. Chen, and H. Li, “Lotteryfl: Empower edge intelligence with personalized and communication-efficient federated learning,” in 2021 IEEE/ACM Symposium on Edge Computing (SEC), pp. 68–79, IEEE, 2021.
  * [33] M. Setayesh, X. Li, and V. W. Wong, “Perfedmask: Personalized federated learning with optimized masking vectors,” in The Eleventh International Conference on Learning Representations, 2023.
  * [34] Y. Jiang, J. Konečnỳ, K. Rush, and S. Kannan, “Improving federated learning personalization via model agnostic meta learning,” arXiv preprint arXiv:1909.12488, 2019.
  * [35] A. Fallah, A. Mokhtari, and A. Ozdaglar, “Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach,” Advances in Neural Information Processing Systems, vol. 33, pp. 3557–3568, 2020\.
  * [36] I. Achituve, A. Shamsian, A. Navon, G. Chechik, and E. Fetaya, “Personalized federated learning with gaussian processes,” Advances in Neural Information Processing Systems, vol. 34, pp. 8392–8406, 2021.
  * [37] A. Shamsian, A. Navon, E. Fetaya, and G. Chechik, “Personalized federated learning using hypernetworks,” in International Conference on Machine Learning, pp. 9489–9502, PMLR, 2021.
  * [38] F. Sattler, K.-R. Müller, and W. Samek, “Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints,” IEEE transactions on neural networks and learning systems, vol. 32, no. 8, pp. 3710–3722, 2020.
  * [39] M. Duan, D. Liu, X. Ji, R. Liu, L. Liang, X. Chen, and Y. Tan, “Fedgroup: Efficient federated learning via decomposed similarity-based clustering,” in 2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), pp. 228–237, IEEE, 2021.
  * [40] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran, “An efficient framework for clustered federated learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 19586–19597, 2020.
  * [41] W.-C. Chen, C.-C. Chang, and C.-R. Lee, “Knowledge distillation with feature maps for image classification,” in Computer Vision–ACCV 2018: 14th Asian Conference on Computer Vision, Perth, Australia, December 2–6, 2018, Revised Selected Papers, Part III 14, pp. 200–215, Springer, 2019.
  * [42] B. Qian, Y. Wang, H. Yin, R. Hong, and M. Wang, “Switchable online knowledge distillation,” in Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XI, pp. 449–466, Springer, 2022.
  * [43] D. Li and J. Wang, “Fedmd: Heterogenous federated learning via model distillation,” arXiv preprint arXiv:1910.03581, 2019.
  * [44] T. Lin, L. Kong, S. U. Stich, and M. Jaggi, “Ensemble distillation for robust model fusion in federated learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 2351–2363, 2020.
  * [45] Y. J. Cho, J. Wang, T. Chirvolu, and G. Joshi, “Communication-efficient and model-heterogeneous personalized federated learning via clustered knowledge transfer,” IEEE Journal of Selected Topics in Signal Processing, 2023.
  * [46] C. He, M. Annavaram, and S. Avestimehr, “Group knowledge transfer: Federated learning of large cnns at the edge,” Advances in Neural Information Processing Systems, vol. 33, pp. 14068–14080, 2020.
  * [47] J. Nguyen, K. Malik, H. Zhan, A. Yousefpour, M. Rabbat, M. Malek, and D. Huba, “Federated learning with buffered asynchronous aggregation,” in International Conference on Artificial Intelligence and Statistics, pp. 3581–3607, PMLR, 2022.
  * [48] L. Zhu, H. Lin, Y. Lu, Y. Lin, and S. Han, “Delayed gradient averaging: Tolerate the communication latency for federated learning,” Advances in Neural Information Processing Systems, vol. 34, pp. 29995–30007, 2021.
  * [49] M. Bornstein, T. Rabbani, E. Z. Wang, A. Bedi, and F. Huang, “SWIFT: Rapid decentralized federated learning via wait-free model communication,” in Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022), 2022.
  * [50] A. Akbari, M. Awais, M. Bashar, and J. Kittler, “How does loss function affect generalization performance of deep learning? application to human age estimation,” in International Conference on Machine Learning, pp. 141–151, PMLR, 2021.
  * [51] A. Krizhevsky, G. Hinton, et al., “Learning multiple layers of features from tiny images,” 2009.
  * [52] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [53] G. Van Horn, O. Mac Aodha, Y. Song, Y. Cui, C. Sun, A. Shepard, H. Adam, P. Perona, and S. Belongie, “The inaturalist species classification and detection dataset,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8769–8778, 2018.
  * [54] Z. Zhu, J. Hong, and J. Zhou, “Data-free knowledge distillation for heterogeneous federated learning,” in International conference on machine learning, pp. 12878–12889, PMLR, 2021.


11institutetext: Université Paris-Saclay, CEA-List, F-91120, Palaiseau, France
11email: {valentin.gilbert<EMAIL_ADDRESS>
# Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All

Valentin Gilbert  0009-0001-1004-0204 Stéphane Louise  0000-0003-4604-6453

###### Abstract

Quantum annealers (QA), such as D-Wave systems, become increasingly efficient
and competitive at solving combinatorial optimization problems. However,
solving problems that do not directly map the chip topology remains
challenging for this type of quantum computer. The creation of logical qubits
as sets of interconnected physical qubits overcomes limitations imposed by the
sparsity of the chip at the expense of increasing the problem size and adding
new parameters to optimize. This paper explores the advantages and drawbacks
provided by the structure of the logical qubits and the impact of the
rescaling of coupler strength on the minimum spectral gap of Ising models. We
show that densely connected logical qubits require a lower chain strength to
maintain the ferromagnetic coupling. We also analyze the optimal chain
strength variations considering different minor embeddings of the same
instance. This experimental study suggests that the chain strength can be
optimized for each instance. We design a heuristic that optimizes the chain
strength using a very low number of shots during the pre-processing step. This
heuristic outperforms the default method used to initialize the chain strength
on D-Wave systems, increasing the quality of the best solution by up to
$17.2\%$ for tested instances on the max-cut problem.

###### Keywords:

quantum annealing Ising chain strength minor embedding

##  1 Introduction

The idea of using Quantum Annealers to solve combinatorial problems is not new
and was exposed by E. Farhi et al. [9]. Despite strong theoretical proofs
based on the quantum adiabatic theorem, the speed-up brought up by quantum
annealers still needs to be quantified for real useful application. It comes
from the fact that quantum annealers implement a noisy version of the more
general Adiabatic Quantum Computation (AQC) (the reader may refer to T. Albash
et al. [2] for an introduction to AQC). Indeed, D-Wave systems suffer from
more than five different sources of Integrated Control Errors (ICE) [1]. The
maximal number of qubits available on the quantum chip limits the size of the
problem that can be solved. Minor embedding algorithms transform the initial
problem into a new one that fits the sparsely connected quantum chip. The
transformation consists of mapping the initial problem’s logical variables to
a set of physical variables that can be straightly encoded on the physical
qubits of the quantum annealer. As mentioned in V. Gilbert et al. [10],
assessing the quality of an embedding is not trivial. The number of physical
qubits used in the embedding can serve as a first quality indicator, but the
physical qubit’s topology used to encode the logical qubits can also be
considered. To the authors’ knowledge, a single contribution on this issue was
made by E. Pelofske [13]. Topologies used for physical qubits are usually
chains of qubits because this structure maximizes the number of potential
connections of the logical qubit. E. Pelofske shows that the performance of
the quantum solver is increased when logical qubits are encoded on cliques
instead of chains. The minor embedding of a logical variable into a set of
physical qubits requires the setting of an accurate ferromagnetic coupling.
Current state-of-the-art methods often scan a static range of values to find
the appropriate ferromagnetic coupler strength.

In this context, we explore the advantages and drawbacks of different logical
qubit encodings. This first analysis shows that the minimum spectral gap
varies depending on the qubit encoding, as well as the minimum chain strength
required to maintain ferromagnetic couplings. We perform a detailed analysis
of the average performance of the two main existing minor embedding methods.
This analysis helps to select sets of instances on which we analyze the chain
break tendency w.r.t the chain strength value. In particular, we discover that
the optimal value of the chain strength varies depending on the embedding
choice, which suggests that a per-instance chain strength setting method is
desirable. The final contribution of this article is the design of a simple
algorithm used to find appropriate values for the chain strength using very
few pre-processing calls to the quantum computer. This new algorithm
outperforms the default method implemented by D-Wave.

The rest of the paper is organized as follows: Section 2 introduces background
about quantum annealing and minor-embedding methods. Section 3 surveys the
related work used in the study. Section 4 describes the method and technical
settings for the experiments. Section 5 analyzes and proves the minimum
spectral gap reduction induced by coupler strength rescaling. The Section 6
gathers experiments on embedding and chain breaks that are used to build the
algorithm presented in Section 7.

##  2 Quantum Annealing and Minor Embedding Methods

D-Wave systems evolution is based on the transverse field Ising model. This
model can be described with a linear interpolation of two Hamiltonians: a
mixing Hamiltonian $H_{\mathrm{M}}$, which ground state (i.e., state of lower
energy which can be degenerate) is easy to prepare, and a problem Hamiltonian
$H_{\mathrm{P}}$, which ground state encodes the solution to the problem. The
evolution of the system at annealing fraction $s=\frac{t}{T}$ is described by
the Hamiltonian:

$H(s)=(1-s)H_{\mathrm{M}}+sH_{\mathrm{P}}$ (1)

where $T$ denotes the total run time of the quantum evolution and $t\in[0,T]$.
The transverse field Hamiltonian
$H_{\mathrm{M}}=\sum_{i=0}^{n-1}\sigma_{i}^{x}$ has its ground state defined
by a uniform superposition of all the quantum states of the computational
basis. The problem Hamiltonian can be fully specified by the user on a graph
$G_{\mathrm{s}}=(V_{\mathrm{s}},E_{\mathrm{s}})$:

$H_{\mathrm{P}}=\sum_{v\in V_{\mathrm{s}}}h_{v}\sigma_{v}^{z}+\sum_{(u,v)\in
E_{\mathrm{s}}}J_{uv}\sigma_{u}^{z}\sigma_{v}^{z}$ (2)

The ground state of the Hamiltonian $H_{\mathrm{P}}$ gives the solution to the
Ising cost function minimization problem :

$\min C(\textbf{x})=\sum_{v\in V_{\mathrm{s}}}h_{v}x_{v}+\sum_{(u,v)\in
E_{\mathrm{s}}}J_{uv}x_{u}x_{v}$ (3)

where $x_{u},x_{v}\in\\{-1,+1\\}$ and $h_{v},J_{uv}\in\mathbb{R}$. The optimal
solution is given by $\textbf{x*}=(x_{0},x_{1},...,x_{n-1})$. The Hamiltonian
$H(s)$, at a fixed annealing fraction $s$, corresponds to a Hermitian matrix
$H_{s}$, and can be decomposed in terms of its eigenvalues $E_{i}(s)$ and
eigenvectors $\ket{v_{i}(s)}$:

$H_{s}\ket{v_{i}(s)}=E_{i}(s)\ket{v_{i}(s)}\textrm{ with
}E_{0}(s)<E_{1}(s)<...<E_{k}(s)$ (4)

This decomposition is also called eigenenergies decomposition as the
eigenvalues $E_{i}(s)$ correspond to the energy of each eigenvector
$\ket{v_{i}(s)}$. The spectral gap of the Hamiltonian $\Delta_{\mathrm{min}}$
is the difference between the energy of the first excited state and the energy
of the ground state at any annealing fraction $s$:

$\Delta_{\mathrm{min}}=\min_{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))$ (5)

The adiabatic theorem guarantees that a quantum state remains in its
instantaneous ground state if $T$ is chosen large enough to smooth the quantum
evolution. In the best case, the time $T$ scales as
$O(1/\Delta_{\mathrm{min}}^{2})$ [2].

When the Ising cost function of interest cannot be straigthly mapped on the
chip topology, one has to use a method to minor embed the problem into the
quantum chip. This problem is well defined by the theory of graph minors
developed by Robertson and Seymour [16]. The problem is defined as follows:

Given a source graph $G_{\mathrm{s}}=(V_{\mathrm{s}},E_{\mathrm{s}})$, a
target graph $G_{\mathrm{t}}=(V_{\mathrm{t}},E_{\mathrm{t}})$, the aim is to
find a mapping function
$\phi:V_{\mathrm{s}}\xrightarrow{}\mathcal{P}(V_{\mathrm{t}})$ such that :

  1. 1.

each vertex $v\in V_{\mathrm{s}}$ is mapped onto a connected subgraph
$\phi(v)$ of $G_{\mathrm{t}}$.

  2. 2.

each connected subgraph must be vertex disjoint
$\phi(v)\cap\phi(v^{\prime})=\emptyset$, with $v\neq v^{\prime}$.

  3. 3.

each edge $(u,v)\in E_{\mathrm{s}}$ is mapped onto at least one edge in
$E_{\mathrm{t}}$ : $\forall(u,v)\in E_{\mathrm{s}},\exists
u^{\prime}\in\phi(u),\exists
v^{\prime}\in\phi(v),~{}such~{}that~{}(u^{\prime},v^{\prime})\in
E_{\mathrm{t}}$.

For each vertex $v\in V_{\mathrm{s}}$, a ferromagnetic coupling strength
$F_{\phi(v)}$ (also called chain strength) is applied to each edge of the
subgraph $\phi(v)$. When this ferromagnetic coupling strength is the same for
all ferromagnetic couplers, we note it $F_{\phi}$. In the rest of the paper,
we refer to $V_{s}$ as the set of logical qubits and $V_{t}$ as the set of
physical qubits. A chain break on a logical qubit $v$ means that at least one
ferromagnetic coupling in $\phi(v)$ is corrupted. An edge of the subgraph
$\phi(v)$ is a ferromagnetic coupling.

##  3 Related Work

Two categories of methods are used to find a minor embedding of an Ising
problem. The first category comprises a set of heuristics for which the source
graph $G_{s}$ and target graph $G_{t}$ are given as input. The state-of-the-
art implementation for this category is the CMR heuristic of Cai et al. [4].
The first step of this algorithm aims to find an initial embedding of each
logical qubit with possible overlaps between their associated connected
subgraph of physical qubits. The second step is a refinement that tries to
reduce this overlap to return a valid embedding. The second category of
methods considers that the source graph $G_{s}$ is a clique (i.e., a complete
graph) and that the target graph $G_{t}$ is static. The state-of-the-art
method used to generate Clique Minor Embeddings (CME) on D-Wave systems is an
iterative method designed by Boothby et al. [3], which leverages the regular
topology of the quantum annealer and considers inoperable qubits. Both CMR and
CME methods have been extended with some pre or post-processing treatments to
boost their performance (one example is Spring-based MinorMiner and Clique-
Based MinorMiner [20]).

Prior theoretical work by V. Choi [5] formulates two upper bounds on the
minimum value of the ferromagnetic coupling strength $F_{\phi(v)}$. The first
bound is straighty derived and corresponds to:

$F_{\phi(v)}<-\left(|h_{v}|+\sum_{u\in\mathrm{nbr}(v)}|J_{uv}|\right)$ (6)

where $\mathrm{nbr}(v)$ gives the set of nodes connected to $v$. This bound is
fast to compute with $O(D)$ complexity, where $D$ is the vertex degree. V.
Choi also details a more elaborated bound calculated in $O(DL)$ where $L$ is
the chain length. In the paper of Fang et al. [8], the authors derive a new
tighter bound that can be computed in $O(D2^{L})$. The main idea is to set the
chain strength with a negative strength with its absolute value greater than
the maximum potential energy gain of any configuration of the physical qubits
that are not part of the ground state. Thus, this method scales exponentially
w.r.t the size of the chain length. The authors of [18] provided a second
approach. They study the value of the optimal coupling strength by setting a
global chain strength $F_{\phi}$. They observe that the optimal coupling value
$F_{\phi}$ grows as the critical point of temperature of their embedded
Sherrington Kirkpatrick model. Beyond this critical value, the success
probability decreases. In the paper of Raymond et al. [15], the authors
suggest that the chain strength should be tuned as:

$\lambda=\lambda_{0}\sqrt{\sigma^{2}N}=\lambda_{0}\tau\sqrt{N}$ (7)

where $\sigma^{2}=\frac{2}{N(N-1)}\sum_{(u,v)\in E_{s}}J_{uv}^{2}$ is the
variance of the coupling strength (which is 1 for clique spin glasses). Their
motivation is that a spin glass transition exists at optimal $\lambda_{0}$.
However, $\lambda_{0}$ remains to be set empirically. This paper led to the
default method uniform_torque_compensation implemented on D-Wave systems [1],
which sets the value of the chain strength:

$F_{\phi}=-1.414\times\sqrt{\bar{d}}\times\sqrt{\frac{1}{|E_{s}|}\sum_{(u,v)\in
E_{s}}J^{2}_{uv}}$ (8)

where $\bar{d}$ is the average degree of the graph $G_{s}$. This formula comes
from the fact that, for general Ising problem, the chain strength scales as
$\tau\sqrt{N}$ where $\tau$ is the root mean square of the quadratic couplers.
In practice, the value of the chain strength is mostly set with a basic chain
scan method used to maximize the average expectation value of the QA. For
detailed experimental studies on chain strength scanning, the reader may refer
to [12, 19]. The chain scan method performs well but is very expensive in
terms of the number of calls to the QA. The optimization of the chain strength
is usually done based on the expectation value. A single advanced optimization
method of the chain strength has been developed for the max-clique problem by
H. Djidjev recently and is based on augmented lagrangian method [7]. Recent
studies have benchmarked the chain break properties. In E. Grant et al. [11],
the authors find that the chain break concentrates on specific locations of
the D-Wave 2000Q processor and design post-processing strategies to limit
these bias. In another recent paper of Pelofske [14], it is seen that the
approximation ratio is inversely correlated with the rate of getting chain
breaks. The author shows that the optimal chain strength is also conditioned
by the density of the problem and the type of quantum solver used. We reuse
these conclusions as well as the first theoretical bound given in equation 6
to create an efficient method to set the chain strength.

##  4 Method

This article solves two types of problems: the weighted Ising problem and the
max-cut problem. Section 5 is based on a non-degenerate instance of the
weighted Ising problem. This problem consists in minimizing the Ising cost
function formulated in equation 3. The minimum spectral gap of the problem
$\Delta_{\mathrm{min}}$ is calculated using the exact diagonalization of the
Hermitian matrix $H_{s}$ at each step of the annealing schedule $s\in[0,1]$.
The schedule used is the one corresponding to D-Wave Advantage6.4. The
detailed description of this schedule can be downloaded at [1].

The max-cut problem is used in Sections 6 and 7. The weights $J_{uv}$ are set
to 1 for all edges, $h_{v}$ weights are set to 0. All the experiments are run
at a constant annealing time of $100\mu s$. We use uniform logical weight
spreading, majority vote to unembed the problem and the auto-scale method for
weight rescaling. We do not use spin reversal methods or annealing offsets.
The figures always show the chain strength in absolute value. The heatmaps
from Fig 2 are generated from sets of 100 instances for each size and density.
Erdős-Rényi graphs and random d-regular graphs are generated using the Python
networkx library. The CMR heuristic (implemented in [17]) runs until a valid
embedding is found. The CME heuristic is the default method provided by D-Wave
[1]. For all the experiments, we select the first valid embedding found. The
plots from Fig 3 are averaged over 30 instances of random Erdős-Rényi graphs
of size $n=80$ and density $p=0.3$. The solver used is the Advantage6.4 and
the number of shots is set to $1024$ for each chain strength. The plots from
Fig 4 are obtained from a single Erdős-Rényi instance of size $n=60$ and
density $p=0.4$. The solver used is the Advantage2_prototype2.2 and the number
of shots is set to $4096$ for each chain strength and for the runs with
uniform_torque_compensation method. The results obtained in Table 1 are
obtained with solvers Advantage6.4 and Advantage2_prototype2.2. The results
are averaged over 30 instances of Erdős-Rényi graphs for each specified size
and density. The number of shots in the preprocessing method is set to $128$.
The final run used to retrieve the statistics is set to $4096$. The run with
uniform_torque_compensation method is also set to $4096$.

The metric used to compare the performance of heuristics that generate minor
embeddings in Fig 2 is defined as the average ratio of the number of qubits
used by the CMR method and by the CME method:

$r_{emb}=\frac{1}{N_{\mathrm{p}}}\sum_{i}^{N_{\mathrm{p}}}\frac{n_{i}^{\mathrm{CMR}}}{n_{i}^{\mathrm{CME}}}$
(9)

where $N_{\mathrm{p}}$ is the number of instances, $n_{i}^{\mathrm{CMR}}$ and
$n_{i}^{\mathrm{CME}}$ is the number of physical qubits found by the embedding
method CMR resp. CME on instance $i$. The average breaking chain rate
$\epsilon_{b}$ of a single shot is defined by:

$\epsilon_{b}=\frac{1}{n_{lq}}\sum_{i=1}^{n_{lq}}p_{b}(i)$ (10)

with $n_{lq}$ the number of logical qubits. $p_{b}(i)$ is set to $1$ if the
logical qubit contains at least one broken chain and $0$ otherwise. The
average breaking chain rate of a serie of shots is given by:

$\bar{\epsilon_{b}}=\frac{1}{n_{s}}\sum_{i=1}^{n_{s}}\epsilon_{b}^{(i)}$ (11)

where $n_{s}$ defines the number of shots used in the experiment.

##  5 Logical Qubit Structure

Figure 1: Minimum spectral gap evaluations considering different types of
logical qubits encoding a) Native Ising problem instance b) Same instance as
in a. with the red qubit encoded as a chain of physical qubits c) Same
instance as in a. with the red qubit encoded as a cycle of physical qubits d)
Same instance as in a. with the red qubit encoded with a clique of physical
qubits. Black edges represent logical couplers and red edges represent
ferromagnetic couplers parametrized by the chain strength. The auto-coupler
strength $h_{6}$ is uniformly spread on each physical qubit. e) Evolution of
$\Delta_{\mathrm{min}}$ considering the whole annealing schedule for different
values of the global chain strength $|F_{\phi}|$. f) Spectral gap evolution of
each encoding type programmed with the corresponding optimal chain strength
indicated by dashed lines in e.

We study the evolution of the minimum spectral gap $\Delta_{\mathrm{min}}$ of
a single max-cut instance by exhaustively simulating the quantum system
evolution via matrix diagonalization. For this purpose, we design a single
instance of an Ising problem with 6 nodes (see Fig. 1.a). We choose three
possible encodings for the physical qubits that replace the red logical qubit
in 1.a. The selected structures are: chain, cycle and clique. Each structure
is respectively shown in Fig. 1.b, 1.c and 1.d. Figure 1.e shows the evolution
of the minimum spectral gap of each encoding according to the chain strength
value used to maintain the ferromagnetic coupling. For each encoding, the
chain strength starts at the minimum analytical value, which is sufficient to
maintain the ferromagnetic coupling of the logical qubit (0.3 for the clique,
0.45 for the cycle and 0.9 for the chain). Each embedding exhibits some sweet
spots that maximize the minimum spectral gap. The size of the minimum spectral
gap decreases when the chain becomes stronger. The optimal value of the chain
strength decreases with the density of the logical qubit encoding. This is a
desirable feature as D-Wave quantum processors have a limited working range
for auto-coupler (h_range) and coupler (extended_j_range) strengths. In
addition, the maximum coupling range limit imposes that the total strength of
the couplers linked to each qubit remains in a specific range. These two
physical limitations lead to a global rescaling of coupler strengths when the
values exceed these ranges.

Reusing the work of V. Choi [6], it is straightforward to demonstrate that
rescaling the coupler strength in the problem Hamiltonian also rescales with
the same factor the minimum spectral gap of the Ising model Hamiltonian. Let
the $\alpha$-rescaled Hamiltonian with $s_{2}\in[0,1]$ and $\alpha>1$:

$H^{1/\alpha}(s_{2})=(1-s_{2})H_{\mathrm{M}}+s_{2}\frac{1}{\alpha}H_{\mathrm{P}}$
(12)

We take equation 1 as the initial Hamiltonian $H$ with annealing fraction
$s_{1}\in[0,1]$. Consider the system:

$\begin{cases}\frac{H(s_{1})}{1-s_{1}}=H_{\mathrm{M}}+\frac{s_{1}}{1-s_{1}}H_{\mathrm{P}}\\\
\frac{H^{1/\alpha}(s_{2})}{1-s_{2}}=H_{\mathrm{M}}+\frac{s_{2}}{\alpha(1-s_{2})}H_{\mathrm{P}}\end{cases}$
(13)

The equality $\frac{s_{1}}{1-s_{1}}=\frac{s_{2}}{\alpha(1-s_{2})}$ can be
solved with $s_{1}=\frac{s_{2}}{(\alpha-1)(1-s_{2})+1}$ and
$s_{2}=\frac{s_{1}}{\frac{1}{\alpha}(1-s_{1})+s_{1}}$. Using this
correspondance, we have:

$\frac{H^{1/\alpha}(s_{2})}{1-s_{2}}=\frac{H(s_{1})}{1-s_{1}}$ (14)

The rescaled Hamiltonian has the form:

$H^{1/\alpha}(s_{2})=\frac{1-s_{2}}{1-s_{1}}H(s_{1})=\left(1+\left(\frac{1}{\alpha}-1\right)s_{2}\right)H(s_{1})$
(15)

The eigenenergies of the Hamiltonian are then rescaled with the same factor.
According to equation 4, we have:

$E^{1/\alpha}_{i}(s_{2})=\left(1+\left(\frac{1}{\alpha}-1\right)s_{2}\right)E_{i}(s_{1})$
(16)

Fig 1.f. shows the effect of couplers strength rescaling on the spectral gap.
This figure shows that rescaling the global coupling strength reduces the
minimum spectral gap by the same factor. It also shifts the spectral gap to
the right. Encoding logical qubits on a set of physical qubits has a
detrimental effect on the spectral gap of the problem. The difference in
spectral gap reduction between these encodings seems negligible compared to
the rescaling of the weights. Logical qubit encodings that are dense, such as
clique, require a lower coupling strength to maintain ferromagnetic coupling
within the physical qubits. This type of encoding could be favored compared to
chain encoding in specific cases to limit the effect of coupler strength
rescaling.

##  6 Embeddings and Chain Break Analysis

Figure 2: Heatmaps showing the average percentage overhead of the number of
qubits used to embed similar instances using the CMR method compared to CME
method. Each score is an average done over 100 instances. The score
calculation in each cell is detailed in equation 9. a) and b) are embeddings
generated for Advantage6.4 topology for Erdős-Rényi and d-regular graphs. b)
and c) are embeddings generated for Advantage2_prototype2.2 topology using the
same instances. Advantage6.4 and Advantage2_prototype2.2 can embed complete
graphs of maximum size 82 and 174. Figure 3: Statistics on the breaking chain
rate (see equation 11) averaged over 30 instances of Erdős-Rényi graphs of
size $n=80$ and density $p=0.3$. a) resp. b) show the average chain length
repartition of embedding obtained with CMR resp. CME methods. Blue bars show
the average frequency of each chain length. Orange bars show the average
breaking chain rate with a black error bar for the standard deviation. c)
shows the average and median frequency of corrupted ferromagnetic couplings on
CMR embeddings. d) shows the number of different ferromagnetic coupling that
are corrupted at least once during the 1024 shots on CMR embeddings.

Figure 2 compares the embedding performance in terms of the number of qubits
used by the CMR method [4] against the CME method [3]. The comparison is done
on Erdős–Rényi and d-regular graphs. It shows that CMR performs better on
sparse graphs of small size, while CME is almost always preferred for large
graphs. We use this heatmap to select sets of instances for which CMR and the
CME methods produce embeddings with approximately the same number of physical
qubits. Hence, we choose to generate 30 random instances of the max-cut
problem with size $n=80$ and density $p=0.3$. The aim is to analyze the impact
of the embedding method on the chain strength and length. CMR and CME produce
embeddings with a similar number of physical qubits for these instances. To be
fair in the comparison, we force the CMR method to generate minor embeddings
with $\pm 1\%$ qubits compared to the embeddings generated by CME. Figure 3.a
and b. respectively show the repartition of the chain length for CMR resp. CME
embeddings. While the CME method produces almost uniform chains of length 8
and 9, the CMR method produces chain lengths that approach a Gaussian
distribution and vary from 4 to 15. The coupling strength required by the CME
embeddings to obtain the same breaking chain rate is higher than for CMR
embeddings. For the CMR method, the optimal solution probability occurs at
chain strength 8, while this value is raised to 12 for CME embeddings. Figure
3.d shows that the number of different corrupted couplings only slightly
changes when the chain strength is increased. Fig 3.c shows that when the
chain strength is insufficient to maintain ferromagnetic couplings, the
average number of corrupted ferromagnetic couplings is very high compared to
the median. It suggests that the corruptions concentrate on the same few
ferromagnetic couplings. When the chain strength value is increased, the
average number of corruptions decreases. However, the number of different
corrupted couplings remains the same, suggesting that the corruption becomes
sparse when the chain strength is sufficient. We computed statistics on the
number of corrupted ferromagnetic couplings per logical qubits. At the optimal
chain strength value, the most likely scenario is to have only a single
corruption of couplings on the logical qubit ($99.9\%$ cases) and very few
chances of double corruption of couplings ($0.01\%$ cases).

Figure 4: Maximum cut size obtained with a chain scan on four different
embeddings of the same instance. The uniform_torque_compensation is run once
for each embedding (hence, it is independent of the chain scan). The CME and
upper right CMR embedding have the same number of physical qubits ($\pm 1\%$).
The two other embeddings have $10\%$ more and $10\%$ less qubits than the CME
embedding. The red violins show the average breaking chain rate
$\bar{\epsilon_{b}}$ related to the chain scan curve.

The above experiment suggests that the optimal chain strength value is related
to the embedding. We select another instance that produces approximately the
same number of qubits for both embedding methods for the
Advantage2_prototype2.2. We generate four different embeddings for a single
instance of the max-cut problem of 60 nodes and 0.4 density. The first
embedding is generated by the CME method. We generate three other embeddings
using the CMR method: one with a similar number of qubits as in the CME
embedding ($\pm 1\%$), one which has $10\%$ less qubits than the CME
embedding, one which has $10\%$ more qubits than the CME embedding. Figure 4
shows the best cut size found with each embedding. At first, we can see that
the uniform_torque_compensation method performs well in all the cases compared
to the chain scan that requires heavy pre-processing ($93\%$ of the best cut
size in the worst case with CME embedding). For each instance, the best cut
size reaches a plateau when the chain strength becomes sufficient. This
plateau is reached at different chain strength values for each instance.
However, this plateau can also be located by only considering the average
breaking chain rate from equation 11 (for example, considering that the chain
break probability should remain under $2\times 10^{-2}$). As specified in
[13], the chain break probability susceptible to provide the best result
depends also on the quantum computer.

##  7 Chain Strength Setting Heuristic

The previous section detailed our motivations for designing a heuristic to set
the chain strength for each instance. Algorithm 1 describes this method in
pseudo-code. The algorithm performs a binary search to find the optimal chain
strength value within an initial interval of chain strengths set by the user
$csInterval$. When the user does not specify it, the default interval’s upper
bound is set according to Choi’s first bound (line 3):

$F_{\phi}=\min_{v\in G_{t}}{F_{\phi(v)}}$ (17)

Algorithm 1 Chain strength binary search

1:$embInstance$, $cbInterval$, $csInterval$ (nullable)

2:$cbInterval[0]<cbInterval[1]$

3:$hasConverged\leftarrow False$

4:if $csInterval$ is None then

5: $csInterval\leftarrow[0,getUpperBound(embInstance)]$ $\triangleright$ (see
equation 17)

6:end if

7:while not $hasConverged$ do

8: $cs\leftarrow csInterval[0]+(csInterval[0]-csInterval[1])/2$

9: $res\leftarrow runQA(embInstance,cs)$

10: $\bar{\epsilon_{b}}\leftarrow getChainBreakRate(res)$ $\triangleright$
(see equation 11)

11: if $cbInterval[0]\leq\bar{\epsilon_{b}}\leq cbInterval[1]$ then

12: $hasConverged\leftarrow True$

13: else if $\bar{\epsilon_{b}}>cbInterval[1]$ then

14: $csInterval[0]\leftarrow cs$

15: else

16: $csInterval[1]\leftarrow cs$

17: end if

18:end while

Table 1: Performance comparison between D-Wave’s default method (uniform_torque_compensation) and our binary search heuristic. The column Best cut size shows the average of the maximum cut size obtained for each instance with the uniform_torque_compensation method. The column Cut size improvement contains the minimum and maximum cut size improvement obtained with the chain strength found by Algorithm 1. The standard deviation is shown is column std. The column Step counts the number of iterations required by our heuristic. Advantage2_prototype2.2 | Best cut size | Cut size improvement | Step
---|---|---|---
Instance size | Density | Embedding |  | min | max | mean | std |
$n=40$ | 0.1 | CMR | 66.4 | $+0\%$ | $+0\%$ | $+0\%$ | $0\%$ | 5.4
0.5 | CMR | 243 | $+0\%$ | $+2\%$ | $+0.2\%$ | $0\%$ | 5.8
0.9 | CMR | 362.8 | $+2.1\%$ | $+8.2\%$ | $+5\%$ | $1.6\%$ | 4.6
$n=80$ | 0.1 | CMR | 235.5 | $+0\%$ | $+0\%$ | $+0\%$ | $0\%$ | 4.7
0.5 | CME | 804 | $+9.8\%$ | $+17.2\%$ | $+12.5\%$ | $0.2\%$ | 4.2
0.9 | CME | 1435 | $+2\%$ | $+4.7\%$ | $+3.2\%$ | $0.6\%$ | 4.2
Advantage6.4 | Best Cut size | Cut size improvement | Step
Instance size | Density | Embedding |  | min | max | mean | std |
$n=100$ | 0.1 | CMR | 355.9 | $+0\%$ | $+0.3\%$ | $+0\%$ | $0\%$ | 4.5
0.5 | CME | 1271.4 | $+5.6\%$ | $+14.5\%$ | $+8.8\%$ | $1.8\%$ | 2.7
0.9 | CME | 2243 | $+1.4\%$ | $+3.7\%$ | $+2.5\%$ | $0.5\%$ | 3.7
$n=170$ | 0.1 | CMR | 950.8 | $-2.1\%$ | $+0.6\%$ | $-0.5\%$ | $0.5\%$ | 2.1
0.5 | CME | 3631.4 | $+2.8\%$ | $+6.2\%$ | $+4.5\%$ | $0.7\%$ | 2.1
0.9 | CME | 6519.4 | $+0.4\%$ | $+1.4\%$ | $+0.8\%$ | $0.2\%$ | 3.2

At each iteration, the chain strength $cs$ is chosen as the midpoint of the
chain strength interval $csInterval$ (line 6). The embedded instance
$embInstance$ is then sent to the quantum annealer with the specified chain
strength $cs$ (line 7). We then compute the breaking chain rate of the result
according to equation 11 and check if the new breaking chain rate is in the
interval specified by the user $cbInterval$. If this is the case, the
algorithm converges (lines 9 and 10), and the loop breaks. If the chain break
is higher than the upper bound of $cbInterval$, the chain strength is
insufficient and requires an increase: we then rescale the lower bound of
$csInterval$ (lines 11 and 12). In the other case, the upper bound of the
chain strength interval is rescaled (line 14). The subtlety of this algorithm
relies in the setting of the chain break interval $cbInterval$ which stops the
algorithm when the sampling produces a breaking chain rate in this interval.
This interval depends on the effective noise of the quantum computer and may
also depend on the size of the instance. We test our heuristic and compare the
results obtained with the default method implemented by D-Wave that relies on
equation 8. The comparison is done both on Advantage2_prototype2.2 on small
Erdős-Rényi instances ($n=40$ and $n=80$) and Advantage6.4 for large instances
($n=100$ and $n=170$) with density $p\in\\{0.1,0.5,0.9\\}$. For each instance
set, we choose the embedding heuristic that provides the best average
performance based on the size and density of the instance (see Fig 2). We
empirically set the interval $cbInterval$ to $[6\times 10^{-3},2\times
10^{-2}]$ for the Advantage2_prototype2.2 and to $[2\times 10^{-2},5\times
10^{-2}]$ for the Advantage6.4. This range stays untouched during the whole
experiment. Each round of pre-processing step is done with 128 shots. The
final run of our heuristic, as well as the default D-Wave method, is
programmed with 4096 shots for instances run on Advantage2_prototype2.2 and
3072 shots for instances run on Advantage6.4. Table 1 shows the result of this
experiment. With a global setting of the value for $cbInterval$, our heuristic
is able to outperform in almost every case the default
uniform_torque_compensation method. The breaking chain rate can be obtained
with relatively high fidelity in a few shots. It gives a considerable
advantage to our method compared to the basic chain strength scans that always
use the expectation value to find optimal values of the chain strength and,
hence, require a very high number of shots. Our optimization method does, on
average, between 2 and 6 iterations to find a suitable value for the chain
strength (i.e., $\approx 750$ extra runs in worst cases). This running
overhead is almost negligible compared to the 4096 and 3072 shots used to
evaluate the final chain strength and the uniform_torque_compensation method.
The default uniform_torque_compensation performs well on embeddings generated
by CME for dense and sparse graphs that use CMR heuristic. Our heuristic seems
to perform the best with mid-density instances by increasing cut size up to
$17.2\%$ for the Advantage2_prototype2.2 and $14.5\%$ for the Advantage6.4.

##  8 Conclusion

This paper presents a detailed analysis of the minimum spectral gap evolution
considering different topologies for the set of physical qubits representing a
single logical qubit. Each encoding requires a specific chain strength value
to maintain ferromagnetic couplings between the physical qubits. The denser
the logical qubit encoding is, the lower the chain strength has to be. This
feature is desirable as the coupler strength rescaling, usually driven by
chain strength values in combinatorial problems such as Max-cut, reduces the
minimum spectral gap of the problem. This consideration could be included in
future embedding heuristics designs to enhance the quality of the generated
minor embeddings.

The analysis of the breaking chain rate considering different embeddings of
the same instance has shown that the optimal chain strength varies depending
on the embedding used. This experiment led to the design of a simple but fast
heuristic used to optimize the chain strength for each instance. The heuristic
converged in most cases in less than 5 pre-processing steps. This number has
to be considered cautiously as it strongly depends on the chain break
interval, which acts as the breaking condition of the heuristic. We used large
intervals in this experiment. The precise identification of the breaking chain
rate that produces the best results for each quantum computer could help to
refine these bounds. Even if this new method does not provide better solutions
than the basic chain scan, the original use of the breaking chain rate in the
optimization process drastically reduces the pre-processing time required by a
simple chain scan and does not require any assumption over the scanning range
of chain strengths.

The performance of our heuristic can be questioned due to the relatively low
gain on the max-cut size ($17\%$ in the best case). However, the default
uniform_torque_compensation method performed quite well compared to the chain
scan method on the max-cut problem, meaning that this default heuristic is
well-calibrated for this problem. However, even a small percentage gain in the
cut size can reduce the Time To Solution of several orders of magnitude. We
could not run such an experiment due to our restricted access time to the
D-Wave quantum systems.

A detailed study on the determination of refined breaking chain bounds for
each solver is a relevant perspective. This heuristic could also be used as a
fast pre-processing routine to find relatively good global chain strengths,
followed by a refinement step optimizing each ferromagnetic coupling strength.

## References

  * [1] D-wave system. solver properties and parameters (2024), https://docs.dwavesys.com/docs/latest/doc_solver_ref.html
  * [2] Albash, T., Lidar, D.A.: Adiabatic quantum computation. Reviews of Modern Physics 90(1), 015002 (2018)
  * [3] Boothby, T., King, A.D., Roy, A.: Fast clique minor generation in chimera qubit connectivity graphs. Quantum Information Processing 15, 495–508 (2016)
  * [4] Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 (2014)
  * [5] Choi, V.: Minor-embedding in adiabatic quantum computation: I. the parameter setting problem. Quantum Information Processing 7, 193–209 (2008)
  * [6] Choi, V.: The effects of the problem hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization. QIP 19(3), 90 (2020)
  * [7] Djidjev, H.N.: Logical qubit implementation for quantum annealing: augmented lagrangian approach. Quantum Science and Technology 8(3), 035013 (2023)
  * [8] Fang, Y.L., Warburton, P.: Minimizing minor embedding energy: an application in quantum annealing. Quantum Information Processing 19(7), 191 (2020)
  * [9] Farhi, E., Goldstone, J., et al.: A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292(5516), 472–475 (2001)
  * [10] Gilbert, V., Rodriguez, J.: Discussions about high-quality embeddings on Quantum Annealers. In: Emerging optimization methods: from metaheuristics to quantum approaches. Troyes, France (Apr 2023)
  * [11] Grant, E., Humble, T.S.: Benchmarking embedded chain breaking in quantum annealing. Quantum Science and Technology 7(2), 025029 (Mar 2022)
  * [12] Hamerly, R., Inagaki, T., McMahon, et al.: Experimental investigation of performance differences between coherent ising machines and a quantum annealer. Science Advances 5(5) (May 2019)
  * [13] Pelofske, E.: 4-clique network minor embedding for quantum annealers. arXiv preprint arXiv:2301.08807 (2023)
  * [14] Pelofske, E.: Comparing three generations of d-wave quantum annealers for minor embedded combinatorial optimization problems. arXiv:2301.03009 (2023)
  * [15] Raymond, J., Ndiaye, N., et al.: Improving performance of logical qubits by parameter tuning and topology compensation. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). pp. 295–305. IEEE (2020)
  * [16] Robertson, N., Seymour, P.: Graph minors .XIII. the disjoint paths problem. Journal of Combinatorial Theory, Series B 63(1), 65–110 (Jan 1995)
  * [17] Roy, A.: Minorminer. https://github.com/dwavesystems/minorminer (2024)
  * [18] Venturelli, D., Mandrà, S., et al.: Quantum optimization of fully connected spin glasses. Physical Review X 5(3), 031040 (2015)
  * [19] Willsch, D., Willsch, M., et al.: Benchmarking advantage and d-wave 2000q quantum annealers with exact cover problems. QIP 21(4) (Apr 2022)
  * [20] Zbinden, S., Bärtschi, A., et al.: Embedding Algorithms for Quantum Annealers with Chimera and Pegasus Connection Topologies, p. 187–206. Springer International Publishing (2020)