# Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling

arXiv: https://arxiv.org/abs/2410.06397 · HTML: https://mlsanity.com/paper/2410.06397/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 80 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 30 of 33)

- [Equilibrium Propagation: Bridging the Gap Between Energy-Based Models and Backpropagation](https://mlsanity.com/paper/1602.05179/) (2016)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Split-and-augmented Gibbs sampler - Application to large-scale inference problems](https://mlsanity.com/paper/1804.05809/) (2018)
- [Predictive Coding: Towards a Future of Deep Learning beyond Backpropagation?](https://mlsanity.com/paper/2202.09467/) (2022)
- [Energy-based learning algorithms for analog computing: a comparative study](https://mlsanity.com/paper/2312.15103/) (2023)
- [Continuous Time Analysis of Momentum Methods](https://mlsanity.com/paper/1906.04285/) (2019)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting](https://mlsanity.com/paper/1905.11937/) (2019)
- [Continuous-time Models for Stochastic Optimization Algorithms](https://mlsanity.com/paper/1810.02565/) (2018)
- [Thermodynamic Computing System for AI Applications](https://mlsanity.com/paper/2312.04836/) (2023)
- [Convergence of coordinate ascent variational inference for log-concave measures via optimal transport](https://mlsanity.com/paper/2404.08792/) (2024)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Efficient Optimization with Higher-Order Ising Machines](https://mlsanity.com/paper/2212.03426/) (2022)
- [On the Accuracy of Analog Neural Network Inference Accelerators](https://mlsanity.com/paper/2109.01262/) (2021)
- [Improving Noise Tolerance of Mixed-Signal Neural Networks](https://mlsanity.com/paper/1904.01705/) (2019)
- [Asymptotic convergence of constrained primal-dual dynamics](https://mlsanity.com/paper/1510.02150/) (2015)
- [Langevin Monte Carlo: random coordinate descent and variance reduction](https://mlsanity.com/paper/2007.14209/) (2020)
- [Random Coordinate Langevin Monte Carlo](https://mlsanity.com/paper/2010.01405/) (2020)
- [Random Coordinate Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2010.11366/) (2020)
- [A sharp uniform-in-time error estimate for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2207.09304/) (2022)

## Abstract (arXiv)

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.