Title: A SIMPLE AND EFFECTIVE FRAMEWORK FOR PAIR-WISE DEEP METRIC LEARNING

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 problemimbalanced 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 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.

1. INTRODUCTION:

Metric Learning aims to learn a metric to measure the distance between examples that captures certain notion of human-defined similarity between examples. Deep metric learning (DML) has emerged as an effective approach for learning a metric by training a deep neural network. Simply speaking, a deep neural network can induce new feature embedding of examples and it is trained in such a 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. (2018) ; Wang et al. (2017) ). 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 (LS) loss (Oh Song et al. (2016) ), N-pair loss (Sohn (2016) ), triplet loss (Schroff et al. (2015) ), multi-similarity (MS) loss (Wang et al. (2019) . The major difference between these pair-based losses lies at 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, a positive pair interacts with all negative pairs. In LS loss and MS loss, a 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 2 ) or O(N 3 ) 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 a minibatch to update the model. To combat this issue, various pair mining methods have been proposed to complement the design of loss function, such as hard (semi-hard) mining for triplet loss (Schroff 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 a 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 to provide a 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 as follows:

• We propose a general solution framework for DML, 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 distributional 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. Experimental 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 at how to group the pairs. N-pair loss put one positive pair and all negative pairs together, Lifted-structure 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 a 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 pair mining methods have been proposed, including semihard 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, Schroff et al. (2015) selects the hard negative pairs whose distance is smaller than that between the positive pairs in triplets, Shi et al. (2016) 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 according to their distance distribution within a batch. The proposed DRO framework induce a pair sampling method by using the optimal distributional variables that defines the robust loss over pairs within a mini-batch. As a 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 in machine learning which have tackled the imbalanced issue. Commonly used tricks include over-sampling, under-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-Shwartz & Wexler, 2016) , minimizing top-k losses (Fan et al., 2017) and minimizing variance-regularized 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 a mini-batch of examples, which inherits the theoretical explanation 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-regularized 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 DML. 

Preliminaries. Let x ∈ R D denote

(θ) = 1 B 2 B i=1 B j=1 l ij (θ).

However, this approach will suffer from the severe imbalanced issue, i.e., most pairs are negative pairs. The gradient of F avg will be dominated by that of negative pairs.

3.1. GENERAL DRO-BASED FRAMEWORK:

To address the imbalanced pair issue, we propose a general DRO formulation to compute a robust loss. The formulation of our DRO-based loss over all pairs within a mini-batch is given below:

EQUATION

where p ∈ R B 2 + is a non-negative vector with each element p ij representing a weight for an individual pair.

U ⊆ R B 2

denotes the decision set of p, which encodes some prior knowledge about p. In the literature of DRO Namkoong & Duchi (2017) , p is interpreted as a probability vector such that ij p ij = 1 called the distributional variable and U denotes the uncertainty set that specifies how p deviates from the uniform probabilities (1/B 2 , . . . , 1/B 2 ). 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 (1) to exiting works in machine learning by considering three different uncertainty sets for p. First, we can consider a simple constraint U = ∆ = {p ij ≥ 0, ij p ij = 1}. As a result, F (θ) = max ij l ij (θ) becomes the maximal loss over all pairs. Shalev-Shwartz & Wexler (2016) shows that minimizing maximum loss is robust to imbalanced data distributions and also derives better generalization error for imbalanced data with a 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-regularized loss (Namkoong & Duchi, 2017) are proposed, which can be induced by the above DRO framework.

If we set U = { ij p ij = 1, 0 ≤ p ij ≤ 1/K}, F will become the top-K loss F (θ) = 1 K K i=1 l [i] (θ), where l [i] (θ) denotes the i-th largest loss over all pairs. If we set U φ = {p ∈ ∆, D φ (p 1/B 2 ) ≤ ρ B 2 }, where D φ (p p ) = φ( dp dp

)dp is the φ-divergence between two distributions p and p with φ(t) = 1 2 (t -1) 2 , then the DRO-based loss becomes the variance-regularized loss under certain condition about the variance of the random loss, i.e., for a set of i.i.d random losses { 1 , ..., n }(n = B 2 ) we could have

