🤖 machine learning

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

This paper establishes new lower bounds on the embedding dimension required to guarantee universality for permutation-invariant neural networks, specifically proving the correct minimal dimension up to a constant factor for Deep Sets and providing the first non-trivial lower bound for $k$ -ary Janossy pooling when $k > 1$ .

Original authors: Ali Syed, Aditya Nambiar, Jonathan W. Siegel

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Syed, Aditya Nambiar, Jonathan W. Siegel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to understand a bag of marbles. It doesn't matter if you pull the marbles out in a specific order (red, blue, green) or a different order (green, red, blue); the bag is the same. In the world of AI, this is called permutation invariance. The computer needs to learn that the set of marbles matters, not the sequence in which they appear.

To do this, scientists use special neural network architectures called Deep Sets and Janossy Pooling. Think of these as a two-step process:

The Encoder (The Translator): It looks at each marble (or small groups of marbles) and translates them into a secret code, or "embedding."
The Aggregator (The Summarizer): It adds up all these secret codes to create a final answer.

The big question this paper asks is: How long does that secret code need to be?

If the code is too short, the computer gets confused. It might think two completely different bags of marbles are the same. If the code is long enough, the computer can distinguish between any two different bags. The authors of this paper wanted to find the minimum length required for this code to work perfectly for any possible bag of marbles.

The Problem: The "Too Short" Code

Imagine you have a bag of 10 marbles, and you want to describe them using a secret code.

If you only use a code with 1 digit (0 or 1), you can only describe two things. You can't possibly describe 10 different marbles uniquely.
If you use a code with 10 digits, you might be able to do it, but maybe not if the marbles are complex (like 3D objects instead of just colors).

The paper proves that there is a hard mathematical limit on how short this code can be. If you go below this limit, no matter how smart your computer is, it will fail to tell some different bags apart.

The New Discovery: A "Topological" Trick

The authors used a clever mathematical tool called the Borsuk-Ulam theorem. To understand this simply, imagine a globe (the Earth). The theorem basically says: "If you paint the Earth with a certain number of colors, there will always be two opposite points (like the North and South Pole) that share the same color."

The authors used this idea to prove that if your secret code is too short, the computer's "translator" will inevitably make a mistake. It will accidentally assign the exact same code to two completely different bags of marbles that are "opposite" in a mathematical sense. Because the codes are identical, the computer can't tell them apart.

What They Found

The paper gives specific rules for how long the code needs to be based on two things:

$n$ : How many items are in the bag (e.g., 10 marbles).
$d$ : How complex each item is (e.g., a simple number vs. a 3D point with x, y, and z coordinates).

Here are their main findings in plain English:

1. For the Simple Case (Deep Sets):
If the computer looks at marbles one by one (ignoring how they interact with each other), the code length must be at least $d \times (n - 1)$ .

Analogy: If you have 10 marbles in 3D space ( $d=3$ ), you need a code of at least $3 \times 9 = 27$ digits.
Why it matters: Before this, we knew the code needed to be at least $n$ (10). This paper proves it actually needs to be much longer (27) because the marbles are 3D objects. It closes the gap between what we knew was necessary and what we knew was sufficient.

2. For the Complex Case (Janossy Pooling):
If the computer looks at groups of marbles at once (e.g., pairs or triplets), the math gets more complicated. The authors proved the first-ever non-trivial rule for this.

They found the code length must grow with the complexity of the items and the number of items, roughly following the formula: $(d \times n)^{1/k}$ , where $k$ is the group size.
Analogy: Even if you let the computer look at pairs of marbles to understand them better, you can't get away with a tiny code. The code still has to grow as the marbles get more complex or the bag gets bigger.

The "Fixed" vs. "Flexible" Translator

The paper also highlights a subtle but important distinction:

Fixed Translator: If you force the computer to use the same translation rules for every problem, the code needs to be very long (at least $d \times n$ ).
Flexible Translator: If you allow the computer to change its translation rules depending on the specific problem, you can get away with a slightly shorter code.
The Paper's Result: Even with this flexibility, the authors proved you still can't go below the limits they calculated. There is a hard floor.

Summary

This paper is like a construction inspector for AI architects. It says: "You cannot build a house (a neural network) that understands sets of objects if you use too little material (embedding dimension). We have calculated the exact minimum amount of material you need to guarantee the house won't collapse (fail to distinguish between different inputs)."

They proved that for 3D objects, the "material" needed is significantly more than previously thought, and they provided the first solid proof for how much material is needed when the AI looks at groups of objects rather than just single ones.

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

Problem Statement
The paper addresses the theoretical question of universality in permutation-invariant neural network architectures, specifically Deep Sets and its generalization, Janossy pooling. While it is established that these architectures can approximate any continuous permutation-invariant function, a critical open problem remains: determining the minimal embedding dimension $M$ (the latent dimension) required to guarantee this universality.

