論文の概要: Learning to Schedule
- arxiv url: http://arxiv.org/abs/2105.13655v1
- Date: Fri, 28 May 2021 08:04:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-31 13:46:30.465879
- Title: Learning to Schedule
- Title（参考訳）: スケジュールの学習
- Authors: Dabeen Lee, Milan Vojnovic
- Abstract要約: 本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。
各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
- 参考スコア（独自算出の注目度）: 3.5408022972081685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes a learning and scheduling algorithm to minimize the
expected cumulative holding cost incurred by jobs, where statistical parameters
defining their individual holding costs are unknown a priori. In each time
slot, the server can process a job while receiving the realized random holding
costs of the jobs remaining in the system. Our algorithm is a learning-based
variant of the $c\mu$ rule for scheduling: it starts with a preemption period
of fixed length which serves as a learning phase, and after accumulating enough
data about individual jobs, it switches to nonpreemptive scheduling mode. The
algorithm is designed to handle instances with large or small gaps in jobs'
parameters and achieves near-optimal performance guarantees. The performance of
our algorithm is captured by its regret, where the benchmark is the minimum
possible cost attained when the statistical parameters of jobs are fully known.
We prove upper bounds on the regret of our algorithm, and we derive a regret
lower bound that is almost matching the proposed upper bounds. Our numerical
results demonstrate the effectiveness of our algorithm and show that our
theoretical regret analysis is nearly tight.
- Abstract（参考訳）: 本稿では,ジョブが蓄積する累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。
各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
アルゴリズムは、スケジューリングのための$c\mu$ルールの学習ベースの変種であり、学習フェーズとして一定の長さのプリエンプション期間から始まり、個々のジョブに関する十分なデータを蓄積した後、非プリエンプティブスケジューリングモードに切り替える。
このアルゴリズムは、ジョブのパラメータの大きなあるいは小さなギャップを持つインスタンスを処理し、ほぼ最適性能を保証するように設計されている。
提案アルゴリズムの性能は,ジョブの統計的パラメータが完全に把握された場合,ベンチマークが最小限のコストで達成されるという,後悔の念に捉えられている。
我々は,アルゴリズムの後悔に対する上限を証明し,提案する上限にほぼ一致する後悔の下限を導出する。
数値解析の結果,提案アルゴリズムの有効性を実証し,理論的後悔分析がほぼ厳密であることを示す。
関連論文リスト
- Constrained Online Two-stage Stochastic Optimization: Algorithm with
(and without) Predictions [19.537289123577022]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳（メタデータ） (2024-01-02T07:46:33Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Reinforcement Learning with Success Induced Task Prioritization [68.8204255655161]
本稿では,自動カリキュラム学習のためのフレームワークであるSuccess induced Task Prioritization (SITP)を紹介する。
アルゴリズムはエージェントに最速の学習を提供するタスクの順序を選択する。
我々は,SITPが他のカリキュラム設計手法と一致するか,あるいは上回っていることを実証する。
論文 参考訳（メタデータ） (2022-12-30T12:32:43Z) - Stochastic Direct Search Method for Blind Resource Allocation [6.574808513848414]
線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
論文 参考訳（メタデータ） (2022-10-11T07:40:45Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Metalearning Linear Bandits by Prior Update [7.519872646378836]
完全なベイズ的アプローチは、問題のパラメータは既知の事前から生成されると仮定するが、実際にはそのような情報は欠落することが多い。
この問題は、ある部分的な情報を持つ意思決定設定において悪化し、不特定事前の使用は、探索の質が悪く、性能が劣る可能性がある。
この研究において、線形帯域幅とガウス事前の文脈において、事前推定が真の事前に十分近い限り、不特定事前を用いたアルゴリズムの性能は真の先行を用いたアルゴリズムのそれに近いことを証明した。
論文 参考訳（メタデータ） (2021-07-12T11:17:01Z) - Non-Parametric Stochastic Sequential Assignment With Random Arrival
Times [3.871148938060281]
ジョブがランダムに到着し、ランダムな値を仮定する問題を考える。
本稿では,NPSA(Non-Parametric Sequential Allocation)アルゴリズムを提案する。
NPSAアルゴリズムによって返される期待報酬は、M$が大きくなるにつれて、最適性に収束することを示す。
論文 参考訳（メタデータ） (2021-06-09T09:41:38Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。