論文の概要: Some Inapproximability Results of MAP Inference and Exponentiated
Determinantal Point Processes
- arxiv url: http://arxiv.org/abs/2109.00727v1
- Date: Thu, 2 Sep 2021 05:45:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-03 14:02:58.994227
- Title: Some Inapproximability Results of MAP Inference and Exponentiated
Determinantal Point Processes
- Title（参考訳）: MAP推論と指数決定点過程の不適合性
- Authors: Naoto Ohsaka
- Abstract要約: 決定点過程(DPP)における2つの難解問題の計算複雑性について検討する。
1つは最大部分行列(MAP指数)であり、最大部分行列は最大部分行列である。
もう1つはDPP(E-DPPs)の確率的推測である
E-DPPのMAP推論と正規化定数の近似の難しさを説明した複雑性理論的難易度の結果を以下に示す。
- 参考スコア（独自算出の注目度）: 8.832969171530056
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the computational complexity of two hard problems on determinantal
point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to
find a principal submatrix having the maximum determinant. The other is
probabilistic inference on exponentiated DPPs (E-DPPs), which can sharpen or
weaken the diversity preference of DPPs with an exponent parameter $p$. We
prove the following complexity-theoretic hardness results that explain the
difficulty in approximating MAP inference and the normalizing constant for
E-DPPs.
1. Unconstrained MAP inference for an $n \times n$ matrix is NP-hard to
approximate within a factor of $2^{\beta n}$, where $\beta = 10^{-10^{13}} $.
This result improves upon a $(\frac{9}{8}-\epsilon)$-factor inapproximability
given by Kulesza and Taskar (2012).
2. Log-determinant maximization is NP-hard to approximate within a factor of
$\frac{5}{4}$ for the unconstrained case and within a factor of
$1+10^{-10^{13}}$ for the size-constrained monotone case.
3. The normalizing constant for E-DPPs of any (fixed) constant exponent $p
\geq \beta^{-1} = 10^{10^{13}}$ is NP-hard to approximate within a factor of
$2^{\beta pn}$. This gives a(nother) negative answer to open questions posed by
Kulesza and Taskar (2012); Ohsaka and Matsuoka (2020).
- Abstract（参考訳）: 決定点過程(DPP)における2つの難解問題の計算複雑性について検討する。
1つは、最大決定基を持つ主部分行列を見つけるために、最大後続(MAP)推論である。
もう1つは指数パラメータ$p$で DPPs の多様性の選好を鋭くまたは弱めることができる指数 DPPs (E-DPPs) に関する確率的推論である。
E-DPPのMAP推論と正規化定数の近似の難しさを説明した複雑性理論的難易度の結果を以下に示す。
1.
$n \times n$Matrix に対する非制約MAP推論は、NPハードで$2^{\beta n}$ の係数で近似し、$\beta = 10^{-10^{13}} $ となる。
この結果は、Kulesza と Taskar (2012) によって与えられる $(\frac{9}{8}-\epsilon)$-factor inapproximability によって改善される。
2.
対数行列の最大化は、非制約の場合の$\frac{5}{4}$とサイズ制約のモノトンの場合の$+10^{-10^{13}}$に近似するNPハードである。
3.
固定された)定数指数 $p \geq \beta^{-1} = 10^{10^{13}}$ の E-DPP の正規化定数は、NP-ハードで、2^{\beta pn}$ の係数で近似する。
これは Kulesza と Taskar (2012)、Ohsaka と Matsuoka (2020) によるオープンな質問に対する否定的な回答を与える。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - 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) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Hardness of Maximum Likelihood Learning of DPPs [25.06251462216571]
与えられたデータセットに対して最大極大 DPP モデルを求める問題は NP-完全である、というクレスザの予想を証明する。
技術面では、データセット上のDPPの最大ログ類似度を減らし、ハイパーグラフ上の「ベクトル」問題のギャップを解消する。
論文 参考訳（メタデータ） (2022-05-24T21:46:23Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - TensorPlan and the Few Actions Lower Bound for Planning in MDPs under
Linear Realizability of Optimal Value Functions [0.0]
我々は,オンラインプランニングにおけるミニマックスクエリの複雑さを,固定水平決定プロセスにおける生成モデルを用いて検討する。
A=Omega(min(d1/4,H1/2)) が指数的に大きい下界を持つことを示す。
論文 参考訳（メタデータ） (2021-10-05T17:42:46Z) - SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。
SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
論文 参考訳（メタデータ） (2021-01-07T03:14:05Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。