acceptodds
Under review as a conference paper at ICLR 2027

Learning Wasserstein-Stable Permutation-Invariant Functions: -Independent Latent Dimension and Sample Complexity

Abstract

Learning permutation-invariant functions over sets is fundamental to many applications, including point-cloud analysis, multi-instance learning, and data-driven stochastic optimization. DeepSets provide a standard architecture for this task by applying a shared encoder to individual elements and aggregating their representations. However, whether increasing the set size necessarily increases the complexity of either representation or learning remains open. Existing latent-dimension bounds scale from for exact multiset representation to for Wasserstein-stable approximation, while the dependence of the required number of training samples on remains open. In this paper, we show that both the latent dimension and the sample complexity can be made independent of for Wasserstein-stable permutation-invariant functions. We first develop a Soft-Histogram Encoder and prove an -independent latent-dimension bound for continuous DeepSets approximation. We then establish an -independent sample-complexity bound for learning such functions from i.i.d. training sets. To improve data efficiency under limited labeling budgets arising from expensive target evaluations, we further develop permutation-aware maximin sampling (PAMS), which selects training sets to maximize their separation under optimal permutation matching. Numerical experiments on resource-allocation problems validate the predicted -independent scaling of both the critical latent dimension and the number of training sets required to reach a fixed prediction accuracy, and show that PAMS achieves lower prediction error than random sampling under the same labeling budget. Together, these results establish that Wasserstein stability enables cardinality-independent representation and learning, while providing a practical route toward data-efficient permutation-invariant learning.

Primary area:
learning theory
Keywords:
Permutation-invariant functions, latent dimension, DeepSets

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_QcKoOpenReview ↗
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
AuthorsOpenReview ↗

Response to Reviewer QcKo

Dear Reviewer QcKo,

Thank you for your constructive and insightful feedback. Below, we respond to each point in detail.

C1. "Novelty: The relationship to existing approximation results on probability measures is not sufficiently developed ..."

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 NN.

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,m\leq\left\lceil\frac{3\sqrt{D}L_F}{\tau}\right\rceil^{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 NN.

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.)

C2. "Limited validation: The experiments use a single resource-allocation problem with all input elements sampled from the same uniform distribution ..."

Response. Thank you for this insightful comment. You are correct that drawing all elements from a common distribution causes the targets to concentrate as NN grows. Our additional analysis confirms this effect, although the constant predictor remains about 15 times above the accuracy threshold even at N=1000N=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 NN.

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 NN.

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.)

Q1. "Novelty clarification: How do your results differ from existing universal approximation results on probability measures ..."

Response. Please see our response to C1.

Q2. "Experimental clarification: As set size increases, how much do the target values vary, and how well would simply predicting the training-set mean perform?"

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.

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 NN-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 O(log⁡N)\mathcal{O}(\log N) dependence on set size.

Thank you again for your constructive feedback, which has helped us strengthen the manuscript.

Reviewer_udimOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the representation and sample complexity of permutation-invariant functions under Wasserstein stability. The primary theoretical contribution is to establish an upper bound on the latent dimension required by DeepSets to approximate Wasserstein-stable functions within a prescribed error tolerance. In particular, the authors show that this bound is independent of the set cardinality N, depending instead on the input dimension D, the Wasserstein-Lipschitz constant, and the approximation tolerance. To establish this result, the authors construct a Soft-Histogram Encoder that approximates empirical measures using a fixed number of grid centers, and then exploit Wasserstein stability to bound the resulting function approximation error. The paper further extends this result to learning theory, establishing an N-independent sample-complexity bound through ReLU network approximation and uniform convergence analysis. Additionally, the authors introduce permutation-aware maximin sampling (PAMS) to improve data efficiency under limited labeling budgets. Overall, I find the motivation and theoretical objectives clearly presented. The two main theoretical results follow a coherent progression from measure-theoretic representation to function approximation and finite-sample learning. From my reading, the overall proof framework appears logically consistent and internally well-structured.

