PaperlayerView exact revision on arXiv

Source-linked AI summary

The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy

T. Tony Cai, Yichen Wang, Linjun Zhang

arXiv:1902.04495v5stat.MLcs.CRcs.DScs.LG

TL;DR

The paper asks how much statistical accuracy is sacrificed to protect privacy in mean estimation and linear regression across low- and high-dimensional settings. It refines tracing-adversary arguments to prove minimax lower bounds and constructs efficient private algorithms matching them up to logarithmic factors. Simulations and real-data analyses report robust computational performance and accuracy gaps between private and non-private methods.

  • Problem

    The paper quantifies the privacy–accuracy tradeoff and seeks minimax-optimal estimation rates for mean estimation and linear regression under (ε, δ)-differential privacy.

  • Method

    The paper refines tracing-adversary lower-bound arguments and designs computationally efficient private algorithms, including a private iterative hard-thresholding method for sparse regression.

  • Results

    The proposed algorithms attain corresponding minimax lower bounds up to logarithmic factors, with numerical studies showing robust performance and shrinking but non-vanishing private–non-private accuracy gaps.

  • Takeaways & Limitations

    The theoretical and numerical results characterize the accuracy sacrifice required by differential privacy for the studied estimation problems.

  • Takeaways & Limitations

    The scope is limited to mean estimation and linear regression, while broader problems and more general privacy-preserving design and lower-bound techniques remain future work.

Abstract

from arXiv · show

Privacy-preserving data analysis is a rising challenge in contemporary statistics, as the privacy guarantees of statistical methods are often achieved at the expense of accuracy. In this paper, we investigate the tradeoff between statistical accuracy and privacy in mean estimation and linear regression, under both the classical low-dimensional and modern high-dimensional settings. A primary focus is to establish minimax optimality for statistical estimation with the $(\varepsilon,δ)$-differential privacy constraint. To this end, we find that classical lower bound arguments fail to yield sharp results, and new technical tools are called for. By refining the "tracing adversary" technique for lower bounds in the theoretical computer science literature, we formulate a general lower bound argument for minimax risks with differential privacy constraints, and apply this argument to high-dimensional mean estimation and linear regression problems. We also design computationally efficient algorithms that attain the minimax lower bounds up to a logarithmic factor. In particular, for the high-dimensional linear regression, a novel private iterative hard thresholding pursuit algorithm is proposed, based on a privately truncated version of stochastic gradient descent. The numerical performance of these algorithms is demonstrated by simulation studies and applications to real data containing sensitive information, for which privacy-preserving statistical methods are necessary.

1. Introduction.

The paper studies the privacy–accuracy tradeoff in mean estimation and linear regression under (ε, δ)-differential privacy, spanning low- and high-dimensional settings. It develops tracing-based lower bounds and private algorithms that match them up to logarithmic factors.

  • Motivation: Differential privacy protects individuals against adversaries using algorithm outputs, but typically incurs statistical accuracy loss.The paper frames this loss as a quantitative privacy–accuracy tradeoff under minimax risk.
  • Lower bounds: The paper establishes minimax lower bounds for mean estimation and linear regression under (ε, δ)-differential privacy.The results include improved low-dimensional mean-estimation bounds and new bounds for high-dimensional mean estimation and regression.
  • Lower bounds: Tracing adversaries yield lower bounds by showing that an overly accurate private estimator could reveal whether an individual datum appears in the sample.This contradiction with differential privacy prevents the estimator from being too accurate.
  • Algorithms: The proposed differentially private algorithms achieve convergence rates matching the corresponding lower bounds up to logarithmic factors.For high-dimensional sparse estimation, the paper presents what it describes as the first such results under (ε, δ)-differential privacy.
  • Algorithms: The high-dimensional linear-regression method is a private version of iterative hard thresholding, while low-dimensional regression analysis targets parameter-estimation error.The algorithms are designed for sparse estimation when dimension can exceed sample size.
  • Framework: The paper defines the cost of privacy through constrained minimax risk and develops upper- and lower-bound tools for characterizing it.The analysis focuses on mean estimation and linear regression under the stated privacy constraint.

