Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the problem of finding top-k eigenvalues of the symmetric generalized eigenvalue problem (SGEP). It proposes a game-theoretic formulation whose Nash equilibrium is the top-k eigenvalues of SGEP. Using this new result, the authors develop a parallelizable algorithm suitable for tackling SGEP with streaming data sets. It proves the asymptotic convergence of the proposed algorithm and show how to achieve O(dk) runtime complexity. 
strength_and_weaknesses: Strength:
1. The paper is clearly motivated and written. It is a pleasure to read.
2. The game-theoretic formulation is novel, which motivates the development of the novel algorithm.
3. The proposed algorithm is equipped with strong convergence guarantees.
4. The proposed algorithm is suitable for parallelization and can achieve O(dk) runtime complexity, which outperforms O(d^2k) in state-of-the-art algorithms.

Weakness:
1. It seems that the convergence guarantee of the stochastic version of the algorithm is missing.
2. Can this approach be applied to general non-symmetric GEP? 
clarity,_quality,_novelty_and_reproducibility: Quality: High
Clarity: Overall good. It would be better to add the keyword "symmetric" in the title. 
Originality: High
summary_of_the_review: This paper proposes a game-theoretic formulation for SGEP. Based on the novel result that the Nash equilibrium of the formulation is the top-k eigenvalues of SGEP, the authors propose a novel algorithm, which shed new light on many problems that can be equivalently formulated as SGEP. The full-batch version of the proposed algorithm is equipped with theoretical guarantee. It is also applicable to streaming data set with seemingly good numerical performance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work provides an algorithm for identifying the top-$k$ generalized eigenvalues for a pair of symmetric positive definite matrices $A$ and $B$. The algorithm works by reducing this problem to finding a Nash equilibrium to a multi-player game. For this game the authors prove that the gradient ascent algorithm provably converges asymptotically to the top-$k$ generalized eigenvalues. 

The authors also seek to extend their algorithm to the stochastic setting where matrices $A$ and $B$ are accessible through stochastic estimates of their vector products via batching. They propose several modifications to their original objective that addresses several problems that arise with providing unbiased gradient estimates. While their modifications lead to unbiased estimators, they also make a complete and formal analysis harder and thus they leave it for future work. Empirically though, they do observe convergence on problems 1000x larger than the ones studied by prior work.

The ability to have independent machines processing independent mini-batches of $A$ and $B$, allows for low per-iteration complexity $O(dk)$ as compared to prior state of the art which requires $O(d^2k)$. The key is that matrix vector products cost $O(d)$ instead of $O(d^2)$ when considering minibatches of $O(1)$ samples. 
strength_and_weaknesses: This work has three major strengths. First, the problem of generalized eigenvalue problem and its importance to the machine learning community is thoroughly motivated. Second, although there have been several works studying game-theoretic solutions to the standard (non-generalized) eigenvalue problem, these approaches are not directly applicable since the generalized eigenvalue problem is not equivalent to a standard eigenvalue problem for a symmetric positive definite $A$. Third, a direct generalization of previous approaches (for example using Equation (4) or (5)) poses unique challenges when applied to the stochastic (mini-batch) setting. Up to the technical issues outlined in Appendix E.2, the proposed approach resolves these challenges.

Regarding weaknesses, there are some points in this work that could benefit from additional elaboration.

a) $O(dk)$ iteration complexity property
The way I understand it, every algorithm that uses matrix vector products and has as many machines per player as the datapoints in the batch of $A$ and $B$ also avoids the $O(kd^2)$ factor in their per-iteration analysis. Effectively, it seems to me that the key claim is that the proposed algorithm only uses matrix vector products whereas prior art does not. I think clarifying if this is really the case and why prior work cannot adopt the same matrix-vector product interface would help. 

Secondarily, as stated the result has some limitations. It is unclear how setting the batch size to be equal to the machine count per player affects the number of iterations required. It is not clear if we are trading off faster iterations and higher iteration counts. 

b) Comparison with top-1 generalized eigenvector + deflation
This theoretical analysis of this work a lot of times argues that given (approximate) convergence of players $i < j$, player $j$ can approximately find the $j$th generalized eigenvector. To me this seems very similar to how we can use power iteration and variants to find the top eigenvector, apply a deflation step and then find the next eigenvector.