Critical strengths
  1. Clear motivation and meaningful theoretical contribution. The paper addresses an important question in permutation-invariant learning: whether the representation dimension and sample complexity must increase with the set cardinality N. The N-independent upper bounds under Wasserstein stability provide a meaningful theoretical perspective on this problem.
  2. Coherent theoretical framework. The theoretical development is logically well-structured. By introducing a measure-theoretic representation and constructing a Soft-Histogram Encoder, the authors establish a connection between Wasserstein stability and function approximation. The sample-complexity analysis further extends the representation result to finite-sample learning.
  3. Connection between theory and practical applications. Beyond the theoretical analysis, the paper introduces permutation-aware maximin sampling (PAMS) to improve data efficiency. The numerical experiments on resource-allocation problems provide preliminary empirical support for the theoretical findings and demonstrate the potential benefits of the proposed sampling strategy.
Critical weaknesses
  1. Limited Discussion of the Applicability of Wasserstein Stability The main theoretical results rely on the assumption that the target functional is Wasserstein-Lipschitz with a constant independent of the set cardinality N. While this assumption is natural for certain distributional functionals, its applicability to broader permutation-invariant learning tasks remains insufficiently discussed. In particular, tasks involving extreme values, rare instances, or highly localized features may not satisfy this condition uniformly as N increases. Although the paper motivates its contributions using applications such as point-cloud analysis and multi-instance learning, it remains unclear under what conditions these applications satisfy the theoretical assumptions. A more detailed discussion of the practical applicability of Wasserstein stability, along with an explicit justification for the resource-allocation objective used in the experiments, would strengthen the significance of the theoretical results.
  2. Limited Experimental Validation and Potential Confounding Effects The experimental evaluation is limited to a resource-allocation problem in which the elements of each input set are independently sampled from the same uniform distribution. However, the theoretical results do not require the elements within each set to be i.i.d. Under the current experimental setting, as N increases, the empirical distributions of different input sets become increasingly concentrated around the same underlying distribution. For Wasserstein-stable target functionals, this may also reduce the variability of the target values, potentially making the prediction task easier as N grows. Consequently, the observed N-independent behavior in Figures 2 and 3 may partly reflect this decreasing target variability rather than providing strong empirical evidence for the general theoretical guarantees. Furthermore, Figure 2 evaluates the critical latent width using training RMSE, whereas Theorem 4.1 establishes a uniform approximation guarantee over the entire input space. Evaluating more diverse set distributions, such as mixtures with set-specific parameters, would provide stronger empirical support.
Questions for authors
  1. Clarification on the D-scaling Experiment Theorem 4.1 establishes an N-independent upper bound on the latent dimension, but this bound exhibits an exponential dependence on the element dimension D. In Figure 2(c), the critical latent width is reported as "Not attained" for the evaluated dimensions D = 8, 16, and 32 within the tested range of m ≤ 2048. However, it remains unclear whether larger latent dimensions are necessary to achieve the target accuracy, or whether the observed failure is caused by other factors, such as limited encoder/decoder capacity or insufficient optimization convergence. In particular, the current results do not clearly distinguish the effect of latent dimension from other architectural and training constraints. Could the authors clarify this distinction? Additional experiments or analyses that isolate the effect of latent dimension from model capacity and optimization would help better understand the practical implications of the theoretical bound, particularly for high-dimensional inputs.
  2. Connection Between the Theoretical Construction and Experimental Models The proof of Theorem 4.1 relies on a constructive Soft-Histogram Encoder that approximates empirical measures using a fixed grid. However, the experiments appear to use standard DeepSets models with learnable ReLU encoders and decoders. Could the authors clarify whether the proposed Soft-Histogram construction is explicitly implemented in the experiments, or whether it is used only for the theoretical existence proof? Additionally, an empirical comparison with the constructive encoder or the prior random-feature approach would help clarify how the theoretical insights translate into practical representation efficiency.
2 comments
AuthorsOpenReview ↗

Response to the Reviewer udim

Dear Reviewer udim,

Thank you for your constructive feedback. Below, we respond to each point in detail.

C1. "Limited ... N increases."

Response. We agree that the applicability of Wasserstein stability deserves a more detailed discussion. Tasks involving extreme values, rare instances, or highly localized features may not satisfy this condition, since a single element can change the target by a fixed amount, whereas Wasserstein stability requires its influence to decay at rate 1/N1/N.

Our results apply when the target depends on the distribution of the set elements as a whole, as in stochastic optimization, risk-aware decision making, and distribution comparison. We have added this discussion in Sec. 3.2.

C2. "Although ... assumptions."

