论文标题
通过梯度下降的高维鲁棒平均估计
High-Dimensional Robust Mean Estimation via Gradient Descent
论文作者
论文摘要
我们研究了存在恒定比例的对抗异常值的高维鲁棒平均估计的问题。最近的一项工作为此问题提供了复杂的多项式时间算法，并为一系列自然分布家族提供了无关的错误保证。 在这项工作中，我们表明，该问题的天然非凸公式可以通过梯度下降直接解决。我们的方法利用了一种新型的结构引理，粗略地表明，我们的非凸目标的任何近似固定点为基础可靠的估计任务提供了近乎最佳的解决方案。我们的工作建立了算法高维鲁棒统计数据与非凸优化之间的有趣联系，这可能在其他健壮的估计任务中具有更广泛的应用。
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.
