Technical Summary: Adaptive Power Iteration Method for Differentially Private PCA

Problem Statement

This paper addresses the problem of approximately computing the top singular vector of a matrix $A \in \mathbb{R}^{n \times d}$, where each row represents a private data point of an individual. The goal is to design algorithms that satisfy $(\epsilon, \delta)$-differential privacy (DP) under the standard model where neighboring inputs differ by exactly one row (with bounded $\ell_2$ norm).

While the worst-case additive approximation guarantees for this problem are well-understood (specifically the $e\tilde{O}(\sqrt{d})$ bound by Dwork et al. [DTTZ14]), these bounds are often too loose for practical, high-dimensional applications. The paper seeks to achieve beyond-worst-case guarantees by leveraging structural properties of the input matrix, specifically low coherence, without requiring prior knowledge of this parameter.

Methodology

The authors propose a novel Adaptive Power Iteration Method (Algorithm 1). The algorithm follows the classical power iteration template but introduces two critical innovations to handle the specific privacy constraints of row-level changes:

1. Adaptive Filtering:
   In standard power iteration, the update step is $x^{(t+1)} = A^\top A x^{(t)}$. In the private setting, adding noise proportional to the sensitivity is required. For row-level privacy, the sensitivity of the update depends on $\max_a \|a\|_2 |\langle a, x^{(t)} \rangle|$. Simply thresholding the iterate $x^{(t)}$ is insufficient because the sensitivity can still grow with the magnitude of the data rows.
   Instead, the proposed algorithm filters out rows $a$ where the quantity $\|a\|_2 |\langle a, x^{(t)} \rangle|$ exceeds a dynamic threshold $\theta^{(t)}$. This threshold is determined adaptively in each iteration using the Sparse Vector Technique (specifically the AboveThreshold algorithm). By filtering rows with large contributions, the algorithm ensures the sensitivity of the subsequent update is bounded by the threshold $\theta^{(t)}$ itself.

2. Noise Injection:
   After filtering, the algorithm performs the power update on the filtered matrix $A^{(t)}$ and adds Gaussian noise scaled to the threshold $\theta^{(t)}$:
   $$x^{(t+1)} = (A^{(t)})^\top A^{(t)} x^{(t)} + \frac{\theta^{(t)}\sqrt{2\log(2/\delta)}}{\epsilon} g^{(t)}$$
   where $g^{(t)} \sim \mathcal{N}(0, I)$.

3. New Analytical Framework:
   The paper departs from the analysis techniques used in prior work (e.g., Hardt and Roth [HR13]), which relied on sign symmetry of the iterates in the eigenbasis. The authors note that the filtering step breaks this symmetry. Consequently, they develop a new analysis tracking two sequences:

   • $m^{(t)}$: The component of the iterate along the top eigenvector.
   • $M^{(t)}$: The maximum dot product between the iterate and the rows of the matrix in the remaining coordinates.
     They establish recurrence relations showing that $m^{(t)}$ grows exponentially with the top eigenvalue $\sigma_1^2$, while $M^{(t)}$ grows significantly slower, provided the eigengap $\kappa = (\sigma_1^2 - \sigma_2^2)/\sigma_1^2$ is sufficiently large relative to the noise and coherence parameters.

Key Contributions

• Novel Algorithm: A private power iteration algorithm that automatically adapts to the coherence of the input matrix without requiring it as an input parameter.
• Beyond-Worst-Case Guarantees: The algorithm provides error bounds that scale with the coherence parameter $\Upsilon$ (related to the maximum entry of the singular vectors) rather than just the ambient dimension $d$. This yields significantly tighter bounds for matrices with low coherence (e.g., random Gaussian data or structured non-random data).
• Privacy Model: The work operates in the more natural and less restrictive privacy model where neighboring inputs differ by one row (bounded $\ell_2$ norm), contrasting with prior beyond-worst-case works like [HR13] that required a stricter entry-wise privacy model.
• Stochastic Analysis: The authors extend their results to the case where data is sampled i.i.d. from a Gaussian distribution, providing error guarantees relative to the population covariance matrix.

Results

The paper presents two main theorems:

1. Deterministic Case (Theorem 1.1 & Corollary 1.1):
   For an input matrix with low coherence $\Upsilon$ and eigengap $\kappa$, the algorithm outputs a vector $x$ such that the squared sine of the angle to the true top singular vector is bounded by:
   $$\sin^2(v_1, x) = \tilde{O}\left( \frac{\min\{4n/\sigma_1^2, d\}\Upsilon^2 + \sigma_1^2\Upsilon^2/\kappa + d\sigma_1^2\Upsilon^2\kappa}{\epsilon^2(\sigma_1^2 - \sigma_2^2)^2} \right)$$
   This bound improves upon the state-of-the-art worst-case bounds of [DTTZ14] and [dN26] in regimes where $\Upsilon$ is small (e.g., $\Upsilon \approx 1/\sqrt{n}$) and $\kappa$ is not too small. Specifically, for Gaussian-like data where $\Upsilon \approx 1/\sqrt{n}$, the error scales favorably compared to previous methods.

2. Gaussian i.i.d. Case (Theorem 1.2):
   When rows are i.i.d. samples from $\mathcal{N}(0, \Sigma^2)$, the algorithm achieves an error of:
   $$\sin^2(v_1, x) = \tilde{O}\left( \frac{d}{\epsilon^2 n^2 \sigma_1^2 \kappa^2} + \frac{1}{\epsilon^2 n^2 \sigma_1^2 \kappa^3} + \frac{1}{n \sigma_1^2 \kappa^2} + \frac{1}{n^2 \sigma_1^4 \kappa^2} \right)$$
   This result holds for any constant $\epsilon$ and requires a sample complexity of $n \geq \tilde{\Omega}(d + \frac{1}{\epsilon \sigma_1^2 \kappa})$. This improves upon the sample complexity requirements of prior work [LKJO22], which either required $\epsilon = O(1/\sqrt{n})$ or prohibitive sample sizes for small eigengaps.

Significance and Claims

The authors claim that their work provides an affirmative answer to the question of whether it is possible to design a differentially private algorithm that is private on all input matrices (under row-level changes) while achieving beyond-worst-case guarantees for low-coherence matrices.

The significance of the work lies in:

• Bridging the Gap: It successfully extends beyond-worst-case analysis to the standard row-level privacy model, a setting where previous attempts (like [HR13]) failed to provide guarantees without restrictive assumptions on the change magnitude (e.g., $\ell_1$ bounds).
• Practical Utility: By adapting to coherence, the algorithm offers a practical solution for high-dimensional data analysis where worst-case bounds render algorithms unusable.
• Technical Innovation: The introduction of adaptive filtering combined with a new analytical technique to handle the loss of sign symmetry represents a significant methodological advance in the literature on private power iteration methods.

The paper concludes that while the focus is on deterministic data, the algorithm's performance on random data (specifically Gaussian) compares favorably with state-of-the-art results, offering better sample complexity and flexibility regarding the privacy parameter $\epsilon$.