用二维平行退火解决约束优化中的惩罚参数难题，提升采样效率。
Two-dimensional Parallel Tempering for Constrained Optimization
- 引入二维平行退火，通过插值惩罚强度增强混合性能。
- 在图稀疏化任务中实现近似理想混合，KL散度按1/t衰减。
- 无需手动调参，适用于各类约束伊辛模型，可部署于现有硬件。
采样玻尔兹曼概率分布对机器学习与优化至关重要，推动了如伊辛机等硬件加速器的发展。尽管伊辛模型理论上可编码任意优化问题，但实际应用常受软约束影响：惩罚过强会降低混合速度，过弱则无法保证可行性。本文提出二维平行退火算法（2D-PT），通过增加一个插值惩罚强度的维度，确保最终副本满足约束，类似低温下的低能态。该方法显著改善重约束副本的混合性能，并消除对惩罚强度的手动调优需求。在带有复制约束的图稀疏化示例中，2D-PT实现近似理想混合，Kullback-Leibler散度以O(1/t)速率衰减；应用于稀疏化威沙特实例时，相较传统平行退火，在相同副本数下提速达数量级。该方法广泛适用于约束伊辛问题，可部署于现有伊辛机。
原文摘要 · Abstract (English)
Sampling Boltzmann probability distributions plays a key role in machine learning and optimization, motivating the design of hardware accelerators such as Ising machines. While the Ising model can in principle encode arbitrary optimization problems, practical implementations are often hindered by soft constraints that either slow down mixing when too strong, or fail to enforce feasibility when too weak. We introduce a two-dimensional extension of the powerful parallel tempering algorithm (PT) that addresses this challenge by adding a second dimension of replicas interpolating the penalty strengths. This scheme ensures constraint satisfaction in the final replicas, analogous to low-energy states at low temperature. The resulting two-dimensional parallel tempering algorithm (2D-PT) improves mixing in heavily constrained replicas and eliminates the need to explicitly tune the penalty strength. In a representative example of graph sparsification with copy constraints, 2D-PT achieves near-ideal mixing, with Kullback-Leibler divergence decaying as O(1/t). When applied to sparsified Wishart instances, 2D-PT yields orders of magnitude speedup over conventional PT with the same number of replicas. The method applies broadly to constrained Ising problems and can be deployed on existing Ising machines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。