Robust Similarity Learning with Difference Alignment Regularization

Thank you for your positive and constructive comments! Our point-by-point responses are given below.

---

Comment_1: Calculating the higher-order difference requires complex calculation complexity. It would be better to report the running time comparison of different methods with some specific dataset to show the effectiveness.

Response_1: Thank you for the great suggestion! Here we would like to provide the training time comparison of our DASL and the baseline methods (SimCLR and SwAV) on the CIFAR-10 and ImageNet-100 datasets. Specifically, we use two NVIDIA TeslaV100 GPUs to train our models based on SimCLR and SwAV with 100 epochs, respectively. For each case, we set the batch size to 512 and 1024.

The table above reveals that the introduction of the proposed regularizer causes very little increase in time consumption. This is because the gradient calculation of the CTV norm is independent of the size of the training data, thereby keeping the training time well within practical limits. We have also added the above time comparison in the revised appendix.

---

Comment_2: There are also other ways to enhance inter-class compactness in the metric learning field, e.g., [1-3]. Please discuss the differences between the current algorithm and these works. [1] Learning multiple local metrics: Global consideration helps, TPAMI 2019. [2] Deep metric learning with angular loss, ICCV 2017. [3] What Makes Objects Similar: A Unified Multi-Metric Learning Approach, TAPMI 2018.

Response_2: Thank you for the comment! We agree with the reviewer that the three works [1-3] also consider the inter-class similarities. However, our work differs substantially from the above three works, as here [1] and [3] mainly focus on learning a global metric merged from multiple local metrics to better capture the inter-class similarities in different contextual scenarios. Furthermore, [2] constructs a new loss function to mitigate the incorrect reduction of inter-class distances caused by the scale variance, and it does not consider the variation of the correct inter-class distances. In comparison, we propose a general regularization technique to encourage those correct inter-class differences to be as close as possible. These distinctions set our method apart from the three mentioned methods in terms of both motivation and methodology.

We have cited the above three works and also added the corresponding discussions in our revised paper.

---

Comment_3: It would be better to report the sensitivity with regard to the regularization parameter lambda. Does the change of it heavily influence the final performance? What is the default choice?

Response_3: Thank you for the suggestion! In our appendix, we have already provided the corresponding description and discussion for the default value and sensitivity of the regularization parameter $\lambda$.

To be more specific, we recommend a value of $\lambda$ equal to 0.5, as it consistently provides the best performance across a wide range of tasks. Additionally, we conducted experiments on STL-10 and CIFAR-10 datasets to thoroughly investigate the parametric sensitivity of $\lambda$. We systematically varied $\lambda$ within the range of [0.01, 5] and recorded the classification accuracy of our method under different conditions (batch sizes of 256, 512, and 1024, and 100 training epochs). The table presenting the results shows that the accuracy of our method exhibits a variation of less than 2% across these different parameter settings.

These results clearly demonstrate that the regularization parameter $\lambda$ is very stable within a given range, and thus the hyper-parameter of our method can be easily tuned in practical use.

Thank you for your positive and constructive comments! Our point-by-point responses are provided below.

---

Comment_1: Could you give some insight as to why it's different from the standard contrastive loss? The standard contrastive loss is $L=ReLu(d^{+}-\delta^{+})+ReLu(\delta^{-}-d^{-})$, where $d^{+}$ denotes the distance between positive pairs, $d^{-}$ denotes the distance between negative pairs, $\delta^{+}$ denotes the positive margin and $\delta^{-}$ denotes the native margin. This loss repels features of negative pairs until they are $\delta^{-}$ away from each other. This would also satisfy your loss function. Could your loss function be doing something similar to enforcing a negative margin?

Response_1: As the reviewer suggested, the conventional contrastive similarity loss can indeed ensure that all negative pairs are $\delta^{-}$-away from each other, i.e., the inter-class distances are always larger than $\delta^{-}$. However, this effect is still quite different from our primary goal. Although the ReLu function can effectively penalize the incorrect inter-class distances $d^{-}$ that are smaller than $\delta^{-}$, it is still unclear how the correct inter-class distances are distributed in $(\delta^{-}, +\infty)$ because there is no constraint any more for these correct inter-class distances which are larger than $\delta^{-}$ (i.e., $ReLu(\delta^{-}-d^{-})$ is always 0). Therefore, we still need difference alignment regularization (DAR) to explicitly promote consistent representation differences.

Furthermore, in our original manuscript, we provided experiments to demonstrate that our DAR can significantly improve the representative contrastive loss ProxyAnchor on the CAR, CUB, and SOP datasets. Meanwhile, the numerical experiments in Fig. 8 of Appendix A.3 also validate that the conventional ProxyAnchor fails to obtain the difference-aligned features. During the training phase, the CTV-norm of ProxyAnchor is generally located around a relatively large value. In comparison, our method can minimize the empirical loss under the condition of a very small CTV-norm value.

In summary, our ultimate learning objective is different from directly enforcing a negative margin by contrastive loss, because we can further constrain those correct inter-class distances that lie in $(\delta^{-}, +\infty)$.

---

Comment_2: Minor issues: complicated notation and trivial description of Theorem 2.

Response_2: Thank you for pointing out the above problems! We have tried our best to further simplify the notation, and we will also move Theorem 2 to Appendix in the camera-ready version.

