A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration

• URL: http://arxiv.org/abs/2501.19082v2
• Date: Thu, 13 Feb 2025 16:14:34 GMT
• Title: A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration
• Authors: Yuchen Hu, Xi Chen, Weidong Liu, Xiaojun Mao,
• Abstract summary: 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.
• Score: 19.83835152405735
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed stochastic optimization algorithms can simultaneously process large-scale datasets, significantly accelerating model training. However, their effectiveness is often hindered by the sparsity of distributed networks and data heterogeneity. In this paper, we propose a momentum-accelerated distributed stochastic gradient algorithm, termed Exact-Diffusion with Momentum (EDM), which mitigates the bias from data heterogeneity and incorporates momentum techniques commonly used in deep learning to enhance convergence rate. Our theoretical analysis demonstrates that the EDM algorithm converges sub-linearly to the neighborhood of the optimal solution, the radius of which is irrespective of data heterogeneity, when applied to non-convex objective functions; under the Polyak-Lojasiewicz condition, which is a weaker assumption than strong convexity, it converges linearly to the target region. Our analysis techniques employed to handle momentum in complex distributed parameter update structures yield a sufficiently tight convergence upper bound, offering a new perspective for the theoretical analysis of other momentum-based distributed algorithms.

Related papers

• Spectral Algorithms under Covariate Shift [4.349399061959293]
  Spectral algorithms leverage spectral regularization techniques to analyze and process data. We investigate the convergence behavior of spectral algorithms under distribution shifts. We propose a weighted spectral algorithm that incorporates density ratio information into the learning process.
  arXiv  Detail & Related papers  (2025-04-17T04:02:06Z)
• Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework [33.417831716314495]
  Decentralized gradient descent (DGD) and diffusion are workhorses in decentralized machine learning. We propose a principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies. The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes.
  arXiv  Detail & Related papers  (2025-03-18T15:36:36Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• 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)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Flow-based Distributionally Robust Optimization [23.232731771848883]
  We present a framework, called $textttFlowDRO$, for solving flow-based distributionally robust optimization (DRO) problems with Wasserstein uncertainty sets. We aim to find continuous worst-case distribution (also called the Least Favorable Distribution, LFD) and sample from it. We demonstrate its usage in adversarial learning, distributionally robust hypothesis testing, and a new mechanism for data-driven distribution perturbation differential privacy.
  arXiv  Detail & Related papers  (2023-10-30T03:53:31Z)
• 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)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning. This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
  arXiv  Detail & Related papers  (2023-04-24T02:19:39Z)
• Composite Optimization Algorithms for Sigmoid Networks [3.160070867400839]
  We propose the composite optimization algorithms based on the linearized proximal algorithms and the alternating direction of multipliers. Numerical experiments on Frank's function fitting show that the proposed algorithms perform satisfactorily robustly.
  arXiv  Detail & Related papers  (2023-03-01T15:30:29Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  This paper tackles the problem of missing data imputation for noisy and non-Gaussian data. A new EM algorithm is investigated for mixtures of elliptical distributions with the property of handling potential missing data. Experimental results on synthetic data demonstrate that the proposed algorithm is robust to outliers and can be used with non-Gaussian data.
  arXiv  Detail & Related papers  (2022-01-28T10:01:37Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• Kernel Interpolation of High Dimensional Scattered Data [22.857190042428922]
  Data sites selected from modeling high-dimensional problems often appear scattered in non-paternalistic ways. We propose and study in the current article a new framework to analyze kernel of high dimensional data, which features bounding approximation error by the spectrum of the underlying kernel matrix.
  arXiv  Detail & Related papers  (2020-09-03T08:34:00Z)
• 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)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  The article rigorously establishes why symplectic discretization schemes are important for momentum-based optimization algorithms. It provides a characterization of algorithms that exhibit accelerated convergence.
  arXiv  Detail & Related papers  (2020-02-28T00:32:47Z)

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.