sup p∈U φ n i=1 p i i = 1 n n i=1 i + 2ρVar n ( ) n ,

where Var n ( ) denotes the empirical variance of 1 , ..., n . 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 varianceregularized 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 to update the model parameter θ based on the robust loss F (θ) defined by (1). A simple approach is to find an optimal distributional variable p * to (1) and then update θ according to the subgradient of weighted loss by ∂ θ g(θ, p * ) = ij p * ij ∇l ij (θ), which is justified by the following lemma. Lemma 1 Assume that g is proper, lower-semicontinuous in θ and level-bounded in p locally uniformly in θ. Then the subgradient ∂F (θ) ⊂ p * ∈P * (θ) ∂ θ g(θ, p * ), where P * (θ) denotes the optimal solution set of the maximization problem in (1). Furthermore, when l ij (θ) is smooth in θ and P * (θ) is a singleton, i.e., p * = arg max p g(θ, p) is unique, we have ∂F (θ) = ∂ θ g(θ, p * ).

Remark 1:

The above lemma can be proved by Theorem 10.13 in Rockafellar & Wets (2009) . It shows that even if we may not directly compute ∂F (θ), our framework can at least obtain its superset ∂ θ g(θ, p * ). Particularly, if we have additional conditions, i.e., l ij (θ) is smooth in θ and the optimal solution p * is unique (considering our regularized formulation below), it theoretically guarantees that our framework exactly computes ∂F (θ).

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 i that serves as an anchor data, let 

P i = {j|y ij = 1, j ∈ [B]} and N i = {j|y ij = 0, j ∈ [B]}

p ij l ij (θ), s.t. B i=1 j∈Pi∪Ni p ij = 1, 0 ≤ p ij ≤ 1/K,

where K is a hyper-parameter. 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-regularized loss. Instead of specifying the uncertainty set U φ , we use a regularization term for the ease of computation, which is defined by DRO-KL: max

p∈R P +N + B i=1 j∈Pi∪Ni p ij l ij (θ) -γD KL (p|| 1 P + N ), s.t. B i=1 j∈Pi∪Ni p ij = 1,

where γ > 0 is a hyper-parameter and D KL denotes the KL divergence between two probabilities. The optimal solution to p can be easily computed following Namkoong & Duchi (2016) . It is notable that the optimal solution p * is not necessarily sparse. Hence, computing ij p * ij ∇l ij (θ) 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 a 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 is explicitly balancing the number of positive pairs and negative pairs by choosing top K/2 pairs for each class, which is denoted by DRO-TopK-PN:

DRO-TopK-PN: max p∈{0,1} P +N B i=1 j∈Pi∪Ni p ij l ij (θ), s.t. B i=1 j∈Pi p ij ≤ K 2 , B i=1 j∈Ni p ij ≤ K 2 .

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-BASED LOSS:

Next we show that proposed framework can recover the method based on SOTA complicated losses. With the induced feature vector f (x; θ) normalized to have unit norm, we define the similarity of two samples as S ij := f (x i ; θ), f (x j ; θ) , where •, • denotes dot product. Specifically, we consider two SOTA loss functions, LS and MS loss, which are defined below:

EQUATION

EQUATION

where α, β, λ are hyper-parameters of these losses.

The key to our argument is that the gradient computed based on these losses can be exactly computed according to our DRO framework by choosing appropriate constrained set U and setting the pairwise loss as 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) :

EQUATION

which can be alternatively written as

EQUATION

It can be shown that for LS loss, derivations are provided in the supplementary, we have

EQUATION

)

