Neural Bregman Divergences for Distance Learning
Authors: Fred Lu
Edward Raff
Francis Ferraro
Venue: ICLR 2023 poster (2023)
Keywords: metric learning
Bregman divergences
distance learning
embedding

Abstract: Many metric learning tasks, such as triplet learning, nearest neighbor retrieval, and visualization, are treated primarily as embedding tasks where the ultimate metric is some variant of the Euclidean distance (e.g., cosine or Mahalanobis), and the algorithm must learn to embed points into the pre-chosen space. The study of non-Euclidean geometries is often not explored, which we believe is due to a lack of tools for learning non-Euclidean measures of distance. Recent work has shown that Bregman divergences can be learned from data, opening a promising approach to learning asymmetric distances. We propose a new approach to learning arbitrary Bergman divergences in a differentiable manner via input convex neural networks and show that it overcomes significant limitations of previous works. We also demonstrate that our method more faithfully learns divergences over a set of both new and previously studied tasks, including asymmetric regression, ranking, and clustering. Our tests further extend to known asymmetric, but non-Bregman tasks, where our method still performs competitively despite misspecification, showing the general utility of our approach for asymmetric learning. 

Published as a conference paper at ICLR 2023
NEURAL BREGMAN DIVERGENCES FOR DISTANCE LEARNING
Fred Lu", Edward Raff", & Francis Ferraro'
University of Maryland. Baltimore County i Booz Allen Hamilton (lu fred, raff_ (edeeedwwdddaaa com, ferraro@umbc. edu
ABSTRACT
Many metric learning tasks, such as triplet learning, nearest neighbor retrieval, and visualization, are treated primarily as embedding tasks where the ultimate metric is some variant of the Euclidean distance (e.g., cosine or Mahalanobis), and the algorithm must learn to embed points into the pre-chosen space. The study of hon-Euclideal geometries is often not explored, which we believe is due to a lack of tools for learning non-Euclidean measures of distance. Recent work has shown that Bregman divergences can be learned from data, opening promising approach to learning asymmetric distances. We propose a new approach to learning arbitrary Bergman divergences in differentiable manner via input convex neural networks and show that it overcomes significant limitations of previous works. We also demonstrate that method more faithfully learns divergences new and previously studied tasks, including asymmetric regression, ranking, and clustering. Our tests further extend to known asymmetrie, but non-Bregman tasks, where our method still performs competitively despite misspecification, showing the general utility of our approach for asymmetric learning.
set of both
INTRODUCTION
Learning lask-relevant metric among samples common application machine learning, with use in retrieval, clustering, and ranking. A classic example of retrieval is in visual recognition where, given an object image, the system tries identify the class based on an existing labeled dataset. To do this, the model can learn measure of similarity between pairs of images, assigning small distances between images the same object type. Given the broad successes of deep learning, there has been recent surge of interest in deep metric learning-usiin neural networks to automatically learn these similarities (Hoffer & Ailon 2015
Huang et al. 2016 Zhang et al., 2020).
The traditional approach to deep metric learning learns an embedding function over the input space so that simple distance measure between pairs embeddings corresponds to task-relevant spatial relations between the inputs. The embedding function / is computed by a neural network, which is learned to encode those spatial relations. For example, we can use the basic Euclidean distance metric to measure the distance between two samples and y fx) [v) This distance is critical in two ways. First, it is used to define the loss functions, such as triplet or contrastive loss, to dictate how this distance should be used to capture task-relevant properties of the input space. Second, since f is trained to optimize the loss function, the distance influences the learned embedding f.
This approach has limitations. When the underlying reference distance is asymmetric or does not follow the triangle inequality, a standard metric cannot accurately capture the data. An important example is clustering over probability distributions, where the standard k-means approach with Euclidean distance is sub-optimal, leading to alternatives being used like the KL-divergence (Banerjee) al. 2005). Other cases include textual entailment and learning graph distances which disobey the triangl le inequality.
Recent work has shown interest in learning appropriate distance from the data instead of pre- determining the final metric between embeddings (Cilingir et al. 2020 Pitis et al. 2020 natural class of distances that include common measures such as the squared Euclidean distance the Bregman divergences (Bregman) [967). They are parametrized by a strictly convex function ø and measure the distance between points and y as the first-order Taylor approximation emro of the

---

Published as a conference paper at ICLR 2023
Method
Φ representation
Learning Approach
Complexity
Joint Learning
NBD
((x) = ICNN(x)
Gradient Descent
(10))
Yes
PBDL
(xx) = max, (b, x zi)
Linear Programming
O
No
Deep-div ((x) max, (b, + 2;)
Gradient Descent
O1AA + K)
Yes
Table I:
Comparison of our Bregman learning approach NBD with prior methods. NBD simultane- ously has better representational power and computational efficiency.
function originating from at xr. The current best approach in Bregman learning approximates using the maximum of affine hyperplanes (Siahkamari al. 2020 Cilingir et al., 2020p.
In this work we address significant limitations of previous approaches and present our solution, Neural Bregman Divergences (NBD). NBD is the first non max-affine approach learn a deep Bregman divergence, avoiding key limitations of prior works. We instead directly model the generating function 6(z), and then use (xx) to implement the full divergence Dg. To demonstrate efficacy, we leverage prior and propose several new benchmarks of asymmetry organized into three types of information they provide: 1) quality of learning a Bregman divergence directly, 2) ability to learn a Bregman divergence and feature extractor jointly, and 3) effectiveness in asymmetric tasks where the ground truth is known to be non-Bregman. This set of tests shows how NBD is far more efficacious in representing actual Bregman divergences than prior works, while simultaneously performing better in non- non-Brrgmann learning tasks.
The rest of our paper is organized as follows. In 2 we show how to implement NBD using an Input Convex Neural Network and compare to related work, with further related work in 3 In $ we demonstrate experiments where the underlying goal is learn known Bregman measure, and then to jointly learn Bregman measure with an embedding of the data from which the measure is computed. Then | studies the performance of our method on asymmetric tasks where the underlying metric is not Bregman, to show more general utility where prior Bregman methods fail. Finally we conclude in $6
NEURAL BREGMAN DIVERGENCE LEARNING
Bregman divergence computes the divergence between two points x and y from space X' by taking the first-order Taylor approximation of generating function ø. This generating function is defined over X' and can be thought of as (re-)em nee)eencdinng points from X. A proper and informative ø is incredibly important: different are defined. Our aim in this paper is to learn Bregman divergences by providing a neural method for learning informative functions á.
capture different properties of the spaces over which they
Definition 2.1.
Let x, E X, where X RR.. Given a continuously differentiable, strictly convex X R. the Bregman divergence parametrized by is
Da(g, y) = (xx) - d(y) - V
where ( represents the dot product and Vo(y) is the gradient of á evaluated at y-
properly defined & can capture critical, inherent properties of the underlying space. By learning via Eq. I we aim to automatically leam these properties. For example, Bregman divergences can capture asymmetrical relations: if X' is the D-dimensional simplex representing D-dimensional discrete probability distributions then d(x)
(ar, log yields the KI divergence, D2(2,, v) Ex log Za On the other hand, if X Rd and á is the squared L2 norm (Φ(y) llv, then
Va'
Da(r, y) = || - v1l.. Focusing on the hypothesis space of Bregman divergences is valuable due to the fact that many core machine learning measures, including squared Fuclidean, Kullback-Leiife and Ikura-Saito divergences, are special cases of Bregman divergences. While special cases of the Bregman divergence are used today, and many general results have been proven over the space of Bregman measures, less progress has been made in learning Bregman divergences.
2.1 EXISTING BREGMAN LEARNING A APPROACHES
PBDL. Recent works have proposed ways to empirically learn the Bregman divergence that best represents dataset by focusing max-affine representation of ø (Siahkamari al. 2020
2

---

Published as a conference paper at ICLR 2023
2022). Given set of K affine hyperplanes of the form by x + 24. the convex function & can be given lower-bound approximation as ((xx) max, (b, x + z,). Given a dataset of m distance constraints between pairs of samples (IIa xp) S D(Ia, In), the parameters {6,, {b;, can be learned using convex optimization to minimize an objective function, e.g. a variant of the triplet loss Ler Zp. kn) و==
t max(0, 1 + D(Fay Tp,) ( In₂) )} With some rewriting of the objective, the problem can be solved with techniques such as ADMM. We have modified some of the presentation for simplicity; refer to the original works for detail.
While effective smaller datasets at learning suitable divergence for ranking and clustering, this approach has limitations when scaling up to the dataset sizes used deep learning. It requires fixed set of triplets for training which limits the data size (whereas on-demand mining can generate (nz²) triplets). Even though ADMM can be distributed (and the 2-block ADMM from Siahkamari et al. (2022) is order of magnitude faster than the original), it does not scale well as batch gradient descent methods to large data. Morcover, it cannot be directly used for deep learning tasks, as we cannot simultaneously learn an embedding with the divergence.
Deep-diy, Following the max-affine approach, Cilingir et al. (2020) proposed the first deep learning approach to learn Ø, where the base neural network followed by layer of K max-affine components. Each max-affine component is a linear layer (or a shallow network), trained via backpropagation. Recall that 6(x) max; (b,- x zy) and let (x) b, x+ 2, for each i. To simplify the computation of do (z. v). they make use of the following property.
Fact 2.1.1. Let i and j be the corresponding max-affine components for Φ(x) and <ly)- Then the Bregman divergence between two points x and y is Dæ(x, v) x(()) ())))((()))))) (z(²).
Thus for a given I, y, the components i.j are updated by backpropagation. Observe that no matter how large K is, Φ is neither continuously differentiable nor strictly convex. As result, this structure not reliably learned using gradient descent. We provide an example to illustrate this, which is confirmed in our experiments (e.g. Table[4]
Example 2.2. Consider a Bregman regression problem learning D(x,, y) from known targets d and loss function [xx, y, d: Φ)= = (Dolæ, y) d)² The gradient with respect to each parameter b is
VoL(s, d: (6) 2(D (x. v) d) VoDa(z.))
For any max-affine slopes b, by. (z, y) are I and -r respectively, while the others are O. If we are also learning an embedding f fz)) then replace with fx) above, and furthermore for any embedding parameter 0, we have D DoDo
(b. bb) Vof(x).
From this we infer that when = j no learning occurs. Furthermore, if any max-affine hyperplane I is (nearly) dominated by the others over the domain of the inputs (that is, òπ(x) <. 6(x) for (almost) all 2), that component never (rarely) gets updated, resulting in essentially 'dead' components.
Another implication is that dı y) 0 for any 2, y located the same maximal component. By linearity there are at most K such regions, thus in classification or clustering with K classes the run- time of Deep-div is forced increase with K. Even so, this resolution is low for more fine-grained tasks such as regression unless K is very large. In practice, training this method on deep metric learning or regression shows issues which corroborate our analysis.
2.2 REPRESENTING Do VIA & DIRECTLY
Next we describe our new method, where we directly learn & with continuous convex neural network, which has a number of advantages over the piecewise approach. Whereas each pass of Deep-div requires an O OK) loop over the max-affine components, slowing training and inference, our approach does not incur additional complexity beyond an additional backpropagation step. Our approach is suited for both classification and regression tasks because gives much finer resolution to d. while max-affine approaches incur irreducible error when the target is smooth. This is further improved by selecting an activation function to make the learned strictly convex, continuously differentiable. unlike the max-affine approximation. Empirically, we demonstrate that our method converges consistently and more efficiently to lower error solutions.
To represent ó. adopt the Input Convex Neural Network (ICNN) (Amos et al. 2017). The ICNN composes linear layers with neg-negative weights W and affine functions with unconstrained weights U with convex non-decreasing activation functions g(-). The composition of these three
3

