Fast Conservative Monte Carlo Confidence Intervals

Extant "fast" algorithms for Monte Carlo confidence sets are limited to univariate shift parameters for the one-sample and two-sample problems using the sample mean as the test statistic; moreover, some do not converge reliably and most do not produce conservative confidence sets. We outline general methods for constructing confidence sets for real-valued and multidimensional parameters by inverting Monte Carlo tests using any test statistic and a broad range of randomization schemes. The method exploits two facts that, to our knowledge, had not been combined: (i) there are Monte Carlo tests that are conservative despite relying on simulation, and (ii) since the coverage probability of confidence sets depends only on the significance level of the test of the true null, every null can be tested using the same Monte Carlo sample. The Monte Carlo sample can be arbitrarily small, although the highest nontrivial attainable confidence level generally increases as the number $N$ of Monte Carlo replicates increases. We present open-source Python and R implementations of new algorithms to compute conservative confidence sets for real-valued parameters from Monte Carlo tests, for test statistics and randomization schemes that yield $P$-values that are monotone or weakly unimodal in the parameter, with the data and Monte Carlo sample held fixed. In this case, the new method finds conservative confidence sets for real-valued parameters in $O(n)$ time, where $n$ is the number of data. The values of some test statistics for different simulations and parameter values have a simple relationship that makes more savings possible.