论文标题
通过SGD在线稳健回归的L1损失
Online Robust Regression via SGD on the l1 loss
论文作者
论文摘要
我们考虑在线环境中的鲁棒线性回归问题，在线环境中我们可以以流方式访问数据，一个数据点又一个数据点。更具体地说，对于真正的参数$θ^* $，我们考虑损坏的高斯线性模型$ y = \ langle x，\θ^* \ rangle + \ varepsilon + v varepsilon + b $，其中对抗性噪声$ b $可以将任何值带有概率$η$，否则等于零。我们认为这个对手是遗忘的（即，独立于数据的$ b $），因为这是唯一可能的污染模型。当前的算法依赖于手头上的整个数据来识别和删除异常值。相比之下，我们在这项工作中表明，在$ \ ell_1 $损失上的随机梯度下降在$ \ tilde {o}（1 /（1-η）^2 n）$速率上收敛到真实参数向量，这与受污染的测量值无关。我们的证明依赖于高斯数据对非平滑$ \ ell_1 $损失的优雅平滑，以及对Polyak-Rupppert平均SGD的经典非反应分析。此外，我们还提供了这种简单且高度可扩展算法的效率的实验证据。
We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner, one data point after the other. More specifically, for a true parameter $θ^*$, we consider the corrupted Gaussian linear model $y = \langle x , \ θ^* \rangle + \varepsilon + b$ where the adversarial noise $b$ can take any value with probability $η$ and equals zero otherwise. We consider this adversary to be oblivious (i.e., $b$ independent of the data) since this is the only contamination model under which consistency is possible. Current algorithms rely on having the whole data at hand in order to identify and remove the outliers. In contrast, we show in this work that stochastic gradient descent on the $\ell_1$ loss converges to the true parameter vector at a $\tilde{O}( 1 / (1 - η)^2 n )$ rate which is independent of the values of the contaminated measurements. Our proof relies on the elegant smoothing of the non-smooth $\ell_1$ loss by the Gaussian data and a classical non-asymptotic analysis of Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of the efficiency of this simple and highly scalable algorithm.
