Let $f_{1}$ and $f_{2}$ be both subanalytic functions, then the sum of $f_{1}$
and $f_{2}$, i.e., $f_{1}+f_{2}$ is a subanalytic function if at least one of
them map a bounded set to a bounded set or if both of them are nonnegative.

######  Lemma 8 (Property of subanalytic functions [12]).

Let $h:\mathbb{R}^{p}\to\mathbb{R}\cup\\{+\infty\\}$ be a subanalytic function
with closed domain, and assume that $h$ is continuous on its domain, then $h$
is a KŁ function.

######  Proposition 6 (KŁ property of $\mathcal{L}$).

Suppose that Assumption 1 holds, then the Lagrangian function $\mathcal{L}$
defined in (10) is a KŁ function.

###### Proof.

From (10), we have

$\begin{split}\mathcal{L}(\Theta,W,\Pi,\boldsymbol{w})&:=\sum_{i=1}^{m}\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{w},\boldsymbol{\pi}_{i}),\\\
\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{\pi}_{i},\boldsymbol{w})&:=\alpha_{i}(f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}\|\boldsymbol{\theta}_{i}\\!-\boldsymbol{w}_{i}\|^{2})+\langle\boldsymbol{\pi}_{i},\boldsymbol{w}_{i}-\boldsymbol{w}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}-\boldsymbol{w}\|^{2},\end{split}$
(42)

which mainly includes the following types of functions, i.e.,

$\displaystyle
f_{i}(\boldsymbol{\theta}_{i}),\,\|\boldsymbol{\theta}_{i}\\!-\boldsymbol{w}_{i}\|^{2},\,\langle\boldsymbol{\pi}_{i},\boldsymbol{w}_{i}-\boldsymbol{w}\rangle,\,\|\boldsymbol{w}_{i}-\boldsymbol{w}\|^{2}.$

Following from Assumption 1, we have $f_{i}(\boldsymbol{\theta}_{i})$ is
either real analytic or semialgebraic. Note that
$\|\boldsymbol{\theta}_{i}\\!-\boldsymbol{w}_{i}\|^{2},\,\langle\boldsymbol{\pi}_{i},\boldsymbol{w}_{i}-\boldsymbol{w}\rangle,\,\|\boldsymbol{w}_{i}-\boldsymbol{w}\|^{2}$
are all polynomial functions with variables
$\boldsymbol{\theta}_{i},\,\boldsymbol{w}_{i},\boldsymbol{\pi}_{i},$ and
$\boldsymbol{w}$, thus according to [41] and [11], they are both real analytic
and semialgebraic. Since each term of $\mathcal{L}$ is either real analytic or
semialgebraic, then according to Lemma 7, $\mathcal{L}$ is a subanalytic
function. Next, we can infer that $\mathcal{L}$ is a KŁ function according to
Lemma 8. ∎

###  A-C Proof of Lemma 1

###### Proof.

We decompose the gap between $\mathcal{L}^{t+1}$ and $\mathcal{L}^{t}$ as

$\displaystyle\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{t})$
$\displaystyle=\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t+1},\boldsymbol{w}^{t+1})-\mathcal{L}(\Theta^{t},W^{t},\Pi^{t},\boldsymbol{w}^{t})$
$\displaystyle=\underbrace{\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t+1},\boldsymbol{w}^{t+1})\\!-\\!\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t+1},\boldsymbol{w}^{t})}_{e_{1}^{t}}+\underbrace{\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t+1},\boldsymbol{w}^{t})\\!-\\!\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t},\boldsymbol{w}^{t})}_{e_{2}^{t}}$
$\displaystyle\quad+\underbrace{\mathcal{L}(\Theta^{t+1},W^{t+1},\Pi^{t},\boldsymbol{w}^{t})\\!-\\!\mathcal{L}(\Theta^{t+1},W^{t},\Pi^{t},\boldsymbol{w}^{t})}_{e_{3}^{t}}+\underbrace{\mathcal{L}(\Theta^{t+1},W^{t},\Pi^{t},\boldsymbol{w}^{t})\\!-\\!\mathcal{L}(\Theta^{t},W^{t},\Pi^{t},\boldsymbol{w}^{t})}_{e_{4}^{t}}.$
(43)

Next, we individually estimate $e_{1}^{t}$, $e_{2}^{t}$, $e_{3}^{t}$, and
$e_{4}^{t}$.

Estimate of $e_{1}^{t}$. By employing the Lagrangian function, we can deduce
the subsequent expression:

$\displaystyle e_{1}^{t}$
$\displaystyle=\sum_{i=1}^{m}\langle\boldsymbol{\pi}_{i}^{t+1},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t+1}\rangle-\langle\boldsymbol{\pi}_{i}^{t+1},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t+1}\|^{2}-\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\|^{2}$
$\displaystyle=\sum_{i=1}^{m}\langle\boldsymbol{\pi}_{i}^{t+1}+\rho\boldsymbol{w}_{i}^{t+1}-\frac{\rho}{2}(\boldsymbol{w}^{t}+\boldsymbol{w}^{t+1}),\boldsymbol{w}^{t}-\boldsymbol{w}^{t+1}\rangle$
(44) $\displaystyle=-\frac{\rho
m}{2}\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2},$ (45)

where (45) follows from Equation (14).

Estimate of $e_{2}^{t}$. Utilizing the Lagrangian function, we obtain

$\displaystyle e_{2}^{t}$
$\displaystyle=\sum_{i=1}^{m}\langle\boldsymbol{\pi}^{t+1}_{i}-\boldsymbol{\pi}^{t}_{i},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\rangle$
$\displaystyle=\underbrace{\sum_{i\notin\mathcal{S}^{t}}\langle\boldsymbol{\pi}^{t+1}_{i}-\boldsymbol{\pi}^{t}_{i},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\rangle}_{=0}+\sum_{i\in\mathcal{S}^{t}}\langle\boldsymbol{\pi}^{t+1}_{i}-\boldsymbol{\pi}^{t}_{i},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\rangle$
(46)
$\displaystyle=\sum_{i\in\mathcal{S}^{t}}\frac{1}{\rho}\|\boldsymbol{\pi}^{t+1}_{i}-\boldsymbol{\pi}^{t}_{i}\|^{2}$
(47)
$\displaystyle=\sum_{i\in\mathcal{S}^{t}}\frac{\lambda^{2}\alpha_{i}^{2}}{\rho}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}+\boldsymbol{w}^{t}_{i}\|^{2}$
(48)
$\displaystyle\leq\sum_{i\in\mathcal{S}^{t}}\frac{\lambda^{2}\alpha_{i}^{2}(1+\rho)}{\rho}(\|\boldsymbol{\theta}_{i}^{t+1}\\!-\\!\boldsymbol{\theta}_{i}^{t}\|^{2}\\!+\\!\frac{1}{\rho}\|\boldsymbol{w}_{i}^{t+1}\\!-\\!\boldsymbol{w}^{t}_{i}\|^{2}),$
(49)

where (46) follows from Line 1 in Algorithm 1, (47) follows from (13), (48)
follows from Lemma 3, and (49) follows from Proposition 5.

Estimate of $e_{3}^{t}$. By employing the Lagrangian function, we obtain

$\displaystyle e_{3}^{t}$
$\displaystyle=\sum_{i=1}^{m}\frac{\lambda\alpha_{i}}{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t+1}\|^{2}-\frac{\lambda\alpha_{i}}{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}+\langle\boldsymbol{\pi}_{i}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\rangle-\langle\boldsymbol{\pi}_{i}^{t},\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\|^{2}-\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}$
$\displaystyle=\sum_{i=1}^{m}\frac{\lambda\alpha_{i}}{2}\langle
2\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1},\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\rangle+\langle\boldsymbol{\pi}_{i}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\rangle+\frac{\rho}{2}\langle\boldsymbol{w}_{i}^{t+1}+\boldsymbol{w}_{i}^{t}-2\boldsymbol{w}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\rangle$
(50)
$\displaystyle=\sum_{i\in\mathcal{S}^{t}}\langle\frac{\lambda\alpha_{i}+\rho}{2}(\boldsymbol{w}_{i}^{t+1}+\boldsymbol{w}_{i}^{t})-\lambda\alpha_{i}\boldsymbol{\theta}_{i}^{t+1}+\boldsymbol{\pi}_{i}^{t}-\rho\boldsymbol{w}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\rangle$
(51)
$\displaystyle=\sum_{i\in\mathcal{S}^{t}}\\!\langle\frac{\lambda\alpha_{i}+\rho}{2}(\boldsymbol{w}_{i}^{t+1}\\!+\\!\boldsymbol{w}_{i}^{t})-(\lambda\alpha_{i}+\rho)\boldsymbol{w}_{i}^{t+1},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\rangle$
(52)
$\displaystyle=-\sum_{i\in\mathcal{S}^{t}}\frac{\lambda\alpha_{i}+\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}.$
(53)

where (51) follows from Line 1 in Algorithm 1, (52) follows from Equation
(12).

Estimate of $e_{4}^{t}$. By employing the Lagrangian function, we obtain

$\displaystyle e_{4}^{t}$
$\displaystyle=\\!\sum_{i=1}^{m}\\!\alpha_{i}(f_{i}(\boldsymbol{\theta}_{i}^{t+1})\\!+\\!\frac{\lambda}{2}\|\boldsymbol{\theta}_{i}^{t+1}\\!\\!-\\!\boldsymbol{w}_{i}^{t}\|^{2}\\!-\\!f_{i}(\boldsymbol{\theta}_{i}^{t})\\!-\\!\frac{\lambda}{2}\|\boldsymbol{\theta}_{i}^{t}\\!-\\!\boldsymbol{w}_{i}^{t}\|^{2})$
$\displaystyle\leq\sum_{i=1}^{m}\alpha_{i}\langle\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1}),\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\rangle+\frac{L\alpha_{i}}{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\frac{\lambda\alpha_{i}}{2}\langle\boldsymbol{\theta}_{i}^{t+1}+\boldsymbol{\theta}_{i}^{t}-2\boldsymbol{w}_{i}^{t},\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\rangle$
(54) $\displaystyle=\sum_{i\in\mathcal{S}^{t}}\alpha_{i}\langle\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})+\lambda(\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}),\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\rangle+\frac{\alpha_{i}(L-\lambda)}{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}$
(55)
$\displaystyle\leq\sum_{i\in\mathcal{S}^{t}}(\frac{1-\rho^{2}}{\rho^{2}}\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2})\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\frac{\alpha_{i}(L-\lambda)}{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\frac{\alpha_{i}^{2}}{(\frac{1}{\rho^{2}}-1)\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2}}\epsilon_{i}^{t}$
(56)
$\displaystyle=\sum_{i\in\mathcal{S}^{t}}(\frac{1-\rho^{2}}{\rho^{2}}\lambda^{2}\alpha_{i}^{2}-\frac{\lambda\alpha_{i}+\rho}{2})\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\frac{\alpha_{i}^{2}}{(\frac{1}{\rho^{2}}-1)\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2}}\epsilon_{i}^{t+1}$
(57)
$\displaystyle\leq\sum_{i\in\mathcal{S}^{t}}\Bigl{(}\frac{1-\rho^{2}}{\rho^{2}}\lambda^{2}\alpha_{i}^{2}-\frac{\lambda\alpha_{i}+\rho}{2})\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}-\frac{\alpha_{i}^{2}}{\bigl{(}(\frac{1}{\rho^{2}}-1)\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2}\bigr{)}(1-\upsilon_{i})}(\epsilon_{i}^{t+1}-\epsilon_{i}^{t})\Bigr{)}.$
(58)

where (54) follows from Assumption 2, and (56) follows from Equation (17) and
Proposition 5. Next, substituting Equations (A-C), (49), (53), and (58) into
Equation (A-C), we obtain

$\displaystyle\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{t})\leq$
$\displaystyle-\frac{\rho
m}{2}\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\sum_{i\in\mathcal{S}^{t}}\Bigl{(}\frac{\lambda^{2}\alpha_{i}^{2}(1+\rho)}{\rho}\times(\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\frac{1}{\rho}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}_{i}\|^{2})-\frac{\lambda\alpha_{i}+\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}$
$\displaystyle+(\frac{1-\rho^{2}}{\rho^{2}}\lambda^{2}\alpha_{i}^{2}-\frac{\lambda\alpha_{i}+\rho}{2})\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}-\frac{\alpha_{i}^{2}}{\bigl{(}(\frac{1}{\rho^{2}}-1)\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2}\bigr{)}(1-\upsilon_{i})}(\epsilon_{i}^{t+1}-\epsilon_{i}^{t})\Bigr{)}$
$\displaystyle=$ $\displaystyle-\frac{\rho
m}{2}\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\sum_{i\in\mathcal{S}^{t}}\Bigl{(}(\frac{\lambda^{2}\alpha_{i}^{2}(1+\rho)}{\rho^{2}}-\frac{\lambda\alpha_{i}+\rho}{2})\times(\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}+\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2})$
$\displaystyle-\frac{\alpha_{i}^{2}}{\bigl{(}(\frac{1}{\rho^{2}}-1)\lambda^{2}\alpha_{i}^{2}-\frac{L\alpha_{i}+\rho}{2}\bigr{)}(1-\upsilon_{i})}(\epsilon_{i}^{t+1}-\epsilon_{i}^{t})\Bigr{)}.$
(59)

