Algorithmic Robustness for Learning via (ε, γ, τ)-Good Similarity Functions

2014/12/19 by Nicolae, Maria-Irina, Sebban, Marc, Habrard, Amaury +2
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1412.6452

Abstract

The notion of metric plays a key role in machine learning problems such as classification, clustering or ranking. However, it is worth noting that there is a severe lack of theoretical guarantees that can be expected on the generalization capacity of the classifier associated to a given metric. The theoretical framework of (ε, γ, τ)-good similarity functions (Balcan et al., 2008) has been one of the first attempts to draw a link between the properties of a similarity function and those of a linear classifier making use of it. In this paper, we extend and complete this theory by providing a new generalization bound for the associated classifier based on the algorithmic robustness framework.

Related

• Supervised Metric Learning with Generalization Guarantees
• Generalization Bounds for Metric and Similarity Learning
• Guaranteed Classification via Regularized Similarity Learning
• Provably Robust Metric Learning
• Robustness and Generalization