Efficient Monte Carlo for high excursions of Gaussian random fields

Robert J. Adler, José Blanchet, Jingchen LiuThe Annals of Applied Probability 2012 · DOI

Abstract

Our focus is on the design and analysis of efficient Monte Carlo methods for computing tail probabilities for the suprema of Gaussian random fields, along with conditional expectations of functionals of the fields given the existence of excursions above high levels, $b$. Naïve Monte Carlo takes an exponential, in $b$, computational cost to estimate these probabilities and conditional expectations for a prescribed relative accuracy. In contrast, our Monte Carlo procedures achieve, at worst, polynomial complexity in $b$, assuming only that the mean and covariance functions are Hölder continuous. We also explain how to fine tune the construction of our procedures in the presence of additional regularity, such as homogeneity and smoothness, in order to further improve the efficiency.

Introduction

Gaussian random fields (GRFs) serve as a fundamental mathematical framework for modeling spatial data across diverse scientific disciplines, including cosmology, brain imaging, and environmental science. A critical task in these fields is the analysis of "high excursions"—rare events where the field's maximum value exceeds a high threshold $b$. These events often represent significant physical phenomena, such as identifying a neural signal in a noisy fMRI scan or detecting density peaks in the early universe. However, calculating the probability of these excursions and understanding the field's behavior during such events presents a formidable computational challenge.

The Challenge of Rare Events

The difficulty in estimating high excursion probabilities is two-fold. First, there is the Rare Event Problem: as the threshold $b$ increases, the probability of an excursion decreases at an exponential rate, roughly proportional to $e^{-cb^2}$. For a threshold that is even moderately high, naïve Monte Carlo simulation becomes computationally infeasible, as it would require an astronomical number of samples to observe even a single excursion.

Second, there is the Continuity Problem. While GRFs are continuous objects, computational simulations must operate on discrete grids. Balancing the density of this discretization with the accuracy of the estimated maximum is mathematically complex. If the grid is too sparse, the true maximum is underestimated; if it is too dense, the computational cost of simulating the field points becomes prohibitive.

A Polynomial Complexity Framework

This research introduces a novel Monte Carlo framework that transforms the computational cost of estimating these probabilities from exponential to polynomial time relative to the threshold $b$. The core of this approach is a Fully Polynomial Randomized Approximation Scheme (FPRAS) based on adaptive importance sampling.

Instead of sampling the field from its natural distribution and waiting for a rare peak, the algorithm samples from a "biased" distribution where high peaks are guaranteed to occur. The results are then mathematically "un-biased" to provide an accurate estimate. To ensure the variance of this estimator remains stable, the authors introduce an "undershoot" relaxation: rather than sampling the field given it exceeds $b$ at a specific point, they sample given it exceeds a slightly lower threshold $b - a/b$. This small buffer prevents the estimator's variance from exploding as $b$ grows.

Technical Innovations and Generality

A key insight of this work is treating discretization not as a nuisance, but as a controlled parameter. For fields that are only Hölder continuous (not necessarily smooth), the authors developed a strategy where the number of grid points $M$ grows polynomially with $b$.

For smoother, twice-differentiable fields, the framework incorporates the Slepian model, which describes the local shape of a field near a peak. By fine-tuning the importance sampling using this model, the researchers achieve "strong efficiency," a state where the relative error of the estimate remains constant regardless of how high the threshold $b$ is set. Unlike previous heuristics (such as the Euler Characteristic Heuristic), which often require specific smoothness and constant variance, this general algorithm is applicable to any Hölder continuous field.

Empirical Performance

The effectiveness of the algorithm was validated using several synthetic benchmarks, including 1D cosine processes and various 2D fields (both smooth and non-differentiable).

In a 1D cosine process test, the algorithm estimated a probability of $3.81 \times 10^{-23}$ with high precision using only 1,000 simulations. To achieve the same result, a naïve Monte Carlo approach would have required approximately $10^{25}$ simulations. Furthermore, numerical experiments confirmed that as the threshold $b$ increases, the relative error remains stable, confirming the theoretical claims of polynomial complexity. Complex 2D excursion probabilities that were previously considered intractable can now be computed in seconds or minutes on standard hardware.

Limitations and Future Directions

While the framework significantly reduces the number of required simulations, it introduces a new bottleneck: the Cholesky decomposition of the covariance matrix. As the discretization grid becomes finer for very high thresholds, the $O(M^3)$ cost of this decomposition becomes the primary computational burden. Additionally, while the theory holds for $d$-dimensional space, the "curse of dimensionality" still impacts the size of the discretization grid in very high-dimensional settings.

Future research may explore hybrid approaches combining this importance sampling framework with Quasi-Monte Carlo methods or more efficient linear algebra techniques to mitigate the Cholesky bottleneck, further extending the reach of these high-precision rare event simulations.

Summary updated

Abstract

Our focus is on the design and analysis of efficient Monte Carlo methods for computing tail probabilities for the suprema of Gaussian random fields, along with conditional expectations of functionals of the fields given the existence of excursions above high levels, b. Naïve Monte Carlo takes an exponential, in b, computational cost to estimate these probabilities and conditional expectations for a prescribed relative accuracy. In contrast, our Monte Carlo procedures achieve, at worst, polynomial complexity in b, assuming only that the mean and covariance functions are Hölder continuous. We also explain how to fine tune the construction of our procedures in the presence of additional regularity, such as homogeneity and smoothness, in order to further improve the efficiency.
BibTeX
@article{adler2012efficient,
  author = {Robert J. Adler and José Blanchet and Jingchen Liu},
  title = {{Efficient Monte Carlo for high excursions of Gaussian random fields}},
  journal = {The Annals of Applied Probability},
  year = {2012},
  doi = {10.1214/11-aap792},
}
Figure