Post-processing and Composition.

The paper refines tracing-adversary arguments to establish sharp differential-privacy lower bounds, then matches them with private estimators for mean-estimation problems. These results characterize privacy costs across low-dimensional and sparse high-dimensional settings.

  • Post-processing and Composition.: Post-processing preserves (ε, δ)-differential privacy when an arbitrary deterministic mapping is applied to a private algorithm’s output.
  • Post-processing and Composition.: Differential privacy guarantees compose additively: composing (ε1, δ1)- and (ε2, δ2)-private algorithms yields (ε1 + ε2, δ1 + δ2)-privacy.
  • Lower-bound technique: The refined tracing-adversary technique converts an overly accurate private estimator into an attack that detects whether a candidate datum belongs to the dataset, yielding minimax lower bounds.
  • Low-dimensional mean estimation: The paper sharpens preliminary low-dimensional mean-estimation lower bounds and establishes rate-optimality through differentially private estimators attaining the lower bound.
  • Low-dimensional mean estimation: For low-dimensional mean estimation, privacy dominates statistical risk when d log(1/δ)/nε^2 ≳ 1; bounded-support rates match the lower bound exactly, while sub-Gaussian rates incur an O(log n) gap.
  • Sparse mean estimation: For sparse mean estimation, the private lower bound depends only logarithmically on dimension d, and the proposed estimator attains it up to logarithmic factors.

5 end

The sparse-mean algorithm truncates the sample mean and privately selects its large coordinates, using bounded sensitivity to preserve privacy. Its convergence rate reaches the sparse lower bound up to a log^2 n factor under stated tuning conditions.

  • Privacy mechanism: The peeling algorithm provides approximate accuracy while selecting a sparse support from the truncated sample mean.
  • Sparse mean estimation algorithm: Algorithm 3 computes a truncated sample mean before privately selecting coordinates for sparse mean estimation.
  • Privacy mechanism: Truncation bounds the change between adjacent datasets, enabling the privacy guarantee for the peeling-based coordinate-selection procedure.
  • Theoretical guarantee: Under R = Kσ√log n, s ≥ s* and s ≍ s*, Algorithm 3 achieves its stated high-probability error guarantee.
  • Theoretical guarantee: With δ = n^−(1+ω), Algorithm 3 reaches the sparse lower bound up to a log^2 n gap, while data-driven tuning is discussed for numerical performance.

4. The Cost of Privacy in Linear Regression.

This section develops privacy lower bounds and efficient algorithms for low- and high-dimensional linear regression. The results show that tracing attacks yield sharp lower bounds, while private gradient-based methods attain them up to logarithmic factors under stated assumptions.

  • Lower bounds: Tracing-adversary arguments establish minimax lower bounds for differentially private linear regression.The argument uses attacks whose values distinguish whether an observation belongs to the sample.
  • Low-dimensional linear regression: Under bounded-design and covariance assumptions, the low-dimensional lower bound is sharp up to factors of log n.A differentially private noisy gradient algorithm is analyzed to match the lower bound at this scale.
  • Practical tuning: The theoretical truncation choice depends on the often unknown noise scale σ, motivating a data-driven differentially private alternative for practice.The paper demonstrates this alternative numerically.
  • High-dimensional linear regression: For sparse high-dimensional regression, the lower bound depends only logarithmically on dimension d and is achieved up to factors of log n by a private algorithm.The construction leverages a sparse-regression modification based on the peeling algorithm.
  • High-dimensional linear regression: When d exceeds n, least-squares minimization becomes inaccurate because the Hessian is rank deficient, so the low-dimensional noisy-gradient method no longer applies.The high-dimensional formulation instead assumes that β is sparse.
  • High-dimensional linear regression: The high-dimensional algorithm uses private truncation and hard-thresholding ideas, with privacy guaranteed under bounded-design, moment, and parameter assumptions.Its tuning includes a sparsity parameter and a noise level calibrated through the truncation level.

