  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
