# Mean Estimation with User-level Privacy under Data Heterogeneity

Rachel Cummings111Columbia University. Part of this work was completed while
the author was at Apple. Supported in part by NSF grant CNS-2138834 and an
Apple Privacy-Preserving Machine Learning Award. Vitaly Feldman222Apple Audra
McMillan22footnotemark: 2 Kunal Talwar22footnotemark: 2

###### Abstract

A key challenge in many modern data analysis tasks is that user data are
heterogeneous. Different users may possess vastly different numbers of data
points. More importantly, it cannot be assumed that all users sample from the
same underlying distribution. This is true, for example in language data,
where different speech styles result in data heterogeneity. In this work we
propose a simple model of heterogeneous user data that allows user data to
differ in both distribution and quantity of data, and provide a method for
estimating the population-level mean while preserving user-level differential
privacy. We demonstrate asymptotic optimality of our estimator and also prove
general lower bounds on the error achievable in the setting we introduce.

##  1 Introduction

Many practical problems in statistical data analysis and machine learning deal
with the setting in which each user generates multiple data points. In such
settings the distribution of each user’s data may be somewhat different and,
furthermore, users may possess vastly different numbers of samples. This issue
is one the key challenges in federated learning (Kairouz et al., 2021) leading
to considerable interest in models and algorithms that address this issue.

As an example, consider the task of next-word prediction for a keyboard.
Different users typing on a keyboard may have different styles of writing or
focus on different topics, leading to different distributions. There are
aspects of the language that are common to all users, and likely additional
aspects of style that are common to large groups of users. Thus while each
user has their own data distribution, there are commonalities between the
distributions, and additional commonalities amongst distributions
corresponding to particular subsets of users. Modeling and learning such
relationships between users’ distributions is crucial for building a better
global model for all users, as well as for personalizing models for users.

The focus of this work is on differentially private algorithms for such
settings. We assume that there is an unknown global meta-distribution
$\mathcal{D}$. For each user $i$, a personal data distribution
$\mathcal{D}_{i}$ is chosen randomly from $\mathcal{D}$ (for example, by
sampling a set of parameters that define $\mathcal{D}_{i}$). Each user then
receives some number $k_{i}$ of i.i.d. samples from $\mathcal{D}_{i}$. The
goal is to solve an analysis task relative to $\mathcal{D}$, with an eye
towards better modeling of each $\mathcal{D}_{i}$ even when $k_{i}$ is small.
This abstract setting can model many practical settings where the
relationships between the $\mathcal{D}_{i}$’s take different forms. Indeed the
standard loss in federated learning is the (unweighted) average over users of
a per-user loss function (Kairouz et al., 2021, Sec. 3.3.2), which corresponds
to learning when the underlying distribution is $\mathcal{D}$. Little
theoretical work has been done in this setting and even the most basic
statistical tasks are poorly understood. Thus we start by focusing on the
fundamental problem of mean estimation. Specifically, in our model,
$\mathcal{D}$ is a distribution on the interval $[0,1]$ with unknown mean $p$
and unknown variance $\sigma_{p}^{2}$. Further, we assume that
$\mathcal{D}_{i}$ is simply a Bernoulli distribution with mean
$p_{i}\sim\mathcal{D}$.

While the general $\mathcal{D}_{i}$ setting is of interest, the Bernoulli case
captures a variety of interesting use cases. For example, each sample from the
Bernoulli distribution could represent whether or not the user has clicked on
an ad. Another common example is model evaluation, where the user produces a
Bernoulli sample by engaging or not engaging with a feature (e.g., phone
keyboard next word suggestion, crisis helpline link, search engine knowledge
panels, sponsored link in search results, etc.). As a concrete example, a
language model is used to make the next word suggestions on a phone keyboard.
A new version of this model would be first tested to measure the average
suggestion acceptance rate over users. Each user would thus generate a set of
independent Bernoulli r.v.’s with each individual mean $p_{i}$ corresponding
to the model accuracy for the specific user. Heterogeneity comes from
different users typing differently (and hence model accuracy varying across
users) and using the keyboard with different frequency. Note that the
distribution of model accuracies among users is the meta distribution
$\mathcal{D}$ in our work. More generally, measuring the average accuracy of a
classification model among a large group of users is an important task in
itself. Such models are deployed in privacy-sensitive applications such as
health and finance. The resulting statistics may need to be shared with third
parties or other teams within a company, raising potential user privacy
concerns.

Our main contribution is a differentially private algorithm that estimates the
mean of $\mathcal{D}$ in this heterogeneous setting. We first study this
question in an idealized setting, where the variance of $\mathcal{D}$ is
known, and no privacy constraints. Here the optimal non-private estimator for
$p_{i}$ is simple and linear: it is a weighted linear combination of the
individual user means with weights that depend on the $k_{i}$’s and on
$\sigma_{p}$. The variance of this estimate is
$\sigma_{ideal}^{2}\approx(\sum_{i}\min(k_{i},\sigma_{p}^{-2}))^{-1}$. This
expression has a natural interpretation: this is the variance from using
$\min(k_{i},\sigma_{p}^{-2})$ samples from user $i$ and averaging all the
Bernoulli samples thus obtained. We then design a differentially private
estimator for $p$. We show that under mild assumptions, there is no asymptotic
price to privacy (and to not knowing $\sigma_{p}$). That is, our
differentially private estimator has variance $\tilde{O}(\sigma_{ideal}^{2})$.
For some intuition, note that the restriction on using at most
$\sigma_{p}^{-2}$ samples from each user ensures that the estimator is not too
affected by their individual mean $p_{i}$. Interestingly, the estimator
achieving this bound in the private setting is non-linear. Further, we show
that $\sigma_{ideal}^{2}$ is close to the best achievable variance, under some
mild technical conditions.

Our technical results highlight several of the challenges associated with
ensuring user-level privacy when data is heterogeneous. For example, in the
heterogeneous setting, the optimal choice of weights for each user
contribution depends on properties of $\mathcal{D}$ that also need to be
estimated from the data. Further, we show a novel approach to proving lower
bounds for private statistical estimation in the heterogenous setting. Our
approach builds on the proof of the Cramér-Rao lower bound in statistics, and
we show how privacy terms can be incorporated in this approach to show near
optimality of our algorithms for nearly every setting of $k_{i}$’s. These
tools and insights should be useful for modeling and designing algorithms for
more involved data analysis tasks.

We note that the optimal algorithm for this problem was not known prior to
this work, even in the special case where all $\mathcal{D}_{i}$’s are
identical (or, equivalently, $\sigma_{p}^{2}=0$) but users hold different
numbers of samples. In the absence of privacy constraints, this setting poses
no additional complexity over the case where each user has a single data
point, since the data points all come from the same distribution. However,
with the requirement of user-level differential privacy, even this special
case appears to require many of the technical tools developed in this work
(see Section 4.3 for a detailed discussion).

We aim to help foster similar model-driven exploration in other settings.
There have been attempts to handle heterogeneity by phrasing the problem as
meta-learning or multi-task learning (Kairouz et al., 2021, Sec 3.3.3). These
works rely on implicit assumptions about the different distributions. Our goal
is to start with a more principled approach that makes explicit the
assumptions on the relationship between different distributions and use that
to derive algorithms. For example, if we were to model the $\mathcal{D}_{i}$’s
as having means coming from a mixture of Gaussians, the estimation of cluster
means would be a necessary step in an EM-type algorithm. Our choice of
$\mathcal{D}_{i}$’s being Bernoulli is meant to capture discrete distribution
learning problems that have been extensively studied in private federated
settings. Our techniques are general and extend naturally to real-valued
random variables where, e.g., $\mathcal{D}_{i}$ is a Gaussian with mean
$p_{i}$ and known variance. While we make minimal assumptions on
$\mathcal{D}$, our results asymptotically match the lower bounds for the case
of $\mathcal{D}$ being Gaussian with known variance. Our techniques also have
natural extensions to higher dimensions.

#### Summary of our results:

Our main results involve three estimators; an idealized (non-realisable)
estimator $\widehat{p}_{\epsilon}^{\rm ideal}$ that assumes that the mean and
variance of $\mathcal{D}$ are known to the algorithm, an estimator
$\widehat{p}_{\epsilon}$ that is private with respect to the user’s samples,
but not with respect to each user’s number of samples $k_{i}$, and finally an
estimator $\hat{p}_{\epsilon}^{\text{\rm priv }k}$ that is private with
respect to both the samples _and_ the number of samples. Let $\widehat{p}_{i}$
be the mean of the $k_{i}$ samples from user $i$. The estimators
$\widehat{p}_{\epsilon}$ and $\hat{p}_{\epsilon}^{\text{\rm priv }k}$ both
require as input initial, less accurate $(\epsilon,\delta)$-DP mean and
variance estimators $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$. The main results of this paper can be
(informally) summarised as follows:

  * •

Near optimality of $\widehat{p}_{\epsilon}^{\rm ideal}$ [Theorem 5.1]. For any
parameterized family of distributions $p\mapsto\mathcal{D}_{p}$, such that the
Fisher information of $\widehat{p}_{i}$ is inversely proportional to the
variance of $\widehat{p}_{i}$ for all $i$, each $\widehat{p}_{i}$ is
sufficiently-well concentrated (e.g. sub-Gaussian) and $p\in[1/3,2/3]$, we
have that $\widehat{p}_{\epsilon}^{\rm ideal}$ is minimax optimal, up to
logarithmic (in $n$) factors, among all unbiased estimators of $p$. The
estimator $\widehat{p}_{\epsilon}^{\rm ideal}$ itself is not unbiased, but it
has very low bias. The proof of this result involves a Cramér-Rao style
argument which may be of independent interest. This result allows us to use
$\widehat{p}_{\epsilon}^{\rm ideal}$ as a yardstick by which to compare
$\widehat{p}_{\epsilon}$ and $\hat{p}_{\epsilon}^{\text{\rm priv }k}$.

  * •

Near optimality of $\widehat{p}_{\epsilon}$ [Theorem 4.1]. Assume there exists
mean and variance estimators, $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$, such that when run with a constant
fraction (say $n/10$) of the users, $\rm\texttt{mean}_{\epsilon,\delta}$
returns a sufficiently good estimate of $p$ (roughly no worse than the
estimate from any single user, and implies a constant multiplicative
approximation to $p(1-p)$), and when run with $\log n/\epsilon$ users,
$\texttt{variance}_{\epsilon,\delta}$ returns a constant multiplicative
approximation to $\sigma_{p}^{2}$. If the maximum $k_{i}$ and median $k_{i}$
are within a factor of $(n\epsilon/\log n)-1$, then the variance of
$\widehat{p}_{\epsilon}$, with $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$ as the inputted initial estimators, is
within a constant factor of the variance of $\widehat{p}_{\epsilon}^{\rm
ideal}$. The conditions on $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$ are not particularly stringent and such
estimators exist, for example, when $\mathcal{D}$ is a truncated Gaussian
distribution with mean bounded away from 0 or 1 and sufficiently small
variance.

  * •

Near Optimality of $\hat{p}_{\epsilon}^{\text{\rm priv }k}$ [Theorem 4.3].
Under slightly more stringent conditions on $\mathcal{D}$ and the assumption
that the maximum $k_{i}$ and median $k_{i}$ are within a factor of
$O(n\epsilon^{2}/\log n)$, we extend the upper bounds to the case when
$k_{i}$’s are also considered private information. The conditions are again
satisfied, for example, by truncated Gaussian distributions with mean bounded
away from 0 or 1 and sufficiently small variance.

  * •

Lower bound in terms of $k_{i}$ [Corollary 5.6]. Finally, we show that for any
sequence $k_{1},\cdots,k_{n}$ and variance $\sigma_{p}^{2}$ there exists
$k^{*}$ and a family of distributions $p\mapsto\mathcal{D}_{p}$ such that the
minimax optimal error among all unbiased estimators of $p$, for $p$ in the
range $[1/3,2/3]$, is lower bounded by

$\tilde{\Omega}\left(\min\left\\{\sqrt{\tfrac{\frac{k^{*}}{\epsilon^{2}}+\sum_{i=1}^{n}\min\\{k_{i},k^{*}\\}}{(\sum_{i=1}^{n}\min\\{k_{i},\sqrt{k_{i}k^{*}}\\})^{2}}},\frac{\sigma_{p}}{\sqrt{n}}\right\\}\right).$

We note that our main algorithmic results require concentration of the meta-
distribution $\mathcal{D}$. We note that in practice, this is not an
unreasonable assumption. For example, in the case of model evaluation, it may
be be reasonable to assume that a general model has similar accuracy for the
vast majority of users, or formally, that the model accuracy is well-
concentrated.

###  1.1 Related Work

Frequency estimation in the example-level privacy model has been well-studied
in the central (Dwork et al., 2006; Dwork and Roth, 2014) and local models
(Hsu et al., 2012; Erlingsson et al., 2014; Chen et al., 2020; Acharya and
Sun, 2019; Acharya et al., 2019). Similarly, private mean estimation has been
well studied in both central (Dwork et al., 2006; Hardt and Talwar, 2010) and
local models (Duchi et al., 2018; Duchi and Rogers, 2019; Bhowmick et al.,
2019) of privacy. These works have focused on providing example-level privacy
(rather than user-level) in settings with homogeneous data, i.e., i.i.d.
samples.

Liu et al. (2020) recently studied the problem of learning discrete
distributions in the homogeneous cases (same distribution and same number of
samples per user) with user-level differential privacy, and Levy et al. (2021)
extended such results to other statistical tasks. These works also consider
the setting with different number of samples per user although only via a
reduction to same number of samples by discarding the data of users that have
less than the median number of samples and effectively only using the median
number of samples from all the other users. This approach can be
asymptotically suboptimal for many natural distributions of $k_{i}$’s and is
also likely to be worse in practice. Previously, McSherry and Mironov (2009)
showed how to build a (user-level) differentially private recommendation
system, and McMahan et al. (2018) showed how to train a language model with
user-level differential privacy.

User-level differential privacy in the context of heterogeneous data
distributions has been studied in the constant $k_{i}$ setting Ozkara et al.
(2022). Much of the complexity in our setting arises from variation in the
$k_{i}$ values, which makes it challenging to maintain user-level privacy
while leveraging the additional data points from users with a large number of
data points.

The challenges to optimization due to data heterogeneity have also been
studied; Zhou and Cong (2018); Hanzely and Richtárik (2020), and Eichner et
al. (2019) study the approach of using different models for different groups
from a convex optimization point-of-view.

Mathematically, similar issues are addressed in meta-analysis (Borenstein et
al., 2021; Wikipedia contributors, 2021), where the heterogeneity comes from
different studies instead of different users. The non-private approach of
inverse variance weighting that we recap in Section 3 is standard in that
context.

##  2 Model and Preliminaries

Let $\mathcal{D}$ be a distribution on $[0,1]$ with (unknown) mean $p$ and
variance $\sigma_{p}^{2}$. We assume a population of $n\in\mathbb{N}$ users,
where each user $i\in[n]$ has a hidden variable $p_{i}\sim\mathcal{D}$ and
$k_{i}\in\mathbb{N}$ samples
$x_{i}^{1},\ldots,x_{i}^{k_{i}}\sim_{i.i.d.}Ber(p_{i})$. That is, the samples
of user $i$ are i.i.d. from a Bernoulli distribution with parameter $p_{i}$,
which we will denote $\mathcal{D}_{i}=$Ber$(p_{i})$. Assume without loss of
generality that individuals are sorted by their $k_{i}$, so that
$k_{1}\geq\cdots\geq k_{n}$. The hidden variables $p_{i}$ of each user are
unknown to the analyst. In the non-private setting, the samples $x_{i}^{j}$
and $k_{i}$ will be accessible to the analyst. In the private setting, access
to these data is constrained.

The analyst’s goal is to estimate the population mean $p$ with an estimator of
minimum variance in a manner that is differentially private with respect to
user data ($p_{i}$ and $\\{x_{i}^{j}\\}$). Each user provides their own
estimate of their $p_{i}$ to the analyst based on their data $x_{i}$:
$\widehat{p}_{i}=\frac{1}{k_{i}}\sum_{j=1}^{k_{i}}x_{i}^{j}$. The analyst can
then aggregate these (possibly along with other information) into her estimate
of $p$.

Let us first give some intuition for the distribution of these
$\widehat{p}_{i}$. Let $\mathcal{D}(k)$ be the distribution that first samples
$p_{i}\sim\mathcal{D}$, then samples $x_{1},\cdots,x_{k}\sim Ber(p_{i})$ and
finally outputs $\widehat{p}_{i}=\frac{1}{k}\sum_{i=1}^{k}x_{i}$. The
following lemma (proven in Appendix A) shows that the variance of
$\widehat{p}_{i}$ is larger than $\sigma_{p}^{2}$ and transitions from
$p(1-p)$ to $\sigma_{p}^{2}$ as $k$ increases (equivalently as
$\widehat{p}_{i}$ concentrates around $p_{i}$).

######  Lemma 2.1.

For all distributions $\mathcal{D}$ supported on $[0,1]$ with mean $p$ and
variance $\sigma_{p}^{2}$, $\sigma_{p}^{2}\leq p(1-p)$. Further,
$\mathbb{E}[\mathcal{D}(k)]=p$ and ${\rm
Var}(\mathcal{D}(k))=\frac{1}{k}p(1-p)+\left(1-\frac{1}{k}\right)\sigma_{p}^{2}$.

