- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This work investigates the sample complexity of size generalization for permutation invariant learning on sets and graphs. By employing invariant polynomial representations with representation stability, we characterize how the number of invariant features grows with the degree. By combining these counts with polynomial or exponential source conditions, It derives learning rates independent with dimension. This work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.
Critical strengths
-
The theoretical question is important. Understanding whether statistical learning guarantees can be independent of input size is an interesting question, especially for sets and graphs.
-
The use of stable invariant polynomial dimensions is interesting.
Critical weaknesses
-
My major concern is that he minimax lower bound may conflict with the global transfer assumptions. Section 3 assumes coherent isometric transfers for all , implying . Therefore, every globally consistent target admits approximation in the smaller space , whose dimension is only , with approximation error at most . However, Appendix E constructs an Assouad hypercube with orthogonal directions at a large training size . The construction only addresses compatibility with larger sizes, without showing that these perturbations can arise from size while satisfying the uniform source condition. In fact, projecting the hypercube onto gives the necessary condition $B(K)\ge u^2\bigl(m_k\dim(V_{1,K})\bigr). $ Taking and appears to contradict polynomial source decay, since grows superpolynomially while grows only polynomially.
-
Under the assumption of isometric transfer, Appendix D demonstrates that estimation errors are fully preserved across different scales. Consequently, transferring a learned model to a larger scale introduces no additional error. However, the claimed exponential divergence appears to stem from comparing a fixed training scale against worst-case guarantees that account for all possible training scales. This gap undermines the practicality of this paper.
Questions for authors
-
Why can an estimator not restrict itself to ?
-
In Appendix E, the lower bound uses independent directions at a large training size. It is unclear whether these directions can all arise from globally consistent target families transferred from size . Could the authors clarify this point?