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

• URL: http://arxiv.org/abs/2605.08377v1
• Date: Fri, 08 May 2026 18:34:54 GMT
• Title: Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling
• Abstract summary: We study the universality of Janossy pooling, which generalizes the popular Deep Sets architecture.<n>We prove new lower bounds on the required size of this embedding dimension.<n>For $k$-ary Janossy pooling, we prove the first non-trivial lower bound on the required embedding dimension when $k > 1$.
• Score: 8.7045093817125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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$.

Related papers

• Geometric Layer-wise Approximation Rates for Deep Networks [13.496991650323038]
  We develop a framework in which depth admits a precise scale-dependent interpretation.<n>Our network design is inspired by multigrade deep learning, where depth serves as a progressive refinement mechanism.
  arXiv  Detail & Related papers  (2026-04-22T06:09:20Z)
• $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval [99.8640829555514]
  This paper studies the minimal dimension required to embed subset memberships ($m$ elements and $mchoose k$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED)<n>The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $ell$ metric, inner product and cosine similarity.
  arXiv  Detail & Related papers  (2026-01-28T18:45:43Z)
• New advances in universal approximation with neural networks of minimal width [4.424170214926035]
  We show that autoencoders with leaky ReLU activations are universal approximators of $Lp$ functions. We broaden our results to show that smooth invertible neural networks can approximate $Lp(mathbbRd,mathbbRd)$ on compacta.
  arXiv  Detail & Related papers  (2024-11-13T16:17:16Z)
• Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifolds [75.51968172401394]
  We study the sample complexity of the neural policy mirror descent (NPMD) algorithm with deep convolutional neural networks (CNN) In each iteration of NPMD, both the value function and the policy can be well approximated by CNNs. We show that NPMD can leverage the low-dimensional structure of state space to escape from the curse of dimensionality.
  arXiv  Detail & Related papers  (2023-09-25T07:31:22Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSets is the most widely used neural network architecture for set representation. We present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE)
  arXiv  Detail & Related papers  (2023-07-08T16:00:59Z)
• Exponential Separations in Symmetric Neural Networks [48.80300074254758]
  We consider symmetric Networkparencitesantoro 2017simple architecture as a natural generalization of DeepSetsparencitezaheerdeep architecture. Under the restriction to analytic activation functions, we construct a symmetric function acting on sets of dimensions $N$ in dimension with $D$.
  arXiv  Detail & Related papers  (2022-06-02T19:45:10Z)
• Universal Approximation of Functions on Sets [39.35754251872388]
  Deep Sets is known to be a universal approximator for continuous set functions. Deep Sets may be viewed as the most efficient incarnation of the Janossy pooling paradigm.
  arXiv  Detail & Related papers  (2021-07-05T11:56:26Z)
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances [9.390008801320024]
  We show that adding one extra neuron to each is sufficient to connect all previously discrete minima into a single manifold. We show that the number of symmetry-induced critical subspaces dominates the number of affine subspaces forming the global minima manifold.
  arXiv  Detail & Related papers  (2021-05-25T21:19:07Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  We present a simple proof for the benefit of depth in multi-layer feedforward network with rectified activation ("depth separation") We present a concrete neural network with linear depth (in $m$) and small constant width ($leq 4$) that classifies the problem with zero error.
  arXiv  Detail & Related papers  (2021-01-18T15:40:27Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.