Fugu-MT 論文翻訳(概要): Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate

論文の概要: Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate

arxiv url: http://arxiv.org/abs/2102.12646v1
Date: Thu, 25 Feb 2021 02:45:10 GMT
ステータス: 処理完了
システム内更新日: 2021-02-26 13:41:40.820452
Title: Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
Title（参考訳）: Spanning Tree Constrained Determinantal Point Processs is hard to a approximately (Avaluate)
Authors: Tatsuya Matsuoka and Naoto Ohsaka
Abstract要約: 我々は,木にまたがる決定的点過程を考える。我々は$sharptextP$-hardness of computing the normalizing constant for spanning-tree DPPsを証明した。森林に制約されたDPPについても同様の結果を示した。
参考スコア（独自算出の注目度）: 12.640283469603357
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such that we draw $S\subseteq E$ with probability proportional to $\det(\mathbf{A}_S)$ only if $S$ induces a spanning tree. We prove $\sharp\textsf{P}$-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.
Abstract（参考訳）: 決定点過程 (DPPs) は, 木を分散させることによって制約される。グラフ $G=(V,E)$ と正半定値行列 $\mathbf{A}$ が$E$ でインデックスされたとき、スパンニングツリー DPP は、$S\subseteq E$ が $\det(\mathbf{A}_S)$ に比例する確率を持つような分布を定義する。我々はspanning-tree dppsの正規化定数を計算するための$\sharp\textsf{p}$-hardnessを証明し、fprasが知られていない混合判別式からの近似保存還元を提供する。森林に制約されたDPPについても同様の結果を示した。

関連論文リスト

On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文参考訳（メタデータ） (2023-03-10T00:11:18Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
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)
Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文参考訳（メタデータ） (2022-10-12T16:25:48Z)
Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文参考訳（メタデータ） (2022-03-24T08:14:12Z)
FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。 $cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。 $mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文参考訳（メタデータ） (2021-10-19T17:43:50Z)
Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文参考訳（メタデータ） (2021-10-07T05:49:55Z)
Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文参考訳（メタデータ） (2021-06-03T07:22:48Z)
Approximating the Log-Partition Function [16.59989033959959]
基礎となるグラフ構造の性質を通じて近似比を定量化する手法を提案する。グラフの有効抵抗を最小に抑えた平方根の逆に等しい近似比を実現するニアリニアタイム変量を提供する。
論文参考訳（メタデータ） (2021-02-19T22:57:32Z)
Testing Determinantal Point Processes [0.0]
配電体の特性試験という新たな視点からDPPについて検討する。 DPPをテストするための最初のアルゴリズムを提案する。より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
論文参考訳（メタデータ） (2020-08-09T04:45:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。