  Invariance-based randomization tests -- such as permutation tests, rotation
tests, or sign changes -- are an important and widely used class of statistical
methods. They allow drawing inferences under weak assumptions on the data
distribution. Most work focuses on their type I error control properties, while
their consistency properties are much less understood.
  We develop a general framework and a set of results on the consistency of
invariance-based randomization tests in signal-plus-noise models. Our framework
is grounded in the deep mathematical area of representation theory. We allow
the transforms to be general compact topological groups, such as rotation
groups, acting by general linear group representations. We study test
statistics with a generalized sub-additivity property. We apply our framework
to a number of fundamental and highly important problems in statistics,
including sparse vector detection, testing for low-rank matrices in noise,
sparse detection in linear regression, and two-sample testing. Comparing with
minimax lower bounds, we find perhaps surprisingly that in some cases,
randomization tests detect signals at the minimax optimal rate.
