in a,…,z in A,…,Z in A,…,Z in A,…,Z

# Empirical Mean and Frequency Estimation Under Heterogeneous Privacy: A
Worst-Case Analysis

Syomantak Chaudhuri
University of California, Berkeley
<EMAIL_ADDRESS>
&Thomas A. Courtade
University of California, Berkeley
<EMAIL_ADDRESS>
###### Abstract

Differential Privacy (DP) is the current gold-standard for measuring privacy.
Estimation problems under DP constraints appearing in the literature have
largely focused on providing equal privacy to all users. We consider the
problems of empirical mean estimation for univariate data and frequency
estimation for categorical data, two pillars of data analysis in the industry,
subject to heterogeneous privacy constraints. Each user, contributing a sample
to the dataset, is allowed to have a different privacy demand. The dataset
itself is assumed to be worst-case and we study both the problems in two
different formulations – the correlated and the uncorrelated setting. In the
former setting, the privacy demand and the user data can be arbitrarily
correlated while in the latter setting, there is no correlation between the
dataset and the privacy demand. We prove some optimality results, under both
PAC error and mean-squared error, for our proposed algorithms and demonstrate
superior performance over other baseline techniques experimentally.

##  1 Introduction

Mean and frequency estimation are pillars of data analysis. Empirical mean
estimation plays a crucial role in fields like Modern Portfolio Theory [1],
Machine Learning [2], and Healthcare [3] to name a few. For service providers,
relative frequencies of categorical data is an import statistic such as
distribution of traffic across websites [4], age and geographical distribution
of social media users [5], and so on. Thus, it is crucial to study the
estimation of these statistics under the lens of privacy due to the increased
demand for privacy, as reflected in recent laws such as GDPR and CCPA. We
adopt the popular framework of Differential Privacy [6, 7], which has found
real-world applications [8, 9, 10].

The trade-off between estimation accuracy and afforded privacy is one of the
most fundamental questions in this field. An aspect of estimation subject to
privacy constraints that has not been studied well in literature is the case
when different users demand different levels of privacy for their data.
Existing literature mostly focus on a common privacy level for the users (see
Wang et al. [11] for references), but this does not reflect the real-world
where different users have different privacy requirements [12]. These
heterogeneous privacy demands naturally arise in social media platforms, where
users can get more features by opting-in to share more data. For example, in a
discontinued feature, users on Facebook could share their location with
Facebook in order to get notified if a friend is nearby [13]. Thus,
heterogeneity in privacy requirements is an important consideration and there
needs to be a greater understanding of the accuracy-privacy trade-off. The
presented work focuses on understanding this trade-off for mean and frequency
estimation.

###  1.1 Our Contribution and Problem Description

We consider the problem of mean estimation of univariate data and frequency
estimation of categorical data under heterogeneous privacy demands in the
Central-DP model. In Central-DP, the users trust the server and send their
true data to the server [7]. The users provide the server with their datapoint
(such as their salary in mean estimation or salary bracket in frequency
estimation) and a privacy level. The server is then tasked with publishing an
estimate of the mean or relative frequencies of the categories in the dataset,
while respecting the individual privacy constraints. We consider the
adversarial minimax setting where the dataset is the worst-case for the
algorithm. This is in contrast to the statistical minimax setting where the
dataset is sampled from the worst-case distribution. Under the adversarial
regime, we formulate two distinct settings: the so-called correlated and
uncorrelated settings. These are explained below, and formally defined in
Section 2. Each problem is studied in each setting under both PAC error and
mean-squared error.

Since we assume that we are given the heterogeneous privacy demands, simply
considering the worst-case dataset might lead to arbitrary correlations
between user data values and their individual privacy requirements.
Correlations may be reasonable for certain cases. For example, users sharing
their salary may demand higher privacy if they are have an extremely high or
low salary. Such correlations make it harder to estimate frequencies of
categories in which users demand a lot more privacy; this is a problem for
mean estimation as well. We emphasize that such correlations, although often
accepted to be present in real-world, have never been modeled in the
literature prior to this work that the authors are aware of.

It is equally well-motivated to consider the uncorrelated setting where users
do not have a correlation between their data and privacy demand. For example,
for frequency estimation of users’ geographical-region, there may be no
meaningful correlation between a user’s location and their privacy demand. We
formulate this “uncorrelated" setting by modeling the realization of the
dataset as a uniformly random permutation of a worst-case dataset.

We propose algorithms for both PAC error and mean-squared error, for both
correlated and uncorrelated settings, for both mean and frequency estimation.
Thus, in this work, we consider eight different minimax rates. To obtain tight
upper bounds on the minimax rates, we consider slightly different algorithms
tailored to each combination of problem, setting, and error metric. However,
we also present a fast heuristic algorithm that is agnostic to the underlying
modeling assumptions and performs well in practice for all the eight problems.
We compare our algorithms to natural baseline algorithms and show superior
performance of our algorithms. We also prove the minimax optimality of our
algorithms in some problems and error metrics.

Organization: We define the problem in Section 2 and describe our algorithm in
Section 3. Experiments are presented in Section 4, followed by theoretical
analysis of the minimax rate in Section 5. Extended discussion can be found in
Section 6, followed by some concluding remarks.

###  1.2 Related Work

The two most common models for DP are the Central-DP model and the Local-DP
model. In Local-DP, users do not trust the server and send noisy data to the
server, ensuring their privacy (see Kasiviswanathan et al. [14] for more
details). In this work, we focus on the Central-DP model.

The problem of frequency estimation under privacy constraints is well-studied
under homogeneous DP [7, 15, 8, 16]. In terms of heterogeneity in privacy
demands, a special case considered in the literature is the existence of a
dataset requiring homogeneous privacy in conjunction with a public dataset
[17, 18, 19, 20, 21, 15, 22, 23, 24]. Mean estimation under privacy is well-
studied as well (see Biswas et al. [25] for references). Although most work on
mean estimation focuses on the statistical setting, one can use the ideas from
empirical frequency estimation of Dwork et al. [7] and corresponding lower
bounds from Vadhan [26] to come up with good error bounds for empirical mean
estimation.

Alaggan et al. [27] and Jorgensen et al. [28] have proposed task-agnostic
methods to deal with Heterogeneous DP (HDP). While their methods are versatile
since they are task agnostic, one can not expect competitive performance from
their methods for specific tasks like mean or frequency estimation. Further,
neither of the methods can handle the case if there is a single user having no
privacy demand (public data).

Mean estimation under Heterogeneous DP (HDP) is considered by Ferrando et al.
[29] in the Local-DP model, assuming the variance of the distribution is
known. HDP mean estimation under the Central-DP model has been studied in
Fallah et al. [30], Chaudhuri and Courtade [31], Chaudhuri et al. [32],
Cummings et al. [33]; these works have focused on the statistical setting
where the data is sampled i.i.d. from some distribution. The problem of
creating confidence intervals for the mean under sequential observations in
Local-DP was studied by Waudby-Smith et al. [34] for univariate random
variables with heterogeneity in privacy demand. Canonne and Sun [35] present
the problem of testing whether two datasets are from the same multinomial
distribution under a different privacy constraint for each dataset. HDP has
also been considered in the context of mechanism design, auctions, and data
valuation [30, 36, 37]. Acharya et al. [38] study the problem of ridge
regression under HDP and provide an algorithm similar to one of our baseline
techniques we use in the experiments. 111Their method can perform arbitrarily
worse than the minimax optimal ridge regression algorithm (see Prop algorithm
in Section 4 to understand why).

In the context of modeling correlations between privacy demand and data, the
authors are only aware of the work by Ghosh and Roth [39] \- a negative result
in the context of auction design. The question of how to deal with
correlations between data and privacy is a crucial one in HDP. However, the
literature lacks any proper formulation of the problem itself.

##  2 Problem Definition

###  2.1 Notation

We denote positive real numbers by $\bbR_{>0}$. The notation $[n]$ refers to
the set $\\{1,2,\ldots,n\\}$. The probability simplex in $n$-dimensions is
represented by $\Delta_{n}$. Throughout this work the $\ell_{1}$ norm,
$\lVert\cdot\rVert_{1}$, is interchangeably used for sum of elements of
vectors with positive components. The notation $a\wedge b$ is used to denote
$\min\\{a,b\\}$. We shall use $\lceil\cdot\rceil$ to refer to the modified
ceiling function $\lceil x\rceil=\min\\{m\in\bbZ:m>x\\}$. The notation
$c\bm{1}$ shall denote the vector, of appropriate length, with all entries
being equal to $c$. In this work, the notation $M(\cdot)$, for a randomized
algorithm $M$ mapping $\cX^{n}$ to a probability distribution on ${\cY}$, will
interchangeably be used to refer to the output distribution or a sample from
it. For vectors $\vecx$ and $\vecy$, $\vecx/\vecy$ shall represent element-
wise division. The notations $\lesssim$ and $\simeq$ denote inequality and
equality that hold up to a universal multiplicative constant.

###  2.2 Problem Definition

Heterogeneous Differential Privacy (HDP) permits users to have different
privacy requirements. The standard definition for HDP is presented in
Definition 2.1 [27, 30].

######  Definition 2.1 (Heterogeneous Differential Privacy).

A randomized algorithm $M:\cX^{n}\to\cY$ is said to be $\bm{\epsilon}$-DP for
$\bm{\epsilon}\in\bbR_{>0}^{n}$ if

$\mathbb{P}\\{M(X)\in S\\}\leq e^{\epsilon_{i}}\mathbb{P}\\{M(X^{\prime i})\in
S\\}\ \ \ \forall i\in[n],$ (1)

for all measurable sets $S\subseteq\cY$, where $X,X^{\prime i}\in\cX^{n}$ are
any two ‘neighboring’ datasets that differ arbitrarily in only the $i$-th
component.

The probability in Definition 2.1 is taken over the randomized algorithm
conditioned on the given datasets $X,X^{\prime i}$, i.e., it is a conditional
probability. In the DP framework, smaller $\epsilon$ means higher privacy. The
privacy levels $\epsilon$ can range from zero to infinity.

Let $n$ be the number of users and let the heterogeneous privacy demand of the
users be the vector $\bm{\epsilon}$. Without loss of generality, we assume it
is arranged in a non-decreasing order, i.e., user $i$ has privacy requirement
$\epsilon_{i}$, and $\epsilon_{i}\leq\epsilon_{j}$ for $i\leq j$. We operate
in the Central-DP regime and assume that the privacy demand is public as
stated in 2.2; we justify it in Section 2.3.

######  Assumption 2.2.

The privacy demand $\bm{\epsilon}$ is public.

For normalized frequency estimation with $k$ categories (or bins), we have
$\cX=[k]$ and $\cY=[0,1]^{k}$; the parameter $k$ is assumed to be known. For
mean estimation, without loss of generality, we consider $\cX=[0,1]$ and
$\cY=[0,1]$; one can consider arbitrary length intervals as long as the length
of the interval is known, the position of the interval does not need to be
known.

We study the problem in the adversarial minimax regime – for an algorithm, the
worst case performance over all datasets is analyzed. We formulate two
settings to capture possible correlations.

In order to define the two settings, let the underlying dataset be denoted by
$D\in\cX^{n}$.

  * •

Correlated setting: In this setting, the dataset is simply $D$. In other
words, user $i$ has privacy demand $\epsilon_{i}$ and datapoint $D_{i}$ for
$i\in[n]$.

  * •

Uncorrelated setting: In this setting, to break correlations between the
dataset and the privacy demand, we assume that the actual realization of the
dataset is a random uniform permutation of $D$. Let $\sigma:[n]\to[n]$ denote
a random permutation over $[n]$ then we shall denote the realization of the
dataset as $D_{\sigma}$, i.e., user $i$ has the datapoint $D_{\sigma(i)}$ and
privacy demand $\epsilon_{i}$. The notation $\sigma(i)$ indicates which
element of $D$ gets mapped to the $i$-th user.

Let $\mu(D)$ refer to the true empirical statistic of the dataset. In other
words,

  * •

for mean estimation, $\mu(D)\in[0,1]$ and it is defined as
$\mu(D)=\frac{1}{n}\sum_{i=1}^{n}D_{i}$.

  * •

for frequency estimation, $\mu(D)\in\Delta_{k}$ and the $j$-th component of
$\mu(D)$ is defined as
$\mu(D)_{j}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\\{D_{i}=j\\},\ j\in[k]$.

Note that this function is permutation-invariant $\mu(D)=\mu(D_{\sigma})$. Let
$\cM_{\bm{\epsilon}}$ refer to the set of all $\bm{\epsilon}$-DP mechanisms
from $\cX^{n}$ to $\cY$. We define the minimax rates of frequency estimation
in Definition 2.3.

######  Definition 2.3 (Minimax Rates of Frequnecy Estimation).

The PAC-minimax rate for $k$ bins, privacy demand $\bm{\epsilon}$, and error
probability $\beta$ is the minimum value of the $(1-\beta)$-th quantile of the
$\ell_{\infty}$ error under the worst-case dataset for any $\bm{\epsilon}$-DP
algorithm. The MSE-minimax rate is similarly defined.
(A) Correlated Setting: The PAC-minimax rate is given by

