Year: 2021

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

heading: 1 INTRODUCTION
text: Large, high-dimensional datasets containing billions of samples are commonplace. Dimensionality reduction to extract the most informative features is an important step in the data processing pipeline which enables faster learning of classifiers and regressors (Dhillon et al., 2013), clustering (Kannan and Vempala, 2009), and interpretable visualizations. Many dimensionality reduction and clustering techniques rely on eigendecomposition at their core including principal component analysis (Jolliffe, 2002), locally linear embedding (Roweis and Saul, 2000), multidimensional scaling (Mead, 1992), Isomap (Tenenbaum et al., 2000), and graph spectral clustering (Von Luxburg, 2007).
Numerical solutions to the eigenvalue problem have been approached from a variety of angles for centuries: Jacobi’s method, Rayleigh quotient, power (von Mises) iteration (Golub and Van der Vorst, 2000). For large datasets that do not fit in memory, approaches that access only subsets—or minibatches—of the data at a time have been proposed.
Recently, EigenGame (Gemp et al., 2021) was introduced with the novel perspective of viewing the set of eigenvectors as the Nash strategy of a suitably defined game. While this work demonstrated an algorithm that was empirically competitive given access to only subsets of the data, its performance degraded with smaller minibatch sizes, which are required to fit high dimensional data onto devices.
One path towards circumventing EigenGame’s need for large minibatch sizes is parallelization. In a data parallel approach, updates are computed in parallel on partitions of the data and then combined such that the aggregate update is equivalent to a single large-batch update. The technical obstacle preventing such an approach for EigenGame lies in the bias of its updates, i.e., the divide-and-conquer EigenGame update is not equivalent to the large-batch update. Biased updates are not just a theoretical nuisance; they can slow and even prevent convergence to the solution (made obvious in Figure 4).
In this work we introduce a formulation of EigenGame which admits unbiased updates which we term µ-EigenGame. We will refer to the original formulation of EigenGame as α-EigenGame.3
µ-EigenGame and α-EigenGame are contrasted in Figure 1. Unbiased updates allow us to increase the effective batch size using data parallelism. Lower variance updates mean that µ-EigenGame should converge faster and to more accurate solutions than α-EigenGame regardless of batch size. In Figure 1a (top), the density of the shaded region shows the distribution of steps taken by the stochastic variant of each algorithm after 100 burn-in steps. Although the expected path of α-EG is
3µ signifies unbiased or unloaded and α denotes original.
1The trajectory when updating with E[X>t Xt]. 2Overestimation is expected by Jensen’s: E[ 1
X ] ≥ 1E[X] .
slightly more direct, its stochastic variant has much larger variance. Figure 1a (bottom) shows that with increasing iterations, the µ-EG trajectory approaches its expected value whereas α-EG exhibits larger bias. Figure 1b further supports µ-EigenGame’s reduced bias with details in Sections 3 and 4.
Our contributions: In the rest of the paper, we present our new formulation of EigenGame, analyze its bias and propose a novel unbiased parallel variant, µ-EigenGame with stochastic convergence guarantees. µ-EigenGame’s utilities are distinct from α-EigenGame and offer an alternative perspective. We demonstrate its performance with extensive experiments including dimensionality reduction of massive data sets and clustering a large social network graph. We conclude with discussions of the algorithm’s design and context within optimization, game theory, and neuroscience.

