論文の概要: Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2104.04853v1
- Date: Sat, 10 Apr 2021 20:11:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-15 07:19:41.090806
- Title: Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint
- Title（参考訳）: 点的部分モジュラリティを超えて:クナップサック制約を受ける非単調適応部分モジュラー最大化
- Authors: Shaojie Tang
- Abstract要約: ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
- 参考スコア（独自算出の注目度）: 26.171841086317574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the non-monotone adaptive submodular maximization
problem subject to a knapsack constraint. The input of our problem is a set of
items, where each item has a particular state drawn from a known prior
distribution. However, the state of an item is initially unknown, one must
select an item in order to reveal the state of that item. Moreover, each item
has a fixed cost. There is a utility function which is defined over items and
states. Our objective is to sequentially select a group of items to maximize
the expected utility subject to a knapsack constraint. Although the
cardinality-constrained, as well as the more general matroid-constrained,
adaptive submodular maximization has been well studied in the literature,
whether there exists a constant approximation solution for the
knapsack-constrained adaptive submodular maximization problem remains an open
problem. We fill this gap by proposing the first constant approximation
solution. In particular, our main contribution is to develop a sampling-based
randomized algorithm that achieves a $\frac{1}{10}$ approximation for
maximizing an adaptive submodular function subject to a knapsack constraint.
- Abstract（参考訳）: 本稿では,knapsack制約を受ける非単調適応部分モジュラー最大化問題について検討する。
問題の入力は項目の集合であり、各項目は既知の事前分布から引き出された特定の状態を持つ。
しかしながら、アイテムの状態は当初不明であり、アイテムの状態を明らかにするためにアイテムを選択する必要がある。
さらに、各アイテムには固定コストがある。
アイテムとステートの上に定義されたユーティリティ関数があります。
本研究の目的は,knapsack制約の対象となる実用性を最大化するために,項目群を順次選択することである。
より一般的なマトロイド拘束型適応サブモジュラー最大化と同様に濃度制限された適応サブモジュラー最大化は文献でよく研究されているが、クナプサック拘束適応サブモジュラー最大化問題に対する定数近似解が存在するかどうかは未解決のままである。
このギャップを埋めるために、最初の定数近似解を提案する。
特に,ナップサック制約を受ける適応部分モジュラ関数を最大化するための$\frac{1}{10}$近似を実現するサンプリングに基づくランダム化アルゴリズムの開発に寄与した。
関連論文リスト
- Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-07T15:12:02Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
論文 参考訳（メタデータ） (2022-02-28T12:26:47Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳（メタデータ） (2021-11-01T21:06:35Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Adaptive Cascade Submodular Maximization [19.29174615532181]
本研究では,適応条件下でのカスケード部分モジュラー問題について検討する。
本研究の目的は,選択項目の有効性を最大化するために,選択項目の最適シーケンスを特定することである。
論文 参考訳（メタデータ） (2020-07-07T16:21:56Z) - 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) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。