Abstract
Multiview representation learning is a cornerstone of latent factor analysis, essential for modeling dependencies across diverse data sources in machine learning and information retrieval. While researchers traditionally favor convex optimization for its guaranteed global optima, these formulations often impose significant computational and memory overhead. This paper investigates a nonconvex formulation for online multiview learning, specifically Partial Least Squares (PLS), solved via a simple stochastic gradient descent (SGD) algorithm. By modeling the algorithm as a continuous diffusion process, we establish asymptotic global convergence rates and demonstrate that dropping convexity yields a massive efficiency boost. Our theoretical findings, supported by numerical experiments, show that nonconvex SGD converges to the global optimum a full factor of $1/\epsilon$ faster than its convex counterparts.
Introduction
In the era of big data, multiview representation learning—finding shared patterns across different data sources, such as matching image pixels with text captions—requires algorithms that are both scalable and efficient. Partial Least Squares (PLS) is a common tool for this task, identifying low-dimensional subspaces that preserve the maximum covariance between two views.
Traditionally, theorists have relied on "convex relaxations" of these problems because they are mathematically safe; any local optimum is a global one. However, this safety comes with a "convexity tax." These methods require complex, computationally expensive projection steps and massive memory storage. Conversely, practitioners have long observed that "heuristic" nonconvex methods perform exceptionally well in practice, though they lacked rigorous theoretical justification. This research bridges that gap by providing a theoretical framework for nonconvex online multiview learning.
Methodology: The Generalized Hebbian Algorithm
The authors focus on the Generalized Hebbian Algorithm (GHA), also known as Sanger’s rule. Unlike standard convex approaches like Matrix Stochastic Gradient (MSG), GHA is a "dual-free" update. It avoids the $O(d^3)$ computational cost associated with projecting onto a feasible set and requires only $O(m + d)$ memory, rather than storing a full $m \times d$ matrix.
To prove convergence in a nonconvex landscape, the authors utilize diffusion approximations. Instead of analyzing the algorithm as a sequence of discrete jumps, they model the trajectory of the SGD as a solution to a Stochastic Differential Equation (SDE). This allows for a precise characterization of the optimization landscape's "physics" and the iterates' movement toward the global maximum.
The Geometry of Nonconvex Convergence
A key contribution of this work is the identification of the "Three-Phase Journey" that the algorithm undergoes to reach the optimum:
- Phase I (The Escape): The algorithm begins near an unstable saddle point. In this stage, it behaves like an Ornstein-Uhlenbeck (O-U) process, where stochastic randomness actually assists the iterates in escaping the bad equilibrium.
- Phase II (The Sprint): Once clear of the saddle point, the dynamics become nearly deterministic. The algorithm follows an Ordinary Differential Equation (ODE) trajectory directly toward the global maximum.
- Phase III (The Refinement): As it nears the optimum, the algorithm enters a final O-U phase, oscillating in a small, controlled random walk around the peak.
By characterizing the Hessian at stationary points, the authors prove that the only stable points in this nonconvex landscape are the global optima. All other stationary points are unstable, meaning the algorithm is naturally repelled by them.
Performance and Results
The paper validates its theory using both synthetic data (to visualize the three phases) and a real-world MNIST subset (handwritten digits 3, 4, 5, and 9). The results highlight several critical advantages of the nonconvex approach:
- Iteration Complexity: Nonconvex SGD achieves an $\epsilon$-optimal solution in $O(\epsilon^{-1} \log(\epsilon^{-1}))$ iterations, whereas the state-of-the-art convex version requires $O(\epsilon^{-2} \log(\epsilon^{-1}))$. This represents a $1/\epsilon$ speedup.
- Wall-Clock Efficiency: On the MNIST dataset, the nonconvex SGD significantly outperformed the convex MSG in actual runtime, primarily because it bypasses the expensive projection steps required by convex methods.
- Scalability: The algorithm’s memory footprint scales linearly with the number of features ($O(m+d)$), making it far more suitable for high-dimensional big data applications than matrix-based convex methods.
Conclusion and Future Work
This research demonstrates that for online multiview representation learning, nonconvexity is not a hurdle but an advantage. By leveraging the GHA and analyzing it through the lens of diffusion processes, the authors provide the first rigorous proof that simple nonconvex SGD is more efficient than complex convex relaxations.
Future work remains to extend these results beyond the rank-1 case (finding the top pair of singular vectors). Extending the analysis to rank-$r$ cases is challenging because solutions are no longer unique, complicating the SDE analysis. Additionally, while the current framework assumes a fixed step size, exploring diminishing step sizes and extending the analysis to Canonical Correlation Analysis (CCA)—where ODEs lack simple closed-form solutions—presents promising avenues for further investigation.
Summary updated