Optimal Mean Estimation without a Variance
Optimal Mean Estimation without a Variance
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Yeshwanth Cherapanamjeri;Nilesh Tripuraneni;P. Bartlett;Michael I. Jordan
中科院分区：
文献类型：
--
作者：
Yeshwanth Cherapanamjeri;Nilesh Tripuraneni;P. Bartlett;Michael I. Jordan
在数据生成分布的方差不存在的情况下，我们研究了重尾均值估计问题。具体地说，给定一个样本$\mathbf{X}=\{X_i\}_{i=1}^n$，该样本来自$\mathbb{R}^d$上的分布$\mathbb{R}^d$，它满足以下弱时刻假设：对于某个${a\in[0，1]}$：\Begin{公式*}\for all v=1：\mathbb{E}_{X\thicksim\mathcal{D}}[\lvert\langX-\u，在给定目标失效概率的情况下，我们的目标是设计一个估计器，使其获得作为$n，d，\Delta$的函数的最小可能的置信度区间。对于$\α=1$的特殊情形，Lugosi和Mendelson的基础工作展示了一个达到次高斯可信区间的估计量，随后的工作导致了该估计量的计算有效版本。在这里，我们研究了一般的$\α$的情形，并在最优可达置信度区间上建立了如下信息论下界：\Begin{等式*}\Omega\Left(\Sqrt{\frac{d}{n}}+\Left(\frac{d}{n}\right)^{\frac{\pha}{(1+\α)}+\Left(\frac{\log1/\Delta}{n}\right)^{\frac{\α}{(1+\α)}}\Right)。此外，我们还设计了一个计算有效的估计器，它达到了这个下界。
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.