Exponential Separations in Symmetric Neural Networks

Abstract

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.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Zweig and Bruna. "Exponential Separations in Symmetric Neural Networks." Neural Information Processing Systems, 2022.

Markdown

[Zweig and Bruna. "Exponential Separations in Symmetric Neural Networks." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/zweig2022neurips-exponential/)

BibTeX

@inproceedings{zweig2022neurips-exponential,
  title     = {{Exponential Separations in Symmetric Neural Networks}},
  author    = {Zweig, Aaron and Bruna, Joan},
  booktitle = {Neural Information Processing Systems},
  year      = {2022},
  url       = {https://mlanthology.org/neurips/2022/zweig2022neurips-exponential/}
}