論文の概要: Optimal Mean Estimation without a Variance
- arxiv url: http://arxiv.org/abs/2011.12433v2
- Date: Tue, 8 Dec 2020 20:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 13:02:15.751848
- Title: Optimal Mean Estimation without a Variance
- Title(参考訳): 分散のない最適平均推定法
- Authors: Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter L. Bartlett,
Michael I. Jordan
- Abstract要約: 本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
- 参考スコア(独自算出の注目度): 103.26777953032537
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of heavy-tailed mean estimation in settings where the
variance of the data-generating distribution does not exist. Concretely, given
a sample $\mathbf{X} = \{X_i\}_{i = 1}^n$ from a distribution $\mathcal{D}$
over $\mathbb{R}^d$ with mean $\mu$ which satisfies the following
\emph{weak-moment} assumption for some ${\alpha \in [0, 1]}$: \begin{equation*}
\forall \|v\| = 1: \mathbb{E}_{X \thicksim \mathcal{D}}[\lvert \langle X - \mu,
v\rangle \rvert^{1 + \alpha}] \leq 1, \end{equation*} and given a target
failure probability, $\delta$, our goal is to design an estimator which attains
the smallest possible confidence interval as a function of $n,d,\delta$. For
the specific case of $\alpha = 1$, foundational work of Lugosi and Mendelson
exhibits an estimator achieving subgaussian confidence intervals, and
subsequent work has led to computationally efficient versions of this
estimator. Here, we study the case of general $\alpha$, and establish the
following information-theoretic lower bound on the optimal attainable
confidence interval: \begin{equation*} \Omega \left(\sqrt{\frac{d}{n}} +
\left(\frac{d}{n}\right)^{\frac{\alpha}{(1 + \alpha)}} + \left(\frac{\log 1 /
\delta}{n}\right)^{\frac{\alpha}{(1 + \alpha)}}\right). \end{equation*}
Moreover, we devise a computationally-efficient estimator which achieves this
lower bound.
- Abstract(参考訳): 本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
Concretely, given a sample $\mathbf{X} = \{X_i\}_{i = 1}^n$ from a distribution $\mathcal{D}$ over $\mathbb{R}^d$ with mean $\mu$ which satisfies the following \emph{weak-moment} assumption for some ${\alpha \in [0, 1]}$: \begin{equation*} \forall \|v\| = 1: \mathbb{E}_{X \thicksim \mathcal{D}}[\lvert \langle X - \mu, v\rangle \rvert^{1 + \alpha}] \leq 1, \end{equation*} and given a target failure probability, $\delta$, our goal is to design an estimator which attains the smallest possible confidence interval as a function of $n,d,\delta$.
特定の場合の$\alpha = 1$の場合、lugosi と mendelson の基礎的な研究は、サブガウシアン信頼区間を達成する推定子を示し、その後の研究はこの推定子の計算効率の高いバージョンへと導かれる。
ここで、一般の$\alpha$の場合を研究し、最適な到達可能な信頼区間について次の情報理論下限を確立する: \begin{equation*} \omega \left(\sqrt{\frac{d}{n}} + \left(\frac{d}{n}\right)^{\frac{\alpha}{(1 + \alpha)}} + \left(\frac{\log 1 / \delta}{n}\right)^{\frac{\alpha}{(1 + \alpha)}}\right)。
さらに、この下限を達成する計算効率の高い推定器を考案する。
関連論文リスト
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2024-11-11T03:43:52Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳(メタデータ) (2024-06-07T08:26:31Z) - Estimating the Mixing Coefficients of Geometrically Ergodic Markov
Processes [5.00389879175348]
実数値の幾何学的エルゴード的マルコフ過程の個々の$beta$-mixing係数を1つのサンプルパスから推定する。
予想される誤差率は$mathcal O(log(n) n-1/2)$である。
論文 参考訳(メタデータ) (2024-02-11T20:17:10Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳(メタデータ) (2023-09-29T14:14:53Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Convergence Rates of Stochastic Zeroth-order Gradient Descent for \L
ojasiewicz Functions [6.137707924685666]
Lojasiewicz関数に対するゼロ階勾配 Descent (SZGD) アルゴリズムの収束率を証明する。
その結果, mathbbN $ における f (mathbfx_t) - f (mathbfx_infty) _t は $ | mathbfx_infty よりも早く収束できることがわかった。
論文 参考訳(メタデータ) (2022-10-31T00:53:17Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
我々は、ほとんどの方向において$bfu$と$nu=mathrmpoly(k)$に対して、$n=mathrmpoly(k)$測定を用いて、高い精度で$bfu$を推定するアルゴリズムを開発し、分析する。
数値実験により,非漸近的条件下でも良好な性能が得られた。
論文 参考訳(メタデータ) (2021-10-04T02:10:47Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳(メタデータ) (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。