A Generalized EigenGame With Extensions to Deep Multiview Representation Learning
Authors: James William Harvey Chapman
Ana Lawry Aguila
Lennie Wells
Venue: Submitted to ICLR 2023 (2023)
Keywords: Optimisation
Generalized Eigenvalue Problem
Deep CCA
CCA
PLS

Abstract: Generalized Eigenvalue Problems (GEPs) encompass a range of interesting scientific computing problems. Canonical Correlation Analysis (CCA) and Partial Least Squares (PLS) are two such examples of GEPs which are often used to learn representations of multiview data. Development of efficient stochastic approaches to these problems would allow them to scale to large datasets. Furthermore, existing deep learning based extensions of CCA require large minibatch sizes in the stochastic setting to achieve good performance. Inspired by recent formulations of Principal Components Analysis and GEPs as games with differentiable utilities, we develop an alternative game theoretic approach to solving GEPs in which all constraints are softly enforced by Lagrange multipliers. We show that our approach shares much of the theoretical grounding of the previous game theoretic approaches but has fewer hyperparameters, is faster to converge, and permits extension to general function approximators like neural networks for certain GEPs including CCA. We demonstrate the effectiveness of our method for solving GEPs using canonical multiview datasets and demonstrate state-of-the-art performance for the Deep CCA problem for multiview representation learning.

Under review as a conference paper at ICLR 2023
A GENERALIZED EIGENGAME WITH EXTENSIONS TO DEEP MULTIVIEW REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Generalized Eigenvalue Problems (GEPs) encompass range of interesting di- mensionality reduction methods. Development of efficient stochastic approaches to these problems would allow them to scale to larger datasets. Canonical Cor- relation Analysis (CCA) is one example of GEP for dimensionality reduction which has found extensive use in problems with two more views of the data. Deep learning extensions of CCA require large mini-batch sizes, and therefore large memory consumption, in the stochastic setting to achieve good performance and this has limited its application in practice. Inspired by the Generalized Heb- bian Algorithm, all constraints are softly enforced by Lagrange multipliers. Then by considering the integral of this Lagrangian function, its pseudo-utility, and inspired by recent formulations of Principal Components Analysis and GEPs as games with differen- inspired approach to solving GEPs. We
develop approach solving stochastic GEPs in which
tiable utilities, we develop show that our approaches share much of the theoretical grounding of the previous Hebbian and game theoretic approaches for the linear case but our method permits extension to general function approximators like neural networks for certain GEPs for dimensionality reduction including CCA which means our method can be used for deep multiview representation learning. We demonstrate the effectiveness of our method for solving GEPs the stochastic setting using canonical multiview datasets and demonstrate state-of-ther performance for optimizing Deep CCA.
INTRODUCTION
A Generalised Eigenvalue Problem (GEP) is defined by two symmetric matrices A, B E Rdxd They are usually characterised by the set of solutions to the equation
Aw ABw
with À E R, w E Rd, called (generalised) eigenvalue and (generalised) eigenvector respectively. Note that by taking B we recover the standard eigenvalue problem. We shall only be con- cerned with the case where B is positive definite to avoid degeneracy; in this case one can find basis of eigenvectors spanning Rd. Without loss of generality, take W1, Wy such basis of eigenvectors, with decreasing corresponding eigenvalues λ 2 ... 2 Aa. The following variational characterisation Stewart Sun (1990) provides useful alternative, iterative definition: ueg solves
max w T Aw subject to T Bw = 1, T Bwj= = 0 for j = l,...,
(2)
WERd
There also simpler (non-iterative) variational characterisation for the top-k subspace (that spanned by .wi....; Wk Wk)), namely
trace(WT AW) subject W BW It WeRaxk
again see Stewart & Sun 1990p; the drawback of this characterisation is it only recovers the subspace and not the individual eigenvectors. We shall see that these two different characterisations lead to different algorithms for the GEP.
or, generally, Hermitian Stewart & Sun (190))

---

Under review as a conference paper at ICLR 2023
Many classical dimensionality reduction methods can be viewed GEPs including but not lim- ited to Principal Components Analysis (Hotelling [933), Partial Least Squares Haenlein & Kaplan 2004), Fisher Discriminant Analysis Mika al. (1999), and Canonical Correlation Analysis (CCA)
Hotelling 1992).
Each of the problems above is defined population level, using population values of the matrices A, B. usually functionals of some appropriate covariance matrices. The practical challenge is the sample version: to estimate the population GEP where we only have estimates of A, B through some finite number of samples (zn = classically, one just solves the GEP with A, B estimated by plugging in the relevant sample covariance matrices.
However for very large datasets. the dimensionality of the associated GEPs makes it memory and compute intensive to compute solutions using existing full-batch algorithms; these are usually vari- ants of the singular value decomposition where successive eigenvalue eigenvector pairs are calcu- lated sequentially by deflation Mackey 2008) and so cannot exploit parallelism over the eigenvec- tors.
This work was motivated in particular by CCA, a classical method for learning representations of data with two or more distinct views: problem known as multiview (representation) learning. Mul- tiview learning methods are useful for learning representations of data with multiple sets of features, or "views". CCA identifies projections subspaces in at least two different views that are highly correlated and can be used to generate robust www-dimesioonll representations for downstream pre- diction task, to discover relationships between views, or to generate representations of view that is missing at test time. CCA has been widely applied across a range of fields such as Neuroimaging Krishhan et al. 2011 Finance (Cassel al., 2000), and Imaging Genetics (Hansen et al.) 2021).
Deep learning functional forms are often extremely effective for modelling extremely large datasets as they have more expressivity than linear models and scale better than kernel methods. While PCA has found natural stochastic non-linear extension in the popular autoencoder architecture (Kramer, 1991]. applications of Deep CCA (Andrew et al. 2013) have been more limited because estimation of the constraints in the problem outside the full batch setting are more challenging to optimize. In particular, DCCA performs badly when its objective is maximized using stochastic nini-batches. This is unfortunate as DCCA would appear to be well suited to a number of multiview machine learning applications as a number of successful deep multiview machine learning (Suzuki & Matsuo, 2022) and certain self-supervised learning approaches (Zbontar et al. )021) are designed around similar principals to DCCA; to maximize the consensus between non non-linear models of different NewwsNguyen
views Nguyen& & Wang (2020).
Recently, a number of algorithms have been proposed to approximate GEPs|Arors et al. (2012), and CCA specifically Bhatia et al. (2018), in the 'stochastic' or 'data-streaming' setting; these have big computational savings. Typically, the computational complexity of classical GEP algorithms is O ((N + k)d²); by exploiting parallelism (both between eigenvectors and between samples in mini mini-batch)),
reduce this down to O (dk) (Arora et al. 2016). Stochastic algorithms also introduce a form of regularisation which can be very helpful in these high high-dimensional settings.
A key motivation for us was recent line of work reformulating top-k eigenvalue problems as games (Gemp et al. 2020 202T), later extended to GEPs in Gemp et al. (022).. We shall refer to these ideas as the "Eigengame framework'. Unfortunately, their GEP extension is very complicated, with 3 different hyperparameters; this complication is needed because they constrain their estimates to lie on the unit sphere, which is natural geometry for the usual eigenvalue problem but not natural for the GEP. By replacing this unit sphere constraint with a Lagrange multiplier penalty, we obtain much simpler method (GHA-GEP) with only single hyperparameter; this a big practical im- provement because the convergence of the algorithms is mostly sensitive to step-size (learning rate) parameter Li & Jordan (202T). and it allows practitioner to explore many more learning rates for the same computational budget. We also propose second class of method (8- (5-EigeGGame) defied via optimising explicit utility functions, rather than being defined via updates, which enjoys the same practical advantages and similar performance. These utilities give unconstrained variational forms for GEPs that we have not seen elsewhere in the literature and may be of independent interest; their key practical advantage is that they only contain linear factors of A, B so we can easily obtain unbiased updates for gradients. The other key advantage of these utility-based methods is that they
2

