Quantitative Convergence of Quadratically Regularized Linear Programs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910915854598144 |
|---|---|
| author | González-Sanz, Alberto Nutz, Marcel |
| author_facet | González-Sanz, Alberto Nutz, Marcel |
| contents | Linear programs with quadratic regularization are attracting renewed interest due to their applications in optimal transport: unlike entropic regularization, the squared-norm penalty gives rise to sparse approximations of optimal transport couplings. It is well known that the solution of a quadratically regularized linear program over any polytope converges stationarily to the minimal-norm solution of the linear program when the regularization parameter tends to zero. However, that result is merely qualitative. Our main result quantifies the convergence by specifying the exact threshold for the regularization parameter, after which the regularized solution also solves the linear program. Moreover, we bound the suboptimality of the regularized solution before the threshold. These results are complemented by a convergence rate for the regime of large regularization. We apply our general results to the setting of optimal transport, where we shed light on how the threshold and suboptimality depend on the number of data points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantitative Convergence of Quadratically Regularized Linear Programs González-Sanz, Alberto Nutz, Marcel Optimization and Control Analysis of PDEs Probability 49N10, 49N05, 90C25 Linear programs with quadratic regularization are attracting renewed interest due to their applications in optimal transport: unlike entropic regularization, the squared-norm penalty gives rise to sparse approximations of optimal transport couplings. It is well known that the solution of a quadratically regularized linear program over any polytope converges stationarily to the minimal-norm solution of the linear program when the regularization parameter tends to zero. However, that result is merely qualitative. Our main result quantifies the convergence by specifying the exact threshold for the regularization parameter, after which the regularized solution also solves the linear program. Moreover, we bound the suboptimality of the regularized solution before the threshold. These results are complemented by a convergence rate for the regime of large regularization. We apply our general results to the setting of optimal transport, where we shed light on how the threshold and suboptimality depend on the number of data points. |
| title | Quantitative Convergence of Quadratically Regularized Linear Programs |
| topic | Optimization and Control Analysis of PDEs Probability 49N10, 49N05, 90C25 |
| url | https://arxiv.org/abs/2408.04088 |