首次精确刻画Transformer的样本复杂度，揭示模型容量与输入长度的关系。
Tight Sample Complexity of Transformers
- 通过VC维分析深度Transformer的表达能力，给出紧致上下界。
- 证明链式思维学习需至少Ω(LW log((T+T′)W/L))个样本。
- 适用于理解大模型泛化性能，适合理论研究者阅读。
我们精确刻画了深度为L、总参数量为W的Transformer在将长度为T的输入序列映射到单一输出时的VC维，建立了上界O(LW log(TW))和几乎匹配的下界Ω(LW log(TW/L))。进一步精确刻画了使用此类Transformer进行链式思维学习的样本复杂度：教师强制法（即在训练数据中选择与整个思维链一致的预测器）的样本复杂度为O(LW log((T+T′)W))，而任何利用链式思维数据的学习规则至少需要Ω(LW log((T+T′)W/L))个样本，其中T为输入长度，T′为自回归步数。
原文摘要 · Abstract (English)
We tightly characterize the VC dimension of depth-$L$ Transformers with a total of $W$ parameters, mapping an input sequence of length $T$ to a single output, establishing an upper bound of $O(L W \log (T W))$ and a nearly matching lower bound of $Ω(L W \log (T W / L))$. We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity $O\left(L W \log \left(\left(T+T^{\prime}\right) W\right)\right)$ and that any learning rule that uses chain-of-thought data requires at least $Ω\left(L W \log \left(\left(T+T^{\prime}\right) W / L\right)\right)$ examples, where $T$ is the input length and $T^{\prime}$ is the number of autoregressive steps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。