(2) we know that this term is 0 if $i\neq j$, and a weighted sum of product of
sigmoid functions if $i=j$. Then, using the Facts 1-4 the function
$\nabla_{\bf x}\widetilde{Q}_{\bf c}({\bf x})_{j,i}$ is Lipschitz continuous.
Since $i,j$ were arbitrarily chosen, $\nabla_{\bf x}\widetilde{Q}_{\bf c}({\bf
x})_{j,i}$ is Lipschitz continuous for all $i,j$. Then, by Fact 5,
$\nabla_{\bf x}\widetilde{Q}_{\bf c}({\bf x})$ is Lipschitz continuous, which
implies that $\widetilde{Q}_{\bf c}({\bf x})$ is $L_{Q_{1}}$-smooth for some
coefficient $L_{Q_{1}}<\infty$. ∎

######  Claim 9.

$\widetilde{Q}_{\bf c}({\bf x})$ is $l_{Q_{2}}$-Lipschitz continuous and
$L_{Q_{2}}$-smooth with respect to ${\bf c}$.

###### Proof.

For Lipschitz continuity we have,

$\displaystyle\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{i}}{\partial
c_{j}}$
$\displaystyle=\sigma(P(x_{i}-\frac{c_{j}+c_{j-1}}{2}))-\sigma(P(x_{i}-\frac{c_{j}+c_{j+1}}{2}))$
$\displaystyle\quad+(c_{j}-c_{j+1})\frac{P}{2}\sigma(P(x_{i}-\frac{c_{j}+c_{j+1}}{2}))(1-\sigma(P(x_{i}-\frac{c_{j}+c_{j+1}}{2})))$
$\displaystyle\quad-(c_{j}-c_{j-1})\frac{P}{2}\sigma(P(x_{i}-\frac{c_{j}+c_{j-1}}{2}))(1-\sigma(P(x_{i}-\frac{c_{j}+c_{j-1}}{2})))$

As a result, $\|\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{i}}{\partial
c_{j}}\|\leq 2+c_{max}\frac{P}{2}$. Similar to Claim 8 using the facts that
$i$ is arbitrary and the Fact 5, we find there exists $l_{Q_{2}}$ such that
$\|\widetilde{Q}_{\bf c}({\bf x})-\widetilde{Q}_{\bf d}({\bf x})\|\leq
l_{Q_{1}}\|{\bf c}-{\bf d}\|$. In other words, $\widetilde{Q}_{\bf c}({\bf
x})$ is Lipschitz continuous. And for the smoothness, following the same idea
from the proof of Claim 9 we find $\widetilde{Q}_{\bf c}({\bf x})$ is
$L_{Q_{2}}$-smooth with respect to ${\bf c}$. ∎

The example we gave in this section is simple yet provides technical
necessities we require in the analysis. Other examples can also be used as
long as they provide the smoothness properties that we utilize in the next
sections.

###  A.5 Lipschitz Relations

In this section we will use the assumptions A.1-5 and show useful relations
for partial gradients derived from the assumptions. We have the following
gradient for the composite function:

$\displaystyle\nabla_{({\bf x},{\bf c})}h({\bf x},{\bf c})=\nabla_{({\bf
x},{\bf c})}f(\widetilde{Q}_{\bf c}({\bf x}))=\nabla_{({\bf x},{\bf
c})}\widetilde{Q}_{\bf c}({\bf x})\nabla_{\widetilde{Q}_{\bf c}({\bf
x})}f(\widetilde{Q}_{\bf c}({\bf x}))$ (3)

where $dim(\nabla h({\bf x},{\bf c}))=(d+m)\times 1,\
dim(\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf
x})))=d\times 1,\ dim(\nabla\widetilde{Q}_{\bf c}({\bf x}))=(d+m)\times d$.
Note that the soft quantization functions of our interest are elementwise
which implies $\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{i}}{\partial
x_{j}}=0$ if $i\neq j$. In particular, for the gradient of the quantization
function we have,

$\displaystyle\nabla_{({\bf x},{\bf c})}\widetilde{Q}_{\bf c}({\bf
x})=\begin{bmatrix}\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{1}}{\partial
x_{1}}&0&\ldots\\\ 0&\frac{\partial\widetilde{Q}_{\bf c}({\bf
x})_{2}}{\partial x_{2}}&0\ldots\\\ \vdots&\vdots&\vdots\\\
\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{1}}{\partial
c_{1}}&\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{2}}{\partial
c_{1}}&\ldots\\\ \vdots&\vdots&\vdots\\\ \frac{\partial\widetilde{Q}_{\bf
c}({\bf x})_{1}}{\partial c_{m}}&\frac{\partial\widetilde{Q}_{\bf c}({\bf
x})_{2}}{\partial c_{m}}&\ldots\end{bmatrix}$ (4)

Moreover for the composite function we have,

$\displaystyle\nabla h({\bf x},{\bf c})=\begin{bmatrix}&\frac{\partial
f}{\partial\widetilde{Q}_{\bf c}({\bf x})_{1}}\frac{\partial\widetilde{Q}_{\bf
c}({\bf x})_{1}}{\partial x_{1}}&+0&+\ldots\\\ &0&+\frac{\partial
f}{\partial\widetilde{Q}_{\bf c}({\bf x})_{2}}\frac{\partial\widetilde{Q}_{\bf
c}({\bf x})_{2}}{\partial x_{2}}&+\ldots\\\ &\vdots\\\ &\frac{\partial
f}{\partial\widetilde{Q}_{\bf c}({\bf x})_{1}}\frac{\partial\widetilde{Q}_{\bf
c}({\bf x})_{1}}{\partial c_{1}}&+\frac{\partial f}{\partial\widetilde{Q}_{\bf
c}({\bf x})_{2}}\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{2}}{\partial
c_{1}}&+\ldots\\\ &\vdots\\\ &\frac{\partial f}{\partial\widetilde{Q}_{\bf
c}({\bf x})_{1}}\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{1}}{\partial
c_{m}}&+\frac{\partial f}{\partial\widetilde{Q}_{\bf c}({\bf
x})_{2}}\frac{\partial\widetilde{Q}_{\bf c}({\bf x})_{2}}{\partial
c_{m}}&+\ldots\end{bmatrix}$ (5)

In (5) and (4) we use $x_{i}$, $c_{j}$ to denote $({\bf x})_{i}$ and $({\bf
c})_{j}$ (i’th, j’th element respectively) for notational simplicity. Now, we
prove two claims that will be useful in the main analysis.

######  Claim 10.

$\displaystyle\|\nabla_{\bf x}f(\widetilde{Q}_{\bf c}({\bf x}))-\nabla_{\bf
y}f(\widetilde{Q}_{\bf c}({\bf y}))\|=\|\nabla h({\bf x},{\bf c})_{1:d}-\nabla
h({\bf y},{\bf c})_{1:d}\|\leq(GL_{Q_{1}}+G_{Q_{1}}Ll_{Q_{1}})\|{\bf x}-{\bf
y}\|$

###### Proof.

