論文の概要: List-Decodable Covariance Estimation

• arxiv url: http://arxiv.org/abs/2206.10942v1
• Date: Wed, 22 Jun 2022 09:38:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-23 15:42:39.404958
• Title: List-Decodable Covariance Estimation
• Title（参考訳）: リスト決定可能な共分散推定
• Authors: Misha Ivkov and Pravesh K. Kothari
• Abstract要約: 共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
• 参考スコア（独自算出の注目度）: 1.9290392443571387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first polynomial time algorithm for \emph{list-decodable covariance estimation}. For any $\alpha > 0$, our algorithm takes input a sample $Y \subseteq \mathbb{R}^d$ of size $n\geq d^{\mathsf{poly}(1/\alpha)}$ obtained by adversarially corrupting an $(1-\alpha)n$ points in an i.i.d. sample $X$ of size $n$ from the Gaussian distribution with unknown mean $\mu_*$ and covariance $\Sigma_*$. In $n^{\mathsf{poly}(1/\alpha)}$ time, it outputs a constant-size list of $k = k(\alpha)= (1/\alpha)^{\mathsf{poly}(1/\alpha)}$ candidate parameters that, with high probability, contains a $(\hat{\mu},\hat{\Sigma})$ such that the total variation distance $TV(\mathcal{N}(\mu_*,\Sigma_*),\mathcal{N}(\hat{\mu},\hat{\Sigma}))<1-O_{\alpha}(1)$. This is the statistically strongest notion of distance and implies multiplicative spectral and relative Frobenius distance approximation for parameters with dimension independent error. Our algorithm works more generally for $(1-\alpha)$-corruptions of any distribution $D$ that possesses low-degree sum-of-squares certificates of two natural analytic properties: 1) anti-concentration of one-dimensional marginals and 2) hypercontractivity of degree 2 polynomials. Prior to our work, the only known results for estimating covariance in the list-decodable setting were for the special cases of list-decodable linear regression and subspace recovery due to Karmarkar, Klivans, and Kothari (2019), Raghavendra and Yau (2019 and 2020) and Bakshi and Kothari (2020). These results need superpolynomial time for obtaining any subconstant error in the underlying dimension. Our result implies the first polynomial-time \emph{exact} algorithm for list-decodable linear regression and subspace recovery that allows, in particular, to obtain $2^{-\mathsf{poly}(d)}$ error in polynomial-time. Our result also implies an improved algorithm for clustering non-spherical mixtures.
• Abstract（参考訳）: 我々は、 \emph{list-decodable covariance estimation} に対する最初の多項式時間アルゴリズムを与える。 任意の$\alpha > 0$に対して、我々のアルゴリズムはサンプル$Y \subseteq \mathbb{R}^d$ of size $n\geq d^{\mathsf{poly}(1/\alpha)}$を、未知の平均$\mu_*$と共分散$\Sigma_*$でガウス分布から$1-\alpha)n$の点を逆転して得られる。 $n^{\mathsf{poly}(1/\alpha)}$ timeでは、$k = k(\alpha)= (1/\alpha)^{\mathsf{poly}(1/\alpha)$ candidateパラメータを出力し、高い確率で、$(\hat{\mu},\hat{\Sigma})$を含み、総変動距離$TV(\mathcal{N}(\mu_*,\Sigma_*),\mathcal{N}(\hat{\mu},\hat{\Sigma}))<1-O_{\alpha}(1)$である。 これは統計上最も強い距離の概念であり、次元独立な誤差を持つパラメータに対する乗法スペクトルと相対フロベニウス距離近似を意味する。 我々のアルゴリズムは、より一般的に、1-\alpha)$-corruptions of any distribution $D$ that possesss low-degree sum-of-squares certificates of two natural analysis propertiesに対して機能する。 1) 一次元辺縁の反集中 2)次数 2 多項式の超収縮率。 本研究以前は,カルマルカ,クリバン,コタリ(2019),ラガヴェンドラとヤウ(2019年,2020年),バクシとコタリ(2020年)によるリスト決定可能な線形回帰と部分空間回復の特別なケースで,リスト決定可能な設定における共分散を推定する唯一の既知の結果であった。 これらの結果は、下層の次元における任意のサブコンスタント誤差を得るために超ポリノミカル時間を必要とする。 その結果、リスト決定可能な線形回帰と部分空間復元のための最初の多項式時間 \emph{exact} アルゴリズムが示され、特に多項式時間で 2^{-\mathsf{poly}(d)}$ の誤差を得ることができる。 また,非球面混合をクラスタリングするための改良アルゴリズムも提案する。

関連論文リスト

• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  潜在変数モデル学習の課題について検討する。 このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。 一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
  論文  参考訳（メタデータ） (2024-11-23T23:13:24Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• 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)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• 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)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• 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)
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time [5.812499828391904]
  リスト化可能部分空間のリカバリにおいて、入力は$n$ポイント$alpha n$(ある$alpha ll 1/2$)の集合であり、それらは分布$mathcalD$から引き出される。 本研究は, より高速な固定ポリノミカルランニング時間を用いて, アンフェクタブルな集中防止誤差の3つの側面について, 結果を改善するものである。
  論文  参考訳（メタデータ） (2020-02-12T18:30:09Z)

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

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