論文の概要: Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization

• arxiv url: http://arxiv.org/abs/2007.15839v2
• Date: Tue, 19 Jan 2021 00:27:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-04 06:30:29.707737
• Title: Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• Title（参考訳）: 後悔の最小化によるロバストで重み付き平均推定
• Authors: Samuel B. Hopkins, Jerry Li, Fred Zhang
• Abstract要約: 本研究では, 試料が逆向きに破壊されたり, 分布が重くなったりした場合に, 分布の平均を高次元で推定する問題について検討する。 メタプロブレムと双対性定理は、高次元におけるロバストで重み付き平均推定に関する新しい統一的な見解をもたらす。
• 参考スコア（独自算出の注目度）: 21.64869023699999
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent developments in robust statistics have established efficient and (near) optimal procedures for both settings. However, the algorithms developed on each side tend to be sophisticated and do not directly transfer to the other, with many of them having ad-hoc or complicated analyses. In this paper, we provide a meta-problem and a duality theorem that lead to a new unified view on robust and heavy-tailed mean estimation in high dimensions. We show that the meta-problem can be solved either by a variant of the Filter algorithm from the recent literature on robust estimation or by the quantum entropy scoring scheme (QUE), due to Dong, Hopkins and Li (NeurIPS '19). By leveraging our duality theorem, these results translate into simple and efficient algorithms for both robust and heavy-tailed settings. Furthermore, the QUE-based procedure has run-time that matches the fastest known algorithms on both fronts. Our analysis of Filter is through the classic regret bound of the multiplicative weights update method. This connection allows us to avoid the technical complications in previous works and improve upon the run-time analysis of a gradient-descent-based algorithm for robust mean estimation by Cheng, Diakonikolas, Ge and Soltanolkotabi (ICML '20).
• Abstract（参考訳）: 本研究では, 試料が逆破壊されたり, 分布が重かったりした場合に, 分布の平均を高次元で推定する問題について検討する。 近年のロバスト統計学の発展は、両方の設定に対して効率的かつ(ほぼ)最適な手順を確立している。 しかしながら、各側で開発されたアルゴリズムは洗練されており、直接他へ転送することはない傾向にあり、その多くはアドホックまたは複雑な分析を持つ。 本稿では,メタプロブレムと双対性定理を提案し,高次元におけるロバストおよび重み付き平均推定の新しい統一的な視点を導いた。 本研究では,最近のロバスト推定に関する文献からのフィルタアルゴリズムの変種や,ドン,ホプキンス,li (neurips '19) による量子エントロピースコアリングスキーム (que) によって,メタプロブレムが解決できることを示す。 我々の双対性定理を利用することで、これらの結果は堅牢かつ重み付けされた設定の両方に対して単純かつ効率的なアルゴリズムに変換される。 さらに、QUEベースのプロシージャは、両方のフロントで知られている最も高速なアルゴリズムにマッチする実行時間を持つ。 フィルタの解析は、乗法重み付け更新法の古典的な後悔のバウンドを通して行う。 この接続により,過去の作業における技術的複雑化を回避し,cng,diakonikolas,ge,soltanolkotabi (icml '20) によるロバスト平均推定のための勾配-descent-basedアルゴリズムの実行時間解析を改善した。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Robust recovery for stochastic block models [16.74630355427558]
  ブロックモデルのロバストバージョンにおいて、弱い回復のための効率的なアルゴリズムを開発する。 その結果,ブロックモデルにロバストさの代償はないことがわかった。
  論文  参考訳（メタデータ） (2021-11-16T15:43:00Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
  ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。 このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
  論文  参考訳（メタデータ） (2020-02-20T12:04:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。