Title: ADASAMPLE: ADAPTIVE SAMPLING OF HARD POSITIVES FOR DESCRIPTOR LEARNING

Abstract: Triplet loss is commonly used in descriptor learning, where the performance heavily relies on mining triplets. Typical solution to that is first picking pairs of intraclass patches (positives) from the dataset to form batches, and then selecting inbatch negatives to construct triplets. For high-informativeness triplet collection, researchers mainly focus on mining hard negatives in the second stage, while they pay relatively less attention to constructing informative batches, i.e., matching pairs are often randomly sampled from the dataset. To address this issue, we propose AdaSample, an adaptive and online batch sampler. Specifically, we sample positives based on their informativeness, and formulate our hardness-aware positive mining pipeline within a novel maximum loss minimization training protocol. The efficacy of the proposed method is demonstrated in several standard benchmarks, in which it results in a significant and consistent performance gain on top of the existing strong baselines. The source code will be released upon acceptance.

1. INTRODUCTION:

Feature descriptors are widely used for finding correspondences (Bian et al., 2017; Yi et al., 2018) across images, and hence allow for many computer vision applications, including structure-frommotion (Agarwal et al., 2009) , image retrieval (Philbin et al., 2010) , and panorama stitching (Brown & Lowe, 2007) . Despite rich efforts made on that, the representation power of traditional descriptors, like SIFT (Lowe, 2004) , is limited. With the rapid development of deep learning, recent works (Han et al., 2015; Zagoruyko & Komodakis, 2015; Yi et al., 2016; Tian et al., 2017) show that CNN-based descriptors achieve better performance in terms of patch classification (Brown et al., 2011) . Especially, HardNet (Mishchuk et al., 2017) demonstrates the generalization ability of deeply learned descriptors in multiple vision tasks.

Learning descriptors from a large image patch collection is challenging. Other than network design and optimization, sampling informative pairs or triplets of patches is also critical. Mishchuk et al. (2017) leverage the hardest-in-batch solution to construct high-quality triplets, making significant progress on the performance and generalization ability. This demonstrates the importance of triplet sampling in descriptor learning. However, current sampling strategies focus on sampling hard triplets in batch level, while batches are randomly constructed from the dataset. We propose to construct high-informativeness batches in a more principled manner to improve the performance.

The proposed method is nominated as AdaSample, which adaptively collects informative positive pairs from the dataset for batch construction. The methodology is developed based on informativeness analysis, where we define informativeness of potential samples and estimate their optimal sampling probabilities. Moreover, we propose a novel training protocol inspired by maximum loss minimization (Shalev-Shwartz & Wexler, 2016) to boost the generalization ability of the descriptor network. We make comprehensive evaluations and ablation studies of the proposed approach in several standard benchmarks, in which the results clearly demonstrate the superiority of our method.

2. RELATED WORK:

Local Descriptor Learning. Traditional handcrafted descriptors, e.g. SIFT (Lowe, 2004) , extract low-level texture information from image patches. Due to the low representation ability, recent research has gradually been shifted to the learned descriptors. Han et al. (2015) propose a two-stage Siamese architecture to extract features and measure patch similarity, which significantly improves the performance and demonstrates the great potential of CNNs in descriptor learning. In (Zagoruyko & Komodakis, 2015) , another Siamese network is introduced to explore different network architectures with a central-surround structure to boost the performance. Simo-Serra et al. (2015) mine hard negatives and use a shallow architecture for the pairwise similarity. Balntas et al. (2016) use a triplet-based architecture and show its superiority against the pair-based one. Kumar et al. (2016) use a triplet network and a global loss function to separate the distribution of matching and non-matching pairs. L2-Net (Tian et al., 2017) uses n matching pairs in each batch to generate n(n -1) negative samples and requires that the distance of matching pairs is minimum in each row and column. HardNet (Mishchuk et al., 2017) mines the hardest-in-batch negatives and significantly improves performance. Recently, SOSNet (Tian et al., 2019a) proposes a second order similarity regularization term, and achieves more compact patch clusters in the feature space.