---

Published as a conference paper at ICLR 2023
components for the ith layer of an ICNN is given by Eq. (2. with 23 the i'th layer's input and 2;+1 the output,
2++1 9 (W,++ 2, U220 + b.).
By construction, the resulting neural network satisfies convexity, Chen et al. (011)) and Pitis et al. (2020) have shown under specific conditions that ICNNs universally approximate convex functions. Furthermore, with hidden layers. the representational power of an ICNN is exponentially greater than that of a max-affine function (Chen et al. (2019) Thm. 2), giving much finer resolution over Φ
Prior works on the ICNN have only tried piecewise linear activation functions such as the ReLU variants for g()) = max(æ; (z, 0); we instead use the Softplus activation g(z) log(1 + exp(z)) which lends the network smoothness and strict convexity. This is an important design choice as learning Vo(y) involves the second derivatives, which for any piecewise activation is zero. This causes vanishing gradients the (Vó(y), x 2) term, restricting the capacity to learn. We further discuss its representational capacity in
Efficient Computation. In order to backpropagate a loss through the Voly) term in I we use double backpropagation as in Drucker & Le Cun [1991. Normally computing the gradient of Vd(y) would involve constructing the Hessian, with a resultng quadratic increase in computation and memory use. Double hackpropagation uses automatic differentiation to efficiently compute gradients with respect to the inputs with the "Jacobian vector product" (Frostig et al. 2021), so that (Vo(y), x ---3 y) can be computed in the cost of evaluating d(y) one additional time. Since there are already three calls to ø, this is only a 25% increase in computational overhead to backpropagate through Eq. (T). provided we have learnable representation of Φ. This functionality has been implemented in the PyTorch API (Paszke et al. 2017). Furthermore, we can vectorize the Bregman divergence over a pairwise matrix, making our method significantly more computationally efficient than prior approaches. In particular, avoiding the O ((K) max-affine computation of Deep-div cuts our training time in half (Table K).
We show empirical timings, along with discussion, in Appendix A
2.3 JOINT TRAINING
The original feature space is rarely ideal for computing the distance measures between samples. Classical metric learning generally attempts to apply a linear transformation to the feature space in order to apply fixed distance function D)-,)) such as Euclidean distance (Jain et al. 2012 Kulis
et al. 2012). In deep metric learning, a neural network fo is used to embed the samples into a latent space where the distance function is more useful (Musgrave al. 2020). In our approach, instead of fixing the distance function, we also learn a Bregman divergence as the measure:
(s(f
((f(()) ((f( - (Vo(ū), fo(x) - fo()))
(3)
with V evaluated at ÿ = fv)).
Algorithm Neural Bregman Divergence (NBD). Given data pairs (a:, bi), our approach learns (1) fo to featurize 0g and b;: (2) Φ to compute a Bregman divergence value 9 between the featurized data points. The computed Bregman divergence is trained via loss function to be close to a larget divergence value y;- If target divergence value isn ' available, an implicit loss function can be used.
Note we now have two sets of param- eters to learn: those associated with and the encoder (0). During train- ing, they are simultaneously learned through gradient descent, which in- volves
as de- scribed earlier. We summarize this process in Alg. [] The metric model accepts two samples as input and es- timates the divergence between them. When the target divergence value is available, the metric can be trained using a regression loss function such as mean square error. Otherwise, an implicit comparison such as triplet or contrastive loss can be used.
Require: Dataset of pairs and target distance, Loss function
{( RR + E
1: fo + arbitrary neural network as a feature extractor
2: à < ICNN network parameterized by Eq. ?
3: for each data tuple (a,, b,) with label y; in dataset do Perform feature extraction
4:
x fo(a.)
5:
y + fo(b:)
6:
rhs t (Voly), 3)
Use double backprop > Empirical Bregman
7:
ÿ + x(x) - x(y) rhs
é (Ø. vt) backward()
& Compute gradients
9:
update parameters of Φ and 0
OTHER
10: return Jointly trained feature extractor fo and learned Bregman Divergence &
RELATED WORK
In classic metric learning methods, a linear or kernel transform the ambient feature space is used, combined with standard distance
4

---

Published as a conference paper at ICLR 2023
Exponential
Gaussian
Multinomial
Model
Purity
Rand Index
Purity
Rand Index
Purity
Rand Index
NBD
0.735 0.08
0.830 0.03
0.913 0.05
0.938 0.03
0.921 0.02
0.939 0.01
Deep-div
0.665 0.12
0.788 0.08
0.867 0.12
0.910 0.07
0.876 0.0s
0.919 0.04
Euclidean
0.365 0.02
0.615 0.02
0.782 0.11
0.869 0.05
0.846 0.09
0.900 0.05
Mahalanobis
0.452 0.05
0.697 0.02
0.908 0.06
0.935 0.03
0.894 0.06
0.926 0.03
PBDL
0.718 0.08 0.830 0.04 0.806 0.14 0.874 0.09 0.833 0.0s 0.895 0.04
Table 2: We cluster data generated from a mixture of exponential, Gaussian, and multinomial distributions. Learning the metric from data is superior to using standard metric such as Euclidean. Our approach NBD furthermore outperforms all other divergence learning methods. Means and standard deviations are reported over 10 runs.
function such as Euclidean or cosine distance. The linear case is equivalent to Mahalanobis distance learning. Information on such approaches are in (Xing et al. [202 Kulis et al.) 2012 Jain al.) 2012: Kulis et al., 2009). Bregman divergences generalize many standard distance measures and can further introduce useful properties such as asymmetry. They have classically been used in machine learning for clustering. by modifying the distance metric used in common algorithms such as kmeans (Banerjee al., 2005 Wu al., 2009). One of the first methods to learn a Bregman divergence fits a non-parametric kernel to give local Mahalanobis metric. The coefficients for the data points are fitted using subgradient descent [Wu et al. 2009). We described the more recent approaches earlier.
Recently Pitis et al. (2020) approached asymmetric distance learning by fitting a norm N with modified neural networks which satisfy norm properties and using the induced distance metric N(x y)- They introduce two versions that we include as haselines: one (Deepnorm) parametrizes N with a modified ICNN that satisfies properties such as non-negativity and subadditivity. The second (Widenorm) computes a nonlinear transformation of a set of Mahalanobis norms. By construction, these metries allow for asymmetry but still satisfy the triangle inequality. On the other hand, the Bregman divergence does not necessarily obey the triangle inequality. This is appealing for situations
where the triangle inequality may be too restrictive.
Datasct
Model
MAP
AUC
Purity
Rand
BREGMAN EXPERIMENTS
Deep-div
0.281
0.645
0.377
0.660
We conduct several experiments that validate our approach as an effective means of learn- ing divergences across a number of tasks. Over 44 comparisons, NBD outperforms prior Breg- man learning approaches in all bui three. In the first section $4. we demonstrate that NBD effectively learns slandard Bregmun reirieval and clustering benchmarks, outperforming the previous Bregman methods PBDL and Deep- div. In addition, we construct a Bregman regres- sion task in 44.2 where the labels are known divergences over raw feature vectors, so that the only learning lask is that of the divergence it- self. Finally in $4.3) we investigate the ability of our method learn the ground truth diver- gence while simultaneously learning to extract needed representation, training a sub-network's parameters 0 and our divergence & jointly. This is typified by the "BregMNIST" benchmark, which combines learning the MNIST digits with the only supervisory signal being the ground truth divergence between the digit values. Refer to the Appendix for detailed training protocols and data generation procedures.
Euclidean
0.301
0.666
0.422
0.750
abalone
Mahalanobis
0.310
0.677
0.419
0.750
NBD
0.316
0.682
0.432
0.750
PBDL
0.307
0.659
0.386
0.735
Decp-div
0.804
0.859
0.869
0.828
Faclidean
0.611
0.666
0.633
0.568
balance scale
Mahalanobis
0.822
0.834
0.851
0.761
NBD
0.887
0.915
0.898
0.872
PBDI.
0.836
0.855
0.872
0.814
Decp-div
0.787
0.757
0.852
0.750
Faclidean
0.681
0.589
0.704
0.523
car
Mahalanobis
0.787
0.752
0.778
0.654
NED
0.820
0.803
0.860
0.758
PRDL.
0.798
0.775
0.854
0.750
Decp-div
0.945
0.967
0.811
0.820
Euclidean
0.827
0.897
0.820
0.828
iris
Mahalanobis
0.946
0.973
0.884
0.879
NED 0.957
0.977
0.909
0.902
PBDL 0.943
0.967
0.889
0.888
Table 3: On real datasets, learned Bregman di- vergences outperform Euclidean Mahalanobis metrics for downstream ranking (MAP, AUC) and clustering (Purity, Rand Index). NBD beats prior Bregman learning approaches on most datasets. See Appendix Table[o for standard deviations and more datasets.
5

---

Published as a conference paper at ICLR 2023
4.1 BREGMAN RANKING AND CLUSTERING
Our first task expands the distributional clustering experiments in Banerjee et al. (000);; Cilingir et al. (2020). The datasets consist of mixtures of N 1000 points in T from five clusters, where the multivariate distribution given cluster identity is non-isotropic Gaussian, exponential, or multinomial. Given a distance metrie, we apply generalized k-means algorithm to cluster the data points. While standard metrics, such as L2-distance and KL-divergence, may be ideal for specific forms of data (c.g. isotropic Gaussian and simplex data, respectively), our goal is to learn an appropriate metric uniquely
directly from separate labeled training set. In particular, because Bregman divergences associated with each member of the exponential family (Banerjee et al.] (005), our method is especially suited for clustering data from a wide range of distributions which may not be known ahead of time. To learn the metric from data, we apply triplet mining, including all triplets with non-zero loss (Hoffer & Ailon
2013). We use the same method train all models except for the Euclidean baseline, which requires no training, and PBDL where we directly use the authors' code.
As shown in Table 2 our method NBD gives improved clustering over all distributions compared to all baselines. In particular, standard k-means with Euclidean distance is clearly inadequate. While the Mahalanobis baseline shows significant improvement, it is only comparable to NBD in the Gaussian case, where matrix can be learned to scale the clusters to be isotropic. This task indicates the importance of learning flexible divergences from data.
After demonstrating success distributional clustering, we now apply our method to ranking and clustering real data (Table as first shown in Siahkamari et al. (2020). For the ranking tasks, the test set is treated as queries for which the learned model retrieves items from the training set in order of increasing divergence. The ranking is scored using mean average precision (MAP) and area under ROC curve (AUC). Our method again outperforms the other Bregman learning methods in the large majority of datasets and metries. We emphasize that these are standard experiments from recent work, on which our method proves superior.
4.2
DIVERGENCE REGRESSION
Truth
Euclidean
Mahalanobis
Ir log x
KL
Correlation
None
Med
High
None
Med
High
None
Med
High
None
Med
High
NBD
0.17
0.15
0.16
0.16
0.18
0.20
0.52
0.54
0.57
0.19
0.19
0.19
Deep-div
7.78
7.81
7.84
17.92
12.26
14.15
2.59
2.67
2.70
0.44
0.50
0.51
Deepnorm
3.56
3.97
4.15
7.70
5.97
7.66
1.59
1.74
1.79
0.30
0.28
0.28
Widenorm
3.56
3,99
4.12
7.73
6.01
7.60
1.49
1.48
1.48
0.30
0.28
0.28
Mahalanobis
0.00
0.03
0.05
0.02
0.04
0.09
1.45
1.67
1.72
0.23
0.22
0.22
Table 4: Regression test MAE when unused distractor features are correlated (None/Med/High) with the true/used features. Best results in bold, second best italics. NBD performs best on asymmetric regression, and second-best to Mahalanobis symmetric regression, where a Mahalanobis distance is expected to fit perfectly.
As confirmation that our method can faithfully represent Bregman divergences, we use simulated data to demonstrate that our method efficiently learns divergences between pairs of inputs. We generate pairs of 20-dim. vectors from Normal distribution, with 10 informative features used to compute the target divergence and 10 distractors. To be more challenging and realistic, we add various levels of correlations among all features to make the informative features harder separate.
The following target divergences used: (1) squared Euclidean distance (symmetric); (2) squared Mahalanobis distance (symmetric); (3) Φ(x) = x: log x (asymmetric); (4) KL-divergence (asym- metric). In this task we compare our NBD with Deep-div and Mahalanobis, but we did not find regression option for PBDL. in the authors' code. Instead we add Deepnorm and Widenorm metrics from Pitis al. 2 as alternative baselines which do not learn Bregman divergences.
The results of these experiments are in Table 4 with loss curves shown in Appendix Fig. In the symmetric cases of the Euclidean and Mahalanobis ground-truth, our NBD method pertorms nearly as well using a Mahalanobis distance itself. This shows that method is not losing any representational capacity in being able to represent these standard measures. This is notably not true for the prior approaches for asymmetric learning: Deepnorm, Widenorm, and Deep-div.

---

Published as a conference paper at ICLR 2023
10
NBD
Doep-div
Deapocem
Widenemm
10
20
40
20
40
Figure 2: MSE (y-axis) after epochs of training (X-axis) asymmetric BregMNIST (left) and BregCIFAR (right) with true d(x) = x log x. NBD performs best both tasks.
Notably, unlike in the clustering tasks, the piecewise representation of Φ in Deep-div is unable to accurately represent Bregman regression targets, discussed earlier in $2.1 In Fig. |4c and Fig. 4d two asymmetric divergences are used, and our NBD approach performs hetter than all existing options. Because these experiments isolate purely the issue of learning the divergence itself, have strong evidence that our approach is the most faithful to learning known divergence from supervisory signal. Note that the Mahalanobis distance performed second best under all noise levels, meaning the prior asymmetric methods were in fact less accurate at learning asymmetric measures than purely symmetric model.
4.3
CO-LEARNING AN EMBEDDING WITH A DIVERGENCE
Having shown that our method outperforms the prior Bregman learning approaches on shallow clustering, classification, and regression, we introduce more challenging task, BregMNIST, where neural embedding must be learned along with the divergence metric. The dataset consists of paired MNIST images, with the target distance being Bregman divergence between the digits shown in the images. Example pairs are displayed in Fig. [ foor the asymmetrical Bregman divergence parametrized by (xx) = (x: + log(æ 1).
We also make a harder version by substitut- ing MNIST with CIFARIO with the same di- vergence labels. In both cases the relation of features to class label arbitrary (that is, we impose ordinal relation among labels that does not exist in the data), meaning that the embedding function must learn to effectively map image classes to the correct number used to compute the divergence, while the metrie head must also learn to compute the target Breg- man divergence. The results of the experiments (Fig. 12p mirror our results in $4.2] For both BregMNIST and BregCIFAR NED performs best, while prior methods of learning asym- metric measures perform worse than the Maha- lanobis distance.
f(Jwao
CNN
CNN
3
5
D(a
4log ( -14-2 (4-6)
so 0.378
Figure 1: Demonstration of the BregMNIST task. Nodes with the same color indicate weight shar- ing. Each image is embedded by a CNN, and the ground-truth divergence is computed from the digit values of the input images. The embeddings of each image given NBD, and the loss puted from NBD's output and the true divergence. The CNN and NBD are learned jointly.
NON-BREGMAN LEARNING
We have shown that our NBD method is the most effective among available options when the underlying ground-truth is from the class of Bregman divergences. In this section we will now explore the effectiveness our approach on tasks that are known to be non-Euclidean, but not necessarily representable by Bregman divergence. The purpose of these experiments is to show that NBD does not depend on the underlying representation being a proper divergence order to still be reasonably effective, and that it is still more effective then the prior Deep-div approach Bregman learning. This also of practical relevance to applications: just as the Euclidean metric was used for convenient properties and simplicity, without belief that the underlying system truly Euclidean, NBD)
7

---

Published as a conference paper at ICLR 2023
may be valuable for developing more flexible methods that inherit the mathematical convenience of Bregman divergences. These tasks probe the efficacy of the closest Bregman approximation of the underlying divergence, expect that method will not surpass SOTA when the task is sufficiently non-Bregman.
CIFARIO
STL10
SVHN
5.1 DEEP METRIC LEARNING
We extend the ranking experiments from $4.1 and the architecture of Fig. [ to the deep metric learning setting where embedding is learned alongside the divergence. We use a ResNet-Ie 18 the base feature extractor and apply batch triplet mining to learn Eq. 3 by minimizing the triplet loss.
NBD
95.6
95.0
96.9
Deep-div
93.3
92.3
96.0
Deepnorm
95.0
95.0
96.9
Widenorm
95.6
95.1
96.9
Euclidean 95.0
95.0
96.9
Table 5: MAP@@ 10 on deep metric learning, replac- ing the standard Euclidean distance with metric co-learned with the embedding.
Most metrics perform comparably in this exper- iment, although Deep-div is consistently outper- formed by the others. We observed that Deep-div has higher variance, and depending the ini- tialization could learn well or not at all. This may be due to "dead" affine components discussed earlier. Fixing the Euclidean distance still appears effective learning the final metric here. We hypothesize this is because the embedding space of image datasets is well-behaved enough for standard distance accurately cluster images. In the following experiments will investigate tasks where, even after applying an arbitrary feature extractor, a standard distance measure is no longer sufficient.
5.2 APPROXIMATE SEMANTIC DISTANCE
The next task involves learning symmetric distances that do not follow the triangle inequality. We group the CIFARI0 classes into two categories: man-made and natural. Within each category select an arbitrary exemplar class (car and deer in our experiment). We then assign proxy distances between classes reflect semantic similarity: 0.5 within the same class, 2 between any non-exemplar class and its category exemplar, and 8 between non-exemplar classes within category. Pairs from different categories are compared. Besides disobeying the triangle inequality, the distance values do not reflect a known divergence and can be changed.
Metric NBD
Same
Unseen
Like BregCIFAR, we present pairs of images to the model, which simultaneously adjusts neural embedding and learn divergence function such that inter-class distances in the em- bedding space match the target values. This task is harder than the previous ones because it is not sufficient to learn a separable embedding for each class; the embeddings must additionally be arranged appropriately in a -un-Euclidean space. The results in Table (jindictte our method effectively learns distances that do not follow the triangle inequality. The Deep-div approach does second-bess best here due to the small space of valid outputs. The other approaches by limitation adhere the triangle inequality and do not perform as well.
0.04
3.52
Deep-div
0.10
4.13
Deepnorm
1.23
4.18
Widenorm
1.39
4.50
Mahalanobis
2.00
4.56
Table 6: MSE for CIFARIO cate- gory semantic distance after 200 epochs. Our NBD performs the best on seen and unseen images.
5.3
OVERLAP DISTANCE
0.3
Deepnorm
The overlap distance task presents pairs of the same image or different images, but with differ- ent crops taken out. A horizontal and vertical cut are chosen uniformly at random from each image. When the crops are based on the same image, the asymmetrical divergence measure be- tween images X and Y is the percent intersec- tion area: D(X, Y) =
lest lest MSE
Widerorm
0.2
Depp-die
Mahalanobis
0.1
XnnY Otherwise
20
40
60
80
100
|Xi
the divergence 1. We use the INRIA Holidays dataset (see Appendix G). The results be found in Fig. 3 where we see NBD performs the second best of all options.
Figure 3: MSE (y-axis) for predicting the overlap
D(X, Y) between two image embeddings learned jointly with the underlying CNN.
8

---

Published as a conference paper at ICLR 2023
3d
3dd
octagon
taxi
traffic
Method
Train
Test
Train
Test
Train
Test
Train
Test
Train
Test
NBD
4.34
33.49
19.91
337.59
4.67
25.32
3.11
66.27
2.53
12.03
Deepuorm
4.97
22.44
34.40
275.99
4.81
15.19
1.52
20.31
1.76
5.27
Mahalanobis
4.45
30.90
24.99
267.18
6.82
44.30
1.31
18.32
1.47
5.60
Deep-div
695.97
930.57
589.13
806.14
879.94
1046.08
489.80
625.16
399.14
618.94
Widenorm
4.49
27.92
25.76
253.65
5.17
23.46
1.18
16.20
1.44
5.21
Bregman-sqrt
5.94
27.59
27.70
266.25
8.62
40.18
1.57
19.02
1.63
5.23
Bregman-GS 4,50
30.51
23.78
266.91
7.26
43.13
1.17
16.71
1.55
5.49
Table 7: Results of estimattnn distances the shortest-path task. Triangle-inequalin preserving deep and wide-norm are expected to perform best. Our NBD performs significantly better than previous Bregman learning approach Deep-div, and can be competitive with the trangle-inequalle preserving methods. The gap between train and test loss shows the impact of triangle inequality helping to avoid over-fitting the observed sub-graph used for training. Dataset and experiment details in Appendix.
We observe that Widenorm performs better on this task, especially during the initial learning process, due to the fact that it is permitted violate the positive definiteness property of norms: (ar, O. Thus the method learns to map a difference of zero between embeddings to some intermediate distance with lower MSE. This can be problematic in use cases where the definiteness important.
5.4 SHORTEST PATH LENGTH
Our final task involves estimating the shortest path graph from one embedded node to another based on their distances to and from set of landmark nodes. This task inherently favors the Widenorm and Deepnorm methods because they maintain the triangle inequality (i.e., no shortcuts allowed in shortest path), and so are expected to perform better than NBD. We reproduce the experimental setup of Pitis et al. (2020) closely with details in Appendix
The results for each method are shown in $5.4 which largely match expectations. The triangle- inequality preserving measures usually perform best, given the nature of the problem: any violation of the triangle inequality means the distance measure is "taking a shortcut" through the graph search space, and thus must be under-estimating the true distance to the target node. NBD and Deep-div, by being restricted the space of Bregman divergences, have no constraint that prevents violating the and thus often under-estimate the true distances. Comparing the train and test losses help to further assess this behavior, as the training pairs can be overfit to an extent. We see that NBD effectively learns the asymmetric relationships between seen points despite underestimating the distance to new points.
To further explore the degree to which the properties underlying Bregman divergences affect shortest path length learning. introduce two extensions NBD. The first is soft modification encouraging the triangle incquality to be obeyed (Bregman-sqrll The second has a hard constraint guaranteeing the triangle inequality (Bregman-Gre GS) and is defined as D (z, y) (r( y) + D (v,, x) + ållc
v1l3 + 1 (z()) Vo(v)l (Acharyya al. 2013). Results included in $5.4. with detail on the extensions in the Appendix. There Is an inherent tradeoff between the two extensions as Bregman- sqrt can be asymmetric but still does not require satisfying the triangle inequality, while Bregman-GS is symmetric but always satisfies the triangle inequality. We see that these two modifications to NBD are highly competitive with Deepnorm and Widenorm. Furthermore, the relative performance of each provides an indication of whether asymmetry or triangle inequality is more crucial to modeling given dataset. These methods highlight that even when a given task is highly non- non-Bregne Bregman, NBD can be readily extended to relax or strengthen various assumptions to better model the data.
6 CONCLUSION
To enable future asymmetric modeling research, we have developed the Neural Bregman Divergence (NBD). NBD jointly learns a Bregman measure and a feature extracting neural network. We show that NBD learns divergences directly indirectly when trained jointly with network, and that NBD still learns effectively when the underlying metric is not a divergence, allowing effective use of our tool across wide spectrum but retaining the nice properties of Bregman divergences.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their comments, questions, and suggestions. This material is based in part upon work supported by the National Science Foundation under Grant No. IIS-2024878, with some computation provided by the UMBC HPCF, supported by the National Science Foundation under Grant No. CNS-1920079. This material is also based on research that is in part supported by the Army Research Laboratory, Grant No. W91 NNIIN2220000 and by the Air Force Research Laboratory (AFRL). DARPA, for the KAIROS program under agreement number The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either express or implied, the Air Force Research Laboratory (AFRL), DARPA, or the U.S. Government.
PA8750-19-2-11
REFERENCES
Sreangsu Acharyya, Arindam Banerjee, and Daniel Boley. Bregman divergences and triangle inequality. ICDM, pp. 476-484, 2013.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In ICML, 2017.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with bregman divergences. Journal of machine learning research, 6(10), 2005.
L.M. Bregman. The relaxation method finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-217, jan 1967. ISSN 00415553. doi: (.100660041-5553366)) 90040-7.
Benjamin Charlier, Jean Feydy, Joan Alexis Glaunès, François-David Collin, and Ghislain Durif. Kernel operations on the gpu, with autodiff, without memory overflows. Journal of Machine Learning Research, 22((4): 2021.
Pengwen Chen, Yunmei Chen, Murali Rao, et al. Metrics defined by bregman divergences. Commu- nications in Mathematical Sciences, 6(4):915-926, 2008
Yize Chen, Yuanyuan Shi, and Baosen Zhang. Optimal control via neural networks: A convex approach. In ICIR, 2019.
Hatice Kubra Cilingir, Rachel Manzelli, and Brian Kulis. Deep divergence learning. In ICML, 2020.
Harris Drucker and Y. Le Cun. Double backpropagation increasing generalization performance. In IJCNN, pp. 145-150. IEEE, 1991. ISBN 0-7803-0164-1. doi: 10. 1119/IICCN..991115553333.3.
Roy Frostig, Matthew Johnson, Dougal Maclaurin, Adam Paszke, and Alexey Radul. Decomposing reverse-mode automatic differentiation. In POPI., 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International workshop on similarity-base based pattern recognition, pp. 92. Springer, 2015.
Chen Huang, Chen Change Loy, and Xiaoou Tang. Local similarity-awer deep feature embedding. In NeurIPS, 2016.
Prateek Jain, Brian Kulis, Jason V Davis, and Inderjit S Dhillon. Metric and kemell learning using a linear transformation. The Journal of Machine Learning Research, 13:519-547, 2012.
Hervé Jegou, Douze Matthijs, and Cordelia Schmid. Hamming embedding and weak geometry consistency for large scale image search-extended version-. 2008.
Brian Kulis, Mátyás A Sustik, and Inderjit S Dhillon. Low-rank kernel learning with bregman matrix divergences. Journal of Machine Learning Research, 10(2), 2009.
10

---

Published as a conference paper at ICLR 2023
Brian Kulis et al. Metric learning: A survey. Foundations and trends in machine learning, 5(4): 287-364, 2012.
Kevin Musgrave, Serge Belongie, and Ser-Nam Lim. A metric learning reality check. In ECCV, 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Silviu Pitis, Harris Chan, Kiarash Jamali, and Jimmy Ba. An inductive bias for distances: Neural nets that respect the triangle inequality. arXiv preprint arXiv:2002.05825, 2020.
Ali Siahkamari, Xide Xia, Venkatesh Saligrama, David Castañón, and Brian Kulis. Learning to approximate bregman divergence. In NewrIPS, volume 33, pp. 3603-3612, 2020.
Ali Siahkamari, Durmus Alp Emre Acar, Christopher Liao, Kelly L Geyer, Venkatesh Saligrama, and Brian Kulis. Faster algorithms for learning convex functions. In International Conference on Machine Learning, pp. 20176-20194. PMLR, 2022.
Lei Wu, Rong Jin, Steven CH Hoi, Jianke Zhu, and Nenghai Yu. Learning bregman distance functions and its application for supervisd clustering. In NeurlPS, 2009.
Eric P Xing, Andrew Y Ng, Michael Jordan, and Stuart Russell. Distance metric learning with application to clustering with side-information. In NeurIPS, volume 15, pp. 12. Citeseer, 2002.
Dingyi Zhang. Yingming Li, and Zhongfei Zhang, Deep metric learning with spherical embedding.
In NeurlPS, 2020.

---

Published as a conference paper at ICLR 2023
A COMPUTATIONAL DISCUSSION
We measure timing information of NBD as well as the benchmarks used in our experiments for divergence learning task in $4.2 The training time (forward and backward passes), inference time (forward pass), and pairwise distance matrix computation are collected. While the pairwise distance not directly used in our experiments, is commonly computed metric learning applications such as clustering and classification. The data dimension size N x D used here is characteristic of the size of many metric learning experiments, where the x N pairwise distance matrix can be stored on GPU memory, but the N x N x D tensor with embedding dimension D does not fit: the fast but naive approach of flattening the matrix and passing as a N x N -lennghh batch does not work.
The Mahalanobis method is naturally the fastest method and serves reasonable runtime lower bound. This is because the distance can be expressed a simple composition of a norm with linear layer. The squared Euclidean norm be simplified as ( y) ||==1] [ + l1vll3 2(x,, y), which can be efficiently computed. We can similarly compute the Bregman divergences. For example, the squared Euclidean distance equivalently written (ar, y) |>:|| l (2y, x v). which is its Bregman divergence formulation. Though not necessary for our current experiments, the pairwise distances for larger batch sizes for the Mahalanobis and NBD be readily implemented in PyKeOps Charlier et al. (2021). Thus the longer computational time for NBD can likely be attributed the increased cost of double backpropagation and the convex metric architecture.
Method
Training
Inference
Pairwise distance
NBD
0.73 (0.08)
0.10 (0.03)
0.52 (0.06)
Deep-div
1.63 (0.11)
0.12 (0.02)
0.59 (0.03)
Deepnorm
0.81 (0.07)
0.09 (0.02)
4.53 (0.03)
Widenorm
0.52 (0.04)
0.08 (0.02)
2.61 (0.03)
Mahalanobis
0.46 (0.03)
0.08 (0.02)
0.40 (0.03)
Table 8: Timing information for a divergence learning task as in $42 with embedding dimension 20 and batch size of 1000, comparing the methods used in our experiments. We compute the per-epoch training time (forward and backward passes), inference time (forward pass), and pairwise distance matrix computation. Results averaged over 30 runs, with standard deviation in parentheses.
On the other hand, the Deepnorm cannot be vectorized in such manner, so pairwise distances need to be computed on the order of O(N2) runtime, for example by further splitting the tensor into smaller mini-batches. While the Widenorm is composed of Mahalanobis metrics (set to 32 in experiments) that can be vectorized, in our experiments the memory requirement was still too high, also requiring looping over sub-batches. We use sub-batch size 200 in this analysis. We note that the loop can be alternatively performed over the Mahalanobis components in Widenorm, but this would still be slower than the standard Mahalanobis and NBD methods. Finally, the Deep-div method efficiently computes pairwise distances, but its forward pass requires the input to be passed through a of K affine sub-networks via looping, increasing the computational time.
12

---

Published as a conference paper at ICLR 2023
B
FIGURES FOR BREGMAN REGRESSION TASK
130
(a) Euclidean target
(b) Mahalanobis target
log
target
(d) KL-div. target
Figure 4: Results when vectors with 10 real features and 10 distractor features are used to compute different specific Bregman divergences. Mean absolute error is on the y-axis and number of training epochs on the x-axis. The shaded region around each plot shows the standard deviation of the results. Note in all cases our NBD has very low variance while effectively learning the target divergence.
13

---

Published as a conference paper at ICLR 2023
C DATA GENERATION DETAILS
Distributional clustering. We sample 1000 points uniformly into 5 clusters, each with 10 feature dimensions. To generate non-isotropic Gaussians we sample means uniformly in the hyper-box within [-4, 4] for each coordinate. The variances are random PSD matrix (scikit-learn make_ mat_ri) added with o²I where o² = 5. The reason for these values are because we aimed to have each mixture task be similarly difficult (clusters not perfectly separable but also not too challenging). For the multinomial task, we sampled 100 counts into the 10 feature dimensions. Each cluster's underlying probability distribution was sampled from Dirichle((110, 10, .., 10)). Finally, the exponential case are iid samples for each feature. The underlying cluster rates are sampled uniformly between [0.1, 10].
Regression noise features. To add correlation among features (both informative and distractors), we generate covariance matrices with controlled condition number K while keeping the marginal distributions of each feature x2 (0, 1). For the medium correlation task K < 100, while for high correlation x is between 250 and 500.
50000 pairs were generated with 20 features.
D EXPERIMENTAL PROCEDURE
Overview. Our experiments fall into two categories: regression (e.g. sections 4.2, 4.3, 5.3, 5.4) and clustering/ranking (e.g. sections 4.1, 5.1). For the first category a scalar divergence target is assumed. Square error loss used, and input pair of samples is drawn from underlying dataset or randomly generated. From the input pair, the true divergence target is computed. For example the dataset has N samples, there are ((N2) possible pairs. Pairs are drawn simultancously as batches with specified batch size, and an epoch (unless otherwise stated) is defined as the number of pairs equal to the size of the original dataset (so an epoch is the usual length, but not all data has necessarily been seen).
For the second category, a divergence target does not exist, only the relative ranking of anchor-positive being less distance than anchor-negative The triplet loss is used here. In all such metric learning tasks, we fit models using triplct mining, with margin 0.2, and Adam optimizer. All triplets with non-zero loss are mined from a batch. For more detail on triplet loss and mining see Musgrave al. (2020). Thus for batch size of B there are up to O(B3) triplets. We iterate over the dataset in batches. The exception is PBDL which uses the authors' original code with pre- mreggeneateed tuples.
Distributional clustering. We used batch size 128, 200 epochs, le-3 learning rate for all models. Here, and in all subsequent experiments, to train PBDL. we used the authors' provided Python code, which uses the alternating direction method of multipliers (ADMM) technique. (They also provide Matlab code using Gurobi.)
Bregman ranking. Since Deep-div and NBD are deep learning approaches, we use Adam to optimize this problem instead of convex optimization solvers. To ensure convergence, tune the learning rate and number of epochs using gridsearch over a validation set separated from the training data, We do the same for the Mahalanobis approach. A typical example of the parameters is batch size 256, 250 epochs, learning rate lc-3.
Regression. We used 100 epochs of training with learning rate Ie-3, batch size 1000.
Deep regression experiments. For the remaining experiments which involve co-learning an embed- ding, we use default hyperparameter settings to keep methods comparable, such as Adam optimizer, learning rate 1e-3, batch size 128, embedding dimension 128, and 200 epochs. By deep regression, we refer to tasks that have a continuous target, such as BregMNIST, overlap distance, and shortest path.
For the MNIST/CIFAR tasks the embedding network consists of two/four convolutional layers respectively followed by two fully-connected layers (more specific details follow). the semantic distance CIFAR task, we used a pretrained ResNet20 as the embedding without freezing any layers for faster learning He et al. (2066). Results were robust to the embedding model chosen.
We replicated each training and reported means and standard deviations. For the Bregman benchmark tasks trained 20x, while for the deep learning/graph learning tasks we trained 5x. Learning curves
14

---

Published as a conference paper at ICLR 2023
Dainset
Asymmetric
Dimension
Edge weights
Details
3d
No
50x50x50 cubic grid 25x25x25x25 (two objects on 2d grid)
uniform (0.01.0.02..
1.00)
edges wrap around no wrap
taxi
No
uniform (0.01.0.02.... 1.00)
only one edge in each dimension available
3dd
50x50x50 cubic grid
uniform {0.01, 0.02.........................0.. 1,000
forward and reverse sampled from Normal with mean from uniform (0.01. 0.02, .... 1.000
traffic
Yes
100x 100 grid
wrap
forward and reverse sampled from Normal
octagon
Yes
100x100 2d grid. diagonals connected
with mean from uniform (0.01, 0.02,.... ........................ 1.003
wrap
Table 9: Details of the shortest-pale paiteestt-pthhhee datasets, the number of dimensions in the graph, and how the edge weights the graph are computed. These tasks were originally proposed by Pitis et al. (2020) and favor asymmetric methods that maintain the triangle inequality.
in the figures show mean and 95% confidence interval for the loss over each epoch. We used Quadro RTX 6000 GPUs to train our models.
Deep metric learning. Finally, this refers to the triplet loss experiment with co-learning of embedding and metric. For this we use the following settings: learning rate le-4, Adam optimizer, batch size 64, embedding dimension 32, 30 epochs. For all datasets that are 32x32, we resized to 224x224 and used a pretrained ResNet18 as the base embedding model, which is then finetuned during training. We used smaller learning rate and embedding/batch dimensions in keeping with the standard metric learning protocol in Musgrave et al. (2020) which we found gave more stable results.
We note that in Cilingir et al. (2220) they ran their Deep-div
similar task and reported some results better and some worse than our results with Deep-div. We note that there are differences in protocol, where they extensively tuned the training procedure with hyperparmater optimization, whereas we selected default values to ensure robustness. However, we used a larger base extractor with pretrained weights whereas they used custom CNN. As result differences in performance can be expected. While our reported metric is MAP@ 10 and theirs was nearest neighbor accuracy, we found both measures be very close across our experiments.
E SHORTEST PATH DETAILS
Pitis et al. (020)) introduced learning shortest path length in graphs as a task. The problem consists of learning d(æ;, y) where x, y E V are pair of nodes in large weighted graph G (V,E). For each node, the predictive features consist of shortest distances from the node to a set of 32 landmark nodes (and vice versa for asymmetric graphs). As this task requires predicting the distance from one node to another, maintaining the triangle inequality has inherent advantages and is the correct inductive bias for the task. We still find the task useful to elucidate the difference between NBD and the prior Deep-div.
We reproduce the experimental setup of Pitis et al. 2020) closely, collecting 150K random subset of pairs from the graph as the dataset, with true distances computed using A" search. While the original work normalized distances to mean 50, found that such large regression outputs were difficult to learn. Instead we normalize to mean 1, which results in faster convergence of all methods. A 50K/10K train-test split was used. The features are standardized with added noise sampled from NN 0.2), and 96 normal- -distributed distractor features were included. For additional details refer to Appendix E of Pitis et al. (2020). However, their experimental detail and code was sufficient to only reproduce three of the graph datasets (3d, taxi, 3dd). Therefore, we develop two additional asymmetric graphs (traffic and octagon). The details of all the shortest-patll graphs we use are provided in Table Models were trained for 50 epochs at learning rate 5e-5 and 50 epochs at 5e-6.
E.1 EXTENSIONS OF BREGMAN DIVERGENCE FOR THE TRIANGLE INEQUALITY
For the first we draw from mathematical literature demonstrating that metrics can be induced from the square root of certain symmetrized Bregman divergences, depending on constraints on & Chen et al. 2008). We learn the square root of the Bregman divergence to provide a soft inductive bias (as an illustrative example, Euclidean distance is metric but squared Fuclidean distance not).
For the second we introduce a modification of the Bregman divergence known as the Generalized Symmetrized Bregman divergence. As shown by Acharyya et al. (2013), the square root of such
15

---

Published as a conference paper at ICLR 2023
divergence is guaranteed to satisfy the triangle inequality. This divergence is defined (z v) Do(y, .) + 211 ul [ - vé(v)ll
(x.y) (
There is inherent tradeoff between the two extensions Bregman-sqrt can be asymmetric but still does not require satisfying the triangle inequality, while Bregman-GS is symmetric but always satisfies the triangle inequality.
F ADDITIONAL HYPERPARAMETER DETAILS
We followed the hyperparameter specifications for the Deepnorm and Widenorm results stated in Pitis et al. (2020). The Widenorm used 32 components with size 32, concave activation size 5, and max-average reduction. For the Deepnorm we used the neural metric version which gave the strongest performance in their paper: 3 layers with dimension 128, MaxReLU pairwise activations, concave activation size 5, and max-average reduction. We adapt their PyTorch code from hitps: wwtp.//p/ppsiseeeeeoso.. In the graph distance task, results show the same learning pattern (and relative performances between models) but the overall error magnitudes that we obtain are rather different than their reported results.
We re-implemented the Deep-div method following the description Cilingir et al. (2020). The number of affine sub-networks stated in their paper varied but was generally set to low values such as 10, for the purpose of matching the number classes in their classification tasks. In their appendix they experiment with increasing numbers of sub-networks and find best results 50. For this reason we set 50 for our experiments. Following their paper, we use small FNNs for the max-affine components.
Our NBD uses a 2 hidden layer FICNN with width 128 for ø. We found that our results are robust to the depth and width of the FICNN.
F.1 ACTIVATION FOR FICNN
While developing theory using the softplus directly is harder because of the non-linearity, we believe that the approximation error using softplus activations is upper bounded by the ReLU approximation error. This is because the softplus
be made arbitrarily close to ReLU by making a large in the operation 9a (z) = log(1 + expl (ax)) aa. As the a value could be learned in the affine components of the neural network, ICNN with ReLU can be closely expressed as ICNN with softplus. So we can simply substitute 9ts (x) for ReLU(x) in the original proofs, and therefore our optimal error is less than equal the ReLU error. (In particular when the true function has curvature then it will be strictly better than ReLU).
G OVERLAP DETAILS
We use the INRIA Holidays dataset et al. (2008), which contains over 800 high-quality vacation pictures contributed by the original authors. Many caaneecutveenuumeere images (e.g. 129800.jpg. 129801. j29802.jpg) are retakes of the same scene, which would interfere with assigning zero overlap to different images. To address this we only use images ending in 00.jpg, which are all different scenes. This leaves 300 images, which we resize to 72x72 then apply a 64x64 center-crop. The training set consists of 10, 000 pairs sampled with random crops each epoch from the first 200 of the images, while the test set is fixed set of 10, 000 pairs with crops drawn from the last 100. We set 25% chance for a given pair to come from different images and receive a divergence of 1. All models were trained with batch size 128, Adam optimizer with learning rate 5e-4, and embedding dimension of 128. The embedding network consists of four 3x3 convolutional layers (32, 64, 128, 256 filters respectively) with 2x2 max pooling layers followed by two linear layers with hidden dimension 256.
We compute overlap the percent of non-intersecting area from the crops. We show this in
Fig. 5
16

---

Published as a conference paper at ICLR 2023
Vonaa 6)
1 0.24
1
0.76
0.0
CNN
CNN
CNN
CNN
g
D(a
D(b,0)
Figure 5: Demonstration of how the overlap distance is computed in our setup. Ground-truth distance the intersection of the shared images divided by the area of the first image.
H BREGMAN RANKING AND CLUSTERING STANDARD DEVIATIONS
Full version of Table
Standard deviations in small font, means in regular font.
MAP
AUC
Purity
Rand Index
Dataset
Model
Deep-div
0.281 0.01
0.645 0.02
0.377
0.660 0.04
Euclidean
0.301 0.01
0.666 0.01
0.422 0.03
0.750 0.01
abalone
Mahalanobis
0.310 0.01
0.677 0.01
0.419 0.02
0.750 0.01
NBD
0.316 0.01
0.682 0.01
0.432 0.03
0.750 0.01
PBDL
0.307 0.01
0.659
0.386
0.735 0.02
Deep-div
0.804 0.03
0.859 0.02
0.869 0.02
0.828 0.03
Euclidean
0.611 0.01
0.666 0.01
0.633
0.568 0.04
balance-scale
Mahalanobis
0.822 0.01
0.854 0.01
0.851 0.06
0.761 0.05
NBD
0.887 0.01
0.915 0.01
0.898 0.02
0.872 0.03
PBDL
0.836 0.02
0.855 0.02
0.872 0.02
0.814 0.03
Deep-div
0.787 0.01
0.757 0.01
0.852 0.04
0.750 0.04
Euclidean
0.681 0.00
0.589 0.00
0.704 0.02
0.523
Mahalanobis
0.787 0.01
0.752 0.01
0.778 0.02
0.654 0.03
NBD
0.820 0.01
0.803 0.01
0.860 0.01
0.758 0.02
PBDL
0.798 0.01
0.775 0.01
0.854 0.m1
0.750 o.n2
Deep-div
0.945 0.03
0.967 0.02
0.811 0.16
0.820 0.16
Euclidean
0.827 0.02
0.897 0.01
0.820 0.07
0.828 0.05
iris
Mahalanobis
0.946 0.03
0.973 0.01
0.884
0.879 0.11
NBD
0.957 0.02
0.977 0.01
0.909 0.10
0.902 0.10
PBDL
0.943 0.u3
0.967 0.02
0.889 0.14
0.888 0.13
Deep-div
0.648 0.01
0.525
0.02
0.756 0.03
0.621 0.04
Euclidean
0.666 0.01
0.536 0.01
0.748 0.03
0.563 0.04
transfusion
Mahalanobis
0.680 0.01
0.570 0.01
0.750 0.03
0.543 0.05
NBD
0.695 0.01
0.603 0.01
0.756 0.08
0.600 0.04
PBDL
0.637 0.01
0.504 0.01
0.748 0.03
0.622 0.03
Deep-div
0.983 0.02
0.987
0.01
0.953 0.08
0.947 0.08
Euclidean
0.844 0.02
0.884
0.02
0.902 0.07
0.887 0.06
wine
Mahalanobis
0.949 0.02
0.970 0.01
0.944 0.10
0.940 0.09
NBD
0.969 0.02
0.980 0.01
0.960 0.05
0.948
PBDL
0.978 0.02
0.982 0.01
0.820 0.14
0.823 0.12
Table 10: Across several real datasets, a learned Bregman divergence is superior to Euclidean or Mahalanobis metries for downstream ranking (MAP, AUC) and clustering (Purity, Rand Index) tasks. Furthermore, approach NBD consistently outperforms the prior Bregman learning approaches, Deep-div and PBDL, on most datasets. MAP mean average precision, AUC area under curve
17

---

Published as a conference paper at ICLR 2023
I
FIGURE (BREGMNIST) INCLUDING SYMMETRIC CASE
NBD
10
Decpnom
NBD
Widenorm
Deeptorm
100
Mahulanahis
Widenerm
Desp-div
Mabalutobis
100
50
0
10
20
30
40
50
10
20
30
40
50
(a) squared Euclidean distance.
(b) ((x) = (x + 1) log(2 + 1)
Figure 6: MSE (y-axis) after epochs of training (X-axis), where NBD performs best in the symmetric (left) and asymmetric (center, right) Bregman learning tasks, We see Mahalanobis performs well in the symmetric task (left) since it is correctly specified for the ground truth, but performs relatively poorly in the asymmetric case (right). Deep-div is unable to learn effectively in either (not shown on left because the error was too high).
18


Reviews:
[{"review_id": "VX0udYXC_g", "reviewer": "Reviewer_XV53", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a method for learning Bergman divergences using input convex neural networks as the convex generating function. This eliminates the shortcomings of previous work on the topic including non convexity of the neural network for deep divergence learning and high computational complexity of linear Bregman divergence learning. They further use CNN's as feature extractors and implement joint training. They experiment with various tasks such as regression, ranking and clustering and outperform the competing methods. Further they extend the Bregman divergence learning in two directions, one where the divergence satisfies both triangle inequality and symmetry and another where only triangle inequality is satisfied. ", "summary_of_the_review": "I think the paper has done enough work and has good quality for publication in the conference. Accept.", "strength_and_weaknesses": "The paper has many contributions and experiments. The idea of using input convex neural networks for learning Bergman divergences is new. The extensions to satisfy the triangle inequality and symmetry are also new. They have done extensive experimentation with different tasks and have compared to a significant number of competing methods. Further they have defined interesting divergence regression tasks such as BregMNIST and BregCifar.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "VVZnilLcWn", "reviewer": "Reviewer_GJoF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a new method called NBD to learn Bregman divergences between data points using a deep neural network. The proposed method is tested on some synthetic and small machine learning benchmark data sets. The results show that NBD outperforms several other metric learning approaches for some tasks.", "summary_of_the_review": "The paper seems to have a step forward in non-Euclidean distance learning. However, the main contribution is unclear, and the impact of the proposed method is questionable. I tend to give borderline rejection.", "strength_and_weaknesses": "Strength:\n\nThe authors adopted a more generic method to parameterize the phi function, which seems better than several other existing Bregman divergence learning approaches in various settings.\n\n\nWeakness:\n\nI doubt the usefulness of non-Euclidean distance learning. The authors enumerate the use in retrieval, clustering, and ranking in the introduction. However, there is little evidence in the paper to show significant improvement in these applications compared to Euclidean approaches. Instead, the authors focused on various artificial settings of the pairwise distances. Winning in such artificial scenarios may not justify the new method.\n\nSection 5.1 seems to be a realistic application. But the MAP@10 values are low compared with the state-of-the-art. Suppose we just use an image classifier (e.g., ResNet or Vision Transformer) and calculate the MAP@10 using the softmax outputs and their Euclidean distances. What is the benefit of using the proposed method?\n\nIt is infeasible to show that NBD works well for arbitrary non-Bregman distance learning. In Section 5.4, the authors have to modify the distance function as a remedy, which makes the claims looser.\n\nThe experiment setting is not clear. How many supervised pairs were used in training (compared to the number of data points)? Which pairs did you sample?\n\nTable 4: most SVHN results are 96.9, which looks unnatural. Why?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Im6Ew_lmo--", "reviewer": "Reviewer_DTa2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the limitation of previous methods for Bregman divergence learning and proposes a solution named Neural Bregman Divergences (NBD) using Input Convex Neural Network (ICNN), which can be computed efficiently and gives finer resolution to the generating function. Experimental results verify the performance of the proposed method on many metric learning tasks.", "summary_of_the_review": "This paper developed a new Neural Bregman Divergence, which jointly learns a Bregman measure and a feature extracting neural network.  It also demonstrates that the proposed method more faithfully learns divergences over a set of both new and previously studied tasks, including asymmetric regression, ranking, and clustering. Some experimental results verify the effectiveness of the proposed method. However, the novelty of this paper is limited. ", "strength_and_weaknesses": "Strength:\n\nThis paper developed a new Neural Bregman Divergence, which jointly learns a  Bregman measure and a feature extracting neural network. It also demonstrates that the proposed method more faithfully learns divergences over a set of both new and previously studied tasks, including asymmetric regression, ranking, and clustering.\n\nWeakness:\n\n1. The novelty of this paper is limited. The proposed method basically follows the existing Bregman learning methods (Siahkamari et al., 2020; Cilingir et al.,2020), and only jointly learns a Bregman measure and a feature extracting neural network in the proposed method. \n\n2. The experimental results of non-Bregman learning do not outperform SOTA methods. Does it mean the proposed method NBD only achieves better result on specific tasks where the underlying ground truth is from Bregman divergence? Will it restrict the application of NBD?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DftbVs2XCJ", "reviewer": "Reviewer_rc5T", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for learning a Bregman divergence using neural networks. A Bregman divergence is the divergence defined using a convex function, and any convex function has its corresponding Bregman divergence. The proposed method learns the divergence by representing the convex function by an Input Convex Neural Network (ICNN) (Amos et al., 2017). The paper provides a series of experiments to confirm the superiority of the proposed method over the previous methods.", "summary_of_the_review": "Overall, I like the paper and the authors make great contributions with many empirical results. I have a few concerns that I mentioned above, but I tend to accept the paper.", "strength_and_weaknesses": "# Strengths\n- The approach of directly learning the convex function by an ICNN seems interesting. Related papers on ICNNs support the representation power of the model.\n- The paper presents quite extensive experiments, and the proposed method shows excellent performance.\n\n# Weaknesses\n- I have a concern with Eq. (2). The paper says \"by construction, the resulting neural network satisfies convexity,\" but I don't think this is the case. If, additionally, $g$ were a non-decreasing function as assumed in Amos et al. (2017), I would understand the claim. I understand that the proposed method uses $g(x) = \\log(1 + \\exp(x))$ which is nondecreasing, so this may not be a big problem. However, I wonder if theories by Chen et al. (2019) and Pitis et al. (2020) apply to this activation function.\n- If I understand well, some experiments assume that divergence values are given as labels, which I believe is not very realistic in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster