  We consider the problem of estimating the optimal transport map between two
probability distributions, $P$ and $Q$ in $\mathbb R^d$, on the basis of i.i.d.
samples. 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,
we consider the important special case where the data distribution $Q$ is a
discrete measure supported on a finite number of points in $\mathbb R^d$. We
study a computationally efficient estimator initially proposed by Pooladian and
Niles-Weed (2021), based on entropic optimal transport, and show in the
semi-discrete setting that it converges at the minimax-optimal rate $n^{-1/2}$,
independent of dimension. Other standard map estimation techniques both lack
finite-sample guarantees in this setting and provably suffer from the curse of
dimensionality. We confirm these results in numerical experiments, and provide
experiments for other settings, not covered by our theory, which indicate that
the entropic estimator is a promising methodology for other discontinuous
transport map estimation problems.
