論文の概要: Identity Testing for High-Dimensional Distributions via Entropy
Tensorization
- arxiv url: http://arxiv.org/abs/2207.09102v1
- Date: Tue, 19 Jul 2022 06:49:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-20 14:41:02.723381
- Title: Identity Testing for High-Dimensional Distributions via Entropy
Tensorization
- Title(参考訳): エントロピーテンソル化による高次元分布のアイデンティティテスト
- Authors: Antonio Blanca, Zongchen Chen, Daniel \v{S}tefankovi\v{c}, Eric Vigoda
- Abstract要約: 我々は,n$次元分布の同一性テスト問題に対して,改良されたアルゴリズムと,統計的および計算的下界の整合性を示す。
同一性テスト問題では、明示的な分布 $mu$, $varepsilon>0$, and access to a sample oracle for a hidden distribution $pi$ が与えられる。
エントロピーの近似テンソル化として知られる解析的性質が可視分布の$mu$に対して成り立つならば、$tildeO(n/vareps)を使用する隠された$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
- 参考スコア(独自算出の注目度): 4.370097023410272
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present improved algorithms and matching statistical and computational
lower bounds for the problem of identity testing $n$-dimensional distributions.
In the identity testing problem, we are given as input an explicit distribution
$\mu$, an $\varepsilon>0$, and access to a sampling oracle for a hidden
distribution $\pi$. The goal is to distinguish whether the two distributions
$\mu$ and $\pi$ are identical or are at least $\varepsilon$-far apart. When
there is only access to full samples from the hidden distribution $\pi$, it is
known that exponentially many samples may be needed, and hence previous works
have studied identity testing with additional access to various conditional
sampling oracles. We consider here a significantly weaker conditional sampling
oracle, called the Coordinate Oracle, and provide a fairly complete
computational and statistical characterization of the identity testing problem
in this new model.
We prove that if an analytic property known as approximate tensorization of
entropy holds for the visible distribution $\mu$, then there is an efficient
identity testing algorithm for any hidden $\pi$ that uses
$\tilde{O}(n/\varepsilon)$ queries to the Coordinate Oracle. Approximate
tensorization of entropy is a classical tool for proving optimal mixing time
bounds of Markov chains for high-dimensional distributions, and recently has
been established for many families of distributions via spectral independence.
We complement our algorithmic result for identity testing with a matching
$\Omega(n/\varepsilon)$ statistical lower bound for the number of queries under
the Coordinate Oracle. We also prove a computational phase transition: for
sparse antiferromagnetic Ising models over $\{+1,-1\}^n$, in the regime where
approximate tensorization of entropy fails, there is no efficient identity
testing algorithm unless RP=NP.
- Abstract(参考訳): n$次元分布の同一性テスト問題に対するアルゴリズムの改良と統計的および計算的下限のマッチングについて述べる。
アイデンティティテスト問題では、明示的な分布 $\mu$, $\varepsilon>0$, and access to a sample oracle for a hidden distribution $\pi$ が与えられる。
目標は、$\mu$ と $\pi$ の2つのディストリビューションが同一か、少なくとも$\varepsilon$-far かを区別することである。
隠れ分布の$\pi$から完全なサンプルにしかアクセスできない場合、指数関数的に多くのサンプルが必要になることが知られており、それ故に以前の研究は様々な条件付きサンプリングオラクルへの追加アクセスでアイデンティティテストを研究した。
ここでは、コーディネートオラクルと呼ばれる、かなり弱い条件サンプリングオラクルを検討し、この新しいモデルにおけるアイデンティティテスト問題のかなり完全な計算と統計的な特徴付けを提供する。
エントロピーの近似テンソル化として知られる解析的性質が、可視分布 $\mu$ に対して成り立つならば、座標オラクルに$\tilde{o}(n/\varepsilon)$クエリを使用する隠れた$\pi$ に対する効率的なアイデンティティテストアルゴリズムが存在することが証明される。
エントロピーの近似テンソル化は、高次元分布に対するマルコフ連鎖の最適混合時間境界を証明する古典的なツールであり、近年はスペクトル独立性を通じて分布の多くの族に対して確立されている。
我々は,Oracleのコーディネートの下でのクエリ数に対して,一致する$\Omega(n/\varepsilon)$statistical lowerboundでIDテストのアルゴリズム結果を補完する。
計算位相遷移も証明する:$\{+1,-1\}^n$上のスパース反強磁性イジングモデルに対して、エントロピーの近似テンソル化が失敗する状況では、RP=NPがなければ効率的な恒等性検査アルゴリズムは存在しない。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳(メタデータ) (2024-02-13T12:52:41Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳(メタデータ) (2023-09-25T09:50:15Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳(メタデータ) (2023-02-21T17:52:23Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳(メタデータ) (2023-02-20T23:29:43Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳(メタデータ) (2022-02-23T16:10:23Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳(メタデータ) (2020-10-07T01:43:07Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。