Deep Metric Learning with Chance Constraints

Yeti Ziya Gürbüz, Ogul Can, A. Aydin AlatanWACV 2024 · OpenReview

Abstract: Deep metric learning (DML) aims to minimize empirical expected loss of the pairwise intra-/inter- class proximity violations in the embedding space. We relate DML to feasibility problem of finite chance constraints. We show that minimizer of proxy-based DML satisfies certain chance constraints, and that the worst case generalization performance of the proxy-based methods can be characterized by the radius of the smallest ball around a class proxy to cover the entire domain of the corresponding class samples, suggesting multiple proxies per class helps performance. To provide a scalable algorithm as well as exploiting more proxies, we consider the chance constraints implied by the minimizers of proxy-based DML instances and reformulate DML as finding a feasible point in intersection of such constraints, resulting in a problem to be approximately solved by iterative projections. Simply put, we repeatedly train a regularized proxy-based loss and re-initialize the proxies with the embeddings of the deliberately selected new samples. We applied our method with 4 well-accepted DML losses and show the effectiveness with extensive evaluations on 4 popular DML benchmarks.

Introduction

Deep Metric Learning (DML) is fundamental to tasks like image retrieval and face recognition, where the goal is to learn an embedding space that clusters similar items together while separating dissimilar ones. In large-scale applications, researchers frequently employ proxies—learnable vectors representing class centers—to mitigate the computational complexity of pairwise comparisons. While using multiple proxies per class has empirically shown benefits, a theoretical gap remained regarding why this improves generalization and how to prevent multiple proxies from coalescing into a single point during training.

Theoretical Framework: Chance Constraints and Covering Radius

This work reframes DML as a feasibility problem within the context of Chance Constrained Programming (CCP). Instead of merely minimizing a loss function, the objective is to find a model parameter $\theta$ that satisfies a set of constraints: the probability of a distance violation (e.g., a similar pair being too far apart) must remain below a small threshold $\epsilon$.

A key contribution of this paper is the formal proof that the generalization error of proxy-based DML is upper-bounded by the covering radius. This radius is defined as the size of the smallest ball around a proxy required to cover all samples of its respective class. To minimize this error, the covering radius must be reduced, which theoretically necessitates the use of multiple, well-distributed proxies per class.

The CCP-DML Algorithm

To operationalize these theoretical insights, the authors introduce CCP-DML, an iterative algorithm that treats DML as a set intersection problem. The process cycles through two main phases:

  1. Proxy Selection: A "Greedy K-Center" approach is used to identify new anchor samples from the dataset that best cover previously "uncovered" regions of the class distribution.
  2. Iterative Projection: Proxies are re-initialized with these new samples, followed by solving a regularized version of the DML loss. The regularization term prevents the model from drifting too far from the previous iteration's solution, effectively projecting the model onto the intersection of different constraint sets.
Overview of the CCP-DML algorithm and visualization of embedding space coverage.

Experimental Results

The CCP-DML method was evaluated using four standard base losses (Contrastive, Triplet, Multi-similarity, and Contrastive with Margin) across four major benchmarks: CUB-200-2011, Cars196, Stanford Online Products (SOP), and In-shop Clothes Retrieval.

Performance comparison (MAP@R) of CCP-DML against baseline methods across four standard benchmarks.

The results demonstrate consistent performance gains. CCP-DML outperformed baseline proxy methods across nearly all datasets. Notably, on large-scale datasets like SOP and In-shop, the method showed substantial improvements, validating the "covering radius" theory in high-variance environments. Visualizations on MNIST further confirmed that the method successfully prevents proxy coalescence, maintaining a diverse set of anchors that better represent the underlying data geometry.

Conclusion

By linking DML to chance constraints, this research provides a rigorous explanation for the efficacy of multi-proxy methods. The proposed CCP-DML algorithm offers a scalable way to exploit multiple proxies while ensuring they remain diverse. While the method introduces additional hyperparameters and iterative training cycles, its ability to consistently improve generalization across diverse benchmarks makes it a significant advancement in the field of deep metric learning.

Summary updated

Abstract

Deep metric learning (DML) aims to minimize empirical expected loss of the pairwise intra-/inter- class proximity violations in the embedding space. We relate DML to feasibility problem of finite chance constraints. We show that minimizer of proxy-based DML satisfies certain chance constraints, and that the worst case generalization performance of the proxy-based methods can be characterized by the radius of the smallest ball around a class proxy to cover the entire domain of the corresponding class samples, suggesting multiple proxies per class helps performance. To provide a scalable algorithm as well as exploiting more proxies, we consider the chance constraints implied by the minimizers of proxy-based DML instances and reformulate DML as finding a feasible point in intersection of such constraints, resulting in a problem to be approximately solved by iterative projections. Simply put, we repeatedly train a regularized proxy-based loss and re-initialize the proxies with the embeddings of the deliberately selected new samples. We applied our method with 4 well-accepted DML losses and show the effectiveness with extensive evaluations on 4 popular DML benchmarks. Code is available at: https://github.com/yetigurbuz/ccp-dml
BibTeX
@inproceedings{gurbuz2024deep,
  author = {Yeti Ziya Gürbüz and Ogul Can and A. Aydin Alatan},
  title = {{Deep Metric Learning with Chance Constraints}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2024},
  url = {https://openreview.net/forum?id=DyEGas6iex},
}
Figure