The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium
Authors: Ian Gemp
Charlie Chen
Brian McWilliams
Venue: ICLR 2023 notable top 25% (2023)
Keywords: generalized eigenvalue problem
nash
riemannian optimization
canonical correlation analysis
independent component analysis
distributed computing

Abstract: The symmetric generalized eigenvalue problem (SGEP) is a fundamental concept in numerical linear algebra. It captures the solution of many classical machine learning problems such as canonical correlation analysis, independent components analysis, partial least squares, linear discriminant analysis, principal components and others. Despite this, most general solvers are prohibitively expensive when dealing with *streaming data sets* (i.e., minibatches) and research has instead concentrated on finding efficient solutions to specific problem instances. In this work, we develop a game-theoretic formulation of the top-$k$ SGEP whose Nash equilibrium is the set of generalized eigenvectors. We also present a parallelizable algorithm with guaranteed asymptotic convergence to the Nash. Current state-of-the-art methods require $\mathcal{O}(d^2k)$ runtime complexity per iteration which is prohibitively expensive when the number of dimensions ($d$) is large. We show how to modify this parallel approach to achieve $\mathcal{O}(dk)$ runtime complexity. Empirically we demonstrate that this resulting algorithm is able to solve a variety of SGEP problem instances including a large-scale analysis of neural network activations.

