PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates

John C. Duchi, Michael I. Jordan, Martin J. Wainwright

arXiv:1302.3203v4math.STcs.CRcs.ITmath.ITstat.TH

TL;DR

The paper asks how local privacy, which keeps data private even from the statistician, affects statistical estimation. It derives information inequalities and applies minimax methods to canonical problems; the resulting rates characterize privacy’s effect on effective sample size and estimation accuracy. The analysis also notes that optimal private mechanisms can complicate errors-in-variables procedures.

  • Problem

    The paper investigates how to balance statistical utility with privacy when data providers do not trust the statistician collecting their data.

    Source: §1 · pp. 2–3

  • Method

    It derives privacy-dependent information inequalities and combines them with Le Cam, Fano, and Assouad minimax techniques to bound estimation risk.

    Source: §1 · p. 1, §2 · p. 5

  • Results

    For many d-dimensional estimation problems, local privacy reduces effective sample size from n to nα^2/d.

    Source: §3.2 · p. 9

  • Takeaways & Limitations

    The analysis identifies a continuum for trading privacy against utility through accurate statistical estimates.

    Source: §10 · p. 38

    In errors-in-variables models, the analyzed optimal strategies are more complicated than adding noise directly to covariates, complicating estimation procedures.

    Source: §6.3 · p. 27

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 utility of the resulting statistical estimators. We prove bounds on information-theoretic quantities, including mutual information and Kullback-Leibler divergence, that depend on the privacy guarantees. When combined with standard minimax techniques, including the Le Cam, Fano, and Assouad methods, these inequalities allow for a precise characterization of statistical rates under local privacy constraints. We provide a treatment of several canonical families of problems: mean estimation, parameter estimation in fixed-design regression, multinomial probability estimation, 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.

1 Introduction

The paper examines how to balance statistical utility with privacy, focusing on local privacy, where data providers do not trust the statistician collecting their data. It brings differential privacy into statistical decision theory, deriving minimax bounds and applying them to canonical estimation problems.

1 Introduction

  • The analysis treats privacy as an abstract constraint on estimators and derives minimax lower bounds using Le Cam, Fano, and Assouad, with matching upper bounds from specific private procedures.The framework targets estimation of population quantities, unlike much prior privacy work focused on approximating statistics from fixed data.Source: §1 · pp. 1–2, §1.1 · p. 3
  • The local-privacy model allows interactive channels that depend on prior private observations, as well as non-interactive channels in which each private view depends only on its corresponding observation.The paper defines an α-locally private view through a bound on conditional probabilities across possible data values.Source: §1 · p. 2
  • Differential privacy can constrain disclosure, but its stringency has raised concerns about poor utility; the paper investigates whether methods can be optimal and how privacy trades off against statistical efficiency.The paper focuses on local privacy, where providers do not trust the statistician collecting their data.Source: §1 · pp. 2–3

1.1 Our contributions

  • The paper applies its techniques to mean estimation, fixed-design regression, multinomial probability estimation, and density estimation, deriving minimax rates for these population-level problems.It identifies Warner’s randomized response as an optimal mechanism for multinomial estimation.Source: §1.1 · pp. 3–4
  • For α^2 < 1, the information bounds imply that local privacy can reduce effective sample size from n to at most α^2n for problems amenable to classical information-theoretic minimax methods.For a mean with variance at most 1, the minimax estimation rate changes from 1/n to 1/(nα^2).Source: §1.1 · p. 4
  • Theorems 2 and 3 extend the information bounds with dimension-dependent analogues of total variation, supporting Fano-based mutual-information bounds and Assouad-based summed KL-divergence bounds.For many d-dimensional problems, the effective sample size is reduced from n to nα^2/d.Source: §1.1 · p. 4

2 Background and problem formulation

The section formulates private estimation as a minimax problem in which an estimator uses privatized observations to estimate a population parameter. It reduces lower-bound arguments to hypothesis testing and controls testing difficulty through variation distance or mutual information.

2 Background and problem formulation

  • In the local-privacy setting, a conditional distribution Q transforms the original sample into private observations Z, from which an estimator must recover the unknown parameter.The minimax risk measures estimation error under a chosen loss, with the worst case taken over the distribution class and the best estimator chosen from functions of Z.Source: §2 · p. 5
  • The α-minimax rate minimizes the minimax risk over all conditional distributions that guarantee α-local privacy.The risk is defined using a parameter-space semimetric and a non-decreasing loss function.Source: §2 · p. 5
  • A standard lower-bound reduction constructs a finite family of distributions whose parameters are separated, then tests which family member generated the private sample.Le Cam’s inequality applies to two hypotheses, while Fano’s inequality applies to a uniformly chosen index from a larger finite family.Source: §2 · pp. 5–6
  • For hypercube-indexed families, Assouad’s method reduces estimation to multiple binary tests, with a lemma bounding error through coordinate-wise testing difficulty.The section then relates private minimax bounds to total variation between marginals or mutual information between the private sample and the random index.Source: §2 · pp. 6–7

