論文の概要: Compressing Value Predictions for Learning-Augmented Metrical Task Systems

• arxiv url: http://arxiv.org/abs/2609.33580v1
• Date: Sun, 27 Sep 2026 13:54:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-05 15:36:07.200186
• Title: Compressing Value Predictions for Learning-Augmented Metrical Task Systems
• Title（参考訳）: 学習強化メトリックタスクシステムにおける圧縮値予測
• Abstract要約: 本稿では,メートル法タスクシステムに対するランドマーク圧縮値予測について紹介する。 固定されたランドマークを用いて任意のランダム化アルゴリズムに対して、一致する$(T r_m)$ローバウンドを証明した。 本研究の結果は,オンラインMSSにおいて,メトリックカバレッジ,予測インターフェース,圧縮予測の学習保証を関連づけるものである。
• 参考スコア（独自算出の注目度）: 11.025817260296492
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their algorithmic value. We introduce landmark-compressed value predictions, in which the predictor reports predicted dual values only at $m$ landmarks and the remaining values are reconstructed by a Lipschitz extension. Our algorithm achieves additive excess cost $O(T\,r(L) + \sum_t δ_t)$, where $r(L)$ is the covering radius of the landmarks and $δ_t$ measures prediction error up to additive shifts; local and value-dependent bounds refine this guarantee. For sparse landmark sets on unit-spaced finite lines, we prove a matching $Ω(T r_m)$ lower bound for every randomized algorithm using fixed landmarks, even with advance access to their entire exact absolute-value table. The prediction interface also matters: on two states with one landmark, exact absolute values permit horizon-independent excess, whereas exact relative values force worst-case expected excess linear in $T$. We give PAC guarantees for learning compressed prediction tables, with efficient empirical-risk minimization for fixed landmarks. Our results connect metric coverage, prediction interfaces, and learning guarantees for compressed predictions in online MTS.
• Abstract（参考訳）: 計量的タスクシステム(MTS)の学習強化アルゴリズムは、正準双対値の予測を利用することができるが、既存の定式化は、通常、全ての状態に対して予測を必要とする。 これらの予測が,アルゴリズムの値を維持しつつ,少数の代表状態に圧縮できるかどうかを検討する。 我々はランドマーク圧縮された値予測を導入し、予測器が予測した2値は$m$のランドマークのみであり、残りの値はリプシッツ拡張によって再構成される。 我々のアルゴリズムは、加法的余剰コスト$O(T\,r(L) + \sum_t δ_t)$, ここで、$r(L)$はランドマークの被覆半径であり、$δ_t$は加法的シフトまで予測誤差を測定する。 単位空間の有限直線上のスパースランドマーク集合に対して、固定されたランドマークを用いて全てのランダム化アルゴリズムに対して、完全絶対値テーブル全体への事前アクセスでさえ一致する$Ω(T r_m)$ローバウンドを証明する。 1つの目印を持つ2つの状態において、正確な絶対値は地平線非依存の余剰を許容し、一方、正確な相対値は、最悪のケース予測余剰を$T$で強制する。 我々は、圧縮予測テーブルの学習にPAC保証を与え、固定されたランドマークに対する効率的な経験リスク最小化を行う。 本研究の結果は,オンラインMSSにおいて,メトリックカバレッジ,予測インターフェース,圧縮予測の学習保証を関連づけるものである。

関連論文リスト

• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
  マシンが学習した予測は、オフラインNPハード最適化を高速化するが、予測者にその問題を解決するために何をすべきかを尋ねる。 CASP (Certificate-Augmented Solution Pruning) は代わりに、どの部分の検索空間を無視するかを尋ね、サウンドタイム検証器がチェックした後のみ、各回答を受け入れる。 トレーニングされた予測器では、未検証プルーニングは配布シフト時の最適値の最大26%を失うが、検証された同じ予測のデプロイでは、何も失われることはない。
  論文  参考訳（メタデータ） (2026-07-16T04:02:15Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
  論文  参考訳（メタデータ） (2026-05-21T08:57:38Z)
• Backward Conformal Prediction [46.298122008420414]
  我々は、予測セットのサイズを柔軟に制御しながら、コンフォーマルカバレッジを保証するメソッドである$textitBackward Conformal Prediction$を紹介した。 提案手法は,観測データに基づいて,予測セットサイズがどう振る舞うかを制約するルールを定義し,それに応じてカバレッジレベルを適応させる。 このアプローチは、医療診断のような大きな予測セットが実用的でないアプリケーションで特に有用である。
  論文  参考訳（メタデータ） (2025-05-19T21:08:14Z)
• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)

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

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