  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.