$\cR_{c}^{f}(k,\beta,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\min_{\bbP\\{\lVert
M(D)-\mu(D)\rVert_{\infty}>\alpha\\}\leq\beta}\alpha\ ,$ (2)

where the probability is taken over the randomness in the map $M$. The MSE-
minimax rate is given by

$\cE_{c}^{f}(k,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\bbE[\lVert
M(D)-\mu(D)\rVert_{\infty}^{2}]\ ,$ (3)

where the expectation is taken over the randomness in the map $M$.
(B) Uncorrelated Setting: The PAC-minimax rate is given by

$\cR_{u}^{f}(k,\beta,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\min_{\bbP\\{\lVert
M(D_{\sigma})-\mu(D)\rVert_{\infty}>\alpha\\}\leq\beta}\alpha\ ,$ (4)

where the probability is taken over the randomness in the map $M$ and the
uniform permutation $\sigma$ of the dataset $D$. The MSE-minimax rate is given
by

$\cE_{u}^{f}(k,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\bbE[\lVert
M(D_{\sigma})-\mu(D)\rVert_{\infty}^{2}]\ ,$ (5)

where the expectation is taken over the randomness in the map $M$ and the
uniform permutation $\sigma$ of the dataset $D$.

Similarly, we define the minimax rates for mean estimation in Definition A.1,
deferred to Appendix A.

###  2.3 Modeling Choice

On 2.2: In the worst-case, where arbitrary correlation between the data and
the privacy demands are allowed, knowing the privacy demand can leak all
information about the data. Indeed, one example would be the case where the
privacy demand is equal to the data! Protecting the privacy demand in addition
to the data is a more complex problem that is not yet studied in literature
and hence, we simplify the problem by assuming the privacy demand itself is
public and does not need to be protected. With this assumption, our algorithm
does not leak any extra information than claimed. This assumption is indeed
encountered in certain practical scenarios like social media where anyone can
see if some user has decided to keep their profile and data private. Since no
prior work has ever tried to model these correlations, we view our work as a
first step in this crucial direction. There do exist cases where privacy
demands should also be protected but that is beyond the scope of this work.
One possible way to decrease such privacy risks is if the service provider
allows the users to choose their privacy from a set of pre-determined privacy
levels, as is typical in many practical systems.t

On the minimax rates and correlations: Since we consider the error bounds for
a given privacy demand and an adversarial dataset, there could be an arbitrary
correlation between the dataset and the privacy demand in the correlated
setting. Considering arbitrary worst-case correlations avoids the need for
obscure assumptions on joint distribution between privacy and data. This may
or may not be desired, depending on the application. For example, if the
categorical data consists of salary range of users, then the users in the
highest and lowest salary range might demand a higher privacy leading to
correlations between data and privacy demands. A counterexample is if the
categorical data consists of different types of cancers in patients; in this
case such correlations need not exist in a meaningful way. Thus, to model such
setting without meaningful correlations, we formulate the uncorrelated
setting. Another possible way to break the correlation is to go to the
statistical minimax setting where the samples are generated i.i.d. from some
distribution, independent of the privacy demands, and the goal is to estimate
the underlying multinomial distribution.

The above described statistical minimax rate is not related to the correlated
adversarial minimax rate. To see this, consider the case where all the users
have no privacy constraint; the correlated adversarial minimax error is zero
but the statistical minimax error is of the order $\frac{1}{\sqrt{n}}$ (PAC or
square-root of MSE). Conversely, consider the case where $n/2$ users demand no
privacy and rest of the users demand $\epsilon\to 0$ – the statistical rate is
of the order $\frac{1}{\sqrt{n}}$ but the correlated adversarial minimax rate
is of the order $1$. However, the uncorrelated adversarial minimax rates and
the statistical minimax rates are closely related (see Theorem 5.3).

We do not consider the worst case of $\bm{\epsilon}$ since the worst-case is
trivial when every user demands full privacy ($\epsilon\to 0$) and no
meaningful estimation can be done. Other possible modeling choices, not
presented in this work, include a different norm for errors, the statistical
setting where the underlying dataset and privacy demand is jointly generated
according to some distribution, and so on.

##  3 Algorithm Description

Algorithm 1 Heterogeneously Private Frequency (HPF)

Input: weights $\vecw\in\Delta_{n}$, $X\in[k]^{n}$

Sample i.i.d.
$N_{1},\ldots,N_{k}\sim\text{Laplace}(2\|\frac{\vecw}{\bm{\epsilon}}\|_{\infty})$

Calculate $\vecy\in\bbR^{k}$:
$y_{j}=N_{j}+\sum_{i=1}^{n}w_{i}\mathbb{I}\\{X_{i}=j\\},\ \ \forall j\in[k].$

Set $y_{j}\leftarrow\max\\{\min\\{y_{j},1\\},0\\}$ $\forall j\in[k]$.

return $\vecy$

Table 1: Weights for Algorithm 1 for different settings.

Algorithm | Weights $\vecw$
---|---
HPF-C | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{C}(\vecw,k,\beta,\bm{\epsilon})$
HPF-C | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{C}(\vecw,k,1,\bm{\epsilon})$
HPF-U | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{U}(\vecw,k,\beta,\bm{\epsilon})$
HPF-U | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{U}(\vecw,k,1,\bm{\epsilon})$
HPF-A | $\frac{1-e^{-\bm{\epsilon}}}{\lVert 1-e^{-\bm{\epsilon}}\rVert_{1}}$

Let

$\displaystyle r_{C}(\vecw,k,\beta,\bm{\epsilon})^{2}$
$\displaystyle=\left\|\vecw-\frac{\bm{1}}{n}\right\|^{2}_{1}+\log\left(\frac{k}{\beta}\right)^{2}\left\|\frac{\vecw}{\bm{\epsilon}}\right\|_{\infty}^{2},$
(6) $\displaystyle r_{U}(\vecw,k,\beta,\bm{\epsilon})^{2}$
$\displaystyle=\left(\left\|\vecw-\frac{\bm{1}}{n}\right\|^{2}_{1}\wedge\log\left(\frac{k}{\beta}\right)\lVert\vecw\rVert_{2}^{2}\right)+\log\left(\frac{k}{\beta}\right)^{2}\left\|\frac{\vecw}{\bm{\epsilon}}\right\|_{\infty}^{2}.$
(7)

These functions help us track the errors for problems. For frequency
estimation, we propose a family of algorithms HPF with the skeleton code
presented in Algorithm 1. Section 3 outlines our suggested weights to be used
in HPF for the relevant setting. Note that these different weight suggestions
are mainly to obtain theoretically good performance in the respective setting.
For example, to get good theoretical performance under PAC metric for error
level $\beta$ in the correlated setting, one would use the weights given by
HPF-C from the table. The second-last letter of the algorithm names specify if
the algorithm is for correlated setting (C) or uncorrelated setting (U). The
last letter specifies if the algorithm is geared for optimizing the PAC error
() error or the MSE error ().

While these methods are intended to facilitate characterization of fundamental
limits, an alternate fast, heuristic-based algorithm HPF-A is also described
which can be used in either setting and error metric, i.e., it is agnostic to
the modeling assumptions and error metric. We stress that while we propose a
different algorithm based on the setting and error metric for proving
theoretical guarantees, HPF-A can be used agnostic to the setting since it
enjoys good performance (see Section 4) across the settings and metric, and
can be employed in practice.

Similarly, for mean estimation, we propose the family of algorithms HPM
presented in Algorithm 2 and the corresponding weights are presented in
Appendix A, both deferred to Appendix A.

The performance guarantees for the algorithms and lower bounds on the minimax
rate can be found in Section 5. Lemma 3.1 guarantees that the algorithms
described in Algorithm 1 satisfy the privacy constraint; the proof can be
found in Appendix D.

######  Lemma 3.1.

The proposed family of algorithms HPF and HPM satisfy the $\bm{\epsilon}$-DP
constraint defined in Definition 2.1.

Broadly, our proposed algorithms assign different weights to different users
instead of equally weighing the users for the estimation task. For example, in
frequency estimation, for weights $\vecw\in\Delta_{n}$, if user $i$ has a
datapoint in bin $j$, then HPF adds $w_{i}$ to bin $j$ instead of
$\frac{1}{n}$. In particular, if the users with more stringent privacy are
weighed less, then the magnitude of noise that is required to be added to the
frequency estimate for ensuring $\bm{\epsilon}$-DP can be significantly less.
On the flip side, this reweighing introduces bias in the output as the data
from less privacy stringent users dominates. Thus, the weights need to be
carefully chosen to optimize this trade-off.

The minimization in the algorithm minimizes an upper bound for error metric in
the relevant setting. For example, HPF-C minimizes an upper bound for the
$(1-\beta)$-th quantile of the $\ell_{\infty}$-error over the set of weights
$\vecw\in\Delta_{n}$. All the optimization problems are quadratic programs
with linear constraints and can be solved using a numerical optimizer like
cvxpy [40]. Faster variants of the algorithms which can be computed in
$O(n\log n)$ time are discussed in Section 6.

##  4 Representative Experiments

Figure 1: (A): The negative log MSE for six algorithms for three experiments
(higher is better) in the correlated regime is plotted. (B): The negative log
of the 95-th empirical error quantile for the six algorithms for three
experiments (higher is better) in the uncorrelated regime is plotted.

We only present some representative experiments for frequency estimation in
this section in Figure 1. More extensive experiments and exact implementation
details can be found in Appendix B. In Figure 1(A), we consider three
different datasets and construct a privacy demand that is correlated with the
categorical data. We aim to optimize the MSE ($l_{\infty}$ error) so the
variant of HPF that we employ is HPF-C. The negative of the log MSE is plotted
for the different algorithms. Similarly, in Figure 1(B), we consider three
different datasets and construct a privacy demand that is uncorrelated with
the categorical data. We aim to optimize the PAC error with $\beta=0.05$,
i.e., the 95-th quantile of the error so the variant of HPF that we employ is
HPF-U with $\beta=0.05$. The negative of the log of the 95-th empirical error
quantile is plotted for the different algorithms.

Overall, in both correlated and uncorrelated settings, under both PAC and MSE,
HPF-A is a superior algorithm due to it good performance and being agnostic to
the modeling choices and the error metric.

##  5 Performance Analysis

Recall the functions $r_{C}$ and $r_{U}$ from (6) and (7) respectively. We
denote their corresponding minimum values by

$R_{C}(k,\beta,\bm{\epsilon})=\left(\min_{\vecw\in\Delta_{n}}r_{C}(\vecw,k,\beta,\bm{\epsilon})\right)\wedge
1,$ (8)

and

$R_{U}(k,\beta,\bm{\epsilon})=\left(\min_{\vecw\in\Delta_{n}}r_{U}(\vecw,k,\beta,\bm{\epsilon})\right)\wedge
1.$ (9)

These functions are relevant in tracking the upper bound values in the various
settings.

We summarize our theoretical results in this section. Table 2 summarizes the
results presented in this work. The theorems can be found in Appendix C. For
the rest of the section, we focus on the question of minimax optimality - are
our upper and lower bounds of the same order?

Table 2: A summary of the theoretical results presented in this paper. The setting column specifies the problem – (F)requency estimation or (M)ean estimation, the setting – (C)orrelated or (U)ncorrelated, and the error metric – ()AC or MS(). The algorithm column specifies the algorithm used to obtain the upper bound in the next column, the functions $R_{C}$ and $R_{U}$ are defined in (8) and (9) respectively. The Lower Bound column references the location where the lower bounds can be found and the last column is on whether our upper and lower bounds are of the same order. Setting | Algorithm | Upper Bound (UB) | Lower Bound (LB) | UB $\simeq$ LB?
---|---|---|---|---
F, C,  | HPF-C  | $R_{C}(k,\beta,\bm{\epsilon})$ | Theorem C.3 | Yes
F, C,  | HPF-C  | $R_{C}(k,1,\bm{\epsilon})^{2}$ | ✗ | N/A
F, U,  | HPF-U  | $R_{U}(k,\beta,\bm{\epsilon})$ | Theorem C.3 | Under certain assumptions
F, U,  | HPF-U  | $R_{U}(k,1,\bm{\epsilon})^{2}$ | Theorem C.4 | Near-optimal
M, C,  | HPM-C  | $R_{C}(1,\beta,\bm{\epsilon})$ | Theorem C.3 | Yes
M, C,  | HPM-C  | $R_{C}(1,e,\bm{\epsilon})^{2}$ | ✗ | N/A
M, U,  | HPM-U  | $R_{U}(1,\beta,\bm{\epsilon})$ | Theorem C.3 | Under certain assumptions
M, C,  | HPM-U  | $R_{U}(1,e,\bm{\epsilon})^{2}$ | Theorem C.4 | Yes

###  5.1 Minimax Optimality in Correlated Regime

In the correlated regime, we present Theorem 5.1 on the minimax optimality of
HPF-C and HPM-C in a certain regime of interest of the PAC minimax rate. The
proof is presented in Appendix I.

######  Theorem 5.1 (PAC Minimax Optimality: Correlated Setting).

.
(A) For $\frac{1}{2n}\leq\cR_{c}^{f}(k,\beta,\bm{\epsilon})\leq\frac{1}{4}$,
the lower bound in Theorem C.3 implies that error incurred by HPF-C is of the
same order as the minimax rate, i.e.,

$\cR_{c}^{f}(k,\beta,\bm{\epsilon})\simeq R_{C}(k,\beta,\bm{\epsilon}).$

(B) For $\frac{1}{2n}\leq\cR_{c}^{m}(\beta,\bm{\epsilon})\leq\frac{1}{4}$, the
lower bound in Theorem C.3 implies that error incurred by HPM-C is of the same
order as the minimax rate, i.e.,

$\cR_{c}^{m}(\beta,\bm{\epsilon})\simeq R_{C}(1,\beta,\bm{\epsilon}).$

In particular, when the PAC minimax rate is at least $\frac{1}{2n}$ and at
most $\frac{1}{4}$, then our upper bound is of the same order as the minimax
rate, for both mean and frequency estimation. We emphasize that this really is
the regime of interest for the problem being considered; without any privacy
constraint, normalized mean and frequency count is naturally of the precision
$\frac{1}{n}$. Theorem C.3 also assumes that the PAC minimax rate is bounded
away from the trivial upper bound of $\frac{1}{2}$. Thus, for the practically
important regime of values of the PAC minimax rate, our proposed algorithms
are order optimal.

###  5.2 Minimax Optimality in Uncorrelated Regime

In the uncorrelated regime, to compare the PAC upper and lower bounds, we
consider two regimes. This is primarily because of the lower bounds presented
in Theorem C.3 are difficult to analyze without further simplifications. Let
$\mathsf{Var}(e^{-\bm{\epsilon}})$ denote the empirical variance of the vector
$e^{-\bm{\epsilon}}$. Theorem 5.2 shows how the upper and lower bounds behave
in the high privacy regime; the proof can be found in Appendix I.

######  Theorem 5.2 (PAC Minimax Optimality: Uncorrelated Setting).

.
Assume high privacy demand where $\lVert\bm{\epsilon}\rVert_{\infty}\leq 1$,
for the two problems.
(A) Frequency Estimation: In the regime
$\frac{1}{2n}\leq\cR_{u}^{f}(k,\beta,\bm{\epsilon})$, we have the following
upper and lower bound on $\cR_{u}^{f}$,

$\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}\lesssim\cR_{u}^{f}(k,\beta,\bm{\epsilon})\lesssim\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}+\frac{\sqrt{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})\wedge
n\log(k/\beta)}}{\lVert\bm{\epsilon}\rVert_{1}}.$ (10)

The upper bound is achieved by HPF-U and HPF-A. Further, if
$\mathsf{Var}(e^{-\bm{\epsilon}})\lesssim\frac{\log^{2}(k/\beta)}{n^{2}}$,
then we have

$\cR_{u}^{f}(k,\beta,\bm{\epsilon})\simeq\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}.$
(11)

(B) Mean Estimation: In the regime
$\frac{1}{2n}\leq\cR_{u}^{m}(\beta,\bm{\epsilon})$, we have the following
upper and lower bound on $\cR_{u}^{m}$,

$\frac{\log(1/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}\lesssim\cR_{u}^{m}(\beta,\bm{\epsilon})\lesssim\frac{\log(1/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}+\frac{\sqrt{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})\wedge
n\log(1/\beta)}}{\lVert\bm{\epsilon}\rVert_{1}}.$ (12)

The upper bound is achieved by HPM-U and HPM-A. Further, if
$\mathsf{Var}(e^{-\bm{\epsilon}})\lesssim\frac{\log^{2}(1/\beta)}{n^{2}}$,
then we have

$\cR_{u}^{m}(\beta,\bm{\epsilon})\simeq\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}.$
(13)

The high privacy assumption, i.e., $\lVert\bm{\epsilon}\rVert_{\infty}\leq 1$,
is helpful for dealing with the implicit lower bounds presented in terms of
expectation in Theorem C.3. Such assumptions on the privacy level are frequent
in the literature, even for homogeneous privacy [30, 41]. The downside to this
regime is that it does not explain what occurs if there are some users
desiring no privacy $(\epsilon\to\infty)$, i.e., there is some public data.
While HPF-U and HPM-U can handle such $\bm{\epsilon}$, the theorem can not. We
remark that the assumptions made in Theorem 5.2 might be a shortcoming of the
analysis and not the algorithm.

For the homogeneous privacy demand $\epsilon$, one can recover the minimax
rate $1/n\epsilon$ for homogeneous DP222See Dwork et al. [7] and Vadhan [26]
for upper and lower bounds respectively in homogeneous DP for frequency
estimation. from the theorem since the variance term is zero.

Before presenting Theorem 5.3, we define another minimax rate closely related
to the problem. For some set $S$, let $\cP(S)$ denote the set of probability
distributions on $S$. Similar to the MSE-minimax rates, we define the minimax
rate for mean estimation under $\bm{\epsilon}$-DP from i.i.d. data as

