論文の概要: When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

• arxiv url: http://arxiv.org/abs/2610.26967v2
• Date: Wed, 21 Oct 2026 02:00:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.082356
• Title: When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
• Title（参考訳）: 弱部分モジュラリティがマトロイドと出会う時:標準グリーディはどのように働くのか?
• Abstract要約: 我々は、$R_mathrmgr(,r)$の標準フォワードグリーディの最悪のケース保証について検討し、$r$はマトロイドのランクである。 R_mathrmgr(,r)$, beginequationlabeleq_upper_label R_gr(,r) leminleftfrac12,20maxfracr(,r) frac214に対して対応する上限を設定する。
• 参考スコア（独自算出の注目度）: 53.71015942776893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight $(1-e^{-γ})$-approximation guarantee, where $γ$ denotes the submodularity ratio. However, when considering general matroid constraints, \emph{how well standard greedy can perform} has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee $R_{\mathrm{gr}}(γ,r)$ of standard forward greedy, where $r$ is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{gr}(γ,r)\ge \max\left\{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right\}, \end{equation*} where $B_γ\triangleq2-γ+γ^2$. This lower bound not only strictly improves upon the previous guarantee of $0.4γ^2/(1+\sqrt{γr})$, but also can recover the classical $1/2$-approximation guarantee at $γ=1$. Subsequently, a corresponding upper bound is established for $R_{\mathrm{gr}}(γ,r)$, namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left\{\frac{1}{2},20\max\left\{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right\}\right\}. \end{equation} For every fixed $γ\in(0,1)$, this equation effectively sharpens the recent $O_γ(1/\log(n-1))$ upper bound to $O_γ(r^{-1/2})$, where $n$ is the size of ground set. Putting all these results together, we eventually can obtain \[R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).\]
• Abstract（参考訳）: 弱い部分モジュラー最大化は、機械学習、データマイニング、統計学に多くの応用を見出す。 特に、濃度制約の下では、標準グリーディアルゴリズムは、1-e^{-γ})$-approximation(英語版)という厳密な$(1-e^{-γ})$-approximation(英語版)を保証することが知られている。 しかし、一般のマトロイドの制約を考えるとき、'emph{how well standard greedy can perform} は長年の未解決問題のままである。 本稿では、この問題を、$R_{\mathrm{gr}}(γ,r)$ of standard forward greedy, where $r$ is the rank of matroid。 具体的には、以下の洗練された下界 \begin{equation*} R_{gr}(γ,r)\ge \max\left\{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right\}, \end{equation*} ここでは、B_γ\triangleq2-γ+γ^2$である。 この下限は、以前の0.4γ^2/(1+\sqrt{γr})$の保証を厳密に改善するだけでなく、古典的な1/2$-近似保証を$γ=1$で回復することもできる。 すると、対応する上限が$R_{\mathrm{gr}}(γ,r)$、すなわち \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left\{\frac{1}{2},20\max\left\{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right\right\right\} に対して成立する。 \end{equation} すべての固定された$γ\in(0,1)$に対して、この方程式は、最近の$O_γ(1/\log(n-1))$上界を$O_γ(r^{-1/2})$に事実上鋭くする。 これらの結果をまとめると、最終的に \[R_{gr}(γ,r) = >\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\right\right が得られる。 \]

関連論文リスト

• Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids [46.81212204219748]
  本稿では,不均一なポアソン時計を注意深く制御することで,最大利得の局所交換を繰り返すMGPEと呼ばれる新しいアルゴリズムを提案する。 また,マトロイド制約が濃度に減少するか,あるいは目標が$$$-weak DR-submodularityというより強い概念を満たす場合,MGPEはそれぞれ1-e-$と1-e-$の厳密な近似比を自動的に回復できることを示した。
  論文  参考訳（メタデータ） (2026-09-21T13:35:10Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Boundary-driven quantum systems near the Zeno limit: steady states and long-time behavior [0.0]
  有限次元状態空間 $mathcal H_Aotimes 数学 H_B$ はリンドブラッド方程式 $'(t) = 数学 L_(t)$ によって支配される。 もし$mathcal D_Psharp$がエルゴディックでギャップがあるなら、$mathcal L_$ for all large $$、$bar_$が$mathcal L_$のユニークな定常状態であることを示す。
  論文  参考訳（メタデータ） (2025-12-14T20:13:54Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• Constrained HRT Surfaces and their Entropic Interpretation [0.0]
  我々は、サブリージョン$A$のR'enyiエントロピーを、サブリージョン$B$の固定領域状態において研究する。 この結果は,標準ランダムネットワークを用いて時間依存測地を記述しようとする試みに関連するいくつかの問題に関係している。
  論文  参考訳（メタデータ） (2023-11-30T06:50:40Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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