heading: 2 PRELIMINARIES AND RELATED WORK
text: In this work, we aim to compute the top-k right singular vectors of dataX , which is either represented as a matrix, X ∈ Rn×d, of n d-dimensional samples, or as a d-dimensional random variable. In either case, we assume we can repeatedly sample a minibatch Xt from the data of size n′ < n, Xt ∈ Rn
′×d. The top-k right singular vectors of the dataset are then given by the top-k eigenvectors of the (sample) covariance matrix, C = E[ 1n′X > t Xt] = E[Ct].
For small datasets, SVD is appropriate. However, the time, O(min{nd2, n2d}), and space, O(nd), complexity of SVD prohibit its use for larger datasets (Shamir, 2015) including when X is a random variable. For larger datasets, stochastic, randomized, or sketching algorithms are better suited. Stochastic algorithms such as Oja’s algorithm (Oja, 1982; Allen-Zhu and Li, 2017) perform power iteration (Rutishauser, 1971) to iteratively improve an approximation, maintaining orthogonality
of the eigenvectors typically through repeated QR decompositions. Alternatively, randomized algorithms (Halko et al., 2011; Sarlos, 2006; Cohen et al., 2017) first compute a random projection of the data onto a (k + p)-subspace approximately containing the top-k subspace. This is done using techniques similar to Krylov subspace iteration methods (Musco and Musco, 2015). After projecting, a call to SVD is then made on this reduced-dimensionality data matrix. Sketching algorithms (Feldman et al., 2020) such as Frequent Directions (Ghashami et al., 2016) also target learning the top-k subspace by maintaining an overcomplete sketch matrix of size (k + p)× d and maintaining a span of the top subspace with repeated calls to SVD. In both the randomized and sketching approaches, a final SVD of the n× (k + p) dataset is required to recover the desired singular vectors. Although the SVD scales linearly in n, some datasets are too large to fit in memory; in this case, an out-of-memory SVD may suffice (Haidar et al., 2017). For this reason, the direct approach of stochastic algorithms, which avoid an SVD call altogether, is appealing when processing very large datasets.
Algorithm 1 µ-EigenGameR
1: Given: data stream Xt ∈ Rn ′×d, vectors v̂0i ∈
Sd−1, step sequence ηt, and iterations T . 2: v̂i ← v̂0i for all i 3: for t = 1 : T do 4: parfor i = 1 : k do 5: rewards← 1n′X > t Xtv̂i 6: penalties ← 1 n′ ∑ j<i〈Xtv̂i, Xtv̂j〉v̂j 7: ∇̃µi ← rewards− penalties 8: ∇̃µ,Ri ← ∇̃ µ i − 〈∇̃ µ i , v̂i〉v̂i 9: v̂′i ← v̂i + ηt∇̃ µ,R i
10: v̂i ← v̂ ′ i ||v̂′i|| 11: end parfor 12: end for 13: return all v̂i
A large literature on distributed approaches to PCA exists (Liang et al., 2014; Garber et al., 2017; Fan et al., 2019). These typically follow the pattern of computing solutions locally and then aggregating them in a single round (or minimal rounds) of communication. The modern distributed machine learning setting which has evolved to meet the needs of deep learning is fundamentally different. Many accelerators joined with fast interconnects means the cost of communication is low compared to the cost of a single update step, however existing approaches to distributed PCA cannot take full advantage of this.
Notation: We follow the same notation as Gemp et al. (2021). Variables returned by an approximation algorithm are distinguished from the true solutions with hats, e.g., the column-wise matrix of eigenvectors V̂ approximates V . We order the columns of V such that the ith column, vi, is the eigenvector with the ith largest eigenvalue λi. The set of all eigenvectors {vj} with λj larger than λi, namely vi’s parents, will be denoted by vj<i. Similarly, sums over subsets of indices may be abbreviated as ∑ j<i = ∑i−1 j=1. The set of all parents and children of vi are denoted by v−i. Let the ith eigengap gi = λi − λi+1. We assume the standard Euclidean inner product 〈u, v〉 = u>v and denote the unit-sphere and simplex in ambient space Rd with Sd−1 and ∆d−1 respectively.
α-EigenGame. We build on the algorithm introduced by Gemp et al. (2021), which we refer to here as α-EigenGame. This algorithm is derived by formulating the eigendecomposition of a symmetric positive definite matrix as the Nash equilibrium of a game among k players, each player i owning the approximate eigenvector v̂i ∈ Sd−1. Each player is also assigned a utility function, uαi (v̂i|v̂j<i), that they must maximize:
uαi (v̂i|v̂j<i) = Var︷ ︸︸ ︷ v̂>i Cv̂i− ∑ j<i Align-penalty︷ ︸︸ ︷ 〈v̂i, Cv̂j〉2 〈v̂j , Cv̂j〉 . (1)
These utilities balance two terms, one that rewards a v̂i that captures more variance in the data and a second term that penalizes v̂i for failing to be orthogonal to each of its parents v̂j<i (these terms are indicated with Var and Align-penalty in equation (1)). In α-EigenGame, each player simultaneously updates v̂i with gradient ascent, and it is shown that this process converges to the Nash equilibrium. We are interested in extending this approach to the data parallel setting where each player i may distribute its update computation over multiple devices.

