論文の概要: Static Scheduling with Predictions Learned through Efficient Exploration

• arxiv url: http://arxiv.org/abs/2205.15695v1
• Date: Tue, 31 May 2022 11:19:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-01 12:50:38.360776
• Title: Static Scheduling with Predictions Learned through Efficient Exploration
• Title（参考訳）: 効率的な探索による予測による静的スケジューリング
• Authors: Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, Vianney Perchet
• Abstract要約: オンラインアルゴリズムの最悪のケース分析を超えて、一般的なアプローチは、パフォーマンスを改善するために活用できる予測の存在を仮定することである。 信頼できる予測は、実行中にアルゴリズムによって構築できる、と私たちは主張する。 対照的に、期待されるジョブサイズが分かっている場合、この情報を利用する最良のアルゴリズムであるFollow-The-Perfect-Predictionは、はるかに優れたパフォーマンスを示す。
• 参考スコア（独自算出の注目度）: 15.075691719756877
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A popular approach to go beyond the worst-case analysis of online algorithms is to assume the existence of predictions that can be leveraged to improve performances. Those predictions are usually given by some external sources that cannot be fully trusted. Instead, we argue that trustful predictions can be built by algorithms, while they run. We investigate this idea in the illustrative context of static scheduling with exponential job sizes. Indeed, we prove that algorithms agnostic to this structure do not perform better than in the worst case. In contrast, when the expected job sizes are known, we show that the best algorithm using this information, called Follow-The-Perfect-Prediction (FTPP), exhibits much better performances. Then, we introduce two adaptive explore-then-commit types of algorithms: they both first (partially) learn expected job sizes and then follow FTPP once their self-predictions are confident enough. On the one hand, ETCU explores in "series", by completing jobs sequentially to acquire information. On the other hand, ETCRR, inspired by the optimal worst-case algorithm Round-Robin (RR), explores efficiently in "parallel". We prove that both of them asymptotically reach the performances of FTPP, with a faster rate for ETCRR. Those findings are empirically evaluated on synthetic data.
• Abstract（参考訳）: オンラインアルゴリズムの最悪のケース解析を超越する一般的なアプローチは、パフォーマンスを改善するために活用できる予測の存在を仮定することです。 これらの予測は通常、完全に信頼できない外部ソースによって与えられる。 その代わり、信頼できる予測は、実行中にアルゴリズムによって構築できると主張する。 指数関数的なジョブサイズを持つ静的スケジューリングの例示的文脈で,この概念を考察する。 実際、この構造に非依存なアルゴリズムは最悪の場合よりも性能が良くないことを示す。 対照的に、期待されるジョブサイズが分かっている場合、この情報を利用する最良のアルゴリズムであるFollow-The-Perfect-Prediction (FTPP)は、はるかに優れたパフォーマンスを示す。 次に,2つの適応型探索型アルゴリズムを導入する。2つのアルゴリズムは,それぞれが(部分的に)期待されるジョブサイズを学習し,自己予測が十分に自信があればftppをフォローする。 一方、ETCUは「シリーズ」を探索し、連続的に仕事を完了して情報を取得する。 一方、最短ケースアルゴリズムであるラウンドロビン(RR)にインスパイアされたETCRRは、「並列」を効率的に探索する。 ETCRRよりも速い速度でFTPPの性能に漸近的に到達することが証明された。 これらの結果は合成データで実証的に評価される。

関連論文リスト

• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Multi-task Bias-Variance Trade-off Through Functional Constraints [102.64082402388192]
  マルチタスク学習は、多様なタスクによく機能する関数の集合を取得することを目的としている。 本稿では,2つの極端な学習シナリオ,すなわちすべてのタスクに対する単一関数と,他のタスクを無視するタスク固有関数から直感を抽出する。 本稿では,集中関数に対するドメイン固有解を強制する制約付き学習定式化を導入する。
  論文  参考訳（メタデータ） (2022-10-27T16:06:47Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Metalearning Linear Bandits by Prior Update [7.519872646378836]
  完全なベイズ的アプローチは、問題のパラメータは既知の事前から生成されると仮定するが、実際にはそのような情報は欠落することが多い。 この問題は、ある部分的な情報を持つ意思決定設定において悪化し、不特定事前の使用は、探索の質が悪く、性能が劣る可能性がある。 この研究において、線形帯域幅とガウス事前の文脈において、事前推定が真の事前に十分近い限り、不特定事前を用いたアルゴリズムの性能は真の先行を用いたアルゴリズムのそれに近いことを証明した。
  論文  参考訳（メタデータ） (2021-07-12T11:17:01Z)
• Learning to Schedule [3.5408022972081685]
  本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。 各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
  論文  参考訳（メタデータ） (2021-05-28T08:04:06Z)
• Discriminative, Generative and Self-Supervised Approaches for Target-Agnostic Learning [8.666667951130892]
  生成的および自己教師型学習モデルは、そのタスクでうまく機能することが示されている。 擬似相似理論の導出した定理は、結合分布モデルの推定に関係があることも示している。
  論文  参考訳（メタデータ） (2020-11-12T15:03:40Z)
• Temporally Correlated Task Scheduling for Sequence Learning [143.70523777803723]
  多くのアプリケーションにおいて、シーケンス学習タスクは通常、複数の時間的に相関した補助タスクと関連付けられている。 シーケンス学習に学習可能なスケジューラを導入し、トレーニングのための補助的なタスクを適応的に選択できる。 本手法は,同時翻訳とストックトレンド予測の性能を著しく向上させる。
  論文  参考訳（メタデータ） (2020-07-10T10:28:54Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Sequence-to-sequence models for workload interference [1.988145627448243]
  データセンターでのジョブのスケジューリングは難しいシナリオであり、ジョブは厳しいスローダウンや実行の失敗につながるリソースを競うことができる。 現在のテクニックは、多くが機械学習とジョブモデリングを含むもので、時間にわたってワークロードの振る舞いを要約に基づいている。 本稿では,リソースや実行時間に対する行動に基づいて,データセンタ上でのジョブの協調スケジューリングをモデル化する手法を提案する。
  論文  参考訳（メタデータ） (2020-06-25T14:11:46Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  逐次データによる曖昧な予測を扱うために,Multiple hypothesis Prediction(MHP)モデルの拡張を提案する。 また、不確実性を考慮するのに適した曖昧な問題に対する新しい尺度も導入する。
  論文  参考訳（メタデータ） (2020-03-10T09:15:42Z)

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

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