no. 11-12
Statistics
Entropic optimal transport is maximum-likelihood deconvolution
[Le transport optimal entropique correspond à l'estimateur du maximum de vraisemblance en déconvolution]

Présenté par : the Editorial Board

Rigollet, Philippe1 ; Weed, Jonathan1
1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA
Comptes Rendus. Mathématique, Tome 356 (2018) no. 11-12, pp. 1228-1235.

Cette note donne un interprétation statistique du transport optimal entropique : on montre que l'estimateur du maximum de vraisemblance en deconvolution gaussienne correspond à la projection de la loi empirique des données au sens de la distance définie par le transport optimal entropique. Ce résultat structurel donne une justification théorique, qui soutient l'adoption massive de ces outils par la communauté de l'apprentissage automatique.

We give a statistical interpretation of entropic optimal transport by showing that performing maximum-likelihood estimation for Gaussian deconvolution corresponds to calculating a projection with respect to the entropic optimal transport distance. This structural result gives theoretical support for the wide adoption of these tools in the machine learning community.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2018.10.010
Rigollet, Philippe 1 ; Weed, Jonathan 1

1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA 
@article{CRMATH_2018__356_11-12_1228_0,
     author = {Rigollet, Philippe and Weed, Jonathan},
     title = {Entropic optimal transport is maximum-likelihood deconvolution},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1228--1235},
     publisher = {Elsevier},
     volume = {356},
     number = {11-12},
     year = {2018},
     doi = {10.1016/j.crma.2018.10.010},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1016/j.crma.2018.10.010/}
}
TY  - JOUR
AU  - Rigollet, Philippe
AU  - Weed, Jonathan
TI  - Entropic optimal transport is maximum-likelihood deconvolution
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 1228
EP  - 1235
VL  - 356
IS  - 11-12
PB  - Elsevier
UR  - http://archive.numdam.org/articles/10.1016/j.crma.2018.10.010/
DO  - 10.1016/j.crma.2018.10.010
LA  - en
ID  - CRMATH_2018__356_11-12_1228_0
ER  - 
%0 Journal Article
%A Rigollet, Philippe
%A Weed, Jonathan
%T Entropic optimal transport is maximum-likelihood deconvolution
%J Comptes Rendus. Mathématique
%D 2018
%P 1228-1235
%V 356
%N 11-12
%I Elsevier
%U http://archive.numdam.org/articles/10.1016/j.crma.2018.10.010/
%R 10.1016/j.crma.2018.10.010
%G en
%F CRMATH_2018__356_11-12_1228_0
Rigollet, Philippe; Weed, Jonathan. Entropic optimal transport is maximum-likelihood deconvolution. Comptes Rendus. Mathématique, Tome 356 (2018) no. 11-12, pp. 1228-1235. doi : 10.1016/j.crma.2018.10.010. http://archive.numdam.org/articles/10.1016/j.crma.2018.10.010/

[1] Altschuler, J.; Weed, J.; Rigollet, P. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, 2017, 4–9 December 2017, Long Beach, CA, USA (Guyon, I.; von Luxburg, U.; Bengio, S.; Wallach, H.M.; Fergus, R.; Vishwanathan, S.V.N.; Garnett, R., eds.) (2017), pp. 1961-1971

[2] Arjovsky, M.; Chintala, S.; Bottou, L. Wasserstein GAN, 2017 (preprint) | arXiv

[3] Bassetti, F.; Bodini, A.; Regazzini, E. On minimum Kantorovich distance estimators, Stat. Probab. Lett., Volume 76 (2006) no. 12, pp. 1298-1302 (MR 2269358)

[4] Benamou, J.-D. Numerical resolution of an “unbalanced” mass transport problem, M2AN, Math. Model. Numer. Anal., Volume 37 (2003) no. 5, pp. 851-868 (MR 2020867)

[5] Bickel, P.J.; Doksum, K.A. Mathematical Statistics: Basic Ideas and Selected Topics, vol. 1, Prentice-Hall, 2006 (updated printing)

[6] Bonneel, N.; van de Panne, M.; Paris, S.; Heidrich, W. Displacement interpolation using lagrangian mass transport, ACM Trans. Graph., Volume 30 (2011) no. 6, p. 158:1-158:12

