# Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [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)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [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)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [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)
- [Wasserstein k-means with sparse simplex projection](https://mlsanity.com/paper/2011.12542/) (2020)
- [Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs](https://mlsanity.com/paper/1605.09346/) (2016)
- [Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport](https://mlsanity.com/paper/2103.05857/) (2021)

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

- [Robust Estimation under the Wasserstein Distance](https://mlsanity.com/paper/2302.01237/) (2023)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [Control, Optimal Transport and Neural Differential Equations in Supervised Learning](https://mlsanity.com/paper/2503.15105/) (2025)
- [Anchor Space Optimal Transport as a Fast Solution to Multiple Optimal Transport Problems](https://mlsanity.com/paper/2310.16123/) (2023)
- [Take It or Leave It: Intent-Controlled Partial Optimal Transport](https://mlsanity.com/paper/2605.20030/) (2026)

## Abstract (arXiv)

The optimal transport (OT) problem has been used widely for machine learning. It is necessary for computation of an OT problem to solve linear programming with tight mass-conservation constraints. These constraints prevent its application to large-scale problems. To address this issue, loosening such constraints enables us to propose the relaxed-OT method using a faster algorithm. This approach has demonstrated its effectiveness for applications. However, it remains slow. As a superior alternative, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm for a convex semi-relaxed OT. Specifically, we prove their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Additionally, we develop two fast variants of the proposed BCFW. Numerical experiments have demonstrated that our proposed algorithms are effective for color transfer and surpass state-of-the-art algorithms. This report presents a short version of arXiv:2103.05857.