$\cE_{stat}(\bm{\epsilon})=\min_{M\in
M_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\bbE_{X_{1},\ldots,X_{n}\sim
P}[|M(X^{n})-\mu(P)|^{2}].$ (14)

We take a moment to comment on $\cE_{stat}(\bm{\epsilon})$. For $n$-users with
no privacy demand, let $\bm{\infty}=(\infty,\ldots,\infty)$, then note that
$\cE_{stat}(\bm{\infty})\simeq\frac{1}{n}$ as this is the standard minimax
rate for mean estimation without privacy constraints (see Wainwright [42] for
reference). If there is no privacy demand, then we also have
$\cE_{u}^{f}(k,\bm{\infty}),\cE_{u}^{m}(\bm{\infty})=0$. In Theorem 5.3, we
show MSE-minimax optimality of the proposed algorithms for the uncorrelated
setting in the regime of privacy demands where $\bm{\epsilon}$ causes a non-
trivial increase in the statistical rate $\cE_{stat}$ to be greater than
$\frac{1}{2n}$. In fact, in this regime, the MSE-minimax rates for empirical
mean and frequency estimation are nearly the same as the MSE-minimax rate for
statistical mean estimation.

######  Theorem 5.3 (MSE Bounds for Uncorrelated Setting).

.
For values of $\bm{\epsilon}$ satisfying
$\cE_{stat}(\bm{\epsilon})\geq\frac{1}{2n}$, HPF-U and HPM-U are minimax
optimal. Further,

$\cE_{stat}(\bm{\epsilon})\lesssim\cE_{u}^{f}(k,\bm{\epsilon})\lesssim\log(k)^{2}\cE_{stat}(\bm{\epsilon})$
(15)

for frequency estimation and

$\cE_{u}^{m}(\bm{\epsilon})\simeq\cE_{stat}(\bm{\epsilon})$ (16)

for mean estimation.

The proof can be found in Appendix J.

##  6 Extended Discussion

Efficient and approximate versions of HPF and HPM algorithms: The
minimizations in the HPF and HPM algorithms (except HPF-A and HPM-A) can be
the bottleneck in terms of computation and numerical stability. In order to
address these two concerns, one can consider making the upper bound loose by
replacing the $\ell_{1}$-norm with $n\ell_{2}$-norm (the latter upper bounds
the former). These variants of the algorithm can be efficiently implemented in
$O(n\log n)$ time using the algorithm presented by Chaudhuri et al. [32]. Some
experiments with this variant of the algorithm are presented in Appendix M.

Free Privacy: An interesting phenomenon in the context of estimation under
heterogeneous privacy constraints is the emergence of extra privacy given by
the algorithm to some of the users than what is required, contrary to the
intuition that invading more privacy should lead to improved
performance333This is true in homogeneous privacy in general.. When an HPF or
HPM algorithm uses weights $\vecw$ (in either setting), the privacy guarantee
for user $i$ is
$w_{i}/\lVert\vecw/\bm{\epsilon}\rVert_{\infty}\leq\epsilon_{i}$. The equality
only holds for every user when the weights are chosen proportional to the
privacy parameter, i.e., $\vecw\propto\bm{\epsilon}$. In the context of
minimax optimality, we know that this proportional weighing can be strictly
sub-optimal. Thus, there is a phenomenon of free and extra privacy afforded to
the users by the algorithm.

##  7 Conclusion

The problem of mean estimation of univariate data and frequency estimation of
categorical data under heterogeneous differential privacy is considered for an
adversarial data setting. We formulate two distinct problem settings, one for
scenarios where a correlation exists between the dataset and users’ privacy
demands, and another for scenarios where no such correlation exists. For each
problem, in each setting, we consider the minimax rate under mean squared
error and PAC error. For each of the eight combinations of problem, setting,
and error metric, we demonstrate good upper bounds on the corresponding
minimax rates by analysis of an algorithm tailor-made for this purpose. For
practical use, we also suggest a heuristic algorithm which experimentally
demonstrate superior performance relative to baseline.

A possible line of future work can be on making the upper and lower bounds
tighter for some of the minimax rates. Other directions include proving lower
bounds for frequency estimation under Heterogeneous Local-DP. Another exciting
line of work is to possibly provide privacy to the privacy demand of the
users, i.e., solving the problem without 2.2.

## Broader Impacts

This work considers an important problem in the field of Machine Learning and
Statistics regarding privacy. Understanding heterogeneous privacy demand can
lead to more tailored privacy offerings by services, leading to better user
satisfaction. No negative consequences of this work are apparent to the
authors.

## References

  * Markowitz [1952] Harry Markowitz.  Portfolio selection.  _The Journal of Finance_ , 7(1):77–91, 1952.  ISSN 00221082, 15406261.  URL http://www.jstor.org/stable/2975974.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Batko and Ślęzak [2022] Kornelia Batko and Andrzej Ślęzak.  The use of big data analytics in healthcare.  _Journal of big Data_ , 9(1):3, 2022.
  * Yang et al. [2018] Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou, Rui Miao, Xiaoming Li, and Steve Uhlig.  Elastic sketch: Adaptive and fast network-wide measurements.  In _Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication_ , pages 561–575, 2018.
  * Saha et al. [2021] Koustuv Saha, Yozen Liu, Nicholas Vincent, Farhan Asif Chowdhury, Leonardo Neves, Neil Shah, and Maarten W Bos.  Advertiming matters: Examining user ad consumption for effective ad allocations on social media.  In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–18, 2021.
  * Dwork et al. [2006a] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual international conference on the theory and applications of cryptographic techniques_. Springer, 2006a.
  * Dwork et al. [2006b] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_. Springer, 2006b.
  * Erlingsson et al. [2014] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In _Proceedings of the 21st ACM Conference on Computer and Communications Security_ , Scottsdale, Arizona, 2014.
  * Apple [2017] Apple.  Learning with privacy at scale differential.  2017\.  URL https://api.semanticscholar.org/CorpusID:43986173.
  * Abowd [2018] John M. Abowd.  The u.s. census bureau adopts differential privacy.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. Association for Computing Machinery, 2018\.
  * Wang et al. [2020] Teng Wang, Xuefeng Zhang, Jingyu Feng, and Xinyu Yang.  A comprehensive survey on local differential privacy toward data statistics and analysis.  _Sensors_ , 2020.
  * Ackerman et al. [1999] Mark S. Ackerman, Lorrie Faith Cranor, and Joseph Reagle.  Privacy in e-commerce: examining user scenarios and privacy preferences.  In _Proceedings of the 1st ACM Conference on Electronic Commerce_ , EC ’99, page 1–8. Association for Computing Machinery, 1999.
  * Li et al. [2012] Hong Ping Li, Haibo Hu, and Jianliang Xu.  Nearby friend alert: Location anonymity in mobile geosocial networks.  _IEEE Pervasive Computing_ , 12(4):62–70, 2012\.
  * Kasiviswanathan et al. [2011] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  _SIAM Journal on Computing_ , 2011.
  * Kairouz et al. [2021] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta.  (Nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces.  In _Conference on Learning Theory_. PMLR, 2021.
  * Wang et al. [2017] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha.  Locally differentially private protocols for frequency estimation.  In _USENIX Security Symposium_ , 2017.
  * Bassily et al. [2020a] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu.  Private query release assisted by public data.  In _International Conference on Machine Learning_. PMLR, 2020a.
  * Bassily et al. [2020b] Raef Bassily, Shay Moran, and Anupama Nandi.  Learning from mixtures of private and public populations.  _Advances in Neural Information Processing Systems_ , 2020b.
  * Liu et al. [2021] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu.  Leveraging public data for practical private query release.  In _International Conference on Machine Learning_. PMLR, 2021.
  * Alon et al. [2019] Noga Alon, Raef Bassily, and Shay Moran.  Limits of private learning with access to public data.  _Advances in neural information processing systems_ , 2019.
  * Nandi and Bassily [2020] Anupama Nandi and Raef Bassily.  Privately answering classification queries in the agnostic pac model.  In _Algorithmic Learning Theory_. PMLR, 2020.
  * Amid et al. [2022] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta.  Public data-assisted mirror descent for private model training.  In _International Conference on Machine Learning_. PMLR, 2022.
  * Wang et al. [2021] Di Wang, Huangyu Zhang, Marco Gaboardi, and Jinhui Xu.  Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data.  In _Algorithmic Learning Theory_. PMLR, 2021.
  * Bie et al. [2022] Alex Bie, Gautam Kamath, and Vikrant Singhal.  Private estimation with public data.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Biswas et al. [2020] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman.  Coinpress: Practical private mean and covariance estimation.  _Advances in Neural Information Processing Systems_ , 33:14475–14485, 2020.
  * Vadhan [2017] Salil Vadhan.  The complexity of differential privacy.  _Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich_ , pages 347–450, 2017.
  * Alaggan et al. [2017] Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec.  Heterogeneous differential privacy.  _Journal of Privacy and Confidentiality_ , 2017.
  * Jorgensen et al. [2015] Zach Jorgensen, Ting Yu, and Graham Cormode.  Conservative or liberal? personalized differential privacy.  In _2015 IEEE 31St international conference on data engineering_ , 2015.
  * Ferrando et al. [2021] Cecilia Ferrando, Jennifer Gillenwater, and Alex Kulesza.  Combining public and private data.  In _NeurIPS 2021 Workshop Privacy in Machine Learning_ , 2021.
  * Fallah et al. [2022] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar.  Optimal and differentially private data acquisition: Central and local mechanisms.  _arXiv preprint arXiv:2201.03968_ , 2022.
  * Chaudhuri and Courtade [2023] Syomantak Chaudhuri and Thomas Courtade.  Mean estimation under heterogeneous privacy: Some privacy can be free.  In _2023 IEEE International Symposium on Information Theory (ISIT)_ , 2023.
  * Chaudhuri et al. [2023] Syomantak Chaudhuri, Konstantin Miagkov, and Thomas A Courtade.  Mean estimation under heterogeneous privacy demands.  _arXiv preprint arXiv:2310.13137_ , 2023.
  * Cummings et al. [2023] Rachel Cummings, Hadi Elzayn, Emmanouil Pountourakis, Vasilis Gkatzelis, and Juba Ziani.  Optimal data acquisition with privacy-aware agents.  In _2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , pages 210–224. IEEE, 2023.
  * Waudby-Smith et al. [2023] Ian Waudby-Smith, Steven Wu, and Aaditya Ramdas.  Nonparametric extensions of randomized response for private confidence sets.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 36748–36789. PMLR, 23–29 Jul 2023.
  * Canonne and Sun [2023] Clément L Canonne and Yucheng Sun.  Private distribution testing with heterogeneous constraints: Your epsilon might not be mine.  _arXiv preprint arXiv:2309.06068_ , 2023.
  * Anjarlekar et al. [2023] Ameya Anjarlekar, Rasoul Etesami, and R Srikant.  Striking a balance: An optimal mechanism design for heterogenous differentially private data acquisition for logistic regression.  _arXiv preprint arXiv:2309.10340_ , 2023.
  * Kang et al. [2023] Justin Kang, Kannan Ramchandran, and Ramtin Pedarsani.  The fair value of data under heterogeneous privacy constraints in federated learning.  In _International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023_ , 2023.
  * Acharya et al. [2024] Krishna Acharya, Franziska Boenisch, Rakshit Naidu, and Juba Ziani.  Personalized differential privacy for ridge regression.  _arXiv preprint arXiv:2401.17127_ , 2024.
  * Ghosh and Roth [2011] Arpita Ghosh and Aaron Roth.  Selling privacy at auction.  In _Proceedings of the 12th ACM conference on Electronic commerce_ , pages 199–208, 2011.
  * Diamond and Boyd [2016] Steven Diamond and Stephen Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  _Journal of Machine Learning Research_ , 2016.
  * Duchi et al. [2013] John Duchi, Michael Jordan, and Martin Wainwright.  Local privacy and minimax bounds: Sharp rates for probability estimation.  _Adv. Neural Inform. Process. Syst_ , 2013.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Kairouz et al. [2016] Peter Kairouz, Keith Bonawitz, and Daniel Ramage.  Discrete distribution estimation under local privacy.  In _International Conference on Machine Learning_ , pages 2436–2444. PMLR, 2016.
  * CA State Controller [2022] CA State Controller.  University of california salary data, 2022.  URL https://publicpay.ca.gov/Reports/RawExport.aspx.  Accessed: 2024-01-22.
  * U.S. Department of Health and Human Services et al. [2020] U.S. Department of Health and Human Services, Centers for Disease Control and Prevention, and National Cancer Institute.  U.s. cancer statistics data visualizations tool, based on 2022 submission data (1999-2020), 2020.  URL https://gis.cdc.gov/Cancer/USCS/#/AtAGlance/.  Accessed: 2024-01-22.
  * Wajc [2017] David Wajc.  Negative association: definition, properties, and applications.  2017\.
  * Chen et al. [2020] Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur.  Breaking the communication-privacy-accuracy trilemma.  _Advances in Neural Information Processing Systems_ , 33:3312–3324, 2020.
  * Kearns and Saul [2013] Michael Kearns and Lawrence Saul.  Large deviation methods for approximate probabilistic inference.  _arXiv preprint arXiv:1301.7392_ , 2013.
  * Berend and Kontorovich [2013] Daniel Berend and Aryeh Kontorovich.  On the concentration of the missing mass.  _Electronic Communications in Probability_ , 18(none):1 – 7, 2013.  doi: 10.1214/ECP.v18-2359.
  * Chan et al. [2011] T-H Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _ACM Transactions on Information and System Security (TISSEC)_ , 14(3):1–24, 2011.

##  Appendix A Mean Estimation

######  Definition A.1 (Minimax Rates of Mean Estimation).

(A) Correlated Setting: The PAC-minimax rate is given by

$\cR_{c}^{m}(\beta,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[0,1]^{n}}\min_{\bbP\\{|M(D)-\mu(D)|>\alpha\\}\leq\beta}\alpha\
,$ (17)

where the probability is taken over the randomness in the map $M$. The MSE-
minimax rate is given by

$\cE_{c}^{m}(\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[0,1]^{n}}\bbE[|M(D)-\mu(D)|^{2}]\
,$ (18)

where the expectation is taken over the randomness in the map $M$.
(B) Uncorrelated Setting: The PAC-minimax rate is given by

$\cR_{u}^{m}(\beta,\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[0,1]^{n}}\min_{\bbP\\{|M(D_{\sigma})-\mu(D)|>\alpha\\}\leq\beta}\alpha\
,$ (19)

where the probability is taken over the randomness in the map $M$ and the
uniform permutation $\sigma$ of the dataset $D$. The MSE-minimax rate is given
by

$\cE_{u}^{m}(\bm{\epsilon})=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[0,1]^{n}}\bbE[|M(D_{\sigma})-\mu(D)|^{2}]\
,$ (20)

where the expectation is taken over the randomness in the map $M$ and the
uniform permutation $\sigma$ of the dataset $D$.

The family of algorithms HPM is presented in Algorithm 2, along with the
choices of weights in Appendix A.

Algorithm 2 Heterogeneously Private Mean (HPM)

Input: weights $\vecw\in\Delta_{n}$, $X\in[0,1]^{n}$

Sample $N\sim\text{Laplace}(\|\frac{\vecw}{\bm{\epsilon}}\|_{\infty})$

return $\max\\{\min\\{N+\sum_{i=1}^{n}w_{i}X_{i},1\\},0\\}$

Table 3: Weights for Algorithm 2 for different settings.

Algorithm | Weights $\vecw$
---|---
HPM-C | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{C}(\vecw,1,\beta,\bm{\epsilon})$
HPM-C | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{C}(\vecw,e,1,\bm{\epsilon})$
HPM-U | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{U}(\vecw,1,\beta,\bm{\epsilon})$
HPM-U | $\operatornamewithlimits{arg\leavevmode\nobreak\ min}_{\vecw\in\Delta_{n}}r_{U}(\vecw,e,1,\bm{\epsilon})$
HPM-A | $\frac{1-e^{-\bm{\epsilon}}}{\lVert 1-e^{-\bm{\epsilon}}\rVert_{1}}$

##  Appendix B Experiment Details

Uniformly enforce $\epsilon_{1}$-DP (UNI): This approach offers the highest
privacy level $\epsilon_{1}$ to all the datapoints and uses the known minimax
estimator for homogeneous $\epsilon_{1}$-DP mean and frequency estimation,
depending on the problem. UNI can be arbitrarily worse than the optimal
algorithm – consider a dataset with a single high and several low privacy
datapoints444High privacy corresponds to a low value of $\epsilon$..

Proportional Weighing (Prop): This approach uses the weights
$\vecw\propto\bm{\epsilon}$. This weighing minimizes the amount of Laplace
noise required over all possible weights, but it comes at the cost of a higher
bias. In the case that $\bm{\epsilon}$ have a high variance, this weighing
strategy can perform rather poorly. For example, in the case that there is
just one user requiring no privacy ($\epsilon\to\infty$), this strategy would
disregard the data of all other users.

Sampling Mechanism (SM): This mechanism was proposed by Jorgensen et al. [28].
Let $t=\|\bm{\epsilon}\|_{\infty}$. Then sample $i$-th datapoint independently
with probability $(e^{\epsilon_{i}}-1)/(e^{t}-1)$. On the sub-sampled dataset,
we can use any homogeneous $t$-DP algorithm and this will be
$\bm{\epsilon}$-DP. A shortcoming of this mechanism is of just one user
requires no privacy, the SM algorithm disregards the rest of the dataset.

Local Differential Private Frequency (LDP): A simple Local-DP approach to
heterogeneous DP is to send the user $i$’s data to the server via an
$\epsilon_{i}$-DP channel.

  * •

Mean estimation: the LDP channels adds Laplace$(\frac{1}{\epsilon_{i}})$ noise
to the user $i$’s data.

  * •

Frequency estimation: we use $k$-RAPPOR [8, 43] to send the datapoints to the
central server, which essentially does randomized response on one-got encoding
of user data.

The exact scheme used by us for combining these estimates from different users
at the server in outlined in Appendix L. While this is not a completely fair
comparison with other algorithms since Local-DP is typically more noisy than
Central-DP, it is still insightful to see the performance difference. In fact,
our implementation of this Local-DP mechanism under heterogeneous privacy is
on par with some of the baseline Central-DP techniques for frequency
estimation.

For PAC error evaluation, we set $\beta=0.05$ for all experiments for
obtaining the weights for the PAC variants of HPF and HPM algorithms. We run
the experiments on both synthetic and real datasets. Keeping the dataset and
privacy demand fixed, several trials of the algorithms are performed for each
experiment. For the uncorrelated setting, in each trial, the dataset is
randomly permuted.

For each experiment on the PAC variants, we record the empirical
$\ell_{\infty}$ error of the algorithms for each trial and report the $95$-th
quantile error. For each experiment on the MSE variant, we report the mean
squared $l_{\infty}$-error.

###  B.1 Frequency Estimation under Correlated Setting

For the correlated setting, we sub-sample the University of California (UC)
salary data for 2022 [44] consisting of the salaries of 50K employees in the
UC system. We partition the salaries into 12 bins and assign less privacy
demand to the people in the more central bins. In particular, a user that
belongs to bin $i$ has a privacy demand randomly sampled as
$\log\epsilon\sim-|i-6.5|+$ Uniform$[-3,3]$. We sample the privacy demands
once and keep it fixed, while running several trials. Results of the
experiments are outlined in Table 4. Our proposed algorithms HPF-C and HPF-C
outperforms the other algorithms, while HPF-A also performs competitively. The
empirical error distributions are plotted in Figure 1(a) to illustrate the
performance of different algorithms. The Prop algorithm exhibits a steep curve
since this method adds the minimum amount of Laplace noise, at the cost of
higher bias.

We also consider two synthetic datasets with $n=10000$; the number of bins $k$
is set as $5$ and $20$. The privacy demand is randomly sampled, with different
distributions for users in different bins. UNI performs poorly since it adds
significantly more noise, but LDP’s performance is impressive since Local-DP
typically performs significantly worse than Central-DP. In Table 4, in the
synthetic datasets, HPF-A outperforms HPF-C and HPF-C.

###  B.2 Frequency Estimation under Uncorrelated Setting

For uncorrelated setting, we consider the number of new cancers in the state
of Colorado in 2020 [45] containing data of about 17K surgeries with ten
different types of cancers. We sample $\log\bm{\epsilon}\sim$Uniform$[-5,5]$
and keep $\bm{\epsilon}$ fixed. For each trial, the dataset, mapping each user
to a type of cancer surgery, is randomly permuted. We perform $O(n\log n)$
trials to get meaningful results due to the random permutations. The plot for
empirical cdf of the errors is shown in Figure 1(b). Our proposed algorithms
HPF-A, HPF-U, and HPF-U perform better than the other baseline algorithms.

In a similar manner as the correlated setting, we also test the algorithms
under synthetic datasets. From Table 4, it can be seen that while HPF-A
performs superior to the other algorithms, HPF-U and HPF-U also enjoy good
performance.

Table 4: We present the performance of various algorithms under different datasets and settings. The first column specifies the dataset, whether it is the correlated or the uncorrelated setting, and whether the reported numbers are empirical 95-th quantile error ($\bbP$) or mean squared error ($\bbE$) under $\ell_{\infty}$ norm. Datasets of form $(n,k)$ are synthetic datasets with $n$ users and $k$ bins. The variant of the HPF algorithm used is given by the regime and error metric for the dataset listed in the first column. Dataset, Regime, Error Metric | HPF | HPF-A | Prop | UNI | SM | LDP
---|---|---|---|---|---|---
UC Salary, C, $\bbP$ | 0.118 | 0.174 | 0.273 | 1.000 | 0.459 | 0.420
UC Salary, C, $\bbE$ | 0.011 | 0.030 | 0.074 | 0.396 | 0.180 | 0.087
(10000, 5), C, $\bbP$ | 0.105 | 0.083 | 0.202 | 1.000 | 0.924 | 0.253
(10000, 5), C, $\bbE$ | 0.012 | 0.007 | 0.041 | 0.834 | 0.779 | 0.027
(10000, 20), C, $\bbP$ | 0.020 | 0.003 | 0.090 | 0.233 | 1.000 | 0.125
(10000, 20), C, $\bbE$ |  3$\times 10^{-4}$ | 7$\times 10^{-6}$ | 0.008 | 0.022 | 0.779 | 0.008
Cancer Types, U, $\bbP$ | 0.009 | 0.005 | 0.014 | 0.091 | 0.382 | 0.012
Cancer Types, U, $\bbE$ |  5$\times 10^{-5}$ | 1$\times 10^{-5}$ |  8$\times 10^{-5}$ | 0.003 | 0.036 |  7$\times 10^{-5}$
(10000, 5), U, $\bbP$ | 0.012 | 0.008 | 0.023 | 0.370 | 0.798 | 0.0152
(10000, 5), U, $\bbE$ |  1$\times 10^{-4}$ | 3$\times 10^{-5}$ |  2$\times 10^{-4}$ | 0.043 | 0.198 |  1$\times 10^{-4}$
(10000, 20), U, $\bbP$ | 0.013 | 0.007 | 0.020 | 0.482 | 0.348 | 0.015
(10000, 20), U, $\bbE$ |  1$\times 10^{-4}$ | 2$\times 10^{-5}$ |  2$\times 10^{-4}$ | 0.095 | 0.028 |  1$\times 10^{-4}$

###  B.3 Mean Estimation under Correlated Setting:

For the correlated setting, we consider the UC Dataset and use the the method
described in frequency estimation to get a correlated data and privacy demand.
Results of the experiments are outlined in Table 5. We also consider a
synthetic datasets with $n=10000$ and use a method similar to the frequency
estimation experiments to obtain correlated data and privacy demand.

###  B.4 Mean Estimation under Uncorrelated Setting:

For uncorrelated setting, we test the algorithms under a synthetic dataset.
Overall, HPM-A performs superior as comapred to the other algorithms.

Table 5: We present the performance of various algorithms under different datasets and settings. The first column specifies the dataset, whether it is the correlated or the uncorrelated setting, and whether the reported numbers are empirical 95-th quantile error ($\bbP$) or mean squared error ($\bbE$) under $\ell_{\infty}$ norm. The variant of the HPM algorithm used is given by the regime and error metric for the dataset listed in the first column. Dataset, Regime, Error Metric | HPM | HPM-A | Prop | UNI | SM | LDP
---|---|---|---|---|---|---
UC Salary, C, $\bbP$ | 0.064 | 0.005 | 0.005 | 0.066 | 0.005 | 1.000
UC Salary, C, $\bbE$ | 2$\times 10^{-5}$ | 2$\times 10^{-5}$ | 2$\times 10^{-5}$ | 0.001 | 2$\times 10^{-5}$ | 0.832
10000, C, $\bbP$ | 0.008 | 0.009 | 0.009 | 0.027 | 0.052 | 0.085
10000, C, $\bbE$ |  4$\times 10^{-5}$ |  7$\times 10^{-5}$ |  8$\times 10^{-4}$ |  2$\times 10^{-4}$ | 2$\times 10^{-5}$ | 0.002
10000, U, $\bbP$ | 0.008 | 0.001 | 0.004 | 0.027 | 0.110 | 0.086
10000, U, $\bbE$ |  4$\times 10^{-5}$ | 3$\times 10^{-7}$ |  5$\times 10^{-6}$ |  1$\times 10^{-4}$ | 0.003 | 0.002

##  Appendix C Upper and Lower Bounds

###  C.1 Upper Bounds

Recall the functions $r_{C}$ and $r_{U}$ from (6) and (7) respectively. We
denote their corresponding minimum values by

$R_{C}(k,\beta,\bm{\epsilon})=\left(\min_{\vecw\in\Delta_{n}}r_{C}(\vecw,k,\beta,\bm{\epsilon})\right)\wedge
1,$ (21)

and

$R_{U}(k,\beta,\bm{\epsilon})=\left(\min_{\vecw\in\Delta_{n}}r_{U}(\vecw,k,\beta,\bm{\epsilon})\right)\wedge
1.$ (22)

These functions are relevant for expressing the PAC and MSE errors for either
problems in either settings.

For a choice of weights $\vecw\in\Delta_{n}$ in Algorithm 1 or Algorithm 2,
the term $\lVert\vecw-\bm{1}/n\rVert_{1}$ in $r_{C}$ and $r_{U}$ are errors
due to having weights different from $\bm{1}/n$. The
$\|\frac{\vecw}{\bm{\epsilon}}\|_{\infty}$ term accounts for noise needed to
satisfy the privacy demand. The algorithms minimizing their respective errors
over the choices of weights $\vecw$.

Theorem C.1 provides upper bounds for the PAC-minimax rates in the two
settings and the two problems; its proof can be found in Appendix E.

######  Theorem C.1 (PAC Upper Bounds).

.
(A) Correlated Setting: For frequency estimation

$\cR_{c}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{C}(k,\beta,\bm{\epsilon}),$
(23)

and for mean estimation

$\cR_{c}^{m}(\beta,\bm{\epsilon})\lesssim R_{C}(1,\beta,\bm{\epsilon}).$ (24)

(B) Uncorrelated Setting: For frequency estimation

$\cR_{u}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{U}(k,\beta,\bm{\epsilon}),$
(25)

and for mean estimation

$\cR_{u}^{m}(\beta,\bm{\epsilon})\lesssim R_{U}(1,\beta,\bm{\epsilon}).$ (26)

Since we are considering PAC error under $\ell_{\infty}$-norm for frequency
estimation, the $\log(k/\beta)$ captures the effect of union bound. Simply
substituting $k=1$ recovers the guarantee for mean estimation.

Theorem C.2 provides an upper bound on the MSE-minimax rates for the two
settings for both frequency and mean estimation, its proof can be found in
Appendix F.

######  Theorem C.2 (MSE Upper Bounds).

.
(A) Correlated Setting: For frequency estimation

$\cE_{c}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{C}(k,1,\bm{\epsilon})^{2},$
(27)

and for mean estimation

$\cE_{c}^{m}(\beta,\bm{\epsilon})\lesssim R_{C}(e,1,\bm{\epsilon})^{2}.$ (28)

(B) Uncorrelated Setting: For frequency estimation

$\cE_{u}^{f}(k,\bm{\epsilon})\lesssim R_{U}(k,1,\bm{\epsilon})^{2},$ (29)

and for mean estimation

$\cE_{u}^{m}(\bm{\epsilon})\lesssim R_{U}(e,1,\bm{\epsilon})^{2}.$ (30)

We mention that for frequency estimation in Theorem C.2, the MSE upper bound
has $\log(k)$ term instead of $\log(k/\beta)$ so we just set $\beta=1$ in
$R_{C}$ and $R_{U}$ for brevity. Similarly, for mean estimation, there is no
$\log(k/\beta)$ term in our upper bounds; hence, we substitute the constant
$\beta\leftarrow 1,k\leftarrow e$ in the $R_{C}$ and $R_{U}$ functions for
brevity. We also assume $k\geq 2$ for frequency estimation to make
simplifications like $\log(2k)\lesssim\log(k)$ in the proof. Theorem C.2 is
obtained by some concentration inequalities and the tail-sum identity for
expectation, using the PAC bounds in Theorem C.1.

As one would expect, the upper bounds in the correlated setting is always
greater than the corresponding one in uncorrelated setting – in both mean and
frequency estimation under both PAC and MSE bounds.

For comparison, in frequency estimation, consider the straw-man approach of
assigning every user equal weight555This is the UNI algorithm defined in
Section 4. and adding i.i.d. Laplace$(\frac{2}{n\epsilon_{1}})$ noise to each
bin., leading to the PAC-error of the order
$\frac{\log(k/\beta)}{n\epsilon_{1}}$ and MSE-error of the order
$\frac{\log(k)^{2}}{n^{2}\epsilon_{1}^{2}}$ (in both settings). This method
has a clear drawback in case there is one user demanding an extremely high
privacy ($\epsilon_{1}\to 0$) and the rest of the users requiring no privacy.
It is simply better to ignore the first user and do non-private frequency
calculation for the rest of the users; in correlated setting, this leads to a
PAC-error of at most $\frac{1}{n}$ from Theorem C.1, and MSE-error of
$\frac{1}{n^{2}}$ from Theorem C.2. In the uncorrelated setting, it leads to
PAC-error of at most $\sqrt{\frac{\log(k/\beta)}{n}}\wedge\frac{1}{n}$ and
MSE-error of $\frac{1}{n}$. A similar case can be made for mean estimation.

###  C.2 Lower Bounds

For frequency estimation, the trivial output of $\bm{1}/2$ achieves an
$\ell_{\infty}$ error of $\frac{1}{2}$. Therefore, we have
$\cR_{c}^{f}(k,\beta,\bm{\epsilon}),\cR_{u}^{f}(k,\beta,\bm{\epsilon})\leq\frac{1}{2}$.
Similarly, for mean estimation we have
$\cR_{c}^{m}(\beta,\bm{\epsilon}),\cR_{u}^{m}(\beta,\bm{\epsilon})\leq\frac{1}{2}$.

Our lower bounds for PAC rates follow from a packing argument and are
presented in Theorem C.3. We remind the readers that $\bm{\epsilon}$ is
assumed to be in non-decreasing order.

When the minimax rates are strictly less than half, we show that the minimax
rate must satisfy the conditions in Theorem C.3. The proof can be found in
Appendix G.

######  Theorem C.3 (Implicit PAC Lower Bounds).

.
We have
$\cR_{c}^{f}(k,\beta,\bm{\epsilon}),\cR_{u}^{f}(k,\beta,\bm{\epsilon}),\cR_{c}^{m}(\beta,\bm{\epsilon}),\cR_{u}^{m}(\beta,\bm{\epsilon})\leq\frac{1}{2}$.
(A) Correlated Setting: if $\cR_{c}^{f}(k,\beta,\bm{\epsilon})<\frac{1}{2}$,
then it also satisfies

$\sum_{i=1}^{\lceil
2n\cR_{c}^{f}(k,\beta,\bm{\epsilon})\rceil}\epsilon_{i}\gtrsim\log\left(\frac{k(1-\beta)}{\beta}\right).$
(31)

Similarly, if $\cR_{c}^{m}(\beta,\bm{\epsilon})<\frac{1}{2}$, then it also
satisfies

$\sum_{i=1}^{\lceil
2n\cR_{c}^{m}(\beta,\bm{\epsilon})\rceil}\epsilon_{i}\gtrsim\log\left(\frac{(1-\beta)}{\beta}\right).$
(32)

(B) Uncorrelated Setting:
Let $\\{Z_{i}\\}_{i=1}^{n}$ be sampled without replacement from the entries of
$\bm{\epsilon}$. If $\cR_{u}^{f}(k,\beta,\bm{\epsilon})<\frac{1}{2}$, then it
also satisfies

$\displaystyle\bbE\left[\exp\left\\{-\sum_{i=1}^{\lceil
2n\cR_{u}^{f}(k,\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\leq\frac{k\beta}{k-1},$ (33)
$\displaystyle\bbE\left[\exp\left\\{\sum_{i=1}^{\lceil
2n\cR_{u}^{f}(k,\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\geq k(1-\beta).$ (34)

Similarly, if $\cR_{u}^{m}(\beta,\bm{\epsilon})<\frac{1}{2}$, then it also
satisfies

$\displaystyle\bbE\left[\exp\left\\{-\sum_{i=1}^{\lceil
2n\cR_{u}^{m}(\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\leq\beta,$ (35)
$\displaystyle\bbE\left[\exp\left\\{\sum_{i=1}^{\lceil
2n\cR_{u}^{m}(\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\geq(1-\beta).$ (36)

While the conditions presented in Theorem C.3 are implicit, it should be noted
that the conditions imply a lower limit to the minimax rates.

We also present MSE lower bounds in the uncorrelated setting in Theorem C.4.
In order to present the lower bound, we define another minimax rate closely
related to the problem. For some set $S$, let $\cP(S)$ denote the set of
probability distributions on $S$. Similar to the MSE-minimax rates, we define
the minimax rate for mean estimation under $\bm{\epsilon}$-DP from i.i.d. data
as

$\cE_{stat}(\bm{\epsilon})=\min_{M\in
M_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\bbE_{X_{1},\ldots,X_{n}\sim
P}[|M(X^{n})-\mu(P)|^{2}].$ (37)

######  Theorem C.4 (MSE Lower Bounds).

.
We have
$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})\leq\frac{1}{4}$. Both
$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})$ satisfy

$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})\geq\left(\sqrt{\cE_{stat}(\bm{\epsilon})}-\sqrt{\frac{1}{4n}}\right)_{+}^{2}.$
(38)

In Theorem C.4, we use the notation $(x)_{+}$ to refer to the function
$\max\\{x,0\\}$. We interpret this lower bound in Section 5.2 and compare it
with the upper bound. We mention that we do not present any lower bounds for
the MSE-minimax rates $\cE^{f}_{c}$ and $\cE^{m}_{c}$.

##  Appendix D  Proof of Lemma 3.1

######  Lemma (3.1).

The proposed family of algorithms HPF and HPM satisfy the $\bm{\epsilon}$-DP
constraint defined in Definition 2.1.

###### Proof.

We present the proof for frequency estimation (HPF); similar steps can be used
to show $\bm{\epsilon}$-DP property for HPM. In this proof, we use the
notation $\theta_{\vecw}(X)\in\Delta_{k}$ to denote the vector where
$\theta_{\vecw}(X)_{i}=\sum_{j}w_{j}\mathbb{I}\\{X_{j}=i\\}$. Note that the
algorithms compute $\theta_{\vecw}(X)$ and adds i.i.d.
Laplace($2\lVert\vecw/\bm{\epsilon}\rVert_{\infty}$) noise in each component.
We have

$\displaystyle\frac{p\\{M(X)=\veca\\}}{p\\{M(X^{\prime i})=\veca\\}}$
$\displaystyle=\prod_{j=1}^{k}\exp\left(\frac{|\theta_{\vecw}(X)_{j}-a_{j}|-|\theta_{\vecw}(X^{\prime
i})_{j}-a_{j}|}{2\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}\right)$ (39)
$\displaystyle\leq\exp\left(\sum_{j=1}^{k}\frac{|\theta_{\vecw}(X)_{j}-\theta_{\vecw}(X^{\prime
i})_{j}|}{2\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}\right)$ (40)
$\displaystyle\leq\exp{\frac{w_{i}}{\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}}\leq\exp\epsilon_{i},$
(41)

where we used $\sum_{j}|\theta_{\vecw}(X)_{j}-\theta_{\vecw}(X^{\prime
i})_{j}|\leq 2w_{i}$ since $X^{\prime i}$ differs from $X$ only in the $i$-th
coordinate. ∎

##  Appendix E  Proof of Theorem C.1

######  Theorem (C.1).

.
(A) Correlated Setting: For frequency estimation

$\cR_{c}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{C}(k,\beta,\bm{\epsilon}),$
(42)

and for mean estimation

$\cR_{c}^{m}(\beta,\bm{\epsilon})\lesssim R_{C}(1,\beta,\bm{\epsilon}).$ (43)

(B) Uncorrelated Setting: For frequency estimation

$\cR_{u}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{U}(k,\beta,\bm{\epsilon}),$
(44)

and for mean estimation

$\cR_{u}^{m}(\beta,\bm{\epsilon})\lesssim R_{U}(1,\beta,\bm{\epsilon}).$ (45)

###### Proof.

(A) We consider frequency estimation. Substituting $k=1$ recovers the
guarantees for mean estimation.

Suppose that with probability greater than $1-\beta$, the algorithm is within
$\alpha$ of the true frequency. Let $Q\in\\{0,1\\}^{k\times n}$ such that
$Q(i,j)=\mathbb{I}\\{D_{j}=i\\}$. Further, let $\vecN=(N_{1},\ldots,N_{k})$
where the components are i.i.d.
$\text{Laplace}(2\|\frac{\vecw^{*}}{\bm{\epsilon}}\|_{\infty})$. Then we have,

$\displaystyle\mathbb{P}\\{\lVert
Q\vecw+\vecN-\mu(D)\rVert_{\infty}>\alpha\\}$
$\displaystyle=\mathbb{P}\\{\lVert
Q(\vecw-\bm{1}/n)+\vecN\rVert_{\infty}>\alpha\\}$ (46)
$\displaystyle\leq\mathbb{P}\\{\lVert
Q(\vecw-\bm{1}/n)\rVert_{\infty}>\alpha/2\\}+\mathbb{P}\\{\lVert\vecN\rVert_{\infty}>\alpha/2\\}$
(47)
$\displaystyle\leq\mathbb{I}\\{\alpha/2\leq\|\vecw-\bm{1}/n\|_{\mathsf{TV}}\\}+k\exp(-\frac{\alpha}{4\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}),$
(48)

where we used the fact that $\lVert
Q(\vecw-\bm{1}/n)\rVert_{\infty}\leq\|\vecw-\bm{1}/n\|_{\mathsf{TV}}$. To see
this, note that the $a$-th component of $Q(\vecw-\bm{1}/n)$ is given by
$\sum_{i}Q(a,i)(w_{i}-\frac{1}{n})$, which is less than
$\|\vecw-\bm{1}/n\|_{\mathsf{TV}}$ almost surely by straightforward definition
of TV-distance. The second term is obtained by union bound on laplace tail
probabilities.

To get a condition on $\alpha$, it is sufficient to upper bound the first term
by $0$ and second term by $\beta$ in (48). Thus, since $\alpha$ satisfies both
conditions, we have
$\alpha^{2}\gtrsim\max\\{\lVert\vecw-\bm{1}/n\rVert_{1}^{2},\log^{2}(k/\beta)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}\\}\simeq\lVert\vecw-\bm{1}/n\rVert_{1}^{2}+\log^{2}(k/\beta)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}$.
Taking minimum over $\alpha$ satisfying the $(1-\beta)$ quantile condition in
the definition of PAC minimax rate implies
$\alpha^{2}\simeq\lVert\vecw-\bm{1}/n\rVert_{1}^{2}+\log^{2}(k/\beta)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}$.

Optimizing over the weights $\vecw$ and due to the projection to $[0,1]$ in
the algorithm, we have $\cR_{c}^{f}\lesssim R_{C}(k,\beta,\bm{\epsilon})$.

(B) We consider frequency estimation. Substituting $k=1$ recovers the
guarantees for mean estimation. Let $Q_{\sigma}\in\\{0,1\\}^{k\times n}$ such
that $Q_{\sigma}(i,j)=\mathbb{I}\\{D_{\sigma(j)}=i\\}$. Thus, we have

$\displaystyle\mathbb{P}\\{\lVert
Q_{\sigma}\vecw+\vecN-\mu(D)\rVert_{\infty}>\alpha\\}$
$\displaystyle=\mathbb{P}\\{\lVert
Q_{\sigma}(\vecw-\bm{1}/n)+\vecN\rVert_{\infty}>\alpha\\}$ (49)
$\displaystyle\leq\mathbb{P}\\{\lVert
Q_{\sigma}(\vecw-\bm{1}/n)\rVert_{\infty}>\alpha/2\\}+\mathbb{P}\\{\lVert\vecN\rVert_{\infty}>\alpha/2\\}$
(50)

We focus on the $\mathbb{P}\\{\lVert
Q_{\sigma}(\vecw-\bm{1}/n)\rVert_{\infty}>\alpha/2\\}$ term. By previous part,
it can be at most $\|\vecw-\bm{1}/n\|_{\mathsf{TV}}$ (almost surely). However,
we also have another bound using the fact that the data is uniformly permuted.
We shall now prove

$\mathbb{P}\\{|\sum_{i}Q_{\sigma}(a,i)(w_{i}-\frac{1}{n})|>\alpha/2\\}\leq
2\exp\left(-\frac{\alpha^{2}}{2\lVert\vecw\rVert_{2}^{2}}\right).$ (51)

Since we restrict our attention to the $a$-th component in (51), we shall
denote the vector $Q_{\sigma}(a,\cdot)$ by $\vecz_{\sigma}\in\\{0,1\\}^{n}$.
We start by noting

$\displaystyle\sum_{i}(w_{i}-\frac{1}{n})z_{\sigma(i)}$
$\displaystyle=\sum_{i}(w_{i}-\frac{1}{n})(z_{\sigma(i)}-c)\ \text{ for any
constant $c$}$ (52)
$\displaystyle=\sum_{i}(w_{i}-\frac{1}{n})(z_{\sigma(i)}-\mu)\ \text{by
setting $c=\mu=\sum_{i}\vecz_{i}/n$}$ (53)
$\displaystyle=\sum_{i}w_{i}(z_{\sigma(i)}-\mu).$ (54)

Define the random variables $Y_{1},\ldots,Y_{n}$ sampled without replacement
from $\vecz-\mu\bm{1}$. Note that the $Y$(s) are ‘permutation’ random
variables and they are zero-mean. Thus, they satisfy Negative Association and
we have,

$\displaystyle\mathbb{P}\\{\sum_{i}w_{i}Y_{i}>t\\}$
$\displaystyle=\mathbb{P}\\{\exp(\lambda\sum_{i}w_{i}Y_{i})>\exp(\lambda
t)\\}$ (55) $\displaystyle\leq\frac{\bbE[\prod_{i}\exp(\lambda
w_{i}Y_{i})]}{e^{\lambda t}}$ (56)
$\displaystyle\leq\frac{\prod_{i}\bbE[\exp(\lambda w_{i}Y_{i})]}{e^{\lambda
t}}$ (57)
$\displaystyle\leq\frac{\exp(\lambda^{2}\lVert\vecw\rVert_{2}^{2}/8)}{e^{\lambda
t}}$ (58) $\displaystyle\leq\exp(-2t^{2}/\lVert\vecw\rVert_{2}^{2}).$ (59)

In (57) we used Negative association and the fact that each function is
increasing in $Y$ since $w_{i}\geq 0$ (see Corollary 4 and Lemma 8 from Wajc
[46]). Thus, we proved (51). Overall, we have

$\displaystyle\mathbb{P}\\{\lVert
Q_{\sigma}\vecw+\vecN-\mu(D)\rVert_{\infty}>\alpha\\}$ $\displaystyle\leq
2k\mathbb{I}\\{\alpha\leq\lVert\vecw-\bm{1}/n\rVert_{1}\\}\exp\left(-\frac{\alpha^{2}}{2\lVert\vecw\rVert_{2}^{2}}\right)+k\exp{\left(-\frac{\alpha}{4\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}\right)},$
(60)

where (60) results from the fact that maximum error is the TV-distance
established in (48). We can upper bound each term by $\beta/2$ to get the
condition that

$\displaystyle\alpha^{2}$
$\displaystyle\gtrsim\max\\{\min\\{\lVert\vecw-\bm{1}/n\rVert_{1}^{2},\log(k/\beta)\lVert\vecw\rVert_{2}^{2}\\},\log^{2}(k/\beta)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}\\}$
(61)
$\displaystyle\simeq\min\\{\lVert\vecw-\bm{1}/n\rVert_{1}^{2},\log(k/\beta)\lVert\vecw\rVert_{2}^{2}\\}+\log^{2}(k/\beta)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}.$
(62)

Taking minimum over such $\alpha$, optimizing over the weights $\vecw$, and
due to the projection to $[0,1]$ in the algorithm, we have
$\cR_{u}^{f}\lesssim R_{U}(k,\beta,\bm{\epsilon})$.

Interesting Note: In (60), we used union bound and (51), which finally results
in (62). In particular, there is a $\log(k/\beta)$ coefficient to the
$\lVert\vecw\rVert_{2}^{2}$ term. This is might be intuitive as the $\log(k)$
term results from union bound over the $k$ coordinates. However, this method
completely disregards that the matrix $Q$ has only one-hot vectors and one can
leverage this structure to get tighter inequalities. In particular, using the
Kearns-Saul inequality, one can get a coefficient of the order
$1+\frac{\log(1/\beta)}{\log k}$. Thus, the effect of $k$ is now opposite – a
higher $k$ results in a smaller coefficient! ∎

##  Appendix F Proof of Theorem C.2

######  Theorem (C.2).

.
(A) Correlated Setting: For frequency estimation

$\cE_{c}^{f}(k,\beta,\bm{\epsilon})\lesssim R_{C}(k,1,\bm{\epsilon})^{2},$
(63)

and for mean estimation

$\cE_{c}^{m}(\beta,\bm{\epsilon})\lesssim R_{C}(e,1,\bm{\epsilon})^{2}.$ (64)

(B) Uncorrelated Setting: For frequency estimation

$\cE_{u}^{f}(k,\bm{\epsilon})\lesssim R_{U}(k,1,\bm{\epsilon})^{2},$ (65)

and for mean estimation

$\cE_{u}^{m}(\bm{\epsilon})\lesssim R_{U}(e,1,\bm{\epsilon})^{2}.$ (66)

###### Proof.

We shall reuse parts of the proof of Theorem C.1 in Appendix E. We present the
proof for frequency estimation, similar steps can be used for mean estimation.

(A) Begin by noting that

$\displaystyle\bbE[\lVert Q\vecw+\vecN-\mu(D)\rVert_{\infty}^{2}]$
$\displaystyle=\bbE[\lVert Q(\vecw-\bm{1}/n)+\vecN\rVert_{\infty}^{2}]$ (67)
$\displaystyle\leq\bbE[\lVert
Q(\vecw-\bm{1}/n)\rVert_{\infty}^{2}]+\bbE[\lVert\vecN\rVert_{\infty}^{2}].$
(68)

From (48), recall

$\mathbb{P}\\{\lVert
Q(\vecw-\bm{1}/n)\rVert_{\infty}>\alpha/2\\}\leq\mathbb{I}\\{\alpha/2\leq\|\vecw-\bm{1}/n\|_{\mathsf{TV}}\\}.$
(69)

Therefore, using the above and tail-sum form of expectation, we get

$\bbE[\lVert
Q(\vecw-\bm{1}/n)\rVert_{\infty}^{2}]\lesssim\lVert\vecw-\bm{1}/n\rVert_{1}^{2}.$
(70)

Using Lemma F.1 (it can be applied since squared magnitudes of Laplace
distribution is equivalent to squared of exponential distribution), we get

$\bbE[\lVert\vecN\rVert_{\infty}^{2}]\lesssim\log^{2}(k)\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}.$
(71)

Combining (70) and (71), we get the result. Note that for mean estimation,
$k=1$, one needs to use (76) instead of the result in Lemma F.1 which assumes
$k\geq 2$.

(B) In the uncorrelated setting, we shall use the results of part (a) along
with another inequality that we shall prove. Begin by noting that

$\displaystyle\bbE[\lVert Q_{\sigma}\vecw+\vecN-\mu(D)\rVert_{\infty}^{2}]$
$\displaystyle=\bbE[\lVert
Q_{\sigma}(\vecw-\bm{1}/n)+\vecN\rVert_{\infty}^{2}]$ (72)
$\displaystyle\leq\bbE[\lVert
Q_{\sigma}(\vecw-\bm{1}/n)\rVert_{\infty}^{2}]+\bbE[\lVert\vecN\rVert_{\infty}^{2}].$
(73)

(70) already gives us a bound on $\bbE[\lVert
Q_{\sigma}(\vecw-\bm{1}/n)\rVert_{\infty}^{2}]$ but we shall also derive an
alternate bound. From (51), we know that each element of the vector $\lVert
Q_{\sigma}(\vecw-\bm{1}/n)\rVert_{\infty}^{2}$ behaves like a sub-exponential
random variable. In particular, let
$Y_{i}=|\sum_{j}Q_{\sigma}(i,j)(w_{j}-1/n)|^{2}\geq 0$. Then, from (51), we
have

$\mathbb{P}\\{Y_{i}\geq t\\}\leq
2\exp\left(-\frac{2t}{\lVert\vecw\rVert_{2}^{2}}\right).$

Using Lemma F.2, we have

$\bbE[\max_{i}Y_{i}]\lesssim\log(k)\lVert\vecw\rVert_{2}^{2},$

completing the proof. Note that for mean estimation, $k=1$, one can not use
the fact $\log(2k)\lesssim\log(k)$ used above. ∎

######  Lemma F.1.

Let $k\geq 2$ and $N_{1},\ldots,N_{k}$ be i.i.d. $\text{Exp}(\lambda)$ random
variables. Then
$E[\max_{i=1}^{k}N_{i}^{2}]\simeq\frac{\log^{2}(k)}{\lambda^{2}}$.

###### Proof.

Note that $\max_{i=1}^{k}N_{i}$ can be written as $\sum_{i=1}^{k}Y_{i}$ where
$Y_{i}$ is $\text{Exp}((k-i+1)\lambda)$ and independent of other $Y$s. Thus,

$\displaystyle E[\max_{i=1}^{k}N_{i}^{2}]$
$\displaystyle=\mathsf{Var}(\sum_{i}Y_{i})+E[\sum_{i}Y_{i}]^{2}$ (74)
$\displaystyle=\frac{1}{\lambda^{2}}\left(\sum_{i}1/i^{2}+(\sum_{i}1/i)^{2}\right)$
(75) $\displaystyle\simeq\frac{1}{\lambda^{2}}\left(1+\log^{2}(k)\right)$ (76)
$\displaystyle\simeq\frac{\log^{2}k}{\lambda^{2}}.$ (77)

∎

######  Lemma F.2.

Let $Y_{1},\ldots,Y_{k}$ non-negative be sub-exponential random variables
satisfying $\mathbb{P}\\{Y_{i}\geq t\\}\leq c_{1}\exp(-c_{2}t)\ \ \forall
t>0$, not necessarily independent. Then,
$E[\max_{i=1}^{k}Y_{i}]\leq\frac{(c_{1}+1)\log(2k)}{c_{2}}$.

###### Proof.

Similar to the standard technqiue for proving upper bound on maximum of sub-
gaussians, for $\lambda>0$, we have

$\displaystyle e^{\lambda\bbE[\max_{i=1}^{k}Y_{i}]}$
$\displaystyle\leq\bbE[e^{\lambda\max_{i=1}^{k}Y_{i}}]$ (78)
$\displaystyle\leq\bbE[\sum_{i}e^{\lambda Y_{i}}]$ (79)
$\displaystyle=k\int_{0}^{\infty}\mathbb{P}\\{e^{\lambda Y}>t\\}dt$ (80)
$\displaystyle\leq
k\left(1+\int_{1}^{\infty}\mathbb{P}\\{Y>\log(t)/\lambda\\}dt\right)$ (81)
$\displaystyle\leq
k\left(1+c_{1}\int_{0}^{\infty}\exp(-c_{2}\log(t)/\lambda)dt\right)$ (82)
$\displaystyle=k+\frac{kc_{1}}{c_{2}/\lambda-1}\,\,\text{ for
$\lambda<c_{2}$}$ (83)

Plugging in $\lambda=c_{2}/(c_{1}+1)$ gives the desired result. ∎

##  Appendix G Proof of Theorem C.3

######  Theorem (C.3).

We have
$\cR_{c}^{f}(k,\beta,\bm{\epsilon}),\cR_{u}^{f}(k,\beta,\bm{\epsilon}),\cR_{c}^{m}(\beta,\bm{\epsilon}),\cR_{u}^{m}(\beta,\bm{\epsilon})\leq\frac{1}{2}$.
(A) Correlated Setting: if $\cR_{c}^{f}(k,\beta,\bm{\epsilon})<\frac{1}{2}$,
then it also satisfies

$\sum_{i=1}^{\lceil
2n\cR_{c}^{f}(k,\beta,\bm{\epsilon})\rceil}\epsilon_{i}\gtrsim\log\left(\frac{k(1-\beta)}{\beta}\right).$
(84)

Similarly, if $\cR_{c}^{m}(\beta,\bm{\epsilon})<\frac{1}{2}$, then it also
satisfies

$\sum_{i=1}^{\lceil
2n\cR_{c}^{m}(\beta,\bm{\epsilon})\rceil}\epsilon_{i}\gtrsim\log\left(\frac{(1-\beta)}{\beta}\right).$
(85)

(B) Uncorrelated Setting:
Let $\\{Z_{i}\\}_{i=1}^{n}$ be sampled without replacement from the entries of
$\bm{\epsilon}$. If $\cR_{u}^{f}(k,\beta,\bm{\epsilon})<\frac{1}{2}$, then it
also satisfies

$\displaystyle\bbE\left[\exp\left\\{-\sum_{i=1}^{\lceil
2n\cR_{u}^{f}(k,\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\leq\frac{k\beta}{k-1},$ (86)
$\displaystyle\bbE\left[\exp\left\\{\sum_{i=1}^{\lceil
2n\cR_{u}^{f}(k,\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\geq k(1-\beta).$ (87)

Similarly, if $\cR_{u}^{m}(\beta,\bm{\epsilon})<\frac{1}{2}$, then it also
satisfies

$\displaystyle\bbE\left[\exp\left\\{-\sum_{i=1}^{\lceil
2n\cR_{u}^{m}(\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\leq\beta,$ (88)
$\displaystyle\bbE\left[\exp\left\\{\sum_{i=1}^{\lceil
2n\cR_{u}^{m}(\beta,\bm{\epsilon})\rceil}Z_{i}\right\\}\right]$
$\displaystyle\geq(1-\beta).$ (89)

###### Proof.

$\cR_{c}^{f},\cR_{c}^{m},\cR_{u}^{f}$ and $\cR_{u}^{m}$ are less than equal to
half is trivial since the estimate of $\bm{1}/2$ or $1/2$ achieves error at
most half. We only illustrate the proof technique for frequency estimation.
Similar steps can be used for mean estimation.

The proof technique adapts the homogeneous DP packing lower bounds (for
example, see Vadhan [26]) to our setting. Let $M(\cdot)$ be an
$\bm{\epsilon}$-DP randomized algorithm that is within $\alpha<\frac{1}{2}$ of
$\mu(D)$, in $l_{\infty}$ norm, with probability greater than $1-\beta$ for
any dataset $D$.
Define $k$ different datasets $D^{i}$ for $i\in[k]$ in the following way:
$\mu(D^{i})=(1-t)\vece_{1}+t\vece_{i}$, where $e_{j}$ is the $j$-th standard
basis vector in $\bbR^{k}$. Without loss of generality, we assume the first
$nt$ indexes in $D^{i}$ are the ones with value in bin $i$. Let
$B_{\alpha}(D^{i})$ be the $l_{\infty}$-ball of radius $\alpha$ centered at
$\mu(D^{i})$. Setting $t=\frac{\lceil 2\alpha n\rceil}{n}$, observe that
$B_{\alpha}(D^{i})$ are disjoint666Note the slightly modified definition of
ceiling function that we use which ensures the sets are disjoint..

(A) In the correlated setting, we have

$1-\beta\leq\bbE[\mathbb{I}\\{M(D^{i})\in B_{\alpha}(D^{i})\\}]\ \forall i,$
(90)

where the expectation is over the randomness in the algorithm $\cM$. By DP
constraint, we also have,

$\displaystyle\bbE[\mathbb{I}\\{M(D^{i})\in$ $\displaystyle
B_{\alpha}(D^{i})\\}]\leq
e^{\sum_{i=1}^{nt}\epsilon_{i}}\bbE[\mathbb{I}\\{M(D^{1})\in
B_{\alpha}(D^{i})\\}].$ (91)

By (90) and (91), summing $i\in[k]$, and noting that $B_{\alpha}(D^{i})$ are
disjoint, we get

$\displaystyle k(1-\beta)$ $\displaystyle\leq
e^{\sum_{i=1}^{nt}\epsilon_{i}}.$ (92)

Thus, $\sum_{i=1}^{nt}\epsilon_{i}\geq\log k(1-\beta)$. In (91), if we instead
use

$\mathbb{P}\\{M(D^{i})\in B_{\alpha}(D^{i})\\}\leq
1-e^{-\sum_{i=1}^{nt}\epsilon_{i}}+e^{-\sum_{i=1}^{nt}\epsilon_{i}}\mathbb{P}\\{M(D^{1})\in
B_{\alpha}(D^{i})\\},$

which is also a consequence of the DP definition (see Lemma 13 in Chaudhuri et
al. [32]), then we obtain
$\sum_{i=1}^{nt}\epsilon_{i}\geq\log(\frac{k-1}{k\beta})$. Thus, we can get

$\sum_{i=1}^{nt}\epsilon_{i}\gtrsim\log\frac{(k-1)(1-\beta)}{\beta}.$

(B) In the uncorrelated setting we have:

$1-\beta\leq\bbE[\mathbb{I}\\{M(D^{i}_{\sigma})\in B_{\alpha}(D^{i})\\}]\
\forall i,$ (93)

where the expectation is over the randomness in the algorithm $\cM$ and the
permutation $\sigma$. Let $\gamma:[n]\to[n]$ be such that
$\gamma(i)=\sigma^{-1}(i)$. By DP constraint, we also have,

$\displaystyle\bbE[\mathbb{I}\\{M(D^{i}_{\sigma})\in$ $\displaystyle
B_{\alpha}(D^{i})\\}|\sigma]\leq
e^{\sum_{i=1}^{nt}\epsilon_{\gamma(i)}}\bbE[\mathbb{I}\\{M(D_{\sigma}^{1})\in
B_{\alpha}(D^{i})\\}|\sigma].$ (94)

By taking expectation over $\sigma$ (94) and (93), summing $i\in[k]$, noting
that $B_{\alpha}(D^{i})$ are disjoint, we get

$\displaystyle k(1-\beta)$
$\displaystyle\leq\bbE[e^{\sum_{i=1}^{nt}\epsilon_{\gamma(i)}}].$ (95)

Using the same argument as part (A), using the alternate expression implied by
DP, the following is obtained

$E[e^{-\sum_{i=1}^{nt}\epsilon_{\gamma(i)}}]\leq\frac{k\beta}{k-1}.$ (96)

It should be noted that the above steps are only valid if
$\alpha<\frac{1}{2}$. $\alpha=\frac{1}{2}$ is not admissible in the above due
to our modified definition of the ceiling function rendering $t$ to be greater
than one.

∎

##  Appendix H Proof of Theorem C.4

Our proof is based on the idea of [47], augmented by a more methodical step-
by-step analysis.

######  Theorem (C.4).

.
We have
$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})\leq\frac{1}{4}$. Both
$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})$ satisfy

$\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(\bm{\epsilon})\geq\left(\sqrt{\cE_{stat}(\bm{\epsilon})}-\sqrt{\frac{1}{4n}}\right)_{+}^{2}.$
(97)

###### Proof.

We start with mean estimation.

$\displaystyle\cE_{u}^{m}(\bm{\epsilon})$
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[0,1]^{n}}\bbE\left[|\mu(D)-M(D_{\sigma})|^{2}\right]$
(98)
$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in\\{0,1\\}^{n}}\bbE\left[|\mu(D)-M(D_{\sigma})|^{2}\right]$
(99)
$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\bbE_{Z_{1},\ldots,Z_{n}\sim
P}\left[\left(\mu(Z)-M(Z)\right)^{2}\right],$ (100)
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\bbE_{Z_{1},\ldots,Z_{n}\sim
P}\left[\left(\mu(Z)-\mu(P)\right)^{2}+\left(\mu(P)-M(Z)\right)^{2}-2\left(\mu(Z)-\mu(P)\right)\left(\mu(P)-M(Z)\right)\right],$
(101)
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left\\{\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]+\frac{\mathsf{Var}(P)}{n}-2\bbE\left[\left(\mu(Z)-\mu(P)\right)\left(\mu(P)-M(Z)\right)\right]\right\\},$
(102)
$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left\\{\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]+\frac{\mathsf{Var}(P)}{n}-2\sqrt{\bbE\left[\left(\mu(Z)-\mu(P)\right)^{2}\right]\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]}\right\\},$
(103)
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left\\{\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]+\frac{\mathsf{Var}(P)}{n}-2\sqrt{\frac{\mathsf{Var}(P)}{n}\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]}\right\\},$
(104)
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left\\{\underbrace{f(M,P)+\frac{\mathsf{Var}(P)}{n}-2\sqrt{\frac{\mathsf{Var}(P)}{n}f(M,P)}}_{\text{Quadratic
in }\sqrt{\frac{\mathsf{Var}(P)}{n}}}\right\\}.$ (105)

(100) follows by relaxing worst-case dataset to worst-case distribution where
the data is sampled i.i.d. – this also helpds get rid of the permutation.
(103) follows by Cauchy-Schwarz and we use the notation
$f(M,P)=\bbE\left[\left(\mu(P)-M(Z)\right)^{2}\right]$ in (105). Now, we
minimize the quadratic in (105) wrt $\sqrt{\frac{\mathsf{Var}(P)}{n}}$, which
has a domain of $\left[0,\sqrt{\frac{1}{4n}}\right]$ for $P\in\cP(\\{0,1\\})$.

$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left\\{f(M,P)+(f(M,P)\wedge\frac{1}{4n})-2\sqrt{(f(M,P)\wedge\frac{1}{4n})f(M,P)}\right\\},$
(106)
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left(\sqrt{f(M,P)}-\sqrt{\frac{1}{4n}}\right)_{+}^{2}$
(107)

Now let $P^{*}(M)=\operatornamewithlimits{arg\leavevmode\nobreak\
max}_{P\in\cP(\\{0,1\\})}f(M,P)$.

For a given $M$, (107) is maximized wrt $P$ if $f(M,P)$ is maximized. Thus,

$\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\left(\sqrt{f(M,P)}-\sqrt{\frac{1}{4n}}\right)_{+}^{2}=\min_{M\in\cM_{\bm{\epsilon}}}\left(\sqrt{f(M,P^{*}(M))}-\sqrt{\frac{1}{4n}}\right)_{+}^{2}.$
(108)

The minimum over $M$ is achieved when $f(M,P^{*}(M))$ is minimized. Noting
that
$\min_{M\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}f(M,P)=\min_{M\in\cM_{\bm{\epsilon}}}f(M,P^{*}(M))=\cE_{stat}(\bm{\epsilon})$,
we have the desired result.

For frequency estimation,

$\displaystyle\cE_{u}^{f}(k,\bm{\epsilon})$
$\displaystyle=\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\bbE\left[\|\mu(D)-M(D_{\sigma})\|^{2}_{\infty}\right]$
(109)
$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\bbE\left[|\mu(D)_{1}-M(D_{\sigma})_{1}|^{2}\right]$
(110)

(110) follows since the error in the first coordinate will be lower than the
infinity norm. Next, we describe how we can now reduce this problem and follow
the same steps as that of mean estimation.

Let $Q(p)=(p,1-p,0,0,\ldots,0)$ be a multinomial distribution over $k$ values.
Then, we have

$\displaystyle\min_{M\in\cM_{\bm{\epsilon}}}\max_{D\in[k]^{n}}\bbE\left[|\mu(D)_{1}-M(D_{\sigma})_{1}|^{2}\right]$
$\displaystyle\geq\min_{M\in\cM_{\bm{\epsilon}}}\max_{p\in[0,1]}\bbE_{Z_{1},\ldots,Z_{n}\sim
Q(p)}\left[|\mu(Z_{1}^{n})_{1}-M(Z_{1}^{n})_{1}|^{2}\right],$ (111)
$\displaystyle=\min_{\tilde{M}\in\cM_{\bm{\epsilon}}}\max_{P\in\cP(\\{0,1\\})}\bbE_{W_{1},\ldots,W_{n}\sim
P}\left[|\mu(W)-\tilde{M}(W)|^{2}\right].$ (112)

The first inequality follows by replacing worst-case dataset by expectation
over the dataset generated by the multinomial distribution. Since a sample
from the multinomial distribution is fully determined by the first-coordinate,
we can restrict to algorithms $\tilde{M}$ which only depend on the first-
coordinate; thus, we have a change of variables and represent the problem as a
scalar and now the same steps as that of mean estimation can be applied. We
believe our bounds for frequency estimation can be made tighter with a more
delicate analysis. ∎

##  Appendix I Proof of Theorem 5.1 and Theorem 5.2

######  Theorem (5.1).

(A) For $\frac{1}{2n}\leq\cR_{c}^{f}(k,\beta,\bm{\epsilon})\leq\frac{1}{4}$,
the lower bound (31) implies that error incurred by HPF-C is of the same order
as the minimax rate, i.e.,

$\cR_{c}^{f}(k,\beta,\bm{\epsilon})\simeq R_{C}(k,\beta,\bm{\epsilon}).$

(B) For $\frac{1}{2n}\leq\cR_{c}^{m}(\beta,\bm{\epsilon})\leq\frac{1}{4}$, the
lower bound (32) implies that error incurred by HPM-C is of the same order as
the minimax rate, i.e.,

$\cR_{c}^{m}(\beta,\bm{\epsilon})\simeq R_{C}(1,\beta,\bm{\epsilon}).$

###### Proof.

We present the proof for frequency estimation. Similar steps can be used for
mean estimation.

Let $t=\lceil 2n\cR_{C}\rceil$. Since
$\frac{1}{2n}\leq\cR_{c}\leq\frac{1}{4}$, we have $\frac{t}{n}\simeq\cR_{c}$
and $n-t\simeq n$. The lower bound in Theorem C.3(A) implies that $t$
satisfies $\sum_{i=1}^{t}\epsilon_{i}\gtrsim\log(k/\beta)$ (we assume
$1-\beta\geq 1/2$ for meaningful regimes where we want low probability of
error). Thus, we have

$\epsilon_{t+1}\geq\log(k/\beta)/t\,,$

since $\bm{\epsilon}$ is non-decreasing. Consider the weights $\vecw$ such
that the first $t$ entries are zero and the rest $n-t$ entries are $1/(n-t)$.
Using these weights, we get

$R_{C}(k,\beta,\bm{\epsilon})^{2}\lesssim\frac{t^{2}}{n^{2}}\simeq\cR_{c}(k,\beta,\bm{\epsilon})^{2},$

where we used $\frac{1}{(n-t)\epsilon_{t+1}}\lesssim\frac{t}{n\log(k/\beta)}$.
∎

######  Theorem (5.2).

Assume high privacy demand where $\lVert\bm{\epsilon}\rVert_{\infty}\leq 1$,
for the two problems.
(A) Frequency Estimation: In the regime
$\frac{1}{2n}\leq\cR_{u}^{f}(k,\beta,\bm{\epsilon})$, we have the following
upper and lower bound on $\cR_{u}^{f}$,

$\begin{split}\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}\lesssim&\cR_{u}^{f}(k,\beta,\bm{\epsilon})\lesssim\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}+\\\
&\frac{\sqrt{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})\wedge
n\log(k/\beta)}}{\lVert\bm{\epsilon}\rVert_{1}}.\end{split}$ (113)

The upper bound is achieved by HPF-U and HPF-A. Further, if
$\mathsf{Var}(e^{-\bm{\epsilon}})\lesssim\frac{\log^{2}(k/\beta)}{n^{2}}$,
then we have

$\cR_{u}^{f}(k,\beta,\bm{\epsilon})\simeq\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}.$
(114)

(B) Mean Estimation: In the regime
$\frac{1}{2n}\leq\cR_{u}^{m}(\beta,\bm{\epsilon})$, we have the following
upper and lower bound on $\cR_{u}^{m}$,

$\begin{split}\frac{\log(1/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}\lesssim&\cR_{u}^{m}(\beta,\bm{\epsilon})\lesssim\frac{\log(1/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}+\\\
&\frac{\sqrt{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})\wedge
n\log(1/\beta)}}{\lVert\bm{\epsilon}\rVert_{1}}.\end{split}$ (115)

The upper bound is achieved by HPM-U and HPM-A. Further, if
$\mathsf{Var}(e^{-\bm{\epsilon}})\lesssim\frac{\log^{2}(1/\beta)}{n^{2}}$,
then we have

$\cR_{u}^{m}(\beta,\bm{\epsilon})\simeq\frac{\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}}.$
(116)

###### Proof.

We present the proof for frequency estimation. Similar steps can be used for
mean estimation.

In the upper bound, use the HPF-A weights
$\vecw=\frac{1-\exp(-\bm{\epsilon})}{\lVert
1-\exp(-\bm{\epsilon})\rVert_{1}}$. Using
$\lVert\vecw-\bm{1}/n\rVert_{1}^{2}\leq n\lVert\vecw-\bm{1}/n\rVert_{2}^{2}$,
we have

$\displaystyle R_{C}(k,\beta,\bm{\epsilon})^{2}$
$\displaystyle\leq\frac{\min\\{n\lVert 1-e^{-\bm{\epsilon}}-\frac{\lVert
1-e^{-\bm{\epsilon}}\rVert_{1}}{n}\rVert_{2}^{2},\log(k/\beta)\lVert
1-e^{-\bm{\epsilon}}\rVert_{2}^{2}\\}+\log^{2}(k/\beta)\left(\frac{1-e^{-\epsilon_{1}}}{\epsilon_{1}}\right)^{2}}{\lVert
1-e^{-\bm{\epsilon}}\rVert_{1}^{2}}$ (117)
$\displaystyle\leq\frac{\min\\{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}}),\log(k/\beta)\lVert
1-e^{-\bm{\epsilon}}\rVert_{2}^{2}\\}+\log^{2}(k/\beta)}{\lVert
1-e^{-\bm{\epsilon}}\rVert_{1}^{2}}$ (118) Using $1-e^{-\epsilon}\gtrsim$
$\displaystyle\text{$\epsilon$ for $\epsilon\leq 1$},$ (119)
$\displaystyle\leq\frac{\min\\{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}}),\log(k/\beta)\lVert
1-e^{-\bm{\epsilon}}\rVert_{2}^{2}\\}+\log^{2}(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}^{2}}$
(120) Using $\lVert 1-e^{-\bm{\epsilon}}\rVert_{2}^{2}=n\mathsf{Var}$
$(e^{-\bm{\epsilon}})+\frac{\lVert 1-e^{-\bm{\epsilon}}\rVert_{1}^{2}}{n}\leq
n\mathsf{Var}(e^{-\bm{\epsilon}})+\frac{\lVert\bm{\epsilon}\rVert_{1}^{2}}{n}$,
(121)
$\displaystyle\leq\frac{\min\\{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}}),\log(k/\beta)n\mathsf{Var}(e^{-\bm{\epsilon}})+\log(k/\beta)\frac{\lVert\bm{\epsilon}\rVert_{1}^{2}}{n}\\}+\log^{2}(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}^{2}}$
(122)
$\displaystyle=\frac{\log^{2}(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}^{2}}+\min\left\\{\frac{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})}{\lVert\bm{\epsilon}\rVert_{1}^{2}},\log(k/\beta)\left(\frac{1}{n}+\frac{n\mathsf{Var}(e^{-\bm{\epsilon}})}{\lVert\bm{\epsilon}\rVert_{1}^{2}}\right)\right\\}$
(123)

