Decentralized and Equitable Optimal Transport

Abstract

This paper considers the decentralized (discrete) optimal transport (D-OT) problem. In this setting, a network of agents seeks to design a transportation plan jointly, where the cost function is the sum of privately held costs for each agent. We reformulate the D-OT problem as a constraint-coupled optimization problem and propose a single-loop decentralized algorithm with an iteration complexity of O(1/ε) that matches existing centralized first-order approaches. Moreover, we propose the decentralized equitable optimal transport (DE-OT) problem. In DE-OT, in addition to cooperatively designing a transportation plan that minimizes transportation costs, agents seek to ensure equity in their individual costs. The iteration complexity of the proposed method to solve DE-OT is also O(1/ε). This rate improves existing centralized algorithms, where the best iteration complexity obtained is O(1/ε^2).

Accepted to ACC 2024

References in corpus (10)

• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• Implicit Tracking-Based Distributed Constraint-Coupled Optimization
• On the Efficiency of Entropic Regularized Algorithms for Optimal Transport
• Recent Advances in Optimal Transport for Machine Learning
• Equitable and Optimal Transport with Multiple Agents
• On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
• Decentralized Entropic Optimal Transport for Distributed Distribution Comparison