Prediction Under Imperfect Compression: A Theory of Approximate MDL¶

会议: NeurIPS 2026
arXiv: 2606.04834
OpenReview: https://openreview.net/forum?id=id5F8lsOvb
领域: 模型压缩
关键词: 最小描述长度, 近似优化, 序贯预测, 通用归纳, 复杂度正则化

一句话总结¶

本文首次形式化建立了近似最小描述长度（Approx-MDL）理论框架，证明加性松弛在正则化参数 $\lambda \ge 1$ 时能保持有限累积均方预测误差，并揭示了弱正则化（$\lambda < 1$）下的点态过拟合以及乘性松弛导致泛化彻底崩溃的理论分界。

研究背景与动机¶

最小描述长度（Minimum Description Length, MDL）原则通过最小化模型复杂度与模型解释数据长度之和 $L(\mathrm{model}) + L(\mathrm{data}\mid\mathrm{model})$，为奥卡姆剃刀法则奠定了严密的信息论基础。在序贯预测与通用归纳（Universal Induction）理论中，经典 MDL 范式指出：在可实现的可数测度族或可估计测度类上，精确极小化两阶段描述长度能够提供极其严格的压缩保障，进而转化为强可靠的渐近单步预测收敛性（如总变差收敛与有限累积均方误差）。这种“完美压缩等价于可靠预测”的理论基石，长期指引着统计推断、通用编码以及当代机器学习中的描述长度正则化方法。

然而，经典理论与实际计算之间存在着一道难以逾越的鸿沟。现代机器学习模型的训练与模型选择本质上受限于算力瓶颈与非凸优化困难，只能找到目标函数的局部极小或近似解；而所涉及的 Kolmogorov 复杂度等信息论度量更是不可计算的。正如图灵奖得主 Marvin Minsky 所洞见的，基于算法概率的最优模型选择虽然极其优美，但要求遍历无限搜索空间；在实践中，我们不可避免地只能采用某种有限精度的近似算法。这引发了一个深层的理论疑问：当精确压缩降级为“不完美压缩”（即仅获得近似极小值）时，MDL 还能否保证序贯预测的可靠性？这一保证依赖于怎样的近似尺度（加性松弛 vs 乘性松弛）以及何种强度的模型复杂度正则化？

本文正视了这一根本挑战，系统分析了带有复杂度惩罚系数 $\lambda$ 的平衡目标函数 $\lambda \cdot K_w(\nu) - \log_2 \nu(x_{<t})$ 在不同优化松弛条件下的序贯泛化性。核心 idea：证明了固定加性松弛在正则化参数 $\lambda \ge 1$ 时完全保持有限累积均方误差与零渐近单步误差，而在 $\lambda < 1$ 时必定引发可计算的确定性点态过拟合；同时证明乘性松弛因容忍随数据长度线性发散的误差，会在所有 $\lambda > 0$ 下彻底破坏通用预测保证。

方法详解¶

整体框架¶

本文考虑在有限字母表 $\mathcal{X}$（通用归纳特化为 $\{0, 1\}$）上的序贯预测问题。真实环境 $\mu$ 生成无限数据流 $X_{1:\infty} \sim \mu$。在时间步 $t$，预测器在观察到历史前缀 $x_{<t} = x_1 \dots x_{t-1}$ 后，从可数概率测度族 $\mathcal{M}$（配置先验权重 $(w_\nu)_{\nu \in \mathcal{M}}$ 满足 $\sum_\nu w_\nu \le 1$）中选择一个模型 $\tilde{\nu}_t$，并用条件分布 $\tilde{\nu}_t(\cdot \mid x_{<t})$ 预测下一个符号 $x_t$。预测器的整体表现由累积期望均方预测误差 $S_\infty(\mu, \rho) = \sum_{t \ge 1} \mathbb{E}_\mu [\sum_{a \in \mathcal{X}} (\mu(a \mid X_{<t}) - \rho_t(a \mid X_{<t}))^2]$ 衡量。带有正则化强度 $\lambda > 0$ 的加权 MDL 目标定义为： $$ L_{\lambda, w}(\nu; x_{<t}) := \lambda K_w(\nu) - \log_2 \nu(x_{<t}) = -\log_2 \bigl(w_\nu^\lambda \nu(x_{<t})\bigr), $$ 其中 $K_w(\nu) = -\log_2 w_\nu$。在此基础上，论文构建了三种截然不同的优化场景：精确极小化、具有固定常数 $C \ge 0$ 的加性近似（Additive Slack），以及具有相对比例 $(1+\varepsilon)$ 的乘性近似（Multiplicative Slack）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据流前缀 $x_{<t}$"] --> B["近似模型选择准则<br/>加性松弛 $C$ 或乘性松弛 $1+\varepsilon$"]
    B --> C["加性强正则化 $\lambda \ge 1$<br/>似然比超鞅与亲和力错位界"]
    B --> D["加性弱正则化 $\lambda < 1$<br/>确定性狄拉克测度点态记忆过拟合"]
    B --> E["乘性近似松弛 $\lambda > 0$<br/>允许误差随观测长度 $n$ 线性发散"]
    C --> F["输出：有限累积平方误差<br/>实现通用归纳与单步误差归零"]
    D --> G["输出：累积误差发散至 $+\infty$<br/>单步平方误差恒为 $1/2$ 无法消除"]
    E --> H["输出：选择有偏测度导致累积误差 $+\infty$<br/>通用预测一致性彻底失效"]

关键设计¶

1. 加性强正则化下的亲和力错位与似然比停时分析：证明 $\lambda \ge 1$ 下有限累积平方误差

