Online Learning of Halfspaces with Massart Noise

We study the task of online learning in the presence of Massart noise. Instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context x is selected adversarially but the label y presented to the learner disagrees with the ground-truth label of x with unknown probability at most η. We study the fundamental class of γ-margin linear classifiers and present a computationally efficient algorithm that achieves mistake bound η T + o(T). Our mistake bound is qualitatively tight for efficient algorithms: it is known that even in the offline setting achieving classification error better than η requires super-polynomial time in the SQ model. We extend our online learning model to a k-arm contextual bandit setting where the rewards -- instead of satisfying commonly used realizability assumptions -- are consistent (in expectation) with some linear ranking function with weight vector w^ast. Given a list of contexts x1,ldots xk, if w^*· xi > w^* · xj, the expected reward of action i must be larger than that of j by at least Delta. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least (1-1/k)~ Delta T - o(T) bigger than choosing a random action at every round.