Efficient Globally Convergent Stochastic Optimization for Canonical
  Correlation Analysis
  We study the stochastic optimization of canonical correlation analysis (CCA),
whose objective is nonconvex and does not decouple over training samples.
Although several stochastic gradient based optimization algorithms have been
recently proposed to solve this problem, no global convergence guarantee was
provided by any of them. Inspired by the alternating least squares/power
iterations formulation of CCA, and the shift-and-invert preconditioning method
for PCA, we propose two globally convergent meta-algorithms for CCA, both of
which transform the original problem into sequences of least squares problems
that need only be solved approximately. We instantiate the meta-algorithms with
state-of-the-art SGD methods and obtain time complexities that significantly
improve upon that of previous work. Experimental results demonstrate their
superior performance.
