The Perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant

We give an adversary strategy that forces the Perceptron algorithm to make (N \Gamma k + 1)=2 mistakes when learning k-literal disjunctions over N variables. Experimentally we see that even for simple random data, the number of mistakes made by the Perceptron algorithm grows almost linearly with N , even if the number k of relevant variable remains a small constant. In contrast, Littlestone's algorithm Winnow makes at most O(k log N ) mistakes for the same problem. Both algorithms use linear threshold functions as their hypotheses. However, Winnow does multiplicative updates to its weight vector instead of the additive updates of the Perceptron algorithm. 1 Introduction This paper addresses the familiar problem of predicting with a linear threshold function. The instances are N - dimensional real vectors, and a threshold function is given by an N-dimensional real weight vector w and a real threshold `. The linear threshold function has the value 1 on an instance x if w \Delta x `, a..