Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation

• URL: http://arxiv.org/abs/2502.17615v1
• Date: Mon, 24 Feb 2025 20:02:27 GMT
• Title: Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation
• Authors: Fangshuo Liao, Wenyi Su, Anastasios Kyrillidis,
• Abstract summary: We study a distributed PCA framework where each worker targets a distinct eigenvector and refines its solution by updating from intermediate solutions provided by peers deemed as "superior"<n>Our proposed framework offers comparable performance to EigenGame-$mu$, the state-of-the-art model-parallel PCA solver.
• Score: 9.613011825024476
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a distributed Principal Component Analysis (PCA) framework where each worker targets a distinct eigenvector and refines its solution by updating from intermediate solutions provided by peers deemed as "superior". Drawing intuition from the deflation method in centralized eigenvalue problems, our approach breaks the sequential dependency in the deflation steps and allows asynchronous updates of workers, while incurring only a small communication cost. To our knowledge, a gap in the literature -- the theoretical underpinning of such distributed, dynamic interactions among workers -- has remained unaddressed. This paper offers a theoretical analysis explaining why, how, and when these intermediate, hierarchical updates lead to practical and provable convergence in distributed environments. Despite being a theoretical work, our prototype implementation demonstrates that such a distributed PCA algorithm converges effectively and in scalable way: through experiments, our proposed framework offers comparable performance to EigenGame-$\mu$, the state-of-the-art model-parallel PCA solver.

Related papers

• SAMBO-RL: Shifts-aware Model-based Offline Reinforcement Learning [9.88109749688605]
  Model-based offline reinforcement learning trains policies using pre-collected datasets and learned environment models.<n>This paper offers a comprehensive analysis that disentangles the problem into two fundamental components: model bias and policy shift.<n>We introduce Shifts-aware Model-based Offline Reinforcement Learning (SAMBO-RL), a practical framework that efficiently trains classifiers to approximate SAR for policy optimization.
  arXiv  Detail & Related papers  (2024-08-23T04:25:09Z)
• Revisiting Spurious Correlation in Domain Generalization [12.745076668687748]
  We build a structural causal model (SCM) to describe the causality within data generation process. We further conduct a thorough analysis of the mechanisms underlying spurious correlation. In this regard, we propose to control confounding bias in OOD generalization by introducing a propensity score weighted estimator.
  arXiv  Detail & Related papers  (2024-06-17T13:22:00Z)
• Approximate Global Convergence of Independent Learning in Multi-Agent Systems [19.958920582022664]
  We study two representative algorithms, independent $Q$-learning and independent natural actor-critic, within value-based and policy-based frameworks. The results imply a sample complexity of $tildemathcalO(epsilon-2)$ up to an error term that characterizes the fundamental limit of IL in achieving global convergence.
  arXiv  Detail & Related papers  (2024-05-30T08:20:34Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Boosted Control Functions: Distribution generalization and invariance in confounded models [10.503777692702952]
  We introduce a strong notion of invariance that allows for distribution generalization even in the presence of nonlinear, non-identifiable structural functions.<n>We propose the ControlTwicing algorithm to estimate the Boosted Control Function (BCF) using flexible machine-learning techniques.
  arXiv  Detail & Related papers  (2023-10-09T15:43:46Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  We take a closer theoretical look at Independent Subnetwork Training (IST) IST is a recently proposed and highly effective technique for solving the aforementioned problems. We identify fundamental differences between IST and alternative approaches, such as distributed methods with compressed communication.
  arXiv  Detail & Related papers  (2023-06-28T18:14:22Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  We propose a novel and general theoretical scheme for a non-decreasing performance guarantee of model-based RL (MBRL) Our follow-up derived bounds reveal the relationship between model shifts and performance improvement. A further example demonstrates that learning models from a dynamically-varying number of explorations benefit the eventual returns.
  arXiv  Detail & Related papers  (2022-10-15T17:57:43Z)
• DDAC-SpAM: A Distributed Algorithm for Fitting High-dimensional Sparse Additive Models with Feature Division and Decorrelation [16.232378903482143]
  We propose a new distributed statistical learning algorithm, DDAC-SpAM, which divides the features under a high-dimensional sparse additive model. The effectiveness and efficiency of the proposed algorithm are demonstrated through theoretical analysis and empirical results on both synthetic and real data. Our approach provides a practical solution for fitting sparse additive models, with promising applications in a wide range of domains.
  arXiv  Detail & Related papers  (2022-05-16T18:31:03Z)
• Multi-Task Learning on Networks [0.0]
  Multi-objective optimization problems arising in the multi-task learning context have specific features and require adhoc methods. In this thesis the solutions in the Input Space are represented as probability distributions encapsulating the knowledge contained in the function evaluations. In this space of probability distributions, endowed with the metric given by the Wasserstein distance, a new algorithm MOEA/WST can be designed in which the model is not directly on the objective function.
  arXiv  Detail & Related papers  (2021-12-07T09:13:10Z)
• Generalization Properties of Optimal Transport GANs with Latent Distribution Learning [52.25145141639159]
  We study how the interplay between the latent distribution and the complexity of the pushforward map affects performance. Motivated by our analysis, we advocate learning the latent distribution as well as the pushforward map within the GAN paradigm.
  arXiv  Detail & Related papers  (2020-07-29T07:31:33Z)
• Implicit Distributional Reinforcement Learning [61.166030238490634]
  implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs) Semi-implicit actor (SIA) powered by a flexible policy distribution. We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
  arXiv  Detail & Related papers  (2020-07-13T02:52:18Z)
• Adversarial Distributional Training for Robust Deep Learning [53.300984501078126]
  Adversarial training (AT) is among the most effective techniques to improve model robustness by augmenting training data with adversarial examples. Most existing AT methods adopt a specific attack to craft adversarial examples, leading to the unreliable robustness against other unseen attacks. In this paper, we introduce adversarial distributional training (ADT), a novel framework for learning robust models.
  arXiv  Detail & Related papers  (2020-02-14T12:36:59Z)

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.