$\displaystyle\|\nabla h({\bf x},{\bf c})_{1:d}-\nabla h({\bf y},{\bf
c})_{1:d}\|$ $\displaystyle=\|\nabla_{\bf x}f(\widetilde{Q}_{{\bf c}}({\bf
x}))-\nabla_{\bf y}f(\widetilde{Q}_{{\bf c}}({\bf y}))\|$
$\displaystyle=\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf
c}({\bf x}))\nabla_{\bf x}\widetilde{Q}_{\bf c}({\bf
x})-\nabla_{\widetilde{Q}_{\bf c}({\bf y})}f(\widetilde{Q}_{\bf c}({\bf
y}))\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf y})\|$
$\displaystyle=\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf
c}({\bf x}))\nabla_{\bf x}\widetilde{Q}_{\bf c}({\bf
x})-\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf
x}))\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf y})$
$\displaystyle\quad+\nabla_{\widetilde{Q}_{\bf c}({\bf
x})}f(\widetilde{Q}_{\bf c}({\bf x}))\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf
y})-\nabla_{\widetilde{Q}_{\bf c}({\bf y})}f(\widetilde{Q}_{\bf c}({\bf
y}))\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf y})\|$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\|\nabla_{\widetilde{Q}_{\bf
c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf x}))\|\|\nabla_{\bf
x}\widetilde{Q}_{\bf c}({\bf x})-\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf
y})\|_{F}$ $\displaystyle\quad+\|\nabla_{\bf y}\widetilde{Q}_{\bf c}({\bf
y})\|_{F}\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf
x}))-\nabla_{\widetilde{Q}_{\bf c}({\bf y})}f(\widetilde{Q}_{\bf c}({\bf
y}))\|$ $\displaystyle\leq GL_{Q_{1}}\|{\bf x}-{\bf
y}\|+G_{Q_{1}}L\|\widetilde{Q}_{\bf c}({\bf x})-\widetilde{Q}_{\bf c}({\bf
y})\|$ $\displaystyle\leq GL_{Q_{1}}\|{\bf x}-{\bf
y}\|+G_{Q_{1}}Ll_{Q_{1}}\|{\bf x}-{\bf y}\|$
$\displaystyle=(GL_{Q_{1}}+G_{Q_{1}}Ll_{Q_{1}})\|{\bf x}-{\bf y}\|$

To obtain (a) we have used the fact $\|{\bf A}{\bf x}\|_{2}\leq\|{\bf
A}\|_{F}\|{\bf x}\|_{2}$. ∎

######  Claim 11.

$\displaystyle\|\nabla_{\bf c}f(\widetilde{Q}_{\bf c}({\bf x}))-\nabla_{\bf
d}f(\widetilde{Q}_{\bf d}({\bf x}))\|$ $\displaystyle=\|\nabla h({\bf x},{\bf
c})_{d+1:m}-\nabla h({\bf x},{\bf d})_{d+1:m}\|$
$\displaystyle\leq(GL_{Q_{2}}+G_{Q_{2}}Ll_{Q_{2}})\|{\bf c}-{\bf d}\|$

###### Proof.

We can follow similar steps,

$\displaystyle\|\nabla h({\bf x},{\bf c})_{d+1:m}{-}\nabla h({\bf x},{\bf
d})_{d+1:m}\|$ $\displaystyle=\|\nabla_{\bf c}f(\widetilde{Q}_{{\bf c}}({\bf
x})){-}\nabla_{\bf d}f(\widetilde{Q}_{{\bf d}}({\bf x}))\|$
$\displaystyle=\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf
c}({\bf x}))\nabla_{\bf c}\widetilde{Q}_{\bf c}({\bf
x}){-}\nabla_{\widetilde{Q}_{\bf d}({\bf y})}f(\widetilde{Q}_{\bf d}({\bf
y}))\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf y})\|$
$\displaystyle=\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf
c}({\bf x}))\nabla_{\bf c}\widetilde{Q}_{\bf c}({\bf
x})-\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf
x}))\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf x})$
$\displaystyle\quad+\nabla_{\widetilde{Q}_{\bf c}({\bf
x})}f(\widetilde{Q}_{\bf c}({\bf x}))\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf
y}){-}\nabla_{\widetilde{Q}_{\bf d}({\bf x})}f(\widetilde{Q}_{\bf d}({\bf
y}))\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf y})\|$
$\displaystyle\leq\|\nabla_{\widetilde{Q}_{\bf c}({\bf
x})}f(\widetilde{Q}_{\bf c}({\bf x}))\|\|\nabla_{\bf c}\widetilde{Q}_{\bf
c}({\bf x})-\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf y})\|_{F}$
$\displaystyle\quad+\|\nabla_{\bf d}\widetilde{Q}_{\bf d}({\bf
y})\|_{F}\|\nabla_{\widetilde{Q}_{\bf c}({\bf x})}f(\widetilde{Q}_{\bf c}({\bf
x})){-}\nabla_{\widetilde{Q}_{\bf d}({\bf y})}f(\widetilde{Q}_{\bf d}({\bf
y}))\|$ $\displaystyle\leq GL_{Q_{2}}\|{\bf c}-{\bf
d}\|+G_{Q_{2}}L\|\widetilde{Q}_{\bf c}({\bf x})-\widetilde{Q}_{\bf d}({\bf
x})\|$ $\displaystyle\leq GL_{Q_{2}}\|{\bf c}-{\bf
d}\|+G_{Q_{2}}Ll_{Q_{2}}\|{\bf c}-{\bf d}\|$
$\displaystyle=(GL_{Q_{2}}+G_{Q_{2}}Ll_{Q_{2}})\|{\bf c}-{\bf d}\|$

where $\nabla_{\bf c}\widetilde{Q}_{\bf c}({\bf x})=\nabla\widetilde{Q}_{\bf
c}({\bf x})_{(d+1:d+m,:)}$. ∎

###  A.6 Assumption A.7 is a Corollary of other Assumptions

In this section we discuss how Assumption A.7 can be inferred from A.1-A.5.
Here we drop client indices $i$ for notational simplicity. Let us define
$f_{w}({\bf w})$ as the neural network loss function with model ${\bf w}$.
First we will argue that $f^{KD}({\bf w},{\bf x})$ is smooth, given that
$f_{w}({\bf w})$ and $f({\bf x})$ are two smooth neural network loss functions
with Cross Entropy as the loss function, and that $f_{w}({\bf w})$ and $f({\bf
x})$ have bounded gradients. These two standard assumptions imply the
smoothness of $f^{KD}({\bf w},{\bf x})$ individually with respect to both
input parameters.

######  Proposition 1.

$f^{KD}({\bf w},{\bf x})$ is $L_{D_{1}}$-smooth with respect to ${\bf x}$ and
$L_{D_{2}}$-smooth with respect to ${\bf w}$ for some positive constants
$L_{D_{1}},L_{D_{2}}$.

###### Proof.

Note that $f({\bf x})=\frac{1}{N}\sum_{i=1}^{N}{\bf
y}_{i}^{T}\log(\frac{1}{s({\bf x};\xi_{i})})$ where $i$ denotes the index of
data sample, ${\bf y}_{i}$ is the one hot encoding label vector, $N$ is the
total number of data samples, $\log$ denotes elementwise logarithm and
$\frac{1}{s({\bf x};\xi_{i})}$ denotes elementwise inverse; softmax function
$s({\bf x}):\mathbb{R}^{d}\rightarrow\mathbb{R}^{K}$, where $K$ denotes the
number of classes (similarly $s^{w}({\bf
w}):\mathbb{R}^{d}\rightarrow\mathbb{R}^{K}$ is the function whose output is a
vector of softmax probabilities and input is global model), is defined in
Section 2, here we explicitly state that data samples $\xi_{i}$ is a
parameterization of $s$. Assuming $f({\bf x})$ is smooth for any possible pair
of $({\bf y}_{i},\xi_{i})$ implies $\log(\frac{1}{s({\bf x})_{j}})$ is
$C_{x}$-smooth for some constant $C_{x}$, here we used $s({\bf x})_{j}$ to
denote $j$’th output of $s({\bf x})$ and we omitted $\xi_{i}$ since
$\log(\frac{1}{s({\bf x})_{j}})$ is smooth independent of $\xi_{i}$. Note that
$s({\bf x})_{j}:\mathbb{R}^{d}\rightarrow\mathbb{R}$. We have,

