Source-linked AI summary
Near-Optimal Algorithms for Differentially-Private Principal Components
Kamalika Chaudhuri, Anand D. Sarwate, Kaushik Sinha
TL;DR
The paper asks how to approximate PCA privately while preserving utility on sensitive data. It proposes PPCA, an exponential-mechanism method that favors subspaces close to PCA, and compares it with existing procedures theoretically and empirically. PPCA scales as O(d), matching the Ω(d) lower bound, while the existing method scales as Ω(d3/2√log d), with experiments showing a marked performance gap.
Problem
Differentially private PCA must approximate useful principal subspaces while protecting sensitive individual data, but existing procedures can have unfavorable dimension-dependent utility.
Method
PPCA uses the exponential mechanism with an approximation-quality utility function and is implemented with an MCMC sampler.
Results
PPCA has sample complexity O(d) versus Ω(d3/2√log d) for SULQ, while any differentially private approximation requires Ω(d) samples.
Takeaways & Limitations
PPCA is nearly optimal in sample complexity, and experiments show a marked utility gap between PPCA and MOD-SULQ on real data.
Takeaways & Limitations
The sample-complexity analysis applies only to k = 1, and the implementation’s MCMC convergence remains an open question.
Abstract
from arXiv · showhide
Principal components analysis (PCA) is a standard tool for identifying good low-dimensional approximations to data in high dimension. Many data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We show that the sample complexity of the proposed method differs from the existing procedure in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling. We furthermore illustrate our results, showing that on real data there is a large performance gap between the existing method and our method.
1 Introduction
The paper studies differentially private PCA for sensitive, high-dimensional data and proposes PPCA, which directly optimizes approximation quality. Its analysis shows PPCA has near-optimal dimension dependence and experiments find a substantial gap over SULQ.
- Motivation: Differentially private PCA addresses the need to learn structural relationships from sensitive, high-dimensional individual data.The paper frames differential privacy as a privacy guarantee for algorithms operating on personal information.
- Problem and approach: PPCA outputs a k-dimensional subspace biased toward subspaces close to standard PCA, unlike SULQ’s utility treatment.PPCA is implemented with MCMC sampling from a matrix Bingham distribution and is differentially private when the procedure converges.
- Results: SULQ has sample complexity Ω(d3/2√log d), whereas PPCA has sample complexity O(d).These bounds are given for k = 1 and explain the observed performance gap between the methods.
- Results: Any differentially private PCA algorithm requires Ω(d) samples, making PPCA nearly optimal in its dependence on data dimension.The lower bound applies absent additional limitations on the data set.
- Open questions: The paper leaves computational and theoretical questions involving finite precision, MCMC sampling, general k, and private selection of k.Its sample-complexity analysis applies only to k = 1, although PPCA’s privacy guarantees hold for all k.
2 Preliminaries
The preliminaries represent data through a positive semidefinite second-moment matrix and define PCA subspaces, approximation quality, and differential privacy. They measure private PCA utility by how closely an output subspace matches the leading eigenspace.
- Data and PCA: The data consist of bounded private vectors x_i ∈ R^d, whose second-moment matrix A is positive semidefinite with Frobenius norm at most 1.The paper seeks a low-rank approximation to A using its leading principal components.
- PCA representation: The top-k PCA subspace is formed by the eigenvectors associated with the k largest eigenvalues of A.The k-th eigengap is Δ_k = λ_k − λ_k+1.
- PCA representation: A rank-k approximation A^(k) reconstructs A from its top-k eigenvectors and eigenvalues; for k = 1 it is λ_1(A)v_1v_1^T.The top eigenvector v_1 corresponds to the largest eigenvalue.
- Utility: The quality function q(Ŵ) is maximized when Ŵ contains the top-k eigenvectors of A.For the theoretical analysis, the paper focuses on the inner product between the output vector and the true top eigenvector.
- Differential privacy: Differential privacy compares output distributions on data sets differing in one entry, with ε_p and δ controlling the privacy guarantee.Lower ε_p and δ provide stronger privacy, while δ bounds the probability of failure in the weaker guarantee.
3 Algorithms and results
The paper compares MOD-SULQ, which perturbs the empirical second-moment matrix, with PPCA, which samples subspaces using a utility-biased exponential mechanism. PPCA is differentially private and nearly optimal in sample-complexity scaling, while the theory is primarily for k = 1.
- Input perturbation: MOD-SULQ perturbs each entry of the empirical second-moment matrix with Gaussian noise before releasing its top-k eigenvectors.The modified procedure uses a symmetric noise matrix so the resulting eigenvectors are real.
- Exponential mechanism: PPCA samples a k-dimensional subspace from a privacy-preserving distribution biased toward subspaces close to PCA's output.This distribution is the matrix Bingham distribution, and PPCA is implemented with a Gibbs sampler.
- Privacy guarantees: PPCA is ϵp-differentially private, whereas MOD-SULQ provides (ϵp, δ)-differential privacy.These guarantees apply to their respective private PCA approximations.
- Sample-complexity results: PPCA's sample complexity grows linearly with d and is nearly optimal because every ϵp-differentially private algorithm requires Ω(d) samples.For k = 1, the PPCA upper and general lower bounds match in scaling with d, ϵp, and the eigengap Δ.
- Sample-complexity results: MOD-SULQ requires d^3/2 dependence on sample complexity, compared with d for PPCA, despite its slightly weaker privacy guarantee.The paper proves this comparison for k = 1 and leaves the scaling behavior with k as an open problem.
4 Analysis of PPCA
PPCA is analyzed through exponential-mechanism guarantees, yielding eigengap-dependent utility and sample-complexity bounds. Its O(d) dimension scaling is nearly optimal because every differentially private PCA algorithm requires Ω(d) samples.
- Exponential-mechanism analysis: PPCA applies the exponential mechanism to a score function measuring subspace quality relative to PCA.The analysis uses the resulting Bingham distribution to derive guarantees for k = 1.
- Utility and sample complexity: For k = 1, PPCA’s sample complexity depends on the eigengap λ1 − λ2 between the two largest eigenvalues.The proof bounds the exponential-mechanism output relative to the optimal top-eigenvector score.
- General lower bound: Every ϵp-differentially private PCA algorithm requires Ω(d) samples for the constructed lower-bound instances.The lower-bound argument uses multiple nearby databases whose top eigenvectors are separated and limits average utility across them.
5 Analysis of MOD-SULQ
MOD-SULQ is analyzed as a differentially private input-perturbation method whose utility deteriorates with dimension and limited sample size. Theorem 11 converts this behavior into a lower bound on expected correlation and sample complexity.
- Proof strategy: The MOD-SULQ analysis constructs packed unit-vector inputs and applies Fano’s inequality to lower-bound estimation error.The resulting distributions correspond to noisy second-moment matrices under different input directions.
- Utility bound: Theorem 11 bounds MOD-SULQ’s expected correlation with the empirical top eigenvector for some data set.The guarantee assumes MOD-SULQ is (ϵp, δ)-differentially private on data in R^d with n elements.
- Numerical illustration: Figure 1 plots the lower bound on E[|⟨v̂1, v1⟩|] against log10(n) for d from 50 to 1000 and multiple ϵp values.All plotted experiments use δ = 0.01.
- Numerical illustration: In high dimension with few data points, the lower bound indicates poor expected MOD-SULQ performance.The paper notes that performance may be more favorable in lower-dimensional, data-rich regimes.
- Scope of the limitation: The resulting limitation is especially acute when intrinsically low-dimensional data are represented in a very high-dimensional space.The paper states that input perturbation is not a good approach in such sparse settings.
6 Experiments
The experiments implement PPCA with Gibbs sampling, assess convergence and burn-in, and compare its utility and classification performance with alternative methods on real datasets. PPCA substantially outperforms MOD-SULQ in utility and approaches non-private PCA in classification accuracy.
- Implementation of Gibbs sampling: PPCA was implemented with a Gibbs sampler, requiring empirical selection of a finite burn-in time because convergence-time guarantees were unavailable.The experiments examined multiple traces and initial states to assess convergence behavior.
- Datasets and preprocessing: The experiments used four real datasets spanning network, demographic, medical-sensor, and insurance domains, with preprocessing that produced dimensions 116, 513, 44, and 150.Categorical features were one-hot encoded, and rows and columns were normalized before PCA evaluation.
- Implementation of Gibbs sampling: For data with a few hundred dimensions and k between 5 and 10, simulations found convergence to F_k(t) < 0.01 at t = 20,000.Convergence was faster when the best rank-k approximation was close to the data matrix and slower for larger sample sizes.
- Utility comparison: As sample size increased at fixed privacy, PPCA utility improved, while MOD-SULQ was generally no better than a randomly chosen subspace.The localization dataset was an exception, where its lower dimension and larger sample size yielded reasonable MOD-SULQ utility.
- Classification performance: PPCA classification performed almost as well as non-private PCA, while MOD-SULQ and random projections were somewhat worse and more variable.The higher variance of the latter methods was attributed to projections farther from the top-k PCA subspace.
7 Conclusion
The conclusion finds a marked empirical gap between MOD-SULQ and PPCA, explained by their different dimension-dependent sample-complexity scaling. It also identifies theoretical and practical directions for extending and validating the results.
- MOD-SULQ and PPCA differ markedly in how well they approximate the data’s top-k subspace.The paper attributes this empirical gap to their different sample-complexity scaling with data dimension.
- PPCA uses qF(·) in the exponential mechanism, while MOD-SULQ often performs comparably to random projections on real data.The comparison suggests that the real datasets contained too few points for MOD-SULQ to be effective.
- PPCA is nearly optimal because every differentially private approximation to PCA requires Ω(d) samples.
- Practical limitations: Practical deployment requires accounting for finite precision, pseudorandomness, approximate optimization, and empirically unresolved MCMC convergence.The paper notes that analytical convergence-rate bounds for the Gibbs sampler are not yet available.
- Future theoretical work: Theoretical sample-complexity results should be extended from k = 1 to general k > 1 using suitable approximation metrics and manifold packings.
A A packing lemma
The packing lemma constructs many unit vectors on the sphere with pairwise inner products bounded below a chosen threshold. Its probabilistic proof samples random vectors, controls collisions through conditional expectations, and extracts a suitable subset.
- The lemma seeks a large set of unit vectors on S^(d−1) whose pairwise inner products are smaller than φ.Such a set provides separated points on the sphere for the later packing argument.
- Randomly sampled unit vectors are screened by indicators that flag a vector having large inner product with an earlier sample.The indicator fi equals 1 when Zi has inner product exceeding φ with some preceding Zj.
- A union bound and the spherical inner-product inequality upper-bound each collision indicator’s conditional expectation.The bound is 2(i − 1)(1 − φ^2)^((d−1)/2).
- A conditional-expectation bound implies that a subset of the sampled vectors avoids all forbidden large inner products with finite probability.The resulting subset has size K = ⌊(1 − t)N⌋ under the lemma’s parameter conditions.
- The construction is probabilistic and its bounds can be tightened for smaller dimensions, while the maximum possible spherical-code size remains open.The stated construction captures the relevant scaling with d rather than necessarily the largest packing.