Distributed Optimization

Ask about this topic

Overview

Distributed optimization studies how multiple machines, clients, or robots can solve a shared problem using local data and limited communication. Common approaches include consensus and decentralized gradient methods, local or federated SGD, ADMM and primal-dual algorithms, and asynchronous updates; communication can be reduced through compression, quantization, or less frequent synchronization. These methods support settings from large-model training and statistical learning to robot coordination, energy systems, and networked control. A central challenge is balancing communication and computation against convergence when data and worker speeds differ, messages are delayed, or participants may be unreliable or adversarial.

Latest papers

CardsList

92 papers11 papers in the last four weeks, up 267% on the four weeks before. 0.1% of all new papers.

May 1, 2026

Learning to Act and Cooperate for Distributed Black-Box Consensus Optimization

Distributed blackbox consensus optimization is a fundamental problem in multi-agent systems, where agents must improve a global objective using only local objective queries and limited neighbor communication. Existing methods largely rely on handcrafted update rules and static cooperation patterns, which often struggle to balance local adaptation, global coordination, and communication efficiency in heterogeneous nonconvex environments. In this paper, we take an initial step toward trajectory-driven self-design for distributed black-box consensus optimization. We first redesign the agent-level swarm dynamics with an adaptive internal mechanism tailored to decentralized consensus settings, improving the balance between exploration, convergence, and local escape. Built on top of this adaptive execution layer, we propose Learning to Act and Cooperate (LACMAS), a trajectorydriven framework in which large language models provide sparse highlevel guidance for shaping both agentinternal action behaviors and agentexternal cooperation patterns from historical optimization trajectories. We further introduce a phased cognitive scheduling strategy to activate different forms of adaptation in a resource-aware manner. Experiments on standard distributed black-box benchmarks and real-world distributed tasks show that LAC-MAS consistently improves solution quality, convergence efficiency, and communication efficiency over strong baselines, suggesting a practical route from handcrafted distributed coordination toward self-designing multi-agent optimization systems.

Zi-Bo Qin, Feng-Feng Wei, Tai-You Chen +1

School of Computer Science and Engineering, South China University of Technology, Guangzhou, China.

Multi-Agent System OptimizationMulti-Agent CoordinationBlack-Box OptimizationDistributed OptimizationLarge Language Model-Guided OptimizationMulti-Agent Consensus
AskPDF
May 1, 2026

Hierarchical Federated Learning for Networked AI: From Communication Saving to Architecture-Aware Design

Federated learning (FL) is fundamentally a distributed optimization problem executed by communicating agents with local data, local computation, and partial system visibility. Once FL is viewed through that lens, hierarchy is not merely a scalability mechanism. It becomes the natural place to rethink how distributed optimization should be organized over real multi-tier networks. This article argues that hierarchical federated learning (HFL) should move beyond its common framing as a communication-saving protocol and instead be viewed as an architecture-aware design framework for networked AI. The framework is organized around three coupled design axes: architectural parameters, layer-wise optimization decomposition, and layer-wise communication realization. The first axis determines the coordination geometry of learning through hierarchy depth, layer asymmetry, and layered connectivity. The second determines how the global FL objective is decomposed across layers and highlights modular multi-layer optimization as a major opportunity beyond one dominant method everywhere. The third determines how the distributed optimization is physically realized under heterogeneous communication regimes, from interference-limited lower tiers to reliable upper tiers. A central message is that, in HFL, convergence becomes architecture-dependent: it is directly shaped by the chosen hierarchy, the assigned optimization roles, and the communication mechanisms that connect them. We develop this viewpoint using large-scale wireless edge intelligence as a flagship networked AI setting, then provide a comparative perspective on flat FL, two-tier HFL, and deep HFL together with a regime-oriented design map. The resulting perspective positions HFL as a practical methodology for designing future networked AI systems.

Seyed Mohammad Azimi-Abarghouyi, Mehdi Bennis, Leandros Tassiulas

Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden · Centre for Wireless Communications, University of Oulu, Oulu, Finland · Department of Electrical Engineering, Yale University, New Haven, USA

Hierarchical Federated LearningCommunication-Efficient Distributed TrainingDistributed OptimizationFederated LearningEdge AI
AskPDF
Apr 27, 2026

FreeScale: Distributed Training for Sequence Recommendation Models with Minimal Scaling Cost

Modern industrial Deep Learning Recommendation Models typically extract user preferences through the analysis of sequential interaction histories, subsequently generating predictions based on these derived interests. The inherent heterogeneity in data characteristics frequently result in substantial under-utilization of computational resources during large-scale training, primarily due to computational bubbles caused by severe stragglers and slow blocking communications. This paper introduces FreeScale, a solution designed to (1) mitigate the straggler problem through meticulously load balanced input samples (2) minimize the blocking communication by overlapping prioritized embedding communications with computations (3) resolve the GPU resource competition during computation and communication overlapping by communicating through SM-Free techniques. Empirical evaluation demonstrates that FreeScale achieves up to 90.3% reduction in computational bubbles when applied to real-world workloads running on 256 H100 GPUs.

Chenhao Feng, Haoli Zhang, Shakhzod Ali-Zade +17

1Meta Inc.