$\displaystyle f^{KD}({\bf w},{\bf x})=\frac{1}{N}\sum_{i=1}^{N}(s^{w}({\bf
w};\xi_{i}))^{T}\log(\frac{s^{w}({\bf w};\xi_{i})}{s({\bf x};\xi_{i})})$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}(s^{w}({\bf
w};\xi_{i}))^{T}\log(s^{w}({\bf w};\xi_{i}))$ $\displaystyle\hskip
28.45274pt+\frac{1}{N}\sum_{i=1}^{N}(s^{w}({\bf
w};\xi_{i}))^{T}\log(\frac{1}{s({\bf x};\xi_{i})})$

where the operations are elementwise as before. In this expression only the
last term depends on ${\bf x}$ and for each $i$, since $s^{w}({\bf
w};\xi_{i})_{j}\leq 1$ with $\sum_{j}s^{w}({\bf w};\xi_{i})_{j}=1$, the
expression is a weighted average of smooth functions $\log(\frac{1}{s({\bf
x})_{j}})$; as a result, $f^{KD}({\bf w},{\bf x})$ is $L_{D_{1}}$-smooth with
respect to ${\bf x}$ for some constant $L_{D_{1}}$.

Now we investigate smoothness with respect to ${\bf w}$. First, note that we
can assume for all $j$ and ${\bf w}$, $s^{w}({\bf w})_{j}$ is lower bounded by
a positive constant $M>0$ and upper bounded by a positive constant $P<1$
since, by definition, output vector of the softmax function contains values
between 0 and 1 (we ignore the limiting case when a logit is infinitely
large). Then, note that assuming a gradient bound on $f_{w}({\bf
w})=\frac{1}{N}\sum_{i=1}^{N}{\bf y}_{i}^{T}\log(\frac{1}{s({\bf
w};\xi_{i})})$ implies that for all $j$ $\|\nabla\log(\frac{1}{s^{w}({\bf
w})_{j}})\|=\|\frac{\nabla s^{w}({\bf w})_{j}}{s^{w}({\bf w})_{j}}\|\leq
G_{w}$ for some constant $G_{w}$ (again the division operation is
elementwise); since $0<s^{w}({\bf w})_{j}<1$ we have $\|\nabla s^{w}({\bf
w})_{j}\|\leq G_{w}$. Moreover, similar to the first part, by assuming
$f_{w}({\bf w})$ is smooth we obtain that $\log(\frac{1}{s^{w}({\bf w})_{j}})$
is smooth for all $j$. This implies having a bounded Hessian:

$\displaystyle\text{ for some constant $C$ we have
}C\geq\Big{\|}\nabla^{2}\log(\frac{1}{s^{w}({\bf w})_{j}})\Big{\|}_{F}$
$\displaystyle=\Big{\|}\frac{\nabla s^{w}({\bf w})_{j}\nabla s^{w}({\bf
w})_{j}^{T}}{s^{w}({\bf w})_{j}^{2}}-\frac{\nabla^{2}s^{w}({\bf
w})_{j}}{s^{w}({\bf w})_{j}}\Big{\|}_{F}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\Big{|}\Big{\|}\frac{\nabla
s^{w}({\bf w})_{j}\nabla s^{w}({\bf w})_{j}^{T}}{s^{w}({\bf
w})_{j}}\Big{\|}_{F}-\Big{\|}\nabla^{2}s^{w}({\bf w})_{j}\Big{\|}_{F}\Big{|}$
$\displaystyle=\Big{|}\frac{G_{w}^{2}}{s^{w}({\bf
w})_{j}}-\Big{\|}\nabla^{2}s^{w}({\bf w})_{j}\Big{\|}_{F}\Big{|}$
$\displaystyle\geq\Big{\|}\nabla^{2}s^{w}({\bf
w})_{j}\Big{\|}_{F}-\frac{G_{w}^{2}}{s^{w}({\bf w})_{j}}$
$\displaystyle\geq\Big{\|}\nabla^{2}s^{w}({\bf
w})_{j}\Big{\|}_{F}-\frac{G_{w}^{2}}{M}$

where (a) is due to reverse triangular inequality and $0<s^{w}({\bf
w})_{j}<1$. As a result we obtain
$C+\frac{G_{w}^{2}}{M}\geq\Big{\|}\nabla^{2}s^{w}({\bf w})_{j}\Big{\|}_{F}$
for all $j$, i.e., $s^{w}({\bf w})_{j}$ is $L_{S}$-smooth with some constant
$L_{S}\leq C+\frac{G_{w}^{2}}{M}$. Thus, both $s^{w}({\bf w})_{j}$ and
$\log(s^{w}({\bf w})_{j})$ are smooth functions. Note both $s^{w}({\bf
w})_{j}$ and $\log(s^{w}({\bf w})_{j})$ are bounded functions. Consequently,
the first summation term in the definition of $f^{KD}({\bf w},{\bf x})$
consists of the sum of product of bounded and smooth functions and the second
term consists of sum of smooth functions multiplied with positive constants
(as $\log(\frac{1}{s({\bf x};\xi_{i})})$ does not depend on ${\bf w}$). Using
Fact 3 and Fact 4 we conclude there exists a constant $L_{D_{2}}$ such that
$f^{KD}({\bf w},{\bf x})$ is $L_{D_{2}}$-smooth w.r.t ${\bf w}$. ∎

######  Proposition 2.

$f^{KD}({\bf w},\widetilde{Q}_{{\bf c}}({\bf x}))$ is $L_{DQ_{1}}$-smooth with
respect to ${\bf x}$, $L_{DQ_{2}}$-smooth with respect to ${\bf c}$, and
$L_{DQ_{3}}$-smooth with respect to ${\bf w}$ for some constants
$L_{DQ_{1}},L_{DQ_{2}},L_{DQ_{3}}$.

###### Proof.

The proof is exactly the same as in Proposition 1, instead of using smoothness
of $f({\bf x})$, using smoothness of $f(\widetilde{Q}_{{\bf c}}({\bf x}))$
with respect to ${\bf x},{\bf c}$ from Claims 10 and 11 gives the result. ∎

##  Appendix B Omitted Details in Proof of Theorem 1

First we derive the optimization problems that the alternating updates
correspond to. Remember we had the following alternating updates:

$\displaystyle{\bf x}^{t+1}=\text{prox}_{\eta_{1}\lambda R_{{\bf c}^{t}}}({\bf
x}^{t}-\eta_{1}\nabla f({\bf x}^{t})-\eta_{1}\nabla_{{\bf
x}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf x}^{t})))$ $\displaystyle{\bf
c}^{t+1}=\text{prox}_{\eta_{2}\lambda R_{{\bf x}^{t+1}}}({\bf
c}^{t}-\eta_{2}\nabla_{{\bf c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t+1})))$

For ${\bf x}^{t+1}$, from the definition of proximal mapping we have:

$\displaystyle{\bf x}^{t+1}$ $\displaystyle=\underset{{\bf
x}\in\mathbb{R}^{d}}{\arg\min}\left\\{\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
x}^{t}+\eta_{1}\nabla_{{\bf x}^{t}}f\left({\bf
x}^{t}\right)+\eta_{1}\nabla_{{\bf x}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t}))\right\|_{2}^{2}+\lambda R({\bf x},{\bf c}^{t})\right\\}$
$\displaystyle=\underset{{\bf
x}\in\mathbb{R}^{d}}{\arg\min}\Big{\\{}\left\langle{\bf x}-{\bf
x}^{t},\nabla_{{\bf x}^{t}}f\left({\bf
x}^{t}\right)\right\rangle+\left\langle{\bf x}-{\bf x}^{t},\nabla_{{\bf
x}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t}))\right\rangle+\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
x}^{t}\right\|_{2}^{2}$ $\displaystyle\hskip
56.9055pt+\frac{\eta_{1}}{2}\|\nabla_{{\bf x}^{t}}f({\bf x}^{t})+\nabla_{{\bf
x}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf x}^{t}))\|^{2}+\lambda R({\bf
x},{\bf c}^{t})\Big{\\}}$ $\displaystyle=\underset{{\bf
x}\in\mathbb{R}^{d}}{\arg\min}\Big{\\{}\left\langle{\bf x}-{\bf
x}^{t},\nabla_{{\bf x}^{t}}f\left({\bf
x}^{t}\right)\right\rangle+\left\langle{\bf x}-{\bf x}^{t},\nabla_{{\bf
x}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t}))\right\rangle+\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
x}^{t}\right\|_{2}^{2}$ $\displaystyle\hskip 56.9055pt+\lambda R({\bf x},{\bf
c}^{t})\Big{\\}}$ (6)

