Department of Computer, Control and Management Engineering

In this talk, we describe a general algorithmic approach to nonparametric learning in data streams.  Our method covers the input space using simple classifiers that are locally trained. A good balance between model complexity and predictive accuracy is achieved by dynamically adapting the cover to the local complexity of the classification problem. For the simplest instance of our approach, we prove a theoretical performance guarantee against any Lipschitz classifier and without stochastic assumptions on the stream. Experiments on standard benchmarks complement the theoretical results, showing good performance even when the model size is kept independent of the stream length.