Dimension Free Generalization Bounds for Non Linear Metric Learning
This work provides theoretical guarantees for the generalization of non-linear metric learning, which is a fundamental problem for machine learning researchers and practitioners using neural networks.
This paper provides dimension-free generalization bounds for metric learning using neural network embeddings, addressing both sparse and non-sparse regimes. For the non-sparse regime, a new property called "bounded amplification" is introduced to explain generalization without relying on sparsity, which is common in unregularized SGD.
In this work we study generalization guarantees for the metric learning problem, where the metric is induced by a neural network type embedding of the data. Specifically, we provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime which we term \emph{bounded amplification}. The sparse regime bounds correspond to situations where $\ell_1$-type norms of the parameters are small. Similarly to the situation in classification, solutions satisfying such bounds can be obtained by an appropriate regularization of the problem. On the other hand, unregularized SGD optimization of a metric learning loss typically does not produce sparse solutions. We show that despite this lack of sparsity, by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees. Consequently, these bounds can explain generalization in non sparse real experimental situations. We illustrate the studied phenomena on the MNIST and 20newsgroups datasets.