#  The Poisson binomial mechanism for secure and private federated learning

Wei-Ning Chen† The early stage of this work is done while on internship at
Google. Ayfer Özgür† Peter Kairouz‡

(Stanford University†, Google Research‡
{wnchen<EMAIL_ADDRESS><EMAIL_ADDRESS>)

###### Abstract

We introduce the Poisson Binomial mechanism (PBM), a discrete differential
privacy mechanism for distributed mean estimation (DME) with applications to
federated learning and analytics. We provide a tight analysis of its privacy
guarantees, showing that it achieves the same privacy-accuracy trade-offs as
the continuous Gaussian mechanism. Our analysis is based on a novel bound on
the Rényi divergence of two Poisson binomial distributions that may be of
independent interest.

Unlike previous discrete DP schemes based on additive noise, our mechanism
encodes local information into a parameter of the binomial distribution, and
hence the output distribution is discrete with bounded support. Moreover, the
support does not increase as the privacy budget $\varepsilon\rightarrow 0$ as
in the case of additive schemes which require the addition of more noise to
achieve higher privacy; on the contrary, the support becomes smaller as
$\varepsilon\rightarrow 0$. The bounded support enables us to combine our
mechanism with secure aggregation (SecAgg), a multi-party cryptographic
protocol, without the need of performing modular clipping which results in an
unbiased estimator of the sum of the local vectors. This in turn allows us to
apply it in the private FL setting and provide an upper bound on the
convergence rate of the SGD algorithm. Moreover, since the support of the
output distribution becomes smaller as $\varepsilon\rightarrow 0$, the
communication cost of our scheme decreases with the privacy constraint
$\varepsilon$, outperforming all previous distributed DP schemes based on
additive noise in the high privacy or low communication regimes.

##  1 Introduction

The standard technique for ensuring differential privacy (DP) Dwork et al.
(2006b) of learning algorithms is to add noise either to the output of a
function evaluated on the data (in the centralized setting) or locally to the
data itself (in federated settings Kairouz et al. (2019); McMahan et al.
(2016)). Two commonly used distributions for noise are the Gaussian and
Laplace distributions. While simple enough for mathematical reasoning and
analysis, the continuous nature of these distributions presents a number of
challenges. First, it is not possible to represent real samples on finite
computers, making these mechanisms prone to numerical errors that can break
privacy guarantees Mironov (2012). Second, they cannot be used in the
federated setting where it may be desirable to first locally perturb the data
(e.g. the local model update computed by stochastic gradient descent(SGD)
iterations) and then use cryptographic primitives such as secure aggregation
(SecAgg) Bonawitz et al. (2016b) to allow the server to obtain a summary of
the local data (such as the mean of local model updates) without having access
to individual information. This combination of local DP and secure aggregation
is desirable as it does not rely on the clients’ full trust in the server,
while potentially achieving the same utility-privacy trade-off as in the
centralized case. However, secure aggregation is based on modular arithmetic
which is not compatible with the real output from a privatization mechanism
that relies on perturbing data with continuous noise. This has led to an
increasing recent interest in mechanisms that perturb the data (or a function
of it) with the addition of discrete noise, such as the binomial in Dwork et
al. (2006a); Agarwal et al. (2018), the discrete Gaussian in Canonne et al.
(2020); Kairouz et al. (2021), and Skellam noise in Agarwal et al. (2021).

These additive discrete noise mechanisms however have a few of their own
shortcomings. First, when the data itself is continuous, as in the case of
local model updates obtained from SGD iterations in federated learning, it has
to be discretized before the addition of discrete noise. This adds
quantization noise and complicates analysis. Second, these distributions have
discrete yet unbounded support which means that the privatized data has to go
through modular clipping when combined with secure aggregation protocols which
operate on a finite group. This is the approach in Kairouz et al. (2021) and
Agarwal et al. (2021), which focus on developing differentially private
federated learning algorithms by using these additive noise mechanisms locally
at the clients and then feeding the privatized local updates to the secure
aggregation protocol. Upon modular clipping, however, the discrete additive
noise becomes no longer zero-mean, and hence the resulting estimator (of the
mean of the local model updates) is _biased_. The bias makes it difficult to
provide tight convergence guarantees for stochastic first-order optimization
methods which rely on this estimate. In contrast, it is usually not difficult
to provide a tight convergence analysis when the optimization method has
access to a noisy but unbiased estimate of the true mean of the updates.
Finally, all additive noise mechanism (continuous or discrete) share the
common principle of adding more noise to achieve higher privacy, i.e. they
require a higher noise variance when higher privacy is desired. This, however,
has a direct impact on the communication cost in federated settings when the
noise is added locally. Indeed, for all of the above mentioned schemes Kairouz
et al. (2021); Agarwal et al. (2021, 2018) the communication cost grows
_inversely_ with the privacy budget; when high privacy is desired nodes need a
large bit budget to communicate the large noise they add to their updates.
This contradicts the conclusion of Chen et al. (2020) which shows that in a
federated learning setting without secure aggregation the optimal
communication cost can be made to _decrease_ with the privacy budget;
intuitively we can use less bits in the high privacy regime because we are
required to communicate less information about the local data.

In this paper, we develop a novel differential privacy mechanism that does not
rely on additive noise. This mechanism, which we call the multi-dimensional
Poisson Binomial mechanism (PBM), takes a continuous input, encodes it into
the parameter $p$ of a binomial distribution $\mathsf{Binom}\left(m,p\right)$,
and generates a sample from this distribution111We note that the binomial
mechanism proposed in Agarwal et al. (2018) is an additive noise mechanism (it
adds Binomial noise to the data), and while it has a finite output range, it
does not provide any Rényi DP guarantees (which is the main focus of this
paper as RDP allows for tightly accounting privacy loss across multiple
rounds).. This results in a finite and discrete output in $\mathbb{Z}_{m}$
which can be easily combined with the integer modular arithmetic in SecAgg,
without the need for quantization or modular clipping. As a result, the
estimate (of the average model updates) obtained at the output of SecAgg is
_unbiased_ leading, to our knowledge, to the first unbiased privacy scheme
compatible with SecAgg. Moreover, the communication cost of PBM decreases when
the privacy budget $\varepsilon$ decreases. This is because the first
parameter $m$ of the distribution $\mathsf{Binom}\left(m,p\right)$ is linear
in the privacy budget $\varepsilon$ and hence the logarithm of it, which
dictates the communication budget, decreases to $1$ as $\varepsilon\rightarrow
0$.

#### Our contributions.

Our main technical contributions are summarized as follows.

  * •

We introduce the multi-dimensional Poisson binomial mechanism, an unbiased and
bounded discrete DP mechanism for distributed mean estimation (DME). We
provide a tight analysis for its Rényi DP (RDP) guarantees showing that it
provides the same utility-privacy trade-off as the continuous Gaussian
mechanism. As a by-product, our analysis yields a novel bound on the Rényi
divergence of two Poisson binomial distributions that can be useful in other
applications.

  * •

We show that the communication cost of our scheme (defined as the number of
bits needed to achieve the accuracy of the centralized DP model) decreases
with the privacy budget, as opposed to previous discrete DP schemes Agarwal et
al. (2018); Kairouz et al. (2021); Agarwal et al. (2021). Thus in the high-
privacy regime, our scheme uses significantly less bandwidth while still
achieving the right order of accuracy.

  * •

We combine PBM with distributed SGD and SecAgg in a FL setting and analyze its
convergence rate.

###  1.1 Problem setup and prerequisites

In this section, we present the distributed mean estimation (DME) Suresh et
al. (2017) problem under differential privacy and SecAgg. Note that DME is
closely related to federated learning with SGD, where in each iteration, the
server updates the global model by a noisy mean of the local model updates.
This noisy estimate is typically obtained by using a DME scheme, and thus one
can easily build a distributed DP-SGD scheme (and hence a private FL scheme)
from a differentially private DME scheme.

Consider $n$ clients each with local data $x_{i}\in\mathbb{R}^{d}$ that
satisfies $\left\lVert x_{i}\right\rVert_{2}\leq c$ (one can think of $x_{i}$
as a clipped local gradient). A server wants to learn an estimate $\hat{\mu}$
of the mean $\mu\triangleq\frac{1}{n}\sum_{i}x_{i}$ after communicating with
the $n$ clients.

#### Secure aggregation.

In order to fully leverage the distributed nature of FL to enhance clients’
privacy, the honest-but-curious server collects local data through a _secure
aggregation protocol_. More precisely, each client encodes $x_{i}$ into a
finite additive group $\mathcal{Z}$ by computing
$Z_{i}\triangleq\mathcal{A}_{\mathsf{enc}}(x_{i})$. The $n$ clients and the
server then participate in the SecAgg protocol, so that only $\sum_{i}Z_{i}$
can be revealed to the server. Finally, the server computes $\hat{\mu}$ based
on $\sum_{i}Z_{i}$, an estimate of the true mean. The goal is to jointly
design an encoder $\mathcal{A}_{\mathsf{enc}}$ and an estimator $\hat{\mu}$,
such that

  1. 1.

$\hat{\mu}$ satisfies a differential privacy constraint (see Definition 1.1
and Definition 1.2 for formal statements).

  2. 2.

The per-client communication cost $b=\log\left\lvert\mathcal{Z}\right\rvert$
is small.

  3. 3.

$\hat{\mu}$ is unbiased (i.e. $\mathbb{E}[\hat{\mu}]=\mu$) and has small mean
squared error (MSE):
$\mathbb{E}\left[\left\lVert\hat{\mu}-\mu\right\rVert^{2}_{2}\right]$.

Without loss of generality, we will set $\mathcal{Z}$ to be
$\left(\mathbb{Z}_{M}\right)^{l}$ for some $l,M\in\mathbb{N}$ (where
$\mathbb{Z}_{M}$ is the group of integers modulo $M$ equipped with modulo $M$
addition), so $b=l\log M$ is the total number of communicated bits. The
summation is coordinate-wise modulo $M$ addition, i.e.

$\mathsf{SecAgg}\left(\mathcal{A}_{\mathsf{enc}}(x_{1}),...,\mathcal{A}_{\mathsf{enc}}(x_{n})\right)=\sum_{i}\mathcal{A}_{\mathsf{enc}}(x_{i})\mathsf{mod}M.$

#### Differential Privacy.

Finally, we introduce the notion of differential privacy Dwork et al. (2006b)
and Rényi differential privacy (RDP) Mironov (2017). We are mostly interested
in developing mechanisms that satisfy RDP, as it allows for tight privacy
accounting across training iterations.

######  Definition 1.1 ((Approximate) Differential Privacy).

For $\varepsilon,\delta\geq 0$, a randomized mechanism $M$ satisfies
$(\varepsilon,\delta)$-DP if for all neighboring datasets $D,D^{\prime}$ and
all $\mathcal{S}$ in the range of $M$, we have that

$\mathbb{P}\left(M(D)\in\mathcal{S}\right)\leq
e^{\varepsilon}\mathbb{P}\left(M(D^{\prime})\in\mathcal{S}\right)+\delta,$

where $D$ and $D^{\prime}$ are neighboring pairs if they can be obtained from
each other by adding or removing all the records that belong to a particular
user.

######  Definition 1.2 ( Rényi Differential Privacy (RDP)).

A randomized mechanism $M$ satisfies $(\alpha,\varepsilon)$-RDP if for any two
neighboring datasets $D,D^{\prime}$, we have that
$D_{\alpha}\left(P_{M(D)},P_{M(D^{\prime})}\right)\leq\varepsilon$ where
$D_{\alpha}\left(P,Q\right)$ is the Rényi divergence between $P$ and $Q$ and
is given by

$D_{\alpha}\left(P,Q\right)\triangleq\frac{1}{\alpha}\log\left(\mathbb{E}_{Q}\left[\left(\frac{P(X)}{Q(X)}\right)^{\alpha}\right]\right).$

Note that one can cast RDP to (approximate) DP. See Section A for details.

###  1.2 Related works

The closest works to ours are the distributed discrete DP mechanisms cpSGD
Agarwal et al. (2018), DDG Kairouz et al. (2021), and Skellam Agarwal et al.
(2021). Unlike our proposed scheme, these mechanisms achieve differential
privacy (DP) Dwork et al. (2006b) by adding discrete noise that (1) has a
distribution that asymptotically converges to a normal distribution, and (2)
are (nearly) “closed” under addition. However, since the noise is
asymptotically normal, in the high-privacy regimes where $\varepsilon$ is
small, the variance of the noise (and hence the communication cost) explodes.
In addition, since the noise has infinite range (except for cpSGD222However,
we note that cpSGD only satisfies approximate DP but not Renyi DP, so we can
only use strong composition theorems Dwork et al. (2010); Kairouz et al.
(2016) to account privacy loss.), one has to perform modular clipping in order
to perform SecAgg. This leads to bias that can cause issues for the downstream
tasks such as SGD.

Another closely related work is Cheu et al. (2019), in which a distributed DP
scheme for scalar mean estimation under the _shuffled_ model of DP is
proposed. The scheme introduced in Cheu et al. (2019) can be viewed as a
concatenation of stochastic rounding and randomized response, and although
introduced under the context of shuffling instead of secure aggregation (which
is considered in this work), statistically their scheme is equivalent to (the
scalar version of) our scheme when the parameters are properly selected.

However, we remark on several main differences as follows. First, under the
shuffled model, Cheu et al. (2019) suffers from sub-optimal communication
cost; indeed, the per-client message size (and hence the communication cost)
grows as $O(\sqrt{n}\varepsilon)$, which is improved in follow-up work Ghazi
et al. (2021). This sub-optimal communication issue, however, does not appear
under the secure aggregation model, and indeed, the per-client communication
cost of our scheme (which is under the secure aggregation model) is
$O\left(\log n\right)$. Second, Cheu et al. (2019) only considers the scalar
mean estimation problem, which does not directly apply to FL. Extending the
results to the multi-dimensional setting, while still preserving the order-
optimal privacy-accuracy trade-offs, is non-trivial. In this work, we address
it via Kashin’s representation (Lyubarskii & Vershynin, 2010). Finally, Cheu
et al. (2019) studies $(\varepsilon,\delta)$ approximate DP and only obtains
an order-wise optimal bound on the privacy guarantees. In this paper, we
analyze Rényi DP (which allows for tighter privacy accounting), and more
importantly, our analysis provides a method to numerically compute the _exact_
privacy loss. Indeed, in addition to theoretically proving the order-wise
optimality (under Rényi DP), we numerically show that our scheme converges to
the centralized Gaussian mechanism (i.e. it matches the Gaussian mechanism’s
constants).

In this paper, we combine our discrete DP mechanism with SecAgg (more
precisely, single-server SecAgg) to achieve distributed DP without introducing
bias. Single-server SecAgg is achieved via additive masking over a finite
group Bonawitz et al. (2016a); Bell et al. (2020). To achieve provable privacy
guarantees, however, SecAgg is insufficient as the sum of local model updates
may still leak sensitive information Melis et al. (2019); Song & Shmatikov
(2019); Carlini et al. (2019); Shokri et al. (2017). To address this issue,
DP-SGD or DP-FedAvg can be employed Song et al. (2013); Bassily et al. (2014);
Geyer et al. (2017); McMahan et al. (2017). In this work, we aim to provide
privacy guarantees in the form of Rényi DP Mironov (2017) because it allows
for tracking the end-to-end privacy loss tightly.

We also distinguish our distributed DP setup from the local DP setup
Kasiviswanathan et al. (2011); Evfimievski et al. (2004); Warner (1965), where
the data is perturbed on the client-side before it is collected by the server
in the clear. Although both local DP and distributed DP with SecAgg do not
rely on a fully trusted centralized server, the local DP model provides
stronger privacy guarantees as it allows the server to observe individual
(privatized) information, while distributed DP requires that the server
executes the SecAgg protocol faithfully. Given its strong privacy guarantees,
local DP naturally suffers from poor privacy-utility trade-offs
Kasiviswanathan et al. (2011); Duchi et al. (2013); Kairouz et al. (2016).
That is why we focus on distributed DP via SecAgg in this paper.

Our scheme also makes use of Kashin’s representation Kashin (1977); Lyubarskii
& Vershynin (2010), a powerful tool that enables us to transform the
$\ell_{2}$ geometry of the input data to an $\ell_{\infty}$ one in a lossless
fashion. This facilitates the analysis and allows for decoupling the high-
dimensional problem into 1-dimensional sub-tasks. Similar idea has been used
in different settings; for instance, Feldman et al. (2017); Caldas et al.
(2018); Chen et al. (2020).

##  2 Main Results

Algorithm 1 The Poisson Binomial Mechanism

Input: $x_{1},...,x_{n}\in\mathcal{B}_{d}(c)$, parameters
$\theta\in[0,\frac{1}{4}]$, $m\in\mathbb{N}$, a tight frame $U$ associated
with Kashin’s representation at level $K>0$

for each client $i$ do

Set $y_{i}$ to be the Kashin’s representation of $x_{i}$, so
$y_{i}\in\mathbb{R}^{\Theta(d)}$ and $\left\lVert
y_{i}\right\rVert_{\infty}\leq\frac{cK}{\sqrt{d}}$.

for coordinate $j$ of $y_{i}$ do

$Z_{ij}\leftarrow\mathsf{scalar\\_PBM}\left(y_{ij},m,\theta,c^{\prime}=\frac{cK}{\sqrt{d}}\right)$

end for

Send $Z_{i}$ to the server via SecAgg

end for

(Server) Computes
$\hat{\mu_{y}}=\frac{c^{\prime}}{mn\theta}\left(\sum_{i}Z_{i}-\frac{mn}{2}\right)$

(Server) Computes $\hat{\mu}=U\hat{\mu_{y}}$

Return: $\hat{\mu}$

We introduce the Poisson Binomial mechanism for DME with SecAgg and
differential privacy. The proposed protocol (Algorithm 1) consists of three
stages:

  * •

Each client computes the Kashin’s representation of local data $x_{i}$
(denoted as $y_{i}$), which allows for optimally transforming the $\ell_{2}$
geometry of the data into $\ell_{\infty}$.

  * •

The $n$ clients apply the scalar Poisson Binomial mechanism (Algorithm 2)
separately on each coordinate of $y_{i}$, and the server estimates
$\mu_{y}\triangleq\frac{1}{n}\sum_{i}y_{i}$.

  * •

The server reconstructs $\hat{\mu}_{x}$ from the Kashin representation of
$\hat{\mu}_{y}$.

Algorithm 2 The (Scalar) Poisson Binomial Mechanism

Input: $c>0$, $x_{i}\in[-c,c]$, $\theta\in[0,\frac{1}{4}]$, $m\in\mathbb{N}$

Re-scaling $x_{i}$: $p_{i}\triangleq\frac{\theta}{c}x_{i}+\frac{1}{2}$.

Privatization:
$Z_{i}\triangleq\mathsf{Binom}\left(m,p_{i}\right)\in\mathbb{Z}_{m}.$

Return: $Z_{i}$

Note that Algorithm 1 builds on Algorithm 2, the scalar version of PBM, which
we analyze in Section 3. Parameters $(m,\theta)$ determine privacy,
communication cost, and MSE; in other words, the privacy-utility trade-offs of
Algorithm 1 can be fully characterized by $(m,\theta)$, which we summarize in
the following theorem.

######  Theorem 2.1.

Let $\left\lVert x_{i}\right\rVert\leq c$, $m\in\mathbb{N}$, and
$\theta\in[0,\frac{1}{4}]$. Then with parameters $m,\theta$, Algorithm 1:

  * •

satisfies $\left(\alpha,\varepsilon(\alpha)\right)$-RDP for any $\alpha>1$ and
$\varepsilon(\alpha)=\Omega\left({dm\theta^{2}\alpha}/{n}\right)$,

  * •

requires $O(d\left(\log m+\log n\right))$ bits of per-client communication,

  * •

yields an unbiased estimator $\hat{\mu}$ with
$O\left(\frac{c^{2}}{nm\theta^{2}}\right)$ MSE.

######  Remark 2.2.

Although in Theorem 2.1 we present an asymptotic result, we remark that (1)
the MSE can be upper bound explicitly, and (2) the Rényi DP can be computed
numerically (as shown in Section 2.1). Indeed, we show that when we pick
$\theta$ small enough, the MSE of PBM converges to the (centralized
continuous) Gaussian mechanism quickly.

Several observations are given in order. First, the privacy guarantee
$\varepsilon(\alpha)$ can be written as a function of the variance (i.e., the
MSE):
$\varepsilon(\alpha)=\Omega\left(\frac{dc^{2}\alpha}{n^{2}\mathsf{MSE}\left(\hat{\mu}\right)}\right)$.
This privacy-accuracy trade-off matches that of the (centralized) Gaussian
mechanism 333We notice that when the $\ell_{2}$ sensitivity is $c^{2}/n^{2}$,
a Gaussian mechanism that adds $N(0,\sigma^{2}\mathbb{I}_{d})$ noise achieves
RDP
$\varepsilon_{\mathsf{Gauss}}(\alpha)=\frac{c^{2}\alpha}{2n^{2}\sigma^{2}}$,
and the corresponding $\mathsf{MSE}(\hat{\mu}_{\mathsf{Gauss}})=d\sigma^{2}$.
given by
$\varepsilon_{\mathsf{Gauss}}(\alpha)=\Omega\left(\frac{dc^{2}\alpha}{n^{2}\mathsf{MSE}\left(\hat{\mu}_{\mathsf{Gauss}}\right)}\right)$
(which is obtained by bounding the sensitivity of the mean function by
$c^{2}/n^{2}$). This implies that Algorithm 1 attains order-optimal errors. In
Section 2.1 below, we numerically compute the MSE-privacy trade-offs of PBM
and the Gaussian mechanism.

Note that in Theorem 2.1, both $\varepsilon(\alpha)$ and the the variance of
the estimator depend on the parameters $m$ and $\theta$ of the algorithm
through the product $m\theta^{2}$. Hence, this leaves some freedom in the
choice of $m$ and $\theta$ if one is concerned only with privacy and MSE.
However, the choice of $m$ also dictates the communication cost. We next
describe how one can pick $(\theta,m)$ to minimize the communication cost for
the same $\left(\alpha,\varepsilon(\alpha)\right)$-RDP constraint and MSE,
where the latter is dictated by the first according to the above trade-off.
Observe that the privacy budget $\varepsilon(\alpha)$ fixes the value of the
product $m\theta^{2}$, so to minimize $m$, and hence the communication cost,
we would like to pick $\theta$ as large as possible. However, $\theta$ is
restricted to $[0,\frac{1}{4}]$. Therefore we can determine $m$ and $\theta$
by the following two steps:

  1. 1.

Set $m=1$ and compute the corresponding $\theta$ such that the resulting
privacy is $\varepsilon(\alpha)$. If $\theta>1/4$, clip $\theta$ to 1/4. This
leads to
$\theta=O\left(\min\left(\frac{1}{4},\sqrt{\frac{n\varepsilon(\alpha)}{d\alpha}}\right)\right)$.

  2. 2.

Then, we adjust $m$ again according to $\theta$. If $\theta=1/4$ (i.e. when
$\theta$ clipped in the previous step), we set
$m=O\left(\frac{n\varepsilon(\alpha)}{d\alpha}\right)$. Otherwise $m=1$. Hence
$m$ is upper bounded by
$\max\left(1,O\left(\frac{n\varepsilon(\alpha)}{d\alpha}\right)\right).$

Plugging the above upper bound on $m$ to Theorem 2.1, the communication cost
becomes
$O\left(d\left(\log\left(n+\frac{n\varepsilon(\alpha)}{d\alpha}\right)\right)\right)$.

Next, to compare the communication cost of our scheme with previous schemes,
we convert it into $(\varepsilon_{\mathsf{DP}}(\delta),\delta)$-DP via Lemma
A.2 and arrive at the following corollary:

######  Corollary 2.3 (Approximate DP of PBM).

By setting
$\theta=O\left(\min\left(\frac{1}{4},\sqrt{\frac{n\varepsilon_{\mathsf{DP}}^{2}}{d\log(1/\delta)}}\right)\right)$
and $m=\lceil\frac{n\varepsilon^{2}_{\mathsf{DP}}}{d\log(1/\delta)}\rceil$,
Algorithm 1 satisfies
$\left(\varepsilon_{\mathsf{DP}},\delta\right)$-approximate DP. Moreover, the
(per-client) communication cost is
$O\left(d\left(\log\left(n+\frac{n\varepsilon_{\mathsf{DP}}^{2}}{d\log(1/\delta)}\right)\right)\right)$,
and $\hat{\mu}$ is unbiased with MSE at most
$O_{\delta}\left(\frac{c^{2}d}{n^{2}\varepsilon_{\mathsf{DP}}^{2}}\right)$.

We remark that the communication cost of PBM decreases as
$\varepsilon_{\mathsf{DP}}$) decreases, exhibiting the correct dependency on
$\varepsilon_{\mathsf{DP}}$ in the high-privacy regime. The communication cost
of other discrete DP mechanisms based on additive noise, such as Agarwal et
al. (2018); Kairouz et al. (2021); Agarwal et al. (2021) increase as
$\varepsilon$ gets smaller. For instance, the DDG mechanism Kairouz et al.
(2021) requires
$O\left(d\left(\log\left(n+\frac{d}{\varepsilon_{\mathsf{DP}}^{2}}\right)\right)\right)$
bits of communication per-client, which becomes unbounded when
$\varepsilon_{\mathsf{DP}}\rightarrow 0$. See Table 1 for a comparison.

