AutoStep: Locally adaptive involutive MCMC
Authors: Tiange Liu
Nikola Surjanovic
Miguel Biron-Lattes
Alexandre Bouchard-Cote
Trevor Campbell
Venue: ICML 2025 poster (2025)
Keywords: MCMC
Markov chain Monte Carlo
adaptive
involution
step size
tuning
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods
TL;DR: We introduce a new locally-adaptive MCMC algorithm that automatically adjusts its step size parameter on the fly while maintaining pi-invariance.

Abstract: Many common Markov chain Monte Carlo (MCMC) kernels can be formulated using a deterministic involutive proposal with a step size parameter.  Selecting an appropriate step size is often a challenging task in practice; and for complex multiscale targets, there may not be one choice of step size that works well globally.  In this work, we address this problem with a novel class of involutive MCMC methods---AutoStep MCMC---that selects an appropriate step size at each iteration adapted to the local geometry of the target distribution.  We
prove that under mild conditions AutoStep MCMC is $\pi$-invariant, irreducible, and aperiodic, and obtain bounds on expected energy jump distance and cost per iteration. Empirical results examine the robustness and efficacy of our proposed step size selection procedure, and show that AutoStep MCMC is competitive with state-of-the-art methods in terms of effective sample size per unit cost on a range of challenging target distributions.

AutoStep:
Locally adaptive involutive MCMC
Tiange Liu
Nikola Surjanovie'
Miguel Biron-Lattes'
Alexandre Bouchard-Côté Trevor Campbell
Abstract
often rejected, while too small a choice leads to nearby pro- posals that do not explore the state space quickly; either case results in slow convergence of the chain. For certain multiscale targets (e.g. Bayesian posteriors with scale priors (Polson & Scott, 2012)) there may not even be single good choice of step size throughout the whole state space.
Many common Markov chain Monte Carlo (MCMC) kernels can be formulated using de- terministic involutive proposal with a step size parameter. Selecting an appropriate step size is of- ten a challenging task in practice; and for complex multiscale targets, there may not be one choice of step size that works well globally. In this work, we address this problem with novel class of invo- MCMC-th selects an appropriate step size at each iteration adapted to the local geometry of the target dis- tribution. We prove that under mild conditions AutoStep MCMC ziinvariant, irreducible, and aperiodic, and obtain bounds on expected energy jump distance and cost per iteration. Empirical results examine the robustness and efficacy of our proposed step size selection procedure, and show that Auto MCMC is competitive with state- of-the-art methods in terms of effective sample size per unit cost on a range of challenging target distributions.
Existing methods for selecting step size parameters fall generally into three categories: adaptive MCMC, discrep- ancy minimization, and locally-adaptive kernels. Adaptive MCMC algorithms (Haario et al., 2001; Atchadé, 2006; An- dricu & Thoms, 2008; Marshall & Roberts, 2012) tune the proposal distribution using previous draws from the chain, often targeting a particular acceptance rate derived from high-dimensional asymptotics (Roberts et al., 1997; Roberts & Rosenthal, 1998). Obtaining theoretical guarantees on estimates produced by adaptive MCMC targeting distri- bution is technically difficult and often requires strict conditions on the adaptation process, such as increasingly infrequent adaptation (Chimisov et al., 2018). Discrepancy minimization (Neklyudov et al., 2018; Coullon et al., 2023) involves tuning using a divergence between the empirical distribution of draws and the target स, which requires multi- ple MCMC runs to estimate the divergence for each candi- date step size. Both approaches also identify only a single step size value, which may not be appropriate for the whole state space.
lutive MCMC methods-AAtoss
1. Introduction
Markov chain Monte Carlo (MCMC) (Metropolis et al., 1953; Hastings, 1970) is an effective tool for approximating integrals arising Bayesian inference problems. The perfor- mance of MCMC is often sensitive to the choice of tuning parameters in the Markov kernel. In particular, methods that propose new state followed by an accept/reject step e.g., random-wall walk Hatropolis-Hasting (RWMH) (Hast- ings, 1970), the Metropolis-an adjussed Langevin algorithm (MALA) (Rossky et al., 1978), and Hamiltonian Monte Carlo (HMC) (Duane et al., 1987; Neal, 1996) often in- volve a scalar step size parameter 0 2 0 that governs the distance of the proposed next state from the current state. Too large a choice of 0 results in distant proposals that are
Locally-adaptive kernels, in contrast, select a value for the step size each iteration based on the current state. Be- cause the step size depends on the current state, these kernels can adapt to the local shape of the target æ and because they depend only on the current state, they are Markovian and one can use standard tools to prove π i-inaariance. There are many approaches to locally adaptive step size selection in the literature. Mixture kernels with state-dependent weights (Maire & Vandekerkhove, 2022) and delayed-rejection (Tier- ney & Mira, 1999; Green & Mira. 2001) are both general approaches, but each requires prespecified maximum num- ber of step sizes to consider at each iteration. There are also numerous methods specific to certain samplers, e.g., HMC and MALA (Girolami & Calderhead, 201 1; Nishimura & Dunson, 2016; Kleppe, 2016; Modi et al., 2024; Biron- Lattes et al., 2024; Turok et al., 2024), RWMH (see Liv- ingstone, 2021), or slice sampling (Neal, 2003). Of these, the method most related to the present work is autoMALA
'Dpartment of Statistics, University of British Columbia, Canada. Correspondence to: Trevor Campbell <trevor @sttattuutt.a........
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