Note, in the third equality we remove the terms that do not depend on ${\bf
x}$. Similarly, for ${\bf c}^{t+1}$ we have:

$\displaystyle{\bf c}^{t+1}$ $\displaystyle=\underset{{\bf
c}\in\mathbb{R}^{m}}{\arg\min}\left\\{\frac{1}{2\eta_{2}}\left\|{\bf c}-{\bf
c}^{t}+\eta_{2}\nabla_{{\bf c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t+1}))\right\|_{2}^{2}+\lambda R({\bf x}^{t+1},{\bf c})\right\\}$
$\displaystyle=\underset{{\bf
c}\in\mathbb{R}^{m}}{\arg\min}\Big{\\{}\left\langle{\bf c}-{\bf
c}^{t},\nabla_{{\bf c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t+1}))\right\rangle+\frac{1}{2\eta_{2}}\left\|{\bf c}-{\bf
c}^{t}\right\|_{2}^{2}+\frac{\eta_{2}}{2}\|\nabla_{{\bf
c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf x}^{t+1}))\|^{2}$
$\displaystyle\hskip 56.9055pt+\lambda R({\bf x}^{t+1},{\bf c})\Big{\\}}$
$\displaystyle=\underset{{\bf
c}\in\mathbb{R}^{m}}{\arg\min}\left\\{\left\langle{\bf c}-{\bf
c}^{t},\nabla_{{\bf c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t+1}))\right\rangle+\frac{1}{2\eta_{2}}\left\|{\bf c}-{\bf
c}^{t}\right\|_{2}^{2}+\lambda R({\bf x}^{t+1},{\bf c})\right\\}$ (7)

Minimization problems in (B) and (B) are the main problems to characterize the
update rules and we use them in multiple places throughout the section.

######  Claim (Restating Claim 1).

$f({\bf x})+f(\widetilde{Q}_{\bf c}({\bf x}))$ is
$(L+GL_{Q_{1}}+G_{Q_{1}}LL_{Q_{1}})$-smooth with respect to ${\bf x}$.

###### Proof.

From our assumptions, we have $f$ is $L$-smooth. And from Claim 10 we have
$f(\widetilde{Q}_{\bf c}({\bf x}))$ is
$(GL_{Q_{1}}+G_{Q_{1}}LL_{Q_{1}})$-smooth. Using the fact that if two
functions $g_{1}$ and $g_{2}$ are $L_{1}$ and $L_{2}$ smooth respectively,
then $g_{1}+g_{2}$ is $(L_{1}+L_{2})$-smooth concludes the proof. ∎

######  Claim (Restating Claim 2).

Let

$\displaystyle A({\bf x}^{t+1})$ $\displaystyle:=\lambda R({\bf x}^{t+1},{\bf
c}^{t})+\left\langle\nabla f({\bf x}^{t}),{\bf x}^{t+1}-{\bf
x}^{t}\right\rangle+\left\langle\nabla_{{\bf x}^{t}}f(\widetilde{Q}_{{\bf
c}^{t}}({\bf x}^{t})),{\bf x}^{t+1}-{\bf x}^{t}\right\rangle$
$\displaystyle\hskip 56.9055pt+\frac{1}{2\eta_{1}}\|{\bf x}^{t+1}-{\bf
x}^{t}\|^{2}$ $\displaystyle A({\bf x}^{t})$ $\displaystyle:=\lambda R({\bf
x}^{t},{\bf c}^{t}).$

Then $A({\bf x}^{t+1})\leq A({\bf x}^{t})$.

###### Proof.

Let $A({\bf x})$ denote the expression inside the $\arg\min$ in (B) and we
know that (B) is minimized when ${\bf x}={\bf x}^{t+1}$. So we have $A({\bf
x}^{t+1})\leq A({\bf x}^{t})$. This proves the claim. ∎

######  Claim (Restating Claim 3).

Let

$\displaystyle B({\bf c}^{t+1})$ $\displaystyle:=\lambda R({\bf x}^{t+1},{\bf
c}^{t+1})+\left\langle\nabla_{{\bf c}^{t}}f(\widetilde{Q}_{{\bf c}^{t}}({\bf
x}^{t+1})),{\bf c}^{t+1}-{\bf c}^{t}\right\rangle+\frac{1}{2\eta_{1}}\|{\bf
c}^{t+1}-{\bf c}^{t}\|^{2}$ $\displaystyle B({\bf c}^{t})$
$\displaystyle:=\lambda R({\bf x}^{t+1},{\bf c}^{t}).$

Then $B({\bf c}^{t+1})\leq B({\bf c}^{t})$.

###### Proof.

Let $B({\bf c})$ denote the expression inside the $\arg\min$ in (B) and we
know that (B) is minimized when ${\bf c}={\bf c}^{t+1}$. So we have $B({\bf
c}^{t+1})\leq B({\bf c}^{t})$. This proves the claim. ∎

##  Appendix C Omitted Details in Proof of Theorem 2

######  Claim (Restating Claim 4.).

$(1-\lambda_{p})(f_{i}({\bf x})+f_{i}(\widetilde{Q}_{\bf c}({\bf
x})))+\lambda_{p}(f^{KD}_{i}({\bf x},{\bf w})+f^{KD}_{i}(\widetilde{Q}_{\bf
c}({\bf x}),{\bf w}))$ is
$(\lambda_{p}(L_{D_{1}}+L_{DQ_{1}})+(1-\lambda_{p})(L+G^{(i)}L_{Q_{1}}+G^{(i)}_{Q_{1}}Ll_{Q_{1}}))$-smooth
with respect to ${\bf x}$.

###### Proof.

From our assumptions, we have $f_{i}$ is $L$-smooth, $f^{KD}_{i}({\bf x},{\bf
w})$ is $L_{D_{1}}$-smooth and $f^{KD}_{i}(\widetilde{Q}_{\bf c}({\bf x}),{\bf
w})$ is $L_{DQ_{1}}$-smooth with respect to ${\bf x}$. And applying the Claim
10 to each client separately gives that $f_{i}(\widetilde{Q}_{\bf c}({\bf
x}))$ is $(G^{(i)}L_{Q_{1}}+G^{(i)}_{Q_{1}}Ll_{Q_{1}})$-smooth. Using the fact
that if two functions $g_{1}$ and $g_{2}$ (defined over the same space) are
$L_{1}$ and $L_{2}$-smooth respectively, then $g_{1}+g_{2}$ is
$(L_{1}+L_{2})$-smooth, and the fact that $\alpha g_{1}$ is $\alpha
L_{1}$-smooth for a given constant $\alpha$ concludes the proof. ∎

######  Claim (Restating Claim 5.).

Let

