$\widetilde{\epsilon}=\frac{\epsilon}{2\sqrt{2R\ln(2/\delta)}}$ (we used the
assumption $\epsilon\leq 2\ln(2/\delta)$ here) and
$\widetilde{\delta}=\frac{\delta}{2R}.$ First, condition on the randomness due
to local sampling of the local data point $x^{r}_{1,1}$ (line 4 of Algorithm
1). Now, the $L_{2}$ sensitivity of each local step of SGD is bounded by
$\Delta:=\sup_{|X_{1}\Delta X^{\prime}_{1}|\leq
2,w\in\mathcal{W}}\|\frac{1}{K}\sum_{j=1}^{K}\nabla f(w,x_{1,j})-\nabla
f(w,x^{\prime}_{1,j})\|\leq 2L/K,$ by $L$-Lipschitzness of $f.$ Thus, the
standard privacy guarantee of the Gaussian mechanism (see Theorem A.1 in
[DR14]) implies that (conditional on the randomness due to sampling) taking
$\sigma^{2}_{1}\geq\frac{8L^{2}\ln(1.25/\widetilde{\delta})}{\widetilde{\epsilon}^{2}K^{2}}$
suffices to ensure that round $r$ (in isolation) is
$(\widetilde{\epsilon},\widetilde{\delta})$-LDP. Now we invoke the randomness
due to sampling: [Ull17] implies that round $r$ (in isolation) is
$(\frac{2\widetilde{\epsilon}K}{n_{1}},\widetilde{\delta})$-LDP. The
assumption on $K_{i}$ ensures that
$\epsilon^{\prime}:=\frac{n_{1}}{2K}\frac{\epsilon}{2\sqrt{2R\ln(2/\delta})}\leq
1$, so that the privacy guarantees of the Gaussian mechanism and amplification
by subsampling stated above indeed hold. Therefore, with sampling, it suffices
to take
$\sigma^{2}_{1}\geq\frac{32L^{2}\ln(1.25/\widetilde{\delta})}{n_{1}^{2}\widetilde{\epsilon}^{2}}=\frac{256L^{2}R\ln(2.5R/\delta)\ln(2/\delta)}{n_{1}^{2}\epsilon^{2}}$
to ensure that round $r$ (in isolation) is
$(\widetilde{\epsilon},\widetilde{\delta})$-LDP for all $r$ and hence that the
full algorithm ($R$ rounds) is $(\epsilon,\delta)$-LDP.

Excess loss: First suppose $f$ is merely convex ($\mu=0$). By Lemma E.2, Lemma
E.1, and Lemma E.4 (and noting $\phi^{*}_{\max}\leq 4L^{2}$ and
$\upsilon_{*}^{2}=0$ since client data is i.i.d.), we have:

$\displaystyle\mathbb{E}F(\widehat{w}_{R})-F(w^{*})$
$\displaystyle\leq\alpha+\mathbb{E}\widehat{F}(\widehat{w}_{R})-\widehat{F}(w^{*})$
(23) $\displaystyle\leq\frac{2L^{2}R\eta}{n_{\min}M}+\frac{D^{2}}{\eta R}$
(24)
$\displaystyle+2\eta\left[\min\left\\{\frac{\Phi_{*}^{2}}{M^{\prime}K},\frac{(\phi^{*}_{\max})^{2}}{MK}\right\\}+\left(1-\frac{M-1}{N-1}\right)\frac{\upsilon_{*}^{2}}{M}+\frac{d}{2}\min\left\\{\frac{\Sigma^{2}}{M^{\prime}},\frac{\sigma^{2}_{\max}}{M}\right\\}\right]$
(25) $\displaystyle\leq\frac{2L^{2}R\eta}{n_{\min}M}+\frac{D^{2}}{\eta
R}+2\eta\left[4Rd\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\}+\frac{4L^{2}}{MK}\right]$
(26) $\displaystyle\leq\eta
L^{2}\left[R\left(\frac{2}{Mn_{\min}}+256d\min\left\\{\frac{\Xi}{M^{\prime}},\frac{\xi_{\max}}{M}\right\\}\right)+\frac{8}{MK}\right]+\frac{D^{2}}{\eta
R}$ (27)

for any $\eta\leq\frac{1}{4\beta}.$ Then one can verify that the prescribed
choice of $\eta$ and $R$ yields the desired bound.

Now suppose $f$ is $\mu$-strongly convex. The prescribed choice of $\eta$ and
$R$ imply that

$\mathbb{E}\widehat{F}(\widehat{w}_{R})-\widehat{F}(w^{*})=\widetilde{\mathcal{O}}\left(\frac{d}{\mu}\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\}\right)$

by Lemma E.4. Then the result follows from Lemma E.1 and Lemma E.2. ∎

###  E.4 Complete statement and proof of Theorem 2.2

Using the same notation as in the complete version of Theorem 2.1, we have:

Theorem 2.2 [Complete Version] Let
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ be $\mu$-strongly convex (with
$\mu=0$ for convex case) and $L$-Lipschitz, in $w$ for all $x\in\mathcal{X},$
where $\mathcal{W}$ is a closed convex set in $\mathbb{R}^{d}$ s.t. $\|w\|\leq
D$ for all $w\in\mathcal{W}.$ Let $\mathcal{D}$ be an arbitrary probability
distribution on $\mathcal{X}.$ For each client $i\in[N]$, draw a local i.i.d.
data set $X_{i}\sim\mathcal{D}^{n_{i}}.$ Denote
$\widetilde{M}:=\begin{cases}\sqrt{M^{\prime}}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\sqrt{M}&\mbox{otherwise}\end{cases}$ and
$\widetilde{\Psi}:=\begin{cases}\Psi&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\psi_{\max}&\mbox{otherwise}\end{cases}.$ Similarly, denote
$\widetilde{\Xi}:=\widetilde{\Psi}/L^{2}.$ Then, running Algorithm 1 on
$f_{\beta}(w,x):=\min_{v\in\mathcal{W}}\left(f(v,x)+\frac{\beta}{2}\|w-v\|^{2}\right)$
with $\beta$ as prescribed below and the same $\sigma_{i}^{2}$,
$\eta_{r}=\eta$ and $\\{\gamma_{r}\\}_{r=0}^{R-1}$ in Theorem 2.1[Complete
Version] results in the following upper bounds on the excess loss w.r.t. $f$ :
1\. (Convex) Setting
$\beta:=\frac{L\sqrt{\widetilde{M}}}{D}\min\left(\sqrt{n_{\min}},\frac{1}{\sqrt{d\widetilde{\Xi}}}\right)$
and
$R:=\left\lceil\widetilde{M}\min\left\\{n_{\min},\frac{1}{d\widetilde{\Xi}}\right\\}\right\rceil$
yields

$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})\leq
545\frac{LD}{\sqrt{\widetilde{M}}}\max\left\\{\frac{1}{\sqrt{n_{\min}}},\sqrt{d\widetilde{\Xi}}\right\\}.$

2\. (Strongly convex) Setting
$\beta:=\mu\widetilde{M}\min\left\\{n_{\min},\frac{1}{d\widetilde{\Xi}}\right\\}$
and
$R:=\left\lceil\max\left\\{8\widetilde{M}\min\left\\{n_{\min},\frac{1}{d\widetilde{\Xi}}\right\\}\ln\left(\frac{\beta
D^{2}\mu
M^{\prime}}{dL^{2}\widetilde{\Xi}}\right),\frac{1}{d\widetilde{\Xi}}\right\\}\right\rceil$
yields

$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{1}{Mn_{\min}}+d\min\left\\{\frac{\Xi}{M^{\prime}},\frac{\xi_{\max}}{M}\right\\}\right)\right).$

The proof follows from applying Theorem 2.1 to the $\beta$-smooth, Lipschitz,
convex loss $F_{\beta}$ to upper bound
$\mathbb{E}F_{\beta}(\widehat{w}_{R})-F^{*}_{\beta}$ and then relating this
quantity to $\mathbb{E}F(\widehat{w}_{R})-F(w^{*})$ by using:

######  Lemma E.10.

[Nes05] Let $f:\mathcal{W}\to\mathbb{R}^{d}$ be convex and $L$-Lipschitz and
let $\beta>0$. Then the $\beta$-Moreau envelope
$f_{\beta}(w):=\min_{v\in\mathcal{W}}\left(f(v)+\frac{\beta}{2}\|w-v\|^{2}\right)$
satisfies:
1\. $f_{\beta}$ is convex, $2L$-Lipschitz, and $\beta$-smooth.
2\. $\forall w$, $f_{\beta}(w)\leq f(w)\leq
f_{\beta}(w)+\frac{L^{2}}{2\beta}.$

###### Proof of Theorem 2.2.

We have
$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})\leq\mathbb{E}F_{\beta}(\widehat{w}_{R})-F^{*}_{\beta}+\frac{L^{2}}{2\beta},$
by part 2 of Lemma E.10. Then plugging in $\beta$ and combining part 1 of
Lemma E.10 with Theorem 2.1 completes the proof. ∎

###  E.5 Noisy Accelerated MB-SGD Algorithm and the statement and proof of
federated ERM upper bounds

####  E.5.1 Noisy Accelerated MB-SGD Algorithm and federated ERM upper bounds
for smooth losses

The Noisy Accelerated MB-SGD algorithm is formally described in Algorithm 2.
We first state the informal guarantee (assuming same parameters across
clients) of Algorithm 2 for smooth losses:

######  Theorem E.1.

[Informal] Denote
$\hat{\Phi}^{2}=\sup_{w\in\mathcal{W}}\frac{1}{nN}\sum_{i=1}^{N}\sum_{j=1}^{n}\|\nabla
f(w,x_{i,j})-\nabla\widehat{F}(w)\|^{2}$. Let
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}^{d}$ be $L$-Lipschitz,
$\beta$-smooth, $\mu$-strongly convex (with $\mu=0$ for convex case). Then,
Algorithm 2 with
$\sigma_{i}^{2}:=\frac{256L^{2}R\ln(2.5R/\delta_{0})\ln(2/\delta_{0})}{n^{2}\epsilon_{0}^{2}}$
and $K_{i}=K\geq\frac{\epsilon_{0}n}{4\sqrt{2R\ln(2/\delta_{0})}}$ is
$(\epsilon_{0},\delta_{0})$-LDP for any $\epsilon_{0}\leq 2\ln(2/\delta_{0})$.
Moreover, for any $\mathbf{X}\in\mathcal{X}^{n\times N}$, its output
$\widehat{w}^{ag}_{R}$ satisfies:
1\. (Convex) Setting $R=\max\left(\left(\frac{\beta
D\sqrt{M}\epsilon_{0}n}{L\sqrt{d}}\right)^{1/2},\mathbbm{1}_{\\{MK<Nn\\}}\frac{\epsilon_{0}^{2}n^{2}\hat{\Phi}^{2}}{Kd\ln(1/\delta_{0})L^{2}}\right)$
yields

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})=\widetilde{\mathcal{O}}\left(LD\left(\frac{\sqrt{d\ln(2/\delta_{0})}}{\epsilon_{0}n\sqrt{M}}\right)\right).$
(28)

2\. (Strongly convex) Setting
$R=\max\left(\sqrt{\frac{\beta}{\mu}}\ln\left(\frac{D\mu
M\epsilon_{0}^{2}n^{2}}{Ld}\right),\mathbbm{1}_{\\{MK<Nn\\}}\frac{\epsilon_{0}^{2}n^{2}\hat{\Phi}^{2}}{Kd\ln(1/\delta_{0})L^{2}}\right)$
yields

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{d\ln(2/\delta_{0})}{\epsilon_{0}^{2}n^{2}M}\right)\right).$
(29)

Algorithm 2 Noisy Accelerated MB-SGD

1: Input: Number of clients $N\in\mathbb{N},$ dimension $d\in\mathbb{N}$ of
data, noise parameters $\\{\sigma_{i}\\}_{i\in[N]},$ closed convex set
$\mathcal{W}\subset\mathbb{R}^{d}$, data sets
$X_{i}\in\mathcal{X}_{i}^{n_{i}}$ for $i\in[N]$, loss function $f(w,x),$
number of communication rounds $R\in\mathbb{N}$, number $K_{i}\in\mathbb{N}$
of local samples drawn per round, step size parameters
$\\{\eta_{r}\\}_{r\in[R]},\\{\alpha_{r}\\}_{r\in[R]}$ such that
$\alpha_{1}=1,\alpha_{r}\in(0,1)$ for all $r\geq 2$ and $\eta_{r}>0$ for all
$r\geq 1,$ norm $D$ of some optimum $w^{*}$ of $F.$

2: Set initial point $w_{0}^{ag}=w_{0}\in\mathcal{W}$ and $r=1.$

3: for $r\in[R]$ do

4: Server updates and broadcasts
$w_{r}^{md}=\frac{(1-\alpha_{r})(\mu+\eta_{r})}{\eta_{r}+(1-\alpha_{r}^{2})\mu}w_{r-1}^{ag}+\frac{\alpha_{r}[(1-\alpha_{r})\mu+\eta_{r}]}{\eta_{r}+(1-\alpha_{r}^{2})\mu}w_{r-1}$

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

6: Client draws $K_{i}$ samples $x_{i,j}^{r}$ from $X_{i}$ (for $j\in[K_{i}]$)
and noise $u_{i}\sim\mathcal{N}(0,\sigma_{i}^{2}\mathbf{I}_{d}).$

7: Client computes
$\widetilde{g}_{r}^{i}:=\frac{1}{K_{i}}\sum_{j=1}^{K_{i}}\nabla
f(w_{r}^{md},x_{i,j}^{r})+u_{i}.$

8: end for

9: Server aggregates
$\widetilde{g}_{r}:=\frac{1}{M}\sum_{i=1}^{M}\widetilde{g}_{r}^{i}.$

