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

Optimal Transport (OT) has evolved from a classical mathematical problem to a versatile tool in machine learning, computer vision, and economics. Brenier’s theorem guarantees the existence of a Monge map under regularity conditions, facilitating geometric interpretations. Recent advances introduced entropic regularization (EOT), which improves computational efficiency but results in full support solutions, limiting sparsity interpretability. Conversely, quadratic regularization (QOT) exhibits empirical support sparsity, yet lacks rigorous quantitative bounds, especially in high dimensions. Understanding the support structure under regularization is crucial for interpretability, computational efficiency, and stability in large-scale problems, motivating the current study.

The core challenge lies in quantifying how the support of the quadratically regularized OT solution concentrates and how close it remains to the Monge map as the regularization parameter \(\epsilon\) approaches zero. Existing results show Hausdorff convergence but lack explicit bounds on support size and bias. This gap impairs the ability to select regularization parameters optimally and limits understanding of the sparsity phenomenon. Moreover, high-dimensional support behavior remains poorly understood, especially under general geometric conditions of μ and ν, making the problem both theoretically and practically significant.

The paper introduces a novel framework combining pointwise density bounds, the concept of ε-扩散δ(ε), and Minty’s trick to derive explicit support bounds. It extends previous one-dimensional or special-case results to general high-dimensional settings, providing sharp rates. The approach leverages the convexity of dual potentials, their approximate conjugacy, and the geometric properties of μ’s support, especially when star-shaped. This systematic quantification of support sparsity and bias under quadratic regularization is unprecedented, offering new insights into the structure of solutions and guiding practical parameter choices.

• �� Analyze dual potentials \(f_\epsilon, g_\epsilon\) to establish pointwise density bounds, introducing the ε-spread δ(ε) as a measure of μ’s uniformity.
• �� Use Minty’s trick to relate the duality gap to the support geometry, transforming bounds on the dual potentials into explicit support size and location estimates.
• �� Derive support concentration bounds by combining density bounds with geometric assumptions, especially for μ supported on star-shaped sets.
• �� In the μ=ν case, exploit symmetry and dual potential properties to obtain optimal support bias rates of \(\epsilon^{1/(2+d)}\).
• �� Validate bounds through rigorous inequalities involving Hausdorff distances, support diameters, and density measures, ensuring sharpness and generality.

Simulations on synthetic high-dimensional distributions with controlled support geometries verify the theoretical bounds. Varying ε demonstrates the predicted \(\epsilon^{1/(2+d)}\) support bias rate. Support size and bias are measured via Hausdorff distance and support diameter, confirming the bounds’ sharpness. Additional experiments compare the sparsity of QOT versus EOT, highlighting the support reduction in QOT. The robustness of δ(ε) as a measure of μ’s uniformity is tested across different support geometries, including star-shaped and irregular supports.

Theoretical bounds show that support support regions concentrate at a rate proportional to \(\sqrt{\delta(\epsilon)}\), with bias decreasing as \(\epsilon^{1/(2+d)}\). Empirical results align with these rates, confirming the sharpness of the bounds. In the μ=ν case, the support Hausdorff distance converges optimally, and support sparsity improves as ε diminishes. The bounds hold under mild regularity assumptions, providing a comprehensive quantitative picture of support behavior in high-dimensional quadratic regularized OT.

These results inform the design of scalable algorithms for high-dimensional data matching, image registration, and generative modeling, where support sparsity reduces computational load. The explicit bias bounds guide regularization parameter tuning, balancing sparsity and approximation accuracy. The theoretical insights also support interpretability in applications like domain adaptation and Wasserstein barycenters, where understanding support structure is crucial for meaningful solutions.

The bounds rely on assumptions such as μ’s support being compact, star-shaped, and having a Lipschitz boundary, limiting applicability to irregular or unbounded supports. The dependence on Lipschitz constants and geometric regularity may restrict extension to highly complex or fractal supports. Computationally, estimating δ(ε) and support bounds in practice remains challenging, especially in very high dimensions. Further work is needed to relax these assumptions and develop efficient algorithms for support estimation.