Source-linked AI summary
Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
Min Ye, Alexander Barg
TL;DR
The paper studies minimax estimation of a discrete distribution from independently privatized samples under local differential privacy. It proposes new schemes for the medium-privacy regime, proves substantial reductions in expected loss over existing schemes, and establishes order optimality when e^ε is much smaller than k.
Problem
The problem is to estimate a discrete distribution with support size k from privatized rather than raw samples while selecting an ε-private scheme with minimal worst-case estimation loss.
Method
The paper proposes a family of new privatization schemes and derives their performance and lower bounds across privacy regimes.
Results
50% lower expected loss under ℓ2^2 and 30% lower expected loss under ℓ1 are proved for 3.8 < ε < ln(k/9), relative to existing schemes.
Takeaways & Limitations
The schemes are order optimal in the regime where e^ε is much smaller than k.
Abstract
from arXiv · showhide
We consider the minimax estimation problem of a discrete distribution with support size $k$ under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number $ε$ measures the privacy level of a privatization scheme. For a given $ε,$ we consider the problem of constructing optimal privatization schemes with $ε$-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes in the literature provide order optimal performance in the high privacy regime where $ε$ is very close to $0,$ and in the low privacy regime where $e^ε\approx k,$ respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when $1\ll e^ε \ll k.$ More concretely, we prove that when $3.8 < ε<\ln(k/9) ,$ our schemes reduce the expected estimation loss by $50\%$ under $\ell_2^2$ metric and by $30\%$ under $\ell_1$ metric over the existing schemes. We also prove a lower bound for the region $e^ε \ll k,$ which implies that our schemes are order optimal in this regime.
I. INTRODUCTION
The paper studies how to estimate a discrete distribution from independently privatized samples while balancing statistical accuracy against protection of individual data.
- Differential privacy formalizes protection against reliably inferring an individual’s data from public statistics, including in the local setting.The local context concerns individuals disclosing their personal data rather than institutions releasing group statistics.
- The problem is minimax estimation of a distribution with support size k under locally differential privacy.The estimator must recover the raw-sample distribution from privatized observations generated independently through a conditional distribution Q.
- Smaller ε makes the original data harder to infer from privatized samples.
A. Existing results:
Prior work establishes order-optimal schemes at the high- and low-privacy extremes, while leaving the medium-privacy regime comparatively unresolved.
- k-RAPPOR is order optimal when ε is very close to 0, whereas k-RR is order optimal when e^ε is much smaller than k.
- Existing schemes were not known to work well when e^ε is far from both 1 and k.This identifies the medium-privacy regime as the gap between the established extreme regimes.
- A tight lower bound was known for the high-privacy regime, but no meaningful lower bounds were known for medium privacy.
B. Our contributions:
The paper introduces new privatization schemes for medium-to-high privacy, shows substantial improvements over k-RR and k-RAPPOR, and proves order optimality across e^ε much smaller than k.
- B. Our contributions:: The new family is order optimal in the medium-to-high privacy regimes when e^ε is much smaller than k.
- B. Our contributions:: 50% lower expected loss under ℓ2^2 and 30% lower expected loss under ℓ1 occur when 3.8 < ε < ln(k/9).These reductions are measured against the existing schemes.
- B. Our contributions:: The scheme outperforms k-RR by a factor of Θ(k/e^ε) under ℓ2^2 loss, with similar results for k-RAPPOR and ℓ1 loss.
- B. Our contributions:: A tight lower bound over the region e^ε much smaller than k implies order optimality there.
- B. Our contributions:: The paper also shows that k-subset mechanisms had been proposed earlier, with prior work reporting experimental improvements over k-RR and k-RAPPOR.The paper distinguishes its contribution by providing detailed analysis of the schemes in the medium-privacy regime.
II. PRELIMINARIES AND PROBLEM FORMULATION
The paper formulates private distribution estimation through a privatization mechanism Q, an induced marginal distribution, and minimax risk under locally differential privacy.
- Notation: The source alphabet is X = {1, 2, ..., k}, and p is a probability distribution on this alphabet.The distribution lies in the k-dimensional probability simplex.
- Private distribution estimation: In the private problem, raw i.i.d. samples are independently transformed by Q into privatized samples in an output alphabet Y.The output alphabet need not equal the source alphabet.
- Risk and estimation: The estimator maps privatized samples in Y^n to an estimate in R^k and is evaluated using expected loss and minimax risk.
- Local differential privacy: A mechanism is ε-locally differentially private when output probabilities under any two inputs differ by at most a factor of e^ε.The definition applies to all inputs and measurable output events, with a finite-alphabet equivalent stated for individual outputs.
- Optimization objective: For a fixed privacy level ε, the goal is to choose the locally private mechanism with the smallest possible minimax risk.
- Induced distribution: The induced marginal distribution of privatized samples is denoted m = pQ.
III. NEW SCHEMES
The paper introduces privatization schemes parameterized by d, with output vectors containing exactly d ones, and derives empirical estimators and risk-optimal choices of d for ℓ2^2 and ℓ1 loss.
- Scheme construction: The new scheme Qk,d outputs binary vectors in an alphabet whose vectors contain exactly d ones.The parameter d ranges from 1 to k−1.
- Estimation: The marginal distribution of each output coordinate is calculated to solve for an empirical estimator of p.The resulting estimator is given in equation (6).
- Risk optimization: The optimal choice of d for both ℓ2^2 and ℓ1 risk is one of the nearest integers to k/(e^ε + 1).For ℓ2^2 risk, minimizing the relevant expression yields d = k/(e^ε + 1); the integer constraint selects a neighboring integer.
- Risk bounds: For d = floor[k/(e^ε + 1)], Proposition III.3 gives risk upper bounds and asymptotic expressions across privacy regimes.The proposition applies when k ≥ max(4, e^ε + 1), and separately describes the regimes e^ε ≪ k and 1 ≪ e^ε ≪ k.
A. Comparison of our scheme with k-RR and k-RAPPOR
The proposed scheme is compared with k-RR and k-RAPPOR across privacy regimes. It matches k-RR at low privacy, matches k-RAPPOR asymptotically at high privacy, and improves over both in the medium-privacy regime.
- Low privacy: When e^ε ≥ k, the proposed scheme chooses d = 1 and coincides with k-RR.The k-RR scheme is itself Qk,1 in this paper.
- Existing schemes: The k-RAPPOR scheme flips each coordinate of the input basis vector independently with probability 1/(1 + e^(ε/2)).Its output alphabet is the set of binary vectors of length k.
- High privacy: At high privacy, k-RAPPOR is order optimal, while the proposed scheme has the same approximate ℓ2^2 risk and therefore does not improve over it.This comparison concerns small ε and large k.
- Medium privacy: In the medium-privacy regime 1 ≪ e^ε ≪ k, the proposed scheme compares favorably with both k-RR and k-RAPPOR.Proposition III.4 gives the risks of the two existing schemes in this regime.
- Medium privacy: When 3.8 < ε < log(k/9), the proposed scheme's expected loss is at most 50% of existing schemes under ℓ2^2 loss and at most 70% under ℓ1 loss.These bounds correspond to reductions of 50% and 30%, respectively.
IV. LOWER BOUND
The section establishes a tight lower bound on minimax risk and outlines a two-step reduction to extremal private mechanisms. The result applies under a sample-size condition stated in Theorem IV.1.
- The proof first restricts attention to privatization schemes with extremal configurations, following Theorem IV.5.The section describes this as the first step toward obtaining optimal performance.
- The lower-bound argument is organized around the regime e^ε ≪ k.The proof is presented as a refinement of a private version of Assouad’s method.
- Theorem IV.1 gives a tight lower bound on the minimax risk when n exceeds a condition involving k and e^ε.The theorem statement is followed by bounds for the relevant risk quantities.
A. Reduction to extremal configurations
This section reduces the search for optimal mechanisms to finite-output schemes with extremal configurations. It uses finite partitions and convex decompositions while preserving the induced distribution and estimation risk.
- Finite output alphabets: Finite output alphabets suffice when searching for optimal schemes.A technical approximation argument constructs a finite-output mechanism and estimator with risk within any α > 0.
- Finite output alphabets: The reduction partitions the output space and replaces measurable outputs with finite cells while controlling estimation loss.The construction uses partitions of Y and Y^n into measurable sets and defines a finite mechanism from the cell probabilities.
- Extremal configurations: Every likelihood-ratio vector in [1,e^ε]^k is a convex combination of the 2^k extremal vectors in {1,e^ε}^k.This cube-vertex representation underlies the reduction to extremal configurations.
- Extremal configurations: An extremal mechanism can reproduce the original mechanism’s output distribution and preserve the estimator’s expected loss.The construction expands the output alphabet, then maps expanded outputs back to the original outputs.
B. Derivation of the lower bound: Proof of Theorem IV.1
The proof derives the lower bound using a private Assouad-style construction over perturbed distributions and bounds distinguishability between the resulting privatized mixtures. It treats ℓ2^2 loss before adapting the argument to ℓ1 loss.
- Construction: The lower-bound construction uses distributions indexed by sign vectors that perturb paired coordinates around the uniform distribution.The proof begins with even k and notes that odd k requires only a minor modification.
- Loss function ℓ2^2: For ℓ2^2 loss, the estimator induces sign tests for each coordinate pair, reducing estimation error to testing errors between privatized mixture distributions.The functions g_j are defined from the estimator’s coordinate deviations.
- Loss function ℓ2^2: The testing errors are bounded through Cauchy–Schwarz and Pinsker’s inequality, producing the lower-bound expression for every private mechanism.The proof combines these inequalities with the mixture construction and obtains the bound in equation (29).
- Loss function ℓ1: The ℓ1 proof follows the same structure, with δ/k replacing δ^2/k^2 in the relevant intermediate bound.The section states that this is the only difference in the corresponding equation.
2) Loss function ℓ1:
For ℓ1 loss, the proof analyzes likelihood-ratio configurations of private mechanisms and derives bounds across privacy regimes. The resulting lower bound is tight over the larger region e^ε ≪ k.
- Lower-bound optimization: The proof optimizes over likelihood-ratio vectors whose coordinates lie in {1,e^ε}.If both entries in a paired coordinate are e^ε, resetting one to 1 improves the objective, so at least one paired entry is 1.
- Lower-bound optimization: The parameter t is optimized over paired coordinates, and the maximizing choice is t = k/(e^ε − 1).This choice provides intuition for why d ≈ k/e^ε is optimal.
- Comparison with prior work: The improved proof treats the numerator and denominator jointly, yielding a tight lower bound throughout the larger region e^ε ≪ k.The earlier method is tight only when e^ε is very close to 1.
APPENDIX A PROOF OF PROPOSITION III.1
The appendix verifies properties of the estimator and constructs the finite measurable partition needed for the proof. It also uses product-measure and finite-algebra arguments to establish measurability and partition structure.
- The proof begins by checking that the estimator p̂ in (6) is unbiased.
- A central-limit-theorem argument identifies the large-sample Gaussian limit of the normalized statistic T_i−E[T_i].
- The proof constructs the n-fold product σ-algebra from measurable rectangles and uses finite-algebra generation to obtain a finite partition of Y^n.