10: Server updates and
broadcasts:$w_{r}:=\operatorname*{argmin}_{w\in\mathcal{W}}\left\\{\alpha_{r}\left[\langle\widetilde{g}_{r},w\rangle+\frac{\mu}{2}\|w_{r}^{md}-w\|^{2}\right]+\left[(1-\alpha_{r})\frac{\mu}{2}+\frac{\eta_{r}}{2}\right]\|w_{r-1}-w\|^{2}\right\\}.$

11: Server updates and broadcasts
$w_{r}^{ag}=\alpha_{r}w_{r}+(1-\alpha_{r})w_{r-1}^{ag}.$

12: end for

13: Output: $w_{R}^{ag}.$

Next, we state the complete version of Theorem E.1, using notation as in
Section E.1:
Theorem E.1 [Complete Version] Let
$\mathbf{X}\in\mathcal{X}_{1}^{n_{1}}\times\cdots\mathcal{X}_{N}^{n_{N}}.$
Suppose $f(\cdot,x_{i})$ is $L_{i}$-Lipschitz and convex on $\mathcal{W}$ for
all $x_{i}\in\mathcal{X}_{i},i\in[N],$
$\widehat{F}(\cdot,\mathbf{X}):=\widehat{F}(\cdot)$ is
$\widebar{\beta}$-smooth, Assumption 4 part 1 and Assumption 3 hold. Set
$\sigma_{i}^{2}=\frac{256L_{i}^{2}R\ln(\frac{2.5R}{\delta_{i}})\ln(2/\delta_{i})}{n_{i}^{2}\epsilon_{i}^{2}}$.
Denote

$V^{2}:=\frac{\hat{\Phi}^{2}}{MK}+d\min\left\\{\frac{\Sigma^{2}}{M^{\prime}},\frac{\sigma^{2}_{\max}}{M}\right\\},$

where $K:=\min_{i\in[N]}K_{i}$ and
$\sup_{w\in\mathcal{W}}\frac{1}{\widetilde{N}}\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}\|\nabla
f(w,x_{i,j})-\nabla\widehat{F}(w)\|^{2}=\hat{\Phi}^{2}$. Then Algorithm 2 is
$\\{(\epsilon_{i},\delta_{i})\\}_{i\in[N]}$-LDP for any
$\epsilon_{i}\in(0,\ln(\frac{2}{\delta_{i}})]$ and $\delta_{i}\in(0,1),$
provided $K_{i}\geq\frac{\epsilon_{i}n}{4\sqrt{2R\ln(2/\delta_{i})}}$.
Moreover:
1\. Running Algorithm 2 on
$\widetilde{F}(w):=\widehat{F}(w)+\frac{\lambda}{2}\|w\|^{2}$ with
$\lambda:=\frac{V}{2D\sqrt{R}}$ for $R$ rounds yields (for some choice of
stepsizes)

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})\lesssim\frac{\widebar{\beta}D^{2}}{R^{2}}+\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}D}{\sqrt{MKR}}+D\left[\min\left\\{\sqrt{\frac{d\Psi}{M^{\prime}}},\sqrt{\frac{d\psi_{\max}}{M}}\right\\}+\right].$
(30)

In particular, setting
$R=\begin{cases}\max\left\\{\left(\frac{\widebar{\beta}D\sqrt{M^{\prime}}}{\sqrt{d\Psi}}\right)^{1/2},\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{d\Psi}\right\\}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\max\left\\{\left(\frac{\widebar{\beta}D\sqrt{M}}{\sqrt{d\psi_{\max}}}\right)^{1/2},\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{d\psi_{\max}}\right\\}&\mbox{otherwise}\end{cases}$
implies

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})\lesssim
D\sqrt{d}\min\left\\{\frac{\sqrt{\Psi}}{\sqrt{M^{\prime}}},\frac{\sqrt{\psi_{\max}}}{\sqrt{M}}\right\\},$
(31)

assuming $R\geq 1.$
2\. If, in addition, $\widehat{F}$ is $\widebar{\mu}$-strongly convex, then
running a multi-stage implementation of Algorithm 2 directly on $\widehat{F}$
yields

$\displaystyle\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})$
$\displaystyle\lesssim\Delta\exp\left(-\sqrt{\frac{\widebar{\mu}}{\widebar{\beta}}}R\right)$
$\displaystyle+\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{\mu
MKR}+\frac{d}{\widebar{\mu}}\left[\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\}\right],$
(32)

where $\widehat{F}(w_{0})-\widehat{F}^{*}\leq\Delta.$
In particular, choosing
$R=\begin{cases}\max\left\\{\sqrt{\frac{\widebar{\beta}}{\widebar{\mu}}}\ln\left(\frac{\Delta\widebar{\mu}M^{\prime}}{d\Psi}\right),\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{d\Psi}\right\\}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\max\left\\{\sqrt{\frac{\widebar{\beta}}{\widebar{\mu}}}\ln\left(\frac{\Delta\widebar{\mu}M}{d\psi_{\max}}\right),\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{d\psi_{\max}}\right\\}&\mbox{otherwise}\end{cases}$
implies

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})\lesssim\frac{d}{\widebar{\mu}}\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\},$
(33)

provided $R\geq 1.$

###### Proof of Theorem E.1.

LDP of Algorithm 1 follows from LDP of Algorithm 1 (see Theorem 2.1) and the
post-processing property of DP (see Proposition 2.1 in [DR14]). Namely, since
the choice of noise given in Theorem E.1 ensures that clients’ local
stochastic minibatch gradients are LDP and the iterates in Algorithm 2 are
functions of these private noisy gradients (which do not involve additional
data queries), it follows that the iterates themselves are LDP.
For convergence, we begin with the convex ($\widebar{\mu}=0$) part. We will
need the following lemma:

######  Lemma E.11.

[WPS20b] Let $F:\mathcal{W}\to\mathbb{R}^{d}$ be convex and $\beta$-smooth,
and suppose that the unbiased stochastic gradients $\widetilde{g}(w_{t})$ at
each iteration have bounded variance $\mathbb{E}\|\widetilde{g}(w)-\nabla
F(w)\|^{2}\leq V^{2}.$ If $\widehat{w}^{ag}$ is computed by $T$ steps of AC-SA
on the regularized objective
$\widetilde{F}(w)=F(w)+\frac{V}{2\|w_{0}-w^{*}\|\sqrt{T}}\|w-w_{0}\|^{2},$
then

$\mathbb{E}F(\widehat{w}^{ag})-F^{*}\lesssim\frac{\beta\|w_{0}-w^{*}\|^{2}}{T^{2}}+\frac{V\|w_{0}-w^{*}\|}{\sqrt{T}}.$

Combining Lemma E.11 with the estimate of the variance of the stochastic
gradients

$V^{2}=\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{MK}+d\min\left\\{\frac{\Sigma^{2}}{M^{\prime}},\frac{\sigma^{2}_{\max}}{M}\right\\}$

from Lemma E.5 for the ERM case (and replacing $\beta$ by $\widebar{\beta}$)
proves the first (convex) part of Theorem E.1.

For the second (strongly convex) part, we follow [GL13, WPS20b] and use the
following multi-stage implementation of Algorithm 2 to further accelerate
convergence: Let $F(0)-F^{*}\leq\Delta$ and $q_{0}=0.$ Then for $k\in[U]$, do
the following:

  1. 1.

Run $R_{k}$ rounds of Algorithm 2 using $w_{0}=q_{k-1}$,
$\\{\alpha_{r}\\}_{r\geq 1}$ and $\\{\eta_{r}\\}_{r\geq 1},$ where

$R_{k}=\left\lceil\max\left\\{4\sqrt{\frac{2\beta}{\mu}},\frac{128V^{2}}{3\mu\Delta
2^{-(k+1)}}\right\\}\right\rceil,$
$\alpha_{r}=\frac{2}{r+1},~{}\eta_{r}=\frac{4\upsilon_{k}}{r(r+1)},$
$\upsilon_{k}=\max\left\\{2\beta,\left[\frac{\mu V^{2}}{3\Delta
2^{-(k-1)}R_{k}(R_{k}+1)(R_{k}+2)}\right]^{1/2}\right\\}$

  2. 2.

Set $q_{k}=w_{R_{k}}^{ag},$ where $w_{R_{k}}^{ag}$ is the output of Step 1
above. Then update $k\leftarrow k+1$ and return to Step 1.

We then have the following risk bound for the multi-stage protocol:

######  Lemma E.12.

[GL13] Let $F:\mathcal{W}\to\mathbb{R}^{d}$ be $\mu$-strongly convex and
$\beta$-smooth, and suppose that the unbiased stochastic gradients
$\widetilde{g}(w_{t})$ at each iteration have bounded variance
$\mathbb{E}\|\widetilde{g}(w)-\nabla F(w)\|^{2}\leq V^{2}.$ If
$\widehat{w}^{ag}$ is computed by $T$ steps of the multi-stage AC-SA, then

$\mathbb{E}F(\widehat{w}^{ag})-F^{*}\lesssim\Delta\exp\left(-\sqrt{\frac{\mu}{\beta}}T\right)+\frac{V^{2}}{\mu
T},$

where $\Delta=F(w_{0})-F^{*}.$

In our notation, $T=R$ and $F$ is replaced by $\widehat{F}$, which is
$\widebar{\mu}$-strongly convex and $\widebar{\beta}$-smooth by assumption. If
$U$ is chosen so that $\sum_{k=1}^{U}R_{k}\leq R$ total rounds of Algorithm 2,
then the full algorithm, run with noise $\sigma_{i}^{2}$ specified in Theorem
E.1 [Complete Version], is LDP. Applying Lemma E.12 with

$V^{2}=\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\hat{\Phi}^{2}}{MK}+d\min\left\\{\frac{\Sigma^{2}}{M^{\prime}},\frac{\sigma^{2}_{\max}}{M}\right\\}$

from Lemma E.5 proves the strongly convex portion of Theorem E.1. ∎

####  E.5.2 Complete version and proof of Theorem 2.4

We now turn to non-smooth losses. With notation as in Section E.1, we have the
following precise version of Theorem 2.4:

Theorem 2.4 [Complete Version] Suppose $f(\cdot,x_{i})$ is $L$-Lipschitz and
convex on $\mathcal{W}$ for all $x_{i}\in\mathcal{X}_{i},i\in[N],$ Assumption
4 part 1 and Assumption 3 hold. Set
$\sigma_{i}^{2}=\frac{256L^{2}R\ln(\frac{2.5R}{\delta_{i}})\ln(2/\delta_{i})}{n_{i}^{2}\epsilon_{i}^{2}}$.
Denote

$V^{2}=\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{4L^{2}}{MK}+d\min\left\\{\frac{\Sigma^{2}}{M^{\prime}},\frac{\sigma^{2}_{\max}}{M}\right\\},$

where $K:=\min_{i\in[N]}K_{i}.$ Also denote
$\widetilde{M}:=\begin{cases}\sqrt{M^{\prime}}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\sqrt{M}&\mbox{otherwise}\end{cases}$ and
$\widetilde{\Psi}:=\begin{cases}\Psi&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\psi_{\max}&\mbox{otherwise}\end{cases}.$ Fix any
$\mathbf{X}\in\mathcal{X}_{1}^{n_{1}}\times\cdots\times\mathcal{X}_{N}^{n_{N}}$
and denote
$\widehat{F}_{\beta}(w):=\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}\frac{1}{n_{i}}f_{\beta}(w,x_{i,j}),$
with $f_{\beta}$ defined earlier (see complete version of Theorem 2.2). Then
Algorithm 2 is $\\{(\epsilon_{i},\delta_{i})\\}_{i=1}^{N}$-LDP provided
$K_{i}\geq\frac{\epsilon_{i}n}{4\sqrt{2R\ln(2/\delta_{i})}}$ and
$\epsilon_{i}\leq\ln(2/\delta_{i})$. Further:
1\. Running Algorithm 2 on
$\widetilde{F}_{\beta}(w):=\widehat{F}_{\beta}(w)+\frac{\lambda}{2}\|w\|^{2}$
with $\lambda:=\frac{V}{2D\sqrt{R}}$ and
$\beta:=\frac{L^{2}\sqrt{\widetilde{M}}}{D\sqrt{d\widetilde{\Psi}}}$ for $R$
rounds yields (for some choice of stepsizes)

$\displaystyle\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})$
$\displaystyle\lesssim\frac{L^{2}D\sqrt{\widetilde{M}}}{R^{2}\sqrt{d\widetilde{\Psi}}}+~{}\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{LD}{\sqrt{MKR}}+D\sqrt{d}\left[\min\left\\{\sqrt{\frac{\Psi}{M^{\prime}}},\sqrt{\frac{\psi_{\max}}{M}}\right\\}\right]$

In particular, setting
$R=\begin{cases}\max\left\\{\left(\frac{L\sqrt{M^{\prime}}}{\sqrt{d\Psi}}\right),~{}\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{L^{2}}{d\Psi}\right\\}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\max\left\\{\left(\frac{L\sqrt{M}}{\sqrt{d\psi_{\max}}}\right),~{}\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{L^{2}}{d\psi_{\max}}\right\\}&\mbox{otherwise}\end{cases}$
implies

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})\lesssim
D\sqrt{d}\min\left\\{\frac{\sqrt{\Psi}}{\sqrt{M^{\prime}}},\frac{\sqrt{\psi_{\max}}}{\sqrt{M}}\right\\},$
(34)

assuming $R\geq 1.$
2\. If, in addition, $\widehat{F}$ is $\widebar{\mu}$-strongly convex, then
running a multi-stage implementation of Algorithm 2 on $\widehat{F}_{\beta}$
with $\beta:=\frac{\widebar{\mu}\widetilde{M}L^{2}}{d\widetilde{\Psi}}$ yields

$\displaystyle\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})$
$\displaystyle\lesssim\Delta\exp\left(-R\sqrt{\frac{d\widetilde{\Psi}}{\widetilde{M}L^{2}}}\right)+\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{\Phi^{2}}{\mu
MKR}+\frac{d}{\widebar{\mu}}\left[\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\}\right],$
(35)

