论文标题
稳健回归的光谱算法，并具有次高斯的速率
A spectral algorithm for robust regression with subgaussian rates
论文作者
论文摘要
我们研究了新的线性至二次时间算法，用于线性回归，如果没有对样品的基本分布和存在异常值的强烈假设。目的是设计一个实际工作代码附带的过程，即使数据只有有限的矩（最高$ l_4 $），并且在可能存在对抗性异常值的情况下，即使数据只有有限的矩（最高$ l_4 $），该过程即使达到最佳的次高斯错误。最近已经发现了一个多项式时间解决方案，但由于使用了平方层次结构编程，因此运行时间很高。我们算法的核心是对线性回归问题的平均估计问题引入的光谱方法的适应。作为副产品，我们建立了线性回归问题与最远的超平面问题之间的联系。从随机的角度来看，除了研究经典二次和乘数过程外，我们还引入了第三个经验过程，该过程自然而然地研究了算法的统计特性。
We study a new linear up to quadratic time algorithm for linear regression in the absence of strong assumptions on the underlying distributions of samples, and in the presence of outliers. The goal is to design a procedure which comes with actual working code that attains the optimal sub-gaussian error bound even though the data have only finite moments (up to $L_4$) and in the presence of possibly adversarial outliers. A polynomial-time solution to this problem has been recently discovered but has high runtime due to its use of Sum-of-Square hierarchy programming. At the core of our algorithm is an adaptation of the spectral method introduced for the mean estimation problem to the linear regression problem. As a by-product we established a connection between the linear regression problem and the furthest hyperplane problem. From a stochastic point of view, in addition to the study of the classical quadratic and multiplier processes we introduce a third empirical process that comes naturally in the study of the statistical properties of the algorithm.
