Technical Summary: Generalization Analysis with Deep ReLU Networks for Metric and Similarity Learning

1. Problem Statement

Metric and similarity learning aim to learn a function $d(x, x')$ that estimates the distance or similarity between pairs of observations $(x, x')$ based on their labels. The performance is typically measured by the generalization error (true risk) $E(d) = \mathbb{E}_{Z,Z'}[\ell(\tau(Y, Y')d(X, X'))]$, where $\ell$ is a convex surrogate loss (e.g., hinge loss) and $\tau$ is a reducing function indicating whether labels match.

While extensive theoretical work exists on the estimation error (convergence of the empirical minimizer to the best function within a fixed hypothesis space) for metric learning, a rigorous understanding of the approximation error (the gap between the best function in the hypothesis space and the true optimal metric $d_\rho$) has been lacking. Previous studies largely focused on linear hypothesis spaces, such as Mahalanobis distances $d_M(x, x') = (x-x')^\top M (x-x')$ or pairwise similarities $s_M(x, x') = x^\top M x'$. These spaces are limited in expressiveness, as their complexity is constrained by the input dimension $p$ (specifically $O(p^2)$), potentially leading to large approximation errors even if estimation errors converge rapidly.

This paper addresses the gap in generalization analysis by investigating the specific structure of the true metric $d_\rho$ and constructing a hypothesis space capable of approximating it effectively using deep ReLU networks.

2. Methodology

2.1 Explicit Form of the True Metric

The authors first derive an explicit representation of the true metric $d_\rho$ for the hinge loss. By minimizing the conditional expectation of the loss, they prove that the true metric is determined by the conditional probability that two samples share the same label:
$$\eta(x, x') = \mathbb{P}(Y = Y' \mid X=x, X'=x') = \langle P_x, P_{x'} \rangle$$
where $P_x$ is the conditional probability vector of labels given $x$. The true metric is shown to be:
$$d_\rho(x, x') = \text{sgn}(1 - 2\eta(x, x')) = \text{sgn}\left(1 - 2\sum_{i=1}^m p_i(x)p_i(x')\right)$$
where $p_i(x) = \mathbb{P}(Y=y_i \mid X=x)$. This representation reveals that learning the metric is equivalent to learning the conditional probabilities $p_i(x)$ and their inner products.

2.2 Structured Deep ReLU Network Construction

To approximate $d_\rho$, the authors construct a structured deep ReLU network $d(x, x')$ composed of three parts:

1. Sub-networks ($h_i$): $m$ deep ReLU networks approximating the conditional probabilities $p_i(x)$.
2. Product Approximation ($\phi$): A deep ReLU network approximating the multiplication function $xy$.
3. Sign Approximation ($F_a$): A two-layer ReLU network approximating the sign function $\text{sgn}(\cdot)$, defined as $F_a(t) = \frac{1}{a}(\sigma(t+a) - \sigma(t-a) - a)$.

The final hypothesis is defined as:
$$d(x, x') = F_a\left(1 - 2\sum_{i=1}^m \phi(h_i(x), h_i(x'))\right)$$
This structure explicitly mimics the derived form of $d_\rho$.

2.3 Error Analysis Framework

The authors analyze the excess generalization error $E(\hat{d}_S) - E(d_\rho)$ by decomposing it into approximation error and estimation error:

1. Approximation Error: Using the smoothness of conditional probabilities (Sobolev space $W^{r, \infty}$) and Tsybakov's noise condition, they bound the error of approximating $d_\rho$ by the structured network.
2. Estimation Error: They utilize the pseudo-dimension of the hypothesis space and a variance-expectation bound (derived from the noise condition) to bound the deviation between the empirical risk and the true risk.
3. Trade-off: By balancing the network complexity (depth, width, number of weights) against the sample size $n$, they derive an explicit excess risk rate.

3. Key Contributions

• First Explicit Excess Risk Bounds: The paper provides the first generalization analysis for metric and similarity learning that yields explicit excess risk bounds, covering both estimation and approximation errors. Previous works only bounded the estimation error.
• Explicit Learning Rate: Under mild conditions (Sobolev smoothness of conditional probabilities and Tsybakov's noise condition), the authors derive a learning rate of order:
  $$O\left(n^{-\frac{(\theta+1)r}{p+(\theta+2)r}}\right)$$
  (up to logarithmic factors), where $p$ is the input dimension, $\theta$ is the noise parameter, and $r$ is the smoothness index.
• Structured Hypothesis Space: The construction of a specific deep ReLU architecture that aligns with the theoretical form of the true metric, demonstrating that such networks can achieve favorable approximation and estimation bounds.
• Structural Insights:
  • Bias Term: The paper shows that the bias term $b$ often used in metric learning is not intrinsic to the theoretical characterization of the true metric; it merely induces a constant shift.
  • Finite Labels: It is argued that the label space $Y$ should be finite; if $Y$ is continuous, the true metric becomes a generalized constant almost surely.
  • Symmetry and Self-Similarity: The true metric is proven to be symmetric. Furthermore, under convex, non-decreasing losses, the paper investigates conditions under which the distance between identical samples is less than or equal to the distance between different samples, providing theoretical justification for symmetric models like Mahalanobis distance.

4. Experimental Results

The authors empirically validate their theoretical findings through two sets of experiments:

1. Real-World Data (FashionMNIST):

   • The proposed structured model was compared against a standard Deep Metric Learning (DML) baseline using a distance-based criterion $\|f(x) - f(x')\|^2 - b$.
   • On both medium-difficulty and hard-difficulty class pairs, the proposed model achieved slightly higher balanced accuracy (e.g., 93.86% vs. 93.67% on the medium pair; 74.87% vs. 74.30% on the hard pair).
   • The results suggest the proposed model captures the underlying similarity structure more effectively.

2. Synthetic Data:

   • A controlled experiment was designed where the true metric is governed by an inner-product structure that violates standard distance-based intuition (specifically, pairs in an "uncertain region" may be similar or dissimilar based on label probabilities rather than geometric distance).
   • The proposed model maintained near-optimal accuracy (~99.9%) across varying levels of uncertainty ($\lambda$) and number of classes ($m$).
   • In contrast, the distance-based DML baseline performance degraded significantly as the uncertainty region grew or the number of classes increased, dropping to ~75% in difficult regimes. This confirms the theoretical prediction that distance-based metrics fail when the similarity structure is not purely geometric.

5. Significance and Claims

The paper claims to be the first to provide explicit excess risk bounds for metric and similarity learning, moving beyond the limitations of previous analyses that focused solely on estimation error within restricted linear hypothesis spaces.

By exploiting the specific structure of the true metric, the authors demonstrate that deep ReLU networks can be theoretically justified not just as universal approximators, but as structured tools that align with the probabilistic nature of the learning problem. The derived learning rates highlight the interplay between input dimension, noise, and smoothness, offering a more nuanced understanding of generalization in these tasks.

The authors note that their assumptions are tailored to their proof techniques (relying on uniform approximation) and leave extensions to other loss functions (like logistic loss) and alternative noise conditions as directions for future work.