- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies whether learning a function of an unordered set becomes harder as the number of elements N increases. The work considers Wasserstein-stable functions, meaning small changes in the input distribution produce small changes in the output, with a sensitivity bound independent of N. Under this assumption, it shows that both the representation width and a sufficient number of labeled training sets can be bounded independently of set size.
The proof constructs a soft-histogram encoder. Each input point distributes its weight among nearby centers on a fixed grid, and averaging these weights produces a fixed-length representation of the entire set. The grid resolution controls the Wasserstein approximation error, which in turn controls the output error through the stability assumption. The same encoder and decoder work for all set sizes, with an explicit width bound depending on input dimension, stability, and desired accuracy.
The authors then extend this construction to ReLU networks and derive a cardinality-independent sample-complexity guarantee using covering-number and uniform-convergence arguments. They also propose permutation-aware maximin sampling, which selects well-separated training sets using optimal-matching distance. Experiments on a synthetic resource-allocation problem illustrate the scaling results and show that this selection strategy generally improves over random sampling.
Critical strengths
-
Cardinality-independent approximation: The paper constructs a soft-histogram representation whose width depends on input dimension, Wasserstein stability, and desired accuracy, with the same encoder–decoder pair working for every set cardinality. This provides a clear quantitative explanation of when fixed-width representations are sufficient and is the strongest theoretical contribution supporting acceptance.
-
Cardinality-independent learning: The paper extends the approximation result to show that a sufficient number of labeled training sets can also be bounded independently of cardinality. By showing that mean pooling does not amplify encoder approximation errors and combining this with covering-number arguments, it connects representational sufficiency to a finite-sample learning guarantee. This broadens the main theorem's significance beyond expressivity alone.
Critical weaknesses
-
Novelty: The relationship to existing approximation results on probability measures is not sufficiently developed. These results appear to imply qualitative cardinality independence, so the paper needs to distinguish more clearly what its explicit width bound and learning analysis add. This uncertainty makes it harder to assess the theoretical advance.
-
Limited validation: The experiments use a single resource-allocation problem with all input elements sampled from the same uniform distribution. As set size increases, the empirical distributions concentrate, potentially making prediction easier. Without a constant-prediction baseline or experiments with varying underlying distributions, the observed scaling provides limited evidence for the theory's broader significance.
Questions for authors
-
Novelty clarification: How do your results differ from existing universal approximation results on probability measures, particularly Pevny and Kovarik (2019)? Is the main advance the explicit accuracy-dependent width bound, or does cardinality independence itself require an additional argument?
-
Experimental clarification: As set size increases, how much do the target values vary, and how well would simply predicting the training-set mean perform? This would clarify whether the observed scaling reflects the model’s learning ability or whether inputs become more similar as larger sets are sampled from the same distribution.
3 comments
Thank you for the detailed rebuttal and revisions. The additional experiments with heterogeneous distributions and the constant-prediction baseline convincingly address my concerns about the experiments. I also appreciate the clearer positioning relative to previous approximation results.
My remaining reservation concerns novelty. While the explicit quantitative bounds and sample-complexity analysis are useful contributions, the underlying cardinality-independence result was already implied by prior work, and the theoretical techniques are largely established.
Overall, the paper has improved, but I will maintain my rating of Weak Accept.
Dear Reviewer QcKo,
Thank you for your thoughtful follow-up. We appreciate your recognition of the additional experimental evidence and the clearer positioning of our contributions.
We will further revise the manuscript to distinguish existing qualitative approximation results from our quantitative guarantees: an explicit latent-dimension bound obtained through a constructive, target-independent encoder, and an -independent sample-complexity guarantee under Wasserstein stability. To the best of our knowledge, both results are new for this function class, and the previous explicit bound considered in our comparison retains an dependence on set size.
Thank you again for your constructive feedback, which has helped us strengthen the manuscript.
Response to Reviewer QcKo
Dear Reviewer QcKo,
Thank you for your constructive and insightful feedback. Below, we respond to each point in detail.
Response. Thank you for pointing out this important connection, which our submission did not discuss. You are correct that the universal approximation result of Pevný and Kovařík (2019) already implies qualitative cardinality independence. Their theorem establishes that neural networks with mean aggregation are dense in the space of continuous functionals on a compact space of probability measures. Since this space contains the empirical measures of sets of every cardinality, a single finite-dimensional representation can approximate a given continuous functional uniformly for all N.
However, we would like to clarify that our contribution is to establish quantitative cardinality-independent guarantees for Wasserstein-stable functions, which the existing qualitative result does not provide.
First, Theorem 4.1 gives an explicit sufficient latent dimension,
m≤⌈τ3DLF⌉D,
which depends only on the element dimension, the Wasserstein-Lipschitz constant, and the target accuracy. This bound holds uniformly over the function class, and it is attained by a constructive Soft-Histogram Encoder that does not depend on the target.
Second, Theorem 4.2 extends this representation guarantee to learning, and establishes a sample-complexity bound that is independent of N.
We remark that neither guarantee follows from the universal approximation theorem of Pevný and Kovařík (2019). We have revised the manuscript to discuss this work and to clarify that our novelty lies in the explicit latent-dimension bound and the learning guarantee, rather than in qualitative cardinality independence.
We appreciate your feedback, which has helped us position our contributions more precisely.
(Please refer to Sec. 1 and Sec. 2 of the revised manuscript for details.)
Response. Thank you for this insightful comment. You are correct that drawing all elements from a common distribution causes the targets to concentrate as N grows. Our additional analysis confirms this effect, although the constant predictor remains about 15 times above the accuracy threshold even at N=1000.
To separate the predicted scaling from this effect, we repeated the experiments with heterogeneous input distributions, in which each set is drawn from its own distribution. In this setting, the target variability no longer decreases with N.
The predicted scaling persists. DeepSets attains an error more than 400 times smaller than that of the constant predictor, and neither the critical latent width nor the number of training sets required to reach the target accuracy grows with N.
These results indicate that the cardinality-independent behavior cannot be attributed to target concentration alone. We have added these experiments to the revised manuscript.
(Please refer to Appendix H.2 of the revised manuscript for details.)
Response. Please see our response to
C1.Response. Please see our response to
C2.We hope these responses address your concerns. If any part of the presentation or the technical content remains unclear, we would be glad to clarify further.