We assume that $k_{i}$ and $p_{i}$ are independent, so the amount of data an
individual has is independent of her data distribution. This is crucial for
the problem setup: in order for learning from the heterogeneous population to
be advantageous, there must a common meta-distribution is shared across all
individuals in the population, rather than a meta-distribution only for each
fixed $k_{i}$. If $k_{i}$ and $p_{i}$ can be arbitrarily correlated, then the
meta-distribution for each value of $k_{i}$ can be different. Hence, the best
solution in that setting is to learn on each sub-population (where the sub-
populations are defined by their value of $k_{i}$) separately. While this
assumption is natural in some settings, it is unlikely to hold in others – for
example, different writing styles that are more or less verbose. In future
work, it may be interesting to explore how various heterogeneity assumptions
affect learning algorithms.

###  2.1 Differential Privacy

Differential privacy (DP) (Dwork et al., 2006) informally limits the
inferences that can be made about an individual as a result of computations on
a large dataset containing their data. This privacy guarantee is achieved
algorithmically by randomizing the computation to obscure small changes in the
dataset. The definition of differential privacy requires a _neighbouring
relation_ between datasets. If two datasets $D$ and $D^{\prime}$ are
neighbours under the neighbouring relation, then differences between these two
datasets should be hidden by the private algorithm.

######  Definition 2.2 ( $(\epsilon,\delta)$-Differential Privacy (Dwork et
al., 2006)).

Given $\epsilon\geq 0$, $\delta\in[0,1]$ and a neighbouring relation $\sim$, a
randomized mechanism $\mathcal{M}:\mathfrak{D}~{}\rightarrow~{}\mathcal{Y}$
from the set of datasets to an output space $\mathcal{Y}$ is
$(\epsilon,\delta)$-_differentially private_ if for all neighboring datasets
$D\sim D^{\prime}\in\mathfrak{D}$, and all events $E\subseteq\mathcal{Y}$,

$\displaystyle\Pr[\mathcal{M}(D)\in E]\leq
e^{\epsilon}\cdot\Pr[\mathcal{M}(D^{\prime})\in E]+\delta,$

where the probabilities are taken over the random coins of $\mathcal{M}$. When
$\delta=0$, we may refer to this as _$\epsilon$ -differential privacy_.

When each user has a single data point, the neighbouring relation is typically
defined as: $D$ and $D^{\prime}$ are neighbours if they differ on the data of
a single individual, i.e., a single data point. In our setting where users
have multiple data points, we must distinguish between _user-level_ and
_event-level_ DP. The former considers $D$ and $D^{\prime}$ neighbours if they
differ on all data points associated with a single user, whereas the latter
considers $D$ and $D^{\prime}$ neighbours only if they differ on a _single_
data point, regardless of the number of data points contributed by that user.
Naturally, user-level DP provides substantially stronger privacy guarantees,
and is often more challenging to achieve from a technical perspective. In this
work, we will provide user-level DP guarantees.

Further, when defining user-level DP where users have heterogeneous quantities
of data, we also need to distinguish between settings where the number of data
points held by each user is protected information, and settings where it is
publicly known. We’ll refer to the former as _private $k$ user-level
differential privacy_, where the entry that differs between neighboring
databases can have arbitrarily different number of data points, and the latter
as _public-size user-level differential privacy_, where the amount of data
held by each user is the same in neighboring databases. Formally, let
$D_{i}=\\{x_{i}^{1},\cdots,x_{i}^{k_{i}}\\}$ be the data of user $i$ for each
$i\in[n]$. For private $k$ user-level differential privacy, we say $D$ and
$D^{\prime}$ are neighbours if there exists an index $i$ such that for all
$j\in[n]\backslash\\{i\\}$, $D_{j}=D_{j}^{\prime}$. For public-size user-level
differential privacy, we say $D$ and $D^{\prime}$ are neighbours if they are
neighbours under private $k$ user-level differential privacy and additionally
$|D_{i}|=|D_{i}^{\prime}|$ for all $i\in[n]$.

One standard tool for achieving $\epsilon$-differential privacy is the
_Laplace Mechanism_. For a given function $f$ to be evaluated on a dataset
$D$, the Laplace Mechanism first computes $f(D)$ and then adds Laplace noise
which depends on the _sensitivity_ of $f$, defined for real-valued functions
as

$\Delta f=\max_{D,D^{\prime}\text{ neighbors}}|f(D)-f(D^{\prime})|.$

The Laplace Mechanism outputs $\mathcal{M}_{L}(D,f,\epsilon)=f(D)+{\rm
Lap}(\Delta f/\epsilon)$, and is $(\epsilon,0)$-DP.

Differential privacy satisfies _robustness to post-processing_ , meaning that
any function of a DP mechanism will retain the same privacy guarantee. DP also
_composes adaptively_ , meaning that if an $(\epsilon_{1},\delta_{1})$-DP
mechanism and and an $(\epsilon_{2},\delta_{2})$-DP mechanism are both applied
to the _same dataset_ , then the entire process is
$(\epsilon_{1}+\epsilon_{2},\delta_{1}+\delta_{2})$-DP. _Parallel composition_
of DP mechanisms says that if DP mechanisms are applied to disjoint datasets,
then composition is not required. That is, if an
$(\epsilon_{1},\delta_{1})$-DP mechanism and and an
$(\epsilon_{2},\delta_{2})$-DP mechanism are each applied to _disjoint
datasets_ , then the entire process is
$(\max\\{\epsilon_{1},\epsilon_{2}\\},\max\\{\delta_{1},\delta_{2}\\})$-DP
with respect to both datasets together.

##  3 A Non-Private Estimator

We begin by illustrating the procedure for computing an optimal estimator
$\widehat{p}$ in the non-private setting. The general structure of the
estimator will be the same in both the private and non-private settings. The
analyst will compute the population-level mean estimate $\widehat{p}$ as a
weighted linear combination of the user-level estimates
$\widehat{p}_{i}$.111In the non-private setting, this restriction is without
loss of generality since the optimal estimator takes this form. In the private
setting this is still near-optimal; see Section 5 for more details. The key
question is how to derive the weights so that individuals with more reliable
estimates (i.e., larger $k_{i}$) have more influence over the final result.

Algorithm 1 Non-private Heterogeneous Mean Estimation $\widehat{p}$

Input: number of users $n$, number of samples held by each user
$(k_{1},\ldots,k_{n}\;s.t.\;k_{i}\geq k_{i+1}$), user-level estimates
$(\widehat{p}_{1},\cdots,\widehat{p}_{n})$.

1:Initial Estimates

2:$\widehat{p}^{\rm initial}=\sum_{i=9n/10}^{n}x_{i}^{1}$ $\triangleright$
Initial mean estimate

3:$\widehat{\sigma}_{p}^{2}=\tfrac{1}{\log n(\log
n-1)}\textstyle\sum_{i,j\in[\log n]}(\widehat{p}_{i}-\widehat{p}_{j})^{2}$
$\triangleright$ Initial variance estimate

4:Defining weights

5:for $i=\log n$ to $9n/10$ do

6: Compute $\widehat{\sigma}_{i}^{2}=\tfrac{1}{k_{i}}(\widehat{p}^{\rm
initial}-(\widehat{p}^{\rm
initial})^{2})+(1-\tfrac{1}{k_{i}})\widehat{\sigma}_{p}^{2}.$ $\triangleright$
Estimate individual variances

7: $\widehat{w_{i}}=\tfrac{1/\widehat{\sigma}_{i}^{2}}{\sum_{j=\log
n}^{9n/10}1/\widehat{\sigma}_{j}^{2}}$ $\triangleright$ Compute normalised
weights

8:Final Estimate

9:return $\widehat{p}=\textstyle\sum_{i=\log
n}^{n}\widehat{w_{i}}\widehat{p}_{i}$ $\triangleright$ Final estimate

Let $\sigma_{i}^{2}$ be the variance of $\widehat{p}_{i}$. In an idealized
setting where the $\sigma_{i}^{2}$ are all known, the analyst can minimize the
variance of the estimator by weighting each user’s estimate $\widehat{p}_{i}$
proportionally to the inverse variance of their estimate. The weights are then
normalised to ensure the estimate is unbiased. This approach yields the
following estimator, which is optimal in the non-private setting (Hartung et
al., 2008):

$\widehat{p}^{\rm
ideal}=\textstyle\sum_{i=1}^{n}w_{i}^{*}\widehat{p}_{i}\text{ where
}w_{i}^{*}=\tfrac{1/\sigma_{i}^{2}}{\sum_{j=1}^{n}1/\sigma_{j}^{2}}.$ (1)

In practice, the $\sigma_{i}^{2}$s are unknown, so the analyst must rely on
estimates to assign weights. Fortunately, the user-level variance
$\sigma_{i}^{2}$ can be expressed as a function of $k_{i}$ and the population
statistics $p$ and $\sigma_{p}^{2}$, as shown in Lemma 2.1:

$\sigma_{i}^{2}=\tfrac{1}{k_{i}}(p-p^{2})+(1-\tfrac{1}{k_{i}})\sigma_{p}^{2}.$
(2)

Now, $p$ and $\sigma_{p}^{2}$ are also unknown but since they are population
statistics, we can use simple estimators to obtain initial estimates. These
initial statistics can then be used to define the weights, resulting in a
refined estimate of the mean $p$. Specifically, as outlined in Algorithm 1, we
split users into three groups. The $\log n$ individuals with the most data are
used to produce an estimate of ${\rm Var}(\mathcal{D}({k_{\log n}}))$, which
serves as a proxy for $\sigma_{p}^{2}$. The $1/10$th of individuals with the
least data are used to produce an initial estimate of the mean $p$. The
remaining $9n/10-\log n$ individuals are used to produce the final estimate.
We split the individuals into separate groups to ensure the initial estimates
and the final estimate are independent so we can easily obtain variance bounds
on the final estimate. The specific sizes of the three groups are heuristic;
the exact fraction $1/10$ is not necessary. Under some mild conditions on
$\mathcal{D}$, and if $n$ is large enough, the error incurred by $\widehat{p}$
is within a constant factor of the error incurred by the ideal estimator
$\widehat{p}^{\rm ideal}$.222This can be observed by viewing the non-private
setting as a simplified version of the setting studied in Section 5, which
proves near-optimality of (truncated) linear estimators for this problem.

##  4 A Framework for Private Estimators

We now turn to our main result, which is a framework for designing
differentially private estimators for the mean $p$ of the meta-distribution
$\mathcal{D}$. We discussed in Section 3 the need for initial estimates of $p$
and $\sigma_{p}^{2}$ to weight the contributions of the users. In the non-
private setting, there are canonical, optimal choices of these estimators; the
empirical mean and empirical variance. In the private setting, these choices
are not canonical, and different estimators may perform better in different
settings. There is a considerable literature exploring various mean and
variance estimators for the homogeneous, single-data-point-per-user setting.
As such, we leave the choice of the specific initial mean and variance
estimators as parameters of the framework. This allows us to focus on the
nuances of the heterogeneous setting, not addressed in prior work. In Section
6, we give a specific pair of private mean and variance estimators that
provably perform well in our framework.

We will define three estimators: a ideal estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$ (only implementable if all the
$\sigma_{i}^{2}$ are known), and a realisable estimator
$\widehat{p}_{\epsilon}$ in the public-size user-level DP setting, and a
realisable estimator $\hat{p}_{\epsilon}^{\text{\rm priv }k}$ in the private
$k$ user-level DP setting. The main result in the public-size user-level DP
setting (Theorem 4.1) is that under some mild conditions and assuming $n$ is
sufficiently large, there exists an $(\epsilon,\delta)$-DP estimator
$\widehat{p}_{\epsilon}$ (Algorithm 2) such that for some constant $C$,

${\rm Var}(\widehat{p}_{\epsilon})\leq C\cdot{\rm
Var}(\widehat{p}_{\epsilon}^{\rm ideal}).$

In Section 4.4, we extend this result to the case where $k_{i}$s are private
and unknown to the analyst. We will maintain the optimality of the estimator
(up to logarithmic factors), under slightly more restrictive conditions
(Theorem 4.3).

###  4.1 The Complete Information Private Estimator

As in Section 3, we begin with a discussion of the ideal estimator if the
$\sigma_{i}$ were known. This ideal private estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$ has a similar form to $\widehat{p}^{\rm
ideal}$ with some crucial differences. The first main distinction is that
Laplace noise is added to achieve DP, where the standard deviation of the
noise must be scaled to the sensitivity of the statistic. A natural solution
would be to add noise directly to the non-private estimator $\widehat{p}^{\rm
ideal}$, but the sensitivity of this statistic is too high. In fact, the worst
case sensitivity of $\widehat{p}^{\rm ideal}$ is 1, which would result in the
noise that completely masks the signal. Thus, the first change we make is to
limit the weight of any individual’s contribution by setting

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

for some truncation parameter $T$. Analogous to the weights used in Section 3,
this choice of $w_{i}$ is still inversely proportional to $\sigma^{2}_{i}$ up
to an upper limit that depends on the truncation parameter $T$, and then
normalized to ensure the weights sum to 1 so the estimator is unbiased.
Intuitively, the parameter $T$ controls the trade-off between variance of the
weighted sum of individual estimates (which is minimized by assigning high
weight to low variance estimators) and variance of the noise added for privacy
(which is minimized by assigning roughly equal weight to all users).

We make one final modification to lower the sensitivity of the statistic.
Inspired by the Gaussian mean estimator of Karwa and Vadhan (2018), we
truncate the individual contributions $\widehat{p}_{i}$ into a sub-interval of
$[0,1]$. The truncation intervals $[a_{i},b_{i}]$ are chosen to be as small as
possible (to reduce the sensitivity and hence the noise added for privacy),
while simultaneously ensuring that $\widehat{p}_{i}\in[a_{i},b_{i}]$ with high
probability (to avoid truncating relevant information for the estimation). In
order to achieve this, we need a tail bound on the distribution $\mathcal{D}$.
To maintain generality for now, we assume there exists a known function
$f^{k}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ that gives high-probability
concentration guarantees of $\widehat{p}_{i}$ around $p$, and is defined such
that

$\Pr\left(\forall i,|\widehat{p}_{i}-p|\leq
f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\right)\geq 1-\beta.$

Appendix F presents a more detailed discussion of the structure of these
concentration functions and how they may be estimated if they are unknown to
the analyst.

We can now describe the full information, or _ideal_ estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$:

$\widehat{p}_{\epsilon}^{\rm
ideal}=\textstyle\sum_{i=1}^{n}w_{i}^{*}[\widehat{p}_{i}]_{a_{i}}^{b_{i}}+{\rm
Lap}(\tfrac{\max_{i}w_{i}^{*}|b_{i}-a_{i}|}{\epsilon}),$ (3)

where $[\widehat{p_{i}}]_{a_{i}}^{b_{i}}$ denotes the projection of
$\widehat{p_{i}}$ onto the interval $[a_{i},b_{i}]$ and

$\displaystyle a_{i}$
$\displaystyle=p-f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta),\quad
b_{i}=p+f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta),\;\text{ and
}\;w_{i}^{*}=\tfrac{\min\\{1/\sigma_{i}^{2},T^{*}/\sigma_{i}\\}}{\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},T^{*}/\sigma_{j}\\}}.$
(4)

We would like to choose the truncation parameter $T^{*}$ to minimise the
variance of the resulting estimator:

$\displaystyle{\rm Var}(\widehat{p}_{\epsilon}^{\rm ideal})$
$\displaystyle=\textstyle\sum_{i=1}^{n}(w_{i}^{*})^{2}{\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})+\max_{i}\tfrac{(w_{i}^{*})^{2}|b_{i}-a_{i}|^{2}}{\epsilon^{2}}.$
(5)

Although we do not know ${\rm Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})$
exactly, we do know that $[\widehat{p}_{i}]_{a_{i}}^{b_{i}}=\widehat{p}_{i}$
with high probability, and thus we can approximate ${\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})$ with $\sigma_{i}^{2}$. Throughout the
remainder of the paper, we will assume that $\beta$ is chosen such that
$\frac{1}{2}\sigma_{i}^{2}\leq{\rm Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}}).$
Thus, we will approximate the optimal truncation parameter by

$\displaystyle T^{*}$
$\displaystyle=\arg\min_{T}\sum_{i=1}^{n}(w_{i}^{*})^{2}\sigma_{i}^{2}+\max_{i}\frac{(w_{i}^{*})^{2}|b_{i}-a_{i}|^{2}}{\epsilon^{2}}$
$\displaystyle=\arg\min_{T}\tfrac{1}{{(\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},T/\sigma_{i}\\})^{2}}}(\textstyle\sum_{i=1}^{n}\min\\{1/\sigma_{i}^{2},{T^{2}}\\}+\max_{i}\tfrac{\min\\{1/\sigma_{i}^{4},T^{2}/\sigma_{i}^{2}\\}|b_{i}-a_{i}|^{2}}{\epsilon^{2}}).$
(6)

We’ll show in Section 5 that under some conditions on the Fisher information
of $\mathcal{D}(k)$, $\widehat{p}_{\epsilon}^{\rm ideal}$ is optimal up to
logarithmic factors among all private unbiased estimators for heterogeneous
mean estimation.

