Lecture

In this work, we focus on learning a similarity for linear classification,
based on the notion of goodness of a similarity function (Balcan et al.). We
cast our learning problem as an efficient convex quadratic program. Using the
framework of uniform stability, we are able to derive generalization bounds
guaranteeing the consistency of our method. Experiments on various datasets
show the practical effectiveness of our approach, the great sparsity of the
resulting models and its robustness to overfitting.