AutoStep: Locally adaptive involutive MCMC
(Biron-Lattes al., 2024), which chooses a step size in MALA using doubling/halving procedure that targets Metropolis-Hastingg acceptance ratio in randomized range (a. b) C [o. 1]. While the method was shown to be æ invariant, it was crucially not shown to be either irreducible or aperiodic. In practice, AutoMALA indeed can get stuck in certain states, especially when the initialization point is far from the mass of the target distribution, as commonly the case in Bayesian inference; to address this, AutoMALA requires inexact unadjusted steps (see Algorithm 3 in Biron- Lattes et al. (2024)).
Lebesgue measure, and a family of differentiable involu- tions fo X' x 2 X x 2 parametrized by 0 E 6. Then, starting from a state Zt, we draw 2 m and the proposal
M #++ So (x(e:
We set the next state to 21+1 = 2 with probability
mip((,, 2,, 0))}
(2)
where
( (fo(2) (()))((2)
((1,, 22, 2) log
In this work, we develop novel method, AutoStep MCMC, for locally-adaptien step size selection in the broad class of involutive MCMC methods (Tierney. 1998; Andrieu et al., 2020; Neklyudov et al., 2020). We show that these Markov kernels are r--invariant, irreducible, and aperiodic under mild assumptions on the target distribution, thereby substan- tially generalizing and improving upon AutoMALA. We further provide bounds on energy jump distances and ex- pected cost per iteration, demonstrating the robustness of the method to the setting of an initial step size parameter. Empirical results confirm the theory and demonstrate that AutoStep is stable, reliable, and competitive with other adap- tive methods. Proofs of all theoretical results are provided in Appendix A.
and otherwise set it to Tt+1 = Ft. The sequence 24 is Markov chain and has stationary distribution и if so is continuously differentiable (Tierney, 1998, Thm. 2).
Choosing different families of involutions {fo} and aux- iliary distributions m yields different MCMC algorithms. For example, random walk (Hastings, 1970) with step size @ > 0 and mass matrix M is obtained by setting
(RWMH)
fo(2, =) - (x + OM OM- 2, =2) m. = NO M).
(3)
The Metropolis-adjusted Langevin algorithm (MALA)
(Rossky et al., 1978) with step size @ > 0 and mass matrix M is obtained by setting
Note that concurrent work on Gibbs self-tuning (Bou-Rabee et al., 2024b;a) introduces the same general technique for locally-adaptive involutive MCMC, proves т r-innariaacee and develops specific adaptation schemes for HMC and NUTS (Neal, 2011; Hoffman & Gelman, 2014). In this work, we provide an analysis of m-invariance, irreducibilityy aperiodicity, and expected cost and performance, with a specific focus on involutions parametrized by step size.
So =) = -z')
m = -0, M),
where x', 2' are computed via the leapfrog map
0 V log ((x)
212 - 2
2
x' x- x + OM 21/2
2' + 21/2
v logx(x').
2
2. Backkround
Finally, Hamiltonian Monte Carlo (HMC) (Duane et al., 1987; Neal, 1996) with step size 0 > 0, mass matrix M, and path length L is obtained by setting
Let i be a given target probability distribution on an open subset X' C Rdd With slight abuse of notation, we assume that π admits density x (Ir) with respect to the I Lebesgue measure on IRd, and that we can evaluate a function 7(x) x (z) pointwise so that
fo 2) = (x',
m = -O,
where x', are computed via I. leapfrogs.
Many involutive MCMC methods including the above three examples- have a positive scalar tuming parameter 0 >> O that can be interpreted as a form of "step size": larger values result more distant proposals, while smaller values result in nearby proposals. Too large a choice of 0 results in many rejected proposals, while too small choice results in proposals that are accepted but explore the state space slowly. Furthermore, there may not be a single choice of 0 that applies globally, c.g., in the case of multiscale targets (Polson & Scott, 2012). This work resolves this problem by selecting an appropriate at each iteration depending on the local behaviour of the augmented target π m.
7(x)
(2)
where I (x()) is the unknown normalizing constant.
Involutive Markov Chain Monte Carlo (Tiemney, 1998; An- drieu et al., 2020; Neklyudov et al., 2020) is an MCMC method that uses involutions, i.e., functions/ ʃ where f-1 f. to generate new proposals. While there are many possi- ble variations of involutive MCMC, in this work we use the following formulation. Fix a distribution m on an open subset& 2 C Rp with density m(2) with respect to the
2

---

AutoStep: Locally adaptive involutive MCMC
Algorithm 1 One iteration of AutoStep MCMC
2. Tuning parameter refreshment: Draw 02 ~ ry(00) It, Rt. Ur, bt).
Require: Initial a with T(æ) > 0, target т,, auxiliary distri- bution m, step size distribution 77, involutions {fo heee
1: 2 a m
D auxiliary refreshment soft acceptance bounds refresh tuning parameter augmented state > involutive proposal
3. Proposal: Set 8, = (Z,, 2t. ae. by, 0x) and
2: (a.b) Uni
3: 8 ~ mnddf
2, a,
S11 = F((s) = (1/+1) 2441 d b/ 8,+1).
4: + a,2,0,
5: s + f(s)
4. Accept: Set 2e+1 = x'(1 with probability
6: U ~ Unif(o,1 1]
7: if U S min
1,
x(d') [())
{(s)
then > accept
min { 1, ( J(
8: return
[(t))
9:
else
and otherwise set Te41 It.
10:
return
reject
11: end if
We can recover standard involutive MCMC by setting n(d0)2r 2,,, = 6u, (d0) for some fixed Og O. Fur- ther, choosing different involution families {fe 0 E θ} and auxiliary distributions m on Z recovers variants of common algorithms, e.g., RWMH, MALA, and HMC. The major improvement is that the chain may draw the tuning parameter 0 E O automatically at each step a manner that depends on the current state (Iz, 22, Qg b₂). The key design choice, then, is to select a conditional tuning refreshment distribution 1y that yields values of & that are well- to the local shape of the target न. In this work, we focus on the design of the conditional tuning refreshment distribution 1) in the case where is a step size parameter (with é RR+), However, the AutoStep MCMC method described previ- ously has the correct stationary distribution for more general parameter spaces C (see Proposition 4.2). Note also that the above approach of sampling tuning parameter O from a conditional distribution 1) given the augmented state was also introduced in concurrent work on Gibbs self-tuning (Bou-Rabee et al., 2024b;a), although the design of 7) in Section 3.1 differs.
3. AutoStep MCMC
In this section, we develop AutoStep MCMC, a family of modified involutive MCMC methods that automatically se- lect appropriate tuning parameter values at each iteration. The key technique in developing AutoStep MCMC is to for- mulate the sampler on an augmented space that includes the tuning parameter 0 E θ as well as other auxiliary quantities. For a given family of continuously differentiable involutions {ff : E } on Xx x 2, define the augmented space as
= x θ
where X' x Z is the original augmented space for invo- lutive MCMC, == {a, E 1)² a < <b} a set of acceptance ratio thresholds (a,b) b). and θ is the set of tuning parameters f for the involutions. We assume θ is stan- dard Borel space, such that S is standard Borel as well. Let f F:S S + S denote the augmented involution fg: for a point 8 = (x, b, b,0) 0) E S, define
f(x) = (Jo b,00)
J(s) = V fo =)]-
3.1. Step size selection
Note that f is itself an involution S. We then define the augmented target density
We now focus on the design of the tuning refreshment dis- tribution 77 when is a step size parameter with e R. Intuitively, good choice of should yield a proposal for which the acceptance ratio exp(((x, 0)) of the original involutive method is not too close to either 0 (0 is too large) or (0 is too small). Critically, this should also be true for
a(s) = (T)x) m(z)- (a r 2,
where we assume that T (x)) and m²)) are with respect to the Lebesgue measure on X' x Z, that both m and v admit i.i.d. draws, and that there exists a offinite measure d0 on θ such that for all & E X, 2 E Z and (a, b) E A, ny( x, a, b) a density with respect to d0, but otherwise may depend arbitrarily on x, 2, a, The X' X'-magginal of is the target of interest, x.
2, f)), which is the acceptance ratio in the reverse direction
{ (2, 2), -- 2).
To avoid setting arbitrary fixed bounds on f, we use random a, b as thresholds and ensure that [L] roughly tries to fall in the range (I [og()))). [lo((a)). More precisely, given a fixed initial step size 0o > O, we propose setting the step size to
Given this setup, starting from Te E X, AutoStep MCMC (Algorithm 1) consists of the following steps:
1. Auxiliary refreshment: Draw and
0 Oo 20(2,z,0.))
24 m
(er, Uni
3

---

AutoStep: Locally adaptive involutive MCMC
Algorithm 2 Step size selector j
Algorithm 3 Round-based AutoStep MCMC
Require: state æ, 2, a, b, initial step size Do.
Require:
Initial 2o, number of rounds R. target n, auxil- iary distribution m, step size distribution 1/, involutions [fo)ace.
0 < Bu
2: L < fx,,, 2, 0)
3: 4--+11 1[16] < |lo
[[()]
llogal)
1: 0u t 1, 1,M t m t NN(O,T) Ia)
4: j =0
number of doublings/halvings
5: if u = 0 then
for r in 1,2, ..., R do T
6: return j
4:
b Number of iterations
7: end if
5:
7 DiraccOo 22(2.,. (d8)
8: while true do
6:
for 1. 1,2, l....... T.... do
9:
x j+ U
7:
E~ 5~060 3Ó1 + B)) Random mixing of the preconditioner
10:
f -+ 22
11:
f f(x, 2, 0)
8:
M + -MM + +1-
12:
if = 1 and [6] 2 loog b) then
9:
m + M)
13:
return j
> Require final halving
& see definition of 1r in Section 3.2 It. μ4 + AutoStep(@---aat- n, m, 7h (fooce)
14:
else if v = -1 and |&| < |log al then
10:
15:
return j end if
11:
end for
12:
8g 0g x 2mediaa((41..-..
17: end while
13: Jo FT
(1)) 1 ([Varlof
14: M t diag
lt=1 j=1)
where μ is the step size selector function
15: end for
16: return {x1)1=2
p(x,22 2,a, b,
min E zt 2 z, 0022)
2 log bl} - 1,
[6] < log bl
max [j E x- [1(x,, z, 0022)) log a|}, 0,
6a| log a
otherwise,
3.2. Round-based tuning
and 6 - ((x, 0o)- Therefore n(d0 (r, 2, a, b) is the Dirac measure at plzz, 2, a. b), which has a density with respect to the counting measure on (0o x 2 : E Z).
The AutoStep MCMC method has one free parameter: the initial step size 0g. While the method is insensitive to 6 in that its performance per unit cost shrinks slowly at rate of roughly O() log Ool) (see Figs. 3 and 4 and Corollary 4.10 for empirical and theoretical evidence to that effect), it is still helpful to tune this parameter to minimize the number of doubling/halving steps. Furthermore, many involutive MCMC methods- e.g., RWMH, MALA, and HMC-ha preconditioner, or mass matrix M that needs be tuned.
The pseudocode for computing p(z, z, a, b) is given in Al- gorithm 2. If the initial step size 6g yields an acceptable (6u). the function simply returns j = If the initial step size is too large (f6o > log al). j is decreased until 16ol S |log a). And if the initial step size is too small (1oo < llog bl). j is increased until |&ol > log b), and then finally decreased by to avoid poor proposals. Note that this function does not guarantee that log < |&] < log al precisely, but finds a good trade-off by approximately targeting that range while avoiding the need for expensive methods to find values exactly within the bounds.
In this work, use round- based procedure to tune 9g and M (A (Algorithm 3). Each round corresponds to block of iterations during which parameters are held constant. We use 0g = and M = / for the first round. At the end of each round we update 6g < 0g x 2 where çü is the empirical median of the selected log step sizes μ4 = p(æ,, 2t, ae, by) from the current round. We also set M to the diagonal of the inverse sample covariance matrix, which is then mixed with the identity as a regularizer to form M each iteration (Line in Algorithm 3).
The step size refreshment was inspired by that of autoMALA (Biron-Lattes et al.. 2024), but has two important differences. First, we use symmetric thresholds that check loog bl < [e] S log a). instead of checking log < < log a. This crucial for ensuring irreducibility of the method (see Sec- tion 4), and avoids the sampler getting stuck in the tails or near the mode of the target (see Fig. for empirical re- sults to this effect). Second, we include the step size 0 as an augmentation of our state variable, which substantially simplifies theoretical analyses (compare the proof of Propo- sition 4.2 in Appendix A with the proof of Theorem 3.4 in (Biron-Latte Lattes et al., 2024)).
4. Theoretical Analysis
The marginal sequence on X' of AutoStep MCMC is itself a Markov chain because each step redraws 2,, Or b,, 0, independently of their previous value conditioned on ay- In this section we establish various properties of the X-
4

---