heading: 3 A SCALABLE UNBIASED ALGORITHM
text: We present our novel modification to α-EigenGame called µ-EigenGame along with intuition, theory, and empirical support for critical lemmas. We begin with identifying and systematically removing the bias that exists in the α-EigenGame updates. We then explain how removing bias allows us to exploit modern compute architectures culminating in the development of a highly parallelizable algorithm.
3.1 α-EIGENGAME’S BIASED UPDATES
Consider partitioning the sample covariance matrix Ct into a sum ofmmatrices as Ct = 1n′X > t Xt = 1 m ∑ m m n′X > tmXtm = 1 m ∑ m Ctm. For sake of exposition, we drop the additional subscript t on C in what follows. We would like α-EigenGame to parallelize over these partitions. However, the gradient of uαi with respect to v̂i does not decompose cleanly over the data partitions:
∇αi ∝ Var︷︸︸︷ Cv̂i − ∑ j<i Align-penalty︷ ︸︸ ︷ v̂>i Cv̂j v>j Cv̂j Cv̂j = 1 m ∑ m [ Cmv̂i − ∑ j<i v̂>i Cv̂j v̂>j Cv̂j Cmv̂j ] . (2)
We include the superscript α on the EigenGame gradient to differentiate it from the µ-EigenGame direction later. The nonlinear appearance of C in the penalty terms makes obtaining an unbiased gradient difficult. The quadratic term in the numerator of equation (2) could be made unbiased by using two sample estimates ofC, one for each term. But the appearance of the term in the denominator does not have an easy solution. Cm is likely singular for small n′ (n′ < d) which increases the likelihood of a small denominator, i.e., a large penalty coefficient (boxed), if we were to estimate the denominator with samples. The result is an update that emphasizes penalizing orthogonality over capturing data variance. Techniques exist to reduce the bias of samples of ratios of random variables, but to our knowledge, techniques to obtain unbiased estimates are not available. This was conjectured by Gemp et al. (2021) as the reason for why α-EigenGame performed worse with small minibatches.
3.2 REMOVING α-EIGENGAME’S BIAS
It is helpful to rearrange equation (2) to shift perspective from estimating a penalty coefficient (in red) to estimating a penalty direction (in blue):
∇αi ∝ 1
m ∑ m [ Cmv̂i − ∑ j<i v̂>i Cmv̂j Cv̂j v̂>j Cv̂j ] . (3)
The penalty direction in equation (3) is still difficult to estimate. However, consider the case where v̂j is any eigenvector of C with associated (unknown) eigenvalue λ′. In this case, Cv̂j = λ′v̂j and the penalty direction (in blue) simplifies to v̂j because ||v̂j || = 1. While this assumption is certainly not met at initialization, α-EigenGame leads each v̂j towards vj , so we can expect this assumption to be met asymptotically.
This intuition motivates the following µ-EigenGame update direction for v̂i with inexact parents v̂j (compare orange in equation (4) to blue in equation (3)):
∆µi = Cv̂i − ∑ j<i (v̂>i Cv̂j)v̂j = 1 m ∑ m [ Cmv̂i − ∑ j<i (v̂>i Cmv̂j)v̂j ] . (4)
We use ∆ instead of ∇ because the direction is not a gradient (discussed later). Notice how the strictly linear appearance of C in µ-EigenGame allows the update to easily decompose over the data partitions in equation (4). The µ-EigenGame update satisfies two important properties. Lemma 1 (Asymptotic equivalence). The µ-EigenGame direction, ∆µi , with exact parents (v̂j = vj ∀ j < i) is equivalent to α-EigenGame.
Proof. We start with α-EigenGame and add a superscript e to its gradient to emphasize this is the gradient computed with exact parents (v̂j = vj). Then simplifying, we find
∇α,ei ∝ Cv̂i − ∑ j<i v̂>i Cvj v>j Cvj Cvj = Cv̂i − ∑ j<i v̂>i Cvj v>j λjvj λjvj = Cv̂i − ∑ j<i (v̂>i Cvj)vj = ∆ µ i . (5)
Therefore, once the first (i − 1) eigenvectors are learned, learning the ith eigenvector with µEigenGame is equivalent to learning with α-EigenGame.
Lemma 2 (Zero bias). Unbiased estimates of ∆µi can be obtained with samples from p(X).
Proof. Let X ∼ p(X) where X ∈ Rd and p(X) is the uniform distribution over the dataset. Then
E[∆µi ] = E[XX >]v̂i − ∑ j<i (v̂>i E[XX>]v̂j)v̂j = Cv̂i − ∑ j<i (v̂>i Cv̂j)v̂j . (6)
where all expectations are with respect to p(X).
These two lemmas provide the foundation for a performant algorithm. The first enables convergence to the desired solution, while the second facilitates scaling to larger datasets. Algorithm 1 presents pseudocode for µ-EigenGame where computation is parallelized over the k players.
3.3 MODEL AND DATA PARALLELISM
In our setting we have a number of connected devices. Specifically we consider the parallel framework specified by TPUv3 available in Google Cloud, however our setup is applicable to any multi-host, multi-device system. The α-EigenGame formulation (Gemp et al., 2021) considers an extreme form of model parallelism (Figure 2a) where each device has its own unique set of eigenvectors.
In this work we further consider a different form of model and data parallelism which is directly enabled by having unbiased updates (Figure 2b). This enables µ-EigenGame to deal with both high-dimensional problems as well as massive sample sizes. Here each set of eigenvectors is copied on M devices. Update directions are computed on each device individually using a different data stream and then combined by summing or averaging. Updates are applied to a sin-
gle copy and this is duplicated across theM−1 remaining devices. In this way, updates are computed using an M× larger effective batch size while still allowing device-wise model parallelism. This setting is particularly useful when the number of samples is very large. This form of parallelism is not possible using the original EigenGame formulation since it relies on combining unbiased updates. In this sense, the parallelism discussed in this work generalizes that introduced by Gemp et al. (2021).
Note that we also allow for within-device parallelism. That is, each vi in Figure 2 is a contiguous collection of eigenvectors which are updated independently, in parallel, on a given device (for example using vmap in Jax). We provide pseudocode in Algorithm 2 in the appendix which simply augments Algorithm 1 with an additional parallelized for-loop and aggregation step over available devices. We also provide detailed Jax pseudo-code for parallel µ-EigenGame in Appendix F. We compare the empirical scaling performance of µ-EigenGame against α-EigenGame on a 14 billion sample dataset in section 5.

