Fast Test Inversion for Resampling Methods

Randomization-based inference commonly relies on grid search methods to construct confidence intervals by inverting hypothesis tests over a range of parameter values. While straightforward, this approach is computationally intensive and can yield conservative intervals due to discretization. We propose a novel method that exploits the algebraic structure of a broad class of test statistics--including those with variance estimators dependent on the null hypothesis--to produce exact confidence intervals efficiently. By expressing randomization statistics as rational functions of the parameter of interest, we analytically identify critical values where the test statistic's rank changes relative to the randomization distribution. This characterization allows us to derive the exact p-value curve and construct precise confidence intervals without exhaustive computation. For cases where the parameter of interest is a vector and a confidence region is needed, our method extends by calculating and storing the coefficients of the polynomial functions involved. This approach enables us to compute approximate p-value functions and confidence regions more efficiently than traditional grid search methods, as we avoid recalculating test statistics from scratch for each parameter value. We illustrate our method using tests from Pouliot (2024) and extend it to other randomization tests, such as those developed by DiCiccio and Romano (2017) and D'Haultf{\oe}uille and Tuvaandorj (2024). Our approach significantly reduces computational burden and overcomes the limitations of traditional grid search methods, providing a practical and efficient solution for confidence interval and region construction in randomization-based inference.