pith. sign in

arxiv: 2605.24644 · v2 · pith:HZ4EPYJ7new · submitted 2026-05-23 · 🧮 math.OC · stat.ML

Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis

Long Nguyen-Chi , Nam Nguyen , Binh Nguyen This is my paper

Pith reviewed 2026-06-30 13:07 UTC · model grok-4.3

classification 🧮 math.OC stat.ML
keywords quadratically regularized optimal transportlocalization boundsMonge graphdirected Hausdorff distanceaffine Brenier regimevalue gapGaussian transportsparsity
0
0 comments X

The pith

Quadratically regularized optimal transport cannot localize around the Monge graph faster than order ε to the power 1 over d plus 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves a lower bound on the rate at which solutions to quadratically regularized optimal transport can approach the Monge graph. The directed Hausdorff distance between the support of the optimizer and the graph stays at least on the order of ε raised to 1 over d plus 2. The bound matches the rate conjectured to be optimal under standard assumptions on the measures and cost. The paper further shows that the regularization gap controls the expected squared deviation from the transport map at the related scale ε to the power 2 over d plus 2. In the special affine Brenier setting, including Gaussian-to-Gaussian transport, the same order yields a pointwise tube bound after reduction to self-transport.

Core claim

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)} in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions. We also show that the QOT value gap controls the mean-squared deviation E_{π_ε} ||y-T(x)||^2 by the scale of ε^{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)} by reducing the problem to self-transport and applying recent self-transport sparsity results.

What carries the argument

The directed Hausdorff distance between the support of the quadratically regularized coupling and the Monge graph, which quantifies the localization rate.

If this is right

  • The value gap bounds expected squared deviation from the Monge map by ε^{2/(d+2)}.
  • In the affine Brenier regime a pointwise tube bound holds at order ε^{1/(d+2)}.
  • The lower bound matches the conjectured optimal exponent.
  • The theoretical rates are consistent with synthetic high-dimensional experiments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The dimension-dependent slowdown in high d implies that quadratic regularization may require careful ε scaling to achieve usable sparsity in practice.
  • The self-transport reduction technique could be applied to other structured transport problems beyond the affine case.
  • Similar lower bounds on localization might hold for other regularizers whose dual densities exhibit comparable hinge-like behavior.
  • Numerical checks of the bound in non-affine settings would test how sharply the rate depends on the regularity assumptions.

Load-bearing premise

The measures and cost function satisfy the standard regularity assumptions that make the conjectured exponent optimal.

What would settle it

An explicit example or numerical case, under those regularity assumptions, where the support concentrates around the Monge graph at a rate strictly faster than ε^{1/(d+2)} in directed Hausdorff distance.

Figures

Figures reproduced from arXiv: 2605.24644 by Binh Nguyen, Long Nguyen-Chi, Nam Nguyen.

