that estimates the order statistic using the common differential privacy
framework called the exponential mechanism [McSherry and Talwar, 2007] is
sufficient up to a constant factor. For a full description of this algorithm,
as well as its accuracy guarantees see [Asi and Duchi, 2020]. ∎

See 4.3

###### Proof of Theorem 4.3.

The main component remaining to prove is that truncating at
$T=\frac{1}{\widehat{\sigma_{\min}}^{2}}$ rather than the optimal truncation
does not affect the utility by more than a constant factor, under the
assumptions of the theorem. Let $k_{1}\geq k_{2}\geq\cdots\geq k_{n}$.
Firstly, we need to show that $\widehat{k_{L}}$ is a sufficiently good
estimate of $k_{L}$. Lemma C.1 provides us with a $\epsilon$-DP estimator of
the $L$-th order statistic that has the guarantee that with probability
$1-\beta$, $k_{L+\frac{1}{\epsilon}(\ln
k_{\max}+\ln(1/\beta))}\leq\widehat{k_{L}}\leq k_{L-\frac{1}{\epsilon}(\ln
k_{\max}+\ln(1/\beta))}$. Since by assumption $2L\geq\frac{1}{\epsilon}(\ln
k_{\max}+\ln(1/\beta))$, this implies that with probability $1-\beta$,
$k_{\frac{1}{2}L}\leq\widehat{k_{L}}\leq k_{\frac{3}{2}L}$. That is, only
$\frac{1}{2}L$ more data points than desired will be truncated.

Next, we need to show that truncating at any point within this range provides
an estimator with accuracy competitive with the optimal truncation. Assume the
PTR component of the algorithm does not fail, the variance of
$\hat{p}_{\epsilon}^{\text{\rm priv }k}$ can be written as two terms, the
variance that exists in the non-private setting, and the additional noise due
to privacy;

${\rm Var}(\hat{p}_{\epsilon}^{\text{\rm priv
}k})=\underbrace{\frac{\sum_{i=L+1}^{9n/10}\min\left\\{\frac{T^{2}}{\widehat{\sigma}_{i}^{2}},\frac{1}{\widetilde{\sigma_{i}}^{4}}\right\\}{\rm
Var}([\widehat{p}_{i}]_{\widetilde{a_{i}}}^{\widetilde{b_{i}}}])}{\left(\sum_{i=L+1}^{9n/10}\min\left\\{\frac{T}{\widetilde{\sigma_{i}}},\frac{1}{\widetilde{\sigma^{2}_{i}}}\right\\}\right)^{2}}}_{\text{non-
private
term}}+\underbrace{\frac{\left(12\frac{f^{\widehat{k_{L}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\widehat{\sigma_{\min}}^{2}\widehat{N}}\right)^{2}}{\epsilon^{2}}}_{\text{private
term}}.$

The truncation has opposite effects on each of these terms. As $T$ decreases,
the private term decreases while the non-private term increases. When we set
$T_{L}=1/{\rm Var}(\mathcal{D}(k_{L+K}))$, where
$K\in[-\frac{1}{2}L,\frac{1}{2}L]$ then if $K$ is negative, no truncation
occurs and the non-private term is optimal. Even if $K$ is positive, only a
small number of data points are truncated so the non-private term is still
close to it’s optimal value:

$\displaystyle\frac{\sum_{i=L+1}^{9n/10}\min\left\\{\frac{T_{L}^{2}}{\widehat{\sigma}_{i}^{2}},\frac{1}{\widehat{\sigma_{i}}^{4}}\right\\}{\rm
Var}([\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}])}{\left(\sum_{i=L+1}^{9n/10}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma}_{i}^{2}}\right\\}\right)^{2}}$
$\displaystyle\leq
O\left(\frac{\sum_{i=L+K}^{9n/10}\frac{1}{\widehat{\sigma_{i}}^{4}}{\rm
Var}([\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}])}{\left(\sum_{i=L+K}^{9n/10}\frac{1}{\widehat{\sigma}_{i}^{2}}\right)^{2}}\right)$
$\displaystyle\leq
O\left(\frac{\sum_{i=L+1}^{9n/10}\frac{1}{\widehat{\sigma_{i}}^{4}}{\rm
Var}([\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}])}{\left(\sum_{i=L+1}^{9n/10}\frac{1}{\widehat{\sigma}_{i}^{2}}\right)^{2}}\right)$

where the first inequality follows from the same proof as Theorem 4.1given
$A\leq\frac{n/2-3L/2}{3L/2}$. The truncation disappears on the right hand side
of the first inequality since
$T_{L}^{2}\leq\frac{1}{\widehat{\sigma_{i}^{2}}}$ for $i\geq L+K$. The second
inequality follows from the fact that adding more high quality data points
only improves the variance of the estimator. Therefore, the non-private term
in the variance is within a constant factor of optimal.

Next, we will show that under the conditions outlined in the theorem, the non-
private term dominates the variance. The normalisation term also appears in
the private term but as an approximation:

$\widehat{N}=\sum_{j=L+1}^{9n/10}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}+{\rm
Lap}\left(\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\right)-\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\ln(2\delta).$

With probability $1-\delta$,

$\displaystyle\widehat{N}$
$\displaystyle\geq\sum_{j=L+1}^{9n/10}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}-2\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\ln(2\delta)$
$\displaystyle\geq\sum_{j=L+1}^{n/4}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}+\sum_{j=n/4+1}^{n/2}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}-2\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\ln(2\delta)$
$\displaystyle\geq\sum_{j=L+1}^{n/4}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}+(n/4-1)\frac{1}{\widehat{\sigma}_{k_{\text{med}}}^{2}}-2\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\ln(2\delta)$
$\displaystyle\geq\sum_{j={L}+1}^{n/4}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}$
$\displaystyle\geq\frac{1}{2}\sum_{j={L}+1}^{9n/10}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma_{i}}^{2}}\right\\}$

where the first inequality comes from high probability bounds on the Laplacian
distribution, the second inequality is simply separating the sum into two
pieces and removing the contribution of users $i\in[n/2+1,9n/10]$, the third
inequality comes from the fact that any user with more than $k_{\text{med}}$
data points has weight larger than $1/\hat{\sigma}_{k_{\text{med}}}^{2}$. The
fourth inequality follows from
$\frac{\widehat{\sigma_{k_{\text{med}}}}}{\widehat{\sigma_{\min}}^{2}}\leq\frac{(n/4-1)\epsilon}{3\ln(2/\delta)}.$
Now, let us turn to the proof that the non-private noise is dominant when
$\epsilon$ is not too large. To see this note that the non-private term
satisfies

$\displaystyle\frac{\sum_{i=L+1}^{9n/10}\min\left\\{\frac{T_{L}^{2}}{\widehat{\sigma}_{i}^{2}},\frac{1}{\widehat{\sigma_{i}}^{4}}\right\\}{\rm
Var}([\widehat{p}_{i}]_{\widetilde{a_{i}}}^{\widetilde{b_{i}}}])}{\left(\sum_{i={L}+1}^{9n/10}\min\left\\{\frac{T_{L}}{\widehat{\sigma_{i}}},\frac{1}{\widehat{\sigma}_{i}^{2}}\right\\}\right)^{2}}$
$\displaystyle\geq\Omega\left(\frac{\sum_{i={L}+1}^{9n/10}\min\\{T_{L}^{2},\frac{1}{\sigma_{i}^{2}}\\}}{\left(\sum_{i={L}+1}^{9n/10}\min\\{\frac{T_{L}}{\sigma_{i}},\frac{1}{\sigma_{i}^{2}}\\}\right)^{2}}\right)$

where the inequality comes from noting that
$[\widehat{a_{i}},\widehat{b_{i}}]\subset[\widetilde{a_{i}},\widetilde{b_{i}}]$,
which implies ${\rm
Var}([\widehat{p}_{i}]_{\widetilde{a_{i}}}^{\widetilde{b_{i}}}])\geq{\rm
Var}([\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}])\geq\frac{1}{2}\sigma_{i}^{2}$
and $\widehat{\sigma}_{i}^{2}$ is within a constant multiplicative factor of
$\sigma_{i}^{2}$. Further, let
$N=\sum_{i={L}+1}^{9n/10}\min\\{\frac{T_{L}}{\sigma_{i}},\frac{1}{\sigma_{i}^{2}}\\}$
so the private term satisfies

