An Online Riemannian PCA for Stochastic Canonical Correlation Analysis
Authors: Zihang Meng
Rudrasis Chakraborty
Vikas Singh
Venue: NeurIPS 2021 Poster (2021)
Keywords: CCA
streaming
differential geometry
DeepCCA
fairness

Abstract: We present an efficient stochastic algorithm (RSG+) for canonical correlation analysis (CCA) using a reparametrization of the projection matrices. We show how this reparametrization (into structured matrices), simple in hindsight, directly presents an opportunity to repurpose/adjust mature techniques for numerical optimization on Riemannian manifolds. Our developments nicely complement existing methods for this problem which either require $O(d^3)$ time complexity per iteration with $O(\frac{1}{\sqrt{t}})$ convergence rate (where $d$ is the dimensionality) or only extract the top $1$ component with $O(\frac{1}{t})$ convergence rate. In contrast, our algorithm offers a strict improvement for this classical problem: it achieves $O(d^2k)$ runtime complexity per iteration for extracting the top $k$ canonical components with $O(\frac{1}{t})$ convergence rate. While the paper primarily focuses on the formulation and technical analysis of its properties, our experiments show that the empirical behavior on common datasets is quite promising, We also explore a potential application in training fair models where the label of protected attribute is missing or otherwise unavailable. 

