Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis

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.

Optimal transport is widely used to infer correspondences between two distributions, but the regularization that makes it easier to compute can blur the coupling and obscure the map one hopes to estimate. Quadratic regularization is appealing because it yields sparser couplings, yet its small regularization behavior near the Monge map is not fully understood. We prove lower bounds showing that, under standard assumptions, quadratically regularized couplings cannot concentrate around the optimal map faster than a specific rate. This rules out a faster rate, rather than merely closing a gap in existing analysis. We also show that excess objective value controls the mean squared displacement from the optimal map, linking cost accuracy to map accuracy. For affine optimal maps, including Gaussian-to-Gaussian transport, we obtain a sharp accuracy bound and verify the predicted scaling on synthetic examples. These results clarify when sparse regularized transport is reliable for correspondence and map estimation, and where its accuracy has a built-in limit.