$\displaystyle\frac{\left(12\frac{f^{\widehat{k_{L}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\widehat{\sigma_{\min}}^{2}\widehat{N}}\right)^{2}}{\epsilon^{2}}$
$\displaystyle=O\left(\frac{\log(n/\beta)}{\widehat{\sigma_{\min}^{2}}N^{2}\epsilon^{2}}\right)$
$\displaystyle=O\left(\frac{\log(n/\beta)}{\sigma_{\min}^{2}\epsilon^{2}(\sum_{i=L+1}^{9n/10}\min\\{\frac{T_{L}}{\sigma_{i}},\frac{1}{\sigma_{i}^{2}}\\})^{2}}\right)$

Now, comparing these two terms we can see that the non-private term dominates
when:

$\frac{\sum_{i=L+1}^{9n/10}\min\\{T^{2}_{L},\frac{1}{\sigma_{i}^{2}}\\}}{\left(\sum_{i=\log
n+1}^{9n/10}\min\\{\frac{T_{L}}{\sigma_{i}},\frac{1}{\sigma_{i}^{2}}\\}\right)^{2}}=\Omega\left(\frac{\log(n/\beta)}{\sigma_{\min}^{2}\epsilon^{2}(\sum_{i=L+1}^{9n/10}\min\\{\frac{T_{L}}{\sigma_{i}},\frac{1}{\sigma_{i}^{2}}\\})^{2}}\right).$

That is, when:

$\sum_{i=L+1}^{9n/10}\min\left\\{T^{2}_{L},\frac{1}{\sigma_{i}^{2}}\right\\}\geq\Omega\left(\frac{\log(n/\beta)}{\sigma^{2}_{\min}\epsilon^{2}}\right).$

This condition is satisfied since

$\sum_{i=L+1}^{9n/10}\min\left\\{T^{2}_{L},\frac{1}{\sigma_{i}^{2}}\right\\}\geq(n/2-L-1)\frac{1}{\sigma_{\text{med}}^{2}}\geq\Omega\left(\frac{\log(n/\beta)}{\sigma^{2}_{\min}\epsilon^{2}}\right)$

where the first inequality is simply because more than $(n/2-L-1)$ of the user
have weight larger than the median weight, and the second inequality follows
from the assumption that
$\frac{k_{\max}}{k_{\text{med}}}\leq\frac{\epsilon^{2}(n/2-\log
n-1)}{\log(n/\beta)}$. Therefore, with high probability (based on the accuracy
of $\widehat{k_{L}}$), truncating at $1/\sigma_{\min}^{2}$ rather than the
optimal truncation $T$ does not affect the variance of the estimator by more
than a constant factor.

Now that we have established that the noise added for privacy is not too
large, the only remaining potential point of failure for the algorithm is that
the PTR component fails and the algorithm outputs $\widehat{p}_{\epsilon}^{\rm
initial}$ rather than the more accurate weighted estimate. The fact that this
does not happen with high probability is a direct corollary of Lemma 4.4. ∎

##  Appendix D Proofs from Section 5

See 5.2

###### Proof of Lemma 5.2.

Let

$w^{*}=\arg\min_{\begin{subarray}{c}w\in[0,1]^{n}\\\
\sum_{i=1}^{n}w_{i}=1\end{subarray}}{\rm
Var}(\widehat{p})=\arg\min_{\begin{subarray}{c}w\in[0,1]^{n}\\\
\sum_{i=1}^{n}w_{i}=1\end{subarray}}\sum_{i=1}^{n}w_{i}^{2}\sigma_{i}^{2}+\frac{\max_{k}w_{k}^{2}\sigma_{k}^{2}}{\epsilon^{2}}$

be an optimal weight vector that minimizes variance of $\widehat{p}$. We start
with a few observations on structural properties of the optimal weights. Let
$M=\\{\arg\max_{k}w^{*}_{k}\sigma_{k}\\}$ be the set of all users with maximum
weighted-variance contribution to the estimate $\widehat{p}$.

First, notice that for all $i,j\in[n]$, if $w_{i}^{*}>w_{j}^{*}$ then
$\sigma_{i}^{2}\leq\sigma_{j}^{2}$. This follows since if
$\sigma_{i}^{2}>\sigma_{j}^{2}$ then
$w_{i}^{*}\sigma_{j}^{2}+w_{j}^{*}\sigma_{i}^{2}<w_{i}^{*}\sigma_{i}^{2}+w_{j}^{*}\sigma_{j}^{2}$
and $\max\\{w_{i}^{*}\sigma_{j}^{2},w_{j}^{*}\sigma_{i}^{2}\\}\leq
w_{i}^{*}\sigma_{i}$ which implies that swapping the weights of $i$ and $j$
would result in an estimator with lower variance. This is a contradiction
given the definition of $w^{*}$.

Next, we show that if $i,j\notin M$ then
$w_{i}^{*}\sigma_{i}^{2}=w_{j}^{*}\sigma_{j}^{2}$. Suppose towards a
contradiction that $w_{i}^{*}\sigma_{i}^{2}<w_{j}^{*}\sigma_{j}^{2}$. Let
$\alpha=\min\\{\frac{w_{j}^{*}\sigma_{j}^{2}-w_{i}^{*}\sigma_{i}^{2}}{\sigma_{i}^{2}+\sigma_{j}^{2}},\frac{\max_{k}w_{k}^{*}\sigma_{k}-w_{i}^{*}\sigma_{i}}{\sigma_{i}},w_{j}^{*}\\}$.
Then $\alpha>0$, and
$(w_{j}^{*}-\alpha)\sigma_{j},(w_{i}^{*}+\alpha)\sigma_{i}\in[0,\max_{k}w_{k}^{*}\sigma_{k}]$.
Also,

$\displaystyle(w_{j}^{*}-\alpha)^{2}\sigma_{j}^{2}+(w_{i}^{*}+\alpha)^{2}\sigma_{i}^{2}$
$\displaystyle={w_{j}^{*}}^{2}\sigma_{j}^{2}+{w_{i}^{*}}^{2}\sigma_{i}^{2}+\alpha^{2}(\sigma_{i}^{2}+\sigma_{j}^{2})-2\alpha(w_{j}^{*}\sigma_{j}^{2}-w_{i}^{*}\sigma_{i}^{2})$
$\displaystyle={w_{j}^{*}}^{2}\sigma_{j}^{2}+{w_{i}^{*}}^{2}\sigma_{i}^{2}+\alpha(\alpha(\sigma_{i}^{2}+\sigma_{j}^{2})-2(w_{j}^{*}\sigma_{j}^{2}-w_{i}^{*}\sigma_{i}^{2}))$
$\displaystyle<{w_{j}^{*}}^{2}\sigma_{j}^{2}+{w_{i}^{*}}^{2}\sigma_{i}^{2}.$

This implies that shifting $\alpha$ weight from $w^{*}_{i}$ to $w^{*}_{j}$
would reduce the variance of the estimator $\widehat{p}$ without changing the
maximum weighted-variance, which is a contradiction of the optimality of
$w^{*}$.

Define $H=\max_{k}w_{k}^{*}\sigma_{k}$ and note that there exists $R>0$ such
that $w_{i}^{*}=R/\sigma_{i}^{2}$ for all $i\notin M$. From these
observations, there must exist some threshold $T$ such that if $\sigma_{i}\geq
1/T$, then $w_{i}^{*}=R/\sigma_{i}^{2}$, and if $\sigma_{i}<1/T$, then
$w_{i}^{*}=H/\sigma_{i}$. By continuity, $H=RT$, and we can write the optimal
weights as: $w_{i}^{*}=\min\\{1/\sigma^{2}_{i},T/\sigma_{i}\\}R$. Since the
weights $w^{*}_{i}$ must sum to 1, we know that
$R=\frac{1}{\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},T/\sigma_{j}\\}}$.

Thus the optimal weights are:

$w_{i}^{*}=\frac{\min\\{1/\sigma_{i}^{2},T/\sigma_{i}\\}}{\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},T/\sigma_{j}\\}},$

for some appropriate threshold $T$.

∎

Let us recall some notation. Let $\mathcal{P}$ be a parameterized family of
distributions $p\mapsto\mathcal{D}_{p}$, so $\mathbb{E}[\mathcal{D}_{p}]$.
Given an estimator $M$, vector $\boldsymbol{q}\in[0,1]^{n}$ and set
$I\subset[n]$, let

$\mu_{M}(x_{[n]\backslash I};\boldsymbol{q})=\mathbb{E}_{\forall i\in
I,x_{i}\sim\mathcal{D}_{q_{i}}(k_{i}),M}[M(x_{1},\cdots,x_{n})]$

be the expectation taken only over the randomness of $I$ and $M$. Note that in
this notation, user $i$ is sampling from a meta-distribution with mean
$q_{i}$, which may be different for each user. We will abuse notation slightly
and for $p\in[0,1]$, we will let $\mu_{M}(x_{[n]\backslash
I};p)=\mu_{M}(x_{[n]\backslash I};(p,\cdots,p))$. Let
$\mu_{M}(\boldsymbol{q})=\mu_{M}(\emptyset;\boldsymbol{q})$. When the
estimator $M$ is clear from context, we will simply use the notation
$\mu(x_{[n]\backslash I};\boldsymbol{p})$. Recall that for $p\in[0,1]$ and
$k\in\mathbb{N}$, $\phi_{p,k}$ is the probability density function of
$\mathcal{D}_{p}(k)$. We will prove Lemma 5.4 first since this lemma is
required for the proof of Lemma 5.3.

See 5.4

###### Proof of Lemma 5.4.

Let $M:[0,1]^{n}\to[0,1]$ be a randomised mechanism and suppose that each
$x_{i}\sim\mathcal{D}(p_{i},k_{i})$ where $p_{i}\sim\mathcal{D}$. Now, our
goal is to decompose the variance of $M$ into the variance conditioned on each
coordinate, and the variance inherent in the mechanism itself. Let
$\mu=\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[M(x_{1},\cdots,x_{n})]$
be the expectation and for any $I\subset[n]$, let $\mu(x_{[n]\backslash
I})=\mathbb{E}_{\forall i\in I,x_{i}\sim\mathcal{D}(k_{i}),M}[M(x)]$ be the
expectation conditioned only on the randomness in $I$. So,

$\displaystyle{\rm Var}(M)$
$\displaystyle=\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu)^{2}]$
$\displaystyle=\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1})}\mathbb{E}_{x_{2}\sim\mathcal{D}(k_{2}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu_{1}(x_{1})+\mu_{1}(x_{1})-\mu)^{2}]$
$\displaystyle=\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1})}\mathbb{E}_{x_{2}\sim\mathcal{D}(k_{2}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu_{1}(x_{1}))^{2}$
$\displaystyle\hskip
72.26999pt+2(M(x_{1},\cdots,x_{n})-\mu_{1}(x_{1}))(\mu_{1}(x_{1})-\mu)+(\mu_{1}(x_{1})-\mu)^{2}]$
$\displaystyle=\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1})}[(\mu_{1}(x_{1})-\mu)^{2}]+\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1})}\mathbb{E}_{x_{2}\sim\mathcal{D}(k_{2}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu_{1}(x_{1}))^{2}].$

Now, by induction we obtain the following decomposition of the variance of
$M$,

$\displaystyle{\rm Var}(M)$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{i}\sim\mathcal{D}(k_{i})}[(\mu(x_{j\leq
i})-\mu(x_{j<i}))^{2}]$ $\displaystyle\hskip
72.26999pt+\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu(x_{1},\cdots,x_{n}))^{2}]$
$\displaystyle\geq\sum_{i=1}^{n}\mathbb{E}_{x_{i}\sim\mathcal{D}(k_{i})}[(\mu(x_{i})-\mu)^{2}]+\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{n}\sim\mathcal{D}(k_{n}),M}[(M(x_{1},\cdots,x_{n})-\mu(x_{1},\cdots,x_{n}))^{2}]$

where the second inequality follows from Jensen’s inequality:

