論文の概要: A Unified Approach to Submodular Maximization Under Noise
- arxiv url: http://arxiv.org/abs/2510.21128v1
- Date: Fri, 24 Oct 2025 03:31:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 06:57:23.376904
- Title: A Unified Approach to Submodular Maximization Under Noise
- Title（参考訳）: 雑音下における部分モジュラ最大化への統一的アプローチ
- Authors: Kshipra Bhawalkar, Yang Cai, Zhe Feng, Christopher Liaw, Tao Lin,
- Abstract要約: 我々は,関数の雑音値オラクルにアクセスできる部分モジュラ函数を最大化する問題を考える。
greedy greedyアルゴリズムを用いて、雑音下での非拘束的(非モノトーン)部分モジュラーに対する1/2$-近似を求める。
- 参考スコア（独自算出の注目度）: 15.762704657089637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a $(1-1/e)$-approximation (resp. $1/e$-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a $1/2$-approximation for unconstrained (non-monotone) submodular maximization under noise.
- Abstract（参考訳）: 我々は,関数の雑音値オラクルにアクセスできるような部分モジュラ函数を最大化する問題を,正確な値オラクルの代わりに考慮する。
以前の作業と同様に、特定の集合に対する複数の呼び出しが常に同じ値を返すという点で、ノイズの多いオラクルは永続的であると仮定する。
このモデルでは、Hassidim and Singer (2017) は、濃度制約を受けるモノトン部分モジュラー最大化のための$(1-1/e)$-approximationアルゴリズムを設計し、Huang et al (2022) は任意の任意の行列制約を受けるモノトン部分モジュラー最大化のための$(1-1/e)/2$-approximationアルゴリズムを設計した。
本稿では,ブラックボックスとして,任意の「ロバスト」アルゴリズムをブラックボックスとして利用し,近似保証を維持しながら雑音設定のためのアルゴリズムに変換するメタアルゴリズムを設計する。
測定された連続グリードアルゴリズムを用いてメタアルゴリズムを用いて、雑音下でのマトロイド制約を受けるモノトーン (resp. non-monotone) 部分モジュラー最大化に対する$(1-1/e)$-approximation (resp. $1/e$-approximation) を求める。
さらに, メタアルゴリズムと二重グリーディアルゴリズムを用いて, 雑音下での非拘束的(非モノトーン)部分モジュラー最大化に対する1/2$-近似を求める。
関連論文リスト
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。
1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。
第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
論文 参考訳（メタデータ） (2025-09-26T17:16:34Z) - 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) - Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - Dynamic Non-monotone Submodular Maximization [11.354502646593607]
濃度制約$k$で非単調部分モジュラ函数を最大化することから、同じ制約の下で単調部分モジュラ函数を最大化することへの還元を示す。
我々のアルゴリズムは、ソリューションの$(epsilon)$-approximateを維持し、期待される$O(epsilon-3k3log3(n)log(k)$ query per updateを使用する。
論文 参考訳（メタデータ） (2023-11-07T03:20:02Z) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-07-26T07:08:03Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - 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) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization in Linear Time [17.19443570570189]
濃度制約を受ける非単調適応部分モジュラー問題について検討する。
適応的ランダムグリードアルゴリズムは適応的部分モジュラリティの下で1/e$の近似比を達成することを示す。
我々は,$O(nepsilon-2log epsilon-1)$値オラクルクエリを期待して,1-1/e-epsilon$近似比を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-11T21:06:52Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。