Similarity learning for provably accurate sparse linear classification

In recent years, the crucial importance of metrics in machine learning algorithms has led to an increasing interest for optimizing distance and similarity functions. Most of the state of the art focus on learning Maha-lanobis distances (requiring to fulfill a con-straint of positive semi-definiteness) for use in a local k-NN algorithm. However, no theo-retical link is established between the learned metrics and their performance in classifica-tion. In this paper, we make use of the formal framework of (ǫ, γ, τ)-good similarities intro-duced by Balcan et al. to design an algorithm for learning a non PSD linear similarity op-timized in a nonlinear feature space, which is then used to build a global linear classi-fier. We show that our approach has uniform stability and derive a generalization bound on the classification error. Experiments per-formed on various datasets confirm the effec-tiveness of our approach compared to state-of-the-art methods and provide evidence that (i) it is fast, (ii) robust to overfitting and (iii) produces very sparse classifiers. 1