Source-linked AI summary
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
Jayadev Acharya, Ziteng Sun, Huanyu Zhang
TL;DR
Private distribution estimation asks how to estimate distributions when users privatize data before sending it to an untrusted collector, while computation and communication remain important in large-scale applications. The paper proposes a symmetric, no-shared-randomness scheme based on Hadamard matrices with sample-order optimality, logarithmic communication, and near-linear running time. A technical scope caveat is that its analyzed raw estimates can be negative, though simplex projection preserves the same order performance.
Problem
Private distribution estimation must account for users privatizing data before release, while computation and communication are important resources in large-scale applications.
Method
The paper proposes a symmetric local privatization scheme requiring no shared randomness, with encoding and decoding based on Hadamard matrices.
Results
The scheme is sample-order optimal across privacy regimes, uses logarithmic communication in domain size, and runs in near-linear time in the number of samples.
Takeaways & Limitations
The approach jointly targets statistical efficiency, low communication, and computational efficiency for private distribution estimation.
Takeaways & Limitations
The analyzed raw estimates can be negative, although projecting them onto the simplex preserves the same order performance.
Abstract
from arXiv · showhide
We study the problem of estimating $k$-ary distributions under $\varepsilon$-local differential privacy. $n$ samples are distributed across users who send privatized versions of their sample to a central server. All previously known sample optimal algorithms require linear (in $k$) communication from each user in the high privacy regime $(\varepsilon=O(1))$, and run in time that grows as $n\cdot k$, which can be prohibitive for large domain size $k$. We propose Hadamard Response (HR}, a local privatization scheme that requires no shared randomness and is symmetric with respect to the users. Our scheme has order optimal sample complexity for all $\varepsilon$, a communication of at most $\log k+2$ bits per user, and nearly linear running time of $\tilde{O}(n + k)$. Our encoding and decoding are based on Hadamard matrices, and are simple to implement. The statistical performance relies on the coding theoretic aspects of Hadamard matrices, ie, the large Hamming distance between the rows. An efficient implementation of the algorithm using the Fast Walsh-Hadamard transform gives the computational gains. We compare our approach with Randomized Response (RR), RAPPOR, and subset-selection mechanisms (SS), both theoretically, and experimentally. For $k=10000$, our algorithm runs about 100x faster than SS, and RAPPOR.
1 Introduction
Distribution estimation seeks to recover an unknown probability distribution p from samples by constructing an estimate p̂. Statistical efficiency is measured primarily by minimizing the sample complexity.
- Distribution estimation recovers an unknown probability distribution p from samples using an estimate p̂.
- The primary efficiency objective is minimizing the sample complexity required for estimation.
1. Utility. What is the sample complexity of estimation?
Private distribution estimation studies how to estimate distributions when users privatize data before release, while accounting for privacy, computation, and communication. These resources matter because large-scale applications can make computational overhead and communication bottlenecks prohibitive.
- Local differential privacy requires users to privatize their data before releasing it because the data collector is not trusted.
- Private distribution estimation supports applications such as understanding population drug usage and internet traffic distributions while preserving individual privacy.
- Computation and communication are crucial resources that earlier private distribution-estimation work had not considered sufficiently.
- High computational overhead can be prohibitive in high-dimensional or large-sample applications, even when sample complexity is optimal.
- Communication is a bottleneck in distributed applications because devices may have limited uplink capacity and processors may communicate slowly with servers.
- The paper aims for sample-order optimality, logarithmic communication per symbol, and linear-time dependence on input and output size simultaneously.
2 Preliminaries
The paper formulates private distribution estimation under ε-LDP and evaluates schemes by sample, communication, and computational complexity. It introduces Hadamard Response, which is sample-order optimal across privacy regimes while using logarithmic communication and near-linear computation.
- Problem formulation: ε-LDP privatizes each user’s categorical sample before release, and the server estimates the underlying distribution from the privatized outputs.The task requires an ε-LDP mechanism and estimator achieving a target distributional error with high probability.
- Complexity measures: Sample complexity is the least number of users needed for the target estimation guarantee, while communication counts transmitted bits and computation includes user privatization and server estimation.These three resources define the paper’s complexity criteria.
- Previous methods and guarantees: RR is sample-optimal only in low privacy, RAPPOR only in high privacy, whereas SS and HR are sample-order-optimal for all ε.The comparison concerns ℓ1 distribution estimation; ℓ2 sample complexities are a factor k smaller in each table cell.
- Evaluation methodology: The communication comparison is defined through the entropy of the privatized output distribution, while time bounds account for faithfully reading the communicated bits.For n users, n·H(Z) provides the server-side time lower bound used for the table.
- Motivation and trade-offs: In the high-privacy regime, existing optimal methods require Θ(k^2) samples, Ω(k) communication per sample, and Ω(k^3) server time, while RR uses Θ(k^3) samples.The Ω(k^3) time bound is a factor k above the optimal Θ(k^2) sample complexity.
- Hadamard Response: Hadamard Response is sample-optimal for all parameter regimes, has logarithmic communication in the domain size, and runs in near-linear time for both ℓ1 and ℓ2 estimation.Its estimator can be computed in O(k log k) using a Hadamard vector product, and its high-privacy running time is Õ(k^2).
3 A family of ε-LDP schemes
The paper introduces a general family of ε-LDP schemes that privatizes each symbol through a chosen output alphabet and symbol-specific subset. The construction includes randomized response as a special case and uses carefully selected subsets to transmit more information.
- The paper first develops the general family, then specializes it to a sample-optimal high-privacy scheme and extends it to general ε.
- The scheme chooses an output alphabet [K], a subset size s, and a set Cx ⊆ [K] of size s for each input symbol x.Each privatized output receives higher probability when it belongs to Cx.
- The resulting mapping is ε-LDP and assigns higher probability to outputs in Cx than to outputs outside Cx.
- Randomized response is the special case K = k, s = 1, and Cx = {x}.
4 Optimal scheme for high privacy regime
For constant privacy, the paper uses Hadamard-based subsets with large pairwise separation to obtain sample-optimal distribution estimation and low communication. Fast Walsh–Hadamard decoding yields nearly linear running time.
- Hadamard construction: Hadamard-based subsets are designed with pairwise symmetric difference K, making distinct symbols statistically distinguishable.The construction uses K between k and 2k with s = K/2.
- Statistical guarantees: For ε = O(1), the scheme estimates distributions using O(k^2/ε^2α^2) samples for ℓ1 distance α and O(k/ε^2α^2) samples for ℓ2 distance.
- Statistical guarantees: For ε = O(1), communication is at most log(k) + 1 bits per user and the sample complexity is optimal for both ℓ1 and ℓ2 estimation.
- Estimation and computation: The estimator recovers p from empirical estimates of p(Cx), then computes normalized Hadamard vector products.The Hadamard transform supports vector multiplication in O(K log K) time.
- Caveat: The unconstrained estimator may have negative coordinates, but projecting it onto the simplex preserves the same order performance.
- Estimation and computation: HR satisfies the theorem’s guarantees with running time Õ(n + k).Users can sample from the relevant Hadamard subsets in O(log K) time.
5 General privacy regimes
The general-privacy construction interpolates between Hadamard response and randomized response through block-structured reduced Hadamard matrices. It achieves optimal statistical performance across privacy levels while keeping communication logarithmic and runtime nearly linear.
- Construction: The scheme interpolates between Hadamard matrices in the high-privacy regime and the identity matrix corresponding to randomized response in the low-privacy regime.
- Construction: A reduced Hadamard matrix is built from B diagonal Hadamard blocks of size b, with K = B · b.
- Parameter choices: B is chosen as the largest power of two below min{e^ε, 2k}, while b is the smallest power of two larger than k.
- Complexity: K ≤ 4k, so communication is at most log k + 2 bits per user.
- Privatization: The mechanism uses s = b/2 and assigns symbols to rows of the embedded Hadamard blocks.Privatization can be performed in O(log k) time per user.
- Guarantees: For all ε and k, the construction provides an estimate with running time Õ(n + k) and communication at most log k + 2 bits.
6 Experiments.
Experiments compare HR with RR, RAPPOR, and SS across distributions, domain sizes, sample sizes, and privacy levels. HR matches the best statistical performance while substantially reducing decoding time, especially for large k.
- HR’s statistical performance is comparable to the best possible across privacy regimes, while its decoding time is similar to RR.The experiments evaluate geometric, Zipf, two-step, and uniform distributions over multiple k, n, and ε settings.
- For k = 1000, HR matches the best schemes at ε = 0.5 and ε = 7 for geometric distributions.For uniform distributions at k = 1000 and larger k such as 10000, the reported statistical performance is similarly competitive.
- Theoretically, HR’s running time is a factor k/log k smaller than RAPPOR and subset selection.The plots show orders-of-magnitude gaps for large k.
- 100x faster decoding is achieved by HR than SS and RAPPOR for k = 10000 and ε = 1.The computation gap grows with k, consistent with the theoretical analysis.
- O(nk/(1+e^ε)) and O(nk/(1+e^(ε/2))) are the expected decoding times for SS and k-RAPPOR, respectively, under fast implementations.A naive implementation takes O(nk) time.
- HR remains substantially faster than k-RAPPOR and SS in the middle privacy regime, while low-privacy comparisons reduce essentially to RR.The middle-regime decoding-time plots use a logarithmic scale and fast implementations for RAPPOR and SS.
A Proof of Lemma 6
The proof of Lemma 6 analyzes how Hadamard blocks and set intersections determine privatized output probabilities. Three cases for symbol pairs yield the required probability expression.
- Symbols are grouped into sets T_i according to the Hadamard block containing their associated row.The proof uses these groups to relate C_x and output sets S_i.
- The resulting expression for p(C_x) contains separate terms for p(x) and the mass p(T_i) of its Hadamard block.This is the probability identity used in the lemma’s proof.
- The proof considers x′ = x, x′ in the same block, and x′ outside the block to evaluate Hadamard-set intersections.The corresponding intersection sizes are b/2, b/4, and 0.
- For x in T_i, C_x is contained in S_i, whereas for x outside T_i, C_x is disjoint from S_i.These relations give |S_i ∩ C_x| = b/2 or zero, respectively.
- p(S_i) is expressed in terms of p(T_i) by combining the within-block and outside-block cases.Rearranging the resulting identity gives the stated relation.
B Proof of sample complexity bounds (Theorem 7)
The proof of Theorem 7 derives the sample-complexity bound by subtracting the estimator’s expectation from the target distribution and bounding the resulting squared error.
- Theorem 7 follows from Lemma 6 by subtracting the lemma’s expression from the estimator identity.The proof then bounds the resulting ℓ2 error.
- Squaring the difference and applying (a − b)^2 ≤ 2(a^2 + b^2) separates the error terms.This inequality is used before taking expectations.
- The empirical quantities p(C_x) and p(S_i) are averages of independent Bernoulli variables with means p(C_x) and p(S_i).Their sampling variability is therefore handled through expectation bounds.
- Summing the per-symbol relation over x and using the block bounds controls the aggregate contribution from p(x) and p(T_i).Each block T_i has size at most b.
- Using B < e^ε yields the final bound on the expected squared ℓ2 error.The proof substitutes the preceding bounds into the expectation calculation.
C.1 k-RAPPOR.
The k-RAPPOR mechanism one-hot encodes each input into a k-bit vector and independently flips its bits under local differential privacy. Its output can require substantial communication, including a linear lower bound in k for low privacy.
- Any faithful communication protocol for RAPPOR requires at least H(Z|p) bits by Shannon’s coding theorem.The bound applies even when the server knows the input distribution p.
- For uniform inputs and ε > 2 log k, the output is nearly uniform on basis vectors, giving H(Z) ≥ log k.This identifies a logarithmic lower bound in the high-privacy parameter range described.
- For any input, the k − 1 non-input coordinates are independent Bernoulli variables, yielding an entropy lower bound based on their binary entropy.The proof lower-bounds the output entropy by (k − 1)h(1/(1 + e^(ε/2))).
- For ε < 1, the communication lower bound reduces to Ω(k), and for ε < 2 log k it remains linear in k up to logarithmic factors.These bounds concern faithfully transmitting the privatized output.
C.2 Subset Selection Approaches.
Subset Selection is sample-order optimal for every ε, but its per-user communication depends critically on ε and can be undesirable when ε is small.
- Communication: Its communication complexity is characterized through the entropy of the mechanism’s output distribution.
- Communication: Under a uniform underlying distribution, the output is uniform over binary strings with Hamming weight d.
- Communication: For small ε, the communication cost is strictly undesirable.
- Communication: For the uniform input distribution, H(Z) is at least log k when ε > log k.
- Subset Selection remains sample-order optimal for all values of ε.