Following the fact that the local parameters remain unchanged for clients not
included in $\mathcal{S}^{t}$ and according to (18), we have

$\displaystyle\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\geq\mathcal{D}_{1}\sum_{i=1}^{m}(\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\|\boldsymbol{w}^{t+1}_{i}-\boldsymbol{w}_{i}^{t}\|^{2}+\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}),$
(60)

where
$\mathcal{D}_{1}:=\min_{i}\\{\frac{\rho}{2},\frac{\lambda\alpha_{i}+\rho}{2}-\frac{\lambda^{2}\alpha_{i}^{2}(1+\rho)}{\rho^{2}}\\}$.
∎

###  A-D Proof of Lemma 2

###### Proof.

Since we have

$\displaystyle\nabla\tilde{\mathcal{L}}(\mathcal{P}^{t})=(\\{\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}\\}_{i=1}^{m},\\{\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}\\}_{i=1}^{m},\\{\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}\\}_{i=1}^{m},\\{\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}\\})(\mathcal{P}^{t}),$

then it is obvious that

$\begin{split}\|\nabla\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}=\|\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}+\sum_{i=1}^{m}\|\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}+\|\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}(\boldsymbol{w}_{i}^{t})\|^{2}+\|\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}(\boldsymbol{\pi}_{i}^{t})\|^{2}.\end{split}$
(61)

Next, we individually bound
$\|\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$,
$\|\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$,
$\|\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}(\boldsymbol{w}_{i}^{t})\|^{2}$
and
$\|\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}(\boldsymbol{\pi}_{i}^{t})\|^{2}$.

Bound of
$\|\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$. By
utilizing the Lagrangian function, we derive

$\begin{split}&\|\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}=\|\sum_{i=1}^{m}\rho(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t})-\boldsymbol{\pi}_{i}^{t}\|=0,\end{split}$
(62)

where (62) follows from Equation (14).

Bound of
$\|\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$.
According to the Lagrangian function, We denote

$\displaystyle\|\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$
$\displaystyle=\|\alpha_{i}(\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t})+\lambda(\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}_{i}^{t}))\|^{2}=\alpha_{i}^{2}\|\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t})+\lambda\boldsymbol{\theta}_{i}^{t}-\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})-\lambda\boldsymbol{\theta}_{i}^{t+1}+\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})+\lambda(\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t})\|^{2}$
$\displaystyle\leq 2\alpha_{i}^{2}\|\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t})+\lambda\boldsymbol{\theta}_{i}^{t}-\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})-\lambda\boldsymbol{\theta}_{i}^{t+1}\|^{2}+2\alpha_{i}^{2}\|\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})+\lambda(\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{w}_{i}^{t})\|^{2}$
(63) $\displaystyle\leq 4\alpha_{i}^{2}\|\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t})-\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t+1})\|^{2}+4\alpha_{i}^{2}\lambda^{2}\|\boldsymbol{\theta}_{i}^{t}-\boldsymbol{\theta}_{i}^{t+1}\|^{2}+2\epsilon_{i}^{t+1}$
(64) $\displaystyle\leq
4\alpha_{i}^{2}(L^{2}+\lambda^{2})\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+2\epsilon_{i}^{t+1},$
(65)

where (63) follows from Proposition 5, (64) follows from Proposition 5 and
(17), and (65) is due to the $L$-smoothness of $f_{i}$.

Bound of
$\|\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$.
Leveraging the Lagrangian function, we denote

$\displaystyle\|\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$
$\displaystyle=\|\alpha_{i}\lambda(\boldsymbol{w}_{i}^{t}-\boldsymbol{\theta}_{i}^{t})+\boldsymbol{\pi}_{i}^{t}+\rho(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t})\|^{2}$
$\displaystyle=\|\rho(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t})\|^{2}$ (66)
$\displaystyle=\|\rho(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}+\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t})\|^{2}$
(67) $\displaystyle\leq
2\rho^{2}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\|^{2}+2\|\boldsymbol{\pi}_{i}^{t+1}-\boldsymbol{\pi}_{i}^{t}\|$
(68)
$\displaystyle\leq(2\rho^{2}+4\lambda^{2}\alpha_{i}^{2})\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\|^{2}+4\lambda^{2}\alpha_{i}^{2}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}.$
(69)

where (66) follows from Lemma 3, (67) follows from Equation (13) and
Proposition 5, and (69) follows from Lemma 3 and Proposition 5.

Bound of
$\|\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$.
By using the Lagrangian function, we denote

$\displaystyle\|\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}$
$\displaystyle=\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}$
$\displaystyle\leq\frac{2\rho^{2}+4\lambda^{2}\alpha_{i}^{2}}{\rho^{2}}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\|^{2}+\frac{4\lambda^{2}\alpha_{i}^{2}}{\rho^{2}}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}.$
(70)

where (A-D) follows from (66) and (69). Next, by substituting (62), (65),
(69), and (A-D) into (61), we obtain

$\displaystyle\|\nabla\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}=\|\nabla_{\boldsymbol{w}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}+\sum_{i=1}^{m}\|\nabla_{\boldsymbol{\theta}_{i}}\tilde{\mathcal{L}}(\mathcal{P}^{t})\|^{2}+\|\nabla_{\boldsymbol{w}_{i}}\tilde{\mathcal{L}}(\boldsymbol{w}_{i}^{t})\|^{2}+\|\nabla_{\boldsymbol{\pi}_{i}}\tilde{\mathcal{L}}(\boldsymbol{\pi}_{i}^{t})\|^{2}$
$\displaystyle\leq\sum_{i=1}^{m}\left(4\lambda^{2}\alpha_{i}^{2}(1+\frac{1}{\rho^{2}})+2\alpha_{i}^{2}(L^{2}+2\lambda^{2})\right)\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\left(4\lambda^{2}\alpha_{i}^{2}(1+\frac{1}{\rho^{2}})+2\rho^{2}+2\right)\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}+2\epsilon_{i}^{t+1}$
$\displaystyle\leq
D_{2}\sum_{i=1}^{m}\left(\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2}+\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|^{2}+\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\epsilon_{i}^{t+1}\right)$
(71)

where
$D_{2}:=\max_{i}\\{4\lambda^{2}\alpha_{i}^{2}(1+\frac{1}{\rho^{2}})+2\alpha_{i}^{2}(L^{2}+2\lambda^{2})+2\rho^{2}+2\\}$.
∎

###  A-E Proof of Theorem 1

######  Lemma 9.

Let $\mathcal{P}^{t}$ be the sequence generated by Algorithm 1, then the
following results hold under Assumption 2.

  * a)

Sequences $\\{\tilde{L}(\mathcal{P}^{t})\\}$ is non-increasing.

  * b)

$\tilde{L}(\mathcal{P}^{t})\geq f(\Theta^{t},W^{t})\geq f^{*}\geq-\infty$ for
any $t\geq 1$.

  * c)

For any $i\in[m]$, the limits of the following terms are zero,

$\displaystyle(\epsilon_{i}^{t+1},\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t},\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t},\boldsymbol{\pi}_{i}^{t+1}-\boldsymbol{\pi}_{i}^{t})\to
0.$ (72)

###### Proof.

a) Following from Lemma 1, we have

$\displaystyle\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\geq\mathcal{D}_{1}\sum_{i=1}^{m}(\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\|\boldsymbol{w}^{t+1}_{i}-\boldsymbol{w}_{i}^{t}\|^{2}+\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2})\geq
0,$ (73)

which implies $\\{\mathcal{L}(\mathcal{P}^{t})\\}$ is non-increasing.

b) We consider bounding the following term:

$\displaystyle\tilde{\mathcal{L}}(\mathcal{P}^{t})-f(\Theta^{t},\boldsymbol{w}^{t})$
$\displaystyle=\sum_{i=1}^{m}\Bigl{(}\frac{\lambda\alpha_{i}}{2}\bigl{(}\|\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}_{i}^{t}\|^{2}-\|\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}\bigr{)}+\langle\boldsymbol{\pi}_{i}^{t},\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}+\iota_{i}\epsilon_{i}^{t}\Bigr{)}$
$\displaystyle=\sum_{i=1}^{m}\Bigl{(}\frac{\lambda\alpha_{i}}{2}\langle\boldsymbol{w}^{t}+\boldsymbol{w}_{i}^{t}-2\boldsymbol{\theta}_{i}^{t},\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\rangle+\langle\lambda\alpha_{i}(\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}_{i}^{t}),\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}+\iota_{i}\epsilon_{i}^{t}\Bigr{)}$
(74)
$\displaystyle=\sum_{i=1}^{m}\Bigl{(}\frac{\rho-\lambda\alpha_{i}}{2}\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t}\|^{2}+\iota_{i}\epsilon_{i}^{t}\Bigr{)}\geq
0,$ (75)

where (74) follows from Lemma 3 and (75) follows from the fact that
$\rho\geq\lambda\alpha_{i}$.

c) Following from the fact that
$\epsilon_{i}^{t+1}=\upsilon_{i}\epsilon_{i}^{t}$ and $0<\upsilon_{i}<1$, then
it can be easily indicated that $\epsilon_{i}^{t+1}\to 0$. Next, under Lemma 1
and $\tilde{L}^{t}>-\infty$, we obtain

$\displaystyle
D_{1}\sum_{t=0}^{\infty}\Delta\Gamma^{t+1}\leq\sum_{t=0}^{\infty}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\Bigr{)}\leq\tilde{\mathcal{L}}(\mathcal{P}^{0})-f^{*}\leq+\infty,$
(76)

which implies the sequences $\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|\to
0$, $\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}_{i}^{t}\|\to 0$, and
$\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|\to 0$. Next, we
consider

$\displaystyle\|\boldsymbol{\pi}_{i}^{t+1}-\boldsymbol{\pi}_{i}^{t}\|$
$\displaystyle=\lambda\alpha_{i}\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}+\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\|$
$\displaystyle\leq
2\lambda\alpha_{i}(\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|+\|\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1}\|),$
(77)

which implies $\|\boldsymbol{\pi}_{i}^{t+1}-\boldsymbol{\pi}_{i}^{t}\|\to 0$.
Furthermore, following from the fact that
$\boldsymbol{\pi}_{i}^{t+1}=\boldsymbol{\pi}_{i}^{t}+\rho(\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t})$,
we have

$\displaystyle\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\|=\frac{1}{\rho}\|\boldsymbol{\pi}_{i}^{t+1}-\boldsymbol{\pi}_{i}^{t}\|\to
0,$ (78)

which completes the proof.

∎

###### Proof of Theorem 1.

a) Based on Lemma 9, we have $\tilde{\mathcal{L}}(\mathcal{P}^{1})\geq
f(\Theta^{t},\boldsymbol{w}^{t})=\sum_{i=1}^{m}\alpha_{i}\Bigl{(}f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}||\boldsymbol{\theta}_{i}-\boldsymbol{w}||^{2}\Bigr{)}$.
Along with the coercive property of $f_{i}$, we can infer that the sequences
$\\{\Theta^{t}\\}$ and $\\{\boldsymbol{w}^{t}\\}$ are bounded. Following from
the fact that $\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}\|\to 0$, we can
infer that the sequence $\\{\boldsymbol{w}_{i}^{t}\\}$ is bounded. Finally, we
consider bounding $\boldsymbol{\pi}_{i}^{t}$ as

$\displaystyle\|\boldsymbol{\pi}_{i}^{t}\|=\lambda\alpha_{i}\|\boldsymbol{\theta}_{i}^{t}-\boldsymbol{w}_{i}^{t}\|\leq\lambda\alpha_{i}(\|\boldsymbol{\theta}_{i}^{t}\|+\|\boldsymbol{w}_{i}^{t}\|)\leq+\infty,$
(79)

which completes the proof.