If in (120), we use $\lVert 1-e^{-\bm{\epsilon}}\rVert_{2}^{2}\leq n$, then we
would get

$R_{C}^{2}\lesssim\frac{\log^{2}(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}^{2}}+\min\left\\{\frac{n^{2}\mathsf{Var}(e^{-\bm{\epsilon}})}{\lVert\bm{\epsilon}\rVert_{1}^{2}},\frac{n\log(k/\beta)}{\lVert\bm{\epsilon}\rVert_{1}^{2}}\right\\}.$

Coming to the lower bound, use Jensen’s inequality in (33) to obtain

$\log\frac{k-1}{k\beta}\leq\frac{\lceil
2n\cR_{u}\rceil}{n}\lVert\bm{\epsilon}\rVert_{1}\simeq\cR_{u}\lVert\bm{\epsilon}\rVert_{1}.$
(124)

Let $Z$ be a sample from the vector $\sim\bm{\epsilon}$. Using Negative
Association in (34), we get

$\displaystyle k(1-\beta)$ $\displaystyle\leq\bbE[e^{Z}]^{\lceil
2n\cR_{u}\rceil}$ (125)
$\displaystyle=\left(\frac{1}{n}\sum_{i}e^{\epsilon_{i}}\right)^{\lceil
2n\cR_{u}\rceil}$ (126)
$\displaystyle\leq\left(\frac{1}{n}\sum_{i}(1+(e-1)\epsilon_{i})\right)^{\lceil
2n\cR_{u}\rceil}$ (127)
$\displaystyle=\left(1+\frac{(e-1)}{n}\lVert\bm{\epsilon}\rVert_{1}\right)^{\lceil
2n\cR_{u}\rceil}.$ (128)

