On the Universality of Invariant Networks
This addresses a foundational theoretical gap in machine learning for designing invariant networks, with implications for applications in symmetry-aware models, though it is incremental in extending universality results.
The paper investigates whether invariant networks, which respect symmetry transformations from a group G, can approximate any continuous invariant function, focusing on subgroups of the symmetric group acting by permuting coordinates. It shows that universality is achievable with high-order tensors but not always with first-order ones, providing a necessary condition for the latter case.
Constraining linear layers in neural networks to respect symmetry transformations from a group $G$ is a common design principle for invariant networks that has found many applications in machine learning. In this paper, we consider a fundamental question that has received little attention to date: Can these networks approximate any (continuous) invariant function? We tackle the rather general case where $G\leq S_n$ (an arbitrary subgroup of the symmetric group) that acts on $\mathbb{R}^n$ by permuting coordinates. This setting includes several recent popular invariant networks. We present two main results: First, $G$-invariant networks are universal if high-order tensors are allowed. Second, there are groups $G$ for which higher-order tensors are unavoidable for obtaining universality. $G$-invariant networks consisting of only first-order tensors are of special interest due to their practical value. We conclude the paper by proving a necessary condition for the universality of $G$-invariant networks that incorporate only first-order tensors.