The perceptron algorithm versus winnow: linear versus logarithmic mistake bounds when few input variables are relevant

We give an adversary strategy that forces the Perception algorithm to make Ω(kN) mistakes in learning monotone disjunctions over N variables with at most k literals. In contrast, Littlestone's algorithm Winnow makes at most O(k log N) mistakes for the same problem. Both algorithms use thresholded linear functions as their hypotheses. However, Winnow does multiplicative updates to its weight vector instead of the additive updates of the Perceptron algorithm. In general, we call an algorithm additive if its weight vector is always a sum of a fixed initial weight vector and some linear combination of already seen instances. Thus, the Perceptron algorithm is an example of an additive algorithm. We show that an adversary can force any additive algorithm to make (N + k - 1)/2 mistakes in learning a monotone disjunction of at most k literals. Simple experiments show that for k ≪ N, Winnow clearly outperforms the Perceptron algorithm also on nonadversarial random data.