为混合类比优化算法提供可证明的精度边界，解决设备差异带来的性能不确定性。
Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling
- 将混合局部搜索转化为块朗之万扩散模型，建立理论分析框架。
- 证明理想设备下KL散度指数收敛，有限设备误差与步长、噪声成正比。
- 给出设备偏差与超参数的闭式关系，指导跨设备训练部署。
类比动力学加速器（DXs）在机器学习、优化与采样任务中展现出相比传统数字方法数量级的能效与延迟优势。然而，受限容量的加速器需依赖混合类比/数字算法求解实际问题，通常采用大邻域局部搜索（LNLS）框架。不同于全数字算法，混合LNLS缺乏非渐近收敛保证与系统性超参数选择方法，尤其限制了跨设备训练与推理。本文通过将混合LNLS约化为块朗之万扩散（BLD）算法，提供了非渐近收敛保证。结合经典采样理论工具，我们证明了在理想DX下，随机与循环块选择策略均实现指数级KL散度收敛。考虑有限设备变异时，给出了2-Wasserstein偏差的显式上界，其依赖于步长、噪声强度及函数参数。本研究构建了既有理论与新型计算平台间的桥梁，所得理论结果建立了设备变异、算法超参数与性能之间的闭式关联。
原文摘要 · Abstract (English)
Analog dynamical accelerators (DXs) are a growing sub-field in computer architecture research, offering order-of-magnitude gains in power efficiency and latency over traditional digital methods in several machine learning, optimization, and sampling tasks. However, limited-capacity accelerators require hybrid analog/digital algorithms to solve real-world problems, commonly using large-neighborhood local search (LNLS) frameworks. Unlike fully digital algorithms, hybrid LNLS has no non-asymptotic convergence guarantees and no principled hyperparameter selection schemes, particularly limiting cross-device training and inference. In this work, we provide non-asymptotic convergence guarantees for hybrid LNLS by reducing to block Langevin Diffusion (BLD) algorithms. Adapting tools from classical sampling theory, we prove exponential KL-divergence convergence for randomized and cyclic block selection strategies using ideal DXs. With finite device variation, we provide explicit bounds on the 2-Wasserstein bias in terms of step duration, noise strength, and function parameters. Our BLD model provides a key link between established theory and novel computing platforms, and our theoretical results provide a closed-form expression linking device variation, algorithm hyperparameters, and performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。