Gen-Oja: A Simple and Efficient Algorithm for Streaming Generalized Eigenvector Computation

Kush Bhatia, Aldo Pacchiano, Nicolas Flammarion, Peter L. Bartlett, Michael I. Jordan

Abstract

In this paper, we study the problems of principal Generalized Eigenvector computation and Canonical Correlation Analysis (CCA) in the stochastic setting. We propose a simple and efficient algorithm, Gen-Oja, for these problems. We prove the global convergence of our algorithm, borrowing ideas from the theory of fast-mixing Markov chains and two-time-scale stochastic approximation, showing that it achieves the optimal rate of convergence. In the process, we develop tools for understanding stochastic processes with Markovian noise which might be of independent interest.

Introduction

Principal Component Analysis (PCA) is the standard tool for identifying the direction of maximum variance in a single dataset. However, in multi-view data analysis—where two different sets of variables describe the same underlying phenomena—researchers often turn to Canonical Correlation Analysis (CCA). CCA seeks linear transformations that maximize the correlation between these views, a task that can be mathematically framed as a Generalized Eigenvalue Problem (GEP).

In modern data science, we increasingly encounter "streaming" scenarios where data arrives one sample at a time. In these contexts, storing the entire dataset or performing $O(d^3)$ matrix inversions is computationally infeasible. While Oja’s algorithm provides a famous and efficient solution for streaming PCA, a similarly simple and provably optimal counterpart for GEP has been elusive. The primary challenge lies in the fact that GEP involves maximizing a ratio of expectations, which introduces complex stochastic noise that is significantly harder to control than the noise in standard PCA.

The Gen-Oja Algorithm

We propose Gen-Oja, a "two-line" streaming algorithm designed to solve GEP and CCA on the fly. The algorithm maintains two coupled sequences that operate at different speeds:

  1. The Fast Scale ($w_t$): This sequence performs a single stochastic gradient step to solve an inner least-squares problem. Its role is to estimate the product $B^{-1}Av_t$.
  2. The Slow Scale ($v_t$): This sequence provides the actual estimate of the principal generalized eigenvector. It performs an update step similar to Oja’s algorithm but utilizes the output from the fast-scale sequence.

Two-Time-Scale Stochastic Approximation

The core innovation of Gen-Oja is the use of two-time-scale stochastic approximation. By setting the step sizes such that $w_t$ updates much faster than $v_t$, the fast scale "sees" $v_t$ as nearly constant and quickly converges toward the correct direction. Conversely, the slow scale $v_t$ "sees" the fast scale $w_t$ as a rapidly mixing Markov chain. This coupling allows the algorithm to remain simple while maintaining theoretical rigor.

Theoretical Contributions: Markovian Noise Control

Proving the convergence of Gen-Oja required moving beyond standard stochastic approximation tools, which typically assume independent noise. Because the updates in Gen-Oja are coupled, the noise is "Markovian" (dependent on previous states).

We utilized the theory of fast-mixing Markov chains to demonstrate that even though the noise is correlated, it decays quickly enough to allow for optimal convergence. Our analysis shows that Gen-Oja achieves a convergence rate of $\tilde{O}(1/n)$, which is the theoretical limit for these types of stochastic problems. These tools for understanding stochastic processes with Markovian noise represent a contribution that may be of independent interest to the optimization community.

Experimental Results

We evaluated Gen-Oja using synthetic streaming data with 20-dimensional vectors ($d=20$) and one million samples ($T=10^6$). The data streams were generated from normal distributions with covariance structures where eigenvalues decay as $1/i$, providing a clear principal direction for testing.

Key findings from our simulations include:

  • Superior Efficiency: Gen-Oja converged significantly faster than traditional "two-step" methods that alternate between blocks of SGD and Oja updates. Methods that required the inner loop to converge perfectly before updating the eigenvector were often an order of magnitude slower.
  • Robustness: The algorithm proved robust to various step-size choices. Even when parameters were not perfectly tuned to the specific eigengap of the problem, Gen-Oja maintained its $O(1/t)$ convergence rate, suggesting high practicality for real-world applications where exact problem parameters are unknown.

Conclusion and Future Work

Gen-Oja provides a simple, efficient, and provably optimal solution for streaming GEP and CCA. By leveraging two-time-scale approximation and Markovian noise analysis, we bridge the gap between the simplicity of Oja's algorithm and the complexity of generalized eigenvalue problems.

Future research directions include:

  • Dimension-Free Analysis: Reducing the current polynomial dependence on the dimension $d$ in the theoretical bounds.
  • Top-K Eigenvectors: Extending the two-time-scale analysis to find the top-$k$ eigenvectors (streaming $k$-CCA).
  • Gap-Free Settings: Investigating the convergence rates in scenarios where there is no significant gap between the first and second eigenvalues.

Summary updated

Abstract

In this paper, we study the problems of principal Generalized Eigenvector computation and Canonical Correlation Analysis in the stochastic setting. We propose a simple and efficient algorithm, Gen-Oja, for these problems. We prove the global convergence of our algorithm, borrowing ideas from the theory of fast-mixing Markov chains and two-time-scale stochastic approximation, showing that it achieves the optimal rate of convergence. In the process, we develop tools for understanding stochastic processes with Markovian noise which might be of independent interest.
BibTeX
@inproceedings{bhatia2018gen,
  author = {Kush Bhatia and Aldo Pacchiano and Nicolas Flammarion and Peter L. Bartlett and Michael I. Jordan},
  title = {{Gen-Oja: A Simple and Efficient Algorithm for Streaming Generalized Eigenvector Computation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJZjqDbuWr},
}
Figure