# Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 10 Mar 2021.

## Builds on (most cited first, 27 of 27)

- [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)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Style Transfer by Relaxed Optimal Transport and Self-Similarity](https://mlsanity.com/paper/1904.12785/) (2019)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Optimal Transport for Multi-source Domain Adaptation under Target Shift](https://mlsanity.com/paper/1803.04899/) (2018)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Adversarial Risk via Optimal Transport and Optimal Couplings](https://mlsanity.com/paper/1912.02794/) (2019)
- [Minimizing the Maximal Loss: How and Why?](https://mlsanity.com/paper/1602.01690/) (2016)
- [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019)
- [Generalized conditional gradient: analysis of convergence and applications](https://mlsanity.com/paper/1510.06567/) (2015)
- [LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space](https://mlsanity.com/paper/2012.03612/) (2020)
- [Inference with Aggregate Data: An Optimal Transport Approach](https://mlsanity.com/paper/2003.13933/) (2020)
- [Wasserstein k-means with sparse simplex projection](https://mlsanity.com/paper/2011.12542/) (2020)
- [Faster Coordinate Descent via Adaptive Importance Sampling](https://mlsanity.com/paper/1703.02518/) (2017)
- [Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs](https://mlsanity.com/paper/1605.09346/) (2016)
- [MAP inference via Block-Coordinate Frank-Wolfe Algorithm](https://mlsanity.com/paper/1806.05049/) (2018)
- [Convex Clustering via Optimal Mass Transport](https://mlsanity.com/paper/1307.5459/) (2013)

## Built on by (most cited first, 3 of 3)

- [Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis](https://mlsanity.com/paper/2111.01361/) (2021)
- [Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem](https://mlsanity.com/paper/2205.13766/) (2022)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)

## Abstract (arXiv)

Optimal transport (OT), which provides a distance between two probability distributions by considering their spatial locations, has been applied to widely diverse applications. Computing an OT problem requires solution of linear programming with tight mass-conservation constraints. This requirement hinders its application to large-scale problems. To alleviate this issue, the recently proposed relaxed-OT approach uses a faster algorithm by relaxing such constraints. Its effectiveness for practical applications has been demonstrated. Nevertheless, it still exhibits slow convergence. To this end, addressing a convex semi-relaxed OT, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm, which gives sparse solutions. Specifically, we provide their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Three fast variants of the proposed BCFW are also proposed. Numerical evaluations in color transfer problem demonstrate that the proposed algorithms outperform state-of-the-art algorithms across different settings.