An Iterative Algorithm for Differentially Private k k -PCA with Adaptive Noise
Johanna Düngler, Amartya Sanyal · 2025
Read An Iterative Algorithm for Differentially Private k k -PCA with Adaptive Noise by Johanna Düngler, Amartya Sanyal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10879.txt.
Introduction
Johanna Düngler and Amartya Sanyal work on a privacy-preserving form of principal component analysis, a standard tool for finding the main patterns in data. Their 2025 paper asks how to find not just the top pattern, but the top several, from random matrices, without leaking facts about any single person's data.
Older methods needed huge sample sizes or added so much noise that results suffered. Their repeating algorithm adjusts its noise as it goes and handles any number of top patterns. They prove error bounds that match a lower limit they also derive, up to a small factor. Tests back the theory against rival methods.
Catalog record
| CREATOR | Johanna Düngler, Amartya Sanyal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 133 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-10879
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Iterative Algorithm for Differentially Private k k -PCA with Adaptive Noise Johanna Düngler, Amartya Sanyal Abstract Given n n i.i.d. random matrices A i ∈ ℝ d × d A_{i}\in\mathbb{R}^{d\times d} that share a common expectation Σ \Sigma , the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension k k that captures the largest variance directions of Σ \Sigma , while preserving differential privacy (DP) of each individual A i A_{i} . Existing methods either (i) require the sample size n n to scale super-linearly with dimension d d , even under Gaussian assumptions on the A i A_{i} , or (ii) introduce excessive noise for DP even when the intrinsic randomness within A i A_{i} is small. Liu et al. 2022a addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ( k = 1 k=1 ) using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top k k eigenvectors for arbitrary k ≤ d k\leq d , whilst overcoming both limitations above. For k = 1 k=1 , our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when n = O ~ ( d ) n=\tilde{O}(d) . We further provide a lower bound for general k > 1 k>1 , matching our upper bound up to a factor of k k , and experimentally demonstrate the advantages of our algorithm over comparable baselines. 1 Introduction Principal Component Analysis (PCA) is a foundational statistical method widely utilized for dimensionality reduction, data visualisation, and noise filtering. Given n data points \left\{{x_{i}}\right\}_{i=1}^{n} , classical PCA computes the top eigenvectors of the empirical covariance matrix X:=\sum_{i=1}^{n}x_{i}x_{i}^{\top}\in\mathbb{R}^{d\times d} . This problem of extracting the top k eigenvectors is commonly known as k -PCA. In this work, we consider the problem of Stochastic k -PCA, which differs from the standard setting as follows: instead of inputting a single matrix, we input a stream of matrices A_{1},\ldots,~A_{n} , that are sampled independently from distributions that share the same expectation \Sigma . Given this input, the goal of a Stochastic k -PCA algorithm is to approximate the dominant k eigenvectors of \Sigma . Differential privacy (DP) ( Dwork et al. 2006 ) provides rigorous, quantifiable guarantees of individual data privacy and has been widely adopted in sensitive data contexts, such as census reporting ( Abowd et al. 2020 ) and large-scale commercial analytics ( Apple 2017 ) . Despite extensive study of differentially private PCA ( Blum et al. 2005 ; Chaudhuri et al. 2013 ; Hardt and Roth 2013 ; Dwork et al. 2014b ) , existing methods in the stochastic setting suffer from sample complexity super - linear in d or inject noise at a scale that ignores the underlying stochasticity in the data. When applied to the stochastic setting, these works generally yield suboptimal error rates of O(\sqrt{dk/n}+d^{3/2}k/(\varepsilon n)) where \varepsilon is the DP parameter. Example 1 (Spiked Covariance) . In the spiked covariance model, we observe i.i.d. matrices A_{i}\in\mathbb{R}^{d\times d} that contain both a deterministic (low-rank) signal and random noise, causing the A_{i} to be full-rank. As a concrete illustration, consider data points x_{i}=s_{i}+n_{i} , composed of a signal s_{i}\sim\text{Unif}\left(\{v,-v\}\right) with v a unit vector and n_{i}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}) . Therefore A_{i}:=x_{i}x_{i}^{\top} consists of a deterministic part vv^{\top} and noise terms that scale with \sigma^{2} . One would hope that the privacy noise that is needed, shrinks as the noise variance \sigma^{2} decreases. Instead, most differentially private PCA methods employ non-adaptive clipping thresholds, so their added privacy noise scales only with that threshold, resulting in unnecessarily large privacy noise for many distributions. Recent advances by Liu et al. 2022a address these limitations for sub-Gaussian distributions, but only for the top eigenvector case ( k=1 ). Cai et al. 2024 achieve optimal performance specifically for the k -dimensional spiked covariance model, yet their privacy guarantees only apply under distributional assumptions on the data. Our Contributions. In this work, we propose k - DP - PCA , the first DP algorithm for stochastic PCA that simultaneously (1) achieves sample complexity n=\tilde{O}(d) under similar assumptions as Liu et al. 2021 , (2) adapts its privacy noise to the data’s inherent randomness, (3) generalizes seamlessly to any target dimension k\leq d , and (4) is simple to implement . For k=1 , k - DP - PCA matches the risk of Liu et al. 2022a under sub - Gaussian assumptions. For general k , we prove a nearly matching lower bound up to a linear factor in k , precisely characterising the cost of privacy in this general setting. Technically, we employ the deflation framework: iteratively estimate the top eigenvector, project it out, and repeat. We extend the recent deflation analysis of Jambulapati et al. 2024 to the stochastic setting via a novel stochastic e-PCA oracle ( Definition 3 ), which may be of independent interest. We then adapt DP subroutines from Liu et al. 2022a based on Oja’s algorithm and finally, through a novel utility analysis of non-private Oja’s algorithm, demonstrate that the adapted subroutines satisfy the oracle’s requirements, yielding a simple to implement, memory - efficient method. The remainder of this paper is structured as follows. We formally define our setting in Section 2 , state main results in Section 3 , present technical analyses in Section 4 and empirical evaluations demonstrating the effectiveness of our approach in Section 5 . Finally, we end with a discussion and open questions in Section 6 and conclusion in Section 7 . 2 Problem formulation Let A_{1},\dots,A_{n}\in\mathbb{\mathbb{R}}^{d\times d} be independent random matrices with common expectation \Sigma=\mathbb{{\mathbb{E}}}\left[{A_{i}}\right] . We assume \Sigma is symmetric positive semi-definite (PSD) with eigenvalues \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{d}\geq 0 . For a given k<d , we assume the eigengap \Delta_{k}=\lambda_{k}-\lambda_{k+1}>0 . The goal of Stochastic PCA is to produce a U\in\mathbb{R}^{d\times k} whose orthonormal columns approximate the top- k eigenspace of \Sigma . We measure the utility of U by comparing it to V_{k} , the matrix containing the true top k eigenvectors of \Sigma as columns. Throughout, \left\lVert\cdot\right\rVert_{2} denotes the operator norm, \left\langle{\cdot},{\cdot}\right\rangle the Frobenius inner product: \left\langle{A},{B}\right\rangle=\mathrm{Tr}\left({A^{\top}B}\right) , and \gtrsim and \tilde{O}(\cdot) hide polylogarithmic factors. Definition 1 ( \zeta -approximate Utility) . We say U\in\mathbb{R}^{d\times k} is \zeta -approximate if U has orthonormal columns and \displaystyle\langle UU^{\top},\Sigma\rangle\geq(1-\zeta^{2})\langle V_{k}V_{k}^{\top},\Sigma\rangle. Although several utility measures exist for PCA, our choice is motivated by the error measure used in Jambulapati et al. 2024 . This is a natural measure of usefulness, as \langle UU^{\top},\Sigma\rangle quantifies how much of the original “energy” of \Sigma is retained when projecting onto the lower-dimensional subspace spanned by U , and by the Eckart-Young Theorem we know V_{k} is the optimal rank- k approximation of \Sigma . Further, we use the add/remove model of differential privacy, namely Definition 2 (Differential Privacy ( ( Dwork et al. 2006 ) )) . Given two multi-sets S and S^{\prime} , we say the pair (S,S^{\prime}) is neighboring if |S\setminus S^{\prime}|+|S^{\prime}\setminus S|\leq 1. We say a stochastic query q over a dataset S satisfies (\varepsilon,\delta) -differential privacy for some \varepsilon>0 and \delta\in(0,1) if P(q(S)\in A)\leq e^{\varepsilon}P(q(S^{\prime})\in A)+\delta for all neighboring (S,S^{\prime}) and all subsets A of the range of q . Before