b) Lemma 9 indicates that $\\{\tilde{\mathcal{L}}(\mathcal{P}^{t})\\}$ is non-
increasing and lower bounded. Then it is not hard to indicate that
$\tilde{\mathcal{L}}(\mathcal{P}^{t})\to\mathcal{L}(\mathcal{P}^{t})$ due to
the fact that $\epsilon_{i}^{t+1}\to 0$. Next, we consider

$\begin{split}\mathcal{L}(\mathcal{P}^{t+1})-\tilde{f}(\Theta^{t+1},W^{t+1})=\sum_{i=1}^{m}\langle\boldsymbol{\pi}_{i}^{t+1},\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t+1}\rangle+\frac{\rho}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t+1}\|^{2}\to
0,\end{split}$ (80)
$\begin{split}\mathcal{L}(\mathcal{P}^{t+1})-f(\Theta^{t+1},\boldsymbol{w}^{t+1})=\sum_{i=1}^{m}\Bigl{(}\frac{\rho-\lambda\alpha_{i}}{2}\|\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t+1}\|^{2}\Bigr{)}\to
0,\end{split}$ (81)

which completes the proof.

c) We begin by defining

$\displaystyle g_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i}):$
$\displaystyle=\nabla_{\boldsymbol{\theta}_{i}}\mathcal{L}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{\pi}_{i},\boldsymbol{w})$
$\displaystyle=\alpha_{i}\Bigl{(}\nabla
f_{i}(\boldsymbol{\theta}_{i})+\lambda(\boldsymbol{\theta}_{i}-\boldsymbol{w}_{i})\Bigr{)}.$
(82)

Then it holds that
$\|g_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t})\|^{2}\leq\epsilon^{t+1}_{i}$.
Next, we consider the following terms

$\displaystyle\|\nabla_{\Theta}\tilde{f}(\Theta^{t+1},W^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}g_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t})+\lambda\alpha_{i}(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1})\|$
$\displaystyle\leq\sum_{i=1}^{m}\|g_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t})\|+\lambda\alpha_{i}\|(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}_{i}^{t+1})\|\to
0,$ (83) $\displaystyle\|\nabla_{\Theta}f(\Theta^{t+1},W^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}g_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t})+\lambda\alpha_{i}(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t+1})\|$
$\displaystyle\leq\sum_{i=1}^{m}\|g_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t})\|+\lambda\alpha_{i}\|(\boldsymbol{w}_{i}^{t}-\boldsymbol{w}^{t+1})\|\to
0,$ (84) $\displaystyle\|\nabla_{W}\tilde{f}(\Theta^{t+1},W^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}\lambda\alpha_{i}(\boldsymbol{w}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}\boldsymbol{\pi}_{i}^{t+1}\|=\|\rho\sum_{i=1}^{m}(\boldsymbol{w}^{t+1}-\boldsymbol{w}_{i}^{t+1})\|$
(85)
$\displaystyle\leq\|\rho\sum_{i=1}^{m}(\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t})\|+\|\rho\sum_{i=1}^{m}(\boldsymbol{w}^{t}-\boldsymbol{w}_{i}^{t+1})\|\to
0,$ (86) $\displaystyle\|\nabla_{\boldsymbol{w}}f(\Theta^{t+1},W^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}\lambda\alpha_{i}(\boldsymbol{w}^{t+1}-\boldsymbol{\theta}_{i}^{t+1})\|$
$\displaystyle=\|\sum_{i=1}^{m}\boldsymbol{\pi}_{i}^{t+1}+\boldsymbol{w}^{t+1}-\boldsymbol{w}_{i}^{t+1}\|\to
0,$ (87)

where (83) and (84) follow from (72) in Lemma 9, (85) follows from Lemma 3 and
(14), (85) follows from (72) in Lemma 9, and (87) follows from (85) and (86).
∎

###  A-F Proof of Theorem 2

###### Proof.

a) Let $(\Theta^{\infty},W^{\infty},\Pi^{\infty},\boldsymbol{w}^{\infty})$ be
any accumulating point of the sequence
$\\{(\Theta^{t},W^{t},\Pi^{t},\boldsymbol{w}^{t})\\}$. Then we consider

$\displaystyle
g_{i}(\boldsymbol{\theta}_{i}^{\infty},\boldsymbol{w}_{i}^{\infty})=\alpha_{i}\Bigl{(}\nabla
f_{i}(\boldsymbol{\theta}_{i}^{\infty})+\lambda(\boldsymbol{\theta}_{i}^{\infty}-\boldsymbol{w}_{i}^{\infty})\Bigr{)}=0.$
(88)

Based on (85), we have

$\displaystyle\sum_{i=1}^{m}\boldsymbol{\pi}_{i}^{\infty}=0.$ (89)

According to Lemma 3, we have

$\displaystyle\lambda\alpha_{i}(\boldsymbol{\theta}_{i}^{\infty}-\boldsymbol{w}_{i}^{\infty})-\boldsymbol{\pi}_{i}^{\infty}=0$
(90)

Following from Lemma 9, we have

$\displaystyle\boldsymbol{w}_{i}^{\infty}-\boldsymbol{w}^{\infty}=0.$ (91)

Combining (88), (89), (90), and (91) yields the stationary point condition in
(16). Moreover, it can be easily inferred that $(\Theta^{\infty},W^{\infty})$
is a stationary point of Problem (6), which completes the proof.

b) Following from Proposition 6, it holds that $\tilde{\mathcal{L}}$ is a KŁ
function. According to Definition 11, we have

$\displaystyle\psi^{\prime}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\text{dist}\Bigl{(}0,\,\partial\tilde{\mathcal{L}}(\mathcal{P}^{t})\Bigr{)}\geq
1,$ (92)

which implies

$\displaystyle\psi^{\prime}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\geq\frac{1}{\text{dist}\Bigl{(}0,\,\partial\tilde{\mathcal{L}}(\mathcal{P}^{t})\Bigr{)}}\geq\frac{1}{\sqrt{\mathcal{D}_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})}}.$
(93)

Since $\psi$ is a concave function, we have

$\displaystyle\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}$
$\displaystyle\leq\psi^{\prime}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{t})\Bigr{)}$
$\displaystyle\leq-\frac{\mathcal{D}_{1}\Delta\Gamma^{t+1}}{\sqrt{\mathcal{D}_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})}},$
(94)

which implies

$\displaystyle\sqrt{\Delta\Gamma^{t+1}}$
$\displaystyle\leq\sqrt{\frac{\sqrt{\mathcal{D}_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})}}{\mathcal{D}_{1}}\Biggl{(}\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\Biggr{)}}$
$\displaystyle\leq\frac{1}{2}\frac{\sqrt{\mathcal{D}_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})}}{\mathcal{D}_{1}}+\frac{1}{2}\Biggl{(}\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\Biggr{)}$
(95)
$\displaystyle\leq\frac{1}{2}\frac{\sqrt{\mathcal{D}_{2}\Delta\Gamma^{t+1}}}{\mathcal{D}_{1}}+\frac{1}{2}\frac{\sqrt{\mathcal{D}_{2}\varepsilon^{t+1}}}{\mathcal{D}_{1}}+\frac{1}{2}\Biggl{(}\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\Biggr{)}.$
(96)

Summing over (96) from 0 to $+\infty$ yields

$\displaystyle\sum_{t=0}^{+\infty}\sqrt{\Delta\Gamma^{t+1}}\leq\sum_{t=0}^{+\infty}\frac{1}{2}\frac{\sqrt{\mathcal{D}_{2}\Delta\Gamma^{t+1}}}{\mathcal{D}_{1}}+\frac{1}{2}\frac{\sqrt{\mathcal{D}_{2}\varepsilon^{t+1}}}{\mathcal{D}_{1}}+\frac{1}{2}\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{0})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty}\Bigr{)},$
(97)

which implies

$\displaystyle\sum_{t=0}^{+\infty}\sqrt{\Delta\Gamma^{t+1}}\leq\frac{D_{1}}{2D_{1}-\sqrt{D_{2}}}\psi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{0})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty}\Bigr{)}+\sum_{t=1}^{+\infty}\frac{\sqrt{D_{2}\varepsilon^{t+1}}}{2D_{1}-\sqrt{D_{2}}}\leq\infty$
(98)

Following from the definition of $\Delta\Gamma^{t+1}$, we have

$\displaystyle\Delta\Gamma^{t+1}=\sum_{i=1}^{m}(\|\boldsymbol{w}^{t+1}-\boldsymbol{w}^{t}\|^{2}+\|\boldsymbol{w}^{t+1}_{i}-\boldsymbol{w}_{i}^{t}\|^{2}+\|\boldsymbol{\theta}_{i}^{t+1}-\boldsymbol{\theta}_{i}^{t}\|^{2})<\infty.$
(99)

Then we can infer from (99) that the sequence
$\\{\Theta^{t},\boldsymbol{w}^{t},W^{t}\\}$ is convergent. Next, by Lemma 3,
we can infer that $\\{\Pi^{t}\\}$ is convergent. Overall, the sequence
$\\{\mathcal{P}^{t}\\}$ is convergent. ∎

###  A-G Proof of Theorem 3

###### Proof.

Following from Lemma 1 and Lemma 2, it holds that

$\displaystyle\|\partial\tilde{L}(\mathcal{P}^{t})\|^{2}\leq
D_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})\leq\frac{D_{2}}{D_{1}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\Bigr{)}+D_{2}\varepsilon^{t+1}$
(100)

Telescoping (100) and dividing $T$, we obtain

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\partial\tilde{L}(\mathcal{P}^{t})\|^{2}$
$\displaystyle\leq\frac{D_{2}}{D_{1}T}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{0})-\tilde{\mathcal{L}}(\mathcal{P}^{T})\Bigr{)}+D_{2}\varepsilon^{1}$
$\displaystyle\leq\frac{D_{2}}{D_{1}T}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{0})-f^{*}\Bigr{)}+D_{2}\varepsilon^{1},$
(101)

which completes the proof.

∎

###  A-H Proof of Theorem 4

###### Proof.

Given the desingularizing function
$\psi(x)=\frac{\sqrt{c}}{1-\tau}x^{1-\tau}$, let
$\varepsilon^{t+1}:=\sum_{i=1}^{m}\epsilon_{i}^{t+1}$ we have

$\displaystyle 1$
$\displaystyle\leq\psi^{\prime}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2}\text{dist}\Bigl{(}0,\,\partial\tilde{\mathcal{L}}(\mathcal{P}^{t})\Bigr{)}^{2}$
(102) $\displaystyle\leq
c\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}\mathcal{D}_{2}(\Delta\Gamma^{t+1}+\varepsilon^{t+1})$
(103) $\displaystyle\leq
c\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}D_{2}\Bigl{(}\frac{\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})}{D_{1}}+\varepsilon^{t+1}\Bigr{)},$
(104)

where (103) follows from Lemma 1 and (104) follows from Lemma 2. Then we can
obtain

$\displaystyle\frac{D_{1}}{cD_{2}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}\leq\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}+D_{1}\varepsilon^{t+1}.$
(105)

Next, we consider the three cases with respect to $\tau$.

  * •

If $\tau=0$, then according to (105), it holds that

$\displaystyle\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}+D_{1}\varepsilon^{t+1}\geq\frac{D_{1}}{cD_{2}}.$
(106)

However,
$\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\to
0$ and $\varepsilon^{t+1}\to 0$, which are conflict with (106). Therefore, we
can deduce that there must exist $t\geq t_{1}>0$ such that
$\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})=0$.

  * •

If $\tau\in(0,1/2]$, there must exist $t\geq t_{2}>0$, such that
$0\leq\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\leq
1$. Then according to (105), we have

$\displaystyle\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}+D_{1}\varepsilon^{t+1}\geq\frac{D_{1}}{cD_{2}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}\geq\frac{D_{1}}{cD_{2}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)},$

which implies

$\displaystyle\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})$
$\displaystyle\leq\frac{cD_{2}}{D_{1}+cD_{2}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})+D_{1}\varepsilon^{t+1}\Bigr{)}$
(107)
$\displaystyle\leq\Bigl{(}\frac{cD_{2}}{D_{1}+cD_{2}}\Bigr{)}^{2}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t-1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})+D_{1}\varepsilon^{t+1}\Bigr{)}$
(108)
$\displaystyle\leq\Bigl{(}\frac{cD_{2}}{D_{1}+cD_{2}}\Bigr{)}^{t-t_{2}+1}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t_{2}})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})+D_{1}\varepsilon^{t+1}\Bigr{)}$
(109)
$\displaystyle\leq\Bigl{(}\frac{cD_{2}}{D_{1}+cD_{2}}\Bigr{)}^{t-t_{2}+1}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t_{2}})-f^{*}+D_{1}\varepsilon^{t+1}\Bigr{)}.$
(110)

  * •

