Optimal transport (OT) suffers from the curse of dimensionality. Therefore, OT can only be used in machine learning if it is substantially regularized. In this talk, I will present a new regularization of OT which leverages the regularity of the Brenier map. Instead of considering regularity as a property that can be proved under suitable assumptions, we consider regularity as a condition that must be enforced when estimating OT. From a statistical point of view, this defines new estimators of the OT map and 2-Wasserstein distance between arbitrary measures. From an algorithmic point of view, this leads to an infinite-dimensional optimization problem, which, when dealing with discrete measures, can be rewritten as a finite-dimensional separately-convex problem. I will finish by sharing some recent ideas on how to speed up the algorithms. The talk is based on some joint work with Marco Cuturi and Alexandre d'Aspremont.