######  Example 1.

As a simple example, suppose that $p\in(\frac{1}{3},\frac{2}{3})$,
$\sigma_{p}=1/\sqrt{n}$, and $k_{i}=\lceil\frac{n}{i}\rceil$. In this case, an
asymptotically optimal non-private estimator averages all the $\sum
k_{i}=O(n\log n)$ available samples. It can be shown that this gives us an
unbiased estimator with standard deviation $\Theta(\frac{1}{\sqrt{n\log n}})$.
A naive sensitivity-based noise addition method will give us privacy error
$O(\frac{1}{\varepsilon\log n})$, since the weight of the first user in this
average is $\Theta(1/\log n)$. Our truncation-based algorithm will truncate
the $i$th user’s contribution to a range of width $\sqrt{\frac{\log
n}{k_{i}}}\approx\sqrt{\frac{i\log n}{n}}$. Applying our algorithm would then
give us privacy error $\Theta(\frac{1}{\varepsilon\sqrt{n\log n}})$. In other
words, for constant $\varepsilon$, privacy does not have an asymptotic cost.
We remark that in this case, any uniform weighted average will incur
asymptotically larger standard deviation $\Omega(\frac{1}{\sqrt{n}})$.

###  4.2 Realizable Private Heterogeneous Mean Estimation

Our goal in this section is to design a realizable estimator
$\widehat{p}_{\epsilon}$ that is competitive with the ideal estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$. As in the non-private setting, we divide
the individuals into three groups. The first group, consisting of the $n/10$
individuals with the lowest $k_{i}$ will be used to compute the initial mean
estimate $\widehat{p}_{\epsilon}^{\rm initial}$. The $L$ individuals with the
largest $k_{i}$ will be used to compute the initial variance estimate
$\widehat{\sigma}_{p}^{2}$. These will respectively be computed using private
subroutines $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$, which each provide event-level DP, as
they each operate on only a single point from each user. These initial
estimates will be plugged into expressions to compute
$\widehat{\sigma}_{i}^{2}$, $\widehat{a_{i}}$, and $\widehat{b_{i}}$ for the
remaining individuals $L+1\leq i\leq 9n/10$. As in the non-private setting,
the specific sizes of these groups are heuristic. The important thing is that
the size of the first two groups are large enough that the resulting mean and
variance estimates are sufficiently accurate, and the last group contains
$\Theta(n)$-users whose $k_{i}$ is above the median.

Since the estimate $\widehat{p}_{\epsilon}^{\rm initial}$ used in
$\widehat{a_{i}}$ and $\widehat{b_{i}}$ may have additional error up to
$\alpha$ (which will depends on the additive accuracy guarantee of
$\rm\texttt{mean}_{\epsilon,\delta}$), we shift these estimates by an additive
$\alpha$ to account for this error. Next, all of these intermediate estimates
and the user-level mean estimates $\widehat{p}_{i}$ from users $L+1\leq i\leq
9n/10$ will be used to compute the optimal weight cutoff $\widehat{T}^{*}$,
the optimal weights $\widehat{w}_{i}^{*}$ for each user $L+1\leq i\leq 9n/10$,
and finally the estimator $\widehat{p}_{\epsilon}$ as a weighted sum of the
truncated user-level estimates
$[\widehat{p}_{i}]_{\widehat{a}_{i}}^{\widehat{b}_{i}}$ plus Laplace noise.
This procedure is presented in full detail in Algorithm 2.

Algorithm 2 Private Heterogeneous Mean Estimation $\widehat{p}_{\epsilon}$

Input parameters: privacy parameters $\epsilon>0$, $\delta\in[0,1]$, desired
high probability bound $\beta\in[0,1]$, number of users $n$, an
$(\epsilon,\delta)$-DP mean estimator $\rm\texttt{mean}_{\epsilon,\delta}$,
error guarantee on $\rm\texttt{mean}_{\epsilon,\delta}$ $\alpha>0$, an
$(\epsilon,\delta)$-DP variance estimator
$\texttt{variance}_{\epsilon,\delta}$, number of samples for variance
estimator $L$, and number of samples held by each user
$(k_{1},\ldots,k_{n}\;s.t.\;k_{i}\geq k_{i+1}$).
Input data: User-level estimates $(\widehat{p}_{1},\cdots,\widehat{p}_{n})$

1:Initial Estimates

2:$\widehat{p}_{\epsilon}^{\rm
initial}=\rm\texttt{mean}_{\epsilon,\delta}(x_{9n/10+1}^{1},\cdots,x_{n}^{1})$
$\triangleright$ Initial mean estimate

3:$\widehat{\sigma}_{p}^{2}=\texttt{variance}_{\epsilon,\delta}(\widehat{p}_{1},\cdots,\widehat{p}_{L})$
$\triangleright$ Initial variance estimate

4:Defining weights and truncation

5:for $i=L+1$ to $9n/10$ do

6: Compute
$\widehat{\sigma}_{i}^{2}=\tfrac{1}{k_{i}}(\widehat{p}_{\epsilon}^{\rm
initial}-(\widehat{p}_{\epsilon}^{\rm
initial})^{2})+(1-\tfrac{1}{k_{i}})\widehat{\sigma}_{p}^{2}.$ $\triangleright$
Estimate individual variances

7: $\widehat{a_{i}}=\widehat{p}_{\epsilon}^{\rm
initial}-\alpha-f^{k_{i}}_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta)$

8: $\widehat{b_{i}}=\widehat{p}_{\epsilon}^{\rm
initial}+\alpha+f^{k_{i}}_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta)$
$\triangleright$ Estimate truncation parameters

9:
$\widehat{T}^{*}=\arg\min_{T}\frac{\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\widehat{\sigma}_{i}^{2}},{T^{2}}\\}+\max_{{L+1}\leq
i\leq{9n/10}}\frac{\min\\{1/\widehat{\sigma_{i}}^{4},{T^{2}/\widehat{\sigma}_{i}^{2}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}}{{(\sum_{i=L+1}^{9n/10}\min\\{1/\widehat{\sigma}_{j}^{2},T/\widehat{\sigma}_{i}\\})^{2}}}$

10:$\triangleright$ Compute weight truncation

11:for $i=L+1$ to $9n/10$ do

12:
$\widehat{w_{i}}^{*}=\frac{\min\\{1/\widehat{\sigma}_{i}^{2},\widehat{T}^{*}/\widehat{\sigma_{i}}\\}}{\sum_{j=L+1}^{9n/10}\min\left\\{1/\widehat{\sigma}_{j}^{2},\widehat{T}^{*}/\widehat{\sigma}_{i}\right\\}}$
$\triangleright$ Compute weights

13:Final Estimate

14:
$\Lambda=\max_{i\in[L+1,9n/10]}\frac{\min\\{1/\widehat{\sigma}_{i}^{2},\widehat{T}^{*}/\widehat{\sigma_{i}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|}{\sum_{j=L+1}^{9n/10}\min\left\\{1/\widehat{\sigma}_{j}^{2},\widehat{T}^{*}/\widehat{\sigma}_{i}\right\\}}$
$\triangleright$ Compute sensitivity

15:Sample $Y\sim{\rm Lap}\left(\frac{\Lambda}{\epsilon}\right)$
$\triangleright$ Sample noise added for privacy

16: return
$\widehat{p}_{\epsilon}=\sum_{i=L+1}^{9n/10}\widehat{w_{i}}^{*}[\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}+Y$
$\triangleright$ Final estimate

For the remainder of this section, we turn to establishing the accuracy
requirements of $\rm\texttt{mean}_{\epsilon,\delta}$ and
$\texttt{variance}_{\epsilon,\delta}$ that ensure that the variance of
$\widehat{p}_{\epsilon}$ is within a constant factor of the variance of
$\widehat{p}_{\epsilon}^{\rm ideal}$.

######  Theorem 4.1.

For any $\epsilon>0$, $\delta\in[0,1]$, $\alpha>0$, $\beta\in[0,1]$,
$n\in\mathbb{N}$, $0\leq L\leq 3n/5$, $(\epsilon,\delta)$-DP mean estimator
$\rm\texttt{mean}_{\epsilon,\delta}$, $(\epsilon,\delta)$-DP variance
estimator $\texttt{variance}_{\epsilon,\delta}$, and sequence
$(k_{1},\ldots,k_{n}\;s.t.\;k_{i}\geq k_{i+1}$), Algorithm 2 is
$(\epsilon,\delta)$-DP. If,

  * •

$\rm\texttt{mean}_{\epsilon,\delta}$ is such that given $n/10$ samples from
$\mathcal{D}$, with probability $1-\beta$, $|p-\widehat{p}_{\epsilon}^{\rm
initial}|\leq f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ and
$\widehat{p}_{\epsilon}^{\rm initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})\in\left[\tfrac{1}{2}p(1-p),\tfrac{3}{2}p(1-p)\right]$,

  * •

$\texttt{variance}_{\epsilon,\delta}$ is such that given $L$ samples from
$\mathcal{D}(k)$, with probability $1-\beta$,
$\widehat{\sigma}_{p}^{2}\in\left[{\rm Var}(\mathcal{D}({k})),~{}8{\rm
Var}(\mathcal{D}({k}))\right]$,

  * •

the $k_{i}$s are such that $\tfrac{k_{1}}{k_{n/2}}\leq\tfrac{n/2-L}{L}$,

then with probability $1-2\beta$, ${\rm Var}(\widehat{p}_{\epsilon})\leq
C\cdot{\rm Var}(\widehat{p}_{\epsilon}^{\rm ideal})$ for some absolute
constant $C$.

The final assumption ensures that the $L$ users with the most data can not
estimate the mean of meta-distribution alone. In the setting where these $L$
users can give a very accurate estimate of the mean, we conjecture that there
is little benefit in incorporating the data of the remaining users. If this
assumption does not hold, then an estimator that better utilizes only the top
log $n$ users may be optimal. The strictness of this condition depends on the
sample complexity of estimating the variance of $\mathcal{D}(k)$. We’ll see in
Section 6.2 that for well-behaved distributions like Gaussians, the sample
complexity for obtaining a constant multiplicative approximation of ${\rm
Var}(\mathcal{D}(k))$ is $O(\log(1/\beta)/\epsilon)$. Thus for sufficiently
well-behaved distributions, up to logarithmic factors, this condition simply
requires that the number of data points held by the user with the most data is
at most $n$ times the number of data points of the median user. If $n$ is
large, then this is unlikely to be a limiting factor.

The first two conditions of Theorem 4.1 ensure that the mean and variance
estimates are sufficiently accurate to use in the remainder of the algorithm.
Notice that the initial estimates do not need to be especially accurate. In
fact, provided $p$ is not too close to 0 or 1, the DP mean estimator that
simply adds noise to the sample mean achieves sufficient accuracy (see Lemma
6.1 for details). In Section 6, we also give a DP variance estimator that
achieves the desired accuracy guarantee using only $L=\log n/\epsilon$
samples, under some mild conditions (Lemma 6.4). Thus the set of mean and
variance estimators that satisfy the accuracy requirements of Theorem 4.1 are
non-empty. We note that the constants $1/2$ , $3/2$ and $8$ in Theorem 4.1 are
not intrinsic; any constant multiplicative factors will suffice. We also note
that the specific sizes of the three groups outlined in Algorithm 2 are
heuristic and can be varied to ensure that the initial estimator achieves the
required accuracy.

A full proof of Theorem 4.1 is given in Appendix B; we present intuition and a
proof sketch here.

The main distinction between $\widehat{p}_{\epsilon}^{\rm ideal}$ and
$\widehat{p}_{\epsilon}$ is the use of the output of the estimators
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
to estimate $\sigma_{i}^{2}$, $a_{i}$ and $b_{i}$. Thus, the main component of
the proof of Theorem 4.1 is to show that the conditions stated in the theorem
are enough to ensure that $\widehat{\sigma_{i}}^{2}$, $\widehat{a}_{i}$ and
$\widehat{b}_{i}$ are sufficiently accurate.

######  Lemma 4.2.

Given $\widehat{p}_{\epsilon}^{\rm initial}$, $\widehat{\sigma}_{p}^{2}$, and
$k_{i}$, define
$\widehat{\sigma_{i}}^{2}=\frac{1}{k_{i}}\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})+\frac{k_{i}-1}{k_{i}}\widehat{\sigma}_{p}^{2}$. Under the conditions
of Theorem 4.1, for all $i>L$, we have
$\widehat{\sigma_{i}}^{2}\in\left[\frac{1}{2}\sigma_{i}^{2},9.5\sigma_{i}^{2}\right]$
and $|\widehat{b}_{i}-\widehat{a}_{i}|\leq 4|b_{i}-a_{i}|$.

A detailed proof of Lemma 4.2 is presented in Appendix B. Lemma 4.2 implies
that the individual variance estimates used in the weights, and the truncation
parameters are accurate up to constant multiplicative factors. The main
ingredient left then is to show that using only a subset of the population in
the final estimate only affects the performance up to a multiplicative factor.
Under the assumption that $\frac{k_{\max}}{k_{\rm med}}\leq\frac{n/2-L}{L}$,
where $\sigma_{k_{\max}}^{2}={\rm Var}(\widehat{p}_{1})$ and $\sigma_{k_{\rm
med}}^{2}={\rm Var}(\widehat{p}_{n/2})$ then

$\displaystyle\sigma_{k_{\rm med}}^{2}$ $\displaystyle=\tfrac{1}{k_{\rm
med}}p(1-p)+(1-\tfrac{1}{k_{\rm med}})\sigma_{p}^{2}$
$\displaystyle\leq\tfrac{n/2-L}{L}\tfrac{1}{k_{\max}}p(1-p)+(1-\tfrac{1}{k_{\max}})\sigma_{p}^{2}$
$\displaystyle\leq\tfrac{n/2-L}{L}\sigma_{k_{\max}}^{2}.$ (7)

We use this to show that for any truncation parameter $T$,

$\textstyle\sum_{i=1}^{n}\min\\{\tfrac{1}{\sigma_{i}^{2}},\tfrac{T}{\sigma_{i}}\\}\leq
4\textstyle\sum_{i=L+1}^{9n/10}\min\\{\tfrac{1}{\sigma_{i}^{2}},\tfrac{T}{\sigma_{i}}\\}.$

Using this, along with the bounds on estimated quantities from Lemma 4.2, we
show that with high probability, the variance of the our estimator
$\widehat{p}_{\epsilon}$ is within a constant factor of ${\rm
Var}(\widehat{p}_{\epsilon}^{\rm ideal})$, as given in Equation (5):

$\displaystyle{\rm Var}(\widehat{p}_{\epsilon})$
$\displaystyle=\tfrac{\sum_{i=L+1}^{9n/10}\min\\{\tfrac{1}{\widehat{\sigma_{i}}^{4}},\tfrac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}\\}\sigma_{i}^{2}+\max_{i}\tfrac{\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},{\tfrac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}}{(\textstyle\sum_{j=L+1}^{9n/10}\min\\{1/\widehat{\sigma_{j}}^{2},\tfrac{\widehat{T}^{*}}{\widehat{\sigma_{i}}}\\})^{2}}$
(8) $\displaystyle\leq O({\rm Var}(\widehat{p}_{\epsilon}^{\rm ideal})).$

We remark that this framework is amenable to being performed in a federated
manner if one has private federated mean and variance estimators. Steps (6) -
(8) and Step (12) can be performed locally. Steps (9) and the final sum in
Step (16) would need to be altered to fit the federated framework. We will see
in Section 4.4 that it is sufficient to replace Step (9) with an estimate of
$\frac{1}{\sigma_{L}}$ (the inverse standard deviation of the user with the
$L$-th most data). The final step is then a simple addition with output
perturbation, which can be performed in a federated manner (e.g., McMahan et
al. (2017); Kairouz et al. (2021)).

###  4.3 Special Case: The constant $p_{i}$ case.

In the previous section, we considered the setting where there was
heterogeneity in both the users’ distributions (i.e., the $p_{i}$s were not
constant), as well as the number of data points that they each held (i.e., the
$k_{i}$s were not constant). In the absence of variation in the $p_{i}$, each
user is sampling from the same distribution ${\rm Ber}(p)$. When privacy is
not a concern, this setting reduces to the single-data-point-per-user setting
where the sample size is increased to $\sum_{i=1}^{n}k_{i}$. However, under
the constraint of user-level differential privacy, this setting is distinct
from the single-data-point-per-user setting, since we need to protect the
entirety of each users data set. In fact, much of the complexity of Algorithm
2 is required even in this simpler case. In particular, the truncated inverse
variance weighting is still required in this case when there is variation in
the $k_{i}$. In fact, the only step of Algorithm 2 that is not required is
Step 3, since already know that $\sigma_{p}^{2}=0$. Since there is no variance
in $\mathcal{D}$, the high probability bound
$f^{k_{i}}_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta)$ is just due to the
randomness in the binomial distribution ${\rm Bin}(k_{i},p)$, which comes from
averaging $k_{i}$ samples drawn from ${\rm Ber}(p)$.

