論文の概要: Online Robust Regression via SGD on the l1 loss
- arxiv url: http://arxiv.org/abs/2007.00399v1
- Date: Wed, 1 Jul 2020 11:38:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 22:45:44.380031
- Title: Online Robust Regression via SGD on the l1 loss
- Title（参考訳）: L1損失に対するSGDによるオンラインロバスト回帰
- Authors: Scott Pesme and Nicolas Flammarion
- Abstract要約: ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
- 参考スコア（独自算出の注目度）: 19.087335681007477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the robust linear regression problem in the online setting where
we have access to the data in a streaming manner, one data point after the
other. More specifically, for a true parameter $\theta^*$, we consider the
corrupted Gaussian linear model $y = \langle x , \ \theta^* \rangle +
\varepsilon + b$ where the adversarial noise $b$ can take any value with
probability $\eta$ and equals zero otherwise. We consider this adversary to be
oblivious (i.e., $b$ independent of the data) since this is the only
contamination model under which consistency is possible. Current algorithms
rely on having the whole data at hand in order to identify and remove the
outliers. In contrast, we show in this work that stochastic gradient descent on
the $\ell_1$ loss converges to the true parameter vector at a $\tilde{O}( 1 /
(1 - \eta)^2 n )$ rate which is independent of the values of the contaminated
measurements. Our proof relies on the elegant smoothing of the non-smooth
$\ell_1$ loss by the Gaussian data and a classical non-asymptotic analysis of
Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of
the efficiency of this simple and highly scalable algorithm.
- Abstract（参考訳）: オンライン環境でのロバストな線形回帰問題を考えると、ストリーミング方式でデータにアクセスする場合、1つのデータポイントが次になる。
より具体的には、真のパラメータ $\theta^*$ に対して、崩壊したガウス線型モデル $y = \langle x , \ \theta^* \rangle + \varepsilon + b$ を考える。
我々は、この敵は、一貫性が可能である唯一の汚染モデルであるため、(データから独立して$b$)不可避であると考えている。
現在のアルゴリズムは、外れ値を特定し、取り除くためにデータ全体を手元に置いておくことに依存している。
対照的に、この研究において、$\ell_1$損失の確率勾配降下は、汚染された測定値に依存しない$\tilde{O}(1 / (1 - \eta)^2 n)$レートで真のパラメータベクトルに収束することを示した。
我々の証明は、ガウスデータによる非滑らかな$\ell_1$損失のエレガントな平滑化と、Polyak-Ruppert平均SGDの古典的非漸近解析に依存している。
さらに、この単純でスケーラブルなアルゴリズムの効率性を示す実験的な証拠を提供する。
関連論文リスト
- Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳（メタデータ） (2023-10-30T19:52:43Z) - Noise Stability Optimization for Flat Minima with Tight Rates [18.009376840944284]
関数 $F(W) = mathbbE_U[f(W + U)]$ を最小化する方法を示す。
私たちは、U$と$-U$の両方にノイズを加えるシンプルな実用的なアルゴリズムを設計します。
論文 参考訳（メタデータ） (2023-06-14T14:58:36Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$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
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。