Algorithmic Robustness for Learning via $(ε, γ, τ)$-Good Similarity Functions
This work provides incremental theoretical improvements for researchers in machine learning, particularly those focused on classification and similarity-based methods.
The paper addresses the lack of theoretical guarantees for generalization in classifiers using similarity functions by extending the theory of (ε, γ, τ)-good similarity functions with a new generalization bound based on algorithmic robustness.
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.