When $\sigma_{p}^{2}=0$, $\sigma_{i}$ has the simple formula
$\sigma_{i}=\frac{\sqrt{p(1-p)}}{k_{i}}$ and we can directly translate from
the truncation threshold $T$ on $\sigma_{i}$ to a truncation threshold $k$ on
$k_{i}$, $T=\frac{\sqrt{p(1-p)}}{k}$. Further, if we assume that all the
$k_{i}$ are large enough ($\min k_{i}\geq 2\ln(1/\delta)/p$) then we also have
the simple formula
$f^{k_{i}}_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta)=\sqrt{\frac{3p\ln(2/\beta)}{k_{i}}}$.
We can plug these into Equation (4.1) (recall that $T^{*}$ is defined as the
truncation threshold that minimizes the variance of
$\widehat{p}_{\epsilon}^{\rm ideal}$) to obtain the following formula for the
variance of $\widehat{p}_{\epsilon}^{\rm ideal}$, and hence the variance of
$\widehat{p}_{\epsilon}$ is:

$\displaystyle\min_{k}\tfrac{p(1-p)\textstyle\sum_{i=1}^{n}\min\\{k_{i},k\\}+6p\ln(2/\beta)\tfrac{k}{\epsilon^{2}}}{{(\sum_{j=1}^{n}\min\\{k_{i},\sqrt{k_{i}k}\\})^{2}}}.$
(9)

Even in the private setting, one can reduce to the single-data-point-per-user
setting by reducing the sample size by a factor of 2, and forcing the $n/2$
users with the most data points to produce their estimate $\hat{p_{i}}$ using
only $k_{\rm med}$ (the median $k_{i}$) data points. Then each estimate
$\hat{p_{i}}$ is a sample from the same distribution and we can compute their
mean. To the best of our knowledge, all the prior work in the private
literature that handles variations in $k_{i}$ follows this formula. However,
not only does this algorithm reduce the sample size by a factor of 2, it also
unnecessarily hinders the contribution of users with many data points. As a
simple example, suppose that all the users have a single data point, except
for $\sqrt{n}$ users, which have $n$ data points. Then the algorithm which
forces $n/2$ of the users to use the median number of data points has an error
rate of $\Theta(\frac{1}{n}+\frac{1}{n^{2}\epsilon^{2}})$ assuming that $p$ is
bounded away from 0 or 1. Letting $k=n$ in Equation 9 implies that that the
truncated inverse variance weighted algorithm in the previous section is
better able to utilise the data of the users with high $k_{i}$s, resulting in
an error rate of $O(\frac{1}{n^{3/2}}+\frac{1}{n^{2}\epsilon^{2}})$.

###  4.4 Extension: private $k$ user-level differential privacy setting

Let us now turn to our problem in the private $k$ user-level differential
privacy setting, where the $k_{i}$s are considered private and require formal
privacy protections. We will need to add considerably more machinery to
Algorithm 2 to make it private under this stronger notion of privacy. Under
public-size user-level privacy, the quantities $\hat{T}^{*}$ (the weight
truncation parameter) and $\Lambda$ (the sensitivity of the final estimate) in
Algorithm 2 do not pose privacy concerns since they only depend on the private
data $\widehat{p}_{i}$ through the $\widehat{p}_{\epsilon}^{\rm initial}$ and
$\widehat{\sigma}_{i}^{2}$, which are both produced differentially privately.
However, both these quantities depend on the $k_{i}$ directly, and hence care
needs to be taken when using them under private $k$ user-level DP.

In Algorithm 3, we outline the extension of Algorithm 2 to satisfy private $k$
user-level differential privacy. It is different to Algorithm 2 in two main
ways: the method for truncating the weights and the method for computing the
scale of the noise needed to maintain privacy.

Algorithm 3 Private Heterogeneous Mean Estimation
$\hat{p}_{\epsilon}^{\text{\rm priv }k}$

Input parameters: Privacy parameters $\epsilon>0$, $\delta\in[0,1]$, desired
high probability bound $\beta\in[0,1]$, number of users $n$, an
$(\epsilon,\delta)$-DP mean estimator $\rm\texttt{mean}_{\epsilon,\delta}$,
error guarantee on $\rm\texttt{mean}_{\epsilon,\delta}$ $\alpha>0$, an
$(\epsilon,\delta)$-DP variance estimator
$\texttt{variance}_{\epsilon,\delta}$, number of samples for variance
estimator $L$, an upper bound on the total number of data points held by a
single user $k_{\max}$, an $\epsilon$-DP estimator of the $\ell$th order
statistic $\texttt{EM}_{\epsilon}(\cdot;\ell,k_{\max})$.
Input data: Number of samples held by each user
$(k_{1},\ldots,k_{n}\;s.t.\;k_{i}\geq k_{i+1}$), and user-level estimates
$(\widehat{p}_{1},\cdots,\widehat{p}_{n})$.

1:Initial Estimates

2:$\widehat{p}^{\rm
initial}=\rm\texttt{mean}_{\epsilon,\delta}(x_{9n/10+1}^{1},\cdots,x_{n}^{1})$
$\triangleright$ Initial mean estimate

3:$\widehat{\sigma}_{p}^{2}=\texttt{variance}_{\epsilon,\delta}(\widehat{p}_{1},\cdots,\widehat{p}_{L})$
$\triangleright$ Initial variance estimate

4:Compute Sensitivity Proposal

5:$\widehat{k_{L}}=\texttt{EM}_{\epsilon}(k_{1},\cdots,k_{n};L,k_{\max})$
$\triangleright$ Compute $L$-th order statistic

6:for $i\in[L+1,9n/10]$ do

7: $\widetilde{k_{i}}=\min\\{k_{i},\widehat{k_{L}}\\}$

8:
${\widetilde{\sigma_{i}}}^{2}=\tfrac{1}{\widetilde{k_{i}}}(\widehat{p}_{\epsilon}^{\rm
initial}-(\widehat{p}_{\epsilon}^{\rm
initial})^{2})+(1-\tfrac{1}{\widetilde{k_{i}}})\widehat{\sigma_{p}}^{2}.$

9: $v_{i}=\frac{1}{{\widetilde{\sigma_{i}}}^{2}}$ $\triangleright$ Compute
truncated, unnormalised weights

10:${\widehat{\sigma_{\min}}}^{2}=\tfrac{1}{\widehat{k_{L}}}(\widehat{p}_{\epsilon}^{\rm
initial}-(\widehat{p}_{\epsilon}^{\rm
initial})^{2})+(1-\tfrac{1}{\widehat{k_{L}}})\widehat{\sigma_{p}}^{2}.$

11:$\widehat{N}=\sum_{j=L+1}^{9n/10}v_{i}+{\rm
Lap}\left(\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\right)-\frac{1}{\epsilon{\widehat{\sigma_{\min}}}^{2}}\ln(2\delta)$
$\triangleright$ Compute noisy normalisation term

12:$\Lambda=12\frac{f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\widehat{\sigma_{\min}}^{2}\widehat{N}}$
$\triangleright$ Compute local sensitivity proposal

13:Propose-Test-Release on
$\mathcal{M}(\cdot\;;\widehat{k_{L}},n,\widehat{p}_{\epsilon}^{\rm
initial},\widehat{\sigma}_{p}^{2},\alpha)$

14:$D_{T}=\\{(\widehat{p}_{i},k_{i})\\}_{i\in[L+1:9n/10]}$

15:$\kappa^{*}=\arg\max\\{\kappa\in\mathbb{N}\;|\;\forall D^{\prime}\text{
s.t. }D^{\prime}\text{ is a }\kappa\text{-neighbor of
}D_{T},\text{\rm{LS}}(\mathcal{M}(\cdot;\widehat{k_{L}},9n/10-L,\widehat{p}_{\epsilon}^{\rm
initial},\widehat{\sigma}_{p}^{2},\alpha);D^{\prime})\leq\Lambda\\}$

16: $\triangleright$ Compute distance to high sensitivity dataset

17:$\tilde{\kappa}=\kappa^{*}+{\rm Lap}(1/\epsilon)$

18:if $\tilde{\kappa}<\frac{\log(1/\delta)}{\epsilon}$ then

19: return $\hat{p}_{\epsilon}^{\text{\rm priv }k}=\widehat{p}_{\epsilon}^{\rm
initial}$ $\triangleright$ Return initial estimate if proposed local
sensitivity too small

20:else

21: Sample $Y\sim{\rm Lap}\left(\frac{\Lambda}{\epsilon}\right)$
$\triangleright$ Sample noise added for privacy

22: return $\hat{p}_{\epsilon}^{\text{\rm priv
}k}=\mathcal{M}(D_{T};\widehat{k_{L}},9n/10-L,\widehat{p}_{\epsilon}^{\rm
initial},\widehat{\sigma}_{p}^{2},\alpha)+Y$ $\triangleright$ Final estimate

Algorithm 4 Truncated weighted mean,
$\mathcal{M}(\cdot;k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)$

Input: number of users $n$, number of samples held by each user
$(k_{1},\ldots,k_{n})$, user-level estimates
$(\widehat{p}_{1},\cdots,\widehat{p}_{n})$, desired upper bound $k_{\max}$,
mean estimate $\hat{p}$, variance estimate $\hat{\sigma_{p}^{2}}$, accuracy on
mean estimate $\alpha$

1:for $i\in[n]$ do

2: $\widetilde{k_{i}}=\min\\{k_{i},k_{\max}\\}$

3:
$\widetilde{a_{i}}=\hat{p}-\alpha-f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)$

4:

5:
$\widetilde{b_{i}}=\hat{p}+\alpha+f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)$

6:

7:
${\widetilde{\sigma_{i}^{2}}}=\tfrac{1}{\widetilde{k_{i}}}(\hat{p}-(\hat{p})^{2})+(1-\tfrac{1}{\widetilde{k_{i}}})\hat{\sigma_{p}^{2}}.$

8: $v_{i}=\frac{1}{{\widetilde{\sigma_{i}^{2}}}}$

9:Return
$\frac{\sum_{i\in[n]}v_{i}[\widehat{p}_{i}]_{\widehat{a_{i}}}^{\widehat{b_{i}}}}{\sum_{i\in[n]}v_{i}}$

The first significant change in Algorithm 3 is how the sensitivity parameter
$\Lambda$ is chosen. The final statistic is more sensitive under the view of
private $k$ user level privacy; the weight of every user can change as a
result of a single user changing the amount of data they hold (due to the
resulting change in the normalisation constant). Rather than an upper bound on
the global sensitivity, $\Lambda$ as defined in Algorithm 3, is, with high
probability, an upper bound on the _local_ sensitivity of all databases that
lie in a neighbourhood of $D$. Given a function $f$ from the set of databases
to $\mathbb{R}$, and a database $D$, the _local sensitivity_ of $f$ at $D$ is
defined by $\text{\rm{LS}}(f;D)=\max_{D^{\prime}\text{ neighbour of
}D}|f(D)-f(D^{\prime})|.$ We use a standard framework from the differential
privacy literature called propose-test-release (PTR) (Dwork and Lei, 2009) to
privately verify that $\Lambda$ is indeed an upper bound on the local
sensitivity of all databases in a neighbourhood of $D$, which allows us to
safely add noise proportional to $\Lambda$ to privatise the final statistic. A
database $D^{\prime}$ is said to be a $\kappa$-neighbour of $D$ if it differs
from $D$ on the data of at most $\kappa$ data subjects, and if it contains the
same number of data subjects.

Next, the function $\mathcal{M}$ as described in Algorithm 4 incorporates the
truncation of weights in a slightly different (but nearly equivalent) manner
to Algorithm 2, but is otherwise the same as Algorithm 2, without the addition
of noise. Observe that choosing a truncation parameter $T$ is equivalent to
choosing an integer $k$ such that $T=1/{\rm Var}(\mathcal{D}(k))$, so
$\widehat{k_{L}}$ plays the role in Algorithm 3 that $T^{*}$ plays in
Algorithm 2. The statistic $\widehat{k_{L}}$ is a private estimate of the
$L$-th order statistic of the set $\\{k_{1},\cdots,k_{n}\\}$. Since the only
users that participate in the final estimate (and hence have their data
truncated) all have $k_{i}<k_{L}$, this algorithm attempts to find the
smallest truncation parameter such that no data are actually truncated. We
will show that provided either $\epsilon$ is not too small or the ratio
$k_{\max}/k_{\rm med}$ is not too large, this level of truncation is
sufficient. There are several existing algorithms in the literature that can
be used to privately estimate the $L$-th order statistic $\widehat{k_{L}}$. A
simple algorithm (Dwork and Lei, 2009; Thakurta and Smith, 2013; Johnson and
Shmatikov, 2013; Alabi et al., 2020; Asi and Duchi, 2020) that estimates the
order statistic using standard differential privacy framework called the
Exponential Mechanism (EM) (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). In order for this algorithm to
produce accurate results, we need an upper bound on the maximum number of data
points a single user can have; we will call this number $k_{\max}$.

######  Theorem 4.3.

For any $\epsilon>0$, $\delta\in[0,1]$, $\beta\in[0,1]$, $n\in\mathbb{N}$,
$\alpha>0$, $L\in[n]$ $(\epsilon,\delta)$-DP mean estimator
$\rm\texttt{mean}_{\epsilon,\delta}$, $(\epsilon,\delta)$-DP variance
estimator $\texttt{variance}_{\epsilon,\delta}$, $k_{\max}\in\mathbb{N}$,
$\epsilon$-DP estimator of the $\ell$th order statistic
$\texttt{EM}_{\epsilon}(\cdot;\ell,k_{\max})$, Algorithm 3 is
$(3\epsilon,2\delta)$-DP. Let
$\Upsilon=\frac{\log(1/\delta)}{\epsilon}+\frac{\ln(1/\delta)\ln(1/\beta)}{\epsilon}$.
If the conditions of Theorem 4.1 hold and

  * •

$\frac{1}{2}\frac{1}{\epsilon}(\ln k_{\max}+\ln(1/\beta))\leq L\leq n/4$,

  * •

$\frac{k_{\max}}{k_{\text{med}}}\leq\min\left\\{\frac{\log\frac{n}{\beta}}{\log\frac{n^{\Upsilon+1}}{\beta}}\frac{n-\Upsilon-1}{2},\frac{n-1}{2(\Upsilon+1)},\frac{\epsilon^{2}(n/2-L-1)}{\log^{2}(n/\beta)},\frac{(n/4-1)\epsilon}{3\ln(2/\delta)}\right\\}$,

  * •

for all $k\leq k_{\max}$, $\max\\{\alpha,\sigma_{k}\\}\leq
f^{k}_{\mathcal{D}}(n,\hat{\widehat{\sigma}_{p}}^{2},\beta)\leq
2\sigma_{k}\sqrt{\log(n/\beta)}$, where $\sigma_{k}^{2}={\rm
Var}(\mathcal{D}(k))$

  * •

for any set $I\subset[n]$, with probability $1-\beta$, $\left|\frac{\sum_{i\in
I}v_{i}\widehat{p}_{i}}{\sum_{i\in I}v_{i}}-p\right|\leq 2\sqrt{{\rm
Var}\left(\frac{\sum_{i\in I}v_{i}\widehat{p}_{i}}{\sum_{i\in
I}v_{i}}\right)\log(1/\beta)}$,

then with probability $1-4\beta$, ${\rm Var}(\hat{p}_{\epsilon}^{\text{\rm
priv }k})\leq\tilde{O}\left({\rm Var}(\widehat{p})\right)$

Theorem 4.3 implies that under some mild conditions, the variance of
$\hat{p}_{\epsilon}^{\text{\rm priv }k}$ is within a constant factor of the
variance of $\widehat{p}$, the non-private realisable estimator. While the
conditions of this theorem may seem intimidating, they are not particularly
stringent for reasonable parameter settings.

  * •

Conditions on L. In Section 4.2, when discussing the conditions of Theorem
4.1, we discussed that $L=\tilde{O}(1/\epsilon)$ is sufficient for learning a
constant multiplicative approximation to $\sigma_{p}^{2}$ for sufficiently
well-behaved distributions. We’ll give such an example estimator in Section
6.2. If we increase $L$ to $O(\log(n)/\epsilon)$ then the third condition in
Theorem 4.1 (which we still need to satisfy) becomes only slightly more
restrictive, and we can satisfy the first condition of Theorem 4.3 provided
$k_{\max}$ and $1/\beta$ are both polylogarithmic in $n$.

  * •

Conditions on $k_{\max}/k_{\rm med}$. Up to logarithmic factors, the required
upper bound on the ratio $k_{\max}/k_{\rm med}$ is $\tilde{O}(\epsilon^{2}n)$.
For moderate values of $\epsilon$, this condition is unlikely to be
prohibitive in practice, although it is more restrictive than the upper bound
of $\tilde{O}(\epsilon n)$ that was required in Theorem 4.1.

  * •

Concentration bounds. The final two conditions are concentration bounds,
essentially requiring $\mathcal{D}(k)$ to be sub-Gaussian. This condition is
technically absent from Theorem 4.1, although a similar condition is required
in order to design a private variance estimation algorithm with sufficiently
good accuracy.

The proof that Algorithm 3 is $(3\epsilon,2\delta)$-DP is fairly routine,
details can be found in the appendix. There are two main differences between
Algorithm 3 and Algorithm 2 that affect the utility: the replacement of the
optimal truncation with truncation based on $\widehat{k_{L}}$, and the use of
propose-test-release (PTR) to determine the level of noise added to the final
estimate. We will control the impact of these two factors separately.

