Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling
Provides theoretical guarantees for practitioners designing permutation-invariant neural networks, clarifying the minimal embedding size needed for universal function approximation.
This paper proves new lower bounds on the embedding dimension required for Deep Sets and Janossy pooling architectures to achieve universality on permutation-invariant functions over point clouds. For Deep Sets, the bound is tight up to a constant factor for all dimensions d > 1; for k-ary Janossy pooling, it provides the first non-trivial lower bound for k > 1.
In many practical applications it is important to build symmetries into neural network architectures. Consider the important case of permutation symmetry on point clouds consisting of $n$ points in $d$ dimensions. In this case the network learns a function on a set of $n$ points in $\mathbb{R}^d$, and a natural paradigm for constructing invariant networks is Janossy pooling, which generalizes the popular Deep Sets architecture. We study the universality of this approach, in particular the important question of how large the embedding dimension must be to guarantee universality of this architecture. Specifically, using a novel technique, we prove new lower bounds on the required size of this embedding dimension. For Deep Sets, this gives the correct minimal dimension up to a constant factor for all $d > 1$. For $k$-ary Janossy pooling, we prove the first non-trivial lower bound on the required embedding dimension when $k > 1$.