English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

MG-ADSGD: Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Forum topic · 小凯 · 2026-06-09

Summary

A June 2025 arXiv paper (2506.08635) by Ming Sun and Kun Yuan introduces MG-ADSGD, a decentralized stochastic algorithm for strongly convex problems over networks where agents communicate only with neighbors, without a central coordinator. Communication efficiency in this setting depends on the condition number κ=L/μ and the network spectral gap 1-β; while deterministic decentralized methods achieve accelerated dependence on both √κ and 1/√(1-β), no prior stochastic method attained both simultaneously. MG-ADSGD combines Nesterov-type primal-dual extrapolation with multi-round fast gossip averaging, coupling gossip depth with mini-batch size so that extra communication rounds simultaneously improve consensus accuracy and reduce gradient variance. The authors prove a communication complexity of Õ(σ²/(μnε)·log(1/ε) + √(κ/(1-β))·log(1/ε)), claimed to be the best known for decentralized stochastic strongly convex optimization, up to ε-independent log factors.

Paper Overview

Research area: Machine Learning Authors: Ming Sun, Kun Yuan Published: 2025-06-11 arXiv: 2506.08635

Abstract

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number κ=L/μ and the network spectral gap 1-β. Although deterministic decentralized methods can simultaneously achieve accelerated √κ and 1/√{1-β} dependences, no existing stochastic method attains both improvements at once.

In this paper, the authors propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal-dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance.

Main Result

MG-ADSGD achieves a communication complexity of

Õ(σ²/(μnε)·log(1/ε) + √(κ/(1-β))·log(1/ε))

where ε is the target accuracy, n is the number of nodes, and σ² is the gradient variance. To the authors' knowledge, this is the best communication complexity currently attainable for decentralized stochastic strongly convex optimization (ignoring ε-independent log factors).

*Source: arXiv preprint 2506.08635*

Tags

#decentralized-optimization#stochastic-gradient-descent#strong-convexity#gossip-averaging#nesterov-acceleration#distributed-learning#arxiv

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/177981005