Let us consider the impact of changing the truncation parameter. Set
$T_{L}=\frac{1}{\widehat{\sigma_{\min}}^{2}}$. Assuming 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, namely 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_{L}^{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_{L}}{\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 variance term decreases while the non-private variance 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 its optimal value. However, setting the truncation parameter this
large means that the private term is larger than necessary. We show that even
though the private term may be larger than it would be with the optimal
truncation, under the conditions of the theorem, the non-private term
dominates the variance anyway.

Let us now consider the impact of the use of propose-test-release (PTR). The
two relevant components for the how the PTR component of Algorithm 3 affects
the utility are the scale of $\Lambda/\epsilon$ and the probability that the
proposed sensitivity is too small resulting in the algorithm ending in line
(19), rather than line (22). The impact of the former is easy to analyse since
the noise added is simply output perturbation. In order to show that the PTR
ends in line (22) with high probability, we need to show that with high
probability (over the randomness in the samples), $\kappa^{*}$ as defined in
line (15) is large enough. Since this claim is in essence about
$\mathcal{M}(\cdot;k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2})$, we will state
this claim in the notation of Algorithm 4.

######  Lemma 4.4.

Given $k_{\max}\in\mathbb{N}$, $n\in\mathbb{N}$, $\hat{p}\in[0,1]$,
$\hat{\sigma_{p}}^{2}\in[0,1]$ and $k_{1},\cdots,k_{n}$, let
$\Upsilon=\frac{\log(1/\delta)}{\epsilon}+\frac{\ln(1/\delta)\ln(1/\beta)}{\epsilon}$,
if the conditions of Theorem 4.3 hold and
$D=\\{(\widehat{p}_{i},k_{i})\\}_{i=1}^{n}$ is a dataset such that
$\widehat{p}_{i}\sim\mathcal{D}(k_{i})$, then with probability $1-\beta$, for
any $D^{\prime}$ that is a $\kappa$-neighbour of $D$ for
$0\leq\kappa\leq\Upsilon$, we have

$\text{\rm{LS}}(\mathcal{M}(\cdot;k_{\max},m,\hat{p},\hat{\sigma_{p}}^{2},\alpha);D^{\prime})\leq
12\frac{v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\sum_{i=1}^{n}v_{i}}.$

##  5 Near Optimality and Lower Bounds

In Section 4, we showed that the variance of our realisable private estimator
$\widehat{p}_{\epsilon}$ was within a constant of that of the complete
information estimator $\widehat{p}_{\epsilon}^{\rm ideal}$. In this section,
we will show that in fact, $\widehat{p}_{\epsilon}$ performs as well (up to
logarithmic factors) as the true optimal private estimator. We’ll also give a
lower bound on the performance of the optimal estimator in terms of the
$k_{i}$. This will give us some intuition into the types of distributions of
$k_{i}$’s that benefit from this refined analysis.

###  5.1 Minimax Optimality of $\widehat{p}_{\epsilon}$

The goal of this section is to show that the estimator
$\widehat{p}_{\epsilon}$ discussed in Section 4.2 is minimax optimal up to
logarithmic factors among the class of unbiased estimators. In light of
Theorem 4.1, it suffices to show that the estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$ defined by Equations 3, (4), and (4.1) is
minimax optimal up to logarithmic factors. Let $\mathcal{P}$ be a
parameterized family of distributions $p\mapsto\mathcal{D}_{p}$, where
$\mathbb{E}[\mathcal{D}_{p}]=p$ and $\mathcal{D}_{p}$ is supported on $[0,1]$.
For $p\in[0,1]$ and $k\in\mathbb{N}$, let $\phi_{p,k}$ be the probability
density function of $\mathcal{D}_{p}(k)$. In this section, we will return to
the known size user-level differential privacy setting. Hence, we will let
$k_{1},\cdots,k_{n}$ be fixed.

Our lower bound will show that the estimation error must consist of a
statistical term and a privacy term. Such a lower bound thus must generalize a
statistical lower bound. We will rely on the Cramér-Rao approach to proving
statistical lower bounds; as we show, it is particularly amenable to
incorporating a privacy term. This approach relates the variance of any
unbiased estimator of the mean of a distribution to the inverse of the Fischer
information; the proof naturally extends to the case where we are given
samples from a set of distributions with the same mean but different
variances, as is the case in our setting. For many distributions of interest,
e.g., Gaussian and Bernoulli, the Fischer information of a single sample is
the inverse of the variance, and we make that assumption for
$\mathcal{D}_{p}$. We also assume that the $\mathcal{D}_{p}$ has sub-Gaussian
tails. Thus, as long as the set of permissible meta-distributions includes
distributions with this property, e.g., includes truncated Gaussians, our
lower bound applies.

######  Theorem 5.1.

Let $\mathcal{P}$ be a parameterized family of distributions
$p\mapsto\mathcal{D}_{p}$ and suppose that for all $p\in[0,1]$ and
$k\in\mathbb{N}$, the Fisher information of $\phi_{p,k}$ is inversely
proportional to the variance, ${\rm Var}(\mathcal{D}_{p}(k))$:

$\textstyle\int(\tfrac{\partial}{\partial
p}\log\phi_{p,k}(x))^{2}\phi_{p,k}(x)dx=O(\tfrac{1}{{\rm
Var}(\mathcal{D}_{p}(k))}),$ (10)

and for all $p$, $n>0$, $k\in\mathbb{N}$ and $\beta\in[1/3,2/3]$,
$f^{k}_{\mathcal{D}_{p}}(n,\sigma_{p}^{2},\beta)=\tilde{O}({\rm
Var}(\mathcal{D}_{p}(k)))$, then

$\displaystyle\min_{M\text{\rm, unbiased}}\max_{p\in[1/3,2/3]}[{\rm
Var}_{\forall i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M}(M)]$
$\displaystyle=\tilde{O}\left(\max_{p\in[1/3,2/3]}\left[{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M}(\widehat{p}_{\epsilon}^{\rm
ideal})\right]\right)$
$\displaystyle=\tilde{O}\left(\min_{T}\tfrac{\textstyle\sum_{i=1}^{n}\min\\{1/\sigma_{i}^{2},{T^{2}}\\}+\max_{i}\tfrac{\min\\{1/\sigma_{i}^{4},T^{2}/\sigma_{i}^{2}\\}|b_{i}-a_{i}|^{2}}{\epsilon^{2}})}{{(\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},T/\sigma_{i}\\})^{2}}}\right).$

Further, under the conditions of Theorem 4.1,

$\displaystyle\max_{p\in[1/3,2/3]}\left[{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M}(\widehat{p}_{\epsilon})\right]=\tilde{O}\left(\min_{M\text{\rm,
unbiased}}\max_{p\in[1/3,2/3]}[{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M}(M)]\right).$

Theorem 5.1 says the estimator $\widehat{p}_{\epsilon}^{\rm ideal}$ has
variance only a logarithmic factor worse than the variance of the optimal
unbiased estimator. Due to the truncation of the $\hat{p_{i}}$, the estimator
$\widehat{p}_{\epsilon}^{\rm ideal}$ is not unbiased, although the bias can be
made polynomially small by widening the truncation interval so truncation does
not occur with high probability. The theorem can also be slightly extended to
include estimators with polynomially small bias. This small bias assumption
seems to be inherent in the Cramer-Rao style proof that we use.

We will prove Theorem 5.1 in three steps. The following class of noisy linear
estimators, NLE, will act as an intermediary in our proof. The notation
$\sigma_{i}$ denotes ${\rm Var}(x_{i})$, which accounts for the randomness in
generating $x_{i}$.

$\displaystyle\text{\rm{NLE}}=\Big{\\{}M_{\texttt{NL}}(\mathbf{x};\mathbf{w})=$
$\displaystyle\textstyle\sum_{i=1}^{n}w_{i}x_{i}+{\rm
Lap}(\tfrac{\max_{i}w_{i}\sigma_{i}}{\epsilon})\;\big{|}\;w_{i}\in[0,1],\textstyle\sum_{i=1}^{n}w_{i}=1\Big{\\}}.$

Similar to $\widehat{p}_{\epsilon}^{\rm ideal}$, this class of estimators is
not realizable since we only have access to an estimate of $\sigma_{i}={\rm
Var}(\mathcal{D}_{p}(k_{i}))$. Additionally, the estimators in NLE are not
necessarily $\epsilon$-DP.

To prove Theorem 5.1, we will first show that the weights used in
$\widehat{p}_{\epsilon}^{\rm ideal}$ define the optimal weight vector among
the estimators in NLE. Then, we’ll show that (up to constant factors) the
minimax optimal estimator among unbiased estimators lies in NLE. Finally,
we’ll show that the variance of $\widehat{p}_{\epsilon}^{\rm ideal}$ is at
most a logarithmic factor worse than its not-quite-private counterpart in NLE.
This completes the proof of the near minimax optimality of
$\widehat{p}_{\epsilon}^{\rm ideal}$, and hence $\widehat{p}_{\epsilon}$.

The first step is shown in Lemma 5.2, which shows that the weights used in
$\widehat{p}_{\epsilon}^{\rm ideal}$ are optimal (i.e., variance-minimizing)
among all estimators in the set NLE.

######  Lemma 5.2.

Given $\widehat{p}_{i}\sim\mathcal{D}_{p}(k_{i})$ with variance
$\sigma^{2}_{i}$ for all $i\in[n]$ and $w\in[0,1]^{n}$ such that
$\sum_{i=1}^{n}w_{i}=1$, let
$\widehat{p}=\sum_{i=1}^{n}w_{i}\widehat{p}_{i}+{\rm
Lap}(\frac{\max_{i}w_{i}\sigma_{i}}{\epsilon})$. The variance of $\widehat{p}$
is minimized by the following weights:

$\tilde{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 $T$.

Since the threshold $T^{*}$ in $\widehat{p}_{\epsilon}^{\rm ideal}$ was chosen
to minimize ${\rm Var}(\widehat{p}_{\epsilon}^{\rm ideal})$, then we know that
the weights $w_{i}^{*}$ in $\widehat{p}_{\epsilon}^{\rm ideal}$ are optimal.
The proof of Lemma 5.2 can be found in Appendix D. The main component of the
proof is showing that under the constraint of differential privacy, no
individual’s contribution should be too heavily weighted.

Now, let us turn to the second – and main – component of the proof of Theorem
5.1. Lemma 5.3 formalises the statement that an estimator inside the class NLE
is minimax optimal among unbiased estimators. That is, for any unbiased
estimator $M$, there exists an estimator $M_{\texttt{NL}}\in\text{\rm{NLE}}$
with lower worst-case variance.

######  Lemma 5.3.

Let $\mathcal{P}$ be a parameterized family of distributions
$p\mapsto\mathcal{D}_{p}$ and suppose that $M:[0,1]^{n}\to[0,1]$ is an
$\epsilon$-DP estimator such that for all $p\in[1/3,2/3]$, if

  1. 1.

$M$ is unbiased, $\mu_{M}(p)=p$

  2. 2.

the Fisher information of $\phi_{p,k_{i}}$ is inversely proportional to the
variance

$\textstyle\int(\tfrac{\partial}{\partial
p}\log\phi_{p,k_{i}}(x_{i}))^{2}\phi_{p,k_{i}}(x_{i})dx_{i}=O(\tfrac{1}{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}),$

then there exists an estimator $M_{\texttt{NL}}\in\text{\rm{NLE}}$ such that

$\displaystyle\max_{p\in[1/3,2/3]}$ $\displaystyle[{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M_{\texttt{NL}}}(M_{\texttt{NL}})]\leq
O\left(\max_{p\in[1/3,2/3]}[{\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}(k_{i}),M}(M)]\right).$

A detailed proof of Lemma 5.3 can be found in Appendix D, but let us give a
brief sketch of the proof here. Given an estimator
$M_{\texttt{NL}}\in\text{\rm{NLE}}$, the variance of $M_{\texttt{NL}}$ can be
written as

$\displaystyle{\rm Var}(M_{\texttt{NL}})$
$\displaystyle\leq\textstyle\sum_{i=1}^{n}w_{i}^{2}{\rm
Var}(\mathcal{D}(k_{i}))+O(\tfrac{\max w_{i}\sigma_{i}}{\epsilon})^{2}.$ (11)

That is, it can be decomposed as the variance contribution of each individual
coordinate, and the variance contribution of the additional noise due to
privacy. Lemma 5.4 (proved in Appendix D) shows that the variance of any
estimator $M$ can be lower bounded by a similar decomposition. Since this
involves considering the impact of each coordinate individually, the following
notation will be useful. 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 over only randomness in $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 to let
$\mu_{M}(\boldsymbol{q})=\mu_{M}(\emptyset;\boldsymbol{q})$, 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))$. When the estimator $M$ is
clear from context, we will omit it.

######  Lemma 5.4.

For any randomised mechanism $M:[0,1]^{n}\to[0,1]$,

$\displaystyle{\rm Var}_{{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}}(M)=\mathbb{E}_{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}[(M(x_{1},...,x_{n})-\mu(p))^{2}]$
$\displaystyle\hskip
21.68121pt\geq\textstyle\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},...,x_{n})-\mu(x_{1},...,x_{n};p))^{2}]$
(12)

In Equation (12), 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. Now we want to define a weight
vector $\bf{w}$ such that the terms in Equation (12) are lower bounded by the
corresponding terms in Equation (11). The key component of the proof is the
observation that if we let

$w_{i}(p)=\tfrac{\partial}{\partial
q_{i}}\mu(\boldsymbol{q})\;\big{\rvert}_{\boldsymbol{q}=(p,\cdots,p)}$ (13)

then we can show that there exists a constant $c$ such that

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

This controls the contribution of each individual coordinate to the variance
of $M$. It remains only to control the contribution of the noise due to
privacy. We show that there exists $x_{i}$, $x_{i}^{\prime}$ such that

$|\mu(x_{i};p)-\mu(x_{i}^{\prime};p)|\geq\Omega(w_{i}(p)\cdot\textstyle\sqrt{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}),$

which we show implies that,

$\displaystyle\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}]\geq\Omega(\tfrac{w_{i}(p)^{2}{\rm
Var}(\mathcal{D}_{p}(k_{i}))}{\epsilon^{2}}).$ (15)

Intuitively, the worst-case $|\mu(x_{i};p)-\mu(x_{i}^{\prime};p)|$ plays an
analogous role to the sensitivity, since it captures the impact of changing
one user’s data. Since $M$ is an $\epsilon$-DP mechanism and
$|\mu(x_{i};p)-\mu(x_{i}^{\prime};p)|$ is at least
$\Omega(w_{i}(p)\cdot\sqrt{{\rm Var}(\mathcal{D}_{p}(k_{i}))})$, we show that
it must include noise with standard deviation of at least this magnitude over
$\epsilon$. This is consistent with, e.g., the Laplace Mechanism that adds
noise with standard deviation $\Theta(\Delta f/\epsilon)$.

Combining Lemma 5.4 with Equations (14) and (15) gives that the variance of
$M$ is at least,

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

Finally, we must create a corresponding $M_{\texttt{NL}}\in\text{\rm{NLE}}$
for comparison, using the same weights. Since $\sum_{i=1}^{n}w_{i}(p)$ as
defined in Equation (13) need not equal 1, these weights will need to be
normalized to sum to 1 to create an estimator in NLE. We need to show this
normalisation does not substantially increase the variance of the resulting
estimator. In order to show this, we show that there exists a
$p^{*}\in[1/3,2/3]$ such that $\sum_{i=1}^{n}w_{i}(p^{*})\geq 1$, since
normalizing the estimator by a factor of
$\frac{1}{\sum_{i=1}^{n}w_{i}(p^{*})}$ will affect the variance by a factor of
$\frac{1}{(\sum_{i=1}^{n}w_{i}(p^{*}))^{2}}$, and thus if
$\sum_{i=1}^{n}w_{i}(p^{*})\geq 1$, then this will decrease variance. This
desired fact follows from the definition of $w_{i}$, and the fact that $M$ is
unbiased. Now, if we define

$M_{\texttt{NL}}(\mathbf{x})=\tfrac{\textstyle\sum_{i=1}^{n}w_{i}(p^{*})x_{i}+{\rm
Lap}(\tfrac{\max_{i}w_{i}(p^{*})\sqrt{{\rm
Var}(\mathcal{D}_{p}(k_{i}))}}{\epsilon})}{\textstyle\sum_{i=1}^{n}w_{i}(p^{*})},$

then $M_{\texttt{NL}}\in\text{\rm{NLE}}$ and ${\rm Var}_{\forall
i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M_{\texttt{TNL}}}(M_{\texttt{NL}})=\Theta\left({\rm
Var}_{\forall i\in[n],x_{i}\sim\mathcal{D}_{p}(k_{i}),M}(M)\right)$.

The final component needed for the proof of Theorem 5.1 is a translation from
the estimators in NLE, which are not $\epsilon$-DP to the corresponding
$\epsilon$-DP estimator. For any weight vector $\bf{w}$, we can define an
$\epsilon$-DP estimator by truncating the data point $x_{i}$ and calibrating
the noise appropriately:

