### On-line learning with malicious noise and the closure algorithm

**Authors: Peter Auer and Nicolò Cesa-Bianchi**.

Email: wiehagen@informatik.uni-kl.de

**Source: ***Annals of Mathematics and Artificial Intelligence*
Vol. 23, No. 1-2, 1998, 83-99.

**Abstract.**
We investigate a variant of the on-line learning model for classes of {0,1}-valued functions
(concepts) in which the labels of a certain amount of the input instances are corrupted by
adversarial noise. We propose an extension of a general learning strategy, known as ``Closure
Algorithm'', to this noise model, and show a worst-case mistake bound of m + (d+1)K for
learning an arbitrary intersection-closed concept class C, where K is the number of noisy labels, d
is a combinatorial parameter measuring C's complexity, and m is the worst-case mistake bound of
the Closure Algorithm for learning C in the noise-free model. For several concept classes our
extended Closure Algorithm is efficient and can tolerate a noise rate up to the
information-theoretic upper bound. Finally, we show how to efficiently turn any algorithm for the
on-line noise model into a learning algorithm for the PAC model with malicious noise.

©Copyright 1998 Baltzer Science Publishers