$K_{1}=K_{2}=n$ (full batch).
Privacy: First, by independence of the Gaussian noise across silos, it is
enough show that transcript of silo $i$’s interactions with the server is DP
for all $i\in[N]$ (conditional on the transcripts of all other silos). Since
$\epsilon\leq 2\ln(1/\delta)$, it suffices (by Proposition D.1) to show that
silo $i$’s transcript is $\frac{\epsilon^{2}}{8\ln(1/\delta)}$-zCDP. Then by
Proposition D.2 and Lemma D.1, it suffices to bound the sensitivity of the
update in line 7 of Algorithm 3 by $2L/n$ and the update in line 11 by
$\frac{1}{n}\min\\{2\beta\|w_{r}-w_{r-1}\|,4L\\}$.The line 7 sensitivity bound
holds because $\sup_{X_{i}\sim
X^{\prime}_{i}}\|\frac{1}{n}\sum_{j=1}^{n}\nabla f^{0}(w,x_{i,j})-\nabla
f^{0}(w,x^{\prime}_{i,j})\|=\sup_{x,x^{\prime}}\|\nabla f^{0}(w,x)-\nabla
f^{0}(w,x^{\prime})\|\leq 2L/n$ for any $w$ since $f^{0}$ is $L$-Lipschitz.
The line 11 sensitivity bound holds because $\sup_{X_{i}\sim
X^{\prime}_{i}}\|\frac{1}{n}\sum_{j=1}^{n}\nabla f^{0}(w_{r},x_{i,j}-\nabla
f^{0}(w_{r-1},x_{i,j})-(f^{0}(w_{r},x^{\prime}_{i,j})-\nabla
f^{0}(w_{r-1},x^{\prime}_{i,j}))\|=\frac{1}{n}\sup_{x,x^{\prime}}\|\nabla
f^{0}(w_{r},x-\nabla f^{0}(w_{r-1},x)-(f^{0}(w_{r},x^{\prime})-\nabla
f^{0}(w_{r-1},x^{\prime}))\|\leq\frac{1}{n}\min\\{2\beta\|w_{r}-w_{r-1}\|,4L\\}$
since $f^{0}$ is $L$-Lipschitz and $\beta$-smooth. Note that if $R<q$, then
only one update in line 7 is made, and the privacy of this update follows
simply from the guarantee of the Gaussian mechanism and the sensitivity bound,
without needing to appeal to the composition theorem.
Utility: Fix any $\mathbf{X}\in\mathbb{X}$ and denote
$\widehat{\mathcal{G}}_{\eta}(w)=\widehat{\mathcal{G}}_{\eta}(w,\mathbf{X})$
for brevity of notation. Recall the notation of Algorithm 3. Note that Lemma
F.1 holds with

$\displaystyle\tau_{1}^{2}$ $\displaystyle=\sup_{r\equiv
0~{}(\text{mod}~{}q)}\mathbb{E}\left\|h_{r}-\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})\right\|^{2}$
$\displaystyle=\sup_{r\equiv
0~{}(\text{mod}~{}q)}\mathbb{E}\left\|\frac{1}{M_{r}n}\sum_{i\in
S_{r}}\sum_{j=1}^{n}\left[\nabla
f^{0}(w_{r},x_{i,j})-\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})\right]\right\|^{2}+\frac{d\sigma_{1}^{2}}{M}$
$\displaystyle\leq\frac{2L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{d\sigma_{1}^{2}}{M},$

using independence of the noises across silos and Lemma F.2. Further, for any
$r$, we have (conditional on $w_{r},w_{r-1}$)

$\displaystyle\mathbb{E}\left\|H_{r}-\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})\right\|^{2}$
$\displaystyle\leq
2\left[\frac{d\sigma_{2}^{2}}{M}\|w_{r}-w_{r-1}\|^{2}+\mathbb{E}\left\|\frac{1}{M_{r}n}\sum_{i\in
S_{r}}\sum_{j=1}^{n}\left[\nabla f^{0}(w_{r},x_{i,j})-\nabla
f^{0}(w_{r-1},x_{i,j})-\left(\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-\widehat{F}_{\mathbf{X}}^{0}(w_{r-1})\right)\right]\right\|^{2}\right]$
$\displaystyle\leq\frac{2d\sigma_{2}^{2}}{M}\|w_{r}-w_{r-1}\|^{2}+\frac{8\beta^{2}}{Mn}\|w_{r}-w_{r-1}\|^{2}\mathds{1}_{\\{M<N\\}},$

using Young’s inequality, independence of the noises across silos, and Lemma
F.2. Therefore, Lemma F.1 holds with
$\tau_{2}^{2}=8\left(\frac{\beta^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{d\sigma_{2}^{2}}{M}\right)$.
Next, we claim that if $\eta=1/2\beta$ and
$q\leq\frac{1}{\eta^{2}\tau_{2}^{2}}$, then

$\mathbb{E}\|\mathcal{G}_{\eta}(w_{\text{priv}})\|^{2}\leq
16\left(\frac{\hat{\Delta}_{\mathbf{X}}}{\eta R}+\tau_{1}^{2}\right).$ (45)

We prove 45 as follows. Let $g(w_{r}):=-\frac{1}{\eta}(w_{r+1}-w_{r})$. By
Lemma E.2 (with $y=w_{r+1},~{}z=w=w_{r},~{}d^{\prime}=h_{r}$), we have

$\displaystyle\mathbb{E}\widehat{F}_{\mathbf{X}}(w_{r+1})$
$\displaystyle\leq\mathbb{E}\widehat{F}_{\mathbf{X}}(w_{r})+\mathbb{E}\left\langle
w_{r+1}-w_{r},\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-h_{r}\right\rangle+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\mathbb{E}\|w_{r+1}-w_{r}\|^{2}-\frac{1}{2\eta}\mathbb{E}\|w_{r+1}-w_{r}\|^{2}$
$\displaystyle\leq\mathbb{E}\widehat{F}_{\mathbf{X}}(w_{r})+\frac{\eta}{2}\mathbb{E}\left\|\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-h_{r}\right\|^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\mathbb{E}\|w_{r+1}-w_{r}\|^{2}$
$\displaystyle=\mathbb{E}\widehat{F}_{\mathbf{X}}(w_{r})+\frac{\eta}{2}\mathbb{E}\left\|\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-h_{r}\right\|^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{r})\|^{2}.$

Thus, by Lemma F.1, we have

$\displaystyle\mathbb{E}[\widehat{F}_{\mathbf{X}}(w_{r+1})-\widehat{F}_{\mathbf{X}}(w_{r})]$
$\displaystyle\leq\frac{\eta}{2}\mathbb{E}\left\|\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-h_{r}\right\|^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{r})\|^{2}$
$\displaystyle\leq\frac{\eta}{2}\tau_{2}^{2}\sum_{t=s_{r}+1}^{r}\mathbb{E}[\|w_{t}-w_{t-1}\|^{2}]+\frac{\eta}{2}\tau_{1}^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{r})\|^{2}$
$\displaystyle=\frac{\eta^{3}}{2}\tau_{2}^{2}\sum_{t=s_{r}+1}^{r}\mathbb{E}[\|g(w_{t})\|^{2}]+\frac{\eta}{2}\tau_{1}^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{r})\|^{2},$

where $s_{r}=\lfloor\frac{r}{q}\rfloor q$. Now we sum over a given phase (from
$s_{r}$ to $r$), noting that $r-q\leq s_{r}\leq r$:

