One-shot Distibuted Algorithm for PCA with RBF Kernels

• URL: http://arxiv.org/abs/2005.02664v3
• Date: Thu, 29 Apr 2021 07:11:47 GMT
• Title: One-shot Distibuted Algorithm for PCA with RBF Kernels
• Authors: Fan He, Kexin Lv, Jie Yang, Xiaolin Huang
• Abstract summary: Our algorithm is inspired by the dual relationship between sample-distributed and feature-distributed scenario. In theoretical part, we analyze the approximation error for both linear and RBF kernels. The result suggests that when eigenvalues decay fast, the proposed algorithm gives high quality results with low communication cost.
• Score: 23.266613551011638
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This letter proposes a one-shot algorithm for feature-distributed kernel PCA. Our algorithm is inspired by the dual relationship between sample-distributed and feature-distributed scenario. This interesting relationship makes it possible to establish distributed kernel PCA for feature-distributed cases from ideas in distributed PCA in sample-distributed scenario. In theoretical part, we analyze the approximation error for both linear and RBF kernels. The result suggests that when eigenvalues decay fast, the proposed algorithm gives high quality results with low communication cost. This result is also verified by numerical experiments, showing the effectiveness of our algorithm in practice.

Related papers

• 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)
• Fair principal component analysis (PCA): minorization-maximization algorithms for Fair PCA, Fair Robust PCA and Fair Sparse PCA [6.974999794070285]
  We propose a new iterative algorithm to solve the fair PCA (FPCA) problem. The proposed algorithm relies on the relaxation of a semi-orthogonality constraint which is proved to be tight at every iteration of the algorithm. We numerically compare the performance of the proposed methods with two of the state-of-the-art approaches on synthetic data sets and a real-life data set.
  arXiv  Detail & Related papers  (2023-05-10T08:14:32Z)
• Plug-and-Play split Gibbs sampler: embedding deep generative priors in Bayesian inference [12.91637880428221]
  This paper introduces a plug-and-play sampling algorithm that leverages variable splitting to efficiently sample from a posterior distribution. It divides the challenging task of posterior sampling into two simpler sampling problems. Its performance is compared to recent state-of-the-art optimization and sampling methods.
  arXiv  Detail & Related papers  (2023-04-21T17:17:51Z)
• Distributed Robust Principal Analysis [0.0]
  We study the robust principal component analysis problem in a distributed setting. We propose the first distributed robust principal analysis algorithm based on consensus factorization, dubbed DCF-PCA.
  arXiv  Detail & Related papers  (2022-07-24T05:45:07Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• A Linearly Convergent Algorithm for Distributed Principal Component Analysis [12.91948651812873]
  This paper introduces a feedforward neural network-based one time-scale distributed PCA algorithm termed Distributed Sanger's Algorithm (DSA) The proposed algorithm is shown to converge linearly to a neighborhood of the true solution.
  arXiv  Detail & Related papers  (2021-01-05T00:51:14Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• 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)
• 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)
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures [31.986482149142503]
  We cast this question as a distribution view by introducing the emphsigned measure A series of non-PD kernels can be associated with the linear combination of specific finite Borel measures. Specifically, this solution is also computationally implementable in practice to scale non-PD kernels in large sample cases.
  arXiv  Detail & Related papers  (2020-05-30T12:10:35Z)

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.