We study online algorithms for selective sampling that use regularized least squares (RLS) as base classier. These algorithms typically perform well in practice, and some of them have formal guarantees on their mistake and query rates. We rene and extend these guarantees in various ways, proposing algorithmic variants that exhibit better empirical behavior while enjoying performance guarantees under much more general conditions. We also show a simple way of coupling a generic gradient-based classier with a specic RLSbased selective sampler, obtaining hybrid algorithms with combined performance guarantees.
['Francesco Orabona', 'Nicolò Cesa-Bianchi']
Better Algorithms for Selective Sampling