$\displaystyle\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{i}\sim\mathcal{D}(k_{i})}[(\mu(x_{j\leq
i})-\mu(x_{j<i}))^{2}]$
$\displaystyle\geq\mathbb{E}_{x_{i}\sim\mathcal{D}(k_{i})}[(\mathbb{E}_{x_{1}\sim\mathcal{D}(k_{1}),\cdots,x_{i-1}\sim\mathcal{D}(k_{i})}[\mu(x_{j\leq
i})-\mu(x_{j<i})])^{2}]$
$\displaystyle=\mathbb{E}_{x_{i}\sim\mathcal{D}(k_{i})}[(\mu(x_{i})-\mu)^{2}].$

∎

See 5.3

###### Proof of Lemma 5.3.

We first apply Lemma 5.4 to decompose the variance of the estimate computed by
$M$ as:

${\rm Var}_{{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}}(M)\geq\sum_{i=1}^{n}\mathbb{E}_{x_{i}\sim\mathcal{D}_{p}(k_{i})}[(\mu(x_{i};p)-\mu(p))^{2}]+\mathbb{E}_{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}[(M(x_{1},\cdots,x_{n})-\mu(x_{1},\cdots,x_{n};p))^{2}]$

The first term is the sum of contributions to the variance of the individual
terms $x_{i}$, and the second term is the contribution to the variance of the
noise added for privacy. We will proceed by bounding these terms separately,
starting with the first term.

First note that by definition,

$\int(\mu(x_{i};\boldsymbol{q})-\mu(\boldsymbol{q}))\phi_{q_{i},k_{i}}(x_{i})dx_{i}=\mathbb{E}_{x_{i}\sim\mathcal{D}_{q_{i}}(k_{i})}[\mu(x_{i};\boldsymbol{q})]-\mu(\boldsymbol{q})=0.$

Therefore, by taking the partial derivative with respect to $q_{i}$ we have

$\int\left[\left(\frac{\partial}{\partial
q_{i}}(\mu(x_{i};\boldsymbol{q})-\mu(\boldsymbol{q}))\right)\phi_{q_{i},k_{i}}(x_{i})+(\mu(x_{i};\boldsymbol{q})-\mu(\boldsymbol{q}))\frac{\partial}{\partial
q_{i}}\phi_{q_{i},k_{i}}(x_{i})\right]dx_{i}=0.$

Note that $\mu(x_{i};\boldsymbol{q})$ is constant in $q_{i}$ so rearranging,
and noting that $\frac{\partial}{\partial
q_{i}}\phi_{q_{i},k_{i}}(x_{i})=\phi_{q_{i},k_{i}}(x_{i})\left(\frac{\partial}{\partial
q_{i}}\log\phi_{q_{i},k_{i}}(x_{i})\right)$ we have,

$\displaystyle\int\left(\frac{\partial}{\partial
q_{i}}\mu(\boldsymbol{q})\right)\phi_{q_{i},k_{i}}(x_{i})dx_{i}$
$\displaystyle=\int(\mu(x_{i};\boldsymbol{q})-\mu(\boldsymbol{q}))\phi_{q_{i},k_{i}}(x_{i})\left(\frac{\partial}{\partial
q_{i}}\log\phi_{q_{i},k_{i}}(x_{i})\right)dx_{i}$
$\displaystyle\leq\sqrt{\left(\int(\mu(x_{i};\boldsymbol{q})-\mu(\boldsymbol{q}))^{2}\phi_{q_{i},k_{i}}(x_{i})dx_{i}\right)\left(\int\left(\frac{\partial}{\partial
q_{i}}\log\phi_{q_{i},k_{i}}(x_{i})\right)^{2}\phi_{q_{i},k_{i}}(x_{i})dx_{i}\right)}.$
(21)

Let

$w_{i}(p)=\int\left(\frac{\partial}{\partial
q_{i}}\mu(\boldsymbol{q})\right)\phi_{q_{i},k_{i}}(x_{i})dx_{i}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}=\frac{\partial}{\partial
q_{i}}\mu(\boldsymbol{q})\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}$

and note that by assumption there exists a constant $c$ such that for all
$i\in[n]$ and $q_{i}\in[1/3,2/3]$,

$\int\left(\frac{\partial}{\partial
q_{i}}\log\phi_{q_{i},k_{i}}(x_{i})\right)^{2}\phi_{q_{i},k_{i}}(x_{i})dx_{i}\leq\frac{1}{c\cdot{\rm
Var}(\mathcal{D}_{q_{i}}(k_{i})}).$

Then evaluating both sides of Equation (21) at the constant vector
$\boldsymbol{q}=(p,\cdots,p)$, we have

$\left(\int(\mu(x_{i};p)-\mu(p))^{2}\phi_{p,k_{i}}(x_{i})dx_{i}\right)\geq\frac{w_{i}(p)^{2}}{\int\left(\frac{\partial}{\partial
p}\log\phi_{p,k_{i}}(x_{i})\right)^{2}\phi_{p,k_{i}}(x_{i})dx_{i}}\geq c\cdot
w_{i}(p)^{2}{\rm Var}(\mathcal{D}_{p}(k_{i})).$

Now we have controlled the contribution of each individual coordinate to the
variance of $M$, and it remains to control the contribution of the noise due
to privacy.

We will show that for two independent samples $x_{i}$, $x_{i}^{\prime}$ drawn
from $\mathcal{D}_{p}(k_{i})$,

$\mathbb{E}[(\mu(x_{i};p)-\mu(x_{i}^{\prime};p))^{2}]\geq\Omega\Big{(}w_{i}(p)^{2}\cdot{\rm
Var}(\mathcal{D}_{p}(k_{i}))\Big{)}.$ (22)

Letting

$\alpha=\sqrt{\mathbb{E}[(\mu(x_{i};p)-\mu(x_{i}^{\prime};p))^{2}]},$

we can write

$\displaystyle w_{i}(p)$
$\displaystyle=\frac{\partial\mu(\boldsymbol{q})}{\partial
q_{i}}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}$
$\displaystyle=\frac{\partial(\mu(\boldsymbol{q})-\mu(x_{i}^{\prime};\boldsymbol{q}))}{\partial
q_{i}}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}$
$\displaystyle=\frac{\partial}{\partial
q_{i}}\int_{x_{i}}(\mu(x_{i};\boldsymbol{q})-\mu(x_{i}^{\prime};\boldsymbol{q}))\phi_{q_{i},k_{i}}(x_{i})dx_{i}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}$
$\displaystyle=\int_{x_{i}}(\mu(x_{i};p)-\mu(x_{i}^{\prime};p))\left(\frac{\partial\phi_{q_{i},k_{i}}(x_{i})}{\partial
q_{i}}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}\right)dx_{i}$
$\displaystyle=\int_{x_{i}}(\mu(x_{i};p)-\mu(x_{i}^{\prime};p))\left(\frac{\partial\log\phi_{q_{i},k_{i}}(x_{i})}{\partial
q_{i}}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}\right)\phi_{p,k_{i}}(x_{i})dx_{i}$
$\displaystyle\leq\sqrt{\left(\int_{x_{i}}(\mu(x_{i};p)-\mu(x_{i}^{\prime};p))^{2}\phi_{p,k_{i}}(x_{i})dx_{i}\right)\left(\int_{x_{i}}\left(\frac{\partial\log\phi_{q_{i},k_{i}}(x)}{\partial
q_{i}}\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}\right)^{2}\phi_{p,k_{i}}(x)dx_{i}\right)}$
$\displaystyle\leq\alpha\cdot\sqrt{\int_{x_{i}}\left(\frac{\partial\log\phi_{p_{i},k_{i}}(x_{i})}{\partial
p_{i}}\;\Bigg{\rvert}_{\boldsymbol{p}=(p,\cdots,p)}\right)^{2}\phi_{p_{i},k_{i}}(x_{i})dx_{i}}$
$\displaystyle\leq\alpha\cdot\sqrt{\frac{1}{c\cdot{\rm
Var}(\mathcal{D}_{p}(k_{i}))}}$

The first equality is by definition. The second equality follows from the fact
that $\mu(x_{i}^{\prime};\mathbf{q})$ is constant with respect to $q_{i}$, so
its derivative is 0. The third inequality simply expands out the definition of
$\mu(\mathbf{q})$. The fourth equality follows from the linearity of
derivatives, the fact that
$\mu(x_{i};\mathbf{q})-\mu(x_{i}^{\prime},\mathbf{q})$ is constant with
respect to $q_{i}$, and the fact that
$(\mu(x_{i};\mathbf{q})-\mu(x_{i}^{\prime},\mathbf{q}))|_{\mathbf{q}=(p,\cdots,p)}=(\mu(x_{i};p)-\mu(x_{i}^{\prime},p))$.
The fifth equality follows from the formula $\frac{\partial}{\partial x}\ln
f(x)=\frac{\frac{\partial}{\partial x}f(x)}{f(x)}$, which holds for any
differentiable function $f$. The first inequality is a result of the Cauchy-
Schwarz inequality. The second inequality follows from the definition of
$\alpha$, and the final inequality follows from Assumption 2 of Lemma 5.3.

Therefore,

$\alpha\geq w_{i}(p)\cdot\sqrt{c\cdot{\rm Var}(\mathcal{D}_{p}(k_{i}))}.$

We now argue that any $(\epsilon,\epsilon^{2}/100)$-differentially private
mechanism should have variance
$\Omega(\alpha^{2}\log\frac{1}{\epsilon}/10\epsilon^{2})$. Suppose that we had
a mechanism that violated this property. Then by running this mechanism
$\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}}$ times and averaging, the
advanced composition theorem implies that this average is $(1,1/100)$-DP. This
averaged output however has variance $O(\alpha^{2}/10)$. Thus given samples
$x_{i}$, and $x^{\prime}_{i}$ such that
$|\mu(x_{i};p)-\mu(x_{i}^{\prime};p)|\geq\alpha/2$, if the noise had variance
$O(\alpha^{2}/10)$ on $(x_{i},x_{-i})$ as well as on $(x^{\prime}_{i},x_{-i})$
(when $x_{-i}$ is drawn randomly), then these two inputs would be
distinguishable with probability at least $9/10$. This however violates the
$(1,1/100)$-DP of the averaged algorithm. This implies that for random
$x_{i}$, the noise added by the DP algorithm is at least
$\Omega(\alpha^{2}\log\frac{1}{\epsilon}/20\epsilon^{2})$

Thus the variance of $M$ is,

${\rm Var}_{{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}}(M)\geq\sum_{i=1}^{n}c\cdot
w_{i}(p)^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))+\Omega\Big{(}\frac{w_{i}(p)^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))}{\epsilon^{2}}\Big{)}$ (23)

Finally, since the weights $w_{i}(p)$ that we defined need not sum to 1, they
will need to be normalized to sum to 1 to satisfy the conditions of NLE. We
need to show this normalisation does not substantially increase the variance
of the estimator in NLE defined by these weights. This is equivalent to
showing that the normalisation term, $\sum_{i=1}^{n}w_{i}(p)$ is large for
some $p$. For $p\in[1/3,2/3]$, let $\gamma:[1/3,2/3]\to[0,1]^{n}$, defined by
$\gamma(p)=(p,\cdots,p)$, be a path in $[0,1]^{n}$ then by the fundamental
theorem of line integrals,

$\displaystyle 3\int_{1/3}^{2/3}\sum_{i=1}^{n}w_{i}(p)dp$
$\displaystyle=3\int_{1/3}^{2/3}\left(\sum_{i=1}^{n}\left(\frac{\partial}{\partial
q_{i}}\mu(\boldsymbol{q})\right)\;\Bigg{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}\right)dp$
$\displaystyle=3\int_{\gamma}\nabla\mu(\boldsymbol{q})\cdot\boldsymbol{1}d\boldsymbol{q}$
$\displaystyle=3(\mu(2/3,\cdots,2/3)-\mu(1/3,\cdots,1/3))$ $\displaystyle=1$

This implies that there exists $p^{*}\in[1/3,2/3]$ such that
$\sum_{i=1}^{n}w_{i}(p^{*})\geq 1$. Define

$\displaystyle M_{\texttt{NL}}(x_{1},\cdots,x_{n})$
$\displaystyle=\sum_{i=1}^{n}\frac{w_{i}(p^{*})}{\sum_{j=1}^{n}w_{j}(p^{*})x_{j}}+{\rm
Lap}\left(\frac{\max_{i}\frac{w_{i}(p^{*})}{\sum_{j=1}^{n}w_{j}(p^{*})}\sqrt{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}}{\epsilon}\right)$
$\displaystyle=\frac{1}{\sum_{i=1}^{n}w_{i}(p^{*})}\left(\sum_{i=1}^{n}w_{i}(p^{*})x_{i}+{\rm
Lap}\left(\frac{\max_{i}w_{i}(p^{*})\sqrt{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}}{\epsilon}\right)\right),$

where the second equality follows from properties of the Laplace distribution.
Now,

$\displaystyle{\rm Var}_{\mathcal{D}_{p}}(M_{\texttt{NL}})$
$\displaystyle\leq\frac{1}{(\sum_{i=1}^{n}w_{i}(p^{*}))^{2}}\left(\sum_{i=1}^{n}w_{i}(p^{*})^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))+O\left(\frac{\max_{i}w_{i}(p^{*})^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))}{\epsilon^{2}}\right)\right)$
$\displaystyle\leq\sum_{i=1}^{n}w_{i}(p^{*})^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))+O\left(\frac{\max_{i}w_{i}(p^{*})^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))}{\epsilon^{2}}\right),$

where the second inequality comes from the fact that
$\sum_{i=1}^{n}w_{i}(p^{*})\geq 1$. Comparing this with Equation 23, we see
that specifically, at $p=p^{*}$,

${\rm Var}_{\mathcal{D}_{p^{*}}}(M_{\texttt{NL}})\leq O\left({\rm
Var}_{\mathcal{D}_{p^{*}}}(M)\right).$

Now, if $p,p^{*}\in[1/3,2/3]$ then ${\rm
Var}(\mathcal{D}_{p}(k_{i}))=\Theta\left({\rm
Var}(\mathcal{D}_{p^{*}}(k_{i}))\right)$ so ${\rm
Var}_{D_{p}}(M_{\texttt{NL}})=\Theta({\rm Var}_{D_{p^{*}}}(M_{\texttt{NL}}))$.
Therefore, the worst case variance of $M_{\texttt{NL}}$ is less than the worst
case variance of $M$ over all $p\in[1/3,2/3]$, as required. ∎

See 5.5

###### Proof of Lemma 5.5.

The variance claim follows immediately from noting that ${\rm
Var}\left([x_{i}]_{p-f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}^{p+f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}\right)\leq{\rm
Var}(x_{i})$, and the assumption that
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)=\tilde{O}({\rm
Var}(\mathcal{D}(k_{i}))$. The bias claim follows from noting that with
probability $1-\beta$,
$[x_{i}]_{p-f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}^{p+f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}=x_{i}$.
This implies that $M_{\texttt{TNL}}$ is within $\beta$ in total variation
distance to an unbiased estimator. Since $M_{\texttt{TNL}}$ takes values in
$[0,1]$, this implies the mean is in $[p-\beta,p+\beta]$. ∎

See 5.6

###### Proof of Corollary 5.6.

Firstly, suppose that $\sigma_{p}=0$, so the meta-distribution is constant,
and $\mathcal{D}_{p}(k_{i})={\rm Bin}(k_{i},p)$. Then the Fisher information
of $\phi_{p,k_{i}}$ is $\int\left(\frac{\partial}{\partial
p}\log\phi_{p,k_{i}}(x_{i})\right)^{2}\phi_{p,k_{i}}(x_{i})dx_{i}=\frac{k_{i}}{p(1-p)}$
and ${\rm Var}(\mathcal{D}_{p}(k_{i}))=\frac{p(1-p)}{k_{i}}$, so
$\mathcal{D}_{p}(k_{i})$ satisfies Condition 2 of Lemma 5.3. Additionally,

$\displaystyle\min_{M\text{, unbiased}}\max_{p\in[1/3,2/3]}{\rm
Var}_{\mathcal{D}_{p}}[M]$
$\displaystyle=\tilde{\Omega}\left(\max_{p\in[1/3,2/3]}{\rm
Var}_{\mathcal{D}_{p}}[\widehat{p}_{\epsilon}^{\rm
ideal}]\right)\quad\text{(under conditions of Thm \ref{metatheorem})}$

We can view the truncation as simply choosing a maximum $k^{*}$ so that
$T=\sqrt{\frac{k^{*}}{p(1-p)}}$. Now, the un-normalised weights of
$\widehat{p}_{\epsilon}^{\rm ideal}$ are

$\min\left\\{\frac{1}{{\rm Var}(\mathcal{D}_{p}(k_{i}))},\frac{T}{\sqrt{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}}\right\\}=\min\left\\{\frac{k_{i}}{p(1-p)},\frac{\sqrt{k_{i}k^{*}}}{p(1-p)}\right\\}.$

Further, ${\rm Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})\leq{\rm
Var}(\mathcal{D}(k_{i}))$ and we assume throughout this paper that ${\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})\geq(1/2){\rm
Var}(\mathcal{D}(k_{i}))$. So, ${\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})=\Theta({\rm
Var}(\mathcal{D}(k_{i})))=\Theta(\frac{p(1-p)}{k_{i}})$. Finally, since
binomials are highly concentrated, $|b_{i}-a_{i}|=\Omega(\sigma_{i})$, which
implies that $\tfrac{\max_{i}w_{i}^{*}|b_{i}-a_{i}|}{\epsilon}$ as defined in
Equation (3) is achieved at $k_{i}=k^{*}$. Thus,

$\displaystyle\min_{M\text{, unbiased}}\max_{p\in[1/3,2/3]}{\rm
Var}_{\mathcal{D}_{p}}[M]$
$\displaystyle=\max_{p\in[1/3,2/3]}\frac{\Omega\left(\frac{k^{*}}{p(1-p)\epsilon^{2}}\right)+\sum_{i=1}^{n}\left(\min\left\\{\frac{k_{i}}{p(1-p)},\frac{\sqrt{k_{i}k^{*}}}{p(1-p)}\right\\}\right)^{2}\frac{1}{2}\frac{p(1-p)}{k_{i}}}{\left(\sum_{i=1}^{n}\min\left\\{\frac{k_{i}}{p(1-p)},\frac{\sqrt{k_{i}k^{*}}}{p(1-p)}\right\\}\right)^{2}}$
$\displaystyle=\tilde{\Omega}\left(\max_{p\in[1/3,2/3]}p(1-p)\frac{\frac{k^{*}}{\epsilon^{2}}+\sum_{i=1}^{n}\min\\{k_{i},k^{*}\\}}{(\sum_{i=1}^{n}\min\\{k_{i},\sqrt{k_{i}k^{*}}\\})^{2}}\right)$
$\displaystyle=\tilde{\Omega}\left(\frac{\frac{k^{*}}{\epsilon^{2}}+\sum_{i=1}^{n}\min\\{k_{i},k^{*}\\}}{(\sum_{i=1}^{n}\min\\{k_{i},\sqrt{k_{i}k^{*}}\\})^{2}}\right),$

where the first equality comes from Theorem 5.1, the second equality pulls out
common factors, and the third equality is because $p$ is bounded away from 0
and 1.

For the other component of the bound we will let $\mathcal{D}_{p}$ be a
truncated Gaussian distribution. Let $\phi$ and $\Phi$ respectively be the
probability density function and cumulative density function of the standard
Gaussian $\mathcal{N}(0,1)$. Let $W$ be such that
$\gamma:=\Phi(W)-\Phi(-W)\geq 9/10$ and
$\lambda:=\frac{2W\phi(W)}{\Phi(W)-\Phi(-W)}\leq 1/2$. Define the truncated
Gaussian $\mathcal{D}_{p}$ with mean $p$ on
$[p-\frac{\sigma_{p}}{\sqrt{1-\lambda}}W,p+\frac{\sigma_{p}}{\sqrt{1-\lambda}}W]$
by the probability density function:

$\phi_{p}(q)=\begin{cases}\frac{1}{\gamma}\phi\left((q-p)\frac{\sqrt{1-\lambda}}{\sigma_{p}}\right)&q\in[p-\frac{\sigma_{p}}{\sqrt{1-\lambda}}W,p+\frac{\sigma_{p}}{\sqrt{1-\lambda}}W]\\\
0&\text{otherwise.}\end{cases}.$