$\displaystyle\mathbb{E}[\widehat{F}_{\mathbf{X}}(w_{r+1})-\widehat{F}_{\mathbf{X}}(w_{s_{r}})]$
$\displaystyle\leq\frac{\eta^{3}\tau_{2}^{2}}{2}\sum_{k=s_{r}}^{r}\sum_{j=s_{r}+1}^{k}\mathbb{E}[\|g(w_{j})\|^{2}]+\sum_{k=s_{r}}^{r}\left[\frac{\eta}{2}\tau_{1}^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{k})\|^{2}\right]$
$\displaystyle\leq\frac{q\eta^{3}\tau_{2}^{2}}{2}\sum_{k=s_{r}}^{r}\mathbb{E}[\|g(w_{k})\|^{2}]+\sum_{k=s_{r}}^{r}\left[\frac{\eta}{2}\tau_{1}^{2}+\left(\frac{\beta}{2}-\frac{1}{2\eta}\right)\eta^{2}\mathbb{E}\|g(w_{k})\|^{2}\right]$
$\displaystyle=-\sum_{k=s_{r}}^{r}\left\\{\mathbb{E}[\|g(w_{k})\|^{2}]\left(\frac{\eta}{2}-\frac{\beta\eta^{2}}{2}-\frac{\eta^{3}\tau_{2}^{2}q}{2}\right)-\frac{\eta\tau_{1}^{2}}{2}\right\\}$

Denoting
$A=\frac{\eta}{2}-\frac{\beta\eta^{2}}{2}-\frac{\eta^{3}\tau_{2}^{2}q}{2}$ and
summing over all phases
$P=\\{p_{0},p_{1},\ldots\\}=\left\\{0,q,\ldots,\lfloor\frac{R-1}{q}\rfloor
q,R\right\\}$, we get

$\displaystyle\mathbb{E}[\widehat{F}_{\mathbf{X}}(w_{R})-\widehat{F}_{\mathbf{X}}(w_{0})]$
$\displaystyle\leq\sum_{j=1}^{|P|}\mathbb{E}[\widehat{F}_{\mathbf{X}}(w_{p_{j}})-\widehat{F}_{\mathbf{X}}(w_{p_{j-1}})]$
$\displaystyle\leq\frac{\eta
R\tau_{1}^{2}}{2}-A\sum_{r=0}^{R}\mathbb{E}[\|g(w_{r})\|^{2}],$

which implies

$\frac{1}{R}\sum_{r=0}^{R}\mathbb{E}[\|g(w_{r})\|^{2}]\leq\frac{\hat{\Delta}_{\mathbf{X}}}{RA}+\frac{\eta\tau_{1}^{2}}{2A}.$
(46)

Now, for any $r\geq 0$,

$\displaystyle\left\|\widehat{\mathcal{G}}_{\eta}(w_{r})-g(w_{r})\right\|^{2}$
$\displaystyle=\frac{1}{\eta^{2}}\left\|w_{r+1}-\texttt{{prox}}_{\eta
f^{1}}(w_{r}-\eta\widehat{F}_{\mathbf{X}}^{0}(w_{r}))\right\|^{2}$
$\displaystyle=\frac{1}{\eta^{2}}\left\|\texttt{{prox}}_{\eta
f^{1}}(w_{r}-\eta h_{r})-\texttt{{prox}}_{\eta
f^{1}}(w_{r}-\eta\widehat{F}_{\mathbf{X}}^{0}(w_{r}))\right\|^{2}$
$\displaystyle\leq\frac{1}{\eta^{2}}\left\|-\eta
h_{r}+\eta\widehat{F}_{\mathbf{X}}^{0}(w_{r})\right\|^{2}$
$\displaystyle=\left\|h_{r}-\widehat{F}_{\mathbf{X}}^{0}(w_{r})\right\|^{2},$

by non-expansiveness of the proximal operator. Furthermore, conditional on the
uniformly drawn $r=r^{*}\in\\{0,1,\ldots,R\\}$, we have

$\displaystyle\mathbb{E}\left\|\widehat{\mathcal{G}}_{\eta}(w_{r^{*}})-g(w_{r^{*}})\right\|^{2}$
$\displaystyle\leq\mathbb{E}\left\|h_{r^{*}}-\widehat{F}_{\mathbf{X}}^{0}(w_{r^{*}})\right\|^{2}$
$\displaystyle\leq\tau_{2}^{2}\sum_{k=s_{r^{*}}+1}^{r^{*}}\mathbb{E}\|w_{k}-w_{k-1}\|^{2}+\tau_{1}^{2}$
$\displaystyle=\eta^{2}\tau_{2}^{2}\sum_{k=s_{r^{*}}+1}^{r^{*}}\mathbb{E}\|g(w_{k-1})\|^{2}+\tau_{1}^{2},$

by Lemma F.1, and taking total expectation yields

$\displaystyle\mathbb{E}\left\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})-g(w_{\text{priv}})\right\|^{2}$
$\displaystyle\leq\frac{\eta^{2}\tau_{2}^{2}}{R}\sum_{r=1}^{R}\sum_{k=s_{r}+1}^{r}\mathbb{E}\|g(w_{r-1})\|^{2}+\tau_{1}^{2}$
$\displaystyle\leq\frac{q\eta^{2}\tau_{2}^{2}}{R}\sum_{r=1}^{R}\mathbb{E}\|g(w_{r-1})\|^{2}+\tau_{1}^{2}$
$\displaystyle\leq
q\eta^{2}\tau_{2}^{2}\left[\frac{\hat{\Delta}_{\mathbf{X}}}{RA}+\frac{\eta\tau_{1}^{2}}{2A}\right]+\tau_{1}^{2},$

where the last inequality follows from 46. Hence

$\displaystyle\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})\|^{2}$
$\displaystyle\leq
2\left[q\eta^{2}\tau_{2}^{2}\left[\frac{\hat{\Delta}_{\mathbf{X}}}{RA}+\frac{\eta\tau_{1}^{2}}{2A}\right]+\tau_{1}^{2}\right]+2\mathbb{E}\|g(w_{\text{priv}})\|^{2}$
$\displaystyle\leq
2\left[q\eta^{2}\tau_{2}^{2}\left[\frac{\hat{\Delta}_{\mathbf{X}}}{RA}+\frac{\eta\tau_{1}^{2}}{2A}\right]+\tau_{1}^{2}\right]+\frac{2\hat{\Delta}_{\mathbf{X}}}{RA}+\frac{\eta\tau_{1}^{2}}{A},$

by Young’s inequality and 46. Now, our choices of $\eta=1/2\beta$ and
$q\leq\frac{1}{\tau_{2}^{2}\eta^{2}}$ imply
$A=\frac{\eta}{2}-\frac{\beta\eta^{2}}{2}-\frac{\eta^{3}\tau_{2}^{2}q}{2}\geq\frac{\eta}{4}$
and

$\displaystyle\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})\|^{2}$
$\displaystyle\leq
8\left[\left(\frac{\hat{\Delta}_{\mathbf{X}}}{R\eta}+\frac{\tau_{1}^{2}}{2}\right)+\tau_{1}^{2}\right]+\frac{8\hat{\Delta}_{\mathbf{X}}}{R\eta}+4\tau_{1}^{2}$
$\displaystyle=\frac{16\hat{\Delta}_{\mathbf{X}}}{R\eta}+16\tau_{1}^{2},$

