Distributed accelerated algorithm improves optimal transport on bipartite graphs

A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs

Distributed, Parallel, and Cluster Computing

Summary

Optimal transport is a way to find the best way to move things from one place to another, which is useful in many fields like economics and machine learning. The authors noticed that existing methods for problems involving networks with two sets of points (bipartite graphs) can be slow and inefficient. They developed a faster and fully distributed algorithm allowing each point to communicate only with its neighbors, speeding up the process without needing a central controller. Their method also adjusts internal settings on its own to improve speed and comes with guarantees about how quickly it converges to the best solution.

What this means in practice

  • For machine learning engineers: Improve efficiency of allocation tasks involving network data by using the accelerated distributed algorithm for optimal transport on bipartite graphs.
  • For operations research teams: Speed up distributed resource allocation and supply chain optimization where network connectivity and unbalanced mass arise.

Authors

Jiayi Zhu, Haihang Lan

Abstract

Optimal transport (OT) has found broad applications in machine learning, economics, and management. Classical OT models, however, are not directly suited to allocation problems with graph-structured connectivity and unbalanced mass. Distributed OT formulations on bipartite graphs address these requirements but are typically solved by ADMM, whose slow convergence limits communication efficiency. We adapt the accelerated preconditioned ADMM (AP-ADMM) to the quadratically regularized distributed OT model and develop DAP-ADMM, a fully distributed algorithm in which each node communicates only with its graph neighbors. For fixed local penalty parameters, we establish global convergence and non-ergodic $O(1/k)$ bounds for both the KKT-residual norm and the primal objective gap. We derive an exact solver-free routine for the interval-constrained projections arising in the local ADMM subproblems. We propose a distributed self-adaptive penalty mechanism that updates node-specific penalties using locally computable KKT-residual components without global aggregation. Numerical experiments confirm the efficiency of the solver-free routine and the practical acceleration of DAP-ADMM over standard distributed ADMM.
View PDFOpen arXiv