論文の概要: Gradient and Projection Free Distributed Online Min-Max Resource
Optimization
- arxiv url: http://arxiv.org/abs/2112.03896v1
- Date: Tue, 7 Dec 2021 18:42:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-08 16:07:44.160540
- Title: Gradient and Projection Free Distributed Online Min-Max Resource
Optimization
- Title(参考訳): 勾配・投影自由分散オンラインmin-maxリソース最適化
- Authors: Jingrong Wang and Ben Liang
- Abstract要約: パラレルエージェントとパラメータサーバを組み合わせた分散オンラインmin-maxリソース割り当てについて検討する。
本研究では、分散オンラインリソース再割り当て(DORA)と呼ばれる新しいオンラインアルゴリズムを提案し、非ストラグラーはリソースを放棄し、ストラグラーとリソースを共有することを学習する。
- 参考スコア(独自算出の注目度): 33.98662563413433
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider distributed online min-max resource allocation with a set of
parallel agents and a parameter server. Our goal is to minimize the pointwise
maximum over a set of time-varying convex and decreasing cost functions,
without a priori information about these functions. We propose a novel online
algorithm, termed Distributed Online resource Re-Allocation (DORA), where
non-stragglers learn to relinquish resource and share resource with stragglers.
A notable feature of DORA is that it does not require gradient calculation or
projection operation, unlike most existing online optimization strategies. This
allows it to substantially reduce the computation overhead in large-scale and
distributed networks. We show that the dynamic regret of the proposed algorithm
is upper bounded by $O\left(T^{\frac{3}{4}}(1+P_T)^{\frac{1}{4}}\right)$, where
$T$ is the total number of rounds and $P_T$ is the path-length of the
instantaneous minimizers. We further consider an application to the bandwidth
allocation problem in distributed online machine learning. Our numerical study
demonstrates the efficacy of the proposed solution and its performance
advantage over gradient- and/or projection-based resource allocation algorithms
in reducing wall-clock time.
- Abstract(参考訳): 分散オンラインmin-maxリソース割り当てを並列エージェントとパラメータサーバのセットで検討する。
我々のゴールは、これらの関数に関する事前情報なしで、時間変動凸の集合に対するポイントワイドな最大値とコスト関数の減少を最小化することである。
本研究では,非ストラグラーが資源を放棄し,資源をストラグラーと共有することを学ぶ,分散オンラインリソース再配置(dora)と呼ばれる新しいオンラインアルゴリズムを提案する。
DORAの注目すべき特徴は、既存のオンライン最適化戦略とは異なり、勾配計算や投射操作を必要としないことである。
これにより、大規模および分散ネットワークにおける計算オーバーヘッドを大幅に削減できる。
提案アルゴリズムの動的後悔は、$O\left(T^{\frac{3}{4}}(1+P_T)^{\frac{1}{4}}\right)$で上界し、$T$はラウンドの総数、$P_T$は即時最小化器のパス長であることを示す。
さらに,分散オンライン機械学習における帯域幅割り当て問題への応用を検討する。
本研究は,提案手法の有効性と,壁面時間短縮のための勾配および/または投影に基づく資源配分アルゴリズムに対する性能上の優位性を示す。
関連論文リスト
- Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳(メタデータ) (2023-09-16T07:30:12Z) - Oracle-Efficient Smoothed Online Learning for Piecewise Continuous
Decision Making [91.89643024162973]
この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。
次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
論文 参考訳(メタデータ) (2023-02-10T18:45:52Z) - Teal: Learning-Accelerated Optimization of WAN Traffic Engineering [89.23404108080585]
本稿では,GPUの並列処理能力を活用してTE制御を高速化する学習型TEアルゴリズムTealを提案する。
問題スケールの削減と学習のトラクタビリティ向上のために,Tealはマルチエージェント強化学習(RL)アルゴリズムを用いて,各トラフィック要求を独立に割り当てる。
他のTE加速方式と比較して、Tealは需要を6~32%増やし、197~625倍のスピードアップを達成している。
論文 参考訳(メタデータ) (2022-10-25T04:46:30Z) - Unsupervised Optimal Power Flow Using Graph Neural Networks [172.33624307594158]
グラフニューラルネットワークを用いて、要求された電力と対応するアロケーションとの間の非線形パラメトリゼーションを学習する。
シミュレーションを通して、この教師なし学習コンテキストにおけるGNNの使用は、標準解法に匹敵するソリューションにつながることを示す。
論文 参考訳(メタデータ) (2022-10-17T17:30:09Z) - Optimal Resource Allocation for Serverless Queries [8.59568779761598]
以前の作業では、リソース割り当てと実行時の積極的なトレードオフを無視しながら、ピークアロケーションの予測に重点を置いていた。
本稿では,新しいクエリと過去のクエリの両方に対して,アグレッシブなトレードオフでパフォーマンスを予測できる最適なリソース割り当てシステムを提案する。
論文 参考訳(メタデータ) (2021-07-19T02:55:48Z) - Energy Efficient Edge Computing: When Lyapunov Meets Distributed
Reinforcement Learning [12.845204986571053]
本研究では,エッジコンピューティングによるエネルギー効率のよいオフロード問題について検討する。
考慮されたシナリオでは、複数のユーザが同時に無線およびエッジコンピューティングリソースを競う。
提案されたソリューションは、ベンチマークアプローチと比較してネットワークのエネルギー効率を高めることもできます。
論文 参考訳(メタデータ) (2021-03-31T11:02:29Z) - Distributed Learning and Democratic Embeddings: Polynomial-Time Source
Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient
Descent under Communication Constraints [46.17631511884969]
我々は、n次元ユークリッド空間においてベクトルを圧縮する問題を考える。
数値化器の被覆効率が次元独立であるか、あるいは非常に弱い対数依存であるという意味では、民主主義的および民主的に近いソースコーディングスキームが(ほぼ)最適であることを示す。
分散最適化アルゴリズムDGD-DEFを提案する。このアルゴリズムは,提案した符号化戦略を用いて,(ほぼ)定数要素内における最小収束率を実現する。
論文 参考訳(メタデータ) (2021-03-13T00:04:11Z) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。
様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。
我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
論文 参考訳(メタデータ) (2020-11-18T18:39:17Z) - Coordinated Online Learning for Multi-Agent Systems with Coupled
Constraints and Perturbed Utility Observations [91.02019381927236]
本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。
提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
論文 参考訳(メタデータ) (2020-10-21T10:11:17Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-27T17:38:51Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳(メタデータ) (2020-07-01T14:24:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。