proving 45. The rest of the proof follows from plugging in $\tau_{1}^{2}$ and
setting algorithmic parameters. Plugging
$\tau_{1}^{2}=\frac{2L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{d\sigma_{1}^{2}}{M}\leq\frac{2L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{16dL^{2}R\ln(1/\delta)}{q\epsilon^{2}n^{2}M}+\frac{16dL^{2}\ln(1/\delta)}{\epsilon^{2}n^{2}M}$
into 45 yields

$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})\|^{2}\leq
16\left(\frac{\hat{\Delta}_{\mathbf{X}}}{\eta
R}+\frac{2L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{16dL^{2}R\ln(1/\delta)}{q\epsilon^{2}n^{2}M}+\frac{16dL^{2}\ln(1/\delta)}{\epsilon^{2}n^{2}M}\right).$

Choosing $R=\frac{\epsilon
n\sqrt{Mq}\sqrt{\hat{\Delta}_{\mathbf{X}}\beta}}{L\sqrt{d\ln(1/\delta)}}$
equalizes the two terms in the above display involving $R$ (up to constants)
and we get

$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})\|^{2}\leq
C\left(\frac{L\sqrt{\hat{\Delta}_{\mathbf{X}}\beta}\sqrt{d\ln(1/\delta)}}{\epsilon
n\sqrt{Mq}}+\frac{dL^{2}\ln(1/\delta)}{\epsilon^{2}n^{2}M}+\frac{L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}\right)$
(47)

for some absolute constant $C>0$. Further, with this choice of $R$, it
suffices to choose

$q=\left\lfloor\min\left\\{\left(\frac{\epsilon
nL\sqrt{M}}{\sqrt{d\ln(1/\delta)\hat{\Delta}_{\mathbf{X}}\beta}}\right)^{2/3},\frac{nM}{\mathds{1}_{\\{M<N\\}}}\right\\}\right\rfloor$

to ensure that $q\leq\frac{1}{\tau_{2}^{2}\eta^{2}}$, so that 45 holds. Assume
$q\geq 1$. Then plugging this $q$ into 47 yields

$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}})\|^{2}\leq
C^{\prime}\left[\left(\frac{\sqrt{L\beta\hat{\Delta}_{\mathbf{X}}d\ln(1/\delta)}}{\epsilon
n\sqrt{M}}\right)^{4/3}+\frac{dL^{2}\ln(1/\delta)}{\epsilon^{2}n^{2}M}+\left(\frac{L\sqrt{\beta\hat{\Delta}_{\mathbf{X}}d\ln(1/\delta)}}{\epsilon
n^{3/2}M}+\frac{L^{2}}{Mn}\right)\mathds{1}_{\\{M<N\\}}\right]$

for some absolute constant $C^{\prime}>0$, as desired. In case $q<1$, then we
must have
$L<\frac{\sqrt{\beta\hat{\Delta}_{\mathbf{X}}d\ln(1/\delta)}}{\epsilon
n\sqrt{M}}$; hence, we can simply output $w_{0}$ (which is clearly ISRL-DP)
instead of running Algorithm 3 and get
$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}},\mathbf{X})\|^{2}\leq
L^{2}<\left(\frac{\sqrt{L\beta\hat{\Delta}_{\mathbf{X}}d\ln(1/\delta)}}{\epsilon
n\sqrt{M}}\right)^{4/3}$. ∎

The lemmas used in the above proof are stated below. The following lemma is an
immediate consequence of the martingale variance bound for SPIDER, given in
((Fang et al., 2018, Proposition 1)):

######  Lemma F.1 (((Fang et al., 2018))).

Let $r\in\\{0,1,\ldots,R\\}$ and $s_{r}=\lfloor\frac{r}{q}\rfloor q$. With the
notation of Algorithm 3, assume that
$\mathbb{E}|h_{s_{r}}-\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{s_{r}})\|^{2}\leq\tau_{1}^{2}$
and
$\mathbb{E}\left\|H_{r}-\left(\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r})-\nabla\widehat{F}_{\mathbf{X}}^{0}(w_{r-1})\right)\right\|^{2}\leq\tau_{2}^{2}\|w_{r}-w_{r-1}\|^{2}$.
Then for all $r\geq s_{r}+1$, the iterates of Algorithm 3 satisfy:

$\mathbb{E}\|h_{r}-\nabla\widehat{F}^{0}_{\mathbf{X}}(w_{r})\|^{2}\leq\tau_{2}^{2}\sum_{t=s_{r}+1}^{r}\mathbb{E}\|w_{t}-w_{t-1}\|^{2}+\tau_{1}^{2}.$

######  Lemma F.2 (((Lei et al., 2017))).

Let $\\{a_{l}\\}_{l\in[\widetilde{N}]}$ be an arbitrary collection of vectors
such that $\sum_{l=1}^{\widetilde{N}}a_{l}=0$. Further, let $\mathcal{S}$ be a
uniformly random subset of $[\widetilde{N}]$ of size $\widetilde{M}$. Then,

$\mathbb{E}\left\|\frac{1}{\widetilde{M}}\sum_{l\in\mathcal{S}}a_{l}\right\|^{2}=\frac{\widetilde{N}-\widetilde{M}}{(\widetilde{N}-1)\widetilde{M}}\frac{1}{\widetilde{N}}\sum_{l=1}^{\widetilde{N}}\|a_{l}\|^{2}\leq\frac{\mathds{1}_{\\{\widetilde{M}<~{}\widetilde{N}\\}}}{\widetilde{M}~{}\widetilde{N}}\sum_{l=1}^{\widetilde{N}}\|a_{l}\|^{2}.$

We present SDP FedProx-SPIDER in Algorithm 10.

Algorithm 10 SDP FedProx-SPIDER

1: Input:
$R\in\mathbb{N},K_{1},K_{2}\in[n],\mathbf{X}\in\mathbb{X},\eta>0,\epsilon>0,\delta\in(0,1/2),q\in\mathbb{N},w_{0}\in\mathcal{W}$.

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

3: for $i\in S_{r}$ in parallel do

4: Server sends global model $w_{r}$ to silo $i$.

5: if $r\equiv 0~{}(\text{mod}~{}q)$ then

6: silo $i$ draws $K_{1}$ samples $\\{x_{i,j}^{r}\\}_{j=1}^{K_{1}}$ u.a.r.
from $X_{i}$ (with replacement).

7: silo $i$ computes $\left\\{\nabla
f^{0}(w_{r},x_{i,j}^{r})\right\\}_{j=1}^{K_{1}}$.

8: Server updates
$h_{r}=\frac{1}{MK_{1}}\mathcal{P}_{\text{vec}}\left(\left\\{\nabla
f^{0}(w_{r},x_{i,j}^{r})\right\\}_{i\in S_{r},j\in[K_{1}]};\frac{\epsilon
nN}{4K_{1}M\sqrt{2\ln(1/\delta)}\max\left(1,\frac{\sqrt{q}}{\sqrt{R}}\right)},\frac{\delta
q}{2R};L\right).$

9: else

10: silo $i$ draws $K_{2}$ samples $\\{x_{i,j}^{r}\\}_{j=1}^{K_{1}}$ u.a.r.
from $X_{i}$ (with replacement).

11: silo $i$ computes $J_{i}=\\{\nabla f^{0}(w_{r},x_{i,j}^{r})-\nabla
f^{0}(w_{r-1},x_{i,j}^{r})\\}_{j=1}^{K_{2}}$.

12: Server receives
$H_{r}=\frac{1}{MK_{2}}\mathcal{P}_{\text{vec}}\Big{(}\\{J_{i}\\}_{i\in
S_{r}};\frac{\epsilon
Nn}{4MK_{2}\sqrt{2R\ln(1/\delta)}};\frac{\delta}{2R};\min\\{2L,\beta\|w_{r}-w_{r-1}\|\\}\Big{)}$,
and updates $h_{r}=h_{r-1}+H_{r}$.

13: end if

14: end for

15: Server updates $w_{r+1}=\texttt{{prox}}_{\eta f^{1}}(w_{r}-\eta h_{r})$.

16: end for

