論文の概要: Simultaenous Sieves: A Deterministic Streaming Algorithm for
Non-Monotone Submodular Maximization
- arxiv url: http://arxiv.org/abs/2010.14367v3
- Date: Mon, 2 Nov 2020 15:35:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 12:58:46.535258
- Title: Simultaenous Sieves: A Deterministic Streaming Algorithm for
Non-Monotone Submodular Maximization
- Title(参考訳): Simultaenous Sieves:非モノトン部分モジュラー最大化のための決定論的ストリーミングアルゴリズム
- Authors: Alan Kuhnle
- Abstract要約: 定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。
単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
- 参考スコア(独自算出の注目度): 16.346069386394703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we present a combinatorial, deterministic single-pass streaming
algorithm for the problem of maximizing a submodular function, not necessarily
monotone, with respect to a cardinality constraint (SMCC). In the case the
function is monotone, our algorithm reduces to the optimal streaming algorithm
of Badanidiyuru et al. (2014). In general, our algorithm achieves ratio $\alpha
/ (1 + \alpha) - \varepsilon$, for any $\varepsilon > 0$, where $\alpha$ is the
ratio of an offline (deterministic) algorithm for SMCC used for
post-processing. Thus, if exponential computation time is allowed, our
algorithm deterministically achieves nearly the optimal $1/2$ ratio. These
results nearly match those of a recently proposed, randomized streaming
algorithm that achieves the same ratios in expectation. For a deterministic,
single-pass streaming algorithm, our algorithm achieves in polynomial time an
improvement of the best approximation factor from $1/9$ of previous literature
to $\approx 0.2689$.
- Abstract(参考訳): 本研究では,濃度制約(SMCC)に関して,必ずしも単調ではない部分モジュラ関数を最大化する問題に対して,組合せ的決定論的単一パスストリーミングアルゴリズムを提案する。
関数がモノトーンの場合、アルゴリズムはバダニディユルら(2014)の最適なストリーミングアルゴリズムに還元される。
一般に、このアルゴリズムは$\alpha / (1 + \alpha) - \varepsilon$、任意の$\varepsilon > 0$に対して、$\alpha$は後処理に使用されるsmccのオフライン(決定論的)アルゴリズムの比率である。
したがって、指数計算時間が許された場合、アルゴリズムは決定論的に最適な1/2$比を達成する。
これらの結果は、最近提案されたランダムなストリーミングアルゴリズムとほぼ一致し、予測の同じ比率を達成する。
決定論的で単一パスのストリーミングアルゴリズムでは、多項式時間で、最良近似係数を以前の文献の1/9ドルから約 0.2689$に改善する。
関連論文リスト
- 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) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time [16.346069386394703]
単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
論文 参考訳(メタデータ) (2020-09-10T16:35:54Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳(メタデータ) (2020-09-03T22:43:55Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。