論文の概要: Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

• arxiv url: http://arxiv.org/abs/2609.24569v2
• Date: Tue, 22 Sep 2026 03:00:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:04.001108
• Title: Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
• Title（参考訳）: 部分モジュラリティを超えたポアソン交換:マトロイドに対するオフラインおよびオンラインサブセット選択のための効果的な近似アルゴリズム
• Abstract要約: 本稿では,不均一なポアソン時計を注意深く制御することで,最大利得の局所交換を繰り返すMGPEと呼ばれる新しいアルゴリズムを提案する。 また,マトロイド制約が濃度に減少するか,あるいは目標が$$$-weak DR-submodularityというより強い概念を満たす場合,MGPEはそれぞれ1-e-$と1-e-$の厳密な近似比を自動的に回復できることを示した。
• 参考スコア（独自算出の注目度）: 46.81212204219748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over the past decade, a growing body of research has shown that $γ$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $γ$-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative $(1+1/γ)^{-2}$ factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to $ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} }$. In sharp contrast to the previous guarantee, our obtained factor $ρ_γ$ not only strictly improves upon $(1+1/γ)^{-2}$ for every $γ\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $γ\to1$. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of $α$-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of $1-e^{-γ}$ and $1-e^{-α}$, respectively. Here, $α\in(0,1]$ denotes the DR ratio.
• Abstract（参考訳）: 過去10年間で、機能選択、ニューラルネットワークのプルーニング、ビデオの要約など、多数のサブセット選択タスクにおいて、$γ$-weakのサブモジュラリティが広範に発生することが、研究機関によって示されている。 その有界性にもかかわらず、一般のマトロイド制約に従属する$γ$弱部分モジュラ函数を最大化することは依然として困難である。 現在知られている唯一の近似保証は、 \citet{chen2018weakly} によって確立された保守的な$(1+1/γ)^{-2}$因子である。 この結果を改善するために,不均一なポアソン時計を慎重に制御することで,最大ゲイン局所交換を繰り返す新しいアルゴリズムである \MGPE を提案し,この \MGPE\ が任意の近似比を$ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} に近似できることを示した。 以前の保証とは対照的に、得られた係数 $ρ_γ$ は、すべての$γ\in(0,1]$に対して$(1+1/γ)^{-2}$ を厳密に改善するだけでなく、部分モジュラー最大化に対する $(1-1/e)$-近似を$γ\to1$ として漸近的にアプローチすることができる。 さらに、マトロイドの制約が濃度に減少したり、目的が$α$-弱 DR-部分モジュラリティの強い概念を満たすと、 \MGPE\ はそれぞれ $1-e^{-γ}$ と $1-e^{-α}$ の厳密な近似比を自動的に回復できる。 ここで、$α\in(0,1]$はDR比を表す。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization [42.50444156527582]
  閉鎖凸体上の非単調な$$$-weakly DR-submodular関数について検討した。 我々のアプローチは、Frank-Wolfe指導の継続的機械学習フレームワークと$-greedyのステップを組み合わせています。 これにより、非単調な$$-weakly DR-submodular over down-closed convex bodyに対する最先端の保証が得られる。
  論文  参考訳（メタデータ） (2026-01-02T08:44:10Z)
• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。 係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。 オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
  論文  参考訳（メタデータ） (2022-01-03T15:10:17Z)
• 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)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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