论文标题
通过VC维度的强大次高斯估计
Robust subgaussian estimation with VC-dimension
论文作者
论文摘要
基于均值（MOM）的程序中值程序即使数据是重尾和/或损坏的，也可以提供非反应和较强的偏差界限。这项工作提出了一种新的一般方法，以限制妈妈估计器的多余风险。核心技术是使用VC维数（而不是Rademacher复杂性）来测量统计复杂性。特别是，这允许为稀疏估计提供第一个可靠的估计器，该估计估计达到所谓的Subgaussian速率，仅假设未腐败的数据有有限的第二刻。相比之下，以前使用Rademacher复杂性的工作需要许多有限的力矩，使对数随尺寸增长。通过这种技术，我们得出了新的鲁棒sugaussian界限，以在任何规范中进行平均估计。我们还为协方差估计得出了一个新的可靠估计器，该估计是第一个在没有$ l_4-l_2 $ norm quart等价的情况下实现Subgaussian界限的估计值。
Median-of-means (MOM) based procedures provide non-asymptotic and strong deviation bounds even when data are heavy-tailed and/or corrupted. This work proposes a new general way to bound the excess risk for MOM estimators. The core technique is the use of VC-dimension (instead of Rademacher complexity) to measure the statistical complexity. In particular, this allows to give the first robust estimators for sparse estimation which achieves the so-called subgaussian rate only assuming a finite second moment for the uncorrupted data. By comparison, previous works using Rademacher complexities required a number of finite moments that grows logarithmically with the dimension. With this technique, we derive new robust sugaussian bounds for mean estimation in any norm. We also derive a new robust estimator for covariance estimation that is the first to achieve subgaussian bounds without $L_4-L_2$ norm equivalence.
