Gen-Oja: A Two-time-scale approach for Streaming CCA

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

In modern machine learning, extracting meaningful patterns from high-dimensional data often requires identifying the most significant directions of variance or correlation. While Principal Component Analysis (PCA) is the standard tool for single-view data, Canonical Correlation Analysis (CCA) is required when dealing with two related sets of variables—such as audio and video streams or genomic and proteomic data.

Mathematically, CCA is a specific instance of the Generalized Eigenvalue Problem (GEP), which seeks a vector $v$ such that: $$Av = \lambda Bv$$ where $A$ and $B$ are covariance and cross-covariance matrices. In a streaming setting, where data arrives one sample at a time, we cannot afford to store these matrices or perform expensive $O(d^3)$ matrix inversions. While Oja’s algorithm provides an elegant solution for streaming PCA, adapting it to the GEP is non-trivial because the objective involves a ratio of expectations, leading to complex, non-independent noise structures.

The Challenge: Markovian Noise

The primary difficulty in streaming GEP/CCA is that the optimal direction depends on $B^{-1}A$. In a stochastic environment, we only have access to noisy samples $A_t$ and $B_t$. Simply plugging these into a standard update rule creates "Markovian noise"—noise that depends on the algorithm's previous state. This violates the standard assumptions of independent and identically distributed (IID) noise required by most stochastic approximation proofs.

The Gen-Oja Algorithm

To address this, we introduce Gen-Oja, a "two-line" iterative algorithm that decouples the estimation process into two distinct time scales:

  1. The Fast Scale ($w_t$): This sequence performs a stochastic gradient step to estimate the direction $B^{-1}Av_t$. By using a larger step size ($\alpha_t$), this component "mixes" quickly, allowing it to track the evolving eigenvector estimate.
  2. The Slow Scale ($v_t$): This represents the actual estimate of the principal generalized eigenvector. It uses a smaller step size ($\beta_t$) and performs an Oja-style update based on the direction provided by the fast-scale $w_t$.

Why the Two-Time-Scale Approach Works

Because the eigenvector estimate $v_t$ moves slowly, the fast-moving $w_t$ perceives $v_t$ as nearly stationary. This allows $w_t$ to converge toward the correct direction $B^{-1}Av_t$. Conversely, the slow scale $v_t$ treats $w_t$ as a noisy but increasingly accurate indicator of the principal generalized eigenvector. This symbiotic relationship allows the system to stabilize and converge without requiring explicit matrix inversions at each step.

Theoretical Contributions

We provide a rigorous global convergence analysis for Gen-Oja. By utilizing tools from the theory of fast-mixing Markov chains, we demonstrate that the Markovian noise eventually "washes out."

Our analysis shows that Gen-Oja achieves a convergence rate of $\tilde{O}(1/n)$, which is the optimal rate for stochastic approximation. Furthermore, unlike standard PCA algorithms that assume symmetry, our analysis specifically accounts for the asymmetry of $B^{-1}A$ by incorporating both right and left eigenvectors into the convergence proofs.

Empirical Results

We evaluated Gen-Oja using synthetic datasets with $d=20$ dimensions and $T=10^6$ streaming samples. The matrices $A$ and $B$ were designed with decaying eigenvalues to simulate realistic data structures.

  • Efficiency: Gen-Oja significantly outperformed "batch-streaming" methods—approaches that alternate between multiple SGD steps and a single Oja step. Gen-Oja converged an order of magnitude faster.
  • Robustness: The algorithm proved robust to step-size selection. As long as the fundamental two-time-scale relationship ($\beta_t \ll \alpha_t$) was maintained, the algorithm consistently achieved the $O(1/t)$ convergence rate.
  • Sample Complexity: Our results confirm that Gen-Oja produces an $\epsilon$-accurate estimate using only $O(1/\epsilon)$ samples with high probability ($> 4/5$).

Limitations and Future Work

While Gen-Oja represents a significant step forward for streaming CCA, several avenues for future research remain:

  • Dimension Dependence: Current bounds include polynomial factors of the dimension $d$. Future work could explore "dimension-free" analysis.
  • Gap-Free Settings: The current $O(1/n)$ rate assumes a spectral gap between the first and second eigenvalues. Investigating performance in gap-free scenarios is a logical next step.
  • Top-k Eigenvectors: This study focuses on the single principal eigenvector. Extending the two-time-scale framework to find the top $k$ eigenvectors (streaming k-CCA) would broaden its applicability to complex multi-dimensional data analysis.

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 Two-time-scale approach for Streaming CCA}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJZjqDbuWr},
}
Figure