Private and Communication-Efficient Algorithms for Entropy Estimation
Authors: Gecia Bravo-Hermsdorff
Robert Istvan Busa-Fekete
Mohammad Ghavamzadeh
Andres Munoz medina
Umar Syed
Venue: NeurIPS 2022 Accept (2022)
Keywords: Shannon entropy
collision entropy
Gini entropy
differentially private algorithms
communication-efficient algorithms

Abstract: Modern statistical estimation is often performed in a distributed setting where each sample belongs to single user who shares their data with a central server. Users are typically concerned with preserving the privacy of their sample, and also with minimizing the amount of data they must transmit to the server. We give improved private and communication-efficient algorithms for estimating several popular measures of the entropy of a distribution. All of our algorithms have constant communication cost and satisfy local differential privacy. For a joint distribution on many variables whose conditional independence graph is a tree, we describe algorithms for estimating Shannon entropy that require a number of samples that is linear in the number of variables, compared to the quadratic sample complexity of prior work. We also describe an algorithm for estimating Gini entropy whose sample complexity has no dependence on the support size of the distribution and can be implemented using a single round of concurrent communication between the users and the server, while the previously best-known algorithm has high communication cost and requires the server to facilitate interaction between the users. Finally, we describe an algorithm for estimating collision entropy that matches the space and sample complexity of the best known algorithm but generalizes it to the private and communication-efficient setting.

Private and Communication-Effiieee Algorithms for Entropy Estimation
Gecia Bravo-Hermsdorff Department of Statistics University College London gecia. bravo@gmail. com
Róbert Busa-Fekete Google Research busarobi@google. com
Mohammad Ghavamzadeh Google Research ghavamza@google.comm com
Andres Muñoz Medina
Umar Syed Google Research usyed&google.com com
Google Research ammedina@google. com
Abstract
Modern statistical estimation is often performed in a distributed setting where each sample belongs single user who shares their data with central server. Users are typically concerned with preserving the privacy of their samples, and also with minimizing the amount of data they must transmit to the server. We give improved private and communication--ffiiiee algorithms for estimating several popular measures of the entropy of distribution. All of our algorithms have constant communication cost and satisfy local differential privacy. For joint distribution over many variables whose conditional independence is given by a tree, we describe algorithms for estimating Shannon entropy that require number samples that linear in the number of variables, compared to the quadratic sample complexity of prior work. We also describe algorithm for estimating Gini entropy whose sample complexity has no dependence on the support size of the distribution and can be implemented using single round of concurrent communication between the users and the server. In contrast, the previously best- known algorithm has high communication cost and requires the server facilitate interaction between the users. Finally, we describe an algorithm for estimating collision entropy that matches the space and sample complexity of the best known algorithm but generalizes it to the private and communication-efficieee setting.
Introduction
Statistical estimation has traditionally focused on minimizing the number of samples needed to estimate properties of a distribution. In the 'big data' era, statisticians and computer scientists have also tried to minimize the space complexity estimation algorithms, particularly in the streaming setting. More recently, the increasing prevalence of mobile computing has led to focus the privacy and communication costs of statistical estimation. In this paper, we consider the following setting: of users each draw sample from distribution, and share information about their sample with a central server. The central server then uses the collected data to estimate a property of the distribution. Users are concerned with preserving the privacy of their sample, and also with minimizing the amount of data that is transmitted to the server.
For example, consider the problem of detecting fingerprinting the web 31 Many websites track users across the web without their consent by recording (enough) information about their devices (e.g., installed fonts, operating system, timezone, etc.), practice known "browser fingerprinting" Entropy is the standard metric used to quantify the identifiability the collected fingerprints. So
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

