# Voting Rules That Are Unbiased But Not Transitive-Symmetric

Aadyot Bhatnagar
California Institute of Technology
Pasadena, CA, U.S.A.
<EMAIL_ADDRESS>
###### Abstract

We explore the relation between two natural symmetry properties of voting
rules. The first is transitive-symmetry — the property of invariance to a
transitive permutation group — while the second is the “unbiased” property of
every voter having the same influence for all i.i.d. probability measures. We
show that these properties are distinct by two constructions — one
probabilistic, one explicit — of rules that are unbiased but not transitive-
symmetric.

##  1 Introduction

We study voting rules: functions $\Phi:\\{-1,1\\}^{n}\to\\{-1,1\\}$ that map a
voting profile — the preferences of a set $V=[n]$ of $n$ voters between
alternatives $-1$ and $1$ — to an outcome in $\\{-1,1\\}$. We restrict our
attention to voting rules $\Phi$ that are odd, i.e. such that
$\Phi(-x)=-\Phi(x)$, and monotone, i.e. such that
$\Phi(x)\geqslant\Phi(x^{\prime})$ whenever $x\geqslant x^{\prime}$
coordinate-wise.

Let $S_{n}$ be the set of permutations over $V$. For a permutation $\sigma\in
S_{n}$, we define a permutation of a voting rule $\Phi$ as
$(\sigma\Phi)(x)=\Phi(\sigma^{-1}(x))$. We say that $\sigma$ is an
automorphism of $\Phi$ if $\sigma\Phi=\Phi$. We denote by $\mathrm{aut}(\Phi)$
the automorphism group of $\Phi$. A voting rule $\Phi$ is said to be
transitive-symmetric if $\mathrm{aut}(\Phi)$ is transitive, i.e. for every
pair of voters $u,v\in V$, there is an automorphism
$\sigma\in\mathrm{aut}(\Phi)$ such that $\sigma(u)=v$. Intuitively,
transitive-symmetric voting rules define “equitable” elections where each
voter plays the same “role” in determining the final outcome. These objects
were studied in detail by [2], who call them “equitable voting rules.”

For any voting rule $\Phi$ and a probability measure $q$ over
$\\{-1,1\\}^{n}$, voter $i$’s influence on $\Phi$ is the probability that they
are pivotal for a voting profile chosen from $q$. More formally, for any
$x\in\\{-1,1\\}^{n}$, let $x^{\oplus
i}=(x_{1},\ldots,x_{i-1},-x_{i},x_{i+1},\ldots,x_{n})$ be the voting profile
obtained when only voter $i$ changes their vote from $x$. We say $i$ is
pivotal for $x$ in $\Phi$ if $\Phi(x)\neq\Phi(x^{\oplus i})$, and the
influence of $i$ on $\Phi$ with respect to probability measure $q$ on
$\\{-1,1\\}^{n}$ is

$\mathbb{I}_{i}^{p}(\Phi)=\operatorname*{\mathbb{P}}_{x\sim
q}\left[{\Phi(x)\neq\Phi(x^{\oplus i})}\right]$

We say that a voting rule $\Phi$ is unbiased if
$\mathbb{I}_{1}^{q}(\Phi)=\cdots=\mathbb{I}_{n}^{q}(\Phi)$ for every i.i.d.
probability measure $q=p^{\otimes n}$ on $\\{-1,1\\}^{n}$. It is easy to see
that all transitive-symmetric voting rules are unbiased, but it is unclear
whether the converse holds. Our main theorem shows that the two properties are
distinct:111We only consider odd $n$ because it is a long-standing open
question for which even $n$ there exist odd, monotone, transitive-symmetric
voting rules [3].

######  Theorem 1.

For all $n$ odd and large enough, there exist odd, monotone voting rules
$\Phi:\\{-1,1\\}^{n}\to\\{-1,1\\}$ that are unbiased but not transitive-
symmetric.

We prove Theorem 1 by introducing a class of graphic voting rules defined by
an underlying graph (Section 2). Informally, we associate transitive-symmetric
voting rules to vertex-transitive graphs, and unbiased voting rules to regular
graphs. This construction reduces our task to proving the existence of
$d$-regular graphs that satisfy certain properties. In Section 3, we provide a
probabilistic existence proof inspired by [4] showing that the graphic voting
rules of random regular graphs are unbiased and have trivial automorphism
groups with probability $1-o(1)$. Section 4 provides an explicit construction
of a voting rule that is unbiased but not transitive-symmetric by composing a
specific asymmetric graphic voting rule with a transitive-symmetric voting
rule. However, this construction is only valid for specific $n$. Section 5
concludes.

##  2 Preliminaries

###  2.1 Graph Theory

Let $G=(V,E)$ be an unweighted, undirected graph with vertex set $V=[n]$ and
edge set $E$. We intentionally overload notation because we will associate
each vertex of a graph $G$ to a voter in a voting rule $\Phi_{G}$. For any two
vertices $u,v\in V$, let $d(u,v)$ denote the length of a shortest path between
$u$ and $v$ in $G$. The ball of radius $r$ about a vertex $v$ in $G$ is the
set of all points a distance at most $r$ away from $v$, i.e. $B_{r}(v)=\\{u\in
V:d(u,v)\leqslant r\\}$. Analogously, we also let $B_{r}(G)=\\{B_{r}(v):v\in
V\\}$ denote the set of all balls of radius $r$ in $G$. The diameter of $G$ is
$\mathrm{diam}(G)=\max_{u,v\in V}d(u,v)$, and the radius of $G$ is
$\mathrm{rad}(G)=\lceil\mathrm{diam}(G)/2\rceil$. While this definition of the
graph radius is non-standard, it has the attractive property that
$\mathrm{rad}(G)=\min\\{r\in\mathbb{R}:B_{r}(u)\cap
B_{r}(v)\neq\varnothing\,\,\forall u,v\in V\\}$.

For a permutation $\sigma\in S_{n}$, let
$\sigma(G)=(V,\\{\\{\sigma(u),\sigma(v)\\}:\\{u,v\\}\in E\\})$ be the graph
obtained by using $\sigma$ to permute the endpoints of every edge in $G$. If
$\sigma(G)=G$, then we say that $\sigma$ is an automorphism of $G$, or
$\sigma\in\mathrm{aut}(G)$. Analogously, if $B_{r}(\sigma(G))=B_{r}(G)$, then
we say that $\sigma$ is an automorphism of $B_{r}(G)$, or
$\sigma\in\mathrm{aut}(B_{r}(G))$. Note that while
$\mathrm{aut}(G)\subseteq\mathrm{aut}(B_{r}(G))$, it is unclear when the
converse holds. Figure 1 provides two examples where
$\mathrm{aut}(G)=\mathrm{aut}(B_{1}(G))$.

We say that a graph is vertex-transitive if for every pair of vertices $u,v\in
V$, there is an automorphism $\sigma\in\mathrm{aut}(G)$ such that
$\sigma(u)=v$. We say that $G$ is asymmetric if
$\absolutevalue{\mathrm{aut}(G)}=1$, i.e. the identity is the only
automorphism of $G$. We define vertex-transitivity and asymmetry for
$B_{r}(G)$ analogously. Finally, we call a graph $d$-regular if all of its
vertices have degree $d$. It is easy to see that all vertex-transitive graphs
must be regular, though the converse need not hold (Figure 1).

(a) This 3-regular graph is not vertex-transitive, though it still has
nontrivial automorphisms.

(b) This 4-regular graph is totally asymmetric, i.e. it has no non-trivial
automorphisms.

Figure 1: Regular graphs that are not vertex-transitive and have
$\mathrm{aut}(G)=\mathrm{aut}(B_{1}(G))$. The graphic voting rule associated
with the graph in Figure 1b is unbiased but not transitive-symmetric.

###  2.2 Winning Coalitions of Voting Rules

A winning coalition for a voting rule $\Phi$ is a set of voters
$S\subseteq[n]$ such that if a voting profile $x\in\\{-1,1\\}^{n}$ has
$x_{i}=y$ for all $i\in S$, then $\Phi(x)=y$. We say that a winning coalition
$S$ is minimal if no strict subset $T\subset S$ of it is also a winning
coalition. We note that $\Phi$ is odd and monotone if and only if the winning
coalitions for both alternatives $-1$ and $1$ are equal, and any superset of a
winning coalition is also a winning coalition. This observation gives rise to
the following characterization of odd, monotone voting rules:

######  Definition 2.

For any odd $n$, let $\mathcal{F}\subseteq 2^{[n]}$ be a family of sets such
that $T\cap S\neq\varnothing$ and $S\not\subset T$ for all
$S,T\in\mathcal{F}$. Define the voting rule
$\Phi_{\mathcal{F}}:\\{-1,1\\}^{n}\to\\{-1,1\\}$ as

$\Phi_{\mathcal{F}}(x)=\begin{cases}y&\exists
S\in\mathcal{F}\,\,\mathrm{s.t.}\,\,x_{i}=y\,\,\forall i\in S\\\
\mathrm{maj}_{n}(x)&\mathrm{otherwise}\end{cases}$

$\Phi_{\mathcal{F}}$ is well-defined only if $\mathcal{F}$ is an intersecting
family of sets. This is because every $S\in\mathcal{F}$ is a minimal winning
coalition for $\Phi_{\mathcal{F}}$ (minimality follows because $S\not\subset
T$ for any $S,T\in\mathcal{F}$). We call a voter $i$ pivotal for a winning
coalition $S$ if $S\setminus\\{i\\}$ is not a winning coalition. This re-
framing of voting rules in terms of winning coalitions gives us the following
characterization of odd, monotone, unbiased voting rules:

######  Lemma 3.

Let $\Phi:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be an odd, monotone voting rule with
minimal winning coalitions $\mathcal{F}$. $\Phi$ is unbiased if and only if
every voter $i$ is pivotal for an equal number of winning coalitions of each
size.

###### Proof.

Let $\mathcal{F}_{i}=\\{T:\exists!S\in\mathcal{F}\mbox{ s.t. }i\in S\mbox{ and
}S\subseteq T\\}$ be the set of winning coalitions of $\Phi$ for which voter
$i$ is pivotal, and let
$\mathcal{F}_{i,j}=\\{S\in\mathcal{F}_{i}:\absolutevalue{S}=j\\}$ be the
subset of these coalitions with size $j$. If we let
$m_{i,j}=\absolutevalue{\mathcal{F}_{i,j}}$, then for any probability measure
$p$ on $\\{-1,1\\}$, voter $i$ has influence

where, with the slight abuse of notation $\operatorname*{\mathbb{P}}_{x\sim
p}\left[{x=1}\right]=p$, the coefficients are
$c_{j}(p)=p^{j-1}(1-p)^{n-j+1}+p^{n-j+1}(1-p)^{j-1}+p^{j}(1-p)^{n-j}+p^{n-j}(1-p)^{j}$.
Because $\Phi$ is unbiased, we know that
$\sum_{j=1}^{n}m_{1,j}c_{j}(p)=\cdots=\sum_{j=1}^{n}m_{n,j}c_{j}(p)$ for all
$p$. This is possible if and only if $m_{1,j}=\cdots=m_{n,j}$ for each
$j\in[n]$.

∎

We can also lower bound the size of the smallest winning coalition of any odd,
monotone, unbiased voting rule:

######  Lemma 4.

Let $\Phi:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be an odd, monotone, unbiased voting
rule with minimal winning coalitions $\mathcal{F}$. Then,
$\absolutevalue{S}\geqslant\lceil\sqrt{n}\rceil$ for all $S\in\mathcal{F}$.

###### Proof.

