論文の概要: A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
- arxiv url: http://arxiv.org/abs/2403.04726v1
- Date: Thu, 7 Mar 2024 18:23:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-08 13:05:33.028699
- Title: A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
- Title（参考訳）: ロバストスパース平均推定のためのサブ量子時間アルゴリズム
- Authors: Ankit Pensia
- Abstract要約: 逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
- 参考スコア（独自算出の注目度）: 6.853165736531941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the algorithmic problem of sparse mean estimation in the presence of
adversarial outliers. Specifically, the algorithm observes a \emph{corrupted}
set of samples from $\mathcal{N}(\mu,\mathbf{I}_d)$, where the unknown mean
$\mu \in \mathbb{R}^d$ is constrained to be $k$-sparse. A series of prior works
has developed efficient algorithms for robust sparse mean estimation with
sample complexity $\mathrm{poly}(k,\log d, 1/\epsilon)$ and runtime $d^2
\mathrm{poly}(k,\log d,1/\epsilon)$, where $\epsilon$ is the fraction of
contamination. In particular, the fastest runtime of existing algorithms is
quadratic ($\Omega(d^2)$), which can be prohibitive in high dimensions. This
quadratic barrier in the runtime stems from the reliance of these algorithms on
the sample covariance matrix, which is of size $d^2$. Our main contribution is
an algorithm for robust sparse mean estimation which runs in
\emph{subquadratic} time using $\mathrm{poly}(k,\log d,1/\epsilon)$ samples. We
also provide analogous results for robust sparse PCA. Our results build on
algorithmic advances in detecting weak correlations, a generalized version of
the light-bulb problem by Valiant.
- Abstract（参考訳）: 逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
具体的には、アルゴリズムは$\mathcal{n}(\mu,\mathbf{i}_d)$のサンプルの \emph{corrupted} 集合を観察し、未知の平均$\mu \in \mathbb{r}^d$ は $k$-sparse に制約される。
一連の先行研究は、サンプル複雑性による堅牢なスパース平均推定のための効率的なアルゴリズムを開発した。$\mathrm{poly}(k,\log d, 1/\epsilon)$とランタイム $d^2 \mathrm{poly}(k,\log d, 1/\epsilon)$。
特に、既存のアルゴリズムの最速実行時間は、高次元では禁止される二次(\omega(d^2)$)である。
この2次障壁は、これらのアルゴリズムがサンプル共分散行列に依存しており、これはサイズは$d^2$である。
我々の主な貢献は、$\mathrm{poly}(k,\log d,1/\epsilon)$サンプルを用いて、 \emph{subquadratic} 時間で実行される頑健なスパース平均推定アルゴリズムである。
また,頑健なスパースPCAに対する類似結果も提供する。
この結果は,バリアントによる電球問題の一般化版である弱い相関を検出するアルゴリズムの進歩に基づいている。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - 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) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Distribution Compression in Near-linear Time [27.18971095426405]
シンニングアルゴリズムを高速化するシンプルなメタプロデューサであるCompress++を紹介する。
$sqrtn$ポイントを$mathcalO(sqrtlog n/n)$統合エラーで提供し、Monte-Carlo の最大誤差を最大化します。
論文 参考訳（メタデータ） (2021-11-15T17:42:57Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。