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.
- The Core ($p_q$): This term is estimated using fast and accurate randomized quasi-Monte Carlo (QRSVN) methods.
- 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).
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