論文の概要: Robust Mean Estimation Without a Mean: Dimension-Independent Error in
Polynomial Time for Symmetric Distributions
- arxiv url: http://arxiv.org/abs/2302.10844v1
- Date: Tue, 21 Feb 2023 17:52:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 14:06:53.936721
- Title: Robust Mean Estimation Without a Mean: Dimension-Independent Error in
Polynomial Time for Symmetric Distributions
- Title（参考訳）: 意味のないロバスト平均推定:対称分布の多項式時間における次元非依存誤差
- Authors: Gleb Novikov, David Steurer, Stefan Tiegel
- Abstract要約: モーメント境界のない分布の平均/位置パラメータを頑健に推定する問題について検討する。
誤差に次元依存因子を生じさせることなく効率よく位置を推定できるアルゴリズムの列を与える。
- 参考スコア（独自算出の注目度）: 7.143879014059894
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study the problem of robustly estimating the mean/location
parameter of distributions without moment bounds. For a large class of
distributions satisfying natural symmetry constraints we give a sequence of
algorithms that can efficiently estimate its location without incurring
dimension-dependent factors in the error. Concretely, suppose an adversary can
arbitrarily corrupt an $\varepsilon$-fraction of the observed samples. For
every $k \in \mathbb{N}$, we design an estimator using time and samples
$\tilde{O}({d^k})$ such that the dependence of the error on the corruption
level $\varepsilon$ is an additive factor of $O(\varepsilon^{1-\frac{1}{2k}})$.
The dependence on other problem parameters is also nearly optimal. Our class
contains products of arbitrary symmetric one-dimensional distributions as well
as elliptical distributions, a vast generalization of the Gaussian
distribution. Examples include product Cauchy distributions and multi-variate
$t$-distributions. In particular, even the first moment might not exist.
We provide the first efficient algorithms for this class of distributions.
Previously, such results where only known under boundedness assumptions on the
moments of the distribution and in particular, are provably impossible in the
absence of symmetry [KSS18, CTBJ22]. For the class of distributions we
consider, all previous estimators either require exponential time or incur
error depending on the dimension. Our algorithms are based on a generalization
of the filtering technique [DK22]. We show how this machinery can be combined
with Huber-loss-based approach to work with projections of the noise. Moreover,
we show how sum-of-squares proofs can be used to obtain algorithmic guarantees
even for distributions without first moment. We believe that this approach may
find other application in future works.
- Abstract（参考訳）: 本研究では,モーメント境界のない分布の平均/位置パラメータを頑健に推定する問題について検討する。
自然対称性の制約を満たす分布の広いクラスに対して、その位置を誤差の次元依存性因子を伴わずに効率的に推定できるアルゴリズムの列を与える。
具体的には、敵が観測されたサンプルの$\varepsilon$-fractionを任意に破壊できると仮定する。
すべての$k \in \mathbb{N}$に対して、時間とサンプルを使用した推定器を設計する。$\tilde{O}({d^k})$ は、汚職レベルへの誤差の依存が$O(\varepsilon^{1-\frac{1}{2k}})$ の加算因子である。
他の問題パラメータへの依存もほぼ最適である。
本クラスは、任意の対称一次元分布の積と、ガウス分布の広範な一般化である楕円分布を含む。
例えば、製品コーシー分布や多変量$t$-分布などがある。
特に、最初の瞬間でさえ存在しないかもしれない。
この分布のクラスに対する最初の効率的なアルゴリズムを提供する。
従来、分布のモーメントにおける有界性仮定でのみ知られているような結果は、対称性(KSS18, CTBJ22)の欠如で証明不可能であった。
我々が考慮する分布のクラスについて、すべての過去の推定器は指数時間または次元に依存する不正確な誤差を必要とする。
我々のアルゴリズムはフィルタリング技術[dk22]の一般化に基づいている。
この機械とフーバーロスに基づく手法が組み合わさることで,騒音の投影と協調できることを示す。
さらに,第1モーメントのない分布においても,二乗和証明を用いてアルゴリズム的保証を得る方法を示す。
このアプローチは将来の作業で他のアプリケーションを見つける可能性があると考えています。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。