論文の概要: The Power of Subsampling in Submodular Maximization

• arxiv url: http://arxiv.org/abs/2104.02772v1
• Date: Tue, 6 Apr 2021 20:25:57 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-09 02:36:53.069992
• Title: The Power of Subsampling in Submodular Maximization
• Title（参考訳）: submodular maximization (複数形 submodular maximizations)
• Authors: Christopher Harshaw, Ehsan Kazemi, Moran Feldman, Amin Karbasi
• Abstract要約: このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
• 参考スコア（独自算出の注目度）: 51.629656762796564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set, and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual offline setting, we present SampleGreedy, which obtains a $(p + 2 + o(1))$-approximation for maximizing a submodular function subject to a $p$-extendible system using $O(n + nk/p)$ evaluation and feasibility queries, where $k$ is the size of the largest feasible set. The approximation ratio improves to $p+1$ and $p$ for monotone submodular and linear objectives, respectively. In the streaming setting, we present SampleStreaming, which obtains a $(4p +2 - o(1))$-approximation for maximizing a submodular function subject to a $p$-matchoid using $O(k)$ memory and $O(km/p)$ evaluation and feasibility queries per element, where $m$ is the number of matroids defining the $p$-matchoid. The approximation ratio improves to $4p$ for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
• Abstract（参考訳）: 集中およびオンライン設定における部分モジュラ最大化のための統一的なアルゴリズム手法としてサブサンプリングを提案する。 アイデアは単純で、基底集合から独立した要素をサンプリングし、これらのサンプル要素に単純な組合せ技術(グリーディや局所探索など)を使用する。 このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 通常のオフライン設定では、$o(n + nk/p)$評価と実行可能性クエリを使用して、$p$-extendibleシステムに属するサブモジュラー関数を最大化するための$(p + 2 + o(1))$近似を求める。 近似比は単調部分モジュラーおよび線形目的に対してそれぞれ$p+1$および$p$に改善される。 ストリーミング設定では、$O(k)$メモリと$O(km/p)$評価とフィーザビリティクエリを使用して、$O(k)$メモリと$O(km/p)$のサブモジュール関数を最大化するための$(4p + 2 - o(1))$-approximationを得る。 近似比はモノトン部分モジュラー目的に対して4p$に向上する。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。

関連論文リスト

• 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)
• Linear Submodular Maximization with Bandit Feedback [7.926559636438099]
  準モジュラー目的関数 $f:2UtomathbbR_geq 0$, ここでは $f=sum_i=1dw_iF_i$ に対する近似アルゴリズムの開発を検討する。 F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。 我々のアルゴリズムは、$fの線形構造を利用していないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2024-07-02T18:40:52Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  適応部分モジュラ函数の最小コスト被覆の問題を考える。 このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
  論文  参考訳（メタデータ） (2022-08-17T15:26:47Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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