Quantitative Convergence of Quadratically Regularized Linear Programs

作     者：González-Sanz, Alberto Nutz, Marcel 

作者机构：Department of Statistics Columbia University NY United States Departments of Statistics and Mathematics Columbia University NY United States 

出 版 物：《Applied Mathematics and Optimization》 (Appl Math Optim)

年 卷 期：2025年第91卷第3期

页      面：1-18页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：M. Nutz was partially supported by NSF Grants DMS-1812661  DMS-2106056  DMS-2407074.The authors thank Roberto Cominetti  Andr\u00E9s Riveros Valdevenito and two anonymous referees for helpful comments. M. Nutz\u2019 research was supported by NSF Grants DMS-1812661  DMS-2106056  DMS-2407074 

主　　题：Linear programming 

摘      要：Linear programs with quadratic (ridge) regularization are of recent interest in optimal transport: unlike entropic regularization, the squared-norm penalty gives rise to sparse approximations of optimal transport couplings. More broadly, quadratic regularization is used in overparametrized learning problems to single out a particular solution. 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. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.