  We revisit heavy-tailed corrupted least-squares linear regression assuming to
have a corrupted $n$-sized label-feature sample of at most $\epsilon n$
arbitrary outliers. We wish to estimate a $p$-dimensional parameter $b^*$ given
such sample of a label-feature pair $(y,x)$ satisfying $y=\langle
x,b^*\rangle+\xi$ with heavy-tailed $(x,\xi)$. We only assume $x$ is $L^4-L^2$
hypercontractive with constant $L>0$ and has covariance matrix $\Sigma$ with
minimum eigenvalue $1/\mu^2>0$ and bounded condition number $\kappa>0$. The
noise $\xi$ can be arbitrarily dependent on $x$ and nonsymmetric as long as
$\xi x$ has finite covariance matrix $\Xi$. We propose a near-optimal
computationally tractable estimator, based on the power method, assuming no
knowledge on $(\Sigma,\Xi)$ nor the operator norm of $\Xi$. With probability at
least $1-\delta$, our proposed estimator attains the statistical rate
$\mu^2\Vert\Xi\Vert^{1/2}(\frac{p}{n}+\frac{\log(1/\delta)}{n}+\epsilon)^{1/2}$
and breakdown-point $\epsilon\lesssim\frac{1}{L^4\kappa^2}$, both optimal in
the $\ell_2$-norm, assuming the near-optimal minimum sample size
$L^4\kappa^2(p\log p + \log(1/\delta))\lesssim n$, up to a log factor. To the
best of our knowledge, this is the first computationally tractable algorithm
satisfying simultaneously all the mentioned properties. Our estimator is based
on a two-stage Multiplicative Weight Update algorithm. The first stage
estimates a descent direction $\hat v$ with respect to the (unknown)
pre-conditioned inner product $\langle\Sigma(\cdot),\cdot\rangle$. The second
stage estimate the descent direction $\Sigma\hat v$ with respect to the (known)
inner product $\langle\cdot,\cdot\rangle$, without knowing nor estimating
$\Sigma$.
