# Partial Wasserstein Covering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 59 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [BDD100K: A Diverse Driving Dataset for Heterogeneous Multitask Learning](https://mlsanity.com/paper/1805.04687/) (2018)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Geometric Dataset Distances via Optimal Transport](https://mlsanity.com/paper/2002.02923/) (2020)
- [Deep Active Learning: Unified and Principled Method for Query and Training](https://mlsanity.com/paper/1911.09162/) (2019)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [On Scalable and Efficient Computation of Large Scale Optimal Transport](https://mlsanity.com/paper/1905.00158/) (2019)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Tight Approximation Bounds for the Seminar Assignment Problem](https://mlsanity.com/paper/1610.04785/) (2016)

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

- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [UniPROT: Uniform Prototype Selection via Partial Optimal Transport with Submodular Guarantees](https://mlsanity.com/paper/2604.10952/) (2026)
- [CoverPrune: Coverage-Driven Token Pruning for 3D VLMs via Optimal Transport](https://mlsanity.com/paper/2608.13226/) (2026)
- [StyleDiff: Attribute Comparison Between Unlabeled Datasets in Latent Disentangled Space](https://mlsanity.com/paper/2303.05102/) (2023)

## Abstract (arXiv)

We consider a general task called partial Wasserstein covering with the goal of providing information on what patterns are not being taken into account in a dataset (e.g., dataset used during development) compared with another dataset(e.g., dataset obtained from actual applications). We model this task as a discrete optimization problem with partial Wasserstein divergence as an objective function. Although this problem is NP-hard, we prove that it satisfies the submodular property, allowing us to use a greedy algorithm with a 0.63 approximation. However, the greedy algorithm is still inefficient because it requires solving linear programming for each objective function evaluation. To overcome this inefficiency, we propose quasi-greedy algorithms that consist of a series of acceleration techniques, such as sensitivity analysis based on strong duality and the so-called C-transform in the optimal transport field. Experimentally, we demonstrate that we can efficiently fill in the gaps between the two datasets and find missing scene in real driving scenes datasets.