If $\tau\in(1/2,1)$, we define a function
$\phi(z):=\frac{CD_{2}}{D_{1}(1-2\tau)}z^{1-2\tau}$. Let
$1>\frac{1}{R}>\min_{i}{\nu_{i}}>0$ be a constant, we consider two cases, if
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}\geq\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}/R$,
we obtain

$\displaystyle\phi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}$
(111) $\displaystyle=$
$\displaystyle\int_{\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})}^{\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})}\phi^{\prime}(z)dz=\int_{\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})}^{\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})}\frac{cD_{2}}{D_{1}}z^{-2\tau}dz$
(112) $\displaystyle\geq$
$\displaystyle\frac{cD_{2}}{D_{1}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\Bigr{)}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}$
(113) $\displaystyle\geq$
$\displaystyle\frac{cD_{2}}{RD_{1}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})\Bigr{)}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}$
(114) $\displaystyle=$
$\displaystyle\frac{cD_{2}}{RD_{1}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{t+1})+D_{1}\varepsilon^{t+1}\Bigr{)}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}-\frac{cD_{2}}{RD_{1}}D_{1}\varepsilon^{t+1}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}$
(115) $\displaystyle=$
$\displaystyle\frac{1}{R}-\frac{cD_{2}}{R}\frac{\varepsilon^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}.$
(116)

    * a)

If $\varepsilon^{t+1}$ is a lower-order infinitesimal of
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}$,
then we can obtain

$\displaystyle\lim_{t\to+\infty}\frac{\varepsilon^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}=\lim_{t\to+\infty}\frac{\sum_{i=1}^{m}\nu_{i}\epsilon_{i}^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}=\infty.$
(117)

Based on (117), we can derive the convergence rate of
$\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}\to
0$ is faster than $\sum_{i=1}^{m}\nu_{i}\epsilon_{i}^{t+1}\to 0$, which
implies

$\displaystyle\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}<\min_{i}\nu_{i}\times\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}<\frac{1}{R}\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau},$
(118)

Note that (118) is conflict with
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}\geq\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}/R$,
then $\varepsilon^{t+1}$ cannot be a lower-order infinitesimal of
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}$.

    * b)

If $\varepsilon^{t+1}$ is a higher-order infinitesimal of
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}$,
then we obtain

$\displaystyle\lim_{t\to+\infty}\frac{\varepsilon^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}=0.$
(119)

If $\varepsilon^{t+1}$ and
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{2\tau}$
are same-order infinitesimals, then we obtain

$\displaystyle\lim_{t\to+\infty}\frac{\varepsilon^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}=\alpha\neq
0.$ (120)

Then there exists $Q>0$ such that
$\frac{\varepsilon^{t+1}}{\bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\bigr{)}^{2\tau}}\leq
Q$. Therefore, we obtain that

$\displaystyle\phi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}\geq\frac{1}{R}-\frac{cD_{2}Q}{R}.$
(121)

Consider another case, if
$\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}<\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{-2\tau}/R$,
then we can infer

$\displaystyle
R^{\frac{1}{2\tau}}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}<\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty}),$
(122)

which implies

$\displaystyle\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}$
$\displaystyle>\overline{R}\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau},$
(123)
$\displaystyle\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}-\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}$
$\displaystyle>(\overline{R}-1)\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau},$
(124)

where $\overline{R}=R^{\frac{2\tau-1}{\tau}}>1$. Since $\overline{R}-1>0$ and
$\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\to
0^{+}$, then there exists $\overline{\mu}>0$ such that
$(\overline{R}-1)\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}>\overline{\mu}$
for all $t\geq t_{3}$. Therefore, we obtain that

$\displaystyle\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t+1})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}-\Bigl{(}\tilde{\mathcal{L}}(\mathcal{P}^{t})-\tilde{\mathcal{L}}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}\geq\overline{\mu}>0$
(125)

for all $t\geq t_{3}$. Then we bound
$\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}$
as

$\displaystyle\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}=$
$\displaystyle\frac{cD_{2}}{(1-2\tau)D_{1}}\Biggl{(}\Bigl{(}\mathcal{L}(\mathcal{P}^{t})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}-\Bigl{(}\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}^{1-2\tau}\Biggr{)}$
$\displaystyle\geq$
$\displaystyle\frac{c\overline{\mu}D_{2}}{(2\tau-1)D_{1}}.$ (126)

If we define
$\mu:=\min\\{\frac{1}{R}-\frac{cD_{2}Q}{R},\frac{c\overline{\mu}D_{2}}{(2\tau-1)D_{1}}\\}>0$,
one can combine (111) and (• ‣ A-H) to obtain that

$\displaystyle\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}\geq\mu$
(127)

for all $t\geq t_{3}$. By summing (127) from $t_{3}$ to some $t$ greater than
$t_{3}$, we obtain

$\displaystyle\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t_{3}})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}-\phi\Bigl{(}\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\Bigr{)}\geq(t-t_{3})\mu,$
(128)

which implies

$\displaystyle\mathcal{L}(\mathcal{P}^{t+1})-\mathcal{L}(\mathcal{P}^{\infty})\leq\Bigl{(}\frac{(2\tau-1)\mu
D_{1}}{cD_{2}}(t-t_{3})\Bigr{)}^{\frac{1}{1-2\tau}},$ (129)

which completes the proof.

∎

##  Appendix B Robustness and Fairness

In this section, we are inspired by [59] to consider employing an example of
federated linear regression to analyze the fairness and robustness of FLAME.
Suppose the truly personalized model on client $i$ is
$\boldsymbol{\theta}_{i}$, each client possesses $N$ samples222For simplicity,
we assume each client possesses an equal number of samples., and the covariate
on client $i$ is $\\{\boldsymbol{x}_{i,j}\\}_{j=1}^{N}$ with
$\boldsymbol{x}_{i,j}\in\mathbb{R}^{d}$ is fixed. The observations are
generated by
$y_{i,j}=\boldsymbol{x}_{i,j}^{\top}\boldsymbol{\theta}_{i}+z_{i,j}$, where
$z_{i,j}$ denotes an i.i.d. Gaussian noise with distribution
$\mathcal{N}(0,\sigma^{2})$. Then the loss on client $i$ is
$f_{i}(\boldsymbol{\theta}_{i})=\frac{1}{2N}\sum_{j=1}^{N}(y_{i,j}-\boldsymbol{x}_{i,j}^{\top}\boldsymbol{\theta}_{i})$.

###  B-A Solutions of FLAME

We consider to derive the solution of FLAME under the case of federated linear
regression. Let
$X_{i}=(\boldsymbol{x}_{i,1},\boldsymbol{x}_{i,2},\cdots,\boldsymbol{x}_{i,N})$
and $\boldsymbol{y}_{i}=(y_{i,1},y_{i,2},\cdots,y_{i,N})^{\top}$, then the
observations can be rewritten as
$\boldsymbol{y}_{i}=X_{i}\boldsymbol{\theta}_{i}+\boldsymbol{z}_{i}$ with
$\boldsymbol{z}_{i}\sim\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$,
and the loss on client $i$ can be rewritten as
$f_{i}(\boldsymbol{\theta}_{i})=\frac{1}{2N}\|X_{i}\boldsymbol{\theta}_{i}-\boldsymbol{y}_{i}\|^{2}$.
Suppose $X_{i}^{\top}X_{i}$ is invertible, then the estimator of
$\boldsymbol{\theta}_{i}$ is

$\displaystyle\hat{\boldsymbol{\theta}}_{i}=(X_{i}^{\top}X_{i})^{-1}X_{i}^{\top}\boldsymbol{y}_{i}.$
(130)

Recall the optimization problem of FLAME is

$\displaystyle\min_{\boldsymbol{w},\boldsymbol{\theta}_{i}}\Bigl{\\{}f(\Theta,\boldsymbol{w}):=\sum_{i=1}^{m}\alpha_{i}\Bigl{(}f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}||\boldsymbol{\theta}_{i}-\boldsymbol{w}||^{2}\Bigr{)}\Bigr{\\}}$
(131)

with optimal conditions

$\displaystyle\left\\{\begin{aligned} \nabla
f_{i}(\boldsymbol{\theta}_{i}^{*})+\lambda(\boldsymbol{\theta}_{i}^{*}-\boldsymbol{w}^{*})&=0,&i\in[m],\\\
\boldsymbol{w}^{*}-\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{\theta}_{i}^{*}&=0.&\\\
\end{aligned}\right.$ (132)

Substituting the loss function
$f_{i}(\boldsymbol{\theta}_{i})=\frac{1}{2N}\|X_{i}\boldsymbol{\theta}_{i}-\boldsymbol{y}_{i}\|^{2}$
of linear regression into (131) and (132) yields

$\displaystyle
f(\Theta,\boldsymbol{w})=\sum_{i=1}^{m}\alpha_{i}\Bigl{(}\frac{1}{2N}\|X_{i}\boldsymbol{\theta}_{i}-\boldsymbol{y}_{i}\|^{2}+\frac{\lambda}{2}||\boldsymbol{\theta}_{i}-\boldsymbol{w}||^{2}\Bigr{)},$
(133)

and

$\displaystyle\left\\{\begin{aligned}
\frac{1}{N}X_{i}^{\top}(X_{i}\boldsymbol{\theta}_{i}^{*}-\boldsymbol{y}_{i})+\lambda(\boldsymbol{\theta}_{i}^{*}-\boldsymbol{w}^{*})&=0,&i\in[m],\\\
\boldsymbol{w}^{*}-\sum_{i=1}^{m}\alpha_{i}\boldsymbol{\theta}_{i}^{*}&=0.&\\\
\end{aligned}\right.$ (134)

Without loss of generality, we let $\alpha_{i}=\frac{1}{m}$, then we can
derive from (134) that

$\displaystyle\left\\{\begin{aligned}
\boldsymbol{w}^{*}&=\Bigl{(}\boldsymbol{I}_{d}-\frac{1}{m}\sum_{i=1}^{m}\lambda\Bigl{(}\frac{1}{N}X_{i}^{\top}X_{i}+\lambda\boldsymbol{I}_{d}\Bigr{)}^{-1}\Bigr{)}^{-1}\frac{1}{m}\sum_{i=1}^{m}\lambda\Bigl{(}\frac{1}{N}X_{i}^{\top}X_{i}+\lambda\boldsymbol{I}_{d}\Bigr{)}^{-1}\frac{1}{N}X_{i}^{\top}X_{i}\hat{\boldsymbol{\theta}}_{i},&\\\
\boldsymbol{\theta}_{i}^{*}&=\Bigl{(}\frac{1}{N}X_{i}^{\top}X_{i}+\lambda\boldsymbol{I}_{d}\Bigr{)}^{-1}\Bigl{(}\frac{1}{N}X_{i}^{\top}X_{i}\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{*}\Bigr{)},\quad
i\in[m].&\\\ \end{aligned}\right.$ (135)

However, for the general $X_{i}$, obtaining a concise expression for
$\boldsymbol{w}^{*}$ and $\boldsymbol{\theta}_{i}^{*}$ is challenging. To
streamline the calculations, we assume
$X_{i}^{\top}X_{i}=Nb_{i}\boldsymbol{I}_{d}$. Consequently, the solution in
(135) can be simplified as

$\displaystyle\left\\{\begin{aligned}
\boldsymbol{w}^{*}&=\frac{\sum_{i=1}^{m}b_{i}\hat{\boldsymbol{\theta}}_{i}/(b_{i}+\lambda)}{\sum_{i=1}^{m}b_{i}/(b_{i}+\lambda)},&\\\
\boldsymbol{\theta}_{i}^{*}&=\frac{b_{i}\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{*}}{b_{i}+\lambda},\quad
i\in[m].&\\\ \end{aligned}\right.$ (136)

If we further assume $b_{i}=b$333This assumption is reasonable since datasets
are often normalized., then we obtain

$\displaystyle\left\\{\begin{aligned}
\boldsymbol{w}^{*}&=\frac{1}{m}\sum_{i=1}^{m}\hat{\boldsymbol{\theta}}_{i},&\\\
\boldsymbol{\theta}_{i}^{*}&=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{*}}{b+\lambda},\quad
i\in[m].&\\\ \end{aligned}\right.$ (137)

According to [59], we can obtain the solutions of pFedMe and Ditto are the
same with FLAME when $b_{i}=b,\,i\in[m]$.

###  B-B Test Loss

Recall that the local dataset on client $i$ is $(X_{i},\boldsymbol{y}_{i})$,
where $X_{i}$ is fixed and $\boldsymbol{y}_{i}$ follows a Gaussian
distribution
$\mathcal{N}(X_{i}\boldsymbol{\theta}_{i},\sigma^{2}\boldsymbol{I}_{d})$.
Consequently, the data heterogeneity among clients arises solely from the
heterogeneity of $\boldsymbol{\theta}_{i}$. Then based on (130) and (137), we
can derive the distribution of the FLAME’s solutions as follows,

$\displaystyle\boldsymbol{w}^{*}\sim\mathcal{N}\Bigl{(}\overline{\boldsymbol{\theta}},\frac{\sigma^{2}}{bmN}\boldsymbol{I}_{d}\Bigr{)},\,\boldsymbol{\theta}_{i}^{*}\sim\mathcal{N}\Bigl{(}\frac{b\boldsymbol{\theta}_{i}+\lambda\overline{\boldsymbol{\theta}}}{b+\lambda},\frac{(b^{2}+\frac{2b\lambda}{m})\frac{\sigma^{2}}{bN}+\frac{\lambda^{2}\sigma^{2}}{bmN}}{(b+\lambda)^{2}}\boldsymbol{I}_{d}\Bigr{)}$
(138)

where
$\overline{\boldsymbol{\theta}}=\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{\theta}_{i}$.
Given that $X_{i}$ is fixed, we assume the test dataset is
$(X_{i},\boldsymbol{y}_{i}^{\prime})$ where
$\boldsymbol{y}_{i}^{\prime}=X_{i}\boldsymbol{\theta}_{i}+\boldsymbol{z}_{i}^{\prime}$
with
$\boldsymbol{z}_{i}^{\prime}\sim\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$,
which is independent of $\boldsymbol{z}_{i}$. Next, according to [59], the
test losses of the global and personalized models on client $i$ are defined as
follows,

$\displaystyle f_{i}(\boldsymbol{w}^{*})$
$\displaystyle:=\frac{1}{2N}\mathbb{E}\|X_{i}\boldsymbol{w}^{*}-\boldsymbol{y}_{i}^{\prime}\|^{2}=\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}(\operatorname{var}(\boldsymbol{w}^{*}))+\frac{b}{2}\|\mathbb{E}\boldsymbol{w}^{*}-\boldsymbol{\theta}_{i}\|^{2}$
(139) $\displaystyle f_{i}(\boldsymbol{\theta}_{i}^{*})$
$\displaystyle:=\frac{1}{2N}\mathbb{E}\|X_{i}\boldsymbol{\theta}_{i}^{*}-\boldsymbol{y}_{i}^{\prime}\|^{2}=\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}(\operatorname{var}(\boldsymbol{\theta}_{i}^{*}))+\frac{b}{2}\|\mathbb{E}\boldsymbol{\theta}_{i}^{*}-\boldsymbol{\theta}_{i}\|^{2},$
(140)

and the average losses are defined as follows,

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{i}(\boldsymbol{w}^{*})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}(\operatorname{var}(\boldsymbol{w}^{*}))+\frac{b}{2m}\sum_{i=1}^{m}\|\mathbb{E}\boldsymbol{w}^{*}-\boldsymbol{\theta}_{i}\|^{2},$
(141)
$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{i}(\boldsymbol{\theta}_{i}^{*})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b}{2m}\sum_{i=1}^{m}\operatorname{tr}(\operatorname{var}(\boldsymbol{\theta}_{i}^{*}))+\frac{b}{2m}\sum_{i=1}^{m}\|\mathbb{E}\boldsymbol{\theta}_{i}^{*}-\boldsymbol{\theta}_{i}\|^{2}.$
(142)

