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 ε-suboptimality in the population objective in poly(1/ε) iterations. We also consider practical variants of the proposed algorithms and compare them with other methods for CCA both theoretically and empirically.