| communication | MSE | bias
---|---|---|---
PBM | $O\left(d\log\left(\lceil{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{n\varepsilon_{\mathsf{DP}}^{2}}{d}}\rceil\cdot n\right)\right)$ | $O_{\delta}\left(\frac{c^{2}d}{n^{2}\varepsilon_{\mathsf{DP}}^{2}}\right)$ | no
DDG | $O\left(d\log\left(\lceil\frac{d}{\varepsilon_{\mathsf{DP}}^{2}}\rceil\cdot n\right)\right)$ | $O_{\delta}\left(\frac{c^{2}d}{n^{2}\varepsilon_{\mathsf{DP}}^{2}}\right)$ | yes
Skellam | $O\left(d\log\left(\lceil\frac{d}{\varepsilon_{\mathsf{DP}}^{2}}\rceil\cdot n\right)\right)$ | $O_{\delta}\left(\frac{c^{2}d}{n^{2}\varepsilon_{\mathsf{DP}}^{2}}\right)$ | yes
Binomial | $O\left(d\log\left(\lceil\frac{d}{\varepsilon_{\mathsf{DP}}^{2}}\rceil\cdot n\right)\right)$ | $O_{\delta}\left(\frac{c^{2}d\log(d)}{n^{2}\varepsilon_{\mathsf{DP}}^{2}}\right)$ | yes
Table 1: A comparison of the communication costs and MSEs of different
discrete DP schemes. For the communication cost, we hide the dependency on
$\log n$ since we are interested in high-dimensional regimes where $d\gg n$.

