Learning Bregman Divergences

Ali Siahkamari, Venkatesh Saligrama, David Castanon, Brian Kulis

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

Metric learning is the process of tailoring a distance function to a specific task using supervised data, such as relative comparisons. While most theoretical work focuses on learning Mahalanobis distances, these are strictly linear and may not capture the complexities of real-world data. Non-linear methods like deep metric learning offer expressivity but often lack rigorous statistical guarantees and require massive datasets. This paper bridges the gap by introducing a principled framework for learning arbitrary Bregman divergences from supervised data.

Methodology: Piecewise Bregman Divergence Learning (PBDL)

Bregman divergences are defined by a strictly convex generating function $\phi$. The authors propose parameterizing $\phi$ using max-affine functions, which are piecewise linear functions defined as the maximum of $K$ linear functions: $h(x) = \max_k (a_k^T x + b_k)$.

Visualization of max-affine approximation and resulting Bregman divergence surfaces.

A key contribution of this work is the proof that max-affine functions can accurately approximate not just the convex function itself, but also its gradient—a property essential for defining Bregman divergences. Using this parameterization, the metric learning problem is formulated as a convex optimization problem (specifically a Linear Program) that minimizes a hinge-like loss with Lipschitz regularization. This approach, termed Piecewise Bregman Divergence Learning (PBDL), avoids the local minima issues common in deep learning while maintaining high expressivity.

Theoretical Guarantees

Despite the increased complexity of searching the space of arbitrary piecewise-linear Bregman divergences, the authors prove that PBDL does not suffer a penalty in sample complexity. They establish a generalization error bound of $\mathcal{O}_p(m^{-1/2})$, where $m$ is the number of training points. This matches the known bounds for the strictly less general Mahalanobis metric learning, providing a strong theoretical foundation for the method.

Empirical Results

The authors evaluated PBDL against eight strong baselines, including Information Theoretic Metric Learning (ITML) and Large Margin Nearest Neighbors (LMNN), across several UCI benchmarks.

Performance comparison of PBDL against standard metric learning algorithms on UCI datasets.

PBDL achieved the best or second-best results in 22 out of 30 experimental comparisons across clustering, ranking, and classification tasks. For instance, on the Iris dataset, PBDL reached a 94.5% Rand-Index in clustering and a 96.5% AUC in ranking. Furthermore, synthetic experiments demonstrated that PBDL could successfully recover ground-truth non-linear divergences (like KL or LogDet) from noisy data, a task where standard Mahalanobis methods failed.

Conclusion and Future Work

PBDL offers a powerful middle ground between linear metric learning and deep non-linear methods. While it provides strong guarantees and empirical performance, it faces challenges in high-dimensional spaces where the number of required hyperplanes $K$ may grow exponentially. Future work involves scaling these methods using distributed optimization and exploring neural network parameterizations to further enhance expressivity in high-dimensional domains.

Summary updated

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.
BibTeX
@inproceedings{siahkamari2020learning,
  author = {Ali Siahkamari and Venkatesh Saligrama and David Castanon and Brian Kulis},
  title = {{Learning Bregman Divergences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=1PjyPEYesow},
}
Figure