Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem
Authors: Albert Xu
Jhih-Yi Hsieh
Bhaskar Vundurthy
Nithya Kemp
Eliana Cohen
Lu Li
Howie Choset
Venue: ICLR 2024 poster (2024)
Keywords: Metric Learning
Triplet Loss
Hard Negative Mining
Primary area: metric learning, kernel learning, and sparse coding
TL;DR: A theoretical explanation for why the Triplet Loss with Hard Negative Mining sometimes leads to network collapse, and identification of hyperparameters that contribute to collapse.

Abstract: In deep metric learning, the triplet loss has emerged as a popular method to learn many computer vision and natural language processing tasks such as facial recognition, object detection, and visual-semantic embeddings. One issue that plagues the triplet loss is network collapse, an undesirable phenomenon where the network projects the embeddings of all data onto a single point. Researchers predominately solve this problem by using triplet mining strategies. While hard negative mining is the most effective of these strategies, existing formulations lack strong theoretical justification for their empirical success. In this paper, we utilize the mathematical theory of isometric approximation to show an equivalence between the triplet loss sampled by hard negative mining and an optimization problem that minimizes a Hausdorff-like distance between the neural network and its ideal counterpart function. This provides the theoretical justifications for hard negative mining's empirical efficacy. Experiments performed on the Market-1501 and Stanford Online Products datasets with various network architectures corroborate our theoretical findings, indicating that network collapse tends to happen when batch size is too large or embedding dimension is too small. In addition, our novel application of the isometric approximation theorem provides the groundwork for future forms of hard negative mining that avoid network collapse.

Published as a conference paper at ICLR 2024
MATHEMATICAL JUSTIFICATION OF HARD NEGATIVE MINING VIA ISOMETRIC APPROXIMATION THEOREM
Albert Xu, Jhih-Yi Hsich, Bhaskar Vundurthy, Nithya Kemp, Eliana Cohen, Lu Li, & Howie Choset
Robotics Institute Camegie Mellon University Piusburgh, PA 15232, USA (albertx, jhihyih, pvundurt (eaddrew.wawwdw.ccccmmm jeundurtteanddeev..om
ABSTRACT
In deep metric learning, the triplet loss has emerged as a popular method to learn many computer vision and natural language processing tasks such as facial recog- nition, object detection, and visual-semantic embeddings. One issue that plagues the triplet loss is network collapse, an undesirable phenomenon where the network projects the embeddings of all data onto a single point. Researchers predomi- nately solve this problem by using triplet mining strategies. While hard negative mining is the most effective these strategies, existing formulations lack strong theoretical justification for their empirical success. In this paper, we utilize the mathematical theory of isometric approximation to show an equivalence between the triplet loss sampled by hard negative mining and an optimization problem that minimizes Hausdorff-like distance between the neural network and its ideal counterpart function. This provides the theoretical justifications for hard nega- tive mining's 's empirical efficacy. Experiments performed on the Market- 1501 and Stanford Online Products datasets with various network architectures corroborate our theoretical findings, indicating that network collapse tends to happen when the batch size too large or embedding dimension is too small. addition, our novel application of the isometric approximation theorem provides the groundwork for future forms of hard negative mining that avoid network collapse.
INTRODUCTION
Research in deep metric learning investigates techniques for training deep neural networks to learn similarities and dissimilarities between data samples. This is typically achieved by learning dis- tance metric via feature embeddings in IR.. Deep metric learning is commonly applied to face recognition SScrroff al. (2015), ; Liu et al. (2017); Hermans al. (2017) and other computer vision tasks Tack et al. (2020): Chen et al. (2020a) where there is an abundance of label values.
Contrastive loss Hadsell al. (006) and triplet loss Schroff et al. (205)) are prominent amples of deep metric learning, each with variants to address specific applications. For instance, SimCLR Chen al. (2020a b) recent contrastive loss variant designed to perform unsupervised deep metric learning with state-of-the-arr performance on ImageNet Russakovsky et al. (2015). Ladder Loss Zhou et al. (201)) generalized variant of the triplet loss, handles coherent visual- semantic embedding and has important applications in multiple visual and language understanding tasks KaskatKap al. (2014); Ma et (2015): Vinyals et (2014). Cross-level concept distillation Zheng et al. (2022) achieves state of the art performance on hierarchical image classification and dy- namic metric learning. Given the success of metric learning
wide range of applications, we see value in investigating its underlying theories. In particular, we focus on the triplet loss and present theoretical framework which explains observed but previously unexplained behaviors of the triplet loss.
triplet selection strategy is fundamental to any triplet loss-based deep metric learning Wu et al. (2017). This paper deals with hard negative mining. triplet selection strategy that outperforms other mining strategies in a number of applications, for instance, person re-identification Hermans ett al. (207)). In some scenarios, hard negative mining is known suffer from network collapse,

---

Published as a conference paper at ICLR 2024
phenomenon where the network projects all data points onto single point. Schroff et al. (2015) observe this effect their experiments with a person re-identification dataset. On the other hand, Hermans et al. (2017) show that hard negative mining does not suffer from collapsed solutions for similar dataset. These seemingly contradictory results showcase the need for a theoretical framework explain the nature of hard negative mining and the root cause for any collapsed solutions.
There has been some prior literature investigating the phenomenon of network collapse. Xuan et al. (2020) show that hard negative mining leads collapsed solutions by analyzing the gradients of simplified neural network model. Levi et al. 202T) prove that, under a label randomization assump- tion. the globally optimal solution to the triplet loss necessarily exhibits network collapse. However, neither analysis offers sufficient explanation for why hard negative mining can work in practice Hermans et al. (2077); Faghri al. (2017) and how one may reproduce such desirable behavior.
In this work, we explain why network collapse happens by using the theory of isometric approxima- tion Vaisala (2002a) to draw an equivalence between the triplet loss with hard negative mining and Hausdorff-like distance metric (..1 On the Hausdorff-like metric, we observe that collapsed solutions are more likely when the batch size is large or when the embedding dimension small. Our experiments with the person re-identification dataset (Market- maakket-150) 1501 Zheng et al. (2015) recon- cile the findings of Schroff et al. (2015), where a batch size in the order of thousands led to network collapse, and Hermans al. (2017), where batch size of N 72 showed no network collapse. We further support our predictions via experiments spanning three additional datasets (SOP Oh Song et al. (2016), CARS Krause et al. (2013), and CUB200 Wah al. (201T) and three different net- work architectures (ResNet-18, 18, ResNet-50 He et al. (2016). GoogLeNet Szegedy et al. 2015). and 2-layer convnet).
The paper is organized as follows. We begin with the definition of triplet loss with hard negative mining and then present the isometric approximation theorems in Section 2 In Section we define the Hausdorff-like distance and outline proof of its equivalence to the triplet loss with hard negative mining. This leads a measure for network collapse followed by an illustration on how the network collapse is related to the batch size and embedding dimension. Section 4 demonstrates the validity of our theory with experiments on four datasets spanning three network architectures. Section concludes the paper with possible future applications for our theory.
2 BACKGROUND AND DEFINITIONS
Let X' be the data manifold and let y be the classes with | = c being the number of classes. Let h: X' + y be the true hypothesis function, or true labels of the data. Then the dataset consists of pairs {(TK, ) with Th E X, yv E 3 and h(Tx). ). We define the learned neural network R" which maps similar points in the data manifold X to similar points in
J==
as function fo R".
As our paper focuses on metric learning, we define the similarity between embeddings to be the Euclidean distance
= [1fo(z1) (x2)))
(1)
where 21, E X.
2.1 TRIPLET LOSS AND HARD NEGATIVE MINING
In this section, we discuss the triplet loss that considers triplets of data composed of the anchor
(xr E X'), positive (x+),, and negative (x-) samples, described in (2)) and (2)). The similarity
relation (2) requires that the anchor and positive samples must be of the same class, while the dissimilarity relation (2p) requires the anchor and negative must be of different classes.
x= E (a' E x()((x) = h(2')}
(2a)
x E fx' E x()(x)) * h(2))}
(2b)
Restating the objective of supervised metrie learning, the embedding of the anchor sample must be closer to the positive than the negative for every triplet. An example of satisfactory triplet is shown
2

---

Published as a conference paper at ICLR 2024
Priple-Sepprrtte boundary for Class A
Positive
Class
Negative
Anchor
d
Class
Figure I: An example anchor, positive, and negative triplet. The blue dotted contour is the Triplet- Separated boundary for Class A. is computed by considering inequality (5) for all points in Class A. Because Class B is outside the Triplet-Separated boundary for Class A, the triplet loss for this example is zero.
in Figure
I Formally, we express this relation via (3 where a is the margin term.
(2, x + a S x xx , x== e X
(3)
This leads the definition of the triplet loss in (4)
Ciiple [do(x, de(x, x² a)
(4)
The function [-]+ max satisfy the desired relation.
(-,0)) 0) zeroes negative values order to ignore all the triplets that already
Definition 2.1. e-Triplet-Separated. We refer to non-empty subsets X X)...,, X C R" as
Seppraeet-Separated if for every X* and X with + we have
1 vll s 2|l Vx, X
This property can be extended to a function fe X + R= by checking whether the embedding subsets X3, are
X (fo(z))< X,h(x) = =i}
It is worth noting that (fo) 0 if and only if fo is a- a-Triplet-Separated An example of two Triplet-Separated sets is shown in Figure
As mentioned in Section 1 the triplet loss relies heavily its triplet mining strategy achieve its performance for two popularly accepted reasons: First, enumerating all O(N3) triplets of data every iteration would be too computationally intensive be tractable. Second, improper sampling of triplets risks network collapse Xuan er al. (2020). Our work substantiates the use of hard nega- tive mining, a successful triplet mining strategy, by characterizing conditions that lead network collapse.
2.2 ISOMETRIC APPROXIMATION
We will present a novel application of the isometric approximation theorem Vaisala (202a)) Eu- clidean subsets in order mathematically justify hard negative mining. The isometric approx- imation theorem primarily defines the behavior near-isometries, or functions that are close to isometries, given by Definition 2.2

---