17: Output: $w_{\text{priv}}\sim\text{Unif}(\\{w_{r}\\}_{r=1,\cdots,R})$.

######  Theorem F.2 (Complete Statement of Theorem 3.2).

Let $\epsilon\leq\ln(1/\delta),~{}\delta\in(0,\frac{1}{2})$, and

$M_{r}=M\geq\left(\frac{\epsilon
Nd^{2}}{n^{2}}\right)^{1/3}\left(\frac{L}{\sqrt{\beta\hat{\Delta}_{\mathbf{X}}}}\right)^{1/3}\left[1+\left(\frac{L}{\sqrt{\beta\hat{\Delta}_{\mathbf{X}}}}\right)^{1/3}\right].$

Then, there exist algorithmic parameters such that SDP FedProx-SPIDER is
$(\epsilon,\delta)$-SDP. Further,

$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}},\mathbf{X})\|^{2}\lesssim\left[\left(\frac{\sqrt{L\beta\hat{\Delta}_{\mathbf{X}}d\ln^{3}(dnN/\delta)}}{\epsilon
nN}\right)^{4/3}+\frac{dL^{2}\ln^{3}(Rd/q\delta)}{\epsilon^{2}n^{2}N^{2}}+\mathds{1}_{\\{M<N\\}}\left(\frac{L\sqrt{\beta\hat{\Delta}_{\mathbf{X}}d\ln^{3}(dnN/\delta)}}{\epsilon
n^{3/2}N\sqrt{M}}+\frac{L^{2}}{Mn}\right)\right].$

###### Proof.

We will choose

$R=\left\lceil\frac{\epsilon
nN}{L}\sqrt{\frac{\hat{\Delta}_{\mathbf{X}}\beta}{d\ln^{3}(dnN/\delta)}}\min\left\\{\frac{\sqrt{Mn}}{\mathds{1}_{\\{M<N\\}}},\left(\frac{\epsilon
nNL}{\sqrt{\hat{\Delta}_{\mathbf{X}}\beta
d\ln^{3}(dnN/\delta)}}\right)\right\\}\right\rceil,$

$\eta=1/2\beta$, and $K_{1}=K_{2}=n$.
Privacy: By Theorem D.1, it suffices to show that the message received by the
server in each update in line 12 of Algorithm 10 (in isolation) is
$\left(\frac{\epsilon}{2\sqrt{2R\ln(1/\delta)}},\frac{\delta}{2R}\right)$-DP,
and that each update in line 8 is
$\left(\frac{\epsilon\sqrt{q}}{2\sqrt{2R\ln(1/\delta)}},\frac{\delta
q}{2R}\right)$-DP. Conditional on the random subsampling of silos, Theorem D.2
(together with the sensitivity estimates established in the proof of Theorem
3.1) implies that each update in line 12 is
$(\epsilon^{\prime},\delta^{\prime})$-SDP, where
$\epsilon^{\prime}\leq\frac{\epsilon N}{4M\sqrt{2R\ln(1/\delta)}}$ and
$\delta^{\prime}=\frac{\delta}{2R}$; each update in line 8 is
$(\epsilon^{\prime\prime},\delta^{\prime\prime})$-SDP, where
$\epsilon^{\prime\prime}=\epsilon^{\prime}\sqrt{q}$ and
$\delta^{\prime\prime}=\delta^{\prime}\sqrt{q}$. By our choice of $R$ and our
assumption on $M$, we have $M\geq\frac{\epsilon N}{4\sqrt{2R\ln(1/\delta)}}$
and hence $\epsilon^{\prime}\leq 1$. Thus, privacy amplification by
subsampling (silos only) (see e.g. ((Ullman, 2017, Problem 1))) implies that
the privacy loss of each round is bounded as desired, establishing that
Algorithm 10 is $(\epsilon,\delta)$-SDP, as long as $q\leq R$. If instead
$q>R$, then the update in line 8 is only executed once (at iteration $r=0$),
so our choice of $\sigma_{1}^{2}$ ensures SDP simply by Theorem D.2 and
privacy amplification by subsampling.

Utility: Denote the (normalized) privacy noises induced by
$\mathcal{P}_{\text{vec}}$ in lines 8 and 12 of the algorithm by $Z_{1}$ and
$Z_{2}$ respectively. By Theorem D.2, $Z_{i}$ is an unbiased estimator of its
respective mean and we have

$\mathbb{E}\|Z_{1}\|^{2}\lesssim\frac{dL^{2}\ln^{3}(Rd/q\delta)}{\epsilon^{2}n^{2}N^{2}}\max\left(\frac{R}{q},1\right),$

and

$\mathbb{E}\|Z_{2}\|^{2}\lesssim\frac{dR\ln^{3}(dR/\delta)}{\epsilon^{2}n^{2}N^{2}}\beta^{2}\|w_{r}-w_{r-1}\|^{2}$

for the $r$-th round. Also, note that Lemma F.1 is satisfied with