Response. These applications satisfy the assumption when the target depends on the distribution of the elements as a whole. In point-cloud analysis, this holds for shape-level targets that are Lipschitz in the earth mover's distance, which are robust to sensor noise [Ref1, Proposition 3.3], but not for targets determined by a few critical points. In multi-instance learning, it holds when the target is the average of a Lipschitz instance score, but not when a single positive instance determines the label. For stochastic optimization, [Ref1, Proposition 3.2] proves Wasserstein stability of the optimal solution under strong convexity.

[Ref1] M. Zhou et al., O(log⁡N)\mathcal{O}(\log N) latent dimension suffices for universal approximation of permutation-invariant functions, ICML 2026.

C3. "A ... results."

Response. For practical applicability, please see C1 and C2 above. We have added a proof that the resource-allocation objective is Wasserstein-stable with a constant independent of NN (Proposition E.1). By Lagrangian duality, the objective is the minimum over the budget multiplier of a function that depends on the users only through an average of per-user terms. Each term is Lipschitz in the user's features with a constant that depends only on the penalty weight and the element dimension, because the optimal allocation of every user is bounded. The average is therefore Lipschitz in the Wasserstein distance with the same constant for every NN, and so is the minimum.

C4. "Limited ... guarantees."

Response. We agree that sampling all elements from a common distribution reduces the target variability as NN grows. Our tests show that the constant predictor remains 15 times above the accuracy threshold at N=1000N=1000.

We repeated the experiments with heterogeneous input distributions, where each set has its own distribution and the target variability stays constant in NN. DeepSets attains an error over 400 times smaller than the constant predictor, and neither the critical latent width nor the required number of training sets grows with NN, confirming that the observed scaling is not caused by target concentration alone (Appendix H.2).

C5. "Furthermore ... space."

Response. We use the training error because Theorem 4.1 is an approximation result: it characterizes whether a DeepSets model with latent width mm can represent the target. The training error directly measures this capability, namely how accurately such a model can fit the target, and is therefore the empirical counterpart of the approximation error in Theorem 4.1. Figure 3 uses the test error for the sample complexity in Theorem 4.2.

We agree that an average error does not verify a uniform guarantee. Figure 2 examines the implication of Theorem 4.1 that the latent width required for a prescribed RMSE is bounded independently of NN. We have clarified this in Sec. 6.1.

Q1. "Clarification ... inputs."

Response. The "Not attained" results reflect limited training and network size, not an insufficient latent dimension. For D=8D=8 and D=16D=16, m=2m=2 reaches the target accuracy once training is extended from 20,000 to 60,000 updates. For D=32D=32, widths up to m=2048m=2048 fail at hidden width 128, whereas m=128m=128 succeeds at hidden width 512 (Appendix H.3).

While these widths are below the exponential bound in Theorem 4.1, this is consistent with the theorem: its bound is a worst-case sufficient condition, and an individual target may admit a much smaller latent dimension.

Q2. "Connection ... efficiency."

Response. The Soft-Histogram Encoder, like the random-feature encoder of [Ref1], is a proof technique. Theorem 4.1 uses it to show that an NN-independent latent dimension is achievable; other encoders may achieve it as well. By Proposition C.1, ReLU networks can realize this construction. Our experiments therefore train standard DeepSets with ReLU encoder and decoder networks, not the Soft-Histogram Encoder, and test whether the required latent width grows with NN.

[Ref1] M. Zhou et al., O(log⁡N)\mathcal{O}(\log N) latent dimension suffices for universal approximation of permutation-invariant functions, ICML 2026.

Dear Reviewer udim,

Thank you again for taking the time to provide a detailed and constructive review.

As the author discussion period approaches its end, we would appreciate knowing whether our rebuttal and additional experiments have addressed your main concerns.

We would be happy to clarify any remaining questions or concerns before the discussion closes.

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

This paper studies permutation‑invariant set‑learning models for point‑cloud processing and resource allocation. Under the Wasserstein‑Lipschitz stability assumption, it proposes a Soft‑Histogram Encoder and the PAMS sampling algorithm. It constructively proves that both latent dimension and training‑set quantity can be independent of set cardinality N, though latent dimension scales exponentially with element dimension D. Validated on synthetic tasks only, its theory applies exclusively to Wasserstein‑stable functions, and PAMS lacks real‑world‑dataset evaluation. All experiments are conducted on synthetic resource‑allocation tasks. Notably, all theoretical guarantees apply only to Wasserstein‑stable functions, and PAMS has not been evaluated on real‑world datasets.