[7] Caillerie, C.; Chazal, F.; Dedecker, J.; Michel, B. Deconvolution for the Wasserstein metric and geometric inference, Electron. J. Stat., Volume 5 (2011), pp. 1394-1423 (MR 2851684)

[8] Carroll, R.J.; Hall, P. Optimal rates of convergence for deconvolving a density, J. Amer. Stat. Assoc., Volume 83 (1988) no. 404, pp. 1184-1186

[9] Carroll, R.J.; Ruppert, D.; Stefanski, L.A.; Crainiceanu, C.M. Measurement error in nonlinear models, A Modern Perspective, Monogr. Stat. Appl. Probab., vol. 105, Chapman & Hall/CRC, Boca Raton, FL, 2006

[10] Catoni, O. Statistical learning theory and stochastic optimization, July 8–25, 2001 (Lect. Notes Math.), Volume vol. 1851 (2004) MR 2163920 (2006d:62004)

[11] Chizat, L.; Peyré, G.; Schmitzer, B.; Vialard, F.-X. Scaling algorithms for unbalanced transport problems, 2016 (preprint) | arXiv

[12] Courty, N.; Flamary, R.; Tuia, D.; Rakotomamonjy, A. Optimal transport for domain adaptation, IEEE Trans. Pattern Anal. Mach. Intell., Volume 39 (2017) no. 9, pp. 1853-1865

[13] Cuturi, M. Sinkhorn distances: lightspeed computation of optimal transport, held December 5–8, 2013, Lake Tahoe, Nevada, United States (Burges, C.J.C.; Bottou, L.; Ghahramani, Z.; Weinberger, K.Q., eds.) (2013), pp. 2292-2300

[14] Dalalyan, A.; Tsybakov, A.B. Aggregation by exponential weighting, sharp pac-bayesian bounds and sparsity, Mach. Learn., Volume 72 (2008) no. 1, pp. 39-61

[15] Dalalyan, A.S.; Tsybakov, A.B. Mirror averaging with sparsity priors, Bernoulli, Volume 18 (2012) no. 3, pp. 914-944 (MR 2948907)

[16] Dalalyan, A.S.; Tsybakov, A.B. Sparse regression learning by aggregation and Langevin Monte-Carlo, J. Comput. Syst. Sci., Volume 78 (2012) no. 5, pp. 1423-1443 | arXiv

[17] Fan, J. On the estimation of quadratic functionals, Ann. Stat., Volume 19 (1991) no. 3, pp. 1273-1294 MR 1126325 (92j:62006)

[18] Forrow, A.; Hütter, J.-C.; Nitzan, M.; Schiebinger, G.; Rigollet, P.; Weed, J. Statistical optimal transport via factored couplings, 2018 | arXiv

[19] Frogner, C.; Zhang, C.; Mobahi, H.; Araya-Polo, M.; Poggio, T.A. Learning with a Wasserstein loss, December 7–12, 2015, Montreal, Quebec, Canada (Cortes, C.; Lawrence, N.D.; Lee, D.D.; Sugiyama, M.; Garnett, R., eds.) (2015), pp. 2053-2061

[20] Genevay, A.; Cuturi, M.; Peyré, G.; Bach, F.R. Stochastic optimization for large-scale optimal transport, December 5–10, 2016, Barcelona, Spain (Lee, D.D.; Sugiyama, M.; von Luxburg, U.; Guyon, I.; Garnett, R., eds.) (2016), pp. 3432-3440

[21] Genevay, A.; Peyré, G.; Cuturi, M. Learning generative models with sinkhorn divergences, 9–11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain (Storkey, A.J.; Pérez-Cruz, F., eds.) (Proceedings of Machine Learning Research), Volume vol. 84, PMLR (2018), pp. 1608-1617

[22] Giné, E.; Nickl, R. Mathematical Foundations of Infinite-Dimensional Statistical Models, Cambridge Ser. Statist. Probab. Math., vol. 40, Cambridge University Press, New York, 2016 (MR 3588285)

[23] Jitkrittum, W.; Szabó, Z.; Chwialkowski, K.P.; Gretton, A. Interpretable distribution features with maximum testing power, December 5–10, 2016, Barcelona, Spain (Lee, D.D.; Sugiyama, M.; von Luxburg, U.; Guyon, I.; Garnett, R., eds.) (2016), pp. 181-189

