Linear-Cost Vecchia Approximation of Multivariate Normal Probabilities

TL;DR

The paper develops Vecchia MET (VMET), a linear-time method for estimating multivariate normal probabilities and sampling truncated MVN distributions by combining the Vecchia approximation with minimax exponential tilting. It shows VMET matches MET’s convergence or acceptance rate while reducing per-sample and proposal-optimization complexity from cubic/quadratic to linear.

Key findings

• VMET reduces the per-MC-sample complexity from O(n²) to O(n) and the cost of solving for the exponential tilting parameter from O(n³) to O(n), giving overall complexity O(Tnm + Nnm); it preserves MET’s convergence/acceptance rate.
• In n = 900 simulations, VMET achieved the same level of error as MET while reducing computation times by 90%; for TMVN sampling, MET took 494.4 seconds versus 19.9 seconds for VMET.
• For n = 6,400, VMET had a better accuracy–cost trade-off than SOV and TLR; in a censored GP example, VMET regional sampling gave prediction RMSE 0.19 versus 0.45 for the LOD-augmented GP, with a minimum possible RMSE of 0.17 due to nugget variance 0.03.
• On a groundwater tetrachloroethylene dataset with n = 24,701 responses and 20,730 censored responses, the partially censored MVN model had a Brier score/RMSE of 0.36 versus 0.74 for the LOD-augmented GP at 179 Texas test points.

Methods

• The authors re-parameterize the SOV and MET integrands using the sparse inverse Cholesky factor from the Vecchia approximation, truncating conditioning sets to size m and computing conditional means and variances in O(m) per dimension.
• They derive sparse gradient and Hessian expressions for the log density ratio and use L-BFGS to optimize the exponential tilting parameter in O(n); optional techniques include Vecchia-based variable reordering and multi-level Monte Carlo.
• Numerical studies use Matérn-1.5 kernels in n = 900 and n = 6,400 scenarios, plus a USGS groundwater contamination dataset modeled with a partially censored MVN and Matérn-1.5 kernel, split 80% training and 20% testing.

Limitations

• The paper states that VMET is an approximation to the original covariance, so estimation bias is unavoidable; however, Vecchia bias is typically negligible relative to Monte Carlo error for m around 30 to 50.
• The paper notes that multi-level Monte Carlo may be less effective when VMET bias does not decrease monotonically with m, and that regional TMVN sampling ignores censored locations outside the selected region, with boundary extension reducing bias but lowering acceptance rate.
• The paper states that variable reordering is not used for parameter estimation to avoid discontinuity in the log-likelihood surface, and that only positive-definite covariance matrices are considered; linear constraints and rank-deficient covariance matrices are left for future research.
• Evident from the text: MET is treated as a gold standard but is not computationally scalable to large n, and acceptance rates can be very low for large TMVN dimensions, making global sampling infeasible in some examples.