Let $k=\min\\{\absolutevalue{S}:S\in\mathcal{F}\\}$ be the size of a smallest
winning coalition of $\Phi$ (call it a minimum winning coalition) and let
$\mathcal{F}^{*}=\bigcup_{i=1}^{n}\mathcal{F}^{*}_{i}$ be the set of all
minimum winning coalitions. Let
$m_{i}=\absolutevalue{\\{S\in\mathcal{F}^{*}:i\in S\\}}$ and
$m=\absolutevalue{\mathcal{F}^{*}}$. Since $\Phi$ is unbiased and every
participating voter is pivotal for a minimum winning coalition,
$m_{1}=\cdots=m_{n}=mk/n$ by Lemma 3 and the fact that
$\sum_{i=1}^{n}m_{i}=mk$.

Therefore, for any $S\in\mathcal{F}^{*}$, $\sum_{i\in
S}\sum_{T\in\mathcal{F}}\mathds{1}[i\in T]=\sum_{i\in S}m_{i}=mk^{2}/n$. This
implies that the elements of $S$ collectively appear in at most $mk^{2}/n$
different $T\in\mathcal{F}^{*}$. Finally, because
$\mathcal{F}^{*}\subseteq\mathcal{F}$ is an intersecting family of sets with
$\absolutevalue{\mathcal{F}^{*}}=m$, we can conclude that $m\leqslant
mk^{2}/n\implies k\geqslant\sqrt{n}$. Since $k\in\mathbb{Z}$, this implies
that $k\geqslant\lceil\sqrt{n}\rceil$.

∎

It is worth noting that [2] proved that
$\absolutevalue{S}\geqslant\lceil\sqrt{n}\rceil$ for all $S\in\mathcal{F}$
when $\Phi$ is transitive-symmetric (Theorem 2), and moreover, there exist
transitive-symmetric $\Phi$ for which this lower bound is tight (Theorem 6).
Our Lemma 4 has just shown that the lower bound even holds under the weaker
condition $\Phi$ is unbiased. Our Theorem 16 proves that this lower bound is
tight up to a constant factor if $\Phi$ is unbiased but not transitive-
symmetric, but it is unclear whether the bound is achieved exactly by any
voting rules that are unbiased but not transitive-symmetric.

###  2.3 Graphic Voting Rules

We consider voting rules that equate the set of voters with the vertices of an
underlying graph $G$. To avoid treating ties in a voting model that only
admits strict preferences, we assume $\absolutevalue{V}=n$ is odd. The graphic
voting rule associated to a graph $G$ of radius $r$ is just
$\Phi_{G}=\Phi_{B_{r}(G)}$, i.e.

$\displaystyle\Phi_{G}(x)=\Phi_{B_{r}(G)}(x)=\begin{cases}y&\exists v\in
V\,\,\mathrm{s.t.}\,\,x_{i}=y\,\,\forall i\in B_{r}(v)\\\
\mathrm{maj}_{n}(x)&\mathrm{otherwise}\end{cases}$

We make a few remarks about this definition, some of which will motivate us to
impose additional assumptions on the graph $G$ underlying the voting rule
$\Phi_{G}$.

  1. 1.

$\Phi_{G}$ is a valid voting rule that is odd and monotone because $B_{r}(G)$
is an intersecting family of sets by our definition of the graph radius.

  2. 2.

Because $\Phi_{G}$ is uniquely determined by $G$’s balls of radius $r$, we
know that $\mathrm{aut}(\Phi_{G})\subseteq\mathrm{aut}(B_{r}(G))$. So if
$B_{r}(G)$ is not vertex-transitive, then $\Phi_{G}$ is not transitive-
symmetric.

  3. 3.

We can assume that $\mathrm{diam}(G)=2$ (and therefore $\mathrm{rad}(G)=1$)
without loss of generality: if $\mathrm{rad}(G)=r$, let
$G^{\prime}=\quantity(V,\\{\\{u,v\\}:u\in V,v\in B_{r}(u)\\})$ be the graph
obtained by connecting all the vertices of $G$ in balls of radius $r$. It is
easy to see that $\mathrm{rad}(G^{\prime})=1$ and
$\Phi_{G}=\Phi_{G^{\prime}}$. We ignore the trivial case where where
$\mathrm{diam}(G^{\prime})=1$ and $G^{\prime}$ is just the complete graph.

  4. 4.

We further assume that $G$ is $d$-regular and has all balls of radius 1
distinct. Then, every voter in $\Phi_{G}$ participates in exactly $d+1$
minimum winning coalitions, each of size $d+1$.

  5. 5.

To ensure that $\Phi_{G}\neq\mathrm{maj}_{n}$, we further assume that $G$ is
$d$-regular with $d\leqslant(n-3)/2$.

Theorem 6 shows that 3 - 5 are reasonable assumptions, even in conjunction. We
now provide an explicit example of an odd, monotone voting rule on $n=11$
voters that is unbiased but not transitive-symmetric:

######  Theorem 5.

Let $G$ be the graph depicted in Figure 1b. Then $\Phi_{G}$ is an odd,
monotone, unbiased voting rule with
$\absolutevalue{\mathrm{aut}(\Phi_{G})}=1$, i.e. $\Phi_{G}$ is totally
asymmetric.

###### Proof.

$G$ is a 4-regular graph on 11 vertices with $\mathrm{diam}(G)=2$ and all
balls of radius 1 distinct. One can also check through exhaustive computation
that $\mathrm{aut}(B_{1}(G))$ is trivial. Therefore,
$\Phi_{G}:\\{-1,1\\}^{11}\to\\{-1,1\\}$ is such that
$\mathrm{aut}(\Phi_{G})\subseteq\mathrm{aut}(B_{1}(G))=\\{\mathrm{id}\\}$, and
each of the 11 voters participates in exactly 5 minimum winning coalitions of
size 5. Because these are the only winning coalitions in which $\Phi_{G}$
differs from majority rule, every voter is pivotal to an equal number of
winning coalitions of each size. By Lemma 3, this implies that $\Phi_{G}$ is
unbiased.

∎

##  3 A Probabilistic Construction

Here, we use the probabilistic method to prove the existence of a class of
regular graphs whose associated graphic voting rules are totally asymmetric,
unbiased, and have winning coalitions of size $\lfloor 0.293n\rfloor$. This
result immediately implies our main Theorem 1. More specifically, let
$\mathcal{G}_{n,d}$ be the uniform distribution over $d$-regular graphs on $n$
vertices, where $nd$ is even. For our purposes, this means that $n$ is odd and
$d$ is even. Theorem 6 shows that probability of sampling a graph of interest
from $\mathcal{G}_{n,d}$ is $1-o(1)$, as long as the degree $d$ is large
enough:

######  Theorem 6.

Let $G\sim\mathcal{G}_{n,d}$ with $\sqrt{n}\log n\leqslant d\leqslant n/2$.
Then, with probability $1-o(1)$, $\absolutevalue{\mathrm{aut}(B_{1}(G))}=1$
and $\absolutevalue{B_{1}(u)\cap B_{1}(v)}=(1+o(1))d^{2}/n$ for every pair of
vertices $u\neq v$.

When taken together with the following result, our main Theorem 1 follows:

######  Theorem 7.

Let $G$ be a $d$-regular graph with $\lfloor 0.293n\rfloor-1\leqslant
d\leqslant(n-3)/2$, $\absolutevalue{\mathrm{aut}(B_{1}(G))}=1$, and
$\absolutevalue{B_{1}(u)\cap B_{1}(v)}=(1+o(1))d^{2}/n$ for every pair of
vertices $u\neq v$. If $n$ is odd, then $\Phi_{G}$ is an odd, monotone,
unbiased voting rule with $\absolutevalue{\mathrm{aut}(\Phi_{G})}=1$.
Moreover, $\Phi_{G}$ has winning coalitions of size $d+1$.

###### Proof.

Because $0<\absolutevalue{B_{1}(u)\cap B_{1}(v)}=(1+o(1))d^{2}/n<d+1$ for all
$u\neq v\in V$, we know that $\mathrm{rad}(G)=1$ and all balls of radius 1 are
distinct. Therefore,
$\mathrm{aut}(\Phi_{G})\subseteq\mathrm{aut}(B_{1}(G))=\\{\mathrm{id}\\}$, and
each voter participates in exactly $d+1$ minimum winning coalitions of size
$d+1$. Now, we prove that $\Phi_{G}$ is unbiased.

Let $k=\max_{u\neq v}\absolutevalue{B_{1}(u)\cap B_{1}(v)}=(1+o(1))d^{2}/n$ be
the maximal intersection between any two minimum winning coalitions of
$\Phi_{G}$, and consider the following families of winning coalitions for each
$v\in V$:

$\mathcal{F}_{v}=\\{S\supseteq
B_{1}(v):\absolutevalue{S}<\min\\{2(d+1)-k,(n+1)/2\\}\\}$

Because $\absolutevalue{S}<2(d+1)-k\leqslant\absolutevalue{B_{1}(u)\cup
B_{1}(v)}$ for all $S\in\mathcal{F}$ and $u\neq v\in V$, we know that
$\mathcal{F}_{u}\cap\mathcal{F}_{v}=\varnothing$ and
$\absolutevalue{\\{S\in\mathcal{F}_{u}:\absolutevalue{S}=t\\}}=\absolutevalue{\\{S\in\mathcal{F}_{v}:\absolutevalue{S}=t\\}}$
for all $t$. Moreover, if $S\in\mathcal{F}_{v}$, then $S\setminus\\{u\\}$ is
not a winning coalition for any $u\in B_{1}(v)$ (since no
$S\in\mathcal{F}_{v}$ is a majority). In words, every voter in $B_{1}(v)$ is
pivotal to every winning coalition in $\mathcal{F}_{v}$.

Now assume that $2(d+1)-k\geqslant(n+1)/2$. Then, $\bigcup_{v\in
V}\mathcal{F}_{v}$ is exactly the set of all winning coalitions smaller than a
majority. Because every voter $v\in V$ participates in exactly $d+1$ minimum
winning coalitions $B_{1}(u)$ of size $d+1$, the analysis above implies that
every voter is pivotal for an equal number of winning coalitions of each size.
By Lemma 3, this implies that $\Phi_{G}$ is unbiased.

Finally, we translate the assumption that $2(d+1)-k\geqslant(n+1)/2$ into an
assumption about $d$. Since, $k=(1+o(1))d^{2}/n$, we solve the quadratic
inequality $2(d+1)-(1+o(1))d^{2}/n\geqslant(n+1)/2$ to obtain the condition
that $d\geqslant(1-1/\sqrt{2}+o(1))n$. For $n$ large enough,
$d\geqslant\lfloor 0.293n\rfloor-1$ will suffice.

∎

The remainder of this section proves Theorem 6 as a concentration inequality
about the defect of a random regular graph. Intuitively, the defect of a graph
$G$ quantifies just how asymmetric its balls $B_{1}(G)$ of radius 1 are. More
formally, we have the following definition and lemma, inspired by [4]:

######  Definition 8.

Let $G=(V,E)$ be a graph, and let $\sigma,\pi\in S_{n}$ be permutations of
$V$. The defect of a vertex $v$ with respect to $\sigma$ and $\pi$ is

$D_{\sigma,\pi}(v)=\absolutevalue{\sigma(B_{1}(v))\,\,\Delta\,\,B_{1}(\pi(v))}$

where $\Delta$ denotes the symmetric difference. Analogously, we define the
defect of the graph $G$ with respect to $\sigma$ and $\pi$ as
$D_{\sigma,\pi}(G)=\max_{v\in V}D_{\sigma,\pi}(v)$.

