A Generalized Mean Approach for Distributed-PCA

• URL: http://arxiv.org/abs/2410.00397v1
• Date: Tue, 1 Oct 2024 04:39:40 GMT
• Title: A Generalized Mean Approach for Distributed-PCA
• Authors: Zhi-Yu Jou, Su-Yun Huang, Hung Hung, Shinto Eguchi,
• Abstract summary: We propose a novel DPCA method that incorporates eigenvalue information to aggregate local results via the matrix $beta$-mean. The $beta$-DPCA offers a flexible and robust aggregation through the adjustable choice of $beta$ values.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Principal component analysis (PCA) is a widely used technique for dimension reduction. As datasets continue to grow in size, distributed-PCA (DPCA) has become an active research area. A key challenge in DPCA lies in efficiently aggregating results across multiple machines or computing nodes due to computational overhead. Fan et al. (2019) introduced a pioneering DPCA method to estimate the leading rank-$r$ eigenspace, aggregating local rank-$r$ projection matrices by averaging. However, their method does not utilize eigenvalue information. In this article, we propose a novel DPCA method that incorporates eigenvalue information to aggregate local results via the matrix $\beta$-mean, which we call $\beta$-DPCA. The matrix $\beta$-mean offers a flexible and robust aggregation method through the adjustable choice of $\beta$ values. Notably, for $\beta=1$, it corresponds to the arithmetic mean; for $\beta=-1$, the harmonic mean; and as $\beta \to 0$, the geometric mean. Moreover, the matrix $\beta$-mean is shown to associate with the matrix $\beta$-divergence, a subclass of the Bregman matrix divergence, to support the robustness of $\beta$-DPCA. We also study the stability of eigenvector ordering under eigenvalue perturbation for $\beta$-DPCA. The performance of our proposal is evaluated through numerical studies.

Related papers

• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [61.79405341803085]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in federated learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in federated learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
  We present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. LoRa-PI learns an $varepsilon$-optimal policy using $widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$ samples where $S$ denotes the number of states (resp. actions) and $gamma$ the discount factor.
  arXiv  Detail & Related papers  (2024-10-30T20:22:17Z)
• Sparse PCA with Oracle Property [115.72363972222622]
  We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations. We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
  arXiv  Detail & Related papers  (2023-12-28T02:52:54Z)
• Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
  We present a distributed coreset-based 3-round approximation algorithm for k-means with $z$ outliers for general metric spaces. An important feature of our algorithm is that it obliviously adapts to the intrinsic complexity of the dataset, captured by the dimension doubling $D$ of the metric space.
  arXiv  Detail & Related papers  (2022-02-16T16:24:31Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  We give an input sparsity time sampling algorithm for approximating the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time.
  arXiv  Detail & Related papers  (2022-02-09T15:26:03Z)
• Robust factored principal component analysis for matrix-valued outlier accommodation and detection [4.228971753938522]
  Factored PCA (FPCA) is a probabilistic extension of PCA for matrix data. We propose a robust extension of FPCA (RFPCA) for matrix data. RFPCA can adaptively down-weight outliers and yield robust estimates.
  arXiv  Detail & Related papers  (2021-12-13T16:12:22Z)
• Classification of high-dimensional data with spiked covariance matrix structure [0.5156484100374059]
  We study the classification problem for high-dimensional data with $n$ observations on $p$ features.<n>We propose an adaptive classifier that first performs dimension reduction on the feature vectors prior to classification in the dimensionally reduced space.<n>We show that the resulting classifier is Bayes optimal whenever $n rightarrow infty$ and $s sqrtn-1 ln p rightarrow 0$.
  arXiv  Detail & Related papers  (2021-10-05T11:26:53Z)
• Efficient Matrix-Free Approximations of Second-Order Information, with Applications to Pruning and Optimization [16.96639526117016]
  We investigate matrix-free, linear-time approaches for estimating Inverse-Hessian Vector Products (IHVPs) These algorithms yield state-of-the-art results for network pruning and optimization with lower computational overhead relative to existing second-order methods.
  arXiv  Detail & Related papers  (2021-07-07T17:01:34Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering [43.50783459690612]
  The method consists in randomly "puncturing" both the data matrix $XinmathbbCptimes n$ and its corresponding kernel (Gram) matrix $K$ through Bernoulli masks. We empirically confirm on GAN-generated image databases, that it is possible to drastically puncture the data, thereby providing possibly huge computational and storage gains.
  arXiv  Detail & Related papers  (2021-02-24T14:01:58Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  We introduce a new randomized algorithm, Hutch++, which computes a $(1 pm epsilon)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$. We show that it significantly outperforms Hutchinson's method in experiments.
  arXiv  Detail & Related papers  (2020-10-19T16:45:37Z)
• A New Basis for Sparse Principal Component Analysis [5.258928416164104]
  Previous versions of sparse principal component analysis presumed that the eigen-basis (a $p times k$ matrix) is approximately sparse. We propose a method that presumes the $p times k$ matrix becomes approximately sparse after a $k times k$ rotation. We show that for the same level of sparsity, the proposed sparse PCA method is more stable and can explain more variance compared to alternative methods.
  arXiv  Detail & Related papers  (2020-07-01T16:32:22Z)

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.