Estimating Orthant Probabilities of High-Dimensional Gaussian Vectors with An Application to Set Estimation

Dario Azzimonti, David GinsbourgerJournal of Computational and Graphical Statistics 2017 · DOI · arXiv

Abstract

The computation of Gaussian orthant probabilities has been extensively studied for low-dimensional vectors. Here, we focus on the high-dimensional case and we present a two-step procedure relying on both deterministic and stochastic techniques. The proposed estimator relies indeed on splitting the probability into a low-dimensional term and a remainder. While the low-dimensional probability can be estimated by fast and accurate quadrature, the remainder requires Monte Carlo sampling. We further refine the estimation by using a novel asymmetric nested Monte Carlo (anMC) algorithm for the remainder and we highlight cases where this approximation brings substantial efficiency gains. The proposed methods are compared against state-of-the-art techniques in a numerical study, which also calls attention to the advantages and drawbacks of the procedure. Finally, the proposed method is applied to derive conservative estimates of excursion sets of expensive to evaluate deterministic functions under a Gaussian random field prior, without requiring a Markov assumption.

Introduction

Calculating the probability that a high-dimensional Gaussian vector falls within a specific orthant is a foundational problem in statistics. However, as the dimensionality ($d$) increases, computational complexity grows exponentially. While existing tools like the Genz algorithm (QRSVN) perform excellently for $d < 1000$, modern applications in spatial modeling and Gaussian Process (GP) regression often involve thousands of dimensions, necessitating more scalable solutions.

This paper introduces a hybrid approach that combines deterministic quadrature with a novel "asymmetric" Monte Carlo technique to effectively estimate these probabilities for $d > 1000$.

Methodology

The Two-Step Hybrid Approach

The core innovation is a "divide and conquer" strategy. The total probability $p$ is decomposed into a low-dimensional "core" and a stochastic "remainder" using the identity: $$p = P(\max X > t) = p_q + (1 - p_q)R_q$$ where $p_q$ represents the probability associated with a small subset of $q$ "active dimensions" ($q \ll d$), and $R_q$ is the remainder probability.

  1. The Core ($p_q$): This term is estimated using fast and accurate randomized quasi-Monte Carlo (QRSVN) methods.
  2. The Remainder ($R_q$): This term represents the probability that the remaining dimensions exceed the threshold given the core dimensions did not. This is estimated via simulation.

Active Dimension Selection

The efficiency of this decomposition depends heavily on selecting the most informative dimensions for the core. The authors propose two heuristics, Method A and Method B, which prioritize dimensions with high marginal excursion probabilities (those closest to the threshold).

Comparison of active dimension selection methods. Methods A and B significantly outperform random selection in capturing the probability mass as $q$ increases.

As shown in Figure 1, these strategic selection methods are significantly more effective than random choice at capturing the probability mass with a small number of dimensions.

Asymmetric Nested Monte Carlo (anMC)

To estimate the remainder $R_q$, the authors developed the asymmetric nested Monte Carlo (anMC) algorithm. Simulating the remainder involves two distinct steps:

  • Generating samples from a truncated Gaussian distribution (computationally expensive).
  • Generating conditional samples for the remaining dimensions (computationally cheap).

The anMC algorithm mathematically optimizes the computational budget by determining the ideal ratio of "cheap" to "expensive" samples, thereby minimizing total variance for a fixed time budget.

Results and Benchmarking

The proposed methods were evaluated against state-of-the-art algorithms, including QRSVN, GHK (Geweke-Hajivassiliou-Keane), and MET (Minimax Exponential Tilting), using discretized Gaussian Random Fields (GRF) with dimensions up to $d=7000$.

  • Efficiency Gains: In a benchmark with $d=5000$, the anMC algorithm demonstrated a 45-fold efficiency increase over GHK and was 3.8 times more efficient than MET.
  • Scalability: While standard QRSVN fails to scale beyond $d=1000$ due to memory constraints, the hybrid approach handled $d=7000$ effectively.
  • Application to Set Estimation: The method was applied to a 2D test case on a $100 \times 100$ grid ($d=10,000$). It successfully computed conservative 95% confidence regions for excursion sets, a task previously considered computationally prohibitive.

Conclusion

By splitting high-dimensional orthant probabilities into a deterministic core and a stochastic remainder, and optimizing the simulation budget via anMC, the authors provide a scalable framework for high-dimensional Gaussian inference. While challenges remain for extremely rare events, the hybrid approach offers a significant leap in efficiency for practical spatial statistics and reliability engineering applications.

Summary updated

Abstract

The computation of Gaussian orthant probabilities has been extensively studied for low-dimensional vectors. Here, we focus on the high-dimensional case and we present a two-step procedure relying on both deterministic and stochastic techniques. The proposed estimator relies indeed on splitting the probability into a low-dimensional term and a remainder. While the low-dimensional probability can be estimated by fast and accurate quadrature, the remainder requires Monte Carlo sampling. We further refine the estimation by using a novel asymmetric nested Monte Carlo (anMC) algorithm for the remainder and we highlight cases where this approximation brings substantial efficiency gains. The proposed methods are compared against state-of-the-art techniques in a numerical study, which also calls attention to the advantages and drawbacks of the procedure. Finally, the proposed method is applied to derive conservative estimates of excursion sets of expensive to evaluate deterministic functions under a Gaussian random field prior, without requiring a Markov assumption. Supplementary material for this article is available online.
BibTeX
@article{azzimonti2017estimating,
  author = {Dario Azzimonti and David Ginsbourger},
  title = {{Estimating Orthant Probabilities of High-Dimensional Gaussian Vectors with An Application to Set Estimation}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2017},
  doi = {10.1080/10618600.2017.1360781},
}
Figure