Discrete Optimal Transport: A Geometric Revolution in Simulated Annealing

TL;DR

This paper introduces a rigorous discrete optimal transport framework to provide the first non-asymptotic convergence guarantees for simulated annealing on finite state spaces. By defining a discrete Wasserstein-2 action, the authors prove that the complexity of sampling from complex physics models—like the Ising and Potts models—is determined by the path geometry. They achieve polynomial-time sampling even in regimes with first-order phase transitions.

The Geometry of "Moving Targets"

Sampling from high-dimensional discrete distributions (e.g., $10^{100}$ configurations of an Ising model) is notoriously difficult. Markov Chain Monte Carlo (MCMC) methods often get "stuck" in local minima (metastability). Simulated Annealing circumvents this by starting at a high temperature (easy to sample) and slowly cooling down to the target.

The Problem: How slow is "slow enough"? Historically, we used "warm starting" arguments—if the distributions $P_t$ and $P_{t+1}$ are close, the chain stays near equilibrium. However, this is hard to quantify without model-specific mixing time proofs.

The Insight: Inspired by recent work in continuous spaces (Langevin dynamics), the authors view the annealing process as a path in the Wasserstein space of probability measures. The "effort" required to traverse this path is its Action. If we can bound this action, we can bound the algorithm's error.

Methodology: Building a Discrete Benamou–Brenier Formula

In continuous space, the Wasserstein distance is famously characterized by the Benamou–Brenier formula, which treats the problem as a fluid flow minimizing kinetic energy. Discrete space lacks a natural gradient $abla$, so the authors had to build a substitute.

1. Generalized Edge Capacity

They define the mass transport as a flow along graph edges $\{x,y\}$ using a capacity function $c_{\rho }(x,y)$. This capacity reflects the dynamics of the underlying Markov chain (e.g., Glauber dynamics).

2. Dual Flux Formulation

Calculating the "Action" $|\dot{\pi }{|}_t^2$ is an optimization problem. The authors show a beautiful duality: the squared speed of a distribution's movement equals the minimum energy of a Flux $J$ that satisfies a discrete continuity equation: ${\partial }_t{\pi }_t+ext{div}_{d}J=0$

Figure 1: The free energy landscape of the Potts model. As temperature changes, the number and stability of equilibrium states (modes) shift, creating the "topography" our algorithm must navigate.

Application: Breaking the Potts Transition

The $q$-state Potts model is the "Final Boss" of sampling because it undergoes a first-order phase transition. At the critical temperature, the system acts like a mixture of "ordered" and "disordered" states separated by a massive energy barrier. Standard annealing schedules get trapped here.

The Authors' Solution:

1. Symmetry Reduction: They project the massive $q^n$ state space onto a much smaller $n^q$ space based on "magnetization vectors."
2. Reversed Schedule: Instead of cooling down from chaos, they start at a very low temperature (monochromatic states) and "heat up" to the target. This ensures the path stays within the "ordered" phase, avoiding the discontinuous transition entirely.

Table 1: Convergence of the Annealed Ising model compared to classic benchmarks.

Key Quantitative Results

• Ising Model: $O(n^5{\beta }^2/ϵ)$ steps across all temperatures.
• Potts Model: Poly($n,\beta ,1/ϵ$) steps for $\beta \ge q/2$.

Critical Analysis & Future Outlook

Why This Matters

This paper successfully bridges Optimal Transport and Algorithmic Statistics. By transforming the sampling problem into a geometric construction of "fluxes," it allows researchers to bypass the grueling work of calculating spectral gaps for every new model. If you can define a "smooth" path on a graph, you can sample it.

Limitations

• Symmetry Dependence: The polynomial bounds for Ising/Potts rely heavily on the models being "mean-field" (highly symmetric). For sparse graphs (like 2D lattices), the projection method is not directly applicable.
• $n^5$ Complexity: While polynomial, an $n^5$ or $n^C$ scaling is still computationally expensive for billion-scale graphs.

Conclusion

"Discrete Optimal Transport" is no longer just a theoretical curiosity for mathematicians; it is a powerful lens for designing the next generation of sampling algorithms. The "Action-based" perspective proves that the path we choose is just as important as the destination.

Takeaway: To sample from a hard distribution, don't just cool it down—plan a path in Wasserstein space that minimizes geometric action.