論文の概要: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions

• arxiv url: http://arxiv.org/abs/2211.16333v1
• Date: Tue, 29 Nov 2022 16:13:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-30 15:55:25.516034
• Title: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
• Title（参考訳）: ヘビーテール分布に対するoutlier-robust sparse平均推定
• Authors: Ilias Diakonikolas, Daniel M. Kane, Jasper C.H. Lee, Ankit Pensia
• Abstract要約: 少数の破損したサンプルが与えられた場合、ゴールは確率の高い$mu$を正確に近似する仮説を効率的に計算することである。 本アルゴリズムは, 周辺次元と対数的にスケーリングするサンプルを多数使用して, 最適誤差を実現する。 我々の分析は、ある空間特性を満たす正の半定値に対する(非スペクトル)分解の繊細な設計を含む、独立した関心を持つかもしれない。
• 参考スコア（独自算出の注目度）: 42.6763105645717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an additive $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.
• Abstract（参考訳）: 本研究では,大口径分布における外乱平均推定の基本的な課題について検討する。 特に、$\mu$ の平均がスパースであることが保証される高次元の重尾分布から少数の腐敗したサンプルを与えられた場合、目標は$\mu$ を高い確率で正確に近似する仮説を効率的に計算することである。 以前の研究では、光尾分布のロバストなスパース平均推定のための効率的なアルゴリズムが得られた。 本研究では,軽度モーメント仮定下での重み付き分布に対して,最初のサンプル効率と多項式時間ロバストなスパース平均推定器を与える。 本アルゴリズムは,環境次元と対数的にスケーリングする多数のサンプルを用いて,最適漸近誤差を達成する。 重要なことに、本手法のサンプル複雑性は、付加的な$\log(1/\tau)$依存を持つ失敗確率$\tau$の関数として最適である。 本アルゴリズムは,アルゴリズムのロバストな統計文献からの安定性に基づくアプローチを活用し,決定的(かつ必要)な適応を行う。 この解析は独立な興味を持ち、ある種のスパーシティ特性を満たす正の半定義行列に対する(非スペクトル)分解の繊細な設計を含む。

関連論文リスト

• Mean-Square Analysis of Discretized It\^o Diffusions for Heavy-tailed Sampling [17.415391025051434]
  重み付きポインカーの不等式に関連する伊藤拡散の自然クラスを離散化することにより、重み付き分布のクラスからのサンプリングの複雑さを分析する。 平均二乗解析に基づいて、ワッサーシュタイン2計量のターゲット分布に近い分布が$epsilon$のサンプルを得るための反復複雑性を確立する。
  論文  参考訳（メタデータ） (2023-03-01T15:16:03Z)
• Convergence for score-based generative modeling with polynomial complexity [9.953088581242845]
  我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。 以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。 予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
  論文  参考訳（メタデータ） (2022-06-13T14:57:35Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。 我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。 技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
  論文  参考訳（メタデータ） (2022-02-02T20:11:33Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Non-asymptotic analysis and inference for an outlyingness induced winsorized mean [0.0]
  本稿では,平均の下位ゲージ推定器のロバスト性について検討する。 いずれも、データ中の25%以上の汚染に耐えられないことが明らかになった。 また、最高の堅牢性を有するアウトライン性誘起Winsorized平均も導入しています。
  論文  参考訳（メタデータ） (2021-05-05T21:35:24Z)
• Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms [43.134933182911766]
  最小二乗問題に対するRandNLAサンプリング推定器の分布を導出する解析法を開発した。 AAMSE(Asymptotic Mean Squared Error)とEAMSE(Asymsymotic Mean Squared Error)に基づく最適なサンプリング確率の同定を行った。 提案手法は, サンプリングプロセスにおけるレバレッジの役割を明らかにするとともに, 実験により既存の手法よりも改善したことを示す。
  論文  参考訳（メタデータ） (2020-02-24T20:34:50Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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