論文の概要: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack
Constraint
- arxiv url: http://arxiv.org/abs/2007.05014v1
- Date: Thu, 9 Jul 2020 18:15:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 05:17:55.142068
- Title: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack
Constraint
- Title（参考訳）: ナップサック制約を受ける高速適応型非単調サブモジュラー最大化
- Authors: Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi,
Rebecca Reiffenh\"auser
- Abstract要約: 我々は5.83ドルの近似を達成し、O(n log n)$ time, 少なくとも$n$を他の最先端アルゴリズムよりも高速に実行するグリーディアルゴリズムを提案する。
提案アルゴリズムの実験的評価は,実データおよび合成データ上での性能向上を示す。
- 参考スコア（独自算出の注目度）: 14.077478685398379
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constrained submodular maximization problems encompass a wide variety of
applications, including personalized recommendation, team formation, and
revenue maximization via viral marketing. The massive instances occurring in
modern day applications can render existing algorithms prohibitively slow,
while frequently, those instances are also inherently stochastic. Focusing on
these challenges, we revisit the classic problem of maximizing a (possibly
non-monotone) submodular function subject to a knapsack constraint. We present
a simple randomized greedy algorithm that achieves a $5.83$ approximation and
runs in $O(n \log n)$ time, i.e., at least a factor $n$ faster than other
state-of-the-art algorithms. The robustness of our approach allows us to
further transfer it to a stochastic version of the problem. There, we obtain a
$9$-approximation to the best adaptive policy, which is the first constant
approximation for non-monotone objectives. Experimental evaluation of our
algorithms showcases their improved performance on real and synthetic data.
- Abstract（参考訳）: 制限付きサブモジュラー最大化問題は、パーソナライズドレコメンデーション、チーム形成、バイラルマーケティングによる収益最大化など、幅広い応用を包含している。
現代のアプリケーションで発生する巨大なインスタンスは、既存のアルゴリズムを違法に遅くするが、それらのインスタンスは本質的に確率的でもある。
これらの課題に着目し,ナップサック制約を受ける(多分単調でない)部分モジュラー関数を最大化する古典的な問題を再考する。
5.83$の近似を達成し、o(n \log n)$の時間、すなわち、他の最先端のアルゴリズムよりも少なくとも1倍の速さで実行される単純なランダム化グリーディアルゴリズムを提案する。
私たちのアプローチの堅牢性は、問題を確率的なバージョンにさらに移すことを可能にします。
そこでは,非単調な目的に対する最初の定数近似である最適適応ポリシーに対する9ドル近似を得る。
提案アルゴリズムの実験的評価は,実データおよび合成データの性能向上を示す。
関連論文リスト
- Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。
我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文 参考訳（メタデータ） (2024-09-06T17:17:52Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。