Considering the ubiquity of linear thresholds in classification, the list of relevant references is far too long to include here; as such, we highlight only those most germane to our work. The perceptron algorithm was introduced in [1]} and a margin-based mistake bound was proved in [2]}. There have been many variations on and applications of this bound, from [3]} using it to bound the Littlestone dimension of linear thresholds with margin to dealing with non-realizable samples [4]}, [5]}. To the best of our knowledge our work constitutes the first to explore the effect that a smoothed adversary has on the perceptron algorithm.
