Decentralized Optimization

Follow this topic Ask about this topic

Decentralized optimization studies how networked agents can jointly minimize an objective or coordinate decisions while each uses local data and communicates with neighbors rather than relying on a central coordinator. Common approaches include gossip and consensus, decentralized stochastic gradient descent with gradient tracking, primal-dual and ADMM methods, and local updates paired with compressed or intermittent communication. These methods are tested in settings such as image and language-model training, online and bilevel learning, power systems, and multi-robot estimation. A central challenge is balancing communication cost, network topology, data heterogeneity, and robustness against noise or adversaries while retaining fast convergence and reliable solutions.

Latest papers

60 papers15 papers in the last four weeks, up 150% on the four weeks before. 0.1% of all new papers.

Jul 2, 2026

Revisiting Decentralized Online Convex Optimization with Compressed Communication

Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.

Hao Zhou, Xiaoyu Wang, Chang Yao +2

School of Software Technology, Zhejiang University, Ningbo, China · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China

Online Convex Optimization Follow-the-Regularized-Leader Decentralized Optimization

Jun 23, 2026

Decentralized Pose Graph Riemannian Optimization for Object-based Multi-Robot SLAM

Pose graph optimization (PGO) is a key back-end component for state estimation in networked multi-robot simultaneous localization and mapping (SLAM). In object-based multi-robot SLAM, the problem becomes more tightly coupled because robots must jointly estimate both their trajectories and the poses of persistent objects observed by multiple agents. Existing decentralized solutions often assume that the communication graph closely matches the physical interaction topology, which is restrictive in realistic deployments where communication is sparse, intermittent, or time-varying. This paper presents a fully decentralized Riemannian optimization framework for object-based multi-robot PGO that decouples the coupled estimation problem via a consensus mechanism, enabling flexible communication topologies. To improve convergence under limited communication budgets, we further develop a distributed approximate-Newton scheme that exploits local second-order information while operating directly on the SE(d) manifold to preserve geometric consistency, and we establish the convergence to Riemannian first-order stationary points and provide a local condition-number analysis explaining the benefit of approximate second-order information over first-order Riemannian descent. The resulting method reduces iteration count and communication overhead without sacrificing estimation accuracy. Extensive evaluations on public benchmarks, large-scale simulations, and real-world multi-robot experiments demonstrate improved accuracy, runtime efficiency, scalability across network topologies, and robustness to communication failures.

Yixian Zhao, Yan Huang, Yang Xu +2

College of Control Science and Engineering, Zhejiang University, Hangzhou, 310027, China · Division of Decision and Control Systems, School of EECS, KTH Royal Institute of Technology, Stockholm, SE-100 44, Sweden · Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai, 201210, China

Simultaneous Localization and Mapping Riemannian Optimization Pose Graph Optimization Decentralized Optimization

Jun 19, 2026

DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity

Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well-defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective. We show that DUET achieves an iteration complexity of

O(1/T^{1-5p-\frac{11}{4}τ})

for approximate KKT-stationary point convergence under relaxed assumptions, where

p

and

τ

are control parameters for LL learning rate and averaging, respectively. In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, a key challenge in DBO settings. To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity. Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.

Zhen Qin, Zhuqing Liu, Songtao Lu +2

Department of Electrical and Computer Engineering, The Ohio State University · Department of Computer Science and Engineering, University of North Texas · Department of Computer Science and Engineering, The Chinese University of Hong Kong

Bilevel Optimization Decentralized Optimization

Jun 9, 2026

Unifying Local Communications and Local Updates for LLM Pretraining

Communication-efficient pre-training of LLMs is increasingly important as training draws on compute distributed across clusters, data centers, and lower-bandwidth links. Many practical methods reduce communication frequency but still rely on synchronous All-Reduce operations that maintain identical model states and tie progress to global collectives. This can become a bottleneck when bandwidth or worker speed is heterogeneous. We introduce GASLoC, a novel decentralized pre-training algorithm that generalizes the notion of communication acceleration to the recently popular "outer optimizer" to allow a practical gossip-based training framework that is compatible with adaptive optimizers, allows for local optimizer steps, and can utilize sparse randomized peer communication. Empirically, on a number of standard LLM training tasks, we demonstrate that GASLoC outperforms state-of-the-art decentralized algorithms in single step per communication setting for a number of topologies and, unlike existing decentralized methods in the LLM setting, it allows to obtain performance competitive with DiLoCo when utilizing multiple local steps. In the heterogeneous bandwidth setting we demonstrate the advantage of GASLoC showing that it can significantly outperform DiLoCo.

Pietro Cagnasso, Eugene Belilovsky, Edouard Oyallon

Concordia University · Mila · CNRS, Sorbonne University

Language Model Pretraining Communication-Efficient Distributed Training Distributed Optimization Decentralized Learning Decentralized Optimization

Jun 8, 2026

