Toric geometry of entropic regularization

DOI10.1016/J.JSC.2023.102221MaRDI QIDQ6170808zbMATH OpenOpenAlexFDO

Authors Bernd Sturmfels, Simon Telen, François-Xavier Vialard, Max-K. Von Renesse

Publication date 10 August 2023

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.01571

zbMATH Keywords

entropic regularizationlinear programmingtoric geometry

Mathematics Subject Classification ID

Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Computational aspects of higher-dimensional varieties (14Q15) Linear programming (90C05) Large-scale problems in mathematical programming (90C06)

Abstract: Entropic regularization is a method for large-scale linear programming. Geometrically, one traces intersections of the feasible polytope with scaled toric varieties, starting at the Birch point. We compare this to log-barrier methods, with reciprocal linear spaces, starting at the analytic center. We revisit entropic regularization for unbalanced optimal transport, and we develop the use of optimal conic couplings. We compute the degree of the associated toric variety, and we explore algorithms like iterative scaling.

Recommendations

• Entropic optimal transport: geometry and large deviations
• Entropic approach to interior point solution of linear programs
• Convergence of entropic schemes for optimal transport and gradient flows
• Iterative Bregman projections for regularized transportation problems
• A geometric perspective on regularized optimal transport

Cites work

• Algebraic Statistics for Computational Biology
• Computational methods for martingale optimal transport problems
• Generalized Iterative Scaling for Log-Linear Models
• Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Iterative Proportional Scaling Revisited: A Modern Optimization Perspective
• Likelihood equations and scattering amplitudes
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Martingale optimal transport and robust hedging in continuous time
• On the convergence of the coordinate descent method for convex differentiable minimization
• Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures
• Scaling algorithms for unbalanced optimal transport problems
• The central curve in linear programming
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Toric invariant theory for maximum likelihood estimation in log-linear models
• Triangulations. Structures for algorithms and applications
• Unbalanced optimal transport: dynamic and Kantorovich formulations

Cited in

(6)

• Gibbs manifolds
• Proximal Galerkin: a structure-preserving finite element method for pointwise bound constraints
• Regularity theory and geometry of unbalanced optimal transport
• Fisher-Rao gradient flows of linear programs and state-action natural policy gradients
• Santaló geometry of convex polytopes
• Lissajous varieties

This page was built for publication: Toric geometry of entropic regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170808)