Huber汚染下の最適誤差を持つガウシアンに対する頑健なスパース推定

我々は、Huberの汚染モデルにおけるガウシアンのスパース推定タスクを研究し、平均推定、主成分分析（PCA）、および線形回帰に焦点を当てます。これらのタスクのそれぞれに対し、サンプル数と計算効率が良く、最適誤差保証を持つ頑健な推定器を初めて提供します。全ての先行の効率的なアルゴリズムは、定量的にサブ最適な誤差を引き起こします。具体的には、汚染率が>0のRᵈにおけるガウシアン頑健kスパース平均推定に対して、我々のアルゴリズムはサンプル複雑性(k²/²)polylog(d/)を持ち、サンプル多項式時間で実行され、対象の平均を₂誤差O()内で近似します。以前の効率的なアルゴリズムは本質的に誤差( (1/) )を引き起こします。技術的には、他の応用を見つける可能性のあるスパース領域における新しい多次元フィルタリング手法を開発します。