Adaptive Power Iteration Method for Differentially Private PCA
This work addresses privacy-preserving PCA for data analysts, offering incremental improvements in utility for specific matrix structures.
The paper tackles the problem of computing the top singular vector under differential privacy, introducing an adaptive power iteration method that improves utility for matrices with low coherence, achieving better guarantees than worst-case approaches.
We study $(ε,δ)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a datapoint in $\mathbb{R}^{d}$. In our privacy model, neighboring inputs differ by one single row/datapoint. We study the private variant of the power iteration method, which is widely adopted in practice. Our algorithm is based on a filtering technique which adapts to the coherence parameter of the input matrix. This technique provides a utility that goes beyond the worst-case guarantees for matrices with low coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which designed a private power iteration method for the privacy model where neighboring inputs differ in one single entry by at most 1.