Accelerated method improves sparse transport plan computation
Accelerated Algorithm for Sparse Regularized Partial Optimal Transport
Machine Learning
Summary
Optimal transport is a way to match things from one group to another, but sometimes you only want part of the matching, which is called partial optimal transport. The authors focus on making this matching sparse, meaning only a few important connections are chosen, which helps with understanding and speed. They developed a new algorithm that uses advanced math tricks to find these sparse matches faster and better than older methods. Their tests on tasks like changing image colors, adapting machine learning models, and aligning 3D points show that their approach works well and is more efficient.
What this means in practice
- •For computer vision teams: Improve color transfer tasks by computing sparser and faster partial transport maps between images.
- •For machine learning developers: Accelerate domain adaptation by efficiently learning sparse transport plans to align different data distributions.
Authors
Khoa Nguyen, Dung T. Nguyen, Thong Huynh, Hoang-Hiep Nguyen-Mau, Anh Nguyen, Minh Ngoc Dinh, Juho Kannala
Abstract
Partial Optimal Transport (POT) extends the classical optimal transport problem by relaxing the strict mass conservation constraint, enabling its use in a wide range of real-world applications. In many of these settings, sparse transport plans are preferred for their interpretability and computational benefits. While smooth and strongly convex regularizers - such as quadratic or elastic net - have been vastly used in various machine learning applications to induce sparsity and accelerate computation, they have received less algorithmic attention compared to entropic approaches for computational POT. In this paper, we propose a new optimization framework that leverages these regularizers through a penalty-based reformulation, enabling efficient gradient-based updates while preserving the structure of the original problem. Our method accommodates a broad class of regularizers that promote structured and sparse transport plans. Building on this formulation, we design an accelerated first-order algorithm that alternates between smooth updates and simple projection steps. Through empirical benchmarks on color transfer, domain adaptation, and point cloud registration, our approach consistently outperforms established baselines - achieving lower transport cost, higher sparsity, and faster convergence - making it a practical and scalable solution for modern transport problems.