論文の概要: Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity
- arxiv url: http://arxiv.org/abs/2102.08327v1
- Date: Tue, 16 Feb 2021 18:15:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 14:49:33.337228
- Title: Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity
- Title（参考訳）: ナップサック制約を受ける部分モジュラ最大化:近最適適応複雑性を有するコンビナールアルゴリズム
- Authors: Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi,
Alberto Marchetti Spaccamela, Rebecca Reiffenh\"auser
- Abstract要約: knap制約を満たした非単調部分モジュラー対象に対する最初の emphconstant factor approximation algorithm を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で修正できる。
これはまた、問題に対する非線形適応的複雑さを持つ最初の組換えアプローチである。
- 参考スコア（独自算出の注目度）: 12.472204825917625
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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}, capturing the
number of sequential rounds of parallel computation needed. 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: one needs to account for the total number of function
evaluations (or value queries) as well. 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. Finally, we showcase our algorithms'
applicability on real-world datasets.
- Abstract（参考訳）: 大規模なインスタンスを扱う必要性の増大は、ソリューションの品質と適用可能性のバランスをとるアルゴリズムの設計を動機付ける。
後者にとって重要な測度は \emph{adaptive complexity} であり、必要な並列計算の逐次ラウンドの数をキャプチャする。
本研究では, \emph{near-optimal} $O(\log n)$ 適応的複雑性を伴うナップサック制約を受ける非モノトーン部分モジュラ最大化に対する,最初の \emph{constant factor} 近似アルゴリズムを得る。
機能評価(または値クエリ)の総数も考慮する必要があります。
我々のアルゴリズムは$\tilde{O}(n^2)$の値クエリを問うが、代わりに$\tilde{O}(n)$だけを実行するように修正できる。
上記の適応性の改善に加えて、この問題に対する部分線形適応的複雑性を持つ最初の \emph{combinatorial} アプローチであり、濃度制約や単調目的の特別な場合であっても、最先端に匹敵するアルゴリズムが得られる。
最後に,実世界のデータセットに対するアルゴリズムの適用性を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - 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) - Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
論文 参考訳（メタデータ） (2023-08-21T11:48:34Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - 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) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。