論文の概要: Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks

• arxiv url: http://arxiv.org/abs/2408.16215v1
• Date: Thu, 29 Aug 2024 02:18:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-30 15:15:25.370242
• Title: Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks
• Title（参考訳）: 帯域フィードバックに基づく適応型ネットワーク最適化:非定常マルチホップネットワークにおけるユーティリティの最大化
• Authors: Yan Dai, Longbo Huang,
• Abstract要約: 古典的なSNOアルゴリズムでは、ネットワーク条件は時間とともに定常である必要がある。 これらの問題に触発され、我々は帯域幅のフィードバックの下でAdversarial Network Optimization (ANO) を検討する。 提案するUMO2アルゴリズムは,ネットワークの安定性を保証し,また,「微妙に変化する」参照ポリシーの実用性に適合する。
• 参考スコア（独自算出の注目度）: 35.78834550608041
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic Network Optimization (SNO) concerns scheduling in stochastic queueing systems. It has been widely studied in network theory. Classical SNO algorithms require network conditions to be stationary with time, which fails to capture the non-stationary components in many real-world scenarios. Many existing algorithms also assume knowledge of network conditions before decision, which rules out applications where unpredictability presents. Motivated by these issues, we consider Adversarial Network Optimization (ANO) under bandit feedback. Specifically, we consider the task of *i)* maximizing some unknown and time-varying utility function associated to scheduler's actions, where *ii)* the underlying network is a non-stationary multi-hop one whose conditions change arbitrarily with time, and *iii)* only bandit feedback (effect of actually deployed actions) is revealed after decisions. Our proposed `UMO2` algorithm ensures network stability and also matches the utility maximization performance of any "mildly varying" reference policy up to a polynomially decaying gap. To our knowledge, no previous ANO algorithm handled multi-hop networks or achieved utility guarantees under bandit feedback, whereas ours can do both. Technically, our method builds upon a novel integration of online learning into Lyapunov analyses: To handle complex inter-dependencies among queues in multi-hop networks, we propose meticulous techniques to balance online learning and Lyapunov arguments. To tackle the learning obstacles due to potentially unbounded queue sizes, we design a new online linear optimization algorithm that automatically adapts to loss magnitudes. To maximize utility, we propose a bandit convex optimization algorithm with novel queue-dependent learning rate scheduling that suites drastically varying queue lengths. Our new insights in online learning can be of independent interest.
• Abstract（参考訳）: 確率的ネットワーク最適化(SNO)は確率的キューシステムにおけるスケジューリングに関するものである。 ネットワーク理論で広く研究されている。 古典的なSNOアルゴリズムは、ネットワーク条件を時間とともに定常的に要求するが、実世界の多くのシナリオにおいて静止しないコンポーネントを捕捉することができない。 多くの既存のアルゴリズムは、決定の前にネットワーク条件の知識を前提としており、予測不可能なアプリケーションを制御する。 これらの問題に触発され、我々は帯域幅のフィードバックの下でAdversarial Network Optimization (ANO) を検討する。 具体的には、*i)* のタスクをスケジューラの動作に関連する未知かつ時間変化のあるユーティリティ関数を最大化する、*ii)* 基礎となるネットワークは、時間とともに条件が任意に変化する非定常マルチホップであり、*iii)* バンドフィードバック(実際にデプロイされたアクションの影響)のみが決定後に明らかにされる、と考える。 提案したUMO2アルゴリズムは,ネットワークの安定性を保証し,多項式的に減衰するギャップまでの「最小変化」参照ポリシーの効用最大化性能と一致させる。 我々の知る限りでは、従来のANOアルゴリズムはマルチホップネットワークを処理したり、バンディットフィードバックの下でユーティリティ保証を達成できたりはしませんが、どちらも可能です。 マルチホップネットワークにおける待ち行列間の複雑な依存性を扱うために,オンライン学習とリアプノフの議論のバランスをとるための巧妙な手法を提案する。 潜在的に非有界な待ち行列サイズによる学習障害に対処するために,損失の大きさに自動的に適応するオンライン線形最適化アルゴリズムを設計する。 有効性を最大化するために,待ち行列に依存する新しい学習率スケジューリングを用いた帯域凸最適化アルゴリズムを提案する。 オンライン学習における私たちの新しい洞察は、独立した関心を持つことができます。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
  通信遅延によるネットワークの分散最適化問題を考察する。 そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。 通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。
  論文  参考訳（メタデータ） (2024-05-29T20:51:38Z)
• Optimization Guarantees of Unfolded ISTA and ADMM Networks With Smooth Soft-Thresholding [57.71603937699949]
  我々は,学習エポックの数の増加とともに,ほぼゼロに近いトレーニング損失を達成するための最適化保証について検討した。 トレーニングサンプル数に対する閾値は,ネットワーク幅の増加とともに増加することを示す。
  論文  参考訳（メタデータ） (2023-09-12T13:03:47Z)
• Learning Optimal Admission Control in Partially Observable Queueing Networks [4.254099382808599]
  本稿では、部分的に観測可能な待ち行列ネットワークにおいて、最適入場制御ポリシーを学習する効率的な強化学習アルゴリズムを提案する。 我々のアルゴリズムは、ネットワーク内のジョブの最大数のみにサブラインナリーに依存していることを後悔している。
  論文  参考訳（メタデータ） (2023-08-04T15:40:23Z)
• Neural Quantile Optimization for Edge-Cloud Networking [13.509945075582447]
  我々は,バースト可能な請求書に基づいて制約を満足し,コストを最小化するエッジ・クラウド・コンピューティング・ネットワークにおいて,最適なトラフィック割当方式を模索する。 本稿では,教師なし学習による最適化問題を解決するため,Gumbel-softmaxサンプリングネットワークを提案する。 トレーニングされたネットワークは、効率的なトラフィック割当スキームサンプリングとして機能し、実現可能性およびコスト関数値のランダム戦略を著しく上回る。
  論文  参考訳（メタデータ） (2023-07-11T11:05:10Z)
• Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
  K$キューからなるワンホップ単一サーバキューシステムについて検討する。 我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。 ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-03T07:17:09Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  本稿では,リアルタイムフィードバックに基づいてシードノードを逐次活性化する,コンテンツ依存型オンライン影響問題の適応バージョンについて検討する。 提案アルゴリズムは,最適政策を楽観的に改善しつつ,ネットワークモデルの推定を保守し,適応的にシードを選択する。
  論文  参考訳（メタデータ） (2022-06-29T18:17:28Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• Deep Multi-Task Learning for Cooperative NOMA: System Design and Principles [52.79089414630366]
  我々は,近年のディープラーニング(DL)の進歩を反映した,新しいディープ・コラボレーティブなNOMAスキームを開発する。 我々は,システム全体を包括的に最適化できるように,新しいハイブリッドカスケードディープニューラルネットワーク(DNN)アーキテクチャを開発した。
  論文  参考訳（メタデータ） (2020-07-27T12:38:37Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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