To recover the gradient of the LS loss under our DRO framework, we employ the pairwise margin loss for l ij (θ), i.e., l ij (θ) = [m + y ij (λ -S ij )] + , where m and λ are two hyper-parameters and [a] + = max{0, a}. Assume that the margin parameter m is sufficiently large such that l ij (θ) > 0 for all pairs. The key to deriving the same gradient of the LS loss under our framework is to group distributional variables in p for the positive and negative pairs according to the anchor data. Let p + i ∈ R Pi and p - i ∈ R Ni denote the corresponding vectors of positive and negative pairs for the anchor x i , respectively. Let us consider the following DRO formulation:

EQUATION

where γ + i ≥ 0 and γ - i ≥ 0 for i ∈ [B] are hyper-parameters. we can easily derive the closed-form solution for p * , i.e., p + * ij =

EQUATION

p - * ij = 1 k∈N i e (S ik -S ij )/γ - i .

Then computing the gradient of the robust loss with respect to θ by using the above optimal p * , we have:

∂F (θ) = B i=1 j∈Ni p - * ij ∂S ij ∂θ - j∈Pi p + * ij ∂S ij ∂θ

which exactly recover the gradient in (6) by setting γ + i = γ - i = 1. Finally, we can recover the gradient based on the MS loss in a very similar way. The difference is to add a pseudo positive pair and pseudo negative pair with 0 loss for each anchor x i , and augment each p + i and p - i by one additional dimension. The details are provided in the supplementary. Table 1 and 3 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 outperform all other SOTA methods in bold. We can see that our five variants outperform other SOTA methods on recall@1 on all three datasets. Particularly on Cars-196, our five variants outperforms other SOTA methods on all recall@k measures. On Cub-200-2011, DRO-TopK B achieves a higher recall@1 (improving 2.4 in recall@1) than the best SOTA, MS. On Cars-196, DRO-KL M has the best performance, which improves 2.3 and 1.2 in recall@1 compared to the best non-ensemble SOTA, MS, and the best ensemble SOTA, ABE. On In-Shop, DRO-TopK-PN M 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. In Section 3.3, we theoretically show that LS loss and MS loss can be viewed as special cases of our DRO framework. In this experiment, we aim to empirically demonstrate that our framework is general enough and recovers LS loss. Specifically, we would show 1) when γ = 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 hyper-parameter, and 3) our generalized LS loss outperforms MS loss, even though the performance of the ordinary LS loss is inferior to that of MS loss.

4. EXPERIMENTS:



4.2. ABLATION STUDY 4.2.1 COMPARISON WITH LS LOSS AND MS LOSS:

We adopt the set up of embedding dimension and batchsize in the ablation study of Wang et al. (2019) , i.e., d = 64 and B = 80. Therefore, we report the existing results of MS and LS loss presented in Wang et al. (2019) on Cars-196. For Cub-200-2011 and  In-Shop, we implement MS and LS 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 ( 7), and denote this variant of DRO framework as DRO-KL-G. We set

