Thumbnail - No thumbnail

A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

Vacher, Jonathan; Muzellec, Boris; Rudi, Alessandro; Bach, Francis; Vialard, François-Xavier (2021), A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation, in Mikhail Belkin, Samory Kpotufe, Proceedings of Machine Learning Research, vol. 134, COLT 2021 - 34th Annual Conference on Learning Theory, Journal of Machine Learning Research, p. 4143-4173

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-03454237/document
Date
2021
Conference title
COLT 2021 - 34th Annual Conference on Learning Theory
Conference date
2021-08
Conference city
Boulder
Conference country
United States
Book title
Proceedings of Machine Learning Research, vol. 134, COLT 2021 - 34th Annual Conference on Learning Theory
Book author
Mikhail Belkin, Samory Kpotufe
Publisher
Journal of Machine Learning Research
Pages
4143-4173
Metadata
Show full item record
Author(s)
Vacher, Jonathan
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Laboratoire des systèmes perceptifs [LSP]
Muzellec, Boris
Statistical Machine Learning and Parsimony [SIERRA]
Rudi, Alessandro cc
Statistical Machine Learning and Parsimony [SIERRA]
Bach, Francis
Statistical Machine Learning and Parsimony [SIERRA]
Vialard, François-Xavier
Laboratoire d'Informatique Gaspard-Monge [LIGM]
Abstract (EN)
It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexity of these recently proposed methods still degrade exponentially with the dimension. In this paper, thanks to an infinitedimensional sum-of-squares representation, we derive a statistical estimator of smooth optimal transport which achieves a precision ε fromÕ(ε −2) independent and identically distributed samples from the distributions, for a computational cost ofÕ(ε −4) when the smoothness increases, hence yielding dimension-free statistical and computational rates, with potentially exponentially dimension-dependent constants.