Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
  Problems
  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.