$\displaystyle A({\bf x}^{t+1}_{i})$
$\displaystyle:=(1-\lambda_{p})\left\langle\nabla f_{i}({\bf x}^{t}_{i}),{\bf
x}^{t+1}_{i}-{\bf
x}^{t}_{i}\right\rangle+(1-\lambda_{p})\left\langle\nabla_{{\bf
x}^{t}_{i}}f_{i}(\widetilde{Q}_{{\bf c}^{t}_{i}}({\bf x}^{t}_{i})),{\bf
x}^{t+1}_{i}-{\bf x}^{t}_{i}\right\rangle$ $\displaystyle\hskip
28.45274pt+\left\langle\lambda_{p}(\nabla_{{\bf x}^{t}_{i}}f^{KD}_{i}({\bf
x}^{t}_{i},{\bf w}^{t}_{i})),{\bf x}^{t+1}_{i}-{\bf
x}^{t}_{i}\right\rangle+\left\langle\lambda_{p}(\nabla_{{\bf
x}^{t}_{i}}f^{KD}_{i}(\widetilde{Q}_{{\bf c}^{t}_{i}}({\bf x}^{t}_{i}),{\bf
w}^{t}_{i})),{\bf x}^{t+1}_{i}-{\bf x}^{t}_{i}\right\rangle$
$\displaystyle\hskip 28.45274pt+\lambda R({\bf x}^{t+1}_{i},{\bf
c}^{t}_{i})+\frac{1}{2\eta_{1}}\|{\bf x}^{t+1}_{i}-{\bf x}^{t}_{i}\|^{2}$
$\displaystyle A({\bf x}^{t}_{i})$ $\displaystyle:=\lambda R({\bf
x}^{t}_{i},{\bf c}^{t}_{i}).$

Then $A({\bf x}^{t+1}_{i})\leq A({\bf x}^{t}_{i})$.

###### Proof.

Let $A({\bf x})$ denote the expression inside the $\arg\min$ in (17) and we
know that (17) is minimized when ${\bf x}={\bf x}^{t+1}_{i}$. So we have
$A({\bf x}^{t+1}_{i})\leq A({\bf x}^{t}_{i})$. This proves the claim. ∎

######  Claim (Restating Claim 6.).

$(1-\lambda_{p})f_{i}(\widetilde{Q}_{\bf c}({\bf
x}))+\lambda_{p}f^{KD}_{i}(\widetilde{Q}_{{\bf c}}({\bf x}),{\bf w}))$ is
$(\lambda_{p}L_{DQ_{2}}+(1-\lambda_{p})(G^{(i)}L_{Q_{2}}+G^{(i)}_{Q_{2}}Ll_{Q_{2}}))$-smooth
with respect to ${\bf c}$.

###### Proof.

Proof is similar to the proof of Claim 4. ∎

######  Claim (Restating Claim 7.).

Let

$\displaystyle B({\bf c}^{t+1}_{i})$ $\displaystyle:=\lambda R({\bf
x}^{t+1}_{i},{\bf c}^{t+1}_{i})+(1-\lambda_{p})\left\langle\nabla_{{\bf
c}^{t}_{i}}f_{i}(\widetilde{Q}_{{\bf c}^{t}_{i}}({\bf x}^{t+1}_{i})),{\bf
c}^{t+1}_{i}-{\bf c}^{t}_{i}\right\rangle$
$\displaystyle\quad+\lambda_{p}\left\langle\nabla_{{\bf
c}^{t}_{i}}f^{KD}_{i}(\widetilde{Q}_{{\bf c}^{t}_{i}}({\bf x}^{t+1}_{i}),{\bf
w}^{t}_{i}),{\bf c}^{t+1}_{i}-{\bf
c}^{t}_{i}\right\rangle+\frac{1}{2\eta_{2}}\|{\bf c}^{t+1}_{i}-{\bf
c}^{t}_{i}\|^{2}$ $\displaystyle B({\bf c}^{t}_{i})$ $\displaystyle:=\lambda
R({\bf x}^{t+1}_{i},{\bf c}^{t}_{i}).$

Then $B({\bf c}^{t+1}_{i})\leq B({\bf c}^{t}_{i})$.

###### Proof.

Let $B({\bf c})$ denote the expression inside the $\arg\min$ in (18) and we
know that (18) is minimized when ${\bf c}={\bf c}^{t+1}_{i}$. So we have
$B({\bf c}^{t+1}_{i})\leq B({\bf c}^{t}_{i})$. This proves the claim. ∎

Obtaining (7.1.3),

$\displaystyle F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t+1})\leq
F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})+\left\langle\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf w}^{t}),{\bf w}^{t+1}-{\bf w}^{t}\right\rangle$
$\displaystyle\hskip
142.26378pt+\frac{\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})}{2}\|{\bf w}^{t+1}-{\bf
w}^{t}\|^{2}$ $\displaystyle=F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})-\left\langle\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf w}^{t}),\eta_{3}{\bf
g}^{t}\right\rangle+\frac{\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})}{2}\|\eta_{3}{\bf
g}^{t}\|^{2}$ $\displaystyle=F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})$ $\displaystyle\quad-\eta_{3}\left\langle\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t}),{\bf
g}^{t}-\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})+\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\right\rangle$
$\displaystyle\quad+\frac{\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})}{2}\eta_{3}^{2}\|{\bf
g}^{t}-\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})+\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\|^{2}$ $\displaystyle=F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})-\eta_{3}\Big{\|}\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\quad-\eta_{3}\left\langle\nabla_{{\bf w}^{t}}F_{i}({\bf
x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t}),{\bf g}^{t}-\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\right\rangle$
$\displaystyle\quad+\frac{\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})}{2}\eta_{3}^{2}\|{\bf
g}^{t}-\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})+\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\|^{2}$ $\displaystyle\leq F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf w}^{t})-\eta_{3}\Big{\|}\nabla_{{\bf w}^{t}}F_{i}({\bf
x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\Big{\|}^{2}+\frac{\eta_{3}}{2}\Big{\|}\nabla_{{\bf w}^{t}}F_{i}({\bf
x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\quad+\frac{\eta_{3}}{2}\Big{\|}{\bf g}^{t}-\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\Big{\|}^{2}+\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2}\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\Big{\|}^{2}$
$\displaystyle\quad+\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2}\Big{\|}\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle=F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})-(\frac{\eta_{3}}{2}-\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\quad+(\frac{\eta_{3}}{2}+\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})+\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf w}^{t}_{i})$ $\displaystyle\quad-\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\leq F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})-(\frac{\eta_{3}}{2}-\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\quad+(\eta_{3}+2\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})\Big{\|}^{2}$
$\displaystyle\quad+(\eta_{3}+2\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}\nabla_{{\bf
w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})-\nabla_{{\bf w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t})\Big{\|}^{2}$ $\displaystyle\leq F_{i}({\bf x}^{t+1}_{i},{\bf
c}^{t+1}_{i},{\bf
w}^{t})-(\frac{\eta_{3}}{2}-\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}\nabla_{{\bf
w}^{t}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t})\Big{\|}^{2}$
$\displaystyle\quad+(\eta_{3}+2\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})\Big{\|}^{2}$
$\displaystyle\quad+(\eta_{3}+2\lambda_{p}(L_{D_{2}}+L_{DQ_{3}})\eta_{3}^{2})(\lambda_{p}(L_{D_{2}}+L_{DQ_{3}}))^{2}\Big{\|}{\bf
w}^{t}_{i}-{\bf w}^{t}\Big{\|}^{2}.$

Rearranging the terms gives (7.1.3),

######  Lemma (Restating Lemma 1).

Let $\eta_{3}$ be chosen such that
$\eta_{3}\leq\sqrt{\frac{1}{6\tau^{2}(\lambda_{p}L_{w})^{2}\left(1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\right)}}$
where $L^{(\min)}_{\max}=\min\\{L^{(i)}_{\max}:i\in[n]\\}$ and
$\overline{L}_{\max}=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}}$
(where $L^{(i)}_{\max}$ is defined in (36)), then we have,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\|{\bf
w}^{t}-{\bf w}^{t}_{i}\|^{2}\leq\frac{1}{T}\sum_{t=0}^{T-1}\gamma_{t}\leq
6\tau^{2}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$

###### Proof.

Let $t_{c}$ be the latest synchronization time before $t$. Define
$\gamma_{t}=\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\|{\bf w}^{t}-{\bf
w}^{t}_{i}\|^{2}$. Then:

