The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium
This work addresses the computational bottleneck in solving SGEP for streaming data in machine learning, offering a more efficient method for applications like canonical correlation analysis and linear discriminant analysis, though it is incremental as it builds on existing solvers.
The authors tackled the symmetric generalized eigenvalue problem (SGEP) by developing a game-theoretic formulation where the Nash equilibrium corresponds to generalized eigenvectors, and they presented a parallelizable algorithm with asymptotic convergence that reduces runtime complexity from O(d^2k) to O(dk) per iteration, demonstrating its effectiveness on large-scale neural network activations.
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(d^2k)$ 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.