PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax Optimal Procedures for Locally Private Estimation

John Duchi, Martin Wainwright, Michael Jordan

arXiv:1604.02390v2math.STcs.ITstat.ME

TL;DR

The paper asks how local privacy changes the risk of statistical estimation when data remains private from the statistician. It integrates differential privacy with minimax decision theory and develops private analogues of classical lower-bound methods alongside matching procedures. Across several canonical problems, it characterizes privacy-dependent rates and identifies optimal mechanisms, while highlighting substantial accuracy losses in some high-dimensional settings.

  • Problem

    The paper studies how to characterize and balance statistical utility against privacy when data providers do not trust the statistician, including whether differential privacy can support statistically efficient estimation.

  • Method

    The authors combine minimax decision theory with local differential privacy, deriving private versions of Le Cam’s, Fano’s, and Assouad’s methods and analyzing specific private procedures.

  • Results

    The paper obtains sharp minimax rates for locally private estimation and develops mechanisms and estimators with matching lower and upper bounds across canonical problems.

  • Takeaways & Limitations

    The framework quantifies the privacy–utility continuum and helps identify mechanisms that preserve more statistical utility at a given privacy level.

  • Takeaways & Limitations

    The results include pessimistic high-dimensional cases where local differential privacy can cause significant losses in inferential accuracy.

Abstract

from arXiv · show

Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the risk of the resulting statistical estimators. We develop private versions of classical information-theoretic bounds, in particular those due to Le Cam, Fano, and Assouad. These inequalities allow for a precise characterization of statistical rates under local privacy constraints and the development of provably (minimax) optimal estimation procedures. We provide a treatment of several canonical families of problems: mean estimation and median estimation, generalized linear models, and nonparametric density estimation. For all of these families, we provide lower and upper bounds that match up to constant factors, and exhibit new (optimal) privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds. Additionally, we present a variety of experimental results for estimation problems involving sensitive data, including salaries, censored blog posts and articles, and drug abuse; these experiments demonstrate the importance of deriving optimal procedures.

1 Introduction

The paper studies the statistical cost of protecting data locally, where providers do not trust the statistician, and develops minimax tools and procedures for optimal private estimation. It derives privacy-aware lower and upper bounds, compares mechanisms, and applies them to canonical estimation problems and sensitive-data experiments.

  • The paper treats privacy as an inferential constraint and seeks fundamental limits and optimal mechanisms for differentially private estimation.
  • Local privacy protects data even from the statistician collecting it, making the privacy requirement comparatively stringent.
  • The authors characterize the statistical price of privacy and compare concrete procedures or mechanisms for producing private data.
  • Optimal mechanisms can differ from widely accepted privacy procedures while providing the same privacy guarantee and better statistical performance.
  • Figure 1 compares Laplace noise, an ℓ∞ minimax-optimal sampling strategy, and a minimax lower bound for estimating drug-use proportions.
  • The paper analyzes mean, median, high-dimensional sparse sequence, generalized linear model, and density estimation problems.

2 Background and problem formulation

The paper extends the classical minimax framework to local differential privacy by restricting estimators to privatized observations generated through private channels. It formalizes privacy, defines the resulting risk, and develops testing-based interpretations and mechanism classes for interactive and non-interactive settings.

  • 2.1 Classical minimax framework: The classical framework estimates θ(P) from observations drawn from P and evaluates an estimator using a risk determined by a metric ρ and loss function Φ.
  • 2.1 Classical minimax framework: The minimax risk takes the supremum over distributions and infimum over estimators, providing the baseline that the privacy-constrained formulation modifies.
  • 2.1 Classical minimax framework: Figure 2 represents conditional independence between raw variables X_i and private data Z_i, distinguishing interactive from non-interactive channels.
  • 2.2 Local differential privacy: A local privacy mechanism transforms each raw observation X_i into a privatized variable Z_i through a conditional distribution, possibly depending on previous privatized outputs.
  • 2.2 Local differential privacy: In the non-interactive case, each Z_i depends only on X_i; interactive dependence can simplify optimal estimator construction in median and generalized linear model examples.
  • 2.2 Local differential privacy: α-local differential privacy constrains likelihood ratios of privatized outputs under any two raw inputs to be at most exp(α), for every prior output history.
  • 2.2 Local differential privacy: Small α makes hypothesis testing close to random guessing, while α → +∞ removes the privacy constraint and recovers classical minimax risk.
  • 2.3 α-private minimax risks: Under local privacy, estimators use only private observations, and the paper seeks mechanisms in Q_α that minimize the resulting α-private minimax risk.

