論文の概要: Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity
- arxiv url: http://arxiv.org/abs/2102.08327v2
- Date: Fri, 20 Oct 2023 08:22:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-26 04:09:20.811973
- 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要約: 我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
- 参考スコア（独自算出の注目度）: 13.416309759182635
- 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 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 constant factor approximation algorithm for
non-monotone submodular maximization subject to a knapsack constraint with
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 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)は、データマイニングや機械学習のさまざまな応用において、古典的なアルゴリズムの問題である。
後者にとって重要な尺度は適応的複雑性(adaptive complexity)であり、アルゴリズムが終了するのに必要な並列計算の逐次ラウンド数をキャプチャする。
この研究において、準最適$O(\log n)$適応複雑性を持つクナプサック制約を受ける非単調な極大化に対する最初の定数係数近似アルゴリズムを得る。
考慮すべき重要な機能は、機能評価(あるいは値クエリ)の総数によって表される。
我々のアルゴリズムは$\tilde{O}(n^2)$の値クエリを問うが、代わりに$\tilde{O}(n)$だけを実行するように修正できる。
上記の適応性の改善に加えて、これは問題に対して部分線形適応的複雑性を持つ最初の組合せアプローチであり、濃度制約や単調目的の特別な場合であっても最先端のアルゴリズムに匹敵する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。