Linear-Cost Vecchia Approximation of Multivariate Normal Probabilities
提出一种基于Vecchia近似的算法，将多元正态概率估计和截断抽样复杂度从立方降为线性，在蒙特卡洛误差可忽略的前提下保持相同收敛率，并用两万多个删失数据验证了可扩展性。
Multivariate normal (MVN) probabilities arise in myriad applications, but they are analytically intractable and need to be evaluated via Monte Carlo-based numerical integration. For the state-of-the-art minimax exponential tilting (MET) method, we show that the complexity of each of its components can be greatly reduced through an integrand parameterization that uses the sparse inverse Cholesky factor produced by the Vecchia approximation, whose approximation error is often negligible relative to the Monte Carlo error. Based on this idea, we derive algorithms that can estimate MVN probabilities and sample from truncated MVN distributions in linear time (and that are easily parallelizable) at the same convergence or acceptance rate as MET, whose complexity is cubic in the dimension of the MVN probability. We showcase the advantages of our methods relative to existing approaches using several simulated examples. We also analyze a groundwater-contamination dataset with over 20,000 censored measurements to demonstrate the scalability of our method for partially censored Gaussian-process models. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.