Stochastic Approximation for Canonical Correlation Analysis
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.
I read the rebuttal and thank the authors for the clarifications about differences between the proposed method and previous work in [3,4]. I agreed with Reviewer 2's concerns about the limits of the evaluation section. Giving experiments on only one medium scale data set, it is insufficient to show the potential computational advantages of the proposed method (scale easily to very large datasets) compared to the alternative methods.
Summary
The paper proposes two novel first-order stochastic optimization algorithms to solve the online CCA problem. Inspired from previous work, the proposed algorithms are instances of noisy matrix stochastic / exponentiated gradient (MSG / MEG):  at each iteration, for a new sample (x_t , y_t), the algorithms work by first updating the empirical estimates of the whitening transformations which define the inexact gradient partial_t, followed by a projection step over the constrain set of the problem to get a rank-k projection matrix (M_t). The theoretical analysis and experimental results show the superiority of the algorithms compared to state-of-the-art methods for CCA.
Qualitative Assessment
Significance - Justification:
The main contributions of the paper are (1) the derivation of a new noisy stochastic mirror descent method to solve a convex relaxation for the online version of CCA and (2) the provision of 
generalization bounds (or convergence guarantees) for the proposed algorithms. These contributions appear to be incremental advances considered that similar solutions have been proposed previously  for PCA [3] and PLS [4].
Detailed comments:
The paper on the whole is well written, the algorithms are explained clearly, the theorems for the algorithms are solid and sound, and the performance of the algorithms outperforms that of state-of-the-art methods for CCA.
Some questions/comments:
What differentiates your algorithm from that of the previous work in references [3, 4]? Except solving different problems (CCA vs PCA and PLS), is your algorithm fundamentally different in some ways (e.g. add whitening transformations to alleviate the gradient updates for CCA problems or provide convergence analysis)? 
The reviewer read references [3, 4] and noticed that the algorithms in your papers are similar to those proposed in [3, 4] in terms of similar convex relaxation and stochastic optimization algorithms. The reviewer would have expected the authors to provide a comparison/summary of the differences / similarities between previous work [3, 4, 21] and current paper in the related work. This would also highlight explicitly the main contributions of the paper.
There are a few typos:
Line 90: build -> built; study -> studied
Line 91: in the batch setting ->  in a batch setting
Line 96: pose -> posed;  consider -> considered
Line 101-102: rewrite this sentence “none of the papers above give generalization
bounds and focus is entirely on analyzing the quality of the solution to that of the empirical minimizer”. I guess you intend to express the following: “all the papers mentioned above focus entirely / mainly on analyzing the quality of the solution to that of the empirical minimizer, but provide no generalization bounds”
remove line 150