Research map / Federated learning and privacy / Differential privacy
An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes k-DP-PCA, a deflation-based differentially private stochastic k-PCA algorithm built on an adaptive-noise 1-PCA oracle (ModifiedDP-PCA) and a DP Oja variant (k-DP-Ojas), with utility linear in d and adaptive to data randomness.
Problem
Differentially private stochastic k-PCA: estimate the top-k eigenspace of the expectation of i.i.d. random matrices while preserving DP of each sample, with sample complexity near-linear in d and noise adapting to data variability.
Approach
Extends deflation to the stochastic setting via a stochastic ePCA oracle, and uses an adaptive two-stage private Oja update (PrivRange then PrivMean) so that privacy noise scales with the data's intrinsic spread rather than a fixed clipping threshold.
Key results
- k-DP-PCA's utility guarantee is zeta = O~(kappa'(sqrt(Vk/n) + gamma d k sqrt(log(1/delta))/(eps n))), linear in d, versus O(d^{3/2}k/(eps n)) for prior private methods.
- Lower bound for spiked covariance matches the upper bound in sigma, d, n, eps up to factors of k, sqrt(lambda_1+sigma^2) and sqrt(log(1/delta)).
- Experiments on spiked covariance (d=200, k=2, eps=1, delta=0.01) show k-DP-PCA outperforming DP-Gauss-1, DP-Gauss-2 and DP-Power-Method, especially when sigma is much smaller than lambda_1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use k-DP-PCA instead of DP-Gauss-1, DP-Gauss-2, or DP-Power-Method | Spiked covariance · Spiked covariance; varying sample size and noise level | utility | Helped |
| Use k-DP-PCA instead of k-DP-Ojas | Spiked covariance · Low-noise regime (σ ≪ λ₁) | utility | Helped |
| Use k-DP-Ojas instead of k-DP-PCA | Spiked covariance · Higher-noise regime | utility | Mixed |
| Increase the ambient dimension | DP-Gauss-1, DP-Gauss-2, and DP-Power-Method relative to k-DP-PCA · Spiked covariance; fixed sample size | utility | Hurt |
| Increase the eigengap | DP-Gauss-2 · Spiked covariance; varying eigengap | utility | Helped |
| Increase the eigengap | DP-Gauss-1 · Spiked covariance; varying eigengap | utility | No clear effect |
Surprising findings
- The simpler k-DP-Ojas often matches or exceeds k-DP-PCA at larger noise levels, owing to fewer hyperparameters and more robustness to learning rates.
- Existing DP-PCA guarantees (relative error on E[P] Sigma E[P]) cannot be plugged directly into the deflation framework, since E[P] is not a projection.
Limitations
- Sample splitting across k deflation rounds incurs an extra factor of k in the upper bound, not matched by the lower bound.
- Assumption 4 (bounded bilinear-form tail) excludes heavy-tailed outer products; relaxing it worsens the privacy term.
- Sample complexity has an exponential dependence on the spectral gap kappa' in the stated condition; subroutines are not streaming-compatible.
Experimental setup
Datasets: synthetic spiked covariance data
Benchmarks: spiked covariance synthetic data
Metrics: zeta approximation error (relative captured variance) utility vs sample size utility vs dimension utility vs eigengap
Baselines: DP-Gauss-1 DP-Gauss-2 DP-Power-Method k-DP-Ojas
Builds on: DP-PCA (Dwork et al. 2014 style private PCA with PrivRange/PrivMean) Oja's algorithm deflation for k-PCA (black-box reduction) noisy power method
Closest papers by meaning
- Optimal Rates for Adaptive Private $k$-PCA (NeurIPS 2026 · similarity 0.97)
- Dimension-free Private Mean Estimation for Anisotropic Distributions (NeurIPS 2024 · similarity 0.87)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.86)
- Correlated Noise Provably Beats Independent Noise for Differentially Private Learning (ICLR 2024 · similarity 0.86)
- On the Computational Complexity of Private High-dimensional Model Selection (NeurIPS 2024 · similarity 0.86)
- Private Adaptive Covariance Estimation via Gaussian Graphical Models (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.