acceptodds
Under review as a conference paper at ICLR 2027

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

Abstract

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement in these settings is size generalization: the ability of a model trained on inputs of one size to generalize reliably to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with the input dimension. Moreover, although extensive work has established when models on sets and graphs can be transferred across input sizes, such transferability results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. Toward this goal, we develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting denote the number of training samples, we show that polynomial source decay, a standard condition in classical learning theory, is insufficient for efficient size generalization: while it yields generalization error and hence polynomial sample complexity for in-domain learning, the error for size generalization decays only as , yielding an exponential separation in sample complexity. Thus, conditions sufficient for polynomial sample complexity in classical learning can require exponentially more samples when generalizing across input sizes. We then identify an exponential source condition under which size generalization achieves error , recovering polynomial sample complexity. All of these guarantees are independent of the input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing the optimality of our results. To our knowledge, 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
size generalization, sample complexity, invariance, symmetry, statistical learning theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_4WXGOpenReview ↗
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
  1. 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.

  2. The use of stable invariant polynomial dimensions is interesting.

Critical weaknesses
  1. My major concern is that he minimax lower bound may conflict with the global transfer assumptions. Section 3 assumes coherent isometric transfers for all d≤Dd\le D, implying fd⋆=T1→df1⋆f_d^\star=T_{1\to d}f_1^\star. Therefore, every globally consistent target admits approximation in the smaller space T1→d(V1,k)T_{1\to d}(V_{1,k}), whose dimension is only O(kr)O(k^r), with approximation error at most B(k)B(k). However, Appendix E constructs an Assouad hypercube with mk≳qX(k)m_k\gtrsim q_X(k) orthogonal directions at a large training size dkd_k. The construction only addresses compatibility with larger sizes, without showing that these perturbations can arise from size 11 while satisfying the uniform source condition. In fact, projecting the hypercube onto T1→dk(V1,K)T_{1\to d_k}(V_{1,K}) gives the necessary condition $B(K)\ge u^2\bigl(m_k\dim(V_{1,K})\bigr). $ Taking K=k2K=k^2 and mku2≍B(k)m_ku^2\asymp B(k) appears to contradict polynomial source decay, since qX(k)q_X(k) grows superpolynomially while dim⁡(V1,K)\dim(V_{1,K}) grows only polynomially.

  2. 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
  1. Why can an estimator not restrict itself to T1→d(V1,k)T_{1\to d}(V_{1,k})?

  2. In Appendix E, the lower bound uses qX(k)q_X(k) independent directions at a large training size. It is unclear whether these directions can all arise from globally consistent target families transferred from size 11. Could the authors clarify this point?

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

This paper studies sample complexity in size-generalization setting as compared to classical in-domain setting. They measure the target regularity with the best approximation error of the target function with k-th degree invariant polynomials. When this quantity decays polynomially with kk (polynomial source decay), size-generalization has slowly-decaying generalization error of (log⁡n)−Θ(1)(\log n)^{-\Theta(1)} as compared to the the error of n−Θ(1)n^{-\Theta(1)} in the in-domain learning setting. They also identify a stronger setting of exponential source dacay, where this quantity decays exponentially with kk, so that size generalization can have rate n−Θ(1)n^{-\Theta(1)}. Minimax lower bound is also established to show the result is tight.

Critical strengths
  • The paper is well-presented with the theoretical results rigorously stated.
  • The intuitive explanation is provided regarding why such distinction between size generalization and in-domain learning arises. This provides useful insights for understanding the difficulty of size generalization.
  • The lower bound match up with the upper bound to give a coherent theoretical story.
Critical weaknesses

It seems that the assumptions made by the paper (e.g Theorem 4.1) are very strong, which make the practical applicability of the results questionable. I am worried that the claim of the paper that the error rate is independent of dd strongly depends on these assumptions which do not hold in general.

  1. I'm particularly concerned with the "exact isometric transfer" assumption. The authors seem to claim in Appendix C that deepsets and GNNs satisfy these assumptions, but I'm not convinced. For example, for the set case in appendix C.1. The paper consider deepset model in the "shared deep sets rules" and "replication and empirical measures" part, but seems to switch to a different model in the "stable feature expansions" to show isometry of Td→DT_{d\to D}. I believe isometry of Td→DT_{d\to D} does not hold for deepset fd(X)=F(1d∑ϕ(xi))f_{d}(X)= F(\frac{1}{d}\sum \phi(x_i)). e.g. when F=id,ϕ=idF=id, \phi=id, we have ∥1d∑ixi∥L2(λd)2=1d2∑i,jE[xixj]=1/d\|\frac1d\sum_ix_i\|^2_{L^2(\lambda_d)}=\frac{1}{d^2}\sum_{i,j}\mathbb{E}[x_ix_j]=1/d, so ∥fd∥2=1d,∥Td→Dfd∥2=1/D\|f_{d}\|^{2}=\frac{1}{d},\|T_{d\to D} f_{d}\|^2=1/D. In general, I think this exactly leads to size generalization error to depend on dd, but the paper claim to avoid the dd-dependence by strong, infeasible assumptions. The graph case in appendix C.2 seem to also have the same problem.
  2. for neural networks that apply to different sizes by parameter sharing, the operator Td→DT_{d\to D} is not well-defined on function space. It is hence not well-defined as stated. The size-d function alone does not determine its parameter-reused realization at size D>dD>d.
  3. Moreover for such Td→DT_{d\to D}, I'm not convinced that Td→D(Fd,k)⊆FD,kT_{d\to D}(\mathcal F_{d,k})\subseteq\mathcal F_{D,k} is satisfied
  4. the assumption that constants α,σ\alpha,\sigma independent of both dd and kk is also very strong and not justified.
