B1258
Title: Minimax estimation of discontinuous optimal transport maps: The semi-discrete case
Authors: Aram-Alexandre Pooladian - New York University (United States) [presenting]
Vincent Divol - Universite Paris Dauphine PSL (France)
Jonathan Niles-Weed - New York University (United States)
Abstract: The problem of estimating the optimal transport map between two probability distributions, $P$ and $Q$ in $R^d$, based on i.i.d. samples is considered. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, the important special case is considered where the data distribution $Q$ is a discrete measure supported on a finite number of points in $R^d$. A computationally efficient estimator initially proposed is studied in previous work based on entropic optimal transport. It is shown in the semi-discrete setting that it converges at the minimax-optimal rate $n^{1/2}$, independent of dimension. Other standard map estimation techniques lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. These results are confirmed in numerical experiments, and experiments for other settings are provided, not covered by the theory, which indicates that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems.