In the above, (127) follows from $\lVert\bm{\epsilon}\rVert_{\infty}\leq 1$.
Taking logarithm and using $\log(1+x)\leq x$, we get

$\log k(1-\beta)\lesssim\cR_{u}\lVert\bm{\epsilon}\rVert_{1}.$ (129)

By adding (124) and (129), we get

$\log\frac{k}{\beta}\lesssim\cR_{u}\lVert\bm{\epsilon}\rVert_{1}.$ (130)

∎

##  Appendix J Proof for Theorem 5.3

######  Theorem (5.3).

For values of $\bm{\epsilon}$ satisfying
$\cE_{stat}(\bm{\epsilon})\geq\frac{1}{2n}$, we have

$\cE_{stat}(\bm{\epsilon})\lesssim\cE_{u}^{f}(k,\bm{\epsilon})\lesssim\log(k)^{2}\cE_{stat}(\bm{\epsilon})$
(131)

for frequency estimation and

$\cE_{u}^{m}(\bm{\epsilon})\simeq\cE_{stat}(\bm{\epsilon})$ (132)

for mean estimation.

###### Proof.

From Theorem C.4, we directly have
$\cE_{stat}(\bm{\epsilon})\lesssim\cE_{u}^{f}(k,\bm{\epsilon}),\cE_{u}^{m}(k,\bm{\epsilon})$
in the regime of interest.

