Feuilleter
no. 3
Subadditivity and optimal matching of unbounded samples
[Sous-additivité et couplage optimal d’échantillons non bornés]
Emanuele Caglioti1 ; Michael Goldman2 ; Francesca Pieroni1 ; Dario Trevisan3
1Sapienza University of Rome, Department of Mathematics, Piazzale Aldo Moro, 5, 00185, Rome, Italy
2École polytechnique, Institut Polytechnique de Paris, CMAP, CNRS, 91120 Palaiseau, France
3University of Pisa, Department of Mathematics, Largo Bruno Pontecorvo, 5, 56127, Pisa, Italy
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 35 (2026) no. 3, pp. 697-742

We obtain new bounds for the optimal matching cost for empirical measures with unbounded support. For a large class of radially symmetric and rapidly decaying probability laws, we prove for the first time the asymptotic rate of convergence for the whole range of power exponents $p$ and dimensions $d$. Moreover we identify the exact prefactor when $p\le d$. We cover in particular the Gaussian case, going far beyond the currently known bounds. Our proof technique is based on approximate sub- and super-additivity bounds along a geometric decomposition adapted to some features of the density, such as its radial symmetry and its decay at infinity.

Nous obtenons de nouvelles bornes pour le coût d’appariement optimal de certaines mesures empiriques à support non borné. Pour une large classe de lois de probabilité à symétrie radiale et à décroissance rapide, nous établissons pour la première fois le taux asymptotique de convergence pour toute la gamme des exposants de puissance $p$ et des dimensions $d$. De plus, nous identifions le facteur multiplicatif exact lorsque $p\le d$. Nous couvrons en particulier le cas gaussien, en allant bien au-delà des bornes actuellement connues. Notre technique de preuve repose sur des bornes d’additivité approchée inférieure et supérieure, fondées sur une décomposition géométrique adaptée à certaines propriétés de la densité, telles que sa symétrie radiale et sa décroissance à l’infini.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/afst.1861
Classification : 60D05, 90C05, 39B62, 60F25, 49Q22
Keywords: bipartite matching problem, optimal transport, geometric probability
Mots-clés : problème du couplage biparti, transport optimal, probabilité géométrique

Emanuele Caglioti  1   ; Michael Goldman  2   ; Francesca Pieroni  1   ; Dario Trevisan  3

1 Sapienza University of Rome, Department of Mathematics, Piazzale Aldo Moro, 5, 00185, Rome, Italy
2 École polytechnique, Institut Polytechnique de Paris, CMAP, CNRS, 91120 Palaiseau, France
3 University of Pisa, Department of Mathematics, Largo Bruno Pontecorvo, 5, 56127, Pisa, Italy
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
Emanuele Caglioti; Michael Goldman; Francesca Pieroni; Dario Trevisan. Subadditivity and optimal matching of unbounded samples. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 35 (2026) no. 3, pp. 697-742. doi: 10.5802/afst.1861
@article{AFST_2026_6_35_3_697_0,
     author = {Emanuele Caglioti and Michael Goldman and Francesca Pieroni and Dario Trevisan},
     title = {Subadditivity and optimal matching of unbounded samples},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {697--742},
     year = {2026},
     publisher = {Universit\'e de Toulouse, Toulouse},
     volume = {Ser. 6, 35},
     number = {3},
     doi = {10.5802/afst.1861},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1861/}
}
TY  - JOUR
AU  - Emanuele Caglioti
AU  - Michael Goldman
AU  - Francesca Pieroni
AU  - Dario Trevisan
TI  - Subadditivity and optimal matching of unbounded samples
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2026
SP  - 697
EP  - 742
VL  - 35
IS  - 3
PB  - Université de Toulouse, Toulouse
UR  - https://afst.centre-mersenne.org/articles/10.5802/afst.1861/
DO  - 10.5802/afst.1861
LA  - en
ID  - AFST_2026_6_35_3_697_0
ER  - 
%0 Journal Article
%A Emanuele Caglioti
%A Michael Goldman
%A Francesca Pieroni
%A Dario Trevisan
%T Subadditivity and optimal matching of unbounded samples
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2026
%P 697-742
%V 35
%N 3
%I Université de Toulouse, Toulouse
%U https://afst.centre-mersenne.org/articles/10.5802/afst.1861/
%R 10.5802/afst.1861
%G en
%F AFST_2026_6_35_3_697_0

[1] Miklós Ajtai; János Komlós; Gábor Tusnády On optimal matchings, Combinatorica, Volume 4 (1984), pp. 259-264 | DOI | Zbl | MR

[2] Luigi Ambrosio; Michael Goldman; Dario Trevisan On the quadratic random matching problem in two-dimensional domains, Electron. J. Probab., Volume 27 (2022), 54, 35 pages | DOI | Zbl | MR

[3] Luigi Ambrosio; Federico Stra; Dario Trevisan A PDE approach to a 2-dimensional matching problem, Probab. Theory Relat. Fields, Volume 173 (2019) no. 1-2, pp. 433-477 | DOI | Zbl | MR

