# Safe Screening for Unbalanced Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 67 references that are in the map.
- First posted on arXiv 1 Jul 2023.

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

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Scalable Unbalanced Optimal Transport using Generative Adversarial Networks](https://mlsanity.com/paper/1810.11447/) (2018)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transport](https://mlsanity.com/paper/2305.14777/) (2023)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Scaling Algorithms for Unbalanced Transport Problems](https://mlsanity.com/paper/1607.05816/) (2016)
- [Improving Sequence-to-Sequence Learning via Optimal Transport](https://mlsanity.com/paper/1901.06283/) (2019)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Cross-domain Activity Recognition via Substructural Optimal Transport](https://mlsanity.com/paper/2102.03353/) (2021)
- [Wasserstein regularization for sparse multi-task regression](https://mlsanity.com/paper/1805.07833/) (2018)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Screening Tests for Lasso Problems](https://mlsanity.com/paper/1405.4897/) (2014)
- [Safe Screening With Variational Inequalities and Its Application to LASSO](https://mlsanity.com/paper/1307.7577/) (2013)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)

## Abstract (arXiv)

This paper introduces a framework that utilizes the Safe Screening technique to accelerate the optimization process of the Unbalanced Optimal Transport (UOT) problem by proactively identifying and eliminating zero elements in the sparse solutions. We demonstrate the feasibility of applying Safe Screening to the UOT problem with ℓ2-penalty and KL-penalty by conducting an analysis of the solution's bounds and considering the local strong convexity of the dual problem. Considering the specific structural characteristics of the UOT in comparison to general Lasso problems on the index matrix, we specifically propose a novel approximate projection, an elliptical safe region construction, and a two-hyperplane relaxation method. These enhancements significantly improve the screening efficiency for the UOT's without altering the algorithm's complexity.