Improved Convergence Analysis of Topology Dependence in Decentralized SGD

Decentralized SGD is a fundamental algorithm in decentralized learning, although the influence of an underlying network topology on its convergence behavior is not yet fully understood. Existing convergence analyses have shown that topologies with a small spectral gap significantly deteriorate the convergence rate of Decentralized SGD in both homogeneous and heterogeneous cases. However, many prior papers have reported that indeed the choice of the topology has a significant experimental impact in the heterogeneous case, but has little experimental impact on training behavior in the homogeneous case. In this paper, we present a tighter convergence analysis of Decentralized SGD, offering a more precise understanding of how topologies affect the convergence rate than the prior analysis. Specifically, unlike existing convergence analyses that used only the spectral gap as a property of the topology, our novel analysis shows that all eigenvalues of the mixing matrix affect the convergence rate. Throughout the experiments, we carefully evaluated the convergence behavior of Decentralized SGD and demonstrated that our novel convergence analysis can more accurately describe the effect of topology on the convergence rate.

Yuki Takezawa, Anastasia Koloskova, Sebastian U. Stich

Toyota Motor Corporation · University of Zurich · CISPA Helmholtz Center for Information Security

Optimization Convergence Analysis Decentralized Learning Decentralized Optimization

Jun 5, 2026

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

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

\sqrtκ

and

1/\sqrt{1-β}

dependences, no existing stochastic method attains both improvements at once. In this paper, we 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. We show that MG-ADSGD achieves the communication complexity

\widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right),

where

ε

denotes the target accuracy,

n

is the number of nodes, and

σ^2

is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of

ε

.

Ming Sun, Kun Yuan

Center for Machine Learning Research Peking University

Gradient Descent Accelerated Gradient Methods Decentralized Optimization Stochastic Gradient Descent

Jun 3, 2026

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

We study decentralized stochastic smooth convex optimization, where

M

workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of

N

gradient samples while still preserving the centralized

O(1/\sqrt N)

statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to

\smash{M\lesssim \sqrtρ\,N^{3/4}}

workers, where

ρ

is the spectral gap of the gossip network, improving the best prior maximal scaling of

\smash{M\lesssim ρ\sqrt N}

. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.

Nitai Kluger, Amit Attia, Tomer Koren

Blavatnik School of Computer Science, Tel Aviv University · Google Research Tel Aviv

Stochastic Optimization Convergence Accelerated Gradient Methods Decentralized Optimization

May 29, 2026

S $^3$ LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization

Networked AI systems increasingly rely on multiple agents that collaboratively learn and adapt models over communication networks. In such systems, bilevel formulations naturally arise in hyperparameter optimization, data cleaning, and meta-learning, but the repeated evaluation of gradients, Jacobians, and Hessians can impose a substantial computational burden on individual agents. To address this challenge, we propose Snapshot-SLDBO (S

^3

LDBO), an efficient single-loop decentralized bilevel optimization algorithm that enables agents to intermittently skip expensive derivative evaluations through a snapshot mechanism. This mechanism can be interpreted as an autonomous computation-adaptation strategy for networked AI, where agents selectively perform costly local updates while maintaining global collaborative learning. We establish the ergodic iteration complexity and the high probability nonergodic iteration complexity of the proposed algorithm within a deterministic setting. Experimental results on hyperparameter optimization with synthetic and MNIST datasets, data hyper-cleaning on Fashion-MNIST, and decentralized meta-learning on miniImageNet demonstrate that the proposed algorithm improves computational efficiency while maintaining competitive learning performance.

Chao Yin, Youran Dong, Shiqian Ma +2

School of Mathematics, Hohai University, Nanjing, P. R. China · School of Mathematics, Nanjing University, Nanjing, P. R. China · Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, USA

Multi-Agent System Optimization Bilevel Optimization Decentralized Optimization

May 27, 2026

Decentralized Parameter-Free Online Learning with Compressed Gossip

We study decentralized online convex optimization when agents communicate over a graph and messages may be compressed. Classical decentralized online methods typically require learning-rate choices that depend on the horizon, comparator scale, or other problem parameters, while compressed communication introduces additional disagreement that must be controlled. We propose DECO-EF (DEcentralized COin-betting with Error Feedback), a decentralized parameter-free online learning algorithm that combines coin-betting predictions with compressed difference-based gossip. Each agent maintains a clean accumulated state and a compressed tracker, and communicates only compressed state differences during gossip steps. The method is parameter-free in the online-learning sense: it does not tune to the horizon, the comparator norm, or the learning rate. We prove expected comparator-adaptive network-regret bounds for DECO-EF under compressed communication. To the best of our knowledge, this gives the first expected sublinear network-regret guarantees for parameter-free decentralized online learning under compressed communication.

Tomas Ortega, Hamid Jafarkhani

Center for Pervasive Communications & Computing and EECS Department, University of California, Irvine, Irvine, CA 92697 USA

