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
| CREATOR | Ali Syed, Aditya Nambiar, Jonathan W. Siegel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08377