EigenGame Unloaded: When playing games is better than optimizing
This work provides a more robust and scalable method for eigendecomposition, which is crucial for researchers and practitioners working with large datasets in machine learning and data analysis.
This paper addresses the biased updates in the original EigenGame when using minibatches, proposing an unbiased stochastic update that is asymptotically equivalent. This new method allows for greater parallelism and experimentally outperforms the original EigenGame, enabling applications to massive datasets and spectral clustering.
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.