γ + i = γ - i = γ = {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. Cub-200-2011, Cars-196 and In-Shop, respectively. As 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. (2019) . When γ = 1, our method performs similarly to LS loss, which verifies that our method recovers LS loss. Furthermore, when we treat γ as a hyper-parameter (especially γ = 0.001) and regard our framework as generalized 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. 

Table 2 and 3 show experiment results on:



4.2.2. CAPACITY TO HANDLE PAIR IMBALANCE.:

In this experiment, we compare our DRO framework with different sampling methods, i.e., semihard (SH) and DWS, in terms of sensitivity to the imbalance ratio. By setting different batchsizes B ∈ {80, 160, 320, 480, 640}, we have different positive-negative pair ratios |P| : |N | ∈ {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 is originally designed for triplet loss. Since there is no straightforward choice for the positive pair, we use λ as the upper bound to simulate the similarity of the positive pair in triplet loss. For DWS, we follow the parameter setting in the original paper (Wu et al. (2017) ). We apply margin loss in the proposed three variants our DRO framework, which are denoted by DRO-TopK M , DRO-TopK-PN M and DRO-KL M , respectively. We set K = 2 * B both for DRO-TopK M , DRO-TopK-PN M . We evaluate recall@1 of all methods and report results in Figure 1 .

Figure 1 shows that the DWS has better performance when the positive-negative pair ratio is relatively large, and encounters a 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 M and DRO-KL M have similar performance, with SH on all positive-negative pair ratios, while they perform slightly better than SH when the positive-negative ratios are small. DRO-TopK-PN M constantly outperforms all other methods. The reason why DWS performs poorly when the positivenegative 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 recall@1 as the positive-negative ratio increases. These two observations together demonstrate the effectiveness of our DRO framework to handle pair imbalance.

4.2.3. SENSITIVITY OF K IN TOP-K:

As we mentioned in section 1, selecting too many pairs within a 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 framework-how the performance of our DRO framework is 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 |N | = 198080. We set K from the range {640, 960, 1280, 1600, 1920, 2560} and evaluate recall@k for models trained by different K. We choose the above range of K according to the number of pairs selected by DWS and SH in Section 4.2.2 (both selects 2560 pairs roughly).

Figure 2 illustrates how different values of K affect recall@k 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 a reasonably large range. Recall@k Recall@k with Different K on In-shop Recall@1 Recall@10 Recall@20 Recall@30 Recall@40 Recall@50 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-based mining methods and losses. For all of our three variants, pairs are selected directly from all the pairs, while additional cost is required to 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. In contrast, SH requires to compare negative pairs with the lower and upper bound of an interval at each iteration for each anchor, which increases the computational burden. It can be the reason why SH is slower than DWS.

5. CONCLUSION:

In this paper, we cast DML as a simple pairwise binary classification problem and formulate it as a DRO framework. Compared to existing DML methods that leverage all pairs in a 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 us to recover the state-of-the-art loss functions. Experiments show that our framework outperforms the state-of-the-art DML methods on benchmark datasets. We also empirically demonstrate that our framework is efficient, general and flexible.

6. SUPPLEMENTARY:

6.1 DERIVATION OF RECOVER SOTA LOSSES

In this section, we show how our DRO framework recovers SOTA loss functions, LS loss and MS loss. Their definitions are as follows, respectively.

EQUATION

)

where λ is the margin hyper-parameter.

L M S = 1 n n i=1 { 1 α log[1 + k∈Pi e -α(S ik -λ) ] + 1 β log[1 + k∈Ni e β(S ik -λ) ]} (9)

where λ is the margin hyper-parameter and α and β are coefficient hyper-parameters.

6.1.1. LS LOSS UNDER OUR FRAMEWORK:

Recall that the objective function is decomposable in terms of

p i = [p + i , p - i ] ∈ R Pi+Ni .

We denote the p ij = p + ij when j ∈ P i , and p ij = p - ij when j ∈ N i for simplicity. The Lagrangian function of (7) can be represented as:

EQUATION

where

EQUATION

Under review as a conference paper at ICLR 2020 According to KKT conditions, v + * i and v - * i are the optimal solutions of the dual function, and p * i is the optimal solution of the primal problem (7), if and only if

EQUATION

EQUATION

)

We first derive p * i in terms of v + i , v - i using equation ( 12), i.e.:

dL dp * i = -l i (θ) + γ + i log(np + * i ) + γ - i log(np - * i ) + γ + i 1 + + γ - i 1 -+ v + i 1 + + v - i 1 -= 0 (14)

where

l i (θ) = {l i1 (θ), • • • , l i|p + i ∪N + i | (θ)}, 1 + ∈ R |Pi| , 1 -∈ R |Ni| .

Then the closed form of p * i for positive pairs and negative pairs can be written as follows

EQUATION

)

Substitute p + * ij , p - * ij into equation ( 13), which means v + * i and v - * i need to satisfy:

EQUATION

Even though equal ( 16) also equals to 0 when v

+ * i = 0 or v - * i = 0, or v + * i = v - * i = 0

, but the corresponding optimal solution p * i will not meet the equality constraints, i.e., j∈Pi p + * ij = 1 and j∈Pi p + * ij = 1, in the original formulation (7). Therefore, we only have

EQUATION

