論文の概要: Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions

• arxiv url: http://arxiv.org/abs/2602.09502v1
• Date: Tue, 10 Feb 2026 07:59:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.436248
• Title: Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions
• Title（参考訳）: 分散オンライン部分モジュラ最大化のための削減による近似レグレットの改善
• Authors: Yuanyu Wan, Yu Shen, Dingzhi Yu, Bo Xue, Mingli Song,
• Abstract要約: 近似凸設定境界と後悔境界のギャップを利用する方法を示す。 また,集中型自由度アルゴリズムは複雑な決定集合を効率的に処理できることを示す。 我々の主要な技術は、D-OCSMから分散オンライン凸最適化(D-OCO)までである。
• 参考スコア（独自算出の注目度）: 59.626542575681725
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To expand the applicability of decentralized online learning, previous studies have proposed several algorithms for decentralized online continuous submodular maximization (D-OCSM) -- a non-convex/non-concave setting with continuous DR-submodular reward functions. However, there exist large gaps between their approximate regret bounds and the regret bounds achieved in the convex setting. Moreover, if focusing on projection-free algorithms, which can efficiently handle complex decision sets, they cannot even recover the approximate regret bounds achieved in the centralized setting. In this paper, we first demonstrate that for D-OCSM over general convex decision sets, these two issues can be addressed simultaneously. Furthermore, for D-OCSM over downward-closed decision sets, we show that the second issue can be addressed while significantly alleviating the first issue. Our key techniques are two reductions from D-OCSM to decentralized online convex optimization (D-OCO), which can exploit D-OCO algorithms to improve the approximate regret of D-OCSM in these two cases, respectively.
• Abstract（参考訳）: 分散オンライン学習の適用性を高めるため、従来の研究では、連続DRサブモジュラー報酬関数を備えた非凸/非凹面設定である分散オンラインサブモジュラー最大化(D-OCSM)のためのいくつかのアルゴリズムが提案されている。 しかし、その近似的後悔境界と凸設定で達成される後悔境界との間には大きなギャップがある。 さらに、複雑な決定集合を効率的に処理できるプロジェクションフリーアルゴリズムに焦点を合わせると、集中的な設定で達成された近似的後悔境界を回復することができない。 本稿では,一般凸決定集合に対するD-OCSMについて,これら2つの問題を同時に扱うことができることを示す。 さらに,D-OCSMを下方修正した下方決定集合に対して,第2の問題は,第1の問題を著しく緩和しつつ対処可能であることを示す。 D-OCSM から分散化オンライン凸最適化 (D-OCO) への2つの改善が鍵となる。

関連論文リスト

• Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition [44.61147231796296]
  オンライン学習(OKL)は、ストリーミング環境での予測性能が期待できるため、かなりの研究関心を集めている。 既存の2次OKLアプローチは、予め設定された予算に関して、少なくとも2次時間の複雑さに悩まされている。 本稿では,2次OKLに適した高速増分行列スケッチと分解手法FORTSを提案する。
  論文  参考訳（メタデータ） (2024-10-15T02:07:48Z)
• Efficiently Training Deep-Learning Parametric Policies using Lagrangian Duality [55.06411438416805]
  制約付きマルコフ決定プロセス(CMDP)は、多くの高度な応用において重要である。 本稿では,パラメトリックアクターポリシーを効率的に訓練するための2段階深度決定規則(TS-DDR)を提案する。 現状の手法と比較して, 解の質を高め, 数桁の計算時間を削減できることが示されている。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。 我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
  論文  参考訳（メタデータ） (2023-07-05T13:52:10Z)
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
  MapReduce(MR)モデルのサブモジュラー関数は注目されている。 MR設定において,複数のサブ線形適応アルゴリズムが動作に必要な整合性を満たすことを示す。
  論文  参考訳（メタデータ） (2022-06-20T04:17:32Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)

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

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