Reviews: Consistent Robust Regression

Summary: The paper presents a provably consistent, polynomial-time algorithm (that they call consistent robust regression, or CRR) for linear regression with corrupted samples under the oblivious adversary model. The algorithm is a simple iterative hard thresholding (IHT) procedure, and the authors show that this algorithm exhibits linear convergence. The analysis is supported by some representative synthetic numerical results. Strengths: Quality: Somewhat surprisingly, this method appears to be the first consistent procedure for robust linear regression, i.e., the parameter estimation error vanishes as the number of samples tends to infinity. Other estimation procedures (such as LASSO-type methods) seem to only provide solutions with error comparable to the noise level, even in the large sample limit.