Then from equation ( 17), we can get

EQUATION

Plugging them into (15) and apply margin loss as the base loss function for each pair, l ij (θ) = [m + y ij (λ -S ij )] + , we successfully derive the weighting representation of LS loss:

EQUATION

Thus, when updating the model parameter θ, we are going to minimize the following objective function:

EQUATION

Taking the gradients to equation 20 in terms of θ, we can get:

EQUATION

Similarly, we take gradients to the L LS loss function (8):

EQUATION

By substituting equation ( 19) into equation ( 26), we can see that equation ( 22) and ( 26) are equivalent. This shows our DRO framework successfully recovers the LS loss by setting the uncertainty decision set U in equation ( 7).

6.1.2 MS LOSS UNDER OUR FRAMEWORK MS loss, a combination of binomial loss and LS loss, can also be formulated into our DRO framework. 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] P + +N + +2B by adding one more element to P i and p - i . Therefore, now we have p

+ i ∈ [0, 1] P + i +1 and p - i ∈ [0, 1] N + i +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 of MS loss can be written as:

EQUATION

As the analysis of LS loss, we can also obtain the representation of MS loss under our DRO framework from formulation (23), i.e.,

EQUATION

where c + , c -, γ + i , γ - i are hyperpatmeters. Similar to LS loss, waking the gradients to ∂g(θ, p * ) in terms of θ, we can get: Since S ij -S ik , S ik -S ij in the exponential function is derived from q + ij and q - ij , thus they are also a constant scalars when taking derivative to θ. By taking derivative to L HAP 2S , we get:

EQUATION

We can see that the subgradients of L HAP 2E in (34) are the same as the subgradients of LS loss in ( 22). As a result, L HAP 2S is a special case of our DRO framework.

6.2. SUPPLEMENTARY EXPERIMENTS:

Recall@1 Recall@2 Recall@8 Recall@32

Recall@k To investigate the effect of randomness of the stochastic algorithms and evaluate the robustness of our DRO framework, we report the average mean and standard variance of recall@k on Cub-200-2011 in Figure 4 . We do not plot recall@4 and recall@16 for better visualization. The experimental setting is the same as the experiments of the SOTA quantitative results we reported in Table 1 (section 4.1) but with five runs. The gray bars are the recall@k of best performer among SOTA baselines, i.e., MS. It is clear to see that all our DRO variants outperform MS in terms of the average recall@k over all different values of k. Specifically, the average recall@1 of DRO-TopK B is 67.9%, which has a significant improvement over the baselines, i.e., 65.7% of MS. In addition, the small standard deviation error bars imply that our DRO framework is robust enough to have a better performance than SOTA methods.

To show the effect of the network architecture to our DRO framework and its robustness, we additionally repeat the experiments of Recall/Imbalance Ratio in section 4.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 on embedding space dimensions 1024 in Figure 1 , we can see that the fluctuations of recall@1 on different PN-Ratios are sublet when the feature embedding 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-PN M , from 0.9018 to 0.9021 for DRO-KL M , when PN-Ratio is 0.006. Further, the trends of different methods imply that our DRO framework can 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 to 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 in different embedding space dimensions. In contrast, it shows that the baseline DWS is relatively more sensitive to the embedding space dimension. In Figure 5 where embedding space dimension is set to 512, DWS has a smaller performance drop from P-N ration = 0.012 to 0.006, while in Figure 1 where the embedding space dimension is 1024, DWS encounters a much larger performance decrease.

:

For simplicity, we consider all pairs including self-pair.

Figures and Tables:

denote the index sets of positive and negative pairs, respectively. Let P = B i=1 P i and N = B i=1 N i . We denote the cardinality of a set by P = |P|. For simplicity, we let P i = |P i |, N i = |N i |, P = |P| and N = |N |. 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-largest losses, which is equivalent to the following DRO formulation: DRO-TopK: max p B i=1 j∈Pi∪Ni

