EigenGame Unloaded: When playing games is better than optimizing

2021/02/08 by Ian Gemp, Gemp, Ian, Brian McWilliams +5 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Cluster analysis #Complex Network Analysis Techniques #Computation #Computer science #Context (archaeology) #Convergence (economics) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Opinion Dynamics and Social Influence #Parallel computing #Parallelism (grammar) #Perspective (graphical) #Sample (material) #Theoretical computer science #cs.AI #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2102.04152

published in arXiv (Cornell University) (Cornell University) · Published in ICLR '22

openalex publication_date 2021/02/08 · arxiv created 2022/03/22 · arxiv updated 2022/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• A Global Geometric Framework for Nonlinear Dimensionality Reduction
• Nonlinear Dimensionality Reduction by Locally Linear Embedding
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Eigenvalue computation in the 20th century
• A tutorial on spectral clustering
• Simplified neuron model as a principal component analyzer
• Spectral Normalization for Generative Adversarial Networks
• Towards a Human-like Open-Domain Chatbot

Cited by

• Eigenfunction Extraction for Ordered Representation Learning
• Revisiting Orbital Minimization Method for Neural Operator Decomposition
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning

Related

• EigenGame: PCA as a Nash Equilibrium
• A Generalized EigenGame with Extensions to Multiview Representation Learning
• Note on Computing Ratings from Eigenvectors
• Nash Equilibria via Stochastic Eigendecomposition
• Shapley-Snow kernels, multiparameter eigenvalue problems and stochastic games