AutoStep: Locally adaptive involutive MCMC
marginal Markov chain.
We now apply Proposition 4.5 to the case where is step size parameter and we use 7 from Section 3.1. In this setting, Assumption 4.4 simplifies substantially.
4.1. Invariance
Corollary 4.6. Suppose Q = (0, xo), Assumption 4.3 holds, and we use 1I frfrrmm Section 3. Then, AutoStep MCMC is irreducible and aperiodic for all x E 2 and m.e.e 2 E Z. [e(x, 2, 2,)l & (0)
First, we show that AutoStep MCMC is i-invariant on the augmented space S, and hence r--ivvrriant X. The result is a straightforward application of Tiemey (1998, Theorem 2) on the augmented space S. Note that while this work focuses on step size parameters 0 E Rt. Proposition 4.2 below holds for general parameter spaces θ and tuning refreshment distributions n(d0),, Jr, 2, a. a,
We show in Lemmas A.I and A.2 that Assumption 4.3 holds for both RWMH and MALA under weak conditions, and hence the irreducibility and aperiodicity of AutoStep RWMH and MALA follows from [(x 2, 0o)l & {0,
Assumption 4.1. For each 0 E O, So is a continuously differentiable involution.
Proposition 4.2. Under Assumption 4.1, AutoStep MCMC is π TT-ivarians, and hence the X X-marginal is T-invariant.
4.3. Step size selector termination
We now establish that under mild conditions, the step size selector function can be computed in finite time. For starting state = (x, z, a, b) and initial step size 0o > O, let T (ss, Bu) 2 1 be the number of iterations of the while loop in Algorithm 2. The key condition, Assumption 4.7, is satisfied intuitively when the density m continuous and the involution fa becomes the identity 0 0 and grows without bound as 0 oc. Assumption 4.7.
4.2. Irreducibility and aperiodicity
Next, we establish that the X-mmrginna of AutoStep MCMC is n-irreducible and aperiodic (see Roberts & Rosenthal (2004)); intuitively, the chain has positive probability of eventually visiting any measurable A C X' with (AA) > 0, and it does not visit various sets in a repeating pattern. We will demonstrate 7-irreducibility and aperiodicity simul- taneously by showing that the X' X'-component of the chain can reach any measurable set A C X in a single step with positive probability (one-step irreuuiibility. The first as- sumption needed is that for any fixed 0 E O the mm-magainal kernel Po (Z.,,)) -) of the original involutive MCMC algorithm given by Eqs. (1) and (2) can do so as well.
For x m-u.e. (Ir E X x 2, lim 10(x, 2.)) 8-0-
lim [( 2,0) xc.
8
Proposition 4.8. Let 0g > 0 and suppose Assumption 4.7 holds. Then T(s, Ou) < 0o, a-..s
Note that while Proposition 4.8 guarantees that the Markov chain can be simulated in finite time in practice, the long- run computational cost of the step size adaptation depends on the expected number of doubling/halving iterations in each step, (E(ss, 80) for म. Proposition 4.9 bounds this expectation in terms of 2, for t E Z.
Assumption 4.3. For all x E X. E θ, and A S X such that π (A) > 0, the X-marginal kernel Py of involutive MCMC (Eqs. (1) and (2)) satisfies Po A) > 0.
The second assumption needed is that there is non-null set of parameters 0 E θ that can be selected and result in an accepted move from any point x, 2 E X' x Z in the original augmented space of involutive MCMC. We encode this using the positivity of the function
Proposition 4.9. For = (x, 2, a, b, 0) ~ में and all 0o > 0.
210 (1 (1-e - ( ?
(s(, < E
2)) / min(n(()
The first and second terms in the sum in Proposition 4.9 capture the expected number of doubling and halving steps, respectively. While more detailed bounds on (r 9v) re- quire problem-specifie analysis that depends on fo. n, and m, both terms will typically decay quickly in t. Corol- lary 4.10 provides an example of more detailed result based on Proposition 4.9 in a representative setting when using AutoStep with random walk Metropolis Hastings.
x, (0,00000122,,,))) n(0 ())
Assumption 4.4. There exists B θ such that f do 0 and all E X, m-aee E Z, and 0 B,
1a, z, 0) > 0.
These assumptions yield the desired result, which holds for general parameter spaces θ and distributions v).
Corollary 4.10. Let log ((x) be strongly concave with Lip- schitz gradients, and set fo as in Eq. (3) with M = I. Then
Proposition 4.5. If both Assumptions 4.3 and 4.4 hold, then AutoStep MCMC is one-step irreducible, and hence irreducible and aperiodic.
ET O(llog Pol) as Oo - 0 0o - c0,
with a dimensiion-ndeependeee leading constant.
5

---

AutoStep: Locally adaptive involutive MCMC
Corollary 4.10 shows that the expected number of doublings/halvings--ee the long-run average evaluations of fo and & per iteration-is very robust to the initial step size parameter tp. This translates to a robust performance per unit cost: in the setting in Corollary 401 we expect Au- toStep RWMH to exhibit an average jump distance per unit cost to scale like ( log Oa| 0)l for small/large 0g Contrast this to the significantly worse ((exp(- log Bul) decay for fixed step size RWMH. This difference in behaviour is con- firmed empirically in Fig. 4.
10-
Rcceptancc Probabiiity
10-
20
10
Sym, AutoStep RWMH
Asym. AutoStep RWMH
10
Laplace Cauchy
10-9
10
10
10
10
16 [H]
10'
Figure 1: Comparison of the symmetric (this work, blue) versus asymmetric ((Biron-Lattes et al., 2024), orange) step size criteria in Algorithm 2, terms the move acceptance probability of AutoStep RWMH as function of the state norm || Note that the asymmetric criterion yields very low acceptance probabilities for states near the mode (left side of the plot) and in the tails (right side of the plot).
4.4. Energy jump distance
For (ar, 2, a, b,0) n. 8' f(s) ,'' and U ~ Unif(O, 1J. define the energy jump distance
* m ((s) (())
D = 11 0)
which we use to encode the change in one iteration of AutoStep MCMC, Proposition 4. shows that any involutive MCMC method both traditional and AutoStep methods-han have an expected energy jump distance bounded above by simple expression via the tuning param- eter proposal density ratio 17.
after
5. Experiments
In this section we present empirical evaluation of two AutoStep MCMC variants: RWMH and MALA. We first use synthetic targets with varying tail behaviour to examine the effect of the symmetric termination criterion in Algorithm 2 versus the asymmetric criterion from Biron- Lattes et al. (2024), the efficacy of our proposed tuning procedure for 8y. and the robustness of the performance of our proposed method versus the initial step size 0g. We then investigate the performance of AutoStep RWMH and AutoStep MALA in comparison to previous adaptive methods.
710 fo o),b)). n,,,
1 = ess sup
(under F).
(1 v, b)
Proposition 4.11. Under Assumption 4.1,
ED < 27 max {e (e- Flog
Throughout, we measure the efficiency of each sampler in terms of effective sample size (ESS) (Flegal et al., 2008) per second. However, we found empirically that stan- dard ESS estimates (Gelman et al., 2013, p. 286-287), (Galin L. Jones & Neath, 2006, p. 1539-1541) did not ac- curately characterize sampler performance because they do not incorporate knowledge of the target distribution di- rectly. Therefore we instead use a diagnostic (KSESS) outlined in Appendix D that involves the maximum dif- ference between the empirical CDF and target CDF across all dimensions, where the target CDF is approximated us- ing a long run of parallel tempering with Pigeons. jl (Surjanovic et al., 2023). KSESS is used here solely for research comparisons and is not recommended for practi- cal data analysis, as it relies on knowledge of the target or expensive gold-standard samples. The code for reproduc- ing the main experimental results available at https: / // thub. com/ Julilalllaa aallla--eemnn www.rreeeeenntttttteeeeeeeeeeeee
In particular, for traditional involutive MCMC with a fixed parameter / = fg. or for AutoStep MCMC with x² = 0, or AutoStep MCMC with a fixed-width uniform distribution for 17. we have that 57 < 1, so
ED S 2e ~ 0.736
The step size selector presented in Section 3.1 is a computa- tionally efficient method to make [((x, 2, 8)] fall roughly in the range () log b), log al), where a, b ~ AA). There- fore, as heuristic, we expect
0.5 log bl $ E|((s, z, 0)] E log 1.5,
with departures from exactness arising due to the discrete doubling/halving procedure (as opposed to an exact root finder). In other words, the step size selector in this work creates proposals with mean energy jump distance roughly targeting the maximum zs 0.736 for a broad class of involu- tive MCMC methods.
5.1. Symmetrie step size selection criterion
We first assess the benefit of using the symmetric step size criterion in Algorithm 2 versus the asymmetric cri-
6

---

AutoStep: Locally adaptive involutive MCMC
each of the same three synthetic targets as in Section 5.1, we initialize the state x (O, 20²). ). d E {10-7.... ..... 107), and run the Markov chain for R 20 doubling rounds (= 2 x 10 steps total), tuning Bu per Algorithm 3 after each round. For each trace, we track the value of 0o as it is tuned, as well as the per iteration cost, measured by the number of evaluations of in each round. Note that fixed step size MCMC methods call & once per iteration, whereas AutoStep calls & once plus additional time for each doubling or halving during step size tuning.
16
AutoStep RWMH AutoStepp MALA
16
Normal
Laplace
16
Cauchy
16
10
10
10-
5
10
15
20
Tuning Round
(a) Values of Oo
Fig. 2 displays the results from this experiment: Fig. 2a shows the tuned values of fo as a function of doubling round, while Fig. 2b shows the corresponding average cost per iter- ation during each round. Both figures together indicate that the proposed tuning procedure is highly effective: despite the initialization of 8g spanning 14 orders of magnitude, the tuning remains stable and converges to a reasonable value of 0o ~ 1, while the cost per iteration is quickly minimized and remains stable throughout the rounds.
RWNH-
50
Normal
AutaStep
Cost per Itoratton
Cauchy
Laplace
30
10
5
10
15
20
Tuning Round
5.3. Robustness to initial step size d
(b) Cost per iteration
Next we examine the robustness of AutoStep RWMH/MALA to the setting of 0o compared with sxee-step-size RWMH/MALA. In this experiment we do not tune Oo. and fix it at values On E {(10",... ,..,, 107}. For each of the three targets from Section 5.1, and each fixed tg. we initialized each sampler at target draw, and collected various metries over 10 MCMC steps.
The effect of tuning On. showing traces of 6g (Fig. 2a) and cost per iteration (Fig. 2b) versus tuning round when 0g is initialized in {10-? ..... 107}. Despite the wide range of initializations, the tuned values and cost per itera- tion stabilize quickly and reliably.
Figure 2:
The results are presented in Figs. 3 and 4. The main compar- ison is in Fig. 3, which illustrates the difference in KSESS per unit cost for fixed step size vs. AutoStep methods, where one unit cost corresponds to one evaluation of f. For these ID unimodal targets, standard fixed step size meth- ods perform well when well-tuned. But for poor step size choices, performance decays quickly at a rate of roughly Oc fol)). In contrast, AutoStep methods incur a penalty for adaptivity, but the performance is far more robust to 6n and decays like O(1 log fol=-)) which aligns with our theory from Corollary 4. 4.10. This main compar- ison supported by additional results in Fig. 4. Fig. 4a demonstrates that AutoStep methods empirically provide high energy jump distance per iteration across all values of fg. which is valuable especially in the context of anneal- ing/tempering methods that depend on the mixing of the energy statistic (Surjanovic et al., 2024). Fig. 4b shows that the acceptance probability of AutoStep robustly remains bounded away from 0 and 1 across all values of dg. Finally Fig. 4c confirms the O() log fol) scaling of cost per iteration predicted by Corollary 4.10.
terion from Biron-Lattes et al. (2024) on three synthetic targets with varying tail behavior: (0, 1), Laplace (0, 1), and Cauchy(O, 1). For each ||=||| E (10-5, 10-1, 102). we simulated 10² draws from the target and renormalized them to the specified value. Then, for each draw, we simu- lated one step of AutoStep RWMH/MALA (0g 1), and recorded the acceptance probability.
The average of these acceptance probabilities is shown in Fig. I for AutoStep RWMH, showing that the asymmetric step size selector can get stuck for extended periods near the mode of the target (small ||=r]) and in the tails (large |æ=]]) This behavior particularly problematic in practice for Bayesian inference, which is often initialized in the tails. In contrast, the proposed symmetric step size selector is more robust, exhibiting an acceptance probability that is greater than 10% for the entire range of norms from 10 to 102. This result aligns with our theoretical results (Proposition 4.5 and Corollary 4.6) on the irreducibility of AutoStep with the symmetric step size selection criterion.
5.2. Tuning the initial step size 0o
Next, we assess the stability and efficacy of the round-based tuning procedure for og in AutoStep RWMH/MALA. For
7

---

