Skew Brownian motion and complexity of the ALPS algorithm. (English) Zbl 1497.60101
Summary: Simulated tempering is a popular method of allowing Markov chain Monte Carlo algorithms to move between modes of a multimodal target density \(\pi\). N. G. Tawn et al. [“Annealed leap-point sampler for multimodal target distributions, Preprint, arXiv:2112.12908] introduced the Annealed Leap-Point Sampler (ALPS) to allow for rapid movement between modes. In this paper we prove that, under appropriate assumptions, a suitably scaled version of the ALPS algorithm converges weakly to skew Brownian motion. Our results show that, under appropriate assumptions, the ALPS algorithm mixes in time \(O(d [\log d]^2)\) or \(O(d)\), depending on which version is used.
MSC:
| 60J25 | Continuous-time Markov processes on general state spaces |
| 60J05 | Discrete-time Markov processes on general state spaces |
| 60J22 | Computational methods in Markov chains |
| 60J65 | Brownian motion |
References:
| [1] | Aarts, E. and Korst, J. (1988). Simulated Annealing and Boltzmann Machines. John Wiley, New York. · Zbl 0674.90059 |
| [2] | Atchadé, Y. F., Roberts, G. O. and Rosenthal, J. S. (2011). Towards optimal scaling of Metropolis-coupled Markov chain Monte Carlo. Statist. Comput.21, 555-568. · Zbl 1223.65001 |
| [3] | Barlow, M. T., Pitman, J. and Yor, M. (1989). On Walsh’s Brownian motions. In Séminaire de Probabilités XXIII, eds J. Azéma, M. Yor and P. A. Meyer. Springer, New York, pp. 275-293. · Zbl 0747.60072 |
| [4] | Bédard, M. and Rosenthal, J. S. (2008). Optimal scaling of Metropolis algorithms: Heading toward general target distributions. Canad. J. Statist.36, 483-503. · Zbl 1167.60344 |
| [5] | Beskos, A., Pillai, N., Roberts, G., Sanz-Serna, J.-M. and Stuart, A. (2013). Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli, 19, 1501-1534. · Zbl 1287.60090 |
| [6] | Brooks, S., Gelman, A., Jones, G. L. and Meng, X.-L. (eds) (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall, London. · Zbl 1218.65001 |
| [7] | Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, New York. · Zbl 0592.60049 |
| [8] | Freidlin, M. and Weber, M. (2001). On random perturbations of Hamiltonian systems with many degrees of freedom. Stoch. Proc. Appl.94, 199-239. · Zbl 1053.60058 |
| [9] | Geyer, C. J. (1991). Markov chain Monte Carlo maximum likelihood. Comput. Sci. Statist.23, 156-163. |
| [10] | Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika57, 97-109. · Zbl 0219.65008 |
| [11] | Jacka, S. and Hernández-Hernández, Ma. E. (2019). Minimising the expected commute time. Stoch. Proc. Appl., DOI doi:10.1016/j.spa.2019.04.010. · Zbl 1489.60127 |
| [12] | Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680. · Zbl 1225.90162 |
| [13] | Kone, A. and Kofke, D. A. (2005). Selection of temperature intervals for parallel-tempering simulations. J. Chem. Phys.122, 206101. |
| [14] | Lejay, A. (2006). On the constructions of the skew Brownian motion. Prob. Surv.3, 413-466. · Zbl 1189.60145 |
| [15] | Liggett, T. M. (2010). Continuous Time Markov Processes: An Introduction. American Mathematical Society, Providence, RI. · Zbl 1205.60002 |
| [16] | Marinari, E. and Parisi, G. (1992). Simulated tempering: A new Monte Carlo scheme. Europhys. Lett.19, 451. |
| [17] | Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys.21, 1087-1092. · Zbl 1431.65006 |
| [18] | Pincus, M. (1970). A Monte Carlo method for the approximate solution of certain types of constrained optimization problems. J. Operat. Res. Soc. Amer.18, 967-1235. · Zbl 0232.90063 |
| [19] | Predescu, C., Predescu, M. and Ciobanu, C. V. (2004). The incomplete beta function law for parallel tempering sampling of classical canonical systems. J. Chem. Phys.120, 4119-4128. |
| [20] | Revuz, D. and Yor, M. (2004). Continuous Martingales and Brownian Motion, 3rd edn. Springer, New York. · Zbl 0731.60002 |
| [21] | Roberts, G. O., Gelman, A. and Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Prob.7, 110-120. · Zbl 0876.60015 |
| [22] | Roberts, G. O. and Rosenthal, J. S. (1998). Optimal scaling of discrete approximations to Langevin diffusions. J. R. Statist. Soc. B 60, 255-268. · Zbl 0913.60060 |
| [23] | Roberts, G. O. and Rosenthal, J. S. (2001). Optimal scaling for various Metropolis-Hastings algorithms. Statist. Sci.16, 351-367. · Zbl 1127.65305 |
| [24] | Roberts, G. O. and Rosenthal, J. S. (2014). Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits. J. Appl. Prob.24, 1-11. |
| [25] | Roberts, G. O. and Rosenthal, J. S. (2014). Minimising MCMC variance via diffusion limits, with an application to simulated tempering. Ann. Appl. Prob.24, 131-149. · Zbl 1298.60078 |
| [26] | Rosenthal, J. S. (2002). Quantitative convergence rates of Markov chains: A simple account. Electron. Commun. Prob.7, 123-128. · Zbl 1013.60053 |
| [27] | Rosenthal, J. S. (2020). Maximum binomial probabilities and game theory voter models. Adv. Appl. Statist., 64, 75-85. |
| [28] | Syed, S., Bouchard-Côté, A., Deligiannidis, G. and Doucet, A. (2020). Non-reversible parallel tempering: A scalable highly parallel MCMC scheme. Preprint, arXiv:1905.02939. |
| [29] | Tawn, N. G., Moores, M. T. and Roberts, G. O. (2021). Annealed Leap-Point Sampler for multimodal target distributions. Preprint, arXiv:2112.12908. |
| [30] | Tawn, N. G. and Roberts, G. O. (2018). Accelerating parallel tempering: Quantile Tempering Algorithm (QuanTA). Adv. Appl. Prob.51, 802-834. · Zbl 1429.65012 |
| [31] | Tawn, N. G., Roberts, G. O. and Rosenthal, J. S. (2020). Weight-preserving simulated tempering. Statist. Comput.30, 27-41. · Zbl 1431.60082 |
| [32] | Woodard, D. B., Schmidler, S. C. and Huber, M. (2009). Sufficient conditions for torpid mixing of parallel and simulated tempering. Electron. J. Prob.14, 780-804. · Zbl 1189.65021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
