EigenGame: PCA as a Nash Equilibrium
Authors: Ian Gemp
Brian McWilliams
Claire Vernade
Thore Graepel
Venue: ICLR 2021 Oral (2021)
Keywords: pca
principal components analysis
nash
games
eigendecomposition
svd
singular value decomposition

Abstract: We present a novel view on principal components analysis as a competitive game in which each approximate eigenvector is controlled by a player whose goal is to maximize their own utility function. We analyze the properties of this PCA game and the behavior of its gradient based updates. The resulting algorithm---which combines elements from Oja's rule with a  generalized Gram-Schmidt orthogonalization---is naturally decentralized and hence parallelizable through message passing. We demonstrate the scalability of the algorithm with experiments on large image datasets and neural network activations. We discuss how this new view of PCA as a differentiable game can lead to further algorithmic developments and insights.

Published as a conference paper at ICLR 2021
EIGENGAME: PCA AS A NASH EQUILIBRIUM
Ian Gemp, Brian McWilliams, Claire Vernade & Thore Graepel DeepMind
Lingemp, bnow, vernade, thore) @google. com
ABSTRACT
We present a novel view on principal component analysis (PCA) as competitive game which each approximate eigenvector is controlled by a player whose goal is to maximize their own utility function. We analyze the properties of this PCA game and the behavior of its gradient based updates. The resulting bigorithm-whieh combines elements from Oja's rule with generalized Gram- Schmidt orthogonalization is naturally decentralized and hence parallelizable through message passing. We demonstrate the scalability of the algorithm with experiments on large image datasets and neural network activations. We discuss how this new view of PCA differentiable game can lead to further algorithmic developments and insights.
INTRODUCTION
The principal components of data are the vectors that align with the directions of maximum variance. These have two main purposes: a) as interpretable features and b) for data compression. Recent methods for principal component analysis (PCA) focus on the latter, explicitly stating objectives to find the k-dimensional subspace that captures maximum variance (e.g., (Tang) 2019)), and leaving the problem of rotating within this subspace to, for example, a more efficient downstream singular value (SVD) decomposition sterß] This point is subtle, yet critical. For example, any pair of two- dimensional, orthogonal vectors spans all of R2 and, therefore, captures maximum variance of any wwo-dimensional dataset. However, for these vectors be principal components, they must, in addition, align with the directions of maximum variance which depends on the covariance of the data. By learning the optimal subspace, rather than the principal components themselves, objectives focused on subspace error ignore the first purpose of PCA. In contrast, modern nonlinear representation learning techniques focus on learning features that are both disentangled (uncorrelated) and low dimensional (Chen et al. 2016 Mathieu et al. 2018 Locatello et al. 2019 Sarhan et al.) 2019).
It is well known that the PCA solution of the d-dimensional dataset X Raxd is given by the cigenvectors of X X or equivalently, the right singular vectors of X. Impractically, the cost of ndd (ndd n-dde)-ttme and (ndd)-saace (Shamir 2015 Tang
computing the full SVD scales with Ommin
2019). For moderately sized data, randomized methods can be used (Halko et al. 2011). Beyond this.
stochastic-oe or online-methods based on Oja's rule (Oja 1982) or power iterations (Rutishauser
1971) are common. Another option is to use streaming KAPCA algorithms such as Frequent Directions
(FD) Ghashami et al. (016) or Oja's s algorithn (Allen-Zhy and Li 2017 with storage complexity
O kd)) Sampling or sketching methods also scale well, but again, focus on the top-k subspace (Sarlos
2006
Cohen et al., 2017: Feldman et al. 2020).
In contrast to these approaches, view each principal component (equivalently eigenvector) as a player in game whose objective is to maximize their own local utility function in controlled competition with other vectors. The proposed utility gradients are interpretable combination of process. We make the following contributions:
Oja's rule and a generalized
A novel formulation of PCA as finding the Nash equilibrium of a suitable game,
A sequential, globally convergent algorithm for approximating the Nash on full-batch data,
I After learning the top-k subspace V E R gl the rotation can be recovered via an SVD of XV.
FD approximates the top-k subspace; Oja's algorithm approximates the top-k eigenvectors.

---

