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* center dot x). In particular, y = g(w* center dot x) + xi + epsilon where. is the oblivious noise drawn independently of x, satisfying Pr[xi = 0] =>= o(1), and epsilon similar to N(0, sigma(2)). Our goal is to accurately recover a function g(w center dot x) with arbitrarily small error when compared to the true values g(w* center dot x), rather than the noisy measurements y. We present an algorithm that tackles the problem in its most general distribution-independent setting, where the solution may not be identifiable. The algorithm is designed to return the solution if it is identifiable, and otherwise return a small list of candidates, one of which is close to the true solution. Furthermore, we characterize a necessary and sufficient condition for identifiability, which holds in broad settings. 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* center dot x) + A for some real number A, while also having large error when compared to g(w* center dot x). This is the first result for GLM regression which can handle more than half the samples being arbitrarily corrupted. Prior work focused largely on the setting of linear regression with oblivious noise, and giving algorithms under more restrictive assumptions.