Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem

We thank the reviewer for the constructive comments. We respond to the comments below and update the manuscript accordingly.

$\mathbf Q_1$: "...figure 3 is not clear"

$A_1$: Thank you for the feedback. We have updated the figure to remove extraneous lines. The difference in the distance metric should now be more evident. Further, we improved the clarity of the object marked by $d_\textrm{iso}(f_\theta,\mathcal F_{TS})$ by removing the clutter of lines surrounding the text in the figure. We hope this addresses the illustration in Fig. 3.

$\mathbf Q_2$: "Figure 4 can be extended to multiple views to illustrate..."

$A_2$: Thank you for the suggestion and for the reference. We have modified our Fig. 4 to match the style in [1]. Additionally, we compute $d_\textrm{haus}(f_\theta,\mathcal F_{TS})$ as $d_\textrm{haus}(f_\theta, f^*)$ using the approximated $f^*$ function and have marked the function value in Fig. 4 to provide additional context.

$\mathbf Q_3$: "typos: section 1..."

$A_3$: Thank you for pointing this out. We have fixed the typo in the revised version.

$\mathbf Q_4$: "How is the lower bound curve (17) related to the retrieval performance?"

$A_4$: We are unaware of any strong theoretical connection between (17) and retrieval performance. There is no guarantee that retrieval performance will always improve as the diameter increases. However, in the converse, we know retrieval performance will be negatively impacted when the diameter goes to zero, indicating network collapse.

$\mathbf Q_5$: "Triplet loss is rarely used in Self-supervised learning... is the DML problem similar to the SSL problem in the embedding level?"

$A_5$: The reviewer points to an interesting connection between self-supervised learning (SSL) and deep metric learning (DML) at the embedding level. While we acknowledge a similarity in how SSL and DML use contrastive loss, there exists a difference in the structures of their respective datasets. We believe exploring and presenting the extension of our theory to SSL will likely need new terminology and careful consideration in the proofs, and thus we keep this for future work.

We thank the reviewer for the constructive comments. We respond to the comments below and update the manuscript accordingly.

$\mathbf Q_1$: "...comparison with other approaches would provide a more comprehensive understanding..."

$A_1$: Thank you for the question. As we state in the fifth paragraph of section 1, this work aims to explain why network collapse happens by using the theory of isometric approximation to draw an equivalence between the triplet loss with hard negative mining and Hausdorff-like distance metric. We would like to clarify that our paper does not propose a new method, and the performance of the triplet loss with hard negative mining has already been recorded in other papers.

Prior works such as [1] point to a network collapse in the context of hard negative mining while the authors in [2] show the absence of network collapse with hard negative mining for a similar dataset. To address these seemingly contradictory results, our work offers a systematic explanation for network collapse, its causes, and how to avoid it in the context of triplet loss with hard negative mining.

[1] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 815–823, 2015.

[2] Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person reidentification. arXiv preprint arXiv:1703.07737, 2017.

$\mathbf Q_2$: "Including quantitative evaluations would enhance the rigor and credibility of the proposed method."

$A_2$: Continuing our response from the previous section, the focus of this work is to provide a mathematical justification for network collapse and not present a new method to perform hard negative mining. Consequently, our experiments are directed to corroborate the likelihood of network collapse when the batch size is large or when the embedding dimension is small and not to provide precise quantitative measurements for hard negative mining.

$\mathbf Q_3$: "The absence of mining time analysis and discussion on the time complexity..."

$A_3$: We feel that the mining time analysis is not relevant to this work. While it is true that discussion on time complexity is an essential factor when proposing new triplet sampling methods, our work primarily investigates the phenomenon of network collapse on an existing method, i.e., hard negative mining.

$\mathbf Q_4$: "...experiments are conducted on a limited set of network architectures..."