Substitute the mean and variance of $\boldsymbol{w}^{*}$ and
$\boldsymbol{\theta}_{i}^{*}$ in (138) into (141) and (142), we obtain

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{i}(\boldsymbol{w}^{*})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{\sigma^{2}d}{2mN}+\frac{b}{2m}\sum_{i=1}^{m}\|\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2},$
(143)
$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{i}(\boldsymbol{\theta}_{i}^{*})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{mb^{2}+2b\lambda+\lambda^{2}}{m(b+\lambda)^{2}}\cdot\frac{\sigma^{2}d}{2N}+\frac{b\lambda^{2}}{2m(b+\lambda^{2})}\sum_{i=1}^{m}\|\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}.$
(144)

###  B-C Robustness

In this subsection, we analyze the robustness of FLAME against three types of
Byzantine attacks. In the previous subsection, we concentrate solely on the
exact solutions of FLAME and overlook the algorithmic processes. To thoroughly
assess robustness, it is essential to examine the algorithm’s procedures. We
consider a simplified scenario with an infinite number of local update steps,
a single round of communication, and participation from all clients.
Throughout this subsection, we assume there are $m_{a}$ malicious clients and
$m_{b}$ benign clients, with $m_{a}+m_{b}=m$, and let $\mathcal{S}_{a}$ denote
the indices of malicious clients and $\mathcal{S}_{b}$ denote the indices of
benign clients.

Before we analyze the impact of these attacks on the solutions of FLAME and
compare the average test losses on benign clients, we demonstrate that after
one round of communication, FLAME obtains inexact solutions that are different
from the exact solutions as defined in Appendix B-A. Consider the update step
of $\boldsymbol{w}_{i}$:

$\displaystyle\boldsymbol{w}_{i}^{1}=\frac{1}{\lambda\alpha_{i}+\rho}(\lambda\alpha_{i}\boldsymbol{\theta}_{i}^{1}+\rho\boldsymbol{w}^{0}-\boldsymbol{\pi}_{i}^{0})$
(145)

where
$\boldsymbol{\theta}_{i}^{1}=\operatorname*{argmin}_{\boldsymbol{\theta}_{i}}\Bigl{\\{}f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}\|\boldsymbol{\theta}_{i}-\boldsymbol{w}_{i}^{0}\|\Bigr{\\}}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}_{i}^{0}}{b+\lambda}$444For
the local update step of $\boldsymbol{\theta}_{i}$:
$\boldsymbol{\theta}_{i}^{t,h+1}=\boldsymbol{\theta}_{i}^{t,h}-\eta(\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t,h},\xi)+\lambda(\boldsymbol{\theta}_{i}^{t,h}-\boldsymbol{w}_{i}^{t}))$,
it is noteworthy that when the number of local update steps is infinite, it is
reasonable to assume that we can obtain the exact solution of
$\boldsymbol{\theta}_{i}$.. Then we can rewrite the update step of
$\boldsymbol{w}_{i}$ as follows

$\displaystyle\boldsymbol{w}_{i}^{1}=\frac{1}{\lambda\alpha_{i}+\rho}(\lambda\alpha_{i}\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}_{i}^{0}}{b+\lambda}+\rho\boldsymbol{w}^{0}-\boldsymbol{\pi}_{i}^{0})$
(146)

Suppose we initialize $\boldsymbol{w}^{0}$, $\boldsymbol{\pi}^{0}$, and
$\boldsymbol{w}_{i}^{0}$ to 0, we obtain
$\boldsymbol{w}_{i}^{1}=\frac{\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}\hat{\boldsymbol{\theta}}_{i}$.
Then based on (13) and (14), each client sends the update messages as
$\boldsymbol{u}_{i}=\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}\hat{\boldsymbol{\theta}}_{i}$.
Next, the server aggregates the update messages and updates the global model
as
$\boldsymbol{w}^{\texttt{FLAME}}=\frac{1}{m}\sum_{i=1}^{m}\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}\hat{\boldsymbol{\theta}}_{i}$
to each client. Finally, each client solves the personalized model as
$\boldsymbol{\theta}_{i}^{\texttt{FLAME}}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{\texttt{FLAME}}}{b+\lambda}$.

####  B-C1 Same-value Attacks

Consider the following two cases:

  * •

When client $i$ is benign, then it will send
$\boldsymbol{u}_{i}^{(be)}=\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}\hat{\boldsymbol{\theta}}_{i}$
to the server. Recall that
$\hat{\boldsymbol{\theta}}_{i}=(X_{i}^{\top}X_{i})^{-1}X_{i}^{\top}\boldsymbol{y}_{i}\sim\mathcal{N}(\boldsymbol{\theta}_{i},\frac{\sigma^{2}}{bN}\boldsymbol{I}_{d})$.
Then we can derive that
$\boldsymbol{u}_{i}^{(be)}\sim\mathcal{N}(\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}\boldsymbol{\theta}_{i},(\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda})^{2}\cdot\frac{\sigma^{2}}{bN}\boldsymbol{I}_{d})$.
If we set $\rho\geq\lambda\alpha_{i}$ (this condition should also be satisfied
in our convergence analysis), then we can define
$q:=\frac{2\lambda\alpha_{i}}{\lambda\alpha_{i}+\rho}\frac{b}{b+\lambda}<1$,
which implies
$\boldsymbol{u}_{i}^{(be)}\sim\mathcal{N}(q\boldsymbol{\theta}_{i},\frac{q^{2}\sigma^{2}}{bN}\boldsymbol{I}_{d})$.

  * •

When client $i$ is malicious, then it will send
$\boldsymbol{u}_{i}^{(ma)}=p\boldsymbol{1}_{d}\in\mathbb{R}^{d}$ to the server
with $p\sim\mathcal{N}(0,\gamma^{2})$, which implies that
$\boldsymbol{u}_{i}^{(ma)}\sim\mathcal{N}(\boldsymbol{0},\gamma^{2}\boldsymbol{1}_{d})$,
where $\boldsymbol{1}_{d}=\begin{pmatrix}1&1&\cdots&1\\\ 1&1&\cdots&1\\\
\vdots&\vdots&\ddots&\vdots\\\ 1&1&\cdots&1\end{pmatrix}\in\mathbb{R}^{d\times
d}$.

Then the server aggregates the update messages from each client and obtains
$\boldsymbol{w}^{\text{SVA}}=\frac{1}{m}\Bigl{(}\sum_{i\in\mathcal{S}_{a}}\boldsymbol{u}_{i}^{(ma)}+\sum_{i\in\mathcal{S}_{b}}\boldsymbol{u}_{i}^{(be)}\Bigr{)}$,
which implies
$\boldsymbol{w}^{\text{SVA}}\sim\mathcal{N}\Bigl{(}\frac{1}{m}\sum_{i\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i},\frac{1}{m^{2}}(m_{a}\gamma^{2}\boldsymbol{1}_{d}+\frac{m_{b}q^{2}\sigma^{2}}{bN}\boldsymbol{I}_{d})\Bigr{)}$.
Next, based on (139), we obtain the average test loss of the global model
$\boldsymbol{w}^{\text{SVA}}$ on benign clients as

$\displaystyle\text{Loss}^{\texttt{FLAME-GM},\text{SVA}}(q)=$
$\displaystyle\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}f_{i}(\boldsymbol{w}^{\text{SVA}})$
$\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}\bigl{(}{\operatorname{var}(\boldsymbol{w}^{\text{SVA}})}\bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\mathbb{E}\boldsymbol{w}^{\text{SVA}}-\boldsymbol{\theta}_{i}\|^{2}$
(147) $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{bd}{2m^{2}}\Bigl{(}m_{a}\gamma^{2}+\frac{m_{b}q^{2}\sigma^{2}}{bN}\Bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i^{\prime}}}{m}-\boldsymbol{\theta}_{i}\|^{2}.$
(148)

Next, we consider obtaining the distribution of the personalized model. Recall
that
$\boldsymbol{\theta}_{i}^{*}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{*}}{b+\lambda}$,
then the benign clients compute the personalized model as
$\boldsymbol{\theta}_{i}^{\text{SVA}}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{\text{SVA}}}{b+\lambda}$,
which implies the distribution of $\boldsymbol{\theta}_{i}^{\text{SVA}}$ is

$\displaystyle\boldsymbol{\theta}_{i}^{\text{SVA}}\sim\mathcal{N}\Bigl{(}\frac{b\boldsymbol{\theta}_{i}+\frac{\lambda}{m}\sum_{i^{\prime}\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i^{\prime}}}{b+\lambda},\frac{\Bigl{(}\bigl{(}b+\frac{q\lambda}{m}\bigr{)}^{2}\frac{\sigma^{2}}{bN}+(m_{b}-1)\frac{q^{2}\lambda^{2}}{m^{2}}\frac{\sigma^{2}}{bN}\Bigr{)}\boldsymbol{I}_{d}+\frac{m_{a}\lambda^{2}\gamma^{2}}{m^{2}}\boldsymbol{1}_{d}}{(b+\lambda)^{2}}\Bigr{)}.$
(149)