$\displaystyle\gamma_{t}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{\|}{\bf
w}^{t_{c}}-\frac{\eta_{3}}{n}\sum_{j=t_{c}}^{t}\sum_{k=1}^{n}\nabla_{{\bf
w}^{j}_{k}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf w}^{j}_{k})$
$\displaystyle\hskip 28.45274pt-({\bf
w}^{t_{c}}-\eta_{3}\sum_{j=t_{c}}^{t}\nabla_{{\bf w}^{j}_{i}}F_{i}({\bf
x}^{j+1}_{i},{\bf c}^{j+1}_{i},{\bf w}^{j}_{i})\Big{\|}^{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\tau\sum_{j=t_{c}}^{t}\frac{\eta_{3}^{2}}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{\|}\frac{1}{n}\sum_{k=1}^{n}\nabla_{{\bf
w}^{j}_{k}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf
w}^{j}_{k})-\nabla_{{\bf w}^{j}_{i}}F_{i}({\bf x}^{j+1}_{i},{\bf
c}^{j+1}_{i},{\bf w}^{j}_{i})\Big{\|}^{2}$ ($\star 1$)
$\displaystyle=\tau\sum_{j=t_{c}}^{t}\frac{\eta_{3}^{2}}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{[}\Big{\|}\frac{1}{n}\sum_{k=1}^{n}\Big{(}\nabla_{{\bf
w}^{j}_{k}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf
w}^{j}_{k})-\nabla_{{\bf w}^{j}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf
w}^{j})$ $\displaystyle\hskip 28.45274pt+\nabla_{{\bf w}^{j}}F_{k}({\bf
x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf w}^{j})\Big{)}-\nabla_{{\bf
w}^{j}}F_{i}({\bf x}^{j+1}_{i},{\bf c}^{j+1}_{i},{\bf w}^{j})+\nabla_{{\bf
w}^{j}}F_{i}({\bf x}^{j+1}_{i},{\bf c}^{j+1}_{i},{\bf w}^{j})$
$\displaystyle\hskip 28.45274pt-\nabla_{{\bf w}^{j}_{i}}F_{i}({\bf
x}^{j+1}_{i},{\bf c}^{j+1}_{i},{\bf w}^{j}_{i}\Big{\|}^{2}\Big{]}$
$\displaystyle\leq\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\frac{\eta_{3}^{2}}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{[}\Big{\|}\frac{1}{n}\sum_{k=1}^{n}\left(\nabla_{{\bf
w}^{j}_{k}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf
w}^{j}_{k})-\nabla_{{\bf w}^{j}}F_{k}({\bf x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf
w}^{j})\right)\Big{\|}^{2}$ $\displaystyle\hskip
28.45274pt+\Big{\|}\frac{1}{n}\sum_{k=1}^{n}\nabla_{{\bf w}^{j}}F_{k}({\bf
x}^{j+1}_{k},{\bf c}^{j+1}_{k},{\bf w}^{j})-\nabla_{{\bf w}^{j}}F_{i}({\bf
x}^{j+1}_{i},{\bf c}^{j+1}_{i},{\bf w}^{j})\Big{\|}^{2}$ $\displaystyle\hskip
28.45274pt+\Big{\|}\nabla_{{\bf w}^{j}}F_{i}({\bf x}^{j+1}_{i},{\bf
c}^{j+1}_{i},{\bf w}^{j})-\nabla_{{\bf w}^{j}_{i}}F_{i}({\bf x}^{j+1}_{i},{\bf
c}^{j+1}_{i},{\bf w}^{j}_{i}\Big{\|}^{2}\Big{]}$
$\displaystyle\leq\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\eta_{3}^{2}\Big{[}\frac{(\lambda_{p}L_{w})^{2}n}{n^{2}}\sum_{k=1}^{n}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\|{\bf
w}^{j}_{k}-{\bf
w}^{j}\|^{2}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$
$\displaystyle\hskip
28.45274pt+(\lambda_{p}L_{w})^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\|{\bf
w}^{j}-{\bf w}^{j}_{i}\|^{2}\Big{]}$
$\displaystyle\leq\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\eta_{3}^{2}\Big{[}\frac{(\lambda_{p}L_{w})^{2}n}{n^{2}}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\frac{1}{(L^{(\min)}_{\max})^{2}}\sum_{k=1}^{n}(L^{(k)}_{\max})^{2}\|{\bf
w}^{j}_{k}-{\bf w}^{j}\|^{2}$ $\displaystyle\hskip
28.45274pt+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}+(\lambda_{p}L_{w})^{2}\gamma_{j}\|^{2}\Big{]}$
$\displaystyle=\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\eta_{3}^{2}\left((\lambda_{p}L_{w})^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\frac{1}{(L^{(\min)}_{\max})^{2}}\gamma_{j}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}+(\lambda_{p}L_{w})^{2}\gamma_{j}\right)$
$\displaystyle=\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\eta_{3}^{2}\left((\lambda_{p}L_{w})^{2}\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\gamma_{j}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}+(\lambda_{p}L_{w})^{2}\gamma_{j}\right)$
($\star 2$)

in (a) we use the facts that $\|\sum_{i=1}^{K}a_{i}\|^{2}\leq
K\sum_{i=1}^{K}\|a_{i}\|^{2}$, $t\leq\tau+t_{c}$ and that we are summing over
non-negative terms. As a result, we have:

$\displaystyle\gamma_{t}$
$\displaystyle\leq\tau\sum_{j=t_{c}}^{t_{c}+\tau}3\eta_{3}^{2}\left((\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\gamma_{j}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}\right)$
$\displaystyle\Longrightarrow\sum_{t=t_{c}}^{t_{c}+\tau}\gamma_{t}$
$\displaystyle\leq\sum_{t=t_{c}}^{t_{c}+\tau}\sum_{j=t_{c}}^{t_{c}+\tau}3\tau\eta_{3}^{2}\left((\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\gamma_{j}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}\right)$
$\displaystyle=3\tau^{2}\eta_{3}^{2}(\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\sum_{j=t_{c}}^{t_{c}+\tau}\gamma_{j}+3\tau^{3}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$

Let us choose $\eta_{3}$ such that
$3\tau^{2}\eta_{3}^{2}(\lambda_{p}L_{w})^{2}\left(1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\right)\leq\frac{1}{2}\Leftrightarrow\eta_{3}\leq\sqrt{\frac{1}{6\tau^{2}(\lambda_{p}L_{w})^{2}\left(1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\right)}}$,
sum over all syncronization times, and divide both sides by $T$:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\gamma_{t}\leq\frac{1}{2}\sum_{j=0}^{T-1}\gamma_{j}+3\tau^{2}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$
$\displaystyle\Longrightarrow$
$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\gamma_{t}\leq
6\tau^{2}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$

∎

######  Corollary (Restating Corollary 1.).

Recall, ${\bf g}^{t}=\frac{1}{n}\sum_{i=1}^{n}\nabla_{{\bf w}^{t}}F_{i}({\bf
x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf w}^{t}_{i})$. Then, we have:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})\Big{\|}^{2}$ $\displaystyle\leq
3\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$
$\displaystyle+3(\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}6\tau^{2}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i},$

where $L^{(i)}_{\max}$ is defined in (36), and
$\overline{L}_{\max},L^{(\min)}_{\max}$ are defined in Lemma 1.

###### Proof.

fl From ($\star 1$) $\leq$ ($\star 2$) in the proof of Lemma 1, we have:

$\displaystyle\sum_{t=t_{c}}^{t_{c}+\tau}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})\Big{\|}^{2}$ $\displaystyle\hskip
85.35826pt\leq\sum_{t=t_{c}}^{t_{c}+\tau}3\left((\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\gamma_{t}+\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}\right)$

