EigenGame: PCA as a Nash Equilibrium

• URL: http://arxiv.org/abs/2010.00554v2
• Date: Tue, 16 Mar 2021 20:43:46 GMT
• Title: EigenGame: PCA as a Nash Equilibrium
• Authors: Ian Gemp, Brian McWilliams, Claire Vernade, Thore Graepel
• Abstract summary: We present a novel view on principal component analysis (PCA) as a competitive game. We analyze the properties of this PCA game and the behavior of its gradient based updates. We demonstrate the scalability of the algorithm with experiments on large image datasets and neural network activations.
• Score: 21.548912902011054
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel view on principal component analysis (PCA) as a competitive game in which each approximate eigenvector is controlled by a player whose goal is to maximize their own utility function. We analyze the properties of this PCA game 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. We demonstrate the scalability of the algorithm with experiments on large image datasets and neural network activations. We discuss how this new view of PCA as a differentiable game can lead to further algorithmic developments and insights.

Related papers

• Quantum EigenGame for excited state calculation [8.957579200590988]
  We extend the EigenGame algorithm for both a $0textth$-order approach and for quantum computers. Results show that using the Quantum EigenGame allows us to converge to excited states of a given Hamiltonian without the need of a deflation step.
  arXiv  Detail & Related papers  (2025-03-17T18:48:40Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Deciphering 'What' and 'Where' Visual Pathways from Spectral Clustering of Layer-Distributed Neural Representations [15.59251297818324]
  We present an approach for analyzing grouping information contained within a neural network's activations. We exploit features from all layers and obviating the need to guess which part of the model contains relevant information.
  arXiv  Detail & Related papers  (2023-12-11T01:20:34Z)
• An online algorithm for contrastive Principal Component Analysis [9.090031210111919]
  We derive an online algorithm for cPCA* and show that it maps onto a neural network with local learning rules, so it can potentially be implemented in energy efficient neuromorphic hardware. We evaluate the performance of our online algorithm on real datasets and highlight the differences and similarities with the original formulation.
  arXiv  Detail & Related papers  (2022-11-14T19:48:48Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Principal Geodesic Analysis of Merge Trees (and Persistence Diagrams) [8.430851504111585]
  We introduce an efficient, iterative algorithm which exploits shared-memory parallelism, as well as an analytic expression of the fitting energy gradient. We show the utility of our contributions by extending to merge trees two typical PCA applications. We present a dimensionality reduction framework exploiting the first two directions of the MT-PGA basis to generate two-dimensional layouts.
  arXiv  Detail & Related papers  (2022-07-22T09:17:22Z)
• Personalized PCA: Decoupling Shared and Unique Features [4.976703689624386]
  We propose personalized PCA (PerPCA) to decouple shared and unique features from heterogeneous datasets. We show that, under mild conditions, both unique and shared features can be identified and recovered by a constrained optimization problem. As a systematic approach to decouple shared and unique features from heterogeneous datasets, PerPCA finds applications in several tasks, including video segmentation, topic extraction, and feature clustering.
  arXiv  Detail & Related papers  (2022-07-17T00:09:47Z)
• coVariance Neural Networks [119.45320143101381]
  Graph neural networks (GNN) are an effective framework that exploit inter-relationships within graph-structured data for learning. We propose a GNN architecture, called coVariance neural network (VNN), that operates on sample covariance matrices as graphs. We show that VNN performance is indeed more stable than PCA-based statistical approaches.
  arXiv  Detail & Related papers  (2022-05-31T15:04:43Z)
• Priming PCA with EigenGame [0.0]
  We introduce primed-PCA, an extension of the recently proposed EigenGame algorithm for computing principal components in a large-scale setup. Our algorithm first runs EigenGame to get an approximation of the principal components, and then applies an exact PCA in the subspace they span. In our experiments we achieve improvements in convergence speed by factors of 5-25 on the datasets of the original EigenGame paper.
  arXiv  Detail & Related papers  (2021-09-08T15:16:53Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• Eigen Analysis of Self-Attention and its Reconstruction from Partial Computation [58.80806716024701]
  We study the global structure of attention scores computed using dot-product based self-attention. We find that most of the variation among attention scores lie in a low-dimensional eigenspace. We propose to compute scores only for a partial subset of token pairs, and use them to estimate scores for the remaining pairs.
  arXiv  Detail & Related papers  (2021-06-16T14:38:42Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.