Then the average test loss of the personalized model on benign clients is

$\displaystyle\text{Loss}^{\texttt{FLAME-PM},\text{SVA}}(q)=$
$\displaystyle\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}f_{i}(\boldsymbol{\theta}_{i}^{\text{SVA}})$
$\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\operatorname{tr}\bigl{(}{\operatorname{var}(\boldsymbol{\theta}_{i}^{\text{SVA}})}\bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\mathbb{E}\boldsymbol{\theta}_{i}^{\text{SVA}}-\boldsymbol{\theta}_{i}\|^{2}$
(150) $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{bd}{2}\frac{\Bigl{(}b^{2}+\frac{2bq\lambda}{m}+\frac{m_{b}q^{2}\lambda^{2}}{m^{2}}\Bigr{)}\frac{\sigma^{2}}{bN}+\frac{m_{a}\lambda^{2}\gamma^{2}}{m^{2}}}{(b+\lambda)^{2}}+\frac{b\lambda^{2}}{2m_{b}(b+\lambda)^{2}}\sum_{i\in\mathcal{S}_{b}}\|\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i^{\prime}}}{m}-\boldsymbol{\theta}_{i}\|^{2}.$
(151)

According to [59], the average test loss of personalized and global models on
benign clients for pFedMe and Ditto are

$\displaystyle\text{Loss}^{{\texttt{pFedMe-PM},\text{SVA}}}=$
$\displaystyle\text{Loss}^{{\texttt{Ditto-
PM},\text{SVA}}}=\frac{\sigma^{2}}{2}+\frac{bd}{2}\frac{\Bigl{(}b^{2}+\frac{2b\lambda}{m}+\frac{m_{b}\lambda^{2}}{m^{2}}\Bigr{)}\frac{\sigma^{2}}{bN}+\frac{m_{a}\lambda^{2}\gamma^{2}}{m^{2}}}{(b+\lambda)^{2}}+\frac{b\lambda^{2}}{2m_{b}(b+\lambda)^{2}}\sum_{i\in\mathcal{S}_{b}}\|\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m}-\boldsymbol{\theta}_{i}\|^{2},$
(152) $\displaystyle\text{Loss}^{{\texttt{pFedMe-GM},\text{SVA}}}=$
$\displaystyle\text{Loss}^{{\texttt{Ditto-
GM},\text{SVA}}}=\frac{\sigma^{2}}{2}+\frac{bd}{2m^{2}}\Bigl{(}m_{a}\gamma^{2}+\frac{m_{b}\sigma^{2}}{bN}\Bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m}-\boldsymbol{\theta}_{i}\|^{2}.$
(153)

Note that the testing losses of pFedMe and Ditto can be considered as the
testing loss of FLAME when $q=1$. Next, we take the derivatives of the testing
loss of FLAME with respect to $q$. They are

$\displaystyle\frac{\partial\text{Loss}^{{\texttt{FLAME-
GM},\text{SVA}}}(q)}{\partial q}$
$\displaystyle=\frac{bd}{2m^{2}}\frac{2m_{b}q\sigma^{2}}{bN}+\frac{b}{2m_{b}}2(qm_{b}-m)\Bigl{(}\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m}\Bigr{)}^{\top}\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m},$
(154) $\displaystyle\frac{\partial\text{Loss}^{{\texttt{FLAME-
PM},\text{SVA}}}(q)}{\partial q}$
$\displaystyle=\frac{bd}{2}\frac{\frac{\sigma^{2}}{bN}}{(b+\lambda)^{2}}\Bigl{(}\frac{2b\lambda}{m}+\frac{2m_{b}q\lambda^{2}}{m^{2}}\Bigr{)}+\frac{b\lambda^{2}}{2m_{b}(b+\lambda)^{2}}\cdot
2(qm_{b}-m)\Bigl{(}\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m}\Bigr{)}^{\top}\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m}.$
(155)

One can check $\frac{\partial\text{Loss}^{{\texttt{FLAME-
GM},\text{SVA}}}(q)}{\partial q}\geq 0$ when
$q\geq\frac{mNb\overline{\boldsymbol{\theta}}^{\top}_{b}\overline{\boldsymbol{\theta}}_{b}}{d\sigma^{2}+m_{b}Nb}$,
and $\frac{\partial\text{Loss}^{{\texttt{FLAME-PM},\text{SVA}}}(q)}{\partial
q}\geq 0$ when
$q\geq\frac{mb(m_{b}N\lambda\overline{\boldsymbol{\theta}}^{\top}_{b}\overline{\boldsymbol{\theta}}_{b}-d\sigma^{2})}{d\sigma^{2}m_{b}\lambda+m_{b}^{2}Nb\lambda\overline{\boldsymbol{\theta}}^{\top}_{b}\overline{\boldsymbol{\theta}}_{b}}$,
where
$\overline{\boldsymbol{\theta}}_{b}=\frac{\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}}{m_{b}}$.
Then we can infer that $\text{Loss}^{\texttt{FLAME-
PM},\text{SVA}}\leq\text{Loss}^{{\texttt{pFedMe-
PM},\text{SVA}}}(\lambda)=\text{Loss}^{{\texttt{Ditto-
PM},\text{SVA}}}(\lambda)$ and $\text{Loss}^{\texttt{FLAME-
GM},\text{SVA}}\leq\text{Loss}^{{\texttt{pFedMe-
GM},\text{SVA}}}=\text{Loss}^{{\texttt{Ditto-GM},\text{SVA}}}$.

####  B-C2 Sign-flipping Attacks

We consider computing the test loss of FLAME under Sign-flipping attacks.

  * •

When client $i$ is benign, then it will send $\boldsymbol{u}_{i}^{(be)}$ to
the server and
$\boldsymbol{u}_{i}^{(be)}\sim\mathcal{N}(q\boldsymbol{\theta}_{i},\frac{q^{2}\sigma^{2}}{bm}\boldsymbol{I}_{d})$.

  * •

When client $i$ is malicious, then it will send
$\boldsymbol{u}_{i}^{(ma)}=-|p|\boldsymbol{u}_{i}$ to the server, where
$p\sim\mathcal{N}(0,\gamma^{2})$. Then we can obtain the mean and covariance
of $\boldsymbol{u}_{i}^{(ma)}$ by the independence of $|p|$ and
$\boldsymbol{u}_{i}$ as [59]

$\displaystyle\mathbb{E}[\boldsymbol{u}_{i}^{(ma)}]$
$\displaystyle=\mathbb{E}[-|p|\boldsymbol{u}_{i}^{(be)}]=-\sqrt{\frac{2}{\pi}}\gamma
q\boldsymbol{\theta}_{i},$ (156)
$\displaystyle\operatorname{var}[\boldsymbol{u}_{i}^{(ma)}]$
$\displaystyle=\operatorname{var}[-|p|\boldsymbol{u}_{i}^{(be)}]$
$\displaystyle=\mathbb{E}[p^{2}\boldsymbol{u}_{i}^{(be)}(\boldsymbol{u}_{i}^{(be)})^{\top}]-\mathbb{E}[|c|\boldsymbol{u}_{i}^{(be)}]\mathbb{E}[|c|(\boldsymbol{u}_{i}^{(be)})^{\top}]$
$\displaystyle=\gamma^{2}\Bigl{(}q^{2}\boldsymbol{\theta}_{i}\boldsymbol{\theta}_{i}^{\top}+\frac{q^{2}\sigma^{2}}{bm}\boldsymbol{I}_{d}\Bigr{)}-\frac{2}{\pi}\gamma^{2}q^{2}\boldsymbol{\theta}_{i}\boldsymbol{\theta}_{i}^{\top}$
$\displaystyle=\frac{\pi-2}{\pi}\gamma^{2}q^{2}\boldsymbol{\theta}_{i}\boldsymbol{\theta}_{i}^{\top}+\gamma^{2}\frac{q^{2}\sigma^{2}}{bm}\boldsymbol{I}_{d}=:q^{2}\boldsymbol{V}_{i}.$
(157)

where (157) defines
$\boldsymbol{V}_{i}:=\frac{\pi-2}{\pi}\gamma^{2}\boldsymbol{\theta}_{i}\boldsymbol{\theta}_{i}^{\top}+\gamma^{2}\frac{\sigma^{2}}{bm}\boldsymbol{I}_{d}$.

Then the server aggregates the updated messages from each client and updates
the global model by
$\boldsymbol{w}^{\text{SFA}}=\frac{1}{m}\Bigl{(}\sum_{i\in\mathcal{S}_{b}}\boldsymbol{u}_{i}^{(be)}+\sum_{i\in\mathcal{S}_{a}}\boldsymbol{u}_{i}^{(ma)}\Bigr{)}$,
which implies

$\displaystyle\mathbb{E}[\boldsymbol{w}^{\text{SFA}}]$
$\displaystyle=\frac{1}{m}\Bigl{(}\sum_{i\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i}-\sum_{i\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma
q\boldsymbol{\theta}_{i}\Bigr{)},$ (158)
$\displaystyle\operatorname{var}[\boldsymbol{w}^{\text{SFA}}]$
$\displaystyle=\frac{1}{m^{2}}\Bigl{(}\frac{m_{b}q^{2}\sigma^{2}}{bm}\boldsymbol{I}_{d}+\sum_{i\in\mathcal{S}_{a}}q^{2}\boldsymbol{V}_{i}\Bigr{)}.$
(159)

Then the average test loss of the global model on benign clients is

$\displaystyle\\!\\!\\!\\!\\!\\!\text{Loss}^{\texttt{FLAME-
GM},\text{SVA}}(q)=$
$\displaystyle\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}f_{i}(\boldsymbol{w}^{\text{SFA}})$
$\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}\bigl{(}{\operatorname{var}(\boldsymbol{w}^{\text{SFA}})}\bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\mathbb{E}\boldsymbol{w}^{\text{SFA}}-\boldsymbol{\theta}_{i}\|^{2}$
(160) $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{bd}{2m^{2}}\Bigl{(}\frac{m_{b}q^{2}\sigma^{2}}{bm}+q^{2}\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i})}{d}\Bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{a}}\Bigl{\|}\frac{1}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma
q\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}-\boldsymbol{\theta}_{i}\Bigr{\|}^{2}.$
(161)

Next, we consider obtaining the mean and variance of the personalized model.
Recall that
$\boldsymbol{\theta}_{i}^{*}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{*}}{b+\lambda}$,
then the benign clients compute the personalized model as
$\boldsymbol{\theta}_{i}^{\text{SFA}}=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{\text{SFA}}}{b+\lambda}$,
which implies that

$\displaystyle\mathbb{E}[\boldsymbol{\theta}_{i}^{\text{SFA}}]=$
$\displaystyle\frac{1}{b+\lambda}\Biggl{(}b\theta_{i}+\frac{\lambda}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}q\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma
q\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}\Biggr{)}$ (162)
$\displaystyle\operatorname{var}[\boldsymbol{\theta}_{i}^{\text{SFA}}]=$
$\displaystyle\frac{\Bigl{(}\bigl{(}b+\frac{q\lambda}{m}\bigr{)}^{2}\frac{\sigma^{2}}{bN}+(m_{b}-1)\frac{q^{2}\lambda^{2}}{m^{2}}\frac{\sigma^{2}}{bN}\Bigr{)}\boldsymbol{I}_{d}+\frac{q^{2}\lambda^{2}}{m^{2}}\sum_{i^{\prime}\in\mathcal{S}_{a}}\boldsymbol{V}_{i}}{(b+\lambda)^{2}}$
(163)

Then the test loss of the personalized model on benign clients is

$\displaystyle\text{Loss}^{\texttt{FLAME-PM},\text{SFA}}(q)$
$\displaystyle=\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}f_{i}(\boldsymbol{\theta}_{i}^{\text{SFA}})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\operatorname{tr}\bigl{(}{\operatorname{var}(\boldsymbol{\theta}_{i}^{\text{SFA}})}\bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{b}}\|\mathbb{E}\boldsymbol{\theta}_{i}^{\text{SFA}}-\boldsymbol{\theta}_{i}\|^{2}$
(164)
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{bd}{2}\frac{\Bigl{(}b^{2}+\frac{2bq\lambda}{m}+\frac{m_{b}q^{2}\lambda^{2}}{m^{2}}\Bigr{)}\frac{\sigma^{2}}{bN}+\frac{q^{2}\lambda^{2}}{m^{2}}\sum_{i^{\prime}\in\mathcal{S}_{a}}\frac{\operatorname{tr}({\boldsymbol{V}_{i}})}{d}}{(b+\lambda)^{2}}$
$\displaystyle+\frac{b\lambda^{2}}{2(b+\lambda)^{2}}\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}\Bigl{\|}\frac{q}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}-\boldsymbol{\theta}_{i}\Bigr{\|}^{2}$
(165)