heading: 4 SVD AS THE SOLUTION TO A NEW EIGENGAME
text: We theoretically examine the µ-EigenGame algorithm and 1) prove that, using only minibatches of data, µ-EigenGame converges globally to the true eigenvectors, which 2) comprise the Nash equilibrium of a novel game formulation we recover through deriving pseudo-utility functions from update rules. Beyond proving specific theoretical properties of µ-EigenGame, we believe these proof techniques may be of wider interest to the community.

heading: 4.1 CONVERGENCE TO SVD
text: The asymptotic equivalence of µ-EigenGame to α-EigenGame ensures µ-EigenGame is globally, asymptotically convergent and its unbiased updates ensure it is scalable. Proof in appendix C. Theorem 1 (Global convergence). Given a positive definite covariance matrixC with the top-k eigengaps positive and a square-summable, not summable step size sequence ηt (e.g., 1/t), Algorithm 1 converges to the top-k eigenvectors asymptotically (limT→∞) with probability 1.
This stochastic asymptotic convergence result is complimentary to the deterministic (full-batch) finite-sample result in Gemp et al. (2021) where each v̂i is learned in sequence. In contrast, the proof above applies when learning all v̂i in parallel. We leave finite-sample convergence to future work (Durmus et al., 2020).
4.2 SVD IS NASH OF µ-EIGENGAME
We arrived at µ-EigenGame by analyzing and improving properties of the α-EigenGame update. However, the µ-EigenGame update direction is linear in each v̂i. This suggests we may be able to design a pseudo-utility function for it. Rearranging the update direction from equation (4) as
∆µi = Cv̂i − ∑ j<i v̂j(v̂ > j Cv̂i) = [ I − ∑ j<i v̂j v̂ > j ] Cv̂i = ∇̃µi (7)
reveals that we can reverse-engineer the following utility function
uµi = v̂ > i
[ deflation︷ ︸︸ ︷ I − ∑ j<i v̂j v̂ > j ] C [v̂i] (8)
where is the stop gradient operator commonly used in deep learning packages. As the name implies, stops gradients from flowing through its argument so that equation (8) appears linear in v̂i instead of quadratic when differentiating the expression. In light of this, we have renamed ∆µi to ∇̃ µ i to emphasize that it is a pseudo-gradient of uµi . Note that without the stop gradient, the true gradient of uµi would be [A+A >]v̂i rather than Av̂i where A = [I − ∑ j<i v̂ > j v̂j ]C. We analyze this alternative in Appendix H.1 and find it, interestingly, to perform worse than µ-EigenGame empirically.
The utility function uµi has an intuitive meaning. It is the Rayleigh quotient for the matrix Ci = [I− ∑ j<i v̂
>v̂j ]C, which gives the covariance after the subspace spanned by v̂j<i has been removed. In other words, player i is directed to find the largest eigenvalue in the orthogonal complement of the approximate top-(i− 1) subspace. This approach is known as “deflating" the matrix C. Figure 1b illustrates µ-EigenGame’s reduced bias when estimating the new utility function (and resulting optimum) from an average over minibatches. Definition 1 (µ-EigenGame). Let µ-EigenGame be the game with players i ∈ {1, . . . , k}, their respective strategy spaces v̂i ∈ Sd−1, and their corresponding utilities uµi as defined in equation (8). Theorem 2. Top-k SVD is the unique Nash of µ-EigenGame given symmetric C with the top-k eigengaps positive.
Proof. We will show by induction that each vi is the unique best response to v−i, which implies they constitute the unique Nash equilibrium. First, consider player 1’s utility. It is the Rayleigh quotient of C because v̂1 is constrained to the unit-sphere, i.e., u µ 1 = v̂ > 1 Cv̂1 = v̂>1 Cv̂1 v̂>1 v̂1
. Therefore, we know v1 maximizes u µ 1 and the maximizer is unique because its eigengap g1 > 0. In game theory parlance, v1 is a best response to v−1. The proof continues by induction. The utility of player i is uµi = v̂ > i [I − ∑ j<i vjv > j ]Cv̂i, which is the Rayleigh quotient with the subspace spanned by the top (i− 1) eigenvectors removed. Therefore, the maximizer of uµi is the largest eigenvector in the remaining subspace, i.e., vi. As before, gi > 0, so this maximizer is unique. This shows that each vi is the unique best response to v−i, therefore, the set of vi forms the unique Nash.
Notice how the induction proof of Theorem 2 relies on a) the hierarchy of vectors (v1 does not depend on v−1) and b) the fact that u µ i need only be a sensible utility when all player i’s parents
are eigenvectors. We revisit this in conjunction with Figure 5b later in discussion section 6.1 to aid researchers in the design of future approaches.
The Nash property is important because it enables the use of any black-box procedure for computing best responses. Like prior work, we develop a gradient method for optimizing each utility, however, that is not a requirement. Any approach suffices if it can efficiently compute a best response.

