Improved Monte Carlo methods for high dimensional sums and integrals

“蒙特卡罗”算法是一种在运行时做出随机决策的计算方法。蒙特卡罗算法(可以追溯到曼哈顿计划)已经成为物理学、计算机科学、统计学和许多其他领域的宝贵工具，并已成为现代计算工具包中不可或缺的一部分。蒙特卡罗方法使积分的近似成为可能，否则这些积分将是遥不可及的。这个项目将开发和分析新类型的蒙特卡罗算法，最终目标是更好地逼近高维积分和和。这些方法将有助于找到统计对象，如最大似然估计器和精确的p值，使用贝叶斯统计进行模型分段，以及为计算机科学中出现的可证明困难的问题建立近似算法。许多现有的蒙特卡罗算法提供了点估计，但无法给出这些估计的可证明的良好误差界。首席研究员最近的工作表明，在某些情况下，有可能建立算法，其中误差只取决于算法，而不是所考虑的特定问题。例如，一种称为配对乘积估计的新方法给出了一种快速估计高维积分的方法，其中估计的误差精确有界。这些界限与被采样的分布无关。本项目的目的是进一步开发和分析这些算法，以提高它们的理论和实践效率。这些将是基本的方法，并应被用作许多不同领域的研究人员的通用工具。该项目将在蒙特卡洛模拟中开发几种新的方法。第一种算法用于估计伯努利随机变量的平均值。这是蒙特卡罗算法中用于估计统计学中准确的p值和用于使用接受拒绝估计积分的基本步骤。通过使用Huber的方法，可以创建估计，使得估计中的相对误差与平均值无关。计算机实验表明，该方法是快速的；在项目的这一部分，胡贝尔将试图证明，在获得这样一个估计所需的样本数量方面，该方法是被证明接近最优的。还将开发一种从马尔可夫随机场采样的新协议，如伊辛模型，部分递归接受拒绝。通过为图形创建一棵可能的标签树，然后仔细修剪这棵(指数级大的)树，可以只使用多项式(偶数线性)步骤数来从伊辛模型(在临界温度以上的温度下)进行采样。这样的模型通常可以写成吉布斯分布，而且通常很难找到这些分布的归一化常数(称为配分函数)。该项目的一部分将提炼一个名为配对乘积估计器的想法，它以一种可以证明是快速的方式近似配分函数：现在的目标是使该方法实际上也是有效的。

A "Monte Carlo" algorithm is a computational method that makes random decisions as it runs. Monte Carlo algorithms (dating back to the Manhattan Project) have been an invaluable tool in physics, computer science, statistics, and many other fields, and have become an indispensable part of the modern computing toolkit. Monte Carlo methods enable approximations of integrals that would otherwise remain out of reach. This project will develop and analyze new types of Monte Carlo algorithms, with the ultimate goal of better approximation for high-dimensional integrals and sums. These methods will assist in finding statistical objects such as the maximum likelihood estimator and exact p values, in performing model section using Bayesian statistics, and in building approximation algorithms for provably hard problems that arise in computer science. Many existing Monte Carlo algorithms deliver point estimates, but fail to give provably good error bounds on these estimates. Recent work of the principal investigator shows that in some instances, it is possible to build algorithms where the error only depends on the algorithm, and not on the particular problem under consideration. For example, a new method called the Paired Product Estimator gives a fast method for estimating integrals in high dimension where the error of the estimate is precisely bounded. These bounds are independent of the distribution being sampled from. The project purpose is to further develop and analyze these algorithms to improve both their theoretical and practical efficiency. These will be foundational methods, and should find use as a general tool for researchers in many different fields. This project will develop several new methodologies in Monte Carlo simulation. The first algorithm is for estimating the mean of a Bernoulli random variable. This is an essential step in Monte Carlo algorithms for estimating exact p values in statistics and for estimating integrals using acceptance rejection. By employing a method of Huber, it is possible to create an estimate such that the relative error in the estimate is independent of the value of the mean. Computer experiments indicate the method is fast; in this part of the project, Huber will try to show that this method is provably close to the optimal in the number of samples needed to obtain such an estimate. A new protocol for sampling from Markov random fields such as the Ising model will also be developed, partially recursive acceptance rejection. By creating a tree of possible labels for a graph and then carefully pruning this (exponentially large) tree, it is possible to sample from the Ising model (at temperatures above the critical temperature) using only a polynomial (even linear) number of steps. Such models can usually be written as Gibbs distributions, and often finding the normalizing constant (called the partition function) for these distributions is computationally very difficult. One part of the project will be refining an idea called the Paired Product Estimator, that approximates the partition function in a provably fast way: now the goal is to make the method practically efficient as well.