The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

📄 arXiv: 2607.07423v1 📥 PDF

作者: Zhiyuan Li

分类: cs.LG, stat.ML

发布日期: 2026-07-08

备注: 33 pages

💡 一句话要点

提出最优样本复杂度以学习自回归思维链

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自回归学习 思维链 样本复杂度 奇偶维度 多类学习 PAC学习 深度学习

📋 核心要点

  1. 现有方法在处理自回归思维链时，样本复杂度受到局部类维度的限制，且对回放长度敏感。
  2. 论文提出了一种新的样本复杂度上界，利用奇偶维度作为DS维度的细化，解决了回放长度对复杂度的影响。
  3. 主要结果表明，样本复杂度与回放长度无关，且在最坏情况下，样本复杂度的依赖性是最优的。

📝 摘要（中文）

本文证明在可实现的PAC设置下，完整自回归思维链的精确轨迹学习的样本复杂度由局部下一个标记类的标准多类速率上界所限制，该速率由Daniely-Shalev-Shwartz维度控制。在精确轨迹损失下，任何错误的动作都会使整个轨迹不正确；然而，对于每个停止规则和每个逐点停止的局部类，样本复杂度与回放长度无关。引入了奇偶维度，这是一种基于偶伪立方体的回放稳定的DS维度细化。该方法在有限限制下通过低坐标生成定理控制单包含密度，并且与DS维度不同的是，在自回归回放下不会增加。

🔬 方法详解

问题定义：本文要解决的是自回归思维链的学习样本复杂度问题，现有方法在多类学习中对回放长度的依赖性使得样本复杂度较高。

核心思路：论文提出了一种新的上界，利用奇偶维度来细化DS维度，从而在不增加复杂度的情况下控制样本复杂度。

技术框架：整体架构包括样本复杂度分析、奇偶维度的引入以及对局部类的适用性分析，主要模块包括样本复杂度的计算和奇偶维度的定义。

关键创新：最重要的技术创新点是引入了奇偶维度，这种维度在自回归回放下保持稳定，解决了DS维度在回放过程中的增加问题。

关键设计：在参数设置上，采用精确轨迹损失函数，并通过低坐标生成定理来控制单包含密度，确保样本复杂度的最优性。具体的网络结构和损失函数设计未详细说明，需进一步研究。

🖼️ 关键图片

img_0
img_1

📊 实验亮点

实验结果表明，样本复杂度与回放长度无关，且在最坏情况下，样本复杂度的依赖性为O((DSdim(H)+log(1/δ))/ε)，与现有方法相比，提供了显著的复杂度降低，提升了学习效率。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、智能对话系统和复杂决策支持系统。通过优化样本复杂度，可以在资源有限的情况下提高模型的学习效率，具有重要的实际价值和未来影响。

📄 摘要（原文）

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule $\mathtt{halt}$ and every pointwise $\mathtt{halt}$-halting local class $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)$, with no dependence on rollout length. The dependence on $\operatorname{DSdim}(\mathrm{H})$ is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of $\mathrm{H}$. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.