Published as a conference paper at ICLR 2021
A decentralized algorithm with experiments demonstrating the approach as competitive with modern streaming &-PCA algorithms on synthetic and real data,
In demonstration of the scaling of the approach, we compute the top-32 principal components of the matrix of RESNET-200 activations on the IMAGENET dataset (n s 10 d x 20 90%...
Each of these contributions is important. Novel formulations often lead to deeper understanding of problems, thereby, opening doors improved techniques. In particular, k-player games are in general complex and hard to analyze. In contrast, PCA has been well-studied. By combining the two fields we hope to develop useful analytical tools. Our specific formulation is important because it obviates the need for any centralized orthonormalization step and lends itself naturally to decentralization. And lastly, theory and experiments support the viability of this approach for continued research.
PCA AS AN EIGEN-GAME
We adhere the following notation. Vectors and matrices meant to approximate principal components (equivalently eigenvectors) are designated with hats, á and V' respectively, whereas true principal components are v and V. Subscripts indicate which eigenvalue a vector is associated with. For example, 0 is the ith largest eigenvector. an abuse of notation, djzc refers to the set of vectors {uylj {I...., }}} and are also referred to as the parents of Vi (v; is their child). Sums over indices should be clear from context, e.g.,
this work, we will assume each eigenvalue is distinct. By
Σ Ejet 2j=1- The Euclidean inner product is written (u, u) = u T v. We denote the unit sphere by S and simplex by Ad-1 in d-dimensional ambient space.
Outline of derivation As argued in the introduction, the PCA problem is often mis-interpreted as learning projection of the data into a subspace that captures maximum variance (equiv. maximizing the trace of a suitable matrix R introduced below). This is in contrast to the original goal of learning the principal components. We first develop the intuition for deriving our utility functions by (i) showing that only maximizing the trace of R is not sufficient for recovering all principal components (equiv. eigenvectors), and (ii) showing that minimizing off-diagonal terms in a complementary objective to maximizing the trace and can recover all components. We then consider learning only the top-k and construct utilities that are consistent with findings in (i) and (ii), equal the true eigenvalues at the Nash of the game construct, and result in game that is amenable analysis.
Derivation of player utilitics. The eigenvalue problem for a symmetric matrix X M E Raxd is find matrix of d orthonormal column vectors V (implies V is full-rank) such that MV = VA with A diagonal. Given a solution to this problem. the columns of V are known as eigenvectors and corresponding entries in are eigenvalues. By lelt-mulg by VT and recalling V V = V = I by orthonormality (i.e., V is unitary), we can rewrite the equality as
VV =
unitary A.
(1)
Let V denote a guess or estimate of the true eigenvectors V and define R(V) MV. The PCA problem is often posed as maximizing the trace of R (equiv. minimizing reconstruction error):
ER R4 TT(R)= TH(V MV) (VVV M) Tr(a).
max PTV=I
Surprisingly. the objective in is independent of V. so it cannot be used to recover all (i.e., k = d) the cigenvectors of (i). Alternatively, Equation (I) implics the eigenvalue problem can be phrased ensuring all off off-diagonal terms of R are zero, thereby ensuring R is diagonal-(ii
min DTV=I
It is worth further examining the entries of R in detail. Diagonal entries R, (0,, Mo) recognized as Rayleigh quotients because ||0;|| = 1 by the constraints. Off-diagonal entries R.j = (ö,, Mog) measure alignment between é; and 0g under generalized inner product (s/)ar.
2

---

Published as a conference paper at ICLR 2021
Figure I: Each player i's utility function depends on its parents represented here by a directed acyclic graph. Each parent must broadcast its vector, "location", down the hierarchy in fixed order.
So far, we have considered learning all the eigenvectors. If we repeat the logic for the top-k eigenvectors with & < d. then by Equation (I). R must still be diagonal. V is not square, so VVT # I, but assuming V is orthonormal as before, we have VV = P is projection matrix. Left-multiplying Equation (I) by V now reads (PM) VA so are solving an eigenvalue problem for a subspace of M.
If we only desire the top-k cigenvectors, maximizing the trace encourages learning subspace spanned by the top-k eigenvectors, but does not recover the eigenvectors themselves. On the other hand, Equation (3) places no preference on recovering large over small eigenvectors, but does enforce
the columns of V to actually be eigenvectors. The preceding exercise is intended introduce minimizing the off-diagonal terms of ft as a possible complementary objective for solving top-k PCA. Next, we will use these two objectives to construct utility functions for each eigenvector é;.
We want to combine the objectives to take advantage of both their strengths. A valid proposal is
max Σ R.
Σ R2 191'
(4)
However, this objective ignores the natural hierarchy of the top-k eigenvectors. For example, é is penalized for aligning with êg and vice versa, but é1, being the estimate of the largest eigenvector, should be free to search for the direction that captures the most variance independent of the locations of the other vectors. Instead, first consider solving for the top-1 eigenvector, V1 in which case R = [ M }| is a 1 x matrix. In this setting, Equation (3) is not applicable because there are no off-diagonal elements, so max,7 =1=1 (01, M2) is a sensible utility function for 01.
If considering the top-2 eigenvectors, 01 's utility remains as before, and we introduce a new utility for 02. Equation is now applicable, so 02 's utility is
(02, Mo2) (02, M
max 1, Pg
(5)
0
(Ø1, Mo1)
where we have divided the off-diagonal penalty by (01, M11) so a) the two terms in Equation on a similar scale and b) for reasons that ease analysis. Additionally note that the constraint 07 0g
5 are
may be redundant at the optimum (0) U1, 02 12)) because the second term, (65, M07 (U2, Mo,)² = Ai (v2, ) already penalizes such deviations (Ais is the ith largest eigenvector). These reasons motivate the following set of objectives (utilities), one for each vector E (1....,k) k):
max 6: 8,=1
{ (u,(0: (z4e) = 6, Mé.
Σ JCN
(0. May)
= ||AI|
(X X (X0 X0,)
(6)
MG,
where the notation (a,(b()) emphasizes that player i adjusts a, to maximize a utility conditioned on b.
It is interesting to note that by incorporating knowledge of the natural hierarchy (see Figure []. we are immediately led to constructing asymmetric utilities, and thereby, inspired to formulate the PCA problem as a game, rather than direct optimization problem as in Equation (4).
A key concept in games is a Nash equilibrium. A Nash equilibrium specifies variable for each player from which no player can unilaterally deviate and improve their outcome. In this case, V' is (strict-) Nash equilibrium if and only if for all i, (, (5)+))) > (=(2:(ūz<z) for all 2; E dd-1
Theorem 2.1 (PCA Solution is the Unique strict-Nash Equilibrium). Assume that the top-k eigenvalues of X X are positive and distinct. Then the top-k eigenvectors form the unique strict- Nash equilibrium of the proposed game in Equation 66 The proof is deferred to Appendix L
Solving for the Nash of game is difficult in general. Specifically, it belongs to the class of PPAD- complete problems (Gilboa and Zemel 1989 Daskalakis et al. 2009). However, because the game
3

---

Published as a conference paper at ICLR 2021
is hierarchical and each player's utility only depends on its parents, it is possible to construct sequential algorithm that is convergent by solving each player's optimization problem in sequence.
3 METHOD
Utility gradient. In Section 2 we mentioned that normalizing the penalty term from Equation ( had motivation beyond scaling. Dividing by (Øg, My) results in the following gradient for player
(Xúx, Xūş)
Ve, (o(l) 2M
0z
13
2X
X
Xūg
(7)
generalized Schmidt
The resulting gradient with normalized penalty term has an intuitive meaning. It consists of single generalized Saaami step followed by the standard matrix product found in power iteration and Oja's rule. Also, notice that applying the gradient as a fixed point operator sequence (6; 6 2 v. u4 (4,6 (0,(0y<x)) on M I recovers the standard Gram-Schmin Schmidt procedure for orthogonalization
sequential algorithm. Each eigenvector can be learned by maximizing its utility. The vectors are constrained the unit sphere, a non-convex Riemannian manifold, so we use Riemma- nian gradient ascent with gradients given by Equation 77) In this case, Riemannian optimization theory simply requires an
V2
intermediate step where the gradient, Vi, is projected onto the tangent space of the sphere to compute the Riemannian gradient, E. more detailed illustration can be found in Appendix Recall that each u; depends on Ūj<í- If any of êicc are being learned concurrently, then 0; is maximizing a non-stationary objective which makes convergence proof diffieult. Instead, for completeness, we prove convergence assuming each ú; is learned in sequence. Algorithm [ learns é; given fixed parents 0 03c6 we present the convergence guarantee in Section 4 and details on setting P: and a in Appendix
True PCS
VR.
Figure 2: EigenGame guides each i, along the unit-sphere from 1 to f
in parallel; M = di ( (3,,, 1)).
Algorithm 1 EigenGame Sequeential
Algorithm EigenGame (EigenGame- Given: matrix X E Raxdd maximum error with Va, instead of VR) tolerance Pt. initial vector of E Sa-1 learned approximate parents ôzzú, and step size a.
Given: stream, X, E mxd total iterations T, initial vector 60 Set and step size
0; 1- 09 4; = - min suuil/2,,i)>
0 + 1
for 1:
for - 1: do
rewards t X20;
rewards X0;
penalties + Ejer (X,e,
X,
penalties + Ejet X Xx,) X0,
Va, + 2X, rewards - penalties
VA + T rewards penalties
VR + V., (V 0
R + V.
(V., 0.)0;
8 6 ta
F.
8 + 6. + +av R
|
0 |
broadcast(())
end for return 02
end for return 0;
decentralized algorithm. While Aggorihmm[enjppe a convergence guarantee, learning every parent θÿ<ج before learning 0; may be unnecessarily restrictive. Intuitively, as parents approach their respective optima, they become quasi-stationary. so we do not expect maximizing utilities in parallel to be problematic in practice. To this end, we propose Algorithm visualized in Figure 2
Unnque up sign change; this is expected hoth 1ú and -t4 represent the same principal component.
4

---

Published as a conference paper at ICLR 2021
Eneary Decaytng Spactrum
Exponendally Cacay Spectrum
Eogencees Strak
VABST
VNIST
Lingor Grrect
b.coreurr St
10
20
250
400
600
002
3002
200
400
603
300
1000
58
117
346
Heratior
25
146
(a) Synthetic data
(b) MNIST
Figure 3: (a) The longest streak consecutive vectors with angular error less than radians is plotted versus algorithm iterations for a matrix M E 500x00 with a spectrum decaying from 1000 to linearly and exponentially. Average runtimes
reported in milliseconds next the method n We omit Krasulina's as it is only designed to find the top-k subspace. Both EigenGime variants and GHA achieve similar asymptotes on the linear spectrum. (b) Longest streak and subspace distance on MNIST with average runtimes reported in seconds. (a Learning rates were chosen from {10-3 10-6] 10 held runs. Solid lines denote results with the best performing learning rate. Dotted and dashed lines denote results using the best learning rate x 10 and 0.1. All plots show means over 10 trials. Shading highlights standard error of the mean for the best learning rates.
In practice we can assign each eigenvector update to its own device (e.g. a GPU or TPU). Systems with fast interconnects may facilitate tens, hundreds or thousands of accelerators be used. In such settings, the overhead of (roadcast((g) is minimal. We can also specify that the data stream is co-located with the update so i; updates with respect its own X,,t- This a standard paradigm for e.g. data-parallel distributed neural network training. We provide further details in Section 6
Message Passing a DAG. Our proposed utilities enforce strict hierarchy the eigenvectors. This a simplification that both eases analysis (see Appendix M and improves convergence" however, is not optimal. We assume vectors are initialized randomly on the sphere and, for instance, O% may be initialized closer to Uj than even ú and vice versa. The hierarchy shown in Figure enforces a strict graph structure for broadcasting information of parents the childrens' utilities.
To our knowledge, our utility formulation in Equation (6) is novel. One disadvantage is that stochastic gradients of Equation (7) are biased. This mitigated with large batch sizes (further discussion in Appendix D
4 CONVERGENCE OF EIGENGAME
Here, we first show that Equation 66 has simple form such that any local maximum of uy is also a global maximum. Player utility depends on parents, so we next explain how error in the parents propagates to children through missspecification of player i's utility. Using the first result and accounting for this error, we are then able to give global, finite-sample convergence guarantees in the full-batch setting by leveraging recent non-convex Riemannian optimization theory.
The utility landscape and parent-to-child error propagation. Equation (6) is abstruse, but we prove that the shape of player i's utility is simply sinusoidal in the angular deviation of 6; from the optimum. The amplitude of the sinusoid varies with the direction the angular deviation along the unit-sphere and is dependent on the accuracy of players < i. In the special case where players j < have learned the tip-(i 1) eigenvectors exactly, player i's utility simplifies (see Lemma N.1 to
u. (Uzest) Au sin? sinn(())) (Au
Σ EzAA
where 6, is the angular deviation and 2 E A 1 parameterizes the deviation direction. Note that sin? has period instead of 2m,, which simply reflects the fact that i and -t; are both eigenvectors.
"FgenGGame sans order learns max PC sans onder-normalization PCs on data Figure FI Gage runtimes are longer than those of FigenGame in the synthetic experiments despite strictly requiring fewer FL POPS; apparently this due low-level floating point arithmetic specific the experiments.
5

---

Published as a conference paper at ICLR 2021
An error propagation analysis reveals that it is critical to learn the parents to a given degree of accuracy. The angular distance between iú and the maximizer of plaver i's utility with approximate parents has tan dependence (i.c., soft fopcttntiio;; see Lemma and
and Figure 13 in Appendix [N)
Theorem 4.1 (Global convergence). Algorithm A aachevees finite sample convergence to within Boot angular ervor of the top-k principal components, independent of initialization. Furthermore, if each 0g is initialized to within 3 of v6 Algorithm| D returns the components with angular error less than Owr
in T -1o
(k-1) 1)! ONN
II [10AN)]
l.
]"] iterations. Proofs deferred to Appendices O.4 and
Angular error is defined as the angle between 6 and 25: 0, = sin sin (v-1 (Dy, 0,)2 The first is in the formula for T appears from a naive summing of worst case bounds on the number of iterations required to learn each ūjz individually. The constant 16 arises from the error propagation analysis; parent vectors, ojei. must be learned to under 1/16th of a canonical error threshold, アー for the
child 0 where gi Aa 1++1,++. The Riemannian optimization theory we leverage dictates that + iterations are required meet a (pp) error threshold. This is why the squared inverse of the error threshold appears here. Breaking down the error threshold itself, the ratio A11/9 says that more iterations are required to distinguish eigenvectors when the difference between them (summarized by the gap gi) is small relative to the scale of the spectrum, A11- The (A: 1)! term appears because learning smaller eigenvectors requires learning much more accurate 01 higher up the DAG.
Lastly, the utility function for each é; is sinusoidal, and it is possible that we initialize é; with initial utility arbitrarily close to the trough (bottom) of the function where gradients are arbitrarily small. This is why the global convergence rate depends on the initialization in general. Note that Al Algorithm]] [ effectively detects the trough by measuring the norm of the initial gradient (V and scales the number of required iterations appropriately. A complete theorem that considers the probability of initializing é within of 0; is in Appendix [ but this possibility shrinks to zero in high dimensions.
We would also like to highlight that these theoretical findings strong relative to some other claims. For example, the exponential convergence guarantee for Matrix Krasulina requires the initial guess at the eigenvectors capture the top-(k: 1) subspace (Tang 2019), unlikely when d >> k. A similar condition is required in (Shamir 2016b). These guarantees are given for the mini-batch setting while ours for the full-batch, however, we provide global convergence without restrictions on initialization.
5 RELATED WORK
PCA is a century-old problem and a massive literature exists (Jolliffe. 2002; Golub and Van Loan 2012). The standard solution to this problem is to compute the SVD, possibly combined with randomized algorithms, to recover the top-k components as in (Halko et al. 2011) or with Frequent
Directions (Ghashami et al. 2016) which combines sketching with SVD.
In neuroscience, Hebb's rule (Hebb 2005) refers to a connectionist rule that solves for the top eigenvector of matrix M using additive updates of vector
<- + MM Likewise, Oja's rule (Oja 1982: Shamir 2015) refers to a similar update v + e + ny(T we" MMM In machine learning, using normalization step of v + e/|[e]] with Hebb's rule is somewhat confusingly referred to as Oja's algorithm (Shamir, 2015), the reason being that the subtractive term in Oja's rule can be viewed regularization term for implicitly enforcing the normalization. In the limit of infinite step size, 77 + co, Oja's algorithm effectively becomes the well known Power method. If a normalization step is added to Oja's rule, this is referred to as Krasulina's algorithm (Krasulina 1969). In the language of Riemannian manifolds, w/|le|| can be recognized as a retraction and (7 Tv as
projecting the gradient Me onto the tangent space of the sphere (Absil et al.. 2009).
Many of the methods above have been generalized to the top-k components. Most generalizations involve adding an orthonormalization step after each update, typically accomplished with a QR factorization plus some minor sign accounting (e.g., see Algorithm Appendix A. An extension of Krasulina'ss 's algorithm to the top-k setting, termed Matrix Krasulina (Tang) 22019). was recently proposed in the machine learning literature. This algorithm be recognized projecting the gradient onto the Stiefel manifold (the space of orthonormal matrices) followed by a QR step to maintain orthonormality, which is well known retraction.

---

Published as a conference paper at ICLR 2021
Maintaining orthonormality via OR is computationally expensive, Amid and Warmuth (2019) propose an alternative Krasulina method which does not require re-orthonormalization but instead requires inverting a & x k matrix; in streaming setting restricted to minibatches of size 1 (X, IR),,
Sherman-Mortnn Morrison (Golub and Van Loan 2012) can be used to efficiently replace the inversion step. Raja and Bajwa (2020) develop a data- natt-parallel distributed algorithm for the top eigenvector. Alternatively, the Jacobi eigenvalue algorithm explicitly represents the matrix of cigenvectors as Givens rotation matrix using sin's 's and cos's and rotates M until it is diagonal (Golub and Van der
Vorst, 2000).
In contrast, other methods extract the top components sequence by solving for the ith component using an algorithm such as power iteration or Oja's, and then enforcing orthogonality by removing the learned subspace from the matrix, a process known as deflation. Alternatively, the deflation process may be intertwined with the learning of the top components. The generalized Hebbian algorithm (Sanger 1989) (GHA) works this way as do Lagrangian inspired formulations (Ghojogh al.) 2019) as well our own approach. We make the connection between GHA and our algorithm concrete in Prop. K. Note, however, that the GHA update is not the gradient of any utility (Prop. K.2
and therefore, lacks clear game interpretation.
Of these. Oja's algorithm has arguably been the most extensively studied (Shamir 2016a Allen-Zhu and Li 2017 Note that Oja's algorithm converges to the actual principal components (Allen-Zhe and [i 2017) and Matrix Krasulina (Tang. 2019) converges to the top-k subspace. However, neither can be obviously decentralized. GHA (Sanger 1989) converges to the principal components asymptotically
and can be decentralized (Gang et al.
2019). Each of these is applicable in the streaming k-PCA
setting.
6 EXPERIMENTS
We compare our approach against GHA, Matrix Krasulina, and Oja's algorithm? We present both EigenGame and EigenGame" which projects the gradient onto the tangent space of the sphere each step. We measure performance of methods in terms of principal component accuracy and subspace distance. We measure principal component accuracy by the number of consecutive components, or longest streak, that are estimated within an angle of & from ground truth. For example, the angular errors of the 0; 's returned by a method are, in order, [01, 00,00,,0 0z.
x T -J. then the method is credited with a streak of only regardless of the errors 0, For Matrix Krasulina, first compute the optimal matching from é; to ground truth before measuring angular error. We present the longest streak as opposed to "# of cigenvectors found" because, in practice, no ground truth is available and we think the user should be able place higher confidence in the larger eigenvectors being correct. If an algorithm returns & vectors, 2 of which are accurate components but does not indicate which, this is less helpful. We measure normalized subspace distance using 1 Tr(UU P) 1] where U VVt and P VVi similarly to Tang 2019).
Synthetic data. Experiments on synthetic data demonstrate the viability of our approach (Figure Baj Oja's algorithm performs best on synthetic experiments because strictly enforcing orthogonalization with an expensive QR step greatly helps when solving for all cigenvectors. EigenGame is able to effectively parallelize this over k machines and the advantage of QR diminishes in Figure 33b The remaining algorithms perform similarly on a linearly decaying spectrum, however, EigenGame performs better on an exponentially decaying spectrum due possibly to instability of Riemannian gradients near the equilibrium (see Appendix J for further discussion). GHA and EigenGame are equivalent under specific conditions (see Proposition K.I).
Figure 4a shows EigenGame solves for the eigenvectors up to high degree of accuracy 32 i.c. the convergence results in Figure Ba are not the result of using a loose tolerance of x. With the lower tolerance, all algorithms take slightly more iterations to learn the eigenvectors of the linear spectrum; it is difficult to see any performance change for the exponential spectrum. Although Theorem [. assumes distinct eigenvalues, Figure supports eigenvalues for convergence. We leave proving convergence in this setting to future work.
suppooorss the claim that EigenGame does not require distinct
'See Table in Allen-Zhu and Li 2017)
"A detailed discussion of Frequent Directions Ghashami al. 2016) can be found in Appendix H
7

---

Published as a conference paper at ICLR 2021
Liearry Cecastng Spactrum
Eyponendally Cocay Spectrum
Linary Decojdty Spactrun
Exponentilly Decay Spactum
Unngor Grrect
Cornect Bquenece
-0
DANDARI
Lorgur Correct
10
220
400 600
002
3002
220
600
603
300
1002
220
600
600
803
1002
200
400
600
03:
1032
Training
(a) Synthetic data: Stricter Tolerance
(b) Synthetic: Repeated Eigenvalues
Figure 4: (a) Repeats analysis of Figure 3a but for a lower angular tolerance of _ b Repeats
32
analysis of Figure Bal with angular tolerance of g as before, but with eigenvalues 10 19 of the ordered spectrum overwritten with λιo of the original spectrum. We compute angular error for the eigenvectors either side of this "bubble" show that EigenGame finds these eigenvectors despite repeated eigenvalues in the spectrum; note 40/50 is optimal this experiment.
1E3
121
KB
K3
KI1
KSL
KM
1218
KB
KX
KM
KN
Principal Components
(h) Block-1 Mcan Filter Maps
Figure 5: (ab Top-8 principal components of the activations of a RESNET-200 on IMAGENET ordered block-wise by network topology (dimension of each block on the right y-axis). Block closest to input and Block 5 is the output of the network. Color coding is based on relative variance between blocks across the top-8 PCs from blue (low) to red (high). (b) Block mean activation maps of the top-32 principal components of RESNET-200 on IMAGENET computed with EigenGame.
MNIST handwritten digits. We compare EigenGame against GHA, Matrix Krasulina, and Oja's algorithm on the MNIST dataset (Figure 3b). We flatten each image in the training set to obtain 60, 000 x 784 dimensional matrix. EigenGame is competitive with Oja's in high batch size regime (1024 samples per mini-batch). The performance gap between EigenGame and the other methods shrinks as the mini-batcr size reduced (see Appendix[]] [Ip expectedly due to biased gradients.
The principal components of RESNET-200 activations on IMAGENET are edge filters. A pri- mary goal of PCA is to obtain interpretable fow-dimensiona. representations. To this end present an example of using EigenGame to compute the top-32 principal components of the activations of a the IMAGENET dataset. We concatenate the flattened activations from the output of each residual block resulting in d se 20M dimensional vector representation for each of the roughly 1.2M input images. It is not possible store the entire 195TB matrix in memory, nor incrementally compute the Gram/covariance matrix.
pretrained N
We implemented data-and-model parallel version of EigenGame in JAX (Bradbury et al. 2018) where each ig is assigned to it's own TPU (Jouppi et al., 2017). Each device keeps a local copy of the RESNET parameters and the IMAGENET datastream. Sampling mini-batch (of size 128), computing the network activations and updating é; are all performed locally. The broadcast (6;) step is handled by the pmap and lax. _gather functions. Computing the top-32 principal components takes approximately nine hours 32 3sUv
Figure 5a shows the top principal components the activations of the trained network organized by network topology (consisting of five residual blocks). Note that EigenGame is not applied blsek-wise, but on all 20M dimensions. We do not assume independence between blocks and the eigenvector has unit norm across all blocks. We observe that Block I (closest to input) of PC has very small magnitude activations relative to the other PCs. This is because PC should capture the variance which discriminates most between the classes in the dataset. Since Block is mainly
8

---

Published as a conference paper at ICLR 2021
concerned with learning low-level image filters, it stands to reason that although these are important for good performance, they do not necessarily extract abstract representations which are useful for that PC has larger relative activations in the later blocks.
classification. Conversely,
We visualize the average principal activation in Block | Figure 5b) The higher PCs learn distinct filters (Gabor filters, Sataaaciiino---uusssii filters c.f. (Bell and Sejnowski 1997)).
7 CONCLUSION
seems easier to train bi-directional LSTM with attention than to compute the SVD of large matrix. -Chris Re
NeurIPS 2017 Test-of-Tine Time Award, Rahimi and Recht (Rahimi and Recht (017)-
In this work we motivated PCA from the perspective of a multi-player game. This inspired a decentralized algorithm which enables large-scale principal components estimation. To demonstrate this we used EigenGame to analyze a large neural network through the lens of PCA. To our know ledge this is the first academic analysis of its type and scale (for reference, (Tang 2019) compute the top-6 PCs of the = 2300 outputs of VGG). FigenGame also opens a variety of research directions.
Scale. In experiments, we broadcast across all edges in Figure I every iteration. Introducing lag or broadcasting with dropout may improve efficiency. Can we further reduce our memory footprint by storing only scalars of the losses and avoiding congestion through online bandit or reinforcement learning techniques? Our decentralized algorithm may have implications for federated and privacy preserving learning as well (Heinze et al. 2016 Heinze-Deme
al. 2018 Bonawitz al., 2019).
Games. EigenGame has unique Nash equilibrium due to the fixed DAG structure, but vectors are initialized randomly so 0g may start closer to in than éj does. Adapting the DAG could make sense, but might also introduce spurious fixed points suboptimal Nash. Might replacing vectors with populations accelerate extraction of the top principal components?
Core ML. EigenGame could be useful diagnostic or for accelerating training (Desjardins et al., 2013; Krummenacher et al. 2016); similarly, spectral normalization has shown to be a valuable tool for stabilizing GAN training (Miyato et al. 2018).
Lastly, GANs (Goodfellow et al. 2014) recently reformulated learning a generative model as a two-player zero-sum game. Here, we show how another fundamental unsupervised learning task can be formulated as a k-player game. While two-player, zero-sum games are well understood, research on k-player, general-sum games lies the forefront in machine learning. We hope that marrying fundamental, well-understood task in PCA with the relatively less understood domain of many player games will help advance techniques on both ends.
ACKNOWLEDGEMENT
We are grateful to Trevor Cai for his help scaling the JAX implementation of EigenGame to handle the large IMAGENET experiment and Daniele Calandriello for sharing his expert knowledge of related work and advice on revising parts of the manuscript.
REFERENCES
P-A. Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization Algorithms Matrix Manifolds. Princeton University Press, 2009.
Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: global, gap- free, and ncar-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487 492. IEEE, 2017.
Ehsan Amid and Manfred Warmuth. An implicit form of Krasulina's 's k-PCA update without the orthonormality constraint, arXiv preprint arXiv:1909.0480) 2019.
Authony J Bell and Terrence J Sejnowski. The "independent components" of natural scenes edge filters. Vision Research. 37(23):3377-3338 1997.
'hhe activations in Block result from convolving 64 filters over the layer's input. We take the mean over the 64 channels and plot the resulting 112 112 image.

---

Published as a conference paper at ICLR 2021
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Koneeny, Stefano Mazzocchi, Brendan McMahan, Towards foderated learning scale: system design, arXiv preprint 11X.:::900000400 2019.
Nicolas Boumal, Pierre-Antoine Absil, and Coralia Cartis. Global rates of convergence nonconvex optimiza- tion on manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, 2019.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://gittub.. wwt. cttp://///o/oooo/e/e/o///
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, llya Sutskever, and Pieter Abbeel. Infogan: interpretable representation learning by information maximizing generative adversarial nets. Advances in Neural Information Processing Systems, pages 2172-2180, 2016.
Michael B Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1758-1777. SIAM, 2017.
Constantinos Daskalakis, Paul W Goldherg, and Christos H Papadimitriou. The complexity of computing Nash equilibrium. SIAM Journal on Computing, 39( (91))195-229, 2009.
Guillaume Desjardins, Karen Simonyan, Razvan Pascanu, al. Natural neural networks. In Advances in Neural Information Processing Systems, pages 207 1-2079, 2015.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-sizz coresets for k-means, PCA, and projective clustering. SIAM Journal on Computing, 49(3):601-657, 2020.
Arpita Gang, Haroon Raja, and Waheed U Bajwa. Fast and communication-cffiiinn distributed pea. In ICASSP 2019- 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages IEEE, 2019.
Mina Ghashami, Edo Liberty, Jeff M Phillips, and David P Woodruff. Frequent directions: simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5):1762-1792 2016.
Benyamin Ghojagh, Fakhri Karray, and Mark Crowley. Eigenvalue and generalized eigenvalue problems: Tutorial, arXiv preprint arXiv: /903. 1240, 2019.
Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989.
Gene H Golub and Henk A Van der Vorst. Eigenvalue computation in the 20th century. Journal of Computational and Applied Mathematics, 123(1-2):33 65, 2000.
Gene H Golub and Charles F Van Loan. Matrix Computations, volume 3. JHU press, 2012.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farte Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pages 2672-2680, 2014.
Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp. Finding structure with randomness: probabilistic algorithms constructing approximate matrix decompositions. SIAM review, 53(2):217-288, 2011.
Donald Olding Hebb. The Organization of Behavior: A Neumpsychological Theory. Psychology Press, 2005.
Christina Heinze, Brian McWilliams, and Nicolai Meinshausen. Dual-loco: distributing statistical estimation using random projections. In Artificial Intelligence and Statistics, pages 875-883, 2016.
Christina Heinze-Deml. Brian McWilliams, and Nicolai Meinshausen. Preserving privacy between features in distributed estimation. Stat, 7())e118, 2018.
Roger A Horn and Charles R Johnson. Matrix Analysis. Cambridge University Press, 2012.
Ian T Jolliffe, Principal components in regression analysis. In Principal Component Analysis. Springer, 2002.
Norman P Jouppi. Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th Annual International Symposium Computer Architecture, pages 1-12, 2017.
10

---

Published as a conference paper at ICLR 2021
TP Krasulina. The method of stochastic approximation for the determination of the least eigenvalue of symmetrical matrix. USSR Computational Mathematics and Mathematical Physics, 9(6):189-1999 1969.
Gabriel Krummenacher, Brian McWilliams, Yannic Kilcher. Joachim M Buhmann, and Nicolai Meinshausen. Scalable adaptive stochastic optimization using random projections. Advances in Neural Information Processing Systems, pages 1750-1758, 2016.
Shenggiao Li. Concise formulas for the area and volume of hyperspherical cap, Asian Journal of Mathematics and Statistics, 4(1):66 70, 2011.
Francesco Locatello, Stefan Bauer. Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf. and Olivier Bachem. Challenging common assumptions the unsupervised Icarning of disentangled representations. In Proceedings of the International Conference on Machine Learning, pages 41 411441124, 2019.
Emile Mathieu, Tom Rainforth, Siddharth, and Yee Whye Teh. Disentangling disentanglement in variational autoencoders. arXiv preprint arXiv:1812.02833 2018.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint 1802.0800.005990 2018.
Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of Mathematical Biology, 15(3): 267-273, 1982.
Ali Rahimi and Benjamin Recht. Reflections on random kitchen sinks, 2017. URL http:://ww...tet.ec
net net/201 20120022222// 02/05/22/////// 00/00/5///00 ht////iitaie chen- sinks/]
Haroon Raja and Waheed Bajwa, Distributed stochastic algorithms for high-rate streaming principal component analysis. arXiv preprint (xXi::001.01017 2020.
Rutishauser. Simultaneous iteration method for symmetric matrices. In Handbook for Automatic Computation, pages 284-302. Springer, 1971.
Terence D Sanger. Optimal unsupervised learning in a single-layer linear feedforward neural network. Neural Networks, 2(6):459 473, 1989.
Mhd Hasan Sarhan, Abouzar Eslami, Nassir Navab, and Shadi Albarqouni, Learning interpretable disentangled representations using adversarial VAEs. In Domain Adaptation and Representation Transfer and Medicul Image Learning with Less Labels and Imperfect Data, pages 37-44. Springer, 2019.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Annual IEEE Symposium Foundations Computer Science (FOCS pages 143-152. IEEE, 2006.
Ohad Shamir. A stochastic PCA and SVD algorithm with an exponential convergence rate. In Proceedings of the International Conference Machine Learning, pages 144-152, 2015.
Ohad Shamir. Convergence of stochastic gradient descent for PCA. In Proceedings of the International Conference on Machine Learning, pages 257-265, 2016a.
Ohad Shamir. Fast stochastic algorithms for SVD and PCA: Convergence properties and convexity. In
Proceedings of the International Conference on Machine Learning, pages 248-256, 2016b.
Cheng Tang. Exponentially convergent stochastic k-PCA without variance reduction. In Advances in Neural Information Processing Systems, pages 12393-12404, 2019.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient. estimation. In Advances Neural Information Processing Systems, pages 3835-3844, 2018.
11


Reviews:
[{"review_id": "tb-KwwqKvD", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present new insights on PCA analysis by reconceiving it in terms of a Nash equilibrium among different players, related to the different components. The importance of an objective function minimizing the off-diagonal elements of R is emphasized. The insights lead to parallel algorithms and are demonstrated on large scale problems, which is nice. Overall the new insights can be very valuable and also inspiring for future work and for new developments,  from a broader perspective.\n\nPoints that can be improved:\n\n- related to eqs (1)(2) the authors claim that there is a problem with some classical interpretation of PCA analysis. However, this statement is unclear and possibly incorrect: for coming to (2) the authors start from the solution i.e. the eigenvalue problem, while this should be the result of the derivation. This part should be clarified. Probably it is better to replace this part of the paper by a standard formulation and derivation of PCA analysis as given in standard textbooks. Also one can find it component per component and add orthogonality constraints in each step.\n\n- it is nice that a parallel algorithm is obtained. However, at this point the positioning of the result within the existing literature is not clear yet. In the areas of signal processing and neural networks, parallel algorithms and parallel implementations (systolic arrays, VLSI, etc.) of PCA analysis exist for more than 30 years, see e.g.  the book Principal Component Neural Networks: Theory and Applications by K.I. Diamantaras, S.Y. Kung, and related work.\n\n- section 5: missing methods are e.g. the power method, Lanczos method, Jacobi etc.\n\n- related to future work the authors mention the role of PCA analysis with respect to VAE. There is existing work on generative kernel models, eigenvalue problems and disentanglement that is related to it, see Pandey et al  https://arxiv.org/abs/1906.08144\n\n\n\n\n\n\n\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "D-teiZsPsXI", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nA. Summarize\nThis paper proposes to not only maximizes the trace of the projected covariance matrix R but also minimizes the off-diagonal element of R, which helps to recover the real principal components(eigenvectors of the covariance matrix) from data, while the other large-scale algorithms only recover the top-k subspace.\nFurthermore, the authors utilize the hierarchical relation between eigenvectors and design a utility function for each eigenvector. Therefore, each eigenvector serves as a player in a game and they will achieve strict-Nash Equilibrium at the end, which enables a decentralized algorithm for large-scale PCA problems. \nIn the experiment, the authors conduct experiments on synthetic data, moderate scale data, and large scale data by resnet activation maps. The first two experiments demonstrate that the proposed algorithm is competitive with Oja's algorithm and even better under some conditions. The large scale experiment on resnet activation maps is only feasible by the proposed algorithm and demonstrate that it is a powerful tool to achieve interpretable representation. \n\nB. Strength\n1.  This paper is well organized and easy to follow. The explanation about why other algorithms only recover the top-k subspace but not the principal components is step-by-step. Based on this observation, the authors propose to minimize off-diagonal elements and derives the utility function, which adds a generalized Gram-Schmidt step to the gradient and can be decentralized naturally. \n2. Besides the algorithm itself, the proposed method also opens new doors for other interesting future research other than recovering principle components.\n3. The experiments are simple yet sufficient to demonstrate the superiority of the proposed algorithm. To the best of my knowledge, the proposed algorithm is the first that dealS with a problem as large as in the resnet-200 experiment. \n\nC. Weakness:\n1. My only question is that the proposed algorithm focuses on recovering the real principle components and finding interpretable features. So it would be good if we can see some comparison of the lower-dimensional features in some downstream applications. For example, can we cluster the input data into meaningful clusters better than other algorithms?\n\nD. Justification of score:\nThis is a great paper that gives a new perspective on PCA and derives a novel decentralized large-scale algorithm and will inspire a lot of further research along this line. So I vote to accept this paper.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2xNCZziLo-A", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Principal component analysis (PCA) is a well-known dimensionality reduction and feature learning technique in the literature that leads to uncorrelated features. While there are a plethora of algorithms for PCA, along with accompanying analysis, a majority of these works have been developed from an optimization perspective. This paper differs from existing works in that it motivates the $k$-PCA problem, which involves learning the $k$-dominant eigen vectors of the sample covariance matrix, as a competitive game between $k$ players in which each player is supposed to estimate one of the eigen vectors and the PCA solution is the unique strict-Nash equilibrium. The main contributions of the paper in this regard are the following:\n\n- Setting up the PCA problem as a competitive game between $k$ players and showing that the Nash equilibrium corresponds to the PCA solution (Theorem 2.1)\n- Development of two games (algorithms), with one a sequential algorithm and the other a decentralized algorithm, for solving the PCA problem (Algorithms 1 and 2)\n- Convergence analysis of the sequential algorithm under a restrictive set of assumptions (Theorem 4.1)\n- Establishment of the equivalence between the decentralized algorithm and the Generalized Hebbian Algorithm (GHA) of Sanger (Proposition H.1)\n\nOverall, this is a novel paper in that it offers an alternate view of the PCA problem, which might lead to further advances in our understanding of PCA-type algorithms in the future. I therefore have a favorable view of this paper. There are however several important aspects of this paper that need to be clarified by the authors in a subsequent revision before it becomes ready for publication.\n\n**Major Comments**\n\n1. Theorem 2.1 is based on the assumption of the top-$k$ eigenvalues being distinct. Algorithms such as Orthogonal Iteration (\"subspace\" power method), to the best of my understanding, only require an eigen gap between the $k$ and $k+1$ eigenvalues and do not require the first $k$ eigenvalues to be distinct. This needs to be discussed clearly in the paper.\n2. While Theorem 4.1 for the sequential game does not explicitly state it, it appears that it also requires the eigenvalues to be distinct (Theorem L.4, e.g.). This, once again, is a major assumption that is neither discussed clearly in the paper, nor compared to other works that do not seem to have this limitation.\n3. Majority of the works in the PCA literature require the initialization subspace to not be orthogonal to the $k$-PCA subspace. This work, however, requires the stringent assumption that each eigenvector is initialized to within $\\pi/4$ radians of the original eigenvector. Not only is this a strict probabilistic assumption in the case of random initialization, but it also becomes harder to satisfy as $k$ increases (as the authors also discuss). In light of this strict condition, this reviewer is confused by the claim in the paper that \"these theoretical findings are strong relative to other claims.\" I would also have liked the authors to discuss this assumption up front in the paper.\n4. The sequential game appears to be very similar to other approaches that have been proposed in the literature that estimate an eigenvector, subtract its contributions from the data, and then estimate the next eigenvector (see, e.g., Allen-Zhu and Li, 2017 and Raja and Bajwa, 2020). Such approaches of course suffer from the fact that they require distinct eigenvalues, but they don't require any QR decomposition. There is however no discussion of the connections between such approaches and the proposed sequential game.\n5. Why is the decentralized game being called \"decentralized\"? Is there a distinction the authors are making between distributed and decentralized? What's the topology being considered by the authors in relation to this game and what exactly does \"broadcast($\\widehat{v}_i$)\" mean in terms of reaching out to other nodes? Some discussion of this would be useful.\n6. While the decentralized game has not been analyzed in this paper, the distributed variant of GHA has been analyzed in the literature; see \"Fast and communication-efficient distributed PCA\". It would be helpful for the authors to comment on the differences between their decentralized algorithm and this distributed GHA work.\n7. Why is \"the longest streak of consecutive vectors with angular error less than $\\pi/8$ radians\" the right metric for the experiments?\n8. The claim in Figure 3 that \"We omit Krasulina’s as it is only designed to find the top-$k$ subspace\" is not clear to this reviewer.\n9. It would be useful for the authors to discuss the use of $\\nabla^R_v$, rather than $\\nabla_{v_i}$, for updates in both algorithms.\n\n**Minor Comments**\n\n1. In my opinion, it is incorrect to say that PCA leads to interpretable features.\n2. The claim \"An exponential convergence rate in the full-batch setting is possible using Riemannian acceleration techniques\" is perhaps too ambitious, unless the authors are confident that this is doable, in which case one wonders why this was not shown in the paper.\n3. The experimental plots in the paper is too hard to see clearly. It might be a useful idea to add them to the appendix also, where they can be shown in larger sizes.\n\n***Post-discussion period comments***\n\nThe authors have satisfactorily addressed all of my comments as well as, in my opinion, comments of other reviewers. Based on the latest revised version of the paper, I am increasing my score to 8 (from 7). I believe this paper is worthy of publication in proceedings of ICLR 2021 and I recommend it as such.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel game-theoretic view on PCA which yields an algorithm (EigenGame; Algorithm 2) that allows evaluation of singular vectors in a decentralized manner. The proposed algorithm is significant in its scalability, as demonstrated in the experiment on a large-scale dataset (ResNet-200 activations). This paper is generally clearly written, and in particular Section 2 provides an easy-to-follow reasoning leading to the proposed game-theoretic reformulation of PCA. I felt that the later sections are a bit condensed, including the figures. In the authors response major concerns raised by the reviewers have been appropriately addressed. I would thus recommend acceptance of this paper.

What I found particularly interesting in their game-theoretic reformulation is that in the utility functions shown in (6) the orthogonality constraints $\hat{u}_j^\top\hat{u}_i=0$ have been removed and replaced with the soft constraints represented as the regularizer terms encouraging the orthogonality. Although several alternative forms for the regularizers would be possible, it is this particular form that allows an efficient gradient-ascent algorithm which does not require explicit orthonormalization or matrix inversion is straightforwardly parallelizable.

Pros:
- Provides a novel game-theoretic reformulation of PCA.
- Proposes a sequential algorithm and a decentralized algorithm for PCA on the basis of the game-theoretic reformulation.
- Provides theoretical guarantee for the global convergence of the sequential algorithm.
- Demonstrates that the proposed decentralized algorithm is scalable to large-scale problems.

Cons:
- The latter statement of Theorem 4.1 requires conditions on the initialization, which are hard to satisfy in high-dimensional settings.
- Significance of the proposed game-theoretic formulation in the context of game theory does not seem to be well explored.

Decision: Accept (Oral)