Previous work has provided sufficient upper bounds (e.g., $M = 2nd + 1$ for Deep Sets with $d > 1$ ) and necessary lower bounds only in specific cases (e.g., $M \ge n$ for $d=1$ ). For Deep Sets with $d > 1$ , no lower bound growing with the ambient dimension $d$ was known. For $k$ -ary Janossy pooling (where $k > 1$ ), no non-trivial lower bounds existed. The paper focuses on the scalar-output case ( $p=1$ ) where the encoder maps $\Phi$ may depend on the target function $f$ , a setting where standard embedding obstructions do not directly apply.

Methodology
The authors introduce a novel technique based on the Borsuk-Ulam theorem to derive lower bounds on the embedding dimension. The methodology proceeds through the following logical steps:

Reduction to Indexed Janossy Pooling: The authors first establish that if the standard $k$ -ary Janossy architecture is universal, then a larger class of functions, termed "indexed Janossy pooling," must also be universal. In this indexed class, the encoder $\Phi$ is allowed to depend on the specific indices of the input tuple $(i_1, \dots, i_k)$ , rather than being a single shared function $\Phi(x_{i_1}, \dots, x_{i_k})$ . This reduction allows the authors to prove a lower bound for the indexed class, which automatically applies to the standard class.
Finite-Difference Rigidity: A key lemma is proven showing that for an indexed Janossy latent map, if the map agrees on an "axis" subset of a grid (where at least one coordinate is zero), it must agree on the entire grid. This property is derived using finite-difference arguments.
Borsuk-Ulam Construction: To prove the lower bound, the authors construct two disjoint compact sets, $E_+$ and $E_-$ , within the input space. They utilize the Borsuk-Ulam theorem to show that if the embedding dimension $M$ is below a certain threshold, any continuous indexed latent map $\Phi$ must map some pair of points $x_+ \in E_+$ and $x_- \in E_-$ to the same latent vector (a collision).
Separation Argument: By constructing a continuous function $g$ that takes value 1 on $E_+$ and 0 on $E_-$ , they demonstrate that any architecture with a latent dimension below the derived threshold cannot approximate $g$ uniformly, thereby violating universality.

Key Contributions and Results

New Lower Bound Technique: The paper presents a Borsuk-Ulam-based method specifically designed to handle the case where the encoder depends on the target function, overcoming the limitations of fixed-feature embedding obstructions.
Deep Sets ( $k=1$ ): For Deep Sets acting on sets of $n$ points in $\mathbb{R}^d$ , the authors prove the lower bound:
$M_{\text{univ}}(d, n, 1) \ge d(n - 1)$
This is the first lower bound for $d > 1$ that grows with the ambient dimension $d$ . Combined with existing upper bounds, this establishes that the required latent dimension scales linearly with both $n$ and $d$ (specifically $\Theta(nd)$ ) up to constant factors.
$k$ -ary Janossy Pooling ( $k > 1$ ): For general $k$ -ary Janossy pooling, the paper proves the first non-trivial lower bound:
$M_{\text{univ}}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$
This result demonstrates that even with higher-order interactions ( $k > 1$ ), the required latent dimension must grow with both the ambient dimension $d$ and the set size $n$ .
Summary of Bounds: The paper provides a comprehensive overview of known bounds (Table 1), highlighting that for $k > 1$ , the new lower bound is the first to explicitly depend on $d$ and $n$ in a non-trivial way.

Significance and Claims
The authors claim that their results resolve significant gaps in the theoretical understanding of permutation-invariant architectures:

Deep Sets: The result confirms that for $d > 1$ , the embedding dimension must scale with $d$ , correcting the previous lack of dimension-dependent lower bounds. The scaling $d(n-1)$ is shown to be tight up to constant factors when compared to the $2nd+1$ upper bound.
Janossy Pooling: The paper establishes that finite-order interactions do not eliminate the need for large latent dimensions; the dimension must still grow with the problem size and ambient dimension.
Methodological Advance: The Borsuk-Ulam approach provides a new tool for analyzing universality in settings where the encoder is target-dependent, a scenario where standard topological embedding obstructions fail.

Limitations
The authors note that the derived bounds are not sharp in all regimes.

For Deep Sets, the bound is $d(n-1)$ rather than $dn$, a gap attributed to the construction requiring one input point to separate the obstruction sets.
For $k > 1$ , the exponent $1/k$ in the lower bound is a limitation of the current construction (specifically the grid labeling strategy). There remains a substantial gap between this lower bound and the inherited $O(nd)$ upper bound from Deep Sets. Determining the exact dependence on $d, n,$ and $k$ for finite-order Janossy pooling remains an open problem.

The Problem: The "Too Short" Code

The New Discovery: A "Topological" Trick

What They Found

The "Fixed" vs. "Flexible" Translator

Summary

More like this