Quantitative Convergence of Quadratically Regularized Linear Programs

Understand

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.