###  2.1 Numerical evaluation

Figure 1:  Privacy-MSE (variance) trade-offs of PBM and the Gaussian
mechanism.

In Figure 1, we numerically compute the privacy guarantee of Algorithm 1 and
compared it with the Gaussian mechanism. For the PBM, we fix the communication
cost (i.e. fix $m$), vary parameter $\theta$, and compute the corresponding
Rényi DP (i.e., $\varepsilon(\alpha)$) and MSE. We see that as $m$ increases,
the privacy-MSE curve approaches to that of the Gaussian mechanism, indicating
that our scheme is also optimal in its leading constant. We present another
numerical results in Section B, in wich we fix $\theta$ and vary $m$ to get
the trade-off curves.

##  3 The Scalar Poisson Binomial Mechanism

In this section, we analyze the utility and privacy guarantees of the scalar
version of PBM (i.e., with $d=1$). Recall that when $d=1$, each $x_{i}$ in the
DME task (see the formulation in Section 1.1) becomes a bounded real number
with $|x_{i}|<c$ eliminating the Kashin step. Under this special case,
Algorithm 2 encodes each $x_{i}$ into a parameter of a binomial distribution
by 1) first mapping $x_{i}$ into
$\left[\frac{1}{2}-\theta,\frac{1}{2}+\theta\right]$ by
$p_{i}\triangleq\frac{1}{2}+\frac{\theta}{c}x_{i}$, and then 2) generating a
binomial random variable $Z_{i}\sim\mathsf{Binom}(m,p_{i})$.

Notice that from each $Z_{i}$, one can obtain an unbiased estimator on $x_{i}$
by computing
$\hat{x_{i}}=\frac{c}{\theta}\left(\frac{1}{m}Z_{i}-\frac{1}{2}\right).$
Therefore, upon collecting $\sum_{i}Z_{i}$ from SecAgg protocol, the server
can estimate $\mu$ by
$\hat{\mu}\left(\sum_{i}Z_{i}\right)\triangleq\frac{c}{nm\theta}\left(\sum_{i}Z_{i}-\frac{mn}{2}\right)$
(recall that the server can only learn $\sum_{i}Z_{i}$ but not individual
$Z_{i}$).

######  Remark 3.1.

As discussed before, $m$ and $\theta$ can be chosen to achieve a desired
privacy-utility-communciation trade-off. Intuitively, with larger $m$, one can
reduce the variance of the estimator while weakening the privacy guarantees;
similarly with smaller $\theta$, one would get a better privacy guarantee by
trading off the accuracy.

#### Utility of the scalar PBM.

As mentioned above, $\hat{\mu}$ yields an _unbiased_ estimate on $\mu$, and
the variance can be calculated as
$\mathsf{Var}\left(\hat{\mu}\right)=\frac{c^{2}}{m^{2}\theta^{2}}\sum_{i}\mathsf{Var}\left(Z_{i}\right)\leq\frac{c^{2}}{4nm\theta^{2}}.$

On the other hand, since $Z_{i}\leq m$, $\sum_{i}Z_{i}\leq nm$. Thus to avoid
overflow, we will set $M=nm$, where recall that $M$ the size of the finite
group SecAgg operates on. Therefore, the communication cost of Algorithm 2 is
$\log M=\log n+\log m$ bits per client.

#### Privacy of the scalar PBM.

Next, the privacy guarantee (in an RDP form), is summarized in the following
corollary.

######  Corollary 3.2.

Let $m\in\mathbb{N}$ and $\theta\in[0,\frac{1}{4}]$ be parameters of Algorithm
2. Then Algorithm 2 satisfies $(\alpha,\varepsilon(\alpha))$-RDP for any
$\alpha>1$ and

$\varepsilon(\alpha)\geq
C_{0}\left(\frac{\theta^{2}}{(1-2\theta)^{4}}\right)\frac{\alpha m}{n},$ (1)

where $C_{0}>0$ is an universal constant.

###  3.1 Analysis of the RDP

To analyze the privacy loss of Algorithm 1, let
$Y_{i}\sim\mathsf{Binom}(m,p_{i})$ and
$Y_{1}^{\prime}\sim\mathsf{Binom}(m,p_{1}^{\prime})$, where recall that
$p_{1},...,p_{n},p_{1}^{\prime}\in\left[\frac{1}{2}-\theta,\frac{1}{2}+\theta\right]$.
For any $\alpha>1$, the $\varepsilon(\alpha)$ is given by

$\max_{p_{1},...,p_{n},p_{1}^{\prime}}D_{\alpha}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right),$
(2)

with the maximum taken over
$\left[\frac{1}{2}-\theta,\frac{1}{2}+\theta\right]^{n+1}$. Our main technical
contribution is the following (orderwise) tight upper bound on the Rényi
divergence of two Poisson binomial distributions, which then characterizes the
privacy loss of our scheme.

######  Theorem 3.3.

Let $\alpha>1$ and
$p_{1},...,p_{n},p^{\prime}_{1}\in[\frac{1}{2}-\theta,\frac{1}{2}+\theta]$.
Let $Y_{i}\sim\mathsf{Binom}(m,p_{i})$ and
$Y_{1}^{\prime}\sim\mathsf{Binom}(m,p_{1}^{\prime})$. Then it holds that

$\displaystyle
D_{\alpha}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right)$
$\displaystyle\vspace{3em}\leq
C_{0}\frac{\theta^{2}}{(1-2\theta)^{4}}\left(\min\left(4,\frac{\alpha^{2}}{\alpha-1}\right)\right)\frac{m}{n},$

where $C_{0}>0$ is an universal constant.

