論文の概要: Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes
- arxiv url: http://arxiv.org/abs/2209.05953v1
- Date: Fri, 9 Sep 2022 23:35:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-14 12:30:29.284833
- Title: Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes
- Title（参考訳）: ノイズレジームにおける高次元簡易学習のためのサンプル複雑境界
- Authors: Amir Hossein Saberi, Amir Najafi, Seyed Abolfazl Motahari and Babak H.
Khalaj
- Abstract要約: n$のデータセットは、未知の任意の単純集合上の一様分布から引き出されたサンプルを含む。
高確率で真単純度から$epsilon + Oleft(mathrmSNR-1right)$の総変動距離を持つ単純度を出力する戦略を提案する。
真の単純度に近づくと、$ngetildeOleft(K2/epsilon2right)$サンプルを持つことは十分である。
- 参考スコア（独自算出の注目度）: 5.526935605535376
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose a sample complexity bound for learning a simplex
from noisy samples. A dataset of size $n$ is given which includes i.i.d.
samples drawn from a uniform distribution over an unknown arbitrary simplex in
$\mathbb{R}^K$, where samples are assumed to be corrupted by an additive
Gaussian noise of an arbitrary magnitude. We propose a strategy which outputs a
simplex having, with high probability, a total variation distance of $\epsilon
+ O\left(\mathrm{SNR}^{-1}\right)$ from the true simplex, for any $\epsilon>0$.
We prove that to arrive this close to the true simplex, it is sufficient to
have $n\ge\tilde{O}\left(K^2/\epsilon^2\right)$ samples. Here, SNR stands for
the signal-to-noise ratio which can be viewed as the ratio of the diameter of
the simplex to the standard deviation of the noise. Our proofs are based on
recent advancements in sample compression techniques, which have already shown
promises in deriving tight bounds for density estimation in high-dimensional
Gaussian mixture models.
- Abstract（参考訳）: 本稿では,ノイズのあるサンプルからsimplexを学習するためのサンプル複雑性を提案する。
サイズ$n$のデータセットが与えられ、そのデータセットには、未知の任意の単純集合上の一様分布から引き出されたサンプルが $\mathbb{r}^k$ で示され、サンプルは任意の大きさの付加ガウス雑音によって崩壊すると仮定される。
任意の$\epsilon>0$に対して、真のsimplexから$\epsilon + o\left(\mathrm{snr}^{-1}\right)$の全変動距離を持つsimplexを出力する戦略を提案する。
これを真の単純性に近づけると、$n\ge\tilde{o}\left(k^2/\epsilon^2\right)$ のサンプルが得られる。
ここでは、SNRはノイズの標準偏差に対する単純度の直径の比と見なせる信号対雑音比を表す。
この証明は,高次元ガウス混合モデルにおける密度推定の厳密な境界を導出する可能性をすでに示している試料圧縮技術の最近の進歩に基づいている。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Estimation of Shortest Path Covariance Matrices [21.772761365915176]
共分散行列 $mathbfSigma in mathbbRdtimes d$ of a distribution $mathcal D$ over $mathbbRd$ given independent sample。
単に$O(sqrtD)$エントリ複雑性と$tilde O(r)を使って、標準エラーまで$mathbfSigma$を推定するための非常に単純なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-11-19T17:37:46Z) - Multi-reference alignment in high dimensions: sample complexity and
phase transition [31.841289319809814]
マルチ参照アライメントは、円形にシフトしたノイズの多いコピーから$mathbbRL$のシグナルを推定する。
単一粒子の低温電子顕微鏡により、高次元状態における問題のサンプルの複雑さを解析した。
我々の分析では、パラメータ $alpha = L/(sigma2log L)$ で制御される相転移現象を発見し、$sigma2$ はノイズの分散である。
論文 参考訳（メタデータ） (2020-07-22T15:04:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。