論文の概要: A Faster Sampler for Discrete Determinantal Point Processes
- arxiv url: http://arxiv.org/abs/2210.17358v1
- Date: Mon, 31 Oct 2022 14:37:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 15:56:41.932641
- Title: A Faster Sampler for Discrete Determinantal Point Processes
- Title（参考訳）: 離散決定点過程のための高速サンプリング器
- Authors: Simon Barthelm\'e, Nicolas Tremblay and Pierre-Olivier Amblard
- Abstract要約: Discrete Determinantal Point Processs (DPP) は、データセットのサブサンプル化に幅広い可能性を持つ。
最悪の場合、サンプリングコストは$O(n3)$で、nは基底集合の要素の数である。
この禁止コストに対する一般的な回避策は、低ランクカーネルによって定義されたDPPをサンプリングすることである。
- 参考スコア（独自算出の注目度）: 10.355938901584567
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Discrete Determinantal Point Processes (DPPs) have a wide array of potential
applications for subsampling datasets. They are however held back in some cases
by the high cost of sampling. In the worst-case scenario, the sampling cost
scales as $O(n^3)$ where n is the number of elements of the ground set. A
popular workaround to this prohibitive cost is to sample DPPs defined by
low-rank kernels. In such cases, the cost of standard sampling algorithms
scales as $O(np^2 + nm^2)$ where m is the (average) number of samples of the
DPP (usually $m \ll n$) and p ($m \leq p \leq n$) the rank of the kernel used
to define the DPP. The first term, $O(np^2)$, comes from a SVD-like step. We
focus here on the second term of this cost, $O(nm^2)$, and show that it can be
brought down to $O(nm + m^3 log m)$ without loss on the sampling's exactness.
In practice, we observe extremely substantial speedups compared to the
classical algorithm as soon as $n > 1, 000$. The algorithm described here is a
close variant of the standard algorithm for sampling continuous DPPs, and uses
rejection sampling. In the specific case of projection DPPs, we also show that
any additional sample can be drawn in time $O(m^3 log m)$. Finally, an
interesting by-product of the analysis is that a realisation from a DPP is
typically contained in a subset of size $O(m log m)$ formed using leverage
score i.i.d. sampling.
- Abstract（参考訳）: Discrete Determinantal Point Processs (DPP) は、データセットのサブサンプル化に幅広い可能性を持つ。
しかし、サンプリングのコストが高い場合もあります。
最悪の場合、サンプリングコストは$O(n^3)$とスケールする。
この禁止コストに対する一般的な回避策は、低ランクカーネルによって定義されたDPPをサンプリングすることである。
そのような場合、標準的なサンプリングアルゴリズムのコストは$O(np^2 + nm^2)$で、ここで m は DPP (通常 $m \ll n$) のサンプルの(平均)数であり、p (m \leq p \leq n$) は DPP を定義するのに使用されるカーネルのランクである。
第一項の$O(np^2)$はSVDのようなステップに由来する。
ここでは、このコストの第二項である$O(nm^2)$に着目し、サンプリングの精度を損なうことなく$O(nm + m^3 log m)$にすることができることを示す。
実際、我々は古典的アルゴリズムと比較して、$n > 1, 000$ の速さで非常に大きなスピードアップを観測する。
ここで述べるアルゴリズムは、連続dppをサンプリングするための標準アルゴリズムの近縁な変種であり、拒絶サンプリングを使用する。
射影dppsの特定の場合、追加のサンプルは時間$o(m^3 log m)$で描画可能であることも示します。
最後に、分析の興味深い副産物は、DPP からの実現は通常、レバレッジスコア i.d. サンプリングを用いて形成される$O(m log m)$ のサブセットに含まれることである。
関連論文リスト
- Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
我々は、$k$-means++の量子実装を示し、その時間は$tildeO(zeta2 k2)$で実行される。
これは、量子バージョンが$O(logk)$近似を保証する$k$-means++の堅牢な近似解析によって示される。
これはQI-$k$-means++と呼ばれ、実行時間は$O(Nd) + tildeO(zeta)である。
論文 参考訳（メタデータ） (2024-05-22T05:13:28Z) - Weighted least-squares approximation with determinantal point processes and generalized volume sampling [33.33724208084121]
与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。
近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
論文 参考訳（メタデータ） (2023-12-21T17:34:18Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳（メタデータ） (2023-05-25T08:43:11Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。
最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。
低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-01T15:22:12Z) - Sampling from a $k$-DPP without looking at all items [58.30573872035083]
カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。
既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。
そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-06-30T16:40:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。