---

Under review as a conference paper at ICLR 2023
easily be extended to deep learning solve problems motivated by GEPs. In particular propose a simple but powerful method for the Deep CCA problem.
1.1 NOTATION
We have collected here some notational conventions which we think may provide a helpful reference for the reader. We shall always have A, B E RR.. We denote (estimates to dummy variables for) the th generalised eigenvectors by ue; and denote CCA directions u, E IRP v E IR9, The number of directions we want to estimate will be k. For stochastic algorithms, denote batch-size by b. We use (, for inner products; implicitly we always take Euclidean inner product over vectors and Frobenius 'trace' inner product for matrices.
2 A CONSTRAINT-FREE ALGORITHM FOR GEPS
Our first proposed method solves the general form of the generalized eigenvalue problem in equation ② for the top-k eigenvalues and their associated eigenvectors in parallel. We are thus interested in both the top-k subspace problem and the top-k eigenvectors themselves. Our method extends the Generalized Hebbian Algorithm to GEPs, and we thus refer to it as GHA-GEP.
In the full-batch version of our algorithm, each eigenvector estimate has updates with the form
Reward
Penalty
Reward
Variance Penalty
Orthogonality Penalty
A GHA-GEP
Aw;
Bud (10] Ard;)
Aw;
Brde 1 Awd)
Bud (áū Awo)
(4)
jci
Ponalty
Reward
Aw;
BúiT
(5)
where toy is estimator to the eigenvector associated with the j"h largest eigenvalue and in the stochastic setting, we can replace A and with their unbiased estimates Á and B. We will use the notation Fú (a² Adē;) to facilitate comparison with previous work in Appendix A Piy has indeed, Chen et al.
natural interpretation as Lagrange multiplier for the constraint 1i Bw, 2019) prove that [ Aw; is the optimal value of the corresponding Lagrange multiplier for their Tormuuulltionn; we summarise this derivation in Appendix C.2 for ease of reference. We also label for
the terms as rewards and penalties to facilitate discussion with respect to the EigenGame framework in Appendix [A.3 and recent work in self- learning in Appendix E
Proposition 2.1 (Unique stationary point). Given exact parents and assuming the top-k generalized eigenvalues of A and B are distinct and positive, the only stable stationary point of the iteration defined by () eigenvector w, (up to sign).
2.1 DEFINING UTILITIES AND PSEUDO-UTILITIES LAGRANGIAN FUNCTIONS
Now observe that our proposed updates can written as the gradients Lagrangian pseudo-utility function:
CUl GEP
(w:lwjen I') T Ad; fr w
Bú,,)
Σ Er. Búü jei
(6)
We show how this result is closely related to the pseudo-utility functions in Chen et al. (2019) and suggests an alternative pscudo-utility function for the work in Gemp et al. (202) in Appendix C. which, unlike the original work, does not require stop gradient operators.
3

---

Under review as a conference paper at ICLR 2023
If we plug in the relevant w; and wy terms into r, we obtain the following utility function:
Ut wy<e)) 20, Add + 2 Aw; db Bris)
ú Au, 2 Búg;
J&
[ Ad;
[ (10 Bri)))
- Awt (w) Bid))
J
A remarkable fact is that this utility function actually defines solution the GEP problem! We prove the following consistency result in Appendix B.I
Proposition 2.2 (Unique stationary point). Assuming the top-i generalized eigenvalues of the GEP 2 are positive and distinct. Then unique maximizer of the utility 7 for exact parents is precisely the th eigenvector (up to sign).
An immediate corollary is: Corollary 2.1. The top-k generalized eigenvectors form the unique, strict Nash equilibrium of A- EigenGame
Furthermore, the penalty terms in the utility function (6 have natural interpretation as projection deflation as shown in appendix C.5
This utility function allows to formalise A A-EigeGGame, whose solution corresponds to the top-k solution of equation (2).
Definition 2.1. Let A-EigenGame be the game with players i E (1,...,) k), strategy space vy E IRd,
where d the dimensionality of A and B, and utilities Us defined in equation 7
Next note that it is easy to compute the derivative
ou, (w;; wyes))
A
(8)
Swa
2A0; (1 Bix (1)) Aw;
Σ (Aūr (w) Bú,) + (w) Adr Bry jzs
A GHA-GEP + (Awi
Σ Auy [b) Bw;)
is
This motivates an alternative algorithm for the GEP which we call O-EigenGame (where, consistent with previous work, we use upper case for the game and lower case for its associated algorithm).
2.2 STOCHASTIC/DATT-SSTRRAA
VERSIONS
This paper is motivated by cases where the algorithm only has access to unbiased sample estimates of A and These estimates, denoted Å and B, are therefore random variables. A nice property of both our proposed GHA-GEP and 8 S-me is that A and B appear as multiplications in both of their updates (as opposed to as divisors). This means that we can simply substitute them our unbiased estimates at each iteration. For the GHA-GEP algorithm this gives updates based on stochastic unbiased estimates the gradient
GHA-GEP =A
Σ J
Biū NoT Aviz)
(9)
Which we can use to form algorithm
Likewise we can form stochastic updates for 5-EigenGame
A -A. (1, Bwi)) + (1)7 Aw, - [wA Big)) + (10J Aw).)) Brn)) (10)
JZi
Which give algorithm 2
Furthermore, the simplicity of the form of the updates means that, in contrast to previous work, our updates in the stochastic setting require only one hyperparameter the learning rate.
4

---

