# The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium

arXiv: https://arxiv.org/abs/2206.04993 · HTML: https://mlsanity.com/paper/2206.04993/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 10 Jun 2022.

## Builds on (most cited first, 21 of 21)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Similarity of Neural Network Representations Revisited](https://mlsanity.com/paper/1905.00414/) (2019)
- [Insights on representational similarity in neural networks with canonical correlation](https://mlsanity.com/paper/1806.05759/) (2018)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Eigenoption Discovery through the Deep Successor Representation](https://mlsanity.com/paper/1710.11089/) (2017)
- [EigenGame: PCA as a Nash Equilibrium](https://mlsanity.com/paper/2010.00554/) (2020)
- [Spectral Inference Networks: Unifying Deep and Spectral Learning](https://mlsanity.com/paper/1806.02215/) (2018)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Exponentially convergent stochastic k-PCA without variance reduction](https://mlsanity.com/paper/1904.01750/) (2019)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis](https://mlsanity.com/paper/1604.03930/) (2016)
- [Canonical Correlation Analysis (CCA) Based Multi-View Learning: An Overview](https://mlsanity.com/paper/1907.01693/) (2019)
- [Stochastic Canonical Correlation Analysis](https://mlsanity.com/paper/1702.06533/) (2017)
- [Stochastic Approximation for Canonical Correlation Analysis](https://mlsanity.com/paper/1702.06818/) (2017)
- [Stochastic Approximation on Riemannian manifolds](https://mlsanity.com/paper/1711.10754/) (2017)
- [An Online Riemannian PCA for Stochastic Canonical Correlation Analysis](https://mlsanity.com/paper/2106.07479/) (2021)
- [Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition](https://mlsanity.com/paper/1607.06017/) (2016)
- [Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis](https://mlsanity.com/paper/1604.01870/) (2016)
- [Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature](https://mlsanity.com/paper/1907.10531/) (2019)
- [Correlated random features for fast semi-supervised learning](https://mlsanity.com/paper/1306.5554/) (2013)

## Abstract (arXiv)

The symmetric generalized eigenvalue problem (SGEP) is a fundamental concept in numerical linear algebra. It captures the solution of many classical machine learning problems such as canonical correlation analysis, independent components analysis, partial least squares, linear discriminant analysis, principal components and others. Despite this, most general solvers are prohibitively expensive when dealing with streaming data sets (i.e., minibatches) and research has instead concentrated on finding efficient solutions to specific problem instances. In this work, we develop a game-theoretic formulation of the top-k SGEP whose Nash equilibrium is the set of generalized eigenvectors. We also present a parallelizable algorithm with guaranteed asymptotic convergence to the Nash. Current state-of-the-art methods require O(d2k) runtime complexity per iteration which is prohibitively expensive when the number of dimensions (d) is large. We show how to modify this parallel approach to achieve O(dk) runtime complexity. Empirically we demonstrate that this resulting algorithm is able to solve a variety of SGEP problem instances including a large-scale analysis of neural network activations.