Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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:

- 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)
- 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)
- Convergence analysis of the sequential algorithm under a restrictive set of assumptions (Theorem 4.1)
- Establishment of the equivalence between the decentralized algorithm and the Generalized Hebbian Algorithm (GHA) of Sanger (Proposition H.1)

Overall, 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.

**Major Comments**

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. Why is "the longest streak of consecutive vectors with angular error less than $\pi/8$ radians" the right metric for the experiments?
8. 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.
9. 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.

**Minor Comments**

1. In my opinion, it is incorrect to say that PCA leads to interpretable features.
2. 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.
3. 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.

***Post-discussion period comments***

The 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.
review_title: A comprehensive and interesting take on the PCA problem; needs some more refinement, which can possibly be managed in a revision

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 
A. Summarize
This 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.
Furthermore, 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. 
In 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. 

B. Strength
1.  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. 
2. Besides the algorithm itself, the proposed method also opens new doors for other interesting future research other than recovering principle components.
3. 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. 

C. Weakness:
1. 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?

D. Justification of score:
This 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.


review_title: A novel decentralized PCA derived from the perspective of Nash equilibrium.

final_score: rating: 7: Good paper, accept
review_content: 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.

Points that can be improved:

- 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.

- 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.

- section 5: missing methods are e.g. the power method, Lanczos method, Jacobi etc.

- 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








 
review_title: PCA as a Nash equilibrium

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)