The triplet mining framework can generally be decomposed into two stages, i.e., batch construction from the dataset and triplet generation within the mini-batch. Previous works mainly focus on mining hard negatives in the second stage, while the first stage is often cursorily done by random sampling. Therefore, we argue that their triplet sampling solutions are still sub-optimal. To address this problem, we propose AdaSample to construct informative batches in the first place. Combined with the hardest-in-batch solution in Mishchuk et al. (2017) to mine negatives within the minibatches, we formulate a complete and powerful triplet mining framework for descriptor learning. Hard Negative Mining. Hard negative mining is widely used in object detection (Tian et al., 2019b) and other vision tasks for collecting good training examples. FaceNet (Schroff et al., 2015) proposes to sample semi-hard triplets within the batch. Wu et al. (2017) select training examples based on their relative distances. Our sampling solution differs from them in that we analyze the informativeness of the training data and ensure the most useful gradients for parameters update. Besides, our method adaptively adjusts the hard level of the selected training samples with training. Therefore, well-classified samples are filtered out, and the network is always fed with informative triplets with suitable hard levels. Comprehensive results demonstrate consistent performance improvement contributed by our proposed approach.

3. METHODOLOGY:



3.1. PROBLEM OVERVIEW:

Given a dataset that consists of N classes with each containing k patches, we decompose the triplet generation into two stages. Firstly, we select n matching pairs (positives) to form a mini-batch, where n is the batch size. This is done by proposed AdaSample, as introduced in Section 3.2. Secondly, we mine the hardest-in-batch negatives for each matching pair, and use the triplet loss to supervise the network training, as in Section 3.3. The overall solution is summarized in Section 3.4.

3.2. ADASAMPLE:

Previous works (Tian et al., 2017; Mishchuk et al., 2017) sample positives randomly to construct batches, yielding a majority of similar matching pairs which can be easily discriminated by the network. This reduces the overall "hardness" of the triplets. Motivated by the hardest-in-batch mining strategy in Mishchuk et al. (2017) , a naive solution is to select the most dissimilar matching pairs. However, this has potential issues, i.e., the network may be trained with bias in favor of dissimilar matching pairs, while other cases are less-considered. We validate this solution, nominated as Hardpos, in experiments (Section 5.3).

A more principled solution is to sample positives based on their informativeness. Here we assume that more informative pairs are those contributing more to the optimization, i.e., providing effective gradients for parameters update. Therefore, we quantify the informativeness of matching pairs by measuring their contributing gradients during training. Moreover, we employ maximum loss minimization (Shalev-Shwartz & Wexler, 2016) to improve the generalization ability of the learned model. We then show that the resulting gradient estimator is an unbiased estimator of the true gradient. In the following, we introduce our derivation and elaborate theoretical justification in Section 4.

Informativeness Based Sampling. In the end-to-end learning literature, the training data contribute to learning via gradients, so we measure the informativeness of training examples by analyz-ing their resulting gradients. Generally, we consider the generic deep learning training framework, in which each data-label pair contributes independent gradients. Let (x i , y i ) be the i th data-label pair of the training set, f (x; θ) be the model parameterized by θ, and L(•, •) be a differentiable loss function. The goal is to find the optimal model parameters θ * that minimize the average loss, i.e.,

EQUATION

where 

K

EQUATION

For simplicity, we omit the superscript t when no ambiguity is made. By setting w i =1 Kpi , we can make the gradient estimator G i an unbiased estimator of the true gradient, i.e.,

EQUATION

Without loss of generality, we use stochastic gradient descent (SGD) to update model parameters:

EQUATION

where η t is the learning rate at iteration t. As the goal is to find optimal θ * , we define the expected progress towards the optimum at each iteration as follows.

Definition 2. At iteration t, the expected parameter rectification R t is defined as the expected reduction of the squared distance between the parameter θ and the optimum θ * after iteration t,

EQUATION

Generally, tens of thousands iterations are included in the training, so the empirical average parameter rectification will converge to the average of R t asymptotically. By maximizing R t , we guarantee the most progressive step towards parameters optimum at each iteration in the expectation sense.

