Learning to approximate a Bregman divergence
Files
Date
2020
DOI
Authors
Siahkamari, Ali
Xia, Xide
Saligrama, Venkatesh
Castanon, David
Kulis, Brian
Version
Published version
OA Version
Citation
Ali Siahkamari, Xide Xia, Venkatesh Saligrama, David Casta nón, Brian Kulis. 2020. "Learning to Approximate a Bregman Divergence." Advances in Neural Information Processing Systems. https://papers.nips.cc/paper/2020/hash/24bcb4d0caa4120575bb45c8a156b651-Abstract.html
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 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.