Robustness and Generalization for Metric Learning

Abstract

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.

16 pages, to appear in Neurocomputing

References in corpus (5)

• A Survey on Metric Learning for Feature Vectors and Structured Data
• Parametric Local Metric Learning for Nearest Neighbor Classification
• Similarity Learning for Provably Accurate Sparse Linear Classification
• Similarity-based Learning via Data Driven Embeddings
• Generalization Bounds for Metric and Similarity Learning

Cited by in corpus (17)

• A Survey on Metric Learning for Feature Vectors and Structured Data
• Revisiting Training Strategies and Generalization Performance in Deep Metric Learning
• Sample complexity of learning Mahalanobis distance metrics
• Sparse Compositional Metric Learning
• Escaping the Curse of Dimensionality in Similarity Learning: Efficient Frank-Wolfe Algorithm and Generalization Bounds
• Online Learning with Pairwise Loss Functions
• Learning to Approximate a Bregman Divergence
• Supervised Metric Learning with Generalization Guarantees
• A Probabilistic Theory of Supervised Similarity Learning for Pointwise ROC Curve Optimization
• Online Pairwise Learning Algorithms with Kernels
• Deep Divergence Learning
• MALTS: Matching After Learning to Stretch
• Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning
• Gentle Local Robustness implies Generalization
• Geometry-aware Deep Transform
• On Tree-based Methods for Similarity Learning
• Dimension Free Generalization Bounds for Non Linear Metric Learning