Exponential Separations in Symmetric Neural Networks
In this work we demonstrate a novel separation between symmetric neural
network architectures. Specifically, we consider the Relational
Network~\parencite{santoro2017simple} architecture as a natural generalization
of the DeepSets~\parencite{zaheer2017deep} architecture, and study their
representational gap. Under the restriction to analytic activation functions,
we construct a symmetric function acting on sets of size $N$ with elements in
dimension $D$, which can be efficiently approximated by the former
architecture, but provably requires width exponential in $N$ and $D$ for the
latter.