Learning to Approximate a Bregman Divergence

Ali Siahkamari, Xide Xia, Venkatesh Saligrama, David A. Castañón, Brian Kulis

Introduction

Researchers from Boston University have developed a principled framework for learning non-linear distance measures known as Bregman divergences. By approximating a convex "generating function" with a piecewise linear (max-affine) model, they created an algorithm that outperforms traditional metric learning methods while maintaining the strong theoretical guarantees typically reserved for simpler linear models.

The Challenge of Metric Learning

In machine learning, defining how we measure the "distance" between two points is crucial for tasks like clustering, ranking, and similarity search. While standard Euclidean distance is common, many real-world problems require more complex, tailored measures.

Existing approaches generally fall into two camps:

  1. Linear (Mahalanobis) Methods: These are well-understood and have solid theoretical guarantees regarding sample complexity, but they are strictly limited to linear transformations of the data.
  2. Deep Metric Learning: These utilize neural networks to learn highly non-linear distances. While they perform exceptionally well, they often lack theoretical backing and require massive amounts of data.

This paper bridges the gap by targeting Bregman divergences—a broad family of distances that includes squared Euclidean distance and KL divergence. Because a Bregman divergence is defined by an underlying convex function, learning an arbitrary one from scratch is mathematically challenging.

Piecewise Bregman Divergence Learning (PBDL)

The authors introduce PBDL (Piecewise Bregman Divergence Learning). The core innovation is representing the complex, unknown convex function $\phi$ that generates the divergence as a max-affine function. This means the function is constructed by taking the maximum of several linear planes: $h(x) = \max_k (a_k^T x + b_k)$.

Geometric intuition of max-affine approximation and resulting divergences

Key technical steps include:

  • Parameterization: Instead of attempting to learn a smooth curve, the model learns a set of "hyperplanes" that hug the shape of the true convex function.
  • Optimization: The learning process is formulated as a Linear Program (LP). Given "triplet" supervision (e.g., "Point A should be closer to B than to C"), the algorithm adjusts the slopes and offsets of the planes to satisfy these constraints.
  • Theoretical Proofs: The authors prove that as more planes ($K$) are added, the approximation error drops at a rate of $O(K^{-1/d})$. Crucially, they demonstrate that the generalization error matches the $O(m^{-1/2})$ rate of much simpler linear models, offering a "best of both worlds" scenario: non-linear flexibility with rigorous mathematical backing.

Experimental Results

The authors evaluated PBDL on four standard UCI machine learning benchmarks (Iris, Balance Scale, Wine, and Transfusion) for clustering and ranking tasks. The method was compared against eight baselines, including popular techniques like ITML and LMNN.

Experimental results comparing PBDL to baseline metric learning algorithms
  • Consistent Top Performance: PBDL ranked 1st or 2nd in 14 out of 16 experimental comparisons across the datasets.
  • Significant Gains: On the "Balance Scale" dataset, PBDL achieved a Rand-Index (a clustering accuracy metric) of 84.4%, vastly outperforming the next best linear method (GMML at 72.9%) and standard Euclidean distance (59.3%).
  • Robustness in Ranking: The method showed particularly strong performance in ranking tasks (measured by AUC and Average Precision), indicating its effectiveness at capturing the relative neighborhood structure of the data.

Limitations and Future Directions

While powerful, the framework has limitations. The approximation bound includes a $1/d$ term (where $d$ is the number of features), meaning that as data becomes higher-dimensional, exponentially more planes ($K$) might be needed to maintain accuracy—a classic case of the "curse of dimensionality." Additionally, while Linear Programs are efficient, scaling to massive datasets might require specialized optimization techniques like ADMM.

Looking forward, the authors suggest this framework could be extended into "Deep Divergence Learning," using neural networks to learn feature representations before applying the Bregman framework, opening promising paths for complex image and text data.

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 Xide Xia and Venkatesh Saligrama and David A. Castañón and Brian Kulis},
  title = {{Learning to Approximate a Bregman Divergence}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=1PjyPEYesow},
}
Figure