TL;DR
This paper introduces the first "natural" stochastic approximation algorithms for Canonical Correlation Analysis (CCA) that directly optimize for the population objective rather than just the training data. By using convex relaxation and inexact gradient updates, the researchers developed two algorithms—MSG-CCA and MEG-CCA—that scale efficiently to massive datasets and provide theoretical guarantees for generalization that don't rely on the "eigengap" assumptions required by previous methods.
What Problem Does This Paper Address?
Canonical Correlation Analysis (CCA) is a classic statistical tool used to find the best linear relationships between two different "views" of data (like video frames and their corresponding audio). While powerful for unsupervised learning, CCA is computationally difficult to scale.
The authors identify three major hurdles:
- Non-convexity: The standard formulation of CCA isn't convex, making it hard to optimize using standard gradient descent.
- Stochastic Constraints: Unlike standard machine learning problems where you minimize a sum of losses, CCA's constraints involve the covariance of the data itself. If you only see one sample at a time, you can't easily satisfy these constraints.
- The "Expectation" Problem: The CCA objective is a ratio of expectations, which doesn't decompose neatly into a sum over individual samples. This makes it very hard to get an "unbiased" estimate of the gradient from a single data point.
Most existing solutions are "batch" methods that look at the whole dataset at once, which is impossible for truly massive or streaming data.
Methods
The authors propose two primary algorithms based on Stochastic Approximation (SA), which process data one sample at a time:
- MSG-CCA (Matrix Stochastic Gradient): This method uses "lifting" to turn the non-convex problem into a convex one by looking at the matrix $M = UV^\top$. Because they can't get a perfect gradient, they use an inexact proximal gradient approach. They maintain a running estimate of the "whitening" transformations (which normalize the data) and use those to create a noisy, but useful, gradient estimate.
- MEG-CCA (Matrix Exponentiated Gradient): This is a multiplicative weight update version. It uses a technique called "self-adjoint dilation" to turn the rectangular CCA matrices into a larger symmetric matrix, allowing them to apply mirror descent with quantum relative entropy as the potential function.
To make these practical, they also introduced Capped MSG-CCA, which restricts the rank of the matrices during updates. This drops the computational cost per iteration from $O(d^3)$ to $O(dK^2)$, where $d$ is the data dimension and $K$ is the desired number of components.
Datasets
The researchers evaluated their algorithms on the Mediamill dataset.
- Content: 10,000 instances of paired videos and text commentary.
- Features: 120-dimensional visual features and 100-dimensional textual features.
- Goal: Learn a shared representation (top $k$ correlated directions) between the video and text views.
Key Insights and Ideas
- Optimizing for the Population: Most CCA research focuses on how well the algorithm performs on the specific samples it was given (Empirical Risk Minimization). This paper focuses on the population objective—how well the learned model will perform on new, unseen data from the same distribution.
- No Eigengap Needed: Traditional CCA analysis often assumes there is a significant "gap" between the strengths of different correlations (the eigengap). These new algorithms provide sub-optimality guarantees even if no such gap exists, making them more robust for real-world data.
- Handling "Inexact" Gradients: The authors proved that even though their gradient estimates are biased (because the whitening matrices are only estimates), the error decreases fast enough ($O(1/\sqrt{t})$) to ensure the whole algorithm still converges to the global optimum.
Key Results
- Theoretical Convergence: Both algorithms achieve $\epsilon$-suboptimality (getting within $\epsilon$ of the best possible correlation) in $poly(1/\epsilon)$ iterations.
- Speed vs. Accuracy: In head-to-head tests on the Mediamill dataset, the "Capped MSG" variant was the clear winner in terms of overall CPU runtime. While some batch methods (like CCALin) made more progress per iteration, they were much slower to compute each step.
- Scalability: Because these are streaming algorithms, they can handle datasets that are too large to fit into a computer's memory, which is a major limitation for traditional "batch" CCA.
Limitations and Future Work
- MEG-CCA Performance: While MEG-CCA has strong theoretical roots, it didn't achieve the "fast optimistic rates" seen in similar problems like PCA. The authors attribute this to the fact that the noise in the inexact gradients decreases too slowly.
- Heuristic Capping: The "Capped MSG" variant, while highly effective in practice, is currently a heuristic. The authors noted that more work is needed to provide the same rigorous theoretical guarantees for the capped version as they did for the full-rank version.
- Generalizing Inexact Proximal Gradient: The analysis used here for handling biased gradients might be applicable to a wider range of machine learning problems where unbiased gradients are difficult to obtain.
Summary updated