Multitask Metric Learning: Theory and Algorithm

Boyu Wang, Hejia Zhang, Peng Liu, Zebang Shen, Joelle PineauAISTATS 2019 · OpenReview

Abstract

In this paper, we study the problem of multitask metric learning (mtML). We first examine the generalization bound of the regularized mtML formulation based on the notion of algorithmic stability. Our analysis provides theoretical justification for sharing information across tasks to improve generalization performance. To address the computational challenges of high-dimensional metric learning, we introduce a scalable boosting-based algorithm, mt-BML, and a low-rank variant, mt-LRBML, which utilizes a novel Riemannian retraction operator.

Introduction

Metric learning is a fundamental component of many machine learning algorithms, such as k-Nearest Neighbors and K-means, which rely on distance metrics to determine data similarity. While standard metric learning focuses on a single task, multitask metric learning (mtML) aims to jointly learn metrics for multiple related tasks by leveraging shared underlying structures.

Despite its empirical success, mtML has historically faced two major hurdles: a lack of rigorous theoretical justification explaining why task-sharing improves generalization, and a computational bottleneck caused by the need for Semidefinite Programming (SDP) to maintain Symmetric Positive Definite (SPD) constraints. This paper addresses both issues by providing a stability-based theoretical framework and a highly scalable boosting algorithm.

Theoretical Foundations of mtML

To bridge the theoretical gap, we utilize the concept of algorithmic stability to derive generalization bounds for mtML. We model the metric for a specific task as the sum of a shared global metric and a task-specific metric. Our analysis proves that mtML acts as a bridge between single-task learning and pooling-task learning (treating all data as one giant task).

By sharing data across $T$ tasks, mtML can accelerate the convergence rate of the model's stability from $O(1/n)$ to $O(1/(Tn))$, effectively reducing generalization error when tasks are related. We mathematically formalize a "performance gap"—the difference in loss between single-task and pooling-task approaches—guaranteeing that mtML performs optimally when this gap is small, indicating intrinsic task similarity.

The mt-BML Algorithm

To overcome the $O(d^3)$ complexity of traditional SDP-based methods, we propose Multitask Boosted Metric Learning (mt-BML). This framework treats metric learning as a boosting task using Trace-One Rank-One (TORO) matrices as "weak learners." Because any SPD matrix can be decomposed into a positive linear combination of TORO matrices, the SPD constraint is naturally satisfied without expensive projections.

For high-dimensional data, we introduce mt-LRBML, a low-rank variant. To maintain low-rank efficiency without costly Singular Value Decompositions (SVD), we designed a custom second-order Riemannian retraction operator called SROMU (Symmetric Rank-One Matrix Update). SROMU maps rank-one boosting updates back to a low-rank manifold with $O(dk)$ complexity, providing a massive speedup over naive $O(d^2k)$ projections.

Experimental Evaluation

We evaluated our algorithms on several multitask benchmarks, including Isolet (speech), CoIL (object recognition), and Letter (character recognition).

Performance in Low-Data Regimes

As shown in our experiments, mt-BML consistently outperforms baseline algorithms like mt-LMNN and mt-GPML. This advantage is most pronounced when the ratio of training examples is small, demonstrating the algorithm's ability to effectively leverage cross-task information when individual task data is scarce.

Figure 5: Error rate vs. training ratio on the Isolet dataset. mt-BML demonstrates significant performance gains, especially in low-data regimes.

Efficiency of Low-Rank Representations

The low-rank variant, mt-LRBML, matches or exceeds the performance of full-rank models even at very low ranks. On the Letter dataset, mt-LRBML maintains the lowest error rate across a wide range of metric ranks, proving that the model can compress discriminative information into a compact representation.

Figure 1: Error rate vs. metric rank on the Letter dataset. mt-LRBML achieves superior performance compared to other metric learning methods even at lower ranks.

Scalability

On synthetic datasets scaled up to 1,000 dimensions, mt-BML and mt-LRBML were vastly faster than SDP-based methods. By requiring only the largest eigenvalue ($O(d^2)$) rather than full matrix projections ($O(d^3)$), the boosting framework scales gracefully to high-dimensional spaces.

Conclusion

This work provides both the theoretical "why" and the algorithmic "how" for efficient multitask metric learning. By combining stability-based generalization bounds with a boosting framework and Riemannian optimization, we achieve state-of-the-art accuracy and scalability. Future work will explore the dynamic balancing of tasks within the boosting procedure and extend the "performance gap" concept to transfer and meta-learning domains.

Summary updated

Abstract

In this paper, we study the problem of multitask metric learning (mtML). We first examine the generalization bound of the regularized mtML formulation based on the notion of algorithmic stability, ...
BibTeX
@inproceedings{wang2019multitask,
  author = {Boyu Wang and Hejia Zhang and Peng Liu and Zebang Shen and Joelle Pineau},
  title = {{Multitask Metric Learning: Theory and Algorithm}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=Dl5lOu-6n},
}
Figure