Research map / Learning theory and algorithms / Optimal transport
Double-Bounded Optimal Transport for Advanced Clustering and Classification
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.
Proposes Double-Bounded Optimal Transport (DB-OT), which relaxes the target equality constraint to a [lower, upper] range, derives three entropic Sinkhorn-style solvers, and applies it to size-controlled clustering and long-tailed classification (loss and test-time inference).
Problem
Standard optimal transport requires fixed source and target marginals, which does not fit settings where target masses are uncertain and only bounded; this matters for cluster-size control and long-tailed classification.
Approach
Replace the equality constraint on the column sums of the coupling with two inequality bounds (b^d <= P^T 1 <= b^u), solve the entropic version with three Sinkhorn-like algorithms (Bregman, Sinkhorn-Knopp, dual), and use it both as a barycenter-based clustering assignment and as a loss/inference rule for long-tailed classification (Balanced Softmax is a special case with one iteration and delta=0)
Key results
- DB-OT loss reaches 81.9% average top-1 on CIFAR10-LT versus 79.0% for Balanced Softmax, and 47.9% on CIFAR100-LT versus 47.0%.
- DB-OT test-time inference on CIFAR100 with a vanilla Softmax model raises reverse-LT accuracy from 18.7% to 36.6% while keeping LT accuracy at 71.8%.
- On 2D Gaussian clustering, top-1 cluster accuracy is 82.67% for OT-LDA, 88.00% for DB-OT without reweighting, and 100.00% with reweighting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DB-OT loss instead of Balanced Softmax | long-tailed classification · CIFAR10-LT, All | Top-1 accuracy (%): 79.0 -> 81.9 | Helped |
| use DB-OT loss instead of Balanced Softmax | long-tailed classification · CIFAR100-LT, All | Top-1 accuracy (%): 47.0 -> 47.9 | Helped |
| use DB-OT loss instead of Balanced Softmax | long-tailed classification · ImageNet-LT, All | Top-1 accuracy (%): 41.1 -> 41.6 | Helped |
| replace vanilla Softmax inference with DB-OT inference | Vanilla Softmax Loss classifier · CIFAR100, Reverse LT | Top-1 accuracy (%): 18.7 -> 36.6 | Helped |
| replace vanilla Softmax inference with DB-OT inference | Vanilla Softmax Loss classifier · CIFAR100, Uniform | Top-1 accuracy (%): 42.0 -> 48.5 | Helped |
| replace vanilla Softmax inference with DB-OT inference | Vanilla Softmax Loss classifier · CIFAR100, LT | Top-1 accuracy (%): 71.6 -> 71.8 | No clear effect |
| replace vanilla Softmax inference with DB-OT inference | DB-OT loss classifier · CIFAR10-LT, LT / Uniform / Reverse LT | Top-1 accuracy (%): 85.3 -> 89.5; 79.7 -> 81.9; 64.1 -> 82.4 | Helped |
| add barycenter reweighting (ablation) | DB-OT clustering · Gaussian mixture synthetic clustering | Top-1 accuracy: 88.00% -> 100.00% | Helped |
| increase training iteration from 1 to 3 (ablation) | DB-OT classification · CIFAR10, testing iteration 10 | Top-1 accuracy: 75.2 -> 83.6 | Helped |
| increase training iteration from 3 to 5 (ablation) | DB-OT classification · CIFAR10, testing iteration 10 | Top-1 accuracy: 83.6 -> 78.5 | Hurt |
| vary training δ from 0 to 0.1–0.2 (ablation) | DB-OT loss · CIFAR10, inference δ=0, All | Top-1 accuracy: 81.8 -> 82.5; 81.8 -> 82.7 | Helped |
| increase inference δ from 0 to 0.8 (ablation) | DB-OT loss with training δ=0.2 · CIFAR10, All | Top-1 accuracy: 82.7 -> 79.9 | Hurt |
Surprising findings
- Test-time DB-OT inference applied to a vanilla Softmax model can outperform trained-for-balance baselines on uniform and reverse long-tailed test distributions, while the Balanced Softmax model's gain is smaller.
Limitations
- Clustering bounds control coupling column sums rather than strict sample counts, so cluster sizes are only softly controlled.
- Reported classification experiments use small backbones (ResNet32, ResNet10) and small datasets; results on larger models are not shown.
Experimental setup
Datasets: CIFAR10-LT CIFAR100-LT ImageNet-LT MNIST
Benchmarks: CIFAR10-LT CIFAR100-LT ImageNet-LT MNIST
Metrics: top-1 accuracy
Baselines: Vanilla Softmax LDAM Balanced Softmax Focal Loss LogitAdjust CB-CE classifier normalization class-aware bias K-means OT-LDA
Builds on: Sinkhorn algorithm unbalanced optimal transport inverse optimal transport Balanced Softmax OT-LDA
Closest papers by meaning
- Transport Clustering: Solving Low-Rank Optimal Transport via Clustering (ICML 2026 · similarity 0.89)
- A Swiss Army Knife for Minimax Optimal Transport (ICML 2020 · similarity 0.89)
- Relative Entropic Optimal Transport: a (Prior-aware) Matching Perspective to (Unbalanced) Classification (NeurIPS 2023 · similarity 0.88)
- An Optimal Transport View for Subspace Clustering and Spectral Clustering (AAAI 2024 · similarity 0.87)
- Hierarchical Refinement: Optimal Transport to Infinity and Beyond (ICML 2025 · similarity 0.87)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · 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.