EigenGame Unloaded: When playing games is better than optimizing
Authors: Ian Gemp
Brian McWilliams
Claire Vernade
Thore Graepel
Venue: ICLR 2022 Poster (2022)
Keywords: pca
principal components analysis
nash
games
eigendecomposition
svd
singular value decomposition

Abstract: We build on the recently proposed EigenGame that views eigendecomposition as a competitive game. EigenGame's updates are biased if computed using minibatches of data, which hinders convergence and more sophisticated parallelism in the stochastic setting. In this work, we propose an unbiased stochastic update that is asymptotically equivalent to EigenGame, enjoys greater parallelism allowing computation on datasets of larger sample sizes, and outperforms EigenGame in experiments. We present applications to finding the principal components of massive datasets and performing spectral clustering of graphs. We analyze and discuss our proposed update in the context of EigenGame and the shift in perspective from optimization to games.

Published as a conference paper at ICLR 2022
: EIGENGAME UNLOADED WHEN PLAYING GAMES IS BETTER THAN OPTIMIZING
Ian Gemp", Brian McWilliams", Claire Vernade & Thore Graepel DeepMind, London UK ingemp, knew, vernade @ddeppiind.comm com, thoregraepel@gmail..
ABSTRACT
We build on the recently proposed EigenGame that views cigendecomposition as a competitive game. EigenGame's updates are biased if computed using minibatches of data, which hinders convergence and more sophisticated parallelism in the stochastic setting. In this work, we propose an unbiased stochastic update that is asymptotically equivalent to EigenGame, enjoys greater parallelism allowing computation on datasets of larger sample sizes, and outperforms EigenGame in experiments. We present applications to finding the principal components of massive datasets and performing spectral clustering graphs. We analyze and discuss our proposed update in the context of EigenGame and the shift in perspective from optimization to games.
INTRODUCTION
Large, high-dimensional datasets containing billions samples are commonplace. Dimensionality reduction extract the most informative features is important step in the data processing pipeline which enables faster learning of classifiers and regressors (Dhillon et al. (2013). clustering (Kannan and Vempala 2009), and interpretable visualizations. Many dimensionality reduction and clustering techniques rely on eigendecomposition at their core including principal component analysis (Jolliffe 2002). locally linear embedding (Roweis and Saul (000), multidinensional scaling (Mead) 1992).
Isomap (Teenbaum et al. 2000). and graph spectral clustering (Von Luxburg 2007).
Numerical solutions to the eigenvalue problem have been approached from variety of angles for centuries: Jacobi's method, Rayleigh quotient, power (von Mises) iteration (Golub and Van der Vorst 2000). For large datasets that do not fit memory, approaches that access only subsets-on or minibatches--o of the data at time have been proposed.
Recently, EigenGame (Gemp et al. 2021) was introduced with the novel perspective of viewing the set of eigenvectors as the Nash strategy of suitably defined game. While this work demonstrated an algorithm that was empirically competitive given access only subsets of the data, its performance degraded with smaller minibatch sizes, which are required to fit high dimensional data onto devices.
One path towards circumventing FigenGame's need for large minibatch sizes parallelization. In data parallel approach, updates are computed in parallel partitions of the data and then combined such that the aggregate update is equivalent to single large-batch update. The technical obstacle preventing such approach for EigenGame lies in the bias its updates, i.e., the divide-and-conquer EigenGame update is not equivalent to the large-batch update. Biased updates are not just a theoretical nuisance; they can slow and even prevent convergence the solution (made obvious in Figure 4).
In this work we introduce a formulation of EigenGame which admits unbiased updates which we term g-EiienGamme. We will refer to the original formulation of EigenGame a-EigenGamme
μ- u-EigenGame and a-EigenGame are contrasted in Figure I Unbiased updates allow us to increase the effective batch size using data parallelism. Lower variance updates mean that B-EigenGame should converge faster and to more accurate solutions than a- G-EigenGame regardless of batch size. In Figure Ta (top), the density of the shaded region shows the distribution of steps taken by the
denotes equal contribution. I signifies unbiased or wnloaded and a denotes original.

---

Published as a conference paper at ICLR 2022
U3
0
(1)
(i))
e-2G
LEEG
(iii)
(iv)
Distance to Expected Trajectory
0
(a)
(b)
Figure 1: a Comparing a-EigenGame (Gemp al. 2021 and EigeeGGaaem (this work)
over 1000 trials with batch size of 1. (top) The expected trajectory of each algorithm from initialization (O) to the true value of the third eigenvector (x). (bottom) The distribution of distances between stochastic update trajectories and the expected trajectory of each algorithm as function of iteration count (bolder lines are later iterations and modes further left more desirable).
(b) Empirical support for Lemma 2 In the top row, player 3's utility is given for parents mis-specified by angular distance along the sphere of Z(ūjei: E [-200 100, 10 20% moving from light to dark. Player 3's mis-specification. Z(êi, 24), is given by the x-axis (optimum at 0 radians). a-EigenGame (i) exhibits slightly lower sensitivity than p-EigenGame (ii) to mis-specified parents (see equation (8)) However, when the utilities are estimated using samples X, p(X) (faint lines), M-EigenGame remains accurate (iv), while a-EigenGame (iii) returns utility (dotted line) with an optimum that is shifted to the left and down. The downward shift occurs because of the random variable the denominator of the penalty terms (see equation (3)
The trajectory when updating with E[X,] X.). 'Overestimation is expected by Jensen's s: [B[ 2 X[
stochastic variant of each algorithm after 100 burn-in steps. Although the expected path of a-EG is slightly more direct, its stochastic variant has much larger variance. Figure (bottom) shows that with increasing iterations, the μ-EG trajectory approaches its expected value whereas a-EG exhibits larger bias. Figure Tb further supports μ y-EigenGiame 's reduced bias with details in Sections and
Our contributions: the rest of the paper, we present our new formulation of EigenGame, analyze its bias and propose novel unbiased parallel variant, Ga-EigenGame with stochastic convergence guarantees. j--iieeGamme's utilities are distinct from a-EigenGame and offer an alternative perspec- tive. We demonstrate its performance with extensive experiments including dimensionality reduction of massive data sets and clustering large social network graph. We conclude with discussions the algorithm's design and context within optimization, game theory, and neuroscience.
2 PRELIMINARIES AND RELATED WORK
In this work, we aim to compute the k right singular vectors of data X, which is either represented as matrix, X axd of n d-dimensional samples, or as d-dimensional random variable. In either case, we assume we can repeatedly sample minibatch X, from the data of size n'' < n, X E R xd The top-k right singular vectors of the dataset then given the top-k eigenvectors of the (sample) covariance matrix, C E X X,) = E[C]].
For small datasets, SVD is appropriate. However, the time, (min (nd, nddd),, and space, O(nd), complexity of SVD prohibit its use for larger datasets (Shamir 2015) including when X is ran- dom variable. For larger datasets, stochastic, randomized, or sketching algorithms are better suited. Stochastic algorithms such Oja's algorithm (Oja 1982 Allen-Zhu and Li (017) perform power
2

---

Published as a conference paper at ICLR 2022
iteration (Rutishauser 1971) to iteratively improve approximation, maintaining orthogonality of the eigenvectors typically through repeated QR decompositions. Alternatively, randomized algo- rithms (Halko et al. 2011 Sarlos 2006 Cohen et al. 2017) first compute random projection of the data onto a (A + ssubuspe approximately containing the top-k subspace. This is done using techniques similar Krylov subspace iteration methods (Musco and Musco 2013). After projecting, a call to SVD is then made on this
data matrix. Sketching algorithms (Feld- man et al. 2020) such as Frequent Directions (Ghashami et at.) 2016) also target learning the top-k overcomplete sketch matrix of size (A + p) x d and maintaining a span of the top subspace with repeated calls to SVD. In both the randomized and sketching approaches, a final SVD of the n x (k + p) dataset is required to recover the desired singular vectors. Although the SVD scales linearly ni, some datasets are too large to fit in memory; in this case, an out-of-memory SVD may suffice (Haidar el al.) (017). For this reason, the direct approach of stochastic algorithmss, which avoid an SVD call altogether, is appealing when processing very large datasets.
subspace by maintaining
A large literature distributed approaches to PCA exists (Liang et al. 2014, Garber et al. 2017; Fan al.) 2019). These typically fol-
Algorithm 1 j-EigenGame"
1: Given: data stream X₁ R xd vectors og
low the pattern of computing solutions locally and then aggregating them in single round (or minimal rounds) of communication. The mod- ern distributed machine learning setting which
Sd-1 step sequence 1/t and iterations T.
2: 6, < 6 for a
3: for = :: do
has evolved to meet the needs of deep learning fundamentally different. Many accelerators joined with fast interconnects means the cost of communication is low compared to the cost of single update step, however existing approaches to distributed PCA cannot take full advantage of this.
4: parfor i= do
5:
rewards +- n X X
6: penalties
(xr X,0,)
7:
V + rewards - penalties
F. + -i -V",,
8:
6f + iz + m V.
9:
Notation: We follow the same notation as Gemp et al. (2021). Variables returned by approxi-
"
10:
6 ाहा
mation algorithm are distinguished from the true
11: end parfor
12: end for
solutions with hats, e.g., the column- wise matrix of eigenvectors V approximates V. We order the columns of V such that the ith column, f4+ the eigenvector with the ith largest eigenvalue A₁ The set of all eigenvectors {u,} with X, larger than A, namely uj's parents, will be denoted by
13: return all 0
Žド= Vjcc- Similarly, sums over subsets of indices may be abbreviated as = = The set of all parents and children of i denoted by u-i. Let the ith eigengap 9i X; \ We assume the standard Euclidean inner product (u, v) = u v and denote the unit-sphere and simplex in ambient space Rd with sd-1 and A respectively.
a-EigenGame. We build on the algorithm introduced by Gemp et al. (202)), which we refer to here as a- G-EeeenGame. This algorithm is derived by formulating the cigendecompossiionn of a symmetric positive definite matrix as the Nash equilibrium of game among it players, each player i owning the approximate eigenvector i E 1 Each player is also assigned utility function, utf (0: (0/0))e)) that they must maximize:
xliign-emally
(0, Cot)?
(0:10) C
Co
(I)
(oj, Coiz)
These utilities balance two terms, one that rewards a 6. that captures more variance in the data and a second term that penalizes é; for failing to be orthogonal to each of its parents شzزر (these terms are indicated with Var and ailign-penalyy in equation simultancously updates é; with gradient ascent, and it is shown that this process converges to the
(I).. In a EigenGaame, each player
Nash equilibrium. We are interested in extending this approach to the data parallel setting where each player i may distribute its update computation over multiple devices.
3

---

Published as a conference paper at ICLR 2022
3 A SCALABLE UNBIASED ALGORITHM
We present our novel modification to a- ---igenGamme called y-FigenGame along with intuition, theory, and empirical support for critical lemmas. We begin with identifying and systematically removing the bias that exists in the a-EigenGame updates. We then explain how removing bias allows us to exploit modern compute architectures culminating in the development of a highly parallelizable algorithm.
3.1 Q- E-EIGENGAME'S S BIASED UPDATES
Consider partitioning the sample covariance matrix C2 into a sum of m matrices as C, =
n , =
L - mn Xm Xm = 1 Σm Ctm- For sake of exposition, we drop the additional subscript on T in what follows. We would like a-EigenGamm parallelize over these partitions. However, the gradient of u, with respect to û; does not decompose cleanly over the data partitions:
mi
Aliga-penalty
Var
V &
Ci
Coj Ce
Cop
Σ
Cmus [[cmi m
Σ JCC
8. C Ct3
C Uz)
(2)
We include the superscript a on the EigenGame gradient to differentiate it from the μ j-EiignGaaee direction later. The nonlinear appearance of C in the penalty terms makes obtaining gradient difficult. The quadratic term in the numerator of equation (2) could be made unbiased by using two sample estimates of C, one for each term. But the appearance of the term in the denominator does not have an easy solution. Cm is likely singular for small n' (n' < d) which increases the likelihood of small denominator, i.e., a large penalty coefficient (boxed), we were to estimate the denominator with samples. The result is an update that emphasizes penalizing orthogonality over capturing data variance. Techniques exist to reduce the bias of samples of ratios of random variables, but to our knowledge, techniques to obtain unbiased estimates are not available. This was conjectured by Gemp el al. (202T) as the reason for why a-FigenGame performed worse with small minibatches.
unbiased
3.2 REMOVING a- O-EIGENGAME' BIAS
It is helpful to rearrange equation 2 to shift perspective from estimating a penalty coefficient (in red) to estimating a penalty direction (in blue):
Ci DJ CO,
V
Σ
Cmo=
Σ a<i
00 Cm
(3)
The penalty direction in equation 3) is still difficult to estimate. However, consider the case where oy is any eigenvector of C' with associated (unknown) eigenvalue X. In this case, Cê, = Xē; and the penalty direction (in blue) simplifies to êy because || = 1. While this assumption is certainly not met at initialization, E-EignGGame leads each by towards Uy. be met asymptotically.
expect this assumption to
This intuition motivates the following j-EigenGaame update direction for is with inexact parents Ú, (compare orange in equation (4) to blue equation (3)::
A = Cb.- [(TTCa))
C.
(4)
j-3
m
We use A instead of V because the direction not a gradient (discussed later). Notice how the strictly linear appearance of C' in p-EigenGamm allows the update easily decompose over the data partitions in equation 4 The G-EigenGame update satisfies two important properties.
Lemma 1 (Asymptotic equivalence). The u-EigenGame direction, A with exact parents (Ū. 0g j < i) is equivalent to a- a-EigenGame.
Proof. We start with a- e-EigenGame and add superscript to its gradient to emphasize this is the gradient computed with exact parents (ū, = Uz). Then simplifying, we find
0. Cu; Cuj = Cbs Σ
aJ Cvj Xuu3 = Cbs - [ = A (5)
V x Co. -E
0 Cvj
0 Y03
jei
jai
4

---

Published as a conference paper at ICLR 2022
Therefore, once the first (i 1) eigenvectors are leamned, learning the ith eigenvector with p
EigenGame equivalent to learning with a a-EigenGame.
Lemma 2 (Zero bias). Unbiased estimates of A can be obtained with samples from p(X)
Proof. Let X p(X) where X Id and p(X) is the uniform distribution over the dataset. Then
B| = EXXX 00
Σ
T 10,66 Cē. -(O, Co,C Coy)
jEi
where all expectations are with respect to p(X).
These two lemmas provide the foundation for a performant algorithm. The first enables convergence the desired solution, while the second facilitates scaling to larger datasets. Algorithm presents pseudocode for j-EigenGame where computation is parallelized over the l players.
3.3 MODEL AND DATA PARALLELISM
In our setting we have number of connected devices. Specifically we consider the paral- lel framework specified by TPUv3 available in Google Cloud, however our setup is appli- cable to any multi-host, multi-device system. The a-FigenGaame formulation (Gemp et al.) 2021) considers extreme form of model par- allelism (Figure 2ah where each device has its unique set of eigenvectors.
Vic
Viei
Vk
Vx-2
VK-1
VK
Vi-
Vien
In this work we further consider a different form of model and data parallelism which is directly enabled by having unbiased updates (Figure (b)). This enables ja- high-dimensional problems as well as massive sample sizes. Here each copied on MM devices. Update directions are computed on each device individually using different data stream and then combined by sum- ming or averaging. Updates are applied to sin- gle copy and this is duplicated across the M W-1 remaining devices. In this way, updates are computed using an M x larger effective batch size while still allowing device-wise model parallelism. This setting is particularly useful when the number of samples is very large. This form of parallelism not possible using the original EigenGame formulation since it relies on combining unbiased updates. In this sense, the parallelism discussed in this work generalizes that introduced by Gemp et al. (2021).
(a)
(b)
Figure 2: (al Extreme model parallelism as pro- posed in a- a-EigenGame. (b) Model and data par- allelism enabled by p-EigenGame. Squares are separate devices (here, M 4). Copies of es- timates are color-coded. Updates are averaged across copies for larger effective batch size.
deal with both
eigenvectors is
Note that we also allow for within-device parallelism. That is, each 0; in Figure 2 is contiguous collection of eigenvectors which updated independently, in parallel, on given device (for example using vmap in Jax). We provide pseudocode in Algorithm| 2 in the appendix which simply augments Algorithm [ with additional parallelized for-loop and aggregation step over available devices. We also provide detailed Jax pseudo-code for parallel μ gaEigenGamee in Appendix F We compare the empirical scaling performance of p-EigenGame against a-EigenGame on 14 billion sample dataset in section
4 SVD AS THE SOLUTION TO A NEW EIGENGAME
We theoretically examine the u-EigenGame algorithm and 1) prove that, using only minibatches of data, Jl-EigeGGame converges globally to the true eigenvectors, which 2) comprise the Nash equilibrium of novel game formulation recover through deriving pseudo-utility functions from update rules. Beyond proving specific theoretical properties of ja-EigenGame, we believe these proof techniques may be of wider interest the community.

---

Published as a conference paper at ICLR 2022
4.1 CONVERGENCE TO SVD
The asymptotic equivalence of ja-iigenGame to a-EigenGame ensures j--EigenGame is globally, asymptotically convergent and its unbiased updates ensure is scalable. Proof in appendix C
Theorem 1 (Global convergence). Given a positive definite covariance matrix C with the top-k eigen- gaps positive and a qquare-summande not summable step size sequence 1)t (e.g.. 1/11, Algorithm converges to the lop-k eigenvectors asymplotically (lint-+.)) with probability 1.
This stochastic asymptotic convergence result is complimentary to the deterministic (full-batch) sanite-sample result in Gemp et al. (2021) where each é; is learned in sequence. In contrast, the proof above applies when learning all i; in parallel. We leave finite-sample convergence to future work (Durmus el al. 2020
4.2 SVD IS NASH OF D-BIGENGAME
We arrived at μ JamiigeGaame by analyzing and improving properties of the a-EigenGame update. However, the u-FigenGaame update direction is linear each i; This suggests we may be able to design pseudo-utility function for it. Rearranging the update direction from equation (4) as
A = Ci. E5 (6,) = | Σ j<
0,0
Ca, = V
j<b
reveals that we can reverse-engineer the following utility function
deflation
u/ = 0.
0,0
C
[O.
(8)
j<i
where the stop gradient operator commonly used in deep learning packages. As the name implies, stops gradients from flowing through its argument so that equation (8) appears linear in è; instead of quadratic when differentiating the expression. In light of this, we have renamed A to A to emphasize that it is pseudo-graddd gradient of u!! Note that without the stop gradient. the true gradient of wf, would be [A + 16; rather than Ab; where A = [ - -Ejes 6J ú,JCC We analyze this alternative in Appendix H.l and find it, interestingly, to perform worse than μ EigiennG empirically.
The utility function ut has an intuitive meaning. It is the Rayleigh quotient for the matrix C, = 11-E 6 0z]C, which gives the covariance after the subspace spanned by Ūiاi has been removed. In other words, player i is directed to find the largest eigenvalue in the orthogonal complement of the approximate top-(i - 1) subspace. This approach is known as "deflating" the matrix C. Figure Tb illustrates p-EigenGame's 's reduced bias when estimating the new utility function (and resulting optimum) from an average over minibatches.
Definition 1 (u-EEienGaame. Lei y-EigenGame be the game with players E (I,....k), k.), their respective strategy spaces 6 E Sa-11, and their corresponding utilities ui as defined equation (g). Theorem 2. Top-k SVD is the unique Nash of p-EigenGame given symmetric C with the top-k eigengaps positive.
Proof. We will show by induction that each v; is the unique best response to U_s. which implies they constitute the unique Nash equilibrium. First, consider player l's utility. It is the Rayleigh quotient of C' because új is constrained to the unit-sphere, i.e., uf" = 6T Ct
8, Ca, Therefore, 6,
we know U1 maximizes uf and the maximizer is unique because its eigengap 91 > O. In game theory parlance, is best response U-1- The proof continues by induction. The utility of player is 2 8. [[- Ejet uyu, [C which is the Rayleigh quotient with the subspace spanned by the top (i - 1) cigenvectors removed. Therefore, the maximizer of uf is the largest eigenvector in the remaining subspace, i.e., Us. As before, 9: > 0, so this maximizer is unique. This shows that each U is the unique best response to u_;. therefore, the set of forms the unique Nash.
Notice how the induction proof of Theorem rellies on a) the hierarchy of vectors (v) does not depend v-1) and b) the fact that uf need only be sensible utility when all player i's parents

---

Published as a conference paper at ICLR 2022
Subspace Distance Longest Correct
Eigenieecor Streak
16
(Minibatch 1024)
Subspace Distance Longest Correct
Elgenveccoor Streak
(Minibatch 256)
Longest Correct
Eigenvector Streak
1.6
[Minibatch
(PEG (17)
JLFG 1134 P4 (55)
EG (2741
(19:
O C250
(0 (22)
50 19911
Cosu Bas 221
10a
10
Subspaac Distance
10
(43)
Eo (274)
GBA (391
10-2
Grandiian
10
10-2.
(16
Ous
122
Couss (43)
Reasufrae
30
40
10
20
30
40
10
50
Epachs
Epachs
Epachs
29
87
117
14
117
234
351
468
52
937 1875 2812 375a 4687 Iterations (thousends)
lteraions (thousands)
lterationn (thousands)
Figure 3: MNIST Experiment. Runtime (seconds) in legend on CPU (m 1). Each column evaluates a different minibatch size E {1024, 256, 32}. Shading indicates = standard error of the mean. Learning rates were chosen from {10-3 ..... 10-6) on 10 held out runs. Solid lines denote results with the best performing learning rate. All plots show means over trials (randomness arising from minibatches and initialization). Shaded regions highlight + standard error of the mean.
are eigenvectors. We revisit this in conjunction with Figure 5b later in discussion section 6. to aid researchers in the design of future approaches.
The Nash property is important because it enables the use of any black-box procedure for computing best responses. Like prior work, we develop a gradient method for optimizing each utility, however, that is not requirement, Any approach suffices if it can efficiently compute a best response.
EXPERIMENTS
As in FigenGame, we omit the projection of gradients onto the tangent space of the sphere; specifically, we omit line 8 in Algorithm[] 1 As discussed in Gemp er al. (2021). this has the effect of intelligently adapting the step size to use smaller learning rates near the fixed point. To ease comparison with previous work, we count the longest correct eigenvector streak as introduced by Gemp et al. (202)) which measures the number eigenvectors that have been learned, in order, to within an angular threshold (e.g., π 7/8) of the true eigenvectors. We also measure how well the set of é; captures the top-k subspace with normalized subspace distance: - 1/k Tr(U** P) E [0. where U = VVt
and P - vi Tang 2019). We provide additional experiments in Appendix
We compare u-EigenGame against a-EigenGame, GHA (Sanger 1989). Matrix Kra- sulina [Tang] 2019), and Oja's algorithm (Allen-Zhu and Li 2017) on the MNIST datasct. We flatten each image in the training set to obtain 60, 000 x 784 dimensional matrix X. deguossrjemoosstrtte y-EigenGame's 's robustness to minibatch size. performs best the longest streak metric and better than a- e-EigenGaame in subspace distance. We attribute this improvement to its unbiased updates and additional acceleration effects which we discuss detail section
MNIST.
Meena conversational model. This dataset consists a subset of the 40 billion words used train the transformer- based Meena language model (Adiwardana et al. (2020). The subset was preprocessed to remove duplicates and then embedded using the trained model.
The dataset consists of n ss 14 billion embeddings each with dimensionality d = 2560; its total size 131TB. Due its moderate dimensionality we can exactly compute the ground truth solution by iteratively accumulating the covariance matrix of the data and computing its cigendecomposstion. On a single machine this takes 1.5 days (but is embarrassingly parallelizable with MapReduce).
We use minibatches of size 4,096 in each TPU. We do model parallelism across 4 TPUs 16,384 samples per iteration. We test two additional degrees of data parallelism with 4x (16 TPUs, 65,536 samples) and 8x (32 TPUs, 131,072 samples) the amount of data per iteration respectively. We compute and apply updates using SGD with a learning rate of x 10 and Nesterov momentum with factor of 0.9.
7

---

Published as a conference paper at ICLR 2022
256
Eigenvertor Streak
Longest Correct
192
6-5G
8-EG
128
EG
J+EG (4x)
AE (8x)
64
120
Iterations (thousands)
Figure 4: Comparison between jz-FigenGame and a-EigenGamme with different degrees of data parallelism (in parentheses) the Meena dataset.
Tigure44comppe the mean performance of j-EigenGame against a-EiggnGaame as a function of the degree of parallelism in computing the top k = 256 eigenvectors (standard errors computed over 5 random seeds). Each TPU is tasked with learning 32 contiguous eigenvectors. We see that increasing the degree of parallelism has effect on the performance of a-FigenGamee As expected, it is unable to take advantage of the higher data throughput since its updates are biased and cannot be meaningfully linearly combined across copies. contrast, the performance of u-EigenGame scales with the effective batch size achieved through parallelism. j--EigenGame (8x) is able to recover 256 eigenvectors less than 40,000 iterations 2 hours 45 minutes (approximately 0.5 epochs).
Spectral clustering on graphs. We conducted experiment on learning the eigenvectors of the graph Laplacian of a social network graph (Leskovec and McAuley) 2012) for the purpose spectral clustering. The eigenvalues of the graph Laplacian reveal several interesting properties as well such as the number connected components, an approximation to the sparsest cut, and the diameter of a connected graph (Chung et al. 1994).
Given a graph with a set of nodes and set of edges E, the graph Laplacian can be written as - X where each row of the incidence matrix E | represents a distinct edge; (e=(i,)) is a vector containing only 2 nonzero entries, 1 at index i and -1 at index j (Horaud 2009). In this setting, the eigenvectors of primary interest are the bottom-k (dyy), Åpr)- rather than the top-k )2..)..... however, a simple algebraic manipulation allows
reuse top-
solver. By defining the matrix -- = X L with X > \1 we ensure L > and the top-k eigenvectors of L are the bottom-k of L. The update in equation (4) is transformed into Ej<r (0, (X*I L) éz. We provide efficient pseudo-code in Appendix G D/ (X*I L)
The Facebook graph consists of 134, 833 nodes, 380, 293 edges, and 8 connected components, each formed by a set of Facebook pages belonging to a distinct category, e.g., Government, TV shows, etc. [Leskovec and Krevl 2014 Rozemberczki et al. 2019). We add single edge between every pair of components to create a connected graph. By projecting this graph onto the bottom [E] eigenvectors of the graph Laplacian using μ-EG (M 1, n' Q 1000 ) and then running k-means clustering (Pedregosa et al. 201T]. we are able to recover the ground truth clusters (see Figure (5) with 99.92% accuracy. The experiment was run on single CPU.
6 DISCUSSION
6.1 UTILITIES TO UPDATES AND BACK
summarizes the relationships advising the designs of the various EigenGame algorithms. Starting from the a- a-EiienGame utility, its update arrived at by simply following the standard gradient ascent paradigm. In noticing that stochastic estimates of the gradient are biased, arrive at the ya-EigenGame update by considering how to remove this bias in a principled manner.
Figure 5b
Sacrificing the exact steepest decent direction for direction that allows unbiased estimates is tradcoff that in this case has benefits. Also, while V.r is not gradient (except with exact parents), the new penalties have properties (above) that make them intuitively more desirable than the originals; they adaptive the state of the system (discussed further in section H.2
8

---

Published as a conference paper at ICLR 2022
Approx. Eigencelues (ry @ Bottom)
10-3
Var & Allign
10-4
remove bias
50 100
150
200
lterations (Enousands))
(b)
(5a) Facebook Page Networks. (Left) Petals differentiate ground truth clusters; colors differentiate learned clusters. Petals are ideally colored according to the color bar starting with the rightmost petal and proceeding counterclockwise Numbers indicate ground truth cluster size. g|
Figure 5:
Clusters are extracted by running k-means clustering on the learned cigenvectors (samples on rows). (Right) Rayleigh quotient plot reveals gap between the 8th and 9th eigenvalues indicating = 8 clusters exist. (5b) Relationships between utilities and updates. An arrow indicates the endpoint is reasonably derived from the origin; the lack of an arrow indicates the direction unlikely.
We derive pseudo-utilities with desired theoretical properties by integrating the new updates with help from the stop gradient operator. However, it is unlikely that this utility would be developed independently of these steps to solve the problem at hand (see Appendix for for more details). This suggests alternative approach algorithm design complementary to the optimization perspective: directly designing updates themselves which converge to the desired solution, reminiscent of previous paradigms that drove neuro-inspired learning rules.
6.2 BRIDGING HEBBIAN AND OPTIMIZATION APPROACHES
The Generalized Hebbian Algorithm (GHA) (Sanger 1989 Gang al. 2019 Chen et al. 2019) update direction for 0; with inexact parents Ün is similar to μ- EigeenGame:
A ghe = Ci: Σ ( Co2)
C' appears linearly in this update so GHA can also be parallelized. In contrast to y-EigenGame,, GHA additionally penalizes the alignment of i; to itself and removes the unit norm constraint on é; (not shown). Without any constraints, GHA overflows in experiments. We take the approach of Gemp et al. 2021 and constrain ú; to the unit-ball (|@::| < 1) rather than the unit-sphere (||ō:|| 1).
The connection between GHA and j--igenGamme is interesting because unlike y-FigenGame, GHA is a Hebbian learning algorithm inspired by neuroscience and its update rule not motivated from the perspective maximizing of a utility function. Game formulations of classical machine learning problems may provide bridge between statistical and biologically inspired viewpoints.
7 CONCLUSION
We introduced p-aieddp--iie p-EigenGame, an unbiased, globally convergent, parallelizable algorithm that recovers the top-k eigenvectors of a symmetric positive definite matrix. We demonstrated the performance of μ- H-EiignGamme on large scale dimension reduction and clustering problems. We discussed technical details of p gaEe within the context game theory, machine learning and neuroscience.
Like its predecessor, JaFeienGGame is k-player, general-sum game allowing model parallelism over players; our unbiased reformulation allows even greater parallelism over data. Furthermore, the hierarchy and Nash property enable the exploration of more sophisticated best responses.
u-EigenGame's ' improved robustness to smaller minibatches makes it more amenable to being used as part of deep learning, optimization (Krummenacher et al.) (0166), and regularization (Miyato et al. 2018) techniques which leverage spectral information of gradient covariances or Hessians. Graph spectral methods have also recently shown be related to state-of-the ofe-the-rtt representation learning algorithms (HaoChen et al.) (02I)) further cementing the importance of efficient SVD algorithms in modern machine learning.

---

Published as a conference paper at ICLR 2022
Acknowledgements. We would like to thank Trevor Cai, Rosalia Schneider, Dimitrios Vytiniotis for invaluable help with optimizing algorithm performance on TPU. We also thank Maribeth Rauh, Zonglin Li, Daniel Adiwardana and the Meena team for providing with data and assistance. And finally, we thank Alexander Novikov for helpful feedback on the manuseript.
REFERENCES
P.-. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009.
D. Adiwardana, M.-T. Luong, D. R. So, J. Hall, N. Fiedel, R. Thoppilan, Z. Yang, A. Kul- shreshtha, G. Nemade, Lu, et al. Towards a human-like open-domain chatbot. arXiv preprint arXiv:2001.00 099:97701.09977,, 2020.
Z. Allen-Zhu and Y. 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), pages 487-492. IEEE, 2017.
R. W. Brockett. Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems. Linear Algebra and its applications, 146:79-91, 01,799911111 1991.
Z. Chen, X. Li, L. Yang. J. Haupt, and T. Zhao. On constrained nonconvex stochastic optimization:
A case study for generalized eigenvalue decomposition. In The 22nd International Conference Artificial Intelligence and Statistics, pages 916-925. PMLR, 2019.
F. R. Chung, V. Faber, and T. A. Manteuffel. An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian. SIAM Journal Discrete Mathematics, 7(3)443-457, 1994.
M. B. Cohen, C. Musco, and C. Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Eventy-Eighttf Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1758-1777. SIAM, 2017.
P. S. Dhillon, D. P. Foster, S. M. Kakade, and L. H. Ungar. A risk comparison of ordinary least squares ridge regression. The Journal of Machine Learning Research, 14()):1505-1511 2013.
A. Durmus, Jiménez, É. Moulines, Said, and H.-T. Wai. Convergence analysis of Riemannian stochastic approximation schemes. arXiv preprint arXiv:2005. 3284, 2020.
J. Fan, D. Wang. K. Wang. and Z. Zhu. Distributed estimation of principal eigenspaces. Annals of statistics, 47603309, 2019.
D. Feldman, M. Schmidt, and C. Sohler. Turning big data into tiny data: Constant-sizi coresets for k-means, PCA, and projective clustering, SIAM Journal on Computing, 49(3):601-657, 2020.
A. Gang, H. Raja, and W. U. Bajwa. Fast and Communication-efficcee distributed PCA. In ICASSP 2019-2019 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7450-7454. IEEE, 2019.
D. Garber, O. Shamir, and N. Srebro. Communication-effiiin algorithms for distributed stochastic principal component analysis. In International Conference on Machine Learning, pages 1203-1212. PMLR, 2017.
I. Gemp, B. McWilliams, C. Vernade, and T. Graepel. Eigengame: PCA Nash equilibrium. In International Conference for Learning Representations, 2021.
M. Ghashami, E. Liberty, J. M. Phillips, and D. Woodruff. Frequent directions: simple and deterministic matrix sketching. SIAM Journal on Computing, 4565):172 2016.
G. H. Golub and H. A. Van der Vorst. Eigenvalue computation in the 20th century. Journal of Computational and Applied Mathematics, 23(112):35-65 2000.
A. Haidar, K. Kabir, D. Fayad, S. Tomov, and J. Dongarra. Out of memory SVD solver for big data. In 2017 IEEF High Performance Extreme Computing Conference (HPEC), pages 1-7. IEFE, 2017.
10

---

Published as a conference paper at ICLR 2022
N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217-288, 2011.
HaoChen, C. Wei, A. Gaidon, and T. Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. arXiv preprint arXiv:2106.0411 2021.
M. Hessel, D. Budden, E. Viola, M. Rosca, E. Sezener, and Hennigan. Optax: composable gradient transformation and optimisation, in JAX!, 2020.
R. Horaud. short tutorial on graph Laplacians, Laplacian embedding. and spectral clustering. 2009.
I. T. Jolliffe. Principal components in regression analysis. In Principal Component Analysis. Springer, 2002.
R. Kannan and S. Vempala. Spectral algorithms. Now Publishers Inc, 2009.
G. Krummenacher, B. McWilliams, Y. Kilcher, J. M. Buhmann, and N. Meinshausen. Scalable adaptive stochastic optimization using random projections. In Advances in Neural Information Processing Systems, pages 1750-1758, 2016.
Leskovec and A. Krevi. SNAP Datasets: Stanford large network dataset collection. http: //smap.stanform edu / June 2014.
Leskovec and McAuley. Learning to discover social circles in ego networks. Advances Neural Information Processing Systems, 25:539-547, 2012.
Y. Liang. M.-F. Balcan, V. Kanchanapally, and D. P. Woodruff. Improved distributed principal component analysis. In NIPS, 2014.
A. Mead. Review of the development of multidimensional scaling methods. Journal of the Royal Statistical Society: Series D (The Statistician), 41(1):27-39, 1992.
T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: /802.0555, 2018.
C. Musco and C. Musco. Randomized block Krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems, 2015.
E. Oja. Simplified neuron model as principal component analyzer. Journal of Mathematical Biology, 15(3):267-273, 1982.
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Scikit-learn; Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830. 2011.
S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding, Science, 290,55000:2333-2322, 2000.
B. Rozemberezki, R. Davies, R. Sarkar, and C. Sutton. Gemsec: Graph embedding with self clustering. In Proceedings of the 2019 IEEE/ACM International Conference on Advances Social Networks Analysis and Mining 2019, pages 65-72. ACM, 2019.
H. Rutishauser. Simultaneous iteration method for symmetric matrices. In Handbook for Automatic Computation, pages 284-302. Springer. 1971.
T. D. Sanger. Optimal unsupervised learning in a single-layer linear feedforward neural network. Neural Networks, 2(6):4594473 1989.
T. Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Anmual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 143-152. IEEE, 2006.
11

---

Published as a conference paper at ICLR 2022
S. M. Shah. Stochastic approximation Riemannian manifolds. Applied Mathematics & Optimiza- tion, pages 1-29, 2019.
O. Shamir. A stochastic PCA and SVD algorithm with an exponential convergence rate. In Proceed- ings of the International Conference on Machine Learning, pages 144-152, 2015.
C. Tang. Exponentially convergent stochastic k-PCA without variance reduction. In Advances in Neural Information Processing Systems, pages 12393-12404, 2019.
J. B. Tenenbaum, V. De Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 29065500)2319-2223,, 2000.
U. Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395-41, 2007.
Y. Wang, N. Xiu, and J. Han. On cone of nonsymmetric positive semidefinite matrices. Linear Algebra and its Applications, 433(4):718- 2010.
12

---

Published as a conference paper at ICLR 2022
A EXPERIMENTS ON SYNTHETIC DATA
Linearly Decaying Spectrum
Exponentially Decaying Spectrum
Eigenvector Streak
Ojas (407)
o:EG (323)
Eigenvector Streak
Ojas (306)
Longest Correct
Longest Correct
40
40
(268)
GHV (214)
GHA (192)
20
20
Krasulinas (288)
Krasulinas (271)
200
400
800
1000
0
200
400
600
800
1000
# Training lterations
of Training Iterations
Figure 6: Synthetic Experiment. Runtime (milliseconds) in legend.
We validate u-EigenGame in full-batch setting on two synthetic datasets: one with exponentially decaying spectrum; the other with a linearly decaying spectrum. Figure [ shows p-EigenGame outperforms G-EigenGame on the former and matches its performance on the latter. We discuss possible reasons for this gap in the discussion in Section 6
B PARALLELIZED ALGORITHM
Riemannian Manifolds. Before introducing an algorithm for p-EigenGamee, we first briefly review necessary terminology for learning on Riemannian manifolds [Absil er al. (2009). specifically for the sphere. The notation Te denotes the set of vectors tangent to the sphere at point é (i.e., any vector orthogonal to 0z). Rs, (2) = ect.s
is the commonly used restriction of the retraction on
||6++e||
S to the tangent bundle at 0g (i.e., step in tangent direction & and then unit-normalize the result).
The operator IIg (v) = (I 6, 0g)y projects the direction y onto Te, Sd-1, Combining these tools
together results in a movement along the Riemannian manifold: af (((+1) < Rs, (v))
We present pseudocode for j-EigenGame below where computation is parallelized both over the k players and over M machines per player.
Algorithm 2 ju- Ra-migenGame
1: Given: data stream X, 12n xd number of parallel machines M per player (minibatch size per machine n" 37 initial vectors of 8d-1, step size sequence Wts and number of iterations T.
2: 6 < 6 for all
3: 1: do
4: parfor 1 do
5: parfor m = 1: M do
6:
rewards +- X Xemú;
7:
penalties + Eje (Xem X G3)0
8:
au in F..
+ (rewards
Stenaltin ies)
9:
p im
( am 0:
im
10:
end parfor
11:
Σ m im
R
M
12:
6. 03
1/
V.l.
13:
Q + [
end parfor
15: end for
return all 0
13

---

Published as a conference paper at ICLR 2022
C GLOBAL STOCHASTIC CONVERGENCE
Theorem Gllobal Convergence), Given a positive definite covariance matrix C with the top-k eigen- gaps positive and a square-summabbee not summable step size sequence тy (e.g., g., 1/t), Algorithm 1 converges to the top-k eigenvectors asymptotically (limT=+0e) with probability 1.
Proof. Assume none of the ig are initialized to an angle exactly 90º away from the true eigenvector: (0,, U1) # O. The set of vectors {6, (0,, v.) 0} has Lebesgue measure O, therefore, the above assumption holds w.p.1. The update direction for the top eigenvector ú1 is exactly equal to that of a-EiienGame (V = Vi), therefore, they have the same limit points for 81. The proof then proceeds by induction. As <i approach their limit points, the update for the ith eigenvector éG approaches that of a-EigenGame (V Vit and, by Lemma the stable region of u-EigenGame also shrinks to point around the top-k eigenvectors.
Denote the "update field" H (v) match the work of Shah 2219). H (v) is simply the concatenation of all players' Riemannian update rules, i.e., all players updating in parallel using their Riemannian updates:
H(v)= = - -166, )4 (I 6g )
Red
R.
(10)
where A is defined in equation 7 and (1 1PPPPPP ) projects A onto the tangent space of player i's unit sphere.
The result is then obtained by applying Theorem 7 of Shah (2019) with the following information: a) the unit-sphere is a compact manifold with an injectivity radius of æ, b) the update field is polynomial in { and therefore smooth (analytic), and c) by Lemma (see Appendix the update noise constitutes a bounded martingale difference sequence.
While the convergence proof for a-EG provides finite-sample rates, it only applies to the algorithm applied sequentially (not parallelized over eigenvectors) and in the deterministic setting (minibatch contains the entire data set). The experiments in Gemp el al. (202T) apply the algorithm in parallel and with mini batch sizes, meaning the a-EG theorem does not actually apply to their experimental setting. That
say, the a-EG paper proposes updating eigenvectors parallel in practice despite the lack of convergence guarantee.
In contrast, our convergence theorem applies to μ-EG when applied in parallel (over the eigenvectors) and in the stochastic setting (with mini batch sizes), which is what we examine empirically in our experiments. The downside is that we not provide finite-sample convergence rates.
Although we do not provide convergence rates, Lemma proves that the μ-EG update converges to the a-EG update for each eigenvector, so intuitively, we expect the convergence rates to be relatively similar given that the algorithms are equivalent in the limit. Note that in the full batch setting where stochasticity does not conflate the differences between the two algorithms, Figure in Appendix A empirically supports the similarity of the convergence rates for the two algorithms. Figure 3 (minibatch of 1024) which looks at a large (but not full) minibatch size, also shows a small difference between convergence for the two algorithms.
In summary, the a-EG convergence theorem is impractical- it provides convergence rates for a (non-parallel) algorithm in the (non-stochastic) setting, which is combination that a-EG paper does not suggest be applied in practice. In contrast, our fi-EG convergence theorem is practical-in provides asymptotic convergence for parallel algorithm in the stochastic setting.
Difficulties Obtaining Finite Sample Rates In consideration of a finite sample convergence result, we consulted Durmus et al. (220)). The primary obstacle to applying their convergence theorem is the construction of suitable Lyapunov function to satisfy their Assumption A.2 stated on page 4. Constructing Lyapunov functions is typically a tedious, unpredictable process. The work in Durmus et al. (2020) is very recent and finite sample convergence of Riemannian stochastic approximation (i.e., update directions are not gradients of any function) schemes is cutting edge, highly technical research. This is in contrast to Riemannian optimization (i.e., update directions the gradient of function), which is much more mature. We hope theory advances in the near future to a point where can more easily provide convergence rates for algorithms like o-FigenGamme
14

---

Published as a conference paper at ICLR 2022
D ERROR PROPAGATION / SENSITIVITY ANALYSIS
Lemma 3. An (c)) angular error of parent 0zzi implies an (c)) angular error in the location of the solution for iz
Proof. The proof proceeds in three steps:
1. (cc angular error of parent = (c) Euclidean error of parent
2. (c)) Fuclidean error of parent
(e) Euclidean error of norm of child gradient
3. (c)) Euclidean error of norm child gradient + instability of minimum at =
(
angular error of child's solution.
Angular error in the parent can be converted to Euclidean error by considering the chord length between the mis-specified parent and the true parent direction. The two vectors plus the chord form an isoceles triangle with the relation that chord length / = 2 sin }) is (c)) for c <
Next, write the mis mnesiiee parents as ê Uy + wy where ||y| is O(e) Let equal the difference between the Riemannian update direction V with approximate parents and that with exact parents. All directions we consider here are the Riemannian directions, i.c., they have been projected onto the tangent space of the sphere. Then
have just shown.
Σ
Co;)6) (6) Cuz)us
(11)
projection onto sphere jái
and the norm of the difference is
(12)
||a|| = 11(7 - 6,07) Σ
(0. Cht) (07 Cvy) II
(13)
JZ6
< ||/ -,0%% 11 -1- Σ (oTC) (6)7 Cus)os ||
(14)
j<i
< (0) Cūj)0; - (6, (,,T Cr.)os
(15)
jsi
We can further bound the summands with
I1(0 Cε,)E, (o) Cuy)oy) = 11(0,0] - 0j0, Cbal
(16)
$ 110,00 -20, |II
(17)
S Aelll,Ø - u
(18)
= =Ail(1; + w;) wyy) u30
(19)
= -Allww,, + t + www II
(20)
S A1 + [1a/e]] || + [mmmm
(21)
= O(e).
(22)
This upper bound on the norm of the difference between the two directions translates lower bound on the inner product of the two directions wherever [| specifically (Vu.s, V (see Figure 7ap. And recall that the direction with exact parents is equivalent to the gradient of a-FigenGame with exact parents, V
Therefore, by a Lyapumov argument, the T direction is an ascent direction on the a-EigenGame utility where it forms acute angle (positive inner product) with V.... Furthermore, V is the gradient of a utility function that is sinusoidal along the sphere manifold; specifically, it is cosine with period and positive amplitude dependent on the spectrum of C (c.f. equation (8) of Gemp
15

---

Published as a conference paper at ICLR 2022
O(e)
V
V, (a)
repellrr
repeller
(b)
Figure 7: a
Close in Euclidean distance can imply close in angular distance if the vectors are long The stable region for y-EigenGame consists an (e)) (ee) ball around the true optimum as
enough. -
0.
et al. 20221) ) We can derive an upper bound the size of the angular region for which V is not necessarly an ascent direction (the "?" marks in Figure 7 This region is defined as the set of angles for which the norm of the utility's 'ss derivative is small, i.e., Vo S c. The derivative of cosine is sine, which depends linearly on its argument (angle) for small values, therefore, |0] < O(e) or 15 0| S O(e). As long as ú; does not lie within the _ O(e) region, p-FigenGamm will ascend the utility landscape to within (c)) angular error of the true eigenvector 14 In the limit as e + 0, the size the 5 (e)) region vanishes
point, ozt. To understand the stability of this point, -see
can again appeal to the analysis from Gemp ef al. (202T) see equation (8) on page 7 of that work. The Jacobian of V and the Hessian of ut are equal with exact parents, and we know that its Riemannian Hessian is positive definite the ith eigengap positive: H. [u.] č (A+ A+11). This means that the point of is repeller for a-EigenGame. Similarly to before, we can show more formally that an (c)) perturbation parents results in (e)) perturbation to the Jacobian of V/ from H [[{]]
J=
Σ
0,0
(23)
jái
[I Σ
(u, + wy)(U, + w
(24)
jai
11 Σ CojuJCC- IlwjuJ + tjje + w.wwiC
(25)
jái
jzi
[ Σ
S -(())
(26)
JA
Huf O())W
(27)
where W is some matrix with ((1) entries (w.rt. <). For the sphere, the Riemannian Jacobian is linear function of the Jacobian (J therefore the error remains O(e). The set of (non)symmetric, positive semidefinite matrices (AA is p.s.d. iff y Ay > 0 V y) forms a closed convex cone, the interior of which contains positive definite matrices Wang et al. (2010). Therefore, J remains in this set after small enough (cc) perturbation. Therefore, in the limit - O, the spectrum the Jacobian will also be positive definite indicating the point e. is repeller. This is indicated by the blue arrows in Figure 7b
6,6, )J (6, Jé.) = " O(e)) and
Figure 7b summarizes the results that the stable region for a- E-EiienGame consists of an O(e) ball around the true optimum for parents with O(c) angular error.
16

---

Published as a conference paper at ICLR 2022
E NOISE IS MARTINGALE DIFFERENCE SEQUENCE
Let A = - I- 1900 Cill be the ju-EigenGame update direction computed using the full expected covariance matrix. Let A I- Eイe 05 Dj
( C,ol") be the update direction
computed using a minibatch estimate of the covariance matrix where minibatches are unbiased because they formed from data sampled uniformly random from the dataset. Define M
ÁN A and let M [M [ML.4....,MM.4.
M J where V (9) (
Lemma 4. (MHL) } is a bounded martingale difference sequence with respect to the increasing a-fields
F. = =[[((((() ..... (6)
10 )..,)
(28)
Proof.
Given the filtration Fe, we find
vin B 1M44+12 FF = 1
Σ
T T
B|C, SJC,-C90f -00 =0
(29)
where the first equality holds because each C. is formed from a minibatch sampled i.i.d. from the dataset and therefore independent of the filtration. This result holds for all i E [k], therefore
E[MH V
[ = =0
(30)
Furthermore,
sup B|II [2
(31)
PT
P
dins OTT (C, (C,-C) 1
o of (U)
(C, -
F.
(32)
- Laaaaa (C, C) -)) Va (T) (C, C) [)
PT P(C,- - C)a Frl
(33)
(34)
Ao (T) E[(C, - T TC, - FF)
(35)
$ mmxf1, (1 2
(36)
where < max (1, (i 2)²} is the max singular value of / E[(C, T - -C)] over all t. Summing over we find
F Fand g² is the maximum eigenvalue of
dhs 11 <
x)
(37)
k-2
$ (2 + Σ a²)c²
(38)
= (2 + 6
(k: 2)(k - 1)(2k -
(39)
$ (2 + 23
(40)
3
'In the worst case, each subspace subtracted off by 0y67 subtracts a 1 from the eigenvalue of 1 of the identity matrix.
17

---

Published as a conference paper at ICLR 2022
This is worst bound. As the parent eigenvectors converge, the max singular value of P converges to 1 so that the variance of the magnitude of the martingale difference is upper bounded by kg?.
Note: For a finite dataset of n samples or for a distribution with bounded moments like the Gaussian distribution, will be finite. However, for other distributions like the Cauchy distribution, may be unbounded, so care should be taken when running Ja-iggeGGame in different stochastic settings.
F JAX PSEUDOCODE
For the sake of reproducibility we have included pseudocode Jax. We use the Optax optimiza- tion library Hessel et al. (2020) and the Jaxline training framework Our graph algorithm is straightforward modification the provided pseudo-code. See section for details.
***
Copyright 2020 The EigenGame Unlcaded Authors.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain copy of the License at
https://www.apatt www.:/...chhe..//1/....o /tt.ppaca....o.ooasss/s/aaaaaaaa cecsss//
10
11 Unless required by applicable law or agreed to in writing, software
12 distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS
ANY KIND, either express implied. 14 See the License for the specific language governing permissions and
15 limitations under the License.
16
18 import jax
19 import optax
20
import jax.numpy as jnp
def egagrads (vi: inp indaray,,
23
weights: jup.ndarray,
24
eigs: jng.ndarray
25
data: jdarrayrray) -> inp.rdarray:
Args:
28
vi: shape (d,), eigenvector to updated
29
weights: shape (k,), mask for penalty coefficients,
30
cigs: shape (k, d), i.e., vecters on rows
data: shape (N, d), minibatch x_t
32
Returns:
33
grads: shape (d,), gradient for
14
weights_ij - (jnp. sign (weights 0.5) 1.) / 2. maps -1 to -1 else to 0
36
data vi dot (data, vi)
37
data eigs transpoee (jnp. dot (data, jnp. tra.sranspose ( 4 Xvj on row vi_m_vj jnp. dot (data_eigs, data_vi)
38
40
penalty_grads vi_m_vj tnp.transpose (eigs)
41
penalty_grade inp. dot ipenalty_gradeee weights_ij)
grads = dot (jnp. hhpp.transposs (data), data_vi) + penalty_grads 42
return grads
45
16
def utility(vi, weights, eigs, data):
cot.://p.oom///mmm////// nd/ /pppppax
httpps://gi thu.. com www/deepmiiiioooooemoeeeeee.m.ea nd/ jax ine
18

---

Published as a conference paper at ICLR 2022
Computt Eigengame utilities.
48
util: shape (1,), utility for vi
49
=**
90
data_vi = jnp. dot (data, vi)
data_eigs jnp. transpoe (jnp det (data, jnp. tra.spose (eigs))) (eigs))) Xvj
row
52
vi_m_vj2 jnp.dot idata_eigs, d
53
vi_m_vj = jap.sum (data_eigs data_eigs, axis=1)
54
r_ij vi_m_vj2 / vi
util inp, dot array (r ii), weights)
56
return util
Listing I: Gradient and utility functions.
def _gradis_an__udatee weights, eigs, input, opt_state, betss_ndde_ggeeoe
"*"Compute utilities and update directions, psum and apply. Args:
vi: shape (d,), eigenvecter be updated
weights: shape (k_per_device, k,), mask for penalty coefficients, eigs: shape (k, d), i.e., vectors on rows
input: shape (N, d), minibatch X_t.
opt_state: optax state axis_index_grone
For multi-host parallelisn https://jax, httddatetos..bbee//attee//////ee jardules/ja///ee srt/sr//aaaa wttp://wwwpaaalleel///
10
Returns:
vi newn shape (d,), eigenvector to be updated opt_state: new optax state
13
utilities: shape (1,), utilities ***
14
15
grads, utilities = grads_and_utille avg_grads jax. lax. psum
weights, V, input)
16
grads, axis n'
18
vi_nww ept_state, ir return vi_new, opt_state, utilities
(vi, avg_grads, opt_state)
19
20
def ggrads_and_utiinng
weights, v, inputs): ** "omppute utiltiies and update ricections ("grads").
23
wrap in jax. for k_per_device dimension.
24
utilities = utility(vi, weights, V, inputs)
grads = eg grads (vi, weights, V, inputs) return grads, utilities
27
28
dof _updatc_with__rrad (vi, grads, opt_state):
29
"*"Compute and apply updatcs with optax optimizer.
Wrap in vmap for k_per_device dimension. updates, opt_state self._optimizer.. update (-grads, opt_state) vi_new
32
(vi, updates) vi_new /- www.liinng.....vv......... return new, opt opt_state
33
34
Listing EigenGame Update functions.
def init (self, +):
"""nitialiiatton function for Jaxline experiment. "un
weights ep.eye (self. _total_k))
on.ones ((seff self.
weights (np.
inpiiriiiindiees indices (self._total__ k, felf._weights inp. reshape (weights,
1)] = 0.
[self werff_nun__eee deviced, self feff__k_per_devee device, self._totallk])
local_rny rng jax. random. fold www.de....noeenneeeeeeeoooo fa.. hdst_id
()) keys jax, random. split (local __rgg, faf.f__umdevvieee
19

---

Published as a conference paper at ICLR 2022
= jax paaappmappppm (ambda key: jax. random. normal (key, (self. per device, self (elfs_dims)) (keys)
12
self._V pax.pmap (lambda V: V cop.linaag.neen norm (V, axis=1, keepdims- Truc)] (V)
Define parallel update functien. If k_per_device is not None, wrap individual functions with vmap here.
15
self gar.._ppatiaa__gaa__pooooo
sunctools.partiall
16
larrrads_and_upaattt axis_groups=selt..o axis
self selt._par_grad update jax.pmap(
18
_elf axis_name-
in_axes- (0, None, 0, 0),
19
selt._ = eetax.sge
momentum=0.9,
nesterov=Irue)
21
22
def stepfsclf, *);
23
"**Stcp function for a Jaxline experiment"""
inputs next (input_data_itcrattte
self._local_" jnp. reshape (self._V, (self._total) self._dimp self._V, _elf._oot_statee utilities, self._par__e perf.__arrgradduuddtte self._V, sel self._weights_ing self._local_W, inputs, self. opt_state,
26
27
[lobal_step)
Listing 3: Skeleton for Jaxline experiment.
G J--IIGENGAME ON GRAPHS
Algorithm 3 receives stream of edges represented outgoing node id (out) and incoming node id (in) as nonegative integers on the columns. The method veros_like(s
matrix with edges the rows and
returns array of zeros with the same dimensions as z. The method index index_add( idæ, val) adds the values in array val to 2 at the corresponding indices in array idr with threadsafe locking that indices in idr may be duplicated. Both methods are available in JAx. The largest cigenvector új is learned to estimate Å₁ and may be discarded. The bottom-k cigenvectors are returned by the algorithm in increasing order. A expects k + random unit vectors as input rather than l: in order to additionally estimate the top eigenvector necessary for the computation; otherwise, the inputs are the same as Algorithm
H ALGORITHM DESIGN PROCESS
In section 4.1
we presented v/ as the Rayleigh quotient a deflated matrix (repeated in equation for convencience):
deflation
0
C
[0
(41)
jJi
of C
[0.]
Ci,) (.)o)))))
(42)
1-penalty
Var
(o,, Co,)
u
(43)
(0), Cii))
Alternatively, we can consider uf as equation 42 in light of the derivation for uf by Gemp et al. (2021). In that case, utilities constructed from entries in the matrix
20

---

Published as a conference paper at ICLR 2022
Algorithm 3 ju- Ju-EigenGame for Graphs (w/o Riemannian gradient projection)
1: Given: Edge stream & E R number of parallel machines M per player (minibatch size per
partition n² n/). initial vectors of E Sd-1, step size sequence 7/i and iterations T.
2: 6 < 0, for all E (I,..., 1}
3: A1 < 2/ uupper bound on top eigenvalue*
4: for ::: do
5: parfor =
k + do
6:
parfor m = M do
7:
Xcc 0, (outem)) (inem)
8:
X X + zeros_like (0:
9:
XTxul; iinde__ddoor X Xx) out [Xel;)
10:
X Xul; f- inddin add( Xx). inm.: - [(o)s)
11:
if then
12:
A + ||
13:
VH X Xul
else
15:
V mn - \1 - Ei<jet (0, 0z)
16:
[el (y(outem) (inem) for all
V [X Xuli Eiejes ([Xo] (X
18:
end if
19:
end parfor
20:
Σn (
21:
6 0; + m7 Vi
22:
0 - :I
23:
end parfor
24:
end for
25: return (ūsli {2, . 1}}
ú1, Cot)
(0,, C(i))
( Cüa) (2 Chal
(i2 Coty
(i2, Cop
vVC==
(44)
(0a, Coi)
(0a, C(2))
(Ua, Coa)
It is argued that if V. diagonalizes M and captures maximum variance, then the diagonal (6:, Cii)) terms must maximized and the off-diagonal (6g, Cūt) terms must be zero. As the latter mixed terms may be negative, the authors square the mixed terms form "minimizable utilities" and divide them by (ey, Cit) so that they have similar "units" " to the terms (b,, Cli;) of the first type. In contrast, the u. utilities could be arrived at by instead multiplying the mixed terms by (6e, 0z)- While this ensures the mixed terms are positive with exact parents (because (0;, Cuty) = (0z. u2)), ), does not ensure they are always positive in genera(" In other words, u.t is defined in way such that the L-penalties actually encourage vectors align at times when they should in fact do the opposite! We therefore consider it unlikely that anyone would pose equation (42 as utility if coming from the perspective of a-FigenGame.
We could have extended the diagram in Figure 55 include this dead end link. We have also included the true gradient of ue logical endpoint. We present these extensions in Figure
2 1
e..g. let C
and place in -0 and 02 90".
21

---

Published as a conference paper at ICLR 2022
Eq. 42
Var & 1
remove
bias
Figure 8: This diagram presents the relationships between utilities and updates. An arrow indicates the endpoint is reasonably derived from the origin; the lack of an arrow indicates the direction is unlikely. The link from equation (42) explicitly crossed out with a hard stop for emphasis.
H.1 GRADIENT ASCENT ON u!:
we remove the stop gradient from equation we are left with equation 45
deflation
u
0.
Co..
(45)
JJB
If we then differentiate this utility, we find its gradient is
V Cb:
E [CTTCaje + (6, C,)])
(46)
We also reran experiments with this update direction, V on the synthetic and MNIST domains. The update is unbiased, so it would be expected to scale well, however, it (in orange) appears to scale more poorly than j-EigenGame with smaller minibatches.
Exponentially Decaying Spectrum
Linearly Decaying Spectrum
Longest Correct
Eigenvector Streak
40
(268)
Longest Correct
Eigenvector Streak
40
PEG (299)
(323)
(PEG (519)
L-FG 1281
P-E6 [374]
20
20
200 400
600
800
1000
0
200
400 600
800
1000
of Training Iterations
of Training Iterations
Figure 9: Synthetic Experiment. Runtime (milliseconds) in legend.
jiEG appears converge terms of subspace error but slows in terms of longest eigenvector streak. ji-EG updates are also unbiased so we would expect it is convergent globally, but underperforms relative to J-EG. In contrast, o-EG stalls terms of subspace error likely due to bias.
In Figure 10
Note that with exact parents, mu-EG and mu-tilde-BG have the same update (plug Cuj = Ayvÿ into equation (46)). so the difference must come from when the parents are still inaccurate.
In Figure we have plotted the norm of the difference between subsequent values of the eigenvectors over training. i.c., how "far" v, moves after every update. Note all algorithms were run with the same fixed step size of 10-3, which was optimal for each algorithm this setting. Clearly, the gradient version of a-EigenGame (fiEG) shown in Figure TIc exhibits higher norms overall.
We believe this due to the higher variance penalty terms (all methods maximize the same Rayleigh quotient term). Note that both a-EG and μ-EG construct their pentalty directions by weighted sum of terms. These terms are computed differently, but both compute weights with inner products between v; and vú after projecting onto the samples in the minibatch X,. For example, f-EG
22

---

Published as a conference paper at ICLR 2022
Subspace Distance Langest Correct
Eigenvecior Streak
26
MNIST (Minibatch 1024)
Subspace Distance Langesi Correct
Eigenivecoor Streak
26
MNIST (Minioatch 256)
Longest Correct
Elgerivector Streak
-6
MNIST (Minibatch - 32)
E
(43
(2740)
8-
8-
PEE (253)
(291)
10a
10a
Subspace Distance
10
GEG (223)
10-2
10-2
10
(46)
WEG (42)
I80 12/41
0
10
20
30
40
10
20
30
40
0
10
20
30
40
50
Epochs
Epochs
Epochs
58
117
117
234
351
468
937
1675 2812 3750 4687
Iterationn (thousands)
Iterations (thousands]
Iterations (thousands)
Figure 10: MNIST Experiment, Runtime (seconds) in legend. Each column evaluates a different minibatch size E (1024, 32).
computes (Xte,, X2,,) = v.a Ceuy. Without loss of generality, assume C' is a diagonal matrix (with the eigenvalues on its diagonal). Then (u, Cuy) Ex Us The eigenvectors v; e; in this case, and so the inner product measures alignment between o; and vy in the dimensions that i and By are trained to be orthogonal. Due to noise in the minibatches Xt, U/ and v may "drift" in the remaining dimensions. Projecting essentially ignores these though because they are weighted by small eigenvalues.
In contrast, ji-EG computes weights as raw inner products between i/ and By. Therefore, any drift of U and by due to noise in the minibatch samples contributes to the inner product: (0,, ny} = Σx Uag Uzk- We suspect this is the reason fiEEG exhibits higher drift distance.
In summary, o-EG updates are computed as a weighted sum of terms where the weights are computed using inner products between ny and its parents after projecting them to lower dimensional space. Computing the inner product in this particular space results in lower variance for each inner product. Unfortunately, a-EG updates are biased, so while they cxhibit relatively low "norm of drift", they converge to the incorrect solution (parents never converge to precise solution which prohibits children from learning accurately solutions).
jiEG updates are unbiased, they should converge the correct solution in the limit, but they exhibit higher variance due to their penalty weights being computed in the original high dimensional space (i.e., they pick up every little bit of noise).
Finally, f--GG updates are unbiased and compute their penalty weights in a lower dimensional space, suppressing the bulk of the noise that appears from drift caused by randomness in the minibatches. They exhibit the lowest levels of "norm of drift".
Norm of Drift: 6-EG
Nom of Drift: p-5G
Norm of Drift: f AGGG
L35-
1.5
135
120
Epochs
Epochs
Epochi
(a)
(b)
(c)
correspond to j-EigenGame, a-EigenGame, and the gradient version of a- E-EieeGGame discussed above respectively. Each experiment is conducted with a minibatch size of 32 over five epochs of training and averaged over 10 trials. Each curve shows the update distance after each iteration for one of the top-16 eigenvectors. Cyan curves indicate eigenvectors higher in the hierarchy (e.g., f1) ) and magenta curves indicate eigenvectors lower in the hierarchy.
Figure 1I: MNIST Experiment. Subfigures
c
23

---

Published as a conference paper at ICLR 2022
H.2 ACCELERATION
We conjecture that j-EigenGame converges more quickly than a-EigenGame because of the following two claims.
Claim The penalty terms of V are all within 90" of those of V because
CB. Coj 01) = 1 > 0.
Claim The penalty terms of Vi are smaller in magnitude than those V ||,
Cū Co.
Indeed, consider the direction Cūj By properties of the vector rejection, we know the rejection of this direction onto the tangent space of the unit sphere has magnitude less than or equal that of the original vector, ||Cóy]|- The projection is (7 ر (C Therefore, the rejection is ú 0 (Ct,)
and, by the preceding argument, we know its magnitude |0] Cšylll8,|| is less than or equal to || Rearranging the inequality completes the proof.
By Claim 1, the penalty directions of μ-EG and a-EG approximately agree. And by Claim 2, a-EG's penalty direction is shorter. Consider scenario where a parent of i; has not converged and transiently occupies space along 6, 's geodesic its true endpoint Ü; strong penalty term will force 0 to take roundabout trajectory, thereby slowing its convergence. A weaker penalty term allows é; to pass through regions occupied by its parent as long as its parent not an eigenvector. Recall from Section that the two utilities are equivalent when the parents are eigenvectors.
24


Reviews:
[{"review_id": "ts5bMRtg9y8", "reviewer": "Reviewer_Tfdg", "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": "Strengths:\n- the paper is very easy to read, and the challenges and main ideas to address them are very clear. Lemmas 1 and 2 are very simple yet provide good intuition on how to approach the problem. \n- the paper improves on previous work by showing how to do an unbiased update for eigengame, that can be run in parallel. This gets around the challenge from previous work that the update does not decompose cleanly over data partitions, due to non-linearities in the covariance matrix. \n- the author show that SVD is the \\emph{unique} Nash of the game they consider and define. This means there is no equilibrium selection problem, and their approach is guaranteed to find SVD and not another equilibrium.\n- The experiments seem to show that the authors approach does better and coverges faster than previous work when it comes to the longest correct eigenvalue streak. The approach does better than standard Eigengame and not any worse than other approaches in terms of distance between the subspace defined by the true eigenvalues/eigenvectors and the one that is recovered.  \n\nWeaknesses:\n- The main weakness of the paper is that the results are convergence results, and do not deal with finite samples. It might be nice to write down some concentration bounds on how well the authors' approach performs in-sample (though the authors' experiments give some insights as to this)\n- Can the authors say a bit more about how they find an equilibrium, and why do they expect their approach to find one? Computing an equilibrium of general, non 2-player zero-sum games is known to be hard (even if this is only true in the worst-case). Being able to compute best responses is generally a much easier problem than finding their intersection. I was wondering if there was some intuition behind how the authors find one. ", "summary_of_the_paper": "The paper studies \"EigenGame\", which is a game-theoretic approach to eigenvalue decomposition. This paper extends EigenGame to parallel settings; the authors propose an unbiased stochastic update rule to compute eigenvalues of a matrix in parallel, that outperforms previous approaches. ", "summary_of_the_review": "Overall I think this is a novel and interesting contribution, that solves an important problem and provides a framework that improves over previous work.", "strength_and_weaknesses": "", "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": "gtB2CHnh_c1", "reviewer": "Reviewer_JMvM", "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": "Regarding strengths, the authors clearly explain the weakness of the existing $\\alpha$- EigenGame algorithm and update. They also elucidate the core intuition of why their simple yet effective solution works (Lemma 1) and how their approach can be interpreted as a deflation technique commonly used by traditional algorithms for SVD (Equation 7). While these intuitions are probably more than sufficient to deduce that $\\mu$-EigenGame converges in practice, establishing the same results theoretically requires non trivial additional work as showcased in sections C, D and E of the Appendix.\n\nRegarding weaknesses, I agree with the statement of the authors in Appendix H.1 that further research is needed to understand what properties affect convergence rates in practice. It is clear that update bias and data parallelism do not solely determine the empirical convergence rate. Thus I think it would be beneficial to explore more detailed comparisons between the $\\mu$-EigenGame, its variant $\\tilde{\\mu}$ and of course $\\alpha$-EigenGame. For example, maybe the variance of the updates is the core contributor for the low performance of both $\\alpha$-EigenGame and the $\\tilde{\\mu}$-EigenGame for small batch sizes. While this comparison does not change the fact that $\\mu$-EigenGame outperforms the alternatives, it would be beneficial for the community to understand the practical reasons in more detail.  \n\nI have read the author's response. I find that the updated version of Appendix H improves the paper and I would encourage to incorporate elements of it or at least some of the takeaways in the main paper. I remain in favor of acceptance.\n   ", "summary_of_the_paper": "The authors study the problem of finding the top $k$ right singular vectors of a data matrix $X$. They propose a modification of an established game theoretic gradient based algorithm $\\alpha$-EigenGame. They observe that the gradients of $\\alpha$-EigenGame are biased when implemented stochastically by subsampling the data matrix $X$. Their proposed modification guarantees unbiased updates while converging to the true singular vectors. Their modified updates in combination with their data parallel distrusted algorithm leads to significantly improved convergence rates.  ", "summary_of_the_review": "The authors address the problem of the biased updates of the $\\alpha$-EigenGame in a simple yet effective and theoretically sound way. The proposed changes make the algorithm both highly data parallel and also very robust when using small batch sizes. While more work is definitely required to understand the underlying factors that affect convergence rates, I am confident that this work makes an important first step towards this goal.", "strength_and_weaknesses": "", "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": "X9ggUi31yKN", "reviewer": "Reviewer_T9Hp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper improves $\\alpha$-EigenGame by proposing a novel unbiased variant $\\mu$-EigenGame. The proposed method adopts unbiased and parallelizable updates in the stochastic setting and is guaranteed by global convergence. The ideas of the paper are interesting and the writing is good. However, given the prior work $\\alpha$-EigenGame, the (technical) novelty of this paper is not so much. Also, the theoretical part of this paper is on the weak side.\n\nTheorem 1 requires that covariance matrix C is positive definite with distinct eigenvalues. I think this assumption is a bit strong since the algorithm only computes the top-k eigenvectors. Why it requires all eigenvalues of C to be distinct? Actually, $\\alpha$-EigenGame only requires top-k eigenvalues are distinct (Theorem 2.1 of (Gemp et al., 2021)). In addition, methods such as Oja's algorithm only require an eigengap between the k and k+1 eigenvalues.\n\nTheorem 1 only gives an asymptotic convergence. I think providing a finite-sample convergence can largely increase the theoretical contribution of this paper.", "summary_of_the_paper": "The paper considers PCA problem from a game-theoretic view and propose a novel algorithm ($\\mu$-EigenGame) with stochastic convergence guarantees. The proposed method introduces an unbiased update which allows greater parallelism over data. The empirical results show that $\\mu$-EigenGame outperforms its predecessor $\\alpha$-EigenGame.", "summary_of_the_review": "Though the idea of this paper is interesting, the weakness of the theoretical analysis reduces my criterion on it. I think this paper is a bit below the bar.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "44WMfVqZglF", "reviewer": "Reviewer_ub8e", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written. It has a concise introduction and clear motivations to the problem, the proposed solution, and the final results. I am not in this area and I didn’t read the EigenGame before but I can quickly get the main contribution and the key observation of the paper. \n\nAlthough this paper makes the story of EigenGame more complete, I think it is arguable that the contributions meet the acceptance threshold. The introduction of the unbiased estimation (Lemma 2) is nice, but it seems not very surprising given the EigenGame results. I think it would be great if the authors can highlight some technical contributions in the proof of Theorem 1.  Another weakness is that the convergence is asymptotic. I think the authors may also briefly discuss the difficulty of getting non-asymptotic convergence.\n\nLooking at Figure 2 (a), it seems like the vectors in the \\alpha-EigenGame can be learned in parallel, but the remark below Theorem 1 says the deterministic result in Gemp et al. (2021) requires that each v is learned in sequence. I wonder which one is the case in their paper. ", "summary_of_the_paper": "The authors extend previous work EigenGame from full-batch updates to stochastic updates. They propose an unbiased stochastic update that is asymptotically equivalent to the deterministic update, but it allows better parallelism.  ", "summary_of_the_review": "Although the paper is interesting and well written, I have some concerns regarding the theoretical contributions. Therefore, I think the paper is slightly below the bar.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: Motivated by the recently proposed EigenGame, this paper proposes an unbiased stochastic update to replace the biased one in the original EigenGame. The new algorithm is asymptotically equivalent to EigenGame, enjoys better parallelism on big data, and beats EigenGame in experiments. Some reviewers are originally concerned about the lack of finite sample convergence results. After the author's response and reviewer discussion, this paper does get sufficient support. Therefore, I recommend acceptance and encourage the authors to think about how to deliver a finite-sample analysis in future work.
Decision: Accept (Poster)