无遗憾语言生成

arXiv:2610.23641v1 公告类型：新论文 摘要：我们引入无遗憾生成，要求生成器在所有演示序列和兼容的目标语言上，统一地将错误次数控制为次线性。我们还提出了一个不可知变体，允许演示任意给定，且这些演示可能与任何语言都不兼容。针对这两种设置，我们引入了基于树的强制犯错维数，该维数能够精确刻画有限时域的极小极大复杂度，并建立无遗憾生成的充要条件。我们的刻画揭示了丰富的生成速率谱：在常数缩放意义下，每个可容许的非递减曲线都能在可实现和不可知设置中实现。最后，我们将生成复杂度与在线预测联系起来：对于具有有限 Littlestone 维数 \(d\) 的语言类，我们得到可实现情形下的错误上界 \(O(d\log(1+T/d))\)，以及不可知情形下的遗憾上界 \(O(\sqrt{dT\log(1+T/d)})\)。可实现情形下的上界在普适常数意义下是最优的。