Deep metric learning (DML) aims to structure an embedding space where semantically similar items are pulled close together and dissimilar items are pushed far apart. Traditionally, this structuring relies on pair-based losses (like contrastive loss) or triplet-based losses. While intuitively straightforward, these formulations suffer from a severe computational bottleneck: evaluating pairs scales quadratically ($O(n^2)$) with the number of training instances, and triplets scale cubically ($O(n^3)$).
To train these models on large datasets, practitioners traditionally rely on complex hard-negative mining heuristics to select the most informative pairs or triplets. However, sample mining is computationally expensive, highly sensitive to outliers, and provides only a local view of the embedding space during mini-batch updates.
A rapidly growing body of research circumvents this combinatorial explosion by shifting the paradigm from instance-to-instance comparisons to instance-to-proxy comparisons. By optimizing distances between individual data points and a compressed set of global class representatives—variously termed proxies, centroids, exemplars, or virtual targets—this approach reduces the computational complexity of metric learning to a linear scale ($O(n)$).
The Geometry of Proxy-Based Losses
Why does comparing an individual data point to a single global proxy successfully optimize the relationships between all data points? The answer lies in the triangle inequality and global consensus.
Traditional Triplet Loss (O(n³)) Proxy-Based Loss (O(n))
[Instance A] [Instance A]
/ \ |
/ \ | (Minimize)
/ \ v
[Instance B] --- [Instance C] [Class Proxy]
(Positive) (Negative) |
| (Maximize)
v
[Other Proxies]
Instead of evaluating whether Instance A is closer to Positive Instance B than to Negative Instance C, a proxy-based loss minimizes the distance between Instance A and its corresponding class proxy, while simultaneously maximizing its distance to all other class proxies.
As Yair Alon et al. demonstrated in No Fuss Distance Metric Learning Using Proxies, replacing exhaustive point-to-point comparisons with learned representative vectors completely bypasses the need for sample mining while maintaining or improving retrieval accuracy. By pulling an instance toward its class proxy, the network implicitly pulls all instances of that class closer to each other.
To understand why this global approximation works so effectively, Takuya Furusawa leveraged mean field theory from statistical physics in Mean Field Theory in Deep Metric Learning. The work demonstrates that complex, high-order pair-to-pair interactions can be mathematically approximated as simpler point-to-average-field interactions. This global field provides a smoothing effect over the optimization landscape, making the model significantly more robust to label noise. For instance, the PRISM algorithm developed by Chang Liu et al. in Noise-Resistant Deep Metric Learning With Ranking-Based Instance Selection uses class centroids to filter out mislabeled data, relying on class-level consensus rather than volatile instance-level pairs.
Fixed Targets and Virtual Regression
While some methods learn proxies dynamically alongside the network's weights, another facet of this direction fixes the targets entirely, transforming metric learning into a straightforward regression problem.
In Regressive Virtual Metric Learning, Michaël Perrot et al. proved that pairwise constraints can be swapped for a multivariate regression task against fixed "virtual points" in the target space. This formulation yields a closed-form solution that scales linearly with dataset size.
This principle scales effectively to highly complex data structures:
- Sequential Data: Bing Su et al. introduced Regressive Virtual Sequence Metric Learning (RVSML) in Learning Distance for Sequences by Learning a Ground Metric, mapping multi-dimensional sequences to class-specific "virtual sequences" to avoid the combinatorial explosion of sequence alignment constraints.
- Cross-Modal Retrieval: In Joint Cluster Unary Loss for Efficient Cross-Modal Hashing, Jianmin Li et al. utilized fixed auxiliary semantic cluster centers. Minimizing a unary loss between multi-modal data points and these fixed centers acts as a proxy for minimizing cross-modal triplet loss via the triangle inequality, dropping cross-modal training complexity to $O(n)$.
Managing Complex and Collapsing Distributions
Transitioning to a proxy-based framework introduces two geometric challenges: capturing intra-class variance and preventing inter-class proxy collapse.
Capturing Multi-Modal Distributions
A single centroid assumes that a class distribution is unimodal. However, in real-world datasets, a single category (e.g., a specific car model) can exhibit massive visual variance due to changes in viewpoint, lighting, or sub-configurations.
To address this, Qi Qian et al. proposed SoftTriple Loss: Deep Metric Learning Without Triplet Sampling. Instead of a single proxy, SoftTriple assigns multiple learnable centers to each category, using a softmax activation to dynamically determine which sub-center an instance should map to. This retains the linear complexity of proxy models while successfully mapping highly non-linear, multi-modal intra-class structures.
Preventing Proxy Collapse
When an embedding space is optimized solely to pull instances toward class centers, the centers themselves can drift close together, reducing the discriminative power of the network.
To enforce global separation, Xiawu Zheng et al. developed the Decorrelated Global Centralized Ranking Loss (DGCRL) in Towards Optimal Fine Grained Retrieval via Decorrelated Centralized Loss with Normalize-Scale Layer. DGCRL projects features onto a hypersphere and applies Gram-Schmidt orthogonalization directly to the class centers. This forces the proxies to remain distinct and orthogonal to one another, maximizing inter-class margins globally while accelerating training speeds.
Broad Applications of Linear-Complexity Metrics
By breaking the polynomial complexity barrier, proxy- and center-based metric learning enables deep networks to tackle large-scale or dense spatial problems that were previously computationally intractable.
Dense Spatial Segmentation
In 3D point cloud instance segmentation, computing a full point-to-point similarity matrix requires $O(n^2)$ space complexity, which quickly exhausts GPU memory even on small spatial patches. In Rethinking Task and Metrics of Instance Segmentation on 3D Point Clouds, Kosuke Arase et al. bypassed this by calculating distances exclusively between individual points and their respective instance centroids. This optimization reduces space complexity to a linear scale, allowing models to process significantly larger spatial scenes in a single forward pass.
Multi-Instance Learning
Multi-instance learning traditionally requires comparing entire "bags" of samples to other bags, scaling cubically relative to the number of training bags. In Maximum Margin Multi-Instance Learning ($M^3I$), Hua Wang et al. reformulated the objective to measure the distance between a query bag and a consolidated class representation. Shifting from bag-to-bag to class-to-bag comparisons flattens the computational overhead, allowing multi-instance frameworks to scale seamlessly to massive image categorization datasets.
Key Foundational Work
Maximum Margin Multi-Instance Learning (2011) — contributed 2 concept elements to this direction.
Learning large margin likelihoods for realtime head pose tracking (2009) — contributed 2 concept elements to this direction.