Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present a new streaming algorithm for canonical correlation analysis using a re-parametrization of the projection matrices. The algorithm enjoys improved computational complexity as well as convergence rate for extracting the top-k canonical components.

main_review: The main idea of the paper is clear and the theoretical analysis looks solid.
The key technique used in the approach is a re-parameterization of the projection matrices such that efficient off-the-shelf streaming PCA algorithms can be utilized.

Theoretical analysis shows that the algorithm can extract the top-k components at reduced computational complexity, from O(d^3) to O(d^2 k) per iteration where d is the dimensionality.

The authors performed extensive numerical experiments on several real datasets, where the proposed method generally captures a higher proportion of correlations. The authors also demonstrated the utility of the method in feature learning as well as a fairness application.
limitations_and_societal_impact: - From Figure 2, the proposed algorithm has subpar performance when the sample size is small.
- The fairness application utilizes a pre-trained network. When the network is biased, the linear CCA may not be sufficient to achieve fairness.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a stochastic algorithm for canonical correlation analysis (CCA). It is based on a reformulation of CCA so that it can use existing tools in online PCA and manifold optimization. Some convergence analyses are shown, and an abundance of experiments (mostly involving deep neural nets) are used to support the claims.
main_review: This paper has the appeal of modernizing CCA computations for large-scale machine learning tasks. However, I find this paper not clearly written: notations are not clearly defined and results are not clearly stated. I have an impression that this paper is rushed. Nevertheless, the experiments and applications seem interesting, so I can imagine that this paper would be much improved from revision and re-organization.

Some major questions:

- The reformulation does include the original constraints $U^T C_X U = I_k$ and $V^T C_Y V = I_k$, so I don't know why exactly the reformulation would help. Is it true that we only need to update the other decision variables and then the constraints for $U$ and $V$ are satisfied automatically? The algorithm seems to suggest so but I don't know why.

- In the analysis, many statistical assumptions are stated, but it is unclear how they are used. Proposition 1 seems to be a deterministic result, so I don't know why sub-Gaussian assumption is made. Theorem 1 is stated in an extremely ambiguous way.  What does it mean when it says "goes to zero"? (in terms of dimension?) Does it hold with high probability?

- Is $Exp$ clearly defined? What is the Riemannian gradient update? This is a major algorithmic component that should be clearly defined and stated. 

- The theoretical analysis does not seem to contain much novelty (many are cited), but the abstract suggest otherwise.
limitations_and_societal_impact: The authors do mention aspects of societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a Riemannian framework for stochastic CCA.  In particular, they reformulate the problem into an optimization problem over the Stiefel manifold, special orthogonal group, and triangular scaling matrices. The estimates on this product manifold are updated using Riemannian gradient descent. Assuming the iterates are restricted to a strongly convex geodesic ball, then the method converges with rate $O(1/t)$. In practice, the method performs well on a few real data experiments including baseline datasets, deep CCA, as well as an application in fairness.
main_review: Upsides:

+ The reformulation of the CCA problem is novel and interesting. It allows for more scalable and efficiently computable CCA.
+ Citations appear adequate.
+ The general idea of the paper is clear.
+ The method performs quite well in the given experiments. In particular, the scaling of deep CCA is interesting, as well as the application to fairness.
+ This is a novel manifold optimization application to CCA. In particular, it takes advantage of the fact that remaining on the manifold keeps the constraints satisfied. Furthermore, it casts the problem as an optimization over a product manifold, which is interesting.

Downsides:

- The manifold optimization techniques and results are just standard applications of known theorems. 
-The cited theorems seem to need the objective to be geodesically convex. Is it obvious that this is true for the new CCA objective used here? Furthermore, why are the other assumptions satisfied, i.e., why is the gradient bounded, and why are the iterates bounded?
- It is not clear why the performance degrades for Mediamill. In particular, the authors mention that it is due to the fact that the first eigenvalue is large, but it does not seem to be that much larger.  The data is not ill-conditioned, and it is reasonable that many datasets in the wild may exhibit qualities like this.
- Theorem 1 is not sufficiently clear. The assumptions are not clearly referenced. The use of the norm in Theorem 1 is strange, as it is between 1-dimensional quantities (differences in cost). Also, the statement is not precise, as it is unclear what it means for the quantity to “go to zero” — I don’t see a sequence defined here.
- It is not discussed how step sizes are chosen and how sensitive the method is to choices of these. Also, it seems like initialization may be important, but this is not discussed either.
- How would running projected gradient descent perform on (4)? How much does one gain from Riemannian optimization in practice?