######  Remark 3.4.

Although we present an asymptotic result here, using the quasi-convexity of
Rényi divergence, one can show that the worst-case scenario is attained by the
extremal points (i.e., when
$p_{i}\in\left\\{\frac{1}{2}-\theta,\frac{1}{2}+\theta\right\\}$), as shown in
Lemma 3.5. This allows us to efficiently compute the privacy loss _exactly_ ,
as shown in Section 2.1.

An immediate corollary of Theorem 3.3 is the RDP guarantee of the proposed PBM
(summarized in Corollary 3.2).

In the rest of this section, we provide a proof of Theorem 3.3.

#### Step 0: decomposing $Y_{i}$.

To begin with, observe that since $Y_{i}\sim\mathsf{Binom}(m,p_{i})$, we can
decompose it into sum of $m$ independent and identical copies of
$\mathsf{Ber}(p_{i})$, i.e., $Y_{i}=\sum_{j=1}^{m}X^{(j)}_{i}$, where
$X^{(j)}_{i}\overset{\text{i.i.d.}}{\sim}\mathsf{Ber}(p_{i})$ for $j\in[m]$.
Therefore

$\sum_{i=1}^{n}Y_{i}=\sum_{i=1}^{n}\sum_{j=1}^{m}X^{(j)}_{i}=\sum_{j=1}^{m}\underbrace{\left(\sum_{i=1}^{n}X^{(j)}_{i}\right)}_{\triangleq
Z_{j}},$

and similarly we can write
$Y_{1}^{\prime}+\sum_{i=2}^{n}Y_{i}=\sum_{j=1}^{m}Z_{j}^{\prime}$, where
$Z_{j}^{\prime}=X^{{}^{\prime}(j)}_{1}+\sum_{i=2}^{n}X^{(j)}_{i}$.

Grouping the summation of $X^{(j)}_{i}$ according to $j\in[m]$ and applying
the data processing inequality for Rényi divergence, we upper bound (2) by

$\displaystyle\max_{p_{1},...,p_{n},p_{1}^{\prime}}D_{\alpha}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right)$
$\displaystyle=\max_{p_{1},...,p_{n},p_{1}^{\prime}}D_{\alpha}\left(P_{Z_{1}+...+Z_{m}}\middle\|P_{Z^{\prime}_{1}...+Z^{\prime}_{m}}\right)$
$\displaystyle\leq\max_{p_{1},...,p_{n},p_{1}^{\prime}}mD_{\alpha}\left(P_{Z_{1}}\middle\|P_{Z^{\prime}_{1}}\right)$
$\displaystyle=\max_{p_{1},...,p_{n},p_{1}^{\prime}}mD_{\alpha}\left(P_{X_{1}+X_{2}+...+X_{n}}\middle\|P_{X^{\prime}_{1}+X_{2}+...+X_{n}}\right),$
(3)

where $X_{i}\sim\mathsf{Ber}(p_{i})$ and
$X^{\prime}_{1}\sim\mathsf{Ber}(p^{\prime}_{1})$.

#### Step 1: maximum achieved by extremal points.

Next, since $(P,Q)\mapsto D_{\alpha}\left(P\middle\|Q\right)$ is quasi-convex
(Van Erven & Harremos, 2014, Thoerem 13), we claim that (3.1) is maximized at
extreme points:

######  Lemma 3.5.

(3.1) is maximized at extreme points i.e., when
$p_{1},...,p_{n},p_{1}^{\prime}\in\left\\{\frac{1}{2}-\theta,\frac{1}{2}+\theta\right\\}$.

This implies (3.1) can be upper bounded by the following binomial form:

$\displaystyle\max_{k\in[n-1]}D_{\alpha}\Big{(}P_{\mathsf{Binom}\left(1+k,\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k-1,\frac{1}{2}+\theta\right)}\big{\|}P_{\mathsf{Binom}\left(k,\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k,\frac{1}{2}+\theta\right)}\Big{)}.$
(4)

#### Step 2: applying data processing inequality.

Next, we simplify (4) by carefully applying the data processing inequality.
Let $k^{*}\in[n-1]$ maximize (4). If $k^{*}\leq\frac{n}{2}$, we apply the data
processing inequality to discard the first half of common binomial random
variables (see Figure 2 for an illustration), i.e.,

$\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime}-k^{*},\frac{1}{2}+\theta\right),$

where $n^{\prime}\triangleq\lceil\frac{n-1}{2}\rceil$. On the other hand, if
$k^{*}\geq\frac{n}{2}$, then we apply the data processing inequality to remove
the second half of common parts, i.e.,

$\mathsf{Binom}\left(n^{\prime}+k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right).$

Figure 2: An illustration of applying data processing inequality, where under
the scenario of $k^{*}\leq\frac{1}{2}$, we discard the first half of common
binomial sum.

This leads to the following lemma:

######  Lemma 3.6.

(4) is upper bounded by the maximum of the following two quantities:

  1. (a)

$D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}\right)$,

  2. (b)

$D_{\alpha}\left(P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}-\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}-\theta\right)}\right)$.

#### Step 3: bounding the Rényi divergence via MGF.

Finally, we upper bound each of the two terms in (C.3) separately. We start
with the following simple but useful lemma, which bounds the Rényi divergence
of two distributions by the sub-Gaussian norm of their likelihood ratio (LR).

######  Lemma 3.7.

Let $P,Q$ be two probability measures on $\mathcal{X}$ and let
$\frac{dP}{dQ}(x)$ be the Radon-Nikodym derivative. Let $X\sim Q$. Then for
any $\alpha>1$,

$D_{\alpha}\left(P\middle\|Q\right)\leq
C_{0}\frac{\alpha^{2}}{\alpha-1}\left\lVert\frac{dP}{dQ}\left(X\right)-1\right\rVert^{2}_{\psi_{2}},$

where $\left\lVert Z\right\rVert_{\psi_{2}}$ denotes the sub-Gaussian norm of
$Z$ and $C_{0}>0$ is a universal constant.

To apply Lemma 3.7 to control (a) and (b) in Lemma 3.6, we need to compute and
bound the sub-Gaussian norms of the likelihood ratio (LRs) of random variables
in (a) and (b) of Lemma 3.6, respectively.

To this end, let us define
$R(i)\triangleq\frac{P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}(i)}{P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}(i)}.$
Then the LRs corresponding to random variables of (a) and (b) in Lemma 3.6 are
$R(I)$ and $1/R(I^{\prime})$ respectively, where $I\sim
P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}$ and
$I^{\prime}\sim
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}$.

It turns out that $R(i)$ is a linear function of $i$, and since both $I$ and
$I^{\prime}$ are sum of binary random variables, one can control their sub-
gaussian norms (and hence that of $R(I)$ and $1/R(I^{\prime})$). We summarize
the bound in the following lemma and defer the proof to Section C.5.

######  Lemma 3.8.

Let $R(i)$ be defined as above and let $I\sim
P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}$ and
$I^{\prime}\sim
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}$.
Then

  * •

$\left\lVert R(I)-1\right\rVert^{2}_{\psi_{2}}\leq
C_{1}\frac{\theta^{2}}{(1-4\theta^{2})^{2}(n^{\prime}+1)},$

  * •

$\left\lVert 1/R(I^{\prime})-1\right\rVert^{2}_{\psi_{2}}\leq
C_{2}\frac{\theta^{2}}{(1-2\theta)^{4}}\frac{1}{n^{\prime}+1},$

for some $C_{1},C_{2}>0$.

#### Step 4: putting everything together.

Combining Lemma 3.8, Lemma 3.7, and Lemma 3.6, we obtain that

$\displaystyle\eqref{eq:ber_extreme}\leq
C_{3}\frac{\theta^{2}}{(1-2\theta)^{4}}\left(\frac{\alpha^{2}}{\alpha-1}\right)\frac{1}{n^{\prime}+1}.$

Together with Lemma 3.5 and (3.1), we conclude that

$\displaystyle\max_{p_{1},...,p_{n},p_{1}^{\prime}}$ $\displaystyle
D_{\alpha}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right)$
$\displaystyle\leq
C_{7}\left(\frac{\theta^{2}}{(1-2\theta)^{4}}\right)\left(\frac{\alpha^{2}}{\alpha-1}\right)\frac{m}{n^{\prime}+1}$
$\displaystyle\leq
C_{0}\left(\frac{\theta^{2}}{(1-2\theta)^{4}}\right)\left(\frac{\alpha^{2}}{\alpha-1}\right)\frac{m}{n},$
(5)

for some $C_{0}>0$ large enough. Finally, since Rényi divergence is increasing
with $\alpha$, we also have for $\alpha<2$,

$\displaystyle\max_{p_{1},...,p_{n},p_{1}^{\prime}}D_{\alpha}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right)$
$\displaystyle\leq\max_{p_{1},...,p_{n},p_{1}^{\prime}}D_{2}\left(P_{Y_{1}+Y_{2}+...+Y_{n}}\middle\|P_{Y^{\prime}_{1}+Y_{2}+...+Y_{n}}\right)$
$\displaystyle\leq
C_{0}\left(\frac{\theta^{2}}{(1-2\theta)^{4}}\right)\frac{4m}{n}.$ (6)

Combining (3.1) and (3.1), we establish Theorem 3.3.

##  4 The Multi-dimensional PBM

Next, we extend the scalar PBM into the multi-dimensional setting, where
$x_{i}\in\mathbb{R}^{d}$ and $\left\lVert x_{i}\right\rVert_{2}\leq c$. The
description of multi-dimensional PBM is given in Algorithm 1. The key step
that allows us to cast the multi-dimensional DME into the scalar one is via
Kashin’s representation, which transforms the $\ell_{2}$ geometry of the data
into an $\ell_{\infty}$ geometry and hence enables us to decompose the problem
into scalar sub-tasks.

###  4.1 Kashin’s representation

We first introduce the idea of a tight frame in Kashin’s representation. A
tight frame is a set of vectors
$\left\\{u_{j}\right\\}^{D}_{j=1}\in\mathbb{R}^{d}$ that satisfy Parseval’s
identity, i.e. $\left\|x\right\|^{2}_{2}=\sum_{j=1}^{D}\langle
u_{j},x\rangle^{2}\,\text{ for all }x\in\mathbb{R}^{d}.$

A frame can be viewed as a generalization of the notion of an orthogonal basis
in $\mathbb{R}^{d}$ for $D>d$. To increase robustness, we wish the information
to be spread evenly across different coefficients, which motivates the
following definition of a Kashin’s representation:

######  Definition 4.1 (Kashin’s representationKashin (1977)).

For a set of vectors $\left\\{u_{j}\right\\}_{j=1}^{D}$, we say the expansion

$x=\sum_{j=1}^{D}a_{j}u_{j},\text{ with }\max_{j}\left\lvert
a_{j}\right\rvert\leq\frac{K}{\sqrt{D}}\left\lVert x\right\rVert_{2}$

is a Kashin’s representation of vector $x$ at level $K$ .

