Scalable Metric Learning for High Dimensional Data

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 166 papers69 conceptsfrozen 2026-10-04

In machine learning, the choice of "distance" determines everything. Whether you are clustering images, retrieving documents, or identifying faces, you are essentially asking: how similar are these two points? While the standard Euclidean distance is a natural starting point, it assumes all features are equally important and independent.

To capture the true semantic relationships in complex data, researchers use Metric Learning. The goal is to learn a Mahalanobis distance—a way of "stretching" and "rotating" the data space so that similar items are pulled together and dissimilar ones are pushed apart. However, as data dimensionality grows, this process hits a "computational wall."

The Geometry of Stretching Space

A Mahalanobis distance is defined by a matrix $M$. For two points $x$ and $y$, the distance is $d_M(x, y) = \sqrt{(x-y)^T M (x-y)}$. If $M$ is the identity matrix, we have Euclidean distance. If $M$ is diagonal, we are simply re-scaling each feature. If $M$ is a full-rank matrix, we are accounting for complex correlations between features.

As Brian Kulis and Jason V. Davis point out in Metric and Kernel Learning using a Linear Transformation, learning this matrix $M$ is essentially learning a linear transformation of the data. The challenge is that $M$ must be positive semi-definite (PSD) to ensure distances are never negative. Maintaining this PSD constraint during optimization is the primary source of computational grief.

Breaking the Cubic Wall

Traditional metric learning relies on Semidefinite Programming (SDP). This requires repeated eigenvalue decompositions, which scale cubically ($O(d^3)$) with the number of features $d$. For a 10,000-dimensional image descriptor, this is a non-starter.

To bypass this, Jason V. Davis and Brian Kulis introduced Information-Theoretic Metric Learning (ITML) in Information-theoretic Metric Learning. Instead of expensive projections, ITML minimizes a Bregman divergence between the learned metric and a prior. This transforms a global matrix constraint into a series of simple linear updates, allowing metric learning to scale to much larger problems.

Exploiting Low-Rank Structure

In high-dimensional settings, we often don't need to learn all $d^2$ parameters of a full matrix. Most data lives on a much lower-dimensional manifold.

Wei Liu and colleagues demonstrated in Low-Rank Similarity Metric Learning in High Dimensions that the optimal metric often resides within the subspace spanned by the training data. By constraining the search to this subspace, they reduced the complexity from $d$-dimensional to $n$-dimensional (where $n$ is the number of samples), making it practical for genomics and computer vision.

Similarly, Qi Qian and Shenghuo Zhu developed Multi-stage Metric Learning (MsML) in Fine-Grained Visual Categorization via Multi-stage Metric Learning. They break the optimization into smaller stages using randomized low-rank approximations, effectively turning a cubic problem into a linear one.

Optimization on the Manifold

Rather than treating the PSD constraint as a barrier to be checked after every step, some researchers treat the space of valid metrics as a curved geometric surface—a Riemannian manifold.

In Fixed-Rank Supervised Metric Learning on Riemannian Manifold, Yadong MU uses a "retraction operator" to ensure that every gradient step stays on the manifold of low-rank matrices. This avoids the need for costly decompositions entirely. Mathieu Salzmann extended this logic in Joint Dimensionality Reduction and Metric Learning: A Geometric Take, arguing that dimensionality reduction and metric learning should be learned together on this manifold rather than as separate pre-processing steps.

Learning Under Compression

Can we learn a high-dimensional metric without ever looking at the full-dimensional data? Recent work suggests yes. Efstratios Palias showed in The Effect of Intrinsic Dimension on Metric Learning under Compression that if data has a low "stable dimension," we can train on randomly compressed data and still recover an accurate metric. This suggests that the "curse of dimensionality" is often a ghost—the intrinsic geometry of the data is what actually dictates the difficulty of the learning task.

Why It Works: The Intuition

The shift in this research area has been from exact optimization to structured approximation.

  1. Sparsity: If features are mostly independent, a diagonal matrix is enough. Xingyu Gao showed in SOML: Sparse Online Metric Learning with Application to Image Retrieval that for million-dimensional vectors, sparsity-inducing techniques prevent overfitting and save memory.
  2. Decomposition: Chunhua Shen and Junae Kim demonstrated in Positive Semidefinite Metric Learning Using Boosting-like Algorithms that a complex metric can be built as an ensemble of simple, rank-one "weak learners."
  3. Dual Spaces: Qi Qian and Rong Jin proposed Dual Random Projection (DuRP) in Towards Making High Dimensional Distance Metric Learning Practical, solving the problem in a low-dimensional dual space and then projecting the solution back.

By moving away from the rigid, $O(d^3)$ requirements of early Mahalanobis methods, these researchers have made it possible to learn custom similarity measures for the massive, high-dimensional datasets that define modern AI.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_metric_learning_for_high_dimens_50d44fd7,
  title = {Scalable Metric Learning for High Dimensional Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-metric-learning-for-high-dimensional-data/rdr_50d44fd7618a4f17ae0b2f369b82f12e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_metric_learning_for_high_dimens_50d44fd7_v1,
  title = {Scalable Metric Learning for High Dimensional Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-metric-learning-for-high-dimensional-data/rdr_50d44fd7618a4f17ae0b2f369b82f12e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}