3 Bounds on pairwise divergences: Le Cam’s bound and variants

The paper develops private analogues of classical minimax lower-bound techniques and uses them to characterize estimation risk under local differential privacy. For mean and median estimation, these bounds yield sharp privacy-dependent rates and motivate optimal private procedures.

  • Private Le Cam bound: A private analogue of Le Cam’s method gives lower bounds for α-locally private minimax risk from two-point testing problems.The result applies to 2δ-separated distributions and estimators based only on privatized observations.
  • Private Le Cam bound: For α ∈[0, 2/3], local differential privacy reduces the effective sample size from n to at most 4α^2n.This follows from the private Le Cam bound and reflects contraction of divergence through the privacy channel.
  • Mean estimation: When k = 2, local privacy worsens the finite-variance mean-estimation rate relative to the non-private 1/n benchmark.The cited passage introduces the non-private sample-mean risk and the privacy-induced rate change, although the latter expression is truncated.
  • Mean estimation: For mean estimation under finite-k moment constraints, the α-private minimax rate scales as (nα^2)^−(k−1)/(k+1).The corresponding bounded-support limit k ↑∞ gives the standard parametric rate (nα^2)^−1.
  • Mean estimation: The Laplace mechanism is optimal for one mean-estimation setting, but later examples show that it is not universally optimal.The paper also proposes and analyzes other privacy mechanisms and estimators achieving upper bounds.
  • Mean estimation: For location estimation, local differential privacy is more reasonable on bounded domains and imposes more severe constraints when samples lie in an unbounded space.The paper connects this distinction to the limiting case k ↑∞ and to the tail behavior controlled by k.
  • Median estimation: The paper extends the same private minimax framework to median estimation using a risk gap and obtains universal-constant bounds for distributions with |med(P)| ≤ r.The median setting focuses on an M-estimator because general-distribution median estimation is impossible even without privacy.
  • Divergence bounds: A general contraction inequality for locally private channels bounds pairwise divergence through total variation and supports private Le Cam and Fano arguments.The contraction is strong enough that induced marginals have finite KL divergence even when the original pair has infinite KL divergence.

4 Bounds on private mutual information: Fano’s method

The paper extends Fano’s method to non-interactive local privacy, yielding minimax lower bounds that support sharp rates for classical and high-dimensional mean estimation. These results expose privacy-driven dimension penalties and motivate carefully designed optimal mechanisms.

  • Private Fano method: The private Fano method lower bounds non-interactive α-private minimax risk using separated distribution families and privatized samples.It combines Fano’s inequality with a variational upper bound on mutual information after privatization.
  • Private Fano method: The private analogue of the mixture distribution is formed from the marginal distributions induced by the privacy channel.For non-interactive channels, the privatized sample distribution is a product distribution.
  • Mean estimation: Sharp private minimax rates follow for compactly supported d-dimensional mean estimation, with matching lower and upper bounds.The lower bound uses private Fano’s method, while the upper bound follows from optimal mechanisms.
  • Mean estimation: The privacy constraint imposes a multiplicative d/α^2 penalty in mean-squared error, reducing effective sample size from n to α^2n/d.For α ∈ [0,1], the large-n rate becomes d/(nα^2), independent of p ∈ [1,2].
  • Sparse mean estimation: For 1-sparse means, local privacy can make high-dimensional estimation impossible when d ≥ n, unlike the non-private scaling d ≍ e^n.The non-interactive result leaves possible localization after important variables are identified to future work.
  • Optimal mechanisms: Optimal mechanisms produce unbiased α-private views and can attain the minimax rate, whereas a Laplacian mechanism has quadratic rather than linear dimension dependence.The optimal d-dimensional mechanism scales linearly in d, while the Laplacian alternative incurs d^2 dependence.

