Source-linked AI summary
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
John C. Duchi, Michael I. Jordan, Martin J. Wainwright
TL;DR
The paper asks how accurately probability distributions can be estimated when data remains private even from the statistician. It combines local differential privacy with minimax decision theory to derive sharp rates for discrete and continuous estimation, showing privacy-dependent losses in statistical efficiency and the optimality of randomized response.
Problem
The paper addresses the limited characterization of estimation accuracy and privacy–utility tradeoffs when observations are protected through local privacy.
Method
The paper uses minimax decision theory, locally private channels, divergence bounds, and matching efficient algorithms to analyze probability estimation.
Results
Sharp convergence rates are obtained for multinomial and density estimation, and Warner’s randomized response has optimal sample complexity for survey sampling.
Takeaways & Limitations
Privacy and statistical efficiency form a fundamental continuum that can be adjusted to meet the privacy or utility needs of the statistician and sampled population.
Takeaways & Limitations
Direct Laplace perturbation of samples cannot attain the target density-estimation convergence rate because the resulting deconvolution problem imposes a slower rate.
Abstract
from arXiv · showhide
We provide a detailed study of the estimation of probability distributions---discrete and continuous---in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental tradeoffs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efficiency continuum. One of the consequences of our results is that Warner's classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents.
1 Introduction
The paper develops a formal minimax framework for probability estimation when each observation is transformed through a locally private channel. It derives privacy–efficiency tradeoffs for multinomial and density estimation, including sharp rates and optimality of randomized response.
- Contributions: The paper combines differential privacy with minimax decision theory to characterize optimal probability estimation under local privacy constraints.It derives lower bounds for all private estimators and matching upper bounds achieved by computationally efficient algorithms.
- Setting: Local privacy allows interactive channels, so each private view may depend on its own datum and the other providers’ private views.This broader setting can permit more efficient algorithms and makes the lower bounds stronger.
- Setting: Each private view is required to satisfy α-local differential privacy for the corresponding original observation.The privacy guarantee is imposed directly through the conditional channel producing each individual’s private view.
- Main results: For d-dimensional multinomial estimation, sufficiently small constant privacy reduces the effective sample size from n to nα^2/d.The paper concludes that Warner’s randomized response achieves optimal sample complexity for this survey-estimation problem.
- Main results: For densities with β continuous derivatives, local privacy changes the polynomial rate from the classical n^-2β/(2β+1) to (α^2n)^-2β/(2β+2).Efficient algorithms attain matching sharp upper bounds, and some require non-trivial sampling strategies to preserve privacy.
2 Background and Problem Formulation
The paper formulates private estimation as a minimax problem over both estimators and locally private channels, then reduces lower bounds to testing and controls the resulting divergences and mutual information. These tools support sharp privacy-dependent bounds for discrete and nonparametric estimation.
- 2.1 Minimax framework: The framework defines a parameter map θ over a distribution class, a semimetric ρ for estimation error, and a loss function Φ for measuring risk.For density estimation, the parameter space may be probability densities on [0,1], with Φ(t)=t^2 as an example.
- 2.1 Minimax framework: The α-private minimax rate takes the infimum over all α-locally private channels after evaluating the worst-case estimation risk.The expectation averages over both the original data distribution and the private channel.
- 2.1 Minimax framework: Lower bounds reduce estimation to identifying a member of a finite, well-separated packing of parameter values.The packing condition requires pairwise parameter separation of at least 2δ, and the unknown index is selected uniformly.
- 2.1 Minimax framework: Because the statistician observes only private samples, the analysis uses the marginal channel induced by passing the original sample through the joint private channel.The induced distribution is defined by integrating the channel conditional on the original data distribution.
- 2.1 Minimax framework: Le Cam’s two-point method and Fano’s inequality convert testing difficulty into minimax risk lower bounds for private estimation.The testing procedure maps the private observations to a candidate index, while the lemma supplies the corresponding risk bound.
- 2.2 Information bounds: The divergence tools bound total variation, pairwise KL divergences, and mutual information as functions of privacy and distances between underlying distributions.Pairwise KL bounds support Le Cam and simple Fano arguments, while variational mutual-information bounds enable sharper applications of Fano’s inequality.
- 2.2 Information bounds: The bounds apply to every α-locally private channel and compare each conditional data distribution with the marginal distribution induced by that channel.The analysis introduces component distributions and their mixture to express the relevant information quantities.
- 2.2 Information bounds: Combining the information proposition with the minimax risk lemma yields sharp lower bounds, with carefully constructed packings needed to retain dimension dependence.A simpler bound can lose the desired dimension dependence, whereas the stronger bound supports more refined constructions.
3 Multinomial Estimation under Local Privacy
Under α-local differential privacy, multinomial probability estimation has sharp minimax rates that quantify a substantial privacy cost. Warner’s randomized response achieves the optimal convergence rate, while Laplace perturbation offers a comparable, efficiently computable alternative.
- Sharp upper and lower bounds characterize the minimax mean-squared-error rate for multinomial estimation under α-local differential privacy.
- nα^2/d is the effective sample size for d-dimensional multinomial estimation when α is sufficiently small and constant.Local privacy reduces the effective sample size from n to nα^2/d.
- Warner’s randomized response mechanism, with minor modification, achieves the optimal convergence rate for private multinomial estimation.The paper also identifies Laplace perturbation as another strategy achieving the optimal rate.
- Private multinomial estimation strategies: Randomized response privately transforms each multinomial sample into a binary vector by sampling coordinates independently, then estimates the probability vector using projection onto the simplex.The resulting estimator is efficiently computable because simplex projection takes time linear in d.
- Private multinomial estimation strategies: Laplace perturbation adds independent Laplace noise to each data coordinate and can have sharper constants than randomized response for small α.Its simplicity may nevertheless make randomized response preferable for survey sampling.
4 Density Estimation under Local Privacy
The paper studies density estimation under α-local differential privacy and shows that privacy changes the classical minimax convergence exponent. It develops lower bounds and efficient histogram and orthogonal-series estimators that attain them.
- Problem setup: For densities in Sobolev-type classes Fβ,C, the paper measures estimation error using squared L2 loss and represents functions with an orthonormal basis.The class constrains coefficient decay according to smoothness β; trigonometric bases correspond to derivative smoothness conditions.
- Lower bound: The classical density-estimation rate n^-2β/(2β+1) becomes (α^2n)^-2β/(2β+2) under local privacy, even for bounded, well-behaved densities.For β = 1, the rate degrades from n^-2/3 to n^-1/2.
- Lower bound: No estimator based on directly perturbing samples with Laplace or exponential noise can attain the locally private lower-bound rate.The deconvolution connection yields a stronger limitation for Laplace perturbation, with rate no better than n^-2β/(2β+5).
- Achievability: For Lipschitz densities, a private histogram with k = (nα^2)^1/4 bins achieves the minimax rate and is therefore minimax-optimal.The estimator uses privatized bin indicators with Laplace noise, projects onto the simplex, and produces a valid density estimate.
- Achievability: For smoothness β > 1, an orthogonal-series estimator with k = (nα^2)^1/(2β+2) achieves the lower bound for Sobolev classes.The construction uses a locally private sampling strategy and an efficiently computable private estimator.
5 Proof of Theorem 1
The proof of Theorem 1 reduces estimation to testing over a carefully constructed packing, controls the private observations’ mutual information, and then applies testing inequalities. The argument uses Fano’s inequality in the high-dimensional case and Le Cam’s inequality when the dimension is small.
- Proof strategy: The proof first reduces the estimation problem to a multi-way testing problem over a separated family of hypotheses.The construction uses a set V of candidate vectors with controlled pairwise separation and sufficiently large cardinality.
- Information bound: The proof bounds mutual information between the private observations and the hidden hypothesis by reducing the relevant supremum to the covariance operator norm.This is the step that exploits the local-privacy structure rather than only standard estimation arguments.
- Packing construction: A hypercube packing provides many separated candidates while controlling the covariance operator norm needed for the information bound.The packing has cardinality at least (d/k)^c1k and pairwise ℓ1 separation at least max{⌊k/4⌋, 1}.
- Large dimension: Fano’s inequality converts the information bound and hypothesis separation into the desired lower bound when the dimension is sufficiently large.The large-dimension case selects k according to the regime and combines the resulting testing bound with Fano’s inequality.
- Small dimension: When the dimension is small, the proof uses a two-point construction in dimension d = 2 and applies Le Cam’s inequality.The two hypotheses have total-variation distance δ, and Pinsker’s inequality connects this separation to the marginal private distributions.
- Conclusion: Combining the two regimes yields the theorem’s minimax lower bound, including a d log 2/(nα^2) bound in the final case.The proof concludes after combining Le Cam’s inequality with the KL-divergence control from the privacy proposition.
6 Proofs of Density Estimation Results
The density-estimation proofs construct smooth packings, control the information revealed by locally private channels, and combine these bounds with testing inequalities to obtain matching rates. The upper-bound analysis uses projection and optimizes the resolution parameter to control mean-squared L2 error.
- Lower bounds: Local packing is used instead of global metric entropy because the private setting requires controlling the mutual information through a carefully constructed packing set.The argument is described as more classical than the metric-entropy approach and tailored to local differential privacy.
- Lower bounds: Smooth bump functions generate a family of β-times differentiable densities whose pairwise L2 separation is at least ck^-2β.The resulting class forms a (ck^-β)-packing with cardinality at least exp(c0k).
- Lower bounds: The lower-bound construction passes i.i.d. density samples through an α-locally private channel and bounds the mutual information between the private outputs and the packing index.The proof then applies Fano’s inequality to the packing in L2.
- Upper bounds: Euclidean projection of the unprojected estimator onto the scaled probability simplex cannot increase its L2 error.This reduces the upper-bound analysis to the unprojected estimator.
- Upper bounds: The mean-squared L2-error is bounded by combining the bias, variance, and privacy-noise terms, then choosing k = (nα2)1/(2β+2).The choice of k completes the proof of the stated upper bound.
- Lower bounds: The lower-bound construction also defines a valid density by combining basis functions and rescaling when necessary to preserve nonnegativity.The final lower bound is obtained by minimizing over k.
7 Discussion
The discussion links minimax decision theory with differential privacy to derive sharp convergence rates and characterize privacy as a tunable tradeoff against statistical utility. The authors emphasize contraction-based techniques as a basis for analyzing privacy costs across statistical problems.
- Main implications: Divergence bounds show that differentially private sampling acts essentially as a contraction on distributions.The authors suggest that this contraction perspective may apply beyond the problems studied here.
- Main implications: Sharp convergence rates are obtained for nonparametric problems as well as standard finite-dimensional settings under local differential privacy.The discussion presents these as part of a broader connection between minimax analysis and differential privacy.
- Privacy–utility tradeoff: The results identify a continuum along which privacy can be traded for utility in the form of accurate statistical estimates.This continuum is intended to help adjust procedures to privacy or utility needs.
- Future scope: Formally identifying privacy–utility tradeoffs in additional statistical problems is presented as a direction for understanding their costs and benefits.The authors characterize the paper as groundwork for this broader analysis.
A Proof of Lemma 2
The proof of Lemma 2 constructs a large, separated packing of the Boolean hypercube with controlled covariance using a probabilistic argument. Tail bounds, union bounds, and matrix Bernstein inequalities establish the required packing properties.
- Probabilistic verification: Combinatorial counting bounds the number of nearby vectors, while monotonicity yields the required neighborhood estimate.These steps support the separation tail bound.
- Packing construction: The proof reduces the main range to k ∈ 4N and sets ℓ = k/4, using a random construction over the Boolean hypercube.The nonintegral case is handled by concatenating coordinates without increasing covariance.
- Packing construction: K = (d/(6ℓ))3ℓ/2 random vectors are sampled to form a candidate set that is ℓ-separated and has controlled covariance.The target properties are shown to hold with non-zero probability.
- Probabilistic verification: The construction relies on two tail bounds controlling separation and covariance-related quantities.These bounds are later combined with a union bound to establish the packing claim.
- Conclusion: The resulting packing has the cardinality and separation properties required by the lemma.The proof concludes after applying the tail bounds and accounting for constant-factor changes.
- Covariance control: Matrix Bernstein inequalities control the covariance by bounding the operator norm and variance of the associated random matrix.The random vector is centered and has the covariance normalization used in the argument.
B Proof of Lemma 4
The proof of Lemma 4 reduces the information bound over bounded functions to a finite-dimensional optimization by exploiting extreme points and the sign structure of the constructed densities. This reduction enables operator and covariance bounds for the locally private channel.
- Finite-dimensional reduction: The proof starts from the divergence bound in Proposition 1 and represents bounded functions as vectors constant on a partition of [0, 1].The partition uses intervals Di on which the constructed density differences do not change sign.
- Finite-dimensional reduction: Extreme-point analysis restricts the optimization to functions taking values in {e^-α − e^α, e^α − e^-α}/2.The restriction follows from compactness, convexity, and the convexity of the relevant functionals.
- Finite-dimensional reduction: Replacing mixed signs within any partition interval by constant signs preserves the relevant constraints through a convex-combination argument.This proves that an optimizer can be taken constant on each Di up to measure-zero sets.
- Operator bound: The supremum is therefore reduced to a finite-dimensional problem over a subset of R2k.The subsequent bound uses the Kronecker-product representation of this reduced problem.
- Operator bound: The packing covariance and operator inequalities combine to bound the reduced information expression.For α ∈ [0, 1/4], the factor (e^α − e^-α)^2 is bounded by a constant multiple of α^2.