Inspired by the greedy algorithm (Edmonds, 1971) , we aim to maximize R t at each iteration.

It can be shown that maximizing R t is equivalent to minimizing tr(Var [G It ]), as shown in Theorem 1. Under this umbrella, we show that the optimal sampling probability is proportional to the per-sample gradient norm (a special case of Theorem 2). Therefore, the optimal sampling probability of each datum happens to be proportional to its informativeness. This property justifies our definition of informativeness as the resulting gradient norm of each training example.

However, as the neural network has multiple layers with a large number of parameters, it is computationally prohibitive to calculate the full gradient norm. Instead, we prove that the matching distance in the feature space is a good approximation to the informativeness 1 in Section 4.2. Concretely, for each class consisting of k patches {X i : i = 1, . . . , k}, we first select a patch X i0 randomly, which serves as the anchor patch, and then sample a matching patch X i with probability

EQUATION

where x i is the extracted descriptor of X i , and d(•, •) measures the discrepancy of the extracted descriptors. See specific choices of d in Section 3.4.

Maximum Loss Minimization. Minimizing the average loss may be sub-optimal because the training tends to be overwhelmed by well-classified examples that may contribute noisy gradients (Lin et al., 2017) . On the contrary, well-classified examples can be adaptively filtered out by minimizing the maximum loss (Shalev-Shwartz & Wexler, 2016) , which can further improve the generalization ability of models. However, directly minimizing the maximum loss may lead to insufficient usage of data and sensitivity to outliers, so we approximate the gradient of maximum loss by

∇ θt 1 K K i=1 L α i

, in which α is sufficiently large. As G It is used to update parameters, consider its expectation

EQUATION

To guarantee G It to be an unbiased estimator of ∇ θt

EQUATION

as in this case,

EQUATION

)

Following previous reasoning, we need minimize tr(Var [G It ]) given the constraints in Equation 9, in order to step most progressively at each iteration. In Theorem 2, we show that the optimal sampling probability and re-weighting scalar should be given by

p i ∝ L α-1 i ||∇ θt L i || 2 and w i ∝ ||∇ θt L i || -1 2 .

(11) As previously claimed, we approximate the gradient norm via the matching distance in the feature space. Besides, in our case, the loss function is hinge triplet loss (Equation 14), which is positively (or even linearly) correlated with the matching distance squared. Therefore, we use matching distance squared as an approximation of the loss. Thus, the sampling probability and re-weighting scalar are given by

EQUATION

Moreover, for better approximation, it is preferable to adjust α adaptively, i.e., increase α with training. Intuitively, when easy matching pairs have already been correctly classified, we focus more on hard ones. A good indicator of the training progress is the average loss. As a result, instead of predefining a sufficiently large α, we set 2α -1 = λ/L avg , where λ is a tunable hyperparameter and L avg is the moving average of history loss. Formally, we formulate our sampling probability and re-weighting scalar as

p i ∝ d(x i , x i0 ) λ Lavg and w i ∝ d(x i , x i0 ) -1 , f or i = i 0 .

(13) The exponent increases adaptively with training, so our sampling method is named as AdaSample.

3.3. TRIPLET GENERATION BY HARDEST-IN-BATCH:

AdaSample focuses on the batch construction stage; nevertheless, for a complete triplet mining framework, we need to mine negatives from the mini-batch as well. Here, we adopt the hardestin-batch strategy in Mishchuk et al. (2017) . Formally, given a mini-batch of n matching pairs

{( Xi , X+ i ) : i = 1, . . . , n}, let ( xi , x+ i ) be the descriptors extracted from ( Xi , X+ i ) 2 .

For each matching pair ( Xi , X+ i ), we select the non-matching patch which lies closest to one of the matching patches in the feature space. Then, the Hinge Triplet (HT) loss is defined as follows:

EQUATION

EQUATION

)

where t denotes the margin. Incorporating the re-weighting scalar, we update the model parameters via the gradient estimator n i=1 w i ∇ θ L i .

