Provable Convergence Bounds for Hybrid Dynamical Sampling and Optimization
Authors: Matthew X. Burns
Qingyuan Hou
Michael Huang
Venue: ICLR 2025 Poster (2025)
Keywords: langevin
accelerators
sampling
optimization
diffusion
analog computing
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We provide novel non-asymptotic convergence rates for a class of hybrid analog-digital algorithms for dynamics-accelerated activation sampling and inference.

Abstract: 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.

Published as a conference paper at ICLR 2025
PROVABLE ACCURACY BOUNDS FOR HYBRID DYNAMICAL OPTIMIZATION AND SAMPLING
Matthew X. Burns, Qingyuan Hou & Michael C. Huang Department of Electrical and Computer Engineering University of Rochester Rochester, NY 14527, USA
{mburns13, ghou3) rochester........ edd mi michael hwwng@rochesteeeeeeeeee edu
ABSTRACT
Analog dynamical accelerators (DXs) are growing sub-field in computer ar- chitecture research, offering order-of-magnitude gains in power efficiency and latency over traditional digital methods in several machine learning, optimiza- tion, 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 non-asympotiic convergence guarantees and no principled hyperparameter selection schemes, particularly limiting cross-device training and inference.
In this work, 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 pro- vides key link between established theory and novel computing platforms, and theoretical results provide closed-form expression linking device variation, algorithm hyperparameters, and performance.
INTRODUCTION
Computing research has long borrowed from the physical sciences. Sampling and optimization algorithms such as simulated annealing (Kirkpatrick) 1984), parallel tempering (J. Earl W. Deem 2005). and Langevin Monte Carlo (LMC) (Chewi et al. 202T) were directly inspired by physical processes observed in nature. In like spirit, a growing computer architecture sub-field has proposed leveraging physical dynamics accelerate computationally expensive workloads using "dynamical accelerators" (DXs). Originally, research focused on combinatorial optimization problems (Inagaki al. 2016 Mohseni et al. (022) and matrix-vector multiplication Xiao et al. (2022). However, the field has
al.) 2017 Wang Roychowdhury 2019; Afoakwa al.) 2021
expanded to sampling for energy-base -based model training and inference (Vengalam et al. 2023 and
generative inference in graph neural networks (Wu et al. 2024 Song et al. 2024).
The interest in analog acceleration coincides with novel proposals for "local update" algorithms, where layer activations /i are solutions to a minimization problem h; argmin, (Scellier & Bengio 2017 Stern al., 202T Millidge al., 2022 Scellier et al. 2023). While costly in digital systems, stochastic analog optimizers
effectively solve argmin, f(h in minimal time and en- ergy (Wu et al. 2024), making them suitable candidates for local-update learning implementations.
However, real-world problems are typically too large for dynamical accelerators to optimize in their entirety, requiring routines to partition and iteratively sample/optimize subspaces (Booth et al. 2017 Sharma al.) 2022: Song al. 2024), most commonly using hybrid harge--nighboohood local search" (LNLS) frameworks (Ahuja et al. 2002; Booth et al. 2017). In hybrid LNLS, the DX is used perform alternating sampling/minimizztionn
within-capacity subproblems. However, hybrid

---

Published as a conference paper at ICLR 2025
LNLS has undergone little theoretical examination. No non-asymptotic convergence bounds yet exist, limiting the appeal of hybrid LNLS compared with more well-understood digital algorithms. Moreover, the effect of algorithm hyperparameters non-idealities is unclear. Models trained on one DX may require hyperparameter adjustment, not outright device-specific retraining, prior to inference on another (He et al. [019 Long al. 2019). Without non-asymptotic analysis linking device variation and accelerator convergence, accelcrator adaptation reduces trial-and-error.
convergence and their interplay with device
In this work, we provide the first explicit probabilistic convergence guarantees for hybrid LNLS algorithms in activation sampling and optimization: a crucial first step in optimizing and analyzing hybrid DX frameworks. We start by reducing hybrid LNLS to block sampling with continuous- time, Langevin diffusion- based sub-samplers, to which we can apply tools from classical sampling analysis. Two block selection rules for "block Langevin diffusion" (BLD) are examined, randomized and cyclic, using ideal (Secs. 3.2 3.3) and umite-variation (SeeB.4) analog components. Under log-Sobolev inequality (LSI), we prove that ideal accelerators converge to the target distribution exponentially fast. However, we show that finite device variation incurs a bias in W₂ distance, variation magnitude. We illustrate findings with
proportional step duration and dependent numerical experiments on a toy Gaussian sampling problem, demonstrating the effect of device variation and hyperparameter choice on convergence.
Our contributions can be summarized as follows:
1. We provide the first bounds on randomized block diffusions using explicit constants (The- orem D strengthening the results of Ding et al. (2020)
2. We provide completely novel bounds for cyclic block diffusions (Theorem) 2 by proving general conditional sampling lemma for Kullback-
divergence (Lemma
3. Using a Talagrand transportation inequality, we combine our ideal results with analysis fol- lowing Raginsky et al. (2017) to provide non-asymptotic guarantees for DXs with analog non-idealities (Theorem 3 applicable to both sampling and optimization tasks.
2 BACKGROUND
2.1 RELATED WORKS
Ding & Li (202T) and Ding et al. (202T) proposed and analyzed "randomized coordinate Langevin Monte Carlo" (RCLMC) methods for sampling tasks using over and underdamped Langevin dy- namics. Their methodology used Wasserstein coupling arguments akin to Dalalyan (2016), in contrast to interpolation arguments following Vempala & Wibisono 2019). Accordingly, the authors assumed a strongly-log concave target distribution: a much stronger assumption than an LSI. Moreover, Ding et al. (2021) provided insufficient analysis for the continuous-time case, focus- ing primarily on the discrete RCLMC algorithm. DX algorithm analysis required continuous-time bounds with explicit constants, necessitating our contributions.
Two algorithms related to BLD gamering recent interest are "coordinate ascent variational in- ference" (CAVI), which performs variational inference over factorized "mean-field" distribu- tions (Bhattacharya et al.) 2023) Arnese & Lacker 2024), and the split Gibbs sampler (SGS), which alternates sampling over problem variables with augmented priors (Vono al., 2019 2022). CAVI
is similar to BLD, and indeed the information theoretic analysis Le[eee (2022) has a similar structure to our proof of Lemma [ SGS has been likened to ADMM optimization Vono et al. (2022), indi- cating there may be an equivalence to BLD akin to classical block optimization Tibshirani (2017).
related class of works have analyzed the accuracy of analog matrix matrix-vector multiplication (MVM) accelerators in neural network inference (Klachko et al. [2019] Xiao et al. 2022). MVM accelerators are a restricted class of DXs minimizing min,ceR |yy W x analog domain. Our analysis generalizes MVM analysis and is applicable in more complex analog
equivalent to performing MVM the
settings such as generative sampling (Vengalam et al. 2023 Melanson et al. 2023 Wu et al. 2024).
carried out by Ere- mentchouk et al.] (2022); Pramanik et al.] (2023). Asymptotic convergence in expectation to the global minimizer was proved by Pramanik al. (2023 in the zero-temperature limit with decreas-
Optimization-bu based convergence analyses of specific DX architectures
2

---

Published as a conference paper at ICLR 2025
ing stepsize, echoing results in Sec. 3.4 However, neither work accounted for the effect of device variation or problem partitioning, and both focused on specific DX modalities (nonlinear clectroniicoptical oscillators) rather than general model of DX behavior. informattionthhorrett analysis conducted by Dambre et al. (2012); Hu et al. (2023) have bounded the asymptotic compu- tational capabilities of DX systems, but not their probabilistic convergence.
2.2
DYNAMICAL ACCELERATORS
The first wave of dynamicc--cceelratte optimizers primarily targeted the lsing Spin Glass (ISG) Hamiltonian from statistical physics, earning the appellation "Ising Machines". The ISG Hamilto- nian describes quadratic interactions between binary "spins". which can be used to solve intractable combinatorial problems (Lucas 2014p. Ising machines have been implemented using quantum
spins UshjjimaMWesspp
et al. 2017 electronic (Wang& & Roychowdhury 2019: Albertsson &
Rusu 2023) and optical (Inagaki et al., 2016 Honjo et al., 2021) oscillator phases, resistively- coupled capacitors (Afoakwa et al. 2021] ) and many more besides (Mohseni et al. 2022). These
initial prototypes successfully optimized binary target functions. However, recent architectures have broader applications domains: with support for non-quadratic cost functions (Sharma et al. [023]
Bashar & Shukla 2023 Bybee et al. 2023) and continuous values (Brown et al. 2024; Wu et al,,
2024 Song al. 2024). Since these designs have moved beyond the ISG Hamilonian
term
this broader class simply as "dynamical accelerators" (DXs).
While the physical implementation differs between DXs, several proposals can be described by Langevin stochastic differential equation (SDE)
dr. (a t)dt + 2B(())
where x, A xx()) is the system state, dW, is Brownian noise term, h(r,, () is the deterministic system potential, and 3(1) = (L) is the (potentially time dependent) inverse pseudo-temperature of the system.
rt()) represents the continuous, physical degrees of freedom of the optimizer/sammler, such as capac- itor voltage (Afoakwa al. [022] oscillator phase (Inagaki et al. 20166] Wang & Roychowdhury
2019). Several prototypes have been shown to follow forms of Equation (I. either intentionally
to escape local minima (Wang & Roychowdhury, 2019. Sharma et al. 2023 Aifer et al. 2023 or
unintentionally to model dynamic environment noise (Wang et al. 2013). The potential h(r t) in-
cludes the target function f(x) along with optional time-dependent terms, such as a sub-harmonic injection locking potential for binarization (Wang & Roychowdhury/ 2019).
DXs are also prone to static "device variation" owing to analog non-idealities. Unlike the Brownian term dWe, static non-idealities are not self-averaging, and result in biased estimate ga(x) of the gradient (xx)). In a quadratic function f(x) = x² x, for instance, the gradient estimate can be described (z) (W + WT) + óx, where di (00 ?) are fixed non-idealities in device components. Previous studies have examined the impact of static variation on binary op- timization (Albash et al.) 2019) and matrix-vector multiplication (Xiao al. 2022). but have not extended to non-asymptotic convergence analysis for more general functions over R2
2.3 LANGEVIN DIFFUSION
If we restrict our analysis to the hime-homogeneous case where M(x f(x), 3(1) 8, the dynamics are Markovian with constant stationary distribution
(x(x) & e -8(())
The Langevin SDE
dx, = f(((t) + 2
produces continuous sample path sr()) with each x(T), T 2 0 acting as a random variable. The law of Tt, μe (denoted μ4 = L(xx)). , is described by the Fokker-Planci equation (FPE)
0,44 = v-' 14 + V [(xr))
The Langevin SDE describes the physical evolution of xe, while the FPE describes the change in the sample distribution μe in measure space. If n satisfies a Sog-Sobolev inequality (LSI, see Sec. 3), then 14 converges ny exponentially fast (Theorem 1 Vempala & Wibisono 2019).
3

---

Published as a conference paper at ICLR 2025
Theorem 0 (LD Convergence (Theorem 1 of Vempala & Wibisono 2019 Suppose πe(a))
e-ff()) satisfies LSI with constant 1/7. Then the distribution jrt of the Langevin diffussoo at time satisfies
(HE(TT S e-228 2-245 "DKL (pol(T
where (HelTT & J (c(x)) log px(2) a(x) dr A M log de
due is the Kullback-Leibler (KL) divergence
between two probability measures.
Recalling the Otto- Villai theorem (Theorem Otto & Villani 2000), an LSI inequality further implies Talagrand transportation inequality
(2)
2
1/2
W2(Me, x) S
DRL (MellT)
where W2(H,, x) = inf infvec(uem) (f tween and π and y E C(ue, x) is a coupling over μt, भ. Convergence in DKL under an LSI there- fore implies convergence
y)drdy) is the 2- Wasserstein distance be-
W2, allowing us state bounds in both. Crucially for our purposes, the 2-Wasserstein distance is metric over probability distributions, allowing use of the triangle inequality (Raginsky et al. 2017).
As 3 + 00, (x) concentrates around the minimizer(s) of f. This observation permits us to unite optimization and sampling using annealing schemes (Kirkpatrick) 1984, Chiang et al. 1987] Chak et al. (023) which gradually increase 3 to escape early local minima and (hopefully) find the global minimum, indicating a direction for future work extending our results. Previous works have also used bounds on convergence to Ty constant 3 to bound optimizer hitting times Zhang et al. (2017) and expected excess risk (Raginsky et al. 2017 Xu et al. 20200] Farghly & Rebeschini 2021 ZZang al. 2023) in non-convex optimization.
MAIN RESULTS
3.1
LNLS BLOCK SAMPLING
DXs have finite capacity, necessitating hybrid analog/digital algorithms to solve problems exceed- ing that capacity. A popular candidate for hybrid optinization/sampiinn is the Large- Sernge--eighbbroooo
Local Search (LNI.S) framework (Ahuja et al., 2002 Booth et al., 2017 Sharma et al.) 2022 Ray- mond et al. 2023), where local solver (the DX) is used to optimize/sample blocks of variables [Bi, B2, .... Bb conditioned on the rest of the problem state, illustrated in Fig.
B
B
B
B x
X,
DX
DX
B A,
Host
Host
Host
B A
B2
B
B
Time
Time
Figure 1: Illustration of the LNLS algorithm 3-block, 9-variable problem. [T.fft] An illustration of the variable sample paths during algorithm execution. When a block not being actively evolved, the constituent variables remain fixed (gray). [Right] Logical partition of variables in LNLS framework, where one block is being actively evolved by the DX with the others resident in digital memory. The digital host performs the control operations needed read the block state, write back to memory, and begin the next block evolution.
We can formalize LNLS by borrowing notation from classical coordinate descent (Nestervv 2012
Beck Tetruashvili 2013). We decompose the space Rdd into disjoint blocks X Bü where
4

---

Published as a conference paper at ICLR 2025
Algorithm Block Langevin Diffusion (BLD)
1: procedure (L. E dom(f), Decomposition (Bi..., Bo), Step Size Set À E RR.)
2: for k 2 0 do
3: Choose block index (Random or Deterministic)
4: Set tx+1 ix Ao
5: Sample:
1++1
U.Vf(x)dt + (' U://2-1ld,
x(tx+1) = x((t))
6: end for
7:
end procedure
each subspace B, has dimension d, LNLS frameworks perform alternating sampling from each conditional distribution (B.:BB...bb> where each block is chosen at random in deterministic order.
For simplified notation, decompose 1dt - Ei U, where each U3 Rdxd has ones along diagonal indices corresponding to dimensions in B, and zeros elsewhere. Then Ei=u, U.V.(z) = V fxr) and express the SDE for single block B, diffusion
dr (U) + U. 23-1dW
(3)
Equation (3) leaves the conditioned dimensions B, (j E {1,..., d} j E B²} invariant. Each block diffusion occurs in continuous time, but the blocks are swapped at discrete steps. Accord- ingly, denote x(4x) the iterate at time in block step and Nt, its associated probability distribution.
model LNL.S block sampling algorithm, termed Block Langevin Diffussion (BLD), shown in Algorithm [ BLD is continuous- generalization of "randomized coordinate Langevin Monte Carlo" (RCLMC) stud- ied in Ding et al. (202T): Ding & Li (202T). By reducing LNLS to BLD, we can tractably analyze algorithm performance using deve-peel tools from stochastic process analysis. As expressed, Algorithm [ leaves open the choice of block selection. Here we consider randomized and cyclic selection rules, denoted Randomized Block Langevin Diffusion (RBLD) and Cyclic Block Langevin Diffusiio (CBLD) respectively.
When each block evolves constant according Equation (3)
Throughout our analysis, we make the following assumptions on f.
Assumption 1. f is continuously differentiable
Assumption 2. Ty & exp[-8 satisfies log-Sobolev inequality (LSI) with CLst 4. That is, for all distributions with finite second moment
FT(()(TT)
(KL(A))TT / u(xx) log
m(x) dr Te(x) 27 [(z))lV log
((x)
Fr
where FT( ) is the (relative) Fisher information. An LSI can hold even in non-log-concave dis- tributions, making it more general assumption than the strong log-concavity presumed by Ding &
Li (201). Examples include globally strongly log-concave measures with bounded regions of non- log concavity (Raginsky al. 2017 Ma et al. 2019). high-temperature spin systems (Bauerschmidt & Bodineau 2019) and heavy- -tiled distributions which may not be strongly log- log-concave (such as measures with potentials f satisfying a Kurdyka Lojoykka--jsiiiiizz inequality Boltte al. (2010))
3.2 RANDOMIZED BLOCK LANGEVIN DIFFUSION
In the randomized case, we select the next variable block according to probability mass function Φ E R with all Φ; > 0. Ding et al. 2022 analyzed RCLMC using Wasserstein coupling arguments, however analysis builds on the traditional proof of Equation (2) which relies on the de Bruijin identity
0 D (p)l -3-1
- FI(eellv)
5

---

Published as a conference paper at ICLR 2025
which, when combined with the LSI, proves exponential convergence since
FI( [1) Σ
-2 DKL (p)l In the same vein, we use probabilistic arguments in Appendix C.2 to prove a de Bruijin inequality
d DKL (pel(T)) I -mmin 9 FT(u41lu)
where Pmin is the minimum block probability in ø.
By integrating and expanding the inequality, we casily obtain convergence in DKL (H((tx][(Tg)) ex- pressed in Theorem [
We also prove convergence for discrete-time variant (RBLMC) in Ap-
pendix C
Theorem (RBLD DKL. (1t,, (T)))) Convergence). Let Φ (01:--.-60) 4b) be the block selection prob- ability mass function, Φ; 0, and let X (A1,-..,As) Rh be the sampling times for each block, X; > O. For any Tg x expl-3f(x)) satisfying Assumptions and 2 and any 3 > O, the sample distribution after k steps of RBLD (ptz) satisfies
DKL [T) S 278 Omin Aminh DKL (KI(Po|TTD)
3.3 CYCLIC BLOCK LANGEVIN DIFFUSION
While our randomized results tighten existing theory, real-world instances of LNLS often use cyclic orderings Sharma al. (2022); Song et al. (2024); Wu et al. (2024), as they are more amenable to direct hardware and software optimization and are simpler to implement.
However, unlike RBLD, we cannot easily prove "de Bruijin inequality" for CBLD. Instead, we make extensive use of the chain lemma for DKL.
DRL(ullv) End [DLL (HAlel|Aaae) + (RD(UD)EE)
where A, E are disjoint subspaces of R2, A U E = RR, and are measures supported on Ed with MAJE denotes the measure over A conditioned on E y for arbitrary y. Note that we set = B,, E = B. the CBLD diffusion will result exponential contraction in Eyz, [DKr. B, IB, 11 T3, while leaving (KI, (!T,)) constant. CBLD then trivially results non-increasing DKL (f))))) however expressing descent across iterations is more subtle due to the uub-additivit of KL-divergence.
Taking inspiration from Beck & Tetruashvili 2013), we bound descent across steps, an entire "cycle" over the problem space, expressed in general lemma for (K (( (proved in Ap- pendix D)
Lemma (Cyclic KL Contraction). Let the C (Ci,..., C.} R4 satisfy 0 < C. < and let D; E R be arbitrary constants D, 2 O and let т be an arbitrary distribution with finite second moment. Suppose (Ho: (1.... sequence of measures satisfying for k 2 and
mod! b (1 3) S C. (Kt + (1 -C.) DRI(P (|TB). + D,,-
Then bound
DKL (ptas ())
< Cl DKL (Mtta- 1/7 -
where Cmax max(CCi C.).
Lee 2022 lower bounded the KI-divergence in Bayesian coordinate ascent variational inference by similarly comparing the change in DKL across conditioned steps. However, their focus was on inference over mean-field parametric distributions rather than the broader class of LSI Gibbs measures, making Lemma stronger result.
The convergence CBLD follows by choosing D, = 0, Cmax = 2 2 Amnn
(B.,...,B) Bb) be given block per- mutation and let À (A ....,, Ao) Rd be the sampling times for each block, X > 0. For any T x expl-3f(x)) satisfying Assumptions) and and any 3 > O, the sample distribution after kb steps of CBLD (Pte.) satisfies
Theorem 2 (CBLD DKL (u(t+) (T)) Convergence). Let
DRA (8)) S -2y0 Ammak (Hol(T

---

Published as a conference paper at ICLR 2025
When D; * 0, Lemma| accounts for biased sampling algorithms, such Langevin Monte Carlo (LMC). Accordingly, we combine Lemma
[ with existing LSI bounds for LMC from Vempala & Wibisono (2019); Chewi et al. (2021 to prove convergence for discrete time "cyclic block
L.angevin Monte Carlo" in Appendix
Observations: For RBLD and CBLD, the convergence is limited by the shortest step duration Amin and minimal block probability Ømin For constant block sizes, the optimal choice for both CBLD and RBLD therefore constant X X3 = À and uniform d; = 1/b. This contrasts discrete- time block optimization, where distinct step sizes/probabillin distributions provide advantage on ill-conditioned problems (Nesterov] 2012 Beck Tetruashvili 2013 Ding et al. (02I) due the effect of varying Lipschitz constants in discretization error terms. In the case of constant À with uniform Φ RBLD and CBLD have identical descent bounds, as we numerically demonstrate in Section 4 This considerably simplifies hyperparameter selection for ideal devices, reducing from (bb) parameters to 1 (A). the following section we continue to assume a constant step duration A for simplicity, though future analyses may reveal more optimized step size selections for finite- variation devices.
3.4 FINITE VARIATION
Theorems D and 2 provide optimistic lower bounds for DX sampling, however real machine will have analog errors perturbing the target function (Albash et al. 2019 Melanson et al. 2023). As a generalization of Albash et al. (2019), we model DX with analog variation with "perturbed" gradient oracle (r) IR" R. where E D denotes fixed perturbation from arbitrary domain D. Unlike stochastic optimization, which assumes that the perturbation changes with each gradient evaluation, DX perturbations are fixed for each device. To provide guarantees under device variation, we need to restrict the perturbations and functions permitted:
Assumption 3. For fixed 8 D, there exist constants M, B 2 0 such that for all æ E Rd
[[V (>x)) < M | B².
Assumption 4. f is L-smooth and, for fixed D, 98 G-Lipschitz continuous. That is, for all J,y Rd
[V f((il < L|| - y|l, (1)((r) ال(ا) < G||a - vll-
Assumption 5. and go are (m, diddsiippeeee and (m, c)-dissipative respectively, i.e., there exists positive constants > 0, m, 2 0 such that for all E Rd:
(v)())
2 m m||a/||
V (Vgs(r),
2 m m||x:||2 c
Assumption 3 limits the Euclidean distance between Vf and gs. with the constants M and B ap- pearing in later bounds. Assumption 5 is a common assumption in analyses of stochastic gradient sampling algorithms (Raginsky al. 2017 Li & Wang. 2022 Zhhnn et al. 2023). Specifically, it enables us to bound the ideal Langevin second moment y (+x)l in the proof of Theorem Assumption 4 not directly used in our proofs, but is required for a Girsanov change of measure. Assumptions 3 and 5 restrict the type of perturbation with Assumption 3Janp limiting the mag- nitude. If Assumptions and 5 hold for the target potential, it is reasonable expect that they hold for the perturbed oracle as well, since DX variation typically manifests as additive or multiplicative perturbations analog components implementing V Xiao al. 2022 : Aifer al. (2023).
Take the example of a Gaussian potential f(x) 1/x Σ- l with ga (x) = x-' +8)ar, where d E d is "perturbation matrix" with d, (O, A?) and denotes component-wise. Hadamard product. Regardless of the standard deviation A, we satisfy Assumptions 33 and 4 with M and L both equal to the maximal magnitude eigenvalue of 5 and Σ-1 respectively with /3 0. However, if E1 5) has negative eigenvalues there is no m > 0 satisfying Assumption 5 placing an upper limit on the perturbation strength.
Assumption 6. The density of the initial law po satisfies
Kg log
cllwll dpo 00.
Rd
7

---

Published as a conference paper at ICLR 2025
In practice, dynamical accelerators typically operate over bounded domains, such the unit hy- percube (Afoakwa et al. 202I) or unit circle (Wang & Roychowdhury 2019) Inagaki et al.) 2016), hence the iterate magnitude is bounded in any case. However, bounding over the entire space would provide insufficiently tight upper bounds and our methodology assumes that the measures are sup- ported on Te. We leave consideration of domains with bounded support to future work, potentially applying methods from reflected Langevin diffusion theory (Bubeck et al., 2018) or projected dif- ferential analysis (Cherukuri et al. 2016).
We begin by stating the following bound on the distance between the measures of ideal and perturbed BLD, proved in Appendix [
Lemma 2 (Finite Variation Block Langevin W2 Distance), Let r(t), y(t) be non-ideal and ideal block Langevin processes respectively with associated distributions Pr, Vt. For any T x Hg satisfying
ffpl-8((x)) satisfying and 5 wwth 3 2. 96(x) satisfying Assumption Assumption 0 and kλ after ksb Terations of BLD
m.
(o( +C2+ VO2V KA
W2(Hees Pow)) = S
V
where Co. C1, and O2 are given in Appendix E
From previous discussions, setting o; 1/b, X = À unifies the bounds for RBLD and CBLD. In this regime, we can prove the following statement as a simple consequence of the triangle inequality W2(n1, 2) S (2(,,)) 1) + (1) v) and the Otto-Vila Villani theorem Theorem (Finite-Variation Variation BLD W2 Convergence).
2
1/2
1 A V (KL(MO + Co [a (G VG)+ V KA.
Wa(Mtau ma) S
2v 122 (Hol=z)) and set X I
Following
Raginsky et al. (017)), if we choose kd = log
eva
(EY)* (glog (T (vrr)) -1 we have
We(PuurTT 2 8 + v [ci V
a log 2 2/2 + +&v C2 + Von
(4)
8V7
We thereby obtain a total bound on the Wasserstein error Ollog 1 e + E) for arbitrary E > 0.
Observations: Similar to discrete-time LMC, our Wasserstein bound has non-zero lower bound with respect to 6: non-ideal devices introduce bias. Unlike discrete LMC, the bias in Equation (4) does not result from forward-flow discretization (Wibisono) 2018 Chewi et al. 2021). Instead, the constants Co, C1, C2 are solely due to finite analog variation. For MM O. B O, we re- cover exponential, unbiased convergence in W2. However, akin to LMC, practitioners can select the step size À and the injected noise 3 to control the bias. Higher temperatures (lower 3) result in a lower bias, as expected from the application of a noisy channel in measure space. Moreover, DX users/designers typically characterize M, B during device calibration: simultaneously lowering the impact of analog non-ideality and allowing for rough bound on the distribution bias (See Section C.2.a of Melanson et al., 2023).
Wasserstein bound suffices as performance guarantee in sampling tasks such as Boltzmann machine inference (Hinton et al. (2066) or statistical physics simulation (Hamerly et al. 2019 Ng et al. 2022 Inaba et al. (023). For optimization, assuming quadratic function growth with , 2
and dissapative gradient oracle (Assumption 5) allows the use of continuity inequality (Lemma
of Raginsky et al.
2017) and second moment bound (Proposition 11 of Raginsky et al. 2017 to
bound ppp,, [x)
E (z)] and IE,, [x)) min f(x) respectively
E Pan [f()] - Ex, [f(x)) < (Ma + W2 (T))
(5)
d
eL
c3
+ )
E [xx)
min f(x) -
log
(6)
ZERd 2,3
m
d
8

---

Published as a conference paper at ICLR 2025
where o² max [x2), Eng [ag (given in Appendix we obtain
E
Combining Equations ( and (
min =ERd f(x) v d
el.
cB (Mo B)
+1)
Bpre [f(z)]
log
2
m
O 3
log 3d + (M + B) loge=
Controlling the first term requires increasing / (lower injected noise) tandem with problem di- mension. Conversely, controlling the second term requires Akb x B, À ze, i.c., more iterations free to choose À arbitrarily
with lower step duration with increasing B. In digital algorithms, small to meet given precision requirements (though the program convergence may be impracticably slow). Dynamical accelerators typically have lower bound on (e.g. digital clock), translating into an effective upper bound on B.
NUMERICAL EXPERIMENTS
As an illustrative example, we simulated CBLD and RBLD behavior for = 50 Gaussian sam- pling with 3 1 and uniform A; = Gaussian distributions permit closed-form solutions for (NL Σn (uz, Σ2)). allowing for a quantitative estimate of convergence. Moreover, sev- eral proposed use cases for DXs rely on Gaussian sampling. including matrix inversion (Aifer al.]
2023) and uncertainty quantification (Melanson et al., 2023). Other works have also proposed using
DXx optimize strongly-conye functions of the form J(x (x- u) W(x u) (Wu al. 2024
Song et al. 2024). As discussed in the preceding section, our bounds provide expected function gap
guarantees from sampling π (u, 23 2
W-- ). where optimization would occur in the 3 oo
limit. Appendix A gives more experimental details.
Fig. 2a shows the convergence DKL for the estimated distribution br with block counts E (1,2, 5, 10} versus simulated time. Note that we are only comparing the convergence relative to ideal LD (b 1) rather than the exact rate or DKL value (see Appendix (A). The block methods converge slower than the full-gradient process, with the rate of convergence decreasing with more blocks. By comparing the expo- nents Theorems 0 (-229-11 and (-27 (-27,8-Xxdmlal Xdmiukk) we note that choos- ing X makes the two contrac- tions equal. Similarly, the exponent Theorem 2 for a contraction in itera- tions (-2,,3-1 Ak) suggests the choice block, this suggests that equating the total time per block should result in roughly equivalent tractions. Fig. 2b confirms this prediction by showing the same data after rescaling the x-axis by for each method, with the curves converging within sampling error. Block sampling therefore incurs an (b) slowdown in real time, similar to coordinate methods in optimization (without accounting for smoothness (Wright 2015)).
10
10
Black
10-3
10
Dac (pcl))
101
10p
ZUP
10-1
10-1
0.5
1.0
2.0
0.5
1.0
2.0
Time
Ic-6
Resealed Tine (a/ Block) Tc-6
(b)
Figure 2: Convergence in DKL. for varying block counts b with for b-BCLD and b-RCLD (a) versus simulated time and (b) versus cycles kb. The inset plot (a) shows the absolute difference between the RBLD and CBLD DKL values averaged over each block count.
iterations. Since the amount of time, spent per
Coode and data be found http:///wttt/p/////////////////a

---

Published as a conference paper at ICLR 2025
Our testing showed that all step sizes lead to the same convergence rate with respect to time (not shown). However, larger step sizes lead to larger decay whole problem cycles (b itera- tions), as shown in Fig. [a] This re- inforces the importance of per block sampling time for continuous coordi- nate methods. Finally, we perturb the similarity matrix Σ with component- wise variation Eij (1 + 61j), 8y ~ (0, A). Fig. 3b shows the im- pact on DKL convergence with increas-
16'
263
10
Lao20
Dasiota
10
Mo.10
40
10
15000
Cyck:
Time
1e-5
(a)
(b)
Figure 3: BCLD DKL convergence (a) versus whole-
problem cycles with varying block duration À and (b) ver- sus simulated time with varying multiplicative Gaussian perturbations.
ing perturbation strength. At A 0.6, E is no longer positive-defintte caus-
ing the iterate to diverge (not shown on plot). A E (0.1, 0.2, 0.3, 0.4, 0.5) satisfied Assumption 5 and were therefore stable (though biased), but = 0.6 did not, in line with discussion in the preceding section.
CONCLUSION
Findings: In this work, we prove novel bounds for Large Neighborhood Local Search (LNLS) sampling algorithms leveraging continuous Langevin diffusion, providing valuable information to device designers, potential DX adopters, and future analyses. Specifically, we
1. prove novel non-asymptotic convergence bounds for randomized and cyclic block selection strategies, finding that both methods produce identical convergence rates in KL-divergence.
2. provide probabilistic convergence bounds for LNI.S sampling using non-ideal analog de- vices, with biases expressed using practically measurable/estimable constants
3. validate theoretical results by numerical simulation, demonstrating @ the expected equivalence of cyclic and randomized strategies and @ the expected dependence of con- vergence rates on algorithmmproblem parameters.
Limitations: Assumptions and 5 provvdd useful bounds for many ML and optimization prob- lems over continuous domains. However, DX applications include discrete choice problems and/or significantly non-convex potentials, such as mixed integer programming. Future bounds necessarily involve more general assumptions than the 7-LSI class considered here. Analog accelerators also typically use low-precision (< 86) DACs and ADCs for input/output (Xiao et al.) (022), making studies of quantizated convergence/expeeted function gap critical for real-world applications.
technical limitation is the assumption of support over Rd. DXs operate in bounded subspaces such the unit circle (Inagaki et al. 2016) hypercube (Afoakwa et al. 2021). Future work applying
projected differential analysis (Cherukuri et al. 2016 Bubeck et al. 2018) is therefore needed.
In this work, we focused on the "inference" stage where the cou- pling parameters are fixed. For training, current usages DX systems update model weights in discrete time, either by the digital controller (Song al. 2024 by discrete step in the analog domain /Vengalam et al. 2023). It will be a boon to DX research to further develop thcories for the training regime where model weights become the end goal for dynamics.
Directions for Future Work:
Finally, this work focuses on a simplified LNLS framework, relevant to the dynamics- accelerated LNLS popular in literature (Sharma et al. 2022 Raymond et al.) 2023 Wu et al.) 2024). It leaves open the question whether additional digital steps, such as a Hatroooois-Hasting filter or replica exchange, could improve the non-asymptotic accuracy convergence rate.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by NSF under Awards No. 2231036 and No. 2233378; and by DARPA under contract No. FA8650-23-C-7312 Our thanks go Prof. Jiaming Liang for several fruitful discussions and helpful feedback on an early draft of this work.
REFERENCES
Richard Afoakwa, Yiqiao Zhang, Uday Kumar Reddy Vengalam, Zeljko Ignjatovic, and Michael Huang. BRIM: Bistable Resistively-Coupled Ising Machine. In 2021 IEEE International Sym- posium on High- Perfo-Pefoen Computer Architecture (HPCA), pp. 749-760, February 2021. doi: 10.1109/1PC551147.2221..000
ISSN: 2378-203X.
Ravindra K. Ahuja, Özlem Ergun. James B. Orlin, and Abraham P. Punnen. A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematiccs 123()):55-102 November 2002. ISSN 0166-218X. doi: 10.1006//0016--218x0000000000000
URL https:
w/www.sciencedi.ee...
com/ wttp://ccceeeeerrraaaaaaa///////
Maxwell Aifer, Kaelan Donatella, Max Hunter Gordon, Thomas Ahle, Daniel Simpson, Gavin E. Crooks, and Patrick J. Coles. Thermodynamic Linear Algebra, August 2023. URL http:
05660 urXiv:2308.05666 [cond-mat, physies:quant-ph)
Tameem Albash, Victor Martin-Mayor, and Itay Hen. Analog emrors in Ising machines. Quantum Science and Technology, 4(2):02LT33, April 2019. ISSN 2058-9565. doi: 10.1088/2058-9500
ab13ea. URL https::/ www.:doi..rggggo... 100.:/.1110000000000122 Publishing.
Publisher: IOP
Dagur Albertsson and Ana Rusu. Ising Machine Based on Bifurcations in a Network of Duffing Oscillators. In 2023 IEEE International Symposium Circuits and Systems (ISCAS), pp. 1-5, Monterey, CA, USA, May 2023, IEBE, ISBN 978-1-66545-10 109-3, doi: 10. 1597SC 2023.10181810
ieee http:///ww.......ooooooooooeetta
Manuel Arnese and Daniel Lacker. Convergence of coordinate ascent variational inference for log- concave measures via optimal transport, April 2024. httpp://t//a 20b.
08792 arXiv:2404.08792 [cs, math, stat].
Mohammad Khairul Bashar and Nikhil Shukla. Designing Ising machines with higher order spin interactions and their application in solving combinatorial optimization. Scientific Reports, 13 (1):9558, June 2023. ISSN 2045-2322. doi: 10. 100100008811118---3--363333
URL https: Publisher: Nature Publishing
//www. www.nature.c. com/ wtt.///aaaatttseeeeoooooo
36531
Group.
Roland Bauerschmidt and Thierry Bodineau. very simple proof of the LSI for high temperature spin systems. Journal of Functional Analysis, 276(8):2582 2588, April 2019. ISSN 0022- 1236. doi: jfa 2019.01.07.. URL https:: / www.w//wws...mm. sci encedi rect. wwm sc ence/
article/pi http:///pi/00022222222 93300277
Amir Beck and Luba Tetruashvili. On the Convergence of Block Coordinate Descent Type Methods. SIAM Journal on Optimization, 23(4):2037 2060, January 2013. ISSN 1052-6234, doi: 10.1 1337/ 120887679. httpt:tt////pptt Society for Industrial and Applied Mathematics.
siam. 02t0///01100011171116677777
Publisher:
Anirban Bhattacharya, Debdeep Pati, and Yun Yang. On the Convergence of Coordinate As- cent Variational Inference, June 2023. URL http:://axxi arXiv:2306.01 122 [cs, math, stat].
01122
François Bolley and Cédric Villani. Weighted to transportation inequalities. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 14, pp. 3-525, 2005.
inequalities and applications
Jérôme Bolte, Aris Daniliidis, Olivier Ley, and Laurent Mazet. Characterizations of tojasiewicz inequalities: subgradient flows, talweg, convexity. Transactions of the American Mathenatical Society, 362(6):3319-3366 2010.

---

Published as a conference paper at ICLR 2025
Michael Booth, Steven P Reinhardt, and Aidan Roy. Partitioning Optimization Problems for Hybrid Classical/Quantum Execution. Technical report, D- D-Wave, 2017.
Robin Brown, Davide Venturelli, Marco Pavone, and David E. Bernal Neira. Accelerating Contin- uous Variable Coherent Ising Machines via Momentum, January 2024. URL http://arxxxii.
org/ (tce/bs/2200 2401 12135 1xXiv:2401122133 [quant-ph].
Sébastien Bubeck. Ronen Eldan, and Joseph Lehec. Sampling from Log- Distribution with Projected Langevin Monte Carlo. Discrete Computational Geometry, 59(4))757-783, //dot .tt.////oooorr////o////o///
June 2018. ISSN 1432-0444.
doi: 10. (007/s00444-001-9999)
10.1007/500 018 - 9992-1
Connor Bybee, Denis Kleyko, Dmitri E. Nikonov, Amir Khosrowshahi, Bruno A. Olshausen, and Friedrich T. Sommer. Efficient optimization with higher-order Ising machines. Nature Commu- nications, 14(1):6033, September 2023. ISSN 2041-1723. doi: 10.
41214
Publisher: Na-
ture Publishing Group.
Martin Chak, Nikolas Kantas, and Grigorios A. Pavliotis. On the Generalized Langevin Equa- tion for Simulated Annealing. SIAM/ASA Journal on Uncertainty Quantification, 11(1):139- 167, March 2023. doi: 10.1 10.1137/11M1462999
URLbttpss /ttpp//pssss./////// si am. org/do/ full/ Publisher: Society for Industrial and Applied Mathematics.
10. 11.1/27/ 429970
Ashish Cherukuri, Enrique Mallada, and Jorge Cortés. Asymptotic convergence of constrained pri- mal-dual dynamics.. Systems & Control Letters, 87:10-15, January 2016. ISSN 0167-6911. doi: 10.006. URL https: //ww: sci encedi com..ccccccccccccccceccecee
att.icleepp.1/501776911111
Sinho Chewi. Log-Concave Sampling. March 2024. URL http:://ccewiiiinoo...iiit/
1o/ /////ain.... pdE
Sinho Chewi, Murat A. Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev, December 2021. /RRlittp://arxiv
org/abs/2112 12662 arXiv:21 10.::212.1100 12.66662 [math, stat].
Tzuu-Shuh Chiang, Chii-Rues Hwang, and Shuenn Jyi Sheu. Diffusion for Global Optimization in R". SIAM Journal on Control and Optimization, 25(3):737-753, May 1987. ISSN 0363-0129. doi: 10.1 10.1137/032504.. URL https: / /eppss..s.... s aim.. wwt.ooogg/oooooo 00. 1137 Publisher: Society for Industrial and Applied Mathematics.
Arnak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- conccve densities, December 2016. http: http://aaxxiv....aaa//. allp:///bb/11/....//. 1412. 7392 arXiv: 1XXV::142.77392 [math, stat].
Joni Dambre, David Verstraeten, Benjamin Schrauwen, and Serge Massar. Information Processing
Capacity of Dynamical Systems. Scientific Reports, 2(1))514, July 2012. ISSN 2045-2322. doi: 10.1038/srep005144 URL https:/ nature www.:aattur..ccmmaaaaaaaaeeeeeee lisher: Nature Publishing Group.
Pub-
Zhiyan Ding and Qin Li. Langevin Monte Carlo: random coordinate descent and variance reduction. The Journal of Machine Learning Research, 22(1):205:911222559922, January 2021. ISSN
1532-4435.
Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J. Wright. Random Coordinate Underdamped Langevin Monte Carlo, October 2020. URL http:://arctv.oog/aab///// 11366 arXiv:2010.1 1136 [cs, stat].
Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen Wright. Random Coordinate Langevin Monte Carlo. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. PMLR, July 2021. URL htRp/tttss////rceeiiinne mll.sssmm.lr www.st..rssssiieese //ig///anaa..a.aa// .tml ISSN: 2640-3498.
12

---

Published as a conference paper at ICLR 2025
Mikhail Erementchouk, Aditya Shukla, and Pinaki Mazumder. On computational capabilities of Ising machines based on nonlinear oscillators.. Physica D: Nonlinear Phenomena. 437:133334, September 2022. ISSN 01672789. doi: (0.1016ff.hhysd22022. 133334..
org/abs / 05. 07591 arXiv:2105.0755 [cond-mat, physics:physics,
Tyler Farghly and Patrick Rebeschini. Time-independent Generalization Bounds for SGLD in Non-convex Settings, November 2021. URL
12876
arXiv:2111.12876 [cs, math, stat].
Ryan Hamerly, Takahiro Inagaki, Peter McMahon, Davide Venturelli, Alireza Marandi, Tat- suhiro Onodera, Edwin Ng, Carsten Langrock, Kensuke Inaba, Toshimori Honjo, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Shoko Utsunomiya, Satoshi Kako, Ken-ichi Kawarabayashi, Robert L. Byer, Martin M. Fejer, Hideo Mabuchi, Dirk Englund, Eleanor Rieffel, Hiroki Take- sue, and Yoshihisa Yamamoto. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Science Advances, 5(5):eaau0823, May 2019. doi: 10. aa002aa URL bttps::: /www wttp:./ccii..... sccieece, org/ fulli/ffuu////////// 1126/ aau0823 Publisher: American Association for the Advancement of Science.
Zhezhi He, Jie Lin, Rickard Ewetz, Jiann-Shiun Yuan, and Deliang Fan. Noise Injection Adap- tion: End-to-End ReRAM Crossbar Non-ideal Effect Adaption for Neural Network Mapping. In Proceedings of the 56th Annual Design Automation Conference 2019, DAC 19, pp. 1-6, New York, NY. USA, June 2019. Association for Computing Machinery. ISBN 978 1 14501-1-5553-55511 37781111 6781.
doi: 10. 111131167111337777 33377770. URL httpt:tt//// //dl:://dllr acm. org/ doi 010.://111111/11111111
3370
Geoffrey E Hinton, Simon Osindero, and Yee-Whye Teh. A fast learning algorithm for deep belief' nets. Neural computation, 18(7):15271155, 2006.
Toshimori Honjo, Tomohiro Sonobe, Kensuke Inaba, Takahiro Inagaki, Takuya Ikuta, Ya- suhiro Yamada, Takushi Kazama, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Ken-ichi Kawarabayashi, and Hiroki Takesue. 100,000-spin coherent Ising machine. Science Ad- vances, 7(40):eab00952, September 2021. doi: 10. 10.11220 sciience wwtpo//////ooo//////// tion for the Advancement of Science.
httpssts::/// Publisher: American Associa-
(0112//cciaaae abh0
Fangjun Hu, Gerasimos Angelatos, Saeed A. Khan, Marti Vives, Esin Türeci, Leon Bello, Gra- ham F. Rowlands, Guilhem Ribeill, and Hakan E. Türeci. Tackling Sampling Noise Physical Systems for Machine Learning Applications: Fundamental Limits and Eigentasks. Physical Re- view X, 13(4):041020 October 2023. ISSN 11600-3088888 doi: 10. 10.11000yy 13.044400.... URL wwt.//yysee....... 041020
https: 1iwkiiin...... atw.appp...p.opppapp
Kensuke Inaba, Yasuhiro Yamada, and Hiroki Takesue. Thermodynamic quantities of two-
dimensional Ising models obtained by noisy mean field annealing and coherent Ising machine,
February 2023. URL htt.::tttt///iiii org/ abs/ 220///2322a0 01454 arXiv:2302.01454 [cond- mat, physics:quant-ph)
Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe, Shuhei Tamate, Toshimori Honjo, Alireza Marandi, Peter L. McMahon, Takeshi Umeki, Koji Enbutsu, Osamu Tadanaga, Hi- rokazu Takenouchi, Kazuyuki Aihara, Ken-ichi Kawarabayashi, Kyo Inoue, Shoko Utsunomiya, and Hiroki Takesue. A coherent Ising machine for 2000-node optimization problems. Sci- ence, 354(6312);603 606, November 2016. doi: 10. aaaaeeiiiinnee.a444..... 7/ 7/ /wwww.w. science...cccc...o..coo frgg/ooi/fullie 1/1. wttp//ccence..o /tt////ciennceeaa22233. aah4243
URL, https: Publisher: Ameri-
can Association for the Advancement of Science.
Richard Jordan, David Kinderlehrer, and Felix Otto. The Variational Formulation of the Fokker- Planck Equation. SIAM Journal on Mathematicall Analysis, 29(1):1-17, January 1998. ISSN 0036-14100 1095-7154. doi: 10. 10.11377550361140996333333 O
URL http::/epubs.stt
David J. Earl and Michael W. Deem. Parallel tempering:
Theory, applications, and new per- spectives. Physical Chemistry Chemical Physics, 7(23):310-33166. 2005. doi: 10.1039/ B509983H. URL
rac, http:aass../////aatteetttarrttt.
cpp/550998hh
Publisher: Royal Society of Chemistry.
13

---

Published as a conference paper at ICLR 2025
Scott Kirkpatrick. Optimization by simulated annealing: Quantitative studies. Journal of Statisti- cal Physics, 34(5):975 986, March 1984. ISSN 1572-9613. doi: 10.1007/BFF1100955.. URL
atttps://dee wtt.:/oorr/....00/B0PL.....
Michael Klachko, Mohammad Reza Mahmoodi, and Dmitri Strukov. Improving Noise Toler- ance of Mixed-Signal Neural Networks. In 2019 International Joint Conference on Neural Networks (IJCN), pp. 1-8, July 2019. doi: 10.1109/UCNN.2009 8851966. URL https: ieee.
www.mmettooooootooooccccm /885 966
ISSN: 2161-4407.
Se Yoon Lee. Gibbs sampler and coordinate ascent variational inference: A set-theoretical review. Communications in Statistics Theory and Methods, 51(6):159-1168,, March 2022. ISSN 0361-0926. doi: 11180003610222.2211.222929
URL https:/
doi. orq/l0.///.... 1080 00000/033109220000 2021 1921214 Publisher: Taylor & Francis .eprint:
Lei Li and Yuliang Wang. A sharp uniform-in-time erro estimate for Stochastic Gradi- ent Langevin Dynamies, October 2022. URL http::/ http:://aaxxv.oorraa///22220
arXiv:2207099304 [cs, math, stat].
Yun Long, Xueyuan She, and Saibal Mukhopadhyay. Design of Reliable DNN Accelerator with Un-reliable ReRAM. In 2019 Design, Automation & Test in Europe Conference Exhibition (DATE), pp. 1769 1779-1774, March 2019. doi:
URL (RLhttps::/ ISSN: 1558-1101
ieee. http:////..at.aaaaaaattrttttttta
Andrew Lucas. Ising formulations many NP problems. Frontiers Physics, 2, 2014. ISSN 2296-
424X. URL httpps:/wwwt frontiersin wwg./rtiilee.eeeoooooooooo htt.://nw...iiii..rrrrooooooeeee 3389/
3389/ Ephy 2014.
00005
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I. Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):20881- 20885, October 2019. doi: 10. 10.1073/pmas. 18200031 URL https: /www, pnas. org/ Publisher: Proceedings of the National Academy
doi/abs/10. 1073/ wwt.//pas.... 820000116 of Sciences.
Denis Melanson, Mohammad Abu Khater, Maxwell Aifer, Kaclan Donatella, Max Hunter Gordon, Thomas Ahle, Gavin Crooks, Antonio J. Martinez, Faris Shahi, and Patrick J. Coles. Thermody- namic Computing System for AI Applications, December 2023. URL
abs/2313 04836 arXiv:2312.04836 [cond-mat].
Beren Millidge, Tommaso Salvatori, Yuhang Song, Rafal Bogacz, and Thomas Lukasiewicz. Pre- dictive Coding: Towards Future of Deep Learning beyond Backpropagation', February 2022.
URL httpt:tttaxxiv.coo wwwpsxivv..rr/eoooooooooo abs/ 09467 arXiv:2202.09467 [cs].
Nacimeh Mohseni, Peter L. McMahon, and Tim Bymnes. Ising machines as hardware solvers of com- problems Nature Reviews Physics, 4(6))363-379, June 2022. ISSN 2522- binatorial optimization problems.
5820. doi: 02200000444222540200000000000000 URL https: www.wwww...oomm www.:/w.......e.mt.wt..twwwww nature. cww/ artnarrrtccees//// Number: 6 Publisher: Nature Publishing Group.
0122544-022-00400-00
Yu. Nesterov. Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems. SIAM Journal on Optimization, 22(2):341 i am..m....
January 2012. ISSN 1052 6234. doi: 10.1 Pub-
100802001. htt.:::tt/////ttt
lisher: Society for Industrial and Applied Mathematics.
Edwin Ng, Tatsuhiro Onodera, Satoshi Kako, Peter L. McMahon, Hideo Mabuchi, and Yoshi- hisa Yamamoto. Efficient sampling of ground and low-energy Ising spin configurations with coherent Ising machine. Physical Review Research, 4(1):013009, January 2022. ISSN 2643- 1564. doi: 10. 4.wp:Phyy.ReeReeeec...........3 1103 11C0:PlyskeerReeeaccc........ 013009
URL/attp:://Iin/ axtp
Otto and C. Villani. Generalization an Inequality by Talagrand and Links with the Logarith- mic Sobolev Inequality. Journal of Functional Analysis, 173())361-400, June 2000. ISSN 0022-1236. doi: 10. 10..0066ff...11999995555 1999.95579 URL https: www. wcwencedirect.ccom
sci acciemee//rriiia/////01122333333
14

---

Published as a conference paper at ICLR 2025
Yury Polyanskiy and Yihong Wu. Wasserstein Continuity of Entropy and Outer Bounds for Inter- ference Channels. IEEE Trans. Inf. Theor. 62(7):3992 July 2016. ISSN 0018-9448, doi: 10.1199/IT.201125666600 1tt////e/////....oo0..0000111111 25626630
Sayantan Pramanik, Sourav Chatterjee, and Harshkumar Oza. Convergence Analysis of Opto- Electronic Oscillator based Coherent Ising Machines, December 2023. URL [xttp://axxxi
brg/abs/2311 04290 arXiv:2312.042900 [quant-ph].
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via Stochastic Gradient Langevin Dynamics: nonasymptotic analysis. In Proceedings of the 2017 Conference on Learming Theory, pp. 1674-1703. PMLR, June 2017. URL httts::/pproceedii ISSN: 2640-3498.
m1 r. wt..peas//v//rraiinssssss
7a httll
Jack Raymond, Radomir Stevanovic, William Beroudy,, Kelly Boothby, Catherine McGeoch, An- drew J. Berkley, Pau Farré, and Andrew D. King. Hybrid quantum annealing for lar lattice-structured problems. ACM Transactions on Quantum Computing, 4(3):1-30, September 2023. ISSN 2643-6809 2643-6817 17, doi: 10.1145/3579368. 2202. 03044 arXiv:2202.0304 [quant-ph].
Benjamin Scellier and Yoshua Bengio. Equilibrium Propagation: Bridging the Gap between Energy- Based Models and Backpropagation. Frontiers Computational Neuroscience, 11, May 2017.
ISSN 1662-5188.
doi: 11.338/ficom.2211.00022
URL hatps: www. Frontierssi
org/articless 3389/ fncom. 2017. 00024, Publisher: Frontiers.
Benjamin Scellier, Maxence Ernoult. Jack Kendall, and Suhas Kumar. Energy-based learning algorithms for analog computing: comparative study. Advances in Neural Information Processing Systems, 36:52705-52731, December 2023. URL
https: fttts:://prcceeding neurii.pp...................... a 35550004544444777775544444444443
fi http:ppprr..llleppppp///////////
Anshujit Sharma, Richard Afoakwa, Zeljko Ignjatovic, and Michael Huang. Increasing ising ma- chine capacity with multi-chip architectures. In Proceedings of the 49th Annual International Symposium Computer Architecture, ISCA '22, pp. 508-521, New York, NY, USA, June doi: 10. 145344543
2022. Association for Computing Machinery, ISBN 978-1-4503-8610-4 3527414. URL https://dl acm. org /wo/ 11.1...1144440000 351749966555744 3527414
Anshujit Sharma, Matthew Burns, and Michael C. Huang. Combining Cubic Dynamical Solvers with Make/Break Heuristics to Solve SAT. In Meena Mahajan and Friedrich Slivovsky (eds.), 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), vol- ume 271 of Leibniz International Proceedings in Informatics (LIPlcs), pp. 25:1 1-:221,, Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz- für Informatik. ISBN 978-3-95977- 286-0. doi: vo Soolttexxte2223311444
URL ISSN: 1868-8969.
Ruibing Song, Chunshu Wu, Chuan Liu, Ang Li, Michael Huang, and Tong Geng. DS-GL: Advanc- ing Graph Learning via Hamnesiing the Power of Nature within Dynamic Systems. Technical Re- port MANL-SSA1967611 Pacific Northwest National Laboratory (PNNL), Richland, WA (United States), August 2024. URL httph:ts///// www. osti wwwp////w..o///21...332
Menachem Stern, Daniel Hexner, Jason W. Rocks, and Andrea J. Liu. Supervised Learning in Physical Networks: From Machine Leamning to Learning Machines. Physical Review X, 11(2): 021045, May 2021. doi: 10. 10.1 1t5510..103/PaysRev...
URL https: pttp:://ling //inkkn,,..////// aps. o Publisher: American Physical Society.
021045
Ryan J Tibshirani. Dykstra' s Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions. In Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL https: http:::://pppcccpeeeeee www.:/ewwweddie.e.eeeeeeeeeeeeee neurips. http/ppper/2117/haae 3al -0- html
Hayato Asshjima-MWesigwwe Christian F. A. Negre, and Susan M. Mniszewski. Graph Partitioning using Quantum Annealing on the D-Wave System. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, PMES' 17, pp. 22-29, New York, NY, USA,
15

---

Published as a conference paper at ICLR 2025
November 2017. Association for C 3149526.3 149531. 149531.
doi: 10.1145/
acm. http://.......rr////////11111131
Santosh Vempala and Andre Wibisono. Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices. In Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc.. 2019. URL http:::t//////.a htt.tppp://ppoccceeiiniioooo bash/65a99bbe 2dd www.ssstttttttttttttttt.....a... Abstract. html
neurips wttpp/ppppppppppppppee/
Uday Kumar Reddy Vengalam, Yongchao Liu, Tong Geng, Hui Wu, and Michael Huang. SUP- PORTING ENERGY-BASER LEARNING WITH AN ISING MACHINE SUBSTRATE: A CASE STUDY ON RBM. In Proceedings of the 56th Annual IEEE/ACM International Sym- posium on Microarchitecture, MICRO '23, pp. 465-478, New York, NY, USA, December 2023. Association for Computing Machinery. ISBN 9798400703294, doi: 10.1 00.11457361342436614155
URL https: acm. org/ wogg/doi/iee doi/10..0000001 1et..111//36144..251 3614315
Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. Split-and-Augmented Gibbs Sam- Aoe-AAppitatioon Large-Seur Scale Inference Problems. IEEE Transactions on Signal Process-
ing. 67(6):1648-1666 1661, March 2019. ISSN 1941-0476. doi: 10.1109/TSP22111288888
URL https: /eeeeeeeeeppppppeeeeeeeeeeeeeeee ore. ieee. absttrsttttttttte/./ ata.btraat//ocomeee//665555555 Confer- ence Name: IEEE Transactions Signal Processing.
Maxime Vono, Daniel Paulin, and Arnau Doucet. Efficient MCMC sampling with dimension- free convergence rate using ADMM-type splitting. The Journal of Machine Learning Research, 23 11::25:1100-25: 166, January 2022. ISSN 1532-4435.
Tianshi Wang and Jaiject Roychowdhury. OIM: Oscillator-based Ising Machines for Solving Com- binatorial Optimisation Problems, March 2019. URL
07163 arXiv:1903.074 [cs].
Zhe Wang, Alireza Marandi, Kai Wen, Robert L. Byer, and Yoshihisa Yamamoto. Coherent Ising machine based on degenerate optical parametric oscillators. Physical Review A, 88(6):063853, December 2013. doi: 10. Sew.s/PhyseeeA.........
aps org/doi/ Publisher: American Physical Society.
10. 10.1103/PhysReev 88 063853
Andre Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as composite optimization problem. In Proceedings of the 3/st Conference On Learning The- ory, pp. 2093-3027. PMLR, July 2018. URL
mlr htw.p//.ssmmm......////s..
wi wibisonol8a.hug html
ISSN: 2640-3498.
Stephen J. Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3-34, June 2015. ISSN 1436-4646.
doi: 10. 10.10077110107-015-009-3. URL
1007/ 1007/s10107-015-111
Chunshu Wu, Ruibing Song, Chuan Liu, Yunan Yang, Ang Li, Michael Huang, and Tong Geng. Extending power of nature from binary to real-valued graph learning in real world. In The Twelfth International Conference on Learning Representations, 2024.
T. Patrick Xiao, Ben Feinberg, Christopher H. Bennett, Venkatraman Prabhakar, Prashant Saxena, Vineet Agrawal, Sapan Agarwal, and Matthew J. Marinella. On the Accuracy of Analog Neu- ral Network Inference Accelerators. IEEE Circuits and Systems Magazine, 22(():26 (00)26648,, 2022. ISSN 1558-0830. doi: 10.
URL pttttss://eeeeee lore. ieee.
orgg/dccuent// http://0000000//////mmbbrrrrrrr 0010010011000000000 80230t0022 Conference Name: IEEE
Circuits and Systems Magazine.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization, October 2020. URL http:///axiv..rt
abs/ 06618 arXiv:1707.06611 [cs, math, stat].
Ying Zhang, Ömer Deniz Akyildiz, Theodoros Damoulas, and Sotirios Sabanis. Nonasymp- totic Estimates for Stochastic Gradient Langevin Dynamics Under Local Conditions in Non- convex Optimization. Applied Mathematics & Optinization, 87(2):25, January 2023. ISSN 1432-0606. doi: 010077/000255002--999333 000245-022-099322
URL Attps: //t/:///....// /ttp:/::///a1.../1111000000
16

---

Published as a conference paper at ICLR 2025
Yiqiao Zhang, Uday Kumar Reddy Vengalam, Anshujit Sharma, Michael Huang, and Zeljko Ignja- tovic. QuBRIM: A CMOS Compatible Resistively-Couplle Ising Machine with Quantized Nodal Interactions. In Proceedings of the s1 IEEE/ACM International Conference Computer- Aided Design, ICCAD '22, pp. 1-8, New York, NY, USA, December 2022. Association for Computing Machinery. ISBN 978-1 978-1-4503-9217-4
doi: 10.1145/5508352.554444. URL https://al. acm. www.aac.......o....eooeo./oooooe wtt.a//......../...110/333322230
Yuchen Zhang, Percy Liang, and Moses Charikar, A Hitting Time Analysis of Stochastic Gradient
Langevin Dynamies. Proceedings of the 2017 Conference on Learning Theory, pp. 1980-2022. PMLR, June 2017. httppt//: /ttps:///preee///e/ ngs ml prwss/ressss... / v65 zhangl 7b. html
ISSN: 2640-3498.
17

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY MATERIALS
Here we provide proofs and explanations of experimental methods. Additionally, we apply our analysis to bound DKL for discrete-time variants of RBLD and CBLD (RBLMC and CBLMC), For clarity of notation, we omit the 3 subscript when referring to the target distribution _ ng..
A EXPERIMENTAL METHODS
A.1 DIFFUSION SIMULATION
The purpose of experiments is "proof-of-concepp"" hence foeus demonstrating @ the expected performance equivalence between RBLD and CBLD, the significance of stepsize choice, and @ the impact of stochastic perturbations.
We simulate I Langevin SDEs using an Fuler-Maruyama integration scheme with time step size of 1.6 10-11 seconds. Block diffusions simulated for fixed number of steps, then the block is switched either cyclically or randomly, depending on the algorithm. All code is implemented in PyTorch and was run on desktop system using an i9-13900k with 64 GB of RAM and RTX 4090 GPU. Our simulator, plotting code, and data is publicly available at https: /gtthu..
htmm/ur-acca/slcccaare
We take the resistively coupled BRIM architecture from Afoakwa et al. (2021) ) with the Langevin perturbations proposed by /Sharma al. (2023) as our baseline DX. The BRIM architecture is more
easily extensible to general classes of real-valued functions (Sharma et al. 2023 Song et al. 2024
Wu et al. 2024) than oscillator-bel based DXs (Wang & Roychowdhury 2019 Inagaki et al. 2016). motivating the selection.
We model the device using 310 kOhm resistors and 50 capacitors, leading to an RC time constant of 1.55 x 10-$s and an effective step size of 1.55 x 10-1's s, which we use plot total estimated DX time. These circuit parameters are comparable to those proposed in literature (Afoakwa et al. however different device parameters will simply rescale the x-axis.
2021 Zhang et al. 2022
A.2 TARGET POTENTIAL
As stated in the main text, we choose a Gaussian target measure to obtain a direct estimate of convergence rather than using proxy statistical observables, done in Ding & Li (2021). The d = 50 Gaussian used to produce Fig. 3 was generated using the following procedure:
1. Generate a 50 x 50 matrix Σz1 with elements Unif[ 5]
2. Make the matrix symmetric by setting V = - + (2)))
3. To make Σ, positive definite, set Σz --1 + 1.2 150
The resulting matrix is symmetric and positive-definit, making it a valid similarity matrix. We then invert Σ-1 obtain the target covariance matrix Σ,, We choose [-5, 5] as the distribution to test a larger range of perturbation strengths A E [0.1, 0.4), as the W2 diverged much earlier (A < 0.2) with a uniform [-1, 1] distribution.
As our focus is sampling rather than optimization, we set 3 1 for simplicity. We also assume the Gaussian mean is zero, making the target distribution
xxx)
1x 1
A.3 SAMPLING PROCEDURE
We randomiy initialize N- 1 states and evolve them in parallel with equivalent block selections. Every 30 iterations (time !) we compute the empirical covariance matrix for time Σ, and the em- pirical mean u, to obtain the estimated Er, = (u,,, Σ,). We then compute the similarity to the target Gaussian. For completeness compute both W2 and DKL using
W (14, Met. E2)) || 2 + Tr E, En
2
E. EE,,, Σn
18

---

Published as a conference paper at ICLR 2025
for W2 and PyTorch library function for DKL, which computes (KL Σ₂)) 2 det Ei
log det Σ d Tr Ei] + +u MnE=-1u ut
B REVIEW OF LANGEVIN DYNAMICS
In this section we review the traditional proof of Equation 2 as presented by Vempala & Wibisono (219); Chewi (2024). Proofs in succeeding sections follow similar processes, making brief review useful for establishing context.
Recall that the LD SDE is given by
dx (())dl + 223-IdW,
The Tokker-Planck equation (FPE) for Equation is given by (Vempala & Wibisono/ 2019 Jordan al. 1998)
0p = Mi
[e Vf(()
Ōt
where Pe is the law of æ(t). For convenience, we will abbreviate du: as Deple. Note that the right hand side of the FPE can be equivalently expressed as B- v2 Mr + V [Me V [x))
= B - [ + 3p4 V f [x)
= 3
1/ V In /4 V 1
(8)
1t TB
[p+ In In
The time derivative of the KL-divergence is given by
0 (KL((H))))T) = 0 / (x(x) In Me(x)
TT(x) dx
= - [(o In Melx) TT(x) + +e(x)a (x())) dx
TT(T)]
The second term is equal to zero, since
f (r(())0 In [e(x) dx = f (rpi(t)do= = (e(x)dr== =
\イ(x)
Then, applying Equation 8 and integrating by parts
a DKL(HeT))) = (0)))(z0) In (e(x)
dx (T)
/ 3 3-'V . [nr(x) Me(x)
(x) dx
(x)
[T((r)
ff 8-1 m |n (x)
Me (xx dr
In
TT(x))
T.g (x)
=-f 3-1 14: (x))
pdr = - 3 FI (1)
(x)
where FI( is the relative Fisher information of μ relative TT. TT(2)) Af(x) satisfies log-Sobolev inequality then
DKL. (() < 2n FT(ull(TT)
Combining the LSI with Equation
B we obtain
0 (Ke((L] 3 (I(el(TT) S 27,3 DKL (He (T)))
which implies exponential convergence of (KI,(M
(Mel -2 (MolITT)
19

---

Published as a conference paper at ICLR 2025
C RANDOMIZED BLOCK LANGEVIN DIFFUSION (RBLD)
In this section provide proofs relating Randomized Block Langevin Diffusion (RBLD, the focus of the main text) and a time-discretized version, Randomized Block Langevin Monte Carlo (RBLMC). RBLMC was previously introduced in Ding et al. (2021) as a coordinate-wist scheme, however we examine block partitions. Moreover, our results using 7-LSI target measures are more general than the strongly log-concave convergence results given in that work. For simplicity, we use the shorthand 22 - rtt) throughout.
Algorithm gives the structure of RBLD/RBLMC sampling, where ø {oi..... is discrete probability mass function over coordinate block indices.
C.I CONTINUOUS TIME ITERATION
Algorithm Randomized Block Langevin Dynamics (RBLD)
1: procedure RBLD(rg E dom(f), Block Distribution over {Bi, Bo}, Step Size Set À
R$b
2:
for k: 2 do
3: Choose ~ & and set tx+1 = tx + As
4: Sample:
24e |
Abi1 U.Vf(z)dt+ (x 1.M. U1
Jta+1
5: end for
6: end procedure
We first consider the when each diffusion occurs in continuous time. For single iteration, can formulate the evolution of the system by the following Itô SDE:
dx U (f(r)dt v23-IaW.)
To prove continuous-timg descent in K L-iiveereee,,, combine standard Langevin gradient flow arguments with methodology inspired by Ref. Vempala & Wibisono (2019) when considering ex- pectation terms.
C.2 FOKKER-PLANCK EQUATION
Let d4 be the law of Ie, and let Majo be the measure jointly conditioned @ on the state at time 0 and @ the choice of block Bg- Within a single step, Mejo will obey the Fokker-Planck continuity equation
O.po = Tr 2 + V (P
we were tracking the diffusion over a single block, we would take expectation over the starting state zo while conditioning the block index. However, as discussed in the main text, we take "meta-Eulerian" perspective. Instead of tracking one block diffusion, our approach finds the average behavior of ensemble of diffusion processes, each independently sampling their blocks according to á. We therefore take expectation over both vp and B₁ to derive the change in the "ensemble" measure 14.
Therefore we have
= = Uy EVV (M)oU>V((T))
Where have defined Ug A (01 (bbb) Rdxd
20

---

Published as a conference paper at ICLR 2025
Let be the joint law of (æ0, B&). Note that Me (x) B&) = (i(rs))( Bxl
(r(oe))(zolze BR (B)u(
(o(ze)u( B (B)))
= -e(ze)u(zo)ze Bx)
Then we can express the second term as
E (14 (ltooVVV(()))
V
Me ( (J) i)d
1=1
Φi / [lle:JU ()dzo)
V (2(I)))
since
Therefore, the FPE of the "meta-Eulerian" " RBLD process is
Sep = 1 v nrl + V (HiUs V((.))
Note that the we can use the identity f (x) = 3 ' log to re-express the FPE as
0:4 = V Mu Pt
C.3 KL-DIVERGENCE CONTRACTION
Lemma 3.
DKL (MelIT) S (follTTe 23-1 "Amin
Proof. The proof follows conventional analyses of Langevin diffusion processes, e.g., see |eepala Wibisono (2019): Chewi (2024); [Chewi et al. (2021). However, we complete the proof anew for completeness, as well to show the differences with baseline LD.
With the time evolution measure, we can now express the time evolution KL-divergence
0 (KI.(uel| = a, / m (1(x)) log
Pr da
π [x)
= / 0.(u)(z) log
(x)
do
π Txx)
Me(x) dr + / anpu(o)dd Txx)
= =- (z)
where the second is equal zero since
/ @rrn(s)dds 0. [1(x)do 0,(1] 0.
Using Eqn. 9 we then have
O DKL = /IV (8-1((o log 4) } log
Me(z)
dx.
π TTx))
Through integration by parts, we obtain
O (KI.(uellT) = -B-1 / UUate V log
Mt V log
Me(x)
dr
π Txx))
( ( (UoV log
(e(z)
= = 'Bu
V log
n (x:
21

---

Published as a conference paper at ICLR 2025
Ug is positive-defintte with minimum eigenvalue Omin. therefore
0, DKL (uel=)) 3- Ex ( log
14 V log
Me(o) xt ((x)
11 - -8-1 Umin
Ht 2
log π
7
=- 9- f F FT [|>]]//]]] S 2,3
Aomin DKI. ((+lITT)
where the last inequality utilizes the y-LSI. Here we highlight a principle difference between LD and RBLD analysis. In LD, we have the "de Brujin identity"
ae (Mell( = 22 1 "FF (HellTT.
However, for RBLD we have "de Brujin inequality"
0, (Keel -
We now integrate up Ag- Since this step size depends on the choice of k. we take expectation of (KL (TT) where to Di=1 dR
E (DDL((a||= S Ble --8 22 (RE
or deterministically
(HE(HI] 2e-215 Amin (KL(HE-11(TT
Expanding the inequality k times yields the result.
C.4 RCLMC: EULER-MARUYAN DISCRETIZATION
We now extend our analysis to discrete-time Randomized Block Langevin Monte Carlo (RBLMC), shown in Algorithm. While the continuous-time diffusion can be implemented dynamical
Algorithm 3 Randomized Block Langevin Monte Carlo (RBLMC)
1: procedure RBLMC(ro dom(f), Block Distribution & over [B1, ..., Bb}. Step Size Set À
Rb
2:
for > do
3: Choose i ~ Φ. sample şh ~N10 1d)
4: Set:
x
x² -UUNV(((*))
5:
end for
6: end procedure
hardware, digital applications require an error bound in the discrete-setting, The following derivation closely follows the methods of Vempala & Wibisono (2019) by modeling the divergence of the discrete scheme from a continuous-tine interpolation. To simplify constant terms, we take / for this section.
We now consider the SDE
dr U + V2dw,)
where zo is the initial state. The SDE has the solution
Fr 3o + Ux[-V/(x0)++ V21g.)
for [0, An] and & NO, ). Conditioned the initial state zo and the choice of i, we have the FPE
0. 2 Melk.no + V Melke,nn (fzo(()).
Taking expectation over both sides (as previously) yields
U. Ozp = Tr(U's V Mukkzol + V E (Vzo)))).
22

---

Published as a conference paper at ICLR 2025
Again noting that the choice of block and the initial state 2o are independent, express the expectation as
U
Σ
i=1
Note that while z0 and o, independent random variables, they are not independent when condi- tioned on 24. We then have
a1) 20) i)
= (( ilzx)) ((xx)u((zo In 1)0 (rrr)) an, 1)
Then
Σ di /
b
= Σ Φb /
b
= u(zz) / ((
-mUbB(Vs(Zo))
We then have the following FPE
0, = Tr(U V m V [(t)
=V [U vu, + [(zo)(
Combining our previous argument with the analysis of Vempala & Wibisono 2019), we have
[+(2)) log Me(x) Tσx))
O (KI((ellT) 0:
dx
(og (x(x). Txx)
dx
log (e(x) de ((x)
UU 14 + u U HUUU
/
V log Me(x)) (πx)
Us V. +
dr
/
UOUI VOHIVIOBH Uott V log μ4 V log n + H: H.U, V log
Mc(x)
dr
T(x))
/
(UOJI V log
HE + PU.EE V (xxo) - ()(')))], log [x(z)
dx
(()))
(x) (x)
12]+ + E U 1/2 [V (z(o)),, U 1/2 v log Me(x))
-EIIUU V log
T(x)
where we have used the fact that Us is a diagonal matrix with non-negative entries, so Us U!!???1/2 (2) Then have (by Cauchy-Schwartz and Young's)
EI 1/2 E( (((o))), U 1/2 v log
He(a) π TΦx)
> E v
Bll v log Me(x)
((x))
/ vS(ma)]]
E log
23

---

Published as a conference paper at ICLR 2025
We can decompose the first term
E 2 f Σ (.IL) U2
-
In line with the presentation in the draft Chewi (0224)
we apply Lemma 16 from Chewi et al. 202
which only requires smoothness and L integrability in the marginal potential:
Lemma (Lemma 16 Chewi et al. (2021)). Assume probability measure т ix e- E (2()R has L-smooth potential J. Then for any probubility measure 1
(F(ull) + 2dT.
By the smoothness of f. we have:
Bl - Us V/(o))) zoll
Suppose t S A S 1 then
2L
Bl - U (200)) =
Hence
- E| - +
Plugging in Lemma yields
-
E(Sid, (11 +
4d,131).
Assume A <
Vomen
Then
AL.
Φmi di
E
[At L.F [TTB.) + SdL33 + 4d, < E
Fl (TB.)) + Σ oi + Ldt]
Ømin Σ D Ld, 4d,
Omin FI( + E
s (Bd. 4d.1
Quin
We then have
O (KI((ellz)) < Qmin FT (T( 6E|d, < 7 (RL(HU]TTT + (E(d,T?0)
We start by multiplying both sides by Aminte and integrating from 0
(LL(,,1))) S dmnnd (KI(H))TT) + 3d,
Taking expectation over then gives the result
E []]] < E.ee Tomia As DKL (poll + 3E|d, A1
24

---

Published as a conference paper at ICLR 2025
Iterating C.4 gives
d
E EIKL [[]]]
El
Amin jk DEL (MollT) + 3R|,
Ele
7Pmin Amin
e Tominnn Ack DKL (HollTT
E[d,
7pmin Amin
where we first bound using the minimum step size, then apply the power series bound
Ble Temin Arji
romin Amto
Tomin Amin
and then apply T-
to obtain
3a
E
PPmin Arain
37pmiinAiin
D CYCLIC BLOCK LANGEVIN DIFFUSION
In this section we provide proofs relating to Cyclic Block Langevin Diffusion (CBLD, the focus of the main text) and time-discretized version, Cyclic Block Langevin Monte Carlo (CBLMC).
The CBLD sampling algorithm is shown in Algorithm
Algorithm 4 Cyclic Block Langevin Diffusion (CBLD)
1: procedure CBLD(ro dom(f), Block Permutation BBi, ... BaJ, Step Sizes À R$)
2: for k 2 0 do
3: Define To tgb
4: for 1 to b do
5: Choose = on and set Tn = Tn-1 + X
6:
Sample:
(.Vf(z)dt+ + L
U. 23-1
Zrn = Irn-l
Tn-1
Tm-1
7:
end for
8:
Set: Ste++166 = ITt
9:
((k+1)b Tb
10: end for
end procedure
A crucial identity used in our analysis the "chain lemma" for KL.-divergence. For any distri- butions
DKL = DDD [B)) + (H4,
where is subspace of R.d. DKL (14 a | a) the KL-divergence of du and conditioned on an the KL-divergence of μ4 and marginalized over R. \ B. We also state two trivial lemmas for any 7-LSI distribution v. We first state an equivalent definition of Assumption 2
element of B, and (KI( as (F))
Definition 1 (Alternative LSD). & expl-8f(x)] satisfies log-Sobolev inequality (LSI) with CLSI = 1 if for all smooth g:
1 E. [
E Eg go Ez Ex log E 1 S
2n
where the equivalence with the previous statement follows by choosing (xx
[(x) x(x)
25

---

Published as a conference paper at ICLR 2025
Lemma 5. Suppose A, B are disjoint subspaces of RR with AU B = R Then the A marginal VA also satisfies y-LSI.
Proof. By the LSI, for any smooth g R R Ey [9 log gogg"]]]_ - E, [0 For g A + R. we can re-express the terms as
log Ey [g < Ev [[[
B Ev 119 logg" 9² Evgia (Ena (g") log Ey (g²1) - BuBLA Ey [|V]' Since Bum [0(=)] = ((=) for all E A, we simplify ENg [g² log g²] Evs [0a] log E. [9 & REA [[]]]
Recall that the sub-step dynamics are described by the SDE dr = Un [V)(d) + /2ddW?]
(10)
where dW? denotes dn di-dimeniional Brownian noise. We can then derive the coordinate Fokker- Planck equation:
Lemma 6. Let Prira be the law of time E [0, Anl described by the SDE in Equation IO where Pr|ms is conditioned on the starting state Tn- Then Orl4,,Bal10 = and
dePl, OePt,B..TT... BT. = 1-22 "B..TTa.m
V (H Da vf(x))
is the Fokker-Planck equation for the subspace diffiusion.
Proof. The second claim is trivially shown using Itô's Lemma. Note that since B.,B...B..t. is only supported on B.:
1. Tr Un V P.
B.. 8- Mt B,,20
2. B..BABBA... Vf(z)) V...B. Bn..o vf(x))
Then we have
0e B. Bn.20 --- PB Tin V. ( vf(z))).
We now use this prove the first claim.
Consider the law of æ in sub-step n conditioned on the initial state To given by Ma Note that Melrr Hr, Hr, By the Fokker-Planck equation associated with the SDE and the product rule, we have:
0 -r-'Tr 2 Mysial + V Un V(()))) Pt, l00 DePt, Bulnao + B1,BB,|B..ny d.P, =9 Tr V Mr,B, B.. Li | + V (H Br. Mr Un V f(x)).
Note that
9 TT(UU V22 M4,Ba Ba Ba. Mr, B 3- H4,Ba io V |n..0 Ba.20
n1
and
M2 Un fx(x)) = MI.B, mo
V. (4,, vf(x))
We then have
M,BBa O.H4,Ba - 122 B.... V (Hr,B, vf(x))) = Mr,B,, Br, DeHt,B..
We assume that b4 is supported on Rdd, therefore Mtjzo "M..,lloo B.. 0. As previously discussed, Itô's lemma implies @ is 0. For equality to hold, then, 0,14, 0. n
26

---

Published as a conference paper at ICLR 2025
We prove the following technical lemma for later use in the descent bound: Lemma 7, Suppose A, B are disjoint subspaces of I2 Then we have
DRI(MAl|TA) S AII))A
Proof. Note that for all A
ma(x)= "A,n((,,))d = Bage://nnndddyyeeellaaaaaa En(uAiB]
By the convexity of the KL-divergence and Jensen's Inequality
(KI(HAlTTA) KL[EgluAn| < (MDDEL(AAAB A DRL (MA))BlTTA)B)
Lemma can be considered restatement of the "data processing inequality". Removing the con- ditioning on subspace B effectively reduces the available information, akin to noisy channel, decreasing the divergence between distributions.
Lemma 8.
DKL(Hol|()) S -2y8 1xn (DKL((n-)](T)] -218 1An) DKL ||
Proof. Using Lemma 6 we can show by standard arguments ct al. (222 that within sub-step n::
Vempala & Wibisono 2019) Chewi
DKL (4, (T. S -205 '1 'DKL (T.)
(11)
Using and the chain rule for KL-divergence
DKL [)) E
| B. 13) + DKL 1, 1 DKL BB
e
2
E
|| T..
+ DKL (1
2
DKL. 11 I| [T (KI, 11 11 + DKI (Mo (1T,))
27A08
(1I + (1 ----------e 2rdn0=)) DKI.
An immediate consequence of Lemma is that the KL-divergence is non-increasing, as stated in the following Corollary.
Corollary 1. For all i E (1,...,b), 6}, (uilTT < (Ro((Hol(=)
D.1 PROOF OF LEMMA
Proof. We prove the claim by induction on b. The claim is immediately evident for as consequence of 8 with Crax C1, since B 0.
Now we assume the inductive hypothesis for some h 2 and prove the claim for 2 2 blocks.
We start by applying Lemma twice to obtain terms relating to step 2, obtaining
DKL (T) SG, DKL (16-111) + Cb) DKL DKL 11 + Do
Second descent expansion: -C,Co-1 DKL (1 Cb) D (16-,,, II BT.)
+ C1 Ca- DEL DKL | + Db + CDDb-1
27

---

Published as a conference paper at ICLR 2025
From here, note that DKL (KL-1111.BB (TT satisfies the theorem conditions, since all blocks in BB have been sampled. We can therefore apply the inductive hypothesis and obtain
6-1
(KL(PT
Σ D + Cmax (1 - Cb) DKL B, TT. (1 (1- - Cb)
+ -
+c((1-Cb-)
(k) 2, .ITTT, ) + CoDo-1
Using Lemma we can upper bound
DKL (Ko (TB. DKL (HL T lB (Bo.))
and then apply the chain lemma
DRI.(/0-2BB...1B. BB_
BB 1B_1 (RI.(16-2111)) - (no ,lITA, .)
to obtain
(KL(Hb]IT) (KL(-o-l1)))))
+ + - Co (KL (T b-1
(b) Σ Dj Cmax Cbb DKL (Mo, (TB,) + Do CoDo-1.
We can define Ba.b-1 A Br, n B5-1 (all variable blocks except the last two) and apply the chain lemma
(KI (T.) = DKL. Bo B..- Tho, 118 ,) DKI IT..
obtain the bound
(p6( SC&Cb-1 D (m6-2222111
+ Ca(1 Cb-1) (1o Cb(1 Ob-1) DKD 2,8, 1l
b-1
(1
- Cb) Σ D;
i=1
+ Cmax - Cb) DKL 118--1 1B,,, + Cmaxe Cb) DKL (Ho
+ Do + CoDo-1.
We can regroup the terms and cancel CBDa-1 CBDo-1 yields DEL (p6ll)) SC₁ (16-11))
CbCCuu DKL 1 I 1Ba- )
Σ D.)
i=1
Cb(1 - Co-1) DKL (|TB.).)
+ Cmax DKL (Mo, Mo.
[ 1B + Omax (1 Ob) DKL BBB
Σ Dr
By applying the inductive hypothesis in reverse, we can show
b
-Cy(Cmax DKL (KL(Mo.E_.,1BB11 T B...- _B_ )+
D -CDD 1 1T (B_,)
Substituting this into the second line, we have
(p6l)T -C, DKL (1b6(122117)
-C, DKL (KK
T T -KL (
B.B
+ Cuax DKL (H0, 1,l_1
|| | Ba-1 + Cmax
Cb) DKL (Ho, (B
D
28

---

Published as a conference paper at ICLR 2025
We can again expand the terms
DKL 2,B, 0-100.11110 11m B 1Bo-1
Cuax DKL (Mo, - || IT b- BB |B_r)
Using the chain lemma and canceling the single block terms gives
DKL (Hol|=)) SCb (Ho-22))
C. DKL 2, CK 1 TB
+ Ciaxx DEL (1 (T - CoCmax DKL (140 (B--1)
D2.
Since Cmax 2 Co-1 by definition and DKL is non-increasing with respect to inner loop steps b, we can disregard
C₂C
CmC DIL
S C₂.Oo 2,8, || ,) - C,. (KI 2. || 1) S 0.
We now add zero to the right hand side via
0 C. (KL 2,
C.
We then have the three terms
DK Di,
-C, DKL 2,8, [T,)) C. (M 2, |T B
(12)
Cmaxx DKL (Mo,B, [B,) + C2 (KL
TB,
(13)
Note that the previous time steps left /4a-2,B B, [B, invariant, hence DKL (1o BB | (B,))
(KI B, n,17,)- Then by applying the chain lemma to and 122 we obtain
(HO( <C₁ DRI C. (1s-222 Cmax (Ho( + Σ>> Dr
=Cmax (Ko(Ho|(T) - Σ D
which completes the proof.
D.2 CBLMC: EULER- MARUYAMA DISCRETIZATION
As discussed in the main text, Lemma I can be used to trivially bound both the continuous (C; e- -- D, 0) and discrete (C; e -- D; Ld cases. As with RBLMC in
the previous section, we take 1 to simplify constant terms. Discrete-time CBLMC is shown in Algorithm 5
We recall the convergence results for LMC from Vempala & Wibisono (019)) (adjusted using Lemma 16 of Chewi et al. (202T) as in our analysis of RBLMC).
Theorem (LD Convergence (Theorem of Vempala & Wibisono (2019)). )), Let π be a distribution satisfying LSI with constant with L-smooth potential. Assume that the LMC step size X is chosen such that E (0, ]. Then after a single step of LMC, the distribution pK++1 satisfies
DKL (px+11/ S - (KI( + -X
29

---

Published as a conference paper at ICLR 2025
Algorithm 5 Cyclic Block Langevin Monte Carlo (CBLMC)
procedure CBLDD(ro E dom( Block Permutation a = = {Bi, ..., Bo], Step Sizes E R
2:
for k 2 0 do
Set = x² 4:
3:
for to do
5:
Choose = on sample Ç ~ N0, 14)
k+1 n+ In
k+1 A.U.V((2 - U.V22/5
6:
end for
7: Set gk+1
bb+
8: end for
9: end procedure
For CBLMC, we additionally assume that the potential is L-smooth (Assumption 4 From
Beck
& Tetruashvili 20113), this implies each block has separate smoothness constant L, applying Theorem each block step has the descent
L.
From
DKL (nt (T)) Se-mh DKL (uL(u-1111)) + (1 e DKI(UE b- 11
(lx)))) 3L?d,,?
When iterated for kb cycles, we obtain the bound
DKL (1 [[)) Se "yhhhamni Aani kbb
DKL (1 + Ammin i=1
Σ Lid.A.
where the constant terms are derived analogously to the RBLMC proof in the preceding section.
E PROOF OF THEOREM 3
We begin by recalling the following Lemmas from literature:
Lemma 9 (Uniform I bound on Langevin Diffusion (Lemma 3 of Raginsky et al. (2017)). Let
IRd + be differentiable function satisfying Assumption 5 (0) V((((s))d -o dW., we have the bound
For a random variable xx)) =
|||+(0)11 < B[|=(0)))]e--m + d/3+c +
2mm)..
771
Lemma 10 (Wasserstein bound from Relative Entropy (Corollary 2.3 of Bolley & Villani (2005 )
Let p. v be two probability measures on some measurable space X equipped with measurable
distance 2, and let Φ X + Rt be non-negative measurable function. Assume that 3ro E X, such that I ( dv(x) is finite. Then
W2 < C (1ll//1 + (Drulullu)) 1/4
2
where
1,3 + log (oM((o)))P((()))
1/p
C c inf ZoEX
In addition, we adapt the following Lemma from Raginsky et al. 2017
Lemma (Exponential I Integrability of Block Langevin Diffusion). Let f. Rd + be a dif- ferentiable function functioon satisfying Assumption 5 and let x* (t) z(0) - Sh Uv (( S UndW, be a random variable &&d across some number of iterations where Σ U, = Ta. Suppose the initial state zo is drawn from some Ho satisfying Assumption Band 3 > 2/ m. Then on iteration k
log E caa2ll]] < + 2(c
dmax )R
B
30

---

Published as a conference paper at ICLR 2025
Proof. Define G(a - ell=t1? By Ito's lemma, iteration it of BLD we have
| di 23-1 Tr U2 Axx all di
dG(xt) = - 2 (1) UR
+2 2B ( Uk) ell+111 dw,
2 (
G(t)dt
+ -d G( dt + I(U (o+ Un) G(a))aw
Integrating and summing across steps, we obtain
G( =G(x) + 2 6 (o
G(af)tt
+ L
L'" 2B 23 (a Uw) G(at)aW.
d,3 d G
Applying the dissapativity condition and assuming 3 > 2/m, we can bound the first integrand as (cj.UuVS(E)) 2
"1,,,111 S (2 m) Σ (5 +csc jEB,
which results
&
/ G(zt)dt /-/ 2 2 23G(x UndWi).
G(z))= = G(x +
Σ 2 d
As stated in Raginsky et al. 2017). each Itô integral Jo 2v23G((=²) (at UndW,) is zero-mean Martingale. Taking expectations over both sides and applying Assumption yields
2(c + do.3-1) / B[G(x*)] = B[G(a)) Σ
B[G(x)))dt
Ad
e + + dmax 1-1)
E[G(z))]dt.
where the integrability of [=G((= across block steps follows from the continuity of x across each block step k. By Grönwall's incquality, we have
E[G(xX) < exa 2cotdmae JAA
log [=G((x)) I + 2(c dmax 2-
Theorem 3 follows consequence of Lemma 2 by applying the Otto-Vill Villani theorem coupled with the triangle inequality for W2 as stated in the main text.
E. PROOF OF LEMMA
Proof. Let μu² and Uy be the laws of SGBLD and BLD times t and iteration respectively with iterates x²(s8 (s), y¹ (s). We assume that each process selects the same variable blocks at each iteration, iee B B
Using the Girsanov formula, we can express the Radon-Nikodym derivative def
dnf as
dut = exp
2 %
(UAVF(O(()))
- V28- UzdW,)
dyr
B
+
- (.N Ung: (s))) dt
4
B
[ (UNT)((()) U2 (s))..W. (s)
B % (UEVF(( - (x
exx
2
4
31

---

Published as a conference paper at ICLR 2025
Setting & AR. express DKL (1z ||x]))
(KL( =- / duf log
dut dih
k
B
ΣE
E
||
(U) (s)))
4
since So (U&Vf(y"()) (v (s)). dW.) is a O-mean Martingale.
Using Assumption 3 and Lemma we obtain
3
DRL (1())
E
[UAV Unga (v)a))))))
==1
B
M 2 ddds
Jo
me M + d:/B + (1 (1-c-mo) + Bsds
Jo
m
where we have applied Lemma in the last line. Integrating, obtain
M
(d./33 + c)
(KL(F)
E
(mt -e- -1) B²1
m
m²
Expanding e and leveraging that mi > 1 e e 2 md m² 2
8M2 x
2 (d: + cg)
3B't
(KL(H
E (0)12
4
4
By repeatedly expanding Lemma
we obtain
M2
Ko t mmi-11) M2,
(mmi-i))-M22((4 + 3c)
22, + +B)
3B2 Xk:
DRL (1 <
+
+
8
8
1=0
M 3Ak
M2 + +B3ck
BB
+
4
4
(C1 C2A)AK.
where we have defined for convenience
.
BB²
C₁
4
4
and
M (2mmax + +Bc)
C2 A
By Lemma
10 bound (n ) as
W3(nt, 11 540² (ralulll))/> + (Deifullle) 1/472 2
Setting a = 1, d(x) = 1/211//2, and p = 1/2, we obtain from Lemma
40 < (12 + 4ng + 8(2c + dmax )k))
Note that for any 2 0. we have (Vo + 1/4/2 < 2a + 2 since
1/2
1/2
(Va+ + ())1122 a - 22/4
21/2 + a2 (12)(22))2)11
21/2
32

---

Published as a conference paper at ICLR 2025
By Young's inequality, (24/ va + hence a (Vā+ aa+ (2 a 1/4 /²)(()))))))) 13) 21/2 S 2a +
1/2
2va
S 2a 2va.
v2
plugging in Lemma and assuming KY 2 1, k > A we have
W vt) - 20
(KL(A]le) + VDK((ulle)
<(12 8(Ko + (2c d d fmnxx/11))
(c++2N)A V(G C2A)Re (k2)
<(12 + 8(KO + (2c + d m (1))
(C2+ (G1 + VCJ) (ka)²
=cB (C2 VO2) (C1 Vai) (RA)2-
We thereby obtaining Lemma
2 with:
Co (12 + 8(10 + (2c dinax/ (3))),
C Mr,Kn BB²
4
C2 A M (d + Bc)
4
E.2 CONSTANTS IN EXPECTED FUNCTION GAP BOUNDS
We start by recalling the Lemma from Polyanskiy & Wu (016))
Lemma 12 (Wasserstein Continuity for Quadratic-Growth Potentials). Let be probability dis- tributions with finite second moments and let f IR + R+ be a continuously differentiable function
satisfyyng V f())11 =1| + c2. Then have
/ f())d((x) f(x))d(())
[ (c (2(u.)
where a = / [E,ax(E_.1laa [?3), [+
Raginsky et al. 2017) bound the constant x² max E [x+]] [x(() using unbiased oracle. As discussed in the main text, DXs have fixed device variation from analog errors, precluding unbiased estimation. However, DX errors take the form of perturbations in the underlying function, i.c. the target function characteristics are intact. For instance, DXs with quadratic potential targets (Aifer al. 2023: Song et al., 2024) are still optmizing/sampling quadratic functions. Accordingly, As- sumptions and 5] that the DX gradient retains both Lipschitz continuity and dissipativity, are reasonable. Assuming gs is (m, disisiipaa,,e, have from Lemma of Raginsky al. (2017):
c dBB
[xx(1]] < Ko
m
Then
c + d/3
+ d/3
0² Kg max
m
m
33


Reviews:
[{"review_id": "H55SlUimEz", "reviewer": "Reviewer_wnfD", "summary": "This paper concerns analysis of hybrid large neighborhood local search (LNLS) frameworks, in which the authors provide non-asymptotic convergence guarantees for this framework. In particular, an exponential non-asymptotic bound is obtained for the KL divergence of DXs employing two different strategies (randomized and cyclic block) and a bias bound on the 2-Wasserstein distance is established for finite device variation. Numerical experiments supporting the theoretical results developed.", "questions": "- Can the authors provide further examples of distributions that would satisfy the LSI? How realistic is that assumption in applications?\n\n- Random and Cyclic block approaches seem to produce similar outcomes. What is the motivation to choosing one over another? Is there any intuition on which one should I choose based upon my application?\n\n- In Figure 2 (e), why doesn't the curve associated with \\delta=0 match the ideal curve?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This is an interesting paper and I believe the contributions are novel. The authors provide a good literature review and contextualization of their results with respect to the past literature. Moreover, the authors did a good job in identifying the limitations of their work. \n\nThe paper is objective and its contributions are clearly identified.\n\nI did not have time to review all proofs in detail.", "weaknesses": "-I believe that a discussion on the performance differences between Random and Cyclic block approaches would be good for clarification (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nBg4K148SW", "reviewer": "Reviewer_zAh3", "summary": "I am not engaged in research related to this problem, so I am unable to provide an\nobjective evaluation on this topic. Please disregard my review comments.", "questions": "1. In this paper, the authors assume that a vector can be decomposed using tensor products or Kronecker products. However, this decomposition does not span the entire Hilbert space, which implies that the conclusions presented in the paper lack generality.\n\n2. All equations lack punctuation and should be corrected.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "N/A", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "COBJFfPpIf", "reviewer": "Reviewer_o8aG", "summary": "Analogue accelerators are attracting renewed interest, promising far superior power efficiency and latency compared to digital methods for problems in machine learning, optimization, and sampling.\nWhile the theoretical understanding of analogue accelerators has evolved quickly, significant gaps remain when taking into account a fundamental practical aspect of those devices:\ntheir limited capacity makes it necessary to solve larger problems \"piece-by-piece\".\nThat is, the device operates on a subset of the problem at a time while keeping the rest constant, progressively iterating over the entire problem.\n\nThe authors find a rich connection between this constraint and the theory of block Langevin diffusion algorithms.\nWith the connection to well-established theory, the authors adapt existing methods to obtain novel bounds on the performance of a class of hybrid analogue-digital algorithms and non-asymptotic guarantees for their convergence when accounting for non-ideal devices (which are inevitable in practice).", "questions": "1. In the applications familiar to me, analogue-to-digital conversion tends to be an crucial bottleneck for hybrid analogue/digital accelerators.\n    This affects their accuracy, latency, power efficiency, and, most crucially, die footprint which largely determines their cost.\n    ADCs are so expensive in so many ways that many applications sacrifice as much precision as possible to minimize their use.\n\n    In this light, how are those aspects relevant to your work?\n    Do the experiments take them into account?\n    Do previous works on the topic address them?\n\n\n2. As the authors say, performing experiments with Gaussian distributions allows for closed-form solutions for the 2-Wasserstein distance. Yet, even though the plots from Figure 2 display a $y$-axis with units, it is hard to reason quantitatively reason in terms of $W_2$. Could you provide some general guidance for that? I mean, is a $W_2$ of 1 large? I understand this can be problem-dependent, but some general guidance would be helpful.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written.\n    The exposition is clear with remarkably few typos, the motivation is put clearly, the authors bring and discuss relevant limitations, and they provide some discussion after presenting design choices, results, and new ideas, in general.\n    They also highlight key ideas underlying their proofs.\n\n2. The work is decently contextualized.\n    The contribution relies significantly on many existing works, which the authors appear to recognize and discuss fairly.\n\n3. The authors are upfront and honest about the limitations of their work.\n\n4. The general topic is interesting and timely.\n\n5. The reduction to block Langevin diffusion seems like a natural (and, thus, promising) approach to the problem.\n    I believe it should motivate several follow-up works.\n    The approach also yields significantly softer assumptions compared to similar previous results.\n\n6. The results feature valuable properties for practical applications, such as explicit constants, hyperparameter simplification, and the handling of some device variation.", "weaknesses": "1. The care mentioned in strength (1) does not extend to the appendices. E.g., Appendix A would greatly benefit from some discussion about the impact and intuitions behind the choices made for the experiments.\n\n2. The last sentences of the paragraph 051-059 ask for some substantiation, but the authors offer no references to back them up. Some further discussion could also solve this issue.\n\n3. Despite strength (2) and my comprehension of the space constraints, I believe the paper relies too heavily on references to explain the concept.\n    I do not see the reliance on previous works as a problem in general, as much of it is a side effect of the strong fruitful connection the authors made with consolidated theory.\n    Still, at points such as Section 4, I felt like essential details were left to be found in the references.\n    I am sure there is some curse of knowledge at play here, which is understandable, but it would be a good use of the authors' sharp eloquence to make the paper a bit more self-contained.\n    I apologize for not substantiating this claim with specific examples, but it is hard to do it when my point is precisely that I did not get a good grasp of what was being presented.\n\n4. The role of analogue-to-digital conversion is not discussed.\n    While I am not sure how pertinent this is for this particular work (see question 1), ADC bottlenecks are so common in analogue computing that it should deserve at least a mention.\n\n---\n### Minor issues and suggestions\n\nI'll only mention typographical matters because I noticed the authors were particularly zealous with that —I spotted the 2-letter `\\emph` on line 269!\nThey did a great job, overall, and those suggestions aim to help them further improve their skills.\n\n1. Consider numbering only the equations that are referenced in the text (rather than all of them).\n2. Most colons preceding equations should be removed.\n    More generally, equations are an integral part of the text, reading as sentences.\n    This also means that equations should be punctuated as such (this issue affects almost all equations in this work).\n    Any maths style guide would serve as reference for this. As an example, Section 13.4 of the AMS Style Guide (I'd provide a link, but this is disallowed for reviewers) mentions both issues.\n3. Some `\\mathrm`s and `\\operatorname`s are missing.\n    See, for instance, Assumption 1.\n4. By eyeballing, I suspect the authors use `||` (double vertical bars) when they should use `\\lVert`, `\\rVert`, or `\\Vert` which ensure proper spacing.\n    For example, compare $||x||$ and $\\lVert x \\rVert$ (the latter is the correct one) or $\\mathrm{D}_{\\mathrm{KL}}(\\mu || \\pi)$ and $\\mathrm{D_{KL}}(\\mu \\mathrel{\\Vert} \\pi)$ with the latter being coded as `\\mathrm{D_{KL}}(\\mu \\mathrel{\\Vert} \\pi)`.\n5. At 235, having the domain of $i$ specified in the definition of $\\overline{B}_i$ would be helpful.\n6. At 105, mentioning $\\beta$ is premature.\n    The sentence also references Equation 22 which is 7 pages ahead!\n7. In Assumptions 3 and 4, the domain of $\\delta$ (denoted by $\\mathbf{D}$) is not defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gJpfXFfayY", "reviewer": "Reviewer_YcU8", "summary": "This paper presents the first explicit probabilistic convergence guarantees for hybrid Langevin Noise Likelihood Sampling (LNLS) algorithms in activation sampling and optimization. The authors reduce hybrid LNLS to block sampling using continuous-time Langevin diffusion sub-samplers, analyzing randomized and cyclic block selection rules. They demonstrate that ideal accelerators converge exponentially under a log-Sobolev inequality, while finite device variation introduces bias in the Wasserstein distance. Numerical experiments on a toy Gaussian sampling problem illustrate the effects of device variation and hyperparameters.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly structured, with each theorem building on the previous results to form a coherent narrative.\n\n-  The findings of the paper are supported by clear numerical experiments.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pa177nfLvf", "reviewer": "Reviewer_kqH5", "summary": "The authors analyze analog accelerators and large-neighborhood local search (LNLS) frameworks. Reducing LNLS to block Langevin Diffusion algorithms, the paper provides convergence guarantees using the tools from the classical sampling theory.", "questions": "(see weaknesses)", "limitations": "", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Before I start my review, I should acknowledge that the topics of this paper, including Langevin Diffusion (BLD) algorithms, Analog dynamical accelerators, SDEs, LNLS frameworks, are very different from what I do in my research. My main field of interest is mathematical optimization.\n\nI have no doubt that analog computations are an important direction to accelerate the current expensive digital algorithms: the topic is important and relevant. The author's attempt at approaching the issue is unusual (in a good way) and nontrivial.", "weaknesses": "The main weakness is that it is challenging to read the paper. From the beginning, the authors introduce many uncommon words and terms that are very unlikely to be easily understood by most researchers from the ICLR community. I think the introduction and the background should be significantly simplified for a broad audience. For instance, the main object of interest is LNLS, but the authors do not try to explain the mathematical foundation and the background of LNLS. Figure 1 is too abstract to understand LNLS.  \n\nOther weaknesses and questions:\n1. Why do you consider Block Langevin Diffusion? Why can't we optimize w.r.t. all variables?\n2. Lines 345-347: I guess there should be $||x - y||^2$ instead of $||x^2 - y^2||$\n3. Assumption 5: How does the function inside the integral depends on $t$?\n4. Assumption 6: In my experience, this is a very *uncommon* assumption. Also, Assumption 3 is also very uncommon.\n5. Theorem 3: This theorem yields the convergence rate $\\log \\frac{1}{\\varepsilon} + \\varepsilon,$ which is $\\geq 1.$ What If one wants to make the Wasserstein distance less or equal $0.001$? \n\nUnfortunately, reading this paper, I'm not convinced that the reduction to Langevin Diffusion algorithms can not help to improve and explain analog accelerators. At the same time, I do not have expertise in these fields, so I choose low confidence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)