Sparsity of Quadratically Regularized Optimal Transport: Bounds on concentration and bias

2024/10/04 by Johannes Wiesel, Wiesel, Johannes, Xingyu Xu +1 · 3 citations
Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2410.03425

openalex publication_date 2024/10/04 · openalex created_date 2024/10/31 · openalex updated_date 2026/07/28

Abstract

We study the quadratically regularized optimal transport (QOT) problem for quadratic cost and compactly supported marginals μ and ν. It has been empirically observed that the optimal coupling π_ε for the QOT problem has sparse support for small regularization parameter ε>0. In this article we provide the first quantitative description of this phenomenon in general dimension: we derive bounds on the size and on the location of the support of π_ε compared to the Monge coupling. Our analysis is based on pointwise bounds on the density of π_ε together with Minty's trick, which provides a quadratic detachment from the optimal transport duality gap. In the self-transport setting μ=ν we obtain optimal rates of order ε^(1)/(2+d).

Cited by

• Marginal flows of non-entropic weak Schrödinger bridges
• General Divergence Regularized Optimal Transport: Sample Complexity and Central Limit Theorems
• Linear Convergence of Gradient Descent for Quadratically Regularized Optimal Transport

Related

• Sparsity of Quadratically Regularized Optimal Transport: Scalar Case
• Infinitesimal behavior of Quadratically Regularized Optimal Transport and its relation with the Porous Medium Equation
• Sample Complexity of Quadratically Regularized Optimal Transport
• Quadratically Regularized Optimal Transport: Existence and Multiplicity of Potentials
• Sharp Asymptotics for Regularized Optimal Transport