5. Simulation Studies.

The simulations evaluate truncation and sparsity tuning across low- and high-dimensional mean estimation and regression. Data-driven tuning performs comparably to theoretical choices, while comparisons with other methods require attention to differing objectives.

  • Experimental design: The experiments compare truncation choices, sparsity tuning choices, and private algorithms with non-private and published differentially private counterparts.They use simulated mean-estimation and linear-regression data under low- and high-dimensional settings.
  • Tuning of truncation level: Data-driven truncation produces errors comparable to no truncation and the theoretical choice of R in the reported Gaussian experiments.The authors caution that this favorable result benefits from Gaussian symmetry and light tails.
  • Experimental design: Figures 1–3 plot average ℓ2-error against sample size under fixed privacy levels across low- and high-dimensional mean estimation and regression settings.The high-dimensional plots vary n while specifying d and sparsity s.
  • Tuning of s: Cross-validation for the sparsity parameter s yields errors comparable to using the true sparsity s∗.The cross-validation errors are privately truncated before applying the exponential mechanism.
  • Comparisons: The reported algorithms show significant performance gaps relative to methods in, but those comparators target accurate test statistics or excess empirical risk.The paper therefore notes that the numerical comparison may not reflect their primary advantages.

6. Data Analysis.

The data analyses evaluate private sparse mean and OLS estimators on sensitive genetic and housing datasets, with errors tracked as sample sizes increase. The experiments compare proposed procedures with existing private methods and non-private OLS, while discussion identifies broader extensions.

  • SNP array analysis: The SNP analysis uses 387 subjects and 2,000 SNPs, focusing on MAF differences between average-IQ and low-IQ groups that are expected to be sparse.The matrix entries encode minor-allele counts, and sparsity reflects differences at only a small number of SNP locations.
  • SNP array analysis: Genetic differentially private mean estimates can report SNP minor allele frequencies while limiting individual-level privacy risks from summary-statistic cross-referencing.The motivation is that MAFs can be calculated from SNP-array means, while an adversary may infer an individual’s presence or absence from genetic summary statistics.
  • SNP array analysis: For m from 50 to 120, the sparse mean estimator’s error is estimated over 100 repetitions with s = 20 and (ε, δ) = (0.5, 10/n^1.1).The estimates are shown in Figure 4(a) and compared with the method in.
  • Housing-price regression: The housing dataset contains 20,640 California census block groups with economic and demographic covariates, and privacy-preserving methods remain desirable despite the absence of individual households.Ordinary summary statistics such as means or medians do not themselves provide differential privacy guarantees.
  • Housing-price regression: For m from 2,000 to 20,000, private OLS error is estimated over 100 repetitions using standardized covariates, with (ε, δ) = (0.5, 10/n^1.1).Figure 4(b) compares the proposed estimator with the method in and measures error against non-private OLS fitted to the full sample.
  • Discussion: The algorithms show robust tuning performance, accuracy comparable to or better than existing private methods, and efficient computation up to sample sizes and dimensions in the tens of thousands.Private and non-private accuracy gaps shrink but remain non-vanishing, matching the cost of privacy described by the theorems.

8. Proofs.

The proofs establish privacy-constrained minimax lower and upper bounds using tracing-adversary ideas, group privacy, concentration, and sparse optimization properties. For private iterative regression, restricted strong convexity and smoothness control optimization while Laplace perturbations are bounded probabilistically.

  • Lower bounds: The lower-bound proof reduces privacy analysis to bounding how often each element of a with-replacement subsample is repeated.Group privacy implies that the relevant privacy loss depends on max_i m_i, the maximum multiplicity.
  • Lower bounds: A two-case analysis of δ’s asymptotic behavior yields high-probability multiplicity bounds sufficient to preserve a useful differentially private lower-bound argument.The dichotomy depends on monotonicity of log(δ)/log(n) and the condition δ < n^−(1+ω).
  • Lower bounds: Conditioning on the nonzero index set S and rescaling the conditional algorithm produces an (ε, δ)-differentially private procedure for the retained sample.The construction defines ˜M(X_S) = α^−1 E[M(X)|S = S] and preserves the relation μ = αE[y_1].
  • Private iterative regression: For high-dimensional regression, sparse iterates permit restricted strong convexity and restricted smoothness even when global strong convexity and smoothness fail because d > n.The estimator is constrained by an ℓ2 radius and sparsity level.
  • Private iterative regression: Under the event that truncation leaves observations unchanged, the objective gap decays exponentially in the iteration index.The proof combines this event with restricted-geometry inequalities and additional high-probability events.
  • Private iterative regression: Laplace-noise control and concentration bounds establish high-probability bounds for the accumulated perturbations used in the private iterations.One bound controls max_t W_t with probability at least 1 − c_1 exp(−c_2 log(d/(s* log n))).

APPENDIX A: PROOFS OF UPPER BOUND RESULTS

The appendix proves upper-bound ingredients for private mean estimation and regression by combining concentration inequalities, sparse-support comparisons, privacy composition, and noisy gradient-descent analysis. These arguments separately control statistical error, perturbation error, and failure probabilities.

  • Sparse mean upper bounds: The sparse mean proof decomposes estimation error into noise, overlap, and support-mismatch terms.The decomposition is then combined with bounds involving the true and estimated supports.
  • Sparse mean upper bounds: With high probability, sub-Gaussian coordinate deviations satisfy ||X − μ||_∞^2 < Cσ^2 log d/n, enabling control of the sparse estimation terms.The resulting bound scales with the sparse support size and the maximum coordinate deviation.
  • Private regression upper bounds: The private regression proofs allocate (ε/T, δ/T)-privacy to each of T iterations and invoke differential privacy composition for the full algorithm.Gradient-step sensitivity is controlled before applying the Gaussian mechanism.
  • Private regression upper bounds: On suitable concentration events, the regression objective is smooth and strongly convex over the relevant region, so gradient descent contracts toward the constrained minimizer.The step size is chosen using the smoothness parameter, and the recursion includes an additive noise term.
  • Private regression upper bounds: The noisy regression analysis bounds the perturbation contribution by a term proportional to σ^2 d^3 log(1/δ) log^3 n/(n^2 ε^2) with high probability.This bound is combined with the statistical convergence rate and model assumptions.
  • Private regression upper bounds: Failure probabilities for the concentration events are controlled exponentially in n, log n, or d, depending on the event.The proof concludes by combining these high-probability controls.

A.6. Proof of Lemma 4.4.

The proof of Lemma 4.4 analyzes private iterative hard thresholding through sparse gradient updates, noisy support selection, and restricted curvature. It chooses algorithmic parameters so contraction dominates the accumulated Laplace perturbation.

  • Privacy and update structure: Each iteration adds privacy noise to a gradient step, and composition yields overall privacy after T iterations.The proof establishes (ε/T, δ/T)-differential privacy per iteration.
  • Support selection: The peeling property compares selected coordinates with omitted coordinates, supporting bounds on support-selection error for sparse vectors.The proof applies this comparison to index sets formed from current, next, and target supports.
  • Contraction analysis: The recursion combines contraction of the objective gap with terms for selected-support noise and accumulated update noise.The resulting inequality is iterated over t to control the full trajectory.
  • Privacy and update structure: The update separates the projected sparse vector from Laplace noise added during iterative support selection.The selected support S_{t+1} is used to form the sparse noisy iterate.
  • Contraction analysis: Choosing η = 2/3 and s = 72(γ/α)^2s* makes the sparse-support terms small enough for the contraction argument.The parameter choice uses the restricted smoothness bound to select a sufficiently large constant c.
  • Contraction analysis: The proof concludes after combining the recursive bound with the objective-gap term and the auxiliary peeling lemma.This establishes the lemma’s claimed control of the private iterative update.

B.1. Proof of Lemma 2.1.

The proof controls conditional moment-generating functions using independence and sub-Gaussian bounds, then constructs a uniform prior to establish the desired probability bound.

  • Prior construction: The proof introduces the prior µ = σp, with coordinates of p sampled independently from Uniform(−1, 1).This prior is used in the second part of the argument.
  • Conclusion: The argument combines these bounds to obtain the target result under the stated sample-size range and probability condition.The proof concludes after establishing the required bound for some constant γ and δ.
  • Conditional concentration: The proof conditions on F = {X, M(X)} and uses conditional independence of p1, ..., pd.The coordinates are treated as i.i.d. given both X and F.
  • Conditional concentration: Sub-Gaussian norm bounds yield a conditional exponential-moment inequality for each Wj.The bound uses |M(X)j| ≤ σ and controls φX,j(pj) through nσ-scale deviations.
  • Conditional concentration: Multiplying the coordinatewise bounds produces the d-dimensional moment-generating-function control.The resulting inequality has the form e^(C n^2 σ^2 u^2 · d).
  • Prior construction: The marginal distribution of the transformed coordinate is shown to be uniform using a binomial representation and a beta-function identity.The proof combines the binomial law with B(k + 1, n − k + 1) = 1/(n + 1).

B.2. Proof of Lemma 3.2.

The proof establishes the sparse-mean lower bound by choosing a truncated-normal sparse prior, applying a tracing inequality, and transferring Bayes-risk bounds to maximum risk.

  • Prior construction: The prior selects the s∗ coordinates with largest absolute values from truncated-normal draws to construct a sparse mean.The resulting parameter has support size s∗ and coordinates bounded through truncation at −1 and 1.
  • Prior analysis: Stein’s Lemma is applied to analyze the prior-averaged coordinatewise behavior of the estimator.The proof sums the resulting terms after substituting the truncated-normal density.
  • Prior construction: An order-statistic calculation shows that the selected prior places nontrivial expected mass on sufficiently large coordinates.The proof derives P(Y > 1/2) > 1 − (2/e)^s∗ and concludes that c s∗ < Eπ.
  • Privacy lower bound: Lemma B.2 supplies a differential-privacy tracing inequality used to control the estimator’s deviations.The inequality is identified as previously appearing in analyses of tracing attacks.
  • Privacy lower bound: The argument uses the sparsity and coordinate-bound assumptions to control the tail probability for every µ in the parameter class.The relevant assumptions are ∥µ∥0 ≤ s∗ and ∥µ∥∞ < 1.
  • Conclusion: Under δ < n^−(1+ω), the resulting Bayes-risk lower bound is converted into a maximum-risk lower bound.The proof concludes because Bayes risk always lower bounds maximum risk.

B.4. Proof of Lemma 4.1.

The proof of the regression lower bound parallels the sparse-mean argument: it constructs a scaled truncated-normal prior, applies analogous analytic and privacy inequalities, and concludes via Bayes risk.

  • Prior construction: The prior draws truncated-normal coordinates and scales them so that the regression parameter satisfies ∥β∥2 < 1.The construction uses independent draws truncated at −1 and 1.
  • Prior analysis: The proof analyzes prior-averaged coordinate behavior by summing terms obtained from the truncated-normal density.The coordinatewise quantities are defined through Ey,X|β M(y, X)j.
  • Privacy lower bound: The regression lower-bound proof applies Lemma 4.1 together with the first part of Lemma B.2 to control estimator deviations.It then separately handles the tail-probability term before combining the bounds.
  • Conclusion: The argument assumes δ < n^−(1+ω) and concludes the lower bound for every (ε, δ)-differentially private mechanism.The same Bayes-risk-to-maximum-risk conclusion is used at the end.
  • Prior analysis: The sparse regression prior is a scaled version of the sparse-mean prior, allowing the same order-statistic calculation under the sparsity assumption.The proof explicitly invokes the sparse-mean calculation and assumes s∗ = o(d^(1−ω)).
Loading 1902.04495v5…