SGD with decreasing entropic regularization on semi-discrete OT is efficient! In this work, (i) we prove an O(1/t) lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation, and (ii) we propose a Stochastic Gradient Descent (SGD) algorithm with adaptive entropic regularization and averaging acceleration. Moreover, while being as computationally and memory efficient as vanilla SGD, our algorithm achieves the unusual fast rates of our theory in numerical experiments. Click on the title to read the abstract.