論文の概要: List-Decodable Mean Estimation via Iterative Multi-Filtering

• arxiv url: http://arxiv.org/abs/2006.10715v2
• Date: Sat, 20 Jun 2020 18:34:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 13:40:24.663049
• Title: List-Decodable Mean Estimation via Iterative Multi-Filtering
• Title（参考訳）: 反復的マルチフィルタによるリスト決定平均推定
• Authors: Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard
• Abstract要約: 未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。 仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
• 参考スコア（独自算出の注目度）: 44.805549762166926
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of {\em list-decodable mean estimation} for bounded covariance distributions. Specifically, we are given a set $T$ of points in $\mathbb{R}^d$ with the promise that an unknown $\alpha$-fraction of points in $T$, where $0< \alpha < 1/2$, are drawn from an unknown mean and bounded covariance distribution $D$, and no assumptions are made on the remaining points. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the mean of $D$. We give the first practically viable estimator for this problem. In more detail, our algorithm is sample and computationally efficient, and achieves information-theoretically near-optimal error. While the only prior algorithm for this setting inherently relied on the ellipsoid method, our algorithm is iterative and only uses spectral techniques. Our main technical innovation is the design of a soft outlier removal procedure for high-dimensional heavy-tailed datasets with a majority of outliers.
• Abstract（参考訳）: 有界共分散分布に対する"em list-decodable mean estimation}問題について検討する。 具体的には、未知の$\alpha$-fraction of points in $T$($0< \alpha < 1/2$)が未知の平均および有界共分散分布$D$($D$)から引き出されることを約束して、$\mathbb{R}^d$の点のセット$T$が与えられる。 目標は、少なくとも1つが$d$の平均に近いような仮説ベクトルの小さなリストを出力することである。 この問題に対する最初の実用的な推定器を与える。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。 この設定の唯一の先行アルゴリズムは、本質的に楕円型法に依存しているが、このアルゴリズムは反復的であり、スペクトル技術のみを使用する。 当社の主な技術的革新は、ほとんどの外れ値を持つ高次元重尾データセットに対するソフトな外れ値除去手順の設計です。

関連論文リスト

• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
  そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。 両課題を適度な条件下で克服する簡易平均推定器を提案する。 私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
  論文  参考訳（メタデータ） (2023-05-24T16:02:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• List-Decodable Sparse Mean Estimation [7.594050968868919]
  最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。 本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
  論文  参考訳（メタデータ） (2022-05-28T05:13:45Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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