論文の概要: Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

• arxiv url: http://arxiv.org/abs/2605.07902v1
• Date: Fri, 08 May 2026 15:42:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.170609
• Title: Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
• Title（参考訳）: 有意性を超えた曲率:任意部分モジュラ関数に対するGreedy Guarantees
• Authors: Yixin Chen, Alan Kuhnle,
• Abstract要約: サブモジュール関数は機械学習の中心である。 負の値を取る部分モジュラー関数に対する曲率制御の乗算比を持つグリーディアルゴリズム。
• 参考スコア（独自算出の注目度）: 11.839184290641247
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight $63\%$ approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime $1 \le c_g < 2.2$, the bound strictly beats the best known uniform ratio of $0.401$ (for non-negative $f$), and it recovers the classical $(1-e^{-c_g})/c_g$ guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.
• Abstract（参考訳）: サブモジュール関数 -- リターンの減少を示す関数 -- は、マシンラーニングの中心である。 目的が単調で非負の場合、greedyアルゴリズムは6,3\%の近似を厳密に達成する。 しかし、実際的な目的の多くはいくつかの入力に対して負のコストを伴い、既存の乗法的保証は非負性を必要とする。 以前の作業は、特別な分解可能関数のクラスと非単調性に対する部分単調性パラメータの付加的境界による負性を扱うが、これらは分離の難しさに対処し、古典的構造理論を拡張しない。 関数が線型性からどのくらい離れているかを測定するパラメータである 'emph{curvature} をすべての部分モジュラ函数に拡張し、古典的な概念を通じて非単調性と負性の両方を扱う。 プルーニングを用いたグリーディアルゴリズムは、負の値を取る関数を含む、n-emph{any} 部分モジュラー関数に対する曲率制御の乗法比を達成する。 非単調な状態において、$ $1 \le c_g < 2.2$ は、0.401$ (非負の$f$) の最もよく知られた均一比を厳密に上回り、古典的な 1-e^{-c_g})/c_g$ の単調関数の保証を回復する。 多線形拡張変種は、フレームワークを多線形緩和を通じて一般的な組合せ制約にまで拡張する。 費用対効果のある実験設計, カバレッジ, 特徴選択, およびマルチニューズ流路選択における曲率スイープに関する実験は, この理論を支持している。

関連論文リスト

• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  自己正規化マルティンガレのスケール不変上界が可能であることを示す。 通常の正規化ペナルティを含まない自己正規化濃度不等式を導出する。
  論文  参考訳（メタデータ） (2026-05-02T22:39:00Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。 また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-23T02:30:01Z)
• Stochastic $k$-Submodular Bandits with Full Bandit Feedback [29.705337940879705]
  オンラインの$k$-submodular最適化問題に対して,最初のサブ線形$alpha$-regretバウンダリをフルバンドフィードバックで提示する。 私たちの研究の重要な貢献は、アルゴリズムの堅牢性を分析することです。
  論文  参考訳（メタデータ） (2024-12-14T05:02:53Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Partial-Monotone Adaptive Submodular Maximization [19.29174615532181]
  サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。 これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
  論文  参考訳（メタデータ） (2022-07-26T12:16:12Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  多くの標準部分モジュラーアルゴリズムに対して、単調性比に依存する新しい近似保証を証明できることが示される。 これにより、映画レコメンデーション、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比が向上する。
  論文  参考訳（メタデータ） (2022-02-07T10:35:40Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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