Fugu-MT 論文翻訳(概要): Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

論文の概要: Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

arxiv url: http://arxiv.org/abs/2610.19279v1
Date: Tue, 13 Oct 2026 22:55:32 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-16 12:10:45.439262
Title: Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation
Title（参考訳）: 大規模一般化のための次元自由スケーリング法則-指数分離
Abstract要約: 我々は,サイズ一般化の統計的学習理論を開発し,急激な指数的分離サンプル複雑性を確立する。次に、サイズ一般化が誤差$n-(1)$を達成する指数的ソース条件を同定する。これらの保証は入力次元とは独立であり、トレーニングサンプルの数にのみ依存する。この研究は、最初の次元自由最小値理論と、いつ、何の統計的コストで、学習は入力サイズ間で伝達できるのかという厳密な特徴を与える。
参考スコア（独自算出の注目度）: 15.56971726974056
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize 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 input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such 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. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-Θ(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-Θ(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-Θ(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. 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.
Abstract（参考訳）: 現代の機械学習モデルは、集合やグラフのような可変サイズの構造化データでますます機能する。中心的な要件は \emph{size generalization} であり、ある大きさの入力に基づいて訓練されたモデルが、異なる、より大きなサイズの入力に一般化する能力である。しかし古典的な統計的学習理論は、主に固定入力領域を考慮し、その保証はしばしば入力次元によって悪化する。集合とグラフのモデルが入力サイズにまたがって転送できることは広く研究されているが、そのような結果は、サイズ一般化のサンプルの複雑さや古典的なドメイン内学習との関係といった統計的コストを特徴づけるものではない。我々は,サイズ一般化の統計的学習理論を開発し,標本複雑性の急激な指数的分離を確立する。トレーニングサンプルの数を$n$とすると、多項式源の減衰は効率のよいサイズの一般化には不十分であることが示される: 誤差は$n^{->(1)}$であり、したがって、ドメイン内学習には多項式サンプルの複雑さが生じるが、サイズ一般化誤差は$(\log n)^{->(1)}$でしかなく、指数関数的な分離をもたらす。したがって、多項式のドメイン内サンプルの複雑さは、サイズによって指数関数的になる。次に、多項式サンプルの複雑性を回復する誤差$n^{->(1)}$を大まかに一般化した指数関数的ソース条件を同定する。これらの保証は入力次元とは独立であり、トレーニングサンプルの数にのみ依存する。また、一致したミニマックスの下位境界も提供し、最適性を確立します。我々の知る限り、この研究は、サイズ一般化の次元自由最小理論と、いつ、何の統計的コストで、学習が入力サイズ間で伝達できるかを厳密に特徴づけるものである。

論文の概要: Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

関連論文リスト