Online Convex Optimization Decentralized Learning Decentralized Optimization

May 21, 2026

FIRMA: FIbonacci Ring Model Aggregation for Privacy-preserving Federated Learning

Federated learning protocols face a structural trilemma: canonical server-based aggregation~\cite{mcmahan2017} creates a single point of failure and gradient inversion risk; decentralised ring-gossip alternatives~\cite{hu2019segmented} expose classification heads to semi-honest peers via uninformed uniform weights; and personalised methods~\cite{collins2021exploiting} reintroduce central aggregation. No existing protocol simultaneously achieves server-free operation, permanently private heads, ring topology, and principled asymmetric neighbour weighting. We propose FIRMA (FIbonacci Ring Model Aggregation), a family of three progressively enhanced federated learning protocols: 1) \fibfl\ establishes the foundation: server-free ring aggregation with Fibonacci-weighted neighbour blending and permanently private classification heads. 2) \fibflp\ augments this with accuracy-gated neighbour suppression, selectively down-weighting poorly-converged peers while preserving the Fibonacci directional bias. 3) \fibflpp, the full system, completes the family with a 2-opt ring permutation that maximises adjacent-client class diversity, global ring coverage via

K_g{=}\lceil N/2\rceil

gossip passes, and cosine-annealed self-retention calibration. We establish a convergence rate bound and three supporting propositions governing normalisation, coverage, retention, and diversity optimality. Systematic experiments across 28 configurations -- four benchmarks crossed with seven heterogeneity regimes -- demonstrate that \fibflpp\ surpasses \fedavg\ in all 12 label-skew configurations, with a peak advantage of

+20.7

,pp on CIFAR-10 at

K{=}1

. Under Dirichlet heterogeneity, \fibflpp\ is the Pareto-dominant method among all server-free protocols, achieving the highest accuracy in 17 of 28 configurations.

Rachid Hedjam

Department of Computer Science Bishop’s University Sherbrooke, Qc, Canada

Federated Learning Aggregation Non-IID Federated Learning Privacy-Preserving ML Decentralized Optimization Federated Learning Privacy-Preserving Federated Learning

May 20, 2026

Distributed Direct Preference Optimization

Preference-based reinforcement learning (RL) is a key paradigm for aligning policies with human judgments, yet its theoretical behavior in distributed settings where preference data are fragmented across heterogeneous users remains poorly understood. Direct Preference Optimization (DPO) avoids explicit reward modeling but lacks convergence guarantees under federated and decentralized training, where communication constraints and non-IID preferences fundamentally alter optimization dynamics. We provide the first convergence and time-complexity analysis of DPO in distributed environments. Modeling personalized offline RL with user-specific preference distributions, we characterize the induced global optimization landscape. For federated DPO, we derive convergence rates that quantify the impact of client drift, communication frequency, and preference heterogeneity; for decentralized DPO, we establish convergence over general communication graphs and show how spectral connectivity governs optimization speed and consensus. Empirically, we corroborate our theoretical insights on standard alignment benchmarks, demonstrating that our proposed methods not only enjoy strong theoretical guarantees but also deliver robust and scalable performance in practice. The code base is available here.

Zhanhong Jiang

Translational AI Center, Iowa State University, Ames, USA.

Direct Preference Optimization Non-IID Federated Learning Decentralized Optimization Federated Learning

May 18, 2026

Efficient Gradient Methods for Distributed Saddle Problems

The distributed setting for Saddle Problems (SPs) has recently emerged as a framework for various modern applications in machine learning and multiagent systems. Despite its relevance, the theoretical foundations of this setting have not yet been thoroughly established. In this paper, we advance this research direction by formalizing the distributed setup for SPs and providing rigorous definitions of communication and computational costs. Our main result is a novel decoupled method that achieves optimal communication cost within the zero-respecting framework. Our method is based on a multi-stage reduction to the decoupled minimization of residual norms, which yields strict improvements over the best known communication cost for the class and the long-standing oracle cost of the Extragradient method. Further, we show by a matching lower bound that our method is communication-optimal within the family of gradient-span algorithms. Finally, we study the extension of distributed SP into Variational Inequality Problem (VIP), which generalizes two-player zero-sum games to multiplayer general-sum games. We show that our decoupled method achieves a new state-of-the-art communication complexity for this broader class.

Ruichen Luo, Anton Rodomanov, Sebastian U. Stich

Institute of Science and Technology Austria · CISPA Helmholtz Center

Distributed Optimization Decentralized Optimization

May 11, 2026

Unveiling High-Probability Generalization in Decentralized SGD

Decentralized stochastic gradient descent (D-SGD) is an efficient method for large-scale distributed learning. Existing generalization studies mainly address expected results, achieving rates limited to

\mathcal{O}\left(\frac{1}{δ\sqrt{mn}}\right)

, where

δ

is the confidence parameter,

m

