論文の概要: Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean
Estimation and Linear Regression
- arxiv url: http://arxiv.org/abs/2312.01547v1
- Date: Mon, 4 Dec 2023 00:31:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 16:45:27.555296
- Title: Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean
Estimation and Linear Regression
- Title（参考訳）: ハマー汚染を持つガウスの近似アルゴリズム:平均推定と線形回帰
- Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
- Abstract要約: 最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。
堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。
これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
- 参考スコア（独自算出の注目度）: 44.13655983242414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fundamental problems of Gaussian mean estimation and linear
regression with Gaussian covariates in the presence of Huber contamination. Our
main contribution is the design of the first sample near-optimal and almost
linear-time algorithms with optimal error guarantees for both of these
problems. Specifically, for Gaussian robust mean estimation on $\mathbb{R}^d$
with contamination parameter $\epsilon \in (0, \epsilon_0)$ for a small
absolute constant $\epsilon_0$, we give an algorithm with sample complexity $n
= \tilde{O}(d/\epsilon^2)$ and almost linear runtime that approximates the
target mean within $\ell_2$-error $O(\epsilon)$. This improves on prior work
that achieved this error guarantee with polynomially suboptimal sample and time
complexity. For robust linear regression, we give the first algorithm with
sample complexity $n = \tilde{O}(d/\epsilon^2)$ and almost linear runtime that
approximates the target regressor within $\ell_2$-error $O(\epsilon)$. This is
the first polynomial sample and time algorithm achieving the optimal error
guarantee, answering an open question in the literature. At the technical
level, we develop a methodology that yields almost-linear time algorithms for
multi-directional filtering that may be of broader interest.
- Abstract（参考訳）: ガウス平均推定とガウス共変量を用いた線形回帰の基本問題について, フーバー汚染の存在下で検討した。
我々の主な貢献は、これら2つの問題に対して最適なエラー保証を備えた、ほぼ最適およびほぼ線形時間アルゴリズムの最初のサンプルの設計である。
具体的には、gaussian robust mean estimation on $\mathbb{r}^d$ with contamination parameter $\epsilon \in (0, \epsilon_0)$ for a small absolute constant $\epsilon_0$ に対して、サンプル複雑性 $n = \tilde{o}(d/\epsilon^2)$ のアルゴリズムと、$\ell_2$-error $o(\epsilon)$の目標平均を近似するほぼ線形なランタイムを与える。
これにより、多項式の準最適サンプルと時間の複雑さにより、このエラー保証を達成する事前作業が改善される。
堅牢な線形回帰のために、サンプル複雑性$n = \tilde{O}(d/\epsilon^2)$と、ターゲット回帰器を$\ell_2$-error $O(\epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。
これは、最適誤差保証を達成する最初の多項式のサンプルと時間アルゴリズムであり、文献の公開質問に答えている。
技術的レベルでは、より広範な関心を持つ多方向フィルタリングのためのほぼ直線的な時間アルゴリズムを生成する手法を開発する。
関連論文リスト
- Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。
それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。
技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文 参考訳（メタデータ） (2024-03-15T15:51:27Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。