Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T02:49:19.116Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Construction of Interpolating Sets for High-Dimensional Integration

Part of: Probabilistic theory: distribution modulo $1$; metric theory of algorithms Numerical approximation and computational geometry Special processes

Published online by Cambridge University Press:  30 January 2018

Mark Huber  and
Sarah Schott
Mark Huber*
Affiliation:
Claremont McKenna College
Sarah Schott*
Affiliation:
Duke University
*
∗ Postal address: Department of Mathematical Sciences, Claremont McKenna College, 850 Columbia Avenue, Claremont, CA 91711, USA. Email address: [email protected]
∗∗ Postal address: Department of Mathematics, Duke University, 117 Physics Building, Science Drive, Durham, NC 27708, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Computing the value of a high-dimensional integral can often be reduced to the problem of finding the ratio between the measures of two sets. Monte Carlo methods are often used to approximate this ratio, but often one set will be exponentially larger than the other, which leads to an exponentially large variance. A standard method of dealing with this problem is to interpolate between the sets with a sequence of nested sets where neighboring sets have relative measures bounded above by a constant. Choosing such a well-balanced sequence can rarely be done without extensive study of a problem. Here a new approach that automatically obtains such sets is presented. These well-balanced sets allow for faster approximation algorithms for integrals and sums using fewer samples, and better tempering and annealing Markov chains for generating random samples. Applications, such as finding the partition function of the Ising model and normalizing constants for posterior distributions in Bayesian methods, are discussed.

Keywords

IntegrationMonte Carlo methodcooling scheduleself-reducible

MSC classification

Primary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 11K45: Pseudo-random numbers; Monte Carlo methods 65D30: Numerical integration
Type
Research Article
Information
Journal of Applied Probability , Volume 51 , Issue 1 , March 2014 , pp. 92 - 105
Copyright
© Applied Probability Trust 

References

Besag, J. (1974). Spatial interaction and the statistical analysis of lattice systems. J. R. Statist. Soc. B 36, 192–236.Google Scholar
Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493–507.Google Scholar
Dyer, M. and Frieze, A. (1991). Computing the volume of convex bodies: a case where randomness provably helps. In Probabilistic Combinatorics and Its Applications (Proc. Symp. Appl. Math. 44), American Mathematical Society, Providence, RI, pp. 123–169.Google Scholar
Fishman, G. S. (1994). Choosing sample path length and number of sample paths when starting in steady state. Operat. Res. Lett. 16, 209–219.Google Scholar
Geyer, C. J. (1991). Markov chain Monte Carlo maximum likelihood. In Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, pp. 156–163.Google Scholar
Huber, M. L. (2012). Approximating algorithms for the normalizing constant of Gibbs distributions. Preprint. Available at http:/uk.arxiv.org/abs/1206.2689.Google Scholar
Huber, M. and Schott, S. (2011). Using T{P}{A} for Bayesian inference. In Bayesian Statistics 9 (Proc. 9th Valencia Internat. Meeting), Oxford University Press, pp. 257–282.Google Scholar
Huber, M. L. and Wolpert, R. L. (2009). Likelihood-based inference for Matérn type-{III} repulsive point processes. Adv. Appl. Prob. 41, 958–977.Google Scholar
Jerrum, M. R., Valiant, L. G. and Vazirani, V. V. (1986). Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188.Google Scholar
Karatzas, I. and Shreve, S. E. (1991). Brownian Motion and Stochastic Calculus, 2nd edn. Springer, New York.Google Scholar
Kirkpatrick, S., Gelatt, C. D. Jr. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220, 671–680.Google Scholar
Marinari, E. and Parisi, G. (1992). Simulated tempering: a new Monte Carlo scheme. Europhys. Lett. 19, 451–458.CrossRefGoogle Scholar
Motwani, R. and Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.Google Scholar
Murray, I., Ghahramani, Z. and MacKay, D. J. C. (2006). MCMC for doubly-intractable distributions. In Proc. 22nd Annual Conf. Uncertainty Artificial Intelligence, AUAI Press, pp. 359–366.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.Google Scholar
Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods, 2nd edn. Springer, New York.CrossRefGoogle Scholar
Shonkwiler, R. W. and Mendivil, F. (2009). Expolorations in Monte Carlo Methods. Springer, New York.Google Scholar
Skilling, J. (2006). Nested sampling for general Bayesian computation. Bayesian Analysis 1, 833–859.Google Scholar
ŠtefankoviČ, D., Vempala, S. and Vigoda, E. (2009). Adaptive simulated annealing: a near-optimal connection between sampling and counting. J. ACM 56, 36pp.Google Scholar
Swendsen, R. H. and Wang, J.-S. (1986). Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett. 57, 2607–2609.Google Scholar
Valleau, J. P. and Card, D. N. (1972). Monte Carlo estimation of the free energy by multistage sampling. J. Chem. Phys. 57, 5457–5462.Google Scholar
Woodward, D. B., Schmidler, S. C. and Huber, M. (2009). Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions. Ann. Appl. Prob. 19, 617–640.Google Scholar
Woodward, 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.Google Scholar