######  Lemma 9.

Let $G=(V,E)$ be a graph and $\sigma\in S_{n}$ a permutation of $V$. Then,
$\sigma\in\mathrm{aut}(B_{1}(G))$ if and only if there exists another
permutation $\pi\in S_{n}$ such that $D_{\sigma,\pi}(G)=0$. Moreover,
$\sigma\in\mathrm{aut}(G)$ if and only if $D_{\sigma,\sigma}(G)=0$.

###### Proof.

By definition, $\sigma$ is an automorphism of $B_{1}(G)$ if and only if for
every vertex $v\in V$, there is another vertex $v^{\prime}\in V$ such that
$\sigma(B_{1}(v))=B_{1}(v^{\prime})$. In the case where all balls $B_{1}(v)$
are distinct, this is possible if and only if the mapping $v\mapsto
v^{\prime}$ is a permutation, which we will call $\pi$. In the general case,
$\pi$ need not be bijective, but there will always be a bijective $\pi$ for
which the desired statement holds biconditionally. Since
$\sigma(B_{1}(v))=B_{1}(\pi(v))$ for all $v\in V$, $D_{\sigma,\pi}(G)=0$. The
second statement follows from the fact that $\sigma\in\mathrm{aut}(G)$ if and
only if $\\{\sigma(u),\sigma(v)\\}\in E$ for every edge $\\{u,v\\}\in E$. This
is equivalent to saying that $B_{1}(\sigma(v))=\sigma(B_{1}(v))$ for every
vertex $v\in V$.

∎

Our proof of Theorem 6 closely follows the approach of [4]. Subsection 3.1
proves a concentration inequality about the defect of an Erdős-Rényi random
graph, and Subsection 3.2 uses that result to prove an analogous statement
(from which Theorem 6 follows) about random regular graphs.

###  3.1 A Result About Erdős-Rényi Random Graphs

The Erdős-Rényi random graph distribution $G(n,p)$ is the probability space
over graphs with vertex set $V=[n]$, where each of the $\binom{n}{2}$ possible
edges is present independently with probability $p$. In this subsection, we
prove the following concentration inequality about the defect of a graph drawn
from the Erdős-Rényi distribution $G(n,p)$. The proof closely follows that of
Theorem 3.1 in [4]:

######  Theorem 10.

Let $G\sim G(n,p)$ with $p=\omega(\log n/n)$ and $1-p=\omega(\log n/n)$. Then,
there exist permutations $\sigma,\pi\in S_{n}$ such that
$\absolutevalue{\\{v\in V:\sigma(v)\neq v\mbox{ or }\pi(v)\neq
v\\}}\geqslant\ell$ and $D_{\sigma,\pi}(G)<(2-o(1))np(1-p)$ with probability
at most

$\displaystyle 4\sum_{k=\ell}^{n}\exp(-c\epsilon^{2}np(1-p)+2\log n)^{k}=o(1)$

for some constant $c>0$ and any $\epsilon=\epsilon(n)$ such that
$\epsilon=o(1)$ and $\epsilon^{2}np(1-p)=\omega(\log n)$. For example,
$p=\log(n)^{2}/n$ and $\epsilon=\log(n)^{-1/3}$ suffice.

Intuitively, Theorem 10 implies that $B_{1}(G)$ from almost every $G\sim
G(n,p)$ is highly asymmetric. We state the probability bound in a particularly
technical way to facilitate the proof of an analogous theorem about random
$np$-regular graphs in Subsection 3.2. The centerpiece of our proof of Theorem
10 is the following concentration inequality, which represents a refinement of
McDiarmid’s bounded difference inequality [6] to the special case of Bernoulli
random variables:

######  Lemma 11 (Alon et al. [1]).

Let $X$ be a random variable on a probability space generated by finitely many
independent Bernoulli random variables $Y_{i}\sim\mathrm{Bern}(p_{i})$. Let
$\delta$ be such that changing any $Y_{i}$ (keeping all others the same) can
change $X$ by at most $\delta$. Define
$\Delta^{2}=\delta^{2}\sum_{i}p_{i}(1-p_{i})$. Then, for all
$0<t<2\Delta/\delta$,
$\operatorname*{\mathbb{P}}\left[{\absolutevalue{X-\operatorname*{\mathbb{E}}\left[{X}\right]}>t\Delta}\right]\leqslant
2e^{-t^{2}/4}$.

###### Proof (Theorem 10)..

Let $\sigma,\pi\in S_{n}$ be permutations of the vertices of $G$, and let
$U=\\{v\in V:\sigma(v)\neq v\mbox{ or }\pi(v)\neq v\\}$ be the vertices not
fixed in place by $\sigma$ and $\pi$. Let $k=\absolutevalue{U}$, and assume
that $k>0$ for non-triviality. Next, let $X=\sum_{v\in U}D_{\sigma,\pi}(v)$.
We will apply Lemma 11 to the random variable $X$ later in the proof.

For any vertex $v\in U$, let $E_{1}^{uv}$ be the event that
$u\in\sigma(B_{1}(v))\setminus B_{1}(\pi(v))$ and let $E_{2}^{uv}$ be the
event that $u\in B_{1}(\pi(v))\setminus\sigma(B_{1}(v))$. $E_{1}^{uv}$ occurs
if and only if $\\{\sigma^{-1}(u),v\\}\in E$ and $\\{u,\pi(v)\\}\notin E$,
while $E_{2}^{uv}$ occurs if and only if $\\{u,\pi(v)\\}\in E$ and
$\\{\sigma^{-1}(u),v\\}\notin E$. Since $v$ is moved by at least one of
$\sigma$ or $\pi$ (by the assumption that $v\in U$), this implies that

where the terms $(n-1)$ and $(n-2)$ account for cases where $u=\pi(v)$ and
$\sigma^{-1}(u)=v$. Therefore,