5 Bounds on multiple pairwise divergences: Assouad’s method

The paper develops a private Assouad method that yields minimax lower bounds for interactive local privacy channels and sharp rates in generalized linear and density estimation. Matching private procedures achieve these rates, while suitable mechanisms are essential for optimality.

  • Private Assouad method: Private Assouad bounds apply to any locally differentially private channel, including interactive settings.The method requires a coordinate-wise structure expressed through a Hamming separation condition.
  • Private Assouad method: The bound is based on a variational quantity that jointly compares multiple mixture distributions, generalizing total variation distance.This variational formulation underlies the private Assouad and Fano methods.
  • Generalized linear model estimation: In logistic regression, local privacy produces an effective sample-size degradation from n to n(e^α−1)^2.The lower bound shows that private estimators cannot generally outperform the stochastic-gradient convergence guarantee.
  • Generalized linear model estimation: Private stochastic-gradient estimators achieve asymptotic MSE of order ∥∇^2A(θ⋆)−1∥^2/(nα^2) under either ℓ2- or ℓ∞-sampling, with the corresponding bounded-data assumptions.The ℓ2 result assumes data in an ℓ2-ball of radius r, while the ℓ∞ result assumes data in an ℓ∞-ball of radius r.
  • Density estimation: For Lipschitz density estimation, the locally private rate is n^−1/2 rather than the classical n^−2/3.More generally, the private exponent is 2β/(2β+2), compared with 2β/(2β+1) classically.
  • Density estimation: Orthogonal projection estimators attain the sharp density-estimation lower bound and are easy to compute, whereas direct Laplace perturbation cannot attain it.For β=1, histogram estimators with Laplacian-noise-perturbed counts achieve the optimal rate; higher smoothness motivates orthogonal-series estimators.

6 Experiments

The experiments evaluate private mean and median estimation on sensitive UC salary data, comparing minimax-oriented procedures with assumptions about moments and median radius. Results show that privacy and modeling assumptions materially affect estimation error.

  • Mean and median salary estimation: The experiments use publicly available sensitive datasets as proxies for evaluating privacy-preserving mechanisms and estimation schemes.The salary experiments use 2010 UC salaries from a population of 252,540 employees, with mean salary $39,531 and median salary $24,968.
  • Mean salary estimation: For heavy-tailed salary data, choosing approximately k ≈3 moments substantially improves truncated-mean estimation.Assuming bounded data produces high variance and large radii, while assuming too few moments slows convergence.
  • Mean salary estimation: At α = 1, the best private mean estimator incurs approximately 6% mean absolute error, versus 0.2% for a non-private estimator using half the population.Table 1 selects the best moment k post hoc for each privacy level.
  • Median salary estimation: The median experiments compare minimax-optimal stochastic gradient descent with a naive estimator that adds noise to truncated individual salaries.The naive estimator uses Zi = Π[−r,r](Xi) + Wi and takes the median of the privatized observations.
  • Median salary estimation: The median study varies the assumed radius across r ∈ {1.5, 2, 4, 8, 16} med(P) and performs private stochastic gradient steps from a random initialization.The SGD procedure samples observations without replacement and uses the specified stepsizes and averaged predictor.

2. We compute the naive private median (41) with Wi