Now, observe that

$\displaystyle\cE_{u}^{f}(k,\bm{\epsilon})$
$\displaystyle\lesssim\min_{\vecw\in\Delta_{n}}\left(\left\|\vecw-\frac{\bm{1}}{n}\right\|_{1}^{2}\wedge\log(k)\lVert\vecw\rVert_{2}^{2}\right)+\log(k)^{2}\left\|\frac{\vecw}{\bm{\epsilon}}\right\|^{2}_{\infty},$
(133)
$\displaystyle\lesssim\log(k)^{2}\min_{\vecw\in\Delta_{n}}\lVert\vecw\rVert_{2}^{2}+\left\|\frac{\vecw}{\bm{\epsilon}}\right\|^{2}_{\infty}.$
(134)

Similarly,

$\cE_{u}^{m}(\bm{\epsilon})\lesssim\min_{\vecw\in\Delta_{n}}\lVert\vecw\rVert_{2}^{2}+\left\|\frac{\vecw}{\bm{\epsilon}}\right\|^{2}_{\infty}.$
(135)

Using the result of Chaudhuri et al. [32] that
$\cE_{stat}(\bm{\epsilon})\simeq\min_{\vecw\in\Delta_{n}}\lVert\vecw\rVert_{2}^{2}+\left\|\frac{\vecw}{\bm{\epsilon}}\right\|^{2}_{\infty}$,
we get the desired.

