Priming PCA with EigenGame

• URL: http://arxiv.org/abs/2109.03709v1
• Date: Wed, 8 Sep 2021 15:16:53 GMT
• Title: Priming PCA with EigenGame
• Authors: B\'alint M\'at\'e, Fran\c{c}ois Fleuret
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce primed-PCA (pPCA), 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. Since this subspace is of small dimension in any practical use of EigenGame, this second step is extremely cheap computationally. Nonetheless, it improves accuracy significantly for a given computational budget across datasets. In this setup, the purpose of EigenGame is to narrow down the search space, and prepare the data for the second step, an exact calculation. We show formally that pPCA improves upon EigenGame under very mild conditions, and we provide experimental validation on both synthetic and real large-scale datasets showing that it systematically translates to improved performance. In our experiments we achieve improvements in convergence speed by factors of 5-25 on the datasets of the original EigenGame paper.

Related papers

• Value-Based Deep RL Scales Predictably [100.21834069400023]
  We show that value-based off-policy RL methods are predictable despite community lore regarding their pathological behavior. We validate our approach using three algorithms: SAC, BRO, and PQL on DeepMind Control, OpenAI gym, and IsaacGym.
  arXiv  Detail & Related papers  (2025-02-06T18:59:47Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium. We also give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium. Our algorithm for approximately optimal EFCE is, to our knowledge, the first that achieves 3 desiderata simultaneously.
  arXiv  Detail & Related papers  (2024-12-22T09:12:05Z)
• Learning-Augmented K-Means Clustering Using Dimensional Reduction [1.7243216387069678]
  We propose a solution to reduce the dimensionality of the dataset using Principal Component Analysis (PCA) PCA is well-established in the literature and has become one of the most useful tools for data modeling, compression, and visualization.
  arXiv  Detail & Related papers  (2024-01-06T12:02:33Z)
• PPI++: Efficient Prediction-Powered Inference [31.403415618169433]
  We present PPI++: a methodology for estimation and inference based on a small labeled dataset and a typically much larger dataset of machine-learning predictions. The methods automatically adapt to the quality of available predictions, yielding easy-to-compute confidence sets. PPI++ builds on prediction-powered inference (PPI), which targets the same problem setting, improving its computational and statistical efficiency.
  arXiv  Detail & Related papers  (2023-11-02T17:59:04Z)
• Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [43.106438224356175]
  We develop a nearly-linear time algorithm for robust PCA with near-optimal error guarantees. We also develop a single-pass streaming algorithm for robust PCA with memory usage nearly-linear in the dimension.
  arXiv  Detail & Related papers  (2023-05-04T04:45:16Z)
• 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)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  We propose a Shapley value based method to evaluate operation contribution (Shapley-NAS) for neural architecture search. We show that our method outperforms the state-of-the-art methods by a considerable margin with light search cost.
  arXiv  Detail & Related papers  (2022-06-20T14:41:49Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  We study human-in-the-loop reinforcement learning (RL) with trajectory preferences. Instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. We propose the first optimistic model-based algorithm for PbRL with general function approximation.
  arXiv  Detail & Related papers  (2022-05-23T09:03:24Z)
• An Extension to Basis-Hypervectors for Learning from Circular Data in Hyperdimensional Computing [62.997667081978825]
  Hyperdimensional Computing (HDC) is a computation framework based on properties of high-dimensional random spaces. We present a study on basis-hypervector sets, which leads to practical contributions to HDC in general. We introduce a method to learn from circular data, an important type of information never before addressed in machine learning with HDC.
  arXiv  Detail & Related papers  (2022-05-16T18:04:55Z)
• VSAC: Efficient and Accurate Estimator for H and F [68.65610177368617]
  VSAC is a RANSAC-type robust estimator with a number of novelties. It is significantly faster than all its predecessors and runs on average in 1-2 ms, on a CPU. It is two orders of magnitude faster and yet as precise as MAGSAC++, the currently most accurate estimator of two-view geometry.
  arXiv  Detail & Related papers  (2021-06-18T17:04:57Z)
• EigenGame Unloaded: When playing games is better than optimizing [19.522120239876486]
  EigenGame views eigendecomposition as a competitive game. We build on the recently proposed EigenGame that views eigendecomposition as a competitive game.
  arXiv  Detail & Related papers  (2021-02-08T12:04:59Z)
• EigenGame: PCA as a Nash Equilibrium [21.548912902011054]
  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.
  arXiv  Detail & Related papers  (2020-10-01T17:12:33Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)

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.