Orthogonality-Promoting Distance Metric Learning: Convex Relaxation and Theoretical Analysis

Pengtao Xie, Wei Wu, Yichen Zhu, Eric P. Xing

Abstract

Distance Metric Learning (DML) is a critical technique for learning distance measures where similar items are clustered and dissimilar items are separated. While Orthogonality-Promoting Regularization (OPR) is often used to improve model "balancedness" and generalization, its traditional formulations are non-convex and computationally expensive. This paper introduces a convex relaxation for OPR, transitioning from non-convex projection-based DML to a convex Mahalanobis-based framework. We provide the first formal theoretical analysis linking OPR to reduced generalization error and improved performance on imbalanced datasets. Empirical evaluations across diverse domains—including healthcare, text, and images—demonstrate that our convex approach significantly outperforms existing methods in both accuracy and computational efficiency.

Introduction

Distance Metric Learning (DML) aims to learn a transformation that maps data into a space where semantic relationships are preserved. A common strategy is to employ Orthogonality-Promoting Regularization (OPR), which encourages projection vectors to be as perpendicular as possible. Despite its empirical success, OPR has historically faced significant challenges: the optimization problems are typically non-convex, leading to local optima and high computational costs; and there has been a lack of theoretical understanding regarding why OPR improves performance on imbalanced data.

Methodology

To address these challenges, we propose a convex relaxation of OPR. We shift the focus from Projection-based DML (PDML) to Mahalanobis-based DML (MDML).

Convex Relaxation

We derive convex approximations for three popular non-convex regularizers based on Bregman Matrix Divergences: Squared Frobenius Norm, von Neumann Divergence, and Log-Determinant Divergence. By utilizing the trace norm as a convex proxy for the rank of the Mahalanobis matrix, our model can automatically determine the optimal number of projection vectors during training.

Optimization

The resulting convex optimization problem is solved using a stochastic proximal subgradient descent algorithm. This approach ensures global optimality and eliminates the need for the numerous random restarts required by non-convex baselines.

Experimental Setup

We evaluated our proposed methods on seven diverse datasets spanning healthcare, text, image, and sensory domains. The healthcare (MIMIC-III, EICU) and Reuters datasets are particularly notable for their high class imbalance, serving as a rigorous test for the "balancedness" promoted by OPR.

Table 1: Statistics of the seven datasets used in the experiments, including training/testing sizes, feature dimensions, and number of classes.

Key Results and Discussion

Our analysis reveals several critical insights into the benefits of OPR:

  1. The "Spreading" Effect: We formalize the Imbalance Factor (IF) and prove that OPR forces projection vectors to "spread out" across the feature space. This prevents the model from over-focusing on majority classes and ensures that latent signals from infrequent classes are captured.
  2. Performance and Efficiency: The convex MDML methods consistently outperformed standard DML baselines like LMNN. On the EICU dataset, our method achieved a significant speedup, completing training in ~45 hours compared to the ~500 hours required by non-convex versions.
  3. Generalization: Theoretical bounds show that OPR reduces the Rademacher complexity of the model. Experimental results confirm a smaller gap between training and testing performance, indicating superior generalization.

Conclusion

This work provides a robust mathematical and theoretical foundation for orthogonality-promoting regularization in DML. By introducing convex relaxations, we transform a computationally difficult problem into an efficient one while providing formal proofs for the empirical benefits of OPR. Future work will explore the approximation errors introduced by trace-norm regularization and extend the theoretical analysis specifically to the convex formulations.

Summary updated

BibTeX
@inproceedings{xie2018orthogonality,
  author = {Pengtao Xie and Wei Wu and Yichen Zhu and Eric P. Xing},
  title = {{Orthogonality-Promoting Distance Metric Learning: Convex Relaxation and Theoretical Analysis}},
  booktitle = {International Conference on Machine Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=Sk4wPnZ_ZB},
}
Figure