Now, the variance of $\mathcal{D}_{p}$ is $\sigma_{p}^{2}$ and the Fisher
information of $\mathcal{D}_{p}$ is given by Mihoc and Fătu [2003]

$\frac{1}{\sigma_{p}^{2}}\left(1-\lambda\right)^{2}\in\left[\frac{1}{4\sigma_{p}^{2}},\frac{1}{\sigma_{p}^{2}}\right].$
(24)

Since any sample from $\mathcal{D}$ can be post-processed into a sampling from
$\mathcal{D}(k)$ for any $k\in\mathbb{N}$, we have

$\displaystyle\min_{M\text{, unbiased}}\max_{p\in[1/3,2/3]}{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i})}[M(x_{1},\cdots,x_{n})]$
$\displaystyle\geq\min_{M\text{, unbiased}}\max_{p\in[1/3,2/3]}{\rm
Var}_{p_{1},\cdots,p_{n}\sim\mathcal{D}_{p}}[M(p_{1},\cdots,p_{n})]$
$\displaystyle\geq\max_{p\in[1/3,2/3]}O\left(\frac{\sigma_{p}^{2}}{n}\right)$
$\displaystyle=O(\frac{\sigma_{p}^{2}}{n}),$

where the second inequality follows from the Cramér-Rao bound [Nielsen, 2013]
and Equation (24). ∎

##  Appendix E Proofs from Section 6

See 6.1

###### Proof of Lemma 6.1.

Firstly, the privacy guarantees follows immediately from the Laplace Mechanism
in differential privacy [Dwork et al., 2006] noting that
$\frac{10}{n}\sum_{i=(9n/10)+1}^{n}x^{1}_{i}$ has sensitivity $\frac{10}{n}$.

Now, let us turn to the two accuracy guarantees. We will start with the
guarantee that $\widehat{p}_{\epsilon}^{\rm initial}$ is close to $p$ with
high-probability. Note that $\mathcal{D}$ is simply a Bernoulli random
variable with mean $p$ so since each sample is independent,
$\frac{10}{n}\sum_{i=(9n/10)+1}^{n}x^{1}_{i}={\rm Bin}(n/10,p)$. Thus, if
$n\geq\frac{20\log(1/\beta)}{p}$, a Chernoff bound gives

$\Pr\left[\left|\frac{10}{n}\sum_{i=(9n/10)+1}^{n}x^{1}_{i}-p\right|\geq\sqrt{\frac{3\min\\{p,1-p\\}\log(4/\beta)}{n/10}}\right]\leq\beta/2.$

Therefore, combining with a high probability bound on the Laplace
distribution,

$\Pr\left[\left|\widehat{p}_{\epsilon}^{\rm
initial}-p\right|\geq\sqrt{\frac{3\min\\{p,1-p\\}\log(4/\beta)}{n/10}}+\frac{\log(2/\beta)}{\epsilon
n/10}\right]\leq\beta.$

We will condition on the following event for the remainder of the proof, which
will occur with probability $1-\beta$:

$\left|\widehat{p}_{\epsilon}^{\rm initial}-p\right|\leq
2\max\left\\{\sqrt{\frac{3\min\\{p,1-p\\}\log(4/\beta)}{n/10}},\frac{\log(2/\beta)}{\epsilon
n/10}\right\\}.$

Now if $\left|\widehat{p}_{\epsilon}^{\rm initial}-p\right|\leq
2\sqrt{\frac{3\min\\{p,1-p\\}\log(4/\beta)}{n/10}}$. Since we need $\alpha$ in
terms of $\widehat{p}_{\epsilon}^{\rm initial}$ rather than $p$ (since
$\widehat{p}_{\epsilon}^{\rm initial}$ is known to the algorithm), we need to
rework this formula. Squaring both sides and bringing all the terms to the
same side, we obtain

$p^{2}-2\left(\widehat{p}_{\epsilon}^{\rm
initial}+\frac{6\log(4/\beta)}{n/10}\right)p+(\widehat{p}_{\epsilon}^{\rm
initial})^{2}\leq 0.$

Completing the square we obtain

$\left(p-\widehat{p}_{\epsilon}^{\rm
initial}-\frac{6\log(4/\beta)}{n/10}\right)^{2}+(\widehat{p}_{\epsilon}^{\rm
initial})^{2}-\left(\widehat{p}_{\epsilon}^{\rm
initial}+\frac{6\log(4/\beta)}{n/10}\right)^{2}\leq 0.$

Now, rearranging and taking the square root, we obtain

$\left|p-\widehat{p}_{\epsilon}^{\rm
initial}-\frac{6\log(4/\beta)}{n/10}\right|\leq\sqrt{\left(\widehat{p}_{\epsilon}^{\rm
initial}+\frac{6\log(4/\beta)}{n/10}\right)^{2}-(\widehat{p}_{\epsilon}^{\rm
initial})^{2}}$

then by squaring both sides, using the fact that $\min\\{p,1-p\\}\leq p$, and
rearranging we have

$\displaystyle|\widehat{p}_{\epsilon}^{\rm
initial}-p|\leq\sqrt{\frac{12\widehat{p}_{\epsilon}^{\rm
initial}\log(4/\beta)}{n/10}+\frac{36\log^{2}(4/\beta)}{n^{2}/100}}+\frac{6\log(4/\beta)}{n/10}$

which implies that,

$\left|\widehat{p}_{\epsilon}^{\rm initial}-p\right|\leq
2\max\left\\{\sqrt{\frac{12\widehat{p}_{\epsilon}^{\rm
initial}\log(4/\beta)}{n/10}+\frac{36\log^{2}(4/\beta)}{n^{2}/100}}+\frac{6\log(4/\beta)}{n/10},\frac{\log(2/\beta)}{\epsilon
n/10}\right\\}.$

We need to show that this expression is less than or equal to
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ because
$\alpha=O(1/\sqrt{n})$. To see this, note that $\alpha=O(1/\sqrt{n})$ and
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ is increasing towards 1 as
$n$ grows large. Thus for $n$ sufficiently large, $\alpha\leq
f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ will be satisfied.

Next we turn to proving the second accuracy claim, that
$\widehat{p}_{\epsilon}^{\rm initial}(1-\widehat{p}_{\epsilon}^{\rm initial})$
is concentrated around $p(1-p)$. Let $\mathcal{E}=\widehat{p}_{\epsilon}^{\rm
initial}-p$ so

$\displaystyle\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm initial})$
$\displaystyle=(p+\mathcal{E})(1-p-\mathcal{E})=p(1-p)+(1-2p)\mathcal{E}-\mathcal{E}^{2}$

Now, if $\min\\{p,1-p\\}\geq
K\max\left\\{\frac{3\log(4/\beta)}{n/10},\frac{\log(2/\beta)}{\epsilon
n/10}\right\\}$ for some constant $K$, then

$\displaystyle|\mathcal{E}|$
$\displaystyle\leq\sqrt{\frac{3\min\\{p,1-p\\}\log(4/\beta)}{n/10}}+\frac{\log(2/\beta)}{\epsilon
n/10}$
$\displaystyle\leq\sqrt{\frac{\min\\{p,1-p\\}\min\\{p,(1-p)\\}}{K}}+\frac{\min\\{p,(1-p)\\}}{K}$
$\displaystyle\leq\frac{2\min\\{p,1-p\\}}{K}.$

Thus, combining this with the fact that $1-2p\leq\max\\{p,1-p\\}$ for
$p\in[0,1]$,

$\displaystyle|(1-2p)\mathcal{E}-\mathcal{E}^{2}|$
$\displaystyle\leq\max\\{p,1-p\\}\frac{2\min\\{p,1-p\\}}{K}+\left(\frac{2\min\\{p,1-p\\}}{K}\right)^{2}$
$\displaystyle\leq\frac{6p(1-p)}{K}$

Finally, choosing $K=12$ gives,

$\widehat{p}_{\epsilon}^{\rm initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})\in\left[\frac{p(1-p)}{2},\frac{3p(1-p)}{2}\right].$

∎

See 6.3

###### Proof of Lemma 6.3.

Note that $\mathbb{E}[\mathcal{D}(k)]=p$. Then we can bound the absolute third
central moment as follows,

$\displaystyle\mathbb{E}_{x\sim\mathcal{D}(k)}[|x-p|^{3}]$
$\displaystyle=\mathbb{E}_{p_{i}\sim\mathcal{D}}\mathbb{E}_{y\sim{\rm
Bin}(k,p_{i})}[|(\frac{1}{k}y-p_{i})-(p-p_{i})|^{3}]$ $\displaystyle\leq
4\left(\mathbb{E}_{p_{i}\sim\mathcal{D}}\mathbb{E}_{y\sim{\rm
Bin}(k,p_{i})}[|\frac{1}{k}y-p_{i}|^{3}]+\mathbb{E}_{p_{i}\sim\mathcal{D}}[|p-p_{i}|^{3}]\right)$
$\displaystyle\leq
4\left(\frac{1}{k^{3}}\mathbb{E}_{p_{i}\sim\mathcal{D}}\left[\sqrt{\mathbb{E}_{y\sim{\rm
Bin}(k,p_{i})}[|y-k\cdot p_{i}|^{2}]\mathbb{E}_{y\sim{\rm
Bin}(k,p_{i})}[|y-p_{i}|^{4}]}\right]+\gamma\sigma_{p}^{3}\right)$ (by Cauchy-
Schwarz inequality) $\displaystyle\leq
4\left(\frac{1}{k^{3}}\mathbb{E}_{p_{i}\sim\mathcal{D}}\left[\sqrt{k^{2}(p_{i}(1-p_{i}))^{2}(1+3kp_{i}(1-p_{i}))}\right]+\gamma\sigma_{p}^{3}\right)$
$\displaystyle\leq
4\left(\frac{1}{k^{3}}\mathbb{E}_{p_{i}\sim\mathcal{D}}[k(p_{i}(1-p_{i}))]+\frac{1}{k^{3}}\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{3k^{3}(p_{i}(1-p_{i}))^{3}}]+\gamma\sigma_{p}^{3}\right)$
$\displaystyle\leq
4\left(\frac{1}{k^{2}}p(1-p)+\frac{\sqrt{3}}{k^{3/2}}\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{(p_{i}(1-p_{i}))^{3}}]+\gamma\sigma_{p}^{3}\right)$
(by Jensen’s inequality) $\displaystyle\leq
4\left(\frac{1}{k^{3/2}}\sqrt{(p(1-p))^{3}}+\frac{\sqrt{3}}{k^{3/2}}\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{(p_{i}(1-p_{i}))^{3}}]+\gamma\sigma_{p}^{3}\right),$