It may be noted that the statistical minimax rate considered in Chaudhuri et
al. [32] is over all distributions on $[0,1]$ instead of our definition of all
distributions on $\\{0,1\\}$. However, bound their upper and lower bound work
for this case as well and leads to identical result. ∎

##  Appendix K A Special Case for $\cE_{c}^{f}$

We consider a special case in this Section and prove a tight lower bound using
a different technique. This Section is added purely for fun.

Consider the scenario where there are only two bins and out of $n$ users,
$n/2$ of them have privacy demand $\epsilon\to 0$ and the rest have a privacy
demand of $\epsilon\to\infty$. Let the dataset be presented as
$Z=(Z_{1},\ldots,Z_{n})\in\\{0,1\\}$. The frequency is given by
$\mu(Z)=(1-\frac{\sum_{i}Z_{i}}{n},\frac{\sum_{i}Z_{i}}{n})$. For this
section, we use slightly different notations, that we described below.

For this special setting, we denote the minimax rate by $\hat{\cR}_{u}(n)$.
Let the set of all algorithms that are $0$-DP in the first $n/2$ entries and
$\infty$-DP in the next $n/2$ entries of the input be represented as
$\hat{\cM}(n)$. In particular, we have the definition for minimax expected
squared $\ell_{\infty}$ error as