3.4. DISTANCE METRIC:

Euclidean distance is widely used in previous works (Tian et al., 2017; Mishchuk et al., 2017; Tian et al., 2019a) . However, as descriptors lie on the unit hypersphere in 128-dimensional space (Appendix C), it is more natural to adopt the geodesic distance of the embedded manifold. Therefore, we adopt the angular distance (Deng et al., 2018) as follows:

EQUATION

where • denotes inner product. We nominate our loss function as Angular Hinge Triplet (AHT) loss, which is demonstrated to result in consistent performance improvement (see Section 5.3).

Algorithm 1 summarizes the overall triplet generation framework. For each training iteration, we first randomly pick n distinct classes from the dataset and extract descriptors for patches belonging to these classes (Step 1, 2). Then, we randomly choose a patch as anchor from each selected class (Step 4), and adopt AdaSample to select an informative matching patch (Step 5). With the generated mini-batch, we mine hard negatives following Mishchuk et al. (2017) and compute Angular Hinge Triplet (AHT) loss (Step 7). An illustration of our sampling pipeline can be found in Appendix B.

Algorithm 1 Pipeline of AdaSample framework.

Require::

Dataset of N classes with each containing k matching patches; Moving average of history loss L avg ; Hyperparameter λ; 1: Randomly select n distinct classes from the dataset without replacement; 2: Extract descriptors of the patches belonging to the selected classes; 3: for each selected class with k patches {X i : i = 1, . . . , k} do 

4. THEORETICAL ANALYSIS:

In this section, we complete the theoretical analysis of informativeness in Section 4.1, and prove that the matching distance can serve as a good approximation of informativeness in Section 4.2.

4.1. INFORMATIVENESS FORMULATION:

Following notations in Section 3.2, we reformulate R t (Equation 6), and give an equivalent condition for maximizing R t . The same conclusion can be found in Katharopoulos & Fleuret (2018) . Theorem 1. Let R t , θ * and G i be defined as in Equation 6, 1 and 3, respectively. Then, we have

EQUATION

)

Due to unbiasedness (Equation 4), the first two terms in Equation 16 is fixed, so maximizing R t is equivalent to minimizing tr(Var [G It ]). Theorem 2 specifies the optimal probabilities to minimize the aforementioned trace under a more general assumption. Theorem 2. Let G i be defined in Equation 3 and suppose the sampled index I t obeys distribution P t . Then, given the constraints

p i w i = α K L α-1 i , tr(Var [G It ]

) is minimized by the following optimal sampling probabilities:

EQUATION

)

Note that in the special case of α = 1, the constraints degrade into p i w i = 1 K and the optimal sampling probabilities become p i ∝ ||∇ θt L i || 2 . The proof of the above theorems can be found in Appendix A.

4.2. APPROXIMATION OF INFORMATIVENESS:

As mentioned in Section 3.2, the matching distance can serve as a good approximation of informativeness, up to a constant factor. We justify this here. For simplicity, we introduce some notations for a L-layer multi-layer perceptron (MLP). Let θ (l) ∈ R M l ×M l-1 be the weight matrix for layer l and g (l) be a Lipschitz continuous activation function. Then the multi-layer perceptron can be formulated as follows:

EQUATION

)

Note that although our notations describe only MLPs without bias, our analysis holds for any affine transformation followed by a Lipschitz continuous non-linearity. Therefore, our reasoning can naturally extend to convolutional neural networks (CNNs). With

EQUATION

we have

EQUATION

)

Various data preprocessing, weight initialization (Glorot & Bengio, 2010; He et al., 2015) , and activation normalization (Ioffe & Szegedy, 2015; Lei Ba et al., 2016; Ulyanov et al., 2016) techniques uniformise the activations of each layer across samples. Therefore, the variation of gradient norms is mostly captured by the gradient of the loss function w.r.t. the output of neural networks,

EQUATION

)