The experiments apply private estimation to drug-use proportions and censorship prediction, comparing minimax-oriented mechanisms with Laplace noise and non-private estimation. Across these settings, dimensionality and mechanism choice strongly influence utility.

  • Drug use and hospital admissions: The drug-use experiment constructs binary admission vectors preserving marginal frequencies from 959,715 emergency-department visits across 27 drugs.Each coordinate indicates whether an admittee used a particular drug.
  • Drug use and hospital admissions: The drug-use comparison evaluates an ℓ∞-sampling strategy against coordinatewise Laplace noise and a non-private subsampled-vector average.Each private observation is produced from a sample of size n = ⌈2N/3⌉.
  • Drug use and hospital admissions: For drug-use data, the optimal private sampling strategy outperforms the equally private Laplace mechanism, with mean error roughly 5 times lower.The comparison estimates 27 drug-use proportions from hospital-admission data.
  • Censorship, privacy, and logistic regression: The logistic-regression experiments predict censorship of Chinese blog posts using either 458 relatively rare words or 24 common words.The dataset contains 190,000 posts, including 90,000 censored and 100,000 uncensored posts.
  • Censorship, privacy, and logistic regression: Privacy causes non-trivial classification degradation, with larger degradation at approximately 450 dimensions than at 24 dimensions.In the higher-dimensional case, the Laplace mechanism is essentially random guessing, whereas the minimax-oriented ℓ2 mechanism performs better.
  • Censorship, privacy, and logistic regression: The ℓ2-optimal randomized-response strategy generally dominates Laplace noise addition, although Laplace performs better in several individual tests.For the 458-word case, Laplace wins three tests at α = 1, one at α = 2, and two at α = 4; for 24 words, it wins two, one, and zero tests.

7 Conclusions

The paper links minimax statistical decision theory with local differential privacy to derive sharp estimation rates and assess the privacy–utility tradeoff. It also identifies unresolved extensions and emphasizes potentially substantial accuracy losses, especially in high dimensions.

  • Contributions: The paper’s central contribution is connecting minimax analysis from statistical decision theory with differential privacy.The framework treats privacy as a constraint on estimators rather than tying analysis to one procedure or mechanism.
  • Contributions: Differentially private sampling acts as a contraction on distributions, enabling private analogues of Le Cam’s, Fano’s, and Assouad’s minimax lower bounds.The resulting divergence inequalities appear in Theorems 1–3 and support Propositions 1–3.
  • Implications: The resulting tools provide sharp minimax rates for estimation under local privacy and support a continuum for trading privacy against accurate statistical estimates.The continuum is intended to help adjust procedures to privacy or utility needs.
  • Open questions: Open questions include tensorized inequalities for interactive mechanisms and extensions to standard non-local differential privacy or other disclosure limitations.Such extensions could inform optimal mechanisms for additional private procedures.
  • Limitations and outlook: Several results are pessimistic: differential privacy may impose a significant loss in inferential accuracy, particularly in high-dimensional settings.The conclusion motivates further work on mechanisms that retain privacy strengths while mitigating undesirable effects on inference.

A.2 Proof of Corollary 3

This proof derives a conditional-divergence bound for locally private observations by combining the chain rule for KL divergence with the single-observation privacy theorem. Conditional independence then yields the claimed result.

  • Proof strategy: The proof defines each privatized observation’s conditional distribution given preceding outputs and applies the KL chain rule.The conditional distribution integrates over the corresponding latent sample coordinate.
  • Proof strategy: Local differential privacy bounds each conditional privatization channel, allowing Theorem 1 to control the corresponding conditional divergence.The argument uses the distribution of Xi conditioned on the packing index and prior privatized outputs.
  • Proof conclusion: Conditional independence of the Xi given the packing index makes the conditional law Pν(i)(· | z1:i−1) equal to Pν(i), producing the claimed bound.The proof concludes after substituting this simplification into the chain-rule expression.

B.1 Proof of Corollary 1