AutoStep: Locally adaptive involutive MCMC
10
10a
K35SS per Cost
10"
10"
107
10"
K555
10
10
10"
10"
10
10
10
1.5
107
10.
10'
10
10
16
30
26'
AutoSitep RWiMH
RONH
Normal
Lagiace
Couchyy
AutoSiteo MALA
MALA
Normal
Lappace -.-
Cauchy
(a) RWMH
(b) MALA
Figure 3: KSESS per unit cost for AutoStep (blue) and fixed-step (orange) RWMH (Fig. 3a) and MALA (Fig. 3b).
hoaaton
40
10"
Cont per taeaation
10a2
Accoptance
30
16
10
10
10"6
10
10"
10'
10'
10
10
20
10"
10"
1.a
10"
10
10
20
10"
10
10"
10"
10"
AutoStop RANH
RWMH
Normal
Laplace
Cauchty
AutoStes RWNH
RWHMH
Normal
Lappacee
AAtoStep RWMH
RANH
Normal
Laplace
Cauctyy
Energy Jump Distance per Iteration
(b) Acceptance Probability
(c) Cost per Iteration
Figure 4: Energy jump distance per iteration (Fig. 4a), acceptance probability (Fig. 4b), and cost per iteration (Fig. 4c) for AutoStep and fixed step RWMH versus initial step size 0o.
et al., 2024). For AutoStep RWMH/MALA, we use round- based adaptive tuning to adjust the initial step size and diag- onal preconditioner. Our benchmarks include two synthetic distributions-NNad funnel in and 100 dimensions and three real Bayesian posteriors: three- stree-parameter linear re- gression model for yearly temperatures at Kilpisjärvi, Fin- land (Bales et al., 2019), an orbit-fitting problem (Thomp- son et al., 2024), and an mRNA transfection model (Ballnus et al., 2017).
du Autottes MALA
26 etc.
1014
ve RiaMer
1644
KSESS
16
Fig. 5 presents the results in terms of minimum KSESS across dimensions per second. This figure demonstrates that AutoStep methods consistently achieve reasonable per- formance across all five benchmarks, particularly on the challenging funnel targets. AutoStep RWMH shows com- petitive performance, generally within the range of the other methods. AutoStep MALA shows slightly lower perfor- mance some settings but exhibits better scaling higher dimensions, as in the funnel 00 results. Overall, both AutoStep variants demonstrate robust efficiency across diverse model geometries.
10736
Nunnel100
Numne
Mip sjani Model
mBMA
oftittl
Figure 5: min KSESS per second for AutoStep and state- of-the-art samplers across five benchmarked models.
5.4. Comparison with other adaptive methods
We compare the performance of AutoStep RWMH/MALA against five state-of-the-an adaptive samplers: NUTS (Neal, 1), the hit-and-run slice sampler (Neal, 2003; Bélisle et al., 1993), adaptive RWMH (Vihola, 2012), adaptive MALA (Xu al., 2020), and delayed rejection HMC (Modi
8

---

AutoStep: Locally adaptive involutive MCMC
6. Conclusion
Metropolis-adjuste Langevin algorithm. In International Conference on Artificial Intelligence and Statistics, 2024.
In this paper we presented AutoStep MCMC, a locally- adaptive step size selection method for involutive MCMC. We proved that AutoStep MCMC kernels are r-iivvariant, irreducible, and aperiodic under mild conditions. We also provided bounds on the mean energy jump distance and expected cost per iteration. We demonstrated empirically that AutoStep MCMC is stable, reliable, and competitive with other adaptive methods. One promising direction for future work is rigorous theoretical analysis of the sampling efficiency of AutoStep MCMC in terms of expected squared jump distance and asymptotic variance.
Bou-Rabee, N., Carpenter, B., Kleppe, T. S., and Marsden, M. Incorporating local step-size adaptivity into the No-U- Turn Sampler using Gibbs self tuning. arXiv: 2408. 2408.08259, 2024a.
Bou-Rabee, N., Carpenter, B., and Marsden, M. GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo. arXiv:2404. 15253, 2024b.
Chimisov, C.,, Latuszynski, K., and Roberts, G. Air Markov chain Monte Carlo. arXiv: 093009 2018.
Acknowledgements
Coullon, J., South, L.,, and Nemeth, C. Efficient and gener- alizable tuning strategies for stochastic gradient MCMC. Statistics and Computing, 33(3):66, 2023.
ABC and TC acknowledge the support of an NSERC Dis- covery Grant. TL acknowlegges the support of the UBC Ad- vanced Machine Learning Training Network. NS acknowl- edges the support of Vanier Canada Graduate Scholarship. We additionally acknowledge use of the ARC Sockeye com- puting platform from the University of British Columbia.
Duane, S., Kennedy, A., Pendleton, B. J., and Roweth, D. Hybrid Monte Carlo. Physics Letters B, 195(2):216-22) 1987.
Flegal, J. M., Haran, M., and Jones, G. L. Markov chain Monte Carlo: Can we trust the third significant figure? Statistical Science, 23(2):250- 260, 2008
Impact Statement
This work presents a new MCMC algorithm; the societal consequences of MCMC need not be discussed in this paper.
Galin L Jones, Murali Haran, B. S. C. and Neath, R. Fixed- width output analysis for Markov chain Monte Carlo. Journal of the American Statistical Association, 101(476): 1537-1547, 2006.
References
Andrieu, C. and Thoms, J. A tutorial on adaptive MCMC. Statistics and Computing, 18(4):343-373, 2008
Gelman, A., Carlin, J., Stern, H., Dunson, D., Vehtari, A., and Rubin, D. Bayesian Data Analysis. CRC Press, 3rd edition, 2013.
Andrieu, C., Lee, A., and Livingstone, S. A gen- eral perspective on the Metropolis-Haase Hastings kernel. arXiv:2012.14888,, 2020.
Geyer, C. J. Practical Markov Chain Monte Carlo. Statistical Science, 7(4):473 - -43,, 1992.
Atchadé, F. An adaptive version for the Metropolis ad- justed Langevin algorithm with a truncated drift. Method- ology and Computing in Applied Probability, 8(2):235- 254, 2006.
Girolami, M. and Calderhead, B. Riemann manifold Langevin and Hamiltonian Monte Carlo methods. Jour- nal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2):123-114 2011.
Bales, B., Pourzanjani, A., Vehtari, A., and Petzold, L. Selecting the metric in hamiltonian monte carlo. arXiv preprint arXiv: 1905.1 99999//99666 1916, 2019.
Green, P. and Mira, A. Delayed rejection in reversible jump Mettonsl Biometrika, 88(4):1035- 1053, 2001.
Ballnus, B., Hug, S., Hatz, K., Görlitz, L., Hasenauer, J., and Theis, J. Comprehensive benchmarking of Markov chain Monte Carlo methods for dynamical systems. BMC Systems Biology, 2017.
Haario, H., Saksman, E., and Tamminen, An adaptive Metropolis algorithm. Bernoulli, 7(2):223-242, 2001.
Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1): 97-109, 1970.
Bélisle, C., Romeijn, E., and Smith, R. Hit-and-run algo- rithms for generating multivariate distributions. Mathe- matics of Operations Research, 18(2):255-266, 1993.
Hoffman, M. D. and Gelman, A. The No-U-Turn Sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. The Journal of Machine Learning Research, 15 (1):1593-1623, 2014.
Lattes, M., Surjanovic, N., Syed, S., Campbell, T., and Bouchard-Côté, A. autoMALA: Locally adaptive

---

AutoStep: Locally adaptive involutive MCMC
Kleppe, T. S. Adaptive step size selection for Hlessan-bbsse manifold Langevin samplers. Scandinavian Journal of Statistics, 43(3):788-805, 2016.
Roberts, G. and Rosenthal, J. General state space Markov chains and MCMC algorithms. Probability Surveys, 1: 20-71, 2004.
Kolmogorov, A. Sulla determinazione empirica di una legge di distributione. Giornale dell' Istituto Italiano degli Attuari, 4:83-91, 91, 1933.
Roberts, G., Gelman, A., and Gilks, W. Weak convergence and optimal scaling of random walk Metropolis algo- rithms. Annals of Applied Probability, 10-:11,--20, 1997.
Livingstone, S. Geometric ergodicity of the random walk Metropolis with position-dependent proposal covariance. Mathematics, 9()) 2021.
Roberts, G. O. and Rosenthal, J. Optimal scaling of discrete approximations Langevin diffusions. Jour- nal of the Royal Statistical Society. Series (Statistical 1998.
Maire, F. and Vandekerkhove, P. Markov kernels local aggregation for noise vanishing distribution sampling. SIAM Journal on Mathematics of Data Science, 4(4):
Methodology),
Rossky, J., Doll, J. D., and Friedman, Brownian dynamics as smart Monte Carlo simulation. The Journal of Chemical Physics, 69(10):46284466 1978.
1999,1319,00 2022.
Marsaglia, G., Tsang, W. W. and Wang, J. Evaluating Kol- mogorov's distribution. Journal of Statistical Software, 8 (18):1-4, 2003.
Surjanovic, N., Biron-Lattes, M., Tiede, P., Syed, S., Campbell, T., and Bouchard-Côté, A. Pigeons.jl: Distributed sampling from intractable distributions. arXiv:2308.09760 2023.
Marshall, T. and Roberts, G. An adaptive approach to Langevin MCMC. Statistics and Computing, 22:1041- 1057, 09 2012.
Surjanovic, N., Syed, S., Bouchard-Cöté, A., and Campbell, T. Uniform ergodicity of parallel tempering with efficient local exploration. arXiv:2405.1 1384, 2024.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087-1092 1953.
Thompson, W., Lawrence, J., Blakely, D., Marois, C., Wang, J., Giordano, M., Brandt, T.,, Johnstone, D., Ruffio, J.-B., Ammons, S., Crotts, K., Do Ó, C., Gonzales, E., and Rice, M. Octofitter: fast, flexible, and accurate orbit modelling detect exoplanets. The Astronomical Journal, 166(164): 1-20, 2024.
Modi, C., Barnett, A., and Carpenter, Delayed rejec- tion Hamiltonian Monte Carlo for sampling multiscale distributions. Bayesian Analysis, 2024.
Neal, R. MCMC using Hamiltonian dynamics. In Brooks, S., Gelman, A., Jones, G., and Meng, X.-L. (eds.), Hand- book of Markov chain Monte Carlo, chapter 5. CRC Press, 2011.
Tierney, L. note on Metsonolis-Hasttngg kernels for general state spaces. The Annals of Statistics, 8(1):1-9, 1998.
Neal, R. M. Bayesian Learning for Neural Networks. Springer New York, 1 edition, 1996.
Tierney, L. and Mira, A. Some adaptive Monte Carlo meth- ods for Bayesian inference. Statistics in Medicine, 18 (17-18):2507-511 1999.
Neal, R. M. Slice sampling. The Annals of Statistics, 31(3): 705-767, 2003.
Turok, G., Modi, C., and Carpenter, B. Sampling from multiscale densities with delayed rejection generalized Hamiltonian Monte Carlo. 2.Xiv:2406.027441 2024.
Neklyudov, K., Shvechikov, P., and Vetrov, D. Metropolis- Hastings view on variational inference and adversarial training. arXiv: 2018.
Vihola, M. Robust adaptive Metropolis algorithm with coerced acceptance rate. Statistics and Computing, 22(5): 997-1008, 2012.
Neklyudov, K., Welling, M., Egorov, E., and Vetrov, D. In- volutive MCMC: A unifying framework. In International Conference on Machine Learning, 2020.
Xu, K., Ge, H., Tebbutt, W., Tarek, M., Trapp. M., and Ghahramani, Z. AdvancedHMC.ji: A robust, modular and efficient implementation of advanced HMC algo- rithms. In Proceedings of The 2nd Symposium on Ad- vances in Approximate Bayesian Inference, 2020.
Nishimura, A. and Dunson, D. Variable length trajectory compressible hybrid Monte Carlo. arXiv:1604.0080 00089, 2016.
Polson, N. G. and Scott, G. On the half-Cauchy prior for a global scale parameter. Bayesian Analysis, 7(4):887-903 2012.
10

---