Sequential RecommendationCommunication-Efficient Distributed TrainingDistributed OptimizationDistributed Training
AskPDF
Apr 27, 2026

CommFuse: Hiding Tail Latency via Communication Decomposition and Fusion for Distributed LLM Training

The rapid growth in the size of large language models has necessitated the partitioning of computational workloads across accelerators such as GPUs, TPUs, and NPUs. However, these parallelization strategies incur substantial data communication overhead significantly hindering computational efficiency. While communication-computation overlap presents a promising direction, existing data slicing based solutions suffer from tail latency. To overcome this limitation, this research introduces a novel communication-computation overlap technique to eliminate this tail latency in state of the art overlap methods for distributed LLM training. The aim of this technique is to effectively mitigate communication bottleneck of tensor parallelism and data parallelism for distributed training and inference. In particular, we propose a novel method termed CommFuse that replaces conventional collective operations of reduce-scatter and all-gather with decomposed peer-to-peer (P2P) communication and schedules partitioned computations to enable fine-grained overlap. Our method provides an exact algorithm for reducing communication overhead that eliminates tail latency. Moreover, it presents a versatile solution compatible with data-parallel training and various tensor-level parallelism strategies, including TPSP and UP. Experimental evaluations demonstrate that our technique consistently achieves lower latency, superior Model FLOPS Utilization (MFU), and high throughput.

Rezaul Karim, Austin Wen, Wang Zongzuo +3

Toronto Ascend Team

Communication-Efficient Distributed TrainingDistributed OptimizationTensor ParallelismDistributed TrainingLLM Training
AskPDF
Apr 23, 2026

Decoupled DiLoCo for Resilient Distributed Pre-training

Modern large-scale language model pre-training relies heavily on the single program multiple data (SPMD) paradigm, which requires tight coupling across accelerators. Due to this coupling, transient slowdowns, hardware failures, and synchronization overhead stall the entire computation, wasting significant compute time at scale. While recent distributed methods like DiLoCo reduced communication bandwidth, they remained fundamentally synchronous and vulnerable to these system stalls. To address this, we introduce Decoupled DiLoCo, an evolution of the DiLoCo framework designed to break the lock-step synchronization barrier and go beyond SPMD to maximize training goodput. Decoupled DiLoCo partitions compute across multiple independent learners'' that execute local inner optimization steps. These learners asynchronously communicate parameter fragments to a central synchronizer, which circumvents failed or straggling learners by aggregating updates using a minimum quorum, an adaptive grace window, and dynamic token-weighted merging. Inspired by chaos engineering'', we achieve significantly improved training efficiency in failure-prone environments with millions of simulated chips with strictly zero global downtime, while maintaining competitive model performance across text and vision tasks, for both dense and mixture-of-expert architectures.

Arthur Douillard, Keith Rush, Yani Donchev +14

1Google DeepMind · 2Google Research

Language Model PretrainingDistributed OptimizationHigh-Performance ComputingFault-Tolerant Distributed TrainingDistributed Training
AskPDF
Apr 21, 2026

A Network-Aware Evaluation of Distributed Energy Resource Control in Smart Distribution Systems

Distribution networks with high penetration of Distributed Energy Resources (DERs) increasingly rely on communication networks to coordinate grid-interactive control. While many distributed control schemes have been proposed, they are often evaluated under idealized communication assumptions, making it difficult to assess their performance under realistic network conditions. This work presents an implementation-driven evaluation of a representative virtual power plant (VPP) dispatch algorithm using a co-simulation framework that couples a linearized distribution-system model with packet-level downlink emulation in ns-3. The study considers a modified IEEE~37-node feeder with high photovoltaic penetration and a primal--dual VPP dispatch that simultaneously targets feeder-head active power tracking and voltage regulation. Communication effects are introduced only on the downlink path carrying dual-variable updates, where per-DER packet delays and a hold-last-value strategy are modeled. Results show that, under ideal communication, the dispatch achieves close tracking of the feeder-head power reference while maintaining voltages within the prescribed limits at selected buses. When realistic downlink delay is introduced, the same controller exhibits large oscillations in feeder-head power and more frequent voltage limit violations. These findings highlight that distributed DER control performance can be strongly influenced by communication behavior and motivate evaluation frameworks that explicitly incorporate network dynamics into the assessment of grid-interactive control schemes.

Houchao Gan

Department of Computer Science City University of New York

Distributed OptimizationFeedback ControlPower Systems
AskPDF
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 OptimizationDecentralized LearningDecentralized Optimization
AskPDF
Apr 20, 2026

Semantic-based Distributed Learning for Diverse and Discriminative Representations

In large-scale distributed scenarios, increasingly complex tasks demand more intelligent collaboration across networks, requiring the joint extraction of structural representations from data samples. However, conventional task-specific approaches often result in nonstructural embeddings, leading to collapsed variability among data samples within the same class, particularly in classification tasks. To address this issue and fully leverage the intrinsic structure of data for downstream applications, we propose a novel distributed learning framework that ensures both diverse and discriminative representations. For independent and identically distributed (i.i.d.) data, we reformulate and decouple the global optimization function by introducing constraints on representation variance. The update rules are then derived and simplified using a primal-dual approach. For non-i.i.d. data distributions, we tackle the problem by clustering and virtually replicating nodes, allowing model updates within each cluster using block coordinate descent. In both cases, the resulting optimal solutions are theoretically proven to maintain discriminative and diverse properties, with a guaranteed convergence for i.i.d. conditions. Additionally, semantic information from representations is shared among nodes, reducing the need for common neural network architectures. Finally, extensive simulations on MNIST, CIFAR-10 and CIFAR-100 confirm the effectiveness of the proposed algorithms in capturing global structural representations.

Zhuojun Tian, Chaouki Ben Issaid, Mehdi Bennis

Center for Wireless Communications, University of Oulu, Oulu, Finland · Division of Information Science and Engineering, KTH Royal of Technology, Stockholm, Sweden · Center for Wireless Communications, University of Oulu, Oulu 90014, Finland

Representation LearningDistributed Optimization
AskPDF
Apr 11, 2026

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

Byzantine-robust distributed optimization relies on robust aggregation rules to mitigate the influence of malicious Byzantine workers. Despite the proliferation of such rules, a unified convergence analysis framework that accommodates general data heterogeneity is lacking. In this work, we provide a thorough convergence theory of Byzantine-robust distributed stochastic gradient descent (SGD), analyzing variants both with and without local momentum. We establish the convergence rates for nonconvex smooth objectives and those satisfying the Polyak-Lojasiewicz condition under a general data heterogeneity assumption. Our analysis reveals that while stochasticity and data heterogeneity introduce unavoidable error floors, local momentum provably reduces the error component induced by stochasticity. Furthermore, we derive matching lower bounds to demonstrate that the upper bounds obtained in our analysis are tight and characterize the fundamental limits of Byzantine resilience under stochasticity and data heterogeneity. Empirical results support our theoretical findings.

Boyuan Ruan, Xiaoyu Wang, Ya-Feng Liu

School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 102206, China

Distributed OptimizationFault-Tolerant Distributed TrainingStochastic Gradient DescentNonconvex Stochastic Optimization
AskPDF
Apr 8, 2026

The Principle of Maximum Heterogeneity Optimises Productivity in Distributed Production Systems Across Biology, Economics, and Computing

The world is full of systems of distributed agents, collaborating and competing in complex ways: firms and workers specialise within economies, neurons adapt their tuning across brain circuits, and species compete and coexist within ecosystems. In that context, individual research fields built theories explaining how comparative advantage drives trade specialisation, how balanced neural representations emerge from sensory coding, and how biodiversity sustains ecological productivity. Here we propose that many of these well-understood findings across fields can be captured in one simple joint cross-disciplinary model, which we call the Distributed Production System. It captures how agent heterogeneity, resource constraints, communication topology, and task structure jointly determine the productivity, efficiency, and robustness of distributed systems across biology, economics, neuroscience, and computing. This model reveals that a small set of underlying laws generates the complex dynamics observed across fields. These can be summarised in our Principle of Maximum Heterogeneity: any distributed production system optimising for performance will converge on an increasingly heterogeneous configuration; environmental demands place an upper bound on the degree of heterogeneity required; and the communication topology determines the spatial scale over which heterogeneity spreads, with this principle applying recursively across all layers of nested production systems. Beyond explaining existing systems, these principles act as a blueprint for constructing ideal ones. We demonstrate this by suggesting specific redesigns for compute systems executing large-scale AI. In total, The Principle of Maximum Heterogeneity reveals a unique convergence of complex phenomena across fields onto simple underlying design principles with important predictive value for future distributed production systems.

Guillhem Artis, Danyal Akarca, Jascha Achterberg

Callosum, London, United Kingdom (www.callosum.com) · Imperial College London, London, United Kingdom · University of Cambridge, Cambridge, United Kingdom +1

Multi-Agent System OptimizationDistributed OptimizationHeterogeneous Computing
AskPDF
Apr 7, 2026

Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

We study asynchronous distributed decision-making for scalable multi-agent bandit submodular maximization. We are motivated by distributed information-gathering tasks in unknown environments and under heterogeneous inter-agent communication delays. To enable scalability despite limited communication delays, existing approaches restrict each agent to coordinate only with its one-hop neighbors. But these approaches assume homogeneous communication delays among the agents and a synchronous global clock. In practice, however, delays are heterogeneous, and agents operate with mismatched local clocks. That is, each agent does not receive information from all neighbors at the same time, compromising decision-making. In this paper, we provide an asynchronous coordination algorithm to overcome the challenges. We establish a provable approximation guarantee against the optimal synchronized centralized solution, where the suboptimality gap explicitly depends on communication delays and clock mismatches. The bounds also depend on the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only. The clock-mismatch penalty is expressed through a bounded oscillation of the reward in the execution times, which, unlike a Lipschitz condition, is available for discrete-valued rewards such as target monitoring. We validate the approach through numerical simulations on multi-camera target monitoring through the lenses of two different reward structures and simulation setups.

Pranjal Sharma, Zirui Xu, Vasileios Tzoumas

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA

Submodular OptimizationDistributed OptimizationMulti-Agent CoordinationCombinatorial Multi-Armed Bandits
AskPDF
Apr 7, 2026

Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements

We study mean estimation of a random vector XX in a distributed parameter-server-worker setup. Worker ii observes samples of ai⊤Xa_i^\top X, where ai⊤a_i^\top is the iith row of a known sensing matrix AA. The key challenges are adversarial measurements and asynchrony: a fixed subset of workers may transmit corrupted measurements, and workers are activated asynchronously--only one is active at any time. In our previous work, we proposed a two-timescale ℓ1\ell_1-minimization algorithm and established asymptotic recovery under a null-space-property-like condition on AA. In this work, we establish tight non-asymptotic convergence rates under the same null-space-property-like condition. We also identify relaxed conditions on AA under which exact recovery may fail but recovery of a projected component of E[X]\mathbb{E}[X] remains possible. Overall, our results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers, with implications for network tomography and related distributed sensing problems.

Nibedita Roy, Vishal Halder, Gugan Thoppe +4

Dept. of Computer Science and Automation, Indian Institute of Science, Bengaluru 560012, India · Department of Computer Science, IMT Atlantique, Plouzané 29280, France

Distributed InferenceRobust EstimationDistributed Optimization
AskPDF
Apr 3, 2026

Communication-free Sampling and 4D Hybrid Parallelism for Scalable Mini-batch GNN Training

Graph neural networks (GNNs) are widely used for learning on graph datasets derived from various real-world scenarios. Learning from extremely large graphs requires distributed training, and mini-batching with sampling is a popular approach for parallelizing GNN training. Existing distributed mini-batch approaches have significant performance bottlenecks due to expensive sampling methods and limited scaling when using data parallelism. In this work, we present ScaleGNN, a 4D parallel framework for scalable mini-batch GNN training that combines communication-free distributed sampling, 3D parallel matrix multiplication (PMM), and data parallelism. ScaleGNN introduces a uniform vertex sampling algorithm, enabling each process (GPU device) to construct its local mini-batch, i.e., subgraph partitions without any inter-process communication. 3D PMM enables scaling mini-batch training to much larger GPU counts than vanilla data parallelism with significantly lower communication overheads. We also present additional optimizations to overlap sampling with training, reduce communication overhead by sending data in lower precision, kernel fusion, and communication-computation overlap. We evaluate ScaleGNN on five graph datasets and demonstrate strong scaling up to 2048 GPUs on Perlmutter, 2048 GCDs on Frontier, and 1024 GPUs on Tuolumne. On Perlmutter, ScaleGNN achieves 3.5x end-to-end training speedup over the SOTA baseline on ogbn-products.

Cunyang Wei, Siddharth Singh, Aishwarya Sarkar +7

University of Maryland, College Park, USA · NVIDIA, Inc. · Iowa State University, USA +3

Graph Neural NetworksDistributed TrainingCommunication-Efficient Distributed TrainingDistributed Optimization
AskPDF
Mar 30, 2026

Gradient Manipulation in Distributed Stochastic Gradient Descent with Strategic Agents: Truthful Incentives with Convergence Guarantees

Distributed learning has gained significant attention due to its advantages in scalability, privacy, and fault tolerance.In this paradigm, multiple agents collaboratively train a global model by exchanging parameters only with their neighbors. However, a key vulnerability of existing distributed learning approaches is their implicit assumption that all agents behave honestly during gradient updates. In real-world scenarios, this assumption often breaks down, as selfish or strategic agents may be incentivized to manipulate gradients for personal gain, ultimately compromising the final learning outcome. In this work, we propose a fully distributed payment mechanism that, for the first time, guarantees both truthful behaviors and accurate convergence in distributed stochastic gradient descent. This represents a significant advancement, as it overcomes two major limitations of existing truthfulness mechanisms for collaborative learning:(1) reliance on a centralized server for payment collection, and (2) sacrificing convergence accuracy to guarantee truthfulness. In addition to characterizing the convergence rate under general convex and strongly convex conditions, we also prove that our approach guarantees the cumulative gain that an agent can obtain through strategic behavior remains finite, even as the number of iterations approaches infinity--a property unattainable by most existing truthfulness mechanisms. Our experimental results on standard machine learning tasks, evaluated on benchmark datasets, confirm the effectiveness of the proposed approach.

Ziqin Chen, Yongqiang Wang

Department of Electrical and Computer Engineering, Clemson University, Clemson, SC 29634 USA

Distributed TrainingDecentralized LearningDistributed OptimizationStochastic Optimization Convergence
AskPDF
Mar 27, 2026

High dimensional theory of two-phase optimizers

The trend towards larger training setups has brought a renewed interest in partially asynchronous two-phase optimizers which optimize locally and then synchronize across workers. Additionally, recent work suggests that the one-worker version of one of these algorithms, DiLoCo, shows promising results as a (synchronous) optimizer. Motivated by these studies we present an analysis of LA-DiLoCo, a simple member of the DiLoCo family, on a high-dimensional linear regression problem. We show that the one-worker variant, LA, provides a different tradeoff between signal and noise than SGD, which is beneficial in many scenarios. We also show that the multi-worker version generates more noise than the single worker version, but that this additional noise generation can be ameliorated by appropriate choice of hyperparameters. We conclude with an analysis of SLA -- LA with momentum -- and show that stacking two momentum operators gives an opportunity for acceleration via a non-linear transformation of the "effective'' Hessian spectrum, which is maximized for Nesterov momentum. Altogether our results show that two-phase optimizers represent a fruitful new paradigm for understanding and improving training algorithms.

