論文の概要: Learning-Augmented Algorithms with Explicit Predictors

• arxiv url: http://arxiv.org/abs/2403.07413v1
• Date: Tue, 12 Mar 2024 08:40:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 22:23:08.039346
• Title: Learning-Augmented Algorithms with Explicit Predictors
• Title（参考訳）: 明示的予測器を用いた学習強化アルゴリズム
• Authors: Marek Elias and Haim Kaplan and Yishay Mansour and Shay Moran
• Abstract要約: アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
• 参考スコア（独自算出の注目度）: 67.02156211760415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper we focus on online problems; prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box (to get the predictions it was trained for). In contrast, in this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor to learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we focus on a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems we consider, we introduce new algorithms that take advantage of explicit learning algorithms which we carefully design towards optimizing the overall performance. We demonstrate the potential of our approach by deriving performance bounds which improve over those established in previous work.
• Abstract（参考訳）: アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 これらのアプローチは、予測が正確である場合のパフォーマンスの向上を実証するとともに、予測が失敗する場合の最悪の保証を提供することによって堅牢性を確保する。 本稿では,オンライン問題に焦点をあてる。この文脈における先行研究は,過去のデータに基づいて予測器を事前訓練し,ブラックボックスとして(トレーニング対象の予測を得るために)使用するパラダイムに焦点をあてた。 対照的に、本研究では、予測器を解き放ち、アルゴリズムの課題の中でそれらが生み出す学習問題を統合する。 特に、予測者が入力のより大きな部分を受信して学習できるようにし、目前にあるアルゴリズムに特化されたオンライン学習アルゴリズムを設計するという究極の目標を掲げる。 この観点から、ブラックボックス設定でよく研究されているキャッシュやスケジューリングなど、いくつかの基本的な問題に焦点を当てる。 検討する各問題に対して,明示的な学習アルゴリズムを活用するアルゴリズムを導入し,全体的な性能の最適化に向けて慎重に設計する。 従来の作業で確立されたものよりも改善された性能境界を導出することで、我々のアプローチの可能性を示す。

関連論文リスト

• Structured Prediction in Online Learning [66.36004256710824]
  オンライン学習環境における構造化予測のための理論的・アルゴリズム的枠組みについて検討する。 このアルゴリズムは教師付き学習環境からの最適アルゴリズムの一般化であることを示す。 本稿では,非定常データ分布,特に逆データを含む2番目のアルゴリズムについて考察する。
  論文  参考訳（メタデータ） (2024-06-18T07:45:02Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• 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)

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

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