Introduction
Canonical Correlation Analysis (CCA) is a fundamental technique in multi-view learning, designed to identify the most correlated linear components between two distinct sets of variables. In practical applications, this allows researchers to find commonalities between different data modalities, such as video frames and their corresponding textual transcripts. Despite its utility, standard CCA solvers face significant hurdles when applied to modern, large-scale datasets. This paper, originally presented at NIPS 2017, introduces a novel framework for scaling CCA using stochastic optimization, providing the first "natural" stochastic approximation algorithms for the problem.
The Challenges of Scaling CCA
Traditional CCA solvers are "batch" methods, requiring the entire dataset to be loaded into memory. This approach is increasingly untenable for web-scale data. However, transitioning CCA to a stochastic (streaming) setting is not straightforward due to two primary issues:
- The "Expectation of a Ratio" Problem: Unlike standard Stochastic Gradient Descent (SGD), where the objective is a simple average of samples, the CCA objective involves a ratio of expectations due to whitening constraints. Consequently, a single sample does not provide an unbiased estimate of the gradient, causing standard stochastic optimization techniques to fail.
- The Eigengap Dependency: Many previous attempts at stochastic CCA required a significant "eigengap"—a clear separation between the top singular values—to guarantee convergence. In many real-world datasets, such a gap does not exist, rendering those methods unreliable.
Proposed Methodology: MSG and MEG
The authors address these challenges by employing Convex Relaxation (Lifting), transforming the non-convex CCA problem into a convex one by optimizing over a matrix $M$ that represents the product of the projection matrices. They propose two primary algorithms:
Matrix Stochastic Gradient (MSG-CCA)
MSG-CCA utilizes inexact proximal gradient descent. To overcome the unbiased gradient problem, the algorithm maintains running estimates of the data's covariance. These estimates are used to construct an "inexact gradient" that incrementally improves in accuracy as more data is processed. The authors provide a rigorous proof that as long as the error in the gradient estimate decays at a rate of $O(1/\sqrt{t})$, the algorithm will converge to the global optimum.
Matrix Exponentiated Gradient (MEG-CCA)
MEG-CCA employs multiplicative weight updates, specifically mirror descent with quantum relative entropy. While theoretically robust, this method is generally more computationally demanding than MSG.
Practical Implementation: Capped-MSG
The basic MSG algorithm carries a computational cost of $O(d^3)$ per iteration, where $d$ is the dimensionality. To make the approach viable for high-dimensional data, the authors introduced Capped-MSG. This variant explicitly restricts the rank of the iterates, reducing the cost per iteration to $O(dK^2)$, where $K$ is the number of desired components.
Theoretical and Empirical Results
Theoretical Contributions
A major contribution of this work is the focus on population suboptimality. Rather than simply fitting a fixed training set (Empirical Risk Minimization), the authors provide bounds on how many samples are required to generalize to the underlying data distribution. Notably, their convergence guarantees are eigengap-free, ensuring robustness even when singular values are closely clustered. Both MSG and MEG achieve $\epsilon$-suboptimality in $O(1/\epsilon^2)$ iterations.
Empirical Performance
The algorithms were evaluated using the Mediamill dataset, a multi-view benchmark consisting of 10,000 videos with 120-dimensional visual features and 100-dimensional textual annotations.
In these experiments, the Capped-MSG variant demonstrated superior performance in terms of CPU runtime compared to existing state-of-the-art methods like CCALin and ALS-CCA. While batch methods (Sample Average Approximation) may eventually reach higher objective values, the stochastic methods reach high-quality solutions significantly faster, making them ideal for large-scale applications where time and memory are constrained.
Limitations and Future Work
While Capped-MSG performs exceptionally well in practice, its theoretical guarantees are currently less developed than those of the uncapped version. Bridging this gap remains a priority for future research. Additionally, while the algorithms are more scalable than batch methods, they still involve matrix operations that can be intensive for extremely high-dimensional features. Finally, the algorithms require an auxiliary dataset to initialize whitening transforms, and the choice of the step size $\eta$ remains a critical practical consideration for users.
Summary updated