where $F(w_{0})-F^{*}\leq\Delta\leq LD.$
In particular, choosing
$R=\begin{cases}\max\left\\{\sqrt{\frac{M^{\prime}L^{2}}{d\Psi}}\ln\left(\frac{\Delta\widebar{\mu}M^{\prime}}{d\Psi}\right),\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{L^{2}}{d\Psi}\right\\}&\mbox{if}~{}\frac{\Psi}{M^{\prime}}\leq\frac{\psi_{\max}}{M}\\\
\max\left\\{\sqrt{\frac{ML^{2}}{d\psi_{\max}}}\ln\left(\frac{\Delta\widebar{\mu}M}{d\psi_{\max}}\right),\mathbbm{1}_{\\{MK<\widetilde{N}\\}}\frac{L^{2}}{d\psi_{\max}}\right\\}&\mbox{otherwise}\end{cases}$
implies

$\mathbb{E}\widehat{F}(w_{R}^{ag})-\widehat{F}(w^{*})\lesssim\frac{d}{\widebar{\mu}}\min\left\\{\frac{\Psi}{M^{\prime}},\frac{\psi_{\max}}{M}\right\\},$
(36)

provided $R\geq 1.$

###### Proof.

The proof is very similar to the proof of Theorem 2.2. Note that by Lemma
E.10, $f_{\beta}(\cdot,x)$ and $\widehat{F}_{\beta}$ are $2L$-Lipschitz for
all $x\in\mathcal{X}$, so
$\hat{\Phi}^{2}_{\beta}:=\sup_{w}\frac{1}{\widetilde{N}}\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}\|\nabla
f_{\beta}(w,x_{i,j})-\nabla\widehat{F}_{\beta}(w)\|^{2}\leq 4L^{2}$. Now, we
apply Theorem E.1 to the $\beta$-smooth objective $\widetilde{F}_{\beta}$ (for
convex case) or $\widehat{F}_{\beta}$ (for strongly convex) and use Lemma
E.10. Our choice of $R$ ensures that excess risk with respect to $\widehat{F}$
increases by at most $L^{2}/\beta$, compared to the smooth bounds in Theorem
E.1. Our choice of $\beta$ ensures that $L^{2}/\beta$ is upper bounded by the
smooth bounds in Theorem E.1. ∎

###  E.6 Complete version and proof of Theorem 2.3

We will state and prove the theorem for general $M\in[N]$ (c.f. Assumption 3).
However, for simplicity, we will assume same parameters across clients
($n_{i}=n,\epsilon_{i}=\epsilon_{0},\delta_{i}=\delta,\phi_{i}=\phi,L_{i}=L$).

Theorem 2.3 [Complete Version] Let $f(\cdot,x)$ be $\beta$-smooth for all
$x\in\mathcal{X}.$ Assume $\epsilon_{0}\leq
8\ln(1/\delta_{0}),~{}\delta_{0}\in(0,1)$ Then, with
$\sigma^{2}=\frac{32L^{2}\ln(1.25/\delta_{0})}{\epsilon_{0}^{2}K^{2}}$, One-
Pass Accelerated Noisy MB-SGD is $(\epsilon_{0},\delta_{0})$-LDP. Moreover, we
have the following excess population loss bounds:
1\. Running One-Pass Accelerated Noisy MB-SGD on
$\widetilde{F}(w):=\widehat{F}(w)+\frac{\lambda}{2}\|w\|^{2}$ with batch size
$K$ yields (for some choices of $\lambda$ and stepsizes)

$\mathbb{E}F(w_{R}^{ag})-F(w^{*})\lesssim\frac{\beta^{2}D^{2}K^{2}}{n^{2}}+\frac{\phi
D}{\sqrt{nM}}+\frac{LD\sqrt{d\ln(1/\delta_{0})}}{\epsilon_{0}\sqrt{KnM}}+\frac{\sqrt{K}\upsilon
D}{\sqrt{nM}}\sqrt{\frac{N-M}{N-1}}\mathbbm{1}_{\\{N>1\\}}.$

Choosing $K=\left(\frac{L}{\beta
D}\right)^{2/5}\frac{n^{3/5}(d\ln(1/\delta_{0})^{1/5}}{\epsilon_{0}^{2/5}M^{1/5}}$
implies

$\mathbb{E}F(w_{R}^{ag})-F(w^{*})=\widetilde{\mathcal{O}}\left(\frac{\phi
D}{\sqrt{nM}}+\left(\frac{\beta^{1/4}LD^{3/2}\sqrt{d\ln(1/\delta_{0})}}{\epsilon_{0}n\sqrt{M}}\right)^{4/5}+\sqrt{\frac{N-M}{N-1}}\mathbbm{1}_{\\{N>1\\}}\frac{\upsilon
L^{1/5}D^{4/5}}{\beta^{1/5}}\left(\frac{\sqrt{d\ln(1/\delta_{0})}}{\epsilon_{0}nM^{3}}\right)^{1/5}\right).$
(37)

In particular, if $M=N$ or
$\upsilon\lesssim\sqrt{\frac{N-1}{N-M}}\left[(L^{3}D^{2}\beta^{2})^{1/5}\frac{M^{1/5}(d\ln(1/\delta_{0}))^{3/10}}{n^{3/5}\epsilon_{0}^{3/5}}+\phi\left(\frac{\beta
D}{L}\right)^{1/5}\left(\frac{\epsilon_{0}^{2}M}{n^{3}d\ln(1/\delta_{0})}\right)^{1/10}\right]$,
then we recover the bound 8 in the informal version of Theorem 2.3, with $N$
replaced by $M$.

2\. If $f(\cdot,x)$ is $\mu$-strongly convex $\forall x\in\mathcal{X}$ and
$\kappa=\frac{\beta}{\mu}$, then running One-Pass Accelerated Noisy MB-SGD
directly on $\widehat{F}$ with batch size $K$ yields

$\mathbb{E}F(w_{R}^{ag})-F(w^{*})\lesssim\Delta\exp\left(\frac{-n}{K\sqrt{\kappa}}\right)+\frac{\phi^{2}}{\mu
nM}+\frac{\upsilon^{2}K}{\mu
nM}\left(1-\frac{M-1}{N-1}\right)\mathbbm{1}_{\\{N>1\\}}+\frac{L^{2}}{\mu}\frac{d\ln(1/\delta_{0})}{Kn\epsilon_{0}^{2}M},$

where $F(w_{0})-F^{*}\leq\Delta$. Choosing
$K=\frac{n}{\sqrt{\kappa}\ln\left(\mu\Delta\min\left\\{\frac{\epsilon_{0}^{2}n^{2}M}{L^{2}d\ln(1/\delta_{0})},\frac{nM}{\phi^{2}}\right\\}\right)}$
implies

$\mathbb{E}F(w_{R}^{ag})-F(w^{*})=\widetilde{\mathcal{O}}\left(\frac{\phi^{2}}{nM}+\frac{L^{2}}{\mu}\frac{\sqrt{\kappa}d\ln(1/\delta_{0})}{\epsilon_{0}^{2}n^{2}M}+\frac{\upsilon^{2}}{\mu\sqrt{\kappa}M}\left(1-\frac{M-1}{N-1}\right)\mathbbm{1}_{\\{N>1\\}}\right).$
(38)

In particular, if $M=N$ or
$\upsilon^{2}\lesssim\left(\frac{N-1}{N-M}\right)\sqrt{\kappa}\left(\frac{\phi^{2}}{n}+\frac{\sqrt{\kappa}L^{2}d\ln(1/\delta_{0})}{\epsilon_{0}^{2}n^{2}}\right)$,
then we recover the bound 9 in the informal version of Theorem 2.3, with $N$
replaced by $M$.

######  Remark E.2.

$K$ can be tuned to minimize population loss depending on the specific values
of parameters $n,M,N,d,\epsilon_{0},\delta_{0},L,\beta,D,\mu$. The choices of
$K$ that are prescribed minimize the respective population losses when $M=N$.
The bound 8 in the informal version of Theorem 2.3 is attained (with $N$
replaced by $M$) when communication is reliable so $M\approx N$, when data is
fairly homogeneous so $\upsilon$ is small (relative to $L$), or when
$M\gtrsim\left(\frac{\epsilon_{0}n}{d\ln(1/\delta_{0})}\right)^{3}$. The bound
9 in the informal version of Theorem 2.3 is attained (with $N$ replaced by
$M$) when communication is reliable so $M\approx N$, when data is fairly
homogeneous and/or $f$ is ill-conditioned so that $\upsilon$ is small relative
to $L\sqrt{\kappa}$.

###### Proof of Theorem 2.3.

1\. Privacy: By post-processing, it suffices to show that the $R=n/K$ noisy
stochastic gradients computed in line 6 of Algorithm 2 are
$(\epsilon_{0},\delta_{0})$-LDP. Further, since the batches sampled locally
are disjoint (because we sample locally without replacement), parallel
composition [McS09] implies that if each update in line 6 is
$(\epsilon_{0},\delta_{0})$-LDP, then the full algorithm is
$(\epsilon_{0},\delta_{0})$-LDP. Now recall that the Gaussian mechanism
provides $(\epsilon_{0},\delta_{0})$-DP if
$\sigma^{2}\geq\frac{8\Delta_{2}^{2}\ln(1.25/\delta_{0})}{\epsilon_{0}^{2}}$,
where $\Delta_{2}=\sup_{w,X_{i}\sim
X^{\prime}_{i}}\|\frac{1}{K}\sum_{j=1}^{K}\nabla f(w,x_{i,j})-\nabla
f(w,x_{i,j}^{\prime})\|=\sup_{w,x,x^{\prime}}\frac{1}{K}\|\nabla f(w,x)-\nabla
f(w,x^{\prime})\|\leq\frac{2L}{K}$ is the $L_{2}$ sensitivity of the non-
private gradient update in line 6 of Algorithm 2: this follows from [BS16,
Propositions 1.3 and 1.6] and our assumption $\epsilon_{0}\leq
8\ln(1/\delta_{0})$. Therefore, conditional on the private transcript of all
other clients, our choice of $\sigma^{2}$ implies that client $i$’s transcript
is $(\epsilon_{0},\delta_{0})$-DP for all $i\in[N]$, which means that One-Pass
Noisy Accelerated Distributed MB-SGD is $(\epsilon_{0},\delta_{0})$-LDP.
2\. Excess loss: For the convex case, we choose
$\lambda=\frac{V}{2D\sqrt{R}}$, where
$V^{2}=\frac{\phi^{2}}{MK}+\frac{\upsilon^{2}}{M}\mathbbm{1}_{\\{N>1\\}}\left(\frac{N-M}{N-1}\right)+\frac{d\sigma^{2}}{M}$
is the variance of the noisy stochastic minibatch gradients (c.f. Lemma E.5)
for our noise with variance
$\sigma^{2}=\frac{8L^{2}\ln(1.25/\delta_{0})}{K^{2}\epsilon_{0}^{2}}$. Now
plugging $V^{2}$ into Lemma E.11 and setting $T=R=n/K$ gives the first bound
in terms of $K$. Then verify that plugging in the prescribed $K$ yields 37.

Similarly, for strongly convex loss, we plug the same estimate for $V^{2}$
into Lemma E.12 with $T=R=n/K$ (using the multi-stage implementation of
Algorithm 2, described in the previous subsection of this appendix) yields the
strongly convex bound as a function of $K$. Finally, plugging in the
prescribed $K$ yields 38. ∎

##  Appendix F Lower Bounds for LDP FL: Supplemental Material and Proofs

###  F.1 Algorithms whose Privacy follows from Advanced Composition Theorem
are $1$-Compositional

Suppose $\mathcal{A}$ is $(\epsilon_{0},\delta_{0})$-LDP by the advanced
composition theorem [DR14, Theorem 3.20]. Then

$\epsilon_{0}=\sqrt{2\sum_{r=1}^{R}(\epsilon_{0}^{r})^{2}\ln(1/\delta^{\prime})}+\sum_{r=1}^{R}\epsilon_{0}^{r}(e^{\epsilon_{0}^{r}}-1),$

and $\delta_{0}=\sum_{r=1}^{R}\delta_{0}^{r}+\delta^{\prime}$ for any
$\delta^{\prime}\in(0,1)$. Assume $\delta^{\prime}\in(0,1/3)$ without loss of
generality: otherwise the privacy guarantee of $\mathcal{A}$ is essentially
meaningless (see Remark F.1). Then
$\epsilon_{0}\geq\sqrt{2\sum_{r=1}^{R}(\epsilon_{0}^{r})^{2}\ln(1/\delta^{\prime})}\geq\sqrt{2}\sqrt{\sum_{r=1}^{R}(\epsilon_{0}^{r})^{2}}\geq\sqrt{\sum_{r=1}^{R}(\epsilon_{0}^{r})^{2}}$,
so that $\mathcal{A}$ is $1$-compositional. Note that even if
$\delta^{\prime}>1/3$, $\mathcal{A}$ would still be compositional, but the
constant $C$ may be larger than $1$.

###  F.2 Example of LDP Algorithm that is Not Compositional

This example is a simple modification of Example 2.2 in [JMNR19] (adapted to
our definition of compositionality for $\delta_{0}>0$). Given any $C>0$, set
$d:=2C^{2}$ and let $\mathcal{X}=\\{e_{1},\cdots e_{d}\\}\subset\\{0,1\\}^{d}$
be the standard basis for $\mathbb{R}^{d}.$ Let $n=1$ and
$\mathbf{X}=(x_{1},\cdots,x_{N})\in\mathcal{X}^{N}.$ For all $i\in[N]$ let
$\mathcal{Q}^{(i)}:\mathcal{X}\to\mathcal{X}$ be the randomized response
mechanism that outputs $\mathcal{Q}^{(i)}(x_{i})=x_{i}$ with probability
$\frac{e^{\epsilon_{0}}}{e^{\epsilon_{0}}+d-1}$ and otherwise outputs a
uniformly random element of $\mathcal{X}\setminus\\{x_{i}\\}.$ Note that
$\mathcal{Q}^{(i)}$ is $\epsilon_{0}$-DP, hence $(\epsilon_{0},\delta_{0})$-DP
for any $\delta_{0}>0$. Consider the $d$-round algorithm
$\mathcal{A}:\mathcal{X}^{N}\to\mathcal{Z}^{d\times N}$ in Algorithm 3, where
$\mathcal{Z}=\mathbb{R}^{d}$

Algorithm 3 LDP Algorithm that is not $C$-compositional

1: for $r\in[d]$ do

2: for $i\in N$ do

3: if $x_{i}=e_{r}$ then

4: $\mathcal{R}^{(i)}_{r}(x_{i}):=\mathcal{Q}^{(i)}(x_{i})$.

5: else

6: $\mathcal{R}^{(i)}_{r}(x_{i}):=0\in\mathbb{R}^{d}$.

7: end if

8: end for

9: end for

10: Output: $\\{\mathcal{R}^{(i)}_{r}(x_{i})\\}_{i\in[N],r\in[d]}$.

Since each client’s data is only referenced once and $\mathcal{Q}^{(i)}$ is
$\epsilon_{0}$-DP, we have $\epsilon_{0}^{r}=\epsilon_{0}$ and $\mathcal{A}$
is $(\epsilon_{0},\delta_{0})$-DP. However,
$\sqrt{\sum_{r=1}^{d}(\epsilon_{0}^{r})^{2}}=\sqrt{d\epsilon_{0}^{2}}=\sqrt{2}C\epsilon_{0}>C\epsilon_{0}$,
so that $\mathcal{A}$ is not $C$-compositional.

###  F.3 Proof of Theorem 3.1

Before we proceed to the proof of Theorem 3.1, we recall the simpler
characterization of LDP for sequentially interactive algorithms. A
sequentially interactive algorithm $\mathcal{A}$ with randomizers
$\\{\mathcal{R}^{(i)}\\}_{i=1}^{N}$ is $(\epsilon_{0},\delta_{0})$-LDP if and
only if for all $i\in[N]$,
$\mathcal{R}^{(i)}(\cdot,Z^{(1:i-1)}):\mathcal{X}_{i}^{n}\times\mathcal{Z}$ is
$(\epsilon_{0},\delta_{0})$-DP for all $Z^{(1:i-1)}\in\mathcal{Z}^{i-1}$. In
what follows, we will fix $\mathcal{X}_{i}=\mathcal{X}$ for all $i$. We now
turn to the proof.

Step 1: Privacy amplification by shuffling. We begin by stating and proving
the amplification by shuffling result that we will leverage to obtain Theorem
3.1:

######  Theorem F.1.

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}$. If $\mathcal{A}$ is compositional, then
assume $\delta_{0}^{r}\in[\frac{2e^{-N/16}}{Nn},\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}\in[\frac{2e^{-N/16}}{Nn},\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}.$