Atish Agarwala

Google DeepMind

Momentum MethodsDistributed OptimizationHigh-Dimensional Linear Regression
AskPDF
Mar 26, 2026

Distributed Real-Time Vehicle Control for Emergency Vehicle Transit: A Scalable Cooperative Method

Rapid transit of emergency vehicles is critical for saving lives and reducing property loss but often relies on surrounding ordinary vehicles to cooperatively adjust their driving behaviors. It is important to ensure rapid transit of emergency vehicles while minimizing the impact on ordinary vehicles. Centralized mathematical solver and reinforcement learning are the state-of-the-art methods. The former obtains optimal solutions but is only practical for small-scale scenarios. The latter implicitly learns through extensive centralized training but the trained model exhibits limited scalability to different traffic conditions. Hence, existing methods suffer from two fundamental limitations: high computational cost and lack of scalability. To overcome above limitations, this work proposes a scalable distributed vehicle control method, where vehicles adjust their driving behaviors in a distributed manner online using only local instead of global information. We proved that the proposed distributed method using only local information is approximately equivalent to the one using global information, which enables vehicles to evaluate their candidate states and make approximately optimal decisions in real time without pre-training and with natural adaptability to varying traffic conditions. Then, a distributed conflict resolution mechanism is further proposed to guarantee vehicles' safety by avoiding their decision conflicts, which eliminates the single-point-of-failure risk of centralized methods and provides deterministic safety guarantees that learned methods cannot offer. Compared with existing methods, simulation experiments based on real-world traffic datasets demonstrate that the proposed method achieves faster decision-making, less impact on ordinary vehicles, and maintains much stronger scalability across different traffic densities and road configurations.

WenXi Wang, JunQi Zhang

School of Computer Science and Technology, Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, China

Intelligent Transportation SystemsMulti-Agent ControlDistributed Optimization
AskPDF
Mar 20, 2026

Distributed Gradient Clustering: Convergence and the Effect of Initialization

We study the effects of center initialization on the performance of a family of distributed gradient-based clustering algorithms introduced in [1], that work over connected networks of users. In the considered scenario, each user contains a local dataset and communicates only with its immediate neighbours, with the aim of finding a global clustering of the joint data. We perform extensive numerical experiments, evaluating the effects of center initialization on the performance of our family of methods, demonstrating that our methods are more resilient to the effects of initialization, compared to centralized gradient clustering [2]. Next, inspired by the KK-means++ initialization [3], we propose a novel distributed center initialization scheme, which is shown to improve the performance of our methods, compared to the baseline random initialization.

Aleksandar Armacki, Himkant Sharma, Dragana Bajović +3

Carnegie Mellon University, Pittsburgh, Pennsylvania, USA · Indian Institute of Technology Kharagpur, Kharagpur, India · Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia +1

ClusteringDistributed Optimization
AskPDF
Mar 18, 2026

Distributed Equilibrium-Seeking in Target Coverage Games via Self-Configurable Networks under Limited Communication

We study a target coverage problem in which a team of sensing agents, operating under limited communication, must collaboratively monitor targets that may be adaptively repositioned by an attacker. We model this interaction as a zero-sum game between the sensing team (known as the defender) and the attacker. However, computing an exact Nash equilibrium (NE) for this game is computationally prohibitive as the action space of the defender grows exponentially with the number of sensors and their possible orientations. Exploiting the submodularity property of the game's utility function, we propose a distributed framework that enables agents to self-configure their communication neighborhoods under bandwidth constraints and collaboratively maximize the target coverage. We establish theoretical guarantees showing that the resulting sensing strategies converge to an approximate NE of the game. To our knowledge, this is the first distributed, communication-aware approach that scales effectively for games with combinatorial action spaces while explicitly incorporating communication constraints. To this end, we leverage the distributed bandit-submodular optimization framework and the notion of Value of Coordination that were introduced in [1]. Through simulations, we show that our approach attains near-optimal game value and higher target coverage compared to baselines.

Jayanth Bhargav, Zirui Xu, Vasileios Tzoumas +2

Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907 USA · Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Multi-Agent CoordinationNash Equilibrium ComputationDistributed OptimizationZero-Sum Games
AskPDF
Mar 16, 2026

Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction

In collaborative and distributed learning, Byzantine robustness reflects a major facet of optimization algorithms. Such distributed algorithms are often accompanied by transmitting a large number of parameters, so communication compression is essential for an effective solution. In this paper, we propose Byz-DM21, a novel Byzantine-robust and communication-efficient stochastic distributed learning algorithm. Our key innovation is a novel gradient estimator based on a double-momentum mechanism, integrating recent advancements in error feedback techniques. Using this estimator, we design both standard and accelerated algorithms that eliminate the need for large batch sizes while maintaining robustness against Byzantine workers. We prove that the Byz-DM21 algorithm has a smaller neighborhood size and converges to ε\varepsilon-stationary points in O(ε−4)\mathcal{O}(\varepsilon^{-4}) iterations. To further enhance efficiency, we introduce a distributed variant called Byz-VR-DM21, which incorporates local variance reduction at each node to progressively eliminate variance from random approximations. We show that Byz-VR-DM21 provably converges to ε\varepsilon-stationary points in O(ε−3)\mathcal{O}(\varepsilon^{-3 }) iterations. Additionally, we extend our results to the case where the functions satisfy the Polyak-Łojasiewicz condition. Finally, numerical experiments demonstrate the effectiveness of the proposed method.

