@HazanPrinceton: 正逢我们下周在ICML的教程，Annie发布了我们通用序列预处理论文的更新…

恰逢下周我们在ICML的教程，安妮更新了我们的通用序列预处理论文，该论文获得了近乎紧的隐藏维度无关遗憾界：（将在教程中介绍！）https://t.co/mxzGAMyVo7 — # 二阶方法用于序列预处理的威力 来源：https://arxiv.org/html/2605.08390 ###### 摘要 针对具有长记忆（即边际稳定系统）的线性动力系统的序列预测方法，其遗憾通常随底层生成模型的隐藏维度线性增长。尽管已开发出许多方法在不同程度上应对这一情况，但我们表明，简单地使用二阶Vovk-Azoury-Warmuth (VAW) 算法来学习一个短的自回归含输入 (ARX) 模型，就能取得惊人强劲的结果：对于来自边际稳定线性动力系统的有界序列数据，该系统的谱位于复圆盘内，但排除了负实轴周围宽度为 \delta 的角形区域，该算法实现了与维度无关的遗憾界 \mathcal{O}\!\left(\delta^{-4}\log^{2}T\right)。据我们所知，这些界是目前最优的。我们结果的关键组成部分来自：1) 使用“通用序列预处理”(USP) 理论 Marsden and Hazan (2025b (https://arxiv.org/html/2605.08390#bib.bib15)) 来证明存在一个自回归系数的最优设置；2) 应用VAW算法，该算法更好地利用了USP提供的记忆压缩；以及 3) 分析圆形扇区上的Faber多项式，以将这些结果扩展到具有复谱的系统。 ## 1 引言 序列预测中的一个核心挑战是底层生成过程同时具有长记忆和高隐藏维度。在此设定下进行研究的经典理论模型是边际稳定线性动力系统。应用于此设定的大多数方法得出的遗憾界随隐藏维度线性增长，例如参见 Hazan et al. (2018 (https://arxiv.org/html/2605.08390#bib.bib2))；Kailath (1980 (https://arxiv.org/html/2605.08390#bib.bib33))；Chen (1999 (https://arxiv.org/html/2605.08390#bib.bib34))；Hazan (2016 (https://arxiv.org/html/2605.08390#bib.bib27))；Simchowitz et al. (2019 (https://arxiv.org/html/2605.08390#bib.bib8))；Tsiamis and Pappas (2019 (https://arxiv.org/html/2605.08390#bib.bib9))；Lee (2022 (https://arxiv.org/html/2605.08390#bib.bib10))；Bakshi et al. (2023 (https://arxiv.org/html/2605.08390#bib.bib11))。通用序列预处理 (USP) Marsden and Hazan (2025b (https://arxiv.org/html/2605.08390#bib.bib15)) 是第一种（据我们所知）同时实现与维度无关的亚线性遗憾的方法，即使在隐藏转移矩阵具有复特征值的情况下也是如此。他们开发的方法是将原始信号与切比雪夫多项式的系数进行卷积。这种构造实现了记忆的指数压缩，将有效记忆减少到与序列长度（或时域）成对数关系。然而，这是有代价的：切比雪夫系数随次数指数增长，导致最优直径很大。这与一阶学习方法不匹配，后者与最优直径呈线性关系，产生了次优的遗憾 \mathcal{O}(T^{11/13}) Marsden and Hazan (2025b (https://arxiv.org/html/2605.08390#bib.bib15))。此外，虽然他们的工作确实适用于具有复特征值的隐藏转移矩阵，但他们要求特征值的复参数以 o(1/\mathrm{poly}\log T) 的速率消失。在这项工作中，我们利用通用序列预处理的记忆压缩洞见，设计了一个更强的算法，该算法对于更广泛的线性动力系统类别实现了与维度无关的、多对数级的遗憾。这是对所有其他已知方法的改进，在表1 (https://arxiv.org/html/2605.08390#S1.T1) 中更清晰地展示。

表 1：对于边际稳定且具有非对称转移矩阵的线性动力系统的累积预测误差界。对于“复角 \phi”，结果仅适用于隐藏转移矩阵的谱位于楔形区域 W_{\phi}=\{z\in\mathbb{C}:|z|\leq 1,\ |\arg(z)|\leq\phi\} 时。

