論文の概要: Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes

• arxiv url: http://arxiv.org/abs/2506.10101v1
• Date: Wed, 11 Jun 2025 18:35:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:22.393687
• Title: Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes
• Title（参考訳）: ノイズレジームにおける高次元簡易学習の基礎的限界
• Authors: Seyed Amir Hossein Saberi, Amir Najafi, Abolfazl Motahari, Babak H. khalaj,
• Abstract要約: 確率の高いアルゴリズムは、$ell$または総変分(TV)距離を真単純度から最大$varepsilon$で出力する。 雑音のないシナリオでは、我々の下界の$n ge Omega(K/varepsilon)$は既知の上界を定数要素まで一致させる。
• 参考スコア（独自算出の注目度）: 0.5892638927736114
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we establish sample complexity bounds for learning high-dimensional simplices in $\mathbb{R}^K$ from noisy data. Specifically, we consider $n$ i.i.d. samples uniformly drawn from an unknown simplex in $\mathbb{R}^K$, each corrupted by additive Gaussian noise of unknown variance. We prove an algorithm exists that, with high probability, outputs a simplex within $\ell_2$ or total variation (TV) distance at most $\varepsilon$ from the true simplex, provided $n \ge (K^2/\varepsilon^2) e^{\mathcal{O}(K/\mathrm{SNR}^2)}$, where $\mathrm{SNR}$ is the signal-to-noise ratio. Extending our prior work~\citep{saberi2023sample}, we derive new information-theoretic lower bounds, showing that simplex estimation within TV distance $\varepsilon$ requires at least $n \ge \Omega(K^3 \sigma^2/\varepsilon^2 + K/\varepsilon)$ samples, where $\sigma^2$ denotes the noise variance. In the noiseless scenario, our lower bound $n \ge \Omega(K/\varepsilon)$ matches known upper bounds up to constant factors. We resolve an open question by demonstrating that when $\mathrm{SNR} \ge \Omega(K^{1/2})$, noisy-case complexity aligns with the noiseless case. Our analysis leverages sample compression techniques (Ashtiani et al., 2018) and introduces a novel Fourier-based method for recovering distributions from noisy observations, potentially applicable beyond simplex learning.
• Abstract（参考訳）: 本稿では,雑音データから高次元の単純さを学習するためのサンプル複雑性境界を$\mathbb{R}^K$で確立する。 具体的には、$n$ i.i.d.サンプルを、未知の単純集合から、未知の分散の加法的なガウスノイズによって、それぞれ破損した$\mathbb{R}^K$で均一に描画する。 確率の高いアルゴリズムでは、大まかに$\ell_2$か、大まかに$\varepsilon$から$\varepsilon$を出力し、$n \ge (K^2/\varepsilon^2) e^{\mathcal{O}(K/\mathrm{SNR}^2)}$、$\mathrm{SNR}$を信号対雑音比とする。 先行処理~\citep{saberi2023sample} を拡張することで、テレビ距離$\varepsilon$は少なくとも$n \ge \Omega(K^3 \sigma^2/\varepsilon^2 + K/\varepsilon)$サンプルを必要とし、$\sigma^2$はノイズ分散を表す。 雑音のないシナリオでは、我々の下界 $n \ge \Omega(K/\varepsilon)$ は既知の上界を定数要素まで一致させる。 開問題は、$\mathrm{SNR} \ge \Omega(K^{1/2})$ が雑音のない場合と一致することを証明することによって解決する。 本分析では,サンプル圧縮技術(Ashtiani et al , 2018)を活用し,ノイズ観測から分布を復元する新しいフーリエ法を導入する。

関連論文リスト

• Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization [0.0]
  本稿では、mathbbRl$における翻訳の$boldsymbolmuを推定し、mathbbR_++$パラメータにおける$sigmaを縮小する複雑性に焦点を当てる。 MLE(Maximum Likelihood Estimation)ではNPハードとなるが、$varepsilon$-approxs for arbitrary $varepsilon > 0$ in $textpoly left( frac1varepsilon )$ time が得られる。
  論文  参考訳（メタデータ） (2025-01-17T13:07:52Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54: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)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。 我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
  論文  参考訳（メタデータ） (2022-09-09T23:35:25Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
  ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。 我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
  論文  参考訳（メタデータ） (2021-07-05T23:34:39Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。