Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling
<|reference_start|>Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling: 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.<|reference_end|>
@article{burns2024provable,
    title={Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling},
    author={Matthew X. Burns, Qingyuan Hou, Michael C. Huang},
    journal={arXiv preprint arXiv:2410.06397},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06397},
    primaryClass={cs.LG cs.DS math.ST stat.TH}
}