Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework

• URL: http://arxiv.org/abs/2503.14353v1
• Date: Tue, 18 Mar 2025 15:36:36 GMT
• Title: Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
• Authors: Erik G. Larsson, Nicolo Michelusi,
• Abstract summary: Decentralized gradient descent (DGD) and diffusion are workhorses in decentralized machine learning.<n>We propose a principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies.<n>The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes.
• Score: 33.417831716314495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The decentralized gradient descent (DGD) algorithm, and its sibling, diffusion, are workhorses in decentralized machine learning, distributed inference and estimation, and multi-agent coordination. We propose a novel, principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies, using contraction mappings coupled with a result called the mean Hessian theorem (MHT). The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes. While these bounds are qualitatively similar to results found in the literature, our approach using contractions together with the MHT decouples the algorithm dynamics (how quickly the algorithm converges to its fixed point) from its asymptotic convergence properties (how far the fixed point is from the global optimum). This yields a simple, intuitive analysis that is accessible to a broader audience. Extensions are provided to multiple local gradient updates, time-varying step sizes, noisy gradients (stochastic DGD and diffusion), communication noise, and random topologies.

Related papers

• A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration [19.83835152405735]
  We propose a momentum-celerated distributed gradient, termed Exact-Diffusion with Momentum (EDM)<n>EDM mitigates the bias from data heterogeneity and incorporates momentum techniques commonly used in deep learning.<n>Our theoretical analysis demonstrates that the EDM algorithm converges sublinearly to the neighborhood optimal solution.
  arXiv  Detail & Related papers  (2025-01-31T12:15:58Z)
• Communication-Efficient Stochastic Distributed Learning [3.2923780772605595]
  We address distributed learning problems, both non and convex, undirected networks.<n>In particular, we design a novel based on the distributed Alternating Method of Multipliers (MM) to address the challenges of high communication costs.
  arXiv  Detail & Related papers  (2025-01-23T10:05:23Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  We propose a federated version of adaptive gradient methods, particularly AdaGrad and Adam, within the framework of over-the-air model training. Our analysis shows that the AdaGrad-based training algorithm converges to a stationary point at the rate of $mathcalO( ln(T) / T 1 - frac1alpha ).
  arXiv  Detail & Related papers  (2024-03-11T09:10:37Z)
• 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)
• Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology [6.6682038218782065]
  We develop a general framework unifying several gradient-based optimization methods for empirical risk minimization problems. We provide a unified perspective for variance-reduction (VR) and gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. The rate results reveal that VR and GT methods can effectively eliminate data within and across devices, respectively, enabling the exact convergence of the algorithm to the optimal solution.
  arXiv  Detail & Related papers  (2022-07-08T07:50:08Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Communication-Efficient Distributed SGD with Compressed Sensing [24.33697801661053]
  We consider large scale distributed optimization over a set of edge devices connected to a central server. Inspired by recent advances in federated learning, we propose a distributed gradient descent (SGD) type algorithm that exploits the sparsity of the gradient, when possible, to reduce communication burden. We conduct theoretical analysis on the convergence of our algorithm in the presence of noise perturbation incurred by the communication channels, and also conduct numerical experiments to corroborate its effectiveness.
  arXiv  Detail & Related papers  (2021-12-15T02:10:45Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• Optimal Complexity in Decentralized Training [45.468216452357375]
  We present a gossip-style decentralized algorithm that achieves the lower bound with only a gap. We show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.
  arXiv  Detail & Related papers  (2020-06-15T02:03:04Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.