To the best of our knowledge, the restriction on $\epsilon_{0}^{r}$ is needed
to obtain $\epsilon=\widetilde{O}(\epsilon_{0}/\sqrt{N})$ in all works that
have analyzed privacy amplification by shuffling [EFM+20b, FMT20, BBGN19,
CSU+19, BKM+20], but these works focus on the sequentially interactive case
with $n=1$, so the restriction amounts to $\epsilon_{0}\lesssim 1$ (or
$\epsilon_{0}=\widetilde{O}(1)).$ The non-sequential $C$-compositional part of
Theorem F.1 will follow as a corollary (Corollary F.1 ) of the following
result which analyzes the privacy amplification in each round:

######  Theorem F.2 (Single round privacy amplification by shuffling).

Let
$\epsilon^{r}_{0}\leq\ln\left(\frac{N}{16\ln(2/\delta^{r})}\right)/n,~{}r\in\mathbb{N}$
and let
$\mathcal{R}^{(i)}_{r}(\mathbf{Z},\cdot):\mathcal{X}^{n}\to\mathcal{Z}$ be an
$(\epsilon_{0}^{r},\delta_{0}^{r})$-DP local randomizer for all
$\mathbf{Z}=Z_{(1:r-1)}^{(1:N)}\in\mathcal{Z}^{(r-1)\times N}$ and $i\in[N],$
where $\mathcal{X}$ is an arbitrary set. Given a distributed data set
$\mathbf{X}=(X_{1},\cdots,X_{N})\in\mathcal{X}^{N\times n}$ and
$\mathbf{Z}=Z_{(1:r-1)}^{(1:N)}$, consider the shuffled algorithm
$\mathcal{A}^{r}_{s}:\mathcal{X}^{n\times N}\times\mathcal{Z}^{(r-1)\times
N}\to\mathcal{Z}^{N}$ that first samples a random permutation $\pi$ of $[N]$
and then computes $Z_{r}=(Z^{(1)}_{r},\cdots,Z^{(N)}_{r}),$ where
$Z^{(i)}_{r}:=\mathcal{R}^{(i)}_{r}(\mathbf{Z},X_{\pi(i)}).$ Then,
$\mathcal{A}^{r}_{s}$ is $(\epsilon^{r},\widetilde{\delta}^{r})$-CDP, where

$\epsilon^{r}:=\ln\left[1+\left(\frac{e^{\epsilon_{0}^{r}}-1}{e^{\epsilon_{0}^{r}}+1}\right)\left(\frac{8\sqrt{e^{n\epsilon_{0}^{r}}\ln(4/\delta^{r})}}{\sqrt{N}}+\frac{8e^{n\epsilon_{0}^{r}}}{N}\right)\right],$
(39)

and
$\widetilde{\delta^{r}}:=\delta^{r}+2Nne^{(n-1)\epsilon_{0}^{r}}\delta_{0}^{r}.$
In particular, if $\epsilon_{0}^{r}=\mathcal{O}\left(\frac{1}{n}\right),$ then

$\epsilon^{r}=\mathcal{O}\left(\frac{\epsilon_{0}^{r}\sqrt{\ln(1/\delta^{r})}}{\sqrt{N}}\right).$
(40)

Further, if $\epsilon_{0}^{r}\leq 1/n$, then setting
$\delta^{r}:=Nn\delta_{0}^{r}$ implies that

$\epsilon^{r}=\mathcal{O}\left(\frac{\epsilon_{0}^{r}\sqrt{\ln(1/nN\delta_{0}^{r})}}{\sqrt{N}}\right)$
(41)

and $\widetilde{\delta^{r}}\leq 7Nn\delta_{0}^{r}$, which is in $(0,1)$ if we
assume $\delta_{0}^{r}\in(0,\frac{1}{7Nn}].$

We sometimes refer to the algorithm $\mathcal{A}_{s}^{r}$ as the “shuffled
algorithm derived from the randomizers $\\{\mathcal{R}^{(i)}_{r}\\}.$” From
Theorem F.2, we obtain:

######  Corollary F.1 ($R$-round privacy amplification for $C$-compositional
algorithms).

Let $\mathcal{A}:\mathcal{X}^{n\times N}\to\mathcal{Z}^{R\times N}$ be an
$R$-round $(\epsilon_{0},\delta_{0})$-LDP and $C$-compositional algorithm such
that $\epsilon_{0}\in(0,\sqrt{N}]$ and $\delta_{0}\in(0,1),$ where
$\mathcal{X}$ is an arbitrary set. 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 $i\in[N],r\in[R]$, where
$\epsilon_{0}^{r}\leq\frac{1}{n}$, and
$\delta_{0}^{r}\in[\frac{2e^{-N/16}}{Nn},\frac{1}{14nNR}].$ Then, the shuffled
algorithm $\mathcal{A}_{s}:\mathcal{X}^{n\times N}\to\mathcal{Z}^{R\times N}$
derived from
$\\{\mathcal{R}^{(i)}_{r}(\mathbf{Z}_{(1:r-1),\cdot})\\}_{i\in[N],r\in[R]}$
(i.e. $\mathcal{A}_{s}$ is the composition of the $R$ shuffled algorithms
$\mathcal{A}^{r}_{s}$ defined in Theorem F.2) is $(\epsilon,\delta)$-CDP,
where $\delta\leq 14Nn\sum_{r=1}^{R}\delta_{0}^{r}$ and
$\epsilon=\mathcal{O}\left(\frac{\epsilon_{0}\ln\left(1/nN\delta_{0}^{\min}\right)C^{2}}{\sqrt{N}}\right),$
where $\delta_{0}^{\min}:=\min_{r\in[R]}\delta_{0}^{r}.$ In particular, if
$\mathcal{A}\in\mathbb{A}$ is compositional, then
$\epsilon=\mathcal{O}\left(\frac{\epsilon_{0}\ln\left(1/nN\delta_{0}^{\min}\right)}{\sqrt{N}}\right)$.

###### Proof.

Let $\delta^{\prime}:=\sum_{r}Nn\delta_{0}^{r}$ and
$\delta^{r}:=Nn\delta_{0}^{r}.$ Then the (central) privacy loss of the full
$R$-round shuffled algorithm is bounded as

$\displaystyle\epsilon$ $\displaystyle\leq
2\sum_{r}(\epsilon^{r})^{2}+\sqrt{2\sum_{r}(\epsilon^{r})^{2}\ln(1/\delta^{\prime})}$
$\displaystyle=\mathcal{O}\left(\sum_{r}\left(\frac{(\epsilon_{0}^{r})^{2}\ln(1/\delta^{r})}{N}\right)+\sqrt{\sum_{r}\frac{(\epsilon_{0}^{r})^{2}\ln(1/\delta^{r})\ln(1/\delta^{\prime})}{N}}\right)$
$\displaystyle=\mathcal{O}\left(\frac{C^{2}\epsilon_{0}\ln(1/nN\delta_{0}^{\min})}{\sqrt{N}}\right),$

where the three (in)equalities follow in order from the Advanced Composition
Theorem [DR14], 41 in Theorem F.2, and $C$-compositionality of $\mathcal{A}$
combined with the assumption $\epsilon_{0}\lesssim\sqrt{N}$. Also,
$\delta=\delta^{\prime}+\sum_{r}\widetilde{\delta}^{r}$ by the Advanced
Composition Theorem, where $\widetilde{\delta}_{r}\leq 7Nn\delta_{0}^{r}$ by
Theorem F.2. Hence $\delta\leq 14Nn\sum_{r}\delta_{0}^{r}.$ In particular, if
$\mathcal{A}$ is compositional, then $C=\mathcal{O}(1)$, so
$\epsilon=\mathcal{O}\left(\frac{\epsilon_{0}\ln\left(1/nN\delta_{0}^{\min}\right)}{\sqrt{N}}\right)$.
∎

######  Remark F.1.

The upper bounds assumed on $\delta_{0}^{r}$ and $\delta^{r}$ in Theorem 3.1
ensure that $\delta\in(0,1)$ and that the lower bounds of [BST14] apply (see
Theorem F.3). These assumptions are not very restrictive in practice, since
$\delta_{0}^{r},\delta_{0}\ll 1/n$ is needed for meaningful privacy guarantees
(see e.g. Chapter 2 in [DR14]) and $R$ must be polynomial for the algorithm to
run. To quote [DR14], “typically we are interested in values of $\delta$ that
are less than the inverse of any polynomial in the size of the database” (page
18). For larger $\delta$ (e.g. $\delta=\Omega(1/n)$), there are examples of
algorithms that satisfy the definition of DP but clearly violate any
reasonable notion of privacy. For instance, an algorithm that outputs
$\delta_{0}n$ random samples from each client’s data set is
$(0,\delta_{0})$-LDP, but completely violates the privacy of at least one
person in each client if $\delta\geq 1/n$. Also, since $N\gg 1$ is the regime
of interest (otherwise if $N=\widetilde{O}(1)$, the CDP lower bounds of
[BFTT19] already match our upper bounds up to logarithms), the requirement
that $N$ be larger than $16\ln(2/\delta_{0}^{\min}n)$ is
unimportant.161616Technically, this assumption on $N$ is needed to ensure that
the condition on $\epsilon_{0}^{r}$ in Theorem F.2 is satisfied. A similar
restriction appears in Theorem 3.8 of [FMT20].

The sequentially interactive part of Theorem F.1 will be clear directly from
the proof of Theorem F.2. We now turn to the proof of Theorem F.2, which uses
the techniques from [FMT20]. First, we’ll need some more notation. The privacy
relation in 3 between random variables $P$ and $Q$ can be characterized by the
hockey-stick divergence:
$D_{e^{\epsilon}}(P\|Q):=\int\max\\{0,p(x)-e^{\epsilon}q(x)\\}dx,$ where $p$
and $q$ denote the probability density or mass functions of $P$ and $Q$
respectively. Then $P\underset{(\epsilon,\delta)}{\simeq}Q$ iff
$\max\\{D_{e^{\epsilon}}(P\|Q),D_{e^{\epsilon}}(Q\|P)\\}\leq\delta.$ Second,
recall the total variation distance between $P$ and $Q$ is given by
$TV(P,Q)=\frac{1}{2}\int_{\mathbb{R}}|p(x)-q(x)|dx.$ Third, we recall the
notion of group privacy:

######  Definition 6 (Group DP).

A randomized algorithm $\mathcal{A}:\mathcal{X}^{\mathcal{N}}\to\mathcal{Z}$
is $(\epsilon,\delta)$ group DP for groups of size $\mathcal{N}$ if
$\mathcal{A}(\mathbf{X})\underset{(\epsilon,\delta)}{\simeq}\mathcal{A}(\mathbf{X}^{\prime})$
for all $\mathbf{X},\mathbf{X}^{\prime}\in\mathcal{X}^{\mathcal{N}}.$

We’ll also need the following stronger version of a decomposition from [KOV15]
and Lemma 3.2 of [MV16].

######  Lemma F.1 ([KOV15]).