By Theorem 3.5 and Theorem 4.1 in Lyubarskii & Vershynin (2010), we have the
following lemma:

######  Lemma 4.2 (Uncertainty principle).

There exists a tight frame $U=[u_{1},...,u_{D}]$ with (1) $D=\Theta(d)$ and
(2) Kashin’s level $K=O\left(1\right)$.

Lemma 4.2 implies that for each $x_{i}\in\mathbb{R}^{d}$ such that
$\left\lVert x_{i}\right\rVert_{2}\leq 1$, one can always represent each
$x_{i}$ with coefficients
$y_{i}\in[-\gamma_{0}/\sqrt{d},\gamma_{0}/\sqrt{d}]^{\gamma_{1}d}$ for some
$\gamma_{0},\gamma_{1}>0$ and $x_{i}=Uy_{i}$.

###  4.2 Proof of Theorem 2.1

With Lemma 4.2, we are well-prepared to analyze the performance of Algorithm
1. Recall that the three main steps in the multi-dimensional PBM are:

  1. 1.

(Clients) compute a Kashin’s representation of $x_{i}$ with respect to a
(common) tight frame $U$ (denoted as $y_{i}$).

  2. 2.

(Clients) sequentially transmit each coordinate of $y_{i}$ via the scalar PBM.

  3. 3.

(Server) reconstructs $\mu$ by $\hat{\mu}=U\hat{\mu}_{y}$.

Let us denote $y_{i}(j)$ as the $j$-th coordinate of $y_{i}$ for
$j\in[\gamma_{1}d]$, and $\mu_{y}(j)$ as the $j$-th coordinate of
$\mu_{y}=\frac{1}{n}\sum_{i=1}^{n}y_{i}$. Due to the property of the Kashin’s
representation, we know that if $\left\lVert x_{i}\right\rVert_{2}\leq c$,
$\left\lVert y_{i}\right\rVert_{\infty}\leq\frac{\gamma_{0}c}{\sqrt{d}}$.

Therefore, using the scalar PBM (with parameters $\theta,m$) for coordinate
$j$ and applying Theorem 3.3, it holds that

  * •

the privacy loss is
$\varepsilon_{\mathsf{j}}(\alpha)=C_{0}\left(\frac{\theta^{2}}{(1-2\theta)^{4}}\right)\frac{\alpha
m}{n}$;

  * •

$\mathbb{E}\left[\hat{\mu}_{y}(j)\right]=\hat{\mu}_{y}(i)$ and
$\mathbb{E}\left[\left(\hat{\mu}_{y}(j)-\mu_{j}\right)^{2}\right]\leq\frac{\gamma^{2}_{0}c^{2}}{4dnm\theta};$

  * •

The communication cost is $O\left(\log n+\log m\right)$ bits.

Repeating for $j=1,..,\gamma_{1}d$ and accounting the overall privacy loss via
the composition theorem of RDP (Mironov, 2017, Proposition 1), the end-to-end
RDP guarantee of Algorithm 2 becomes
$\varepsilon(\alpha)=\sum_{j}\varepsilon_{j}(\alpha)=\gamma_{1}C_{0}\frac{d\alpha
m\theta^{2}}{(1-2\theta)^{4}n}.$ Similarly, the communication cost is
$\gamma_{1}d\left(\log n+\log m\right)$ bits. Finally, we control the
$\ell_{2}$ estimation error
$\mathbb{E}\left[\left\lVert\mu-\hat{\mu}\right\rVert^{2}_{2}\right]$. Note
that since $x_{i}=Uy_{i}$ for all $i=1,...,n$, we have
$\mu_{x}=\frac{1}{n}\sum_{i}Uy_{i}=U\mu_{y}.$ Also,

$\displaystyle\mathbb{E}\left[\left(\hat{\mu}-\mu\right)^{2}\right]=\mathbb{E}\left[\left\lVert\sum\nolimits_{j}\left(\hat{\mu}_{y}(j)-\mu_{y}(j)\right)u_{j}\right\rVert_{2}^{2}\right]$
$\displaystyle\overset{\text{(a)}}{\leq}\mathbb{E}\left[\sum\nolimits_{j}\left(\hat{\mu}_{y}(j)-\mu_{y}(j)\right)^{2}\right]=\mathbb{E}\left[\left\lVert\hat{\mu}_{y}-\mu_{y}\right\rVert_{2}^{2}\right],$

where (a) is due to the Cauchy–Schwarz inequality. Hence to bound the MSE of
$\hat{\mu}$, it suffices to bound
$\mathbb{E}\left[\|\hat{\mu}_{y}-\mu_{y}\|^{2}_{2}\right]\leq\gamma_{1}\gamma_{0}^{2}\frac{c^{2}}{4mn\theta}=O\left(\frac{c^{2}}{4mn\theta}\right).$

##  5 Empirical evaluations

In this section, we evaluate PBM on the distributed mean estimation (DME)
task. We follow the set-up of Kairouz et al. (2021); Agarwal et al. (2021): we
generate $n=1000$ client vectors with dimension $d=250$, i.e.,
$x_{1},...,x_{n}\in\mathbb{R}^{250}$ . Each local vector has bounded
$\ell_{2}$ and $\ell_{\infty}$ norms, i.e. $\left\lVert
x_{i}\right\rVert_{2}\leq 1$ and $\left\lVert
x_{i}\right\rVert_{\infty}\leq\frac{1}{\sqrt{d}}$444We perform the experiments
under an $\ell_{\infty}$ geometry. Under $\ell_{2}$ geometry, one can either
apply random rotation and $\ell_{\infty}$ clipping, or compute the Kashin’s
representation, as discussed in Section 4.. Our goal is to demonstrate that
the utility of PBM matches that of the continuous Gaussian mechanism under the
same privacy guarantees when given sufficient communication budget.

In Figure 3, we apply PBM with different $m$’s (which dictate the
communication cost) under a given privacy requirement $\varepsilon$. Note that
once $m$ is determined, the field that SecAgg operates on will be
$\mathbb{Z}_{2^{\lceil\log_{2}(n\cdot m)\rceil}}$ and hence the communication
cost becomes $\lceil\log_{2}(n\cdot m)\rceil$ bits.

Figure 3: A comparison of PBM with the continuous Gaussian mechanism. We set
$m=\\{2,4,6,16\\}$, and the corresponding communication costs (i.e., the
logarithmic of the field size that SecAgg operates on) are
$B=\\{11,12,13,14\\}$.

#### Reducing communication via modular clipping.

Since the sum of encoded messages (i.e., $\sum Z_{i}$ in Algorithm 2) follows
a Poisson-binomial distribution with
$p_{i}\in\left[\frac{1}{2}-\theta,\frac{1}{2}+\theta\right]$, with high-
probability, $\sum
Z_{i}\in\left[\frac{nm(1-\theta)}{2}-c\sqrt{\frac{nm}{4}},\frac{nm(1+\theta)}{2}+c\sqrt{\frac{nm}{4}}\right]$
(where $c$ is a parameter used to control the failure probability). Therefore
one can (modularly) clip local message in that range to further reduce and
hence communication cost the field size to $nm\theta+c\sqrt{nm}$ (this,
however, will incur _bias_ to the final estimator). In Figure 4, we perform
PBM with modular clipping and set $c=\sqrt{30}$. Since $c$ is large enough, we
observe almost no impact to the errors while saving the (per-parameter)
communication by $1$ bit.

Figure 4: PBM with modular clipping, where $m=\\{2,4,6,16\\}$. We set the
modular clippiing parameter $c=\sqrt{30}$ and report the MSEs and the
corresponding communication cost.

##  6 Application to private SGD

In this section, we apply PBM to distributed SGD. In each round, the server
samples $n$ out of $N$ clients randomly, each (sampled) client computes a
local gradient from its data, and the server aggregates the mean of the local
gradients via PBM. Since PBM ensures distributed DP, we call the resulting
scheme DDP-SGD.

We summarize DDP-SGD in Algorithm 3, in which we use
$\mathsf{PBM}_{\texttt{enc}}$ to denote the clients’ procedure in Algorithm 1
(which includes computing Kashin’s representation, sequentially applying the
scalar PBM, and performing SecAgg) and $\mathsf{PBM}_{\texttt{dec}}$ to denote
the server’s procedure.

Algorithm 3 Distributed DP-SGD

Input: Clients data set $d_{1},...,d_{N}\in\mathcal{D}$, PBM parameters
$(\theta,m)$, loss function $\ell(d,w)$.

Goal: Compute
$w_{T}\approx\arg\min_{w}\sum_{i=1}^{N}\ell\left(d_{i},w\right)$.

Server generates an initial model weights $w_{0}\in\mathbb{W}$

for iteration $t=1,...,T$ do

Server samples a subset of $n$ clients $\mathcal{C}_{t}\subset[N]$ and
broadcasts $w_{t-1}$ to them.

for each client $i\in\mathcal{C}_{t}$ do

Computes
$g^{t}_{i}=\mathsf{Clip}_{\ell_{2},c}\left(\nabla\ell\left(d_{i},w_{t-1}\right)\right)$

Computes $Z^{t}_{i}=\mathsf{PBM}_{\texttt{enc}}\left(g^{t}_{i}\right)$

Send $Z^{t}_{i}$ to the server via SecAgg

end for

(Server) decodes
$\hat{\mu}^{t}_{g}=\mathsf{PBM}_{\texttt{dec}}\left(\sum_{i}Z_{i}^{t}\right)$.

(Server) updates the model by $w_{t}=w_{t-1}+\gamma\hat{\mu}^{t}_{g}$.

end for

Return: $w_{T}$

#### Analysis of convergence rates.

Next, we analyze the convergence rate of Algorithm 3. Due to the unbiased
nature of PBM, one can easily control the convergence rate of DDP-SGD by the
variance of PBM through the following lemma (which originates from Ghadimi &
Lan (2013) but we use a version adapted from Agarwal et al. (2018)):

######  Lemma 6.1 (Corollary 1 in Agarwal et al. (2018)).

Assume $F(w)\triangleq\frac{1}{N}\sum_{i=1}^{N}\ell(w;d_{i})$, where
$\ell(\cdot,d)$ is an $L$-smooth and $c$-Lipschitz function for all
$d\in\mathcal{D}$. Let $w_{0}$ satisfies
$F\left(w_{0}\right)-F\left(w^{*}\right)\leq D_{F}$. Let $\hat{\mu}^{t}_{g}$
be the noisy model updates at round $t$ and let the learning rate
$\gamma\triangleq\min\left\\{L^{-1},\sqrt{2D_{F}}\left(\sigma\sqrt{LT}\right)^{-1}\right\\}$.
Then after $T$ rounds,

$\mathbb{E}_{t\sim\mathsf{unif}(T)}\left[\left\lVert\nabla
F(w_{t})\right\rVert^{2}_{2}\right]\leq\frac{2D_{F}L}{T}+\frac{2\sqrt{2}\sigma\sqrt{LD_{F}}}{\sqrt{T}}+cB,$

