{"ID":2882476,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.10879","arxiv_id":"2508.10879","title":"An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise","abstract":"Given $n$ i.i.d. random matrices $A_i \\in \\mathbb{R}^{d \\times d}$ that share a common expectation $Σ$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $Σ$, while preserving differential privacy (DP) of each individual $A_i$. Existing methods either (i) require the sample size $n$ to scale super-linearly with dimension $d$, even under Gaussian assumptions on the $A_i$, or (ii) introduce excessive noise for DP even when the intrinsic randomness within $A_i$ is small. Liu et al. (2022a) addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ($k=1$) using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top $k$ eigenvectors for arbitrary $k \\leq d$, whilst overcoming both limitations above. For $k=1$ our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when $n = \\tilde{\\!O}(d)$. We further provide a lower bound for general $k \u003e 1$, matching our upper bound up to a factor of $k$, and experimentally demonstrate the advantages of our algorithm over comparable baselines.","short_abstract":"Given $n$ i.i.d. random matrices $A_i \\in \\mathbb{R}^{d \\times d}$ that share a common expectation $Σ$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $Σ$, while preserving differential privacy (DP) of each individual $A...","url_abs":"https://arxiv.org/abs/2508.10879","url_pdf":"https://arxiv.org/pdf/2508.10879v1","authors":"[\"Johanna Düngler\",\"Amartya Sanyal\"]","published":"2025-08-14T17:48:45Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.CR\",\"cs.IT\",\"cs.LG\",\"math.ST\"]","methods":"[]","has_code":false}