Applications of Regularized Least Squares in Classification Problems (invited lecture for ALT 2004) Author: Nicolò Cesa-Bianchi Affiliation: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, Italy Abstract. Regularized least squares (RLS) algorithms, like ridge regression, are well-known approaches for the solution of regression problems. Recently, kernel-based RLS techniques have been used to learn linear-threshold classifiers. In this talk we will present some sparse incremental variants of RLS for classification. We will discuss applications of these variants to hierarchical classification and selective sampling problems, showing theoretical and empirical performance bounds. In some cases, like selective sampling, we will prove bounds in both the statistical learning framework and in the game-theoretic framework. ©Copyright 2004 Author