Let $\mathcal{R}_{0},\mathcal{R}_{1}:\mathcal{X}^{n}\to\mathcal{Z}$ be local
randomizers such that $\mathcal{R}_{0}(X_{0})$ and $\mathcal{R}_{1}(X_{1})$
are $(\epsilon,0)$ indistinguishable. Then, there exists a randomized
algorithm $U:\\{X_{0},X_{1}\\}\to\mathcal{Z}$ such that
$R_{0}(X_{0})=\frac{e^{\epsilon}}{e^{\epsilon}+1}U(X_{0})+\frac{1}{e^{\epsilon}+1}U(X_{1})$
and
$R_{1}(X_{1})=\frac{1}{e^{\epsilon}+1}U(X_{0})+\frac{e^{\epsilon}}{e^{\epsilon}+1}U(X_{1}).$

Lemma F.1 follows from the proof of Lemma 3.2 in [MV16], noting that the
weaker hypothesis assumed in Lemma F.1 sufficient for all steps to go through.

######  Definition 7 (Deletion Group DP).

Algorithm $\mathcal{R}:\mathcal{X}^{n}\to\mathcal{Z}$ is $(\epsilon,\delta)$
deletion group DP for groups of size $n$ if there exists a reference
distribution $\rho$ such that
$\mathcal{R}(X)\underset{(\epsilon,\delta)}{\simeq}\rho$ for all
$X\in\mathcal{X}^{n}.$

It’s easy to show that if $\mathcal{R}$ is deletion group DP for groups of
size $n$, then $\mathcal{R}$ is $(2\epsilon,(1+e^{\epsilon})\delta)$ group DP
for groups of size $n$. In addition, we have the following result:

######  Lemma F.2.

Let $X_{0}\in\mathcal{X}^{n}.$ If $\mathcal{R}:\mathcal{X}^{n}\to\mathcal{Z}$
is an $(\epsilon,\delta)$-DP local randomizer, then $\mathcal{R}$ is
$(n\epsilon,ne^{(n-1)\epsilon}\delta)$ deletion group DP for groups of size
$n$ with reference distribution $\mathcal{R}(X_{0})$ (i.e.
$\mathcal{R}(X)\underset{(\widetilde{\epsilon},\widetilde{\delta})}{\simeq}\mathcal{R}(X_{0})$
for all $X\in\mathcal{X}^{n}$, where $\widetilde{\epsilon}=n\epsilon$ and
$\widetilde{\delta}=ne^{(n-1)\epsilon}\delta$).

###### Proof.

By group privacy (see e.g. Theorem 10 in [Kam20]), and the assumption that
$\mathcal{R}$ is $(\epsilon,\delta)$-DP, it follows that $\mathcal{R}(X)$ and
$\mathcal{R}(X^{\prime})$ are $(n\epsilon,ne^{(n-1)\epsilon}\delta)$
indistinguishable for all $X,X^{\prime}\in\mathcal{X}^{n}.$ In particular,
taking $X^{\prime}:=X_{0}$ completes the proof. ∎

######  Lemma F.3.

Let $\mathcal{R}^{(i)}:\mathcal{X}^{n}\to\mathcal{Z}$ be randomized algorithms
($i\in[N]$) and let $\mathcal{A}_{s}:\mathcal{X}^{n\times
N}\to\mathcal{Z}^{N}$ be the shuffled algorithm
$\mathcal{A}_{s}(\mathbf{X}):=(\mathcal{R}^{(1)}(X_{\pi(1)}),\cdots\mathcal{R}^{(N)}(X_{\pi(N)}))$
derived from $\\{\mathcal{R}^{(i)}\\}_{i\in[N]}$ for
$\mathbf{X}=(X_{1},\cdots,X_{N})$, where $\pi$ is a uniformly random
permutation of $[N]$. Let $\mathbf{X}_{0}=(X_{1}^{0},X_{2},\cdots,X_{N})$ and
$\mathbf{X}_{1}=(X_{1}^{1},X_{2},\cdots,X_{N})$, $\delta\in(0,1)$ and
$p\in[\frac{16\ln(2/\delta)}{N},1]$. Suppose that for all
$i\in[N],X\in\mathcal{X}^{n}\setminus\\{X_{1}^{1},X_{1}^{0}\\}$, there exists
a distribution $LO^{(i)}(X)$ such that

$\mathcal{R}^{(i)}(X)=\frac{p}{2}\mathcal{R}^{(i)}(X_{1}^{0})+\frac{p}{2}\mathcal{R}^{(i)}(X_{1}^{1})+(1-p)LO^{(i)}(X).$

Then
$\mathcal{A}_{s}(\mathbf{X}_{0})\underset{(\epsilon,\delta)}{\simeq}\mathcal{A}_{s}(\mathbf{X}_{1}),$
where

$\epsilon\leq\ln\left(1+\frac{8\sqrt{\ln(4/\delta)}}{\sqrt{pN}}+\frac{8}{pN}\right).$

###### Proof.

The proof mirrors the proof of Lemma 3.3 in [FMT20] closely, replacing their
notation with ours. Observe that the DP assumption in Lemma 3.3 of [FMT20] is
not actually needed in the proof. ∎

######  Lemma F.4.

Let $\mathcal{R}:\mathcal{X}^{n}\to\mathcal{Z}$ be $(\epsilon,\delta)$
deletion group DP for groups of size $n$ with reference distribution $\rho$.
Then there exists a randomizer
$\mathcal{R}^{\prime}:\mathcal{X}^{n}\to\mathcal{Z}$ such that:
(i) $\mathcal{R}^{\prime}$ is $(\epsilon,0)$ deletion group DP for groups of
size $n$ with reference distribution $\rho$; and
(ii) $TV(\mathcal{R}(X),\mathcal{R}^{\prime}(X))\leq\delta.$
In particular, $\mathcal{R}^{\prime}$ is $(2\epsilon,(1+e^{\epsilon})\delta)$
group DP for groups of size $n$ (by $i$).

###### Proof.

The proof is nearly identical to the proof of Lemma 3.7 in [FMT20]. ∎

We also need the following stronger version of Lemma 3.7 from [FMT20]:

######  Lemma F.5.

If
$\mathcal{R}(X_{1}^{0})\underset{(\epsilon_{0},\delta_{0})}{\simeq}\mathcal{R}(X_{1}^{1}),$
then there exists a randomizer
$\mathcal{R}^{\prime}:\mathcal{X}^{n}\to\mathcal{Z}$ such that
$\mathcal{R}^{\prime}(X_{1}^{1})\underset{(\epsilon_{0},0)}{\simeq}\mathcal{R}(X_{1}^{0})$
and
$TV(\mathcal{R}^{\prime}(X_{1}^{1}),\mathcal{R}(X_{1}^{1}))\leq\delta_{0}.$

###### Proof.

The proof follows the same techniques as Lemma 3.7 in [FMT20], noting that the
weaker hypothesis in Lemma F.5 is sufficient for all the steps to go through
and that the assumption of $n=1$ in [FMT20] is not needed in the proof. ∎

######  Lemma F.6 ([DR14], Lemma 3.17).

Given random variables $P,Q,P^{\prime}$ and $Q^{\prime}$, if
$D_{e^{\epsilon}}(P^{\prime},Q^{\prime})\leq\delta$,
$TV(P,P^{\prime})\leq\delta^{\prime}$, and
$TV(Q,Q^{\prime})\leq\delta^{\prime}$, then
$D_{e^{\epsilon}}(P,Q)\leq\delta+(e^{\epsilon}+1)\delta^{\prime}$.

######  Lemma F.7 ([FMT20], Lemma 2.3).

Let $P$ and $Q$ be distributions satisfying $P=(1-q)P_{0}+qP_{1}$ and
$Q=(1-q)P_{0}+qQ_{1}$ for some $q\in[0,1]$. Then for any $\epsilon>0$, if
$\epsilon^{\prime}=\log(1+q(e^{\epsilon}-1)),$ then

$D_{e^{\epsilon^{\prime}}}(P||Q)\leq
q\max\\{D_{e^{\epsilon}}(P_{1}||P_{0}),D_{e^{\epsilon}}(P_{0}||Q_{1})\\}\leq
qD_{e^{\epsilon}}(P_{1}||Q_{1}).$

We are now ready to prove Theorem F.2:

###### Proof of Theorem F.2.

Let $\mathbf{X}_{0},\mathbf{X}_{1}\in\mathcal{X}^{n\times N}$ be adjacent (in
the CDP sense) distributed data sets (i.e.
$|\mathbf{X}_{0}\Delta\mathbf{X}_{1}|\leq 1$). Assume WLOG that
$\mathbf{X}_{0}=(X_{1}^{0},X_{2},\cdots,X_{N})$ and
$\mathbf{X}_{1}=(X_{1}^{1},X_{2},\cdots,X_{N}),$ where
$X_{1}^{0}=(x_{1,0},x_{1,2},\cdots,x_{1,n})\neq(x_{1,1},x_{1,2},\cdots,x_{1,n}).$
We can also assume WLOG that $X_{j}\notin\\{X_{1}^{0},X_{1}^{1}\\}$ for all
$j\in\\{2,\cdots,N\\}$ by re-defining $\mathcal{X}$ and
$\mathcal{R}^{(i)}_{r}$ if necessary.

Fix
$i\in[N],r\in[R],\mathbf{Z}=\mathbf{Z}_{1:r-1}=Z_{(1:r-1)}^{(1:N)}\in\mathcal{Z}^{(r-1)\times
N}$, denote $\mathcal{R}(X):=\mathcal{R}^{(i)}_{r}(\mathbf{Z},X)$ for
$X\in\mathcal{X}^{n},$ and
$\mathcal{A}_{s}(\mathbf{X}):=\mathcal{A}_{s}^{r}(\mathbf{Z}_{1:r-1},\mathbf{X}).$
Draw $\pi$ uniformly from the set of permutations of $[N]$. Now, since
$\mathcal{R}$ is $(\epsilon_{0},\delta_{0})$-DP,
$\mathcal{R}(X_{1}^{1})\underset{(\epsilon_{0}^{r},\delta_{0}^{r})}{\simeq}\mathcal{R}(X_{1}^{0})$,
so by Lemma F.5, there exists a local randomizer $\mathcal{R}^{\prime}$ such
that
$\mathcal{R}^{\prime}(X_{1}^{1})\underset{(\epsilon_{0}^{r},0)}{\simeq}\mathcal{R}(X_{1}^{0})$
and
$TV(\mathcal{R}^{\prime}(X_{1}^{1}),\mathcal{R}(X_{1}^{1}))\leq\delta_{0}^{r}.$

Hence, by Lemma F.1, there exist distributions $U(X_{1}^{0})$ and
$U(X_{1}^{1})$ such that

$\mathcal{R}(X_{1}^{0})=\frac{e^{\epsilon_{0}^{r}}}{e^{\epsilon_{0}^{r}}+1}U(X_{1}^{0})+\frac{1}{e^{\epsilon_{0}^{r}}+1}U(X_{1}^{1})$
(42)

and

$\mathcal{R}^{\prime}(X_{1}^{1})=\frac{1}{e^{\epsilon_{0}^{r}}+1}U(X_{1}^{0})+\frac{e^{\epsilon_{0}^{r}}}{e^{\epsilon_{0}^{r}}+1}U(X_{1}^{1}).$
(43)

Denote $\widetilde{\epsilon_{0}}:=n\epsilon_{0}^{r}$ and
$\widetilde{\delta_{0}}:=ne^{(n-1)\epsilon_{0}^{r}}\delta_{0}^{r}.$ By
convexity of hockey-stick divergence and the hypothesis that $\mathcal{R}$ is
$(\epsilon_{0}^{r},\delta_{0}^{r})$-DP (hence
$\mathcal{R}(X)\underset{(\widetilde{\epsilon_{0}},\widetilde{\delta_{0}})}{\simeq}\mathcal{R}(X_{1}^{0}),\mathcal{R}(X_{1}^{1})$
for all $X$ by Lemma F.2), we have
$\mathcal{R}(X)\underset{(\widetilde{\epsilon_{0}},\widetilde{\delta_{0}})}{\simeq}\frac{1}{2}(\mathcal{R}(X_{1}^{0})+\mathcal{R}(X_{1}^{1})):=\rho$
for all $X\in\mathcal{X}^{n}.$ That is, $\mathcal{R}$ is
$(\widetilde{\epsilon_{0}},\widetilde{\delta_{0}})$ deletion group DP for
groups of size $n$ with reference distribution $\rho.$ Thus, Lemma F.4 implies
that there exists a local randomizer $\mathcal{R}^{\prime\prime}$ such that
$\mathcal{R}^{\prime\prime}(X)$ and $\rho$ are $(\widetilde{\epsilon_{0}},0)$
indistinguishable and
$TV(\mathcal{R}^{\prime\prime}(X),\mathcal{R}(X))\leq\widetilde{\delta_{0}}$
for all $X.$ Then by the definition of $(\widetilde{\epsilon_{0}},0)$
indistinguishability, for all $X$ there exists a “left-over” distribution
$LO(X)$ such that
$\mathcal{R}^{\prime\prime}(X)=\frac{1}{e^{\widetilde{\epsilon_{0}}}}\rho+(1-1/e^{\widetilde{\epsilon_{0}}})LO(X)=\frac{1}{2e^{\widetilde{\epsilon_{0}}}}(\mathcal{R}(X_{1}^{0})+\mathcal{R}(X_{1}^{1}))+(1-1/e^{\widetilde{\epsilon_{0}}})LO(X).$

Now, define a randomizer $\mathcal{L}$ by
$\mathcal{L}(X_{1}^{0}):=\mathcal{R}(X_{1}^{0}),~{}\mathcal{L}(X_{1}^{1}):=\mathcal{R}^{\prime}(X_{1}^{1}),$
and

