# Accelerated Algorithm for Sparse Regularized Partial Optimal Transport

arXiv: https://arxiv.org/abs/2609.40075 · HTML: https://mlsanity.com/paper/2609.40075/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 52 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 30 of 31)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Optimal Transport for Multi-source Domain Adaptation under Target Shift](https://mlsanity.com/paper/1803.04899/) (2018)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Accurate Point Cloud Registration with Robust Optimal Transport](https://mlsanity.com/paper/2111.00648/) (2021)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Quadratically-Regularized Optimal Transport on Graphs](https://mlsanity.com/paper/1704.08200/) (2017)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [Spatio-Temporal Alignments: Optimal transport through space and time](https://mlsanity.com/paper/1910.03860/) (2019)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Tsallis Regularized Optimal Transport and Ecological Inference](https://mlsanity.com/paper/1609.04495/) (2016)
- [Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems](https://mlsanity.com/paper/1612.01216/) (2016)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [Convex Color Image Segmentation with Optimal Transport Distances](https://mlsanity.com/paper/1503.01986/) (2015)
- [Correlated Attention in Transformers for Multivariate Time Series](https://mlsanity.com/paper/2311.11959/) (2023)
- [Enhancing Unsupervised Graph Few-shot Learning via Set Functions and Optimal Transport](https://mlsanity.com/paper/2501.05635/) (2025)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Sparsity of Quadratically Regularized Optimal Transport: Bounds on concentration and bias](https://mlsanity.com/paper/2410.03425/) (2024)
- [Understanding the Scalability of Hyperledger Fabric](https://mlsanity.com/paper/2107.09886/) (2021)
- [Partial Transport for Point-Cloud Registration](https://mlsanity.com/paper/2309.15787/) (2023)
- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)

## Abstract (arXiv)

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.