論文の概要: Robust Sparse Mean Estimation via Incremental Learning
- arxiv url: http://arxiv.org/abs/2305.15276v1
- Date: Wed, 24 May 2023 16:02:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 14:29:35.393171
- Title: Robust Sparse Mean Estimation via Incremental Learning
- Title（参考訳）: インクリメンタル学習によるロバストスパース平均推定
- Authors: Jianhao Ma, Rui Ray Chen, Yinghui He, Salar Fattahi, Wei Hu
- Abstract要約: そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。
両課題を適度な条件下で克服する簡易平均推定器を提案する。
私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
- 参考スコア（独自算出の注目度）: 15.536082641659423
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of robust sparse mean estimation, where
the goal is to estimate a $k$-sparse mean from a collection of partially
corrupted samples drawn from a heavy-tailed distribution. Existing estimators
face two critical challenges in this setting. First, they are limited by a
conjectured computational-statistical tradeoff, implying that any
computationally efficient algorithm needs $\tilde\Omega(k^2)$ samples, while
its statistically-optimal counterpart only requires $\tilde O(k)$ samples.
Second, the existing estimators fall short of practical use as they scale
poorly with the ambient dimension. This paper presents a simple mean estimator
that overcomes both challenges under moderate conditions: it runs in
near-linear time and memory (both with respect to the ambient dimension) while
requiring only $\tilde O(k)$ samples to recover the true mean. At the core of
our method lies an incremental learning phenomenon: we introduce a simple
nonconvex framework that can incrementally learn the top-$k$ nonzero elements
of the mean while keeping the zero elements arbitrarily small. Unlike existing
estimators, our method does not need any prior knowledge of the sparsity level
$k$. We prove the optimality of our estimator by providing a matching
information-theoretic lower bound. Finally, we conduct a series of simulations
to corroborate our theoretical findings. Our code is available at
https://github.com/huihui0902/Robust_mean_estimation.
- Abstract（参考訳）: 本稿では,重み付き分布から引き出された部分的破損標本の集合から,k$-sparse平均を推定することを目的とした,ロバストなスパース平均推定問題について検討する。
既存の推定装置はこの設定で2つの重要な課題に直面している。
まず、計算効率の良いアルゴリズムは$\tilde\omega(k^2)$のサンプルを必要とするが、統計的に最適のアルゴリズムは$\tilde o(k)$のサンプルを必要とする。
第二に、既存の推定器は周囲の寸法に劣るほど実用性に欠ける。
本稿では, 実測値の回収に$\tilde O(k)$サンプルしか必要とせず, ほぼ直線時間とメモリ(双方の周囲次元に関して)で動作する, 適度な条件下で両課題を克服する単純な平均推定器を提案する。
私たちは、ゼロ要素を任意に小さく保ちながら、平均の最上位の$k$非ゼロ要素を漸進的に学習できる単純な非凸フレームワークを導入します。
既存の推定器とは異なり、我々の方法はスパーシティレベル$k$に関する事前知識を必要としない。
我々は情報理論上の下界を一致させることで推定器の最適性を証明する。
最後に,理論的な知見を裏付ける一連のシミュレーションを行う。
私たちのコードはhttps://github.com/huihui0902/Robust_mean_estimationで利用可能です。
関連論文リスト
- Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
我々は citekothari2018robust で導入された正準平方和プログラムを新たに解析する。
このプログラムは,すべての $varepsilon に対して[0,frac12)$ の誤差率を効率よく達成できることを示す。
論文 参考訳（メタデータ） (2024-11-21T16:57:05Z) - Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
測定制約のある問題では、大きなデータセットが利用可能であるにもかかわらず、大きなデータセットのごく一部でラベルを観測するのに手頃な価格にしかならない。
このことは、どのデータポイントが予算制約のあるラベルに最も有益であるかという重要な疑問を引き起こします。
本稿では,測定制約付きM推定フレームワークにおける最適個別化しきい値の推定に焦点をあてる。
論文 参考訳（メタデータ） (2024-11-21T00:21:17Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - 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) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳（メタデータ） (2020-06-19T22:49:42Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。