$\displaystyle\operatorname*{\mathbb{E}}\left[{X}\right]=\sum_{v\in
U}\operatorname*{\mathbb{E}}\left[{D_{\sigma,\pi}(v)}\right]=(2-o(1))knp(1-p$

Now, we analyze how the presence of edges in $G$ influences the value of $X$.
First, we note that $X$ only depends on edges of the graph incident to
vertices in $U$. There are $k(n-k)+\binom{k}{2}$ such edges. Second, adding or
deleting an edge $\\{u,v\\}$ from $G$ can only change the values of the
following six summands, each by at most 1: $D_{\sigma,\pi}(u)$,
$D_{\sigma,\pi}(v)$, $D_{\sigma,\pi}(\sigma^{-1}(u))$,
$D_{\sigma,\pi}(\sigma^{-1}(v))$, $D_{\sigma,\pi}(\pi^{-1}(u))$, and
$D_{\sigma,\pi}(\pi^{-1}(v))$. This means that $X$ satisfies the hypothesis of
Lemma 11 with parameters $\delta=6$ and
$\Delta^{2}=36(k(n-k)+\binom{k}{2})p(1-p)=\Theta(knp(1-p))$. So for some
constant $c>0$,

$\displaystyle\operatorname*{\mathbb{P}}\left[{\absolutevalue{X-\operatorname*{\mathbb{E}}\left[{X}\right]}>2\epsilon
knp(1-p)}\right]\leqslant$

Therefore, with probability at least $1-\exp(-c\epsilon^{2}knp(1-p))$,

$\displaystyle D_{\sigma,\pi}(G)\geqslant\max_{v\in
U}D_{\sigma,\pi}(v)\geqslant\frac{1}{k}\quantity(\operatorname*{\mathbb{E}}\left[{X}\right]-2\epsilon
knp(1-p))=(2-o(1))np(1-p$

To bound the probability that this bound holds for all $\sigma,\pi\in S_{n}$
for which $k=\absolutevalue{U}\geqslant\ell$, we will take a union bound.
There are at most $\binom{n}{k}k!\leqslant n^{k}$ permutations that exactly
fix $n-k$ vertices, so there are at most
$\sum_{i=0}^{k}\sum_{j=0}^{k}n^{i}n^{j}\leqslant 4n^{2k}$ pairs of
permutations $\pi$ and $\sigma$ that fix exactly $n-k$ vertices between them,
i.e. for which $\absolutevalue{U}=k$. Therefore, there exists a non-trivial
pair of permutations $\pi$ and $\sigma$ for which
$\absolutevalue{U}\geqslant\ell$ and $D_{\sigma,\pi}(G)<(2-o(1))np(1-p)$ with
probability at most

$\displaystyle\sum_{k=\ell}^{n}4n^{2k}\exp(-c\epsilon^{2}knp(1-p))=4\sum_{k=\ell}^{n}\exp(-c\epsilon^{2}np(1-p)+2\log
n)^{k}$

∎

###  3.2 Proof of Theorem 6

Theorem 6 follows immediately from Lemmas 12 and 13:

######  Lemma 12 (Krivelevich et al. [5]).

Let $G\sim\mathcal{G}_{n,d}$. If $\sqrt{n}\log n\leqslant d\leqslant
n-n/\log_{2}n$, then with probability $1-o(1)$, $\absolutevalue{B_{1}(u)\cap
B_{1}(v)}=(1+o(1))d^{2}/n$ for every pair of vertices $u\neq v$ in $G$. If
instead $\log n\leqslant d\leqslant\sqrt{n}\log n$, then with probability
$1-o(1)$, there exists a constant $\epsilon>0$ such that
$\absolutevalue{B_{1}(u)\cap B_{1}(v)}<d^{1-\epsilon}$ for every pair of
vertices $u\neq v$ in $G$.

######  Lemma 13.

Let $G\sim\mathcal{G}_{n,d}$, with $d=\omega(\log n)$ and $d\leqslant n/2$.
With probability $1-o(1)$, $\absolutevalue{\mathrm{aut}(B_{1}(G))}=1$, i.e.
$B_{1}(G)$ is totally asymmetric.

To prove Lemma 13, we will need two additional technical lemmas from [4]:

######  Lemma 14 (Kim et al. [4]).

Let $G\sim\mathcal{G}_{n,d}$ with $d\leqslant n^{3/4}$ and $d=\omega(\log n)$.
Then, with probability $1-o(1)$, every subset of vertices in $G$ of size
$a\leqslant nd^{-1/3}$ spans at most $da/\log d$ edges.

######  Lemma 15 (Kim et al. [4]).

Let $G\sim G(n,d/n)$. For any constant $\delta>0$ and $n$ sufficiently large,
$G$ is $d$-regular with probability at least $\exp(-nd^{1/2+\delta})$.

###### Proof (Lemma 13)..

The proof closely follows Section 5 of [4], which proves an analogous result
for $\mathrm{aut}(G)$, rather than $\mathrm{aut}(B_{1}(G))$. Our strategy for
adapting their proof is similar to the way we proved Theorem 10. Re-
introducing notation from that proof, for any non-trivial pair permutations
$\sigma,\pi\in S_{n}$, we will let $U=\\{v\in V:\pi(v)\neq v\mbox{ or
}\sigma(v)\neq v\\}$ and $W=V\setminus U$. The following observation is
critical:

$\displaystyle D_{\sigma,\pi}(v)$
$\displaystyle\geqslant\absolutevalue{(\sigma(B_{1}(v))\cap
W)\,\,\Delta\,\,(B_{1}(\pi(v))\cap W)}$
$\displaystyle=\quantity(d+1-\absolutevalue{\sigma(B_{1}(v))\cap
U})+\quantity(d+1-\absolutevalue{B_{1}(\pi(v))\cap U})$
$\displaystyle\quad-2\absolutevalue{\sigma(B_{1}(v))\cap B_{1}(\pi(v))\cap W}$
$\displaystyle=2d+2-\absolutevalue{B_{1}(v)\cap
U}-\absolutevalue{B_{1}(\pi(v))\cap U}-2\absolutevalue{B_{1}(v)\cap
B_{1}(\pi(v))\cap W}$ (1) $\displaystyle\geqslant
2d-\absolutevalue{B_{1}(v)\cap U}-\absolutevalue{B_{1}(\pi(v))\cap
U}-2\absolutevalue{B_{1}(v)\cap B_{1}(\pi(v))}$ (2)

Inequality 1 follows because that $\sigma(v)\in U$ for all $v\in U$ and
$\sigma(v)=v$ for all $v\in V\setminus U$. Now, we enumerate cases.

  1. 1.

$n^{3/4}\leqslant d\leqslant n/2$. Then, Lemma 12 tells us that
$\absolutevalue{B_{1}(v)\cap B_{1}(\pi(v))}=(1+o(1))d^{2}/n$ with probability
$1-o(1)$. If we let $\ell=d^{1-\delta}=o(d)$ for some small constant
$\delta>0$ ($\delta=1/100$ suffices), we need to analyze two additional sub-
cases:

    1. (a)

$\absolutevalue{U}>\ell$. For any graph $G$, let $B_{G}$ denote the event that
there exist permutations $\sigma,\pi\in S_{n}$ such that
$\absolutevalue{U}>\ell$ and $D_{\sigma,\pi}(G^{\prime})<(2-o(1))d(1-d/n)$. By
Theorem 10,

$\displaystyle\operatorname*{\mathbb{P}}_{G^{\prime}\sim
G(n,d/n)}\left[{B_{G^{\prime}}}$ $\displaystyle\leqslant
4\sum_{k=\ell+1}^{n}\exp(-c\epsilon^{2}d(1-d/n)+2\log n)^{k}$

for an appropriately chosen constant $c$. If we constrain $\epsilon\geqslant
d^{-\delta}$, our assumption that $\ell=d^{1-\delta}$ tells us that this
probability is at most $\exp(-\Omega(d^{2-3\delta}))$ and therefore

The second-to-last line uses the fact that
$\operatorname*{\mathbb{P}}\left[{A\mid
B}\right]\leqslant\operatorname*{\mathbb{P}}\left[{A}\right]/\operatorname*{\mathbb{P}}\left[{B}\right]$,
and the last line invokes Lemma 15, which says that $G^{\prime}$ is regular
with probability at least $\exp(-nd^{1/2+\delta})$. Finally, because we
constrain $n^{3/4}\leqslant d\leqslant n/2$, the final quantity is $o(1)$ as
desired.

    2. (b)

$\absolutevalue{U}\leqslant\ell$. Then, $\absolutevalue{B_{1}(v)\cap
U}\leqslant\absolutevalue{U}=o(d)$ and $\absolutevalue{B_{1}(\pi(v))\cap
U}\leqslant\absolutevalue{U}=o(d)$. Substituting these quantities into
Inequality 2, we get that with probability $1-o(1)$,
$D_{\sigma,\pi}(v)\geqslant(2-o(1))d(1-d/n)$ for all non-trivial pairs of
permutations $\sigma$ and $\pi$ for which $\absolutevalue{U}\leqslant\ell$.

    3. (c)

$d\leqslant n^{3/4}$ and $d=\omega(\log n)$. Then, by Lemma 12,
$\absolutevalue{B_{1}(v)\cap B_{1}(\pi(v))}=o(d)$ for all vertices $v$ with
probability $1-o(1)$. If we let $\ell=nd^{-1/3}\geqslant d$, we have two-sub-
cases again:

      1. i.

$\absolutevalue{U}>\ell$. The analysis is nearly identical to case 1(a), and
proves the same result.

      2. ii.

$\absolutevalue{U}\leqslant\ell$. By Lemma 14, with probability $1-o(1)$,
every subset $U\subseteq V$ of vertices with $\absolutevalue{U}\leqslant\ell$
spans at most $d\absolutevalue{U}/\log d=o(d)$ edges. This implies that with
probability $1-o(1)$, every such $U$ contains a vertex $v\in U$ such that
$\absolutevalue{B_{1}(v)\cap U}=o(d)$ and $\absolutevalue{B_{1}(\pi(v))\cap
U}=o(d)$. So substituting into Inequality 2, we get that with probability
$1-o(1)$, $D_{\sigma,\pi}(G)\geqslant(2-o(1))d\geqslant(2-o(1))d(1-d/n)$ for
every non-trivial pair of permutations $\sigma$ and $\pi$ for which
$\absolutevalue{U}\leqslant\ell$.

Therefore, we can conclude that with probability $1-o(1)$,
$D_{\sigma,\pi}(G)\geqslant(2-o(1))d(1-d/n)$ for every non-trivial pair
permutations $\sigma$ and $\pi$. By Lemma 9, this result implies that
$\absolutevalue{\mathrm{aut}(B_{1}(G))}=1$ with probability $1-o(1)$.

∎

##  4 An Explicit Construction

In this section, we explicitly construct a voting rule that is unbiased,
neither transitive-symmetric nor asymmetric, and has winning coalitions of
size $O(\sqrt{n})$:

######  Theorem 16.

Let $m=q^{2}+q+1$ for some prime power $q$, and let $n=11m$. Then, there
exists an odd, monotone, unbiased voting rule
$\Phi:\\{-1,1\\}^{n}\to\\{-1,1\\}$ that is not transitive symmetric and has
winning coalitions of size $\lfloor 1.508\sqrt{n}\rfloor+5$.

We prove Theorem 16 by using the procedure we describe in Lemma 17 to compose
the unbiased but asymmetric graphic voting rule $\Phi_{1}$ of Theorem 5 with a
transitive-symmetric voting rule $\Phi_{2}$ described by [2]. Informally, we
consider $n_{2}$ groups of $n_{1}$ voters each. We let each of these groups
make a decision using $\Phi_{1}$ and then aggregate these group decisions
using $\Phi_{2}$. More formally,

######  Lemma 17.

Let $\Phi_{1}:\\{-1,1\\}^{n_{1}}\to\\{-1,1\\}$ be an odd, monotone, unbiased
voting rule that is not transitive-symmetric and has winning coalitions of
size $d_{1}$. Let $\Phi_{2}:\\{-1,1\\}^{n_{2}}\to\\{-1,1\\}$ be an odd,
monotone, transitive-symmetric voting rule that has winning coalitions of size
$d_{2}$. Then, there exists a voting rule $\Phi:\\{-1,1\\}^{n_{1}\times
n_{2}}\to\\{-1,1\\}$ that has winning coalitions of size $d_{1}d_{2}$, and is
odd, monotone, unbiased, and not transitive-symmetric.

###### Proof.

For $X\in\\{-1,1\\}^{n_{1}\times n_{2}}$, let
$X^{(i)}=(x_{1,i},\ldots,x_{n_{1},i})^{T}\in\\{-1,1\\}^{n_{2}}$ be the
$i^{th}$ column vector of $X$, and define

$\Phi(X)=\Phi_{2}\quantity(\Phi_{1}(X^{(1)}),\ldots,\Phi_{1}(X^{(n_{2})}))$

$\Phi$ is odd and monotone because $\Phi_{1}$ and $\Phi_{2}$ are also odd and
monotone. We can form a winning coalition of size $d_{1}d_{2}$ for $\Phi$ by
taking a winning coalition for $\Phi_{2}$ and assigning to each member of that
coalition an entire winning coalition for $\Phi_{1}$.

Now, we show that $\Phi$ is unbiased. Because $\Phi_{1}$ is unbiased, every
$x_{i,j}$ has an equal probability of being pivotal to $\Phi_{1}(X^{(j)})$.
Because $\Phi_{2}$ is unbiased, every $\Phi_{1}(X^{(j)})$ has an equal
probability of being pivotal to
$\Phi(X)=\Phi_{2}(\Phi_{1}(X^{(1)}),\ldots,\Phi_{1}(X^{(n_{2})}))$. So every
$x_{i,j}$ has an equal probability of being pivotal to $\Phi(X)$, i.e. $\Phi$
is unbiased.

Finally, we show that $\Phi$ is not transitive-symmetric. Let
$\sigma\in\mathrm{aut}(\Phi)$, so $\Phi(X)=\Phi(\sigma^{-1}(X))$ for all
$X\in\\{-1,1\\}^{n_{1}\times n_{2}}$. By the definition of $\Phi$ and the fact
that $\Phi_{2}$ is non-constant, each $X$ must have some
$\sigma_{2,X}\in\mathrm{aut}(\Phi_{2})$ such that

$\displaystyle\quantity(\Phi_{1}(\sigma^{-1}(X)^{(1)}),\ldots,\Phi_{1}(\sigma^{-1}(X)^{(n_{2})}))=\quantity(\Phi_{1}(X^{\sigma_{2,X}^{-1}(1)}),\ldots,\Phi_{1}(X^{\sigma_{2,X}^{-1}(n_{2})}))$

Because this must hold for all $X$ and $\Phi_{1}$ is also non-constant, this
further implies that each $X$ must also have some
$\sigma_{1,X}\in\mathrm{aut}(\Phi_{1})$ such that

$\sigma^{-1}(X)^{(i)}=\sigma_{1,X}^{-1}(X^{(\sigma_{2,X}^{-1}(i))})$

for all $i\in[n_{2}]$. However, because $\Phi_{1}$ is not transitive-
symmetric, there must be some $u,v\in[n_{1}]$ such that $\sigma_{1,X}(u)\neq
v$ for all $\sigma_{1,X}\in\mathrm{aut}(\Phi_{1})$. Therefore, we can conclude
that $\Phi$ is not transitive-symmetric.

∎

###### Proof (Theorem 16).

Theorem 5 describes a voting rule $\Phi_{1}:\\{-1,1\\}^{11}\to\\{-1,1\\}$ that
is odd, monotone, unbiased, not transitive-symmetric, and has winning
coalitions of size 5. Theorem 6 of [2] constructs a voting rule
$\Phi_{2}:\\{-1,1\\}^{m}\to\\{-1,1\\}$ that is odd, monotone, transitive-
symmetric, and has winning coalitions of size $\lceil\sqrt{m}\rceil$. Lemma 17
provides an algorithm to compose $\Phi_{1}$ and $\Phi_{2}$ to obtain a voting
rule $\Phi:\\{-1,1\\}^{11m}\to\\{-1,1\\}$ that is odd, monotone, unbiased, not
transitive-symmetric, and has winning coalitions of size
$5\lceil\sqrt{m}\rceil\leqslant\frac{5\sqrt{n}}{\sqrt{11}}+5\leqslant\lfloor
1.508\sqrt{n}\rfloor+5$.

∎

##  5 Conclusions and Future Work

We have provided two proofs that there exist voting rules which are unbiased
but not transitive-symmetric. At the crux of our arguments is a class of
voting rules defined by $d$-regular graphs of diameter 2.

Section 3 provides a probabilistic proof that there exist voting rules that
are unbiased and totally asymmetric (not just not transitive-symmetric).
Theorem 6 shows that with probability $1-o(1)$, the voting rules defined by
random $d$-regular graphs for $d\geqslant\sqrt{n}\log n$ are totally
asymmetric and have all voters participate in exactly $d+1$ minimum winning
coalitions of size $d+1$. Theorem 7 shows that if we relax the lower bound on
the degree to $d\geqslant 0.293n-1$, these voting rules are also unbiased with
probability $1-o(1)$.

Section 4 explicitly constructs a class of voting rule that is unbiased, but
neither transitive-symmetric nor totally asymmetric. On the other hand, this
class of voting rules has much smaller winning coalitions of size
$O(\sqrt{n})$, which differs by only a constant factor from the lower bound of
$\lceil\sqrt{n}\rceil$ that we proved in Lemma 4.

We see two possible directions for future work. First, we conjecture that
there exist voting rules that are unbiased, totally asymmetric, and have
winning coalitions of size $\sqrt{n}\log n+1$ (i.e. the lower bound of Theorem
7 can be made to match that of Theorem 6). A more sophisticated proof of Lemma
12 may be a fruitful avenue to such a result.

Second, given the existence of voting rules that are unbiased, neither
transitive-symmetric nor totally asymmetric, and have winning coalitions of
size $O(\sqrt{n})$, we conjecture that Theorems 6 and 7 can be refined to
prove that there exist $d$-regular graphs whose associated voting rules are
unbiased but not transitive-symmetric (rather than totally asymmetric) as long
as $d\geqslant\lceil\sqrt{n}\rceil-1$ (rather than $d\geqslant\sqrt{n}\log
n$). In other words, we believe that the lower bound of Lemma 4 is tight not
only in general, but also for our construction using graphic voting rules.

## Acknowledgments

I would like to thank Omer Tamuz for pointing me to some useful references and
for his helpful feedback on drafts of this paper. I would like to thank
Leonard Schulman for his assistance in verifying the correctness of some of
the proofs in Section 3.

## References

       * [1] Noga Alon, Jeong-Han Kim, and Joel Spencer, _Nearly perfect matchings in regular simple hypergraphs_ , Israel Journal of Mathematics 100 (1997), 171–187.
       * [2] Laurent Bartholdi, Wade Hann-Caruthers, Maya Josyula, Omer Tamuz, and Leeat Yariv, _Equitable voting rules_ , Working paper, 2019.
       * [3] John Isbell, _Homogeneous games II_ , Proceedings of the American Mathematical Society 11 (1960), 159–161.
       * [4] Jeong Han Kim, Benny Sudakov, and Van Vu, _On the asymmetry of random regular graphs and random graphs_ , Random Structures and Algorithms 21 (2002), 216–224.
       * [5] Michael Krivelevich, Benny Sudakov, Van Vu, and Nicholas Wormald, _Random regular graphs of high degree_ , Random Structures and Algorithms 18 (2001), 346–363.
       * [6] Colin McDiarmid, _On the method of bounded differences_ , Surveys in Combinatorics 141 (1989), 148–188.


# Fed-CPrompt: Contrastive Prompt for Rehearsal-Free Federated Continual
Learning

Gaurav Bagwe  Xiaoyong Yuan  Miao Pan  Lan Zhang

###### Abstract

Federated continual learning (FCL) learns incremental tasks over time from
confidential datasets distributed across clients. This paper focuses on
rehearsal-free FCL, which has severe forgetting issues when learning new tasks
due to the lack of access to historical task data. To address this issue, we
propose Fed-CPrompt based on prompt learning techniques to obtain task-
specific prompts in a communication-efficient way. Fed-CPrompt introduces two
key components, asynchronous prompt learning, and contrastive continual loss,
to handle asynchronous task arrival and heterogeneous data distributions in
FCL, respectively. Extensive experiments demonstrate the effectiveness of Fed-
CPrompt in achieving SOTA rehearsal-free FCL performance.

Federated Continual Learning, Federated learning, Rehearsal-free Continual
Learning, Prompt Learning

##  1 Introduction

Federated learning (FL) has been a popular collaborative machine learning
paradigm enabling multiple clients to learn a shared model without exposing
private client data (McMahan et al., 2017). While successful, existing FL
algorithms are mainly designed for a single task with fixed datasets on
clients (McMahan et al., 2017; Li et al., 2020, 2021), which becomes
ineffective in handling non-stationary data distribution over time. Therefore,
recent efforts have been put into federated continual learning (FCL) to learn
tasks that are presented sequentially. Since the model in continual learning
(CL) may overfit data from the current task and suffer from catastrophic
forgetting (Kirkpatrick et al., 2017), the mainstream research to address the
forgetting issue can be roughly divided into two categories: rehearsal-based
and rehearsal-free FCL.

Although rehearsal-based approaches achieve state-of-the-art (SOTA)
performance by using the rehearsal buffer to store and retrain data from
previous tasks, the buffer size needs to be large enough to effectively
mitigate forgetting (Wang et al., 2022b; Dong et al., 2022), leading to
scalability and data storage constraints in FL. Moreover, many applications do
not allow this buffer due to privacy concerns (Smith et al., 2022b), further
restricting their adoption in practice. Hence, this work focuses on rehearsal-
free FCL. Existing efforts along this line regularize the global model with
knowledge from previous tasks when learning a new task (Shoham et al., 2019;
Yoon et al., 2021; Casado et al., 2022; Usmanova et al., 2021, 2022; Ma et
al., 2022). Unfortunately, they have substantially deteriorated performance
compared to rehearsal-based approaches (Wang et al., 2022b). Moreover,
existing research requires continuously exchanging the entire model to learn
incremental tasks in FCL, leading to significant communication overhead. In
view of these, it is critical to developing innovative rehearsal-free FCL in a
communication-efficient way to address the forgetting issue while maintaining
the model plasticity for new tasks.

Enlightened by the recent advance of prompting techniques (Lester et al.,
2021; Liu et al., 2022; Li & Liang, 2021), in this work, we leverage prompt
learning to achieve the above goal. As one promising transfer learning
approach, prompt learning uses insertable embeddings called prompts to
condition a pre-trained model for downstream tasks. Recent research enables
prompt-based CL by using key-query mechanisms, which achieves SOTA rehearsal-
free performance, even outperforming rehearsal-based CL (Wang et al., 2022b,
a; Smith et al., 2022a). Due to the small size of prompt parameters, the
communication efficiency of FCL is expected to be improved significantly.
However, existing prompt-based CL is designed for centralized datasets, which
becomes ineffective in FL with distributed and confidential datasets. The main
limitation is due to the inherent heterogeneity of distributed clients. On the
one hand, clients may observe heterogeneous data for the same task, leading to
biased learning performance and slow convergence. On the other hand,
incremental tasks may arrive asynchronously on clients, further deteriorating
the overall learning performance. Therefore, to unleash the potential of
prompting for rehearsal-free FCL, we propose Fed-CPrompt to facilitate inter-
task and inter-client prompt-based knowledge transfer while addressing the
heterogeneity concerns of data distribution and task arrival over clients. Our
key contributions are summarized below:

  * •

We propose Fed-CPrompt, an innovative rehearsal-free FCL framework based on
prompting techniques. Fed-CPrompt achieves SOTA FCL performance to handle the
stability-plasticity dilemma under heterogeneous FL environments in a
communication-efficient way.

  * •

We introduce two key components to Fed-CPrompt: asynchronous prompt learning
takes advantage of task asynchronicity to strengthen the task-specific
prompts; C2L loss alleviates inter-task forgetting and inter-client data
heterogeneity via a contrastive and continual loss.

  * •

We conduct extensive experiments to demonstrate the effectiveness of Fed-
CPrompt in various challenging FCL settings, such as heterogeneous data
distribution and asynchronous task arrival.

Figure 1: Overview of Fed-CPrompt. Left: overall system framework. A server
maintains a pool of task-specific prompts to coordinate multiple clients for
FCL. The clients may observe different tasks at the same time. Fed-CPrompt
allows asynchronous prompt learning. Right: zoom in view of client $c$’s local
training for task $\mathcal{T}_{m}$. Since only the trainable parameters
($w_{c}^{\mathcal{T}_{m}}$ and $\phi_{c}^{\mathcal{T}_{m}}$) need to be
exchanged, Fed-CPrompt is a communication-efficient FCL approach.

##  2 Proposed Method

###  2.1 Problem Statement

In a standard FCL setting, a central server coordinates a set of distributed
clients $\mathcal{C}$ to learn incremental tasks
${\mathcal{T}_{1},\ldots,\mathcal{T}_{n}}$ over time. The training data for
each task is distributed to clients and cannot be shared. FCL aims to obtain a
global model parameterized by $\mathbf{w}$ to perform all existing tasks. In
this work, we consider a challenging CL problem, class-incremental CL, where
the task labels are unknown during inference (Dong et al., 2022). Our design
can be easily extended to the task- or domain-incremental FCL problems. The
optimization objective can be written as

$\min_{\mathbf{w}}\sum_{i\in\\{1,\ldots,n\\}}\sum_{c\in\mathcal{C}}\frac{\mathrm{n}_{c}^{\mathcal{T}_{i}}}{\mathrm{n}^{\mathcal{T}_{i}}}\mathcal{L}(\mathcal{D}_{c}^{\mathcal{T}_{i}};\mathbf{w}),$
(1)

where $\mathrm{n}_{c}^{\mathcal{T}_{i}}$ and $\mathrm{n}^{\mathcal{T}_{i}}$
represent the number of training samples from client $c$ and all clients for
task $\mathcal{T}_{i}$, respectively. $\mathcal{D}_{c}^{\mathcal{T}_{i}}$ is
the training dataset of $\mathcal{T}_{i}$ on client $c$.

This objective function uses data from all existing tasks, making it a
rehearsal-based FCL problem. This work focuses on rehearsal-free FCL.
Specifically, each client can only observe the training data of the current
task, i.e., when training on task $\mathcal{T}_{n}$, training data of all
previous tasks are unseen. However, due to the unavailability of historical
task data, training the current task can overwrite previous task information
of the model $\mathbf{w}$ in (1), deteriorating the forgetting issues in CL.
Thus, existing rehearsal-free FCL approaches cannot achieve comparable
performance to rehearsal-based approaches (Wang et al., 2023).

###  2.2 Design Principle

In this work, we aim to accommodate the forgetting issue for rehearsal-free
FCL. Inspired by the success of the prompt-based rehearsal-free CL that
achieves SOTA performance, we intend to implement prompting techniques in our
design. Existing prompt-based CL (Smith et al., 2022a; Wang et al., 2022b, a)
use insertable embeddings, called prompts $p$, to condition a frozen pre-
trained model $\theta$ to perform incremental tasks. Due to the small size of
prompt parameters, a task-specific prompt is created and stored for each task
to avoid overwriting previous knowledge. Here, we refer readers to Appendix A
for more details. While successful, the above prompt-based CL research is
designed for centralized datasets, which becomes ineffective in FL settings.

The main challenge of implementing prompting techniques in FCL is the inherent
heterogeneity of distributed clients. On the one hand, the data heterogeneity
among clients leads to biased local updates and slow convergence. On the other
hand, the sequential tasks may appear asynchronously over clients, further
delaying convergence. Due to the small size of learnable parameters in prompt
learning, it is essential to improve their learning capacity by facilitating
knowledge transfer between tasks and clients. Therefore, we propose Fed-
CPrompt, an innovative prompt-based rehearsal-free FCL framework. As shown in
Figure 1, Fed-CPrompt introduces two key components, asynchronous prompt
learning and contrastive and continual loss, to address the aforementioned
task arrival and data heterogeneity concerns. In the following, we first
introduce these two components and then present the overall training of Fed-
CPrompt.

###  2.3 Asynchronous Prompt Learning

We adopt the existing prompt-based CL approach (CODA-P (Smith et al., 2022a))
on clients to learn incremental tasks based on their local data. In CODA-P,
the prompt for the current task is re-weighted based on previous task
information to refine task-specific representation via attention mechanisms
(see Appendix A). In Fed-CPrompt, when client $c\in\mathcal{C}$ learns task
$\mathcal{T}_{m}$,
${p}^{\mathcal{T}_{m}}_{c}=\sum_{i\in[1,m-1]}\alpha^{\mathcal{T}_{i}}_{s}P^{\mathcal{T}_{i}}_{s}+\alpha^{\mathcal{T}_{m}}_{c}P^{\mathcal{T}_{m}}_{c}$,
where $\alpha^{\mathcal{T}_{i}}_{b}$ and $P^{\mathcal{T}_{i}}_{b}$ are the
$\mathcal{T}_{i}$-specific attention and prompt at the server ($b=s$) and
client $c$ ($b=c$), respectively. The updated client-side
${p}^{\mathcal{T}_{m}}_{c}$ will be uploaded to the server and aggregated
based on classical FL (McMahan et al., 2017) to obtain server-side prompt
${p}^{\mathcal{T}_{m}}_{s}$. However, such naive aggregation becomes
inefficient in asynchronous task arrival. When client $c$ is training task
${\mathcal{T}_{m}}$, the latest task observed by other clients might be task
$\mathcal{T}_{n}$ ($m<n$), and $\mathcal{T}_{n}$ will be observed by client
$c$ later. Hence, to handle this condition, Fed-CPrompt introduces
asynchronous prompt learning.

Instead of waiting for updated prompts of the current task $\mathcal{T}_{n}$
from all clients before aggregation, we allow task-specific prompt aggregation
in parallel. In this way, the previously learned prompt at the server
${p}_{s}^{\mathcal{T}_{m}}$ can be refined by ${p}^{\mathcal{T}_{m}}_{c}$.
Moreover, taking advantage of the task arrival heterogeneity, the training of
${p}^{\mathcal{T}_{m}}_{c}$ becomes

$p_{c}^{\mathcal{T}_{m}}=\sum_{i=1}^{m-1}\alpha^{\mathcal{T}_{i}}_{s}P^{\mathcal{T}_{i}}_{s}+\alpha_{c}^{\mathcal{T}_{m}}P_{c}^{\mathcal{T}_{m}}+\sum_{j={m+1}}^{n}\alpha^{\mathcal{T}_{j}}_{s}P^{\mathcal{T}_{j}}_{s},$
(2)

where the first and the third terms are task knowledge from the server, which
are frozen when training task $\mathcal{T}_{m}$. It should be mentioned that
although the newest task for client $c$ is $\mathcal{T}_{m}$, the asynchronous
task arrival in FCL allows client $c$ to leverage unseen task knowledge to
navigate the local training. By incorporating past and future task
representations, we increase the capacity of prompts to learn task-specific
instructions.

###  2.4 C2Loss: Contrastive and Continual Loss

To address the data heterogeneity issue while alleviating forgetting in FCL,
we introduce a new loss function, contrastive and continual loss (C2Loss), to
regularize local training on clients. The goal of C2Loss is mainly twofold.
First, C2Loss accommodates disagreements between clients due to biased local
training with heterogeneous data distribution. Second, C2Loss enforces
distinct task-specific prompts construction, which facilitates CL to avoid the
forgetting effect. Specifically, when learning task $\mathcal{T}_{m}$ at
communication round $r$, we have the C2Loss on client $c\in\mathcal{C}$ given
by

$\displaystyle\mathcal{L}_{C2L}$
$\displaystyle(P_{c}^{\mathcal{T}_{m}}(r))=\max\big{(}||P_{c}^{\mathcal{T}_{m}}(r)-P^{\mathcal{T}_{m}}_{s}(r-1)||_{2}$
(3) $\displaystyle-\gamma$
$\displaystyle\min\\{||P_{c}^{\mathcal{T}_{m}}(r)-P^{\mathcal{T}_{i}}_{s}||_{2},i\in[1,n],i\neq
m\\}+\alpha,0\big{)},$

where the first term within the $\max()$ calculates the change of the current
prompt compared to that in the previous round. By restricting this change,
C2Loss smooths the local update to achieve the first goal. The second term
within the $\max()$ finds the most similar prompt to the current prompt based
on the distance between the current and all previous prompts. By increasing
this distance, C2Loss enforces the discrimination between task-specific
prompts to achieve the second goal. Besides, $\gamma>0$ is the hyperparameter
to balance the impact between the first two terms. $\alpha\in[0,1]$ represents
a margin value that encourages a separation between the first two terms
(Schroff et al., 2015).

###  2.5 Overall Training

In Fed-CPrompt, client $c\in\mathcal{C}$ conducts local training with dataset
$\mathcal{D}_{c}^{\mathcal{T}_{m}}$ for the current task $\mathcal{T}_{m}$. As
discussed in (2), a prompt is constructed based on attention mechanisms, and
thus the learnable prompt parameter for client $c$ is defined by
$\mathbf{w}_{c}^{\mathcal{T}_{m}}=\\{P_{c}^{\mathcal{T}_{m}},K_{c}^{\mathcal{T}_{m}},A_{c}^{\mathcal{T}_{m}}\\}$
($K$ and $A$ composite the $\alpha$ in (2), detailed in Appendix A). By
incorporating the C2Loss to the cross-entropy loss, we have the local
optimization function of client $c$ by

$\displaystyle\min_{\mathbf{w}_{c}^{\mathcal{T}_{m}},\phi_{c}^{\mathcal{T}_{m}}}\mathcal{L}_{CE}(f_{\phi_{c}}(x;\theta,\mathbf{w}_{c}),y)+\lambda~{}\mathcal{L}_{C2L}(\mathbf{w}_{c}^{\mathcal{T}_{m}}),$
(4)

where $\phi_{c}^{\mathcal{T}_{m}}$ represents the classifier parameter for
task $\mathcal{T}_{m}$. Note that $\mathbf{w}_{c}$ and $\phi_{c}$ concatenate
both the frozen previous task parameter and the current task learnable
parameter as discussed in (2). Besides, $\theta$ is the frozen pretrained
model parameters; $(x,y)\in\mathcal{D}_{c}^{\mathcal{T}_{m}}$;
$\lambda\in[0,1]$ is the hyperparameter balancing losses. Both prompt
parameters $\mathbf{w}_{c}^{\mathcal{T}_{m}}$ and classifier parameters
$\phi_{c}^{\mathcal{T}_{m}}$ will be uploaded to the server. The server
handles asynchronous task arrival by conducting parallel aggregation following
classical FL (McMahan et al., 2017). The overall training is illustrated in
Algorithm 1 of Appendix C.

##  3 Experiments

###  3.1 Experimental Setup

We evaluate the proposed Fed-CPrompt based on the CIFAR-100 dataset
(Krizhevsky et al., 2009), a widely used dataset in continual learning for
classification tasks. We consider a total of 10 clients in FCL. The server-
side knowledge aggregation is based on FedAvg (McMahan et al., 2017). The
evaluation metrics include average accuracy and average forgetting, which are
standard metrics used in previous CL research (Wang et al., 2023; Huang et
al., 2022). To comprehensively evaluate Fed-CPrompt, we consider baseline
approaches, including rehearsal-free FL approaches (i.e., Fed-EWC and Fed-LWF)
and recent prompt-based CL approaches (i.e., Fed-CODAP, Fed-DualP, Fed-L2P).
Further details on the dataset setup, FL settings, evaluation metrics, and
baseline approaches can be found in Appendix D.

###  3.2 Experimental Results

Table 1: Performance comparison of rehearsal-free FCL methods under iid settings. Model | Accuracy | Forgetting
---|---|---
Fed-EWC | 9.79 | 84.85
Fed-LwF | 60.92 | 33.75
Fed-L2P | 73.19 | 9.80
Fed-DualP | 76.00 | 9.84
Fed-CODAP | 77.28 | 6.42
Fed-CPrompt | 79.43 | 4.75
Table 2: Performance comparison of prompt-based FCL methods under different non-iid settings (label and quantity skew).  | Model | Accuracy | Forgetting
---|---|---|---
Label Skew | Fed-DualP | 46.28 | 13.16
Fed-CODAP | 54.80 | 11.55
Fed-CPrompt | 65.45 | 9.15
Quantity Skew | Fed-DualP | 77.57 | 8.38
Fed-CODAP | 78.56 | 5.00
Fed-CPrompt | 81.12 | 7.75

Effectiveness of Fed-CPrompt. We evaluate the effectiveness of Fed-CPrompt
under iid and non-iid FL settings. We report the average test accuracy and
forgetting over all ten tasks. As illustrated in Table 1, Fed-CPrompt gains a
significant performance improvement over all rehearsal-free FCL methods under
iid settings. Compared with the best of existing works, Fed-CPrompt achieves
around a 2% increase in Top-1 accuracy and around a 2% drop in Forgetting. It
should be mentioned that non-prompt-based methods (Fed-EWC and Fed-LwF)
optimize about 86 million parameters, while Fed-CPrompt optimizes only 4
million $(\approx 4.18\%)$ to achieve better performance. Moreover, Fed-
CPrompt has better convergence, which significantly reduces the communication
cost for FCL.

Besides, we further compare the Fed-CPrompt with other prompt-based FCL
baselines under non-iid settings. In the experiments following (Li et al.,
2020), we consider two non-iid settings: label skew and quantity skew. As
illustrated in Table 2, Fed-CPrompt outperforms the existing prompt-based
methods under non-iid settings. In particular, under a challenging label-skew
setting, Fed-CPrompt achieves a significant performance improvement by
$10.65\%$.

Impact of Asynchronous Continual Learning Tasks. We demonstrate the
effectiveness of Fed-CPrompt under asynchronous task arrival, where the
clients train the models on different tasks at the same time. As illustrated
in Table 3, the average test accuracy of Fed-CPrompt significantly outperforms
the existing methods by $2.07\%$ and $11.79\%$ under iid and non-iid settings,
respectively. Our findings suggest jointly considering past and future task
information can improve the training efficiency of FCL. It should be noted
that the forgetting of Fed-CPrompt is comparable to or higher than the
existing works; however this is due to the high accuracy gained by Fed-CPrompt
on the first task. Besides the impact of high accuracy on the first task, we
can still observe the substantial advantage of Fed-CPrompt in mitigating
catastrophic forgetting, as the average accuracy on all ten tasks achieved by
Fed-CPrompt is much higher than the existing works.

Impact of C2Loss. We further perform ablation studies to evaluate the
effectiveness of the proposed C2Loss. We compare the performance between
FedProx and Fed-CPrompt with and without C2Loss. As shown in Table 4, Fed-
CPrompt with C2Loss achieves the highest accuracy and lowest forgetting
compared with the rest two methods. This is mainly due to that C2Loss handles
inter-task and inter-client knowledge transfer, thereby leading to better task
discrimination and improved accuracy.

Table 3: Performance comparison of asynchronous continual learning under iid and non-iid (label skew) settings. Model | Accuracy | Forgetting
---|---|---
iid | Fed-DualP | 70.27 | 17.36
Fed-CODAP | 73.63 | 10.94
Fed-CPrompt | 75.70 | 9.82
non-iid | Fed-DualP | 46.80 |  3.89
Fed-CODAP | 50.81 | 8.05
Fed-CPrompt | 62.60 | 10.55
Table 4:  Impact of C2Loss under the non-iid (label skew) setting. Model | Accuracy | Forgetting
---|---|---
$\mathcal{L}_{CE}$ w/ FedProx | 50.81 | 9.16
$\mathcal{L}_{CE}$ w/o $\mathcal{L}_{C2L}$ | 71.30 | 13.52
$\mathcal{L}_{CE}$ w/ $\mathcal{L}_{C2L}$ | 79.30 | 4.50

##  4 Conclusion

This paper proposed Fed-CPrompt, an innovative rehearsal-free FCL framework to
alleviate catastrophic forgetting over incremental tasks and facilitate
knowledge transfer among distributed and heterogeneous clients. Fed-CPrompt
introduces two key components: asynchronous prompt learning to handle
asynchronous arrival, and a simple yet effective contrastive continual loss
that optimizes prompt parameters while providing additional supervision for
learning distinct task-specific prompts. Extensive experiments demonstrate the
effectiveness of our proposal.

## References

  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Casado et al. (2022) Casado, F. E., Lema, D., Criado, M. F., Iglesias, R., Regueiro, C. V., and Barro, S.  Concept drift detection and adaptation for federated and continual learning.  _Multimedia Tools and Applications_ , pp. 1–23, 2022.
  * Dong et al. (2022) Dong, J., Wang, L., Fang, Z., Sun, G., Xu, S., Wang, X., and Zhu, Q.  Federated class-incremental learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10164–10173, 2022.
  * Guo et al. (2022) Guo, T., Guo, S., Wang, J., and Xu, W.  Promptfl: Let federated participants cooperatively learn prompts instead of models–federated learning in age of foundation model.  _arXiv preprint arXiv:2208.11625_ , 2022.
  * Huang et al. (2022) Huang, W., Ye, M., and Du, B.  Learn from others and be yourself in heterogeneous federated learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10143–10153, 2022.
  * Jiang et al. (2020) Jiang, Z., Xu, F. F., Araki, J., and Neubig, G.  How can we know what language models know?  _Transactions of the Association for Computational Linguistics_ , 8:423–438, 2020.
  * Kirkpatrick et al. (2017) Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., Milan, K., Quan, J., Ramalho, T., Grabska-Barwinska, A., et al.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the national academy of sciences_ , 114(13):3521–3526, 2017.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lester et al. (2021) Lester, B., Al-Rfou, R., and Constant, N.  The power of scale for parameter-efficient prompt tuning.  _arXiv preprint arXiv:2104.08691_ , 2021.
  * Li et al. (2021) Li, Q., He, B., and Song, D.  Model-contrastive federated learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10713–10722, 2021.
  * Li et al. (2022) 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)_ , pp. 965–978. IEEE, 2022.
  * Li et al. (2020) Li, T., Sahu, A. K., Talwalkar, A., and Smith, V.  Federated learning: Challenges, methods, and future directions.  _IEEE signal processing magazine_ , 37(3):50–60, 2020.
  * Li et al. (2019) Li, X., Zhou, Y., Wu, T., Socher, R., and Xiong, C.  Learn to grow: A continual structure learning framework for overcoming catastrophic forgetting.  In _International Conference on Machine Learning_ , pp. 3925–3934. PMLR, 2019.
  * Li & Liang (2021) Li, X. L. and Liang, P.  Prefix-tuning: Optimizing continuous prompts for generation.  _arXiv preprint arXiv:2101.00190_ , 2021.
  * Liu et al. (2022) Liu, X., Ji, K., Fu, Y., Tam, W., Du, Z., Yang, Z., and Tang, J.  P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pp. 61–68, 2022.
  * Ma et al. (2022) Ma, Y., Xie, Z., Wang, J., Chen, K., and Shou, L.  Continual federated learning based on knowledge distillation.  In Raedt, L. D. (ed.), _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_ , pp. 2182–2188. International Joint Conferences on Artificial Intelligence Organization, 7 2022.  doi: 10.24963/ijcai.2022/303.  URL https://doi.org/10.24963/ijcai.2022/303.  Main Track.
  * McMahan et al. (2017) 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_ , pp. 1273–1282. PMLR, 2017.
  * Rusu et al. (2016) Rusu, A. A., Rabinowitz, N. C., Desjardins, G., Soyer, H., Kirkpatrick, J., Kavukcuoglu, K., Pascanu, R., and Hadsell, R.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_ , 2016.
  * Schroff et al. (2015) Schroff, F., Kalenichenko, D., and Philbin, J.  Facenet: A unified embedding for face recognition and clustering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 815–823, 2015.
  * Shenaj et al. (2023) Shenaj, D., Toldo, M., Rigon, A., and Zanuttigh, P.  Asynchronous federated continual learning.  _arXiv preprint arXiv:2304.03626_ , 2023.
  * Shin et al. (2020) Shin, T., Razeghi, Y., Logan IV, R. L., Wallace, E., and Singh, S.  Autoprompt: Eliciting knowledge from language models with automatically generated prompts.  _arXiv preprint arXiv:2010.15980_ , 2020.
  * Shoham et al. (2019) Shoham, N., Avidor, T., Keren, A., Israel, N., Benditkis, D., Mor-Yosef, L., and Zeitak, I.  Overcoming forgetting in federated learning on non-iid data.  _arXiv preprint arXiv:1910.07796_ , 2019.
  * Smith et al. (2022a) Smith, J. S., Karlinsky, L., Gutta, V., Cascante-Bonilla, P., Kim, D., Arbelle, A., Panda, R., Feris, R., and Kira, Z.  Coda-prompt: Continual decomposed attention-based prompting for rehearsal-free continual learning.  _arXiv preprint arXiv:2211.13218_ , 2022a.
  * Smith et al. (2022b) Smith, J. S., Tian, J., Hsu, Y.-C., and Kira, Z.  A closer look at rehearsal-free continual learning.  _arXiv preprint arXiv:2203.17269_ , 2022b.
  * Usmanova et al. (2021) Usmanova, A., Portet, F., Lalanda, P., and Vega, G.  A distillation-based approach integrating continual learning and federated learning for pervasive services.  _arXiv preprint arXiv:2109.04197_ , 2021.
  * Usmanova et al. (2022) Usmanova, A., Portet, F., Lalanda, P., and Vega, G.  Federated continual learning through distillation in pervasive computing.  In _2022 IEEE International Conference on Smart Computing (SMARTCOMP)_ , pp. 86–91. IEEE, 2022.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2022a) Wang, Z., Zhang, Z., Ebrahimi, S., Sun, R., Zhang, H., Lee, C.-Y., Ren, X., Su, G., Perot, V., Dy, J., and Pfister, T.  Dualprompt: Complementary prompting for rehearsal-free continual learning.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXVI_ , pp. 631–648. Springer, 2022a.
  * Wang et al. (2022b) Wang, Z., Zhang, Z., Lee, C.-Y., Zhang, H., Sun, R., Ren, X., Su, G., Perot, V., Dy, J., and Pfister, T.  Learning to prompt for continual learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 139–149, 2022b.
  * Wang et al. (2023) Wang, Z., Zhang, Y., Xu, X., Fu, Z., Yang, H., and Du, W.  Federated probability memory recall for federated continual learning.  _Information Sciences_ , 2023.
  * Yoon et al. (2021) Yoon, J., Jeong, W., Lee, G., Yang, E., and Hwang, S. J.  Federated continual learning with weighted inter-client transfer.  In _International Conference on Machine Learning_ , pp. 12073–12086. PMLR, 2021.
  * Zhao et al. (2022) Zhao, H., Du, W., Li, F., Li, P., and Liu, G.  Reduce communication costs and preserve privacy: Prompt tuning method in federated learning.  _arXiv preprint arXiv:2208.12268_ , 2022.
  * Zizzo et al. (2022) Zizzo, G., Rawat, A., Holohan, N., and Tirupathi, S.  Federated continual learning with differentially private data sharing.  In _Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022)_ , 2022.