$\displaystyle\mathcal{L}(X)$
$\displaystyle:=\frac{1}{2e^{\widetilde{\epsilon_{0}}}}\mathcal{R}(X_{1}^{0})+\frac{1}{2e^{\widetilde{\epsilon_{0}}}}\mathcal{R}^{\prime}(X_{1}^{1})+(1-1/e^{\widetilde{\epsilon_{0}}})LO(X)$
$\displaystyle=\frac{1}{2e^{\widetilde{\epsilon_{0}}}}U(X_{1}^{0})+\frac{1}{2e^{\widetilde{\epsilon_{0}}}}U(X_{1}^{1})+(1-1/e^{\widetilde{\epsilon_{0}}})LO(X)$
(44)

for all $X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}.$ (The equality
follows from 42 and 43.) Note that
$TV(\mathcal{R}(X_{1}^{0}),\mathcal{L}(X_{1}^{0}))=0,~{}TV(\mathcal{R}(X_{1}^{1}),\mathcal{L}(X_{1}^{1}))\leq\delta_{0}^{r},$
and for all $X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}$,
$TV(\mathcal{R}(X),\mathcal{L}(X))\leq
TV(\mathcal{R}(X),\mathcal{R}^{\prime\prime}(X))+TV(\mathcal{R}^{\prime\prime}(X),\mathcal{L}(X))\leq\widetilde{\delta_{0}}+\frac{1}{2e^{\widetilde{\epsilon_{0}}}}TV(\mathcal{R}^{\prime}(X_{1}^{1}),\mathcal{R}(X_{1}^{1}))=(ne^{(n-1)\epsilon_{0}^{r}}+\frac{1}{2e^{n\epsilon_{0}^{r}}})\delta_{0}^{r}\leq(2ne^{(n-1)\epsilon_{0}^{r}})\delta_{0}^{r}=2\widetilde{\delta_{0}}.$

Keeping $r$ fixed (omitting $r$ scripts everywhere), for any $i\in[N]$ and
$\mathbf{Z}:=\mathbf{Z}_{1:r-1}\in\mathcal{Z}^{(r-1)\times N},$ let
$\mathcal{L}^{(i)}(\mathbf{Z},\cdot)$, $U^{(i)}(\mathbf{Z},\cdot)$, and
$LO^{(i)}(\mathbf{Z},\cdot)$ denote the randomizers resulting from the process
described above. Let $\mathcal{A}_{\mathcal{L}}:\mathcal{X}^{n\times
N}\to\mathcal{Z}^{N}$ be defined exactly the same way as
$\mathcal{A}_{s}^{r}:=\mathcal{A}_{s}$ (same $\pi$) but with the randomizers
$\mathcal{R}^{(i)}$ replaced by $\mathcal{L}^{(i)}$. Since $\mathcal{A}_{s}$
applies each randomizer $\mathcal{R}^{(i)}$ exactly once and
$\mathcal{R}^{(1)}(\mathbf{Z},X_{\pi(1)},\cdots\mathcal{R}^{(N)}(\mathbf{Z},X_{\pi(N)})$
are independent (conditional on $\mathbf{Z}=\mathbf{Z}_{1:r-1}$) 171717This
follows from the assumption given in the lead up to Definition 2 that
$\mathcal{R}^{(i)}(\mathbf{Z}_{1:r-1},X)$ is conditionally independent of
$X^{\prime}$ given $\mathbf{Z}_{1:r-1}$ for all $\mathbf{Z}_{1:r-1}$ and
$X\neq X^{\prime}$., we have
$TV(\mathcal{A}_{s}(\mathbf{X}_{0}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})\leq
N(2ne^{(n-1)\epsilon_{0}^{r}})\delta_{0}^{r}$ and
$TV(\mathcal{A}_{s}(\mathbf{X}_{1}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})\leq
N(2ne^{(n-1)\epsilon_{0}^{r}})\delta_{0}^{r}$ (see [DH12]). Now we claim that
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$ and
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$ are $(\epsilon^{r},\delta^{r})$
indistinguishable for any $\delta^{r}\geq 2e^{-Ne^{-n\epsilon_{0}^{r}}/16}.$
Observe that this claim implies that $\mathcal{A}_{s}(\mathbf{X}_{0})$ and
$\mathcal{A}_{s}(\mathbf{X}_{1})$ are $(\epsilon^{r},\widetilde{\delta}^{r})$
indistinguishable by Lemma F.6 (with
$P^{\prime}:=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0}),Q^{\prime}:=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1}),P:=\mathcal{A}_{s}(\mathbf{X}_{0}),Q:=\mathcal{A}_{s}(\mathbf{X}_{1})$.)
Therefore, it remains to prove the claim, i.e. to show that
$D_{e^{\epsilon^{r}}}(\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0}),\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})\leq\delta^{r}$
for any $\delta^{r}\geq 2e^{-Ne^{-n\epsilon_{0}^{r}}/16}.$

Now, define
$\mathcal{L}_{U}^{(i)}(\mathbf{Z},X):=\begin{cases}U^{(i)}(\mathbf{Z},X_{1}^{0})&\mbox{if}~{}X=X_{1}^{0}\\\
U^{(i)}(\mathbf{Z},X_{1}^{1})&\mbox{if}~{}X=X_{1}^{1}\\\
\mathcal{L}^{(i)}(\mathbf{Z},X)&\mbox{otherwise}.\end{cases}.$ For any inputs
$\mathbf{Z},\mathbf{X}$, let $\mathcal{A}_{U}(\mathbf{Z},\mathbf{X})$ be
defined exactly the same as $\mathcal{A}_{s}(\mathbf{Z},\mathbf{X})$ (same
$\pi$) but with the randomizers $\mathcal{R}^{(i)}$ replaced by
$\mathcal{L}_{U}^{(i)}$. Then by 42 and 43,

$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})=\frac{e^{\epsilon_{0}^{r}}}{e^{\epsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{0})+\frac{1}{e^{\epsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{1})~{}\text{and}~{}\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})=\frac{1}{e^{\epsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{0})+\frac{e^{\epsilon_{0}^{r}}}{e^{\epsilon_{0}^{r}}+1}\mathcal{A}_{U}(\mathbf{X}_{1}).$
(45)

Then by Section F.3, for any
$X\in\mathcal{X}^{n}\setminus\\{X_{1}^{0},X_{1}^{1}\\}$ and any
$\mathbf{Z}=\mathbf{Z}_{1:r-1}\in\mathcal{Z}^{(r-1)\times N},$ we have
$\mathcal{L}_{U}^{(i)}(\mathbf{Z},X)=\frac{1}{2e^{\widetilde{\epsilon_{0}}}}\mathcal{L}^{(i)}_{U}(\mathbf{Z},X_{1}^{0})+\frac{1}{2e^{\widetilde{\epsilon_{0}}}}\mathcal{L}^{(i)}_{U}(\mathbf{Z},X_{1}^{1})+(1-e^{-\widetilde{\epsilon_{0}}})LO^{(i)}(\mathbf{Z},X).$
Hence, Lemma F.3 (with
$p:=e^{-\widetilde{\epsilon_{0}}}=e^{-n\epsilon_{0}^{r}}$) implies that
$\mathcal{A}_{U}(\mathbf{X}_{0})$ and $\mathcal{A}_{U}(\mathbf{X}_{1})$) are

$\left(\log\left(1+\frac{8\sqrt{e^{\widetilde{\epsilon_{0}}}\ln(4/\delta^{r})}}{\sqrt{N}}+\frac{8e^{\widetilde{\epsilon_{0}}}}{N}\right),\delta^{r}\right)$

indistinguishable for any $\delta^{r}\geq 2e^{-Ne^{-n\epsilon_{0}^{r}}/16}.$
Applying Lemma F.7 with $P:=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$,
$Q=\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$,
$q=\frac{e^{\epsilon_{0}^{r}}-1}{e^{\epsilon_{0}^{r}}+1}$,
$P_{1}=\mathcal{A}_{U}(\mathbf{X}_{0})$,
$Q_{1}=\mathcal{A}_{U}(\mathbf{X}_{1})$, and $P_{0}=\frac{1}{2}(P_{1}+Q_{1})$
yields that $\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{0})$ and
$\mathcal{A}_{\mathcal{L}}(\mathbf{X}_{1})$ are $(\epsilon^{r},\delta^{r})$
indistinguishable, as desired. This proves the claim and hence (by Lemma F.6,
as described earlier) the theorem. ∎

######  Remark F.2.

Notice that if $\mathcal{A}$ is sequentially interactive, then the proof of
Theorem F.2 above almost immediately implies the sequentially interactive part
of Theorem F.1. Essentially, just change notation: replace
$\mathbf{Z}_{1:r-1}$ by $Z^{(1:i-1)}$, the collection of (single) reports sent
by the first $i-1$ clients; note that $\epsilon_{0}^{r}=\epsilon_{0}$,
$\delta_{0}^{r}=\delta_{0}$; and view the $N$ reports as being sent in order
instead of simultaneously. Alternatively, plug our techniques for $n>1$ into
the proof of Theorem 3.8 in [FMT20], which is for sequentially interactive
algorithms.

Step 2: Combine Theorem F.1 with the following CDP SCO lower bounds which
follow from [BST14, BFTT19] and the non-private SCO lower bounds [NY83,
ABRW12] :

######  Theorem F.3.

[BFTT19, BST14] Let $\mu,D,\epsilon>0$, $L\geq\mu D$, and $\delta=o(1/nN).$
Consider
$\mathcal{X}:=\\{\frac{-D}{\sqrt{d}},\frac{D}{\sqrt{d}}\\}^{d}\subset\mathbb{R}^{d}$
and $\mathcal{W}:=B_{2}(0,D)\subset\mathbb{R}^{d}$. Let
$\mathcal{A}:\mathcal{X}^{nN}\to\mathcal{W}$ be any $(\epsilon,\delta)$-CDP
algorithm. Then:
1\. There exists a ($\mu=0$) convex, linear ($\beta$-smooth for any $\beta$),
$L$-Lipschitz loss $f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ and a
distribution $\mathcal{D}$ on $\mathcal{X}$ such that if
$\mathbf{X}\sim\mathcal{D}^{nN}$, then the expected excess loss of
$\mathcal{A}$ is lower bounded as

$\mathbb{E}F(\mathcal{A}(\mathbf{X}))-F^{*}=\widetilde{\Omega}\left(\frac{\phi
D}{\sqrt{Nn}}+LD\min\left\\{1,\frac{\sqrt{d}}{\epsilon nN}\right\\}\right).$

2\. For $L\approx\mu D$, there exists a $\mu$-strongly convex and smooth,
$L$-Lipschitz loss $f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ and a
distribution $\mathcal{D}$ on $\mathcal{X}$ such that if
$\mathbf{X}\sim\mathcal{D}^{nN}$, then the expected excess loss of
$\mathcal{A}$ is lower bounded as

$\mathbb{E}F(\mathcal{A}(\mathbf{X}))-F^{*}=\widetilde{\Omega}\left(\frac{\phi^{2}}{\mu
Nn}+\frac{L^{2}}{\mu}\min\left\\{1,\frac{d}{\epsilon^{2}n^{2}N^{2}}\right\\}\right).$

For general $L,\mu,D$, the above strongly convex lower bound holds with the
factor $\frac{L^{2}}{\mu}$ replaced by $LD$.

Namely, if $\mathcal{A}$ is $(\epsilon_{0},\delta_{0})$-LDP, then (under the
hypotheses of Theorem 3.1) $\mathcal{A}_{s}$ is $(\epsilon,\delta)$-CDP for
$\epsilon=\widetilde{O}(\epsilon_{0}/\sqrt{N})$, so Theorem F.3 implies that
the excess loss of $\mathcal{A}_{s}$ is lower bounded as in Theorem F.3 with
$\epsilon$ replaced by $\epsilon_{0}/\sqrt{N}$.

Step 3:  We simply observe that when the expectation is taken over the
randomness in sampling $\mathbf{X}\sim\mathcal{D}^{n\times N}$, the expected
excess population loss of $\mathcal{A}_{s}$ is identical to that of
$\mathcal{A}$ since $X_{i}$ and $X_{\pi(i)}$ have the same distribution for
all $i,\pi$ by the i.i.d. assumption. This completes the proof of Theorem 3.1.

###  F.4 Lower bounds for LDP Federated ERM

Formally, define the algorithm class
$\mathbb{B}_{(\epsilon_{0},\delta_{0})}:=\mathbb{B}$ to consist of those
(sequentially interactive or compositional, LDP) algorithms
$\mathcal{A}\in\mathbb{A}_{(\epsilon_{0},\delta_{0})}=\mathbb{A}$ such that
for any $\mathbf{X}\in\mathbb{X},~{}f\in\mathcal{F}_{L,D}$, the expected
empirical loss of the shuffled algorithm $\mathcal{A}_{s}$ derived from
$\mathcal{A}$ is upper bounded by the expected loss of $\mathcal{A}$:
$\mathbb{E}_{\mathcal{A},\\{\pi_{r}\\}_{r}}\widehat{F}(\mathcal{A}_{s}(\mathbf{X}))\lesssim\mathbb{E}_{\mathcal{A}}\widehat{F}(\mathcal{A}(\mathbf{X})).$
Here $\mathcal{A}_{s}$ denotes the algorithm that applies the randomizer
$\mathcal{R}^{(i)}_{r}$ to $X_{\pi_{r}(i)}$ for all $i,r$, but otherwise
behaves exactly like $\mathcal{A}$. This is not a very constructive definition
but we will describe examples of algorithms in $\mathbb{B}$. $\mathbb{B}$
includes all compositional or sequentially interactive LDP algorithms that are
symmetric with respect to each of the $N$ clients, meaning that the
aggregation functions $g_{r}$ 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 clients
$i\in[N]$. ($\mathcal{R}^{(i)}_{r}$ can still change with $r$ though.) For
example, Algorithm 1 and Algorithm 2 are both in $\mathbb{B}$. This is because
the aggregation functions used in each round are simple averages of the $M=N$
noisy gradients received from all clients (and they are compositional) and the
randomizers in round $r$ are identical when
$\epsilon_{i}=\epsilon_{0},\delta_{i}=\delta_{0},n_{i}=n,\mathcal{X}_{i}=\mathcal{X}$:
each adds the same gaussian noise to the stochastic gradients. $\mathbb{B}$
also includes sequentially interactive algorithms that choose the order in
which clients are processed uniformly at random. This is because 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.

