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 obtain the excess risk bounds of the order $O(n^{-\frac{1}{2}}
\mathrm{log}n)$ 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.

本研究基于稳定性分析，研究了三元组学习的一般化保证，并获得了随机梯度下降和正则化风险最小化的高概率一般化上限和过量风险下限，这为三元组度量学习的理论奠定了基础。

三元组学习的稳定性和泛化性能

On the Stability and Generalization of Triplet Learning

Learning visual similarity requires to learn relations, typically between
triplets of images. Albeit triplet approaches being powerful, their
computational complexity mostly limits training to only a subset of all
possible training triplets. Thus, sampling strategies that decide when to use
which training sample during learning are crucial. Currently, the prominent
paradigm are fixed or curriculum sampling strategies that are predefined before
training starts. However, the problem truly calls for a sampling process that
adjusts based on the actual state of the similarity representation during
training. We, therefore, employ reinforcement learning and have a teacher
network adjust the sampling distribution based on the current state of the
learner network, which represents visual similarity. Experiments on benchmark
datasets using standard triplet-based losses show that our adaptive sampling
strategy significantly outperforms fixed sampling strategies. Moreover,
although our adaptive sampling is only applied on top of basic triplet-learning
frameworks, we reach competitive results to state-of-the-art approaches that
employ diverse additional learning signals or strong ensemble architectures.
Code can be found under this https URL

本文提出了一种基于强化学习的自适应采样策略，根据当前学习状态调整采样分布，能够大幅提高三元组损失训练框架的性能。