Our methods was implemented by Pytorch and using BN-Inception network(Ioffe & Szegedy (2015)) pre-trained on ImageNet ILSVRC(Russakovsky et al. (2015)) to fairly compare with other works. The same as(Wang et al. (2019)), a 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 -5 learning rate was used for all our experiments.We verify our DRO framework on image retrieval task with three standard datasets,Cub-200-2011,  Cars-196  and In-Shop. These three datasets are split according to the standard protocol. For Cub-200-2011, 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 a 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 = {1, 2, 4, 8, 16, 32} on Cub-200-2011 and Car-196, and k = {1, 10, 20, 30, 40, 50} on In-Shop. We apply margin loss (L M ) and binomial loss (L B , Yi et al.) as base losses for our DRO framework. m is the margin in L M . λ is the threshold for both L M and L B . α and β are hyperparameters in L B . 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 et al. (2018); Kim et al. (2018); Opitz et al. (2018); Ge (2018); Harwood et al. (2017); Wu et al. (2017); 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 psampling. Thus, it makes totally five variants of our DRO framework, denoted by DRO-TopK M , DRO-TopK B , DRO-TopK-PN M , DRO-TopK-PN B and DRO-KL M , 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 B = 80 onCub-200-2011 and  Cars-196, B = 640 on In-Shop. γ is tuned from the range = {0.1 : 0.2 : 0.9} on all three

Figure 1: Recall vs Imbalance Ratio

Figure 2: The effects of K on recall@k on In-Shop

take gradients to the L M S loss function (9):Sij -λ) + B k∈Pi e α(Sij -S ik ) ∂S ij ∂θ + j∈Ni 1 e β(λ-Sij ) + B k∈Ni e β(S ik -Sij ) ∂S ij ∂θ(27)

Figure 4: Mean and std of Recall@k over five runs comparing the best baseline performer (MS)

an input data (e.g., image) and f (•; θ) : R D → R d denote the feature embedding function defined by a deep neural network parameterized by θ. (x j ; θ), y ij ) denote the pairwise classification loss between x i and x j in the embedding space (e.g., margin loss Wu et al. (2017), binomial lossYi et al.). A naive approach for DML is to use the averaged loss over all pairs, i.e., F avg

