Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA

Problem Statement
Principal Component Analysis (PCA) is a fundamental task in machine learning, typically solved using matrix-free algorithms like the Power Method, which rely on matrix-vector products. However, in many practical scenarios—such as private PCA, stochastic PCA, and decentralized PCA—exact matrix-vector products are unavailable. Instead, algorithms must operate with inexact products of the form $Ax + \xi$, where $\xi$ is a bounded perturbation. While the standard Noisy Power Method (NPM) handles these perturbations, its convergence rate is slow for ill-conditioned problems (where the gap between the $k$-th and $(k+1)$-th eigenvalues is small). Accelerated variants, such as the Accelerated Noisy Power Method (ANPM), have been proposed to improve convergence rates by incorporating momentum. However, previous theoretical analyses of ANPM (e.g., Xu, 2023) required noise magnitude bounds that were overly restrictive (scaling with high powers of the inverse eigengap), rendering them impractical for real-world applications like decentralized PCA where communication budgets limit approximation accuracy.

Methodology
The authors propose a novel analysis of the Accelerated Noisy Power Method (ANPM) that preserves the accelerated convergence rate under significantly milder noise conditions. The algorithm iteratively refines an estimate of the top-$k$ eigenspace using a momentum term $\beta$. The core of the new analysis involves studying the evolution of the matrix $H_t = (U_{-k}^\top X_t)(U_k^\top X_t)^{-1}$, where $U_k$ spans the true top-$k$ eigenspace and $U_{-k}$ spans the orthogonal complement. The spectral norm of $H_t$ corresponds to $\tan \theta_k(U_k, X_t)$, the tangent of the $k$-th principal angle between the estimate and the true subspace.

The authors derive a three-term recurrence relation for $H_t$ involving scaled Chebyshev polynomials and a sequence of matrices $\{C_t\}$ that captures the noise effects. By tightly bounding the spectral norms of these factors, they demonstrate that the error decays geometrically at a rate dependent on $\sqrt{\lambda_k / (\lambda_k - 2\sqrt{\beta})}$, provided the noise satisfies specific conditions on its components parallel ($U_k^\top \Xi_t$) and orthogonal ($U_{-k}^\top \Xi_t$) to the target subspace. Crucially, these conditions scale linearly with the eigengap, matching the requirements of the non-accelerated NPM, rather than the exponential scaling required by prior accelerated analyses.

Key Contributions

1. Improved Theoretical Guarantees: The paper establishes that ANPM converges at an accelerated rate of $\tilde{O}(\sqrt{\lambda_k / (\lambda_k - \lambda_{k+1})})$ under noise conditions identical to those of the standard NPM (Hardt & Price, 2014). This is a significant improvement over previous accelerated analyses which required noise magnitudes to be $\epsilon \mu$-small, where $\mu$ is a large power of the inverse gap.
2. Worst-Case Optimality: The authors prove that their analysis is tight up to constants. They construct specific instances showing that:
   • The convergence rate cannot be improved beyond the derived bound in the noiseless case.
   • Relaxing the derived noise conditions (specifically the constants in the bounds for $U_{-k}^\top \Xi_t$ and $U_k^\top \Xi_t$) leads to a failure to converge to the target precision.
3. Application to Decentralized PCA: The authors apply their refined analysis to design the Accelerated Decentralized Power Method (ADePM). By using their milder noise conditions, they demonstrate that ADePM achieves accelerated convergence rates while maintaining communication costs comparable to non-accelerated decentralized methods. This addresses a gap in the literature where no decentralized PCA algorithm with provably accelerated convergence existed.
4. Adaptive Tuning Heuristic: A heuristic is proposed for adaptively tuning the momentum parameter $\beta$ without requiring prior knowledge of the eigenvalues, which is shown to perform similarly to the optimal theoretical choice in practice.

Results

• Theoretical: The convergence rate of ANPM is shown to match the optimal worst-case rate achievable by Krylov subspace methods in the noiseless setting. The noise conditions derived are shown to be necessary; violating them prevents convergence.
• Experimental (Synthetic): Experiments on synthetic data confirm that ANPM with optimal or adaptive $\beta$ significantly outperforms the non-accelerated NPM in terms of convergence speed, particularly for small eigengaps, without sacrificing final accuracy. The results validate the transient geometric decay and the stationary regime determined by the noise magnitude.
• Experimental (Decentralized): Tests on real-world datasets (Fed-Heart-Disease, Digits, Ego-Facebook) show that ADePM converges faster than existing decentralized methods (DePM, DeEPCA) while achieving similar final accuracy for a fixed number of gossip rounds. The method is robust to data heterogeneity.

Significance
The paper claims that its primary significance lies in bridging the gap between theoretical acceleration and practical applicability in noisy environments. By proving that acceleration is possible under the same mild noise constraints as non-accelerated methods, the work enables the design of efficient decentralized algorithms. Specifically, it provides the first decentralized PCA algorithm with provably accelerated convergence, offering a better utility-cost trade-off for systems with strict communication, privacy, or sampling constraints. The authors emphasize that their work is primarily theoretical but is validated by experiments showing that adaptive heuristics can realize these speedups without manual parameter tuning.