It is not clear to me if one could apply an algorithm for a top-1 generalized eigenvector like Bhatia et al. (2018) and with an appropriate deflation step find the next one and so forth. Is this actually the case? If so what are the limitations? If not, why?

A key advantage I can see is that here all players work concurrently whereas the other approach would find the eigenvectors sequentially. The theoretical analysis however does not seem to take advantage of that. Maybe an experimental comparison between updating all players concurrently and only updating after the convergence of previous players would help clarify this point to the reader.


clarity,_quality,_novelty_and_reproducibility: Regarding clarity, I refer the authors to points a) and b) above. Beyond the two points above, both the quality and the clarity of the writing looks good to me. 

Regarding novelty, although the skeleton of the analysis and the main tools (e.g. penalty terms, error propagation etc.) are the same with the prior work for the standard (non-generalized) eigenvalue problem, the generalized eigenvalue problem poses unique challenges (providing unbiased gradient estimators) that this work addresses, at least partially on the theoretical front. On the empirical side, the proposed approach is shown to outperform the previous state of the art approaches.

Regarding reproducibility, the authors detail the hyper-parameters used in their experiments. They also plan to open source their code, making their experimental claims fully auditable by peers.  

summary_of_the_review: I recommend this paper for acceptance. I am inclined to raise my score higher if the authors improve on the points raised in the "Strengths and Weaknesses" section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents an algorithm to compute the $k$ dominant eigenpairs of a streamed matrix. The algorithm is based on an optimization viewpoint where each individual eigenpair is maximizing a separate cost function. Numerical experiments verify the effectiveness of the proposed scheme.
strength_and_weaknesses: I tried my best to check the proofs and they appear correct.

Strengths:
-) The paper introduces a nice setting/idea for eigenvalue computations.
-) Lots of intuition is presented and discussed.
-) Results demonstrate that the proposed method is effective.

-) The difference between eigengame-PCA and the current work is not properly explained.
-) The authors should discuss in more depth other optimization-based eigenvalue solvers such as TraceMIN or LOBPCG. 
-) It's likely I missed something here, but why do the authors need to include the "Nash's equilibrium" phrase throughout their paper? 
It seems to me that the algorithm developed is nothing more than an optimization-based eigenvalue solver for streamed datasets; which is absolutely fine for a publication. What am I missing?
-) The discussion about computational complexity is a bit confusing; why is $O(dk)$ after we parallelize across M=b batches? Is the cost per iteration of for-k loop only $O(d)$? I thought it would $O(dk)$ (which means the paralleized complexity is $O(dk^2)$). I must be missing something here.
-) My main concern is the following: are there really situations where I can not access the matrices A and B in a sequential batched manner? Because in this case the authors can use standard numerical linear algebra optimization-based approaches (i.e., out-of-core computing). In other words, in what applications $A$ and $B$ are accessed truly randomly?
clarity,_quality,_novelty_and_reproducibility: All good.
summary_of_the_review: The proposed method is interesting and the paper is well-written. My main concerns are: a) similarity with the PCA case, and b) realistic application in modern problems.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is concerned with solving the symmetric generalized eigenvalue problem $Av = \lambda B v$ , which generalizes various other well known problems like PCS, CCA, ICA etc. A particular approach chosen is to consider a corresponding game between k players and the rewards are set such that the Nash equilibrium is the top-k solution. What we already know about this problem: If we can invert B in the equation above, then SGEP can be solved as an SVD problem. This however loses structure (for example A and B are symmetric in SGEP) and therefore previous game theoretic approaches to solving SVD do not apply here.

Like mentioned above, the approach in this work is to construct a game between k players each selecting a strategy $v_i$. Their first main contribution is in constructing a sound utility function such that the Nash equilibrium of this game is the top-k SGEP solution. Intuitively, the utility for player i conditioned on players j < i (henceforth parents of i) is designed to: (1) incentivize finding directions that have large eigenvalues (called reward) (2) but simultaneously choosing directions which are far from directions chosen by the parents. 

 To show that these rewards are sound, the work first shows that assuming $B^{-1}A$ has nice spectrum, and the parents converge to correct eigenvectors (called exact parents henceforth), the unique generalized eigenvector $v_i$ maximizes the player i's utility. This follows from noting that for the exact parents, the penalty term linearizes after a re-parameterization (and the reward term is already linear in the said re-parameterization). This shows that the top-k eigenvectors form the strict Nash equilibrium of this game. 

