A SIMPLE AND EFFECTIVE FRAMEWORK FOR PAIRWISE DEEP METRIC LEARNING
Authors: Qi Qi
Yan Yan
Zixuan Wu
Xiaoyu Wang
Tianbao Yang
Venue:  (2020)
Keywords: Deep Metric Learning
Distributionally Robust Optimization

Abstract: Deep metric learning (DML) has received much attention in deep learning due to its wide applications in computer vision. Previous studies have focused on designing complicated losses and hard example mining methods, which are mostly heuristic and lack of theoretical understanding. In this paper, we cast DML as a simple pairwise binary classification problem that classifies a pair of examples as similar or dissimilar. It identifies the most critical issue in this problem---imbalanced data pairs. To tackle this issue, we propose a simple and effective framework to sample pairs in a batch of data for updating the model. The key to this framework is to define a robust loss for all pairs over a mini-batch of data, which is formulated by distributionally robust optimization. The flexibility in constructing the  {\it uncertainty decision set} of the dual variable allows us to recover state-of-the-art complicated losses and also to induce novel variants.  Empirical studies on several benchmark data sets demonstrate that our simple and effective method outperforms the state-of-the-art results.

Under review as a conference paper at ICLR 2020
A SIMPLE AND EFFECTIVE FRAMEWORK FOR PAIR- WISE DEEP METRIC LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Deep metric learning (DML) has received much attention in deep learning due to its wide applications in computer vision. Previous studies have focused on de- signing complicated losses and hard example mining methods, which are mostly heuristic and lack of theoretical understanding. In this paper, cast DML as a simple pairwise binary classification problem that classifies a pair of examples similar dissimilar. It identifies the most critical issue in this problem- imbalanced data pairs. To tackle this issue, we propose a simple and effective framework sample pairs a batch of data for updating the model. The key to this framework is to define robust loss for all pairs over a mini-batch of data, which is formulated by distributionally robust optimization. The flexibility in con- structing the uncertainty decision set of the dual variable allows us to recover state-of-the-arg art complicated losses and also to induce novel variants. Empirical studies several benchmark data sets demonstrate that our simple and effective method outperforms the state-of-the-ar results.
INTRODUCTION
Metric Learning aims learn metric to measure the distance between examples that captures certain notion of human-defined similarity between examples. Deep metric learning (DML) has emerged effective approach for learning metric by training deep neural network. Simply speaking, deep neural network can induce new feature embedding of examples and it is trained in such way that the Euclidean distance between the induced feature embeddings of two similar examples shall be small and that between the induced feature embeddings of two dissimilar pairs shall be large. DML has been widely used in many tasks such as face recognition (Fan et al (2017). image retrieval (Chen & Deng (2019)), and classification (Qian et al. (2015): Li et al. (2019)).
However, unlike training a deep neural network by minimizing the classification error, training a deep neural network for metric learning is notoriously more difficult (Qian et al. (018); Wang et al. (0177). Many studies have attempted to address this challenge by focusing on several issues. The first issue is how to define a loss function over pairs of examples. A variety of loss functions have been proposed such as contrastive loss (Hadsell et al. (2006)). binomial deviance loss (Yi et al.)), margin loss (Wu et al. (2017)), lifted-structure (L.) loss (Oh Song et al. (2016)) N-pair loss (Sohn) (016)). triplet loss (Schroff et al. (2015)). multi-similarity (MS) loss (Wang et al. (2019). The major difference between these pair-based losses lies how the pairs interact with each other in a mini-batch. In simple pairwise loss such as binomial deviance loss, contrastive loss, and margin loss, pairs are regarded as independent of each other. In triplet loss, a positive pair only interacts with one negative pair. In N-pair loss, positive pair interacts with all negative pairs. In LS loss and MS loss, positive pair interacts with all positive pairs and all negative pairs. The trend is that the loss functions become increasingly complicated but are difficult to understand.
In parallel with the loss function, how to select informative pairs to construct the loss function has also received great attention. Traditional approaches that construct pairs or triplets over all examples before training suffer from prohibitive O(N²) or ( sample complexity, where N is the total number of examples. To tackle this issue, constructing pairs within a mini-batch is widely used in practice. Although it helps mitigate the computational and storage burden, slow convergence and model degeneration with inferior performance still commonly exist when using all pairs in mini- batch to update the model. To combat this issue, various pair mining methods have been proposed to complement the design of loss function, such hard (semi-hard) mining for triplet loss (Schroff

---

Under review as a conference paper at ICLR 2020
et al. (2015)) distance weighted sampling (DWS) for margin loss (Wu et al. (2017)) MS sampling for MS loss Wang et al. (2019). These sampling methods usually keep all positive (similar) pairs and select roughly the same order of negative (dissimilar) pairs according to some criterion.
Regardless of these great efforts, existing studies either fail to explain the most fundamental problem in DML or fail to propose most effective approach towards addressing the fundamental challenge. It is evident that the loss functions become more and more complicated. But it is still unclear why these complicated losses are effective and how does the pair mining methods affect the overall loss within a mini-batch. In this paper, we propose a novel effective solution to DML and bring new insights from the perspective of learning theory that can guide the discovery of new methods. Our philosophy is simple: casting the problem of DML into a simple pairwise classification problem and focusing on addressing the most critical issue, i.e., the sheer imbalance between positive pairs and negative pairs. To this end, we employ simple pairwise loss functions (e.g., margin loss, binomial deviance loss) and propose a flexible distributionally robust optimization (DRO) framework for defining a robust loss over pairs within mini-batch. The idea of DRO is to assign different weights to different pairs that are optimized by maximizing the weighted loss over an uncertainty set for the distributional variable. The model is updated by stochastic gradient descent with stochastic gradients computed based on the sampled pairs according to the found optimal distributional variable.
The DRO framework allows us to (i) connect to advanced learning theories that already exhibit their power for imbalanced data, hence providing theoretical explanation for the proposed framework; (ii) to unify pair sampling and loss-based methods provide unified perspective for existing solutions; (iii) to induce simple and effective methods for DML, leading to state-of-the-art performance on several benchmark datasets. The contributions of our work are summarized follows:
We propose a general solution framework for DMI., i.e., by defining a robust overall loss based on the DRO formulation and updating the model based on pairs sampled according to the optimized sampling probabilities. We provide theoretical justification of the proposed framework from the perspective of advanced learning theories.
We show that the general DRO framework can recover existing methods based on complicated pair-based losses: LS loss and MS loss by specifying different uncertainty sets for the distribu- tional variable in DRO. It verifies that our method is general and brings a unified perspective regarding pair sampling and complicated loss over all pairs within a batch.
We also propose simple solutions under the general DRO framework for tackling DML. Exper- imental results show that our proposed variants of DRO framework outperform state-of-the-art methods on several benchmark datasets.
2 RELATED WORK
Loss Design. The loss function is usually defined over the similarities or distances between the induced feature embeddings of pairs. There are simple pairwise losses that simply regard DML as binary classification problem using averaged loss over pairs, e.g., contrastive loss, binomial loss, margin loss. It is notable that the binomial loss proposed in (Yi et al.) assigns asymmetric weights for positive and negative pairs, which can mitigate the issue of imbalance to certain degree. The principal of the newly designed complicated pair-based losses can be summarized as heuristically discovering specific kinds of relevant information between groups of pairs to boost the training. The key difference between these complicated losses lies how to group the pairs. N-pair loss put one positive pair and all negative pairs together, Lifted-structurre loss and MS-loss group all positive pairs together and all negative pairs together for each example. In contrast, our DRO framework employs simple pairwise loss but induce complicated overall loss in systematic and interpretable way.
Pair Mining/Pair Weighting. Wu et al. (2017) points out that pair mining plays an important role in distance metric learning. Different pai mining methods have been proposed, including semi- hard sampling for triplet loss, distance weighted sampling (DWS) for margin loss, MS mining for MS losses. These pair mining methods aim to select the hard positive and negative pairs for each anchor. For instance, [ccrroff et al. (2015) selects the hard negative pairs whose distance is smaller than that between the positive pairs in triplets, Shi et al. (016) selects the hardest positive pair whose distance is smaller than that of the nearest negative pair in a batch, and MS mining (Wang et al. (2019) selects hard negative pairs whose distance is smaller than the largest distance between positive pairs and hard positive pairs whose distance is larger than the smallest distance between negative pairs at the same time. DWS method keeps all positive pairs but samples negative pairs
2

---

Under review as a conference paper at ICLR 2020
according to their distance distribution within a batch. The proposed DRO framework induce pair sampling method by using the optimal distributional variables that defines the robust loss over pairs within batch. As result, the sampling probabilities induced by our DRO framework is automatically adaptive to the pair-based losses. There are other works that study the problem from the perspective of pair weighting instead of pair sampling. For example, Yu et al. (2018) heuristically design exponential weights for the different pairs in a triplet, which is a special case of our DRO framework. Details are provided in the supplementary. However, since the quality of anchors varies very much, it may not be reasonable to sample the same number of pairs from all anchors.
Imbalance Data Classification. There are many studies machine learning which have tackled the imbalanced issue. Commonly used tricks include over-sampling, under- under-sampling sampling and cost-sensitive learning. However, these approaches do not take the differences between examples into account. Other effective approaches grounded on advanced learning theories include minimizing maximal losses (Shalev-Shwarzz & Wexler, 2016), minimizing top-k losses (Fan al. (017] and minimiz- ing variance-regullaiized losses (Namkoong & Duchi 2017). However, these approaches are not efficient for deep learning with big data, which is a severe issue in DML. In contrast, the proposed DRO formulation is defined over mini-batch of examples, which inherits the theoretical explana- tion from the literature and is much more efficient for DML. In addition, the induced loss by our DRO formulation include maximal loss, top-k loss and variance-regulariized loss as special cases by specifying different uncertainty sets of the distributional variable.
3 DML AS A DRO-BASED BINARY CLASSIFICATION PROBLEM
In this section, we will first present a general framework for DML based on DRO with theoretical justification. We will then discuss three simple variants of the proposed framework and also show how the proposed framework recover existing complicated losses for DMI.
Preliminaries. Let TRD denote input data (e.g., image) and f(: : RDD - Rd denote the feature embedding function defined by a deep neural network parameterized by 0. The cen- tral task in DML is to update the model parameter by leveraging pairs of similar and dissimilar examples. Following most existing works, at each iteration we will sample a mini-batch of exam- ples denoted by (xI...,,XB) ).) We can construct B² pairs between these examples D and let yig denote the label of pairs, i.c., Viy = 1 if the pair is similar (positive), and Yij = 0 Of the pair is dissimilar (negative). The label of pairs can be either defined by users or derived from the class label of individual examples. Existing works of DML follow the same paradigm for learning the deep neural network i.e., a loss function F(0) is first defined over the pairs within a mini-batch and the model parameter 0 is updated by gradient-based methods. Various gradient-bast be used, including stochastic gradient descent (SGD), stochastic momentum methods and adaptive gradient methods (e.g. Adam). Taking SGD as an example, the model parameter 0 can be updated by 0 + 0 - v/ (O)), where 7/ denotes the learning rate. The focus here is to how to define the loss function F()) over all pairs within a mini-batch. As mentioned earlier, we will cast the problem as simple binary classification problem, i.e., classifying pair into positive or negative. To this end, we use 4y (0) [ff (x;; 0), f (x,:0), Yir) denote the pairwise classification loss between x; and x, in the embedding space (e.g., margin loss Wu et al. (017). binomial loss Yi et al.). A naive approach for DML is to use the averaged loss over all pairs, i.e., (0) B >i= Ex= (O). However, this approach will suffer from the severe imbalanced issue, i.e., most pairs are negative pairs. The gradient of Favg will be dominated by that of negative pairs.
methods can
3.1 GENERAL DRO-BASH BASED FRAMEWORK
To address the imbalanced pair issue, we propose general DRO formulation to compute robust loss. The formulation of our DRO-based loss over all pairs within a mini-batch is given below:
B B
F(0) = max (g p) = ΣΣ (0)}
peu
where p E RR..² is non-negative vector with each element Pij representing a weight for an individ- ual pair. 21 C B² denotes the decision set of p. which encodes some prior knowledge about p. In
For simplicity, we consider all pairs including self-pair.
3

---

Under review as a conference paper at ICLR 2020
the literature of DRO Namkoong & Duchi (2017). p is interpreted probability vector such that Σi Pij = 1 called the distributional variable and U denotes the uncertainty set that specifies how deviates from the uniform probabilities (1/B²... ................................ . ). In next subsection, we will propose simple variants of the above general framework by specifying different constraints or regularizations for p. Below, we will provide some theoretical evidences to justify the above framework.
To theoretically justify the above loss, we connect T to exiting works in machine learning by considering three different uncertainty sets for p. First. we consider simple constraint U A = {Pt 2 0, Eij Ptj = 1}. As a result, F(0) = max,j 4g becomes the maximal loss over all pairs. Shalev-Shward & Wexler (016) shows that minimizing maximum loss is robust to imbalanced data distributions and also derives better generalization error for imbalanced data with rare class. However, the maximal loss is more sensitive to outliers (Zhu et al. 2019). To address this issue, top- K loss (Fan et al. 2017) and variance- regularzze loss (Namkoong & Duchi 2017) are proposed, which can be induced by the above DRO framework. If we set u {Eig Pij 1,0 S
Piy S 1/K]. F will become the top-K loss F (0) = K E (O)()), where (1) denotes the i-th largest loss over all pairs. If we set Us = {p E A, (p(PII/B)) S ). where (plp')') = ) (((p' )dp' is the d-divergence between two distributions p and p' with @(t) [ 1)a, then the DRO-based loss becomes the variance-regulariie of the random loss, i.e., for a set of i.i.d random losses {li,.., La (n = B²) we could have
loss under certain condition about the variance
1 4 1=1
Va (8)
sup Σnb= DE 1=1
where (fr, denotes the empirical variance of Ei,,.., ..., bu We can see that the second term in R.H.S of the above equation involves the variance, which can play a role of regularization. The variance- regularized loss has been justified from advanced learning theory by Namkoong & Duchi 2017))
and its promising performance for imbalanced data has been observed as well.
Before ending this subsection, we will discuss how update the model parameter I based on the
bust loss F(0) defined by (I) A simple approach is to find an optimal distributional variable p.. to T and then update 9 according to the subgradient of weighted loss by 0øg(0, p¹) = Ei, V4 which is justified by the following lemma.
Lemma 1 Assume that is proper, lower-semicontinuoo in O and level-bounded in locally uni- formly in 6. Then the subgradient (F) C -Up oeg(6. p²), where P" (8) denotes the optimal solution set of the maximization problem in Q Furthermore, when (,)(0) is smooth in 9 and (0) singleton, ie., p arg max, g p) is unique, we have O (0) = O0g(0.p").
Remark The above lemma can be proved by Theorem 10.13 in Rockafellar & Wets (009). It
shows that even if we may not directly compute (F) our framework can at least obtain its superset Particularly, if we have additional conditions, i.e., lz)(0) is smooth in @ and the optimal solution p" is unique (considering our regularized formulation below), it theoretically guarantees that our framework exactly computes (F
Oog(0, O, p²)
3.2 PROPOSED THREE VARIANTS OF OUR FRAMEWORK
In this subsection, we present three variants of our general framework. In order to contrast to other variants recovering existing complicated losses presented in next subsection, we introduce some notations and make some simplifications. For each example x; that serves as an anchor data, let P. {jly Vıj = 1,j [B]) and AV; {ilbi 0,j [B]} denote the index sets of positive and negative pairs, respectively. Let P = U P. and N = U,,,,,, .N. We denote the cardinality of a set by P = |P]. For simplicity,
let P. = [P,l, N, W... [P] and N [W]- Since zero losses usually do not contribute to the computation of the subgradient for updating the model, we can simply eliminate those examples for consideration.
The first variant is to simply select the top-K pairs with K K-largest losses, which is equivalent to the following DRO formulation:
B
B Σ
DRO-TopK: max
Σ
Σ
(0), S.L.
Σ
Ps = 1,=1,05 Ps S 1/K,
P
2= JEP.JN
1=1
JEP,UN
4

---

Under review as a conference paper at ICLR 2020
where K is hyper- parerr-rr.mterr.. The gradient of the robust loss can be simply computed by sorting the pairwise losses and computing the average of top-K losses.
The second variant is a variant of the variance-regullrrized loss. Instead of specifying the uncertainty set Ug, we use a regularization term for the case of computation, which is defined by
B
DRO-KL:
max PRN
Σ
Σ JEPILN.
Pisli(0) -7Dx(00)>Dxx(PPp P+N ) S.L.
Σ JEPLLN
-,
PER P-N
where 7 > 0 is hyper-parameter and DxI. denotes the KI. divergence between two probabilities. The optimal solution to p can be easily computed following Namkoonn & Duchi (2016). It notable that the optimal solution is not necessarily sparse. Hence, computing Dnp Pij (0) needs to compute the gradient of pairwise loss for all pairs, which could be prohibitive in practice when the mini-batch size is large. To alleviate this issue, we can simply sample subset of pairs according to probabilities in p* and the compute the averaged gradient of these sampled pairs.
The third variant of our DRO framework explicitly balancing the number of positive pairs and negative pairs by choosing top K/2 //2 pairs for each class, which is denoted by DRO-TopK-PP -NN::
DRO-TopK-PNY
(0) S.L. Σ (0.) i=1 JEPIUN.
max
Σ E
Σ Pij
K
ΣΣΣ Paj =1ijNN
K
For implementation, we can simply select K/2 positive pairs with largest losses and K/2 negative pairs with largest loss respectively, and compute averaged gradient of the pairwise losses of the selected pairs for updating the model parameter.
3.3 RECOVERING THE METHOD BASED ON SOTA PAIR-BASER BASED Loss
Next we show that proposed framework can recover the method based on SOTA complicated losses. With the induced feature vector f fx; f) normalized have unit norm, we define the similarity of two samples as Sig (J'x;; 0), (x,;; 0)), where (+:-) denotes dot product. Specifically, we consider two SOTA loss functions, LS and MS loss, which are defined below:
LMS
log [1 1+
Σ e -( A11 +
log + Σ
3
REP.
REN.
LLS = >> Dlg
A S-S Siz
+ log Σ )
kEP.
kEN.
where a, B, A are hyper-parameters of these losses.
The key argument is that the gradient computed based these losses can be exactly computed according to our DRO framework by choosing appropriate constrained set 2/ and setting the pairwise loss the margin loss. To this end, we first show the gradient based on the LS loss, which can be computed by (Wang et al. 2019):
OC(S)
AC(S)
as
B
B
aC(S)
(4)
30
as
00
OS.j
00
1=
==
which can be alternatively written as
AC(S)
B = Σ
Σ
as
Σ
Siz 00
Wij
w
(5)
00
00
1=1
JEN;
jEP;
It can be shown that for LS loss, derivations are provided in the supplementary, we have
é A-S
S
Why
B Σ
Sik
Σ
S.
Sik
Σ SAc-A REN:
Σ
Sax -.5
KEP.
kEP:
keA:
To recover the gradient of the LS loss under our DRO framework, we employ the pairwise margin loss for ky (9), i... (9) Im yA S,y),+, where and À two [a]+ = max a}. Assume that the margin parameter m is sufficiently large such that (y()) > for all pairs The key to deriving the same gradient of the LS loss under framework to group
and
5

---

Under review as a conference paper at ICLR 2020
distributional variables in p for the positive and negative pairs according to the anchor data. Let p E R and P; E RR'; denote the corresponding vectors of positive and negative pairs for the anchor X,, respectively, Let consider the following DRO formulation:
B
F(0)= max Σ DER_* i=1 JEP:UN;
E
(1)li(()
E (1t DKL(P P. + n2 (KI
1 N
(7)
s.t. Σ
Pig 1,
Σ REN;
Pik 1, for [B),
jEP.
where 7,5 0 and 7/ 2 0 for i [B] are hyper-parameters. we can easily derive the closed-form
solution for p., i.e. Pij
(8 (u--8amm and Pij
Then computing the
Σ
Σ
(Bik
Sty)/1
N
NEW,
gradient of the robust loss with respect 0 by using the above optimal p", we have:
B
OF(0)
Σ
Σ
Púj
aSG
Σ
Pú
00
00
JEN.
JEP
which exactly recover the gradient in 6 by setting 7,-
7, 1.
Finally, we can recover the gradient based on the MS loss in a very similar way. The difference to add a pseudo positive pair and pseudo negative pair with 0 loss for each anchor x,, and augment each p. and p; by one additional dimension. The details are provided in the supplementary.
EXPERIMENTS
Our methods was implemented by Pytorch and using BN-Inception network (loffe & Szegedy (2013) pre-trained on ImageNet ILSCC (Russakovsky et al. (2013)) to fairly compare with other works. The same as (Wang et al. (2019). FC layer on the top of the model structure following the global pooling layer was added with randomly initialization for our task. Adam Optimizer with 1e learning rate was used for all our experiments.
We verify our DRO framework on image retrieval task with three standard datasets, Cub-200-201 Cars- 196--196dsn and In-Shop. These three datasets are split according to the standard protocol. For Cub- 200-201 1, the first 100 classes with 5864 images are used for training, and the the other 100 classes with 5924 images are saved for testing. Cars-196 consists of 196 car models with 16, 185 images. We use the first 98 classes with 8054 images for training and the remaining 98 classes with 8,131 images for testing. For In-Shop, 997 classes with 25882 images are used for training. The test set is further partitioned to a query set with 14218 images of 3985 classes, and a gallery set containing 3985 classes with 12612 images. Batches are constructed with the following rule: we first sample certain number of classes and then randomly sample M instances for each class. The standard recall@k evaluation metric is used in all our experiments, where k = 21,2,44 4,8, 16, 32) on Cub- 200-2011 1 and Car-196, and k (1, 10, 20, 30, 40, 50) on In-Shop. We apply margin loss (Lar) and binomial loss (C., Yi et al.) as base losses for our DRO framework. m is the margin in L.. X is the threshold for both Ca and Lg. a and |3 are hyperparameters in LB.
4.1 QUANTITATIVE RESULTS
In this experiment, we compare our DRO framework with other SOTA baselines on Cub-200-2011.
Cars-196 and In-Shop, which includes Wang et al. (2019: Yu al. (2018); Kim et al. (2018): Opitz
et al. (2018); Ge (2018); Harwood et al. 2017):10 Wu et al. (): Oh Song et al. (2017). Among them, mining-based methods are Clusetring, HDC, Margin, Smart Mining and HDL, ABIER and ABE are ensemble methods. HAP2S E and MS are sampling- based methods, which are highly related to our methods. For our DRO framework, we test all three variants which are proposed in section 3 We apply two loss functions, margin loss and binomial loss, respectively. Since DRO p-sampling works on all pairs in a batch, the binomial variant may not directly apply to p- sampling. Thus, it makes totally five variants of our DRO framework, denoted by DRO-TopK m. DRO-TopKg. DRO-TopK-PPO PNas. PRO-TopK-BB -N and DRO-KL where the subscript M and B represent the variants of our framework using margin loss and binomial loss, respectively. We set embedding space dimension d = 1024. The batchsize is set = 80 on Cub-200-2011 and Cars-196, B = 640 In-Shop. 7 is tuned from the range (0.1 0.2 0.9} all three

---

Under review as a conference paper at ICLR 2020
Table 1: &ecall@k I on Cub-200-2011 and Cars- 196
Cub-200-2011
Cars- 196
8
16
16
32
Clusetring Song 2017)
48.2
61.4
71.8
81.9
58.1
70.6
80.3
87.8
HDC Song el al
2017)
53.6
65.7
77.0
85.6
91.5
95.5
73.7
83.2
89.5
93.8
96.7
98.4
Margin Wu et al. 2017
63.6
74.4
83.1
90.0
94.2
79.6
86.5
91.9
95.1
97.3
Mining Larwood
2017
49.8
62.3
74.1
83.3
76.2
84.2
90.2
GS 2018]
57.1
68.8
78.7
86.5
92.5
95.5
81.4
88.0
92.7
95.7
97.4
99.0
ABIER(Opil/ di al 2018)
57.5
68.7
78.3
86.2
91.9
95.5
82.0
89.0
93.2
96.1
97.8
98.7
ABE or a. 2018
60.6
71.5
79.8
87.4
85.2
90.5
94.0
96.1
HAP2S EI Yu 2018)
56.1
68.3
79.2
86.9
74.1
83.5
89.9
94.1
MS/Wang or 2019
65.7
77.0
86.3
91.3
94.8
97.0
84.1
90.4
94.0
96.5
98.0
98.9
DRO-
67.4
77.7
85.9
91.6
95.0
97.3
86.0
91.7
95.0
97.3
98.5
99.2
DRO-Topk, ( (Ours)
68.1
78.4
86.0
91.4
95.1
97.6
85.4
91.0
94.2
96.5
98.0
99.0
1.0-TopK-PN.,
67.3
77.6
85.7
91.2
95.0
97.7
86.1
91.7
95.1
97.1
98.4
99.1
DRO-TopK-PHe (Nun)
67.6
77.9
86.0
91.8
95.2
97.7
86.2
91.7
95.8
97.4
98.6
99.3
DRO-KI. (RO--Kl.g(OOur))
67.7
78.0
86.1
91.8
95.6
97.8
86.4
91.9
95.4
97.5
98.7
99.3
datasets and K is tuned from {160, 200, 240, 280} on Cub-200-2011 and Cars-196, and selected
from {640, 960, 1280, 1600, 1920} on In-Shop.
T report the experiment results. We mark the best performer in bold in the corresponding evaluation measure on each column. For our framework, particularly, we mark those who outper- form all other SOTA methods in bold. We can see that our five variants outperform other SOTA methods on 1 on all three datasets. Particularly on Cars- 196, our five variants outperforms other SOTA methods on all recall@kk measures. On Cub-200-2011 recall@1 (improving 2.4 in recall 1) than the best SOTA, MS. On Cars- 196, DRO-KL,, has the best performance, which improves 2.3 and 1.2 recall@1 compared to the best non-ensemble SOTA, MS, and the best ensemble SOTA, ABE. On In-Shop,
DRO-TopK B achieves higher
improves 1.6 in recall@1 compared to the best results among SOTA, MS. The above results verify 1) the effectiveness of our DRO sampling methods and 2) the flexibility of our DRO framework to adopt different losses.
4.2 ABLATION STUDY COMPARISON WITH LS LOSS AND MS LOSS
4.2.1
Table 2: Recover of MS loss and LS loss on Cub-200-2011 I and Cars-
Cub-2000-011
Cars-
Recall@((%)
1
2
4
8
16
32
1
2
4
8
16
32
MS
55.6
67.7
17.4
86.3
92.1
95.8
13.2
81.5
87.6
92.6
LS
56.8
67.9
77.5
85.6
91.2
95.2
69.7
79.3
86.2
91.1
DRO- DRO-KL-G- KL-G--
56.4
68.3
78.9
86.3
91.7
95.8
70.5
79.8
86.6
91.6
94.9
97.1
DRO-KL KL-G-1 0.1
56.8
68.7
79.0
86.6
92.1
95.9
72.5
81.9
88.1
92.3
95.4
97.3
DRO-KI--G-7 0.01
57.0
69.4
79.9
87.0
92.3
95.9
73.1
82,2
88.8
93.4
96.2
98.0
DRO-KI-GG-- 0.001
56.7
68.5
79.0
87.3
92.6
96.0
75.0
83.4
89.5
93.7
96.6
98.3
In Section 3.3
theoretically show that LS loss and MS loss can be viewed special cases of our DRO framework. In this experiment, we aim to empirically demonstrate that our framework is general enough and recovers L.S loss. Specifically, we would show 1) when 7 1, our framework performs similarly to LS loss, as stated in Section 3.3 2) our framework can be seen as a generalized LS loss by treating ? as a though the performance of the ordinary LS loss is inferior to that of MS loss.
and 3) our generalized LS loss outperforms MS loss, even
We adopt the set up of embedding dimension and batchsize in the ablation study of Wang et al. (201)) i.e., d = 64 and B = 80. Therefore, we report the existing results of MS and LS loss presented in WWag et al. (2019) on Cars- 196. For Cub-200-201 and In- Shop, we implement MS and LSS loss according to Wang et al. (2019). Following Wang et al. (2019), we set = 2, = 50 for MS loss. For our DRO framework, we apply grouping to p by equation 77. and denote this variant of DRO framework as DRO-KL-G. We set 7,' 7, = y {1, 0.1, 0.01, 0.001), i [B] for DRO-KL-G, m = 0.2 for the margin loss, and À = 0.5 for all three losses (MS, LS and margin loss). As the pairs with zero loss will not contribute to the updates of model but affect the calculation of p in DRO framework, we remove the pairs with zero loss to further promotes training.
Table and show experiment results can be seen, the performance of MS loss is better than LS loss on three datasets, particularly on Cars- 196, which also verifies the results of ablation study in Wang et al. (019)). When y 1, our method
Cars-196 and In-Shop, respectively. As
7

