PaperlayerView exact revision on arXiv

Source-linked AI summary

The Noisy Power Method: A Meta Algorithm with Applications

Moritz Hardt, Eric Price

arXiv:1311.2495v4cs.DScs.LG

TL;DR

The paper addresses how to compute dominant singular vectors when matrix-vector products are noisy, a setting spanning several machine-learning applications. It analyzes a noisy power method globally in terms of its perturbations and initialization, showing convergence to leading singular vectors and enabling improved application-specific guarantees.

  • Problem

    Existing noisy power-method applications had ad-hoc analyses limited to local initialization, spiked covariance distributions, or p = 1 privacy settings.

  • Method

    The paper gives a general convergence analysis for iterates X_ℓ under noisy updates AX_ℓ + G_ℓ, including randomly initialized orthonormal subspaces.

  • Results

    X_ℓ converges toward the first k singular vectors, with the convergence bound becoming quantitatively stronger when the working dimension p exceeds k.

  • Takeaways & Limitations

    The unified analysis supports novel results for streaming PCA and privacy-preserving spectral analysis, including broader distributional scope and nearly optimal private singular-vector bounds.

  • Takeaways & Limitations

    The convergence corollary assumes a random p-dimensional initialization and imposes two magnitude conditions on the noise, including dependence on the singular-value separation.

Abstract

from arXiv · show

We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result characterizes the convergence behavior of the algorithm when a significant amount noise is introduced after each matrix-vector multiplication. The noisy power method can be seen as a meta-algorithm that has recently found a number of important applications in a broad range of machine learning problems including alternating minimization for matrix completion, streaming principal component analysis (PCA), and privacy-preserving spectral analysis. Our general analysis subsumes several existing ad-hoc convergence bounds and resolves a number of open problems in multiple applications including streaming PCA and privacy-preserving singular vector computation.

1 Introduction

The paper develops the Noisy Power Method, a general framework for computing dominant singular vectors despite adversarial or application-specific noise, and analyzes its global convergence. This analysis supports improved results for streaming PCA and privacy-preserving spectral analysis.

  • General method: The Noisy Power Method replaces each update AX_ℓ with AX_ℓ + G_ℓ, allowing possibly adversarial and adaptive perturbations while optionally maintaining orthonormal columns.QR factorization after each update can maintain orthonormal columns.
  • Applications: The meta-algorithm instantiates different noise terms G_ℓ and initial matrices X_0 to handle matrix completion, streaming PCA, and privacy-preserving spectral analysis.Earlier applications used separate, ad-hoc analyses with narrower assumptions.
  • Convergence analysis: The general analysis characterizes global convergence in terms of the noise G_ℓ and initial subspace X_0, including randomly chosen orthonormal bases.Random initialization is delicate because its initial correlation with the target subspace can vanish with dimension.
  • Convergence analysis: X_ℓ converges toward the first k singular vectors, with a stronger quantitative result when the working dimension p exceeds the target dimension.Theorem 2.4 provides the formal convergence bound.
  • Convergence analysis: Under the stated assumptions, after L = O((σ_k/(σ_k−σ_{k+1})) log(dτ/ε)) steps, the method achieves the corollary’s high-probability convergence guarantee.The guarantee holds with all but τ^−Ω(p+1−k) + e^−Ω(d) probability, for ε < 1/2.
  • Applications: The streaming result strengthens a previously quadratic dependence on k when p = k by increasing p slightly, while the privacy result gives nearly optimal bounds and coherence-based dimension dependence.The privacy analysis also provides a nearly-linear-time algorithm and resolves the main problem left open by Hardt and Roth.
  • Streaming PCA: For streaming PCA, the analysis applies beyond the spiked covariance model and can yield near-linear sample complexity for round distributions or rapidly decaying spectra.With σ_j ≈ j^−c for c > 1/2, the stated bound is n = ˜O(k^(2c+2)d/ε^2).

2 Convergence of the noisy power method