where M is a constant, and M ∇ x (L) L 2 serves as a precise approximation of the full gradient norm. For simplicity, we consider hinge triplet loss (Equation 14) here. Then, the gradient norm w.r.t. the descriptor of the matching patch is just twice the matching distance3 ,

EQUATION

)

As a result, we get the conclusion that the matching distance is a good approximation to informativeness, up to a constant factor. Also, we empirically verify this in Section 5.3.

5. EXPERIMENTS:

We first compare with the state-of-the-art methods on two standard descriptor datasets: UBC Phototour (Brown et al., 2011) and HPatches (Balntas et al., 2017) . Then, we make comprehensive ablation studies. See implementation details in Appendix C and more results on the ETH SfM (Schonberger et al., 2017) dataset in Appendix D.

5.1. UBC PHOTOTOUR:

UBC Phototour (Brown et al., 2011) , also known as Brown dataset, consists of three subsets: Liberty, Notre Dame and Yosemite, with about 400K normalized 64 × 64 patches in each subset. Keypoints were detected by DoG detector (Lowe, 2004) and verified by 3D model. Testing set consists of 100K matching and non-matching pairs for each sequence. For evaluation, models are trained on one subset and tested on the other two. The metric is the false positive rate (FPR) at 95% true positive recall. The evaluation results are reported in Table 1 . (Simo-Serra et al., 2015) 10.9 4.40 5.69 6.99 GeoDesc (Luo et al., 2018) 5.47 1.94 4.72 4.05 L2-Net (Tian et al., 2017) 3.64 5.29 1.15 1.62 4.43 3.30 3.24 CS-L2-Net (Tian et al., 2017) 2.55 4.24 0.87 1.39 3.81 2.84 2.61 HardNet (Mishchuk et al., 2017) 1.47 2.67 0.62 0.88 2.14 1.65 1.57 HardNet-GOR (Zhang et al., 2017) 1 Our method outperforms other approaches by a significant margin. We randomly flip and rotate by 90 degree for data augmentation, noted by +, for all methods. Besides, for our method, we also generate positive patches by random rotation such that each class has 15 patches, noted by *. This is because there are too few patches (two or three) corresponding to one class in UBC Phototour dataset (Brown et al., 2011) , which limits the capacity of our method. To analyze its effect, we also conduct it for HardNet (Mishchuk et al., 2017) , and observe inferior performance, indicating that the performance improvement mainly comes from our adaptive sampling solution.

5.2. HPATCHES:

HPatches (Balntas et al., 2017) consists of 116 sequences of 6 images. The dataset is split into two parts: viewpoint -59 sequences with significant viewpoint change and illumination -57 sequences with significant illumination change. According to the level of geometric noises, the patches can be further divided into three groups: easy, hard and tough. There are three evaluation tasks: patch verification, image matching and patch retrieval. Following standard evaluation protocols of the dataset, we show results in Figure 1 . It shows that our method outperforms other methods on all three tasks when trained on either Liberty dataset (Brown et al., 2011) or HPatches training split.

Under review as a conference paper at ICLR 2020

5.3. ABLATION STUDY:

Informativeness Approximation. We empirically verify the conclusion in Section 4.2 that the probability induced by matching distance is a good approximation to the one induced by informativeness (Figure 2 Impact of λ. We experiment with varying λ in AdaSample, which controls the overall "hardness" of selected matching pairs. The larger λ is, the more likely hard matching pairs will be selected. When λ = 0, our method degrades into random sampling and overall framework becomes HardNet (Mishchuk et al., 2017) , and as λ → +∞, the framework becomes Hardpos. Therefore, both HardNet and Hardpos are special cases of our proposed AdaSample. Table 2 shows the results on HPatches dataset (Balntas et al., 2017) , where λ = 10 leads to the best results in most cases. It demonstrates the advantages of our balanced sampling strategy against the hardest solution.

Table 2 : Abaltion study results on HPatches (Balntas et al., 2017) . 

6. CONCLUSION:

This paper proposes AdaSample for descriptor learning, which adaptively samples hard positives to construct informative mini-batches during training. We demonstrate the efficacy of our method from both theoretical and empirical perspectives. Theoretically, we give a rigorous definition of informativeness of potential training examples. Then, we reformulate the problem and derive a tractable sampling probability expression (Equation 13) based on informativeness. Empirically, we enjoy consistent performance gain on top of HardNet (Mishchuk et al., 2017) baseline when evaluated on various task, including patch classification, patch verification, image matching, and patch retrieval.

A PROOF OF THEOREMS:

Proof of Theorem 1.

Proof. We reformulate R t as follows, 5)

