Research map / Architectures and efficiency / RNNs and normalization
Polynomial Width is Sufficient for Set Representation with High-dimensional Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically that DeepSets latent dimension L only needs to be polynomial in set size N and feature dimension D (for high-dimensional features, real or complex), via linear+power and linear+exponential embedding layers.
Problem
Determining the minimal latent dimension L of DeepSets-style sum-pooling architectures needed to exactly represent continuous set functions over high-dimensional set features (D>1), where prior bounds were exponential in N or D or required complex-analytic activations.
Approach
Constructs anchor-based linear mixing of feature channels so that sum-of-power (linear + power mapping) or sum-of-exponential (linear + exp activation) pooling is injective with a continuous inverse, giving L polynomial in N and D instead of exponential, under real-valued and non-analytic activations.
Key results
- Proves L in [N(D+1), N^5 D^2) suffices and is necessary-lower-bounded for the linear+power (LP) embedding layer for exact set representation with D>1.
- Proves L in [ND, N^4 D^2] suffices for the linear+exponential (LE) embedding layer, improving the upper bound.
- Numerical experiments show log(L*) grows linearly in log N and log D, consistent with polynomial rather than exponential scaling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the LP embedding layer (linear + power mapping) | DeepSets · Continuous permutation-invariant set functions (D ≥ 2) | embedding dimension L: {N+D choose N} - 1 -> N(D+1) ≤ L < N^5D^2 | Helped |
| Use the LE embedding layer (linear + exponential activation) | DeepSets · Continuous permutation-invariant set functions (D ≥ 2) | embedding dimension L: exp(min{√N, D}) -> ND ≤ L ≤ N^4D^2 | Helped |
| Use LE instead of LP | DeepSets · Continuous permutation-invariant set functions (D ≥ 2) | upper bound on embedding dimension L: N^5D^2 -> N^4D^2 | Helped |
| Use polynomial-width LP or LE embeddings rather than the prior exponential-size multivariate polynomial construction | DeepSets · High-dimensional set representation | embedding dimension L: {N+D choose N} - 1 -> N^5D^2 (LP); N^4D^2 (LE) | Helped |
| Set LP's number of linear projections to K ≤ D | LP embedding layer · Continuous permutation-invariant set functions (D ≥ 2) | injectivity of sum-pooling: K ≥ D+1 | Hurt |
| Set LE's embedding dimension below ND | LE embedding layer · Continuous permutation-invariant set functions (D ≥ 2) | injectivity of sum-pooling: L < ND | Hurt |
| Increase the neural-network embedding width L | Empirical DeepSets with SiLU embedding and ReLU decoder · Lexicographical median of vector-valued sets | training RMSE | Helped |
Surprising findings
- Lower bound shows that embedding dimension equal to the degree of freedom ND is not enough for LP injectivity, so K must exceed D.
Limitations
- Tightness of the polynomial bounds is not examined.
- Complexity of the decoder rho is not characterized and may be high in practice.
- Continuity of rho is required; without it, trivial bijection constructions exist.
Experimental setup
Metrics: RMSE critical width L* vs N and D
Baselines: DeepSets Segol & Lipman multi-symmetric polynomial construction Zweig & Bruna exponential-dimension construction
Builds on: DeepSets Wagstaff et al. minimal latent dimension results Zweig & Bruna symmetric polynomial embedding
Closest papers by meaning
- On the Expressive Power of Deep Polynomial Neural Networks (NeurIPS 2019 · similarity 0.88)
- $\mathcal{O}(\log N)$ Latent Dimension Suffices for Universal Approximation of Permutation-invariant Function (ICML 2026 · similarity 0.87)
- Transport of Algebraic Structure to Latent Embeddings (ICML 2024 · similarity 0.85)
- Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach (NeurIPS 2025 · similarity 0.84)
- Fourier Sliced-Wasserstein Embedding for Multisets and Measures (ICLR 2025 · similarity 0.84)
- Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $\mu$ Parametrization (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.