When are Unbiased Monte Carlo Estimators More Preferable than Biased Ones?

Due to the potential benefits of parallelization, designing unbiased Monte Carlo estimators, primarily in the setting of randomized multilevel Monte Carlo, has recently become very popular in operations research and computational statistics. However, existing work primarily substantiates the benefits of unbiased estimators at an intuitive level or using empirical evaluations. The intuition being that unbiased estimators can be replicated in parallel enabling fast estimation in terms of wall-clock time. This intuition ignores that, typically, bias will be introduced due to impatience because most unbiased estimators necesitate random completion times. This paper provides a mathematical framework for comparing these methods under various metrics, such as completion time and overall computational cost. Under practical assumptions, our findings reveal that unbiased methods typically have superior completion times - the degree of superiority being quantifiable through the tail behavior of their running time distribution - but they may not automatically provide substantial savings in overall computational costs. We apply our findings to Markov Chain Monte Carlo and Multilevel Monte Carlo methods to identify the conditions and scenarios where unbiased methods have an advantage, thus assisting practitioners in making informed choices between unbiased and biased methods.

由于并行化的潜在优势，设计无偏蒙特卡罗估计量，主要是在随机多层蒙特卡罗的设定下，最近在运筹学和计算统计学中变得非常流行。然而，现有的工作主要是在直观层面或通过实证评估来证实无偏估计量的优势。其直觉是无偏估计量可以并行复制，从而在挂钟时间方面实现快速估计。这种直觉忽略了一个事实，即通常由于缺乏耐心会引入偏差，因为大多数无偏估计量需要随机的完成时间。本文提供了一个数学框架，用于在各种指标下比较这些方法，例如完成时间和总体计算成本。在实际假设下，我们的研究结果表明，无偏方法通常具有更优的完成时间——其优势程度可通过其运行时间分布的尾部行为来量化——但它们可能不会自动在总体计算成本上提供大量节省。我们将我们的研究结果应用于马尔可夫链蒙特卡罗和多层蒙特卡罗方法，以确定无偏方法具有优势的条件和情形，从而帮助从业者在无偏和有偏方法之间做出明智的选择。