論文の概要: Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time
- arxiv url: http://arxiv.org/abs/2009.04979v3
- Date: Mon, 8 Mar 2021 17:49:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-20 04:12:21.879274
- Title: Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time
- Title（参考訳）: 線形時間における単調部分モジュラ関数の最大化のためのクイックストリーミングアルゴリズム
- Authors: Alan Kuhnle
- Abstract要約: 単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
- 参考スコア（独自算出の注目度）: 16.346069386394703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of monotone, submodular maximization over a ground
set of size $n$ subject to cardinality constraint $k$. For this problem, we
introduce the first deterministic algorithms with linear time complexity; these
algorithms are streaming algorithms. Our single-pass algorithm obtains a
constant ratio in $\lceil n / c \rceil + c$ oracle queries, for any $c \ge 1$.
In addition, we propose a deterministic, multi-pass streaming algorithm with a
constant number of passes that achieves nearly the optimal ratio with linear
query and time complexities. We prove a lower bound that implies no
constant-factor approximation exists using $o(n)$ queries, even if queries to
infeasible sets are allowed. An empirical analysis demonstrates that our
algorithms require fewer queries (often substantially less than $n$) yet still
achieve better objective value than the current state-of-the-art algorithms,
including single-pass, multi-pass, and non-streaming algorithms.
- Abstract（参考訳）: 単調な部分モジュラー極大化の問題を、濃度制約が$k$となる大きさの基底集合$n$の問題を考える。
この問題に対して,線形時間複雑性を持つ最初の決定論的アルゴリズムを導入する。
我々のシングルパスアルゴリズムは任意の$c \ge 1$に対して$\lceil n / c \rceil + c$ oracle クエリの定数比を得る。
さらに,線形クエリと時間複雑度との最適比をほぼ達成する,一定数のパスを持つ決定論的マルチパスストリーミングアルゴリズムを提案する。
不可能な集合に対するクエリが許されたとしても、$o(n)$クエリを使って定数係数近似が存在しないことを示す下界を証明する。
経験的分析により、我々のアルゴリズムはクエリが少ない(多くの場合、$n$未満)が、シングルパス、マルチパス、非ストリーミングアルゴリズムを含む現在の最先端アルゴリズムよりも客観的な価値が得られることを示した。
関連論文リスト
- The Cost of Consistency: Submodular Maximization with Constant Recourse [30.724711970113777]
特に,アルゴリズムが1ステップあたりの更新回数を最大で一定にした場合に達成可能な,最も有望な近似比を求める。
我々は、一般的な部分モジュラ函数に対して$tfrac23$の厳密な情報理論境界と、カバレッジ関数に対して$tfrac34$の改良された(かつ厳密な)境界を示す。
論文 参考訳（メタデータ） (2024-12-03T15:06:07Z) - Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization [13.86054078646307]
制約のある、必ずしも単調な部分モジュラーでなくても、比が1/e$より大きい全ての既知の近似アルゴリズムは連続的な考えを必要とする。
アルゴリズムでは, 単純なランダム化グレディアルゴリズムを用いて, サイズとマトロイドの制約の双方について最もよく知られた近似比を求める。
論文 参考訳（メタデータ） (2024-05-08T16:39:59Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Simultaenous Sieves: A Deterministic Streaming Algorithm for
Non-Monotone Submodular Maximization [16.346069386394703]
定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。
単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
論文 参考訳（メタデータ） (2020-10-27T15:22:49Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。