# An explicit analysis of the entropic penalty in linear programming

arXiv: https://arxiv.org/abs/1806.01879 · HTML: https://mlsanity.com/paper/1806.01879/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

## Built on by (most cited first, 24 of 24)

- [Differentiable Particle Filtering via Entropy-Regularized Optimal Transport](https://mlsanity.com/paper/2102.07850/) (2021)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Convergence Rates for Regularized Optimal Transport via Quantization](https://mlsanity.com/paper/2208.14391/) (2022)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Bandits](https://mlsanity.com/paper/2309.08748/) (2023)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis](https://mlsanity.com/paper/2501.13648/) (2025)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (2024)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes](https://mlsanity.com/paper/2606.28308/) (2026)
- [Toric Geometry of Entropic Regularization](https://mlsanity.com/paper/2202.01571/) (2022)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [Avoiding Premature Collapse: Adaptive Annealing for Entropy-Regularized Structural Inference](https://mlsanity.com/paper/2601.23039/) (2026)
- [Convergence rate of Tsallis entropic regularized optimal transport](https://mlsanity.com/paper/2304.06616/) (2023)
- [Scalable Approximate Algorithms for Optimal Transport Linear Models](https://mlsanity.com/paper/2504.04609/) (2025)
- [Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias](https://mlsanity.com/paper/2505.02614/) (2025)
- [Sinkhorn Linearization and the Spectral Proxy: Unifying the Statistical and Algorithmic Theory of Feature-Parameterized Inverse Optimal Transport via a Single Spectral Sandwich](https://mlsanity.com/paper/2608.13201/) (2026)
- [Support Topology and Gradient Mixing in Sinkhorn Layers](https://mlsanity.com/paper/2609.07954/) (2026)
- [Scaling Online Optimal Transport Minibatches for Flow Matching](https://mlsanity.com/paper/2610.18838/) (2026)

## Abstract (arXiv)

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.