$\displaystyle\text{where }\sigma^{2}=2\Big{(}$ $\displaystyle\max_{1\leq
t\leq T}\mathbb{E}\left[\left\lVert\mu_{g}^{t}-\nabla
F(w_{t})\right\rVert^{2}_{2}\right]$ $\displaystyle\hskip
50.00008pt+\max_{1\leq t\leq
T}\mathbb{E}_{Q}\left[\left\lVert\mu_{g}^{t}-\tilde{\mu}_{g}^{t}\right\rVert^{2}_{2}\right]\Big{)},$

and $B=\max_{1\leq t\leq
T}\left\lVert\mathbb{E}_{Q}\left[\mu_{g}^{t}-\hat{\mu}_{g}^{t}\right]\right\rVert_{2}.$

Note that in each round, (1) $\mu^{t}_{g}$ (the true mean of (the sampled)
clients’ gradients) is an unbiased estimator of $\nabla F(w_{t})$ (because
clients are sampled uniformly at random), and (2) $\hat{\mu}^{t}_{g}$ is an
unbiased estimator of $\mu^{t}_{g}$ since PBM is unbiased555Notice that the
clipping step in Algorithm 3 does not increase bias since by the Lipschitz
condition, $\left\lVert\nabla\ell\right\rVert_{2}\leq c$.. This implies $B=0$
and
$\sigma^{2}=\max_{t}\mathsf{Var}\left(\mu_{g}^{t}\right)+\mathsf{Var}\left(\hat{\mu}_{g}^{t}\middle|\mu_{g}^{t}\right)$,
where the first term is bounded by $c^{2}$, and applying Theorem 2.1, we can
bound the second
$\mathsf{Var}\left(\hat{\mu}_{g}^{t}\middle|\mu_{g}^{t}\right)$ by
$\frac{c^{2}}{4nm\theta^{2}}$. Thus we arrive at the following conclusion:

######  Corollary 6.2 (Convergence of DDP-SGD).

Under the same assumptions of Lemma 6.1, after $\tau\sim\mathsf{uniform}(T)$
iterations, the output of Algorithm 3 satisfies

$\mathbb{E}_{\tau}\left[\left\lVert\nabla
F(w_{\tau})\right\rVert^{2}_{2}\right]\leq\frac{LD_{F}}{T}+\frac{\sqrt{8c^{2}LD_{F}}}{\sqrt{T}}\sqrt{1+\frac{1}{4nm\theta^{2}}}.$

######  Remark 6.3.

Note that due to the convergence guarantees of Lemma 6.1, in Corollary 6.2 we
apply Algorithm 3 with a random stopping time.

#### Accounting for total privacy loss.

To account for the total privacy loss, we first note that the per-round RDP
guarantee is amplified by the sub-sampling of the clients with sampling rate
$\kappa=\frac{n}{N}$. To quantify the tight amplification rate, one can apply
(Wang et al., 2019, Theorem 9) and obtain a non-asymptotic upper bound on
$\varepsilon_{\mathsf{sampled}}(\alpha)$. For instance, (Wang et al., 2019,
Theorem 9) shows that when $\alpha$ is not too large (e.g., when $\alpha\leq
2$),
$\varepsilon_{\mathsf{sampled}}(\alpha)=O\left(\kappa^{2}\varepsilon(\alpha)\right)$.
Applying Theorem 2.1 and plugging
$\varepsilon(\alpha)=\frac{dm\theta^{2}\alpha}{n}$ in this bound, we have
$\varepsilon_{\mathsf{sampled}}(\alpha)=O\left(\frac{ndm\theta^{2}\alpha}{N^{2}}\right).$
To account for the privacy loss over all the $T$ iterations, we apply the
composition theorem for RDP (Mironov, 2017, Proposition 1), concluding that
Algorithm 3 satisfies $\left(\alpha,\varepsilon_{\mathsf{final}}\right)$ with
$\varepsilon_{\mathsf{final}}(\alpha)=O\left(\frac{ndm\theta^{2}\alpha
T}{N^{2}}\right)$ when $\alpha\leq 2$ .

For high-privacy (where $nm\theta^{2}\ll 1$) and small $\alpha$ regimes, we
obtain a convergence rate-privacy trade-off:

$\mathbb{E}_{\tau}\left[\left\lVert\nabla
F(w_{\tau})\right\rVert^{2}_{2}\right]\approx
O\left(\sqrt{\frac{c^{2}d\alpha}{N^{2}\varepsilon_{\mathsf{final}}\left(\alpha\right)}}\right).$

This achieves the optimal rate of reported in (Bassily et al., 2014, Table 1)
(though admittedly, our results only hold for high privacy regime and for
$\alpha<2$). Finally, we remark to obtain non-asymptotic trade-offs for full
$\alpha>1$ regimes, one has to resort to (Wang et al., 2019, Theorem 9).

##  7 Conclusion

In this paper, we present the Poisson Binomial mechanism, a discrete (Rényi)
DP mechanism that can be combined with SecAgg for distributed mean estimation
or federated learning/analytics. Unlike previous schemes, our mechanism is not
based on additive noise, so in addition to achieving the optimal privacy-
accuracy trade-off, it offers two extra advantages: (1) it results in an
unbiased estimator, and (2) the communication cost with SecAgg decreases with
the privacy budget $\varepsilon$. Leveraging the unbiasedness property, we
propose a distributed DP-SGD algorithm and analyze its convergence rate.
Several important open problems include deriving a lower bound on the
communication cost for DME with DP and SecAgg, and evaluating our scheme on
real-world FL datasets.

## Acknowledgments

This work was supported in part by NSF Award # NeTS-1817205 and CCF-2213223, a
Google Faculty research award, and a National Semiconductor Corporation
Stanford Graduate Fellowship. The authors would like to thank Thomas Steinke
for an inspiring discussion in the early stage of this work, and Graham
Cormode for pointing out the connection of PBM to Cheu et al. (2019) and
insightful comments on an earlier draft of this paper.

## References

  * Agarwal et al. (2018) Agarwal, N., Suresh, A. T., Yu, F. X. X., Kumar, S., and McMahan, B.  cpsgd: Communication-efficient and differentially-private distributed sgd.  In _Advances in Neural Information Processing Systems_ , pp. 7564–7575, 2018.
  * Agarwal et al. (2021) Agarwal, N., Kairouz, P., and Liu, Z.  The skellam mechanism for differentially private federated learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Asoodeh et al. (2020) Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., and Sankar, L.  A better bound gives a hundred rounds: Enhanced privacy guarantees via f-divergences.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pp. 920–925. IEEE, 2020.
  * Bassily et al. (2014) Bassily, R., Smith, A., and Thakurta, A.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pp. 464–473. IEEE, 2014.
  * Bell et al. (2020) Bell, J. H., Bonawitz, K. A., Gascón, A., Lepoint, T., and Raykova, M.  Secure single-server aggregation with (poly) logarithmic overhead.  In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 1253–1269, 2020.
  * Bonawitz et al. (2016a) Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K.  Practical secure aggregation for federated learning on user-held data.  _arXiv preprint arXiv:1611.04482_ , 2016a.
  * Bonawitz et al. (2016b) Bonawitz, K. A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K.  Practical secure aggregation for federated learning on user-held data.  In _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016b.  URL https://arxiv.org/abs/1611.04482.
  * Bun & Steinke (2016) Bun, M. and Steinke, T.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In _Theory of Cryptography Conference_ , pp. 635–658. Springer, 2016.
  * Caldas et al. (2018) Caldas, S., Konečny, J., McMahan, H. B., and Talwalkar, A.  Expanding the reach of federated learning by reducing client resource requirements.  _arXiv preprint arXiv:1812.07210_ , 2018.
  * Canonne et al. (2020) Canonne, C. L., Kamath, G., and Steinke, T.  The discrete gaussian for differential privacy.  _arXiv preprint arXiv:2004.00010_ , 2020.
  * Carlini et al. (2019) Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., and Song, D.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In _28th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 19)_, pp. 267–284, 2019.
  * Chen et al. (2020) Chen, W.-N., Kairouz, P., and Ozgur, A.  Breaking the communication-privacy-accuracy trilemma.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Cheu et al. (2019) Cheu, A., Smith, A., Ullman, J., Zeber, D., and Zhilyaev, M.  Distributed differential privacy via shuffling.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pp. 375–403. Springer, 2019.
  * Duchi et al. (2013) Duchi, J. C., Jordan, M. I., and Wainwright, M. J.  Local privacy and statistical minimax rates.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pp. 429–438. IEEE, 2013.
  * Dwork et al. (2006a) Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pp. 486–503. Springer, 2006a.
  * Dwork et al. (2006b) Dwork, C., McSherry, F., Nissim, K., and Smith, A.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pp. 265–284. Springer, 2006b.
  * Dwork et al. (2010) Dwork, C., Rothblum, G. N., and Vadhan, S.  Boosting and differential privacy.  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , pp. 51–60. IEEE, 2010.
  * Evfimievski et al. (2004) Evfimievski, A., Srikant, R., Agrawal, R., and Gehrke, J.  Privacy preserving mining of association rules.  _Information Systems_ , 29(4):343–364, 2004.
  * Feldman et al. (2017) Feldman, V., Guzman, C., and Vempala, S.  Statistical query algorithms for mean vector estimation and stochastic convex optimization.  In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pp. 1265–1277. SIAM, 2017.
  * Geyer et al. (2017) Geyer, R. C., Klein, T., and Nabi, M.  Differentially private federated learning: A client level perspective.  _arXiv preprint arXiv:1712.07557_ , 2017.
  * Ghadimi & Lan (2013) Ghadimi, S. and Lan, G.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.
  * Ghazi et al. (2021) Ghazi, B., Golowich, N., Kumar, R., Pagh, R., and Velingker, A.  On the power of multiple anonymous messages: Frequency estimation and selection in the shuffle model of differential privacy.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pp. 463–488. Springer, 2021.
  * Kairouz et al. (2016) Kairouz, P., Bonawitz, K., and Ramage, D.  Discrete distribution estimation under local privacy.  In _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48, pp. 2436–2444, New York, New York, USA, 20–22 Jun 2016\.
  * Kairouz et al. (2019) Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Kairouz et al. (2021) Kairouz, P., Liu, Z., and Steinke, T.  The distributed discrete gaussian mechanism for federated learning with secure aggregation.  _arXiv preprint arXiv:2102.06387_ , 2021.
  * Kashin (1977) Kashin, B.  Section of some finite-dimensional sets and classes of smooth functions (in russian) izv.  _Acad. Nauk. SSSR_ , 41:334–351, 1977.
  * Kasiviswanathan et al. (2011) Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A.  What can we learn privately?  _SIAM Journal on Computing_ , 40(3):793–826, 2011\.
  * Lyubarskii & Vershynin (2010) Lyubarskii, Y. and Vershynin, R.  Uncertainty principles and vector quantization.  _IEEE Transactions on Information Theory_ , 56(7):3491–3501, 2010.
  * McMahan et al. (2016) McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Arcas, B.  Communication-efficient learning of deep networks from decentralized data (2016).  _arXiv preprint arXiv:1602.05629_ , 2016.
  * McMahan et al. (2017) McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L.  Learning differentially private recurrent language models.  _arXiv preprint arXiv:1710.06963_ , 2017.
  * Melis et al. (2019) Melis, L., Song, C., De Cristofaro, E., and Shmatikov, V.  Exploiting unintended feature leakage in collaborative learning.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pp. 691–706. IEEE, 2019.
  * Mironov (2012) Mironov, I.  On significance of the least significant bits for differential privacy.  In _Proceedings of the 2012 ACM conference on Computer and communications security_ , pp. 650–661, 2012.
  * Mironov (2017) Mironov, I.  Rényi differential privacy.  In _2017 IEEE 30th Computer Security Foundations Symposium (CSF)_ , pp. 263–275. IEEE, 2017.
  * Shokri et al. (2017) Shokri, R., Stronati, M., Song, C., and Shmatikov, V.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pp. 3–18. IEEE, 2017.
  * Song & Shmatikov (2019) Song, C. and Shmatikov, V.  Auditing data provenance in text-generation models.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 196–206, 2019.
  * Song et al. (2013) Song, S., Chaudhuri, K., and Sarwate, A. D.  Stochastic gradient descent with differentially private updates.  In _2013 IEEE Global Conference on Signal and Information Processing_ , pp. 245–248. IEEE, 2013.
  * Suresh et al. (2017) Suresh, A. T., Yu, F. X., Kumar, S., and McMahan, H. B.  Distributed mean estimation with limited communication.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, pp. 3329–3337. JMLR.org, 2017.
  * Van Erven & Harremos (2014) Van Erven, T. and Harremos, P.  Rényi divergence and kullback-leibler divergence.  _IEEE Transactions on Information Theory_ , 60(7):3797–3820, 2014.
  * Vershynin (2018) Vershynin, R.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wang et al. (2019) Wang, Y.-X., Balle, B., and Kasiviswanathan, S. P.  Subsampled rényi differential privacy and analytical moments accountant.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 1226–1235. PMLR, 2019.
  * Warner (1965) Warner, S. L.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.