R t = -E It∼Pt (θ t+1 -θ * ) T (θ t+1 -θ * ) -(θ t -θ * ) T (θ t -θ * ) = -E It∼Pt θ T t+1 θ t+1 -2θ T t+1 θ * -θ T t θ t + 2θ T t θ * = -E It∼Pt (θ t -η t G It ) T (θ t -η t G It ) + 2η t G T It θ * -θ T t θ t (Equation

EQUATION

)

Proof of Theorem 2.

Proof. As G It is an unbiased estimator of the true gradient (Equation 4), E It∼Pt [G It ] is fixed in our case, denoted by µ for short. By the linearity of trace and tr(µµ

EQUATION

)

Mathematically, given the constraints K i=1 p i = 1, the aforementioned harmonic mean of {p 1 , . . . , p K } reaches its minimum when the probabilities satisfy

EQUATION

)

Divided by a normalization factor, we get the expression in Equation 17.

B SAMPLING PIPELINE:

Figure 3 illustrates our sampling pipeline and model architecture. The triplet generation consists of two stages: i) matching pairs are sampled from the dataset to construct mini-batches, and ii) hard negatives are mined from the mini-batch to form triplets. Our AdaSample focuses on sampling informative matching pairs for mini-batch construction, and we follow the hardest-in-batch strategy in Mishchuk et al. (2017) for the second stage. We adopt the architecture of L2-Net (Tian et al., 2017) to embed patches into 128-dimensional feature space.

C IMPLEMENTATION DETAILS:

We adopt the architecture of L2-Net (Tian et al., 2017) to embed local descriptors into the unit hypersphere in 128-dimensional space. Following prior works (Tian et al., 2017; Mishchuk et al., 2017) , all patches are resized to 32 × 32 and normalized to zero per-patch mean and unit per-patch variance. We train our model from scratch in PyTorch library (Paszke et al., 2017) using SGD optimizer with initial learning rate η = 10, momentum 0.5 and weight decay 0.0001. Batch size is 1024, margin t = 1 and λ = 10 unless otherwise specified. We generate 1, 000, 000 matching pairs Note that the training set of GeoDesc is not released, and the comparisons with it is unfair. Besides, we argue that even more powerful descriptor learning framework can be established by combining our method and SOSNet, as our method focuses on data sampling and batch construction, while SOSNet on regularization. However, as the training code of SOSNet is not publicly available, we leave the efficacy comparison and system combination in future work.

D RESULTS ON ETH DATASET:

We evaluate the proposed descriptor on ETH SfM benchmark (Schonberger et al., 2017) to investigate its ability to reconstruct 3D models. We compare with both handcrafted algorithms (SIFT (Lowe, 2004) and DSP-SIFT (Dong & Soatto, 2015) ) and deep methods (L2-Net (Tian et al., 2017) and GeoDesc (Luo et al., 2018) ) as strong baselines. Following the standard protocols in Schonberger et al. ( 2017), we show results in Table 3 , where Reproj. Error indicates the reconstruction accuracy, Track Length also indicates the quality of the reconstructed points, and others stand for reconstruction density.

It is difficult to say which one (density or accuracy) is more important in 3D scene reconstruction.

Here, the results show that our method results in the best accuracy in reconstruction, and the reconstructed points have better track lengths. This is especially clear in large dataset (the last two rows).

Although the reconstruction density of our approach is lower than other methods, we argue that our method is as robust as them. For example, compared with SIFT (Lowe, 2004), which is the most widely used descriptor in SfM problem, the registered of our method is consistently equal or higher.

