mlsanityData to 14 Oct 2026

Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling

arXiv 2410.06397 ↗First posted 8 Oct 2024cs.LG cs.DS math.STcited by 0

Not on the map. Why?

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.

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

33 of 80 references.

References · 33

  1. 2016Equilibrium Propagation: Bridging the Gap Between Energy-Based Models and Backpropagationcited by 259
  2. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  3. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  4. 2015Coordinate Descent Algorithmscited by 219
  5. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  6. 2013Ising formulations of many NP problemscited by 207
  7. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  8. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 97
  9. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 71
  10. 2018Sampling Can Be Faster Than Optimizationcited by 68
  11. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  12. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
21 more
  1. 2018Split-and-augmented Gibbs sampler - Application to large-scale inference problemscited by 47
  2. 2022Predictive Coding: Towards a Future of Deep Learning beyond Backpropagation?cited by 45
  3. 2023Energy-based learning algorithms for analog computing: a comparative studycited by 37
  4. 2019Continuous Time Analysis of Momentum Methodscited by 32
  5. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  6. 2019Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splittingcited by 22
  7. 2018Continuous-time Models for Stochastic Optimization Algorithmscited by 17
  8. 2023Thermodynamic Computing System for AI Applicationscited by 16
  9. 2024Convergence of coordinate ascent variational inference for log-concave measures via optimal transportcited by 14
  10. 2017Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensionscited by 12
  11. 2022Efficient Optimization with Higher-Order Ising Machinescited by 11
  12. 2021On the Accuracy of Analog Neural Network Inference Acceleratorscited by 10
  13. 2019Improving Noise Tolerance of Mixed-Signal Neural Networkscited by 9
  14. 2015Asymptotic convergence of constrained primal-dual dynamicscited by 8
  15. 2020Langevin Monte Carlo: random coordinate descent and variance reductioncited by 7
  16. 2020Random Coordinate Langevin Monte Carlocited by 7
  17. 2020Random Coordinate Underdamped Langevin Monte Carlocited by 6
  18. 2022A sharp uniform-in-time error estimate for Stochastic Gradient Langevin Dynamicscited by 4
  19. 2020On the Generalised Langevin Equation for Simulated Annealingcited by 3
  20. 2024Accelerating Continuous Variable Coherent Ising Machines via Momentumcited by 2
  21. 2023Convergence Analysis of Opto-Electronic Oscillator based Coherent Ising Machinescited by 1

Built on by

Not cited yet.