Quadratically Regularized Optimal Transport

Entropic optimal transport—the optimal transport problem regularized by KL divergence—is highly successful in statistical applications. Thanks to the smoothness of the entropic coupling, its sample complexity avoids the curse of dimensionality, and the strong concavity of the dual problem enables fast computation. The flip side is overspreading: the entropic coupling always has full support, whereas the unregularized coupling that it approximates is usually sparse, often even given by a map. Quadratic regularization is known to allow for sparse approximations but is often thought to suffer from the curse of dimensionality, as the couplings have limited differentiability and the dual is not strongly concave. We refute this conventional wisdom and show that the key empirical quantities converge at the parametric rate. Moreover, we describe the geometry of the dual problem and show that several natural algorithms converge linearly. (Based on joint work with Alberto Gonzalez-Sanz, Eustasio del Barrio, Stephan Eckstein, and Andres Riveros Valdevenito.)