Critical strengths

The core contribution of this work is a constructive proof showing that under Wasserstein‑Lipschitz stability, both latent dimension and the required number of training sets are independent of set cardinality N. It theoretically validates the practical use of fixed‑width networks for handling variable‑size sets. Besides, this paper puts forward the Soft‑Histogram Encoder to realize the above property. As a secondary practical contribution, it develops the PAMS sampling algorithm to boost model performance under limited labeling budgets.

Critical weaknesses
  1. The theoretical guarantees are only valid for Wasserstein-Lipschitz stable functions, and the latent dimension increases exponentially with element dimension D, suffering from the curse of dimensionality.
  2. Empirical validation is limited to synthetic resource allocation tasks; the proposed PAMS algorithm has not been verified on real-world datasets.
Questions for authors

Please see the above comments.

3 comments
AuthorsOpenReview ↗

Response to Reviewer XDVo

Dear Reviewer XDVo,

Thank you for your constructive and insightful feedback. Below, we respond to each point in detail.

C1. "The theoretical guarantees are only valid for Wasserstein-Lipschitz stable functions."

Response. Thank you for the comment. You are correct that our theoretical guarantees are established for Wasserstein-stable functions.

However, we would like to clarify that this assumption is not merely a mathematical convenience. It arises naturally in settings in which the target depends smoothly on the distribution of the set elements, including stochastic optimization, risk-aware decision making, and distribution comparison. For these tasks, our results provide, to the best of our knowledge, the first explicit NN-independent bound on the latent dimension of DeepSets and the first NN-independent sample-complexity guarantee.

We acknowledge that Wasserstein stability is a key assumption that limits the scope of our results. Extending cardinality-independent guarantees to broader function classes remains an open problem for future work. We have revised the manuscript to state this limitation explicitly.

We appreciate your feedback, which has helped us clarify the scope of our contributions.

(Please refer to Sec. 7 of the revised manuscript.)

C2. "Latent dimension increases exponentially with element dimension D, suffering from the curse of dimensionality."

Response. Thank you for the comment. You are correct that the latent-dimension bound in Theorem 4.1 grows exponentially with the element dimension DD.

We would like to clarify that our main contribution is to remove the dependence of both the latent dimension and the sample complexity on the set cardinality NN. In many practical applications, such as point-cloud processing, NN is very large while the element dimension DD remains small. Our guarantees are designed for this regime.

We acknowledge that the exponential dependence on DD is a limitation of our work. Whether this dependence can be improved remains an open problem, which we leave as important future work. We have revised the manuscript to state this limitation explicitly.

We appreciate your feedback, which has helped us state this limitation more clearly.

(Please refer to Sec. 7 of the revised manuscript.)

C3. "Empirical validation is limited to synthetic resource allocation tasks; the proposed PAMS algorithm has not been verified on real-world datasets."

Response. Thank you for the comment. To address this, we conducted an additional set-regression experiment on real handwritten-digit images from MNIST.

Each input set contains 50 images, and the target is the average digit value. Labels are revealed only for the selected sets. PAMS and random sampling use the same labeling budget, frozen image encoder, DeepSets architecture, and training settings. The table reports the test RMSE on 2,000 test sets (mean ± standard deviation over five selection seeds with two network initializations each).

Labeling budget MMRandomPAMS
320.590 ± 0.1130.469 ± 0.033
640.434 ± 0.0420.405 ± 0.015
1280.368 ± 0.0280.368 ± 0.032
2560.312 ± 0.0400.303 ± 0.012
5120.280 ± 0.0190.262 ± 0.014

PAMS achieves a lower mean RMSE at four of the five budgets and is comparable to random sampling at M=128M=128. The improvement is largest at the smallest budget (20.5%), and PAMS also shows a smaller variation across seeds at most budgets. This experiment indicates that the benefit of PAMS is not restricted to the synthetic resource-allocation task and carries over to real image data.

We have added this experiment to the revised manuscript. We have also added scaling experiments with heterogeneous input distributions, in which each set is drawn from its own distribution.

(Please refer to Appendix H.1 and Appendix H.2 of the revised manuscript.)

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.

Thank you for your response.

Dear Reviewer XDVo,

Thank you for taking the time to consider our response. We sincerely appreciate your constructive feedback, which has helped us improve the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.