Chris Junchi Li and Michael I. Jordan
University of California, Berkeley
Abstract
Generalized Eigenvector (GEV) problems, including Canonical Correlation Analysis (CCA) and Principal Component Analysis (PCA), are fundamental to statistical learning. However, solving these problems in an online, streaming setting presents significant challenges due to the biased nature of stochastic gradient estimates derived from ratio-based objectives. This paper introduces Stochastic Scaled-Gradient Descent (SSGD), a one-time-scale algorithm that utilizes unbiased estimates of scaled gradients. We demonstrate that SSGD achieves minimax optimal convergence rates, effectively escapes saddle points via noise injection, and exhibits asymptotic normality through trajectory averaging.
1. Introduction
In modern machine learning, Stochastic Gradient Descent (SGD) serves as the primary algorithmic engine for large-scale optimization. SGD's efficacy typically relies on the availability of unbiased estimates of the loss function's gradient. However, for a broad class of problems known as Generalized Eigenvector (GEV) problems—which underpin classical tools like Fisher’s Linear Discriminant Analysis (LDA) and Canonical Correlation Analysis (CCA)—obtaining such estimates is computationally non-trivial.
The objective function in GEV problems is generally expressed as a generalized Rayleigh quotient: $$f(v) = \frac{v^\top A v}{v^\top B v}$$
In a streaming data environment, where we receive samples to estimate matrices $A$ and $B$, the gradient $\nabla f(v)$ becomes a fraction where both the numerator and denominator involve expectations. Because the expectation of a ratio is not equal to the ratio of expectations, simple sample-based estimates are inherently biased. Previous attempts to resolve this bias have relied on complex "two-time-scale" learning rates or computationally intensive matrix inversions. This research proposes a simpler, one-time-scale alternative: Stochastic Scaled-Gradient Descent (SSGD).
2. Stochastic Scaled-Gradient Descent (SSGD)
The core innovation of SSGD is the realization that convergence to a global optimum does not strictly require the true gradient. Instead, the algorithm utilizes a "scaled" gradient. As long as the stochastic vector $\Gamma$ is an unbiased estimate of $D(v)\nabla F(v)$ (where $D(v)$ is a positive scalar), the algorithm can maintain the optimal convergence rate.
2.1 Methodology
The SSGD framework incorporates three critical components to ensure robustness and optimality:
- Double Stochastic Sampling: To circumvent the "ratio of expectations" bias, the algorithm employs two independent samples at each time step. This allows for the unbiased estimation of the product of terms within the GEV gradient.
- Noise Injection: To navigate the nonconvex landscape, the authors incorporate artificial spherical noise. This ensures the algorithm does not remain trapped at saddle points—points that appear optimal but are actually local maxima or inflection points.
- Trajectory Averaging: By applying Polyak-Juditsky averaging (averaging the iterates over time), the algorithm achieves "local asymptotic normality." This allows the estimates to behave as a Gaussian distribution centered at the true value, facilitating the creation of confidence intervals.
3. Theoretical Contributions and Results
The paper provides a rigorous theoretical foundation for SSGD, proving its efficacy across several dimensions:
- Minimax Optimality: The authors prove that SSGD achieves a finite-sample bound of $O(1/\sqrt{T})$. This matches the information-theoretic lower bound for GEV problems, establishing SSGD as an optimal algorithm.
- Saddle Point Evasion: The research provides a formal proof that SSGD, augmented with noise injection, will escape saddle point plateaus and identify a local minimizer with high probability.
- Dimension-Free Convergence: The local convergence analysis suggests a rate that is largely independent of the data dimension $d$, provided the noise is well-behaved. For specific applications like CCA, the rate scales as $O(\sqrt{d/T})$, matching the theoretical best possible performance.
4. Numerical Validation
The authors validated SSGD using synthetic datasets designed to simulate the complexities of high-dimensional CCA ($d_1 = 65, d_2 = 70$). By controlling the "eigengap"—the distance between the first and second eigenvalues—the researchers tested the algorithm's performance under varying levels of difficulty. The simulations confirmed that SSGD successfully escapes saddle point plateaus and converges to the global minimizer significantly faster than standard methods, confirming the theoretical predictions of asymptotic normality.
5. Conclusion and Future Work
SSGD represents a significant advancement in online nonconvex optimization, providing the first optimal, one-time-scale algorithm for generalized eigenvector problems. While the current analysis focuses on the unit sphere ($v \in S^{d-1}$), future research may extend these results to more complex Riemannian manifolds. Additionally, while synthetic tests are promising, applying SSGD to massive, real-world streaming datasets, such as web-scale cross-modal retrieval, remains an important next step for validating the algorithm's practical utility.
Summary updated