$\hat{\cR}_{u}(n)=\min_{M\in\cM(n)}\max_{Z\in\\{0,1\\}^{n}}\bbE\left[\|\mu(Z)-M(Z_{\sigma})\|^{2}_{\infty}\right].$
(136)

The above expectation is over the permutations and randomness in $M$. By the
result in the following two subsections (see (145) and (137)), we have
$\hat{\cR_{u}}(n)\simeq\frac{1}{n}$. This implies that our upper bound, given
by HPF-U, is tight in this regime.

###  K.1 Upper Bound

HPF-U, for this setting, just uses the empirical frequency from public data as
the estimator. HPF-U will have a squared $\ell_{\infty}$ error greater than
$\frac{\log(2/\beta)}{n}$ with probability less than $\beta$. In terms of
expected squared $\ell_{\infty}$ error, one can integrate the tail bound in
(60) to get the upper bound

$\hat{\cR}_{u}(n)\lesssim\frac{1}{n}.$ (137)

###  K.2 Lower Bound

Let the data of the $n/2$ users with public data be $X=(X_{1},\ldots,X_{n/2})$
which are samples without replacement from $Z$ and let the rest of the private
data be $Y=(Y_{1},\ldots,Y_{n/2})$. Based on $X$, the algorithm would need to
estimate $\mu(Z)$.

Out of the two bins $(0,1)$, we can just focus on bin $1$. Thus we denote
$M(Z_{\sigma})_{1}$ by $f(X)$. We have,

$\displaystyle\hat{\cR}_{u}(n)$
$\displaystyle=\min_{M\in\cM(n)}\max_{Z\in\\{0,1\\}^{n}}\bbE\left[\|\mu(Z)-M(Z_{\sigma})\|^{2}_{\infty}\right]$
(138)
$\displaystyle\geq\min_{M\in\cM(n)}\max_{Z\in\\{0,1\\}^{n}}\bbE\left[|\mu(Z)_{1}-f(X)|^{2}\right]$
(139)
$\displaystyle=\min_{M\in\cM(n)}\max_{Z\in\\{0,1\\}^{n}}\bbE\left[\left|\frac{\sum_{i=1}^{n/2}X_{i}+Y_{i}}{n}-f(X)\right|^{2}\right]$
(140)
$\displaystyle\geq\min_{M\in\cM(n)}\bbE_{Z_{1},\ldots,Z_{n}\sim\mathsf{Bern}(1/2)}\left[\left|\frac{\sum_{i=1}^{n/2}X_{i}+Y_{i}}{n}-f(X)\right|^{2}\right],$
(141)

where the last inequality follows by replacing the worst-case dataset $Z$ by
taking expectation over i.i.d. samples
$Z_{1},\ldots,Z_{n}\sim\mathsf{Bern}(1/2)$. Now, since $Z_{1},\ldots,Z_{n}$
are i.i.d. $\mathsf{Bern}(1/2)$ and $X,Y$ are samples without replacement from
$Z$, we have the fact that $X_{1},\ldots,X_{n/2},Y_{1},\ldots,Y_{n/2}$ are
i.i.d. $\mathsf{Bern}(1/2)$. Since $X$ and $Y$ are now independent, and by the
MMSE property of conditional expectation, we have

$\displaystyle\bbE\left[\left|\frac{\sum_{i=1}^{n/2}X_{i}+Y_{i}}{n}-f(X)\right|^{2}\right]$
$\displaystyle\geq\bbE\left[\left|\frac{\sum_{i=1}^{n/2}X_{i}+Y_{i}}{n}-\bbE\left[\frac{\sum_{i=1}^{n/2}X_{i}+Y_{i}}{n}|X\right]\right|^{2}\right]$
(142)
$\displaystyle=\bbE\left[\left|\frac{\sum_{i=1}^{n/2}Y_{i}}{n}-\frac{1}{4}\right|^{2}\right]$
(143) $\displaystyle=\frac{1}{8n}.$ (144)

Thus, we have

$\hat{\cR_{u}}(n)\gtrsim\frac{1}{n}.$ (145)

##  Appendix L Weights in Local DP

###  L.1 Frequency Estimation

Suppose user $i$ has a datapoint in bin $j$, then present user $i$’s datapoint
$D_{i}$ as $\vece_{j}\in\bbR^{k}$. In the following, we shall represent user
$i$’s true data as $\vecD_{i}\in\\{0,1\\}^{k}$.

In the $k$-RAPPOR scheme, user $i$ flips each bit of the vector independently
with probability $\frac{1}{1+\exp{(\epsilon_{i}/2)}}$ and sends the new vector
$\vecx_{i}$ to the server. After receiving the vector
$\vecx_{i}\in\\{0,1\\}^{k}$ from user $i$, the server can compute
$\coth{(\frac{\epsilon_{i}}{4})}(\vecx_{i}-\bm{1}/(1+\exp{(\epsilon_{i}/2)}))$
which is an unbiased estimator of the user’s data. For weights
$\vecw\in\Delta_{n}$, let the overall estimate for $\mu(D)$ be
$\sum_{i=1}^{n}w_{i}\coth{(\frac{\epsilon_{i}}{4})}(\vecx_{i}-\bm{1}/(1+\exp{(\epsilon_{i}/2)}))$.

Now, representing this mechanism as $M(D)$, we have

$\mathbb{P}\\{\lVert
M(D)-\mu(D)\rVert_{\infty}>\alpha\\}\leq\mathbb{P}\\{\lVert
M(D)-\sum_{i}w_{i}\vecD_{i}\rVert_{\infty}>\alpha/2\\}+\mathbb{P}\\{\lVert\sum_{i}w_{i}\vecD_{i}-\mu(D)\rVert_{\infty}>\alpha/2\\}.$
(146)

Now note that
$\bbE[\coth{(\frac{\epsilon_{i}}{4})}(\vecx_{i}-\bm{1}/(1+\exp{(\epsilon_{i}/2)}))]=\vecD_{i}$.
For $j\in[k]$, let $Y_{i}^{j}$ be the $j$-th component of
$\coth{(\frac{\epsilon_{i}}{4})}(\vecx_{i}-\bm{1}/(1+\exp{(\epsilon_{i}/2)}))-\vecD_{i}$.
Then $Y_{i}^{j}$ is either a
$\coth{(\frac{\epsilon_{i}}{4})}\mathsf{Bern}(\frac{e^{\epsilon_{i}/2}}{1+e^{\epsilon_{i}/2}})-\frac{e^{\epsilon_{i}/2}}{e^{\epsilon_{i}/2}-1}$
RV (if $\vecD_{i}=\vece_{j}$) or a
$\coth{(\frac{\epsilon_{i}}{4})}\mathsf{Bern}(\frac{1}{1+e^{\epsilon_{i}/2}})-\frac{1}{e^{\epsilon_{i}/2}-1}$
RV (otherwise). For a given $j$, $Y^{j}_{i}$ are independent as well.

Therefore, using Kearns-Saul concentration inequality [48, 49], we get

$\mathbb{P}\\{\lVert
M(D)-\sum_{i}w_{i}\vecD_{i}\rVert_{\infty}>\alpha/2\\}\leq
2k\exp\left[-\frac{\alpha^{2}}{8\sum_{i}w_{i}^{2}\coth{(\frac{\epsilon_{i}}{4})}/\epsilon_{i}}\right]$
(147)

For the
$\mathbb{P}\\{\lVert\sum_{i}w_{i}\vecD_{i}-\mu(D)\rVert_{\infty}>\alpha/2\\}$
term, exact same analysis as that of Theorem C.1 works. Thus,

  * •

In the correlated setting, we have

$\alpha^{2}\lesssim\left(\min_{\vecw\in\Delta_{n}}\lVert\vecw-\bm{1}/n\rVert_{1}^{2}+\log(k/\beta)\sum_{i}w_{i}^{2}\coth{(\frac{\epsilon_{i}}{4})}/\epsilon_{i}\right)\wedge
1.$ (148)

  * •

In the uncorrelated setting, we have

$\alpha^{2}\lesssim\left(\min_{\vecw\in\Delta_{n}}\left[\lVert\vecw-\bm{1}/n\rVert_{1}^{2}\wedge\log(k/\beta)\lVert\vecw\rVert_{2}^{2}\right]+\log(k/\beta)\sum_{i}w_{i}^{2}\coth{(\frac{\epsilon_{i}}{4})}/\epsilon_{i}\right)\wedge
1.$ (149)

For the purpose of implementation, we upper bound the $\ell_{1}$ norm in the
above by $n\ell_{2}$ norm.

###  L.2 Mean Estimation

Let user $i$’s data be $X_{i}\in[0,1]$ then it sends to the server
$Y_{i}=X_{i}+N_{i}$ where $N_{i}\sim$Laplace$(\frac{1}{\epsilon_{i}})$. The
server’s estimate is $\sum_{i}w_{i}Y_{i}$ for $\vecw\in\Delta_{n}$.

Now, representing this mechanism as $M(Y)$, we have

$\mathbb{P}\\{|M(Y)-\mu(X)|>\alpha\\}\leq\mathbb{P}\\{|\sum_{i}w_{i}N_{i}|>\alpha/2\\}+\mathbb{P}\\{|\sum_{i}w_{i}X_{i}-\mu(X)|>\alpha/2\\}.$
(150)

For the second term, exact same analysis as that of Theorem C.1 works so we
focus on bounding the first term. Using the tail bound of Chan et al. [50]
(Lemma 2.8), we have

$\mathbb{P}\\{|\sum_{i}w_{i}N_{i}|>\alpha/2\\}\leq\begin{cases}\exp\\{-c\frac{\alpha^{2}}{\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}}\\}&\text{if
}\alpha/2\leq\frac{2\sqrt{2}\lVert\vecw/\bm{\epsilon}\rVert_{2}^{2}}{\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}\\\
\exp\\{-c^{\prime}\frac{\alpha}{\lVert\vecw/\bm{\epsilon}\rVert_{\infty}}\\}&\text{else.}\end{cases}$
(151)

To simplify the problem, we just consider the sub-exponential tail bound as a
heuristic for the optimization. Thus,

  * •

In the correlated setting, we have

$\vecw_{LDP}=\operatornamewithlimits{arg\leavevmode\nobreak\
min}_{\vecw\in\Delta_{n}}\lVert\vecw-\bm{1}/n\rVert_{1}^{2}+\log(1/\beta)^{2}\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}.$
(152)

  * •

In the uncorrelated setting, we have

$\vecw_{LDP}=\operatornamewithlimits{arg\leavevmode\nobreak\
min}_{\vecw\in\Delta_{n}}\left[\lVert\vecw-\bm{1}/n\rVert_{1}^{2}\wedge\log(k/\beta)\lVert\vecw\rVert_{2}^{2}\right]+\log(1/\beta)^{2}\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}.$
(153)

Recall that these are exact same weights obtained in HPM-C and HPM-U!

##  Appendix M Faster Variants of HPF-C and HPF-U

Algorithm 3 Heterogeneously Private Frequency Turbo for different cases. HPF-
CT and HPF-UT are for the correlated and the uncorrelated setting
respectively.

Input: $\bm{\epsilon}\in\bbR_{>0}^{n},\ X\in[k]^{n}$, $\beta>0$

HPF-C-T: Set
$\vecw^{*}=\operatorname*{argmin}_{\vecw\in\Delta_{n}}n\left\|\vecw-\frac{\bm{1}}{n}\right\|^{2}_{2}+\log^{2}(k/\beta)\left\|\frac{\vecw}{\bm{\epsilon}}\right\|^{2}_{\infty}.$

HPF-U-T: Set
$\begin{split}\vecw^{*}=\operatorname*{argmin}_{\vecw\in\Delta_{n}}&\left(n\left\|\vecw-\frac{\bm{1}}{n}\right\|^{2}_{2}\wedge\log\left(\frac{k}{\beta}\right)\lVert\vecw\rVert_{2}^{2}\right)+\\\
&\log^{2}\left(\frac{k}{\beta}\right)\left\|\frac{\vecw}{\bm{\epsilon}}\right\|_{\infty}^{2}\end{split}$

Sample i.i.d.
$N_{1},\ldots,N_{k}\sim\text{Laplace}(2\|\frac{\vecw^{*}}{\bm{\epsilon}}\|_{\infty})$

Calculate $\vecy\in\bbR^{k}$:
$y_{j}=N_{j}+\sum_{i=1}^{n}w_{i}^{*}\mathbb{I}\\{X_{i}=j\\},\ \ \forall
j\in[k].$

Set $y_{j}\leftarrow\max\\{\min\\{y_{j},1\\},0\\}$ $\forall j\in[k]$.

return $\vecy$

In the algorithms HPF-C and HPF-U, the minimization, although convex, can be a
bottleneck and we attempt to consider more efficient variants. If we upper
bound the $\ell_{1}$-norm by $n\ell_{2}$-norm, then the optimization problem
has a closed form solution which we can implement efficiently in $O(n\log n)$
time. Further, the arithmetic operations involved in finding the solution do
not suffer from the numerical instability issues that cvxpy runs into in HPF-C
and HPF-U when the entries of the privacy demand vector can range vary between
several orders of magnitude. Increasing the number of users $n$ also brings
numerical instability for solving the weights using cvxpy.

These variants of the algorithm can be efficiently implemented since
minimizations of form
$\min_{\vecw\in\Delta_{n}}\lVert\vecw\rVert_{2}^{2}+c\lVert\vecw/\bm{\epsilon}\rVert_{\infty}^{2}$
can be solved in $O(n\log n)$ time using the algorithm presented by Chaudhuri
et al. [32]. In brief, for non-decreasing $\bm{\epsilon}$, construct the
sequence

$\displaystyle r_{1}$ $\displaystyle=\epsilon_{1},$ (154) $\displaystyle
r_{k+1}$
$\displaystyle=\frac{\sum_{i=1}^{k}r_{i}^{2}+c}{\sum_{i=1}^{k}r_{i}}\wedge\epsilon_{k+1}\
\ \forall k\in[n-1].$ (155)

The solution can be obtained as $\vecw^{*}=\vecr/\lVert\vecr\rVert_{1}$. We
refer to these two faster variantspresented in Algorithm 3 as HPF-CT and HPF-
UT respectively. For HPF-UT, one can solve two minimization problems – one
using the term $n\lVert\vecw-\bm{1}/n\rVert_{2}^{2}$ and one using the term
$\log(k/\beta)\lVert\vecw\rVert_{2}^{2}$ – and finally choose the weights
corresponding to the one minimizing the two objective values.

We perform experiments with synthetic dataset in a similar manner as our
earlier experiments to compare HPF-C with HPF-CT in the correlated setting,
and HPF-U with HPF-UT in the uncorrelated setting. The graphs showing the
empricial $95$-th quantile of the $l_{\infty}$ error is presented in Figure 2.
Our proposed heuristic algorithm HPF-A performs the best and is the most
efficient. In the correlated regime, HPF-C performs better than HPF-CT at the
cost of being more computationally difficult. In the uncorrelated regime,
HPF-U and HPF-UT perform exactly the same in Figure 2, indicating that the
optimal weights must have been identical, which is possible if
$\log(k/\beta)\lVert\vecw\rVert_{2}^{2}$ term is smaller among the two terms
in the minimization in both HPF-U and HPF-UT.

Similar steps can be performed to speed up HPF-C and HPF-U.

(a) Correlared, Synthetic $(10000,5)$ Dataset (b) Correlared, Synthetic
$(10000,20)$ Dataset

(c) Uncorrelared, Synthetic $(10000,5)$ Dataset (d) Uncorrelared, Synthetic
$(10000,20)$ Dataset

Figure 2: Comparison of performance of the HPF algorithms in Algorithm 1 and
3.