Under review as a conference paper at ICLR 2023
Algorithm A Sample Based Generalized Hebbian Algorithm for GEP
Input: data stream Z₁ consisting of samples from zn Learning rate (n=) Number of time steps T. Number of eigenvectors to compute k.
Initialise: (wi;) ==1 with random uniform entries for /. to 7 do
Construct independent unbiased estimates Å and ß from Z
for = 1 to & do
0; < w; + 17. m GGAA-GEP (As defined in (
end for end for
Algorithm 2 A Sample Based d E-EignnGame for GEP
Input: data stream Z₁ consisting of samples from 2n. Learning rate (nt).. Number of time steps T. Number of cigenvectors to compute k.
Initialise: (ui;) j with random uniform entries for f = 1 to 7 do
Construct independent unbiased estimates À and B from Ze
for i = 1 to k do
ú < w; + 17: n (As defined in 1
end for end for
2.3 COMPLEXITY AND IMPLEMENTATION
For the GEPs we are motivated by, and in particular for CCA, À and / are low rank matrices (specifically, they have most rank b where is the mini-batch size). This means that, like previous variants of EigenGame, our algorithm has a per-iteration cost of (bdkk²) We can similarly leverage parallel computing both the eigenvectors (players) and data achieve theoretical complexity of (dd)).
particular benefit of our proposed form is that we only require one hyperparameter which makes hyperparameter tuning particularly efficient. This is particularly important as prior work has demon- strated that methods related to the stochastic power method are highly sensitive to the choice of learning rate Li & Jordan (2021). Indeed, by using decaying learning rate the user can in principle run our algorithm just once to a desired accuracy given their computational budget. This is in con- trast to recent work proposing an EigenGame solution to stochastic GEPs (Gemp et al. 2022) which requires three hyperparameters.
3 APPLICATION TO CCA AND EXTENSION TO FOR DEEP CCA
Previous EigenGame approaches have not been extended to include deep learning functions. Gemp et al. (2020) noted that the objectives of the players in a-EigenGame were all generalized inner products which should extend to general function approximators. However, it unclear how to translate the constraints in previous HigenGame approaches to the neural network setting. In con- trast, have shown that our work is constraint free but still be written completely generalized inner products for certain GEPs and, particular, dimensionality reduction methods like CCA.
3.1 CANONICAL CORRELATION ANALYSIS
Suppose we have vector-valued random variables X,Y E R², respectively. Then CCA
(Hotelling 1992) defines a sequence of pairs of 'canonical directions' (u,, v.) RP+0 by the it- erative maximisations
max Cov(u T X, subject to Cov(u X) Cov(v TV)= TY== =
(11)
Cov(u T X,u, x) Cov(u Y,oJ 0 for <
5

---

Under review as a conference paper at ICLR 2023
Now write (Xv Σxx, Cov(Y) Σyy, Cov(X,Y) = Exy. It is straightforward show Borga 1998) that CCA corresponds to a GEP with
Exv) Σyx
B = Exx 0
) W (
A =
d = d=p+ (12)
For the sample version of CCA, suppose have observations (In, Yn 3n)n which have been pre- processed to have mean zero. Then the classical CCA estimator solves the GEV above with covari- ances replaced by sample covariances Anderson (2003). To define algorithm in the stochastic case, suppose that time step define A., B, by plugging sample covariances of the mini-batch at time L.
3.2 G-EIGENGAME FOR CCA
We defined CCA by maximising correlation between linear functionals the two views of data; can extend this to DCCA by instead considering non-linear functionals defined by deep neural networks. Consider neural networks f.g which respectively map X and Y to a dimensional subspace. We will refer to the Wth dimension of these subspaces using fx( and 9& (X) where f(X) =
[x(X)] and g(X) = (X), (X).... 9a gx()]. Deep CCA finds f and which maximize Corr(fiXX), (Y)) subject to orthogonality constraints.
To motivate an algorithm, note that 7 is just a function of the inner products
( Ad, Cov(u, X, v. Y) Cov (u, u X) (w:;, Búyz) Cov(u, X, u. X) + Cov(u; Y, Y)
So replacing u/ X with fi(X) and uTY with 9: (Y(),, and using the short-hand
Å =
(13)
Bij Cov(fi(X), (ov
(14)
obtain the objective
ut We. 2Á A. - Bij
(15)
jAi
Next observe by symmetry of matrices A, B that if sum the first k utilities we obtain
k
k
k
U
rsum
U
2
ARBa
>
Ass
iml
4m
jzc
2trace(A)
Σ
Ang Bag
ilj=
trrace(A) trace AB trace (Ā(21s- B)) -B)
(16)
The key strength of this covariance based formulation is that can obtain full-batch algorithm by simply plugging in the sample covariance over the full batch; and obtain mini- batch update by plugging in sample covariances where we slightly abuse notation: we write mini-batches in matrix form X, E g short hand f(X,), ((Y) to denote applying f g each sample in the mini-batch.
the mini-batch. We define DCCA- CCCA--iggnGame in algorithm
xb Y, E Roxb and

---

Under review as a conference paper at ICLR 2023
Algorithm 3 DCCA EigenGame
Input: Stream of data with mini-batch size (X+ E RRbxp, , Y, Rbx9)), neural networks f(X),
g(Y) parameterized by 0 and vi learning rate 7
for = 1 to T do
Construct unbiased estimates A and B from f(Xi) and g(\))
u < trace A(2IIx B)
aU
af Vg 8g
au
0.+1 O. v f. 1h44 +- the + V
end for
We have motivated a loss function for SGD by a heuristic argument. We now give theoretical result justifying the choice. Recall the top-k variational characterisation of the GEP in (3) was hard to use in practice because of the constraints; GEP.
this to prove that the form above characterises the
Proposition 3.1 (Subspace characterisation). The top-k subspace for the GEP 7 can be charac- terised by
max trace (WT AW (2 ls - - BW)) WEB4xk
(17)
We prove this result in Appendix from the paper of Wang et al. 2015c in Appendix C.I
B.3
We also provide an alternative derivation of the utility of (16)
4 RELATED WORK
In particular we note the contemporaneous work in Gemp al. (2022). termed 7-EigenGame, which directly addresses the stochastic GEP setting we have described in this work using an EigenGame- inspired approach. Since their method was designed around the Rayleigh quotient form of GEPs, it takes different and more complicated form and requires additional hyperparameters in order to remove bias from the updates in the stochastic setting due to their proposed utility function contain- ing random variables in denominator terms. It also isn't clear that their updates the gradients of a utility function. Meng et al.] (202T) developed an algorithm, termed RSG+, for streaming CCA which stochastically approximates the principal components of each view in order to approximate the top-k CCA problem, in effect transforming the data so that B = to simplify the problem. Arora et (2017) developed a Matrix Stochastic Gradient method for finding the top-k CCA sub- space. However, the efficiency of this method depends on mini-batch samples of and scales poorly larger mini-bater batch sizes. While there have also been number of approaches the top-1 CCA problem (Li & Jordan 2021 Bhatia et al. 2018), the closest methods in motivation and performance to our work on the linear problem are 7 EigenGame, SGHA, and RSG+.
The original DCCA (Andrew et al. 2013) was defined by the objective
max tracenorm
E >> 1/2
1/2
(18)
and demonstrated strong performance multiview learning tasks when optimized with the full batch L-BFGS optimizer (Liu & Nocedal, 1989). However when the objective is evaluated for small mini-
batches, the whitening matrices 1/2 and //1 are likely be ill-conditioned, causing gradient
1/1/2
estimation to be biased.
Wang et al. 2015b) observed that despite the biased gradients, the original DCCA objective could still be used in the stochastic setting for large enough mini-batches, a method referred to in the literature as stochastic optimization with large mini-batches (DCCA-STOL). Wang et al.) (2015c) developed method which adaptively approximated the covariance of the embedding for each view in order to whiten the targets of a regression in each view. This mean square error type loss can then be decoupled across samples in method called non-lineat orthogonal iterations (DCCA-NOD). To the best of our knowledge this method is the current taat--ofthee-a for DCCA optimisation using stochastic mini mini-batches.
7

---

Under review as a conference paper at ICLR 2023
122 modornel bean
PCD
free POCTer oftrr sutth
Dron4an Copeeen Cefioel $700
Proveaar Cundulier Cantrall
08
014
24gge Game
SCMA
52HA
50HA
Bunoee
Bunoks
Figure I: CCA with stochastic mini-batches: proportion of correlation captured with respect to Scipy ground truth b yGHA-GEH and 8 B-EigenGame vs prior work. The maximum value is 1.
Dhe ThV--90 of Commete Carkend (P00)
Prope for Curricke Oestert
O.Egeruur GHA DEP
1Cam GEA.GEP
D GELAGEP
Thea
Figure 2: CCA with stochastic mini-batches: proportion of correlation captured with respect to Seipy ground truth by GHA-GEP and 6-EigenGame vs prior work. The maximum value is 1.
5 EXPERIMENTS
In this section replicate experiments from recent work on stochastic CCA and Deep CCA in order to demonstrate the accuracy and efficiency of our method.
5.1 STOCHASTIC SOLUTIONS TO CCA
In this section we compare GHA-GEP and 5-FigenGame to previous methods for approximating CCA in the stochastic setting. We optimize for the top-8 eigenvectors for the MediaMill, Split MNIST and Split CIFAR datasets, replicating Gemp et al. (2022); Meng et al. (2021) with double the number of components and mini-batch size 128 and comparing our method theirs. We use the
Seipy (Virtanen et al. 2020) package to solve the population GEPs as a ground truth value and use the proportion of correlation captured (PCC) captured by the learnt subspace as compared to this population ground truth (defined in Appendix F.2
Figure T shows that for all three datasets, both GHA-GEP and ö-EigenGame exhibit faster vergence on both a per-iteration basis compared to prior work and likewise in terms of runtime in figure 2 They also demonstrate comparable or higher PCC at convergence. In these experiments G-migenGame was found to outperform GHA-GEP. These results were broadly consistent across mini-batch sizes from 32 128 which we demonstrate in further experiments in Appendix G.I
The strong performance of GHA-GEP and 6-EigenGame is likely to be because their updates adap- tively weight the objective and constraints the problem and are not constrained arbitrarily the unit sphere. We further explore the shape of the utility function in Appendix C.4
5.2 STOCHASTIC SOLUTIONS TO DEEP CCA
In this section we compare DCCA- CiCA--iignGaaee and DCCA-SGHA to previous methods for opti- mizing DCCA in the stochastic setting. We replicated experiment from Wang et al. (211cc) and compare our proposed methods to DCCA-NOI and DCCA-STOL. Like previous work, we use the total correlation captured (TCC) of the learnt subspace as metric (defined in Appendix ET
8

---

Under review as a conference paper at ICLR 2023
Ocos biask
DCCA legarlure
(BOCA Plyy Flane
OCGA STOL
DCSA ShOL-10 -X
DCCA-STOLIEE
Eoedh
Epsche
DCCA
(SOCA Plgm
OCGA STOL
DC0A STOL-10 19
DCCA-STO_.CE
Eoeche
Epochs
Eooche
Figure 3: Total correlation captured by the 50 latent dimensions in the validation data. The maximum value is 50. The top row show results for mini-batch size 20 and the bottom row show results for mini-batch size 100
In all three datasets, figure 3 shows that DCCA-EigenGam finds higher correlations in the validation data than all methods except DCCA-STOL with n = 500 with typically faster convergence in early iterations compared to DCCA-NOI.
CONCLUSION
We have presented two novel algorithms for optimizing stochastic GEPs. The first, GHA-GEP was based extending the popular GHA and we showed how it could be understood as optimising a Lagrangian psuedo-utility function. The second, d-EigenGame, was developed by swapping the Lagrange multipliers to give proper utility function which allowed to define the solution of GEP with A-EigenGame. Our proposed methods have simple and elegant forms and require only one choice of hyperparameter, making them extremely practical and both demonstrated comparable or better runtime and performance as compared to prior work.
We also showed how this approach state-of-the--ar performance when using stochastic mini-batches. We believe that this will allow researchers to apply DCCA to a much wider range of problems.
also be used to optimize Deep CCA and demonstrated
In future work, we will apply d-EigenGame to other practically interesting GEPs like Generalized CCA for more than two views and Fisher Discriminant Analysis. We will also explore the extensions of other GEPs to the deep learning case in order to build principled deep representations.
REFERENCES
T. W. Anderson. An introduction multivariate statistical analysis. Wiley series in probability and statistics. Wiley-Interscieen Hoboken, N.J, 3rd ed edition, 2003. ISBN 378-0-471-3609111
Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Livescu. Deep canonical correlation analysis. In International conference on machine learning, pp. 1247-1255 PMIRR 2013.
Raman Arora, Andrew Cotter, Karen Livescu, and Nathan Srebro. Stochastic optimization for pca and pls. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 861-868. IEEE, 2012.
Raman Arora, Poorya Mianjy, and Teodor Marinov. Stochastic optimization for multiview repre- sentation learning using partial least squares. In International Conference on Machine Learning, pp. 1786-1794. PMLR, 2016.

---

Under review as a conference paper at ICLR 2023
Raman Arora, Teodor Vanislavov Marinov, Poorya Mianjy, and Nati Srebro. Stochastic approxima- tion for canonical correlation analysis. Advances in Neural Information Processing Systems, 30, 2017.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacci. Jonathan Godwin, Chris Jones, Tom Hennigan, Matteo Hessel, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King. Lena Martens, Vladimir Mikulik, Tamara Norman, John Quan, George Papa- makarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Wojeiech Stokowiec, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL
cttpeeeccc/eeeeeeee dempmine
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning re- cover global and local spectral embedding methods. arXiv preprint arXiv:2205./1500 2022.
Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Varianceiivariiacceoovvaaaae regularzztionn for self-superviss learning. arXiv preprint (eXix:2/05004000 2021.
Kush Bhatia, Aldo Pacchiano, Nicolas Flammarion, Peter L Bartlett, and Michael Jordan. Gen- oja: Simple & efficient algorithm for streaming generalized eigenvector computation. Advances in neural information processing systems, 31, 2018.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL wandb. com/ Software available from wandb.com.
Magnus Borga. Learning Multidimenssonal Signal Processing. PhD thesis, 1998. URL http: Publisher: Linköping
7/urn. kb. htt..//eeeccceeeeeuuuuu.....aee.
University Electronic Press.
Vivek S. Borkar. Stochastic approximation: a dynamical systems viewpoint / Vivek Borkar. Cam- bridge University Press Hindustan Book Agency, Cambridge: New Delhi, 2008. ISBN 978-0- 521-51592-4.
Claes M Cassel, Peter Hackl, and Anders H Westlund. On measurement of intangible assets: a study of robustness of partial least squares. Total Quality Management, 11(7):897-907, 2000.
Zhehui Chen, Xingguo Li, Lin Yang, Jarvis Haupt, and Tuo Zhao. On constrained nonconvex stochastic optimization: case study for generalized eigenvalue decomposition. The 22nd International Conference Artificial Intelligence and Staristics, pp. 916-925. PMLR, 2019.
Ian Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Eigengame unloaded: When playing games is better than optimizing, 2021.
Ian Gemp, Charlie Chen, and Brian McWilliams. The generalized eigenvalue problem as a nash equilibrium. arXiv preprint arXiv:2206 arXhv:2206.04993, 2022.
M. Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Eigengame: PCA as nash equilibrium. CoRR, abs/2010.00554, 2020. URL https::/arxxiv.or///baa. 00554
Michael Haenlein and Andreas M Kaplan. A beginner's guide to partial least squares analysis. Understanding statistics, 3(4):283-29)) 2004.
Justine Hansen, Ross Markello, Jacob Vogel, Jakob Seidlitz, Danilo Bzdok, and Bratislav Misic. Mapping gene transcription and neurocognition across human neocortex. Nature Human Be- haviour, 5:1-11, 09 2021. doi: 10. (0.1038/415522-021-
Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of educational psychology, 24(6):417, 1933.
Harold Hotelling. Relations between two sets of variates. Breakthroughs in statistics, pp. 162- 190. Springer, 1992.
10

---

Under review as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Mark A Kramer. Nonlinear principal component analysis using autoassociative neural networks. AIChE journal, 37(2)233--44 1991.
Anjali Krishnan, Lynne Williams, Anthony McIntosh, and Hervé Abdi. Partial least squares (pls) methods for neuroimaging: A tutorial and review. Neurolmage. 56:455-75, 05 2011. doi: 10.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Harold Kushner, George Yin, and Harold Kushner. Stochastic approximation and recursive algorithms and applications. Number 35 in Applications of mathematics. Springer, New York, 2003. ISBN 978-0-387-008844-3
Yann LeCun, Corinna Cortes, and Chris Burges. Mnist handwritten digit database, 2010.
Chris Junchi and Michael Jordan. Nonconvex stochastic svaled-gradiens descent and generalized eigenvector problems. arXiv preprint arXiv:21 14738, 2021.
Dong Liu and Jorge Nocedal, On the limited memory bfgs method for large scale optimization. Mathematical programming. 45(1):503-528, 1989.
Lester Mackey. Deflation methods for sparse pea. Advances in neural information processing systems, 21, 2008
Zihang Meng. Rudrasis Chakraborty, and Vikas Singh. An online riemannian pea for stochastic canonical correlation analysis. Advances in Neural Information Processing Systems, 34:14056- 14068, 2021.
Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf, and Klaus-Robert Mullers. Fisher diseriminant analysis with kernels. In Neural networks for signal processing IX: Proceed- ings of the 1999 IEEE signal processing society workshop (cat. no. 98th8468), pp. 41-48. Icce, 1999.
Nam D Nguyen and Daifeng Wang. Multiview learning for understanding functional multiomics. PLoS computational biology. 16(4):c000767,, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F, d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Terence D Sanger. Optimal unsupervised learning in single-layer linear feedforward neural net- work. Neural networks, 2(6):459-473, 1989.
Suhail M. Shah.
Stochastic Approximation on Riemannian manifolds, November 2017. URL arXiv:1711.10754 [math].
G. W. Stewart and Ji-Guang Sun. Matrix Perturbation Theory. ACADEMIC PressINC, July 1990. ISBN 978- 11811-4933--199-7.
URL httts::/bbooss.goolll.oo... htt.:///....coouoooooooo//aaaaaa
Matrix Perturbation whwozy..tmliideeeee.e wtt.:a/ww.aeeelrorro..uucuaadaa. esc=yy Google-Bood Books ID: Brooks-ID:bYYEoE...... bIYEogEACAAJ.
Masahiro Suzuki and Yutaka Matsuo. A survey of multimodal deep generative models. Advanced
Robotics, 36(5-6) 278, feb 2022. doi: 10. 09w.:0066661002222222002055 URL https: //doi. .rg. 010.11...0000F0000 864 235533232233355

---

Under review as a conference paper at ICLR 2023
Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Coumapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: funda- mental algorithms for scientific computing in python. Nature methods, 17(3):261-277 27222222222220 2020.
Weiran Wang, Raman Arora, Karen Livescu, and Jeff Bilmes. On deep multi- view representation learning. In International conference machine learning, pp. 1083-1092. PMLR, 2015a.
Weiran Wang, Raman Arora, Karen Livescu, and Jeff Bilmes. Unsupervised learning of acous- tic features via deep canonical correlation analysis. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4590-4594, IEEE, 2015b.
Weiran Wang, Raman Arora, Karen Liveseu, and Nathan Srebro. Stochastic optimization for deep cca via nonlinear orthogonal iterations. In 2015 53rd Annual Allerton Conference on Communi- cation, Control, and Computing (Allerton), pp. 688-695. IEEE, 2015c.
Svante Wold, Amold Ruhe, Herman Wold, and WJ Dunn, Iii. The collinearity problem in linear regression. the partial least squares (pls) approach to generalized inverses. SIAM Journal on Scientific and Statistical Computing, 5(3):735-773) 1984.
Jure Zhontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. arXiv preprint arXiv: 103.03230, 2021.
A COMPARISON TO PREVIOUS WORK
A.1 GENERALIZED HEBBIAN ALGORITHM
Our update closely related to the Generalized Hebbian Algorithm (GHA) ing the PCA problem with updates:
Sanger 1989) for solv-
A GHA
Au;
Σ 55$
w [0) Aw:) = Aw;;
Σ D JSP
(19)
which originally designed to be solved sequentially rather than in parallel. Note that for GEPs where = la like PCA, our proposed method collapses exactly to GHA.
A.2 STOCHASTIC GENERALIZED HEBBIAN ALGORITIIM
To understand how our method extends GHA to generalized eigenvalue problems we consider the Stochastic Generalized Hebbian Algorithm (SGHA) (Chen et al. 2019 SGHA derived from the min-max Lagrangian form of (3)
min max C(W,T) -r (WT AW) (T, WT BW Ix)
(20)
W W TERAXA
Where W is matrix that captures the top-k subspace (but not necessarily the top-k eigenvectors) and I' is Lagrange multiplier that enforces the constraint in (2) along with the B-orthogonality of each cigenvector. By solving for the KKT conditions of equation (20). we have I (W" AW) and
the authors propose to combine the primal and dual updates into a single step to give symmetrical updates for each eigenvector:
A SGHA
Au, Σ Buy (1) Aw.)) Aw, Σ Lo
(21)
Thougg the authors called this SGHA, it rather different to the original proposal, because it is subspace method rather than iterative
12

---

Under review as a conference paper at ICLR 2023
Where we highlight in red the key difference between method and SGHA: that there is hierarchy imposed on eigenvectors, so method can only recover top-k subspace; this is in contrast to proposal, all eigengame methods, and indeed the original GHA method. As noted by Dy/Gemp al. (2020), imposing a hierarchy often appears to improve the stability of the algorithm experiments and has the additional benefit of returning ordered eigenvectors.
A.3 / EIGGNNGGGA
Finally, our method is closely related j-EigenGame Gemp al. (2021) though this is only defined for the B = Is case. Their method restricts estimates to lie the unit sphere, using Riemannian optimization tools to update in directions defined by
A = Atú;
Σ B0 (wj Aw;) jCi
Aw;
Σ T J
(22)
where we again highlight in red the difference compared to our proposal: j=-FigenGame however does not have the term its penalty (and therefore does not use the I" Lagrange multipliers associated with the unit variance constraint v. W; 1).
B PROOFS AND FURTHER THEORETICAL ANALYSIS
B.1 Á-EIGENGAME THEORY
We recall proposition 2.2
Proposition 2.2 (Unique stationary point). Assuming the top-i generalized eigenvalues of the GEP 2 positive and distinct. Then the unique maximizer of the utility in for exact parents is precisely the 8th eigenvector (up to sign).
Proof. For case of reading the proofs this appendix, we slightly change notation, and index the normalised solutions the GEV with superscripts:
(, Bw 1, (w Aw (2) Vi,
while we continue to index our estimates with subseripts. We can write our estimates in this basis to define the coefficients w; = Ep " (P) Next define
(1
m,
(1)))22
(2(
(x
mi
so that the vector = =(x()) (2 takes values in the simplex. Then have:
(i,, Awo 20)
(10 Bwl = v
(10, Aw,, = Σ (P) (v.
(10, Bwi)) = Σ (1(o) m,
13

---

Under review as a conference paper at ICLR 2023
Consider the utility function for player i: u(((),13<<s) = 2(1,, Aw;) (rē,, Bús) Add)) -
-2Σ (wis Brū Aws)
A())
=2 2 Σ 100) (v, (2200))2 -2 E 10) 10) (1²)² -E (0 )2) Σ (2))))))
jzi
= 2 Σ
- C A (v/ (0) ) 15 [v(()))3)
J21
= (2m; - m
Σ
(1) ( m 21)
321
Which is maximized when my = 1 2/ = -ōgg which implies that of = +1 and of = 0 for
j * i.
Note that in the previous lemma, the utility function took simple form when we chose the true generalised eigenvectors as a basis; indeed, when using coefficients with respect to the basis, the utility only depended on the generalised eigenvalues and not the basis itself. This simple form shows how our utility interacts naturally with the geometry of the GEV problem. We will now analyse the corresponding simple form of the update steps.
B.2 GHA-GEP THEORY
We recall proposition 2.1
Proposition 2.1 (Unique stationary point), Given exact parents and assuming the top-k generalized eigenvalues of A and B are distinct and positive, the only stable stationary point of the iteration defined by (5) eigenvector we (up to sign).
Proof. Let ()) v,)), uu be defined in the proof of proposition 2.2
Then the update
A Aw; Búd; (w: Awas
Σ Bú, (10] Au;:)
An; Σ Buj (10] Ares))
351
(os Buolo) )
Σ (1) wipi (P)
Σ
Σ
351
Σ Bull) (x(e) v,0)
Σ (p)
Σ
351
If we define the diagonal matrix A = diag( (11(0)))))) and the vector v; = (v )== rewrite:
())d
then we can
Σ X000y ufa)) -TTAU.. Aug.
Now by orthonormality of the wp(P), we can equate coefficients and combine vector form obtain the update step for the coefficient vectors, which we shall notate by
A = Av -
V3 (V, AvA)
1
Av
i5s
1 Σ Uzu
No. Au--vily Avs)
(23)
14