7(s²) AutoStep: Locally adaptive involutive MCMC
A. Proofs
Proof of Proposition 4.2. The auxiliary refreshment and tuning parameter refreshment steps in AutoStep MCMC (Steps and 2.) resample (z, a, 0) jointly from their conditional distribution given under и. This move is well-known be ø-invariant, and so it remains only to show that the cetropolii-correetee involutive proposal (Steps and 4.) is --invariant. The kernel for the proposal on the augmented space S is
Q(s, (d))(ds),
and the acceptance probability : S RR is given by
als, = min 1, R(s) [(s}
In the notation of Tiemey (1998, Theorem 2), define the measure p(ds, ds') {dss) (co) because f an involution, we have that the symmetric set R and density ratio r R R4 given by
#(ds) f(a) (ds')
R = ((s,s') E S² F(s) = ss) O, x(s) > 0}, r(s, = 7(s') ((0r) (ds)
Note that condition (i) of Tierney (1998, Theorem 2) holds by definition of R and a. Suppose for the moment that r(s, s') = x(() x()) Jss); then condition (ii) and hence Æ-invariance holds because
7(s') (s))
T( ((') min { a(s) F(5') J(N))))) a(s'
als, ((s,"'r(s,s'') min
((s)
((3')
which follows because J(s)J(s')= p-a.e. R. To demonstrate that 8') has the required form, consider test function g 2 R:
I ((d)))))((s)) = / g(s, f(s))
/ g((x, z, a, 0), (fe(z, a,, b,),,, 0)dzdzd(a, b)d0.
Since ʃo continuously differentiable involution, term J(s) fo( =)] in the integrand and by noting x, = fo(x',2'):
transform variables x', So (3r, 2) by including Jacobian
a((fo(=', z)) a,0,), (x',2' a' (.
fe 2') de'd b)d0
/ s')
/ ((F(('), (f(s))) J(s ((s')T(ds') ((s!)
((s) f (( - J(s (dd' (dy)
Examining the first and last integral expressions, the density ratio has the form
r(8,8' x(ds)) (ds') #(s) J(S). ( x(s')
Proof of Proposition 4.5. Let (xx,)) denote the Markov kernel for the X' X'marginnal process of AutoStep MCMC. Since for u, 2 0, min(1, wn) 2 min(1, u) min t). we have that for = (x, 2, a, b,0).
min(1 (((()) J(s) 2 min (lnr)))) min { I, n(0 so 2), a, F(s)
(0 x, z, a, b)

---

AutoStep: Locally adaptive involutive MCMC
Therefore
((x,A) A) 2/ / 1[)((12)) E A 2 min 1, ) } min 1, n(0 fo(a, 2). a) a)
v/0 2, mid0 x, a, (dd(a))
/ ([)((,,)) E x 2) mi 1, Jo 2,(,,
where
((2,2,0) = min(n(0 z, b,,,,,, a,)),,)))a((dl 6)).
By Assumption 4.4, for all m-a.e. 2 2, and for all where Sg d0 > r(x, 2, 0) > 0. Therefore
/ ([f0(112) E A 2] min 1, e, (l (xx 2, ()m(())111 Bjd0
/ 11fo(z,2) E Ax 2) min el mm(d)) Bldø > 0.
The proof concludes by noting that
/ [[)o(1,)) E Ax 2] min mini ()2 1, }m(d=)110 ( BJdo = Pole, A)1 BJd0,
Pole
where (o(x, A) is the one-step probability of transitioning into A from æ for the original involutive chain with parameter 0, and then by applying Assumption 4.3.
Proof of Corollary 4.6. The proof involves verifying Assumption 4.4. Note that d0 is the counting measure on {0 Ao 25 j E z). Consider setting B {0o]. Assumption 4.4 holds if for all x E X and m-ae. 2 E Z,
f niu(z,2,a,b) Ou = (2, (d(a, 0.
That is, if there is nonzero probability of choosing the default parameter 0n at any point (x, =). Note that
p(x, a). b) = -b = m[foo (z, 2), a,,a, a. b) + log(a) < {(x, 2, 0u) < log(b) or log(a) < -1(x,22, 2, 0o) < log(b).
By assumption, for all x E X' and m-a.e = E 2, we have f(r, 2, 0n) & (-,,,,,,000 xo). If f(x, 0n) > 0, then when a < exp(-E(x,,4 00)) < b we have the condition hold. This has positive measure under 1 (d(a, 6)). If f(x z, 0o) then when exp(e(xx, 2, 0o))
the above condition holds. This set also has positive measure.
Lemma A.1. For the AutoStep RWMH kernel with any fixed > O, x E X. and C & with T(A) > 0, we have Po(a, A) > provided that (2)) > 0 for all E X.
Proof of Lemma A.I. Fix A > 0, C X' with T (A) and X. Because π & X, we have A(A) > By translation properties of the Lebesgue measure, for any Rd X(A) X(A x) > where A r {ā 5 A]. Here, 2') (z 2) (x + 2, 2)) and so V (z, =) = 1. Also, since
where ~N I), we have
((x')
{lx,2,0) = log
T(x)
Then,
Pa(x, A) 2) 2 / 1[2 E A- x] min ( 7(x + 2)
m(()) A(dz) > 0,
(xx)
because for all x, 2 we have X(A - -x) 0, m(=) > and min (1, (( + 2)/x(r)3 0.
min(1,
12

---

AutoStep: Locally adaptive involutive MCMC
Lemma A.2. For the AutoStep MALA kernel with any fixed 0 >
X, disserentiable n, positive definite M, and A X with =(A)> O, we have Po(x, A) provided that x (x)) > 0 for all x E X.
Proof of Lemma A.2. Fix 0 0, A c X' with ((A) 0 and E X. Because < X, we have M(A) > O. As in
(Biron-Lattes et al., 2024), we combine the updates on (z, 2) into one step, so that (0 2) ('))) where
0² .M 1.MVViu Vlo (z),
0 v Vlog (x) Vlo (1'g)
(0) x + AM
='(0) 2 2
2
Now, z0) E A if
M(i - x)
A
v log ((x) Vlog
3 A
0
By translation and scaling properties of the Lebesgue measure, for any x E R x(Ax) > 0. It is standard result that the leapfrog integrator satisfies V fo [x) 1. We have
x()))((z')
2(x, = log
x())m(2)
Then,
Po A) / 1[z Aa) min
x (<')m((z) (z))(=)
((dz) A(dz) > 0.
because for all x, 2 we have X(A+) 0, m(2) > and the acceptance ratio positive.
Proof of Proposition 4.8. We generalize the step size termination proof of Theorem 3.3 by Biron-Lattes et al. (2024). Consider first the case where v = 11 Since for m-a.e. J, 2, lim [E(x,, 2, 0)1 0, and log al > 0 almost surely, there exists 8' > 0 such that 40 < 0 < 8', [((x, 2, 0)1 < log a). Therefore there exists a j < 0 such that 2'0 0 and the while loop terminates. Next consider the case where 1. Since for x m-a.e 2,, limo 1e(x, z, 0) = co, and log b| < co almost surely, there exists 0' > 0 such that > 0', |6(x, 0)l > log b). Therefore there exists a j > 0 such that 2 > and the while loop terminates.
Proof of Proposition 4.9.
00
Er(s, Σ
Po) t)
max
z, 2, < |log bogblu
U
min -1si50
10(x,, z, 2, 2'0o)1 > |logal
05151
max 2, < 05
|lggb| +P
min -55300
1((x, 2, 2,22 > |loga]
2(]l(1,,,, 2, 2'0b < |lgbb) +((((,,,,2 > |log al)
P(ll(z, z, 2'00)l < - logb) + P((e(1, 2, 200)) > - log a)
Σ
( |( > >) + AP 00 <n).
Since b are uniform on 0 < < bs 1 1,
Pa(a x) = (1-x)² and P(b < x) x²
13

---

AutoStep: Locally adaptive involutive MCMC
s0
(s 0b) - Be
00
20
6o)1
+1 (1 ( (1--=
(c, 2) m.
Fubini's theorem completes the proof.
Proof of Corollary 4.10.
The involution for RWMH with M = is given by
(0( (x + 0z, -2), = 10,
Therefore,
T(I + (2)) (0).22(mm2 = llog m( + 0z) {(x)m(2)
E(ar, 2) log
log π (xr).
Since log π is I-Lipschitz smooth,
10(x,22 S 5 log (<))22| 21 2 _
Therefore,
e- M00))2)))))
2 Voo -1=111)11=11))))))))) 11==1p))
1=
t=
- 2e 2 20 V (()) =1 0611=11
+ t 2.222 m()) L|444")) 14--%% 081|=]]
t=0
Furthermore, note that (1 e #)² < min(x² 1) for 0. Therefore,
e 2(,,,,, '6021)
2
5
min
0
tm
1 (2-'0//VoogT() (c) 2/ L4 00/1111
min
t=
4-1 4-1 001 4-1(
_08112113 )11)
1
<
min
t=0
Let to [max (0, (3/2) log(
log (x)
=0 Then,
-
-- -(00022002)0000
5
1+
1- 0o (olo
1 1011=1112
0=0
1=0
t=to
lg +
4 4
0o
(o/Vlog)())) +|
T =|
t=0
< to +
4- < to + +433.
1=
Next, since log ग is U-strongly log-concave,
(xx,,00) < 0V (o))(s)²=
1002
-
14

---

AutoStep: Locally adaptive involutive MCMC
If V lo) O, then
1 2,,,, 0 V log (<>)>>) 2 110 - -1001=111- ov log (2)"² 2.
On the other hand, if V log n (z)"² > 0, then
(0(x,,,0) {
0 2V log x(r)²
U||
=10 ov -ogg</)))>
0
U|
Taken together, for 2 0,
2V log (x))²
1 1 oV log (x))
(e(z,2, 2, 0) 2 1
0
11=112
2V log (x:)² ++11 1
0
1
oV [Vlog(())
U1
So,
200 -2.2'
e
21
<
e
11
0=
1=
2//2 -2.21001
9ol
10/300 2
28 lor
0=
Let to [max(0. -0.g3...0/ (3/2) log
2V log
(x)) x-1 |||
where log of negative number is taken to be -00. Then,
f-
2'0001
2.2 21 (og)
1=0
1=
4-1
2/22
$
1=1
2041/
$ 1/
t=0
00
< 1 +
dt
J0
2
8cc
to +
11
dt
log 2
3 < 6 4
Combining the above two bounds, well as the bounds [x] x for 0, w |||||||a|| for vectors u, and |/V log क [I) < [||=||| for an L-Lipschitz smooth function (without loss of generality, assume . ((x) reaches its maximum and has V log π (x) = 0 at x = 0):
4 3
Er(s, 06) < Elo + Ed + - +
3 4
3 2
2T ||||=|||||||| + +1) 21
)).
< 5 + 3 log 11 + 1)51)
E Elog + 0|1||=1||=11 + L 1111)112)
+ Elg
1+
2
Jensen's inequality yields
1 Er(s, 0p) s 5 5 3loglog(11 (1 + 1) log 1 0,111111111111 + L0
3
2T B|<||| + t1) 00,1==12
E Elog
1+
15

---

AutoStep: Locally adaptive involutive MCMC
Since NN(,,) 1) in Rd.
[ d+1
B||||| = V2
S (d (d+1)
and E||=|| = d,
where the bound on E||=|| follows from Gautschi's inequality. Since x has a strongly log-concave and Lipschitz smooth density,
I clog n(x)
|x||| dæ
(2mU-1)d/2) (2mb 1837 e "ell ||-||| da
U1(4+1//111111
L 1)1/2
E |||
ʃ plog m(ar) dæ
(2
(2xl (2x1-11a/2 11a12 [|1211 dz
I. I.-d/2
U(d+1)/2
Finally, for any a. b O,
a||2|| +
a||=|| + 1
a||2|| +
E log 1
[1||]]]|
1] log
1+
EI |||||| 1] log
1 1
b/|2|1
b||ıI|2
b||=||
+++1
a||=|| +
|1[||=
log
1
+ |1[|
2 1] log
b||=||2
b
a+1
1+ aB||2|| +
< [||[||=|||
log
+ log
b||=||2
1+ + 1
aE +
1||==||
1]
dt + +log >6
1 1+
b||=1|2
b
||=|| min
0
dl log 1+ aB|[2|| +
b(et -1) 1)
100
ming 1
aE |
+1
4/2-1 --- -/2/ ds + +og
1+
0
b
)
4/2 14/2-d dt + log
1+ ald + 1)1/2
24/'T
00
2
a 0+1
})
d/2
ald + 1)1/2 +
blet 17
dt + +to log
1+
Jo d24/2T(d/2)
Jog( 14
4/2
2
a+1
(2d/2T(d/2)
dt+ + (08(1++929)
b(et - 11)
dt
ald + 1)1/2 +1
+ log
1 1
b
d/2 | 1og(1+
2
log 1+ a a
- 1 b
(et -6--1)-44 11)-12d dt
+
d24/2T(d/2)
aid + 1)2/2 +1
+ log
1
b
2
log 1 1+ =+1)
- 1
d/2
-dd/2 ex
1 1 c d8
d2</2T(d/22
)lg(
16

---

AutoStep: Locally adaptive involutive MCMC
a(d + 1)111/2 +1
+ log
1+
b
2
log 1+ a a
a - 1
d/2
cdd/
c
(22/2I(d/2)
b
108(2
ald + 1)2/22 +1
+ log
1+
b
d/2
1 -a/2)
2
8o0 1+ a a+1)
a -
(24/2T(d/2)
+
b
a(d + 1)1/2 +1
+ log
1+
b
2
++11 1
2 + log 1 a(d add 1)1/2 +
Bog 1+
(24/2T(d/2)
6
b
Therefore, the final bound is
Er(s, 00) S 5 + 3log (1 + 0) + 3
(d
log 1 1 OoL Uld-1)/2 (d ( (d+1) + Lo8d
2
1+ |||
(14
+1
+ E log
U0
3
(d
1
< 5 + 3 logg
+ 0)=²)
+
log
1 + 0oL
2
U(d+1)/2
2
(d41))+
2L I. (d++1)
+
2 log
1+
2L
+1
+
2
+
3
log
1
Tica-172
+1
(d22//((d/2)
U0o
d
2
U0a
6
3
< 5 + 3logg 0)
+
log
1 OOL
+ LORd
2d/2
U(d+1)/2
2
2L
+1
+1
log
1
24/2
UBo
The result follows by inspection of the above bound.
Proof of Proposition 4.11. The expected jump distance is
ED / |[ 0) min { 1, (c..2,0) (00lfo(z a,b) n1 10 2,
( b)) x 2,
Let Ag {2, 2, a, b, exp(e(x, z, 0)) < (0(,,, z, a, b) (O),fa 2), a, b)}. and define A2,A2, similarly by replacing the inequality in the definition. We begin by splitting the integral into regions Aç, As:
/ (dd > 2,,,,,
ED =
A
+ 1 A
b)))
Next we perform the transformation of variables x' = Sola, z) on the A integral. Recall that f(x, 2, 0) satisfies
((fo(z 0) -((x, -1(xx,,00 0),
17

---

AutoStep: Locally adaptive involutive MCMC
and note that this transformation yields the integration region Ac, such that
ED = J 10(x, 2, ( a1 (d) AC
She 10(2, 0)e ( hatpa///hhhcllcccccaaacccccccaaa d)
The upper bound follows by combining the two terms and bounding the 1) ratio:
(7 a), ED s 2 / 10(x, 0)1c
n000,, x. 2. ()d0)) xr 2, a, ()(d))m(m))((11 b)))
As
$ 27 sup (ule"
v
< 2n sup lyle"
vSlog π
2n max f 17 1)
18

---

AutoStep: Locally adaptive involutive MCMC
Model
Dimension
mRNA
5.767
orbital
12
5.389
kilpisjarvi
5.9561
funnel2
5.960
funnel100
100
72.551
Table 1: The scaling constant for each model, mentioned in Section 5.
B. Additional Experimental Details and Results
B.1. Synthetic and real data models
We present the synthetic and real data models used in Section 5. In the following, (N,, represents normal distribution with mean and variance o². We use N(u, a²; br., bu) to denote a truncated normal distribution with bounds (br., bu).
The Neal's funnel with d dimensions (d 2 2) and scale parameter T > 0, denoted by funnel(d, 7), is given by
X1 (O 9), X2. Xa X1 21 idd
MO, (exp(æ1/7))*).
For the 2-dimensional funnel we used 0.6, and for the 100-dimensional funnel we used 6.
Thee mRNA model with N observations, the time E RN,, and the observed outcomes E R- is given by
1og10(4) ~
Uniform( -2, 1)
10g10 (kp) ~ Uniform( -5,5)
login(3 (3) Uniform (-5,5)
logio ()) Uniform( -5,5)
logı0 (r) Uniform 22
0,
4 - ln S 0
14 = kn exp(-3 (t, to)) exp(-1p 8. (t, - to))
i # 8
1 = 1, 1...,,N
d- 3
ko (t: - -to);
= 8
Vi Pi, ((u, o²), i N.
The kilpisjarvi model with the predictors x E RN,, the observed responses y E RV,, and additional parameters Pos M3,, on, is given by
a N(Hn, 2
8 N1
N;0,
Vi az, 8, o, x; N(a Br, o²), 1, I....,N. N.
In our experiments we used Ha 9.313, μ4g 0, 0. 100. and 03 0.0333.
The orbital model is a model of the multiple system Gliese 229 available in Octofitter.ji (Thompson et al., 2024) at j1.
B.2. Estimation of scaling factors
We measure the cost of each method by Nr + aNg. where N₂ and Ng are the number evaluations of log x(-) and v log TT-), respectively. We use a as target-dependent scaling factor to balance the cost of gradient and density evaluations.
19

---

AutoStep: Locally adaptive involutive MCMC
10a
10
Acceptance Probability
10"
10-3
10a
Sym, AutoSSopp MALA
Asym, AutoStep MALA Normal
10"3
Laplace Cauchy
10-
10
10
10a²
10
10
10
[+]|
Figure 6: The same comparison as 1, except for the MALA involution instead of the RWMH involution.
To determine a, we ran three separate Markov chains using Pigeons to obtain draws, benchmarked the time required for gradient computations, and benchmarked the time for log density evaluations. The scaling factor a is then obtained as the ratio of the total time spent on gradient evaluations to the total time spent on log density evaluations. The chains are long enough such that the estimate error (in absolute difference) is within 2%. The a values used all experiments are presented in Table 1.
There seems to be a positive correlation between and the dimension of the problems. This correlation is likely due to the auto-differentiation system used to compute gradients. While auto-differentiation avoids the need for manual differentiation, it appears to incur a computational cost that increases with dimensionality.
B.3. Algorithm Tuning Parameters
We provide the detailed tuning parameters for the samplers compared in Section 5.4.
Adaptive MALA: Step size 0n- = 0.1.
Delayed Rejection HMC: Step size 0g 0.1, number of subsequent proposals h: 2, and step size divisor a 5.0.
NUTS: Maximum tree depth Lmax 5 and target acceptance ratio Oturget 0.65.
B.4. Additional results
Additional results for the experiments in Sections 5.3 and 5.1 are presented in Figs. to 8. In particular, Fig. 6 shows the same comparison of symmetric and asymmetric step size selectors as in Fig. 1 in the main text, except for the MALA involution. The conclusion here is slightly different for MALA than for RWMH; both asymmetric and symmetric step size selection yields reasonable acceptance probabilities near the mode, while both have decaying acceptance probabilities in the tails. However, despite the decay, the symmetric criterion still yields a substantial increase over the asymmetric criterion, and should still be preferred. Fig. shows the same additional metrics as Fig. 4 when comparing fixed step sizes AutoStep (energy jump distance per iteration, acceptance probability, and cost per iteration) but for the MALA involution. The conclusions for MALA drawn here precisely the same those for RWMH. Finally, Fig. 8 shows the expected jump distance for fixed and AutoStep RWMH and MALA; these plots show the expected decay of at least e Qul for fixed step size methods, and log 0ul 1 for AutoStep methods. It is worth pointing out that the expected jump distance for fixed step size RWMH on very heavy tailed targets (like the Cauchy) can be quite high, but indicates a few very large jumps rather than good mixing behaviour.
We also present additional results in Fig. for the experiments in Section 5.4. The minESS metrics were computed using the method described by Geyer (1992) in Section 3.3, which we found to be more reliable than the default settings in MCMCChains.
C. Reference pair plots
Figs. 10 to 14 display pair plots of the reference draws for each of the experiments in Section 5.4. Each set of reference draws contains between 106-107 draws. These draws were used for computing the KSESS estimates.
20

---

AutoStep: Locally adaptive involutive MCMC
10
Energe Jamp Dut leretton
20"1
Coal per (teration
10
20
20"4
10
10
10
105
10
1P
20"
10
10"
1.5
10
16
10"
20"
10"
16'
10"
16.
16
WALA
Cauchy
AutoSSopp
Lpplace
(a) Energy Jump Distance per Iteration
(b) Acceptance Probability
(c) Cost per Iteration
Figure 7: The same metries as presented Fig. 4, except for the MALA involution instead of the RWMH involution.
18
10
Diz por Cont
10"
10"
jumo Ouno
10"3
lumo Dist
10"3
16
10a
10"
AutoSttes
Normal -- Laplace -..- Cauchy
AutoStop MALA
VALA
homal
Laplace
Caucty
(a) RWMH
(b) MALA
Figure 8: The jump distance per iteration for AutoStep and fixed step RWMH (Fig. Sa) and MALA (Fig. 8b) versus initial step size 0g.
(a) minksEsS per unitcost
(b) miness per second
(c) miness per unit cost
Figure 9: The same comparisons as 5, except that we present MinKSESS per unit cost (Fig. 9a), minESS per second (Fig. 9b), and nESS per unit cost (Fig. 9c), instead of nKsSss per second.
D. KSESS diagnostic
Suppose we obtain a collection of i.i.d. draws (xr)²= from a target distribution with known CDF F(x) (or given a sufficiently large set of draws (Z,) T > T such that the empirical CDF of (z.) can be used in place of F). For any T N, define
D((x))=11) = supp F(x)).
21

---

AutoStep: Locally adaptive involutive MCMC
where Fr(x) is the empirical distribution of (xx) It known that vT D(()) 4 K as T - oo where K follows the Kolmogorov distribution (Kolmogorov, 1933) (see also Marsaglia et al. (2003)),
V2T
(2k-11 2
P(K 2x)
k=1
K = log 2
2
T²
π (log 2)
Var[K]
12
2
Heuristically, given a sample of size
BB, we have that as N, - 0c.
N-1
Σ
VB (z. (2+) = E[K],
N T=0
and hence the sample size T' is approximately
log 2 2
T R KSESS :=
T
I VBD ( b
If instead of exact Monte Carlo draws from the target, we obtain draws from (potentially slowly mixing) Markov chain, expect the D statistic to follow a convergence law roughly of the form VaT ((x;)(()))T=))) 4 K, where aT is the effective sample size. In this case,
Va log 2
KSESS T
N D vaBi (x0)
2 =T(va)==ol aT,
as desired. However, this doesn't measure severe failures well; note that the minimum possible value of KSESS, is Tlog 2/B))/B. which occurs when D = for each batch (i.e., when the sampler is working as poorly as possible). Hence we also consider the metric
2
R KSESS2 = log 2
D((()))(
which characterizes severe failure, but has too high variance to be useful when the sampler functioning well. Hence the final KSESS metric use is
KSESS² KSESS)
KSESS² S 2
KSESS
otherwise
In our experiments set N 40.
22

---

AutoStep: Locally adaptive involutive MCMC
0.6
2.7
0.0
114
1.5
1.5
100
50
2
0
-50
-100
-15
-10
5
0
5
-100
-50
0
50
100
2
Figure 10: Reference samples for funnel 2,
23

---

AutoStep: Locally adaptive involutive MCMC
0.0
0.0 1.0
20
X2
-20
0.0 + 1.0
40
20
10
X4
-0
.20
0.0 1.0
20
X5
20
40
-10
20
70
x3
x5
Figure 11: First 5 dimensions of the reference samples for funnell00
24

---

AutoStep: Locally adaptive involutive MCMC
611
0.018 + 0.007
0.04
0.02
x2
0.00
1.13 0.10
+0.11
1.50
1.5
X3
1.25
1.00
-150
-100
-50
50
0.00
0.02
0.04
0.8
1.0
1.2
1.4
1.6
X1
x2
x3
Figure 12: Reference samples for kilpis jarvi.
25

---

AutoStep: Locally adaptive involutive MCMC
0,95
0.436 + 0.010
0.46
0.44
x2
0.42
0.40
0.98 -93
-2.5
5.00
10.0
12.5
0.310 + 0.021
-0.30
-0.5
-0400
0.100
0.50
0.45
0.40
0.35
0.30
0.6
0.7
0.8
0.9
1.
0.40
0.42
0.44
0.46
110
-040
-0.35
-0300
-025
0.30
0.35
0.40
0.45
0.50
Figure 13: Reference samples for mRNA.
26

---

AutoStep: Locally adaptive involutive MCMC
$
Figure 14: Reference samples for orbital.
27


Reviews:
[{"review_id": "mzxYCRMwsa", "reviewer": "Reviewer_JzQk", "summary": "This work proposes a framework for adaptive MCMC that enables sampling parameters to be optimized for the current location in the state space at each sampling step. In particular, the work focuses on adaptively adjusting the step size parameter which is found in common MCMC algorithms. The key challenge for such an approach is maintaining detailed balance, since naive adjustment of the step size could disrupt the MCMC process so that it no longer follows the intended stationary distribution. Building upon established properties of involutive functions for MCMC sampling, the work proposes to augment the sampling space with a distribution over soft acceptance bounds and a distribution of the step size parameter that depends on the current state, MCMC randomness, and the soft acceptance bounds. By carefully formulating this involutive function, detailed balance can be guaranteed by standard results about involutive MCMC, and irreducibility and aperiodicity proofs follow in a straightforward way from the irreducibility and aperiodicity of the non-augmented MCMC samplers. A theoretical analysis of the time for selecting a step size and for the expected movement with each sampling step is presented. Experiments are conducted showing that the method achieves similar efficiency regardless of the initial step size parameter tuning, favorable comparison with the related adaptive step size selection method AutoMALA, and competitive performance with other adaptive MCMC samplers.\n\n\\## After rebuttal: My view of the paper remains similar. The proposed method is a straightforward and natural way to incorporate adaptive step size in standard MCMC algorithms. Although the method currently does consistently not surpass strong samplers like NUTS, it is possible that future design choices based on this sampler could provide further improvement.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful questions. We hope that our answer will address all your concerns. \n\n> The proposed method does not achieve top performance on any specific scenario.\n\nWhile AutoStep does not outperform all other methods across all examples, we would like to emphasize that it consistently performs well across a wide range of scenarios. This broad robustness is due to the local adaptivity of AutoStep: it is resilient to the choice of initial value $\\theta_0$ and the geometry of the targets, albeit with some additional cost associated with tuning $\\theta$ at each step (Figure 2).\n\n> It is claimed that ESS did not accurately characterize sampling performance, but few details are provided about the inadequacy of ESS and the superiority of KESS.\n\nThank you for bringing this up, this is an important point! Standard ESS estimates do not incorporate knowledge of the target distribution directly, and so can indeed be misleading if the sampler fails to explore the target distribution (Elvira et al, 2022). As an extreme illustrative thought experiment, if the sampler fails severely and does move at all, the sequence of states is indistinguishable from an iid sequence from a Dirac delta, and typical ESS estimates will report a high value despite the correct value being approximately 1. We saw a version of this issue in our experiments; for example, in an experiment using adaptive RWMH on the kilpisjärvi model, the sampler produced samples with almost no spread (variance on the first dimension was 2.472e-6), and yet the minESS reported was 45.47. In contrast, KSESS reported 0.75, which correctly identified the sampling failure. In other words, the traditional ESS estimate was nearly two orders of magnitude higher than it should have been.\n\nNote that we do not recommend using KSESS estimate in practical data analysis, as it requires knowledge of the target or expensive computation to obtain a gold-standard sample set. We use the KSESS only for the purposes of comparing different sampling methods in a research context. We will clarify this in the camera-ready.\n\nElvira, Víctor, Luca Martino, and Christian P. Robert. \"Rethinking the effective sample size.\" International Statistical Review 90.3 (2022): 525-550.\n\n> It must also be shown that the proposed sampler is not null recurrent to establish ergodicity. Can this be shown?\n\nThanks for the question! Please note that for ergodicity (i.e., an MCMC law of large numbers for $\\pi$-a.e. initial state), it is sufficient that the chain is $\\pi$-invariant and irreducible. Our theory provides these two statements. See, e.g., Theorem 5 of Geyer’s lecture notes on Markov chains at https://www.stat.umn.edu/geyer/8112/notes/markov.pdf — per the discussion on p12-13, stationarity can be replaced by $\\pi$-a.e. initialization and $\\pi$-invariance. We do note that if one wants a central limit theorem, more analysis and conditions are required.\n\n> Given the strong performance of NUTS in Figure 5, is it possible to combine the proposed method with NUTS to further improve performance?\n\nThis is a very interesting point, thanks for bringing this up! The AutoStep framework is naturally applicable to all involutive methods with step size parameters. We think it is likely that with the right augmentation, one could view NUTS as such an involutive MCMC scheme, but we are not totally certain and leave a detailed development of that to future work. It can certainly be applied to HMC which is known to be an involutive scheme.\n\nHowever, HMC (and NUTS if it turns out to be involutive) involve a fairly expensive involution. Based on our experiments to date, we suspect that methods with cheaper involutions (like RWMH, MALA) are likely to benefit more from using AutoStep. In particular, we have conducted preliminary experiments with AutoStep applied to HMC with a reasonable path length, and the results suggest that the minESS per cost achieved by AutoStep HMC is approximately 30% of that achieved by traditional HMC with hand-tuned \"optimal\" parameters on benchmark problems. However, those results are very preliminary, and it is possible more engineering effort could improve AutoStep HMC further.", "claims_and_evidence": "The theoretical claims appear valid to me. Involutive MCMC in the augmented sampling space that includes a distribution over acceptance probabilities and step size parameter is a very clean way to include adaptive step size selection while still satisfying detailed balance. Experimental results provide convincing evidence that the method is extremely robust to the initial step size tuning over several orders of magnitude. The comparison with existing adaptive MCMC techniques shows competitive performance with existing adaptive methods as claimed, although the proposed method does not achieve top performance on any specific scenario.", "methods_and_evaluation_criteria": "The overall methodology of using involutive MCMC to build a framework for adaptive step size selection seems very appropriate for the problem at hand. The experimental section provides a fairly thorough comparison of the proposed method with representative SOTA methods. One major choice that does not follow standard methodology is the use of a newly proposed metric KSESS to measure MCMC sampling efficiency rather than the typical ESS method. It is claimed that ESS did not accurately characterize sampling performance, but few details are provided about the inadequacy of ESS and the superiority of KESS. Further explanation of this choice would greatly help to solidify the evaluation methodology.", "theoretical_claims": "A variety of theoretical claims are made in this paper. The most important ones are that the proposed method satisfies detailed balance and that the proposed method is irreducible and aperiodic. I carefully checked these claims and they appear valid. These proofs are fairly straightforward thanks to the clever MCMC formulation. Theoretical results about the expected runtime of step size selection and the state space movement of the proposed method are presented. These claims appear reasonable but I did not carefully check the proof details.", "experimental_designs_or_analyses": "Overall, the experimental design and analysis is appropriate. As mentioned above, the one major area where the experiments do not follow the typical protocol is the use of KSESS as a replacement for the standard ESS metric to measure sampling efficiency. More discussion of this choice would strengthen the paper.", "relation_to_broader_scientific_literature": "This work seeks to provide a principle framework for including an adaptive step size parameter in common MCMC sampling algorithms. Prior works are limited by being restricted to a pre-selected set of step sizes, restriction to use the same step size across the entire state space, or limitations on how frequently the step size can be adjusted during the MCMC process. The present work provides a clear and straightforward way to adjust step sizes that can span a vast range of orders of magnitude, is adapted at each new state space location, and can be adapted at each step. Such methodology has the potential to be widely adopted by the community. Nonetheless, while experiments show the proposed method has reasonable performance, it does not have top performance in any given scenario.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* This work demonstrates detailed balance, irreducibility, and aperiodicity for the proposed sampler. However, it must also be shown that the proposed sampler is not null recurrent to establish ergodicity. Can this be shown?\n* Can you provide a detailed explanation of the shortcomings of ESS and superiority of KSESS? A convincing answer to this question could cause me to increase my rating score.\n* Given the strong performance of NUTS in Figure 5, is it possible to combine the proposed method with NUTS to further improve performance?", "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": "hIwCYAgApr", "reviewer": "Reviewer_s2Kd", "summary": "The paper proposes a MCMC method (called AutoStep MCMC) with locally adaptive step size selection. This method generalizes the previous involutive methods (e.g. RWMH, MALA, HMC etc) allowing adopting step size which is randomly drawn from some conditional distribution. The class of involutive MCMC methods is considered. \nTheoretical properties of MCMC kernel are studied (e.g. invariant distribution, aperiodicity etc). Robustness and scalability properties are also studied.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your thoughtful feedback. We are glad to address your questions one by one.\n\n> Is it possible to provide numerical experiments with mixtures of distributions?\n\nThank you for the suggestion. Please first note that AutoStep is designed to help handle multiscale behaviour in targets (e.g., funnel structure); our methods are not expected to perform substantially differently than a well-tuned fixed-step-size method on multimodal / mixture targets. To help address multimodality, one could instead incorporate AutoStep in a parallel tempering scheme. One potential advantage of AutoStep in that setting is that it will choose an appropriate step size for each chain in the ensemble (which will be different at each temperature), unlike fixed step size methods that each must be tuned individually.\n\nPlease also note that the orbital model (see Fig. 13) already has multiple modes/ridges/varying geometries/etc.\n\n> I would add comparison with modern methods using adaptive kernels (e.g. using normalizing flows, Local-Global MCMC, adaptive Monte Carlo augmented with normalizing flows, GFlowNets, etc.)\n\nWe appreciate the suggestion, though we note that many of the listed methods (e.g., normalizing flow-based MCMC, GFlowNets) typically require significant training time, and are not exact methods. An interesting recent result from He, Du et al (2022) shows almost all neural samplers require several orders of magnitude more target evaluations compared to parallel tempering, itself an expensive meta MCMC algorithm.\n \nBeyond this, neural methods and AutoStep use quite different approaches, and a direct comparison may therefore not be particularly meaningful. That being said, we agree that integrating AutoStep into such frameworks in future work could be an interesting extension.\n\nHe, J., Du, Y., Vargas, F., Zhang, D., Padhy, S., OuYang, R., ... & Hernández-Lobato, J. M. (2025). No Trick, No Treat: Pursuits and Challenges Towards Simulation-free Training of Neural Samplers. arXiv preprint arXiv:2502.06685.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I haven't checked the proves of main results", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "The paper contributes to the long list of locally adaptive MCMC methods", "essential_references_not_discussed": "I would add comparison with modern methods using adaptive kernels (e.g. using normalizing flows); See Local-Global MCMC kernels: the best of both worlds, NeurIPS 2022 or Adaptive Monte Carlo augmented with normalizing flows, PNAS 2022. Or modern sampling methods e.g. GFlowNets for continuous distributions or optimal control methods for sampling (Theoretical guarantees for sampling and inference in generative models with latent diffusions, COLT 2019)", "other_strengths_and_weaknesses": "Strengths\nNew locally adaptive MCMC method;\ne.g. invariant distribution, aperiodicity etc). Robustness and scalability properties are also studied. \n\nWeaknesses\nI would add more numerical experiments with mixtures of distributions (e.g. high dimensional gaussian mixtures) or latent distributions of generative models (e.g. GANs); see e.g. paper Your GAN is Secretly an Energy-based Model and You Should use Discriminator Driven Latent Sampling", "other_comments_or_suggestions": "I would add comparison with modern methods using adaptive kernels (e.g. using normalizing flows); See Local-Global MCMC kernels: the best of both worlds, NeurIPS 2022 or Adaptive Monte Carlo augmented with normalizing flows, PNAS 2022. Or modern sampling methods e.g. GFlowNets for continuous distributions or optimal control methods for sampling (Theoretical guarantees for sampling and inference in generative models with latent diffusions, COLT 2019)", "questions_for_authors": "Is it possible to provide numerical experiments with mixtures of distributions?", "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": "2MEDpGCh68", "reviewer": "Reviewer_GQHY", "summary": "The authors propose a method to tune the step size of MCMC algorithms so that, at each iteration, the acceptance rate is not too high (exploitation) or too low (exploration).\n\n## update after rebuttal\n\nI thank the authors for their clarification on a minor point that I raised. My overall assessment has not changed and I will maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and insightful questions. We hope that our answer has addressed all your concerns.\n\n> There is no visual evidence that tuning the step size helps the MCMC algorithm locate the target modes faster, and therefore converge faster.\n\nPlease note that locating modes is not a primary goal of MCMC algorithms; the goal is to take draws from a target distribution that yield accurate estimates of target expectations. In our work, the focus in particular is on ensuring efficient sampling from models with varying scale. The KSESS / sec metric results presented in our manuscript in Figure 5 captures both sampling correctness and computational efficiency, and is the standard method used in the field for comparing sampling algorithms.\n \n> Could the authors discuss the link between their paper and Cyclical MCMC, which varies the step size cyclically between bigger and smaller values to alternate between mode exploration and exploitation.\n\nCyclical MCMC (Zhang et al, 2020) and AutoStep both modulate the step size, but in fundamentally different ways. Cyclical MCMC follows a prescribed, periodic schedule and is not designed to tune the step size or adapt to the target distribution. Furthermore, Cyclical MCMC is not guaranteed to provide asymptotically correct estimates of expectations unless the number and spacing of temperatures in one cycle is controlled carefully to account for the mixing behaviour of the kernels.\n\nIn contrast, AutoStep adapts the step size based on the local geometry of the target and is always an exact method, i.e., it comes with a guarantee of $\\pi$-invariance.", "claims_and_evidence": "The authors claim a full theoretical analysis that does indeed seem quite complete.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Not in detail.", "experimental_designs_or_analyses": "The experiments mainly substantiate the claim that tuning the step size makes the sampling algorithm robust the initial step size, which should be the case by design.\n\nFigure 5 in particular shows that by a certain measure of efficiency (KSESS), the authors' method performs better. However, there is no visual evidence that tuning the step size helps the MCMC algorithm locate the target modes faster, and therefore converge faster.", "relation_to_broader_scientific_literature": "The authors clearly discuss a related paper by Bou Rabee et al.", "essential_references_not_discussed": "Related works are clearly discussed by the authors. Could the authors discuss the link between their paper and Cyclical MCMC, which varies the step size cyclically between bigger and smaller values to alternate between mode exploration and exploitation.", "other_strengths_and_weaknesses": "Strength: the paper is very clearly written.", "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": "rm701vn0ho", "reviewer": "Reviewer_Anr8", "summary": "This paper introduces AutoStep MCMC, a novel class of locally adaptive involutive MCMC methods that dynamically select the step size parameter at each iteration based on the local geometry of the target distribution.  The proposed method extends previous adaptive MCMC techniques by integrating step size adaptation within involutive MCMC frameworks, ensuring π-invariance, irreducibility, and aperiodicity. Theoretical results establish non-asymptotic guarantees on expected energy jump distance and computational cost per iteration. The experiments demonstrate the robustness and efficiency of their AutoStep method for RWMH and MALA using KSESS on various distributions. They compare with several baseline adaptive samplers, including NUTS, adaptive RWMH,  adaptive MALA, drHMC and slice sampling.\n\n\n### update after rebuttal\nThanks to the authors for the additional work and clarification. After reading the initial response to my questions, as well as the other reviews and replies in general, I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Can AutoStep MCMC be extended to stochastic gradient MCMC like SGLD and SGHMC while preserving its key advantages?\n\nThanks, that’s a great point! Our focus in this paper is on exact, invariant MCMC methods, but it is indeed possible to extend AutoStep to SG MCMC. One approach would be to resample a mini-batch at each iteration and feed it to Alg 2 to estimate a step size $\\theta_j$. \n\nHowever, as noted by Johndrow et al. (2020), subsampling offers little speedup or accuracy gain over exact methods. While approximate MCMC (without MH correction) can be useful during the burn-in for estimating a reasonable $\\theta_0$, in the stationary phase, the computational gains from subsampling may not outweigh the loss in robustness.\n\nJohndrow, J. E., Pillai, N. S., & Smith, A. (2020). No free lunch for approximate MCMC. arXiv preprint arXiv:2010.12514.\n\n> Can AutoStep MCMC scale to high-dimensional models?\n\nThank you for bringing that to our attention. We have run three additional high-dim models (each with 30 seeds) to address your concern: the 111d HMM example from posteriordb, a 133d stochastic volatility model (Kim el al, 1998), and a 312d IRT model (Curtis et al, 2010).\n\nThe table below presents the minESS/sec metrics, which generally shows good performance. The per second timing includes the full computational time (burn-in, $\\theta$ selection, all aspects of tuning, etc). We did not include KSESS results, as generating reliable reference distributions via PT requires days of computation, which was not feasible within the discussion period.\n\n| Sampler         | Model                  | q5       | Median   | q95      |\n|------------------|------------------------|----------|----------|----------|\n│ AutoStep RWMH  | hmm_example          | 19.3966    | 31.3897    | 360.596 |\n│ AutoStep RWMH  | stochastic_volatility   | 1.33824    | 2.04454    | 2.3855   |\n│ AutoStep RWMH  | irt                               | 4.63187    | 4.71388    | 4.7435   |\n│ AutoStep MALA    | hmm_example          | 10.4717    | 13.4765    | 33.5944 |\n│ AutoStep MALA    | stochastic_volatility   | 4.78546    | 5.9194      | 7.23065 |\n│ AutoStep MALA    | irt                               | 0.838859  | 0.959374  | 1.023     |\n\n> There are no detailed analyses and empirical results about the computational trade-offs (e.g., additional overhead of adaptive step size selection)...... Provide more discussion on the computational cost of AutoStep MCMC compared to non-adaptive methods.\n\nPlease note that we provide ESS/sec (Fig. 5) metrics in our experiments, which account for the full computational time (including burn-in, the step size selection, all aspects of tuning, etc). These metrics are intended to reflect the trade-off between statistical efficiency and computational cost. Beyond this, we also have theoretical results (Prop 4.9, Cor 4.10) that put bounds on the expected number of doubling/halving steps per iteration, which capture the dominant additional computational cost over fixed step size methods.\n\n> Some step size adaptation choices (e.g., choice of thresholds) could be further justified.\n\nThere is certainly room for further research on better choices of the distribution over $(a, b)$. The only strict requirement is that the support is on all of $\\Delta$ (i.e. $0<a<b<1$), to guarantee irreducibility. Intuitively, one must also ensure that $a, b$ are “typically” bounded away from 0 and 1 to avoid many overly aggressive or conservative steps. But aside from that, there is room for creativity: for example, one might consider potentially making the distribution favor known optimal acceptance rates of MCMC algorithms. That being said, in our experimentation we found that the uniform distribution on $\\Delta$ achieved the goal of maintaining a reasonable step size, and we believe other improvements (like different mass matrix adaptation) are unlikely to have a far larger influence on performance.\n\n> Discuss the applicability of AutoStep MCMC to more gradient-based samplers beyond MALA (e.g., HMC, NUTS).\n\nWe kindly refer you to our earlier response to Reviewer JzQk, where we discuss the applicability of AutoStep to HMC and NUTS.\n\n> Can you provide more computational complexity analyses of AutoStep MCMC?\n\nNote that the cost is dominated (in the long run asymptotically) by the average number of log-prob evaluations per iteration. The number of log-prob evaluations is in turn controlled by the number of doubling/halving steps in AutoStep. Prop 4.9 places an upper bound on this quantity, which provides the desired result. To apply this result, problem-specific analysis is generally required; however, in Cor 4.10, we are able to specialize the result for a representative class of target distributions in the large/small $\\theta_0$ regime (i.e., when the method is poorly tuned). This result shows that the extra cost incurred by AutoStep grows by a factor of $|\\log \\theta_0|$, indicating that the additional cost of AutoStep should generally be small.", "claims_and_evidence": "The paper makes the following key claims, which are generally well-supported:\n1. AutoStep MCMC is π-invariant, irreducible, and aperiodic under mild conditions. This is supported by rigorous proofs (Proposition 4.2, 4.5, and Corollary 4.6).\n2. AutoStep MCMC adaptively selects step sizes to balance exploration and acceptance rate, improving mixing efficiency. The claim is substantiated by theoretical bounds and empirical evaluations on benchmark distributions.", "methods_and_evaluation_criteria": "The methodology is well-structured and clearly builds on established MCMC principles. The key contribution is the introduction of a dynamically adaptive step size selection mechanism that does not rely on global tuning but instead adjusts step size based on local properties of the target distribution. The evaluation criteria include acceptance rates,  KSESS per unit cost and min KSESS per unit cost, which are appropriate for assessing MCMC performance.", "theoretical_claims": "The theoretical foundations of the paper are solid, with detailed proofs demonstrating the correctness of the proposed method. \n1. Proofs of π-invariance, irreducibility, and aperiodicity (Proposition 4.2, 4.5, and Corollary 4.6).\n2. Bounds on expected energy jump distance and computational cost per iteration (Proposition 4.11 and Corollary 4.10).", "experimental_designs_or_analyses": "The experimental setup is comprehensive, with evaluations on:\n\n1. Synthetic distributions (Gaussian, Laplace, and Cauchy) to assess the benefits of using the symmetric step size criterion, the efficiency of the round-based tuning procedure and the robustness of $\\theta_{0}$.\n2. Bayesian inference problems (linear regression, orbit fitting, mRNA transfection models).\n3. Comparisons with various adaptive MCMC baselines.", "relation_to_broader_scientific_literature": "The paper is well-situated within the existing MCMC literature, particularly within the adaptive MCMC and involutive MCMC frameworks. It builds upon:\n\n1. Adaptive MCMC methods by introducing a locally adaptive approach.\n\n2. Involutive MCMC methods by integrating adaptive step size selection.\n\n3. Recent work on adaptive step size selection in MALA, which the authors improve upon by ensuring irreducibility and aperiodicity.\n\nThe discussion could be further enriched by addressing connections to other step size tuning techniques, such as stochastic gradient-based methods in deep learning.", "essential_references_not_discussed": "The paper adequately cites prior work but could benefit from a broader discussion of step size adaptation in high-dimensional Bayesian inference.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Novel and well-motivated approach to adaptive step size selection.\n2. The paper is theoretical rigour, with solid proofs establishing key properties.\n3. The experimental results indicate the proposed method outperforms competing baselines.\n4. The method is robust to the step size initialization, enhancing its practical usability.\n\nWeaknesses:\n\n1. There are no detailed analyses and empirical results about the computational trade-offs (e.g., additional overhead of adaptive step size selection).\n2. The experiments are too toy. The scalability of the proposed method for high-dimensional problems is unclear.\n3. Some step size adaptation choices (e.g., choice of thresholds) could be further justified.", "other_comments_or_suggestions": "1. Provide more discussion on the computational cost of AutoStep MCMC compared to non-adaptive methods.\n2. Conduct a scalability study on high-dimensional problems (e.g., large Bayesian posterior models).\n3. Discuss the applicability of AutoStep MCMC to more gradient-based samplers beyond MALA (e.g., HMC, NUTS).", "questions_for_authors": "1. Can AutoStep MCMC scale to high-dimensional models? such as posterior sampling for large BNN.\n2. Can you provide more computational complexity analyses of AutoStep MCMC?\n3. Can AutoStep MCMC be extended to stochastic gradient MCMC like SGLD and SGHMC while preserving its key advantages?", "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:

Meta-review: All reviewers agreed that this is a nice paper which introduces a clear and sound methodology for incorporating adaptive step sizes into MCMC algorithms without requiring a fixed, finite adaptation period. While there were some concerns that the method might not be as performant, when applied to random walk MH (or MALA), as a well-tuned NUTS sampler (and thus the method as-presented likely would not be the state-of-the-art in many scenarios), I would agree that the reasons to accept this paper would clearly outweigh this concern. As this is a novel approach to a long-standing concern, it may well additionally inspire future follow-on work.
Decision: Accept (poster)