Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
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. 

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

Looking 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: Strengths:
- 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. 
- 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. 
- 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.
- 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.  

Weaknesses:
- 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)
- 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

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

Theorem 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_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.
review_title: null

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

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

I 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.
   
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.
review_title: null

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)