尺寸泛化的维度无关标度律：一个指数分离

🧒 初中生也能看懂的版本

① 研究背景（为什么要做？）

你有没有想过，一个用来处理集合或图的智能模型，能不能在长大以后还照样管用。比如一个模型只在十个点的小集合上训练过，等到测试时给它上千个点的大集合，它还能不能算对。这类问题叫做尺寸泛化，它和普通的泛化不太一样。普通的泛化说的是，在同一类大小的样本里，没见过的那些能不能算对；而尺寸泛化要求模型换到另一种、往往大得多的尺寸上依然准确。集合里元素的个数会变，图里节点的个数会变，现实里的很多任务都是这样，这就让尺寸泛化成了几何机器学习里一个绕不开的难题。

② 研究问题（要回答什么？）

这篇论文想问一个很朴素、却一直没人讲清楚的问题，模型跨尺寸学习，到底要多少样本才够用。经典的学习理论大多假设输入的大小是固定的，它的结论往往还会随着输入尺寸变大而变得更差，所以没法回答跨尺寸的问题。过去已经有人证明，某些模型确实能把在一种尺寸上学到的规律传到另一种尺寸上，可是这些工作只说了能不能传，没有说传过去以后误差下降得有多快，也没有说和原来那个尺寸上自己学相比，代价是大还是小。作者于是把问题收紧成一句话，如果训练数据都来自某一个尺寸，那么到底要用多少样本，才能保证模型在所有更大的尺寸上同时都够准。

③ 研究方法（怎么做的？）

作者的思路是把尺寸当成一个可以一路变过去的坐标，先用一组叫做置换不变多项式的积木，把模型能表达的东西一层一层搭起来。最底下是最简单的一阶特征，比如集合里元素的平均值；再往上一层是两两之间的关联；越往上就是越复杂的多元素互动。关键在于，同一块积木在不同尺寸下含义是一样的，所以在一张小图上量出来的坐标，可以直接搬到大图上去用，作者把这种搬运叫做精确传递。接着，作者再用一个叫表示稳定性的工具，去数每一种复杂度的积木到底有多少块，也就是随复杂度增长的特征数量。最后，把积木的增长速度和目标函数里高频成分的衰减速度放在一起比，就能推出误差随样本数变化的公式，并且给出一个下界，证明这个速度不可能再快。

④ 结果（发现了什么？）

结果揭示了两种完全不同的命运，取决于目标函数有多光滑。如果目标函数的衰减是多项式型的，也就是越来越弱的关联按照幂次慢慢衰减，那么在自己那个尺寸上学习时，误差差不多按样本数的某个幂次下降，这是大家熟悉的正常速度，样本越多、误差掉得越快。可一旦要求同一个模型在所有更大的尺寸上都准，误差却只能按对数的幂次下降，而对数增长得极慢，这就意味着要让误差小一点点，样本数就得涨成指数级。作者把这两者之间的巨大落差叫做指数分离，换句话说，同一类目标在自己尺寸上只要多项式多的样本，跨到别的尺寸却要指数多的样本。反过来，如果目标函数衰减得足够快，是所谓的指数型衰减，跨尺寸的误差就能重新回到按幂次下降，重新接近最优的速度。

⑤ 讨论（这些发现说明什么？）

作者认为，这个结果最要紧的地方，在于把三件常被混为一谈的事情分开了。第一件，一个架构能不能处理不同尺寸，这只是它长得够通用；第二件，一个固定下来的预测器在尺寸变化时输出稳不稳，这叫做可迁移；第三件，从有限的样本里学出来的预测器，误差会不会随着样本变多而真的下降，这才是统计学意义上的尺寸泛化。前两件让跨尺寸预测成为可能，但都不决定学习效率。作者强调，指数分离不是某个算法没设计好，而是整类问题本身的统计下界，换个架构、换个正则化、换个优化器都绕不过去。想要更快，只能额外假设目标更光滑，或者把可迁移的互动种类缩小。

⑥ 结论（最终结论 + 启示）

一句话，尺寸泛化的难度并不取决于模型能不能迁移，而取决于目标函数的正则性够不够强，也就是高频成分衰减得够不够快。在多项式衰减下，同一类目标在自己尺寸上学习只要多项式多的样本，要跨到别的尺寸却要指数多的样本；只有衰减快到指数型，跨尺寸才会重新变得高效。作者还给出了一整套完整的上下界，证明这个速度差距是问题本身的固有属性，不是估计方法或者分析技巧造成的。这个结论第一次给出了尺寸泛化在最小最大意义下的完整刻画，也告诉后来的人，想在大尺寸上做得好，光换模型没用，得从目标函数的规律性入手。

