Quantitative Approximation Rates for Group Equivariant Learning

1. Problem Statement

The paper addresses a gap in the theoretical understanding of Group Equivariant Learning. While the Universal Approximation Theorem guarantees that neural networks can approximate any continuous function, it lacks quantitative approximation rates (i.e., how the number of parameters scales with the desired accuracy $\epsilon$).

Existing literature has established these rates for standard deep ReLU networks approximating $\alpha$-Hölder functions on compact sets (typically scaling as $\sim \epsilon^{-N/2\alpha}$ where $N$ is the input dimension). However, it is unclear whether equivariant or invariant architectures (which hard-code symmetries like permutations or rotations) suffer a loss in expressivity or, conversely, gain efficiency by exploiting the reduced dimensionality of the orbit space $V/G$.

The authors pose two central questions:

1. Theoretical Limit: Can non-equivariant ReLU networks achieve the optimal approximation rate of $\sim \epsilon^{-N_G/2\alpha}$ (where $N_G$ is the dimension of the quotient space) when approximating invariant/equivariant functions?
2. Architectural Capability: Do specific equivariant architectures (e.g., Deep Sets, Transformers, Frame Averaging) achieve these same optimal rates?

2. Methodology

The authors employ tools from approximation theory, covering numbers, and geometric group theory to derive upper bounds on the number of parameters required for approximation.

• Metric and Dimensionality: They define the problem on a quotient space $V/G$ equipped with a metric $d_G([x], [y]) = \min_{g \in G} \|gx - y\|$. The complexity of approximation is tied to the covering number $N_r(K/G)$ of the quotient space.
• Smoothness: The target functions $f$ are assumed to be $\alpha$-Hölder continuous ($|f(x) - f(y)| \leq C\|x-y\|^\alpha$).
• Constructive Proofs:
  • Deep Sets & Sumformers: They construct explicit ReLU networks using a "digit encoding" strategy. They partition the input domain into small cells, encode the count of points in each cell using base-$(n+1)$ integers, and use a "median" trick over multiple shifted partitions of unity to handle discontinuities and ensure the network is continuous and representable by ReLUs.
  • Rigid Motions ($E(d)$): They utilize the Gram-Schmidt procedure to map point clouds to a canonical subspace. They prove that the Gram-Schmidt process (involving normalization and projection) can be "super-approximated" by ReLU networks with logarithmic depth in $1/\epsilon$. This allows reducing the approximation problem from the full space to a lower-dimensional subspace isomorphic to the quotient space.
  • Bi-Lipschitz Models: They leverage the property that if an embedding $E: V \to \mathbb{R}^m$ is bi-Lipschitz on the quotient space, then approximating $f \circ E^{-1}$ (a function on $\mathbb{R}^m$) yields an approximation for $f$ with rates determined by the intrinsic dimension of the quotient, not the embedding dimension.

3. Key Contributions and Results

The paper provides quantitative approximation rates for three distinct settings, summarized in Table 1 of the paper.

Setting 1: Permutation Invariant/Equivariant Models

• Context: Point sets $X \in \mathbb{R}^{d \times n}$ invariant or equivariant under the permutation group $S_n$.
• Result: Since $S_n$ is finite, the dimension of the quotient space is the same as the ambient space ($N_G = nd$).
• Findings:
  • Deep Sets: The authors prove that Deep Sets architectures can approximate $\alpha$-Hölder permutation-invariant functions with a parameter count of $\sim \epsilon^{-nd/2\alpha}$. This matches the optimal rate for general ReLU networks, proving no loss of expressivity despite the architectural constraints.
  • Sumformer & Transformers: By characterizing equivariant functions as a composition of a shared invariant function and a "omit-one" sum, they show that Sumformers and Transformers also achieve the optimal rate $\sim \epsilon^{-nd/2\alpha}$.
  • Side Result: They improve the known approximation rate for non-invariant functions on low-intrinsic-dimension manifolds from $\epsilon^{-d_{intrinsic}/\alpha}$ to $\epsilon^{-d_{intrinsic}/2\alpha}$.

Setting 2: Joint Invariance to Permutations and Rigid Motions

• Context: Point clouds invariant under $E(d) \times S_n$ (rotations, translations, and permutations). This is crucial for 3D point cloud processing.
• Result: The dimension of the quotient space is reduced: $N_G = nd - \dim(E(d))$.
• Findings:
  • Non-Equivariant ReLU: They prove that standard ReLU networks can approximate these invariant functions with rates scaling as $\sim \epsilon^{-(nd - \dim(E(d)))/2\alpha}$. This confirms that the "hard" constraint of invariance does not hinder the ability of generic networks to learn the function efficiently.
  • Frame Averaging: They show that invariant models constructed by applying Frame Averaging (averaging over a discrete set of group elements) to a Deep Sets backbone also achieve these optimal rates. This validates the theoretical efficiency of popular methods like those based on SVD canonicalization or principal direction alignment.

Setting 3: General Bi-Lipschitz Invariant Models

• Context: General closed isometry groups $G$ acting on $V$.
• Result: For any model that provides a bi-Lipschitz embedding of the quotient space (e.g., Max Filters, sorting-based embeddings, Fourier Sliced-Wasserstein), the approximation rate is determined solely by the intrinsic dimension of the quotient space.
• Findings:
  • Theorem 21: If $E$ is a bi-Lipschitz invariant map, then $f$ can be approximated by $\psi \circ E$ with parameters scaling as $\sim \epsilon^{-d_{intrinsic}/2\alpha}$.
  • This unifies various specific models (Max Filters, sorting, etc.) under a single theoretical guarantee of optimal expressivity.

4. Significance and Implications

1. Expressivity vs. Efficiency: The paper resolves a key debate in equivariant learning. It demonstrates that hard-coding symmetries does not reduce the asymptotic expressivity of neural networks. Equivariant models are not "weaker" than generic ReLU networks; they are equally expressive over the class of symmetric functions.
2. Source of Practical Benefits: Since the approximation rates are identical, the empirical success of equivariant models (better generalization, sample efficiency) must be attributed to optimization landscape improvements and sample complexity reductions, rather than a fundamental increase in the ability to represent the function class.
3. Theoretical Validation of Architectures: The results provide rigorous justification for the use of Deep Sets, Transformers, and Frame Averaging in geometric deep learning, confirming they are theoretically capable of achieving optimal convergence rates for smooth symmetric functions.
4. Intrinsic Dimensionality: The work highlights that the complexity of learning symmetric functions is governed by the dimension of the orbit space (quotient space), not the raw input dimension. This provides a formal framework for understanding why equivariant models work well on high-dimensional data with low-dimensional symmetries.

Conclusion

The paper bridges the gap between qualitative universality and quantitative approximation theory for group equivariant learning. It establishes that for $\alpha$-Hölder functions, specialized equivariant architectures achieve the same optimal approximation rates as generic networks, provided the network size scales with the dimension of the quotient space. This suggests that the primary advantage of equivariant models lies in data efficiency and optimization, not in raw representational power.