On Metric Robustness, Generalization and Over-parameterization

Metric learning has attracted significant attention since it can substantially improve the performance of subsequent tasks such as classification. Current theories of metric learning have mostly focused on the goodness of the learned metric, but how this metric affects subsequent classification performance remains an open problem. In this paper, we study the relationship between the generalization of metric learning and classification. Firstly, we introduce metric robustness of classification algorithms with respect to metrics, which quantifies the influence of metrics on classification performance. Secondly, we establish classification generalization guarantees through metric robustness for a range of commonly used metrics and classifiers. Thirdly, we prove that over-parameterization does not necessarily lead to overfitting for a class of distance metric learning methods, addressing an open problem that remains unresolved in the metric learning literature.