3 Pairwise bounds under privacy: Le Cam and local Fano methods

The section develops information-theoretic bounds for local privacy and applies them with Le Cam and local Fano methods to derive minimax results. Its applications show how privacy changes effective sample size and estimation rates for means and fixed-design regression.

3.1 Pairwise upper bounds on Kullback-Leibler divergences

  • Theorem 1 bounds post-channel KL divergence using the privacy parameter and the input distributions’ total variation distance, contracting even pairs with infinite KL divergence.This contraction supports the section’s minimax lower bounds.Source: §3.1 · p. 7

3.2 Consequences for minimax theory under local privacy constraints

  • Under α-local privacy, Le Cam and local Fano methods reduce the effective sample size from n to 4α²n.The section applies the private forms of both methods to minimax bounds.Source: §3.2 · pp. 8–9

3.3 Some applications of Theorem 1

  • The applications show that mean estimation can lose more effective sample size than α²n, while fixed-design regression has a reduction from n to α²n.The stated bounds assume α∈[0,1] and extend, with different constants, to α∈[0,C] for a universal constant C.Source: §3.3 · p. 10

3.3.1 One-dimensional mean estimation

  • For finite-variance mean estimation, the private minimax rate is 1/(nα²); as the moment order grows, the bounded-domain rate becomes (nα²)^-1.The moment condition E[|X|^k]≤1 approaches the constraint |X|≤1 almost surely as k increases.Source: §3.3.1 · p. 10

3.3.2 Linear regression with fixed design

  • With orthonormal design, regression risk is σ²d/(nα²) versus the classical σ²d/n; adding Laplace noise to responses attains the private upper bound.The analysis assumes bounded noise and a full-rank design; more generally, the rate depends on the design’s largest and smallest singular values.Source: §3.3.2 · p. 11

4 Mutual information under local privacy: Fano’s method

This section develops variational mutual-information bounds for local privacy and applies them with Fano’s method to mean-estimation rates. It also gives matching private mechanisms and identifies Laplace perturbation as sub-optimal for one mean-estimation setting.

4.1 Variational bounds on mutual information

  • Theorem 2’s variational mutual-information bound is never weaker than Theorem 1’s and can sharpen Fano bounds when the supremum–summation interchange is loose.The section uses the stronger bound because Theorem 1’s pairwise-distance bounds require local packings for Fano’s inequality in full generality.Source: §4 · p. 11, §4.1 · pp. 12–13
  • Corollary 4 extends the mutual-information bound to repeated independent sampling under non-interactive privacy; packings with small operator-norm functionals can yield sharper results.Source: §4.1 · p. 13

4.2.1 Minimax rates

  • Under non-interactive α-local privacy, d-dimensional mean estimation reduces effective sample size from n to nα²/d, a d/α² mean-squared-error penalty for p∈[1,2].The result concerns squared ℓ2 error for distributions supported on the specified ℓp-ball.Source: §4.2 · p. 13, §4.2.1 · p. 15
  • For ℓ∞ loss, Proposition 4 likewise shows a privacy-related efficiency loss, illustrated by comparing its rate with the classical sub-Gaussian mean rate for ℓ∞-bounded observations.Source: §4.2.1 · p. 15
  • For 1-sparse means, the non-interactive local-privacy setting makes high-dimensional estimation effectively impossible.The sparse setting assumes the mean has at most one nonzero entry.Source: §4.2.1 · pp. 15–16

4.2.2 Optimal mechanisms: attainability for mean estimation

  • Strategies (26a) and (26b) attain the mean-estimation upper bounds using unbiased stochastic perturbations followed by a standard mean estimator.The mechanisms use the ℓ2-ball and ℓ∞-ball sampling strategies, respectively, with bounds chosen to ensure unbiasedness.Source: §4.2.2 · pp. 16–17
  • For distributions supported on the ℓ2 unit ball, Laplace perturbation has poorer dimension dependence than Proposition 3, making it strictly sub-optimal in that setting.Source: §4.2.2 · p. 17

5 Bounds on multiple pairwise divergences: Assouad’s method

A privatized Assouad method uses bounds on paired divergences to obtain sharp minimax lower bounds in interactive settings for decomposable losses. Across multinomial and density estimation, local privacy reduces the effective sample size to nα²/d.

