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
| CREATOR | Yuchen He, Tianhui Jiang, Sihan Wang, Chihao Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 218 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05877