論文の概要: Robust Mean Estimation Without Moments for Symmetric Distributions
- arxiv url: http://arxiv.org/abs/2302.10844v2
- Date: Wed, 8 Nov 2023 18:49:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-09 20:14:35.857224
- Title: Robust Mean Estimation Without Moments for Symmetric Distributions
- Title（参考訳）: 対称分布に対するモーメントのないロバスト平均推定
- Authors: Gleb Novikov, David Steurer, Stefan Tiegel
- Abstract要約: 大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
- 参考スコア（独自算出の注目度）: 7.105512316884493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of robustly estimating the mean or location parameter
without moment assumptions. We show that for a large class of symmetric
distributions, the same error as in the Gaussian setting can be achieved
efficiently. The distributions we study include products of arbitrary symmetric
one-dimensional distributions, such as product Cauchy distributions, as well as
elliptical distributions.
For product distributions and elliptical distributions with known scatter
(covariance) matrix, we show that given an $\varepsilon$-corrupted sample, we
can with probability at least $1-\delta$ estimate its location up to error
$O(\varepsilon \sqrt{\log(1/\varepsilon)})$ using $\tfrac{d\log(d) +
\log(1/\delta)}{\varepsilon^2 \log(1/\varepsilon)}$ samples. This result
matches the best-known guarantees for the Gaussian distribution and known SQ
lower bounds (up to the $\log(d)$ factor). For elliptical distributions with
unknown scatter (covariance) matrix, we propose a sequence of efficient
algorithms that approaches this optimal error. Specifically, for every $k \in
\mathbb{N}$, we design an estimator using time and samples $\tilde{O}({d^k})$
achieving error $O(\varepsilon^{1-\frac{1}{2k}})$. This matches the error and
running time guarantees when assuming certifiably bounded moments of order up
to $k$. For unknown covariance, such error bounds of $o(\sqrt{\varepsilon})$
are not even known for (general) sub-Gaussian distributions.
Our algorithms are based on a generalization of the well-known filtering
technique. We show how this machinery can be combined with Huber-loss-based
techniques to work with projections of the noise that behave more nicely than
the initial noise. Moreover, we show how SoS proofs can be used to obtain
algorithmic guarantees even for distributions without a first moment. We
believe that this approach may find other applications in future works.
- Abstract（参考訳）: モーメント仮定なしで平均パラメータや位置パラメータを頑健に推定する問題について検討する。
対称分布の大きいクラスでは、ガウス設定の場合と同じ誤差を効率的に達成できることを示す。
本研究では, 任意の対称一次元分布, 積コーシー分布, 楕円分布の積について検討した。
既知の散乱(共分散)行列を持つ積の分布や楕円分布について、$\varepsilon$-corruptedサンプルが与えられた場合、少なくとも1-\delta$はその位置を誤差$O(\varepsilon \sqrt{\log(1/\varepsilon)})$を使用すると$$\tfrac{d\log(d) + \log(1/\delta)}{\varepsilon^2 \log(1/\varepsilon)}$サンプルで推定できることを示す。
この結果はガウス分布と既知の SQ の下界($\log(d)$ factor まで)の最もよく知られた保証と一致する。
未知散乱(共分散)行列を持つ楕円分布に対して,この最適誤差に接近する効率的なアルゴリズムの列を提案する。
具体的には、すべての$k \in \mathbb{N}$に対して、時間とサンプルを使用した推定器を設計し、エラーを$O(\varepsilon^{1-\frac{1}{2k}})$とする。
これは、最大$k$の確定可能な有界モーメントを仮定した場合のエラーと実行時間の保証と一致する。
未知の共分散に対しては、$o(\sqrt{\varepsilon})$のそのような誤差境界は(一般)ガウス分布では知られていない。
我々のアルゴリズムはよく知られたフィルタリング技術の一般化に基づいている。
この機械をハマーロス方式の手法と組み合わせて、初期ノイズよりも優しく振る舞う騒音を投影する方法について述べる。
さらに,最初の瞬間のない分布においても,sos証明を用いてアルゴリズムによる保証を得る方法を示す。
このアプローチは将来の作業で他のアプリケーションを見つける可能性があると考えています。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance
Estimation for Subgaussian Distributions [8.40077201352607]
我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。
我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
論文 参考訳（メタデータ） (2023-01-28T16:57:46Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。