論文の概要: Stochastic Submodular Maximization via Polynomial Estimators

• arxiv url: http://arxiv.org/abs/2303.09960v1
• Date: Fri, 17 Mar 2023 13:32:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-20 14:35:03.930631
• Title: Stochastic Submodular Maximization via Polynomial Estimators
• Title（参考訳）: 多項式推定器による確率的部分モジュラー最大化
• Authors: G\"ozde \"Ozcan and Stratis Ioannidis
• Abstract要約: 未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。 この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
• 参考スコア（独自算出の注目度）: 13.498923494159312
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we study stochastic submodular maximization problems with general matroid constraints, that naturally arise in online learning, team formation, facility location, influence maximization, active learning and sensing objective functions. In other words, we focus on maximizing submodular functions that are defined as expectations over a class of submodular functions with an unknown distribution. We show that for monotone functions of this form, the stochastic continuous greedy algorithm attains an approximation ratio (in expectation) arbitrarily close to $(1-1/e) \approx 63\%$ using a polynomial estimation of the gradient. We argue that using this polynomial estimator instead of the prior art that uses sampling eliminates a source of randomness and experimentally reduces execution time.
• Abstract（参考訳）: 本稿では,オンライン学習,チーム形成,施設配置,影響最大化,アクティブラーニング,客観的機能センシングにおいて自然に発生する,一般的なマトロイド制約を伴う確率的サブモジュラー最大化問題について検討する。 言い換えれば、未知分布を持つ部分モジュラ関数のクラスに対する期待として定義される部分モジュラ関数を最大化することに集中する。 この形の単調関数に対して、確率的連続グリーディアルゴリズムは勾配の多項式推定を用いて、任意に$(1-1/e) \approx 63\%$に近似比(予想)を得ることを示す。 サンプリングを用いた従来の手法の代わりにこの多項式推定器を用いることで、ランダム性の源を排除し、実行時間を実験的に短縮する。

関連論文リスト

• Learning Submodular Sequencing from Samples [11.528995186765751]
  本稿では,いくつかの複合部分モジュラー関数を最適化するために,シーケンス内の項目の選択とランク付けの問題に対処する。 本稿では,各部分モジュラ関数の曲率に依存する近似比を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-09T01:33:13Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。 本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
  論文  参考訳（メタデータ） (2022-10-20T06:00:45Z)
• 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)
• Submodular Maximization via Taylor Series Approximation [16.682504954615922]
  マトロイド制約を用いた部分モジュラー決定論的問題について検討する。 この形式のために、いわゆる連続関数グリーディアルゴリズムは、テイラー級数近似を用いて、およそ 0.63$ 以前の$(1-1/e) に近い比率を得る。
  論文  参考訳（メタデータ） (2021-01-19T02:41:45Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs [54.967872716145656]
  この研究は、無限水平非カウントマルコフ決定過程(MDPs)における関数近似を伴うオフ・ポリティ・アセスメント(OPE)に焦点を当てる。 提案手法は,第1の有限サンプル OPE 誤差境界であり,既存の結果がエピソードおよびディスカウントケースを超えて拡張される。 この結果から,教師あり学習における最大エントロピー的アプローチを並列化して,十分な統計値を持つ指数関数型家族分布が得られた。
  論文  参考訳（メタデータ） (2020-06-17T18:13:37Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。 また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-09T12:32:14Z)

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

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