  We investigate robust linear regression where data may be contaminated by an
oblivious adversary, i.e., an adversary than may know the data distribution but
is otherwise oblivious to the realizations of the data samples. This model has
been previously analyzed under strong assumptions. Concretely, $\textbf{(i)}$
all previous works assume that the covariance matrix of the features is
positive definite; and $\textbf{(ii)}$ most of them assume that the features
are centered (i.e. zero mean). Additionally, all previous works make additional
restrictive assumption, e.g., assuming that the features are Gaussian or that
the corruptions are symmetrically distributed.
  In this work we go beyond these assumptions and investigate robust regression
under a more general set of assumptions: $\textbf{(i)}$ we allow the covariance
matrix to be either positive definite or positive semi definite,
$\textbf{(ii)}$ we do not necessarily assume that the features are centered,
$\textbf{(iii)}$ we make no further assumption beyond boundedness
(sub-Gaussianity) of features and measurement noise.
  Under these assumption we analyze a natural SGD variant for this problem and
show that it enjoys a fast convergence rate when the covariance matrix is
positive definite. In the positive semi definite case we show that there are
two regimes: if the features are centered we can obtain a standard convergence
rate; otherwise the adversary can cause any learner to fail arbitrarily.

Machine Learning