Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions

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^* · x). In particular, newthe noisy labels are of the form y = g(w^* · x) + xi + ε, where xi is the oblivious noise drawn independently of x newand satisfies Pr[xi = 0] ≥ o(1), and ε ~ mathcal N(0, σ2). Our goal is to accurately recover a newparameter vector w such that the function g(w · x) newhas arbitrarily small error when compared to the true values g(w^* · x), rather than the noisy measurements y. We present an algorithm that tackles newthis problem in its most general distribution-independent setting, where the solution may not neweven be identifiable. newOur algorithm returns newan 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 newprovide a necessary and sufficient condition for identifiability, which holds in broad settings. newSpecifically, the problem is identifiable when the quantile at which xi + ε = 0 is known, or when the family of hypotheses does not contain candidates that are nearly equal to a translated g(w^* · x) + A for some real number A, while also having large error when compared to g(w^* · x). This is the first newalgorithmic result for GLM regression newwith 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.