論文の概要: Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes
- arxiv url: http://arxiv.org/abs/2111.14148v1
- Date: Sun, 28 Nov 2021 14:08:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-30 19:04:40.907157
- Title: Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes
- Title(参考訳): 行列点過程の積に対する正規化定数の計算複雑性
- Authors: Naoto Ohsaka and Tatsuya Matsuoka
- Abstract要約: 正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
- 参考スコア(独自算出の注目度): 12.640283469603357
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the product of determinantal point processes (DPPs), a point
process whose probability mass is proportional to the product of principal
minors of multiple matrices, as a natural, promising generalization of DPPs. We
study the computational complexity of computing its normalizing constant, which
is among the most essential probabilistic inference tasks. Our
complexity-theoretic results (almost) rule out the existence of efficient
algorithms for this task unless the input matrices are forced to have favorable
structures. In particular, we prove the following:
(1) Computing $\sum_S\det({\bf A}_{S,S})^p$ exactly for every (fixed)
positive even integer $p$ is UP-hard and Mod$_3$P-hard, which gives a negative
answer to an open question posed by Kulesza and Taskar.
(2) $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})\det({\bf C}_{S,S})$ is
NP-hard to approximate within a factor of $2^{O(|I|^{1-\epsilon})}$ or
$2^{O(n^{1/\epsilon})}$ for any $\epsilon>0$, where $|I|$ is the input size and
$n$ is the order of the input matrix. This result is stronger than the
#P-hardness for the case of two matrices derived by Gillenwater.
(3) There exists a $k^{O(k)}n^{O(1)}$-time algorithm for computing
$\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})$, where $k$ is the maximum rank
of $\bf A$ and $\bf B$ or the treewidth of the graph formed by nonzero entries
of $\bf A$ and $\bf B$. Such parameterized algorithms are said to be
fixed-parameter tractable.
These results can be extended to the fixed-size case. Further, we present two
applications of fixed-parameter tractable algorithms given a matrix $\bf A$ of
treewidth $w$:
(4) We can compute a $2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf
A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time.
(5) We can find a $2^{\sqrt n}$-approximation to unconstrained MAP inference
in $w^{O(w\sqrt n)}n^{O(1)}$ time.
- Abstract(参考訳): 行列点過程(Determinantal point process, DPPs)の積は、確率質量が複数の行列の主部分の積に比例する点過程であり、DPPの自然な有望な一般化である。
本稿では,その正規化定数を計算する計算複雑性について検討する。
私たちの複雑性理論的な結果は(ほとんど)、入力行列が好ましい構造を強制されない限り、このタスクのための効率的なアルゴリズムの存在を除外します。
特に、(1)すべての(固定)正の偶数整数$p$がアップハードで mod$_3$p-hard に対して、$\sum_s\det({\bf a}_{s,s})^p$を正確に計算すると、kulesza と taskar によってなされるオープン質問に対する否定的な答えが得られる。
2)$\sum_s\det({\bf a}_{s,s})\det({\bf b}_{s,s})\det({\bf c}_{s,s})$は$2^{o(|i|^{1-\epsilon})}$または$2^{o(n^{1/\epsilon})}$任意の$\epsilon>0$、ただし$|i|$は入力サイズ、$n$は入力行列の順序である。
この結果は、ギレンウォーター由来の2つの行列の場合の#P硬度よりも強い。
(3) $\sum_s\det({\bf a}_{s,s})\det({\bf b}_{s,s})$を計算するための$k^{o(k)}n^{o(1)}$-timeアルゴリズムがあり、ここで$k$は$\bf a$と$\bf b$の最大ランクである。
このようなパラメータ化アルゴリズムは固定パラメータ扱い可能であると言われている。
これらの結果は固定サイズのケースに拡張できる。
さらに、行列 $\bf A$ of treewidth $w$: (4)$2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time を計算できる。
(5)$w^{o(w\sqrt n)}n^{o(1)}$ time で制約のない写像推論に近似する 2^{\sqrt n}$-approximation を見つけることができる。
関連論文リスト
- Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳(メタデータ) (2023-04-10T05:52:38Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳(メタデータ) (2023-02-26T02:42:39Z) - Additive estimates of the permanent using Gaussian fields [0.0]
本稿では,M$M$実行列$A$から加法誤差までの永久性を推定するランダム化アルゴリズムを提案する。
我々は$mathrmperm(A)$を$epsilonbigg(sqrt32Mprod2M_i=1 C_iibigg)$の加算誤差に時間内に見積もることができる。
論文 参考訳(メタデータ) (2022-12-20T22:13:42Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - 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) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳(メタデータ) (2020-02-17T21:32:04Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。