Solving linear programs by using entropic penalization has recently attracted
new interest in the optimization community, since this strategy forms the basis
for the fastest-known algorithms for the optimal transport problem, with many
applications in modern large-scale machine learning. Crucial to these
applications has been an analysis of how quickly solutions to the penalized
program approach true optima to the original linear program. More than 20 years
ago, Cominetti and San Mart\'in showed that this convergence is exponentially
fast; however, their proof is asymptotic and does not give any indication of
how accurately the entropic program approximates the original program for any
particular choice of the penalization parameter. We close this long-standing
gap in the literature regarding entropic penalization by giving a new proof of
the exponential convergence, valid for any linear program. Our proof is
non-asymptotic, yields explicit constants, and has the virtue of being
extremely simple. We provide matching lower bounds and show that the entropic
approach does not lead to a near-linear time approximation scheme for the
linear assignment problem.

使用熵惩罚方法解决线性规划问题已成为优化界的新热点，这种方法不仅用于解决最优输运问题，并广泛应用于现代大规模机器学习中。本文通过提供一个新的证明来解决关于熵惩罚的长期问题，该证明具有指数收敛和相当的精确度，同时表明熵惩罚方法不适用于线性分配问题的近似解。

线性规划中熵惩罚的明确分析

An explicit analysis of the entropic penalty in linear programming

Optimal transport (OT) distances are finding evermore applications in machine
learning and computer vision, but their wide spread use in larger-scale
problems is impeded by their high computational cost. In this work we develop a
family of fast and practical stochastic algorithms for solving the optimal
transport problem with an entropic penalization. This work extends the recently
developed Greenkhorn algorithm, in the sense that, the Greenkhorn algorithm is
a limiting case of this family. We also provide a simple and general
convergence theorem for all algorithms in the class, with rates that match the
best known rates of Greenkorn and the Sinkhorn algorithm, and conclude with
numerical experiments that show under what regime of penalization the new
stochastic methods are faster than the aforementioned methods.

本论文研究基于熵罚函数的最优传输问题的随机算法，这些算法速度较快、实用，并且在数值实验中验证了它们相对于最优传输方法的优势。