On the Stability and Generalization of Triplet Learning

Document Type

Conference Proceeding

Publication Title

Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023

Abstract

Triplet learning, i.e. learning from triplet data, has attracted much attention in computer vision tasks with an extremely large number of categories, e.g., face recognition and person re-identification. Albeit with rapid progress in designing and applying triplet learning algorithms, there is a lacking study on the theoretical understanding of their generalization performance. To fill this gap, this paper investigates the generalization guarantees of triplet learning by leveraging the stability analysis. Specifically, we establish the first general high-probability generalization bound for the triplet learning algorithm satisfying the uniform stability, and then 1 obtain the excess risk bounds of the order O(n−2 logn) for both stochastic gradient descent (SGD) and regularized risk minimization (RRM), where 2n is approximately equal to the number of training samples. Moreover, an optimistic generalization bound in expectation as fast as O(n−1) is derived for RRM in a low noise case via the on-average stability analysis. Finally, our results are applied to triplet metric learning to characterize its theoretical underpinning.

First Page

7033

Last Page

7041

DOI

10.1609/aaai.v37i6.25859

Publication Date

6-26-2023

Keywords

Machine Learning, Learning Theory

Comments

Access available at AAAI OJS

Open Source Publishing system

Link to Full Text

Share

COinS