$\displaystyle
M_{\texttt{TNL}}(x_{1},\cdots,x_{n};\mathbf{w})=\textstyle\sum_{i=1}^{n}w_{i}[x_{i}]_{p-f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}^{p+f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}+{\rm
Lap}(\tfrac{\max_{i}2w_{i}f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}{\epsilon}).$

Provided $f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\approx{\rm
Var}(\mathcal{D}(k_{i}))$, the estimators $M_{\texttt{TNL}}$ have
approximately the same variance as the corresponding element of NLE, but are
slightly biased. This is formalized in the following lemma.

######  Lemma 5.5.

For any distribution $\mathcal{D}$, $n>0$ and $\beta\in[0,1]$, if for all
$k_{i}$, $f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)=\tilde{O}({\rm
Var}(\mathcal{D}(k_{i}))$ then for any $\mathbf{w}\in[0,1]^{n}$ such that
$\sum_{i=1}^{n}w_{i}=1$, we have ${\rm
Var}(M_{\texttt{TNL}}(\cdot\;;\mathbf{w}))=\tilde{O}({\rm
Var}(M_{\texttt{NL}}(\cdot\;;\mathbf{w})))$. Further, the bias of
$M_{\texttt{TNL}}$ is at most $\beta$.

Finally, we have the tools to prove the main theorem in this section, Theorem
5.1:

$\displaystyle\min_{M\text{ unbiased}}\max_{p\in[1/3,2/3]}[{\rm
Var}_{\mathcal{D}_{p}}(M)]$
$\displaystyle=\Omega(\min_{M\in\texttt{NLE}}\max_{p\in[1/3,2/3]}[{\rm
Var}_{\mathcal{D}_{p}}(M)])$ $\displaystyle=\Omega(\max_{p\in[1/3,2/3]}[{\rm
Var}_{\mathcal{D}_{p}}({p_{\epsilon}^{\texttt{NLE}}})])$
$\displaystyle=\tilde{\Omega}(\max_{p\in[1/3,2/3]}[{\rm
Var}_{\mathcal{D}_{p}}(\widehat{p}_{\epsilon}^{\rm ideal})])$
$\displaystyle=\tilde{\Omega}(\max_{p\in[1/3,2/3]}[{\rm
Var}_{\mathcal{D}_{p}}(\widehat{p}_{\epsilon})])$

where $p_{\epsilon}^{\texttt{NLE}}\in\texttt{NLE}$ has the same weights as
$\widehat{p}_{\epsilon}^{\rm ideal}$. The equalities follow from Lemmas 5.3,
5.2, 5.5, and Theorem 4.1, respectively.

###  5.2 Minimax Lower Bound on Estimation Rate

In addition to establishing the near optimality of $\widehat{p}_{\epsilon}$,
we will also give a lower bound on minimax rate of estimation in terms of the
parameters $k_{1},\cdots,k_{n}$ and $\sigma_{p}^{2}$. Note that we can view
the truncation of the weights $w_{i}$ as establishing an effective upper bound
on $k_{i}$. Given $k_{1},\cdots,k_{n}\in\mathbb{N}$, and $\epsilon>0$, let

$k^{*}=\arg\min_{k}\tfrac{\tfrac{k}{\epsilon^{2}}+\sum_{i=1}^{n}\min\\{k_{i},k\\}}{(\sum_{i=1}^{n}\min\\{k_{i},k\\})^{2}}.$
(16)

Intuitively, in the case that $\sigma_{p}=0$, we want to use as many samples
as possible, but one user contributing many samples leads to larger
sensitivity and thus privacy cost. Limiting the number of samples per user to
$k_{\max}$ allows us to limit the sensitivity to be about
$w_{\max}(1/\sqrt{k_{\max}})$. Since $w_{i}$ is proportional to the number of
samples used, the variance of the estimator when using at most $k^{*}$ samples
per user is akin to choosing a threshold that minimises the variance.

######  Corollary 5.6.

Given $k_{1},\cdots,k_{n}\in\mathbb{N}$, and $\sigma_{p}$, there exists a
family of distributions $\mathcal{D}_{p}$ such that

$\displaystyle\min_{M\text{\rm, 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})]\geq\tilde{\Omega}\left(\min_{k^{*}}\left\\{\tfrac{\frac{k^{*}}{\epsilon^{2}}+\sum_{i=1}^{n}\min\\{k_{i},k^{*}\\}}{(\sum_{i=1}^{n}\min\\{k_{i},\sqrt{k_{i}k^{*}}\\})^{2}},\frac{\sigma_{p}^{2}}{n}\right\\}\right).$

Corollary 5.6 is proved in two parts, using two different families of
distributions $\mathcal{D}_{p}$. The first family is where $\sigma_{p}^{2}=0$,
so $\mathcal{D}_{p}(k)={\rm Bin}(k,p)$ for all $k\in[n]$. For this family, we
know that the minimax error is obtained by the mechanism
$\widehat{p}_{\epsilon}^{\rm ideal}$. Calculating the variance of
$\widehat{p}_{\epsilon}^{\rm ideal}$ on this family, we obtain the first term
of the minimum. The second family is the family of truncated Gaussian
distributions (truncated so that $\mathcal{D}$ is supported on $[0,1]$). The
variance of the optimal estimator for this family would be lower bounded by
$\sigma_{p}^{2}/n$, even if each user was given a sample directly from
$\mathcal{D}$, rather than from $\mathcal{D}(k)$. Thus, using a reduction to
the case of simply estimating $p$ given $n$ samples from $\mathcal{D}$, we
obtain the second term in the minimum.

##  6 Example Initial Estimators

In this section we give example initial mean and variance estimation
procedures that can be used in the framework described in Section 4. For both
estimators, we show that they satisfy the conditions of Theorem 4.1, and thus
can be used as initial estimators in Algorithm 2, assuming all other technical
conditions are satisfied. This also immediately implies that the set of
initial mean and variance estimators which satisfy the conditions of Theorem
4.1 is non-empty.

We note again that the estimators described in this section are examples of
estimators that achieve the conditions of Theorem 4.1, and that any private
mean and variance estimators that satisfy these conditions could be used
instead. As discussed in Section 4.2, one may choose to use different
estimators of these initial quantities in different settings (for example, if
local differential privacy is required or if different distributional
assumptions are known).

###  6.1 Initial Mean Estimation

We will begin with the initial mean estimation procedure
$\rm\texttt{mean}_{\epsilon,\delta}$ to computed $\widehat{p}_{\epsilon}^{\rm
initial}$. We consider the simplest mean estimation subroutine, where the
analyst collects a single data point from the $n/10$ users with the smallest
$k_{i}$, then privately computes the empirical mean of these points using the
Laplace Mechanism. The following lemma shows that this process is
differentially private and satisfies the accuracy conditions of Theorem 4.1,
i.e., that with high probability, $\widehat{p}_{\epsilon}^{\rm initial}$ is
close to $p$ and $\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm initial})$ is close to $p(1-p)$.

######  Lemma 6.1.

Fix any $\epsilon>0$ and let $\widehat{p}_{\epsilon}^{\rm
initial}=\rm\texttt{mean}_{\epsilon,\delta}(x^{1}_{(9n/10)+1},\cdots,x^{1}_{n})=\frac{1}{n/10}\sum_{i=(9n/10)+1}^{n}x_{i}^{1}+{\rm
Lap}\left(\frac{10}{\epsilon n}\right)$. Then
$\rm\texttt{mean}_{\epsilon,\delta}$ is $(\epsilon,0)$-differentially private,
$\mathbb{E}[\widehat{p}_{\epsilon}^{\rm initial}]=p$ and if
$p\geq\frac{20\log(1/\beta)}{n}$, then for $n$ sufficiently large,

$\Pr[|\widehat{p}_{\epsilon}^{\rm initial}-p|\leq\alpha]\leq\beta\text{ for
}\alpha=2\max\\{\sqrt{\tfrac{12\widehat{p}_{\epsilon}^{\rm
initial}\log(4/\beta)}{n/10}+\tfrac{36\log^{2}(4/\beta)}{n^{2}/100}}+\tfrac{6\log(4/\beta)}{n/10},\tfrac{\log(2/\beta)}{\epsilon
n/10}\\}\leq f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta).$

Further, if $\min\\{p,1-p\\}\geq
12\max\left\\{\frac{3\log(4/\beta)}{n/10},\frac{\log(2/\beta)}{\epsilon
n/10}\right\\}$ then with probability $1-\beta$, $\widehat{p}_{\epsilon}^{\rm
initial}\in[\frac{1}{2}p,\frac{3}{2}p]$ and $\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})\in[\frac{p(1-p)}{2},\frac{3p(1-p)}{2}]$.

The concentration bound follows from noticing that $\mathcal{D}={\rm Ber}(p)$
and using the concentration of binomial random variables. The full proof is in
Appendix E.

Note that the expression of $\alpha$ depends only on quantities known to the
analyst – including $\widehat{p}_{\epsilon}^{\rm initial}$, which will be
observed as output – so that $\alpha$ can be computed directly for use in
Algorithm 2. Although our presentation of Algorithm 2 requires $\alpha$ to be
specified up front as input to the algorithm, it could equivalently be
computed internally by the algorithm as a function of
$\widehat{p}_{\epsilon}^{\rm initial}$ and other input parameters.

###  6.2 Initial Variance Estimation

We now turn to our variance estimation procedure
$\texttt{variance}_{\epsilon,\delta}$ for estimating $\sigma_{p}^{2}$. Let us
first provide some background on privately estimating the standard deviation
of well-behaved distributions. Lemma 6.2 guarantees the existence of a
differentially private algorithm for estimating standard deviation within a
small constant factor with high probability, as long as the sample size is
sufficiently large. The following is a slight generalisation of the estimation
of the standard deviation of a Gaussian given by Karwa and Vadhan (2018).

######  Lemma 6.2 (DP standard deviation estimation).

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),\zeta>0,$
there exists an $(\epsilon,\delta)$-differentially private algorithm
$\mathcal{M}$ that satisfies the following: if $x_{1},\ldots,x_{n}$ are i.i.d.
draws from a distribution $P$ which has standard deviation
$\sigma\in[\sigma_{\min},\sigma_{\max}]$ and absolute central third moment
$\rho=\mathbb{E}[|x-\mu(P)|^{3}]$ such that
$\frac{\rho}{\sigma^{3}}\leq\zeta$, then if $n\geq
c\zeta^{2}\min\\{\frac{1}{\epsilon}\ln(\frac{\ln\frac{\sigma_{\max}}{\sigma_{\min}})}{\beta}),\frac{1}{\epsilon}\ln(\frac{1}{\delta\beta})\\}$,
(where $c$ is a universal constant), then $\mathcal{M}$ produces an estimate
$\widehat{\sigma}$ of the standard deviation such that
$\Pr_{x_{1},\ldots,x_{n}\sim
P,\mathcal{M}}(\sigma^{2}\leq\widehat{\sigma}^{2}\leq 8\sigma^{2})\geq
1-\beta$.

The proof of Lemma 6.2 is given formally in Appendix E.1, along with a
detailed description of the algorithm $\mathcal{M}$. The remaining omitted
proofs in this section are in Appendix E. We note that the interval
$[\sigma_{\min},\sigma_{\max}]$ can be set fairly large without much impact on
the sample complexity, in the case that little is known about $\sigma$ a
priori.

In order to estimate $\sigma_{p}^{2}$, we will use the estimator promised by
Lemma 6.2 on the data of the $L=\log n/\epsilon$ users with the largest
$k_{i}$. Let $k=k_{\log n/\epsilon}$, so the top $\log n/\epsilon$ individuals
all have at least $k$ data points. We will have these individuals report
$\widehat{p}_{i}^{k}:=\frac{1}{k}\sum_{j=1}^{k}x_{j}^{i}$, which is the
empirical mean of their first $k$ data points. Thus, we are running the
estimator promised in Lemma 6.2 on $\mathcal{D}(k)$ with $\log n/\epsilon$
data points. In order to utilise Lemma 6.2, we first need to ensure that
$\mathcal{D}(k)$ satisfies the moment condition that $\rho/\sigma^{3}$ is
bounded, which is shown in Lemma 6.3.

######  Lemma 6.3.

For $k\in\mathbb{N}$, suppose $p\in[\frac{1}{k},1-\frac{1}{k}]$,
$\sigma_{p}\geq\frac{1}{k}$, $k\geq 2$, and there exists $\gamma>0$ such that
$\frac{\rho_{\mathcal{D}}}{\sigma_{p}^{3}}\leq\gamma$ where
$\rho_{\mathcal{D}}$ denotes the absolute central third moment of
$\mathcal{D}$. Then $\frac{\rho_{\mathcal{D}(k)}}{{\rm
Var}(\mathcal{D}(k))^{3/2}}\leq 8(3\sqrt{3}+\gamma)$.

With this result, we can apply Lemma 6.2 to our setting to privately achieve
an estimate $\widehat{\sigma}_{p,k}^{2}$ that is close to the true population-
level variance $\sigma_{p}^{2}$, as shown in Lemma 6.4. Note that as $k$ grows
large, the allowable range for $p$ approaches the full support $[0,1]$ and the
allowable standard deviation $\sigma_{p}$ approaches any non-negative number.

Lemma 6.4 combines the two previouse results to show that Lemma 6.2 can be
applied to the individual reports $\widehat{p}_{i}^{k}$ from the top $\log n$
users, and the resulting variance estimate will satisfy the accuracy
conditions of Theorem 4.1.

######  Lemma 6.4.

Given
$\sigma_{\min}<\sigma_{\max}\in[0,\infty],\epsilon>0,\delta\in(0,\frac{1}{n}],\beta\in(0,1/2)$,
and $\zeta>0,$ let $\mathcal{M}$ be the $(\epsilon,\delta)$-differentially
private mechanism given by Lemma 6.2, and let
$\widehat{\sigma}_{p,k}^{2}=\mathcal{M}(\widehat{p}^{k}_{1},\cdots,\widehat{p}^{k}_{\log
n/\epsilon})$, where $\widehat{p}^{k}_{1},\cdots,\widehat{p}^{k}_{\log
n/\epsilon}\sim\mathcal{D}(k)$. If there exists $\zeta>0$ such that
$\frac{\rho_{\mathcal{D}}}{\sigma_{p}^{3}}\leq\zeta$ where
$\rho_{\mathcal{D}}=\mathbb{E}_{x\sim\mathcal{D}}[|x-p|^{3}]$,
$\sqrt{\frac{1}{k}p(1-p)+\frac{k-1}{k}\sigma_{p}^{2}}\in[\sigma_{\min},\sigma_{\max}]$,
$\sigma_{p}>\frac{1}{k}$, $p\in\left[\frac{1}{k},1-\frac{1}{k}\right]$, and
$\log n\geq
c(8(3\sqrt{3}+\zeta))^{2}\min\\{\ln(\frac{\ln(\frac{\sigma_{\max}}{\sigma_{\min}})}{\beta}),\ln(\frac{1}{\delta\beta})\\}$,
then with probability $1-\beta$, $\widehat{\sigma}_{p,k}^{2}\in[{\rm
Var}(\mathcal{D}(k)),8{\rm Var}(\mathcal{D}(k))]$.