An Online Riemannian PCA for Stochastic Canonical Correlation Analysis
Zihang Meng! Rudrasis Chakraborty" Vikas Singh
'University of Wisconsin-Maddisn Butlr
zihangmecs. wisc. edu, rudrasischa@gmail. com, vsingh@biostat. wisc. edu
Abstract
We present efficient stochastic algorithm (RSG+) for canonical correlation anal- ysis (CCA) using reparametrivation of the projection matrices. We show how this reparametrization (into structured matrices), simple in hindsight, directly presents an opportunity to repurpose/adjust mature techniques for numerical optimization Riemannian manifolds. Our developments nicely complement existing methods for this problem which either require ((d)) time complexity per iteration with O convergence rate (where d is the dimensionality) only extract the top component with O(t) convergence rate. In contrast, our algorithm offers an improvement: it achieves (dd)k) runtime complexity per iteration for extracting the top & canonical components with ( convergence rate. While our paper focuses more the formulation and the algorithm, our experiments show that the empirical behavior on common datasets is quite promising. We also explore a potential application in training fair models with missing sensitive attributes.
Introduction
Canonical correlation analysis (CCA) is classical method for evaluating correlations between two commonly used unsupervised multi-view learning, where multiple views of the data may correspond to image, text, audio and so on, RRpnik and Shawe-Taylor (2010) Chaudhuri et al. [2009). [uo et al. [2015), and has been applied to manifold-valued data also Kim et arl. [2014]. Classical formulations have also been extended to leverage advances in representation
sets of variables.
learning, for example, Andrew et al. [2013] showed how the CCA can interfaced with deep neural networks enabling modern use cases. Many results over the last few years have used CCA or its variants for problems including measuring representational similarity in deep neural networks Morcos et al. 2018 and speech recognition Couture et al. 2019].
The goal in CCA to find linear combinations within two random variables X and Y which have maximum correlation with each other. Formally, the CCA problem is defined as follows. Let X Nxd, and Y R. Nxd, N samples respectively drawn from pair of random variables X (d.-variate random variable) and Y (dy-variate random variable), with unknown joint probability distribution. The goal is to find the projection matrices U E Rd. and V R4,k with min(da, dy). such that the correlation maximized:
max F = trace (UT Vx U.V
s.t.
IT
(I)
Here, Cx + x X and Cy ==== denotes the sample cross-covariance.
LYTY y are the sample covariance matrices, and CXY
XX
N
The objective in [[] is the expected cross-correlation in the projected space and the constraints specify that different canonical components should be decorrelated. Let us define the whitened covariance
"qqual contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

T == Cx Cxy and dy (and Vx)) contains the top-k left (and right) singular vectors of
T. It is known Golub and Zha 1992 that the optimum of is achieved at U = Cx + D
V V²=C,'/24 ur We can compute U*, V* by applying a k-truncated SVD T'
Runtime and memory considerations. The above procedure is simple but is only feasible when the data matrices are small. In modern applications, not only are the datasets large but also the dimension d (let d = max(dg d of each sample can be large, especially if representations are learned using deep models. As a result, the resource needs of the algorithm can be high. This has motivated the study of stochastic optimization routines for solving CCA, and many efficient strategies have been proposed. For example, GG et al.] (2016). Waan et al. (2016) present Empirical Risk Minimization (ERM) models which optimize the empirical objective. More recently, Gao et al. 2019). [Bhatia et al.] 2018 Arora et al. 2017] describe proposals that optimize the population objective. To summarize the approaches, if we are satisfied with the top component of CCA, effective schemes with ( convergence rate are available by utilizing either extensions of the Oja's rule Oja generalized eigenvalue problem Bhatia et al. [2018) or the alternating SVRG algorithm Gao et al. [2019). Otherwise, stochastic approach will use an explicit whitening operation which can cost d' operations for each iteration Arora et al. (2017) and the convergence rate for the stochastic scheme
[982] to the
depends on its specific steps and calculations, e.g., O (17,) in Arora et al. [2017] (Thm 2.3, pp 5).
Observation. Most approaches either directly optimize (T) or instead a reparameterized or regularized form Ge et al. (2016). AAleen-Zhu and Li (2016), |Arora et al. [2017). Often, the search space for U and V corresponds to the entire R (ignoring the constraints for the moment). But if the formulation could be cast in form which involved approximately writing U and V as product of structured matrices, we may be able to obtain specialized routines which are tailored to exploit those properties. Such reformulation is not difficult to derive where the matrices used to express U and V can be identified as objects that live in well studied geometric spaces. Then, utilizing the geometry of the space and borrowing relevant tools from differential geometry could lead an efficient approximate scheme for top-k CCA which optimizes the population objective in a streaming fashion.
Contributions. (a) First, we re-parameterize the top-k CCA problem as optimization problem on specific matrix manifolds, and show that it is equivalent to the original formulation in (T. (b)
Informed by the geometry of the manifold, we derive stochastic gradient descent (SGD) algorithms for solving the re-parameterized problem with (d2 cost per iteration and provide convergence rate guarantees. (c) This analysis gives a direct mechanism to obtain upper bound the number of iterations needed to guarantee an e error w.r.t. the population objective for the CCA problem. (d) The algorithm works in streaming manner so it easily scales to large datasets and we do not need to assume access to the full dataset at the outset. (e) We present empirical evidence for the standard CCA model and the DeepCCA setting Andrew et al. (003), describing advantages and limitations.
Stochastic CCA: Reformulation, Algorithm and Analysis
Let us review the objective for CCA as given in [ We denote X E R.N xdz as the matrix consisting of the samples {x,} J drawn from zero mean random variable X ~ X' and Y E R Nxd, denotes the matrix consisting of samples {y:} drawn from zero mean random variable Y ~ ~J. For simplicity. although the results hold for general de and dy. Also recall that Cx (and Cy resp.) is the covariance matrix of X (and Y resp.) and Cxy is the cross-covariance matrix between X and Y. Let U E d (V E R ddkk) be the matrix consisting of (u,) ((v,)) where ((ug),(v)) are the canonical directions. The constraints in (1 are called whitening constraints.
we assume that d. = dy
Reformulation: In the CCA formulation, the matrices consisting of canonical correlation directions, i.e., U and V, are unconstrained, hence the search space is the entire Rdxk Now, we reformulate the CCA objective by reparameterizing U and V. In order to do that, let take brief detour and recall the objective function of principal component analysis (PCA):
i = arg max trace
subject to
U UT Is
(2)
Observe that by performing PCA and assigning U -R--- 1/2 in 1 (analogous for V using Cy),
we can satisfy the whitening constraint. Of course, writing = ÜR 1/2 does satisfy the whitening constraint, but such U (and V) will not maximize trace (U Vxr the objective of d Hence,
2

---

additional work beyond the PCA solution is needed. Let us start from R but relax the PCA solution by using arbitrary R instead of diagonal R. (this will still satisfy the whitening constraint).
Write U = UR with Ü-ū 1 and R E R*k Thus we can approximate CCA objective (we will later check how good this approximation is) as
trace (U'" + trace (i"CxŪ) + trace (v"C
U"CUU=h VTCyV=Iy
max (.
s.t.
R., R.E.R.
Free
U=OR,;; V-VR,
Here, St(kk d) denotes the manifold consisting of d x & (with k S d) column orthonormal matrices, i.e, St(k: d) - (x E R Rdx X X = =/x). Observe that in B3. we approximate the optimal and V as a linear combination of Ü and V respectively. Thus, the aforementioned PCA solution can act as a feasible initial solution for (3)
As the choice of R2 and R. is arbitrary, them to be full rank (of rank k) and using the RQ decomposition Golub and Reinsch [971 which gives the following reformulation.
further reparameteriize these matrices by constraining
A Reformulation for CCA
trace (U" VX)VV + trace (ū*CxÜ) + trace (V'CvV)
max
(4a)
S.. U= VVVS.Q
Fjs
subject to
U"CxU=I -
V"C = In
(4b)
Ú.V E St(k: d); Qu,Qu E E
S,, S, is upper triangular
Here, SO(k) is the space of 1 x k special orthogonal matrices, i.e., SO(k)
(X E R 6xk 1 xet( = 1]. Before evaluating how good the aforementioned approxima- tion is, first point some useful properties of the reformulation (4): (a) in the reparametrization of U and V, all components are structured, hence, the search space becomes a subset R x (b) we essentially initialize with PCA solution and then try optimize via some scheme.
Why (4) helps? First, we note that CCA seeks to maximize the total correlation under the constraint that different components are decorrelated. One difficulty in the optimization is to ensure decorre- lation, which leads to a higher complexity in existing streaming CCA algorithms. On the contrary, in (4). we separate [1] into finding the PCs, U, (by adding the variance maximization terms) and finding the linear combination (S..Q.. and S.Q of the principal directions. After optimizing for these variables, the whitening constraints are, up to a rescaling, automatically satisfied. Here, we can (almost) utilize efficient off-the-shelf streaming PCA algorithm. We will defer describing the specific details of the individual steps until the next sub-section. First, we will show why substituting (I) with (4) is sensible under some assumptions.
Why the solution of the reformulation makes sense? We start by stating some mild assumptions needed for the analysis. Assumptions: (a) The random variables X ~ NNO, E,,) and Y ~ NO E,y) with covariance Σ, A cIa and covariance Σ, 3 cla for some c > 0. (b) The samples X and Y drawn from X' and y respectively have zero mean. (c) For given is S d, Ex, Ey have non-zero top-k eigen values.
We show how the presented solution, assuming access to an effective numerical procedure, approxi- mates the CCA problem presented (T). We formally state the result the following theorem with sketch of proof (appendix includes the full proof) by first stating the following proposition.
Definition 1. A random variable X is called sub- Gaussian if the norm given by |||||=
inf (d > E [exp (1nce(XX" (oao(xxxxx/aa x)/a²)] < 2} is finite. Let U E Rdxk then XU is sub-Gaussian Ver shynin (2017).
Proposition RReiß et al. (2020). Let X be a random variable which follows sub- Gabssaassian distribution. Let X be the approximation of X Nxd (samples drawn from X) with the top-k
3

---

principal vectors. Let Cx be the covariance of X. Also, assume that X is the 1th eigen value of fxr 1,... .d 1 and X; 2 Net1 for all i. Then. the PCA reconstruction error, denoted by = Ex=EX x1| (in the Frobenius norm sense) can be upper bounded as follows
2
E S min (22k
A = Cxxxxxx
X AK+1
The aforementioned proposition suggests that the error between the data matrix X and the recon- structed data matrix X usiin the top-k principal vectors is bounded.
Recall from (T) and (4) that the optimal value of the true and approximated CCA objective denoted by F and F' respectively. The following theorem states that we can bound the error, E = || Fll (proof in the appendix). In other words, if we start from PCA solution and can successfully optimize (4) without leaving the feasible set, we will obtain good solution.
Theorem 1. Using the hypothesis and assumptions above, the approximation error E= = =| Fll as function of N is bounded and goes to zero as N while the whitening constraints in equation 4b are satisfied.
Sketch of the Proof. Let U and V be the true solution of CCA, i.e., of 11. Let -US V.QQu be the solution of 4.. with Ü, V be the PCA solutions of X and Y respectively. Let X XUUT and Φ YVVT be the reconstruction of X and Y using principal vec- tors. Let SuQu- = U and S.Q, = V'v. Then we can write = trace V)
T Pv") Similarly we can write F = trace (1 (XUT)-YV") As X and & = -trace ( (SUr)
the approximation of X and Y respectively using the principal vectors, we use Prop. D bound the error | - FlI. Now observe that XU can be rewritten into XUUTU (similar for VV). Thus, as long as the solution SmQu and S,Q, respectively well-approximate U and VTV, a good approximation of F.
Now, the only unresolved issue is optimization scheme for equation 4a that keeps the constraints in equation 45 satisfied by leveraging the geometry of the structured solution space.
2.1 How to numerically optimize 4a) satisfying constraints in (4b)
4by with respect to Ü, V, Qu. Qu. Sy and S... We will first compute top-k principal vectors to get U and V. Then, we will use gradient update rule solve for Qu. Qu. S, and S, to improve the objective. Since all these matrices are "structured", care must be taken to ensure that the matrices remain on their respective manifolds which is where the geometry of the manifolds will offer desirable properties. We re-purpose a Riemannian stochastic gradient descent (RSGD) to achieve this task, so call our algorithm RSG+. Of course, more sophisticated Riemannian optimization techniques can be substituted in. For instance, different Riemannian optimization methods are available in Absil et al. (2007) and optimization schemes for many manifolds are offered in PyManOpt Boumal et al. 20014).
Overview. We now describe how to maximize the formulation in (4a
The algorithm block is in Algorithm 1 Recall that Fp.. = trace (XTC + trace (VTCyV) is the contribution from the principal directions which we used to ensure the "whitening constraint". Moreover, F trace (UT (UTCyyVV) V) is the contribution from the canonical correlation directions (note that we use the subscript 'cea' for making CCA objective explicit). The algorithm consists of four main blocks denoted by different colors, namely (a) the Red block deals with gradient calculation of the objective function where we calculate the top-k principal vectors (denoted by Fpca) with respect to Ü, V: (b) the Green block describes calculation of the gradient corresponding to the canonical directions (denoted by F) with respect to Ü. V, S.,, S,,, Qn and Q.: (c) the Gray block combines the gradient computation from both Fpen and F with respect unknowns U, V. Su. S.. Qu and Qu: and finally (d) the Blue block performs batch update of the canonical directions F using Riemannian gradient updates.

---

Gradient calculations. The gradient update for Ü, V is divided into two parts (a) The (Red block)
gradient updates the "principal" directions (denoted by VyFes and Vy.fpaa). which is specifically designed to satisfy the whitening constraint. This requires updating the principal subspaces, so, the gradient descent needs to proceed the manifold of k-dimensional subspaces of R i..., the
Grassmannian Gr(k, d). (b) The (green block) gradient from the objective function in (4). is denoted
by ViFF and Vv.F. In order to ensure that the Riemannian gradient update for Ü and V stays on the manifold St(k, d), we need to make sure that the gradients, i.e., Vi and Vi F lies in the tangent space of St(k, d). To do so, we need to first calculate the Euclidean gradient and then project on to the tangent space of St(k:, d).
The gradient updates for Qu, Qu: S, are given the green block, denoted by Ve. VQ. Vs.. F. and V.,, F. Note that unlike the previous step, this gradient only has components from canonical correlation calculation. As before, this step requires first computing the Euclidean gradient and then projecting on to the tangent space of the underlying Riemannian manifolds involved, i.e., (O( and the space of upper triangular matrices.
Finally, we get the gradient to update the canonical directions by combining the gradients which is shown in the gray block. With these gradients we can perform a batch update as shown in the blue block. A schematic diagram is given in Fig.
Using results presented next in Propositions 2 3. this scheme can be shown (under some as- sumptions) to approximately optimize the CCA X R
Fy
Fo Fu Ry
6 - US.0
V V
objective in
Pixe
V..0.
We can now move to the convergence properties of the algorithm. We present two results stating the asymptotic proof of convergence for top-k principal vectors and canonical directions in the algorithm.
o.P. P. P.F.
Figure 1: Schematic diagram of the proposed CCA
Proposition 2 (Chakraborty et al. (2200). (Asymptoticallly If the samples, X. are drawn from a Gaussian distribution, then the gradient update rule presented in Step Algorithm
algorithm, here For F Fpen- where F is the approximated objective value for CCA (as in 44)
returns an orthonormal basis the top-k principal vectors of the covariance matrix Cx.
Proposition 3. (Bonnabel 2013 Consider a connected Riemannian manifold M with injectivity radius bounded from below by I > O. Assume that the sequence of step sizes (m) satisfy the condition (a) Σ 72 < co (b) Σ n oc. Suppose {At} lie in a compact set K C M. We also suppose that 3D > O such that, 9A, V. F. F) D. Then V + and - Dc.
Notice that in our problem, the injectivity radius bound in Proposition 3 is satisficd as "I" for Gr(p, n.). St(p, n)) or SO(p) is т 4/2/22, n /2/2,, x /2 respectively. So, order to apply Proposition 3 we need to guarantee the step sizes satisfy the aforementioned condition. One example of the step sizes that satisfies the property is "
1+1
2.2 Convergence rate and complexity of the RSG+ algorithm
In this section, describe the convergence rate and complexity of the algorithm proposed in Algorithm [ Observe that the key component of Algorithm is a Riemannian gradient update. Let A, be the generic entity needed to be updated in the algorithm using the Riemannian gradient update
A++1 Exp,,. (-1e A. FF) where "/ is the step size at time step t. Also assume
{At} C - for
a Riemannian manifold M. The following proposition states that under certain assumptions, the Riemannian gradient update has convergence rate of O (t).
Proposition 4. (Nemirovski al. (2009), Bécigneul and Ganea (2018)) Let {A,} lie inside geodesic ball of radius less than the minimum of the injectivity radius and the strong convexity radius of M. Assume M be geodesically complete Riemannian manifold with sectional curvature lower bounded by & & O. Moreover, assume that the step size {1t) diverges and the squared step size
converges. Then, the Riemunnian gradient descent update given by Act1 = Exp A.
5

---

Algorithm 1: Riemannian SGD based algorithm (RSG+) compute canonical directions
Input: X E R Nxdz, R Nxdx,
Output: R dedakk .V Rayxk
Initialize U, V, Qu: Su
Partition data X, into batches size B. Let jth batch be denoted by Xy and Y
for j E {1,.... . do
Gradient for top-k principal vectors: calculating V Fi. V Exe
1. Partition X, (Y₃) into L (L 2 () blocks of size d2 x (dy x k);
2. the 1th block be denoted by Zí (Z
3. Orthogonalize each block and
orthogonalized block denoted by 2/ (2
4. Let the subspace spanned by cach Zi (and 21r) be 27 Gr(k; d.) (and 2 E Gr(k, dz)):
ViPPa Expt (2i)
V Fpss
Σ Exp, 2
(5)
Gradient from equation
calculating
v F, V.F, Va. F, Vo. F, V. V.. F
0F VyF=
Ú
08
U
V F
V oF 0V oF
V
00
00
oV
Ve.
AF
Vq, F
8F 5Q
uQu
DQu
UQu
Vs.
F
Upper
OF
V Vs.
Upper
OF
38
85.
Here, Upper returns the upper triangular matrix of the input matrix and Fuclidean gradients, which are provided in appendix.
OF oF 8F oF
aF oF
give the
80
aQ. 8Q.
88.
Gradient to update canonical directions
Fo Vy V
V Fpl VpP:
Vx F where, generic entity: X (Qu, Qu Su, S.):
Batch update of canonical directions
-xpp y A
where, generic entity: A (Ū, V. Qu, Sw, S.):
10 end for
11 U = =ÜQS.. and V = VQ....:
with bounded V A,F. ie.. || C oo fo some C 0, converges the rale of O (t) with the number of iterates bounded by O(N D/E²), ) for some tolerance and for the Lipschitz bound D of the objective objectivvfuunction F.
For this result to be applicable, we need the CCA objective function to be geodesically convex function U and V (proof in the appendix). All Riemannian manifolds we needed, i.c., Gr(k, d). St(k, d) and SO(k) curvatures, i.c., lower bounded by x 0. Morcover the minimum convexity and injectivity radius for Gr(k, d). St(k: d) and SO(k) k) are π 1/2./2. Now, as long as the Riemannian updates lie inside geodesic ball radius less than // 222,2, the convergence rate for RGD applies in our setting.
geodesically complete, and these manifolds have non-negative sectional
Running time. To evaluate time complexity, we must look at the main compute-heays steps needed. The basic modules are Exp and Exp maps for St(k, d), Gr(k, d) and SO(k) manifolds (see Table 1 in appendix for detailed specification of these maps). Observe that the complexity of these modules is influenced by the complexity of svd needed for the Exp map for the St and Gr manifolds. Our algorithm involves structured matrices of size d and not exceed cost of O(max(d* k²)), since in general d > k. Specifically, the most expensive caleulation SVD of matrices of size which O k), see Golub and Reinsch 1971 All other calculations are dominated by this term.
so any matrix operation should

---

Table 1:
Wall-clock runtime of one pass through the data of our RSG+ and MSG on MNIST, Mediamill and CIFAR (average of 5 runs).
MNIST
Mediamill
CIFAR
Time (8)
2
k:
2
k
4
RSG+ (Ours)
4.16
4.24
4.71
1.89
1.60
1.44
14.80
17.22
22.10 106.55
MSG
35.32
42.09
49.17
11.59
14.21
17.34
80.21
100.80
3
Experiments
We first evaluate RSG+ for extracting top-k canonical components on three benchmark datasets and show that it performs favorably compared with Arora et al. [017]. Then, we show that RSG+ also fits into feature learning DeepCCA Andrew et al. 2013 and can scale large feature dimensions where the non-stochastic method fails. Finally, we show that RSG+ can be used to improve fairness
of deep neural networks without full access labels of protected attributes during training.
3.1 CCA on Fixed Datasets
Datasets and baseline. We conduct experiments three benchmark datasets (MNIST LeCun et al. 22000) Mediamill [noek
(Snckk et al. (006) and CIFAR-10 Krizhhvyyy (2009]) to evaluate the performance of RSG+ to extract top-k canonical components. To our knowledge, Arora et al. [2017) is the only
previous work which stochastically optimizes the population objective in a streaming fashion and
compare RSG+ with the matrix stochastic gradient (MSG) method proposed in Arora et al. [2017] (note: there are two methods proposed Arora et al. 20017]
can extract top-k components,
and choose MSG because it performs better in the experiments in Arora al. (0017). The details regarding the three datasets and how we process them are as follows:
LeCun al. 2010]: MNIST contains grey-scale images of size 28 x 28. We use its full training set containing 60K images. Every image is split into left/right half, which are used as the two views. Mediamill, [Snoek et al. [2006]: Mediamill contains around 25.8K paired features of videos and corresponding commentary of dimension 120, 101 respectively. CIFAR-10. Krizhevsky [2009]: CIFAR- 10 contains 60K 32 x 32 color images. Like MNIST, we split the images into left/right half and use them as two views.
Evaluation metric. We choose to use Proportion of Correlations Captured (PCC) which is widely used Ma et al. [2015). Ge et al. [2016], partly due to its efficiency, especially for relatively large datasets. Let U E Rd= V E x denote the estimated subspaces returned by RSG+, and U Rd V* E Rd, denote the true canonical subspaces (all for top-k). The PCC is defined TCC(xE,yV)
as PCC TCC(XU-YVYY. where TCC is the sum of canonical correlations between two matrices.
Performance. We run our algorithm with step sizes chosen from {1, 0.1, 0.01, 0.001, 0.0001, 0.00001). The performance in terms of PCC as function of the number of seen samples (shown in streaming manner) are shown in Fig. 2 and our RSG+ achieves around 10x runtime improvement over MSG (see Table Db. Our RSG+ captures more correlation than MSG Arora al. [2017] while
being - 10 times faster. One case where our RSG+ underperforms Arora et al.
[017]] 7 is when
the top-k eigenvalues are dominated by the top-/ eigenvalues with / k (Fig 2bp: on Mediamill
dataset, the top-4 cigenvalues of the covariance matrix in view are: 8.61, 2.99, 1.15, 0.37. The first eigenvalue is dominantly large compared the rest and our RSG+ performs better for A 1 and
worse than Arora et al. [2017) for k 2, 4. Runtime of RSG+ for different data dimensions (set d) and number of total samples (from a joint Gaussian distribution) is in the appendix.
d2 dy
3.2 CCA for Deep Feature Learning
Background and motivation. A deep neural network (DNN) extension of CCA was proposed by Andrew et al. (2013) and has become popular multi-view representation learning tasks. The idea is to learn a deep neural network as the mapping from original data space latent space where the canonical correlations are maximized. We refer the reader to Andrew al. (0133) for details of this requires
the task. Since deep neural networks are usually trained using SGD on
7

---

MEDIAMILL
CIFAR
0.7
0000000
2.3
0.8
03
Cu--r bud
Out lnd
09
0.1
aurplle abwn
suuppla 2007
Saurplls sownn
(a) on MNIST
(b) Mediamill
(c) on CIFAR
Figure 2: Performance on three datasets in terms of PCC function of # of seen samples.
obtaining estimate of the CCA objective at every iteration in streaming fashion, thus our RSG+ can be a natural fit. We conduct experiments on noisy version of MNIST dataset to evaluate RSG+.
Dataset. We follow Wang et al. [2155] to con- struct noisy version of MNIST: View randomly sampled image which is first rescaled [0, and then rotated by a random angle from [- -. View 2 is randomly sampled from the same class as view Then we add independent uniform noise from [0, to each pixel. Finally the image is truncated into [0, 1] to form view
Table 2: Results of feature learning MNIST.
N/A means fails to yield a result on our hardware.
Accuracy(%)
100
500
d 1000
DeepCCA Ours
80.57
N/A 84.09
N/A 86.39
79.79
Implementation details. We use a simple 2-layer MLP with ReLU nonlinearity, where the hidden
dimension in the middle 512 and the output feature dimension is d E [100, 500, 1000}. After the network is trained on the CCA objective, we use linear Support Vector Machine (SVM) to measure classification accuracy on output latent features. [Andrew et al.] [2013] uses the closed form CCA objective the current batch directly, which costs O(d") memory and time for every iteration.
Performance. Table 2 shows that get similar performance when d 100 and scale to large latent dimensions
1000 while the batch method Andrew et al. 2013) encounters numerical difficulty on our GPU resources and the Pytorch Paszke al. [2019 platform in performing an cigen-decomposition of a x d matrix when 500, and becomes difficult if d is larger than 1000.
3.3 CCA for Fairness applications
Block
Block
Black C
Block D
Block
Pretrained on gender
Leca
Block
Bllcd
Bleck
Block D
Bllck
Training on attractiveeess
2
Figure 3: Training architecture for fairness experiment. The model above is the pretrained model and the model below being trained. Use CCA allows the two network architectures be different.
Background and motivation. Fairness is becoming an important issue to consider the design of learning algorithms. A common strategy to make algorithm fair is to remove the influence of

---

one/more protected attributes when training the models, see Lokhande et al. [2020]. Most methods assume that the labels of protected attributes are known during training but this may not always be possible. CCA enables considering a slightly different setting, where we may not have per-sample protected attributes which may be sensitive or hard to obtain for third-parties [Price and Cohen [2019]. On the other hand, we assume that a model pre-trained to predict the protected attribute labels is provided. For example, if the protected attribute is gender, we only assume that a good classifier which is trained to predict gender from the samples is available rather than sample-wise gender values themselves. We next demonstrate that fairness of the model, using standard measures, can be improved via constraints correlation values from CCA.
Dataset. CelebA Wang et al., [2015b] consists of 200K celebrity face images from the internet. There are up to 40 labels. each of which is binary-valued. Here, we follow Lokhande et al. [2020] to focus on the attactiveness attribute (which we want to train classifier to predict) and the gender is treated as "protected" since it may lead to an unfair classifier according to Lokhande et al. [2020).
Method. Our strategy inspired by |Moroos et al. (2018) which showed that canonical correlations can reveal the similarity in neu- ral networks: when two net- works (same architecture) are trained using different labels/schemes for exam- ple, canonical correlations can indicate how similar their features are. Our ob- servation is the following. Consider a classifier that is trained on gender (the pro- tected attribute), and another classifier that is trained attractiveness, if the features extracted by the latter model share a high similarity with the one trained to predict gender, then it is more likely that the latter model is influenced by features in the image pertinent to gender, which will lead to an unfairly biased trained model. We show that by imposing a loss on the canonical correlation between the network being trained (but lack per-sample protected attribute information) and well trained classifier pre-trained on the protected attributes, we can obtain a more fair model. This may enable training fairer models in settings which would otherwise be difficult. The training architecture is shown in Fig.
Table 3: Fairness results on CelebA. We applied CCA on three dif- ferent layers in Resnet- 18 respectively. See appendix for positions of conv 0, 1, 1. "Ours-conv(O.) [0,1]]conv[1,2)) means stacking features from different layers to form hypercolumn features Hariharan et al. (2013), which shows that our approach allows two networks to have different shape/size.
Accuracy($6)
DEO(%)
DDP(%)
Unconstrained
76.3
22.3
4.8
Ours-conv)
76.5
17.4
1.4
Ours-cony1
77.7
15.3
3.2
Ours-conv2
75.9
22.0
2.8
76.0
22.1
3.9
Implementation details. To simulate the case where we only have pretrained network protected attributes, we train a Resnet-18 He et al. [2016) on the gender attribute, and when we train the classifier to predict attractiveness, we add loss using the canonical correlations between these two networks on intermediate layers: Laotal = Tecoss entropy LecA where the first term is the standard cross entropy term and the second term is the canonical correlation. See appendix for more details of training/evaluation.
Results. We choose two commonly used enror metrics for fairness: difference in Equality of Opportunity Hardt et al. (2016) (DEO), and difference in Demographic Parity Yao and Huang [017]] (DDP). We conduct experiments by applying the canonical correlation loss on three different layers in Resnet-18, 18. In T 3 we can see that applying canonical correlation loss generally improves the DEO and DDP metries (lower is better) over the standard model (trained using cross entropy loss only). Specifically, applying the loss on early layers like convŌ and convl gets better performance than applying relatively late layer like conv2. Another promising aspect of our approach is that is can easily handle the case where the protected attribute is continuous variable (as long as a well trained regression network the protected attribute is given) while other methods like Lokhande et al. 22200) Zhang et al. (2018) need to first discretize the variable and then enforce constraints which can be much more involved.
Limitations. Our current implementation has difficulty to scale beyond d = 10a data dimension and this may be desirable for large scale DNNs. Exploring sparsity may be one way to solve the problem and will be enabled by additional developments in modern toolboxes.

---

4 Related Work
Stochastic CCA: There has been much interest in designing scalable and provable algorithms for CCA:|Ma et al. [2015] proposed the first stochastic algorithm for CCA, where local convergence is proven for the non-stochastic version. Wang et al. (0166 designed an algorithm which uses alternating SVRG combined with shift-and-invert pre-condiiioning with global convergence properties. These stochastic methods, and [ie et al. [2016] Allen-Zhu and Lij [2016], which reduce the CCA problem to generalized eigenvalue problem and solve it via an efficient power method, all belong to the class of methods that seeks to to solve the empirical CCA problem. It can be seen as an ERM approximation of the original population objective, which requires solving numerically the empirical CCA objective on a fixed data set. These methods usually assume access to the full dataset at the outset, which may not be suitable for some practical applications where data presented in streaming manner. Recently. there appears to be an interest in considering the population CCA problem Arora et al. [017]] Gao et al. 2019]. The main difficulty in the population setting is that we have limited knowledge about the objective unless we know the distribution of X and Y. FAroa et al.) [2117] handles this problem by deriving an estimation of the gradient of the population objective whose error can be properly bounded so that applying proximal gradient to a convex relaxed objective will provably converge. Gao et al. [2019] provides a tightened analysis of the time complexity of the algorithm in Wang et al.) [2016], and provides sample complexity for certain distributions. The problem we study is similar to the one in Arora et al. [207], Gao et al. 2019 to optimize the population objective of CCA in a streaming fashion.
Riemannian optimization is a generalization of standard Euclidean optimization methods to smooth manifolds, which takes the following form: given f M - R. solve minge, (x)) where M is a Riemannian manifold. Advantages often include efficient numerical procedures for certain classes of constrained optimization problems. Applications include matrix and tensor factorization Ishteva et al. [011]. [Tan et al. 2014), PCA EEdelmnn et al. [1998]. CCA Yger et al. 2012). and so on. We remark that Y ger et al. 2012) also describes CCA formulation by rewriting it as a Riemannian optimization on the Stiefel manifold. our work, we further explore the benefits of the Riemannian optimization toolkit, decomposing the linear space spanned by canonical vectors into products of several matrices which lie in several different Riemannian manifolds.
Riemannian Optimization:
5 Conclusions
In this work, we presented a stochastic approach (RSG+) for the CCA model based on the observation that the solution of CCA can be decomposed into product of matrices which lic certain structured spaces. This affords specialized numerical schemes and makes the optimization more efficient. The optimization is based Riemannian stochastic gradient descent and we provide proof for its O(t) convergence rate with the number of iterates upper bounded, with (dd2k) time complexity per iteration. In experimental evaluations, we find that our RSG+ behaves favorably relative the baseline stochastic CCA method in capturing the correlation in the datasets. We also show the use of RSG+ in the DeepCCA setting showing feasibility when scaling large dimensions well as in an interesting use case in training fair models.
Our full codebase is available for use at http://giii...cooo//agg//////aaa
Potential negative societal impacts. Since CCA is a fundamental problem in statistical machine learning and not tied to specific applications, we do not see a negative socictal impact of our proposed method. However, it is possible that CCA can be used to uncover relationships between measurements which can be used for undesirable purposes.
6 Acknowledgments
This work was supported by NIH RFIAG0593 12, RFLAG062336 and ROIEB022883, and NSF CCF 11918211. We thank Vishnu Lokhande for help with setting up the fairness experiments.
References
P.A. Absil, R. E. Mahony, and R. Sepulchre. Optimization algorithms matrix manifolds. 2007.
10

---

Z. Allen-Zhu and Y. Li. Doubly accelerated methods for faster eca and generalized eigendecomposi tion. In ICML, 2016.
G. Andrew, R. Arora, J. Bilmes, and K. Livescu. Deep canonical correlation analysis. In International conference on machine learning, pages 1247-1255, 2013.
R. Arora, T. V. Marinov, P. Mianjy, and N. Srebro. Stochastic approximation for canonical correlation analysis. In Advances in Neural Information Processing Systems, pages 4775-4784, 2017.
G. Bécigneul and O.-E. Ganea. Riemannian adaptive optimization methods. arXiv preprint arXiv: 1810.00760, 2018.
K. Bhatia, A. Pacchiano, N. Flammarion, P. Bartlett, and M. I. Jordan. Gen-oja: Simple & efficient algorithm for streaming generalized eigenvector computation. In Advances Neural Information Processing Systems, pages 7016-7025, 2018.
S. Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2117-2229 2013.
N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, matlab toolbox for optimization on manifolds. The Journal of Machine Learning Research, 15(1):1455-1455 2014.
R. Chakraborty, L. Yang, S. Hauberg, and B. Vemuri. Intrinsic grassmann averages for online linear, robust and nonlinear subspace learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
K. Chaudhuri, S. M. Kakade, K. Liveseu, and K. Sridharan. Multi-view clustering via canonical correlation analysis. In Proceedings of the 26th annual international conference machine learning, pages 136, 2009.
H. D. Couture, R. Kwitt, J. S. Marron, M. A. Troester, C. M. Perou, and M. Niethammer. Deep multi-view learning via task-optimal cca. ArXiv, abs/1907.00733 2019.
A. Edelman, T. A. Arias, and S. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20:303-353, 1998.
C. Gao, D. Garber, N. Srebro, Wang, and Wang. Stochastic canonical correlation analysis. Journal of Machine Learning Research, 20(167):1 2019
R. Ge, C. Jin, P. Netrapalli, A. Sidford, et al. Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. In International Conference Machine Learning, pages 2741-2750, 2016.
G. H. Golub and C. Reinsch. Singular value decomposition and least squares solutions. In Linear Algebra, pages 134-151. Springer, 1971.
G. H. Golub and H. Zha. The canonical correlations of matrix pairs and their numerical computation. 1992.
M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pages 3315-3323, 2016.
B. Hariharan, P. Arbeláez, R. Girshick, and Malik. Hypercolumns for object segmentation and fine fine-graine grained localization. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 447-456, 2015.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
M. Ishteva, P.-.. Absil, S. V. Huffel, and L.. D. Lathauwer. Best low multilinear rank approximation of higher-order tensors, based on the riemannian trust-region scheme. SIAM J. Matrix Anal. Appl., 32:1 15-135, 2011.

---

J. Kim, N. Adluru, B. B. Bendlin, S. C. Johnson, B. C. Vemuri, and V. Singh. Canonical correlation analysis on riemannian manifolds and its applications. In European Conference on Computer Vision, pages 251-267. Springer, 2014.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com www..//wwww.oo//ee//iiiisssss 2, 2010.
V. S. Lokhande, A. K. Akash, S. N. Ravi, and V. Singh. Fairalm: Augmented lagrangian method for training fair models with little regret. In European Conference Computer Vision, pages 365-381. Springer, 2020.
Y. Luo, D. Tao, K. Ramamohanarao, C. Xu, and Y. Wen. Tensor canonical correlation analysis for multi-view dimension reduction. IEEE transactions on Knowledge and Data Engineering, 27(11); 3111-3124, 2015.
Z. Ma, Y. Lu, and D. Foster. Finding linear structure in large datasets with scalable canonical correlation analysis. In ICML, 2015.
A. Morcos, M. Raghu, and Bengio. Insights on representational similarity neural networks with canonical correlation. In Advances in Neural Information Processing Systems, pages 5727-5736, 2018.
A. Nemirovski, A. B. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optimization, 19:1574-1609 2009.
E. Oja. Simplified neuron model as a principal component analyzer. Journal of Mathematical Biology, 15:267-273, 1982.
A. Paszke, S. Gross, Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Lin, Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
W. N. Price and G. Cohen. Privacy in the age of medical big data. Nature medicine, 25(1):37-43, 2019.
M. ReiB, M. Wahl, et al. Nonasymptotic upper bounds for the reconstruction error of pca. Annals of Statistics, 48(2): 1098-112,, 2020.
Rupnik and J. Shawe-Taylos Multi-view canonical correlation analysis. In Conference on Data Mining and Data Warehouses (SiKDD 2010), pages 1-4, 2010.
C. Snoek, M. Worring, J. C. Van Gemert, J.-M. Geusebroek, and W. Smeulders. The challenge problem for automated detection of 101 semantic concepts in multimedia. In Proceedings of the 14th ACM international conference on Multimedia, pages 421-430, 2006.
M. Tan, I. W.-H. Tsang, I.. Wang, B. Vandereycken, and S. J. Pan. Riemannian pursuit for big matrix recovery. In JCML,, 2014.
R. Vershynin. Four lectures on probabilistic methods for data science. The Mathematics of Data, IAS/Park City Mathematics Series, pages 231-271, 2017.
W. Wang, R. Arora, K. Livescu, and J. Bilmes. On deep multi-view representation learning. In International Conference Machine Learning, pages 1083-1092, 2015a.
W. Wang, R. Arora, K. Livescu, and N. Srebro. Stochastic optimization for deep cca via nonlinear orthogonal iterations. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 688-695. IEEE, 2015b.
W. Wang. J. Wang, D. Garber, and N. Srebro. Efficient globally convergent stochastic optimization for canonical correlation analysis. In Advances Neural Information Processing Systems, pages 766-774, 2016.
12

---

S. Yao and B. Huang. Beyond parity: Fairness objectives for collaborative filtering. In Advances in Neural Information Processing Systems, pages 2921-2930, 2017.
Yger, M. Berar, G. Gasso, and A. Rakotomamonjy. Adaptive canonical correlation analysis based on matrix manifolds, In ICML, 2012.
B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335-340, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See experiment section (last subsection in fairness experiment).
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the last subsection the paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section 2
(b) Did you include complete proofs of all theoretical results? [Yes] See section 2 and supplement.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplement
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See experiment section.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] The performance reported was averaged over several different runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See experiment section.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] License can be found in cited paper/website.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] In supplement.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "cafanesiBg7", "reviewer": "Reviewer_VGVu", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nSome major questions:\n\n- 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.\n\n- 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?\n\n- Is $Exp$ clearly defined? What is the Riemannian gradient update? This is a major algorithmic component that should be clearly defined and stated. \n\n- The theoretical analysis does not seem to contain much novelty (many are cited), but the abstract suggest otherwise.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do mention aspects of societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "9SPDbdhDS3", "reviewer": "Reviewer_FnHY", "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main idea of the paper is clear and the theoretical analysis looks solid.\nThe 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.\n\nTheoretical 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.\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- From Figure 2, the proposed algorithm has subpar performance when the sample size is small.\n- The fairness application utilizes a pre-trained network. When the network is biased, the linear CCA may not be sufficient to achieve fairness.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "5a53wuHKuOT", "reviewer": "Reviewer_P3Jd", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\n\nThe 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.\nThe 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. \nAll 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. \nCould the authors clarify the novelty of their approach, given that the convergence of the algorithm has already been proved in the literature ?\n\n## Quality\n\nThe 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. \nIs it possible to generalize Theorem 1 and the later statements in section 2.1 to subgaussian variables ? \nAlso, 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).\n\nBased 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 ?\n\nSection 3.1: I cannot find the table reporting the runtime improvement over MSG, can the authors reference the table precisely.\nTable 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 ?\nIs there an explanation for why RSG+ underperforms when the top k eigenvalues are dominated by the top l eigenvalues ?\n\nSection 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 ?\n\n## Clarity\n\nThe 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.\nThe 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.\n\nl.76 I would appreciate more explanations/intuitions to motivate this reformulation\nl.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 ?\nThe statement of Thm 1 is not clear, can the authors specify the quantity that converges so that the error goes to 0 ?\n\nWould it not make sense to write down the bound explicitly in the statement of the theorem 1 (at least in the supplementary material) ?\n\nThe paper would gain in clarity by adding a paragraph in the introduction about convergence rate (introducing the notion and reviewing the literature).\n\nMinor comments:\n- In the proof of Theorem 1, should the solution be denoted as $U$,$V$ instead of $U^\\*$,$V^\\*$ (following eq. (1)) ?\n- l. 63 of the Supplementary Material, typo for \"A. where\"\n- Throughout the paper, \"eigen values\" should read \"eigenvalues\"\n\n## Significance\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "4MxNy2oZ3gt", "reviewer": "Reviewer_LueT", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Upsides:\n\n+ The reformulation of the CCA problem is novel and interesting. It allows for more scalable and efficiently computable CCA.\n+ Citations appear adequate.\n+ The general idea of the paper is clear.\n+ 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.\n+ 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.\n\nDownsides:\n\n- The manifold optimization techniques and results are just standard applications of known theorems. \n-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?\n- 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.\n- 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.\n- 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.\n- How would running projected gradient descent perform on (4)? How much does one gain from Riemannian optimization in practice?\n\n---\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)