Consistent Robust Regression
We present the first efficient and provably consistent estimator for the robust regression problem. The area of robust learning and optimization has generated a significant amount of interest in the learning and statistics communities in recent years owing to its applicability in scenarios with corrupted data, as well as in handling model mis-specifications. In particular, special interest has been devoted to the fundamental problem of robust linear regression where estimators that can tolerate corruption in up to a constant fraction of the response variables are widely studied. Surprisingly however, to this date, we are not aware of a polynomial time estimator that offers a consistent estimate in the presence of dense, unbounded corruptions. In this work we present such an estimator, called CRR. This solves an open problem put forward in the work of [3]. Our consistency analysis requires a novel two-stage proof technique involving a careful analysis of the stability of ordered lists which may be of independent interest. We show that CRR not only offers consistent estimates, but is empirically far superior to several other recently proposed algorithms for the robust regression problem, including extended Lasso and the TORRENT algorithm. In comparison, CRR offers comparable or better model recovery but with runtimes that are faster by an order of magnitude.
Summary. This submission studies robust linear regression under the settings where there are additive white observation noises, and where \alpha=\Omega(1) fraction of the responses are corrupted by an oblivious adversary. For this problem, it proposes a consistent estimator, called CRR, which is computationally easy because it is based on iterative hard thresholding. It is shown to be consistent (i.e., converging to the true solution in the limit of the number of responses tending to infinity) under certain conditions (Theorem 4).
Quality. In Theorem 4, I did not understand how \epsilon is defined, and consequently, the statement of the theorem itself. Is it defined on the basis of the problem or algorithm setting? Or does the statement of the theorem hold "for any" \epsilon>0, or does "there exist" \epsilon for which the statement hold? The same also applies to \epsilon and e_0 in Lemma 5.
In Figure 1, the results with d=500, n=2000, \sigma=2, and k=600 appear in the subfigures (a), (b), and (c), but those in the subfigure (a) seem different from those in (b) and (c), which might question the validity of the results presented here.
Clarity. I think that this submission is basically clearly written.
Originality. Although I have not done an extensive survey in the literature, proposing a computationally efficient algorithm, with consistency guarantee in the limit of the number n of responses tending to infinity, for the robust linear regression problem with Gaussian noise as well as with oblivious adversary, when the fraction \alpha of adversarial corruptions is \Omega(1).
Significance. Even though the fraction \alpha of adversarial corruptions for which CRR is shown to be consistent is quite small (\alpha \le 1/20000), it is still nontrivial to give a consistency guarantee even if a finite fraction of responses are corrupted. It would stimulate further studies regarding finer theoretical analysis as well as algorithmic development.
Minor points:
Line 64: incl(u)ding more expensive methods
Line 76: Among those cite(d)
Line 82 and yet guarantee(s) recovery.
Line 83: while allowing (allow)
Lines 61, 102, and 115: The notation E[...]_2 would require explicit definition.
Equation (5): The equation should be terminated by a period rather than a comma.
Line 164: (more fine -> finer) analysis
Line 173: the (Subset) Strong Smoothness Property
Line 246: consequently ensure(s)
Lines 254-264: I guess that all the norms appearing in this part should be the 2-norm, but on some occasions the subscript 2 is missing.
Lines 285-286: Explicitly mention that the Torrent-FC algorithm was used for comparison. Simply writing "the Torrent algorithm" might be ambiguous, and also in the figures the authors mentioned it as "TORRENT-FC".
Line 293: faster runtimes tha(n) Torrent
Line 295: both Torrent (and) ex-Lasso become(s) intractable with a(n) order
Line 296: Figure(s) 2 (c) and 2(d) show(s)
Line 303: Figure 2 (a -> b) shows
Line 310: we found CRR to (to) be