論文の概要: Streaming Algorithms for High-Dimensional Robust Statistics
- arxiv url: http://arxiv.org/abs/2204.12399v2
- Date: Wed, 3 May 2023 17:59:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-04 19:10:02.848044
- Title: Streaming Algorithms for High-Dimensional Robust Statistics
- Title（参考訳）: 高次元ロバスト統計のストリーミングアルゴリズム
- Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
- Abstract要約: ほぼ最適なメモリ要件を持つ高次元ロバスト統計のための,最初の効率的なストリーミングアルゴリズムを開発した。
本研究の主な成果は,ハマー汚染モデルにおける高次元ロバスト平均推定の課題である。
- 参考スコア（独自算出の注目度）: 43.106438224356175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study high-dimensional robust statistics tasks in the streaming model. A
recent line of work obtained computationally efficient algorithms for a range
of high-dimensional robust estimation tasks. Unfortunately, all previous
algorithms require storing the entire dataset, incurring memory at least
quadratic in the dimension. In this work, we develop the first efficient
streaming algorithms for high-dimensional robust statistics with near-optimal
memory requirements (up to logarithmic factors). Our main result is for the
task of high-dimensional robust mean estimation in (a strengthening of) Huber's
contamination model. We give an efficient single-pass streaming algorithm for
this task with near-optimal error guarantees and space complexity nearly-linear
in the dimension. As a corollary, we obtain streaming algorithms with
near-optimal space complexity for several more complex tasks, including robust
covariance estimation, robust regression, and more generally robust stochastic
optimization.
- Abstract（参考訳）: ストリーミングモデルにおける高次元ロバスト統計タスクについて検討する。
近年,高次元ロバスト推定タスクにおいて計算効率の高いアルゴリズムが提案されている。
残念なことに、以前のアルゴリズムはすべてデータセット全体を格納する必要がある。
本研究では,(対数係数まで)最適に近いメモリ要件を持つ高次元ロバスト統計量に対して,最初の効率的なストリーミングアルゴリズムを開発した。
我々の主な結果は,フーバー汚染モデルにおける高次元ロバスト平均推定の課題である。
ほぼ最適誤差保証と空間の複雑さをほぼ線形とした,このタスクのための効率的なシングルパスストリーミングアルゴリズムを提案する。
結果として,ロバスト共分散推定,ロバスト回帰,より一般にロバストな確率最適化など,より複雑なタスクに対して,最適に近い空間複雑性を持つストリーミングアルゴリズムを得る。
関連論文リスト
- Randomized Dimension Reduction with Statistical Guarantees [0.27195102129095]
この論文は、高速な実行と効率的なデータ利用のためのアルゴリズムをいくつか探求している。
一般化と分散性を向上する様々なデータ拡張を組み込んだ学習アルゴリズムに着目する。
具体的には、第4章では、データ拡張整合正則化のための複雑性分析のサンプルを提示する。
論文 参考訳（メタデータ） (2023-10-03T02:01:39Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Learning the hub graphical Lasso model with the structured sparsity via
an efficient algorithm [1.0923877073891446]
ハブグラフィカルモデルを推定する二相アルゴリズムを提案する。
提案アルゴリズムはまず,乗算器の2つの交互方向法を用いてよい初期点を生成する。
その後、半滑らかなニュートン(SSN)ベースの拡張ラグランジアン法(ALM)を温め、実用的なタスクに十分正確な解を計算する。
論文 参考訳（メタデータ） (2023-08-17T08:24:28Z) - Best-Subset Selection in Generalized Linear Models: A Fast and
Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。
軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。
我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文 参考訳（メタデータ） (2023-08-01T03:11:31Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。
このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
論文 参考訳（メタデータ） (2020-02-20T12:04:05Z) - How to Solve Fair $k$-Center in Massive Data Models [5.3283669037198615]
我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。
主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
論文 参考訳（メタデータ） (2020-02-18T16:11:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。