Published as a conference paper at ICLR 2024
Definition 2.2. s-neartsometry. Let X and Y be real normed spaces. A function f : - Y where A C is called an E-mearisometry (E > 0) if
[1)(()) f - yll Se, VEYEE
In other words, an e-nearisometry is a function that preserves the distance metric within e. The isometric approximation theorem seeks to determine how close f as given by Note (ą(E) is a function of that is fixed for given A and is thus independent of and all e-nearisometries f.
isometry, say U - Y,
f. Consequently, inequality (8) holds for all
fl (2))l - (A V
(8)
Now consider the case where and are n-dimensional Euclidean metric spaces, making A R". Then the following theorems and definitions Vaisala (2002a b); Alestalo et al. (2001) prove that (=) is linear in given a thickness condition on the set A.
Definition 2.3. Thickness. For each unit vector S define the projection Te. R" R by the dot product (e(x)= x c. The thickness of a bounded set is the number
((A)
inf cES
(
(9a)
where diam(X) = sup
||r - r2ll
(9b)
Theorem 2.4 (From Theorem 3.3 Alestalo al. (00T). Suppose that 0 < 9 S 1 and C R" is
compact set with ((A) 2 q diam A). Let f A Rd be e-nearisometry. Then there is
isometry IR" + R such that
-U)) S C A
(10)
with on depending only on dimension.
As this property depends entirely on the set A, we call Theorem 2.44rem22.4thee c-Isometric Approximation Property (c-IAP) on set A with c (iam(A)/0(A))
3
THEORETICAL CONTRIBUTIONS
3.1 OVERVIEW AND PROBLEM SETUP
From the background and definitions, the goal of the triplet loss is to learn function fo such that the induced distance metric dg satisfies the property in (3). In this paper, we aim to justify the use of hard negative mining with the triplet loss for this task and offer theoretical explanations for why it sometimes leads to collapsed solutions. Furthermore, we wish to be able to predict when network collapse happens.
In this section, we first prove equivalence between Hausdorff-like distance (13) and the triplet loss with hard negative mining. Then, with the diameter the network's embedding set as an indicator for network collapse (diam(X,s) 0), use the previous equivalence to show that network collapse happens when the batch size large or when the embedding dimension is small.
3.2 EQUIVALENCE BETWEEN dHAUS AND TRIPLET LOsS
We begin with the definition of the Hausdorff-like distance dhans- draw an equivalence to the isomet- ric error diso, which is equivalent to the triplet loss within a constant factor. Then, we illustrate all three distance functions and their equivalence with toy example.
3.2.1 HAUSDOREF-LIKE DISTANCE dRAUS
Reiterating the training objective from the problem setup, aim learn function fo that is Triplet-Separatee (Definition 2.T). We restate this problem as a distance minimization problem, and prove that it is equivalent to hard negative mining with the triplet loss.
4

---

Published as a conference paper at ICLR 2024
First construct set of all functions f X' - R" that are --Triplet-Separater and denote it with Fs. We next construct the Hausdorff- like distance metric (denoted by dnaus) between these functions that compares the embedding subsets via the Hausdorff distance metric dn.
X = ( E -x))
(11)
dhaus (fi. f2) max dH ;x,,,,
(12)
One way solve metric learning to find the closest fo any function in Fis as indicated by
draus (aams(fe (fe, Fis)
inf fin EFF
draus (Se: Jasss)
(13)
In this paper, claim that the triplet loss with hard negative mining equivalent minimizing dhaus (So, Frs) within a constant factor (see Corollary 3.4
3.2.2 ISOMETRIC APPROXIMATION APPLIED TO dHAUS
In this section, present Theorem 3.2 to show that minimizing the Hausdorff- like distance is equiv- alent to minimizing difference distance metrics, referred to as the isometric error (Definition 3.1.
Definition 3.1. isometric error. For two functions f.9 X - R", define the isometric error diso to be the maximum difference between their distance metrics.
sup x1
[1((z) - -((())))((22)11)
(14)
Similar to 13 we extend the definition of isometric error to Fis) as follows:
doa Fis)
inf
dis(fos fioo)
(15)
fre fLEETss
Theorem 3.2. drana (fo and diso (fo. FTs) upper bound each other within a linear factor for all fo with some minimum thickness 6_.
We present the proof for Theorem 3.2 in Appendix A Theorem 3.2 shows that dhaus and diso exchangeable as minimization objectives because they upper bound each other within linear factors. And as d, is difference of two distance functions, derive the triplet loss.
3.2.3 RECOVERING THE TRIPLET LOSS
In this section, we present Theorem 3.3 show that the isometric error (Detinition 3.1 is equivalent to the triplet loss sampled by hard negative mining.
Theorem 3.3. The triplet loss sampled by hard negative mining and the isometric error das upper bound each other within a linear factor.
We present the proof for Theorem 3.3 in Appendix B proving that diso is exchangable with the triplet loss sampled by hard negative mining. Thus from Theorems 3.2 and 3.3 we have Corollary (34
Corollary 3.4. The optimal solution to the triplet loss sampled by hard negative mining is equivalent the optimal solution dnaw fo, FF within constant factor.
where we show that damus- d and triplet loss sampled by hard negative mining upper and lower bound each other by constant factors. Conse- quently, the optimal solution to triplet loss sampled by hard negative mining, and to drans (fo. F73)). equivalent within a constant factor.
Proof. The proof follows from Theorems 3.2 and 3.3
5

---

Published as a conference paper at ICLR 2024
0.3
0.2-
0.2
0.1
0.0
-..1
-0.1
-0.2
-02
0,3
-0.4
-0.5
0.4
0.3
0.2
0.1
0.0
0.1
0.2
0.3
0.4 -0.3
0.2
0.1
0.0
0.1
0.2
0.3
0.4
Figure 2: (Left) The setup for our toy example is a dataset five arbitrary points. projected through fo onto the embedding space R², divided into two classes, red and blue. (Right) Illustration of dhau([o. (so Frs). The stars represent the emhedding points of the function fiass that minimizes dhaus (f,, and the arrows connect the points projected through fo and fins respectively. The is the maximum distance between two projections, whose arrows are out- lined in black. The red and blue star sets are Triplet-Separated because they lie outside the other's s Tripaet-Separated boundary, indicated by the dashed colored border.
value of
0.3
0.3
Positive
Calance 5. onfferncee
0.1
meste
0.0
-0.1
in
-0.1
-0.2
-0.4
-0.4
Anchor
Negative
-0.5
-0.4 -0.3
-0.2
-0.1
0.0
0.1
0.2
0.3
Figure 3: (Left) Illustration of (fo. Using the toy example shown in Figure 2 we com- pute fg (marked stars) that minimizes difference of the distance between two points under fo (circles) and the distance under fig (stars) as shown by the curly brace the middle. (Right) Illustration of the triplet loss sampled by hard negative mining. Using the toy example shown in Figure 2 we take the triplet (anchor, positive, negative) that maximizes the triplet loss.
Frs). To compute (fo Frs), we take the
3.2.4 ILLUSTRATIVE EXAMPLES FOR TRIPLET LOSS EQUIVALENCE
In this section, we illustrate the key ideas the previous section's 's theorems by using a toy example with margin
0, N 5 points, and embedding dimension d 2. As we will illustrate the cquivalence between the triplet loss with the Hausdorff-like distance and isometric error, we can visualize the embedding points without any underlying data neural network. See Figure 2 for the toy example setup.
Also shown in Figure 2is visualization of dhaus (fo, Frs). The numerical value of dram (fe, Frr)) is determined by the maximum length of the arrows, which is marked in the figure with black outlines. Here, compute the ideal fa see (13) by optimizing the embedding points.

---

Published as a conference paper at ICLR 2024
2 Inteel Contiguration
Step 15 Jis E rrg
Step 30
2: Step 50 (collapsed) fio E Frs
fso $ Frs
-2
-2
drcad -2
dhoud Fra)
dond fnx Frs)
drwa fyn Fix) [s]
0
0
2
Figure 4: Illustration of how hard negative mining leads to collapsed solutions given N 20 samples and embedding dimension d = 2. We approximate the f that minimizes chaus (fee Frs) by applying 50 gradient descent steps and observe that the embedding points collapse into much smaller subset. Also marked are the values ddaus(fss Frs) as measured by their Hausdorff- like distance from the approximated f"
Figure illustrates diso (Jo, Frs), which measures the difference in distance metric. Note that fi that minimizes dise fo. fis.) is not necessarily the same fhaus Revisiting the second part of the proof for Theorem 3.2 (Also see [A). draus Fr. ) is lower bounded by 0.5d (fa, Frs) and upper bounded by Frr). For this specific toy example, calculate the constant factor error to be = 0.53. This essentially illustrates Theorem 3.2
Lastly, show the triplet loss sampled by hard negative mining the right of Figure The equivalence proved by (..3 is shown by comparing the two figues in Figure 3 as the triplet selected by hard negative mining corresponds with the same three points with the largest discrepan- cies in distance metric. Through Figures and 3 we have a visualization of the statement and proof of Corollary 3.4
3.3 THEORETICAL INSIGHTS ON NETWORK COLLAPSE
We can the embedding set diameter diam fe) ) to indicate for network collapse, the diam- eter becomes near zero when the network is collapsed. Furthermore, if we assume that training always ends with Triplet-Separated network frs (collapsed or not), have the following triangle inequality (6).. The change in diameter cannot exceed twice the maximum displacement of each embedding point measured by the Hausdorff-like distance (13).
ddiam( X frs) diam( (aam(XXp) fimn S 2dhhaus 2e Frs)
(16)
Re-arranging (16) and substituting in the constant-factor equivalence proven by Corollary find an inequality lower-bounding the diameter of the triplet-separated network.
3.4 we
diam(X(rs) 2 diam (Xm fm cCuiplec
(17)
From we hypothesize two factors that influence network collapse are batch size and embedding dimension. As the batch size grows large, the triplet loss necessarily grows while the embedding diameter remains constant. Therefore we expect that large batch size leads to network collapse. the other hand, increasing embedding dimension should increase the initial embedding diameter more than the triplet loss. As result, low embedding dimension should lead to network collapse.
To illustrate our hypothesis that large batch size leads to network collapse, we show another toy example with N 20 points with dimension d 2 in Figure 4 The arrows illustrate the f that minimizes dnaus (.fo Frs) for this example, which is a collapsed function. We hypothesize that when f" is collapsed, the function fo learned by using the triplet loss would also be collapsed.
4 EXPERIMENTS
As mentioned in Section I current literature observes that hard negative mining results in network collapse inconsistently. Our theory proposes the testable hypothesis that network collapse happens when the batch size too large, when the embedding dimension is not large enough. We test
7

---

Published as a conference paper at ICLR 2024
6
Maximum Embedeling Distance
Network not Collapsed
Maximum Embedding Distance
2.0
Network
Collapsed
-2
1.5
3
1.0
P=2
P=4
Network Collapse
P=8
Network Collapse
0.5
P-18
a)
16
64
256
b)
16
64
256
1024
Batch Size (N)
Embedding Dimension (d)
Figure 5: Experiments performed on the Market-1501 dataset with randomly initialized ResNet- 18 architecture and margin a = O. Each trial was repeated times, and training is stopped on step 40,000. The theoretical diameter lower bound curve (17) for each experiment is drawn with dashed blue lines. (Left) Experiment A: Network embedding distances vary based on batch size with embedding dimension d = 128. As predicted by our theory, the embedding distances remain large for small batch sizes, with signs of collapse (shown in red) appearing when the batch size is large. The region marked in green indicates a lower probability of network collapse as corroborated by our experiment. (Right) Experiment B: Network embedding distances vary based on embedding dimension with batch size 32 (P 8, K 4). As predicted by our theory, the network embeddings are more likely to collapse when the embedding dimension is small and less when the embedding dimension is large.
our claims by first conducting an experiment on the Market dataset Zheng et al. (2015) with Resnet-18 He al. (2016) architecture. This closely follows the work of Hermans et al. (2017). where the specific emphasis was proving the efficacy of hard negative mining. To this end, we use Kttyle sampling method where P people are sampled per batch and K images are selected per person for a total batch size of N P x K, on the 550 dataset.
Our first experiment (see Figure 5 (a)), illustrates the effect of batch size on network collapse. Here, we use fixed embedding dimension of d 128, train until step 40,000, and repeat each trial 3 times. The batch size and K are varied on grid P 4, 18) and K E {2, 4, 8, 16, 32) for a total of 20 combinations. Using (17) with constant value c 2, we observe that the lower bound, shown in dashed blue, appears to hold across the tested batch size values. Further, as the batch size increases, we see that the embedding diameter decreases until there is network collapse. This confirms our hypothesis that large batch size leads to network collapse.
We then conduct additional experiment (see Figure 5 (b)) to study the relation between the em- bedding dimension and network collapse. Here, we first fix P = 8 and K for each batch and vary the embedding dimension d from 4 to 1024. The network architecture and number of training steps are the same as the previous experiment (Figure (a)). Once again, using (17) with c = 2, observe that the theoretical diameter lower bound (dashed blue line) appears hold across the tested embedding dimension values. Furthermore, as the embedding dimension decreases, we see that the embedding diameter also decreases a point where the network collapses, thus confirming our second hypothesis.
It is worth noting that the experiments described above utilize margin parameter with value of O. While it is conjectured that the parameter a can be tuned to prevent network collapse, we show with an additional set of experiments that does not play as sigmificant role in network collapse as the batch size or embedding dimension. Specifically, the experiments are conducted on the same Market- 1501 dataset and Resnet-18 architecture but with a = 0.01 and a = 0.05. Larger a were also tested, but discarded due to significant overfit. These results are presented in Appendix
We further solidify our claims by conducting three more experiments on the Market1501 dataset Zheng et al. (2015) with a ResNet-50, 2-layer convolutional network and GoogLeNet (Szegedy et al. (2015) (see Appendix E for results). Branching out to other datasets, we also conducted three additional experiments
Stanford Online Products (SOP) Oh Song al. (2016), Stanford Cars (CARS) Krause et al. (2013), and Caltech-UCSS Birds (CUB200) Wah et al. (2011) using a Resnet- 18 architecture (see Appendix D for results). The same network collapse behavior has been
8

---

Published as a conference paper at ICLR 2024
observed in each of these experiments, demonstrating the adverse effects of large batch size and low embedding dimension irrespective of dataset or network architecture.
In summary, observe that the hard negative mining performs well with lower batch size, as reported by [Hermans et al. (2017), and exhibits network collapse when the batch size is increased to large value, which agrees with the triplet loss collapse reported by [Schroff al. (2015). This resolves the apparent contradiction from prior work and offers a unified explanation for network collapse in the context of hard negative mining.
5 DISCUSSION AND CONCLUSION
In this paper, we apply the isometric approximation theorem to prove that the triplet loss sampled by hard negative mining is equivalent minimizing Hausdorff-like distance. This mathematical foundation helps us present novel insights into hard negative mining by establishing relationship between network collapse and the batch size the embedding dimension. Our work presents math- ematical proofs to support this relation and discusses extensive experiments to corroborate the same.
While we note that network collapse negatively affects the network's performance on downstream tasks, lack of network collapse does not necessarily guarantee good performance. While simply choosing batch size be small and embedding dimension to large would be effective for avoiding network collapse, it is not necessarily good for optimizing network performance. Future work could involve looking
effects of small batch size or large embedding dimension and recommending hyperparameter choices for batch size and embedding dimension.
Furthermore, is worth noting that the isometric approximation theorem is independent of the triplet loss. Consequently, the theorem loss Hadsell et al. (2006) (C = d(I, [a- d(z, ((x,x())) - or +1-d((z,a + 3]+). On the other
be applied to any system utilizing the Euclidean metric,
for instance, the pairwise contrastive loss
the margin loss Wu et al. (2017) (C = (d(z,2" 2 hand, the unified metric learning formulation defined by Zheng et al. (2023) opens new avenues to explore alternative sampling methods and their respective functions place of our Hausdorff-Ii like metric d Through this and future work, we intend to leverage mathematical tools from functional analysis explain fundamental principles in modern machine learning and artificial intelligence research.
ACKNOWLEDGEMENT
Thanks to Dr. Jeff Schneider for invaluable advice, discussion, and feedback. We would also like thank the anonymouse reviewers for their comments and suggestions.
A portion of this research was sponsored by the Army Research Laboratory and accomplished The views and conclusions contained
under Cooperative Agreement Number W91 in this document are those of the authors and should not be interpreted as representing the official policies. either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
REFERENCES
Pekka Alestalo, DA Trotsenko, and Jussi Väisälä. Isometric approximation. Israel Journal of Math- ematics, 125(1):61-82, 2001.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pp. 1597-1607. PMLR, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. Advances in neural information pro- cessing systems, 13:22243-22255 2020b.
Fartash Faghri, David Fleet, Jamie Ryan Kiros, and Sanja Fidler. Vse++: Improving visual- semantic embeddings with hard negatives. arXiv preprint arXiv:1707.000 2017.

---

Published as a conference paper at ICLR 2024
R Hadsell, S Chopra, and Y LeCun. Dimensionality reduction by learning invariant map- ping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06) volume 2. pp. 1735-1742. IEEE, 2006. ISBN 9780769525976.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pailern recognition, pp- 770-778, 2016.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person re- identification. arXiv preprini arXiv: 1oXxiv/773...
2017.
Andrej
Karpathy, Armand Joulin, and Li Fei-Fei. Deep fragment embeddings for bidirectional image sentence mapping. CoRR, abs/1406.5679, 2014. URL http://arxiv.org:
14C6.5679
Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3d object representations for fine-grained categorization. In Proceedings of the IEEE international conference on computer vision work- shops, pp. 554-561, 2013.
Elad Levi, Tete Xiao, Xiaolong Wang, and Trevor Darrell. Rethinking preventing class-collapsing in metric learning with margin-based losses. In Proceedings the ference Computer Vision, pp. 10316-10325, 2021.
the IEEE/CVF International Con-
Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. CoRR, abs/1704.08063, 2017. URL http://
arxiv. wex.vvorgg/bs.... abspg//bbs/111 wttp://g//ab///......3. 08063
Lin Ma, Zhengdong Lu, and Hang Li. Learning to answer questions from image using convo- lutional neural network. CoRR, 15s/1506.00333, 2015. URL http://arxiv.erg//e
1506. 00333
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4004-4012, 2016.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-22) 252, 2015. doi: 10.1007/s1 1263-015-0816-)
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 815 823, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 1-9, 2015.
Jihoon Tack, Sangwoo Mo, Jongheon Jeong, and Jinwoo Shin. CSI: novelty detection via contrastive learning on distributionally shifted instances. CoRR, abs/2007.088166 2020. URL https://
arxiv. abs/gg//bs/200 /bw.ab////00011100
Jussi Vaisala. Isometric approximation property in euclidean spaces. Israel Journal of Mathematics,
128(1):1-27, 2002a.
Jussi Vaisala. A survey of nearisometries. arXiv preprint math/0201098, 2002b.
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. CoRR, abs/1411 1.45555,, 2014. URL http://axxiv.org/ http:/iwwrrggab//////ooooooos abs/1411. 4555
Catherine Wah, Steve Branson, Peter Welinder, Pictro Perona, and Serge Belongie. The caltech-ucsd birds-200-2011 dataset. 2011.
10

---

Published as a conference paper at ICLR 2024
Chao-Yuan Wu, R Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE international conference on computer vision, pp. 2840-2848, 2017.
Hong Xuan, Abby Stylianou, Xiaotong Liu, and Robert Pless. Hard negative examples are hard, but useful. In European Conference on Computer Vision, pp. 126-142. Springer, 2020.
Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian. Scalable person re-identification: A benchmark. In Computer Vision, IEEE International Conference on, 2015.
Wenzhao Zheng, Yuanhui Huang, Borui Zhang, Jie Zhou, and Jiwen Lu. Dynamic metric learning with cross-level concept distillation. In European Conference Computer Vision, pp. 197-213. Springer, 2022.
Wenzhao Zheng, Jiwen Lu,, and Jie Zhou. Deep metric learning with adaptively composite dynamic constraints. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Mo Zhou, Zhenxing Niu, Le Wang, Zhanning Gao, Qilin Zhang, and Gang Hua. Ladder loss for coherent semanicc embedding. CoRR, abs/1911.07528. 2019. URL http:://arxtt
11

---

Published as a conference paper at ICLR 2024
A PROOF OF THEOREM 3.2
We now present Lemma A. that extends the results of Theorem 2.4 to apply to dis and use this result to prove Theorem 3.2
Lemma A.1. ('disoJJBo
& and (((()))))))))))))))))))))))))()) 2 q, then there a function U isometric to f such that: l1g(x)) (x))l S one/q Va X
(18)
Proof. If f is invertible, then gf is a function R R. g gf-1 an e-nearisometry because d Then if ((f())) 9. the conditions for Theorem 2.4 are satisfied, so there exists an isometry U1 R R"
-)(=)) / Vx f(X)
(19)
Then
- (((fa)ll((())) 5 Va E
(20)
Therefore if f is invertible, 18 holds with U Uif.
f is not invertible, then there exists 21 * I2 E X such that f(x1) = f(22). We divide the elements of X' into subsets Xet and X such that f is invertible on X f((()()))))) f(X), and diso is unchanged on Xt. Consequently, (20) holds on 211
Moving attention X", for all x' E X' there exists st E xt such that f(x') f(xt). Then because das is unchanged on X [1f(x²) - g(x')ll & I1f(xt) - g(xt)l I GnE/q. Therefore (8) holds for f and g on X.
We first prove that dns upper bounds dhaus. To this end, fix the minimizing function f the following expression:
Proof. [Theorem 322
= inf EFFFs
diso fioo
(21)
From Lemma A. we have that:
S -
sup
disoofos Siso)
(22)
=Ex
with =../0 cn/O2. From the definition of Hausdorff- distance 12 we have 23 and from have (4
13 we
draus (fo, fino) S sup [xf (z)]
(23)
NEX
draus (fe, Fars) I dhaus (fe. fia)
(24)
25 follows from 22 24 proving that diso upper bounds thaus within a constant factor c.
drams ( FaTS)= S e (J,
(25)
For the converse claim that draus upper bounds diso, once again fix the fiaus that minimizes the following expression:
dhaus (fo. Fars) sup [lfo(z)) -fams (x))
(26)
xEX
Next, for the four points fo())) fo(x2), fhim (11)). and fimm (I22, apply the triangle inequality via to get
[1fo(01) - S (x1 I|++ || (x0) fram (Iz2)l+
[1fa(z)) fo(xx2)l
(27)
[ime (x2) - fo (xx2))
f (x1) - finma (12))l+)
2 sup [[)) Shims (x))
(28)
2cX
12

