Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis
Long Nguyen-Chi, Nam Nguyen, Binh T. Nguyen · 2026
Read Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis by Long Nguyen-Chi, Nam Nguyen, Binh T. Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24644.txt.
Introduction
Long Nguyen-Chi and others study quadratically regularized optimal transport, an alternative to entropic regularization with sparse couplings. One open question was how fast optimizer support concentrates around the Monge coupling. They prove concentration cannot beat a stated power-law rate in directed Hausdorff distance. That rate matches the conjectured best exponent. The value gap also controls mean-squared deviation at a related rate. In the affine Brenier case, a sharp pointwise tube bound follows by reduction to self-transport. A synthetic high-dimensional experiment backs the theory.
Catalog record
| CREATOR | Long Nguyen-Chi, Nam Nguyen, Binh T. Nguyen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71899 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis Long Nguyen-Chi, Nam Nguyen, Binh T. Nguyen Abstract Quadratic regularization has emerged as a potential alternative to the popular entropic regularization in computational optimal transport, offering the theoretical advantage of producing sparse couplings through its hinge density structure. Despite recent progress in one-dimensional settings and general upper bounds, fundamental questions about the localization rate of QOT optimizers around the Monge coupling have remained open. In this work, we establish a general lower bound showing that the support of the QOT optimizer cannot concentrate around the Monge graph faster than order ε 1 d + 2 \varepsilon^{\frac{1}{d+2}} in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions in 35 . We also show that the QOT value gap controls the mean-squared deviation 𝔼 π ε ‖ y − T ( x ) ‖ 2 \mathbb{E}_{\pi_{\varepsilon}}\|y-T(x)\|^{2} by the scale of ε 2 d + 2 \varepsilon^{\frac{2}{d+2}} . As a corollary, in the affine Brenier regime, which includes Gaussian-to-Gaussian transport, we derive a sharp pointwise tube bound of order ε 1 d + 2 \varepsilon^{\frac{1}{d+2}} by reducing the problem to self-transport and applying recent self-transport sparsity results. Finally, we validate our theoretical bound with a synthetic experiment in high-dimensional settings. 1 Introduction The optimal transport (OT) problem concerns the task of moving probability measures from a source to a target location ( 27 ) . It has seen multiple applications in machine learning in recent years, including distribution alignment for (unsupervised) domain adaptation ( 8 ) , training generative models with Wasserstein/Sinkhorn OT losses ( 1 ; 14 ) , and using Wasserstein-based losses in structured prediction (including multi-label learning) ( 12 ) . OT also appears in modern generative modeling: flow matching can be instantiated with OT displacement interpolation (Wasserstein geodesics) as the probability path ( 22 ) , and related ODE-based transport methods (e.g., rectified-flow variants) are explicitly OT-motivated ( 23 ) . In computational biology, OT-based models are used for single-cell data integration and for learning perturbation responses ( 32 ; 6 ; 5 ) . In NLP (Natural Language Processing), the Word Mover’s Distance casts document comparison as an OT problem over word embeddings ( 21 ) . Formally, let \mu,\nu\in\mathcal{P}(\mathbb{R}^{d}) be Borel probability measures and let c:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R} be a measurable cost. In Monge’s original formulation, one seeks a measurable map T:\mathbb{R}^{d}\to\mathbb{R}^{d} pushing \mu to \nu (i.e. T_{\#}\mu=\nu ) and minimizing \mathrm{OT}(\mu,\nu)\coloneqq\inf_{T:T_{\#}\mu=\nu}\int c\bigl(x,T(x)\bigr)\mu(dx), where T_{\#}\mu(B)\coloneqq\mu\bigl(T^{-1}(B)\bigr) for all Borel sets B\subseteq\mathbb{R}^{d} . The Kantorovich optimal transport formulation ( 20 ) relaxes the mapping constraint by couplings and yields the convex problem \mathrm{OT}(\mu,\nu)\coloneqq\inf_{\pi\in\Pi(\mu,\nu)}\int c(x,y)\pi(dx,dy), where \Pi(\mu,\nu) is the set of couplings with marginal \mu,\nu : \displaystyle\Pi(\mu,\nu)\coloneqq\{\pi\in\mathcal{P}(\mathbb{R}^{d}\times\mathbb{R}^{d}): \displaystyle\pi(\cdot\times\mathbb{R}^{d})=\mu, \displaystyle\pi(\mathbb{R}^{d}\times\cdot)=\nu\}. Throughout this paper, we focus on the quadratic cost c(x,y)=\frac{1}{2}\|x-y\|^{2} , where \|\cdot\| denotes the Euclidean norm. In this case, if \mu\ll\mathrm{Leb} , and \mu,\nu have finite second moments, Brenier’s theorem ( 4 ) asserts that the Monge and Kantorovich problems coincide and admit a unique optimizer, which means, there exists a convex function \varphi:\mathbb{R}^{d}\to\mathbb{R} such that the map T\coloneqq\nabla\varphi satisfies T_{\#}\mu=\nu and the optimal plan is \pi_{\star}=(\mathrm{Id},T)_{\#}\mu . We refer the readers to 34 for background and further details. Regularization and sparsity. Regularization is ubiquitous in computational OT and in machine learning applications by improving the scalability of the OT problem ( 30 ) . A classical choice is entropic regularization ( 9 ) , which leads to Sinkhorn-type algorithms but produces dense couplings: the optimizer \pi^{\mathrm{ent}}_{\varepsilon} has a strictly positive density w.r.t P=\mu\otimes\nu . Quadratically regularized optimal transport (QOT) replaces the entropic penalty by a squared L^{2}(\mu\otimes\nu) penalty (equivalently a \chi^{2} divergence up to an additive constant), and has been advocated as a sparsity-promoting alternative in both discrete and continuous settings ( 3 ; 33 ; 11 ; 24 ) . A key structural difference from entropic OT is that the QOT optimizer admits a hinge (truncation) density formula (cf. ( 2.2 )), in contrast to the strictly positive Gibbs density of entropic OT. This hinge structure produces exact zeros whenever the dual slack is negative, and therefore directly exposes sparsity through strict inequalities in the dual slack ( 24 ; 29 ) . More precisely, fix \varepsilon>0 and set the reference measure P\coloneqq\mu\otimes\nu . For \pi\ll P , we study the \chi^{2}/L^{2} (quadratic) regularization \mathrm{QOT}_{\varepsilon}(\mu,\nu)\coloneqq\\ \inf_{\pi\in\Pi(\mu,\nu)}\Big\{\int c(x,y)d\pi(x,y)+\frac{\varepsilon}{2}\Big\|\frac{d\pi}{dP}\Big\|_{L^{2}(P)}^{2}\Big\}, (1.1) which differs from the \chi^{2} -divergence D_{\chi^{2}}(\pi\|P)=\int(\frac{d\pi}{dP}-1)^{2}dP only by an additive constant in the objective. Here, \varepsilon>0 is the regularization parameter and d\pi/dP denotes the Radon-Nikodym derivative. Localization around the Monge coupling. We denote by \pi_{\varepsilon} the unique optimizer of the QOT problem ( 1.1 ). A natural question is: as \varepsilon\downarrow 0 , how fast does the optimizer \pi_{\varepsilon} concentrate around the Monge graph \gr T ? This question quantifies the intrinsic sparsity-accuracy tradeoff of QOT: the hinge density promotes sparse support, but a small \varepsilon is needed for \pi_{\varepsilon} to approximate the Monge coupling \pi_{\star} . Controlling the tube thickness around \gr T is also practically relevant when \pi_{\varepsilon} is used as a sparse correspondence/graph (or via barycentric projection to estimate transport maps), rather than only through its scalar cost value ( 26 ; 31 ) . Recent statistical analyses of sparsity-promoting regularized OT further suggest that quantitative control of the geometry of \spt\pi_{\varepsilon} is a key input for obtaining parametric sample complexity for sparse regularizers, including quadratic regularization ( 15 ; 16 ) . We quantify this by the directed Hausdorff distance and vertical bias r\coloneqq\dist(\spt\pi_{\varepsilon};\gr T),b\coloneqq\sup_{(x,y)\in\spt\pi_{\varepsilon}}\|y-T(x)\|. When T is L -Lipschitz, r\leq b\leq\sqrt{1+L^{2}}r (Lemma 3.1 ). Recent work has begun to quantify how \spt\pi_{\varepsilon} concentrates around the Monge coupling as \varepsilon\downarrow 0 , obtaining sharp rates in one dimension and the first general-dimensional upper bounds under geometric and spread assumptions ( 17 ; 35 ; 18 ) . However, outside the self-transport case \mu=\nu , the available general-dimensional upper bounds do not match the conjectured \varepsilon^{1/(d+2)} scale under standard assumptions. Moreover, prior to this work, a general lower bound ruling out faster-than- \varepsilon^{1/(d+2)} concentration was not available. Our contribution can be summarized as follows. Contributions. We provide the following results for the QOT problem with the quadratic cost c(x,y)\coloneqq\frac{1}{2}\|x-y\|^{2} . 1. A general lower bound with the conjectured exponent. Under standard regularity assumptions on \mu,\nu and the Lipschitzness of the Monge map T , we prove that \spt\pi_{\varepsilon} cannot concentrate around \gr T faster than order \varepsilon^{1/(d+2)} in directed Hausdorff distance (Theorem 3.3 ). 2. Mean-squared and high-probability bias from the QOT value gap. We show that the QOT value gap \Delta_{\varepsilon} upper bounds the mean-squared deviation from the Monge map under \pi_{\varepsilon} (Lemma 3.5 ). Combining this with sharp value-gap rates from 10 yields the \varepsilon^{2/(d+2)} mean-square scale and a simple tail bound for \|Y-T(X)\| when (X,Y)\sim\pi_{\varepsilon} (Theorem 3.6 ). 3. Affine regime: sharp pointwise upper bound. When T is affine ( T(x)=Ax+b with A\succ 0 , including Gaussian-to-Gaussian transport), we obtain the sharp pointwise bias upper bound \sup_{(x,y)\in\spt\pi_{\varepsilon}}\|y-T(x)\|\lesssim\sqrt{\lambda_{\max}(A)}\varepsilon^{1/(d+2)} (Theorem 3.7 ). Organization. Section 2 introduces the background for understanding the whole paper, Section 3 gives the three results above, Section 4 shows the important results in QOT, Section 5 provides synthetic experiments validating the \varepsilon^{1/(d+2)} scaling in the affine Brenier