  Optimal Transport (OT) based distances are powerful tools for machine
learning to compare probability measures and manipulate them using OT maps. In
this field, a setting of interest is semi-discrete OT, where the source measure
$\mu$ is continuous, while the target $\nu$ is discrete. Recent works have
shown that the minimax rate for the OT map is $\mathcal{O}(t^{-1/2})$ when
using $t$ i.i.d. subsamples from each measure (two-sample setting). An open
question is whether a better convergence rate can be achieved when the full
information of the discrete measure $\nu$ is known (one-sample setting). In
this work, we answer positively to this question by (i) proving an
$\mathcal{O}(t^{-1})$ lower bound rate for the OT map, using the similarity
between Laguerre cells estimation and density support estimation, and (ii)
proposing a Stochastic Gradient Descent (SGD) algorithm with adaptive entropic
regularization and averaging acceleration. To nearly achieve the desired fast
rate, characteristic of non-regular parametric problems, we design an entropic
regularization scheme decreasing with the number of samples. Another key step
in our algorithm consists of using a projection step that permits to leverage
the local strong convexity of the regularized OT problem. Our convergence
analysis integrates online convex optimization and stochastic gradient
techniques, complemented by the specificities of the OT semi-dual. Moreover,
while being as computationally and memory efficient as vanilla SGD, our
algorithm achieves the unusual fast rates of our theory in numerical
experiments.