heading: 5 EXPERIMENTS
text: As in EigenGame, we omit the projection of gradients onto the tangent space of the sphere; specifically, we omit line 8 in Algorithm 1. As discussed in Gemp et al. (2021), this has the effect of intelligently adapting the step size to use smaller learning rates near the fixed point. To ease comparison with previous work, we count the longest correct eigenvector streak as introduced by Gemp et al. (2021), which measures the number of eigenvectors that have been learned, in order, to within an angular threshold (e.g., π/8) of the true eigenvectors. We also measure how well the set of v̂i captures the top-k subspace with a normalized subspace distance: 1− 1/k · Tr(U∗P ) ∈ [0, 1] where U∗ = V V † and P = V̂ V̂ † (Tang, 2019). We provide additional experiments in Appendix A.
MNIST. We compare µ-EigenGame against α-EigenGame, GHA (Sanger, 1989), Matrix Krasulina (Tang, 2019), and Oja’s algorithm (Allen-Zhu and Li, 2017) on the MNIST dataset. We flatten each image in the training set to obtain a 60, 000× 784 dimensional matrix X . Figure 3 demonstrates µ-EigenGame’s robustness to minibatch size. It performs best in the longest streak metric and better than α-EigenGame in subspace distance. We attribute this improvement to its unbiased updates and additional acceleration effects which we discuss in detail in section H.2.
Meena conversational model. This dataset consists a subset of the 40 billion words used to train the transformer-based Meena language model (Adiwardana et al., 2020). The subset was preprocessed to remove duplicates and then embedded using the trained model.
The dataset consists of n ≈ 14 billion embeddings each with dimensionality d = 2560; its total size is 131TB. Due to its moderate dimensionality we can exactly compute the ground truth solution by iteratively accumulating the covariance matrix of the data and computing its eigendecomposition. On a single machine this takes 1.5 days (but is embarrassingly parallelizable with MapReduce).
We use minibatches of size 4,096 in each TPU. We do model parallelism across 4 TPUs so we see 16,384 samples per iteration. We test two additional degrees of data parallelism with 4× (16 TPUs, 65,536 samples) and 8× (32 TPUs, 131,072 samples) the amount of data per iteration respectively. We compute and apply updates using SGD with a learning rate of 5× 10−5 and Nesterov momentum with a factor of 0.9.
Figure 4 compares the mean performance of µ-EigenGame against α-EigenGame as a function of the degree of parallelism in computing the top k = 256 eigenvectors (standard errors computed over 5 random seeds). Each TPU is tasked with learning 32 contiguous eigenvectors. We see that increasing the degree of parallelism has no effect on the performance of α-EigenGame. As expected, it is unable to take advantage of the higher data throughput since its updates are biased and cannot be meaningfully linearly combined across copies. In contrast, the performance of µ-EigenGame scales with the effective batch size achieved through parallelism. µ-EigenGame (8×) is able to recover 256 eigenvectors in less than 40,000 iterations in 2 hours 45 minutes (approximately 0.5 epochs).
Spectral clustering on graphs. We conducted an experiment on learning the eigenvectors of the graph Laplacian of a social network graph (Leskovec and McAuley, 2012) for the purpose of spectral clustering. The eigenvalues of the graph Laplacian reveal several interesting properties as well such as the number of connected components, an approximation to the sparsest cut, and the diameter of a connected graph (Chung et al., 1994).
Given a graph with a set of nodes V and set of edges E , the graph Laplacian can be written as L = X>X where each row of the incidence matrix X ∈ R|E|×|V| represents a distinct edge; Xe=(i,j)∈E is a vector containing only 2 nonzero entries, a 1 at index i and a −1 at index j (Horaud, 2009). In this setting, the eigenvectors of primary interest are the bottom-k (λ|V|, λ|V|−1, . . .) rather than the top-k (λ1, λ2, . . .), however, a simple algebraic manipulation allows us to reuse a topk solver. By defining the matrix L− = λ∗I − L with λ∗ > λ1, we ensure L− 0 and the top-k eigenvectors of L− are the bottom-k of L. The update in equation (4) is transformed into ∇̃µi = (λ∗I − L)v̂i − ∑ j<i ( v̂>i (λ ∗I − L)v̂j ) v̂j . We provide efficient pseudo-code in Appendix G.
The Facebook graph consists of 134, 833 nodes, 1, 380, 293 edges, and 8 connected components, each formed by a set of Facebook pages belonging to a distinct category, e.g., Government, TV shows, etc. (Leskovec and Krevl, 2014; Rozemberczki et al., 2019). We add a single edge between every pair of components to create a connected graph. By projecting this graph onto the bottom 8 eigenvectors of the graph Laplacian using µ-EG (M = 1, n′ = ηt = |E| 1000 ) and then running k-means clustering (Pedregosa et al., 2011), we are able to recover the ground truth clusters (see Figure 5a) with 99.92% accuracy. The experiment was run on a single CPU.