Figure 1
Figure 1. Figure 1: Affine Brenier scaling diagnostics across dimensions: fitted log-log slope βb (left) and relative error (d + 2)βb − 1 (right). Error bars show ±1 empirical standard deviation over R = 10 random seeds. where (r, s) = F(f, g) are the residuals defined in (B.3). Thus |ri | ≤ initTolε and |sj | ≤ initTolε guarantee [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
read the original 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 $\varepsilon^{\frac{1}{d+2}}$ in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions in \citet{wiesel2025sparsity}. 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 a synthetic experiment in high-dimensional settings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper establishes a general lower bound showing that the support of the QOT optimizer cannot concentrate around the Monge graph faster than order ε^{1/(d+2)} in the directed Hausdorff distance, matching the conjectured optimal exponent under standard regularity assumptions from wiesel2025sparsity. It further shows that the QOT value gap controls the mean-squared deviation E_{π_ε} ||y - T(x)||^2 at scale ε^{2/(d+2)}. As a corollary, in the affine Brenier regime (including Gaussian-to-Gaussian transport), a sharp pointwise tube bound of order ε^{1/(d+2)} is derived by reduction to self-transport. The results are validated via a synthetic experiment in high dimensions.

Significance. If the lower bound holds, the work resolves an open question on the localization rate of QOT optimizers, providing the first matching lower bound to the conjectured exponent and new corollaries for the value gap and affine case. The reduction to self-transport sparsity results and high-dimensional numerical validation are strengths that enhance the contribution to the theory of quadratic regularization in optimal transport.

minor comments (3)
  1. [Abstract] Abstract: the statement of the lower bound and corollaries would benefit from explicit theorem or proposition numbers to allow immediate cross-reference to the proofs in the main text.
  2. The regularity assumptions on the measures and cost (referenced from wiesel2025sparsity) should be restated concisely in the main text or an appendix to make the manuscript self-contained.
  3. The synthetic experiment section would be strengthened by reporting the precise dimensions, sample sizes, and quantitative error metrics alongside the qualitative validation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, accurate summary of the contributions, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives a new general lower bound on the directed Hausdorff distance of the QOT support to the Monge graph (order ε^{1/(d+2)}), explicitly positioned as matching an external conjecture from the cited wiesel2025sparsity under referenced regularity assumptions. The value-gap control on mean-squared deviation and the affine-case tube bound are corollaries obtained by reduction to self-transport sparsity results from the literature. No equations or steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the central claim introduces independent content resolving a prior open question rather than renaming or tautologically reproducing its own assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard regularity assumptions drawn from the cited prior work; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption standard regularity assumptions on the measures and cost function as in wiesel2025sparsity
    Invoked explicitly for the lower bound to hold in general dimension.

pith-pipeline@v0.9.1-grok · 5754 in / 1169 out tokens · 27833 ms · 2026-06-30T13:07:02.501400+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    and Manole, T

    Balakrishnan, S. and Manole, T. Stability bounds for smooth optimal transport maps and their statistical implications. arXiv preprint arXiv:2502.12326,

    work page arXiv

  2. [2]

    Infinitesimal behavior of quadratically regularized opti- mal transport and its relation with the porous medium equation.arXiv preprint arXiv:2407.21528,

    Garriz-Molina, A., Gonz ´alez-Sanz, A., and Mordant, G. Infinitesimal behavior of quadratically regularized opti- mal transport and its relation with the porous medium equation.arXiv preprint arXiv:2407.21528,

    work page arXiv

  3. [3]

    and Nutz, M

    Gonz´alez-Sanz, A. and Nutz, M. Sparsity of quadratically regularized optimal transport: Scalar case.arXiv preprint arXiv:2410.03353,

    work page arXiv

  4. [4]

    Sample complexity of quadratically regularized optimal transport

    9 Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis Gonz´alez-Sanz, A., del Barrio, E., and Nutz, M. Sample complexity of quadratically regularized optimal transport. arXiv preprint arXiv:2511.09807, 2025a. Gonz´alez-Sanz, A., Eckstein, S., and Nutz, M. Sparse regu- larized optimal transport without curse of dimensi...

    work page arXiv

  5. [5]

    T., Ben-Hamu, H., Nickel, M., and Le, M

    Lipman, Y ., Chen, R. T., Ben-Hamu, H., Nickel, M., and Le, M. Flow matching for generative modeling. In11th International Conference on Learning Representations, ICLR 2023,

    2023

  6. [6]

    Rectified Flow: A Marginal Preserving Approach to Optimal Transport

    Liu, Q. Rectified flow: A marginal preserving approach to optimal transport.arXiv preprint arXiv:2209.14577,

    work page internal anchor Pith review Pith/arXiv arXiv

  7. [7]

    A., Manns, P., and Meyer, C

    Lorenz, D. A., Manns, P., and Meyer, C. Quadratically regularized optimal transport.Applied Mathematics & Optimization, 83(3):1919–1949,

    1919

  8. [8]

    and Niles-Weed, J

    Pooladian, A.-A. and Niles-Weed, J. Entropic estimation of optimal transport maps.arXiv preprint arXiv:2109.12004,

    work page arXiv

  9. [9]

    Thereforem ε >0

    12 Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis This contradictsπ ε ≪µ⊗ν. Thereforem ε >0. Lett= √2mε. By Markov’s inequality applied toZ, πε {(x, y) :∥y−T(x)∥ ≤t} =π ε({Z≤2m ε})≥ 1 2 . Forν-a.e.y, define a(y) := Z T −1(B(y,t)) h(x, y)µ(dx). Then0≤a(y)≤1forν-a.e.y, and Z a(y)ν(dy) =π ε({(x, y) :∥y−T(x)∥ ≤t})≥ 1...

    2025

  10. [10]

    Writing A−1(y−a)−m 0 =A −1 y−(Am 0 +a) , we may rewrite the right-hand side of (A.10) as y−(Am 0 +a) ⊤ A−⊤Σ−1 0 A−1 y−(Am 0 +a) +C

    = A−1(y−a)−m 0 ⊤ Σ−1 0 A−1(y−a)−m 0 +C, (A.10) Both sides of (A.10) are quadratic polynomials in y; since Ω1 has nonempty interior, they agree as polynomials on Rd. Writing A−1(y−a)−m 0 =A −1 y−(Am 0 +a) , we may rewrite the right-hand side of (A.10) as y−(Am 0 +a) ⊤ A−⊤Σ−1 0 A−1 y−(Am 0 +a) +C. Equality of the quadratic coefficients gives Σ−1 1 =A −⊤Σ−1 ...

    2021

  11. [11]

    17:Output:(f (k), g(k), π)

    15:untilmax i |ri| ∨max j |sj| ≤tolork=K 16:Recoverπvia (B.5). 17:Output:(f (k), g(k), π). Lety ij :=c ij −g j; then this becomes the scalar monotone equation MX j=1 bj(fi −y ij)+ =ε.(B.1) If yi(1) ≤ · · · ≤y i(M) denotes the sorted list and b(1), . . . , b(M) are the corresponding permuted weights, define prefix sums Bk := kX ℓ=1 b(ℓ), Sk := kX ℓ=1 b(ℓ)y...

    2021