where the first inequality follows from the following inequality that holds
for all real valued $a$ and $b$: $|a-b|^{3}\leq 4(|a|^{3}+|b|^{3})$. The
second to last inequality follows from Jensen’s inequality since $h(x)=x(1-x)$
is concave, and the last inequality follows since
$\frac{1}{\sqrt{k}}\leq\sqrt{p(1-p)}$. Now, we will use a generalised form of
Jensen’s inequality to bound
$\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{(p_{i}(1-p_{i}))^{3}}]$. Let
$h(x)=(x(1-x))^{3/2}$ and

$\phi(x)=\frac{h(x)-h(p)}{(x-p)^{2}}-\frac{h^{\prime}(p)}{x-p}.$

Since $p\in[\frac{1}{k},1-\frac{1}{k}]$,

$\max_{x\in[\frac{1}{2k},1-\frac{1}{2k}]}\phi(x)\leq(1/2)\max_{x\in[\frac{1}{2k},1-\frac{1}{2k}]}h^{\prime\prime}(x)\leq
h^{\prime\prime}\left(\frac{1}{2k}\right)=\frac{3(8(\frac{1}{2k})^{2}-8(\frac{1}{2k})+1)}{4\sqrt{(1-\frac{1}{2k})\frac{1}{2k}}}=\frac{3(8-16k+4k^{2})}{8k\sqrt{(2k-1)}}\leq\frac{3}{2}\sqrt{k}.$

If $x\notin[\frac{1}{2k},1-\frac{1}{2k}]$ then $|x-p|\geq\frac{1}{2k}$ and
$h(x)<h(p)$, so

$\phi(x)\leq\frac{|h^{\prime}(p)|}{|x-p|}=\frac{3|1-2p|\sqrt{p(1-p)}}{2|p-x|}\leq\frac{3}{2}\frac{\sqrt{p(1-p)}}{|p-x|}\leq\max\left\\{\frac{3}{2}\frac{\sqrt{\frac{1}{k}(1-\frac{1}{k})}}{|\frac{1}{k}-x|},\frac{3}{2}\frac{\sqrt{\frac{1}{k}(1-\frac{1}{k})}}{|1-\frac{1}{k}-x|}\right\\}\leq
3\sqrt{k-1}\leq 3\sqrt{k}.$

Therefore, by the generalised Jensen’s inequality,

$\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{(p_{i}(1-p_{i}))^{3}}]\leq\sqrt{(p(1-p))^{3}}+\sigma_{p}^{2}\cdot
3\sqrt{k}\leq\sqrt{(p(1-p))^{3}}+\sigma_{p}^{2}\cdot 3\sqrt{k}.$

Continuing to bound the absolute central third moment as above,

$\displaystyle\mathbb{E}_{x\sim\mathcal{D}(k)}[|x-p|^{3}]$ $\displaystyle\leq
4\left(\frac{1}{k^{3/2}}\sqrt{(p(1-p))^{3}}+\frac{\sqrt{3}}{k^{3/2}}\mathbb{E}_{p_{i}\sim\mathcal{D}}[\sqrt{(p_{i}(1-p_{i}))^{3}}]+\gamma\sigma_{p}^{3}\right)$
$\displaystyle\leq
4\left(\frac{1}{k^{3/2}}\sqrt{(p(1-p))^{3}}+\frac{\sqrt{3}}{k^{3/2}}\sqrt{(p(1-p))^{3}}+3\sqrt{3}\frac{\sigma_{p}^{2}}{k}+\gamma\sigma_{p}^{3}\right)$
$\displaystyle\leq
4\left(\frac{1}{k^{3/2}}\sqrt{(p(1-p))^{3}}+\frac{\sqrt{3}}{k^{3/2}}\sqrt{(p(1-p))^{3}}+3\sqrt{3}\sigma_{p}^{3}+\gamma\sigma_{p}^{3}\right)$
$\displaystyle\leq
4(3\sqrt{3}+\gamma)\left(\frac{1}{k^{3/2}}\sqrt{(p(1-p))^{3}}+\sigma_{p}^{3}\right)$
$\displaystyle\leq
4(3\sqrt{3}+\gamma)\left(\frac{1}{k}p(1-p)+\sigma_{p}^{2}\right)^{3/2}$
$\displaystyle\leq
8(3\sqrt{3}+\gamma)\left(\frac{1}{k}p(1-p)+\frac{k-1}{k}\sigma_{p}^{2}\right)^{3/2},$

where the first and second inequalities follow from above, the third
inequality follows because $k\geq 1$, the fourth is simply rearranging the
terms, the fifth follows from the fact that for all positive, real numbers $a$
and $b$: $a^{3/2}+b^{3/2}<(a+b)^{3/2}$, and the last inequality follows since
if $k\geq 2$ then $(k-1)/k>1/2$. ∎

See 6.4

###### Proof of Lemma 6.4.

Note that the conditions are sufficient to ensure from Lemma 6.3 that
$\frac{\rho_{\mathcal{D}(k)}}{{\rm Var}(\mathcal{D}(k))^{3/2}}\leq
8(3\sqrt{3}+\gamma)$. Then Lemma 6.2 and Lemma 2.1 imply that

${\rm
Var}(\mathcal{D}(k))=\frac{1}{k}p(1-p)+\frac{k-1}{k}\sigma_{p}^{2}\leq\widehat{\sigma}_{p,k}^{2}\leq
8\left(\frac{1}{k}p(1-p)+\frac{k-1}{k}\sigma_{p}^{2}\right)=8{\rm
Var}(\mathcal{D}(k)).$

∎

###  E.1 Proof of Lemma 6.2

In this section we slightly generalise the algorithm and analysis given by
Karwa and Vadhan [2018] beyond Gaussian distributions. We will show that their
algorithm provides accurate estimates of the mean of sufficiently nice
exponential families. This algorithm first estimates the variance of the
distribution, then estimates the mean. Both steps of the estimation are
performed using differentially private histogram queries.

Let $\rho=\mathbb{E}_{P}[|X-\mathbb{E}_{P}(x)|^{3}]$ be the absolute third
central moment of $P$, and let $\sigma$ be the standard deviation. Since the
algorithm of Karwa and Vadhan [2018] is designed for Gaussian distributions we
will use the following lemma that describes the rate of convergence of the
central limit theorem.

######  Lemma E.1 (Berry-Esseen theorem).

Let $X_{1},\cdots,X_{n}$ be iid samples from a distribution $P$ and
$\rho=\mathbb{E}_{P}[|X-\mathbb{E}_{P}(x)|^{3}]$. Set
$S_{n}=\frac{1}{n}\sum_{j=1}^{n}X_{j}$, $\mu=\mathbb{E}_{P}[x]$ and
$\sigma^{2}={\rm Var}(P)$, and let
$Y\sim\mathcal{N}(\mu,\frac{\sigma^{2}}{n})$ then for some absolute constant
$\gamma>0$,

  * •

(Uniform)

$|\mathbb{P}[S_{n}\leq a]-\mathbb{P}[Y\leq
a]|\leq\frac{\gamma\rho}{\sigma^{3}\sqrt{n}}$

  * •

(Non-uniform) For all $a>0$,

$|\mathbb{P}[S_{n}\leq a]-\mathbb{P}[Y\leq
a]|\leq\frac{\gamma\rho}{(1+|a|)^{3}\sigma^{3}\sqrt{n}}.$

######  Lemma E.2 (Histogram Learner [Dwork et al., 2006, Bun et al., 2015,
Vadhan, 2017]).

For all $K\in\mathbb{N}$ and any domain $\Omega$, for any collection of
disjoint bins $B_{1},\cdots,B_{K}$ defined on
$\Omega,n\in\mathbb{N},\epsilon\geq 0,\delta\in(0,1/n),\lambda>0$ and
$\beta\in(0,1)$ there exists an $(\epsilon,\delta)$-DP algorithm
$M:\Omega^{n}\to\mathbb{R}^{K}$ such that for every distribution $D$ on
$\Omega$, if

  1. 1.

$X_{1},\cdots,X_{N}\sim D$ and $p_{k}=\mathbb{P}(X_{i}\in B_{k})$

  2. 2.

$(\tilde{p_{1}},\cdots,\tilde{p_{K}})=M(X_{1},\cdots,X_{n})$ and

  3. 3.

$n\geq\max\left\\{\min\left\\{\frac{8}{\epsilon\lambda}\ln\left(\frac{2K}{\beta}\right),\frac{8}{\epsilon\lambda}\ln\left(\frac{4}{\beta\delta}\right)\right\\},\frac{1}{2\lambda^{2}}\ln\left(\frac{4}{\beta}\right)\right\\}$

then,

$\mathbb{P}_{X\sim D,M}(\max_{k}|\tilde{p_{k}}-p_{k}|\leq\lambda)\geq
1-\beta\;\;\;\text{ and },$ $\mathbb{P}_{X\sim
D,M}(\arg\max_{k}\tilde{p_{k}}=j)\leq\begin{cases}np_{j}+2e^{-(\epsilon
n/8)\cdot(\max_{k}p_{k})}&\text{ if }K<2/\delta\\\ np_{j}&\text{ if }K\geq
2/\delta\end{cases}$

where the probability is taken over the randomness of $M$ and the data
$X_{1},\cdots,X_{n}$.

Algorithm 5 Variance estimator

Input: Sample $X=(x_{1},\dots,x_{n})\sim
P,\epsilon,\delta,\sigma_{\min},\sigma_{\max},\beta,\rho$.

1:Let $\phi=\lceil(600\gamma\rho)^{2}\rceil$, where $\gamma$ is the absolute
constant from Lemma E.1.

