Fugu-MT 論文翻訳(概要): The Primal-Dual method for Learning Augmented Algorithms

論文の概要: The Primal-Dual method for Learning Augmented Algorithms

arxiv url: http://arxiv.org/abs/2010.11632v1
Date: Thu, 22 Oct 2020 11:58:47 GMT
ステータス: 処理完了
システム内更新日: 2022-10-04 08:10:58.028953
Title: The Primal-Dual method for Learning Augmented Algorithms
Title（参考訳）: 拡張アルゴリズム学習のための原始双対法
Authors: \'Etienne Bamas, Andreas Maggiori, Ola Svensson
Abstract要約: 我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
参考スコア（独自算出の注目度）: 10.2730668356857
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.
Abstract（参考訳）: 予測を備えた従来のオンラインアルゴリズムの拡張は、新しい活発な研究領域である。本稿では,オンラインアルゴリズムが行う次のアクションについて助言する予測を組み込むために,オンラインアルゴリズムの原始二重法を拡張した。このフレームワークを用いて、様々なオンライン被覆問題に対する新しいアルゴリズムを得る。これらのアルゴリズムは,予測が正確でありながら,予測が誤解を招く場合に適切な保証を維持しながら,任意のオンラインアルゴリズムよりも優れていることを示す。

関連論文リスト

Improving Online Algorithms via ML Predictions [19.03466073202238]
我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
論文参考訳（メタデータ） (2024-07-25T02:17:53Z)
A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
論文参考訳（メタデータ） (2024-06-05T18:39:28Z)
Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文参考訳（メタデータ） (2024-03-12T08:40:21Z)
Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文参考訳（メタデータ） (2022-10-22T12:58:07Z)
Online Algorithms with Multiple Predictions [17.803569868141647]
本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
論文参考訳（メタデータ） (2022-05-08T17:33:01Z)
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)
Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-12-10T10:02:31Z)
Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文参考訳（メタデータ） (2021-03-02T11:04:33Z)
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文参考訳（メタデータ） (2020-10-22T04:51:01Z)

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