## References

  * Acharya and Sun (2019) J. Acharya and Z. Sun.  Communication complexity in locally private distribution estimation and heavy hitters.  _arXiv preprint arXiv:1905.11888_ , 2019.
  * Acharya et al. (2019) J. Acharya, Z. Sun, and H. Zhang.  Hadamard response: Estimating distributions privately, efficiently, and with little communication.  volume 89 of _Proceedings of Machine Learning Research_ , pages 1120–1129. PMLR, 16–18 Apr 2019.
  * Alabi et al. (2020) D. Alabi, A. McMillan, J. Sarathy, A. Smith, and S. Vadhan.  Differentially private simple linear regression, 2020.
  * Asi and Duchi (2020) H. Asi and J. C. Duchi.  Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 14106–14117. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/a267f936e54d7c10a2bb70dbe6ad7a89-Paper.pdf.
  * Bhowmick et al. (2019) A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers.  Protection against reconstruction and its applications in private federated learning, 2019.
  * Borenstein et al. (2021) M. Borenstein, L. V. Hedges, J. P. Higgins, and H. R. Rothstein.  _Introduction to meta-analysis_.  John Wiley & Sons, 2021.
  * Bun et al. (2015) M. Bun, K. Nissim, and U. Stemmer.  Simultaneous private learning of multiple concepts.  11 2015.  doi: 10.1145/2840728.2840747.
  * Chen et al. (2020) W.-N. Chen, P. Kairouz, and A. Özgür.  Breaking the communication-privacy-accuracy trilemma.  _arXiv preprint arXiv:2007.11707_ , 2020.
  * Duchi and Rogers (2019) J. Duchi and R. Rogers.  Lower bounds for locally private estimation via communication complexity.  In A. Beygelzimer and D. Hsu, editors, _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99 of _Proceedings of Machine Learning Research_ , pages 1161–1191, Phoenix, USA, 25–28 Jun 2019\. PMLR.  URL http://proceedings.mlr.press/v99/duchi19a.html.
  * Duchi et al. (2018) J. C. Duchi, M. I. Jordan, and M. J. Wainwright.  Minimax optimal procedures for locally private estimation.  _Journal of the American Statistical Association_ , 113(521):182–201, 2018.
  * Dwork and Lei (2009) C. Dwork and J. Lei.  Differential privacy and robust statistics.  In _Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing_ , STOC ’09, pages 371–380, New York, NY, USA, 2009. Association for Computing Machinery.  ISBN 9781605585062.
  * Dwork and Roth (2014) C. Dwork and A. Roth.  _The Algorithmic Foundations of Differential Privacy_ , volume 9.  2014\.  URL http://dx.doi.org/10.1561/0400000042.
  * Dwork et al. (2006) C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  volume Vol. 3876, pages 265–284, 01 2006.  doi: 10.1007/11681878_14.
  * Eichner et al. (2019) H. Eichner, T. Koren, B. Mcmahan, N. Srebro, and K. Talwar.  Semi-cyclic stochastic gradient descent.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1764–1773. PMLR, 09–15 Jun 2019.
  * Erlingsson et al. (2014) Ú. Erlingsson, V. Pihur, and A. Korolova.  RAPPOR: randomized aggregatable privacy-preserving ordinal response.  In _ACM SIGSAC Conference on Computer and Communications Security_ , pages 1054–1067, 2014.
  * Hanzely and Richtárik (2020) F. Hanzely and P. Richtárik.  Federated learning of a mixture of global and local models.  _arXiv preprint arXiv:2002.05516_ , 2020.
  * Hardt and Talwar (2010) M. Hardt and K. Talwar.  On the geometry of differential privacy.  In _Proceedings of the Forty-Second ACM Symposium on Theory of Computing_ , STOC ’10, pages 705–714, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781450300506.
  * Hartung et al. (2008) J. Hartung, G. Knapp, and B. Sinha.  Statistical meta-analysis with applications.  08 2008.  doi: 10.1002/9780470386347.
  * Hsu et al. (2012) J. Hsu, S. Khanna, and A. Roth.  Distributed private heavy hitters.  In _International Colloquium on Automata, Languages, and Programming_ , pages 461–472. Springer, 2012.
  * Johnson and Shmatikov (2013) A. Johnson and V. Shmatikov.  Privacy-preserving data exploration in genome-wide association studies.  In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’13, pages 1079–1087, New York, NY, USA, 2013. Association for Computing Machinery.  ISBN 9781450321747.
  * Kairouz et al. (2021) P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konecný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, H. Qi, D. Ramage, R. Raskar, M. Raykova, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.  ISSN 1935-8237.  doi: 10.1561/2200000083.  URL http://dx.doi.org/10.1561/2200000083.
  * Karwa and Vadhan (2018) V. Karwa and S. P. Vadhan.  Finite sample differentially private confidence intervals.  volume abs/1711.03908 of _Innovations in Theoretical Computer Science ’18_ , 2018.
  * Levy et al. (2021) D. Levy, Z. Sun, K. Amin, S. Kale, A. Kulesza, M. Mohri, and A. Suresh.  Learning with user-level privacy.  In _Neural Information Processing Systems (NeurIPS 2021)_ , 2021.
  * Liu et al. (2020) Y. Liu, A. T. Suresh, F. X. X. Yu, S. Kumar, and M. Riley.  Learning discrete distributions: user vs item-level privacy.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 20965–20976. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/f06edc8ab534b2c7ecbd4c2051d9cb1e-Paper.pdf.
  * McMahan et al. (2017) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In A. Singh and J. Zhu, editors, _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 1273–1282, Fort Lauderdale, FL, USA, 20–22 Apr 2017. PMLR.
  * McMahan et al. (2018) H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang.  Learning differentially private recurrent language models.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.  URL https://openreview.net/forum?id=BJ0hF1Z0b.
  * McSherry and Mironov (2009) F. McSherry and I. Mironov.  Differentially private recommender systems: Building privacy into the netflix prize contenders.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 627–636, 2009.
  * McSherry and Talwar (2007) F. McSherry and K. Talwar.  Mechanism design via differential privacy.  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)_ , pages 94–103, 2007.  doi: 10.1109/FOCS.2007.66.
  * Mihoc and Fătu (2003) I. Mihoc and C. Fătu.  Fisher’s information measure and truncated normal distributions (ii).  _Revue d’Analyse Numérique et de Théorie de l’Approximation_ , 32, 01 2003.
  * Nielsen (2013) F. Nielsen.  _Cramér-Rao Lower Bound and Information Geometry_ , pages 18–37.  Hindustan Book Agency, Gurgaon, 2013.  URL https://doi.org/10.1007/978-93-86279-56-9_2.
  * Ozkara et al. (2022) K. Ozkara, A. Girgis, D. Data, and S. Diggavi.  A generative framework for personalized learning and estimation: Theory, algorithms, and privacy.  arXiv pre-print 2207.01771, 07 2022.
  * Thakurta and Smith (2013) A. G. Thakurta and A. Smith.  Differentially private feature selection via stability arguments, and the robustness of the lasso.  In S. Shalev-Shwartz and I. Steinwart, editors, _Proceedings of the 26th Annual Conference on Learning Theory_ , volume 30 of _Proceedings of Machine Learning Research_ , pages 819–850, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.
  * Vadhan (2017) S. Vadhan.  _The Complexity of Differential Privacy_ , pages 347–450.  04 2017.  ISBN 978-3-319-57047-1.  doi: 10.1007/978-3-319-57048-8_7.
  * Wikipedia contributors (2021) Wikipedia contributors.  Meta-analysis — Wikipedia, the free encyclopedia, 2021.  URL https://en.wikipedia.org/w/index.php?title=Meta-analysis&oldid=1023577278.  [Online; accessed May 2021].
  * Zhou and Cong (2018) F. Zhou and G. Cong.  On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization.  In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18_ , pages 3219–3227. International Joint Conferences on Artificial Intelligence Organization, 7 2018\.  doi: 10.24963/ijcai.2018/447.  URL https://doi.org/10.24963/ijcai.2018/447.

##  Appendix A Proofs from Section 2

See 2.1

###### Proof of Lemma 2.1.

Firstly, note that,

$\sigma_{p}^{2}=\mathbb{E}_{x\sim\mathcal{D}}[x^{2}]-p^{2}\leq\mathbb{E}_{x\sim\mathcal{D}}[x]-p^{2}=p(1-p),$

where the inequality follows from the fact that $\mathcal{D}$ is supported on
$[0,1]$.

Next,

$\mathbb{E}[x_{i}]=\int_{x=0}^{1}\Pr(p_{i}=x)\Pr({\rm
Ber}(x)=1)dx=\int_{x=0}^{1}\Pr(p_{i}=x)xdx=p,$

which by linearity of expectation implies that $\mathbb{E}[\mathcal{D}(k)]=p$.

By the Law of Total Variation, the variance of $\widehat{p}_{i}$ is:

$\displaystyle{\rm Var}(\widehat{p}_{i})$
$\displaystyle=\mathbb{E}_{p_{i}}[{\rm
Var}_{x_{i}}(\widehat{p}_{i}|p_{i})]+{\rm
Var}_{p_{i}}(\mathbb{E}_{x_{i}}[\widehat{p}_{i}|p_{i}])$
$\displaystyle=\mathbb{E}_{p_{i}}[\frac{1}{k_{i}}p_{i}(1-p_{i})]+{\rm
Var}_{p_{i}}(p_{i})$
$\displaystyle=\frac{1}{k_{i}}(p-\sigma_{p}^{2}-p^{2})+\sigma_{p}^{2}$
$\displaystyle=\frac{1}{k_{i}}(p-p^{2})+(1-\frac{1}{k_{i}})\sigma_{p}^{2}.$
$\displaystyle=\frac{1}{k_{i}}{\rm Var}({\rm
Ber}(p))+(1-\frac{1}{k_{i}})\sigma_{p}^{2}.$

∎

##  Appendix B Proofs from Section 4.2

First, let us show that the conditions of Theorem 4.1 imply that the variance
and truncation parameter estimates of each individual data subject are correct
up to constant factors.

See 4.2

###### Proof of Lemma 4.2.

Note that $\widehat{\sigma}_{p}^{2}$ is actually an estimate of the variance
of $\mathcal{D}(k_{L})$ since it has access to samples from this distribution
rather than $\mathcal{D}$ itself. Therefore,
$\widehat{\sigma}_{p}^{2}\in\left[{\rm Var}(\mathcal{D}({k_{L}})),8\cdot{\rm
Var}(\mathcal{D}({k_{L}}))\right]$ implies
$\widehat{\sigma}_{p}^{2}\in\left[\sigma_{p}^{2},8\left(\frac{1}{k_{L}}p(1-p)+\sigma_{p}^{2}\right)\right]$.
Then for every $i\geq L$ (i.e., with $k_{i}\leq k_{L}$),

$\displaystyle\widehat{\sigma}_{i}^{2}$
$\displaystyle=\frac{1}{k_{i}}\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})+\frac{k_{i}-1}{k_{i}}\widehat{\sigma}_{p}^{2}$
$\displaystyle\geq\frac{1}{k_{i}}\frac{1}{2}p(1-p)+\frac{k_{i}-1}{k_{i}}\sigma_{p}^{2}$
$\displaystyle\geq\frac{1}{2}\left(\frac{1}{k_{i}}p(1-p)+\frac{k_{i}-1}{k_{i}}\sigma_{p}^{2}\right)$
$\displaystyle=\frac{1}{2}\sigma_{i}^{2},$

where the first inequality follows from the accuracy conditions on
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
in Theorem 4.1, and the last equality follows from the definition of
$\sigma_{i}^{2}$ in Lemma 2.1. Also,

$\displaystyle\widehat{\sigma}_{i}^{2}$
$\displaystyle=\frac{1}{k_{i}}\widehat{p}_{\epsilon}^{\rm
initial}(1-\widehat{p}_{\epsilon}^{\rm
initial})+\frac{k_{i}-1}{k_{i}}\widehat{\sigma}_{p}^{2}$
$\displaystyle\leq\frac{1}{k_{i}}\frac{3}{2}p(1-p)+8\frac{k_{i}-1}{k_{i}}\left(\frac{1}{k_{\log
n}}p(1-p)+\sigma_{p}^{2}\right)$
$\displaystyle=\left(\frac{3}{2}+8\frac{k_{i}-1}{k_{\log
n}}\right)\frac{1}{k_{i}}p(1-p)+8\frac{k_{i}-1}{k_{i}}\sigma_{p}^{2}$
$\displaystyle\leq
9.5\left(\frac{1}{k_{i}}p(1-p)+\frac{k_{i}-1}{k_{i}}\sigma_{p}^{2}\right)$
$\displaystyle=9.5\sigma_{i}^{2},$

where again, the first inequality follows from the accuracy conditions on
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
in Theorem 4.1, and the last equality follows from the definition of
$\sigma_{i}^{2}$ in Lemma 2.1. The intermediate steps are simply algebraic
manipulations. These two facts give us the desired bounds on
$\widehat{\sigma}_{i}^{2}$.

Next we turn to the truncation parameters $\widehat{a_{i}}$ and
$\widehat{b_{i}}$. Using the definition of $\widehat{a_{i}}$ in Algorithm 2,
we have,

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

where the two inequalities respectively follow from the accuracy conditions on
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
in Theorem 4.1. A symmetric result that $\widehat{b_{i}}\geq b_{i}$ follows
similarly.

Finally,

$\displaystyle|\widehat{b_{i}}-\widehat{a_{i}}|$
$\displaystyle=2\alpha+2f^{k_{i}}_{\mathcal{D}}(n,\widehat{\sigma_{p}^{2}},\beta)$
$\displaystyle\leq
2f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)+2f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$
$\displaystyle=4f^{k_{i}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$
$\displaystyle=4|b_{i}-a_{i}|.$

The inequalities again follows from the accuracy conditions on
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
in Theorem 4.1. ∎

See 4.1

###### Proof of Theorem 4.1.

To see that Algorithm 2 is differentially private, consider the three cohorts
into which users are placed. The first cohort, containing the $n/10$ users
with the smallest $k_{i}$ will have their data used in
$\rm\texttt{mean}_{\epsilon,\delta}$, which is $(\epsilon,\delta)$-DP.
Similarly, the second cohort containing the $L$ users with the largest $k_{i}$
will have their data used in $\texttt{variance}_{\epsilon,\delta}$, which is
also $(\epsilon,\delta)$-DP. The intermediate estimators of
$\widehat{\sigma}_{i}^{2}$, $\hat{T}^{*}$, $\hat{a}_{i}$, $\hat{b}_{i}$, and
sensitivity $\Lambda$ are all computed as post-processing on the private
outputs of these initial estimation subroutines and on the public $k_{i}$s,
and thus do not incur any additional privacy cost. The third cohort contains
the middle users $i\in[L+1,9n/10]$. These users’ data are only used in the
final estimate, which is an $(\epsilon,0)$-DP instantiation of the Laplace
Mechanism [Dwork et al., 2006].

Since these cohorts are disjoint and private algorithms are applied to each
cohort’s data separately, parallel composition applies, and the overall
privacy parameters are the maximum of those experienced by any cohort, so the
overall algorithm is $(\epsilon,\delta)$-DP.

For accuracy of the $\widehat{p}_{\epsilon}$ estimator produced by Algorithm
2, first notice that under the assumption that $\frac{k_{\max}}{k_{\rm
med}}\leq\frac{n/2-L}{L}$, if $\sigma_{k_{\max}}^{2}={\rm
Var}(\widehat{p}_{1})$ and $\sigma_{k_{\rm med}}^{2}={\rm
Var}(\widehat{p}_{n/2})$ then

$\sigma_{k_{\rm med}}^{2}=\frac{1}{k_{\rm med}}p(1-p)+\left(1-\frac{1}{k_{\rm
med}}\right)\sigma_{p}^{2}\leq\frac{n/2-L}{L}\frac{1}{k_{\max}}p(1-p)+\left(1-\frac{1}{k_{\max}}\right)\sigma_{p}^{2}\leq\frac{n/2-L}{L}\sigma_{k_{\max}}^{2}.$

Therefore, for any truncation parameter $T$,

$\displaystyle\frac{1}{2}\sum_{i=1}^{n}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle\leq\sum_{i=1}^{n/2}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle=\sum_{i=1}^{L}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}+\sum_{i=L+1}^{n/2}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle\leq
L\cdot\min\left\\{\frac{1}{\sigma_{k_{\max}}^{2}},\frac{T}{\sigma_{k_{\max}}}\right\\}+\sum_{i=L+1}^{n/2}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle\leq(n/2-L)\cdot\min\left\\{\frac{1}{\sigma_{k_{\rm
med}}^{2}},\frac{T}{\sigma_{k_{\rm
med}}}\right\\}+\sum_{i=L+1}^{n/2}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle\leq
2\sum_{i=L+1}^{n/2}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\}$
$\displaystyle\leq
2\sum_{i=L+1}^{9n/10}\min\left\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\right\\},$
(17)

where the first, second, and fourth inequalities follow from our assumed
ordering on the $k_{i}$s. The third inequality comes from our assumption on
$k_{\max}$ and $k_{\rm med}$, and the final inequality follows from the fact
that the summands $\min\\{\frac{1}{\sigma_{i}^{2}},\frac{T}{\sigma_{i}}\\}$
are positive so adding more terms only increases the sum.

Therefore,

