# Fast Regularized Discrete Optimal Transport with Group-Sparse Regularizers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 14 Mar 2023.

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

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [DeCAF: A Deep Convolutional Activation Feature for Generic Visual Recognition](https://mlsanity.com/paper/1310.1531/) (2013)
- [Theoretical Analysis of Domain Adaptation with Optimal Transport](https://mlsanity.com/paper/1610.04420/) (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)
- [Cross-domain Activity Recognition via Substructural Optimal Transport](https://mlsanity.com/paper/2102.03353/) (2021)
- [Screening Sinkhorn Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1906.08540/) (2019)
- [Unsupervised Domain Adaptation using Regularized Hyper-graph Matching](https://mlsanity.com/paper/1805.08874/) (2018)
- [Sample-to-Sample Correspondence for Unsupervised Domain Adaptation](https://mlsanity.com/paper/1805.00355/) (2018)
- [Scaling associative classification for very large datasets](https://mlsanity.com/paper/1805.03887/) (2018)

## Abstract (arXiv)

Regularized discrete optimal transport (OT) is a powerful tool to measure the distance between two discrete distributions that have been constructed from data samples on two different domains. While it has a wide range of applications in machine learning, in some cases the sampled data from only one of the domains will have class labels such as unsupervised domain adaptation. In this kind of problem setting, a group-sparse regularizer is frequently leveraged as a regularization term to handle class labels. In particular, it can preserve the label structure on the data samples by corresponding the data samples with the same class label to one group-sparse regularization term. As a result, we can measure the distance while utilizing label information by solving the regularized optimization problem with gradient-based algorithms. However, the gradient computation is expensive when the number of classes or data samples is large because the number of regularization terms and their respective sizes also turn out to be large. This paper proposes fast discrete OT with group-sparse regularizers. Our method is based on two ideas. The first is to safely skip the computations of the gradients that must be zero. The second is to efficiently extract the gradients that are expected to be nonzero. Our method is guaranteed to return the same value of the objective function as that of the original method. Experiments show that our method is up to 8.6 times faster than the original method without degrading accuracy.