Sample complexity of learning Mahalanobis distance metrics.

Our Research / Publications

janelia7_blocks-janelia7_biblio_header | block

Neural Information Processing Systems Conference. 2015-Jul ;28

Sample complexity of learning Mahalanobis distance metrics. Branson Lab

Verma N, Branson KM

Sample complexity of learning Mahalanobis distance metrics -- Article and Supplementary Materials PDF

janelia7_blocks-janelia7_biblio_abstract | block

Abstract

Metric learning seeks a transformation of the feature space that enhances prediction quality for a given task. In this work we provide PAC-style sample complexity rates for supervised metric learning. We give matching lower- and upper-bounds showing that sample complexity scales with the representation dimension when no assumptions are made about the underlying data distribution. In addition, by leveraging the structure of the data distribution, we provide rates fine-tuned to a specific notion of the intrinsic complexity of a given dataset, allowing us to relax the dependence on representation dimension. We show both theoretically and empirically that augmenting the metric learning optimization criterion with a simple norm-based regularization is important and can help adapt to a dataset’s intrinsic complexity yielding better generalization, thus partly explaining the empirical success of similar regularizations reported in previous works.

node:body | entity_field

Main Menu (Mobile)- Block

Main Menu - Block

Sample complexity of learning Mahalanobis distance metrics.

Abstract

Janelia Authors