Online and Distribution-Free Robustness: Regression and Contextual
  Bandits with Huber Contamination
  In this work we revisit two classic high-dimensional online learning
problems, namely linear regression and contextual bandits, from the perspective
of adversarial robustness. Existing works in algorithmic robust statistics make
strong distributional assumptions that ensure that the input data is evenly
spread out or comes from a nice generative model. Is it possible to achieve
strong robustness guarantees even without distributional assumptions
altogether, where the sequence of tasks we are asked to solve is adaptively and
adversarially chosen?
  We answer this question in the affirmative for both linear regression and
contextual bandits. In fact our algorithms succeed where conventional methods
fail. In particular we show strong lower bounds against Huber regression and
more generally any convex M-estimator. Our approach is based on a novel
alternating minimization scheme that interleaves ordinary least-squares with a
simple convex program that finds the optimal reweighting of the distribution
under a spectral constraint. Our results obtain essentially optimal dependence
on the contamination level $\eta$, reach the optimal breakdown point, and
naturally apply to infinite dimensional settings where the feature vectors are
represented implicitly via a kernel map.