the number of workers, and

n

the sample size. When

m=1

, D-SGD reduces to traditional SGD, whose optimal high-probability generalization bound is

\mathcal{O}\left(\frac{1}{\sqrt{n}}\log (1/δ)\right)

. This discrepancy reveals a gap between high-probability guarantees for SGD and those for D-SGD. To close this, we develop a high-probability learning theory for D-SGD, aiming for the optimal

\mathcal{O}\left(\frac{1}{\sqrt{mn}}\log (1/δ)\right)

rate. We refine bounds for D-SGD using pointwise uniform stability in distributed learning-a weaker notion than uniform stability-and analyze them across convex, strongly convex, and non-convex settings. We also provide high-probability results for gradient-based measures in non-convex cases where only local minima exist, and derive optimization error and excess risk bounds. Finally, accounting for communication overhead, we analyze generalization bounds for local models within time-varying frameworks.

Jiahuan Wang, Ping Luo, Ziqing Wen +2

College of Computer Science and Technology National University of Defense Technology Changsha, Hunan 410073, China

Algorithmic Stability Decentralized Learning Decentralized Optimization Generalization Bounds

May 8, 2026

ADKO: Agentic Decentralized Knowledge Optimization

We present Agentic Decentralized Knowledge Optimization (ADKO), a framework for collaborative black-box optimization across autonomous agents that achieves sample efficiency, privacy preservation, heterogeneous-objective handling, and communication efficiency. Each agent maintains a private Gaussian Process (GP) surrogate trained on local data and communicates only through knowledge tokens-compact, lossy summaries containing directional signals, advantage scores, and optional language-model (LM) insights-without sharing raw data or model parameters. ADKO unifies GP-Upper Confidence Bound (GP-UCB), parallel Bayesian optimization, decentralized learning, and LM-guided discovery. We provide the first formal analysis of dual information loss: token compression, quantified via mutual-information-based fidelity, and LM approximation error, decomposed into bias and stochastic noise. Our main result shows cumulative regret decomposes into GP error, LM bias, LM noise, and compression loss, with necessary and sufficient conditions for sublinear regret. We also propose fidelity-aware token pruning to preserve high-information tokens under memory budget. Experiments on neural architecture search and scientific discovery validate the theory and show consistent improvements over strong baselines.

Lucas Nerone Rillo, Zhanhong Jiang, Nastaran Saadati +4

Iowa State University · New York University

Multi-Agent System Optimization AI Agents for Scientific Discovery Bayesian Optimization Black-Box Optimization Large Language Model-Guided Optimization Decentralized Optimization

May 8, 2026

\mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments

Decentralized machine learning often relies on outsourcing computations, such as gradient evaluations, to untrusted worker nodes. Existing robust aggregation methods can mitigate malicious behavior under honest-majority assumptions, but may fail when adversaries control a majority of the workers. We study this adversary-dominated setting through an incentive-oriented framework in which reports are accepted and rewarded only when they are mutually consistent up to a threshold. This turns the adversary from a pure saboteur into a rational agent that trades off increasing estimation error against the risk of rejection and loss of reward. We consider iterative optimization under this model. Unlike one-shot computation, iterative learning requires long-horizon decisions: permissive acceptance rules enable faster early progress but admit more adversarial corruption, while strict rules improve estimation accuracy but cause frequent rejections. We propose \mathsf{VISTA}, an adaptive algorithm that tunes the acceptance threshold using the optimization history. Numerical results show that \mathsf{VISTA} improves convergence over static thresholds. We also provide a rigorous convergence analysis showing that, with suitable incentive-aware adaptation, adversary-dominated decentralized learning can retain the asymptotic convergence behavior of standard SGD without relying on an honest majority.

Hanzaleh Akbari Nodehi, Parsa Moradi, Soheil Mohajer +1

University of Minnesota

Mechanism Design Byzantine-Robust Federated Learning Decentralized Learning Stochastic Optimization Convergence Decentralized Optimization

May 7, 2026

Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

Classical optimization theory largely focuses on fixed objective functions, whereas many modern learning systems operate in dynamic environments where data arrive sequentially and decisions must be updated continuously. In this work, we study optimization with streaming data over a distributed network of agents. We adopt a structured, weight-based formulation that explicitly captures the streaming-data origin of the time-varying objective: at each time step, every agent receives a new sample, and the network seeks to track the minimizer of a temporally weighted objective formed from all samples observed across the network so far. We focus on decentralized gradient descent (DGD) with a limited communication/computation budget, where at each time step, only a limited number of DGD iterations can be performed before the objective changes again. For strongly convex and smooth losses, we analyze the tracking error with respect to the time-varying minimizer through a fixed-point theory lens. Our analysis reveals that the tracking error decomposes into a fixed-point tracking term and a bias term induced by data heterogeneity across agents. We specialize the analysis to two natural weighting strategies: uniform weights, which treat all samples equally, and exponentially discounted weights, which geometrically decay the influence of older data. Under uniform weighting, DGD tracks the fixed-point at a rate

