論文の概要: Optimal Robust Linear Regression in Nearly Linear Time
- arxiv url: http://arxiv.org/abs/2007.08137v1
- Date: Thu, 16 Jul 2020 06:44:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 22:50:49.477871
- Title: Optimal Robust Linear Regression in Nearly Linear Time
- Title（参考訳）: 近似線形時間における最適ロバスト線形回帰
- Authors: Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael I.
Jordan, Nicolas Flammarion, Peter L. Bartlett
- Abstract要約: 学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
- 参考スコア（独自算出の注目度）: 97.11565882347772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of high-dimensional robust linear regression where a
learner is given access to $n$ samples from the generative model $Y = \langle
X,w^* \rangle + \epsilon$ (with $X \in \mathbb{R}^d$ and $\epsilon$
independent), in which an $\eta$ fraction of the samples have been
adversarially corrupted. We propose estimators for this problem under two
settings: (i) $X$ is L4-L2 hypercontractive, $\mathbb{E} [XX^\top]$ has bounded
condition number and $\epsilon$ has bounded variance and (ii) $X$ is
sub-Gaussian with identity second moment and $\epsilon$ is sub-Gaussian. In
both settings, our estimators: (a) Achieve optimal sample complexities and
recovery guarantees up to log factors and (b) Run in near linear time
($\tilde{O}(nd / \eta^6)$). Prior to our work, polynomial time algorithms
achieving near optimal sample complexities were only known in the setting where
$X$ is Gaussian with identity covariance and $\epsilon$ is Gaussian, and no
linear time estimators were known for robust linear regression in any setting.
Our estimators and their analysis leverage recent developments in the
construction of faster algorithms for robust mean estimation to improve
runtimes, and refined concentration of measure arguments alongside Gaussian
rounding techniques to improve statistical sample complexities.
- Abstract（参考訳）: 生成モデル $y = \langle x,w^* \rangle + \epsilon$ ($x \in \mathbb{r}^d$ と $\epsilon$ independent) から学習者が$n$ のサンプルにアクセスできるような高次元のロバストな線形回帰の問題を研究し、そのサンプルのうち$\eta$ の割が反対に破損している。
この問題に対する推定器を2つの設定で提案する。
(i) $x$ は l4-l2 hypercontractive、$\mathbb{e} [xx^\top]$ は有界条件数、$\epsilon$ は有界分散を持つ。
(ii) $x$ は等式 2 番目の部分ガウジアンであり、$\epsilon$ は準ガウジアンである。
どちらの設定でも、推定器は以下のとおりです。
(a)最適試料複雑度及び回収保証をログファクターまで達成し、
(b) ほぼ線形時間 (\tilde{O}(nd / \eta^6)$) で実行する。
我々の研究に先立ち、最適なサンプル複素量に近い多項式時間アルゴリズムは、同一性共分散を持つ$X$がガウス的であり、$\epsilon$がガウス的であり、任意の設定において線形時間推定器が堅牢な線形回帰について知られていないような環境でのみ知られていた。
我々の推定器とその解析法は、より高速な平均推定アルゴリズムの構築と、ガウスのラウンドリング技術と並行して測度論法を洗練し、統計サンプルの複雑さを向上する。
関連論文リスト
- Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。
我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文 参考訳（メタデータ） (2024-10-02T15:21:07Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳（メタデータ） (2024-03-15T15:51:27Z) - Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean
Estimation and Linear Regression [44.13655983242414]
最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。
堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。
これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
論文 参考訳（メタデータ） (2023-12-04T00:31:16Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Robust Sub-Gaussian Principal Component Analysis and Width-Independent
Schatten Packing [22.337756118270217]
基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。
最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。
私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
論文 参考訳（メタデータ） (2020-06-12T07:45:38Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。