[4] Luigi Ambrosio; Federico Vitillaro; Dario Trevisan Sharp PDE estimates for random two-dimensional bipartite matching with power cost function (2024) | arXiv | Zbl

[5] Franck Barthe; Charles Bordenave Combinatorial optimization over two random point sets, Séminaire de probabilités XLV, Springer, 2013, pp. 483-535 | DOI | Zbl

[6] Dario Benedetto; Emanuele Caglioti Euclidean random matching in 2D for non-constant densities, J. Stat. Phys., Volume 181 (2020) no. 3, pp. 854-869 | DOI | Zbl | MR

[7] Sergey G. Bobkov Isoperimetric and analytic inequalities for log-concave probability measures, Ann. Probab., Volume 27 (1999) no. 4, pp. 1903-1921 | DOI | Zbl | MR

[8] Sergey G. Bobkov; Michel Ledoux Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution, Probab. Theory Relat. Fields, Volume 107 (1997) no. 3, pp. 383-400 | DOI | Zbl | MR

[9] Sergey G. Bobkov; Michel Ledoux One-dimensional empirical measures, order statistics, and Kantorovich transport distances, Memoirs of the American Mathematical Society, 1259, American Mathematical Society, 2019 | DOI | Zbl

[10] Emanuele Caglioti; Francesca Pieroni Random Matching in 2D with Exponent 2 for Gaussian Densities, J. Stat. Phys., Volume 191 (2024) no. 5, 62, 34 pages | DOI | Zbl | MR

[11] Sergio Caracciolo; Carlo Lucibello; Giorgio Parisi; Gabriel Sicuro Scaling hypothesis for the Euclidean bipartite matching problem, Phys. Rev. E, Volume 90 (2014) no. 1, 012118, 9 pages | DOI

[12] Steffen Dereich; Michael Scheutzow; Reik Schottstedt Constructive quantization: approximation by empirical measures, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 49 (2013) no. 4, pp. 1183-1203 | DOI | Zbl | Numdam | MR

[13] Alessio Figalli; Nicola Gigli A new transportation distance between non-negative measures, with applications to gradients flows with Dirichlet boundary conditions, J. Math. Pures Appl. (9), Volume 94 (2010) no. 2, pp. 107-130 | DOI | Zbl | MR

[14] Nicolas Fournier; Arnaud Guillin On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Relat. Fields, Volume 162 (2015) no. 3-4, pp. 707-738 | DOI | Zbl | MR

[15] Michael Goldman; Martin Huesmann; Dario Trevisan Asymptotics for Random Quadratic Transportation Costs (2025) | arXiv | Zbl

[16] Michael Goldman; Dario Trevisan Convergence of asymptotic costs for random Euclidean matching problems, Probab. Math. Phys., Volume 2 (2021) no. 2, pp. 341-362 | DOI | Zbl | MR

[17] Michael Goldman; Dario Trevisan Optimal transport methods for combinatorial optimization over two random point sets, Probab. Theory Relat. Fields, Volume 188 (2024) no. 3-4, pp. 1315-1384 | DOI | Zbl | MR

[18] Martin Huesmann; Francesco Mattesini; Felix Otto There is no stationary cyclically monotone Poisson matching in 2d, Probab. Theory Relat. Fields, Volume 187 (2023) no. 3-4, pp. 629-656 | DOI | Zbl | MR

[19] Michel Ledoux On optimal matching of Gaussian samples, Zap. Nauchn. Semin. (POMI), Volume 457 (2017) no. 25, pp. 226-264 | Zbl

[20] Michel Ledoux; Jie-Xiang Zhu On optimal matching of Gaussian samples III, Probab. Math. Stat., Volume 41 (2021) no. 2, pp. 237-265 | DOI | Zbl | MR

[21] Mauro Mariani; Dario Trevisan Wasserstein Asymptotics for Brownian Motion on the Flat Torus and Brownian Interlacements (2023) | arXiv | Zbl

[22] Rémi Peyre Comparison between ${W}_2$ distance and $\dot{H}^{-1}$ norm, and localization of Wasserstein distance, ESAIM, Control Optim. Calc. Var., Volume 24 (2018) no. 4, pp. 1489-1501 | DOI | Zbl | MR

[23] Michel Talagrand Scaling and non-standard matching theorems, Comptes Rendus. Mathématique, Volume 356 (2018) no. 6, pp. 692-695 | DOI | Zbl | Numdam

[24] Dario Trevisan; Michael Goldman On the concave one-dimensional random assignment problem and Young integration theory, Ann. Sc. Norm. Super. Pisa, Cl. Sci. (5), Volume 27 (2026) no. 1, pp. 589-612 | DOI | Zbl | MR

[25] Joseph E. Yukich Probability theory of classical Euclidean optimization problems, Lecture Notes in Mathematics, 1675, Springer, 2006 (eBook) | DOI | Zbl

Cité par Sources :