論文の概要: Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes
- arxiv url: http://arxiv.org/abs/2209.05953v2
- Date: Sat, 29 Apr 2023 02:17:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 19:39:04.220288
- 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要約: ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
- 参考スコア（独自算出の注目度）: 5.526935605535376
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we find a sample complexity bound for learning a simplex from
noisy samples. Assume a dataset of size $n$ is given which includes i.i.d.
samples drawn from a uniform distribution over an unknown simplex in
$\mathbb{R}^K$, where samples are assumed to be corrupted by a multi-variate
additive Gaussian noise of an arbitrary magnitude. We prove the existence of an
algorithm that with high probability outputs a simplex having a $\ell_2$
distance of at most $\varepsilon$ from the true simplex (for any
$\varepsilon>0$). Also, we theoretically show that in order to achieve this
bound, it is sufficient to have
$n\ge\left(K^2/\varepsilon^2\right)e^{\Omega\left(K/\mathrm{SNR}^2\right)}$
samples, where $\mathrm{SNR}$ stands for the signal-to-noise ratio. This result
solves an important open problem and shows as long as
$\mathrm{SNR}\ge\Omega\left(K^{1/2}\right)$, the sample complexity of the noisy
regime has the same order to that of the noiseless case. Our proofs are a
combination of the so-called sample compression technique in
\citep{ashtiani2018nearly}, mathematical tools from high-dimensional geometry,
and Fourier analysis. In particular, we have proposed a general Fourier-based
technique for recovery of a more general class of distribution families from
additive Gaussian noise, which can be further used in a variety of other
related problems.
- Abstract（参考訳）: 本稿では,ノイズのあるサンプルからsimplexを学習するためのサンプル複雑性を求める。
大きさ$n$のデータセットは、未知の単純体上の一様分布から引き出されたサンプルを$\mathbb{R}^K$と仮定し、サンプルは任意の大きさの多変量加法的ガウス雑音によって破損すると仮定する。
我々は、高い確率で、真単純数から少なくとも$\varepsilon$の$\ell_2$距離を持つ単純数(任意の$\varepsilon>0$)を出力するアルゴリズムの存在を証明した。
また、このバウンドを達成するために、理論上、$n\ge\left(k^2/\varepsilon^2\right)e^{\omega\left(k/\mathrm{snr}^2\right)}$サンプルを持つことが示されている。
この結果は重要な開問題を解き、$\mathrm{SNR}\ge\Omega\left(K^{1/2}\right)$ さえあれば、ノイズのない場合と同じ順序でノイズレジームのサンプル複雑性が得られる。
我々の証明は、 \citep{ashtiani2018nearly} におけるいわゆるサンプル圧縮技術、高次元幾何学の数学的ツール、フーリエ解析の組み合わせである。
特に,加法的ガウス雑音からより一般的な分布族を復元するための一般フーリエに基づく手法を提案し,他の様々な問題にさらに適用することができる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。