On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Not on the map. Why?
Abstract (arXiv)
We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under k-row-column sparsity (k-RCS) of the covariance matrix. In the non-private setting, it is known that mathsfpoly(k, log d) samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires Omega(d) samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a mathsfpoly(k, log d) sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with mathsfpoly(d) lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when k = mathsfpolylog(d). To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 25 of its 56 references that are in the map. First posted on arXiv 20 Jun 2026.
Builds on
25 of 56 references.
References · 25
- 2018Privately Learning High-Dimensional Distributionscited by 104
- 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
- 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
- 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
- 2020Differentially Private Assouad, Fano, and Le Camcited by 55
- 2019Practical Differentially Private Top-k Selection with Pay-what-you-get Compositioncited by 39
- 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
- 2017Tight Lower Bounds for Differentially Private Selectioncited by 34
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2014Statistical and computational trade-offs in estimation of sparse principal componentscited by 26
- 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
- 2013Sparse PCA via Covariance Thresholdingcited by 22
13 more
- 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
- 2021Oneshot Differentially Private Top-k Selectioncited by 16
- 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 11
- 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
- 2019Differentially Private High Dimensional Sparse Covariance Matrix Estimationcited by 7
- 2020The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimationcited by 7
- 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
- 2019Gradient-based Sparse Principal Component Analysis with Extensions to Online Learningcited by 5
- 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
- 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
- 2021The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Modelcited by 1
- 2021Existence and polynomial time construction of biregular, bipartite Ramanujan graphs of all degreescited by 1
- 2025Private Geometric Median in Nearly-Linear Timecited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.