2:If
$n<c\phi\min\left\\{\frac{1}{\epsilon}\ln\left(\frac{\ln\left(\frac{\sigma_{max}}{\sigma_{min}}\right)}{\beta}\right),\frac{1}{\epsilon}\ln\left(\frac{1}{\delta\beta}\right)\right\\},$
where $c$ is an absolute constant whose existence is ensured by Lemma E.2,
then output $\bot$.

3:Divide $[\sigma_{min},\sigma_{max}]$ into bins of exponentially increasing
length. The bins are of the form $B_{j}=(2^{j},2^{j+1}]$ for
$j=j_{min},\cdots,j_{max},$ where
$j_{max}=\lceil\ln_{2}\frac{\sigma_{max}}{\sqrt{\phi}}\rceil+1$ and
$j_{min}=\lfloor\ln_{2}\frac{\sigma_{min}}{\sqrt{\phi}}\rfloor-2.$

4:Let $Z_{i}=\frac{1}{\phi}\sum_{j=1}^{\phi}x_{(i-1)\phi+j}$ for
$i=1,\cdots,\lfloor n/\phi\rfloor$.

5:Let $Y_{i}=Z_{2i}-Z_{2i-1}$ for $i=1,\cdots,\lfloor n/2\rfloor$

6:Run the histogram learner of Lemma E.2 with privacy parameters
$(\epsilon,\delta)$ and bins $B_{j_{min}},\cdots,B_{j_{max}}$ on input
$|Y_{1}|,\cdots,|Y_{n}|$ to obtain noisy estimates
$\tilde{p_{j_{min}}},\cdots,\tilde{p_{j_{max}}}$. Let
$\widehat{l}=\arg\max\tilde{p_{j}}$

7:Output $\widehat{\sigma}=2^{\widehat{l}+2}\sqrt{\phi}$.

Note in particular that the use of approximate $(\epsilon,\delta)$-DP allows
us to set the $K=\infty$, while the sample complexity remains finite. The
following lemma states that provided $\rho/\sigma^{3}$ is bounded, Algorithm 5
can estimate the standard deviation up to a multiplicative constant.

######  Lemma E.3.

For all $n\in\mathbb{N}$,
$\sigma_{min}<\sigma_{max}\in[0,\infty],\epsilon>0,\delta\in(0,\frac{1}{n}],\beta\in(0,1/2),\rho>0,$
Algorithm 5 is $(\epsilon,\delta)$-DP and satisfies that if
$X_{1},\cdots,X_{n}$ are iid draws from $P$, where $P$ has standard deviation
$\sigma\in[\sigma_{min},\sigma_{max}]$ and $\frac{\rho}{\sigma^{3}}\leq\rho$
then if

$n\geq
c\rho^{2}\min\left\\{\frac{1}{\epsilon}\ln\left(\frac{\ln\left(\frac{\sigma_{max}}{\sigma_{min}}\right)}{\beta}\right),\frac{1}{\epsilon}\ln\left(\frac{1}{\delta\beta}\right)\right\\},$

(where $c$ is a universal constant), we have

$\mathbb{P}_{X\sim P,M}(\sigma\leq\widehat{\sigma}\leq 8\sigma)\geq 1-\beta.$

###### Proof of Lemma E.3.

This proof follows almost directly from Theorem 3.2 of Karwa and Vadhan
[2018]. Note that each $Y_{i}$ is sampled from a distribution with mean 0 and
variance $\frac{2\sigma^{2}}{\phi}$, and in addition is the sum of $\phi$
independent random variables. As in [Karwa and Vadhan, 2018], there exists a
bin $B_{l}$ with label
$l\in(\lfloor\ln_{2}\frac{\sigma_{min}}{\sqrt{\phi}}\rfloor-1,\lceil\ln_{2}\frac{\sigma_{max}}{\sqrt{\phi}}\rceil)$
such that $\frac{\sigma}{\sqrt{\phi}}\in(2^{l},2^{l+1}]=B_{l}$. Define,

$p_{j}=\mathbb{P}(|Y_{i}|\in B_{j}).$

Sort the $p_{j}$s as $p_{(1)}\geq p_{(2)}\geq\cdots$, and let
$j_{(1)},j_{(2)},\cdots$ be the corresponding bins. Then the following two
facts imply the result (as in [Karwa and Vadhan, 2018]).

Fact 1: The bins corresponding to the largest and second largest mass
$p_{(1)},p_{(2)}$ are $(j_{(1)},j_{(2)})\in\\{(l,l-1),(l,l+1),(l+1,l)\\}$.

Fact 2: $p_{(1)}-p_{(3)}>1/300$.

Now, let $W_{i}\sim N(0,2\frac{\sigma^{2}}{\phi})$ and let $q_{i},q_{(i)}$ be
the corresponding probabilities for $W_{i}$. Then Karwa and Vadhan [2018]
showed that:

  * •

The bins corresponding to the largest and second largest mass
$q_{(1)},q_{(2)}$ are $(j_{(1)},j_{(2)})\in\\{(l,l-1),(l,l+1),(l+1,l)\\}$.

  * •

$q_{(1)}-q_{(3)}>1/100$.

By Lemma E.1, since $\phi=\lceil(600\gamma\rho)^{2}\rceil$, for all $j$,
$|p_{j}-q_{j}|\leq 1/300$. Therefore,
$\\{p_{(1)},p_{(2)}\\}=\\{q_{(1)},q_{(2)}\\}$, which implies both Fact 1 and
Fact 2. ∎

##  Appendix F Interpretation and Estimation of Concentration Functions

Recall that $f_{\mathcal{D}}^{k_{i}}(n,\sigma_{p}^{2},\beta)$ describes the
concentration of $\widehat{p}_{i}\sim\mathcal{D}({k_{i}})$ and is defined as,

$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)=\arg\inf\\{\alpha\;|\;\Pr_{\widehat{p}_{1},\cdots,\widehat{p}_{n}\sim\mathcal{D}({k_{i}})}\left(\max_{i}|\widehat{p}_{i}-p|\geq\alpha\right)\leq\beta\\}.$

In the main body of the paper, we assumed that this function was known to the
analyst, even if the input value $\sigma_{p}^{2}$ was unknown and had to be
estimated. In this appendix, we interpret the structure of this concentration
function and show that even when this informational assumption is relaxed, our
Algorithm 2 can still be implemented with some minor modifications.

We start by introducing two additional functions:
$f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$, which describes the concentration
of $p_{i}\sim\mathcal{D}$, and $f_{{\rm Bin}}(k_{i},p_{i},\beta)$, which
describes the high probability tail bound on the binomial ${\rm
Bin}(k_{i},p_{i})$:

$f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)=\arg\inf\\{\alpha\;|\;\Pr_{p_{1},\cdots,p_{n}\sim\mathcal{D}}(\max_{i}|p-p_{i}|\geq\alpha)\leq\beta\\}.$
$f_{{\rm Bin}}(k_{i},p_{i},\beta)=\arg\inf\\{\alpha\;|\;\Pr_{x\sim{\rm
Bin}(k_{i},p_{i})}(|\frac{1}{k_{i}}x-p_{i}|\geq\alpha)\leq\beta\\}$

In this appendix, we will assume that only the function
$f_{\mathcal{D}}(n,\cdot,\beta)$ is known to the analyst, but the input
variance parameter $\sigma_{p}^{2}$ of the distribution is not known. For
example, the analyst may know that $\mathcal{D}$ is Gaussian with unknown mean
and variance, and thus she can express the concentration of $p_{i}$ as a
function of the variance. Also note that for any values $k_{i},p_{i}$ and
$\beta$, we can empirically compute $f_{{\rm Bin}}(k_{i},p_{i},\beta)$.

The following lemma shows how we can translate high probability bounds on
$\mathcal{D}$ to high probability bounds on $\mathcal{D}(k)$, using this
binomial tail bound of ${\rm Bin}(k_{i},p_{i})$. Specifically, it shows that
our quantity of interest $f_{\mathcal{D}}^{k_{i}}(n,\sigma_{p}^{2},\beta)$ of
the $\widehat{p_{i}}$s can be upper and lower bounded by concentration of the
$p_{i}$s (as described by $f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$) plus a
binomial tail bound.

######  Lemma F.1.

Suppose that $\mathcal{D}$ is supported on $[0,1/2]$. Given
$k_{i},n\in\mathbb{N}$, $\sigma_{p}^{2}$, and $\beta\in[0,1]$, define
$\beta^{\prime}=2\sqrt{1-\sqrt[n]{1-\beta}}=\Theta(\sqrt{\beta/n})$ and assume
that for all $p_{i}$ in the support of $\mathcal{D}$,

$\Pr_{\widehat{p}_{i}\sim{\rm Bin}(k_{i},p_{i})}(p_{i}-\widehat{p}_{i}\geq
f_{{\rm
Bin}}(k_{i},p_{i},\beta^{\prime}))\geq\frac{1}{2}\beta^{\prime}\;\;\text{ and
}\;\;\Pr_{\widehat{p}_{i}\sim{\rm Bin}(k_{i},p_{i})}(\widehat{p}_{i}-p_{i}\geq
f_{{\rm Bin}}(k_{i},p_{i},\beta^{\prime}))\geq\frac{1}{4}\beta^{\prime}.$

Then for all $\beta\in[0,1]$, for all $i\in[n]$,

$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\leq
f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta/2)+f_{{\rm
Bin}}(k_{i},p_{\max},\beta/n),$

where $p_{\max}=\min\\{1/2,p+f_{\mathcal{D}}(n,\sigma_{p},\beta/2)\\}$.
Further, for all $i\in[n]$,

$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})+f_{{\rm
Bin}}(k_{i},p_{\max},\beta^{\prime}).$

We note that the conditions on $\mathcal{D}$ and ${\rm Bin}(k_{i},p_{i})$ are
mild. The condition on the tails of ${\rm Bin}(k_{i},p_{i})$ is intuitively
claiming that ${\rm Bin}(k_{i},p_{i})$ is symmetric. This occurs whenever
$k_{i}$ is large enough, and $p_{i}$ is bounded away from 0 or 1. We
conjecture that the condition that $\mathcal{D}$ is supported on $[0,1/2]$ can
be relaxed but leave the relaxation to future work.

###### Proof of Lemma F.1.

