Consistent regression when oblivious outliers overwhelm
  We consider a robust linear regression model $y=X\beta^* + \eta$, where an
adversary oblivious to the design $X\in \mathbb{R}^{n\times d}$ may choose
$\eta$ to corrupt all but an $\alpha$ 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 \gtrsim (d/\alpha)^2$ or for logarithmic inlier fraction $\alpha\ge
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.'14], 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 optimal guarantees in nearly-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.
