  We propose novel first-order stochastic approximation algorithms for
canonical correlation analysis (CCA). Algorithms presented are instances of
inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated
gradient (MEG), and achieve $\epsilon$-suboptimality in the population
objective in $\operatorname{poly}(\frac{1}{\epsilon})$ iterations. We also
consider practical variants of the proposed algorithms and compare them with
other methods for CCA both theoretically and empirically.