heading: 6 DISCUSSION

heading: 6.1 UTILITIES TO UPDATES AND BACK
text: Figure 5b summarizes the relationships advising the designs of the various EigenGame algorithms. Starting from the α-EigenGame utility, its update is arrived at by simply following the standard gradient ascent paradigm. In noticing that stochastic estimates of the gradient are biased, we arrive at the µ-EigenGame update by considering how to remove this bias in a principled manner.
Sacrificing the exact steepest decent direction for a direction that allows unbiased estimates is a tradeoff that in this case has benefits. Also, while ∇̃µi is not a gradient (except with exact parents), the new penalties have properties (above) that make them intuitively more desirable than the originals; they are adaptive to the state of the system (discussed further in section H.2).
We derive pseudo-utilities with desired theoretical properties by integrating the new updates with help from the stop gradient operator. However, it is unlikely that this utility would be developed independently of these steps to solve the problem at hand (see Appendix H for more details). This suggests an alternative approach to algorithm design complementary to the optimization perspective: directly designing updates themselves which converge to the desired solution, reminiscent of previous paradigms that drove neuro-inspired learning rules.

heading: 6.2 BRIDGING HEBBIAN AND OPTIMIZATION APPROACHES
text: The Generalized Hebbian Algorithm (GHA) (Sanger, 1989; Gang et al., 2019; Chen et al., 2019) update direction for v̂i with inexact parents v̂j is similar to µ-EigenGame:
∆ghai = Cv̂i − ∑ j≤i (v̂>i Cv̂j)v̂j . (9)
C appears linearly in this update so GHA can also be parallelized. In contrast to µ-EigenGame, GHA additionally penalizes the alignment of v̂i to itself and removes the unit norm constraint on v̂i (not shown). Without any constraints, GHA overflows in experiments. We take the approach of Gemp et al. (2021) and constrain v̂i to the unit-ball (||v̂i|| ≤ 1) rather than the unit-sphere (||v̂i|| = 1). The connection between GHA and µ-EigenGame is interesting because unlike µ-EigenGame, GHA is a Hebbian learning algorithm inspired by neuroscience and its update rule is not motivated from the perspective of maximizing of a utility function. Game formulations of classical machine learning problems may provide a bridge between statistical and biologically inspired viewpoints.

heading: 7 CONCLUSION
text: We introduced µ-EigenGame, an unbiased, globally convergent, parallelizable algorithm that recovers the top-k eigenvectors of a symmetric positive definite matrix. We demonstrated the performance of µ-EigenGame on large scale dimension reduction and clustering problems. We discussed technical details of µ-EigenGame within the context of game theory, machine learning and neuroscience.
Like its predecessor, µ-EigenGame is a k-player, general-sum game allowing model parallelism over players; our unbiased reformulation allows even greater parallelism over data. Furthermore, the hierarchy and Nash property enable the exploration of more sophisticated best responses.
µ-EigenGame’s improved robustness to smaller minibatches makes it more amenable to being used as part of deep learning, optimization (Krummenacher et al., 2016), and regularization (Miyato et al., 2018) techniques which leverage spectral information of gradient covariances or Hessians. Graph spectral methods have also recently shown to be related to state-of-the-art representation learning algorithms (HaoChen et al., 2021) further cementing the importance of efficient SVD algorithms in modern machine learning.

Review summaries:
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.  

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.