Linear Convergence of Gradient Descent for Quadratically Regularized Optimal Transport
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914579768934400 |
|---|---|
| author | González-Sanz, Alberto Nutz, Marcel Valdevenito, Andrés Riveros |
| author_facet | González-Sanz, Alberto Nutz, Marcel Valdevenito, Andrés Riveros |
| contents | In optimal transport, quadratic regularization is an alternative to entropic regularization when sparse couplings or small regularization parameters are desired. Quadratic regularization penalizes transport couplings by the squared $L^2$ norm of their density, or equivalently by the $χ^2$ divergence. While a number of computational approaches have been shown to work in practice, the dual problem is not strongly convex and theoretical convergence results are scarce. We focus on the dual gradient descent algorithm in a continuous setting and establish linear convergence in $L^2$, that is, the $L^2$ distance between the iterates and the limiting potentials decreases exponentially fast. The proof is based on a spectral analysis of the linearized gradient descent operator at the optimum. We show that this operator is a strict contraction and that the nonlinear iteration inherits this property after a burn-in period. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08547 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Convergence of Gradient Descent for Quadratically Regularized Optimal Transport González-Sanz, Alberto Nutz, Marcel Valdevenito, Andrés Riveros Optimization and Control Analysis of PDEs Functional Analysis Probability 49N10, 49N05, 90C25 In optimal transport, quadratic regularization is an alternative to entropic regularization when sparse couplings or small regularization parameters are desired. Quadratic regularization penalizes transport couplings by the squared $L^2$ norm of their density, or equivalently by the $χ^2$ divergence. While a number of computational approaches have been shown to work in practice, the dual problem is not strongly convex and theoretical convergence results are scarce. We focus on the dual gradient descent algorithm in a continuous setting and establish linear convergence in $L^2$, that is, the $L^2$ distance between the iterates and the limiting potentials decreases exponentially fast. The proof is based on a spectral analysis of the linearized gradient descent operator at the optimum. We show that this operator is a strict contraction and that the nonlinear iteration inherits this property after a burn-in period. |
| title | Linear Convergence of Gradient Descent for Quadratically Regularized Optimal Transport |
| topic | Optimization and Control Analysis of PDEs Functional Analysis Probability 49N10, 49N05, 90C25 |
| url | https://arxiv.org/abs/2509.08547 |