論文の概要: Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint
- arxiv url: http://arxiv.org/abs/2009.01947v5
- Date: Mon, 19 Feb 2024 19:16:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 22:06:39.360331
- Title: Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint
- Title（参考訳）: サイズ制約付き非単調部分モジュラー最大化のための実用的並列化アルゴリズム
- Authors: Yixin Chen and Alan Kuhnle
- Abstract要約: サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
- 参考スコア（独自算出の注目度）: 20.104148319012854
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present combinatorial and parallelizable algorithms for maximization of a
submodular function, not necessarily monotone, with respect to a size
constraint. We improve the best approximation factor achieved by an algorithm
that has optimal adaptivity and nearly optimal query complexity to $0.193 -
\varepsilon$. The conference version of this work mistakenly employed a
subroutine that does not work for non-monotone, submodular functions. In this
version, we propose a fixed and improved subroutine to add a set with high
average marginal gain, ThreshSeq, which returns a solution in $O( \log(n) )$
adaptive rounds with high probability. Moreover, we provide two approximation
algorithms. The first has approximation ratio $1/6 - \varepsilon$, adaptivity
$O( \log (n) )$, and query complexity $O( n \log (k) )$, while the second has
approximation ratio $0.193 - \varepsilon$, adaptivity $O( \log^2 (n) )$, and
query complexity $O(n \log (k))$. 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（参考訳）: サイズ制約に関して、必ずしも単調ではない部分モジュラ函数を最大化するための組合せおよび並列化可能なアルゴリズムを提案する。
最適な適応性とほぼ最適なクエリ複雑性を持つアルゴリズムによって達成される最適な近似係数を0.193\varepsilon$に改善する。
この研究のカンファレンスバージョンでは、非単調な部分モジュラー関数では機能しないサブルーチンを誤って採用した。
このバージョンでは、高い平均マージンゲインを持つ集合 threshseq を追加するために、固定および改良されたサブルーチンを提案し、これは高い確率で$o( \log(n) )$適応ラウンドで解を返す。
さらに2つの近似アルゴリズムを提案する。
1つは近似比1/6 - \varepsilon$、アダプティビティ$O( \log (n) )$、クエリ複雑性$O(n \log (k) )$、もう1つは近似比$0.193 - \varepsilon$、アダプティ$O( \log^2 (n) )$、クエリ複雑性$O(n \log (k))$である。
提案アルゴリズムは,多線形拡張を用いた連続アルゴリズムを含む最先端近似アルゴリズムと比較して,目標値の高い解を得た上で,適応ラウンド数や総クエリ数が少ないことを実証的に検証する。
関連論文リスト
- 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。