Yanghao Li, Changxin Liu, Yuhao Yi

Sichuan University · East China University of Science and Technology

Distributed OptimizationCommunication-Efficient Distributed Training
AskPDF
Mar 12, 2026

Byzantine-Robust Optimization under (L0,L1)(L_0, L_1)-Smoothness

We consider distributed optimization under Byzantine attacks in the presence of (L0,L1)(L_0,L_1)-smoothness, a generalization of standard LL-smoothness that captures functions with state-dependent gradient Lipschitz constants. We propose Byz-NSGDM, a normalized stochastic gradient descent method with momentum that achieves robustness against Byzantine workers while maintaining convergence guarantees. Our algorithm combines momentum normalization with Byzantine-robust aggregation enhanced by Nearest Neighbor Mixing (NNM) to handle both the challenges posed by (L0,L1)(L_0,L_1)-smoothness and Byzantine adversaries. We prove that Byz-NSGDM achieves a convergence rate of O(K−1/4)O(K^{-1/4}) up to a Byzantine bias floor proportional to the robustness coefficient and gradient heterogeneity. Experimental validation on heterogeneous MNIST classification, synthetic (L0,L1)(L_0,L_1)-smooth optimization, and character-level language modeling with a small GPT model demonstrates the effectiveness of our approach against various Byzantine attack strategies. An ablation study further shows that Byz-NSGDM is robust across a wide range of momentum and learning rate choices.

Arman Bolatov, Samuel Horváth, Martin Takáč +1

Mohamed bin Zayed University of Artificial Intelligence, UAE

Distributed OptimizationByzantine-Robust Federated LearningStochastic Gradient Descent
AskPDF
Mar 3, 2026

Overlapping Domain Decomposition for Distributed Pose Graph Optimization

We present ROBO (Riemannian Overlapping Block Optimization), a distributed and parallel approach to multi-robot pose graph optimization (PGO) based on the idea of overlapping domain decomposition. ROBO offers a middle ground between centralized and fully distributed solvers, where the amount of pose information shared between robots at each optimization iteration can be set according to the available communication resources. Sharing additional pose information between neighboring robots effectively creates overlapping optimization blocks in the underlying pose graph, which substantially reduces the number of iterations required to converge. Through extensive experiments on benchmark PGO datasets, we demonstrate the applicability and feasibility of ROBO in different initialization scenarios, using various cost functions, and under different communication regimes. We also analyze the tradeoff between the increased communication and local computation required by ROBO's overlapping blocks and the resulting faster convergence. We show that overlaps with an average inter-robot data cost of only 36 Kb per iteration can converge 3.1×\times faster in terms of iterations than state-of-the-art distributed PGO approaches. Furthermore, we develop an asynchronous variant of ROBO that is robust to network delays and suitable for real-world robotic applications.

Aneesa Sonawalla, Yulun Tian, Jonathan P. How

MIT Department of Aeronautics and Astronautics. · Draper Scholar, The Charles Stark Draper Laboratory, Cambridge, MA. · University of Michigan Robotics Department.

Pose Graph OptimizationRobotic OptimizationDistributed Optimization
AskPDF
Mar 1, 2026

riMESA: Consensus ADMM for Real-World Collaborative SLAM

Collaborative Simultaneous Localization and Mapping (C-SLAM) is a fundamental capability for multi-robot teams as it enables downstream tasks like planning and navigation. However, existing C-SLAM back-end algorithms that are required to solve this problem struggle to address the practical realities of real-world deployments (i.e. communication limitations, outlier measurements, and online operation). In this paper we propose Robust Incremental Manifold Edge-based Separable ADMM (riMESA) -- a robust, incremental, and distributed C-SLAM back-end that is resilient to outliers, reliable in the face of limited communication, and can compute accurate state estimates for a multi-robot team in real-time. Through the development of riMESA, we, more broadly, make an argument for the use of Consensus Alternating Direction Method of Multipliers as a theoretical foundation for distributed optimization tasks in robotics like C-SLAM due to its flexibility, accuracy, and fast convergence. We conclude this work with an in-depth evaluation of riMESA on a variety of C-SLAM problem scenarios and communication network conditions using both synthetic and real-world C-SLAM data. These experiments demonstrate that riMESA is able to generalize across conditions, produce accurate state estimates, operate in real-time, and outperform the accuracy of prior works by a factor >7x on real-world datasets.

Daniel McGann, Michael Kaess

The authors are with the Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA.

Simultaneous Localization and MappingPose Graph OptimizationAlternating Direction Method of MultipliersDistributed Optimization
AskPDF
Feb 27, 2026

A distributed semismooth Newton based augmented Lagrangian method for distributed optimization