---
After the response, I will raise my score to a 6 since they demonstrate that the function is geodesically convex. However, I think that the argument they use for the boundedness of the iterates needs to also be made more rigorous and included in a revision.
limitations_and_societal_impact: Societal impact is well-discussed, but the limitations need more expounding, and in particular, the assumptions needed for convergence in Proposition 4, as well as the non-convexity of the method.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of canonical correlation analysis (CCA) to find linear combinations that maximize the correlation between two random variables. Following a reformulation of the problem based on on the principal component analysis (PCA) solution, the authors propose a stochastic algorithm for CCA, called RSG+. Then, they show that their approach improves existing algorithms by achieving lower runtime complexity and/or better convergence rate. Finally, they compare the performance of their algorithm on different image datasets.
main_review: ## Originality

The main claim of the authors is to achieve significantly lower time complexity per iteration for solving the CCA problem while maintaining $\mathcal{O}(1/t)$ convergence.
The authors reformulate CCA using the solution to principal component analysis. Later, they show with Theorem 1 that the error between the reformulated and the original problem is bounded and goes to zero. 
All the convergence properties (Prop. 2-4) of the algorithm presented by the authors are proved using properties available in the literature, which the authors reference. 
Could the authors clarify the novelty of their approach, given that the convergence of the algorithm has already been proved in the literature ?

## Quality

The proof of Theorem 1 uses Def. 1 and Prop. 1 which are valid for subgaussian variables, while the assumption of Theorem 1 requires Gaussian variables for X and Y. 
Is it possible to generalize Theorem 1 and the later statements in section 2.1 to subgaussian variables ? 
Also, the introduction and section 2 introduce the problem for general random variables while the analysis in the paper seems to hold only for gaussian (or sub-gaussian variables).

Based on l.219-225, it seems that the most expensive part of the algorithm is to compute the SVD of matrices, which can be very expensive for large matrices. Would it be possible to further reduce the computational expense of the algorithm using the randomized SVD algorithm ?

Section 3.1: I cannot find the table reporting the runtime improvement over MSG, can the authors reference the table precisely.
Table 2 in the Supplementary Material is not clear (the caption is not detailed) and only references one runtime, is it for the authors' algorithm, MSG ?
Is there an explanation for why RSG+ underperforms when the top k eigenvalues are dominated by the top l eigenvalues ?

Section 3.2: The results from the experiment are not clear, do the authors claim that they maintain the same accuracy as DeepCCA while being able to scale to larger d ?

## Clarity

The paper is well written and the authors start by introducing the CCA problem and stating current challenges and their contributions clearly, which is very appreciable.
The structure of the paper is clear and the authors first go through the theoretical details, then describe their algorithm, and consider different numerical examples to evaluate it in practice.

l.76 I would appreciate more explanations/intuitions to motivate this reformulation
l.110 can the authors define the notation $\Sigma_x \leq cI_d$, does it mean that $c I_d-\Sigma_x$ is positive definite ? Why is this assumption needed ?
The statement of Thm 1 is not clear, can the authors specify the quantity that converges so that the error goes to 0 ?

Would it not make sense to write down the bound explicitly in the statement of the theorem 1 (at least in the supplementary material) ?

The paper would gain in clarity by adding a paragraph in the introduction about convergence rate (introducing the notion and reviewing the literature).

Minor comments:
- In the proof of Theorem 1, should the solution be denoted as $U$,$V$ instead of $U^\*$,$V^\*$ (following eq. (1)) ?
- l. 63 of the Supplementary Material, typo for "A. where"
- Throughout the paper, "eigen values" should read "eigenvalues"

## Significance

The contributions of this paper is significant as the algorithm proposed by the author has a lower time-complexity and a better convergence rate than alternating approaches. Therefore, it allows to scale in large dimensions.
limitations_and_societal_impact: The authors briefly discuss in the conclusions a potentially negative societal impacts if CCA is used for discriminative purposes. Similarly to the authors, I do not see a specific negative impact of the authors' approach.
review_title: null

Meta-review: The paper seems strong for both theoretical and practical point of view.
There were few issues with the paper, but it seems that most of them were solved during the rebuttal. 
The argument used for the boundedness of the iterates needs to be made more rigorous and included in the camera-ready version.
Decision: Accept (Poster)