  Randomization tests rely on simple data transformations and possess an
appealing robustness property. In addition to being finite-sample valid if the
data distribution is invariant under the transformation, these tests can be
asymptotically valid under a suitable studentization of the test statistic,
even if the invariance does not hold. However, practical implementation often
encounters noisy data, resulting in approximate randomization tests that may
not be as robust. In this paper, our key theoretical contribution is a
non-asymptotic bound on the discrepancy between the size of an approximate
randomization test and the size of the original randomization test using
noiseless data. This allows us to derive novel conditions for the validity of
approximate randomization tests under data invariances, while being able to
leverage existing results based on studentization if the invariance does not
hold. We illustrate our theory through several examples, including tests of
significance in linear regression. Our theory can explain certain aspects of
how randomization tests perform in small samples, addressing limitations of
prior theoretical results.
