# Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems

arXiv: https://arxiv.org/abs/2112.14738 · HTML: https://mlsanity.com/paper/2112.14738/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 29 Dec 2021.

## Builds on (most cited first, 19 of 19)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression](https://mlsanity.com/paper/1804.02605/) (2018)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [Near-Optimal Stochastic Approximation for Online Principal Component Estimation](https://mlsanity.com/paper/1603.05305/) (2016)
- [Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis](https://mlsanity.com/paper/1604.03930/) (2016)
- [Stochastic Canonical Correlation Analysis](https://mlsanity.com/paper/1702.06533/) (2017)
- [Stochastic Approximation for Canonical Correlation Analysis](https://mlsanity.com/paper/1702.06818/) (2017)
- [Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow](https://mlsanity.com/paper/1604.08697/) (2016)
- [Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition](https://mlsanity.com/paper/1607.06017/) (2016)
- [Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis](https://mlsanity.com/paper/1506.08170/) (2015)
- [Stochastic Approximation for Online Tensorial Independent Component Analysis](https://mlsanity.com/paper/2012.14415/) (2020)
- [Gen-Oja: A Two-time-scale approach for Streaming CCA](https://mlsanity.com/paper/1811.08393/) (2018)

## Built on by (most cited first, 2 of 2)

- [General Tail Bounds for Non-Smooth Stochastic Mirror Descent](https://mlsanity.com/paper/2312.07142/) (2023)
- [A Generalized EigenGame with Extensions to Multiview Representation Learning](https://mlsanity.com/paper/2211.11323/) (2022)

## Abstract (arXiv)

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 √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.