A Unified Framework for Statistical Testing of Invariance

While invariances naturally arise in almost any type of real-world data, no efficient and robust test exists for detecting them in observational data under arbitrarily given group actions. We tackle this problem by studying discrepancy-based measures of invariance that can capture even subtle distributional asymmetries. Our first contribution is to show that, while detecting worst-case asymmetries can be \emph{computationally intractable}, a randomized method can estimate closeness measures to invariance within \emph{universal constant factors}. This provides a general framework for statistical testing of invariance under compact group actions. Despite the extensive and well-established literature on group-based testing, our methodology, to the best of our knowledge, is the \emph{first} to provide statistical tests for general group invariances with \emph{finite-sample guarantees on Type II errors} against worst-case alternatives. We instantiate the framework for common probability discrepancies, including total variation, Wasserstein distances, integral probability metrics, energy distance, and maximum mean discrepancy, obtaining explicit sample-complexity guarantees from empirical convergence rates.