論文の概要: Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers

• arxiv url: http://arxiv.org/abs/2111.02966v1
• Date: Thu, 4 Nov 2021 15:59:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-05 12:36:44.689852
• Title: Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
• Title（参考訳）: 異常外乱を考慮したPCAとスパース回帰の一貫性推定
• Authors: Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
• Abstract要約: 我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。 スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。 PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
• 参考スコア（独自算出の注目度）: 13.244654316770815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an $\alpha$ fraction of the samples. As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA). For sparse regression, we achieve consistency for optimal sample size $n\gtrsim (k\log d)/\alpha^2$ and optimal error rate $O(\sqrt{(k\log d)/(n\cdot \alpha^2)})$ where $n$ is the number of observations, $d$ is the number of dimensions and $k$ is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples. Prior to this work, no estimator was known to be consistent when the fraction of inliers $\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian design matrices. Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al. [dNS21]. In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussian with variance $1/n^2$). To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsi et al.'s approach [dNS21] in a novel way to analyze the loss function. Our machinery appears to be easily applicable to a wide range of estimation problems.
• Abstract（参考訳）: 計算可能で一貫性のある推定器を効率的に設計する機械を開発し,観測数の増加に伴ってゼロに近づいた推定誤差を達成する。 具体例としてスパース回帰と主成分分析(PCA)の2つの問題を考察する。 スパース回帰では、最適なサンプルサイズ $n\gtrsim (k\log d)/\alpha^2$ と最適なエラーレート $o(\sqrt{(k\log d)/(n\cdot \alpha^2)})$n$ が観測数、$d$ が次元数、$k$ がパラメータベクトルのスパース性であり、標本数における不連続の分数を逆多項化できる。 この研究以前には、(非球面)ガウスの設計行列に対してさえ、inliers $\alpha$ の分数が $o(1/\log \log n)$ であるとき、推定子は一貫性がないことが知られていた。 弱い設計仮定の下で保持された結果と、そのような一般的なノイズの存在は、d'orsiらによって非常に最近、密集した設定(つまり一般線形回帰)でのみ示されてきた。 [dns21] pcaの文脈では、パラメータ行列(通常行列完全化で使われる)上の広いスパイクネス仮定の下で最適誤差保証を達成する。 以前の研究は、イリヤに対応する測定ノイズが$n$(例えば1/n^2$)で多項式的に小さいという仮定の下でのみ、非自明な保証を得ることができた。 推定器を考案するために、フッカー損失を$\ell_1$ノルムや核ノルムのような非滑らかな正則化器と装備し、損失関数を解析するための新しい方法としてd'Orsi et al.のアプローチ(dNS21)を拡張する。 我々の機械は、幅広い推定問題に容易に適用できるように見える。

関連論文リスト

• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。 本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
  論文  参考訳（メタデータ） (2023-06-26T17:13:31Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  本稿では,リスト復号化可能な線形回帰問題について考察する。 我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
  論文  参考訳（メタデータ） (2021-06-17T17:45:21Z)
• 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)
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion [1.0878040851637998]
  ヘテロジニアス雑音を伴う統計的学習フレームワークにおける高次元最小二乗回帰について検討する。 また, 製品プロセスの新たな応用に基づいて, 行列分解を伴う新しいトレーサリグレス理論を提案する。
  論文  参考訳（メタデータ） (2020-12-12T07:42:47Z)
• Computationally and Statistically Efficient Truncated Regression [36.3677715543994]
  計算的かつ統計的に効率的な線形回帰の古典的問題に対する推定器を提供する。 提案手法では, トランキャット標本の負の対数類似度に代わることなく, プロジェクテッド・Descent Gradient (PSGD) を用いて推定する。 本稿では,SGDが単一層ニューラルネットワークの雑音活性化関数のパラメータを学習することを示す。
  論文  参考訳（メタデータ） (2020-10-22T19:31:30Z)
• Consistent regression when oblivious outliers overwhelm [8.873449722727026]
  我々の研究に先立ち、ガウスの$X$でさえ、$beta*$ の見積子は、このモデルでは一貫性がないことが知られていた。 ほぼ線形なサンプルサイズと逆ポリノミアル不整分率で一貫した推定が可能であることを示す。 ここで研究したモデルは、最初の瞬間さえも持たない重い尾の雑音の分布も捉えている。
  論文  参考訳（メタデータ） (2020-09-30T16:21:34Z)
• 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)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)

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

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