---

Published as a conference paper at ICLR 2024
It is worth noting that (28) holds for all 21,22 E X. Furthermore, swap fo and fhas in 28 and use (6) to get 29 and thus (30).
diso (fos Shaus)
(29)
l1fo(z1) - fo(x2))l 111 (21) - h (22))]
sup 21 22E2
Adhaus(fer (fo, FoTs) diso Foo S (Sa S 2dhaus (Jo; F FaTs)
2dhaus
(30)
30 proves that doaus upper bounds dıo within a constant factor of Thus prove that dhaus and dise upper bound each other within constant factors.
B PROOF OF THEOREM 3.3
Proof. [Theorem] 3.3 Here, we present detailed proof for the theorem using equations (31 42
From the definition of diso in 31.. we introduce the anchor, positive, and negative triplet (æ,, x+ x=)) in (32) by re-labelling 5 Recognizing that 22 either have the same different label from F1. we re-label + x or + and pick the max of these distances for any given triplet.
dso FaTs) inf f-FFats 21
sup
[l.6(z1) fo (+2))) (21) ft (x2))]
(31)
max [I[((()) fa(x f1l==11- - f | - f M()
inf f"EFurs zart
sup
(32)
Inequality (33) follows from max(a, b) - a + b for positive a,
sup [[o(a]) fo(x (z) - (ettt|| + -100000) fa(e))) (1/" - (x
< inf GPoTs
(33)
Now fix the f that minimizes positive and the second term (34b) is negative.
33
We next prove via contradiction that the first term (34a
[[)())) -
(34a)
[lfe(x)
(34b)
There are four cases we must consider here, as we treat the zero case as either positive or negative.
Case 1: (3a)) is positive, (34b) is positive. Denoting this as ++, four cases (1 ++),
(2: --:--), (3: +). (4: + Now we prove by contradiction that case 4 is the only valid one.
Case 1(++): Consider the function (x) (1 + 8)f where 8 > 0 is small constant. Then Lo, ft) < doolfoo J'), contradicting the statement that f minimizes d
Case 2( -)= )): Consider the function (x)
5) (z) where 8 > 0 is small constant. Then dnoofo ft) < de f*), contradicting the statement that f" minimizes d
Case 6(++): We can algebraically rearrange
33 to get:
(x) (*
- f (lf((x) fo(x + [1fo(x) - fo(a 2
(35)
(x) - -frt) - fx 50
(36)
(((]t( - fo(x))]l) 20
(37)
13

---

Published as a conference paper at ICLR 2024
36 comes from the definition of f* Triplet-Separater function; then (37) comes from combin- ing (35) and (36). However, this means that the triplet that maximizes the expression has negative triplet loss, therefore there must be some other f2 with smaller value. This contradicts the state- ment that / minimizes dia.-
With Cases 1, 2, and 3 eliminated, only have Case 4 and all the cases (00, +0, 0++, 0-). We note that the cases -0 and 0+ can be dis-proven using the same logic as Case 3. This leaves the four following valid cases (00, 0-, +0, +-), where we can connect back to (33 and write:
sup [lfo(()) - fo
(x
[1f((=)) fo( -f(l -1f f
(38)
[lfo(x) - fo -1 (l) - fo( - 1- f (1)
= sup
2,2 x
(39)
Note that (39) resembles the triplet loss. The triplet loss for f* cannot dominate the maximum triplet loss for fo. otherwise would contradict the statement that f minimizes the isometric error, giving us:
- -((F(()--((=))--00000-----------
sup [1fo(x) fo()))-) - So [Ill a.at a
(40)
(41)
Using 440). we have the following relation with respect to (39).
S 2 sup 3.
[lfo(x) - fe(c+))ll [z) fe )ll
(42)
Note that (42) is identical to twice the expression for the triplet loss sampled by hard negative mining. Therefore the triplet loss sampled by hard negative mining upper bounds the isometric error by a constant factor of 2.
Additionally, can prove that the triplet loss sampled by hard negative mining upper bounds the isometric error. Starting from the definition of isometric error (43 inequality (44) follows from max(a, b) (a (a+bb/22
dis (ao
inf J.EF.Ts m.
sup
[1 fo( -15 ( (12))]
(43)
[1]((z) f6(=+)|- (( (/o -o66)))-000000)
fo (1 -
inf ('Eerre nartt=
sup
((
(x))
(44)
Once again fixing f", we have equality 45 by the same logic as the previous part. Inequality (46) follows from the fact that [*)*(x)) - [1.* (x )|| f -a by the definition as Tripaet-Separated.
1 sup [1fo(x) fo(x*) fo(o (1 (11f (1 f" (I)) a.zt
2
(45)
sup x.
[lfo(z) fa 11.f(()) folx \|| +
(46)
Therefore isometric error upper bounds the triplet loss sampled by hard negative mining by a con- stant factor of 2.
14

---

Published as a conference paper at ICLR 2024
C ADDITIONAL EXPERIMENTS FOR NON-ZERO Q
In the experiments shown in the main paper, we fixed a to be zero. To prove that using a nonzero does not affect the results, repeated the M5rket1501 experiments with 0.01 and 0.05, observing that our results remain consistent. See Figure for the embedding diameter vs batch size plots, which follow the same trends the a 0 experiment shown in Figure | Similarly, the embedding diameter vs dimension plots in Figure also follow similar trends to those shown by the
0 experiments in Figure 5
In addition, we also conducted experiments with a larger a = 0.1, but decided to stop there as the trained networks began to exhibit significant overfit. In particular, the validation loss values began to increase while the training loss flatlined at the C = 0.1 line. As result, the final embedding diameters on the validation data did not show any meaningful pattern, so we choose not to show those plots in the appendix.
Moximum Embbedding Distence
Moximum Embedding Distance
4
3
P-2
P-2
P=8
P=8
P-18
P-18
16
64
256
16
64
256
Batch Size (N)
Batch Size (N)
Figure 6: Embedding diameter batch size experiments with non-zero on Market dataset for dimension d 128. The left figure (a = 0.01) and right figure (a = 0.05) both show network collapse when the batch size is large (red region), and do not collapse when the batch size is smaller (green region). We note that the embedding diameters are larger when a is larger, which is somewhat to be expected. However there appears be collapse threshold around N 128 independent of which may warrant further study in a future work.
0.01
0.05
Makimum Embesdiing Diskence
Maximum Emboddinng Disaonce
2.0
3.0
2.5
2.5
2.0
0.5
16 Embedding
256
(d)
Embedding Dimension
Figure 7: Embedding diameter vs dimension experiments with non-zero a on Market 501 dataset for batch size 32 (P 8, K 4). The left (a 0.01) and right (a 0.05) both show signs of network collapse (red region) for lower dimension and larger embedding diameter (green region) for higher dimension, mirroring the experiment observations.
D ADDITIONAL EXPERIMENTS FOR CUB200, SOP, AND CARS DATASETS
In the main paper, our experiments were conducted only on the Market dataset. To show that results generalize beyond just one dataset, we have replicated the same experiments on additional datasets: Stanford Online Products (SOP) Oh Song et al. (2016). Caltech Birds (CUB200) Wah al. [2011), and Stanford Cars (CARS) Krause et al. (2013). We train Resnet18 network from scratch for each experiment with 3 repetitions for each hyperparameter combination, and leave the margin parameter 0. One difference from the main experiments is that these three datasets
15

---

Published as a conference paper at ICLR 2024
do not lend themselves to the PK -tyle sampling that Market1501 uses, without the same-class guarantees that exist for PK-style sampling. Results are shown in Figures S
fixed batch size
and
On the SOP dataset (Figure 8 we observe that networks collapse for large batch size and small embedding dimension, exactly the same as the Market-1501 dataset shown in the main paper. For the CUB and CARS datasets (Figure 9 we also observe that networks collapse for large batch size. However, when experimenting with the embedding dimension, we observed that the CUB and CARS datasets are extremely sensitive to the batch size; lower batch size would never collapse the network, and higher batch size would always collapse the network. To mitigate this sensitivity, we attempted to explore larger models with higher embedding dimensions than 1024, but were constrained by our hardware and GPU specifications.
SOP dataset
SOP dataset
Moximum Embeedding Distence
n- 1024
Moximum Embodding Distarce
N=
3.5
1.0
0.5
16
64
256
16
64
256
Batch Size (N)
Embedding Dimension In)
Figure 8: Batch size and embedding dimension experiments SOP dataset using Resnet18 and a = O. We observe that the patterns of collapse (red region) for high batch size and low embedding dimension hold for the SOP dataset.
CUB2011 dataset
dataset
Maximum Embeediing Dislance
3.0
n=128
Maximum um Embrdding Distance
2.25
n- 128
2.5
2.00
2.0
1.75
1.50
1.5
1.0
1.00
0.75
0.0
0.50
64
256
1024
16
64
256
Batch Size
Batch Size
Figure 9: Batch size experiments CUB200 and CARS dataset using Resnet18 and a 0. We
observe that the patterns of collapse (red region) for high batch size hold for both datasets.
E ADDITIONAL EXPERIMENTS WITH DIFFERENT BASE NETWORK
As our theory only assumes that an ideal a-Triplet Separated network exists in the function space parameterized by the neural net's 's architecture, it stands to reason that our theory should be somewhat In the main paper. we used a Resnet- 18 base, and in this appendix we train randomly initialized ResNet-50 architecture, GoogL architecture Szegedy et al. (2015) as well as a simple 2-layer convolutional network. The results for ResNet-50 are shown in Figure IC We do observe that the networks collapse for large batch size and small embedding dimension, just as they do using the ResNet-18 backbone.
The results for GoogLeNet are shown in Figure I1
We do observe that the networks collapse for large batch size and small embedding dimension, just as they do using the ResNet-18 backbone. We also observe few instances of network collapse for high embedding dimension. However, noted memory warnings during training due to the large size of the network, and we attribute these anomalies our hardware constraints.
16

---

Published as a conference paper at ICLR 2024
Resnet-50 backbone
ResNet-5D 500 backbone
Maximum Emoedding Distance
70
P=2
Maximum Embeediing Dislance
10
P=
50
40
20
10
16
64
256
16
64
256
1024
Batch Size (N)
Embedding Dimension (n)
Figure 10: Batch size and embedding dimension experiments Marketl dataset using ResNet-50 network and a O. observe that patterns of collapse (red region) for high batch size and low embedding dimension hold for a ResNet-50 network, just they do for Resnet-18 in Figure of Section[4]
However, we also observed couple instances of collapse for high embedding dimension, where our theory hypothesized that collapse would not occur. We note that while training the high embedding dimension networks, code raising memory warnings because the network was too large, so we suspect that these results may not be entirely accurate.
GoogLeNet backbone
GoogLeNet
Embeelsing Ditance
1.4
Moximum Emboddiing Discnn 8
1.2
1.0
0.8
P-2
P-4
0.0
P=18
16
64
256
16
64
256
1024
Batch Size (N)
Embedding Dimension (n)
Figure 11: Batch size and embedding dimension experiments on Market dataset using GoogLeNet and a = We observe that the patterns of collapse (red region) for high batch size and low embedding dimension hold for GoogLeNet architecture, just they do for Resnet-18 in the main paper. We note that the embedding dimension experiments have few outliers for d > 256. We suspect our code into memory issues.
the other hand, the results for a 2-layer convolutional network are shown in Figure 12 Like with GoogLeNet and ResNet, observe that large batch size and small embedding dimension both lead to network collapse.
17

---

Published as a conference paper at ICLR 2024
ConvNet backbone
ConvNet backbone
Maximum Embbedding Distance
Maximum Embrrdding Distanco
1.50
1.0
0.8
1.00
0.6
0.75
0.4
0.50
P-4
0.2
0.25
P=18
16 Batch Size
256
16
256
1024
Embedding Dimension
Figure 12: Batch size and embedding dimension experiments on Market1501 dataset using 2-layer Convolutional network and O. We observe that patterns of collapse (red region) for high batch size and low embedding dimension hold for 2-layer convolutional network, just as they do for Resnet- 18 in the main paper.
18


Reviews:
[{"review_id": "pgJggU850O", "reviewer": "Reviewer_QYwJ", "summary": "In this paper, the authors attempt to analyse the network collapse phenomenon associated with hard negative mining for triplet loss. Such network collapse is not omnipresent and vary depending on the task at hand. The authors attempt to explain this phenomena by drawing a equivalence between the hard negative-mining triplet loss and the Hausdorff-like distance metric by using isometric approximation. Such approximations help to establish a relationship between the network collapse and the batch size or the dimension of the embedding, which provide insights into using different batch size or embedding dimensions for different variety of tasks across a number of tasks (such as person re-identification). Therefore the authors have provided theoretical insights as to why such collapsing happens for learning a distance metric with hard negative sampling, and ways to overcome them by performing experiments across different datasets and different backbones.", "questions": "(1) Will such approximation hold true for any other sampling strategy or loss functions as mentioned in the Weakness section?\n\n(2) In [A], the authors experiment with learnable $\\beta$'s. Can the authors more some insights as to what would happen if $\\alpha$ is also learned, instead of keeping it fixed.\n\n(3) Have the authors done any experiments on face recognition datasets similar to [B, C]? It will be interesting to see if the proposed explanations hold true for experiments on face recognition too.\n\n[A] Wu, Chao-Yuan, et al. \"Sampling matters in deep embedding learning.\" ICCV 2017.\n\n[B] Wang, Hao, et al. \"Cosface: Large margin cosine loss for deep face recognition.\" CVPR 2018.\n\n[C] Deng, Jiankang, et al. \"Arcface: Additive angular margin loss for deep face recognition.\" CVPR 2019.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The connection between network collapse with the batch size or embedding dimensions; using isometric approximation is novel and interesting.\n\nThe authors have provided a detailed analysis of their proposed approximation between the hard negative-mining triplet loss and the Hausdorff-like distance metric along with detailed proofs in the appendix.\n\nThe authors have provided a substantial number of experiments across different datasets and different network backbones to show the effectiveness of their proposed work.", "weaknesses": "The major weakness of the paper is only showing the effectiveness of their proposed method for hard negative mining strategies for learning the distance metric. There have a considerable number of new sampling strategies which improve upon hard negative mining, especially aimed to tackle the slow convergence rate and the network collapsing phenomena. A different variety of loss functions have also been developed  to tackle the above mentioned issues. Therefore the impact of this paper is limited by the choice of the single \"hard mining strategy\". The methods in [A, B, C, D] aim to reduce the dependency of the batch size or the size of the embedding. A similar study has also been conducted in [E]. These methods need not always provide any theoretical explanations (which is a big plus for this paper), but they attempt to solve and tackle similar issue (network collapse). So it will be interesting if such equivalence can be drawn with such methods, which is missing in the paper.\n\n[A] W. Zheng, J. Lu and J. Zhou, \"Deep Metric Learning With Adaptively Composite Dynamic Constraints,\" TPAMI 2023.\n\n[B] Zheng, Wenzhao, et al. \"Dynamic metric learning with cross-level concept distillation.\" ECCV 2022.\n\n[C] Zhang, Borui, et al. \"Attributable visual similarity learning.\" CVPR 2022.\n\n[D] Zheng, Wenzhao, Jiwen Lu, and Jie Zhou. \"Deep metric learning via adaptive learnable assessment.\" CVPR 2020.\n\n[E] Musgrave, Kevin, Serge Belongie, and Ser-Nam Lim. \"A metric learning reality check.\"  ECCV 2020.", "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": "", "extra_scores": {}}, {"review_id": "SMCYBfp9D4", "reviewer": "Reviewer_Mw75", "summary": "This paper delves into the issue of triplet loss collapse, offering a theoretical insight into its causes. The proposed method employs isometric approximation to demonstrate that hard example mining is effectively equivalent to minimizing a distance akin to the Hausdorff distance. Experimental results on two widely used metric learning datasets reveal that network collapse tends to occur with either a large batch size or a small embedding size.", "questions": "See weakness.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- This paper addresses a significant issue related to triplet loss collapse, a topic of keen interest within the research community.\n\n- The paper offers a novel theoretical perspective on the problem of triplet loss collapse by introducing the innovative concept of isometric approximation, contributing a fresh angle to this field.", "weaknesses": "- It would be beneficial to see a more thorough analysis of various triplet loss variants, particularly with regard to different triplet sampling methods. This in-depth examination is essential for a comprehensive understanding of the effectiveness of triplet loss in different settings.\n\n- The figures and examples in this paper suffer from both low quality and a lack of informativeness. They do not effectively convey the discussed settings, making it difficult for readers to comprehend the content.\n\n- The experimental evaluations in this paper are notably limited, making it challenging to substantiate the claims put forth. For instance, the use of a very large batch size with semi-hard triplets in FaceNet raises questions that require further clarification or justification.", "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": "", "extra_scores": {}}, {"review_id": "ZKgkZPK8qR", "reviewer": "Reviewer_hpyY", "summary": "The paper focuses on addressing the issue of network collapse in deep metric learning, specifically in the context of the triplet loss. Network collapse refers to a situation where the network projects all data points onto a single point, leading to ineffective embeddings. The authors propose utilizing the mathematical theory of isometric approximation to establish an equivalence between the triplet loss with hard negative mining and an optimization problem that minimizes a Hausdorff-like distance. This theoretical framework provides the justification for the empirical success of hard negative mining in preventing network collapse. Experimental results on multiple datasets and network architectures validate the theoretical findings.", "questions": "See Weaknesses", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "-\tThe paper offers a theoretical framework based on isometric approximation theory to explain the behavior of the triplet loss with hard negative mining. This provides a solid foundation for understanding and addressing network collapse in deep metric learning\n-\tThe paper investigates the factors that contribute to network collapse, specifically focusing on the batch size and embedding dimension. Through experiments on multiple datasets and network architectures, the authors demonstrate that larger batch sizes and smaller embedding dimensions increase the likelihood of network collapse. \n-\tThe authors conduct experiments on various datasets and network architectures, demonstrating the effectiveness of hard negative mining in preventing network collapse. The empirical results corroborate the theoretical findings and enhance the credibility of the proposed approach.", "weaknesses": "-\tThe paper primarily focuses on hard negative mining as a solution to network collapse but does not thoroughly compare its performance with alternative methods or strategies. A comprehensive comparison with other approaches would provide a more comprehensive understanding of the effectiveness of hard negative mining and its relative advantages or disadvantages compared to other techniques. Without such comparisons, it is difficult to assess the competitiveness of the proposed method.\n-\tWhile the paper presents experimental results on multiple datasets and network architectures, it does not provide precise quantitative measurements of the performance improvements achieved by preventing network collapse through hard negative mining. Without specific metrics, such as accuracy or loss values, it is challenging to assess the magnitude of the improvement or compare it with alternative approaches. Including quantitative evaluations would enhance the rigor and credibility of the proposed method.\n-\tThe absence of mining time analysis and discussion on the time complexity limits the applicability of the proposed method to real-time or time-sensitive applications. Real-time systems often require fast and efficient processing, and the computational cost of hard negative mining can be a critical factor in determining the feasibility of the approach. Considering the practical implications and performance trade-offs in real-time scenarios would enhance the relevance and applicability of the proposed method.\n-\tThe paper primarily focuses on the theoretical framework and experimental results of hard negative mining in preventing network collapse. However, the experiments are conducted on a limited set of network architectures, and it does not include widely used backbone architectures such as ResNet-50 or Inception-BN. These mainstream architectures are commonly employed in deep metric learning and computer vision tasks. The lack of evaluation on such architectures limits the generalizability and applicability of the proposed method to real-world scenarios.", "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": "", "extra_scores": {}}, {"review_id": "CCYG1roVMX", "reviewer": "Reviewer_DHxZ", "summary": "This theoretical paper discusses and analyzes the collapse problem in the Deep Metric Learning area. The author leverages the theory of isometric approximation to show an equivalence between the triplet loss sampled by hard negative mining and an optimization problem that minimizes a Hausdorff-like distance between the neural network and its ideal counterpart function. The main conclusion is equation 17, indicating that network collapse tends to happen when batch size is too large or the embedding dimension is too small. Effective experiments were conducted to visualize and support the conclusion.", "questions": "Some extended questions:\nHow is the lower bound curve (17) related to the retrieval performance?\nTriplet loss is rarely used in Self-supervised learning with a random initialization network. Maybe one of the reasons is also collapse. Can your theory explain the problem? is the DML problem similar to the SSL problem in the embedding level?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The collapse problem is a famous problem blocking DML training. Current literature misses the systematic explanation of this phenomenon. The theory of the paper is helping understand the reason behind the problem and will benefit the DML research community. \n\nThe starting point of the definition of triplet-separated accurately describes and fits the optimization of triplet loss. \nBy leveraging the isometric approximation theorem, the path to achieve the proof to the corollary 3.4 is clear and sound. \nFinally, the experiments with different settings to proof the conclusion is equation 17 is wee conducted and integrated", "weaknesses": "The illustrative examples are not clear. Figure 2 is clear on the examples. But the figure 3 is not clear.\n1. The line in figure 3 overlaps too much. would be good to redraw it.\n2. it is not clear of diso(fθ,FTS) in the figure.\n\nFigure 4 can be extended to multiple views to illustrate the progress of the collapse as the example shown in [1]. and if the diso(fθ,FTS) value can be added in the vis, it will be valued.\n\nminer issue in the typos: section 1 \"CUBwah et al. (2011))\" \n\n[1]: Hong Xuan, Abby Stylianou, Xiaotong Liu, and Robert Pless. Hard negative examples are hard but useful.InEuropeanConferenceonComputerVision, pp.126–142.Springer,2020.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)