---

Under review as a conference paper at ICLR 2020
performs similarly to LS loss, which verifies that our method recovers LS loss. Furthermore, when we treat y as a LS loss, our method obtain improved performance compared to the ordinary LS loss. Lastly, even if MS loss exploits pseudo positive and negative pairs, our generalized LS loss outperforms MS loss.
(especially Y = 0.001) and regard our framework as generalized
Recall@k on Different P-N Ratio
Table 3: Recall on In- In-Shop
0.90
HDC HiM
Recallix
150
10
17.0
30
30.0
50
34.5
91.2
93.1
50.9
94.3
95.8
97.3
97.4
97.8
0.88
ADIER Dovieein m0
95.1
97.3
97.3
98.0
96.7
98.2
98.7
1
97.9
98.8
99.1
99.2
0.86
V131
981
U5.7
913
9911
19.1
DRO-Tipk ((0m))))
90.7
97.7
98.4
98.8
90.0
99.1
DWS
ORO-Tupk-PM.. (Oun))
91.3
98.1
18.7
58.9
99.1
99.2
0.84
SHw
URO-TigR-78
DRO-KLarOus)
90.8
91.1
98.1
98.1
98.6
98.6
99.8
98.8
99.1
99.0
99.2
99.3
DRO-TopKH
Table 4: Recover of MS loss and LS loss
In In-Shop
0.82
DRO-TopK-PNN
(
10
20
30
40
507
DRO-KL#
KI5
193
54.9
96.3
37.6
97.3
98.3
82.6
97.4
0.053
0.026
0,012 P-N Ratio
0,008
0,006
KL-GGy
DRO-KI -G-y
97.5
98.3
DRO KL- KL-G-7 0.01
85.8
96.2
97.9
97.8
98.2
98.4
DRO-KLAG-Y 0.001
85.7
96.1
97.4
97.9
98.2
98..
Figure 1: Recall vs Imbalance Ratio
4.2.2 CAPACITY TO HANDLE PAIR IMBALANCE.
In this experiment, we compare our DRO framework with different sampling methods, i.c., semi- hard (SH) and DWS, in terms of sensitivity to the imbalance ratio. By setting different batch- sizes B E {80, 160, 320, 480, 640), have different pesitive-negative pair ratios |P| [W] {0.053, 0.026, 0.012, 0.008, 0.006]. For all methods, we apply margin loss and set M = 5 for each class and embedding space dimension d 1024. SH mining originally designed for triplet loss. Since there is no straightforward choice for the positive pair, we use À as the upper bound to sim- ulate the similarity of the positive pair in triplet loss. For DWS, we follow the parameter setting in the original paper (Wu et al. (0177). We apply margin loss in the proposed three variants our DRO framework, which are denoted by DRO-TopK M. PRO-TopK-PN. M and DRO-KLM, respectively. We set K = 2 B both for DRO-TopK DRO-TopK-PN., We evaluate recall@1 of all methods and report results in Figure [
Figure [ shows that the DWS has better performance when the positive-negative pair ratio is rel- atively large, and encounters sharp decrease in recall@1 when the ratio decreases. Other four methods obtain better performance when the positive-negative ratio increases. Among them, DRO- TopK and DRO-KL, have similar performance, with SH on all they perform slightly better than SH when the positive-negative ratios small. DRO-TopK-PN,, constantly outperforms all other methods. The reason why DWS performs poorly when the positive- negative pair ratio is small may be that DWS aims to sample pairs uniformly in terms of distance (Wu et al. (2017)), while our DRO framework and SH focus more on hard pairs. To sum up. our framework achieves very competitive performance against SOTA methods, and maintains increasing @ as the positive-negative ratio increases. These two observations together demonstrate the effectiveness of our DRO framework to handle pair imbalance.
pair ratios, while
4.2.3 SENSITIVITY OF K IN TOP-K
As we mentioned in section I selecting too many pairs within batch will leads to poor performance of the model. On the other hand, when the number of selected pairs is too small, the model would be sensitive to outliers. In this experiment, we study the sensitivity of K in our DRO -ram the performance of our DRO framework affected by the value of K. We set the batchsize B 640 and M 5, which makes the number of positive pairs |P| 1280 and the number of negative pairs I = 198080. We set K from the range (640, 960, 1280, 1600, 1920, 2560] and evaluate recall@A for models trained by different K. We choose the above range of K according the number of pairs selected by DWS and SH in Section 4.2.2 (both selects 2560 pairs roughly).
Figure 2 iillustrates how different values of K affect recall@kk on In-Shop. We can see that, DRO- TopK M performs best when K = 1280 and recall@k is stable on the entire range of K. Our DRO framework is not sensitive to K when K is in reasonably large range.
8

---

Under review as a conference paper at ICLR 2020
Recallik with Different on Ia shop
Average Runtime Every Itcration
DRD-Toplu
0.73
ERO-TopiiPMMe
ERO <lus
3.00
Recallg
0:25
Ronelmecsce))
2.29
MS
6:06
tocal 2g
Tocal g20
8.75
0288
tocal
hocal 4400
Rocal 910
(J66
1:0
K
Batchsize
Figure 2: The effects of K on recall@k on In-Shop
Figure 3: Average running time of every iteration
4.2.4 RUNTIME COMPARISON
Next, we compare the running time of our proposed three variants of our DRO framework with different pair mining methods, MS and LS losses on In-shop. Our experiments conducted on eight GTXI0S0Ti GPU. The embedding dimension d 1024, and results compared under different batchsize = {80, 160, 320, 480, 640). The same as previous experiments, we set K = 2 * B both for DRO-TopK as and PRO-TopK-PY. M. 7 0.1 for DRO-KLM- SH is implemented according to the paper Sccroof' et al. (2015). Wu et all 2017). DWS and MS are implemented based on the code provided by the author. LS loss is implemented following the code provided by Waang al. (2019).
Figure 3 reports the average running time of each iteration on 200 epochs. We can see that all of three proposed variants of DRO framework run faster than other anchor-bused mining methods and losses. For all of our three variants, pairs are selected directly from all the pairs, while additional cost required select pairs anchor by anchor in other methods. LS loss is slower than MS loss, because MS mining is applied to MS loss, which would reduce the number of pairs for computing subgradients when updating the model. For DWS, the distance distribution of negative pairs is only calculated once for each iteration. It thus only needs to select pairs according to the pre-computed distribution for each anchor. contrast, SH requires to compare negative pairs with the lower and upper bound of interval at each iteration for each anchor, which increases the computational burden. It can be the reason why SH is slower than DWS.
CONCLUSION
In this paper, we cast DML as simple pairwise binary classification problem and formulate as a DRO framework. Compared to existing DML methods that leverage all pairs in batch or employ heuristic approaches to sample pairs, our DRO framework constructs a robust loss to sample informative pairs, which also comes with theoretical justification from the perspective of learning theory. Our framework is general since it can include many novel designs in its uncertainty decision set. Its flexibility allows to recover the state-of-the-att loss functions. Experiments show that our framework outperforms the state-of-the--rt DMI, methods on benchmark datasets. We also empirically demonstrate that our framework is efficient, general and flexible.
REFERENCES
Binghui Chen and Weihong Deng. Hybrid-attention based decoupled metric learning for zero-shot image retrieval. In Proceedings of the IEEE Conference Computer Vision and Pattern Recog- nition, pp. 2750-2759, 2019.
Yanbo Fan, Siwei Lyu, Yiming Ying, and Baogang Hu. Learning with average top-k loss. In Advances in Neural Information Processing Systems, pp. 497-505, 2017.
Weifeng Ge. Deep metric learning with hierarchical triplet loss. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 269-285, 2018.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recogni- fion (CVPR 06), volume 2, pp. 1735-1742. IEFE, 2006.

---

Under review as a conference paper at ICLR 2020
Ben Harwood, BG Kumar, Gustavo Carneiro, lan Reid, Tom Drummond, et al. Smart mining for deep metric learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2821-2829, 2017.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person identification. arXiv preprint arXiv: 1e00:07737777 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 150.vv/502.03 2015.
Wonsik Kim, Bhavya Goyal, Kunal Chawla, Jungmin Lee, and Keunjoo Kwon. Attention-bass ensemble for deep metric learning. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 736-751, 2018.
Xiaomeng Li, Lequan Yu, Chi-Wing Fu, Meng Fang, and Pheng-Ann Heng. Revisiting metric learning for few-shot image classification. arXiv preprint
2019.
Ziwei Liu, Ping Luo, Shi Qiu, Xiaogang Wang, and Xiaoou Tang. Deepfashion: Powering robust clothes recognition and retrieval with rich annotations, In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1096-1104, 2016.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, pp- 2208-2216, 2016.
Hongseok Namkoong and John C. Duchi. Variance-based regularization with convex objectives, In Advances in Neural Information Processing Systems (NIPS), pp. 2975-2984, 2017.
Hyun Oh Song. Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp.
2016.
Hyun Oh Song, Stefanie Jegelka, Vivek Rathod, and Kevin Murphy. Deep metric learning via facility location. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 5382-5390, 2017.
Michael Opitz, Georg Waltner, Horst Possegger, and Horst Bischof. Deep metric learning with bier: Boosting independent embeddings robustly. IEEE transactions pattern analysis and machine intelligence, 2018
Qi Qian, Rong Jin, Shenghuo Zhu, and Yuanqing Lin. Fine- Eine-grained visual categorization via multi- stage metric learning. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2015.
Qi Qian, Jiasheng Tang, Hao Li, Shenghuo Zhu, and Rong Jin. Large-scale distance metric learn- ing with uncertainty. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8542-8550, 2018
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face the IEEE conference on computer vision and pattern
recognition and clustering. In Proceedings the recognition, pp. 815-823, 2015.
Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In ICML., pp. 793- 801, 2016.
Hailin Shi, Yang Yang, Xiangyu Zhu. Shengcai Liao, Zhen Lei. Weishi Zheng, and Stan Z Li. Embedding deep metric for person re-identification: A study against large variations. In European conference on computer vision, pp. 732-748. Springer, 2016.
10

---

Under review as a conference paper at ICLR 2020
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In Advances in Neural Information Processing Systems, pp. 1857-1865, 2016.
Jian Wang, Feng Zhou, Shilei Wen, Xiao Liu, and Yuanqing Lin. Deep metrie learning with angular loss. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2593-2601, 2017.
Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew R Scott. Multi-similarity loss with general pair weighting for deep metric learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5022-5030, 2019.
Chao-Yual Yuan Wu, Manmatha, Alexander Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE International Conference Computer Vision, pp. 2840-2848, 2017.
Yi, Lei, and SZ Li. Deep metric learning for practical person re-identification (2014). ArXiv e-prints.
Rui Yu, Zhiyong Dou, Song Bai, Zhaoxiang Zhang, Yongchao Xu, and Xiang Bai. Hard-aware point-to-set deep metric for person re-identification. In Proceedings the European Conference on Computer Vision (ECCV), pp. 188-204, 2018.
Dixian Zhu, Zhe Li, Xiaoyu Wang, Boqing Gong, and Tianbao Yang. A robust zero-sum game framework for pool-based active learning. In The 22nd International Conference on Artificial Intelligence and Statisties, pp. 517-526, 2019.
SUPPLEMENTARY
6.1 DERIVATION OF RECOVER SOTA LOSSES
In this section, show how DRO framework recovers SOTA loss functions, LS loss and MS loss. Their definitions are as follows, respectively.
LLS
Σ llog Σ
A-S.
S.h + log Σ
Sa-
+1
kEP:
keN,
where À is the margin paramerrr.eeer...
LMS Σ
log +
e
-a(Su -a]
log + Σ ((Six-A))
(9)
kEP,
KEN,
where is the margin parammer and a and 3 are coefficient hyper-parameters.
6.1.1 LS LOSS UNDER OUR FRAMEWORK
Recall that the objective function decomposable terms p; = =pp,t p. RR We denote the Pij = f when j E P,, and Pij = Pij when j N₁ for simplicity. The Lagrangian function of can be represented as:
C(p.v) v) Σ C(pa, ,,),
(10)
where
((p.ett07)) Σ (i)li;()) + y5. DxI.
v, (pr
P.
N1
jEP:UNG
(11)
w Σ
Pij 1) 17 Σ
Pij 1)-
jEP.
JEM,
11

