{"id":"arxiv/2606.21951","url":"https://arxiv.org/abs/2606.21951","tags":["cs.LG","cs.CR","cs.DS","math.ST"],"score":0,"title":"On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA","domain":"cs.LG","source":"arxiv","authors":["Syamantak Kumar","Shourya Pandey","Purnamrita Sarkar","Kevin Tian"],"reviews":0,"subject":"cs.LG","summary":"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 $\\mathsf{poly}(k, \\log d)$ samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires $Ω(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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-20","reactions":{}}