論文の概要: Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

• arxiv url: http://arxiv.org/abs/2608.12134v1
• Date: Wed, 12 Aug 2026 14:54:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.618584
• Title: Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning
• Title（参考訳）: Poisson-Process submodular Maximization のマトロイドに対する逆レジリエンス:ロバストオフライン最適化からフルバンド学習へ
• Authors: Vaneet Aggarwal,
• Abstract要約: オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-2})$ oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret.
• Abstract（参考訳）: オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー最大化について検討する。 我々の主な成果は、Spiteful Greedy Swap Poisson Process (SGS-Poisson): ポアソン強度、単一元素交換規則、または不必要なドロップステップを変更することなく、このアルゴリズムは非単調な目的に対して1/e$、単調な目的に対して1/e$、そして1/e$の制限を保っている。 より正確には、すべての制御されたオラクルにおいて、$\widehat f$ が $|\widehat f(S)-f(S)|\le は $S$ のすべての集合に対して$|\widehat f(S)-f(S)|\le は、少なくとも$(1/e-\varepsilon)\OPT-O(k)$ と $(1-1/e-\varepsilon)\OPT-O(k)$ の期待値を持つ実現可能な集合を、それぞれ $\widetilde O(nk^2\varepsilon^{-2})$ を使って返します。 その結果、オフラインからオンラインへの還元は、一般のマトロイド制約のサブモジュラー報酬に対して1/e$と1-1/e$と$\widetilde O(n^{1/5}k^{4/5}T^{4/5})の完全帯域CMABアルゴリズムをもたらす。

関連論文リスト

• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model [26.860985092865203]
  ランダム順序モデルにおいて、損失関数の多元集合が逆向きに選択されるが、一様ランダムな順序で表されるオンライン学習について検討する。 提案手法は,無作為順序モデルにおける小さめの後悔境界の確立において,スパーシフィケーションと関連する手法のパワーに光を当てるものである。
  論文  参考訳（メタデータ） (2026-02-10T06:46:01Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。 係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。 オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
  論文  参考訳（メタデータ） (2022-01-03T15:10:17Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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