Decentralized Optimization

Overview

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

63 papers6 papers in the last four weeks, down 60% on the four weeks before. 0.0% of all new papers.

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 agents, each representing an airspace sector, may 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 agent adjusts the departure times of its assigned flights to reduce its own congestion, without requiring centralized joint optimization. A tunable cooperativeness factor models the degree to which each agent accounts for overload in other sectors, while a minimal admissibility rule prevents local updates from creating new overloads. We show that this regulatory restriction is sufficient to guarantee finite-time convergence of best response dynamics to a pure Nash equilibrium under partial cooperation. 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 one month of European flight data demonstrate that the proposed algorithm substantially reduces overload even with only minimal cooperation, achieving performance close to a centralized global mixed-integer optimizer and exceeding a centralized first-come-first-served baseline while requiring substantially less computation than centralized optimization. We further evaluate departure delay and fairness to quantify the operational cost of overload mitigation.
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(T1−θ/2)O(T^{1-θ/2}) with communication complexity of O(Tθ)O(T^θ) and number of linear optimization oracle calls of O(T2θ)O(T^{2θ}) for decentralized upper-linearizable function optimization, for any 0≤θ≤10\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.
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.