EigenGame: PCA as a Nash Equilibrium
Abstract:
We present a novel view on principal component analysis (PCA), equivalently singular value decomposition (SVD), as a competitive game in which each approximate singular vector is controlled by a player whose goal is to maximize their own utility function. We analyze the properties of this EigenGame and the behavior of its gradient based updates. The resulting algorithm -- which combines elements from Oja's rule with a generalized Gram-Schmidt orthogonalization -- is naturally decentralized and hence parallelizable through message passing. We demonstrate the scalability of the algorithm by conducting principal component analyses of large image datasets and neural network activations. We discuss how this new view of SVD as a differentiable game can lead to further algorithmic developments and insights.
This talk is based on joint work with Brian McWilliams, Claire Vernade, and Thore Graepel -- https://arxiv.org/abs/2010.
Deepmind's Blog post: https://deepmind.com/blog/article/EigenGame
Short Bio:
Ian is a Research Scientist on the Multiagent team at DeepMind. His research focuses primarily on two questions. How should agents behave in a group, be it a competitive, mixed-motive, or cooperative setting? And should individual agents themselves (including their constituent tools and algorithms) be considered multi-agent systems in their own right? He studied mechanical engineering and applied math (BS/MS) at Northwestern University (2011) and obtained his MS/PhD in computer science from the University of Massachusetts at Amherst (2018).