Abstract
Motivated by the problem of online canonical correlation analysis, we propose the Stochastic Scaled-Gradient Descent (SSGD) algorithm for minimizing the expectation of a stochastic function over a generic Riemannian manifold. SSGD generalizes the idea of projected stochastic gradient descent and allows the use of scaled stochastic gradients instead of stochastic gradients. In the special case of a spherical constraint, which arises in generalized eigenvector problems, we establish a nonasymptotic finite-sample bound of $\sqrt{1/T}$, and show that this rate is minimax optimal, up to a polylogarithmic factor of relevant parameters. On the asymptotic side, a novel trajectory-averaging argument allows us to achieve local asymptotic normality with a rate that matches that of Ruppert-Polyak-Juditsky averaging. We bring these ideas together in an application to online canonical correlation analysis, deriving, for the first time in the literature, an optimal one-time-scale algorithm with an explicit rate of local asymptotic convergence to normality. Numerical studies of canonical correlation analysis are also provided for synthetic data.
1. Introduction
Many fundamental tasks in machine learning—including Principal Component Analysis (PCA), Canonical Correlation Analysis (CCA), and Fisher’s Linear Discriminant Analysis—rely on solving Generalized Eigenvector (GEV) problems. These problems typically involve minimizing the Rayleigh quotient, a ratio of quadratic forms, which makes the objective function inherently nonconvex.
In the stochastic or "online" setting, a significant challenge arises: the gradient of a ratio of expectations is not equal to the expectation of the gradient of the ratio. This bias makes standard Stochastic Gradient Descent (SGD) difficult to apply directly. While previous research has proposed "two-time-scale" algorithms to manage this, such methods are often computationally expensive and difficult to tune. This paper introduces a simpler, "one-time-scale" approach that is both theoretically optimal and practically efficient.
2. The SSGD Framework
The core innovation of this work is Stochastic Scaled Gradient Descent (SSGD). The algorithm bypasses the need for an unbiased estimate of the true gradient $\nabla F(v)$ by using a stochastic vector $\Gamma(v; \zeta)$ that serves as an unbiased estimate of a scaled version of the gradient, $D(v)\nabla F(v)$, where $D(v)$ is a positive scalar factor.
Key methodological components include:
- The Scaling Trick: For GEV problems, replacing the complex denominator of the gradient with a constant creates a "scaled gradient" that maintains the correct direction for optimization while simplifying the stochastic update.
- Noise Injection: To ensure global convergence in a nonconvex landscape, the authors incorporate artificial spherical noise. This allows the algorithm to effectively escape unstable saddle points that might otherwise trap first-order methods.
- Trajectory Averaging: By employing Ruppert-Polyak-Juditsky averaging after an initial burn-in period, the estimator achieves asymptotic normality, providing statistical robustness and a clear path to convergence.
- Manifold Optimization: The algorithm is designed to handle optimization over the unit sphere, the natural Riemannian manifold for eigenvector problems.
3. Theoretical Guarantees
The authors provide rigorous theoretical backing for SSGD, establishing several key properties:
- Minimax Optimality: The algorithm achieves a convergence rate of $O(\sqrt{d/T})$, matching the information-theoretic lower bound for these problems.
- Local and Global Convergence: Given a "warm" start, the error decreases at a rate of $1/\sqrt{T}$. With noise injection, the algorithm is guaranteed to converge to the global optimizer regardless of the initial starting point.
- Asymptotic Normality: The averaged iterates $\bar{v}_T$ are shown to follow a Gaussian distribution centered at the true solution, a hallmark of high-quality stochastic approximation algorithms.
4. Numerical Results
The algorithm was evaluated using synthetic data for Canonical Correlation Analysis (CCA) with high-dimensional settings ($d_1=65, d_2=70$). The covariance matrices were constructed with a specific "eigengap" to test the algorithm's sensitivity and convergence speed.
As shown in the figure above, SSGD successfully escapes saddle point plateaus and converges to the optimal solution. In log-log simulations (not pictured), the squared error versus step-size $\eta$ yielded a slope of approximately $0.9921$, nearly identical to the theoretical value of $1.0$, confirming that the error scales linearly with the step size at stationarity.
5. Conclusion and Future Work
SSGD provides a robust, single-time-scale framework for solving GEV problems. While highly effective, future work could address the challenges of tuning noise variance in non-synthetic environments. Additionally, extending the theoretical framework from spherical constraints to more complex Riemannian manifolds, such as the Stiefel manifold for multiple eigenvectors, remains a promising direction for research.
Summary updated