  We study random design linear regression with no assumptions on the
distribution of the covariates and with a heavy-tailed response variable. When
learning without assumptions on the covariates, we establish boundedness of the
conditional second moment of the response variable as a necessary and
sufficient condition for achieving deviation-optimal excess risk rate of
convergence. In particular, combining the ideas of truncated least squares,
median-of-means procedures and aggregation theory, we construct a non-linear
estimator achieving excess risk of order $d/n$ with the optimal sub-exponential
tail. While the existing approaches to learning linear classes under
heavy-tailed distributions focus on proper estimators, we highlight that the
improperness of our estimator is necessary for attaining non-trivial guarantees
in the distribution-free setting considered in this work. Finally, as a
byproduct of our analysis, we prove an optimal version of the classical bound
for the truncated least squares estimator due to Gy\"{o}rfi, Kohler, Krzyzak,
and Walk.
