Robustness and Generalization for Metric Learning
This work addresses the problem of understanding and ensuring generalization in metric learning for researchers and practitioners, but it is incremental as it adapts existing robustness concepts to this domain.
The paper tackles the lack of thorough study on generalization ability in metric learning by introducing an adaptation of algorithmic robustness to derive generalization bounds, showing that a weak notion of robustness is necessary and sufficient for generalization, and applying this framework to a large family of existing algorithms, including sparse formulations not covered before.
Metric learning has attracted a lot of interest over the last decade, but the generalization ability of such methods has not been thoroughly studied. In this paper, we introduce an adaptation of the notion of algorithmic robustness (previously introduced by Xu and Mannor) that can be used to derive generalization bounds for metric learning. We further show that a weak notion of robustness is in fact a necessary and sufficient condition for a metric learning algorithm to generalize. To illustrate the applicability of the proposed framework, we derive generalization results for a large family of existing metric learning algorithms, including some sparse formulations that are not covered by previous results.