Gen-Oja: Simple & 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 principle Generalized Eigenvector computation and Canonical Correlation Analysis (CCA) in the stochastic setting. We propose a simple and efficient algorithm 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 a foundational tool in machine learning for dimensionality reduction and feature extraction. While Oja’s algorithm provides an elegant streaming solution for PCA, many modern applications require solving the Generalized Eigenvalue Problem (GEP) or Canonical Correlation Analysis (CCA). These problems involve finding directions that maximize the ratio of expectations—the Rayleigh quotient—rather than a simple expectation.

In a streaming or stochastic setting, where data arrives one sample at a time, solving the GEP is significantly more challenging. Existing approaches often rely on computationally expensive matrix inversions, complex initialization schemes, or "batch-style" updates that fail to utilize the efficiency of a truly streaming process. This paper introduces Gen-Oja, a "two-line" streaming algorithm designed to match the simplicity of Oja’s algorithm while providing provable global convergence and optimal efficiency for the generalized case.

The Gen-Oja Algorithm

The Gen-Oja algorithm operates by updating two coupled sequences, $w_t$ and $v_t$, at every time step. This structure is rooted in the principle of two-time-scale stochastic approximation:

  1. The Fast Scale ($w_t$): This sequence performs a stochastic gradient step to minimize a least-squares objective. Its primary function is to estimate the product $B^{-1}Av_{t-1}$. By using a larger step size, $w_t$ is designed to evolve rapidly.
  2. The Slow Scale ($v_t$): This sequence utilizes the estimate provided by $w_t$ to perform a projection step, analogous to the original Oja’s algorithm. This step updates the estimate of the principal generalized eigenvector.

The core innovation lies in the coupling of these scales. Because the $w_t$ sequence mixes exponentially fast, it effectively "tracks" the necessary matrix operations. From the perspective of the slower $v_t$ sequence, the fast scale appears to have already converged to the correct direction, allowing the overall system to self-correct without explicit matrix inversion.

Theoretical Framework and Markovian Noise

Proving the convergence of Gen-Oja required addressing the inherent Markovian noise within the system. Unlike standard Stochastic Gradient Descent (SGD), where noise is typically assumed to be independent and identically distributed (i.i.d.), the noise in Gen-Oja is "sticky"—it depends on the entire history of the process because $w_t$ and $v_t$ are interdependent.

The authors developed new theoretical tools to show that as long as the fast-scale sequence mixes sufficiently quickly, the resulting noise remains controllable. This allows the algorithm to achieve the optimal convergence rate of $\tilde{O}(1/n)$, where $n$ is the number of samples—the theoretical gold standard for stochastic approximation.

Experimental Validation

To validate the theoretical findings, the authors conducted simulations using synthetic data streams. The experiments involved normally distributed matrices $(A_t, B_t)$ with a dimension of $d=20$ and up to $T=10^6$ samples. The underlying covariance matrices were structured with random eigenvectors and eigenvalues decaying at a rate of $1/i$ to simulate realistic data conditions.

Key empirical findings include:

  • Superior Convergence: Gen-Oja converged significantly faster and with higher accuracy than "two-step" methods that alternate between multiple least-squares steps and single eigenvector updates.
  • Robustness: The algorithm demonstrated robustness to the choice of the fast-scale step size ($\alpha$), though performance remained more sensitive to the slow-scale step size ($\beta$).
  • Global Reach: The algorithm consistently converged to the principal generalized eigenvector from random initializations, confirming the global convergence theory.

Discussion and Future Work

Gen-Oja represents a significant step forward in making generalized eigenvector computation as accessible as standard PCA in streaming environments. However, several avenues for future research remain:

  • Dimension Dependence: Current convergence bounds depend polynomially on the dimension $d$. Future work may seek "dimension-free" bounds where the rate is less sensitive to the number of features.
  • Eigengap Knowledge: Optimal step-size selection currently requires knowledge of the "eigengap" (the distance between the first and second eigenvalues). Implementing "streaming average" step sizes could potentially remove this requirement for practical applications.
  • Higher-Order Components: While this work focuses on the top eigenvector, extending Gen-Oja to compute the top $k$ eigenvectors (streaming $k$-CCA) is a promising direction for multi-dimensional data analysis.

Summary updated

Abstract

In this paper, we study the problems of principle Generalized Eigenvector computation and Canonical Correlation Analysis in the stochastic setting. We propose a simple and efficient algorithm 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: Simple \& Efficient Algorithm for Streaming Generalized Eigenvector Computation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJZjqDbuWr},
}
Figure