Stochastic Canonical Correlation Analysis

Abstract

We study the sample complexity of canonical correlation analysis (CCA), \ie, the number of samples needed to estimate the population canonical correlation and directions up to arbitrarily small error. With mild assumptions on the data distribution, we show that in order to achieve $\epsilon$-suboptimality in a properly defined measure of alignment between the estimated canonical directions and the population solution, we can solve the empirical objective exactly with $N(\epsilon ,\Delta ,\gamma )$ samples, where $\Delta$ is the singular value gap of the whitened cross-covariance matrix and $1/\gamma$ is an upper bound of the condition number of auto-covariance matrices. Moreover, we can achieve the same learning accuracy by drawing the same level of samples and solving the empirical objective approximately with a stochastic optimization algorithm; this algorithm is based on the shift-and-invert power iterations and only needs to process the dataset for $\mathcal{O}\left(\log \frac{1}{\epsilon }\right)$ passes. Finally, we show that, given an estimate of the canonical correlation, the streaming version of the shift-and-invert power iterations achieves the same learning accuracy with the same level of sample complexity, by processing the data only once.

arXiv commentAccepted by JMLR

References in corpus (9)

• A Universal Catalyst for First-Order Optimization
• Fast and Simple PCA via Convex Optimization
• Large-Scale Approximate Kernel Canonical Correlation Analysis
• Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
• Sparse CCA via Precision Adjusted Iterative Thresholding
• Large scale canonical correlation analysis with iterative least squares
• Stochastic Approximation for Canonical Correlation Analysis
• Perturbation theory for the matrix square root and matrix modulus
• Dropping Convexity for More Efficient and Scalable Online Multiview Learning

Cited by in corpus (3)

• A simple normative network approximates local non-Hebbian learning in the cortex
• Tensor Canonical Correlation Analysis with Convergence and Statistical Guarantees
• Gen-Oja: A Two-time-scale approach for Streaming CCA