5 Bounds on multiple pairwise divergences: Assouad’s method; 5.1 Variational bounds on paired divergences

  • Theorem 3 generalizes the paired-divergence bound to dimension d, and its combination with Assouad yields sharp lower bounds when the loss is sufficiently decomposable.The method applies in interactive settings, including multinomial and nonparametric density estimation.Source: §5 · p. 17, §5.1 · p. 18

5.2.1 Minimax rates of convergence for multinomial estimation

  • For multinomial probabilities, the minimax error bounds are given under squared ℓ2 and ℓ1 loss for sequentially interactive channels.The ℓ1 loss is linked to total variation distance and testing.Source: §5.2.1 · p. 19

5.2.1 Minimax rates of convergence for multinomial estimation; 5.3.1 Lower bounds on density estimation

  • Local privacy reduces the effective sample size from n to nα²/d for multinomial estimation, while the private density-estimation rate has a different polynomial exponent from the classical rate.For Lipschitz densities, the rate changes from n^-2/3 to n^-1/2.Source: §5.2.1 · p. 19, §5.3.1 · p. 21

5.2.2 Optimal mechanisms: attainability for multinomial estimation

  • A randomized-response variant is an optimal mechanism for α-locally private multinomial estimation, and its simplex-projection estimator is efficiently computable.The projection can be computed in time linear in dimension d.Source: §5.2.2 · pp. 19–20

5.3.1 Lower bounds on density estimation

  • Direct Laplace or exponential perturbation of observations cannot attain the private density lower-bound rate, so alternative privacy mechanisms are needed.The paper attributes this limitation to the deconvolution rate under additive noise.Source: §5.3.1 · p. 21

5.3.2 Achievability by histogram estimators

  • For any fixed α > 0, the privatized histogram estimator is minimax-optimal for Lipschitz densities, matching the lower bound at rate O((α²n)^-1/2).The histogram uses k = (nα²)^(1/4) bins.Source: §5.3.2 · p. 22

5.3.3 Achievability by orthogonal projection estimators

  • The private density minimax lower bound is sharp: an orthogonal-series estimator attains it for Sobolev smoothness orders β ≥ 1.The construction uses k = (nα²)^(1/(2β+2)) basis terms when the basis is uniformly bounded.Source: §5.3.3 · pp. 22–23
  • Orthogonal-series density estimators using Laplace perturbation are suboptimal, achieving at best a rate polynomially worse than the sharp bound.The paper identifies appropriately chosen noise mechanisms as important for attaining optimal results.Source: §5.3.3 · p. 24

6 Comparison to related work

The comparison distinguishes population-based inference from conditional risk analyses and contrasts local privacy with non-local privacy. It also notes computational complications when locally private mechanisms are used in errors-in-variables models.

6 Comparison to related work

  • The paper distinguishes its population-based convergence-rate analysis from PAC learning results, which characterize learning equivalences up to polynomial sample-size changes.Its focus is finer-grained assessment of inferential procedures and their rates of convergence and optimality.Source: §6 · p. 24

6.1 Sample versus population estimation

  • Population minimax risk lower bounds conditional minimax risk, but conditional-risk lower bounds do not imply population estimation rates; the two risks can differ substantially.For a normal location family, population mean estimation is possible under local privacy while conditional minimax risk is infinite.Source: §6.1 · pp. 25–26

6.2 Local versus non-local privacy

  • Unlike the non-local examples discussed, where privacy affects only higher-order terms when n ≫ d, local privacy can make Laplace mechanisms highly suboptimal.The passage notes similar non-local patterns for histogram, classification, and classical point estimation.Source: §6.2 · pp. 26–27

6.3 Error-in-variables models

  • Optimal local privacy mechanisms in errors-in-variables models are more complicated than direct covariate noise, and efficient nonlinear procedures remain an open direction.Known efficient procedures may require solving integrals or equations, or non-convex optimization.Source: §6.3 · p. 27

7 Proof of Theorem 1 and related results

The proofs combine local-privacy divergence bounds with classical minimax arguments. They establish bounds for mean estimation and fixed-design regression using complementary lower- and upper-bound constructions.

7.1 Proof of Theorem 1

  • Theorem 1’s proof bounds differences between marginal densities and their log ratios using auxiliary results for locally private conditionals.The proof establishes the density bounds before combining them to complete the theorem.Source: §7.1 · pp. 27–28

7.2 Proof of Corollary 1

  • The Corollary 1 proof applies the KL chain rule to conditional privatized observations and uses local privacy to bound the resulting divergences.The sample variables are conditionally independent given the packing index.Source: §7.2 · pp. 29–30