##  Appendix A Preliminaries for Prompt-based Continual Learning

In this work, we build upon the technical foundations of prompt-based methods
from the prior centralized continual learning research (Smith et al., 2022a;
Wang et al., 2022a, b) to introduce prompts, which can collaboratively learn
in heterogeneous federated settings. As done in CODA-P, prompt parameters are
attached to several multi-head self-attention (MSA) layers in a pre-trained
ViT. Define a task-specific prompt parameter for task $\mathcal{T}_{m}$ as
$P^{\mathcal{T}_{m}}\in\mathbb{R}^{L_{P}\times D\times\mathcal{T}_{m}}$, where
$L_{P}$, $D$, and ${\mathcal{T}_{m}}$ are the prompt lengths, embedding
dimension, and the number of prompts for each task, respectively. We consider
prefix-tuning to attach prompts to the keys and values of an MSA layer with
input $h\in\mathbb{R}^{L\times D}$ and the query, key, and value as
$h_{Q},h_{K}$, and $h_{V}$. A prompt $p$ is split into
$\\{P_{K},P_{V}\\}\in\mathbb{R}^{\frac{L_{p}}{2}\times D}$, which are
respectively attached to the key and the value of this layer, i.e.,
$MSA(h_{Q},[P_{K};h_{K}],[P_{V};h_{V}])$. where $[\cdot;\cdot]$ is a
concatenation operation. Since CODA-P achieves SOTA centralized continual
learning performance, we adopt the weighted prompt for local training, and the
prompt for task $\mathcal{T}_{m}$ can be calculated by

