  Invariance-based randomization tests -- such as permutation tests -- are an
important and widely used class of statistical methods. They allow drawing
inferences with few 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. Moreover, we allow actions by general linear group representations.
  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, symmetric submatrix
detection, and two-sample testing. Perhaps surprisingly, we find that
randomization tests can adapt to problem structure and detect signals at the
same rate as tests with full knowledge of the noise distribution.
