論文の概要: Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint
- arxiv url: http://arxiv.org/abs/2309.12025v1
- Date: Thu, 21 Sep 2023 12:42:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-22 15:30:26.089734
- Title: Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint
- Title（参考訳）: ナップサック制約下における非単調$k$-submodular maximizationに対するロバスト近似アルゴリズム
- Authors: Dung T.K. Ha, Canh V. Pham, Tan D. Tran, and Huan X. Hoang
- Abstract要約: 2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of non-monotone $k$-submodular maximization under a knapsack
constraint ($\kSMK$) over the ground set size $n$ has been raised in many
applications in machine learning, such as data summarization, information
propagation, etc. However, existing algorithms for the problem are facing
questioning of how to overcome the non-monotone case and how to fast return a
good solution in case of the big size of data. This paper introduces two
deterministic approximation algorithms for the problem that competitively
improve the query complexity of existing algorithms.
Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within
$O(nk)$ query complexity. The second one, $\RLA$, improves the approximation
ratio to $1/5-\epsilon$ in $O(nk)$ queries, where $\epsilon$ is an input
parameter.
Our algorithms are the first ones that provide constant approximation ratios
within only $O(nk)$ query complexity for the non-monotone objective. They,
therefore, need fewer the number of queries than state-of-the-the-art ones by a
factor of $\Omega(\log n)$.
Besides the theoretical analysis, we have evaluated our proposed ones with
several experiments in some instances: Influence Maximization and Sensor
Placement for the problem. The results confirm that our algorithms ensure
theoretical quality as the cutting-edge techniques and significantly reduce the
number of queries.
- Abstract（参考訳）: knapsack制約の下での非単調な$k$-submodular maximization($\kSMK$)の問題は、データ要約や情報伝搬など、機械学習の多くのアプリケーションで提起されている。
しかし、この問題に対する既存のアルゴリズムは、非モノトーンケースの克服方法と、データのサイズが大きければ迅速に解決策を返却する方法に疑問を呈している。
本稿では,既存のアルゴリズムの問合せ複雑性を競争的に改善する2つの決定論的近似アルゴリズムを提案する。
最初のアルゴリズムである$\laa$は、$o(nk)$のクエリ複雑性内で1/19$の近似率を返す。
2番目の$\rla$は近似比を$o(nk)$クエリで$/5-\epsilon$に改善し、$\epsilon$は入力パラメータである。
我々のアルゴリズムは、非単調目的に対して$o(nk)$のクエリ複雑性で一定の近似比を提供する最初のアルゴリズムである。
したがって、それらは最先端のクエリよりも$\Omega(\log n)$の要素でクエリの数を減らす必要がある。
理論的解析の他に、いくつかの事例においていくつかの実験を行い、問題に対する最大化とセンサ配置の影響を評価した。
その結果,本アルゴリズムは最先端技術として理論的品質を確保し,クエリ数を大幅に削減できることを確認した。
関連論文リスト
- Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - 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) - 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) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - 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) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。