An EigenGame for the Generalized Eigenvalue Problem

We present a game-theoretic formulation of the top-$k$ generalized eigenvalue problem (GEP) and provide an efficient algorithm with guaranteed asymptotic convergence to its solution, the unique Nash equilibrium. The GEP captures several classical machine learning problems including canonical correlation analysis (CCA), independent component analysis (ICA), partial least squares (PLS), successor features (SFs), and others. Current state-of-the-art methods require $\mathcal{O}(d^2k)$ complexity per iteration which is prohibitively expensive for large dimensional ($d$) datasets. We present a highly parallelized, stochastic, unbiased algorithm with $\mathcal{O}(bdk)$ iteration complexity that consumes streaming data in minibatches of size $b$. Our proposed algorithm is not only competitive with state-of-the-art on previous benchmarks, but also scales to datasets too large for prior methods to accommodate. Our experiments include analyses comparing the activations of large neural networks. We show how our formulation generalizes the previous EigenGame formulation of singular value decomposition and provide insights to help illuminate room for improvement on future iterations.

Authors' notes