BriefGPT.xyz
Nov, 2018
近线性时间高维鲁棒均值估计
High-Dimensional Robust Mean Estimation in Nearly-Linear Time
HTML
PDF
Yu Cheng, Ilias Diakonikolas, Rong Ge
TL;DR
本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究,提出了一种基于当前猜测值参数化的SDP族的自然算法,并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解,同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。
Abstract
We study the fundamental problem of
high-dimensional mean estimation
in a
robust model
where a constant fraction of the samples are adversarially corrupted. Recent work gave the first
→