##  Appendix A Conversion of RDP to approximate DP

The following conversion lemma from Asoodeh et al. (2020); Canonne et al.
(2020); Bun & Steinke (2016) relates RDP to
$\left(\varepsilon_{\mathsf{DP}}(\delta),\delta\right)$-DP.

######  Lemma A.1.

If $M$ satisfies $\left(\alpha,\varepsilon(\alpha)\right)$-RDP for all
$\alpha>1$, then, for any $\delta>0$, $M$ satisfies
$\left(\varepsilon_{\mathsf{DP}}(\delta),\delta\right)$-DP, where

$\varepsilon_{\mathsf{DP}}(\delta)=\inf_{\alpha>1}\varepsilon(\alpha)+\frac{\log\left(1/\alpha\delta\right)}{\alpha-1}+\log(1-1/\alpha).$

To compare the privacy-utility trade-off of our mechanism with previous works,
it will be useful sometimes to convert the stronger RDP guarantees to an
approximate DP guarantee. The following lemma, which is a simple application
of Lemma A.1, provides a simple form for the resulting approximate DP
guarantees.

######  Lemma A.2.

If $M$ satisfies $\left(\alpha,\varepsilon(\alpha)\right)$-RDP for all
$\alpha>1$, then, for any $\delta>0$, $M$ satisfies
$\left(\varepsilon_{\mathsf{DP}}(\delta),\delta\right)$-DP, where

$\varepsilon_{\mathsf{DP}}(\delta)=\Theta\left(\sqrt{\left(\sup_{\alpha}\frac{\varepsilon(\alpha)}{\alpha}\right)\log(1/\delta)}\right).$

##  Appendix B Additional plots

Figure 5:  Privacy-MSE (variance) trade-offs of PBM and the Gaussian
mechanism.

#### Numerical evaluation of the scalar PBM.

In figure 5, we compute the privacy guarantee of Algorithm 1 and compared it
with the Gaussian mechanism. For the PBM, we fix $\theta$, vary parameter m,
and compute the corresponding Rényi DP (i.e., $\varepsilon(\alpha)$) and MSE.
We see that as $\theta\rightarrow 0$, the privacy-MSE curve converges to that
of the Gaussian mechanism fast.

##  Appendix C Additional Proofs

###  C.1 Proof of Lemma A.2

$\displaystyle\varepsilon_{\mathsf{DP}}(\delta)$
$\displaystyle\leq\varepsilon(\alpha)+\frac{\log\left(1/\alpha\delta\right)}{\alpha-1}+\log(1-1/\alpha)$
$\displaystyle\leq\varepsilon(\alpha)+\frac{\log(1/\delta)}{\alpha-1}$
$\displaystyle=\frac{\varepsilon(\alpha)}{\alpha}+\frac{\varepsilon(\alpha)}{\alpha}(\alpha-1)+\frac{\log(1/\delta)}{\alpha-1}.$

Next, take
$\alpha^{*}=1+\sqrt{\sup_{\alpha}\frac{\alpha}{\varepsilon(\alpha)}}$, we get

$\varepsilon_{\mathsf{DP}}(\delta)\leq\sup_{\alpha}\frac{\varepsilon(\alpha)}{\alpha}+2\sqrt{\left(\sup_{\alpha}\frac{\varepsilon(\alpha)}{\alpha}\right)\log(1/\delta)}=\Theta\left(\sqrt{\left(\sup_{\alpha}\frac{\varepsilon(\alpha)}{\alpha}\right)\log(1/\delta)}\right),$

if $\frac{\varepsilon(\alpha)}{\alpha}=O(1)$. This suggests that
$(\alpha,\varepsilon(\alpha))$-RDP implies
$(\varepsilon_{\mathsf{DP}}(\delta),\delta)$-DP with
$\varepsilon_{\mathsf{DP}}(\delta)=\Theta_{\delta}\left(\sqrt{\left(\sup_{\alpha}\frac{\varepsilon(\alpha)}{\alpha}\right)}\right)$.

###  C.2 Proof of Lemma 3.5

To see this, observe that
$P_{X_{1}+X_{2}+...+X_{n}}=P_{X_{1}+...+X_{n-1}}\circ P_{X_{n}}$, where
$\circ$ denotes the convolution operator. Since the convolution operator is
linear, we have

$P_{X_{1}+...+X_{n-1}}\circ
P_{X_{n}}=\lambda\left(P_{X_{1}+...+X_{n-1}}\circ\mathsf{Ber}\left(\frac{1}{2}-\theta\right)\right)+(1-\lambda)\left(P_{X_{1}+...+X_{n-1}}\circ\mathsf{Ber}\left(\frac{1}{2}+\theta\right)\right),$

where $\lambda>0$ is such that
$p_{n}=\lambda\left(\frac{1}{2}-\theta\right)+(1-\lambda)\left(\frac{1}{2}+\theta\right)$.
By the quasi-convexty of $D_{\alpha}(\cdot\|\cdot)$, it holds that
$D_{\alpha}\left(P_{X_{1}+X_{2}+...+X_{n}}\middle\|P_{X^{\prime}_{1}+X_{2}+...+X_{n}}\right)$
is upper bounded by

$\max\left(D_{\alpha}\left(P_{X_{1}+X_{2}+...+\mathsf{Ber}\left(\frac{1}{2}-\theta\right)}\middle\|P_{X^{\prime}_{1}+X_{2}+...+\mathsf{Ber}\left(\frac{1}{2}-\theta\right)}\right),D_{\alpha}\left(P_{X_{1}+X_{2}+...+\mathsf{Ber}\left(\frac{1}{2}+\theta\right)}\middle\|P_{X^{\prime}_{1}+X_{2}+...+\mathsf{Ber}\left(\frac{1}{2}+\theta\right)}\right)\right).$

By repetitively applying the quasi-convexity and the extrema argument for
$n-1$ times, we arrive at

$\displaystyle
D_{\alpha}\left(P_{X_{1}+X_{2}+...+X_{n}}\middle\|P_{X^{\prime}_{1}+X_{2}+...+X_{n}}\right)\leq\max_{k\in[n-1]}D_{\alpha}\left(P_{X_{1}+N_{k}}\middle\|P_{X^{\prime}_{1}+N_{k}}\right),$

where
$N_{k}\sim\mathsf{Binom}(k,\frac{1}{2}-\theta)+\mathsf{Binom}(n-k-1,\frac{1}{2}+\theta)$.

In the last step, by making use of the _joint_ quasi-convexity of Rényi
divergence (i.e., $(P,Q)\mapsto D_{\alpha}(P\|Q)$ is quasi-convex), it
suffices to show that

$\displaystyle\left(P_{X_{1}+N_{k}},P_{X^{\prime}_{1}+N_{k}}\right)=\lambda^{*}_{1}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}},P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}}\right)$
$\displaystyle+\lambda^{*}_{2}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}},P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}}\right)+\lambda^{*}_{3}\Big{(}P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}},$
$\displaystyle
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}}\Big{)}+\lambda^{*}_{4}\left(P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}},P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}}\right)$

for some $\lambda^{*}_{i}\in[0,1]$ and $\sum_{i=1}^{4}\lambda^{*}_{i}=1$. To
this end, since $X_{i}\sim\mathsf{Ber}(p_{i})$ and
$X^{\prime}_{i}\sim\mathsf{Ber}(p^{\prime}_{i})$ for some
$p_{i},p^{\prime}_{i}\in\left[\frac{1}{2}-\theta,\frac{1}{2}+\theta\right]$,
we must have

$P_{X_{1}+N_{k}}=\lambda
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}}+(1-\lambda)P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}},\text{
and}$
$P_{X^{\prime}_{1}+N_{k}}=\lambda^{\prime}P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+N_{k}}+(1-\lambda^{\prime})P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+N_{k}}$

for some $\lambda,\lambda^{\prime}\in[0,1]$. Therefore, by setting
$\lambda_{1}^{*}=\lambda\lambda^{\prime}$,
$\lambda_{2}^{*}=\lambda(1-\lambda^{\prime})$,
$\lambda_{3}^{*}=(1-\lambda)\lambda^{\prime}$, and
$\lambda_{4}^{*}=(1-\lambda)(1-\lambda^{\prime})$, we arrive at the desired
result.

###  C.3 Proof of Lemma 3.6

$\displaystyle
P_{\mathsf{Binom}\left(1+k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}=P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}\circ
P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)}$ $\displaystyle
P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}=P_{\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}\circ
P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)},$

and by a data processing inequality, we have

