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

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.

arXiv commentAccepted at NeurIPS 2018

References in corpus (10)

• The Noisy Power Method: A Meta Algorithm with Applications
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Large scale canonical correlation analysis with iterative least squares
• Stochastic Approximation for Canonical Correlation Analysis
• Stochastic Canonical Correlation Analysis
• Discriminative Features via Generalized Eigenvectors