  We demonstrate the first algorithms for the problem of regression for
generalized linear models (GLMs) in the presence of additive oblivious noise.
We assume we have sample access to examples $(x, y)$ where $y$ is a noisy
measurement of $g(w^* \cdot x)$. In particular, \new{the noisy labels are of
the form} $y = g(w^* \cdot x) + \xi + \epsilon$, where $\xi$ is the oblivious
noise drawn independently of $x$ \new{and satisfies} $\Pr[\xi = 0] \geq o(1)$,
and $\epsilon \sim \mathcal N(0, \sigma^2)$. Our goal is to accurately recover
a \new{parameter vector $w$ such that the} function $g(w \cdot x)$ \new{has}
arbitrarily small error when compared to the true values $g(w^* \cdot x)$,
rather than the noisy measurements $y$.
  We present an algorithm that tackles \new{this} problem in its most general
distribution-independent setting, where the solution may not \new{even} be
identifiable. \new{Our} algorithm returns \new{an accurate estimate of} the
solution if it is identifiable, and otherwise returns a small list of
candidates, one of which is close to the true solution. Furthermore, we
\new{provide} a necessary and sufficient condition for identifiability, which
holds in broad settings. \new{Specifically,} the problem is identifiable when
the quantile at which $\xi + \epsilon = 0$ is known, or when the family of
hypotheses does not contain candidates that are nearly equal to a translated
$g(w^* \cdot x) + A$ for some real number $A$, while also having large error
when compared to $g(w^* \cdot x)$.
  This is the first \new{algorithmic} result for GLM regression \new{with
oblivious noise} which can handle more than half the samples being arbitrarily
corrupted. Prior work focused largely on the setting of linear regression, and
gave algorithms under restrictive assumptions.