$\tau_{1}^{2}=\frac{2L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{dL^{2}\ln^{3}(Rd/q\delta)}{\epsilon^{2}n^{2}N^{2}}\max\left(\frac{R}{q},1\right),$

and

$\tau_{2}^{2}=8\beta^{2}\left(\frac{\mathds{1}_{\\{M<N\\}}}{Mn}+\frac{dR\ln^{3}(Rd/\delta)}{\epsilon^{2}n^{2}N^{2}}\right).$

Then by the proof of Theorem 3.1, we have

$\mathbb{E}\|\mathcal{G}_{\eta}(w_{\text{priv}})\|^{2}\leq
16\left(\frac{\hat{\Delta}_{\mathbf{X}}}{\eta R}+\tau_{1}^{2}\right).$ (48)

if $\eta=1/2\beta$ and $q\leq\frac{1}{\eta^{2}\tau_{2}^{2}}$. Thus,

$\mathbb{E}\|\widehat{\mathcal{G}}_{\eta}(w_{\text{priv}},\mathbf{X})\|^{2}\lesssim\frac{\hat{\Delta}_{\mathbf{X}}}{\eta
R}+\frac{L^{2}}{Mn}\mathds{1}_{\\{M<N\\}}+\frac{dL^{2}\ln^{3}(Rd/q\delta)}{\epsilon^{2}n^{2}N^{2}}\max\left(\frac{R}{q},1\right).$

Our choice of $R$ together with the choice of

$q=\left\lfloor\frac{1}{2}\min\left(\frac{Mn}{\mathds{1}_{\\{M<N\\}}},\left(\frac{\epsilon
nNL}{\sqrt{\hat{\Delta}_{\mathbf{X}}\beta
d\ln^{3}(Rd/\delta)}}\right)\right)\right\rfloor$

equalizes the two terms involving $R$ (up to constants), and we obtain the
desired ERM bound (upon noting that $q\leq 1/(\eta^{2}\tau_{2}^{2})$ is
satisfied). ∎

###  F.1 ISRL-DP Lower Bound

We first provide a couple of definitions. Our lower bound will hold for all
non-interactive and sequentially interactive ((Duchi et al., 2013; Joseph et
al., 2019)) algorithms, as well as a broad subclass of fully
interactive131313Full interactivity is the most permissive notion of
interactivity, allowing for algorithms to query silos multiple times,
adaptively, simultaneously, and in any sequence ((Joseph et al., 2019)).
Sequentially interactive algorithms can only query each silo once, adaptively
in sequence. Non-interactive algorithms query each silo once
independently/non-adaptively. ISRL-DP algorithms that are compositional
((Joseph et al., 2019; Lowy and Razaviyayn, 2021b)):

######  Definition 6 (Compositionality).

Let $\mathcal{A}$ be an $R$-round $(\epsilon_{0},\delta_{0})$-ISRL-DP FL
algorithm with data domain $\mathcal{X}$. Let
$\\{(\epsilon_{0}^{r},\delta_{0}^{r})\\}_{r=1}^{R}$ denote the minimal (non-
negative) parameters of the local randomizers $\mathcal{R}^{(i)}_{r}$ selected
at round $r$ such that $\mathcal{R}^{(i)}_{r}(\mathbf{Z}_{(1:r-1)},\cdot)$ is
$(\epsilon_{0}^{r},\delta_{0}^{r})$-DP for all $i\in[N]$ and all
$\mathbf{Z}_{(1:r-1)}.$ For $C>0$, we say that $\mathcal{A}$ is
$C$-compositional if $\sqrt{\sum_{r\in[R]}(\epsilon_{0}^{r})^{2}}\leq
C\epsilon_{0}.$ If such $C$ is an absolute constant, we simply say
$\mathcal{A}$ is compositional.

Any algorithm that uses the composition theorems of ((Dwork and Roth, 2014;
Kairouz et al., 2015)) for its privacy analysis is $1$-compositional; this
includes Algorithm 3 and most (but not all ((Lowy and Razaviyayn, 2021b)))
ISRL-DP algorithms in the literature. Define the $(\epsilon,\delta)$-ISRL-DP
algorithm class $\mathbb{A}_{(\epsilon,\delta),C}$ to contain all sequentially
interactive algorithms and all fully interactive, $C$-compositional
algorithms. If $\mathcal{A}$ is sequentially interactive or
$O\mathcal{O}(1)$-compositional, denote $\mathcal{A}\in\mathbb{A}$.

Next we re-state the precise form of our lower bound (using notation from
Appendix A) and then provide the proof.

######  Theorem F.3 (Precise Statement of Theorem 3.3).

Let $\epsilon\in(0,\sqrt{N}],2^{-\Omega(nN)}\leq\delta\leq
1/(nN)^{1+\Omega(1)}$. Suppose that in each round $r$, the local randomizers
are all $(\epsilon_{0}^{r},\delta_{0}^{r})$-DP, for
$\epsilon_{0}^{r}\lesssim\frac{1}{n},~{}\delta_{0}^{r}=o(1/nNR)$, $M=N\geq
16\ln(2/\delta_{0}^{r}n)$. Then, there exists an $L$-Lispchitz, $\beta$-smooth
smooth, convex loss $f:\mathbb{R}^{d}\times\mathcal{X}\to\mathbb{R}$ and a
database $\mathbf{X}\in\mathcal{X}^{n\times N}$ such that any compositional
and symmetric $(\epsilon_{0},\delta_{0})$-ISRL-DP algorithm $\mathcal{A}$ run
on $\mathbf{X}$ with output $w_{\text{priv}}$ satisfies

$\mathbb{E}\|\nabla\widehat{F}_{\mathbf{X}}(w_{\text{priv}})\|^{2}=\Omega\left(L^{2}\min\left\\{1,\frac{d\ln(1/\delta_{0})}{\epsilon_{0}^{2}n^{2}N}\right\\}\right).$

###### Proof.

The work of ((Lowy and Razaviyayn, 2021b)) showed that a compositional
$(\epsilon_{0},\delta_{0})$-ISRL-DP algorithm can become an
$\left(\mathcal{O}\left(\frac{\epsilon_{0}}{\sqrt{N}}\right),\delta\right)$-SDP
algorithm when a shuffler is introduced:

######  Theorem F.4 (((Lowy and Razaviyayn, 2021b))).

Let $\mathcal{A}\in\mathbb{A}_{(\epsilon_{0},\delta_{0}),C}$ such that
$\epsilon_{0}\in(0,\sqrt{N}]$ and $\delta_{0}\in(0,1).$ Assume that in each
round, the local randomizers
$\mathcal{R}^{(i)}_{r}(\mathbf{Z}_{(1:r-1)},\cdot):\mathcal{X}^{n}\to\mathcal{Z}$
are $(\epsilon_{0}^{r},\delta_{0}^{r})$-DP for all
$i\in[N],~{}r\in[R],~{}\mathbf{Z}_{(1:r-1)}\in\mathcal{Z}^{r-1\times N}$ with
$\epsilon_{0}^{r}\leq\frac{1}{n}$. Assume $N\geq 16\ln(2/\delta_{0}^{r}n)$. If
$\mathcal{A}$ is $C$-compositional, then assume
$\delta_{0}^{r}\leq\frac{1}{14nNR}$ and denote
$\delta:=14Nn\sum_{r=1}^{R}\delta_{0}^{r}$; if instead $\mathcal{A}$ is
sequentially interactive, then assume
$\delta_{0}=\delta_{0}^{r}\leq\frac{1}{7Nn}$ and denote
$\delta:=7Nn\delta_{0}.$ Let $\mathcal{A}_{s}:\mathbb{X}\to\mathcal{W}$ be the
same algorithm as $\mathcal{A}$ except that in each round $r$,
$\mathcal{A}_{s}$ draws a random permutation $\pi_{r}$ of $[N]$ and applies
$\mathcal{R}^{(i)}_{r}$ to $X_{\pi_{r}(i)}$ instead of $X_{i}$. Then,
$\mathcal{A}_{s}$ is $(\epsilon,\delta)$-CDP, where
$\epsilon=\mathcal{O}\left(\frac{\epsilon_{0}\ln\left(1/nN\delta_{0}^{\min}\right)C^{2}}{\sqrt{N}}\right),$
and $\delta_{0}^{\min}:=\min_{r\in[R]}\delta_{0}^{r}$. In particular, if
$\mathcal{A}\in\mathbb{A}$, then
$\epsilon=\mathcal{O}\left(\frac{\epsilon_{0}\ln\left(1/nN\delta_{0}^{\min}\right)}{\sqrt{N}}\right).$
Note that for sequentially interactive $\mathcal{A}$,
$\delta_{0}^{\min}=\delta_{0}.$

Next, we will observe that the expected (squared) gradient norm of the output
of $\mathcal{A}_{s}$ is the same as the expected (squared) gradient norm of
the output of $\mathcal{A}$ for symmetric FL algorithms. The precise
definition of a “symmetric” (fully interactive) ISRL-DP algorithm is that the
aggregation functions $g_{r}$ (used to aggregate silo updates/messages and
update the global model) are symmetric (i.e.
$g_{r}(Z_{1},\cdots,Z_{N})=g_{r}(Z_{\pi(1)},\cdots Z_{\pi(N)})$ for all
permutations $\pi$) and in each round $r$ the randomizers
$\mathcal{R}^{(i)}_{r}=\mathcal{R}_{r}$ are the same for all silos $i\in[N]$.
($\mathcal{R}^{(i)}_{r}$ can still change with $r$ though.) For example, all
of the algorithms presented in this paper (and essentially all algorithms that
we’ve come across in the literature, for that matter) are symmetric. This is
because the aggregation functions used in each round are simple averages of
the $M_{r}$ noisy gradients received from all silos and the randomizers used
by every silo in round $r$ are identical: each adds the same Gaussian noise to
the stochastic gradients. Note that for any symmetric algorithm, the
distributions of the updates of $\mathcal{A}$ and $\mathcal{A}_{s}$ are both
averages over all permutations of $[N]$ of the conditional (on $\pi$)
distributions of the randomizers applied to the $\pi$-permuted database.

Now, for a given $(\epsilon_{0},\delta_{0})$-ISRL-DP algorithm $\mathcal{A}$,
denote the shuffled algorithm derived from $\mathcal{A}$ by $\mathcal{A}_{s}$.
Then apply Theorem F.5 to $\mathcal{A}_{s}$ to obtain lower bounds on its
expected squared gradient norm:

######  Theorem F.5 (((Arora et al., 2022))).

Let $\epsilon\in(0,\sqrt{N}],2^{-\Omega(nN)}\leq\delta\leq
1/(nN)^{1+\Omega(1)}$. Then, there exists an $L$-Lispchitz, $\beta$-smooth
smooth, convex loss $f:\mathbb{R}^{d}\times\mathcal{X}\to\mathbb{R}$ and a
database $\mathbf{X}\in\mathcal{X}^{n\times N}$ such that any
$(\epsilon,\delta)$-CDP algorithm $\mathcal{A}$ run on $\mathbf{X}$ with
output $w_{\text{priv}}$ satisfies

$\mathbb{E}\|\nabla\widehat{F}_{\mathbf{X}}(w_{\text{priv}})\|^{2}=\Omega\left(L^{2}\min\left\\{1,\frac{d\ln(1/\delta)}{\epsilon^{2}n^{2}N^{2}}\right\\}\right).$

Applying Theorem F.5 with $\epsilon=\epsilon_{0}/\sqrt{N}$ yields the desired
lower bound for $\mathcal{A}_{s}$. Further, by the observations above about
symmetric algorithms, this lower bound also apply to $\mathcal{A}$. ∎

##  Appendix G Upper and Lower Bounds for Cross-Device FL Without a Trusted
Server

In this section, we use our results to derive upper and lower bounds for FL
algorithms that satisfy both ISRL-DP and user-level DP. Algorithms that
satisfy both both ISRL-DP and user-level DP provide privacy for the full data
of each individual silo/user, even in the presence of an adversary that has
access to the server, other silos/users, or silo/user communications. Such a
guarantee would be desirable in practical cross-device FL settings in which
silos/users (e.g cell phone users) do not trust the server or other users with
their sensitive data (e.g. text messages).

Assume $M=N$ for simplicity.141414The extension to $M<N$ will be clear. Given
ISRL-DP parameters $(\epsilon,\delta)$ with $\epsilon\leq 1$, let
$\epsilon_{0}=\epsilon/n$ and
$\delta_{0}=\delta/4n\leq\delta/(ne^{(n-1)\epsilon_{0}})=\delta/(ne^{(n-1)\epsilon/n})$.
Consider the Proximal PL case for now. Run Noisy
$(\epsilon_{0},\delta_{0})$-ISRL-DP Prox-SGD, which also satisfies
$(\epsilon,\delta)$-user level DP by Appendix B. Thus, Theorem 2.1 yields an
ISRL-DP/user-level DP excess risk upper bound for heterogeneous FL with
Proximal-PL losses:

$\displaystyle\mathbb{E}F(\widehat{w}_{R})-F(w^{*})$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{\kappa^{2}\sqrt{d\ln(1/\delta_{0})}}{\epsilon_{0}^{2}n^{2}\sqrt{N}}+\frac{\kappa}{\sqrt{Nn}}\right)\right)$
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{\kappa^{2}\sqrt{d\ln(1/\delta_{0})}}{\epsilon^{2}\sqrt{N}}+\frac{\kappa}{\sqrt{Nn}}\right)\right)$
(49)
$\displaystyle=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{\kappa^{2}\sqrt{d\ln(1/\delta_{0})}}{\epsilon^{2}\sqrt{N}}\right)\right).$