$\displaystyle
D_{\alpha}\left(P_{\mathsf{Binom}\left(1+k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq
D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq
D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\right),$

where in the last inequality we use a data processing inequality and define
$n^{\prime}=\lceil\frac{n-1}{2}\rceil$. Similarly, when $k^{*}>\frac{n}{2}$,
we decompose

$\displaystyle
P_{\mathsf{Binom}\left(1+k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}=P_{\mathsf{Binom}\left(1+k^{*},\frac{1}{2}-\theta\right)}\circ
P_{\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}$ $\displaystyle
P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}=P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)}\circ
P_{\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}.$

By a data processing inequality, we obtain

$\displaystyle
D_{\alpha}\left(P_{\mathsf{Binom}\left(1+k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*}-1,\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(k^{*},\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k^{*},\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq
D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}-\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}-\theta\right)}\right).$

Therefore we conclude that (4) can be upper bounded by

$\displaystyle\max_{k\in[n-1]}D_{\alpha}\left(P_{\mathsf{Binom}\left(1+k,\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k-1,\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(k,\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n-k,\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq\max\Big{(}\underbrace{D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\right)}_{\text{(a)}}\Big{)},$
$\displaystyle\hskip
60.00009pt\underbrace{D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}-\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}+\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}-\theta\right)}\right)}_{\text{(b)}}.$
(7)

###  C.4 Proof of Lemma 3.7

Using the inequality $t\leq e^{t-1}$, we have

$\displaystyle D_{\alpha}\left(P\middle\|Q\right)$
$\displaystyle=\frac{1}{\alpha-1}\log\left(\mathbb{E}_{Q}\left[\left(\frac{dP}{dQ}\left(X\right)\right)^{\alpha}\right]\right)$
$\displaystyle\leq\frac{1}{\alpha-1}\log\left(\mathbb{E}_{Q}\left[e^{\alpha\left(\frac{dP}{dQ}\left(X\right)-1\right)}\right]\right)$
$\displaystyle\leq\frac{1}{\alpha-1}\log\left(\mathbb{E}_{Q}\left[e^{\alpha\left(\frac{dP}{dQ}\left(X\right)-1\right)}\right]\right)$
$\displaystyle\overset{\text{(a)}}{\leq}\frac{1}{\alpha-1}\log\left(e^{C_{0}\alpha^{2}\left\lVert\frac{dP}{dQ}\left(X\right)-1\right\rVert^{2}_{\psi_{2}}}\right)$
$\displaystyle=C_{0}\frac{\alpha^{2}}{\alpha-1}\left\lVert\frac{dP}{dQ}\left(X\right)-1\right\rVert^{2}_{\psi_{2}},$

where (a) holds for any sub-gaussian random variable (see, for instance,
Vershynin (2018, Proposition 2.5.2), which states that for a zero-mean random
variable $Z$ with finite sub-gaussian norm, $\mathbb{E}\left[e^{\alpha
Z}\right]\leq e^{C_{0}\alpha^{2}\left\lVert Z\right\rVert^{2}_{\psi_{2}}}$).

###  C.5 Proof of Lemma 3.8

#### Bounding (a)

For notational simplicity, we denote the LR of term (a) in (C.3) as $R(i)$ for
$i\in[n^{\prime}+1]$ and bound it as follows.

$\displaystyle R(i)$
$\displaystyle\triangleq\frac{P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}(i)}{P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}(i)}$
$\displaystyle=\frac{{n^{\prime}\choose
i}\left(\frac{1}{2}+\theta\right)^{i+1}\left(\frac{1}{2}-\theta\right)^{n^{\prime}-i}}{{n^{\prime}+1\choose
i}\left(\frac{1}{2}+\theta\right)^{i}\left(\frac{1}{2}-\theta\right)^{n^{\prime}+1-i}}+\frac{{n^{\prime}\choose
i-1}\left(\frac{1}{2}+\theta\right)^{i}\left(\frac{1}{2}-\theta\right)^{n^{\prime}-i+1}}{{n^{\prime}+1\choose
i}\left(\frac{1}{2}+\theta\right)^{i}\left(\frac{1}{2}-\theta\right)^{n^{\prime}+1-i}}$
$\displaystyle=\left(\frac{n^{\prime}+1-i}{n^{\prime}+1}\right)\left(\frac{1-2\theta}{1+2\theta}\right)+\left(\frac{i}{n^{\prime}+1}\right)\left(\frac{1+2\theta}{1-2\theta}\right)$
$\displaystyle=\left(\frac{1-2\theta}{1+2\theta}\right)+\frac{i}{n^{\prime}+1}\left(\left(\frac{1+2\theta}{1-2\theta}\right)-\left(\frac{1-2\theta}{1+2\theta}\right)\right)$
$\displaystyle=\left(\frac{1-2\theta}{1+2\theta}\right)+\frac{i}{n^{\prime}+1}\left(\frac{8\theta}{1-4\theta^{2}}\right).$

When $I\sim P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}$,
$I-\mathbb{E}[I]$ has a sub-gaussian norm $\left\lVert
I-\mathbb{E}[I]\right\rVert^{2}_{\psi_{2}}\leq\sigma^{2}_{0}(n^{\prime}+1)$
for some universal constant $\sigma_{0}$ (since $I$ is sum of $n^{\prime}+1$
independent binary random variables). Also notice that $\mathbb{E}[R(I)]=1$,
so $R(I)-1$, which is a linear function of $I$, can be written as

$R(I)-1=\frac{8\theta}{(n^{\prime}+1)(1-4\theta^{2})}\left(I-\mathbb{E}[I]\right).$

Therefore, $R(I)-1$ has a sub-gaussian norm bounded by

$\left\lVert R(I)-1\right\rVert^{2}_{\psi_{2}}\leq
C_{1}\frac{\theta^{2}}{(1-4\theta^{2})^{2}(n^{\prime}+1)}.$

By Lemma 3.7, we conclude that term (a) in (C.3) can be controlled by

$\displaystyle
D_{\alpha}\left(P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq
C_{2}\frac{\theta^{2}}{(1-4\theta^{2})^{2}}\frac{\alpha^{2}}{\alpha-1}\frac{1}{n^{\prime}+1},$
(8)

for some constant $C_{2}>0$.

#### Bounding (b)

Similarly, let us denote the LR of term (b) in (C.3) as
$R^{\prime}(i)=\frac{1}{R(i)}$ for $i\in[n^{\prime}+1]$. Let

$I\sim
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}$

and we control the sub-gaussian norm of $R^{\prime}(I)-1$ as follows:

$\displaystyle
R^{\prime}(I)-1=\frac{\mathbb{E}[R(I)]-R(I)}{R(I)}+\frac{1-\mathbb{E}[R(I)]}{R(I)}.$
(9)

For the first term in the right hand side of (9), observe that

$\displaystyle\frac{\mathbb{E}[R(I)]-R(I)}{R(I)}$
$\displaystyle\leq\frac{\left\lvert\mathbb{E}[R(I)]-R(I)\right\rvert}{\left\lvert
R(I)\right\rvert}$
$\displaystyle\leq\left(\frac{1+2\theta}{1-2\theta}\right)\left\lvert\mathbb{E}[R(I)]-R(I)\right\rvert$
(10)

where the last inequality holds since
$R(I)\geq\left(\frac{1+2\theta}{1-2\theta}\right)$ almost surely. Therefore

$\displaystyle\left\lVert\frac{\mathbb{E}[R(I)]-R(I)}{R(I)}\right\rVert^{2}_{\psi_{2}}$
$\displaystyle\leq\left(\frac{1+2\theta}{1-2\theta}\right)^{2}\left\lVert
R(I)-\mathbb{E}[R(I)]\right\rVert^{2}_{\psi_{2}}$ $\displaystyle\leq
C_{3}\left(\frac{1+2\theta}{1-2\theta}\right)^{2}\frac{\theta^{2}}{(1-4\theta^{2})^{2}}\frac{\alpha^{2}}{\alpha-1}\frac{1}{n^{\prime}+1}$
$\displaystyle=C_{3}\frac{\theta^{2}}{(1-2\theta)^{4}}\frac{1}{n^{\prime}+1},$
(11)

where the second inequality is due to the fact that $I-\mathbb{E}[I]$ is sum
of $n^{\prime}+1$ zero-mean bounded random variables.

Next, the second term in (9) can be controlled by

$\displaystyle\left\lvert\frac{1-\mathbb{E}[R(I)]}{R(I)}\right\rvert\leq\left(\frac{1+2\theta}{1-2\theta}\right)\left\lvert
R(I)-1\right\rvert$
$\displaystyle=\left(\frac{1+2\theta}{1-2\theta}\right)\left\lvert\left(\frac{1-2\theta}{1+2\theta}\right)+\frac{\mathbb{E}[I]}{n^{\prime}+1}\left(\frac{8\theta}{1-4\theta^{2}}\right)-1\right\rvert$
$\displaystyle=\left(\frac{1+2\theta}{1-2\theta}\right)\left(\frac{8\theta^{2}}{\left(1-4\theta^{2}\right)(n^{\prime}+1)}\right)$
$\displaystyle=\frac{8\theta^{2}}{\left(1-2\theta\right)^{2}(n^{\prime}+1)},$
(12)

where the second equality holds since

$\mathbb{E}[I]=n^{\prime}\left(1+\frac{\theta}{2}\right)+\left(1-\frac{\theta}{2}\right).$

Combining (C.5) and (C.5), we obtain an upper bound on (9):

$\displaystyle\left\lVert R^{\prime}(I)-1\right\rVert^{2}_{\psi_{2}}$
$\displaystyle\leq
2\left\lVert\frac{\mathbb{E}[R(I)]-R(I)}{R(I)}\right\rVert^{2}_{\psi_{2}}+2\left\lVert\frac{8\theta^{2}}{\left(1-2\theta\right)^{2}(n^{\prime}+1)}\right\rVert^{2}_{\psi_{2}}$
$\displaystyle\leq
2C_{3}\frac{\theta^{2}}{(1-2\theta)^{4}}\frac{1}{n^{\prime}+1}+C_{4}\left(\frac{8\theta^{2}}{\left(1-2\theta\right)^{2}(n^{\prime}+1)}\right)^{2}$
$\displaystyle\leq
C_{5}\frac{\theta^{2}}{(1-2\theta)^{4}}\frac{1}{n^{\prime}+1},$

for some $C_{5}>0$. Also notice that $\mathbb{E}[R^{\prime}(I)-1]=0$ when
$I\sim
P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}$.
Therefore, applying Lemma 3.7, we conclude that term (b) in (C.3) can be
controlled by

$\displaystyle
D_{\alpha}\left(P_{\mathsf{Binom}\left(n^{\prime}+1,\frac{1}{2}+\theta\right)}\middle\|P_{\mathsf{Ber}\left(\frac{1}{2}-\theta\right)+\mathsf{Binom}\left(n^{\prime},\frac{1}{2}+\theta\right)}\right)$
$\displaystyle\leq
C_{6}\frac{\theta^{2}}{(1-2\theta)^{4}}\frac{\alpha^{2}}{\alpha-1}\frac{1}{n^{\prime}+1},$
(13)

for some $C_{6}>0$.