######  Theorem F.4.

Let
$n,d,N,R\in\mathbb{N},~{}\epsilon_{0}\in(0,\sqrt{N}],~{}\delta_{0}\in(0,1)$
and $\mathcal{A}\in\mathbb{B}_{(\epsilon_{0},\delta_{0})}$ such that in every
round $r\in[R]$, 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],~{}\mathbf{Z}_{(1:r-1)}\in\mathcal{Z}^{r-1\times N}$, with
$\epsilon_{0}^{r}\leq\frac{1}{n}$, and
$\delta_{0}^{r}\geq\frac{2e^{-N/16}}{Nn}$. Assume moreover that
$\sum_{r}\delta_{0}^{r}=o(1/n^{2}N^{2})$ if $\mathcal{A}$ is compositional; if
$\mathcal{A}$ is sequentially interactive, assume instead that
$\delta_{0}=o(1/n^{2}N^{2}).$ Then there exists a (linear, hence
$\beta$-smooth $\forall\beta\geq 0$) loss function $f\in\mathcal{F}_{L,D}$ and
a database $\mathbf{X}\in\mathcal{X}^{nN}$ for some $\mathcal{X}$ such that
the excess empirical loss of $\mathcal{A}$ is lower bounded as:

$\mathbb{E}\widehat{F}(\mathcal{A}(\mathbf{X}))-\widehat{F}^{*}=\widetilde{\Omega}\left(LD\min\left\\{1,\frac{\sqrt{d}}{\epsilon_{0}n\sqrt{N}}\right\\}\right).$

Furthermore, there exists another ($\mu$-smooth) $f\in\mathcal{G}_{\mu,L,D}$
such that

$\mathbb{E}\widehat{F}(\mathcal{A}(\mathbf{X}))-\widehat{F}^{*}=\widetilde{\Omega}\left(LD\min\left\\{1,\frac{d}{\epsilon_{0}^{2}n^{2}N}\right\\}\right).$

Here, the $\widetilde{\Omega}$ notation hides logarithmic factors depending on
$\delta_{0}^{r},~{}n$, and $N$.

###### Proof.

Step 1 is identical to Step 1 of the proof of Theorem 3.1. Step 2 is very
similar to Step 2 in the proof of Theorem 3.1, but now we use Theorem F.5
(below) instead of Theorem F.3 to lower bound the excess empirical loss of
$\mathcal{A}_{s}$. Step 3: Finally, the definition of $\mathbb{B}$ implies
that the excess risk of $\mathcal{A}$ is the same as that of
$\mathcal{A}_{s}$, hence the lower bound also applies to $\mathcal{A}$. ∎

######  Theorem F.5.

[BST14] Let $\mu,D,\epsilon>0$, $L\geq\mu D$, and $\delta=o(1/nN).$ Consider
$\mathcal{X}:=\\{\frac{-D}{\sqrt{d}},\frac{D}{\sqrt{d}}\\}^{d}\subset\mathbb{R}^{d}$
and $\mathcal{W}:=B_{2}(0,D)\subset\mathbb{R}^{d}$. Let
$\mathcal{A}:\mathcal{X}^{nN}\to\mathcal{W}$ be any $(\epsilon,\delta)$-CDP
algorithm. Then:
1\. There exists a ($\mu=0$) convex, linear ($\beta$-smooth for any $\beta$),
$L$-Lipschitz loss $f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ and a
database $\mathbf{X}\in\mathcal{X}^{nN}$ such that the expected empirical loss
of $\mathcal{A}$ is lower bounded as

$\mathbb{E}\widehat{F}(\mathcal{A}(\mathbf{X}))-\widehat{F}^{*}=\widetilde{\Omega}\left(LD\min\left\\{1,\frac{\sqrt{d}}{\epsilon
nN}\right\\}\right).$

2\. There exists a $\mu$-strongly convex, $\mu$-smooth, $L$-Lipschitz loss
$f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ and a database
$\mathbf{X}\in\mathcal{X}^{nN}$ such that the expected empirical loss of
$\mathcal{A}$ is lower bounded as

$\mathbb{E}\widehat{F}(\mathcal{A}(\mathbf{X}))-\widehat{F}^{*}=\widetilde{\Omega}\left(LD\min\left\\{1,\frac{d}{\epsilon^{2}n^{2}N^{2}}\right\\}\right).$

##  Appendix G  Proof of Theorem 4.1

For this result, we will just prove the stated version with balanced data and
same privacy needs across clients, and non-random $M_{r}=M\leq N$ (same setup
as [GDD+21] considered for ERM).

###  G.1 Tight Excess Risk Bounds for Cross-Device FL with Algorithms
Satisfying Both LDP and User-Level DP

We explain how our LDP excess risk bounds also imply tight excess risk bounds
for cross-device FL with algorithms that satisfy both LDP and user-level DP
simultaneously. Given $(\epsilon,\delta)$, let
$\epsilon_{0}=\epsilon/n,~{}\delta_{0}=\delta/n$ and apply Theorem 2.1 and
group privacy (see Appendix D) to obtain upper bounds for the hybrid LDP/user-
level DP notion. Regarding lower bounds: note that the semantics of the hybrid
DP notion are essentially identical to classical LDP, except that individual
“records/items” are now thought of as datasets of size $n$. Thus, letting
$n=1$ in our lower bounds (we think of each client as having just one “record”
even though that record is really a dataset), we obtain tight excess risk
bounds. Note that these bounds resemble the bounds for classical LDP [DJW13],
scaling with $N$, but not with $n$.

Theorem 4.1 Let $f:\mathcal{W}\times\mathcal{X}\to\mathbb{R}^{d}$ be
$\beta$-smooth, $L$-Lipschitz, and $\mu$-strongly convex (with $\mu=0$ for
convex case). Assume $\epsilon\leq\ln(2/\delta),~{}\delta\in(0,1),$ and $M\geq
16\ln(18RM^{2}/N\delta)$ for $R$ specified below. Then, there is a constant
$C>0$ such that setting
$\sigma_{i}^{2}:=\frac{CL^{2}RM\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}{n^{2}N^{2}\epsilon^{2}}$
ensures that the shuffled version of Algorithm 1 is $(\epsilon,\delta)$-CDP.
Moreover, there exist $\eta_{r}=\eta$ and $\\{\gamma_{r}\\}_{r=0}^{R-1}$ such
that the shuffled version of Algorithm 1 achieves the following upper bounds
on excess loss:
1\. (Convex) Setting
$R:=\max\left(\frac{n^{2}N^{2}\epsilon^{2}}{M},\frac{N}{M},~{}\min\left\\{n,\frac{\epsilon^{2}n^{2}N^{2}}{dM}\right\\},\frac{\beta
D}{L}\min\left\\{\sqrt{nM},\frac{\epsilon nN}{\sqrt{d}}\right\\}\right)$
yields

$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})=\mathcal{O}\left(LD\left(\frac{1}{\sqrt{nM}}+\frac{\sqrt{d\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}}{\epsilon
nN}\right)\right).$ (46)

2\. (Strongly convex)
$R:=\max\left(\frac{n^{2}N^{2}\epsilon^{2}}{M},\frac{N}{M},\frac{8\beta}{\mu}\ln\left(\frac{\beta
D^{2}\mu\epsilon^{2}n^{2}N^{2}}{dL^{2}}\right),\min\left\\{n,\frac{\epsilon^{2}n^{2}N^{2}}{dM}\right\\}\right)$
yields

$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\mu}\left(\frac{1}{nM}+\frac{d\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}{\epsilon^{2}n^{2}N^{2}}\right)\right).$
(47)

###### Proof of Theorem 4.1.

We fix $K=1$ for simplicity, but note that $K>1$ can also be used (see Lemma 3
in [GDD+21]).

Privacy: The privacy proof is similar to the proof of Theorem 1 in [GDD+21],
except we replace their use of [BBGN19] (for pure DP randomizers) with Theorem
3.8 of [FMT20] for our approximate DP randomizer (Gaussian mechanism). Observe
that in each round $r$, the model updates of the shuffled algorithm
$\mathcal{A}_{s}^{r}$ can be viewed as post-processing of the composition
$\mathcal{M}_{r}(\mathbf{X})=\mathcal{S}_{M}\circ
samp_{M,N}(Z^{(1)}_{r},\cdots,Z^{(N)}_{r}),$ where $\mathcal{S}_{M}$ uniformly
randomly shuffles the $M$ received reports, $samp_{M,N}$ is the mechanism that
chooses $M$ reports uniformly at random from $N$, and
$Z^{(i)}_{r}=samp_{1,n}(\widehat{\mathcal{R}}_{r}(x_{i,1}),\cdots\widehat{\mathcal{R}}_{r}(x_{i,n}))$,
where $\widehat{\mathcal{R}}_{r}(x):=\nabla f(w_{r},x)+u$ and
$u\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d})$. Recall (Theorem A.1 in [DR14])
that
$\sigma^{2}=\frac{8L^{2}\ln(2/\widehat{\delta_{0}})}{\widehat{\epsilon_{0}}^{2}}$
suffices to ensure that $\widehat{\mathcal{R}}_{r}$ is
$(\widehat{\epsilon_{0}},\widehat{\delta_{0}})$-DP if
$\widehat{\epsilon_{0}}\leq 1$. Now note that
$\mathcal{M}_{r}(\mathbf{X})=\widetilde{\mathcal{R}}^{M}(\mathcal{S}_{M}\circ
samp_{M,N}(X_{1},\cdots X_{N})$, where
$\widetilde{\mathcal{R}}:\mathcal{X}^{n}\to\mathcal{Z}$ is given by $X\mapsto
samp_{1,n}(\widehat{\mathcal{R}}(x_{1}),\cdots,\widehat{\mathcal{R}}(x_{n}))$
and $\widetilde{\mathcal{R}}^{M}:\mathcal{X}^{nM}\to\mathcal{Z}^{M}$ is given
by
$\mathbf{X}\mapsto(\widetilde{\mathcal{R}}(X_{1}),\cdots\widetilde{\mathcal{R}}(X_{M}))$
for any $\mathbf{X}=(X_{1},\cdots,X_{M})\in\mathcal{X}^{nM}$. This is because
we are applying the same randomizer (same additive Gaussian noise) across
clients and the operators $\mathcal{S}_{M}$ and $\widetilde{\mathcal{R}}^{M}$
commute. (Also, applying a randomizer to all $N$ clients and then randomly
choosing $M$ reports is equivalent to randomly choosing $M$ clients and then
applying the same randomizer to all $M$ of these clients.) Therefore,
conditional on the random subsampling of $M$ out of $N$ clients (denoted
$(X_{1},\cdots,X_{M})$ for convenience), Theorem 3.8 in [FMT20] implies that
$(\widehat{\mathcal{R}}(x_{\pi(1),1}),\cdots,\widehat{\mathcal{R}}(x_{\pi(1),n}),\cdots,\cdots,\widehat{\mathcal{R}}(x_{\pi(M),1}),\cdots,\widehat{\mathcal{R}}(x_{\pi(M),n}))$
is $(\widehat{\epsilon},\widehat{\delta})$-CDP, where
$\widehat{\epsilon}=\mathcal{O}\left(\frac{\widehat{\epsilon_{0}}\sqrt{\ln(1/M\widehat{\delta_{0}})}}{\sqrt{M}}\right)$
and $\widehat{\delta}=9M\widehat{\delta_{0}}$, provided
$\widehat{\epsilon_{0}}\leq 1$ and $M\geq 16\ln(2/\widehat{\delta_{0}})$
(which we will see is satisfied by our assumption on $M$). Next, privacy
amplification by subsampling (see [Ull17] and Lemma 3 in [GDD+21]) clients and
local samples implies that $\mathcal{M}_{r}$ is
$(\epsilon^{r},\delta^{r})$-CDP, where
$\epsilon^{r}=\frac{2\widehat{\epsilon}M}{nN}=\mathcal{O}\left(\widehat{\epsilon_{0}}\frac{\sqrt{M\ln(1/M\widehat{\delta_{0}})}}{nN}\right)$
and
$\delta^{r}=\frac{M}{nN}\widehat{\delta}=\frac{9M^{2}}{nN}\widehat{\delta_{0}}$.
Finally, by the advanced composition theorem (Theorem 3.20 in [DR14]), to
ensure $\mathcal{A}_{s}$ is $(\epsilon,\delta)$-CDP, it suffices to make each
round
$(\epsilon^{r}:=\frac{\epsilon}{2\sqrt{2R\ln(1/\delta)}},\delta^{r}:=\delta/2R)$-CDP.
Using the two equations to solve for
$\widehat{\epsilon_{0}}=\frac{CnN\epsilon}{\sqrt{R\ln(1/\delta)\ln(RM/nN\delta)M}}$
for some $C>0$ and $\widehat{\delta_{0}}=\frac{nN\delta}{18RM^{2}}$, we see
that
$\sigma^{2}=\mathcal{O}\left(\frac{L^{2}\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta))RM}{n^{2}N^{2}\epsilon^{2}}\right)$
ensures that $\mathcal{A}_{s}$ is $(\epsilon,\delta)$-CDP, i.e. that
$\mathcal{A}$ is $(\epsilon,\delta)$-SDP. Note that our choices of $R$ in the
theorem (specifically $R\geq N/M$ and $R\geq\frac{n^{2}N^{2}\epsilon^{2}}{M}$)
ensure that $\widehat{\delta_{0}},\delta\leq 1$ and
$\widehat{\epsilon_{0}}\lesssim 1$, so that Theorem 3.8 in [FMT20] indeed
gives us the amplification by shuffling result used above.