Regarding lower bounds: note that the semantics of the hybrid ISRL-DP/user-
level DP notion are essentially identical to local DP, except that individual
“records/items” are now thought of as datasets of size $n$. Thus, letting
$n=1$ in the strongly convex ISRL-DP lower bound of ((Lowy and Razaviyayn,
2021b)) (where we think of each silo as having just one “record” even though
that record is really a dataset) yields a lower bound that matches the upper
bound attained above up to a factor of $\widetilde{\mathcal{O}}(\kappa^{2})$.
Note that the minimax risk bounds for ISRL-DP/user-level DP hybrid algorithms
resemble the bounds for LDP algorithms ((Duchi et al., 2013)), scaling with
$N$, but not with $n$. A similar procedure can be used to derive upper and
lower bounds for Proximal PL ERM and non-convex/non-smooth ERM, using our
upper bounds in Theorems 2.2 and 3.1 and lower bound in Theorem 3.3.

##  Appendix H Experimental Details and Additional Results

###  H.1 ISRL-DP Fed-SPIDER: Alternate implementation of ISRL-DP FedProx-
SPIDER

We also evaluated an alternative implementation of ISRL-DP FedProx-SPIDER,
given in Algorithm 11. We found that this variation of ISRL-DP FedProx-SPIDER
sometimes performed better in practice. For each
$\epsilon\in\\{0.75,1,1.5,3,6,12,18\\}$, we chose the algorithm with smaller
training loss and reported the test error for the corresponding algorithm as
SPIDER in the plots.

Algorithm 11 ISRL-DP Fed-SPIDER: Alternate Implementation

1: Input: Number of silos $N\in\mathbb{N},$ dimension $d\in\mathbb{N}$ of
data, noise parameters $\sigma^{2}_{1}$ and $\sigma^{2}_{2}$, data sets
$X_{i}\in\mathcal{X}^{n_{i}}$ for $i\in[N]$, loss function $f(w,x),$ number of
rounds $E-1\in\mathbb{N}$, local batch size parameters $K_{1}$ and $K_{2}$,
step size $\eta$.

2: Server initializes $w_{0}^{2}:=0$ and broadcasts.

3: Silos sync $w_{0}^{i,2}:=w_{0}^{2}$ ($i\in[N]$).

4: Network determines random subset $S_{0}$ of $M_{0}\in[N]$ available silos.

5: for $i\in S_{0}$ in parallel do

6: Silo $i$ draws $K_{2}$ random samples $\\{x^{0,2}_{i,j}\\}_{j\in[K_{2}]}$
(with replacement) from $X_{i}$ and noise $u_{2}^{(i)}\sim
N(0,\sigma_{2}^{2}\mathbf{I}_{d}).$

7: Silo $i$ computes noisy stochastic gradient
$\widetilde{v}^{i,2}_{0}:=\frac{1}{K_{2}}\sum_{j=1}^{K_{2}}\nabla
f(w_{0}^{2},x_{i,j}^{0,2})+u_{2}^{(i)}$ and sends to server.

8: end for

9: Server aggregates $\widetilde{v}^{2}_{0}:=\frac{1}{M_{0}}\sum_{i\in
S_{0}}\widetilde{v}^{i,2}_{0}$ and broadcasts.

10: for $r\in\\{0,1,\cdots,E-2\\}$ do

11: Network determines random subset $S_{r+1}$ of $M_{r+1}\in[N]$ available
silos.

12: for $i\in S_{r+1}$ in parallel do

13: Server updates $w_{r+1}^{0}:=w_{r}^{2}$,
$w_{r+1}^{1}:=w_{r}^{2}-\eta\widetilde{v}_{r}^{2}$ and broadcasts to silos.

14: Silos sync $w^{i,0}_{r+1}:=w_{r+1}^{0}$,
$\widetilde{v}^{i,0}_{r+1}:=\widetilde{v}^{2}_{r}$, and
$w_{r+1}^{i,1}:=w_{r+1}^{1}$ ($i\in[N])$.

15: Silo $i$ draws $K_{1}$ random samples
$\\{x^{r+1,1}_{i,j}\\}_{j\in[K_{1}]}$ (with replacement) from $X_{i}$ and
noise $u_{1}^{(i)}\sim N(0,\sigma_{1}^{2}\mathbf{I}_{d}).$