${p}^{\mathcal{T}_{m}}=\sum_{i\in[1,m]}\alpha^{\mathcal{T}_{i}}P^{\mathcal{T}_{i}},$
(5)

where $P^{\mathcal{T}_{m}}$ is a learnable prompt to the current task
$\mathcal{T}_{m}$, $\alpha^{\mathcal{T}_{m}}=\gamma(q(x)\odot
A^{\mathcal{T}_{m}},K^{\mathcal{T}_{m}})$ measures the cosine similarity
$\gamma$ between the attended query and the key, where the attended query
defined by the element-wise product $\odot$ between query and learnable
attention parameter. The query is produced as
$q(x)\in\mathbb{R}^{D}=f(x;{\theta})$, where $f(\cdot;{\theta})$ is the
encoder of the pre-trained ViT111We refer the reader to sections 4.1 and 4.2
of the CODA-p (Smith et al., 2022a) paper for more details.. For training task
$\mathcal{T}_{m}$, the learnable parameters include $P^{\mathcal{T}_{m}}$,
$K^{\mathcal{T}_{m}}$, $A^{\mathcal{T}_{m}}$, and the classification head
$\phi^{\mathcal{T}_{m}}$, whereas
$(\alpha^{\mathcal{T}_{i}},P^{\mathcal{T}_{i}})~{}\forall i\in[1,m-1]$ is
frozen but contributes to the training as in Equation (5). In addition, the
classification head of the previous task
$\mathcal{T}_{1},\cdots,\mathcal{T}_{m-1}$ , i.e are frozen.