Notice that if $p<q<1/2$ then $f_{{\rm Bin}}(k_{i},p,\beta)\leq f_{{\rm
Bin}}(k_{i},q,\beta)$. Let us consider the upper bound first. With probability
$1-\frac{\beta}{2}$,

$\text{for all $i$, }|p-p_{i}|\leq f_{\mathcal{D}}(n,\sigma_{p},\beta/2).$
(25)

Further, if Equation (25) holds then we have that with probability
$1-\frac{\beta}{2n}$,

$|\widehat{p_{i}}-p_{i}|\leq f_{{\rm Bin}}(k_{i},p_{i},\frac{\beta}{2n})\leq
f_{{\rm Bin}}(k_{i},p_{\max},\frac{\beta}{2n}).$

Thus, for all $i$,

$|p-p_{i}|\leq f_{\mathcal{D}}(n,\sigma_{p},\beta/2)+f_{{\rm
Bin}}(k_{i},p_{\max},\frac{\beta}{2n}).$

Now, for the lower bound, let
$\beta^{\prime}=\sqrt{8}\sqrt{1-\sqrt[n]{1-\beta}}$ and
$\alpha=f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})$. Note that either

$\Pr_{p_{i}\sim\mathcal{D}}\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\geq\frac{1}{2}\beta^{\prime}\;\;\text{
or }\Pr_{p_{i}\sim\mathcal{D}}\left(p-p_{i}\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\geq\frac{1}{2}\beta^{\prime}.$

Assume without loss of generality that
$\Pr_{p_{i}\sim\mathcal{D}}\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\geq\frac{1}{2}\beta^{\prime}$.
Then by assumption,

$\Pr_{\widehat{p_{i}}\sim{\rm
Bin}(k_{i},p_{i})}\left(\widehat{p}_{i}-p_{i}\geq f_{{\rm
Bin}}(k_{i},p_{i},\beta^{\prime})\right)\geq\frac{1}{4}\beta^{\prime}$

Then

$\displaystyle\Pr$ $\displaystyle\left(\max_{i}|\widehat{p}_{i}-p|\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})+f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)$
$\displaystyle\geq\Pr\left(\exists i\text{ s.t. }p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\text{ and
}\widehat{p}_{i}-p_{i}\geq f_{{\rm Bin}}(k_{i},p_{i},\beta^{\prime})\right)$
$\displaystyle=1-\Pr\left(\forall i,p_{i}-p\leq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\text{ or
}\widehat{p}_{i}-p_{i}\leq f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)$
$\displaystyle=1-\left(\Pr\left(p_{i}-p\leq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\text{ or
}\widehat{p}_{i}-p_{i}\leq f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)\right)^{n}.$

Now,

$\displaystyle\Pr$ $\displaystyle\left(p_{i}-p\leq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\text{ or
}\widehat{p}_{i}-p_{i}\leq f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)$
$\displaystyle=1-\Pr\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\text{ and
}\widehat{p}_{i}-p_{i}\geq f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)$
$\displaystyle=1-\Pr\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\Pr\left(\widehat{p}_{i}-p_{i}\geq
f_{{\rm Bin}}(k_{i},p+\alpha,\beta^{\prime})\;|\;p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)$ $\displaystyle\leq
1-\Pr\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\Pr\left(\widehat{p}_{i}-p_{i}\geq
f_{{\rm Bin}}(k_{i},p_{i},\beta^{\prime})\;|\;p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)$ $\displaystyle\leq
1-\Pr\left(p_{i}-p\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})\right)\Pr\left(\widehat{p}_{i}-p_{i}\geq
f_{{\rm Bin}}(k_{i},p_{i},\beta^{\prime})\right)$ $\displaystyle\leq
1-\frac{1}{8}(\beta^{\prime})^{2}$

where the first inequality comes from $p_{i}\geq p+\alpha$, so $f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\leq f_{{\rm
Bin}}(k_{i},p_{i},\beta^{\prime})$ Finally,

$\displaystyle\Pr\left(\max_{i}|\widehat{p}_{i}-p|\geq
f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})+f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime})\right)\geq
1-(1-(\beta^{\prime}/\sqrt{8})^{2})^{n}=\beta,$

which implies the result. ∎

###  F.1 Extending Our Results to Unknown
$f_{\mathcal{D}}^{k_{i}}(n,\sigma_{p}^{2},\beta)$ settings

Lemma F.1 gives both upper bound and lower bounds on
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$, which can be used to modify
Algorithm 2 and extend Theorem 4.1 to apply in the setting where
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ is unknown, but
$f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ is known instead.

Recall that the concentration bound
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ is used in Algorithm 2 to
define the truncation parameters $\widehat{a}_{i}$ and $\widehat{b}_{i}$, and
that we would like to define a truncation window
$[\widehat{a_{i}},\widehat{b_{i}}]$ that both contains $[a_{i},b_{i}]$ (so
that with high probability none of the $\widehat{p}_{i}$ are truncated), and
is not too wide, so $|\widehat{b_{i}}-\widehat{a_{i}}|\leq 6|b_{i}-a_{i}|$ (in
order to invoke Lemma 4.2).

The following lemma proposes new values for $\widehat{a_{i}}$ and
$\widehat{b_{i}}$ for the setting where only
$f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ is known, but not
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$. It combines the bounds on
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ from Lemma F.1, with the
bounds on $\widehat{p}_{\epsilon}^{\rm initial}$ from Lemma 6.1 to show that
$|\widehat{b_{i}}-\widehat{a_{i}}|\leq 6|b_{i}-a_{i}|$, as desired.

######  Lemma F.2.

For $\alpha>0$, let

$\widehat{a_{i}}=\max\left\\{0,\widehat{p}-\alpha-
f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2)-f_{{\rm
Bin}}(k_{i},\widehat{p}+\alpha+f_{\mathcal{D}}(n,\widehat{\sigma_{p}},\beta/2),\beta/n)\right\\}$

and

$\widehat{b_{i}}=\min\left\\{1,\widehat{p}+\alpha+f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2)+f_{{\rm
Bin}}(k_{i},\widehat{p}+\alpha+f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2),\beta/n)\right\\}.$

If $\widehat{\sigma_{p}^{2}}\geq\sigma_{p}^{2}$, and
$|p-\widehat{p}|\leq\alpha$, then for all $i\in[n]$,

$[a_{i},b_{i}]\subset[\widehat{a_{i}},\widehat{b_{i}}].$

Further, if $\alpha\leq f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ and
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\geq\Omega(f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)+f_{{\rm
Bin}}(k_{i},\min\\{1/2,p+f_{\mathcal{D}}(n,\sigma_{p},\beta/2)\\},\beta/n))$
then

$|\widehat{b_{i}}-\widehat{a_{i}}|\leq 6|b_{i}-a_{i}|.$

###### Proof of Lemma F.2.

Let us first show that
$[\widehat{a}_{i},\widehat{b}_{i}]\subset[a_{i},b_{i}]$. Using our modified
definition of $\widehat{a_{i}}$ given above, we have,

$\displaystyle\widehat{a_{i}}$ $\displaystyle=\widehat{p}_{\epsilon}^{\rm
initial}-\alpha-f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2)-f_{{\rm
Bin}}(k_{i},\widehat{p}_{\epsilon}^{\rm
initial}+\alpha+f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2),\beta/n)$
$\displaystyle\leq
p-f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2)-f_{{\rm
Bin}}(k_{i},p+f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2),\beta/n)$
$\displaystyle\leq p-f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta/2)-f_{{\rm
Bin}}(k_{i},p+f_{\mathcal{D}}(n,\sigma_{p},\beta/2),\beta/n)$
$\displaystyle\leq p-f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$
$\displaystyle=a_{i}.$

The first two inequalities respectively follow from the accuracy conditions on
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
in Theorem 4.1; the third inequality comes from Lemma F.1; and the final
equality is by the definition of $a_{i}$. A symmetric result that
$\widehat{b_{i}}\geq b_{i}$ follows similarly.

The second statement of this lemma ensures that the width of the truncation
parameter is not more than a constant factor larger than the ideal.
Specifically,

$\displaystyle|\widehat{b_{i}}-\widehat{a_{i}}|$ $\displaystyle\leq
2\alpha+2\left(f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2)+f_{{\rm
Bin}}(k_{i},\widehat{p}+\alpha+f_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta/2),\beta/n)\right)$
$\displaystyle\leq
2f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)+O(f_{\mathcal{D}}(1,\sigma_{p}^{2},\beta^{\prime})-f_{{\rm
Bin}}(k_{i},p+\alpha,\beta^{\prime}))$ $\displaystyle\leq
2f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)+2\left(2f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\right)$
$\displaystyle\leq 6f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$
$\displaystyle=6|b_{i}-a_{i}|$

∎

We note that Lemma 4.2 as stated requires
$|\widehat{b_{i}}-\widehat{a_{i}}|\leq 4|b_{i}-a_{i}|$, rather than
$6|b_{i}-a_{i}|$, this difference of constants will only affect the constant
$C$ in Theorem 4.1, and the main claim of a constant approximation in variance
will still hold with these new $\widehat{a_{i}}$ and $\widehat{b_{i}}$ values.

We will, however, have to add an additional assumption to Theorem 4.1 in this
setting. We will need to assume that $\mathcal{D}$ is s.t.
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\geq\Omega(f_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)+f_{{\rm
Bin}}(k_{i},\min\\{1/2,p+f_{\mathcal{D}}(n,\sigma_{p},\beta/2)\\},\beta/n))$,
to satisfy the condition of Lemma F.2. This condition is related to the high
probability bound on $\mathcal{D}(k)$. The right hand side of this condition
is the high probability bound on $\mathcal{D}(k)$ that is inherited directly
from the high probability bounds on $\mathcal{D}$ and ${\rm Bin}(k,p)$.
Without further assumptions on $\mathcal{D}$, this is the best upper bound on
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ that we can obtain, and
hence is the bound used in the truncation in $\widehat{p}_{\epsilon}$. The
condition states that this upper bound is within a constant multiplicative
factor of the true value $f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$. We
note that this condition is guaranteed by the lower bound on
$f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ in Lemma F.1 for
$\mathcal{D}$ with support on $[0,1/2]$, and we conjecture that it holds more
broadly.