7.3 Proof of Proposition 1

  • For mean estimation, the upper bound uses truncation followed by Laplace noise, while the lower bound uses a two-point Le Cam comparison.The construction assumes a bounded kth moment, E[|X|^k] ≤ 1.Source: §7.3 · pp. 30–31

7.4 Proof of Proposition 2

  • For fixed-design regression, the upper-bound proof adds Laplace noise to responses and uses least squares, while the lower bound uses Fano’s inequality and a packing of the unit sphere.The lower-bound construction assumes uniform response noise on [−σ, +σ].Source: §7.4 · pp. 32–33

8 Proof of Theorem 2 and related results

The proofs reduce the relevant divergence bound to finite output partitions, then use the mutual-information chain rule for the non-interactive case.

8.1 Proof of Theorem 2

  • Theorem 2’s proof reduces the output space to finite partitions, proves the bound for a finite range, and takes a supremum over partitions to recover the general case.It defines a lower envelope of channel probabilities to bound the final sum.Source: §8.1 · pp. 34–35

8.2 Proof of Corollary 4

  • For Corollary 4, non-interactive outputs are conditionally independent given the packing index, so the mutual-information chain rule and Theorem 2 complete the bound.The proof also reduces without loss of generality to a finite output range.Source: §8.2 · p. 35

9 Proof of Theorem 3

The proof combines conditional KL-divergence calculations with the channel’s independence structure to establish tensorized bounds.

9 Proof of Theorem 3

  • For each output history, the proof lower-bounds conditional channel probabilities by an infimal measure before bounding the expression in inequality (55).It takes the inner supremum independently of the output and history, rescales by e^α − 1, and uses that the infimal measure sums to at most one.Source: §9 · pp. 36–38
  • The proof uses conditional independence and the independence of each observation from previous private outputs to justify a marginalization step.It then applies the KL chain rule, symmetrizes divergence, and sums over coordinates.Source: §9 · pp. 36, 38

10 Conclusions

The paper connects local differential privacy with statistical decision theory through divergence contraction, using it to derive sharp minimax rates. It also outlines a packing-and-information strategy for multidimensional mean-estimation lower bounds and identifies extensions as open questions.

10 Conclusions

  • Divergence inequalities show that private sampling contracts distributions, enabling sharp minimax rates for locally private estimation.The authors describe this framework as potentially more generally applicable.Source: §10 · p. 38
  • The paper characterizes a continuum trading privacy against utility in accurate statistical estimates, allowing procedures to be adjusted to privacy or utility needs.The conclusion grounds this claim in sharp convergence rates for standard procedures under local differential privacy.Source: §10 · p. 38
  • Open questions include tensorized inequalities for interactive mechanisms and extending the results to standard, non-local differential privacy.The authors note that such extensions could inform optimal mechanisms for differentially private procedures.Source: §10 · p. 38

A Proofs of multi-dimensional mean-estimation results

  • The multidimensional mean-estimation lower-bound proof reduces estimation to testing, constructs a separated packing with controlled covariance, then bounds mutual information.The final step applies Theorem 2 and controls Corollary 4’s supremum using the packing covariance’s operator norm.Source: A Proofs of multi-dimensional… · p. 39

A.1 Proof of Proposition 3

These proof sections establish lower-bound arguments for mean-estimation settings by constructing separated hypotheses and controlling information under local privacy; they also give an upper-bound argument for sparse estimation.

A.1 Proof of Proposition 3

  • A hypercube packing with at least exp(k/16) points supports a Fano lower-bound argument for multidimensional mean estimation.The proof constructs distributions whose mean vectors lie in the ball and are separated, then bounds mutual information for non-interactive locally private channels.Source: §A.1 · pp. 39–40

A.2 Proof of Proposition 4

  • The proof of Proposition 4 uses the packing {±e_j} and an information bound for non-interactive private distributions before applying Fano’s inequality.Its constructed mean vectors are separated in ℓ∞ norm.Source: §A.2 · p. 41

A.3 Proof of Proposition 5

  • For Proposition 5, an ℓ1-regularized estimator and the sampling scheme are analyzed with Hoeffding’s inequality and a union bound to obtain the claimed sparse-estimation upper bound.The argument assumes the true mean is s-sparse and selects λ proportional to d log d/(nα²).Source: §A.3 · pp. 41–42

A.4 Proof of inequality (30)

  • Inequality (30) is proved using private Fano and a Laplacian sampling scheme, with δ² chosen as d²/(48nα²).The proof uses a Varshamov–Gilbert hypercube packing.Source: §A.4 · p. 42

B Proofs of multinomial estimation results

