AutoStep: Locally adaptive involutive MCMC

Can AutoStep MCMC be extended to stochastic gradient MCMC like SGLD and SGHMC while preserving its key advantages?

Thanks, 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$.

However, 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.

Johndrow, J. E., Pillai, N. S., & Smith, A. (2020). No free lunch for approximate MCMC. arXiv preprint arXiv:2010.12514.

Can AutoStep MCMC scale to high-dimensional models?

Thank 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).

The 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.

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.

Please 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.

Some step size adaptation choices (e.g., choice of thresholds) could be further justified.

There 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.

Discuss the applicability of AutoStep MCMC to more gradient-based samplers beyond MALA (e.g., HMC, NUTS).

We kindly refer you to our earlier response to Reviewer JzQk, where we discuss the applicability of AutoStep to HMC and NUTS.

Can you provide more computational complexity analyses of AutoStep MCMC?

Note 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.

Thank you for your time and insightful questions. We hope that our answer has addressed all your concerns.

There is no visual evidence that tuning the step size helps the MCMC algorithm locate the target modes faster, and therefore converge faster.

Please 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.

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.

Cyclical 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.

In 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.

We are grateful for your thoughtful feedback. We are glad to address your questions one by one.

Is it possible to provide numerical experiments with mixtures of distributions?

Thank 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.

Please also note that the orbital model (see Fig. 13) already has multiple modes/ridges/varying geometries/etc.

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.)

We 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.

Beyond 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.

He, 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.

Thank you for your insightful questions. We hope that our answer will address all your concerns.

The proposed method does not achieve top performance on any specific scenario.

While 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).

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.

Thank 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.

Note 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.

Elvira, Víctor, Luca Martino, and Christian P. Robert. "Rethinking the effective sample size." International Statistical Review 90.3 (2022): 525-550.

It must also be shown that the proposed sampler is not null recurrent to establish ergodicity. Can this be shown?

Thanks 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.

Given the strong performance of NUTS in Figure 5, is it possible to combine the proposed method with NUTS to further improve performance?

This 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.

However, 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.