Questions for authors

Can you provide a nontrivial practical example (with practical neural network and data distribution) satisfying all these assumptions simultaneously?

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

For the problem of size generalization on sets and graphs, error bounds with no dependency on dd and DD are derived under exact isometric transfer, representation stability, and source decay in invariant polynomial coordinates, together with corresponding minimax lower bounds based on Assouad's method. The central claim is that size generalization admits only logarithmic rates under polynomial source decay, whereas sufficiently fast exponential source decay restores nearly parametric rates. The authors interpret this as an exponential separation in sample complexity between classical in-domain learning and size generalization.

Critical strengths
  1. The problem is important and clearly motivated. Representation stability explains why object size can be removed from the rates, while the rapid growth of stable invariant interactions explains why the convergence may nevertheless be slow.

  2. The set threshold β=r/(r+1)\beta=r/(r+1) and the graph threshold 11 arise from different asymptotics of the stable invariant-feature counts, leading to a clear phase-transition picture. This makes the comparison between sets and graphs theoretically attractive.

  3. The main text, appendices, notation table, and experiments are connected clearly. The paper also attempts to cover squared-loss regression, density estimation, and equivariant field estimation within a unified framework.

Critical weaknesses
  1. The framework assumes both exact target transfer, norm preservation and isometry, so taking the supremum over all D≥dD\ge d introduces essentially no additional statistical difficulty, and no union bound over DD is needed. Although this assumption makes the analysis elegant, it also removes much of the cross-size mismatch that one might expect to be central to size generalization. The practical scope of the resulting theory therefore needs to be stated much more carefully. More importantly, the shared rules used by standard Deep Sets and GNNs do not automatically satisfy isometry in the task L2L^2 norms. Hence, a mean-pooled Deep Sets rule may satisfy semantic weight sharing and even exact target compatibility without satisfying the isometry assumption. Similar issues may arise for normalized motif functionals and GNN readouts whose sampling variability changes with the number of nodes.

  2. In Appendix E.1, for every interaction order kk, the lower-bound construction selects a training size in the stable range. Meanwhile, the optimizing interaction order knk_n in Appendix D grows with nn. Hence, the training size dknd_{k_n} used by the lower bound construction may also change with nn. Furthermore, the lower bound in Appendix E.4 already holds at D=dkD=d_k. The paper explicitly observes that the size-generalization loss contains the choice D=dkD=d_k, so its supremum is at least the corresponding in-domain loss at the training size. The construction therefore appears to establish a lower bound for a sequence of stable-size, in-domain estimation problems, without requiring evaluation at a strictly larger target size. By contrast, the in-domain sample complexity in Corollary 4.3 is stated at fixed dd. This creates a potential mismatch between the two sides of the claimed separation, i.e., the in-domain benchmark uses a fixed training size dd, but the size-generalization lower bound allows the construction to select dkd_k, with kk and hence dkd_k potentially depending on nn, and the lower bound does not intrinsically rely on any D>dD>d. As written, the proof seems to establish slow rates for the particular minimax risk containing sup⁡d≥1\sup_{d\ge1}, but it does not fully rule out faster size-generalization rates at every fixed training size. Nor does it completely isolate the requirement D>dD>d as the cause of the exponential separation.

  3. Theorem 4.1 provides high-probability guarantees of the form:

Pr⁡(sup⁡D≥d∣f^D−fD⋆∣D2≲R0)≥1−δ,\Pr \left( \sup_{D\ge d}\\|\widehat f_D-f_D^\star\\|_D^2 \lesssim R^0 \right) \ge 1-\delta,

R0:=Rn,k,δ.R^0:=R_{n,k,\delta}.

However, Appendix E.1 defines minimax risk using an expectation:

Rn(X,B)=inf⁡f^sup⁡d,f⋆E[sup⁡D≥d∣f^D−fD⋆∣D2].\mathfrak R_n(\mathcal X,B)=\inf_{\widehat f}\sup_{d,f^\star}\mathbb E \left[\sup_{D\ge d}\\|\widehat f_D-f_D^\star\\|_D^2\right].

A high-probability upper bound together with an expected-risk lower bound is not sufficient to establish minimax optimality in this expected-risk sense. On the failure event of probability δ\delta, the squared error may be uncontrolled and may dominate the expectation. Hence, the claim in Theorem 4.2 that every rate in Theorem 4.1 is minimax optimal currently lacks a matching upper bound for the same risk functional.

Questions for authors

Please refer to the Weaknesses for details.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.