规模泛化的维度无关缩放定律：指数级分离

arXiv:2610.19279v1 公告类型：新论文 摘要：现代机器学习模型越来越多地处理集合和图等规模可变的结构化数据。其中一项核心要求是\emph{规模泛化}：即模型在某一规模的输入上训练后，能够泛化到另一种规模、甚至大得多的输入。然而，经典统计学习理论主要考虑固定的输入域，其理论保证往往随输入维度增加而弱化。尽管已有大量研究确定了集合和图上的模型何时能够跨输入规模迁移，但这些结果并未刻画这种迁移的统计代价：规模泛化的样本复杂度及其与经典域内学习的关系，在很大程度上仍属未知。我们建立了规模泛化的统计学习理论，并揭示了样本复杂度上精确的指数级分离。令 $n$ 表示训练样本数，我们证明，多项式源衰减不足以实现高效的规模泛化：虽然它使域内学习达到 $n^{-\Theta(1)}$ 的误差，从而具有多项式样本复杂度，但规模泛化误差仅以 $(\log n)^{-\Theta(1)}$ 的速率衰减，由此产生指数级分离。因此，域内学习的多项式样本复杂度在跨规模时可能变为指数级。随后，我们确定了一种指数源条件，在该条件下，规模泛化可达到 $n^{-\Theta(1)}$ 的误差，从而恢复多项式样本复杂度。这些理论保证与输入维度无关，仅取决于训练样本数，由此得到维度无关的缩放定律。我们还给出了相匹配的极小极大下界，确立了最优性。据我们所知，本研究首次提出了规模泛化的维度无关极小极大理论，并严格刻画了学习何时能够跨输入规模迁移，以及这种迁移需要付出何种统计代价。