Fugu-MT 論文翻訳(概要): Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers

論文の概要: Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers

arxiv url: http://arxiv.org/abs/2008.08071v5
Date: Mon, 3 May 2021 04:25:56 GMT
ステータス: 処理完了
システム内更新日: 2022-10-27 21:32:16.652097
Title: Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
Title（参考訳）: 任意外乱を用いた不完全データのロバスト平均推定
Authors: Lunjia Hu, Omer Reingold
Abstract要約: 我々は,$N$の例として,$d$次元分布の平均を頑健に推定する問題について検討する。ほぼ線形時間における情報理論的に最適な次元非依存誤差保証を用いて分布の平均を推定するアルゴリズムを示す。
参考スコア（独自算出の注目度）: 7.224832132296238
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $\varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $\varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $\widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.
Abstract（参考訳）: 我々は、すべての例の座標が欠落している可能性があり、$\varepsilon N$例が任意に破損している場合、$N$例が与えられた$d$次元分布の平均を頑健に推定する問題を研究する。各座標が $\varepsilon n$ 以上の定数係数で現れると仮定すると、ほぼ線形時間 $\widetilde o(nd)$ において、情報理論上最適次元独立な誤差保証を持つ分布の平均を推定するアルゴリズムを示す。この結果は、計算効率の良いロバスト推定に関する最近の研究を、より広く適用可能な不完全データ設定に拡張する。

関連論文リスト

A Combinatorial Approach to Robust PCA [18.740048806623037]
敵の汚職下でのガウスデータの回復問題について検討する。ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
論文参考訳（メタデータ） (2023-11-28T01:49:51Z)
Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。また、Acharyaなどのアルゴリズムの改良版も提供します。
論文参考訳（メタデータ） (2023-06-20T06:13:56Z)
Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-19T01:09:24Z)
Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
論文参考訳（メタデータ） (2022-12-26T18:37:28Z)
Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文参考訳（メタデータ） (2022-12-15T18:27:39Z)
A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文参考訳（メタデータ） (2022-02-23T16:10:23Z)
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。 PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文参考訳（メタデータ） (2021-11-04T15:59:44Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
$\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文参考訳（メタデータ） (2020-06-13T06:09:27Z)
Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions [19.439945058410203]
高次元状態におけるサンプル外リスク推定の問題について検討する。広範囲にわたる経験的証拠は、アウト・ワン・アウト・クロス・バリデーションの正確さを裏付ける。この理論の技術的利点の1つは、拡張可能な近似LOに関する最近の文献から得られたいくつかの結果を明確化し、接続することができることである。
論文参考訳（メタデータ） (2020-03-03T20:07:07Z)

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