論文の概要: Parsimonious Learning-Augmented Online Metric Matching

• arxiv url: http://arxiv.org/abs/2605.26886v1
• Date: Tue, 26 May 2026 11:47:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:41.983692
• Title: Parsimonious Learning-Augmented Online Metric Matching
• Title（参考訳）: 同時学習型オンラインメトリックマッチング
• Authors: Yongho Shin, Phanu Vajanopath,
• Abstract要約: 増大する研究ラインは、パフォーマンス保証と学習強化アルゴリズムで使用される予測数の間のトレードオフを研究する。 擬似学習拡張アルゴリズムを開発し,その性能の低い境界を確立する。 提案手法は,実際の予測がない場合に仮想的な予測を埋め込むことにより,Follow-the-Predictionフレームワークを擬似的な設定に拡張する。
• 参考スコア（独自算出の注目度）: 1.5755923640031846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.
• Abstract（参考訳）: 近年,特にオンライン最適化の文脈において,学習強化アルゴリズムが注目されている。 キャッシングやメートル法タスクシステムといった問題に対する学習強化アルゴリズムにおける性能保証と予測数のトレードオフを研究する研究が増えている。 本稿では,この研究の行を,擬似的な学習強化アルゴリズムを開発し,その性能の低い境界を確立することで,オンライン計量マッチングに拡張する。 提案手法は,実際の予測がない場合に仮想的な予測を埋め込むことで,その実行を通じて良好な中間マッチングを維持できるオンライン計量マッチングアルゴリズムを用いて,Follow-the-Predictionフレームワークを擬似設定に拡張する。 理論的結果を実証的評価で補完し,本手法の有効性を実証する。

関連論文リスト

• Prediction-Specific Design of Learning-Augmented Algorithms [10.918779264590297]
  予測固有の性能基準は、一貫性と堅牢性という粗い概念よりも大きな性能改善を可能にすることを示す。 我々は,強最適化アルゴリズムを体系的に設計できる汎用的な二段階最適化フレームワークを開発した。 この結果から,予測固有で強い最適化アルゴリズムは,様々なオンライン意思決定環境における性能を著しく向上させることができることが示された。
  論文  参考訳（メタデータ） (2025-10-16T17:06:53Z)
• Algorithms with Calibrated Machine Learning Predictions [9.18151868060576]
  予測を伴うアルゴリズムの分野は、リアルタイムのパフォーマンスを改善するためのオンラインアルゴリズムの設計に機械学習のアドバイスを取り入れている。 既存のアプローチでは、ユーザが総合的な信頼レベルを指定する必要があることが多いが、現代の機械学習モデルは、予測レベルの不確実性を見積もることができる。 このギャップを埋めるための原則的かつ実践的なツールとしてキャリブレーションを提案し、2つのケーススタディを通じてキャリブレーションされたアドバイスの利点を実証する。
  論文  参考訳（メタデータ） (2025-02-05T03:41:18Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  既存の不確実性推定アルゴリズムでは、モデルアーキテクチャとトレーニング手順を変更する必要がある。 本研究では、与えられたトレーニングされたニューラルネットワークに適用し、近似予測間隔を生成できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:18:31Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)

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

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