Abstract
Bregman divergences generalize measures such as the squared Euclidean distance and the KL divergence, and arise throughout many areas of machine learning. In this paper, we focus on the problem of approximating an arbitrary Bregman divergence from supervision, and we provide a well-principled approach to analyzing such approximations. We develop a formulation and algorithm for learning arbitrary Bregman divergences based on approximating their underlying convex generating function via a piecewise linear function. We provide theoretical approximation bounds using our parameterization and show that the generalization error $O_p(m^{-1/2})$ for metric learning using our framework matches the known generalization error in the strictly less general Mahalanobis metric learning setting. We further demonstrate empirically that our method performs well in comparison to existing metric learning methods, particularly for clustering and ranking problems.
Introduction
Distance metrics are fundamental to many machine learning algorithms, yet the standard Euclidean distance is often insufficient for complex, high-dimensional data. Metric learning aims to tailor distance measures to specific datasets. While most research has focused on Mahalanobis distances—which are essentially linear transformations—many real-world phenomena, such as probability distributions, are better characterized by Bregman divergences. This family includes the squared Euclidean distance, Kullback-Leibler (KL) divergence, and Itakura-Saito distance.
Learning an arbitrary Bregman divergence is challenging because it requires learning a strictly convex generating function $\phi$. Previous methods have often been either too restrictive (limited to linear models) or lacked the theoretical guarantees necessary for reliable generalization. This work introduces a framework that bridges this gap, offering both the flexibility of non-linear metric learning and the rigorous theoretical foundations of simpler linear methods.
Methodology: Piecewise Bregman Divergence Learning (PBDL)
The core contribution of this work is Piecewise Bregman Divergence Learning (PBDL). The method parameterizes the generating convex function $\phi$ as a max-affine function: $$h(x) = \max_{k \in [K]} (a_k^T x + b_k)$$ This approach represents a complex convex surface as the upper envelope of a set of $K$ hyperplanes. By increasing $K$, the model can approximate any convex function with arbitrary precision.
Technical Formulation
The learning process is framed as a convex optimization problem. Given relative supervision (e.g., "Point A is more similar to B than to C"), the parameters of the hyperplanes ($a_k, b_k$) can be learned via a Linear Program. Crucially, the authors prove that this max-affine parameterization approximates not only the function's value but also its gradient—a vital property since Bregman divergences are defined using the gradient of $\phi$.
Furthermore, the authors establish a generalization error bound of $O_p(m^{-1/2})$, where $m$ is the number of training samples. This result is significant because it demonstrates that the increased expressivity of the non-linear Bregman model does not come at the cost of statistical efficiency; it matches the known bounds for the simpler Mahalanobis setting.
Experimental Evaluation
The effectiveness of PBDL was evaluated using both synthetic datasets and real-world benchmarks from the UCI repository, including Iris, Balance Scale, Wine, and Transfusion datasets. The experiments focused on semi-supervised clustering and similarity ranking tasks.
Key Results
PBDL consistently outperformed established metric learning baselines such as Information-Theoretic Metric Learning (ITML) and Large Margin Nearest Neighbor (LMNN). On the UCI benchmarks, PBDL achieved top-tier performance in 14 out of 16 comparisons across metrics like Rand-Index, Purity, AUC, and Average Precision.
The results indicate that the Bregman structure provides a powerful inductive bias, especially for ranking tasks where PBDL often surpassed non-linear methods like Kernel NCA. Synthetic experiments further confirmed that while Mahalanobis methods fail to model non-quadratic divergences like KL, PBDL recovers them with high accuracy.
Conclusion
This paper presents a principled approach to learning non-linear distance measures by approximating Bregman divergences with piecewise linear functions. By combining the flexibility of max-affine parameterization with a convex optimization framework, PBDL achieves state-of-the-art performance on standard benchmarks while maintaining strong theoretical generalization guarantees. Future work includes scaling the method for larger datasets and integrating these Bregman-based distance measures into deep learning architectures.
Summary updated