論文の概要: Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
- arxiv url: http://arxiv.org/abs/2607.00680v1
- Date: Wed, 01 Jul 2026 09:22:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-02 19:56:07.829394
- Title: Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
- Title（参考訳）: 境界サンプリングによる分散オンライン帯域サブモジュールの最大化
- Authors: Bin Du, Chang Liu, Dingqi Zhu, Lintao Ye, Dengfeng Sun,
- Abstract要約: 分割マトロイド制約下での分散オンラインサブモジュールについて検討した。
我々は,全情報および包括的フィードバックモデルに対応する統一的なアルゴリズムフレームワークを開発する。
- 参考スコア（独自算出の注目度）: 6.789996850053261
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear $(1-1/e)$-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in $T$, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.
- Abstract（参考訳）: 分割マトロイド制約下での分散オンラインサブモジュールの最大化について検討し、複数のエージェントがそれぞれのサブセットから限られた数のアクションを順次選択し、対象関数列の累積値を最大化する。
我々は,全情報および包括的フィードバックモデルに対応する統一的なアルゴリズムフレームワークを開発する。
両方のフィードバックモデルに対して,提案アルゴリズムが既存の集中型アルゴリズムと同等の1-1/e$-regret保証を実現することを証明した。
さらに, 連続緩和と丸めによるサンプリング違反問題に対処するために, 境界付き確率的ピページ丸め方式を開発し, サンプリング違反の確率が漸近的になくなることを示す。
その結果、累積サンプリング違反は$T$のサブラインに留まり、ある条件下では即効性がないことがさらに示されている。
本論文の理論的知見を数値計算により検証した。
関連論文リスト
- Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。
また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-23T02:30:01Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-10-24T19:57:56Z) - Amortizing intractable inference in large language models [56.92471123778389]
難治性後部分布のサンプルとして, 償却ベイズ推定を用いる。
我々は,LLMファインチューニングの分散マッチングパラダイムが,最大習熟の代替となることを実証的に実証した。
重要な応用として、チェーン・オブ・ソート推論を潜在変数モデリング問題として解釈する。
論文 参考訳（メタデータ） (2023-10-06T16:36:08Z) - Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2023-10-02T08:07:36Z) - Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
我々は、完全に学習率の低い制約付き領域をサンプリングするための新しい粒子ベースのアルゴリズム一式を導入する。
我々は,本アルゴリズムの性能を,単純度に基づくターゲットからのサンプリングを含む,様々な数値的な例で示す。
論文 参考訳（メタデータ） (2023-05-24T09:31:18Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳（メタデータ） (2021-08-25T17:09:01Z) - Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。
情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。
これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
論文 参考訳（メタデータ） (2021-05-25T10:08:41Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。