$\displaystyle{\rm Var}(\widehat{p}_{\epsilon})$
$\displaystyle=\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/\widehat{\sigma_{j}}^{2},\frac{\widehat{T}^{*}}{\widehat{\sigma_{i}}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},\frac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}\\}\sigma_{i}^{2}+\max_{i}\frac{\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},{\frac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/\widehat{\sigma_{j}}^{2},\frac{\widehat{T}^{*}}{\widehat{\sigma_{i}}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},\frac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}\\}2\widehat{\sigma_{i}}^{2}+\max_{i}\frac{\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},\frac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq
2\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/\widehat{\sigma_{j}}^{2},\frac{\widehat{T}^{*}}{\widehat{\sigma_{i}}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\widehat{\sigma}_{i}^{2}},\widehat{T}^{*2}\\}+\max_{i}\frac{\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},\frac{\widehat{T}^{*2}}{\widehat{\sigma_{i}}^{2}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq
2\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/\widehat{\sigma_{j}}^{2},\frac{T^{*}}{\widehat{\sigma_{i}}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\widehat{\sigma}_{i}^{2}},T^{*2}\\}+\max_{i}\frac{\min\\{\frac{1}{\widehat{\sigma_{i}}^{4}},\frac{T^{*2}}{\widehat{\sigma_{i}}^{2}}\\}|\widehat{b_{i}}-\widehat{a_{i}}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq
2\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/10\sigma_{j}^{2},\frac{\sqrt{2}T^{*}}{\sigma_{i}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{2}{\sigma_{i}^{2}},T^{*2}\\}+\max_{i}\frac{\min\\{\frac{4}{\sigma_{i}^{4}},\frac{2T^{*2}}{\sigma_{i}^{2}}\\}6|b_{i}-a_{i}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq
240\frac{1}{{(\sum_{j=L+1}^{9n/10}\min\\{1/\sigma_{j}^{2},\frac{T^{*}}{\sigma_{i}}\\})^{2}}}\left(\sum_{i=L+1}^{9n/10}\min\\{\frac{1}{\sigma_{i}^{2}},T^{*2}\\}+\max_{i}\frac{\min\\{\frac{1}{\sigma_{i}^{4}},\frac{T^{*2}}{\sigma_{i}^{2}}\\}|b_{i}-a_{i}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle\leq
240\frac{1}{{\frac{1}{16}(\sum_{j=1}^{n}\min\\{1/\sigma_{j}^{2},\frac{T^{*}}{\sigma_{i}}\\})^{2}}}\left(\sum_{i=1}^{n}\min\\{\frac{1}{\sigma_{i}^{2}},T^{*2}\\}+\max_{i}\frac{\min\\{\frac{1}{\sigma_{i}^{4}},\frac{T^{*2}}{\sigma_{i}^{2}}\\}|b_{i}-a_{i}|^{2}}{\epsilon^{2}}\right)$
$\displaystyle=3840\cdot{\rm Var}(\widehat{p}_{\epsilon}^{\rm ideal})$

The first equality simply follows from the definition of the estimator and
basic properties of the variance, as well as the fact that ${\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})\leq\sigma_{i}$. The first inequality
follows from the fact that $\sigma_{i}^{2}\leq 2\hat{\sigma_{i}}^{2}$, which
was shown in Lemma 4.2. The second inequality is simply pulling out the
constant to the front. The third inequality follows from the definition of
$\hat{T}$ as the optimiser of the variance using the approximations
$\widehat{\sigma_{i}}^{2}$, $\hat{b_{i}}$ and $\hat{a_{i}}$. The fourth
inequality follows from the fact that
$\widehat{\sigma_{i}}^{2}\in\left[\frac{1}{2}\sigma_{i}^{2},10\sigma_{i}^{2}\right]$
and $|\widehat{b}_{i}-\widehat{a}_{i}|\leq 4|b_{i}-a_{i}|$, as shown in Lemma
4.2, and will hold with probability $1-2\beta$, by taking a union bound over
the $\beta$ failure probabilities from each of the
$\rm\texttt{mean}_{\epsilon,\delta}$ and $\texttt{variance}_{\epsilon,\delta}$
subroutines. The fifth inequality simply pulls out the constants (240=10*4*6).
The final inequality follows from Equation (17) above. The final equality
follows from definition of $\widehat{p}_{\epsilon}^{\rm ideal}$ and the
assumption that $\frac{1}{2}\sigma_{i}^{2}\leq{\rm
Var}([\widehat{p}_{i}]_{a_{i}}^{b_{i}})$.

∎

##  Appendix C Proofs from Section 4.4

###### Proof of privacy claim in Theorem 4.3.

Let us begin with the privacy proof. The population is broken into three
cohorts. Let us consider each cohort individually. First, consider the $L$
individuals with the most data. They participate in private releases in lines
(3) ($(\epsilon,\delta)$-DP), and (5) ($\epsilon$-DP). Using the simple
composition rule of differential privacy [Dwork et al., 2006], Algorithm 3 is
$(2\epsilon,\delta)$-DP with respect to these users.

Next, consider the $1/10$th of users with the least data. These users
participate in lines (2) ($(\epsilon,\delta)$-DP) and (5) ($\epsilon$-DP).
Again using the simple composition rule of differential privacy, Algorithm 3
is $(2\epsilon,\delta)$-DP with respect to these users.

Finally, let us consider the the group consisting of users $i\in[L+1,9n/10]$.
These users first participate in line (5) ($\epsilon$-DP). The post-processing
guarantee of differential privacy states that we can now use these statistics
in the subsequent computations without paying additionally for their privacy.
Lines (7) - (9) are pre-processing for the computation of $\tilde{N}$. The
algorithm releasing $\tilde{N}$ is a simple application of the Laplace
mechanism since each $v_{i}\in[0,\frac{1}{\widehat{\sigma_{\min}}^{2}}]$, and
hence is $\epsilon$-differentially private. The computation of $\Lambda$ in
line (12) does not additionally touch the users data. The final estimate
$\widehat{p}_{\epsilon}$ is an application of the propose-test-release
framework on the function
$\mathcal{M}(\cdot\;;\widehat{k_{T}},n,\widehat{p}_{\epsilon}^{\rm
initial},\widehat{\sigma}_{p}^{2})$ with proposed sensitivity $\Lambda$. This
is a generic application of the propose-test-release framework, so we refer
the reader to [Dwork and Lei, 2009] for a proof that this final step of the
algorithm is $(\epsilon,\delta)$-differentially private. Therefore, again
using the composition theorem, Algorithm 3 is $(3\epsilon,2\delta)$-DP with
respect to this final set of users. ∎

See 4.4

###### Proof of Lemma 4.4.

Let
$\sigma_{\max}^{2}=\tfrac{1}{k_{\min}}\hat{p}(1-\hat{p})+(1-\tfrac{1}{k_{\min}})\hat{\sigma_{p}^{2}}$,
$\sigma_{\min}^{2}=\tfrac{1}{k_{\max}}\hat{p}(1-\hat{p})+(1-\tfrac{1}{k_{\max}})\hat{\sigma_{p}^{2}}$,
$v_{\max}=1/\sigma_{\min}^{2}$ and $v_{\min}=1/\sigma_{\max}^{2}$. Note that
as in Equation (4.2), the condition that $k_{\max}/k_{\min}\leq A$ implies
that $\sigma_{\max}^{2}\leq A\sigma_{\min}^{2}$ and, equivalently,
$v_{\max}\leq Av_{\min}$.

Let $D=\\{(\widehat{p}_{i},k_{i})\\}_{i=1}^{n}$ be a dataset of size $n$ where
each $\widehat{p}_{i}\sim\mathcal{D}(k_{i})$ where $\mathcal{D}$ has mean $p$
and variance $\sigma_{p}^{2}$. It suffices to show that for any database
$D^{\prime}$, which is a $\kappa$-neighbour of $D$ where
$0\leq\kappa\leq\Upsilon+1$, and any $j\in[n]$, if $D^{\prime}_{-j}$ is
$D^{\prime}$ where the data of the $j$th data subject has been removed, then,

$\left|\mathcal{M}(D^{\prime};k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)-\mathcal{M}(D^{\prime}_{-j};k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)\right|\leq
6\frac{v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\sum_{i=1}^{n}v_{i}}.$
(18)

The final result is then a simple application of the triangle inequality.

Our proof that Equation (18) holds with high probability for all
$\kappa$-neighbours of $D$ relies on the fact that with probability $1-\beta$,
$D$ is such that all subsets $S$ of $D$ of size at least $m\geq n-\Upsilon-1$,
$\mathcal{M}(S;k_{\max},m,\hat{p},\hat{\sigma_{p}}^{2})$ is concentrated
around $p$. Let $I$ be a subset of $[n]$ of size $n-\kappa$ where
$\kappa\leq\Upsilon+1$. Then

$\displaystyle{\rm
Var}(\mathcal{M}(S;k_{\max},n-\kappa,\hat{p},\hat{\sigma_{p}}^{2},\alpha))$
$\displaystyle\leq{\rm Var}\left(\frac{\sum_{i\in
I}v_{i}[\widehat{p}_{i}]_{\widetilde{a_{i}}}^{\widetilde{b_{i}}}}{\sum_{i\in
I}v_{i}}\right)$ $\displaystyle=\frac{\sum_{i\in
I}\frac{1}{({\widetilde{\sigma_{i}^{2}}})^{2}}\sigma_{i}^{2}}{\left(\sum_{i\in
I}\frac{1}{{\widetilde{\sigma_{i}^{2}}}}\right)^{2}}$ $\displaystyle\leq
2\frac{1}{\sum_{i\in I}\frac{1}{{\widetilde{\sigma_{i}^{2}}}}}$
$\displaystyle\leq 2\frac{1}{\frac{n-\kappa}{A}\frac{1}{\sigma_{\min}^{2}}}$
$\displaystyle=\frac{2A}{n-\kappa}\sigma_{\min}^{2}$

where the first inequality follows from $\sigma_{i}^{2}\leq
2{\widetilde{\sigma_{i}^{2}}}$ by Lemma 4.2 and the definition of
$\widetilde{\sigma_{i}^{2}}$ from line (7) of Algorithm 4. The second from the
fact that ${\widetilde{\sigma_{i}^{2}}}\leq A\sigma_{\min}^{2}$ for all
$i\in[n]$. Let $\Gamma=\sum_{\kappa=0}^{\Upsilon+1}\binom{n}{\kappa}$ be the
number of subsets of $D$ of size greater than $n-\Upsilon-1$. By the
concentration assumption on
$\mathcal{M}(S;k_{\max},n-\kappa,\hat{p},\hat{\sigma_{p}}^{2})$, with
probability $1-\frac{\beta}{\Gamma}$,

$\left|\mathcal{M}(S;k_{\max},n-\kappa,\hat{p},\hat{\sigma_{p}}^{2},\alpha))-p\right|\leq\sigma_{\min}\sqrt{\log\frac{\Gamma}{\beta}\frac{2A}{n-\kappa}}\leq\sigma_{\min}\sqrt{\log\frac{n}{\beta}}$
(19)

Note that $\Gamma\leq n^{\Upsilon+1}$ so the second inequality follows from
the conditions on $A$. Applying a union bound, with probability $1-\beta$, eqn
(19) holds simultaneously for all subsets of $D$ of sufficiently large size.
For the remainder of the proof, let us assume that this holds.

Let $D^{\prime}$ be a $\kappa$-neighbour of $D$ where
$0\leq\kappa\leq\Upsilon+1$. Without loss of generality, assume that
$D^{\prime}~{}=~{}\\{(\widehat{p}_{i}^{\prime},k_{i}^{\prime})\\}_{i=1}^{n}$
where $(\widehat{p}_{i}^{\prime},k_{i}^{\prime})=(\widehat{p}_{i},k_{i})$ for
$i\in[n-\kappa]$. In order to use this simplification, we will not assume that
the $k_{i}^{\prime}$ are in descending order. Let the $v_{i}$ be the un-
normalised weights corresponding to $D^{\prime}$, as defined in line (8) of
Algorithm 4. Note that the $v_{i}$ depends only on the data of user $i$, not
the data of any other individual in the data set. Then

$\displaystyle\Big{|}\mathcal{M}(D^{\prime};k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)-$
$\displaystyle\mathcal{M}(D^{\prime}_{-j};k_{\max},n-1,\hat{p},\hat{\sigma_{p}}^{2},\alpha)\Big{|}=\left|\frac{\sum_{i=1}^{n}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n}v_{i}}-\frac{\sum_{i=1,i\neq
j}^{n}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1,i\neq j}^{n}v_{i}}\right|$
$\displaystyle=\frac{v_{j}}{\sum_{i=1}^{n}v_{i}}\left|\widehat{p}_{j}^{\prime}-\frac{\sum_{i=1,i\neq
j}^{n}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1,i\neq j}^{n}v_{i}}\right|$
$\displaystyle\leq\frac{v_{j}}{\sum_{i=1}^{n}v_{i}}\left(\left|\widehat{p}_{j}^{\prime}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}}{\sum_{i=1}^{n-\kappa}v_{i}}\right|+\left|\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}}{\sum_{i=1}^{n-\kappa}v_{i}}-\frac{\sum_{i=1,i\neq
j}^{n}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1,i\neq
j}^{n}v_{i}}\right|\right).$ (20)

We will bound the two terms separately. For the first term in Equation (20),
we will use the fact that
$\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-\kappa}v_{i}}$
is concentrated around $p$, and $\hat{p}_{j}^{\prime}$ is truncated to within
$\alpha+f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ of $p$.
So

$\left|\widehat{p}_{j}^{\prime}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}}{\sum_{i=1}^{n-\kappa}v_{i}}\right|\leq\max\left\\{2(\alpha+f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)),\sigma_{\min}\sqrt{\log\frac{n}{\beta}}\right\\}\leq
4f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta),$

where the second inequality follows since
$\max\\{\alpha,\frac{1}{2}\sigma_{\min}\sqrt{\log\frac{n}{\beta}}\\}\leq
f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$ and Eqn (19).

Next, let us handle the second term in Equation (20). Assume that $j=n$ to
simplify notation:

$\displaystyle\left|\frac{\sum_{i=1}^{n-1}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-1}v_{i}}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-\kappa}v_{i}}\right|$
$\displaystyle=\left|\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}}{\sum_{i=1}^{n-1}v_{i}}\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=n-\kappa+1}^{n-1}v_{i}}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-\kappa}v_{i}}\right)\right|$
$\displaystyle\leq\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}}{\sum_{i=1}^{n-1}v_{i}}\right)\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}\left|\widehat{p}_{i}^{\prime}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-\kappa}v_{i}}\right|}{\sum_{i=n-\kappa+1}^{n-1}v_{i}}\right)$
$\displaystyle\leq\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}}{\sum_{i=1}^{n-1}v_{i}}\right)\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}\max\\{(2\alpha+2f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\widehat{\sigma}_{p}^{2},\beta)),\sigma_{\min}\sqrt{\log\frac{n}{\beta}}\\}}{\sum_{i=n-\kappa+1}^{n-1}v_{i}}\right)$
$\displaystyle\leq\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}}{\sum_{i=1}^{n-1}v_{i}}\right)\left(\frac{\sum_{i=n-\kappa+1}^{n-1}v_{i}4f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\widehat{\sigma}_{p}^{2},\beta)}{\sum_{i=n-\kappa+1}^{n-1}v_{i}}\right)$
$\displaystyle\leq\left(\frac{4\sum_{i=n-\kappa+1}^{n-1}v_{i}f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\widehat{\sigma}_{p}^{2},\beta)}{\sum_{i=1}^{n-1}v_{i}}\right)$
$\displaystyle\leq
4\kappa\left(\frac{\max_{i}v_{i}f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\widehat{\sigma}_{p}^{2},\beta)}{\sum_{i=1}^{n-1}v_{i}}\right)$

By assumption,
$\max_{i}v_{i}f^{\widetilde{k_{i}}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)\leq
v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$. Also,
$\sigma_{k_{i}^{\prime}}^{2}\leq A\sigma_{k_{\max}}^{2}$ so we have
$\sum_{i=1}^{n-1}v_{i}\geq\frac{n-1}{A}v_{k_{\max}}$. Therefore,

$\displaystyle\left|\frac{\sum_{i=1}^{n-1}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-1}v_{i}}-\frac{\sum_{i=1}^{n-\kappa}v_{i}\widehat{p}_{i}^{\prime}}{\sum_{i=1}^{n-\kappa}v_{i}}\right|$
$\displaystyle\leq
4\kappa\frac{v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)}{\frac{n-1}{A}v_{k_{\max}}}$
$\displaystyle\leq\frac{4\kappa
A}{n-1}f^{k_{\max}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta).$ $\displaystyle\leq
2f^{k_{\max}}_{\mathcal{D}}(n,\sigma_{p}^{2},\beta)$

where the second inequality follows from
$A\leq\frac{n-1}{2(\Upsilon+1)}\leq\frac{n-1}{2\kappa}$, which holds by
assumption. Therefore,

$\displaystyle\Big{|}\mathcal{M}(D^{\prime};k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)-\mathcal{M}(D^{\prime}_{-j};k_{\max},n-1,\hat{p},\hat{\sigma_{p}}^{2},\alpha)\Big{|}$
$\displaystyle\leq\frac{v_{j}}{\sum_{i=1}^{n}v_{i}}\cdot(4f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)+2f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta))$
$\displaystyle\leq 6\frac{v_{j}}{\sum_{i=1}^{n}v_{i}}\cdot
f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)$

Taking the max over $j$, we again have that
$\max_{j}v_{j}f^{\widetilde{k_{j}}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)\leq
v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)$ so for
all $j$,

$\displaystyle\Big{|}\mathcal{M}(D^{\prime};k_{\max},n,\hat{p},\hat{\sigma_{p}}^{2},\alpha)-\mathcal{M}(D^{\prime}_{-j};k_{\max},n-1,\hat{p},$
$\displaystyle\hat{\sigma_{p}}^{2},\alpha)\Big{|}\leq
6\frac{v_{k_{\max}}f^{k_{\max}}_{\mathcal{D}}(n,\hat{\sigma_{p}}^{2},\beta)}{\sum_{i=1}^{n}v_{i}}$

∎

######  Lemma C.1.

Given $\epsilon>0$, $\delta\in[0,1]$, $\beta\in[0,1]$,
$k_{\max}\in\mathbb{N}$, and $L\in[n]$, there exists a mechanism
$\texttt{EM}_{\epsilon}(k_{1},\cdots,k_{n};L,k_{\max})$ which is
$(\epsilon,\delta)$-DP, and with probability $1-\beta$, and outputs
$\widehat{k_{L}}$ such that

$k_{L+\frac{1}{\epsilon}(\ln k_{\max}+\ln(1/\beta))}\leq\widehat{k_{T}}\leq
k_{L-\frac{1}{\epsilon}(\ln k_{\max}+\ln(1/\beta))}$

###### Proof.

There are several existing algorithms in the literature that can be used to
privately estimate the $L$-th order statistic $\widehat{k_{L}}$ with the
desired accuracy. A simple algorithm [Dwork and Lei, 2009, Thakurta and Smith,
2013, Johnson and Shmatikov, 2013, Alabi et al., 2020, Asi and Duchi, 2020]