Note that the density metrics should be considered with the accuracy. This is because there is no guarantee that the reconstructed points (observations, and registered images) are correct. Here, we find that other deep methods (L2-Net (Tian et al., 2017) and GeoDesc (Luo et al., 2018 )) show higher , 2004) and DSP-SIFT (Dong & Soatto, 2015) ), other deep descriptors (L2-Net (Tian et al., 2017) and GeoDesc (Luo et al., 2018) ) suffer in reconstruction accuracy (Reproj.

Error), although they get higher density. Here we show that deep descriptors (our method) can achieve better accuracy of reconstruction against traditional methods. density than traditional methods (SIFT (Lowe, 2004) and DSP-SIFT (Dong & Soatto, 2015) ), but suffer in accuracy. It is indeed arguable that which type of methods are better. Here, compared with traditional methods, our method can achieve higher accuracy. This has important implications to deep learning based descriptors for high-precision 3D reconstruction.

E COMPARISON OF CONVERGENCE SPEED:

Figure 4 shows the training trend of our method and HardNet (Mishchuk et al., 2017) . Models are all trained and tested on HPatches (Balntas et al., 2017) using split 'a'. By incorporating AdaSample method, our model enjoys significantly better convergence speed. (Mishchuk et al., 2017) on HPatches (Balntas et al., 2017) dataset.

:

The approximation is up to a constant factor, which is insignificant as it will be offset by the learning rate. The same reasoning applies to the approximation of gradients in Maximum Loss Minimization paragraph.

For clarity, ( X , X+ ) denotes the selected matching pairs, with different pairs belonging to different classes. X denotes a generic patch in a specific class, where denotes the placeholder for the index.

This relation holds only when the hinge triplet loss is positive. Empirically, due to the relatively large margin, the hinge loss never becomes zero.

Figures and Tables:

patch X i from the remaining patches with probabilities specified by Equation 13; 6: end for 7: With sampled positive pairs and their descriptors {( xi , x+ i )} n i=1 , compute Angular Triplet Hinge loss by Equation 14; 8: Backpropagate and update model parameters via n i=1 w i ∇ θ L i ;

Figure1: Evaluation results on HPatches dataset(Balntas et al., 2017). "-LIB" indicates descriptors trained on Liberty subset of UBC Phototour dataset(Brown et al., 2011) and "-HP" indicates descriptors trained on training set of HPatches (split 'a'). Marker color indicates the level of geometrical noises and marker type indicates the experimental setup. INTER and INTRA indicate the source of negative examples for the verification task. VIEWP and ILLUM indicate the sequence type for the matching task.

(a)). Besides, the results show that the Pearson correlation is consistently greater than 0.8 with training (Figure 2(b)), which indicates these probabilities have strong correlation with each other statistically. It echoes our theoretical conclusion.

Figure 2: (a) Probabilities induced by informativeness and matching distance. (b) Pearson correlation between probabilities and training epoches.

Figure 3: Training pipeline of AdaSample framework.

Figure 4: Traning trend of AdaSample and HardNet(Mishchuk et al., 2017) on HPatches(Balntas et al., 2017) dataset.

Let random variable I t denote the sampled index at iteration t, then I t ∼ P t , namely, P(I t = i) = p t i . We record the re-weighted gradient induced by training sample (x i , y i ) as

Table content: <table><tr><td colspan="2">denotes the number of training examples. Then we proceed our idea with the following</td></tr><tr><td>definition on the informativeness.</td><td/></tr><tr><td colspan="2">Definition 1. The informativeness of a training example (x i , y i ) is quantified by how much it con-</td></tr><tr><td>tributes in the training iteration t, namely,</td><td/></tr><tr><td>info(x i , y i ) := ||∇ θt L(f (x i ; θ), y i )|| 2 .</td><td>(2)</td></tr><tr><td colspan="2">At iteration t, let P t = {p t 1 , . . . , p t K } be the sampling probabilities of each datum in the training set. More generally, we also re-weight each sample by w t 1 , • • • , w t K .</td></tr></table>

