Research map / Learning theory and algorithms / Optimal transport
Sparsistency for inverse optimal transport
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.
Studies recovery (sparsistency) of the sparse support of a ground cost in inverse entropic optimal transport via an l1-regularized maximum-likelihood estimator, deriving an irrepresentability-type certificate and Gaussian closed forms that interpolate between Lasso and graphical Lasso.
Problem
Recovering the sparse ground cost (support) from samples of an entropic optimal transport coupling is ill-posed and noisy; theoretical guarantees for l1-regularized inverse OT were lacking.
Approach
Derives a non-degeneracy certificate (a generalized Lasso irrepresentability condition) for l1-iOT sparsistency, bounds the sample complexity for finite samples, and shows in the Gaussian case that the certificate interpolates between the Lasso (large epsilon) and the graphical Lasso (small epsilon).
Key results
- Establishes a sufficient non-degeneracy condition on the certificate for l1-iOT sparsistency and a finite-sample bound with sample complexity scaling as n^{-1/2} for the certificate.
- In the Gaussian case, the limit epsilon to infinity gives the Lasso certificate and epsilon to 0 gives the graphical Lasso certificate.
- Numerically, for epsilon=0.1 sparsistency cannot be achieved on a circular graph, while larger epsilon yields exact support recovery once the sample size N is large enough.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ε=0.1 | ℓ1-iOT · Circular graph support recovery | number of inaccurately estimated coordinates: For ε = 0.1, sparsistency cannot be achieved | Hurt |
| Increase ε | ℓ1-iOT · Circular graph support recovery | number of inaccurately estimated coordinates: for larger ε, sparsistency can be attained as soon as the number of samples N is sufficiently large | Helped |
| Increase ε | iOT certificate · Circular, planar, and Erdős–Rényi graphs | certificate non-degeneracy | Helped |
| Use small ε | iOT certificate · Graph support with nearby vertex pairs | certificate non-degeneracy | Hurt |
Surprising findings
- For small epsilon, pairs of vertices close in geodesic distance have the most degenerate certificates, so nearby edges are the most likely to be misestimated.
Limitations
- Analysis restricted to linear cost parameterizations (convexity), not neural costs.
- Sparsistency degrades and the problem becomes ill-posed for small entropic regularization epsilon.
- Gaussian closed forms are only for Gaussian marginals and quadratic costs; numerical illustrations use synthetic graphs only.
Experimental setup
Datasets: synthetic graph-structured cost matrices (circular, planar, Erdos-Renyi)
Metrics: number of wrongly estimated support coordinates certificate magnitude |z_ij|
Builds on: Lasso sparsistency theory Fenchel-Young loss Dupuy and Galichon inverse OT Galichon Gaussian entropic OT formulas
Closest papers by meaning
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.88)
- The Sparse-Plus-Low-Rank Quasi-Newton Method for Entropic-Regularized Optimal Transport (ICML 2025 · similarity 0.88)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.88)
- Safe and Sparse Newton Method for Entropic-Regularized Optimal Transport (NeurIPS 2024 · similarity 0.87)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.87)
- Submodular framework for structured-sparse optimal transport (ICML 2024 · similarity 0.87)
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.