論文の概要: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
- arxiv url: http://arxiv.org/abs/2206.05245v1
- Date: Fri, 10 Jun 2022 17:38:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-13 15:16:26.512827
- Title: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
- Title（参考訳）: ペアの差分フィルタリングによるリスト分解可能なスパース平均推定
- Authors: Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia,
Thanasis Pittas
- Abstract要約: そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に,m = (klog(n))O(t)/alpha と m = (klog(n))O(t)/alpha と、m = (mnt)$ と、m = (klog(n))O(t)/alpha と、m = (1/alpha)O (1/t)$ の誤差を達成する。
- 参考スコア（独自算出の注目度）: 48.07596965953344
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of list-decodable sparse mean estimation. Specifically,
for a parameter $\alpha \in (0, 1/2)$, we are given $m$ points in
$\mathbb{R}^n$, $\lfloor \alpha m \rfloor$ of which are i.i.d. samples from a
distribution $D$ with unknown $k$-sparse mean $\mu$. No assumptions are made on
the remaining points, which form the majority of the dataset. The goal is to
return a small list of candidates containing a vector $\widehat \mu$ such that
$\| \widehat \mu - \mu \|_2$ is small. Prior work had studied the problem of
list-decodable mean estimation in the dense setting. In this work, we develop a
novel, conceptually simpler technique for list-decodable mean estimation. As
the main application of our approach, we provide the first sample and
computationally efficient algorithm for list-decodable sparse mean estimation.
In particular, for distributions with ``certifiably bounded'' $t$-th moments in
$k$-sparse directions and sufficiently light tails, our algorithm achieves
error of $(1/\alpha)^{O(1/t)}$ with sample complexity $m =
(k\log(n))^{O(t)}/\alpha$ and running time $\mathrm{poly}(mn^t)$. For the
special case of Gaussian inliers, our algorithm achieves the optimal error
guarantee of $\Theta (\sqrt{\log(1/\alpha)})$ with quasi-polynomial sample and
computational complexity. We complement our upper bounds with nearly-matching
statistical query and low-degree polynomial testing lower bounds.
- Abstract（参考訳）: リスト化可能なスパース平均推定問題について検討する。
具体的には、パラメータ $\alpha \in (0, 1/2)$ に対して、$m$ points in $\mathbb{R}^n$, $\lfloor \alpha m \rfloor$ が与えられる。
残りのポイントでは、データセットの大部分を形成する仮定は行われない。
目標は、$\| \widehat \mu - \mu \|_2$ が小さいようなベクトル $\widehat \mu$ を含む候補の小さなリストを返すことである。
先行研究は、密集した設定におけるリスト決定可能平均推定の問題を研究していた。
本研究では,リスト記述可能な平均推定のための新しい概念的手法を開発する。
提案手法の主な応用として,リストデコタブルなスパース平均推定のための最初のサンプルと計算効率のよいアルゴリズムを提案する。
特に ``certifiably bounded'''$t$-th moments in $k$-sparse directions and enough light tails の分布に対して、このアルゴリズムは、サンプル複雑性 $m = (k\log(n))^{o(t)}/\alpha$ と実行時間 $\mathrm{poly}(mn^t)$ で誤差(1/\alpha)^{o(1/t)} を達成する。
gaussian inliersの特別な場合、このアルゴリズムは準多項標本と計算複雑性を持つ$\theta (\sqrt{\log(1/\alpha)})$の最適誤差保証を達成する。
我々は上限をほぼ一致した統計クエリと低次多項式テストで補完する。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - 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) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。