The proof establishes the minimax rate by combining a Le Cam lower bound with a truncation-and-Laplacian-noise estimator for the matching upper bound.

  • Proof strategy: The proof is divided into lower- and upper-bound arguments for α ∈(0, 1], with analogous results for finite α.The lower bound uses Le Cam’s method, while the upper bound uses truncation and Laplacian noise.
  • Lower bound: Le Cam’s construction uses two distributions supported on {−δ−1/k, 0, δ1/k} whose means differ by 2δk.The distributions satisfy E[|X|^k] = 1, enabling a moment-constrained testing reduction.
  • Lower bound: Pinsker’s inequality and the private testing bound convert the channel-divergence control into the lower bound in equation (9).The argument applies to the marginal distributions of the privatized samples conditioned on the two hypotheses.
  • Upper bound: The upper-bound estimator clips each Xi to [−T, T] and adds independent Laplace noise with scale determined by α/(2T).The resulting Zi is α-differentially private for Xi, and the mean estimator is built from the privatized observations.
  • Upper bound: Choosing T = (nα2)1/(2k) yields the upper bound in equation (9).The truncation bias is controlled using the moment assumption and Markov’s inequality before balancing it with the privacy noise.

C.1 Proof of Theorem 2

The proof reduces the general privacy-information inequality to finite-output mechanisms, then combines packing, mutual-information control, and a private Fano argument.

  • Finite-domain reduction: The proof first reduces the output domain to finite partitions, proving the claim for finite Z before taking a supremum over partitions.This reduction represents the mechanism through probability mass functions on a finite alphabet.
  • Finite-domain reduction: Differential privacy bounds the conditional probability mass functions through the function class Fα and its centered version.Subtracting the x-independent infimal measure m0(z) changes the range to [0, eα −1]m0(z).
  • Variational bound: The proof bounds the resulting variational expression and concludes the theorem after using that the centered baseline masses sum to at most one.The final inequality is obtained by combining the preceding bounds.
  • Information control: For non-interactive mechanisms, product structure and conditional independence allow mutual information to be decomposed across privatized observations.The chain rule and entropy inequalities reduce the information calculation to single-observation terms.
  • Lower-bound template: The broader lower-bound template reduces estimation to multi-way testing, constructs a well-separated packing, and controls information using Theorem 2.Uniform sampling makes it possible to choose packings whose covariance has relatively small operator norm.

D.1 Proof of Corollary 4

The proof of Corollary 4 develops private minimax lower bounds through carefully designed packings, mutual-information bounds, and Fano testing reductions, then supplies matching upper-bound arguments.

  • Packing constructions: The lower-bound framework constructs well-separated distribution families indexed by hypercubes or sparse signed-coordinate sets.These families produce separated mean vectors while respecting the relevant support or norm constraints.
  • Packing constructions: A single-coordinate sampling scheme yields mean vectors forming a 2t/k-separated set with logarithmic packing ratio at least max{k/6, 2}.The construction samples a coordinate uniformly and assigns a distribution depending on the packing index.
  • Packing constructions: A denser product sampling scheme provides analogous separation of order 2t/k1/p and supports lower bounds over ℓp-bounded distributions.The proof uses independent coordinates with probabilities determined by the packing vector.
  • Sparse estimation: For sparse mean estimation, a ±ej packing gives 2δr separation and leads to an ℓ1-regularized estimator for the matching upper bound.The upper-bound analysis controls privatized coordinates and applies Hoeffding’s inequality with a union bound.
  • Sparse estimation: The upper-bound probability control yields the claimed minimax rate after choosing λ appropriately, with a d log d/n term appearing in the bound.The construction uses bounded privatized observations and a sparsity-aware optimization problem.
  • Laplacian sampling: A Varshamov-Gilbert packing of the hypercube supplies the combinatorial ingredient for the Laplacian sampling lower bound.The selected packing has cardinality at least exp(d/8), after which Fano’s inequality is applied.

E Proof of Theorem 3

