論文の概要: 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$がガウス的であり、任意の設定において線形時間推定器が堅牢な線形回帰について知られていないような環境でのみ知られていた。
我々の推定器とその解析法は、より高速な平均推定アルゴリズムの構築と、ガウスのラウンドリング技術と並行して測度論法を洗練し、統計サンプルの複雑さを向上する。
関連論文リスト
- 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 [114.99728495239056]
群分散ロバスト最適化(GDRO)は凸凸凹サドル点問題である。
オンライン学習は、各ラウンドに必要なサンプル数を$m$から$$に減らし、同じサンプルの複雑さを維持するために使用される。
我々は、分布依存収束率を導出できる重み付きGDROの新しい定式化を導出する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳（メタデータ） (2023-01-17T18:44:41Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。