16: Silo $i$ computes
$\widetilde{v}^{i,1}_{r+1}:=\frac{1}{K_{1}}\sum_{j=1}^{K_{1}}[\nabla
f(w_{r+1}^{1},x^{r+1,1}_{i,j})-\nabla
f(w_{r+1}^{0},x^{r+1,1}_{i,j})]+\widetilde{v}^{i,0}_{r+1}+u_{1}^{(i)}$ and
sends to server.

17: Server aggregates $\widetilde{v}_{r+1}^{1}:=\frac{1}{M_{r+1}}\sum_{i\in
S_{r+1}}\widetilde{v}_{r+1}^{i,1}$, updates
$w_{r+1}^{2}:=w_{r+1}^{1}-\eta\widetilde{v}_{r+1}^{1}$, and broadcasts.

18: Silos sync $w_{r+1}^{i,2}:=w_{r+1}^{2}$.

19: Silo $i$ draws $K_{2}$ random samples
$\\{x_{i,j}^{r+1,2}\\}_{j\in[K_{2}]}$ (with replacement) from $X_{i}$ and
noise $u_{2}^{(i)}\sim N(0,\sigma_{2}^{2}\mathbf{I}_{d}).$

20: Silo $i$ computes
$\widetilde{v}^{i,2}_{r+1}:=\frac{1}{K_{2}}\sum_{j=1}^{K_{2}}\nabla
f(w_{r+1}^{2},x_{i,j}^{r+1,2})+u_{2}^{(i)}$ and sends to server.

21: Server updates $\widetilde{v}_{r+1}^{2}:=\frac{1}{M_{r+1}}\sum_{i\in
S_{r+1}}\widetilde{v}^{i,2}_{r+1}$ and broadcasts.

22: end for

23: end for

24: Output:
$w_{\text{priv}}\sim\text{Unif}(\\{w_{r}^{t}\\}_{r=1,\cdots,E-1;t=1,2})$.

###  H.2 MNIST experiment

The MNIST data is available at http://yann.lecun.com/exdb/mnist/. In our
implementation, we use torchvision.datasets.MNIST to download the MNIST data.
All experiments are conducted on a device with 6-core Intel Core i7-8700.

Experimental setup: To divide the data into $N=25$ silos and pre-process it,
we rely on the code provided by ((Woodworth et al., 2020b)). The code is
shared under a Creative Commons Attribution-Share Alike 3.0 license. We fix
$\delta=1/n^{2}$ (where $n=$number of training samples per silo, is given in
“Preprocessing”) and test $\epsilon\in\\{0.75,1,1.5,3,6,12,18\\}$.

Preprocessing: First, we standardize the numerical data to have mean zero and
unit variance, and flatten them. Then, we utilize PCA to reduce the dimension
of flattened images from $d=784$ to $d=50$. To expedite training, we used 1/7
of the $5,421$ samples per digit, which is 774 samples per digit. As each silo
is assigned data of two digits, each silo has $n=1,543$ samples. We employ an
80/20 train/test split for data of each silo.

Gradient clipping:  Since the Lipschitz parameter of the loss is unknown for
this problem, we incorporated gradient clipping ((Abadi et al., 2016)) into
the algorithms. Noise was calibrated to the clip threshold $L$ to guarantee
ISRL-DP (see below for more details). We also allowed the non-private
algorithms to employ clipping if it was beneficial.

Hyperparameter tuning: For each algorithm, each
$\epsilon\in\\{0.75,1,1.5,3,6,12,18\\}$, and each
$(M,R)\in\\{(12,25),(12,50),$ $(25,25),(25,50)\\}$, we swept through a range
of constant stepsizes and clipping thresholds to find the (approximately)
optimal stepsize and clipping threshold for each algorithm and setting. The
stepsize grid consists of 5 evenly spaced points between $e^{-9}$ and 1. The
clipping threshold includes 5 values of 1, 5, 10, 100, 10000. For ISRL-DP
FedProx-SPIDER, we use $q\in\\{1,2,3,4\\}$ for $R=50$ and $q\in\\{1,2\\}$ for
$R=25$. Due to memory limitation, we did not check large $q$ values because it
results in large batch size based on $K$ in ISRL-DP FedProx-SPIDER (see below
for more details).

Choice of $\sigma^{2}$ and $K$: We used noise with smaller constants/log terms
(compared to the theoretical portion of the paper) to get better utility (at
the expense of needing larger $K$ to ensure privacy), by appealing to the
moments accountant ((Abadi et al., 2016, Theorem 1)) instead of the advanced
composition theorem ((Dwork and Roth, 2014, Theorem 3.20)).

For ISRL-DP FedProx-SPIDER, we used
$\sigma_{1}^{2}=\frac{16L^{2}\ln(1/\delta)}{\epsilon^{2}n^{2}}\max\left(\frac{R}{q},1\right)$,
$\sigma_{2}=\infty$, and
$\hat{\sigma}_{2}^{2}=\frac{64L^{2}R\ln(1/\delta)}{\epsilon^{2}n^{2}}$. We
chose $\sigma_{2}=\infty$ because we do not have an a priori bound on the
smoothness parameter $\beta$. Therefore, only the variance-reduction benefits
of SPIDER are illustrated in the experiments and not the smaller privacy
noise.

For ISRL-DP FedSPIDER: Alternate Implementation, we used
$\sigma_{1}^{2}=\frac{32L^{2}\ln(2/\delta)R}{n^{2}\epsilon^{2}}$ and
$\sigma_{2}^{2}=\frac{8L^{2}\ln(2/\delta)R}{n^{2}\epsilon^{2}}$ with
$K_{1}=K_{2}=\frac{n\sqrt{\epsilon}}{2\sqrt{R}}$ given above, which guarantees
ISRL-DP by ((Abadi et al., 2016, Theorem 1)). Note that the larger constant
$32$ is needed for ISRL-DP in $\sigma_{1}^{2}$ because the $\ell_{2}$
sensitivity of the updates in line 16 of Algorithm 3 is larger than simple SGD
updates (which are used in MB-SGD, Local SGD, and line 20 of Algorithm 3) by a
factor of $2$.

For ISRL-DP MB-SGD and ISRL-DP Local SGD, we use the same implementation as
((Lowy and Razaviyayn, 2021b)).

Generating Noise: Due to the low speed of NumPy package in generating
multivariate random normal vectors, we use an alternative approach to generate
noises. For ISRL-DP SPIDER and ISRL-DP MB-SGD algorithms, we generate the
noises on MATLAB and save them. Then, we load them into Python when we run the
algorithms. Since the number of required noise vectors for ISRL-DP Local SGD
is much larger ($K$ times larger) than two other ISRL-DP algorithms, saving
the noises beforehand requires a lot of memory. Hence, we generate the noises
of ISRL-DP Local SGD on Python by importing a MATLAB engine.

Plots and additional experimental results: See Figure 9 and Figure 10 for
results of the two remaining experiments: $(M=12,R=25)$ and $(M=25,R=50)$. The
results are qualitatively similar to those presented in the main body. In
particular, ISRL-DP SPIDER continues to outperform both ISRL-DP baselines in
most tested privacy levels. Also, ISRL-DP MB-SGD continues to show strong
performance in the high privacy regime ($\epsilon\leq 1.5$).

---
Figure 9: MNIST. $M=12,R=25$.
---
Figure 10: MNIST. $M=25,R=50$.

###  H.3 CIFAR10 experiment

