Efficient Convex Relaxations for Streaming PCA

Raman Arora, Teodor Vanislavov MarinovNeurIPS 2019 · OpenReview

Overview

This paper bridges the gap between theory and practice for convex relaxations of streaming Principal Component Analysis (PCA). By introducing mini-batching and a "warm start" strategy, the authors prove that convex algorithms—specifically Matrix Stochastic Gradient (MSG) and its $\ell_2$-regularized variant (RMSG)—can match the gold-standard efficiency of Oja’s algorithm while providing stronger convergence guarantees in challenging regimes.

The Challenge of Streaming PCA

Principal Component Analysis (PCA) is the go-to tool for dimensionality reduction. However, in the "streaming" setting—where data arrives one vector at a time—computing PCA becomes a moving target.

Traditionally, there are two primary ways to solve this:

  1. Non-convex methods (like Oja’s algorithm): These are incredibly fast, requiring only $O(dk)$ work per update (where $d$ is the dimension and $k$ is the target rank). However, they are mathematically "messy" because the underlying optimization problem is non-convex, making theoretical guarantees harder to establish.
  2. Convex relaxations (like MSG): These methods turn PCA into a convex problem, which is easier to analyze and often performs better in practice.

Despite the practical success of convex relaxations, there was a major theoretical catch: in the worst case, these algorithms might require $O(d^3)$ work per iteration because they manipulate large $d \times d$ matrices. The authors tackle this puzzling contradiction: why do these convex algorithms seem fast in experiments if the theory says they should be slow?

Proposed Methods: MB-MSG and MB-RMSG

The authors introduce MB-MSG and MB-RMSG (Mini-Batched versions of Matrix Stochastic Gradient and its $\ell_2$-regularized variant). Their approach relies on three key pillars to enforce efficiency:

  • Mini-batching as Variance Reduction: Instead of updating the model after every single data point, they group points into mini-batches. This reduces the "noise" in the gradient.
  • Rank Control: The core theoretical breakthrough of the paper is proving that if the gradient estimate is accurate enough (thanks to the mini-batch), the algorithm's internal matrix iterates stay at exactly rank-$k$. This is crucial because it allows the algorithm to use fast low-rank matrix math instead of heavy $d \times d$ operations.
  • Warm Start: They initialize the algorithm using a small initial batch of data to get the starting matrix close to the optimal subspace, ensuring the "rank control" kicks in immediately.

Key Insights

  • The "Unusual" Role of Variance Reduction: Usually, mini-batches are used simply to make optimization smoother. Here, the authors show that variance reduction is actually what enforces computational efficiency. By keeping the noise low, they prevent the matrix rank from "exploding," which keeps the per-iteration cost strictly at $O(dk)$.
  • Matching Oja’s Algorithm: For years, Oja’s algorithm was considered the efficiency ceiling. This paper shows that convex relaxations can reach that same ceiling while offering the stability of convex optimization.
  • Beating Oja in the "Small Gap" Regime: When the difference between the $k$-th and $(k+1)$-th eigenvalue (the eigengap) is very small, Oja’s algorithm struggles. The authors show that their RMSG variant can actually outperform Oja’s in these specific, difficult scenarios.

Empirical and Theoretical Results

The paper evaluates the algorithms on both synthetic high-dimensional data ($d=1000$) with a controlled eigengap, and the classic MNIST dataset ($d=784$) where the eigengap is naturally occurring.

  • Theoretical Parity: The authors successfully prove a total computational complexity that matches Oja’s algorithm up to a factor of $k$.
  • Rank Stability: In experiments, the "rank of iterates" for the mini-batched algorithms stayed consistently low (exactly at $k$), confirming that the theoretical efficiency translates perfectly to real-world performance.
  • Convergence: The paper provides "high probability" bounds for the last iterate of the algorithm, which is a stronger theoretical guarantee than the "average iterate" bounds provided in previous work.
Performance and rank stability of mini-batched algorithms compared to baselines across different target ranks.

As seen in the figure above, the mini-batched variants (MB-MSG and MB-RMSG) maintain a strict rank of $k$ throughout the iterations (bottom row), allowing them to achieve rapid suboptimality convergence (top row) without the computational bloat of their non-batched counterparts.

Limitations and Future Work

While a significant step forward, the approach has a few limitations:

  • Knowledge of the Eigengap: The proposed algorithms require knowing (or tuning) the eigengap $\Delta(C)$ as a hyperparameter. In practice, this value is often unknown and must be estimated.
  • Fixed Rank Assumption: The current proof techniques only work when the iterates are exactly rank-$k$. Extending this to cases where the rank is allowed to grow slightly ($k' > k$) remains an open challenge.
  • Objective vs. Subspace Angle: The guarantees provided are in terms of the optimization objective (variance explained). While standard in convex optimization, some practitioners prefer guarantees based on the "angle" between the predicted and true subspaces, which these bounds do not directly translate to.

Summary updated

Abstract

We revisit two algorithms, matrix stochastic gradient (MSG) and $\ell_2$-regularized MSG (RMSG), that are instances of stochastic gradient descent (SGD) on a convex relaxation to principal component analysis (PCA). These algorithms have been shown to outperform Oja’s algorithm, empirically, in terms of the iteration complexity, and to have runtime comparable with Oja’s. However, these findings are not supported by existing theoretical results. While the iteration complexity bound for $\ell_2$-RMSG was recently shown to match that of Oja’s algorithm, its theoretical efficiency was left as an open problem. In this work, we give improved bounds on per iteration cost of mini-batched variants of both MSG and $\ell_2$-RMSG and arrive at an algorithm with total computational complexity matching that of Oja's algorithm.
BibTeX
@inproceedings{arora2019efficient,
  author = {Raman Arora and Teodor Vanislavov Marinov},
  title = {{Efficient Convex Relaxations for Streaming PCA}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=zlDHcLByux3},
}
Figure