Fugu-MT 論文翻訳(概要): Entangled Mean Estimation in High-Dimensions

論文の概要: Entangled Mean Estimation in High-Dimensions

arxiv url: http://arxiv.org/abs/2501.05425v1
Date: Thu, 09 Jan 2025 18:31:35 GMT
ステータス: 翻訳完了
システム内更新日: 2025-01-10 13:59:54.195622
Title: Entangled Mean Estimation in High-Dimensions
Title（参考訳）: 高次元における絡み合い平均推定
Authors: Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas,
Abstract要約: 信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
参考スコア（独自算出の注目度）: 36.97113089188035
License:
Abstract: We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. Specifically, given $N$ independent random points $x_1,\ldots,x_N$ in $\mathbb{R}^D$ and a parameter $\alpha \in (0, 1)$ such that each $x_i$ is drawn from a Gaussian with mean $\mu$ and unknown covariance, and an unknown $\alpha$-fraction of the points have identity-bounded covariances, the goal is to estimate the common mean $\mu$. The one-dimensional version of this task has received significant attention in theoretical computer science and statistics over the past decades. Recent work [LY20; CV24] has given near-optimal upper and lower bounds for the one-dimensional setting. On the other hand, our understanding of even the information-theoretic aspects of the multivariate setting has remained limited. In this work, we design a computationally efficient algorithm achieving an information-theoretically near-optimal error. Specifically, we show that the optimal error (up to polylogarithmic factors) is $f(\alpha,N) + \sqrt{D/(\alpha N)}$, where the term $f(\alpha,N)$ is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate. Our algorithmic approach employs an iterative refinement strategy, whereby we progressively learn more accurate approximations $\hat \mu$ to $\mu$. This is achieved via a novel rejection sampling procedure that removes points significantly deviating from $\hat \mu$, as an attempt to filter out unusually noisy samples. A complication that arises is that rejection sampling introduces bias in the distribution of the remaining points. To address this issue, we perform a careful analysis of the bias, develop an iterative dimension-reduction strategy, and employ a novel subroutine inspired by list-decodable learning that leverages the one-dimensional result.
Abstract（参考訳）: 信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。具体的には、$N$ 独立乱数点 $x_1,\ldots,x_N$ in $\mathbb{R}^D$ とパラメータ $\alpha \in (0, 1)$ が与えられたとき、各$x_i$ は平均$\mu$ と未知の共分散を持つガウスから引き出される。このタスクの1次元バージョンは、過去数十年間、理論計算機科学と統計学において大きな注目を集めてきた。最近の研究[LY20, CV24]は, 1次元設定に対して, ほぼ最適上界と下界を与えている。一方,多変量設定における情報理論的側面の理解は依然として限られている。本研究では,情報理論的に近似誤差を実現する計算効率のよいアルゴリズムを設計する。具体的には、最適誤差が$f(\alpha,N) + \sqrt{D/(\alpha N)}$であることを示す。我々のアルゴリズム的アプローチは反復的な洗練戦略を採用しており、より正確な近似を$\hat \mu$から$\mu$へと徐々に学習する。これは、異常なノイズのあるサンプルをフィルタリングする試みとして、$\hat \mu$から著しく逸脱した点を除去する、新しい拒絶サンプリング手順によって達成される。複雑化は、リジェクションサンプリングが残りの点の分布にバイアスをもたらすことである。この問題に対処するために、我々はバイアスを慎重に分析し、反復的な次元還元戦略を開発し、1次元結果を活用するリスト復号学習にインスパイアされた新しいサブルーチンを用いる。

関連論文リスト

Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文参考訳（メタデータ） (2024-08-21T01:39:42Z)
Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文参考訳（メタデータ） (2024-06-10T17:48:36Z)
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文参考訳（メタデータ） (2024-03-15T15:51:27Z)
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)
Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。また、Acharyaなどのアルゴリズムの改良版も提供します。
論文参考訳（メタデータ） (2023-06-20T06:13:56Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文参考訳（メタデータ） (2022-05-28T05:13:45Z)
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)
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文参考訳（メタデータ） (2020-06-24T06:01:24Z)
List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文参考訳（メタデータ） (2020-06-18T17:47:37Z)

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

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