\mathcal{O}(1/t)

, whereas discounted weighting yields a non-vanishing fixed-point tracking floor controlled by the discount factor. In both cases, decentralization induces an additional non-zero bias floor under a constant step size. We validate our theoretical findings through numerical simulations.

Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson

School of Electrical, Computer and Energy Engineering, Arizona State University · Department of Electrical Engineering (ISY), Linköping University

Decentralized Optimization

May 3, 2026

Stability and Generalization for Decentralized Markov SGD

Stochastic gradient methods are central to large-scale learning, yet their generalization theory typically relies on independent sampling assumptions. In many practical applications, data are generated by Markov chains and learning is performed in a decentralized manner, which introduces significant analytical challenges. In this work, we investigate the stability and generalization of decentralized stochastic gradient descent (SGD) and stochastic gradient descent ascent (SGDA) under Markov chain sampling. Leveraging a stability-based framework, we characterize how Markovian dependence and decentralized communication jointly influence generalization behavior. Our analysis captures the effects of network topology, Markov chain mixing properties, and primal-dual dynamics. We establish non-asymptotic generalization bounds for both algorithms, extending existing results on Markov stochastic gradient methods to decentralized and minimax settings.

Jiahuan Wang, Ziqing Wen, Ping Luo +2

National Key Laboratory of Parallel and Distributed Computing, National University of Defense Technology, Changsha, 410073, China

Algorithmic Stability Decentralized Optimization Stochastic Gradient Descent Generalization Bounds

Apr 30, 2026

High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking

We study high-probability (HP) convergence guarantees in decentralized stochastic optimization, where multiple agents collaborate to jointly train a model over a network. Existing HP results in decentralized settings almost exclusively focus on the Decentralized Stochastic Gradient Descent (

\mathtt{DSGD}

) algorithm, which requires strong assumptions, such as bounded data heterogeneity, or strong convexity of each agent's cost. This is contrary to the mean-squared error (MSE) results, where methods incorporating bias-correction techniques are known to converge under relaxed assumptions and achieve better practical performance. In this paper we provide the first step toward bridging the gap, by studying HP convergence of

\mathtt{DSGD}

incorporating the gradient tracking technique, in the presence of noise satisfying a relaxed sub-Gaussian condition. We show that the resulting method, dubbed

\mathtt{GT-DSGD}

, achieves order-optimal HP convergence rates for both non-convex and Polyak-Łojasiewicz costs, of order

\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big)

and

\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big)

, respectively, where

n

is the number of agents,

T

is the time horizon and

δ\in (0,1)

is the confidence parameter. Our results establish that

\mathtt{GT-DSGD}

converges in the HP sense under the same conditions on the cost as in the MSE sense, while achieving comparable transient times. To the best of our knowledge, these are the first HP guarantees for decentralized optimization methods incorporating bias-correction. Numerical experiments on real and synthetic data verify our theoretical findings, underlining the superior performance of

\mathtt{GT-DSGD}

and highlighting that the benefits of incorporating bias-correction are also maintained in the HP sense.

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Convergence Analysis Stochastic Optimization Convergence Decentralized Optimization Gradient Descent Dynamics

Apr 21, 2026

Accelerating Optimization and Machine Learning through Decentralization

Decentralized optimization enables multiple devices to learn a global machine learning model while each individual device only has access to its local dataset. By avoiding the need for training data to leave individual users' devices, it enhances privacy and scalability compared to conventional centralized learning, where all data has to be aggregated to a central server. However, decentralized optimization has traditionally been viewed as a necessary compromise, used only when centralized processing is impractical due to communication constraints or data privacy concerns. In this study, we show that decentralization can paradoxically accelerate convergence, outperforming centralized methods in the number of iterations needed to reach optimal solutions. Through examples in logistic regression and neural network training, we demonstrate that distributing data and computation across multiple agents can lead to faster learning than centralized approaches, even when each iteration is assumed to take the same amount of time, whether performed centrally on the full dataset or decentrally on local subsets. This finding challenges longstanding assumptions and reveals decentralization as a strategic advantage, offering new opportunities for more efficient optimization and machine learning.

Ziqin Chen, Zuang Wang, Yongqiang Wang

Clemson University

Distributed Optimization Decentralized Learning Decentralized Optimization

Apr 11, 2026

LoDAdaC: a unified local training-based decentralized framework with adaptive gradients and compressed communication

