Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems

Chris Junchi Li, Michael I. JordanarXiv 2021 · arXiv

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

Abstract

Motivated by the problem of online canonical correlation analysis, we propose the \emph{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.
BibTeX
@misc{li2021nonconvex,
  author = {Chris Junchi Li and Michael I. Jordan},
  title = {{Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems}},
  year = {2021},
  eprint = {2112.14738},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14738},
}
Figure