---

Under review as a conference paper at ICLR 2023
Only now do consider the assumption of exact parents. This corresponds to the coefficient vectors V/ = =jvj < where ej is the jth unit vector ((e,)x = 65x). Then
< JZL
Uju} "uju - ( ( ((-1)x((1-1) (1-11x((--1) ( (((--11))((-1)) ((-++))((--)))
So if we write A, v Avd the update equations for our coefficients become:
A(v) - for porp<i
(24)
A(v).)) (26T) { forp
(25)
So if we observe the qualitative behaviour:
For p < i the coefficients are shrunk towards zero (for sufficiently small step sizes)
For 2 the coefficients grow/decay depending on their generalised eigenvalue. The larger the eigenvalue, the more the components grow / the less they shrink. over time only the ith component will be selected.
The overall magnitude of the solution shrinks faster when X; is large.
stationary point of the iteration therefore requires U, for p < Then for each p 2 i we must have either λ; = (P) or u!!)) O. Furthermore, 1/ grows at faster rate than any of the other components, so provided this was zonozero at initialisation, it will be extracted uniquely. Finally, (p) = 044 * i but v * 0 then we must have ( = X; and also X; = (x so combining with we get 14 =1, as required.
B.2.1 DISCUSSION OF CONTINUOUS DYNAMICS
In particular note that the continuous time case above with exact parents, we can write the solu- tions to 4 (1) A(v); with A (V), as in 25) as
v |p] (1) 1 (0) exp
(122g)0011 -f X((s)ds)
So when 2i (1) + (hopefully this is almost sure), the trajectories on the simplex satisfy
(0) (1) (0)
exp (2(1 - x()1) - 0 as +
and we do indeed select the correct coefficient vector at an exponential rate. Note that in particular this equation for trajectory on the simplex is decoupled from the trajectory of the norm of the coefficients.
Of course, are really interested in the case of in-exact parents. We can provide heuristic argument similar to one of Gemp et al. (202I). Note that the updates for w; only depend on it's parents Üi<á, and one show that Olc) error in the parents propagates an O(c) direction in the child gradient. We know wi will converge very fast to an arbitrary accuracy; then the gradient for w2 will be very close that corresponding exact parents, will quickly converge to that similar order of accuracy; then the gradient of wa will be close to that for exact parents and so on.
B.2.2 EXTENDING TO STOCHASTIC CASE
The real case of interest the discrete time case with mini-batches. Gemp et al. (2021) claim that their algorithm converges almost surely provided the step-size sequence 7) satisfies
x0,
< 0c
(26)
15

