Anonymized Histograms in Intermediate Privacy Models
Authors: Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
shuffle DP
pan privacy
anonymized histograms

Abstract: We study the problem of  privately computing the $\mbox{\it anonymized histogram}$ (a.k.a. $\mbox{\it unattributed histogram}$), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP).

In this work, we provide an algorithm with a nearly matching error guarantee of $\widetilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram!  Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.


Anonymized Histograms in Intermediate Privacy Models
Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Google Research Mountain View, CA, US
Madihghazi@gmaill com, pritish@alum mitt edu, ravi. Syrikk53@mmall. com, pasinggoogle com
Abstract
We study the problem of privately computing the anonymized histogram (a.k.a. unaltributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with f and lz -eerrors of Oz(yn) in the central model of differential privacy (DP).
In this work, we provide an algorithm with a nearly matching error guarantee of Ō=(vn) in the shuffle DP and pan- bun-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.
1 Introduction
Computing histograms is among the most well-studied tasks in data analytics and machine learning.
Suppose that there is a domain [D] == (1..... D), where the ith user's input 2 [D]. The histogram of the users' inputs f.i....,
is defined as h == (hi....,hp hp) where h5 == (i E [n] 2; = ..l. i.e., the number of users who contribute item j E [D]. For many tasks, however, the differ- ent items themselves are not important and it instead suffices to consider the anonymized histogram (a.k.a. unattributed histogram) corresponding to h, which is defined as == (n."))....n where (8) denotes the Åth largest element among the hy 's. Whenever h is clear from context, we will skip the subscript and denote the anonymized histogram as simply n..
n (D)
Anonymized histograms have several applications including estimating symmetric properties dis- crete distributions [11, 2, 16, 31]. privately releasing the degree-distribute in social networks [34, 33, 40], and anonymizing password frequency lists [13, 14]. For more details, we refer the reader [44] and the references therein.
In this work, we study private anonymized histograms. The notion of privacy we study differential privacy (DP) [24, 23], which has emerged very popular notion of private data analysis leading to numerous practical deployments [27, 43, 30, 8, 21, 1, 36, 41].
Multiple works have studied the problem of computing private anonymized histogram, with the focus so far being on the central model of DP. Moreover, two measures of error have been stud- ied: E error and fz-error" For the Eg-error case, Hay et al. [34] give an c-DP algorithm with
'I the central model of DP. trusted curator has access the raw inputs of the users, and is supposed output DP estimate of the desired function, in this case, the anonymized histogram.
Defined as n A/ Σ}e(p) (n | and || All Eyepp((n (n 000), where ñ denotes
the output anonymized histogram.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

an expected error of ((Vn/E?)). As for the f1-error, Blocki et al. [13] observed that the expo- nential mechanism yields an expected eerrro of O(vn/E) since there are at most exp(O(vn)) anonymized histograms in total [32]; recently, this bound was improved to O( O(v /n log(1/s)/e) by Suresh [44]. On the lower bound front, Alda and Simon [5] proved a bound of 52( ([V/2/ ///E) for the expected fi-error; recently, this was improved to 2 ( (og((/))/E) by Manurangsi [37], matching the aforementioned upper bound of [44] to within a constant factor. The latter lower bound also applies (e, 6DP algorithms for any sufficiently small 6 (depending only on e).
The anonymized histogram problem generalizes the COUNT-DISTINCE problem, which asks for the number of items j such that h2 O. COUNT-DISTINCT can be easily solved in the central DP model by applying the discrete Laplace mechanism. In the nonniiteraactiv) local DP setting, Chen et al. [17] proved a lower bound of S2g (n). which means that one cannot asymptotically beat the trivial algorithm that always outputs zero The strong lower bounds on the error incurred by protocols in the local setting generally motivate the study of intermediate models of privacy including the pan- private [25] and shuffle DP [12, 26, 18] models. In these models, it turns out that SOUNT-DISTING can be solved to within O₂ (z))) -error while lower bounds of 22 (2())) are known [38, 9].
In this work, show that, surprisingly, the anonymized histogram problem (which seems much harder than COUNT-DISTINCH can in fact be solved with essentially the same asymptotic error of (v() as the aforementioned lower bound [17] for COUNT-DISTINC" also implies an S2g (n) lower bound for the expected & é1-error of anonymized histogram in the more challenging local DP model. In other words, in the typical case where & an absolute constant, it impossible achieve any asymptotic advantage over the trivial algorithm that always outputs the all-zeros histogram.
in both the pan-private and shuffle DP models. On the other hand,
1.1 Our Results
A prominent approach for computing private histograms in the central DP model is add discrete Laplace noise to each histogram entry. We show that there is a post-processing algorithm that takes such a noised histogram and produces accurate estimate of the anonymized histogram:
Theorem (Informal; Theorems 9 and 21). There is an algorithm that takes in noisy histogram, where an independent discrete Laplace noise of parameter 1/8 is added to each entry, and outputs an approximate anonymized histogram such that the expected E1- and l-errors are ÖelVn+ D).
Note that there is dependency of vD in the error bound in Theorem 1; when the domain size large. this can dominate the vnn term. Fortunately, we show that this can be overcome by first randomly hashing into B buckets before computing the histogram. By picking B to be O(n), we show that one can achieve error that is (z(vn) without any dependency on D:
Theorem 2 (Informal; Corollary 13 and Theorem 22). There is an algorithm that takes in a noisy hashed histogram, where an independent discrete Laplace noise of parameter 1/e added to each bucket after hashing, and outputs an approximate anonymized histogram such that the expected E1- error is Öz(vn) A similar algorithm holds, which uses two noisy hashed histograms and achieves expected ez-error of (v(T)
Random hashing and computing discrete Laplace-noised histograms can be implemented in the pan- private and shuffle DP settings [29, 10], where in the latter case we have concede 8 > in the privacy parameter. Thus, the theorem above yields:
Corollary 3. For any E > 0, E 10. there is an e-DP algorithm for anonymized histogram in the pan- pan-private model and an (E, (D algorithm in the shuffle DP model, with expected E1- and f2-ervors of Ō.(n)).
'In fact, Hay et al. [34] proved a slightly stronger expected error bound of Old n/e?), where d denotes the number of unique values appcaring in n. Since there are at most vn different values in the worst case, this guarantee yiclds an Ol log" n/=²) bound for any instance.
*Our results can be adapted to continuous Laplace noise [24] with only constant factor overhead in the error. We use discrete noise since it can be applicd in the shuffic DP model (which is discrete in nature).
$ $Ō(f) denotes Of log f) for some constant > 0 and (f( denotes (f)(=))) for some function 9(-). 'This is done by starting with D i.i.d. discrete Laplace r.v.'s and incrementing each entry for the next item.

---

As an immediate application of the above. we get algorithms for estimating symmetric properties of distributions; a distribution property is said to be symmetric if it remains unchanged under relabeling of the domain symbols. For any (non-private) symmetric estimator with low sensitivity, we get private estimator in the pan-private and shuffle DP models.
Theorem (Informal; Theorem 17). For all E 0, (0.1), and distributions D. for any symmet- ric distribution property f. and any symmetric estimator f. there exists an e-DP mechanism M in the pan-private model and an (e, 8D-DP mechanism M in the shuffle DP model, such that M out- puts an d a-approximation to f(D) with high probabiliry. The sample complexity of the mechanism M is given as Cj(f, a.) + Dj (a E). where the first term is the non-private sample complexity of f and the second term depends on the sensitivity of
In particular, in Section 5, we apply the above result estimate the Shannon entropy, support coverage, and support size of discrete distributions, which, to the best of our knowledge, is the first such sample complexity bound in the pan-private and shuffle DP models.
1.2 Overview of Techniques
We now describe the high-level ideas of our algorithms and proofs. For ease of exposition, we will occasionally be informal; all details are formalized later sections. To describe our algorithm, we need definitions of prevalence and cumulative prevalence.
Definition 5 (Prevalence and Cumulative Prevalence). The prevalence of a histogram h is defined
as . := (yf...., (hhi), where - := Ifj E [D] : h2 = rr} is the number of entries with value r. The cunulative prevalence of a histogram h is defined as sp := ( (111..... (n) where 2
Hi E [D] h2 2 r}] is the number of entries with value least r.
Prevalence and cumulative prevalence can be similarly defined for an anonymized histogram n; note that - = n and _ = "0 An important property of cumulative prevalence is that it preserves the -ddistance.
Observation For all anonymized histograms n, n, holds that 1|<2
2
|n All
We stress that, while cumulative prevalence has been used before in DP algorithms for computing anonymized histograms [44, 37], these algorithms require access to the true anonymized histogram first and therefore will only work in the central DP model.
Algorithm for L -erorr. For each j E [D], using the discrete Laplace-noised count, we produce an unbiased estimate for whether h 2 for each r [n]. Adding these up over all j E [D] gives an unbiased estimate for p We then "project" the estimated y2 back that it corresponds to valid anonymized histogram. It can be seen that this last step can at most double the error.
While the algorithm described above is simple, it is unclear why it incurs an error of Ōe(vn + D)- The analysis turns out to be quite delicate. The key is that the unbiased estimator we use has variance that decreases exponentially with 1h, - r|. (In other words, the uncertainty is high only when hy is close r.) Roughly speaking, this means that the total error is dominated by the error in the case where hy = r. Suppose for simplicity that we only focus on this case. Since there are of entries satisfying the condition, the expected fi-error for 42r will be (e(V)))) Thus, in total, the l eerrrr of the estimated cumulative prevalence is dominated by (r(ErE))) //f). We can now apply the Sacchy-Schwarz incquality to yield Ere(n) VPD S VEre(n) 1/r V /Eretm) r s
((yn logn), n). where the last equality follows from the fact that Erejy) r pp simply the total counts in the histogram. This concludes our proof sketch. The full proof can be found in Section 3.
Handling Large Domain Sizes. When D > n, we randomly hash into B = =Ō(n) buckets and compute the noisy "reduced" histogram these B buckets. We can use our approach above to compute the anonymized histogram on these B buckets with errrro most (v(7). While this is a reasonable approach, it does not yet give a good estimate for the original anonymized histogram: the reason is that there could be many as ②(n) collisions due to hashing. To handle this,
3

---

define a function that "inverts" the reduced anonymized histogram to the original anonymized his- togram. We then show that (i) this inverse has constant "sensitivity" and (ii) the reduced histogram concentrated around its mean with an diddviition of Ō(vn). Combining these two allows us to conclude that the inverse of the noisy anonymized histogram has expected fi-error of (e(vn) as desired. See Section 4 for details.
Privately Computing Symmetric Properties of Distributions. A large body of work starting with [2] has shown that plug-in estimators using the so-called profile maximum likelihood (PML) distribution achieve nearly optimal sample complexity for many symmetric distribution properties. At the core of these works is an important fact that many symmetric distribution properties have estimators (based on the anonymized histogram) with low sensitivity. Our algorithms then apply these estimators on our private anonymized histogram. The sensitivity of the estimator, together with the & error bound we have shown for our anonymized histogram, immediately yield bounds on the errors of the estimators. See Section for details.
Algorithm for fz-error. Adapting the algorithm for -e-error proceeds as follows: recall (e.g., by Hölder's inequality) that ||n 2 < || All1 ||m flll Notice also that the concentration of the noise implies that each discrete Laplace-noid noised count is within Olog D/s) of the true value. may only change the last (i.e., "projection") step by adding extra constraint that
Due to this, each entry of the output estimated anonymized histogram is within (log D/s) of the corresponding entry of the noisy histogram. This way have ensured that |ln no Olog D/E). Combining this with our earlier bound on the expected & error immediately yields the desired bound on the l2 error. See Appendix B for details.
1.3 Other Related Work
The original paper on the pan-private model [25] also studies the problem estimating sp How- ever, their focus is on algorithms with small space complexity, and, if one were to sum up their error bounds for all r directly, it would yield a trivial bound ((n) on the total error in the anonymized histogram.
Several recent works have studied the testing/estimation/laaniii of symmetric and other properties
of distributions under privacy constraints, mostly in the central DP model [3, 4, 6, 15, 20, 35] and some in the local DP model [22]. particular, Acharya et al. [3] study privately computing symmet- ric distribution properties in the central model. Indeed, they also exploit the fact that the estimators have low sensitivity. However, in the central DP model, low sensitivity allows one to get a private estimate by adding Laplace noise directly to the non-private estimate, whereas we need to compute the estimator from our approximate anonymized histogram.
2 Differential Privacy
In this section, we review the basics of differential privacy (DP) and the shuffle DP and the pan- private models. Let [n] denote the set {1,..., n. and let 1 denote the binary indicator function.
Two datasets S {......, 2n and S' {2/,..... 2 are said to be neighboring. denoted S ~ S', there is an index i E [n] such that 2j = 2/ for all j E [n]] \ (i}. We recall the following definition [24, 23]:
Definition 7 (Differential Privacy (DP)). Let & > 0 and 8 E [0, A randomized algorithm M 2n - R is (c, -idiffferentt private (), if, for all S ~ S" and all (measurable) outcomes E C R, we have that Pr[M(S) E] I ef Pr(M(S') E E] 8.
We denote (c, DP as DD or pure-DP. The case when > 0 is referred to as approximate-DB
In the central DP model, all the inputs are stored and processed by an analyzer and the privacy is enforced only on the output of the analyzer.
Shuffle DP [12, 26, 18). In the shuffle DP model, there are three algorithms, namely, a local randomizer R. shuffler S, and an analyzer A. Let = {=I....; )n} be the input dataset. The randomizer R takes S input and outputs multiset of messages. The shuffler S takes the

---

multiset of messages obtained from R applied to each 2 E S and permutes them randomly. The analyzer A takes this permuted multiset and computes the final output. The privacy the shuffle model is enforced on the output of the shuffler S, when single input is changed.
Pan-privacy [25]. In the pan-private model, there is an algorithm that takes in data stream of unbounded length consisting of elements in the domain. It is required that the internal state of the algorithm after any number of steps satisfies s-DP over the data stream prefix until that step.
We consider two data streams to be neighboring iff they differ by a single entry. This is sometimes referred as the "event-level" or "record-level" setting [7], in contrast to the "user-level" setting that was the focus of the original work on pan-privacy [25]. We remark that the "user-level" setting is not appropriate for our notions of error as it allows for changing an entry of the histogram arbitrarily,, meaning that we cannot achieve any non-trivial error guarantees. Furthermore, our definition above (which allows origin definition in [25], because the latter requires that revealing both the internal state and the final output simultaneously DP. Nonetheless, our algorithm can be easily adapted for this more restricted model, but with a worse dependency on e. We explain this in more detail in Appendix E.
directly implement discrete Laplace-noised histogram) is different from the
Histograms in Central DP. For distribution D, let D denote that the random variable x is chosen from D. For p E (0, 1), the discrete Laplace distribution (aka symmetric geometric distribution), denoted by DLap(p), is the distribution supported on Z whose probability mass at i E Z is
1-p Ltp plil.
We use the following well-known fact about central DP and histograms.
Fact 8. The algorithm that adds DTap(e-s/2) noise to each entry of a histogram is e-DP in the central model.
We refer the output of this algorithm as the discrete Laplace histogram.
For histogram h, we use n&p to denote the anonymized histogram corresponding to h, often drop- ping the subscript whenever h is clear from context.
3 Post-Processing Noised Histogram
In this section we describe our main algorithm, which obtains an anonymized histogram by suitably post-processing noised histogram. We first define the following function ʃ Z - IR, which is used our post-processing method described Algorithm 1.
if m > 0,
+
if m 0,
f(m)
(1-p)²
(1)
if m = -1,
if m -1.
Algorithm Anonymized Histogram Estimator w.r.t. loss.
Input: Discrete Laplace-noises histogram h', i.e., h2 ~ hy + DLap(p)
for r E [n]] do 62r + EjE() f(h/- - r), where f is defined in (1)
return f that minimizes l|p2 221111
We give efficient implementation of the above algorithm in Algorithm 5 (Appendix D.1), which runs in time O(D + n n.). The main idea is to compute ñ that minimizes l1y0 Φ2111 using -isoooni regression. We now state the main guarantee of the post-proe processicsnng method. Theorem 9. For all histograms h with |//l n, the estimate ñ returned by Algorithm I satisfies
E Ell 7 [a] < o (VCp(n - D)
where, Cp == [I-p]s
22 + p-p
5

---

From Fact 8, for E-D,, we may set e- Olv(n (n + D) log / on the expected f-error.
Theorem 9 then gives a bound of
The erucial result needed in analysis is the guarantee of the individual estimator f. We show that f(h; r) is an unbiased estimator of [bg 2 r] and furthermore its variance decreases (expo- nentially) as 1/g - r| increases.
Lemma 10. For all h, r E EU [0). if ~ DLap(p), then it holds that Ejj(h' - r)] = 1 2 r],
and
(2)
Varls(N' -r)] S 4p1i-n|+1
P [-- + (1--1)
(3)
Proof. Let h- r, and p/(1 - - Consider 9 Z + R defined by
g(m) == f(m) 1/2.. Notice that (2) is equivalent to B[g(T')] = 1/r 2 0] 1/2. Due to symmetry,
suffices to consider the case where т 2 In this case, we have
Elg(r')] Ez- + 2 Pr|Z -1| (1/2) Pr|Z < - Z) Z 2 -r].
The last term can be expanded as follows:
[ 2) Z 5
= =1/2++ - = - 2 - -
< -1//2
(1/2) - 1
- (1- x) p(1 -p) -1122) 1
Combining the two equations above, arrive Big(T')] Pr[Z -7] (1/2) + Pr|Z s
-T] (1/2)-11/3 1/2, thereby proving (2).
To prove (3), notice again that Var[s(r')] Varlg(T')). Again, due to symmetry, we may only consider the case + 2 Here, we have
Varlg(r))] B2-DLaptolu((+ - 1/2)
= Pr(Z - - + 7) - 1/2)² 2 S -T]
S p"
- -r].
Similar to before, we can expand the last term as
El(o(T + 2) - 1/2)
-T]
- 2 -T] (1) Pr|Z = - 1/25 -T]
+1 +1.Pr[Z <
= (1
+p²
21 +11(1+++) +x²) .
p(1 - -p) p2
S 4p2 /01/(11p)) + +2p[1 - -p) p).
Plugging this into the above, we get Varlg(r')] < (p/(111/(1111)) (1- (1 (1 (1-p)) -p)) as desired.
The following an immediate consequence of Lemma 10, by summing over all j [D].
Observation 11. For all r E [m], and x == 4p (1 (1-p)a + (1 p)) it holds that
B|pzr| p and Varl s Ei N- pelor--pe-rl ple-rl 47
Proof of Theorem 9. The expected e eerrro is bounded as
|| n2/1 =1103 222l11 I 11 22111 +112 -18111 S 2. 11 -2111
| n||1 5 2. Ere 1r2, $2rl,
(4)

---

where we use that 11 -2212111 S 21 -4 by our choice of ÿ. From Observation 11, we have
E [1 - P2rl s V /arllezr s Vn. VE ploople-r.... 4
Combining this with (4), we have
B| n//1a] _ Eme 1102 - -22r11
S R/R. (Ere(n) Ee=o Pi=ople-r..0
S 2/R Vire(n)+
Ere(N)) T (Ezople-1 v7t
(Cauchy-Schwarz)
VK. OVVlgg
Er (Ereln) r. pple-r)
VF. O(Vlo(oll)))
Ei=o 2(((+1)) (1==((++1)
VK-O(vio Ooolo(vlogg Ei pp: 22( (1/(1-
VE/(1 - p)3
(Vllgg)) V[E l. (()) + (Eizo (8)
(5/(1-1) pill-pp0//oo011 vn D.
4 Reducing Domain Size via Hashing
In this section we propose an algorithm to handle the case where >> n. The approach this case is to hash the domain into something smaller. Let B N be the number of hash values. The distribution of the anonymized histogram produced after random hashing into B buckets is equivalent to the following process:
Let n = (n())...,, (P)) be the starting anonymized histogram.
Pick uniformly random hash function H [D] + [B]
Let hed (hiad ...., red) denote the reduced histogram given by hited Ejen-
Let red denote the corresponding anonymized histogram.
Let _ be the mapping from n to Elyp% "od
where n is generated as above, and the expectation over the choice of random hash functions H. With this notation, we present Algorithm 2.
Algorithm 2 Anonymized Histogram Estimator w.r.t & loss, for large domains.
Input: Discrete Laplace-noised histogram hed i.e., hgyd ~ hijdd DLap(p)
Compute an estimate â red
of n red
using Algorithm s.t. 11, s.t. || =
return á that minimizes [ (n)
Are
We give an efficient implementation of (a variant of) the above algorithm in Algorithm 7 (Ap- pendix D.2), which runs in time Oe logn). The main result of this section is the following:
Theorem 12. For all B > An and histograms h with ||al] the estimate ñ returned by Algorithm 2 satisfies
E El n/11]
< O - red [11] n n n/B
s o (o
Cp log n + n n/BB (using Theorem 9).
By setting B nV/logn, we get the following corollary.
Corollary 13. For all 0 algorithm, and achieves expected eerorr of E(n,e) = O OVVn(log (aillogn)3/44 /
O(1), Algorithm 2 for -022 and B nylogn is an E-DP
By choosing B O (VVn((lo /e9/4/e12/ 1/2/ for 2(log -0. n);; state the simpler bound for brevity.
n.5 logn. the bound in Corollary 13 could be improved
7

---

We describe the main steps in the proof of Theorem 12.
Lipschitzness of Inverse of r We start by showing that the "inverse" of is O(i)-Lipschitz:
Lemma 14. [Proof in Appendix A.1] For B > 4n and all anonymized histograms n, n'' with || || & n,
|T - r (n')ll 2 I n n111
Concentration of red.
We now bound the expected liddistance between 62 and its expecta-
tion r (n).
Lemma 15. Assume that B 2n. Then, B r (n)]lil //
Proof. We have
El n8 - -r = Erejn) B Bl - B (n)r]
Ere(n) Bllogr Blogr11 I1l
S Ere(m) V /arllgr
(5)
We next use the following bound on the variance.
Lemma 16. (Proof in Appendix A.2] For all r E [n], Varlpgr
16n S B
( +
Eie(r-1)
((r-t)
Plugging Lemma 16 into (5), we have
r((--) b.pt B 5 1 (n)llal s o (Vn/B) Ere(nl V Exetr-1]
r(r-1)
Sauchy-Sehward
6Pp 0 (vn/B) . Verem FV Ere(s) (# EnEr-11 -(--))
rup (Vnlog(n)/B Eretal (# (1
r-t
(Vllog(n)/B)
1:20 O((logn) Eie(n-1) Eie(n-1) 7
S
(Vllog(n)BB
O(nlogn) + Ologg) Ete(n-1] pp
(Vn (/llogn)// B
lognlogn)
O(n logn/lo)n.
Putting things together. With all the components ready, we can now prove Theorem 12.
Proof of Theorem 12. By Lemma 14, we have
E||n
[|11] <
E[[[[ B (n) B (1)
[B[]]T" (n) x0 nred
11 + 11 reed -r"(a)laa))
8. [B[jiT (n) - _ rnd
111)
(By definition of ò)
(Billp?" red
2 red
|| || (n)) 50 l11l)
Ol red
A red
[|]] n log /V/B////)/))) (From Lemma 15).

---

Estimating Symmetric Properties of Discrete Distributions
In this section we show how use Theorem 12 for the task of estimating symmetric properties of discrete distributions over [k]. Here, a distribution property is symmetric if it remains unchanged under relabeling of the domain symbols. For example, notable such property the Shannon entropy of distribution D defined as (D) = Σg D(x) log D(z). a central object in information theory, machine learning, and statistics. If the support is unbounded, estimating (D) impossible with any finite number of samples. Our goal is to estimate the entropy of a distribution D E Au up an additive za error, where A denotes the set of all distributions over [At].
One of the key ideas in the literature (e.g., [3]) is to design low sensitivity estimators f 2n R for the desired symmetric distribution property f A + R. The (non-private sample complexity of a property f A + R using estimator f. denoted by Cj(f.a), is the smallest number of samples needed to estimate f(D) upto accuracy a with probability at least 0.9, that is, Pr(lf(S)-
f(D) > a] < 0.1. The sensitivity of estimator f is An.,j which is the smallest value for which it holds for adjacent datasets S ~ S' each with n elements, that Ii(S) - f(S") s A Let Dj(a,E) == min(n An, S O.1a/E(n,ee for E(n, E) defined in Corollary 13.
We will only consider symmetric estimators f, for which we will abuse notation to use f(n) to denote f(S) for any dataset S that corresponds to the anonymized histogram
Theorem 17. For all 0 < < 0(1), 8 E (0, 1]. for any symmetric distribution property f, and any symmetric estimator f. there exists an e- E-DP mechanism in the pan-private model and (c, 5D-P mechanism in the shuffle DP model, such that PrS-D" Pis-D=I[M(S) - f(D) > a] < 0.2 with sample complexity
(C, ( a + Dj (2
Proof. Let n denote the anonymized histogram corresponding to the sampled dataset S. The mech- anism M simply outputs f(n) for á returned by Algorithm 2. Clearly the mechanism M is DP due to the post-processing property.
We have that for a suitable n = 0 (c, (f. + +D +D (g.=)) holds that
Pr [[]mm)) - S(D)
a 0.1 and Pr (r[(((m) f(n)
a 2
S 0.1,
where the first incquality holds by definition of Cj(f. a/2), and the second incquality holds because
(f(()) - f(n)) s A..j || - n n2/1 and by the guarantee of Theorem 12 and Markov's 's inequality
Pr[l| n//1 10E(n, e)] S 0.1. By a union bound, we have Pr(l[((A) f(m)) > a] S 0.44. O
We get the following sample complexity bounds for private estimation of Shannon entropy in the pan-private and shuffle DP models, as an immediate application of Theorem 17.
Corollary 18 (Proof in Appendix C). For all 0 S 0(1), 10, there exists E-DP mechanism in the pan-private model and (). mechanism in the shuffle DP model, that can estimate the entropy of D E AE up an additive error of ta with a sample complexity of
min XE(O.))
{0(=
k
log at
log" (1/(ae))
O
&
loga l a²
+
(1/(ae) 1/(1-2A) a²
These bounds have the same dependence on k as in the work of Acharya et al. [3]. The depen- dence on a and is slightly worse due higher cost of sensitivity in our setting, and the worse dependence on E in our guarantees in Corollary 13.
We also derive sample complexity bounds for private estimation of support coverage and sup- port size. The support coverage a distribution D and an integer m is defined as Sm, =
'The choice of 0.1 is arbitrary; using the "median trick", we can boost the success probability to 1 - 3 with additional multiplicative log(1/8) more samples.

---

Exesupp(D) (1 (1 )), i.e., the expected number of distinct elements seen if we draw m Li.d. samples from D. Here would like to estimate Sm (D) within additive emror of toa.. The support size of a discrete distribution D is the number atoms I such that D(x) > 0. In general, this is impossible with finite sample since some atom of D might have arbritrarily small probability mass. To avoid this, we follow prior work and consider only probability distributions in A21/K == (D] Vx E supp(D), D(x) 1/K), i.e., those with non-zero mass of at least 1/K every atom, for some K. We defer the details of the exact sample complexity bounds and the proofs Appendix C.
Conclusions and Future Directions
In this paper, we give simple algorithms for privately computing anonymized histograms, Our algo- rithms can be implemented in the shuffle and pan-private models. There are several immediate open questions as discussed below.
Our upper bounds have a dependency of O(1/s2.5) in the -eerroor case and O(1/E355 in the 22- error case; it is unclear if these are tight. Similarly, there is a lower order multiplicative term of Ollog v.) and Ollog" n) in our ε and &z-error bounds respectively. Closing these gaps would be an interesting next step: these would also lead to improvements the sample complexity bounds private estimation of symmetric distribution properties, such as the Shannon entropy (Corollary 18).
While our analysis of the large domain case relies on the hash function being uniformly random, it is conceivable that this is not required for the approach to work. will be interesting this approach, perhaps with some modifications, pairwise-independent hash family.
also work with weaker family of hash functions such
Note also that our shuffle DP algorithm has > O, i.e., approximate-DD DP. This may not be necessary: there are a couple of recent algorithms for computing histogram with shuffle DP with d = 0 [28, 19]. Our post-processing approach does not immediately apply to these algorithms because the noise to each count not discrete Laplace noise (and in fact not even an independent additive noise). Adapting approach to their setting is another interesting research direction.
10

---

References
[1] J. M. Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867-2867, 2018.
[2] J. Acharya, H. Das, A. Orlitsky, and A. T. Suresh. A unified maximum likelihood approach for estimating symmetric properties of discrete distributions. In ICML, pages 11-21, 2017.
[3] J. Acharya, G. Kamath, Z. Sun, and H. Zhang. INSPECTRE: privately estimating the unseen. Priv. Confidentiality, 10(2), 2020.
[4] Acharya, Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. In NeurIPS, pages 6879-6891, 2018.
[5] F. Aldà and H. U. Simon. A lower bound the release of differentially private integer parti- tions. IPL, 129: 14,1,,,220 2018.
[6] M. Aliakbarpour. I. Diakomikolas, and R. Rubinfeld. Differentially private identity and equiv- alence testing of discrete distributions. In ICML, pages 169-178, 2018.
[7] K. Amin, Joseph, and Mao. Pan-private uniformity testing. In COLT, pages 183-218, 2020.
[8] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[9] V. Balcer, A. Cheu, M. Joseph, and J. Mao. Connecting robust shuflle privacy and pan-privacy. In SODA, pages 2384-2403, 2021.
[10] B. Balle, Bell, Gascón, and K. Nissim. Private summation in the multi-message shuffle model. In CCS, pages 657-676, 2020.
[11] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions close. In FOCS, pages 259-269, 2000.
[12] A. Bittau, Ú. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer,
U. Kode, J. Tinnés, and B. Seefeld. Prochlo: Strong privacy for analytics the crowd. In SOSP, pages 441-459, 2017.
[13] Blocki, A. Datta, and Bonneau. Differentially private password frequency lists. In NDSS, 2016.
[14] J. Bonneau. The science of guessing: analyzing an anonymized corpus of 70 million pass- words. In P, pages 538-552, 2012.
[15] B. Cai, C. Daskalakis, and G. Kamath. Priv'it: Private and sample efficient identity testing. In ICML, pages 635-644, 2017.
[16] M. Charikar, K. Shiragur, and A. Sidford. Efficient profile maximum likelihood for universal symmetric property estimation. In STOC, pages 780-791, 2019.
[17] L. Chen, B. Ghazi, R. Kumar, and P. Manurangsi. On distributed differential privacy and counting distinct elements. ITCS, pages 56:1 36:1-56:18. 18, 2021.
[18] A. Cheu, A. D. Smith, J. R. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pages 375-403, 2019.
[19] A. Cheu and C. Yan. Pure differential privacy from secure intermediaries. CORR, abs/2112.10032, 2021.
[20] I. Diakonikolas, M. Hardt, and L. Schmidt. Differentially private learning of structured discrete distributions. In NIPS, pages 2566-2574 2015.
[21] B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In NeurlPS, pages 3571-3580, 2017.

---

[22] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Minimax optimal procedures for locally private estimation. JASA, 2017.
[23] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006.
[24] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[25] C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. Pan-private streaming algorithms. ICS, pages 66-80, 2010.
[26] Ó. Erlingsson, V. Feldman, I. Mironov, A. Raghumathan, K. Talwar, and A. Thakurta. Ampli- fication by shuffling: From local to central differential privacy via anonymity. In SODA, pages 2468-2479, 2019.
[27] Ú. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: Randomized aggregatable privacy- preserving ordinal response. In CCS, pages 1054-1067, 2014.
[28] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, R. Pagh, and A. Velingker. Pure differen- tially private summation from anonymous messages. In /TC, pages 15:1-15:23, 2020.
[29] B. Ghazi, R. Kumar, P. Manurangsi, and R. Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In ICML, pages 3505-3514, 2020.
[30] A. Greenberg. Apple's "differential privacy" is about collecting your data - but not your data. Wired, June, 13, 2016.
[31] Y. Hao and A. Orlitsky. The broad optimality of profile maximum likelihood. In NeurIPS, pages 11989-11001, 2019.
[32] G. H. Hardy and S. Ramanujan. Asymptotic Formulaæ in Combinatory Analysis. Proc. London Math. Soc., s2-1 s2-17(1):75-115, 01 1918.
[33] M. Hay, C. Li, G. Miklau, and D. D. Jensen. Accurate estimation of the degree distribution of private networks. In ICDM, pages 169-178, 2009.
[34] M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boosting the accuracy of differentially private histograms through consistency. VLDBB, 3(1):1221-1032 2010.
[35] V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. In ITCS, 2018.
[36] K. Kenthapadi and T. T. L. Tran. Pripearl: A framework for privacy privacy-rreserving analytics and reporting at linkedin. In CIKM, pages 2183-2191, 2018.
[37] P. Manurangsii Tight bounds for differentially private anonymized histograms. In SOSA, pages 203-213, 2022.
[38] M.r.Mir, S. Muthukrishnan, A. Nikolov, and R. N. Wright. Pan -riivpivate algorithms via statistics on sketches. In PODS, pages 37-48, 2011.
[39] A. Orlitsky, A. T. Suresh, and Y. Wu. Optimal prediction of the number of unseen species. PNAS, 113(47):13283-133 13288, 2016.
[40] S. Raskhodnikova and A. Smith. Efficient Lipschitz extensions for high-dimensional graph statisties and node private degree distributions. FOCS, 2016.
[41] R. Rogers, S. Subramaniam, S. Peng. D. Durfee, S. Lee, S. K. Kancha, S. Sahay, and P. Aham- mad. Linkedin's audience engagements API: privacy preserving data analyties system at scale. J. Priv. Confiden. 11(3), 2021.
[42] G. Rote. Isotonic Regression by Dynamic Programming. In SOSA, pages 1:1-1:18, 2019.
[43] S. Shankland. How Google tricks itself to protect Chrome user privacy. CNET, October, 2014.
[44] A. T. Suresh. Differentially private anonymized histograms. NeurlPS, pages 7969-7979,
2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] We discuss limitations and scope for future improvements in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Since this is purely theoretical paper regarding private algorithms for approximately com- puting anonymized histograms, we do not foresee any immediate potential negative impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The proof overviews contained in the main body; with proofs of key lemmas included in the supplemen- tary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URLJ? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "tKluG3phE0R", "reviewer": "Reviewer_EABc", "summary": "This paper studies the problem of releasing anonymized histograms subject to DP in various privacy models.    Privatizing anonymized histograms has been considered before, but only in the global privacy model.  This paper considers the pan privacy and shuffle DP models.  Their results show that the anonymized histograms can be approximated up to error that matches the special case problem of Count-Distinct in both the shuffle and pan privacy models.  ", "questions": "Why not consider continuous Gaussian noise for the $\\ell_2$ error metric?  This can be applied in the shuffle model.  If noise must be discrete for other reasons, perhaps the Skellem distribution could also be used.\n\nShould the $\\ell_2$ error be squared?  Just want to make sure that the informal statements of theorems are supposed to be $\\ell_2^2$ or $\\ell_2$.  ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- Anonymized histograms seem to be growing in popularity as an important problem to research.  The paper presents nice results in various privacy models.\n- The introduction presents the previous work very clearly, giving a nice history of releasing anonymous histograms subject to privacy.  \n- The post processing function to get back an anonymous histogram from a privatized cumulative prevalence is a nice result.  In particular, prior work did not need to consider noise when the cumulative prevalence was privatized before converting back to an anonymous histogram.  This post processing function and its analysis are the main contribution of this work.  \n- I like that this work addressed the issue of large domains, although it does look like an \"off the shelf\" approach with a random hash.  \n- Estimating Symmetric Properties of Discrete Distributions is a nice application of the results in the paper.\n\nWeaknesses: \n- The results seem to follow from prior work on privatizing count-distinct.  Although the anonymized histogram problem is more general, the techniques in the analysis seem to be largely the same.  The main observation is that for count distinct, we need to compute the number of items that have true count larger than 0, which can then be generalized to number of items that have true count larger than r, which will result in a histogram with sensitivity of 1.  Hence the results boil down to the same analysis as before except applying it to a sensitivity 1 histogram rather than a single count.  \n- The general approach largely follows previous work, using Laplace mechanism and estimating the cumulative prevalence to then get an anonymous histogram.  \n- I would have liked to have seen more detail in Section 4, such as how hash functions are selected randomly.  Theorem 12 seems a bit hand wavy.   \n\n\nMinor nits: \n- In the introduction, it states that $n^{\\ell}$ is the $\\ell$th largest element among the $h_j$'s, but should this be the *count* of the $\\ell$th largest element for anonymous histograms?\n- There are too many footnotes in the beginning, which should be included in the main body of the paper.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sNu6hciAQ2", "reviewer": "Reviewer_c3rB", "summary": "\nThe authors study the problem of releasing anonymized (labels are not released) histograms with DP. First result is an algorithm that takes a histogram with Discrete Laplace noise, and returns an anonymized histogram with l_1 and l_2 errors of O(\\sqrt(n + D)). Where n is number of records and D is the size of the histogram domain. Second main result is an algorithm that via hashing, overcomes the dependence on D in the previous bound. This algorithm can be implemented in the pan private model on in the shuffle model of DP. Last main result is an algorithm to estimate symmetric properties of distributions, entropy being an example. ", "questions": "It seems to me that we need knowledge of the domain size D in advance. I’m curious, are there settings of practical interest where D is not known in advance and we still want to release an anonymized histogram? I’m asking because this is an important problem in the setting of DP Histograms with labels (https://proceedings.neurips.cc/paper/2019/file/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf)", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is written clearly, it is easy to follow, literature review is sufficient to give the reader context. Algorithms and bounds are novel and improve upon state of the art. \nWeakness: Seeing the algorithms being applied in a real world problem or a simulation comparing to previous work would have been cool to motivate the reader. However, this is a theory paper and there is limited space so, although I think it would improve the paper,  I don’t think it is a big deal.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XSVMO6_lGu_", "reviewer": "Reviewer_82i7", "summary": "This paper studies private anonymized histograms in shuffle DP and pan privacy models. Under $\\ell_1$ loss, the proposed algorithm achieves $\\tilde{O}(\\sqrt{n}/\\varepsilon^{2.5})$ error, which nearly matches the optimal bound in central DP model in terms of $n$. This paper also applies the proposed algorithm on shannon entropy estimation for discrete distributions.", "questions": "1. Under the central DP model and $\\ell_2^2$ loss, the proposed algorithm is worse than Hay et al [33] (This paper has $O(\\sqrt{n}/\\varepsilon^3.5)$). Both algorithms use a Laplacian noised histogram and a post-processing step. I am wondering if there is any connection and differences.\n\n2. I am not very familiar with pan privacy and the shuffled DP model. I am wondering if there is any lower bound technique that translates central DP bounds into these settings. What would break if you apply prior works for central DP under pan privacy and shuffled DP model?", "limitations": "This paper is theoretical and does not have a direct negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: 1. The proposed algorithm is simple. It is based on random hashing and laplacian mechanism, which can be implemented in pan privacy and shuffled DP models.\n2. This paper is well written. The structure is easy to follow.\n\nWeaknesses: 1. It is not clear if the dependence on $\\varepsilon$ is tight. Compared to the lower bound in central DP, there is a $1/\\varepsilon^{1.5}$ gap. \n2. Time complexity is not discussed here.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hygrtr3axG3", "reviewer": "Reviewer_214Q", "summary": "This paper considers the release of anonymized histograms under differential privacy. In this setting, $n$ users each have some integer from the domain $[D]$. A histogram of the data is the number of users with each integer in the domain. An anonymized histogram is the set of frequencies in the histogram without the corresponding domain labels. This paper first shows that given a noisy histogram procured by adding Laplacian noise with scale parameter $\\frac{1}{\\varepsilon}$, there exists an algorithm that outputs an anonymized histogram with expected $\\ell_1$ and $\\ell_2^2$ error $O_{\\varepsilon}(\\sqrt{n})$. This subroutine can then be used to achieve private anonymized histograms as well as private symmetric function property testers in the pan-private and shuffle models.", "questions": "Are there linear time algorithms for the post-processing steps in Algorithms 1 and 2?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The main subroutine is nice and simple. Given an input (discretized) noisy histogram, the algorithm essentially builds a noisy cumulative mass function and then outputs the best fit integral histogram. The analysis is more intricate but also reasonably intuitive. To decrease the domain size from $D$ to $O(n)$, the algorithm hashes the universe into buckets of size $B=O(n)$. It then remains to bound the collision error, which intuitively should not be too high because many values of the domain must have frequency zero, while the remaining collisions can be charged to the $\\ell_1$ error. \n\nWeakness: I think the main weakness of the paper is that the post-processing algorithms do not have runtime analysis. Specifically, the runtime to output the best fit integral histogram is not analyzed and I think the efficiency of these post-processing algorithms can make a large difference in the practicality of this paper. Perhaps the authors can address this concern in the rebuttal phase.\n\nPost-rebuttal update: I'm pleased to see details for a near-linear time post-processing steps for Algorithm 1 and 2. Though I have not gotten a chance to verify correctness, it seems my main concern is a non-issue, so I have increased my score from a 4 to a 6. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept