論文の概要: Communication-Efficient Decentralized Online Continuous DR-Submodular
Maximization
- arxiv url: http://arxiv.org/abs/2208.08681v1
- Date: Thu, 18 Aug 2022 07:32:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-19 14:09:29.921495
- Title: Communication-Efficient Decentralized Online Continuous DR-Submodular
Maximization
- Title（参考訳）: 通信効率の高い分散型オンライン連続drmサブモジュラー最大化
- Authors: Qixin Zhang, Zengde Deng, Xiangru Jian, Zaiyi Chen, Haoyuan Hu, Yu
Yang
- Abstract要約: 単調連続DR-submodular-Frank問題に対する2つの分散オンラインアルゴリズムを提案する。
1つはOne-shot Decentralized Meta-Wolfe (Mono-DMFW)で、1-1/e)$regret bound $O(T4/5)$を達成している。
次に,非公開ブースティング関数citepzhang2022 に着想を得て,分散オンラインブースティング・グラディエント・アセンジ(DOBGA)アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 11.889570525184801
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maximizing a monotone submodular function is a fundamental task in machine
learning, economics, and statistics. In this paper, we present two
communication-efficient decentralized online algorithms for the monotone
continuous DR-submodular maximization problem, both of which reduce the number
of per-function gradient evaluations and per-round communication complexity
from $T^{3/2}$ to $1$. The first one, One-shot Decentralized Meta-Frank-Wolfe
(Mono-DMFW), achieves a $(1-1/e)$-regret bound of $O(T^{4/5})$. As far as we
know, this is the first one-shot and projection-free decentralized online
algorithm for monotone continuous DR-submodular maximization. Next, inspired by
the non-oblivious boosting function \citep{zhang2022boosting}, we propose the
Decentralized Online Boosting Gradient Ascent (DOBGA) algorithm, which attains
a $(1-1/e)$-regret of $O(\sqrt{T})$. To the best of our knowledge, this is the
first result to obtain the optimal $O(\sqrt{T})$ against a
$(1-1/e)$-approximation with only one gradient inquiry for each local objective
function per step. Finally, various experimental results confirm the
effectiveness of the proposed methods.
- Abstract（参考訳）: 単調部分モジュラ函数の最大化は、機械学習、経済学、統計学における基本的な課題である。
本稿では,単調連続DR-サブモジュラー最大化問題に対する2つの通信効率の高い分散オンラインアルゴリズムを提案する。
1つはOne-shot Decentralized Meta-Frank-Wolfe (Mono-DMFW)で、$(1-1/e)$-regret bound of $O(T^{4/5})$である。
われわれが知る限り、これは単調連続DR-サブモジュラー最大化のための最初の単発およびプロジェクションフリーの分散オンラインアルゴリズムである。
次に,非難解なブースティング関数 \citep{zhang2022boosting} に着想を得て,分散オンラインブースティング勾配上昇(dobga)アルゴリズムを提案し,$(1-1/e)$-regret を$o(\sqrt{t})$とする。
我々の知る限り、これは、各ステップ毎の局所目的関数に対して1つの勾配探索しか持たない$(1-1/e)$-approximationに対して最適な$O(\sqrt{T})$を得る最初の結果である。
最後に,提案手法の有効性を実験的に検証した。
関連論文リスト
- 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) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - 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) - Online Learning for Non-monotone Submodular Maximization: From Full
Information to Bandit Feedback [12.914842850902456]
本稿では, 閉鎖凸集合上でのオンライン非単調連続DR-サブモジュラー問題を再検討する。
メタ-MFWアルゴリズムは$O(sqrtT)$の1/e$-regret境界を達成する。
次に、Mono-MFWを帯域設定に拡張し、$O(T8/9)の1/e$-regretバウンダリのBandit-MFWアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-16T09:32:37Z) - Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。
係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。
オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
論文 参考訳（メタデータ） (2022-01-03T15:10:17Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。