We run an experiment on CIFAR10 data to further evaluate the performance of
ISRL-DP SPIDER in image classification. We partition the data set into 10
heterogeneous silos, each containing one class out of 10 classes of data. We
use a 5-layer CNN with two 5x5 convolutional layers (the first with 6
channels, the second with 16 channels, each followed by a ReLu activation and
a 2x2 max pooling) and three fully connected layers with 120, 84, 10 neurons
in each fully connected layer (the first and second fully connected layers
followed by a ReLu activation). For 7 privacy levels ranging from
$\epsilon=0.75$ to $\epsilon=18$, we compare ISRL-DP SPIDER against standard
FL baselines: MB-SGD, Local SGD (a.k.a. Federated Averaging) ((McMahan et al.,
2017)), ISRL-DP MB-SGD ((Lowy and Razaviyayn, 2021b)), and ISRL-DP Local SGD.
We fix $\delta=1/n^{2}$. As Figure 6 shows, ISRL-DP SPIDER outperforms both
ISRL-DP baselines for most tested privacy levels. The results are based on the
average error of 10 random assignment of train/test split of data for each
algorithm/epsilon pair. CIFAR10 data is available at
https://www.cs.toronto.edu/~kriz/cifar.html. In our implementation, we
directly download the data from torchvision.datasets.CIFAR10.

Experimental setup: To divide the CIFAR10 data into $N=10$ heterogeneous
silos, we use labels. That is, we assign one unique image class to each of 10
heterogeneous silos.

Preprocessing: We standardize the numerical data to have mean zero and unit
variance. We utilize a 80/20 train/test split for data of each client.

Gradient clipping:  Since the Lipschitz parameter of the loss is unknown for
this problem, we incorporated gradient clipping ((Abadi et al., 2016)) into
the algorithms. Noise was calibrated to the clip threshold $L$ to guarantee
ISRL-DP (see below for more details). We also allowed the non-private
algorithms to employ clipping if it was beneficial.

Hyperparameter tuning: It is similar to hyperparameter tuning of MNIST data.
However, we check $(M,R)=(10,50)$ and $(M,R)=(10,100)$ here. Also, the
stepsize grid of Local SGD consists of 20 evenly spaced points between
$e^{-5}$ and $e^{1}$ for local SGD. The stepsize grid of MB-SGD and SPIDER
with R=50 consists of 12 evenly spaced points between $e^{-5}$ and $e^{0}$ and
with R=100 consists of 8 evenly spaced points between $e^{-5}$ and $e^{1}$.
The clipping threshold of all algorithms includes 6 values of 0.001, 0.01,
0.1, 1, 5, 10. For ISRL-DP FedProx-SPIDER, we use $q\in\\{1,2,3,4\\}$ for
$R=50$ and $q\in\\{1,2,\dots,8\\}$ for $R=100$. Due to memory limitation, we
did not check large $q$ values because it results in large batch size based on
$K$ in ISRL-DP FedProx-SPIDER (see below for more details).

Choice of $\sigma^{2}$ and $K$: Same as in MNIST: see Section H.2.

###  H.4 Breast cancer experiment

We run an experiment on Wisconsin Breast Cancer (Diagnosis) data (WBCD) to
further evaluate the performance of ISRL-DP SPIDER in binary (malignant vs.
benign) classification. We partition the data set into 2 heterogeneous silos,
one containing malignant labels and the other benign labels. We use a 2-layer
perceptron with 5 neurons in the hidden layer. For 7 privacy levels ranging
from $\epsilon=0.75$ to $\epsilon=18$, we compare ISRL-DP SPIDER against
standard FL baselines: MB-SGD, Local SGD (a.k.a. Federated Averaging)
((McMahan et al., 2017)), ISRL-DP MB-SGD ((Lowy and Razaviyayn, 2021b)), and
ISRL-DP Local SGD. We fix $\delta=1/n^{2}$. As Figure 8 shows, ISRL-DP SPIDER
outperforms both ISRL-DP baselines for most tested privacy levels. The results
are based on the average error of 10 random assignment of train/test split of
data for each algorithm/epsilon pair. WBCD data is available at
https://archive.ics.uci.edu/ml/datasets and we directly download the data from
UCI repository website. The experiment is conducted on a device with 6-core
Intel Core i7-8700.

Experimental setup: To divide the WBCD data into $N=2$ silos, we use labels
(malignant vs. benign). We split the data into 2 parts, one only has malignant
labels and the other only has benign data. Then, we assign each part to a
client to have full heterogeneous silos. In all experiments, we fix
$\delta=1/n^{2}$ (where $n=$number of training samples per client, is given in
“Preprocessing”) and test $\epsilon\in\\{0.75,1,1.5,3,6,12,18\\}$.

Preprocessing: We standardize the numerical data to have mean zero and unit
variance. We utilize a 80/20 train/test split for data of each client.

Gradient clipping:  Since the Lipschitz parameter of the loss is unknown for
this problem, we incorporated gradient clipping ((Abadi et al., 2016)) into
the algorithms. Noise was calibrated to the clip threshold $L$ to guarantee
ISRL-DP (see below for more details). We also allowed the non-private
algorithms to employ clipping if it was beneficial.

Hyperparameter tuning: It is similar to hyperparameter tuning of MNIST data.
However, we check $(M,R)=(4,25)$ here. Also, the stepsize grid consists of 15
evenly spaced points between $e^{-9}$ and 1. The clipping threshold includes 4
values of 0.1, 1, 5, 10. For ISRL-DP FedProx-SPIDER, we use
$q\in\\{1,2,\dots,10\\}$. Due to memory limitation, we did not check large $q$
values because it results in large batch size based on $K$ in ISRL-DP FedProx-
SPIDER (see below for more details).

Choice of $\sigma^{2}$ and $K$: Same as in MNIST: see Section H.2.

Generating Noise: Due to the low speed of NumPy package in generating
multivariate random normal vectors, we use an alternative approach to generate
noises. For ISRL-DP SPIDER and ISRL-DP MB-SGD algorithms, we generate the
noises on MATLAB and use them in Python when we run the algorithms. Since the
number of required noise vectors for ISRL-DP Local SGD is much larger ($K$
times larger) than two other ISRL-DP algorithms, saving the noises beforehand
requires a lot of memory. Hence, we generate the noises of ISRL-DP Local SGD
on Python by importing a MATLAB engine.

##  Appendix I Limitations

A major focus of this work is on developing DP algorithms that can handle a
broader, more practical range of ML/optimization problems: e.g. non-
convex/non-smooth, Proximal-PL, heterogeneous silos. However, some assumptions
may still be strict for certain practical applications. In particular, the
requirement of an a priori bound on the Lipschitz parameter of the loss–which
the vast majority of works on DP ERM and SO also rely on–may be unrealistic in
cases where the underlying data distribution is unbounded and heavy-tailed.
Understanding what privacy and utility guarantees are possible without this
assumption is an interesting problem for future work.

Limitations of Experiments: Pre-processing and hyperparameter tuning were done
non-privately, since the focus of this work is on DP FL.151515See ((Abadi et
al., 2016; Liu and Talwar, 2019; Papernot and Steinke, 2021)) and the
references therein for discussion of DP PCA and DP hyperparameter tuning. This
means that the total privacy loss of the entire experimental process is higher
than the $\epsilon$ indicated, which only accounts for the privacy loss from
executing the FL algorithms with given (fixed) hyperparameters and (pre-
processed) data.

##  Appendix J Societal Impacts

We expect a net positive impact on society from our work, given that our
algorithms can prevent sensitive data leakage during FL. Nonetheless, like all
technologies, it carries potential for misuse and unintended outcomes. For
instance, companies may attempt to legitimize invasive data collection by
arguing that the user data will solely be utilized to train a differentially
private model to safeguard privacy. Furthermore, in some parameter ranges,
privacy comes at the expense of lower model accuracy, which could have adverse
effects in crucial applications such as medicine and environmental science.