考虑一个具有输入 u_t\in\mathbb{R} 和输出 y_t\in\mathbb{R} 的线性动力系统，其演化方程为： \mathbf{h}_t = \mathbf{A}\mathbf{h}_{t-1} + \mathbf{B}u_t \qquad y_t = \mathbf{C}\mathbf{h}_t, (1) 其中 \mathbf{h}_t\in\mathbb{R}^{d_{\text{hidden}}} 是隐藏状态。我们建议的算法是使用 Vovk-Azoury-Warmuth 预测器，采用一个短的自回归含输入 (ARX) 特征向量 [y_{t-1},...,y_{t-n},u_t,...,u_{t-n+1}] 来预测 y_t，其中 n 是一个超参数，应随预测时域对数增长，详见算法2 (https://arxiv.org/html/2605.08390#alg2)。相比之下，原始的 USP 算法建议将 y_t 预测为 -\sum_{i=1}^{n}c_i y_{t-i} + \sum_{j=0}^{n-1}\theta_j u_{t-j}，其中系数 c_1,...,c_n 是固定的，来自切比雪夫多项式，而 \theta_j 则通过一阶方法学习。

实轴 虚轴 W_{\phi} \pi-\phi \pi-\phi 1 图 1：楔形谱类 W_{\phi}=\{z\in\mathbb{C}:|z|\leq 1,\ |\arg(z)|\leq\phi\}。在我们的主要结果中，\phi=\pi-\delta，因此谱可以占据单位圆盘，但排除了负实轴周围宽度为 2\delta 的对称角形间隙。

在高层面上，预处理器的有效性，即系数集 c_1,...,c_n，由两个量决定：变换后表示的有效记忆和最优直径的大小。在USP的设定中，我们可以将预处理后的信号视为原始信号的压缩表示。压缩表示需要一个与切比雪夫多项式次数成线性的历史，但系数幅度增长非常大。这引出了最小描述长度 (MDL) 原则 Rissanen (1978 (https://arxiv.org/html/2605.08390#bib.bib17))；Grünwald (2007 (https://arxiv.org/html/2605.08390#bib.bib18))，该原则旨在最小化模型结构复杂性与表示其参数所需比特长度的联合成本。对于多项式，最小描述长度原则表明，最高效的表示是多项式的次数线性增长而系数幅度对数增长。受此原则启发，我们观察到 Vovk–Azoury–Warmuth (VAW) 预测器 Azoury and Warmuth (2001 (https://arxiv.org/html/2605.08390#bib.bib20))；Vovk (2001 (https://arxiv.org/html/2605.08390#bib.bib19)) 的遗憾正好匹配这种平衡：它随有效记忆线性增长，而仅随最优直径对数增长。为了在此设定中应用VAW，我们不再通过将 \sum_{i=1}^{n}c_i y_{t-i} 纳入预测来显式地“预处理”信号 y_t，而是将这些自回归项包含在特征向量中。然而，USP的作用仍然至关重要，因为它为最优解提供了认证，并从根本上解释了为什么自回归项允许如此有效的记忆压缩（即，我们只需要使用最后 n 个输入和输出就能做出好的预测）。通过改用二阶VAW算法，我们将累积预测误差从 \mathcal{O}(T^{11/13}) 改进为 \mathcal{O}\!\left(\log^{2}(T)\right)。此外，USP Marsden and Hazan (2025b (https://arxiv.org/html/2605.08390#bib.bib15)) 仅适用于隐藏转移矩阵的谱接近实轴的系统，复参数必须受限于 1/\mathrm{poly}\log(T)。我们的新方法使我们能够考虑整个复圆盘上的谱。事实上，令 W_{\phi}:=\left\{z\in\mathbb{C}:\lvert z\rvert\leq 1\textrm{ and }\arg(z)\leq\phi\right\}。假设数据的底层隐藏转移矩阵的谱位于 W_{\pi-\delta} 中。那么该算法做出的预测所实现的累积平方损失上界为 \mathcal{O}\!\left(\delta^{-4}\log^{2}(TL)\right)。这在 d 的依赖性方面是紧的。已知如果隐藏转移矩阵是移位置换矩阵（其谱位于 W_\pi），那么任何算法的遗憾必须随隐藏维度线性增长 Hazan and Marsden (2026 (https://arxiv.org/html/2605.08390#bib.bib16))。然而，我们表明这个对抗性例子确实依赖于谱位于 W_\pi。实际上，如果我们假设谱包含在 W_{\pi-\delta} 中，对于任何常数 \delta>0，我们都能实现与维度无关的遗憾。为了证明这一点，我们需要一种新的方法来保证扩展到 W_{\pi-\delta} 的最优解，因为切比雪夫多项式仅适用于 W_{1/\mathrm{poly}\log(T)}。解决方案来自适用于圆形扇区的Faber多项式。我们的分析更深入地理解了复谱在学习线性动力系统难度中的作用。更一般地，每个有用的USP预处理器都是一个首一多项式，在隐藏转移矩阵的谱上取值很小。切比雪夫多项式对于接近实轴的谱是最优的；Faber多项式是对应于更一般紧致谱集的极值对象，在本文中我们将它们用于圆形扇区。

1.1 我们的结果

我们的主要贡献如下：

序列预测的对数遗憾：

我们提出了一种二阶有限历史预测器：在原始特征向量 (y_{t-1},\ldots,y_{t-n},u_t,\ldots,u_{t-n+1}) 上运行VAW（参见算法2 (https://arxiv.org/html/2605.08390#alg2)）。在定理2 (https://arxiv.org/html/2605.08390#Thmtheorem2) 中，我们证明如果存在一个次数为 n 的首一多项式，其在谱上的残差大小为 \alpha_n，系数规模为 G_n，那么原始特征VAW问题存在一个比较器，并且VAW的累积预测损失仅为 \mathcal{O}(TL^{2}\alpha_n^{2}+Y^{2}n\log(G_n YL))。相比之下，原始的一阶方法得到的累积预测损失为 \mathcal{O}(n^{2}G_n\sqrt{T}+\alpha_n T^{2})（参见 Marsden and Hazan (2025b (https://arxiv.org/html/2605.08390#bib.bib15)) 中的定理D.1）。将我们的定理实例化为切比雪夫多项式，得到推论1 (https://arxiv.org/html/2605.08390#Thmcorollary1)：对于谱在 [-1,1] 内的情况，累积预测损失为 \mathcal{O}\!\left(\log^{2}(T)\right)，这相较于使用一阶方法得到的 \mathcal{O}(T^{11/13}) 累积损失有了巨大改进。

扩展到具有常数复参数的系统：

我们将通用序列预处理 (USP) 的理论保证扩展到一个严格更广泛的动力系统类别。我们使用适用于圆形扇区的Faber多项式。引理1 (https://arxiv.org/html/2605.08390#Thmlemma1) 表明，对于每个角间隙 \delta>0，存在一个实首一多项式 p_{n,\delta}，满足 \sup_{z\in W_{\pi-\delta}}|p_{n,\delta}(z)|\leq 2e^{-n\delta^{2}/\pi^{2}} 并且 \max_i|c_i|\leq 100^{n}。因此，即使隐藏动力学具有常数复参数，只要谱避开负实轴周围一个常数宽度的楔形区域，近似误差仍然保持指数级小。注意，这个贡献与将VAW应用于USP是正交的。实际上，人们可以将这个关于Faber多项式的结果应用于原始的的一阶方法，并表明USP可以应用于更广泛的序列类别。

1.2 紧致性与角形间隙的作用

我们与维度无关的保证依赖于排除负实轴周围一个常数宽度的楔形区域。这个假设不仅仅是证明的产物。Hazan and Marsden (2026 (https://arxiv.org/html/2605.08390#bib.bib16)) 附录A中的循环置换下界构造了一个 d 维的边际稳定系统，对于该系统，任何精确的有限记忆预测器都需要 \Omega(d) 的记忆，因此对于时域 T\geq d，会产生 \Omega(d) 的累积预测误差。从谱上看，这个构造是一个循环置换：其特征值是 d 次单位根。因此，谱在角尺度 1/d 上接近负实轴，并且对于偶数 d，精确包含 -1。用我们的楔形类记号表示，相应的间隙参数因此是 \delta=\Theta(1/d)。这个下界阐明了Faber和切比雪夫预处理的作用。当目标是维度无关的预测时，如果谱满足足够的角分离，多项式预处理器可以指数级压缩记忆。如果允许与隐藏维度的多项式依赖，那么对于任意谱，总是可以回到经典的Cayley–Hamilton表示，它使用 d 阶记忆。剩下的间隙是数量上的：我们的楔形保证在最终界中缩放为 1/\delta^{4}，而置换下界仅排除了低于 1/\delta 阶的记忆。缩小这个多项式间隙仍然是一个开放问题。

1.3 相关工作

我们的工作与潜在线性动力系统中的预测（而非恢复）文献关系最为密切。早期的谱滤波结果展示了与最优LDS预测器在线竞争的能力，但无需显式的系统辨识，然而这依赖于强谱结构，如对称性 Hazan et al. (2017 (https://arxiv.org/html/2605.08390#bib.bib1))。Hazan et al. (2018 (https://arxiv.org/html/2605.08390#bib.bib2)) 后来将谱滤波扩展到一般的潜在线性动力系统，使用了一种能适应相位的凸松弛，并且不再需要对称的转移矩阵。然而，在非对称设定下，他们的保证仍然具有与时域和隐藏维度的多项式依赖性，因此在我们研究的场景中无法产生多对数级的累积预测误差界。关于 d 和 T 的多项式界也是 Cayley–Hamilton 定理和实现理论的经典结论；例如，参见 Kailath (1980 (https://arxiv.org/html/2605.08390#bib.bib33))；Chen (1999 (https://arxiv.org/html/2605.08390#bib.bib34))。

第二类工作更直接地研究边际稳定系统。Ghai et al. (2020 (https://arxiv.org/html/2605.08390#bib.bib4)) 证明了边际稳定系统具有多项式系统参数依赖性的无遗憾预测保证。在完全观测的对抗性设定下，他们的界仍然与时域呈多项式关系，而其更强的关于 T 的多对数结果要么依赖于随机性假设，要么依赖于简化为有限记忆自回归预测。这些结果并非直接可比，因为