Summing over all $t_{c}$ and dividing by $T$:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\Big{\|}{\bf
g}^{t}-\nabla_{{\bf w}^{t}_{i}}F_{i}({\bf x}^{t+1}_{i},{\bf c}^{t+1}_{i},{\bf
w}^{t}_{i})\Big{\|}^{2}$ $\displaystyle\hskip 56.9055pt\leq
3(\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\frac{1}{T}\sum_{t=0}^{T-1}\gamma_{t}+3\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}$
$\displaystyle\hskip
56.9055pt\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}3(\lambda_{p}L_{w})^{2}\Big{(}1+\frac{\overline{L}_{\max}^{2}}{(L^{(\min)}_{\max})^{2}}\Big{)}\times
6\tau^{2}\eta_{3}^{2}\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i}+3\frac{1}{n}\sum_{i=1}^{n}(L^{(i)}_{\max})^{2}\kappa_{i},$

where (a) is from Lemma 1. ∎

##  Appendix D Additional Details for Experiments

In this section, we first discuss the implementation details for the prox
steps for Algorithm 1 and Algorithm 2 in Section D.1. Section D.2 discusses
implementation details for the algorithms along with hyperparameters which was
omitted in Section 5 of the main paper due to space constraints.

###  D.1 Proximal Updates

For the implementation of Algorithm 1,2, we consider $\ell_{1}$-loss for the
distance function $R({\bf x},{\bf c})$. In other words, $R({\bf x},{\bf
c})=\min\\{\frac{1}{2}\|{\bf z}-{\bf
x}\|_{1}:z_{i}\in\\{c_{1},\cdots,c_{m}\\},\forall i\\}$. For simplicity, we
define $\mathcal{C}=\\{{\bf z}:z_{i}\in\\{c_{1},\cdots,c_{m}\\},\forall i\\}$.
For the first type of update (update of ${\bf x}$) we have:

$\displaystyle\text{prox}_{\eta_{1}\lambda R(\cdot,{\bf c})}({\bf y})$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
x}\in\mathbb{R}^{d}}}\left\\{\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
y}\right\|_{2}^{2}+\lambda R({\bf x},{\bf c})\right\\}$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
x}\in\mathbb{R}^{d}}}\left\\{\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
y}\right\|_{2}^{2}+\frac{\lambda}{2}\min_{{\bf z}\in\mathcal{C}}\|{\bf z}-{\bf
x}\|_{1}\right\\}$ $\displaystyle={\operatorname*{arg\,min}_{{\bf
x}\in\mathbb{R}^{d}}}\min_{{\bf
z}\in\mathcal{C}}\left\\{\frac{1}{2\eta_{1}}\left\|{\bf x}-{\bf
y}\right\|_{2}^{2}+\frac{\lambda}{2}\|{\bf z}-{\bf x}\|_{1}\right\\}$

This corresponds to solving:

$\displaystyle\min_{{\bf z}\in\mathcal{C}}{\min_{{\bf
x}\in\mathbb{R}^{d}}}\left\\{\frac{1}{\eta_{1}}\left\|{\bf x}-{\bf
y}\right\|_{2}^{2}+\lambda\|{\bf z}-{\bf x}\|_{1}\right\\}$

Since both $\ell_{1}$ and squared $\ell_{2}$ norms are decomposable; if we fix
${\bf z}$, for the inner problem we have the following solution to soft
thresholding:

$\displaystyle x^{\star}({\bf
z})_{i}=\begin{cases}y_{i}-\frac{\lambda\eta_{1}}{2},\quad\text{if
}y_{i}-\frac{\lambda\eta_{1}}{2}>z_{i}\\\
y_{i}+\frac{\lambda\eta_{1}}{2},\quad\text{if
}y_{i}+\frac{\lambda\eta_{1}}{2}<z_{i}\\\
z_{i},\quad\text{otherwise}\end{cases}$ (9)

As a result we have:

$\displaystyle\min_{{\bf
z}\in\mathcal{C}}\left\\{\frac{1}{\eta_{1}}\left\|x^{\star}({\bf z})-{\bf
y}\right\|_{2}^{2}+\lambda\|{\bf z}-x^{\star}({\bf z})\|_{1}\right\\}$

This problem is separable, in other words we have:

$\displaystyle{\bf
z}^{\star}_{i}=\operatorname*{arg\,min}_{z_{i}\in\\{c_{1},\cdots,c_{m}\\}}\left\\{\frac{1}{\eta_{1}}(x^{\star}({\bf
z})_{i}-y_{i})^{2}+\lambda|z_{i}-x^{\star}({\bf z})_{i}|\right\\}\ \forall i$

Substituting $x^{\star}({\bf z})_{i}$ and solving for $z_{i}$ gives us:

$\displaystyle{\bf
z}^{\star}_{i}=\operatorname*{arg\,min}_{z_{i}\in\\{c_{1},\cdots,c_{m}\\}}\left\\{|z_{i}-y_{i}|\right\\}\
\forall i$

Or equivalently we have,

$\displaystyle{\bf z}^{\star}=\operatorname*{arg\,min}_{{\bf
z}\in\mathcal{C}}\|{\bf z}-{\bf y}\|_{1}=Q_{\bf c}({\bf y})$ (10)

As a result, $\text{prox}_{\eta_{1}\lambda R(\cdot,{\bf c})}(\cdot)$ becomes
the soft thresholding operator:

$\displaystyle\text{prox}_{\eta_{1}\lambda R(\cdot,{\bf c})}({\bf
y})_{i}=\begin{cases}y_{i}-\frac{\lambda\eta_{1}}{2},\quad\text{if }y_{i}\geq
Q_{\bf c}({\bf y})_{i}+\frac{\lambda\eta_{1}}{2}\\\
y_{i}+\frac{\lambda\eta_{1}}{2},\quad\text{if }y_{i}\leq Q_{\bf c}({\bf
y})_{i}-\frac{\lambda\eta_{1}}{2}\\\ Q_{\bf c}({\bf
y})_{i},\quad\text{otherwise}\end{cases}$ (11)

And for the second type of update we have $\text{prox}_{\eta_{2}\lambda R({\bf
x},\cdot)}(\cdot)$ becomes:

$\displaystyle\text{prox}_{\eta_{2}\lambda R({\bf x},\cdot)}(\bm{\mu})$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
c}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}\left\|{\bf
c}-\bm{\mu}\right\|_{2}^{2}+\lambda R({\bf x},{\bf c})\right\\}$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
c}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}\left\|{\bf
c}-\bm{\mu}\right\|_{2}^{2}+\frac{\lambda}{2}\min_{{\bf z}\in\cal C}\|{\bf
z}-{\bf x}\|_{1}\right\\}$ $\displaystyle={\operatorname*{arg\,min}_{{\bf
c}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}\left\|{\bf
c}-\bm{\mu}\right\|_{2}^{2}+\frac{\lambda}{2}\|Q_{\bf c}({\bf x})-{\bf
x}\|_{1}\right\\}$ (12)

Then,

$\displaystyle\text{prox}_{\eta_{2}\lambda R({\bf x},\cdot)}(\bm{\mu})_{j}$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
c}_{j}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}(c_{j}-\mu_{j})^{2}+\frac{\lambda}{2}\sum_{i=1}^{d}|Q_{\bf
c}({\bf x})_{i}-x_{i}|\right\\}$
$\displaystyle={\operatorname*{arg\,min}_{{\bf
c}_{j}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}(c_{j}-\mu_{j})^{2}+\frac{\lambda}{2}\sum_{i=1}^{d}\mathbbm{1}(Q_{{\bf
c}}({\bf x})_{i}=c_{j})|c_{j}-x_{i}|\right\\}$

We remark that the second term of the optimization problem is hard to solve;
in particular we need to know the assignments of $x_{i}$ to $c_{j}$. In the
algorithm, at each time point $t$, we are given the previous epoch’s
assignments. We can utilize that and approximate the optimization problem by
assuming ${\bf c}^{t+1}$ will be in a neighborhood of ${\bf c}^{t}$. We can
take the gradient of $R({\bf x}^{t+1},{\bf c})$ at ${\bf c}={\bf c}^{t}$ while
finding the optimal point. This is also equivalent to optimizing the first
order Taylor approximation around ${\bf c}={\bf c}^{t}$. As a result we have
the following optimization problem:

