論文の概要: Partial-Monotone Adaptive Submodular Maximization

• arxiv url: http://arxiv.org/abs/2207.12840v1
• Date: Tue, 26 Jul 2022 12:16:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-27 13:31:08.384881
• Title: Partial-Monotone Adaptive Submodular Maximization
• Title（参考訳）: 部分モノトン適応サブモジュラー最大化
• Authors: Shaojie Tang, Jing Yuan
• Abstract要約: サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。 これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
• 参考スコア（独自算出の注目度）: 19.29174615532181
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many sequential decision making problems, including pool-based active learning and adaptive viral marketing, can be formulated as an adaptive submodular maximization problem. Most of existing studies on adaptive submodular optimization focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, \cite{golovin2011adaptive} developed a greedy policy that achieves a $(1-1/e)$ approximation ratio subject to a cardinality constraint. If the utility function is non-monotone and adaptive submodular, \cite{tang2021beyond} showed that a random greedy policy achieves a $1/e$ approximation ratio subject to a cardinality constraint. In this work, we aim to generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio $m\in[0,1]$ to measure the degree of monotonicity of a function. Our main result is to show that a random greedy policy achieves an approximation ratio of $m(1-1/e)+(1-m)(1/e)$ if the utility function is $m$-adaptive monotone and adaptive submodular. Notably this result recovers the aforementioned $(1-1/e)$ and $1/e$ approximation ratios when $m = 0$ and $m = 1$, respectively. We further extend our results to consider a knapsack constraint. We show that a sampling-based policy achieves an approximation ratio of $(m+1)/10$ if the utility function is $m$-adaptive monotone and adaptive submodular. One important implication of our results is that even for a non-monotone utility function, we still can achieve an approximation ratio close to $(1-1/e)$ if this function is ``close'' to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.
• Abstract（参考訳）: プールベースのアクティブラーニングや適応型バイラルマーケティングを含む多くの逐次意思決定問題は、適応型サブモジュラー最大化問題として定式化することができる。 適応部分モジュラー最適化に関する既存の研究の多くは、モノトーンの場合か非モノトーンの場合に焦点をあてている。 具体的には、効用関数が単調かつ適応的な部分モジュラーである場合、\cite{golovin2011adaptive} は濃度制約に従属する$(1-1/e)$近似比を達成する欲望ポリシーを開発した。 実用関数が非単調で適応部分モジュラーであれば、無作為な欲求ポリシーが濃度制約を受ける近似比1/e$を達成することを示した。 本研究では,上述の結果を部分単調適応部分モジュラー最大化問題を用いて一般化する。 この目的のために、関数の単調度を測定するために、適応単調度比$m\in[0,1]$の表記を導入する。 我々の主な結果は、ランダムな欲望ポリシーが、ユーティリティ関数が$m$-adaptive monotoneとadaptive submodularであれば、$m(1-1/e)+(1-m)(1/e)$という近似比を達成することを示すことである。 この結果は、それぞれ$m = 0$ と $m = 1$ のとき、前述の $(1-1/e)$ と 1/e$ の近似比を回復する。 結果をさらに拡張して、knapsack制約を検討する。 実効関数が$m$-adaptive monotoneとadaptive submodularであれば、サンプリングベースのポリシーが$(m+1)/10$の近似比を達成できることを示す。 結果の重要な意味は、非単調効用関数であっても、この関数が単調関数に対して ``close'' であれば、$(1-1/e)$ に近い近似比が得られるということである。 これにより、ユーティリティ関数がほぼ適応単調である多くの機械学習アプリケーションのパフォーマンス境界が改善される。

関連論文リスト

• 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)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  適応部分モジュラ函数の最小コスト被覆の問題を考える。 このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
  論文  参考訳（メタデータ） (2022-08-17T15:26:47Z)
• 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)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• 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)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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