論文の概要: Prediction Under Imperfect Compression: A Theory of Approximate MDL

• arxiv url: http://arxiv.org/abs/2606.04834v1
• Date: Wed, 03 Jun 2026 13:03:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.768826
• Title: Prediction Under Imperfect Compression: A Theory of Approximate MDL
• Title（参考訳）: 不完全圧縮下の予測:近似MDLの理論
• Authors: Qian Li, Xinyu Mao, Shang-Hua Teng, Guangxu Yang,
• Abstract要約: 近似および正規化の形式の下で、MDLは信頼できる逐次予測を保証できるか? 重み付けされた MDL 目的のより一般的な形の加法的 slack $C$ の近似に対して、累積期待二乗予測誤差はすべての$ge1$に対して有限であることを示す。
• 参考スコア（独自算出の注目度）: 11.9016695006988
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.
• Abstract（参考訳）: 最小記述長 (MDL) は、全記述長を最適化することで、オッカムのカミソリの原理を定式化する:$L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$。 逐次予測のために、MDL法は、次のステップ予測のために観測されたプレフィックスの最小目標スコアのモデルを繰り返し選択する。 古典的MDL予測理論は、MDL目標の正確な最適化は、信頼性のある予測をサポートする強力な圧縮保証を提供することを示している。 しかし、現実的な機械学習は通常、目的関数をほぼ最適化することによってのみモデルを見つけることができる。 このギャップを埋めるために、本稿は以下の根本的な問題に対処する: 近似と正規化のどの形態の下で、MDLは信頼できる逐次予測を保証できるか? この作品には原則的な特徴がある。 重み付けされた MDL の目的のより一般的な形の加法的 slack $C$ の近似に対して、$λ\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$ の累積予想二乗予想誤差はすべての $λ\ge1$ に対して有限であることを示す。 affinity-telescoping の議論によって $λ>1$ が証明され、境界の場合 $λ=1$ は、正確な静的 MDL 境界に基づいて、確率比の停止引数によって証明される。 我々の結果は、古典的MDL正規化は任意の固定加算最適化誤差に対して頑健であることを示す。 さらに、近似MDLフレームワークの特性が鋭いことを証明している: 0<λ<1$ のとき、推定可能測度の普遍クラスにおいて過適合が無限累積予想誤差を生じさせることがあり、従ってモデル-複雑正則化の強い形式が必要である。 さらに、モデル選択は、乗法近似の下で、すべての正規化されたレジーム$λ>0$で失敗し、したがって加法近似は十分かつ必須である。

関連論文リスト

• Theoretical Limits of Language Model Alignment [9.45142272392467]
  言語モデル(LM)アライメントは、ベースモデルの能力を保ちながら、人間の好みを反映するモデル出力を改善する。 最も一般的なアライメントアプローチは、(i)強化学習であり、KL分割制約の下で期待される報酬を最大化する。 固定KL分割予算に対する最大期待報酬利得を導出することにより、KL正規化アライメントの情報理論的限界を特徴づける。
  論文  参考訳（メタデータ） (2026-05-08T01:32:22Z)
• A Probabilistic Inference Scaling Theory for LLM Self-Correction [49.42817548142699]
  大規模言語モデル(LLM)は、自己補正によって生成された回答を洗練する能力を示した。 本稿では,精度変化のダイナミクスをモデル化する確率論的理論を提案し,マルチラウンド自己補正で観測された性能改善について説明する。
  論文  参考訳（メタデータ） (2025-08-22T15:15:38Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  対数損失を伴う次のトーケン予測は自己回帰シーケンスモデリングの基盤となる。 次トーケン予測は、適度な誤差増幅を表す$C=tilde O(H)$を達成するために堅牢にすることができる。 C=e(log H)1-Omega(1)$。
  論文  参考訳（メタデータ） (2025-02-18T02:52:00Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。 VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。 後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
  論文  参考訳（メタデータ） (2023-10-17T18:27:27Z)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)
• Revisiting minimum description length complexity in overparameterized models [38.21167656112762]
  本稿では,線形モデルとカーネル手法に対するMDL-COMPの広範な理論的特性について述べる。 カーネル法では,MDL-COMPがサンプル内誤差を最小化し,入力の次元が増加するにつれて減少することを示す。 また、MDL-COMPがサンプル内平均二乗誤差(MSE)を束縛していることも証明する。
  論文  参考訳（メタデータ） (2020-06-17T22:45:14Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。