論文の概要: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack
Constraint
- arxiv url: http://arxiv.org/abs/2007.05014v2
- Date: Mon, 16 Oct 2023 12:21:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 07:27:03.081529
- 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要約: 我々は,knapsack制約を持つ非モノトン部分モジュラー複雑性に対する最初のEmphconstant Factor近似アルゴリズムを得る。
これはまた、この問題に対する部分線型適応アルゴリズムを持つ最初の例であり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
- 参考スコア（独自算出の注目度）: 13.357957711519134
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Submodular maximization is a classic algorithmic problem with multiple
applications in data mining and machine learning; there, the growing need to
deal with massive instances motivates the design of algorithms balancing the
quality of the solution with applicability. For the latter, an important
measure is the \emph{adaptive complexity}, which captures the number of
sequential rounds of parallel computation needed by an algorithm to terminate.
In this work, we obtain the first \emph{constant factor} approximation
algorithm for non-monotone submodular maximization subject to a knapsack
constraint with \emph{near-optimal} $O(\log n)$ adaptive complexity. Low
adaptivity by itself, however, is not enough: a crucial feature to account for
is represented by the total number of function evaluations (or value queries).
Our algorithm asks $\tilde{O}(n^2)$ value queries but can be modified to run
with only $\tilde{O}(n)$ instead while retaining a low adaptive complexity of
$O(\log^2n)$. Besides the above improvement in adaptivity, this is also the
first \emph{combinatorial} approach with sublinear adaptive complexity for the
problem and yields algorithms comparable to the state-of-the-art even for the
special cases of cardinality constraints or monotone objectives.
- Abstract（参考訳）: サブモジュラー最大化(submodular maximization)は、データマイニングや機械学習のさまざまな応用において、古典的なアルゴリズムの問題である。
後者にとって重要な尺度は \emph{adaptive complexity} であり、アルゴリズムが終了するために必要な並列計算の逐次ラウンドの数をキャプチャする。
本研究では、knapsack 制約を満たす非単調な極大化に対する最初の \emph{constant factor} 近似アルゴリズムを、 \emph{near-optimal} $O(\log n)$ 適応複雑性で得られる。
考慮すべき重要な機能は、機能評価(あるいは値クエリ)の総数によって表される。
このアルゴリズムは$\tilde{o}(n^2)$値クエリを要求するが、$o(\log^2n)$という適応的複雑性を低く保ちながら$\tilde{o}(n)$で実行するように修正することができる。
上記の適応性の改善に加えて、この問題に対する部分線形適応的複雑性を持つ最初の \emph{combinatorial} アプローチであり、濃度制約や単調目的の特別な場合であっても、最先端に匹敵するアルゴリズムが得られる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。