private and distributed method for estimating entropy can be used by browser to warn users that this covert tracking could occur, without ever storing the fingerprints themselves.
The study of entropies has an extensive and rich history in mathematics and sciences. Related quantities called "entropy" appear in many contexts (thermodynamics, information theory, dynamical systems [35, category theory 121 etc.). These may be broadly thought as measures of information of system or process obeying certain properties, which, in turn, lead to natural measures of disorder, randomness, outcome diversity, information content, uniformity, etc.
In this paper, we study private and communication--ffiiii algorithms for estimating certain entropies of a distribution. Specifically, we give algorithms for estimating the following entropies, which are widely- in many scientific fields to quantify the uncertainty, diversity and spread of discrete distribution:
Shannon entropy
33 fundamental quantity in information theory.
Gini entropy (also known as Tsallis entropy [88] of order 2, or (one minus the) second frequency moment). Some of its applications include measuring ecological diversity [4 27]. market competition among firms [2I], effective size of political parties 26 and suitability of features to split on during decision tree learning 30
Collision entropy (also known Rényi entropy include measuring the quality of random number generators (66. and determining the number of reads needed to reconstruct a DNA sequence
22 of order 2). Some of its applications
Our algorithms are implemented in either the non-interactive model (for the Gini and collision entropies), in which all users simultancously exchange information with the server during a single round of communication, or the (stronger) sequentially interactive model (for the Shannon entropy), in which the server queries users one at a time, possibly in an adaptive manner 22 When analyzing the communication complexity of an algorithm, we prove bounds on the number of bits that each user transmits to the server. However, the server is allowed to broadcast an arbitrary amount of information to the users (this is also called the blackboard model (I)), including shared random bits (also known as the public coin model [1 23 When analyzing the privacy of our algorithms, we use the framework of local differential privacy about each user's data.
which ensures that the server learns very little
Our contributions:
A sequentially interactive æ-local differentially private algorithm for estimating the Shannon entropy of a joint distribution on d variables within ed error using (d/a2²²) samples and O(1) bits per sample. Our analysis assumes that each of the d variables has a constant support size and that their conditional independence graph a tree. We also describe algorithms that have better dependence on 1/c in certain special cases, such as when the tree has low diameter or is chain. Our algorithms achieve 0(1) communication complexity by observing only two or three of the d variables in any single sample; we call these pair and triplel observations. The only previously known algorithm for estimating the Shannon entropy of a ste-struc distribution from pair observations is a non-interactive algorithm due to Chow and Liu (12] We prove that any non-interactive algorithm requires (dd2) pair observations to achieve (d) error. We also prove that, for any sequentially interactive algorithm, M((/e) pair observations are necessary to achieve (cd) error.
A non-interactive ollocal differentially private algorithm for estimating the Gini entropy of a distribution within error using O max(1 - g. )=²)/( samples, b bits per sample, and Óbb) space, where g E [0. 1] is the Gini entropy of the distribution. The best previous algorithms 100 either have a sample complexity that depends on the support size & of the distribution, or are sequentially interactive, and also require (2k)) bits per sample and 2(k) space. Also our error bound holds with high probability instead of only in expectation.
A non-interactive allocal differentially private algorithm for estimating the collision entropy of distribution with support size i within error using Ö(62k2 ((62k2/(a"== minfk: 2'))) samples, b bits per sample, and ((b) space. Setting b- log le and a O(1) recovers the sample and space complexity guarantees of the non-interactive algorithm from 36 up to logarithmic factors, and thus, our algorithm generalizes the previously best known algorithm to the private and communication- efficient setting.
2

---

2 Related Work
There is a very extensive literature on distributed statistical estimation under communication con- straints (see 40 for the paper that appears to have started this thread). Variations on the problem include whether communication is allowed between users, whether communication happens in one multiple rounds, whether there is shared source of randomness among the users, and whether communication is limited per-user or only cumulatively across all users.
Many previous results in this area bound the sample and communication complexity of estimating the parameters of a distribution Ps. where 0 E θ (see e.g. 20). This problem class includes discrete distribution estimation, where the guarantees are usually stated as bounds the relative entropy or total variation distance between the estimated and true distribution (see e.g. [ Other problems of interest mean estimation 37 and heavy hitter estimation
There has also been significant interest differentially private statistical estimation, and of particular relevance is the work by 3 who gave private algorithms for estimating certain functionals of distribution, including the Shannon entropy. However, they used the central model of differential privacy, while in this paper we prove guarantees using the (stronger) local model.
Entropy Measures
The Shannon, Tsallis, and Rényi entropy of discrete random variable X are defined as
(Shannon)
H(X) Σ Pr[X .| log Pr(X = x).
(Tsallis)
Tx(X) 7 7-1
(1 Σ Pr(X= =x)"),
(2)
(Rényi)
(X) 1-7 log Σ (Pr[X= ==))))=
(3)
where y in 2 and B is free parameter satisfying 7 > 0 and 7 * 1. Both Tsallis and Rényi entropy are generalizations of Shannon entropy in the sense that lim,- (X) = -lim,-11 (X) H(X).
In this paper, we describe algorithms for estimating the Shannon entropy and special cases of the Tsallis and the Rényi entropy that are widely used in many scientific fields: T2()), also known as the Gini entropy, and (X),,, also known as the collision entropy. Substituting 7 2 into the definitions above and using the abbreviations G(X) = (x) and C(X) = Rx(X), we have:
(Gini)
G(X)= Tx(X) = 1 Pr = x13
(Collision)
C(X)= = (x
= loo Σ Pr(X==]])
Gini entropy is so-called because it is equivalent to the Gini diversity index, a statistic proposed by Corrado Gini in 1912 measure income and wealth inequality [19]. Collision entropy takes its name from the observation that if and X' are independent and identically distributed, then C(X)= - log Pr[X = X'].
For the problem of estimating Shannon entropy, we specialize to a high-dimensional setting, where we only observe a pair (or triplet) of the dimensions at a time. That is, X is a random-vector of d discrete variables, where is large, but each X; has a constant support size (c.g., they are binary), and we only observe two (or three) dimensions per sample. Without making any assumption about this joint distribution, the problem is intractable. One of the most common assumptions, which we also adopt in this work, is that the joint distribution is tree-structured. In this case, the distribution can be estimated by the celebrated [1] (and optimal ? Chow-Liu algorithm. While the Chow-Lin algorithm requires ((d²)) pairs observations estimate the Shannon entropy, sequential algorithm requires only (d) pairs observations (see Section 5.2 for more details).
The joint Shannon entropy H(X....., Xa) of a set of random variables XI,... Xa is the Shannon entropy (X) of the random variable X = (XI,..., Xa). We write the abbreviated term joint entropy when the use of Shannon entropy is obvious from context.
3

---

The mutual information between two random variables X and Y and their conditional mutual information given another random variable Z are defined as:
I(X:Y) ((X) + H(Y H(),)), T( Z) = H(X, 2) + H(Y 2) -(X
(4)
(5)
Estimation Algorithms and Evaluation Criteria
A set of users and central server cooperate according to the following protocol to estimate the entropy a random variable X:
1. Each user E [ni] draws independent sample z; according the distribution of X.
2. For rounds:
(a) The server sends information to a subset of the users.
(b) Those users send (partial) information about their sample back the server.
3. The server outputs estimate of the Shannon entropy (Algorithms collision (Algorithm 5 entropies of X.
and or the Gini or
An estimation algorithum specifies the steps that each and the server perform implement the above protocol. The algorithm is non-interactive the protocol consists of a single round which all users participate. In non-interactive algorithm the server cannot adapt its queries users based on responses from other users, since the server communicates with all the users concurrently. An algorithm sequentially interactive if each round consists of communication with single user, who is never contacted again. Sequential interactivity enables the server to query users adaptively [22]
We evaluate estimation algorithms according to the following criteria:
Sample complexity: The number of users from whom the server requests data.
Space complexity: The space used by the server when executing the algorithm.
Communication complexity: The maximum number bits transmitted by any single user to the server. Note that the amount of information sent by the server to the users is not counted when determining communication complexity.
Privacy: Let v; be the sample belonging to user i and o, be the data observed by the server from user i. We say that an algorithm satisfies a-local differential privacy if
Pr(o; E O x = x] S e² Pr(o; E O 24 = x']
for any user measurable set O, and possible sample values ar,
Error: The absolute difference between the true entropy of the distribution and the estimate output by the server.
Estimating Shannon Entropy of Tree-structured Joint Distributions
In this section we assume that X = (Xi, Xa) is vector of d discrete variables, and that the support size of each variable X, is constant (e.g., each variable Boolean). We also assume that X has rree-structured distribution, which means that there exists rooted tree T with d nodes such that for any node E [d] we have Pr[X, X_,]] = Pr[X, (m), where X_, = (X,....X,... X ..),.))) and the node pay the parent of node in tree T'. If is the root node, then we define Pr[X; (x),,())
Pr[X.]. Equivalently. tree-structured distribution is Markov random field with a tree as the underlying undirected graph. Essentially, the tree-structured assumption implies that the only correlations among the X,'s pairwise correlations. If T is chain or a star we say that is chain- strrcturdd and star-structured, respectively. We will treat these two special cases the end of this section (Algorithms 2 and g respectively).

---

5.1 Estimating Entropy of a Marginal Distribution When the Support Size is Small
Before proceeding to describe algorithms for estimating the Shannon entropy of tree-structured distributions, we use existing results for private distribution estimation to devise local differentially private estimator for the Shannon entropy that sample and communication efficient when the support size of the distribution is small (as is the case for the individual marginals). The server will repeatedly invoke this algorithm as a subroutine in the sections below.
First we recall that the difference in Shannon entropy of two random variables can be upper bounded according to Theorem 17.3.3 of 13 as
H(x | p p'Ili log
P P'lli
where Xp and Xp are two discrete random variables with support size e and distributions p and p'. Next, we apply a local differentially private learning algorithm for discrete distribution due to A that learns the parameters a discrete distribution with small L1 error. The following theorem combines these two results by using the fact that xr/ 1og(1/z) S 1 whenever 0 < S 1/2.
Theorem 5.1. For any discrete distribution X with support size e and for any 1/2 <> O, there exists an estimator satisfying o-local differential privacy that estimates (X) within error using n = O log / e/(2a?)) samples with probability 5 when a E (0, 1).
This algorithm resulting from Theorem 5.1 can be used to privately estimate the entropy HX;).. mutual information I [X;;; Xy), and conditional mutual information X( Xx)) of any variables
log 2222
X, and Xg. This can be done using O since each of these variables has constant support size, and both mutual information and conditional mutual information can be expressed in terms of entropies (Eqs. and ). We call such an estimate (at, e, d) -good..
samples per estimate and O(1) bits per sample,
5.2 Our Algorithm for Tree-structured Joint Distributions
Note that the support size of X can be exponential in d. In the worst case, estimating the entropy of a distribution with support size k within constant error requires θ(k) samples [18.. However the tree-structure of X can be exploited to significantly reduce the sample complexity. In their seminal paper. Chow and Liu [12 proved the identity
d
H(X) = Σ H(,)) - max Σ (Xxx
(6)
for any tree-structured random variable X, where the maximization is taken over all possible trees connecting the d variables.
Eq. O suggests a coammunicatioo-effciiee algorithm for estimating the entropy of X, which is known as the Chow-Liu algorithm: First, estimate each marginal entropy H(X)) and each mutual information T(X;; Xj). Next, compute maximum spanning tree on the d variables, where the weight of each edge Xx,X,) is the estimate of the mutual information I T(,;; Xz). Finally, plug these estimators into Eq. 6
The Chow-Liu algorithm requires 12(d)) samples, since it computes the mutual information between every pair of variables in order to compute maximum spanning tree. However, estimating the right-hand side of Eq. (6) only requires estimating the weight of the maximum spanning tree, which is significantly easier than finding the tree itself. Algorithm T adapts a technique from [I] that estimates the weight of the maximum spanning tree of a graph time that sublinear in the number of edges in the graph. The basic idea is to select nodes of the graph at random and use breadth-first search to determine the size of each of their connected components if we were to drop edges that do not meet weight threshold, short-circuiting the search when the size becomes too large. These quantities are combined to estimate the weight of the maximum spanning tree. In our case, an edge weight is mutual information between a pair of variables, which we estimate from pair observations.
Theorem 5.2. Algorithm 7 is a-locclly differentially private and has O(1) communication complexity. The number of samples requested by the server d
a²c3 Let H be the entropy estimate output by the algorithm. If X is tree-structured, then H H (X)] < ed with probability 1 - 6.
5

---

Algorithm Shannon entropy estimation for tree-structured distribution
Let M [|] and 2
2:
for m = ,,.... M do
3: for ,,..,,,..... R do
4:
Choose positive integer Z randomly according to Pr[Z 2 2| 1/2. 5: Choose i" uniformly at random from [d].
6:
if Z 2 2 then Tmr f 0.
7:
else
Breadth-fing first search
8:
Initialize queue to contain i" and set V {i*}. while queue length is non-zero and shorter than Z Remove from front of queue and V = V U (i). for = [d] \ do
9:
10:
11:
12:
Server computes (a, c, -)-good estimate I of X,)
13:
if f.j 2 em then add j to back of queue.
14:
queue length zero then Tmrr f else "Yor + 1.
15:
Cm t R
d >>==>>mm 7mr-
W + eMd -Md-e mm=1 Em=i Cm
17: Server computes (a, E, dgood estimate of each entropy (for the first sum in Eq. (6
18: Let S be the sum of the entropy estimates.
19: Return H = S W.
5.3 Our Algorithm for Chain-structured Joint Distributions
with chain T then for any triplet (X;, Xy,X, Xx), if X₁, is on the unique path in T between X; and X,. then XX;; Xx,) = 0. Thus, for any triplet (X,, X,, Xx) in T, at least one of T(X;; Xx)X)). T(X;; Xx| or T(X;: Xx\X,) has to be zero. This observation alone is not enough to recover the chain, since the conditional mutual information T(X;; X,) {x) can also zero for X,, X, and X₂ when X₃ is not on the path between X; and X3 in the chain T' Nevertheless, under the mild assumption that the mutual information [X,, X,) between every pair of variables is distinct, we can recover the chain T by estimating the conditional mutual information of triplets of variables.
Verma and Pearl [9 observed that if X
Our algorithm is similar to sorting algorithms such mergesort 24 which require Od d) pairwise comparisons over d items. While we cannot compare pairs explicitly like in sorting problem, for any triplet (X,, X.. Xx), we can use their conditional mutual information estimators to locally decide which "item" is between the other two: i.e., X; <> X, <+ XR. X; <> X <> X; or X₁ <> X; <> X, in the chain T. This suggests our Algorithm 2 which inserts the variables in chain one by one in a sequential manner. Algorithm 2 calls Algorithm Baas a subroutine that seeks to find the position where to insert.
Theorem 5.3. Algorithm is a-locally differentially private and has O(1) communication complexity.
The number of samples requested by the server is O log
Let be the entropy estimate output
by the algorithm. If X is shain-structured and [[X;; I(X Xx)) then In - H(X) S ed with probability 6.
5.4 Our Algorithm for Star-structured Joint Distributions
If X is star-structured then recovering the star 7' is a matter of identifying its center, which can be done by computing the mutual information between only (d)) pairs of variables. The algorithm picks random marginal X; and takes "Prim's step" 20 i.e., chooses the neighboring node (say X₂) that has the largest mutual information with X, Assuming that the mutual information T(X,, X2) between every pair of variables distinct, the edge between X; and X₃ is in the maximal spanning tree. Next, the algorithm estimates Σjte 1 (X,,, Xx) and ΣøœR [Xxx, Xi) to decide whether X, or
X₁ is the center node of the star. Algorithm presents the procedure, and Theorem 5.4 gives its sample complexity.

---

Theorem 5.4. Algorithm is a-locally differentially private and has ((1) communication complexity.
The number of samples requested by the server is O dlog
a²c² Let be the entropy estimate oulput
by the algorithm. If X is star-structured and ((xxxXX)) I(X;; Xx) e, then | H(X) S ed with probability
Algorithm 2 Shannon entropy estimation for chain-structured distribution
1: S [d]. C' 0. pick arbitrary i.j.k k S and set S S ki.
2: Server computes (a, e, 8g-oo estimates i(X;; X2 Xx), I(X;; Xu X3) and f(xs; Xx).
3: if XX, [Xx) > E then 21 = ki,
4: else if I(X;; X3) > c then = (i.j.k)
5: else if 7(Xa; X, X2) > c then 21 (j.
6: for E (1....,do 3) do
7: Pick item) from S and set S = S\ (i), r= 2i,1 and p 21,122
8: Server computes (a, c, cgooo estimates f(xy; Xp
Xo), I(x;: X2 1Xp).
9: if T(X;; Xpl Xx) > 6 then 2++1 = (j,
b. Attach X, to the head of the chain D Attach X, to the tail of the chain b Insert X, into the chain defined by æ; Defined in Algorithm
10: else if i(Xo; X, X,) > then Ti+1 (
11: else
12:
= TERNARY SEARCH EHERNARYSEARCHHE
1,
13:
2++1 = (ai[1,... 4. x 1e.....,, 2
14:
Create chain T according to the order defined by zd-2-
15: Server computes (,,,,,)-good estimate of each term in Eq. using T and returns H.
Algorithm 3 TERNARY 4, Jn
1: if f 4, 1 then return &
2: Pick the median element k = [(e, + f,),, and set i = Iz, and o = æea
3: Server computes (a, c, 5) estimate f(X;; X X,).
4: if I(X;; |x,) > e then return TERNARY E,
5: else return TERNARY SEARC((, k. o.j)
Algorithm 4 Shannon entropy estimation for star-structured distribution
1: Pick é E [d uniformly at random.
2: Server computes (a, e, -)ooo estimate X(),,X)) for all j [d] {i}.
3: Find
arg max))((()) X()
4: Server computes (a, e, -) estimate i(X,, Xj).
5: if E, i(X,,
E, [(X,, Xy) then let T'' be a star with X; center
6: else let T be star with X as the center.
7: Server computes (a, e, (e),,,)-goo 5)-oood estimate of each term in Eq. 6 using T and returns A.
5.5 Lower Bounds
We prove sample complexity lower bounds for estimating the Shannon entropy of a tree-structured joint distribution from pair observations. Our first lower bound focuses on the non-interactive case, when the algorithm must select all the pairs in advance. The second claim is more general, and holds for all sequentially interactive algorithms.
Theorem 5.5. For any non-interactive algorithm that uses o(d²) pair observations to estimate Shannon entropy, there exists tree-structured distribution over {0, 13 such that the error of the algorithm is Q(d) with constant probability.
Theorem 5.6. For any e > O and for any sequentially interactive algorithm that uses old/c) pair observations to estimate Shannon entropy, there exists a tree-structured distribution on (0, 13 such that the error of the algorithm is Qie d) with constant probability.
7

---

The lower bound given in Theorem 5.5 is based on Turán's 's theorem R which we use to show that for any algorithm with sub-quadratic sample complexity and for any constant E (0, 1), there is graph with d nodes containing a C d-clique when d is large enough such that the algorithm does not observe any edge of that clique. This implies that the additive error of the algorithm is linear in d. The lower bound for sequentially interactive algorithms in Theorem 5.6 is based on information theoretical approach. Interestingly, our construction of problem instances for which we applied Le Cam's 's theorem is fairly simple, since it contains d independent random variables in every case. Nevertheless, this lower bound shows that Algorithm is optimal in d.
5.6 Comparison to Prior Work
To the best of our knowledge, the Chow-Liu algorithm is the only published method for estimating the entropy of a distribution that takes advantage of its tree structure. Since the algorithm is non- interactive, the lower bound in Theorem 5.5 shows that our algorithms have provably better sample complexity when the number of variables d is large (note that the dependence on d in each of
Theorems 5.2 5.3 and i.4 is sub-quadratic). The Chow-Liu algorithm can also be used to estimate the distribution itself, not just its entropy, and it has recently been shown [ [5 that the algorithm has optimal sample complexity when given full observations (i.e., samples of the entire vector (Xi:..., Xa)) and not just pairs or triplets of the variables). Thus the Chow-Liu algorithm is optimal for estimating a tree-Structured distribution, but suboptimal for estimating the entropy of a tree- structured distribution. The root cause of this difference appears to be the fact that it is significantly easier to estimate the weight of the maximum spanning tree than finding the tree itself.
6 Estimating Gini and Collision Entropies
In this section, we describe a non-iterative protocol (Algorithm 5) that estimates both the Gini and collision entropies of discrete random variable X while observing only bits per sample from its distribution, and does not require any extra assumption on the distribution of X (such as assuming it is tree-structured). First, the server partitions all users into pairs (assume for simplicity that the number of users is even). The server then distributes b-bit hash function to each user, along with a distinct salt to each user pair. Each user then hashes their sample along with their salt, and returns the hash value to the server. The server computes entropy estimates based on the number of observed hash collisions across all pairs. In Algorithm we let (ar, v) denote a binary string that encodes æ, followed by delimiter, and by y.
Algorithm 5 Gini and collision entropy estimation
1: Each user i E [n]] draws a sample x; independently from the distribution of X.
2: Server partitions the users into b/2 disjoint pairs.
[ be the index of the pair containing user i. 4: Server transmits d and hash function h {0, 10,1)*-0 {0, 13.b to each user
3: Let qi
5: Each user i generates a b-bit hash value h;
zz)) for their sample z4-
6: Each user lets h, h, with probability À vسt and otherwise draws h, uniformly from [2*].
7: Server receives h₂ from each user i.
8: If pair g contains users and j then let Gg 1lh; hy] indicate whether hash collision was observed for pair q.
9: Server computes غ (1 [1-A]n Eg Cg)
10: Server outputs & 11 C --1 and Ô = - log G1-
Algorithm 5 is based on the observation that if X and X' are independent and identically distributed then the Gini entropy is equal to Pr[X = X') and the collision entropy is equal to log Pr[X X'). If the server observed each sample directly then it could estimate Pr[X- = X'I using the collision frequency, i.e., the fraction of sample pairs (I., 2ry) such that x; xy. However, the server only observes b-bit hash of each sample. Among sample pairs in which there is a true collision, all of them also produce a hash collision. Among samples pairs in which there not a true collision, about 1 fraction of them produce hash collision. Therefore the true collision frequency can be
8

---

estimated using an appropriately caas-coreected hash collision frequency, and the server uses this estimate to approximate the Gini and collision entropies.
The analysis of Algorithm S is given in Theorem 6.1 below. As is eustomary, for the analysis we assume that the hash function h is constructed by assigning each element of its domain to uniform random element of its range [6. See the Appendix for the proof of the theorem.
Theorem 6.1. Algorithm 5 is a-locally differentially private, has Ö(b) communication complexity and Ó(b) space complexity. Let G and Ć be the oulputs of the algorithm. Let a, e, E (0, 1). If
Ω has support size and Ω
6² max (I-G(())2""))
then IG (G-G(() S e with probability at least 6. Also, if X 6² log 1 at (in(k;2))) then |Č C(X) S c with probability least 1 8.
a=
6.1
Comparison to Prior Work
Recall that Gini entropy is proportional to the second frequency moment. Local differentially private algorithms for estimating frequency moments were recently studied in [TO. Letting 6 1 in Algorithm 5 yields a sample complexity of Ó(1/a²e²), which is independent of the distribution's 's support size, unlike the sample complexity of the non-interactive algorithm for estimating the second frequency moment from TO] Also our algorithm only uses 1 bit per sample and ((1) space, while the previous algorithm uses (2(k) bits per sample and (2()) space, where k is the support size of the distribution. The authors in [[O] asked whether there is a non-interactiv algorithm for privately estimating frequency moments with sample complexity that is independent of the distribution's 's
support size. Here we affirmatively answer this open question for the second frequency moment.
The best known algorithm for estimating collision entropy using Õ(1) space is due to [36] The sample complexity of their algorithm is Ô (k/c²) and its communication complexity Olog k)) bits per user. Letting b log k and = ((1) in 5 recovers these results (up to logarithmic factors), and using smaller values for b or a generalizes the previous algorithm to the private and communication-effice -fffiiinnt setting. Also, it was shown in [14] that (conditioned on a plausible conjecture) any algorithm that estimates collision entropy to within O(1) error using O(1) space requires (2k)) samples. Therefore our algorithm is likely to be Pareto optimal with respect to the sample complexity-space complexity trade-off.
7 Experiments
In this section we present two sets of experiments to support our theoretical findings. First, we demonstrate that Algorithm T is indeed able to estimate the Shannon entropy of tree-structured distributions with linear sample complexity in d. Thus it has superior sample complexity comparing to the state-of-the-arr non-interactive method [12 7 which has a quadratic sample complexity in d. The sample complexity is defined here in terms of number of observations from pairs of marginals. In the second set of experiments, we use our Algorithm to estimate the collision entropy of discrete distributions, and compare its performance to that of the best-known communication efficient, non-private algorithm for this task (which we refer to as Skorski's algorithm 36
To estimate the Shannon entropy of a tree tree-structured distribution as given by eq. ( the marginal entropies and the mutual information between certain or all pairs of marginals have to be estimated. The Chow-Liu algorithm estimates the mutual information between all pairs of marginals which results quadratic sample complexity, whereas Algorithm estimates esstinaesess the mutual information only for a linear fraction of pairs. Both algorithms estimate the marginal entropy values by sampling the marginals independently from the mutual information estimations, and they both use the same additive eиror and privacy budget to estimate the mutual information between pairs of marginals. Thus is fair to compare their performance in terms of number of pairs for which they estimate the mutual information. For the Chow-Liu algorithm this is always dZ, whereas our Algorithm is randomized, thus we evaluate it over 100 repetitions and report the average.
Estimating Shannon entropy:
We ran this experiment on random tree-structured joint distributions over {0, 1]d To create a random tree-structured distribution, we first sample the skeleton of the distribution by taking the maximum spanning tree of complete graph with d nodes and edge weights distributed according to a standard normal. Next, we sample the parameters for each marginal uniformly at random from [o, 1]. and

---

then we achieve the tree-structure by inducing dependence between pairs of variables while preserv- ing the marginals. Specifically. for two marginals X; and X; with sampled parameters P; and Pj. we set: P(X; 0,
= -1), - - pi Pj + rij. - where Fi is sampled uniformly at random from a range of values such that each probability stays positive. The results are displayed in Figure La It is clear that the sample size (i.e., number of mutual informa- tion estimate) is close to linear for our algorithm, whereas the Chow-Liu algorithm requires larger sample size.
= -,, - Pi - -ij. and - 1,,
p.) +rj rij.
P(X; = 0, x
4.0
Alg. Chow-Liu
L/tropy estimation STOr
por
2.5
2.0
1.5
0.0
30000 100h 31000 33083 1740 bits
1005
250
/59 2000
1:00 1/50 2000
Dimension (d)
(h) Absolute error in estimating the col- lision entropy of an exponential distri- bution with domain size k = 1000 for the Skorski's 's algorithm 36 and for
(a) Sample complexity of estimating Shannon entropy of tree-structured dis- tributions (eg. 6 for the Chow-Liu al-
gorithm and for our Algorithm
Algorithm
Estimating collision entropy: In this set of experiments, we drew samples from discrete expo- nential distribution p3 xx e with support size k = 1000 and estimated the collision entropy using algorithm 36 (the previously best-known communication-efffciennt algorithm for this task) and our Algorithm (with and without local differential privacy). Algorithm 33 requires Ollog k) bits per sample and not private, while our algorithm only requires bit per sample and differentially private. The results are displayed in Figure lb The previous algorithm has 5% estimation error after observing 1 10000 bits, while our algorithm has less than 3.5% estimation error. Thus our algorithm has lower error for the same communication cost while also being local differentially private.
8 Conclusion and future work
Estimating entropy is of importance in many practical applications. In this paper, we studied three widely used entropy measures: Shannon, Gini and collision entropy. We described estimation algorithms for each entropy that require minimal communication and satisfy local differential privacy. We also validated our theoretical results with simulations.
Our sequentially interactive algorithm for estimating Shannon entropy of high-dimensional tree- structured distributions observes only two of these dimensions per sample and has sample complexity Od/e²). Our approach relies on the celebrated Chow-L.it approximation [12, providing a substantial improvement on the ((d)) sample complexity of the original non-interactive Chow-Liu algorithm. We also identified two special cases (viz., when the underlying graphical model of the joint distribution is either a chain or star graph) and provided algorithms with a sample complexity of Ö(d log d/e?). Our algorithm for Gini and collision entropy estimation also improved the ofate-of-the-art, either by improving the sample complexity and communication complexity of previous work, or by generalizing the best known algorithm to the private and
catpuuiiiaatinffffiieetee setting.
A natural extension of our work on Shannon entropy estimation is to consider higher-order correlations in the Chow-Liu decomposition (25). In contrast to the second-order case which reduces maximum spanning tree problem, discovering the underlying structure of the joint distribution is already computationally challenging. However, efficiently estimating the entropy of the resulting distribution might still be possible.
References
[1] Jayadev Acharya, Clement Canonne, Cody Freitag, and Himanshu Tyagi. Test without trust: Optimal locally private distribution testing. In Proceedings of the Twenty-Secome International
10

---

Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2067-2076. PMLR, 2019.
[2] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Inference under information constraints: Lower bounds from chi-square contraction. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 3-17. PMLR, 2019.
[3] Jayadev Acharya, Gautam Kamath, Ziteng Sun, and Huanyu Zhang. Inspectre: Privately estimating the unseen. In International Conference on Machine Learning, pages 30-39. PMLR, 2018.
[4] Jayadev Acharya and Ziteng Sun. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning, pages 51-60. PMLR, 2019.
[5] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1120-1129. PMLR, 2019.
[6] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing ef- ficient protocols. In Pruceedings of the 1st ACM Conference on Computer and Communications Security, pages 62-73, 1993.
[7] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and NV Vinodchandran. Near-optimal learning of tree-structured distributions by Chow-Liu, In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 147-160, 2021.
[8] Béla Bollobás. Modern Graph Theory. Graduate Texts in Mathematies 184. 1998.
[9] Tai-Danae Bradley. Entropy as topological operad derivation. Entropy, 23(9). 2021.
[10] Cristina Butucea and Yann Issartel. Locally differentially private estimation of functionals of discrete distributions. In M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24753-24764. Curran Associates, Inc., 2021.
[11] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal computing, 34(6); 2005.
[12] C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14(3):462-455 467, 1968.
[13] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley--nterscieecee, New York, NY, USA, 2006.
[14] Michael Crouch, Andrew McGregor, Gregory Valiant, and David P Woodruff. Stochastic streams: Sample complexity vs. space complexity. 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Degsttul-LLeibniizzZeeruu fuer Informatik, 2016.
(15) Constantinos Daskalakis and Qinxuan Pan. Tree-structured Ising models can be learned efficiently, arXiv e-prints, pages arXiv-2010, 2020.
[16] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pages 1161-1191. 191. PMLR, 2019.
[17] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 933-):211-4077, 2014.
[18] Kazuto Fukuchi and Jun Sakuma. Minimax optimal estimators for additive scalar functionals of discrete distributions. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2103-2107. IEEE, 2017.
[19] C. Gini Variabilità e Mutuabilitd. Contributo allo Studio delle Distribuzioni delle Relazioni Statistiche. Bologna: C. Cuppini., 1912.

---

[20] Yanjun Han, Ayfer Özgür, and Tsachy Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory, pages 3163-3188. PMLR, 2018.
[21] Oc Herfindahl, Concentration in the US steel industry. 1950.
[22] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 94-105. IEFE, 2019.
[23] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 94-105. IEEE Computer Sociery, 2019.
[24] Jyrki Katajainen and Jesper Larsson Träff. A meticulous analysis of mergesort programs. In Italian Conference on Algorithms and Complexity, pages 217-228. Springer, 1997.
[25] Edith Kovács and Tamás Szántai. On the Approximation of a Discrete Multivariate Probability Distribution Using the New Concept of t-Cherry Junction Tree, pages 39-56. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
[26] Markku Laakso and Rein Taagepera. "Effective" number parties: A measure with application to west europe. Comparative Political Studies, 12(1))3-27, 1979.
[27] Tom Leinster. Entropy and Diversity: The Axiomatic Approach. Cambridge University Press, 2021.
[28] Abolfazl S Motahari, Guy Bresler, and NC David. Information theory of DNA shotgun sequencing. IEEE Transactions on Information Theory, 59(10)6673-6288, 2013.
[29] Robert Clay Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6): 1389-1401,, 1957.
[30] Laura Elena Raileanu and Kilian Stoffel. Theoretical comparison between the Gini index and information gain criteria. Annals of Mathematics and Artificial Intelligence, 41(1):77-93, 2004.
[31] Florencia
Rao.
htcps://www.scuuraatt..co combaa//ut.ccccco/////oooooooooc
the ihee-rt-off-e war- wtw.://wwwa.ooooooooooooonnnnnna browssr-Eingrrrintting 2021.
[32] Alfréd Rényi. On measures of information and entropy. In Proceedings of the fourth Berkeley Symposium on Mathematics, Statistics and Probability, pages 547-561, 1960.
[33]
C.E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27:379-423, 1948.
[34] Edward H Simpson. Measurement of diversity. nature, 163(4148):688 688, 1949.
[35] Yakov G. Sinai. On the notion of entropy of a dynamical system. 2010.
[36] Maciej Skorski. Evaluating entropy for true random number generators: Efficient, robust and provably secure. In International Conference on Information Security and Cryptology, pages 526 541, 03 2017.
[37] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference on Machine Learn- ing, pages 3329-3333, PMLR, 2017.
[38] Constantino Tsallis. Introduction to Nonextensive Statistical Mechanics. Springer New York, NY, Greece, 2009.
[39] Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI '90, page 255-270, USA, 1990. Elsevier Science Inc.
[40] Yuchen Zhang, John C Duchi, Michael Jordan, and Martin J Wainwright. Information-theoredd lower bounds for distributed statistical estimation with communication constraints. In NIPS, pages 2328 2236.. Citeseer, 2013.
12


Reviews:
[{"review_id": "tvY7f6nLMk", "reviewer": "Reviewer_MyKL", "summary": "In this paper, the authors focuses on communication-efficient algorithms for estimating the entropy of a distribution under privacy constraints. They propose private methods for Shannon, Ginni and Collision entropy that are the most widely used entropy types. The proposed algorithms are implemented for both interactive and non-interactive models. They showed that the estimation algorithms for each entropy satisfy local differential privacy and require minimal communication.\n", "questions": "It might be useful to provide some background why Ω(d^2) pair observations to achieve O(d) error is good. Similarly, Ω(d/ε) pair observations are necessary to achieve O(εd) error is an improvement and other similar bounds? Maybe it is clear for people who are working in this field but that makes reading the paper more difficult. ", "limitations": "Authors mentions in Checklist that there is a gap between upper and lower bounds. First of all I couldn't find the discussion in the main part of the paper and it is not discussed how the gap between the upper and lower bound can be reduced (if possible). ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: To the best of my knowledge, the proposed approach is novel and solves an important problem in a distributed data setting.\n\nWeaknesses: In my opinion, the main problem is the lack of motivation. I couldn't get why private entropy estimation is important. It is not easy to follow the paper at times as a non-expert in the field. Minor issue: why don't you refer to the previously best-known algorithm in line 14?  That could help to people to engage who are working on similar problems and knows the literature well. ", "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": "cTW1r0YXDCX", "reviewer": "Reviewer_ejtY", "summary": "The authors study the problem of estimating the entropy of a distribution in a distributed setting. Specifically, samples from a distribution are distributed across machines. The goal is for a central entity to estimate the entropy of the distribution. They consider a number of different communication models - (a) non-interactive model, in which all users simultaneously exchange information with the server during a single round of communication (b) sequentially interactive model, in which the server queries users one at a time, possibly in an adaptive manner. They use the blackboard model of communication where the information sent from a machine to the server is broadcast to all machines for free, i.e. the information is written on a metaphorical blackboard and all machines get to view the blackboard for free. \n\nNote that entropy estimation can be very trivially accomplished by estimating the distribution itself, but here they ensure that their algorithms are \"private\" where privacy is defined according to the notion of \"local differential privacy\".\n\nTheir main contributions are: (1) An interactive and private algorithm for estimating the Shannon entropy (2) non-interactive algorithms for estimating the Gini and collision entropy.\n\nMy reviewing capacity: I have some previous experience in doing research in distributed statistical estimation. I am comfortable with basic information theory, randomized algorithms, concentration inequalities, basic analysis. I have taken a look at the proofs in moderate detail.\n\n", "questions": "See suggestions for improvement above.", "limitations": "See comments above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of estimating entropy has been well studied, and this has been studied in distributed settings as well. The paper provides improved algorithms in the settings considered. Other than for Shannon entropy, the authors provide non-interactive algorithms. Obviously it is \"better\" to provide strong non-interactive algorithms because non-interactive algorithms are trivially interactive with just zero interaction. While related work is well cited, more discussion about the importance of the problem is required. The algorithmic techniques are non-obvious. The analysis uses quite basic information theory and concentration inequalities.\nAs I said, I haven't perused the proofs in complete details, but the paper seems sound technically. The analysis is rigorously done. Also, the paper is very clearly written.\n\nI am not very convinced about the strength and importance of the results. For example, with Shannon entropy, which really is the most commonly used form of entropy, they assume that the support size of the distribution is constant. If support size is constant, then distribution estimation can be done with O_eps,delta(1) amount of communication, and in turn entropy estimation can be done trivially. While I don't have context of the relevant work, the authors must clearly describe why they can't use techniques for distributed distribution estimation and why new techniques are required. Another issue is the structure assumed in the distribution. There is no motivation provided about why the distributional structure would be something of interest.\nAlso, I feel that the authors have provided very little motivation about why these problems are important. This is especially important with Gini and collision entropy.\n", "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": "35U9cBxHJ9", "reviewer": "Reviewer_aeFq", "summary": "This paper provides a method for computing the Shannon, Gini, and collision\nentropy of a distribution in the sequentially-interactive differential \nprivacy models.\n\nFor Shannon entropy, they approximate the weight of the Chow-Liu tree \nusing private l_1 estimation between pairs of variables, combined with the fact\nthat the l_1 estimation of a distribution can approximate entropy when the \ndomain is not too large. Under sequential interaction, they show that a\nnear-linear number of samples can be taken by estimating the weight of  \na maximum spanning tree. This improves over the work of Chow and Liu.\nThey also show that their algorithm has optimal dimensionality dependence with a \nlower bound.\n\nThey specialize these results to when the dependency graph of the distribution \nis a chain or a star.\n\nFinally, they show how to use hash collisions to estimate Gini and collision\nentropy in the non-interactive local DP setting.\n", "questions": "What do the authors expect for the approximation quality of the entropy estimation algorithm given that the algorithm only considers tree-structured distributions?\n\nCan we make any statement about sample complexity when the privacy parameter $\\alpha$ is low?", "limitations": "The Shannon entropy of the best tree-structured distribution \nis returned, this is an approximation of the true Shannon entropy which is the \nassumption of the Chow-Liu tree. \n\n(Edit: this seems to be a common assumption, so it’s not a severe limitation.)\n\nThis limitation could best be overcome with an experiments section---the\nalgorithms are straightforward to implement, and one could estimate the quality\nof the entropy estimation on a real-example.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper achieves subquadratic sample complexity for the problem of Entropy\n  estimation, improving over the Chow-Liu algorithm.\n\n+ The communication overhead is a small constant for both algorithms.\n\n- The lower bounds do not depend on $\\alpha$, the privacy parameter, thus they\n  are definitely loose when \\alpha is small.\n\n- There are no experiments to evaluate the approximation quality. (Edit - they've added some which favorably compare their work)\n", "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