Robust estimation via generalized quasi-gradients
Robust estimation via generalized quasi-gradients
复制标题
DOI：
10.1093/imaiai/iaab018
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Banghua Zhu;Jiantao Jiao;J. Steinhardt
中科院分区：
文献类型：
--
作者：
Banghua Zhu;Jiantao Jiao;J. Steinhardt
我们探讨了许多最近提出的强大估计问题是有效解决的，即使潜在的优化问题是非凸面，我们研究了这些稳健的估计问题的损失格局，并确定“一般性的准级别”的存在 - 存在较大的无重格算法的家族，可以保证近似于全球最低限度；这包括常用的过滤算法。优化问题是当校正级别$ \ epsilon <1/3 $时，任何近似的全球最小值。步骤大小，我们将其提高到$ 1/2 $，这对于其他任务是最佳的，包括线性回归和均值和协方差估计，损失格局更加坚固：尽管如此，远离全球最小值，我们表明存在广义的准级别，并构建有效的算法。 $ o（\ epsilon）的小$ \ epsilon $假设经过认证的超额收缩率。 }（d/\ epsilon ^2）$。
We explore why many recently proposed robust estimation problems are efficiently solvable, even though the underlying optimization problems are non-convex. We study the loss landscape of these robust estimation problems, and identify the existence of ’generalized quasi-gradients’. Whenever these quasi-gradients exist, a large family of no-regret algorithms are guaranteed to approximate the global minimum; this includes the commonly used filtering algorithm. For robust mean estimation of distributions under bounded covariance, we show that any first-order stationary point of the associated optimization problem is an approximate global minimum if and only if the corruption level $\epsilon < 1/3$. Consequently, any optimization algorithm that approaches a stationary point yields an efficient robust estimator with breakdown point $1/3$. With carefully designed initialization and step size, we improve this to $1/2$, which is optimal. For other tasks, including linear regression and joint mean and covariance estimation, the loss landscape is more rugged: there are stationary points arbitrarily far from the global minimum. Nevertheless, we show that generalized quasi-gradients exist and construct efficient algorithms. These algorithms are simpler than previous ones in the literature, and for linear regression we improve the estimation error from $O(\sqrt{\epsilon })$ to the optimal rate of $O(\epsilon )$ for small $\epsilon $ assuming certified hypercontractivity. For mean estimation with near-identity covariance, we show that a simple gradient descent algorithm achieves breakdown point $1/3$ and iteration complexity $\tilde{O}(d/\epsilon ^2)$.