Theorem 3’s proof combines interactivity-specific independence arguments with variational bounds to control summed divergences under local privacy.

  • Independence structure: The proof begins by exploiting the independence structure in Figure 2 to establish a tensorization-relevant marginalization claim.This separates the interactive proof’s dependence structure from the later variational argument.
  • Divergence control: For each coordinate and observation, the proof tracks conditional KL divergences between the two hypotheses and then sums them over coordinates.The chain rule for KL divergence organizes these conditional contributions in the interactive setting.
  • Variational reduction: Finite-output reduction and conditional probability mass functions allow the argument to work with m±j,i and an infimal measure m0.The infimal measure is defined pointwise over possible inputs and conditional histories.
  • Variational reduction: Differential privacy rescales the inner supremum by eα −1, producing the penultimate inequality in the variational bound.The proof parallels the finite-domain argument used for Theorem 2.
  • Conclusion: The final step uses that m0 has total mass at most one to complete the proof of the theorem.The result follows after substituting the preceding expression into inequality (54).

F Proof of logistic regression lower bound

The proof establishes the logistic-regression lower bound by reducing estimation to symmetric binary hypothesis testing and controlling testing error under local privacy.

  • Reduction to testing: The proof reduces estimation to identifying a binary vector through a Hamming-separated family of logistic-model parameters.It sets V={−1,1}^d, θν=δν, and constructs distributions whose conditional structure yields the standard logistic model.
  • Privacy contraction: The private testing error is controlled using Theorem 3, whose application requires bounding suprema determined by the covariance structure of the symmetric packing.Symmetry of V={−1,1}^d simplifies these covariance-related quantities.
  • Reduction to testing: The constructed distributions have θν as the population logistic-loss optimizer, linking parameter recovery to binary sign recovery.For any estimator, the signs of its coordinates define a binary decision vector, enabling a Hamming-separation lower bound.
  • Conclusion: Applying Theorem 3 and the resulting divergence inequalities yields the desired logistic-regression lower bound via the sharper Assouad argument.The intermediate expressions aggregate the coordinatewise testing contributions appearing in the Assouad reduction.
  • Privacy contraction: The proof bounds the required variational quantities using symmetry, Jensen’s inequality, and orthogonality of an associated matrix representation.The vectors indexed by coordinate signs are identified with columns of a binary transform, making standard matrix inequalities applicable.

G Proof of Corollary 7

The density-estimation proof constructs smooth hypercube packings and applies Assouad’s method with a locally private divergence bound to obtain the minimax lower bound, while optimizing the packing dimension for the upper bound.

  • Lower bound: Local packing is used instead of global metric entropy because it is better suited to the privacy constraints and information contractions developed in the paper.The proof explicitly contrasts this construction with the global metric-entropy approach of Yang and Barron.
  • Constructing well-separated densities: The proof constructs well-separated β-smooth densities by placing signed smooth bump functions on subintervals of [0,1].The resulting family is indexed by hypercube corners and remains within the β-smooth density class.
  • Lower bound: The density-estimation lower bound reduces to identifying hypercube corners, enabling application of the sharper Assouad lemma.The sign vector associated with each density supplies the discrete parameter used in the reduction.
  • Privacy-sensitive divergence bound: For α≤1, the summed KL-divergence bound becomes cnα^2/k^(2β+1), improving the standard Assouad scale n/k^(2β) by roughly a factor k.The improvement follows from the locally private channel bound in Lemma 9.
  • Upper bound: The upper-bound calculation chooses k=(nα^2)^(1/(2β+2)) to complete the mean-squared L2-error bound.The optimized packing dimension balances the terms in the preceding error expression.

I.3 Proof of unbiasedness for sampling strategy (26)

The proof computes conditional expectations for the sampling strategy separately for odd and even dimensions, using hypercube symmetry and correcting constant multipliers to establish unbiasedness.

  • Odd dimensions: The proof evaluates the sampling strategy’s conditional expectations by exploiting symmetry over sign vectors in the hypercube.The odd-dimensional case uses the equal split of sign vectors having positive inner product with a fixed x.
  • Even dimensions: For even dimensions, the calculation accounts for sign vectors whose inner product with x equals zero.This adds one extra vector to the nonnegative-inner-product set compared with the strictly positive case.
  • Conclusion: After inverting the resulting constant multipliers, the sampling strategy is unbiased.The correction applies to the vectors x in the preceding expectation formulas.
Loading 1604.02390v2…