論文の概要: Robust Regression Revisited: Acceleration and Improved Estimation Rates
- arxiv url: http://arxiv.org/abs/2106.11938v1
- Date: Tue, 22 Jun 2021 17:21:56 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 16:30:05.732088
- Title: Robust Regression Revisited: Acceleration and Improved Estimation Rates
- Title(参考訳): ロバスト回帰を再考:加速と予測率の改善
- Authors: Arun Jambulapati, Jerry Li, Tselil Schramm, Kevin Tian
- Abstract要約: 強い汚染モデルの下で, 統計的回帰問題に対する高速アルゴリズムについて検討する。
目的は、逆向きに破損したサンプルを与えられた一般化線形モデル(GLM)を概ね最適化することである。
実行時や推定保証が改善された頑健な回帰問題に対して,ほぼ直線的な時間アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 25.54653340884806
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study fast algorithms for statistical regression problems under the strong
contamination model, where the goal is to approximately optimize a generalized
linear model (GLM) given adversarially corrupted samples. Prior works in this
line of research were based on the robust gradient descent framework of Prasad
et. al., a first-order method using biased gradient queries, or the Sever
framework of Diakonikolas et. al., an iterative outlier-removal method calling
a stationary point finder.
We present nearly-linear time algorithms for robust regression problems with
improved runtime or estimation guarantees compared to the state-of-the-art. For
the general case of smooth GLMs (e.g. logistic regression), we show that the
robust gradient descent framework of Prasad et. al. can be accelerated, and
show our algorithm extends to optimizing the Moreau envelopes of Lipschitz GLMs
(e.g. support vector machines), answering several open questions in the
literature.
For the well-studied case of robust linear regression, we present an
alternative approach obtaining improved estimation rates over prior
nearly-linear time algorithms. Interestingly, our method starts with an
identifiability proof introduced in the context of the sum-of-squares algorithm
of Bakshi and Prasad, which achieved optimal error rates while requiring large
polynomial runtime and sample complexity. We reinterpret their proof within the
Sever framework and obtain a dramatically faster and more sample-efficient
algorithm under fewer distributional assumptions.
- Abstract(参考訳): 本研究では, 一般線形モデル (glm) を近似的に最適化することを目的とした, 強い汚染モデルの下での統計回帰問題に対する高速アルゴリズムについて検討した。
この系統の研究の以前の成果はプラサードらの強靭な勾配降下フレームワークに基づいていた。
al., バイアス勾配クエリを用いた一階述語法, あるいはダイアコニコラスのSeverフレームワークなど。
al. – 定常点ファインダを呼び出す反復的外乱除去法。
本稿では,実行時や推定保証を改良した頑健な回帰問題に対するほぼ線形時間アルゴリズムを提案する。
滑らかな GLM の一般の場合(例)
対物回帰(ロジスティック回帰)はプラサード等の頑健な勾配降下フレームワークを示す。
アル
アルゴリズムは、リプシッツglmのモローエンベロープ(例えば)を最適化するために拡張される。
文学におけるいくつかのオープンな質問に答えるベクトルマシンのサポート。
頑健な線形回帰をよく研究する場合には,従来のニア線形時間アルゴリズムよりも高い推定率を得る方法を提案する。
興味深いことに,本手法は,Bakshi と Prasad の2乗和アルゴリズム(sum-of-squares algorithm)の文脈で導入された同定可能性証明から始まる。
我々はこれらの証明をSeverフレームワーク内で再解釈し、より少ない分布仮定の下で劇的に高速でよりサンプル効率の高いアルゴリズムを得る。
関連論文リスト
- Stagewise Boosting Distributional Regression [0.0]
本稿では,分布回帰のための段階的ブースティング型アルゴリズムを提案する。
新たな正則化手法である相関フィルタリングを用いて拡張し,さらなる安定性を実現する。
大規模なデータセットを処理するメリットに加えて、近似の性質はより良い結果をもたらす可能性がある。
論文 参考訳(メタデータ) (2024-05-28T15:40:39Z) - Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。
本稿では,直感的に設計を記述し,設計選択について説明する。
本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
論文 参考訳(メタデータ) (2023-10-31T16:15:13Z) - A Novel Framework for Improving the Breakdown Point of Robust Regression
Algorithms [1.9594639581421422]
本稿では,頑健な回帰アルゴリズムの分解点を改善するための効果的なフレームワークを提案する。
反復局所探索(CORALS)を用いた一貫した頑健な回帰アルゴリズムを導出する。
論文 参考訳(メタデータ) (2023-05-20T15:59:33Z) - A Bayesian Robust Regression Method for Corrupted Data Reconstruction [5.298637115178182]
我々は適応的敵攻撃に抵抗できる効果的なロバスト回帰法を開発した。
まず TRIP (hard Thresholding approach to Robust regression with sImple Prior) アルゴリズムを提案する。
次に、より堅牢なBRHT (robust Bayesian Reweighting regression via Hard Thresholding) アルゴリズムを構築するためにベイズ再重み付け(Bayesian reweighting)というアイデアを用いる。
論文 参考訳(メタデータ) (2022-12-24T17:25:53Z) - Scalable Gaussian-process regression and variable selection using
Vecchia approximations [3.4163060063961255]
ヴェッキアをベースとしたミニバッチサブサンプリングは、偏りのない勾配推定器を提供する。
偏りのない勾配推定器を提供するVecchiaベースのミニバッチサブサンプリングを提案する。
論文 参考訳(メタデータ) (2022-02-25T21:22:38Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
政治政策の最適化は強化学習において難しい問題である。
オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
論文 参考訳(メタデータ) (2020-09-14T16:22:46Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳(メタデータ) (2020-07-12T19:33:50Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。
近勾配法はOWL回帰を解くための標準手法として用いられる。
未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
論文 参考訳(メタデータ) (2020-06-29T23:35:53Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-16T04:26:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。