Statistical analysis of the optimal transport problem

Abstract

Optimal transportation is a resource allocation problem present in fields such as economics, finance, physics or artificial intelligence. From a probabilistic point of view, the optimal transport cost endows the space of probability measures with a metric topology. In particular, this topology is equivalent to the weak topology of probability measures together with the convergence of moments. This makes the transport cost an appropriate tool for measuring discrepancies between distributions. On the other hand, the solution of the transport problem is known as optimal plan. That is, an unambiguous way to relate two distributions following an optimality criterion. This optimal plan, when deterministic, is called a transport map.

However, in many cases the probability distribution is a theoretical, unattainable entity. It is only visible to the practitioner through its empirical version, i.e. a finite data set of size n. This work examines the asymptotic behaviour of the transport cost in its empirical version. In other words, we study the limits of the empirical cost and plans when the data grows to infinity. It is well-known that the empirical transport cost converges to the population one. Moreover, for continuous measures it does so at a rate that decreases with dimension. In this thesis we prove the consistency of the transport map using topology of set-valued maps. This leads, indirectly, to being able to state that the rate at which the fluctuations–difference between the expected empirical cost and the empirical cost itself–approximate zero is the parametric one, irrespective of the dimension. Moreover, these fluctuations multiplied by the parametric rate tend toward a Gaussian random variable. In economics the transportation problem appears in numerous occasions in its semi-discrete version, i.e. one of the probability distributions is discrete. In this case, we show that the rate at which the empirical transport cost converges to the population one does not depend on the dimension.

We also show that the well-known entropy regularization (or Sinkhorn regularization), apart from simplifying the computation of the transport problem by giving it a differentiable structure, has highly satisfactory statistical properties. In particular, its bias and the divergence–that the regularization defines–converge with speed greater than the parametric one; the empirical regularized plans converge to the population ones with paramtetric rate moreover, tending to a Gaussian process.

The transport map endows a probability measure P with an order with respect to a given reference. This property leads to the successful definition of M.Hallin’s multivariate distribution function by choosing as a reference measure the spherical uniform. This thesis provides sufficient conditions under which this function defines a homeomorphism between the support of the probability measure P and the unitary ball–i.e. to support of the spherical uniform. Finally, we provide a conditional version of the multivariate distribution function, with applications to quantile regression.

El transporte óptimo es un problema de asignación de recursos presente en ámbitos como economía, finanzas, física o inteligencia artificial. Desde un punto de vista probabilístico, el coste de transporte óptimo dota al espacio de medidas de probabilidad de una topología métrica. En particular, esta topología es equivalente a la topología débil de medidas junto con la convergencia de los momentos. Esto hace el coste del transporte una herramienta apropiada para la medición de discrepancias entre distribuciones. Por otro lado, la solución del problema de transporte es conocido como plan óptimo. Es decir, una manera inequívoca de relacionar dos distribuciones siguiendo un criterio de optimalidad. Este plan óptimo, cuando es determinista, es llamado aplicación de transporte.

Sin embargo, en muchas ocasiones la distribution de probabilidad es un ente teórico, inalcanzable. Solo es visible para el practicante a través de su versión empírica, es decir, de un conjunto de datos de tamaño finito n. Este trabajo examina el comportamiento asintótico del coste de transporte en su versión empírica. En otras palabras, se estudian los límites del coste y planes de transporte empíricos cuando los datos tienden a infinito. Es conocido, en varios trabajos precedentes, que el coste de transporte empírico converge hacia el poblacional. Es más, para medidas continuas lo hace a una velocidad que decrece con la dimensión. En esta tesis se demuestra la consistencia de la aplicación de transporte utilizando topología de aplicaciones que toman valores en un espacio de conjuntos. Esto lleva, de manera indirecta, a poder afirmar que la velocidad a las fluctuaciones –diferencia entre esperanza empírica del coste y el propio coste empírico– se aproxima a cero es la paramétrica Además, estas fluctuaciones tienden hacia una variable gausiana. En aplicaciones económicas el problema de transporte aparece en numerosas ocasiones en su versión semidiscreta, i.e. una de las distribuciones de probabilidad es discreta. En este caso, mostramos que la velocidad a la que el coste de transporte empírico converge hacia el poblacional no depende de la dimensión.

Demostramos también que la conocida regularización por la entropía (o regularización de Sinkhorn), aparte de simplificar la computación del problema de transporte dotándole de una estructura diferenciable, tiene propiedades estadísticas altamente satisfactorias. En particular, su sesgo y la divergencia que la regularización define convergen con velocidad mayor a la paramétrica; los planes regularizados empíricos convergen hacia los poblacionales, con un error gausiano.

La transformación de transporte otorga a una medida de probabilidad P un orden con respecto a una referencia dada. Esta propiedad permite la exitosa definición de la función de distribución multivariada de M.Hallin eligiendo como medida de referencia la uniforme esférica. Esta tesis proporciona condiciones suficientes bajo las cuales esta función define un homeomorfismo entre el soporte de la medida de probabilidad P y la bola unitaria, es decir, el soporte de la uniforme esférica. Finalmente, proporcionamos una versión condicional de la función de distribución multivariada, con aplicaciones a la regresión cuantílica.