How Much of Deep Metric Learning Is Just a Linear Metric?

Metric learning trains a model so that distances between items mean something: two photos of the same bird species should be close, photos of different species far apart. For a decade, papers reported large gains from new training losses applied to whole neural networks. Two careful audits then showed that most of those gains disappear under fair comparison. Once the backbone network, optimizer and tuning budget are held fixed, a 2006 loss roughly matches a 2019 loss, and a frozen ImageNet network with PCA comes close to many published methods. Those audits left one question unasked. When fine-tuning the whole network does help, how much of the help could have come from a single learned linear map applied to frozen features? That map is a Mahalanobis metric, the object classical metric learning has studied since the mid-2000s.

This note proposes a controlled decomposition. It re-runs the audited deep metric learning setups and adds a family of regularized linear metrics trained on the same frozen backbone, with the same splits and the same hyperparameter-search budget. It reports what fraction of the end-to-end improvement the linear metric recovers. The proposal also makes a falsifiable prediction from learning theory: how that fraction should change as the number of training examples grows relative to the feature dimension. If the prediction holds, benchmark papers gain a cheap mandatory reference point, a "linear ceiling," that any end-to-end method must clear to claim that adapting the backbone mattered.

Core Claim

The claim is that on small fine-grained retrieval benchmarks, most of the gap between raw frozen features and tuned end-to-end training is recoverable by a Frobenius-regularized linear metric. Frobenius regularization penalizes the squared size of the matrix entries. The claim further says the unrecovered remainder grows with training-set size and is largest on the many-class Stanford Online Products benchmark.

The theoretical anchor is Sample Complexity of Learning Mahalanobis Distance Metrics. It shows that distance-based metric learning generalizes at rate $O(\sqrt{D/m})$ for ambient dimension $D$ and $m$ samples, and that norm regularization lets the learner adapt to a lower intrinsic dimension. A linear metric on a 512- to 1024-dimensional frozen feature has far fewer parameters than a full backbone. It should therefore win or tie when data are scarce, and lose only when there is enough data to adapt the representation itself. Unbiased Evaluation of Deep Metric Learning Algorithms supports this reading: larger backbones often overfit on small fine-grained datasets.

The quantity we report for each benchmark, backbone and metric is the recovered fraction

$$\rho = \frac{S_{\text{lin}} - S_{\text{frozen}}}{S_{\text{e2e}} - S_{\text{frozen}}}.$$

Here $S_{\text{frozen}}$ is retrieval score with plain cosine distance on frozen features, $S_{\text{lin}}$ is the score after the best regularized linear metric, and $S_{\text{e2e}}$ is the score of the best tuned end-to-end method. A value of $\rho$ near 1 means backbone adaptation added almost nothing beyond a linear re-weighting of features.

Positioning Against Prior Work

The two audits supply both the motivation and the protocol. A Metric Learning Reality Check standardized 13 deep losses on a BN-Inception backbone with frozen batch-norm, RMSprop and Bayesian hyperparameter search under 4-fold cross-validation on training classes. It introduced MAP@R, which scores the whole ranked neighborhood rather than only the top hit. Unbiased Evaluation of Deep Metric Learning Algorithms did the same for 12 losses and showed that backbone changes, such as adding batch normalization, explained gains credited to losses. Both audits compare losses with one another. Neither separates what the loss does to the backbone from what it could do through a linear map on top. We reuse their protocol exactly and add that missing axis.

Classical metric learning supplies the linear methods. Large Margin Nearest Neighbor (LMNN) pulls each point toward chosen same-class neighbors and pushes differently labeled points beyond a margin. Information-Theoretic Metric Learning (ITML) keeps the learned metric close to a prior under distance constraints using cheap rank-one updates. Relevant Component Analysis (RCA) whitens using within-group covariance. These methods were evaluated on MNIST and small tabular sets with hand-built features, never on modern frozen embeddings under audited protocols.

The sample-complexity paper constrains the design: unregularized variants should overfit, so regularization strength must be tuned inside the same cross-validation. Is anisotropy really the cause of BERT embeddings not being semantic? works in the other direction. It shows that unsupervised whitening, an unlearned Mahalanobis transform, changes geometry without recovering meaning. We read that as a warning that only supervised linear metrics are worth testing, not as evidence that linear maps cannot help.

Research Program

We build one codebase on top of the Reality Check protocol, using the same BN-Inception ImageNet weights, image preprocessing, train/test class splits on CUB-200-2011, Cars196 and Stanford Online Products, and 4-fold class-disjoint cross-validation.

End-to-end arm. We retrain the strongest audited losses: Contrastive, Multi-Similarity and Proxy-Softmax.

Linear arm. We first extract frozen features once, using center crops plus a fixed set of augmented crops, so the linear learner sees comparable augmentation. We then fit four metric families on those features. The first is Frobenius-regularized ITML. The second is regularized LMNN, trained by stochastic subgradient steps so it scales to Stanford Online Products. The third is RCA. The fourth is a low-rank linear head trained by SGD with each of the same three deep losses. Each method gets the same number of Bayesian-optimization trials as each end-to-end loss. Tuned settings include rank, regularization strength, margins and number of target neighbors. All test-class data are untouched until final evaluation.

The objective for the regularized linear arm is

$$\min_{L \in \mathbb{R}^{d \times D}} \ \frac{1}{|T|}\sum_{(i,j,l)\in T} \ell\big(\|Lx_i - Lx_j\|^2, \|Lx_i - Lx_l\|^2\big) + \lambda \|L^\top L - I\|_F^2.$$

Here $x$ are frozen features in $\mathbb{R}^D$, $d$ is the output rank, and $T$ is a set of anchor–positive–negative triples. The function $\ell$ is the method's loss: the LMNN hinge, contrastive or proxy-based. The parameter $\lambda$ controls shrinkage toward cosine distance. Setting $\lambda \to \infty$ recovers the frozen baseline, and $\lambda = 0$ gives the unregularized method.

Scaling sweep. To test the theoretical prediction rather than only report $\rho$, we subsample training classes and images per class on Stanford Online Products. This produces a grid of training-set sizes $m$, over which we trace $\rho(m)$. We repeat the sweep with a second frozen backbone of different dimension $D$. Because the $\sqrt{D/m}$ rate is an upper bound, we do not expect a precise curve. We do commit to a direction: $\rho$ should fall as $m/D$ rises.

Text arm. A smaller arm transfers the question to sentence embeddings, where the anisotropy debate lives. Using SentEval's semantic-similarity tasks (STS and SICK-R) through SentEval, we compare three ways of measuring distance on frozen BERT-base-cased and BERT-base-uncased features. The first is unsupervised whitening. The second is a supervised regularized linear metric fit on SICK training pairs. The third is plain cosine. The question is whether a supervised linear metric reverses the whitening failure reported by Fuster Baggetto and Fresno. If it does, that clarifies the claim in ANALOGICAL, which computed Mahalanobis distance from empirical covariance but never learned the metric.

Baselines

Frozen feature with cosine distance. This is the do-nothing reference, run on identical features and splits. It anchors the denominator of $\rho$.

Frozen feature with PCA, and with whitening. These are the unsupervised linear baselines. The Reality Check reports that frozen features with PCA rival many published methods. Their rank is tuned under the same cross-validation. Beating them shows that labels, not just decorrelation, drive the linear arm's gains.

Tuned end-to-end Contrastive loss. This is the strongest existing method under audit. On CUB-200-2011, A Metric Learning Reality Check reports MAP@R of 26.53%, against 24.70% for Multi-Similarity loss. We rerun it with their protocol and budget to confirm we reproduce this number before comparing anything.

Proxy-Softmax. This is the strongest retrieval baseline in Unbiased Evaluation of Deep Metric Learning Algorithms: 58.3% Recall@1 on CUB-200-2011 with Inception-BN and 63.5% with ResNet50. For Cars196 and Stanford Online Products the file gives no audited per-method numbers. No reported result was found on Lacuna for audited MAP@R on Cars196 or Stanford Online Products, so our reproductions will define those references.

What counts as success. The linear arm "matches" end-to-end training on a benchmark if its MAP@R lies within the spread of end-to-end results across random seeds. It "beats" end-to-end training if it exceeds the end-to-end mean by more than that spread.

Ablations. Two ablations isolate the key ingredients. The first sets $\lambda = 0$ to test whether regularization, as the theory predicts, is what keeps the linear metric from overfitting. The second swaps the classical losses for SGD-trained deep losses on the same linear head, to test whether the classical algorithms add anything beyond linearity.

Compute is reported as GPU-hours per method. The linear arm's feature extraction is amortized across its methods, and we report this separately so the cost comparison is honest.

Why not just…?

Why not just use frozen features with PCA, as the Reality Check already suggested? That baseline is in the study, and it may be a serious threat on CUB-200-2011. The Reality Check never measured how far supervised linear metrics move beyond it. Text-classification evidence shows task-blind PCA can hurt badly: in Learning Better Data Representation Using Inference-Driven Metric Learning, error rose from 31.3% to 46.4%, while learned metrics helped. If supervised linear metrics do not beat PCA, $\rho$ collapses to the PCA value, and we will report that as the finding.

Why not just train a linear layer with a tuned deep loss and skip LMNN and ITML? This is a real possibility, and it is built in as an ablation. If an SGD-trained contrastive head equals LMNN and ITML, the conclusion becomes "linearity plus regularization is enough; the classical solvers are optional." That still answers the central question about backbone adaptation. The claim does not depend on classical methods winning.

Why not just fine-tune end-to-end with a tuned 2006 loss, as the audits recommend? That tells you the best score, not where the score comes from. Without the linear arm, a paper cannot tell whether its backbone changes did anything a linear re-weighting could not. The Stanford Online Products scaling sweep is designed to show exactly when fine-tuning becomes necessary.

Decisive Checks

The first check is reproduction. We must recover roughly 26.5% MAP@R for tuned Contrastive loss on CUB-200-2011. Without that, no $\rho$ is interpretable.

The core claim is supported if three things hold together. First, regularized linear metrics reach $\rho \geq 0.7$ on CUB-200-2011 and Cars196 in MAP@R. Second, $\rho$ falls monotonically along the Stanford Online Products subsampling sweep. Third, the $\lambda = 0$ ablation degrades as the training set shrinks. The claim is refuted if $\rho$ stays low on the small benchmarks, or if $\rho$ shows no dependence on training-set size.

Every arm reports MAP@R, Recall@1 and NMI, a clustering score. This lets us check whether the linear metric trades retrieval for clustering in the way Unbiased Evaluation of Deep Metric Learning Algorithms observed for some losses.

In the text arm, the decisive comparison is supervised linear metric against whitening on STS. A clear supervised gain would show that the anisotropy debate conflated unlearned and learned Mahalanobis transforms. No gain would extend Fuster Baggetto and Fresno's negative result to supervised linear metrics.