Instance-optimal Mean Estimation Under Differential Privacy
Authors: Ziyue Huang
Yuting Liang
Ke Yi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Mean estimation
differential privacy
instance optimality

Abstract: Mean estimation under differential privacy is a fundamental problem, but worst-case optimal mechanisms do not offer meaningful utility guarantees in practice when the global sensitivity is very large.  Instead, various heuristics have been proposed to reduce the error on real-world data that do not resemble the worst-case instance.  This paper takes a principled approach, yielding a mechanism that is instance-optimal in a strong sense.  In addition to its theoretical optimality, the mechanism is also simple and practical, and adapts to a variety of data characteristics without the need of parameter tuning.  It easily extends to the local and shuffle model as well.

Instance-optimal Mean Estimation Under Differential Privacy
Ziyue Huang, Yuting Liang, Ke (zhuangbq, yllogggllgnnsss yokeegssykkkeeeee yike]@cse ust .kk Department of Computer Science and Engineering Hong Kong University of Science and Technology
Abstract
Mean estimation under differential privacy is fundamental problem, but worst- case optimal mechanisms do not offer meaningful utility guarantees in practice when the global sensitivity is very large. Instead, various heuristics have been proposed to reduce the error on real-world data that do not resemble the worst-case instance. This paper takes principled approach, yielding a mechanism that is instance-optimal in a strong sense. In addition to its theoretical optimality, the mechanism also simple and practical, and adapts to a variety of data characteris- tics without the need of parameter tuning. It easily extends to the local and shuffle model as well.
Introduction
Mean estimation is one of the most fundamental problems statistics, optimization, and machine learning. However, privacy concerns forbid from using the exact mean in these applications, and the problem of how to achieve the smallest еггоr under a given privacy model has received considerable attention in the literature. Differential privacy (DP) a rigorous mathematical definition for protecting individual privacy and has emerged as the golden standard in analysis nowadays, which has been deployed by Apple [16, Google 22 and Microsoft [17
data
Given a data set D := {x; hein) C Ud, where 4 = [u]. i.e., each coordinate of the input vector is an integer (real-valued coordinates can be handled by quantization;
remark [ goal is to obtain a differentially private estimation M (D) for the mean J(D) = 1 - with small & error [D) f [D) Because f(-) has global & sensitivity GS, v /du/n. n, the standard DP mechanism just adds Gaussian noise scaled to GS, y to each coordinate of f(D), which results in an l error proportional to du/n. This simple mechanism is worst-case optimal (28), but is certainly undesirable in practice, as people often conservatively use a large (e.g., w = 232) but the actual dataset 'D may have much smaller coordinates. Instead, the clipped-mean estimator (1] (see Section 3.1 for details) has been widely used as an effective heuristic, but two questions remain unresolved: (1) how to choose the clipping threshold C: and (2) if it can yield any optimality guarantees. We answer these questions in fairly strong sense in this paper.
1.1 Instance Optimality
As worst-case optimality is theoretically trivial and practically meaningless for the mean estimation problem when the global sensitivity is too large, one may aim at instance optimality, More precisely, let M be the class of DP mechanisms and let
Rins ( = inf inf Pr]])M - < 2 2/3)
M
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

be the smallest error any M' can achieve (with constant probability) on D, then the standard definition of instance optimality requires us design an M such that
(D) S c. Rins (D) 2 2/3
(1)
for every D. where is called the optimality ratio. Unfortunately, for any D, one can design trivial M'(.) = ((D) that has ( error on 'D (but fails miserably on other instances), so Rins (-) = 0, which rules out instance-optimal DP mechanisms by a standard argument 221
Since R-ns(-) is unachievable, relaxed versions can be considered. The above trivial M' exists because it is only required to work well on one instance D. Imposing higher requirements on M' would yield relaxed notions of instance optimality. One natural requirement is that M' should work well not just on D, but also on its neighbors, i.e., we raise the target error from Rins (D) to
Robe == inf
sup M'EM D' (D.
in Pr[ll f(D')ll S 2 2/3).
Vahdan [35 observes that Rabe (D) is exactly LS, (D), the local sensitivity of f at D, up to constant factors. However, (.) may not be an appropriate target to shoot at, depending on what f is. For the MEDIAN problem, , (D) = 0 for certain D's ss and no DP mechanisms can achieve this error
while for mean estimation, (D) ((S,,) @ ((Vdu/n) n) for all D, so this relaxation turns instance optimality into worst-case optimality.
33
The reason why the above relaxation is "too much" for the mean estimation problem is that D' may change one vector of 'D arbitrarily, e.g., from (O....,() 0) to (u,..., u). We restrict this. More precisely, letting sup denote the set of distinct vectors in D, we consider the target error
Rim (D) =
inf M'EM D' (D.D' (tap"""sl.lppppp))cpppppp
sup
in Prr[I ((D))l2 S 5] 2 2/3),
namely, we require M' to work well only on D and its in-neighbors, in which a vector can only be changed another one already existing in D. Correspondingly, an instance-optimal M (w.r.t. the in-neighborhood) is one such that |I holds where Ris is replaced by Rim-ate-
We make few notes on this notion of instance optimality: (1) This optimality is only about the utility of the mechanism, not its privacy. We still require the mechanism to satisfy the DP requirement between any D, 'D' such that dham (D, D') general, a smaller neighhorhood leads to a stronger notion of instance optimality. Thus, the optimality using in-neighbors is stronger than that using all neighbors, which is in turn stronger than worst-case optimality (i.e., D'' can be any instance), while the latter two are actually the same for the mean estimation problem. (3) For an instance-optimal M (by our notion), there still exist D, M' such that M' does better on D than M, but it is not possible for M' to achieve smaller error than the error of M on over all in in-neighbor of D. This is more meaningful than ranging over all neighbors of D, some of which (e.g., one with (u.... ................................ u) as a datum) are unlikely to be the actual instances encountered in practice.
1, not necessarily one and its in-neighbors. (2) In
1.2 Our Results
To design an (D) for the mean function S(D) = - ny that achieves an error W.r.t. Rin (D) for all DD we need an upper bound and lower bound. For the lower bound, we show that Rin (D) = (Dw(D)n)) where w(() == max gixiiiiejnn ||ar; æzyl2 is the diameter of D. Thus, from the upper bound side, suffices to show that the mechanism's 's error bounded by e- w wDD) /m/... This achieved in two steps. First, we use the clipped-mean estimator, but find the clipping threshold C' that optimizes its bias-variance trade-off, which is a certain quantile of the norms of the vectors in D. However, we cannot use the optimal C' directly, as it would violate DP. Thus, we use simple binary search based algorithm that can find any specific quantile privately with an optimal rank error. This results in a DP mechanism with error Ó( (V/dpp) -r(D)/n, where r r(D) == max, ||æ:;12 and p is the privacy parameter (formal definition given in Section (). To reduce the error from r(D) (DD), in the second step, we rotate and shift D into a D such that r(D) = (w)D)) w.h.p., and apply the clipped-mean estimator (with our privatized optimal clipping threshold) on D, leading to an error of ((vd/p) w(D) /n for is optimal, i.e., any mechanism M (D) having error c- w(D)/n nn for all D must have π2( /d/p) for p O(Vd/n).
:==
n = (( pd). We also show that the optimality ratio =
2

---

Our mechanism has the following applications: (1) It can be applied directly to statistical mean estimation, where the vectors in D are i.i.d. samples from certain distribution and one would like to estimate the mean of the distribution (in contrast, the version defined above is referred to as empirical mean estimation). For concreteness, we show how this done for the multivariate Gaussian distributions N E). For the case Σ = I, our algorithm achieves an f2 error of using 0 + 4 samples for I O(1), matching the optimal bound in the statistical setting [8]. For non-identity, unknown Σ, the error is proportional to || as in g Our mechanism requires only crude a priori bounds on and Σ (i.e., the error depends on these bounds logarihhmically) while g needs a constant-factor approximation of m, which can be obtained using n = 2 samples 126] Note that this can be vd-factor higher than the sample complexity of mean estimation. Fundamentally, estimating Σ is harder than estimating μ. and we bypass the former so as to retain the same sample complexity of the latter. In practice, estimating Σ first would consume the privacy budget from the mean estimation problem itself. On the other hand, the benefit of estimating > first is that one obtain error guarantee under the Mahalanobis distance [26]. which cannot be achieved by our method. (2) By simply changing the primitive operations, our mechanism easily extends to the local and shuffle model of differential privacy. In doing so, we also extend the oie-dimensi summation/mman estimation protocol in the shuffle model [5] to high dimensions.
In addition to the theoretical optimality, our mechanism is also simple and practical. Most importantly, there no (internal) parameter to tune. Yet, our experimental results demonstrate that our mechanism outperforms the state-of-the-ar algorithm [8] with the best parameters tuned for each specific setting.
1.3 Related Work
Asi and Duchi 4 recently initialized the study instance optimality under DP. They propose two ways to relax (equivalently, strengthen the requirement on M') the strict instance optimality, which is unachievable. The first is to require M' to be unbiased. This is not appropriate for mean estimation, since many estimators, including clipped-mean, is not unbiased. The second is to require M' to work well over all the r-distance neighbors of 'D for r 2 1. Thus, their optimality is weaker than using Ratr(.). hence not appropriate for the mean estimation problem (i.e., their optimality is the same as worst-case optimality). Instance optimality has not been studied in the local or shuffle model; existing protocols in these two models 7 19 5) all have errors proportional to the global sensitivity.
How to choose the clipping threshold C' for the clipped mean estimator has been extensively studied 3 34 32), but existing methods do not offer any optimality guarantees. In particular, Andrew et al. 3 also use quantile (actually, median) as C, but choice. Furthermore, they use online gradient descent to find a privatized quantile, which does not have any theoretical error guarantees. Amin et al. (2) attempt to select an optimal quantile as the clipping threshold to truncate the number of contributions from each user, instead of clipping the actual samples in high dimensions in our paper.
shall see, median is actually not the optimal
In the statistical setting, where the data are i.i.d. samples from some specific distribution, there are numerous methods 126 8 27 229 that can avoid an error proportional to the global sensitivity. by exploiting the concentration property of the distribution. In particular, Biswas et al. [8] provide a simple and practical mechanism for multivariate Gaussian data. Levy al. [30] propose a private mean estimator with error scaling with the concentration radius T of the distribution rather than the entire range, but their algorithm requires to be publicly known in advance. In the local model, the algorithm in 23) uses a quantile estimation procedure based on binary search as a subroutine for one-dimensional Gaussian data.
Very recently, the relationship between the error of mean estimation and the diameter of the dataset has been exploited in [5] for low-communication protocols, but they do not consider privacy. Our DP protocols in the local and shuffle models have communication cost Ó(d) per user (we do not state the communication costs the theorems as they are not our major concern); would interesting to see if ideas from [15] can be used to reduce it further.
3

---

2 Preliminaries
2.1 Differential Privacy in the Central Model
Definition 1 (Differential Privacy (DP) (2]].. For > 0 and 6 2 0, a randomized algorithm M : x" + V's (s, differrretiil private if for any neighboring datasets D ~ D (i.e., cham (D, D') 1) and any E' V
(D( E EJ S ef Pr((M(D)) E E] 6.
Definition (Concentrated Differential Privacy (zCDP) TO). For p > 0, a randomized algorithm : + y is p-zCDP if for any DD ~ 'D',
(M((II)))))) s pa:
for all a > 1, where (D(M(())) is the a-Rényi divergence between (D) and (D').
Note that (c, O)-DP implies 5- -ZCDP, which implies ( + /2//2oo x 6)-DP for any 5 0. To
release numeric function f(D) taking values in Rd, the most common technique for achieving zCDP is by masking the result with Gaussian noise calibrated to the lz-sensitivity of f. Lemma (Gaussian Mechanism [10). Let : + Rd be function with global fz-sensitivity , == Da [I - SDD")ll2 For given data set E X", the mechanism that releases GS? GS
f(D) +N (0, (,,-, 2p Taxa) satisfies p-zCDP.
Lemma 2 (Composition Theorem 10 211). If M is adaptive composition of differentially private algorithms M1, , MR, then
1. If each M, satisfies (E,, D.) then M satisfies (E, E.r E, 6.)
2. For all E, 5, 8' 2 if each Mj satisfies (s,8)-DP, then M satisfies (E', kō DDD where
e' 22 fe + kE)
3. If each M, satisfies Pc-cCDP, then M satisfies (E PCD-
2.2 Differential Privacy in the Local Model and Shuffle Model
The above definitions of DP and zCDP assume that D is handled by a trusted curator and only the output of the mechanism will be released to the public. Therefore, if the curator is corrupted, the privacy of all users will be breached. For weaker trust assumptions, the most popular models are the local model and the shuffle model, where each user holds their datum and locally privatizes (by some randomized mechanism) the message before sending it out for analysis. Hence, there is no third-party who has direct access to D. Formally, each user holds one datum 2; D, and the protocol interacts with the dataset using some local randomizer R: X' + V, and the privacy guarantee is defined over the transcript (all messages sent during the protocol). For simplicity, we only present the definition for one-round protocols; the privacy guarantee of multi-round protocols can be composed across all rounds by the composition theorem. The definition below uses >CDP; other DP notions can be defined similarly.
Definition 3 (Local Model (LDP)). A protocol using R(-) as the local randomizer satisfies p-zCDP the local model for any xr x' E X, any a > 1, (R(= S par.
Due to the much stronger privacy requirement, the best accuracy guarantee of LDP protocols for several fundamental problems 12 6 [8] 31 is Vi-factor worse than that in the central model. The shuffle model is established on an intermediary level of trust assumption between the local model and the central model and aims for obtaining errors closer to the central model. The key feature of the shuffle model is a trusted shuffler S, which can permute all messages randomly before sending them to the analyzer, so that adversary cannot identify the source of any message. Specifically, consider the multi-message shuffle model, where each local randomizer R X' + ym outputs m messages, and the transcript of the protocol (I) is random permutation of all messages. The following definition uses (c, 5)-D; the other two DP notions can also be defined similarly, but they do not offer the improvements that we want over LDP protocols.
Definition (Shuffle Model). protocol P satisfies (c, 8)-DP in the shuffle model for any D D'. and any set E mmm, Pr[llp(D) E] < e. (r(IIp(D') E] 8.

---

3 Our Method
3.1 Clipped-Mean Estimator
In the rest of the paper, we focus on the mean function f(D) = n شi= very natural idea to clip each vector in its l norm by some threshold C. This reduces GS to 2C/n, leading to the clipped-mest mean estimator [
i= 2,, Since GSy is large,
MD = 1 Σ min
1 22 + N
2C2
(2)
pn?
Lemma 3. For any given C, (D(D) satisfies p-zCDP, and has an expected Ez error at most
1 Σ max{]|=sll2- 0,0+
C. n
2d
([) S(D)ll ((C:D)
An important remaining question is how to set the clipping threshold C. Setting it too low will result in a large bias, while setting it too high will introduce large amount of noise. We show how to choose the optimal C' to balance this bias-varianc trade-off. It is easy to see that the error ECC; D) a convex function w.r.t. C, thus the optimal C' can be found by setting the derivative of {(C; D) to zero, i.e.
( D)
16 [n] |mll2 > CYI /2dp = 0.
ac
n1
Therefore, the optimal choice of C' is the (n - pddpp)-th quantile of (11xe|1a]ve()))
3.2 Private Quantile Selection
However, we cannot use the optimal C' directly, as it would violate DP. Instead, we find a privatized quantile with small rank error. Specifically, for this problem, consists sequence of ordered integers 0 I 2(1) I ... S [()) u. We would like to design DP mechanism that, for given m, returns
(which is not necessarily element in D) such that ((m-r) S I S (( w.h.p. Here 7 is referred to as the rank error. Existing methods on private range counting queries [T] 20 can be used for this purpose, but they actually find all quantiles, which is an overkill. Instead,
a simple binary search algorithm [2 14], which not only simplifies the algorithm, but also reduces the rank error (by (olylog(u) factors) to nearly optimal. Our algorithm PrivQuant makes of
function NoisyRC([a, b), D) that returns a noisy count of [D n [a, b]l. and we present the details in the supplementary material.
In the central DP model, we simply use NoisyRC([O, mid], D) = D [0, mid] + (O, log u/ (2p)). Theorem 1. The algorithum Priuquant preserves p-CDP, and returns a quantile with rank ervor with probability at least 1 3 for /log log
log $ /22p).
In Section 4 we prove an 2 (loooo u/ p) lower bound (Corollary on the rank error under zCDP for constant 3. Thus the algorithm is optimal up to just an O(Vlog log factor
We can now use PrivQuant to find an approximately optimal clipping threshold. Specifically, we invoke PrivQuant with p' = p/4 to find the max(n- max ( 7). 1)-th quantile of {||ar: (12) 1e in)- They are integers no more than du², so replacing u by du in Theorem 1 yields rank
error of r 2 (// log log(du) /p. Then we set Ö as the square root of the returned quantile. Finally, return the clipped mean estimator M (D) with p' = 3p/4. The following theorem analyzes its error.
Theorem 2. Our mean estimation mechanism is pCPCPP and has l error -(d
with probability B, where T 2 log(du) log lug(du)
DDfine z() for j and 2G) for
5

---

3.3 Shifted-Clipped-Mean Estimator
To reduce the error from being proportional to r(D) to being proportional to w(D), we perform a random rotation on D followed by translation. The rotation is done by é; := Dz,, where H is the Hadamard matrix, D a diagonal matrix whose diagonal entry is independently and uniformly drawn from {-1, +1}. Note that for now omit the normalization coefficient + that each coordinate of è; is still an integer, we will apply the normalization to the final estimator instead. Then, for each j E [d]. we invoke PrivQuant with p' = p/(4d) (4d) to find an approximate median of (#:) along dimension j. denoted as ēÿ. Next, we shift the dataset to be centered around č == (c1..... Ca), obtaining D { ;- -; (E Note that é has integer coordinates, does Ty. Finally, we apply the clipped-mean estimator in Theorem with p' = P on D, obtaining an estimation ÿ, and return y = HD) va (Ø + č) as the mean estimator over D.
ya
Theorem 3. Set T
log(du) log dlogidu) B / and assume n ((TVd). Our mean estimation ww(D)/n with probability
mechanism p-zCDP, and has &g error O ((ValD+
Remark 1. For dataset with real coordinates bounded by (in absoluate value), one can quantize each coordinate to an integer using bucket size az/ Vd, for any < < R, and then apply our algorithm over an integer universe of size u = 2R d/a. This just brings an additive a error to the error bound of Theorem
Statistical Mean Estimation. Suppose D consists of i..dd samples drawn from the multivariate Gaussian distribution (1, Σ), and we wish to estimate μ4, assuming a priori bounds ||u||2 S R and 0 - I W Σ < σ max We first clip each sample 2; + min RR') /||=r]12, 1) where
R' = R + 20 V d + log
4n T Then we apply our mechanism with bucket size a/ Vd where
= o min v d/n. We analyze the error the supplementary material. When = I and ignoring + A matching the known optimal
log (1) (0) d
Omar factors, the error in becomes Ô vd
3 auin
V
bound for Gaussian mean estimation g
Lower Bounds
In this section we establish the instance optimality of Theorem via three lower bounds: (I)
(Dn = ((w for all D; (2) an 2( pdpp) lower bound on the optimality ratio, and (3) that the condition n = ((vd))
d/p) p) is necessary.
The first lower bound follows from observation by Vadhan 35
Lemma 4 (35) ). For any f. any (E, 5)DP mechanism M', and any neighboring datasets Do Dr.
there is a b E (0, 1} such that
1+
< (D) [(Pi))la/2) < - -
I+e=t"
Theorem 4. For < 0.1, 5 < 0.1, Rin = ([w((D)w)))
The lower bound on the optimality ratio is by the reduction from statistical mean estimation [26].
Theorem 5. Let M be any p-zCDP mechanism for mean estimation that has l error c- c-w(D)/n with constant probability for any D = [xsbiee() drawn from [u]] If p < O( then e = Ω2 (((d/p))
For the lower bound on n, we consider a weaker problem (so the lower bound is stronger), which is the d-dimensional version of the interior point problem 9 Given a dataset D (2r))ie(n) drawn
from [ujd d the mechanism is only required to return a y E [u] such that min, Fij S yj max; Zij for all; j with constant probability.
Theorem 6. If there exists p-zCDP mechanism that solves the interior point problem with success probability 2/3, then Ω( (D(va /olog u)p)

---

Given a quantile selection mechanism with rank error by finding the median, the 1-dimensional interior point problem can be solved when n ( The following corollary then follows from Theorem 6
Corollary 1. Any p-zCDP mechanism for the quantile selection problem must have rank ervor O( (g u/p).
Extension to the Local Model and Shuffle Model
Our mean estimation framework be summarized as follows: (1) Given D { , Inh. perform a random rotation, obtaining D {á; H Jeinni i (2) For each E [d]. find an approximate median čj of 'D) along dimension j. Shift D to be centered around č, obtaining D = {²; := á - c}: (3) Find clipping threshold C, which is the m-th quantile over the & norms of the vectors in D. In the central model, the optimal choice m = - /2d/p: (4) Perform l2 clipping over D using C, and obtain mean estimator ý of the clipped vectors. Finally, return y (D - (1+ C).
We note that each step has their counterparts in the local and the shuffle model: Step (1) is easy, where the randomized diagonal matrix 1) can be generated using public randomness, or sent from the aggregator each user if public randomness is not available. Step (2) and (3) both rely on quantile selection, which have alternatives in the local model and shuffle model. Step (4) is also easy since all vectors have norms bounded by C. We elaborate on the details in the supplementary material.
The Local Model. For step (4), the standard LDP mechanism is that each user applies the Gaussian mechanism (Lemma I with GS = 2C inject noise to their clipped vector, sends it out, and the aggregator adds them up and divides the sum by n. For quantile selection in step (2) and (3), we use the LDP range counting protocol in [I3], which returns data structure such that any range counting query can be answered. Putting things together, we obtain the following result.
Theorem 7. Set t /n/p p log (du) log 3 and assume Q(Tvd). There is 3-round p-zCDP
du
mean estimation mechanism in the local model, achieving an Ez-error of ((/dn/p + T) T) log nd w(D)/n with probability 1-3. B.
The Shuffle Model. We see that the error in the local model is worse than that in the central model by a /n-factor. turns out that in the shuffle model, we can match the result in the central model up to logarithmic factors, albeit with (s, 8)-DP. This is mostly due to highly accurate summation and range counting protocols discovered recently for the shuffle model. We first extend the one-dimensional summation protocol in [5] for high- dighedimensional data by using random rotation.
Lemma 5. Given D = Jeen C Rd where ||æ/||2 S C for all i, there is one- round (E, (D mean estimation protocol in the shuffle model that returns a y such that
Pr [ly - f(D)ll2 s 0 en Vlog(nd) log / 2 2/3.
For the NoisyRC queries in the algorithm PrivQuant, we can use the range counting mechanism 24 in the shuffle model. Putting things together, we obtain the following result.
Theorem 8. Set
There is 3-round (s, 6D- mean estimation mechanism in the shuffle model, achieving l--error of o V dlog +T) Vlog(nd)) -w(D)/n with probability 2/3.
log'..5 1. (du) log dlog(du) and assume
T (TVd log
8
Experiments
We performed both statistical and empirical mean estimation experiments to evaluate our method.
For statistical mean estimation, we used multivariate Gaussian distributions with various μ and Σ. All algorithms are given the same ft amin. maxx We tried various R, while fixing amin 0.1 and maax R/ For empirical mean estimation, used real-world dataset, MNIST, which consists
7

---

COMPRESS:
CONTRESS:
BESS
EDOPPENSION
EDAIMANSION
CONPRESSE-4
CONPRESS
COBPTESS
DK Sxlee-ge
364
(a) /1 0 1a.
(b) 5 1a.
(c) 10 1d.
Figure 1: le enror vs. d for M(u, faxd), where 4000, 0.5, R 50vd.
Ranvevota
Romppivat
COMPRISS 1-12
CONVEESS
CM
p 0- 1d-
1r 10
Figure 2: Eg error vs. p for Nu,, laxa), where n 4000, d 128, = 50vd.
of 70,000 images of handwritten digits, where each image is represented by vector of dimension = 784 = 28 x 28. We quantized the values to integers [u] for u = 210 We measured the fg error by taking the trimmed mean with trimming parameter 0.1 over 100 trials (as in (8).
For the central model, we compared with COINPRESS S It starts with given confidence ball of radius R that captures the mean, and iteratively refines the confidence ball. The number of iterations t is an important internal parameter this algorithm; we tried 1, 3, 4, 10 following their suggestion.
Lapottan CDOPPENNION CONPRESSE-
CONFRESS
COBPRESS S1ELe-21
(c) 00) Figure 3: l2 enror vs. for (u, E), where Σ = diag([oi, ... R))), 4000, 0.5, R 50vd.
(a) 00 0.1 for E [d].
(b) oj 10.
The results for statistical mean estimation are shown in Fig. settings are given the captions. The results show that our method (Shifted-CM) performs least as well as COINPRESS with the best / across variety of settings. In particular, when Σ is not identity Laxa: our method significantly outperforms COINPRESS and offers errors close to the non non-private estimator as demonstrated in Fig. and Fig. 4 Moreover, seen from Fig. 3 and 5 the best choice of for COINPRESS is quite sensitive to and R, making it difficult to tune in practice.
where the detailed parameter
We also compared with another version of COINPRESS in the supplementary material, where we first scale the data estimated 2 (obtained by MVCRec g using half of the privacy budget p).

---

OORTESS:
DA SUNRE
COMPECSE
CONMTESS
20
CONFEESS
CONMIESS
COMPRNSLINTE
CORVTESS
WETHARM
(a) 03 0.1 for E [d].
0) for all j [d]
(c) (c) 10]
Figure 4: Eg emror p for (H, Σ), where E diag( ([o 02 50
23) 4000, d 128, R
CONMEESC CORTAANO CONMESSS 2FTE5-O NaTErROe
COMPEISE
CHINSSOO
4,402
prodle
pridde
(a) p 1a.
(b) μr 1d.
(c) (1 10 1a.
Figure 5: l2 error vs. for (p, 2). where diag(Lof 02. ...... .03) and of Muar [0, 10] for
each j [d]. 4000, 0.5, d 128.
Both method and COINPRESS are translation-invariint. This can be verified from Fig. 1 and 5 where the results are not effected by μ. However, the approaches taken are different: COIMPRESS iterative process, while shift the dataset be centered around approximate center point. In Fig. [ (ann]] [ we also include CM, our estimator without this shift operation, which is indeed affected by μ..
CORTRANN
30
Colleroon 1o
300
369
(a) digit O.
(b) digit 1.
(c) digit 2.
Figure 6: error vs. p for various digits in MNIST, where d = 784, R 50vd.
For empirical mean estimation on the MNIST dataset, we see in Fig. that our method outperforms COINPRESS for various privacy levels. This means that this dataset, as with most real-world datasets, does not follow Gaussian distribution with an identity Σ. The instance-optimality of our method is precisely the reason behind its robustness to different distributional assumptions, or the lack of.
One important component of our method is the optimal clipping threshold C, which is the (n /2d/p) p)-th quantile of the norms. Note that this depends on d and Prior work [3] used fixed quantile (e.g., the median). To better see the relationship between the optimal C' and d, p. we used synthetic dataset D {i Lx)iejn with 500 and tried different quantiles as the clipping threshold. The results in Fig. 7 confirm our theoretical analysis: The optimal C indeed depends on and p, while our choice attains the optimum.

---

20
5.7
50h
85%
(a) p 0.1.
(b) p 0.5.
p=)
Figure 7: &2 error vs. for clipping at various quantiles of the norms on synthetic dataset.
We also evaluated our algorithm in the local model and compare it with 23 and the results are presented in the supplementary material.
Acknowledgments and Disclosure of Funding
We would like to thank Gautam Kamath and Jonathan Ullman for helpful discussions about Coin- Press g
Funding in direct support of this work: This work is supported by HKRGC under grants 16201318, 16201819, and 16205420.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. Bounding user contribu- tions: bias-variance trade-off in differential privacy. International Conference on Machine Learning, pages 263-271. PMLR, 2019.
[3] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. arXiv preprint arXiv: wwXiv:1905.08877 2019.
[4] Hilal Asi and John C Duchi. Instance-optimalle in diffcrential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems, 33, 2020.
[5] Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. Private summation in the multi- message shuffle model. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657-676, 2020.
[6] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinct histograms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 127-135, 2015.
[7] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Pro- tection against reconstruction and its applications in private federated learning, arXiv preprint 1rXiv:1812.00994 2018.
[8] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural and Information Processing Systems, 2020.
[9] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634-649, IEEE, 2015.
10

---

[10] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. Theory of Cryptography Conference, pages 635-655--6665 Springer. 2016.
[11] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions Information and System Security, 2011.
[12] TH Hubert Chan, Elaine Shi, and Dawn Song. Optimal lower bound for differentially private multi-party aggregation. In European Symposium on Algorithms, pages 277-288. Springer, 2012.
[13] Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proceedings of the VLDB Endowment, 12(10): 126-1166611 138, 2019.
[14] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005.
[15] Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction. In International Conference on Learning Representations, 2021.
[16] Apple Differential Privacy Team.
Learning with privacy scale.
https
/machineleearning.aaap www.:aapplllccceeeeee pdf] December 2017.
[17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In NIPS, 2017.
[18] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pages 1161-1191. PMLR, 2019.
[19] John C Duchi, Michael I Jordan, and Martin Wainwright, Local privacy, data processing inequalities, and minimax rates, arXiv preprint arXiv: 2013.
[20] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N Rothblum. Pure differential privacy for rectangle queries via private partitions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 735-751. Springer, 2015.
[21] Cynthia Dwork. Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):21 1--777, 2014.
[22] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preseriing ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[23] Marco Gaboardi, Ryan Rogers, and Or Sheffet. Locally private mean estimation: 2-test and tight confidence intervals. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2545-2554. PMLR, 2019.
[24] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages. In EuroCRYPT, 2021.
[25] Anna Gilbert, Yannis Kotidis, S Muthukrishnan, and Martin Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In VLDB '0: Proceedings of the 28th
International Conference on Very Large Databases, pages 454-465. Elsevier, 2002.
[26] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, pages 1853-1902 PMLR, 2019.
[27] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages 2204-2235. PMLR, 2020.
[28] Gautam Kamath and Jonathan Ullman. primer on private statisties. 00X0v 2020.
arXiv preprint

---

[29] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl- Leibniz-7Zentrum fuer Informatik, 2018.
[30] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. arXiv preprint arXiv:2102.11844 2021.
[31] Andrew McGregor, llya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan. The limits of two-party differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 81-90. IEEE, 2010.
[32] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:
2017.
[33] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium Theory of computing, pages 75-84, 2007.
[34] Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank J Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv: 07643, 2019.
[35] Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347-450. Springer, 2017.
12


Reviews:
[{"review_id": "uamOMhAqmNo", "reviewer": "Reviewer_Lthh", "summary": "This paper considers the problem of private mean estimation and attempts to develop algorithms that are instance-optimal, that is, adapting to the difficulty of the underlying instance. The authors modify the existing instance-optimality definition in differential privacy, and develop an algorithm that is nearly instance-optimal. The caveat here is that nearly instance-optimal here hides factors that depend on the dimension and privacy parameters, hence making the optimality guarantee less strong than what claimed by the authors.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has two main contributions: first, a new definition of instance optimality, and second a new algorithm for mean estimation that satisfies this definition of instance-optimality. I think the algorithm is nice and the experiments show some advantages in practice (although more experiments are needed; see below). However, I don't think the instance-optimality guarantees are strong enough as they hide a factor of c=\\sqrt{d}/epsilon where d is the dimension. Hence it is misleading to say the algorithm enjoys strong instance-optimality guarantees when there is a sub-optimality factor of \\sqrt{d}/epsilon, which are important problem parameters. More detailed comments below.\n\n1. Instance-optimality: one of my main concerns about this paper is the fact that the algorithms are not really instance-optimal, having a sub-optimal factor of \\sqrt{d}/epsilon which is an artifact of the way the authors define instance-optimality. Therefore I would first suggest the authors to clarify this in the paper. However, this doesn't rule out the possibility that the algorithm is really instance-optimal. It would help strengthen the paper if the authors show strong instance-optimality guarantees (up to constant factors) even in the 1-dimensional setting (using for example the instance-optimality notion of local minimax based on the hardest alternative of [1]). This will at least show that the algorithm has an instance-optimal dependence on the privacy parameter.\n\n2. Clarity: overall the paper could use more work to make it more easily readable, especially in describing the algorithms; the authors currently write the algorithms in a standard text paragraph and I strongly recommend write them in the standard way as most papers do (in a box with pseudocode).\n\n3. Binary search algorithm: the binary search algorithm may be losing a little because of it's iterative nature and a possible candidate here is the exponential mechanism\\inverse sensitivity mechanism for quantiles [1,4].\n\n4. Bound for Gaussian mean estimation: I like the bound for Gaussian mean estimation in corollary 1 in the appendix and I would recommend to have it in the main paper too as it shows some adaptivity to the covariance matrix. Some of the experiments were unnecessary and this bound can be added instead.\n\n5. Experiments:  first, I suggest checking larger values of epsilon in the experiments to verify the same results hold in the low privacy regime. Moreover, the algorithms seems to have good performance in practice and so it is worth trying it with different applications of mean estimation such as DP-SGD. Finally, following on the comment above for instance-optimality at least in 1-dimensional setting, I recommend doing a 1-dimensional experiment in a similar setting to [3] and compare to the following baselines: the trimmed mean algorithm of [3] and the inverse sensitivity algorithm as in [2]. \n\n\n\nReferences\n\n[1] Hilal Asi, John Duchi, Near Instance-Optimality in Differential Privacy, arXiv 2020 \n\n[2] Hilal Asi, John Duchi, Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms, Neurips 2020 \n\n[3] Mark Bun, Thomas Steinke, Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation, Neurips 2019\n\n[4] Jorg Drechsler et al., Non-parametric Differentially Private Confidence Intervals for the Median, arXiv, 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "eiD0lPpoDAe", "reviewer": "Reviewer_tbe2", "summary": "This paper does differentially private mean estimation for empirical estimation, as opposed to statistical estimation (statistical estimation is an application of their work). It focusses on instance optimal mean estimation by introducing a new target error function of the dataset, $\\mathcal{R}_{\\text{in-nbr}}$. It shows both and upper bound and a lower bound for this problem. It has both theoretical and empirical results.\n\nThe theoretical results say that for this measure of error, the optimal error scales according to the diameter of the dataset in question. To prove the upper bound, the authors first use a clipped-mean-estimator, with the clipping threshold decided via a simple derivative of the error. Since that clipping estimate is a function of the dataset, it could not be used directly. So, they came up with a simple quantile estimator to do the same. They, however, first performed a random rotation, followed by a translation to fix scaling issues. Then they finally use the aforementioned clipped-mean-estimator.\n\nThey finally showed application in statistical mean estimation of high-dimensional Gaussians. They showed that they require very weak prior knowledge of the covariance matrix of the Gaussian for this. They finally compared their empirical results with the Coinpress algorithm of Biswas et al.\n\nThey extend these results to the local and shuffle models of DP, too.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update: Edited my final evaluation based on the authors' comments.\n\nStrengths:\n1. The paper has enough theory to support their claims, and enough empirical results on both real and synthetic datasets to verify the validity.\n2. They achieve optimal error rates under their notion of error.\n3. They achieve the same error for statistical mean estimation of high-dimensional Gaussians as Coinpress [Biswas et al.].\n4. Their experimental results show that their algorithm works as well as (and in some instances, better than) Coinpress for a wide range of parameters. This is true for real datasets, too. So, their algorithms seem practical, just in terms of the error.\n5. They also extend their results to the stricter models of differential privacy: local and shuffle models.\n\nWeaknesses:\n1. I don't understand why their error metric is the \"right choice\" for instance-optimal mean estimation. Like their algorithm implies good results for statistical mean estimation, but the metric looks a bit contrived. I didn't see any justification in their paper about this.\n2. Regarding the choice of their error metric and the optimal error. The optimal error scales with the diameter of the dataset, which could well be $u\\sqrt{d}$. Unless I'm missing something, this means that if most vectors in the dataset are \"close to\" $(0,\\dots,0)$, and there is one anomaly of $(u,\\dots,u)$, then the error would be pretty bad. It would be the same as adding noise scaled to the global sensitivity. So, how are they avoiding adding large amounts of noise here?\n3. The choice of colours in the graphs is quite poor, which makes them hard to understand. Squinting too much while reading a paper is never pleasant.\n4. It's nice that they were honest in the checklist, but the paper writing doesn't totally adhere to the prescribed format. Like they didn't discuss the limitations of their work. Is this because they were unaware of them? No code was provided either, so I'm just supposed to \"trust their results\" regardless of whether I want to run their code or not.\n5. I wish they had reported the running times in their experiments, and compared with the state-of-the-art algorithms. It's hard to say how practical their work is without it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Although the authors did not discuss any of this, I feel that there shouldn't be any negative impact of this work. This is a standard type of work in differential privacy literature, which can only be useful, if not harmful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Lw_rQqA2mz", "reviewer": "Reviewer_K1K1", "summary": "The paper proposes a new algorithm for the mean estimation problem that gets around the \"curse of global sensitivity\" and achieves the so-called instance optimality. Experiments including a real-data one are carried out to verify the practicality. The results are also extended to the shuffle and local models of DP.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is always exciting to see that new DP algorithms can get around global sensitivity and most importantly, it works in practice and improves on previous algorithms.\n\nI have one philosophical and one rigorousness/correctness criticism. Beginning with the philosophical one, the idea is that the error is a function of the dataset $D$, so why not compare it to something also depends on $D$. I agree with everything so far. My question is, why does comparing to the so-called \"in-neighbors\" make more sense than comparing to the diameter. The only appearance of the in-nbr after the introduction is to explain how it must be larger than the diameter. So it seems to me than in-nbr is just a story after the authors have the results regarding the diameter, which in my opinion is not more convincing than the diameter story.\n\nPutting aside the philosophy, the in-nbr \"shell\" story may have some correctness issue. The main upper and lower bound seem to be Theorem 3 and 5 respectively. However, they are all stated in terms of the diameter. The statement about in-nbr is only partially supported by a one-sided inequality (Theorem 4). If in-nbr is much smaller than the diameter, then does your algorithm provide any guarantee w.r.t. in-nbr?\n\nIn my opinion, if the in-nbr thing is removed from the main story and treated as a potentially interesting connection, the paper is more correct and makes more sense.\n\nRegarding the experiments, why not compare with other works in the line of \"beyond global sensitivity\"? Is coinpress the absolute best so far? More importantly, all the figures miss the comparison with the diameter $w(D)$, which is the main result. From the proof (if I understand correctly) for some specific non-Gaussian data (e.g. MNIST), the optimal factor can actually be smaller than the lower bound. If that's true, I wonder how much smaller the optimal factor can be.\n\nOverall, I think it is a good and solid paper. However, I'd like to hear the explanation especially regarding the correctness issue before the final decision.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "BMaIOVzL8nl", "reviewer": "Reviewer_aNGi", "summary": "The paper studies instance-optimal mean estimation in the central model of differential privacy, with straightforward extensions to the shuffle and local models. The specific notion of instance optimality used is, I believe, original to this paper: the goal is to find an algorithm minimizing error over a given database D and a restricted neighborhood of databases that are neighbors and only include elements also present in D. The algorithm consists of four steps:\n\n1) randomly rotate the database,\n2) center it using a privately estimated component-wise median,\n3) privately estimate a certain quantile of the L_2 norm of the resulting database and clip data to that estimated L_2 norm,\n4) take a noisy empirical mean of the clipped data and de-bias.\n\nThe paper gives instance-specific upper and lower bounds that are nearly matching, up to logarithmic factors in the dimension and a discretization parameter. Experiments suggest that the algorithm performs well against existing methods.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "—Originality— \n\nThe most original theoretical component of the work might be its restricted-support definition of instance optimality. I don’t think I’ve seen that anywhere else. The algorithmic contributions are largely combinations of methods that have appeared elsewhere in the literature. \n\nTwo specific comments:\n1) The discussion of other papers about the clipped mean estimator in the related work section is not quite accurate. For example, the Amin et al. paper not only uses a quantile as the clipping norm, but attempts to select an optimal one (not the median). Their setting is certainly different, since they are attempting to bound the number of contributions, not clip the actual samples, but the idea of truncating using an optimal quantile is there.\n2) It would be interesting to see how a different private quantile algorithm affects the experimental results. As far as I know, the empirically strongest private quantile algorithms are based on the exponential mechanism (http://cs-people.bu.edu/ads22/pubs/2011/stoc194-smith.pdf, Algorithm 2), not binary search.\n\n—Quality— \n\nI did not check the proofs, but the algorithms and results seem believable, and proofs appear to be given when appropriate.\n\nOne omission: the submission does not provide any experimental code. Since I think the experiments are one of this paper’s strong point, the lack of code is disappointing.\n\n—Clarity— \n\nIn general, the paper is well-written and easy to follow. \n\nSome exceptions:\n1) The initial presentation of the algorithm (erroneously, if I understand correctly) makes it sound like the L_2 clipping step is the first step of the algorithm. It wasn’t until I got to the section about local privacy that I realized I had it backward.\n2) I think the lower bound section is missing a final statement that actually puts the separate lemmas together.\n3) The experiment plots are hard to read. For example, the lines for Coinpress t= 4 and t = 10 are indistinguishable to me. Maybe make the lines thicker, or put some of these plots in the Appendix.\n4) As far as I can tell, the main version of the paper doesn’t explain what the point of the random rotation step is. Some explanation appears in the proof of Theorem 3. I think this intuition should be more prominent.\n\n—Significance— \n\nTo me, the strongest point of this paper is that the proposed algorithm, according to the experiments, achieves better results than the existing state of the art with fewer parameters to tune, and a pretty simple algorithm overall. I think the choice of things like clipping norms is a bit of a blind spot in the existing DP literature, so it’s good to see an application to a basic problem like mean estimation — it’s actually plausible that people would implement something like this in practice. The optimality result is also nice, though the proposed notion R_{in-nbr} does seem a little too restrictive to attach that much importance to it.\n\nThat said, the omission of experiment code and the criticisms above keep me from recommending the paper too highly. However, both of those things are fixable, and I look forward to the discussion period.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper flatly refuses to discuss potential negative societal impact. But that doesn't seem too unreasonable for something this abstract. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a fundamental problem in the differential privacy literature, namely mean estimation. It presents a novel algorithm and accompanies this with a theoretical and experimental evaluation. The reviewers all appreciate these contributions as valuable and worth accepting.

There are some reservations about the clarity of the paper. In particular, the algorithm is not clearly explained and the instance optimality claim hides a significant gap between the upper and lower bounds. Hopefully, these presentation issues can be resolved in the camera ready revision.
Decision: Accept (Poster)