Research map / Learning theory and algorithms / Optimal transport
A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the (p,k)-RPW metric, the smallest epsilon such that the (1-epsilon)-partial p-Wasserstein distance is at most k*epsilon, which is robust to outliers and sampling noise while interpolating between TV and p-Wasserstein.
Problem
The p-Wasserstein distance (especially p>1) is sensitive to small outlier mass and sampling discrepancy, converging slowly from empirical samples; existing partial OT distances are not metrics and are zero for differences below delta.
Approach
Define a distance as the smallest epsilon where the (1-epsilon)-partial p-Wasserstein cost is at most k*epsilon (equivalently, an intersection of the OT-profile with the line y=k(1-x)); this yields a metric that bounds outlier sensitivity by delta and interpolates TV (k=0) and W_p/k (large k), and equals Levy-Prokhorov for p=infinity, k=1.
Key results
- The (2,k)-RPW metric is robust to outlier mass: adding delta mass changes the distance by at most delta, while W_2 can increase by 0.1 for delta=0.01.
- Empirical (2,1)-RPW converges at rate about n^{-1/3} in 2D versus n^{-1/4} for empirical 2-Wasserstein.
- On noisy MNIST, (2,1)-RPW outperforms 1-Wasserstein, 2-Wasserstein and TV retrieval accuracy in the noise-only and noise-plus-shift settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use (2,1)-RPW instead of 2-Wasserstein | Image retrieval · MNIST with noise (scenario i) | retrieval accuracy | Helped |
| Use (2,1)-RPW instead of 1-Wasserstein | Image retrieval · MNIST with noise (scenario i) | retrieval accuracy | Helped |
| Use (2,1)-RPW instead of TV | Image retrieval · MNIST with shifts (scenario ii) | retrieval accuracy | Helped |
| Use (2,1)-RPW instead of 2-Wasserstein | Image retrieval · MNIST with noise and shifts (scenario iii) | retrieval accuracy | Helped |
| Use (2,0.1)-RPW instead of 1-Wasserstein | Image retrieval · CIFAR-10 | retrieval accuracy | Helped |
| Use (2,1)-RPW instead of 2-Wasserstein | Empirical distribution distance estimation · 2-point distribution | convergence rate: n^{-\frac{1}{3}} vs. n^{-1/4} | Helped |
| Use (2,1)-RPW instead of 2-Wasserstein | Empirical distribution distance estimation · Grid distribution | convergence rate | Helped |
Limitations
- Gains demonstrated only on image retrieval and synthetic convergence experiments; no GAN or barycenter applications evaluated.
- Computing the distance requires partial OT solvers, with cubic-time exact algorithm; parallel algorithm left open.
- Results on CIFAR-10 and COREL depend on the choice of k (e.g., k=0.1 used), and sensitivity to k is not systematically studied.
Experimental setup
Datasets: MNIST CIFAR-10 COREL
Benchmarks: MNIST CIFAR-10 COREL
Metrics: retrieval accuracy convergence rate of empirical distance
Baselines: 1-Wasserstein distance 2-Wasserstein distance total variation distance lambda-ROBOT
Builds on: partial optimal transport OT-profile lambda-ROBOT Levy-Prokhorov distance
Closest papers by meaning
- Smooth $p$-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications (ICML 2021 · similarity 0.92)
- Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants (ICML 2025 · similarity 0.90)
- Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances (ICML 2025 · similarity 0.89)
- Sliced Wasserstein Estimation with Control Variates (ICLR 2024 · similarity 0.88)
- Partial Gromov-Wasserstein Metric (ICLR 2025 · similarity 0.87)
- Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.