論文の概要: Submodular Maximization in Clean Linear Time
- arxiv url: http://arxiv.org/abs/2006.09327v5
- Date: Tue, 12 Apr 2022 11:23:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 21:42:39.292801
- Title: Submodular Maximization in Clean Linear Time
- Title（参考訳）: クリーン線形時間におけるサブモジュラー最大化
- Authors: Wenxin Li, Moran Feldman, Ehsan Kazemi, Amin Karbasi
- Abstract要約: 我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
- 参考スコア（独自算出の注目度）: 42.51873363778082
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we provide the first deterministic algorithm that achieves the
tight $1-1/e$ approximation guarantee for submodular maximization under a
cardinality (size) constraint while making a number of queries that scales only
linearly with the size of the ground set $n$. To complement our result, we also
show strong information-theoretic lower bounds. More specifically, we show that
when the maximum cardinality allowed for a solution is constant, no algorithm
making a sub-linear number of function evaluations can guarantee any constant
approximation ratio. Furthermore, when the constraint allows the selection of a
constant fraction of the ground set, we show that any algorithm making fewer
than $\Omega(n/\log(n))$ function evaluations cannot perform better than an
algorithm that simply outputs a uniformly random subset of the ground set of
the right size. We then provide a variant of our deterministic algorithm for
the more general knapsack constraint, which is the first linear-time algorithm
that achieves $1/2$-approximation guarantee for this constraint. Finally, we
extend our results to the general case of maximizing a monotone submodular
function subject to the intersection of a $p$-set system and multiple knapsack
constraints. We extensively evaluate the performance of our algorithms on
multiple real-life machine learning applications, including movie
recommendation, location summarization, twitter text summarization and video
summarization.
- Abstract（参考訳）: 本稿では, 基数(サイズ)制約下でのサブモジュラー最大化の厳密な1-1/e$近似を保証するとともに, 基底集合の$n$と線形にしかスケールしないクエリを多数生成する決定論的アルゴリズムを提案する。
その結果を補完するために,強い情報理論の下界を示す。
より具体的には、解に許容される最大濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムが任意の定数近似比を保証できないことを示す。
さらに、制約が基底集合の定数数の選択を許す場合、$\Omega(n/\log(n))$関数評価より小さい任意のアルゴリズムは、正しい大きさの基底集合の一様ランダムな部分集合を単純に出力するアルゴリズムよりも優れた性能を発揮できないことを示す。
次に、より一般的なknapsack制約に対する決定論的アルゴリズムの変種を提供し、この制約に対して1/2$-近似を保証する最初の線形時間アルゴリズムである。
最後に、この結果は、$p$-set 系と複数のknapsack 制約の交叉を受ける単調部分モジュラ函数を最大化する一般の場合にまで拡張する。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数の実生活機械学習アプリケーションにおけるアルゴリズムの性能を広範囲に評価した。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Randomized Algorithms for Monotone Submodular Function Maximization on
the Integer Lattice [5.543220407902113]
濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。
特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。
提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
論文 参考訳（メタデータ） (2021-11-19T12:07:16Z) - 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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。