mlsanityData to 13 Oct 2026

The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium

arXiv 2206.04993 ↗First posted 10 Jun 2022cs.LG cs.AI cs.GTcited by 0

Not on the map. Why?

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.

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

Builds on

21 of 57 references.

References · 21

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,093
  2. 2019Similarity of Neural Network Representations Revisitedcited by 1,719
  3. 2018Insights on representational similarity in neural networks with canonical correlationcited by 321
  4. 2017A Laplacian Framework for Option Discovery in Reinforcement Learningcited by 109
  5. 2017Eigenoption Discovery through the Deep Successor Representationcited by 86
  6. 2020EigenGame: PCA as a Nash Equilibriumcited by 39
  7. 2018Spectral Inference Networks: Unifying Deep and Spectral Learningcited by 35
  8. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 32
  9. 2021EigenGame Unloaded: When playing games is better than optimizingcited by 13
  10. 2019Exponentially convergent stochastic k-PCA without variance reductioncited by 12
  11. 2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
  12. 2016Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysiscited by 10
9 more
  1. 2019Canonical Correlation Analysis (CCA) Based Multi-View Learning: An Overviewcited by 10
  2. 2017Stochastic Canonical Correlation Analysiscited by 7
  3. 2017Stochastic Approximation for Canonical Correlation Analysiscited by 7
  4. 2017Stochastic Approximation on Riemannian manifoldscited by 7
  5. 2021An Online Riemannian PCA for Stochastic Canonical Correlation Analysiscited by 7
  6. 2016Doubly Accelerated Methods for Faster CCA and Generalized Eigendecompositioncited by 5
  7. 2016Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysiscited by 4
  8. 2019Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvaturecited by 3
  9. 2013Correlated random features for fast semi-supervised learningcited by 2

Built on by

Not cited yet.