Annealed quantitative estimates for the quadratic 2D-discrete random matching problem

1. Problem Statement

The paper addresses the quadratic random matching problem on a closed, compact 2-dimensional Riemannian manifold $M$ (without boundary).

• Setup: Two sequences of random points, $\{X_i\}_{i=1}^n$ and $\{Y_j\}_{j=1}^m$, are sampled from $M$. The goal is to minimize the total squared Riemannian distance between matched pairs.
• Mathematical Formulation: This is equivalent to finding the quadratic Wasserstein distance $W_2^2(\mu_n, \nu_m)$ between the empirical measures $\mu_n = \frac{1}{n}\sum \delta_{X_i}$ and $\nu_m = \frac{1}{m}\sum \delta_{Y_j}$.
• Context: While the asymptotic scaling of the cost is well-understood for independent and identically distributed (i.i.d.) uniform samples (scaling as $\frac{\log n}{n}$ in 2D), this work focuses on quantitative estimates for the transport map itself under more general conditions:
  1. Non-uniform densities: Points are distributed according to a density $\rho$ (bounded and strictly positive).
  2. Correlations: Points are not necessarily i.i.d.; they may exhibit correlations (e.g., via $\alpha$-mixing or Markov chains).
  3. Unequal sample sizes: $n$ and $m$ are asymptotically equivalent but not necessarily equal.

2. Methodology

The authors employ a linearization ansatz combined with quantitative stability analysis and probabilistic concentration inequalities.

A. Linearization of the Monge-Ampère Equation

The core idea, originating from Caracciolo et al. [16] and rigorously justified by Ambrosio et al. [6], is to approximate the optimal transport map $T^n$ by a perturbation of the identity map:
$$T^n \approx \text{Id} + \nabla h_n$$
where $h_n$ is a potential function. Formally, the Monge-Ampère equation $(\nu_n \circ T^n) \det(\nabla T^n) = \mu_n$ is linearized to yield a Poisson-type equation:
$$\nabla \cdot (\rho \nabla h_n) = \mu_n - \nu_n$$
However, the source term $\mu_n - \nu_n$ is too rough (a sum of Dirac masses) for $h_n$ to belong to $H^1$ directly.

B. Regularization Strategy

To handle the roughness, the authors introduce a heat-semigroup regularization at time $t \sim \frac{\log^\kappa n}{n}$.

1. Smoothed Measures: Define $\mu_{n,t} = P_t \mu_n$ and $\nu_{m,t} = P_t \nu_m$, where $P_t$ is the heat semigroup.
2. Regularized PDE: Solve for $h_{n,t}$ in the equation:
   $$\nabla \cdot (\rho \nabla h_{n,t}) = \mu_{n,t} - \nu_{m,t}$$
3. Approximation Plan: Construct the candidate transport plan $\gamma_{n,t} = (\text{Id}, \exp(\nabla h_{n,t}))_\# \mu_{n,t}$.

C. Error Decomposition

The proof strategy splits the error between the optimal plan $\pi$ and the approximated plan $\gamma_{n,t}$ into two main components:

1. Regularization Error: The distance between the smoothed plan $\gamma_{n,t}$ and the plan derived from the unsmoothed (but regularized density) solution. This is controlled using energy estimates and Meyers' estimates for elliptic operators with rough coefficients.
2. Stability Error: The distance between the smoothed plan and the true optimal plan. This relies on the quantitative stability of transport maps (Theorem 2.1), which states that if target measures are close in $W_2$, the transport maps are close in $L^2$.

D. Handling Correlations

A significant technical hurdle is dealing with non-i.i.d. samples. The authors assume:

• $\alpha$-mixing: Correlations decay at a stretched exponential rate: $\alpha_\ell \leq a \exp(-b \ell^\eta)$.
• $\beta$-mixing: Controlled via the sum of mixing coefficients.
• Markov Chains: The results extend to sub-geometrically ergodic Markov chains satisfying a drift condition.
  The authors utilize concentration inequalities (Proposition A.1) adapted for these correlated sequences to bound the fluctuations of the empirical measures and the solutions to the PDEs.

3. Key Contributions and Results

Main Theorems

The paper establishes annealed quantitative estimates (bounds in expectation) for the convergence of the transport plan.

• Theorem 1.2 (Full Matching): For two point clouds satisfying the mixing assumptions, the optimal transport plan $\pi$ between $\mu_n$ and $\nu_m$ is quantitatively approximated by $\gamma_{n,t}$.
  $$\inf_{\pi} W_2^2(\pi, \gamma_{n,t}) \leq C_n \frac{\log n}{n} \sqrt{\frac{\log \log n}{\log n}}$$
  where $C_n$ is a random variable with bounded moments. If the mixing decay is sufficiently fast ($\eta > 2$), the bound improves, and the assumption on the sum of $\beta$-mixing coefficients can be dropped.

• Theorem 1.3 (Semi-discrete Matching): For the matching between the continuous measure $\rho dm$ and the empirical measure $\mu_n$, the optimal map $T^n$ is approximated by $\exp(\nabla f_{n,t})$ in $L^2$ with the same convergence rates.

Technical Innovations

1. Extension to Correlated Data: This is the first work to rigorously justify the linearization ansatz for correlated random points (beyond i.i.d.) in the context of optimal transport.
2. Sub-geometric Ergodicity: The results are extended to a class of discrete-time Markov chains that are not geometrically ergodic but satisfy a sub-geometric drift condition.
3. Refined Regularization: The authors optimize the regularization parameters (time $t$ and density smoothing $\delta$) to balance the trade-off between the roughness of the source term and the stability of the transport map, achieving rates that match the known optimal scaling for the cost.
4. Fourier Analysis & Concentration: The proof heavily relies on Fourier analysis of the heat kernel and novel concentration inequalities for correlated sums to control the $L^q$ norms of the gradient of the potential $h_{n,t}$.

4. Significance

• Rigorous Justification of Physics Heuristics: The paper provides a rigorous mathematical foundation for the "linearization ansatz" widely used in statistical physics (e.g., by Caracciolo, Lucibello, Parisi, Sicuro) to derive asymptotic costs. It moves beyond just the cost to the structure of the transport map.
• Robustness to Dependencies: By handling correlated data and Markov chains, the results are applicable to a much broader class of physical and economic systems where independence is a poor assumption (e.g., interacting particle systems, time-series data).
• Quantitative Precision: The paper provides explicit rates of convergence with precise stochastic integrability (e.g., exponential moments for the error constants), which is crucial for applications requiring high-probability guarantees.
• Open Problems: The authors discuss the sharpness of these rates (suggesting a second-order linearization might be needed for optimality) and potential extensions to $p$-costs, Ginibre ensembles, and Coulomb gases.

Conclusion

Clozeau and Mattesini successfully generalize the quantitative theory of random matching in 2D. They demonstrate that the linearized Monge-Ampère equation, when properly regularized, provides a highly accurate approximation of the optimal transport plan even in the presence of complex correlations and non-uniform densities, with convergence rates matching the theoretical limits of the matching cost.