Metric learning seeks a transformation of the feature space that enhances
prediction quality for the given task at hand. In this work we provide
PAC-style sample complexity rates for supervised metric learning. We give
matching lower- and upper-bounds showing that the sample complexity scales with
the representation dimension when no assumptions are made about the underlying
data distribution. However, by leveraging the structure of the data
distribution, we show that one can achieve rates that are fine-tuned to a
specific notion of intrinsic complexity for a given dataset. Our analysis
reveals that augmenting the metric learning optimization criterion with a
simple norm-based regularization can help adapt to a dataset's intrinsic
complexity, yielding better generalization. Experiments on benchmark datasets
validate our analysis and show that regularizing the metric can help discern
the signal even when the data contains high amounts of noise.

这项工作提供了基于 PAC 风格的样本复杂度给监督式度量学习，并通过使用数据分布的结构，展示了适用于特定隐含复杂的例子的适当匹配的速率。实验也表明，规范化度量学习优化准则可以帮助适应数据集的固有复杂性，从而提高泛化性能。