Distribution-independent Regression for Generalized Linear Models
with Oblivious Corruptions

Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park, Christos Tzamos

Abstract

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, y = g(w∗ · x) + ξ + ϵ where ξ is the oblivious noise drawn independently of x, satisfying Pr[ξ = 0] ≥ o(1), and ϵ ∼ N(0, σ2). Our goal is to accurately recover a function g(w · x) with arbitrarily small error when compared to the true values g(w∗ · 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 ξ + ϵ = 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 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.
COLT 2023