acceptodds
Under review as a conference paper at ICLR 2027

Exponential Separation between Linear Transformers and Janossy Pooling Networks from a Functional Perspective

Abstract

Permutation-invariant architectures, including Janossy pooling networks and linear Transformers, are ubiquitous in modern deep learning, yet their relative theoretical strengths remain insufficiently understood. Through the approximation of statistical functionals, we systematically compare these architectures and establish an exponential separation in representational efficiency favoring linear Transformers. We establish their universal approximation property (UAP) for continuous functionals of probability measures. Despite this universality, we construct a normalized hard functional involving two-stage feature extraction, exactly representable by a shallow linear Transformer with a scalar pooled representation. Nevertheless, DeepSets require a latent dimension exponential in the input dimension for fixed nontrivial accuracy under a suitable input-measure distribution. We further extend this separation to -ary Janossy pooling networks under the uniform norm. These lower bounds hold for arbitrary continuous real-valued feature maps and readouts, regardless of their expressivity. The separation stems from a structural distinction: linear Transformers use multistage information aggregation to implement input-distribution-dependent feature maps, whereas Janossy pooling employs fixed feature maps. Our results expose an intrinsic information bottleneck of single-stage fixed-arity pooling that UAP alone does not capture.

Primary area:
learning theory
Keywords:
Permutation-invariant, Linear Transformer, Janossy Pooling, Statistical functionals, Architecture separation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YHNWOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper proves that Janossy pooling networks and shallow linear Transformers with a single head universally approximate continuous statistical functionals, and establishes an exponential separation in latent dimension that favors linear Transformers, answering an open question from a previous paper.

Critical strengths
  1. The paper is generally well written and structured.
  2. The attempt to answer an open question from previous work is rewarding.
Critical weaknesses

The paper does not sufficiently motivate the practical implications of its theoretical findings. While the mathematical derivations are the central focus, the absence of empirical validation—even on toy datasets or synthetic benchmarks—leaves the practical relevance of the theorems unclear. Furthermore, in an era where formal verification (such as Lean) and automated reasoning are increasingly accessible, unverified theoretical claims without accompanying empirical grounding or reproducible code have limited actionable value for practitioners.

Questions for authors
  1. Could the authors provide a more self-contained explanation and intuitive background on "exponential separation" early in the text to improve readability for a general ML audience?
  2. Why is establishing an exponential separation in this setting practically meaningful? The current framing appears primarily descriptive rather than offering constructive guidance.
  3. Could the authors clarify the motivation for analyzing linear Transformers instead of standard softmax Transformers? Does the analysis rely on linearity for tractability, or does it reflect a specific practical use case?
  4. What actionable takeaways—if any—do the separation results between Janossy pooling and linear Transformers provide for researchers designing or deploying these architectures?
3 comments

We thank the reviewer for recognizing the theoretical contributions and clear presentation of our work, and for highlighting the need for empirical validation and clearer practical implications. We address the concerns and questions point by point below. All corresponding changes in the revised manuscript are highlighted in blue.

Given the character limit, we split our response into two comments: the first addresses the reviewer’s stated weakness, while the second addresses the questions raised. We begin with the response to the weakness.

[W1] Lack of empirical validation

We have added synthetic experiments on two tasks: learning the hard functional constructed in our manuscript and principal eigenvector estimation under the classical rank-one spiked covariance model (Johnstone, 2001). For principal eigenvector estimation, We sample an unknown direction v∼Unif⁡(Sd−1)\boldsymbol v\sim\operatorname{Unif}(\mathbb S^{d-1}) and generate i.i.d. observations xi=ziv+ni\boldsymbol x_i=z_i \boldsymbol v+\boldsymbol n_i, where zi∼N(0,1)z_i\sim\mathcal N(0,1) and ni∼N(0,Id)\boldsymbol n_i\sim\mathcal N(0,\mathbf I_d). The objective is to give an estimation v^\widehat{\boldsymbol v}, evaluated using the absolute cosine similarity ∣⟨v^,v⟩∣|\langle\widehat{\boldsymbol v},\boldsymbol v\rangle|.

We compare DeepSets, Relational Networks, and Linear Transformers across latent dimensions MM. The results are as follows:

