論文の概要: Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time

• arxiv url: http://arxiv.org/abs/2502.06564v1
• Date: Mon, 10 Feb 2025 15:31:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 18:57:51.351467
• Title: Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time
• Title（参考訳）: 多項式時間における楕円分布のロバスト散乱行列推定
• Authors: Gleb Novikov,
• Abstract要約: 我々はフロベニウスノルムで次元非依存誤差を実現する時間アルゴリズムを設計する。 散乱行列 $Sigma$, for every $t in mathbbN$, we design an estimator that, given $n = dO(t)$ sample, in time $nO(t)$ finds $hatSigma。
• 参考スコア（独自算出の注目度）: 2.311583680973075
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of computationally efficient robust estimation of scatter matrices of elliptical distributions under the strong contamination model. We design polynomial time algorithms that achieve dimension-independent error in Frobenius norm. Our first result is a sequence of efficient algorithms that approaches nearly optimal error. Specifically, under a mild assumption on the eigenvalues of the scatter matrix $\Sigma$, for every $t \in \mathbb{N}$, we design an estimator that, given $n = d^{O(t)}$ samples, in time $n^{O(t)}$ finds $\hat{\Sigma}$ such that $ \Vert{\Sigma^{-1/2}\, ({\hat{\Sigma} - \Sigma})\, \Sigma^{-1/2}}\Vert_{\text{F}} \le O(t \cdot \varepsilon^{1-\frac{1}{t}})$, where $\varepsilon$ is the fraction of corruption. We do not require any assumptions on the moments of the distribution, while all previously known computationally efficient algorithms for robust covariance/scatter estimation with dimension-independent error rely on strong assumptions on the moments, such as sub-Gaussianity or (certifiable) hypercontractivity. Furthermore, under a stronger assumption on the eigenvalues of $\Sigma$ (that, in particular, is satisfied by all matrices with constant condition number), we provide a fast (sub-quadratic in the input size) algorithm that, given nearly optimal number of samples $n = \tilde{O}(d^2/\varepsilon)$, in time $\tilde{O}({nd^2 poly(1/\varepsilon)})$ finds $\hat{\Sigma}$ such that $\Vert\hat{\Sigma} - \Sigma\Vert_{\text{F}} \le O(\Vert{\Sigma}\Vert \cdot \sqrt{\varepsilon})$. Our approach is based on robust covariance estimation of the spatial sign (the projection onto the sphere of radius $\sqrt{d}$) of elliptical distributions.
• Abstract（参考訳）: 強い汚染モデルの下で, 楕円分布の散乱行列を計算効率よく頑健に推定する問題について検討した。 我々はフロベニウスノルムにおける次元非依存誤差を実現する多項式時間アルゴリズムを設計する。 最初の結果は、ほぼ最適な誤差にアプローチする効率的なアルゴリズムのシーケンスです。 具体的には、すべての$t \in \mathbb{N}$に対して、散乱行列 $\Sigma$ の固有値に関する穏やかな仮定の下で、$n = d^{O(t)}$サンプルが与えられると、$n^{O(t)}$ finds $\hat{\Sigma}$ が $ \Vert{\Sigma^{-1/2}\, ({\hat{\Sigma} - \Sigma})\, \Sigma^{-1/2}}\Vert_{\text{F}} \le O(t \cdot \varepsilon^{1-\frac{1}{t}})$ となるような推定器を設計する。 分布のモーメントに関する仮定は一切必要としないが、次元に依存しない誤差を伴う堅牢な共分散/散乱推定のための計算効率の良いアルゴリズムは、準ガウス性や(証明可能な)超収縮性のようなモーメントに関する強い仮定に依存している。 さらに、$\Sigma$ の固有値に関する強い仮定の下で(特に、入力サイズが一定であるすべての行列で満たされる)、高速(サブクアドラティックな)アルゴリズムを提供して、サンプルのほぼ最適な数に $n = \tilde{O}(d^2/\varepsilon)$, in time $\tilde{O}({nd^2 poly(1/\varepsilon)})$ finds $\hat{\Sigma}$, $\Vert\hat{\Sigma} - \Sigma\Vert_{\text{F}} \le O(\Vert{\Sigma}\Vert \cdotsqrt{\Sigma}$)を与える。 我々のアプローチは、楕円分布の空間符号(半径$\sqrt{d}$)のロバストな共分散推定に基づいている。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time? [8.74634652691576]
  反復アルゴリズムのクラスで実現可能な分布のサブセット$mathscrF_m,alpha$について検討する。 統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$mathscrF_m,alpha$の間接的な特徴づけを与える。
  論文  参考訳（メタデータ） (2024-06-05T05:54:56Z)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。 我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
  論文  参考訳（メタデータ） (2024-03-07T18:23:51Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions [8.40077201352607]
  我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
  論文  参考訳（メタデータ） (2023-01-28T16:57:46Z)
• 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 Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
  我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。 推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
  論文  参考訳（メタデータ） (2023-01-17T18:44:41Z)
• 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)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• 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)
• 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)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)
• 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)

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

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