論文の概要: Efficient Distance Approximation for Structured High-Dimensional
Distributions via Learning
- arxiv url: http://arxiv.org/abs/2002.05378v2
- Date: Fri, 14 Feb 2020 03:03:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 13:50:20.165437
- Title: Efficient Distance Approximation for Structured High-Dimensional
Distributions via Learning
- Title(参考訳): 学習による高次元構造分布の効率的な距離近似
- Authors: Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, N. V.
Vinodchandran
- Abstract要約: 構成された高次元分布のいくつかのクラスに対する効率的な距離近似アルゴリズムを設計する。
我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
- 参考スコア(独自算出の注目度): 31.552581550603005
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We design efficient distance approximation algorithms for several classes of
structured high-dimensional distributions. Specifically, we show algorithms for
the following problems:
- Given sample access to two Bayesian networks $P_1$ and $P_2$ over known
directed acyclic graphs $G_1$ and $G_2$ having $n$ nodes and bounded in-degree,
approximate $d_{tv}(P_1,P_2)$ to within additive error $\epsilon$ using
$poly(n,\epsilon)$ samples and time
- Given sample access to two ferromagnetic Ising models $P_1$ and $P_2$ on
$n$ variables with bounded width, approximate $d_{tv}(P_1, P_2)$ to within
additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time
- Given sample access to two $n$-dimensional Gaussians $P_1$ and $P_2$,
approximate $d_{tv}(P_1, P_2)$ to within additive error $\epsilon$ using
$poly(n,\epsilon)$ samples and time
- Given access to observations from two causal models $P$ and $Q$ on $n$
variables that are defined over known causal graphs, approximate $d_{tv}(P_a,
Q_a)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples,
where $P_a$ and $Q_a$ are the interventional distributions obtained by the
intervention $do(A=a)$ on $P$ and $Q$ respectively for a particular variable
$A$.
Our results are the first efficient distance approximation algorithms for
these well-studied problems. They are derived using a simple and general
connection to distribution learning algorithms. The distance approximation
algorithms imply new efficient algorithms for {\em tolerant} testing of
closeness of the above-mentioned structured high-dimensional distributions.
- Abstract(参考訳): 我々は,構造化高次元分布のクラスに対して効率的な距離近似アルゴリズムを設計する。
Specifically, we show algorithms for the following problems: - Given sample access to two Bayesian networks $P_1$ and $P_2$ over known directed acyclic graphs $G_1$ and $G_2$ having $n$ nodes and bounded in-degree, approximate $d_{tv}(P_1,P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time - Given sample access to two ferromagnetic Ising models $P_1$ and $P_2$ on $n$ variables with bounded width, approximate $d_{tv}(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time - Given sample access to two $n$-dimensional Gaussians $P_1$ and $P_2$, approximate $d_{tv}(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time - Given access to observations from two causal models $P$ and $Q$ on $n$ variables that are defined over known causal graphs, approximate $d_{tv}(P_a, Q_a)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples, where $P_a$ and $Q_a$ are the interventional distributions obtained by the intervention $do(A=a)$ on $P$ and $Q$ respectively for a particular variable $A$.
我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
これらは分布学習アルゴリズムへの単純で一般的な接続を用いて導出される。
距離近似アルゴリズムは、上述した構造化高次元分布の近接性をテストするための新しい効率的なアルゴリズムである。
関連論文リスト
- Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳(メタデータ) (2023-06-20T06:13:56Z) - Beyond Moments: Robustly Learning Affine Transformations with
Asymptotically Optimal Error [8.615625517708324]
サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。
本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
論文 参考訳(メタデータ) (2023-02-23T19:13:30Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Empirical complexity of comparator-based nearest neighbor descent [0.0]
K$-nearest 隣り合うアルゴリズムの Java 並列ストリームの実装を示す。
Kullback-Leiblerの発散比較器による実験は、$K$-nearest近くの更新ラウンドの数が直径の2倍を超えないという予測を支持している。
論文 参考訳(メタデータ) (2022-01-30T21:37:53Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳(メタデータ) (2021-11-07T13:44:50Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳(メタデータ) (2020-12-29T14:06:09Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。