Dimension Free Generalization Bounds for Non Linear Metric Learning

Mark Kozdoba, Shie MannorarXiv 2021 · OpenReview

Abstract

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 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.

Introduction

Metric learning is a fundamental task in machine learning, focused on discovering a distance function that reflects semantic similarity. In modern deep learning, this is typically achieved by embedding data into a $k$-dimensional space using a neural network—often a Siamese architecture—and optimizing for Euclidean distance. A persistent theoretical challenge has been explaining why these models generalize well even when the embedding dimension $k$ is extremely large, far exceeding the number of training samples.

Traditional generalization bounds for neural networks often rely on sparsity, assuming that regularization (like the $\ell_{2,1}$ norm) keeps the total weight mass small. However, empirical evidence shows that unregularized Stochastic Gradient Descent (SGD) does not produce sparse solutions, yet these models do not overfit. This paper addresses this discrepancy by introducing a novel "bounded amplification" regime that provides dimension-free generalization guarantees.

Theoretical Framework

The authors analyze single-layer non-linear embeddings and derive two distinct types of generalization bounds:

1. Sparsity-Based Bounds

These bounds are adapted from classification theory using covering number estimates and Dudley entropy. They depend on the $\ell_{2,1}$ norm (the sum of column norms) and the spectral norm of the weight matrix. While theoretically sound for regularized models, they fail to explain the performance of unregularized SGD, where these norms grow with the embedding dimension.

2. Bounded Amplification Bounds

To explain the success of unregularized models, the authors introduce a new bound that depends solely on the $\ell_{2,\infty}$ norm—the maximum Euclidean norm of any single column in the weight matrix. This bound is derived using two methods:

  • Rademacher Complexity: Exploiting the sub-additivity of Rademacher complexities for metrics averaged over $k$ coordinates.
  • Dimension Reduction: A scheme showing that any $k$-dimensional distance function can be uniformly approximated by a random projection into a smaller space, independent of $k$.

Empirical Validation

The theoretical findings were tested on two datasets: MNIST (handwritten digits) and 20newsgroups (text data). The 20newsgroups dataset, with its high-dimensional input ($d = 15,000$), serves as a rigorous test for overfitting.

t-SNE visualization of learned embeddings for the 20newsgroups dataset.

The experiments involved training embeddings with $k$ ranging from 1 to 5,000. The results confirmed the "bounded amplification" hypothesis:

  • As $k$ increased, the $\ell_{2,1}$ and spectral norms grew rapidly, rendering sparsity-based bounds useless.
  • The $\ell_{2,\infty}$ norm remained constant regardless of $k$.
  • The generalization gap remained flat, matching the prediction of the dimension-free bound.
t-SNE visualization of learned embeddings for the MNIST dataset.

Key Insights

The core discovery is that unregularized SGD is not sparse, but it is "bounded." Because the distance metric is normalized by $1/k$, the generalization bound becomes independent of the embedding dimension. This suggests that in overparameterized metric learning, all $k$ parameters can be active without causing overfitting, provided their individual amplification is constrained.

Conclusion

This work provides the first uniform generalization bounds for non-linear metric learning that reflect real-world SGD behavior. By shifting focus from total weight mass to individual neuron amplification, the authors explain why increasing embedding dimensions does not necessarily lead to overfitting. Future research will explore the extension of these bounds to deeper architectures and investigate why SGD naturally favors the "bounded amplification" regime.

Summary updated

Abstract

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.
BibTeX
@misc{kozdoba2021dimension,
  author = {Mark Kozdoba and Shie Mannor},
  title = {{Dimension Free Generalization Bounds for Non Linear Metric Learning}},
  year = {2021},
  eprint = {2102.03802},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.03802},
}
Figure