Table content: <table><tr><td>The cen-</td></tr><tr><td>tral task in DML is to update the model parameter θ by leveraging pairs of similar and dissimilar</td></tr><tr><td>examples. Following most existing works, at each iteration we will sample a mini-batch of exam-</td></tr><tr><td>ples denoted by {x 1 , ..., x B }. We can construct B 2 pairs between these examples 1 , and let y ij</td></tr><tr><td>denote the label of pairs, i.e., y ij = 1 if the pair is similar (positive), and y ij = 0 if the pair is</td></tr><tr><td>dissimilar (negative). The label of pairs can be either defined by users or derived from the class</td></tr><tr><td>label of individual examples. Existing works of DML follow the same paradigm for learning the</td></tr><tr><td>deep neural network i.e., a loss function F (θ) is first defined over the pairs within a mini-batch and</td></tr><tr><td>the model parameter θ is updated by gradient-based methods. Various gradient-based methods can</td></tr><tr><td>be used, including stochastic gradient descent (SGD), stochastic momentum methods and adaptive</td></tr><tr><td>gradient methods (e.g. Adam). Taking SGD as an example, the model parameter θ can be updated</td></tr><tr><td>by θ ← θ -η∇F (θ), where η denotes the learning rate. The focus here is to how to define the loss</td></tr><tr><td>function F (θ) over all pairs within a mini-batch. As mentioned earlier, we will cast the problem as</td></tr><tr><td>simple binary classification problem, i.e., classifying a pair into positive or negative. To this end, we</td></tr><tr><td>use l ij (θ) = l(f (x i ; θ), f</td></tr></table>

Recall@k on Cub-200-2011 and Cars-196

Table content: <table><tr><td/><td/><td/><td colspan="2">Cub-200-2011</td><td/><td/><td/><td colspan="2">Cars-196</td><td/><td/><td/></tr><tr><td>Recall@k(%)</td><td>1</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td><td>1</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td></tr><tr><td>Clusetring(Oh Song et al. (2017))</td><td colspan="4">48.2 61.4 71.8 81.9</td><td>-</td><td>-</td><td colspan="4">58.1 70.6 80.3 87.8</td><td>-</td><td>-</td></tr><tr><td>HDC(Oh Song et al. (2017))</td><td colspan="12">53.6 65.7 77.0 85.6 91.5 95.5 73.7 83.2 89.5 93.8 96.7 98.4</td></tr><tr><td>Margin(Wu et al. (2017))</td><td colspan="5">63.6 74.4 83.1 90.0 94.2</td><td>-</td><td colspan="5">79.6 86.5 91.9 95.1 97.3</td><td>-</td></tr><tr><td colspan="5">Smart Mining(Harwood et al. (2017)) 49.8 62.3 74.1 83.3</td><td>-</td><td>-</td><td colspan="4">64.7 76.2 84.2 90.2</td><td>-</td><td>-</td></tr><tr><td>HDL(Ge (2018))</td><td colspan="12">57.1 68.8 78.7 86.5 92.5 95.5 81.4 88.0 92.7 95.7 97.4 99.0</td></tr><tr><td>ABIER(Opitz et al. (2018))</td><td colspan="12">57.5 68.7 78.3 86.2 91.9 95.5 82.0 89.0 93.2 96.1 97.8 98.7</td></tr><tr><td>ABE(Kim et al. (2018))</td><td colspan="4">60.6 71.5 79.8 87.4</td><td>-</td><td>-</td><td colspan="4">85.2 90.5 94.0 96.1</td><td>-</td><td>-</td></tr><tr><td>HAP2S E(Yu et al. (2018))</td><td colspan="4">56.1 68.3 79.2 86.9</td><td>-</td><td>-</td><td colspan="4">74.1 83.5 89.9 94.1</td><td>-</td><td>-</td></tr><tr><td>MS(Wang et al. (2019))</td><td colspan="12">65.7 77.0 86.3 91.3 94.8 97.0 84.1 90.4 94.0 96.5 98.0 98.9</td></tr><tr><td>DRO-TopK M (Ours)</td><td colspan="12">67.4 77.7 85.9 91.6 95.0 97.3 86.0 91.7 95.0 97.3 98.5 99.2</td></tr><tr><td>DRO-TopK B (Ours)</td><td colspan="12">68.1 78.4 86.0 91.4 95.1 97.6 85.4 91.0 94.2 96.5 98.0 99.0</td></tr><tr><td>DRO-TopK-PN M (Ours)</td><td colspan="12">67.3 77.6 85.7 91.2 95.0 97.7 86.1 91.7 95.1 97.1 98.4 99.1</td></tr><tr><td>DRO-TopK-PN B (Ours)</td><td colspan="12">67.6 77.9 86.0 91.8 95.2 97.7 86.2 91.7 95.8 97.4 98.6 99.3</td></tr><tr><td>DRO-KL M (Ours)</td><td colspan="12">67.7 78.0 86.1 91.8 95.6 97.8 86.4 91.9 95.4 97.5 98.7 99.3</td></tr><tr><td colspan="13">datasets and K is tuned from {160, 200, 240, 280} on Cub-200-2011 and Cars-196, and selected</td></tr><tr><td colspan="4">from {640, 960, 1280, 1600, 1920} on In-Shop.</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Recover of MS loss and LS loss onCub-200-2011 and Cars-196

Table content: <table><tr><td/><td/><td/><td colspan="2">Cub-200-2011</td><td/><td/><td/><td colspan="2">Cars-196</td><td/><td/><td/></tr><tr><td>Recall@K(%)</td><td>1</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td><td>1</td><td>2</td><td>4</td><td>8</td><td>16</td><td>32</td></tr><tr><td>MS</td><td colspan="10">55.6 67.7 77.4 86.3 92.1 95.8 73.2 81.5 87.6 92.6</td><td>-</td><td>-</td></tr><tr><td>LS</td><td colspan="10">56.8 67.9 77.5 85.6 91.2 95.2 69.7 79.3 86.2 91.1</td><td>-</td><td>-</td></tr><tr><td>DRO-KL-G-γ = 1</td><td colspan="12">56.4 68.3 78.9 86.3 91.7 95.8 70.5 79.8 86.6 91.6 94.9 97.1</td></tr><tr><td>DRO-KL-G-γ = 0.1</td><td colspan="12">56.8 68.7 79.0 86.6 92.1 95.9 72.5 81.9 88.1 92.3 95.4 97.3</td></tr><tr><td colspan="13">DRO-KL-G-γ = 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</td></tr><tr><td colspan="13">DRO-KL-G-γ = 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</td></tr></table>

Recall@k on In-Shop

Table content: <table><tr><td>Recall@K</td><td>1</td><td>10</td><td>20</td><td>30</td><td>40</td><td>50</td></tr><tr><td colspan="7">FashionNet(Liu et al. (2016)) 53.7 73.0 76.0 77.0 79.0 80.0</td></tr><tr><td>HDC(Oh Song et al. (2017))</td><td colspan="6">62.1 84.9 89.0 91.2 92.3 93.1</td></tr><tr><td>HDL(Ge (2018))</td><td colspan="6">80.9 94.3 95.8 97.2 97.4 97.8</td></tr><tr><td>ABIER(Opitz et al. (2018))</td><td colspan="6">83.1 95.1 96.9 97.5 97.8 98.0</td></tr><tr><td>ABE(Yu et al. (2018))</td><td colspan="6">87.3 96.7 97.9 98.2 98.5 98.7</td></tr><tr><td>MS(Wang et al. (2019))</td><td colspan="6">89.7 97.9 98.5 98.8 99.1 99.2</td></tr><tr><td>DRO-TopKM (Ours)</td><td colspan="5">91.0 98.1 98.7 99.0 99.1</td><td>99.2</td></tr><tr><td>DRO-TopKB(Ours)</td><td colspan="6">90.7 97.7 98.4 98.8 99.0 99.1</td></tr><tr><td>DRO-TopK-PNM (Ours)</td><td colspan="6">91.3 98.0 98.7 98.9 99.1 99.2</td></tr><tr><td>DRO-TopK-PNB(Ours)</td><td colspan="6">91.1 98.1 98.6 98.8 99.0 99.2</td></tr><tr><td>DRO-KLM (Ours)</td><td colspan="6">90.8 98.0 98.6 99.0 99.1 99.2</td></tr></table>

Recover of MS loss and LS loss on In-Shop

Table content: <table><tr><td>Recall@K(%)</td><td>1</td><td>10</td><td>20</td><td>30</td><td>40</td><td>50</td></tr><tr><td>MS</td><td colspan="6">79.8 94.9 96.8 97.6 97.9 98.3</td></tr><tr><td>LS</td><td colspan="6">82.6 94.1 95.6 96.4 96.9 97.4</td></tr><tr><td>DRO-KL-G-γ = 1</td><td colspan="6">84.8 95.9 97.3 97.9 98.2 98.5</td></tr><tr><td>DRO-KL-G-γ = 0.1</td><td colspan="6">85.1 96.1 97.5 98.0 98.3 98.5</td></tr><tr><td>DRO-KL-G-γ = 0.01</td><td colspan="6">85.8 96.2 97.9 97.8 98.2 98.4</td></tr><tr><td colspan="7">DRO-KL-G-γ = 0.001 85.7 96.1 97.4 97.9 98.2 98.5</td></tr></table>

Peer review (iclr2020):
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. I 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. The 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. My 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. Questions: - how does the specific metric learning setup make the considered DRO different from usual unbalanced classification? - how the network architecture affects the performance? For example, would the size of the embedding space change the recall/imbalance plot? - Is the choice of euclidean distances standard in deep metric learning? Would a choice of more general distances be incorporated in the proposed method?