According to [59], the average test loss of personalized and global models on
benign clients for pFedMe and Ditto are

$\displaystyle\text{Loss}^{{\texttt{pFedMe-
PM},\text{SFA}}}=\text{Loss}^{{\texttt{Ditto-PM},\text{SFA}}}$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{bd}{2}\frac{\Bigl{(}b^{2}+\frac{2b\lambda}{m}+\frac{m_{b}\lambda^{2}}{m^{2}}\Bigr{)}\frac{\sigma^{2}}{bN}+\frac{\lambda^{2}}{m^{2}}\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}({\boldsymbol{V}_{i}})}{d}}{(b+\lambda)^{2}}$
$\displaystyle+\frac{b\lambda^{2}}{2(b+\lambda)^{2}}\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{b}}\Bigl{\|}\frac{1}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}-\boldsymbol{\theta}_{i}\Bigr{\|}^{2},$
$\displaystyle\text{Loss}^{{\texttt{pFedMe-
GM},\text{SFA}}}=\text{Loss}^{{\texttt{Ditto-GM},\text{SFA}}}$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{bd}{2m^{2}}\Bigl{(}\frac{m_{b}\sigma^{2}}{bm}+\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i})}{d}\Bigr{)}+\frac{b}{2m_{b}}\sum_{i\in\mathcal{S}_{a}}\Bigl{\|}\frac{1}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}-\boldsymbol{\theta}_{i}\Bigr{\|}^{2}.$

Note that the testing losses of pFedMe and Ditto can be considered as the
testing loss of FLAME when $q=1$. Next, we take the derivatives of the testing
loss of FLAME with respect to $q$. They are

$\displaystyle\frac{\partial\text{Loss}^{{\texttt{FLAME-
GM},\text{SFA}}}(q)}{\partial q}$
$\displaystyle=\frac{bd}{m^{2}}\Bigl{(}\frac{m_{b}\sigma^{2}q}{bm}+q\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i})}{d}\Bigr{)}+\frac{bm_{a}}{m_{b}}\overline{\boldsymbol{\theta}}_{m}^{\top}\overline{\boldsymbol{\theta}}_{m}q-\frac{b}{m_{b}}\sum_{i\in\mathcal{S}_{a}}\boldsymbol{\theta}_{i}^{\top}\overline{\boldsymbol{\theta}}_{m},$
(166) $\displaystyle\frac{\partial\text{Loss}^{{\texttt{FLAME-
PM},\text{SFA}}}(q)}{\partial q}$
$\displaystyle=\frac{bd}{(b+\lambda)^{2}}\Bigl{[}\frac{\sigma^{2}}{bN}\Bigl{(}\frac{b\lambda}{m}+\frac{m_{b}\lambda^{2}q}{m^{2}}\Bigr{)}+\frac{q\lambda^{2}}{m^{2}}\sum_{i^{\prime}\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i^{\prime}})}{d}\Bigr{]}+\frac{\lambda^{2}}{(b+\lambda)^{2}}\Bigl{(}\frac{bm_{a}}{m_{b}}\overline{\boldsymbol{\theta}}_{m}^{\top}\overline{\boldsymbol{\theta}}_{m}q-\frac{b}{m_{b}}\sum_{i^{\prime}\in\mathcal{S}_{a}}\boldsymbol{\theta}_{i}^{\top}\overline{\boldsymbol{\theta}}_{m}\Bigr{)}.$
(167)

One can check $\frac{\partial\text{Loss}^{{\texttt{FLAME-
GM},\text{SFA}}}(q)}{\partial q}\geq 0$ when
$q\geq\frac{\frac{1}{m_{b}}\sum_{i\in\mathcal{S}_{a}}\boldsymbol{\theta}_{i}^{\top}\overline{\boldsymbol{\theta}}_{m}}{\frac{d}{m^{2}}\Bigl{(}\frac{m_{b}\sigma^{2}}{bm}+\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i})}{d}\Bigr{)}+\frac{m_{a}}{m_{b}}\overline{\boldsymbol{\theta}}_{m}^{\top}\overline{\boldsymbol{\theta}}_{m}}$,
and $\frac{\partial\text{Loss}^{{\texttt{FLAME-PM},\text{SFA}}}(q)}{\partial
q}\geq 0$ when
$q\geq\frac{\frac{b\lambda}{m_{b}}\sum_{i^{\prime}\in\mathcal{S}_{a}}\boldsymbol{\theta}_{i}^{\top}\overline{\boldsymbol{\theta}}_{m}-\frac{bd\sigma^{2}}{mN}}{\frac{d\sigma^{2}m_{b}\lambda}{m^{2}N}+\frac{b\lambda
d}{m^{2}}\sum_{i\in\mathcal{S}_{a}}\frac{\operatorname{tr}(\boldsymbol{V}_{i})}{d}+\frac{b\lambda
m_{a}}{m_{b}}\overline{\boldsymbol{\theta}}_{m}^{\top}\overline{\boldsymbol{\theta}}_{m}}$,
where
$\overline{\boldsymbol{\theta}}_{m}=\frac{1}{m}\Bigl{(}\sum_{i^{\prime}\in\mathcal{S}_{b}}\boldsymbol{\theta}_{i^{\prime}}-\sum_{i^{\prime}\in\mathcal{S}_{a}}\sqrt{\frac{2}{\pi}}\gamma\boldsymbol{\theta}_{i^{\prime}}\Bigr{)}$.
Then, following the monotonic increasing property of the testing loss
function, we can infer that $\text{Loss}^{\texttt{FLAME-
PM},\text{SFA}}\leq\text{Loss}^{{\texttt{pFedMe-
PM},\text{SFA}}}(\lambda)=\text{Loss}^{{\texttt{Ditto-
PM},\text{SFA}}}(\lambda)$ and $\text{Loss}^{\texttt{FLAME-
GM},\text{SFA}}\leq\text{Loss}^{{\texttt{pFedMe-
GM},\text{SFA}}}=\text{Loss}^{{\texttt{Ditto-GM},\text{SFA}}}$.

####  B-C3 Gaussian Attacks

When client $i$ is malicious, then it will send
$\boldsymbol{u}_{i}^{(ma)}=p\boldsymbol{I}_{d}$ to the server, where
$p\sim\mathcal{N}(0,\gamma^{2})$, which implies that
$\boldsymbol{u}_{i}^{(ma)}\sim\mathcal{N}(\boldsymbol{0}_{d},\gamma^{2}\boldsymbol{I}_{d})$.
Note that
$\operatorname{tr}(\boldsymbol{I}_{d})=\operatorname{tr}(\boldsymbol{1}_{d})$,
then the test loss on benign clients is similar to that of the same-value
attacks.

###  B-D Fairness

We compute the variance of the test loss of the global model and personalized
model to measure fairness. Recall that after one communication, the
personalized and global models are updated as

$\displaystyle\boldsymbol{w}^{\texttt{FLAME}}$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}q\hat{\boldsymbol{\theta}}_{i}\sim\mathcal{N}\Bigl{(}q\overline{\boldsymbol{\theta}},\frac{q^{2}\sigma^{2}}{bmN}\boldsymbol{I}_{d}\Bigr{)},$
(168) $\displaystyle\boldsymbol{\theta}_{i}^{\texttt{FLAME}}$
$\displaystyle=\frac{b\hat{\boldsymbol{\theta}}_{i}+\lambda\boldsymbol{w}^{\texttt{FLAME}}}{b+\lambda}\sim\mathcal{N}\Bigl{(}\frac{b\boldsymbol{\theta}_{i}+q\lambda\overline{\boldsymbol{\theta}}}{b+\lambda},\frac{(b^{2}+\frac{2bq\lambda}{m})\frac{\sigma^{2}}{bN}+\frac{q^{2}\lambda^{2}\sigma^{2}}{bmN}}{(b+\lambda)^{2}}\boldsymbol{I}_{d}\Bigr{)},i\in[m].$
(169)

Then the test losses of the personalized and global models on each client are

$\displaystyle f_{i}(\boldsymbol{w}^{\texttt{FLAME}})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}(\operatorname{var}(\boldsymbol{w}^{\texttt{FLAME}}))+\frac{b}{2}\|\mathbb{E}\boldsymbol{w}^{\texttt{FLAME}}-\boldsymbol{\theta}_{i}\|^{2}$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{q^{2}\sigma^{2}d}{2mN}+\frac{b}{2}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2},$
(170) $\displaystyle f_{i}(\boldsymbol{\theta}_{i}^{\texttt{FLAME}})$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b}{2}\operatorname{tr}(\operatorname{var}(\boldsymbol{\theta}_{i}^{\texttt{FLAME}}))+\frac{b}{2}\|\mathbb{E}\boldsymbol{\theta}_{i}^{\texttt{FLAME}}-\boldsymbol{\theta}_{i}\|^{2}$
$\displaystyle=\frac{\sigma^{2}}{2}+\frac{b^{2}+\frac{2bq\lambda}{m}+\frac{q^{2}\lambda^{2}}{m}}{(b+\lambda)^{2}}\cdot\frac{\sigma^{2}d}{2N}+\frac{b\lambda^{2}}{2(b+\lambda)^{2}}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}.$
(171)

Then the variances of test losses are obtained as follows,

$\displaystyle\operatorname{var}[f_{i}(\boldsymbol{w}^{\texttt{FLAME}})]$
$\displaystyle=\frac{b^{2}}{4}\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}],$
(172)
$\displaystyle\operatorname{var}[f_{i}(\boldsymbol{\theta}_{i}^{\texttt{FLAME}})]$
$\displaystyle=\frac{b^{2}\lambda^{4}}{4(b+\lambda)^{4}}\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{4}].$
(173)

According to [59], the variances pFedMe and Ditto correspond to the special
cases where $q=1$ in (172) and (173). Next, we consider investigating the
monotonicity of
$\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
with respect to $q$. We now give an equivalent form of
$\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
as

$\displaystyle\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{4}-\Bigl{(}\frac{1}{m}\sum_{i=1}^{m}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}\Bigr{)}^{2}$
$\displaystyle=\frac{1}{m^{2}}\Bigl{(}(m-1)\sum_{i=1}^{m}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{4}-\sum_{i\neq
i^{\prime}}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i^{\prime}}\|^{2}\Bigr{)}$
(174) $\displaystyle=\frac{1}{m^{2}}\sum_{i\neq
i^{\prime}}\frac{(\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}-\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i^{\prime}}\|^{2})^{2}}{2}$
(175)

Then we can obtain the derivative of
$\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
with respect to $q$

$\displaystyle\frac{\partial\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]}{\partial
q}=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}(\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}-\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i^{\prime}}\|^{2})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}.$
(176)

Next, we derive the second-order derivative of
$\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
with respect to $q$

$\displaystyle\frac{\partial^{2}\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]}{\partial
q^{2}}=-\frac{4}{m^{2}}\sum_{i\neq
i^{\prime}}\overline{\boldsymbol{\theta}}^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}\leq
0$ (177)

Thus, we can deduce that
$\frac{\partial\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]}{\partial
q}$ decreases monotonically with $q$, reaching its minimum when $q=1$. That is

$\displaystyle\frac{\partial\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]}{\partial
q}\Big{|}_{q=1}$ $\displaystyle=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}(\|\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}-\|\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i^{\prime}}\|^{2})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}$
$\displaystyle=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}(2\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}$
(178) $\displaystyle=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}2\overline{\boldsymbol{\theta}}^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}-\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}(\boldsymbol{\theta}_{i^{\prime}}+\boldsymbol{\theta}_{i})^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}$
(179) $\displaystyle=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}2\overline{\boldsymbol{\theta}}^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}-\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}(\|\boldsymbol{\theta}_{i^{\prime}}\|^{2}-\|\boldsymbol{\theta}_{i}\|^{2})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}.$
(180)

Suppose that all personalized models are uniform, then we can obtain
$\|\boldsymbol{\theta}_{i^{\prime}}\|^{2}=\|\boldsymbol{\theta}_{i}\|^{2}$ for
any $i^{\prime}\neq i$, which implies

$\displaystyle\frac{\partial\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]}{\partial
q}\Big{|}_{q=1}=\frac{2}{m^{2}}\sum_{i\neq
i^{\prime}}2\overline{\boldsymbol{\theta}}^{\top}(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})(\boldsymbol{\theta}_{i^{\prime}}-\boldsymbol{\theta}_{i})^{\top}\overline{\boldsymbol{\theta}}\geq
0.$ (181)

