CMSA Computer Science for Mathematicians: EigenGame: SVD as a Nash Equilibrium
CMSA EVENTS
Speaker:
Ian Gemp - Google DeepMind
We present a novel view on 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. EigenGame's updates are biased if computed using minibatches of data, which hinders convergence and more sophisticated parallelism in the stochastic setting. Therefore, in follow-up 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 the original EigenGame in experiments. We demonstrate the a) scalability of the algorithm by conducting principal component analyses of large image datasets, language datasets, and neural network activations and b) generality by reusing the same algorithm to perform spectral clustering of a social network. 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 two recent works, both joint work with Brian McWilliams, Claire Vernade, and Thore Graepel --
https://arxiv.org/abs/2010.
https://arxiv.org/abs/2102.
-- and will focus in detail on some of the more interesting mathematical properties of the game.
Zoom: https://harvard.zoom.us/j/98231541450