Hard-functional learning (MSE, lower is better)

Architecture / MM481632
DeepSets0.36650.33320.32590.3566
Relational Network0.25800.22490.28690.2548
Linear Transformer3.86×10−5\boldsymbol{3.86\times 10^{-5}}3.27×10−5\boldsymbol{3.27\times 10^{-5}}2.08×10−5\boldsymbol{2.08\times 10^{-5}}7.77×10−5\boldsymbol{7.77\times 10^{-5}}

Principal eigenvector estimation (cosine similarity, higher is better):

Architecture / MM8163264
DeepSets0.36840.47490.55210.5572
Relational Network0.40460.52210.56560.5572
Linear Transformer0.5791\boldsymbol{0.5791}0.8197\boldsymbol{0.8197}0.9106\boldsymbol{0.9106}0.9195\boldsymbol{0.9195}

Linear Transformers consistently outperform the two pooling architectures. Increasing MM brings limited gains for DeepSets, while pairwise interactions yield only marginal improvements for Relational Networks.

Mechanism. Both tasks require multistage information aggregation. For hard-functional learning, it needs first computing the barycenter mρ\boldsymbol m_{\rho} and then extracting the adaptive feature ∣⟨x,mρ⟩∣|\langle \boldsymbol x,\boldsymbol m_{\rho}\rangle|. Linear attention naturally implements these two stages, whereas Janossy pooling relies on fixed feature maps. For principal eigenvector estimation, single-stage pooling can yield the empirical covariance N−1∑i=1Nxixi⊤→Id+vv⊤N^{-1}\sum_{i=1}^{N} \boldsymbol x_i\boldsymbol x_i^\top \to \mathbf I_d+\boldsymbol v\boldsymbol v^\top, whose leading-to-noise eigenvalue ratio is 2:12:1. In contrast, with identity query, key, and value maps, pooling after aggregation via linear attention can yield N−1∑i=1NAttn⁡i(X)Attn⁡i(X)⊤→Id+7vv⊤N^{-1} \sum_{i=1}^N \operatorname{Attn}\nolimits_i(\mathbf X)\operatorname{Attn}\nolimits_i(\mathbf X)^\top \to \mathbf I_d+7\boldsymbol v\boldsymbol v^\top, increasing the eigenvalue ratio to 8:18:1. This illustrates how multistage information aggregation amplifies the principal direction.

These experiments are presented in Section 5, with detailed experimental setups provided in Appendix C of the revised manuscript. Reproducible code is available at the Anonymous Repository.

References

  • I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of Statistics, 29(2):295–327, 2001.

We next address the reviewer’s questions (Q1–Q4) point by point.

[Q1] Explanation and backgroud on "exponential separation"

We have expanded the Introduction to briefly introduce statistical functionals and motivate exponential separation from the perspective of approximation efficiency. We also provide an intuition for the exponential latent-dimension lower bound: since statistical functionals encompass permutation-invariant inputs of variable lengths, features extracted for one sequence length may not remain informative for another. Accommodating different lengths may therefore require distinct feature representations, potentially leading to exponential growth in the aggregate latent dimension. We further clarify the structural source of the separation in Remark 3.10 and provide a concrete illustrative example in Appendix B.1 of the revised manuscript.

[Q2] Practical implications for exponential separation under statistical functionals.

Statistical functionals provide a natural framework for modeling permutation-invariant functions on variable-length inputs. Specifically, an unordered set X=x1,…,xNX=\\{\boldsymbol x_1,\ldots,\boldsymbol x_N\\} can be represented by its empirical measure ρ^X=N−1∑i=1Nδxi\widehat\rho_X=N^{-1}\sum_{i=1}^N\delta_{\boldsymbol x_i}, allowing a permutation-invariant function to be viewed as a functional of ρ^X\widehat\rho_X. This formulation is particularly relevant to applications such as point-cloud classification and operator learning, where the number of input points may vary. Establishing exponential separations in this setting provides practical guidance for architecture design: it identifies the limitations of single-stage pooling and highlights the advantages of multistage information aggregation for efficiently representing permutation-invaraint functions of variable length. Our results help inform the design and selection of architectures for such tasks.

