The Perceptron Algorithm vs. Winnow: Linear vs. Logarithmic Mistake Bounds when few Input Variables are Relevant.

Jyrki Kivinen, Manfred K. Warmuth

Browse the full COLT paper archive.