Another particular important aspect of this utility design is that every local maximum is a global maximum here which follows from previous work. Together with above result, this suggests a simple gradient based algorithm. The work next shows under deterministic setting (A and B are known), this simple gradient based algorithm asymptotically converges. This requires proving that the error in eigenvectors for parents lead to bounded error in the solutions for the children. This result borrows ideas from previous work [Gemp et al. 2021].

Some care is needed to extend this to stochastic/streaming setting, we need the terms appearing in the denominator to be nicely conditioned and have to be handled appropriately. This algorithm has a per iteration complexity $dk$ which improves over the previous state-of-the-art per iteration complexity $d^2k$. This is followed by extensive experiments on CCA and ICA showing in practice this method is competitive. 
strength_and_weaknesses: I think the writing in the paper could use some more work. Especially since most of the claims have short and simple proofs, it would be nice to include some more intuition about them in the main text. I verified most of the proofs in the supplementary materials. Some other concerns I have:
1. Theorem 1 (which follows from Lemma 1) does not require Proposition 1. And therefore Proposition 1 should not be before Definition 1 and Theorem 1. In fact, its only ever used in showing that Algorithm 2's updates are unbiased. 

2. Lemma 1: $w_p$ are not defined. It would be nice to say they are arbitrary real coefficients and give some exposition on your end goal. For example, we now consider $\hat v_i$ as arbitrary linear combination of $v_i$'s. We will show that maximizing the utility for player is same as solving the following linear program: ...

3. Proposition 1: It would be nice to give a more definite reference for EigenGame (and results implying the utility function is cosine).


I think the claims about improving the per-iteration complexity should be followed by explanation about its implication on total time complexity. I think it should be noted that this algorithm does not have convergence rates and in fact, the error from parents on the time-complexity would show up in the number of iterations needed for the algorithm to converge. This is real and looking through proof of Theorem 2, it seems like the number of iterations even in the deterministic case scale exponentially in $k$ (since the $\epsilon$ error from parents lead to $\sqrt{\epsilon}$ error in children's fixed point).

That said, I would like to emphasize that the above comment does not dilute the contribution of this work.
I think the paper makes a good technical contribution to an important problem.
clarity,_quality,_novelty_and_reproducibility: 
Other than the issues raised above, I do not have any other comments. 
summary_of_the_review: I think this is a good contribution to understanding game theoretic version of various problems like ICA, PCA, CCA etc. Moreover, this work provides a very practical algorithm.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers solving the symmetric generalized eigenvalue problem (SGEP), which is of the form $Av = \lambda Bv,$ where $A$ is a symmetric matrix and $B$ is symmetric positive definite. This setting generalizes PCA/SVD problems and is motivated well by learning applications such as canonical correlation analysis, independent component analysis, and computing successor features in reinforcement learning, provided in the paper. The assumptions about $A$ and $B$ are crucial in ensuring eignevalues are real and eigenvectors are $B$-orthogonal.

The paper introduces a new problem formulation for computing top $k$ eigenvectors of SGEPs corresponding to a multi-player game. The paper shows that the solutions to such games (Nash equilibria) correspond to the top $k$ eigenvectors of corresponding SGEPs. The paper then provides an algorithm for solving this problem and shows that it converges to the desired solution in an asymptotic sense. Additionally, the paper discusses different implementation issues and shows how to reduce the per iteration complexity compared to state-of-the-art by a factor scaling linearly with the problem dimension $d$. Finally, the paper provides numerical experiments that demonstrate the proposed approach is more effective than state of the art, allowing handling problem dimensions higher by a factor of a 1000 when doing an empirical analysis of neural similarity on activations. 

The paper is very well written, easy to follow, and represents a well rounded piece of work. As such, it is a good fit for ICLR. 
justification_for_why_not_higher_score: While interesting, the convergence results are only asymptotic. The game theoretic perspective on computing eigenvectors/eigenvalues is not entirely novel: there are other papers providing similar results but for less general problems. 
justification_for_why_not_lower_score: The work is interesting conceptually, there are theoretical results that justify the proposed algorithm, the algorithm is well motivated from the implementation perspective with care taken when considering modern computational architectures, and the experiments show significant improvement over the state of the art, so clearly the paper deserves to be in this pile.
Decision: Accept: notable-top-25%