論文の概要: List-Decodable Mean Estimation in Nearly-PCA Time
- arxiv url: http://arxiv.org/abs/2011.09973v1
- Date: Thu, 19 Nov 2020 17:21:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-23 20:52:13.053361
- Title: List-Decodable Mean Estimation in Nearly-PCA Time
- Title（参考訳）: ほぼPCA時間におけるリストデコダブル平均推定
- Authors: Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin
Tian
- Abstract要約: 高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
- 参考スコア（独自算出の注目度）: 50.79691056481693
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Traditionally, robust statistics has focused on designing estimators tolerant
to a minority of contaminated data. Robust list-decodable learning focuses on
the more challenging regime where only a minority $\frac 1 k$ fraction of the
dataset is drawn from the distribution of interest, and no assumptions are made
on the remaining data. We study the fundamental task of list-decodable mean
estimation in high dimensions. Our main result is a new list-decodable mean
estimation algorithm for bounded covariance distributions with optimal sample
complexity and error rate, running in nearly-PCA time. Assuming the ground
truth distribution on $\mathbb{R}^d$ has bounded covariance, our algorithm
outputs a list of $O(k)$ candidate means, one of which is within distance
$O(\sqrt{k})$ from the truth. Our algorithm runs in time $\widetilde{O}(ndk)$
for all $k = O(\sqrt{d}) \cup \Omega(d)$, where $n$ is the size of the dataset.
We also show that a variant of our algorithm has runtime $\widetilde{O}(ndk)$
for all $k$, at the expense of an $O(\sqrt{\log k})$ factor in the recovery
guarantee. This runtime matches up to logarithmic factors the cost of
performing a single $k$-PCA on the data, which is a natural bottleneck of known
algorithms for (very) special cases of our problem, such as clustering
well-separated mixtures. Prior to our work, the fastest list-decodable mean
estimation algorithms had runtimes $\widetilde{O}(n^2 d k^2)$ and
$\widetilde{O}(nd k^{\ge 6})$.
Our approach builds on a novel soft downweighting method, $\mathsf{SIFT}$,
which is arguably the simplest known polynomial-time mean estimation technique
in the list-decodable learning setting. To develop our fast algorithms, we
boost the computational cost of $\mathsf{SIFT}$ via a careful "win-win-win"
analysis of an approximate Ky Fan matrix multiplicative weights procedure we
develop, which we believe may be of independent interest.
- Abstract（参考訳）: 伝統的に、ロバスト統計は汚染されたデータに耐性のある推定器の設計に重点を置いてきた。
ロバストリストのデコダブルな学習は、少数派の$\frac 1 k$のデータセットだけが関心の分布から引き出され、残りのデータに仮定されることのない、より困難な体制に焦点をあてる。
高次元におけるリストデコタブル平均推定の基本課題について検討する。
我々の主な成果は、ほぼPCA時間で動作する最適なサンプルの複雑さと誤差率を持つ有界共分散分布に対するリストデコタブル平均推定アルゴリズムである。
基底真理分布が$\mathbb{R}^d$に有界共分散を持つと仮定すると、我々のアルゴリズムは、真理からの距離$O(\sqrt{k})$である$O(k)$の候補平均のリストを出力する。
我々のアルゴリズムは、すべての$k = O(\sqrt{d}) \cup \Omega(d)$に対して、時間$\widetilde{O}(ndk)$で実行される。
また、我々のアルゴリズムの変種には、回復保証に$o(\sqrt{\log k})$因子を犠牲にして、すべての$k$に対して$\widetilde{o}(ndk)$が実行可能であることも示しています。
このランタイムは、データ上で1$k$-PCAを実行するコストの対数的要因と一致します。
我々の研究に先立ち、最も高速な平均推定アルゴリズムはランタイムを$\widetilde{O}(n^2 d k^2)$と$\widetilde{O}(nd k^{\ge 6})$としていた。
提案手法は,リストデコジブル学習環境における多項式時間平均推定法として最も単純なものと考えられる,新しいソフトダウンウェイト法である$\mathsf{SIFT}$に基づいている。
高速アルゴリズムを開発するために、我々は、我々が開発しているkyファン行列乗算重み法(英語版)の注意深い"ウィンウィンウィン"分析を通じて、$\mathsf{sift}$の計算コストを増加させます。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - 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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。