  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.