In the decentralized distributed learning, achieving fast convergence and low communication cost is essential for scalability and high efficiency. Adaptive gradient methods, such as Adam, have demonstrated strong practical performance in deep learning and centralized distributed settings. However, their convergence properties remain largely unexplored in decentralized settings involving multiple local training steps, such as federated learning. To address this limitation, we propose LoDAdaC, a unified multiple Local Training (MLT) Decentralized framework with Adam-type updates and Compressed communication (CC). LoDAdaC accommodates a broad class of optimizers for its local adaptive updates, including AMSGrad, Adam, and AdaGrad; it is compatible with standard (possibly biased) compressors such as low-bit quantization and sparsification. MLT and CC enable LoDAdaC to achieve multiplied reduction of communication cost, while the technique of adaptive updates enables fast convergence. We rigorously prove the combined advantage through complexity analysis. In addition, experiments on image classification and GPT-style language model training validate our theoretical findings and show that LoDAdaC significantly outperforms existing decentralized algorithms in terms of convergence speed and communication efficiency.

Wei Liu, Anweshit Panda, Ujwal Pandey +5

Department of Mathematical Sciences, Rensselaer Polytechnic Institute · Department of Computer Science, Rensselaer Polytechnic Institute · IBM T. J. Watson Research Center +1

Decentralized Optimization Communication-Efficient Distributed Training

Apr 1, 2026

Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

We study distributed optimization over networks with Byzantine agents that may send arbitrary adversarial messages. We propose Gradient Tracking with Probabilistic Edge Dropout (GT-PD), a stochastic gradient tracking method that preserves the convergence properties of gradient tracking under adversarial communication. GT-PD combines two complementary defense layers: a universal self-centered projection that clips each incoming message to a ball of radius

τ

around the receiving agent, and a fully decentralized probabilistic dropout rule driven by a dual-metric trust score in the decision and tracking channels. This design bounds adversarial perturbations while preserving the doubly stochastic mixing structure, a property often lost under robust aggregation in decentralized settings. Under complete Byzantine isolation (

p_b=0

), GT-PD converges linearly to a neighborhood determined solely by stochastic gradient variance. For partial isolation (

p_b>0

), we introduce Gradient Tracking with Probabilistic Edge Dropout and Leaky Integration (GT-PD-L), which uses a leaky integrator to control the accumulation of tracking errors caused by persistent perturbations and achieves linear convergence to a bounded neighborhood determined by the stochastic variance and the clipping-to-leak ratio. We further show that under two-tier dropout with

p_h=1

, isolating Byzantine agents introduces no additional variance into the honest consensus dynamics. Experiments on MNIST under Sign Flip, ALIE, and Inner Product Manipulation attacks show that GT-PD-L outperforms coordinate-wise trimmed mean by up to 4.3 percentage points under stealth attacks.

Amirhossein Dezhboro, Fateme Maleki, Arman Adibi +2

Department of Systems Engineering, Stevens Institute of Technology, Hoboken, NJ 07030. · Department of Industrial and Systems Engineering, Rutgers University, Piscataway, NJ 08854. · School of Computer and Cyber Sciences, Augusta University, Augusta, GA 30912. +1

Decentralized Optimization Stochastic Gradient Descent

Mar 25, 2026

On Gossip Algorithms for Machine Learning with Pairwise Objectives

In the IoT era, information is more and more frequently picked up by connected smart sensors with increasing, though limited, storage, communication and computation abilities. Whether due to privacy constraints or to the structure of the distributed system, the development of statistical learning methods dedicated to data that are shared over a network is now a major issue. Gossip-based algorithms have been developed for the purpose of solving a wide variety of statistical learning tasks, ranging from data aggregation over sensor networks to decentralized multi-agent optimization. Whereas the vast majority of contributions consider situations where the function to be estimated or optimized is a basic average of individual observations, it is the goal of this article to investigate the case where the latter is of pairwise nature, taking the form of a U -statistic of degree two. Motivated by various problems such as similarity learning, ranking or clustering for instance, we revisit gossip algorithms specifically designed for pairwise objective functions and provide a comprehensive theoretical framework for their convergence. This analysis fills a gap in the literature by establishing conditions under which these methods succeed, and by identifying the graph properties that critically affect their efficiency. In particular, a refined analysis of the convergence upper and lower bounds is performed.

Igor Colin, Aurélien Bellet, Stephan Clémençon +1

LTCI, S2A, IP Paris · LTCI, Télécom Paris, Institut Polytechnique de Paris · PREMEDICAL +4

U-Statistics Decentralized Optimization Statistical Learning Theory

Feb 24, 2026

Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs

Push-Sum-based decentralized learning enables optimization over directed communication networks, where information exchange may be asymmetric. While convergence properties of such methods are well understood, their finite-iteration stability and generalization behavior remain unclear due to structural bias induced by column-stochastic mixing and asymmetric error propagation. In this work, we develop a unified uniform-stability framework for the Stochastic Gradient Push (SGP) algorithm that captures the effect of directed topology. A key technical ingredient is an imbalance-aware consistency bound for Push-Sum, which controls consensus deviation through two quantities: the stationary distribution imbalance parameter

δ

and the spectral gap

(1-λ)

