While considerable theoretical progress has been devoted to the study of
metric and similarity learning, the generalization mystery is still missing. In
this paper, we study the generalization performance of metric and similarity
learning by leveraging the specific structure of the true metric (the target
function). Specifically, by deriving the explicit form of the true metric for
metric and similarity learning with the hinge loss, we construct a structured
deep ReLU neural network as an approximation of the true metric, whose
approximation ability relies on the network complexity. Here, the network
complexity corresponds to the depth, the number of nonzero weights and the
computation units of the network. Consider the hypothesis space which consists
of the structured deep ReLU networks, we develop the excess generalization
error bounds for a metric and similarity learning problem by estimating the
approximation error and the estimation error carefully. An optimal excess risk
rate is derived by choosing the proper capacity of the constructed hypothesis
space. To the best of our knowledge, this is the first-ever-known
generalization analysis providing the excess generalization error for metric
and similarity learning. In addition, we investigate the properties of the true
metric of metric and similarity learning with general losses.

我们通过利用真实度量（目标函数）的特定结构，构建了一个近似真实度量的结构化深层 ReLU 神经网络，从而研究了度量和相似性学习的泛化性能，推导了度量和相似性学习问题的过度泛化误差界限，并通过仔细估计逼近误差和估计误差，得出了一个最佳的过度风险率，这是首次的度量和相似性学习的过度泛化错误分析，此外，我们还研究了具有一般损失的度量和相似性学习的真实度量的属性。