Patch classfication results on UBC Phototour dataset(Brown et al., 2011). The false positive rate at 95% recall is reported. + indicates data augmentation and * indicates positive generation.

Table content: <table><tr><td>Train Test</td><td colspan="4">Notredame Yosemite Liberty Yosemite Liberty Notredame Mean Liberty Notredame Yosemite</td></tr><tr><td>SIFT (Lowe, 2004)</td><td>29.84</td><td>22.53</td><td>27.29</td><td>26.55</td></tr><tr><td>DeepDesc</td><td/><td/><td/><td/></tr></table>

Distance metric and training speed. As shown in Table2, our angular hinge triplet (AHT) loss outperforms the commonly-used hinge triplet (HT) loss in most cases. Besides, our method can speedup the network convergence, as non-informative matching pairs are adaptively filtered out. See visualized learning trends in Appendix E.

Table content: <table><tr><td>Task</td><td colspan="2">Verification</td><td colspan="2">Matching</td><td colspan="2">Retrieval</td></tr><tr><td>Loss</td><td>AHT</td><td>HT</td><td>AHT</td><td>HT</td><td>AHT</td><td>HT</td></tr><tr><td>λ = 1</td><td colspan="6">93.84 93.17 64.09 62.64 81.26 79.97</td></tr><tr><td>λ = 2</td><td colspan="6">94.72 94.56 66.04 65.92 83.58 83.34</td></tr><tr><td>λ = 5</td><td colspan="6">94.78 94.76 65.89 65.68 83.80 83.54</td></tr><tr><td>λ = 10</td><td colspan="6">94.78 94.60 65.46 65.37 83.98 83.62</td></tr><tr><td>λ = 20</td><td colspan="6">94.60 94.69 64.56 64.84 83.56 83.69</td></tr><tr><td colspan="7">λ → +∞ 94.42 94.51 63.81 64.02 83.41 83.29</td></tr></table>

SfM results on ETH dataset (Schonberger et al., 2017). Compared with handcrafted methods (SIFT (Lowe

Table content: <table/>

Peer review (iclr2020):
The paper proposes to make two modifications in hard negative mining procedure for descriptor learning: - instead of selecting hardest samples in a minibatch it proposes to sample proportionally to distance between descriptors - gradient wrt model parameters is weighted inverse proportionally to the distance The authors attempt to analyze the method theoretically and evaluate on two descriptor learning benchmarks, UBC phototour 2011 and HPatches 2017. I propose reject mainly for the following reasons: 1) dataset selection and quality of experimental evaluation 2) the writing (presentation of the results) Regarding (1), my main concern is on statistical significance of presented experiments. The authors conduct each experiment once and do not take into account variance coming from neural net training. For example, in table 2 all numbers seem to be very close so it is not possible to conclude anything. Same is true for other experiments, one way to improve would be to do 10-fold cross validation or at least train 5 network with different random seed and provide mean +- std of the results. Then, I think UBC results are not indicative of performance since the dataset is small and very old at this point, so I disagree with the claim that improvement of ~0.1% is of significant margin. Improvement on HPatches seems to be slightly more significant, but it is not clear wether the authors used comparable networks in terms of number of parameters in the network and descriptor size. Regarding (2), the way the paper is written is very confusing and should be improved. The attempts to have a theoretical derivation of the proposed method are welcome, but should not precede the actual explanation of the method. I suggest to explain clearly the modifications to sampling strategy, and only then relate them to informativeness intuition. Further, the improvement over HardNet is not clear. The two proposed modifications are not tested separately. To have a proper ablation study, the authors could sample negatives proportionally to descriptor distance and remove gradient weighting, and vice versa, to sample hardest-in-batch and only add gradient weighting. I also disagree that hard negative mining is *widely used in object detection and other vision tasks* (quoting the authors). It used to be common in metric learning for face recognition, as the authors cite FaceNet 2015, but has been long abandoned in favor of SphereFace-like approaches. Same is true for object detection, where Fast R-CNN and Mask R-CNN without HNM are widely used.