論文の概要: Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency

• arxiv url: http://arxiv.org/abs/2502.05028v1
• Date: Fri, 07 Feb 2025 15:57:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-10 14:55:04.178379
• Title: Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency
• Title（参考訳）: 多エージェント部分モジュラコーディネートのための準最適オンライン学習:タイト近似と通信効率
• Authors: Qixin Zhang, Zongqi Wan, Yu Yang, Li Shen, Dacheng Tao,
• Abstract要約: 離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
• 参考スコア（独自算出の注目度）: 52.60557300927007
• License:
• Abstract: Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications in machine learning, robot planning and control. The existing approaches, such as the OSG algorithm, are often hindered by their poor approximation guarantees and the rigid requirement for a fully connected communication graph. To address these challenges, we firstly present a $\textbf{MA-OSMA}$ algorithm, which employs the multi-linear extension to transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, $\textbf{MA-OSMA}$ leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations in $\textbf{MA-OSMA}$, we also introduce a projection-free $\textbf{MA-OSEA}$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms achieve a regret bound of $\widetilde{O}(\sqrt{\frac{C_{T}T}{1-\beta}})$ against a $(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximizer sequence, $\beta$ is the spectral gap of the network and $c$ is the joint curvature of submodular objectives. This result significantly improves the $(\frac{1}{1+c})$-approximation provided by the state-of-the-art OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-based multi-target tracking.
• Abstract（参考訳）: 予測不可能な環境で、複数のエージェントを協調してサブモジュール関数を最大化する調整は、機械学習、ロボット計画、制御において多くの応用において重要な課題である。 OSGアルゴリズムのような既存のアプローチは、その近似保証の貧弱さと、完全に接続された通信グラフの厳密な要求によって、しばしば妨げられる。 これらの課題に対処するために、まず、離散的な部分モジュラー最大化問題を連続的な最適化に変換するためにマルチ線形拡張を利用する$\textbf{MA-OSMA}$アルゴリズムを提案する。 さらに、$\textbf{MA-OSMA}$は、準最適定常点を避けるために新しい代理勾配を利用する。 また,$\textbf{MA-OSMA}$における計算集約的なプロジェクション操作を排除するために,一様分布を混合することによりKLの発散を効果的に活用するプロジェクションフリーな$\textbf{MA-OSEA}$アルゴリズムを導入する。 理論的には、両アルゴリズムが$\widetilde{O}(\sqrt {\frac{C_{T}T}{1-\beta}})$に対して$(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximumr sequence, $\beta$ is the gap of the network and $c$ is the joint curvature of submodular objectives。 この結果は、最先端OSGアルゴリズムによって提供される$(\frac{1}{1+c})$-approximationを大幅に改善する。 最後に,シミュレーションに基づくマルチターゲットトラッキングによる提案アルゴリズムの有効性を示す。

関連論文リスト

• Distributed Difference of Convex Optimization [1.2661010067882734]
  $-f_i$ と $-f_i$ の $-差分の違いによる各エージェントにおけるn$ エージェントの局所目的関数を含む分散問題のクラスを示す。 DDC-Consensusアルゴリズムは、正規化されていない分散二乗問題を解くために開発された。
  論文  参考訳（メタデータ） (2024-07-23T14:41:32Z)
• Theoretical Study of Conflict-Avoidant Multi-Objective Reinforcement Learning [21.288881065839007]
  本稿では,CA と FC という2つのサブプロデューサの選択肢に基づいて,新しい動的重み付けマルチタスク・アクター・クリティック・アルゴリズム (MTAC) を開発した。 MTAC-CAは、タスク間の最小値改善を最大化する競合回避(CA)更新方向と、MTAC-FCターゲットをはるかに高速な収束速度で見つけることを目的としている。 MT10における実験により,既存のMTRL法よりもアルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2024-05-25T05:57:46Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
  単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。 従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。 同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
  論文  参考訳（メタデータ） (2023-05-29T02:54:31Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• 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)
• Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization [11.889570525184801]
  単調連続DR-submodular-Frank問題に対する2つの分散オンラインアルゴリズムを提案する。 1つはOne-shot Decentralized Meta-Wolfe (Mono-DMFW)で、1-1/e)$regret bound $O(T4/5)$を達成している。 次に,非公開ブースティング関数citepzhang2022 に着想を得て,分散オンラインブースティング・グラディエント・アセンジ(DOBGA)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-18T07:32:28Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [34.77250498401055]
  複数の長期目標の非線形凹関数を最大化する問題を定式化する。 この問題に対してポリシー段階に基づくモデルフリーアルゴリズムを提案する。 提案アルゴリズムは,グローバルオプティマの$epsilon$以内に収束することが示されている。
  論文  参考訳（メタデータ） (2021-05-28T22:20:54Z)

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

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