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.
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.
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