$A_4$: While our initial submission reports findings from three different network architectures (ResNet-18, GoogLeNet, and a 2-layer convnet), we have now conducted experiments with ResNet-50 as the backbone, as per the reviewer's suggestion. The results from this new experiment corroborate our claims that network collapse is more likely when the batch size is large or when the embedding dimension is small. We have now included the details of these results in Appendix E and highlighted the changes in yellow. We thank the reviewer for the suggestion, since including these additional results has surely strengthened our manuscript.

We thank the reviewer for the constructive comments. We respond to the comments below and update the manuscript accordingly.

$\mathbf Q_1$: "...a more thorough analysis of various triplet loss variants..."

$A_1$: While our work focuses on hard negative mining on the triplet loss, it is worth noting that the theory of isometric approximation as used in this manuscript is independent of the triplet loss. Consequently, it can be applied to any system utilizing the Euclidean metric, for instance the pairwise contrastive loss ($\mathcal{L} = |x - x^+| - [\alpha - |x-x^-|]_+$) or the margin loss ($\mathcal{L}=\left[|x-x^+| + \alpha - \beta\right]\_+ + [-|x-x^-| + \alpha + \beta]\_+$).

On the other hand, the fundamental reason for the choice of hard negative mining is that it resembles a $\max_{x,x^+,x^-} \mathcal L(x, x^+, x^-)$ type of operation, which via the isometric approximation theorem, can be directly connected with our defined Hausdorff-like metric $d_\textrm{haus}(f_1, f_2) = \max_x d(f_1(x), X_{f_2}^i)$ or $\max_x d(f_2(x), X_{f_1}^i)$, because they both use max operations. To rigorously examine other triplet sampling methods, we would likely need a careful exploration of functions that naturally connect with those other sampling methods, and thus we keep this for future work.

$\mathbf Q_2$: "The figures and examples in this paper suffer from both low quality and a lack of informativeness..."

$A_2$: Thank you for the feedback. We have clarified the caption of Fig. 2 to better describe the example toy system.

We have removed extraneous lines from Fig. 3, which now exclusively focuses on a single example for illustrating $d_\textrm{iso}$. This should remove any confusion from multiple examples in our prior version and should make the difference in the distance metric more evident. Further, we improved the clarity of the object marked by $d_\textrm{iso}(f_\theta,\mathcal F_{TS})$ by removing the clutter of lines surrounding the text in the figure. We hope this improves the clarity around Fig. 3.

With respect to Fig. 4, we have added a sequential collapse of a solution with insights into how the function looks at intermediate steps. We have also added annotations illustrating the decrease of $d_\textrm{haus}(f_\theta, \mathcal F_{TS})$ for their respective functions. We believe this provides additional context to our figures and examples. If there is some other detail that the reviewer is pointing to, we would be happy to address that as well.

$\mathbf Q_3$: "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."

$A_3$: Thank you for the feedback. Quoting from the FaceNet [1] paper, ``Selecting the hardest negatives can in practice lead to bad local minima early on in training, specifically it can result in a collapsed model (i.e. f(x) = 0).'' FaceNet [1] work uses this fact as a motivating example to propose semi-hard triplets to work with very large batch sizes. Our work supports and justifies their observations that very large batch sizes in combination with hard negative mining adversely affects the network.

In this work, we provide rigorous mathematical analysis to show how large batch sizes and small embedding dimensions adversely affect hard negative mining. Additionally, we present experimental verification with the person re-identification dataset (Market-1501) reconcile the findings of FaceNet [1], where a batch size in the order of thousands led to network collapse, and [2] where a batch size of N = 72 showed no network collapse. We further support our predictions via experiments spanning three additional datasets (SOP, CARS, and CUB200) and three different network architectures (ResNet-18, GoogLeNet, and a 2-layer convnet). We are happy to conduct additional experiments on any specific datasets or network architectures to expand the breadth of our verification, as per the reviewer's additional requests.

Furthermore, our recent experiments with ResNet-50 as the backbone resonate with the findings from the previous three network architectures. We hope the experimental evaluation is now adequate to substantiate the claims put forth in the manuscript. We are happy to conduct supplementary experiments on specific datasets or network architectures to expand the breadth of our verification per the reviewer's additional requests.

