# On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 29 Sep 2021.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [Wasserstein Dependency Measure for Representation Learning](https://mlsanity.com/paper/1903.11780/) (2019)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Projection Robust Wasserstein Distance and Riemannian Optimization](https://mlsanity.com/paper/2006.07458/) (2020)
- [Towards Optimal Transport with Global Invariances](https://mlsanity.com/paper/1806.09277/) (2018)
- [A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance](https://mlsanity.com/paper/2012.05199/) (2020)
- [Iteration Complexity Analysis of Block Coordinate Descent Methods](https://mlsanity.com/paper/1310.6957/) (2013)
- [Alternating Randomized Block Coordinate Descent](https://mlsanity.com/paper/1805.09185/) (2018)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems](https://mlsanity.com/paper/1512.04680/) (2015)
- [Allocating Indivisible Items in Categorized Domains](https://mlsanity.com/paper/1504.05932/) (2015)

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

- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2304.02441/) (2023)
- [Decentralized and Equitable Optimal Transport](https://mlsanity.com/paper/2403.04259/) (2024)

## Abstract (arXiv)

This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon etal citescetbon2021equitable suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.