Research map / Learning theory and algorithms / Optimal transport
Optimal Transport with Tempered Exponential Measures
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.
Extends entropic-regularized optimal transport to tempered exponential measures (TEMs), giving sparse plans, unbalanced OT with co-density normalization, and a Sinkhorn-like algorithm for approximation.
Problem
Entropic-regularized optimal transport yields maximally dense plans, while unregularized OT is sparse but scales poorly; unbalanced OT lacks tight control over total mass. The paper asks whether a generalization can offer both fast approximation and controllable sparsity.
Approach
Generalize the entropic regularizer to a Bregman divergence induced by negative tempered Tsallis entropy and optimize over tempered exponential measures normalized via co-densities; the regularized problem reduces to an unregularized OT with a modified cost matrix M' that can induce sparsity, and approximate solutions are computed by Sinkhorn-style alternating projections on a seed matrix.
Key results
- For n=32, the EOT (t=1) plan is fully dense with 1024 non-zero entries, while the t=1.9 tempered plan has only 83 non-zero values; unregularized OT has 2n-1=63.
- Experiments with n=64 show the number of Sinkhorn iterations to converge follows the contraction ratio of seed matrices, and relative expected cost is inversely related to iteration count.
- Theory: for t<=1 the tempered measured cost satisfies a relaxed triangle inequality; regularized measured cost equals an unregularized OT cost with a modified matrix M' = lambda M - (r c^T)^{1-t}/(1-t), whose structure yields provable sparsity patterns.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase t from 1 toward 2 in regularized expected-cost OT | TEM regularized expected-cost OT · Synthetic transport, n=32 | non-zero transport values: 1024 -> 83 | Helped |
| Increase the regularization parameter λ | TEM regularized OT · Synthetic transport | non-zero seed-matrix elements | Helped |
| Increase the regularization parameter λ | Sinkhorn approximation for TEM regularized OT · Synthetic transport, n=64 | iterations to converge | Hurt |
| Use larger t for the measured-cost seed matrix | Sinkhorn approximation for TEM measured-cost OT · Synthetic transport, n=64 | convergence | Helped |
Surprising findings
- Regularized OT with TEMs for t!=1 can produce sparse plans, which entropic regularization (t=1) cannot.
Limitations
- Approximate Sinkhorn solution is not exact since the solution set is non-convex for t!=1 and does not match the closed-form seed structure.
- Feasibility of the seed matrix for non-negative cases is not fully characterized; large lambda may make the seed too sparse to be feasible.
- Experiments are limited to synthetic random problems with small n.
Experimental setup
Metrics: relative expected cost number of Sinkhorn iterations number of non-zero plan entries contraction ratio
Baselines: entropic-regularized optimal transport (Sinkhorn, t=1) unregularized optimal transport
Builds on: Sinkhorn distances entropic regularized optimal transport exponential families tempered exponential families
Closest papers by meaning
- Submodular framework for structured-sparse optimal transport (ICML 2024 · similarity 0.89)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.88)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.88)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.86)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.86)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (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.