##  Appendix B Related Work

Federated Continual Learning (FCL). FCL performs addresses catastrophic
forgetting across multiple clients trained on their private sequential tasks,
where a global model is obtained by exchanging task-specific knowledge via a
global server. The mainstream FCL research can be roughly divided into two
categories: rehearsal-based and rehearsal-free FCL. The rehearsal-based
research stores and replays information from previous tasks to mitigate the
global model’s forgetting over time (Dong et al., 2022; Huang et al., 2022;
Zizzo et al., 2022; Wang et al., 2023). For example, Huang et al. proposed
FCCL to address the heterogeneity and catastrophic forgetting in federated
learning based on buffered data for intra- and inter-domain knowledge
distillation (Huang et al., 2022). Similarly, Zizzo et al. and Wang et al.
leveraged replay buffers and novel data-sharing approaches based on
differential privacy to mitigate forgetting (Zizzo et al., 2022; Wang et al.,
2023). To tackle the global model’s forgetting brought by heterogeneous
clients, Dong et al. introduced a proxy server to store and select the best
old models to assist clients’ local training (Dong et al., 2022). While
successful, the above rehearsal-based FCL research requires large storage
space and complex data-sharing strategies to replay past information, making
it challenging to scale over time.

Another category of FCL research is rehearsal-free approaches without storing
past information. One group of rehearsal-free continual learning (CL) expands
the model architecture when encountering new tasks (Rusu et al., 2016; Li et
al., 2019). However, most architecture-based approaches require task identity
to condition the network during inference, leading to their ineffectiveness
for class-incremental or task-agnostic CL scenarios, i.e., the task identity
is unknown. In this work, we focus on the practical but more challenging
class-incremental FCL in a rehearsal-free manner. Existing FCL research along
this line proposed regularizing the model with respect to the previous task
knowledge when training a new task. For example, Shoham et al. and Yoon et al.
leveraged the weight consolidation method to restrict the updates of the
important parameters regarding previous tasks while improving the training
performance for the new task (Shoham et al., 2019; Yoon et al., 2021).
Similarly, several recent works implemented knowledge distillation methods to
transfer knowledge from the model for the old task to that for the current
task (Casado et al., 2022; Usmanova et al., 2021, 2022; Ma et al., 2022). In
addition, (Shenaj et al., 2023) investigates the asynchronous-task FCL while
using representation loss and a modified aggregation strategy to address the
forgetting across multiple clients asynchronously learning respective tasks.
While the aforementioned research enables class-incremental FCL without the
rehearsal buffer, they rely on optimizing the entire model on the client side,
leading to heavy communication overhead when iteratively exchanging
distributed client knowledge in FL, especially for CL scenarios. To address
the limitations of existing research, in this work, we propose a novel
rehearsal-free FCL approach for class-incremental learning problems based on
prompt learning techniques.