Excess risk: The proof is very similar to the proof of Theorem 2.1, except
$\sigma^{2}$ is now smaller.
Convex case: Set $\gamma_{r}=\gamma=1/R$ for all $r$. Now 19, Lemma E.2, and
Lemma E.1 together imply for any $\eta\leq 1/4\beta$ that

$\displaystyle\mathbb{E}F(\widehat{w}_{R})-F(w^{*})$
$\displaystyle\lesssim\frac{L^{2}R\eta}{nM}+\frac{D^{2}}{\eta
R}+\eta\left(L^{2}/M+\frac{d\sigma^{2}}{M}\right).$

Now plugging in
$\eta:=\min\left\\{1/4\beta,\frac{D\sqrt{M}}{LR}\min\left\\{\sqrt{n},\frac{\epsilon
nN}{\sqrt{dM\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}}\right\\}\right\\}$
yields

$\displaystyle\mathbb{E}F(\widehat{w}_{R})-F(w^{*})$ $\displaystyle\lesssim
LD\left(\max\left\\{\frac{1}{\sqrt{nM}},\frac{\sqrt{d\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}}{\epsilon
nN}\right\\}\right)$
$\displaystyle+\frac{LD}{R\sqrt{M}}\min\left\\{\sqrt{n},\frac{\epsilon
nN}{\sqrt{dM\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}}\right\\}+\frac{\beta
D^{2}}{R}.$

Then one can verify that plugging in the prescribed $R$ yields the stated
excess population loss bound.
$\mu$-strongly convex case: Let $\mathbf{X}\in\mathcal{X}^{nN}$ and denote the
empirical risk minimizer by $\widetilde{w}$. Then for any $\eta_{t}\leq
1/4\beta$, by 16 and the i.i.d assumption (so $\Upsilon^{2}=0$), we have (for
all $t$)

$\mathbb{E}\|w_{t+1}-\widetilde{w}\|^{2}\leq(1-\mu\eta_{t})\mathbb{E}\|w_{t}-\widetilde{w}\|^{2}-\eta_{t}(\mathbb{E}\widehat{F}(w_{t})-\widehat{F}^{*})+2\eta_{t}^{2}\left(\frac{4L^{2}}{M}+\frac{d\sigma^{2}}{2M}\right).$

Then by Lemma E.9 with $a=\mu$, $b=1$,
$c=2\left(\frac{4L^{2}}{M}+\frac{dCL^{2}R\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}{\epsilon^{2}n^{2}N^{2}}\right)$,
$g=4\beta$, and $T=R$, there exists a constant stepsize $\widetilde{\eta}$ and
averaging weights $\gamma_{r}$ such that

$\mathbb{E}\widehat{F}(\widehat{w}_{R})-\widehat{F}(w^{*})=\widetilde{\mathcal{O}}\left(\beta
D^{2}\exp\left(\frac{-\mu
R}{4\beta}\right)+\frac{L^{2}}{\mu}\left(\frac{1}{MR}+\frac{d\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}{\epsilon^{2}n^{2}N^{2}}\right)\right)$

by Jensen’s inequality. (See Lemma E.9 for the explicit $\widetilde{\eta}$ and
$\gamma_{r}$.) Hence taking $\eta=\min\\{1/4\beta,\widetilde{\eta}\\}$ and
applying Lemma E.1 and Lemma E.2 yields

$\mathbb{E}F(\widehat{w}_{R})-F(w^{*})=\widetilde{\mathcal{O}}\left(\beta
D^{2}\exp\left(\frac{-\mu
R}{4\beta}\right)+\frac{L^{2}}{\mu}\left(\frac{1}{MR}+\frac{d\ln(RM^{2}/N\delta)\ln(R/\delta)\ln(1/\delta)}{\epsilon^{2}n^{2}N^{2}}\right)+\frac{L^{2}}{\mu
Mn}\right).$

Then one verifies that the prescribed $R$ is large enough to achieve the
stated excess population loss bound. ∎

##  Appendix H Experimental Details and Additional Results

Python scripts for the experiments are available at:
https://github.com/lowya/Locally-Differentially-Private-Federated-Learning.

###  H.1 Logistic Regression with MNIST

The data set can be downloaded from http://yann.lecun.com/exdb/mnist. Our code
does this for you automatically.

Experimental setup: To divide the data into $N=25$ clients and for
preprocessing, we borrow code from [WPS20b], which can be downloaded from:
https://papers.nips.cc/paper/2020/hash/45713f6ff2041d3fdfae927b82488db8-Abstract.html.
It is available under a Creative Commons Attribution-Share Alike 3.0 license.
There are $n_{i}=n=8673$ training and $2168$ test examples per client; to
expedite training, we use only $1/7$ of the MNIST samples ($n=1238$ training
examples per client). We fix $\delta_{i}=\delta=1/n^{2}$ and test
$\epsilon\in\\{0.75,1.5,3,6,12,18\\}.$ The maximum $\upsilon_{*}^{2}$ is about
$0.17$ for this problem (corresponding to each client having disjoint local
data sets/pairs of digits).

Preprocessing: We used PCA to reduce the dimensionality to $d=50.$ We used an
$80/20$ train/test split for all clients. To improve numerical stability, we
clipped the input $\langle w,x\rangle$ (i.e. projected it onto $[-15,15]$)
before feeding into logistic loss.

Hyperparameter tuning: For each algorithm and each setting of
$\epsilon,R,K,\upsilon^{2}_{*}$, we swept through a range of constant
stepsizes and ran 3 trials to find the (approximately) optimal stepsize for
that particular algorithm and experiment. We then used the corresponding
$w_{R}$ (averaged over the 3 runs) to compute test error. For (LDP) MB-SGD,
the stepsize grid consisted of 10 evenly spaced points between $e^{-6}$ and
$1.$ For (LDP) Local SGD, the stepsizes were between $e^{-8}$ and $e^{-1}.$ We
repeated this entire process $20$ times for fresh train/test splits of the
data and reported the average test error in our plots.

Choice of $\sigma^{2}$ and $K$: We used smaller noise (compared to the
theoretical portion of the paper) to get better utility (at the cost of larger
$K$/larger computational cost, which is needed for privacy):
$\sigma_{i}^{2}=\sigma^{2}=\frac{8L^{2}\ln(1/\delta)R}{n^{2}\epsilon^{2}},$
which provides LDP by Theorem 1 of [ACG+16] if
$K=\frac{n\sqrt{\epsilon}}{2\sqrt{R}}$ (c.f. Theorem 3.1 in [BFTT19]). Here
$L=2\max_{x\in X}\|x\|$ is an upper bound on the Lipschitz parameter of the
logistic loss and was computed directly from the training data.

To estimate $\upsilon^{2}_{*},$ (defined in Section E.1) we followed the
procedure used in [WPS20b], using Newton’s method to compute $w^{*}$ and then
averaging $\|\nabla\widehat{F}_{i}(w^{*})\|^{2}$ over all $i\in[N].$

Additional experimental result for homogeneous client data: In Fig. 5, we
present an additional experimental result for when data is i.i.d./homogeneous
(i.e. we shuffle all digit pairings across the 25 clients) and $M=12$. We see
that in the homogeneous case, (LDP) MB-SGD and (LDP) Local SGD perform almost
identically, except in the high privacy regime $\epsilon\leq 1.5$ where LDP
MB-SGD outperforms LDP Local SGD. This is consistent with the results of
[WPS20b] for large $K$. In Fig. 6, we show an additional experiment for
heterogeneous clients with $M=18$ available to communicate in each round. The
results are qualitatively similar to the results presented in the main body
for MNIST with heterogeneous clients and $M=25,12$.

Figure 5:  Test error vs. $\epsilon$ for binary logistic regression on MNIST
with i.i.d. (homogeneous) clients. $\delta=1/n^{2}$. We show 90% error bars
over the 20 trials (train/test splits).  Figure 6:  Test error vs. $\epsilon$
for binary logistic regression on MNIST with heterogeneous clients.
$\delta=1/n^{2}$. We show 90% error bars over the 20 trials (train/test
splits).

Limitations of Experiments: It is important to note that pre-processing and
hyperparameter tuning (and estimation of $L$) were not done in an LDP manner,
since we did not want to detract focus from evaluation of LDP FL
algorithms.181818See [ACG+16, LT19, PS21] and the references therein for
discussion of DP PCA and DP hyperparameter tuning. As a consequence, the
overall privacy loss for the entire experimental process is higher than the
$\epsilon$ indicated in the plots, which solely reflects the privacy loss from
running the FL algorithms with fixed hyperparameters and (pre-processed) data.
Similar remarks apply for the linear regression experiments (see Section H.2).

###  H.2 Linear Regression with Health Insurance Data

Data set: The data (https://www.kaggle.com/mirichoi0218/insurance), which is
available under an Open Database license, consists of $\widetilde{N}=1338$
observations. The target variable $y$ is medical charges. There are $d-1=6$
features: age, sex, BMI, number of children, smoker, and geographic region.

Experimental setup: For a given $N,$ we grouped data into $N$ (almost
balanced) clients by sorting $y$ in ascending order and then dividing into $N$
groups, the first $N-1$ of size $\lceil 1338/N\rceil$ and the remaining points
in the last client. For each $N,$ we ran experiments with $R=35$. We ran $20$
trials, each with a fresh random train/test ($80/20$) split. We tested
$\epsilon\in\\{.125,.25,.5,1,2,3\\}$ and fixed $\delta_{i}=1/n_{i}^{2}$ for
all experiments.

To estimate $\upsilon^{2}_{*},$ we followed the procedure used in [WPS20b],
using Newton’s method to compute $w^{*}$ and then averaging
$\|\nabla\widehat{F}_{i}(w^{*})\|^{2}$ over all $i\in[N].$

Preprocessing: We first numerically encoded the categorical variables and then
standardized the numerical features age and BMI to have zero mean and unit
variance.

Gradient clipping:  In the absence of a reasonable a priori bound on the
Lipschitz parameter of the squared loss (as is typical for unconstrained
linear regression problems with potentially unbounded data), we incorporated
gradient clipping [ACG+16] into the algorithms. We then calibrated the noise
to the clip threshold $L$ to ensure LDP. For fairness of comparison, we also
allowed for clipping for the non-private algorithms (if it helped their
performance).

Hyperparameter tuning: For each trial and each algorithm, we swept through a
log-scale grid of 10 stepsizes and 5 clip thresholds 3 times, selected the
parameter $w$ that minimized average (over 3 repetitions) training error
(among all $10\times 5=50$), and computed the corresponding average test
error. The stepsize grids we used ranged from $e^{-8}$ and $e^{1}$ for (LDP)
MB-SGD and from $e^{-10}$ to $1$ for (LDP) Local SGD. The excess risk (train
and test) we computed was for the normalized objective function
$F(w,X,Y)=\|Y-wX\|^{2}/2N_{0}$ where $N_{0}\in\\{1070,268\\}$ ($1070$ for
train, $268$ for test) and $X$ is $N_{0}\times d$ with $d=7$ (including a
column of all $1$s) and $Y\in\mathbb{R}^{N_{0}}.$ The clip threshold grids
were $\\{100,10^{4},10^{6},10^{8},10^{32}\\},$ with the last element
corresponding to effectively no clipping.

Choice of $\sigma^{2}$ and $K$: We used the same $\sigma_{i}^{2}$ and
$K=\frac{n\sqrt{\epsilon}}{2\sqrt{R}}$ as in the logistic regression
experiments described in Section H.1. However, here $L$ is the clip threshold
instead of the Lipschitz parameter.

Relative Root Mean Square Error (RMSE): We scale our reported errors (in the
plots) to make them more interpretable. We define the Relative (test) RMSE of
an algorithm to be
$\sqrt{MSE/NMSE}=\sqrt{\frac{\sum_{i=1}^{N_{\text{test}}}(y_{i}-\hat{y}_{i})^{2}}{\sum_{i=1}^{N_{\text{test}}}(y_{i}-\widebar{y}_{\text{train}})^{2}}}$,
where $NMSE$ (“Naiive Mean Square Error”) is the (test) MSE incurred by the
non-private naiive predictor that predicts $y_{i}$ to be
$\widebar{y}_{\text{train}}$, the average of the training labels, for all test
data $i\in[N_{\text{test}}]$. Here $\hat{y}_{i}$ is the predicted label of the
algorithm. Relative RMSE can be thought of as the Coefficient of Variation or
Relative Standard Deviation of the predictions of the algorithm. Note that
even though the naiive predictor is completely non-private and allowed to
access the entire training data even when $M<N$ (violating the decentralized
data principle of FL), the LDP FL algorithms still outperform this predictor
for most values of $\epsilon$ (except for some experiments when
$\epsilon\approx 0$), as evidenced by values of Relative RMSE being below $1$.
For $\epsilon\approx 1$, LDP MB-SGD tends to outperform the naiive predictor
by $30-40\%$.

Additional experimental results:  In Fig. 7 and Fig. 8, we present results for
experiments with additional settings of $N$ and $M$. We observe qualitatively
similar behavior as in the plots presented in the main body of the paper. In
particular, LDP MB-SGD continues to outperform LDP Local SGD in most tested
setups/privacy levels (especially the high-privacy regime). On the other hand,
for some settings of $M,N,K$, we observe that LDP Local SGD outperforms LDP
MB-SGD as $\epsilon\to 3$ (e.g. Fig. 8, and $N=M=3$). In general, we see that
the utility impact of LDP is relatively insignificant for this problem when
$\epsilon\approx 3$.

Figure 7:  Test error vs. $\epsilon$ for linear regression on heterogeneous
health insurance data. $\delta=1/n^{2}.$ $90\%$ error bars are shown.

Figure 8:  Test error vs. $\epsilon$ for linear regression on heterogeneous
health insurance data. $\delta=1/n^{2}.$ $90\%$ error bars are shown.