This paper proposes a novel distributed semismooth Newton based augmented Lagrangian method for solving a class of optimization problems over networks, where the global objective is defined as the sum of locally held cost functions, and communication is restricted to neighboring agents. Specifically, we employ the augmented Lagrangian method to solve an equivalently reformulated constrained version of the original problem. Each resulting subproblem is solved inexactly via a distributed semismooth Newton method. By fully leveraging the structure of the generalized Hessian, a distributed accelerated proximal gradient method is proposed to compute the Newton direction efficiently, eliminating the need to communicate with full Hessian matrices. Theoretical results are also obtained to guarantee the convergence of the proposed algorithm. Numerical experiments demonstrate the efficiency and superiority of our algorithm compared to state-of-the-art distributed algorithms.

Qihao Ma, Chengjing Wang, Peipei Tang +2

School of Mathematics, Southwest Jiaotong University, No.999, Xian Road, West Park, High-tech Zone, Chengdu 611756, China · School of Computer and Computing Science, Hangzhou City University, Zhejiang Key Laboratory of Big Data Intelligent Computing, Hangzhou, 310015, China · Department of Control Science and Engineering, College of Electronics and Information Engineering, National Key Laboratory of Autonomous Intelligent Unmanned Systems, Tongji University, Shanghai 201804, China +1

Distributed OptimizationAugmented Lagrangian MethodConstrained Optimization
AskPDF
Feb 22, 2026

Event-Triggered Gossip for Distributed Learning

While distributed learning offers a new learning paradigm for distributed network with no central coordination, it is constrained by communication bottleneck between nodes. We develop a new event-triggered gossip framework for distributed learning to reduce inter-node communication overhead. The framework introduces an adaptive communication control mechanism that enables each node to autonomously decide in a fully decentralized fashion when to exchange model information with its neighbors based on local model deviations. We analyze the ergodic convergence of the proposed framework under noconvex objectives and interpret the convergence guarantees under different triggering conditions. Simulation results show that the proposed framework achieves substantially lower communication overhead than the state-of-the-art distributed learning methods, reducing cumulative point-to-point transmissions by 71.61% with only a marginal performance loss, compared with the conventional full-communication baseline.

Zhiyuan Zhai, Xiaojun Yuan, Wei Ni +3

Communication-Efficient Distributed TrainingDecentralized LearningDistributed Optimization
AskPDF
Feb 18, 2026

Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration

This paper is concerned with the distributed composite optimization problem over networks, where agents aim to minimize a sum of local smooth components and a common nonsmooth term. Leveraging the probabilistic local updates mechanism, we propose a communication-efficient Adapt-Then-Combine (ATC) framework, FlexATC, unifying numerous ATC-based distributed algorithms. Under stepsizes independent of the network topology and the number of local updates, we establish sublinear and linear convergence rates for FlexATC in convex and strongly convex settings, respectively. Remarkably, in the strong convex setting, the linear rate is decoupled from the objective functions and network topology, and FlexATC permits communication to be skipped in most iterations without any deterioration of the linear rate. In addition, the proposed unified theory demonstrates for the first time that local updates provably lead to communication acceleration for ATC-based distributed algorithms. Numerical experiments further validate the efficacy of the proposed framework and corroborate the theoretical results.

Luyao Guo, Xinli Shi, Wenying Xu +1

School of Computer Science and Engineering, Suzhou University of Technology, Suzhou 215500, China · School of Mathematics, Southeast University, Nanjing 210096, China · School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China

Distributed OptimizationNonsmooth Convex Optimization
AskPDF
Feb 16, 2026

Distributed Quantum Gaussian Processes for Multi-Agent Systems

Gaussian Processes (GPs) are a powerful tool for probabilistic modeling, but their performance is often constrained in complex, large-scale real-world domains due to the limited expressivity of classical kernels. Quantum computing offers the potential to overcome this limitation by embedding data into exponentially large Hilbert spaces, capturing complex correlations that remain inaccessible to classical computing approaches. In this paper, we propose a Distributed Quantum Gaussian Process (DQGP) method in a multi-agent setting to enhance modeling capabilities and scalability. To address the challenging non-Euclidean optimization problem, we develop a Distributed consensus Riemannian Alternating Direction Method of Multipliers (DR-ADMM) algorithm that aggregates local agent models into a global model. We evaluate the efficacy of our method through numerical experiments conducted on a quantum simulator in classical hardware. We use real-world, non-stationary elevation datasets of NASA's Shuttle Radar Topography Mission and synthetic datasets generated by Quantum Gaussian Processes. Beyond modeling advantages, our framework highlights potential computational speedups that quantum hardware may provide, particularly in Gaussian processes and distributed optimization.

Meet Gandhi, George P. Kontoudis

Colorado School of Mines, Golden, USA

Gaussian ProcessesQuantum Machine LearningMulti-Agent SystemsDistributed Optimization
AskPDF
Feb 3, 2026

Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods

Modern distributed optimization methods mostly rely on traditional synchronous approaches, despite substantial recent progress in asynchronous optimization. We revisit Synchronous SGD and its robust variant, called mm-Synchronous SGD, which can be interpreted as a method with a backup-worker strategy, and theoretically show that they are nearly optimal in many heterogeneous computation and communication scenarios, which is somewhat unexpected. We analyze the synchronous methods under random times and adversarial partial participation of workers, and prove that their time complexities are optimal in many practical regimes, up to logarithmic factors. While synchronous methods are not universal solutions and there exist tasks where asynchronous methods may be necessary, we show theoretically that they are sufficient for many modern heterogeneous computation and communication scenarios.

