Name
Abstract | ||
|---|---|---|
We consider a robust linear regression model y = X beta + eta, where an adversary oblivious to the design X epsilon R-nxd may choose eta to corrupt all but an ff fraction of the observations y in an arbitrary way. Prior to our work, even for Gaussian X, no estimator for beta was known to be consistent in this model except for quadratic sample size n greater than or similar to (d/alpha)(2) or for logarithmic inlier fraction alpha >= 1/log n. We show that consistent estimation is possible with nearly linear sample size and inverse-polynomial inlier fraction. Concretely, we show that the Huber loss estimator is consistent for every sample size n = omega(d/alpha(2)) and achieves an error rate of O(d/alpha 2n)(1/2) (both bounds are optimal up to constant factors). Our results extend to designs far beyond the Gaussian case and only require the column span of X to not contain approximately sparse vectors (similar to the kind of assumption commonly made about the kernel space for compressed sensing). We provide two technically similar proofs. One proof is phrased in terms of strong convexity, extending work of (Tsakonas et al., 2014), and particularly short. The other proof highlights a connection between the Huber loss estimator and high-dimensional median computations. In the special case of Gaussian designs, this connection leads us to a strikingly simple algorithm based on computing coordinate-wise medians that achieves nearly optimal guarantees in linear time, and that can exploit sparsity of beta. The model studied here also captures heavy-tailed noise distributions that may not even have a first moment. |
Year | Venue | DocType |
|---|---|---|
2021 | INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139 | Conference |
Volume | ISSN | Citations |
139 | 2640-3498 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tommaso d'Orsi | 1 | 0 | 0.34 |
| Gleb Novikov | 2 | 1 | 0.72 |
| David Steurer | 3 | 934 | 44.91 |