論文の概要: Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone
Submodular Maximization
- arxiv url: http://arxiv.org/abs/2009.01947v3
- Date: Mon, 8 Mar 2021 18:27:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 08:09:34.135671
- Title: Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone
Submodular Maximization
- Title（参考訳）: 非単調部分モジュラー最大化のための近似線形時間並列化アルゴリズム
- Authors: Alan Kuhnle
- Abstract要約: 単調ではない部分モジュラ函数の並列化複雑性を、濃度制約$k$に関して研究する。
我々は最適な適応性とクエリの複雑さを持つアルゴリズムによって達成される最適な近似係数を改善する。
我々のアルゴリズムのヒューリスティックバージョンは、適応ラウンドの少ないラウンドと総クエリを使用するように検証されている。
- 参考スコア（独自算出の注目度）: 16.346069386394703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study parallelizable algorithms for maximization of a submodular function,
not necessarily monotone, with respect to a cardinality constraint $k$. We
improve the best approximation factor achieved by an algorithm that has optimal
adaptivity and query complexity, up to logarithmic factors in the size $n$ of
the ground set, from $0.039 - \epsilon$ to $0.193 - \epsilon$. We provide two
algorithms; the first has approximation ratio $1/6 - \epsilon$, adaptivity $O(
\log n )$, and query complexity $O( n \log k )$, while the second has
approximation ratio $0.193 - \epsilon$, adaptivity $O( \log^2 n )$, and query
complexity $O(n \log k)$. Heuristic versions of our algorithms are empirically
validated to use a low number of adaptive rounds and total queries while
obtaining solutions with high objective value in comparison with
state-of-the-art approximation algorithms, including continuous algorithms that
use the multilinear extension.
- Abstract（参考訳）: 我々は、濃度制約 $k$ に関して、必ずしも単調ではない部分モジュラ関数の最大化のための並列化可能なアルゴリズムを研究した。
最適な適応性とクエリの複雑さを持つアルゴリズムによって達成された最良近似係数を、基底集合の大きさの対数係数である0.039 - \epsilon$ - $0.193 - \epsilon$ まで改善する。
1つは近似比1/6 - \epsilon$、適応性$o( \log n )$、クエリ複雑性$o(n \log k )$、もう1つは近似比$0.193 - \epsilon$、適応性$o( \log^2 n )$、クエリ複雑性$o(n \log k)$である。
提案アルゴリズムのヒューリスティックバージョンは,多線形拡張を用いた連続アルゴリズムを含む最先端近似アルゴリズムと比較して,高い目的値の解を得た上で,適応ラウンド数や全クエリ数が少ないことを実証的に検証した。
関連論文リスト
- 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) - Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-07-26T07:08:03Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - 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) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。