Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms

Yuchen He, Tianhui Jiang, Sihan Wang, Chihao Zhang · 2026

Read Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms by Yuchen He, Tianhui Jiang, Sihan Wang, Chihao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05877.txt.

Description

Yuchen He and three co-authors build a discrete optimal transport framework for studying simulated annealing. Annealing searches for good states by slowly cooling a random process, and sharp guarantees on its speed have been scarce. The team define a generalized discrete Wasserstein distance and a matching notion of action for paths of probability measures on graphs.

With those tools, the error of annealing is controlled by the action of its cooling path. They apply the result to two classic physics models, the mean field Ising model and the q-state Potts model. In both cases the annealing dynamics reach a set error within a polynomial number of steps. Symmetry reduces each analysis to a low dimensional projected chain.

Catalog record

CREATORYuchen He, Tianhui Jiang, Sihan Wang, Chihao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE218 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05877

Browse the full library · About the Tower of Babel