論文の概要: Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints
- arxiv url: http://arxiv.org/abs/2408.07831v2
- Date: Wed, 12 Mar 2025 22:56:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-14 21:36:22.284384
- Title: Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints
- Title（参考訳）: デッドライン制約付き時空間オンラインアロケーションのための学習強化競合アルゴリズム
- Authors: Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy,
- Abstract要約: 我々は,サステナビリティとエネルギの新たな課題によって動機付けられた,新たなオンライン問題を紹介し,研究する。
オンラインプレーヤーは$mathsfSOADで、ポイント当たりのメートル法空間$(, d) にアロケートしてスケジューリングすることで、ワークロードを完了します。
各時点において、各時点における作業負荷のコストを表すサービスコスト関数が明らかにされ、プレーヤは、現在の作業のポイントへの割り当てを不当に決定しなければならない。
- 参考スコア（独自算出の注目度）: 11.029788598491077
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce and study spatiotemporal online allocation with deadline constraints ($\mathsf{SOAD}$), a new online problem motivated by emerging challenges in sustainability and energy. In $\mathsf{SOAD}$, an online player completes a workload by allocating and scheduling it on the points of a metric space $(X, d)$ while subject to a deadline $T$. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metric $d(\cdot, \ \cdot)$ that captures, e.g., an overhead cost. $\mathsf{SOAD}$ formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for $\mathsf{SOAD}$ along with a matching lower bound establishing its optimality. Our main algorithm, \textsc{ST-CLIP}, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that \textsc{ST-CLIP} substantially improves on heuristic baseline methods.
- Abstract（参考訳）: 本稿では,持続可能性とエネルギーの新たな課題に起因した新たなオンライン問題である期限制約付き時空間オンラインアロケーション(\mathsf{SOAD}$)を紹介し,研究する。
オンラインプレーヤーは、$\mathsf{SOAD}$で、納期$T$を条件として、計量空間$(X, d)$のポイントにアロケートしてスケジューリングすることで、ワークロードを完了する。
各タイムステップにおいて、各ポイントでの作業負荷を処理するコストを表すサービスコスト関数が明らかにされ、プレーヤは、現在の作業のポイントへの割り当てを不当に決定しなければならない。
プレイヤーがこのアロケーションを移動したときには、移動コストが$d(\cdot, \ \cdot)$で定義される。
$\mathsf{SOAD}$は、オンラインアルゴリズムの文献における一般的なメトリクスと期限制約を組み合わせたオープンな問題を公式化し、メトリックタスクシステムやオンライン検索のような問題を統一する。
我々は,$\mathsf{SOAD}$に対する競争的アルゴリズムと,その最適性を確立するための一致した下界を提案する。
我々の主アルゴリズムである‘textsc{ST-CLIP} は、予測(例えば、関連するコストの予測)を活かし、最適整合性-損益性トレードオフを実現する学習強化アルゴリズムである。
提案アルゴリズムは, 分散データセンターネットワーク上での遅延耐性バッチ計算ジョブをスケジューリングする, 持続可能なコンピューティングアプリケーションである, 炭素対応時空間負荷管理のシミュレーションケーススタディで評価する。
これらの実験では, ヒューリスティックベースライン法において, <textsc{ST-CLIP} が大幅に改善されることが示されている。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
各ラウンドにおいて、各エージェント$i$は、オンラインの方法で、強い凸打撃コスト関数$fi_t$を受け取る。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳（メタデータ） (2024-11-13T05:59:04Z) - Contractual Reinforcement Learning: Pulling Arms with Invisible Hands [68.77645200579181]
本稿では,契約設計によるオンライン学習問題において,利害関係者の経済的利益を整合させる理論的枠組みを提案する。
計画問題に対して、遠目エージェントに対する最適契約を決定するための効率的な動的プログラミングアルゴリズムを設計する。
学習問題に対して,契約の堅牢な設計から探索と搾取のバランスに至るまでの課題を解き放つために,非回帰学習アルゴリズムの汎用設計を導入する。
論文 参考訳（メタデータ） (2024-07-01T16:53:00Z) - On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
我々は,100万ドル以上の分散データを用いたオンラインモデル選択について検討し,クライアント間のコラボレーションの必要性について検討する。
i) クライアント上の計算コストが$o(K)$に制限された場合, (ii) クライアント上での計算制約がない場合, (i) 協調は不要であり, (ii) クライアント上での計算コストは$o(K)$に制限される。
論文 参考訳（メタデータ） (2024-04-15T06:32:28Z) - LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand [1.423958951481749]
本稿では,未知の作業時間(OCSU)を用いたオンラインCO_2-Awareリソーススケーリング問題について検討する。
我々は,論理的に堅牢な学習拡張アルゴリズムであるLACSを提案し,OCSUを解く。
LACSは、納期を意識した炭素に依存しない作業と比較して、炭素フットプリントの32%の削減を実現している。
論文 参考訳（メタデータ） (2024-03-29T04:54:22Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。
本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。
そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
論文 参考訳（メタデータ） (2023-10-31T16:34:49Z) - A Schedule of Duties in the Cloud Space Using a Modified Salp Swarm
Algorithm [0.0]
クラウド領域で最も重要なNPハード問題のひとつはスケジューリングです。
Salp Swarm Algorithm (SSA)と呼ばれる集団知能アルゴリズムの1つが拡張され、改良され、適用された。
その結果,本アルゴリズムは一般に他のアルゴリズムよりも高い性能を示した。
論文 参考訳（メタデータ） (2023-09-18T02:48:41Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - TransPath: Learning Heuristics For Grid-Based Pathfinding via
Transformers [64.88759709443819]
探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。
私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。
第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
論文 参考訳（メタデータ） (2022-12-22T14:26:11Z) - Movement Penalized Bayesian Optimization with Application to Wind Energy
Systems [84.7485307269572]
文脈ベイズ最適化(CBO)は、与えられた側情報を逐次決定する強力なフレームワークである。
この設定では、学習者は各ラウンドでコンテキスト(天気条件など)を受け取り、アクション(タービンパラメータなど)を選択する必要がある。
標準的なアルゴリズムは、すべてのラウンドで意思決定を切り替えるコストを前提としませんが、多くの実用的なアプリケーションでは、このような変更に関連するコストが最小化されるべきです。
論文 参考訳（メタデータ） (2022-10-14T20:19:32Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Learning to Schedule [3.5408022972081685]
本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。
各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
論文 参考訳（メタデータ） (2021-05-28T08:04:06Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z) - APMSqueeze: A Communication Efficient Adam-Preconditioned Momentum SGD
Algorithm [39.110478306078974]
AdamはBERTやImageNetといった多くの重要なタスクをトレーニングするための効率性と正確性を保証する重要な最適化アルゴリズムである。
本稿では,bf ADAM bfプレコンディション付きbf Momentum SGDアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-26T02:20:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。