Stochastic Approximation for Canonical Correlation Analysis

Raman Arora, Teodor Vanislavov Marinov, Poorya Mianjy, Nati Srebro

Canonical Correlation Analysis (CCA) is a cornerstone of multi-view learning, designed to find the highest linear correlations between two different "views" of data (e.g., video frames and their corresponding audio). However, traditional CCA methods struggle with massive, "streaming" datasets where only one sample can be processed at a time.

This paper introduces the first "natural" stochastic approximation algorithms for CCA that optimize for the underlying population distribution rather than just a fixed training set. Crucially, these algorithms achieve convergence without requiring an "eigengap"—a common but restrictive assumption in spectral methods—and scale efficiently to large-scale problems.

The Challenges of Scaling CCA

Scaling CCA to massive datasets presents three major hurdles that existing research has struggled to overcome:

  1. Non-convexity: The standard CCA objective is inherently non-convex, making it difficult to optimize directly using standard gradient-based methods.
  2. The "Ratio of Expectations" Problem: Unlike standard supervised learning, where the goal is to minimize an average loss, the CCA objective involves a ratio of expectations. This means it is impossible to get an unbiased estimate of the gradient from a single data sample, effectively breaking standard Stochastic Gradient Descent (SGD).
  3. The Eigengap Dependency: Most existing solvers only perform well if there is a significant gap between the correlation values of different components. If correlations are similar, these algorithms often fail or suffer from extremely slow convergence.

Proposed Stochastic Algorithms

To tackle these challenges, the authors propose two main algorithms based on a convex relaxation of the CCA problem. By "lifting" the problem into a higher-dimensional matrix space, they successfully transform the non-convex objective into a convex one.

  • MSG-CCA (Matrix Stochastic Gradient): This is an instance of inexact stochastic mirror descent using the Frobenius norm. Because an unbiased gradient cannot be calculated from a single sample, the algorithm relies on an "inexact" gradient based on running estimates of the data's "whitening" transformations (which normalize the variance of the views).
  • MEG-CCA (Matrix Exponentiated Gradient): This approach utilizes multiplicative weight updates (von Neumann entropy). MEG is frequently preferred for matrix problems because it can yield faster convergence rates in specific geometries.
  • Capped MSG-CCA (Practical Variant): To maintain computational speed, the authors introduce a "capping" mechanism. Instead of performing full $O(d^3)$ matrix operations, they explicitly constrain the rank of the iterates. This reduces the cost per iteration to $O(dK^2)$, where $K$ is the number of desired components.

Key Insights and Theoretical Guarantees

The theoretical contributions of this work are significant, particularly in how the algorithms handle noise and structural assumptions:

  • Eigengap-Free Convergence: The proposed algorithms are guaranteed to find an $\epsilon$-suboptimal solution regardless of whether the singular values of the data are well-separated. This removes a major bottleneck present in prior spectral methods.
  • Population vs. Empirical Risk: While most research focuses on fitting a fixed training dataset, this paper targets the population objective—ensuring that the learned components will generalize to unseen data drawn from the same underlying distribution.
  • Handling Inexactness: The authors provide a tight analysis of how gradient noise (caused by estimating covariance matrices on the fly) impacts convergence. They prove that even with biased, noisy gradients, the algorithms still converge at a sub-linear rate.

Empirical Results

The methods were evaluated on the Mediamill dataset, which consists of 10,000 samples of paired videos (120-dimensional visual features) and text commentary (100-dimensional textual features). The task was to recover the top $k$ correlated components ($k \in \{1, 2, 4\}$).

  • Iteration Complexity: Both MSG-CCA and MEG-CCA achieve $\epsilon$-suboptimality in the population objective in $O(1/\epsilon^2)$ iterations.
  • Runtime Performance: In empirical tests, Capped-MSG significantly outperformed existing state-of-the-art methods (such as CCALin and ALS-CCA) in total CPU runtime required to reach a target objective value.
  • Robustness: While traditional batch methods like Sample Average Approximation (SAA) are highly accurate, they are computationally prohibitive for large datasets. The proposed stochastic methods offer a vastly superior trade-off between accuracy and speed for large-scale streaming data.

Limitations and Future Work

Despite the strong theoretical and empirical results, the authors note a few areas for future exploration:

  • Optimistic Rates: For related problems like PCA, MEG often achieves "fast" (logarithmic) convergence rates. For CCA, however, the authors were unable to recover these fast rates because the error in the inexact gradient does not decrease quickly enough.
  • Theoretical Gap for Capping: While the "Capping" heuristic works exceptionally well in practice to reduce computational overhead, a rigorous theoretical understanding of why this constraint does not harm convergence is still needed.
  • Memory Constraints: Although the algorithms are designed for streaming data, they still require maintaining and updating estimates of whitening matrices. This could become a memory bottleneck for extremely high-dimensional datasets.

Summary updated

Abstract

We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve $\epsilon$-suboptimality in the population objective in $\operatorname{poly}(\frac{1}{\epsilon})$ iterations. We also consider practical variants of the proposed algorithms and compare them with other methods for CCA both theoretically and empirically.
BibTeX
@inproceedings{arora2017stochastic,
  author = {Raman Arora and Teodor Vanislavov Marinov and Poorya Mianjy and Nati Srebro},
  title = {{Stochastic Approximation for Canonical Correlation Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=S1NRYd-uWr},
}
Figure