論文の概要: Robust Mean Estimation in High Dimensions via $\ell_0$ Minimization
- arxiv url: http://arxiv.org/abs/2008.09239v1
- Date: Fri, 21 Aug 2020 00:19:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 21:27:10.845577
- Title: Robust Mean Estimation in High Dimensions via $\ell_0$ Minimization
- Title(参考訳): $\ell_0$ 最小化による高次元ロバスト平均推定
- Authors: Jing Liu, Aditya Deshmukh, Venugopal V. Veeravalli
- Abstract要約: 本研究では,高次元におけるロバスト平均推定問題について検討し,データポイントの0.5ドル分を任意に破壊することができることを示した。
圧縮センシングによってモチベーションを得た結果、ロバスト平均推定問題を$ell_p$$(0p1)$の最小化として定式化する。
合成データ実験と実データ実験の両方で、提案アルゴリズムは最先端のロバストな平均推定法を大幅に上回っていることが示された。
- 参考スコア(独自算出の注目度): 21.65637588606572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the robust mean estimation problem in high dimensions, where $\alpha
<0.5$ fraction of the data points can be arbitrarily corrupted. Motivated by
compressive sensing, we formulate the robust mean estimation problem as the
minimization of the $\ell_0$-`norm' of the outlier indicator vector, under
second moment constraints on the inlier data points. We prove that the global
minimum of this objective is order optimal for the robust mean estimation
problem, and we propose a general framework for minimizing the objective. We
further leverage the $\ell_1$ and $\ell_p$ $(0<p<1)$, minimization techniques
in compressive sensing to provide computationally tractable solutions to the
$\ell_0$ minimization problem. Both synthetic and real data experiments
demonstrate that the proposed algorithms significantly outperform
state-of-the-art robust mean estimation methods.
- Abstract(参考訳): 高次元におけるロバスト平均推定問題について検討し、データポイントの$\alpha <0.5$分を任意に破壊することができる。
圧縮センシングによって動機づけられたロバスト平均推定問題を、外れ値インジケータベクトルの$\ell_0$-`norm' の最小化として、外れ値データ点に対する第2モーメント制約下で定式化する。
我々は,この目標の最小値がロバスト平均推定問題に対して最適であることを示すとともに,目標を最小化する汎用フレームワークを提案する。
さらに、$\ell_1$および$\ell_p$$(0<p<1)$, 圧縮センシングにおける最小化技術を活用して、$\ell_0$最小化問題に対する計算処理可能な解を提供する。
合成データ実験と実データ実験の両方で、提案アルゴリズムは最先端のロバストな平均推定法を大幅に上回ることを示した。
関連論文リスト
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳(メタデータ) (2023-11-21T18:50:38Z) - Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。
両課題を適度な条件下で克服する簡易平均推定器を提案する。
私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
論文 参考訳(メタデータ) (2023-05-24T16:02:28Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳(メタデータ) (2022-11-29T18:38:40Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳(メタデータ) (2021-11-12T01:51:50Z) - NoisyCUR: An algorithm for two-cost budgeted matrix completion [13.094997642327371]
matrix completionは、機械学習とデータ分析のユビキタスなツールだ。
この設定のための回帰ベースの補完アルゴリズムを紹介します。
我々は,合成データと実データの両方における手法の性能を実験的に検証した。
論文 参考訳(メタデータ) (2021-04-16T10:39:56Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳(メタデータ) (2021-02-23T18:25:13Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。
我々は「一般化された準次数」の存在を識別する
一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-05-28T15:14:33Z) - 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) - High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。
我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
論文 参考訳(メタデータ) (2020-05-04T10:48:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。