---

Comment_3: Minor issue: Theorem 4 ignores the tradeoff between generalization and approximation (you say that higher lambda leads to a smaller upper-bound on the generalization gap, but a higher lambda also means $\mathcal{L}$ is a bad approximation of what you actually want to minimize.)

Response_3: Yes, we agree with the reviewer that the tradeoff between model fitting and model generalization is a longstanding and critically important problem in machine learning. In our case, it is also very difficult to provide theoretical analyses to answer the optimal value of $\lambda$. However, we had provided empirical investigations to show that the modestly large $\lambda$ does not harm the fitting result and also obtains a good empirical risk $\mathcal{L}$.

Specifically, from Fig. 8 we can clearly observe that the empirical loss $\mathcal{L}$ (for model fitting) can still be well minimized and converge to a stable point even though the regularization parameter $\lambda$ is increased from 0 to 0.5. It means that the value of $\mathcal{L}$ in Theorem 4 can still be kept at a small value when we increase the parameter $\lambda$. In this case, the shrinking of the error bound will give a good generalization ability (i.e., the small $\widetilde{\mathcal{L}}$).

Thanks for your positive and insightful comments! Our explanation and clarification can be found as follows.

---

Comment_1: The only concern I have is about the theoretical analysis, especially thm 3 and 4. The two theorems assumed that $x$, $z$, $\widehat{x}$, and $\widehat{z}$ are from the same distribution. I wonder if the assumption is so strong that makes the result meaningless in the real world. The authors are clearly more interested in regularizing the differences of inter-class feature differences. In that case, the samples are clearly from different distributions, as the authors assumed in the conceptual experiments in Fig. 2.

Response_1: Thank you for the detailed comment! Please allow us to clarify that in each sub-figure of Fig. 2, all three different clusters are considered to follow a single overall distribution with mixed Gaussians (i.e., each sub-figure is a Gaussian mixture model (GMM)), and thus both the training and test examples are sampled from such a single distribution (as we had discussed in Appendix A.1). In this case, the data points $x$ and $\widehat{x}$ (as well as $z$ and $\widehat{z}$) may come from the same cluster or from two different clusters, but they are sampled from the same distribution of the corresponding GMM.

We totally agree with the reviewer that the independent and identically distributed (i.i.d.) assumption is indeed very important for our theoretical analyses. However, here the i.i.d. assumption on the data points $x$, $z$, $\widehat{x}$, and $\widehat{z}$ is actually a relatively mild condition that has been commonly applied in many classical machine learning tasks. The conventional analyses [R1-R3] on generalization error are also based on the i.i.d. assumption, so we simply follow this common practice to perform our theoretical analyses in Theorem 3 and 4.

In summary, our i.i.d. assumption in Theorem 3 and Theorem 4 is generally mild, and it is also consistent with the practical setting of our experiments. Therefore, we think that the analytical results are still meaningful in real-world applications.

Reference

[R1]. Generalization Bounds for Metric and Similarity Learning, MLJ’16.

[R2]. A Theoretical Analysis of Contrastive Unsupervised Representation Learning, ICML’19.

[R3]. Curvilinear Distance Metric Learning, NeurIPS’19.

Thank you for your appreciation of the novelty, theoretical analyses, and experimental results of our paper! Thanks also for your very insightful and constructive suggestions! Our point-by-point responses are as follows.

---

Comment_1: Inconsistency between theoretical justification and method. Theorem 4 presents a bound on the generalization gap based on $\max{d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})}$, a metric akin to first-order measurement of feature distance. Despite the notion that smoothness of discrepancy could minimize the largest $d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})$ by pulling it towards the majority, this mechanism inherently relies on first-order measurement. Consequently, the theorem does not robustly support the paper's primary claim.

Response_1: First of all, we agree with the reviewer that the error bound in Theorem 4 is partly based on the first-order measurement (i.e., the distance $d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})$), and the higher-order difference is also defined as the consistency between first-order differences, so minimizing our CTV-norm regularizer will naturally affect the first-order difference. However, this does not mean that the existing first-order approaches can directly achieve the difference-aligned effect, because they do not explicitly constrain the variation of pairwise differences. In this case, as an important factor of the error bound, $\max{d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})}$ tends to become a large value which increases the corresponding generalization error.

In comparison, by introducing our CTV-norm regularizer, the feature embedding is learned from a shrunken hypothesis space (i.e., the regularized learning objective $\mathcal{F}(\boldsymbol{\varphi})$ as we mentioned in Theorem 4), so that $\max{d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})}$ is well reduced to produce a tighter error bound. Meanwhile, we want to further clarify that the error bound in Theorem 4 not only depends on the maximal distance $\max{d_{\boldsymbol{\varphi}}(\boldsymbol{t}, \widehat{\boldsymbol{t}})}$, but is also influenced by the parameter $\lambda$. The introduction of our new regularizer will increase $\lambda$ from 0 to a default value of 0.5, and thus further reducing the final error bound.

We agree with the reviewer that there is usually a real gap between the theoretical results and the effectiveness of the method, and such a gap commonly exists in many existing theoretical analyses of machine learning. In our case, we simply follow the common practice of investigating the upper bound of the generalization error, so that we can have a guarantee for the worst case of model generalizability.