[Q3] Motivation for Linear Transformers

We focus on linear Transformers in the main text because they admit a simpler and more transparent theoretical analysis. Indeed, the exponential separation stems from the contrast between the single-stage pooling of rr-ary Janossy networks and the two-stage information aggregation of Transformers, which also holds with standard softmax attention. In particular, we construct a hard functional establishing an analogous exponential separation between softmax Transformers and rr-ary Janossy pooling networks. We have added a brief discussion in Remark 3.10 and provided the detailed construction and proof in Appendix B.5 of the revised manuscript.

[Q4] Architectural Takeaways

Our results suggest that, for practical variable-length permutation-invariant tasks, such as point-cloud classification and operator learning, single-stage rr-ary Janossy pooling may be insufficient when target functions require multistage information interactions. In such settings, attention-based Transformer architectures are preferable, as stacking attention blocks enables repeated global information aggregation and adaptive feature extraction, thereby enhancing expressivity and potentially improving performance.

We hope our responses address the reviewer’s questions and concerns. We would be happy to provide further clarification if needed. Thank you for your time and constructive feedback.

We would like to briefly follow up on our previous responses and the updated manuscript. We would greatly appreciate your feedback on whether our clarifications have addressed your concerns, and we would be glad to provide further explanations if needed. Thank you for your time and consideration.

Reviewer_x1ghOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the expressivity of DeepSets (r-ary Janossy Pooling layers) and linear transformers form a functional perspective. Two main results are presented: The first is that both linear transformers and DeepSets layers satisfy the UAP for statistical functionals, whereas the second is that there exists functions that linear transformers can approximate in latent dimensions M=1 where DeepSets require M exponential in input dimension d to approximate.

However, they do not show the converse: That for any functional that DeepSets can approximate in latent dimension M, linear transformers can do in f(M).

Critical strengths