Published as a conference paper at ICLR 2023
THE SYMMETRIC GENERALIZED EIGENVALUE PROBLEM AS A NASH EQUILIBRIUM
Ian Gemp'
Charlie Chen
Brian McWilliams
DeepMind London, UK
DeepMind
Google Research
London, UK
Zürich, Switzerland
imgemp@deepmindd com
ccharlie@deeppinngg com
bmcw@google.com com
ABSTRACT
The symmetric generalized eigenvalue problem (SGEP) is fundamental concept in numerical linear algebra. It captures the solution of many classical machine learning problems such canonical correlation analysis, independent compo- nents analysis, partial least squares, linear discriminant analysis, principal com- ponents and others. Despite this, most general solvers are prohibitively expensive when dealing with streaming data sets (i.e., minibatches) and research has instead concentrated finding efficient solutions specific problem instances. In this work, we develop a game-theoretic formulation of the top-k SGEP whose Nash equilibrium is the set of generalized eigenvectors. We also present a parallelizable algorithm with guaranteed asymptotic convergence to the Nash. Current state-of- the-art methods require k)) runtime complexity per iteration which is pro- hibitively expensive when the number of dimensions (d) is large. We show how to modify this parallel approach to achieve (dd) runtime complexity. Empirically we demonstrate that this resulting algorithm is able to solve variety of SGEP problem instances including a large- scale analysis neural network activations.
INTRODUCTION
This work considers the symmetric generalized eigenvalue problem (SGEP),
Au ABv
(1)
where A is symmetric and B is symmetric, positive definite. While the SGEP not common sight in modern machine learning literature, remarkably, it underlies several fundamental problems. Most obviously, when A = X X, B T, and X is data matrix, recover the ubiquitous SVD/PCA. However, by considering other forms of A and B we recover other well known problems. In general, assume A and B consist of sums or expectations over outerproducts (e.g.. X or EEry ']) to enable efficient matrix-vedd products. These include, but are not limited to:
Canonical Correlation Analysis (CCA): Given a dataset of paired observations (or views) E Rd and E dy (e.g., gene expressions and medical imaging y corresponding to the same patient), CCA returns the linear projections of æ and y that are maximally correlated. CCA is particularly useful for learning multi-modal representations of data and in semi-supervised learn- ing (MeWilliams et al., 2013); it is effectively the multi-view generalization of PCA (Guo & Wul 2019) where A and B contain the cross- and auto-covariances of the two views respectively:
0
E E[zy"]
B[rx
4
B
(2)
E 1yx
0
0
Jyy
Asterisk denotes equal contribution. Work done while DeepMind.

---

Published as a conference paper at ICLR 2023
Independent Component Analysis (ICA): ICA seeks the directions in the data which are most structured, or alternatively, appear least Gaussian (Hyvärinen Oja 2000). A common SGEP formulation of ICA uncovers latent variables which maximize the non- non-Gaussianity of the data as defined by its excess kurtosis. ICA has famously been proposed as a solution to the so-called cocktail party nource-spparation problem in audio processing and has been used for denoising and more generally, the discovery of explanatory latent factors in data. Here A and B are the excess kurtosis and the covariance of the data respectively (Parra & Sajda 2003
A = E (1 x)xx tr( 2B2
B= B-Erx'
The graph Laplacian matrix (L) central to tasks such spec- L. = I) where its eigenvectors are known to solve a relaxation of min- cut Von Luxburg 2007p. Alternatives, such the random walk normalized Laplacian (A L,
Normalized Graph Laplacians:
tral clustering (A
B is the diagonal node-degree matrix), approximate other min-cut objectives. These normalized variants, in particular, are important to computing representations for learning value functions in reinforcement learning such as successor features (Machado et al. 2017a Stachenteld et al.) 2014]
Machado et al. 2017b), an extension proto-value functions (Mahadevan 2005) which uses the un-normalized graph Laplacian (A L, B l). 1).
Partial least squares (PLS) can be formualted similarly to CCA and finds extensive use chemo- metrics (Buchher et al. 2013), medical domains (Altmann al. 2021) and beyond (MeWilliams & Montana 2010). Likewise, linear discriminant analysis (LDA) can be formulated as a SGEP and learns label-aware projection of the data that separates classes well (Rao 1948). More examples and uses of the SGEP can be found in (Bie et al., 2005 Borga et al.) 1997). We now shift focus to the mathematical properties and challenges of the corresponding SGEP.
In this work, we assume the matrices A and B above can either be defined using expectations under data distribution (e.g., Ex=p(=)) [xx )) or means over finite sample dataset (e.g., X " where X IRxxd=). In either case, we typically assume the data has mean zero unless specified otherwise.
Note that the SGEP, Ar = XBu, is similar to the eigenvalue problem B-1 Av = Ae. There are two reasons for working with the SGEP instead: 1) inverting B is prohibitively expensive for large matrix and 2) while A and B > 0 are symmetric, B is not, which hides useful information about the eigenvalues and eigenvectors (they are necessarily real and B-orthogonal). This also highlights that the SGEP is a fundamentally more challenging problem than SVD and why direct application of previous game-theoree theoretic approaches such as (Gemp et al. 2021 2022 is not possible.
The complexity of solving the SGEP is O(d") where d is the dimension of the square matrix A
(equiv. B). Several libraries exist for solving the SGEP in-memory (Tzounas et al. (020)_ There is
also numerics literature cannot do justice that considers large matrices (Sorensen, 2002
We specifically focus on the stochastic, streaming data setting which is of particular interest to machine learning methods which learn by iterating over small minibatches of data (e.g., stochastic gradient descent). Under this setting, machine learning research has developed simple approximan solvers for singular value decomposition (SVD) that scale very large datasets (Allen-Zhu Li] 20176.. Similarly, in this work, we contribute a simple, elegant solution to the SGEP, including
A game whose Nash equilibrium is the top-k SGEP solution,
An easily parallelizable algorithm with Odd)) per-iteration complexity relying only on matrix-vector products,
An empirical analysis of neural similarity on activations 1000 larger than prior work.
The game and accompanying algorithm developed synergistically achieve formulation that amenable to analysis and naturally leads to an elegant and efficient algorithm.
GENERALIZED EIGENGAME: PLAYERS, STRATEGIES, AND UTILITIES
In this work, we take the approach of defining the top-k SGEP as a k-player game. It is an open question how define k-player game appropriately such that key properties of the SGEP are
2

---

Published as a conference paper at ICLR 2023
captured] D As argued in previous work (Gemp et al. 2021 2022). game formulations make obvious how computation can be distributed over players, leading to high parallelization, which is critical for processing large datasets. They have also clarified geometrical properties of the problem.
Specifically, we are interested in solving the top-k SGEP which means we are interested in finding the (unit-norm) generalized eigenvectors oy associated with the top-k largest generalized eigenval- ues A; Therefore, let there be l players denoted E {1,..., k), and let each select a vector 0; (strategy) from the unit-sphere S (strategy space). We define player i's utility function condi- tioned on its parents (players j < i) as follows:
soneratiual Rayleigh Quotient
(0,, Adr)
(0r, BB,)² (ūg, (ú,) (0,, Büs)
u=(b:lūzes)=
(4)
(0,, Bü;)
A
Σ
(0r, 2
where 0,
(5)
|
jei
roward
penalty
A; = (6..AR) and ||=||B Vie Bz).
Player i's utility has an intuitive explanation. The first term is recognized as the generalized Rayleigh quotient which can be derived by left multiplying both sides of the SGEP (v T Av = Au Bo) and solving for A. Note that the generalized eigenvectors
guaranteed to be B-orthogonal, i.e., io Bry = 0 for all # j (Appx. Lemma 3 Therefore, the reward term incentivizes players to find directions that result in large eigenvalues, but are simultaneously penalized for choosing direc- tions that align with their parents (players with index less than i, higher in the hierarchy). Finally, the penalty coefficient X serves to balance the magnitude of the penalty terms with the reward term such that players have no incentive to "overlap" with parents. In Appx. B Proposition 4 we derive these same utilities via a deflation perspective. Next, we formally prove these utilities are well-posed in the sense that, given exact parents, their optima coincide with the top-k SGEP solution.
Lemma (Well-posed Utilities). Given exact parents and assuming the top-k eigenvalues of B- are distinct and positive, the maximizer of player i's utility is the unique generalized eigenvector U; (up to sign, i.e., Ug is also valid).
Note that Å; = (0..A0.) (6s 60./116:|| n. Ac.//
(e. T C.lle. Be./ (.)) B.. therefore, the results above still hold
for utilities defined using vectors constrained to the unit ellipsoid, | = 1, rather than the unit- sphere, ||0:|| / = However, in our setting, is massive matrix which can never be explicitly constructed and instead only observed via minibatches. It is then not clear how to handle the con- straint ||A*| A = 1. We therefore only consider an approach that assumes ||sa||s 1.
Next, we provide intuition for the shape of these utilities. Surprisingly, while non-concave, we prove analytically in Appx. B that they have a simple sinusoidal shape. numerical illustration is given in Figure to help the reader visualize this property.
Proposition 1 (Utility Shape). Each player's 's utility is periodic in the angular deviation (0) along the sphere. Its shape is sinusoidal, but with its angular axis (0) smoothly deformed as a function of B. Most importantly, every local maximum is global maximum.
Figure I illustrates primary difficulty of solving the SGEP over SVD. Due to the extreme differ- ences in curvature caused by the B matrix, the SGEP should benefit from optimizers employing adaptive per-dimension learning rates. To our knowledge, this 1-d visualization of the difficulty of the SGEP is novel and we exploit this insight in experiments.
Finally, we formally define our proposed game and prove its equilibrium constitutes the top-k SGEP solution. We use the Greek letter gammu to denote generalized, and we differentiate between the game and the algorithm with upper I' and lower case Y respectively.
Definition 1 (I (aaeee. Let T-EigenGame be the game with plavers i E (l,...,k), their sirategy spaces i; E Sd-1, and their utilities u; as defined in equation (48).
'The Courant-Fischer min-max principle poses the ith generalized eigenvalue as the solution to a two-player, zero-sum game Paaretti 1998) sce Appx. A.2 for further discussion.
3

---

Published as a conference paper at ICLR 2023
Player Uniltt
ΣARt 12c
(see Appx. B)
I A..Ae Boror..0
Uniitty 2-
EA By, jor
V2
104" 175'
Angle Along 2-0 Sphere (ra Manitok))
Figure 1: Each player's utility is sinusoid angular deviation according to B: values for A and B used in this example are given in Appx. B Three mathematical representations of the utility are plotted; their equivalence is supported by the overlapping curves. If player 2 aligns with the top eigenvector (dashed vertical), they receive zero utility. If they align with the second eigenvector (solid vertical), they receive X2 (optimal) as reward. If B = / as in SVD/PCA, the vertical lines indicating the minima and maxima would be separated by exactly 90% In this case, the matrix B redefines what it means for two vectors be orthogonal (f0;, Biy) = 0), so that the vectors are 71 (equivalently, 180º - 71 = 109") from each other.
the sphere warped tangentially along the axis of
Theorem (Nash Property). Assuming the top-k generalized eigenvalues of the generalized eigen- value problem Av XBv are positive and distinct, their corresponding generalized eigenvectors form the unique, strict Nash equilibrium of TaneeeGGane.
,.....,, k}) is the unique best response to U-i, which implies the entire set constitutes the unique Nash equilibrium.
Proof. Lemma !
proves that each generalized eigenvector eN (i (l....,
ALGORITHM: UNBIASED PLAYER UPDATES AND AUXILIARY VARIABLES
Given that T-EigenGame suitably captures the top-k SGEP, we now develop an iterative algorithm approximate its solution. The basic approach we take is to perform parallel gradient ascent on all player utilities simultaneously. We focus on this approach in particular because it aligns with the predominant machine learning paradigm and hardware. We will first write down the gradient of each player's utility and then introduce several simplifications for the purpose of enabling unbiased estimates in the stochastic setting.
Up to scaling factors, the gradient of player i's utility function with respect to 0; is
(o) B6:) (0, Ao A0:)
(0), Bog) (0) Bi,) (6i, Būt) Bü, (ūi, Bi,)
(6)
(oi, B
(0z, B
See Lemma 5 in Appx. B for a derivation of the gradient. Recall that B matrix that we intend to estimate with samples, i.e., it is random variable, and it appears several times in the denominator of the gradient. Obtaining unbiased estimates of inverses of random variables is difficult (e.g., the naive approach gives overestimate; E[1/2] > 1/E[z] by Jensen's ''s inequality). We remove the scalar (0,, B in the denominator because it is common to all terms and will not change the direction of the gradient the location of fixed points; this step is critical the design of stochastic algorithm which we will explain later. We also use the following two additional relations:
Ag (or, Bo,) (0;, Ao₂) if player i's parents match their solutions, i.e., Újzi Ujsc iii (6), Bd,) |, B is strictly positive and real-valued because B > 0.
to arrive at the simplified update direction
reward
penalty
V, = (0] Ai:)A0; - (0, Bú;
Σ
(6_ Agg (6,, Boa) Bū, (0,, Būg) Bo;
(7)
jzt
4

---

Published as a conference paper at ICLR 2023
Algorithm Deterministic Full-batch 7-EigenGame
1: Given: A E Raxd and B E Raddd step size sequence T/t and number of iterations T.
2: 6 ~ 84-1, i.e., i1 ~ (( Ia): 0 <- 0//l6;, for all
3: for = 1:: do
4: parfor = 1: do
8,
5: "j Bo,)
6: rewards + (0. B6, (0. Bo
7:
penalties t jes (0, Aúj) ((; Bo,)Bi, (0,, Búj)
8:
V f- rewards penalties
9:
6 0; M
10:
& + [
11: end parfor
12: end for
return all 0%
Simplifying the gradient using 1 sound because the hierarchy of players ensures the parents will be learned exactly asymptotically. For instance, player I's update has no penalty terms and so will converge asymptotically. The argument then proceeds by induction.
We will revisit this issue later, but for now we will show this update converges to the desired solution given exact estimates of expectations (full- setting). Lemma is a stepping stone proving convergence with arbitrary parents in Theorem 2
Note that B still appears in the denominator via the ūj terms (recall equation
48
Lemma 2. The direction V, defined in equation un u,(6/ (e(s)) given exact parents 0z<i = Uyci-
is a steepest ascent direction on utility
Proof. This fact follows from the above argument that removing positive scalar multiplier does not change the direction of the gradient of u, w.rt. ég and applying relation
We present the deterministic version of ? G-meennGame in Algorithm| where k players use V, in maximize their utilities in parallel (see parfor-loop below). While simultaneous gradient ascent fails to converge to Nash equilibria in games in general, succeeds in this case because the hierarchy we impose ensures each player has a unique best response (Lemma I this type of procedure is known as iterative strict dominance in the game theory literature. Theorem 2 guarantees it converges asymptotically to the true solution.
proven in Appx.
Theorem 2 (Deterministic / Full-batch Global Convergence). Given symmetric matrix A and symmetric positive definite matrix B where the top-k eigengaps of B A are positive along with square-summable, not summable step size sequence Tp. (e.g., 1/t), Algorithm ! converges to the top-k generalized eigenvectors asymptotically (limy with probability 1.
In the big data setting, A and B statistical estimates, i.c., expectations of quantities over large datasets. Precomputing exact estimates is computationally expensive, so we assume a data model that allows drawing small minibatches of data at time. Under such a model, stochastic approxi- mation theory typically guarantees that as long as the update directions are unbiased, i.e., equal in expectation to the updates with exact estimates, then an appropriate algorithm will converge to true solution.
In order to construct an unbiased update direction given access to minibatches of data, we need to draw multiple minibatches independently at random. We construct an unbiased estimate of products of expectations, e.g.. (6 B6,) A by drawing an independent batch for each, e.g., one for B and one for A. However, the B that appears in the denominator of új is problematic; we cannot construct an unbiased estimate of the inverse of a random variable.
These problematic ú terms only appear in the penalties, which function of the parents' eigen- vector approximations. The first eigenvector has no parents, and so we can easily construct an unbiased estimate for it using multiple minibatches. We can then construct unbiased estimate for
5

---

(0, Published as a conference paper at ICLR 2023
Algorithm 2 Stochastic GamegenGame
1: Given: paired data streams X, Rxxd, and Y, E R number of parallel machines M
per player (minibatch size per machine // h ) step size sequences V and 7ts scalar lower bounding Omin (B), and number of iterations X/
2: 6 ~ 5t-1 L.C., 02 NNO,,, Ia): 0 c 0//l6;] for all
3: [Bé]; + 6 for a
4: for t 7 do
5: parfor i
do 6: parfor 1: M do
7:
Construct Aem and Bim (*unbiased estimates using independent data batches)
8:
Dj
V (m, [B6],
9:
[Bil, max max ()()).))
10:
rewards (0, B 03) A Amm 0;
11:
penalties Ee<r (0 AmmD,) Bem B) (0,, Bem
Bem
12:
f rewards penalties
(Bem [(),)
im
14:
end parfor
15:
V. + M Em V mm
16:
6f ú; + 1/e V
17:
6 f [.l
18:
VB + MI Eml
Bv
im
19:
Bi] < [Bo]: + 7/8
Bv
20:
end parfor
21:
end for
22:
return all 0
each subsequent player by inductive reasoning. Intuitively, once the parents have been learned, úg should be stable and it should be possible to estimate Bú, from a running average, and in turn, ÿy. This suggests introducing an auxiliary variable, denoted BBö] to track the running averages of Bi, (a similar approach employed in (Přau et al., 2018)). This effectively replaces Bý, with non-random variable, avoiding the bias dilemma, ables. Note that introducing this auxiliary variable implics the inner product (0), [BE],} may not be positive definite, therefore, manually clip the result to be greater than equal to p. the minimum singular value of B.
the expense of doubling the number of vari-
highlighted in color (auxiliary differences in blue, clipping in red). We point out that introducing an auxiliary variable for player track [Bo]; is not feasible because unlike player i's parents' variables, cannot be sumed non-stationary. This is why removing (6,, Bū,), earlier from the denominator of equation d was critical. Lastly, note that these modifications the update are derived using an understanding of the intended computation and theoretical considerations; put shortly, autograd libraries will not
Precise pseudocode is given in Algorithm 2 Differences to Algorithm
uncover this solution. See Appx. E.2 for more discussion and analysis of Algorithm 2
Computational Complexity and Parallelization. The naive, per-iteration runtime and work costs of this update are (bdk?²) with batch size but due to the simplicty of the update (i.e., purely matrix-vector products), there are several opportunities for both model and data parallelism to reduce runtime cost to (dkk) (see Appx. [ for steps). Note that low aggregate batch sizes can induce high gradient variance, slowing convergence (Durmus al. 2021b. making data parallelism desircable.
To give a concrete example, if each player (model) parallelizes over M b machines (data) as indicated by the two parfor-loops, the complexity reduces to O(dk). This is easy to implement with modern libraries, e.g., pmap using Jax, and as in prior work (Gemp et al., 2021). the com- munication of parents Ui<i between machines is efficient in systems with fast interconnects (c.g., TPUs) although this presents a bottleneck we hope to alleviate in future work. Alternative par- allel implementations discussed in Appx. Lastly, the update consists purely of inexpensive

---

Published as a conference paper at ICLR 2023
M cad Signals
Original Signats
Sklearn ICA
Scipy
PEgeenC ome
Blind Source Separation. Algorithm - D--geenGamm) run for 1000 epochs with mini- batches of size n subsampled i..dd. from the dataset recovers the three original signals from the linearly mixed signals. Seikit-lear''s FastICA also recovers the signals by maximizing an alterna- tive measure of non- -on-Gauusia Directly solving the SGEP using scipy. .inallg....... eigh (A, B) fails to cleanly recover the gray sinusoid (black circle highlights a discontinuity) due to overfit- ting to the sample dataset. We confirm this by training y-EigenGame for many more iterations and show it exhibits similar artifacts in Appx. G
Figure 2:
elementwise operations and matrix-vector products that be computed quickly on deep learning hardware (e.g.. GPUs and TPUs); unlike previous state-of-the-art (Meng el al. 2021) no calls to CPU-bound linear algebra subroutines are necessary.
4 RELATED WORK
The SGEP is a fundamental problem in numerical linear algebra with numerous applications in machine learning and statistics. There long history in numerical computing of solving large
SGEP problems (Sorensen 2002 Knyazev & Skorokhodov 1994, Golub & Ye. 2002 Aliaga al.)
2012
Klinvex et al. 2013). Many methods iterate with what can be viewed as "gradient-lie like up-
dates yakonov & Knyazev 1982, yakonov & Knyazev 1992). however, they not immedi-
ately applicable in the stochastic, streaming data setting. To our knowledge, efficient approaches for the SGEP specific sub-problems (e.g., CCA) scale best Old)k) in the streaming data setting.
Ge et al. (2166) give an algorithm for top-k SGEP that makes repeated use of a linear system solver to approximate the subspace of the true generalized eigenvectors, but may return arbitrary rotation of the solution. While their method is theoretically efficient, it requires precomputing A and B which prohibits its use in streaming data setting. The sequential least squares CCA algorithm proposed by Wang et al. (016) similarly requires access to the full dataset up front, however, in their case, it to ensure the generalized eigenvectors are exactly unit-norm relative to the matrix B. Alllen-Zhu & Li (2017a) develop a SGEP algorithm that is theoretically linear in the size of the input (nd) and k. however, they assume access to the entire dataset non-streamingg. LOBPCG (Knyazev 2017) non-streaming, Rayleigh maximizing technique with line-search and preconditioned gradient.
Arora et al. (017)) propose a convex relaxation the CCA problem along with streaming algo- rithm with convergence guarantees. However, instead of learning Vn E Rdd and V,, E Rdv directly, it learns M V. E Rdz which is prohibitively expensive to store in memory for high- dimensional problems. Moreover, the complexity of this algorithm is (dd²) due expensive projection step requiring an SVD of M. They propose an alternative version without guarantees that reduces the cost per iteration Odk?2).
Run with 1 logosh approximation negentropy (sec Hyvääinen & Oja 2000 for explanation).
7

---

Published as a conference paper at ICLR 2023
Minibatch Size Full batch
match Sec 1/16 FUl
Minibatch Sizo 1/256 Full batch
Egensoluc
Eggenvalue
Egeraalux
Thue 2k
Thee MX
True 3k
Appros. AA
Approx.
Approz I
-20
-10
-20
200
900
600
800
1000
0
200
400
630
800
1000
200
000
500
800
1000
Epochs
Epochs
Epochs
Top-4 MEDIAMILL 16,-120, 4.-100)
Top-4 CCA MMIST (d, 4-303)
Top-4 CCA on CIFAR 112-15366. 1,-15.30
Wropert Cornlations
1.0
Propoo ton of Correattons
ton Correiations
24.0
0.8
Capturee (POC)
0.8-
1.4
Capturet (PCE)
0.8
0.0
2.8
0.6
3.5
0.5
0.0
23.5
Captu
0.4
0.4
Sigentamm
Fige Come
Rigentaame
0.0
Meng al 21
0.0-
Mong et 21
Morg at al 23
0.5
1.0
L5
2.5
Samples
Samples (len Thousand)
Samp ('en Thousand)
Figure 3: Top: 7-EigenGame converges to the true SGEP solution regardless of minibatch size in support of the unbiased nature of the derived update scheme (Algorithm 2 See Appx. G.2 for additional experiments showing learning in sequence performs worse than its parallel counterpart above. Bottom: y EigenGame compared to (Meng et al., 2021) on proportion of correlations cap-
tured Σ
\ Σ A Shading indicates +1 stdev. Markers indicate runtime in seconds.
Gao et al. (019 also consider the streaming setting, but instead focuse on top-1 CCA and like (Wang al. 6 and (Allen-Zhu & Li 2017a), use shift-invert preconditioning accelerate convergence, Bhatia et al. 2018) solves top-1 SGEP in the streaming setting.
Most recently. Meng et al. (2021) proposed a method to estimate top-k CCA in streaming set- ting. Their algorithm requires several expensive Riemmanian optimization subroutines, giving per iteration complexity of (dd Their convergence guarantee is in terms of subspace error, so as mentioned above, the projection matrices Va and Vy may be rotations of their ordered (by cor- relation) counterparts. Their approach is the current state-of-the-a when considering CCA in the streaming setting for large datasets.
5 EXPERIMENTS
We demonstrate our proposed stochastic approach, Algorithm solving ICA and CCA via their SGEP formulations, and provide empirical support for its veracity. A Jax implementation is available
github. com/ deepmi hweemmind/eggggggg eigengame Scipy's linalg.. eigh (A, B) (Virtanen et al. 2020 is treated as ground truth when the data size permits. Hyperparameters are listed in Appx.
Independent Components Analysis. ICA can be used disentangle mixed signals such in the cocktail party problem. Here, we use the SGEP formulation to unmix three linearly mixed signals. Note that because the SGEP learns a linear unmixing of the data, the magnitude (and sign) of the original signals cannot be learned. Any change in the magnitude of a signal extracted by the SGEP can be offset by adjusting the magnitude and sign of mixing weight.
We replicate synthetic experiment from scikit- -eeettteeernnnne (Pedregooaa et al., 2011 and compare Algorithm 2 to several approaches. Figure shows our stochastic approach (7- (y-EinnGamme) is able to recover the shapes of the original signals (length 2000 time series).
Implicit Regularization via Fixed Step Size Updates. Note that if we run Algorithm 2 for 100x more iterations with 1/10th the step size, we converge to the exact SGEP solution (as found by scipy) and see similar artifacts the extracted signals due to overfitting. Recently, Durmus et al. (021) proved that fixed step size Riemannian approximation schemes converge stationary distri- bution around their solutions, which suggests E-EienGaame enjoys a natural regularization property and explains its high performance this the unmixing task. In Appx. G we show that it is difficult to achieve similar results with scipy by regularizing or B directly (c.g.. A + el) prior to calling sci scipy. py. 1 final eigh.
8

---

Published as a conference paper at ICLR 2023
corelorain Coeffic 127
Cornettonn Coefficent 6.
0.800
Step
Stop 2
Stop
0.600
5k
Ok
0.400
25c
0.900
23k
0.200
75kc
1004
B00K
200
400
600
800
200
400
600
500
50
100
250
200
250
Sarted Eiqemvalue Index
Sorted Elgenwalue Index
Sorted Eigenvalue Indox (d)
Figure 4: 3-EigenGame compares the representation (activations) of a deep network trained on CIFAR-10 for steps to that of its final learned representation (25k or 100k steps). Curves with higher correlation coefficients indicate more similar representations.
Unbiased Updates. We empirically support our claim that the fixed point of Algorithm 2 is un- biased regardless of minibatch size Not only does y-EigenGame recover the same generalized eigenvalues, but the top row of figure also suggests that the algorithm takes a similar trajectory for each minibatch size.
7-EigenGame linearly project multimodal datasets into swwrr-dimeniioal spaces such that they are maximally correlated. As discussed in re- lated work, several approaches have been developed extend CCA streaming, high-dimensional datasets. Recall that our approach has per-iteration complexity (bddk) with the previous state-of- the-art in the streaming setting having (df))) Meng al., 2021). We replicate the experiments of (Meng et al. (02T) and compare against their approach on three datasets.
Canonical Correlations Analysis. Here,
The bottom row of figure shows our approach competitive with (Meng et al. 202 We also point out that while the previous approach by Meng et al. (202T) enjoys theoretical convergence guarantees with rates, appears to slow in progress near a biased solution. These datasets are low dimensional (d < 3072), so we are able to obtain ground truth eigenvectors efficiently using scipy. Our next set of experiments considers much higher dimensional where a naive call to scipy fails.
Large-scale Neural Network Analysis. Recently, CCA has been used to aid in interpreting the rep- resentations deep neural networks (Raghu et al. 2017 Morcos et al. 2018 Kornblith et al. 2019). These approaches dimensionality views of representations (via PCA), or small dataset sizes to accomodate current limits of CCA approaches. We replicate one of their analyses (specifically Fig. 1a of (Morcos al.) 2018)) on the activations of an entire network (not just a layer), unblocking this type of analysis for larger deep learning models.
restricted to layer-wise comparisons of representations, reduced-
The largest dimensions handled in (Raghu et al. 2017 are O(103). Figure demonstrates our approach (parallelized over TPU chips) on (11))) dimensions (left), (109) dimensions (middle), and (110)) dimensions (right). Note that in these experiments, we are loading minibatches of CIFAR-10 images, running them through deep convolutional network, harvesting the activations, and then passing them to our distributed 7-EigenGamm solver. As mentioned in Section P our understanding of the geometry of the utilities suggests replacing the standard gradient ascent on ú; with Adam (Kingma& & Bal (214)): Adam exhibits behavior that implicitly improves stability around equílbriia Geep & McWilliams, 2019). For the smaller O setting, where we can exactly compute ground truth using scips py, we confirm that our approach converges to the t0p-1024 (out of 2048 possible) cigenvectors with a subspace error of 0.002 (see Appx. A).
6 CONCLUSION
We presented I T-EigenGame, a game-theoretic formulation of the generalized eigenvalue problem (SGEP). Our formulation enabled the development a novel algorithm that scales to massive streaming datasets. The SGEP underlies many classical data processing tools across the sciences, and we believe our proposed approach unblocks its use on the ever-growing size of modern datasets in the streaming setting. In particular, it achieves this by parallelizing computation using modern Al-centric distributed compute infrastructure such as GPUs and TPUs.
"The gray line converges last because chose minimize rather than maximize kurtosis.

---

Published as a conference paper at ICLR 2023
We thank Claire Vernade for reviewing the paper and proofs and early dis- cussions. Thore Graepel for early discussions. Zhe Wang for guidance on engineering. Sukhdeep Singh for project management.
Acknowledgements.
REFERENCES
Jose I Aliaga, Paolo Bientinesi, Davor Davidović, Edoardo Di Napoli, Francisco D Igual, and En- rique S Quintana- Orti. Solving dense generalized eigenproblems on multi-threaded architectures. Applied mathematics and computation, (18(22):11279111
2012.
Zeyuan Allen-Zhu and Yuanzhi Li. Doubly accelerated methods for faster and generalized eigendecomposition. In International Conference on Machine Learning, pp. 98-106. PMLR, 2017a
Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: global, gap- free, and near-optimal rate. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 487-492. IEEE, 2017b.
Andre Altmann, Neda Jahanshad, Paul M Thompson, and Marco Lorenzi. Partial least squares provides a whole-genome whole-brain imaging genetics approach. 2021.
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.
Haim Avron. A generalized courant-fischer minimax theorem. 2008
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.
Tijl De Bie, Nello Cristianini, and Roman Rosipal Figenproblems in pattern recognition. In Hand- book of geometric computing, pp. 129-167. Springer, 2005.
Magnus Borga, Tomas Landelius, and Hans Knutsson. A unified approach PCA, PLS, MLR and CCA. Linköping University, Department of Electrical Engineering, 1997.
Thomas F Boucher, Marie Ozanne, Marco L Carmosino, M Darby Dyar, Sridhar Mahadevan, Elly A Breves, Kate Lepore, and Samuel M Clegg. A study of machine learning regression methods for major elemental analysis of rocks using laser-induced breakdown spectroscopy. Spec- trochimica Acta Part B: Atomic Spectroscopy. 107:1-10. 2015.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142 2012.
Alain Durmus, Pablo Jiménez, Éric Moulines, and SAID Salem. On riemannian stochastic approx- imation schemes with fixed siep-size. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2021.
EG D' yakonov and AV Knyazev. Group iterative method for finding lower-order eigenvalues. Moscow University Computational Mathematics and Cybernetics, 15:32-40, 1982.
EG D' yakonov and AV Knyazev. On an iterative method for finding lovver eigenvalues. Russian Journal of Numerical Analysis and Mathematical Modeling, 1992.
Chao Gao, Dan Garber, Nathan Srebro, Jialei Wang, and Weiran Wang. Stochastic canonical corre- lation analysis. J. Mach. Learn. Res., 20:167 2019.
Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. In Inter- national Conference on Machine Learning, pp. 2741-2750. PMLR, 2016.
Ian Gemp and Brian McWilliass The unreasonable effectiveness of adam on cycles. In NeurIPS Workhhop Bridging Game Theory and Deep Learning, 2019.
10

---

Published as a conference paper at ICLR 2023
Ian Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Eigengame: PCA as Nash equilibrium. In Interaational Conference for Learning Representations, 2021.
lan Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Eigengame unloaded: When
playing games is better than optimizing. International Conference for Learning Representations, 2022.
Gene H Golub and Qiang Ye. An inverse free preconditioned krylov subspace method for symmetric generalized eigenvalue problems. SIAM Journal on Scientific Computing, 24(1):312-334, 2002.
Navin Goyal and Abhishek Shetty. Sampling and optimization on convex sets in riemannian man- ifolds non-negative curvature. In Conference on Learning Theory, pp. 1519-1561. PMLR, 2019.
Chenfeng Guo and Dongrui Wu. Canonical correlation analysis (CCA) based multi-view learning: An overview. arXiv preprint urXiv:1977.01693 2019.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard Maradda,, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant, Ar- ray programming with NumPy. Nature, 585(7825)3357-362,, September 2020. doi: 10. 1038/ 11.56-02002649---1 URL bttps:///oi.org//100//
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications.
Neural networks, 13(4-5):411 1-430, 2000.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988 2014.
A Klinvex, Faisal Saied, and A Sameh. Parallel implementations of the trace minimization scheme tracemin for the sparse symmetric eigenvalue problem. Computers Mathematics with Applica- fions, 6563):660-468, 2013.
Andrew Knyazev. Recent implementations, applications, and extensions of the locally optimal block preconditioned conjugate gradient method (LOBPCG), arXiv preprint 1rXiv:1708.08354 2017.
Andrew V Knyazev and Alexander I. Skorokhodov. Preconditioned gradient-type iterative methods in subspace for partial generalized symmetric eigenvalue problems. SIAM journal on numerical analysis, (1): 1226-122222229999 1994.
Simon Korbliihh, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton. Similarity of neural network representations revisited. In International Conference on Machine Learning, pp. 3519- 3529. PMLR, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yuanyuan Liu, Fanhua Shang,James Cheng, Hong Cheng, and Licheng Jiao. Accelerated first-order methods for geodesically convex optimization Riemannian manifolds. In Advances in Neural Information Processing Systems, pp. 4868-4877, 2017.
Marlos C Machado, Marc G Bellemare, and Michael Bowling. A laplacian framework for op- tion discovery in reinforcement learning. In International Conference on Machine Learning, pp- 2295-2304 PMLR. 2017a.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. arXiv preprint 17X0v 1089, 2017b.
Sridhar Mahadevan. Proto-value functions: developmental reinforcement learning. In Proceedings of the International Conference Machine learning, pp. 553-560, 2005.
11

---

Published as a conference paper at ICLR 2023
MATLAB. 9.7.0.1190202 (R2019b). The MathWorks Inc., Natick, Massachusetts, 2018.
Brian McWilliams and Giovanni Montana. Sparse partial least squares regression for on-line vari- able selection with multivariate data streams. Staristical Analysis and Data Mining: The ASA Data Science Journal, 3(3):170-193, 2010.
Brian Me WcWilliams David Balduzzi, and Joachim M Buhmann. Correlated random features for fast superviueee learning. In Advances in Neural Information Processing Systems, pp. 440-448, 2013.
Zihang Meng, Rudrasis Chakraborty, and Vikas Singh. An online riemannian pea for stochastic canonical correlation analysis. Advances in Neural Information Processing Systems, 34, 2021.
Ari Morcos, Maithra Raghu, and Samy Bengio. Insights on representational similarity in neural networks with canonical correlation. Advances in Neural Information Processing Systems, 31, 2018.
Beresford N Parlett. The symmetric eigenvalue problem. SIAM, 1998.
Lucas Parra and Paul Sajda. Blind source separation via generalized eigenvalue decomposition. The Journal of Machine Learning Research, 4:1261-1269, 2003.
Pedregosa, G. Varoquaux, Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825- 2011.
David Pfau, Stig Petersen, Ashish Agarwal, David GT Barrett, and Kimberly I. Stachenfeld. Spec- tral inference networks: Unifying deep and spectral learning. In International Conference Learning Representations, 2018.
Maithra Raghu, Justin Gilmer, Jason Yosinski, and Jascha Sohl-Dickstein. SVCCA: Singular vector canonical correlation analysis for deep learning dynamics and interpretability. In Advances in Neural Information Processing Systems, pp. 6076-6085, 2017.
C Radhakkishha Rao. The utilization of multiple measurements in problems of biological classifica- tion. Journal of the Royal Statistical Society. Series B (Methodological), 10(2):159-200 1948.
Suhail M Shah. Stochastic approximation on Riemannian manifolds. Applied Muthematics Opti- mization, pp. 1-29, 2019.
Cees GM Snoek, Marcel Worring, Jan Van Gemert, Jan-Mark Geusebroek, and Arnold WM Smeulders. The challenge problem for automated detection of 101 semantic concepts in multi- media. In Proceedings of the 14th ACM international conference on Multimedia, pp. 421-430, 2006.
Danny Sorensen. Numerical methods for large eigenvalue problems. Acta Numerica, 11:519-584, 2002.
Kimberly I. Stachenfeld, Matthew Botvinick, and Samuel Gershman. Design principles of the hippocampal cognitive map. Advances in neural information processing systems, 27, 2014.
Vincent Tan, Nick Firoozye, and Stefan Zohren. Canonical portfolios: Optimal asset and signal combination. arXiv preprint arXiv:2202.10817. 2022.
Cheng Tang. Exponentially convergent stochastic k-PCA without variance reduction. In Advances in Neural Information Processing Systems, pp. 12393-12404, 2019.
Georgios Tzounas, Ioannis Dassios, Muyang Liu, and Federico Milano. Comparison of numerical methods and open-source libraries for eigenvalue analysis large-scale power systems. Applied Sciences, 10(21):7592, 2020.
12

---

Published as a conference paper at ICLR 2023
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nel- son, Eric Jones, Robert Kern, Hric Larson, C J Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-201 2020. doi: 10.1038/s4 192-019-0686--1
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395-416, 2007.
Weiran Wang. Jialei Wang, Dan Garber, and Nati Srebro. Efficient globally convergent stochas- tic optimization for canonical correlation analysis. Advances in Neural Information Processing Systems, 29, 2016.
13


Reviews:
[{"review_id": "zBDWfNCxNbh", "reviewer": "Reviewer_U98f", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This work provides an algorithm for identifying the top-$k$ generalized eigenvalues for a pair of symmetric positive definite matrices $A$ and $B$. The algorithm works by reducing this problem to finding a Nash equilibrium to a multi-player game. For this game the authors prove that the gradient ascent algorithm provably converges asymptotically to the top-$k$ generalized eigenvalues. \n\nThe authors also seek to extend their algorithm to the stochastic setting where matrices $A$ and $B$ are accessible through stochastic estimates of their vector products via batching. They propose several modifications to their original objective that addresses several problems that arise with providing unbiased gradient estimates. While their modifications lead to unbiased estimators, they also make a complete and formal analysis harder and thus they leave it for future work. Empirically though, they do observe convergence on problems 1000x larger than the ones studied by prior work.\n\nThe ability to have independent machines processing independent mini-batches of $A$ and $B$, allows for low per-iteration complexity $O(dk)$ as compared to prior state of the art which requires $O(d^2k)$. The key is that matrix vector products cost $O(d)$ instead of $O(d^2)$ when considering minibatches of $O(1)$ samples. ", "summary_of_the_review": "I recommend this paper for acceptance. I am inclined to raise my score higher if the authors improve on the points raised in the \"Strengths and Weaknesses\" section. ", "strength_and_weaknesses": "This work has three major strengths. First, the problem of generalized eigenvalue problem and its importance to the machine learning community is thoroughly motivated. Second, although there have been several works studying game-theoretic solutions to the standard (non-generalized) eigenvalue problem, these approaches are not directly applicable since the generalized eigenvalue problem is not equivalent to a standard eigenvalue problem for a symmetric positive definite $A$. Third, a direct generalization of previous approaches (for example using Equation (4) or (5)) poses unique challenges when applied to the stochastic (mini-batch) setting. Up to the technical issues outlined in Appendix E.2, the proposed approach resolves these challenges.\n\nRegarding weaknesses, there are some points in this work that could benefit from additional elaboration.\n\na) $O(dk)$ iteration complexity property\nThe way I understand it, every algorithm that uses matrix vector products and has as many machines per player as the datapoints in the batch of $A$ and $B$ also avoids the $O(kd^2)$ factor in their per-iteration analysis. Effectively, it seems to me that the key claim is that the proposed algorithm only uses matrix vector products whereas prior art does not. I think clarifying if this is really the case and why prior work cannot adopt the same matrix-vector product interface would help. \n\nSecondarily, as stated the result has some limitations. It is unclear how setting the batch size to be equal to the machine count per player affects the number of iterations required. It is not clear if we are trading off faster iterations and higher iteration counts. \n\nb) Comparison with top-1 generalized eigenvector + deflation\nThis theoretical analysis of this work a lot of times argues that given (approximate) convergence of players $i < j$, player $j$ can approximately find the $j$th generalized eigenvector. To me this seems very similar to how we can use power iteration and variants to find the top eigenvector, apply a deflation step and then find the next eigenvector.\n\nIt is not clear to me if one could apply an algorithm for a top-1 generalized eigenvector like Bhatia et al. (2018) and with an appropriate deflation step find the next one and so forth. Is this actually the case? If so what are the limitations? If not, why?\n\nA key advantage I can see is that here all players work concurrently whereas the other approach would find the eigenvectors sequentially. The theoretical analysis however does not seem to take advantage of that. Maybe an experimental comparison between updating all players concurrently and only updating after the convergence of previous players would help clarify this point to the reader.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lz0PV9-ED3", "reviewer": "Reviewer_dLpL", "summary": "", "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": "", "summary_of_the_paper": "This paper presents an algorithm to compute the $k$ dominant eigenpairs of a streamed matrix. The algorithm is based on an optimization viewpoint where each individual eigenpair is maximizing a separate cost function. Numerical experiments verify the effectiveness of the proposed scheme.", "summary_of_the_review": "The proposed method is interesting and the paper is well-written. My main concerns are: a) similarity with the PCA case, and b) realistic application in modern problems.", "strength_and_weaknesses": "I tried my best to check the proofs and they appear correct.\n\nStrengths:\n-) The paper introduces a nice setting/idea for eigenvalue computations.\n-) Lots of intuition is presented and discussed.\n-) Results demonstrate that the proposed method is effective.\n\n-) The difference between eigengame-PCA and the current work is not properly explained.\n-) The authors should discuss in more depth other optimization-based eigenvalue solvers such as TraceMIN or LOBPCG. \n-) It's likely I missed something here, but why do the authors need to include the \"Nash's equilibrium\" phrase throughout their paper? \nIt seems to me that the algorithm developed is nothing more than an optimization-based eigenvalue solver for streamed datasets; which is absolutely fine for a publication. What am I missing?\n-) The discussion about computational complexity is a bit confusing; why is $O(dk)$ after we parallelize across M=b batches? Is the cost per iteration of for-k loop only $O(d)$? I thought it would $O(dk)$ (which means the paralleized complexity is $O(dk^2)$). I must be missing something here.\n-) My main concern is the following: are there really situations where I can not access the matrices A and B in a sequential batched manner? Because in this case the authors can use standard numerical linear algebra optimization-based approaches (i.e., out-of-core computing). In other words, in what applications $A$ and $B$ are accessed truly randomly?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cItbdZXmcFq", "reviewer": "Reviewer_aVkz", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 considers the problem of finding top-k eigenvalues of the symmetric generalized eigenvalue problem (SGEP). It proposes a game-theoretic formulation whose Nash equilibrium is the top-k eigenvalues of SGEP. Using this new result, the authors develop a parallelizable algorithm suitable for tackling SGEP with streaming data sets. It proves the asymptotic convergence of the proposed algorithm and show how to achieve O(dk) runtime complexity. ", "summary_of_the_review": "This paper proposes a game-theoretic formulation for SGEP. Based on the novel result that the Nash equilibrium of the formulation is the top-k eigenvalues of SGEP, the authors propose a novel algorithm, which shed new light on many problems that can be equivalently formulated as SGEP. The full-batch version of the proposed algorithm is equipped with theoretical guarantee. It is also applicable to streaming data set with seemingly good numerical performance.", "strength_and_weaknesses": "Strength:\n1. The paper is clearly motivated and written. It is a pleasure to read.\n2. The game-theoretic formulation is novel, which motivates the development of the novel algorithm.\n3. The proposed algorithm is equipped with strong convergence guarantees.\n4. The proposed algorithm is suitable for parallelization and can achieve O(dk) runtime complexity, which outperforms O(d^2k) in state-of-the-art algorithms.\n\nWeakness:\n1. It seems that the convergence guarantee of the stochastic version of the algorithm is missing.\n2. Can this approach be applied to general non-symmetric GEP? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "U3yk23nowoc", "reviewer": "Reviewer_4TCc", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper is concerned with solving the symmetric generalized eigenvalue problem $Av = \\lambda B v$ , which generalizes various other well known problems like PCS, CCA, ICA etc. A particular approach chosen is to consider a corresponding game between k players and the rewards are set such that the Nash equilibrium is the top-k solution. What we already know about this problem: If we can invert B in the equation above, then SGEP can be solved as an SVD problem. This however loses structure (for example A and B are symmetric in SGEP) and therefore previous game theoretic approaches to solving SVD do not apply here.\n\nLike mentioned above, the approach in this work is to construct a game between k players each selecting a strategy $v_i$. Their first main contribution is in constructing a sound utility function such that the Nash equilibrium of this game is the top-k SGEP solution. Intuitively, the utility for player i conditioned on players j < i (henceforth parents of i) is designed to: (1) incentivize finding directions that have large eigenvalues (called reward) (2) but simultaneously choosing directions which are far from directions chosen by the parents. \n\n To show that these rewards are sound, the work first shows that assuming $B^{-1}A$ has nice spectrum, and the parents converge to correct eigenvectors (called exact parents henceforth), the unique generalized eigenvector $v_i$ maximizes the player i's utility. This follows from noting that for the exact parents, the penalty term linearizes after a re-parameterization (and the reward term is already linear in the said re-parameterization). This shows that the top-k eigenvectors form the strict Nash equilibrium of this game. \n\nAnother particular important aspect of this utility design is that every local maximum is a global maximum here which follows from previous work. Together with above result, this suggests a simple gradient based algorithm. The work next shows under deterministic setting (A and B are known), this simple gradient based algorithm asymptotically converges. This requires proving that the error in eigenvectors for parents lead to bounded error in the solutions for the children. This result borrows ideas from previous work [Gemp et al. 2021].\n\nSome care is needed to extend this to stochastic/streaming setting, we need the terms appearing in the denominator to be nicely conditioned and have to be handled appropriately. This algorithm has a per iteration complexity $dk$ which improves over the previous state-of-the-art per iteration complexity $d^2k$. This is followed by extensive experiments on CCA and ICA showing in practice this method is competitive. ", "summary_of_the_review": "I think this is a good contribution to understanding game theoretic version of various problems like ICA, PCA, CCA etc. Moreover, this work provides a very practical algorithm.", "strength_and_weaknesses": "I think the writing in the paper could use some more work. Especially since most of the claims have short and simple proofs, it would be nice to include some more intuition about them in the main text. I verified most of the proofs in the supplementary materials. Some other concerns I have:\n1. Theorem 1 (which follows from Lemma 1) does not require Proposition 1. And therefore Proposition 1 should not be before Definition 1 and Theorem 1. In fact, its only ever used in showing that Algorithm 2's updates are unbiased. \n\n2. Lemma 1: $w_p$ are not defined. It would be nice to say they are arbitrary real coefficients and give some exposition on your end goal. For example, we now consider $\\hat v_i$ as arbitrary linear combination of $v_i$'s. We will show that maximizing the utility for player is same as solving the following linear program: ...\n\n3. Proposition 1: It would be nice to give a more definite reference for EigenGame (and results implying the utility function is cosine).\n\n\nI think the claims about improving the per-iteration complexity should be followed by explanation about its implication on total time complexity. I think it should be noted that this algorithm does not have convergence rates and in fact, the error from parents on the time-complexity would show up in the number of iterations needed for the algorithm to converge. This is real and looking through proof of Theorem 2, it seems like the number of iterations even in the deterministic case scale exponentially in $k$ (since the $\\epsilon$ error from parents lead to $\\sqrt{\\epsilon}$ error in children's fixed point).\n\nThat said, I would like to emphasize that the above comment does not dilute the contribution of this work.\nI think the paper makes a good technical contribution to an important problem.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%