Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

Ali Syed, Aditya Nambiar, Jonathan W. Siegel · 2026

Read Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling by Ali Syed, Aditya Nambiar, Jonathan W. Siegel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08377.txt.

Description

Ali Syed, Aditya Nambiar, and Jonathan Siegel bound the price of permutation symmetry in set-based networks. Deep Sets and its generalization Janossy pooling process point clouds and other unordered sets. They embed each element before pooling. Universality asks whether they can approximate any symmetric function.

The question the authors settle is how wide that embedding must be. With a new technique, they prove lower bounds on the required embedding dimension. For Deep Sets, the bound pins the minimum to within a constant factor. That holds for every point dimension above one. For k-ary Janossy pooling with k above one, they give the first nontrivial bound of its kind.

Catalog record

CREATORAli Syed, Aditya Nambiar, Jonathan W. Siegel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.08377

Browse the full library · About the Tower of Babel