mlsanityData to 7 Oct 2026

Safe Screening for Unbalanced Optimal Transport

arXiv 2307.00247 ↗First posted 1 Jul 2023math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

34 of 67 references.

References · 34

  1. 2022Flow Matching for Generative Modelingcited by 5,426
  2. 2021Convex optimizationcited by 2,479
  3. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  4. 2023Improving and generalizing flow-based generative models with minibatch optimal transportcited by 835
  5. 2015Optimal Transport for Domain Adaptationcited by 457
  6. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  7. 2019Generalized Sliced Wasserstein Distancescited by 205
  8. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 188
  9. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  10. 2017Smooth and Sparse Optimal Transportcited by 83
  11. 2016Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problemscited by 69
  12. 2021Low-Rank Sinkhorn Factorizationcited by 66
22 more
  1. 2019GOT: An Optimal Transport framework for Graph comparisoncited by 64
  2. 2020On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithmcited by 61
  3. 2018Scalable Unbalanced Optimal Transport using Generative Adversarial Networkscited by 41
  4. 2018Massively scalable Sinkhorn distances via the Nystr"om methodcited by 40
  5. 2023Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transportcited by 39
  6. 2016Gap Safe screening rules for sparsity enforcing penaltiescited by 38
  7. 2016Scaling Algorithms for Unbalanced Transport Problemscited by 36
  8. 2019Improving Sequence-to-Sequence Learning via Optimal Transportcited by 33
  9. 2018Celer: a Fast Solver for the Lasso with Dual Extrapolationcited by 31
  10. 2021Unbalanced Optimal Transport through Non-negative Penalized Linear Regressioncited by 31
  11. 2017Structured Optimal Transportcited by 30
  12. 2021Cross-domain Activity Recognition via Substructural Optimal Transportcited by 21
  13. 2018Wasserstein regularization for sparse multi-task regressioncited by 18
  14. 2019On a Combination of Alternating Minimization and Nesterov's Momentumcited by 18
  15. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  16. 2014Screening Tests for Lasso Problemscited by 15
  17. 2013Safe Screening With Variational Inequalities and Its Application to LASSOcited by 11
  18. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 10
  19. 2019Learning with Batch-wise Optimal Transport Loss for 3D Shape Recognitioncited by 8
  20. 2021Expanding boundaries of Gap Safe screeningcited by 7
  21. 2018Safe Triplet Screening for Distance Metric Learningcited by 4
  22. 2021Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squarescited by 4

Built on by

Not cited yet.