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 神经网络，从而研究了度量和相似性学习的泛化性能，推导了度量和相似性学习问题的过度泛化误差界限，并通过仔细估计逼近误差和估计误差，得出了一个最佳的过度风险率，这是首次的度量和相似性学习的过度泛化错误分析，此外，我们还研究了具有一般损失的度量和相似性学习的真实度量的属性。

深度 ReLU 网络的度量学习和相似性学习的泛化分析

Generalization analysis with deep ReLU networks for metric and  similarity learning

Pairwise learning refers to learning tasks where a loss takes a pair of
samples into consideration. In this paper, we study pairwise learning with deep
ReLU networks and estimate the excess generalization error. For a general loss
satisfying some mild conditions, a sharp bound for the estimation error of
order $O((V\log(n) /n)^{1/(2-\beta)})$ is established. In particular, with the
pairwise least squares loss, we derive a nearly optimal bound of the excess
generalization error which achieves the minimax lower bound up to a logrithmic
term when the true predictor satisfies some smoothness regularities.

本文研究深度 ReLU 网络下的成对学习，估计其多余泛化误差。通过成对最小二乘损失函数，取得近乎最优的估计上界。