The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy

DOI10.1214/21-AOS2058zbMATH Open1486.62074arXiv1902.04495OpenAlexW3211357969MaRDI QIDQ2054532FDOQ2054532

Authors: Yichen Wang, Linjun Zhang, T. Tony Cai 

Publication date: 3 December 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: 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,delta)$-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.

Full work available at URL: https://arxiv.org/abs/1902.04495

Recommendations

• Privacy-preserving statistical estimation with optimal convergence rates
• Optimal Privacy-Aware Estimation
• Geometrizing rates of convergence under local differential privacy constraints
• Estimation Efficiency Under Privacy Constraints
• Differentially private distributed parameter estimation
• Comparing approximate and probabilistic differential privacy parameters
• Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy
• Efficient estimation under privacy restrictions in the disclosure problem
• Asymptotically Optimal and Private Statistical Estimation
• Concentrated differential privacy: simplifications, extensions, and lower bounds

zbMATH Keywords

high-dimensional datalinear regressionminimax optimalitydifferential privacymean estimation

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Linear regression; mixed models (62J05) Minimax procedures in statistical decision theory (62C20) Parametric inference under constraints (62F30) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• High-dimensional statistics. A non-asymptotic viewpoint
• Iterative hard thresholding for compressed sensing
• Theory of Cryptography
• Title not available (Why is that?)
• Sparse spatial autoregressions
• Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
• Statistical estimation and optimal recovery
• Title not available (Why is that?)
• What can we learn privately?
• On minimax estimation of a sparse normal mean vector
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• The algorithmic foundations of differential privacy
• Minimax Optimal Procedures for Locally Private Estimation
• A statistical framework for differential privacy
• Geometrizing rates of convergence under local differential privacy constraints
• Finite sample differentially private confidence intervals
• Fingerprinting codes and the price of approximate differential privacy
• Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
• Privacy-preserving statistical estimation with optimal convergence rates

Cited In (29)

• Private Sampling: A Noiseless Approach for Generating Differentially Private Synthetic Data
• On robustness and local differential privacy
• Optimal Privacy-Aware Estimation
• Constrained forms of statistical minimax: computation, communication, and privacy
• Gaussian differentially private robust mean estimation and inference
• Distributed optimal subsampling for quantile regression with massive data
• Privacy-preserving statistical estimation with optimal convergence rates
• General inferential limits under differential and pufferfish privacy
• Privacy-preserving parameter estimation in distributed cases
• A Survey of Differentially Private Regression for Clinical and Epidemiological Research
• Majority vote for distributed differentially private sign selection
• Econometrics with privacy preservation
• Differentially private high dimensional sparse covariance matrix estimation
• Differentially private precision matrix estimation
• Local differential privacy: elbow effect in optimal density estimation and adaptation over Besov ellipsoids
• Geometrizing rates of convergence under local differential privacy constraints
• Comment
• Finite sample differentially private confidence intervals
• Privacy-preserving parametric inference: a case for robust statistics
• Differentially private SGD with non-smooth losses
• Efficiency in local differential privacy
• A novel adaptive differential privacy algorithm for empirical risk minimization
• Differentially private distributed parameter estimation
• Interactive versus noninteractive locally differentially private estimation: two elbows for the quadratic functional
• Differentially private inference via noisy optimization
• Differentially private confidence intervals for proportions under stratified random sampling
• Edge differentially private estimation in the \(\beta\)-model via jittering and method of moments
• Estimation and Inference for High-Dimensional Generalized Linear Models with Knowledge Transfer
• Privacy aware learning

Uses Software

• RAPPOR

This page was built for publication: The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054532)