---

Under review as a conference paper at ICLR 2023
Their key tool is a result on Stochastic Approximation (SA) Riemannian manifolds Shah (2017)
This result extends the now-classical ODE method for analysis of SA schemes to Riemannian man- ifolds, mostly drawing on the presentation of Borkar (2008). One key difficulty of applying the literature on SA schemes is obtaining stability bounds (saying that the estimates never get too big); this becomes trivial when considering updates on compact manifolds like the unit sphere, which is why [eemp et al. (2021) are able to apply their SA tool 'out-of-the-box" In our case, because we do not restrict to the unit sphere, we are able apply more classical results on SA, for example Kushner et al. (2003), however, we would need to prove the corresponding stability estimates. These should hold intuitively because the variance penalty term should keep estimates small, but they are technically difficult. We note that obtaining such stability estimates has attracted lot of theoretical attention, but in practice they are often unnecessary because only a bounded subset of the parameter space is physically sensible. This applies to our GEP: it only makes sense to consider vectors w with w" Bw I 1; and though B is unknown in general, we may well be able to lower bound its eigenval- ues, giving bounded parameter space of interest. We could modify our algorithm to project onto this bounded subset of parameter space. The theory of Kushner et al.] (2003) can be applied to such of projected SA; indeed this theory has the added advantage of requiring weaker conditions on the step-sizes, namely only that
Σ
+ 0
Note such step-size schedules with slower decay sometimes observed give better empirical results in other SA problems Kushner et al. (2003).
We now point out what we understand to be a technical oversight in the proof of almost sure con- vergence in Gemp et al. (202I). They proof that wy converges a.s. to true value given fixed exact parents wyct appears valid; as does the conclusion that w; converges a.s. mum given fixed inexact parents; and also does their statement that if parents are close to correct then the corresponding optimum is close to correct. However, this does not say anything about convergence of w; when the parents are inexact and varying; in particular the arguments of [Shah] (017)) do not apply in this case. We believe that it would be possible to fix this oversight by con- sidering suitable coupling of solution paths starting from an e-covering of a neighbourhood of the true solution. Alternatively. it may be possible to apply the result of Shah (2017) to the combined estimates (w1...., w Similar analysis will be needed for GEP-GHA because we also propose parallel updates for computational speed.
corresponding opti-
We next note that this SA literature also applies to d-eigengame algorithm, whose updates unbiased estimates to the gradient of the utilities 24 In this case, analysis may be more straightfor- ward because we can also apply other existing literature on stochastic gradient descent.
We have not yet had time to make the discussion above more rigorous; we plan to do so in fu- ture work. Our algorithms fit very naturally into the well-studied SA framework, and we expect this literature to contain useful intuition and suggestions for implementation, as well as theoretical guarantees.
B.3 SUBSPACE CHARACTERISATION
We recall proposition
Proposition 3.1 (Subspace characterisation). The top-k subspace for the GEP 7 can be charac-
terised by
trace (WT AW (2 T (WB))
(17)
4x
Proof. Let the objective function be h(W). Firstly note that because is assumed positive definite, h becomes negative for sufficiently large values of W, in particularly outside some compact set C. Second, note that for small W, is positive. Therefore any maximizer must be in C., Next note that h is a composition of the trace linear map) with matrix polynomial is differentiable, and in particular continuous; so the maximum on C' is attained. Further, at any maximizer W, the derivative h (W) is zero. We now compute it:
H' N'(W) 2AW (WT BW 2T) 2BW BBW AW)
16