The paper is admirably clear in that general properties such as UAP hides significant practical concerns (such as bounds on latent dimensions, parameters, et.c.). It is also well written, relatively easy to follow, and seems well motivated in relevant litterature (although I'm not very familiar with it).

Critical weaknesses

The main weakness is the architectural separation, and its consequences. The linear transformers considered here can be viewed as a staged DeepSets-style architecture that first aggregates global information, uses that information to transform original tokens, and then aggregates again. The final pooled dimension M does not really describe the same information bottleneck as the single pooled dimension in DeepSets. As such it is unclear how much of the advantage is specific to attention, or a consequence of an implicit redefinition of latent dimension M. The paper does highlight that the advantage of Linear Transformers comes from this, but I do not believe it adequately addresses the

Questions for authors

The final pooled dimension M does not really describe the same information bottleneck as the single pooled dimension in DeepSets: Could you give a motivation, (e.g. in terms of computational complexity) that motivates treating M for DeepSets and Linear Transformers as comparable ,,, things?

2 comments

We thank the reviewer for recognizing the clarity of our work and raising concerns about the architectural comparison and converse result. We address these points below, with all corresponding revisions highlighted in blue.

[Weakness in the summary] Lack of converse theorem for DeepSets.

We establish the converse embedding for DeepSets in Theorem 3.7 as GM(1)⊂TMd\mathcal{G}_M^{(1)} \subset \mathcal{T}_M^{d}. Specifically, any functional represented by DeepSets can be exactly realized by a shallow dd-head linear Transformer, using the same feature map and readout, without increasing the latent dimension MM. The detailed proof is provided in Appendix B.3.

[W1 & Q1] Rationale for Comparing Latent Dimensions.

We thank the reviewer for raising this important concern. We clarify the rationale for using MM as a comparison metric and further discuss the implications of our results.

  • The dimension of the pooled representation MM is a commonly studied architectural quantity in permutation-invariant models, including Deep Sets [Zaheer et al., 2017], Relation Networks [Santoro et al., 2017], and Set Transformer [Lee et al., 2019]. In both architectures, MM represents the number of extracted features passed to the final readout. Comparing the latent dimensions required by different architectures to achieve universal approximation provides a quantitative of expressivity: a smaller required MM indicates a more efficient architecture. We have clarified this motivation in the Introduction.
  • Our separation also admits a computational interpretation. For the hard functional, choosing AQ=AK=AV=Id\mathcal{A}_Q = \mathcal{A}_K = \mathcal{A}_V = \mathbf{I}_d makes each attention interaction of ⟨x,y⟩y\langle \boldsymbol{x}, \boldsymbol{y}\rangle \boldsymbol{y}, requiring O(d)O(d) operations. Moreover, both φ1\varphi_1 and φ2\varphi_2 are two-layer ReLU networks with hidden width 22 and input/output dimensions at most dd, whose evaluation costs O(d)O(d). Therefore, the overall computational complexity of the linear Transformer is O(d)O(d). In contrast, our lower bound shows that DeepSet requires M=2Ω(d)M=2^{\Omega(d)} features to achieve accurate approximation. Explicitly computing this MM feature representation incurs at least 2Ω(d)2^{\Omega(d)} operations. Hence, our separation results on latent-dimension lso implies an exponential separation in the computational complexity of these architectures.
  • As for the implications of our results, we reveal an expressivity bottleneck of rr-ary Janossy pooling networks: single-stage pooling cannot efficiently capture the features of functionals requiring multi-stage information aggregation, leading to an exponential increase in the required latent dimension. We highlight that the advantage of linear Transformers stems from the additional aggregation stage introduced by attention, as the resulting two-stage information aggregation enables more effective and accurate feature extraction. Moreover, the adaptive weighting of tokens based on their correlations induced by attention may provide additional advantages, which we leave for future investigation (Section 6).

References

  • M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola. Deep Sets. Advances in Neural Information Processing Systems, 30:3391–3401, 2017.

  • A. Santoro, D. Raposo, D. G. T. Barrett, M. Malinowski, R. Pascanu, P. Battaglia, and T. Lillicrap. A simple neural network module for relational reasoning. Advances in Neural Information Processing Systems, 30:4967–4976, 2017.

  • J. Lee, Y. Lee, J. Kim, A. Kosiorek, S. Choi, and Y. W. Teh. Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks. Proceedings of the 36th International Conference on Machine Learning, 97:3744–3753, 2019.

We hope our responses address the reviewer’s questions and concerns. We would be happy to provide further clarification if needed. Thank you for your time and constructive feedback.

We hope our rebuttal and the revisions to the manuscript have helped address your concerns. With the discussion period nearing its end, we would appreciate any additional comments or questions you may have. Thank you very much for your time and valuable feedback.

Reviewer_P2rDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies permutation-invariant architectures through the approximation of continuous statistical functionals. The paper first shows that both rr-ary Janossy pooling networks (including DeepSets) and one-layer linear Transformers are universal approximators for such functionals. Despite this shared universality, the paper establishes an exponential separation: there is a hard functional that a linear Transformer represents exactly with latent dimension M=1M = 1, while Janossy pooling networks require a latent dimension exponential in the input dimension dd to approximate it. The lower bounds hold for arbitrary continuous feature maps and readouts. The separation stems from attention enabling input-distribution-dependent features, whereas Janossy pooling uses fixed feature maps.

Critical strengths
  1. This is solid theoretical work with complete and rigorous proofs; the proof sketches in Section 4 are well structured and the appendix is detailed.
  2. The result is somewhat surprising: since permutation-invariant structures are universal approximators of continuous functionals. The result is clearly non-trivial in high dimensions (d>1d > 1).
  3. The lower bound on the embedding (latent) dimension is also non-trivial: it holds for arbitrary continuous feature maps and readouts, regardless of depth or width, which isolates the pooling mechanism itself as the bottleneck. This also resolves (in the distributional-input setting) the open question of Zweig & Bruna (2022) under real-valued continuity, in contrast to the negative answer of Wang et al. (2024) for fixed-length sequences.
Critical weaknesses

Overall, the presentation of this work is hard to follow. As this is not the major weakness, I am happy to raise my score if the authors can nicely address my concerns and questions in the rebuttal process.

  • It would be better to introduce the meaning of the embedding (latent) dimension MM and the notation N,dN, d in the introduction, so that readers can understand the contribution before reaching Section 3.
  • This paper considers approximating statistical functionals of probability measures. As a functional is an abstract concept, it would be better to define it, or give intuition and concrete examples (e.g., moments, or the mean-alignment functional used as the hard instance), before the main results. By the way, can the universal approximation results cover general continuous functions/mappings beyond functionals of measures?
  • There is a line of work on universal approximation properties of DeepSets and Janossy pooling. Some of them characterize the embedding dimension for approximating permutation-invariant functions on fixed-length sequences, while this paper considers continuous functionals of measures. The exponential-in-dd lower bound here is much larger than their polynomial/linear upper bounds for the sequence setting. A table summarizing these related works would greatly help readers position the contribution: for example, with columns for network structure, target function class (sequences vs. measures), norm, embedding dimension bound, and dependence on dd and NN. Clarifying why the two settings lead to such different answers (as touched on in Remark 3.9) would also strengthen the paper.
  • There are also many existing works on universal approximation of Janossy pooling and Transformers. What are the technical challenges and genuinely new results in your UAP results (Propositions 3.1 and 3.2) compared to these? In particular, Proposition 3.1 appears to follow directly from Pevny & Kovarik (2019) via the inclusion G(1)⊆G(r)\mathcal{G}^{(1)} \subseteq \mathcal{G}^{(r)}.
Questions for authors
  1. Can the UAP results be extended beyond functionals of probability measures, e.g., to general continuous mappings on other compact metric spaces, or to measure-to-measure maps?
  2. Could you provide a comparison table of related work as described above (architecture, target class, norm, embedding-dimension bounds, dependence on dd and NN)?
  3. Can you explain intuitively why the lower bound is exponential in dd for statistical functionals, whereas poly(N,d)\mathrm{poly}(N, d) suffices for permutation-invariant functions on fixed-length sequences (Wang et al., 2024)? Where exactly does the fixed-length-sequence argument break down in the infinite-NN / measure setting?
  4. What is new in your UAP proofs relative to prior universality results for Janossy pooling and (deep) Transformers? Is the main novelty the injectivity of the attention-induced transformation (Lemma A.3) for shallow linear Transformers?
  5. The lower bound for r≥2r \ge 2 is only in the uniform norm (as acknowledged in the Limitations). Is there a fundamental obstruction to obtaining an L2L^2 version, or is it mainly technical?
5 comments

We thank the reviewer for recognizing the rigor and significance of our results, and for the constructive comments on presentation clarity and technical aspects. We address the raised weaknesses and questions point by point below, with all corresponding revisions highlighted in blue in the revised manuscript. Due to the character limit, we have divided our response into four parts. We first address W1, W2, and Q1 below.

[W1] Clarification of notation

To improve readability, we have clarified the meanings of the latent dimension MM, sequence length NN, and token dimension dd in the Introduction when introducing permutation-invariant functions.

[W2 & Q1] Extension of UAPs

To improve accessibility for a broader ML audience, we now briefly define a statistical functional as a mapping from an input probability measure to a real number, with the expectation ∫xdρ(x)\int \boldsymbol{x} \mathrm{d} \rho(\boldsymbol{x}) as a canonical example in the introduction. We also explain its motivation for modeling permutation-invariant functions on variable-length sequences x^=[x1,⋯ ,xN]\widehat{\boldsymbol{x}}=[\boldsymbol{x} _ 1, \cdots, \boldsymbol{x} _ N] through their empirical measures ρ^X=N−1∑i=1Nδxi\widehat{\rho} _ X=N^{-1} \sum_{i=1}^N \delta_{\boldsymbol{x} _ i}.

Regarding extensions, the key ingredient in our UAP proof is the injectivity of the attention-induced transformation established in Lemma A.3. The same UAP argument applies to compact spaces of measures whenever this injectivity property holds. For example, it extends to the space of finite nonnegative Borel measures with bounded total mass, M+,C(X):=μ≥0:μ is a Borel measure on X,μ(X)≤C\mathcal{M} _ {+,C}(\mathcal X):=\\{ \mu \geq 0:\mu \text{ is a Borel measure on } \mathcal{X}, \mu(\mathcal{X}) \leq C\\}. However, injectivity need not hold for arbitrary measure spaces. For instance, consider finite signed measures on Sd−1\mathbb{S}^{d-1} and let μ=δe1−δ−e1≠0\mu=\delta _ {\boldsymbol{e} _ 1}-\delta _ {-\boldsymbol{e} _ 1} \neq 0, where e1\boldsymbol{e} _ 1 is the first standard basis vector. Then Σμ=∫xx⊤dμ(x)=0\Sigma _ {\mu} = \int \boldsymbol{x} \boldsymbol{x} ^ {\top} \mathrm{d} \mu(\boldsymbol{x})=0, so the transformation \mu \mapsto (\Sigma _ {\mu}) _ {\\#} \mu is not injective. Thus, our current proof does not establish UAP on this signed-measure space.

For general measure-to-measure operators, simple modifications of our linear Transformer architecture, such as removing the outer pooling, are insufficient for UAP. For a Dirac input (a probability measure concentrated at a single point), the resulting operator necessarily produces another Dirac measure. In contrast, the continuous operator F(ρ)=0.5δ−1+0.5δ1\mathcal F(\rho)=0.5 \delta _ {-1}+0.5\delta _ 1 on P([−1,1])\mathcal{P}([-1,1]) maps every Dirac input to a non-Dirac measure. A more expressive measure-valued output mechanism is therefore needed. We have added these discussions to Appendix A.2 of the revised manuscript.

The following is our response to the concern raised in W3 and Q2 regarding the lack of comparison with existing works.

[W3 & Q2] Comparison with existing works.

We have added the following table to summarize existing results on latent-dimension requirements for permutation-invariant architectures, comparing their network structures, target function classes, feature-map/readout assumptions, and latent-dimension bounds.

WorkNetworkTargetFeature maps / readoutsLatent dimension MM
Zweig et al. (2022)DeepSetsSequenceComplex-analytic2Ω(min⁡d,N)2 ^ {\Omega(\min\\{d,\sqrt{N}\\})}
Wang et al. (2024); Tabaghi & Wang (2024)DeepSetsSequenceReal-continuousO(poly⁡(N,d))O(\operatorname{poly}(N,d))
Syed et al. (2026)rr-ary JanossySequenceReal-continuousΩ((d(N−r))1/r)\Omega((d(N-r)) ^ {1/r})
Oursrr-ary JanossyMeasureReal-continuousΩ(4d/dr−1/2)\Omega(4 ^ d/d ^ {r-1/2})

To the best of our knowledge, our work is the first to study the latent-dimension requirements of rr-ary Janossy pooling networks for universal approximation of continuous statistical functionals, showing that the required latent dimension can grow exponentially with the input dimension dd.

As for norm constraints, which are also important for controlling model complexity, existing UAP results for permutation-invariant architectures have primarily focused on the latent dimension MM, without characterizing the required norms of feature maps and readouts. Determining the latent-dimension requirements for achieving UAP under norm constraints on these maps is an interesting and important question, which we leave for future work (see Section 6).

References

  • Zweig et al. (2022). Exponential Separations in Symmetric Neural Networks. NeurIPS.
  • Wang et al. (2024). Polynomial Width is Sufficient for Set Representation with High-Dimensional Features. ICLR.
  • Tabaghi & Wang (2024). Universal Representation of Permutation-Invariant Functions on Vectors and Tensors. ALT.
  • Syed et al. (2026). Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling. arXiv:2605.08377.

The following is our response to W3 and Q3 regarding the intuition behind the exponential lower bounds.

[W3 & Q3] Intuition for the exponential latent-dimension lower bound.

Wang et al. (2024) established that DeepSets achieve UAP for continuous permutation-invariant functions on sequences of any fixed length NN with latent dimension M=poly⁡(N,d)M=\operatorname{poly}(N,d). However, this polynomial dependence no longer suffices in our statistical-functional setting, where an exponential latent dimension M=2Ω(d)M=2^{\Omega(d)} may be necessary. The key distinction is that statistical functionals are defined over the entire probability-measure space P(X)\mathcal{P}(\mathcal{X}), which contains empirical measures of arbitrary finite lengths (Lemma B.1), rather than sequences of a prescribed length. Consequently, features extracted for one fixed length may not remain informative at another, potentially requiring distinct feature representations across lengths and leading to exponential growth in the aggregate latent dimension.

We illustrate this using our hard functional. For N=2N=2, consider ρ^2=12(δx1+δx2)\widehat{\rho} _ {2}=\frac{1}{2}(\delta_{\boldsymbol{x} _ {1}}+\delta_{\boldsymbol{x} _ {2}}). Since both points have unit norm, ⟨xi,mρ^2⟩=1+⟨x1,x2⟩2=∣mρ^2∣22\langle\boldsymbol{x} _ {i},\boldsymbol{m} _ {\widehat{\rho} _ {2}}\rangle=\frac{1+\langle\boldsymbol{x} _ {1},\boldsymbol{x} _ {2}\rangle}{2}=\\|\boldsymbol{m} _ {\widehat{\rho} _ {2}}\\| _ {2} ^ {2} for i=1,2i=1,2. Hence, h(ρ^2)=∣mρ^2∣22h(\widehat{\rho} _ {2})=\\|\boldsymbol{m} _ {\widehat{\rho} _ {2}}\\| _ {2} ^ {2}, which admits an exact DeepSets representation with ϕ1(x)=x\phi _ {1}(\boldsymbol{x})=\boldsymbol{x} and ϕ2(z)=cd,qd(∣z∣22−βd)\phi _ {2}(\boldsymbol{z})=c _ {d,q _ {d}}(\\|\boldsymbol{z}\\| _ {2} ^ {2}-\beta _ {d}), requiring only M=dM=d features.

However, this feature map fails for N=6N=6. Consider the two six-point sets X _ {A}=\left\\{\frac{4}{5}\boldsymbol{e} _ {1}\pm\frac{3}{5}\boldsymbol{e} _ {2},\\ \pm\boldsymbol{e} _ {2},\\ -\frac{1}{5}\boldsymbol{e} _ {1}\pm\frac{2\sqrt{6}}{5}\boldsymbol{e} _ {2}\right\\} and X _ {B}=\left\\{\frac{3}{5}\boldsymbol{e} _ {1}\pm\frac{4}{5}\boldsymbol{e} _ {2},\\ \frac{2}{5}\boldsymbol{e} _ {1}\pm\frac{\sqrt{21}}{5}\boldsymbol{e} _ {2},\\ -\frac{2}{5}\boldsymbol{e} _ {1}\pm\frac{\sqrt{21}}{5}\boldsymbol{e} _ {2}\right\\}, where e1,e2\boldsymbol{e} _ {1},\boldsymbol{e} _ {2} are the first two standard basis vectors, and each ±\pm denotes both choices. Their empirical measures ρ^A,ρ^B∈P6(Sd−1)\widehat{\rho} _ {A},\widehat{\rho} _ {B}\in\mathcal{P} _ {6}(\mathbb{S} ^ {d-1}) satisfy mρ^A=mρ^B=15e1\boldsymbol{m} _ {\widehat{\rho} _ {A}}=\boldsymbol{m} _ {\widehat{\rho} _ {B}}=\frac{1}{5}\boldsymbol{e} _ {1}, but h(ρ^A)=115≠775=h(ρ^B)h(\widehat{\rho} _ {A})=\frac{1}{15}\neq\frac{7}{75}=h(\widehat{\rho} _ {B}). Thus, the same pooled features under ϕ1(x)=x\phi _ {1}(\boldsymbol{x})=\boldsymbol{x} cannot distinguish these measures, regardless of the readout.

This illustrates why features sufficient for one sequence length may fail at another, motivating the need for different feature representations across lengths. We briefly discuss this intuition in Remark 3.9 and provide the detailed construction in Appendix B.1 of the revised manuscript.

Comments on the paper

1 comment
Area_Chair_kknaOpenReview ↗

Reminder: Follow-up Feedback Before Discussion Closes

Dear reviewers,

With the discussion period nearing its end, I would appreciate it if you could review the authors’ responses and revised manuscript and share their follow-up feedback.

Please indicate which concerns have been addressed and which remain, and update your assessment and score where appropriate.

Thank you for your time and contributions to the discussion.

Best, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.