Fugu-MT 論文翻訳(概要): Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination

論文の概要: Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination

arxiv url: http://arxiv.org/abs/2502.14772v1
Date: Thu, 20 Feb 2025 17:53:13 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-21 14:28:39.581452
Title: Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Title（参考訳）: 平均シフト汚染下における効率的な多変量ロバスト平均推定
Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Thanasis Pittas,
Abstract要約: 平均シフト汚染を用いた高次元ロバスト平均推定のための計算効率のよい最初のアルゴリズムを提案する。提案アルゴリズムは, ほぼ最適サンプルの複雑性を持ち, サンプル・ポリノミカル時間で動作し, ターゲット平均を任意の精度で近似する。
参考スコア（独自算出の注目度）: 35.67742880001828
License:
Abstract: We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given a set of points in $\mathbb{R}^d$ generated i.i.d. via the following process. For a parameter $\alpha<1/2$, the $i$-th sample $x_i$ is obtained as follows: with probability $1-\alpha$, $x_i$ is drawn from $\mathcal{N}(\mu, I)$, where $\mu \in \mathbb{R}^d$ is the target mean; and with probability $\alpha$, $x_i$ is drawn from $\mathcal{N}(z_i, I)$, where $z_i$ is unknown and potentially arbitrary. Prior work characterized the information-theoretic limits of this task. Specifically, it was shown that, in contrast to Huber contamination, in the presence of mean-shift contamination consistent estimation is possible. On the other hand, all known robust estimators in the mean-shift model have running times exponential in the dimension. Here we give the first computationally efficient algorithm for high-dimensional robust mean estimation with mean-shift contamination that can tolerate a constant fraction of outliers. In particular, our algorithm has near-optimal sample complexity, runs in sample-polynomial time, and approximates the target mean to any desired accuracy. Conceptually, our result contributes to a growing body of work that studies inference with respect to natural noise models lying in between fully adversarial and random settings.
Abstract（参考訳）: 平均シフト汚染の存在下での恒等性共分散ガウスのロバスト平均推定のアルゴリズム的問題について検討する。この汚染モデルでは、以下のプロセスにより$\mathbb{R}^d$ 生成された点の集合が与えられる。パラメータ $\alpha<1/2$ に対して、$i$-th サンプル $x_i$ は、次のようになる: 確率 $1-\alpha$, $x_i$ は $\mathcal{N}(\mu, I)$ から引き出されるが、$\mu \in \mathbb{R}^d$ はターゲット平均であり、確率 $\alpha$ では $x_i$ は $\mathcal{N}(z_i, I)$ から引き出される。以前の研究は、このタスクの情報理論の限界を特徴付けていた。具体的には,ハマー汚染とは対照的に,平均シフト汚染が一貫した推定が可能であった。一方、平均シフトモデルにおける全ての既知のロバスト推定器は、その次元において指数関数的な実行時間を持つ。ここでは、平均シフト汚染を用いた高次元ロバスト平均推定のための計算効率のよい最初のアルゴリズムについて述べる。特に,本アルゴリズムは, ほぼ最適サンプル量を持ち, サンプリング・ポリノミカル時間で動作し, ターゲット平均を任意の精度で近似する。概念的には,本研究の結果は,完全対向的およびランダムな設定の間に存在する自然騒音モデルに対する推論研究の進展に寄与する。

関連論文リスト

Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond [28.931489333515618]
非正規化確率密度 $piproptomathrme-V$ が与えられたとき、正規化定数 $Z=int_mathbbRdmathrme-V(x)mathrmdx$ または自由エネルギー $F=-log Z$ はベイズ統計学、統計力学、機械学習において重要な問題である。本稿では,逆拡散型サンプリング器に基づく新しい正規化定数推定アルゴリズムを提案し,その複雑さを解析するための枠組みを確立する。
論文参考訳（メタデータ） (2025-02-07T00:05:28Z)
Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文参考訳（メタデータ） (2025-01-09T18:31:35Z)
Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-01T17:59:53Z)
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文参考訳（メタデータ） (2024-03-15T15:51:27Z)
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
論文参考訳（メタデータ） (2023-12-05T01:13:10Z)
Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。また、Acharyaなどのアルゴリズムの改良版も提供します。
論文参考訳（メタデータ） (2023-06-20T06:13:56Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文参考訳（メタデータ） (2022-03-18T18:50:52Z)
The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文参考訳（メタデータ） (2020-12-31T18:24:41Z)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。