The Metropolis-adjusted Langevin algorithm (MALA) is an informed MCMC method that is used to sample from a target distribution of interest. Its proposal distribution makes use of the gradient of the target’s log-density in order to generate suitable candidates for the chain. This sampler is quite efficient in the stationary phase, but displays a notoriously erratic behaviour out of stationarity. The Metropolis-adjusted Langevin algorithm with annealed proposals (aMALA) is a generalization of the usual MALA that features two tuning parameters: the usual step size \(\delta\) and a parameter \(\gamma\) that may be adjusted to accommodate N, the dimension of the target distribution (with \(\gamma =1\) corresponding to MALA). It has been established in Boisvert-Beaudry and Bédard (Stat Comput 32(1):5, 2022) that aMALA with \(1<\gamma \le 2\) usually outperforms MALA, even in high-dimensional contexts where the latter should become optimal. The results of this paper demonstrate that the computational cost of aMALA is \(\mathcal {O}(N^{1/3})\) in its non-stationary regime and that it may be as small as \(\mathcal {O}(N^{1/5})\) in stationarity. This is in contrast to MALA, whose cost is \(\mathcal {O}(N^{1/2})\) out of stationarity and \(\mathcal {O}(N^{1/3})\) in its stationary regime. Hence, in virtually any situation of practical relevance where we study an N-dimensional target distribution (with \(N<\infty\) ) and/or the algorithm is started out of stationarity, the MALA with annealed proposals turns out to be superior to MALA, and as easily implemented/tuned as the latter.