🎓 专业 IRMaD 结构解读

I. Introduction（引言）

集合与图这类尺寸可变的结构化数据在几何机器学习中越来越普遍，模型在一种尺寸上训练、在远更大尺寸上部署已成常态，由此衍生出 size generalization（尺寸泛化）问题。既有工作沿两条线索展开：一条经由图极限、graphon 与稳定性框架刻画跨尺寸的可迁移性（Ruiz et al., 2020；Keriven et al., 2020；Levie et al., 2021；Levin et al., 2025），另一条借助表示稳定性（representation stability, Farb 2014）设计任意维度的学习规则（Levin & Díaz, 2024；Díaz et al., 2025）。这些结果给出了结构性洞见，却留下一个未被回答的维度无关极小最大问题：跨尺寸学习的样本复杂度究竟是多少，它与经典的域内学习又相差多少。本文填补这一空白，证明了一个尖锐的指数分离，并给出匹配的极小最大下界，从而首次建立尺寸泛化的维度无关极小最大理论。与最接近的工作 Levin et al. (2025) 相比，后者的传递与泛化率依赖域上的覆盖数等维度相关复杂度度量，而本文识别出让收敛率与对象尺寸无关的条件，并刻画了不变特征维数增长与目标逼近之间的权衡。

I. Theoretical Framework & Hypotheses（理论框架与假设）

框架在函数类层面展开，不绑定具体神经参数化。设对象尺寸为 d（集合元素数或图节点数），特征维 r 固定。集合记为 X∈ℝ^r×d，带属性图记为 X∈ℝ^r×d×d，参考测度取标准高斯 λ_d（置换不变）。目标分无监督密度估计（dμ_d=f_d* dλ_d）与有监督回归（f_d*(x)=E[Y|X=x]）两类，工作空间分别为 H_d=L²(λ_d) 与 L²(μ_d)。跨尺寸由线性算子 T_d→D: H_d^inv→H_D^inv 承担，要求在 d≤D≤E 上满足相干性 T_d→d=Id、T_D→E∘T_d→D=T_d→E，精确目标传递 T_d→Df_d*=f_D*，以及范数保持 ‖T_d→Df−T_d→Dh‖_D=‖f−h‖_d。核心目标是维度无关的均匀界 sup_D≥d‖T_d→Df̂^inv_n,d−f_D*‖_D²≤ε（以概率至少 1−δ）。逼近能力由两条源条件刻画，见下表。

源条件	定义	含义
多项式源衰减	`B(k) ≲ k^{-τ}, τ>0`	有限光滑度的类比，高阶互动处处存在但递减
指数源衰减	`B(k) ≲ exp(-a k^ν), a,ν>0`	远强的正则性，ν 决定能否压过特征增长

M. Materials & Methods（材料与方法）

函数类与系数：以次数 ≤k 的置换不变多项式张成的空间 V_d,k 为积木，经 Gram–Schmidt 正交化；表示稳定性给出稳定维数 q_X(k) = sup_{d≥1} dim(V_{d,k})。
集合：对应多重对称多项式，由 Hardy–Ramanujan / Meinardus 分拆渐近得 q_set(k) = exp(C_r k^β + o(k^β))，其中 β = r/(r+1)，C_r = ((r+1)/r)(r ζ(r+1))^{1/(r+1)}（ζ 为黎曼 zeta）。
图：不变多项式由无标号属性多重图模式索引，枚举得 q_graph(k) = exp(k log k + O_r(k log log k))。固定尺寸 d 时，次数 ≤k 的不变特征数按 k^{rd}（集合）/ k^{rd²}（图）增长。
源条件：最佳 k 阶逼近误差 B_d(k) = inf_{f∈F_{d,k}} ‖f_d*−f‖_d²，其关于尺寸的一致包络 B(k) = sup_{d≥1} B_d(k)；回归下最优点为正交投影 Π_d,kf_d*，B(k) 即阶数 >k 的平方能量。
估计量：不变经验风险最小化 f̂^inv_{n,d,k}；有限维正则条件——损失在相关邻域曲率 ≥α、居中的经验得分次高斯参数 σ²，且 α,σ 对 d,k 一致。平方损失回归时 L_d(f)−L_d(f_d*) = ‖f−f_d*‖²_{L²(μ_d)}，故逼近误差恰由 B_d(k) 度量。
下界：源类 𝔉_X(B) 含表示稳定性计数出的所有不变方向；每个阶 k 需一个含 q_X(k) 个正交局部扰动、邻近分布 KL 二次的稳定尺寸子模型；极小最大风险 𝔑_n(X,B) = inf_{f̂} sup_{d≥1} sup_{f*∈𝔉_X(B)} E[sup_{D≥d} ‖f̂_D−f_D*‖_D²]。

