Fugu-MT 論文翻訳(概要): Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time

論文の概要: Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time

arxiv url: http://arxiv.org/abs/2006.13312v1
Date: Tue, 23 Jun 2020 20:21:27 GMT
ステータス: 処理完了
システム内更新日: 2022-11-17 23:02:24.640698
Title: Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
Title（参考訳）: 近似行列乗算時間におけるロバストガウス共分散推定
Authors: Jerry Li, Guanghao Ye
Abstract要約: ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
参考スコア（独自算出の注目度）: 14.990725929840892
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Robust covariance estimation is the following, well-studied problem in high dimensional statistics: given $N$ samples from a $d$-dimensional Gaussian $\mathcal{N}(\boldsymbol{0}, \Sigma)$, but where an $\varepsilon$-fraction of the samples have been arbitrarily corrupted, output $\widehat{\Sigma}$ minimizing the total variation distance between $\mathcal{N}(\boldsymbol{0}, \Sigma)$ and $\mathcal{N}(\boldsymbol{0}, \widehat{\Sigma})$. This corresponds to learning $\Sigma$ in a natural affine-invariant variant of the Frobenius norm known as the \emph{Mahalanobis norm}. Previous work of Cheng et al demonstrated an algorithm that, given $N = \Omega (d^2 / \varepsilon^2)$ samples, achieved a near-optimal error of $O(\varepsilon \log 1 / \varepsilon)$, and moreover, their algorithm ran in time $\widetilde{O}(T(N, d) \log \kappa / \mathrm{poly} (\varepsilon))$, where $T(N, d)$ is the time it takes to multiply a $d \times N$ matrix by its transpose, and $\kappa$ is the condition number of $\Sigma$. When $\varepsilon$ is relatively small, their polynomial dependence on $1/\varepsilon$ in the runtime is prohibitively large. In this paper, we demonstrate a novel algorithm that achieves the same statistical guarantees, but which runs in time $\widetilde{O} (T(N, d) \log \kappa)$. In particular, our runtime has no dependence on $\varepsilon$. When $\Sigma$ is reasonably conditioned, our runtime matches that of the fastest algorithm for covariance estimation without outliers, up to poly-logarithmic factors, showing that we can get robustness essentially "for free."
Abstract（参考訳）: ロバスト共分散推定は、高次元統計学におけるよく研究された問題である:$d$-dimensional Gaussian $\mathcal{N}(\boldsymbol{0}, \Sigma)$から$N$のサンプルが与えられるが、サンプルの$\varepsilon$-fractionが任意に破損している場合、出力$\widehat{\Sigma}$$$$\mathcal{N}(\boldsymbol{0}, \Sigma)$と$\mathcal{N}(\boldsymbol{0}, \widehat{\Sigma})$$の合計変動距離を最小化する。これは \emph{Mahalanobis norm} として知られるフロベニウスノルムの自然なアフィン不変変種で $\Sigma$ を学ぶことに対応する。 Chengらによる以前の研究は、$N = \Omega (d^2 / \varepsilon^2)$のサンプルが与えられたとき、$O(\varepsilon \log 1 / \varepsilon)$のほぼ最適誤差を達成し、さらに、それらのアルゴリズムは時間$\widetilde{O}(T(N, d) \log \kappa / \mathrm{poly} (\varepsilon)$で実行され、$T(N, d)$はその変換によって$d \times N$行列を乗算するのにかかる時間である。もし$\varepsilon$が比較的小さい場合、実行時の$/\varepsilon$に対する多項式依存は、非常に大きい。本稿では,同じ統計的保証を達成するが,時間$\widetilde{o} (t(n, d) \log \kappa)$ で実行される新しいアルゴリズムを示す。特に、ランタイムは$\varepsilon$に依存していません。しかし、$\sigma$ が合理的に条件付けされた場合、我々のランタイムは、外れ値のない共分散推定の最も高速なアルゴリズムのそれと一致し、多対数因子によって、本質的に「自由」な堅牢性が得られることを示している。

関連論文リスト

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)
Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文参考訳（メタデータ） (2024-09-05T16:59:56Z)
Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文参考訳（メタデータ） (2024-02-22T02:20:24Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians [3.5788754401889014]
強い$varepsilon$-contaminationモデルでは、元のガウスサンプルのベクトルの$varepsilon$分を他のベクトルに置き換えたと仮定する。我々は、少なくとも1-デルタの確率で満足するコフラ行列 $Sigma の推定器 $widehat Sigma を構築する。
論文参考訳（メタデータ） (2023-01-21T23:28:55Z)
A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文参考訳（メタデータ） (2022-09-06T23:37:31Z)
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)
Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文参考訳（メタデータ） (2021-06-25T17:59:16Z)
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)
Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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