Self-Certified Deep Metric Learning with N-Tuple Losses

Deep metric learning (DML) excels in retrieval and re-identification tasks, driven by tuple-wise loss functions that capture rich inter-sample relationships. Yet, the non-i.i.d. nature of such training complicates generalisation analysis, and the impact of tuple size remains unclear. While PAC-Bayes bounds have been applied to pairwise learning, their behaviour for higher-order tuples is unexplored. We extend this evaluation to general N-tuple settings using neural networks trained with a PAC-Bayes regularised surrogate loss. Experiments on CIFAR-10 show that sample complexity increases with tuple size, revealing trade-offs be tween tuple size, model capacity, and certificate tightness.