Prompt Learning. Prompt learning has been a popular transfer learning approach
that modifies the input sample with input embedding called prompts, aiming to
provide additional information to condition the model to perform downstream
tasks (Brown et al., 2020; Jiang et al., 2020; Shin et al., 2020). However,
designing the prompt function for various downstream tasks is challenging.
Recent research has introduced ”soft prompts” to automatically train the
learnable prompt parameters to replace the heuristic manual selection, such as
the prompt tuning, p-tuning, and prefix tuning (Lester et al., 2021; Liu et
al., 2022; Li & Liang, 2021). Prompt learning has shown great potential for
parameter-efficient transfer learning with a small set of prompt parameters.
Taking advantage of the small parameter size, Zhao et al. (Zhao et al., 2022)
and Guo et al. (Guo et al., 2022) adopted prompt learning to improve federated
learning efficiency.

Some recent works have implemented prompt learning techniques in CL. Wang et
al. proposed L2P by using the key-query-based similarity method to select
prompts from a prompt pool to instruct different tasks in CL (Wang et al.,
2022b). Later, DualPrompt was introduced as the follow-up to L2P with better
CL performance, which learns two sets of disjoint prompt spaces to encode
task-specific and task-invariant instructions, respectively (Wang et al.,
2022a). More recently, CODA-Prompt was proposed using an attention-based end-
to-end key-query method, which produces the input-conditioned prompts to
further improve CL performance (Smith et al., 2022a). Nevertheless, the above
prompt-based CL approaches designed for centralized datasets cannot be
directly used for federated learning scenarios, as they ignore the unique
challenges raised by distributed nature of clients, such as the heterogeneous
data distribution and asynchronous task arrival over clients. To the best of
our knowledge, none of the existing prompt learning research has been done for
FCL.

##  Appendix C Algorithm

The overall training process includes four main steps (a-d) as shown in
Algorithm 1. (a) The server distributes the prompts and model to each new
participating device. (b) Each user first freezes the previous prompt
parameters. (c) Each user optimizes the local prompt parameters and classifier
head following CE loss and Equation (3). (d) The clients return the locally
trained model to the server. Further, the server aggregates the model
following classical FedAvg (McMahan et al., 2017). Algorithm 1 follows steps
(a) - (d) until convergence.

Algorithm 1 Fed-CPrompt

Input: Set of $\mathcal{C}$ clients, $R$ communication rounds, total tasks
$\mathcal{T}$, trainable parameters
$\mathbf{w}_{s}=\\{P_{s},A_{s},K_{s}\\},\phi_{s}$, frozen pretrained large
model parameters $\theta$, local epochs $E$, learning rate $\eta$

Output: $\mathbf{w},\phi$

1: Server executes:

2: Send the pretrained model $\phi,\theta,\mathbf{w}_{s}$ parameters to
clients. (a)

3: for $r\in\\{1,\cdots,R\\}$ do

4: for each client $c\in\mathcal{C}$ do

5: $\mathbf{w}_{c}\leftarrow\ \mathbf{w}_{s}$

6: $\phi_{c}\leftarrow\phi_{s}$

7: $\mathbf{w_{c}},\phi_{c}\leftarrow$ Client
Update($\mathbf{w_{c}},\phi_{c}$)

8: end for

9: Aggregate $\mathbf{w}_{c}^{\mathcal{T}_{m}}$ and
$\phi_{c}^{\mathcal{T}_{m}}$ using FedAvg (d)

10: end for

11: return $\theta_{r+1}$

1: Client Update $(\mathbf{w_{c}},\phi)$:

2: for $i\in[1,n]$ do

3: if $m\neq n$ then

4: Freeze $w_{c}^{\mathcal{T}_{i}},\phi_{c}^{\mathcal{T}_{i}}$ (b)

5: end if

6: end for

7: for $e\in E$ do

8: $\mathcal{L}_{CE}\leftarrow$ Calculate cross entropy loss
$\mathcal{L}_{CE}$

9: $\mathcal{L}_{C2L}\leftarrow$ Calculate C2Loss using (3)

10: Update $\mathbf{w}_{c}^{\mathcal{T}_{m}},\phi_{c}^{\mathcal{T}_{m}}$ (c)

11: end for

12: return $\mathbf{w}_{c}^{\mathcal{T}_{m}},\phi_{c}^{\mathcal{T}_{m}}$

##  Appendix D Implementation details

In this section, we conduct extensive experiments to evaluate the proposed
Fed-CPrompt. We first introduce the experimental setup, followed by the
experimental results. Additionally, the same random seed is used to conduct
all experiments for reproducibility.

###  D.1 Dataset Setup.

The CIFAR-100 dataset consists of $100$ classes with $600$ samples per class.
In the experiments, we divide the dataset into $10$ disjoint tasks with $10$
classes per task ($5,000$ training samples per task). We divide the samples on
each task among clients following a uniform distribution for the iid settings
in federated learning. We implement label-based and quantity-based
distribution skew (i.e., label skew and quantity skew) for non-iid settings
with non-iid degree $\beta=0.5$ following (Li et al., 2022). The test dataset
consists of $10,000$ samples, with $1,000$ samples per task.

###  D.2 Federated Learning Settings.

The learning rate is set to $lr=0.0001$. We also deploy an early-stopping
mechanism in each task using a validation set. We consider $\mathcal{C}=10$
clients, $R=40$ communication rounds, and local epochs $l_{epochs}=5$. The
network parameters are optimized using Adam optimizer and a batch size of
$128$ images. We split the CIFAR100 dataset into $10$ tasks, each with $10$
classes. This is distributed among the $10$ clients following § D.1.

###  D.3 Asynchronous Tasks.

We consider an asynchronous scenario where different clients learn from
different tasks at the same time. Specifically, we select a random set of 5
clients to participate in the following task
$\mathcal{T}_{n}=\mathcal{T}_{m+1}$, while the remaining 5 clients remain on
task $\mathcal{T}_{m}$.

###  D.4 Baseline Approaches.

We compare our proposed Fed-CPrompt with CODA-Prompt (Smith et al., 2022a),
Dual prompt (Wang et al., 2022a), L2P (Wang et al., 2022b) applied to
federated settings. These prompt-based methods have shown potential parameter-
efficient SOTA solutions in continual learning. Additionally, we consider
conventional non-prompt-based rehearsal-free methods to demonstrate the
advantages of prompt-based methods. Specifically, Fed-EWC (Shoham et al.,
2019) and Fed-LWF (Usmanova et al., 2022) provide a fair representation of
conventional non-prompt-based rehearsal-free methods in continual learning
(Yoon et al., 2021; Casado et al., 2022; Usmanova et al., 2021). This
comparison allows us to show the potential of a prompt-based approach to other
rehearsal-free methods. The same set of hyper-parameters, such as the learning
rate, batch size, and number of rounds is adopted in the baselines and our
proposed Fed-CPrompt.

###  D.5 Prompt parameters.

We use prefix-tuning (Li & Liang, 2021) to attach the prompts to layers (1-5)
of the pretrained ViT network (Vaswani et al., 2017). The total prompt size is
$n=100$, and $10$ prompts per task. Each prompt is set with length $L_{p}=8$
and embedding dimension $D=768$.

###  D.6 Evaluation metrics.

We evaluate our model on the standard continual learning metrics, including
average accuracy and average forgetting, which are widely used in previous
works (Li & Liang, 2021; Usmanova et al., 2022; Wang et al., 2023). We follow
the standard definition of accuracy and forgetting mentioned in (Smith et al.,
2022a).

##  Appendix E Additional Results

Training Efficiency. Figure 2(a) and Figure 2(b) demonstrate the effect of
catastrophic forgetting when training new incremental tasks. Overall, we
observe that in Fed-CPrompt retains knowledge from previous tasks, mitigating
the catastrophic forgetting issues. Additionally, the accuracy per task is
higher due to the increased capacity of prompts compared to prompts used in
Dual Prompt and L2P. Overall, our findings suggest that prompt-based
algorithms, especially Fed-CPrompt, can effectively mitigate the problem of
catastrophic forgetting and improve the training efficiency of lifelong
learning systems.

(a) Total Test Accuracy.

(b) Overall Forgetting.

Figure 2: Total test accuracy and forgetting of the global model after
training each incremental task in standard iid settings. Note that the total
test accuracy is the average test accuracy of the current task and all the
previous tasks.

(a) Total Test Accuracy.

(b) Forgetting.

Figure 3: Total test accuracy and forgetting after training each incremental
task on non-iid (label-skew). Figure 4: Test accuracy of the prompt-based
methods at each round of federated training.  Figure 5: Test accuracy of first
5 tasks in synchronous (sync) and asynchronous (async) iid settings. Under
asynchronous settings, prompts in our approach leverage information from other
tasks, thus increasing the convergence speed and better initialization.

Impact of Asynchronous Continual Learning Tasks. To investigate the impact of
client pacing on the training efficiency of our lifelong learning system, we
conduct experiments with varying degrees of client pacing. Specifically, we
compare the system’s performance when all clients move to the next task
simultaneously versus when some clients move to the next task while others are
still at the current task. Our results show that when some clients move to the
next task, the knowledge of the next task can benefit the current task prompt
by providing additional context and improving the convergence speed (Figure
5). The model can leverage the knowledge learned from the next task to
understand the current task better, leading to faster convergence and improved
accuracy.

Moreover, we also explore the idea of leveraging the prompts from other tasks
for example in our design, the clients on task $\mathcal{T}_{m+1}$ leverage
prompts from task $\mathcal{T}_{m}$ to improve the convergence speed of the
current task. In addition, clients on task $\mathcal{T_{m}}$ have an increased
capacity due to the additional prompt from task $\mathcal{T}_{m+1}$. Our
experiments show that incorporating prompts from previous tasks into the
current task prompt can significantly improve the convergence speed and reduce
the training time, as shown in Figure 5. This is because the model can reuse
the knowledge learned from previous tasks and incorporate it into the current
task prompt to improve its understanding of the new task.