离散最优传输：突破模拟退火收敛分析的几何新范式

TL;DR

模拟退火（Simulated Annealing）作为处理多峰分布采样的经典策略，长期以来缺乏像连续 Langevin 动力学那样优雅的几何理论支撑。本文通过引入离散 Wasserstein-2 距离，首次建立了一套基于“离散动作（Discrete Action）”的非渐进收敛框架。该框架将复杂的马尔可夫链收敛分析简化为了对退火路径几何性质的控制，并成功在均场 Ising 和 Potts 模型上验证了其多项式级的复杂度。

背景定位：从连续到离散的桥梁

在连续空间中，ICLR 2025 的工作 [GTC25] 已经证明了退火 Langevin 动力学的复杂度由 $W_2$ 空间中的“动作”决定。然而，离散空间（如 Ising 模型的构型空间）具有组合爆炸特征且缺乏梯度，使得 Benamou–Brenier 等描述最优传输的动力学公式难以直接搬运。本文的主要贡献在于：它不仅是理论的修补，更是开创性地将模拟退火转化为一个纯粹的几何路径分析问题。

核心直觉：什么是离散 Wasserstein 动作？

作者通过改进 Maas (2011) 的理论，定义了离散状态空间上的流量（Flux）和势能（Potential）。

1. 离散连续性方程

在图 $G=(V,E)$ 上，概率质量的演化不再通过梯度，而是通过边上的流量。作者定义了满足以下方程的离散通量 $J_t$： ${\partial }_t{\pi }_t+{\mathrm{div}}_d{J}_t=0$ 这意味着在时刻 $t$ 概率分布的变化必须由边上的进出流量严格补偿。

2. 动作 (Action) 的物理含义

动作可以被理解为在退火路径上移动概率质量所消耗的“总动能”。其核心公式为： $|\dot{\pi }{|}_t^2={\min }_{J_t}\frac{1}{2}{\sum }_{x,y\in \Omega }\frac{J_t(x,y{)}^2}{c_{{\pi }_t}(x,y)}$ 其中 $c_{{\pi }_t}$ 是反映马尔可夫键转移效率的边容量。直觉上：如果路径走得太快，或者经过了转移阻力大的区域（容量低），动作就会激增，从而导致算法误差变大。

关键技术：对称性还原 (Symmetry Reduction)

面对指数级的状态空间 $\{\pm 1{\}}^n$，直接计算动作是不可能的。作者提出了一个强有力的引理：如果投影映射保留了系统对称性，那么投影后的低维路径动作与原始高维路径动作完全一致。

图 1: Potts 模型的相图与自由能景观。通过将高维构型投影到磁化强度向量，复杂的能量景观被简化为可分析的单峰或多峰结构。

实验与结果：挑战 Potts 模型的相变

Potts 模型因其一级相变（First-order phase transition）而臭名昭著。在临界温度附近，传统的采样算法（如 Swendsen-Wang）会陷入指数级变慢的泥淖。

本文通过设计一种“反向退火”时间表（从极低温开始，逐渐升温至目标温度），避开了不连续相变的剧烈波动区域。

表 1: 不同算法在均场 Potts 模型上的复杂度对比。可以看到，本文方法在全 $\beta \ge {\beta }_s$ 区域均实现了多项式级的复杂度，而传统算法在特定区域会失效。

深度洞察

1. 脱离 Warm-start 的束缚：该理论标志着从“局部混合时间”向“全局几何路径”分析的范式转移。
2. 双向性：该框架不仅能证明收敛，“动作”的概念也为寻找最优退火路径（即动作最小的路径）提供了理论依据。
3. 局限性：目前的投影方法高度依赖于模型的对称性。对于缺乏对称性的复杂神经网络能量景观，如何构造有效的边容量和路径仍是巨大的挑战。

总结

本文通过离散最优传输理论，为采样算法的非渐进分析提供了极其严密的数学工具。它告诉我们：采样不仅是一个概率问题，更是一个在 Wasserstein 流形上的路径规划问题。