論文の概要: Improved algorithms for online load balancing

• arxiv url: http://arxiv.org/abs/2007.07515v2
• Date: Tue, 21 Jul 2020 00:43:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 06:29:19.945432
• Title: Improved algorithms for online load balancing
• Title（参考訳）: オンライン負荷分散のための改良アルゴリズム
• Authors: Yaxiong Liu, Kohei Hatano, Eiji Takimoto
• Abstract要約: オンラインロードバランシング問題とその拡張をゲーム繰り返しのフレームワークで検討する。 プレイヤーのコストは累積計算時間ベクトルのノルムによって測定される。 ゴールは、後ろ向きの最高の固定分布のコストに対してプレイヤーのコストを最小化することである。
• 参考スコア（独自算出の注目度）: 0.6875312133832078
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an online load balancing problem and its extensions in the framework of repeated games. On each round, the player chooses a distribution (task allocation) over $K$ servers, and then the environment reveals the load of each server, which determines the computation time of each server for processing the task assigned. After all rounds, the cost of the player is measured by some norm of the cumulative computation-time vector. The cost is the makespan if the norm is $L_\infty$-norm. The goal is to minimize the regret, i.e., minimizing the player's cost relative to the cost of the best fixed distribution in hindsight. We propose algorithms for general norms and prove their regret bounds. In particular, for $L_\infty$-norm, our regret bound matches the best known bound and the proposed algorithm runs in polynomial time per trial involving linear programming and second order programming, whereas no polynomial time algorithm was previously known to achieve the bound.
• Abstract（参考訳）: オンラインロードバランシング問題とその拡張をゲーム繰り返しのフレームワークで検討する。 各ラウンドにおいて、プレイヤーは$k$サーバー以上の分散(タスク割り当て)を選択し、環境が各サーバの負荷を明らかにし、割り当てられたタスクを処理する各サーバの計算時間を決定する。 すべてのラウンドの後、プレイヤーのコストは累積計算時間ベクトルのノルムによって測定される。 コストは、ノルムが$l_\infty$-normである場合のmakespanである。 ゴールは、後方で最高の固定分布のコストに対してプレイヤーのコストを最小化すること、すなわち、後悔を最小限に抑えることである。 一般規範に対するアルゴリズムを提案し,その後悔の限界を証明する。 特に、$l_\infty$-norm に対して、我々の後悔のバウンドは最もよく知られたバウンドと一致し、提案されたアルゴリズムは、線形計画と二階計画を含む試行ごとに多項式時間で実行される。

関連論文リスト

• CarbonClipper: Optimal Algorithms for Carbon-Aware Spatiotemporal Workload Management [11.029788598491077]
  炭素を意識したワークロード管理は、データセンターの環境への影響の増大に対処しようとしている。 MathsfSOAD$は、オンラインアルゴリズムにおける一般的なメトリクスと期限制約を組み合わせたオープンな問題を公式化する。 rm Cscriptsize ARCscriptsize LIPPER$は、予測の利点を生かした学習強化アルゴリズムである。
  論文  参考訳（メタデータ） (2024-08-14T22:08:06Z)
• Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost [12.783783498844022]
  オンラインの非最適化問題は、一連のサーバのフロータイム(トータル遅延)を目標とする。 各処理は、アクティブサーバ数の変更に伴うコストを最小限に抑えるために、任意の時間で処理できる。
  論文  参考訳（メタデータ） (2024-03-26T08:22:09Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。 我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
  論文  参考訳（メタデータ） (2020-12-17T04:56:51Z)
• Continuous-Time Multi-Armed Bandits with Controlled Restarts [32.63624728528415]
  時間制約決定過程に対する再起動制御による帯域幅問題について検討する。 特に、各決定がランダムな完了時間を要し、最後にランダムで相関した報酬が得られるような帯域設定を考える。 我々は,再起動戦略の有限かつ連続的な行動空間において,$O(log(tau))$と$O(sqrttaulog(tau))$後悔を用いて効率的なオンライン学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-30T19:50:39Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)

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

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