当优化器仅能找到满足 $L_{\lambda, w}(\nu_t; x_{<t}) \le \min_{\nu \in \mathcal{M}} L_{\lambda, w}(\nu; x_{<t}) + C$ 的加性次优解时，其加权似然满足 $w_{\nu_t}^\lambda \nu_t(x_{<t}) \ge 2^{-C} \max_{\nu} \{w_\nu^\lambda \nu(x_{<t})\ge 2^{-C} w_\mu^\lambda \mu(x_{<t})$。这表明模型 $\nu$ 被选中的充要条件是似然比跨越依赖权重的阈值： $$ L_t^\nu := \frac{\nu(X_{<t})}{\mu(X_{<t})} \ge 2^{-C} \left(\frac{w_\mu}{w_\nu}\right)^\lambda =: c_\nu. $$ 为了严格控制在阈值事件 $\{L_t^\nu \ge c_\nu\}$ 下的预测误差，作者结合了两种互补的技术：首先，引入亲和力缺口（Affinity Gap）$d_t^\alpha(\mu, \nu) = 1 - \sum_{a} \mu(a \mid X_{<t})^{1-\alpha} \nu(a \mid X_{<t})^\alpha$，通过推广的 Csiszár $f$-发散 Pinsker 型不等式控制单步方差，证明了在参数 $\alpha \in (0, 1)$ 下的错位级数可由非负超鞅的差分相消控制，导出上界 $O(c_\nu^{-\alpha})$；其次，针对临界状态，利用似然比首次穿越阈值的停时 $\tau = \inf\{t \ge 1: L_t^\nu \ge c_\nu\}$，将条件续测度转化为两模型类静态 MDL，利用 Optional Stopping 与 Fatou 引理导出紧致的 $O(c_\nu^{-1})$ 界。通过在权重比 $r_\nu = w_\nu / w_\mu$ 上对两界进行最优点态内插，最终证明了总误差上界： $$ S_\infty(\mu, \rho) \le 16 K_{\mathrm{PH}} \lambda 2^{C/\lambda} w_\mu^{-1} < \infty, $$ 其中 $K_{\mathrm{PH}} = 21$ 为 Poland-Hutter 常数。该界对任意固定加性误差 $C$ 均成立，从而确立了经典 MDL 准则对加性优化噪声的强韧性。

2. 弱正则化下的点态过拟合构造：揭示 $\lambda < 1$ 时通用归纳的本质失败

为了判定 $\lambda = 1$ 是否为不可逾越的理论相变点，作者在通用预测环境（即 $\mathcal{M}$ 为全部可估计测度类，先验采用 Kolmogorov 复杂度权重 $w_\nu = 2^{-K(\nu)}$）中构造了对抗性选择器。当 $\lambda \in (0, 1)$ 时，对于任意观测到的二进制前缀 $x \in \{0, 1\}^*$，作者利用可估计测度概率计算描述与二进区间分割算法（Lemma A.3），构造了一个直接在该前缀上放置概率质量 1 的确定性可估计测度 $\nu_x$（即 $\nu_x(x) = 1$），其程序复杂度仅比最优测度额外增加 $-\log_2 \nu^\star(x) + O(\log(-\log_2 \nu^\star(x)))$。其得分满足： $$ L_\lambda(\nu_x; x) - \operatorname{OPT}\lambda(x) \le \lambda c - (1-\lambda)B, $$ 其中 }} \log_2(B+2) + \lambda c_{\mathrm{det}$B = -\log_2 \nu^\star(x)$。由于 $1 - \lambda > 0$，随着前缀长度增长使得负对数似然 $B \to \infty$，右端项存在一致有限上确界 $C_\lambda < \infty$。这意味着一个在历史上精确“死记硬背”当前样本的确定性模型，其正则化惩罚与数据解释代价的总和能够始终落入全局最优解的加性常数 $C_\lambda$ 邻域内。在真实环境为公平硬币 $\mathrm{Bern}(1/2)^\infty$ 时，这种确定性过拟合模型在每一步均预测确定性单点分布，导致单步期望平方误差永远恒等于 $(1/2 - 1)^2 + (1/2 - 0)^2 = 1/2$，累积误差发散为 $+\infty$，完全丧失了通用归纳能力。

3. 乘性松弛下的误差发散机制：证明相对优化尺度必然破坏预测

进一步将近似准则替换为最优化理论中更常见的相对（乘性）近似 $L_\lambda(\nu_t; x_{<t}) \le (1+\varepsilon) \operatorname{OPT}_\lambda(x_{<t})$。作者证明此时对任意正正则化系数 $\lambda > 0$ 和任意微小的松弛因子 $\varepsilon > 0$，通用预测均会彻底失效。其内在机制在于加性容忍度被放大为 $\varepsilon \operatorname{OPT}_\lambda(X_{1:n})$。 - 当 $0 < \lambda < 1$ 时，前述确定性点态记忆模型的加性差距仅为常数 $C_0$，而真实随机序列的最优目标值 $\operatorname{OPT}_\lambda(X_{1:n}) \ge \lambda K_m(X_{1:n}) - C_1$ 随前缀长度以概率 1 趋向无穷大，故该过拟合模型在 $n$ 充分大时必然进入 $(1+\varepsilon)$ 的容许乘性区间。 - 当 $\lambda \ge 1$ 时，最优得分在随机序列上以高概率满足 $\operatorname{OPT}_\lambda(X_{1:n}) \ge n - 4$。作者引入了一个微小偏置的有理参数伯努利测度 $\nu_\theta = \mathrm{Bern}(\theta)^\infty$（其中 $\theta \in (0, 1) \setminus \{1/2\}$），其描述复杂度 $K(\nu_\theta)$ 为常数，而交叉熵满足 $h_\theta < 1 + \varepsilon/4$。当序列长度 $n$ 增长时，乘性允许的松弛误差 $\varepsilon n$ 将远远压过有偏模型的轻微似然惩罚，导致选择器在至少 $67/80$ 的极高概率下被错误模型 $\nu_\theta$ 捕获。因为偏置模型的下一符号预测永远与真实公平硬币存在固定距离 $2(\theta - 1/2)^2 > 0$，其累积平方误差再次发散至 $+\infty$。

损失函数 / 训练策略¶

作为纯数学理论工作，本文没有经验损失的数值优化迭代，而是针对序贯决策规则建立了闭式极值分析。核心目标函数为带正则化因子的两阶段描述长度准则： $$ \min_{\nu \in \mathcal{M}} \left{ \lambda K_w(\nu) + \log_2 \frac{1}{\nu(x_{<t})} \right}. $$ 优化的理论约束由选择器的逼近质量给定： 1. 加性松弛：求解出的模型 $\nu_t$ 满足 $L_{\lambda, w}(\nu_t; x_{<t}) - \operatorname{OPT}_{\lambda, w}(x_{<t}) \le C$； 2. 乘性松弛：求解出的模型 $\nu_t$ 满足 $L_{\lambda, w}(\nu_t; x_{<t}) \le (1+\varepsilon) \operatorname{OPT}_{\lambda, w}(x_{<t})$。在理论分析中，选择器可在可容许集合内呈现任意对抗性行为（即 worst-case selector）；本文的肯定性结论是在这种全对抗鲁棒性下给出的最坏情况泛化证书。

实验关键数据¶

主实验¶

本文为纯理论成果，下表系统整理了论文在通用可估计测度类 $\mathcal{M}$ 与先验 $w_\nu = 2^{-K(\nu)}$ 下证明的不同近似优化条件下的累积期望均方误差保证 $S_\infty(\mu, \rho)$：

优化精度设定	正则化参数范围 $\lambda$	累积误差界 $S_\infty(\mu, \rho)$	单步预测收敛性 $e_t \to 0$	证明核心机制 / 对应定理
精确极小化 (Poland & Hutter, 2005)	$\lambda = 1$ (标准 MDL)	有限 ($< \infty$)	保证收敛至 0	静态 MDL 停时边界分析
精确极小化 (Milovanov, 2024)	$\lambda > 2$ (强正则化)	有限 ($< \infty$)	保证收敛至 0	Martin-Löf 随机序列单路径分析
加性松弛 (本文 Theorem 1.1)	$\lambda \ge 1$ (临界与强正则)	$\le 16 K_{\mathrm{PH}} \lambda 2^{C/\lambda} w_\mu^{-1} < \infty$	严格保证收敛至 0	亲和力伸缩与临界似然比停时内插
加性松弛 (本文 Theorem 1.2)	$0 < \lambda < 1$ (弱正则)	$+ \infty$ (发散)	不收敛 ($e_t \equiv 1/2$)	确定性测度常数级点态过拟合
乘性松弛 (本文 Theorem 1.3)	$\lambda > 0$ (全部正则区间)	$+ \infty$ (发散)	不收敛 ($e_t \ge \text{const} > 0$)	线性发散容许误差掩盖持续微小偏置

误差界紧致性与消融分析¶

为验证 Theorem 1.1 中对加性松弛 $C$ 与先验权重 $w_\mu$ 依赖关系的紧致性，作者在 Proposition 1.1 中构造了对抗性有限二值环境类，给出了匹配的下界分析：

理论构造 / 设定维度	累积误差下界表达式 / 渐近阶	与上界对比的理论结论
加性松弛常数 $C$ 敏感度	$\ge c \lambda \cdot 2^{C/\lambda} (w_\mu^{-1} - 1)$	证明指数增长因子 $2^{C/\lambda}$ 在最坏情况下不可避免
环境先验权重 $w_\mu$ 敏感度	$\propto w_\mu^{-1}$	证实对真实模型先验复杂度的逆线性依赖阶数严格紧致
正则化系数 $\lambda$ 渐近关系	$\ge c \lambda$	证实上界中关于 $\lambda$ 的线性缩放是本质内在规律
弱正则化下界 ($\lambda < 1$)	$S_\infty = \sum_{t=1}^\infty \frac{1}{2} = +\infty$	确立 $\lambda = 1$ 为可预测性的严格数学相变临界点

关键发现¶

相变边界严格确立：正则化系数 $\lambda = 1$ 是加性近似优化下通用预测成立与否的锋利相变阈值。当 $\lambda \ge 1$ 时，复杂度惩罚足够沉重，模型无法靠死记硬背历史样本获益；当 $\lambda < 1$ 时，描述历史数据所节约的似然收益必然压过编码确定性延伸所需的模型复杂度惩罚，导致不可避免的点态过拟合。
优化误差尺度的本质分离：加性松弛（绝对误差上界）与乘性松弛（相对误差上界）具有截然不同的泛化命运。在机器学习算法分析中普遍采用的相对近似比（$1+\varepsilon$），在长序贯决策中允许累积发散的绝对误差容量，彻底摧毁了压缩与预测之间的对应链条。

亮点与洞察¶

首次打通了不完美压缩与算法概率预测理论：将实际优化中无法精确求解极小值的现实约束数学化为近似松弛算子，填补了 Solomonoff 归纳与实际机器学习逼近算法之间长达数十年的理论空缺。
理论上证明了标准两阶段 MDL 正则化对加性优化噪声具备天然的免疫鲁棒性：只要惩罚权重不小于 1，算法工程师使用启发式或梯度下降等求得的近似解依然享有与精确求解同阶的预测一致性保证。
深刻揭示了相对松弛比（Multiplicative Factor）在通用归纳中的结构性缺陷，为大模型剪枝、量化与结构搜索中采用两阶段编码准则时的目标函数设计提供了明确原则：必须控制绝对描述长度误差而非相对误差。

局限与展望¶

作者承认本理论主要建立在离散可数测度族与通用可估计测度类框架下，尚未直接推广到参数连续可微的深层神经网络假设空间。
在实际应用中，加性常数 $C$ 可能随着神经网络参数量或数据吞吐量的提升而隐式缩放，未来工作需要进一步刻画当松弛量 $C(t)$ 成为时间步 $t$ 的缓慢增长函数时，预测一致性的衰减界限。
理论下界的构造依赖于对抗性选择器（worst-case selector），而在实际工程实践中（如 SGD 的隐式正则化），求解器的优化轨迹可能倾向于良态局部极小值，经验表现可能宽于纯对抗上界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次针对近似 MDL 建立完整的预测理论，数学证明兼具深度与严谨性。
实验充分度: ⭐⭐⭐⭐☆ 虽为纯数学理论论文无实证跑分，但正反两方面界限的数学构造极其完备且紧致。
写作质量: ⭐⭐⭐⭐⭐ 动机阐述深刻，技术链路严密，符号定义清晰，定理证明结构条理分明。
价值: ⭐⭐⭐⭐⭐ 为以压缩为核心驱动的深度学习模型选择与序贯预测算法提供了不可替代的理论基石。

理论构造 / 设定维度	累积误差下界表达式 / 渐近阶	与上界对比的理论结论
加性松弛常数 \(C\) 敏感度	\(\ge c \lambda \cdot 2^{C/\lambda} (w_\mu^{-1} - 1)\)	证明指数增长因子 \(2^{C/\lambda}\) 在最坏情况下不可避免
环境先验权重 \(w_\mu\) 敏感度	\(\propto w_\mu^{-1}\)	证实对真实模型先验复杂度的逆线性依赖阶数严格紧致
正则化系数 \(\lambda\) 渐近关系	\(\ge c \lambda\)	证实上界中关于 \(\lambda\) 的线性缩放是本质内在规律
弱正则化下界 (\(\lambda < 1\))	\(S_\infty = \sum_{t=1}^\infty \frac{1}{2} = +\infty\)	确立 \(\lambda = 1\) 为可预测性的严格数学相变临界点

优化精度设定	正则化参数范围 \(\lambda\)	累积误差界 \(S_\infty(\mu, \rho)\)	单步预测收敛性 \(e_t \to 0\)	证明核心机制 / 对应定理
精确极小化 (Poland & Hutter, 2005)	\(\lambda = 1\) (标准 MDL)	有限 (\(< \infty\))	保证收敛至 0	静态 MDL 停时边界分析
精确极小化 (Milovanov, 2024)	\(\lambda > 2\) (强正则化)	有限 (\(< \infty\))	保证收敛至 0	Martin-Löf 随机序列单路径分析
加性松弛 (本文 Theorem 1.1)	\(\lambda \ge 1\) (临界与强正则)	\(\le 16 K_{\mathrm{PH}} \lambda 2^{C/\lambda} w_\mu^{-1} < \infty\)	严格保证收敛至 0	亲和力伸缩与临界似然比停时内插
加性松弛 (本文 Theorem 1.2)	\(0 < \lambda < 1\) (弱正则)	\(+ \infty\) (发散)	不收敛 (\(e_t \equiv 1/2\))	确定性测度常数级点态过拟合
乘性松弛 (本文 Theorem 1.3)	\(\lambda > 0\) (全部正则区间)	\(+ \infty\) (发散)	不收敛 (\(e_t \ge \text{const} > 0\))	线性发散容许误差掩盖持续微小偏置