[24] Juditsky, A.; Rigollet, P.; Tsybakov, A. Learning by mirror averaging, Ann. Stat., Volume 36 (2008) no. 5, pp. 2183-2206 (MR MR2458184)

[25] Kearns, M.J.; Mansour, Y.; Ng, A.Y. An information-theoretic analysis of hard and soft assignment methods for clustering, Brown University, Providence, Rhode Island, USA, August 1–3, 1997 (Geiger, D.; Shenoy, P.P., eds.), Morgan Kaufmann (1997), pp. 282-293

[26] Léonard, C. A survey of the Schrödinger problem and some of its connections with optimal transport, Discrete Contin. Dyn. Syst., Volume 34 (2014) no. 4, pp. 1533-1574 (MR 3121631)

[27] Liero, M.; Mielke, A.; Savaré, G. Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures, Invent. Math., Volume 211 (2018) no. 3, pp. 969-1117 (MR 3763404)

[28] Lindsay, B.G. Mixture models: theory, geometry and applications, Regional Conference Series in Probability and Statistics, vol. 5, Institute of Mathematical Statistics and American Statistical Association, Haywood CA and Alexandria VA, 1995

[29] Montavon, G.; Müller, K.-R.; Cuturi, M. Wasserstein training of restricted boltzmann machines, December 5–10, 2016, Barcelona, Spain (Lee, D.D.; Sugiyama, M.; von Luxburg, U.; Guyon, I.; Garnett, R., eds.) (2016), pp. 3711-3719

[30] Mueller, J.; Jaakkola, T.S. Principal differences analysis: interpretable characterization of differences between distributions, December 7–12, 2015, Montreal, Quebec, Canada (Cortes, C.; Lawrence, N.D.; Lee, D.D.; Sugiyama, M.; Garnett, R., eds.) (2015), pp. 1702-1710

[31] Peyré, G.; Cuturi, M. Computational Optimal Transport, 2017 (Tech. report)

[32] Rigollet, P. Kullback–Leibler aggregation and misspecified generalized linear models, Ann. Stat., Volume 40 (2012) no. 2, pp. 639-665 (MR 2933661)

[33] Rigollet, P.; Tsybakov, A. Exponential screening and optimal rates of sparse estimation, Ann. Stat., Volume 39 (2011) no. 2, pp. 731-771 (MR 2816337)

[34] Rigollet, P.; Tsybakov, A. Sparse estimation by exponential weighting, Stat. Sci., Volume 27 (2012) no. 4, pp. 558-575

[35] Rigollet, P.; Weed, J. Uncoupled isotonic regression via minimum Wasserstein deconvolution, 2018 | arXiv

[36] Rolet, A.; Cuturi, M.; Peyré, G. Fast dictionary learning with a smoothed wasserstein loss, AISTATS 2016, Cadiz, Spain, May 9–11, 2016 (Gretton, A.; Robert, C.C., eds.) (J. Mach. Learn. Res. Workshop Conf. Proc.), Volume vol. 51, JMLR.org (2016), pp. 630-638

[37] Rubner, Y.; Tomasi, C.; Guibas, L.J. The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vis., Volume 40 (2000) no. 2, pp. 99-121

[38] Santambrogio, F. Optimal Transport for Applied Mathematicians, Birkäuser, NY, 2015

[39] G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V. Subramanian, A. Solomon, S. Liu, S. Lin, P. Berube, L. Lee, et al., Reconstruction of developmental landscapes by optimal-transport analysis of single-cell gene expression sheds light on cellular reprogramming, bioRxiv (2017) 191056.

[40] Schrödinger, E. Sur la théorie relativiste de l'électron et l'interprétation de la mécanique quantique, Ann. Inst. Henri Poincaré, Volume 2 (1932) no. 4, pp. 269-310 (MR 1508000)

[41] Solomon, J.; De Goes, F.; Peyré, G.; Cuturi, M.; Butscher, A.; Nguyen, A.; Du, T.; Guibas, L. Convolutional wasserstein distances: efficient optimal transportation on geometric domains, ACM Trans. Graph., Volume 34 (2015) no. 4, p. 66

[42] Wilson, A.G. The use of entropy maximising models, in the theory of trip distribution, mode split and route split, J. Transp. Econ. Policy, Volume 3 (1969) no. 1, pp. 108-126

Cité par Sources :