# Learning to Approximate a Bregman Divergence

arXiv: https://arxiv.org/abs/1905.11545 · HTML: https://mlsanity.com/paper/1905.11545/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 3 of 3)

- [Faster Algorithms for Learning Convex Functions](https://mlsanity.com/paper/2111.01348/) (2021)
- [Max-affine regression via first-order methods](https://mlsanity.com/paper/2308.08070/) (2023)
- [Max-Linear Regression by Convex Programming](https://mlsanity.com/paper/2103.07020/) (2021)

## Abstract (arXiv)

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