Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments
Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments
复制标题
均值估计中的最优性：超越最坏情况、超越亚高斯和超越 1+α 矩
DOI：
10.48550/arxiv.2311.12784
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Paul Valiant
中科院分区：
文献类型：
--
作者：
Trung Dang;Jasper C. H. Lee;Maoyuan Song;Paul Valiant
在改善我们对基本统计问题（例如平均估计）的算法理解的兴趣越来越大，这是基于了解我们可以从宝贵数据中提取的限制的目标所驱动的。在$ \ mathbb {r} $中平均估计的最新结果是1）[lv22]的最佳次高斯均值估计器，所有具有有限但未知差异的分布的紧密次高仪常数，2 ）[bcl13]和[dllo16]的下部限制对中间算法的分析，表征了Big-O最佳错误的发行版，仅$ 1+\ alpha $时刻存在于$ \ alpha \ in （0,1）$。但是，这两个结果仅在最坏的情况下都是最佳的。我们启动了平均估计问题的细粒度研究：算法是否可以利用输入分布的有用特征来击败高斯率，而没有明确了解此类特征？我们以一个出乎意料的细微差别解决这个问题：“是的，在有限的政权中，但总的来说是不是”。对于任何具有有限均值的分销$ p $，我们构建了一个分配$ Q $，其平均值与$ p $ s分别为$ p $，但是$ p $和$ q $却没有高概率和$ q $的区别进一步保留了$ p $的瞬间。最主要的结果是，对于任何分布，没有合理的估计器可以渐近地获得比高斯以下错误率更好，这与[LV22]的最坏情况相匹配。更普遍地，我们引入了一个新的定义框架，以分析算法的细颗粒最佳性，我们称之为“邻里最佳性”，在无与伦比的强大“实例最优性”与琐碎的“可理性”定义之间进行了插值。应用新框架，我们表明均值是邻里最佳的，直到不变的因素。开放的是找到一个邻居最佳估计器，而没有恒定的因素松弛度。
There is growing interest in improving our algorithmic understanding of fundamental statistical problems such as mean estimation, driven by the goal of understanding the limits of what we can extract from valuable data. The state of the art results for mean estimation in $\mathbb{R}$ are 1) the optimal sub-Gaussian mean estimator by [LV22], with the tight sub-Gaussian constant for all distributions with finite but unknown variance, and 2) the analysis of the median-of-means algorithm by [BCL13] and a lower bound by [DLLO16], characterizing the big-O optimal errors for distributions for which only a $1+\alpha$ moment exists for $\alpha \in (0,1)$. Both results, however, are optimal only in the worst case. We initiate the fine-grained study of the mean estimation problem: Can algorithms leverage useful features of the input distribution to beat the sub-Gaussian rate, without explicit knowledge of such features? We resolve this question with an unexpectedly nuanced answer:"Yes in limited regimes, but in general no". For any distribution $p$ with a finite mean, we construct a distribution $q$ whose mean is well-separated from $p$'s, yet $p$ and $q$ are not distinguishable with high probability, and $q$ further preserves $p$'s moments up to constants. The main consequence is that no reasonable estimator can asymptotically achieve better than the sub-Gaussian error rate for any distribution, matching the worst-case result of [LV22]. More generally, we introduce a new definitional framework to analyze the fine-grained optimality of algorithms, which we call"neighborhood optimality", interpolating between the unattainably strong"instance optimality"and the trivially weak"admissibility"definitions. Applying the new framework, we show that median-of-means is neighborhood optimal, up to constant factors. It is open to find a neighborhood-optimal estimator without constant factor slackness.
通过近似逆敏感性机制实现差分隐私中的实例最优性
DOI：
--
发表时间：
2020
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Asi, Hilal;Duchi, John
通讯作者：
Duchi, John
采用 Fisher 信息率的有限样本对称均值估计
DOI：
--
发表时间：
2023
期刊：
Conference on Learning Theory
影响因子：
--
作者：
Gupta, S;Lee, J;Price, E
通讯作者：
Price, E