---

Under review as a conference paper at ICLR 2023
Setting to zero, left multiplying by W and using the previous notation À W P'TAW, W BW gives
BA+ AB 2A
and so 1)A+ - S symmetric). But then right multiplying by A-1 gives
0
(B I)A is skew-symmetric (using that A, B are both
symmetric
skow-symmetric
B
SA
So in fact we must have both sides equal to zero and therefore B = 1. But then by the arguments at the start of the proof, we see that any maximizer of must in fact have W BW 1; so 17 is indeed equivalent to (3) and any maximizer recovers the top-k subspace.
We now indulge in some vague intuition: a key strength of this unconstrained formulation is that it is straightforward to transform with respect to arbitrary changes of basis; therefore one can do analysis in the basis of generalised eigenvectors. By contrast, the orthogonality constraint in (3) only permits orthogonal changes of basis. This may give intuition why p-eigengame only works in the B case but our approach is effective for general GEPs.
C FURTHER CONNECTIONS TO PREVIOUS WORK
C.I RELATIONSHIP TO PREVIOUS DCCA FORMULATIONS
In Wang et al. (213c),, DCCA formalised as
traco(U FGTV) (FTT
subject to U
max f.g.UER VER
where F= (f(z))...., of the training data under functions f. defined by neural networks in some class of functions F, with input and output dimensions (p, dz), (g. dy) respectively. Observe that this optimisation is really targeting the population problem
G
are matrices whose columns are images
max UEF. VERdyy trace Σ 1 subject to U UEE = V 99
Ix
Where E, = Var(f(X)) Σg write (x)),,,, (YY) to correspond the sum of the first i canonical correlations of the pair of random variables f()),(() It is well known that if we fix f, g in the above then the optimisation problem defines the top-k subspace for CCA. So we can write the optimisation as
(X(f(X),g())) Egg Var(g(Y)) We now abuse notation
max R& (x(((X),(X))) SEF.9eg
But then using proposition 3.1 this optimisation also equivalent to
max JET GEF.gEG,WERR dg)xk
trace (WT ATTAs9 (2 W B)g
(27)
where we define
Eig )0)
Big = (201
Eff
0
Asa
Eggf
Egg
d = d=p+q.
We have now almost recovered the form of (T6), the only difference that there an optimisation over W in the above. To finish the derivation we follow Wwng et al. (2015c) and define the augmented function classes:
f -U FUU.URE
- g: Rdxxb
For any W Rddo+ there exist unique Rd. V RRd with W = (UT, VT). Also
for f = UT f.g = VT g follows from definition of covariance that
U UTEUU== =Eif. U
UESUU
VTgge Eng
17

---

Under review as a conference paper at ICLR 2023
indeed write 27
max trace gE
(Aig (2 - B1s))
(28)
which precisely matches our objective in (16).
We now comment on this analysis: the definition from Wang et al. (2015c) proposes DCCA to find a pair of -wwddimnsioonl feature maps under which the two sets of data highly correlated. Intuitively, this analysis says that if we take sufficiently expressive class of neural networks, we only need to consider i dimensional latent space recover the top-k subspace of 'deep canonical directions'. Note also that one only needs to apply a k-dimensional classical CCA to recover the top-k directions from this subspace. Finally, we warn that in general these directions may be highly non-unique, and that many of the nice properties of CCA are dependent on the structure of Euclidean space and do not hold for DCCA.
C.2 DERIVATION SGHA ALGORITHM FROM CHEN AL..
(019
The Lagrangian function in Chen et al. 2019) corresponding to is given as:
C(W, (WTAW) AW) (I, W
TTWW BW - 1)
(29)
Differentiating with respect to W gives
2AW 2BWT =
Left multiplying by W and using the constraint W BW = J shows that at any stationary point have
:= W AW
(30)
They then plug this value of into a gradient descent step for W to obtain an update direction:
SGHA (W) - AW BW SWWWT (WT AW)
(where we follow their exposition and drop the factor at this point). Note that this technique of plugging in the optimal dual variable is non-standard to our knowledge. The algorithm needs their theoretical results for more concrete justification.
C.3 PSEUDO-UTHI UTILITIES IN PREVIOUS WORK
Recall defined the pseudo-utility of GHA-GEP be
Pu.
(w, (allWjes I) = w6 Ad, + Ta([11111. wi Búx)) -2 - [
B
(31)
is closely related to expressions in previous work. Consider first SGHA. The Lagrangian function Chen al. (2019) is given above in (29).
Considering single 'player' this utility can be written:
SUAGHA (w;, D)) uo Adē + Ia w. Bid.)
rig Bú,
(32)
We can also write the updates y-EigenGame Gemp et al. (202T) as Lagrangian pseudo-utility. Note that this is slightly different expression to that given by the authors.
PU: (w::(w/luue (WilWieh 1") w. Au;
Σ jzt
I Ti
(33)
18

---

Under review as a conference paper at ICLR 2023
C.4 UTILITY SHAPE
Lemma C.1. Let de; ma(oss (0s) w; sin (0t) A.) where úi Bú; m, then:
Ui (w;, wjes) = U4 (man,, Wyes) (in)( (mar,, wyer)) - Ui (mAs; Wjes))
(34)
We will show that this result follows from similar logic to Gemp al. (0200) once the scaling factor m is accounted for.
Proof. Let Ei prw,, ||p|| 1. Decomposing the utility function for player we have:
Ue (ws, wjes) = 2(10;, Aw;) - ( Bwi)) (vit, Arr) 2 Σ (wis, Buol)) (10 Aws)
(35)
= (2m - (cos (0.) + sin" (A, ^A;))
2m
Σ
(cos (0:) wi + sin (0.) A., Awj) (cos (0;) w; sin (0:) A., Bloz)
(36)
jei
(2m - m² (cos" (0.) + sin (0:) (A;))
2m
Σ j<{
sin (0.) (A;, Awey) (A,, Bwo)
(37)
(2m 1omm-m?)xp )
(2m m²) sin 2 (0:) + sin ( AD,)
2m E (Ai, Awt; (Ai, Bwx)
(38)
(2m - m )
sin (0.) (0.) - m ) + +2m m m ADd) 2n
Σ (A,, Aw,) (Ai, Bw;))
jzi
(39)
u, (mw,, wy<s) sin)(0,)((4, (mwy, Wg<s) -24, (m1 wy<1))
(40)
C.5 UTILITY AS PROJECTION DEFLATION
projection deflation
u. 20,
[
Búi |A - + Búxw Add (41)
Analogously to the previous work a-EigenGame (Gemp et al. 2020), the matrix [ Ejs: Bui has natural interpretation projection deflation.
19

---

Under review as a conference paper at ICLR 2023
D VECTORIZED Ó- G-EIGENGAME
Algorithm 4 Vectorized 8- B-EigenGame
Input: data stream Z4 consisting of b samples from Σn. learning for / to 7 do
Construct independent unbiased estimates Å and B from Ze
Rewards 2AW
Penalties f- BW triu(W/TAA (AW)
V < Rewards Penalties
W' f W + 1/
end for
Where triu returns a matrix with the entries below the main diagonal set to zero.
CONNECTION TO SELF-SUPERVISED LEARNING METHODS
Reorganizing update equation 5p, find that the intuition of method also be understood as three terms encouraging variance in A, penalizing variance in B, and discouraging covariance.
Variance Pemally
Orthogonality Pemally
Aw;
Brog (11g Auts))
Buig (1² Add))
(42)
The motivation similar to that in recent work in self-supervised learning (Zbontar et al.) 2021) and in particular the VICReg method in Bardes et al. (2021). Recent work has shown links between several self-super learning approaches and classical spectral embedding methods (Balestriero) & LeCun 2022), some of which could be represented by GEPs. Like CCA, many self-supervised learning approaches are based on finding a function which is invariant to an image and its augmented version the learnt representations of both are correlated.
F EXPERIMENT DETAILS
F.1 TOTAL CORRELATION CAPTURED (TCC)
This is the sum of the canonical correlations of the learnt representation (i.e. the sum of the top-k canonical correlations of X and Y).
F.2 PROPORTION CORRELATION CAPTURED (PCC)
This is the sum of the canonical correlations of the learnt representation as proportion of the sum of the canonical correlations of the learnt representation using the population ground truth (i.e. the sum of the top-k canonical correlations of X and Y).
F.3 STOCHASTIC CCA
The latter two datasets are formed from left and right halves of the canonical datasets (LeCun al., 2010 Krizhevsky et al. 2009). With the same initialization for all methods, we trained for 10 epochs on each dataset with a mini-bat bani-batch size 128 and illustrate the models with the best performance in the validation set.
F.4 STOCHASTIC CCA HYPERPARAMETERS
Learning rate was tuned from = (10-1, 10- 10
10 10040044000 10 10-5) and T E-geenGame parameter ?
tuned from the range. We used Jax (Babuschkin et al. 2020) optimize the linear CCA
20

---

Under review as a conference paper at ICLR 2023
models using the Jaxline framework. We used WandB (Biewald 2020) for experiment tracking to develop insights for this paper.
F.5 DEEP CCA
We use two variants of paired MNIST datasets. The first identical to the split MNIST dataset in the previous section. The second harder problem is closely related to experiment by Waang ctt al. (2015a). Their 'noisy' paired MNIST data takes two different digits with the same class. The first rotated randomly while the second has additive gaussian noise. Finally, Microbeam (XRMB) dataset from Arroa et al.] (2016). For all of the datasets, we use two encoders with 50 latent dimensions and two hidden layers with size 800 and leaky ReLu activation functions, a similar architecture to that used in Wang et al. (2015c). We compare our proposed method to DCCA-NOI at mini-batch sizes of 20 and 100 and DCCA-STOL with mini-batch size 100 and 500 (DCCA-STOL cannot be used for mini- sizes less than the number of latent dimensions).
the X-Ray
F.6 DCCA HYPERPARAMETERS
We trained for 30 epochs on each dataset with mini-batch sizes of 20 and 100. Learning rate was tuned from 17 (10 1010- 10100- 10_00,,10 10-5) and the DCCA-NOI parameter p was tuned be- tween 0 and 1. We use PyTorch (Paszke et al. 2011)) with the Adam optimizer (Kingma & Ba 2014..
G ADDITIONAL EXPERIMENTS
G.1 STOCHASTIC CCA WITH SMALLER MINI-BATCH SIZES
In this section repeat the experiments described in the main text with smaller mini-batch sizes (64 and 32).
Results for mini-batch sizes 32 and 64 are broadly similar to those in the main text for mini-batch size 128. In the MNIST data we can see again that there is a tradeoff between speed of convergence in early iterations and the quality of the solution.
Tran for readend baichrste
Tran PPC remiet buichssze
"Tee PCC bie
Phopar 21 Covertee Caplard p702
04
64
D16-222 12
CHA.EEP
016-223
CogeCCaee
y'leer Gure
p-ge
30H0
Sumplia
Qumplec
Tean Por resdanal banchobs
Tralo POO Far bithaoe
PCC
Comerce Capaane: 1001
60
model Co
Commens
mocel
5/10
100
2000
4000
1000
1000
1000
3 X0000 20000 3000 4000 0030 WOOD
12000
20000
20000
6000
Figure 4: CCA with stochastic mini-batches of size 64 (top) and 32 (bottom): proportion of corre- lation captured with respect to Scipy ground truth by 8-EigenGame vs prior work. The maximum value is 1.
21

---

Under review as a conference paper at ICLR 2023
G.2 PARTIAL LEAST SQUARES
The Partial Least Squares (PL.S) Wold et al. (1984) problem can also be formulated as similar GEP but with B replaced by the identity matrix. PLS equivalent to finding the singular value decomposition (SVD) of the covariance matrix X Y. It has an interpretation regularised CCA where the covariance matrices Σxx and Σyy are replaced by identity matrices; this corresponds assuming collinearity between variables.
(infinitely) ridge
G.2.1 PLS WITH STOCHASTIC MINI-BATCHES
In this experiment compare method the Stochastic Power method Arora al. (2116) y-EigenGame, and SGHA for the stochastic PLS problem.
For these experiments use the Proportion of Variance captured (PV). This is the of the singular values of the learnt representation using each stochastic optimisation method as proportion of the of the singular values of the learnt representation using the population ground truth (i.e. the sum of the top-k singular values of the covariance matrix X Y).
Figure shows that all of the methods perform similarly in terms of variance captured across the datasets. While the stochastic power method is very fast to converge in the MNIST and CIFAR data, it solutions can be suboptimal. The performance of 8- B-EigenGame is arguably more suprising for the PLS problem because both the Stochastic Power method and 7-EigenGame explicitly enforce the constraints each iteration whereas 5-megenGame only enforces the constraint via penalty terms.
Tpgo
[Jean Prsporie
Progeraen of Vonarno Eeeeerekkaee Explaned
5-byr vorme
model
wittgor flew
recei Fupe Sigeecuraa
robi
SCEA
Sa10
Stnode
Figure 5: PLS with stochastic mini-batches: proportion of variance captured with respect to Scipy ground truth by ô-EigenGame prior work. The maximum value is 1.
22

---

Under review as a conference paper at ICLR 2023
Tip
mode
60/A
1000
0030 0000
00000
8000
Camplex
Sanslen
Samples
[ym Phope ooo thitaree PPo
Papooioo "eeancc (r)) rend with barth 12
Props fon Venaroo bo char tethh
Phososor Wetrre oe Eqaatee
Eiass Sochestc Pover
Prppodie Narorio
54
redi Eigendaas prgeedem
C4
Prozartor
2004
20-4
Semples
Sanade
Sumples
Figure 6: PLS with stochastic mini-batches of size 64 (top) and 32 (bottom): proportion of variance captured with respect to Scipy ground truth by 5-EigenGame vs prior work. The maximum value is
23


Reviews:
[{"review_id": "97Wd6baCtF-", "reviewer": "Reviewer_nriX", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper proposes new algorithms for CCA and Partial Least Squares problems based on game-theoretic formulations, following previous work by Gemp et al. The proposed algorithm relaxes some constraints and works well empirically.", "summary_of_the_review": "The paper is not ready for publication in its current state. I encourage the authors to state the motivations more clearly and improve the presentation of the proposed method.", "strength_and_weaknesses": "While the proposed algorithm seems to be promising empirically, its description and motivations are unclear and under-developed in the manuscript.\n\nThe key elements that are presented to motivate the algorithm are its lack of hard constraints, which are supposedly \"softly\" enforced by Lagrange multipliers, and reduced number of hyperparameters. Yet, in the presentation of the algorithm, I see no description of Lagrange multipliers, or soft-enforcement of constraints, and at least for the full-batch version, Algorithm 1 in [Gemp et al](https://arxiv.org/abs/2206.04993) seems to have only the step-size as a hyper-parameter, just like the present paper, and the projection on the sphere doesn't seem like a big issue in practice.\n\nOverall, I encourage the authors to provide a clearer and more formal description of the proposed algorithm, and its motivation (ideally in a way that doesn't involve stop-gradients as currently done in eq.(12)), and a precise comparison to previous work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "73u0bGFU3l", "reviewer": "Reviewer_sgfU", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper presents a top-k eigenvalue solver for stochastic eigenvalue problems. The proposed approach undertakes an optimization viewpoint using Lagrange multipliers. The effectiveness of the proposed scheme is validated through numerical experiments on simulated datasets.", "summary_of_the_review": "My main concerns are: a) novelty, and  b) advantage over existing methods since no running-times are presented.", "strength_and_weaknesses": "\nStrengths:\n-) The discussion of related work is sufficient. \n-) Numerical experiments confirm that the method is competitive from a qualitative perspective.\n-) The proposed scheme appears to be well-fit for parallel computing, although this direction is not explored in the paper.\n\nWeaknesses:\n-) The paper is poorly written and some concepts, like the ones presented in Section 2 before Section 2.1 are not explained well (also, Eq. (13) is empty). Eqs (16), (17) etc. are poorly motivated, and it is not clear how they appear.\n-) The novelty of the algorithm seems to lack. On several occasions, the paper feels to step on the work by Gemp et al. and the authors try hard to overstate the potential differences; to the point that it disrupts the natural flow of the submission. \n-) Unless I missed it, there are no running time comparisons between different schemes. Note that faster convergence does not translate to a better algorithm if there are no running time advantages (or maximum qualitative accuracy captrured).\n\nMinor comments:\n-) The \\hat operators below Eq. (15) are misaligned.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0NfXao9xOt", "reviewer": "Reviewer_CZPK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the application of EigenGame formulation to solve the Generalized Eigenvalue Problem (GEPs). The previous work had defined the implementation $\\alpha$ and $\\mu$ - EigenGame, while this one defines the $\\delta$- EigenGame version. EigenGame is a reduction of the problem to compute eigenvalues to the problem of computing a Nash equilibrium in a ''quasi''-collaborative/potential game.\nIn the previous line of work, in order to compute this strict-pure Nash equilibrium, a Riemannian Gradient Descent is employed, (as an analogue of Best-Response in a potential game). This work describes an alternative description of the game, which implicitly incorporates the constrained optimization via Lagrange multipliers.", "summary_of_the_review": "Currently, I feel that the work is below the threshold. However, at the first glance, it is clear that the paper provides an interesting implementation details about simplifying difficulties of previous versions of EigenGames. However, as standalone work, it seems a bit incremental  improvement. In the case that authors would not like to focus on the theoretical aspect of the optimization (which is fare), it is necessary to explain the importance of the applications and the burdens that are overpassed thanks to this EigenGame version.", "strength_and_weaknesses": "This question falls within a general research thread that has recently attracted considerable attention in the literature. To start with a positive point about the current submission, the current authors proved that, indeed, the unique equilibrium of the new game is again the solution of the Gen. EigenProblem. In other words, they proved that the reduction is meaningful . I will return to this general positioning later. The main contribution of the paper is to explain that experimentally a Lagrangian Multipliers usage in the optimization process can accelerate the Game Dynamics Process.\n\nAn objection that I raise collectively with the ''EigenGame'' reductions for all versions, is the inclusion of the stop-differentiate operator, introduced by Gemp et al from the alpha-version. Under this way, we lose completely the ''game-theoretic'' intuition. Actually, it would be interesting to understand even if the utility function is smooth/continuous. An important weakness of this series of work is the finite sample complexity. See the discussion of the discussion at the initial work of \\alpha-EigenGame.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject