Fast Low-rank Metric Learning for Large-scale and High-dimensional Data

Han Liu, Zhizhong Han, Yu-Shen Liu, Ming Gu

TL;DR

FLRML (Fast Low-Rank Metric Learning) is a novel framework designed to learn distance metrics for massive, high-dimensional datasets that break traditional algorithms. By reformulating low-rank optimization as a search on the Stiefel manifold, the authors achieve state-of-the-art accuracy with orders-of-magnitude speedups and a significantly smaller memory footprint.

The Challenge of Scale in Metric Learning

Metric learning is the art of teaching a model how to calculate the "distance" between data points so that similar items are close together and dissimilar ones are far apart. This is foundational for tasks like image retrieval, k-nearest neighbor classification, and dimensionality reduction.

However, modern datasets present a "double whammy" challenge:

  1. High Dimensionality ($D$): Data points (like high-res images or text vectors) have thousands or millions of features.
  2. Large Scale ($n$): There are hundreds of thousands of samples.

Existing methods often struggle because their computational complexity scales quadratically or cubically with $D$ or $n$. Even "low-rank" methods, which try to simplify the problem by finding a lower-dimensional projection, often still require storing and manipulating massive $D \times D$ matrices during the optimization process. On standard hardware, this inevitably leads to "out-of-memory" errors.

The FLRML Approach

The authors introduce FLRML, which tackles these computational bottlenecks through several key innovations:

  • Stiefel Manifold Optimization: Instead of optimizing in a standard flat (Euclidean) space where low-rank constraints are difficult to enforce, they treat the problem as an unconstrained optimization on the Stiefel manifold (the space of matrices with orthogonal columns). This naturally maintains the low-rank structure without needing complex regularizers.
  • Matrix Embedding of Constraints: They cleverly embed thousands of "triplet constraints" (e.g., "Point A should be closer to B than to C") into a single matrix $K$. This allows them to express the loss function in a compact "trace form," which is much faster to compute than summing individual losses.
  • Complexity Decoupling: By using Singular Value Decomposition (SVD) as a preprocessing step, they reduce the size of the optimization variables from the raw dimension $D$ to the intrinsic rank of the data $r$. This means the "heavy lifting" of the optimization happens on much smaller matrices.
Convergence of FLRML across various datasets
  • Mini-batch Version (M-FLRML): For datasets so large they cannot be loaded into memory for an initial SVD, the authors propose a stochastic version. It processes small chunks of data at a time, calculating descent directions and updating the global metric incrementally.
Accuracy over mini-batches for M-FLRML

Key Insights and Results

The researchers evaluated their method on eight diverse benchmarks, including text collections (NG20, RCV1, TDT2), image data (MNIST), and grueling 3D voxel datasets (like M40-100) featuring up to 1,000,000 dimensions per sample.

  • Unprecedented Memory Efficiency: The most striking result is the scale FLRML can handle. For the M40-100 dataset, a standard dense matrix would require 880 GB of RAM. M-FLRML processed it using only 6.2 GB, making high-dimensional metric learning possible on a standard desktop PC.
  • Blazing Speed: On the TDT2 dataset, FLRML achieved its results in just 10 seconds, while a popular competitor (LMNN) took 1,850 seconds.
  • State-of-the-Art Accuracy: FLRML consistently outperformed or matched state-of-the-art methods. For example, on the NG20 text dataset, it reached 80.2% accuracy, significantly higher than the next best low-rank method.
  • Bypassing the SVD Bottleneck: The authors realized that for truly large-scale data, the optimization itself isn't always the slowest part—the initial data decomposition (SVD) is. The M-FLRML variant successfully bypasses this, allowing the algorithm to handle million-dimensional data without crashing.

Limitations and Future Work

While highly efficient, the current implementation runs on a single processor. The authors note that the next logical step is a distributed version to handle "Big Data" clusters. Additionally, like many manifold-based methods, performance can depend on the choice of the rank hyperparameter. While they provide a heuristic upper bound, more automated ways to determine the optimal rank could further improve the framework's usability. Finally, while M-FLRML mitigates the SVD issue, the core FLRML still relies on it, which can remain computationally expensive if the data's intrinsic rank is very high.

Summary updated

Abstract

Low-rank metric learning aims to learn better discrimination of data subject to low-rank constraints. It keeps the intrinsic low-rank structure of datasets and reduces the time cost and memory usage in metric learning. However, it is still a challenge for current methods to handle datasets with both high dimensions and large numbers of samples. To address this issue, we present a novel fast low-rank metric learning (FLRML) method. FLRML casts the low-rank metric learning problem into an unconstrained optimization on the Stiefel manifold, which can be efficiently solved by searching along the descent curves of the manifold. FLRML significantly reduces the complexity and memory usage in optimization, which makes the method scalable to both high dimensions and large numbers of samples. Furthermore, we introduce a mini-batch version of FLRML to make the method scalable to larger datasets which are hard to be loaded and decomposed in limited memory. The outperforming experimental results show that our method is with high accuracy and much faster than the state-of-the-art methods under several benchmarks with large numbers of high-dimensional data. Code has been made available at https://github.com/highan911/FLRML.
BibTeX
@inproceedings{liu2019fast,
  author = {Han Liu and Zhizhong Han and Yu-Shen Liu and Ming Gu},
  title = {{Fast Low-rank Metric Learning for Large-scale and High-dimensional Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure