論文の概要: Regularized Submodular Maximization at Scale

• arxiv url: http://arxiv.org/abs/2002.03503v1
• Date: Mon, 10 Feb 2020 02:37:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 07:43:00.270743
• Title: Regularized Submodular Maximization at Scale
• Title（参考訳）: スケールでの正則化サブモジュラー最大化
• Authors: Ehsan Kazemi and Shervin Minaee and Moran Feldman and Amin Karbasi
• Abstract要約: 亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
• 参考スコア（独自算出の注目度）: 45.914693923126826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose scalable methods for maximizing a regularized submodular function $f = g - \ell$ expressed as the difference between a monotone submodular function $g$ and a modular function $\ell$. Indeed, submodularity is inherently related to the notions of diversity, coverage, and representativeness. In particular, finding the mode of many popular probabilistic models of diversity, such as determinantal point processes, submodular probabilistic models, and strongly log-concave distributions, involves maximization of (regularized) submodular functions. Since a regularized function $f$ can potentially take on negative values, the classic theory of submodular maximization, which heavily relies on the non-negativity assumption of submodular functions, may not be applicable. To circumvent this challenge, we develop the first one-pass streaming algorithm for maximizing a regularized submodular function subject to a $k$-cardinality constraint. It returns a solution $S$ with the guarantee that $f(S)\geq(\phi^{-2}-\epsilon) \cdot g(OPT)-\ell (OPT)$, where $\phi$ is the golden ratio. Furthermore, we develop the first distributed algorithm that returns a solution $S$ with the guarantee that $\mathbb{E}[f(S)] \geq (1-\epsilon) [(1-e^{-1}) \cdot g(OPT)-\ell(OPT)]$ in $O(1/ \epsilon)$ rounds of MapReduce computation, without keeping multiple copies of the entire dataset in each round (as it is usually done). We should highlight that our result, even for the unregularized case where the modular term $\ell$ is zero, improves the memory and communication complexity of the existing work by a factor of $O(1/ \epsilon)$ while arguably provides a simpler distributed algorithm and a unifying analysis. We also empirically study the performance of our scalable methods on a set of real-life applications, including finding the mode of distributions, data summarization, and product recommendation.
• Abstract（参考訳）: 本稿では,単調部分モジュラ関数 $g$ とモジュラ関数 $\ell$ との差として表現される正規化部分モジュラ関数 $f = g - \ell$ を最大化するスケーラブルな手法を提案する。 実際、亜モジュラリティは本質的に多様性、範囲、代表性の概念と関係している。 特に、行列点過程、部分モジュラー確率モデル、強い対数凹凸分布など、多様性の多くの一般的な確率モデルのモードを見つけることは、(正規化)部分モジュラー函数の最大化を伴う。 正規化函数 $f$ は負の値を取ることができるので、部分モジュラー函数の非負性仮定に強く依存する部分モジュラー極大化の古典理論は適用できないかもしれない。 この課題を回避するために,$k$-cardinality制約を受ける正則化部分モジュラ関数を最大化するための最初の1パスストリーミングアルゴリズムを開発した。 解 $S$ を $f(S)\geq(\phi^{-2}-\epsilon) \cdot g(OPT)-\ell (OPT)$ とすると、$\phi$ は黄金比である。 さらに、$\mathbb{e}[f(s)] \geq (1-\epsilon) [(1-e^{-1}) \cdot g(opt)-\ell(opt)]$ in $o(1/ \epsilon)$ rounds of mapreduce computingを保証して、$s$を返す最初の分散アルゴリズムを開発した。 モジュラー項 $\ell$ が 0 であるような非正規化の場合でさえ、既存の作業のメモリと通信の複雑さを$O(1/ \epsilon)$ の係数で改善し、より単純な分散アルゴリズムと統一解析を提供する。 また,分散モードの発見やデータの要約,製品レコメンデーションなど,一連の実生活アプリケーション上でのスケーラブルな手法の性能を実証的に検討する。

関連論文リスト

• 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)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Partial-Monotone Adaptive Submodular Maximization [19.29174615532181]
  サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。 これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
  論文  参考訳（メタデータ） (2022-07-26T12:16:12Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• 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)

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

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