Technical Summary: Achieving Approximate Symmetry is Exponentially Easier Than Exact Symmetry

Problem Statement

The paper addresses a fundamental question in geometric machine learning: What is the computational cost of enforcing exact symmetry versus approximate symmetry? While exact symmetry (invariance or equivariance) is a powerful inductive bias that improves sample complexity and generalization, it often imposes rigid constraints that may not hold in real-world data (e.g., medical imaging or symmetry discovery). Conversely, approximate symmetry offers flexibility but lacks a rigorous theoretical understanding regarding its efficiency compared to exact enforcement.

The authors formalize this comparison through the lens of averaging complexity. They consider a setting where a learner has access to a black-box model and can only post-process it via a limited number of Action Queries (AQs). An AQ consists of querying the model on a transformed input $gx$ for a group element $g$. The goal is to construct a linear combination of these queries (an averaging scheme) that yields a function satisfying the desired symmetry properties. The "cost" is defined as the minimum number of non-zero weights (queries) required in this linear combination.

Methodology and Framework

1. Averaging Complexity Definition

The authors introduce Averaging Complexity as a metric to quantify the difficulty of enforcing symmetry.

• Exact Symmetry: A function is exactly symmetric if $f(gx) = f(x)$ for all $g \in G$. The complexity $AC_{ex}(F)$ is the minimal size of an averaging scheme $\omega$ such that the resulting operator $E_\omega$ maps any $f \in F$ to an exactly symmetric function.
• Approximate Symmetry: Defined via an $L^2(X)$-norm relaxation.
  • Weak Approximate Symmetry: The expected $L^2$ distance to symmetry over random $g$ is reduced by a factor $\epsilon$.
  • Strong Approximate Symmetry: The $L^2$ distance to symmetry is reduced by $\epsilon$ for every $g \in G$.
  • The complexities $AC_{wk}(F, \epsilon)$ and $AC_{st}(F, \epsilon)$ measure the minimal scheme size to achieve these relaxations.

2. Theoretical Tools

The analysis relies heavily on representation theory and Fourier analysis on finite groups:

• Group Representations: The action of the group $G$ on the function space $F$ is viewed as a linear representation $\rho$.
• Tensor Powers: To prove lower bounds for exact symmetry, the authors analyze the symmetric tensor powers $\text{Sym}^{\otimes k}(F)$. They leverage the fact that as $k$ increases, the tensor powers eventually contain all irreducible representations (irreps) of the group.
• Fourier Transform on Groups: The averaging scheme $\omega$ is treated as a signal on the group. Its Fourier transform $\hat{\omega}(\pi)$ (where $\pi$ are irreps) determines the behavior of the averaging operator.
  • For exact symmetry, $\hat{\omega}(\pi)$ must vanish for all non-trivial irreps.
  • For approximate symmetry, $\hat{\omega}(\pi)$ must have a small operator norm for non-trivial irreps.

3. Proof Strategy

• Lower Bound (Exact Symmetry): The authors show that if the function class includes sufficiently high-order tensor powers (specifically up to degree $K$), the averaging scheme must have non-zero weights on all group elements to annihilate all non-trivial irreps. This forces the scheme to be the uniform distribution over $G$, requiring $|G|$ queries.
• Upper Bound (Approximate Symmetry): Using a probabilistic construction, the authors demonstrate that a random subset of group elements of size $O(\log |G|)$ suffices to make the Fourier coefficients of non-trivial irreps small (bounded by $\epsilon$) with high probability. This relies on matrix concentration inequalities (e.g., Matrix Bernstein).

Key Results

The paper establishes an exponential separation between the complexities of exact and approximate symmetry enforcement:

1. Linear Complexity for Exact Symmetry:
   Under a "Faithful Group Action" assumption, there exists a degree $K$ (dependent on the group structure and function class) such that enforcing exact symmetry on the space of polynomial features of degree $K$ requires linear averaging complexity:
   $$AC_{ex}(\text{Sym}^{\otimes K}(F)) = |G|$$
   This implies that to guarantee exact invariance for rich function classes, one must query the entire group.

2. Logarithmic Complexity for Approximate Symmetry:
   For any function class $F$ and any precision $\epsilon > 0$, the averaging complexity for both weak and strong approximate symmetry is logarithmic in the group size:
   $$AC_{wk}(F, \epsilon) = O\left(\frac{\log |G|}{\epsilon}\right), \quad AC_{st}(F, \epsilon) = O\left(\frac{\log |G|}{\epsilon}\right)$$
   This bound is universal and does not depend on the specific structure of the function class, only on the group size.

3. Tightness:
   The paper provides a lower bound showing that $\Omega(\log |G|)$ queries are necessary for approximate symmetry in certain cases (e.g., when the group is a vector space over $\mathbb{F}_2$), confirming that the logarithmic upper bound is tight up to constants.

Experimental Validation

The authors present a proof-of-concept experiment involving a regression task with sign-flip symmetry ($G = \{\pm 1\}^d$).

• Setup: A neural network is trained on data labeled by a target function invariant under sign flips. At evaluation, predictions are averaged over a random subset $S \subset G$.
• Observation: The test loss decreases as the subset size $|S|$ increases. Crucially, the majority of the performance gain is achieved when $|S| \approx 32$ (which is $\log_2(2^{20})$ for $d=20$), with diminishing returns for larger subsets.
• Conclusion: This empirically validates the theoretical claim that logarithmic-sized subsets capture the benefits of full group averaging.

Significance and Claims

The paper claims to provide the first theoretical separation between exact and approximate symmetry in the context of machine learning. Its primary contributions are:

1. Theoretical Justification for Approximate Symmetry: The results formally justify why approximate symmetry is often preferred in practice. It is not merely a heuristic for handling noise; it is exponentially more efficient to achieve in terms of query complexity.
2. New Metric (Averaging Complexity): The introduction of averaging complexity provides a new framework for quantifying the cost of symmetry enforcement, independent of specific model architectures.
3. Generalizability: The tools developed (representation-theoretic analysis of averaging schemes) are presented as having independent interest for broader studies in geometric machine learning, including data augmentation and symmetry discovery.

The authors remain modest regarding the scope, noting that the results apply to finite groups and that extending these bounds to infinite groups or other metrics (beyond $L^2$) remains an open challenge. They emphasize that while exact symmetry is theoretically "perfect," the exponential cost makes approximate symmetry the practically superior choice for large groups.