Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis

Long Nguyen Chi, Nam Nguyen, Binh Nguyen
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:19438-19458, 2026.

Abstract

Quadratically 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 setting 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 $\varepsilon^{\frac{1}{d+2}}$ in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions in Wiesel & Xu (2025). We also show that the QOT value gap controls the mean-squared deviation $\mathbb E_{\pi_\varepsilon}||y-T(x)||^2$ by the scale of $\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 $\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 synthetic experiment in high dimensions setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-chi26c, title = {Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis}, author = {Chi, Long Nguyen and Nguyen, Nam and Nguyen, Binh}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {19438--19458}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/chi26c/chi26c.pdf}, url = {https://proceedings.mlr.press/v306/chi26c.html}, abstract = {Quadratically 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 setting 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 $\varepsilon^{\frac{1}{d+2}}$ in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions in Wiesel & Xu (2025). We also show that the QOT value gap controls the mean-squared deviation $\mathbb E_{\pi_\varepsilon}||y-T(x)||^2$ by the scale of $\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 $\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 synthetic experiment in high dimensions setting.} }
Endnote
%0 Conference Paper %T Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis %A Long Nguyen Chi %A Nam Nguyen %A Binh Nguyen %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-chi26c %I PMLR %P 19438--19458 %U https://proceedings.mlr.press/v306/chi26c.html %V 306 %X Quadratically 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 setting 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 $\varepsilon^{\frac{1}{d+2}}$ in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions in Wiesel & Xu (2025). We also show that the QOT value gap controls the mean-squared deviation $\mathbb E_{\pi_\varepsilon}||y-T(x)||^2$ by the scale of $\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 $\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 synthetic experiment in high dimensions setting.
APA
Chi, L.N., Nguyen, N. & Nguyen, B.. (2026). Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:19438-19458 Available from https://proceedings.mlr.press/v306/chi26c.html.

Related Material