governing mixing speed. This decomposition enables us to disentangle statistical effects from topology-induced bias. We establish finite-iteration stability and optimization guarantees for both convex objectives and non-convex objectives satisfying the Polyak--Łojasiewicz condition. For convex problems, SGP attains excess generalization error of order

\tilde{\mathcal{O}}\!\left(\frac{1}{\sqrt{mn}}+\fracγ{δ(1-λ)}+γ\right)

under step-size schedules, and we characterize the corresponding optimal early stopping time that minimizes this bound. For PŁ objectives, we obtain convex-like optimization and generalization rates with dominant dependence proportional to

κ\!\left(1+\frac{1}{δ(1-λ)}\right)

, revealing a multiplicative coupling between problem conditioning and directed communication topology. Our analysis clarifies when Push-Sum correction is necessary compared with standard decentralized SGD and quantifies how imbalance and mixing jointly shape the best attainable learning performance.

Yifei Liang, Yan Sun, Xiaochun Cao +1

School of Cyber Science and Technology, Sun Yat-sen University, Shenzhen, Guangdong 518107, China · The University of Sydney, Sydney, NSW 2006, Australia

Decentralized Optimization Decentralized Learning Algorithmic Stability Stochastic Gradient Descent

Feb 19, 2026

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

The paper studies decentralized optimization over networks, where agents minimize a sum of {\it locally} smooth (strongly) convex losses and plus a nonsmooth convex extended value term. We propose decentralized methods wherein agents {\it adaptively} adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols. Our design stems from a three-operator splitting factorization applied to an equivalent reformulation of the problem. The reformulation is endowed with a new BCV preconditioning metric (Bertsekas-O'Connor-Vandenberghe), which enables efficient decentralized implementation and local stepsize adjustments. We establish robust convergence guarantees. Under mere convexity, the proposed methods converge with a sublinear rate. Under strong convexity of the sum-function, and assuming the nonsmooth component is partly smooth, we further prove linear convergence. Numerical experiments corroborate the theory and highlight the effectiveness of the proposed adaptive stepsize strategy.

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA

Decentralized Optimization Nonsmooth Convex Optimization

Feb 2, 2026

Decentralized SGD with Controlled Disagreement Finds Flatter Minima

Decentralized training is often regarded as inferior to centralized training because the consensus errors between workers are thought to undermine convergence and generalization. This work challenges this view by introducing decentralized SGD with Adaptive Consensus (DSGD-AC), which uses a time-dependent scaling mechanism to maintain consensus errors throughout the training. We show that adaptive consensus changes the stationary variance of disagreement modes by balancing two effects: it preserves consensus-error magnitude through weaker graph damping while still allowing curvature-dependent damping to shape the disagreement directions. This balance can produce a stronger Hessian-weighted loss-envelope penalty around the deployed model, even when normalized Hessian alignment is weaker than in standard DSGD. Empirical results on image classification show that DSGD-AC reaches flatter solutions and higher test accuracy than standard DSGD and even centralized SGD. Together, these results support consensus errors as a useful implicit regularizer and open a new perspective on the design of decentralized learning algorithms.

Zesen Wang, Mikael Johansson

Division of Decision and Control Systems KTH Royal Institute of Technology

Decentralized Learning Flat Minima Implicit Regularization Decentralized Optimization

Jan 28, 2026

Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning

Asynchronous primal-dual methods for decentralized non-smooth convex optimization often require each node to maintain

\mathcal{O}(d)

auxiliary variables, where

d

is its degree. This dependence on degree increases memory requirements and can amplify the effects of stale information, especially in dense networks. Motivated by the challenge of frugal memory management in decentralized learning, we introduce Goal-PD, an asynchronous gossip-based primal-dual algorithm that maintains only two variables per node, regardless of the node's degree. We establish almost-sure convergence of Goal-PD to a minimizer of the underlying optimization problem, and prove linear convergence when the objective functions are piecewise linear-quadratic. For decentralized mean estimation, we show that pairwise averaging is a special case of Goal-PD, which establishes a direct link between the proposed primal-dual framework and classical gossip. Experiments on synthetic and real datasets over various network topologies, with non-smooth objectives including median estimation, show that Goal-PD converges faster than existing asynchronous baselines while requiring significantly less memory by design.

Anna van Elst, Olivier Fercoq, Igor Colin +1

LTCI, Télécom Paris, Institut Polytechnique de Paris

Decentralized Learning Nonsmooth Convex Optimization Decentralized Optimization

Nov 28, 2025

Distributed Dynamic Associative Memory via Online Convex Optimization

An associative memory (AM) enables cue-response recall, and it has recently been recognized as a key mechanism underlying modern neural architectures such as Transformers. In this work, we introduce the concept of distributed dynamic associative memory (DDAM), which extends classical AM to settings with multiple agents and time-varying data streams. In DDAM, each agent maintains a local AM that must not only store its own associations but also selectively memorize information from other agents based on a specified interest matrix. To address this problem, we propose a novel tree-based distributed online gradient descent algorithm, termed DDAM-TOGD, which enables each agent to update its memory on the fly via inter-agent communication over designated routing trees. We derive rigorous performance guarantees for DDAM-TOGD, proving sublinear static regret in stationary environments and a path-length dependent dynamic regret bound in non-stationary environments. These theoretical results provide insights into how communication delays and network structure impact performance. Building on the regret analysis, we further introduce a combinatorial tree design strategy that optimizes the routing trees to minimize communication delays, thereby improving regret bounds. Numerical experiments demonstrate that the proposed DDAM-TOGD framework achieves superior accuracy and robustness compared to representative online learning baselines such as consensus-based distributed optimization, confirming the benefits of the proposed approach in dynamic, distributed environments.

Bowen Wang, Matteo Zecchin, Osvaldo Simeone

Department of Engineering, King’s College London, London WC2R 2LS, U.K. · Communication Systems Department, EURECOM, 06904 Sophia Antipolis, France · Institute for Intelligent Networked Systems (INSI) at Northeastern University London, London E1 8PH, U.K.

Online Convex Optimization Associative Memory Decentralized Optimization

Nov 14, 2025

Game-theoretic Regulated Decentralized Coordination for Airspace Sector Overload Mitigation

Decentralized air traffic management systems offer a scalable alternative to centralized control, but often assume high levels of cooperation. In practice, such assumptions frequently break down since airspace sectors operate independently and prioritize local objectives. We address the problem of sector overload in decentralized air traffic management by proposing a regulated decentralized protocol that models self-interested behaviors based on best response dynamics. Each sector adjusts the departure times of flights under its control to reduce its own congestion, without requiring centralized joint optimization. A tunable cooperativeness factor models the degree to which each sector accounts for overload in other sectors, while a minimal admissibility rule prevents local updates from creating new overloads. We prove that the proposed protocol satisfies a potential game structure, ensuring that best response dynamics converge to a pure Nash equilibrium under this restriction. In addition, we identify a sufficient condition under which an overload-free solution corresponds to a global minimizer of the potential function. Numerical experiments using 24 hours of European flight data demonstrate that the proposed algorithm substantially reduces overload even with only minimal cooperation between sectors, while maintaining scalability and achieving solution quality comparable to the centralized benchmark.

Jaehan Im, Daniel Delahaye, David Fridovich-Keil +1

The University of Texas at Austin, 110 Inner Campus Drive, Austin, 78712, Texas, United States · École Nationale de lAviation Civile, 7 Avenue Édouard Belin, CS 54005, Toulouse Cedex 4, 31055, France

Multi-Agent Coordination Air Traffic Management Intelligent Transportation Systems Potential Games Decentralized Optimization

Jan 30, 2025

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of

O(T^{1-θ/2})

with communication complexity of

O(T^θ)

and number of linear optimization oracle calls of

O(T^{2θ})

for decentralized upper-linearizable function optimization, for any

0\le θ\le 1

. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Submodular Optimization Online Convex Optimization Bandit Learning Constrained Optimization Decentralized Optimization

Oct 27, 2023

LOOP-MAC: Learning-Based Multi-Agent Coordination with Guaranteed Local Feasibility in a Virtual Power Plant

By aggregating distributed energy resources (DERs) into a single dispatchable resource, virtual power plants (VPPs) enable the grid to use the flexibility of numerous small-scale DERs. Delivering an aggregate VPP commitment requires multi-agent coordination, where agents manage local DER models and operating constraints while jointly meeting a power commitment within limited communication rounds. Classical distributed optimization is computationally intensive, requiring iterative local optimization and repeated communication to reach consensus. Learning-based methods can accelerate coordination but often lack guarantees of local feasibility and accurate commitment tracking. This paper proposes LOOP-MAC (Learning to Optimize the Optimization Process for Multi-Agent Coordination), a fully decentralized learning-based framework that ensures local feasibility by construction while efficiently reducing the aggregate commitment gap. LOOP-MAC employs a two-stage decision process. Learned coordination uses neural optimizers equipped with a gauge layer to produce locally feasible schedules through a few rounds of message exchange. Local adjustment then rebalances each schedule toward feasible flexibility extremes using a commitment-gap estimate inferred from messages already received. The adjusted schedule remains locally feasible as a convex combination of feasible schedules, and the adjustment requires no additional communication round. On a 100-agent VPP, five communication rounds followed by local adjustment reduce the mean commitment gap from 5.1% to 0.75% of the agents' aggregate absolute power and the optimality gap from 3.93% to 3.07% relative to learned coordination alone. Per-agent online computation takes approximately 1.1 ms, including the adjustment.

Meiyi Li, Lucas Ruda, Javad Mohammadi

Multi-Agent Coordination Power Systems Decentralized Optimization Learning to Optimize