R. Results（结果）

Theorem 4.1（维度无关标度律）：在精确等距传递、表示稳定性、相容性 T_{d→D}(F_{d,k}) ⊆ F_{D,k} 与一致损失正则条件下，仅用尺寸 d 数据训练的不变经验估计量，其平方误差同时对所有 D≥d 成立且与 d,D 无关：
(i) B(k) ≲ k^{-τ}：集合率 (log n)^{-τ(r+1)/r}；图率 (log n / log log n)^{-τ}。
(ii) B(k) ≲ exp(−a k^ν)：集合（β=r/(r+1)）分三段——ν>β 时 n^{-1+o(1)}；ν=β 时 n^{-a/(a+C_r)+o(1)}；0<ν<β 时 exp[−a C_r^{−ν/β}(log n)^{ν/β}(1+o(1))]。图在 ν>1 时 n^{-1+o(1)}，0<ν≤1 时 exp[−a(log n/log log n)^ν(1+o(1))]。
Theorem 4.2（极小最大最优性）：每个速率在常数与低阶因子内最优，𝔑_n(set,k^{-τ}) ≍ (log n)^{-τ(r+1)/r}，𝔑_n(graph,k^{-τ}) ≍ (log n/log log n)^{-τ}；下界在合适的稳定训练尺寸即成立，因而对取 sup_D≥d 的损失继续成立。这排除了换架构/正则化/优化器/传递规则带来改进的可能。
Corollary 4.3（样本复杂度的指数分离）：B(k)≍k^{-τ} 时，域内 n_in(ε)=ε^{-(τ+rd)/τ}（集合）、ε^{-(τ+rd²)/τ}（图）；均匀尺寸泛化 n_size(ε)=exp(Θ(ε^{-r/(τ(r+1))}))（集合）、exp(Θ(ε^{-1/τ} log(1/ε)))（图）。同一多项式源类：域内多项式、跨尺寸指数。
Table 2（极小最大速率对照） 见下表。

源衰减	域内率	集合（跨尺寸）	图（跨尺寸）
多项式 k^-τ	集合 n^-τ/(τ+rd) ；图 n^-τ/(τ+rd²)	(log n)^-τ(r+1)/r	(log n/log log n)^-τ
指数 exp(-a k^ν)	两者 n^-1+o(1)	ν>r/(r+1) 时 n^-1+o(1)	ν>1 时 n^-1+o(1)

a / D. Discussion & Conclusion（讨论与结论）

三个被混淆的属性：架构对尺寸的适用性、固定预测器的可迁移性、有限数据学习的统计尺寸泛化。前两者使跨尺寸预测成为可能，却都不决定样本复杂度，本文针对第三者。
精确传递的作用：精确传递移除跨尺寸近似失配，把统计困难孤立出来；若传递只是近似的，则即使数据无限也会留下一个额外的误差项。
与架构的关系：结果在函数类层面陈述，兼容置换等变图架构（含图 Transformer 配置换不变读出），但对称性本身不蕴含上述速率，仍需验证跨尺寸相容、范数受控传递、稳定特征增长与源衰减四项条件，作者不声称所有图 Transformer 都按此速率尺寸泛化。
分离的内在性：指数分离是整类问题的内在统计限制，不是多项式回归或证明技巧的产物；要更快只能加额外结构（更快的源衰减，或更小的可迁移互动族）。
局限与延伸：不同对称性的问题需要各自的稳定特征计数、不必有相同阈值；近似传递与更多对称群是自然的延伸方向，但与本文的有限样本现象不同。全文未提及资助来源。

🧠 IRMaD 思维导图

I 引言 R 研究问题/假设 M 方法 R 结果 a 讨论 D 结论

mindmap
  root((尺寸泛化的指数分离))
    I 引言
      尺寸可变 集合与图
      经典理论 域固定
      迁移已知 速率未知
      开放问题 样本复杂度
    R 框架
      置换不变多项式
      精确等距传递
      表示稳定性
      两条源衰减条件
    M 方法
      集合 多重对称多项式
      图 无标号多重图模式
      特征增长 计数
      极小最大下界
    R 结果
      多项式 对数率
      指数 近参数率
      集合图 阈值不同
      样本复杂度 指数分离
    a 讨论
      适用 迁移 泛化
      精确传递 孤立统计难
      兼容图架构
      内在限制非算法
    D 结论
      正则性决定效率
      快衰减才高效
      首次维度无关刻画

图：本研究的 IRMaD 思维导图。蓝色 I 引言；橙色 R 研究问题；绿色 M 方法；橙色 R 结果；紫色 a 讨论；红色 D 结论。