arXiv:2606.04834cs.LG2026-06

研究近似压缩下的预测可靠性,发现只要误差固定,经典压缩方法仍有效。

Prediction Under Imperfect Compression: A Theory of Approximate MDL

  • 提出带松弛项的广义平衡MDL框架,分析近似优化下的预测性能
  • 证明当λ≥1时,累积预测误差有界,λ<1则可能无限膨胀
  • 揭示加法近似充分且必要,乘法近似会引发模型选择失败

最小描述长度(MDL)通过最小化模型与数据联合描述长度来实现奥卡姆剃刀原则。对于序列预测,经典MDL方法在每一步选择使观察前缀描述长度最小的模型。已有理论表明,精确优化可提供强压缩保证,支持可靠预测。然而实际机器学习中常只能近似优化目标函数。本文回答核心问题:何种近似和正则化形式下,近似MDL仍能保证可靠预测?研究证明:对更一般的平衡MDL目标 $λ·L(模型)+L(数据|模型)$,只要添加固定加性松弛 $C$,且 $λ≥1$,则所有 $λ≥1$ 下累积期望平方预测误差均有限。$λ>1$ 通过亲和-望远镜论证证明,$λ=1$ 基于精确静态MDL界限的似然比停止论证。结果表明,经典MDL正则化对固定加性优化误差具有鲁棒性。进一步证明该刻画是紧致的:当 $0<λ<1$ 时,在可估计测度的通用类中可能发生过拟合,导致累积期望误差无穷,因此必须强正则化模型复杂度。此外,在任意 $λ>0$ 的正则化区间内,乘法近似会导致模型选择失败,故加法近似既是充分条件也是必要条件。

原文摘要 · Abstract (English)

Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: $L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$. For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction? This work offers a principled characterization. We prove that for any approximation with additive slack $C$ of the more general form of the balanced MDL objective: $λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$, the cumulative expected squared prediction error is finite for all $λ\ge1$. The case $λ>1$ is proved by an affinity-telescoping argument, while the boundary case $λ=1$ is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When $0<λ<1$, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime $λ>0$, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.

信息论预测理论正则化模型选择

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。