On the Effects of Data Heterogeneity on the Convergence Rates of
Distributed Linear System Solvers
- URL: http://arxiv.org/abs/2304.10640v2
- Date: Fri, 16 Feb 2024 00:02:49 GMT
- Title: On the Effects of Data Heterogeneity on the Convergence Rates of
Distributed Linear System Solvers
- Authors: Boris Velasevic, Rohit Parasnis, Christopher G. Brinton, Navid Azizan
- Abstract summary: We consider the problem of solving a large-scale system of linear equations with the help of a set of machines.
We compare two classes of algorithms with a particular focus on the most efficient method from each class.
Our analysis results in a number of novel insights besides showing that APC is the most efficient method in realistic scenarios.
- Score: 10.103350854870992
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the fundamental problem of solving a large-scale system of linear
equations. In particular, we consider the setting where a taskmaster intends to
solve the system in a distributed/federated fashion with the help of a set of
machines, who each have a subset of the equations. Although there exist several
approaches for solving this problem, missing is a rigorous comparison between
the convergence rates of the projection-based methods and those of the
optimization-based ones. In this paper, we analyze and compare these two
classes of algorithms with a particular focus on the most efficient method from
each class, namely, the recently proposed Accelerated Projection-Based
Consensus (APC) and the Distributed Heavy-Ball Method (D-HBM). To this end, we
first propose a geometric notion of data heterogeneity called angular
heterogeneity and discuss its generality. Using this notion, we bound and
compare the convergence rates of the studied algorithms and capture the effects
of both cross-machine and local data heterogeneity on these quantities. Our
analysis results in a number of novel insights besides showing that APC is the
most efficient method in realistic scenarios where there is a large data
heterogeneity. Our numerical analyses validate our theoretical results.
Related papers
- Quantized Hierarchical Federated Learning: A Robust Approach to
Statistical Heterogeneity [3.8798345704175534]
We present a novel hierarchical federated learning algorithm that incorporates quantization for communication-efficiency.
We offer a comprehensive analytical framework to evaluate its optimality gap and convergence rate.
Our findings reveal that our algorithm consistently achieves high learning accuracy over a range of parameters.
arXiv Detail & Related papers (2024-03-03T15:40:24Z) - Synergistic eigenanalysis of covariance and Hessian matrices for
enhanced binary classification [75.90957645766676]
We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model.
Our approach is substantiated by formal proofs that establish its capability to maximize between-class mean distance and minimize within-class variances.
arXiv Detail & Related papers (2024-02-14T16:10:42Z) - 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) - Distributed Linear Regression with Compositional Covariates [5.085889377571319]
We focus on the distributed sparse penalized linear log-contrast model in massive compositional data.
Two distributed optimization techniques are proposed for solving the two different constrained convex optimization problems.
In the decentralized topology, we introduce a distributed coordinate-wise descent algorithm for obtaining a communication-efficient regularized estimation.
arXiv Detail & Related papers (2023-10-21T11:09:37Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
We propose a novel methodology for addressing the hyperspectral image deconvolution problem.
A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network.
The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
arXiv Detail & Related papers (2023-06-10T08:25:16Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings.
We exploit a warm-start strategy to amortize the estimation of the exact gradient.
By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
arXiv Detail & Related papers (2021-11-29T15:10:09Z) - 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) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
Bilevel optimization is a tool for many machine learning problems.
We propose a novel stoc-efficientgradient estimator named stoc-BiO.
arXiv Detail & Related papers (2020-10-15T18:09:48Z) - A Method for Handling Multi-class Imbalanced Data by Geometry based
Information Sampling and Class Prioritized Synthetic Data Generation (GICaPS) [15.433936272310952]
This paper looks into the problem of handling imbalanced data in a multi-label classification problem.
Two novel methods are proposed that exploit the geometric relationship between the feature vectors.
The efficacy of the proposed methods is analyzed by solving a generic multi-class recognition problem.
arXiv Detail & Related papers (2020-10-11T04:04:26Z) - Communication-efficient distributed eigenspace estimation [31.69089186688224]
We develop a communication-efficient distributed algorithm for computing the leading invariant subspace of a data matrix.
Our algorithm uses a novel alignment scheme that minimizes the Procrustean distance between local solutions and a reference solution.
We show that our algorithm achieves a similar error rate to that of a centralized estimator.
arXiv Detail & Related papers (2020-09-05T02:11:22Z) - Distributed Bayesian Matrix Decomposition for Big Data Mining and
Clustering [13.491022200305824]
We propose a distributed matrix decomposition model for big data mining and clustering.
Specifically, we adopt three strategies to implement the distributed computing including 1) the accelerated gradient descent, 2) the alternating direction method of multipliers (ADMM), and 3) the statistical inference.
Our algorithms scale up well to big data and achieves superior or competing performance compared to other distributed methods.
arXiv Detail & Related papers (2020-02-10T13:10:53Z)
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.