The multinomial proof reduces estimation to binary testing and uses privacy-dependent information bounds to derive lower bounds; the density-estimation appendix introduces bump functions for packing its function class.

B Proofs of multinomial estimation results

  • The multinomial lower-bound proofs use Assouad’s reduction to binary tests, with Theorem 3 controlling testing error and symmetry removing the need for carefully designed packings.The Euclidean-error proof is given first, followed by the ℓ1-error argument.Source: B Proofs of multinomial estimation… · p. 43
  • The multinomial lower-bound argument applies Theorem 3 to bound sums of signed measure differences, then chooses δ² = min{1, d²/(16n(e^α − 1)²)}.For the ℓ1-error case, the proof changes the separation factor and repeats the parallel argument.Source: B Proofs of multinomial estimation… · pp. 43–44

C Proofs of density estimation results

C.1 Proof of Proposition 7

The density-estimation proofs use local packings and private divergence bounds to establish rates, and examine both projection-based and orthogonal-series estimators. They also show a limitation of standard Laplace perturbation and construct separated hypercube packings.

C.1 Proof of Proposition 7

  • The density-estimation proof constructs smooth densities as corners of a hypercube and uses local packings suited to privacy constraints.The authors state this approach is better suited to their privacy constraints and information contractions than global metric entropy.Source: §C.1 · pp. 45–46
  • The local-packing argument yields a KL-divergence bound roughly a factor of k tighter than the standard Assouad bound of roughly n/k^(2β).For α ≤ 1, the bound is cnα²/k^(2β+1).Source: §C.1 · p. 47

C.2 Proof of Proposition 8

  • Projecting the estimator onto the scaled probability simplex can only decrease its L2 error, so it suffices to bound the unprojected estimator.Πk projects (k/n)∑ Zi onto the scaled probability simplex.Source: §C.2 · p. 47

C.3 Proof of Proposition 9

  • Choosing k = (nα²)^(1/(2β+2)) completes the proof of the orthogonal-series estimator bound.The coefficient estimates have expectation θj and are bounded by B.Source: §C.3 · p. 48

C.4 Insufficiency of Laplace noise for density estimation

  • Standard Laplace noise added to basis expansions degrades the density-estimation rate, but this does not prove every Laplace-based approach is suboptimal.The construction perturbs k basis coefficients with independent Laplace noise.Source: §C.4 · p. 49

D.1 Proof of Lemma 5

  • A d-dimensional hypercube packing has size at least exp(d/8), with pairwise L1 separation at least d/2.Source: §D.1 · p. 49

D.2 Proof of Lemma 6

The appendix constructs separated vector packings and reduces information-bound arguments to structured finite-dimensional problems. It also collects technical proofs used in these arguments.

D.2 Proof of Lemma 6

  • Taking t = 24 and N = ⌈exp(k/16)⌉ makes the stated bound less than 1, proving existence of a packing satisfying the constraints.Source: §D.2 · p. 50

E.1 Proof of Lemma 7

  • The mutual-information proof applies Theorem 2 after representing functions on the finite set X as vectors.The argument assumes radius r = 1 without loss of generality.Source: §E.1 · pp. 50–51

E.2 Proof of Lemma 8

  • For X = {−1, 1}^d, the proof represents sign patterns as vectors and uses orthogonality among the resulting Hadamard-transform columns.Source: §E.2 · pp. 51–52

E.3 Proof of Lemma 10

  • For Lemma 10, the information-bound supremum can be reduced to functions constant on intervals and then to a finite-dimensional problem.The proof restricts attention to extreme points taking values in {−1, 1}.Source: §E.3 · pp. 52–53

F Technical arguments

F.1 Proof of Lemma 1

The appendix derives a testing bound, verifies a sampling strategy’s properties, and gives a non-compact example where local privacy has an extreme effect on minimax risk.

F.1 Proof of Lemma 1

  • The proof of Lemma 1 derives its testing bound by averaging over separated parameter mixtures and then taking the infimum over testing procedures.Source: §F.1 · pp. 54–55

F.2 Proof of unbiasedness for sampling strategy (26a)

  • For α ≤ 1, the sampling strategy has output norm bounded by 8r.The proof uses rotational symmetry to evaluate its expectation.Source: §F.2 · pp. 55–56

G Effects of differential privacy in non-compact spaces

  • With variance-one distributions on the real line and finite α, the example has infinite minimax risk, unlike the non-private sample mean’s 1/n risk.The construction is described as contrived, but the authors note it shows that a parametric non-private rate need not have a locally private counterpart.Source: G Effects of differential privacy in… · p. 56

Related papers

Loading 1302.3203v4…