$\displaystyle\text{prox}_{\eta_{2}\lambda R({\bf
x}^{t+1},\cdot)}(\bm{\mu})_{j}\approx{\operatorname*{arg\,min}_{{\bf
c}_{j}\in\mathbb{R}^{m}}}\left\\{\frac{1}{2\eta_{2}}(c_{j}-\mu_{j})^{2}+\frac{\lambda}{2}\sum_{i=1}^{d}\mathbbm{1}(Q_{{\bf
c}^{t}}({\bf x}^{t+1})_{i}=c^{t}_{j})|c^{t}_{j}-x^{t+1}_{i}|\right.$
$\displaystyle\left.+(c_{j}-c^{t}_{j})\frac{\lambda}{2}\sum_{i=1}^{d}\mathbbm{1}(Q_{{\bf
c}^{t}}({\bf
x}^{t+1})_{i}=c^{t}_{j})\frac{\partial|c^{t}_{j}-x^{t+1}_{i}|}{\partial
c^{t}_{j}}\right\\}$

In our implementation, we take
$\frac{\partial|c^{t}_{j}-x^{t+1}_{i}|}{\partial c^{t}_{j}}$ as $1$ if
$c^{t}_{j}>x^{t+1}_{i}$, $-1$ if $c^{t}_{j}<x^{t+1}_{i}$ and $0$ otherwise.
Now taking the derivative with respect to $c_{j}$ and setting it to 0 gives
us:

$\displaystyle\text{prox}_{\eta_{2}\lambda R({\bf
x}^{t+1},\cdot)}(\bm{\mu})_{j}$
$\displaystyle\approx\mu_{j}-\frac{\lambda\eta_{2}}{2}(\sum_{i=1}^{d}\mathbbm{1}(Q_{{\bf
c}^{t}}({\bf x}^{t+1})_{i}=c^{t}_{j})\mathbbm{1}(x^{t+1}_{i}>c^{t}_{j})$
$\displaystyle\hskip 56.9055pt-\sum_{i=1}^{d}\mathbbm{1}(Q_{{\bf c}^{t}}({\bf
x}^{t+1})_{i}=c^{t}_{j})\mathbbm{1}(x^{t+1}_{i}<c^{t}_{j}))$

Proximal map pulls the updated centers toward the median of the weights that
are assigned to them.

Using $P\rightarrow\infty$. In the experiments we observed that using
$P\rightarrow\infty$, i.e. using hard quantization function produces good
results and also simplifies the implementation. The implications of
$P\rightarrow\infty$ are as follows:

  * •

We take $\nabla_{\bf x}f(\widetilde{Q}_{\bf c}({\bf x}))=0$ and $\nabla_{\bf
x}f^{KD}(\widetilde{Q}_{\bf c}({\bf x}),{\bf w})=0$.

  * •

We take $\nabla_{\bf c}f(\widetilde{Q}_{\bf c}({\bf x}))=\nabla_{\bf
c}f(Q_{\bf c}({\bf x}))=\begin{bmatrix}\sum_{i=1}^{d}\frac{\partial f(Q_{\bf
c}({\bf x}))}{\partial Q_{\bf c}({\bf x})_{i}}\mathbbm{1}(Q_{\bf c}({\bf
x})_{i}=c_{1})\\\ \vdots\\\ \sum_{i=1}^{d}\frac{\partial f(Q_{\bf c}({\bf
x}))}{\partial Q_{\bf c}({\bf x})_{i}}\mathbbm{1}(Q_{\bf c}({\bf
x})_{i}=c_{m})\end{bmatrix}$ and $\nabla_{\bf c}f^{KD}(\widetilde{Q}_{\bf
c}({\bf x}),{\bf w})=\nabla_{\bf c}f^{KD}(Q_{\bf c}({\bf x}),{\bf
w})=\begin{bmatrix}\sum_{i=1}^{d}\frac{\partial f^{KD}(Q_{\bf c}({\bf x}),{\bf
w})}{\partial Q_{\bf c}({\bf x})_{i}}\mathbbm{1}(Q_{\bf c}({\bf
x})_{i}=c_{1})\\\ \vdots\\\ \sum_{i=1}^{d}\frac{\partial f^{KD}(Q_{\bf c}({\bf
x}),{\bf w})}{\partial Q_{\bf c}({\bf x})_{i}}\mathbbm{1}(Q_{\bf c}({\bf
x})_{i}=c_{m})\end{bmatrix}$.

###  D.2 Implementation Details and Hyperparameters

In this section we discuss the implementation details and hyperparameters used
for the algorithms considered in Section 5 of our main paper.

Fine tuning. In both centralized and federated settings we employ a fine
tuning procedure similar to [1]. At the end of the regular training procedure,
model weights are hard-quantized. After the hard-quantization, during the fine
tuning epochs we let the unquantized parts of the network to continue training
(e.g. batch normalization layers) and different from [1] we also continue to
train quantization levels.

####  D.2.1 Centralized Setting

For centralized training, we use CIFAR-10 dataset and train a ResNet [13]
model following [1] and [29]. We employ ADAM with learning rate $0.01$ and no
weight decay. We choose $\lambda(t)=10^{-4}t$. For the implementation of
ResNet models we used a
toolbox888https://github.com/akamaster/pytorch˙resnet˙cifar10. In Table 1 we
reported the results from [29] directly and implemented ProxQuant using their
published code999https://github.com/allenbai01/ProxQuant. We use a learning
schedule for $\eta_{2}$, particularly, we start with $\eta_{2}=10^{-4}$ and
multiply it with 0.1 at epochs 80 and 140.

####  D.2.2 Federated Setting

  * •

QuPeD101010For federated experiments we have used Pytorch’s Distributed
package.: For CNN1 we choose $\lambda_{p}=0.25$ on CIFAR-10. On FEMNIST
111111We use https://github.com/tao-shen/FEMNIST˙pytorch to import FEMNIST
dataset. and MNIST we choose $\lambda(t)=5\times 10^{-6}t$ for 2Bits and
$\lambda=10^{-6}t\frac{1}{0.99^{t}}$ for 1Bit training. For CNN2 we use
$\lambda_{p}=0.15$. Global model has the same learning schedule as the
personalized models. Furthermore, we use $\eta_{2}=10^{-4}$.

QuPeL: We used $\lambda_{p}=0.2$, $\eta_{3}=0.5$ (same as pFedMe [6]) and took
$\lambda$ values from QuPeD.

  * •

Per-FedAvg [7] and pFedMe [6]:To implement Per-FedAvg, we used the same
learning rate as mentioned in Section 5 schedule for main learning rate and
$\alpha=0.001$ for CNN1 and $\alpha=2.5\times 10^{-3}$ for CNN2 (we tuned in
the interval $[8\times 10^{-4},5\times 10^{-3}]$), for the auxiliary learning
rate. For pFedMe we used the same learning rate schedule for main learning
rate, $K=5$ for the number of local iterations; and we used $\lambda=0.5$,
$\eta=0.2$ for CNN1 and $\lambda=0.2$, $\eta=0.15$ for CNN2 (we tuned in the
interval $[0.1,1]$ for both parameters).

  * •

Federated Mutual Learning [26]: Since authors do not discuss the
hyperparameters in the paper, we used $\alpha=\beta=0.25$ for CNN1 and
$\alpha=\beta=0.15$ for CNN2, similar to our use of $\lambda_{p}$ in QuPeD.
Global model has the same learning schedule as the personalized models.

For QuPeD and Federated ML we used CNN1 as the global model in all settings.
For the other methods where global and personalized models cannot be different
we used the same structure as personalized models.