Therefore, we can infer that
$\operatorname{var}[\|q\overline{\boldsymbol{\theta}}-\boldsymbol{\theta}_{i}\|^{2}]$
increases monotonically with respect to $q$, which completes the proof.

##  Appendix C Extension

We extend the established ADMM-based training method to the recently proposed
fair and robust PFL framework: Lp-Proj [59]. We present the specific algorithm
of ADMM-based Lp-Proj in Algorithm 2.

Input: $T:$ the total communication rounds, $\rho$: the penalty parameter,
$\lambda$: the hyperparameter, $m$: the number of clients, $X_{i},i\in[m]$:
the local dataset, $\eta$: the learning rate, $H$: the number of local
iterations, $\boldsymbol{P}$: the projection matrix.

1 Initialize:
$\boldsymbol{\theta}_{i}^{0},\boldsymbol{w}_{i}^{0},\boldsymbol{\pi}_{i}^{0},\boldsymbol{u}_{i}^{0}=\boldsymbol{w}_{i}^{0}+\frac{1}{\rho}\boldsymbol{\pi}_{i}^{0}$,
$i\in[m]$.

2for  _$t=0,1,\dots,T-1$_ do

/* On the server side. */

3 Randomly select $s$ clients $\mathcal{S}^{t}\subset[m]$;

4

5 Call each client, uploading
$\\{\boldsymbol{z}^{t}_{1},\dots,\boldsymbol{z}^{t}_{m}\\}$ to the server;

6

7 Update $\boldsymbol{w}^{t}=\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{u}_{i}^{t}$;

8

9 Broadcast $\boldsymbol{w}^{t}$ to the selected clients;

10

/* On the client side. */

11

12 for  _each client $i\in\mathcal{S}^{t}$_ do

13 Create Batches $\mathcal{B}$;

14

15 for  _$h=0,1,\dots,H-1$_ do

16 for  _batch $\xi\in\mathcal{B}$_ do

17 Compute the gradient $f_{i}(\boldsymbol{\theta}_{i}^{t,h},\xi)$;

18

19 $\boldsymbol{\theta}_{i}^{t,h+1}=\boldsymbol{\theta}_{i}^{t,h}-\eta(\nabla
f_{i}(\boldsymbol{\theta}_{i}^{t,h},\xi)+\lambda\boldsymbol{P}^{\top}(\boldsymbol{P}\boldsymbol{\theta}_{i}^{t,h}-\boldsymbol{w}_{i}^{t}))$;

20

21 $\boldsymbol{\theta}_{i}^{t+1}=\boldsymbol{\theta}_{i}^{t,H-1}$;

22

23
$\boldsymbol{w}_{i}^{t+1}=\frac{1}{\lambda\alpha_{i}+\rho}(\lambda\alpha_{i}\boldsymbol{P}\boldsymbol{\theta}_{i}^{t+1}+\rho\boldsymbol{w}^{t}-\boldsymbol{\pi}_{i}^{t})$;

24

25
$\boldsymbol{\pi}_{i}^{t+1}=\boldsymbol{\pi}_{i}^{t}+\rho(\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t})$;

26

27
$\boldsymbol{u}_{i}^{t+1}=\boldsymbol{w}_{i}^{t+1}+\frac{1}{\rho}\boldsymbol{\pi}_{i}^{t+1}$;

28

29 for  _each client $i\notin\mathcal{S}^{t}$_ do

30
$(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i}^{t+1},\boldsymbol{\pi}_{i}^{t+1},\boldsymbol{u}_{i}^{t+1})=(\boldsymbol{\theta}_{i}^{t},\boldsymbol{w}_{i}^{t},\boldsymbol{\pi}_{i}^{t},\boldsymbol{u}_{i}^{t})$;

31

Algorithm 2 ADMM-based Lp-Proj-2

Next, we introduce the objective function and propose our training framework
for Lp-Proj. Lin et al. [59] proposed to project local models into a shared-
and-fixed low-dimensional random subspace and uses infimal convolution to
control the deviation between the global model and projected local models.
Specifically, they construct the objective function for PFL as

$\begin{split}\min_{\boldsymbol{w}}\\!\sum_{i=1}^{m}\alpha_{i}F_{i}(\boldsymbol{w}),\,\,\text{where
}F_{i}(\boldsymbol{w}):=\min_{\boldsymbol{\theta}_{i}}f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{p}||\boldsymbol{w}-\boldsymbol{P}\boldsymbol{\theta}_{i}||^{p}_{p},\,\,i\in[m].\end{split}$
(182)

where $p\geq 1$ and $\boldsymbol{P}\in\mathbb{R}^{d_{sub}\times d}$ is a
random matrix that is generated initially and will not vary anymore. $d_{sub}$
is the dimension of the shared-and-fixed random subspace. Without loss of
generality, we consider the case where $p=2$, referring to Lp-Proj-2. Next, we
consider converting (182) into the following optimization problem using the
same approach as applied to FLAME,

$\begin{split}\min_{\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{w}}\Bigr{\\{}\tilde{f}(\Theta,W):=\sum_{i=1}^{m}\alpha_{i}\Bigl{(}f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}||\boldsymbol{w}_{i}-\boldsymbol{P}\boldsymbol{\theta}_{i}||^{2}\Bigr{)}\Bigl{\\}},\,\,\text{
s.t. }\,\boldsymbol{w}_{i}=\boldsymbol{w},\,\,i\in[m].\end{split}$ (183)

To implement ADMM for Problem (183), we establish the corresponding augmented
Lagrangian function as follows:

$\begin{split}\mathcal{L}(\Theta,W,\Pi,\boldsymbol{w})&:=\sum_{i=1}^{m}\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{w},\boldsymbol{\pi}_{i}),\\\
\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i},\boldsymbol{\pi}_{i},\boldsymbol{w})&:=\alpha_{i}(f_{i}(\boldsymbol{\theta}_{i})+\frac{\lambda}{2}||\boldsymbol{w}_{i}-\boldsymbol{P}\boldsymbol{\theta}_{i}||^{2})+\langle\boldsymbol{\pi}_{i},\boldsymbol{w}_{i}-\boldsymbol{w}\rangle+\frac{\rho}{2}||\boldsymbol{w}_{i}-\boldsymbol{w}||^{2},\end{split}$
(184)

The ADMM framework for solving Problem (183) can be summarized as follows:
after initializing the variables with
$(\Theta^{0},W^{0},\Pi^{0},\boldsymbol{w}^{0})$, the following update steps
are executed iteratively for each $t\geq 0,$

$\displaystyle\boldsymbol{\theta}_{i}^{t+1}$
$\displaystyle=\operatorname{argmin}_{\boldsymbol{\theta}_{i}}\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{w}_{i}^{t},\boldsymbol{\pi}^{t}_{i},\boldsymbol{w}^{t},),$
(185) $\displaystyle\boldsymbol{w}_{i}^{t+1}$
$\displaystyle=\operatorname{argmin}_{\boldsymbol{w}_{i}}\mathcal{L}_{i}(\boldsymbol{\theta}_{i}^{t+1},\boldsymbol{w}_{i},\boldsymbol{\pi}^{t}_{i},\boldsymbol{w}^{t})$
$\displaystyle=\frac{1}{\lambda\alpha_{i}+\rho}(\lambda\alpha_{i}\boldsymbol{P}\boldsymbol{\theta}_{i}^{t+1}+\rho\boldsymbol{w}^{t}-\boldsymbol{\pi}_{i}^{t}),$
(186) $\displaystyle\boldsymbol{\pi}_{i}^{t+1}$
$\displaystyle=\boldsymbol{\pi}_{i}^{t}+\rho(\boldsymbol{w}_{i}^{t+1}-\boldsymbol{w}^{t}),$
(187) $\displaystyle\boldsymbol{w}^{t+1}$
$\displaystyle=\operatorname{argmin}_{\boldsymbol{w}}\mathcal{L}(\Theta^{t+1},W^{t+1},\boldsymbol{w},\Pi^{t+1})$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}(\boldsymbol{w}_{i}^{t+1}+\frac{1}{\rho}\boldsymbol{\boldsymbol{\pi}}_{i}^{t+1}).$
(188)

In Algorithm 2, we introduce the ADMM-based Lp-Proj-2. Except for the updates
of $\boldsymbol{\theta}_{i}$ and $\boldsymbol{w}_{i}$, all other aspects are
identical to FLAME. After being mapped by the projection matrix
$\boldsymbol{P}$, the global model is compressed into a lower-dimensional
matrix, rendering it no longer useful.

##  Appendix D Additional and Complete Experiment Results

###  D-A Complete Results on Accuracy and Convergence

Fig. 13 \- Fig. 20 show how the accuracy of different methods changes with
communication rounds for different types of heterogeneous data. We can see
that FLAME-HM achieves the highest accuracy and convergence in most datasets
and data partitioning methods. In label skew scenarios, personalized models
typically perform better, while in other types of heterogeneous data, the
global model generally performs better.

###  D-B Complete Results on Robustness

Complete results for different methods under various types of Byzantine
attacks and heterogeneous data are shown in Fig. 21 \- Fig. 35. FLAME shows
stable performance and is more robust than other methods against most attacks
and with most types of heterogeneous data.

###  D-C Complete Results on Fairness

Fig. 36 \- Fig. 43 show the trade-off between variance and accuracy for
different methods on various types of heterogeneous data. We can see that
FLAME-HM achieves the best trade-off in most datasets and data partitioning
methods, and its accuracy is consistently the highest. In the case of label
skew, personalized models usually achieve a better trade-off, while for other
types of heterogeneous data, the global model usually achieves a better trade-
off.

Figure 13: A comparison of the test accuracy across different methods with
quantity-based label imbalance ($q=2$). Figure 14: A comparison of the test
accuracy across different methods with quantity-based label imbalance ($q=3$).
Figure 15: A comparison of the test accuracy across different methods with
quantity-based label imbalance ($q=4$). Figure 16: A comparison of the test
accuracy across different methods with quantity-based label imbalance ($q=5$).
Figure 17: A comparison of the test accuracy across different methods with
quantity-based label imbalance ($q=6$). Figure 18: A comparison of the test
accuracy across different methods with distribution-based label imbalance.
Figure 19: A comparison of the test accuracy across different methods with
quality skew. Figure 20: A comparison of the test accuracy across different
methods with quantity skew.

Figure 21: Robustness comparison of different methods under label poisoning
attacks with distribution-based label imbalance. Figure 22: Robustness
comparison of different methods under label poisoning attacks with quantity-
based label imbalance. Figure 23: Robustness comparison of different methods
under label poisoning attacks with quality skew. Figure 24: Robustness
comparison of different methods under label poisoning attacks with quantity
skew. Figure 25: Robustness comparison of different methods under same-value
attacks with quantity-based label imbalance ($q=2$). Figure 26: Robustness
comparison of different methods under same-value attacks with distribution-
based label imbalance. Figure 27: Robustness comparison of different methods
under same-value attacks with quality skew. Figure 28: Robustness comparison
of different methods under same-value attacks with quantity skew. Figure 29:
Robustness comparison of different methods under sign-flipping attacks with
quantity-based label imbalance ($q=2$). Figure 30: Robustness comparison of
different methods under sign-flipping attacks with distribution-based label
imbalance. Figure 31: Robustness comparison of different methods under sign-
flipping attacks with quality skew. Figure 32: Robustness comparison of
different methods under sign-flipping attacks with quantity skew. Figure 33:
Robustness comparison of different methods under Gaussian attacks with
quantity-based label imbalance ($q=2$). Figure 34: Robustness comparison of
different methods under Gaussian attacks with quality skew. Figure 35:
Robustness comparison of different methods under Gaussian attacks with
quantity skew.

Figure 36: Accuracy-fairness trade-off of competing methods with distribution-
based label imbalance. Figure 37: Accuracy-fairness trade-off of competing
methods with quantity-based label imbalance ($q=2$). Figure 38: Accuracy-
fairness trade-off of competing methods with quantity-based label imbalance
($q=3$). Figure 39: Accuracy-fairness trade-off of competing methods with
quantity-based label imbalance ($q=4$). Figure 40: Accuracy-fairness trade-off
of competing methods with quantity-based label imbalance ($q=5$). Figure 41:
Accuracy-fairness trade-off of competing methods with quantity-based label
imbalance ($q=6$). Figure 42: Accuracy-fairness trade-off of competing methods
with quality skew. Figure 43: Accuracy-fairness trade-off of competing methods
with quantity skew.