論文の概要: Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints
- arxiv url: http://arxiv.org/abs/2305.15558v2
- Date: Wed, 3 Apr 2024 10:45:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 23:37:29.437009
- Title: Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints
- Title（参考訳）: 長期制約を考慮したランダム化ネットワークリソース割り当てのオンライン最適化
- Authors: Ahmed Sid-Ali, Ioannis Lambadaris, Yiqiang Q. Zhao, Gennady Shaikhet, Shima Kheradmand,
- Abstract要約: 簡単な通信網における最適オンラインリソース予約問題について検討する。
そこで我々は,オンラインサドルポイントアルゴリズムを提案し,関連するK-ベンチマークの後悔に対する上限を提示する。
- 参考スコア（独自算出の注目度）: 0.610240618821149
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study an optimal online resource reservation problem in a simple communication network. The network is composed of two compute nodes linked by a local communication link. The system operates in discrete time; at each time slot, the administrator reserves resources for servers before the actual job requests are known. A cost is incurred for the reservations made. Then, after the client requests are observed, jobs may be transferred from one server to the other to best accommodate the demands by incurring an additional transport cost. If certain job requests cannot be satisfied, there is a violation that engenders a cost to pay for each of the blocked jobs. The goal is to minimize the overall reservation cost over finite horizons while maintaining the cumulative violation and transport costs under a certain budget limit. To study this problem, we first formalize it as a repeated game against nature where the reservations are drawn randomly according to a sequence of probability distributions that are derived from an online optimization problem over the space of allowable reservations. We then propose an online saddle-point algorithm for which we present an upper bound for the associated K-benchmark regret together with an upper bound for the cumulative constraint violations. Finally, we present numerical experiments where we compare the performance of our algorithm with those of simple deterministic resource allocation policies.
- Abstract（参考訳）: 本稿では,シンプルな通信ネットワークにおける最適オンラインリソース予約問題について検討する。
ネットワークは、ローカル通信リンクによってリンクされた2つの計算ノードで構成される。
システムは個別の時間で動作し、管理者は各時間帯に、実際のジョブ要求が知られる前に、サーバのリソースを予約する。
予約の費用がかかる。
そして、クライアント要求が観測された後、追加の転送コストを発生させることで、要求に最も適するように、あるサーバから別のサーバにジョブを転送することができる。
特定のジョブ要求が満足できない場合、ブロックされたジョブのそれぞれに支払う費用を負担する違反が発生します。
目標は、一定の予算制限の下で累積的違反と輸送コストを維持しながら、有限地平線上での総予約コストを最小化することである。
そこで本研究では,まず,予約可能な予約空間上のオンライン最適化問題から導出される確率分布の列に基づいて,予約をランダムに描画する自然に対する繰り返しゲームとして定式化する。
次に、オンラインサドルポイントアルゴリズムを提案し、関連するK-ベンチマークの後悔に対する上限と累積制約違反に対する上限を提示する。
最後に,本アルゴリズムの性能を単純な決定論的資源割り当てポリシーと比較する数値実験について述べる。
関連論文リスト
- Autoregressive Policy Optimization for Constrained Allocation Tasks [4.316765170255551]
本稿では,各エンティティのアロケーションを逐次サンプリングする自己回帰プロセスに基づく制約付きアロケーションタスクの新しい手法を提案する。
さらに, 逐次サンプリングによる初期バイアスに対処する新しい脱バイアス機構を提案する。
論文 参考訳（メタデータ） (2024-09-27T13:27:15Z) - A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
顧客に対して順次表示される補完アイテムの動的価格設定の問題に対処する。
各項目の価格を個別に最適化するのは効果がないため、補完項目のコヒーレントな価格ポリシーが不可欠である。
実世界のデータからランダムに生成した合成設定を用いて,我々のアプローチを実証的に評価し,制約違反や後悔の観点からその性能を比較した。
論文 参考訳（メタデータ） (2024-07-08T09:55:31Z) - Exponentially Weighted Algorithm for Online Network Resource Allocation with Long-Term Constraints [0.6466206145151128]
本稿では,ジョブ転送を伴う通信ネットワークにおける最適資源予約問題について検討する。
本稿では,長期制約を含むランダム化指数重み付け法に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-03T10:12:40Z) - 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) - Online Optimization for Network Resource Allocation and Comparison with
Reinforcement Learning Techniques [0.6466206145151128]
本稿では、ジョブ転送におけるオンラインネットワークリソース割り当て問題に取り組む。
本稿では指数重み付け手法に基づくランダム化オンラインアルゴリズムを提案する。
提案アルゴリズムは,その経験からアルゴリズムが適応し,学習していることを示す。
論文 参考訳（メタデータ） (2023-11-16T17:08:27Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳（メタデータ） (2022-09-16T09:38:38Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Scheduling Servers with Stochastic Bilinear Rewards [7.519872646378837]
システム最適化問題は、マルチクラス、マルチサーバキューシステムスケジューリングで発生する。
本稿では,報酬の限界コストを付加した重み付き比例フェアアロケーション基準に基づくスケジューリングアルゴリズムを提案する。
我々のアルゴリズムは,時間的地平線に関して,サブ線形後悔とサブ線形平均保持コスト(および待ち時間境界)を考慮し,待ち行列システムの安定性を保証する。
論文 参考訳（メタデータ） (2021-12-13T00:37:20Z) - Coordinated Online Learning for Multi-Agent Systems with Coupled
Constraints and Perturbed Utility Observations [91.02019381927236]
本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。
提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
論文 参考訳（メタデータ） (2020-10-21T10:11:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。