[1] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 815–823, 2015.

[2] Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person reidentification. arXiv preprint arXiv:1703.07737, 2017.

$\mathbf Q_2$: "Will such approximation hold true for any other sampling strategy or loss functions as mentioned in the Weakness section?"

$A_2$: We thank the reviewer for the question. Continuing our response from the previous section, the theory of isometric approximation as used in this manuscript is independent of the triplet loss. Further, the sampling strategy and loss function are also somewhat independent in that one can freely swap the sampling strategy or the loss function. For instance, if the isometric approximation holds for a given combination of sampling strategy A + loss function B, we expect it to hold for hard negative mining + loss function B and also for sampling strategy A + triplet loss.

$\mathbf Q_3$: "Can the authors more some insights as to what would happen if $\alpha$ is also learned?"

$A_3$: The $\beta$ in [A] fulfills a different role from the margin parameter $\alpha$ in the triplet loss for our paper. While we have not performed experiments with learnable $\alpha$, we expect that because $\mathcal L_{\alpha=0}(x) \leq \mathcal L_{\alpha}(x)$ for all $\alpha > 0$, the network would always learn $\alpha=0$. Increasing $\alpha$ can never decrease the loss value, so naturally, it should always go to zero without some forcing term. It is worth noting that the margin $\alpha$ in [A] exhibits a similar behavior and is also not treated as a learnable parameter. Since we do not have a boundary term $\beta$ in our formulation, we hope that our response on learning the margin parameter $\alpha$ addresses the query above.

$\mathbf Q_4$: "Have the authors done any experiments on face recognition datasets..."

$A_4$: We thank the reviewer for the suggestion. Our recent investigation with the face recognition dataset from [B, C] (Labeled faces in the Wild) reveals a trend similar to the proposed explanations, where the likelihood of network collapse increases with an increase in the batch size. Specifically, the final embedding diameter of 2.10 with a batch size of 4 decreases to a value of 0.68 when the batch size is increased to 512, indicating network collapse.

We thank the reviewer for the constructive comments. We respond to the comments below and update the manuscript accordingly.

$\mathbf Q_1$: "The major weakness of the paper is only showing the effectiveness of their proposed method for hard negative mining strategies..."

$A_1$: Thank you for this insightful feedback.

While our work focuses on hard negative mining on the triplet loss, it is worth noting that the theory of isometric approximation as used in this manuscript is independent of the triplet loss. Consequently, it can be applied to any system utilizing the Euclidean metric, for instance the pairwise contrastive loss ($\mathcal L = \|x-x^+\| - [\alpha - \|x-x^-\|]_+$) or the margin loss ($\mathcal L = [\|x-x^+\| + \alpha - \beta]\_+ + [-\|x-x^-\| + \alpha + \beta]\_+$). As both these loss functions essentially use a difference in distances, we can use the isometric approximation theorem to connect to other potentially useful functional forms which may reveal interesting theoretical conclusions.

On the other hand, the fundamental reason for the choice of hard negative mining is that it resembles a $\max_{x,x^+,x^-} \mathcal L(x, x^+, x^-)$ type of operation, which via the isometric approximation theorem, can be directly connected with our defined Hausdorff-like metric $d_\textrm{haus}(f_1, f_2) = \max_x d(f_1(x), X_{f_2}^i)$ or $\max_x d(f_2(x), X_{f_1}^i)$ because they both use max operations.

Following the unified metric learning formulation defined by Zheng et al. [A] in eq (7), a different mining strategy would require some change to the Hausdorff-like metric. In particular, we suspect that rather than $\max_x$ we would have some function dependent on the chosen graph $G(\mathbf Y, \mathbf P, \pi(\mathbf y, \mathbf p))$ and distribution $\pi(\mathbf Y,\mathbf P)$ from [A]. But it does feel possible that a connection is waiting to be made there.

We thank the reviewer for this feedback. We have amended our conclusion with these insights and highlighted the changes in yellow.