The noisy power method tracks convergence through principal angles between an iterate and the top-k eigenspace, showing geometric contraction under controlled noise and suitable initialization. A random orthonormal start supplies the required initial correlation with high probability.

  • The tangent of the kth principal angle contracts by the singular-value ratio σk+1/σk in each noisy power iteration.
  • Theorem 2.4 gives global convergence when the initial subspace and every noise matrix satisfy its stated conditions.The method reaches an ε-error after a number of iterations governed by the spectral gap and target accuracy.
  • The convergence proof repeatedly applies the one-step principal-angle lemma until the tangent reaches ε and remains there.
  • A randomly chosen orthonormal start has vanishing initial correlation in dimension d when p is small, so its alignment must be controlled probabilistically.The analysis uses Gaussian random-matrix bounds on the smallest singular value to establish a usable initial angle.

3 Memory efficient streaming PCA

The streaming power method computes dominant covariance eigenvectors using O(dk) space, without storing the d^2-entry sample covariance matrix. A general noisy-power analysis yields sample guarantees for broad distributions and improves prior streaming PCA results.

  • 3 Memory efficient streaming PCA: O(dk) space lets streaming PCA retain only the necessary output-sized state instead of the full d^2-entry sample covariance matrix.
  • 3 Memory efficient streaming PCA: The analysis applies in principle to any distribution satisfying the normalization condition, but its sample complexity depends quadratically on B.
  • 3 Memory efficient streaming PCA: Theorem 3.2 guarantees tanθ(U,X)≤ε with probability 9/10 for (B,p)-round distributions after sufficiently many samples.
  • 3 Memory efficient streaming PCA: For p=k+Θ(k), the streaming method receives the general theorem’s stated guarantee, with a slightly stronger result available for all p≥k.
  • 3 Memory efficient streaming PCA: For power-law eigenvalues σj≈j^-c with c>1/2, the sample complexity becomes n=Õ(k^(2c+2)d/ε^2).
  • 3 Memory efficient streaming PCA: The error in each streaming iteration is represented as a noisy-power perturbation and bounded using matrix Chernoff concentration after truncating samples.The resulting iteration count is L=O(log(d/ε)/(1−σk+1/σk)).

4 Privacy-preserving singular vector computation

The paper instantiates the noisy power method with calibrated random noise to compute private singular vectors and low-rank approximations. The resulting algorithms provide nearly tight error bounds, including coherence-dependent improvements over dimension-based bounds.

  • 4 Privacy-preserving singular vector computation: The privacy guarantee is defined by comparing algorithm outputs on matrices differing in one entry by at most 1.
  • 4 Privacy-preserving singular vector computation: A Gaussian-noise instance of the noisy power method computes differentially private singular vectors in time nearly linear in the number of nonzero input entries.
  • 4 Privacy-preserving singular vector computation: Accurate private singular subspaces yield good spectral-norm low-rank approximations, including rank-2k outputs under the stated differential-privacy guarantee.
  • 4 Privacy-preserving singular vector computation: Under unit spectral-norm changes, Gaussian noise gives (ε,0)-differential privacy, while the corresponding bound matches a lower bound up to Õ(k).
  • 4 Privacy-preserving singular vector computation: Compared with the Kapralov–Talwar upper bound, the algorithm is faster by more than a quadratic factor in d and improves under (ε,δ)-privacy.
  • 4.3 Dimension-free bounds for incoherent matrices: The algorithm’s dimension dependence can be replaced by an essentially tight dependence on matrix coherence, resolving the main problem left open by Hardt and Roth.

A Deferred Concentration Inequalities

The appendix records concentration tools used to control Gaussian and Laplacian perturbations, including spectral norms, entrywise bounds, and matrix Chernoff deviations.

  • A scalar Chernoff inequality bounds deviations of sums of independent variables in [-1,1].
  • The appendix invokes standard Gaussian concentration properties to justify the stated probability bounds.
  • Gaussian perturbation bounds control the spectral norm of U⊤Gℓ uniformly across iterations with high probability.
  • The Laplacian analogue supplies corresponding concentration control for independently sampled Laplacian noise matrices.
  • Matrix Chernoff bounds control sums of independent, uniformly bounded random matrices around their mean.

B Reduction to symmetric matrices

Non-symmetric singular-vector problems are converted into symmetric eigendecomposition problems through a block-matrix construction that preserves the relevant parameters.

  • B Reduction to symmetric matrices: The block matrix A = [0 B; B⊤ 0] converts an m × n matrix B into a symmetric (m + n) × (m + n) matrix.This transformation preserves all parameters relevant to the analysis.
Loading 1311.2495v4…