Generalization Bounds for Adversarial Metric Learning

Wen Wen, Han Li, Hong Chen, Rui Wu, Lingjuan Wu, Liangxuan ZhuIJCAI 2023 · DOI

Abstract

Metric learning is a fundamental technique for measuring similarity between objects, powering applications such as facial recognition and image retrieval. Despite its widespread use, the theoretical robustness of metric learning models against adversarial perturbations has remained under-explored. This paper presents the first high-probability generalization bounds for adversarial metric learning (AML) involving pairwise perturbations. We establish a standard convergence rate of $O(n^{-1/2})$ for general losses and a "fast" rate of $O(n^{-1})$ for smooth losses. Our findings provide a rigorous mathematical guarantee that robust distance metrics can generalize effectively from training data to unseen real-world scenarios.

Introduction

Adversarial Metric Learning (AML) aims to defend distance-based models against tiny, calculated perturbations that can deceive a model into misidentifying objects. While empirical defenses have shown promise, a theoretical gap existed regarding their generalization capabilities. Unlike standard classification, metric learning operates on pairs of samples, where an adversary can perturb both elements simultaneously. This pairwise interaction introduces significant mathematical complexity. This work addresses this gap by analyzing how sample size, model complexity, and adversarial strength influence performance on new data.

Theoretical Framework

The study employs two primary theoretical frameworks to derive generalization bounds:

  1. Uniform Convergence and Covering Numbers: To address the non-smooth nature of many adversarial loss functions, the authors utilize $\ell_\infty$ covering numbers. This approach bounds the complexity of the learnable function space, ensuring the training error remains a reliable proxy for the true test error.
  2. Local Rademacher Complexity: For smooth loss functions (e.g., logistic loss), the authors apply local Rademacher complexity to derive tighter, "optimistic" bounds. This demonstrates that under specific conditions, the model can achieve a faster convergence rate of $O(n^{-1})$.

These analyses are applicable to both linear models and deep neural networks, providing broad relevance to modern AI architectures.

Experimental Results

The theoretical insights were validated using four standard benchmarks: Wine, Spambase, MNIST, and CIFAR-10. These classification datasets were adapted for metric learning by forming pairs of "same" and "different" category samples.

Impact of Regularization

The experiments confirmed that regularization significantly enhances generalization under adversarial attack. As shown in Figure 1, increasing the regularization parameter $\lambda$ consistently reduces the generalization error across various datasets and perturbation strengths ($\epsilon$).

Generalization error across four datasets with varying regularization parameter λ.

Dimensionality Reduction as a Defense

A key insight from the theoretical analysis is that projecting high-dimensional data into a lower-dimensional embedding space improves generalization. By limiting the "surface area" available for adversarial attacks, lower-dimensional embeddings ($d'$) lead to a smaller generalization gap. This is empirically demonstrated in Figure 2 for the MNIST dataset.

Effect of embedding dimension d' on the generalization error for the MNIST dataset.

Conclusion

This work provides the first rigorous theoretical foundation for the generalization of adversarial metric learning. By establishing $O(n^{-1/2})$ and $O(n^{-1})$ rates, the authors prove that robust distance metrics are statistically efficient. Future research may focus on dimension-independent bounds, non-additive attacks (e.g., rotations), and the optimization challenges inherent in adversarial objectives.

Summary updated

BibTeX
@inproceedings{wen2023generalization,
  author = {Wen Wen and Han Li and Hong Chen and Rui Wu and Lingjuan Wu and Liangxuan Zhu},
  title = {{Generalization Bounds for Adversarial Metric Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/489},
}
Figure