Abstract
In optimal transport, quadratic regularization is an alternative to entropic regularization when sparse couplings or small regularization parameters are desired. Here quadratic regularization means that transport couplings are penalized by the squared $L^2$ norm, or equivalently the $\chi^2$ divergence. While a number of computational approaches have been shown to work in practice, quadratic regularization is analytically less tractable than entropic, and we are not aware of a previous theoretical convergence rate analysis. We focus on the gradient descent algorithm for the dual transport problem in continuous and semi-discrete settings. This problem is convex but not strongly convex; its solutions are the potential functions that approximate the Kantorovich potentials of unregularized optimal transport. The gradient descent steps are straightforward to implement, and stable for small regularization parameter — in contrast to Sinkhorn's algorithm in the entropic setting. Our main result is that gradient descent converges linearly; that is, the $L^2$ distance between the iterates and the limiting potentials decreases exponentially fast. Our analysis centers on the linearization of the gradient descent operator at the optimum and uses functional-analytic arguments to bound its spectrum. These techniques seem to be novel in this area and are substantially different from the approaches familiar in entropic optimal transport.
Introduction
Optimal Transport (OT) has become a cornerstone of modern data science, utilized in diverse fields ranging from single-cell RNA sequence alignment to the training of generative adversarial networks (GANs). While the entropic regularization approach, typically solved via the Sinkhorn algorithm, is the current industry standard, it possesses inherent limitations. Specifically, entropic regularization tends to "blur" results by producing non-sparse transport plans and becomes numerically unstable when the regularization parameter is small.
Recent research by Alberto González-Sanz, Marcel Nutz, and Andrés Riveros Valdevenito establishes a rigorous theoretical foundation for a powerful alternative: Quadratically Regularized Optimal Transport (QOT). This approach penalizes the transport plan using the $L^2$ norm, offering a more numerically stable framework that produces sparser, sharper results than traditional entropic methods.
Bridging the Theoretical Gap
While practitioners have observed the empirical success of QOT, a formal convergence rate analysis has been missing. The dual problem for QOT is convex but not strongly convex, a property that usually complicates the proof of fast (linear) convergence. This paper addresses this gap by proving that gradient descent for the dual QOT problem converges linearly—meaning the error decreases exponentially fast to the optimal solution.
Methodology: A Functional-Analytic Approach
The authors analyze a gradient descent algorithm applied to the dual formulation of the QOT problem in both continuous and semi-discrete settings. The core of their proof involves:
- Linearization: Linearizing the gradient descent operator at the optimal potential functions.
- Spectral Bounding: Using functional-analytic arguments to bound the spectrum of the linearized operator. They demonstrate that the operator acts as a strict contraction, ensuring that each iteration reliably reduces the distance to the optimum.
- Stability: Unlike the exponential terms in Sinkhorn's algorithm that can lead to numerical overflow or underflow, the gradient for QOT remains "tame" and stable even as the regularization parameter $\epsilon$ approaches zero.
Key Insights and Numerical Stability
A defining feature of QOT is its ability to produce sparse couplings, mimicking the behavior of unregularized OT more closely than entropic methods. This sparsity is achieved because the quadratic penalty naturally creates "dead zones" where no transport occurs.
Furthermore, the research identifies a critical threshold for the step size ($\eta$). The theory dictates that if $\eta < \epsilon$, linear convergence is guaranteed. This requirement is not merely a theoretical safety margin but a sharp boundary; numerical experiments confirm that convergence fails when the step size significantly exceeds the regularization parameter.
Results and Validation
The primary theoretical contribution, Theorem 2.3, mathematically proves that the $L^2$ distance between the algorithm's iterates and the true solution decreases exponentially ($ \le \delta^n$).
To validate these findings, the authors conducted experiments on synthetic datasets, including:
- 1D Distributions: Transporting between Uniform distributions and between Uniform and Beta distributions.
- 2D Distributions: Transporting between 2D Uniform squares using discretized meshes.
Numerical results showed a characteristic "burn-in" period followed by a linear trajectory on a log-scale error plot, providing empirical confirmation of the proven linear convergence rates.
Conclusion and Future Directions
This work provides the first convergence rate analysis for quadratically regularized OT, justifying the use of gradient descent as a robust alternative to entropic methods. While the current proof requires at least one distribution to be continuous, future research may extend these results to purely discrete-to-discrete transport. Additionally, while the analysis focused on squared Euclidean distance, the authors suggest that these functional-analytic techniques could be adapted for other continuous cost functions and potentially stronger geometric results, such as a universal quadratic growth condition.
Summary updated