ROBUST SUB-GAUSSIAN ESTIMATION OF A MEAN VECTOR IN NEARLY LINEAR TIME

• 成果类型: Article
• 署名作者: Depersin, Jules; Lecue, Guillaume
• 署名单位: Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/21-AOS2118
• 发表日期: 2022
• 页码: 511-536
• 关键词: Adaptive Estimation; high-dimensions; matrix; rates

摘要

We construct an algorithm for estimating the mean of a heavy-tailed random variable when given an adversarial corrupted sample of N independent observations. The only assumption we make on the distribution of the non-corrupted (or informative) data is the existence of a covariance matrix Sigma, unknown to the statistician. Our algorithm outputs (mu) over cap, which is robust to the presence of vertical bar O vertical bar adversarial outliers and satisfies parallel to(mu) over cap - mu parallel to(2) less than or similar to root Tr(Sigma)/N + root parallel to Sigma parallel to K-op/N with probability at least 1 - exp(-c(0)K) - exp(-c(1)u), and runtime (O) over tilde (Nd uKd) where K is an element of {600 vertical bar O vertical bar, ..., N} and u is an element of N* are two parameters of the algorithm. The algorithm is fully data-dependent and does not use (1) in its construction, which combines recently developed tools for median-of-means estimators and covering semidefinite programming We also show that this algorithm can automatically adapt to the number of outliers (adaptive choice of K) and that it satisfies the same bound in expectation.