Grigory Begunov, Alexander Tyurin

AXXX, Moscow, Russia · Lomonosov Moscow State University, Moscow, Russia

Distributed OptimizationStochastic Gradient DescentStochastic Optimization ConvergenceHeterogeneous Computing
AskPDF
Feb 2, 2026

DASH: Faster Shampoo via Batched Block Preconditioning and Efficient Inverse-Root Solvers

Shampoo is one of the leading approximate second-order optimizers: a variant of it has won the MLCommons AlgoPerf competition, and it has been shown to produce models with lower activation outliers that are easier to compress. Yet, applying Shampoo currently comes at the cost of significant computational slowdown, due to its expensive internal operations. In this paper, we take a significant step to address this shortcoming by proposing \method (for Distributed Accelerated SHampoo), a faster implementation of Distributed Shampoo based on two main new techniques: First, we show that preconditioner blocks can be stacked into 3D tensors to significantly improve GPU utilization; second, we introduce the Newton-DB iteration and the Chebyshev polynomial approximations as novel and faster approaches for computing the inverse matrix roots required by Shampoo. Along with these algorithmic contributions, we provide a first in-depth analysis of how matrix scaling critically affects Shampoo convergence. On the practical side, our GPU-aware implementation achieves up to 5.6×5.6\times faster optimizer steps compared to the well-optimized Distributed Shampoo, while Newton-DB attains the lowest validation perplexity per iteration among all tested methods. Our code is available at https://github.com/IST-DASLab/DASH.

Ionut-Vlad Modoranu, Philip Zmushko, Erik Schultheis +2

Institute of Science and Technology Austria · Lancaster University · Red Hat AI

Deep Learning OptimizationGPU AccelerationDistributed OptimizationSecond-Order Optimization
AskPDF
Nov 4, 2025

Census-Based Population Autonomy For Distributed Robotic Teaming

Collaborating teams of robots show promise due to their ability to complete missions more efficiently and with improved robustness, attributes that are particularly useful for systems operating in marine environments. A key issue is how to model, analyze, and design these multi-robot systems to realize the full benefits of collaboration, a challenging task since the domain of multi-robot autonomy encompasses both collective and individual behaviors. This paper introduces a layered model of multi-robot autonomy that uses the principle of census, or a weighted count of the inputs from neighbors, for collective decision-making about teaming, coupled with multi-objective behavior optimization for individual decision-making about actions. The census component is expressed as a nonlinear opinion dynamics model and the multi-objective behavior optimization is accomplished using interval programming. This model can be reduced to recover foundational algorithms in distributed optimization and control, while the full model enables new types of collective behaviors that are useful in real-world scenarios. To illustrate these points, a new method for distributed optimization of subgroup allocation is introduced where robots use a gradient descent algorithm to minimize portions of the cost functions that are locally known, while being influenced by the opinion states from neighbors to account for the unobserved costs. With this method the group can collectively use the information contained in the Hessian matrix of the total global cost. The utility of this model is experimentally validated in three categorically different experiments with fleets of autonomous surface vehicles: an adaptive sampling scenario, a high value unit protection scenario, and a competitive game of capture the flag.

Tyler M. Paine, Anastasia Bizyaeva, Michael R. Benjamin

Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA · Woods Hole Oceanographic Institution Woods Hole, MA 02543, USA · Sibley School of Mechanical and Aerospace Engineering, Cornell University, Ithaca, NY 14853, USA

Multi-Robot CoordinationDistributed OptimizationMulti-Robot Task Allocation
AskPDF
Jul 26, 2025

Douglas-Rachford Splitting for Group-Sparse Feedback Linear-Quadratic Control

In this paper, we study the distributed linear quadratic problem with fixed communication topology (DFT-LQ) and the sparse feedback linear quadratic (SF-LQ) problem through a unified optimization framework. Specifically, both problems are formulated as a nonconvex, nonsmooth optimization problem equipped with an ℓ0\ell_0-penalty under affine constraints. To solve this problem, we first investigate the application of the Douglas-Rachford (DR) splitting algorithm. Under the local condition that the generated iterates remain on a fixed smooth manifold, we establish the convergence of the DR splitting to a stationary point. Furthermore, we characterize this stationary point as the global minimizer of a corresponding DFT-LQ problem. To bypass the restriction of the smooth manifold assumption, we introduce a projected subgradient descent algorithm that achieves global convergence without relying on smooth-manifold structures. This algorithm may serve as a warm-start mechanism that effectively drives the iterates toward the desired smooth manifolds, thereby establishing a favorable initialization where the convergence theory of the DR splitting algorithm becomes fully applicable. Numerical experiments shed light on the effectiveness of the proposed methods in distributed group-sparse controller design.

Lechen Feng, Xun Li, Yuan-Hua Ni

Department of Applied Mathematics, The Hong Kong Polytechnic University, China · College of Artificial Intelligence, Nankai University, Tianjin, China

Distributed OptimizationDistributed ControlNonconvex OptimizationFeedback ControlContinuous ControlLinear Quadratic Regulator
AskPDF