The Normal Law Under Linear Restrictions: Simulation and Estimation via Minimax Tilting

TL;DR

The paper proposes a minimax exponential tilting method for exact iid simulation and estimation of Gaussian integrals under linear restrictions, improving on the Genz separation-of-variables (SOV) estimator. It proves vanishing relative error in tail asymptotic regimes and demonstrates high accuracy and acceptance rates in numerical examples up to about 100 dimensions.

Key findings

• The minimax-tilted (MET) estimator is unbiased and can achieve vanishing relative error under conditions in Theorems 4.1 and 4.2; otherwise it has bounded relative error.
• In Example I, at \(d=25\) the SOV estimator gave \(2.371\times10^{-48}\) with 33% relative error, while MET gave \(2.6847\times10^{-53}\) with 0.02% relative error; at \(d=50\), MET gave \(2.1364\times10^{-153}\) with 0.06% relative error and acceptance probability 0.95.
• In Example IV with \(A=[1,\infty]^{100}\), MET had median relative error 0.077% versus SOV median 26%, and the MET variance was typically more than \(10^5\) times smaller than SOV.
• For probit posterior simulation, the accept-reject scheme had acceptance rate \(1/217\), compared with naive acceptance rejection of \(O(10^{-146})\) and without minimax tilting \(O(10^{-16})\).

Methods

• The method exponentially tilts the Genz SOV importance density and selects the tilting parameter by solving the minimax saddle-point problem \(\inf_\mu \sup_{x\in C}\psi(x;\mu)\), using log-concavity and Karush-Kuhn-Tucker conditions; the optimal pair is found via Powell’s Dogleg method or a convex solver.
• Exact simulation uses accept-reject with instrumental density \(g(x;\mu^*)\) and envelope \(c=\exp(\psi(x^*;\mu^*))\); the estimator is \(\hat\ell=\exp(\psi(X;\mu^*))\), \(X\sim P_{\mu^*}\).
• Numerical experiments compare MET with SOV using randomized quasi Monte Carlo (Richtmyer sequence), including structured covariance matrices, random correlation matrices, and an extramarital-affairs probit model with \(m=601\) observations, \(k=7\) predictors, and 8000 iid posterior simulations.

Limitations

• The paper states that the method is not a panacea against the curse of dimensionality: acceptance probability eventually becomes a rare-event probability as \(d\to\infty\), and the bounded or vanishing relative error properties do not hold in the \(d\uparrow\infty\) regime; it generally works reliably for \(d\le 100\), and may sometimes work higher only if \(\ell\) does not decay too fast.
• The paper notes that the probit acceptance rate \(1/217\) could have been better and will deteriorate with increasing dimensionality, and that MET is not immune to numerical underflow and loss of precision.
• Evident from the text: MET was about 20% more costly than SOV in Example III, and the numerical comparisons focus mainly on SOV because specialized alternatives are not competitive beyond low dimensions.