---

Under review as a conference paper at ICLR 2020
According to KKT conditions, of" and v; are the optimal solutions of the dual function, and P the optimal solution of the primal problem if and only if
dC dp:
0,
(12)
Pij
Σ
Pij"
-1 =0.
(13)
JEP.
JEN,
We first derive P terms of of ii using equation 12) i.c.
dC (0) + 75- log(np, 7, log(np;;) + 7:t 1 + 7.
+ +, (14)
dp;
where (,) = {4. (0), lpl uN! (0)) 1 E RP..l 1 E Rl Then the closed form of
for positive pairs and negative pairs can be written as follows
(15)
Pgj
Pij
W e
P
Substitute plj Pij
into equation
13
which means 2/" and is need satisfy:
uu
- = O.
(16)
P.
W
JEP:
JEN;
Even though equal (16) also equals to O when of* = 0 or i. = 0, or uj = =/-² 0, but the corresponding optimal solution P will not meet the equality constraints, i.e, EjEp, Pij Σjep, Ptj 1, in the original formulation Therefore, only have
+ = 1 and
Σ JEP,
=1, 1,
Σ JEN:
(17)
P
N
Then from equation 17
we can get
y log
1) 2/ = v log
Σ JEN
(9) 7
P
N
(18)
JEP:
Plugging them into 15) and apply margin loss as the base loss function for each pair, 4,( [m + Vig (X S. we successfully derive the weighting representation of LS loss:
(m+(A-5
Big
Pij
[++(A-8ue1++
Σ kEP;
Σ
Σ kEP.
kEP:
(19)
1ay(0)
el
(S -1]1+
Bi
Pij
(0)
10+ -811+
Σ kEN,
e
Σ
Σ
7
REN:
KEN:
Thus, when updating the model parameter we are going to minimize the following objective function:
g(0,p") Σ Σ
(0)
JEP,UN,
(20)
Σ
p
(0)
Σ
pij (0)
jEP.
JEN,
12

---

Under review as a conference paper at ICLR 2020
Taking the gradients to equation 20 in terms of 8, get:
@g(O, p²)
aSe
B
[Sij
Poj
Pij
(21)
00
00
00
JEP:
JEN:
Similarly, we take gradients to the LLS loss function
OCLS
B
aSa
B
aSig
00
B 5ix
00
B
00
(22)
JEP:
JEN;
e
Si
kEP.
REN.
that equation alent. This shows our DRO framework successfully recovers the LS loss by setting the uncertainty decision set U in equation
By substituting equation 19) into equation (26..
22 and (2) equiv-
6.1.2 MS LOSS UNDER OUR FRAMEWORK
MS Ioss, combination of binomial loss and LS loss, can also be formulated into our DRO frame- work. LS loss only considers the lifted structure between pairs, while binomial loss focusing on the intrinsic property of an independent pair while encoding the pair class information. To recover MS loss under our framework, we re-define p [0, 1] +N+++0+ +2B by adding
more element to P; and p; Therefore, now we have D [0, 1] +1 and p; E [0, 1] +1, where the newly added element corresponds to a zero loss, and thus does not contribute to the computation of overall loss. Then based on the formulation of LS loss, the formulation MS loss can be written as:
max [E|0.1]P+++0
Σ
Σ
Piylis(0) 75t DKL (Pill
P.l 75 DKL (P. Wi (1(+1²)
1
+o++++++++ +22
i=1
jEPIUN:
s.t. Σ Pij 11
Σ
Pik 1,i [B].
JEP:+1
kEN++1
(23)
Note that
Σ
(() + P
0 PT,tt 0
Σ
Piglay (0), vi E [B].
(24)
JEP
JEP.+IUM++1
As the analysis of LS loss we can also obtain the representation of MS loss under our DRO frame- work from formulation i.e.,
4g (0)
[m+ Sty 1+
?
Myy
Pij
[m++A 11+01--101----
Σ kEP
e
1+ Σ e
Σ
e
-
kEP:
kEP.
(25)
li
(m+ A
e
Viy --
%
Pij
likk
bo (8.k All
Sin 813
e
1+
Σ e
76
Ke
KEP;
KEA,
where et, e_, Vo Mi are hyperpatmeters. Similar to LS loss waking the gradients to (g p²) in terms of f, we can get:
@g p'
B
asyy
B
aS
Σ
Pij
Σ
Pij
(26)
00
00
00
1=1
JEP,
jEN;
Similarly, we take gradients to the LMS loss function
غLLS 00
Σ
Σ
aS.j +
Σ
aS,
B
00
B
00
1=1
jEP.
ea(S, + Σ
ca(S Saa)
JeNi
((A-
+
Σ
(Sa
-Sa--81))
kEP:
KEN;
(27)
13

---

Under review as a conference paper at ICLR 2020
By substituting (5 into (21 and set ct X + m, = À - m - 2 3. [B]. is
obvious show equation and (27 are the same. As result, DRO framework also recovers the MS loss.
6.1.3 RECOVERING OF HAP2S E YUETTA AL. 2018
Yu al. (2018) provides an hardaware point to set (HAP2S) triplet loss with an adaptive hard mining scheme to address the sensitive issue caused by mining the hardest positive pair and negative pair Heermans al. (2017). The key HAP2S loss is assign different weights the points in P: and N; for each anchor x,. We show that our DRO framework is able to recover HAP2S with exponential weighting scheme by exactly using the DRO formulation equation (7 for LS loss.
The triplet loss is defined as follows:
Lirp
Σ Dy
18th Sij + m]+
(28)
NO
where [x]++ m)) Sty and Sikk denote the similarity of positive pair (x, negative pair {x,, 1b E NN for the same anchor x,, .N, is the number of all possible triplets in the mini-batch. Without causing ambiguity. S =S when j E P.. Sij = S.y. when j E M, Similar to pair losses, such as margin loss and binomial loss, there exist huge amount of triplets in batch that have no contribution to the Lirp. As result, pair mining is critical to improve the performance of the model.
P..
Hermans et al. (017)) provide a variant of triplet loss by selecting the hardest positive pair and the hardest negative pair for each anchor. The formulation can be written as:
1 LirpBH B
Σ
max Siz min Sig + m]+ JEN. JEP,
(29)
The state-of-the-art results on two large-scale datasets has been reported based on this variant of triplet loss. However, equation (29) is sensitive to outliers which usually serve as the hardest sample. To increase the robustness the model, HAP2S triplet loss has been proposed Yu et al. (2018):
LHAP2S
S
S + m]+
(30)
B a=1
where
Σ
S
Σ s
bj
J
REN
S
JEP
(31)
Σ JEN,
4.j
Σ
JEP.
where di is the weights designed to each pair, for which they propose two variants of weighting schemes for HAP2S, i.e., exponential weighting and polynomial weighting. Here we show that our DRO formulation is able to recover the HAP2S with exponential weighting scheme (denoted by HAP2S E), i.e. the weight ūú of each pair is an exponential function over its similarity:
d exp St S Byj exp
Sij ) EN
(32)
Note that 4 and Viy are constant scalars that not involved in the gradient of LHAP2S w.r. to Substitute equation
31
and
32
into
30
B
CHAP2S
M
Σ
exp(
S
8.h
SS +
Σ
exp(
S.t-
S1y )S,,) + D
(33)
i=1
JEP:
jEN;
kEP.
kEN:
where D absorbs all constants.
14

---

Under review as a conference paper at ICLR 2020
Since Siy Scx Six Stz in the exponential function is derived from 9.j and Jij thus they also a constant scalars when taking derivative to 0. By taking derivative to AHAPSS we get:
HLHAP2S a0
1
aSi 00
1
DS.j
) (34)
B
Σ kEP;
exp(
S.
Σ REV.
exp
Sie S1g
00
jEP,
iEN;
We can see that the subgradients of CHAP2E in 34) are the same as the subgradients of LS loss in (22). As a result, LHAP2S is special case of our DRO framework.
6.2
SUPPLEMENTARY EXPERIMENTS
Mean and Std of Recall@k
Recall@k on Different P-N Ratio
DRO-TopKa
0.90
0.95
DRO-TopK-PMy
DRO-TopK
DRO-KLy
Mcan Std
0.85
DRO-TopK-PNM
@1
MS
0.86
DWSM
0.75
0.84
SHM
DRO-TepKe
0.82
DRO-TopK-PNN
DRO-KLwv
0.60
0.80
Recalig2
Recalig
Recalig
0.053
0.026
0.012
0.008
0.006
Recall@k
P-N Ratio
Figure& 4: Mean and std of Recall@t over five runs Figure 5: Recall @ I vs Imbalance Ratio embed- comparing the best baseline performer (MS)
ding space dimension 512
To investigate the effect of randomness of the stochastic algorithms and evaluate the robustness of DRO framework, we report the average mean and standard variance of recall@k Cub-200- 2011 in Figure 4 We do not plot 4 and recall@16 for better visualization. The experimental setting is the same the experiments of the SOTA quantitative results we reported in Table (sec- 1.] but with five runs. The gray bars are the @ of best performer among SOTA baselines, i.e., MS. is clear to see that all our DRO variants outperform MS in terms the average recall@k over all different values of k. Specifically, the average recall of DRO-TopK is 67.9 67.9%, which has significant improvement over the baselines, i.e., 65. 55.7% of MS. addition, the small standard deviation eтror bars imply that our DRO framework is robust enough to have better performance than SOTA methods.
To show the effect of the network architecture our DRO framework and its robustness, we addi- tionally repeat the experiments of Recall/Imbllance Ratio in section [.2.2] but with the embedding space dimensions 512 (rather than 1024 in Section 4.2.2). The results are illustrated in Figure 5 In comparison with the performance of recall@1 1 on embedding space dimensions 1024 in Figure] we see that the fluctuations of recall@1 ding changes from 1024 to 512. For example, the recall@1 only changes, from 0,9046 to 0.9058 for DRO-TopK.M from 0.9086 to 0.9073 for DRO-Topk Too-TopK-PPP -N from 0.9018 0.9021 for DRO-KLM, when PN-Ratio is 0.006. Further, the trends of different methods imply that our DRO framework consistently achieve competitive even best results compared with other SOTA methods (SH and DWS) under different embedding space dimensions. Since different P-N Ratios in corresponding batchsizes {80, 160, 320, 480, 640), the above experimental results verify that our methods are not too sensitive to the embedding space dimensions in different batchsizes, and also outperform other SOTA mining methods different embedding space dimensions. In contrast, shows that the baseline DWS is relatively more sensitive to the embedding space dimension. In Figure where embedding space dimension set to 512, DWS has a smaller performance drop from P-N ration = 0.012 to 0.006, while in Figure [ where the embedding space dimension is 1024, DWS encoun- ters a much larger performance decrease.
different PN-Ratios are sublet when the feature embed-
15


Reviews:
[{"review_id": "SyevOXVstr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors address the (increasingly popular) problem of learning a metric from a given multi-dimensional data set. They consider the deep metric learning setup, where target distances are defined as the euclidean distances in an artificial feature space (created by a deep neural network). Main focus of the paper is to cases where the data set is affected by a substantial imbalance between the amount of examples that are similar to each other and the total number of examples.\n\nI would tend to accept the paper because handling the imbalance problem in metric learning is important and both the theoretical analysis and the experiments show that the proposed method may have some impact.\n\nThe idea of reducing the problem to a binary classification between similar and dissimilar examples may look too simple but i) is a common approach in deep metric learning, ii) helps to handle the implicit imbalance problem and iii) suggests possible generalisations to other network-based problems (for example, where similarity is naturally defined by the existence of absence of a link). Showing that many complicated losses are equivalent to DRO may also help the general understanding of the metric learning task.\n\nMy main concerns are about the net contribution of the paper. Tackling the imbalance problem is important but it is not clear whether the full metric learning setup is really needed. The authors could have stated more precisely in what sense the metric learning unbalanced problem they consider is different from usual unbalanced binary classification. Otherwise, as DRO is well known, it is hard to identify the real novelty of their method.\n\nQuestions: \n- how does the specific metric learning setup make the considered DRO different from usual unbalanced classification? \n- how the network architecture affects the performance? For example, would the size of the embedding space change the recall/imbalance plot? \n- Is the choice of euclidean distances standard in deep metric learning? Would a choice of more general distances be incorporated in the proposed method?\n \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJgZmWvTtr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper casts deep metric learning (DML) as a pairwise binary classification problem such that pairs of examples need to be classified as similar or dissimilar. The authors propose an objective function that computes a weighted sum over the pairwise losses in a mini-batch. The weight vector is selected to maximize the objective from a decision set encoding constraints. This formulation is called the distributionally robust optimization (DRO) framework.\n\nThe authors argue that the DRO framework is theoretically justified by showing how certain decision sets result in existing machine learning loss functions. This portion of the paper seemed hand-wavy. It is not clear what is the purpose of including the theorem from Namkoon & Duchi. It would be more clear in my view to just make the short point that a certain decision set recovers the DRO with f-divergence as would be expected. The claims with regard to learning theory are over-stated in the paper.\n\nThe authors proposed three variants of the general framework. They include a top-K formulation, a variance-regularized version, and a top-K version using a balance between positive and negative examples. The DRO framework and the variants are the main contributions in terms of methodology in this paper. It is also shown that the framework generalizes more complicated recently proposed losses.\n\nThe experiments demonstrate the DRO framework consistently outperforms state of the art deep metric learning methods on benchmark datasets by small margins. There is also a computational speed advantage that is shown.\nOverall, this paper shows that the ideas from distributionally robust optimization work well in deep metric learning. In particular, the paper shows that by combining the DRO framework with simple loss functions, performance comparable with complicated loss functions can be obtained. This aspect, along with the generality are the main strong suits. That being said, I do not see this paper to be that significant of a contribution. The main idea in the paper seems like a rather direct application of the DRO modeling framework and it does not provide too significant of improvement over the MS loss.  The paper was not written super clearly and was too long. Reviewers were instructed to apply a higher standard to papers in excess of 8 pages and this paper would have been presented more effectively if it was shorter. For these reasons, I recommended a weak reject.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lyrJVHtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework for deep metric learning. Using ideas from distributionally robust optimization, the loss (in each batch) is the worst case weighted average of all pairwise classification losses, taken over an uncertainty set of possible weights. The framework is shown to be general and encompass various previous approaches. Based on it, the authors propose several new algorithms, which are shown to outperform the SOTA on image retrieval data sets in terms of recall.\n\nThe main contribution of the paper is a unification of previous deep metric learning algorithms, which would be helpful to the community and could inspire new approaches. I found the empirical observation that the proposed algorithms are able to reduce the computation time by nearly half to be compelling. However, apart from DRO-TopK-PN, the proposed algorithms appear to be minor modifications of existing algorithms. \n\nQuestions about the experimental protocol:\n1. Are the results from one run, or averaged over several? Standard errors of the evaluation metrics would be very helpful to judge the improvements made by the algorithms, especially as the algorithms are stochastic due to batching. \n2. The proposed algorithms seem to be similar to those of Fan et al. (2017) and Namkoong and Duchi (2017). Is there a particular reason why they weren’t included in the experiments? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this is a reasonable paper but somewhat derivative. The authors discussed the contribution further in the rebuttal, but even in light of their comments, I consider the significance of this work too low for acceptance.
Decision: Reject