mlsanityData to 7 Oct 2026

DP-PCA: Statistically Optimal and Differentially Private PCA

arXiv 2205.13709 ↗First posted 27 May 2022cs.LG cs.CR cs.ITcited by 24

Not on the map. Why?

Abstract (arXiv)

We study the canonical statistical task of computing the principal component from n i.i.d.~data in d dimensions under (varepsilon,δ)-differential privacy. Although extensively studied in literature, existing solutions fall short on two key aspects: (i) even for Gaussian data, existing private algorithms require the number of samples n to scale super-linearly with d, i.e., n=Omega(d3/2), to obtain non-trivial results while non-private PCA requires only n=O(d), and (ii) existing techniques suffer from a non-vanishing error even when the randomness in each data point is arbitrarily small. We propose DP-PCA, which is a single-pass algorithm that overcomes both limitations. It is based on a private minibatch gradient ascent method that relies on em private mean estimation, which adds minimal noise required to ensure privacy by adapting to the variance of a given minibatch of gradients. For sub-Gaussian data, we provide nearly optimal statistical error rates even for n=tilde O(d). Furthermore, we provide a lower bound showing that sub-Gaussian style assumption is necessary in obtaining the optimal error rate.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 50 of its 90 references that are in the map. First posted on arXiv 27 May 2022.

Builds on

50 of 90 references.

References · 50

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2013The Composition Theorem for Differential Privacycited by 290
  3. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  4. 2019Differentially Private Learning with Adaptive Clippingcited by 218
  5. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  6. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  8. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  9. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  10. 2018Privately Learning High-Dimensional Distributionscited by 103
  11. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  12. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
38 more
  1. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  2. 2021Robust and Differentially Private Mean Estimationcited by 66
  3. 2021Differential privacy and robust statistics in high dimensionscited by 64
  4. 2015Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlocited by 61
  5. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  6. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  7. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  8. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  9. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  10. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  11. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  12. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  13. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 42
  14. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  15. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  16. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  17. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  18. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  19. 2016On the Theory and Practice of Privacy-Preserving Bayesian Data Analysiscited by 34
  20. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  21. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  22. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  23. 2017Calibrating Noise to Variance in Adaptive Data Analysiscited by 28
  24. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  25. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  26. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  27. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  28. 2013Bayesian Differential Privacy through Posterior Samplingcited by 17
  29. 2015Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionariescited by 16
  30. 2021Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacycited by 15
  31. 2022On robustness and local differential privacycited by 15
  32. 2018Locally Private Mean Estimation: Z-test and Tight Confidence Intervalscited by 14
  33. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  34. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  35. 2018Distributed Differentially-Private Algorithms for Matrix and Tensor Factorizationcited by 7
  36. 2018Locally Private Gaussian Estimationcited by 7
  37. 2021Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementationcited by 4
  38. 2021Universal Private Estimatorscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 7; 2025: 3; 2026: 8.

24 papers.

Sort:

By area:

  1. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  2. 2023Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distancecited by 14
  3. 2022DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacycited by 10
  4. 2023PILLAR: How to make semi-private learning more effectivecited by 10
  5. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  6. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  7. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  8. 2024Differentially private and decentralized randomized power methodcited by 6
  9. 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
  10. 2024Federated PCA and Estimation for Spiked Covariance Matrices: Optimal Rates and Efficient Algorithmcited by 3
  11. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  12. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
12 more
  1. 2024Provable Privacy with Non-Private Pre-Processingcited by 2
  2. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  3. 2026Adaptive Power Iteration Method for Differentially Private PCAcited by 1
  4. 2026Differentially Private Preference Data Synthesis for Large Language Model Alignmentcited by 1
  5. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
  6. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  7. 2024Near-Optimal differentially private low-rank trace regression with guaranteed private initializationcited by 0
  8. 2024Investigating Privacy Leakage in Dimensionality Reduction Methods via Reconstruction Attackcited by 0
  9. 2026Factor Augmented High-Dimensional SGDcited by 0
  10. 2026Enhancing Differentially Private Mechanisms via Empirical Bayescited by 0
  11. 2026Privacy-preserving federated tensor decomposition of single-cell immune data: recovering multicellular programs across institutionscited by 0
  12. 2026Gap-free Differentially Private PCA for Gaussian Datacited by 0