論文の概要: Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances

• arxiv url: http://arxiv.org/abs/2312.02417v1
• Date: Tue, 5 Dec 2023 01:13:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-06 17:15:56.001975
• Title: Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
• Title（参考訳）: ヘテロスケダス性変種による近距離平均推定
• Authors: Spencer Compton, Gregory Valiant
• Abstract要約: Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。 我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。 たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
• 参考スコア（独自算出の注目度）: 15.990720051907864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given data drawn from a collection of Gaussian variables with a common mean but different and unknown variances, what is the best algorithm for estimating their common mean? We present an intuitive and efficient algorithm for this task. As different closed-form guarantees can be hard to compare, the Subset-of-Signals model serves as a benchmark for heteroskedastic mean estimation: given $n$ Gaussian variables with an unknown subset of $m$ variables having variance bounded by 1, what is the optimal estimation error as a function of $n$ and $m$? Our algorithm resolves this open question up to logarithmic factors, improving upon the previous best known estimation error by polynomial factors when $m = n^c$ for all $0<c<1$. Of particular note, we obtain error $o(1)$ with $m = \tilde{O}(n^{1/4})$ variance-bounded samples, whereas previous work required $m = \tilde{\Omega}(n^{1/2})$. Finally, we show that in the multi-dimensional setting, even for $d=2$, our techniques enable rates comparable to knowing the variance of each sample.
• Abstract（参考訳）: 共通平均を持つガウス変数の集合から引き出されたデータについて、その共通平均を推定するのに最適なアルゴリズムは何か。 我々はこの課題に対して直感的かつ効率的なアルゴリズムを提案する。 異なるクローズドフォーム保証を比較するのが難しいため、Subset-of-Signalsモデルはヘテロスケダスティック平均推定のベンチマークとして機能する:$n$ Gaussian変数の未知のサブセットを持つ$m$変数が1で制限されている場合、$n$と$m$の関数として最適な推定誤差は何か? 我々のアルゴリズムは、このオープンな問題を対数的因子まで解決し、すべての$0<c<1$に対して$m = n^c$となるときの多項式因子による既知推定誤差を改善する。 特に、エラー$o(1)$ with $m = \tilde{O}(n^{1/4})$ variance-bounded sample を得るのに対して、以前の作業では $m = \tilde{\Omega}(n^{1/2})$ が必要であった。 最後に、d=2$の多次元設定において、我々の手法は各サンプルの分散を知るのに匹敵する速度を実現できることを示す。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• 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)
• A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
  我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。 推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
  論文  参考訳（メタデータ） (2023-01-17T18:44:41Z)
• 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)
• CountSketches, Feature Hashing and the Median of Three [18.85876632959721]
  古典的なCountSketch法は、(高次元)ユークリッドベクトル $v$ を次元 $(2t-1) s$ に変換するスパースでランダムな射影である。 我々の主な貢献は、Count-Sketchの新しい分析であり、$t > 1$ のとき、$O(min|v|2/s2,|v|2/s2)$ への分散の改善を示す。 この結果は、基本的にCountSketchと同一であるが中央値を使用しないFeature Hashing法が可能であることを示唆している。
  論文  参考訳（メタデータ） (2021-02-03T18:45:21Z)
• 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 Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  ガウス下収束を考慮した新しい推定器を提案する。 我々の推定器はその分散に関する事前の知識を必要としない。 我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2020-11-17T02:47:24Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)
• 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)

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

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