High-Dimensional Robust Mean Estimation via Gradient Descent
High-Dimensional Robust Mean Estimation via Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Yu Cheng;Ilias Diakonikolas;Rong Ge;M. Soltanolkotabi
中科院分区：
文献类型：
--
作者：
Yu Cheng;Ilias Diakonikolas;Rong Ge;M. Soltanolkotabi
我们研究了高维鲁棒均值估计的问题，在存在一个常数分数的敌对离群值。最近的一系列工作提供了复杂的多项式时间算法，这个问题与尺寸无关的误差保证范围内的自然分布家庭。在这项工作中，我们表明，一个自然的非凸制定的问题可以直接解决梯度下降。我们的方法利用了一个新的结构引理，粗略地表明，我们的非凸目标的任何近似稳定点给出了一个接近最优的解决方案，以基本的鲁棒估计任务。我们的工作建立了一个有趣的算法高维鲁棒统计和非凸优化，这可能有更广泛的应用到其他鲁棒估计任务之间的联系。
We study the problem of high-dimensional robust mean estimation in the presence of a constant fraction of adversarial outliers. A recent line of work has provided sophisticated polynomial-time algorithms for this problem with dimension-independent error guarantees for a range of natural distribution families. In this work, we show that a natural non-convex formulation of the problem can be solved directly by gradient descent. Our approach leverages a novel structural lemma, roughly showing that any approximate stationary point of our non-convex objective gives a near-optimal solution to the underlying robust estimation task. Our work establishes an intriguing connection between algorithmic high-dimensional robust statistics and non-convex optimization, which may have broader applications to other robust estimation tasks.