多项式时间下的亚高斯速率均值估计

Sep, 2018

多项式时间下的亚高斯速率均值估计

Mean Estimation with Sub-Gaussian Rates in Polynomial Time

Samuel B. Hopkins

TL;DR本论文利用半定规划松弛和高维中位数，首次提出了一种多项式时间算法，能在有限均值和协方差的假设下估计具有重尾分布的多维随机向量的均值，并实现亚高斯置信区间。

Abstract

We study polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector. We assume only that the random vector $X$ has finite mean and covariance. In this setting, the radius of confidence intervals achieved by the empirical mean are large compared to t

polynomial time algorithms heavy-tailed multivariate random vector sub-gaussian confidence intervals semidefinite programming relaxation high-dimensional median

发现论文，激发创造

亚高斯速率下的快速均值估计

提出了一种估计随机向量均值的估计器，时间复杂度为 $O (n^4+n^2d)$，其误差界限符合亚高斯分布。与 Hopkins（2018）介绍的基于二次项和谐级数的多项式时间估计器一样，在具有有限均值和协方差的数据分布方面，效率最高，但运行时间更快，分析更简单。

Feb, 2019

具有亚高斯速率的均值估计的快速谱算法

研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题，提供了一种基于谱方法的算法来解决该问题，并且只需要计算近似特征向量，取得了最优的统计性能和更快的运行速度。

Aug, 2019

随机向量均值的次高斯估计器

本研究介绍了一种基于多元中位数的新估计方法，能在随机向量的二阶矩存在的条件下达到纯亚高斯性能。

Feb, 2017

亚高斯均值估计器

本文从非渐近的角度探讨了从非正态分布中的独立同分布观测中估计实值随机变量均值的可能性和局限性，提出了一些呈现次高斯分布特征的估计器，并证明了几个均值估计器的不可能性结果。

Sep, 2015

重尾统计算法：回归、协方差估计和更多

研究怎样在不假设样本的基础分布为高斯分布的前提下，只假定有限个矩的情况下，有效地进行线性回归和协方差估计，并关注能用多少样本来实现高精度和指数级成功概率。使用八阶圆当量半定规划提供算法，预备性的证据表明在我们的算法使用的平均中位数框架中无法在多项式时间内改善这些误差率。

Dec, 2019

近线性时间高维鲁棒均值估计

本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究，提出了一种基于当前猜测值参数化的 SDP 族的自然算法，并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解，同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。

Nov, 2018

无需方差的最优均值估计

研究了在数据生成分布的方差不存在的情况下对重尾均值估计问题的解决方案，提出了一种具备计算效率的估计器，并通过信息理论建立了最优可达置信区间的信息理论下界。

Nov, 2020

鲁棒均值估计有多难？

该论文阐述了在自然情况下改善多项式算法稳健均值估计误差率在计算上可能是不可行的，并探索了改善现有算法的错误率的自然方法，并证明了这将意味着小集合扩展问题的有效算法。

Mar, 2019

高斯均值全方位健壮估计器

本文研究了一个基于迭代重新加权的估计方法，该方法针对多元高斯分布的均值具有鲁棒性，且具有多个优秀性质，包括计算上的可行性、对平移、伸缩和正交变换的不变性、高断点以及渐近有效性。此外，本文还为提出的估计器建立了无维度的非渐近风险界限，并将结果推广到了子高斯分布和污染率未知、协方差矩阵未知等情形。

Feb, 2020

近线性时间鲁棒次高斯均值向量估计

本文介绍了一种基于 Median-of-Means 方法和 Semi-definite Programming 的算法，使用时并不需要先验知识，能够高效处理大数据，包含异常值和重尾数据等，稳定性强，能达到次高斯速率

Jun, 2019