論文の概要: 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$.
我々の結果は、これらのよく研究された問題に対する最初の効率的な距離近似アルゴリズムである。
これらは分布学習アルゴリズムへの単純で一般的な接続を用いて導出される。
距離近似アルゴリズムは、上述した構造化高次元分布の近接性をテストするための新しい効率的なアルゴリズムである。
関連論文リスト
- Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。
直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T12:24:14Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。