論文の概要: 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$がガウス的であり、任意の設定において線形時間推定器が堅牢な線形回帰について知られていないような環境でのみ知られていた。
我々の推定器とその解析法は、より高速な平均推定アルゴリズムの構築と、ガウスのラウンドリング技術と並行して測度論法を洗練し、統計サンプルの複雑さを向上する。
関連論文リスト
- 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) - Beyond Moments: Robustly Learning Affine Transformations with
Asymptotically Optimal Error [8.615625517708324]
サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。
本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
論文 参考訳(メタデータ) (2023-02-23T19:13:30Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳(メタデータ) (2022-02-27T09:41:43Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳(メタデータ) (2021-11-04T15:59:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。